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

Last change on this file since 5537 was 5537, checked in by cameron, 23 months ago

Enable ?m and ?x mode flags

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