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

Last change on this file was 5737, checked in by cameron, 7 days ago

Remove experimental property-class mode expressions

File size: 38.8 KB
Line 
1/*
2 *  Copyright (c) 2016 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_parser_helper.h>
9#include <re/re_parser_pcre.h>
10#include <re/re_parser_ere.h>
11#include <re/re_parser_bre.h>
12#include <re/re_parser_prosite.h>
13#include <re/re_name.h>
14#include <re/re_alt.h>
15#include <re/re_any.h>
16#include <re/re_end.h>
17#include <re/re_rep.h>
18#include <re/re_seq.h>
19#include <re/re_start.h>
20#include <re/re_diff.h>
21#include <re/re_intersect.h>
22#include <re/re_assertion.h>
23#include <re/printer_re.h>
24#include <UCD/resolve_properties.h>
25#include <UCD/CaseFolding.h>
26#include <sstream>
27#include <string>
28#include <algorithm>
29#include <iostream>
30#include <llvm/Support/Casting.h>
31#include <llvm/Support/ErrorHandling.h>
32#include <llvm/Support/raw_ostream.h>
33#include <llvm/ADT/STLExtras.h> // for make_unique
34
35using namespace llvm;
36
37namespace re {
38
39
40RE * RE_Parser::parse(const std::string & regular_expression, ModeFlagSet initialFlags, RE_Syntax syntax, bool ByteMode) {
41
42    std::unique_ptr<RE_Parser> parser = nullptr;
43    switch (syntax) {
44        case RE_Syntax::PCRE:
45            parser = make_unique<RE_Parser_PCRE>(regular_expression);
46            break;
47        case RE_Syntax::ERE:
48            parser = make_unique<RE_Parser_ERE>(regular_expression);
49            break;
50        case RE_Syntax ::BRE:
51            parser = make_unique<RE_Parser_BRE>(regular_expression);
52            break;
53        case RE_Syntax ::PROSITE:
54            parser = make_unique<RE_Parser_PROSITE>(regular_expression);
55            break;
56        default:
57            //TODO handle FixString
58            ParseFailure("Unsupported RE syntax!");
59            break;
60    }
61    parser->fByteMode = ByteMode;
62    parser->fModeFlagSet = initialFlags;
63    parser->fNested = false;
64    parser->fGraphemeBoundaryPending = false;
65    parser->mCaptureGroupCount = 0;
66    RE * re = parser->parse_RE();
67    if (re == nullptr) {
68        ParseFailure("An unexpected parsing error occurred!");
69    }
70    return re;
71}
72
73RE_Parser::RE_Parser(const std::string & regular_expression)
74: fByteMode(false)
75, fModeFlagSet(0)
76, fNested(false)
77, fGraphemeBoundaryPending(false)
78, fSupportNonCaptureGroup(false)
79, mCursor(regular_expression)
80, mCaptureGroupCount(0)
81, mReSyntax(RE_Syntax::PCRE)
82{
83
84}
85
86RE * makeAtomicGroup(RE * r) {
87    RE_Parser::ParseFailure("Atomic grouping not supported.");
88}
89
90RE * makeBranchResetGroup(RE * r) {
91    // Branch reset groups only affect submatch numbering, but
92    // this has no effect in icgrep.
93    return r;
94}
95
96RE * RE_Parser::parse_RE() {
97    return parse_alt();
98}
99
100RE * RE_Parser::parse_alt() {
101    std::vector<RE *> alt;
102    for (;;) {
103        alt.push_back(parse_seq());
104        if (*mCursor != '|') {
105            break;
106        }
107        ++mCursor; // advance past the alternation character '|'
108    }
109    if (alt.empty()) {
110        ParseFailure("No regular expression found!");
111    }
112    return makeAlt(alt.begin(), alt.end());
113}
114
115RE * RE_Parser::parse_seq() {
116    std::vector<RE *> seq;
117    if (!mCursor.more() || (*mCursor == '|') || (*mCursor == ')')) return makeSeq();
118    for (;;) {
119        RE * re = parse_next_item();
120        if (re == nullptr) {
121            if (fGraphemeBoundaryPending == true) {
122                seq.push_back(makeZeroWidth("GCB"));
123                fGraphemeBoundaryPending = false;
124            }
125            break;
126        }
127        re = extend_item(re);
128        seq.push_back(re);
129    }
130    return makeSeq(seq.begin(), seq.end());
131}
132
133RE * RE_Parser::parse_next_item() {
134    RE * re = nullptr;
135    if (fModeFlagSet & IGNORE_SPACE_MODE_FLAG) {
136        while (mCursor.more() && *mCursor == ' ') {
137            ++mCursor;
138        }
139    }
140    if (mCursor.more()) {
141        switch (*mCursor) {
142            case '(':
143                ++mCursor;
144                return parse_group();
145            case '^':
146                ++mCursor;
147                if ((fModeFlagSet & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
148                    return makeNegativeLookBehindAssertion(makeByte(makeCC(makeCC(0, '\n'-1), makeCC('\n'+1, 0xFF))));
149                }
150                return makeStart();
151            case '$':
152                ++mCursor;
153                if ((fModeFlagSet & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
154                    return makeLookAheadAssertion(makeCC('\n'));
155                }
156                return makeEnd();
157            case '|': case ')':
158                break;
159            case '*': case '+': case '?': case '{':
160                ParseFailure("Need something to repeat before *, +, ? or {.");
161            case ']':
162                if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
163                    return createCC(parse_literal_codepoint());
164                }
165                ParseFailure("Use  \\] for literal ].");
166            case '}':
167                if (fNested) {
168                    break;  //  a recursive invocation for a regexp in \N{...}
169                } else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
170                    return createCC(parse_literal_codepoint());
171                }
172                ParseFailure("Use \\} for literal }.");
173            case '[':
174                mCursor++;
175                re = parse_charset();
176                if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
177                    re = makeSeq({re, makeZeroWidth("GCB")});
178                }
179                break;
180            case '.': // the 'any' metacharacter
181                mCursor++;
182                return makeAny();
183            case '\\'// escape processing
184                ++mCursor;
185                return parse_escaped();
186            default:
187                re = createCC(parse_literal_codepoint());
188                if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
189                    fGraphemeBoundaryPending = true;
190                }
191        }
192    }
193    return re;
194}
195
196
197// Parse some kind of parenthesized group.  Input precondition: mCursor
198// after the (
199RE * RE_Parser::parse_group() {
200    const ModeFlagSet modeFlagSet = fModeFlagSet;
201    RE * group_expr = nullptr;
202    if (*mCursor == '?' && fSupportNonCaptureGroup) {
203        switch (*++mCursor) {
204            case '#'// comment
205                while (*++mCursor != ')');
206                ++mCursor;
207                return parse_next_item();
208            case ':':  // Non-capturing paren
209                ++mCursor;
210                group_expr = parse_alt();
211                break;
212            case '=':
213                ++mCursor;
214                group_expr = makeLookAheadAssertion(parse_alt());
215                break;
216            case '!':
217                ++mCursor;
218                group_expr = makeNegativeLookAheadAssertion(parse_alt());
219                break;
220            case '>':
221                ++mCursor;
222                group_expr = makeAtomicGroup(parse_alt());
223                break;
224            case '|':
225                ++mCursor;
226                group_expr = makeBranchResetGroup(parse_alt());
227                break;
228            case '<':
229                ++mCursor;
230                if (*mCursor == '=') {
231                    ++mCursor;
232                    group_expr = makeLookBehindAssertion(parse_alt());
233                }
234                else if (*mCursor == '!') {
235                    ++mCursor;
236                    group_expr = makeNegativeLookBehindAssertion(parse_alt());
237                } else {
238                    ParseFailure("Illegal lookbehind assertion syntax.");
239                }
240                break;
241            case '-': case 'd' : case 'i': case 'm': case 's': case 'x': case 'g':
242                while (*mCursor != ')' && *mCursor != ':') {
243                    bool negateMode = false;
244                    ModeFlagType modeBit;
245                    if (*mCursor == '-') {
246                        negateMode = true;
247                        ++mCursor;
248                    }
249                    switch (*mCursor) {
250                        case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
251                        case 'g': modeBit = GRAPHEME_CLUSTER_MODE; break;
252                        case 'm': modeBit = MULTILINE_MODE_FLAG; break;
253                        //case 's': modeBit = DOTALL_MODE_FLAG; break;
254                        case 'x': modeBit = IGNORE_SPACE_MODE_FLAG; break;
255                        case 'd': modeBit = UNIX_LINES_MODE_FLAG; break;
256                        default: ParseFailure("Unsupported mode flag.");
257                    }
258                    ++mCursor;
259                    if (negateMode) {
260                        fModeFlagSet &= ~modeBit;
261                        negateMode = false;  // for next flag
262                    } else {
263                        fModeFlagSet |= modeBit;
264                    }
265                }
266                if (*mCursor == ':') {
267                    ++mCursor;
268                    group_expr = parse_alt();
269                    fModeFlagSet = modeFlagSet;
270                    break;
271                } else {  // if *_cursor == ')'
272                    ++mCursor;
273                    return parse_next_item();
274                }
275            default:
276                ParseFailure("Illegal (? syntax.");
277        }
278    } else { // Capturing paren group.
279        RE * captured = parse_alt();
280        mCaptureGroupCount++;
281        std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
282        Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
283        auto key = std::make_pair("", captureName);
284        mNameMap.insert(std::make_pair(std::move(key), capture));
285        group_expr = capture;
286    }
287    if (*mCursor != ')') {
288        ParseFailure("Closing parenthesis required.");
289    }
290    ++mCursor;
291    return group_expr;
292}
293
294// TODO: Set ENABLE_EXTENDED_QUANTIFIERS false for ERE, BRE
295#define ENABLE_EXTENDED_QUANTIFIERS true
296   
297// Extend a RE item with one or more quantifiers
298RE * RE_Parser::extend_item(RE * re) {
299    if (LLVM_UNLIKELY(!(mCursor.more()))) return re;
300    int lb = 0, ub = 0;
301    switch (*mCursor) {
302        case '*':
303            lb = 0;
304            ub = Rep::UNBOUNDED_REP;
305            break;
306        case '?':
307            lb = 0;
308            ub = 1;
309            break;
310        case '+':
311            lb = 1;
312            ub = Rep::UNBOUNDED_REP;
313            break;
314        case '{':
315            std::tie(lb, ub) = parse_range_bound();
316            if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
317                ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
318            }
319            break;
320        default:
321            // No quantifiers
322            return re;
323    }
324    ++mCursor;
325    if (ENABLE_EXTENDED_QUANTIFIERS) {
326        if (LLVM_UNLIKELY(!(mCursor.more()))) return makeRep(re, lb, ub);;
327        if (*mCursor == '?') { // Non-greedy qualifier
328            // Greedy vs. non-greedy makes no difference for icgrep.
329            ++mCursor;
330            re = makeRep(re, lb, ub);
331        } else if (*mCursor == '+') {
332            ++mCursor;
333            if (ub == Rep::UNBOUNDED_REP) {
334                re = makeSeq({makeRep(re, lb, ub), makeNegativeLookAheadAssertion(re)});
335            } else if (lb == ub) {
336                re = makeRep(re, ub, ub);
337            } else /* if (lb < ub) */{
338                re = makeAlt({makeSeq({makeRep(re, lb, ub-1), makeNegativeLookAheadAssertion(re)}), makeRep(re, ub, ub)});
339            }
340        } else {
341            re = makeRep(re, lb, ub);
342        } 
343    } else {
344        re = makeRep(re, lb, ub);
345    }
346    // The quantified expression may be extended with a further quantifier, e,g., [a-z]{6,7}{2,3}
347    return extend_item(re);
348}
349
350std::pair<int, int> RE_Parser::parse_range_bound() {
351    int lower_bound = 0, upper_bound = 0;
352    if (*++mCursor != ',') {
353        lower_bound = parse_int();
354    }
355    if (*mCursor == '}') {
356        upper_bound = lower_bound;
357    } else if (*mCursor != ',') {
358        ParseFailure("Bad lower bound!");
359    } else if (*++mCursor == '}') {
360        upper_bound = Rep::UNBOUNDED_REP;
361    } else {
362        upper_bound = parse_int();
363        if (*mCursor != '}') {
364            ParseFailure("Bad upper bound!");
365        }
366    }
367    return std::make_pair(lower_bound, upper_bound);
368}
369
370unsigned RE_Parser::parse_int() {
371    unsigned value = 0;
372    while (isdigit(*mCursor)) {
373        value *= 10;
374        value += static_cast<int>(*mCursor++) - 48;
375    }
376    return value;
377}
378
379
380const uint64_t setEscapeCharacters = bit3C('b') | bit3C('p') | bit3C('q') | bit3C('d') | bit3C('w') | bit3C('s') | bit3C('<') | bit3C('>') |
381                                     bit3C('B') | bit3C('P') | bit3C('Q') | bit3C('D') | bit3C('W') | bit3C('S') | bit3C('N') | bit3C('X');
382
383bool RE_Parser::isSetEscapeChar(char c) {
384    return c >= 0x3C && c <= 0x7B && ((setEscapeCharacters >> (c - 0x3C)) & 1) == 1;
385}
386                                 
387
388RE * RE_Parser::parse_escaped() {
389   
390    if (isSetEscapeChar(*mCursor)) {
391        return parseEscapedSet();
392    }
393    else if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) {
394        codepoint_t cp = parse_escaped_codepoint();
395        if ((cp >= 0x80) && (cp <= 0xFF)) {
396            return makeByte(makeCC(cp));
397        }
398        else return createCC(cp);
399    }
400    else if (isdigit(*mCursor)) {
401        mCursor++;
402        std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
403        auto key = std::make_pair("", backref);
404        auto f = mNameMap.find(key);
405        if (f != mNameMap.end()) {
406            return makeReference(backref, f->second);
407        }
408        else {
409            ParseFailure("Back reference " + backref + " without prior capture group.");
410        }
411    }
412    else {
413        return createCC(parse_escaped_codepoint());
414    }
415}
416   
417RE * RE_Parser::parseEscapedSet() {
418    bool complemented = false;
419    RE * re = nullptr;
420    switch (*mCursor) {
421        case 'B': complemented = true;
422        case 'b':
423            if (*++mCursor != '{') {
424                return complemented ? makeWordNonBoundary() : makeWordBoundary();
425            } else {
426                ++mCursor;
427                if (isCharAhead('}')) {
428                    switch (*mCursor) {
429                        case 'g':
430                            re = complemented ? makeZeroWidth("NonGCB") : makeZeroWidth("GCB");
431                            ++mCursor;
432                            ++mCursor;
433                            break;
434                        case 'w': ParseFailure("\\b{w} not yet supported.");
435                        case 'l': ParseFailure("\\b{l} not yet supported.");
436                        case 's': ParseFailure("\\b{s} not yet supported.");
437//                        default: ParseFailure("Unrecognized boundary assertion");
438                    }
439                }
440                if (!re) {
441                    auto propExpr = parsePropertyExpression();
442                    if (*mCursor++ != '}') {
443                        ParseFailure("Malformed boundary assertion");
444                    }
445                    re = complemented ? makeReNonBoundary(propExpr) : makeReBoundary(propExpr);
446                }
447                return re;
448            }
449        case 'd':
450            ++mCursor;
451            return makeDigitSet();
452        case 'D':
453            ++mCursor;
454            return makeComplement(makeDigitSet());
455        case 's':
456            ++mCursor;
457            return makeWhitespaceSet();
458        case 'S':
459            ++mCursor;
460            return makeComplement(makeWhitespaceSet());
461        case 'w':
462            ++mCursor;
463            return makeWordSet();
464        case 'W':
465            ++mCursor;
466            return makeComplement(makeWordSet());
467        case 'Q':
468            complemented = true;
469        case 'q':
470            if (*++mCursor != '{') {
471                ParseFailure("Malformed grapheme-boundary property expression");
472            }
473            ++mCursor;
474            ParseFailure("Literal grapheme cluster expressions not yet supported.");
475            if (*mCursor != '}') {
476                ParseFailure("Malformed grapheme-boundary property expression");
477            }
478            ++mCursor;
479            return complemented ? makeComplement(re) : re;
480        case 'P':
481            complemented = true;
482        case 'p':
483            if (*++mCursor != '{') {
484                ParseFailure("Malformed property expression");
485            }
486            ++mCursor;
487            re = parsePropertyExpression();
488            if (*mCursor != '}') {
489                ParseFailure("Malformed property expression");
490            }
491            ++mCursor;
492            return complemented ? makeComplement(re) : re;
493        case 'X':
494            // \X is equivalent to ".+?\b{g}"; proceed the minimal number of characters (but at least one)
495            // to get to the next extended grapheme cluster boundary.
496            ++mCursor;
497            return makeSeq({makeAny(), makeRep(makeSeq({makeZeroWidth("NonGCB"), makeAny()}), 0, Rep::UNBOUNDED_REP), makeZeroWidth("GCB")});
498        case 'N':
499            if (*++mCursor != '{') {
500                ParseFailure("Malformed \\N expression");
501            }
502            ++mCursor;
503            re = parseNamePatternExpression();
504            if (*mCursor != '}') {
505                ParseFailure("Malformed \\N expression");
506            }
507            ++mCursor;
508            assert (re);
509            return re;
510        case '<':
511            ++mCursor;
512            return makeWordBegin();
513        case '>':
514            ++mCursor;
515            return makeWordEnd();
516        default:
517            ParseFailure("Internal error");
518    }
519}
520   
521void InvalidUTF8Encoding() {
522    RE_Parser::ParseFailure("Invalid UTF-8 encoding!");
523}
524
525codepoint_t RE_Parser::parse_literal_codepoint() {
526    if (fByteMode) {
527       return static_cast<uint8_t>(*mCursor++);
528    }
529    else return parse_utf8_codepoint();
530}
531
532codepoint_t RE_Parser::parse_utf8_codepoint() {
533    // Must cast to unsigned char to avoid sign extension.
534    unsigned char pfx = static_cast<unsigned char>(*mCursor++);
535    codepoint_t cp = pfx;
536    if (pfx < 0x80) return cp;
537    unsigned suffix_bytes = 0;
538    if (pfx < 0xE0) {
539        if (pfx < 0xC2) {  // bare suffix or illegal prefix 0xC0 or 0xC2
540            InvalidUTF8Encoding();
541        }
542        suffix_bytes = 1;
543        cp &= 0x1F;
544    } else if (pfx < 0xF0) { // [0xE0, 0xEF]
545        cp &= 0x0F;
546        suffix_bytes = 2;
547    } else { // [0xF0, 0xFF]
548        cp &= 0x0F;
549        suffix_bytes = 3;
550    }
551    while (suffix_bytes--) {
552        if (mCursor.noMore()) {
553            InvalidUTF8Encoding();
554        }
555        char_t sfx = *mCursor++;
556        if ((sfx & 0xC0) != 0x80) {
557            InvalidUTF8Encoding();
558        }
559        cp = (cp << 6) | (sfx & 0x3F);
560    }
561    // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
562    // or a 4-byte sequence is used to encode a codepoint < 0x10000.
563    if ((pfx == 0xE0 && cp < 0x800) || (pfx == 0xF0 && cp < 0x10000)) {
564        InvalidUTF8Encoding();
565    }
566    // It is an error if a 4-byte sequence is used to encode a codepoint
567    // above the Unicode maximum.
568    if (cp > UCD::UNICODE_MAX) {
569        InvalidUTF8Encoding();
570    }
571    return cp;
572}
573
574std::string RE_Parser::canonicalize(const cursor_t begin, const cursor_t end) {
575    std::locale loc;
576    std::stringstream s;   
577    for (auto i = begin; i != end; ++i) {
578        switch (*i) {
579            case '_': case ' ': case '-':
580                break;
581            default:
582                s << std::tolower(*i, loc);
583        }
584    }
585    return s.str();
586}
587
588bool RE_Parser::isCharAhead(char c) {
589    if (mCursor.remaining() < 2) {
590        return false;
591    }
592    auto nextCursor = mCursor.pos() + 1;
593    return *nextCursor == c;
594}
595
596RE * RE_Parser::parsePropertyExpression() {
597    const auto start = mCursor.pos();
598    while (mCursor.more()) {
599        bool done = false;
600        switch (*mCursor) {
601            case '}': case ':': case '=':
602                done = true;
603        }
604        if (done) {
605            break;
606        }
607        ++mCursor;
608    }
609    if (*mCursor == '=') {
610        // We have a property-name = value expression
611        const auto prop_end = mCursor.pos();
612        mCursor++;
613        auto val_start = mCursor.pos();
614        if (*val_start == '/') {
615            // property-value is another regex
616            auto previous = val_start;
617            auto current = (++mCursor).pos();
618            val_start = current;
619           
620            while (true) {
621                if (*current == '/' && *previous != '\\') {
622                    break;
623                }
624               
625                if (!mCursor.more()) {
626                    ParseFailure("Malformed property expression");
627                }
628               
629                previous = current;
630                current = (++mCursor).pos();
631            }
632            ++mCursor;
633            //return parseRegexPropertyValue(canonicalize(start, prop_end), std::string(val_start, current));
634            return createName(canonicalize(start, prop_end), std::string(val_start-1, current));
635        }
636        if (*val_start == '@') {
637            // property-value is @property@ or @identity@
638            auto previous = val_start;
639            auto current = (++mCursor).pos();
640            val_start = current;
641           
642            while (true) {
643                if (*current == '@' && *previous != '\\') {
644                    break;
645                }
646               
647                if (!mCursor.more()) {
648                    ParseFailure("Malformed property expression");
649                }
650               
651                previous = current;
652                current = (++mCursor).pos();
653            }
654            ++mCursor;
655            //return parseRegexPropertyValue(canonicalize(start, prop_end), std::string(val_start, current));
656            return createName(canonicalize(start, prop_end), std::string(val_start-1, current));
657        }
658        else {
659            // property-value is normal string
660            while (mCursor.more()) {
661                bool done = false;
662                switch (*mCursor) {
663                    case '}': case ':':
664                        done = true;
665                }
666                if (done) {
667                    break;
668                }
669                ++mCursor;
670            }
671            return createName(canonicalize(start, prop_end), std::string(val_start, mCursor.pos()));
672        }
673    }
674    return createName(canonicalize(start, mCursor.pos()));
675}
676
677Name * RE_Parser::parseNamePatternExpression(){
678
679    const auto start = mCursor.pos();
680    while (mCursor.more()) {
681        if (*mCursor == '\\') {
682            ++mCursor;
683            if (!mCursor.more()) {
684                break;
685            }
686        }
687        else if (*mCursor == '}') {
688            break;
689        }
690        ++mCursor;
691    }
692    std::string nameRegexp = "/(?i)" + std::string(start, mCursor.pos());
693    return createName("na", nameRegexp);
694}
695
696bool RE_Parser::isUnsupportChartsetOperator(char c) {
697    return false;
698}
699
700CharsetOperatorKind RE_Parser::getCharsetOperator() {
701    if (isUnsupportChartsetOperator(*mCursor)) {
702        return emptyOperator;
703    }
704    switch (*mCursor) {
705        case '&':
706            ++mCursor;
707            if (*mCursor == '&') {
708                ++mCursor;
709                return intersectOp;
710            } else if (*mCursor == '[') {
711                // Short-hand for intersectOp when a set follows
712                return intersectOp;
713            }
714            return ampChar;
715        case '-':
716            ++mCursor;
717            if (*mCursor == '-') {
718                ++mCursor;
719                return setDiffOp;
720            } else if (*mCursor == '[') {
721                return setDiffOp;
722            } else if (*mCursor == ']') {
723                return hyphenChar;
724            }
725            return rangeHyphen;
726        case '[':
727            ++mCursor;
728            if (*mCursor == ':') {
729                ++mCursor;
730                return posixPropertyOpener;
731            }
732            return setOpener;
733        case ']':
734            ++mCursor;
735            return setCloser;
736        case '\\':
737            ++mCursor;
738            return backSlash;
739        default:
740            return emptyOperator;
741    }
742}
743
744// Precondition: cursor is immediately after opening '[' character
745RE * RE_Parser::parse_charset() {
746    // Sets are accumulated using two variables:
747    // subexprs accumulates set expressions such as \p{Lu}, [\w && \p{Greek}]
748    // cc accumulates the literal and calculated codepoints and ranges
749    std::vector<RE *> subexprs;
750    CC * cc = makeCC();
751    // When the last item deal with is a single literal charcacter or calculated codepoint,
752    // a following hyphen can indicate a range.   When the last item is a set subexpression,
753    // a following hyphen can indicate set subtraction.
754    enum {NoItem, CodepointItem, RangeItem, SetItem, BrackettedSetItem} lastItemKind = NoItem;
755
756    codepoint_t lastCodepointItem = 0;
757    bool havePendingOperation = false;
758    bool possibleByteCodeEscape = false;  // set to true when \x, \o or \0 hex or octal escapes seen.
759    CharsetOperatorKind pendingOperationKind = intersectOp;
760    RE * pendingOperand = nullptr;
761
762    // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
763    bool negated = false;
764    if (*mCursor == '^') {
765        negated = true;
766        ++mCursor;
767    }
768    // Legacy rule: an unescaped ] may appear as a literal set character
769    // if and only if it appears immediately after the opening [ or [^
770    if ( *mCursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
771        insert(cc, ']');
772        lastItemKind = CodepointItem;
773        lastCodepointItem = static_cast<codepoint_t> (']');
774        ++mCursor;
775    } else if ( *mCursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
776        ++mCursor;
777        insert(cc, '-');
778        lastItemKind = CodepointItem;
779        lastCodepointItem = static_cast<codepoint_t> ('-');
780        if (*mCursor == '-') {
781            ParseFailure("Set operator has no left operand.");
782        }
783    }
784    while (mCursor.more()) {
785        const CharsetOperatorKind op = getCharsetOperator();
786        switch (op) {
787            case intersectOp:
788            case setDiffOp: {
789                if (lastItemKind == NoItem) {
790                    ParseFailure("Set operator has no left operand.");
791                }
792                if (!cc->empty()) {
793                    subexprs.push_back(mMemoizer.memoize(cc));
794                }
795                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
796                subexprs.clear();
797                cc = makeCC();
798                if (havePendingOperation) {
799                    if (pendingOperationKind == intersectOp) {
800                        pendingOperand = makeIntersect(pendingOperand, newOperand);
801                    }
802                    else {
803                        pendingOperand = makeDiff(pendingOperand, newOperand);
804                    }
805                }
806                else {
807                    pendingOperand = newOperand;
808                }
809                havePendingOperation = true;
810                pendingOperationKind = op;
811                lastItemKind = NoItem;
812            }
813            break;
814            case setCloser: {
815                if (lastItemKind == NoItem) {
816                    ParseFailure("Set operator has no right operand.");
817                }
818                if (!cc->empty()) {
819                    if (possibleByteCodeEscape && (cc->max_codepoint() <= 0xFF) && subexprs.empty() && !havePendingOperation) {
820                        subexprs.push_back(makeByte(cc));
821                    }
822                    else {
823                        subexprs.push_back(mMemoizer.memoize(cc));
824                    }
825                }
826                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
827                if (havePendingOperation) {
828                    if (pendingOperationKind == intersectOp) {
829                        newOperand = makeIntersect(pendingOperand, newOperand);
830                    }
831                    else {
832                        newOperand = makeDiff(pendingOperand, newOperand);
833                    }
834                }
835                if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
836                    if (CC * cc1 = dyn_cast<CC>(newOperand)) {
837                        newOperand = caseInsensitize(cc1);
838                    }
839                }
840                return negated ? makeComplement(newOperand) : newOperand;
841            }
842            case setOpener:
843            case posixPropertyOpener: {
844                if (lastItemKind != NoItem) {
845                    if (!cc->empty()) {
846                        subexprs.push_back(mMemoizer.memoize(cc));
847                    }
848                    RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
849                    subexprs.clear();
850                    cc = makeCC();
851                    if (havePendingOperation) {
852                        if (pendingOperationKind == intersectOp) {
853                            pendingOperand = makeIntersect(pendingOperand, newOperand);
854                        } else {
855                            pendingOperand = makeDiff(pendingOperand, newOperand);
856                        }
857                    }
858                    else {
859                        pendingOperand = newOperand;
860                    }
861                    subexprs.push_back(pendingOperand);
862                    havePendingOperation = false;
863                }
864                if (op == setOpener) {
865                    subexprs.push_back(parse_charset());
866                    lastItemKind = SetItem;
867                }
868                else if (op == posixPropertyOpener) {
869                    bool negated = false;
870                    if (*mCursor == '^') {
871                        negated = true;
872                        mCursor++;
873                    }
874                    RE * posixSet = parsePropertyExpression();
875                    subexprs.push_back(negated ? makeComplement(posixSet) : posixSet);
876                    lastItemKind = BrackettedSetItem;
877                    if (*mCursor++ != ':' || *mCursor++ != ']')
878                        ParseFailure("Posix set expression improperly terminated.");
879                }
880            }
881            break;
882            case rangeHyphen:
883                if (lastItemKind != CodepointItem) {
884                    ParseFailure("Range operator - has illegal left operand.");
885                }
886                if (*mCursor == '\\') {
887                    mCursor++;
888                    if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) possibleByteCodeEscape = true;
889                    insert_range(cc, lastCodepointItem, parse_escaped_codepoint());
890                } else {
891                    insert_range(cc, lastCodepointItem, parse_literal_codepoint());
892                }
893                lastItemKind = RangeItem;
894                break;
895            case hyphenChar:
896                insert(cc, '-');
897                lastItemKind = CodepointItem;
898                lastCodepointItem = static_cast<codepoint_t> ('-');
899                break;
900            case ampChar:
901                insert(cc, '&');
902                lastItemKind = CodepointItem;
903                lastCodepointItem = static_cast<codepoint_t> ('&');
904                break;
905            case backSlash:
906                if (isSetEscapeChar(*mCursor)) {
907                    subexprs.push_back(parseEscapedSet());
908                    lastItemKind = SetItem;
909                }
910                else {
911                    if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) possibleByteCodeEscape = true;
912                    lastCodepointItem = parse_escaped_codepoint();
913                    insert(cc, lastCodepointItem);
914                    lastItemKind = CodepointItem;
915                }
916                break;
917            case emptyOperator:
918                lastCodepointItem = parse_literal_codepoint();
919                insert(cc, lastCodepointItem);
920                lastItemKind = CodepointItem;
921                break;
922        }
923    }
924    ParseFailure("Set expression not properly terminated.");
925}
926
927
928// A backslash escape was found, and various special cases (back reference,
929// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
930// cluster \X have been ruled out.
931// It may be one of several possibilities or an error sequence.
932// 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
933// 2. General control codes c[@-_a-z?]
934// 3. Restricted octal notation 0 - 0777
935// 4. General octal notation o\{[0-7]+\}
936// 5. General hex notation x\{[0-9A-Fa-f]+\}
937// 6. An error for any unrecognized alphabetic escape
938// 7. An escaped ASCII symbol, standing for itself
939
940codepoint_t RE_Parser::parse_escaped_codepoint() {
941    codepoint_t cp_value;
942    switch (*mCursor) {
943        case 'a': ++mCursor; return 0x07; // BEL
944        case 'e': ++mCursor; return 0x1B; // ESC
945        case 'f': ++mCursor; return 0x0C; // FF
946        case 'n': ++mCursor; return 0x0A; // LF
947        case 'r': ++mCursor; return 0x0D; // CR
948        case 't': ++mCursor; return 0x09; // HT
949        case 'v': ++mCursor; return 0x0B; // VT
950        case 'c': // Control-escape based on next char
951            ++mCursor;
952            // \c@, \cA, ... \c_, or \ca, ..., \cz
953            if (((*mCursor >= '@') && (*mCursor <= '_')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))) {
954                cp_value = static_cast<codepoint_t>(*mCursor & 0x1F);
955                mCursor++;
956                return cp_value;
957            }
958            else if (*mCursor++ == '?') return 0x7F;  // \c? ==> DEL
959            else ParseFailure("Illegal \\c escape sequence");
960        case '0': // Octal escape:  0 - 0377
961            ++mCursor;
962            return parse_octal_codepoint(0,3);
963        case 'o':
964            ++mCursor;
965            if (*mCursor == '{') {
966                ++mCursor;
967                cp_value = parse_octal_codepoint(1, 7);
968                if (*mCursor++ != '}') ParseFailure("Malformed octal escape sequence");
969                return cp_value;
970            }
971            else {
972                ParseFailure("Malformed octal escape sequence");
973            }
974        case 'x':
975            ++mCursor;
976            if (*mCursor == '{') {
977              ++mCursor;
978              cp_value = parse_hex_codepoint(1, 6);
979              if (*mCursor++ != '}') ParseFailure("Malformed hex escape sequence");
980              return cp_value;
981            }
982            else {
983                return parse_hex_codepoint(1,2);  // ICU compatibility
984            }
985        case 'u':
986            ++mCursor;
987            if (*mCursor == '{') {
988                ++mCursor;
989                cp_value = parse_hex_codepoint(1, 6);
990                if (*mCursor++ != '}') ParseFailure("Malformed hex escape sequence");
991                return cp_value;
992            }
993            else {
994                return parse_hex_codepoint(4,4);  // ICU compatibility
995            }
996        case 'U':
997            ++mCursor;
998            return parse_hex_codepoint(8,8);  // ICU compatibility
999        default:
1000            // Escaped letters should be reserved for special functions.
1001            if (((*mCursor >= 'A') && (*mCursor <= 'Z')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))){
1002                //Escape unknown letter will be parse as normal letter
1003                return parse_literal_codepoint();
1004                //ParseFailure("Undefined or unsupported escape sequence");
1005            }
1006            else if ((*mCursor < 0x20) || (*mCursor >= 0x7F))
1007                ParseFailure("Illegal escape sequence");
1008            else return static_cast<codepoint_t>(*mCursor++);
1009    }
1010}
1011
1012codepoint_t RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
1013    codepoint_t value = 0;
1014    int count = 0;
1015    while (mCursor.more() && count < maxdigits) {
1016        const char t = *mCursor;
1017        if (t < '0' || t > '7') {
1018            break;
1019        }
1020        value = value * 8 | (t - '0');
1021        ++mCursor;
1022        ++count;
1023    }
1024    if (count < mindigits) ParseFailure("Octal sequence has too few digits");
1025    if (value > UCD::UNICODE_MAX) ParseFailure("Octal value too large");
1026    return value;
1027}
1028
1029codepoint_t RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
1030    codepoint_t value = 0;
1031    int count = 0;
1032    while (mCursor.more() && isxdigit(*mCursor) && count < maxdigits) {
1033        const char t = *mCursor;
1034        if (isdigit(t)) {
1035            value = (value * 16) | (t - '0');
1036        }
1037        else {
1038            value = ((value * 16) | ((t | 32) - 'a')) + 10;
1039        }
1040        ++mCursor;
1041        ++count;
1042    }
1043    if (count < mindigits) ParseFailure("Hexadecimal sequence has too few digits");
1044    if (value > UCD::UNICODE_MAX) ParseFailure("Hexadecimal value too large");
1045    return value;
1046}
1047
1048Name * RE_Parser::createCC(const codepoint_t cp) {
1049    CC * cc = nullptr;
1050    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
1051        cc = makeCC();
1052        caseInsensitiveInsert(cc, cp);
1053    } else {
1054        cc = makeCC(cp);
1055    }
1056    return mMemoizer.memoize(cc);
1057}
1058
1059void RE_Parser::insert(CC * cc, const codepoint_t cp) {
1060    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
1061        caseInsensitiveInsert(cc, cp);
1062    } else {
1063        cc->insert(cp);
1064    }
1065}
1066
1067void RE_Parser::insert_range(CC * cc, const codepoint_t lo, const codepoint_t hi) {
1068    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
1069        caseInsensitiveInsertRange(cc, lo, hi);
1070    } else {
1071        cc->insert_range(lo, hi);
1072    }
1073}
1074
1075RE * RE_Parser::makeComplement(RE * s) {
1076  return makeDiff(makeAny(), s);
1077}
1078
1079           
1080
1081                           
1082RE * RE_Parser::makeWordBoundary() {
1083    Name * wordC = makeWordSet();
1084    return makeReBoundary(wordC);
1085}
1086
1087RE * RE_Parser::makeWordNonBoundary() {
1088    Name * wordC = makeWordSet();
1089    return makeReNonBoundary(wordC);
1090}
1091
1092inline RE * RE_Parser::makeReBoundary(RE * re) {
1093    return makeBoundaryAssertion(re);
1094}
1095inline RE * RE_Parser::makeReNonBoundary(RE * re) {
1096    return makeNegativeBoundaryAssertion(re);
1097}
1098
1099RE * RE_Parser::makeWordBegin() {
1100    Name * wordC = makeWordSet();
1101    return makeNegativeLookBehindAssertion(wordC);
1102}
1103
1104RE * RE_Parser::makeWordEnd() {
1105    Name * wordC = makeWordSet();
1106    return makeNegativeLookAheadAssertion(wordC);
1107}
1108
1109Name * RE_Parser::makeDigitSet() {
1110    return mMemoizer.memoize(createName("nd"));
1111}
1112
1113Name * RE_Parser::makeAlphaNumeric() {
1114    return mMemoizer.memoize(createName("alnum"));
1115}
1116
1117Name * RE_Parser::makeWhitespaceSet() {
1118    return mMemoizer.memoize(createName("whitespace"));
1119}
1120
1121Name * RE_Parser::makeWordSet() {
1122    return mMemoizer.memoize(createName("word"));
1123}
1124
1125Name * RE_Parser::createName(std::string value) {
1126    auto key = std::make_pair("", value);
1127    auto f = mNameMap.find(key);
1128    if (f != mNameMap.end()) {
1129        return f->second;
1130    }
1131    Name * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
1132    mNameMap.insert(std::make_pair(std::move(key), property));
1133    return property;
1134    }
1135
1136Name * RE_Parser::createName(std::string prop, std::string value) {
1137    auto key = std::make_pair(prop, value);
1138    auto f = mNameMap.find(key);
1139    if (f != mNameMap.end()) {
1140        return f->second;
1141    }
1142    Name * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
1143    mNameMap.insert(std::make_pair(std::move(key), property));
1144    return property;
1145}
1146
1147LLVM_ATTRIBUTE_NORETURN void RE_Parser::ParseFailure(std::string errmsg) {
1148    llvm::report_fatal_error(errmsg);
1149}
1150
1151}
Note: See TracBrowser for help on using the repository browser.