Regex timeout applies per word per item, so one catastrophic-backtracking pattern still freezes Filter() for N seconds (10 items: 10 s)

[matt-edmondson]

What's wrong

Commit b249339 bounded regex evaluation with a 1-second RegexMatchTimeout (TextFilter/TextFilter.cs:121-124). The comment says this is "short enough that a pathological one cannot wedge a UI", and the DoesMatchRegex remarks say "a caller-supplied pattern cannot hang the calling thread".

The timeout limits each Regex.IsMatch call, and nothing remembers that a pattern timed out. DoesMatchRegex catches the RegexMatchTimeoutException and returns false for that one token (TextFilter.cs:494-506). The next word, and the next item in Filter, run the same pathological pattern again and wait the full second each time. Worst-case time is therefore:

items × distinct words per item × 1 s

The cache (AddBounded(RegexCache, ...), line 477) stores the compiled Regex, so the pattern stays expensive on every keystroke and every item for the lifetime of the process.

Reproduction

using System.Diagnostics;
using ktsu.TextFilter;

string bad = new string('a', 40) + "X";
var items = Enumerable.Range(0, 10).Select(i => bad + i).ToList();
var sw = Stopwatch.StartNew();
var res = TextFilter.Filter(items, "(a+)+$", TextFilterType.Regex, TextFilterMatchOptions.ByWholeString).ToList();
Console.WriteLine($"Filter 10 items: {res.Count} results in {sw.ElapsedMilliseconds} ms");

sw.Restart();
bool r = TextFilter.IsMatch(string.Join(' ', Enumerable.Range(0, 5).Select(i => new string('a', 40) + "X" + i)),
    "(a+)+$", TextFilterType.Regex, TextFilterMatchOptions.ByWordAny);
Console.WriteLine($"IsMatch, one text of 5 words: {r} in {sw.ElapsedMilliseconds} ms");

Observed (net10.0, main 1a5f996):

Filter 10 items: 0 results in 10005 ms
IsMatch, one text of 5 words: False in 5028 ms

Expected: once the pattern has timed out, the rest of the evaluation should not pay the timeout again. The whole Filter call should take about 1 s, not 1 s per item and per word.

In a keystroke-driven filter box over 1,000 entries (the use case the cache comments describe), a pattern like (a+)+$ or (\w+\s?)+$ blocks the UI thread for about 17 minutes, which is the hang the timeout was meant to prevent. The existing test ACatastrophicallyBacktrackingPatternTimesOutInsteadOfHanging checks only a single IsMatch on a single token, so it does not catch this.

Suggested fix / acceptance criteria

• When a pattern times out, record that under its cache key (for example, replace the cached Regex with a "timed out" sentinel or track it in a bounded set). Later tokens and calls should then return the degraded answer (false) immediately instead of running the regex again.
• Optionally, treat the timeout as a budget for the whole DoesMatchRegex call rather than for each token.
• Add tests:
  • Filter over at least 10 pathological items with (a+)+$ completes in well under 10 × the timeout (for example < 3 s).
  • IsMatch with ByWordAny/ByWordAll on text with several distinct pathological words completes in about one timeout.
  • Ordinary patterns are unaffected, and a pattern that timed out under one case sensitivity does not poison the other (the keys already differ by the i:/s: prefix).

[matt-edmondson]

Triage

• Category: Bug
• Priority: High. The 1 s regex timeout added in b249339 was meant to stop a pathological pattern from hanging the UI, but it is paid again for every word of every item. A user typing (a+)+$ into a filter box over 1,000 entries blocks the thread for about 17 minutes. The hang the fix was supposed to prevent is still reachable from user input.
• Area / suggested assignee: TextFilter.DoesMatchRegex and the regex cache (RegexCache). Owner: @matt-edmondson
• Duplicates / in progress: not a duplicate. Open PRs Split filters and text on all whitespace, not only ' ' #116 (whitespace splitting) and Match any optional glob token under ByWholeString #117 (glob tokens) touch the same file but not the regex path. Expect minor merge overlap only.
• Next step: cache a "timed out" sentinel per pattern key so later tokens and items short-circuit to false, optionally make the timeout a per-call budget, and add the multi-item and multi-word timing tests.

---

Generated by Claude Code