Ignore:
Timestamp:
Sep 21, 2014, 10:25:56 AM (5 years ago)
Author:
nmedfort
Message:

RE Parser modification to use ParseFailure? exceptions; removed the list reversal within Alt and Seq constructors and adjusted the functions that relied on it occurring.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re_parser.cpp

    r4017 r4182  
    66
    77#include "re_parser.h"
    8 
    9 
    10 ParseResult* RE_Parser::parse_re(std::string input_string)
     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)
    1129{
    12     parse_result_retVal re_result = parse_re_helper(input_string);
    13 
    14     if (re_result.remaining.length() == 0)
     30
     31}
     32
     33RE * RE_Parser::parse_alt(const bool subexpression) {
     34    std::unique_ptr<Alt> alt(new Alt());
     35    for (;;) {
     36        alt->push_back(parse_seq());
     37        if (_cursor == _end || *_cursor != '|') {
     38            break;
     39        }
     40        ++_cursor; // advance past the alternation character '|'
     41    }
     42    if (alt->empty())
    1543    {
    16         return re_result.result;
    17     }
    18     else if (ParseSuccess* re_success = dynamic_cast<ParseSuccess*>(re_result.result))
     44        throw NoRegularExpressionFound();
     45    }
     46    else if (subexpression) {
     47        if (_cursor == _end || *_cursor != ')') {
     48            throw ParseFailure("Parenthesization error!");
     49        }
     50        ++_cursor;
     51    }
     52    else if (_cursor != _end) { // !subexpression
     53        throw ParseFailure("Cannot fully parse statement!");
     54    }
     55
     56    RE * re;
     57    if (alt->size() == 1) {
     58        re = alt->back();
     59        alt->pop_back();
     60    }
     61    else {
     62        re = alt.release();
     63    }
     64    return re;
     65}
     66
     67inline RE * RE_Parser::parse_seq() {
     68    std::unique_ptr<Seq> seq(new Seq());
     69    for (;;) {
     70        RE * re = parse_next_token();
     71        if (re == nullptr) {
     72            break;
     73        }
     74        seq->push_back(extend_item(re));
     75    }
     76    if (seq->empty())
    1977    {
    20         ParseFailure* failure = new ParseFailure("Junk remaining!");
    21 
    22         return failure;
    23     }
    24     else if (ParseFailure* re_failure = dynamic_cast<ParseFailure*>(re_result.result))
    25     {
    26         return re_failure;
    27     }
    28     else
    29     {
    30         return 0;
    31     }
    32 }
    33 
    34 parse_result_retVal RE_Parser::parse_re_helper(std::string s)
    35 {
    36     parse_result_retVal result_retVal;
    37 
    38     parse_re_list_retVal af_result = parse_re_alt_form_list(s);
    39 
    40     if (af_result.re_list.size() == 0)
    41     {
    42         result_retVal.result = new ParseFailure("No regular expression found!");
    43         result_retVal.remaining = s;
    44     }
    45     else if (af_result.re_list.size() == 1)
    46     {
    47         result_retVal.result = new ParseSuccess(af_result.re_list.front());
    48         result_retVal.remaining = af_result.remaining;
    49     }
    50     else
    51     {
    52         result_retVal.result = new ParseSuccess(new Alt(&af_result.re_list));
    53         result_retVal.remaining = af_result.remaining;
    54     }
    55 
    56     return result_retVal;
    57 }
    58 
    59 parse_re_list_retVal RE_Parser::parse_re_alt_form_list(std::string s)
    60 {
    61     parse_re_list_retVal re_list_retVal;
    62     parse_result_retVal form_result = parse_re_form(s);
    63 
    64     if (ParseSuccess* re_success = dynamic_cast<ParseSuccess*>(form_result.result))
    65     {
    66         if (form_result.remaining.operator [](0) == '|')
    67         {           
    68             parse_re_list_retVal t1_re_list_retVal =
    69                     parse_re_alt_form_list(form_result.remaining.substr(1, form_result.remaining.length() - 1));
    70             std::list<RE*>::iterator it;
    71             it=t1_re_list_retVal.re_list.begin();
    72             re_list_retVal.re_list.assign(it, t1_re_list_retVal.re_list.end());
    73             re_list_retVal.remaining = t1_re_list_retVal.remaining;
    74         }
    75         else
    76         {
    77             re_list_retVal.remaining = form_result.remaining;
    78         }
    79         re_list_retVal.re_list.push_back(re_success->getRE());
    80     }
    81     else
    82     {
    83         re_list_retVal.re_list.clear();
    84         re_list_retVal.remaining = s;
    85     }
    86 
    87     return re_list_retVal;
    88 }
    89 
    90 parse_result_retVal RE_Parser::parse_re_form(std::string s)
    91 {
    92     parse_result_retVal form_retVal;
    93     parse_re_list_retVal item_list_result = parse_re_item_list(s);
    94 
    95     if (item_list_result.re_list.size() == 0)
    96     {
    97         form_retVal.result = new ParseFailure("No Regular Expression Found!");
    98         form_retVal.remaining = s;
    99     }
    100     else if (item_list_result.re_list.size() == 1)
    101     {
    102         form_retVal.result = new ParseSuccess(item_list_result.re_list.front());
    103         form_retVal.remaining = item_list_result.remaining;
    104     }
    105     else
    106     {
    107         form_retVal.result = new ParseSuccess(new Seq(&item_list_result.re_list));
    108         form_retVal.remaining = item_list_result.remaining;
    109     }
    110 
    111     return form_retVal;
    112 }
    113 
    114 parse_re_list_retVal RE_Parser::parse_re_item_list(std::string s)
    115 {
    116     parse_re_list_retVal item_list_retVal;
    117     parse_result_retVal item_result = parse_re_item(s);
    118 
    119     if (ParseSuccess* re_success = dynamic_cast<ParseSuccess*>(item_result.result))
    120     {
    121         parse_re_list_retVal t1_item_list_retVal = parse_re_item_list(item_result.remaining);
    122 
    123         std::list<RE*>::iterator it;
    124         it=t1_item_list_retVal.re_list.begin();
    125         item_list_retVal.re_list.assign(it, t1_item_list_retVal.re_list.end());
    126         item_list_retVal.re_list.push_back(re_success->getRE());
    127         item_list_retVal.remaining = t1_item_list_retVal.remaining;
    128     }
    129     else
    130     {
    131         item_list_retVal.re_list.clear();
    132         item_list_retVal.remaining = s;
    133     }
    134 
    135     return item_list_retVal;
    136 }
    137 
    138 parse_result_retVal RE_Parser::parse_re_item(std::string s)
    139 {
    140     parse_result_retVal item_retVal;
    141     parse_result_retVal unit_result = parse_re_unit(s);
    142 
    143     if (ParseSuccess* re_success = dynamic_cast<ParseSuccess*>(unit_result.result))
    144     {
    145         item_retVal = extend_item(re_success->getRE(), unit_result.remaining);
    146     }
    147     else
    148     {
    149         item_retVal.result = new ParseFailure("Parse item failure!");
    150         item_retVal.remaining = s;
    151     }
    152 
    153     return item_retVal;
    154 }
    155 
    156 parse_result_retVal RE_Parser::parse_re_unit(std::string s)
    157 {
    158     parse_result_retVal unit_retVal;
    159 
    160     if (s.length() == 0)
    161     {
    162         unit_retVal.result = new ParseFailure("Incomplete regular expression! (parse_re_unit)");
    163         unit_retVal.remaining = "";
    164     }
    165     else if (s.operator[](0) == '(')
    166     {
    167         parse_result_retVal t1_unit_retVal = parse_re_helper(s.substr(1, s.length() - 1));
    168         ParseSuccess* success = dynamic_cast<ParseSuccess*>(t1_unit_retVal.result);
    169         if ((success != 0) && (t1_unit_retVal.remaining.operator[](0) == ')'))
    170         {
    171             unit_retVal.result = success;
    172             unit_retVal.remaining = t1_unit_retVal.remaining.substr(1, t1_unit_retVal.remaining.length() - 1);
    173         }
    174         else
    175         {
    176             unit_retVal.result = new ParseFailure("Bad parenthesized RE!");
    177             unit_retVal.remaining = s.substr(1, s.length() - 1);
    178         }
    179     }
    180     else if (s.operator [](0) == '^')
    181     {
    182         unit_retVal.result = new ParseSuccess(new Start);
    183         unit_retVal.remaining = s.substr(1, s.length() - 1);
    184     }
    185     else if (s.operator[](0) == '$')
    186     {
    187         unit_retVal.result = new ParseSuccess(new End);
    188         unit_retVal.remaining = s.substr(1, s.length() - 1);
    189     }
    190     else
    191     {
    192         unit_retVal = parse_cc(s);
    193     }
    194 
    195     return unit_retVal;
    196 }
    197 
    198 parse_result_retVal RE_Parser::extend_item(RE *re, std::string s)
    199 {
    200      parse_result_retVal extend_item_retVal;
    201 
    202      if (s.operator [](0) == '*')
    203      {
    204          return extend_item(new Rep(re, 0, unboundedRep), s.substr(1, s.length() - 1));
    205      }
    206      else if (s.operator[](0) == '?')
    207      {
    208          return extend_item(new Rep(re, 0, 1), s.substr(1, s.length() - 1));
    209      }
    210      else if (s.operator[](0) == '+')
    211      {
    212          return extend_item(new Rep(re, 1, unboundedRep), s.substr(1, s.length() - 1));
    213      }
    214      else if (s.operator[](0) == '{')
    215      {
    216         parse_int_retVal int_retVal = parse_int(s.substr(1, s.length() - 1));
    217 
    218         if ((int_retVal.i != -1) && (int_retVal.remaining.operator [](0) == '}'))
    219         {
    220             extend_item_retVal =
    221                     extend_item(new Rep(re, int_retVal.i, int_retVal.i), int_retVal.remaining.substr(1, int_retVal.remaining.length() - 1));
    222 
    223         }
    224         else if ((int_retVal.i != -1) && ((int_retVal.remaining.operator [](0) == ',') && (int_retVal.remaining.operator [](1) == '}')))
    225         {
    226             extend_item_retVal =
    227                     extend_item(new Rep(re, int_retVal.i, unboundedRep), int_retVal.remaining.substr(2, int_retVal.remaining.length() - 2));
    228 
    229         }
    230         else if ((int_retVal.i != -1) && (int_retVal.remaining.operator [](0) == ','))
    231         {
    232             parse_int_retVal t1_int_retVal = parse_int(int_retVal.remaining.substr(1, int_retVal.remaining.length() - 1));
    233 
    234             if ((t1_int_retVal.i != -1) && (t1_int_retVal.remaining.operator [](0) == '}'))
    235             {
    236                 extend_item_retVal =
    237                         extend_item(new Rep(re, int_retVal.i, t1_int_retVal.i), t1_int_retVal.remaining.substr(1, t1_int_retVal.remaining.length() - 1));
    238             }
    239             else
    240             {
    241                 extend_item_retVal.result = new ParseFailure("Bad upper bound!");
    242                 extend_item_retVal.remaining = int_retVal.remaining.substr(1, int_retVal.remaining.length() - 1);
    243             }
    244         }
    245         else
    246         {
    247             extend_item_retVal.result = new ParseFailure("Bad lower bound!");
    248             extend_item_retVal.remaining = s.substr(1, s.length() - 1);
    249         }
    250      }
    251      else
    252      {
    253          extend_item_retVal.result = new ParseSuccess(re);
    254          extend_item_retVal.remaining = s;
    255      }
    256 
    257      return extend_item_retVal;
    258 }
    259 
    260 parse_result_retVal RE_Parser::parse_cc(std::string s)
    261 {
    262     parse_result_retVal cc_retVal;
    263 
    264     if (s.operator [](0) == '\\')
    265     {
    266         if (s.operator [](1) == '?')
    267         {
    268             cc_retVal.result = new ParseSuccess(new CC('?'));
    269         }
    270         else if (s.operator [](1) == '+')
    271         {
    272             cc_retVal.result = new ParseSuccess(new CC('+'));
    273         }
    274         else if (s.operator [](1) == '*')
    275         {
    276             cc_retVal.result = new ParseSuccess(new CC('*'));
    277         }
    278         else if (s.operator [](1) == '(')
    279         {
    280             cc_retVal.result = new ParseSuccess(new CC('('));
    281         }
    282         else if (s.operator [](1) == ')')
    283         {
    284             cc_retVal.result = new ParseSuccess(new CC(')'));
    285         }
    286         else if (s.operator [](1) == '{')
    287         {
    288             cc_retVal.result = new ParseSuccess(new CC('{'));
    289         }
    290         else if (s.operator [](1) == '}')
    291         {
    292             cc_retVal.result = new ParseSuccess(new CC('}'));
    293         }
    294         else if (s.operator [](1) == '[')
    295         {
    296             cc_retVal.result = new ParseSuccess(new CC('['));
    297         }
    298         else if (s.operator [](1) == ']')
    299         {
    300             cc_retVal.result = new ParseSuccess(new CC(']'));
    301         }
    302         else if (s.operator [](1) == '|')
    303         {
    304             cc_retVal.result = new ParseSuccess(new CC('|'));
    305         }
    306         else if (s.operator [](1) == '.')
    307         {
    308             cc_retVal.result = new ParseSuccess(new CC('.'));
    309         }
    310         else if (s.operator [](1) == '\\')
    311         {
    312             cc_retVal.result = new ParseSuccess(new CC('\\'));
    313         }
    314         else if (s.operator [](1) == 'u')
    315         {
    316             parse_int_retVal hex_val = parse_hex(s.substr(2, s.length() - 2));
    317 
    318             if (hex_val.i == -1)
    319             {
    320                 cc_retVal.result = new ParseFailure("Bad Unicode hex notation!");
    321                 cc_retVal.remaining = hex_val.remaining;
    322             }
    323             else
    324             {
    325                 cc_retVal.result = new ParseSuccess(new CC(hex_val.i));
    326                 cc_retVal.remaining = hex_val.remaining;
    327             }
    328 
    329             return cc_retVal;
    330         }
    331         else if (s.operator [](1) == 'p')
    332         {
    333             return cc_retVal = parse_unicode_category(s.substr(2, s.length() - 2), /* negated = */ false);
    334         }
    335         else if (s.operator [](1) == 'P')
    336         {
    337             return cc_retVal = parse_unicode_category(s.substr(2, s.length() - 2), /* negated = */ true);
    338         }
    339         else
    340         {
    341             cc_retVal.result = new ParseFailure("Illegal backslash escape!");
    342             cc_retVal.remaining = s.substr(1, s.length() - 1);
    343 
    344             return cc_retVal;
    345         }
    346 
    347         cc_retVal.remaining = s.substr(2, s.length() - 2);
    348 
    349         return cc_retVal;
    350     }
    351 
    352     if (s.operator [](0) == '.')
    353     {       
    354         CC* cc = new CC();
    355         cc->insert_range(0, 9);
    356         cc->insert_range(11, 0x10FFFF);
    357         cc_retVal.result = new ParseSuccess(cc);
    358         cc_retVal.remaining = s.substr(1, s.length() - 1);
    359 
    360         return cc_retVal;
    361     }
    362 
    363     if (s.operator [](0) == '[')
    364     {
    365         if (s.operator[](1) == '^')
    366         {
    367             cc_retVal = negate_cc_result(parse_cc_body(s.substr(2, s.length() - 2)));
    368         }
    369         else
    370         {
    371             cc_retVal = parse_cc_body(s.substr(1, s.length() - 1));
    372         }
    373 
    374         return cc_retVal;
    375     }
    376 
    377     std::string metacharacters = "?+*(){}[]|";
    378     std::string c = s.substr(0,1);
    379 
    380     if (metacharacters.find(c) == std::string::npos)
    381     {
    382         cc_retVal.result = new ParseSuccess(new CC(s.operator [](0)));
    383         cc_retVal.remaining = s.substr(1, s.length() - 1);
    384     }
    385     else
    386     {
    387         cc_retVal.result = new ParseFailure("Metacharacter alone!");
    388         cc_retVal.remaining = s;
    389     }
    390 
    391     int next_byte = (s.operator [](0) & 0xFF);
    392 
    393     if ((next_byte >= 0xC0) && (next_byte <= 0xDF))
    394     {       
    395         cc_retVal = parse_utf8_bytes(1, s);
    396     }
    397     else if ((next_byte >= 0xE0) && (next_byte <= 0xEF))
    398     {
    399         cc_retVal = parse_utf8_bytes(2, s);
    400     }
    401     else if((next_byte >= 0xF0) && (next_byte <= 0xFF))
    402     {
    403         cc_retVal = parse_utf8_bytes(3, s);
    404     }
    405 
    406     return cc_retVal;
    407 }
    408 
    409 parse_result_retVal RE_Parser::parse_utf8_bytes(int suffix_count, std::string s)
    410 {
    411     CC* cc = new CC((s.operator [](0) & 0xFF));
    412     Seq* seq = new Seq();
    413     seq->setType(Seq::Byte);
    414     seq->AddREListItem(cc);
    415 
    416     return parse_utf8_suffix_byte(suffix_count, s.substr(1, s.length() - 1), seq);
    417 }
    418 
    419 parse_result_retVal RE_Parser::parse_utf8_suffix_byte(int suffix_byte_num, std::string s, Seq *seq_sofar)
    420 {
    421     parse_result_retVal result_RetVal;
    422 
    423     if (suffix_byte_num == 0)
    424     {
    425         result_RetVal.result = new ParseSuccess(seq_sofar);
    426         result_RetVal.remaining = s;
    427     }
    428     else if (s.length() == 0)
    429     {
    430         result_RetVal.result = new ParseFailure("Invalid UTF-8 encoding!");
    431         result_RetVal.remaining = "";
    432     }
    433     else
    434     {
    435         if ((s.operator [](0) & 0xC0) == 0x80)
    436         {
    437             CC* cc = new CC((s.operator [](0) & 0xFF));
    438             seq_sofar->AddREListItem(cc);
    439             suffix_byte_num--;
    440             result_RetVal = parse_utf8_suffix_byte(suffix_byte_num, s.substr(1, s.length() - 1), seq_sofar);
    441         }
    442         else
    443         {
    444             result_RetVal.result = new ParseFailure("Invalid UTF-8 encoding!");
    445             result_RetVal.remaining = s;
    446         }
    447     }
    448 
    449     return result_RetVal;
    450 }
    451 
    452 parse_result_retVal RE_Parser::parse_unicode_category(std::string s, bool negated)
    453 {
    454     parse_result_retVal result_retVal;
    455 
    456     if (s.operator [](0) == '{')
    457     {
    458         Name* name = new Name();
     78        throw NoRegularExpressionFound();
     79    }
     80
     81    RE * re;
     82    if (seq->size() == 1) {
     83        re = seq->back();
     84        seq->pop_back();
     85    }
     86    else {
     87        re = seq.release();
     88    }
     89    return re;
     90}
     91
     92RE * RE_Parser::parse_next_token() {
     93    RE * re = nullptr;
     94    if (_cursor != _end) {
     95        switch (*_cursor) {
     96            case '(':
     97                ++_cursor;
     98                re = parse_alt(true);
     99                break;
     100            case '^':
     101                ++_cursor;
     102                re = new Start;
     103                break;
     104            case '$':
     105                ++_cursor;
     106                re = new End;
     107                break;
     108            case '|': case ')':
     109                break;
     110            case '*': case '+': case '?': case ']': case '{': case '}':
     111                throw ParseFailure("Illegal metacharacter usage!");
     112            case '[':
     113                re = parse_charset();
     114                break;
     115            case '.': // the 'any' metacharacter
     116                re = parse_any_character();
     117                break;
     118            default:
     119                re = parse_literal();
     120                break;
     121        }
     122    }
     123    return re;
     124}
     125
     126CC * RE_Parser::parse_any_character() {
     127    CC * cc = new CC();
     128    cc->insert_range(0, 9);
     129    cc->insert_range(11, 0x10FFFF);
     130    ++_cursor;
     131    return cc;
     132}
     133
     134RE * RE_Parser::extend_item(RE * re) {
     135    if (_cursor == _end) {
     136        return re;
     137    }
     138    switch (*_cursor) {
     139        case '*':
     140            ++_cursor; // skip past the '*'
     141            re = new Rep(re, 0, UNBOUNDED_REP);
     142            break;
     143        case '?':
     144            ++_cursor; // skip past the '?'
     145            re = new Rep(re, 0, 1);
     146            break;
     147        case '+':
     148            ++_cursor; // skip past the '+'
     149            re = new Rep(re, 1, UNBOUNDED_REP);
     150            break;
     151        case '{':
     152            re = parse_range_bound(re);
     153            break;
     154        default:
     155            return re;
     156    }
     157    // this only occurs if we encountered one of the non-default cases above.
     158    return extend_item(re);
     159}
     160
     161inline RE * RE_Parser::parse_range_bound(RE * re) {
     162    ++_cursor;
     163    throw_incomplete_expression_error_if_end_of_stream();
     164    Rep * rep = nullptr;
     165    unsigned lower_bound;
     166    if (*_cursor == ',') {
     167        ++_cursor;
     168        lower_bound = 0;
     169    }
     170    else {
     171        lower_bound = parse_int();
     172    }
     173    throw_incomplete_expression_error_if_end_of_stream();
     174    if (*_cursor == '}') {
     175        rep = new Rep(re, lower_bound, lower_bound);
     176    }
     177    else if (*_cursor != ',') {
     178        throw BadLowerBound();
     179    }
     180    else { // [^,}]
     181        ++_cursor;
     182        throw_incomplete_expression_error_if_end_of_stream();
     183        if (*_cursor == '}') {
     184            rep = new Rep(re, lower_bound, UNBOUNDED_REP);
     185        }
     186        else {
     187            const unsigned upper_bound = parse_int();
     188            if (*_cursor != '}') {
     189                throw BadUpperBound();
     190            }
     191            rep = new Rep(re, lower_bound, upper_bound);
     192        }
     193    }
     194    ++_cursor;
     195    return rep;
     196}
     197
     198inline RE * RE_Parser::parse_literal() {
     199    // handle the escaped metacharacter (assuming it is one)
     200    if (*_cursor == '\\') {
     201        return parse_escaped_metacharacter();
     202    }
     203    else {
     204        return new CC(parse_utf8_codepoint());
     205    }
     206}
     207
     208inline RE * RE_Parser::parse_escaped_metacharacter() {
     209    ++_cursor;
     210    throw_incomplete_expression_error_if_end_of_stream();
     211    bool negated = false;
     212    switch (*_cursor) {
     213        case '(': case ')': case '*': case '+':
     214        case '.': case '?': case '[': case '\\':
     215        case ']': case '{': case '|': case '}':
     216            return new CC(*_cursor++);
     217        case 'u':
     218            return new CC(parse_hex());
     219        case 'P':
     220            negated = true;
     221        case 'p':
     222            return parse_unicode_category(negated);
     223    }
     224    throw ParseFailure("Illegal backslash escape!");
     225}
     226
     227unsigned RE_Parser::parse_utf8_codepoint() {
     228    unsigned c = static_cast<unsigned>(*_cursor++);
     229    if (c > 0x80) { // if non-ascii
     230        if (c < 0xC2) {
     231            throw InvalidUTF8Encoding();
     232        }
     233        else { // [0xC2, 0xFF]
     234            unsigned bytes = 0;
     235            if (c < 0xE0) { // [0xC2, 0xDF]
     236                c &= 0x1F;
     237                bytes = 1;
     238            }
     239            else if (c < 0xF0) { // [0xE0, 0xEF]
     240                c &= 0x0F;
     241                bytes = 2;
     242            }
     243            else { // [0xF0, 0xFF]
     244                c &= 0x0F;
     245                bytes = 3;
     246            }
     247            while (--bytes) {
     248                if (++_cursor == _end || (*_cursor & 0xC0) != 0x80) {
     249                    throw InvalidUTF8Encoding();
     250                }
     251                c = (c << 6) | static_cast<unsigned>(*_cursor & 0x3F);
     252            }
     253        }
     254    }
     255    return c;
     256}
     257
     258inline Name * RE_Parser::parse_unicode_category(const bool negated) {
     259    if (++_cursor != _end && *_cursor == '{') {
     260        std::unique_ptr<Name> name = std::unique_ptr<Name>(new Name);
    459261        name->setType(Name::UnicodeCategory);
    460262        name->setNegated(negated);
    461         result_retVal = parse_unicode_category1(s.substr(1,1), s.substr(2, s.length() - 2), name);
    462     }
    463     else
    464     {
    465         result_retVal.result = new ParseFailure("Incorrect Unicode character class format!");
    466         result_retVal.remaining = "";
    467     }
    468 
    469     return result_retVal;
    470 }
    471 
    472 parse_result_retVal RE_Parser::parse_unicode_category1(std::string character, std::string s, Name* name_sofar)
    473 {
    474     parse_result_retVal unicode_cat1_retVal;
    475 
    476     if (s.length() == 0)
    477     {
    478         delete name_sofar;
    479         unicode_cat1_retVal.result = new ParseFailure("Unclosed Unicode character class!");
    480         unicode_cat1_retVal.remaining = "";
    481     }
    482     else if (s.operator [](0) == '}')
    483     {
    484         name_sofar->setName(name_sofar->getName() + character);
    485         if (isValidUnicodeCategoryName(name_sofar))
    486         {
    487             unicode_cat1_retVal.result = new ParseSuccess(name_sofar);
    488             unicode_cat1_retVal.remaining = s.substr(1, s.length() - 1);
    489         }
    490         else
    491         {
    492             unicode_cat1_retVal.result = new ParseFailure("Unknown Unicode character class!");
    493             unicode_cat1_retVal.remaining = s.substr(1, s.length() - 1);
    494         }
    495     }
    496     else
    497     {
    498         name_sofar->setName(name_sofar->getName() + character);
    499         unicode_cat1_retVal = parse_unicode_category1(s.substr(0,1), s.substr(1, s.length() - 1), name_sofar);
    500     }
    501 
    502     return unicode_cat1_retVal;
    503 }
    504 
    505 parse_result_retVal RE_Parser::parse_cc_body(std::string s)
    506 {
    507     parse_result_retVal result_retVal;
    508 
    509     if (s.length() == 0)
    510     {
    511         result_retVal.result = new ParseFailure("Unclosed character class!");
    512         result_retVal.remaining = "";
    513     }
    514     else
    515     {
    516         CC* cc = new CC();
    517         result_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc);
    518     }
    519 
    520     return result_retVal;
    521 }
    522 
    523 parse_result_retVal RE_Parser::parse_cc_body0(std::string s, CC* cc_sofar)
    524 {
    525     parse_result_retVal cc_body0_retVal;
    526 
    527     if (s.length() == 0)
    528     {
    529         delete cc_sofar;
    530         cc_body0_retVal.result = new ParseFailure("Unclosed character class!");
    531         cc_body0_retVal.remaining = "";
    532     }
    533     else if (s.operator [](0) == ']')
    534     {
    535         cc_body0_retVal.result = new ParseSuccess(cc_sofar);
    536         cc_body0_retVal.remaining = s.substr(1, s.length() - 1);
    537     }
    538     else if ((s.operator [](0) == '-') && (s.operator [](1) == ']'))
    539     {
    540         cc_sofar->insert1('-');
    541         cc_body0_retVal.result = new ParseSuccess(cc_sofar);
    542         cc_body0_retVal.remaining = s.substr(2, s.length() - 2);
    543     }
    544     else if (s.operator [](0) == '-')
    545     {
    546         delete cc_sofar;
    547         cc_body0_retVal.result = new ParseFailure("Bad range in character class!");
    548         cc_body0_retVal.remaining = s.substr(1, s.length() - 1);
    549     }
    550     else
    551     {
    552         cc_body0_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc_sofar);
    553     }
    554 
    555     return cc_body0_retVal;
    556 }
    557 
    558 parse_result_retVal RE_Parser::parse_cc_body1(int chr, std::string s, CC* cc_sofar)
    559 {
    560     parse_result_retVal cc_body1_retVal;
    561 
    562     if (s.length() == 0)
    563     {
    564         delete cc_sofar;
    565         cc_body1_retVal.result = new ParseFailure("Unclosed character class!");
    566         cc_body1_retVal.remaining = "";
    567     }
    568     else if (s.operator [](0) == ']')
    569     {
    570         cc_sofar->insert1(chr);
    571         cc_body1_retVal.result = new ParseSuccess(cc_sofar);
    572         cc_body1_retVal.remaining = s.substr(1, s.length() - 1);
    573     }
    574     else if (s.length() == 1)
    575     {
    576         delete cc_sofar;
    577         cc_body1_retVal.result = new ParseFailure("Unclosed character class!");
    578         cc_body1_retVal.remaining = "";
    579     }
    580     else if ((s.operator [](0) == '-') && (s.operator [](1) == ']'))
    581     {
    582         cc_sofar->insert1(chr);
    583         cc_sofar->insert1('-');
    584         cc_body1_retVal = parse_cc_body0(s, cc_sofar);
    585     }
    586     else if ((s.operator [](0) == '-') && (s.operator [](1) == '\\') && (s.operator [](2) == 'u'))
    587     {
    588         parse_int_retVal int_retVal = parse_hex(s.substr(3, s.length() - 3));
    589 
    590         if (int_retVal.i == -1)
    591         {
    592             cc_body1_retVal.result = new ParseFailure("Bad Unicode hex notation!");
    593             cc_body1_retVal.remaining = "";
    594         }
    595         else
    596         {
    597             cc_sofar->insert_range(chr, int_retVal.i);
    598             cc_body1_retVal = parse_cc_body0(int_retVal.remaining, cc_sofar);
    599         }
    600     }
    601     else if ((s.operator [](0) == '-') && ( s.length() > 1))
    602     {
    603         cc_sofar->insert_range(chr, s.operator [](1));
    604         cc_body1_retVal = parse_cc_body0(s.substr(2, s.length() - 2), cc_sofar);
    605     }
    606     else if ((s.operator [](0) == 'u') && ( s.length() > 1))
    607     {
    608         parse_int_retVal int_retVal = parse_hex(s.substr(1, s.length() - 1));
    609 
    610         if (int_retVal.i == -1)
    611         {
    612             cc_body1_retVal.result = new ParseFailure("Bad Unicode hex notation!");
    613             cc_body1_retVal.remaining = "";
    614         }
    615         else
    616         {
    617             cc_body1_retVal = parse_cc_body1(int_retVal.i, int_retVal.remaining, cc_sofar);
    618         }
    619     }
    620     else
    621     {
    622         cc_sofar->insert1(chr);
    623         cc_body1_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc_sofar);
    624     }
    625 
    626     return cc_body1_retVal;
    627 }
    628 
    629 parse_int_retVal RE_Parser::parse_hex(std::string s)
    630 {
    631     parse_int_retVal int_retVal;
    632 
    633     if (s.operator [](0) == '{')
    634     {
    635         int hexval_sofar = 0;
    636         int_retVal = parse_hex_body(hexval_sofar, s.substr(1, s.length() - 1));
    637     }
    638     else
    639     {
    640         int_retVal.i = -1;
    641         int_retVal.remaining = s;
    642     }
    643 
    644     return int_retVal;
    645 }
    646 
    647 parse_int_retVal RE_Parser::parse_hex_body(int i, std::string s)
    648 {
    649     parse_int_retVal int_retVal;
    650 
    651     if (s.length() == 0)
    652     {
    653         int_retVal.i = i;
    654         int_retVal.remaining = "";
    655     }
    656     else if (s.operator [](0) == '}')
    657     {
    658         int_retVal.i = i;
    659         int_retVal.remaining = s.substr(1, s.length() - 1);
    660     }
    661     else if ((s.operator [](0) >= '0') && (s.operator [](0) <= '9'))
    662     {
    663         int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
    664     }
    665     else if ((s.operator [](0) >= 'a') && (s.operator [](0) <= 'f'))
    666     {
    667         int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
    668     }
    669     else if ((s.operator [](0) >= 'A') && (s.operator [](0) <= 'F'))
    670     {
    671         int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
    672     }
    673     else
    674     {
    675         int_retVal.i = -1;
    676         int_retVal.remaining = s;
    677     }
    678 
    679     return int_retVal;
    680 }
    681 
    682 int RE_Parser::parse_hex_body1(int i, std::string hex_str)
    683 {
    684     int retVal = 0;
    685     int newVal = 0;
    686 
    687     retVal = i << 4;
    688 
    689     std::stringstream ss(hex_str);
    690     ss >> std::hex >> newVal;
    691 
    692     retVal = retVal | newVal;
    693 
    694     return retVal;
    695 }
    696 
    697 parse_int_retVal RE_Parser::parse_int(std::string s)
    698 {
    699     parse_int_retVal int_retVal;
    700 
    701     if (isdigit(s.operator [](0)))
    702     {
    703         int_retVal = parse_int1(s.operator [](0) - 48, s.substr(1, s.length() - 1));
    704     }
    705     else
    706     {
    707         int_retVal.i = -1;
    708         int_retVal.remaining = s;
    709     }
    710 
    711     return int_retVal;
    712 }
    713 
    714 parse_int_retVal RE_Parser::parse_int1(int i, std::string s)
    715 {
    716     parse_int_retVal int1_retVal;
    717 
    718     if (s.length() == 0)
    719     {
    720         int1_retVal.i = i;
    721         int1_retVal.remaining = "";
    722     }
    723     else if (isdigit(s.operator [](0)))
    724     {
    725         int1_retVal = parse_int1(i * 10 + (s.operator [](0) - 48), s.substr(1, s.length() - 1));
    726     }
    727     else
    728     {
    729         int1_retVal.i = i;
    730         int1_retVal.remaining = s;
    731     }
    732 
    733     return int1_retVal;
    734 }
    735 
    736 parse_result_retVal RE_Parser::negate_cc_result(parse_result_retVal cc_result)
    737 {
    738     if (ParseSuccess* success = dynamic_cast<ParseSuccess*>(cc_result.result))
    739     {
    740         if (CC* cc = dynamic_cast<CC*>(success->getRE()))
    741         {
    742             cc->negate_class();
    743             //Remove any new-line.
    744             cc->remove1(10);
    745         }
    746     }
    747 
    748     return cc_result;
    749 }
    750 
    751 bool RE_Parser::isValidUnicodeCategoryName(Name* name)
    752 {
    753     std::string cat_name = name->getName();
    754 
    755     if (cat_name == "Cc")
     263        const cursor_t start = _cursor + 1;
     264        for (;;) {
     265            ++_cursor;
     266            if (_cursor == _end) {
     267                throw UnclosedUnicodeCharacterClass();
     268            }
     269            if (*_cursor == '}') {
     270                break;
     271            }
     272            ++_cursor;
     273        }
     274        name->setName(std::string(start, _cursor));
     275        if (isValidUnicodeCategoryName(name)) {
     276            ++_cursor;
     277            return name.release();
     278        }
     279    }
     280    throw ParseFailure("Incorrect Unicode character class format!");
     281}
     282
     283RE * RE_Parser::parse_charset() {
     284    std::unique_ptr<CC> cc(new CC());
     285    bool negated = false;
     286    bool included_closing_square_bracket = false;
     287    cursor_t start = ++_cursor;
     288    while (_cursor != _end) {
     289        bool literal = true;
     290        switch (*_cursor) {
     291            case '^':
     292                // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
     293                if (start == _cursor) {
     294                    negated = true;
     295                    start = ++_cursor; // move the start ahead incase the next character is a [ or -
     296                    literal = false;                   
     297                }
     298                break;
     299            case ']':
     300                // To include a ], put it immediately after the opening [ or [^; if it occurs later it will
     301                // close the bracket expression.
     302                if (start == _cursor) {
     303                    cc->insert1(']');
     304                    ++_cursor;
     305                    included_closing_square_bracket = true;
     306                    literal = false;
     307                    break;
     308                }
     309                if (negated) {
     310                    negate_cc(cc);
     311                }
     312                ++_cursor;
     313                return cc.release();
     314            // The hyphen (-) is not treated as a range separator if it appears first or last, or as the
     315            // endpoint of a range.
     316            case '-':
     317                if (true) {
     318                    literal = false;
     319                    const cursor_t next = _cursor + 1;
     320                    if (next == _end) {
     321                        goto parse_failed;
     322                    }
     323                    if ((start == _cursor) ? (*next != '-') : (*next == ']')) {
     324                        _cursor = next;
     325                        cc->insert1('-');
     326                        break;
     327                    }
     328                }
     329                throw ParseFailure("Invalid Lower Range Bound!");
     330            // case ':':
     331        }
     332        if (literal) {
     333            unsigned low;
     334            if (parse_charset_literal(low)) {
     335                // the previous literal allows for a - to create a range; test for it
     336                if (_cursor == _end) {
     337                    break; // out of loop to failure handling
     338                }
     339                if (*_cursor == '-') { // in range unless the next character is a ']'
     340                    if (++_cursor == _end) {
     341                        break; // out of loop to failure handling
     342                    }
     343                    if (*_cursor != ']') {
     344                        unsigned high;
     345                        if (!parse_charset_literal(high)) {
     346                            throw ParseFailure("Invalid Upper Range Bound!");
     347                        }
     348                        cc->insert_range(low, high);
     349                    }
     350                    continue;
     351                }
     352            }
     353            cc->insert1(low);
     354        }
     355    }
     356parse_failed:
     357    if (included_closing_square_bracket) {
     358        throw ParseFailure("One ']' cannot close \"[]\" or \"[^]\"; use \"[]]\" or \"[^]]\" instead.");
     359    }
     360    else {
     361        throw UnclosedCharacterClass();
     362    }
     363}
     364
     365inline bool RE_Parser::parse_charset_literal(unsigned & literal) {
     366    if (_cursor == _end) {
     367        return false;
     368    }
     369    if (*_cursor == '\\') {
     370        if (++_cursor == _end) {
     371            return false;
     372        }
     373        switch (*_cursor) {
     374            case '(': case ')': case '*': case '+':
     375            case '.': case '?': case '[': case '\\':
     376            case ']': case '{': case '|': case '}':
     377                if (_allow_escapes_within_charset) {
     378                    literal = *_cursor++;
     379                    return true;
     380                }
     381                break;
     382            case 'u':
     383                literal = parse_hex();
     384                return true;
     385            // probably need to pass in the CC to handle \w, \s, etc...
     386        }
     387        throw ParseFailure("Unknown charset escape!");
     388    }
     389    else {
     390        literal = parse_utf8_codepoint();
    756391        return true;
    757     else if (cat_name == "Cf")
    758         return true;
    759     else if (cat_name == "Cn")
    760         return true;
    761     else if (cat_name == "Co")
    762         return true;
    763     else if (cat_name == "Cs")
    764         return true;
    765     else if (cat_name == "C")
    766         return true;
    767     else if (cat_name == "Ll")
    768         return true;
    769     else if (cat_name == "Lt")
    770         return true;
    771     else if (cat_name == "Lu")
    772         return true;
    773     else if (cat_name == "L&")
    774         return true;
    775     else if (cat_name == "Lc")
    776         return true;
    777     else if (cat_name == "Lm")
    778         return true;
    779     else if (cat_name == "Lo")
    780         return true;
    781     else if (cat_name == "L")
    782         return true;
    783     else if (cat_name == "Mc")
    784         return true;
    785     else if (cat_name == "Me")
    786         return true;
    787     else if (cat_name == "Mn")
    788         return true;
    789     else if (cat_name == "M")
    790         return true;
    791     else if (cat_name == "Nd")
    792         return true;
    793     else if (cat_name == "Nl")
    794         return true;
    795     else if (cat_name == "No")
    796         return true;
    797     else if (cat_name == "N")
    798         return true;
    799     else if (cat_name == "Pc")
    800         return true;
    801     else if (cat_name == "Pd")
    802         return true;
    803     else if (cat_name == "Pe")
    804         return true;
    805     else if (cat_name == "Pf")
    806         return true;
    807     else if (cat_name == "Pi")
    808         return true;
    809     else if (cat_name == "Po")
    810         return true;
    811     else if (cat_name == "Ps")
    812         return true;
    813     else if (cat_name == "P")
    814         return true;
    815     else if (cat_name == "Sc")
    816         return true;
    817     else if (cat_name == "Sk")
    818         return true;
    819     else if (cat_name == "Sm")
    820         return true;
    821     else if (cat_name == "So")
    822         return true;
    823     else if (cat_name == "S")
    824         return true;
    825     else if (cat_name == "Zl")
    826         return true;
    827     else if (cat_name == "Zp")
    828         return true;
    829     else if (cat_name == "Zs")
    830         return true;
    831     else if (cat_name == "Z")
    832         return true;
    833     else
    834         return false;
    835 }
    836 
    837 
    838 
    839 
    840 
    841 
    842 
    843 
    844 
    845 
    846 
    847 
    848 
    849 
    850 
    851 
    852 
    853 
    854 
    855 
    856 
     392    }
     393    return false;
     394}
     395
     396unsigned RE_Parser::parse_int() {
     397    unsigned value = 0;
     398    for (; _cursor != _end; ++_cursor) {
     399        if (!isdigit(*_cursor)) {
     400            break;
     401        }
     402        value *= 10;
     403        value += static_cast<int>(*_cursor) - 48;
     404    }
     405    return value;
     406}
     407
     408unsigned RE_Parser::parse_hex() {
     409    if (++_cursor != _end && *_cursor == '{') {
     410        unsigned value = 0;
     411        for (++_cursor; _cursor != _end; ++_cursor) {
     412            const char t = *_cursor;
     413            if (t == '}') {
     414                ++_cursor;
     415                return value;
     416            }
     417            value *= 16;
     418            if (t >= '0' && t <= '9') {
     419                value |= (t - '0');
     420            }
     421            else if ((t | 32) >= 'a' && (t | 32) <= 'f') {
     422                value |= ((t | 32) - 'a') + 10;
     423            }
     424            else {
     425                break;
     426            }
     427        }
     428    }
     429    throw ParseFailure("Bad Unicode hex notation!");
     430}
     431
     432inline void RE_Parser::negate_cc(std::unique_ptr<CC> & cc) {
     433    cc->negate_class();
     434    cc->remove1(10);
     435}
     436
     437bool RE_Parser::isValidUnicodeCategoryName(const std::unique_ptr<Name> & name) {
     438    static const char * SET_OF_VALID_CATEGORIES[] = {
     439        "C", "Cc", "Cf", "Cn", "Co", "Cs",
     440        "L", "L&", "Lc", "Ll", "Lm", "Lo", "Lt", "Lu",
     441        "M", "Mc", "Me", "Mn",
     442        "N", "Nd", "Nl", "No",
     443        "P", "Pc", "Pd", "Pe", "Pf", "Pi", "Po", "Ps",
     444        "S", "Sc", "Sk", "Sm", "So",
     445        "Z", "Zl", "Zp", "Zs"
     446    };
     447    // NOTE: this method isn't as friendly as using an unordered_set for VALID_CATEGORIES since it requires
     448    // that the set is in ALPHABETICAL ORDER; however it ought to have less memory overhead than an
     449    // unordered_set and roughly equivalent speed.
     450    return std::binary_search(std::begin(SET_OF_VALID_CATEGORIES), std::end(SET_OF_VALID_CATEGORIES), name->getName());
     451}
     452
     453inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
     454    if (_cursor == _end) throw IncompleteRegularExpression();
     455}
Note: See TracChangeset for help on using the changeset viewer.