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

Last change on this file since 5787 was 5787, checked in by cameron, 11 months ago

RE parser restructuring; parsing symbolic ranges, collation and equivalence exprs

File size: 32.0 KB
Line 
1/*
2 *  Copyright (c) 2017 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_parser_helper.h>
9#include <re/re_parser_pcre.h>
10#include <re/re_parser_ere.h>
11#include <re/re_parser_bre.h>
12#include <re/re_parser_prosite.h>
13#include <re/parse_fixed_strings.h>
14#include <re/re_name.h>
15#include <re/re_alt.h>
16#include <re/re_any.h>
17#include <re/re_end.h>
18#include <re/re_rep.h>
19#include <re/re_seq.h>
20#include <re/re_start.h>
21#include <re/re_range.h>
22#include <re/re_diff.h>
23#include <re/re_intersect.h>
24#include <re/re_group.h>
25#include <re/re_assertion.h>
26#include <re/printer_re.h>
27#include <sstream>
28#include <string>
29#include <algorithm>
30#include <iostream>
31#include <llvm/Support/Casting.h>
32#include <llvm/Support/ErrorHandling.h>
33#include <llvm/Support/raw_ostream.h>
34#include <llvm/ADT/STLExtras.h> // for make_unique
35
36using namespace llvm;
37
38namespace re {
39
40
41RE * RE_Parser::parse(const std::string & regular_expression, ModeFlagSet initialFlags, RE_Syntax syntax, bool ByteMode) {
42
43    std::unique_ptr<RE_Parser> parser = nullptr;
44    switch (syntax) {
45        case RE_Syntax::PCRE:
46            parser = make_unique<RE_Parser_PCRE>(regular_expression);
47            break;
48        case RE_Syntax::ERE:
49            parser = make_unique<RE_Parser_ERE>(regular_expression);
50            break;
51        case RE_Syntax ::BRE:
52            parser = make_unique<RE_Parser_BRE>(regular_expression);
53            break;
54        case RE_Syntax ::PROSITE:
55            parser = make_unique<RE_Parser_PROSITE>(regular_expression);
56            break;
57        default:
58            parser = make_unique<FixedStringParser>(regular_expression);
59            break;
60    }
61    parser->fByteMode = ByteMode;
62    parser->fModeFlagSet = initialFlags;
63    parser->mGroupsOpen = 0;
64    parser->fNested = false;
65    parser->mCaptureGroupCount = 0;
66    RE * re = parser->parse_RE();
67    if (re == nullptr) {
68        ParseFailure("An unexpected parsing error occurred!");
69    }
70    return re;
71}
72
73RE_Parser::RE_Parser(const std::string & regular_expression)
74: fByteMode(false)
75, fModeFlagSet(MULTILINE_MODE_FLAG)
76, fNested(false)
77, mGroupsOpen(0)
78, fSupportNonCaptureGroup(false)
79, mCursor(regular_expression)
80, mCaptureGroupCount(0)
81, mReSyntax(RE_Syntax::PCRE)
82{
83
84}
85
86RE * makeAtomicGroup(RE * r) {
87    RE_Parser::ParseFailure("Atomic grouping not supported.");
88}
89
90RE * makeBranchResetGroup(RE * r) {
91    // Branch reset groups only affect submatch numbering, but
92    // this has no effect in icgrep.
93    return r;
94}
95
96RE * RE_Parser::parse_RE() {
97    return parse_alt();
98}
99
100RE * RE_Parser::parse_alt() {
101    std::vector<RE *> alt;
102    do {
103        alt.push_back(parse_seq());
104    }
105    while (accept('|'));
106    return makeAlt(alt.begin(), alt.end());
107}
108   
109RE * RE_Parser::parse_seq() {
110    std::vector<RE *> seq;
111    if (!mCursor.more() || (*mCursor == '|') || ((mGroupsOpen > 0) && (*mCursor == ')'))) return makeSeq();
112    for (;;) {
113        RE * re = parse_next_item();
114        if (re == nullptr) {
115            break;
116        }
117        re = extend_item(re);
118        seq.push_back(re);
119    }
120    return makeSeq(seq.begin(), seq.end());
121}
122
123RE * createStart(ModeFlagSet flags) {
124    if ((flags && ModeFlagType::MULTILINE_MODE_FLAG) == 0) return makeZeroWidth("^s");  //single-line mode
125    if ((flags & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
126        return makeNegativeLookBehindAssertion(makeByte(makeCC(makeCC(0, '\n'-1), makeCC('\n'+1, 0xFF))));
127    }
128    return makeStart();
129}
130RE * createEnd(ModeFlagSet flags) {
131    if ((flags && ModeFlagType::MULTILINE_MODE_FLAG) == 0) return makeZeroWidth("$s");  //single-line mode
132    if ((flags & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
133        return makeNegativeLookAheadAssertion(makeByte(makeCC(makeCC(0, '\n'-1), makeCC('\n'+1, 0xFF))));
134    }
135    return makeEnd();
136}
137RE * createAny(ModeFlagSet flags) {
138    return makeAny();
139}
140   
141   
142RE * RE_Parser::parse_next_item() {
143    if (mCursor.noMore() || atany("*?+{|")) return nullptr;
144    else if (((mGroupsOpen > 0) && at(')')) || (fNested && at('}'))) return nullptr;
145    else if (accept('^')) return createStart(fModeFlagSet);
146    else if (accept('$')) return createEnd(fModeFlagSet);
147    else if (accept('.')) return createAny(fModeFlagSet);
148    else if (accept('(')) return parse_group();
149    else if (accept('[')) return parse_extended_bracket_expression();
150    else if (accept('\\')) return parse_escaped();
151    else return createCC(parse_literal_codepoint());
152}
153                                                         
154
155// Parse some kind of parenthesized group.  Input precondition: mCursor
156// after the (
157RE * RE_Parser::parse_group() {
158    const ModeFlagSet savedModeFlagSet = fModeFlagSet;
159    mGroupsOpen++;
160    RE * group_expr = nullptr;
161    if (*mCursor == '?' && fSupportNonCaptureGroup) {
162        switch (*++mCursor) {
163            case '#'// comment
164                while (*++mCursor != ')');
165                ++mCursor;
166                return parse_next_item();
167            case ':':  // Non-capturing paren
168                ++mCursor;
169                group_expr = parse_alt();
170                break;
171            case '=':
172                ++mCursor;
173                group_expr = makeLookAheadAssertion(parse_alt());
174                break;
175            case '!':
176                ++mCursor;
177                group_expr = makeNegativeLookAheadAssertion(parse_alt());
178                break;
179            case '>':
180                ++mCursor;
181                group_expr = makeAtomicGroup(parse_alt());
182                break;
183            case '|':
184                ++mCursor;
185                group_expr = makeBranchResetGroup(parse_alt());
186                break;
187            case '<':
188                ++mCursor;
189                if (*mCursor == '=') {
190                    ++mCursor;
191                    group_expr = makeLookBehindAssertion(parse_alt());
192                }
193                else if (*mCursor == '!') {
194                    ++mCursor;
195                    group_expr = makeNegativeLookBehindAssertion(parse_alt());
196                } else {
197                    ParseFailure("Illegal lookbehind assertion syntax.");
198                }
199                break;
200            case '-': case 'd' : case 'i': case 'm': case 's': case 'x': case 'g':
201                while (*mCursor != ')' && *mCursor != ':') {
202                    bool negateMode = false;
203                    ModeFlagType modeBit;
204                    if (*mCursor == '-') {
205                        negateMode = true;
206                        ++mCursor;
207                    }
208                    switch (*mCursor) {
209                        case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
210                        case 'g': modeBit = GRAPHEME_CLUSTER_MODE; break;
211                        case 'm': modeBit = MULTILINE_MODE_FLAG; break;
212                        //case 's': modeBit = DOTALL_MODE_FLAG; break;
213                        case 'x': modeBit = IGNORE_SPACE_MODE_FLAG; break;
214                        case 'd': modeBit = UNIX_LINES_MODE_FLAG; break;
215                        default: ParseFailure("Unsupported mode flag.");
216                    }
217                    ++mCursor;
218                    if (negateMode) {
219                        fModeFlagSet &= ~modeBit;
220                        negateMode = false;  // for next flag
221                    } else {
222                        fModeFlagSet |= modeBit;
223                    }
224                }
225                if (*mCursor == ':') {
226                    ++mCursor;
227                    group_expr = parse_alt();
228                    auto changed = fModeFlagSet ^ savedModeFlagSet;
229                    if ((changed & CASE_INSENSITIVE_MODE_FLAG) != 0) {
230                        group_expr = makeGroup(Group::Mode::CaseInsensitiveMode, group_expr,
231                                               (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) == 0 ? Group::Sense::Off : Group::Sense::On);
232                    }
233                    if ((changed & GRAPHEME_CLUSTER_MODE) != 0) {
234                        group_expr = makeGroup(Group::Mode::GraphemeMode, group_expr,
235                                               (fModeFlagSet & GRAPHEME_CLUSTER_MODE) == 0 ? Group::Sense::Off : Group::Sense::On);
236                    }
237                    fModeFlagSet = savedModeFlagSet;
238                    break;
239                } else {  // if *_cursor == ')'
240                    ++mCursor;
241                    auto changed = fModeFlagSet ^ savedModeFlagSet;
242                    if ((changed & (CASE_INSENSITIVE_MODE_FLAG|GRAPHEME_CLUSTER_MODE)) != 0) {
243                        group_expr = parse_seq();
244                        if ((changed & CASE_INSENSITIVE_MODE_FLAG) != 0) {
245                            group_expr = makeGroup(Group::Mode::CaseInsensitiveMode, group_expr,
246                                                   (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) == 0 ? Group::Sense::Off : Group::Sense::On);
247                        }
248                        if ((changed & GRAPHEME_CLUSTER_MODE) != 0) {
249                            group_expr = makeGroup(Group::Mode::GraphemeMode, group_expr,
250                                                   (fModeFlagSet & GRAPHEME_CLUSTER_MODE) == 0 ? Group::Sense::Off : Group::Sense::On);
251                        }
252                        return group_expr;
253                    }
254                    else return parse_next_item();
255                }
256            default:
257                ParseFailure("Illegal (? syntax.");
258        }
259    } else { // Capturing paren group.
260        RE * captured = parse_alt();
261        mCaptureGroupCount++;
262        std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
263        Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
264        auto key = std::make_pair("", captureName);
265        mNameMap.insert(std::make_pair(std::move(key), capture));
266        group_expr = capture;
267    }
268    if (*mCursor != ')') {
269        ParseFailure("Closing parenthesis required.");
270    }
271    mGroupsOpen--;
272    ++mCursor;
273    return group_expr;
274}
275
276// TODO: Set ENABLE_EXTENDED_QUANTIFIERS false for ERE, BRE
277#define ENABLE_EXTENDED_QUANTIFIERS true
278   
279// Extend a RE item with one or more quantifiers
280RE * RE_Parser::extend_item(RE * re) {
281    int lb, ub;
282    if (accept('*')) {lb = 0; ub = Rep::UNBOUNDED_REP;}
283    else if (accept('?')) {lb = 0; ub = 1;}
284    else if (accept('+')) {lb = 1; ub = Rep::UNBOUNDED_REP;}
285    else if (accept('{')) std::tie(lb, ub) = parse_range_bound();
286    else {
287        // No quantifier found.
288        return re;
289    }
290    if (ENABLE_EXTENDED_QUANTIFIERS && accept('?')) {
291        // Non-greedy qualifier: no difference for Parabix RE matching
292        re = makeRep(re, lb, ub);
293    } else if (ENABLE_EXTENDED_QUANTIFIERS && accept('+')) {
294        // Possessive qualifier
295        if (ub == Rep::UNBOUNDED_REP) {
296            re = makeSeq({makeRep(re, lb, ub), makeNegativeLookAheadAssertion(re)});
297        } else if (lb == ub) {
298            re = makeRep(re, ub, ub);
299        } else /* if (lb < ub) */{
300            re = makeAlt({makeSeq({makeRep(re, lb, ub-1), makeNegativeLookAheadAssertion(re)}), makeRep(re, ub, ub)});
301        }
302    } else {
303        re = makeRep(re, lb, ub);
304    }
305    // The quantified expression may be extended with a further quantifier, e,g., [a-z]{6,7}{2,3}
306    return extend_item(re);
307}
308
309std::pair<int, int> RE_Parser::parse_range_bound() {
310    int lb, ub;
311    if (accept(',')) {
312        lb = 0;
313        ub = parse_int();
314    } else {
315        lb = parse_int();
316        if (accept('}')) return std::make_pair(lb, lb);
317        if (!accept(',')) ParseFailure("Expecting , or }");
318        if (accept('}')) return std::make_pair(lb, Rep::UNBOUNDED_REP);
319        ub = parse_int();
320        if (ub < lb) ParseFailure("Upper bound less than lower bound");
321    }
322    if (accept('}')) return std::make_pair(lb, ub);
323    else ParseFailure("Expecting }");
324}
325
326unsigned RE_Parser::parse_int() {
327    unsigned value = 0;
328    while (isdigit(*mCursor)) {
329        value *= 10;
330        value += static_cast<int>(*mCursor++) - 48;
331    }
332    return value;
333}
334
335
336const uint64_t setEscapeCharacters = bit3C('b') | bit3C('p') | bit3C('q') | bit3C('d') | bit3C('w') | bit3C('s') | bit3C('<') | bit3C('>') |
337                                     bit3C('B') | bit3C('P') | bit3C('Q') | bit3C('D') | bit3C('W') | bit3C('S') | bit3C('N') | bit3C('X');
338
339bool RE_Parser::isSetEscapeChar(char c) {
340    return c >= 0x3C && c <= 0x7B && ((setEscapeCharacters >> (c - 0x3C)) & 1) == 1;
341}
342                                 
343
344RE * RE_Parser::parse_escaped() {
345   
346    if (isSetEscapeChar(*mCursor)) {
347        return parseEscapedSet();
348    }
349    else if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) {
350        codepoint_t cp = parse_escaped_codepoint();
351        if ((cp >= 0x80) && (cp <= 0xFF)) {
352            return makeByte(makeCC(cp));
353        }
354        else return createCC(cp);
355    }
356    else if (isdigit(*mCursor)) {
357        mCursor++;
358        std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
359        auto key = std::make_pair("", backref);
360        auto f = mNameMap.find(key);
361        if (f != mNameMap.end()) {
362            return makeReference(backref, f->second);
363        }
364        else {
365            ParseFailure("Back reference " + backref + " without prior capture group.");
366        }
367    }
368    else {
369        return createCC(parse_escaped_codepoint());
370    }
371}
372   
373RE * RE_Parser::parseEscapedSet() {
374    bool complemented = false;
375    RE * re = nullptr;
376    switch (*mCursor) {
377        case 'B': complemented = true;
378        case 'b':
379            if (*++mCursor != '{') {
380                return complemented ? makeWordNonBoundary() : makeWordBoundary();
381            } else {
382                ++mCursor;
383                if (isCharAhead('}')) {
384                    switch (*mCursor) {
385                        case 'g':
386                            re = complemented ? makeZeroWidth("\\B{g}") : makeZeroWidth("\\b{g}");
387                            ++mCursor;
388                            ++mCursor;
389                            break;
390                        case 'w': ParseFailure("\\b{w} not yet supported.");
391                        case 'l': ParseFailure("\\b{l} not yet supported.");
392                        case 's': ParseFailure("\\b{s} not yet supported.");
393//                        default: ParseFailure("Unrecognized boundary assertion");
394                    }
395                }
396                if (!re) {
397                    auto propExpr = parsePropertyExpression();
398                    if (*mCursor++ != '}') {
399                        ParseFailure("Malformed boundary assertion");
400                    }
401                    re = complemented ? makeReNonBoundary(propExpr) : makeReBoundary(propExpr);
402                }
403                return re;
404            }
405        case 'd':
406            ++mCursor;
407            return makeDigitSet();
408        case 'D':
409            ++mCursor;
410            return makeComplement(makeDigitSet());
411        case 's':
412            ++mCursor;
413            return makeWhitespaceSet();
414        case 'S':
415            ++mCursor;
416            return makeComplement(makeWhitespaceSet());
417        case 'w':
418            ++mCursor;
419            return makeWordSet();
420        case 'W':
421            ++mCursor;
422            return makeComplement(makeWordSet());
423        case 'Q':
424            complemented = true;
425        case 'q':
426            if (*++mCursor != '{') {
427                ParseFailure("Malformed grapheme cluster expression");
428            }
429            ++mCursor;
430            ParseFailure("Literal grapheme cluster expressions not yet supported.");
431            if (*mCursor != '}') {
432                ParseFailure("Malformed grapheme cluster expression");
433            }
434            ++mCursor;
435            return complemented ? makeComplement(re) : re;
436        case 'P':
437            complemented = true;
438        case 'p':
439            if (*++mCursor != '{') {
440                ParseFailure("Malformed property expression");
441            }
442            ++mCursor;
443            re = parsePropertyExpression();
444            if (*mCursor != '}') {
445                ParseFailure("Malformed property expression");
446            }
447            ++mCursor;
448            return complemented ? makeComplement(re) : re;
449        case 'X':
450            // \X is equivalent to ".+?\b{g}"; proceed the minimal number of characters (but at least one)
451            // to get to the next extended grapheme cluster boundary.
452            ++mCursor;
453            return makeSeq({makeAny(), makeRep(makeSeq({makeZeroWidth("\\B{g}"), makeAny()}), 0, Rep::UNBOUNDED_REP), makeZeroWidth("\\b{g}")});
454        case 'N':
455            ++mCursor;
456            re = parseNamePatternExpression();
457            assert (re);
458            return re;
459        case '<':
460            ++mCursor;
461            return makeWordBegin();
462        case '>':
463            ++mCursor;
464            return makeWordEnd();
465        default:
466            ParseFailure("Internal error");
467    }
468}
469   
470void InvalidUTF8Encoding() {
471    RE_Parser::ParseFailure("Invalid UTF-8 encoding!");
472}
473
474codepoint_t RE_Parser::parse_literal_codepoint() {
475    if (fByteMode) {
476       return static_cast<uint8_t>(*mCursor++);
477    }
478    else return parse_utf8_codepoint();
479}
480
481codepoint_t RE_Parser::parse_utf8_codepoint() {
482    // Must cast to unsigned char to avoid sign extension.
483    unsigned char pfx = static_cast<unsigned char>(*mCursor++);
484    codepoint_t cp = pfx;
485    if (pfx < 0x80) return cp;
486    unsigned suffix_bytes = 0;
487    if (pfx < 0xE0) {
488        if (pfx < 0xC2) {  // bare suffix or illegal prefix 0xC0 or 0xC2
489            InvalidUTF8Encoding();
490        }
491        suffix_bytes = 1;
492        cp &= 0x1F;
493    } else if (pfx < 0xF0) { // [0xE0, 0xEF]
494        cp &= 0x0F;
495        suffix_bytes = 2;
496    } else { // [0xF0, 0xFF]
497        cp &= 0x0F;
498        suffix_bytes = 3;
499    }
500    while (suffix_bytes--) {
501        if (mCursor.noMore()) {
502            InvalidUTF8Encoding();
503        }
504        char_t sfx = *mCursor++;
505        if ((sfx & 0xC0) != 0x80) {
506            InvalidUTF8Encoding();
507        }
508        cp = (cp << 6) | (sfx & 0x3F);
509    }
510    // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
511    // or a 4-byte sequence is used to encode a codepoint < 0x10000.
512    if ((pfx == 0xE0 && cp < 0x800) || (pfx == 0xF0 && cp < 0x10000)) {
513        InvalidUTF8Encoding();
514    }
515    // It is an error if a 4-byte sequence is used to encode a codepoint
516    // above the Unicode maximum.
517    if (cp > UCD::UNICODE_MAX) {
518        InvalidUTF8Encoding();
519    }
520    return cp;
521}
522
523std::string RE_Parser::canonicalize(const cursor_t begin, const cursor_t end) {
524    std::locale loc;
525    std::stringstream s;   
526    for (auto i = begin; i != end; ++i) {
527        switch (*i) {
528            case '_': case ' ': case '-':
529                break;
530            default:
531                s << std::tolower(*i, loc);
532        }
533    }
534    return s.str();
535}
536
537bool RE_Parser::isCharAhead(char c) {
538    if (mCursor.remaining() < 2) {
539        return false;
540    }
541    auto nextCursor = mCursor.pos() + 1;
542    return *nextCursor == c;
543}
544
545RE * RE_Parser::parsePropertyExpression() {
546    const auto start = mCursor.pos();
547    while (mCursor.more()) {
548        bool done = false;
549        switch (*mCursor) {
550            case '}': case ':': case '=':
551                done = true;
552        }
553        if (done) {
554            break;
555        }
556        ++mCursor;
557    }
558    if (*mCursor == '=') {
559        // We have a property-name = value expression
560        const auto prop_end = mCursor.pos();
561        mCursor++;
562        auto val_start = mCursor.pos();
563        if (*val_start == '/') {
564            // property-value is another regex
565            auto previous = val_start;
566            auto current = (++mCursor).pos();
567            val_start = current;
568           
569            while (true) {
570                if (*current == '/' && *previous != '\\') {
571                    break;
572                }
573               
574                if (!mCursor.more()) {
575                    ParseFailure("Malformed property expression");
576                }
577               
578                previous = current;
579                current = (++mCursor).pos();
580            }
581            ++mCursor;
582            //return parseRegexPropertyValue(canonicalize(start, prop_end), std::string(val_start, current));
583            return createName(canonicalize(start, prop_end), std::string(val_start-1, current));
584        }
585        if (*val_start == '@') {
586            // property-value is @property@ or @identity@
587            auto previous = val_start;
588            auto current = (++mCursor).pos();
589            val_start = current;
590           
591            while (true) {
592                if (*current == '@' && *previous != '\\') {
593                    break;
594                }
595               
596                if (!mCursor.more()) {
597                    ParseFailure("Malformed property expression");
598                }
599               
600                previous = current;
601                current = (++mCursor).pos();
602            }
603            ++mCursor;
604            //return parseRegexPropertyValue(canonicalize(start, prop_end), std::string(val_start, current));
605            return createName(canonicalize(start, prop_end), std::string(val_start-1, current));
606        }
607        else {
608            // property-value is normal string
609            while (mCursor.more()) {
610                bool done = false;
611                switch (*mCursor) {
612                    case '}': case ':':
613                        done = true;
614                }
615                if (done) {
616                    break;
617                }
618                ++mCursor;
619            }
620            return createName(canonicalize(start, prop_end), std::string(val_start, mCursor.pos()));
621        }
622    }
623    return createName(canonicalize(start, mCursor.pos()));
624}
625
626Name * RE_Parser::parseNamePatternExpression(){
627
628    if (!accept('{')) ParseFailure("Expecting { after \\N");
629    const auto start = mCursor.pos();
630    while (mCursor.more()) {
631        if (*mCursor == '\\') {
632            ++mCursor;
633            if (!mCursor.more()) {
634                break;
635            }
636        }
637        else if (*mCursor == '}') {
638            break;
639        }
640        ++mCursor;
641    }
642    std::string nameRegexp = "/(?i)" + std::string(start, mCursor.pos());
643    if (!accept('}')) ParseFailure("Expecting } after \\N{...");
644    return createName("na", nameRegexp);
645}
646
647
648// Parse a bracketted expression with possible && (intersection) or
649// -- (set difference) operators.
650// Initially, the opening bracket has been consumed.
651RE * RE_Parser::parse_extended_bracket_expression () {
652    bool negated = accept('^');
653    RE * t1 = parse_bracketed_items();
654    bool have_new_expr = true;
655    while (have_new_expr) {
656        if (accept("&&")) {
657            RE * t2 = parse_bracketed_items();
658            t1 = makeIntersect(t1, t2);
659        } else if (accept("--")) {
660            RE * t2 = parse_bracketed_items();
661            t1 = makeDiff(t1, t2);
662        }
663        else have_new_expr = false;
664    }
665    if (!accept(']')) ParseFailure("Expecting ]");
666    if (negated) return makeComplement(t1);
667    else return t1;
668}
669
670// Parsing items within a bracket expression.
671// Items represent individual characters or sets of characters.
672// Ranges may be formed by individual character items separated by '-'.
673RE * RE_Parser::parse_bracketed_items () {
674    std::vector<RE *> items;
675    do {
676        if (accept('[')) {
677            if (accept('=')) items.push_back(parse_equivalence_class());
678            else if (accept('.')) items.push_back(range_extend(parse_collation_element()));
679            else if (accept(':')) items.push_back(parse_Posix_class());
680            else items.push_back(parse_extended_bracket_expression());
681        } else if (accept('\\')) {
682            if (at('N') || !isSetEscapeChar(*mCursor)) items.push_back(range_extend(parse_escaped_char_item()));
683            else items.push_back(parseEscapedSet());
684        } else {
685            items.push_back(range_extend(makeCC(parse_literal_codepoint())));
686        }
687    } while (mCursor.more() && !at(']') && !at("&&") && (!at("--") || at("--]")));
688    return makeAlt(items.begin(), items.end());
689}
690
691//  Given an individual character expression, check for and parse
692//  a range extension if one exists, or return the individual expression.
693RE * RE_Parser::range_extend(RE * char_expr1) {
694    // A range extension is signalled by a hyphen '-', except for special cases:
695    // (a) if the following character is "]" the hyphen is a literal set character.
696    // (b) if the following character is "-" the hyphen is part of a set subtract
697    // operator, unless it the set is immediately closed by "--]".
698    if (!at('-') || at("-]") || (at("--") && !at("--]"))) return char_expr1;
699    accept('-');
700    RE * char_expr2 = nullptr;
701    if (accept('\\')) char_expr2 = parse_escaped_char_item();
702    else if (accept('[')) {
703        if (accept('.')) char_expr2 = parse_collation_element();
704        else ParseFailure("Error in range expression");
705    } else {
706        char_expr2 = makeCC(parse_literal_codepoint());
707    }
708    return makeRange(char_expr1, char_expr2);
709}
710
711RE * RE_Parser::parse_equivalence_class() {
712    const auto start = mCursor.pos() - 1;
713    while (mCursor.more() && !at('=')) {
714        ++mCursor;
715    }
716    std::string name = std::string(start, mCursor.pos());
717    if (!accept("=]")) ParseFailure("Posix equivalence class improperly terminated.");
718    return createName(name);
719}
720RE * RE_Parser::parse_collation_element() {
721    const auto start = mCursor.pos() - 1;
722    while (mCursor.more() && !at('.')) {
723        ++mCursor;
724    }
725    std::string name = std::string(start, mCursor.pos());
726    if (!accept(".]")) ParseFailure("Posix equivalence class improperly terminated.");
727    return createName(name);
728}
729
730RE * RE_Parser::parse_Posix_class() {
731    bool negated = accept('^');
732    RE * posixSet = parsePropertyExpression();
733    if (!accept(":]")) ParseFailure("Posix set expression improperly terminated.");
734    if (negated) return makeComplement(posixSet);
735    else return posixSet;
736}
737
738RE * RE_Parser::parse_escaped_char_item() {
739    if (accept('N')) return parseNamePatternExpression();
740    else return makeCC(parse_escaped_codepoint());
741}
742
743
744// A backslash escape was found, and various special cases (back reference,
745// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
746// cluster \X have been ruled out.
747// It may be one of several possibilities or an error sequence.
748// 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
749// 2. General control codes c[@-_a-z?]
750// 3. Restricted octal notation 0 - 0777
751// 4. General octal notation o\{[0-7]+\}
752// 5. General hex notation x\{[0-9A-Fa-f]+\}
753// 6. An error for any unrecognized alphabetic escape
754// 7. An escaped ASCII symbol, standing for itself
755
756codepoint_t RE_Parser::parse_escaped_codepoint() {
757    codepoint_t cp_value;
758    if (accept('a')) return 0x07; // BEL
759    else if (accept('e')) return 0x1B; // ESC
760    else if (accept('f')) return 0x0C; // FF
761    else if (accept('n')) return 0x0A; // LF
762    else if (accept('r')) return 0x0D; // CR
763    else if (accept('t')) return 0x09; // HT
764    else if (accept('v')) return 0x0B; // VT
765    else if (accept('c')) {// Control-escape based on next char
766            // \c@, \cA, ... \c_, or \ca, ..., \cz
767            if (((*mCursor >= '@') && (*mCursor <= '_')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))) {
768                cp_value = static_cast<codepoint_t>(*mCursor & 0x1F);
769                mCursor++;
770                return cp_value;
771            }
772            else if (accept('?')) return 0x7F;  // \c? ==> DEL
773            else ParseFailure("Illegal \\c escape sequence");
774    } else if (accept('0')) {
775        return parse_octal_codepoint(0,3);
776    } else if (accept('o')) {
777        if (!accept('{')) ParseFailure("Malformed octal escape sequence");
778        cp_value = parse_octal_codepoint(1, 7);
779        if (!accept('}')) ParseFailure("Malformed octal escape sequence");
780        return cp_value;
781    } else if (accept('x')) {
782        if (!accept('{')) return parse_hex_codepoint(1,2);  // ICU compatibility
783        cp_value = parse_hex_codepoint(1, 6);
784        if (!accept('}')) ParseFailure("Malformed hex escape sequence");
785        return cp_value;
786    } else if (accept('u')) {
787        if (!accept('{')) return parse_hex_codepoint(4,4);  // ICU compatibility
788        cp_value = parse_hex_codepoint(1, 6);
789        if (!accept('}')) ParseFailure("Malformed hex escape sequence");
790        return cp_value;
791    } else if (accept('U')) {
792        return parse_hex_codepoint(8,8);  // ICU compatibility
793    } else {
794        if (((*mCursor >= 'A') && (*mCursor <= 'Z')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))){
795            //Escape unknown letter will be parse as normal letter
796            return parse_literal_codepoint();
797            //ParseFailure("Undefined or unsupported escape sequence");
798        }
799        else if ((*mCursor < 0x20) || (*mCursor >= 0x7F))
800            ParseFailure("Illegal escape sequence");
801        else return static_cast<codepoint_t>(*mCursor++);
802    }
803}
804
805codepoint_t RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
806    codepoint_t value = 0;
807    int count = 0;
808    while (mCursor.more() && count < maxdigits) {
809        const char t = *mCursor;
810        if (t < '0' || t > '7') {
811            break;
812        }
813        value = value * 8 | (t - '0');
814        ++mCursor;
815        ++count;
816    }
817    if (count < mindigits) ParseFailure("Octal sequence has too few digits");
818    if (value > UCD::UNICODE_MAX) ParseFailure("Octal value too large");
819    return value;
820}
821
822codepoint_t RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
823    codepoint_t value = 0;
824    int count = 0;
825    while (mCursor.more() && isxdigit(*mCursor) && count < maxdigits) {
826        const char t = *mCursor;
827        if (isdigit(t)) {
828            value = (value * 16) | (t - '0');
829        }
830        else {
831            value = ((value * 16) | ((t | 32) - 'a')) + 10;
832        }
833        ++mCursor;
834        ++count;
835    }
836    if (count < mindigits) ParseFailure("Hexadecimal sequence has too few digits");
837    if (value > UCD::UNICODE_MAX) ParseFailure("Hexadecimal value too large");
838    return value;
839}
840
841Name * RE_Parser::createCC(const codepoint_t cp) {
842    CC * cc = makeCC(cp);
843    return mMemoizer.memoize(cc);
844}
845
846void RE_Parser::insert(CC * cc, const codepoint_t cp) {
847    cc->insert(cp);
848}
849
850void RE_Parser::insert_range(CC * cc, const codepoint_t lo, const codepoint_t hi) {
851    cc->insert_range(lo, hi);
852}
853
854RE * RE_Parser::makeComplement(RE * s) {
855  return makeDiff(makeAny(), s);
856}
857
858           
859
860                           
861RE * RE_Parser::makeWordBoundary() {
862    Name * wordC = makeWordSet();
863    return makeReBoundary(wordC);
864}
865
866RE * RE_Parser::makeWordNonBoundary() {
867    Name * wordC = makeWordSet();
868    return makeReNonBoundary(wordC);
869}
870
871inline RE * RE_Parser::makeReBoundary(RE * re) {
872    return makeBoundaryAssertion(re);
873}
874inline RE * RE_Parser::makeReNonBoundary(RE * re) {
875    return makeNegativeBoundaryAssertion(re);
876}
877
878RE * RE_Parser::makeWordBegin() {
879    Name * wordC = makeWordSet();
880    return makeNegativeLookBehindAssertion(wordC);
881}
882
883RE * RE_Parser::makeWordEnd() {
884    Name * wordC = makeWordSet();
885    return makeNegativeLookAheadAssertion(wordC);
886}
887
888Name * RE_Parser::makeDigitSet() {
889    return mMemoizer.memoize(createName("nd"));
890}
891
892Name * RE_Parser::makeAlphaNumeric() {
893    return mMemoizer.memoize(createName("alnum"));
894}
895
896Name * RE_Parser::makeWhitespaceSet() {
897    return mMemoizer.memoize(createName("whitespace"));
898}
899
900Name * RE_Parser::makeWordSet() {
901    return mMemoizer.memoize(createName("word"));
902}
903
904Name * RE_Parser::createName(std::string value) {
905    auto key = std::make_pair("", value);
906    auto f = mNameMap.find(key);
907    if (f != mNameMap.end()) {
908        return f->second;
909    }
910    Name * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
911    mNameMap.insert(std::make_pair(std::move(key), property));
912    return property;
913    }
914
915Name * RE_Parser::createName(std::string prop, std::string value) {
916    auto key = std::make_pair(prop, value);
917    auto f = mNameMap.find(key);
918    if (f != mNameMap.end()) {
919        return f->second;
920    }
921    Name * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
922    mNameMap.insert(std::make_pair(std::move(key), property));
923    return property;
924}
925
926LLVM_ATTRIBUTE_NORETURN void RE_Parser::ParseFailure(std::string errmsg) {
927    llvm::report_fatal_error(errmsg);
928}
929
930}
Note: See TracBrowser for help on using the repository browser.