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

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

Moved responsibility of handling 'special cases of Unicode TR #18' and 'compatibility properties of UTR #18 Annex C' into RE_Parser.

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