Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1from __future__ import annotations
3import re
4from collections.abc import Callable, Iterable, Sequence
5from typing import NamedTuple
7from prompt_toolkit.document import Document
8from prompt_toolkit.filters import FilterOrBool, to_filter
9from prompt_toolkit.formatted_text import AnyFormattedText, StyleAndTextTuples
11from .base import CompleteEvent, Completer, Completion
12from .word_completer import WordCompleter
14__all__ = [
15 "FuzzyCompleter",
16 "FuzzyWordCompleter",
17]
20class FuzzyCompleter(Completer):
21 """
22 Fuzzy completion.
23 This wraps any other completer and turns it into a fuzzy completer.
25 If the list of words is: ["leopard" , "gorilla", "dinosaur", "cat", "bee"]
26 Then trying to complete "oar" would yield "leopard" and "dinosaur", but not
27 the others, because they match the regular expression 'o.*a.*r'.
28 Similar, in another application "djm" could expand to "django_migrations".
30 The results are sorted by relevance, which is defined as the start position
31 and the length of the match.
33 Notice that this is not really a tool to work around spelling mistakes,
34 like what would be possible with difflib. The purpose is rather to have a
35 quicker or more intuitive way to filter the given completions, especially
36 when many completions have a common prefix.
38 Fuzzy algorithm is based on this post:
39 https://blog.amjith.com/fuzzyfinder-in-10-lines-of-python
41 :param completer: A :class:`~.Completer` instance.
42 :param WORD: When True, use WORD characters.
43 :param pattern: Regex pattern which selects the characters before the
44 cursor that are considered for the fuzzy matching.
45 :param enable_fuzzy: (bool or `Filter`) Enabled the fuzzy behavior. For
46 easily turning fuzzyness on or off according to a certain condition.
47 """
49 def __init__(
50 self,
51 completer: Completer,
52 WORD: bool = False,
53 pattern: str | None = None,
54 enable_fuzzy: FilterOrBool = True,
55 ) -> None:
56 assert pattern is None or pattern.startswith("^")
58 self.completer = completer
59 self.pattern = pattern
60 self.WORD = WORD
61 self.pattern = pattern
62 self.enable_fuzzy = to_filter(enable_fuzzy)
64 def get_completions(
65 self, document: Document, complete_event: CompleteEvent
66 ) -> Iterable[Completion]:
67 if self.enable_fuzzy():
68 return self._get_fuzzy_completions(document, complete_event)
69 else:
70 return self.completer.get_completions(document, complete_event)
72 def _get_pattern(self) -> str:
73 if self.pattern:
74 return self.pattern
75 if self.WORD:
76 return r"[^\s]+"
77 return "^[a-zA-Z0-9_]*"
79 def _get_fuzzy_completions(
80 self, document: Document, complete_event: CompleteEvent
81 ) -> Iterable[Completion]:
82 word_before_cursor = document.get_word_before_cursor(
83 pattern=re.compile(self._get_pattern())
84 )
86 # Get completions
87 document2 = Document(
88 text=document.text[: document.cursor_position - len(word_before_cursor)],
89 cursor_position=document.cursor_position - len(word_before_cursor),
90 )
92 inner_completions = list(
93 self.completer.get_completions(document2, complete_event)
94 )
96 fuzzy_matches: list[_FuzzyMatch] = []
98 if word_before_cursor == "":
99 # If word before the cursor is an empty string, consider all
100 # completions, without filtering everything with an empty regex
101 # pattern.
102 fuzzy_matches = [_FuzzyMatch(0, 0, compl) for compl in inner_completions]
103 else:
104 pat = ".*?".join(map(re.escape, word_before_cursor))
105 pat = f"(?=({pat}))" # lookahead regex to manage overlapping matches
106 regex = re.compile(pat, re.IGNORECASE)
107 for compl in inner_completions:
108 matches = list(regex.finditer(compl.text))
109 if matches:
110 # Prefer the match, closest to the left, then shortest.
111 best = min(matches, key=lambda m: (m.start(), len(m.group(1))))
112 fuzzy_matches.append(
113 _FuzzyMatch(len(best.group(1)), best.start(), compl)
114 )
116 def sort_key(fuzzy_match: _FuzzyMatch) -> tuple[int, int]:
117 "Sort by start position, then by the length of the match."
118 return fuzzy_match.start_pos, fuzzy_match.match_length
120 fuzzy_matches = sorted(fuzzy_matches, key=sort_key)
122 for match in fuzzy_matches:
123 # Include these completions, but set the correct `display`
124 # attribute and `start_position`.
125 yield Completion(
126 text=match.completion.text,
127 start_position=match.completion.start_position
128 - len(word_before_cursor),
129 # We access to private `_display_meta` attribute, because that one is lazy.
130 display_meta=match.completion._display_meta,
131 display=self._get_display(match, word_before_cursor),
132 style=match.completion.style,
133 )
135 def _get_display(
136 self, fuzzy_match: _FuzzyMatch, word_before_cursor: str
137 ) -> AnyFormattedText:
138 """
139 Generate formatted text for the display label.
140 """
142 def get_display() -> AnyFormattedText:
143 m = fuzzy_match
144 word = m.completion.text
146 if m.match_length == 0:
147 # No highlighting when we have zero length matches (no input text).
148 # In this case, use the original display text (which can include
149 # additional styling or characters).
150 return m.completion.display
152 result: StyleAndTextTuples = []
154 # Text before match.
155 result.append(("class:fuzzymatch.outside", word[: m.start_pos]))
157 # The match itself.
158 characters = list(word_before_cursor)
160 for c in word[m.start_pos : m.start_pos + m.match_length]:
161 classname = "class:fuzzymatch.inside"
162 if characters and c.lower() == characters[0].lower():
163 classname += ".character"
164 del characters[0]
166 result.append((classname, c))
168 # Text after match.
169 result.append(
170 ("class:fuzzymatch.outside", word[m.start_pos + m.match_length :])
171 )
173 return result
175 return get_display()
178class FuzzyWordCompleter(Completer):
179 """
180 Fuzzy completion on a list of words.
182 (This is basically a `WordCompleter` wrapped in a `FuzzyCompleter`.)
184 :param words: List of words or callable that returns a list of words.
185 :param meta_dict: Optional dict mapping words to their meta-information.
186 :param WORD: When True, use WORD characters.
187 """
189 def __init__(
190 self,
191 words: Sequence[str] | Callable[[], Sequence[str]],
192 meta_dict: dict[str, str] | None = None,
193 WORD: bool = False,
194 ) -> None:
195 self.words = words
196 self.meta_dict = meta_dict or {}
197 self.WORD = WORD
199 self.word_completer = WordCompleter(
200 words=self.words, WORD=self.WORD, meta_dict=self.meta_dict
201 )
203 self.fuzzy_completer = FuzzyCompleter(self.word_completer, WORD=self.WORD)
205 def get_completions(
206 self, document: Document, complete_event: CompleteEvent
207 ) -> Iterable[Completion]:
208 return self.fuzzy_completer.get_completions(document, complete_event)
211class _FuzzyMatch(NamedTuple):
212 match_length: int
213 start_pos: int
214 completion: Completion