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

Last change on this file since 5241 was 5241, checked in by nmedfort, 3 years ago

Potential fix for '\p{script=/.*hir.*/}'

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