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

Last change on this file since 5371 was 5308, checked in by cameron, 3 years ago

Boundary assertions; comment out a bug with RemoveNullableAfterAssertion?

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