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

Last change on this file since 4852 was 4852, checked in by nmedfort, 4 years ago

Bug fix for \N{..} + minor optimization changes.

File size: 33.7 KB
RevLine 
[3850]1/*
[4402]2 *  Copyright (c) 2015 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>
[4307]8#include <re/re_name.h>
[4255]9#include <re/re_alt.h>
10#include <re/re_end.h>
11#include <re/re_rep.h>
12#include <re/re_seq.h>
13#include <re/re_start.h>
14#include <re/re_diff.h>
[4298]15#include <re/re_intersect.h>
[4405]16#include <re/re_assertion.h>
[4829]17#include <re/re_grapheme_boundary.hpp>
[4806]18#include <re/printer_re.h>
[4673]19#include <UCD/resolve_properties.h>
[4316]20#include <UCD/CaseFolding_txt.h>
[4803]21#include <toolchain.h>
22#include "utf_encoding.h"
[4839]23#include <llvm/IR/Type.h>
[4803]24#include <pablo/pablo_compiler.h>
25#include <do_grep.h>
[4671]26#include <sstream>
[4182]27#include <algorithm>
[3850]28
[4309]29
30// It would probably be best to enforce that {}, [], () must always
31// be balanced.   But legacy syntax allows } and ] to occur as literals
32// in certain contexts (no opening { or [, or immediately after [ or [^ ).
33// Perhaps this define should become a parameter.
34#define LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED true
35#define LEGACY_UNESCAPED_HYPHEN_ALLOWED true
36
37
[4194]38namespace re {
39
[4412]40RE * RE_Parser::parse(const std::string & regular_expression, ModeFlagSet initialFlags) {
[4307]41    RE_Parser parser(regular_expression);
[4412]42    parser.fModeFlagSet = initialFlags;
[4798]43    parser.fNested = false;
[4312]44    RE * re = parser.parse_RE();
[4182]45    if (re == nullptr) {
46        throw ParseFailure("An unexpected parsing error occurred!");
47    }
48    return re;
49}
[3850]50
[4307]51inline RE_Parser::RE_Parser(const std::string & regular_expression)
[4829]52    : mCursor(regular_expression)
[4412]53    , fModeFlagSet(0)
[4798]54    , fNested(false)
[4412]55    {
[4798]56
[4412]57    }
[4798]58
[4311]59RE * makeAtomicGroup(RE * r) {
60    throw ParseFailure("Atomic grouping not supported.");
61}
62
63RE * makeBranchResetGroup(RE * r) {
64    // Branch reset groups only affect submatch numbering, but
65    // this has no effect in icgrep.
66    return r;
67}
[4798]68
[4311]69RE * RE_Parser::parse_RE() {
[4841]70    return parse_alt();
[4311]71}
72
73RE * RE_Parser::parse_alt() {
[4203]74    std::vector<RE *> alt;
[4182]75    for (;;) {
[4203]76        alt.push_back(parse_seq());
[4841]77        if (*mCursor != '|') {
[4182]78            break;
79        }
[4829]80        ++mCursor; // advance past the alternation character '|'
[3850]81    }
[4841]82    if (alt.empty()) {
[4182]83        throw NoRegularExpressionFound();
[3850]84    }
[4203]85    return makeAlt(alt.begin(), alt.end());
[3850]86}
87
[4182]88inline RE * RE_Parser::parse_seq() {
[4203]89    std::vector<RE *> seq;
[4182]90    for (;;) {
[4311]91        RE * re = parse_next_item();
[4182]92        if (re == nullptr) {
93            break;
[3850]94        }
[4852]95        re = extend_item(re);
96        seq.push_back(re);
[3850]97    }
[4249]98    return makeSeq(seq.begin(), seq.end());
[3850]99}
100
[4311]101RE * RE_Parser::parse_next_item() {
[4852]102    if (mCursor.more()) {       
[4829]103        switch (*mCursor) {
[4182]104            case '(':
[4829]105                ++mCursor;
[4311]106                return parse_group();
[4182]107            case '^':
[4829]108                ++mCursor;
[4309]109                return makeStart();
[4182]110            case '$':
[4829]111                ++mCursor;
[4309]112                return makeEnd();
[4182]113            case '|': case ')':
[4841]114                break;
[4798]115            case '*': case '+': case '?': case '{':
[4304]116                throw NothingToRepeat();
[4798]117            case ']':
[4310]118                if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
[4819]119                    return createCC(parse_utf8_codepoint());
[4310]120                }
[4841]121                throw ParseFailure("Use  \\] for literal ].");
[4798]122            case '}':
123                if (fNested) {
[4841]124                    break;  //  a recursive invocation for a regexp in \N{...}
125                } else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
[4819]126                    return createCC(parse_utf8_codepoint());
[4798]127                }
[4841]128                throw ParseFailure("Use \\} for literal }.");
[4182]129            case '[':
[4829]130                mCursor++;
[4309]131                return parse_charset();
[4182]132            case '.': // the 'any' metacharacter
[4829]133                mCursor++;
[4311]134                return makeAny();
[4310]135            case '\\'// escape processing
[4829]136                ++mCursor;
[4309]137                return parse_escaped();
[4182]138            default:
[4819]139                return createCC(parse_utf8_codepoint());
[4182]140        }
[3850]141    }
[4841]142    return nullptr;
[4182]143}
[4798]144
145
[4841]146// Parse some kind of parenthesized group.  Input precondition: mCursor
[4311]147// after the (
148RE * RE_Parser::parse_group() {
[4841]149    const ModeFlagSet modeFlagSet = fModeFlagSet;
150    RE * group_expr = nullptr;
[4829]151    if (*mCursor == '?') {
152        switch (*++mCursor) {
[4311]153            case '#'// comment
[4841]154                while (*++mCursor != ')');
[4829]155                ++mCursor;
[4311]156                return parse_next_item();
157            case ':':  // Non-capturing paren
[4829]158                ++mCursor;
[4311]159                group_expr = parse_alt();
160                break;
161            case '=':
[4829]162                ++mCursor;
[4841]163                group_expr = makeLookAheadAssertion(parse_alt());
[4311]164                break;
165            case '!':
[4829]166                ++mCursor;
[4841]167                group_expr = makeNegativeLookAheadAssertion(parse_alt());
[4311]168                break;
169            case '>':
[4829]170                ++mCursor;
[4841]171                group_expr = makeAtomicGroup(parse_alt());
[4311]172                break;
173            case '|':
[4829]174                ++mCursor;
[4841]175                group_expr = makeBranchResetGroup(parse_alt());
[4311]176                break;
177            case '<':
[4829]178                ++mCursor;
179                if (*mCursor == '=') {
180                    ++mCursor;
[4841]181                    group_expr = makeLookBehindAssertion(parse_alt());
[4311]182                }
[4829]183                else if (*mCursor == '!') {
184                    ++mCursor;
[4841]185                    group_expr = makeNegativeLookBehindAssertion(parse_alt());
[4829]186                } else {
[4311]187                    throw ParseFailure("Illegal lookbehind assertion syntax.");
188                }
189                break;
[4841]190            case '-': case 'd' : case 'i': case 'm': case 's': case 'x': case 'g':
[4831]191                while (*mCursor != ')' && *mCursor != ':') {
[4841]192                    bool negateMode = false;
193                    ModeFlagType modeBit;
[4829]194                    if (*mCursor == '-') {
[4311]195                        negateMode = true;
[4829]196                        ++mCursor;
[4311]197                    }
[4841]198                    switch (*mCursor) {
[4311]199                        case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
[4831]200                        case 'g': modeBit = GRAPHEME_CLUSTER_MODE; break;
[4429]201                        //case 'm': modeBit = MULTILINE_MODE_FLAG; break;
202                        //case 's': modeBit = DOTALL_MODE_FLAG; break;
203                        //case 'x': modeBit = IGNORE_SPACE_MODE_FLAG; break;
204                        //case 'd': modeBit = UNIX_LINES_MODE_FLAG; break;
205                        default: throw ParseFailure("Unsupported mode flag.");
[4311]206                    }
[4841]207                    ++mCursor;
[4311]208                    if (negateMode) {
[4312]209                        fModeFlagSet &= ~modeBit;
[4311]210                        negateMode = false;  // for next flag
[4829]211                    } else {
212                        fModeFlagSet |= modeBit;
[4311]213                    }
214                }
[4829]215                if (*mCursor == ':') {
216                    ++mCursor;
[4311]217                    group_expr = parse_alt();
[4841]218                    fModeFlagSet = modeFlagSet;
219                    break;
[4829]220                } else {  // if *_cursor == ')'
221                    ++mCursor;
[4311]222                    return parse_next_item();
223                }
224            default:
225                throw ParseFailure("Illegal (? syntax.");
226        }
[4829]227    } else { // Capturing paren group, but ignore capture in icgrep.
[4311]228        group_expr = parse_alt();
229    }
[4829]230    if (*mCursor != ')') {
231        throw ParseFailure("Closing parenthesis required.");
232    }
233    ++mCursor;
[4311]234    return group_expr;
[3850]235}
[4798]236
[4841]237inline RE * RE_Parser::extend_item(RE * re) {
238    if (LLVM_LIKELY(mCursor.more())) {
[4829]239        int lb = 0, ub = 0;
[4841]240        bool hasRep = true;
[4829]241        switch (*mCursor) {
242            case '*':
243                lb = 0;
244                ub = Rep::UNBOUNDED_REP;
245                break;
246            case '?':
247                lb = 0;
248                ub = 1;
249                break;
250            case '+':
251                lb = 1;
252                ub = Rep::UNBOUNDED_REP;
253                break;
254            case '{':
255                std::tie(lb, ub) = parse_range_bound();
256                break;
257            default:
[4841]258                hasRep = false;
[4829]259        }
[4841]260        if (hasRep) {
261            if (lb > MAX_REPETITION_LOWER_BOUND || ub > MAX_REPETITION_UPPER_BOUND) {
262                throw ParseFailure("Bounded repetition exceeds icgrep implementation limit");
263            }
264            if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
265                throw ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
266            }
[4831]267            ++mCursor;
[4841]268            if (*mCursor == '?') { // Non-greedy qualifier
269                // Greedy vs. non-greedy makes no difference for icgrep.
270                ++mCursor;
271            } else if (*mCursor == '+') {
272                ++mCursor;
273                throw ParseFailure("Possessive repetition is not supported in icgrep 1.0");
274            }
275            re = makeRep(re, lb, ub);
[4829]276        }
[3850]277    }
[4841]278    if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
279        re = makeGraphemeClusterBoundary(GraphemeBoundary::Sense::Positive, re);
280    }
281    return re;
[4829]282}
283
284inline std::pair<int, int> RE_Parser::parse_range_bound() {
285    int lower_bound = 0, upper_bound = 0;
[4831]286    if (*++mCursor == ',') {
[4829]287        ++mCursor;
288    } else {
[4182]289        lower_bound = parse_int();
[3850]290    }
[4829]291    if (*mCursor == '}') {
[4306]292        upper_bound = lower_bound;
[4829]293    } else if (*mCursor != ',') {
[4182]294        throw BadLowerBound();
[4831]295    } else if (*++mCursor == '}') {
296        upper_bound = Rep::UNBOUNDED_REP;
297    } else {
298        upper_bound = parse_int();
299        if (*mCursor != '}') {
300            throw BadUpperBound();
[3850]301        }
[4182]302    }
[4829]303    return std::make_pair(lower_bound, upper_bound);
[3850]304}
305
[4309]306unsigned RE_Parser::parse_int() {
307    unsigned value = 0;
[4831]308    while (isdigit(*mCursor)) {
[4309]309        value *= 10;
[4831]310        value += static_cast<int>(*mCursor++) - 48;
[4309]311    }
312    return value;
313}
314
[3850]315
[4307]316#define bit40(x) (1ULL << ((x) - 0x40))
[4829]317const uint64_t setEscapeCharacters = bit40('b') | bit40('p') | bit40('q') | bit40('d') | bit40('w') | bit40('s') |
318                                     bit40('B') | bit40('P') | bit40('Q') | bit40('D') | bit40('W') | bit40('S') | bit40('N') | bit40('X');
[4307]319
320inline bool isSetEscapeChar(char c) {
321    return c >= 0x40 && c <= 0x7F && ((setEscapeCharacters >> (c - 0x40)) & 1) == 1;
322}
323
324inline RE * RE_Parser::parse_escaped() {
[4830]325    if (isSetEscapeChar(*mCursor)) {
326        return parseEscapedSet();
327    }
328    else {
329        return createCC(parse_escaped_codepoint());
330    }
[4307]331}
[4830]332   
[4671]333RE * RE_Parser::parseEscapedSet() {
[4310]334    bool complemented = false;
[4829]335    RE * re = nullptr;
336    switch (*mCursor) {
[4830]337        case 'B': complemented = true;
[4402]338        case 'b':
[4831]339            if (*++mCursor != '{') {
[4830]340                return complemented ? makeWordNonBoundary() : makeWordBoundary();
[4831]341            } else {
342                switch (*++mCursor) {
[4841]343                    case 'g':
344                        re = makeGraphemeClusterBoundary(complemented ? GraphemeBoundary::Sense::Negative : GraphemeBoundary::Sense::Positive);
345                        break;
[4830]346                    case 'w': throw ParseFailure("\\b{w} not yet supported.");
347                    case 'l': throw ParseFailure("\\b{l} not yet supported.");
348                    case 's': throw ParseFailure("\\b{s} not yet supported.");
349                    default: throw ParseFailure("Unrecognized boundary assertion");
350                }
[4831]351                if (*++mCursor != '}') {
[4830]352                    throw ParseFailure("Malformed boundary assertion");
353                }
354                ++mCursor;
[4841]355                return re;
[4830]356            }
[4310]357        case 'd':
[4829]358            ++mCursor;
[4310]359            return makeDigitSet();
360        case 'D':
[4829]361            ++mCursor;
[4310]362            return makeComplement(makeDigitSet());
363        case 's':
[4829]364            ++mCursor;
[4310]365            return makeWhitespaceSet();
366        case 'S':
[4829]367            ++mCursor;
[4310]368            return makeComplement(makeWhitespaceSet());
369        case 'w':
[4829]370            ++mCursor;
[4310]371            return makeWordSet();
372        case 'W':
[4829]373            ++mCursor;
[4310]374            return makeComplement(makeWordSet());
[4829]375        case 'Q':
376            complemented = true;
377        case 'q':
378            if (*++mCursor != '{') {
379                throw ParseFailure("Malformed grapheme-boundary property expression");
380            }
381            ++mCursor;
[4830]382            throw ParseFailure("Literal grapheme cluster expressions not yet supported.");
[4829]383            if (*mCursor != '}') {
384                throw ParseFailure("Malformed grapheme-boundary property expression");
385            }
386            ++mCursor;
387            return complemented ? makeComplement(re) : re;
[4182]388        case 'P':
[4309]389            complemented = true;
[4182]390        case 'p':
[4829]391            if (*++mCursor != '{') {
392                throw ParseFailure("Malformed property expression");
393            }
394            ++mCursor;
395            re = parsePropertyExpression();
396            if (*mCursor != '}') {
397                throw ParseFailure("Malformed property expression");
398            }
399            ++mCursor;
400            return complemented ? makeComplement(re) : re;
401        case 'X':
402            // \X is equivalent to ".+?\b{g}"; proceed the minimal number of characters (but at least one)
[4830]403            // to get to the next extended grapheme cluster boundary.
[4829]404            ++mCursor;
[4841]405            // return makeSeq({makeRep(makeAny(), 1, Rep::UNBOUNDED_REP), makeGraphemeClusterBoundary()});
406            return makeGraphemeClusterBoundary(GraphemeBoundary::Sense::Positive, makeAny());
[4798]407        case 'N':
[4829]408            if (*++mCursor != '{') {
409                throw ParseFailure("Malformed \\N expression");
410            }
411            ++mCursor;
412            re = parseNamePatternExpression();
413            if (*mCursor != '}') {
414                throw ParseFailure("Malformed \\N expression");
415            }
416            ++mCursor;
[4852]417            assert (re);
[4829]418            return re;
[4310]419        default:
420            throw ParseFailure("Internal error");
[3850]421    }
422}
423
[4311]424codepoint_t RE_Parser::parse_utf8_codepoint() {
[4332]425    // Must cast to unsigned char to avoid sign extension.
[4829]426    unsigned char pfx = static_cast<unsigned char>(*mCursor++);
[4333]427    codepoint_t cp = pfx;
428    if (pfx < 0x80) return cp;
[4829]429    unsigned suffix_bytes = 0;
[4333]430    if (pfx < 0xE0) {
431        if (pfx < 0xC2) {  // bare suffix or illegal prefix 0xC0 or 0xC2
[4182]432            throw InvalidUTF8Encoding();
[3934]433        }
[4333]434        suffix_bytes = 1;
435        cp &= 0x1F;
[4829]436    } else if (pfx < 0xF0) { // [0xE0, 0xEF]
[4333]437        cp &= 0x0F;
438        suffix_bytes = 2;
[4829]439    } else { // [0xF0, 0xFF]
[4333]440        cp &= 0x0F;
441        suffix_bytes = 3;
442    }
443    while (suffix_bytes--) {
[4829]444        if (mCursor.noMore()) {
[4333]445            throw InvalidUTF8Encoding();
[3934]446        }
[4829]447        char_t sfx = *mCursor++;
[4333]448        if ((sfx & 0xC0) != 0x80) {
449            throw InvalidUTF8Encoding();
450        }
451        cp = (cp << 6) | (sfx & 0x3F);
[3934]452    }
[4333]453    // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
454    // or a 4-byte sequence is used to encode a codepoint < 0x10000.
455    if ((pfx == 0xE0 && cp < 0x800) || (pfx == 0xF0 && cp < 0x10000)) {
456        throw InvalidUTF8Encoding();
457    }
[4798]458    // It is an error if a 4-byte sequence is used to encode a codepoint
459    // above the Unicode maximum.
[4812]460    if (cp > UCD::UNICODE_MAX) {
[4194]461        throw InvalidUTF8Encoding();
462    }
[4332]463    return cp;
[3934]464}
465
[4671]466std::string RE_Parser::canonicalize(const cursor_t begin, const cursor_t end) {
467    std::locale loc;
[4829]468    std::stringstream s;   
[4671]469    for (auto i = begin; i != end; ++i) {
470        switch (*i) {
471            case '_': case ' ': case '-':
472                break;
473            default:
474                s << std::tolower(*i, loc);
475        }
476    }
477    return s.str();
478}
479
[4819]480RE * RE_Parser::parsePropertyExpression() {
[4829]481    const auto start = mCursor.pos();
482    while (mCursor.more()) {
483        bool done = false;
484        switch (*mCursor) {
485            case '}': case ':': case '=':
486                done = true;
487        }
488        if (done) {
489            break;
490        }
491        ++mCursor;
[4310]492    }
[4829]493    if (*mCursor == '=') {
494        const auto prop_end = mCursor.pos();
495        mCursor++;
496        const auto val_start = mCursor.pos();
497        while (mCursor.more()) {
498            bool done = false;
499            switch (*mCursor) {
500                case '}': case ':':
501                    done = true;
502            }
503            if (done) {
504                break;
505            }
506            ++mCursor;
[4377]507        }
508        // We have a property-name = value expression
[4829]509        return createName(std::move(canonicalize(start, prop_end)), std::move(canonicalize(val_start, mCursor.pos())));
[4377]510    }
[4829]511    return createName(std::move(canonicalize(start, mCursor.pos())));
[3935]512}
[4377]513
[4852]514Name * RE_Parser::parseNamePatternExpression(){
[4671]515
[4819]516    ModeFlagSet outerFlags = fModeFlagSet;
[4798]517    fModeFlagSet = 1;
518
519    bool outerNested = fNested;
520    fNested = true;
521
522    RE * nameRE = parse_RE();
[4829]523
[4798]524    // Reset outer parsing state.
525    fModeFlagSet = outerFlags;
526    fNested = outerNested;
527
528    // Embed the nameRE in ";.*$nameRE" to skip the codepoint field of Uname.txt
[4819]529    RE * embedded = makeSeq({mMemoizer.memoize(makeCC(0x3B)), makeRep(makeAny(), 0, Rep::UNBOUNDED_REP), nameRE});
[4803]530    Encoding encoding(Encoding::Type::UTF_8, 8);
[4806]531    embedded = regular_expression_passes(encoding, embedded);
[4829]532
[4803]533    pablo::PabloFunction * nameSearchFunction = re2pablo_compiler(encoding, embedded);
534    llvm::Function * nameSearchIR = nullptr;
535   
536    pablo_function_passes(nameSearchFunction);
[4839]537    pablo::PabloCompiler pablo_compiler(VectorType::get(IntegerType::get(getGlobalContext(), 64), BLOCK_SIZE/64));
[4803]538    try {
539        nameSearchIR = pablo_compiler.compile(nameSearchFunction);
540    }
541    catch (std::runtime_error e) {
542        releaseSlabAllocatorMemory();
[4819]543        throw e;
[4803]544    }
[4829]545
546    llvm::ExecutionEngine * engine = JIT_to_ExecutionEngine(nameSearchIR);   
[4803]547    icgrep_Linking(nameSearchIR->getParent(), engine);
548   
549    // Ensure everything is ready to go.
550    engine->finalizeObject();
[4852]551       
552    void * icgrep_MCptr = engine->getPointerToFunction(nameSearchIR);   
553    CC * codepoints = nullptr;
[4803]554    if (icgrep_MCptr) {
[4852]555        void * icgrep_init_carry_ptr = engine->getPointerToFunction(nameSearchIR->getParent()->getFunction("process_block_initialize_carries"));
[4826]556        GrepExecutor grepEngine(icgrep_init_carry_ptr, icgrep_MCptr);
[4803]557        grepEngine.setParseCodepointsOption();
558        grepEngine.doGrep("../Uname.txt");
[4852]559        codepoints = grepEngine.getParsedCodepoints();
560        assert (codepoints);
[4803]561    }
562    delete engine;
[4852]563    if (codepoints) {
564        Name * const result = mMemoizer.memoize(codepoints);
565        assert (*cast<CC>(result->getDefinition()) == *codepoints);
566        return result;
567    }
568    return nullptr;
[4798]569}
570
571
[4309]572CharsetOperatorKind RE_Parser::getCharsetOperator() {
[4829]573    switch (*mCursor) {
[4310]574        case '&':
[4829]575            ++mCursor;
[4831]576            if (*mCursor == '&') {
[4829]577                ++mCursor;
[4310]578                return intersectOp;
[4831]579            } else if (*mCursor == '[') {
[4310]580                // Short-hand for intersectOp when a set follows
581                return intersectOp;
582            }
[4831]583            return ampChar;
[4310]584        case '-':
[4829]585            ++mCursor;
[4831]586            if (*mCursor == '-') {
[4829]587                ++mCursor;
[4310]588                return setDiffOp;
[4831]589            } else if (*mCursor == '[') {
[4310]590                return setDiffOp;
[4831]591            } else if (*mCursor == ']') {
[4310]592                return hyphenChar;
593            }
[4831]594            return rangeHyphen;
[4310]595        case '[':
[4829]596            ++mCursor;
[4831]597            if (*mCursor == ':') {
[4829]598                ++mCursor;
[4310]599                return posixPropertyOpener;
600            }
[4831]601            return setOpener;
[4310]602        case ']':
[4829]603            ++mCursor;
[4310]604            return setCloser;
605        case '\\':
[4829]606            ++mCursor;
[4310]607            return backSlash;
608        default:
609            return emptyOperator;
610    }
[4798]611}
612
[4309]613// Precondition: cursor is immediately after opening '[' character
[4182]614RE * RE_Parser::parse_charset() {
[4310]615    // Sets are accumulated using two variables:
616    // subexprs accumulates set expressions such as \p{Lu}, [\w && \p{Greek}]
[4798]617    // cc accumulates the literal and calculated codepoints and ranges
[4310]618    std::vector<RE *> subexprs;
[4272]619    CC * cc = makeCC();
[4310]620    // When the last item deal with is a single literal charcacter or calculated codepoint,
621    // a following hyphen can indicate a range.   When the last item is a set subexpression,
622    // a following hyphen can indicate set subtraction.
623    enum {NoItem, CodepointItem, RangeItem, SetItem, BrackettedSetItem} lastItemKind = NoItem;
[4311]624    codepoint_t lastCodepointItem;
[4798]625
[4310]626    bool havePendingOperation = false;
627    CharsetOperatorKind pendingOperationKind;
628    RE * pendingOperand;
[4798]629
[4309]630    // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
[4182]631    bool negated = false;
[4829]632    if (*mCursor == '^') {
[4516]633        negated = true;
[4829]634        ++mCursor;
[4309]635    }
[4310]636    // Legacy rule: an unescaped ] may appear as a literal set character
637    // if and only if it appears immediately after the opening [ or [^
[4829]638    if ( *mCursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
[4819]639        insert(cc, ']');
[4310]640        lastItemKind = CodepointItem;
[4311]641        lastCodepointItem = static_cast<codepoint_t> (']');
[4829]642        ++mCursor;
643    } else if ( *mCursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
644        ++mCursor;
[4819]645        insert(cc, '-');
[4310]646        lastItemKind = CodepointItem;
[4311]647        lastCodepointItem = static_cast<codepoint_t> ('-');
[4829]648        if (*mCursor == '-') {
[4516]649            throw ParseFailure("Set operator has no left operand.");
650        }
[4309]651    }
[4829]652    while (mCursor.more()) {
[4622]653        const CharsetOperatorKind op = getCharsetOperator();
[4310]654        switch (op) {
[4516]655            case intersectOp:
656            case setDiffOp: {
657                if (lastItemKind == NoItem) {
658                    throw ParseFailure("Set operator has no left operand.");
659                }
[4819]660                if (!cc->empty()) {
661                    subexprs.push_back(mMemoizer.memoize(cc));
[4516]662                }
[4310]663                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
664                subexprs.clear();
665                cc = makeCC();
666                if (havePendingOperation) {
667                    if (pendingOperationKind == intersectOp) {
668                        pendingOperand = makeIntersect(pendingOperand, newOperand);
669                    }
670                    else {
671                        pendingOperand = makeDiff(pendingOperand, newOperand);
672                    }
673                }
674                else {
675                    pendingOperand = newOperand;
676                }
677                havePendingOperation = true;
678                pendingOperationKind = op;
679                lastItemKind = NoItem;
680            }
681            break;
682            case setCloser: {
[4516]683                if (lastItemKind == NoItem) {
684                    throw ParseFailure("Set operator has no right operand.");
685                }
[4819]686                if (!cc->empty()) {
687                    subexprs.push_back(mMemoizer.memoize(cc));
[4320]688                }
[4310]689                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
690                if (havePendingOperation) {
691                    if (pendingOperationKind == intersectOp) {
692                        newOperand = makeIntersect(pendingOperand, newOperand);
693                    }
694                    else {
695                        newOperand = makeDiff(pendingOperand, newOperand);
696                    }
697                }
[4320]698                if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
699                    if (CC * cc1 = dyn_cast<CC>(newOperand)) {
700                        newOperand = caseInsensitize(cc1);
701                    }
702                }
[4516]703                return negated ? makeComplement(newOperand) : newOperand;
[4310]704            }
[4516]705            case setOpener:
706            case posixPropertyOpener: {
[4310]707                if (lastItemKind != NoItem) {
[4819]708                    if (!cc->empty()) {
709                        subexprs.push_back(mMemoizer.memoize(cc));
710                    }
[4310]711                    RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
712                    subexprs.clear();
713                    cc = makeCC();
714                    if (havePendingOperation) {
715                        if (pendingOperationKind == intersectOp) {
716                            pendingOperand = makeIntersect(pendingOperand, newOperand);
[4829]717                        } else {
[4310]718                            pendingOperand = makeDiff(pendingOperand, newOperand);
719                        }
720                    }
721                    else {
722                        pendingOperand = newOperand;
723                    }
724                    subexprs.push_back(pendingOperand);
725                    havePendingOperation = false;
726                }
727                if (op == setOpener) {
728                    subexprs.push_back(parse_charset());
729                    lastItemKind = SetItem;
730                }
731                else if (op == posixPropertyOpener) {
732                    bool negated = false;
[4829]733                    if (*mCursor == '^') {
[4310]734                        negated = true;
[4829]735                        mCursor++;
[4310]736                    }
[4671]737                    RE * posixSet = parsePropertyExpression();
[4829]738                    subexprs.push_back(negated ? makeComplement(posixSet) : posixSet);
[4310]739                    lastItemKind = BrackettedSetItem;
[4829]740                    if (*mCursor++ != ':' || *mCursor++ != ']')
[4310]741                        throw ParseFailure("Posix set expression improperly terminated.");
742                }
743            }
744            break;
745            case rangeHyphen:
[4516]746                if (lastItemKind != CodepointItem) {
747                    throw ParseFailure("Range operator - has illegal left operand.");
748                }
[4819]749                insert_range(cc, lastCodepointItem, parse_codepoint());
[4310]750                lastItemKind = RangeItem;
751                break;
752            case hyphenChar:
[4819]753                insert(cc, '-');
[4310]754                lastItemKind = CodepointItem;
[4311]755                lastCodepointItem = static_cast<codepoint_t> ('-');
[4310]756                break;
757            case ampChar:
[4819]758                insert(cc, '&');
[4310]759                lastItemKind = CodepointItem;
[4311]760                lastCodepointItem = static_cast<codepoint_t> ('&');
[4310]761                break;
762            case backSlash:
[4829]763                if (isSetEscapeChar(*mCursor)) {
[4671]764                    subexprs.push_back(parseEscapedSet());
[4310]765                    lastItemKind = SetItem;
766                }
767                else {
768                    lastCodepointItem = parse_escaped_codepoint();
[4819]769                    insert(cc, lastCodepointItem);
[4310]770                    lastItemKind = CodepointItem;
771                }
772                break;
773            case emptyOperator:
774                lastCodepointItem = parse_utf8_codepoint();
[4819]775                insert(cc, lastCodepointItem);
[4310]776                lastItemKind = CodepointItem;
777                break;
778        }
779    }
780    throw ParseFailure("Set expression not properly terminated.");
[3850]781}
782
[4309]783
[4311]784codepoint_t RE_Parser::parse_codepoint() {
[4831]785    if (*mCursor == '\\') {
[4829]786        mCursor++;
[4309]787        return parse_escaped_codepoint();
[4831]788    } else {
[4309]789        return parse_utf8_codepoint();
[3850]790    }
[4182]791}
[3850]792
[4305]793// A backslash escape was found, and various special cases (back reference,
[4402]794// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
[4305]795// cluster \X have been ruled out.
796// It may be one of several possibilities or an error sequence.
[4402]797// 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
[4305]798// 2. General control codes c[@-_a-z?]
799// 3. Restricted octal notation 0 - 0777
800// 4. General octal notation o\{[0-7]+\}
801// 5. General hex notation x\{[0-9A-Fa-f]+\}
[4798]802// 6. An error for any unrecognized alphabetic escape
[4305]803// 7. An escaped ASCII symbol, standing for itself
804
[4311]805codepoint_t RE_Parser::parse_escaped_codepoint() {
806    codepoint_t cp_value;
[4829]807    switch (*mCursor) {
808        case 'a': ++mCursor; return 0x07; // BEL
809        case 'e': ++mCursor; return 0x1B; // ESC
810        case 'f': ++mCursor; return 0x0C; // FF
811        case 'n': ++mCursor; return 0x0A; // LF
812        case 'r': ++mCursor; return 0x0D; // CR
813        case 't': ++mCursor; return 0x09; // HT
814        case 'v': ++mCursor; return 0x0B; // VT
[4310]815        case 'c': // Control-escape based on next char
[4829]816            ++mCursor;
[4310]817            // \c@, \cA, ... \c_, or \ca, ..., \cz
[4829]818            if (((*mCursor >= '@') && (*mCursor <= '_')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))) {
819                cp_value = static_cast<codepoint_t>(*mCursor & 0x1F);
820                mCursor++;
[4310]821                return cp_value;
822            }
[4829]823            else if (*mCursor++ == '?') return 0x7F;  // \c? ==> DEL
[4310]824            else throw("Illegal \\c escape sequence");
825        case '0': // Octal escape:  0 - 0377
[4829]826            ++mCursor;
[4310]827            return parse_octal_codepoint(0,3);
[4798]828        case 'o':
[4829]829            ++mCursor;
830            if (*mCursor == '{') {
831                ++mCursor;
[4310]832                cp_value = parse_octal_codepoint(1, 7);
[4829]833                if (*mCursor++ != '}') throw ParseFailure("Malformed octal escape sequence");
[4310]834                return cp_value;
835            }
836            else {
837                throw ParseFailure("Malformed octal escape sequence");
838            }
[4798]839        case 'x':
[4829]840            ++mCursor;
841            if (*mCursor == '{') {
842              ++mCursor;
[4310]843              cp_value = parse_hex_codepoint(1, 6);
[4829]844              if (*mCursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
[4310]845              return cp_value;
846            }
847            else {
848                return parse_hex_codepoint(1,2);  // ICU compatibility
849            }
850        case 'u':
[4829]851            ++mCursor;
852            if (*mCursor == '{') {
853                ++mCursor;
[4310]854                cp_value = parse_hex_codepoint(1, 6);
[4829]855                if (*mCursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
[4310]856                return cp_value;
857            }
858            else {
859                return parse_hex_codepoint(4,4);  // ICU compatibility
860            }
[4798]861        case 'U':
[4829]862            ++mCursor;
[4310]863            return parse_hex_codepoint(8,8);  // ICU compatibility
864        default:
865            // Escaped letters should be reserved for special functions.
[4829]866            if (((*mCursor >= 'A') && (*mCursor <= 'Z')) || ((*mCursor >= 'a') && (*mCursor <= 'z')))
[4310]867                throw ParseFailure("Undefined or unsupported escape sequence");
[4829]868            else if ((*mCursor < 0x20) || (*mCursor >= 0x7F))
[4310]869                throw ParseFailure("Illegal escape sequence");
[4829]870            else return static_cast<codepoint_t>(*mCursor++);
[4310]871    }
[3850]872}
873
[4311]874codepoint_t RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
875    codepoint_t value = 0;
[4310]876    int count = 0;
[4829]877    while (mCursor.more() && count < maxdigits) {
878        const char t = *mCursor;
[4310]879        if (t < '0' || t > '7') {
880            break;
881        }
882        value = value * 8 | (t - '0');
[4829]883        ++mCursor;
[4310]884        ++count;
885    }
886    if (count < mindigits) throw ParseFailure("Octal sequence has too few digits");
[4812]887    if (value > UCD::UNICODE_MAX) throw ParseFailure("Octal value too large");
[4310]888    return value;
[4305]889}
890
[4311]891codepoint_t RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
892    codepoint_t value = 0;
[4310]893    int count = 0;
[4829]894    while (mCursor.more() && isxdigit(*mCursor) && count < maxdigits) {
895        const char t = *mCursor;
[4310]896        if (isdigit(t)) {
897            value = (value * 16) | (t - '0');
898        }
[4798]899        else {
[4310]900            value = (value * 16) | ((t | 32) - 'a') + 10;
901        }
[4829]902        ++mCursor;
[4310]903        ++count;
904    }
905    if (count < mindigits) throw ParseFailure("Hexadecimal sequence has too few digits");
[4812]906    if (value > UCD::UNICODE_MAX) throw ParseFailure("Hexadecimal value too large");
[4310]907    return value;
[4305]908}
909
[4819]910inline Name * RE_Parser::createCC(const codepoint_t cp) {
911    CC * cc = nullptr;
912    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
913        cc = makeCC();
914        caseInsensitiveInsert(cc, cp);
915    } else {
916        cc = makeCC(cp);
917    }
918    return mMemoizer.memoize(cc);
[4194]919}
[4316]920
[4819]921inline void RE_Parser::insert(CC * cc, const codepoint_t cp) {
[4316]922    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
923        caseInsensitiveInsert(cc, cp);
[4812]924    } else {
925        cc->insert(cp);
[4316]926    }
927}
928
[4819]929inline void RE_Parser::insert_range(CC * cc, const codepoint_t lo, const codepoint_t hi) {
[4316]930    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
931        caseInsensitiveInsertRange(cc, lo, hi);
[4812]932    } else {
933        cc->insert_range(lo, hi);
[4316]934    }
935}
[4798]936
[4671]937RE * RE_Parser::makeComplement(RE * s) {
938  return makeDiff(makeAny(), s);
[4316]939}
[4671]940
[4830]941           
942                       
943                           
[4829]944RE * RE_Parser::makeWordBoundary() {
945    Name * wordC = makeWordSet();
[4671]946    return makeAlt({makeSeq({makeNegativeLookBehindAssertion(wordC), makeLookAheadAssertion(wordC)}),
947                    makeSeq({makeLookBehindAssertion(wordC), makeNegativeLookAheadAssertion(wordC)})});
948}
949
[4829]950RE * RE_Parser::makeWordNonBoundary() {
951    Name * wordC = makeWordSet();
[4671]952    return makeAlt({makeSeq({makeNegativeLookBehindAssertion(wordC), makeNegativeLookAheadAssertion(wordC)}),
953                    makeSeq({makeLookBehindAssertion(wordC), makeLookAheadAssertion(wordC)})});
954}
955
[4829]956inline Name * RE_Parser::makeDigitSet() {
957    return mMemoizer.memoize(createName("nd"));
[4671]958}
959
[4829]960inline Name * RE_Parser::makeAlphaNumeric() {
961    return mMemoizer.memoize(createName("alnum"));
[4671]962}
963
[4829]964inline Name * RE_Parser::makeWhitespaceSet() {
965    return mMemoizer.memoize(createName("whitespace"));
[4671]966}
967
[4829]968inline Name * RE_Parser::makeWordSet() {
969    return mMemoizer.memoize(createName("word"));
[4671]970}
971
[4829]972Name * RE_Parser::createName(std::string && value) {
[4819]973    auto key = std::make_pair("", value);
974    auto f = mNameMap.find(key);
975    if (f != mNameMap.end()) {
976        return f->second;
977    }
[4829]978    Name * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
[4819]979    mNameMap.insert(std::make_pair(std::move(key), property));
980    return property;
[4671]981}
[4819]982
[4829]983Name * RE_Parser::createName(std::string && prop, std::string && value) {
[4819]984    auto key = std::make_pair(prop, value);
985    auto f = mNameMap.find(key);
986    if (f != mNameMap.end()) {
987        return f->second;
988    }
[4829]989    Name * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
[4819]990    mNameMap.insert(std::make_pair(std::move(key), property));
991    return property;
992}
993
994}
Note: See TracBrowser for help on using the repository browser.