Adding upstream version 3.0.36.upstream/3.0.36upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

7 files changed, 1069 insertions, 0 deletions

diff --git a/src/prompt_toolkit/completion/__init__.py b/src/prompt_toolkit/completion/__init__.py
new file mode 100644
index 0000000..270c743
--- /dev/null
+++ b/src/prompt_toolkit/completion/__init__.py
@@ -0,0 +1,41 @@
+from .base import (
+    CompleteEvent,
+    Completer,
+    Completion,
+    ConditionalCompleter,
+    DummyCompleter,
+    DynamicCompleter,
+    ThreadedCompleter,
+    get_common_complete_suffix,
+    merge_completers,
+)
+from .deduplicate import DeduplicateCompleter
+from .filesystem import ExecutableCompleter, PathCompleter
+from .fuzzy_completer import FuzzyCompleter, FuzzyWordCompleter
+from .nested import NestedCompleter
+from .word_completer import WordCompleter
+
+__all__ = [
+    # Base.
+    "Completion",
+    "Completer",
+    "ThreadedCompleter",
+    "DummyCompleter",
+    "DynamicCompleter",
+    "CompleteEvent",
+    "ConditionalCompleter",
+    "merge_completers",
+    "get_common_complete_suffix",
+    # Filesystem.
+    "PathCompleter",
+    "ExecutableCompleter",
+    # Fuzzy
+    "FuzzyCompleter",
+    "FuzzyWordCompleter",
+    # Nested.
+    "NestedCompleter",
+    # Word completer.
+    "WordCompleter",
+    # Deduplicate
+    "DeduplicateCompleter",
+]
diff --git a/src/prompt_toolkit/completion/base.py b/src/prompt_toolkit/completion/base.py
new file mode 100644
index 0000000..bd575ec
--- /dev/null
+++ b/src/prompt_toolkit/completion/base.py
@@ -0,0 +1,455 @@
+"""
+"""
+from abc import ABCMeta, abstractmethod
+from typing import AsyncGenerator, Callable, Iterable, List, Optional, Sequence
+
+from prompt_toolkit.document import Document
+from prompt_toolkit.eventloop import (
+    aclosing,
+    generator_to_async_generator,
+    get_event_loop,
+)
+from prompt_toolkit.filters import FilterOrBool, to_filter
+from prompt_toolkit.formatted_text import AnyFormattedText, StyleAndTextTuples
+
+__all__ = [
+    "Completion",
+    "Completer",
+    "ThreadedCompleter",
+    "DummyCompleter",
+    "DynamicCompleter",
+    "CompleteEvent",
+    "ConditionalCompleter",
+    "merge_completers",
+    "get_common_complete_suffix",
+]
+
+
+class Completion:
+    """
+    :param text: The new string that will be inserted into the document.
+    :param start_position: Position relative to the cursor_position where the
+        new text will start. The text will be inserted between the
+        start_position and the original cursor position.
+    :param display: (optional string or formatted text) If the completion has
+        to be displayed differently in the completion menu.
+    :param display_meta: (Optional string or formatted text) Meta information
+        about the completion, e.g. the path or source where it's coming from.
+        This can also be a callable that returns a string.
+    :param style: Style string.
+    :param selected_style: Style string, used for a selected completion.
+        This can override the `style` parameter.
+    """
+
+    def __init__(
+        self,
+        text: str,
+        start_position: int = 0,
+        display: Optional[AnyFormattedText] = None,
+        display_meta: Optional[AnyFormattedText] = None,
+        style: str = "",
+        selected_style: str = "",
+    ) -> None:
+
+        from prompt_toolkit.formatted_text import to_formatted_text
+
+        self.text = text
+        self.start_position = start_position
+        self._display_meta = display_meta
+
+        if display is None:
+            display = text
+
+        self.display = to_formatted_text(display)
+
+        self.style = style
+        self.selected_style = selected_style
+
+        assert self.start_position <= 0
+
+    def __repr__(self) -> str:
+        if isinstance(self.display, str) and self.display == self.text:
+            return "{}(text={!r}, start_position={!r})".format(
+                self.__class__.__name__,
+                self.text,
+                self.start_position,
+            )
+        else:
+            return "{}(text={!r}, start_position={!r}, display={!r})".format(
+                self.__class__.__name__,
+                self.text,
+                self.start_position,
+                self.display,
+            )
+
+    def __eq__(self, other: object) -> bool:
+        if not isinstance(other, Completion):
+            return False
+        return (
+            self.text == other.text
+            and self.start_position == other.start_position
+            and self.display == other.display
+            and self._display_meta == other._display_meta
+        )
+
+    def __hash__(self) -> int:
+        return hash((self.text, self.start_position, self.display, self._display_meta))
+
+    @property
+    def display_text(self) -> str:
+        "The 'display' field as plain text."
+        from prompt_toolkit.formatted_text import fragment_list_to_text
+
+        return fragment_list_to_text(self.display)
+
+    @property
+    def display_meta(self) -> StyleAndTextTuples:
+        "Return meta-text. (This is lazy when using a callable)."
+        from prompt_toolkit.formatted_text import to_formatted_text
+
+        return to_formatted_text(self._display_meta or "")
+
+    @property
+    def display_meta_text(self) -> str:
+        "The 'meta' field as plain text."
+        from prompt_toolkit.formatted_text import fragment_list_to_text
+
+        return fragment_list_to_text(self.display_meta)
+
+    def new_completion_from_position(self, position: int) -> "Completion":
+        """
+        (Only for internal use!)
+        Get a new completion by splitting this one. Used by `Application` when
+        it needs to have a list of new completions after inserting the common
+        prefix.
+        """
+        assert position - self.start_position >= 0
+
+        return Completion(
+            text=self.text[position - self.start_position :],
+            display=self.display,
+            display_meta=self._display_meta,
+        )
+
+
+class CompleteEvent:
+    """
+    Event that called the completer.
+
+    :param text_inserted: When True, it means that completions are requested
+        because of a text insert. (`Buffer.complete_while_typing`.)
+    :param completion_requested: When True, it means that the user explicitly
+        pressed the `Tab` key in order to view the completions.
+
+    These two flags can be used for instance to implement a completer that
+    shows some completions when ``Tab`` has been pressed, but not
+    automatically when the user presses a space. (Because of
+    `complete_while_typing`.)
+    """
+
+    def __init__(
+        self, text_inserted: bool = False, completion_requested: bool = False
+    ) -> None:
+        assert not (text_inserted and completion_requested)
+
+        #: Automatic completion while typing.
+        self.text_inserted = text_inserted
+
+        #: Used explicitly requested completion by pressing 'tab'.
+        self.completion_requested = completion_requested
+
+    def __repr__(self) -> str:
+        return "{}(text_inserted={!r}, completion_requested={!r})".format(
+            self.__class__.__name__,
+            self.text_inserted,
+            self.completion_requested,
+        )
+
+
+class Completer(metaclass=ABCMeta):
+    """
+    Base class for completer implementations.
+    """
+
+    @abstractmethod
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        """
+        This should be a generator that yields :class:`.Completion` instances.
+
+        If the generation of completions is something expensive (that takes a
+        lot of time), consider wrapping this `Completer` class in a
+        `ThreadedCompleter`. In that case, the completer algorithm runs in a
+        background thread and completions will be displayed as soon as they
+        arrive.
+
+        :param document: :class:`~prompt_toolkit.document.Document` instance.
+        :param complete_event: :class:`.CompleteEvent` instance.
+        """
+        while False:
+            yield
+
+    async def get_completions_async(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> AsyncGenerator[Completion, None]:
+        """
+        Asynchronous generator for completions. (Probably, you won't have to
+        override this.)
+
+        Asynchronous generator of :class:`.Completion` objects.
+        """
+        for item in self.get_completions(document, complete_event):
+            yield item
+
+
+class ThreadedCompleter(Completer):
+    """
+    Wrapper that runs the `get_completions` generator in a thread.
+
+    (Use this to prevent the user interface from becoming unresponsive if the
+    generation of completions takes too much time.)
+
+    The completions will be displayed as soon as they are produced. The user
+    can already select a completion, even if not all completions are displayed.
+    """
+
+    def __init__(self, completer: Completer) -> None:
+        self.completer = completer
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        return self.completer.get_completions(document, complete_event)
+
+    async def get_completions_async(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> AsyncGenerator[Completion, None]:
+        """
+        Asynchronous generator of completions.
+        """
+        # NOTE: Right now, we are consuming the `get_completions` generator in
+        #       a synchronous background thread, then passing the results one
+        #       at a time over a queue, and consuming this queue in the main
+        #       thread (that's what `generator_to_async_generator` does). That
+        #       means that if the completer is *very* slow, we'll be showing
+        #       completions in the UI once they are computed.
+
+        #       It's very tempting to replace this implementation with the
+        #       commented code below for several reasons:
+
+        #       - `generator_to_async_generator` is not perfect and hard to get
+        #         right. It's a lot of complexity for little gain. The
+        #         implementation needs a huge buffer for it to be efficient
+        #         when there are many completions (like 50k+).
+        #       - Normally, a completer is supposed to be fast, users can have
+        #         "complete while typing" enabled, and want to see the
+        #         completions within a second. Handling one completion at a
+        #         time, and rendering once we get it here doesn't make any
+        #         sense if this is quick anyway.
+        #       - Completers like `FuzzyCompleter` prepare all completions
+        #         anyway so that they can be sorted by accuracy before they are
+        #         yielded. At the point that we start yielding completions
+        #         here, we already have all completions.
+        #       - The `Buffer` class has complex logic to invalidate the UI
+        #         while it is consuming the completions. We don't want to
+        #         invalidate the UI for every completion (if there are many),
+        #         but we want to do it often enough so that completions are
+        #         being displayed while they are produced.
+
+        #       We keep the current behavior mainly for backward-compatibility.
+        #       Similarly, it would be better for this function to not return
+        #       an async generator, but simply be a coroutine that returns a
+        #       list of `Completion` objects, containing all completions at
+        #       once.
+
+        #       Note that this argument doesn't mean we shouldn't use
+        #       `ThreadedCompleter`. It still makes sense to produce
+        #       completions in a background thread, because we don't want to
+        #       freeze the UI while the user is typing. But sending the
+        #       completions one at a time to the UI maybe isn't worth it.
+
+        # def get_all_in_thread() -> List[Completion]:
+        #   return list(self.get_completions(document, complete_event))
+
+        # completions = await get_event_loop().run_in_executor(None, get_all_in_thread)
+        # for completion in completions:
+        #   yield completion
+
+        async with aclosing(
+            generator_to_async_generator(
+                lambda: self.completer.get_completions(document, complete_event)
+            )
+        ) as async_generator:
+            async for completion in async_generator:
+                yield completion
+
+    def __repr__(self) -> str:
+        return f"ThreadedCompleter({self.completer!r})"
+
+
+class DummyCompleter(Completer):
+    """
+    A completer that doesn't return any completion.
+    """
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        return []
+
+    def __repr__(self) -> str:
+        return "DummyCompleter()"
+
+
+class DynamicCompleter(Completer):
+    """
+    Completer class that can dynamically returns any Completer.
+
+    :param get_completer: Callable that returns a :class:`.Completer` instance.
+    """
+
+    def __init__(self, get_completer: Callable[[], Optional[Completer]]) -> None:
+        self.get_completer = get_completer
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        completer = self.get_completer() or DummyCompleter()
+        return completer.get_completions(document, complete_event)
+
+    async def get_completions_async(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> AsyncGenerator[Completion, None]:
+        completer = self.get_completer() or DummyCompleter()
+
+        async for completion in completer.get_completions_async(
+            document, complete_event
+        ):
+            yield completion
+
+    def __repr__(self) -> str:
+        return f"DynamicCompleter({self.get_completer!r} -> {self.get_completer()!r})"
+
+
+class ConditionalCompleter(Completer):
+    """
+    Wrapper around any other completer that will enable/disable the completions
+    depending on whether the received condition is satisfied.
+
+    :param completer: :class:`.Completer` instance.
+    :param filter: :class:`.Filter` instance.
+    """
+
+    def __init__(self, completer: Completer, filter: FilterOrBool) -> None:
+        self.completer = completer
+        self.filter = to_filter(filter)
+
+    def __repr__(self) -> str:
+        return f"ConditionalCompleter({self.completer!r}, filter={self.filter!r})"
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        # Get all completions in a blocking way.
+        if self.filter():
+            yield from self.completer.get_completions(document, complete_event)
+
+    async def get_completions_async(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> AsyncGenerator[Completion, None]:
+
+        # Get all completions in a non-blocking way.
+        if self.filter():
+            async with aclosing(
+                self.completer.get_completions_async(document, complete_event)
+            ) as async_generator:
+                async for item in async_generator:
+                    yield item
+
+
+class _MergedCompleter(Completer):
+    """
+    Combine several completers into one.
+    """
+
+    def __init__(self, completers: Sequence[Completer]) -> None:
+        self.completers = completers
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        # Get all completions from the other completers in a blocking way.
+        for completer in self.completers:
+            yield from completer.get_completions(document, complete_event)
+
+    async def get_completions_async(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> AsyncGenerator[Completion, None]:
+
+        # Get all completions from the other completers in a non-blocking way.
+        for completer in self.completers:
+            async with aclosing(
+                completer.get_completions_async(document, complete_event)
+            ) as async_generator:
+                async for item in async_generator:
+                    yield item
+
+
+def merge_completers(
+    completers: Sequence[Completer], deduplicate: bool = False
+) -> Completer:
+    """
+    Combine several completers into one.
+
+    :param deduplicate: If `True`, wrap the result in a `DeduplicateCompleter`
+        so that completions that would result in the same text will be
+        deduplicated.
+    """
+    if deduplicate:
+        from .deduplicate import DeduplicateCompleter
+
+        return DeduplicateCompleter(_MergedCompleter(completers))
+
+    return _MergedCompleter(completers)
+
+
+def get_common_complete_suffix(
+    document: Document, completions: Sequence[Completion]
+) -> str:
+    """
+    Return the common prefix for all completions.
+    """
+    # Take only completions that don't change the text before the cursor.
+    def doesnt_change_before_cursor(completion: Completion) -> bool:
+        end = completion.text[: -completion.start_position]
+        return document.text_before_cursor.endswith(end)
+
+    completions2 = [c for c in completions if doesnt_change_before_cursor(c)]
+
+    # When there is at least one completion that changes the text before the
+    # cursor, don't return any common part.
+    if len(completions2) != len(completions):
+        return ""
+
+    # Return the common prefix.
+    def get_suffix(completion: Completion) -> str:
+        return completion.text[-completion.start_position :]
+
+    return _commonprefix([get_suffix(c) for c in completions2])
+
+
+def _commonprefix(strings: Iterable[str]) -> str:
+    # Similar to os.path.commonprefix
+    if not strings:
+        return ""
+
+    else:
+        s1 = min(strings)
+        s2 = max(strings)
+
+        for i, c in enumerate(s1):
+            if c != s2[i]:
+                return s1[:i]
+
+        return s1
diff --git a/src/prompt_toolkit/completion/deduplicate.py b/src/prompt_toolkit/completion/deduplicate.py
new file mode 100644
index 0000000..6ef9522
--- /dev/null
+++ b/src/prompt_toolkit/completion/deduplicate.py
@@ -0,0 +1,43 @@
+from typing import Iterable, Set
+
+from prompt_toolkit.document import Document
+
+from .base import CompleteEvent, Completer, Completion
+
+__all__ = ["DeduplicateCompleter"]
+
+
+class DeduplicateCompleter(Completer):
+    """
+    Wrapper around a completer that removes duplicates. Only the first unique
+    completions are kept.
+
+    Completions are considered to be a duplicate if they result in the same
+    document text when they would be applied.
+    """
+
+    def __init__(self, completer: Completer) -> None:
+        self.completer = completer
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        # Keep track of the document strings we'd get after applying any completion.
+        found_so_far: Set[str] = set()
+
+        for completion in self.completer.get_completions(document, complete_event):
+            text_if_applied = (
+                document.text[: document.cursor_position + completion.start_position]
+                + completion.text
+                + document.text[document.cursor_position :]
+            )
+
+            if text_if_applied == document.text:
+                # Don't include completions that don't have any effect at all.
+                continue
+
+            if text_if_applied in found_so_far:
+                continue
+
+            found_so_far.add(text_if_applied)
+            yield completion
diff --git a/src/prompt_toolkit/completion/filesystem.py b/src/prompt_toolkit/completion/filesystem.py
new file mode 100644
index 0000000..719eac6
--- /dev/null
+++ b/src/prompt_toolkit/completion/filesystem.py
@@ -0,0 +1,117 @@
+import os
+from typing import Callable, Iterable, List, Optional
+
+from prompt_toolkit.completion import CompleteEvent, Completer, Completion
+from prompt_toolkit.document import Document
+
+__all__ = [
+    "PathCompleter",
+    "ExecutableCompleter",
+]
+
+
+class PathCompleter(Completer):
+    """
+    Complete for Path variables.
+
+    :param get_paths: Callable which returns a list of directories to look into
+                      when the user enters a relative path.
+    :param file_filter: Callable which takes a filename and returns whether
+                        this file should show up in the completion. ``None``
+                        when no filtering has to be done.
+    :param min_input_len: Don't do autocompletion when the input string is shorter.
+    """
+
+    def __init__(
+        self,
+        only_directories: bool = False,
+        get_paths: Optional[Callable[[], List[str]]] = None,
+        file_filter: Optional[Callable[[str], bool]] = None,
+        min_input_len: int = 0,
+        expanduser: bool = False,
+    ) -> None:
+
+        self.only_directories = only_directories
+        self.get_paths = get_paths or (lambda: ["."])
+        self.file_filter = file_filter or (lambda _: True)
+        self.min_input_len = min_input_len
+        self.expanduser = expanduser
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        text = document.text_before_cursor
+
+        # Complete only when we have at least the minimal input length,
+        # otherwise, we can too many results and autocompletion will become too
+        # heavy.
+        if len(text) < self.min_input_len:
+            return
+
+        try:
+            # Do tilde expansion.
+            if self.expanduser:
+                text = os.path.expanduser(text)
+
+            # Directories where to look.
+            dirname = os.path.dirname(text)
+            if dirname:
+                directories = [
+                    os.path.dirname(os.path.join(p, text)) for p in self.get_paths()
+                ]
+            else:
+                directories = self.get_paths()
+
+            # Start of current file.
+            prefix = os.path.basename(text)
+
+            # Get all filenames.
+            filenames = []
+            for directory in directories:
+                # Look for matches in this directory.
+                if os.path.isdir(directory):
+                    for filename in os.listdir(directory):
+                        if filename.startswith(prefix):
+                            filenames.append((directory, filename))
+
+            # Sort
+            filenames = sorted(filenames, key=lambda k: k[1])
+
+            # Yield them.
+            for directory, filename in filenames:
+                completion = filename[len(prefix) :]
+                full_name = os.path.join(directory, filename)
+
+                if os.path.isdir(full_name):
+                    # For directories, add a slash to the filename.
+                    # (We don't add them to the `completion`. Users can type it
+                    # to trigger the autocompletion themselves.)
+                    filename += "/"
+                elif self.only_directories:
+                    continue
+
+                if not self.file_filter(full_name):
+                    continue
+
+                yield Completion(
+                    text=completion,
+                    start_position=0,
+                    display=filename,
+                )
+        except OSError:
+            pass
+
+
+class ExecutableCompleter(PathCompleter):
+    """
+    Complete only executable files in the current path.
+    """
+
+    def __init__(self) -> None:
+        super().__init__(
+            only_directories=False,
+            min_input_len=1,
+            get_paths=lambda: os.environ.get("PATH", "").split(os.pathsep),
+            file_filter=lambda name: os.access(name, os.X_OK),
+            expanduser=True,
+        ),
diff --git a/src/prompt_toolkit/completion/fuzzy_completer.py b/src/prompt_toolkit/completion/fuzzy_completer.py
new file mode 100644
index 0000000..ab5402f
--- /dev/null
+++ b/src/prompt_toolkit/completion/fuzzy_completer.py
@@ -0,0 +1,213 @@
+import re
+from typing import Callable, Dict, Iterable, List, NamedTuple, Optional, Tuple, Union
+
+from prompt_toolkit.document import Document
+from prompt_toolkit.filters import FilterOrBool, to_filter
+from prompt_toolkit.formatted_text import AnyFormattedText, StyleAndTextTuples
+
+from .base import CompleteEvent, Completer, Completion
+from .word_completer import WordCompleter
+
+__all__ = [
+    "FuzzyCompleter",
+    "FuzzyWordCompleter",
+]
+
+
+class FuzzyCompleter(Completer):
+    """
+    Fuzzy completion.
+    This wraps any other completer and turns it into a fuzzy completer.
+
+    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'.
+    Similar, in another application "djm" could expand to "django_migrations".
+
+    The results are sorted by relevance, which is defined as the start position
+    and the length of the match.
+
+    Notice that this is not really a tool to work around spelling mistakes,
+    like what would be possible with difflib. The purpose is rather to have a
+    quicker or more intuitive way to filter the given completions, especially
+    when many completions have a common prefix.
+
+    Fuzzy algorithm is based on this post:
+    https://blog.amjith.com/fuzzyfinder-in-10-lines-of-python
+
+    :param completer: A :class:`~.Completer` instance.
+    :param WORD: When True, use WORD characters.
+    :param pattern: Regex pattern which selects the characters before the
+        cursor that are considered for the fuzzy matching.
+    :param enable_fuzzy: (bool or `Filter`) Enabled the fuzzy behavior. For
+        easily turning fuzzyness on or off according to a certain condition.
+    """
+
+    def __init__(
+        self,
+        completer: Completer,
+        WORD: bool = False,
+        pattern: Optional[str] = None,
+        enable_fuzzy: FilterOrBool = True,
+    ) -> None:
+
+        assert pattern is None or pattern.startswith("^")
+
+        self.completer = completer
+        self.pattern = pattern
+        self.WORD = WORD
+        self.pattern = pattern
+        self.enable_fuzzy = to_filter(enable_fuzzy)
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        if self.enable_fuzzy():
+            return self._get_fuzzy_completions(document, complete_event)
+        else:
+            return self.completer.get_completions(document, complete_event)
+
+    def _get_pattern(self) -> str:
+        if self.pattern:
+            return self.pattern
+        if self.WORD:
+            return r"[^\s]+"
+        return "^[a-zA-Z0-9_]*"
+
+    def _get_fuzzy_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        word_before_cursor = document.get_word_before_cursor(
+            pattern=re.compile(self._get_pattern())
+        )
+
+        # Get completions
+        document2 = Document(
+            text=document.text[: document.cursor_position - len(word_before_cursor)],
+            cursor_position=document.cursor_position - len(word_before_cursor),
+        )
+
+        inner_completions = list(
+            self.completer.get_completions(document2, complete_event)
+        )
+
+        fuzzy_matches: List[_FuzzyMatch] = []
+
+        if word_before_cursor == "":
+            # If word before the cursor is an empty string, consider all
+            # completions, without filtering everything with an empty regex
+            # pattern.
+            fuzzy_matches = [_FuzzyMatch(0, 0, compl) for compl in inner_completions]
+        else:
+            pat = ".*?".join(map(re.escape, word_before_cursor))
+            pat = f"(?=({pat}))"  # lookahead regex to manage overlapping matches
+            regex = re.compile(pat, re.IGNORECASE)
+            for compl in inner_completions:
+                matches = list(regex.finditer(compl.text))
+                if matches:
+                    # Prefer the match, closest to the left, then shortest.
+                    best = min(matches, key=lambda m: (m.start(), len(m.group(1))))
+                    fuzzy_matches.append(
+                        _FuzzyMatch(len(best.group(1)), best.start(), compl)
+                    )
+
+            def sort_key(fuzzy_match: "_FuzzyMatch") -> Tuple[int, int]:
+                "Sort by start position, then by the length of the match."
+                return fuzzy_match.start_pos, fuzzy_match.match_length
+
+            fuzzy_matches = sorted(fuzzy_matches, key=sort_key)
+
+        for match in fuzzy_matches:
+            # Include these completions, but set the correct `display`
+            # attribute and `start_position`.
+            yield Completion(
+                text=match.completion.text,
+                start_position=match.completion.start_position
+                - len(word_before_cursor),
+                # We access to private `_display_meta` attribute, because that one is lazy.
+                display_meta=match.completion._display_meta,
+                display=self._get_display(match, word_before_cursor),
+                style=match.completion.style,
+            )
+
+    def _get_display(
+        self, fuzzy_match: "_FuzzyMatch", word_before_cursor: str
+    ) -> AnyFormattedText:
+        """
+        Generate formatted text for the display label.
+        """
+
+        def get_display() -> AnyFormattedText:
+            m = fuzzy_match
+            word = m.completion.text
+
+            if m.match_length == 0:
+                # No highlighting when we have zero length matches (no input text).
+                # In this case, use the original display text (which can include
+                # additional styling or characters).
+                return m.completion.display
+
+            result: StyleAndTextTuples = []
+
+            # Text before match.
+            result.append(("class:fuzzymatch.outside", word[: m.start_pos]))
+
+            # The match itself.
+            characters = list(word_before_cursor)
+
+            for c in word[m.start_pos : m.start_pos + m.match_length]:
+                classname = "class:fuzzymatch.inside"
+                if characters and c.lower() == characters[0].lower():
+                    classname += ".character"
+                    del characters[0]
+
+                result.append((classname, c))
+
+            # Text after match.
+            result.append(
+                ("class:fuzzymatch.outside", word[m.start_pos + m.match_length :])
+            )
+
+            return result
+
+        return get_display()
+
+
+class FuzzyWordCompleter(Completer):
+    """
+    Fuzzy completion on a list of words.
+
+    (This is basically a `WordCompleter` wrapped in a `FuzzyCompleter`.)
+
+    :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.
+    """
+
+    def __init__(
+        self,
+        words: Union[List[str], Callable[[], List[str]]],
+        meta_dict: Optional[Dict[str, str]] = None,
+        WORD: bool = False,
+    ) -> None:
+
+        self.words = words
+        self.meta_dict = meta_dict or {}
+        self.WORD = WORD
+
+        self.word_completer = WordCompleter(
+            words=self.words, WORD=self.WORD, meta_dict=self.meta_dict
+        )
+
+        self.fuzzy_completer = FuzzyCompleter(self.word_completer, WORD=self.WORD)
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        return self.fuzzy_completer.get_completions(document, complete_event)
+
+
+class _FuzzyMatch(NamedTuple):
+    match_length: int
+    start_pos: int
+    completion: Completion
diff --git a/src/prompt_toolkit/completion/nested.py b/src/prompt_toolkit/completion/nested.py
new file mode 100644
index 0000000..f8656b2
--- /dev/null
+++ b/src/prompt_toolkit/completion/nested.py
@@ -0,0 +1,107 @@
+"""
+Nestedcompleter for completion of hierarchical data structures.
+"""
+from typing import Any, Dict, Iterable, Mapping, Optional, Set, Union
+
+from prompt_toolkit.completion import CompleteEvent, Completer, Completion
+from prompt_toolkit.completion.word_completer import WordCompleter
+from prompt_toolkit.document import Document
+
+__all__ = ["NestedCompleter"]
+
+# NestedDict = Mapping[str, Union['NestedDict', Set[str], None, Completer]]
+NestedDict = Mapping[str, Union[Any, Set[str], None, Completer]]
+
+
+class NestedCompleter(Completer):
+    """
+    Completer which wraps around several other completers, and calls any the
+    one that corresponds with the first word of the input.
+
+    By combining multiple `NestedCompleter` instances, we can achieve multiple
+    hierarchical levels of autocompletion. This is useful when `WordCompleter`
+    is not sufficient.
+
+    If you need multiple levels, check out the `from_nested_dict` classmethod.
+    """
+
+    def __init__(
+        self, options: Dict[str, Optional[Completer]], ignore_case: bool = True
+    ) -> None:
+
+        self.options = options
+        self.ignore_case = ignore_case
+
+    def __repr__(self) -> str:
+        return f"NestedCompleter({self.options!r}, ignore_case={self.ignore_case!r})"
+
+    @classmethod
+    def from_nested_dict(cls, data: NestedDict) -> "NestedCompleter":
+        """
+        Create a `NestedCompleter`, starting from a nested dictionary data
+        structure, like this:
+
+        .. code::
+
+            data = {
+                'show': {
+                    'version': None,
+                    'interfaces': None,
+                    'clock': None,
+                    'ip': {'interface': {'brief'}}
+                },
+                'exit': None
+                'enable': None
+            }
+
+        The value should be `None` if there is no further completion at some
+        point. If all values in the dictionary are None, it is also possible to
+        use a set instead.
+
+        Values in this data structure can be a completers as well.
+        """
+        options: Dict[str, Optional[Completer]] = {}
+        for key, value in data.items():
+            if isinstance(value, Completer):
+                options[key] = value
+            elif isinstance(value, dict):
+                options[key] = cls.from_nested_dict(value)
+            elif isinstance(value, set):
+                options[key] = cls.from_nested_dict({item: None for item in value})
+            else:
+                assert value is None
+                options[key] = None
+
+        return cls(options)
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        # Split document.
+        text = document.text_before_cursor.lstrip()
+        stripped_len = len(document.text_before_cursor) - len(text)
+
+        # If there is a space, check for the first term, and use a
+        # subcompleter.
+        if " " in text:
+            first_term = text.split()[0]
+            completer = self.options.get(first_term)
+
+            # If we have a sub completer, use this for the completions.
+            if completer is not None:
+                remaining_text = text[len(first_term) :].lstrip()
+                move_cursor = len(text) - len(remaining_text) + stripped_len
+
+                new_document = Document(
+                    remaining_text,
+                    cursor_position=document.cursor_position - move_cursor,
+                )
+
+                yield from completer.get_completions(new_document, complete_event)
+
+        # No space in the input: behave exactly like `WordCompleter`.
+        else:
+            completer = WordCompleter(
+                list(self.options.keys()), ignore_case=self.ignore_case
+            )
+            yield from completer.get_completions(document, complete_event)
diff --git a/src/prompt_toolkit/completion/word_completer.py b/src/prompt_toolkit/completion/word_completer.py
new file mode 100644
index 0000000..28c133e
--- /dev/null
+++ b/src/prompt_toolkit/completion/word_completer.py
@@ -0,0 +1,93 @@
+from typing import Callable, Iterable, List, Mapping, Optional, Pattern, Union
+
+from prompt_toolkit.completion import CompleteEvent, Completer, Completion
+from prompt_toolkit.document import Document
+from prompt_toolkit.formatted_text import AnyFormattedText
+
+__all__ = [
+    "WordCompleter",
+]
+
+
+class WordCompleter(Completer):
+    """
+    Simple autocompletion on a list of words.
+
+    :param words: List of words or callable that returns a list of words.
+    :param ignore_case: If True, case-insensitive completion.
+    :param meta_dict: Optional dict mapping words to their meta-text. (This
+        should map strings to strings or formatted text.)
+    :param WORD: When True, use WORD characters.
+    :param sentence: When True, don't complete by comparing the word before the
+        cursor, but by comparing all the text before the cursor. In this case,
+        the list of words is just a list of strings, where each string can
+        contain spaces. (Can not be used together with the WORD option.)
+    :param match_middle: When True, match not only the start, but also in the
+                         middle of the word.
+    :param pattern: Optional compiled regex for finding the word before
+        the cursor to complete. When given, use this regex pattern instead of
+        default one (see document._FIND_WORD_RE)
+    """
+
+    def __init__(
+        self,
+        words: Union[List[str], Callable[[], List[str]]],
+        ignore_case: bool = False,
+        display_dict: Optional[Mapping[str, AnyFormattedText]] = None,
+        meta_dict: Optional[Mapping[str, AnyFormattedText]] = None,
+        WORD: bool = False,
+        sentence: bool = False,
+        match_middle: bool = False,
+        pattern: Optional[Pattern[str]] = None,
+    ) -> None:
+
+        assert not (WORD and sentence)
+
+        self.words = words
+        self.ignore_case = ignore_case
+        self.display_dict = display_dict or {}
+        self.meta_dict = meta_dict or {}
+        self.WORD = WORD
+        self.sentence = sentence
+        self.match_middle = match_middle
+        self.pattern = pattern
+
+    def get_completions(
+        self, document: Document, complete_event: CompleteEvent
+    ) -> Iterable[Completion]:
+        # Get list of words.
+        words = self.words
+        if callable(words):
+            words = words()
+
+        # Get word/text before cursor.
+        if self.sentence:
+            word_before_cursor = document.text_before_cursor
+        else:
+            word_before_cursor = document.get_word_before_cursor(
+                WORD=self.WORD, pattern=self.pattern
+            )
+
+        if self.ignore_case:
+            word_before_cursor = word_before_cursor.lower()
+
+        def word_matches(word: str) -> bool:
+            """True when the word before the cursor matches."""
+            if self.ignore_case:
+                word = word.lower()
+
+            if self.match_middle:
+                return word_before_cursor in word
+            else:
+                return word.startswith(word_before_cursor)
+
+        for a in words:
+            if word_matches(a):
+                display = self.display_dict.get(a, a)
+                display_meta = self.meta_dict.get(a, "")
+                yield Completion(
+                    text=a,
+                    start_position=-len(word_before_cursor),
+                    display=display,
+                    display_meta=display_meta,
+                )