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

Last change on this file since 5752 was 5752, checked in by cameron, 18 months ago

Allow unescaped ) as a literal left paren when there are no pending groups

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