Repository: Textualize/rich
Pull request #2346 (2022-06-15 20:01:05)

Fixed Style hash
Fixes a performance bug in the Style class.

Essentially the hash calculation was inconsistent. Things that were equal would sometimes have different hashes. I noticed this when adding `lru_cache` to `Style.__add__`. What should have been an easy win caused dramatically reduced performance, because it broken the mechanics of storing Styles in a dict.

The hashing is now in once place. It is also lazy, so the hash is stored the first time it is used.


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 88e04594..24306ba8 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -14,6 +14,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - Allow exceptions that are raised while a Live is rendered to be displayed and/or processed https://github.com/Textualize/rich/pull/2305
 - Fix crashes that can happen with `inspect` when docstrings contain some special control codes https://github.com/Textualize/rich/pull/2294
 - Fix edges used in first row of tables when `show_header=False` https://github.com/Textualize/rich/pull/2330
+- Fixed hash issue in Styles class https://github.com/Textualize/rich/pull/2346
 
 ## [12.4.4] - 2022-05-24
 
diff --git a/rich/_lru_cache.py b/rich/_lru_cache.py
index a2278943..46e775f0 100644
--- a/rich/_lru_cache.py
+++ b/rich/_lru_cache.py
@@ -1,38 +1,116 @@
-from typing import Dict, Generic, TypeVar, TYPE_CHECKING
-import sys
+from threading import Lock
+from typing import Dict, Generic, List, Optional, TypeVar, Union, overload
 
 CacheKey = TypeVar("CacheKey")
 CacheValue = TypeVar("CacheValue")
+DefaultValue = TypeVar("DefaultValue")
 
-if sys.version_info < (3, 9):
-    from typing_extensions import OrderedDict
-else:
-    from collections import OrderedDict
 
-
-class LRUCache(OrderedDict[CacheKey, CacheValue]):
+class LRUCache(Generic[CacheKey, CacheValue]):
     """
     A dictionary-like container that stores a given maximum items.
 
     If an additional item is added when the LRUCache is full, the least
     recently used key is discarded to make room for the new item.
 
+    The implementation is similar to functools.lru_cache, which uses a linked
+    list to keep track of the most recently used items.
+
+    Each entry is stored as [PREV, NEXT, KEY, VALUE] where PREV is a reference
+    to the previous entry, and NEXT is a reference to the next value.
+
     """
 
-    def __init__(self, cache_size: int) -> None:
-        self.cache_size = cache_size
+    def __init__(self, maxsize: int) -> None:
+        self.maxsize = maxsize
+        self.cache: Dict[CacheKey, List[object]] = {}
+        self.full = False
+        self.root: List[object] = []
+        self._lock = Lock()
         super().__init__()
 
-    def __setitem__(self, key: CacheKey, value: CacheValue) -> None:
-        """Store a new views, potentially discarding an old value."""
-        if key not in self:
-            if len(self) >= self.cache_size:
-                self.popitem(last=False)
-        super().__setitem__(key, value)
+    def __len__(self) -> int:
+        return len(self.cache)
+
+    def set(self, key: CacheKey, value: CacheValue) -> None:
+        """Set a value.
+
+        Args:
+            key (CacheKey): Key.
+            value (CacheValue): Value.
+        """
+        with self._lock:
+            link = self.cache.get(key)
+            if link is None:
+                root = self.root
+                if not root:
+                    self.root[:] = [self.root, self.root, key, value]
+                else:
+                    self.root = [root[0], root, key, value]
+                    root[0][1] = self.root  # type: ignore[index]
+                    root[0] = self.root
+                self.cache[key] = self.root
+
+                if self.full or len(self.cache) > self.maxsize:
+                    self.full = True
+                    root = self.root
+                    last = root[0]
+                    last[0][1] = root  # type: ignore[index]
+                    root[0] = last[0]  # type: ignore[index]
+                    del self.cache[last[2]]  # type: ignore[index]
+
+    __setitem__ = set
+
+    @overload
+    def get(self, key: CacheKey) -> Optional[CacheValue]:
+        ...
+
+    @overload
+    def get(
+        self, key: CacheKey, default: DefaultValue
+    ) -> Union[CacheValue, DefaultValue]:
+        ...
+
+    def get(
+        self, key: CacheKey, default: Optional[DefaultValue] = None
+    ) -> Union[CacheValue, Optional[DefaultValue]]:
+        """Get a value from the cache, or return a default if the key is not present.
+
+        Args:
+            key (CacheKey): Key
+            default (Optional[DefaultValue], optional): Default to return if key is not present. Defaults to None.
+
+        Returns:
+            Union[CacheValue, Optional[DefaultValue]]: Either the value or a default.
+        """
+        link = self.cache.get(key)
+        if link is None:
+            return default
+        if link is not self.root:
+            with self._lock:
+                link[0][1] = link[1]  # type: ignore[index]
+                link[1][0] = link[0]  # type: ignore[index]
+                root = self.root
+                link[0] = root[0]
+                link[1] = root
+                root[0][1] = link  # type: ignore[index]
+                root[0] = link
+                self.root = link
+        return link[3]  # type: ignore[return-value]
 
     def __getitem__(self, key: CacheKey) -> CacheValue:
-        """Gets the item, but also makes it most recent."""
-        value: CacheValue = super().__getitem__(key)
-        super().__delitem__(key)
-        super().__setitem__(key, value)
-        return value
+        link = self.cache[key]
+        if link is not self.root:
+            with self._lock:
+                link[0][1] = link[1]  # type: ignore[index]
+                link[1][0] = link[0]  # type: ignore[index]
+                root = self.root
+                link[0] = root[0]
+                link[1] = root
+                root[0][1] = link  # type: ignore[index]
+                root[0] = link
+                self.root = link
+        return link[3]  # type: ignore[return-value]
+
+    def __contains__(self, key: CacheKey) -> bool:
+        return key in self.cache
diff --git a/rich/cells.py b/rich/cells.py
index 834c3710..77cae8c2 100644
--- a/rich/cells.py
+++ b/rich/cells.py
@@ -1,6 +1,6 @@
 import re
 from functools import lru_cache
-from typing import Dict, List
+from typing import List
 
 from ._cell_widths import CELL_WIDTHS
 from ._lru_cache import LRUCache
@@ -9,7 +9,7 @@ from ._lru_cache import LRUCache
 _is_single_cell_widths = re.compile("^[\u0020-\u006f\u00a0\u02ff\u0370-\u0482]*$").match
 
 
-def cell_len(text: str, _cache: Dict[str, int] = LRUCache(1024 * 4)) -> int:
+def cell_len(text: str, _cache: LRUCache[str, int] = LRUCache(1024 * 4)) -> int:
     """Get the number of cells required to display text.
 
     Args:
diff --git a/rich/style.py b/rich/style.py
index 17b1ace8..c4b43282 100644
--- a/rich/style.py
+++ b/rich/style.py
@@ -2,9 +2,10 @@ import sys
 from functools import lru_cache
 from marshal import dumps, loads
 from random import randint
-from typing import Any, Dict, Iterable, List, Optional, Type, Union, cast
+from typing import Any, Dict, Iterable, List, Optional, Tuple, Type, Union, cast
 
 from . import errors
+from ._lru_cache import LRUCache
 from .color import Color, ColorParseError, ColorSystem, blend_rgb
 from .repr import Result, rich_repr
 from .terminal_theme import DEFAULT_TERMINAL_THEME, TerminalTheme
@@ -59,7 +60,7 @@ class Style:
     _bgcolor: Optional[Color]
     _attributes: int
     _set_attributes: int
-    _hash: int
+    _hash: Optional[int]
     _null: bool
     _meta: Optional[bytes]
 
@@ -119,6 +120,9 @@ class Style:
         "o": "overline",
     }
 
+    # Caches results of Style.__add__
+    _add_cache: LRUCache[Tuple["Style", Optional["Style"]], "Style"] = LRUCache(1024)
+
     def __init__(
         self,
         *,
@@ -190,16 +194,7 @@ class Style:
         self._link = link
         self._link_id = f"{randint(0, 999999)}" if link else ""
         self._meta = None if meta is None else dumps(meta)
-        self._hash = hash(
-            (
-                self._color,
-                self._bgcolor,
-                self._attributes,
-                self._set_attributes,
-                link,
-                self._meta,
-            )
-        )
+        self._hash: Optional[int] = None
         self._null = not (self._set_attributes or color or bgcolor or link or meta)
 
     @classmethod
@@ -227,17 +222,8 @@ class Style:
         style._link = None
         style._link_id = ""
         style._meta = None
-        style._hash = hash(
-            (
-                color,
-                bgcolor,
-                None,
-                None,
-                None,
-                None,
-            )
-        )
         style._null = not (color or bgcolor)
+        style._hash = None
         return style
 
     @classmethod
@@ -257,16 +243,7 @@ class Style:
         style._link = None
         style._link_id = ""
         style._meta = dumps(meta)
-        style._hash = hash(
-            (
-                None,
-                None,
-                None,
-                None,
-                None,
-                style._meta,
-            )
-        )
+        style._hash = None
         style._null = not (meta)
         return style
 
@@ -366,6 +343,7 @@ class Style:
         Returns:
             str: String containing codes.
         """
+
         if self._ansi is None:
             sgr: List[str] = []
             append = sgr.append
@@ -446,16 +424,26 @@ class Style:
     def __eq__(self, other: Any) -> bool:
         if not isinstance(other, Style):
             return NotImplemented
-        return (
-            self._color == other._color
-            and self._bgcolor == other._bgcolor
-            and self._set_attributes == other._set_attributes
-            and self._attributes == other._attributes
-            and self._link == other._link
-            and self._meta == other._meta
-        )
+        return self.__hash__() == other.__hash__()
+
+    def __ne__(self, other: Any) -> bool:
+        if not isinstance(other, Style):
+            return NotImplemented
+        return self.__hash__() != other.__hash__()
 
     def __hash__(self) -> int:
+        if self._hash is not None:
+            return self._hash
+        self._hash = hash(
+            (
+                self._color,
+                self._bgcolor,
+                self._attributes,
+                self._set_attributes,
+                self._link,
+                self._meta,
+            )
+        )
         return self._hash
 
     @property
@@ -502,9 +490,9 @@ class Style:
         style._set_attributes = self._set_attributes
         style._link = self._link
         style._link_id = f"{randint(0, 999999)}" if self._link else ""
-        style._hash = self._hash
         style._null = False
         style._meta = None
+        style._hash = None
         return style
 
     @classmethod
@@ -677,7 +665,7 @@ class Style:
         style._set_attributes = self._set_attributes
         style._link = link
         style._link_id = f"{randint(0, 999999)}" if link else ""
-        style._hash = self._hash
+        style._hash = None
         style._null = False
         style._meta = self._meta
         return style
@@ -700,7 +688,7 @@ class Style:
         """
         if not text or color_system is None:
             return text
-        attrs = self._make_ansi_codes(color_system)
+        attrs = self._ansi or self._make_ansi_codes(color_system)
         rendered = f"\x1b[{attrs}m{text}\x1b[0m" if attrs else text
         if self._link and not legacy_windows:
             rendered = (
@@ -721,6 +709,10 @@ class Style:
         sys.stdout.write(f"{self.render(text)}\n")
 
     def __add__(self, style: Optional["Style"]) -> "Style":
+        cache_key = (self, style)
+        cached_style = self._add_cache.get(cache_key)
+        if cached_style is not None:
+            return cached_style.copy() if cached_style.link else cached_style
         if not (isinstance(style, Style) or style is None):
             return NotImplemented
         if style is None or style._null:
@@ -738,12 +730,13 @@ class Style:
         new_style._set_attributes = self._set_attributes | style._set_attributes
         new_style._link = style._link or self._link
         new_style._link_id = style._link_id or self._link_id
-        new_style._hash = style._hash
         new_style._null = style._null
         if self._meta and style._meta:
             new_style._meta = dumps({**self.meta, **style.meta})
         else:
             new_style._meta = self._meta or style._meta
+        new_style._hash = None
+        self._add_cache[cache_key] = new_style
         return new_style
 
 


Test patch:
diff --git a/tests/test_lrucache.py b/tests/test_lrucache.py
index 3cb1e298..76ba5a67 100644
--- a/tests/test_lrucache.py
+++ b/tests/test_lrucache.py
@@ -1,6 +1,5 @@
 from __future__ import unicode_literals
 
-
 from rich._lru_cache import LRUCache
 
 
@@ -12,18 +11,49 @@ def test_lru_cache():
     cache["bar"] = 2
     cache["baz"] = 3
     assert "foo" in cache
+    assert "bar" in cache
+    assert "baz" in cache
 
     #  Cache size is 3, so the following should kick oldest one out
     cache["egg"] = 4
     assert "foo" not in cache
-    assert "egg" in "egg" in cache
+    assert "egg" in cache
 
     # cache is now full
     # look up two keys
     cache["bar"]
     cache["baz"]
 
+    # Insert a new value
+    cache["eggegg"] = 5
+    assert len(cache) == 3
+    # Check it kicked out the 'oldest' key
+    assert "egg" not in cache
+    assert "eggegg" in cache
+
+
+def test_lru_cache_get():
+    cache = LRUCache(3)
+
+    # insert some values
+    cache["foo"] = 1
+    cache["bar"] = 2
+    cache["baz"] = 3
+    assert "foo" in cache
+
+    #  Cache size is 3, so the following should kick oldest one out
+    cache["egg"] = 4
+    # assert len(cache) == 3
+    assert cache.get("foo") is None
+    assert "egg" in cache
+
+    # cache is now full
+    # look up two keys
+    cache.get("bar")
+    cache.get("baz")
+
     # Insert a new value
     cache["eggegg"] = 5
     # Check it kicked out the 'oldest' key
     assert "egg" not in cache
+    assert "eggegg" in cache