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

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

Move responsibility for acquire/release of logical segment number into pipeline compilers.

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