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

Last change on this file since 4402 was 4402, checked in by cameron, 5 years ago

Parsing support for word boundary assertions \b, \B

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