[thirdparty/gcc.git] / libstdc++-v3 / include / bits / regex_compiler.tcc

// class template regex -*- C++ -*-

// Copyright (C) 2013-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/**
 *  @file bits/regex_compiler.tcc
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{regex}
 */

// FIXME make comments doxygen format.

// This compiler refers to "Regular Expression Matching Can Be Simple And Fast"
// (http://swtch.com/~rsc/regexp/regexp1.html"),
// but doesn't strictly follow it.
//
// When compiling, states are *chained* instead of tree- or graph-constructed.
// It's more like structured programs: there's if statement and loop statement.
//
// For alternative structure (say "a|b"), aka "if statement", two branches
// should be constructed. However, these two shall merge to an "end_tag" at
// the end of this operator:
//
//                branch1
//              /        \
// => begin_tag            end_tag =>
//              \        /
//                branch2
//
// This is the difference between this implementation and that in Russ's
// article.
//
// That's why we introduced dummy node here ------ "end_tag" is a dummy node.
// All dummy node will be eliminated at the end of compiling process.

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __detail
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  template<typename _TraitsT>
    _Compiler<_TraitsT>::
    _Compiler(_IterT __b, _IterT __e,
	      const typename _TraitsT::locale_type& __loc, _FlagT __flags)
    : _M_flags((__flags
		& (regex_constants::ECMAScript
		   | regex_constants::basic
		   | regex_constants::extended
		   | regex_constants::grep
		   | regex_constants::egrep
		   | regex_constants::awk))
	       ? __flags
	       : __flags | regex_constants::ECMAScript),
      _M_scanner(__b, __e, _M_flags, __loc),
      _M_nfa(make_shared<_RegexT>(__loc, _M_flags)),
      _M_traits(_M_nfa->_M_traits),
      _M_ctype(std::use_facet<_CtypeT>(__loc))
    {
      _StateSeqT __r(*_M_nfa, _M_nfa->_M_start());
      __r._M_append(_M_nfa->_M_insert_subexpr_begin());
      this->_M_disjunction();
      if (!_M_match_token(_ScannerT::_S_token_eof))
	__throw_regex_error(regex_constants::error_paren);
      __r._M_append(_M_pop());
      _GLIBCXX_DEBUG_ASSERT(_M_stack.empty());
      __r._M_append(_M_nfa->_M_insert_subexpr_end());
      __r._M_append(_M_nfa->_M_insert_accept());
      _M_nfa->_M_eliminate_dummy();
    }

  template<typename _TraitsT>
    void
    _Compiler<_TraitsT>::
    _M_disjunction()
    {
      this->_M_alternative();
      while (_M_match_token(_ScannerT::_S_token_or))
	{
	  _StateSeqT __alt1 = _M_pop();
	  this->_M_alternative();
	  _StateSeqT __alt2 = _M_pop();
	  auto __end = _M_nfa->_M_insert_dummy();
	  __alt1._M_append(__end);
	  __alt2._M_append(__end);
	  // __alt2 is state._M_next, __alt1 is state._M_alt. The executor
	  // executes _M_alt before _M_next, as well as executing left
	  // alternative before right one.
	  _M_stack.push(_StateSeqT(*_M_nfa,
				   _M_nfa->_M_insert_alt(
				     __alt2._M_start, __alt1._M_start, false),
				   __end));
	}
    }

  template<typename _TraitsT>
    void
    _Compiler<_TraitsT>::
    _M_alternative()
    {
      if (this->_M_term())
	{
	  _StateSeqT __re = _M_pop();
	  this->_M_alternative();
	  __re._M_append(_M_pop());
	  _M_stack.push(__re);
	}
      else
	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_dummy()));
    }

  template<typename _TraitsT>
    bool
    _Compiler<_TraitsT>::
    _M_term()
    {
      if (this->_M_assertion())
	return true;
      if (this->_M_atom())
	{
	  while (this->_M_quantifier());
	  return true;
	}
      return false;
    }

  template<typename _TraitsT>
    bool
    _Compiler<_TraitsT>::
    _M_assertion()
    {
      if (_M_match_token(_ScannerT::_S_token_line_begin))
	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_begin()));
      else if (_M_match_token(_ScannerT::_S_token_line_end))
	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_end()));
      else if (_M_match_token(_ScannerT::_S_token_word_bound))
	// _M_value[0] == 'n' means it's negative, say "not word boundary".
	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->
	      _M_insert_word_bound(_M_value[0] == 'n')));
      else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin))
	{
	  auto __neg = _M_value[0] == 'n';
	  this->_M_disjunction();
	  if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
	    __throw_regex_error(regex_constants::error_paren);
	  auto __tmp = _M_pop();
	  __tmp._M_append(_M_nfa->_M_insert_accept());
	  _M_stack.push(
	      _StateSeqT(
		*_M_nfa,
		_M_nfa->_M_insert_lookahead(__tmp._M_start, __neg)));
	}
      else
	return false;
      return true;
    }

  template<typename _TraitsT>
    bool
    _Compiler<_TraitsT>::
    _M_quantifier()
    {
      bool __neg = (_M_flags & regex_constants::ECMAScript);
      auto __init = [this, &__neg]()
	{
	  if (_M_stack.empty())
	    __throw_regex_error(regex_constants::error_badrepeat);
	  __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
	};
      if (_M_match_token(_ScannerT::_S_token_closure0))
	{
	  __init();
	  auto __e = _M_pop();
	  _StateSeqT __r(*_M_nfa,
			 _M_nfa->_M_insert_repeat(_S_invalid_state_id,
						  __e._M_start, __neg));
	  __e._M_append(__r);
	  _M_stack.push(__r);
	}
      else if (_M_match_token(_ScannerT::_S_token_closure1))
	{
	  __init();
	  auto __e = _M_pop();
	  __e._M_append(_M_nfa->_M_insert_repeat(_S_invalid_state_id,
						 __e._M_start, __neg));
	  _M_stack.push(__e);
	}
      else if (_M_match_token(_ScannerT::_S_token_opt))
	{
	  __init();
	  auto __e = _M_pop();
	  auto __end = _M_nfa->_M_insert_dummy();
	  _StateSeqT __r(*_M_nfa,
			 _M_nfa->_M_insert_repeat(_S_invalid_state_id,
						  __e._M_start, __neg));
	  __e._M_append(__end);
	  __r._M_append(__end);
	  _M_stack.push(__r);
	}
      else if (_M_match_token(_ScannerT::_S_token_interval_begin))
	{
	  if (_M_stack.empty())
	    __throw_regex_error(regex_constants::error_badrepeat);
	  if (!_M_match_token(_ScannerT::_S_token_dup_count))
	    __throw_regex_error(regex_constants::error_badbrace);
	  _StateSeqT __r(_M_pop());
	  _StateSeqT __e(*_M_nfa, _M_nfa->_M_insert_dummy());
	  long __min_rep = _M_cur_int_value(10);
	  bool __infi = false;
	  long __n;

	  // {3
	  if (_M_match_token(_ScannerT::_S_token_comma))
	    if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7}
	      __n = _M_cur_int_value(10) - __min_rep;
	    else
	      __infi = true;
	  else
	    __n = 0;
	  if (!_M_match_token(_ScannerT::_S_token_interval_end))
	    __throw_regex_error(regex_constants::error_brace);

	  __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);

	  for (long __i = 0; __i < __min_rep; ++__i)
	    __e._M_append(__r._M_clone());

	  if (__infi)
	    {
	      auto __tmp = __r._M_clone();
	      _StateSeqT __s(*_M_nfa,
			     _M_nfa->_M_insert_repeat(_S_invalid_state_id,
						      __tmp._M_start, __neg));
	      __tmp._M_append(__s);
	      __e._M_append(__s);
	    }
	  else
	    {
	      if (__n < 0)
		__throw_regex_error(regex_constants::error_badbrace);
	      auto __end = _M_nfa->_M_insert_dummy();
	      // _M_alt is the "match more" branch, and _M_next is the
	      // "match less" one. Switch _M_alt and _M_next of all created
	      // nodes. This is a hack but IMO works well.
	      std::stack<_StateIdT> __stack;
	      for (long __i = 0; __i < __n; ++__i)
		{
		  auto __tmp = __r._M_clone();
		  auto __alt = _M_nfa->_M_insert_repeat(__tmp._M_start,
							__end, __neg);
		  __stack.push(__alt);
		  __e._M_append(_StateSeqT(*_M_nfa, __alt, __tmp._M_end));
		}
	      __e._M_append(__end);
	      while (!__stack.empty())
		{
		  auto& __tmp = (*_M_nfa)[__stack.top()];
		  __stack.pop();
		  swap(__tmp._M_next, __tmp._M_alt);
		}
	    }
	  _M_stack.push(__e);
	}
      else
	return false;
      return true;
    }

#define __INSERT_REGEX_MATCHER(__func, args...)\
	do\
	  if (!(_M_flags & regex_constants::icase))\
	    if (!(_M_flags & regex_constants::collate))\
	      __func<false, false>(args);\
	    else\
	      __func<false, true>(args);\
	  else\
	    if (!(_M_flags & regex_constants::collate))\
	      __func<true, false>(args);\
	    else\
	      __func<true, true>(args);\
	while (false)

  template<typename _TraitsT>
    bool
    _Compiler<_TraitsT>::
    _M_atom()
    {
      if (_M_match_token(_ScannerT::_S_token_anychar))
	{
	  if (!(_M_flags & regex_constants::ECMAScript))
	    __INSERT_REGEX_MATCHER(_M_insert_any_matcher_posix);
	  else
	    __INSERT_REGEX_MATCHER(_M_insert_any_matcher_ecma);
	}
      else if (_M_try_char())
	__INSERT_REGEX_MATCHER(_M_insert_char_matcher);
      else if (_M_match_token(_ScannerT::_S_token_backref))
	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->
				 _M_insert_backref(_M_cur_int_value(10))));
      else if (_M_match_token(_ScannerT::_S_token_quoted_class))
	__INSERT_REGEX_MATCHER(_M_insert_character_class_matcher);
      else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin))
	{
	  _StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_dummy());
	  this->_M_disjunction();
	  if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
	    __throw_regex_error(regex_constants::error_paren);
	  __r._M_append(_M_pop());
	  _M_stack.push(__r);
	}
      else if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
	{
	  _StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_subexpr_begin());
	  this->_M_disjunction();
	  if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
	    __throw_regex_error(regex_constants::error_paren);
	  __r._M_append(_M_pop());
	  __r._M_append(_M_nfa->_M_insert_subexpr_end());
	  _M_stack.push(__r);
	}
      else if (!_M_bracket_expression())
	return false;
      return true;
    }

  template<typename _TraitsT>
    bool
    _Compiler<_TraitsT>::
    _M_bracket_expression()
    {
      bool __neg =
	_M_match_token(_ScannerT::_S_token_bracket_neg_begin);
      if (!(__neg || _M_match_token(_ScannerT::_S_token_bracket_begin)))
	return false;
      __INSERT_REGEX_MATCHER(_M_insert_bracket_matcher, __neg);
      return true;
    }
#undef __INSERT_REGEX_MATCHER

  template<typename _TraitsT>
  template<bool __icase, bool __collate>
    void
    _Compiler<_TraitsT>::
    _M_insert_any_matcher_ecma()
    {
      _M_stack.push(_StateSeqT(*_M_nfa,
	_M_nfa->_M_insert_matcher
	  (_AnyMatcher<_TraitsT, true, __icase, __collate>
	    (_M_traits))));
    }

  template<typename _TraitsT>
  template<bool __icase, bool __collate>
    void
    _Compiler<_TraitsT>::
    _M_insert_any_matcher_posix()
    {
      _M_stack.push(_StateSeqT(*_M_nfa,
	_M_nfa->_M_insert_matcher
	  (_AnyMatcher<_TraitsT, false, __icase, __collate>
	    (_M_traits))));
    }

  template<typename _TraitsT>
  template<bool __icase, bool __collate>
    void
    _Compiler<_TraitsT>::
    _M_insert_char_matcher()
    {
      _M_stack.push(_StateSeqT(*_M_nfa,
	_M_nfa->_M_insert_matcher
	  (_CharMatcher<_TraitsT, __icase, __collate>
	    (_M_value[0], _M_traits))));
    }

  template<typename _TraitsT>
  template<bool __icase, bool __collate>
    void
    _Compiler<_TraitsT>::
    _M_insert_character_class_matcher()
    {
      _GLIBCXX_DEBUG_ASSERT(_M_value.size() == 1);
      _BracketMatcher<_TraitsT, __icase, __collate> __matcher
	(_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits);
      __matcher._M_add_character_class(_M_value, false);
      __matcher._M_ready();
      _M_stack.push(_StateSeqT(*_M_nfa,
	_M_nfa->_M_insert_matcher(std::move(__matcher))));
    }

  template<typename _TraitsT>
  template<bool __icase, bool __collate>
    void
    _Compiler<_TraitsT>::
    _M_insert_bracket_matcher(bool __neg)
    {
      _BracketMatcher<_TraitsT, __icase, __collate> __matcher(__neg, _M_traits);
      while (!_M_match_token(_ScannerT::_S_token_bracket_end))
	_M_expression_term(__matcher);
      __matcher._M_ready();
      _M_stack.push(_StateSeqT(
		      *_M_nfa,
		      _M_nfa->_M_insert_matcher(std::move(__matcher))));
    }

  template<typename _TraitsT>
  template<bool __icase, bool __collate>
    void
    _Compiler<_TraitsT>::
    _M_expression_term(_BracketMatcher<_TraitsT, __icase, __collate>& __matcher)
    {
      if (_M_match_token(_ScannerT::_S_token_collsymbol))
	__matcher._M_add_collating_element(_M_value);
      else if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
	__matcher._M_add_equivalence_class(_M_value);
      else if (_M_match_token(_ScannerT::_S_token_char_class_name))
	__matcher._M_add_character_class(_M_value, false);
      else if (_M_try_char()) // [a
	{
	  auto __ch = _M_value[0];
	  if (_M_try_char())
	    {
	      if (_M_value[0] == '-') // [a-
		{
		  if (_M_try_char()) // [a-z]
		    {
		      __matcher._M_make_range(__ch, _M_value[0]);
		      return;
		    }
		  // If the dash is the last character in the bracket
		  // expression, it is not special.
		  if (_M_scanner._M_get_token()
		      != _ScannerT::_S_token_bracket_end)
		    __throw_regex_error(regex_constants::error_range);
		}
	      __matcher._M_add_char(_M_value[0]);
	    }
	  __matcher._M_add_char(__ch);
	}
      else if (_M_match_token(_ScannerT::_S_token_quoted_class))
	__matcher._M_add_character_class(_M_value,
					 _M_ctype.is(_CtypeT::upper,
						     _M_value[0]));
      else
	__throw_regex_error(regex_constants::error_brack);
    }

  template<typename _TraitsT>
    bool
    _Compiler<_TraitsT>::
    _M_try_char()
    {
      bool __is_char = false;
      if (_M_match_token(_ScannerT::_S_token_oct_num))
	{
	  __is_char = true;
	  _M_value.assign(1, _M_cur_int_value(8));
	}
      else if (_M_match_token(_ScannerT::_S_token_hex_num))
	{
	  __is_char = true;
	  _M_value.assign(1, _M_cur_int_value(16));
	}
      else if (_M_match_token(_ScannerT::_S_token_ord_char))
	__is_char = true;
      return __is_char;
    }

  template<typename _TraitsT>
    bool
    _Compiler<_TraitsT>::
    _M_match_token(_TokenT token)
    {
      if (token == _M_scanner._M_get_token())
	{
	  _M_value = _M_scanner._M_get_value();
	  _M_scanner._M_advance();
	  return true;
	}
      return false;
    }

  template<typename _TraitsT>
    int
    _Compiler<_TraitsT>::
    _M_cur_int_value(int __radix)
    {
      long __v = 0;
      for (typename _StringT::size_type __i = 0;
	   __i < _M_value.length(); ++__i)
	__v =__v * __radix + _M_traits.value(_M_value[__i], __radix);
      return __v;
    }

  template<typename _TraitsT, bool __icase, bool __collate>
    bool
    _BracketMatcher<_TraitsT, __icase, __collate>::
    _M_apply(_CharT __ch, false_type) const
    {
      bool __ret = std::binary_search(_M_char_set.begin(), _M_char_set.end(),
				      _M_translator._M_translate(__ch));
      if (!__ret)
	{
	  auto __s = _M_translator._M_transform(__ch);
	  for (auto& __it : _M_range_set)
	    if (__it.first <= __s && __s <= __it.second)
	      {
		__ret = true;
		break;
	      }
	  if (_M_traits.isctype(__ch, _M_class_set))
	    __ret = true;
	  else if (std::find(_M_equiv_set.begin(), _M_equiv_set.end(),
			     _M_traits.transform_primary(&__ch, &__ch+1))
		   != _M_equiv_set.end())
	    __ret = true;
	  else
	    {
	      for (auto& __it : _M_neg_class_set)
		if (!_M_traits.isctype(__ch, __it))
		  {
		    __ret = true;
		    break;
		  }
	    }
	}
      if (_M_is_non_matching)
	return !__ret;
      else
	return __ret;
    }

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace __detail
} // namespace
Commit	Line	Data
6cb784b6 TS	1	// class template regex -- C++ --
6cb784b6 TS	2
aa118a03	3	// Copyright (C) 2013-2014 Free Software Foundation, Inc.
6cb784b6 TS	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
b21abcee	31	// FIXME make comments doxygen format.
7c812a2a TS	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	//
097f0bcf JW	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:
7c812a2a TS	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
6cb784b6 TS	56	namespace std _GLIBCXX_VISIBILITY(default)
	57	{
	58	namespace __detail
	59	{
	60	_GLIBCXX_BEGIN_NAMESPACE_VERSION
	61
ddf41e9d TS	62	template<typename _TraitsT>
	63	_Compiler<_TraitsT>::
	64	_Compiler(_IterT __b, _IterT __e,
2bde8cac	65	const typename _TraitsT::locale_type& __loc, _FlagT __flags)
c2669da9 TS	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),
2bde8cac TS	75	_M_scanner(__b, __e, _M_flags, __loc),
	76	_M_nfa(make_shared<_RegexT>(__loc, _M_flags)),
	77	_M_traits(_M_nfa->_M_traits),
	78	_M_ctype(std::use_facet<_CtypeT>(__loc))
6cb784b6	79	{
2bde8cac TS	80	_StateSeqT __r(*_M_nfa, _M_nfa->_M_start());
2bde8cac TS	81	__r._M_append(_M_nfa->_M_insert_subexpr_begin());
7c812a2a TS	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());
2bde8cac TS	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();
6cb784b6 TS	90	}
6cb784b6 TS	91
ddf41e9d	92	template<typename _TraitsT>
6cb784b6	93	void
ddf41e9d	94	_Compiler<_TraitsT>::
6cb784b6 TS	95	_M_disjunction()
	96	{
	97	this->_M_alternative();
7c812a2a	98	while (_M_match_token(_ScannerT::_S_token_or))
6cb784b6	99	{
7c812a2a TS	100	_StateSeqT __alt1 = _M_pop();
	101	this->_M_alternative();
	102	_StateSeqT __alt2 = _M_pop();
2bde8cac	103	auto __end = _M_nfa->_M_insert_dummy();
7c812a2a TS	104	__alt1._M_append(__end);
7c812a2a TS	105	__alt2._M_append(__end);
ad9ec7b3 TS	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.
2bde8cac TS	109	_M_stack.push(_StateSeqT(*_M_nfa,
	110	_M_nfa->_M_insert_alt(
	111	__alt2._M_start, __alt1._M_start, false),
7c812a2a	112	__end));
6cb784b6 TS	113	}
	114	}
	115
ddf41e9d	116	template<typename _TraitsT>
6cb784b6	117	void
ddf41e9d	118	_Compiler<_TraitsT>::
6cb784b6 TS	119	_M_alternative()
	120	{
	121	if (this->_M_term())
	122	{
7c812a2a	123	_StateSeqT __re = _M_pop();
6cb784b6	124	this->_M_alternative();
7c812a2a	125	__re._M_append(_M_pop());
6cb784b6 TS	126	_M_stack.push(__re);
6cb784b6 TS	127	}
7c812a2a	128	else
2bde8cac	129	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_dummy()));
6cb784b6 TS	130	}
6cb784b6 TS	131
ddf41e9d	132	template<typename _TraitsT>
6cb784b6	133	bool
ddf41e9d	134	_Compiler<_TraitsT>::
6cb784b6 TS	135	_M_term()
	136	{
	137	if (this->_M_assertion())
	138	return true;
	139	if (this->_M_atom())
	140	{
053eb1f3	141	while (this->_M_quantifier());
6cb784b6 TS	142	return true;
	143	}
	144	return false;
	145	}
	146
ddf41e9d	147	template<typename _TraitsT>
6cb784b6	148	bool
ddf41e9d	149	_Compiler<_TraitsT>::
6cb784b6 TS	150	_M_assertion()
6cb784b6 TS	151	{
7c812a2a	152	if (_M_match_token(_ScannerT::_S_token_line_begin))
2bde8cac	153	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_begin()));
7c812a2a	154	else if (_M_match_token(_ScannerT::_S_token_line_end))
2bde8cac	155	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_end()));
7c812a2a	156	else if (_M_match_token(_ScannerT::_S_token_word_bound))
097f0bcf	157	// _M_value[0] == 'n' means it's negative, say "not word boundary".
2bde8cac	158	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->
7b86458e	159	_M_insert_word_bound(_M_value[0] == 'n')));
7c812a2a	160	else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin))
7b86458e TS	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();
2bde8cac	167	__tmp._M_append(_M_nfa->_M_insert_accept());
7b86458e TS	168	_M_stack.push(
7b86458e TS	169	_StateSeqT(
2bde8cac TS	170	*_M_nfa,
2bde8cac TS	171	_M_nfa->_M_insert_lookahead(__tmp._M_start, __neg)));
7b86458e	172	}
7c812a2a TS	173	else
	174	return false;
	175	return true;
6cb784b6 TS	176	}
6cb784b6 TS	177
ddf41e9d	178	template<typename _TraitsT>
053eb1f3	179	bool
ddf41e9d	180	_Compiler<_TraitsT>::
6cb784b6 TS	181	_M_quantifier()
6cb784b6 TS	182	{
c2669da9	183	bool __neg = (_M_flags & regex_constants::ECMAScript);
7b86458e	184	auto __init = [this, &__neg]()
6cb784b6 TS	185	{
	186	if (_M_stack.empty())
	187	__throw_regex_error(regex_constants::error_badrepeat);
7b86458e TS	188	__neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
	189	};
	190	if (_M_match_token(_ScannerT::_S_token_closure0))
	191	{
	192	__init();
7c812a2a	193	auto __e = _M_pop();
2bde8cac TS	194	_StateSeqT __r(*_M_nfa,
	195	_M_nfa->_M_insert_repeat(_S_invalid_state_id,
	196	__e._M_start, __neg));
7c812a2a	197	__e._M_append(__r);
6cb784b6	198	_M_stack.push(__r);
6cb784b6	199	}
7c812a2a	200	else if (_M_match_token(_ScannerT::_S_token_closure1))
6cb784b6	201	{
7b86458e	202	__init();
7c812a2a	203	auto __e = _M_pop();
2bde8cac TS	204	__e._M_append(_M_nfa->_M_insert_repeat(_S_invalid_state_id,
2bde8cac TS	205	__e._M_start, __neg));
7c812a2a	206	_M_stack.push(__e);
6cb784b6	207	}
7c812a2a	208	else if (_M_match_token(_ScannerT::_S_token_opt))
6cb784b6	209	{
7b86458e	210	__init();
7c812a2a	211	auto __e = _M_pop();
2bde8cac TS	212	auto __end = _M_nfa->_M_insert_dummy();
	213	_StateSeqT __r(*_M_nfa,
	214	_M_nfa->_M_insert_repeat(_S_invalid_state_id,
	215	__e._M_start, __neg));
7c812a2a TS	216	__e._M_append(__end);
7c812a2a TS	217	__r._M_append(__end);
6cb784b6	218	_M_stack.push(__r);
6cb784b6	219	}
7c812a2a	220	else if (_M_match_token(_ScannerT::_S_token_interval_begin))
6cb784b6	221	{
c2669da9 TS	222	if (_M_stack.empty())
c2669da9 TS	223	__throw_regex_error(regex_constants::error_badrepeat);
6cb784b6 TS	224	if (!_M_match_token(_ScannerT::_S_token_dup_count))
6cb784b6 TS	225	__throw_regex_error(regex_constants::error_badbrace);
7c812a2a	226	_StateSeqT __r(_M_pop());
2bde8cac	227	_StateSeqT __e(*_M_nfa, _M_nfa->_M_insert_dummy());
6cb43087	228	long __min_rep = _M_cur_int_value(10);
c2669da9	229	bool __infi = false;
6cb43087	230	long __n;
c2669da9	231
7c812a2a	232	// {3
6cb784b6	233	if (_M_match_token(_ScannerT::_S_token_comma))
7c812a2a	234	if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7}
c2669da9 TS	235	__n = _M_cur_int_value(10) - __min_rep;
	236	else
	237	__infi = true;
	238	else
	239	__n = 0;
6cb784b6 TS	240	if (!_M_match_token(_ScannerT::_S_token_interval_end))
6cb784b6 TS	241	__throw_regex_error(regex_constants::error_brace);
c2669da9 TS	242
	243	__neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
	244
6cb43087	245	for (long __i = 0; __i < __min_rep; ++__i)
c2669da9 TS	246	__e._M_append(__r._M_clone());
	247
	248	if (__infi)
	249	{
	250	auto __tmp = __r._M_clone();
2bde8cac TS	251	_StateSeqT __s(*_M_nfa,
	252	_M_nfa->_M_insert_repeat(_S_invalid_state_id,
	253	__tmp._M_start, __neg));
c2669da9 TS	254	__tmp._M_append(__s);
	255	__e._M_append(__s);
	256	}
	257	else
	258	{
	259	if (__n < 0)
	260	__throw_regex_error(regex_constants::error_badbrace);
2bde8cac	261	auto __end = _M_nfa->_M_insert_dummy();
c2669da9 TS	262	// _M_alt is the "match more" branch, and _M_next is the
c2669da9 TS	263	// "match less" one. Switch _M_alt and _M_next of all created
097f0bcf	264	// nodes. This is a hack but IMO works well.
c2669da9	265	std::stack<_StateIdT> __stack;
6cb43087	266	for (long __i = 0; __i < __n; ++__i)
c2669da9 TS	267	{
c2669da9 TS	268	auto __tmp = __r._M_clone();
2bde8cac TS	269	auto __alt = _M_nfa->_M_insert_repeat(__tmp._M_start,
2bde8cac TS	270	__end, __neg);
c2669da9	271	__stack.push(__alt);
2bde8cac	272	__e._M_append(_StateSeqT(*_M_nfa, __alt, __tmp._M_end));
c2669da9 TS	273	}
	274	__e._M_append(__end);
	275	while (!__stack.empty())
	276	{
2bde8cac	277	auto& __tmp = (*_M_nfa)[__stack.top()];
c2669da9 TS	278	__stack.pop();
	279	swap(__tmp._M_next, __tmp._M_alt);
	280	}
	281	}
7c812a2a	282	_M_stack.push(__e);
6cb784b6	283	}
053eb1f3 TS	284	else
	285	return false;
	286	return true;
6cb784b6 TS	287	}
6cb784b6 TS	288
ddf41e9d TS	289	#define __INSERT_REGEX_MATCHER(__func, args...)\
	290	do\
	291	if (!(_M_flags & regex_constants::icase))\
	292	if (!(_M_flags & regex_constants::collate))\
	293	__func<false, false>(args);\
	294	else\
	295	__func<false, true>(args);\
	296	else\
	297	if (!(_M_flags & regex_constants::collate))\
	298	__func<true, false>(args);\
	299	else\
	300	__func<true, true>(args);\
	301	while (false)
	302
	303	template<typename _TraitsT>
6cb784b6	304	bool
ddf41e9d	305	_Compiler<_TraitsT>::
6cb784b6 TS	306	_M_atom()
	307	{
	308	if (_M_match_token(_ScannerT::_S_token_anychar))
f43cc2a6	309	{
ddf41e9d TS	310	if (!(_M_flags & regex_constants::ECMAScript))
ddf41e9d TS	311	__INSERT_REGEX_MATCHER(_M_insert_any_matcher_posix);
f43cc2a6	312	else
ddf41e9d	313	__INSERT_REGEX_MATCHER(_M_insert_any_matcher_ecma);
f43cc2a6	314	}
7c812a2a	315	else if (_M_try_char())
ddf41e9d	316	__INSERT_REGEX_MATCHER(_M_insert_char_matcher);
7c812a2a	317	else if (_M_match_token(_ScannerT::_S_token_backref))
2bde8cac	318	_M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->
7c812a2a TS	319	_M_insert_backref(_M_cur_int_value(10))));
7c812a2a TS	320	else if (_M_match_token(_ScannerT::_S_token_quoted_class))
ddf41e9d	321	__INSERT_REGEX_MATCHER(_M_insert_character_class_matcher);
7c812a2a	322	else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin))
6cb784b6	323	{
2bde8cac	324	_StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_dummy());
7c812a2a TS	325	this->_M_disjunction();
	326	if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
	327	__throw_regex_error(regex_constants::error_paren);
	328	__r._M_append(_M_pop());
	329	_M_stack.push(__r);
6cb784b6	330	}
7c812a2a	331	else if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
6cb784b6	332	{
2bde8cac	333	_StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_subexpr_begin());
6cb784b6 TS	334	this->_M_disjunction();
	335	if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
	336	__throw_regex_error(regex_constants::error_paren);
7c812a2a	337	__r._M_append(_M_pop());
2bde8cac	338	__r._M_append(_M_nfa->_M_insert_subexpr_end());
6cb784b6	339	_M_stack.push(__r);
6cb784b6	340	}
7c812a2a TS	341	else if (!_M_bracket_expression())
	342	return false;
	343	return true;
6cb784b6 TS	344	}
6cb784b6 TS	345
ddf41e9d	346	template<typename _TraitsT>
6cb784b6	347	bool
ddf41e9d	348	_Compiler<_TraitsT>::
6cb784b6 TS	349	_M_bracket_expression()
6cb784b6 TS	350	{
33fbbb76 TS	351	bool __neg =
	352	_M_match_token(_ScannerT::_S_token_bracket_neg_begin);
	353	if (!(__neg \|\| _M_match_token(_ScannerT::_S_token_bracket_begin)))
e280b6ff	354	return false;
ddf41e9d TS	355	__INSERT_REGEX_MATCHER(_M_insert_bracket_matcher, __neg);
	356	return true;
	357	}
	358	#undef __INSERT_REGEX_MATCHER
	359
	360	template<typename _TraitsT>
	361	template<bool __icase, bool __collate>
	362	void
	363	_Compiler<_TraitsT>::
	364	_M_insert_any_matcher_ecma()
	365	{
2bde8cac TS	366	_M_stack.push(_StateSeqT(*_M_nfa,
2bde8cac TS	367	_M_nfa->_M_insert_matcher
ddf41e9d TS	368	(_AnyMatcher<_TraitsT, true, __icase, __collate>
	369	(_M_traits))));
	370	}
	371
	372	template<typename _TraitsT>
	373	template<bool __icase, bool __collate>
	374	void
	375	_Compiler<_TraitsT>::
	376	_M_insert_any_matcher_posix()
	377	{
2bde8cac TS	378	_M_stack.push(_StateSeqT(*_M_nfa,
2bde8cac TS	379	_M_nfa->_M_insert_matcher
ddf41e9d TS	380	(_AnyMatcher<_TraitsT, false, __icase, __collate>
	381	(_M_traits))));
	382	}
	383
	384	template<typename _TraitsT>
	385	template<bool __icase, bool __collate>
	386	void
	387	_Compiler<_TraitsT>::
	388	_M_insert_char_matcher()
	389	{
2bde8cac TS	390	_M_stack.push(_StateSeqT(*_M_nfa,
2bde8cac TS	391	_M_nfa->_M_insert_matcher
ddf41e9d TS	392	(_CharMatcher<_TraitsT, __icase, __collate>
	393	(_M_value[0], _M_traits))));
	394	}
	395
	396	template<typename _TraitsT>
	397	template<bool __icase, bool __collate>
	398	void
	399	_Compiler<_TraitsT>::
	400	_M_insert_character_class_matcher()
	401	{
	402	_GLIBCXX_DEBUG_ASSERT(_M_value.size() == 1);
	403	_BracketMatcher<_TraitsT, __icase, __collate> __matcher
	404	(_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits);
4dae67e0	405	__matcher._M_add_character_class(_M_value, false);
ddf41e9d	406	__matcher._M_ready();
2bde8cac TS	407	_M_stack.push(_StateSeqT(*_M_nfa,
2bde8cac TS	408	_M_nfa->_M_insert_matcher(std::move(__matcher))));
ddf41e9d TS	409	}
	410
	411	template<typename _TraitsT>
	412	template<bool __icase, bool __collate>
	413	void
	414	_Compiler<_TraitsT>::
	415	_M_insert_bracket_matcher(bool __neg)
	416	{
	417	_BracketMatcher<_TraitsT, __icase, __collate> __matcher(__neg, _M_traits);
7c812a2a TS	418	while (!_M_match_token(_ScannerT::_S_token_bracket_end))
7c812a2a TS	419	_M_expression_term(__matcher);
f43cc2a6	420	__matcher._M_ready();
2bde8cac TS	421	_M_stack.push(_StateSeqT(
	422	*_M_nfa,
	423	_M_nfa->_M_insert_matcher(std::move(__matcher))));
6cb784b6 TS	424	}
6cb784b6 TS	425
ddf41e9d TS	426	template<typename _TraitsT>
ddf41e9d TS	427	template<bool __icase, bool __collate>
6cb784b6	428	void
ddf41e9d TS	429	_Compiler<_TraitsT>::
ddf41e9d TS	430	_M_expression_term(_BracketMatcher<_TraitsT, __icase, __collate>& __matcher)
6cb784b6 TS	431	{
6cb784b6 TS	432	if (_M_match_token(_ScannerT::_S_token_collsymbol))
7c812a2a TS	433	__matcher._M_add_collating_element(_M_value);
	434	else if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
	435	__matcher._M_add_equivalence_class(_M_value);
	436	else if (_M_match_token(_ScannerT::_S_token_char_class_name))
4dae67e0	437	__matcher._M_add_character_class(_M_value, false);
7c812a2a	438	else if (_M_try_char()) // [a
e280b6ff	439	{
33fbbb76 TS	440	auto __ch = _M_value[0];
33fbbb76 TS	441	if (_M_try_char())
e280b6ff	442	{
7c812a2a	443	if (_M_value[0] == '-') // [a-
e280b6ff	444	{
33fbbb76 TS	445	if (_M_try_char()) // [a-z]
	446	{
	447	__matcher._M_make_range(__ch, _M_value[0]);
	448	return;
	449	}
	450	// If the dash is the last character in the bracket
	451	// expression, it is not special.
	452	if (_M_scanner._M_get_token()
	453	!= _ScannerT::_S_token_bracket_end)
e280b6ff	454	__throw_regex_error(regex_constants::error_range);
e280b6ff	455	}
33fbbb76	456	__matcher._M_add_char(_M_value[0]);
e280b6ff	457	}
33fbbb76	458	__matcher._M_add_char(__ch);
e280b6ff	459	}
4dae67e0 TS	460	else if (_M_match_token(_ScannerT::_S_token_quoted_class))
	461	__matcher._M_add_character_class(_M_value,
	462	_M_ctype.is(_CtypeT::upper,
	463	_M_value[0]));
7c812a2a TS	464	else
7c812a2a TS	465	__throw_regex_error(regex_constants::error_brack);
6cb784b6 TS	466	}
6cb784b6 TS	467
ddf41e9d	468	template<typename _TraitsT>
33fbbb76	469	bool
ddf41e9d	470	_Compiler<_TraitsT>::
33fbbb76 TS	471	_M_try_char()
	472	{
	473	bool __is_char = false;
	474	if (_M_match_token(_ScannerT::_S_token_oct_num))
	475	{
	476	__is_char = true;
	477	_M_value.assign(1, _M_cur_int_value(8));
	478	}
	479	else if (_M_match_token(_ScannerT::_S_token_hex_num))
	480	{
	481	__is_char = true;
	482	_M_value.assign(1, _M_cur_int_value(16));
	483	}
	484	else if (_M_match_token(_ScannerT::_S_token_ord_char))
	485	__is_char = true;
	486	return __is_char;
	487	}
	488
ddf41e9d	489	template<typename _TraitsT>
7c812a2a	490	bool
ddf41e9d	491	_Compiler<_TraitsT>::
7c812a2a TS	492	_M_match_token(_TokenT token)
	493	{
	494	if (token == _M_scanner._M_get_token())
	495	{
	496	_M_value = _M_scanner._M_get_value();
	497	_M_scanner._M_advance();
	498	return true;
	499	}
	500	return false;
	501	}
	502
ddf41e9d	503	template<typename _TraitsT>
6cb784b6	504	int
ddf41e9d	505	_Compiler<_TraitsT>::
6cb784b6 TS	506	_M_cur_int_value(int __radix)
6cb784b6 TS	507	{
6cb43087	508	long __v = 0;
6cb784b6	509	for (typename _StringT::size_type __i = 0;
33fbbb76 TS	510	__i < _M_value.length(); ++__i)
33fbbb76 TS	511	__v =__v * __radix + _M_traits.value(_M_value[__i], __radix);
6cb784b6 TS	512	return __v;
	513	}
	514
ddf41e9d	515	template<typename _TraitsT, bool __icase, bool __collate>
7d9d2185	516	bool
ddf41e9d TS	517	_BracketMatcher<_TraitsT, __icase, __collate>::
ddf41e9d TS	518	_M_apply(_CharT __ch, false_type) const
6cb784b6	519	{
097f0bcf JW	520	bool __ret = std::binary_search(_M_char_set.begin(), _M_char_set.end(),
	521	_M_translator._M_translate(__ch));
	522	if (!__ret)
e280b6ff	523	{
ddf41e9d	524	auto __s = _M_translator._M_transform(__ch);
e3509691 TS	525	for (auto& __it : _M_range_set)
e3509691 TS	526	if (__it.first <= __s && __s <= __it.second)
e280b6ff TS	527	{
	528	__ret = true;
	529	break;
	530	}
ddf41e9d TS	531	if (_M_traits.isctype(__ch, _M_class_set))
	532	__ret = true;
	533	else if (std::find(_M_equiv_set.begin(), _M_equiv_set.end(),
	534	_M_traits.transform_primary(&__ch, &__ch+1))
	535	!= _M_equiv_set.end())
	536	__ret = true;
4dae67e0 TS	537	else
	538	{
	539	for (auto& __it : _M_neg_class_set)
	540	if (!_M_traits.isctype(__ch, __it))
	541	{
	542	__ret = true;
	543	break;
	544	}
	545	}
e280b6ff	546	}
6cb784b6	547	if (_M_is_non_matching)
33fbbb76 TS	548	return !__ret;
	549	else
	550	return __ret;
6cb784b6 TS	551	}
	552
	553	_GLIBCXX_END_NAMESPACE_VERSION
	554	} // namespace __detail
	555	} // namespace