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

Last change on this file since 4904 was 4904, checked in by cameron, 3 years ago

Refactoring progress towards layered kernels

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