EDL: add support for new EDL file format

The timeline code previously added to support Matroska ordered
chapters allows constructing a playback timeline from segments picked
from multiple source files. Add support for a new EDL format to make
this machinery available for use with file formats other than Matroska
and in a manner easier to use than creating files with ordered
chapters.

Unlike the old -edl option which specifies an additional file with
edits to apply to the video file given as the main argument, the new
EDL format is used by giving only the EDL file as the file to play;
that file then contains the filename(s) to use as source files where
actual video segments come from. Filename paths in the EDL file are
ignored. Currently the source files are only searched for in the
directory of the EDL file; support for a search path option will
likely be added in the future.

Format of the EDL files

The first line in the file must be "mplayer EDL file, version 2".
The rest of the lines belong to one of these classes:
1) lines specifying source files
2) empty lines
3) lines specifying timeline segments.

Lines beginning with '<' specify source files. These lines first
contain an identifier used to refer to the source file later, then the
filename separated by whitespace. The identifier must start with a
letter. Filenames that start or end with whitespace or contain
newlines are not supported.

On other lines '#' characters delimit comments. Lines that contain
only whitespace after comments have been removed are ignored.

Timeline segments must appear in the file in chronological order. Each
segment has the following information associated with it:
- duration
- output start time
- output end time (= output start time + duration)
- source id (specifies the file the content of the segment comes from)
- source start time (timestamp in the source file)
- source end time (= source start time + duration)
The output timestamps must form a continuous timeline from 0 to the
end of the last segment, such that each new segment starts from the
time the previous one ends at. Source files and times may change
arbitrarily between segments.

The general format for lines specifying timeline segments is
[output time info] source_id [source time info]
source_id must be an identifier defined on a '<' line. Both the time
info parts consists of zero or more of the following elements:
1) timestamp
2) -timestamp
3) +duration
4) *
5) -*
, where "timestamp" and "duration" are decimal numbers (computations
are done with nanosecond precision). Whitespace around "+" and "-" is
optional. 1) and 2) specify start and end time of the segment on
output or source side. 3) specifies duration; the semantics are the
same whether this appears on output or source side. 4) and 5) are
ignored on the output side (they're always implicitly assumed). On the
source side 4) specifies that the segment starts where the previous
segment _using this source_ ended; if there was no previous segment
time 0 is used. 5) specifies that the segment ends where the next
segment using this source starts.

Redundant information may be omitted. It will be filled in using the
following rules:
- output start for first segment is 0
- two of [output start, output end, duration] imply third
- two of [source start, source end, duration] imply third
- output start = output end of previous segment
- output end = output start of next segment
- if "*", source start = source end of earlier segment
- if "-*", source end = source start of a later segment

As a special rule, a last zero-duration segment without a source
specification may appear. This will produce no corresponding segment
in the resulting timeline, but can be used as syntax to specify the
end time of the timeline (with effect equal to adding -time on the
previous line).

Examples:
----- begin -----
mplayer EDL file, version 2
< id1 filename

  0 id1 123
100 id1 456
200 id1 789
300
-----  end  -----
All segments come from the source file "filename". First segment
(output time 0-100) comes from time 123-223, second 456-556, third
789-889.

----- begin -----
mplayer EDL file, version 2
< f filename
f  60-120
f 600-660
f  30- 90
-----  end  -----
Play first seconds 60-120 from the file, then 600-660, then 30-90.

----- begin -----
mplayer EDL file, version 2
< id1 filename1
< id2 filename2

+10 id1 *
+10 id2 *
+10 id1 *
+10 id2 *
+10 id1 *
+10 id2 *
-----  end  -----
This plays time 0-10 from filename1, then 0-10 from filename1, then
10-20 from filename1, then 10-20 from filename2, then 20-30 from
filename1, then 20-30 from filename2.

----- begin -----
mplayer EDL file, version 2
< t1 filename1
< t2 filename2

t1 * +2            # segment 1
+2 t2 100          # segment 2
t1 *               # segment 3
t2 *-*             # segment 4
t1 3 -*            # segment 5
+0.111111 t2 102.5 # segment 6
7.37 t1 5 +1       # segment 7
-----  end  -----
This rather pathological example illustrates the rules for filling in
implied data. All the values can be determined by recursively applying
the rules given above, and the full end result is this:
+2         0-2                 t1  0-2              # segment 1
+2         2-4                 t2  100-102          # segment 2
+0.758889  4-4.758889          t1  2-2.758889       # segment 3
+0.5       4.4758889-5.258889  t2  102-102.5        # segment 4
+2         5.258889-7.258889   t1  3-5              # segment 5
+0.111111  7.258889-7.37       t2  102.5-102.611111 # segment 6
+1         7.37-8.37           t1  5-6              # segment 7

2 files changed, 398 insertions, 18 deletions

diff --git a/timeline/tl_edl.c b/timeline/tl_edl.c
new file mode 100644
index 0000000000..99b9ddad82
--- /dev/null
+++ b/timeline/tl_edl.c
@@ -0,0 +1,398 @@
+/*
+ * This file is part of MPlayer.
+ *
+ * MPlayer is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * MPlayer is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with MPlayer; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <inttypes.h>
+#include <ctype.h>
+
+#include "talloc.h"
+
+#include "mp_core.h"
+#include "mp_msg.h"
+#include "libmpdemux/demuxer.h"
+#include "path.h"
+#include "bstr.h"
+#include "mpcommon.h"
+
+
+struct edl_source {
+    struct bstr id;
+    char *filename;
+    int lineno;
+};
+
+struct edl_time {
+    int64_t start;
+    int64_t end;
+    bool implied_start;
+    bool implied_end;
+};
+
+struct edl_part {
+    struct edl_time tl;
+    struct edl_time src;
+    int64_t duration;
+    int id;
+    int lineno;
+};
+
+static int find_edl_source(struct edl_source *sources, int num_sources,
+                           struct bstr name)
+{
+    for (int i = 0; i < num_sources; i++)
+        if (!bstrcmp(sources[i].id, name))
+            return i;
+    return -1;
+}
+
+void build_edl_timeline(struct MPContext *mpctx)
+{
+    const struct bstr file_prefix = BSTR("<");
+    void *tmpmem = talloc_new(NULL);
+
+    struct bstr *lines = bstr_splitlines(tmpmem, mpctx->demuxer->file_contents);
+    int linec = MP_TALLOC_ELEMS(lines);
+    struct bstr header = BSTR("mplayer EDL file, version ");
+    if (!linec || !bstr_startswith(lines[0], header)) {
+        mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Bad EDL header!\n");
+        goto out;
+    }
+    struct bstr version = bstr_strip(bstr_cut(lines[0], header.len));
+    if (bstrcmp(BSTR("2"), version)) {
+        mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Unsupported EDL file version!\n");
+        goto out;
+    }
+    int num_sources = 0;
+    int num_parts = 0;
+    for (int i = 1; i < linec; i++) {
+        if (bstr_startswith(lines[i], file_prefix)) {
+            num_sources++;
+        } else {
+            int comment = bstrchr(lines[i], '#');
+            if (comment >= 0)
+                lines[i] = bstr_splice(lines[i], 0, comment);
+            if (bstr_strip(lines[i]).len)
+                num_parts++;
+        }
+    }
+    if (!num_parts) {
+        mp_msg(MSGT_CPLAYER, MSGL_ERR, "No parts in timeline!\n");
+        goto out;
+    }
+
+    // Parse source filename definitions
+
+    struct edl_source *edl_ids = talloc_array_ptrtype(tmpmem, edl_ids,
+                                                      num_sources);
+    num_sources = 0;
+    for (int i = 1; i < linec; i++) {
+        struct bstr line = lines[i];
+        if (!bstr_startswith(line, file_prefix))
+            continue;
+        line = bstr_cut(line, file_prefix.len);
+        struct bstr id = bstr_split(line, WHITESPACE, &line);
+        if (find_edl_source(edl_ids, num_sources, id) >= 0) {
+            mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Repeated ID on line %d!\n",
+                   i+1);
+            goto out;
+        }
+        if (!isalpha(*id.start)) {
+            mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Invalid ID on line %d!\n",
+                   i+1);
+            goto out;
+        }
+        char *filename = mp_basename(bstrdup0(tmpmem, bstr_strip(line)));
+        if (!strlen(filename)) {
+            mp_msg(MSGT_CPLAYER, MSGL_ERR,
+                   "EDL: Invalid filename on line %d!\n", i+1);
+            goto out;
+        }
+        struct bstr dirname = mp_dirname(mpctx->demuxer->filename);
+        char *fullname = mp_path_join(tmpmem, dirname, BSTR(filename));
+        edl_ids[num_sources++] = (struct edl_source){id, fullname, i+1};
+    }
+
+    // Parse timeline part definitions
+
+    struct edl_part *parts = talloc_array_ptrtype(tmpmem, parts, num_parts);
+    int total_parts = num_parts;
+    num_parts = 0;
+    for (int i = 1; i < linec; i++) {
+        struct bstr line = bstr_strip(lines[i]);
+        if (!line.len || bstr_startswith(line, file_prefix))
+            continue;
+        parts[num_parts] = (struct edl_part){{-1, -1}, {-1, -1}, 0, -1};
+        parts[num_parts].lineno = i + 1;
+        for (int s = 0; s < 2; s++) {
+            struct edl_time *p = !s ? &parts[num_parts].tl :
+                &parts[num_parts].src;
+            while (1) {
+                struct bstr t = bstr_split(line, WHITESPACE, &line);
+                if (!t.len) {
+                    if (!s && num_parts < total_parts - 1) {
+                        mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: missing source "
+                               "identifier on line %d (not last)!\n", i+1);
+                        goto out;
+                    }
+                    break;
+                }
+                if (isalpha(*t.start)) {
+                    if (s)
+                        goto bad;
+                    parts[num_parts].id = find_edl_source(edl_ids, num_sources,
+                                                          t);
+                    if (parts[num_parts].id < 0) {
+                        mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Undefined source "
+                               "identifier on line %d!\n", i+1);
+                        goto out;
+                    }
+                    break;
+                }
+                while (t.len) {
+                    struct bstr next;
+                    struct bstr arg = bstr_split(t, "+-", &next);
+                    if (!arg.len) {
+                        next = bstr_split(line, WHITESPACE, &line);
+                        arg = bstr_split(next, "+-", &next);
+                    }
+                    if (!arg.len)
+                        goto bad;
+                    int64_t val;
+                    if (!bstrcmp(arg, BSTR("*")))
+                        val = -1;
+                    else if (isdigit(*arg.start)) {
+                        val = bstrtoll(arg, &arg, 10) * 1000000000;
+                        if (arg.len && *arg.start == '.') {
+                            int len = arg.len - 1;
+                            arg = bstr_splice(arg, 1, 10);
+                            int64_t val2 = bstrtoll(arg, &arg, 10);
+                            if (arg.len)
+                                goto bad;
+                            for (; len < 9; len++)
+                                val2 *= 10;
+                            val += val2;
+                        }
+                    } else
+                        goto bad;
+                    int c = *t.start;
+                    if (isdigit(c) || c == '*') {
+                        if (val < 0)
+                            p->implied_start = true;
+                        else
+                            p->start = val;
+                    } else if (c == '-') {
+                        if (val < 0)
+                            p->implied_end = true;
+                        else
+                            p->end = val;
+                    } else if (c == '+') {
+                        if (val < 0)
+                            goto bad;
+                        if (val == 0) {
+                            mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: zero duration "
+                                   "on line %d!\n", i+1);
+                            goto out;
+                        }
+                        parts[num_parts].duration = val;
+                    } else
+                        goto bad;
+                    t = next;
+                }
+            }
+        }
+        num_parts++;
+        continue;
+    bad:
+        mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Malformed line %d!\n", i+1);
+        goto out;
+    }
+
+    // Fill in implied start/stop/duration values
+
+    int64_t *times = talloc_zero_array(tmpmem, int64_t, num_sources);
+    while (1) {
+        int64_t time = 0;
+        for (int i = 0; i < num_parts; i++) {
+            for (int s = 0; s < 2; s++) {
+                struct edl_time *p = s ? &parts[i].tl : &parts[i].src;
+                if (!s && parts[i].id == -1)
+                    continue;
+                int64_t *t = s ? &time : times + parts[i].id;
+                p->implied_start |= s && *t >= 0;
+                if (p->implied_start && p->start >= 0 && *t >= 0
+                    && p->start != *t) {
+                    mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Inconsistent line "
+                           "%d!\n", parts[i].lineno);
+                    goto out;
+                }
+                if (p->start >= 0)
+                    *t = p->start;
+                if (p->implied_start)
+                    p->start = *t;
+                if (*t >= 0 && parts[i].duration)
+                    *t += parts[i].duration;
+                else
+                    *t = -1;
+                if (p->end >= 0)
+                    *t = p->end;
+            }
+        }
+        for (int i = 0; i < num_sources; i++)
+            times[i] = -1;
+        time = -1;
+        for (int i = num_parts - 1; i >= 0; i--) {
+            for (int s = 0; s < 2; s++) {
+                struct edl_time *p = s ? &parts[i].tl : &parts[i].src;
+                if (!s && parts[i].id == -1)
+                    continue;
+                int64_t *t = s ? &time : times + parts[i].id;
+                p->implied_end |= s && *t >= 0;
+                if (p->implied_end && p->end >= 0 && *t >=0 && p->end != *t) {
+                    mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Inconsistent line "
+                           "%d!\n", parts[i].lineno);
+                    goto out;
+                }
+                if (p->end >= 0)
+                    *t = p->end;
+                if (p->implied_end)
+                    p->end = *t;
+                if (*t >= 0 && parts[i].duration) {
+                    *t -= parts[i].duration;
+                    if (t < 0) {
+                        mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Negative time "
+                               "on line %d!\n", parts[i].lineno);
+                        goto out;
+                    }
+                } else
+                    *t = -1;
+                if (p->start >= 0)
+                    *t = p->start;
+            }
+        }
+        int missing_duration = -1;
+        int missing_srcstart = -1;
+        bool anything_done = false;
+        for (int i = 0; i < num_parts; i++) {
+            int64_t duration = parts[i].duration;
+            if (parts[i].tl.start >= 0 && parts[i].tl.end >= 0) {
+                int64_t duration2 = parts[i].tl.end - parts[i].tl.start;
+                if (duration && duration != duration2)
+                    goto incons;
+                duration = duration2;
+                if (duration <= 0)
+                    goto neg;
+            }
+            if (parts[i].src.start >= 0 && parts[i].src.end >= 0) {
+                int64_t duration2 = parts[i].src.end - parts[i].src.start;
+                if (duration && duration != duration2) {
+                incons:
+                    mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Inconsistent line "
+                           "%d!\n", i+1);
+                    goto out;
+                }
+                duration = duration2;
+                if (duration <= 0) {
+                neg:
+                    mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: duration <= 0 on "
+                           "line %d!\n", parts[i].lineno);
+                    goto out;
+                }
+            }
+            if (parts[i].id == -1)
+                continue;
+            if (!duration)
+                missing_duration = i;
+            else if (!parts[i].duration)
+                anything_done = true;
+            parts[i].duration = duration;
+            if (duration && parts[i].src.start < 0)
+                if (parts[i].src.end < 0)
+                    missing_srcstart = i;
+                else
+                    parts[i].src.start = parts[i].src.end - duration;
+        }
+        if (!anything_done) {
+            if (missing_duration >= 0) {
+                mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Could not determine "
+                        "duration for line %d!\n",
+                        parts[missing_duration].lineno);
+                goto out;
+            }
+            if (missing_srcstart >= 0) {
+                mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: no source start time for "
+                       "line %d!\n", parts[missing_srcstart].lineno);
+                    goto out;
+            }
+            break;
+        }
+    }
+
+    // Open source files
+
+    struct content_source *sources = talloc_array_ptrtype(NULL, sources,
+                                                          num_sources + 1);
+    mpctx->sources = sources;
+    sources[0].stream = mpctx->stream;
+    sources[0].demuxer = mpctx->demuxer;
+    mpctx->num_sources = 1;
+
+    for (int i = 0; i < num_sources; i++) {
+        int format = 0;
+        struct stream *s = open_stream(edl_ids[i].filename, &mpctx->opts,
+                                       &format);
+        if (!s)
+            goto openfail;
+        struct demuxer *d = demux_open(&mpctx->opts, s, format,
+                                       mpctx->opts.audio_id,
+                                       mpctx->opts.video_id,
+                                       mpctx->opts.sub_id,
+                                       edl_ids[i].filename);
+        if (!d) {
+            free_stream(s);
+        openfail:
+            mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Could not open source "
+                   "file on line %d!\n", edl_ids[i].lineno);
+            goto out;
+        }
+        sources[mpctx->num_sources].stream = s;
+        sources[mpctx->num_sources].demuxer = d;
+        mpctx->num_sources++;
+    }
+
+    // Write final timeline structure
+
+    struct timeline_part *timeline = talloc_array_ptrtype(NULL, timeline,
+                                                          num_parts + 1);
+    int64_t starttime = 0;
+    for (int i = 0; i < num_parts; i++) {
+        timeline[i].start = starttime / 1e9;
+        starttime += parts[i].duration;
+        timeline[i].source_start = parts[i].src.start / 1e9;
+        timeline[i].source = sources + parts[i].id + 1;
+    }
+    if (parts[num_parts - 1].id != -1) {
+        timeline[num_parts].start = starttime / 1e9;
+        num_parts++;
+    }
+    mpctx->timeline = timeline;
+    mpctx->num_timeline_parts = num_parts - 1;
+
+ out:
+    talloc_free(tmpmem);
+}
diff --git a/timeline/tl_matroska.c b/timeline/tl_matroska.c
index 46d0e33a45..03b6cc3dc4 100644
--- a/timeline/tl_matroska.c
+++ b/timeline/tl_matroska.c
@@ -259,31 +259,13 @@ void build_ordered_chapter_timeline(struct MPContext *mpctx)
         return;
     }
 
-    mp_msg(MSGT_CPLAYER, MSGL_V, "Timeline contains %d parts from %d "
-           "sources. Total length %.3f seconds.\n", part_count, num_sources,
-           timeline[part_count].start);
     if (missing_time)
         mp_msg(MSGT_CPLAYER, MSGL_ERR, "There are %.3f seconds missing "
                "from the timeline!\n", missing_time / 1e9);
-    mp_msg(MSGT_CPLAYER, MSGL_V, "Source files:\n");
-    for (int i = 0; i < num_sources; i++)
-        mp_msg(MSGT_CPLAYER, MSGL_V, "%d: %s\n", i,
-               filename_recode(sources[i].demuxer->filename));
-    mp_msg(MSGT_CPLAYER, MSGL_V, "Timeline parts: (number, start, "
-           "source_start, source):\n");
-    for (int i = 0; i < part_count; i++) {
-        struct timeline_part *p = timeline + i;
-        mp_msg(MSGT_CPLAYER, MSGL_V, "%3d %9.3f %9.3f %3td\n", i, p->start,
-               p->source_start, p->source - sources);
-    }
-    mp_msg(MSGT_CPLAYER, MSGL_V, "END %9.3f\n", timeline[part_count].start);
     mpctx->sources = sources;
     mpctx->num_sources = num_sources;
     mpctx->timeline = timeline;
     mpctx->num_timeline_parts = part_count;
     mpctx->num_chapters = num_chapters;
     mpctx->chapters = chapters;
-
-    mpctx->timeline_part = 0;
-    mpctx->demuxer = timeline[0].source->demuxer;
 }