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
14namespace 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 */
24template <typename V>
25struct 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 */
48template <typename E>
49struct 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 */
67template <size_t, typename... Es> struct SelectV;
68
69template <typename E, typename... Es>
70struct SelectV<0, E, Es...> {
71    using V = typename E::V;
72};
73
74template <size_t idx, typename E, typename... Es>
75struct 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 */
87template <typename... E> struct Seq;
88
89template <>
90struct 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
99template <typename E, typename... Es>
100struct 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 */
142template <typename E1, typename E2>
143struct 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 */
172template <typename E>
173struct 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 */
197template <typename E>
198using Some = Seq<E, Any<E>>;
199
200/**
201 * End-of-string atom.  Matches \0.
202 */
203struct 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 */
216template <char... Cs> struct LIT;
217
218template <>
219struct 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
228template <char C, char... Cs>
229struct 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