diff options
| author | Florian Bruhin <me@the-compiler.org> | 2024-01-12 18:34:26 +0100 |
|---|---|---|
| committer | Florian Bruhin <me@the-compiler.org> | 2024-01-12 18:53:22 +0100 |
| commit | ee9aecda46ea610644452d2280cefe3ffd64dcbf (patch) | |
| tree | a271b2991c05fb49e1421fe20293dc7b868b75db | |
| parent | 13f6cfa715a018cb314603a67bf0b920f7671a2e (diff) | |
| download | qutebrowser-ee9aecda46ea610644452d2280cefe3ffd64dcbf.tar.gz qutebrowser-ee9aecda46ea610644452d2280cefe3ffd64dcbf.zip | |
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>
| -rw-r--r-- | qutebrowser/completion/models/listcategory.py | 2 | ||||
| -rw-r--r-- | tests/unit/completion/test_models.py | 5 |
2 files changed, 4 insertions, 3 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) diff --git a/tests/unit/completion/test_models.py b/tests/unit/completion/test_models.py index 837298550..e0bce8f04 100644 --- a/tests/unit/completion/test_models.py +++ b/tests/unit/completion/test_models.py @@ -1310,11 +1310,11 @@ def test_url_completion_benchmark(benchmark, info, web_history.completion.insert_batch(entries) quickmark_manager_stub.marks = collections.OrderedDict([ - ('title{}'.format(i), 'example.com/{}'.format(i)) + ('title{}'.format('a'*i), 'example.com/{}'.format(i)) for i in range(1000)]) bookmark_manager_stub.marks = collections.OrderedDict([ - ('example.com/{}'.format(i), 'title{}'.format(i)) + ('example.com/{}'.format('a'*i), 'title{}'.format(i)) for i in range(1000)]) def bench(): @@ -1326,6 +1326,7 @@ def test_url_completion_benchmark(benchmark, info, model.set_pattern('ex 1') model.set_pattern('ex 12') model.set_pattern('ex 123') + model.set_pattern('zzzzz') # no match benchmark(bench) |