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

Last change on this file was 5835, checked in by nmedfort, 5 weeks ago

Revised RE_Minimizer to use alphabets + minor optimizations to RE functions

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