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

Last change on this file was 5698, checked in by cameron, 3 days ago

Modularization progress

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