This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]
Other format:	[Raw text]

Re: [Patch] Small refactor on <regex> _State<>

From: Jonathan Wakely <jwakely at redhat dot com>
To: Tim Shen <timshen at google dot com>
Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
Date: Sat, 25 Jul 2015 16:31:21 +0100
Subject: Re: [Patch] Small refactor on <regex> _State<>
Authentication-results: sourceware.org; auth=none
References: <CAG4ZjNnYLoCYnjNpkJYHa2Q-ux0KnKmVXBDUOa33xk29MzeTKA at mail dot gmail dot com>

On 25/07/15 00:11 -0700, Tim Shen wrote:

It's not a very necessary refactoring, but simply can't resist. :)

I'm not sure of the ::memcpy calls. It looks not very idiomatic, but
std::copy on char* looks even more weird? :/


The ::memcpy(this, &rhs, sizeof(rhs))...) makes me quite
uncomfortable, because _State is not trivially-copyable, although its
_State_base base class _is_ trivially-copyable, and is at the same
address and has the same size ... so I think it's safe.

But couldn't you replace that memcpy with an assignment?

   _State_base::operator=(__rhs);

The implicitly defined assignment operator should do the same thing as
a memcpy.

_State should have a deleted copy assignment operator though (or a
user-provided one that correctly handles the _S_opcode_match case, but
since it's not needed it should just be deleted).

I'll review the rest of the patch ASAP.

Bootstrapped and tested.

Thanks!


--
Regards,
Tim Shen

commit c546499cac2bdb13b31dff373fc814a1330bbdeb
Author: Tim Shen <timshen@google.com>
Date:   Fri Jul 24 23:12:09 2015 -0700

   	* include/bits/regex_automaton.h(_State_base, _State<>):
   	Remove _TraitsT dependency from _State<>; Make matcher member
   	into the union to reduce struct size.
   	* include/bits/regex_automaton.tcc(_State_base<>::_M_print,
   	_State_base<>::_M_dot, _StateSeq<>::_M_clone):
   	Adjust to fit the interface. Factor out common parts in
   	_M_clone as _State<>::_M_has_alt.
   	* include/bits/regex_executor.h: Pass by const reference for
   	_M_lookahead.
   	* include/bits/regex_executor.tcc: Adjust to fit the interface.

diff --git a/libstdc++-v3/include/bits/regex_automaton.h b/libstdc++-v3/include/bits/regex_automaton.h
index fc0eb41..298c6b0 100644
--- a/libstdc++-v3/include/bits/regex_automaton.h
+++ b/libstdc++-v3/include/bits/regex_automaton.h
@@ -70,51 +70,126 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      _S_opcode_accept,
  };

-  struct _State_base
-  {
-    _Opcode      _M_opcode;           // type of outgoing transition
-    _StateIdT    _M_next;             // outgoing transition
-    union // Since they are mutually exclusive.
+  template<size_t _Matcher_size>
+    struct _State_base
    {
-      size_t _M_subexpr;        // for _S_opcode_subexpr_*
-      size_t _M_backref_index;  // for _S_opcode_backref
-      struct
+    protected:
+      _Opcode      _M_opcode;           // type of outgoing transition
+
+    public:
+      _StateIdT    _M_next;             // outgoing transition
+      union // Since they are mutually exclusive.
      {
-	// for _S_opcode_alternative, _S_opcode_repeat and
-	// _S_opcode_subexpr_lookahead
-	_StateIdT  _M_alt;
-	// for _S_opcode_word_boundary or _S_opcode_subexpr_lookahead or
-	// quantifiers (ungreedy if set true)
-	bool       _M_neg;
+	size_t _M_subexpr;        // for _S_opcode_subexpr_*
+	size_t _M_backref_index;  // for _S_opcode_backref
+	struct
+	{
+	  // for _S_opcode_alternative, _S_opcode_repeat and
+	  // _S_opcode_subexpr_lookahead
+	  _StateIdT  _M_alt;
+	  // for _S_opcode_word_boundary or _S_opcode_subexpr_lookahead or
+	  // quantifiers (ungreedy if set true)
+	  bool       _M_neg;
+	};
+	char _M_matcher_storage[_Matcher_size];        // for _S_opcode_match
      };
-    };

-    explicit _State_base(_Opcode __opcode)
-    : _M_opcode(__opcode), _M_next(_S_invalid_state_id)
-    { }
+    protected:
+      _State_base() = default;

-  protected:
-    ~_State_base() = default;
+      explicit _State_base(_Opcode __opcode)
+      : _M_opcode(__opcode), _M_next(_S_invalid_state_id)
+      { }
+
+      void
+      _M_copy_common(const _State_base& __rhs)
+      {
+	_M_opcode = __rhs._M_opcode;
+	_M_next = __rhs._M_next;
+      }
+
+    public:
+      bool
+      _M_has_alt()
+      {
+	return _M_opcode == _S_opcode_alternative
+	  || _M_opcode == _S_opcode_repeat
+	  || _M_opcode == _S_opcode_subexpr_lookahead;
+      }

-  public:
#ifdef _GLIBCXX_DEBUG
-    std::ostream&
-    _M_print(std::ostream& ostr) const;
+      std::ostream&
+      _M_print(std::ostream& ostr) const;

-    // Prints graphviz dot commands for state.
-    std::ostream&
-    _M_dot(std::ostream& __ostr, _StateIdT __id) const;
+      // Prints graphviz dot commands for state.
+      std::ostream&
+      _M_dot(std::ostream& __ostr, _StateIdT __id) const;
#endif
-  };
+    };

-  template<typename _TraitsT>
-    struct _State : _State_base
+  template<typename _Char_type>
+    struct _State : _State_base<sizeof(_Matcher<_Char_type>)>
    {
-      typedef _Matcher<typename _TraitsT::char_type> _MatcherT;
+      typedef _Matcher<_Char_type> _MatcherT;
+      typedef _State_base<sizeof(_MatcherT)> _Base_type;
+
+      explicit
+      _State(_Opcode __opcode) : _Base_type(__opcode)
+      {
+	if (_M_opcode() == _S_opcode_match)
+	  new (this->_M_matcher_storage) _MatcherT();
+      }
+
+      _State(const _State& __rhs)
+      {
+	if (__rhs._M_opcode() == _S_opcode_match)
+	  {
+	    new (this->_M_matcher_storage) _MatcherT(__rhs._M_get_matcher());
+	    _Base_type::_M_copy_common(__rhs);
+	  }
+	else
+	  {
+	    ::memcpy(this, &__rhs, sizeof(__rhs));
+	  }
+      }
+
+      _State(_State&& __rhs)
+      {
+	if (__rhs._M_opcode() == _S_opcode_match)
+	  {
+	    new (this->_M_matcher_storage)
+	      _MatcherT(std::move(__rhs._M_get_matcher()));
+	    _Base_type::_M_copy_common(__rhs);
+	  }
+	else
+	  {
+	    ::memcpy(this, &__rhs, sizeof(__rhs));
+	  }
+      }
+
+      ~_State()
+      {
+	if (_M_opcode() == _S_opcode_match)
+	  _M_get_matcher().~_MatcherT();
+      }
+
+      // Since correct ctor and dtor rely on _M_opcode, it's better not to
+      // change it over time.
+      _Opcode
+      _M_opcode() const
+      { return _Base_type::_M_opcode; }
+
+      bool
+      _M_matches(_Char_type __char) const
+      { return _M_get_matcher()(__char); }

-      _MatcherT      _M_matches;        // for _S_opcode_match
+      _MatcherT&
+      _M_get_matcher()
+      { return *reinterpret_cast<_MatcherT*>(this->_M_matcher_storage); }

-      explicit _State(_Opcode __opcode) : _State_base(__opcode) { }
+      const _MatcherT&
+      _M_get_matcher() const
+      { return *reinterpret_cast<const _MatcherT*>(this->_M_matcher_storage); }
    };

  struct _NFA_base
@@ -155,10 +230,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

  template<typename _TraitsT>
    struct _NFA
-    : _NFA_base, std::vector<_State<_TraitsT>>
+    : _NFA_base, std::vector<_State<typename _TraitsT::char_type>>
    {
-      typedef _State<_TraitsT>				_StateT;
-      typedef _Matcher<typename _TraitsT::char_type>	_MatcherT;
+      typedef typename _TraitsT::char_type	_Char_type;
+      typedef _State<_Char_type>		_StateT;
+      typedef _Matcher<_Char_type>		_MatcherT;

      _NFA(const typename _TraitsT::locale_type& __loc, _FlagT __flags)
      : _NFA_base(__flags)
@@ -202,7 +278,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      _M_insert_matcher(_MatcherT __m)
      {
	_StateT __tmp(_S_opcode_match);
-	__tmp._M_matches = std::move(__m);
+	__tmp._M_get_matcher() = std::move(__m);
	return _M_insert_state(std::move(__tmp));
      }

diff --git a/libstdc++-v3/include/bits/regex_automaton.tcc b/libstdc++-v3/include/bits/regex_automaton.tcc
index 72fe978..a5906a4 100644
--- a/libstdc++-v3/include/bits/regex_automaton.tcc
+++ b/libstdc++-v3/include/bits/regex_automaton.tcc
@@ -35,101 +35,103 @@ namespace __detail
_GLIBCXX_BEGIN_NAMESPACE_VERSION

#ifdef _GLIBCXX_DEBUG
-  inline std::ostream&
-  _State_base::_M_print(std::ostream& ostr) const
-  {
-    switch (_M_opcode)
+  template<size_t _Matcher_size>
+    std::ostream&
+    _State_base<_Matcher_size>::_M_print(std::ostream& ostr) const
    {
-      case _S_opcode_alternative:
-      case _S_opcode_repeat:
-	ostr << "alt next=" << _M_next << " alt=" << _M_alt;
-	break;
-      case _S_opcode_subexpr_begin:
-	ostr << "subexpr begin next=" << _M_next << " index=" << _M_subexpr;
-	break;
-      case _S_opcode_subexpr_end:
-	ostr << "subexpr end next=" << _M_next << " index=" << _M_subexpr;
-	break;
-      case _S_opcode_backref:
-	ostr << "backref next=" << _M_next << " index=" << _M_backref_index;
-	break;
-      case _S_opcode_match:
-	ostr << "match next=" << _M_next;
-	break;
-      case _S_opcode_accept:
-	ostr << "accept next=" << _M_next;
-	break;
-      default:
-	ostr << "unknown next=" << _M_next;
-	break;
+      switch (_M_opcode)
+      {
+	case _S_opcode_alternative:
+	case _S_opcode_repeat:
+	  ostr << "alt next=" << _M_next << " alt=" << _M_alt;
+	  break;
+	case _S_opcode_subexpr_begin:
+	  ostr << "subexpr begin next=" << _M_next << " index=" << _M_subexpr;
+	  break;
+	case _S_opcode_subexpr_end:
+	  ostr << "subexpr end next=" << _M_next << " index=" << _M_subexpr;
+	  break;
+	case _S_opcode_backref:
+	  ostr << "backref next=" << _M_next << " index=" << _M_backref_index;
+	  break;
+	case _S_opcode_match:
+	  ostr << "match next=" << _M_next;
+	  break;
+	case _S_opcode_accept:
+	  ostr << "accept next=" << _M_next;
+	  break;
+	default:
+	  ostr << "unknown next=" << _M_next;
+	  break;
+      }
+      return ostr;
    }
-    return ostr;
-  }

  // Prints graphviz dot commands for state.
-  inline std::ostream&
-  _State_base::_M_dot(std::ostream& __ostr, _StateIdT __id) const
-  {
-    switch (_M_opcode)
+  template<size_t _Matcher_size>
+    std::ostream&
+    _State_base<_Matcher_size>::_M_dot(std::ostream& __ostr, _StateIdT __id) const
    {
-      case _S_opcode_alternative:
-      case _S_opcode_repeat:
-	__ostr << __id << " [label=\"" << __id << "\\nALT\"];\n"
-	       << __id << " -> " << _M_next
-	       << " [label=\"next\", tailport=\"s\"];\n"
-	       << __id << " -> " << _M_alt
-	       << " [label=\"alt\", tailport=\"n\"];\n";
-	break;
-      case _S_opcode_backref:
-	__ostr << __id << " [label=\"" << __id << "\\nBACKREF "
-	       << _M_subexpr << "\"];\n"
-	       << __id << " -> " << _M_next << " [label=\"<match>\"];\n";
-	break;
-      case _S_opcode_line_begin_assertion:
-	__ostr << __id << " [label=\"" << __id << "\\nLINE_BEGIN \"];\n"
-	       << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
-	break;
-      case _S_opcode_line_end_assertion:
-	__ostr << __id << " [label=\"" << __id << "\\nLINE_END \"];\n"
-	       << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
-	break;
-      case _S_opcode_word_boundary:
-	__ostr << __id << " [label=\"" << __id << "\\nWORD_BOUNDRY "
-	       << _M_neg << "\"];\n"
-	       << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
-	break;
-      case _S_opcode_subexpr_lookahead:
-	__ostr << __id << " [label=\"" << __id << "\\nLOOK_AHEAD\"];\n"
-	       << __id << " -> " << _M_next
-	       << " [label=\"epsilon\", tailport=\"s\"];\n"
-	       << __id << " -> " << _M_alt
-	       << " [label=\"<assert>\", tailport=\"n\"];\n";
-	break;
-      case _S_opcode_subexpr_begin:
-	__ostr << __id << " [label=\"" << __id << "\\nSBEGIN "
-	       << _M_subexpr << "\"];\n"
-	       << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
-	break;
-      case _S_opcode_subexpr_end:
-	__ostr << __id << " [label=\"" << __id << "\\nSEND "
-	       << _M_subexpr << "\"];\n"
-	       << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
-	break;
-      case _S_opcode_dummy:
-	break;
-      case _S_opcode_match:
-	__ostr << __id << " [label=\"" << __id << "\\nMATCH\"];\n"
-	       << __id << " -> " << _M_next << " [label=\"<match>\"];\n";
-	break;
-      case _S_opcode_accept:
-	__ostr << __id << " [label=\"" << __id << "\\nACC\"];\n" ;
-	break;
-      default:
-	_GLIBCXX_DEBUG_ASSERT(false);
-	break;
+      switch (_M_opcode)
+      {
+	case _S_opcode_alternative:
+	case _S_opcode_repeat:
+	  __ostr << __id << " [label=\"" << __id << "\\nALT\"];\n"
+		 << __id << " -> " << _M_next
+		 << " [label=\"next\", tailport=\"s\"];\n"
+		 << __id << " -> " << _M_alt
+		 << " [label=\"alt\", tailport=\"n\"];\n";
+	  break;
+	case _S_opcode_backref:
+	  __ostr << __id << " [label=\"" << __id << "\\nBACKREF "
+		 << _M_subexpr << "\"];\n"
+		 << __id << " -> " << _M_next << " [label=\"<match>\"];\n";
+	  break;
+	case _S_opcode_line_begin_assertion:
+	  __ostr << __id << " [label=\"" << __id << "\\nLINE_BEGIN \"];\n"
+		 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
+	  break;
+	case _S_opcode_line_end_assertion:
+	  __ostr << __id << " [label=\"" << __id << "\\nLINE_END \"];\n"
+		 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
+	  break;
+	case _S_opcode_word_boundary:
+	  __ostr << __id << " [label=\"" << __id << "\\nWORD_BOUNDRY "
+		 << _M_neg << "\"];\n"
+		 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
+	  break;
+	case _S_opcode_subexpr_lookahead:
+	  __ostr << __id << " [label=\"" << __id << "\\nLOOK_AHEAD\"];\n"
+		 << __id << " -> " << _M_next
+		 << " [label=\"epsilon\", tailport=\"s\"];\n"
+		 << __id << " -> " << _M_alt
+		 << " [label=\"<assert>\", tailport=\"n\"];\n";
+	  break;
+	case _S_opcode_subexpr_begin:
+	  __ostr << __id << " [label=\"" << __id << "\\nSBEGIN "
+		 << _M_subexpr << "\"];\n"
+		 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
+	  break;
+	case _S_opcode_subexpr_end:
+	  __ostr << __id << " [label=\"" << __id << "\\nSEND "
+		 << _M_subexpr << "\"];\n"
+		 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
+	  break;
+	case _S_opcode_dummy:
+	  break;
+	case _S_opcode_match:
+	  __ostr << __id << " [label=\"" << __id << "\\nMATCH\"];\n"
+		 << __id << " -> " << _M_next << " [label=\"<match>\"];\n";
+	  break;
+	case _S_opcode_accept:
+	  __ostr << __id << " [label=\"" << __id << "\\nACC\"];\n" ;
+	  break;
+	default:
+	  _GLIBCXX_DEBUG_ASSERT(false);
+	  break;
+      }
+      return __ostr;
    }
-    return __ostr;
-  }

  template<typename _TraitsT>
    std::ostream&
@@ -174,13 +176,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    {
      for (auto& __it : *this)
	{
-	  while (__it._M_next >= 0 && (*this)[__it._M_next]._M_opcode
+	  while (__it._M_next >= 0 && (*this)[__it._M_next]._M_opcode()
		 == _S_opcode_dummy)
	    __it._M_next = (*this)[__it._M_next]._M_next;
-	  if (__it._M_opcode == _S_opcode_alternative
-	      || __it._M_opcode == _S_opcode_repeat
-	      || __it._M_opcode == _S_opcode_subexpr_lookahead)
-	    while (__it._M_alt >= 0 && (*this)[__it._M_alt]._M_opcode
+	  if (__it._M_has_alt())
+	    while (__it._M_alt >= 0 && (*this)[__it._M_alt]._M_opcode()
		   == _S_opcode_dummy)
	      __it._M_alt = (*this)[__it._M_alt]._M_next;
	}
@@ -200,11 +200,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
	  __stack.pop();
	  auto __dup = _M_nfa[__u];
	  // _M_insert_state() never return -1
-	  auto __id = _M_nfa._M_insert_state(__dup);
+	  auto __id = _M_nfa._M_insert_state(std::move(__dup));
	  __m[__u] = __id;
-	  if (__dup._M_opcode == _S_opcode_alternative
-	      || __dup._M_opcode == _S_opcode_repeat
-	      || __dup._M_opcode == _S_opcode_subexpr_lookahead)
+	  if (__dup._M_has_alt())
	    if (__dup._M_alt != _S_invalid_state_id
		&& __m.count(__dup._M_alt) == 0)
	      __stack.push(__dup._M_alt);
@@ -223,9 +221,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
	      _GLIBCXX_DEBUG_ASSERT(__m.count(__ref._M_next) > 0);
	      __ref._M_next = __m[__ref._M_next];
	    }
-	  if (__ref._M_opcode == _S_opcode_alternative
-	      || __ref._M_opcode == _S_opcode_repeat
-	      || __ref._M_opcode == _S_opcode_subexpr_lookahead)
+	  if (__ref._M_has_alt())
	    if (__ref._M_alt != _S_invalid_state_id)
	      {
		_GLIBCXX_DEBUG_ASSERT(__m.count(__ref._M_alt) > 0);
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index 404f30b..c97e056 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -148,7 +148,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      _M_word_boundary() const;

      bool
-      _M_lookahead(_State<_TraitsT> __state);
+      _M_lookahead(const _State<_CharT>& __state);

       // Holds additional information used in BFS-mode.
      template<typename _SearchMode, typename _ResultsVec>
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 9b5c1c6..1bc7739 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -145,7 +145,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
  template<typename _BiIter, typename _Alloc, typename _TraitsT,
	   bool __dfs_mode>
    bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_lookahead(_State<_TraitsT> __state)
+    _M_lookahead(const _State<_CharT>& __state)
    {
      _ResultsVec __what(_M_cur_results.size());
      _Executor __sub(_M_current, _M_end, __what, _M_re, _M_flags);
@@ -203,7 +203,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      const auto& __state = _M_nfa[__i];
      // Every change on _M_cur_results and _M_current will be rolled back after
      // finishing the recursion step.
-      switch (__state._M_opcode)
+      switch (__state._M_opcode())
	{
	// _M_alt branch is "match once more", while _M_next is "get me out
	// of this quantifier". Executing _M_next first or _M_alt first don't

Follow-Ups:
- Re: [Patch] Small refactor on <regex> _State<>
  - From: Tim Shen

References:
- [Patch] Small refactor on <regex> _State<>
  - From: Tim Shen

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]