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

Last change on this file since 5934 was 5880, checked in by cameron, 16 months ago

Grapheme cluster support: represent B{g} using Seq{} - b{g}; parser cleanups

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