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

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

Embedded UnicodeSet? into CC objects (will currently cause memory leak)

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