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

Last change on this file since 5816 was 5816, checked in by cameron, 19 months ago

Supporting multiple alphabets in RE compilation - initial check-in

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