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

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

Work on character name patterns

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