Repository: amjith/fuzzyfinder

Issue:
Highlighting feature
Hi, first of all, let me tell you the code of your library is really cool because of the simplicity!

Now, I was wondering if you knew how to modify it slightly so the results would be highlighted like SublimeText, TextMate or similars...

To see what I mean take a look to [fuzzysort](https://github.com/farzher/fuzzysort):

![showcase](https://camo.githubusercontent.com/0b1900060c81f156ba40325249e4aec60eb70507/687474703a2f2f692e696d6775722e636f6d2f314d365a7267532e676966)

which has an interface such as:

    /*
    WHAT: SublimeText-like Fuzzy Search
    USAGE:
      fuzzysort.single('fs', 'Fuzzy Search') // {score: -16}
      fuzzysort.single('test', 'test') // {score: 0}
      fuzzysort.single('doesnt exist', 'target') // null
      fuzzysort.go('mr', ['Monitor.cpp', 'MeshRenderer.cpp'])
      // [{score: -18, target: "MeshRenderer.cpp"}, {score: -6009, target: "Monitor.cpp"}]
      fuzzysort.highlight(fuzzysort.single('fs', 'Fuzzy Search'), '<b>', '</b>')
      // <b>F</b>uzzy <b>S</b>earch
    */

So, any ideas how to add a "highlight" feature?

Discussion:
@nacezavrtanik: Solution
--------
First, notice that the highlighting need not be connected to the fuzzyfinder itself. To get the highlighting functionality, it would therefore suffice to define a function which highlights a given substring in an iterable, which can then be used on the fuzzyfinder results. The highlighting of strings is achieved by prepending and appending to the given substring certain special strings, where the prepended string activates a certain style and the appended string deactivates it. For instance, you can use [ANSI escape codes](https://en.wikipedia.org/wiki/ANSI_escape_code
) for printing highlighted strings to the terminal, or [HTML tags](
https://www.w3schools.com/tags/ref_byfunc.asp
) for displaying highlighted strings in the browser (like in the **fuzzysort** example you provided).

~~~python
def highlight_substring(substring, collection, highlight):
    """Highlight first occurrences of substring in elements of collection.

    Args:
        substring (str): Substring to highlight.
        collection (iterable): Iterable of strings in which to highlight substring.
        highlight (tuple): Tuple of strings, where the first element activates
                           a style and the second element deactivates it.

    Yields:
        String from collection, with first occurrence of substring surrounded
        by highlight strings.
    """
    style, reset_style = highlight
    for item in collection:
        highlighted_item = ""
        substring_iter = iter(substring)
        take_next = True
        for item_char in item:
            if take_next:
                try:
                    substring_char = next(substring_iter)
                except StopIteration:
                    substring_char = "I am not equal to any single character"
                else:
                    take_next = False
            if item_char.lower() == substring_char.lower():
                highlighted_item += style + item_char + reset_style
                take_next = True
            else:
                highlighted_item += item_char
        yield highlighted_item
~~~

Now, you may want to create a wrapper function around `highlight_substring` and `fuzzyfinder` to obtain a fuzzyfinder with the highlighting functionality built in. Notice that `highlight_substring` is actually a generator function, which makes the wrapper have a consistent return type.

~~~python
from fuzzyfinder import fuzzyfinder

def highlighting_fuzzyfinder(
    input, collection, accessor=lambda x: x, sort_results=True, highlight=None
):
    """Find strings matching input, and maybe highlight matching substring."""
    results = fuzzyfinder(
        input, collection, accessor=accessor, sort_results=sort_results
    )
    if highlight:
        return highlight_substring(input, results, highlight)
    else:
        return results
~~~

Usage
-----
It should prove convenient to define some constants with the special styling strings. Here, I organized the constants into classes, but plain old strings will do as well.

~~~python
class ANSI:
    """ANSI escape codes for styling."""
    RESET_STYLE = "\033[0m"
    BOLD = "\033[1m"
    UNDERLINE = "\033[4m"
    GREEN = "\033[32m"
    GREEN_BG = "\033[42m"

class HTML:
    """HTML tags for styling."""
    BOLD = "<b>"
    RESET_BOLD = "</b>"
    GREEN_BG = "<mark style='background:#00FF00'>"
    RESET_GREEN_BG = "</mark>"
~~~

Here are some highlighted matches printed to the terminal:
![Screenshot from 2024-08-30 21-36-41](https://github.com/user-attachments/assets/85e9dff5-ae5c-4f27-a614-613829d45f32)

Here are some highlighted matches displayed in the browser:
![Screenshot from 2024-08-30 21-36-16](https://github.com/user-attachments/assets/c20f85d5-8d64-44fa-8eb0-181af9f8ced6)
![Screenshot from 2024-08-30 21-18-33](https://github.com/user-attachments/assets/663bbb5c-81a3-4150-8ad5-4f13f98dd702)

---
*Tested in Python 3.11.*


Solution patch:
diff --git a/README.rst b/README.rst
index 07bc5e2..1d93799 100644
--- a/README.rst
+++ b/README.rst
@@ -78,6 +78,18 @@ Usage
     >>> list(suggestions)
     ['aac', 'aaa', 'aab', 'ada']
 
+    >>> # Highlight matching substrings when printing to the terminal
+    >>> collection = ['apple', 'banana', 'grape', 'orange', 'pineapple']
+    >>> suggestions = fuzzyfinder('ape', collection, highlight=True)
+    >>> list(suggestions)
+    ['gr\x1b[42mape\x1b[0m', '\x1b[42map\x1b[0mpl\x1b[42me\x1b[0m', 'pine\x1b[42map\x1b[0mpl\x1b[42me\x1b[0m']
+
+    >>> # Custom highlighting (use with ANSI, HTML, etc.)
+    >>> parentheses = '(', ')'
+    >>> suggestions = fuzzyfinder('ape', collection, highlight=parentheses)
+    >>> list(suggestions)
+    ['gr(ape)', '(ap)pl(e)', 'pine(ap)pl(e)']
+
 Similar Projects
 ----------------
 
diff --git a/docs/usage.rst b/docs/usage.rst
index 959c229..c0f3fca 100644
--- a/docs/usage.rst
+++ b/docs/usage.rst
@@ -22,8 +22,8 @@ necessarily adjacent to each other.
     >>> list(suggestions)
     ['abcd', 'defabca', 'aagbec']
 
-Customized matching
--------------------
+Custom matching
+---------------
 
 By passing the :code:`accessor` keyword argument, you can influence how the
 fuzzy matching is done. The accessor must be a function which returns a string.
@@ -31,8 +31,8 @@ This accessor function is used on each element of the collection, with the
 resulting strings being used for the fuzzy matching instead of the original
 elements.
 
-Customized string matching
-^^^^^^^^^^^^^^^^^^^^^^^^^^
+Custom string matching
+^^^^^^^^^^^^^^^^^^^^^^
 
 Only use the second word of the string for matching.
 
@@ -94,3 +94,78 @@ to the :code:`sort_results` keyword argument.
     >>> list(suggestions)
     ['aac', 'aaa', 'aba', 'ada']
 
+Highlighting matches
+--------------------
+
+When displaying fuzzyfinder's suggestions, it is often convenient do visually
+emphasize the matched substring within each suggestion. You can control such
+behavior with the :code:`highlight` keyword argment.
+
+.. note::
+   Highlighting only works for collections of strings.
+
+Highlighting in the terminal
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+In the terminal, characters are highlighted using ANSI escape codes. They are
+inserted into individual suggestion strings, and are rendered as colors when
+the string is printed.
+
+By passing :literal:`True` to the :code:`highlight` keyword argument, the
+matching substring will be highlighted in the default color (*green*).
+
+.. code:: python
+
+    >>> collection = ['apple', 'banana', 'grape', 'orange', 'pineapple']
+    >>> suggestions = fuzzyfinder('ape', collection, highlight=True)
+    >>> # Print individual elements to render highlights
+    >>> list(suggestions)
+    ['gr\x1b[42mape\x1b[0m', '\x1b[42map\x1b[0mpl\x1b[42me\x1b[0m', 'pine\x1b[42map\x1b[0mpl\x1b[42me\x1b[0m']
+
+Alternatively, you can pass a string argument, which will apply highlights of
+the corresponding color. Accepted values are ``'red'``, ``'green'``,
+``'yellow'``, ``'blue'``, ``'magenta'``, and ``'cyan'``.
+
+For more flexibility, see the next subsection.
+
+Custom highlighting
+^^^^^^^^^^^^^^^^^^^
+
+You can apply custom highlighting by passing to the :code:`highlight` keyword
+argument, as a :code:`tuple`, a prefix-suffix pair. The prefix and suffix are
+prepended and appended to contiguous matching substring chunks, and can range
+from anything like parentheses or ANSI escape codes to HTML tags with class or
+style attributes.
+
+Parentheses
+"""""""""""
+
+.. code:: python
+
+    >>> collection = ['apple', 'banana', 'grape', 'orange', 'pineapple']
+    >>> parentheses = '(', ')'
+    >>> suggestions = fuzzyfinder('ape', collection, highlight=parentheses)
+    >>> list(suggestions)
+    ['gr(ape)', '(ap)pl(e)', 'pine(ap)pl(e)']
+
+ANSI
+""""
+
+.. code:: python
+
+    >>> collection = ['apple', 'banana', 'grape', 'orange', 'pineapple']
+    >>> bold_with_peach_bg = "\033[48;5;209m\033[1m", "\033[0m"
+    >>> suggestions = fuzzyfinder('ape', collection, highlight=bold_with_peach_bg)
+    >>> list(suggestions)
+    ['gr\x1b[48;5;209m\x1b[1mape\x1b[0m', '\x1b[48;5;209m\x1b[1map\x1b[0mpl\x1b[48;5;209m\x1b[1me\x1b[0m', 'pine\x1b[48;5;209m\x1b[1map\x1b[0mpl\x1b[48;5;209m\x1b[1me\x1b[0m']
+
+HTML
+""""
+
+.. code:: python
+
+    >>> collection = ['apple', 'banana', 'grape', 'orange', 'pineapple']
+    >>> html_class = '<span class="highlight">', '</span>'
+    >>> suggestions = fuzzyfinder('ape', collection, highlight=html_class)
+    >>> list(suggestions)
+    ['gr<span class="highlight">ape</span>', '<span class="highlight">ap</span>pl<span class="highlight">e</span>', 'pine<span class="highlight">ap</span>pl<span class="highlight">e</span>']
diff --git a/fuzzyfinder/main.py b/fuzzyfinder/main.py
index a3518b6..b72cc06 100755
--- a/fuzzyfinder/main.py
+++ b/fuzzyfinder/main.py
@@ -1,12 +1,83 @@
 # -*- coding: utf-8 -*-
-from typing import Iterable, Iterator, Callable, Any
+from typing import Any, Callable, Iterable, Iterator, Tuple, Union
 import re
 from . import export
 
 
+COLORS_TO_ANSI = {
+    "red": "\033[41m",
+    "green": "\033[42m",
+    "yellow": "\033[43m",
+    "blue": "\033[44m",
+    "magenta": "\033[45m",
+    "cyan": "\033[46m",
+}
+ANSI_RESET = "\033[0m"
+
+
+def highlight_substring(
+    substring: str,
+    string: str,
+    highlight: Union[bool, str, Tuple[str, str]],
+    ignore_case: bool,
+) -> str:
+    """Apply `highlight` to contiguous chunks of `substring` within `string`."""
+    assert highlight, "called function when 'highlight' was falsy"
+    default_highlight = "green"
+    if highlight is True:
+        highlight = default_highlight
+    if isinstance(highlight, str):
+        if not (ansi_code := COLORS_TO_ANSI.get(highlight.lower())):
+            raise ValueError(f"highlight, if a string, must be one of: {str(list(COLORS_TO_ANSI)).strip('[]')}")
+        highlight = ansi_code, ANSI_RESET
+    assert isinstance(highlight, tuple), "incorrect type for 'highlight'"
+
+    # We apply to the main string, pairwise, styling prefixes and suffixes
+    # which mark the matched substring. We iterate over both the main string
+    # and the substring exactly once, and make sure that prefix-suffix pairs
+    # wrap entire chunks of adjacent matched characters as opposed to each
+    # character individually.
+    prefix, suffix = highlight
+    highlighted_string = ""
+    # We use an iterator for iterating over the main string. This ensures that:
+    # (1) for each substring character, we start iteration where we stopped for
+    # the previous substring character;
+    # (2) after matching the final substring character, the remainder of the
+    # main string's characters is preserved within the iterator.
+    string_iter = iter(string)
+    unpaired_prefix = False
+    for substring_char in substring:
+        for string_char in string_iter:
+            match = string_char == substring_char
+            case_insensitive_match = string_char.lower() == substring_char.lower()
+            if match or (ignore_case and case_insensitive_match):
+                if not unpaired_prefix:
+                    highlighted_string += prefix
+                    unpaired_prefix = True
+                highlighted_string += string_char
+                break
+            else:
+                if unpaired_prefix:
+                    highlighted_string += suffix
+                    unpaired_prefix = False
+                highlighted_string += string_char
+    # If the final match is between the last characters of both strings,
+    # a prefix is left unpaired, so we check for it here.
+    if unpaired_prefix:
+        highlighted_string += suffix
+    remainder = "".join(string_iter)
+    highlighted_string += remainder
+    return highlighted_string
+
+
 @export
 def fuzzyfinder(
-    input: str, collection: Iterable[Any], accessor: Callable[[Any], str] = lambda x: x, sort_results: bool = True, ignore_case: bool = True
+    input: str,
+    collection: Iterable[Any],
+    accessor: Callable[[Any], str] = lambda x: x,
+    sort_results: bool = True,
+    ignore_case: bool = True,
+    highlight: Union[bool, str, Tuple[str, str]] = False,
 ) -> Iterator[Any]:
     """Filter a collection of objects by fuzzy matching against an input string.
 
@@ -34,6 +105,21 @@ def fuzzyfinder(
             If this parameter is set to ``False``, the filtering is
             case-sensitive.
             Defaults to ``True``.
+        highlight:
+            Highlight the matching substrings when printed to the terminal, or
+            elsewhere.
+            If ``True``, when printed to the terminal, the matching substrings
+            will have the default highlight (*green*).
+            If this parameter is a ``str``, when printed to the terminal, the
+            matching substrings will be highlighted in the corresponding color.
+            Accepted values are: ``'red'``, ``'green'``, ``'yellow'``,
+            ``'blue'``, ``'magenta'``, and ``'cyan'``.
+            If this parameter is a ``tuple``, it must be a 2-tuple consisting
+            of a prefix and a suffix string. The prefix and suffix are
+            prepended  and appended to contiguous substring chunks, and can
+            range from anything like parentheses or ANSI escape codes to HTML
+            tags with class or style attributes.
+            Defaults to ``False``.
 
     Returns:
         Iterator[Any]:
@@ -57,6 +143,11 @@ def fuzzyfinder(
             suggestions.append((len(best.group(1)), best.start(), accessor(item), item))
 
     if sort_results:
-        return (z[-1] for z in sorted(suggestions))
+        results = (z[-1] for z in sorted(suggestions))
     else:
-        return (z[-1] for z in sorted(suggestions, key=lambda x: x[:2]))
+        results = (z[-1] for z in sorted(suggestions, key=lambda x: x[:2]))
+
+    if highlight:
+        results = (highlight_substring(input, result, highlight, ignore_case) for result in results)
+
+    return results


Test patch:
diff --git a/tests/test_fuzzyfinder.py b/tests/test_fuzzyfinder.py
index f62a942..8b7d723 100755
--- a/tests/test_fuzzyfinder.py
+++ b/tests/test_fuzzyfinder.py
@@ -52,6 +52,11 @@ def dict_collection():
     ]
 
 
+@pytest.fixture
+def highlighting_collection():
+    return ["fuuz", "fuz", "fufuz", "afbcfdzeuffzhijkl", "python"]
+
+
 def test_substring_match(collection):
     text = "txt"
     results = fuzzyfinder(text, collection)
@@ -129,3 +134,75 @@ def test_no_alpha_num_sort():
     results = fuzzyfinder(text, collection, sort_results=False)
     expected = ["zzfuz", "nnfuz", "aafuz", "ttfuz"]
     assert list(results) == expected
+
+
+def test_highlight_boolean_input(highlighting_collection):
+    text = "fuz"
+    results = fuzzyfinder(text, highlighting_collection, highlight=True)
+    expected = [
+        "\033[42mfuz\033[0m",
+        "\033[42mfu\033[0mfu\033[42mz\033[0m",
+        "\033[42mfu\033[0mu\033[42mz\033[0m",
+        "a\033[42mf\033[0mbcfdze\033[42mu\033[0mff\033[42mz\033[0mhijkl",
+    ]
+    assert list(results) == expected
+
+
+@pytest.mark.parametrize(
+    ("color", "ansi_code"),
+    [
+        ("red", "\033[41m"),
+        ("green", "\033[42m"),
+        ("yellow", "\033[43m"),
+        ("blue", "\033[44m"),
+        ("magenta", "\033[45m"),
+        ("cyan", "\033[46m"),
+    ],
+)
+def test_highlight_string_input(highlighting_collection, color, ansi_code):
+    text = "fuz"
+    results = fuzzyfinder(text, highlighting_collection, highlight=color)
+    expected = [
+        f"{ansi_code}fuz\033[0m",
+        f"{ansi_code}fu\033[0mfu{ansi_code}z\033[0m",
+        f"{ansi_code}fu\033[0mu{ansi_code}z\033[0m",
+        f"a{ansi_code}f\033[0mbcfdze{ansi_code}u\033[0mff{ansi_code}z\033[0mhijkl",
+    ]
+    assert list(results) == expected
+
+
+def test_highlight_ansi_tuple_input(highlighting_collection):
+    text = "fuz"
+    bold_with_peach_bg = "\033[48;5;209m\033[1m", "\033[0m"
+    results = fuzzyfinder(text, highlighting_collection, highlight=bold_with_peach_bg)
+    expected = [
+        "\033[48;5;209m\033[1mfuz\033[0m",
+        "\033[48;5;209m\033[1mfu\033[0mfu\033[48;5;209m\033[1mz\033[0m",
+        "\033[48;5;209m\033[1mfu\033[0mu\033[48;5;209m\033[1mz\033[0m",
+        "a\033[48;5;209m\033[1mf\033[0mbcfdze\033[48;5;209m\033[1mu\033[0mff\033[48;5;209m\033[1mz\033[0mhijkl",
+    ]
+    assert list(results) == expected
+
+
+def test_highlight_html_tuple_input(highlighting_collection):
+    text = "fuz"
+    html_class = "<span class='highlight'>", "</span>"
+    results = fuzzyfinder(text, highlighting_collection, highlight=html_class)
+    expected = [
+        "<span class='highlight'>fuz</span>",
+        "<span class='highlight'>fu</span>fu<span class='highlight'>z</span>",
+        "<span class='highlight'>fu</span>u<span class='highlight'>z</span>",
+        "a<span class='highlight'>f</span>bcfdze<span class='highlight'>u</span>ff<span class='highlight'>z</span>hijkl",
+    ]
+    assert list(results) == expected
+
+
+def test_highlight_case_sensitive(cased_collection):
+    text = "mi"
+    parentheses = "(", ")"
+    results = fuzzyfinder(text, cased_collection, ignore_case=False, highlight=parentheses)
+    expected = [
+        "(mi)grations.doc",
+        "django_ad(mi)n_log.py",
+    ]
+    assert list(results) == expected