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

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

First attempt at adding grapheme cluster mode to icgrep.

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