fmalita | 6cf896d | 2016-08-25 08:44:35 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2016 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
| 8 | #ifndef SkPEG_DEFINED |
| 9 | #define SkPEG_DEFINED |
| 10 | |
| 11 | #include "SkTArray.h" |
| 12 | #include "SkTLazy.h" |
| 13 | |
| 14 | namespace skpeg { |
| 15 | |
| 16 | /** |
| 17 | * The result of an expression match attempt. |
| 18 | * |
| 19 | * If the match was successful, |fNext| points to the next unconsumed character in the |
| 20 | * input string, and |fValue| holds an (arbitrarily nested) match result value. |
| 21 | * |
| 22 | * Otherwise, |fNext| is nullptr and |fValue| is uninitialized. |
| 23 | */ |
| 24 | template <typename V> |
| 25 | struct MatchResult { |
| 26 | MatchResult(std::nullptr_t) : fNext(nullptr) {} |
| 27 | MatchResult(const char* next, const V& v) : fNext(next), fValue(&v) {} |
| 28 | |
| 29 | operator bool() const { |
| 30 | SkASSERT(fValue.isValid() == SkToBool(fNext)); |
| 31 | return SkToBool(fNext); |
| 32 | } |
| 33 | |
| 34 | const V& operator* () const { return *fValue.get(); } |
| 35 | const V* operator->() const { return fValue.get(); } |
| 36 | |
| 37 | const char* fNext; |
| 38 | SkTLazy<V> fValue; |
| 39 | }; |
| 40 | |
| 41 | /** |
| 42 | * Optional operator (e?). Always succeeds. |
| 43 | * |
| 44 | * If e also matches, then the result of e::Match() is stored in |fValue|. |
| 45 | * Otherwise, |fValue| is uninitialized. |
| 46 | * |
| 47 | */ |
| 48 | template <typename E> |
| 49 | struct Opt { |
| 50 | struct V { |
| 51 | V(const typename E::V* v) : fValue(v) {} |
| 52 | |
| 53 | SkTLazy<typename E::V> fValue; |
| 54 | }; |
| 55 | using MatchT = MatchResult<V>; |
| 56 | |
| 57 | static MatchT Match(const char* in) { |
| 58 | const auto m = E::Match(in); |
| 59 | return m ? MatchT(m.fNext, V(m.fValue.get())) |
| 60 | : MatchT(in, nullptr); |
| 61 | } |
| 62 | }; |
| 63 | |
| 64 | /** |
| 65 | * Helper for selecting the value type of the n-th expression type in the list. |
| 66 | */ |
| 67 | template <size_t, typename... Es> struct SelectV; |
| 68 | |
| 69 | template <typename E, typename... Es> |
| 70 | struct SelectV<0, E, Es...> { |
| 71 | using V = typename E::V; |
| 72 | }; |
| 73 | |
| 74 | template <size_t idx, typename E, typename... Es> |
| 75 | struct SelectV<idx, E, Es...> { |
| 76 | using V = typename SelectV<idx - 1, Es...>::V; |
| 77 | }; |
| 78 | |
| 79 | /** |
| 80 | * Sequence operator (e0 e1...). |
| 81 | * |
| 82 | * Succeeds when all expressions match, in sequence. The subexpression match |
| 83 | * results can be accessed via get<INDEX>() -- where get<0> returns the value |
| 84 | * of the first expression, and so on. |
| 85 | * |
| 86 | */ |
| 87 | template <typename... E> struct Seq; |
| 88 | |
| 89 | template <> |
| 90 | struct Seq<> { |
| 91 | struct V {}; |
| 92 | using MatchT = MatchResult<V>; |
| 93 | |
| 94 | static MatchT Match(const char* in) { |
| 95 | return MatchT(in, V()); |
| 96 | } |
| 97 | }; |
| 98 | |
| 99 | template <typename E, typename... Es> |
| 100 | struct Seq<E, Es...> { |
| 101 | class V { |
| 102 | public: |
| 103 | V(const typename E::V& head, const typename Seq<Es...>::V& tail) |
| 104 | : fHeadV(head), fTailV(tail) {} |
| 105 | |
| 106 | template <size_t idx, typename std::enable_if<idx == 0, bool>::type = 0> |
| 107 | const typename E::V& get() const { |
| 108 | return fHeadV; |
| 109 | } |
| 110 | |
| 111 | template <size_t idx, typename std::enable_if<idx != 0, bool>::type = 0> |
| 112 | const typename SelectV<idx, E, Es...>::V& get() const { |
| 113 | return fTailV.template get<idx - 1>(); |
| 114 | } |
| 115 | |
| 116 | private: |
| 117 | typename E::V fHeadV; |
| 118 | typename Seq<Es...>::V fTailV; |
| 119 | }; |
| 120 | using MatchT = MatchResult<V>; |
| 121 | |
| 122 | static MatchT Match(const char* in) { |
| 123 | const auto headMatch = E::Match(in); |
| 124 | if (!headMatch) { |
| 125 | return nullptr; |
| 126 | } |
| 127 | |
| 128 | const auto tailMatch = Seq<Es...>::Match(headMatch.fNext); |
| 129 | return tailMatch ? MatchT(tailMatch.fNext, V(*headMatch, *tailMatch)) |
| 130 | : nullptr; |
| 131 | } |
| 132 | }; |
| 133 | |
| 134 | /** |
| 135 | * Ordered choice operator (e1|e2). |
| 136 | * |
| 137 | * Succeeds when either e1 or e2 match (e1 is tried first, then e2). |
| 138 | * |
| 139 | * The (optional) match results are stored in |v1|, |v2|. |
| 140 | * |
| 141 | */ |
| 142 | template <typename E1, typename E2> |
| 143 | struct Choice { |
| 144 | struct V { |
| 145 | V (const typename E1::V* v1, const typename E2::V* v2) : v1(v1), v2(v2) |
| 146 | { |
| 147 | SkASSERT(!v1 || !v2); |
| 148 | } |
| 149 | |
| 150 | SkTLazy<typename E1::V> v1; |
| 151 | SkTLazy<typename E2::V> v2; |
| 152 | }; |
| 153 | using MatchT = MatchResult<V>; |
| 154 | |
| 155 | static MatchT Match(const char* in) { |
| 156 | if (const auto m1 = E1::Match(in)) { |
| 157 | return MatchT(m1.fNext, V(m1.fValue.get(), nullptr)); |
| 158 | } |
| 159 | if (const auto m2 = E2::Match(in)) { |
| 160 | return MatchT(m2.fNext, V(nullptr, m2.fValue.get())); |
| 161 | } |
| 162 | return nullptr; |
| 163 | } |
| 164 | }; |
| 165 | |
| 166 | /** |
| 167 | * Zero-or-more operator (e*). Always succeeds. |
| 168 | * |
| 169 | * Matches e greedily, and stores the match results in |fValues|. |
| 170 | * |
| 171 | */ |
| 172 | template <typename E> |
| 173 | struct Any { |
| 174 | struct V { |
| 175 | V(SkTArray<typename E::V>&& vs) : fValues(vs) {} |
| 176 | |
| 177 | SkTArray<typename E::V> fValues; |
| 178 | }; |
| 179 | using MatchT = MatchResult<V>; |
| 180 | |
| 181 | static MatchT Match(const char* in) { |
| 182 | SkTArray<typename E::V> values; |
| 183 | while (const auto m = E::Match(in)) { |
| 184 | in = m.fNext; |
| 185 | values.push_back(*m); |
| 186 | } |
| 187 | return MatchT(in, std::move(values)); |
| 188 | } |
| 189 | }; |
| 190 | |
| 191 | /** |
| 192 | * One-or-more operator (e+). |
| 193 | * |
| 194 | * Same as zero-or-more, except it fails if e doesn't match at least once. |
| 195 | * |
| 196 | */ |
| 197 | template <typename E> |
| 198 | using Some = Seq<E, Any<E>>; |
| 199 | |
| 200 | /** |
| 201 | * End-of-string atom. Matches \0. |
| 202 | */ |
| 203 | struct EOS { |
| 204 | struct V {}; |
| 205 | using MatchT = MatchResult<V>; |
| 206 | |
| 207 | static MatchT Match(const char* in) { |
| 208 | return (*in != '\0') ? nullptr : MatchT(in, V()); |
| 209 | } |
| 210 | }; |
| 211 | |
| 212 | |
| 213 | /** |
| 214 | * Literal atom. Matches a list of char literals. |
| 215 | */ |
| 216 | template <char... Cs> struct LIT; |
| 217 | |
| 218 | template <> |
| 219 | struct LIT<> { |
| 220 | struct V {}; |
| 221 | using MatchT = MatchResult<V>; |
| 222 | |
| 223 | static MatchT Match(const char* in) { |
| 224 | return MatchT(in, V()); |
| 225 | } |
| 226 | }; |
| 227 | |
| 228 | template <char C, char... Cs> |
| 229 | struct LIT<C, Cs...> { |
| 230 | struct V {}; |
| 231 | using MatchT = MatchResult<V>; |
| 232 | |
| 233 | static MatchT Match(const char* in) { |
| 234 | if (*in != C) { |
| 235 | return nullptr; |
| 236 | } |
| 237 | const auto m = LIT<Cs...>::Match(in + 1); |
| 238 | return m ? MatchT(m.fNext, V()) : nullptr; |
| 239 | } |
| 240 | }; |
| 241 | |
| 242 | } // skpeg ns |
| 243 | |
| 244 | #endif // SkPEG_DEFINED |