timeline: add new EDL format

Edit Decision Lists (EDL) allow combining parts from multiple source
files into one virtual file. MPlayer had an EDL format (which sucked),
which mplayer2 tried to improve with its own format (which sucked). As
logic demands, mpv introduces its very own format (which sucks).

The new format should actually be much simpler and easier to use, and
its implementation is simpler and smaller too.

6 files changed, 385 insertions, 8 deletions

diff --git a/DOCS/edl-mpv.rst b/DOCS/edl-mpv.rst
new file mode 100644
index 0000000000..611182b003
--- /dev/null
+++ b/DOCS/edl-mpv.rst
@@ -0,0 +1,94 @@
+EDL files
+=========
+
+EDL files basically concatenate ranges of video/audio from multiple source
+files into a single continuous virtual file. Each such range is called a
+segment, and consists of source file, source offset, and segment length.
+
+For example::
+
+    mpv EDL v0
+    f1.mkv,10,20
+    f2.mkv
+    f1.mkv,40,10
+
+This would skip the first 10 seconds of the file f1.mkv, then play the next
+20 seconds, then switch to the file f2.mkv and play all of it, then switch
+back to f1.mkv, skip to the 40 second mark, and play 10 seconds, and then
+stop playback. The difference to specifying the files directly on command
+line (and using ``--{ --start=10 --length=20 f1.mkv --}`` etc.) is that the
+virtual EDL file appears as a single file, instead as a playlist.
+
+The general simplified syntax is:
+
+    <filename>
+    <filename>,<start in seconds>,<length in seconds>
+
+If the start time is omitted, 0 is used. If the length is omitted, the
+estimated duration of the source file is used.
+
+Note::
+
+    mpv can't use ordered chapter files or libquvi-resolved URLs in EDL
+    entries. Usage of relative or absolute paths as well as any protocol
+    prefixes is prevented for security reasons.
+
+
+Syntax of mpv EDL files
+=======================
+
+Generally, the format is relatively strict. No superfluous whitespace (except
+empty lines and commented lines) are allowed. You must use UNIX line breaks.
+
+The first line in the file must be ``mpv EDL v0``. This designates that the
+file uses format version 0, which is not frozen yet and may change any time.
+(If you need a stable EDL file format, make a feature request. Likewise, if
+you have suggestions for improvements, it's not too late yet.)
+
+The rest of the lines belong to one of these classes:
+
+1) An empty or commented line. A comment starts with ``#``, which must be the
+   first character in the line. The rest of the line (up until the next line
+   break) is ignored. An empty line has 0 bytes between two line feed bytes.
+2) A segment entry in all other cases.
+
+Each segment entry consists of a list of named or unnamed parameters.
+Parameters are separated with ``,``. Named parameters consist of a name,
+followed by ``=``, followed by the value. Unnamed parameters have only a
+value, and the name is implicit from the parameter position.
+
+Syntax::
+
+    segment_entry ::= <param> ( <param> ',' )*
+    param         ::= [ <name> '=' ] ( <value> | '%' <number> '%' <valuebytes> )
+
+The ``name`` string can consist of any characters, except ``=%,;\n``. The
+``value`` string can consist of any characters except to ``,;\n``.
+
+The construct starting with ``%`` allows defining any value with arbitrary
+contents inline, where ``number`` is an integer giving the number of bytes in
+``valuebytes``. If a parameter value contains disallowed characters, it has to
+be guarded by a length specifier using this syntax.
+
+The parameter name defines the meaning of the parameter:
+
+1) ``file``, the source file to use for this segment.
+2) ``start``, a time value that specifies the start offset into the source file.
+3) ``length``, a time value that specifies the length of the segment.
+
+(Currently, time values are floating point values in seconds.)
+
+Unnamed parameters carry implicit names. The parameter position determines
+which of the parameters listed above is set. For example, the second parameter
+implicitly uses the name ``start``.
+
+Example::
+
+    mpv EDL v0
+    %18%filename,with,.mkv,10,length=20,param3=%13%value,escaped,param4=value2
+
+this sets ``file`` to ``filename,with,.mkv``, ``start`` to ``10``, ``length``
+to ``20``, ``param3`` to ``value,escaped``, ``param4`` to ``value2``.
+
+Instead of line breaks, the character ``;`` can be used. Line feed bytes and
+``;`` are treated equally.
diff --git a/Makefile b/Makefile
index 7ccea8d1b6..07d05d7fe0 100644
--- a/Makefile
+++ b/Makefile
@@ -224,6 +224,7 @@ SOURCES = audio/audio.c \
           mpvcore/player/video.c \
           mpvcore/player/timeline/tl_edl.c \
           mpvcore/player/timeline/tl_matroska.c \
+          mpvcore/player/timeline/tl_mpv_edl.c \
           mpvcore/player/timeline/tl_cue.c \
           osdep/io.c \
           osdep/numcores.c \
diff --git a/demux/demux_edl.c b/demux/demux_edl.c
index 5c6afa2d9b..dd6c660f74 100644
--- a/demux/demux_edl.c
+++ b/demux/demux_edl.c
@@ -25,18 +25,19 @@
 #include "demux.h"
 #include "stream/stream.h"
 
+static bool test_header(struct stream *s, char *header)
+{
+    return bstr_equals0(stream_peek(s, strlen(header)), header);
+}
+
+// Note: the real work is handled in tl_mpv_edl.c.
 static int try_open_file(struct demuxer *demuxer, enum demux_check check)
 {
     struct stream *s = demuxer->stream;
     if (check >= DEMUX_CHECK_UNSAFE) {
-        const char header[] = "mplayer EDL file";
-        const int len = sizeof(header) - 1;
-        char buf[len];
-        if (stream_read(s, buf, len) < len)
-            return -1;
-        if (strncmp(buf, header, len))
+        if (!test_header(s, "mplayer EDL file") &&
+            !test_header(s, "mpv EDL v0\n"))
             return -1;
-        stream_seek(s, 0);
     }
     demuxer->file_contents = stream_read_complete(s, demuxer, 1000000);
     if (demuxer->file_contents.start == NULL)
@@ -46,7 +47,7 @@ static int try_open_file(struct demuxer *demuxer, enum demux_check check)
 
 const struct demuxer_desc demuxer_desc_edl = {
     .name = "edl",
-    .desc = "mplayer2 edit decision list",
+    .desc = "Edit decision list",
     .type = DEMUXER_TYPE_EDL,
     .open = try_open_file,
 };
diff --git a/mpvcore/player/mp_core.h b/mpvcore/player/mp_core.h
index 4dcb218a80..4e0dede812 100644
--- a/mpvcore/player/mp_core.h
+++ b/mpvcore/player/mp_core.h
@@ -425,6 +425,8 @@ void update_subtitles(struct MPContext *mpctx);
 
 // timeline/tl_matroska.c
 void build_ordered_chapter_timeline(struct MPContext *mpctx);
+// timeline/tl_mpv_edl.c
+void build_mpv_edl_timeline(struct MPContext *mpctx);
 // timeline/tl_edl.c
 void build_edl_timeline(struct MPContext *mpctx);
 // timeline/tl_cue.c
diff --git a/mpvcore/player/timeline/tl_edl.c b/mpvcore/player/timeline/tl_edl.c
index 69e2402149..b4715e5a1f 100644
--- a/mpvcore/player/timeline/tl_edl.c
+++ b/mpvcore/player/timeline/tl_edl.c
@@ -70,6 +70,10 @@ void build_edl_timeline(struct MPContext *mpctx)
     struct bstr *lines = bstr_splitlines(tmpmem, mpctx->demuxer->file_contents);
     int linec = MP_TALLOC_ELEMS(lines);
     struct bstr header = bstr0("mplayer EDL file, version ");
+    if (bstr_startswith0(lines[0], "mpv EDL v0\n")) {
+        build_mpv_edl_timeline(mpctx);
+        goto out;
+    }
     if (!linec || !bstr_startswith(lines[0], header)) {
         mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Bad EDL header!\n");
         goto out;
diff --git a/mpvcore/player/timeline/tl_mpv_edl.c b/mpvcore/player/timeline/tl_mpv_edl.c
new file mode 100644
index 0000000000..4c44ea9fc8
--- /dev/null
+++ b/mpvcore/player/timeline/tl_mpv_edl.c
@@ -0,0 +1,275 @@
+/*
+ * 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 <math.h>
+
+#include "talloc.h"
+
+#include "mpvcore/player/mp_core.h"
+#include "mpvcore/mp_msg.h"
+#include "demux/demux.h"
+#include "mpvcore/path.h"
+#include "mpvcore/bstr.h"
+#include "mpvcore/mp_common.h"
+#include "stream/stream.h"
+
+struct tl_part {
+    char *filename;             // what is stream_open()ed
+    double offset;              // offset into the source file
+    double length;              // length of the part (-1 if rest of the file)
+};
+
+struct tl_parts {
+    struct tl_part *parts;
+    int num_parts;
+};
+
+// Parse a time (absolute file time or duration). Currently equivalent to a
+// number. Return false on failure.
+static bool parse_time(bstr str, double *out_time)
+{
+    bstr rest;
+    double time = bstrtod(str, &rest);
+    if (!str.len || rest.len || !isfinite(time))
+        return false;
+    *out_time = time;
+    return true;
+}
+
+/* Returns a list of parts, or NULL on parse error.
+ * Syntax:
+ *    url      ::= ['edl://'|'mpv EDL v0\n'] <entry> ( (';' | '\n') <entry> )*
+ *    entry    ::= <param> ( <param> ',' )*
+ *    param    ::= [<string> '='] (<string> | '%' <number> '%' <bytes>)
+ */
+static struct tl_parts *parse_edl(bstr str)
+{
+    struct tl_parts *tl = talloc_zero(NULL, struct tl_parts);
+    if (!bstr_eatstart0(&str, "edl://"))
+        bstr_eatstart0(&str, "mpv EDL v0\n");
+    while (str.len) {
+        if (bstr_eatstart0(&str, "#"))
+            bstr_split_tok(str, "\n", &(bstr){0}, &str);
+        if (bstr_eatstart0(&str, "\n") || bstr_eatstart0(&str, ";"))
+            continue;
+        struct tl_part p = { .length = -1 };
+        int nparam = 0;
+        while (1) {
+            bstr name, val;
+            // Check if it's of the form "name=..."
+            int next = bstrcspn(str, "=%,;\n");
+            if (next > 0 && next < str.len && str.start[next] == '=') {
+                name = bstr_splice(str, 0, next);
+                str = bstr_cut(str, next + 1);
+            } else {
+                const char *names[] = {"file", "start", "length"}; // implied name
+                name = bstr0(nparam < 3 ? names[nparam] : "-");
+            }
+            if (bstr_eatstart0(&str, "%")) {
+                int len = bstrtoll(str, &str, 0);
+                if (!bstr_startswith0(str, "%") || (len > str.len - 1))
+                    goto error;
+                val = bstr_splice(str, 1, len + 1);
+                str = bstr_cut(str, len + 1);
+            } else {
+                next = bstrcspn(str, ",;\n");
+                val = bstr_splice(str, 0, next);
+                str = bstr_cut(str, next);
+            }
+            // Interpret parameters. Explicitly ignore unknown ones.
+            if (bstr_equals0(name, "file")) {
+                p.filename = bstrto0(tl, val);
+            } else if (bstr_equals0(name, "start")) {
+                if (!parse_time(val, &p.offset))
+                    goto error;
+            } else if (bstr_equals0(name, "length")) {
+                if (!parse_time(val, &p.length))
+                    goto error;
+            }
+            nparam++;
+            if (!bstr_eatstart0(&str, ","))
+                break;
+        }
+        if (!p.filename)
+            goto error;
+        MP_TARRAY_APPEND(tl, tl->parts, tl->num_parts, p);
+    }
+    if (!tl->num_parts)
+        goto error;
+    return tl;
+error:
+    talloc_free(tl);
+    return NULL;
+}
+
+static struct demuxer *open_file(char *filename, struct MPContext *mpctx)
+{
+    struct MPOpts *opts = mpctx->opts;
+    struct demuxer *d = NULL;
+    struct stream *s = stream_open(filename, opts);
+    if (s) {
+        stream_enable_cache_percent(&s,
+                                    opts->stream_cache_size,
+                                    opts->stream_cache_def_size,
+                                    opts->stream_cache_min_percent,
+                                    opts->stream_cache_seek_min_percent);
+        d = demux_open(s, NULL, NULL, opts);
+    }
+    if (!d) {
+        mp_msg(MSGT_CPLAYER, MSGL_ERR, "EDL: Could not open source file '%s'.\n",
+               filename);
+        free_stream(s);
+    }
+    return d;
+}
+
+static struct demuxer *open_source(struct MPContext *mpctx, char *filename)
+{
+    for (int n = 0; n < mpctx->num_sources; n++) {
+        struct demuxer *d = mpctx->sources[n];
+        if (strcmp(d->stream->url, filename) == 0)
+            return d;
+    }
+    struct demuxer *d = open_file(filename, mpctx);
+    if (d)
+        MP_TARRAY_APPEND(NULL, mpctx->sources, mpctx->num_sources, d);
+    return d;
+}
+
+// Append all chapters from src to the chapters array.
+// Ignore chapters outside of the given time range.
+static void copy_chapters(struct chapter **chapters, int *num_chapters,
+                          struct demuxer *src, double start, double len,
+                          double dest_offset)
+{
+    int count = demuxer_chapter_count(src);
+    for (int n = 0; n < count; n++) {
+        double time = demuxer_chapter_time(src, n);
+        if (time >= start && time <= start + len) {
+            struct chapter ch = {
+                .start = dest_offset + time,
+                .name = talloc_steal(*chapters, demuxer_chapter_name(src, n)),
+            };
+            MP_TARRAY_APPEND(NULL, *chapters, *num_chapters, ch);
+        }
+    }
+}
+
+// return length of the source in seconds, or -1 if unknown
+static double source_get_length(struct demuxer *demuxer)
+{
+    double time;
+    // <= 0 means DEMUXER_CTRL_NOTIMPL or DEMUXER_CTRL_DONTKNOW
+    if (demux_control(demuxer, DEMUXER_CTRL_GET_TIME_LENGTH, &time) <= 0)
+        time = -1;
+    return time;
+}
+
+static void build_timeline(struct MPContext *mpctx, struct tl_parts *parts)
+{
+    struct chapter *chapters = talloc_new(NULL);
+    int num_chapters = 0;
+    struct timeline_part *timeline = talloc_array_ptrtype(NULL, timeline,
+                                                          parts->num_parts + 1);
+    double starttime = 0;
+    for (int n = 0; n < parts->num_parts; n++) {
+        struct tl_part *part = &parts->parts[n];
+        struct demuxer *source = open_source(mpctx, part->filename);
+        if (!source)
+            goto error;
+
+        double len = source_get_length(source);
+        if (len <= 0) {
+            mp_msg(MSGT_CPLAYER, MSGL_WARN,
+                   "EDL: source file '%s' has unknown duration.\n",
+                   part->filename);
+        }
+
+        // Unkown length => use rest of the file. If duration is unknown, make
+        // something up.
+        if (part->length < 0)
+            part->length = (len < 0 ? 1 : len) - part->offset;
+
+        if (len > 0) {
+            double partlen = part->offset + part->length;
+            if (partlen > len) {
+                mp_msg(MSGT_CPLAYER, MSGL_WARN,  "EDL: entry %d uses %f "
+                       "seconds, but file has only %f seconds.\n",
+                       n, partlen, len);
+            }
+        }
+
+        // Add a chapter between each file.
+        struct chapter ch = {
+            .start = starttime,
+            .name = talloc_strdup(chapters, part->filename),
+        };
+        MP_TARRAY_APPEND(NULL, chapters, num_chapters, ch);
+
+        // Also copy the source file's chapters for the relevant parts
+        copy_chapters(&chapters, &num_chapters, source, part->offset,
+                      part->length, starttime);
+
+        timeline[n] = (struct timeline_part) {
+            .start = starttime,
+            .source_start = part->offset,
+            .source = source,
+        };
+
+        starttime += part->length;
+    }
+    timeline[parts->num_parts] = (struct timeline_part) {.start = starttime};
+    mpctx->timeline = timeline;
+    mpctx->num_timeline_parts = parts->num_parts;
+    mpctx->chapters = chapters;
+    mpctx->num_chapters = num_chapters;
+    return;
+
+error:
+    talloc_free(timeline);
+    talloc_free(chapters);
+}
+
+// For security, don't allow relative or absolute paths, only plain filenames.
+// Also, make these filenames relative to the edl source file.
+static void fix_filenames(struct tl_parts *parts, char *source_path)
+{
+    struct bstr dirname = mp_dirname(source_path);
+    for (int n = 0; n < parts->num_parts; n++) {
+        struct tl_part *part = &parts->parts[n];
+        char *filename = mp_basename(part->filename); // plain filename only
+        part->filename = mp_path_join(parts, dirname, bstr0(filename));
+    }
+}
+
+void build_mpv_edl_timeline(struct MPContext *mpctx)
+{
+    struct tl_parts *parts = parse_edl(mpctx->demuxer->file_contents);
+    if (!parts) {
+        mp_msg(MSGT_CPLAYER, MSGL_ERR, "Error in EDL.\n");
+        return;
+    }
+    // Don't allow arbitrary paths
+    fix_filenames(parts, mpctx->demuxer->filename);
+    build_timeline(mpctx, parts);
+    talloc_free(parts);
+}