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

Last change on this file was 5772, checked in by cameron, 4 days ago

resolveGraphemeMode

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