- Generated by
1.9.8
|
REAL
Regular Expression Algorithmic Library — constexpr C++20 regex
|
Forward iterator over the non-overlapping matches in a text. More...
#include <real.hpp>
Public Types | |
| using | value_type = basic_match_result< typename Storage::slot_storage > |
| Yielded match type. | |
| using | difference_type = std::ptrdiff_t |
| Iterator traits. | |
| using | reference = const value_type & |
| Dereference type. | |
| using | pointer = const value_type * |
| Arrow type. | |
| using | iterator_category = std::forward_iterator_tag |
| Multipass: copies are independent. | |
Public Member Functions | |
| constexpr | basic_match_iterator ()=default |
| Constructs the end sentinel. | |
| constexpr | basic_match_iterator (detail::program_view prog, std::string_view pattern, std::string_view text, std::size_t start=0, match_semantics sem=match_semantics::first) |
| Constructs a begin iterator and finds the first match. | |
| constexpr void | decide_batching (detail::program_view prog, match_semantics sem, std::size_t text_bytes) |
| Once per walk: which batched filler, if any, serves this scan. | |
| constexpr const value_type & | operator* () const |
| Returns the current match. | |
| constexpr const value_type * | operator-> () const |
| Returns pointer to the current match. | |
| constexpr basic_match_iterator & | operator++ () |
| Advances to the next match. | |
| constexpr basic_match_iterator | operator++ (int) |
| Advances to the next match (post-increment). | |
| constexpr bool | exhausted () const noexcept |
| Whether the walk is over, without building an end sentinel to compare against. | |
| constexpr bool | operator== (const basic_match_iterator &other) const |
Returns true if both denote the same position/end. | |
Private Member Functions | |
| constexpr bool | refill_batch () |
| Cold half of the batched walk: refills batch_ from the engine. | |
| constexpr void | advance () |
| Finds the next match, applying the empty-match advance rules. | |
Private Attributes | |
| detail::program_view | prog_ |
| The program being run. | |
| std::string_view | pattern_ |
| Pattern text (named lookups). | |
| std::string_view | text_ |
| The text being scanned. | |
| std::size_t | pos_ {} |
| Current scan offset. | |
| std::size_t | forbid_empty_until_ {} |
| Empty-match guard (see pike.hpp). | |
| bool | done_ {true} |
| True once exhausted. | |
| bool | cascade_ {} |
| Chosen once — run the memchr-cascade class-run variant for this whole walk. | |
| match_semantics | sem_ {match_semantics::first} |
| leftmost-first (default) or longest (find_iter_longest). | |
| value_type | current_ |
| The current match. | |
| Storage::state_type | state_ |
| VM scratch, reused across the walk. | |
| detail::pike_vm< typenameStorage::state_type, true >::cp_span | batch_ [batch_cap] {} |
| The buffered spans; indices batch_i_ .. batch_n_ are the unread ones. | |
| std::size_t | batch_n_ {} |
| Spans currently buffered. | |
| std::size_t | batch_i_ {} |
| Next span to hand out. | |
| bool | batch_eligible_ {} |
| Route/shape allows batching (decided once). | |
| bool | trailing_la_walk_ {} |
| This walk takes the trailing-lookaround route, chosen once here rather than by specialization — which is what lets basic_regex::find_iter reach it at all. | |
| bool | batch_bytes_ {} |
| bool | batch_cp_ascii_ {} |
Batch the ./negated-class route (real::detail::pike_vm::fill_codepoint_class_spans). | |
| bool | batch_single_cl_ {} |
| Batch the bare single byte-class route (real::detail::pike_vm::fill_single_class_spans). | |
| bool | wb_edge_ {} |
The walk's pattern carries a DROPPED leading \b (real::detail::pattern_hints::wb_lead_maximal_run), so its filler needs the one-position window-edge guard. Decided once, and passed as a template argument rather than tested in the scan loop. | |
| bool | batch_alt_ {} |
| Batch the fixed-alternation route (real::detail::pike_vm::fill_alternation_spans). Its per-match return was 99 % of the row at density – see that filler's own note. | |
| bool | batch_lazy_dfa_ {} |
Batch the lazy-DFA route (pike.hpp's fill_lazy_dfa_spans) — the fifth, and the one shape recognition never reaches. | |
| bool | batch_exact_lit_ {} |
Batch the exact-literal route (pike.hpp's fill_exact_literal_spans) — the sixth, and a refusal reopened on a contrary measurement rather than on a new idea; see there. | |
| bool | batch_inner_lit_ {} |
Batch the inner-literal route (pike.hpp's fill_inner_literal_spans) — the seventh, and the second to need batch_partial_ (its guards abandon). | |
| bool | batch_partial_ {} |
| That filler stopped WITHOUT proving the subject spent, so an empty buffer means "resume on
the per-match path", not "the walk is over". Never set by the other four fillers, whose scans cover the whole subject and for which an empty buffer IS exhaustion. | |
| bool | wb_kept_ {} |
The walk's pattern KEEPS a \b/\B wrap, so the byte-class filler evaluates it on every span. Only that filler handles it; the other batched routes decline such patterns. | |
Static Private Attributes | |
| static constexpr std::size_t | batch_cap {4} |
| Buffered spans for the code-point-class route — see batch_eligible_. | |
Forward iterator over the non-overlapping matches in a text.
Follows Python's empty-match rules: an empty match is yielded (even right after a non-empty one), then the scan advances by one codepoint. The regex and the text must outlive the iterator. Obtained from basic_match_range.
| Storage | The regex's storage policy (selects the result/scratch types). |
|
inlineconstexpr |
Constructs a begin iterator and finds the first match.
| [in] | prog | The compiled program to run. |
| [in] | pattern | The pattern text (for named-group resolution). |
| [in] | text | The text to iterate over (borrowed). |
| [in] | start | Byte offset to begin iterating from (0 = the whole text). |
| [in] | sem | Match semantics: leftmost-first (default) or the experimental leftmost-longest. |
|
inlineconstexprprivate |
Finds the next match, applying the empty-match advance rules.
TrailingLA is fixed for the whole walk (constructor / range). Pure walks (TrailingLA = false) contain no trailing-lookahead symbols at all — what the class-loop codegen needs (see pattern_hints::trailing_lookaround).
always_inline.It is a regression. One ISA reads it as a win with its gauges inside the layout floor; the other regresses the TARGET itself, and regresses unrelated class rows further still. Inlining this into its callers bloats the translation unit past --param inline-unit-growth, and the compiler then starts declining inlines that mattered more – the cliff documented in docs/design.dox 10.1, reproduced here in one experiment.
So the per-match frame is real and stays. Removing it needs the frame to shrink, not the call to disappear.
|
inlineconstexpr |
Once per walk: which batched filler, if any, serves this scan.
| [in] | prog | The compiled program, for its hints. |
| [in] | sem | The walk's match semantics. |
| [in] | text_bytes | Subject length; the lazy-DFA filler needs a minimum runway. |
|
inlineconstexprnoexcept |
Whether the walk is over, without building an end sentinel to compare against.
Prefer this in a hand-rolled loop: it == basic_match_iterator{} answers the same question, but a default-constructed iterator is a full walker and is expensive to materialise just to test.
true once no further match will be produced.
|
inlineconstexpr |
Returns the current match.
|
inlineconstexpr |
Advances to the next match.
|
inlineconstexpr |
Advances to the next match (post-increment).
|
inlineconstexpr |
Returns pointer to the current match.
|
inlineconstexpr |
Returns true if both denote the same position/end.
| [in] | other | Another iterator. |
true if both denote the same position/end.
|
inlineconstexprprivate |
Cold half of the batched walk: refills batch_ from the engine.
Outlined, and the attribute is load-bearing for the same reason advance is NOT force-inlined: this iterator's translation unit sits on gcc's per-unit inline budget (docs/design.dox §10.1). Inline, this refill grows advance enough to charge rows that never touch the batch at all. Outlined, advance's hot path is a compare, an index and a span copy, and it runs once per batch_cap matches instead of once per match.
Each branch bills its route to real::detail::prof::tick_route, which the unbatched routes in real::detail::pike_vm::run also do — the SAME identifier on purpose, so entries / matches stays one number across both. The reading changes meaning, though: a batched route bills once per REFILL, so an effective batch reads 1 / batch_cap (0.25 at four) where an unbatched route reads 1.000. That ratio is therefore the batch's efficiency, and 1.000 on a route that should batch is the signal that it stopped. Billing nothing here — which is what this walk did until now — makes a batched route indistinguishable from one never entered, and it hid every route this file batches from the one instrument that is indifferent to machine load.
count_matches, which is what every throughput measurement runs. Adding ONE branch – calling an existing filler, flag computed in the cold outlined decide_batching, no struct reflow – leaves advance and all six fillers byte-identical and moves only this function (+10 instructions) and count_matches (−2), and that was enough to put 17 of 18 rows' medians positive (+0.2 % to +9.7 %, 21 of 24 draws on most) where the same base without the branch read 13 of 18 negative. No row is REAL by real's decision rule, and the sign across rows is not noise either. Three routes still bill one entry per MATCH – exact_literal, inner_literal and fixed_shape (which serves date, the weakest published row) – and batching any of them through here taxes the other seventeen by about what it might win on one. §3.2 also records why the obvious doors around it are not free. true if at least one span was buffered.
|
private |
Batch the BYTE-class route rather than the code-point one.
|
staticconstexprprivate |
Buffered spans for the code-point-class route — see batch_eligible_.
Tuned, not picked. A wider buffer captures the same Unicode gain but charges the rows that never touch the batch at all, and outlining the refill does not recover that – which is what rules out advance's own size as the cause and points at the ITERATOR's, this array being part of every walk's state whether or not the walk batches.
|
private |
Batch the ./negated-class route (real::detail::pike_vm::fill_codepoint_class_spans).
It was the one class scan with no filler, so it paid a full route entry per match where the other two pay one per batch_cap – several times the per-match cost of its own batched neighbours.
|
private |
Batch the bare single byte-class route (real::detail::pike_vm::fill_single_class_spans).
An unquantified [a-z] crossed one full route entry per accepted BYTE — slower per byte than ., which matches at every position — because real::detail::pattern_hints::greedy_class_loop describes class+ only and carries no "single" flag to batch on.
|
private |
This walk takes the trailing-lookaround route, chosen once here rather than by specialization — which is what lets basic_regex::find_iter reach it at all.
The route exists for [a-z]+(?=[a-z]) and its family, and three of the four entry points took it: count_matches and find_all branch internally onto basic_match_range<Storage, TrailingLA = true>. find_iter could NOT — its return type names the specialization, so a runtime hint cannot pick one — and it fell to the general Pike VM instead. The gap that opened was an order of magnitude, for the same pattern and the same match count, where every pattern WITHOUT a trailing lookaround has the two surfaces within noise of each other – so result construction costs nothing and the whole gap was the missed route. With this flag the two surfaces meet again.
It also says why the defect survived: the benchmark measured count_matches for every row, so the published figure described the fast path while the iterator API ran an order of magnitude slower and no table showed it. That instrument now carries a find_iter row for exactly this reason.
WHAT IT COSTS, AND TWO ATTEMPTS TO REMOVE THAT COST THAT FAILED. The test this flag adds sits in advance's general path, so the routes that are NOT batched pay it once per match. The trade is lopsided but not free: the target row gains almost all of its time back, while the row most exposed to a per-match test loses measurably – exact_literal, unbatched, whose matches are short and frequent, so a per-match constant lands on it hardest.
Two ways out were tried and both made it WORSE, established by disassembly before any campaign: folding this flag and batch_eligible_ into one dense enum field – they are mutually exclusive, so one field should mean one load – grew count_matches from 372 to 381 instructions, because a compare-to-constant costs more than a test-nonzero; and moving the fold's assignment into the cold decide_batching recovered only the constructor, leaving the same +9. So the trade STANDS and is recorded rather than quietly carried: 14x on an API path a caller cannot avoid, against 17 % on a row that leads PCRE2-JIT by 1.29x / 1.94x and can afford it. Anyone reopening this needs a way to select the walk WITHOUT a per-match test, not a cheaper flag.
1.9.8