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