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

Last change on this file since 5770 was 5770, checked in by cameron, 17 months ago

Restructure to eliminate unnecessary dependencies on RegExpCompiler? and UCDLIB

File size: 39.5 KB
Line 
1/*
2 *  Copyright (c) 2017 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include <re/re_parser.h>
8#include <re/re_parser_helper.h>
9#include <re/re_parser_pcre.h>
10#include <re/re_parser_ere.h>
11#include <re/re_parser_bre.h>
12#include <re/re_parser_prosite.h>
13#include <re/parse_fixed_strings.h>
14#include <re/re_name.h>
15#include <re/re_alt.h>
16#include <re/re_any.h>
17#include <re/re_end.h>
18#include <re/re_rep.h>
19#include <re/re_seq.h>
20#include <re/re_start.h>
21#include <re/re_range.h>
22#include <re/re_diff.h>
23#include <re/re_intersect.h>
24#include <re/re_group.h>
25#include <re/re_assertion.h>
26#include <re/printer_re.h>
27#include <UCD/resolve_properties.h>
28#include <UCD/CaseFolding.h>
29#include <sstream>
30#include <string>
31#include <algorithm>
32#include <iostream>
33#include <llvm/Support/Casting.h>
34#include <llvm/Support/ErrorHandling.h>
35#include <llvm/Support/raw_ostream.h>
36#include <llvm/ADT/STLExtras.h> // for make_unique
37
38using namespace llvm;
39
40namespace re {
41
42
43RE * RE_Parser::parse(const std::string & regular_expression, ModeFlagSet initialFlags, RE_Syntax syntax, bool ByteMode) {
44
45    std::unique_ptr<RE_Parser> parser = nullptr;
46    switch (syntax) {
47        case RE_Syntax::PCRE:
48            parser = make_unique<RE_Parser_PCRE>(regular_expression);
49            break;
50        case RE_Syntax::ERE:
51            parser = make_unique<RE_Parser_ERE>(regular_expression);
52            break;
53        case RE_Syntax ::BRE:
54            parser = make_unique<RE_Parser_BRE>(regular_expression);
55            break;
56        case RE_Syntax ::PROSITE:
57            parser = make_unique<RE_Parser_PROSITE>(regular_expression);
58            break;
59        default:
60            parser = make_unique<FixedStringParser>(regular_expression);
61            break;
62    }
63    parser->fByteMode = ByteMode;
64    parser->fModeFlagSet = initialFlags;
65    parser->mGroupsOpen = 0;
66    parser->fNested = false;
67    parser->fGraphemeBoundaryPending = false;
68    parser->mCaptureGroupCount = 0;
69    RE * re = parser->parse_RE();
70    if (re == nullptr) {
71        ParseFailure("An unexpected parsing error occurred!");
72    }
73    return re;
74}
75
76RE_Parser::RE_Parser(const std::string & regular_expression)
77: fByteMode(false)
78, fModeFlagSet(0)
79, fNested(false)
80, mGroupsOpen(0)
81, fGraphemeBoundaryPending(false)
82, fSupportNonCaptureGroup(false)
83, mCursor(regular_expression)
84, mCaptureGroupCount(0)
85, mReSyntax(RE_Syntax::PCRE)
86{
87
88}
89
90RE * makeAtomicGroup(RE * r) {
91    RE_Parser::ParseFailure("Atomic grouping not supported.");
92}
93
94RE * makeBranchResetGroup(RE * r) {
95    // Branch reset groups only affect submatch numbering, but
96    // this has no effect in icgrep.
97    return r;
98}
99
100RE * RE_Parser::parse_RE() {
101    return parse_alt();
102}
103
104RE * RE_Parser::parse_alt() {
105    std::vector<RE *> alt;
106    do {
107        alt.push_back(parse_seq());
108    }
109    while (accept_alt_mark());
110    return makeAlt(alt.begin(), alt.end());
111}
112   
113bool RE_Parser::accept_alt_mark() {
114    if (!mCursor.more() || (*mCursor != '|')) return false;
115    mCursor++;
116    return true;
117}
118
119RE * RE_Parser::parse_seq() {
120    std::vector<RE *> seq;
121    if (!mCursor.more() || (*mCursor == '|') || ((mGroupsOpen > 0) && (*mCursor == ')'))) return makeSeq();
122    for (;;) {
123        RE * re = parse_next_item();
124        if (re == nullptr) {
125            if (fGraphemeBoundaryPending == true) {
126                seq.push_back(makeZeroWidth("GCB"));
127                fGraphemeBoundaryPending = false;
128            }
129            break;
130        }
131        re = extend_item(re);
132        seq.push_back(re);
133    }
134    return makeSeq(seq.begin(), seq.end());
135}
136
137RE * RE_Parser::parse_next_item() {
138    RE * re = nullptr;
139    if (fModeFlagSet & IGNORE_SPACE_MODE_FLAG) {
140        while (mCursor.more() && *mCursor == ' ') {
141            ++mCursor;
142        }
143    }
144    if (mCursor.more()) {
145        switch (*mCursor) {
146            case '(':
147                ++mCursor;
148                return parse_group();
149            case '^':
150                ++mCursor;
151                if ((fModeFlagSet & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
152                    return makeNegativeLookBehindAssertion(makeByte(makeCC(makeCC(0, '\n'-1), makeCC('\n'+1, 0xFF))));
153                }
154                return makeStart();
155            case '$':
156                ++mCursor;
157                if ((fModeFlagSet & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
158                    return makeLookAheadAssertion(makeCC('\n'));
159                }
160                return makeEnd();
161            case '|':
162                break;
163            case ')':
164                if (mGroupsOpen > 0) break;
165                if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
166                    return createCC(parse_literal_codepoint());
167                }
168                ParseFailure("Use  \\) for literal ).");
169            case '*': case '+': case '?': case '{':
170                ParseFailure("Need something to repeat before *, +, ? or {.");
171            case ']':
172                if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
173                    return createCC(parse_literal_codepoint());
174                }
175                ParseFailure("Use  \\] for literal ].");
176            case '}':
177                if (fNested) {
178                    break;  //  a recursive invocation for a regexp in \N{...}
179                } else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
180                    return createCC(parse_literal_codepoint());
181                }
182                ParseFailure("Use \\} for literal }.");
183            case '[':
184                mCursor++;
185                re = parse_charset();
186                if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
187                    re = makeSeq({re, makeZeroWidth("GCB")});
188                }
189                break;
190            case '.': // the 'any' metacharacter
191                mCursor++;
192                return makeAny();
193            case '\\'// escape processing
194                ++mCursor;
195                return parse_escaped();
196            default:
197                re = createCC(parse_literal_codepoint());
198                if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
199                    fGraphemeBoundaryPending = true;
200                }
201        }
202    }
203    return re;
204}
205
206
207// Parse some kind of parenthesized group.  Input precondition: mCursor
208// after the (
209RE * RE_Parser::parse_group() {
210    const ModeFlagSet savedModeFlagSet = fModeFlagSet;
211    mGroupsOpen++;
212    RE * group_expr = nullptr;
213    if (*mCursor == '?' && fSupportNonCaptureGroup) {
214        switch (*++mCursor) {
215            case '#'// comment
216                while (*++mCursor != ')');
217                ++mCursor;
218                return parse_next_item();
219            case ':':  // Non-capturing paren
220                ++mCursor;
221                group_expr = parse_alt();
222                break;
223            case '=':
224                ++mCursor;
225                group_expr = makeLookAheadAssertion(parse_alt());
226                break;
227            case '!':
228                ++mCursor;
229                group_expr = makeNegativeLookAheadAssertion(parse_alt());
230                break;
231            case '>':
232                ++mCursor;
233                group_expr = makeAtomicGroup(parse_alt());
234                break;
235            case '|':
236                ++mCursor;
237                group_expr = makeBranchResetGroup(parse_alt());
238                break;
239            case '<':
240                ++mCursor;
241                if (*mCursor == '=') {
242                    ++mCursor;
243                    group_expr = makeLookBehindAssertion(parse_alt());
244                }
245                else if (*mCursor == '!') {
246                    ++mCursor;
247                    group_expr = makeNegativeLookBehindAssertion(parse_alt());
248                } else {
249                    ParseFailure("Illegal lookbehind assertion syntax.");
250                }
251                break;
252            case '-': case 'd' : case 'i': case 'm': case 's': case 'x': case 'g':
253                while (*mCursor != ')' && *mCursor != ':') {
254                    bool negateMode = false;
255                    ModeFlagType modeBit;
256                    if (*mCursor == '-') {
257                        negateMode = true;
258                        ++mCursor;
259                    }
260                    switch (*mCursor) {
261                        case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
262                        case 'g': modeBit = GRAPHEME_CLUSTER_MODE; break;
263                        case 'm': modeBit = MULTILINE_MODE_FLAG; break;
264                        //case 's': modeBit = DOTALL_MODE_FLAG; break;
265                        case 'x': modeBit = IGNORE_SPACE_MODE_FLAG; break;
266                        case 'd': modeBit = UNIX_LINES_MODE_FLAG; break;
267                        default: ParseFailure("Unsupported mode flag.");
268                    }
269                    ++mCursor;
270                    if (negateMode) {
271                        fModeFlagSet &= ~modeBit;
272                        negateMode = false;  // for next flag
273                    } else {
274                        fModeFlagSet |= modeBit;
275                    }
276                }
277                if (*mCursor == ':') {
278                    ++mCursor;
279                    group_expr = parse_alt();
280                    auto changed = fModeFlagSet ^ savedModeFlagSet;
281                    if ((changed & CASE_INSENSITIVE_MODE_FLAG) != 0) {
282                        group_expr = makeGroup(Group::Mode::CaseInsensitiveMode, group_expr,
283                                               (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) == 0 ? Group::Sense::Off : Group::Sense::On);
284                    }
285                    fModeFlagSet = savedModeFlagSet;
286                    break;
287                } else {  // if *_cursor == ')'
288                    ++mCursor;
289                    auto changed = fModeFlagSet ^ savedModeFlagSet;
290                    if ((changed & CASE_INSENSITIVE_MODE_FLAG) != 0) {
291                        group_expr = parse_seq();
292                        return makeGroup(Group::Mode::CaseInsensitiveMode, group_expr,
293                                               (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) == 0 ? Group::Sense::Off : Group::Sense::On);
294                    }
295                    else return parse_next_item();
296                }
297            default:
298                ParseFailure("Illegal (? syntax.");
299        }
300    } else { // Capturing paren group.
301        RE * captured = parse_alt();
302        mCaptureGroupCount++;
303        std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
304        Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
305        auto key = std::make_pair("", captureName);
306        mNameMap.insert(std::make_pair(std::move(key), capture));
307        group_expr = capture;
308    }
309    if (*mCursor != ')') {
310        ParseFailure("Closing parenthesis required.");
311    }
312    mGroupsOpen--;
313    ++mCursor;
314    return group_expr;
315}
316
317// TODO: Set ENABLE_EXTENDED_QUANTIFIERS false for ERE, BRE
318#define ENABLE_EXTENDED_QUANTIFIERS true
319   
320// Extend a RE item with one or more quantifiers
321RE * RE_Parser::extend_item(RE * re) {
322    if (LLVM_UNLIKELY(!(mCursor.more()))) return re;
323    int lb = 0, ub = 0;
324    switch (*mCursor) {
325        case '*':
326            lb = 0;
327            ub = Rep::UNBOUNDED_REP;
328            break;
329        case '?':
330            lb = 0;
331            ub = 1;
332            break;
333        case '+':
334            lb = 1;
335            ub = Rep::UNBOUNDED_REP;
336            break;
337        case '{':
338            std::tie(lb, ub) = parse_range_bound();
339            if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
340                ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
341            }
342            break;
343        default:
344            // No quantifiers
345            return re;
346    }
347    ++mCursor;
348    if (ENABLE_EXTENDED_QUANTIFIERS) {
349        if (LLVM_UNLIKELY(!(mCursor.more()))) return makeRep(re, lb, ub);;
350        if (*mCursor == '?') { // Non-greedy qualifier
351            // Greedy vs. non-greedy makes no difference for icgrep.
352            ++mCursor;
353            re = makeRep(re, lb, ub);
354        } else if (*mCursor == '+') {
355            ++mCursor;
356            if (ub == Rep::UNBOUNDED_REP) {
357                re = makeSeq({makeRep(re, lb, ub), makeNegativeLookAheadAssertion(re)});
358            } else if (lb == ub) {
359                re = makeRep(re, ub, ub);
360            } else /* if (lb < ub) */{
361                re = makeAlt({makeSeq({makeRep(re, lb, ub-1), makeNegativeLookAheadAssertion(re)}), makeRep(re, ub, ub)});
362            }
363        } else {
364            re = makeRep(re, lb, ub);
365        } 
366    } else {
367        re = makeRep(re, lb, ub);
368    }
369    // The quantified expression may be extended with a further quantifier, e,g., [a-z]{6,7}{2,3}
370    return extend_item(re);
371}
372
373std::pair<int, int> RE_Parser::parse_range_bound() {
374    int lower_bound = 0, upper_bound = 0;
375    if (*++mCursor != ',') {
376        lower_bound = parse_int();
377    }
378    if (*mCursor == '}') {
379        upper_bound = lower_bound;
380    } else if (*mCursor != ',') {
381        ParseFailure("Bad lower bound!");
382    } else if (*++mCursor == '}') {
383        upper_bound = Rep::UNBOUNDED_REP;
384    } else {
385        upper_bound = parse_int();
386        if (*mCursor != '}') {
387            ParseFailure("Bad upper bound!");
388        }
389    }
390    return std::make_pair(lower_bound, upper_bound);
391}
392
393unsigned RE_Parser::parse_int() {
394    unsigned value = 0;
395    while (isdigit(*mCursor)) {
396        value *= 10;
397        value += static_cast<int>(*mCursor++) - 48;
398    }
399    return value;
400}
401
402
403const uint64_t setEscapeCharacters = bit3C('b') | bit3C('p') | bit3C('q') | bit3C('d') | bit3C('w') | bit3C('s') | bit3C('<') | bit3C('>') |
404                                     bit3C('B') | bit3C('P') | bit3C('Q') | bit3C('D') | bit3C('W') | bit3C('S') | bit3C('N') | bit3C('X');
405
406bool RE_Parser::isSetEscapeChar(char c) {
407    return c >= 0x3C && c <= 0x7B && ((setEscapeCharacters >> (c - 0x3C)) & 1) == 1;
408}
409                                 
410
411RE * RE_Parser::parse_escaped() {
412   
413    if (isSetEscapeChar(*mCursor)) {
414        return parseEscapedSet();
415    }
416    else if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) {
417        codepoint_t cp = parse_escaped_codepoint();
418        if ((cp >= 0x80) && (cp <= 0xFF)) {
419            return makeByte(makeCC(cp));
420        }
421        else return createCC(cp);
422    }
423    else if (isdigit(*mCursor)) {
424        mCursor++;
425        std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
426        auto key = std::make_pair("", backref);
427        auto f = mNameMap.find(key);
428        if (f != mNameMap.end()) {
429            return makeReference(backref, f->second);
430        }
431        else {
432            ParseFailure("Back reference " + backref + " without prior capture group.");
433        }
434    }
435    else {
436        return createCC(parse_escaped_codepoint());
437    }
438}
439   
440RE * RE_Parser::parseEscapedSet() {
441    bool complemented = false;
442    RE * re = nullptr;
443    switch (*mCursor) {
444        case 'B': complemented = true;
445        case 'b':
446            if (*++mCursor != '{') {
447                return complemented ? makeWordNonBoundary() : makeWordBoundary();
448            } else {
449                ++mCursor;
450                if (isCharAhead('}')) {
451                    switch (*mCursor) {
452                        case 'g':
453                            re = complemented ? makeZeroWidth("NonGCB") : makeZeroWidth("GCB");
454                            ++mCursor;
455                            ++mCursor;
456                            break;
457                        case 'w': ParseFailure("\\b{w} not yet supported.");
458                        case 'l': ParseFailure("\\b{l} not yet supported.");
459                        case 's': ParseFailure("\\b{s} not yet supported.");
460//                        default: ParseFailure("Unrecognized boundary assertion");
461                    }
462                }
463                if (!re) {
464                    auto propExpr = parsePropertyExpression();
465                    if (*mCursor++ != '}') {
466                        ParseFailure("Malformed boundary assertion");
467                    }
468                    re = complemented ? makeReNonBoundary(propExpr) : makeReBoundary(propExpr);
469                }
470                return re;
471            }
472        case 'd':
473            ++mCursor;
474            return makeDigitSet();
475        case 'D':
476            ++mCursor;
477            return makeComplement(makeDigitSet());
478        case 's':
479            ++mCursor;
480            return makeWhitespaceSet();
481        case 'S':
482            ++mCursor;
483            return makeComplement(makeWhitespaceSet());
484        case 'w':
485            ++mCursor;
486            return makeWordSet();
487        case 'W':
488            ++mCursor;
489            return makeComplement(makeWordSet());
490        case 'Q':
491            complemented = true;
492        case 'q':
493            if (*++mCursor != '{') {
494                ParseFailure("Malformed grapheme cluster expression");
495            }
496            ++mCursor;
497            ParseFailure("Literal grapheme cluster expressions not yet supported.");
498            if (*mCursor != '}') {
499                ParseFailure("Malformed grapheme cluster expression");
500            }
501            ++mCursor;
502            return complemented ? makeComplement(re) : re;
503        case 'P':
504            complemented = true;
505        case 'p':
506            if (*++mCursor != '{') {
507                ParseFailure("Malformed property expression");
508            }
509            ++mCursor;
510            re = parsePropertyExpression();
511            if (*mCursor != '}') {
512                ParseFailure("Malformed property expression");
513            }
514            ++mCursor;
515            return complemented ? makeComplement(re) : re;
516        case 'X':
517            // \X is equivalent to ".+?\b{g}"; proceed the minimal number of characters (but at least one)
518            // to get to the next extended grapheme cluster boundary.
519            ++mCursor;
520            return makeSeq({makeAny(), makeRep(makeSeq({makeZeroWidth("NonGCB"), makeAny()}), 0, Rep::UNBOUNDED_REP), makeZeroWidth("GCB")});
521        case 'N':
522            if (*++mCursor != '{') {
523                ParseFailure("Malformed \\N expression");
524            }
525            ++mCursor;
526            re = parseNamePatternExpression();
527            if (*mCursor != '}') {
528                ParseFailure("Malformed \\N expression");
529            }
530            ++mCursor;
531            assert (re);
532            return re;
533        case '<':
534            ++mCursor;
535            return makeWordBegin();
536        case '>':
537            ++mCursor;
538            return makeWordEnd();
539        default:
540            ParseFailure("Internal error");
541    }
542}
543   
544void InvalidUTF8Encoding() {
545    RE_Parser::ParseFailure("Invalid UTF-8 encoding!");
546}
547
548codepoint_t RE_Parser::parse_literal_codepoint() {
549    if (fByteMode) {
550       return static_cast<uint8_t>(*mCursor++);
551    }
552    else return parse_utf8_codepoint();
553}
554
555codepoint_t RE_Parser::parse_utf8_codepoint() {
556    // Must cast to unsigned char to avoid sign extension.
557    unsigned char pfx = static_cast<unsigned char>(*mCursor++);
558    codepoint_t cp = pfx;
559    if (pfx < 0x80) return cp;
560    unsigned suffix_bytes = 0;
561    if (pfx < 0xE0) {
562        if (pfx < 0xC2) {  // bare suffix or illegal prefix 0xC0 or 0xC2
563            InvalidUTF8Encoding();
564        }
565        suffix_bytes = 1;
566        cp &= 0x1F;
567    } else if (pfx < 0xF0) { // [0xE0, 0xEF]
568        cp &= 0x0F;
569        suffix_bytes = 2;
570    } else { // [0xF0, 0xFF]
571        cp &= 0x0F;
572        suffix_bytes = 3;
573    }
574    while (suffix_bytes--) {
575        if (mCursor.noMore()) {
576            InvalidUTF8Encoding();
577        }
578        char_t sfx = *mCursor++;
579        if ((sfx & 0xC0) != 0x80) {
580            InvalidUTF8Encoding();
581        }
582        cp = (cp << 6) | (sfx & 0x3F);
583    }
584    // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
585    // or a 4-byte sequence is used to encode a codepoint < 0x10000.
586    if ((pfx == 0xE0 && cp < 0x800) || (pfx == 0xF0 && cp < 0x10000)) {
587        InvalidUTF8Encoding();
588    }
589    // It is an error if a 4-byte sequence is used to encode a codepoint
590    // above the Unicode maximum.
591    if (cp > UCD::UNICODE_MAX) {
592        InvalidUTF8Encoding();
593    }
594    return cp;
595}
596
597std::string RE_Parser::canonicalize(const cursor_t begin, const cursor_t end) {
598    std::locale loc;
599    std::stringstream s;   
600    for (auto i = begin; i != end; ++i) {
601        switch (*i) {
602            case '_': case ' ': case '-':
603                break;
604            default:
605                s << std::tolower(*i, loc);
606        }
607    }
608    return s.str();
609}
610
611bool RE_Parser::isCharAhead(char c) {
612    if (mCursor.remaining() < 2) {
613        return false;
614    }
615    auto nextCursor = mCursor.pos() + 1;
616    return *nextCursor == c;
617}
618
619RE * RE_Parser::parsePropertyExpression() {
620    const auto start = mCursor.pos();
621    while (mCursor.more()) {
622        bool done = false;
623        switch (*mCursor) {
624            case '}': case ':': case '=':
625                done = true;
626        }
627        if (done) {
628            break;
629        }
630        ++mCursor;
631    }
632    if (*mCursor == '=') {
633        // We have a property-name = value expression
634        const auto prop_end = mCursor.pos();
635        mCursor++;
636        auto val_start = mCursor.pos();
637        if (*val_start == '/') {
638            // property-value is another regex
639            auto previous = val_start;
640            auto current = (++mCursor).pos();
641            val_start = current;
642           
643            while (true) {
644                if (*current == '/' && *previous != '\\') {
645                    break;
646                }
647               
648                if (!mCursor.more()) {
649                    ParseFailure("Malformed property expression");
650                }
651               
652                previous = current;
653                current = (++mCursor).pos();
654            }
655            ++mCursor;
656            //return parseRegexPropertyValue(canonicalize(start, prop_end), std::string(val_start, current));
657            return createName(canonicalize(start, prop_end), std::string(val_start-1, current));
658        }
659        if (*val_start == '@') {
660            // property-value is @property@ or @identity@
661            auto previous = val_start;
662            auto current = (++mCursor).pos();
663            val_start = current;
664           
665            while (true) {
666                if (*current == '@' && *previous != '\\') {
667                    break;
668                }
669               
670                if (!mCursor.more()) {
671                    ParseFailure("Malformed property expression");
672                }
673               
674                previous = current;
675                current = (++mCursor).pos();
676            }
677            ++mCursor;
678            //return parseRegexPropertyValue(canonicalize(start, prop_end), std::string(val_start, current));
679            return createName(canonicalize(start, prop_end), std::string(val_start-1, current));
680        }
681        else {
682            // property-value is normal string
683            while (mCursor.more()) {
684                bool done = false;
685                switch (*mCursor) {
686                    case '}': case ':':
687                        done = true;
688                }
689                if (done) {
690                    break;
691                }
692                ++mCursor;
693            }
694            return createName(canonicalize(start, prop_end), std::string(val_start, mCursor.pos()));
695        }
696    }
697    return createName(canonicalize(start, mCursor.pos()));
698}
699
700Name * RE_Parser::parseNamePatternExpression(){
701
702    const auto start = mCursor.pos();
703    while (mCursor.more()) {
704        if (*mCursor == '\\') {
705            ++mCursor;
706            if (!mCursor.more()) {
707                break;
708            }
709        }
710        else if (*mCursor == '}') {
711            break;
712        }
713        ++mCursor;
714    }
715    std::string nameRegexp = "/(?i)" + std::string(start, mCursor.pos());
716    return createName("na", nameRegexp);
717}
718
719bool RE_Parser::isUnsupportChartsetOperator(char c) {
720    return false;
721}
722
723CharsetOperatorKind RE_Parser::getCharsetOperator() {
724    if (isUnsupportChartsetOperator(*mCursor)) {
725        return emptyOperator;
726    }
727    switch (*mCursor) {
728        case '&':
729            ++mCursor;
730            if (*mCursor == '&') {
731                ++mCursor;
732                return intersectOp;
733            } else if (*mCursor == '[') {
734                // Short-hand for intersectOp when a set follows
735                return intersectOp;
736            }
737            return ampChar;
738        case '-':
739            ++mCursor;
740            if (*mCursor == '-') {
741                ++mCursor;
742                return setDiffOp;
743            } else if (*mCursor == '[') {
744                return setDiffOp;
745            } else if (*mCursor == ']') {
746                return hyphenChar;
747            }
748            return rangeHyphen;
749        case '[':
750            ++mCursor;
751            if (*mCursor == ':') {
752                ++mCursor;
753                return posixPropertyOpener;
754            }
755            return setOpener;
756        case ']':
757            ++mCursor;
758            return setCloser;
759        case '\\':
760            ++mCursor;
761            return backSlash;
762        default:
763            return emptyOperator;
764    }
765}
766
767// Precondition: cursor is immediately after opening '[' character
768RE * RE_Parser::parse_charset() {
769    // Sets are accumulated using two variables:
770    // subexprs accumulates set expressions such as \p{Lu}, [\w && \p{Greek}]
771    // cc accumulates the literal and calculated codepoints and ranges
772    std::vector<RE *> subexprs;
773    CC * cc = makeCC();
774    // When the last item deal with is a single literal charcacter or calculated codepoint,
775    // a following hyphen can indicate a range.   When the last item is a set subexpression,
776    // a following hyphen can indicate set subtraction.
777    enum {NoItem, CodepointItem, RangeItem, SetItem, BrackettedSetItem} lastItemKind = NoItem;
778
779    codepoint_t lastCodepointItem = 0;
780    bool havePendingOperation = false;
781    bool possibleByteCodeEscape = false;  // set to true when \x, \o or \0 hex or octal escapes seen.
782    CharsetOperatorKind pendingOperationKind = intersectOp;
783    RE * pendingOperand = nullptr;
784
785    // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
786    bool negated = false;
787    if (*mCursor == '^') {
788        negated = true;
789        ++mCursor;
790    }
791    // Legacy rule: an unescaped ] may appear as a literal set character
792    // if and only if it appears immediately after the opening [ or [^
793    if ( *mCursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
794        insert(cc, ']');
795        lastItemKind = CodepointItem;
796        lastCodepointItem = static_cast<codepoint_t> (']');
797        ++mCursor;
798    } else if ( *mCursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
799        ++mCursor;
800        insert(cc, '-');
801        lastItemKind = CodepointItem;
802        lastCodepointItem = static_cast<codepoint_t> ('-');
803        if (*mCursor == '-') {
804            ParseFailure("Set operator has no left operand.");
805        }
806    }
807    while (mCursor.more()) {
808        const CharsetOperatorKind op = getCharsetOperator();
809        switch (op) {
810            case intersectOp:
811            case setDiffOp: {
812                if (lastItemKind == NoItem) {
813                    ParseFailure("Set operator has no left operand.");
814                }
815                if (!cc->empty()) {
816                    subexprs.push_back(mMemoizer.memoize(cc));
817                }
818                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
819                subexprs.clear();
820                cc = makeCC();
821                if (havePendingOperation) {
822                    if (pendingOperationKind == intersectOp) {
823                        pendingOperand = makeIntersect(pendingOperand, newOperand);
824                    }
825                    else {
826                        pendingOperand = makeDiff(pendingOperand, newOperand);
827                    }
828                }
829                else {
830                    pendingOperand = newOperand;
831                }
832                havePendingOperation = true;
833                pendingOperationKind = op;
834                lastItemKind = NoItem;
835            }
836            break;
837            case setCloser: {
838                if (lastItemKind == NoItem) {
839                    ParseFailure("Set operator has no right operand.");
840                }
841                if (!cc->empty()) {
842                    if (possibleByteCodeEscape && (cc->max_codepoint() <= 0xFF) && subexprs.empty() && !havePendingOperation) {
843                        subexprs.push_back(makeByte(cc));
844                    }
845                    else {
846                        subexprs.push_back(mMemoizer.memoize(cc));
847                    }
848                }
849                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
850                if (havePendingOperation) {
851                    if (pendingOperationKind == intersectOp) {
852                        newOperand = makeIntersect(pendingOperand, newOperand);
853                    }
854                    else {
855                        newOperand = makeDiff(pendingOperand, newOperand);
856                    }
857                }
858                return negated ? makeComplement(newOperand) : newOperand;
859            }
860            case setOpener:
861            case posixPropertyOpener: {
862                if (lastItemKind != NoItem) {
863                    if (!cc->empty()) {
864                        subexprs.push_back(mMemoizer.memoize(cc));
865                    }
866                    RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
867                    subexprs.clear();
868                    cc = makeCC();
869                    if (havePendingOperation) {
870                        if (pendingOperationKind == intersectOp) {
871                            pendingOperand = makeIntersect(pendingOperand, newOperand);
872                        } else {
873                            pendingOperand = makeDiff(pendingOperand, newOperand);
874                        }
875                    }
876                    else {
877                        pendingOperand = newOperand;
878                    }
879                    subexprs.push_back(pendingOperand);
880                    havePendingOperation = false;
881                }
882                if (op == setOpener) {
883                    subexprs.push_back(parse_charset());
884                    lastItemKind = SetItem;
885                }
886                else if (op == posixPropertyOpener) {
887                    bool negated = false;
888                    if (*mCursor == '^') {
889                        negated = true;
890                        mCursor++;
891                    }
892                    RE * posixSet = parsePropertyExpression();
893                    subexprs.push_back(negated ? makeComplement(posixSet) : posixSet);
894                    lastItemKind = BrackettedSetItem;
895                    if (*mCursor++ != ':' || *mCursor++ != ']')
896                        ParseFailure("Posix set expression improperly terminated.");
897                }
898            }
899            break;
900            case rangeHyphen:
901                if (lastItemKind != CodepointItem) {
902                    ParseFailure("Range operator - has illegal left operand.");
903                }
904                if (*mCursor == '\\') {
905                    mCursor++;
906                    if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) possibleByteCodeEscape = true;
907                    insert_range(cc, lastCodepointItem, parse_escaped_codepoint());
908                    //subexprs.push_back(makeRange(makeCC(lastCodepointItem), makeCC(parse_escaped_codepoint())));
909                } else {
910                    insert_range(cc, lastCodepointItem, parse_literal_codepoint());
911                    //subexprs.push_back(makeRange(makeCC(lastCodepointItem), makeCC(parse_literal_codepoint())));
912                }
913                lastItemKind = RangeItem;
914                break;
915            case hyphenChar:
916                insert(cc, '-');
917                lastItemKind = CodepointItem;
918                lastCodepointItem = static_cast<codepoint_t> ('-');
919                break;
920            case ampChar:
921                insert(cc, '&');
922                lastItemKind = CodepointItem;
923                lastCodepointItem = static_cast<codepoint_t> ('&');
924                break;
925            case backSlash:
926                if (isSetEscapeChar(*mCursor)) {
927                    subexprs.push_back(parseEscapedSet());
928                    lastItemKind = SetItem;
929                }
930                else {
931                    if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) possibleByteCodeEscape = true;
932                    lastCodepointItem = parse_escaped_codepoint();
933                    insert(cc, lastCodepointItem);
934                    lastItemKind = CodepointItem;
935                }
936                break;
937            case emptyOperator:
938                lastCodepointItem = parse_literal_codepoint();
939                insert(cc, lastCodepointItem);
940                lastItemKind = CodepointItem;
941                break;
942        }
943    }
944    ParseFailure("Set expression not properly terminated.");
945}
946
947
948// A backslash escape was found, and various special cases (back reference,
949// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
950// cluster \X have been ruled out.
951// It may be one of several possibilities or an error sequence.
952// 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
953// 2. General control codes c[@-_a-z?]
954// 3. Restricted octal notation 0 - 0777
955// 4. General octal notation o\{[0-7]+\}
956// 5. General hex notation x\{[0-9A-Fa-f]+\}
957// 6. An error for any unrecognized alphabetic escape
958// 7. An escaped ASCII symbol, standing for itself
959
960codepoint_t RE_Parser::parse_escaped_codepoint() {
961    codepoint_t cp_value;
962    switch (*mCursor) {
963        case 'a': ++mCursor; return 0x07; // BEL
964        case 'e': ++mCursor; return 0x1B; // ESC
965        case 'f': ++mCursor; return 0x0C; // FF
966        case 'n': ++mCursor; return 0x0A; // LF
967        case 'r': ++mCursor; return 0x0D; // CR
968        case 't': ++mCursor; return 0x09; // HT
969        case 'v': ++mCursor; return 0x0B; // VT
970        case 'c': // Control-escape based on next char
971            ++mCursor;
972            // \c@, \cA, ... \c_, or \ca, ..., \cz
973            if (((*mCursor >= '@') && (*mCursor <= '_')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))) {
974                cp_value = static_cast<codepoint_t>(*mCursor & 0x1F);
975                mCursor++;
976                return cp_value;
977            }
978            else if (*mCursor++ == '?') return 0x7F;  // \c? ==> DEL
979            else ParseFailure("Illegal \\c escape sequence");
980        case '0': // Octal escape:  0 - 0377
981            ++mCursor;
982            return parse_octal_codepoint(0,3);
983        case 'o':
984            ++mCursor;
985            if (*mCursor == '{') {
986                ++mCursor;
987                cp_value = parse_octal_codepoint(1, 7);
988                if (*mCursor++ != '}') ParseFailure("Malformed octal escape sequence");
989                return cp_value;
990            }
991            else {
992                ParseFailure("Malformed octal escape sequence");
993            }
994        case 'x':
995            ++mCursor;
996            if (*mCursor == '{') {
997              ++mCursor;
998              cp_value = parse_hex_codepoint(1, 6);
999              if (*mCursor++ != '}') ParseFailure("Malformed hex escape sequence");
1000              return cp_value;
1001            }
1002            else {
1003                return parse_hex_codepoint(1,2);  // ICU compatibility
1004            }
1005        case 'u':
1006            ++mCursor;
1007            if (*mCursor == '{') {
1008                ++mCursor;
1009                cp_value = parse_hex_codepoint(1, 6);
1010                if (*mCursor++ != '}') ParseFailure("Malformed hex escape sequence");
1011                return cp_value;
1012            }
1013            else {
1014                return parse_hex_codepoint(4,4);  // ICU compatibility
1015            }
1016        case 'U':
1017            ++mCursor;
1018            return parse_hex_codepoint(8,8);  // ICU compatibility
1019        default:
1020            // Escaped letters should be reserved for special functions.
1021            if (((*mCursor >= 'A') && (*mCursor <= 'Z')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))){
1022                //Escape unknown letter will be parse as normal letter
1023                return parse_literal_codepoint();
1024                //ParseFailure("Undefined or unsupported escape sequence");
1025            }
1026            else if ((*mCursor < 0x20) || (*mCursor >= 0x7F))
1027                ParseFailure("Illegal escape sequence");
1028            else return static_cast<codepoint_t>(*mCursor++);
1029    }
1030}
1031
1032codepoint_t RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
1033    codepoint_t value = 0;
1034    int count = 0;
1035    while (mCursor.more() && count < maxdigits) {
1036        const char t = *mCursor;
1037        if (t < '0' || t > '7') {
1038            break;
1039        }
1040        value = value * 8 | (t - '0');
1041        ++mCursor;
1042        ++count;
1043    }
1044    if (count < mindigits) ParseFailure("Octal sequence has too few digits");
1045    if (value > UCD::UNICODE_MAX) ParseFailure("Octal value too large");
1046    return value;
1047}
1048
1049codepoint_t RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
1050    codepoint_t value = 0;
1051    int count = 0;
1052    while (mCursor.more() && isxdigit(*mCursor) && count < maxdigits) {
1053        const char t = *mCursor;
1054        if (isdigit(t)) {
1055            value = (value * 16) | (t - '0');
1056        }
1057        else {
1058            value = ((value * 16) | ((t | 32) - 'a')) + 10;
1059        }
1060        ++mCursor;
1061        ++count;
1062    }
1063    if (count < mindigits) ParseFailure("Hexadecimal sequence has too few digits");
1064    if (value > UCD::UNICODE_MAX) ParseFailure("Hexadecimal value too large");
1065    return value;
1066}
1067
1068Name * RE_Parser::createCC(const codepoint_t cp) {
1069    CC * cc = makeCC(cp);
1070    return mMemoizer.memoize(cc);
1071}
1072
1073void RE_Parser::insert(CC * cc, const codepoint_t cp) {
1074    cc->insert(cp);
1075}
1076
1077void RE_Parser::insert_range(CC * cc, const codepoint_t lo, const codepoint_t hi) {
1078    cc->insert_range(lo, hi);
1079}
1080
1081RE * RE_Parser::makeComplement(RE * s) {
1082  return makeDiff(makeAny(), s);
1083}
1084
1085           
1086
1087                           
1088RE * RE_Parser::makeWordBoundary() {
1089    Name * wordC = makeWordSet();
1090    return makeReBoundary(wordC);
1091}
1092
1093RE * RE_Parser::makeWordNonBoundary() {
1094    Name * wordC = makeWordSet();
1095    return makeReNonBoundary(wordC);
1096}
1097
1098inline RE * RE_Parser::makeReBoundary(RE * re) {
1099    return makeBoundaryAssertion(re);
1100}
1101inline RE * RE_Parser::makeReNonBoundary(RE * re) {
1102    return makeNegativeBoundaryAssertion(re);
1103}
1104
1105RE * RE_Parser::makeWordBegin() {
1106    Name * wordC = makeWordSet();
1107    return makeNegativeLookBehindAssertion(wordC);
1108}
1109
1110RE * RE_Parser::makeWordEnd() {
1111    Name * wordC = makeWordSet();
1112    return makeNegativeLookAheadAssertion(wordC);
1113}
1114
1115Name * RE_Parser::makeDigitSet() {
1116    return mMemoizer.memoize(createName("nd"));
1117}
1118
1119Name * RE_Parser::makeAlphaNumeric() {
1120    return mMemoizer.memoize(createName("alnum"));
1121}
1122
1123Name * RE_Parser::makeWhitespaceSet() {
1124    return mMemoizer.memoize(createName("whitespace"));
1125}
1126
1127Name * RE_Parser::makeWordSet() {
1128    return mMemoizer.memoize(createName("word"));
1129}
1130
1131Name * RE_Parser::createName(std::string value) {
1132    auto key = std::make_pair("", value);
1133    auto f = mNameMap.find(key);
1134    if (f != mNameMap.end()) {
1135        return f->second;
1136    }
1137    Name * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
1138    mNameMap.insert(std::make_pair(std::move(key), property));
1139    return property;
1140    }
1141
1142Name * RE_Parser::createName(std::string prop, std::string value) {
1143    auto key = std::make_pair(prop, value);
1144    auto f = mNameMap.find(key);
1145    if (f != mNameMap.end()) {
1146        return f->second;
1147    }
1148    Name * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
1149    mNameMap.insert(std::make_pair(std::move(key), property));
1150    return property;
1151}
1152
1153LLVM_ATTRIBUTE_NORETURN void RE_Parser::ParseFailure(std::string errmsg) {
1154    llvm::report_fatal_error(errmsg);
1155}
1156
1157}
Note: See TracBrowser for help on using the repository browser.