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

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

Word Begin/End? changes from Fahad.

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