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

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

Override LLVM error_handler for return code 2; convert ParseFailure? to LLVM fatal error.

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