libstdc++-v3/include/bits/regex_compiler.tcc

   1 // class template regex -*- C++ -*-
   2
   3 // Copyright (C) 2013-2014 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /**
  26  *  @file bits/regex_compiler.tcc
  27  *  This is an internal header file, included by other library headers.
  28  *  Do not attempt to use it directly. @headername{regex}
  29  */
  30
  31 // FIXME make comments doxygen format.
  32
  33 // This compiler refers to "Regular Expression Matching Can Be Simple And Fast"
  34 // (http://swtch.com/~rsc/regexp/regexp1.html"),
  35 // but doesn't strictly follow it.
  36 //
  37 // When compiling, states are *chained* instead of tree- or graph-constructed.
  38 // It's more like structured programs: there's if statement and loop statement.
  39 //
  40 // For alternative structure (say "a|b"), aka "if statement", two branches
  41 // should be constructed. However, these two shall merge to an "end_tag" at
  42 // the end of this operator:
  43 //
  44 //                branch1
  45 //              /        \
  46 // => begin_tag            end_tag =>
  47 //              \        /
  48 //                branch2
  49 //
  50 // This is the difference between this implementation and that in Russ's
  51 // article.
  52 //
  53 // That's why we introduced dummy node here ------ "end_tag" is a dummy node.
  54 // All dummy node will be eliminated at the end of compiling process.
  55
  56 namespace std _GLIBCXX_VISIBILITY(default)
  57 {
  58 namespace __detail
  59 {
  60 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  61
  62   template<typename _TraitsT>
  63     _Compiler<_TraitsT>::
  64     _Compiler(_IterT __b, _IterT __e,
  65               const _TraitsT& __traits, _FlagT __flags)
  66     : _M_flags((__flags
  67                 & (regex_constants::ECMAScript
  68                    | regex_constants::basic
  69                    | regex_constants::extended
  70                    | regex_constants::grep
  71                    | regex_constants::egrep
  72                    | regex_constants::awk))
  73                ? __flags
  74                : __flags | regex_constants::ECMAScript),
  75     _M_traits(__traits),
  76     _M_ctype(std::use_facet<_CtypeT>(_M_traits.getloc())),
  77     _M_scanner(__b, __e, _M_flags, _M_traits.getloc()),
  78     _M_nfa(_M_flags)
  79     {
  80       _StateSeqT __r(_M_nfa, _M_nfa._M_start());
  81       __r._M_append(_M_nfa._M_insert_subexpr_begin());
  82       this->_M_disjunction();
  83       if (!_M_match_token(_ScannerT::_S_token_eof))
  84         __throw_regex_error(regex_constants::error_paren);
  85       __r._M_append(_M_pop());
  86       _GLIBCXX_DEBUG_ASSERT(_M_stack.empty());
  87       __r._M_append(_M_nfa._M_insert_subexpr_end());
  88       __r._M_append(_M_nfa._M_insert_accept());
  89       _M_nfa._M_eliminate_dummy();
  90     }
  91
  92   template<typename _TraitsT>
  93     void
  94     _Compiler<_TraitsT>::
  95     _M_disjunction()
  96     {
  97       this->_M_alternative();
  98       while (_M_match_token(_ScannerT::_S_token_or))
  99         {
 100           _StateSeqT __alt1 = _M_pop();
 101           this->_M_alternative();
 102           _StateSeqT __alt2 = _M_pop();
 103           auto __end = _M_nfa._M_insert_dummy();
 104           __alt1._M_append(__end);
 105           __alt2._M_append(__end);
 106           // __alt2 is state._M_next, __alt1 is state._M_alt. The executor
 107           // executes _M_alt before _M_next, as well as executing left
 108           // alternative before right one.
 109           _M_stack.push(_StateSeqT(_M_nfa,
 110                                    _M_nfa._M_insert_alt(__alt2._M_start,
 111                                                         __alt1._M_start, false),
 112                                    __end));
 113         }
 114     }
 115
 116   template<typename _TraitsT>
 117     void
 118     _Compiler<_TraitsT>::
 119     _M_alternative()
 120     {
 121       if (this->_M_term())
 122         {
 123           _StateSeqT __re = _M_pop();
 124           this->_M_alternative();
 125           __re._M_append(_M_pop());
 126           _M_stack.push(__re);
 127         }
 128       else
 129         _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_dummy()));
 130     }
 131
 132   template<typename _TraitsT>
 133     bool
 134     _Compiler<_TraitsT>::
 135     _M_term()
 136     {
 137       if (this->_M_assertion())
 138         return true;
 139       if (this->_M_atom())
 140         {
 141           while (this->_M_quantifier());
 142           return true;
 143         }
 144       return false;
 145     }
 146
 147   template<typename _TraitsT>
 148     bool
 149     _Compiler<_TraitsT>::
 150     _M_assertion()
 151     {
 152       if (_M_match_token(_ScannerT::_S_token_line_begin))
 153         _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_line_begin()));
 154       else if (_M_match_token(_ScannerT::_S_token_line_end))
 155         _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_line_end()));
 156       else if (_M_match_token(_ScannerT::_S_token_word_bound))
 157         // _M_value[0] == 'n' means it's negative, say "not word boundary".
 158         _M_stack.push(_StateSeqT(_M_nfa, _M_nfa.
 159               _M_insert_word_bound(_M_value[0] == 'n')));
 160       else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin))
 161         {
 162           auto __neg = _M_value[0] == 'n';
 163           this->_M_disjunction();
 164           if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
 165             __throw_regex_error(regex_constants::error_paren);
 166           auto __tmp = _M_pop();
 167           __tmp._M_append(_M_nfa._M_insert_accept());
 168           _M_stack.push(
 169               _StateSeqT(
 170                 _M_nfa,
 171                 _M_nfa._M_insert_lookahead(__tmp._M_start, __neg)));
 172         }
 173       else
 174         return false;
 175       return true;
 176     }
 177
 178   template<typename _TraitsT>
 179     bool
 180     _Compiler<_TraitsT>::
 181     _M_quantifier()
 182     {
 183       bool __neg = (_M_flags & regex_constants::ECMAScript);
 184       auto __init = [this, &__neg]()
 185         {
 186           if (_M_stack.empty())
 187             __throw_regex_error(regex_constants::error_badrepeat);
 188           __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
 189         };
 190       if (_M_match_token(_ScannerT::_S_token_closure0))
 191         {
 192           __init();
 193           auto __e = _M_pop();
 194           _StateSeqT __r(_M_nfa, _M_nfa._M_insert_repeat(_S_invalid_state_id,
 195                                                          __e._M_start, __neg));
 196           __e._M_append(__r);
 197           _M_stack.push(__r);
 198         }
 199       else if (_M_match_token(_ScannerT::_S_token_closure1))
 200         {
 201           __init();
 202           auto __e = _M_pop();
 203           __e._M_append(_M_nfa._M_insert_repeat(_S_invalid_state_id,
 204                                                 __e._M_start, __neg));
 205           _M_stack.push(__e);
 206         }
 207       else if (_M_match_token(_ScannerT::_S_token_opt))
 208         {
 209           __init();
 210           auto __e = _M_pop();
 211           auto __end = _M_nfa._M_insert_dummy();
 212           _StateSeqT __r(_M_nfa, _M_nfa._M_insert_repeat(_S_invalid_state_id,
 213                                                          __e._M_start, __neg));
 214           __e._M_append(__end);
 215           __r._M_append(__end);
 216           _M_stack.push(__r);
 217         }
 218       else if (_M_match_token(_ScannerT::_S_token_interval_begin))
 219         {
 220           if (_M_stack.empty())
 221             __throw_regex_error(regex_constants::error_badrepeat);
 222           if (!_M_match_token(_ScannerT::_S_token_dup_count))
 223             __throw_regex_error(regex_constants::error_badbrace);
 224           _StateSeqT __r(_M_pop());
 225           _StateSeqT __e(_M_nfa, _M_nfa._M_insert_dummy());
 226           long __min_rep = _M_cur_int_value(10);
 227           bool __infi = false;
 228           long __n;
 229
 230           // {3
 231           if (_M_match_token(_ScannerT::_S_token_comma))
 232             if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7}
 233               __n = _M_cur_int_value(10) - __min_rep;
 234             else
 235               __infi = true;
 236           else
 237             __n = 0;
 238           if (!_M_match_token(_ScannerT::_S_token_interval_end))
 239             __throw_regex_error(regex_constants::error_brace);
 240
 241           __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
 242
 243           for (long __i = 0; __i < __min_rep; ++__i)
 244             __e._M_append(__r._M_clone());
 245
 246           if (__infi)
 247             {
 248               auto __tmp = __r._M_clone();
 249               _StateSeqT __s(_M_nfa,
 250                              _M_nfa._M_insert_repeat(_S_invalid_state_id,
 251                                                      __tmp._M_start, __neg));
 252               __tmp._M_append(__s);
 253               __e._M_append(__s);
 254             }
 255           else
 256             {
 257               if (__n < 0)
 258                 __throw_regex_error(regex_constants::error_badbrace);
 259               auto __end = _M_nfa._M_insert_dummy();
 260               // _M_alt is the "match more" branch, and _M_next is the
 261               // "match less" one. Switch _M_alt and _M_next of all created
 262               // nodes. This is a hack but IMO works well.
 263               std::stack<_StateIdT> __stack;
 264               for (long __i = 0; __i < __n; ++__i)
 265                 {
 266                   auto __tmp = __r._M_clone();
 267                   auto __alt = _M_nfa._M_insert_repeat(__tmp._M_start,
 268                                                        __end, __neg);
 269                   __stack.push(__alt);
 270                   __e._M_append(_StateSeqT(_M_nfa, __alt, __tmp._M_end));
 271                 }
 272               __e._M_append(__end);
 273               while (!__stack.empty())
 274                 {
 275                   auto& __tmp = _M_nfa[__stack.top()];
 276                   __stack.pop();
 277                   swap(__tmp._M_next, __tmp._M_alt);
 278                 }
 279             }
 280           _M_stack.push(__e);
 281         }
 282       else
 283         return false;
 284       return true;
 285     }
 286
 287 #define __INSERT_REGEX_MATCHER(__func, args...)\
 288         do\
 289           if (!(_M_flags & regex_constants::icase))\
 290             if (!(_M_flags & regex_constants::collate))\
 291               __func<false, false>(args);\
 292             else\
 293               __func<false, true>(args);\
 294           else\
 295             if (!(_M_flags & regex_constants::collate))\
 296               __func<true, false>(args);\
 297             else\
 298               __func<true, true>(args);\
 299         while (false)
 300
 301   template<typename _TraitsT>
 302     bool
 303     _Compiler<_TraitsT>::
 304     _M_atom()
 305     {
 306       if (_M_match_token(_ScannerT::_S_token_anychar))
 307         {
 308           if (!(_M_flags & regex_constants::ECMAScript))
 309             __INSERT_REGEX_MATCHER(_M_insert_any_matcher_posix);
 310           else
 311             __INSERT_REGEX_MATCHER(_M_insert_any_matcher_ecma);
 312         }
 313       else if (_M_try_char())
 314         __INSERT_REGEX_MATCHER(_M_insert_char_matcher);
 315       else if (_M_match_token(_ScannerT::_S_token_backref))
 316         _M_stack.push(_StateSeqT(_M_nfa, _M_nfa.
 317                                  _M_insert_backref(_M_cur_int_value(10))));
 318       else if (_M_match_token(_ScannerT::_S_token_quoted_class))
 319         __INSERT_REGEX_MATCHER(_M_insert_character_class_matcher);
 320       else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin))
 321         {
 322           _StateSeqT __r(_M_nfa, _M_nfa._M_insert_dummy());
 323           this->_M_disjunction();
 324           if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
 325             __throw_regex_error(regex_constants::error_paren);
 326           __r._M_append(_M_pop());
 327           _M_stack.push(__r);
 328         }
 329       else if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
 330         {
 331           _StateSeqT __r(_M_nfa, _M_nfa._M_insert_subexpr_begin());
 332           this->_M_disjunction();
 333           if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
 334             __throw_regex_error(regex_constants::error_paren);
 335           __r._M_append(_M_pop());
 336           __r._M_append(_M_nfa._M_insert_subexpr_end());
 337           _M_stack.push(__r);
 338         }
 339       else if (!_M_bracket_expression())
 340         return false;
 341       return true;
 342     }
 343
 344   template<typename _TraitsT>
 345     bool
 346     _Compiler<_TraitsT>::
 347     _M_bracket_expression()
 348     {
 349       bool __neg =
 350         _M_match_token(_ScannerT::_S_token_bracket_neg_begin);
 351       if (!(__neg || _M_match_token(_ScannerT::_S_token_bracket_begin)))
 352         return false;
 353       __INSERT_REGEX_MATCHER(_M_insert_bracket_matcher, __neg);
 354       return true;
 355     }
 356 #undef __INSERT_REGEX_MATCHER
 357
 358   template<typename _TraitsT>
 359   template<bool __icase, bool __collate>
 360     void
 361     _Compiler<_TraitsT>::
 362     _M_insert_any_matcher_ecma()
 363     {
 364       _M_stack.push(_StateSeqT(_M_nfa,
 365         _M_nfa._M_insert_matcher
 366           (_AnyMatcher<_TraitsT, true, __icase, __collate>
 367             (_M_traits))));
 368     }
 369
 370   template<typename _TraitsT>
 371   template<bool __icase, bool __collate>
 372     void
 373     _Compiler<_TraitsT>::
 374     _M_insert_any_matcher_posix()
 375     {
 376       _M_stack.push(_StateSeqT(_M_nfa,
 377         _M_nfa._M_insert_matcher
 378           (_AnyMatcher<_TraitsT, false, __icase, __collate>
 379             (_M_traits))));
 380     }
 381
 382   template<typename _TraitsT>
 383   template<bool __icase, bool __collate>
 384     void
 385     _Compiler<_TraitsT>::
 386     _M_insert_char_matcher()
 387     {
 388       _M_stack.push(_StateSeqT(_M_nfa,
 389         _M_nfa._M_insert_matcher
 390           (_CharMatcher<_TraitsT, __icase, __collate>
 391             (_M_value[0], _M_traits))));
 392     }
 393
 394   template<typename _TraitsT>
 395   template<bool __icase, bool __collate>
 396     void
 397     _Compiler<_TraitsT>::
 398     _M_insert_character_class_matcher()
 399     {
 400       _GLIBCXX_DEBUG_ASSERT(_M_value.size() == 1);
 401       _BracketMatcher<_TraitsT, __icase, __collate> __matcher
 402         (_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits);
 403       __matcher._M_add_character_class(_M_value, false);
 404       __matcher._M_ready();
 405       _M_stack.push(_StateSeqT(_M_nfa,
 406         _M_nfa._M_insert_matcher(std::move(__matcher))));
 407     }
 408
 409   template<typename _TraitsT>
 410   template<bool __icase, bool __collate>
 411     void
 412     _Compiler<_TraitsT>::
 413     _M_insert_bracket_matcher(bool __neg)
 414     {
 415       _BracketMatcher<_TraitsT, __icase, __collate> __matcher(__neg, _M_traits);
 416       while (!_M_match_token(_ScannerT::_S_token_bracket_end))
 417         _M_expression_term(__matcher);
 418       __matcher._M_ready();
 419       _M_stack.push(_StateSeqT(_M_nfa,
 420                                _M_nfa._M_insert_matcher(std::move(__matcher))));
 421     }
 422
 423   template<typename _TraitsT>
 424   template<bool __icase, bool __collate>
 425     void
 426     _Compiler<_TraitsT>::
 427     _M_expression_term(_BracketMatcher<_TraitsT, __icase, __collate>& __matcher)
 428     {
 429       if (_M_match_token(_ScannerT::_S_token_collsymbol))
 430         __matcher._M_add_collating_element(_M_value);
 431       else if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
 432         __matcher._M_add_equivalence_class(_M_value);
 433       else if (_M_match_token(_ScannerT::_S_token_char_class_name))
 434         __matcher._M_add_character_class(_M_value, false);
 435       else if (_M_try_char()) // [a
 436         {
 437           auto __ch = _M_value[0];
 438           if (_M_try_char())
 439             {
 440               if (_M_value[0] == '-') // [a-
 441                 {
 442                   if (_M_try_char()) // [a-z]
 443                     {
 444                       __matcher._M_make_range(__ch, _M_value[0]);
 445                       return;
 446                     }
 447                   // If the dash is the last character in the bracket
 448                   // expression, it is not special.
 449                   if (_M_scanner._M_get_token()
 450                       != _ScannerT::_S_token_bracket_end)
 451                     __throw_regex_error(regex_constants::error_range);
 452                 }
 453               __matcher._M_add_char(_M_value[0]);
 454             }
 455           __matcher._M_add_char(__ch);
 456         }
 457       else if (_M_match_token(_ScannerT::_S_token_quoted_class))
 458         __matcher._M_add_character_class(_M_value,
 459                                          _M_ctype.is(_CtypeT::upper,
 460                                                      _M_value[0]));
 461       else
 462         __throw_regex_error(regex_constants::error_brack);
 463     }
 464
 465   template<typename _TraitsT>
 466     bool
 467     _Compiler<_TraitsT>::
 468     _M_try_char()
 469     {
 470       bool __is_char = false;
 471       if (_M_match_token(_ScannerT::_S_token_oct_num))
 472         {
 473           __is_char = true;
 474           _M_value.assign(1, _M_cur_int_value(8));
 475         }
 476       else if (_M_match_token(_ScannerT::_S_token_hex_num))
 477         {
 478           __is_char = true;
 479           _M_value.assign(1, _M_cur_int_value(16));
 480         }
 481       else if (_M_match_token(_ScannerT::_S_token_ord_char))
 482         __is_char = true;
 483       return __is_char;
 484     }
 485
 486   template<typename _TraitsT>
 487     bool
 488     _Compiler<_TraitsT>::
 489     _M_match_token(_TokenT token)
 490     {
 491       if (token == _M_scanner._M_get_token())
 492         {
 493           _M_value = _M_scanner._M_get_value();
 494           _M_scanner._M_advance();
 495           return true;
 496         }
 497       return false;
 498     }
 499
 500   template<typename _TraitsT>
 501     int
 502     _Compiler<_TraitsT>::
 503     _M_cur_int_value(int __radix)
 504     {
 505       long __v = 0;
 506       for (typename _StringT::size_type __i = 0;
 507            __i < _M_value.length(); ++__i)
 508         __v =__v * __radix + _M_traits.value(_M_value[__i], __radix);
 509       return __v;
 510     }
 511
 512   template<typename _TraitsT, bool __icase, bool __collate>
 513     bool
 514     _BracketMatcher<_TraitsT, __icase, __collate>::
 515     _M_apply(_CharT __ch, false_type) const
 516     {
 517       bool __ret = std::binary_search(_M_char_set.begin(), _M_char_set.end(),
 518                                       _M_translator._M_translate(__ch));
 519       if (!__ret)
 520         {
 521           auto __s = _M_translator._M_transform(__ch);
 522           for (auto& __it : _M_range_set)
 523             if (__it.first <= __s && __s <= __it.second)
 524               {
 525                 __ret = true;
 526                 break;
 527               }
 528           if (_M_traits.isctype(__ch, _M_class_set))
 529             __ret = true;
 530           else if (std::find(_M_equiv_set.begin(), _M_equiv_set.end(),
 531                              _M_traits.transform_primary(&__ch, &__ch+1))
 532                    != _M_equiv_set.end())
 533             __ret = true;
 534           else
 535             {
 536               for (auto& __it : _M_neg_class_set)
 537                 if (!_M_traits.isctype(__ch, __it))
 538                   {
 539                     __ret = true;
 540                     break;
 541                   }
 542             }
 543         }
 544       if (_M_is_non_matching)
 545         return !__ret;
 546       else
 547         return __ret;
 548     }
 549
 550 _GLIBCXX_END_NAMESPACE_VERSION
 551 } // namespace __detail
 552 } // namespace