//usr/include/c++/11/bits
146 items
NAME ↑ SIZE MODIFIED PERMS ACTIONS
.. / Parent Directory
algorithmfwd.h — 23.97 KB
2025-09-15 15:41 · rw-r--r--
23.97 KB 2025-09-15 15:41 rw-r--r--
align.h — 3.62 KB
2025-09-15 15:41 · rw-r--r--
3.62 KB 2025-09-15 15:41 rw-r--r--
alloc_traits.h — 26.98 KB
2025-09-15 15:41 · rw-r--r--
26.98 KB 2025-09-15 15:41 rw-r--r--
allocated_ptr.h — 3.25 KB
2025-09-15 15:41 · rw-r--r--
3.25 KB 2025-09-15 15:41 rw-r--r--
allocator.h — 9.51 KB
2025-09-15 15:41 · rw-r--r--
9.51 KB 2025-09-15 15:41 rw-r--r--
atomic_base.h — 56.07 KB
2025-09-15 15:41 · rw-r--r--
56.07 KB 2025-09-15 15:41 rw-r--r--
atomic_futex.h — 12.1 KB
2025-09-15 15:41 · rw-r--r--
12.1 KB 2025-09-15 15:41 rw-r--r--
atomic_lockfree_defines.h — 2.3 KB
2025-09-15 15:41 · rw-r--r--
2.3 KB 2025-09-15 15:41 rw-r--r--
atomic_timed_wait.h — 13.21 KB
2025-09-15 15:41 · rw-r--r--
13.21 KB 2025-09-15 15:41 rw-r--r--
atomic_wait.h — 12.26 KB
2025-09-15 15:41 · rw-r--r--
12.26 KB 2025-09-15 15:41 rw-r--r--
basic_ios.h — 15.7 KB
2025-09-15 15:41 · rw-r--r--
15.7 KB 2025-09-15 15:41 rw-r--r--
basic_ios.tcc — 5.94 KB
2025-09-15 15:41 · rw-r--r--
5.94 KB 2025-09-15 15:41 rw-r--r--
basic_string.h — 246.04 KB
2025-09-15 15:41 · rw-r--r--
246.04 KB 2025-09-15 15:41 rw-r--r--
basic_string.tcc — 52.92 KB
2025-09-15 15:41 · rw-r--r--
52.92 KB 2025-09-15 15:41 rw-r--r--
boost_concept_check.h — 26.54 KB
2025-09-15 15:41 · rw-r--r--
26.54 KB 2025-09-15 15:41 rw-r--r--
c++0x_warning.h — 1.44 KB
2025-09-15 15:41 · rw-r--r--
1.44 KB 2025-09-15 15:41 rw-r--r--
char_traits.h — 28.66 KB
2025-09-15 15:41 · rw-r--r--
28.66 KB 2025-09-15 15:41 rw-r--r--
charconv.h — 3.35 KB
2025-09-15 15:41 · rw-r--r--
3.35 KB 2025-09-15 15:41 rw-r--r--
codecvt.h — 24.9 KB
2025-09-15 15:41 · rw-r--r--
24.9 KB 2025-09-15 15:41 rw-r--r--
concept_check.h — 3.34 KB
2025-09-15 15:41 · rw-r--r--
3.34 KB 2025-09-15 15:41 rw-r--r--
cpp_type_traits.h — 13.67 KB
2025-09-15 15:41 · rw-r--r--
13.67 KB 2025-09-15 15:41 rw-r--r--
cxxabi_forced.h — 1.77 KB
2025-09-15 15:41 · rw-r--r--
1.77 KB 2025-09-15 15:41 rw-r--r--
cxxabi_init_exception.h — 2.17 KB
2025-09-15 15:41 · rw-r--r--
2.17 KB 2025-09-15 15:41 rw-r--r--
deque.tcc — 41.37 KB
2025-09-15 15:41 · rw-r--r--
41.37 KB 2025-09-15 15:41 rw-r--r--
enable_special_members.h — 12.16 KB
2025-09-15 15:41 · rw-r--r--
12.16 KB 2025-09-15 15:41 rw-r--r--
erase_if.h — 2.02 KB
2025-09-15 15:41 · rw-r--r--
2.02 KB 2025-09-15 15:41 rw-r--r--
exception.h — 2.45 KB
2025-09-15 15:41 · rw-r--r--
2.45 KB 2025-09-15 15:41 rw-r--r--
exception_defines.h — 1.61 KB
2025-09-15 15:41 · rw-r--r--
1.61 KB 2025-09-15 15:41 rw-r--r--
exception_ptr.h — 7.46 KB
2025-09-15 15:41 · rw-r--r--
7.46 KB 2025-09-15 15:41 rw-r--r--
forward_list.h — 49.21 KB
2025-09-15 15:41 · rw-r--r--
49.21 KB 2025-09-15 15:41 rw-r--r--
forward_list.tcc — 13.71 KB
2025-09-15 15:41 · rw-r--r--
13.71 KB 2025-09-15 15:41 rw-r--r--
fs_dir.h — 16.23 KB
2025-09-15 15:41 · rw-r--r--
16.23 KB 2025-09-15 15:41 rw-r--r--
fs_fwd.h — 10.65 KB
2025-09-15 15:41 · rw-r--r--
10.65 KB 2025-09-15 15:41 rw-r--r--
fs_ops.h — 10.49 KB
2025-09-15 15:41 · rw-r--r--
10.49 KB 2025-09-15 15:41 rw-r--r--
fs_path.h — 39.49 KB
2025-09-15 15:41 · rw-r--r--
39.49 KB 2025-09-15 15:41 rw-r--r--
fstream.tcc — 32.88 KB
2025-09-15 15:41 · rw-r--r--
32.88 KB 2025-09-15 15:41 rw-r--r--
functexcept.h — 3.43 KB
2025-09-15 15:41 · rw-r--r--
3.43 KB 2025-09-15 15:41 rw-r--r--
functional_hash.h — 8.39 KB
2025-09-15 15:41 · rw-r--r--
8.39 KB 2025-09-15 15:41 rw-r--r--
gslice.h — 5.39 KB
2025-09-15 15:41 · rw-r--r--
5.39 KB 2025-09-15 15:41 rw-r--r--
gslice_array.h — 7.71 KB
2025-09-15 15:41 · rw-r--r--
7.71 KB 2025-09-15 15:41 rw-r--r--
hash_bytes.h — 2.1 KB
2025-09-15 15:41 · rw-r--r--
2.1 KB 2025-09-15 15:41 rw-r--r--
hashtable.h — 82.94 KB
2025-09-15 15:41 · rw-r--r--
82.94 KB 2025-09-15 15:41 rw-r--r--
hashtable_policy.h — 60.84 KB
2025-09-15 15:41 · rw-r--r--
60.84 KB 2025-09-15 15:41 rw-r--r--
indirect_array.h — 7.72 KB
2025-09-15 15:41 · rw-r--r--
7.72 KB 2025-09-15 15:41 rw-r--r--
invoke.h — 5.92 KB
2025-09-15 15:41 · rw-r--r--
5.92 KB 2025-09-15 15:41 rw-r--r--
ios_base.h — 31.19 KB
2025-09-15 15:41 · rw-r--r--
31.19 KB 2025-09-15 15:41 rw-r--r--
istream.tcc — 30.85 KB
2025-09-15 15:41 · rw-r--r--
30.85 KB 2025-09-15 15:41 rw-r--r--
iterator_concepts.h — 32.55 KB
2025-09-15 15:41 · rw-r--r--
32.55 KB 2025-09-15 15:41 rw-r--r--
list.tcc — 16.8 KB
2025-09-15 15:41 · rw-r--r--
16.8 KB 2025-09-15 15:41 rw-r--r--
locale_classes.h — 24.46 KB
2025-09-15 15:41 · rw-r--r--
24.46 KB 2025-09-15 15:41 rw-r--r--
locale_classes.tcc — 8.18 KB
2025-09-15 15:41 · rw-r--r--
8.18 KB 2025-09-15 15:41 rw-r--r--
locale_conv.h — 18.38 KB
2025-09-15 15:41 · rw-r--r--
18.38 KB 2025-09-15 15:41 rw-r--r--
locale_facets.h — 91.46 KB
2025-09-15 15:41 · rw-r--r--
91.46 KB 2025-09-15 15:41 rw-r--r--
locale_facets.tcc — 39.51 KB
2025-09-15 15:41 · rw-r--r--
39.51 KB 2025-09-15 15:41 rw-r--r--
locale_facets_nonio.h — 68.07 KB
2025-09-15 15:41 · rw-r--r--
68.07 KB 2025-09-15 15:41 rw-r--r--
locale_facets_nonio.tcc — 46.42 KB
2025-09-15 15:41 · rw-r--r--
46.42 KB 2025-09-15 15:41 rw-r--r--
localefwd.h — 5.8 KB
2025-09-15 15:41 · rw-r--r--
5.8 KB 2025-09-15 15:41 rw-r--r--
mask_array.h — 7.54 KB
2025-09-15 15:41 · rw-r--r--
7.54 KB 2025-09-15 15:41 rw-r--r--
max_size_type.h — 22.18 KB
2025-09-15 15:41 · rw-r--r--
22.18 KB 2025-09-15 15:41 rw-r--r--
memoryfwd.h — 2.45 KB
2025-09-15 15:41 · rw-r--r--
2.45 KB 2025-09-15 15:41 rw-r--r--
move.h — 6.64 KB
2025-09-15 15:41 · rw-r--r--
6.64 KB 2025-09-15 15:41 rw-r--r--
nested_exception.h — 4.77 KB
2025-09-15 15:41 · rw-r--r--
4.77 KB 2025-09-15 15:41 rw-r--r--
node_handle.h — 11.07 KB
2025-09-15 15:41 · rw-r--r--
11.07 KB 2025-09-15 15:41 rw-r--r--
ostream.tcc — 12.03 KB
2025-09-15 15:41 · rw-r--r--
12.03 KB 2025-09-15 15:41 rw-r--r--
ostream_insert.h — 3.94 KB
2025-09-15 15:41 · rw-r--r--
3.94 KB 2025-09-15 15:41 rw-r--r--
parse_numbers.h — 7.79 KB
2025-09-15 15:41 · rw-r--r--
7.79 KB 2025-09-15 15:41 rw-r--r--
postypes.h — 8.27 KB
2025-09-15 15:41 · rw-r--r--
8.27 KB 2025-09-15 15:41 rw-r--r--
predefined_ops.h — 9.94 KB
2025-09-15 15:41 · rw-r--r--
9.94 KB 2025-09-15 15:41 rw-r--r--
ptr_traits.h — 6.55 KB
2025-09-15 15:41 · rw-r--r--
6.55 KB 2025-09-15 15:41 rw-r--r--
quoted_string.h — 4.93 KB
2025-09-15 15:41 · rw-r--r--
4.93 KB 2025-09-15 15:41 rw-r--r--
random.h — 174.18 KB
2025-09-15 15:41 · rw-r--r--
174.18 KB 2025-09-15 15:41 rw-r--r--
random.tcc — 103.21 KB
2025-09-15 15:41 · rw-r--r--
103.21 KB 2025-09-15 15:41 rw-r--r--
range_access.h — 10.46 KB
2025-09-15 15:41 · rw-r--r--
10.46 KB 2025-09-15 15:41 rw-r--r--
ranges_algo.h — 114.09 KB
2025-09-15 15:41 · rw-r--r--
114.09 KB 2025-09-15 15:41 rw-r--r--
ranges_algobase.h — 18.43 KB
2025-09-15 15:41 · rw-r--r--
18.43 KB 2025-09-15 15:41 rw-r--r--
ranges_base.h — 23.82 KB
2025-09-15 15:41 · rw-r--r--
23.82 KB 2025-09-15 15:41 rw-r--r--
ranges_cmp.h — 5.88 KB
2025-09-15 15:41 · rw-r--r--
5.88 KB 2025-09-15 15:41 rw-r--r--
ranges_uninitialized.h — 17.71 KB
2025-09-15 15:41 · rw-r--r--
17.71 KB 2025-09-15 15:41 rw-r--r--
ranges_util.h — 20.11 KB
2025-09-15 15:41 · rw-r--r--
20.11 KB 2025-09-15 15:41 rw-r--r--
refwrap.h — 12.9 KB
2025-09-15 15:41 · rw-r--r--
12.9 KB 2025-09-15 15:41 rw-r--r--
regex.h — 101.53 KB
2025-09-15 15:41 · rw-r--r--
101.53 KB 2025-09-15 15:41 rw-r--r--
regex.tcc — 16.11 KB
2025-09-15 15:41 · rw-r--r--
16.11 KB 2025-09-15 15:41 rw-r--r--
regex_automaton.h — 10.54 KB
2025-09-15 15:41 · rw-r--r--
10.54 KB 2025-09-15 15:41 rw-r--r--
regex_automaton.tcc — 7.54 KB
2025-09-15 15:41 · rw-r--r--
7.54 KB 2025-09-15 15:41 rw-r--r--
regex_compiler.h — 15.84 KB
2025-09-15 15:41 · rw-r--r--
15.84 KB 2025-09-15 15:41 rw-r--r--
regex_compiler.tcc — 18.71 KB
2025-09-15 15:41 · rw-r--r--
18.71 KB 2025-09-15 15:41 rw-r--r--
regex_constants.h — 15.18 KB
2025-09-15 15:41 · rw-r--r--
15.18 KB 2025-09-15 15:41 rw-r--r--
regex_error.h — 4.9 KB
2025-09-15 15:41 · rw-r--r--
4.9 KB 2025-09-15 15:41 rw-r--r--
regex_executor.h — 8.64 KB
2025-09-15 15:41 · rw-r--r--
8.64 KB 2025-09-15 15:41 rw-r--r--
regex_executor.tcc — 18.4 KB
2025-09-15 15:41 · rw-r--r--
18.4 KB 2025-09-15 15:41 rw-r--r--
regex_scanner.h — 6.88 KB
2025-09-15 15:41 · rw-r--r--
6.88 KB 2025-09-15 15:41 rw-r--r--
regex_scanner.tcc — 14.89 KB
2025-09-15 15:41 · rw-r--r--
14.89 KB 2025-09-15 15:41 rw-r--r--
semaphore_base.h — 7.75 KB
2025-09-15 15:41 · rw-r--r--
7.75 KB 2025-09-15 15:41 rw-r--r--
shared_ptr.h — 30.25 KB
2025-09-15 15:41 · rw-r--r--
30.25 KB 2025-09-15 15:41 rw-r--r--
shared_ptr_atomic.h — 9.64 KB
2025-09-15 15:41 · rw-r--r--
9.64 KB 2025-09-15 15:41 rw-r--r--
shared_ptr_base.h — 53.62 KB
2025-09-15 15:41 · rw-r--r--
53.62 KB 2025-09-15 15:41 rw-r--r--
slice_array.h — 9.39 KB
2025-09-15 15:41 · rw-r--r--
9.39 KB 2025-09-15 15:41 rw-r--r--
specfun.h — 46.13 KB
2025-09-15 15:41 · rw-r--r--
46.13 KB 2025-09-15 15:41 rw-r--r--
sstream.tcc — 9.91 KB
2025-09-15 15:41 · rw-r--r--
9.91 KB 2025-09-15 15:41 rw-r--r--
std_abs.h — 3.28 KB
2025-09-15 15:41 · rw-r--r--
3.28 KB 2025-09-15 15:41 rw-r--r--
std_function.h — 22.33 KB
2025-09-15 15:41 · rw-r--r--
22.33 KB 2025-09-15 15:41 rw-r--r--
std_mutex.h — 6.29 KB
2025-09-15 15:41 · rw-r--r--
6.29 KB 2025-09-15 15:41 rw-r--r--
std_thread.h — 8.39 KB
2025-09-15 15:41 · rw-r--r--
8.39 KB 2025-09-15 15:41 rw-r--r--
stl_algo.h — 209.67 KB
2025-09-15 15:41 · rw-r--r--
209.67 KB 2025-09-15 15:41 rw-r--r--
stl_algobase.h — 74.6 KB
2025-09-15 15:41 · rw-r--r--
74.6 KB 2025-09-15 15:41 rw-r--r--
stl_bvector.h — 34.74 KB
2025-09-15 15:41 · rw-r--r--
34.74 KB 2025-09-15 15:41 rw-r--r--
stl_construct.h — 8.59 KB
2025-09-15 15:41 · rw-r--r--
8.59 KB 2025-09-15 15:41 rw-r--r--
stl_deque.h — 75.17 KB
2025-09-15 15:41 · rw-r--r--
75.17 KB 2025-09-15 15:41 rw-r--r--
stl_function.h — 42.87 KB
2025-09-15 15:41 · rw-r--r--
42.87 KB 2025-09-15 15:41 rw-r--r--
stl_heap.h — 20.27 KB
2025-09-15 15:41 · rw-r--r--
20.27 KB 2025-09-15 15:41 rw-r--r--
stl_iterator.h — 77 KB
2025-09-15 15:41 · rw-r--r--
77 KB 2025-09-15 15:41 rw-r--r--
stl_iterator_base_funcs.h — 7.99 KB
2025-09-15 15:41 · rw-r--r--
7.99 KB 2025-09-15 15:41 rw-r--r--
stl_iterator_base_types.h — 9.44 KB
2025-09-15 15:41 · rw-r--r--
9.44 KB 2025-09-15 15:41 rw-r--r--
stl_list.h — 68.14 KB
2025-09-15 15:41 · rw-r--r--
68.14 KB 2025-09-15 15:41 rw-r--r--
stl_map.h — 53.41 KB
2025-09-15 15:41 · rw-r--r--
53.41 KB 2025-09-15 15:41 rw-r--r--
stl_multimap.h — 42.51 KB
2025-09-15 15:41 · rw-r--r--
42.51 KB 2025-09-15 15:41 rw-r--r--
stl_multiset.h — 36.79 KB
2025-09-15 15:41 · rw-r--r--
36.79 KB 2025-09-15 15:41 rw-r--r--
stl_numeric.h — 14.26 KB
2025-09-15 15:41 · rw-r--r--
14.26 KB 2025-09-15 15:41 rw-r--r--
stl_pair.h — 19.66 KB
2025-09-15 15:41 · rw-r--r--
19.66 KB 2025-09-15 15:41 rw-r--r--
stl_queue.h — 24.45 KB
2025-09-15 15:41 · rw-r--r--
24.45 KB 2025-09-15 15:41 rw-r--r--
stl_raw_storage_iter.h — 3.74 KB
2025-09-15 15:41 · rw-r--r--
3.74 KB 2025-09-15 15:41 rw-r--r--
stl_relops.h — 4.49 KB
2025-09-15 15:41 · rw-r--r--
4.49 KB 2025-09-15 15:41 rw-r--r--
stl_set.h — 37.05 KB
2025-09-15 15:41 · rw-r--r--
37.05 KB 2025-09-15 15:41 rw-r--r--
stl_stack.h — 12.39 KB
2025-09-15 15:41 · rw-r--r--
12.39 KB 2025-09-15 15:41 rw-r--r--
stl_tempbuf.h — 8.45 KB
2025-09-15 15:41 · rw-r--r--
8.45 KB 2025-09-15 15:41 rw-r--r--
stl_tree.h — 72.16 KB
2025-09-15 15:41 · rw-r--r--
72.16 KB 2025-09-15 15:41 rw-r--r--
stl_uninitialized.h — 33.22 KB
2025-09-15 15:41 · rw-r--r--
33.22 KB 2025-09-15 15:41 rw-r--r--
stl_vector.h — 64.37 KB
2025-09-15 15:41 · rw-r--r--
64.37 KB 2025-09-15 15:41 rw-r--r--
stream_iterator.h — 7.52 KB
2025-09-15 15:41 · rw-r--r--
7.52 KB 2025-09-15 15:41 rw-r--r--
streambuf.tcc — 4.81 KB
2025-09-15 15:41 · rw-r--r--
4.81 KB 2025-09-15 15:41 rw-r--r--
streambuf_iterator.h — 15.17 KB
2025-09-15 15:41 · rw-r--r--
15.17 KB 2025-09-15 15:41 rw-r--r--
string_view.tcc — 7 KB
2025-09-15 15:41 · rw-r--r--
7 KB 2025-09-15 15:41 rw-r--r--
stringfwd.h — 2.63 KB
2025-09-15 15:41 · rw-r--r--
2.63 KB 2025-09-15 15:41 rw-r--r--
this_thread_sleep.h — 3.23 KB
2025-09-15 15:41 · rw-r--r--
3.23 KB 2025-09-15 15:41 rw-r--r--
uniform_int_dist.h — 12.75 KB
2025-09-15 15:41 · rw-r--r--
12.75 KB 2025-09-15 15:41 rw-r--r--
unique_lock.h — 6 KB
2025-09-15 15:41 · rw-r--r--
6 KB 2025-09-15 15:41 rw-r--r--
unique_ptr.h — 31.77 KB
2025-09-15 15:41 · rw-r--r--
31.77 KB 2025-09-15 15:41 rw-r--r--
unordered_map.h — 74.87 KB
2025-09-15 15:41 · rw-r--r--
74.87 KB 2025-09-15 15:41 rw-r--r--
unordered_set.h — 61.46 KB
2025-09-15 15:41 · rw-r--r--
61.46 KB 2025-09-15 15:41 rw-r--r--
uses_allocator.h — 6.74 KB
2025-09-15 15:41 · rw-r--r--
6.74 KB 2025-09-15 15:41 rw-r--r--
uses_allocator_args.h — 7.38 KB
2025-09-15 15:41 · rw-r--r--
7.38 KB 2025-09-15 15:41 rw-r--r--
valarray_after.h — 22.74 KB
2025-09-15 15:41 · rw-r--r--
22.74 KB 2025-09-15 15:41 rw-r--r--
valarray_array.h — 20.8 KB
2025-09-15 15:41 · rw-r--r--
20.8 KB 2025-09-15 15:41 rw-r--r--
valarray_array.tcc — 7.08 KB
2025-09-15 15:41 · rw-r--r--
7.08 KB 2025-09-15 15:41 rw-r--r--
valarray_before.h — 18.69 KB
2025-09-15 15:41 · rw-r--r--
18.69 KB 2025-09-15 15:41 rw-r--r--
vector.tcc — 30.26 KB
2025-09-15 15:41 · rw-r--r--
30.26 KB 2025-09-15 15:41 rw-r--r--
ONLINE
bits
146 items
03:45:27
TERMINAL FM
NAVIGATION
ACTIONS
SELECTION
Edit
Preview
Download
Rename
Copy
Chmod
Delete
// class template regex -*- C++ -*- // Copyright (C) 2013-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 // . /** * @file bits/regex_executor.tcc * 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 namespace __detail { template bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_search() { if (_M_search_from_first()) return true; if (_M_flags & regex_constants::match_continuous) return false; _M_flags |= regex_constants::match_prev_avail; while (_M_begin != _M_end) { ++_M_begin; if (_M_search_from_first()) return true; } return false; } // The _M_main function operates in different modes, DFS mode or BFS mode, // indicated by template parameter __dfs_mode, and dispatches to one of the // _M_main_dispatch overloads. // // ------------------------------------------------------------ // // DFS mode: // // It applies a Depth-First-Search (aka backtracking) on given NFA and input // string. // At the very beginning the executor stands in the start state, then it // tries every possible state transition in current state recursively. Some // state transitions consume input string, say, a single-char-matcher or a // back-reference matcher; some don't, like assertion or other anchor nodes. // When the input is exhausted and/or the current state is an accepting // state, the whole executor returns true. // // TODO: This approach is exponentially slow for certain input. // Try to compile the NFA to a DFA. // // Time complexity: \Omega(match_length), O(2^(_M_nfa.size())) // Space complexity: \theta(match_results.size() + match_length) // template bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_main_dispatch(_Match_mode __match_mode, __dfs) { _M_has_sol = false; *_M_states._M_get_sol_pos() = _BiIter(); _M_cur_results = _M_results; _M_dfs(__match_mode, _M_states._M_start); return _M_has_sol; } // ------------------------------------------------------------ // // BFS mode: // // Russ Cox's article (http://swtch.com/~rsc/regexp/regexp1.html) // explained this algorithm clearly. // // It first computes epsilon closure (states that can be achieved without // consuming characters) for every state that's still matching, // using the same DFS algorithm, but doesn't re-enter states (using // _M_states._M_visited to check), nor follow _S_opcode_match. // // Then apply DFS using every _S_opcode_match (in _M_states._M_match_queue) // as the start state. // // It significantly reduces potential duplicate states, so has a better // upper bound; but it requires more overhead. // // Time complexity: \Omega(match_length * match_results.size()) // O(match_length * _M_nfa.size() * match_results.size()) // Space complexity: \Omega(_M_nfa.size() + match_results.size()) // O(_M_nfa.size() * match_results.size()) template bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_main_dispatch(_Match_mode __match_mode, __bfs) { _M_states._M_queue(_M_states._M_start, _M_results); bool __ret = false; while (1) { _M_has_sol = false; if (_M_states._M_match_queue.empty()) break; std::fill_n(_M_states._M_visited_states.get(), _M_nfa.size(), false); auto __old_queue = std::move(_M_states._M_match_queue); for (auto& __task : __old_queue) { _M_cur_results = std::move(__task.second); _M_dfs(__match_mode, __task.first); } if (__match_mode == _Match_mode::_Prefix) __ret |= _M_has_sol; if (_M_current == _M_end) break; ++_M_current; } if (__match_mode == _Match_mode::_Exact) __ret = _M_has_sol; _M_states._M_match_queue.clear(); return __ret; } // Return whether now match the given sub-NFA. template bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_lookahead(_StateIdT __next) { // Backreferences may refer to captured content. // We may want to make this faster by not copying, // but let's not be clever prematurely. _ResultsVec __what(_M_cur_results); _Executor __sub(_M_current, _M_end, __what, _M_re, _M_flags); __sub._M_states._M_start = __next; if (__sub._M_search_from_first()) { for (size_t __i = 0; __i < __what.size(); __i++) if (__what[__i].matched) _M_cur_results[__i] = __what[__i]; return true; } return false; } // __rep_count records how many times (__rep_count.second) // this node is visited under certain input iterator // (__rep_count.first). This prevent the executor from entering // infinite loop by refusing to continue when it's already been // visited more than twice. It's `twice` instead of `once` because // we need to spare one more time for potential group capture. template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_rep_once_more(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; auto& __rep_count = _M_rep_count[__i]; if (__rep_count.second == 0 || __rep_count.first != _M_current) { auto __back = __rep_count; __rep_count.first = _M_current; __rep_count.second = 1; _M_dfs(__match_mode, __state._M_alt); __rep_count = __back; } else { if (__rep_count.second < 2) { __rep_count.second++; _M_dfs(__match_mode, __state._M_alt); __rep_count.second--; } } } // _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 // mean the same thing, and we need to choose the correct order under // given greedy mode. template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_repeat(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; // Greedy. if (!__state._M_neg) { _M_rep_once_more(__match_mode, __i); // If it's DFS executor and already accepted, we're done. if (!__dfs_mode || !_M_has_sol) _M_dfs(__match_mode, __state._M_next); } else // Non-greedy mode { if (__dfs_mode) { // vice-versa. _M_dfs(__match_mode, __state._M_next); if (!_M_has_sol) _M_rep_once_more(__match_mode, __i); } else { // DON'T attempt anything, because there's already another // state with higher priority accepted. This state cannot // be better by attempting its next node. if (!_M_has_sol) { _M_dfs(__match_mode, __state._M_next); // DON'T attempt anything if it's already accepted. An // accepted state *must* be better than a solution that // matches a non-greedy quantifier one more time. if (!_M_has_sol) _M_rep_once_more(__match_mode, __i); } } } } template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_subexpr_begin(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; auto& __res = _M_cur_results[__state._M_subexpr]; auto __back = __res.first; __res.first = _M_current; _M_dfs(__match_mode, __state._M_next); __res.first = __back; } template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_subexpr_end(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; auto& __res = _M_cur_results[__state._M_subexpr]; auto __back = __res; __res.second = _M_current; __res.matched = true; _M_dfs(__match_mode, __state._M_next); __res = __back; } template inline void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_line_begin_assertion(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; if (_M_at_begin()) _M_dfs(__match_mode, __state._M_next); } template inline void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_line_end_assertion(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; if (_M_at_end()) _M_dfs(__match_mode, __state._M_next); } template inline void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_word_boundary(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; if (_M_word_boundary() == !__state._M_neg) _M_dfs(__match_mode, __state._M_next); } // Here __state._M_alt offers a single start node for a sub-NFA. // We recursively invoke our algorithm to match the sub-NFA. template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_subexpr_lookahead(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; if (_M_lookahead(__state._M_alt) == !__state._M_neg) _M_dfs(__match_mode, __state._M_next); } template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_match(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; if (_M_current == _M_end) return; if (__dfs_mode) { if (__state._M_matches(*_M_current)) { ++_M_current; _M_dfs(__match_mode, __state._M_next); --_M_current; } } else if (__state._M_matches(*_M_current)) _M_states._M_queue(__state._M_next, _M_cur_results); } template struct _Backref_matcher { _Backref_matcher(bool __icase, const _TraitsT& __traits) : _M_traits(__traits) { } bool _M_apply(_BiIter __expected_begin, _BiIter __expected_end, _BiIter __actual_begin, _BiIter __actual_end) { return _M_traits.transform(__expected_begin, __expected_end) == _M_traits.transform(__actual_begin, __actual_end); } const _TraitsT& _M_traits; }; template struct _Backref_matcher<_BiIter, std::regex_traits<_CharT>> { using _TraitsT = std::regex_traits<_CharT>; _Backref_matcher(bool __icase, const _TraitsT& __traits) : _M_icase(__icase), _M_traits(__traits) { } bool _M_apply(_BiIter __expected_begin, _BiIter __expected_end, _BiIter __actual_begin, _BiIter __actual_end) { if (!_M_icase) return _GLIBCXX_STD_A::__equal4(__expected_begin, __expected_end, __actual_begin, __actual_end); typedef std::ctype<_CharT> __ctype_type; const auto& __fctyp = use_facet<__ctype_type>(_M_traits.getloc()); return _GLIBCXX_STD_A::__equal4(__expected_begin, __expected_end, __actual_begin, __actual_end, [this, &__fctyp](_CharT __lhs, _CharT __rhs) { return __fctyp.tolower(__lhs) == __fctyp.tolower(__rhs); }); } bool _M_icase; const _TraitsT& _M_traits; }; // First fetch the matched result from _M_cur_results as __submatch; // then compare it with // (_M_current, _M_current + (__submatch.second - __submatch.first)). // If matched, keep going; else just return and try another state. template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_backref(_Match_mode __match_mode, _StateIdT __i) { __glibcxx_assert(__dfs_mode); const auto& __state = _M_nfa[__i]; auto& __submatch = _M_cur_results[__state._M_backref_index]; if (!__submatch.matched) return; auto __last = _M_current; for (auto __tmp = __submatch.first; __last != _M_end && __tmp != __submatch.second; ++__tmp) ++__last; if (_Backref_matcher<_BiIter, _TraitsT>( _M_re.flags() & regex_constants::icase, _M_re._M_automaton->_M_traits)._M_apply( __submatch.first, __submatch.second, _M_current, __last)) { if (__last != _M_current) { auto __backup = _M_current; _M_current = __last; _M_dfs(__match_mode, __state._M_next); _M_current = __backup; } else _M_dfs(__match_mode, __state._M_next); } } template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_accept(_Match_mode __match_mode, _StateIdT) { if (__dfs_mode) { __glibcxx_assert(!_M_has_sol); if (__match_mode == _Match_mode::_Exact) _M_has_sol = _M_current == _M_end; else _M_has_sol = true; if (_M_current == _M_begin && (_M_flags & regex_constants::match_not_null)) _M_has_sol = false; if (_M_has_sol) { if (_M_nfa._M_flags & regex_constants::ECMAScript) _M_results = _M_cur_results; else // POSIX { __glibcxx_assert(_M_states._M_get_sol_pos()); // Here's POSIX's logic: match the longest one. However // we never know which one (lhs or rhs of "|") is longer // unless we try both of them and compare the results. // The member variable _M_sol_pos records the end // position of the last successful match. It's better // to be larger, because POSIX regex is always greedy. // TODO: This could be slow. if (*_M_states._M_get_sol_pos() == _BiIter() || std::distance(_M_begin, *_M_states._M_get_sol_pos()) < std::distance(_M_begin, _M_current)) { *_M_states._M_get_sol_pos() = _M_current; _M_results = _M_cur_results; } } } } else { if (_M_current == _M_begin && (_M_flags & regex_constants::match_not_null)) return; if (__match_mode == _Match_mode::_Prefix || _M_current == _M_end) if (!_M_has_sol) { _M_has_sol = true; _M_results = _M_cur_results; } } } template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_handle_alternative(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; if (_M_nfa._M_flags & regex_constants::ECMAScript) { // TODO: Fix BFS support. It is wrong. _M_dfs(__match_mode, __state._M_alt); // Pick lhs if it matches. Only try rhs if it doesn't. if (!_M_has_sol) _M_dfs(__match_mode, __state._M_next); } else { // Try both and compare the result. // See "case _S_opcode_accept:" handling above. _M_dfs(__match_mode, __state._M_alt); auto __has_sol = _M_has_sol; _M_has_sol = false; _M_dfs(__match_mode, __state._M_next); _M_has_sol |= __has_sol; } } template void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_dfs(_Match_mode __match_mode, _StateIdT __i) { if (_M_states._M_visited(__i)) return; switch (_M_nfa[__i]._M_opcode()) { case _S_opcode_repeat: _M_handle_repeat(__match_mode, __i); break; case _S_opcode_subexpr_begin: _M_handle_subexpr_begin(__match_mode, __i); break; case _S_opcode_subexpr_end: _M_handle_subexpr_end(__match_mode, __i); break; case _S_opcode_line_begin_assertion: _M_handle_line_begin_assertion(__match_mode, __i); break; case _S_opcode_line_end_assertion: _M_handle_line_end_assertion(__match_mode, __i); break; case _S_opcode_word_boundary: _M_handle_word_boundary(__match_mode, __i); break; case _S_opcode_subexpr_lookahead: _M_handle_subexpr_lookahead(__match_mode, __i); break; case _S_opcode_match: _M_handle_match(__match_mode, __i); break; case _S_opcode_backref: _M_handle_backref(__match_mode, __i); break; case _S_opcode_accept: _M_handle_accept(__match_mode, __i); break; case _S_opcode_alternative: _M_handle_alternative(__match_mode, __i); break; default: __glibcxx_assert(false); } } // Return whether now is at some word boundary. template bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: _M_word_boundary() const { if (_M_current == _M_begin && (_M_flags & regex_constants::match_not_bow)) return false; if (_M_current == _M_end && (_M_flags & regex_constants::match_not_eow)) return false; bool __left_is_word = false; if (_M_current != _M_begin || (_M_flags & regex_constants::match_prev_avail)) { auto __prev = _M_current; if (_M_is_word(*std::prev(__prev))) __left_is_word = true; } bool __right_is_word = _M_current != _M_end && _M_is_word(*_M_current); return __left_is_word != __right_is_word; } } // namespace __detail _GLIBCXX_END_NAMESPACE_VERSION } // namespace