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

   1 // class template regex -*- C++ -*-
   2
   3 // Copyright (C) 2013 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 namespace std _GLIBCXX_VISIBILITY(default)
  32 {
  33 namespace __detail
  34 {
  35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  36
  37   template<typename _BiIter>
  38     void
  39     _Scanner<_BiIter>::
  40     _M_advance()
  41     {
  42       if (_M_current == _M_end)
  43         {
  44           _M_curToken = _S_token_eof;
  45           return;
  46         }
  47
  48       _CharT __c = *_M_current;
  49       if (_M_state & _S_state_in_bracket)
  50         {
  51           _M_scan_in_bracket();
  52           return;
  53         }
  54       if (_M_state & _S_state_in_brace)
  55         {
  56           _M_scan_in_brace();
  57           return;
  58         }
  59 #if 0
  60       // TODO: re-enable line anchors when _M_assertion is implemented.
  61       // See PR libstdc++/47724
  62       else if (_M_state & _S_state_at_start && __c == _M_ctype.widen('^'))
  63         {
  64           _M_curToken = _S_token_line_begin;
  65           ++_M_current;
  66           return;
  67         }
  68       else if (__c == _M_ctype.widen('$'))
  69         {
  70           _M_curToken = _S_token_line_end;
  71           ++_M_current;
  72           return;
  73         }
  74 #endif
  75       else if (__c == _M_ctype.widen('.'))
  76         {
  77           _M_curToken = _S_token_anychar;
  78           ++_M_current;
  79           return;
  80         }
  81       else if (__c == _M_ctype.widen('*'))
  82         {
  83           _M_curToken = _S_token_closure0;
  84           ++_M_current;
  85           return;
  86         }
  87       else if (__c == _M_ctype.widen('+'))
  88         {
  89           _M_curToken = _S_token_closure1;
  90           ++_M_current;
  91           return;
  92         }
  93       else if (__c == _M_ctype.widen('|'))
  94         {
  95           _M_curToken = _S_token_or;
  96           ++_M_current;
  97           return;
  98         }
  99       else if (__c == _M_ctype.widen('['))
 100         {
 101           if (*++_M_current == _M_ctype.widen('^'))
 102             {
 103               _M_curToken = _S_token_bracket_inverse_begin;
 104               ++_M_current;
 105             }
 106           else
 107             _M_curToken = _S_token_bracket_begin;
 108           _M_state |= _S_state_in_bracket;
 109           return;
 110         }
 111       else if (__c == _M_ctype.widen('\\'))
 112         {
 113           _M_eat_escape();
 114           return;
 115         }
 116       else if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 117         {
 118           if (__c == _M_ctype.widen('('))
 119             {
 120               _M_curToken = _S_token_subexpr_begin;
 121               ++_M_current;
 122               return;
 123             }
 124           else if (__c == _M_ctype.widen(')'))
 125             {
 126               _M_curToken = _S_token_subexpr_end;
 127               ++_M_current;
 128               return;
 129             }
 130           else if (__c == _M_ctype.widen('{'))
 131             {
 132               _M_curToken = _S_token_interval_begin;
 133               _M_state |= _S_state_in_brace;
 134               ++_M_current;
 135               return;
 136             }
 137         }
 138
 139       _M_curToken = _S_token_ord_char;
 140       _M_curValue.assign(1, __c);
 141       ++_M_current;
 142     }
 143
 144   template<typename _BiIter>
 145     void
 146     _Scanner<_BiIter>::
 147     _M_scan_in_brace()
 148     {
 149       if (_M_ctype.is(_CtypeT::digit, *_M_current))
 150         {
 151           _M_curToken = _S_token_dup_count;
 152           _M_curValue.assign(1, *_M_current);
 153           ++_M_current;
 154           while (_M_current != _M_end
 155                  && _M_ctype.is(_CtypeT::digit, *_M_current))
 156             {
 157               _M_curValue += *_M_current;
 158               ++_M_current;
 159             }
 160           return;
 161         }
 162       else if (*_M_current == _M_ctype.widen(','))
 163         {
 164           _M_curToken = _S_token_comma;
 165           ++_M_current;
 166           return;
 167         }
 168       if (_M_flags & (regex_constants::basic | regex_constants::grep))
 169         {
 170           if (*_M_current == _M_ctype.widen('\\'))
 171             _M_eat_escape();
 172         }
 173       else
 174         {
 175           if (*_M_current == _M_ctype.widen('}'))
 176             {
 177               _M_curToken = _S_token_interval_end;
 178               _M_state &= ~_S_state_in_brace;
 179               ++_M_current;
 180               return;
 181             }
 182         }
 183     }
 184
 185   template<typename _BiIter>
 186     void
 187     _Scanner<_BiIter>::
 188     _M_scan_in_bracket()
 189     {
 190       if (*_M_current == _M_ctype.widen('['))
 191         {
 192           ++_M_current;
 193           if (_M_current == _M_end)
 194             {
 195               _M_curToken = _S_token_eof;
 196               return;
 197             }
 198
 199           if (*_M_current == _M_ctype.widen('.'))
 200             {
 201               _M_curToken = _S_token_collsymbol;
 202               _M_eat_collsymbol();
 203               return;
 204             }
 205           else if (*_M_current == _M_ctype.widen(':'))
 206             {
 207               _M_curToken = _S_token_char_class_name;
 208               _M_eat_charclass();
 209               return;
 210             }
 211           else if (*_M_current == _M_ctype.widen('='))
 212             {
 213               _M_curToken = _S_token_equiv_class_name;
 214               _M_eat_equivclass();
 215               return;
 216             }
 217         }
 218       else if (*_M_current == _M_ctype.widen('-'))
 219         {
 220           _M_curToken = _S_token_dash;
 221           ++_M_current;
 222           return;
 223         }
 224       else if (*_M_current == _M_ctype.widen(']'))
 225         {
 226           _M_curToken = _S_token_bracket_end;
 227           _M_state &= ~_S_state_in_bracket;
 228           ++_M_current;
 229           return;
 230         }
 231       else if (*_M_current == _M_ctype.widen('\\'))
 232         {
 233           _M_eat_escape();
 234           return;
 235         }
 236       _M_curToken = _S_token_collelem_single;
 237       _M_curValue.assign(1, *_M_current);
 238       ++_M_current;
 239     }
 240
 241   // TODO Complete it.
 242   template<typename _BiIter>
 243     void
 244     _Scanner<_BiIter>::
 245     _M_eat_escape()
 246     {
 247       ++_M_current;
 248       if (_M_current == _M_end)
 249         {
 250           _M_curToken = _S_token_eof;
 251           return;
 252         }
 253       _CharT __c = *_M_current;
 254       ++_M_current;
 255
 256       if (__c == _M_ctype.widen('('))
 257         {
 258           if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 259             {
 260               _M_curToken = _S_token_ord_char;
 261               _M_curValue.assign(1, __c);
 262             }
 263           else
 264             _M_curToken = _S_token_subexpr_begin;
 265         }
 266       else if (__c == _M_ctype.widen(')'))
 267         {
 268           if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 269             {
 270               _M_curToken = _S_token_ord_char;
 271               _M_curValue.assign(1, __c);
 272             }
 273           else
 274             _M_curToken = _S_token_subexpr_end;
 275         }
 276       else if (__c == _M_ctype.widen('{'))
 277         {
 278           if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 279             {
 280               _M_curToken = _S_token_ord_char;
 281               _M_curValue.assign(1, __c);
 282             }
 283           else
 284             {
 285               _M_curToken = _S_token_interval_begin;
 286               _M_state |= _S_state_in_brace;
 287             }
 288         }
 289       else if (__c == _M_ctype.widen('}'))
 290         {
 291           if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
 292             {
 293               _M_curToken = _S_token_ord_char;
 294               _M_curValue.assign(1, __c);
 295             }
 296           else
 297             {
 298               if (!(_M_state && _S_state_in_brace))
 299                 __throw_regex_error(regex_constants::error_badbrace);
 300               _M_state &= ~_S_state_in_brace;
 301               _M_curToken = _S_token_interval_end;
 302             }
 303         }
 304       else if (__c == _M_ctype.widen('x'))
 305         {
 306           ++_M_current;
 307           if (_M_current == _M_end)
 308             {
 309               _M_curToken = _S_token_eof;
 310               return;
 311             }
 312           if (_M_ctype.is(_CtypeT::digit, *_M_current))
 313             {
 314               _M_curValue.assign(1, *_M_current);
 315               ++_M_current;
 316               if (_M_current == _M_end)
 317                 {
 318                   _M_curToken = _S_token_eof;
 319                   return;
 320                 }
 321               if (_M_ctype.is(_CtypeT::digit, *_M_current))
 322                 {
 323                   _M_curValue += *_M_current;
 324                   ++_M_current;
 325                   return;
 326                 }
 327             }
 328         }
 329       else if (__c == _M_ctype.widen('^')
 330                || __c == _M_ctype.widen('.')
 331                || __c == _M_ctype.widen('*')
 332                || __c == _M_ctype.widen('$')
 333                || __c == _M_ctype.widen('\\'))
 334         {
 335           _M_curToken = _S_token_ord_char;
 336           _M_curValue.assign(1, __c);
 337         }
 338       else if (_M_ctype.is(_CtypeT::digit, __c))
 339         {
 340           _M_curToken = _S_token_backref;
 341           _M_curValue.assign(1, __c);
 342         }
 343       else if (_M_state & _S_state_in_bracket)
 344         {
 345           if (__c == _M_ctype.widen('-')
 346               || __c == _M_ctype.widen('[')
 347               || __c == _M_ctype.widen(']'))
 348             {
 349               _M_curToken = _S_token_ord_char;
 350               _M_curValue.assign(1, __c);
 351             }
 352           else if ((_M_flags & regex_constants::ECMAScript)
 353                    && __c == _M_ctype.widen('b'))
 354             {
 355               _M_curToken = _S_token_ord_char;
 356               _M_curValue.assign(1, _M_ctype.widen(' '));
 357             }
 358           else
 359             __throw_regex_error(regex_constants::error_escape);
 360         }
 361       else
 362         __throw_regex_error(regex_constants::error_escape);
 363     }
 364
 365   // Eats a character class or throwns an exception.
 366   // current point to ':' delimiter on entry, char after ']' on return
 367   template<typename _BiIter>
 368     void
 369     _Scanner<_BiIter>::
 370     _M_eat_charclass()
 371     {
 372       ++_M_current; // skip ':'
 373       if (_M_current == _M_end)
 374         __throw_regex_error(regex_constants::error_ctype);
 375       for (_M_curValue.clear();
 376            _M_current != _M_end && *_M_current != _M_ctype.widen(':');
 377            ++_M_current)
 378         _M_curValue += *_M_current;
 379       if (_M_current == _M_end)
 380         __throw_regex_error(regex_constants::error_ctype);
 381       ++_M_current; // skip ':'
 382       if (*_M_current != _M_ctype.widen(']'))
 383         __throw_regex_error(regex_constants::error_ctype);
 384       ++_M_current; // skip ']'
 385     }
 386
 387
 388   template<typename _BiIter>
 389     void
 390     _Scanner<_BiIter>::
 391     _M_eat_equivclass()
 392     {
 393       ++_M_current; // skip '='
 394       if (_M_current == _M_end)
 395         __throw_regex_error(regex_constants::error_collate);
 396       for (_M_curValue.clear();
 397            _M_current != _M_end && *_M_current != _M_ctype.widen('=');
 398            ++_M_current)
 399         _M_curValue += *_M_current;
 400       if (_M_current == _M_end)
 401         __throw_regex_error(regex_constants::error_collate);
 402       ++_M_current; // skip '='
 403       if (*_M_current != _M_ctype.widen(']'))
 404         __throw_regex_error(regex_constants::error_collate);
 405       ++_M_current; // skip ']'
 406     }
 407
 408
 409   template<typename _BiIter>
 410     void
 411     _Scanner<_BiIter>::
 412     _M_eat_collsymbol()
 413     {
 414       ++_M_current; // skip '.'
 415       if (_M_current == _M_end)
 416         __throw_regex_error(regex_constants::error_collate);
 417       for (_M_curValue.clear();
 418            _M_current != _M_end && *_M_current != _M_ctype.widen('.');
 419            ++_M_current)
 420         _M_curValue += *_M_current;
 421       if (_M_current == _M_end)
 422         __throw_regex_error(regex_constants::error_collate);
 423       ++_M_current; // skip '.'
 424       if (*_M_current != _M_ctype.widen(']'))
 425         __throw_regex_error(regex_constants::error_collate);
 426       ++_M_current; // skip ']'
 427     }
 428
 429 #ifdef _GLIBCXX_DEBUG
 430   template<typename _BiIter>
 431     std::ostream&
 432     _Scanner<_BiIter>::
 433     _M_print(std::ostream& ostr)
 434     {
 435       switch (_M_curToken)
 436       {
 437         case _S_token_anychar:
 438           ostr << "any-character\n";
 439           break;
 440         case _S_token_backref:
 441           ostr << "backref\n";
 442           break;
 443         case _S_token_bracket_begin:
 444           ostr << "bracket-begin\n";
 445           break;
 446         case _S_token_bracket_inverse_begin:
 447           ostr << "bracket-inverse-begin\n";
 448           break;
 449         case _S_token_bracket_end:
 450           ostr << "bracket-end\n";
 451           break;
 452         case _S_token_char_class_name:
 453           ostr << "char-class-name \"" << _M_curValue << "\"\n";
 454           break;
 455         case _S_token_closure0:
 456           ostr << "closure0\n";
 457           break;
 458         case _S_token_closure1:
 459           ostr << "closure1\n";
 460           break;
 461         case _S_token_collelem_multi:
 462           ostr << "coll-elem-multi \"" << _M_curValue << "\"\n";
 463           break;
 464         case _S_token_collelem_single:
 465           ostr << "coll-elem-single \"" << _M_curValue << "\"\n";
 466           break;
 467         case _S_token_collsymbol:
 468           ostr << "collsymbol \"" << _M_curValue << "\"\n";
 469           break;
 470         case _S_token_comma:
 471           ostr << "comma\n";
 472           break;
 473         case _S_token_dash:
 474           ostr << "dash\n";
 475           break;
 476         case _S_token_dup_count:
 477           ostr << "dup count: " << _M_curValue << "\n";
 478           break;
 479         case _S_token_eof:
 480           ostr << "EOF\n";
 481           break;
 482         case _S_token_equiv_class_name:
 483           ostr << "equiv-class-name \"" << _M_curValue << "\"\n";
 484           break;
 485         case _S_token_interval_begin:
 486           ostr << "interval begin\n";
 487           break;
 488         case _S_token_interval_end:
 489           ostr << "interval end\n";
 490           break;
 491         case _S_token_line_begin:
 492           ostr << "line begin\n";
 493           break;
 494         case _S_token_line_end:
 495           ostr << "line end\n";
 496           break;
 497         case _S_token_opt:
 498           ostr << "opt\n";
 499           break;
 500         case _S_token_or:
 501           ostr << "or\n";
 502           break;
 503         case _S_token_ord_char:
 504           ostr << "ordinary character: \"" << _M_value() << "\"\n";
 505           break;
 506         case _S_token_subexpr_begin:
 507           ostr << "subexpr begin\n";
 508           break;
 509         case _S_token_subexpr_end:
 510           ostr << "subexpr end\n";
 511           break;
 512         case _S_token_word_begin:
 513           ostr << "word begin\n";
 514           break;
 515         case _S_token_word_end:
 516           ostr << "word end\n";
 517           break;
 518         case _S_token_unknown:
 519           ostr << "-- unknown token --\n";
 520           break;
 521         default:
 522           _GLIBCXX_DEBUG_ASSERT(false);
 523       }
 524       return ostr;
 525     }
 526 #endif
 527
 528   template<typename _InputIter, typename _CharT, typename _TraitsT>
 529     _Compiler<_InputIter, _CharT, _TraitsT>::
 530     _Compiler(_InputIter __b, _InputIter __e,
 531               const _TraitsT& __traits, _FlagT __flags)
 532     : _M_traits(__traits), _M_scanner(__b, __e, __flags, _M_traits.getloc()),
 533       _M_state_store(__flags), _M_flags(__flags)
 534     {
 535       _StateSeqT __r(_M_state_store,
 536                     _M_state_store._M_insert_subexpr_begin());
 537       _M_disjunction();
 538       if (!_M_stack.empty())
 539         {
 540           __r._M_append(_M_stack.top());
 541           _M_stack.pop();
 542         }
 543       __r._M_append(_M_state_store._M_insert_subexpr_end());
 544       __r._M_append(_M_state_store._M_insert_accept());
 545     }
 546
 547   template<typename _InputIter, typename _CharT, typename _TraitsT>
 548     bool
 549     _Compiler<_InputIter, _CharT, _TraitsT>::
 550     _M_match_token(_Compiler<_InputIter, _CharT, _TraitsT>::_TokenT token)
 551     {
 552       if (token == _M_scanner._M_token())
 553         {
 554           _M_cur_value = _M_scanner._M_value();
 555           _M_scanner._M_advance();
 556           return true;
 557         }
 558       return false;
 559     }
 560
 561   template<typename _InputIter, typename _CharT, typename _TraitsT>
 562     void
 563     _Compiler<_InputIter, _CharT, _TraitsT>::
 564     _M_disjunction()
 565     {
 566       this->_M_alternative();
 567       if (_M_match_token(_ScannerT::_S_token_or))
 568         {
 569           _StateSeqT __alt1 = _M_stack.top(); _M_stack.pop();
 570           this->_M_disjunction();
 571           _StateSeqT __alt2 = _M_stack.top(); _M_stack.pop();
 572           _M_stack.push(_StateSeqT(__alt1, __alt2));
 573         }
 574     }
 575
 576   template<typename _InputIter, typename _CharT, typename _TraitsT>
 577     void
 578     _Compiler<_InputIter, _CharT, _TraitsT>::
 579     _M_alternative()
 580     {
 581       if (this->_M_term())
 582         {
 583           _StateSeqT __re = _M_stack.top(); _M_stack.pop();
 584           this->_M_alternative();
 585           if (!_M_stack.empty())
 586             {
 587               __re._M_append(_M_stack.top());
 588               _M_stack.pop();
 589             }
 590           _M_stack.push(__re);
 591         }
 592     }
 593
 594   template<typename _InputIter, typename _CharT, typename _TraitsT>
 595     bool
 596     _Compiler<_InputIter, _CharT, _TraitsT>::
 597     _M_term()
 598     {
 599       if (this->_M_assertion())
 600         return true;
 601       if (this->_M_atom())
 602         {
 603           this->_M_quantifier();
 604           return true;
 605         }
 606       return false;
 607     }
 608
 609   template<typename _InputIter, typename _CharT, typename _TraitsT>
 610     bool
 611     _Compiler<_InputIter, _CharT, _TraitsT>::
 612     _M_assertion()
 613     {
 614       if (_M_match_token(_ScannerT::_S_token_line_begin))
 615         {
 616           // __m.push(_Matcher::_S_opcode_line_begin);
 617           return true;
 618         }
 619       if (_M_match_token(_ScannerT::_S_token_line_end))
 620         {
 621           // __m.push(_Matcher::_S_opcode_line_end);
 622           return true;
 623         }
 624       if (_M_match_token(_ScannerT::_S_token_word_begin))
 625         {
 626           // __m.push(_Matcher::_S_opcode_word_begin);
 627           return true;
 628         }
 629       if (_M_match_token(_ScannerT::_S_token_word_end))
 630         {
 631           // __m.push(_Matcher::_S_opcode_word_end);
 632           return true;
 633         }
 634       return false;
 635     }
 636
 637   template<typename _InputIter, typename _CharT, typename _TraitsT>
 638     void
 639     _Compiler<_InputIter, _CharT, _TraitsT>::
 640     _M_quantifier()
 641     {
 642       if (_M_match_token(_ScannerT::_S_token_closure0))
 643         {
 644           if (_M_stack.empty())
 645             __throw_regex_error(regex_constants::error_badrepeat);
 646           _StateSeqT __r(_M_stack.top(), -1);
 647           __r._M_append(__r._M_front());
 648           _M_stack.pop();
 649           _M_stack.push(__r);
 650           return;
 651         }
 652       if (_M_match_token(_ScannerT::_S_token_closure1))
 653         {
 654           if (_M_stack.empty())
 655             __throw_regex_error(regex_constants::error_badrepeat);
 656           _StateSeqT __r(_M_state_store,
 657                         _M_state_store.
 658                         _M_insert_alt(_S_invalid_state_id,
 659                                       _M_stack.top()._M_front()));
 660           _M_stack.top()._M_append(__r);
 661           return;
 662         }
 663       if (_M_match_token(_ScannerT::_S_token_opt))
 664         {
 665           if (_M_stack.empty())
 666           __throw_regex_error(regex_constants::error_badrepeat);
 667           _StateSeqT __r(_M_stack.top(), -1);
 668           _M_stack.pop();
 669           _M_stack.push(__r);
 670           return;
 671         }
 672       if (_M_match_token(_ScannerT::_S_token_interval_begin))
 673         {
 674           if (_M_stack.empty())
 675             __throw_regex_error(regex_constants::error_badrepeat);
 676           if (!_M_match_token(_ScannerT::_S_token_dup_count))
 677             __throw_regex_error(regex_constants::error_badbrace);
 678           _StateSeqT __r(_M_stack.top());
 679           int __min_rep = _M_cur_int_value(10);
 680           for (int __i = 1; __i < __min_rep; ++__i)
 681             _M_stack.top()._M_append(__r._M_clone());
 682           if (_M_match_token(_ScannerT::_S_token_comma))
 683             if (_M_match_token(_ScannerT::_S_token_dup_count))
 684               {
 685                 int __n = _M_cur_int_value(10) - __min_rep;
 686                 if (__n < 0)
 687                   __throw_regex_error(regex_constants::error_badbrace);
 688                 for (int __i = 0; __i < __n; ++__i)
 689                   {
 690                     _StateSeqT __r(_M_state_store,
 691                                   _M_state_store.
 692                                   _M_insert_alt(_S_invalid_state_id,
 693                                                 _M_stack.top()._M_front()));
 694                     _M_stack.top()._M_append(__r);
 695                   }
 696               }
 697             else
 698               {
 699                 _StateSeqT __r(_M_stack.top(), -1);
 700                 __r._M_push_back(__r._M_front());
 701                 _M_stack.pop();
 702                 _M_stack.push(__r);
 703               }
 704           if (!_M_match_token(_ScannerT::_S_token_interval_end))
 705             __throw_regex_error(regex_constants::error_brace);
 706           return;
 707         }
 708     }
 709
 710   template<typename _InputIter, typename _CharT, typename _TraitsT>
 711     bool
 712     _Compiler<_InputIter, _CharT, _TraitsT>::
 713     _M_atom()
 714     {
 715       if (_M_match_token(_ScannerT::_S_token_anychar))
 716         {
 717           const static auto&
 718           __any_matcher = [](_CharT) -> bool
 719           { return true; };
 720
 721           _M_stack.push(_StateSeqT(_M_state_store,
 722                                   _M_state_store._M_insert_matcher
 723                                   (__any_matcher)));
 724           return true;
 725         }
 726       if (_M_match_token(_ScannerT::_S_token_ord_char))
 727         {
 728           auto __c = _M_cur_value[0];
 729           __detail::_Matcher<_CharT> f;
 730           if (_M_flags & regex_constants::icase)
 731             {
 732               auto __traits = this->_M_traits;
 733               __c = __traits.translate_nocase(__c);
 734               f = [__traits, __c](_CharT __ch) -> bool
 735               { return __traits.translate_nocase(__ch) == __c; };
 736             }
 737           else
 738             f = [__c](_CharT __ch) -> bool
 739             { return __ch == __c; };
 740
 741           _M_stack.push(_StateSeqT(_M_state_store,
 742                                    _M_state_store._M_insert_matcher(f)));
 743           return true;
 744         }
 745       if (_M_match_token(_ScannerT::_S_token_backref))
 746         {
 747           // __m.push(_Matcher::_S_opcode_ordchar, _M_cur_value);
 748           _M_stack.push(_StateSeqT(_M_state_store, _M_state_store.
 749                                    _M_insert_backref(_M_cur_int_value(10))));
 750           return true;
 751         }
 752       if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
 753         {
 754           int __mark = _M_state_store._M_sub_count();
 755           _StateSeqT __r(_M_state_store,
 756                         _M_state_store.
 757                         _M_insert_subexpr_begin());
 758           this->_M_disjunction();
 759           if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
 760             __throw_regex_error(regex_constants::error_paren);
 761           if (!_M_stack.empty())
 762             {
 763               __r._M_append(_M_stack.top());
 764               _M_stack.pop();
 765             }
 766           __r._M_append(_M_state_store._M_insert_subexpr_end());
 767           _M_stack.push(__r);
 768           return true;
 769         }
 770       return _M_bracket_expression();
 771     }
 772
 773   template<typename _InputIter, typename _CharT, typename _TraitsT>
 774     bool
 775     _Compiler<_InputIter, _CharT, _TraitsT>::
 776     _M_bracket_expression()
 777     {
 778       bool __inverse =
 779         _M_match_token(_ScannerT::_S_token_bracket_inverse_begin);
 780       if (!(__inverse || _M_match_token(_ScannerT::_S_token_bracket_begin)))
 781         return false;
 782       _BMatcherT __matcher( __inverse, _M_traits, _M_flags);
 783       // special case: only if  _not_ chr first after
 784       // '[' or '[^' or if ECMAscript
 785       if (!_M_bracket_list(__matcher) // list is empty
 786           && !(_M_flags & regex_constants::ECMAScript))
 787         __throw_regex_error(regex_constants::error_brack);
 788       _M_stack.push(_StateSeqT(_M_state_store,
 789                               _M_state_store._M_insert_matcher(__matcher)));
 790       return true;
 791     }
 792
 793   template<typename _InputIter, typename _CharT, typename _TraitsT>
 794     bool // list is non-empty
 795     _Compiler<_InputIter, _CharT, _TraitsT>::
 796     _M_bracket_list(_BMatcherT& __matcher)
 797     {
 798       if (_M_match_token(_ScannerT::_S_token_bracket_end))
 799         return false;
 800       _M_expression_term(__matcher);
 801       _M_bracket_list(__matcher);
 802       return true;
 803     }
 804
 805   template<typename _InputIter, typename _CharT, typename _TraitsT>
 806     void
 807     _Compiler<_InputIter, _CharT, _TraitsT>::
 808     _M_expression_term(_BMatcherT& __matcher)
 809     {
 810       if (_M_match_token(_ScannerT::_S_token_collsymbol))
 811         {
 812           __matcher._M_add_collating_element(_M_cur_value);
 813           return;
 814         }
 815       if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
 816         {
 817           __matcher._M_add_equivalence_class(_M_cur_value);
 818           return;
 819         }
 820       if (_M_match_token(_ScannerT::_S_token_char_class_name))
 821         {
 822           __matcher._M_add_character_class(_M_cur_value);
 823           return;
 824         }
 825       if (_M_match_token(_ScannerT::_S_token_collelem_single)) // [a
 826         {
 827           auto __ch = _M_cur_value[0];
 828           if (_M_match_token(_ScannerT::_S_token_dash)) // [a-
 829             {
 830               // If the dash is the last character in the bracket expression,
 831               // it is not special.
 832               if (_M_scanner._M_token() == _ScannerT::_S_token_bracket_end)
 833                 __matcher._M_add_char(_M_cur_value[0]); // [a-] <=> [a\-]
 834               else // [a-z]
 835                 {
 836                   if (!_M_match_token(_ScannerT::_S_token_collelem_single))
 837                     __throw_regex_error(regex_constants::error_range);
 838                   __matcher._M_make_range(__ch, _M_cur_value[0]);
 839                 }
 840             }
 841           else // [a]
 842             __matcher._M_add_char(__ch);
 843           return;
 844         }
 845       __throw_regex_error(regex_constants::error_brack);
 846     }
 847
 848   template<typename _InputIter, typename _CharT, typename _TraitsT>
 849     int
 850     _Compiler<_InputIter, _CharT, _TraitsT>::
 851     _M_cur_int_value(int __radix)
 852     {
 853       int __v = 0;
 854       for (typename _StringT::size_type __i = 0;
 855            __i < _M_cur_value.length(); ++__i)
 856         __v =__v * __radix + _M_traits.value(_M_cur_value[__i], __radix);
 857       return __v;
 858     }
 859
 860   template<typename _CharT, typename _TraitsT>
 861     bool _BracketMatcher<_CharT, _TraitsT>::
 862     operator()(_CharT __ch) const
 863     {
 864       auto __oldch = __ch;
 865       if (_M_flags & regex_constants::collate)
 866         if (_M_is_icase())
 867           __ch = _M_traits.translate_nocase(__ch);
 868         else
 869           __ch = _M_traits.translate(__ch);
 870
 871       bool __ret = false;
 872       for (auto __c : _M_char_set)
 873         if (__c == __ch)
 874           {
 875             __ret = true;
 876             break;
 877           }
 878       if (!__ret && _M_traits.isctype(__oldch, _M_class_set))
 879         __ret = true;
 880       else
 881         {
 882           _StringT __s = _M_get_str(__ch);
 883           for (auto& __it : _M_range_set)
 884             if (__it.first <= __s && __s <= __it.second)
 885               {
 886                 __ret = true;
 887                 break;
 888               }
 889         }
 890       if (_M_is_non_matching)
 891         __ret = !__ret;
 892       return __ret;
 893     }
 894
 895 _GLIBCXX_END_NAMESPACE_VERSION
 896 } // namespace __detail
 897 } // namespace