Experimental parsing expression grammar (PEG) template library

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2271743002

Review-Url: https://codereview.chromium.org/2271743002

4 files changed, 547 insertions, 0 deletions

diff --git a/BUILD.gn b/BUILD.gn
index e0ed2a6f80..930bf62db4 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -612,6 +612,7 @@ if (skia_enable_tools) {
           rebase_path("tests/skia_test.cpp"),  # alternate main
         ]
     deps = [
+      ":experimental_svg_model",
       ":flags",
       ":gpu_tool_utils",
       ":skia",
diff --git a/experimental/svg/model/SkPEG.h b/experimental/svg/model/SkPEG.h
new file mode 100644
index 0000000000..886852019e
--- /dev/null
+++ b/experimental/svg/model/SkPEG.h
@@ -0,0 +1,244 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkPEG_DEFINED
+#define SkPEG_DEFINED
+
+#include "SkTDArray.h"
+#include "SkTLazy.h"
+
+namespace skpeg {
+
+/**
+ *  The result of an expression match attempt.
+ *
+ *  If the match was successful, |fNext| points to the next unconsumed character in the
+ *  input string, and |fValue| holds an (arbitrarily nested) match result value.
+ *
+ *  Otherwise, |fNext| is nullptr and |fValue| is uninitialized.
+ */
+template <typename V>
+struct MatchResult {
+    MatchResult(std::nullptr_t) : fNext(nullptr) {}
+    MatchResult(const char* next, const V& v) : fNext(next), fValue(&v) {}
+
+    operator bool() const {
+        SkASSERT(fValue.isValid() == SkToBool(fNext));
+        return SkToBool(fNext);
+    }
+
+    const V& operator* () const { return *fValue.get(); }
+    const V* operator->() const { return  fValue.get(); }
+
+    const char* fNext;
+    SkTLazy<V>  fValue;
+};
+
+/**
+ * Optional operator (e?).  Always succeeds.
+ *
+ * If e also matches, then the result of e::Match() is stored in |fValue|.
+ * Otherwise, |fValue| is uninitialized.
+ *
+ */
+template <typename E>
+struct Opt {
+    struct V {
+        V(const typename E::V* v) : fValue(v) {}
+
+        SkTLazy<typename E::V> fValue;
+    };
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        const auto m = E::Match(in);
+        return m ? MatchT(m.fNext, V(m.fValue.get()))
+                 : MatchT(in, nullptr);
+    }
+};
+
+/**
+ * Helper for selecting the value type of the n-th expression type in the list.
+ */
+template <size_t, typename... Es> struct SelectV;
+
+template <typename E, typename... Es>
+struct SelectV<0, E, Es...> {
+    using V = typename E::V;
+};
+
+template <size_t idx, typename E, typename... Es>
+struct SelectV<idx, E, Es...> {
+    using V = typename SelectV<idx - 1, Es...>::V;
+};
+
+/**
+ * Sequence operator (e0 e1...).
+ *
+ * Succeeds when all expressions match, in sequence.  The subexpression match
+ * results can be accessed via get<INDEX>() -- where get<0> returns the value
+ * of the first expression, and so on.
+ *
+ */
+template <typename... E> struct Seq;
+
+template <>
+struct Seq<> {
+    struct V {};
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        return MatchT(in, V());
+    }
+};
+
+template <typename E, typename... Es>
+struct Seq<E, Es...> {
+    class V {
+    public:
+        V(const typename E::V& head, const typename Seq<Es...>::V& tail)
+            : fHeadV(head), fTailV(tail) {}
+
+        template <size_t idx, typename std::enable_if<idx == 0, bool>::type = 0>
+        const typename E::V& get() const {
+            return fHeadV;
+        }
+
+        template <size_t idx, typename std::enable_if<idx != 0, bool>::type = 0>
+        const typename SelectV<idx, E, Es...>::V& get() const {
+            return fTailV.template get<idx - 1>();
+        }
+
+    private:
+        typename E::V          fHeadV;
+        typename Seq<Es...>::V fTailV;
+    };
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        const auto headMatch = E::Match(in);
+        if (!headMatch) {
+            return nullptr;
+        }
+
+        const auto tailMatch = Seq<Es...>::Match(headMatch.fNext);
+        return tailMatch ? MatchT(tailMatch.fNext, V(*headMatch, *tailMatch))
+                         : nullptr;
+    }
+};
+
+/**
+ * Ordered choice operator (e1|e2).
+ *
+ * Succeeds when either e1 or e2 match (e1 is tried first, then e2).
+ *
+ * The (optional) match results are stored in |v1|, |v2|.
+ *
+ */
+template <typename E1, typename E2>
+struct Choice {
+    struct V {
+        V (const typename E1::V* v1, const typename E2::V* v2) : v1(v1), v2(v2)
+        {
+            SkASSERT(!v1 || !v2);
+        }
+
+        SkTLazy<typename E1::V> v1;
+        SkTLazy<typename E2::V> v2;
+    };
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        if (const auto m1 = E1::Match(in)) {
+            return MatchT(m1.fNext, V(m1.fValue.get(), nullptr));
+        }
+        if (const auto m2 = E2::Match(in)) {
+            return MatchT(m2.fNext, V(nullptr, m2.fValue.get()));
+        }
+        return nullptr;
+    }
+};
+
+/**
+ * Zero-or-more operator (e*).  Always succeeds.
+ *
+ * Matches e greedily, and stores the match results in |fValues|.
+ *
+ */
+template <typename E>
+struct Any {
+    struct V {
+        V(SkTDArray<typename E::V>&& vs) : fValues(vs) {}
+
+        SkTDArray<typename E::V> fValues;
+    };
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        SkTDArray<typename E::V> values;
+        while (const auto m = E::Match(in)) {
+            in = m.fNext;
+            *values.append() = *m;
+        }
+        return MatchT(in, std::move(values));
+    }
+};
+
+/**
+ * One-or-more operator (e+).
+ *
+ * Same as zero-or-more, except it fails if e doesn't match at least once.
+ *
+ */
+template <typename E>
+using Some = Seq<E, Any<E>>;
+
+/**
+ * End-of-string atom.  Matches \0.
+ */
+struct EOS {
+    struct V {};
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        return (*in != '\0') ? nullptr : MatchT(in, V());
+    }
+};
+
+
+/**
+ * Literal atom.  Matches a list of char literals.
+ */
+template <char... Cs> struct LIT;
+
+template <>
+struct LIT<> {
+    struct V {};
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        return MatchT(in, V());
+    }
+};
+
+template <char C, char... Cs>
+struct LIT<C, Cs...> {
+    struct V {};
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        if (*in != C) {
+            return nullptr;
+        }
+        const auto m = LIT<Cs...>::Match(in + 1);
+        return m ? MatchT(m.fNext, V()) : nullptr;
+    }
+};
+
+} // skpeg ns
+
+#endif // SkPEG_DEFINED
diff --git a/gyp/svg.gyp b/gyp/svg.gyp
index 158a3992e3..1160b94d97 100644
--- a/gyp/svg.gyp
+++ b/gyp/svg.gyp
@@ -78,6 +78,8 @@
         '../experimental/svg/model/SkSVGTypes.h',
         '../experimental/svg/model/SkSVGValue.h',
         '../experimental/svg/model/SkSVGValue.cpp',
+
+        '../experimental/svg/model/SkPEG.h',
       ],
       'direct_dependent_settings': {
         'include_dirs': [
diff --git a/tests/SkPEGTest.cpp b/tests/SkPEGTest.cpp
new file mode 100644
index 0000000000..68a47776e8
--- /dev/null
+++ b/tests/SkPEGTest.cpp
@@ -0,0 +1,300 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkPEG.h"
+#include "Test.h"
+
+using namespace skpeg;
+
+namespace {
+
+struct Alpha {
+    using V = char;
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        static constexpr unsigned kAlphaRange = 'z' - 'a';
+        return static_cast<unsigned>(*in - 'a') <= kAlphaRange
+            || static_cast<unsigned>(*in - 'A') <= kAlphaRange
+            ? MatchT(in + 1, *in)
+            : nullptr;
+    }
+};
+
+struct Digit {
+    using V = uint8_t;
+    using MatchT = MatchResult<V>;
+
+    static MatchT Match(const char* in) {
+        static constexpr unsigned kDigitRange = '9' - '0';
+        return static_cast<unsigned>(*in - '0') <= kDigitRange
+            ? MatchT(in + 1, SkTo<uint8_t>(*in - '0'))
+            : nullptr;
+    }
+};
+
+void test_EOS(skiatest::Reporter* r) {
+    static const struct {
+        const char* fInput;
+        bool        fMatch;
+    } gTests[] = {
+        { ""   , true  },
+        { " "  , false },
+        { "\0" , true  },
+        { "foo", false },
+    };
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(gTests); ++i) {
+        const auto match = EOS::Match(gTests[i].fInput);
+        REPORTER_ASSERT(r, match == gTests[i].fMatch);
+        REPORTER_ASSERT(r, match.fNext == (match ? gTests[i].fInput : nullptr));
+    }
+}
+
+void test_LIT(skiatest::Reporter* r) {
+    static const struct {
+        const char* fInput;
+        bool        fMatch;
+    } gTests[] = {
+        { ""  , false },
+        { " " , false },
+        { "x" , false },
+        { "X" , true  },
+        { "xX", false },
+        { "Xx", true  },
+    };
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(gTests); ++i) {
+        const auto match = LIT<'X'>::Match(gTests[i].fInput);
+        REPORTER_ASSERT(r, match == gTests[i].fMatch);
+        REPORTER_ASSERT(r, match.fNext == (match ? gTests[i].fInput + 1 : nullptr));
+    }
+
+    REPORTER_ASSERT(r, !(LIT<'F', 'o', 'o'>::Match("")));
+    REPORTER_ASSERT(r, !(LIT<'F', 'o', 'o'>::Match("Fo")));
+    REPORTER_ASSERT(r, !(LIT<'F', 'o', 'o'>::Match("FoO")));
+    REPORTER_ASSERT(r,  (LIT<'F', 'o', 'o'>::Match("Foo")));
+    REPORTER_ASSERT(r,  (LIT<'F', 'o', 'o'>::Match("Foobar")));
+}
+
+void test_Alpha(skiatest::Reporter* r) {
+    static const struct {
+        const char* fInput;
+        bool        fMatch;
+        char        fMatchValue;
+    } gTests[] = {
+        { ""  , false,  0  },
+        { "\r", false,  0  },
+        { "\n", false,  0  },
+        { "\t", false,  0  },
+        { "0" , false,  0  },
+        { "9" , false,  0  },
+        { "a" , true , 'a' },
+        { "a" , true , 'a' },
+        { "z" , true , 'z' },
+        { "A" , true , 'A' },
+        { "Z" , true , 'Z' },
+        { "az", true , 'a' },
+        { "a0", true , 'a' },
+        { "0a", false,  0  },
+    };
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(gTests); ++i) {
+        const auto match = Alpha::Match(gTests[i].fInput);
+        REPORTER_ASSERT(r, match == gTests[i].fMatch);
+        REPORTER_ASSERT(r, match.fNext == (match ? gTests[i].fInput + 1 : nullptr));
+        if (match) {
+            REPORTER_ASSERT(r, *match == gTests[i].fMatchValue);
+        }
+    }
+}
+
+void test_Digit(skiatest::Reporter* r) {
+    static const struct {
+        const char* fInput;
+        bool        fMatch;
+        uint8_t     fMatchValue;
+    } gTests[] = {
+        { ""   , false, 0 },
+        { "/"  , false, 0 },
+        { ":"  , false, 0 },
+        { "x"  , false, 0 },
+        { "x0" , false, 0 },
+        { "0"  , true , 0 },
+        { "1x" , true , 1 },
+        { "9 a", true , 9 },
+    };
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(gTests); ++i) {
+        const auto match = Digit::Match(gTests[i].fInput);
+        REPORTER_ASSERT(r, match == gTests[i].fMatch);
+        REPORTER_ASSERT(r, match.fNext == (match ? gTests[i].fInput + 1 : nullptr));
+        if (match) {
+            REPORTER_ASSERT(r, *match == gTests[i].fMatchValue);
+        }
+    }
+}
+
+void test_Opt(skiatest::Reporter* r) {
+    static const struct {
+        const char* fInput;
+        bool        fMatch;
+    } gTests[] = {
+        { ""       , false },
+        { "fo"     , false },
+        { " foo"   , false },
+        { "foo"    , true },
+        { "foobar" , true },
+    };
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(gTests); ++i) {
+        const auto m = Opt<LIT<'f', 'o', 'o'>>::Match(gTests[i].fInput);
+        REPORTER_ASSERT(r, m);
+        REPORTER_ASSERT(r, m->fValue.isValid() == gTests[i].fMatch);
+    }
+}
+
+void test_Seq(skiatest::Reporter* r) {
+    REPORTER_ASSERT(r,  (Seq<LIT<'X'>, EOS>::Match("X")));
+    REPORTER_ASSERT(r, !(Seq<LIT<'X'>, EOS>::Match("x")));
+    REPORTER_ASSERT(r, !(Seq<LIT<'X'>, EOS>::Match("xX")));
+    REPORTER_ASSERT(r, !(Seq<LIT<'X'>, EOS>::Match("XX")));
+    REPORTER_ASSERT(r,  (Seq<LIT<'X'>, Seq<LIT<'X'>, EOS>>::Match("XX")));
+    REPORTER_ASSERT(r,  (Seq<LIT<'X'>, Seq<LIT<'X'>, EOS>>::Match("XX")));
+
+    REPORTER_ASSERT(r, !(Seq<LIT<'F', 'o', 'o'>, EOS>::Match("FooBar")));
+    REPORTER_ASSERT(r,  (Seq<LIT<'F', 'o', 'o'>, EOS>::Match("Foo")));
+
+    {
+        const auto m = Seq<LIT<'x'>, Digit>::Match("x5");
+        REPORTER_ASSERT(r, m);
+        REPORTER_ASSERT(r, m->get<1>() == 5);
+    }
+    {
+        const auto m = Seq<Digit, Digit>::Match("42");
+        REPORTER_ASSERT(r, m);
+        REPORTER_ASSERT(r, m->get<0>() == 4);
+        REPORTER_ASSERT(r, m->get<1>() == 2);
+    }
+}
+
+void test_Choice(skiatest::Reporter* r) {
+    REPORTER_ASSERT(r, !(Choice<Digit,Alpha>::Match("")));
+    REPORTER_ASSERT(r, !(Choice<Digit,Alpha>::Match("\t")));
+    REPORTER_ASSERT(r, !(Choice<Digit,Alpha>::Match(" ")));
+    REPORTER_ASSERT(r,  (Choice<Digit,Alpha>::Match("a")));
+    REPORTER_ASSERT(r,  (Choice<Digit,Alpha>::Match("3")));
+    REPORTER_ASSERT(r,  (Choice<Digit,Alpha>::Match("a ")));
+    REPORTER_ASSERT(r,  (Choice<Digit,Alpha>::Match("3 ")));
+    REPORTER_ASSERT(r, !(Choice<Digit,Alpha>::Match(" a ")));
+    REPORTER_ASSERT(r, !(Choice<Digit,Alpha>::Match(" 3 ")));
+
+    {
+        const auto m = Choice<Alpha, Digit>::Match("x");
+        REPORTER_ASSERT(r,  m);
+        REPORTER_ASSERT(r,  m->v1.isValid());
+        REPORTER_ASSERT(r, !m->v2.isValid());
+        REPORTER_ASSERT(r, *m->v1.get() == 'x');
+    }
+
+    {
+        const auto m = Choice<Alpha, Digit>::Match("7");
+        REPORTER_ASSERT(r,  m);
+        REPORTER_ASSERT(r, !m->v1.isValid());
+        REPORTER_ASSERT(r,  m->v2.isValid());
+        REPORTER_ASSERT(r, *m->v2.get() == 7);
+    }
+}
+
+void test_AnySome(skiatest::Reporter* r) {
+    static const struct {
+        const char* fInput;
+        int         fCount;
+    } gTests[] = {
+        { ""      , 0 },
+        { "fo"    , 0 },
+        { "Foo"   , 0 },
+        { "foo"   , 1 },
+        { "foofoo", 2 },
+    };
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(gTests); ++i) {
+        const auto matchAny = Any<LIT<'f', 'o', 'o'>>::Match(gTests[i].fInput);
+        REPORTER_ASSERT(r, matchAny);
+        REPORTER_ASSERT(r, matchAny->fValues.count() == gTests[i].fCount);
+
+        const auto matchSome = Some<LIT<'f', 'o', 'o'>>::Match(gTests[i].fInput);
+        REPORTER_ASSERT(r,  matchSome == (gTests[i].fCount > 0));
+        REPORTER_ASSERT(r, !matchSome ||
+                            matchSome->get<1>().fValues.count() == gTests[i].fCount - 1);
+    }
+
+    {
+        const auto m = Any<Digit>::Match("0123456789foo");
+        REPORTER_ASSERT(r, m);
+        REPORTER_ASSERT(r, m->fValues.count() == 10);
+        for (int i = 0; i < m->fValues.count(); ++i) {
+            REPORTER_ASSERT(r, m->fValues[i] == i);
+        }
+    }
+}
+
+void test_Complex(skiatest::Reporter* r) {
+    // [0-9]+(,[0-9]+)?$
+    using P0 =
+        Seq<
+          Some<Digit>,
+          Opt<Seq<
+            LIT<','>,
+            Some<Digit>>>,
+          EOS>;
+
+    REPORTER_ASSERT(r, !P0::Match(""));
+    REPORTER_ASSERT(r, !P0::Match(","));
+    REPORTER_ASSERT(r, !P0::Match("1,"));
+    REPORTER_ASSERT(r, !P0::Match(",1"));
+    REPORTER_ASSERT(r,  P0::Match("1"));
+    REPORTER_ASSERT(r,  P0::Match("1,2"));
+    REPORTER_ASSERT(r, !P0::Match("1,2 "));
+    REPORTER_ASSERT(r,  P0::Match("123,456"));
+
+    // [ ]*[Ff]oo([Bb]ar)+[Bb]az[ ]*$
+    using P1 =
+        Seq<
+          Any<LIT<' '>>,
+          Choice<LIT<'F'>, LIT<'f'>>,
+          LIT<'o', 'o'>,
+          Some<Seq<
+            Choice<LIT<'B'>, LIT<'b'>>,
+            LIT<'a', 'r'>>>,
+          Choice<LIT<'B'>, LIT<'b'>>,
+          LIT<'a', 'z'>,
+          Any<LIT<' '>>,
+          EOS>;
+
+    REPORTER_ASSERT(r, !P1::Match(""));
+    REPORTER_ASSERT(r, !P1::Match("FooBar"));
+    REPORTER_ASSERT(r, !P1::Match("FooBaz"));
+    REPORTER_ASSERT(r,  P1::Match("FooBarBaz"));
+    REPORTER_ASSERT(r,  P1::Match("foobarbaz"));
+    REPORTER_ASSERT(r,  P1::Match("  FooBarbaz     "));
+    REPORTER_ASSERT(r,  P1::Match(" FooBarbarbarBaz "));
+}
+
+} // anonymous ns
+
+DEF_TEST(SkPEG, r) {
+    test_EOS(r);
+    test_LIT(r);
+    test_Alpha(r);
+    test_Digit(r);
+    test_Opt(r);
+    test_Seq(r);
+    test_Choice(r);
+    test_AnySome(r);
+    test_Complex(r);
+}