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

Last change on this file since 5182 was 5182, checked in by cameron, 3 years ago

Remove inline declarations for subclassing

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