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

Last change on this file was 5648, checked in by cameron, 21 hours ago

Regular expressions for property values: allow aliases, do not canonicalize (Unicode TR 18 - RL2.6)

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