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

Last change on this file since 5753 was 5753, checked in by cameron, 23 months ago

Parser for fixed strings (-F) mode

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