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 "include/private/SkTArray.h"
12 #include "src/core/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 {
MatchResultMatchResult26     MatchResult(std::nullptr_t) : fNext(nullptr) {}
MatchResultMatchResult27     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 {
VOpt::V51         V(const typename E::V* v) : fValue(v) {}
52 
53         SkTLazy<typename E::V> fValue;
54     };
55     using MatchT = MatchResult<V>;
56 
MatchOpt57     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
245