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

Last change on this file since 5206 was 5206, checked in by xwa163, 3 years ago
  1. Extend Regex Syntax, include: (a) RL2.6 of UTS#18, support regex in property value. e.g. \p{script=/.*hir.*/} (b) Support syntax of property expression when parsing boundary. e.g. \b{greek} (c) Extend property expression in non capture group. e.g. (?\p{upper}:\p{greek}\p{script=hira})
  2. Add related test cases
File size: 14.3 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_with_intersect(RE *reToBeIntersected) {
36        std::vector<RE *> alt;
37        for (;;) {
38            alt.push_back(parse_seq_with_intersect(reToBeIntersected));
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 std::pair<int, int> RE_Parser_BRE::parse_range_bound() {
191        int lower_bound = 0, upper_bound = 0;
192        if (*++mCursor != ',') {
193            lower_bound = parse_int();
194        }
195
196        if (isEscapedCharAhead('}')) {
197            upper_bound = lower_bound;
198        } else if (*mCursor != ',') {
199            ParseFailure("Bad lower bound!");
200        } else if (++mCursor, isEscapedCharAhead('}')) {
201            upper_bound = Rep::UNBOUNDED_REP;
202        } else {
203            upper_bound = parse_int();
204            if (!isEscapedCharAhead('}')) {
205                ParseFailure("Bad upper bound!");
206            }
207        }
208        return std::make_pair(lower_bound, upper_bound);
209    }
210
211    // A backslash escape was found, and various special cases (back reference,
212    // quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
213    // cluster \X have been ruled out.
214    // It may be one of several possibilities or an error sequence.
215    // 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
216    // 2. General control codes c[@-_a-z?]
217    // 3. Restricted octal notation 0 - 0777
218    // 4. General octal notation o\{[0-7]+\}
219    // 5. General hex notation x\{[0-9A-Fa-f]+\}
220    // 6. An error for any unrecognized alphabetic escape
221    // 7. An escaped ASCII symbol, standing for itself
222
223    codepoint_t RE_Parser_BRE::parse_escaped_codepoint() {
224        codepoint_t cp_value;
225        switch (*mCursor) {
226            case 'o':
227                ++mCursor;
228                if (isEscapedCharAhead('{')) {
229                    ++mCursor;
230                    ++mCursor;
231                    cp_value = parse_octal_codepoint(1, 7);
232                    if (!isEscapedCharAhead('}')) ParseFailure("Malformed octal escape sequence");
233                    ++mCursor;
234                    ++mCursor;
235                    return cp_value;
236                }
237                else {
238                    ParseFailure("Malformed octal escape sequence");
239                }
240            case 'x':
241                ++mCursor;
242                if (isEscapedCharAhead('{')) {
243                    ++mCursor;
244                    ++mCursor;
245                    cp_value = parse_hex_codepoint(1, 6);
246                    if (!isEscapedCharAhead('}')) ParseFailure("Malformed hex escape sequence");
247                    ++mCursor;
248                    ++mCursor;
249                    return cp_value;
250                }
251                else {
252                    return parse_hex_codepoint(1,2);  // ICU compatibility
253                }
254            case 'u':
255                ++mCursor;
256                if (isEscapedCharAhead('{')) {
257                    ++mCursor;
258                    ++mCursor;
259                    cp_value = parse_hex_codepoint(1, 6);
260                    if (!isEscapedCharAhead('}')) ParseFailure("Malformed hex escape sequence");
261                    ++mCursor;
262                    ++mCursor;
263                    return cp_value;
264                }
265                else {
266                    return parse_hex_codepoint(4,4);  // ICU compatibility
267                }
268            default:
269                return RE_Parser::parse_escaped_codepoint();
270        }
271    }
272
273    RE * RE_Parser_BRE::parsePropertyExpression() {
274        const auto start = mCursor.pos();
275        while (mCursor.more()) {
276            bool done = false;
277            if (isEscapedCharAhead('}')) {
278                done = true;
279            } else {
280                switch (*mCursor) {
281                    case ':': case '=':
282                        done = true;
283                }
284            }
285            if (done) {
286                break;
287            }
288            ++mCursor;
289        }
290        if (*mCursor == '=') {
291            // We have a property-name = value expression
292            const auto prop_end = mCursor.pos();
293            mCursor++;
294            auto val_start = mCursor.pos();
295            if (*val_start != '\\' || !isCharAhead('/')) {
296                // property-value is normal string
297                while (mCursor.more()) {
298                    if (isEscapedCharAhead('}') || *mCursor == ':') {
299                        break;
300                    }
301                    ++mCursor;
302                }
303                return createName(canonicalize(start, prop_end), canonicalize(val_start, mCursor.pos()));
304            } else {
305                // property-value is another regex
306                ++mCursor;
307                auto previous = val_start;
308                auto current = (++mCursor).pos();
309                val_start = current;
310
311                while (true) {
312                    if (*current == '/' && *previous == '\\') {
313                        break;
314                    }
315
316                    if (!mCursor.more()) {
317                        ParseFailure("Malformed property expression");
318                    }
319
320                    previous = current;
321                    current = (++mCursor).pos();
322                }
323                ++mCursor;
324                return parseRegexPropertyValue(canonicalize(start, prop_end), canonicalize(val_start, previous));
325            }
326        }
327        return createName(canonicalize(start, mCursor.pos()));
328    }
329
330    RE * RE_Parser_BRE::parseEscapedSet() {
331        bool complemented = false;
332        RE * re = nullptr;
333        switch (*mCursor) {
334            case 'b':
335                ++mCursor;
336                if (!isEscapedCharAhead('{')) {
337                    return complemented ? makeWordNonBoundary() : makeWordBoundary();
338                } else {
339                    ++mCursor;
340                    switch (*++mCursor) {
341                        case 'g':
342                            re = complemented ? makeZeroWidth("NonGCB") : makeZeroWidth("GCB");
343                            break;
344                        case 'w': ParseFailure("\\b{w} not yet supported.");
345                        case 'l': ParseFailure("\\b{l} not yet supported.");
346                        case 's': ParseFailure("\\b{s} not yet supported.");
347                        default: ParseFailure("Unrecognized boundary assertion");
348                    }
349                    ++mCursor;
350                    if (!isEscapedCharAhead('}')) {
351                        ParseFailure("Malformed boundary assertion");
352                    }
353                    ++mCursor;
354                    ++mCursor;
355                    return re;
356                }
357            case 'q':
358                ++mCursor;
359                if (!isEscapedCharAhead('{')) {
360                    ParseFailure("Malformed grapheme-boundary property expression");
361                }
362                ++mCursor;
363                ++mCursor;
364                ParseFailure("Literal grapheme cluster expressions not yet supported.");
365                if (!isEscapedCharAhead('}')) {
366                    ParseFailure("Malformed grapheme-boundary property expression");
367                }
368                ++mCursor;
369                ++mCursor;
370                return complemented ? makeComplement(re) : re;
371            case 'p':
372                ++mCursor;
373                if (!isEscapedCharAhead('{')) {
374                    ParseFailure("Malformed property expression");
375                }
376                ++mCursor;
377                ++mCursor;
378                re = parsePropertyExpression();
379                if (!isEscapedCharAhead('}')) {
380                    ParseFailure("Malformed property expression");
381                }
382                ++mCursor;
383                ++mCursor;
384                return complemented ? makeComplement(re) : re;
385            case 'N':
386                ++mCursor;
387                if (!isEscapedCharAhead('{')) {
388                    ParseFailure("Malformed \\N expression");
389                }
390                ++mCursor;
391                ++mCursor;
392                re = parseNamePatternExpression();
393                if (!isEscapedCharAhead('}')) {
394                    ParseFailure("Malformed \\N expression");
395                }
396                ++mCursor;
397                ++mCursor;
398                assert (re);
399                return re;
400            default:
401                return RE_Parser::parseEscapedSet();
402        }
403    }
404}
Note: See TracBrowser for help on using the repository browser.