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

Last change on this file was 5267, checked in by nmedfort, 8 months ago

Code clean-up. Removed Pablo Call, SetIthBit? and Prototype.

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