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

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