Reland: Experimental parsing expression grammar (PEG) template library

experimental/svg/model/SkPEG.h

Index: experimental/svg/model/SkPEG.h
diff --git a/experimental/svg/model/SkPEG.h b/experimental/svg/model/SkPEG.h
new file mode 100644
index 0000000000000000000000000000000000000000..326c87b0533e00d780bc9e780ec956697d30d532
--- /dev/null
+++ b/experimental/svg/model/SkPEG.h
@@ -0,0 +1,283 @@
+/*
+ * 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;
+        for (;;) {

[mtklein, 2016/08/24 15:01:55]

Is this loop different from

while (const auto m = E::Match(in)) {
   in = m.fNext;
   *values.append() = *m;
}

?

[f(malita), 2016/08/24 17:17:02]

Done.

+            if (const auto m = E::Match(in)) {
+                in = m.fNext;
+                *values.append() = *m;
+            } else {
+                break;
+            }
+        }
+
+        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...> {

[bungeman-skia, 2016/08/24 15:04:20]

I'm assuming this is for svg and possibly parsing bits of css. Those are defined
in terms of unicode code points and not 'char'.  Is there a plan for that? pegtl
seems to have a fair amount of code devoted to turning various encodings into 
code points.

For example these template parameters could be 'uint32_t' (or 'char32_t')
instead of 'char' which would work with the 'U' UCS-4 character literal. Of
course, the Match input would need to be decoded somehow as well.

[f(malita), 2016/08/24 17:17:02]

Good question, I haven't really thought much about this.

The immediate plan is to use this for parsing SVG *attribute values*.  In
general, these seem to be well-behaved (as in Latin1) - e.g. stuff like
https://www.w3.org/TR/SVG/types.html#DataTypeColor

The only way I can think of for non-Latin1 chars to sneak into attribute values
is via reference strings (fill="#什么他妈的").  But then again these are treated as
opaque strings, and we're not going to attempt parsing them anyway.

We also have a couple more layers sitting between the attribute parser and the
source document:  Expat & SkDOM.  We use the former in UTF-8 mode, and the
latter treats everything as 8bit/char strings - but it is mostly pass-through,
so it prolly doesn't matter.

So I guess we're currently getting fed UTF-8 strings, which seems fine as far as
SVG attribute parsing is concerned.
Yeah, off hand I think we could either

a) parameterize everything on CharType (Match, LIT, ...?)

b) keep using char, declare everything UTF-8, leave it up to the implementations
to decode if/as needed.

I'm inclined to stick with b) for now, as it seems sufficient for the immediate
use case.  WDYT?

+    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;
+    }
+};
+
+/**
+ * Matches a letter (['a'-'z','A'-Z']) and returns the matched

[bungeman-skia, 2016/08/24 15:04:20]

nit: missing a ' before Z

[f(malita), 2016/08/24 17:17:02]

Done.

+ * character as the MatchResult value.
+ *
+ */
+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;
+    }
+};
+
+/**
+ * Matches a digit ([0-9]) and returns the matched char
+ * as the MatchResult value.
+ */
+struct Digit {

[bungeman-skia, 2016/08/24 15:04:20]

Most of the structs here are nice and generic, but Alpha and Digit aren't
really. Every specification seems to have it's own definitions like which
numeral systems (https://en.wikipedia.org/wiki/Numeral_system) are supported and
which code points are legal or considered 'Alpha'. These structs do document
what they do and are useful, it just makes me feel uneasy that the purely
mechanical part is in the same header with these (which seem more part of a
specific parser grammar).

[f(malita), 2016/08/24 17:17:02]

Good point.  I was thinking it'd be helpful to provide some basic atoms, but
yeah, if we remove these then we gain a lot in generality.  Except for maybe
LIT, no one even cares what the encoding is anymore.

I like that.  Moved to the test file.

+    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;
+    }
+};
+
+} // skpeg ns
+
+#endif // SkPEG_DEFINED