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

Last change on this file since 4983 was 4947, checked in by cameron, 4 years ago

Restructuring step

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