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

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

AST support for Lookahead/Lookbehind? assertions

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