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

Last change on this file since 4193 was 4193, checked in by cameron, 5 years ago

More UTF-8 validation

File size: 13.0 KB
Line 
1/*
2 *  Copyright (c) 2014 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_parser.h"
8#include "re_alt.h"
9#include "re_end.h"
10#include "re_rep.h"
11#include "re_seq.h"
12#include "re_start.h"
13#include "parsefailure.h"
14#include <algorithm>
15
16RE * RE_Parser::parse_re(const std::string & regular_expression, const bool allow_escapes_within_charset) {
17    RE_Parser parser(regular_expression, allow_escapes_within_charset);
18    RE * re = parser.parse_alt(false);
19    if (re == nullptr) {
20        throw ParseFailure("An unexpected parsing error occurred!");
21    }
22    return re;
23}
24
25inline RE_Parser::RE_Parser(const std::string & regular_expression, const bool allow_escapes_within_charset)
26: _cursor(regular_expression.begin())
27, _end(regular_expression.end())
28, _allow_escapes_within_charset(allow_escapes_within_charset)
29{
30
31}
32
33template<class T>
34inline static RE * simplify_vector(T & vec) {
35    RE * re;
36    if (vec->size() == 1) {
37        re = vec->back();
38        vec->pop_back();
39    }
40    else {
41        re = vec.release();
42    }
43    return re;
44}
45
46RE * RE_Parser::parse_alt(const bool subexpression) {
47    std::unique_ptr<Alt> alt(new Alt());
48    for (;;) {
49        alt->push_back(parse_seq());
50        if (_cursor == _end || *_cursor != '|') {
51            break;
52        }
53        ++_cursor; // advance past the alternation character '|'
54    }
55    if (alt->empty())
56    {
57        throw NoRegularExpressionFound();
58    }
59    else if (subexpression) {
60        if (_cursor == _end || *_cursor != ')') {
61            throw ParseFailure("Parenthesization error!");
62        }
63        ++_cursor;
64    }
65    else if (_cursor != _end) { // !subexpression
66        throw ParseFailure("Cannot fully parse statement!");
67    }
68    return simplify_vector(alt);
69}
70
71inline RE * RE_Parser::parse_seq() {
72    std::unique_ptr<Seq> seq(new Seq());
73    for (;;) {
74        RE * re = parse_next_token();
75        if (re == nullptr) {
76            break;
77        }
78        seq->push_back(extend_item(re));
79    }
80    if (seq->empty())
81    {
82        throw NoRegularExpressionFound();
83    }
84    return simplify_vector(seq);
85}
86
87RE * RE_Parser::parse_next_token() {
88    RE * re = nullptr;
89    if (_cursor != _end) {
90        switch (*_cursor) {
91            case '(':
92                ++_cursor;
93                re = parse_alt(true);
94                break;
95            case '^':
96                ++_cursor;
97                re = new Start;
98                break;
99            case '$':
100                ++_cursor;
101                re = new End;
102                break;
103            case '|': case ')':
104                break;
105            case '*': case '+': case '?': case ']': case '{': case '}':
106                throw ParseFailure("Illegal metacharacter usage!");
107            case '[':
108                re = parse_charset();
109                break;
110            case '.': // the 'any' metacharacter
111                re = parse_any_character();
112                break;
113            default:
114                re = parse_literal();
115                break;
116        }
117    }
118    return re;
119}
120
121CC * RE_Parser::parse_any_character() {
122    CC * cc = new CC();
123    cc->insert_range(0, 9);
124    cc->insert_range(11, 0x10FFFF);
125    ++_cursor;
126    return cc;
127}
128
129RE * RE_Parser::extend_item(RE * re) {
130    if (_cursor == _end) {
131        return re;
132    }
133    switch (*_cursor) {
134        case '*':
135            ++_cursor; // skip past the '*'
136            re = new Rep(re, 0, Rep::UNBOUNDED_REP);
137            break;
138        case '?':
139            ++_cursor; // skip past the '?'
140            re = new Rep(re, 0, 1);
141            break;
142        case '+':
143            ++_cursor; // skip past the '+'
144            re = new Rep(re, 1, Rep::UNBOUNDED_REP);
145            break;
146        case '{':
147            re = parse_range_bound(re);
148            break;
149        default:
150            return re;
151    }
152    // this only occurs if we encountered one of the non-default cases above.
153    return extend_item(re);
154}
155
156inline RE * RE_Parser::parse_range_bound(RE * re) {
157    ++_cursor;
158    throw_incomplete_expression_error_if_end_of_stream();
159    Rep * rep = nullptr;
160    unsigned lower_bound;
161    if (*_cursor == ',') {
162        ++_cursor;
163        lower_bound = 0;
164    }
165    else {
166        lower_bound = parse_int();
167    }
168    throw_incomplete_expression_error_if_end_of_stream();
169    if (*_cursor == '}') {
170        rep = new Rep(re, lower_bound, lower_bound);
171    }
172    else if (*_cursor != ',') {
173        throw BadLowerBound();
174    }
175    else { // [^,}]
176        ++_cursor;
177        throw_incomplete_expression_error_if_end_of_stream();
178        if (*_cursor == '}') {
179            rep = new Rep(re, lower_bound, Rep::UNBOUNDED_REP);
180        }
181        else {
182            const unsigned upper_bound = parse_int();
183            if (*_cursor != '}') {
184                throw BadUpperBound();
185            }
186            rep = new Rep(re, lower_bound, upper_bound);
187        }
188    }
189    ++_cursor;
190    return rep;
191}
192
193inline RE * RE_Parser::parse_literal() {
194    // handle the escaped metacharacter (assuming it is one)
195    if (*_cursor == '\\') {
196        return parse_escaped_metacharacter();
197    }
198    else {
199        return new CC(parse_utf8_codepoint());
200    }
201}
202
203inline RE * RE_Parser::parse_escaped_metacharacter() {
204    ++_cursor;
205    throw_incomplete_expression_error_if_end_of_stream();
206    bool negated = false;
207    switch (*_cursor) {
208        case '(': case ')': case '*': case '+':
209        case '.': case '?': case '[': case '\\':
210        case ']': case '{': case '|': case '}':
211            return new CC(*_cursor++);
212        case 'u':
213            return new CC(parse_hex());
214        case 'P':
215            negated = true;
216        case 'p':
217            return parse_unicode_category(negated);
218    }
219    throw ParseFailure("Illegal backslash escape!");
220}
221
222unsigned RE_Parser::parse_utf8_codepoint() {
223    unsigned c = static_cast<unsigned>(*_cursor++);
224    if (c > 0x80) { // if non-ascii
225        if (c < 0xC2) {
226            throw InvalidUTF8Encoding();
227        }
228        else { // [0xC2, 0xFF]
229            unsigned bytes = 0;
230            if (c < 0xE0) { // [0xC2, 0xDF]
231                c &= 0x1F;
232                bytes = 1;
233            }
234            else if (c < 0xF0) { // [0xE0, 0xEF]
235                c &= 0x0F;
236                bytes = 2;
237            }
238            else { // [0xF0, 0xFF]
239                c &= 0x0F;
240                bytes = 3;
241            }
242            while (--bytes) {
243                if (++_cursor == _end || (*_cursor & 0xC0) != 0x80) {
244                    throw InvalidUTF8Encoding();
245                }
246                c = (c << 6) | static_cast<unsigned>(*_cursor & 0x3F);
247                // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
248                // or a 4-byte sequence is used to encode a codepoint < 0x10000.
249                // if (((bytes == 1) && (c < 0x20)) || ((bytes == 2) && (c < 0x10))) {
250                if ((c << (bytes - 1)) < 0x20) {
251                    throw InvalidUTF8Encoding();
252                }
253                 
254            }
255        }
256    }
257    // It is an error if a 4-byte sequence is used to encode a codepoint
258    // above the Unicode maximum.   
259    if (c > 0x10FFFF) throw InvalidUTF8Encoding();
260    return c;
261}
262
263inline Name * RE_Parser::parse_unicode_category(const bool negated) {
264    if (++_cursor != _end && *_cursor == '{') {
265        std::unique_ptr<Name> name = std::unique_ptr<Name>(new Name);
266        name->setType(Name::UnicodeCategory);
267        name->setNegated(negated);
268        const cursor_t start = _cursor + 1;
269        for (;;) {
270            ++_cursor;
271            if (_cursor == _end) {
272                throw UnclosedUnicodeCharacterClass();
273            }
274            if (*_cursor == '}') {
275                break;
276            }
277            ++_cursor;
278        }
279        name->setName(std::string(start, _cursor));
280        ++_cursor;
281        return name.release();
282    }
283    throw ParseFailure("Incorrect Unicode character class format!");
284}
285
286RE * RE_Parser::parse_charset() {
287    std::unique_ptr<CC> cc(new CC());
288    bool negated = false;
289    bool included_closing_square_bracket = false;
290    cursor_t start = ++_cursor;
291    while (_cursor != _end) {
292        bool literal = true;
293        switch (*_cursor) {
294            case '^':
295                // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
296                if (start == _cursor) {
297                    negated = true;
298                    start = ++_cursor; // move the start ahead in case the next character is a ] or -
299                    literal = false;                   
300                }
301                break;
302            case ']':
303                // To include a ], put it immediately after the opening [ or [^; if it occurs later it will
304                // close the bracket expression.
305                if (start == _cursor) {
306                    cc->insert(']');
307                    ++_cursor;
308                    included_closing_square_bracket = true;
309                    literal = false;
310                    break;
311                }
312                if (negated) {
313                    negate_cc(cc);
314                }
315                ++_cursor;
316                return cc.release();
317            // The hyphen (-) is not treated as a range separator if it appears first or last, or as the
318            // endpoint of a range.
319            case '-':
320                if (true) {
321                    literal = false;
322                    const cursor_t next = _cursor + 1;
323                    if (next == _end) {
324                        goto parse_failed;
325                    }
326                    if ((start == _cursor) ? (*next != '-') : (*next == ']')) {
327                        _cursor = next;
328                        cc->insert('-');
329                        break;
330                    }
331                }
332                throw ParseFailure("Invalid Lower Range Bound!");
333            // case ':':
334        }
335        if (literal) {
336            unsigned low;
337            if (parse_charset_literal(low)) {
338                // the previous literal allows for a - to create a range; test for it
339                if (_cursor == _end) {
340                    break; // out of loop to failure handling
341                }
342                if (*_cursor == '-') { // in range unless the next character is a ']'
343                    if (++_cursor == _end) {
344                        break; // out of loop to failure handling
345                    }
346                    if (*_cursor != ']') {
347                        unsigned high;
348                        if (!parse_charset_literal(high)) {
349                            throw ParseFailure("Invalid Upper Range Bound!");
350                        }
351                        cc->insert_range(low, high);
352                    }
353                    continue;
354                }
355            }
356            cc->insert(low);
357        }
358    }
359parse_failed:
360    if (included_closing_square_bracket) {
361        throw ParseFailure("One ']' cannot close \"[]\" or \"[^]\"; use \"[]]\" or \"[^]]\" instead.");
362    }
363    else {
364        throw UnclosedCharacterClass();
365    }
366}
367
368inline bool RE_Parser::parse_charset_literal(unsigned & literal) {
369    if (_cursor == _end) {
370        return false;
371    }
372    if (*_cursor == '\\') {
373        if (++_cursor == _end) {
374            throw ParseFailure("Unknown charset escape!");
375        }
376        switch (*_cursor) {
377            case '(': case ')': case '*': case '+':
378            case '.': case '?': case '[': case '\\':
379            case ']': case '{': case '|': case '}':
380                if (_allow_escapes_within_charset) {
381                    literal = *_cursor++;
382                    return true;
383                }
384                break;
385            case 'u':
386                literal = parse_hex();
387                return true;
388            // probably need to pass in the CC to handle \w, \s, etc...
389        }
390        throw ParseFailure("Unknown charset escape!");
391    }
392    else {
393        literal = parse_utf8_codepoint();
394        return true;
395    }
396    return false;
397}
398
399unsigned RE_Parser::parse_int() {
400    unsigned value = 0;
401    for (; _cursor != _end; ++_cursor) {
402        if (!isdigit(*_cursor)) {
403            break;
404        }
405        value *= 10;
406        value += static_cast<int>(*_cursor) - 48;
407    }
408    return value;
409}
410
411unsigned RE_Parser::parse_hex() {
412    if (++_cursor != _end && *_cursor == '{') {
413        unsigned value = 0;
414        for (++_cursor; _cursor != _end; ++_cursor) {
415            const char t = *_cursor;
416            if (t == '}') {
417                ++_cursor;
418                return value;
419            }
420            value *= 16;
421            if (t >= '0' && t <= '9') {
422                value |= (t - '0');
423            }
424            else if ((t | 32) >= 'a' && (t | 32) <= 'f') {
425                value |= ((t | 32) - 'a') + 10;
426            }
427            else {
428                break;
429            }
430        }
431    }
432    throw ParseFailure("Bad Unicode hex notation!");
433}
434
435inline void RE_Parser::negate_cc(std::unique_ptr<CC> & cc) {
436    cc->negate();
437    cc->remove(10);
438}
439
440inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
441    if (_cursor == _end) throw IncompleteRegularExpression();
442}
Note: See TracBrowser for help on using the repository browser.