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

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

Reverted unintended modification of RE parser

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