source: icGREP/icgrep-devel/icgrep/re/re_parser_bre.cpp @ 5181

Last change on this file since 5181 was 5181, checked in by xwa163, 3 years ago

fix undefined vtable caused by llvm O3 optimization for inline function

File size: 13.6 KB
Line 
1/*
2 *  Copyright (c) 2016 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include <re/re_parser_bre.h>
8#include <re/re_parser_helper.h>
9#include <re/re_alt.h>
10#include <re/re_seq.h>
11#include <re/re_start.h>
12#include <re/re_end.h>
13#include <re/re_assertion.h>
14#include <re/re_rep.h>
15
16namespace re{
17
18    // \d and \D Removed
19    const uint64_t setEscapeCharacters = bit3C('b') | bit3C('p') | bit3C('q') | bit3C('w') | bit3C('s') | bit3C('<') | bit3C('>') |
20                                         bit3C('B') | bit3C('P') | bit3C('Q') | bit3C('W') | bit3C('S') | bit3C('N') | bit3C('X');
21
22    bool RE_Parser_BRE::isSetEscapeChar(char c) {
23        return c >= 0x3C && c <= 0x7B && ((setEscapeCharacters >> (c - 0x3C)) & 1) == 1;
24    }
25
26    inline bool RE_Parser_BRE::isUnsupportChartsetOperator(char c) {
27        switch (c) {
28            case '\\':
29                return true;
30            default:
31                return false;
32        }
33    }
34
35    RE * RE_Parser_BRE::parse_alt() {
36        std::vector<RE *> alt;
37        for (;;) {
38            alt.push_back(parse_seq());
39
40            if (!isEscapedCharAhead('|')) {
41                break;
42            }
43            ++mCursor; // advance past the alternation character '\'
44            ++mCursor; // advance past the alternation character '|'
45        }
46        if (alt.empty()) {
47            ParseFailure("No regular expression found!");
48        }
49        return makeAlt(alt.begin(), alt.end());
50    }
51
52    RE * RE_Parser_BRE::parse_next_item() {
53        RE * re = nullptr;
54        if (mCursor.more()) {
55            switch (*mCursor) {
56                case '^':
57                    ++mCursor;
58                    return makeStart();
59                case '$':
60                    ++mCursor;
61                    return makeEnd();
62                case '*':
63                    ParseFailure("Need something to repeat before *, \\+, \\? or \\{.");
64                case ']':
65                    if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
66                        return createCC(parse_utf8_codepoint());
67                    }
68                    ParseFailure("Use  \\] for literal ].");
69                case '[':
70                    mCursor++;
71                    re = parse_charset();
72                    if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
73                        re = makeSeq({re, makeZeroWidth("GCB")});
74                    }
75                    return re;
76                case '.': // the 'any' metacharacter
77                    mCursor++;
78                    return makeAny();
79                case '\\'// escape processing
80                    return parse_escaped();
81                default:
82                    re = createCC(parse_utf8_codepoint());
83                    if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
84                        fGraphemeBoundaryPending = true;
85                    }
86                    return re;
87            }
88        }
89        return nullptr;
90    }
91
92    inline RE * RE_Parser_BRE::parse_escaped() {
93        if (mCursor.remaining() < 2) {
94            ParseFailure("Redundant \\ in the end");
95        }
96        auto nextCursor = mCursor.pos() + 1;
97        switch (*nextCursor) {
98            case '(':
99                ++mCursor;
100                ++mCursor;
101                return parse_group();
102            case '|': case ')':
103                return nullptr;
104            case '}':
105                if (fNested) {
106                    return nullptr;  //  a recursive invocation for a regexp in \N{...}
107                } else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
108                    ++mCursor;
109                    return createCC(parse_utf8_codepoint());
110                }
111                ParseFailure("Use \\} for literal }.");
112            case '+': case '?': case '{':
113                ParseFailure("Need something to repeat before *, \\+, \\? or \\{.");
114        }
115
116        ++mCursor;
117        if (isSetEscapeChar(*mCursor)) {
118            return parseEscapedSet();
119        }
120        else if (isdigit(*mCursor)) {
121            mCursor++;
122            std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
123            auto key = std::make_pair("", backref);
124            auto f = mNameMap.find(key);
125            if (f != mNameMap.end()) {
126                return makeReference(backref, f->second);
127            }
128            else {
129                ParseFailure("Back reference " + backref + " without prior capture group.");
130            }
131        }
132        else {
133            return createCC(parse_escaped_codepoint());
134        }
135    }
136
137    RE * RE_Parser_BRE::extend_item(RE * re) {
138        if (LLVM_LIKELY(mCursor.more())) {
139            if (*mCursor == '*') {
140                return RE_Parser::extend_item(re);
141            } else if (*mCursor == '\\') {
142                if (mCursor.remaining() < 2) {
143                    ParseFailure("Redundant \\ in the end");
144                }
145                if (isCharAhead('?') || isCharAhead('+')) {
146                    ++mCursor;
147                    return RE_Parser::extend_item(re);
148                } else if (isCharAhead('{')) {
149                    ++mCursor;
150                    auto ret = RE_Parser::extend_item(re);
151                    ++mCursor;  //Skip '}'
152                    return ret;
153                }
154            }
155        }
156        return re;
157    }
158
159    // Parse some kind of parenthesized group.  Input precondition: mCursor
160    // after the (
161    RE * RE_Parser_BRE::parse_group() {
162        RE * group_expr = nullptr;
163        // Capturing paren group.
164        RE * captured = parse_alt();
165        mCaptureGroupCount++;
166        std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
167        Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
168        auto key = std::make_pair("", captureName);
169        mNameMap.insert(std::make_pair(std::move(key), capture));
170        group_expr = capture;
171
172        if (!isEscapedCharAhead(')')) {
173            ParseFailure("Closing parenthesis required.");
174        }
175        ++mCursor;
176        ++mCursor;
177        return group_expr;
178    }
179
180    inline bool RE_Parser_BRE::isEscapedCharAhead(char c) {
181        if (*mCursor != '\\') {
182            return false;
183        }
184        if (mCursor.remaining() < 2) {
185            ParseFailure("Redundant \\ in the end");
186        }
187        return isCharAhead(c);
188    }
189
190    inline bool RE_Parser_BRE::isCharAhead(char c) {
191        if (mCursor.remaining() < 2) {
192            return false;
193        }
194        auto nextCursor = mCursor.pos() + 1;
195        return *nextCursor == c;
196    }
197
198    inline std::pair<int, int> RE_Parser_BRE::parse_range_bound() {
199        int lower_bound = 0, upper_bound = 0;
200        if (*++mCursor != ',') {
201            lower_bound = parse_int();
202        }
203
204        if (isEscapedCharAhead('}')) {
205            upper_bound = lower_bound;
206        } else if (*mCursor != ',') {
207            ParseFailure("Bad lower bound!");
208        } else if (++mCursor, isEscapedCharAhead('}')) {
209            upper_bound = Rep::UNBOUNDED_REP;
210        } else {
211            upper_bound = parse_int();
212            if (!isEscapedCharAhead('}')) {
213                ParseFailure("Bad upper bound!");
214            }
215        }
216        return std::make_pair(lower_bound, upper_bound);
217    }
218
219    // A backslash escape was found, and various special cases (back reference,
220    // quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
221    // cluster \X have been ruled out.
222    // It may be one of several possibilities or an error sequence.
223    // 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
224    // 2. General control codes c[@-_a-z?]
225    // 3. Restricted octal notation 0 - 0777
226    // 4. General octal notation o\{[0-7]+\}
227    // 5. General hex notation x\{[0-9A-Fa-f]+\}
228    // 6. An error for any unrecognized alphabetic escape
229    // 7. An escaped ASCII symbol, standing for itself
230
231    codepoint_t RE_Parser_BRE::parse_escaped_codepoint() {
232        codepoint_t cp_value;
233        switch (*mCursor) {
234            case 'o':
235                ++mCursor;
236                if (isEscapedCharAhead('{')) {
237                    ++mCursor;
238                    ++mCursor;
239                    cp_value = parse_octal_codepoint(1, 7);
240                    if (!isEscapedCharAhead('}')) ParseFailure("Malformed octal escape sequence");
241                    ++mCursor;
242                    ++mCursor;
243                    return cp_value;
244                }
245                else {
246                    ParseFailure("Malformed octal escape sequence");
247                }
248            case 'x':
249                ++mCursor;
250                if (isEscapedCharAhead('{')) {
251                    ++mCursor;
252                    ++mCursor;
253                    cp_value = parse_hex_codepoint(1, 6);
254                    if (!isEscapedCharAhead('}')) ParseFailure("Malformed hex escape sequence");
255                    ++mCursor;
256                    ++mCursor;
257                    return cp_value;
258                }
259                else {
260                    return parse_hex_codepoint(1,2);  // ICU compatibility
261                }
262            case 'u':
263                ++mCursor;
264                if (isEscapedCharAhead('{')) {
265                    ++mCursor;
266                    ++mCursor;
267                    cp_value = parse_hex_codepoint(1, 6);
268                    if (!isEscapedCharAhead('}')) ParseFailure("Malformed hex escape sequence");
269                    ++mCursor;
270                    ++mCursor;
271                    return cp_value;
272                }
273                else {
274                    return parse_hex_codepoint(4,4);  // ICU compatibility
275                }
276            default:
277                return RE_Parser::parse_escaped_codepoint();
278        }
279    }
280
281    RE * RE_Parser_BRE::parsePropertyExpression() {
282        const auto start = mCursor.pos();
283        while (mCursor.more()) {
284            bool done = false;
285            if (isEscapedCharAhead('}')) {
286                done = true;
287            } else {
288                switch (*mCursor) {
289                    case ':': case '=':
290                        done = true;
291                }
292            }
293            if (done) {
294                break;
295            }
296            ++mCursor;
297        }
298        if (*mCursor == '=') {
299            const auto prop_end = mCursor.pos();
300            mCursor++;
301            const auto val_start = mCursor.pos();
302            while (mCursor.more()) {
303                if (isEscapedCharAhead('}') || *mCursor == ':') {
304                    break;
305                }
306                ++mCursor;
307            }
308            // We have a property-name = value expression
309            return createName(canonicalize(start, prop_end), canonicalize(val_start, mCursor.pos()));
310        }
311        return createName(canonicalize(start, mCursor.pos()));
312    }
313
314    RE * RE_Parser_BRE::parseEscapedSet() {
315        bool complemented = false;
316        RE * re = nullptr;
317        switch (*mCursor) {
318            case 'b':
319                ++mCursor;
320                if (!isEscapedCharAhead('{')) {
321                    return complemented ? makeWordNonBoundary() : makeWordBoundary();
322                } else {
323                    ++mCursor;
324                    switch (*++mCursor) {
325                        case 'g':
326                            re = complemented ? makeZeroWidth("NonGCB") : makeZeroWidth("GCB");
327                            break;
328                        case 'w': ParseFailure("\\b{w} not yet supported.");
329                        case 'l': ParseFailure("\\b{l} not yet supported.");
330                        case 's': ParseFailure("\\b{s} not yet supported.");
331                        default: ParseFailure("Unrecognized boundary assertion");
332                    }
333                    ++mCursor;
334                    if (!isEscapedCharAhead('}')) {
335                        ParseFailure("Malformed boundary assertion");
336                    }
337                    ++mCursor;
338                    ++mCursor;
339                    return re;
340                }
341            case 'q':
342                ++mCursor;
343                if (!isEscapedCharAhead('{')) {
344                    ParseFailure("Malformed grapheme-boundary property expression");
345                }
346                ++mCursor;
347                ++mCursor;
348                ParseFailure("Literal grapheme cluster expressions not yet supported.");
349                if (!isEscapedCharAhead('}')) {
350                    ParseFailure("Malformed grapheme-boundary property expression");
351                }
352                ++mCursor;
353                ++mCursor;
354                return complemented ? makeComplement(re) : re;
355            case 'p':
356                ++mCursor;
357                if (!isEscapedCharAhead('{')) {
358                    ParseFailure("Malformed property expression");
359                }
360                ++mCursor;
361                ++mCursor;
362                re = parsePropertyExpression();
363                if (!isEscapedCharAhead('}')) {
364                    ParseFailure("Malformed property expression");
365                }
366                ++mCursor;
367                ++mCursor;
368                return complemented ? makeComplement(re) : re;
369            case 'N':
370                ++mCursor;
371                if (!isEscapedCharAhead('{')) {
372                    ParseFailure("Malformed \\N expression");
373                }
374                ++mCursor;
375                ++mCursor;
376                re = parseNamePatternExpression();
377                if (!isEscapedCharAhead('}')) {
378                    ParseFailure("Malformed \\N expression");
379                }
380                ++mCursor;
381                ++mCursor;
382                assert (re);
383                return re;
384            default:
385                return RE_Parser::parseEscapedSet();
386        }
387    }
388}
Note: See TracBrowser for help on using the repository browser.