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

Last change on this file since 4622 was 4622, checked in by nmedfort, 4 years ago

Preliminary changes to inclusion of UCD Compiler into the RE Compiler.

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