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

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

// Copyright (C) 2010-2021 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.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{regex}
 */

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_BEGIN_NAMESPACE_CXX11

  template<typename>
    class regex_traits;

_GLIBCXX_END_NAMESPACE_CXX11

namespace __detail
{
  /**
   * @addtogroup regex-detail
   * @{
   */

  template<typename, bool, bool>
    struct _BracketMatcher;

  /**
   * @brief Builds an NFA from an input iterator range.
   *
   * The %_TraitsT type should fulfill requirements [28.3].
   */
  template<typename _TraitsT>
    class _Compiler
    {
    public:
      typedef typename _TraitsT::char_type        _CharT;
      typedef const _CharT*                       _IterT;
      typedef _NFA<_TraitsT>              	  _RegexT;
      typedef regex_constants::syntax_option_type _FlagT;

      _Compiler(_IterT __b, _IterT __e,
		const typename _TraitsT::locale_type& __traits, _FlagT __flags);

      shared_ptr<const _RegexT>
      _M_get_nfa()
      { return std::move(_M_nfa); }

    private:
      typedef _Scanner<_CharT>               _ScannerT;
      typedef typename _TraitsT::string_type _StringT;
      typedef typename _ScannerT::_TokenT    _TokenT;
      typedef _StateSeq<_TraitsT>            _StateSeqT;
      typedef std::stack<_StateSeqT>         _StackT;
      typedef std::ctype<_CharT>             _CtypeT;

      // accepts a specific token or returns false.
      bool
      _M_match_token(_TokenT __token);

      void
      _M_disjunction();

      void
      _M_alternative();

      bool
      _M_term();

      bool
      _M_assertion();

      bool
      _M_quantifier();

      bool
      _M_atom();

      bool
      _M_bracket_expression();

      template<bool __icase, bool __collate>
	void
	_M_insert_any_matcher_ecma();

      template<bool __icase, bool __collate>
	void
	_M_insert_any_matcher_posix();

      template<bool __icase, bool __collate>
	void
	_M_insert_char_matcher();

      template<bool __icase, bool __collate>
	void
	_M_insert_character_class_matcher();

      template<bool __icase, bool __collate>
	void
	_M_insert_bracket_matcher(bool __neg);

      // Returns true if successfully matched one term and should continue.
      // Returns false if the compiler should move on.
      template<bool __icase, bool __collate>
	bool
	_M_expression_term(pair<bool, _CharT>& __last_char,
			   _BracketMatcher<_TraitsT, __icase, __collate>&
			   __matcher);

      int
      _M_cur_int_value(int __radix);

      bool
      _M_try_char();

      _StateSeqT
      _M_pop()
      {
	auto ret = _M_stack.top();
	_M_stack.pop();
	return ret;
      }

      _FlagT              _M_flags;
      _ScannerT           _M_scanner;
      shared_ptr<_RegexT> _M_nfa;
      _StringT            _M_value;
      _StackT             _M_stack;
      const _TraitsT&     _M_traits;
      const _CtypeT&      _M_ctype;
    };

  template<typename _Tp>
    struct __is_contiguous_iter : is_pointer<_Tp>::type { };

  template<typename _Tp, typename _Cont>
    struct
    __is_contiguous_iter<__gnu_cxx::__normal_iterator<_Tp*, _Cont>>
    : true_type { };

  template<typename _Iter, typename _TraitsT>
    using __enable_if_contiguous_iter
      = __enable_if_t< __is_contiguous_iter<_Iter>::value,
                       std::shared_ptr<const _NFA<_TraitsT>> >;

  template<typename _Iter, typename _TraitsT>
    using __disable_if_contiguous_iter
      = __enable_if_t< !__is_contiguous_iter<_Iter>::value,
                       std::shared_ptr<const _NFA<_TraitsT>> >;

  template<typename _TraitsT, typename _FwdIter>
    inline __enable_if_contiguous_iter<_FwdIter, _TraitsT>
    __compile_nfa(_FwdIter __first, _FwdIter __last,
		  const typename _TraitsT::locale_type& __loc,
		  regex_constants::syntax_option_type __flags)
    {
      size_t __len = __last - __first;
      const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
      using _Cmplr = _Compiler<_TraitsT>;
      return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa();
    }

  template<typename _TraitsT, typename _FwdIter>
    inline __disable_if_contiguous_iter<_FwdIter, _TraitsT>
    __compile_nfa(_FwdIter __first, _FwdIter __last,
		  const typename _TraitsT::locale_type& __loc,
		  regex_constants::syntax_option_type __flags)
    {
      const basic_string<typename _TraitsT::char_type> __str(__first, __last);
      return __compile_nfa<_TraitsT>(__str.data(), __str.data() + __str.size(),
				     __loc, __flags);
    }

  // [28.13.14]
  template<typename _TraitsT, bool __icase, bool __collate>
    class _RegexTranslatorBase
    {
    public:
      typedef typename _TraitsT::char_type	      _CharT;
      typedef typename _TraitsT::string_type	      _StringT;
      typedef _StringT _StrTransT;

      explicit
      _RegexTranslatorBase(const _TraitsT& __traits)
      : _M_traits(__traits)
      { }

      _CharT
      _M_translate(_CharT __ch) const
      {
	if (__icase)
	  return _M_traits.translate_nocase(__ch);
	else if (__collate)
	  return _M_traits.translate(__ch);
	else
	  return __ch;
      }

      _StrTransT
      _M_transform(_CharT __ch) const
      {
	_StrTransT __str(1, __ch);
	return _M_traits.transform(__str.begin(), __str.end());
      }

      // See LWG 523. It's not efficiently implementable when _TraitsT is not
      // std::regex_traits<>, and __collate is true. See specializations for
      // implementations of other cases.
      bool
      _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
		     const _StrTransT& __s) const
      { return __first <= __s && __s <= __last; }

    protected:
      bool _M_in_range_icase(_CharT __first, _CharT __last, _CharT __ch) const
      {
	typedef std::ctype<_CharT> __ctype_type;
	const auto& __fctyp = use_facet<__ctype_type>(this->_M_traits.getloc());
	auto __lower = __fctyp.tolower(__ch);
	auto __upper = __fctyp.toupper(__ch);
	return (__first <= __lower && __lower <= __last)
	  || (__first <= __upper && __upper <= __last);
      }

      const _TraitsT& _M_traits;
    };

  template<typename _TraitsT, bool __icase, bool __collate>
    class _RegexTranslator
    : public _RegexTranslatorBase<_TraitsT, __icase, __collate>
    {
    public:
      typedef _RegexTranslatorBase<_TraitsT, __icase, __collate> _Base;
      using _Base::_Base;
    };

  template<typename _TraitsT, bool __icase>
    class _RegexTranslator<_TraitsT, __icase, false>
    : public _RegexTranslatorBase<_TraitsT, __icase, false>
    {
    public:
      typedef _RegexTranslatorBase<_TraitsT, __icase, false> _Base;
      typedef typename _Base::_CharT _CharT;
      typedef _CharT _StrTransT;

      using _Base::_Base;

      _StrTransT
      _M_transform(_CharT __ch) const
      { return __ch; }

      bool
      _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
      {
	if (!__icase)
	  return __first <= __ch && __ch <= __last;
	return this->_M_in_range_icase(__first, __last, __ch);
      }
    };

  template<typename _CharType>
    class _RegexTranslator<std::regex_traits<_CharType>, true, true>
    : public _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
    {
    public:
      typedef _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
	_Base;
      typedef typename _Base::_CharT _CharT;
      typedef typename _Base::_StrTransT _StrTransT;

      using _Base::_Base;

      bool
      _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
		     const _StrTransT& __str) const
      {
	__glibcxx_assert(__first.size() == 1);
	__glibcxx_assert(__last.size() == 1);
	__glibcxx_assert(__str.size() == 1);
	return this->_M_in_range_icase(__first[0], __last[0], __str[0]);
      }
    };

  template<typename _TraitsT>
    class _RegexTranslator<_TraitsT, false, false>
    {
    public:
      typedef typename _TraitsT::char_type _CharT;
      typedef _CharT                       _StrTransT;

      explicit
      _RegexTranslator(const _TraitsT&)
      { }

      _CharT
      _M_translate(_CharT __ch) const
      { return __ch; }

      _StrTransT
      _M_transform(_CharT __ch) const
      { return __ch; }

      bool
      _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
      { return __first <= __ch && __ch <= __last; }
    };

  template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
    struct _AnyMatcher;

  template<typename _TraitsT, bool __icase, bool __collate>
    struct _AnyMatcher<_TraitsT, false, __icase, __collate>
    {
      typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
      typedef typename _TransT::_CharT                       _CharT;

      explicit
      _AnyMatcher(const _TraitsT& __traits)
      : _M_translator(__traits)
      { }

      bool
      operator()(_CharT __ch) const
      {
	static auto __nul = _M_translator._M_translate('\0');
	return _M_translator._M_translate(__ch) != __nul;
      }

      _TransT _M_translator;
    };

  template<typename _TraitsT, bool __icase, bool __collate>
    struct _AnyMatcher<_TraitsT, true, __icase, __collate>
    {
      typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
      typedef typename _TransT::_CharT                       _CharT;

      explicit
      _AnyMatcher(const _TraitsT& __traits)
      : _M_translator(__traits)
      { }

      bool
      operator()(_CharT __ch) const
      { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }

      bool
      _M_apply(_CharT __ch, true_type) const
      {
	auto __c = _M_translator._M_translate(__ch);
	auto __n = _M_translator._M_translate('\n');
	auto __r = _M_translator._M_translate('\r');
	return __c != __n && __c != __r;
      }

      bool
      _M_apply(_CharT __ch, false_type) const
      {
	auto __c = _M_translator._M_translate(__ch);
	auto __n = _M_translator._M_translate('\n');
	auto __r = _M_translator._M_translate('\r');
	auto __u2028 = _M_translator._M_translate(u'\u2028');
	auto __u2029 = _M_translator._M_translate(u'\u2029');
	return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
      }

      _TransT _M_translator;
    };

  template<typename _TraitsT, bool __icase, bool __collate>
    struct _CharMatcher
    {
      typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
      typedef typename _TransT::_CharT                       _CharT;

      _CharMatcher(_CharT __ch, const _TraitsT& __traits)
      : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
      { }

      bool
      operator()(_CharT __ch) const
      { return _M_ch == _M_translator._M_translate(__ch); }

      _TransT _M_translator;
      _CharT  _M_ch;
    };

  /// Matches a character range (bracket expression)
  template<typename _TraitsT, bool __icase, bool __collate>
    struct _BracketMatcher
    {
    public:
      typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
      typedef typename _TransT::_CharT                       _CharT;
      typedef typename _TransT::_StrTransT                   _StrTransT;
      typedef typename _TraitsT::string_type                 _StringT;
      typedef typename _TraitsT::char_class_type             _CharClassT;

    public:
      _BracketMatcher(bool __is_non_matching,
		      const _TraitsT& __traits)
      : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
      _M_is_non_matching(__is_non_matching)
      { }

      bool
      operator()(_CharT __ch) const
      {
	_GLIBCXX_DEBUG_ASSERT(_M_is_ready);
	return _M_apply(__ch, _UseCache());
      }

      void
      _M_add_char(_CharT __c)
      {
	_M_char_set.push_back(_M_translator._M_translate(__c));
	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
      }

      _StringT
      _M_add_collate_element(const _StringT& __s)
      {
	auto __st = _M_traits.lookup_collatename(__s.data(),
						 __s.data() + __s.size());
	if (__st.empty())
	  __throw_regex_error(regex_constants::error_collate,
			      "Invalid collate element.");
	_M_char_set.push_back(_M_translator._M_translate(__st[0]));
	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
	return __st;
      }

      void
      _M_add_equivalence_class(const _StringT& __s)
      {
	auto __st = _M_traits.lookup_collatename(__s.data(),
						 __s.data() + __s.size());
	if (__st.empty())
	  __throw_regex_error(regex_constants::error_collate,
			      "Invalid equivalence class.");
	__st = _M_traits.transform_primary(__st.data(),
					   __st.data() + __st.size());
	_M_equiv_set.push_back(__st);
	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
      }

      // __neg should be true for \D, \S and \W only.
      void
      _M_add_character_class(const _StringT& __s, bool __neg)
      {
	auto __mask = _M_traits.lookup_classname(__s.data(),
						 __s.data() + __s.size(),
						 __icase);
	if (__mask == 0)
	  __throw_regex_error(regex_constants::error_collate,
			      "Invalid character class.");
	if (!__neg)
	  _M_class_set |= __mask;
	else
	  _M_neg_class_set.push_back(__mask);
	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
      }

      void
      _M_make_range(_CharT __l, _CharT __r)
      {
	if (__l > __r)
	  __throw_regex_error(regex_constants::error_range,
			      "Invalid range in bracket expression.");
	_M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
					 _M_translator._M_transform(__r)));
	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
      }

      void
      _M_ready()
      {
	std::sort(_M_char_set.begin(), _M_char_set.end());
	auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
	_M_char_set.erase(__end, _M_char_set.end());
	_M_make_cache(_UseCache());
	_GLIBCXX_DEBUG_ONLY(_M_is_ready = true);
      }

    private:
      // Currently we only use the cache for char
      typedef typename std::is_same<_CharT, char>::type _UseCache;

      static constexpr size_t
      _S_cache_size =
	1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));

      struct _Dummy { };
      typedef typename std::conditional<_UseCache::value,
					std::bitset<_S_cache_size>,
					_Dummy>::type _CacheT;
      typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;

      bool
      _M_apply(_CharT __ch, false_type) const;

      bool
      _M_apply(_CharT __ch, true_type) const
      { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }

      void
      _M_make_cache(true_type)
      {
	for (unsigned __i = 0; __i < _M_cache.size(); __i++)
	  _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
      }

      void
      _M_make_cache(false_type)
      { }

    private:
      std::vector<_CharT>                       _M_char_set;
      std::vector<_StringT>                     _M_equiv_set;
      std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
      std::vector<_CharClassT>                  _M_neg_class_set;
      _CharClassT                               _M_class_set;
      _TransT                                   _M_translator;
      const _TraitsT&                           _M_traits;
      bool                                      _M_is_non_matching;
      _CacheT					_M_cache;
#ifdef _GLIBCXX_DEBUG
      bool                                      _M_is_ready = false;
#endif
    };

 ///@} regex-detail
} // namespace __detail
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

#include <bits/regex_compiler.tcc>
Commit	Line	Data
849cab7b SW	1	// class template regex -- C++ --
849cab7b SW	2
99dee823	3	// Copyright (C) 2010-2021 Free Software Foundation, Inc.
849cab7b SW	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	/**
f910786b BK	26	* @file bits/regex_compiler.h
	27	* This is an internal header file, included by other library headers.
	28	* Do not attempt to use it directly. @headername{regex}
849cab7b SW	29	*/
849cab7b SW	30
12ffa228 BK	31	namespace std _GLIBCXX_VISIBILITY(default)
12ffa228 BK	32	{
974afa58 TS	33	_GLIBCXX_BEGIN_NAMESPACE_VERSION
	34	_GLIBCXX_BEGIN_NAMESPACE_CXX11
	35
	36	template<typename>
	37	class regex_traits;
	38
	39	_GLIBCXX_END_NAMESPACE_CXX11
974afa58	40
e07b233d	41	namespace __detail
849cab7b	42	{
e07b233d BK	43	/**
	44	* @addtogroup regex-detail
	45	* @{
	46	*/
	47
ddf41e9d	48	template<typename, bool, bool>
33fbbb76	49	struct _BracketMatcher;
849cab7b	50
ee54a3b3	51	/**
097f0bcf	52	* @brief Builds an NFA from an input iterator range.
ee54a3b3 TS	53	*
	54	* The %_TraitsT type should fulfill requirements [28.3].
	55	*/
ddf41e9d	56	template<typename _TraitsT>
849cab7b SW	57	class _Compiler
	58	{
	59	public:
ddf41e9d TS	60	typedef typename _TraitsT::char_type _CharT;
ddf41e9d TS	61	typedef const _CharT* _IterT;
68e69ce2	62	typedef _NFA<_TraitsT> _RegexT;
6cb784b6	63	typedef regex_constants::syntax_option_type _FlagT;
849cab7b	64
ddf41e9d	65	_Compiler(_IterT __b, _IterT __e,
2bde8cac	66	const typename _TraitsT::locale_type& __traits, _FlagT __flags);
849cab7b	67
60c176fb	68	shared_ptr<const _RegexT>
7d9d2185	69	_M_get_nfa()
2bde8cac	70	{ return std::move(_M_nfa); }
849cab7b SW	71
849cab7b SW	72	private:
ddf41e9d TS	73	typedef _Scanner<_CharT> _ScannerT;
	74	typedef typename _TraitsT::string_type _StringT;
	75	typedef typename _ScannerT::_TokenT _TokenT;
	76	typedef _StateSeq<_TraitsT> _StateSeqT;
	77	typedef std::stack<_StateSeqT> _StackT;
	78	typedef std::ctype<_CharT> _CtypeT;
849cab7b SW	79
	80	// accepts a specific token or returns false.
	81	bool
d860c842	82	_M_match_token(_TokenT __token);
849cab7b SW	83
	84	void
	85	_M_disjunction();
	86
399eeef9	87	void
849cab7b SW	88	_M_alternative();
	89
	90	bool
	91	_M_term();
	92
	93	bool
	94	_M_assertion();
	95
053eb1f3	96	bool
849cab7b SW	97	_M_quantifier();
	98
	99	bool
	100	_M_atom();
	101
	102	bool
	103	_M_bracket_expression();
	104
ddf41e9d TS	105	template<bool __icase, bool __collate>
	106	void
	107	_M_insert_any_matcher_ecma();
849cab7b	108
ddf41e9d TS	109	template<bool __icase, bool __collate>
	110	void
	111	_M_insert_any_matcher_posix();
849cab7b	112
ddf41e9d TS	113	template<bool __icase, bool __collate>
	114	void
	115	_M_insert_char_matcher();
849cab7b	116
ddf41e9d TS	117	template<bool __icase, bool __collate>
	118	void
	119	_M_insert_character_class_matcher();
849cab7b	120
ddf41e9d TS	121	template<bool __icase, bool __collate>
	122	void
	123	_M_insert_bracket_matcher(bool __neg);
	124
f9ce3c16 TS	125	// Returns true if successfully matched one term and should continue.
f9ce3c16 TS	126	// Returns false if the compiler should move on.
ddf41e9d	127	template<bool __icase, bool __collate>
f9ce3c16	128	bool
79b576cc TS	129	_M_expression_term(pair<bool, _CharT>& __last_char,
79b576cc TS	130	_BracketMatcher<_TraitsT, __icase, __collate>&
ddf41e9d	131	__matcher);
849cab7b SW	132
	133	int
	134	_M_cur_int_value(int __radix);
	135
33fbbb76 TS	136	bool
	137	_M_try_char();
	138
7c812a2a TS	139	_StateSeqT
	140	_M_pop()
	141	{
	142	auto ret = _M_stack.top();
	143	_M_stack.pop();
	144	return ret;
	145	}
33fbbb76	146
2bde8cac TS	147	_FlagT _M_flags;
	148	_ScannerT _M_scanner;
	149	shared_ptr<_RegexT> _M_nfa;
	150	_StringT _M_value;
	151	_StackT _M_stack;
	152	const _TraitsT& _M_traits;
	153	const _CtypeT& _M_ctype;
849cab7b SW	154	};
849cab7b SW	155
60c176fb	156	template<typename _Tp>
e112d53a	157	struct __is_contiguous_iter : is_pointer<_Tp>::type { };
60c176fb TS	158
	159	template<typename _Tp, typename _Cont>
	160	struct
e112d53a JW	161	__is_contiguous_iter<__gnu_cxx::__normal_iterator<_Tp*, _Cont>>
e112d53a JW	162	: true_type { };
60c176fb TS	163
60c176fb TS	164	template<typename _Iter, typename _TraitsT>
e112d53a JW	165	using __enable_if_contiguous_iter
	166	= __enable_if_t< __is_contiguous_iter<_Iter>::value,
	167	std::shared_ptr<const _NFA<_TraitsT>> >;
60c176fb TS	168
60c176fb TS	169	template<typename _Iter, typename _TraitsT>
e112d53a JW	170	using __disable_if_contiguous_iter
	171	= __enable_if_t< !__is_contiguous_iter<_Iter>::value,
	172	std::shared_ptr<const _NFA<_TraitsT>> >;
60c176fb	173
d840779f	174	template<typename _TraitsT, typename _FwdIter>
e112d53a	175	inline __enable_if_contiguous_iter<_FwdIter, _TraitsT>
60c176fb	176	__compile_nfa(_FwdIter __first, _FwdIter __last,
2bde8cac	177	const typename _TraitsT::locale_type& __loc,
68e69ce2 JW	178	regex_constants::syntax_option_type __flags)
68e69ce2 JW	179	{
60c176fb TS	180	size_t __len = __last - __first;
60c176fb TS	181	const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
ddf41e9d	182	using _Cmplr = _Compiler<_TraitsT>;
60c176fb TS	183	return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa();
	184	}
	185
d840779f	186	template<typename _TraitsT, typename _FwdIter>
e112d53a	187	inline __disable_if_contiguous_iter<_FwdIter, _TraitsT>
60c176fb TS	188	__compile_nfa(_FwdIter __first, _FwdIter __last,
	189	const typename _TraitsT::locale_type& __loc,
	190	regex_constants::syntax_option_type __flags)
	191	{
d840779f JW	192	const basic_string<typename _TraitsT::char_type> __str(__first, __last);
	193	return __compile_nfa<_TraitsT>(__str.data(), __str.data() + __str.size(),
	194	__loc, __flags);
68e69ce2 JW	195	}
68e69ce2 JW	196
ddf41e9d TS	197	// [28.13.14]
ddf41e9d TS	198	template<typename _TraitsT, bool __icase, bool __collate>
974afa58	199	class _RegexTranslatorBase
34d1ff06	200	{
ddf41e9d TS	201	public:
	202	typedef typename _TraitsT::char_type _CharT;
	203	typedef typename _TraitsT::string_type _StringT;
974afa58	204	typedef _StringT _StrTransT;
ddf41e9d TS	205
ddf41e9d TS	206	explicit
974afa58	207	_RegexTranslatorBase(const _TraitsT& __traits)
ddf41e9d TS	208	: _M_traits(__traits)
	209	{ }
	210
	211	_CharT
	212	_M_translate(_CharT __ch) const
	213	{
	214	if (__icase)
	215	return _M_traits.translate_nocase(__ch);
	216	else if (__collate)
	217	return _M_traits.translate(__ch);
	218	else
	219	return __ch;
	220	}
	221
	222	_StrTransT
	223	_M_transform(_CharT __ch) const
	224	{
974afa58 TS	225	_StrTransT __str(1, __ch);
974afa58 TS	226	return _M_traits.transform(__str.begin(), __str.end());
ddf41e9d TS	227	}
ddf41e9d TS	228
974afa58 TS	229	// See LWG 523. It's not efficiently implementable when _TraitsT is not
	230	// std::regex_traits<>, and __collate is true. See specializations for
	231	// implementations of other cases.
	232	bool
	233	_M_match_range(const _StrTransT& __first, const _StrTransT& __last,
	234	const _StrTransT& __s) const
	235	{ return __first <= __s && __s <= __last; }
	236
	237	protected:
	238	bool _M_in_range_icase(_CharT __first, _CharT __last, _CharT __ch) const
	239	{
	240	typedef std::ctype<_CharT> __ctype_type;
	241	const auto& __fctyp = use_facet<__ctype_type>(this->_M_traits.getloc());
	242	auto __lower = __fctyp.tolower(__ch);
	243	auto __upper = __fctyp.toupper(__ch);
	244	return (__first <= __lower && __lower <= __last)
	245	\|\| (__first <= __upper && __upper <= __last);
	246	}
	247
	248	const _TraitsT& _M_traits;
	249	};
	250
	251	template<typename _TraitsT, bool __icase, bool __collate>
	252	class _RegexTranslator
	253	: public _RegexTranslatorBase<_TraitsT, __icase, __collate>
	254	{
	255	public:
	256	typedef _RegexTranslatorBase<_TraitsT, __icase, __collate> _Base;
	257	using _Base::_Base;
	258	};
	259
	260	template<typename _TraitsT, bool __icase>
	261	class _RegexTranslator<_TraitsT, __icase, false>
	262	: public _RegexTranslatorBase<_TraitsT, __icase, false>
	263	{
	264	public:
	265	typedef _RegexTranslatorBase<_TraitsT, __icase, false> _Base;
	266	typedef typename _Base::_CharT _CharT;
	267	typedef _CharT _StrTransT;
	268
	269	using _Base::_Base;
	270
ddf41e9d	271	_StrTransT
974afa58	272	_M_transform(_CharT __ch) const
ddf41e9d TS	273	{ return __ch; }
ddf41e9d TS	274
974afa58 TS	275	bool
974afa58 TS	276	_M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
ddf41e9d	277	{
974afa58 TS	278	if (!__icase)
	279	return __first <= __ch && __ch <= __last;
	280	return this->_M_in_range_icase(__first, __last, __ch);
ddf41e9d	281	}
974afa58	282	};
34d1ff06	283
974afa58 TS	284	template<typename _CharType>
	285	class _RegexTranslator<std::regex_traits<_CharType>, true, true>
	286	: public _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
	287	{
	288	public:
	289	typedef _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
	290	_Base;
	291	typedef typename _Base::_CharT _CharT;
	292	typedef typename _Base::_StrTransT _StrTransT;
	293
	294	using _Base::_Base;
	295
	296	bool
	297	_M_match_range(const _StrTransT& __first, const _StrTransT& __last,
	298	const _StrTransT& __str) const
	299	{
	300	__glibcxx_assert(__first.size() == 1);
	301	__glibcxx_assert(__last.size() == 1);
	302	__glibcxx_assert(__str.size() == 1);
	303	return this->_M_in_range_icase(__first[0], __last[0], __str[0]);
	304	}
ddf41e9d TS	305	};
	306
	307	template<typename _TraitsT>
	308	class _RegexTranslator<_TraitsT, false, false>
e3509691	309	{
ddf41e9d TS	310	public:
	311	typedef typename _TraitsT::char_type _CharT;
	312	typedef _CharT _StrTransT;
	313
	314	explicit
8aed2f2f	315	_RegexTranslator(const _TraitsT&)
ddf41e9d TS	316	{ }
	317
	318	_CharT
	319	_M_translate(_CharT __ch) const
	320	{ return __ch; }
	321
	322	_StrTransT
	323	_M_transform(_CharT __ch) const
	324	{ return __ch; }
974afa58 TS	325
	326	bool
	327	_M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
	328	{ return __first <= __ch && __ch <= __last; }
ddf41e9d TS	329	};
	330
	331	template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
	332	struct _AnyMatcher;
	333
	334	template<typename _TraitsT, bool __icase, bool __collate>
	335	struct _AnyMatcher<_TraitsT, false, __icase, __collate>
	336	{
	337	typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
	338	typedef typename _TransT::_CharT _CharT;
bb038ece	339
e3509691 TS	340	explicit
e3509691 TS	341	_AnyMatcher(const _TraitsT& __traits)
ddf41e9d TS	342	: _M_translator(__traits)
	343	{ }
	344
	345	bool
	346	operator()(_CharT __ch) const
	347	{
	348	static auto __nul = _M_translator._M_translate('\0');
	349	return _M_translator._M_translate(__ch) != __nul;
	350	}
	351
	352	_TransT _M_translator;
	353	};
	354
	355	template<typename _TraitsT, bool __icase, bool __collate>
	356	struct _AnyMatcher<_TraitsT, true, __icase, __collate>
	357	{
	358	typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
	359	typedef typename _TransT::_CharT _CharT;
	360
	361	explicit
	362	_AnyMatcher(const _TraitsT& __traits)
	363	: _M_translator(__traits)
e3509691 TS	364	{ }
	365
	366	bool
	367	operator()(_CharT __ch) const
f43cc2a6 TS	368	{ return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
	369
	370	bool
	371	_M_apply(_CharT __ch, true_type) const
e3509691	372	{
ddf41e9d TS	373	auto __c = _M_translator._M_translate(__ch);
	374	auto __n = _M_translator._M_translate('\n');
	375	auto __r = _M_translator._M_translate('\r');
	376	return __c != __n && __c != __r;
f43cc2a6 TS	377	}
	378
	379	bool
	380	_M_apply(_CharT __ch, false_type) const
	381	{
ddf41e9d TS	382	auto __c = _M_translator._M_translate(__ch);
	383	auto __n = _M_translator._M_translate('\n');
	384	auto __r = _M_translator._M_translate('\r');
	385	auto __u2028 = _M_translator._M_translate(u'\u2028');
	386	auto __u2029 = _M_translator._M_translate(u'\u2029');
	387	return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
e3509691 TS	388	}
e3509691 TS	389
ddf41e9d	390	_TransT _M_translator;
e3509691 TS	391	};
e3509691 TS	392
ddf41e9d	393	template<typename _TraitsT, bool __icase, bool __collate>
e3509691 TS	394	struct _CharMatcher
e3509691 TS	395	{
ddf41e9d TS	396	typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
ddf41e9d TS	397	typedef typename _TransT::_CharT _CharT;
e3509691	398
f43cc2a6	399	_CharMatcher(_CharT __ch, const _TraitsT& __traits)
ddf41e9d	400	: _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
e3509691 TS	401	{ }
	402
	403	bool
	404	operator()(_CharT __ch) const
ddf41e9d	405	{ return _M_ch == _M_translator._M_translate(__ch); }
e3509691	406
ddf41e9d TS	407	_TransT _M_translator;
ddf41e9d TS	408	_CharT _M_ch;
e3509691 TS	409	};
e3509691 TS	410
33fbbb76	411	/// Matches a character range (bracket expression)
ddf41e9d	412	template<typename _TraitsT, bool __icase, bool __collate>
33fbbb76 TS	413	struct _BracketMatcher
33fbbb76 TS	414	{
f43cc2a6	415	public:
ddf41e9d TS	416	typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
	417	typedef typename _TransT::_CharT _CharT;
	418	typedef typename _TransT::_StrTransT _StrTransT;
	419	typedef typename _TraitsT::string_type _StringT;
	420	typedef typename _TraitsT::char_class_type _CharClassT;
33fbbb76	421
f43cc2a6	422	public:
33fbbb76	423	_BracketMatcher(bool __is_non_matching,
ddf41e9d TS	424	const _TraitsT& __traits)
	425	: _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
	426	_M_is_non_matching(__is_non_matching)
33fbbb76 TS	427	{ }
	428
	429	bool
f43cc2a6 TS	430	operator()(_CharT __ch) const
	431	{
	432	_GLIBCXX_DEBUG_ASSERT(_M_is_ready);
097f0bcf	433	return _M_apply(__ch, _UseCache());
f43cc2a6	434	}
33fbbb76 TS	435
	436	void
	437	_M_add_char(_CharT __c)
f43cc2a6	438	{
ddf41e9d	439	_M_char_set.push_back(_M_translator._M_translate(__c));
12dee005	440	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
f43cc2a6	441	}
33fbbb76	442
f9ce3c16 TS	443	_StringT
f9ce3c16 TS	444	_M_add_collate_element(const _StringT& __s)
33fbbb76 TS	445	{
	446	auto __st = _M_traits.lookup_collatename(__s.data(),
	447	__s.data() + __s.size());
	448	if (__st.empty())
236d76c4 TS	449	__throw_regex_error(regex_constants::error_collate,
236d76c4 TS	450	"Invalid collate element.");
ddf41e9d	451	_M_char_set.push_back(_M_translator._M_translate(__st[0]));
12dee005	452	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
f9ce3c16	453	return __st;
33fbbb76 TS	454	}
	455
	456	void
	457	_M_add_equivalence_class(const _StringT& __s)
	458	{
756aa0c3 TS	459	auto __st = _M_traits.lookup_collatename(__s.data(),
	460	__s.data() + __s.size());
	461	if (__st.empty())
236d76c4 TS	462	__throw_regex_error(regex_constants::error_collate,
236d76c4 TS	463	"Invalid equivalence class.");
756aa0c3 TS	464	__st = _M_traits.transform_primary(__st.data(),
756aa0c3 TS	465	__st.data() + __st.size());
ddf41e9d	466	_M_equiv_set.push_back(__st);
12dee005	467	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
33fbbb76 TS	468	}
33fbbb76 TS	469
4dae67e0	470	// __neg should be true for \D, \S and \W only.
33fbbb76	471	void
4dae67e0	472	_M_add_character_class(const _StringT& __s, bool __neg)
33fbbb76	473	{
756aa0c3 TS	474	auto __mask = _M_traits.lookup_classname(__s.data(),
756aa0c3 TS	475	__s.data() + __s.size(),
ddf41e9d	476	__icase);
756aa0c3	477	if (__mask == 0)
236d76c4 TS	478	__throw_regex_error(regex_constants::error_collate,
236d76c4 TS	479	"Invalid character class.");
4dae67e0 TS	480	if (!__neg)
	481	_M_class_set \|= __mask;
	482	else
	483	_M_neg_class_set.push_back(__mask);
12dee005	484	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
33fbbb76 TS	485	}
	486
	487	void
	488	_M_make_range(_CharT __l, _CharT __r)
	489	{
79b576cc	490	if (__l > __r)
236d76c4 TS	491	__throw_regex_error(regex_constants::error_range,
236d76c4 TS	492	"Invalid range in bracket expression.");
ddf41e9d	493	_M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
4dae67e0	494	_M_translator._M_transform(__r)));
12dee005	495	_GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
33fbbb76 TS	496	}
33fbbb76 TS	497
f43cc2a6 TS	498	void
	499	_M_ready()
	500	{
097f0bcf JW	501	std::sort(_M_char_set.begin(), _M_char_set.end());
	502	auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
	503	_M_char_set.erase(__end, _M_char_set.end());
	504	_M_make_cache(_UseCache());
12dee005	505	_GLIBCXX_DEBUG_ONLY(_M_is_ready = true);
f43cc2a6 TS	506	}
	507
	508	private:
097f0bcf JW	509	// Currently we only use the cache for char
	510	typedef typename std::is_same<_CharT, char>::type _UseCache;
	511
	512	static constexpr size_t
a6e1cfdd JM	513	_S_cache_size =
a6e1cfdd JM	514	1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));
097f0bcf	515
f43cc2a6	516	struct _Dummy { };
097f0bcf	517	typedef typename std::conditional<_UseCache::value,
a6e1cfdd	518	std::bitset<_S_cache_size>,
097f0bcf JW	519	_Dummy>::type _CacheT;
097f0bcf JW	520	typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
f43cc2a6	521
f43cc2a6 TS	522	bool
	523	_M_apply(_CharT __ch, false_type) const;
	524
	525	bool
	526	_M_apply(_CharT __ch, true_type) const
	527	{ return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
	528
f43cc2a6 TS	529	void
	530	_M_make_cache(true_type)
	531	{
097f0bcf JW	532	for (unsigned __i = 0; __i < _M_cache.size(); __i++)
097f0bcf JW	533	_M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
f43cc2a6 TS	534	}
	535
	536	void
	537	_M_make_cache(false_type)
	538	{ }
	539
	540	private:
ddf41e9d TS	541	std::vector<_CharT> _M_char_set;
	542	std::vector<_StringT> _M_equiv_set;
	543	std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
4dae67e0	544	std::vector<_CharClassT> _M_neg_class_set;
ddf41e9d TS	545	_CharClassT _M_class_set;
	546	_TransT _M_translator;
	547	const _TraitsT& _M_traits;
	548	bool _M_is_non_matching;
097f0bcf	549	_CacheT _M_cache;
f43cc2a6	550	#ifdef _GLIBCXX_DEBUG
12dee005	551	bool _M_is_ready = false;
f43cc2a6	552	#endif
33fbbb76 TS	553	};
33fbbb76 TS	554
f0b88346	555	///@} regex-detail
e07b233d	556	} // namespace __detail
4a15d842	557	_GLIBCXX_END_NAMESPACE_VERSION
e9599233	558	} // namespace std
6cb784b6 TS	559
6cb784b6 TS	560	#include <bits/regex_compiler.tcc>