listcategory: Fix O(n^2) performance if no match

With the change in #7955, if the regex did not match, it ended up retrying the
lookahead at every position of the string (expected), but then *also* repeated
that process for every position in the string. Thus, a non-matching pattern
ended up in O(n^2) performance (with n = length of URL).

Instead, anchor the pattern at the beginning of the string. This doesn't change
behaviour as we use .* at the beginning of every lookahead anyways, but it means
we end up with O(n) instead of O(n^2) performance.

Co-authored-by: toofar <toofar@spalge.com>

1 files changed, 1 insertions, 1 deletions

diff --git a/qutebrowser/completion/models/listcategory.py b/qutebrowser/completion/models/listcategory.py
index e46f18c69..226f5e999 100644
--- a/qutebrowser/completion/models/listcategory.py
+++ b/qutebrowser/completion/models/listcategory.py
@@ -52,7 +52,7 @@ class ListCategory(QSortFilterProxyModel):
         # Positive lookahead per search term. This means that all search terms must
         # be matched but they can be matched anywhere in the string, so they can be
         # in any order. For example "foo bar" -> "(?=.*foo)(?=.*bar)"
-        val = '(?=.*' + ')(?=.*'.join(map(re.escape, val.split())) + ')'
+        val = '^(?=.*' + ')(?=.*'.join(map(re.escape, val.split())) + ')'
         rx = QRegularExpression(val, QRegularExpression.PatternOption.CaseInsensitiveOption)
         qtutils.ensure_valid(rx)
         self.setFilterRegularExpression(rx)