Now that _Executor is non-recursive most subroutines no longer use their
_Match_mode parameter (previously it was just passed to recursive _M_dfs
calls). For now, just make them unnamed to avoid warnings.
libstdc++-v3/ChangeLog:
* include/bits/regex_executor.tcc (_Executor::_M_rep_once_more):
Make unnused _Match_mode parameter unnamed.
(_Executor::_M_handle_repeat): Likewise.
(_Executor::_M_handle_subexpr_begin): Likewise.
(_Executor::_M_handle_subexpr_end): Likewise.
(_Executor::_M_handle_line_begin_assertion): Likewise.
(_Executor::_M_handle_line_end_assertion): Likewise.
(_Executor::_M_handle_match): Likewise.
(_Executor::_M_handle_backref): Likewise.
(_Executor::_M_handle_alternative): Likewise.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
This mechanical patch removes _Executor's __dfs_mode template parameter.
In passing we can also get rid of the _V2 inline namespace because this
removal alone achieve the goal of the inline namespace which is to make
all of _Executor's member function signatures different from the
previous (GCC < 16) recursive implementation, allowing for safe mixing
of the two incompatible implementations.
libstdc++-v3/ChangeLog:
* include/bits/regex.h (_Executor): Remove __dfs_mode template
parameter and _V2 inline namespace.
* include/bits/regex.tcc (__regex_algo_impl): Adjust after
__dfs_mode template parameter removal.
* include/bits/regex_executor.h (_Executor): Remove __dfs_mode
parameter and _V2 inline namespace.
* include/bits/regex_executor.tcc (_Executor): Likewise.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
That _Executor's __dfs_mode flag is a template parameter means
__regex_algo_impl has to instantiate two different (but largely the
same) versions of _Executor even though the BFS version is rarely used.
And it seems the compiler has trouble DCEing the unused version of
_Executor, which needlessly increases code size and burdens the optimizer.
This patch replaces the template parameter with a run-time data member
_M_search_mode. We in turn need to inline the _Executor::_State_info
member functions and data members into _Executor so that they depend on
the run-time instead of compile-time flag. This means _Executor is
three pointers bigger in DFS mode (due to the unused _M_match_queue and
_M_visited_states members), which we can reduce to one pointer if we
really want to, but that doesn't seem ver worthwhile.
The __dfs_mode template parameter is now unused but not yet removed,
that'll be done in the next patch.
After this patch, both code size and run time for the microbenchmark
for (int i = 0; i < 10000; i++)
regex_match(string(200, 'a'), regex("(a|b|c)*"));
decreases by about 15% each (with -O2). Compile time/memory use decreases
by 5-10%.
libstdc++-v3/ChangeLog:
* include/bits/regex.tcc (__regex_algo_impl): Pass __use_dfs
parameter to _Executor's constructor.
* include/bits/regex_executor.h (_Executor::_Search_mode): New.
(_Executor::_Executor): Add __use_dfs parameter and initialize
_M_search_mode. Adjust after inlining _State_info members into
_Executor.
(_Executor::~_Executor): Free _M_visted_states.
(_Executor::_M_main): Adjust after renaming _M_main_dispatch
overloads to _M_main_dfs and _M_main_bfs.
(_Executor::_State_info): Remove.
(_Executor::_M_visited): Inlined from _State_info.
(_Executor::_M_get_sol_pos): Likewise.
(_Executor::_M_states): Remove.
(_Executor::_M_start): Inlined from _State_info.
(_Executor::_M_sol_pos): Likewise.
(_Executor::_M_match_queue): Likewise.
(_Executor::_M_search_mode): New.
* include/bits/regex_executor.tcc (_Executor::_M_main_dispatch):
Renamed to...
(_Executor::_M_main_dfs, _Executor::_M_main_bfs): ... these.
(_Executor::_M_*): Adjust after _M_states removal.
(_Executor::_M_lookhead): Also adjust _Executor constructor
call.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Prevents uninitialized read bugs, and it's also just natural to assume
flags are initially cleared rather than uninitialized.
In passing rename the _M_end flag to _M_subexpr_end to make it distinct
from _Executor::_M_end.
libstdc++-v3/ChangeLog:
* include/bits/regex_executor.tcc (_ExecutorFrameBase):
Zero-initialize _M_byte0.
(_ExecutorFrameBase::_M_end): Rename to ...
(_ExecutorFrameBase::_M_subexpr_end): ... this.
(_Executor::_M_handle_subexpr_begin): Remove now redundant
clearing of _M_subexpr_end.
(_Executor::_M_handle_subexpr_end): Adjust after renaming.
(_Executor::_M_dfs) <case _S_fopcode_restore_cur_results>:
Likewise.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
The compiler understandably doesn't know that _M_node only ever has a
single call site, _M_dfs, (and is not directly called from other library
headers or user code) and so decides not to inline it. So use the
always_inline attribute to force the inlining. This seems sufficient to
make all _M_dfs subroutines get inlined away, and speeds up the executor
by 30% on some microbenchmarks.
libstdc++-v3/ChangeLog:
* include/bits/regex_executor.tcc (__detail::_Executor::_M_node)
[__OPTIMIZE__]: Add [[gnu::always_inline]] attribute. Declare
inline.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
The incrementing of the current input string position (_M_current) is
done by _M_handle_match, which also makes sure to restore it afterwards,
via a restore_current frame. But restoring _M_current is naturally only
necessary when backtracking is involved, not after every single match.
So this patch moves the responsibility of saving/restoring _M_current
from _M_handle_match to the branching nodes _M_handle_alternative and
_M_handle_repeat. This is done by storing _M_current within the
fallback_next, fallback_rep_once_more and posix_alternative frames.
In turn we can get rid of the now unused restore_current frame kind.
This reduces the maximum size of the _M_frames stack by 15% for
regex_match(string(200000, 'a'), "(a|b|c)*")
PR libstdc++/86164
libstdc++-v3/ChangeLog:
* include/bits/regex_executor.tcc (__detail::_ExecutorFrameOpcode):
Remove _S_fopcode_restore_current.
(__detail::_Executor::_M_handle_repeat): Pass _M_current when
pushing a fallback_next or fallback_rep_once_more frame.
(__detail::_Executor::_M_handle_match): Don't push a
restore_current frame.
(__detail::_Executor::_M_handle_backref): Likewise and simplify
accordingly.
(__detail::_Executor::_M_handle_alternative): Pass _M_current when
pushing a fallback_next or posix_alternative frame.
(__detail::_Executor::_M_dfs) <case _S_fopcode_fallback_next>:
Restore _M_current.
<case _S_fopcode_fallback_rep_once_more>: Likewise.
<case _S_fopcode_posix_alternative>: Likewise.
<case _S_fopcode_restore_current>: Remove.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
This patch replaces the recursive implementation of the DFS executor
with an iterative one using an explicit heap-based stack. System
stack usage of the executor is now constant with respect to input size
rather than linear, avoding stack overflow errors when processing
long inputs.
PR libstdc++/86164
libstdc++-v3/ChangeLog:
* include/bits/regex.h (__detail::_Executor): Use inline
namespace _V2.
* include/bits/regex_executor.h (__detail::_ExecutorFrame):
Declare.
(__detail::_Executor): Use inline namespace _V2.
(__detail::_Executor::_M_node): Declare.
(__detail::_Executor::_M_frames): New data member.
* include/bits/regex_executor.tcc (__detail::_ExecutorFrameOpcode):
New.
(__detail::_ExecutorFrameBase): New.
(__detail::_ExecutorFrame): New.
(__detail::_Executor): Use inline namespace _V2.
(__detail::_Executor::_M_rep_once_more): Replace recursive
_M_dfs calls with an _S_opcode_next frame push, and any work
after such calls with an appropriate frame push.
(__detail::_M_handle_repeat): Likewise.
(__detail::_M_handle_subexpr_begin): Likewise.
(__detail::_M_handle_subexpr_end): Likewise.
(__detail::_M_handle_line_begin_assertion): Likewise.
(__detail::_M_handle_line_end_assertion): Likewise.
(__detail::_M_handle_word_boundary): Likewise.
(__detail::_M_handle_subexpr_lookahead): Likewise.
(__detail::_M_handle_match): Likewise.
(__detail::_M_handle_backref): Likewise.
(__detail::_M_handle_accept): Likewise.
(__detail::_M_handle_alternative): Likewise.
(__detail::_M_node): Factored out from _M_dfs.
(__detail::_M_dfs): Push an initial frame to _M_frames that
visits the starting node and pass this stack each subroutine.
Pop the latest _ExecutorFrame from _M_frames and handle
appropriately according to its _ExecutorFrameOpcode. Loop until
_M_frames is empty.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
This will hardly make a dent in the very slow compile times for <regex>
but it seems worth doing anyway.
libstdc++-v3/ChangeLog:
* include/bits/regex_compiler.h: Replace _GLIBCXX17_CONSTEXPR
with constexpr and disable diagnostics with pragmas.
(_AnyMatcher::operator()): Use constexpr-if instead of tag
dispatching. Postpone calls to _M_translate until after checking
result of earlier calls.
(_AnyMatcher::_M_apply): Remove both overloads.
(_BracketMatcher::operator(), _BracketMatcher::_M_ready):
Replace tag dispatching with 'if constexpr'.
(_BracketMatcher::_M_apply(_CharT, true_type)): Remove.
(_BracketMatcher::_M_apply(_CharT, false_type)): Remove second
parameter.
(_BracketMatcher::_M_make_cache): Remove both overloads.
* include/bits/regex_compiler.tcc (_BracketMatcher::_M_apply):
Remove second parameter.
* include/bits/regex_executor.tcc: Replace _GLIBCXX17_CONSTEXPR
with constexpr and disable diagnostics with pragmas.
(_Executor::_M_handle_backref): Replace __glibcxx_assert with
static_assert.
(_Executor::_M_handle_accept): Mark _S_opcode_backref case as
unreachable for non-DFS mode and do not instantiate
_M_handle_backref for that case.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
The PR points out that we assume the match_results allocator is default
constuctible, which might not be true. We also have a related issue with
unwanted propagation from an object that might have an unequal
allocator.
Ideally we use the same allocator type for _State_info::_M_match_queue
but that would be an ABI change now. We should investigate if that can
be done without breaking anything, which might be possible because the
_Executor object is short-lived and never leaks out of the regex_match,
regex_search, and regex_replace algorithms. If we change the mangled
name for _Executor then there would be no ODR violations when mixing old
and new definitions. This commit does not attempt that.
libstdc++-v3/ChangeLog:
PR libstdc++/107376
* include/bits/regex_executor.h (_Executor::_Executor): Use same
allocator for _M_cur_results and _M_results.
* include/bits/regex_executor.tcc (_Executor::_M_main_dispatch):
Prevent possibly incorrect allocator propagating to
_M_cur_results.
* testsuite/28_regex/algorithms/regex_match/107376.cc: New test.
This moves the last two template parameters of __regex_algo_impl to be
runtime function parameters instead, so that we don't need four
different instantiations for the possible ways to call it. Most of the
function (and what it instantiates) is the same in all cases, so making
them compile-time choices doesn't really have much benefit.
Use 'if constexpr' for conditions that check template parameters, so
that when we do depend on a compile-time condition we only instantiate
what we need to.
libstdc++-v3/ChangeLog:
* include/bits/regex.h (__regex_algo_impl): Change __policy and
__match_mode template parameters to be function parameters.
(regex_match, regex_search): Pass policy and match mode as
function arguments.
* include/bits/regex.tcc (__regex_algo_impl): Change template
parameters to function parameters.
* include/bits/regex_compiler.h (_RegexTranslatorBase): Use
'if constexpr' for conditions using template parameters.
(_RegexTranslator): Likewise.
* include/bits/regex_executor.tcc (_Executor::_M_handle_accept):
Likewise.
* testsuite/util/testsuite_regex.h (regex_match_debug)
(regex_search_debug): Move template arguments to function
arguments.
Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
* include/bits/regex_compiler.tcc: Add line break in empty while
statement.
* include/bits/regex_executor.tcc: Avoid unused parameter
warning.
This reduces the size of <regex> a little. This is one of the largest
and slowest headers in the library.
By using <bits/stl_algobase.h> and <bits/stl_algo.h> instead of
<algorithm> we don't need to parse all the parallel algorithms and
std::ranges:: algorithms that are not needed by <regex>. Similarly, by
using <bits/stl_tree.h> and <bits/stl_map.h> instead of <map> we don't
need to parse the definition of std::multimap.
The _State_info type is not movable or copyable, so doesn't need to use
std::unique_ptr<bool[]> to manage a bitset, we can just delete it in the
destructor. It would use a lot less space if we used a bitset instead,
but that would be an ABI break. We could do it for the versioned
namespace, but this patch doesn't do so. For future reference, using
vector<bool> would work, but would increase sizeof(_State_info) by two
pointers, because it's three times as large as unique_ptr<bool[]>. We
can't use std::bitset because the length isn't constant. We want a
bitset with a non-constant but fixed length.
Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
* include/bits/regex_executor.h (_State_info): Replace
unique_ptr<bool[]> with array of bool.
* include/bits/regex_executor.tcc: Likewise.
* include/bits/regex_scanner.tcc: Replace std::strchr with
__builtin_strchr.
* include/std/regex: Replace standard headers with smaller
internal ones.
* testsuite/28_regex/traits/char/lookup_classname.cc: Include
<string.h> for strlen.
* testsuite/28_regex/traits/char/lookup_collatename.cc:
Likewise.
* include/bits/regex_executor.tcc (_Backref_matcher::_M_apply): Use
_GLIBCXX_STD_A to refer to normal mode algorithms.
* testsuite/28_regex/headers/regex/parallel_mode.cc: New test.
* testsuite/28_regex/headers/regex/std_c++0x_neg.cc: Remove empty
whitespace.
From-SVN: r265314
PR libstdc++/71500
* include/bits/regex_executor.tcc
(_Backref_matcher<BidIt, regex_traits<C>>::_M_apply): Use
std::__equal4 instead of C++14 4-iterator overloads of std::equal.
* include/bits/stl_algobase.h (__equal4): New functions implementing
4-iterator overloads of std::equal for use in C++11.
(equal(It1, It1, It2, It2), equal(It1, It1, It2, It2, BinaryPred)):
Move function bodies to new __equal4 functions.
* testsuite/28_regex/simple_c++11.cc: New.
From-SVN: r252981
PR libstdc++/71500
* include/bits/regex_executor.tcc: Support icase in regex_tratis<...>
for back reference matches.
* testsuite/28_regex/regression.cc: Test case.
From-SVN: r251982
PR libstdc++/68863
* include/bits/regex_executor.tcc (_Executor::_M_lookahead):
Copy the captured content for lookahead, so that the backreferences
inside can refer to them.
* testsuite/28_regex/algorithms/regex_match/ecma/char/68863.cc:
New testcase.
From-SVN: r231641
* 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 (_Executer<>::_M_lookahead):
Only pass state id instead of the whole state.
* include/bits/regex_executor.tcc (_Executer<>::_M_dfs,
_Executer<>::_M_lookahead): Adjust to fit the interface.
* include/std/regex: Include <ext/aligned_buffer.h>
From-SVN: r226395
* include/bits/regex.tcc: Handle regex_constants::__polynomial.
* include/bits/regex_automaton.tcc: Throw exception when parsing
back-reference with flag __polynomial.
* include/bits/regex_constants.h: Add extension flag
syntax_option_type __polynomial.
* bits/regex_executor.tcc: Still let BFS process ECMAScript.
Alternative operation will be fixed in the coming refactoring.
* testsuite/28_regex/algorithms/regex_search/61424.cc: Turn
loose match_search_debug to use DFS only.
From-SVN: r222500
PR libstdc++/64475
* include/bits/regex_executor.tcc (_Executor<>::_M_dfs): Copy the
iterator, since the original one shouldn't be mutated.
From-SVN: r219151
PR libstdc++/63920
* include/bits/regex_executor.h: Make _M_begin non const.
* include/bits/regex_executor.tcc (_Executor<>::_M_search): Increase
_M_begin in search algorithm, so that _M_begin is treated as
"current start position" for each search iteration.
* testsuite/28_regex/algorithms/regex_search/ecma/flags.cc: New
testcase.
From-SVN: r218037
PR libstdc++/61720
* include/bits/regex_executor.tcc (_Executor<>::_M_main_dispatch):
Clear match queue for next use.
* testsuite/28_regex/algorithms/regex_search/61720.cc: New file.
From-SVN: r212539
PR libstdc++/61424
* include/bits/regex.tcc (__regex_algo_impl<>): Use DFS for ECMAScript,
not just regex containing back-references.
* include/bits/regex_compiler.tcc (_Compiler<>::_M_disjunction):
exchange _M_next and _M_alt for alternative operator,
making matching from left to right.
* include/bits/regex_executor.h (_State_info<>::_M_get_sol_pos):
Add position tracking fom DFS.
* include/bits/regex_executor.tcc (_Executor<>::_M_main_dispatch,
_Executor<>::_M_dfs): Likewise.
* include/bits/regex_scanner.h: Remove unused enum entry.
* testsuite/28_regex/algorithms/regex_search/61424.cc: New
testcase from PR.
From-SVN: r212184
* include/bits/regex_compiler.h (__detail::_BracketMatcher): Reorder
members to avoid wasted space when not using a cache.
(__detail::_BracketMatcher::_M_ready()): Sort and deduplicate set.
* include/bits/regex_compiler.tcc
(__detail::_BracketMatcher::_M_apply(_CharT, false_type)): Use binary
search on set.
* include/bits/regex_executor.h (__detail::_Executor::_Match_mode):
New enumeration type to indicate match mode.
(__detail::_Executor::_State_info): New type holding members only
needed in BFS-mode. Replace unique_ptr<vector<bool>> with
unique_ptr<bool[]>.
(__detail::_Executor::_M_rep_once_more, __detail::_Executor::_M_dfs):
Replace template parameter with run-time function parameter.
(__detail::_Executor::_M_main): Likewise. Dispatch to ...
(__detail::_Executor::_M_main_dispatch): New overloaded functions to
implement DFS and BFS mode.
* include/bits/regex_executor.tcc (__detail::_Executor::_M_main):
Split implementation into ...
(__detail::_Executor::_M_main_dispatch): New overloaded functions.
(__detail::_Executor::_M_lookahead): Create nested executor on stack.
(__detail::_Executor::_M_rep_once_more): Pass match mode as function
argument instead of template argument.
(__detail::_Executor::_M_dfs): Likewise.
* include/bits/regex_scanner.tcc: Fix typos in comments.
* testsuite/performance/28_regex/range.cc: New.
From-SVN: r211143
2014-04-27 Tim Shen <timshen91@gmail.com>
* include/bits/regex_automaton.h (_NFA<>::_M_insert_repeat):
Add _S_opcode_repeat support to distingush a loop from
_S_opcode_alternative.
* include/bits/regex_automaton.tcc (_State_base::_M_print,
_State_base::_M_dot, _NFA<>::_M_eliminate_dummy,
_StateSeq<>::_M_clone): Likewise.
* include/bits/regex_compiler.tcc (_Compiler<>::_M_quantifier):
Likewise.
* include/bits/regex_executor.tcc (_Executor<>::_M_dfs): Likewise.
* include/bits/regex_scanner.tcc (_Scanner<>::_M_eat_escape_ecma):
Uglify local variable __i.
* include/bits/regex_compiler.h (_BracketMatcher<>::_M_make_cache):
Use size_t instead of int to compare with vector::size().
2014-04-27 Tim Shen <timshen91@gmail.com>
* include/bits/regex_executor.h: Add _M_rep_count to track how
many times this repeat node are visited.
* include/bits/regex_executor.tcc (_Executor<>::_M_rep_once_more,
_Executor<>::_M_dfs): Use _M_rep_count to prevent entering
infinite loop.
2014-04-27 Tim Shen <timshen91@gmail.com>
* include/bits/regex.tcc (__regex_algo_impl<>): Remove
_GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT and use
_GLIBCXX_REGEX_USE_THOMPSON_NFA instead.
* include/bits/regex_automaton.h: Remove quantifier counting variable.
* include/bits/regex_automaton.tcc (_State_base::_M_dot):
Adjust debug NFA dump.
From-SVN: r209844
2014-01-17 Tim Shen <timshen91@gmail.com>
* include/bits/regex_automaton.tcc (_StateSeq<>::_M_clone()): Do not
use std::map.
* include/bits/regex_automaton.h: Do not use std::set.
* include/bits/regex_compiler.h (_BracketMatcher<>::_M_add_char(),
_BracketMatcher<>::_M_add_collating_element(),
_BracketMatcher<>::_M_add_equivalence_class(),
_BracketMatcher<>::_M_make_range()): Likewise.
* include/bits/regex_compiler.tcc (_BracketMatcher<>::_M_apply()):
Likewise.
* include/bits/regex_executor.h: Do not use std::queue.
* include/bits/regex_executor.tcc (_Executor<>::_M_main(),
_Executor<>::_M_dfs()): Likewise.
* include/std/regex: Remove <map>, <set> and <queue>.
2014-01-17 Tim Shen <timshen91@gmail.com>
* include/bits/regex.h (__compile_nfa<>(), basic_regex<>::basic_regex(),
basic_regex<>::assign()): Change __compile_nfa to accept
const _CharT* only.
* include/bits/regex_compiler.h: Change _Compiler's template
argument from <_FwdIter, _TraitsT> to <_TraitsT>.
* include/bits/regex_compiler.tcc: Likewise.
2014-01-17 Tim Shen <timshen91@gmail.com>
* include/bits/regex_compiler.h: Change _ScannerT into char-type
templated.
* include/bits/regex_scanner.h (_Scanner<>::_Scanner()): Separate
_ScannerBase from _Scanner; Change _Scanner's template argument from
_FwdIter to _CharT. Avoid use of std::map and std::set by using arrays
instead.
* include/bits/regex_scanner.tcc (_Scanner<>::_Scanner(),
_Scanner<>::_M_scan_normal(), _Scanner<>::_M_eat_escape_ecma(),
_Scanner<>::_M_eat_escape_posix(), _Scanner<>::_M_eat_escape_awk()):
Likewise.
* include/std/regex: Add <cstring> for using strchr.
2014-01-17 Tim Shen <timshen91@gmail.com>
* bits/regex_automaton.tcc: Indentation fix.
* bits/regex_compiler.h (__compile_nfa<>(), _Compiler<>,
_RegexTranslator<> _AnyMatcher<>, _CharMatcher<>,
_BracketMatcher<>): Add bool option template parameters and
specializations to make matching more efficient and space saving.
* bits/regex_compiler.tcc: Likewise.
From-SVN: r206690
Patrick Palka