source: icGREP/icgrep-devel/icgrep/re/re_parser.cpp @ 5515

Last change on this file since 5515 was 5515, checked in by cameron, 2 years ago

Allow repeated quantifiers in parsing, support possessive quantifiers, further optimizations

File size: 38.2 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.h>
8#include <re/re_parser_helper.h>
9#include <re/re_parser_pcre.h>
10#include <re/re_parser_ere.h>
11#include <re/re_parser_bre.h>
12#include <re/re_parser_prosite.h>
13#include <re/re_name.h>
14#include <re/re_alt.h>
15#include <re/re_any.h>
16#include <re/re_end.h>
17#include <re/re_rep.h>
18#include <re/re_seq.h>
19#include <re/re_start.h>
20#include <re/re_diff.h>
21#include <re/re_intersect.h>
22#include <re/re_assertion.h>
23#include <re/printer_re.h>
24#include <UCD/UnicodeNameData.h>
25#include <UCD/resolve_properties.h>
26#include <UCD/CaseFolding_txt.h>
27#include <grep_engine.h>
28#include <sstream>
29#include <string>
30#include <algorithm>
31#include <iostream>
32#include <llvm/Support/Casting.h>
33#include <llvm/Support/ErrorHandling.h>
34
35using namespace llvm;
36
37namespace re {
38
39template<typename T, typename... Args>
40std::unique_ptr<T> make_unique(Args&&... args) {
41    return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
42}
43
44RE * RE_Parser::parse(const std::string & regular_expression, ModeFlagSet initialFlags, RE_Syntax syntax) {
45    std::unique_ptr<RE_Parser> parser = nullptr;
46    switch (syntax) {
47        case RE_Syntax::PCRE:
48            parser = make_unique<RE_Parser_PCRE>(regular_expression);
49            break;
50        case RE_Syntax::ERE:
51            parser = make_unique<RE_Parser_ERE>(regular_expression);
52            break;
53        case RE_Syntax ::BRE:
54            parser = make_unique<RE_Parser_BRE>(regular_expression);
55            break;
56        case RE_Syntax ::PROSITE:
57            parser = make_unique<RE_Parser_PROSITE>(regular_expression);
58            break;
59        default:
60            //TODO handle FixString
61            ParseFailure("Unsupported RE syntax!");
62            break;
63    }
64    parser->fModeFlagSet = initialFlags;
65    parser->fNested = false;
66    parser->fGraphemeBoundaryPending = false;
67    parser->mCaptureGroupCount = 0;
68    RE * re = parser->parse_RE();
69    if (re == nullptr) {
70        ParseFailure("An unexpected parsing error occurred!");
71    }
72    return re;
73}
74
75RE_Parser::RE_Parser(const std::string & regular_expression)
76: fModeFlagSet(0)
77, fNested(false)
78, fGraphemeBoundaryPending(false)
79, fSupportNonCaptureGroup(false)
80, mCursor(regular_expression)
81, mCaptureGroupCount(0)
82, mReSyntax(RE_Syntax::PCRE)
83{
84
85}
86
87RE * makeAtomicGroup(RE * r) {
88    RE_Parser::ParseFailure("Atomic grouping not supported.");
89}
90
91RE * makeBranchResetGroup(RE * r) {
92    // Branch reset groups only affect submatch numbering, but
93    // this has no effect in icgrep.
94    return r;
95}
96
97RE * RE_Parser::parse_RE() {
98    return parse_alt();
99}
100
101RE * RE_Parser::parse_alt() {
102    return parse_alt_with_intersect(nullptr);
103}
104
105RE * RE_Parser::parse_alt_with_intersect(RE* reToBeIntersected) {
106    std::vector<RE *> alt;
107    for (;;) {
108        alt.push_back(parse_seq_with_intersect(reToBeIntersected));
109        if (*mCursor != '|') {
110            break;
111        }
112        ++mCursor; // advance past the alternation character '|'
113    }
114    if (alt.empty()) {
115        ParseFailure("No regular expression found!");
116    }
117    return makeAlt(alt.begin(), alt.end());
118}
119
120RE * RE_Parser::parse_seq() {
121    return parse_seq_with_intersect(nullptr);
122}
123
124RE * RE_Parser::parse_seq_with_intersect(RE* reToBeIntersected) {
125    std::vector<RE *> seq;
126    for (;;) {
127        RE * re = parse_next_item();
128        if (re == nullptr) {
129            if (fGraphemeBoundaryPending == true) {
130                seq.push_back(makeZeroWidth("GCB"));
131                fGraphemeBoundaryPending = false;
132            }
133            break;
134        }
135        if (reToBeIntersected) {
136            re = makeIntersect(reToBeIntersected, re);
137        }
138        re = extend_item(re);
139        seq.push_back(re);
140    }
141    return makeSeq(seq.begin(), seq.end());
142}
143
144RE * RE_Parser::parse_next_item() {
145    RE * re = nullptr;
146    if (mCursor.more()) {       
147        switch (*mCursor) {
148            case '(':
149                ++mCursor;
150                return parse_group();
151            case '^':
152                ++mCursor;
153                return makeStart();
154            case '$':
155                ++mCursor;
156                return makeEnd();
157            case '|': case ')':
158                break;
159            case '*': case '+': case '?': case '{':
160                ParseFailure("Need something to repeat before *, +, ? or {.");
161            case ']':
162                if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
163                    return createCC(parse_utf8_codepoint());
164                }
165                ParseFailure("Use  \\] for literal ].");
166            case '}':
167                if (fNested) {
168                    break;  //  a recursive invocation for a regexp in \N{...}
169                } else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
170                    return createCC(parse_utf8_codepoint());
171                }
172                ParseFailure("Use \\} for literal }.");
173            case '[':
174                mCursor++;
175                re = parse_charset();
176                if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
177                    re = makeSeq({re, makeZeroWidth("GCB")});
178                }
179                return re;
180            case '.': // the 'any' metacharacter
181                mCursor++;
182                return makeAny();
183            case '\\'// escape processing
184                ++mCursor;
185                return parse_escaped();
186            default:
187                re = createCC(parse_utf8_codepoint());
188                if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
189                    fGraphemeBoundaryPending = true;
190                }
191                return re;
192        }
193    }
194    return nullptr;
195}
196
197
198// Parse some kind of parenthesized group.  Input precondition: mCursor
199// after the (
200RE * RE_Parser::parse_group() {
201    const ModeFlagSet modeFlagSet = fModeFlagSet;
202    RE * group_expr = nullptr;
203    if (*mCursor == '?' && fSupportNonCaptureGroup) {
204        switch (*++mCursor) {
205            case '#'// comment
206                while (*++mCursor != ')');
207                ++mCursor;
208                return parse_next_item();
209            case ':':  // Non-capturing paren
210                ++mCursor;
211                group_expr = parse_alt();
212                break;
213            case '=':
214                ++mCursor;
215                group_expr = makeLookAheadAssertion(parse_alt());
216                break;
217            case '!':
218                ++mCursor;
219                group_expr = makeNegativeLookAheadAssertion(parse_alt());
220                break;
221            case '>':
222                ++mCursor;
223                group_expr = makeAtomicGroup(parse_alt());
224                break;
225            case '|':
226                ++mCursor;
227                group_expr = makeBranchResetGroup(parse_alt());
228                break;
229            case '<':
230                ++mCursor;
231                if (*mCursor == '=') {
232                    ++mCursor;
233                    group_expr = makeLookBehindAssertion(parse_alt());
234                }
235                else if (*mCursor == '!') {
236                    ++mCursor;
237                    group_expr = makeNegativeLookBehindAssertion(parse_alt());
238                } else {
239                    ParseFailure("Illegal lookbehind assertion syntax.");
240                }
241                break;
242            case '-': case 'd' : case 'i': case 'm': case 's': case 'x': case 'g':
243                while (*mCursor != ')' && *mCursor != ':') {
244                    bool negateMode = false;
245                    ModeFlagType modeBit;
246                    if (*mCursor == '-') {
247                        negateMode = true;
248                        ++mCursor;
249                    }
250                    switch (*mCursor) {
251                        case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
252                        case 'g': modeBit = GRAPHEME_CLUSTER_MODE; break;
253                        //case 'm': modeBit = MULTILINE_MODE_FLAG; break;
254                        //case 's': modeBit = DOTALL_MODE_FLAG; break;
255                        //case 'x': modeBit = IGNORE_SPACE_MODE_FLAG; break;
256                        //case 'd': modeBit = UNIX_LINES_MODE_FLAG; break;
257                        default: ParseFailure("Unsupported mode flag.");
258                    }
259                    ++mCursor;
260                    if (negateMode) {
261                        fModeFlagSet &= ~modeBit;
262                        negateMode = false;  // for next flag
263                    } else {
264                        fModeFlagSet |= modeBit;
265                    }
266                }
267                if (*mCursor == ':') {
268                    ++mCursor;
269                    group_expr = parse_alt();
270                    fModeFlagSet = modeFlagSet;
271                    break;
272                } else {  // if *_cursor == ')'
273                    ++mCursor;
274                    return parse_next_item();
275                }
276            case '\\': {
277                ++mCursor;
278                if (*mCursor == 'p' || *mCursor == 'P') {
279                    RE* reToBeIntersected = parseEscapedSet();
280                    if (*mCursor == ':') {
281                        ++mCursor;
282                        group_expr = parse_alt_with_intersect(reToBeIntersected);
283                        fModeFlagSet = modeFlagSet;
284                        break;
285                    } else {  // if *_cursor == ')'
286                        ++mCursor;
287                        return parse_next_item();
288                    }
289                }
290                break;
291            }
292            default:
293                ParseFailure("Illegal (? syntax.");
294        }
295    } else { // Capturing paren group.
296        RE * captured = parse_alt();
297        mCaptureGroupCount++;
298        std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
299        Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
300        auto key = std::make_pair("", captureName);
301        mNameMap.insert(std::make_pair(std::move(key), capture));
302        group_expr = capture;
303    }
304    if (*mCursor != ')') {
305        ParseFailure("Closing parenthesis required.");
306    }
307    ++mCursor;
308    return group_expr;
309}
310
311// TODO: Set ENABLE_EXTENDED_QUANTIFIERS false for ERE, BRE
312#define ENABLE_EXTENDED_QUANTIFIERS true
313   
314// Extend a RE item with one or more quantifiers
315RE * RE_Parser::extend_item(RE * re) {
316    if (LLVM_UNLIKELY(!(mCursor.more()))) return re;
317    int lb = 0, ub = 0;
318    switch (*mCursor) {
319        case '*':
320            lb = 0;
321            ub = Rep::UNBOUNDED_REP;
322            break;
323        case '?':
324            lb = 0;
325            ub = 1;
326            break;
327        case '+':
328            lb = 1;
329            ub = Rep::UNBOUNDED_REP;
330            break;
331        case '{':
332            std::tie(lb, ub) = parse_range_bound();
333            if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
334                ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
335            }
336            break;
337        default:
338            // No quantifiers
339            return re;
340    }
341    ++mCursor;
342    if (ENABLE_EXTENDED_QUANTIFIERS) {
343        if (LLVM_UNLIKELY(!(mCursor.more()))) return makeRep(re, lb, ub);;
344        if (*mCursor == '?') { // Non-greedy qualifier
345            // Greedy vs. non-greedy makes no difference for icgrep.
346            ++mCursor;
347            re = makeRep(re, lb, ub);
348        } else if (*mCursor == '+') {
349            ++mCursor;
350            if (ub == Rep::UNBOUNDED_REP) {
351                re = makeSeq({makeRep(re, lb, ub), makeNegativeLookAheadAssertion(re)});
352            } else if (lb == ub) {
353                re = makeRep(re, ub, ub);
354            } else /* if (lb < ub) */{
355                re = makeAlt({makeSeq({makeRep(re, lb, ub-1), makeNegativeLookAheadAssertion(re)}), makeRep(re, ub, ub)});
356            }
357        } else {
358            re = makeRep(re, lb, ub);
359        } 
360    } else {
361        re = makeRep(re, lb, ub);
362    }
363    // The quantified expression may be extended with a further quantifier, e,g., [a-z]{6,7}{2,3}
364    return extend_item(re);
365}
366
367std::pair<int, int> RE_Parser::parse_range_bound() {
368    int lower_bound = 0, upper_bound = 0;
369    if (*++mCursor != ',') {
370        lower_bound = parse_int();
371    }
372    if (*mCursor == '}') {
373        upper_bound = lower_bound;
374    } else if (*mCursor != ',') {
375        ParseFailure("Bad lower bound!");
376    } else if (*++mCursor == '}') {
377        upper_bound = Rep::UNBOUNDED_REP;
378    } else {
379        upper_bound = parse_int();
380        if (*mCursor != '}') {
381            ParseFailure("Bad upper bound!");
382        }
383    }
384    return std::make_pair(lower_bound, upper_bound);
385}
386
387unsigned RE_Parser::parse_int() {
388    unsigned value = 0;
389    while (isdigit(*mCursor)) {
390        value *= 10;
391        value += static_cast<int>(*mCursor++) - 48;
392    }
393    return value;
394}
395
396
397const uint64_t setEscapeCharacters = bit3C('b') | bit3C('p') | bit3C('q') | bit3C('d') | bit3C('w') | bit3C('s') | bit3C('<') | bit3C('>') |
398                                     bit3C('B') | bit3C('P') | bit3C('Q') | bit3C('D') | bit3C('W') | bit3C('S') | bit3C('N') | bit3C('X');
399
400bool RE_Parser::isSetEscapeChar(char c) {
401    return c >= 0x3C && c <= 0x7B && ((setEscapeCharacters >> (c - 0x3C)) & 1) == 1;
402}
403                                 
404
405RE * RE_Parser::parse_escaped() {
406   
407    if (isSetEscapeChar(*mCursor)) {
408        return parseEscapedSet();
409    }
410    else if (isdigit(*mCursor)) {
411        mCursor++;
412        std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
413        auto key = std::make_pair("", backref);
414        auto f = mNameMap.find(key);
415        if (f != mNameMap.end()) {
416            return makeReference(backref, f->second);
417        }
418        else {
419            ParseFailure("Back reference " + backref + " without prior capture group.");
420        }
421    }
422    else {
423        return createCC(parse_escaped_codepoint());
424    }
425}
426   
427RE * RE_Parser::parseEscapedSet() {
428    bool complemented = false;
429    RE * re = nullptr;
430    switch (*mCursor) {
431        case 'B': complemented = true;
432        case 'b':
433            if (*++mCursor != '{') {
434                return complemented ? makeWordNonBoundary() : makeWordBoundary();
435            } else {
436                ++mCursor;
437                if (isCharAhead('}')) {
438                    switch (*mCursor) {
439                        case 'g':
440                            re = complemented ? makeZeroWidth("NonGCB") : makeZeroWidth("GCB");
441                            ++mCursor;
442                            ++mCursor;
443                            break;
444                        case 'w': ParseFailure("\\b{w} not yet supported.");
445                        case 'l': ParseFailure("\\b{l} not yet supported.");
446                        case 's': ParseFailure("\\b{s} not yet supported.");
447//                        default: ParseFailure("Unrecognized boundary assertion");
448                    }
449                }
450                if (!re) {
451                    auto propExpr = parsePropertyExpression();
452                    if (*mCursor++ != '}') {
453                        ParseFailure("Malformed boundary assertion");
454                    }
455                    re = complemented ? makeReNonBoundary(propExpr) : makeReBoundary(propExpr);
456                }
457                return re;
458            }
459        case 'd':
460            ++mCursor;
461            return makeDigitSet();
462        case 'D':
463            ++mCursor;
464            return makeComplement(makeDigitSet());
465        case 's':
466            ++mCursor;
467            return makeWhitespaceSet();
468        case 'S':
469            ++mCursor;
470            return makeComplement(makeWhitespaceSet());
471        case 'w':
472            ++mCursor;
473            return makeWordSet();
474        case 'W':
475            ++mCursor;
476            return makeComplement(makeWordSet());
477        case 'Q':
478            complemented = true;
479        case 'q':
480            if (*++mCursor != '{') {
481                ParseFailure("Malformed grapheme-boundary property expression");
482            }
483            ++mCursor;
484            ParseFailure("Literal grapheme cluster expressions not yet supported.");
485            if (*mCursor != '}') {
486                ParseFailure("Malformed grapheme-boundary property expression");
487            }
488            ++mCursor;
489            return complemented ? makeComplement(re) : re;
490        case 'P':
491            complemented = true;
492        case 'p':
493            if (*++mCursor != '{') {
494                ParseFailure("Malformed property expression");
495            }
496            ++mCursor;
497            re = parsePropertyExpression();
498            if (*mCursor != '}') {
499                ParseFailure("Malformed property expression");
500            }
501            ++mCursor;
502            return complemented ? makeComplement(re) : re;
503        case 'X':
504            // \X is equivalent to ".+?\b{g}"; proceed the minimal number of characters (but at least one)
505            // to get to the next extended grapheme cluster boundary.
506            ++mCursor;
507            return makeSeq({makeAny(), makeRep(makeSeq({makeZeroWidth("NonGCB"), makeAny()}), 0, Rep::UNBOUNDED_REP), makeZeroWidth("GCB")});
508        case 'N':
509            if (*++mCursor != '{') {
510                ParseFailure("Malformed \\N expression");
511            }
512            ++mCursor;
513            re = parseNamePatternExpression();
514            if (*mCursor != '}') {
515                ParseFailure("Malformed \\N expression");
516            }
517            ++mCursor;
518            assert (re);
519            return re;
520        case '<':
521            ++mCursor;
522            return makeWordBegin();
523        case '>':
524            ++mCursor;
525            return makeWordEnd();
526        default:
527            ParseFailure("Internal error");
528    }
529}
530   
531void InvalidUTF8Encoding() {
532    RE_Parser::ParseFailure("Invalid UTF-8 encoding!");
533}
534
535codepoint_t RE_Parser::parse_utf8_codepoint() {
536    // Must cast to unsigned char to avoid sign extension.
537    unsigned char pfx = static_cast<unsigned char>(*mCursor++);
538    codepoint_t cp = pfx;
539    if (pfx < 0x80) return cp;
540    unsigned suffix_bytes = 0;
541    if (pfx < 0xE0) {
542        if (pfx < 0xC2) {  // bare suffix or illegal prefix 0xC0 or 0xC2
543            InvalidUTF8Encoding();
544        }
545        suffix_bytes = 1;
546        cp &= 0x1F;
547    } else if (pfx < 0xF0) { // [0xE0, 0xEF]
548        cp &= 0x0F;
549        suffix_bytes = 2;
550    } else { // [0xF0, 0xFF]
551        cp &= 0x0F;
552        suffix_bytes = 3;
553    }
554    while (suffix_bytes--) {
555        if (mCursor.noMore()) {
556            InvalidUTF8Encoding();
557        }
558        char_t sfx = *mCursor++;
559        if ((sfx & 0xC0) != 0x80) {
560            InvalidUTF8Encoding();
561        }
562        cp = (cp << 6) | (sfx & 0x3F);
563    }
564    // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
565    // or a 4-byte sequence is used to encode a codepoint < 0x10000.
566    if ((pfx == 0xE0 && cp < 0x800) || (pfx == 0xF0 && cp < 0x10000)) {
567        InvalidUTF8Encoding();
568    }
569    // It is an error if a 4-byte sequence is used to encode a codepoint
570    // above the Unicode maximum.
571    if (cp > UCD::UNICODE_MAX) {
572        InvalidUTF8Encoding();
573    }
574    return cp;
575}
576
577std::string RE_Parser::canonicalize(const cursor_t begin, const cursor_t end) {
578    std::locale loc;
579    std::stringstream s;   
580    for (auto i = begin; i != end; ++i) {
581        switch (*i) {
582            case '_': case ' ': case '-':
583                break;
584            default:
585                s << std::tolower(*i, loc);
586        }
587    }
588    return s.str();
589}
590
591bool RE_Parser::isCharAhead(char c) {
592    if (mCursor.remaining() < 2) {
593        return false;
594    }
595    auto nextCursor = mCursor.pos() + 1;
596    return *nextCursor == c;
597}
598
599RE * RE_Parser::parsePropertyExpression() {
600    const auto start = mCursor.pos();
601    while (mCursor.more()) {
602        bool done = false;
603        switch (*mCursor) {
604            case '}': case ':': case '=':
605                done = true;
606        }
607        if (done) {
608            break;
609        }
610        ++mCursor;
611    }
612    if (*mCursor == '=') {
613        // We have a property-name = value expression
614        const auto prop_end = mCursor.pos();
615        mCursor++;
616        auto val_start = mCursor.pos();
617        if (*val_start != '/') {
618            // property-value is normal string
619            while (mCursor.more()) {
620                bool done = false;
621                switch (*mCursor) {
622                    case '}': case ':':
623                        done = true;
624                }
625                if (done) {
626                    break;
627                }
628                ++mCursor;
629            }
630            return createName(canonicalize(start, prop_end), canonicalize(val_start, mCursor.pos()));
631        } else {
632            // property-value is another regex
633            auto previous = val_start;
634            auto current = (++mCursor).pos();
635            val_start = current;
636
637            while (true) {
638                if (*current == '/' && *previous != '\\') {
639                    break;
640                }
641
642                if (!mCursor.more()) {
643                    ParseFailure("Malformed property expression");
644                }
645
646                previous = current;
647                current = (++mCursor).pos();
648            }
649            ++mCursor;
650            return parseRegexPropertyValue(canonicalize(start, prop_end), canonicalize(val_start, current));
651        }
652    }
653    return createName(canonicalize(start, mCursor.pos()));
654}
655
656RE * RE_Parser::parseRegexPropertyValue(const std::string & propName, const std::string& regexValue) {
657    RE * propValueRe = RE_Parser::parse("^" + regexValue + "$", fModeFlagSet, mReSyntax);
658    const auto matches = grep::grepPropertyValues(propName, propValueRe);
659    if (matches.empty()) {
660        ParseFailure("regex " + regexValue + " match no property values");
661    } else if (matches.size() == 1) {
662        return createName(propName, matches.front());
663    } else {
664        std::vector<re::RE *> alt;
665        for (auto value : matches) {
666            alt.push_back(createName(propName, value));
667        }
668        return makeAlt(alt.begin(), alt.end());
669    }
670}
671
672Name * RE_Parser::parseNamePatternExpression(){
673
674    ModeFlagSet outerFlags = fModeFlagSet;
675    fModeFlagSet = 1;
676
677    bool outerNested = fNested;
678    fNested = true;
679
680    RE * nameRE = parse_RE();
681
682    // Reset outer parsing state.
683    fModeFlagSet = outerFlags;
684    fNested = outerNested;
685
686    // Embed the nameRE in ";.*$nameRE" to skip the codepoint field of Uname.txt
687    RE * embedded = makeSeq({mMemoizer.memoize(makeCC(0x3B)), makeRep(makeAny(), 0, Rep::UNBOUNDED_REP), nameRE});
688   
689    CC * codepoints = grep::grepCodepoints(embedded, getUnicodeNameDataPtr(), getUnicodeNameDataSize());
690   
691    if (codepoints) {
692        Name * const result = mMemoizer.memoize(codepoints);
693        assert (*cast<CC>(result->getDefinition()) == *codepoints);
694        return result;
695    }
696    return nullptr;
697}
698
699bool RE_Parser::isUnsupportChartsetOperator(char c) {
700    return false;
701}
702
703CharsetOperatorKind RE_Parser::getCharsetOperator() {
704    if (isUnsupportChartsetOperator(*mCursor)) {
705        return emptyOperator;
706    }
707    switch (*mCursor) {
708        case '&':
709            ++mCursor;
710            if (*mCursor == '&') {
711                ++mCursor;
712                return intersectOp;
713            } else if (*mCursor == '[') {
714                // Short-hand for intersectOp when a set follows
715                return intersectOp;
716            }
717            return ampChar;
718        case '-':
719            ++mCursor;
720            if (*mCursor == '-') {
721                ++mCursor;
722                return setDiffOp;
723            } else if (*mCursor == '[') {
724                return setDiffOp;
725            } else if (*mCursor == ']') {
726                return hyphenChar;
727            }
728            return rangeHyphen;
729        case '[':
730            ++mCursor;
731            if (*mCursor == ':') {
732                ++mCursor;
733                return posixPropertyOpener;
734            }
735            return setOpener;
736        case ']':
737            ++mCursor;
738            return setCloser;
739        case '\\':
740            ++mCursor;
741            return backSlash;
742        default:
743            return emptyOperator;
744    }
745}
746
747// Precondition: cursor is immediately after opening '[' character
748RE * RE_Parser::parse_charset() {
749    // Sets are accumulated using two variables:
750    // subexprs accumulates set expressions such as \p{Lu}, [\w && \p{Greek}]
751    // cc accumulates the literal and calculated codepoints and ranges
752    std::vector<RE *> subexprs;
753    CC * cc = makeCC();
754    // When the last item deal with is a single literal charcacter or calculated codepoint,
755    // a following hyphen can indicate a range.   When the last item is a set subexpression,
756    // a following hyphen can indicate set subtraction.
757    enum {NoItem, CodepointItem, RangeItem, SetItem, BrackettedSetItem} lastItemKind = NoItem;
758
759    codepoint_t lastCodepointItem = 0;
760    bool havePendingOperation = false;
761    CharsetOperatorKind pendingOperationKind = intersectOp;
762    RE * pendingOperand = nullptr;
763
764    // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
765    bool negated = false;
766    if (*mCursor == '^') {
767        negated = true;
768        ++mCursor;
769    }
770    // Legacy rule: an unescaped ] may appear as a literal set character
771    // if and only if it appears immediately after the opening [ or [^
772    if ( *mCursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
773        insert(cc, ']');
774        lastItemKind = CodepointItem;
775        lastCodepointItem = static_cast<codepoint_t> (']');
776        ++mCursor;
777    } else if ( *mCursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
778        ++mCursor;
779        insert(cc, '-');
780        lastItemKind = CodepointItem;
781        lastCodepointItem = static_cast<codepoint_t> ('-');
782        if (*mCursor == '-') {
783            ParseFailure("Set operator has no left operand.");
784        }
785    }
786    while (mCursor.more()) {
787        const CharsetOperatorKind op = getCharsetOperator();
788        switch (op) {
789            case intersectOp:
790            case setDiffOp: {
791                if (lastItemKind == NoItem) {
792                    ParseFailure("Set operator has no left operand.");
793                }
794                if (!cc->empty()) {
795                    subexprs.push_back(mMemoizer.memoize(cc));
796                }
797                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
798                subexprs.clear();
799                cc = makeCC();
800                if (havePendingOperation) {
801                    if (pendingOperationKind == intersectOp) {
802                        pendingOperand = makeIntersect(pendingOperand, newOperand);
803                    }
804                    else {
805                        pendingOperand = makeDiff(pendingOperand, newOperand);
806                    }
807                }
808                else {
809                    pendingOperand = newOperand;
810                }
811                havePendingOperation = true;
812                pendingOperationKind = op;
813                lastItemKind = NoItem;
814            }
815            break;
816            case setCloser: {
817                if (lastItemKind == NoItem) {
818                    ParseFailure("Set operator has no right operand.");
819                }
820                if (!cc->empty()) {
821                    subexprs.push_back(mMemoizer.memoize(cc));
822                }
823                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
824                if (havePendingOperation) {
825                    if (pendingOperationKind == intersectOp) {
826                        newOperand = makeIntersect(pendingOperand, newOperand);
827                    }
828                    else {
829                        newOperand = makeDiff(pendingOperand, newOperand);
830                    }
831                }
832                if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
833                    if (CC * cc1 = dyn_cast<CC>(newOperand)) {
834                        newOperand = caseInsensitize(cc1);
835                    }
836                }
837                return negated ? makeComplement(newOperand) : newOperand;
838            }
839            case setOpener:
840            case posixPropertyOpener: {
841                if (lastItemKind != NoItem) {
842                    if (!cc->empty()) {
843                        subexprs.push_back(mMemoizer.memoize(cc));
844                    }
845                    RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
846                    subexprs.clear();
847                    cc = makeCC();
848                    if (havePendingOperation) {
849                        if (pendingOperationKind == intersectOp) {
850                            pendingOperand = makeIntersect(pendingOperand, newOperand);
851                        } else {
852                            pendingOperand = makeDiff(pendingOperand, newOperand);
853                        }
854                    }
855                    else {
856                        pendingOperand = newOperand;
857                    }
858                    subexprs.push_back(pendingOperand);
859                    havePendingOperation = false;
860                }
861                if (op == setOpener) {
862                    subexprs.push_back(parse_charset());
863                    lastItemKind = SetItem;
864                }
865                else if (op == posixPropertyOpener) {
866                    bool negated = false;
867                    if (*mCursor == '^') {
868                        negated = true;
869                        mCursor++;
870                    }
871                    RE * posixSet = parsePropertyExpression();
872                    subexprs.push_back(negated ? makeComplement(posixSet) : posixSet);
873                    lastItemKind = BrackettedSetItem;
874                    if (*mCursor++ != ':' || *mCursor++ != ']')
875                        ParseFailure("Posix set expression improperly terminated.");
876                }
877            }
878            break;
879            case rangeHyphen:
880                if (lastItemKind != CodepointItem) {
881                    ParseFailure("Range operator - has illegal left operand.");
882                }
883                insert_range(cc, lastCodepointItem, parse_codepoint());
884                lastItemKind = RangeItem;
885                break;
886            case hyphenChar:
887                insert(cc, '-');
888                lastItemKind = CodepointItem;
889                lastCodepointItem = static_cast<codepoint_t> ('-');
890                break;
891            case ampChar:
892                insert(cc, '&');
893                lastItemKind = CodepointItem;
894                lastCodepointItem = static_cast<codepoint_t> ('&');
895                break;
896            case backSlash:
897                if (isSetEscapeChar(*mCursor)) {
898                    subexprs.push_back(parseEscapedSet());
899                    lastItemKind = SetItem;
900                }
901                else {
902                    lastCodepointItem = parse_escaped_codepoint();
903                    insert(cc, lastCodepointItem);
904                    lastItemKind = CodepointItem;
905                }
906                break;
907            case emptyOperator:
908                lastCodepointItem = parse_utf8_codepoint();
909                insert(cc, lastCodepointItem);
910                lastItemKind = CodepointItem;
911                break;
912        }
913    }
914    ParseFailure("Set expression not properly terminated.");
915}
916
917
918codepoint_t RE_Parser::parse_codepoint() {
919    if (*mCursor == '\\') {
920        mCursor++;
921        return parse_escaped_codepoint();
922    } else {
923        return parse_utf8_codepoint();
924    }
925}
926
927// A backslash escape was found, and various special cases (back reference,
928// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
929// cluster \X have been ruled out.
930// It may be one of several possibilities or an error sequence.
931// 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
932// 2. General control codes c[@-_a-z?]
933// 3. Restricted octal notation 0 - 0777
934// 4. General octal notation o\{[0-7]+\}
935// 5. General hex notation x\{[0-9A-Fa-f]+\}
936// 6. An error for any unrecognized alphabetic escape
937// 7. An escaped ASCII symbol, standing for itself
938
939codepoint_t RE_Parser::parse_escaped_codepoint() {
940    codepoint_t cp_value;
941    switch (*mCursor) {
942        case 'a': ++mCursor; return 0x07; // BEL
943        case 'e': ++mCursor; return 0x1B; // ESC
944        case 'f': ++mCursor; return 0x0C; // FF
945        case 'n': ++mCursor; return 0x0A; // LF
946        case 'r': ++mCursor; return 0x0D; // CR
947        case 't': ++mCursor; return 0x09; // HT
948        case 'v': ++mCursor; return 0x0B; // VT
949        case 'c': // Control-escape based on next char
950            ++mCursor;
951            // \c@, \cA, ... \c_, or \ca, ..., \cz
952            if (((*mCursor >= '@') && (*mCursor <= '_')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))) {
953                cp_value = static_cast<codepoint_t>(*mCursor & 0x1F);
954                mCursor++;
955                return cp_value;
956            }
957            else if (*mCursor++ == '?') return 0x7F;  // \c? ==> DEL
958            else ParseFailure("Illegal \\c escape sequence");
959        case '0': // Octal escape:  0 - 0377
960            ++mCursor;
961            return parse_octal_codepoint(0,3);
962        case 'o':
963            ++mCursor;
964            if (*mCursor == '{') {
965                ++mCursor;
966                cp_value = parse_octal_codepoint(1, 7);
967                if (*mCursor++ != '}') ParseFailure("Malformed octal escape sequence");
968                return cp_value;
969            }
970            else {
971                ParseFailure("Malformed octal escape sequence");
972            }
973        case 'x':
974            ++mCursor;
975            if (*mCursor == '{') {
976              ++mCursor;
977              cp_value = parse_hex_codepoint(1, 6);
978              if (*mCursor++ != '}') ParseFailure("Malformed hex escape sequence");
979              return cp_value;
980            }
981            else {
982                return parse_hex_codepoint(1,2);  // ICU compatibility
983            }
984        case 'u':
985            ++mCursor;
986            if (*mCursor == '{') {
987                ++mCursor;
988                cp_value = parse_hex_codepoint(1, 6);
989                if (*mCursor++ != '}') ParseFailure("Malformed hex escape sequence");
990                return cp_value;
991            }
992            else {
993                return parse_hex_codepoint(4,4);  // ICU compatibility
994            }
995        case 'U':
996            ++mCursor;
997            return parse_hex_codepoint(8,8);  // ICU compatibility
998        default:
999            // Escaped letters should be reserved for special functions.
1000            if (((*mCursor >= 'A') && (*mCursor <= 'Z')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))){
1001                //Escape unknow letter will be parse as normal letter
1002                return parse_utf8_codepoint();
1003                //ParseFailure("Undefined or unsupported escape sequence");
1004            }
1005            else if ((*mCursor < 0x20) || (*mCursor >= 0x7F))
1006                ParseFailure("Illegal escape sequence");
1007            else return static_cast<codepoint_t>(*mCursor++);
1008    }
1009}
1010
1011codepoint_t RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
1012    codepoint_t value = 0;
1013    int count = 0;
1014    while (mCursor.more() && count < maxdigits) {
1015        const char t = *mCursor;
1016        if (t < '0' || t > '7') {
1017            break;
1018        }
1019        value = value * 8 | (t - '0');
1020        ++mCursor;
1021        ++count;
1022    }
1023    if (count < mindigits) ParseFailure("Octal sequence has too few digits");
1024    if (value > UCD::UNICODE_MAX) ParseFailure("Octal value too large");
1025    return value;
1026}
1027
1028codepoint_t RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
1029    codepoint_t value = 0;
1030    int count = 0;
1031    while (mCursor.more() && isxdigit(*mCursor) && count < maxdigits) {
1032        const char t = *mCursor;
1033        if (isdigit(t)) {
1034            value = (value * 16) | (t - '0');
1035        }
1036        else {
1037            value = ((value * 16) | ((t | 32) - 'a')) + 10;
1038        }
1039        ++mCursor;
1040        ++count;
1041    }
1042    if (count < mindigits) ParseFailure("Hexadecimal sequence has too few digits");
1043    if (value > UCD::UNICODE_MAX) ParseFailure("Hexadecimal value too large");
1044    return value;
1045}
1046
1047Name * RE_Parser::createCC(const codepoint_t cp) {
1048    CC * cc = nullptr;
1049    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
1050        cc = makeCC();
1051        caseInsensitiveInsert(cc, cp);
1052    } else {
1053        cc = makeCC(cp);
1054    }
1055    return mMemoizer.memoize(cc);
1056}
1057
1058void RE_Parser::insert(CC * cc, const codepoint_t cp) {
1059    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
1060        caseInsensitiveInsert(cc, cp);
1061    } else {
1062        cc->insert(cp);
1063    }
1064}
1065
1066void RE_Parser::insert_range(CC * cc, const codepoint_t lo, const codepoint_t hi) {
1067    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
1068        caseInsensitiveInsertRange(cc, lo, hi);
1069    } else {
1070        cc->insert_range(lo, hi);
1071    }
1072}
1073
1074RE * RE_Parser::makeComplement(RE * s) {
1075  return makeDiff(makeAny(), s);
1076}
1077
1078           
1079
1080                           
1081RE * RE_Parser::makeWordBoundary() {
1082    Name * wordC = makeWordSet();
1083    return makeReBoundary(wordC);
1084}
1085
1086RE * RE_Parser::makeWordNonBoundary() {
1087    Name * wordC = makeWordSet();
1088    return makeReNonBoundary(wordC);
1089}
1090
1091inline RE * RE_Parser::makeReBoundary(RE * re) {
1092    return makeBoundaryAssertion(re);
1093}
1094inline RE * RE_Parser::makeReNonBoundary(RE * re) {
1095    return makeNegativeBoundaryAssertion(re);
1096}
1097
1098RE * RE_Parser::makeWordBegin() {
1099    Name * wordC = makeWordSet();
1100    return makeNegativeLookBehindAssertion(wordC);
1101}
1102
1103RE * RE_Parser::makeWordEnd() {
1104    Name * wordC = makeWordSet();
1105    return makeNegativeLookAheadAssertion(wordC);
1106}
1107
1108Name * RE_Parser::makeDigitSet() {
1109    return mMemoizer.memoize(createName("nd"));
1110}
1111
1112Name * RE_Parser::makeAlphaNumeric() {
1113    return mMemoizer.memoize(createName("alnum"));
1114}
1115
1116Name * RE_Parser::makeWhitespaceSet() {
1117    return mMemoizer.memoize(createName("whitespace"));
1118}
1119
1120Name * RE_Parser::makeWordSet() {
1121    return mMemoizer.memoize(createName("word"));
1122}
1123
1124Name * RE_Parser::createName(std::string value) {
1125    auto key = std::make_pair("", value);
1126    auto f = mNameMap.find(key);
1127    if (f != mNameMap.end()) {
1128        return f->second;
1129    }
1130    Name * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
1131    mNameMap.insert(std::make_pair(std::move(key), property));
1132    return property;
1133    }
1134
1135Name * RE_Parser::createName(std::string prop, std::string value) {
1136    auto key = std::make_pair(prop, value);
1137    auto f = mNameMap.find(key);
1138    if (f != mNameMap.end()) {
1139        return f->second;
1140    }
1141    Name * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
1142    mNameMap.insert(std::make_pair(std::move(key), property));
1143    return property;
1144}
1145
1146LLVM_ATTRIBUTE_NORETURN void RE_Parser::ParseFailure(std::string errmsg) {
1147    llvm::report_fatal_error(errmsg);
1148}
1149
1150}
Note: See TracBrowser for help on using the repository browser.