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

Last change on this file since 5558 was 5558, checked in by cameron, 2 years ago

Unix lines mode and support for 'Byte' character classes

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