We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
pants.util.frozendict.FrozenDict has error prone order-sensitive comparisons
**Describe the bug**

The `FrozenDict` type is order sensitive, which differs to a normal `dict`. It also gives `False` when comparing to a normal dict. This makes it easy to get unexpected behaviour, and likely leads to unnecessary cache misses.

https://github.com/pantsbuild/pants/blob/57d1801c80f8273ca386fba198495a05a45f60ae/src/python/pants/util/frozendict.py#L15-L21

```python
d1 = {'a': 0, 'b': 1}
d2 = {'b': 1, 'a': 0}
print(d1 == d2) # True
print(FrozenDict(d1) == FrozenDict(d2)) # False

print(FrozenDict(d1) == d1) # False
```

NB. this seems to apply to all methods that call `tuple(self.items())` or similar: `__eq__`, `__lt__`, `_calculate_hash`/`__hash__`.

**Pants version**

`main`

**OS**

N/A

**Additional info**

This caused half of #20210, see #20220.

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `src/python/pants/util/frozendict.py`
Content:
```
1 # Copyright 2020 Pants project contributors (see CONTRIBUTORS.md).
2 # Licensed under the Apache License, Version 2.0 (see LICENSE).
3 
4 from __future__ import annotations
5 
6 from typing import Any, Callable, Iterable, Iterator, Mapping, TypeVar, cast, overload
7 
8 from pants.util.memo import memoized_method
9 from pants.util.strutil import softwrap
10 
11 K = TypeVar("K")
12 V = TypeVar("V")
13 
14 
15 class FrozenDict(Mapping[K, V]):
16     """A wrapper around a normal `dict` that removes all methods to mutate the instance and that
17     implements __hash__.
18 
19     This should be used instead of normal dicts when working with the engine because normal dicts
20     are not safe to use.
21     """
22 
23     @overload
24     def __init__(self, __items: Iterable[tuple[K, V]], **kwargs: V) -> None:
25         ...
26 
27     @overload
28     def __init__(self, __other: Mapping[K, V], **kwargs: V) -> None:
29         ...
30 
31     @overload
32     def __init__(self, **kwargs: V) -> None:
33         ...
34 
35     def __init__(self, *item: Mapping[K, V] | Iterable[tuple[K, V]], **kwargs: V) -> None:
36         """Creates a `FrozenDict` with arguments accepted by `dict` that also must be hashable."""
37         if len(item) > 1:
38             raise ValueError(
39                 f"{type(self).__name__} was called with {len(item)} positional arguments but it expects one."
40             )
41 
42         # NB: Keep the variable name `_data` in sync with `externs/mod.rs`.
43         self._data = dict(item[0]) if item else dict()
44         self._data.update(**kwargs)
45 
46         # NB: We eagerly compute the hash to validate that the values are hashable and to avoid
47         # performing the calculation multiple times. This can be revisited if it's found to be a
48         # performance bottleneck.
49         self._hash = self._calculate_hash()
50 
51     @classmethod
52     def deep_freeze(cls, data: Mapping[K, V]) -> FrozenDict[K, V]:
53         """Convert mutable values to their frozen counter parts.
54 
55         Sets and lists are turned into tuples and dicts into FrozenDicts.
56         """
57 
58         def _freeze(obj):
59             if isinstance(obj, dict):
60                 return cls.deep_freeze(obj)
61             if isinstance(obj, (list, set)):
62                 return tuple(map(_freeze, obj))
63             return obj
64 
65         return cls({k: _freeze(v) for k, v in data.items()})
66 
67     @staticmethod
68     def frozen(to_freeze: Mapping[K, V]) -> FrozenDict[K, V]:
69         """Returns a `FrozenDict` containing the keys and values of `to_freeze`.
70 
71         If `to_freeze` is already a `FrozenDict`, returns the same object.
72         """
73 
74         return to_freeze if isinstance(to_freeze, FrozenDict) else FrozenDict(to_freeze)
75 
76     def __getitem__(self, k: K) -> V:
77         return self._data[k]
78 
79     def __len__(self) -> int:
80         return len(self._data)
81 
82     def __iter__(self) -> Iterator[K]:
83         return iter(self._data)
84 
85     def __reversed__(self) -> Iterator[K]:
86         return reversed(tuple(self._data))
87 
88     def __eq__(self, other: Any) -> bool:
89         if not isinstance(other, FrozenDict):
90             return NotImplemented
91         return tuple(self.items()) == tuple(other.items())
92 
93     def __lt__(self, other: Any) -> bool:
94         if not isinstance(other, FrozenDict):
95             return NotImplemented
96         return tuple(self._data.items()) < tuple(other._data.items())
97 
98     def _calculate_hash(self) -> int:
99         try:
100             return hash(tuple(self._data.items()))
101         except TypeError as e:
102             raise TypeError(
103                 softwrap(
104                     f"""
105                     Even though you are using a `{type(self).__name__}`, the underlying values are
106                     not hashable. Please use hashable (and preferably immutable) types for the
107                     underlying values, e.g. use tuples instead of lists and use FrozenOrderedSet
108                     instead of set().
109 
110                     Original error message: {e}
111 
112                     Value: {self}
113                     """
114                 )
115             )
116 
117     def __hash__(self) -> int:
118         return self._hash
119 
120     def __repr__(self) -> str:
121         return f"{type(self).__name__}({self._data!r})"
122 
123 
124 class LazyFrozenDict(FrozenDict[K, V]):
125     """A lazy version of `FrozenDict` where the values are not loaded until referenced."""
126 
127     @overload
128     def __init__(
129         self, __items: Iterable[tuple[K, Callable[[], V]]], **kwargs: Callable[[], V]
130     ) -> None:
131         ...
132 
133     @overload
134     def __init__(self, __other: Mapping[K, Callable[[], V]], **kwargs: Callable[[], V]) -> None:
135         ...
136 
137     @overload
138     def __init__(self, **kwargs: Callable[[], V]) -> None:
139         ...
140 
141     def __init__(
142         self,
143         *item: Mapping[K, Callable[[], V]] | Iterable[tuple[K, Callable[[], V]]],
144         **kwargs: Callable[[], V],
145     ) -> None:
146         super().__init__(*item, **kwargs)  # type: ignore[arg-type]
147 
148     def __getitem__(self, k: K) -> V:
149         return self._get_value(k)
150 
151     @memoized_method
152     def _get_value(self, k: K) -> V:
153         return cast("Callable[[], V]", self._data[k])()
154
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/src/python/pants/util/frozendict.py b/src/python/pants/util/frozendict.py
--- a/src/python/pants/util/frozendict.py
+++ b/src/python/pants/util/frozendict.py
@@ -85,19 +85,27 @@
     def __reversed__(self) -> Iterator[K]:
         return reversed(tuple(self._data))
 
-    def __eq__(self, other: Any) -> bool:
-        if not isinstance(other, FrozenDict):
-            return NotImplemented
-        return tuple(self.items()) == tuple(other.items())
+    def __eq__(self, other: Any) -> Any:
+        # defer to dict's __eq__
+        return self._data == other
 
     def __lt__(self, other: Any) -> bool:
         if not isinstance(other, FrozenDict):
             return NotImplemented
-        return tuple(self._data.items()) < tuple(other._data.items())
+        # If sorting each of these on every __lt__ call ends up being a problem we could consider
+        # optimising this, by, for instance, sorting on construction.
+        return sorted(self._data.items()) < sorted(other._data.items())
 
     def _calculate_hash(self) -> int:
         try:
-            return hash(tuple(self._data.items()))
+            h = 0
+            for pair in self._data.items():
+                # xor is commutative, i.e. we get the same hash no matter the order of items. This
+                # "relies" on "hash" of the individual elements being unpredictable enough that such
+                # a naive aggregation is okay. In addition, the Python hash isn't / shouldn't be
+                # used for cryptographically sensitive purposes.
+                h ^= hash(pair)
+            return h
         except TypeError as e:
             raise TypeError(
                 softwrap(

{"golden_diff": "diff --git a/src/python/pants/util/frozendict.py b/src/python/pants/util/frozendict.py\n--- a/src/python/pants/util/frozendict.py\n+++ b/src/python/pants/util/frozendict.py\n@@ -85,19 +85,27 @@\n     def __reversed__(self) -> Iterator[K]:\n         return reversed(tuple(self._data))\n \n-    def __eq__(self, other: Any) -> bool:\n-        if not isinstance(other, FrozenDict):\n-            return NotImplemented\n-        return tuple(self.items()) == tuple(other.items())\n+    def __eq__(self, other: Any) -> Any:\n+        # defer to dict's __eq__\n+        return self._data == other\n \n     def __lt__(self, other: Any) -> bool:\n         if not isinstance(other, FrozenDict):\n             return NotImplemented\n-        return tuple(self._data.items()) < tuple(other._data.items())\n+        # If sorting each of these on every __lt__ call ends up being a problem we could consider\n+        # optimising this, by, for instance, sorting on construction.\n+        return sorted(self._data.items()) < sorted(other._data.items())\n \n     def _calculate_hash(self) -> int:\n         try:\n-            return hash(tuple(self._data.items()))\n+            h = 0\n+            for pair in self._data.items():\n+                # xor is commutative, i.e. we get the same hash no matter the order of items. This\n+                # \"relies\" on \"hash\" of the individual elements being unpredictable enough that such\n+                # a naive aggregation is okay. In addition, the Python hash isn't / shouldn't be\n+                # used for cryptographically sensitive purposes.\n+                h ^= hash(pair)\n+            return h\n         except TypeError as e:\n             raise TypeError(\n                 softwrap(\n", "issue": "pants.util.frozendict.FrozenDict has error prone order-sensitive comparisons\n**Describe the bug**\r\n\r\nThe `FrozenDict` type is order sensitive, which differs to a normal `dict`. It also gives `False` when comparing to a normal dict. This makes it easy to get unexpected behaviour, and likely leads to unnecessary cache misses.\r\n\r\nhttps://github.com/pantsbuild/pants/blob/57d1801c80f8273ca386fba198495a05a45f60ae/src/python/pants/util/frozendict.py#L15-L21\r\n\r\n```python\r\nd1 = {'a': 0, 'b': 1}\r\nd2 = {'b': 1, 'a': 0}\r\nprint(d1 == d2) # True\r\nprint(FrozenDict(d1) == FrozenDict(d2)) # False\r\n\r\nprint(FrozenDict(d1) == d1) # False\r\n```\r\n\r\nNB. this seems to apply to all methods that call `tuple(self.items())` or similar: `__eq__`, `__lt__`, `_calculate_hash`/`__hash__`.\r\n\r\n**Pants version**\r\n\r\n`main`\r\n\r\n**OS**\r\n\r\nN/A\r\n\r\n**Additional info**\r\n\r\nThis caused half of #20210, see #20220.\n", "before_files": [{"content": "# Copyright 2020 Pants project contributors (see CONTRIBUTORS.md).\n# Licensed under the Apache License, Version 2.0 (see LICENSE).\n\nfrom __future__ import annotations\n\nfrom typing import Any, Callable, Iterable, Iterator, Mapping, TypeVar, cast, overload\n\nfrom pants.util.memo import memoized_method\nfrom pants.util.strutil import softwrap\n\nK = TypeVar(\"K\")\nV = TypeVar(\"V\")\n\n\nclass FrozenDict(Mapping[K, V]):\n    \"\"\"A wrapper around a normal `dict` that removes all methods to mutate the instance and that\n    implements __hash__.\n\n    This should be used instead of normal dicts when working with the engine because normal dicts\n    are not safe to use.\n    \"\"\"\n\n    @overload\n    def __init__(self, __items: Iterable[tuple[K, V]], **kwargs: V) -> None:\n        ...\n\n    @overload\n    def __init__(self, __other: Mapping[K, V], **kwargs: V) -> None:\n        ...\n\n    @overload\n    def __init__(self, **kwargs: V) -> None:\n        ...\n\n    def __init__(self, *item: Mapping[K, V] | Iterable[tuple[K, V]], **kwargs: V) -> None:\n        \"\"\"Creates a `FrozenDict` with arguments accepted by `dict` that also must be hashable.\"\"\"\n        if len(item) > 1:\n            raise ValueError(\n                f\"{type(self).__name__} was called with {len(item)} positional arguments but it expects one.\"\n            )\n\n        # NB: Keep the variable name `_data` in sync with `externs/mod.rs`.\n        self._data = dict(item[0]) if item else dict()\n        self._data.update(**kwargs)\n\n        # NB: We eagerly compute the hash to validate that the values are hashable and to avoid\n        # performing the calculation multiple times. This can be revisited if it's found to be a\n        # performance bottleneck.\n        self._hash = self._calculate_hash()\n\n    @classmethod\n    def deep_freeze(cls, data: Mapping[K, V]) -> FrozenDict[K, V]:\n        \"\"\"Convert mutable values to their frozen counter parts.\n\n        Sets and lists are turned into tuples and dicts into FrozenDicts.\n        \"\"\"\n\n        def _freeze(obj):\n            if isinstance(obj, dict):\n                return cls.deep_freeze(obj)\n            if isinstance(obj, (list, set)):\n                return tuple(map(_freeze, obj))\n            return obj\n\n        return cls({k: _freeze(v) for k, v in data.items()})\n\n    @staticmethod\n    def frozen(to_freeze: Mapping[K, V]) -> FrozenDict[K, V]:\n        \"\"\"Returns a `FrozenDict` containing the keys and values of `to_freeze`.\n\n        If `to_freeze` is already a `FrozenDict`, returns the same object.\n        \"\"\"\n\n        return to_freeze if isinstance(to_freeze, FrozenDict) else FrozenDict(to_freeze)\n\n    def __getitem__(self, k: K) -> V:\n        return self._data[k]\n\n    def __len__(self) -> int:\n        return len(self._data)\n\n    def __iter__(self) -> Iterator[K]:\n        return iter(self._data)\n\n    def __reversed__(self) -> Iterator[K]:\n        return reversed(tuple(self._data))\n\n    def __eq__(self, other: Any) -> bool:\n        if not isinstance(other, FrozenDict):\n            return NotImplemented\n        return tuple(self.items()) == tuple(other.items())\n\n    def __lt__(self, other: Any) -> bool:\n        if not isinstance(other, FrozenDict):\n            return NotImplemented\n        return tuple(self._data.items()) < tuple(other._data.items())\n\n    def _calculate_hash(self) -> int:\n        try:\n            return hash(tuple(self._data.items()))\n        except TypeError as e:\n            raise TypeError(\n                softwrap(\n                    f\"\"\"\n                    Even though you are using a `{type(self).__name__}`, the underlying values are\n                    not hashable. Please use hashable (and preferably immutable) types for the\n                    underlying values, e.g. use tuples instead of lists and use FrozenOrderedSet\n                    instead of set().\n\n                    Original error message: {e}\n\n                    Value: {self}\n                    \"\"\"\n                )\n            )\n\n    def __hash__(self) -> int:\n        return self._hash\n\n    def __repr__(self) -> str:\n        return f\"{type(self).__name__}({self._data!r})\"\n\n\nclass LazyFrozenDict(FrozenDict[K, V]):\n    \"\"\"A lazy version of `FrozenDict` where the values are not loaded until referenced.\"\"\"\n\n    @overload\n    def __init__(\n        self, __items: Iterable[tuple[K, Callable[[], V]]], **kwargs: Callable[[], V]\n    ) -> None:\n        ...\n\n    @overload\n    def __init__(self, __other: Mapping[K, Callable[[], V]], **kwargs: Callable[[], V]) -> None:\n        ...\n\n    @overload\n    def __init__(self, **kwargs: Callable[[], V]) -> None:\n        ...\n\n    def __init__(\n        self,\n        *item: Mapping[K, Callable[[], V]] | Iterable[tuple[K, Callable[[], V]]],\n        **kwargs: Callable[[], V],\n    ) -> None:\n        super().__init__(*item, **kwargs)  # type: ignore[arg-type]\n\n    def __getitem__(self, k: K) -> V:\n        return self._get_value(k)\n\n    @memoized_method\n    def _get_value(self, k: K) -> V:\n        return cast(\"Callable[[], V]\", self._data[k])()\n", "path": "src/python/pants/util/frozendict.py"}], "after_files": [{"content": "# Copyright 2020 Pants project contributors (see CONTRIBUTORS.md).\n# Licensed under the Apache License, Version 2.0 (see LICENSE).\n\nfrom __future__ import annotations\n\nfrom typing import Any, Callable, Iterable, Iterator, Mapping, TypeVar, cast, overload\n\nfrom pants.util.memo import memoized_method\nfrom pants.util.strutil import softwrap\n\nK = TypeVar(\"K\")\nV = TypeVar(\"V\")\n\n\nclass FrozenDict(Mapping[K, V]):\n    \"\"\"A wrapper around a normal `dict` that removes all methods to mutate the instance and that\n    implements __hash__.\n\n    This should be used instead of normal dicts when working with the engine because normal dicts\n    are not safe to use.\n    \"\"\"\n\n    @overload\n    def __init__(self, __items: Iterable[tuple[K, V]], **kwargs: V) -> None:\n        ...\n\n    @overload\n    def __init__(self, __other: Mapping[K, V], **kwargs: V) -> None:\n        ...\n\n    @overload\n    def __init__(self, **kwargs: V) -> None:\n        ...\n\n    def __init__(self, *item: Mapping[K, V] | Iterable[tuple[K, V]], **kwargs: V) -> None:\n        \"\"\"Creates a `FrozenDict` with arguments accepted by `dict` that also must be hashable.\"\"\"\n        if len(item) > 1:\n            raise ValueError(\n                f\"{type(self).__name__} was called with {len(item)} positional arguments but it expects one.\"\n            )\n\n        # NB: Keep the variable name `_data` in sync with `externs/mod.rs`.\n        self._data = dict(item[0]) if item else dict()\n        self._data.update(**kwargs)\n\n        # NB: We eagerly compute the hash to validate that the values are hashable and to avoid\n        # performing the calculation multiple times. This can be revisited if it's found to be a\n        # performance bottleneck.\n        self._hash = self._calculate_hash()\n\n    @classmethod\n    def deep_freeze(cls, data: Mapping[K, V]) -> FrozenDict[K, V]:\n        \"\"\"Convert mutable values to their frozen counter parts.\n\n        Sets and lists are turned into tuples and dicts into FrozenDicts.\n        \"\"\"\n\n        def _freeze(obj):\n            if isinstance(obj, dict):\n                return cls.deep_freeze(obj)\n            if isinstance(obj, (list, set)):\n                return tuple(map(_freeze, obj))\n            return obj\n\n        return cls({k: _freeze(v) for k, v in data.items()})\n\n    @staticmethod\n    def frozen(to_freeze: Mapping[K, V]) -> FrozenDict[K, V]:\n        \"\"\"Returns a `FrozenDict` containing the keys and values of `to_freeze`.\n\n        If `to_freeze` is already a `FrozenDict`, returns the same object.\n        \"\"\"\n\n        return to_freeze if isinstance(to_freeze, FrozenDict) else FrozenDict(to_freeze)\n\n    def __getitem__(self, k: K) -> V:\n        return self._data[k]\n\n    def __len__(self) -> int:\n        return len(self._data)\n\n    def __iter__(self) -> Iterator[K]:\n        return iter(self._data)\n\n    def __reversed__(self) -> Iterator[K]:\n        return reversed(tuple(self._data))\n\n    def __eq__(self, other: Any) -> Any:\n        # defer to dict's __eq__\n        return self._data == other\n\n    def __lt__(self, other: Any) -> bool:\n        if not isinstance(other, FrozenDict):\n            return NotImplemented\n        # If sorting each of these on every __lt__ call ends up being a problem we could consider\n        # optimising this, by, for instance, sorting on construction.\n        return sorted(self._data.items()) < sorted(other._data.items())\n\n    def _calculate_hash(self) -> int:\n        try:\n            h = 0\n            for pair in self._data.items():\n                # xor is commutative, i.e. we get the same hash no matter the order of items. This\n                # \"relies\" on \"hash\" of the individual elements being unpredictable enough that such\n                # a naive aggregation is okay. In addition, the Python hash isn't / shouldn't be\n                # used for cryptographically sensitive purposes.\n                h ^= hash(pair)\n            return h\n        except TypeError as e:\n            raise TypeError(\n                softwrap(\n                    f\"\"\"\n                    Even though you are using a `{type(self).__name__}`, the underlying values are\n                    not hashable. Please use hashable (and preferably immutable) types for the\n                    underlying values, e.g. use tuples instead of lists and use FrozenOrderedSet\n                    instead of set().\n\n                    Original error message: {e}\n\n                    Value: {self}\n                    \"\"\"\n                )\n            )\n\n    def __hash__(self) -> int:\n        return self._hash\n\n    def __repr__(self) -> str:\n        return f\"{type(self).__name__}({self._data!r})\"\n\n\nclass LazyFrozenDict(FrozenDict[K, V]):\n    \"\"\"A lazy version of `FrozenDict` where the values are not loaded until referenced.\"\"\"\n\n    @overload\n    def __init__(\n        self, __items: Iterable[tuple[K, Callable[[], V]]], **kwargs: Callable[[], V]\n    ) -> None:\n        ...\n\n    @overload\n    def __init__(self, __other: Mapping[K, Callable[[], V]], **kwargs: Callable[[], V]) -> None:\n        ...\n\n    @overload\n    def __init__(self, **kwargs: Callable[[], V]) -> None:\n        ...\n\n    def __init__(\n        self,\n        *item: Mapping[K, Callable[[], V]] | Iterable[tuple[K, Callable[[], V]]],\n        **kwargs: Callable[[], V],\n    ) -> None:\n        super().__init__(*item, **kwargs)  # type: ignore[arg-type]\n\n    def __getitem__(self, k: K) -> V:\n        return self._get_value(k)\n\n    @memoized_method\n    def _get_value(self, k: K) -> V:\n        return cast(\"Callable[[], V]\", self._data[k])()\n", "path": "src/python/pants/util/frozendict.py"}]}