From 6cf896d7ce03b87b3a5595bc66caf0a34c993755 Mon Sep 17 00:00:00 2001 From: fmalita Date: Thu, 25 Aug 2016 08:44:35 -0700 Subject: [PATCH] Reland: Experimental parsing expression grammar (PEG) template library BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2271743002 Committed: https://skia.googlesource.com/skia/+/9d08cbc8c6131ff61a1e71cc5c8cf27841d62b42 Review-Url: https://codereview.chromium.org/2271743002 --- BUILD.gn | 1 + experimental/svg/model/SkPEG.h | 244 +++++++++++++++++++++++++++++++++ gyp/svg.gyp | 2 + tests/SkPEGTest.cpp | 304 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 551 insertions(+) create mode 100644 experimental/svg/model/SkPEG.h create mode 100644 tests/SkPEGTest.cpp diff --git a/BUILD.gn b/BUILD.gn index 8bc4505..6774890 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -640,6 +640,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 0000000..596a570 --- /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 "SkTArray.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 +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 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 +struct Opt { + struct V { + V(const typename E::V* v) : fValue(v) {} + + SkTLazy fValue; + }; + using MatchT = MatchResult; + + 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 struct SelectV; + +template +struct SelectV<0, E, Es...> { + using V = typename E::V; +}; + +template +struct SelectV { + using V = typename SelectV::V; +}; + +/** + * Sequence operator (e0 e1...). + * + * Succeeds when all expressions match, in sequence. The subexpression match + * results can be accessed via get() -- where get<0> returns the value + * of the first expression, and so on. + * + */ +template struct Seq; + +template <> +struct Seq<> { + struct V {}; + using MatchT = MatchResult; + + static MatchT Match(const char* in) { + return MatchT(in, V()); + } +}; + +template +struct Seq { + class V { + public: + V(const typename E::V& head, const typename Seq::V& tail) + : fHeadV(head), fTailV(tail) {} + + template ::type = 0> + const typename E::V& get() const { + return fHeadV; + } + + template ::type = 0> + const typename SelectV::V& get() const { + return fTailV.template get(); + } + + private: + typename E::V fHeadV; + typename Seq::V fTailV; + }; + using MatchT = MatchResult; + + static MatchT Match(const char* in) { + const auto headMatch = E::Match(in); + if (!headMatch) { + return nullptr; + } + + const auto tailMatch = Seq::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 +struct Choice { + struct V { + V (const typename E1::V* v1, const typename E2::V* v2) : v1(v1), v2(v2) + { + SkASSERT(!v1 || !v2); + } + + SkTLazy v1; + SkTLazy v2; + }; + using MatchT = MatchResult; + + 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 +struct Any { + struct V { + V(SkTArray&& vs) : fValues(vs) {} + + SkTArray fValues; + }; + using MatchT = MatchResult; + + static MatchT Match(const char* in) { + SkTArray values; + while (const auto m = E::Match(in)) { + in = m.fNext; + values.push_back(*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 +using Some = Seq>; + +/** + * End-of-string atom. Matches \0. + */ +struct EOS { + struct V {}; + using MatchT = MatchResult; + + static MatchT Match(const char* in) { + return (*in != '\0') ? nullptr : MatchT(in, V()); + } +}; + + +/** + * Literal atom. Matches a list of char literals. + */ +template struct LIT; + +template <> +struct LIT<> { + struct V {}; + using MatchT = MatchResult; + + static MatchT Match(const char* in) { + return MatchT(in, V()); + } +}; + +template +struct LIT { + struct V {}; + using MatchT = MatchResult; + + static MatchT Match(const char* in) { + if (*in != C) { + return nullptr; + } + const auto m = LIT::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 158a399..1160b94 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 0000000..6773c1b --- /dev/null +++ b/tests/SkPEGTest.cpp @@ -0,0 +1,304 @@ +/* + * 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 "Test.h" + +#if defined(SK_XML) +#include "SkPEG.h" + +using namespace skpeg; + +namespace { + +struct Alpha { + using V = char; + using MatchT = MatchResult; + + static MatchT Match(const char* in) { + static constexpr unsigned kAlphaRange = 'z' - 'a'; + return static_cast(*in - 'a') <= kAlphaRange + || static_cast(*in - 'A') <= kAlphaRange + ? MatchT(in + 1, *in) + : nullptr; + } +}; + +struct Digit { + using V = uint8_t; + using MatchT = MatchResult; + + static MatchT Match(const char* in) { + static constexpr unsigned kDigitRange = '9' - '0'; + return static_cast(*in - '0') <= kDigitRange + ? MatchT(in + 1, SkTo(*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>::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, EOS>::Match("X"))); + REPORTER_ASSERT(r, !(Seq, EOS>::Match("x"))); + REPORTER_ASSERT(r, !(Seq, EOS>::Match("xX"))); + REPORTER_ASSERT(r, !(Seq, EOS>::Match("XX"))); + REPORTER_ASSERT(r, (Seq, Seq, EOS>>::Match("XX"))); + REPORTER_ASSERT(r, (Seq, Seq, EOS>>::Match("XX"))); + + REPORTER_ASSERT(r, !(Seq, EOS>::Match("FooBar"))); + REPORTER_ASSERT(r, (Seq, EOS>::Match("Foo"))); + + { + const auto m = Seq, Digit>::Match("x5"); + REPORTER_ASSERT(r, m); + REPORTER_ASSERT(r, m->get<1>() == 5); + } + { + const auto m = Seq::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::Match(""))); + REPORTER_ASSERT(r, !(Choice::Match("\t"))); + REPORTER_ASSERT(r, !(Choice::Match(" "))); + REPORTER_ASSERT(r, (Choice::Match("a"))); + REPORTER_ASSERT(r, (Choice::Match("3"))); + REPORTER_ASSERT(r, (Choice::Match("a "))); + REPORTER_ASSERT(r, (Choice::Match("3 "))); + REPORTER_ASSERT(r, !(Choice::Match(" a "))); + REPORTER_ASSERT(r, !(Choice::Match(" 3 "))); + + { + const auto m = Choice::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::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>::Match(gTests[i].fInput); + REPORTER_ASSERT(r, matchAny); + REPORTER_ASSERT(r, matchAny->fValues.count() == gTests[i].fCount); + + const auto matchSome = Some>::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::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, + Opt, + Some>>, + 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>, + Choice, LIT<'f'>>, + LIT<'o', 'o'>, + Some, LIT<'b'>>, + LIT<'a', 'r'>>>, + Choice, LIT<'b'>>, + LIT<'a', 'z'>, + Any>, + 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); +} + +#endif // SK_XML -- 2.7.4