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

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

-enable-byte-mode initial check-in

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