Reland: Experimental parsing expression grammar (PEG) template library

experimental/svg/model/SkPEG.h

+/*
+ * 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 T>

[mtklein, 2016/08/24 01:19:28]

Not clear here why this is parameterized on T and not V directly.

[f(malita), 2016/08/24 13:47:29]

True, doesn't do much, does it?  Changed to straight V.

+struct MatchResult {
+    using V = typename T::V;
+
+    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;
+    };
+
+    static MatchResult<Opt> Match(const char* in) {
+        const auto m = E::Match(in);
+        return m ? MatchResult<Opt>(m.fNext, V(m.fValue.get()))

[mtklein, 2016/08/24 01:19:28]

Depending on how that T/V parameterization question goes, it might be neat to
write a little helper to make creating positive MatchResults less repetitive:

template <typename V>
static MatchResult<V> match_result(const char* next, const V& v) {
    return { next, v };
}

[f(malita), 2016/08/24 13:47:29]

I ended up adding a MatchT alias, as it's also applicable to the return type
here.  I think that covers your comment, PTAL.

+                 : MatchResult<Opt>(in, nullptr);
+    }
+};
+
+/**
+ * Sequence operator (e1e2).
+ *
+ * Succeeds when both e1 and e2 match, in sequence.  The subexpression match
+ * results are stored in |v1|, |v2|.
+ *
+ */
+template <typename E1, typename E2>
+struct Seq {

[bungeman-skia, 2016/08/23 20:49:18]

While I'm not sure off hand how to do it, having Seq (especially) take a
variable number of types here would be nice, since otherwise these get nested
like crazy, making it difficult to follow the logic.

[mtklein, 2016/08/24 01:19:28]

Might make sense to have Seq stay binary, but build another n-ary List operator
on top.  May be as simple as:

template <typename... Es> 
struct List;

template <typename E>
struct List<E> : public E {}

template <typename First, typename... Rest>
struct List<First, Rest...> : public Seq<First, List<Rest...>> {}

[f(malita), 2016/08/24 13:47:29]

That's an elegant approach.

One thing I like about making Seq itself a list is that we have this
cool/uniform accessor get<I>().  Maybe something similar could be implemented on
top of List?

[f(malita), 2016/08/24 13:47:29]

Yeah, that would definitely be nice.

At the time I hadn't figured out all the details, but by now I think I've beaten
it into submission.  Certainly seems to help.

(Done)

+    struct V {
+        V(const typename E1::V& v1, const typename E2::V& v2) : v1(v1), v2(v2) {}
+
+        typename E1::V v1;
+        typename E2::V v2;
+    };
+
+    static MatchResult<Seq> Match(const char* in) {
+        const auto m1 = E1::Match(in);
+        if (!m1) {
+            return nullptr;
+        }
+        const auto m2 = E2::Match(m1.fNext);
+        if (!m2) {
+            return nullptr;
+        }
+        return MatchResult<Seq>(m2.fNext, V(*m1, *m2));
+    }
+};
+
+/**
+ * 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;
+    };
+
+    static MatchResult<Choice> Match(const char* in) {
+        if (const auto m1 = E1::Match(in)) {
+            return MatchResult<Choice>(m1.fNext, V(m1.fValue.get(), nullptr));
+        }
+        if (const auto m2 = E2::Match(in)) {
+            return MatchResult<Choice>(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;
+    };
+
+    static MatchResult<Any> Match(const char* in) {
+        SkTDArray<typename E::V> values;
+        for (;;) {
+            if (const auto m = E::Match(in)) {
+                in = m.fNext;
+                *values.append() = *m;
+            } else {
+                break;
+            }
+        }
+
+        return MatchResult<Any>(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>
+struct Some {

[mtklein, 2016/08/24 01:19:28]

Perhaps
    template <typename E>
    using Some = Seq<E, Any<E>>;
?

[f(malita), 2016/08/24 13:47:29]

The only downside is that the value accessor is no longer uniform (seq accessor
for the first value, seq + any for subsequent).  Probably not all that
important.

Done.

+    struct V {
+        V(SkTDArray<typename E::V>&& vs) : fValues(vs) {}
+
+        SkTDArray<typename E::V> fValues;
+    };
+
+    static MatchResult<Some> Match(const char* in) {
+        auto m = Any<E>::Match(in);
+        SkASSERT(m);
+
+        return m->fValues.isEmpty()
+            ? nullptr
+            : MatchResult<Some>(m.fNext, V(std::move(m.fValue.get()->fValues)));
+    }
+};
+
+/**
+ * End-of-string atom.  Matches \0.
+ */
+struct EOS {
+    struct V {};
+
+    static MatchResult<EOS> Match(const char* in) {
+        return *in ? nullptr : MatchResult<EOS>(in, V());

[mtklein, 2016/08/24 01:19:28]

probably nice to write out (*in != '\0') 

[f(malita), 2016/08/24 13:47:29]

Done.

+    }
+};
+
+
+/**
+ * Literal atom.  Matches a list of char literals.

[mtklein, 2016/08/24 01:19:28]

You may find this more or less annoying, but it is possible to take const char*
as a template parameter as long as you do not inline the literal:

#include <stdio.h>
#include <string.h>

template <const char* A>
struct Printer {
    void print() {
        printf("%zu, %s\n", strlen(A), A);
    }
};

static const char hello[] = "Hello!";

int main(void) {
    Printer<hello> p;
    p.print();

    return 0;
}

Printer<"Hello!"> would not work.

[f(malita), 2016/08/24 13:47:29]

Heh, I heard rumors of this unnatural ability :)

I guess the no-inline literal part makes it kinda awkward to use - maybe we
could add as a separate LITS version?

+ */
+template <char... Cs> struct LIT;
+
+template <>
+struct LIT<> {
+    struct V {};
+
+    static MatchResult<LIT> Match(const char* in) {
+        return MatchResult<LIT>(in, V());
+    }
+};
+
+template <char C, char... Cs>
+struct LIT<C, Cs...> {
+    struct V {};
+
+    static MatchResult<LIT> Match(const char* in) {
+        if (*in != C) {
+            return nullptr;
+        }
+        const auto m = LIT<Cs...>::Match(in + 1);
+        return m ? MatchResult<LIT>(m.fNext, V()) : nullptr;
+    }
+};
+
+/**
+ * Matches a letter (['a'-'z','A'-Z']) and returns the matched
+ * character as the MatchResult value.
+ *
+ */
+struct Alpha {
+    using V = char;
+
+    static MatchResult<Alpha> Match(const char* in) {
+        static constexpr unsigned kAlphaRange = 'z' - 'a';
+        return static_cast<unsigned>(*in - 'a') <= kAlphaRange
+            || static_cast<unsigned>(*in - 'A') <= kAlphaRange
+            ? MatchResult<Alpha>(in + 1, *in)
+            : nullptr;
+    }
+};
+
+/**
+ * Matches a digit ([0-9]) and returns the matched char
+ * as the MatchResult value.
+ */
+struct Digit {
+    using V = uint8_t;
+
+    static MatchResult<Digit> Match(const char* in) {
+        static constexpr unsigned kDigitRange = '9' - '0';
+        return static_cast<unsigned>(*in - '0') <= kDigitRange
+            ? MatchResult<Digit>(in + 1, SkTo<uint8_t>(*in - '0'))
+            : nullptr;
+    }
+};
+
+} // skpeg ns
+
+#endif // SkPEG_DEFINED