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

Last change on this file since 4939 was 4939, checked in by lindanl, 3 years ago

new version using the kernels.

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