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

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

Back up check in. Memory leaks should be fixed.

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