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

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

// Copyright (C) 2010-2023 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 _NFA<_TraitsT>              	  _RegexT;
      typedef regex_constants::syntax_option_type _FlagT;

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

      shared_ptr<const _RegexT>
      _M_get_nfa() noexcept
      { 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);

      // Cache of the last atom seen in a bracketed range expression.
      struct _BracketState
      {
	enum class _Type : char { _None, _Char, _Class } _M_type = _Type::_None;
	_CharT _M_char = _CharT();

	void
	set(_CharT __c) noexcept { _M_type = _Type::_Char; _M_char = __c; }

	_GLIBCXX_NODISCARD _CharT
	get() const noexcept { return _M_char; }

	void
	reset(_Type __t = _Type::_None) noexcept { _M_type = __t; }

	explicit operator bool() const noexcept
	{ return _M_type != _Type::_None; }

	// Previous token was a single character.
	_GLIBCXX_NODISCARD bool
	_M_is_char() const noexcept { return _M_type == _Type::_Char; }

	// Previous token was a character class, equivalent class,
	// collating symbol etc.
	_GLIBCXX_NODISCARD bool
	_M_is_class() const noexcept { return _M_type == _Type::_Class; }
      };

      template<bool __icase, bool __collate>
	using _BracketMatcher
	  = std::__detail::_BracketMatcher<_TraitsT, __icase, __collate>;

      // Returns true if successfully parsed one term and should continue
      // compiling a bracket expression.
      // Returns false if the compiler should move on.
      template<bool __icase, bool __collate>
	bool
	_M_expression_term(_BracketState& __last_char,
			   _BracketMatcher<__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;
      }

      static _FlagT
      _S_validate(_FlagT __f)
      {
	using namespace regex_constants;
	switch (__f & (ECMAScript|basic|extended|awk|grep|egrep))
	  {
	  case ECMAScript:
	  case basic:
	  case extended:
	  case awk:
	  case grep:
	  case egrep:
	    return __f;
	  case _FlagT(0):
	    return __f | ECMAScript;
	  default:
	    std::__throw_regex_error(_S_grammar, "conflicting grammar options");
	  }
      }

      _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;
    };

  // [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 _GLIBCXX17_CONSTEXPR (__icase)
	  return _M_traits.translate_nocase(__ch);
	else if _GLIBCXX17_CONSTEXPR (__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 _GLIBCXX17_CONSTEXPR (!__icase)
	  return __first <= __ch && __ch <= __last;
	else
	  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
      using _UseCache = typename std::is_same<_CharT, char>::type;

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

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

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