source: icGREP/icgrep-devel/icgrep/re/parsers/parser.cpp @ 6169

Last change on this file since 6169 was 6169, checked in by cameron, 8 months ago

-K flag for compatibility mode

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