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

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

Moved resolveProperty responsibilities out of RE_Parser but kept expansion of Name objects with definitions in it.

File size: 31.3 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/resolve_properties.h>
19#include <UCD/CaseFolding_txt.h>
20#include <sstream>
21#include <algorithm>
22
23
24// It would probably be best to enforce that {}, [], () must always
25// be balanced.   But legacy syntax allows } and ] to occur as literals
26// in certain contexts (no opening { or [, or immediately after [ or [^ ).
27// Perhaps this define should become a parameter.
28#define LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED true
29#define LEGACY_UNESCAPED_HYPHEN_ALLOWED true
30
31
32namespace re {
33
34RE * RE_Parser::parse(const std::string & regular_expression, ModeFlagSet initialFlags) {
35    RE_Parser parser(regular_expression);
36    parser.fModeFlagSet = initialFlags;
37    RE * re = parser.parse_RE();
38    if (re == nullptr) {
39        throw ParseFailure("An unexpected parsing error occurred!");
40    }
41    return re;
42}
43
44inline RE_Parser::RE_Parser(const std::string & regular_expression)
45    : _cursor(regular_expression.begin())
46    , _end(regular_expression.end())
47    , fModeFlagSet(0)
48    {
49       
50    }
51   
52RE * makeLookAheadAssertion(RE * r) {
53    return makeAssertion(r, Assertion::Kind::Lookahead, Assertion::Sense::Positive);
54}
55
56RE * makeNegativeLookAheadAssertion(RE * r) {
57    return makeAssertion(r, Assertion::Kind::Lookahead, Assertion::Sense::Negative);
58}
59
60RE * makeLookBehindAssertion(RE * r) {
61    return makeAssertion(r, Assertion::Kind::Lookbehind, Assertion::Sense::Positive);
62}
63
64RE * makeNegativeLookBehindAssertion(RE * r) {
65    return makeAssertion(r, Assertion::Kind::Lookbehind, Assertion::Sense::Negative);
66}
67
68RE * makeAtomicGroup(RE * r) {
69    throw ParseFailure("Atomic grouping not supported.");
70}
71
72RE * makeBranchResetGroup(RE * r) {
73    // Branch reset groups only affect submatch numbering, but
74    // this has no effect in icgrep.
75    return r;
76}
77   
78RE * RE_Parser::parse_RE() {
79    RE * r = parse_alt();
80    if (_cursor != _end) { 
81        throw ParseFailure("Unrecognized junk remaining at end of regexp");
82    }
83    return r;
84}
85
86RE * RE_Parser::parse_alt() {
87    std::vector<RE *> alt;
88    for (;;) {
89        alt.push_back(parse_seq());
90        if (_cursor == _end || *_cursor != '|') {
91            break;
92        }
93        ++_cursor; // advance past the alternation character '|'
94    }
95    if (alt.empty())
96    {
97        throw NoRegularExpressionFound();
98    }
99    return makeAlt(alt.begin(), alt.end());
100}
101
102inline RE * RE_Parser::parse_seq() {
103    std::vector<RE *> seq;
104    for (;;) {
105        RE * re = parse_next_item();
106        if (re == nullptr) {
107            break;
108        }
109        seq.push_back(extend_item(re));
110    }
111    //  Note: empty sequences are legal.
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("Unsupported 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    if (lower_bound > MAX_REPETITION_LOWER_BOUND || upper_bound > MAX_REPETITION_UPPER_BOUND) {
289        throw ParseFailure("Bounded repetition exceeds icgrep implementation limit");
290    }
291    if ((upper_bound != Rep::UNBOUNDED_REP) && (lower_bound > upper_bound)) {
292        throw ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
293    }
294    ++_cursor;
295    if (*_cursor == '?') {
296        // Non-greedy qualifier
297        ++_cursor;
298        //return makeNonGreedyRep(re, lower_bound, upper_bound);
299        // Greedy vs. non-greedy makes no difference for icgrep.
300        return makeRep(re, lower_bound, upper_bound);
301    }
302    else if (*_cursor == '+') {
303        // Possessive qualifier
304        ++_cursor;
305        //return makePossessiveRep(re, lower_bound, upper_bound);
306        throw ParseFailure("Possessive repetition is not supported in icgrep 1.0");
307    }
308    else {
309        // Normal repetition operator.
310        return makeRep(re, lower_bound, upper_bound);
311    }
312}
313
314inline void RE_Parser::parse_range_bound(int & lower_bound, int & upper_bound) {
315    ++_cursor;
316    throw_incomplete_expression_error_if_end_of_stream();
317    if (*_cursor == ',') {
318        ++_cursor;
319        lower_bound = 0;
320    }
321    else {
322        lower_bound = parse_int();
323    }
324    throw_incomplete_expression_error_if_end_of_stream();
325    if (*_cursor == '}') {
326        upper_bound = lower_bound;
327    }
328    else if (*_cursor != ',') {
329        throw BadLowerBound();
330    }
331    else { // [^,}]
332        ++_cursor;
333        throw_incomplete_expression_error_if_end_of_stream();
334        if (*_cursor == '}') {
335            upper_bound = Rep::UNBOUNDED_REP;
336        }
337        else {
338            upper_bound = parse_int();
339            if (*_cursor != '}') {
340                throw BadUpperBound();
341            }
342        }
343    }
344}
345
346unsigned RE_Parser::parse_int() {
347    unsigned value = 0;
348    for (; _cursor != _end; ++_cursor) {
349        if (!isdigit(*_cursor)) {
350            break;
351        }
352        value *= 10;
353        value += static_cast<int>(*_cursor) - 48;
354    }
355    return value;
356}
357
358
359#define bit40(x) (1ULL << ((x) - 0x40))
360const uint64_t setEscapeCharacters = bit40('b') | bit40('p') | bit40('d') | bit40('w') | bit40('s') | 
361                                     bit40('B') | bit40('P') | bit40('D') | bit40('W') | bit40('S');
362
363inline bool isSetEscapeChar(char c) {
364    return c >= 0x40 && c <= 0x7F && ((setEscapeCharacters >> (c - 0x40)) & 1) == 1;
365}
366
367inline RE * RE_Parser::parse_escaped() {
368    throw_incomplete_expression_error_if_end_of_stream();
369    if (isSetEscapeChar(*_cursor)) 
370      return parseEscapedSet();
371    else 
372      return build_CC(parse_escaped_codepoint());
373}
374
375RE * RE_Parser::parseEscapedSet() {
376    bool complemented = false;
377    RE * s;
378    switch (*_cursor) {
379        case 'b':
380            ++_cursor;
381            return makeWordBoundary();
382        case 'B':
383            ++_cursor;
384            return makeWordNonBoundary();
385        case 'd':
386            ++_cursor;
387            return makeDigitSet();
388        case 'D':
389            ++_cursor;
390            return makeComplement(makeDigitSet());
391        case 's':
392            ++_cursor;
393            return makeWhitespaceSet();
394        case 'S':
395            ++_cursor;
396            return makeComplement(makeWhitespaceSet());
397        case 'w':
398            ++_cursor;
399            return makeWordSet();
400        case 'W':
401            ++_cursor;
402            return makeComplement(makeWordSet());
403        case 'P':
404            complemented = true;
405        case 'p':
406            ++_cursor;
407            if (_cursor == _end || *_cursor != '{') throw ParseFailure("Malformed property expression");
408            ++_cursor;
409            s = parsePropertyExpression();
410            if (_cursor == _end || *_cursor != '}') throw ParseFailure("Malformed property expression");
411            ++_cursor;
412            return complemented ? makeComplement(s) : s;
413        default:
414            throw ParseFailure("Internal error");
415    }
416}
417
418codepoint_t RE_Parser::parse_utf8_codepoint() {
419    // Must cast to unsigned char to avoid sign extension.
420    unsigned char pfx = static_cast<unsigned char>(*_cursor++);
421    codepoint_t cp = pfx;
422    if (pfx < 0x80) return cp;
423    unsigned suffix_bytes;
424    if (pfx < 0xE0) {
425        if (pfx < 0xC2) {  // bare suffix or illegal prefix 0xC0 or 0xC2
426            throw InvalidUTF8Encoding();
427        }
428        suffix_bytes = 1;
429        cp &= 0x1F;
430    }
431    else if (pfx < 0xF0) { // [0xE0, 0xEF]
432        cp &= 0x0F;
433        suffix_bytes = 2;
434    }
435    else { // [0xF0, 0xFF]
436        cp &= 0x0F;
437        suffix_bytes = 3;
438    }
439    while (suffix_bytes--) {
440        if (_cursor == _end) {
441            throw InvalidUTF8Encoding();
442        }
443        unsigned char sfx = static_cast<unsigned char>(*_cursor++);
444        if ((sfx & 0xC0) != 0x80) {
445            throw InvalidUTF8Encoding();
446        }
447        cp = (cp << 6) | (sfx & 0x3F);
448    }
449    // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
450    // or a 4-byte sequence is used to encode a codepoint < 0x10000.
451    if ((pfx == 0xE0 && cp < 0x800) || (pfx == 0xF0 && cp < 0x10000)) {
452        throw InvalidUTF8Encoding();
453    }
454    // It is an error if a 4-byte sequence is used to encode a codepoint
455    // above the Unicode maximum.   
456    if (cp > CC::UNICODE_MAX) {
457        throw InvalidUTF8Encoding();
458    }
459    return cp;
460}
461
462std::string RE_Parser::canonicalize(const cursor_t begin, const cursor_t end) {
463    std::locale loc;
464    std::stringstream s;
465    for (auto i = begin; i != end; ++i) {
466        switch (*i) {
467            case '_': case ' ': case '-':
468                break;
469            default:
470                s << std::tolower(*i, loc);
471        }
472    }
473    return s.str();
474}
475
476Name * RE_Parser::parsePropertyExpression() {
477    const cursor_t start = _cursor;
478    while (_cursor != _end && *_cursor != '}' and *_cursor != ':' and *_cursor != '=') {
479        _cursor++;
480    }
481    if (_cursor != _end && *_cursor == '=') {
482        const cursor_t prop_end = _cursor;
483        _cursor++;
484        const cursor_t val_start = _cursor;
485        while (_cursor != _end && *_cursor != '}' and *_cursor != ':') {
486            _cursor++;
487        }
488        // We have a property-name = value expression
489        return createName(canonicalize(start, prop_end), canonicalize(val_start, _cursor));
490    }
491    return createName(canonicalize(start, _cursor));
492}
493
494Name * RE_Parser::createName(const std::string value) {
495
496    auto key = std::make_pair("", value);
497    auto f = mNameMap.find(key);
498    if (f != mNameMap.end()) {
499        return f->second;
500    }
501
502    Name * property = UCD::resolveProperty(value, this);
503
504    mNameMap.insert(std::make_pair(std::move(key), property));
505
506    return property;
507}
508
509Name * RE_Parser::createName(const std::string prop, const std::string value) {
510
511    auto key = std::make_pair(prop, value);
512
513    auto f = mNameMap.find(key);
514    if (f != mNameMap.end()) {
515        return f->second;
516    }
517
518    Name * property = UCD::resolveProperty(prop, value, this);
519
520    mNameMap.insert(std::make_pair(std::move(key), property));
521
522    return property;
523}
524
525CharsetOperatorKind RE_Parser::getCharsetOperator() {
526    throw_incomplete_expression_error_if_end_of_stream();
527    switch (*_cursor) {
528        case '&':
529            ++_cursor;
530            if (_cursor != _end && *_cursor == '&') {
531                ++_cursor;
532                return intersectOp;
533            }
534            else if (_cursor != _end && *_cursor == '[') {
535                // Short-hand for intersectOp when a set follows
536                return intersectOp;
537            }
538            else return ampChar;
539        case '-':
540            ++_cursor;
541            if (_cursor != _end && *_cursor == '-') {
542                ++_cursor;
543                return setDiffOp;
544            }
545            else if (_cursor != _end && *_cursor == '[') {
546                return setDiffOp;
547            }
548            else if (_cursor != _end && *_cursor == ']') {
549                return hyphenChar;
550            }
551            else return rangeHyphen;
552        case '[':
553            ++_cursor;
554            if (_cursor != _end && *_cursor == ':') {
555                ++_cursor;
556                return posixPropertyOpener;
557            }
558            else return setOpener;
559        case ']':
560            ++_cursor;
561            return setCloser;
562        case '\\':
563            ++_cursor;
564            return backSlash;
565        default:
566            return emptyOperator;
567    }
568}           
569   
570// Precondition: cursor is immediately after opening '[' character
571RE * RE_Parser::parse_charset() {
572    // Sets are accumulated using two variables:
573    // subexprs accumulates set expressions such as \p{Lu}, [\w && \p{Greek}]
574    // cc accumulates the literal and calculated codepoints and ranges
575    std::vector<RE *> subexprs;
576    CC * cc = makeCC();
577    // When the last item deal with is a single literal charcacter or calculated codepoint,
578    // a following hyphen can indicate a range.   When the last item is a set subexpression,
579    // a following hyphen can indicate set subtraction.
580    enum {NoItem, CodepointItem, RangeItem, SetItem, BrackettedSetItem} lastItemKind = NoItem;
581    codepoint_t lastCodepointItem;
582   
583    bool havePendingOperation = false;
584    CharsetOperatorKind pendingOperationKind;
585    RE * pendingOperand;
586   
587    // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
588    bool negated = false;
589    if (_cursor != _end && *_cursor == '^') {
590        negated = true;
591        ++_cursor;
592    }
593    throw_incomplete_expression_error_if_end_of_stream();
594    // Legacy rule: an unescaped ] may appear as a literal set character
595    // if and only if it appears immediately after the opening [ or [^
596    if ( *_cursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
597        cc->insert(']');
598        lastItemKind = CodepointItem;
599        lastCodepointItem = static_cast<codepoint_t> (']');
600        ++_cursor;
601    }
602    else if ( *_cursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
603        ++_cursor;
604        cc->insert('-');
605        lastItemKind = CodepointItem;
606        lastCodepointItem = static_cast<codepoint_t> ('-');
607        if (*_cursor == '-') {
608            throw ParseFailure("Set operator has no left operand.");
609        }
610    }
611    while (_cursor != _end) {
612        const CharsetOperatorKind op = getCharsetOperator();
613        switch (op) {
614            case intersectOp:
615            case setDiffOp: {
616                if (lastItemKind == NoItem) {
617                    throw ParseFailure("Set operator has no left operand.");
618                }
619                if (cc->begin() != cc->end()) {
620                    subexprs.push_back(cc);
621                }
622                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
623                subexprs.clear();
624                cc = makeCC();
625                if (havePendingOperation) {
626                    if (pendingOperationKind == intersectOp) {
627                        pendingOperand = makeIntersect(pendingOperand, newOperand);
628                    }
629                    else {
630                        pendingOperand = makeDiff(pendingOperand, newOperand);
631                    }
632                }
633                else {
634                    pendingOperand = newOperand;
635                }
636                havePendingOperation = true;
637                pendingOperationKind = op;
638                lastItemKind = NoItem;
639            }
640            break;
641            case setCloser: {
642                if (lastItemKind == NoItem) {
643                    throw ParseFailure("Set operator has no right operand.");
644                }
645                if (cc->begin() != cc->end()) {
646                    subexprs.push_back(cc);
647                }
648                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
649                if (havePendingOperation) {
650                    if (pendingOperationKind == intersectOp) {
651                        newOperand = makeIntersect(pendingOperand, newOperand);
652                    }
653                    else {
654                        newOperand = makeDiff(pendingOperand, newOperand);
655                    }
656                }
657                if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
658                    if (CC * cc1 = dyn_cast<CC>(newOperand)) {
659                        newOperand = caseInsensitize(cc1);
660                    }
661                }
662                return negated ? makeComplement(newOperand) : newOperand;
663            }
664            case setOpener:
665            case posixPropertyOpener: {
666                if (lastItemKind != NoItem) {
667                    if (cc->begin() != cc->end()) subexprs.push_back(cc);
668                    RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
669                    subexprs.clear();
670                    cc = makeCC();
671                    if (havePendingOperation) {
672                        if (pendingOperationKind == intersectOp) {
673                            pendingOperand = makeIntersect(pendingOperand, newOperand);
674                        }
675                        else {
676                            pendingOperand = makeDiff(pendingOperand, newOperand);
677                        }
678                    }
679                    else {
680                        pendingOperand = newOperand;
681                    }
682                    subexprs.push_back(pendingOperand);
683                    havePendingOperation = false;
684                }
685                if (op == setOpener) {
686                    subexprs.push_back(parse_charset());
687                    lastItemKind = SetItem;
688                }
689                else if (op == posixPropertyOpener) {
690                    bool negated = false;
691                    if (*_cursor == '^') {
692                        negated = true;
693                        _cursor++;
694                    }
695                    RE * posixSet = parsePropertyExpression();
696                    if (negated) posixSet = makeComplement(posixSet);
697                    subexprs.push_back(posixSet);
698                    lastItemKind = BrackettedSetItem;
699                    if (_cursor == _end || *_cursor++ != ':' || _cursor == _end || *_cursor++ != ']')
700                        throw ParseFailure("Posix set expression improperly terminated.");
701                }
702            }
703            break;
704            case rangeHyphen:
705                if (lastItemKind != CodepointItem) {
706                    throw ParseFailure("Range operator - has illegal left operand.");
707                }
708                cc->insert_range(lastCodepointItem, parse_codepoint());
709                lastItemKind = RangeItem;
710                break;
711            case hyphenChar:
712                cc->insert('-'); 
713                lastItemKind = CodepointItem;
714                lastCodepointItem = static_cast<codepoint_t> ('-');
715                break;
716            case ampChar:
717                cc->insert('&'); 
718                lastItemKind = CodepointItem;
719                lastCodepointItem = static_cast<codepoint_t> ('&');
720                break;
721            case backSlash:
722                throw_incomplete_expression_error_if_end_of_stream();
723                if (isSetEscapeChar(*_cursor)) {
724                    subexprs.push_back(parseEscapedSet());
725                    lastItemKind = SetItem;
726                }
727                else {
728                    lastCodepointItem = parse_escaped_codepoint();
729                    cc->insert(lastCodepointItem);
730                    lastItemKind = CodepointItem;
731                }
732                break;
733            case emptyOperator:
734                lastCodepointItem = parse_utf8_codepoint();
735                cc->insert(lastCodepointItem);
736                lastItemKind = CodepointItem;
737                break;
738        }
739    }
740    throw ParseFailure("Set expression not properly terminated.");
741}
742
743
744codepoint_t RE_Parser::parse_codepoint() {
745    if (_cursor != _end && *_cursor == '\\') {
746        _cursor++;
747        return parse_escaped_codepoint();
748    }
749    else {
750        return parse_utf8_codepoint();
751    }
752}
753
754// A backslash escape was found, and various special cases (back reference,
755// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
756// cluster \X have been ruled out.
757// It may be one of several possibilities or an error sequence.
758// 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
759// 2. General control codes c[@-_a-z?]
760// 3. Restricted octal notation 0 - 0777
761// 4. General octal notation o\{[0-7]+\}
762// 5. General hex notation x\{[0-9A-Fa-f]+\}
763// 6. An error for any unrecognized alphabetic escape
764// 7. An escaped ASCII symbol, standing for itself
765
766codepoint_t RE_Parser::parse_escaped_codepoint() {
767    codepoint_t cp_value;
768    throw_incomplete_expression_error_if_end_of_stream();
769    switch (*_cursor) {
770        case 'a': ++_cursor; return 0x07; // BEL
771        case 'e': ++_cursor; return 0x1B; // ESC
772        case 'f': ++_cursor; return 0x0C; // FF
773        case 'n': ++_cursor; return 0x0A; // LF
774        case 'r': ++_cursor; return 0x0D; // CR
775        case 't': ++_cursor; return 0x09; // HT
776        case 'v': ++_cursor; return 0x0B; // VT
777        case 'c': // Control-escape based on next char
778            ++_cursor;
779            throw_incomplete_expression_error_if_end_of_stream();
780            // \c@, \cA, ... \c_, or \ca, ..., \cz
781            if (((*_cursor >= '@') && (*_cursor <= '_')) || ((*_cursor >= 'a') && (*_cursor <= 'z'))) {
782                cp_value = static_cast<codepoint_t>(*_cursor & 0x1F);
783                _cursor++;
784                return cp_value;
785            }
786            else if (*_cursor++ == '?') return 0x7F;  // \c? ==> DEL
787            else throw("Illegal \\c escape sequence");
788        case '0': // Octal escape:  0 - 0377
789            ++_cursor;
790            return parse_octal_codepoint(0,3);
791        case 'o':
792            ++_cursor;
793            throw_incomplete_expression_error_if_end_of_stream();
794            if (*_cursor == '{') {
795                ++_cursor;
796                cp_value = parse_octal_codepoint(1, 7);
797                if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed octal escape sequence");
798                return cp_value;
799            }
800            else {
801                throw ParseFailure("Malformed octal escape sequence");
802            }
803        case 'x':
804            ++_cursor;
805            throw_incomplete_expression_error_if_end_of_stream();
806            if (*_cursor == '{') {
807              ++_cursor;
808              cp_value = parse_hex_codepoint(1, 6);
809              if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
810              return cp_value;
811            }
812            else {
813                return parse_hex_codepoint(1,2);  // ICU compatibility
814            }
815        case 'u':
816            ++_cursor;
817            throw_incomplete_expression_error_if_end_of_stream();
818            if (*_cursor == '{') {
819                ++_cursor;
820                cp_value = parse_hex_codepoint(1, 6);
821                if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
822                return cp_value;
823            }
824            else {
825                return parse_hex_codepoint(4,4);  // ICU compatibility
826            }
827        case 'U':
828            ++_cursor;
829            return parse_hex_codepoint(8,8);  // ICU compatibility
830        case 'N':
831            ++_cursor;
832            throw ParseFailure("\\N{...} character name syntax not yet supported.");
833
834        default:
835            // Escaped letters should be reserved for special functions.
836            if (((*_cursor >= 'A') && (*_cursor <= 'Z')) || ((*_cursor >= 'a') && (*_cursor <= 'z')))
837                throw ParseFailure("Undefined or unsupported escape sequence");
838            else if ((*_cursor < 0x20) || (*_cursor >= 0x7F))
839                throw ParseFailure("Illegal escape sequence");
840            else return static_cast<codepoint_t>(*_cursor++);
841    }
842}
843
844
845codepoint_t RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
846    codepoint_t value = 0;
847    int count = 0;
848    while (_cursor != _end && count < maxdigits) {
849        const char t = *_cursor;
850        if (t < '0' || t > '7') {
851            break;
852        }
853        value = value * 8 | (t - '0');
854        ++_cursor;
855        ++count;
856    }
857    if (count < mindigits) throw ParseFailure("Octal sequence has too few digits");
858    if (value > CC::UNICODE_MAX) throw ParseFailure("Octal value too large");
859    return value;
860}
861
862codepoint_t RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
863    codepoint_t value = 0;
864    int count = 0;
865    while (_cursor != _end && isxdigit(*_cursor) && count < maxdigits) {
866        const char t = *_cursor;
867        if (isdigit(t)) {
868            value = (value * 16) | (t - '0');
869        }
870        else {   
871            value = (value * 16) | ((t | 32) - 'a') + 10;
872        }
873        ++_cursor;
874        ++count;
875    }
876    if (count < mindigits) throw ParseFailure("Hexadecimal sequence has too few digits");
877    if (value > CC::UNICODE_MAX) throw ParseFailure("Hexadecimal value too large");
878    return value;
879}
880
881
882inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
883    if (_cursor == _end) throw IncompleteRegularExpression();
884}
885
886CC * RE_Parser::build_CC(codepoint_t cp) {
887    CC * cc = makeCC();
888    CC_add_codepoint(cc, cp);
889    return cc;
890}
891
892void RE_Parser::CC_add_codepoint(CC * cc, codepoint_t cp) {
893    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
894        caseInsensitiveInsert(cc, cp);
895    }
896    else cc->insert(cp);
897}
898
899void RE_Parser::CC_add_range(CC * cc, codepoint_t lo, codepoint_t hi) {
900    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
901        caseInsensitiveInsertRange(cc, lo, hi);
902    }
903    else cc->insert_range(lo, hi);
904}
905   
906RE * RE_Parser::makeComplement(RE * s) {
907  return makeDiff(makeAny(), s);
908}
909
910RE * RE_Parser::makeWordBoundary () {
911    RE * wordC = makeWordSet();
912    return makeAlt({makeSeq({makeNegativeLookBehindAssertion(wordC), makeLookAheadAssertion(wordC)}),
913                    makeSeq({makeLookBehindAssertion(wordC), makeNegativeLookAheadAssertion(wordC)})});
914}
915
916RE * RE_Parser::makeWordNonBoundary () {
917    RE * wordC = makeWordSet();
918    return makeAlt({makeSeq({makeNegativeLookBehindAssertion(wordC), makeNegativeLookAheadAssertion(wordC)}),
919                    makeSeq({makeLookBehindAssertion(wordC), makeLookAheadAssertion(wordC)})});
920}
921
922inline Name * RE_Parser::makeDigitSet() {
923    return createName("nd");
924}
925
926inline Name * RE_Parser::makeAlphaNumeric() {
927    return createName("alnum");
928}
929
930inline Name * RE_Parser::makeWhitespaceSet() {
931    return createName("whitespace");
932}
933
934inline Name * RE_Parser::makeWordSet() {
935    return createName("word");
936}
937
938}
Note: See TracBrowser for help on using the repository browser.