[Patch] Small refactor on <regex> _State<>
Jonathan Wakely
jwakely@redhat.com
Sat Jul 25 15:31:00 GMT 2015
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
More information about the Libstdc++
mailing list