Fuzzy matcher is eliminating valid items #5526
Comments
|
Here's a quick MRE I came up with. Try typing "text_elements" into the search and notice commands being discarded: from functools import partial
from textual.app import App
from textual.command import Hit, Hits, Provider
PATHS = [
"content/controls/text_elements/SetpointText.qml",
"content/controls/text_elements/SimplePropertyLabel.qml",
"content/controls/text_elements/PropertyLabelRetestButton.qml",
"content/controls/text_elements/RollableLabel.qml",
"content/controls/text_elements/PropertyTextInput.qml",
"content/controls/text_elements/PropertyLabel.qml",
]
class ExampleCommands(Provider):
async def search(self, query: str) -> Hits:
matcher = self.matcher(query)
app = self.app
for path in PATHS:
score = matcher.match(path)
if score > 0:
yield Hit(
score,
matcher.highlight(path),
partial(app.notify, path),
)
class ExampleApp(App):
COMMANDS = {ExampleCommands}
def on_mount(self) -> None:
self.action_command_palette()
if __name__ == "__main__":
app = ExampleApp()
app.run() |
|
I found that increasing the limit on the number of loops in the diff --git a/src/textual/fuzzy.py b/src/textual/fuzzy.py
index 9a7a55014..4a78a9fd5 100644
--- a/src/textual/fuzzy.py
+++ b/src/textual/fuzzy.py
@@ -140,7 +140,7 @@ class FuzzySearch:
find = candidate.find
# Limit the number of loops out of an abundance of caution.
# This would be hard to reach without contrived data.
- remaining_loops = 200
+ remaining_loops = 300
while stack and (remaining_loops := remaining_loops - 1):
search = pop()I'm not sure if this reveals a possible issue with the search algorithm, as I'm bit surprised it needs this many iterations? I wrote a quick test script using the Codefrom rich import box
from rich import print as rich_print
from rich.table import Table
from textual.fuzzy import FuzzySearch
PATHS = [
"content/controls/text_elements/PropertyLabelRetestButton.qml",
"content/controls/text_elements/RollableLabel.qml",
"content/controls/text_elements/SimplePropertyLabel.qml",
"content/controls/text_elements/PropertyTextInput.qml",
"content/controls/text_elements/SetpointText.qml",
"content/controls/text_elements/PropertyLabel.qml",
]
FULL_QUERY = "text_elements"
fuzzy = FuzzySearch()
queries = [FULL_QUERY[:i] for i in range(8, len(FULL_QUERY) + 1)]
for query in queries:
score_table = Table("Candidate", "Score", box=box.MARKDOWN)
for candidate in PATHS:
score = fuzzy.match(query, candidate)[0]
score_table.add_row(candidate, f"{score:.2f}")
rich_print(f"### FuzzySearch scores with query '{query}'")
rich_print(score_table)BeforeFuzzySearch scores with query 'text_ele'
FuzzySearch scores with query 'text_elem'
FuzzySearch scores with query 'text_eleme'
FuzzySearch scores with query 'text_elemen'
FuzzySearch scores with query 'text_element'
FuzzySearch scores with query 'text_elements'
AfterFuzzySearch scores with query 'text_ele'
FuzzySearch scores with query 'text_elem'
FuzzySearch scores with query 'text_eleme'
FuzzySearch scores with query 'text_elemen'
FuzzySearch scores with query 'text_element'
FuzzySearch scores with query 'text_elements'
|
|
Very interesting. I can try increasing those iterations as a stopgap but I also suspect there is something wrong with the algorithm itself. Thanks for the awesome diagnosis work @TomJGooding ! |
|
You tested my exact scenario, but I can also confirm that setting loops to 300 works with my actual script. However, even with the increased iterations I can break this scenario by increasing the length of the query. If I enter 2 more characters, /text_elements/, 300 loops no longer works but 400 does. 400 breaks at rols/text_elements/. Typing in the whole path content/controls/text_elements fails all of them with Matcher but not via fzf. |
|
Here's another silly example but helps demonstrate how the current algorithm works to greedily match the query:
This example would actually need 1,334 loops until the recursive search will try the exact match for "peter piper". The number of loops quickly increases depending on the length of the query. For example, matching the full string above would need 2,051 loops. I'm still trying to understand exactly how this fuzzy search works, but am I right in thinking that the recursion starts based on the first character of the query? Would it help to traverse backwards from the last character of the query instead? |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Have you checked closed issues? Yes
Have you checked against the most recent version of Textual? Yes
The bug
The matcher seems to be favoring random characters from the right side. I'm trying to use it to search through paths and it acts very oddly. I've had to fall back to using fzf to do the searching right now because it is incorrectly eliminating results (but fzf doesn't do highlighting so Matcher is doing the highlighting). See below:
You will see that
SimplePropertyLabel,PropertyLabelRetestButton, andRollableLabelaren't highlighted because Matcher incorrectly eliminated those but fzf did not. OnPropertyTextInputyou see it is picking up text from the right side and as soon as I add 't' to my query it also is incorrectly eliminated.Textual Diagnostics
Versions
Python
Operating System
Terminal
Rich Console options
The text was updated successfully, but these errors were encountered: