Add a FuzzyWordCompleter.

amjith · jonathanslenders · commit d1d5d111da1d · 2018-12-12T20:04:33.000+01:00
Commit modified by: Jonathan Slenders.
diff --git a/examples/prompts/auto-completion/fuzzycompletion.py b/examples/prompts/auto-completion/fuzzycompletion.py
@@ -0,0 +1,32 @@
+#!/usr/bin/env python
+"""
+Autocompletion example.
+
+Press [Tab] to complete the current word.
+- The first Tab press fills in the common part of all completions
+    and shows all the completions. (In the menu)
+- Any following tab press cycles through all the possible completions.
+"""
+from __future__ import unicode_literals
+
+from prompt_toolkit.completion import FuzzyWordCompleter
+from prompt_toolkit.shortcuts import prompt
+
+
+animal_completer = FuzzyWordCompleter([
+    'alligator', 'ant', 'ape', 'bat', 'bear', 'beaver', 'bee', 'bison',
+    'butterfly', 'cat', 'chicken', 'crocodile', 'dinosaur', 'dog', 'dolphin',
+    'dove', 'duck', 'eagle', 'elephant', 'fish', 'goat', 'gorilla', 'kangaroo',
+    'leopard', 'lion', 'mouse', 'rabbit', 'rat', 'snake', 'spider', 'turkey',
+    'turtle',
+])
+
+
+def main():
+    text = prompt('Give some animals: ', completer=animal_completer,
+                  complete_while_typing=True)
+    print('You said: %s' % text)
+
+
+if __name__ == '__main__':
+    main()
diff --git a/prompt_toolkit/completion/__init__.py b/prompt_toolkit/completion/__init__.py
@@ -2,6 +2,7 @@
 from .base import Completion, Completer, ThreadedCompleter, DummyCompleter, DynamicCompleter, CompleteEvent, merge_completers, get_common_complete_suffix
 from .filesystem import PathCompleter, ExecutableCompleter
 from .word_completer import WordCompleter
+from .fuzzy_completer import FuzzyWordCompleter
 
 __all__ = [
     # Base.
@@ -20,4 +21,5 @@
 
     # Word completer.
     'WordCompleter',
+    'FuzzyWordCompleter',
 ]
diff --git a/prompt_toolkit/completion/fuzzy_completer.py b/prompt_toolkit/completion/fuzzy_completer.py
@@ -0,0 +1,80 @@
+from __future__ import unicode_literals
+import re
+
+from collections import namedtuple
+from six import string_types
+
+from prompt_toolkit.completion import Completer, Completion
+
+__all__ = [
+    'FuzzyWordCompleter',
+]
+
+
+class FuzzyWordCompleter(Completer):
+    """
+    Fuzzy completion on a list of words.
+
+    If the list of words is: ["leopard" , "gorilla", "dinosaur", "cat", "bee"]
+    Then trying to complete "oar" would yield "leopard" and "dinosaur", but not
+    the others, because they match the regular expression 'o.*a.*r'.
+
+    The results are sorted by relevance, which is defined as the start position
+    of the match and then the proportion of the word span that is covered. As a
+    user, if you want to get leopard, it's better to type 'ld' (first + last
+    letter) because this covers 100% of the word.
+
+    See: https://blog.amjith.com/fuzzyfinder-in-10-lines-of-python
+
+    :param words: List of words or callable that returns a list of words.
+    :param meta_dict: Optional dict mapping words to their meta-information.
+    :param WORD: When True, use WORD characters.
+    :param sort_results: Boolean to determine whether to sort the results (default: True).
+
+    Fuzzy algorithm is based on this post: https://blog.amjith.com/fuzzyfinder-in-10-lines-of-python
+    """
+    def __init__(self, words, meta_dict=None, WORD=False, sort_results=True):
+        assert callable(words) or all(isinstance(w, string_types) for w in words)
+
+        self.words = words
+        self.meta_dict = meta_dict or {}
+        self.sort_results = sort_results
+        self.WORD = WORD
+
+    def get_completions(self, document, complete_event):
+        # Get list of words.
+        words = self.words
+        if callable(words):
+            words = words()
+
+        word_before_cursor = document.get_word_before_cursor(WORD=self.WORD)
+
+        fuzzy_matches = []
+        pat = '.*?'.join(map(re.escape, word_before_cursor))
+        pat = '(?=({0}))'.format(pat)   # lookahead regex to manage overlapping matches
+        regex = re.compile(pat, re.IGNORECASE)
+        for word in words:
+            matches = list(regex.finditer(word))
+            if matches:
+                best = min(matches, key=lambda x: len(x.group(1)))   # find shortest match
+                fuzzy_matches.append(_FuzzyMatch(len(best.group(1)), best.start(), word))
+
+        def sort_key(fuzzy_match):
+            " Sort by start position, then by proportion of word that is covered. "
+            return (
+                fuzzy_match.start_pos,
+                float(fuzzy_match.match_length) / len(fuzzy_match.word)
+            )
+
+        fuzzy_matches = sorted(fuzzy_matches, key=sort_key)
+
+        for match in fuzzy_matches:
+            display_meta = self.meta_dict.get(match.word, '')
+
+            yield Completion(
+                match.word,
+                -len(word_before_cursor),
+                display_meta=display_meta)
+
+
+_FuzzyMatch = namedtuple('_FuzzyMatch', 'match_length start_pos word')
diff --git a/tests/test_completion.py b/tests/test_completion.py
@@ -7,7 +7,7 @@
 from contextlib import contextmanager
 from six import text_type
 
-from prompt_toolkit.completion import CompleteEvent, PathCompleter, WordCompleter
+from prompt_toolkit.completion import CompleteEvent, PathCompleter, WordCompleter, FuzzyWordCompleter
 from prompt_toolkit.document import Document
 
 
@@ -314,3 +314,34 @@ def get_words():
     completions = completer.get_completions(Document('a'), CompleteEvent())
     assert [c.text for c in completions] == ['abc', 'aaa']
     assert called[0] == 2
+
+def test_fuzzy_completer():
+    collection = [
+            'migrations.py',
+            'django_migrations.py',
+            'django_admin_log.py',
+            'api_user.doc',
+            'user_group.doc',
+            'users.txt',
+            'accounts.txt',
+            '123.py',
+            'test123test.py'
+            ]
+    completer = FuzzyWordCompleter(collection)
+    completions = completer.get_completions(Document('txt'), CompleteEvent())
+    assert [c.text for c in completions] == ['users.txt', 'accounts.txt']
+
+    completions = completer.get_completions(Document('djmi'), CompleteEvent())
+    assert [c.text for c in completions] == ['django_migrations.py', 'django_admin_log.py']
+
+    completions = completer.get_completions(Document('mi'), CompleteEvent())
+    assert [c.text for c in completions] == ['migrations.py', 'django_migrations.py', 'django_admin_log.py']
+
+    completions = completer.get_completions(Document('user'), CompleteEvent())
+    assert [c.text for c in completions] == ['user_group.doc', 'users.txt', 'api_user.doc']
+
+    completions = completer.get_completions(Document('123'), CompleteEvent())
+    assert [c.text for c in completions] == ['123.py', 'test123test.py']
+
+    completions = completer.get_completions(Document('miGr'), CompleteEvent())
+    assert [c.text for c in completions] == ['migrations.py', 'django_migrations.py',]
