diff mbox series

[4/4] lib/ts_fsm: document that a match must consume the remaining data

Message ID 20260816170541.3384-5-bernard.ladenthin@gmail.com
State Under Review
Headers show
Series lib/textsearch: fix ts_bm resume offset, add tests, two small cleanups | expand

Commit Message

Bernard Ladenthin Aug. 16, 2026, 5:05 p.m. UTC 
fsm_find() reports a match only once the token chain has matched and the
data is exhausted:

	for (tok_idx = 0; tok_idx < fsm->ntokens; tok_idx++) { ... }

	if (end_of_data())
		goto found_match;
no_match:
	return UINT_MAX;

A chain of three specific tokens therefore matches the text "abc" but not
"abcd". [TS_FSM_HEAD_IGNORE, a, b] does not find "ab" in "xxabyy".
Searching for a pattern in the middle of the data needs TS_FSM_HEAD_IGNORE
at the front and a TS_FSM_ANY token at the end. The latter short-circuits
through "if (next == NULL) goto found_match".

The file header explains the head anchoring but says nothing about the
tail, which makes the interface easy to misuse. Describe it.

This documents the behaviour as it stands. If the end-of-data requirement
is not intended, the fix belongs in fsm_find() and this patch should be
dropped in favour of that.

Signed-off-by: Bernard Ladenthin <bernard.ladenthin@gmail.com>
---
This is my first kernel submission. Corrections on anything I got wrong in
the process are welcome.

 lib/ts_fsm.c | 7 +++++++
 1 file changed, 7 insertions(+)
diff mbox series

Patch

diff --git a/lib/ts_fsm.c b/lib/ts_fsm.c
index 053615f4fcd7..ceec6295505c 100644
--- a/lib/ts_fsm.c
+++ b/lib/ts_fsm.c
@@ -18,6 +18,13 @@ 
  *   is enabled by default and can be disabled by inserting
  *   TS_FSM_HEAD_IGNORE as the first token in the chain.
  *
+ *   A match is only reported once the data has been consumed as well: the
+ *   token chain has to account for every remaining octet, not just for the
+ *   pattern itself. A chain of three specific tokens therefore matches the
+ *   text "abc" but not "abcd". To look for a pattern somewhere in the
+ *   middle of the data, prepend a token with TS_FSM_HEAD_IGNORE and append
+ *   one with TS_FSM_ANY, the latter matching whatever follows.
+ *
  *   The runtime performance of the algorithm should be around O(n),
  *   however while in strict mode the average runtime can be better.
  */