23715422062

Committed 29 Mar 2026 05:59PM UTC coverage: 52.399% (-40.5%) from 92.917%

Build # 23715422062

Build Type

Pull #23200

github

Committed by

web-flow

Commit Message

Merge ee17c6764 into da60c6486

Pull Request Pull Request #23200: perf: Port FrozenOrderedSet to rust

Coverage Stats

18 of 26 new or added lines in 6 files covered. (69.23%)

23004 existing lines in 605 files now uncovered.

31634 of 60371 relevant lines covered (52.4%)

1.05 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

49.47

/src/python/pants/util/ordered_set.py

# Copyright 2020 Pants project contributors (see CONTRIBUTORS.md).
# Licensed under the Apache License, Version 2.0 (see LICENSE).

"""An OrderedSet is a set that remembers its insertion order, and a FrozenOrderedSet is one that is
also immutable.

Based on the library `ordered-set` developed by Robyn Speer and released under the MIT license:
https://github.com/LuminosoInsight/ordered-set.

The library `ordered-set` is itself originally based on a recipe originally posted to ActivateState
Recipes by Raymond Hettiger and released under the MIT license:
http://code.activestate.com/recipes/576694/.
"""

from __future__ import annotations

import itertools
from collections.abc import Iterable, Iterator, MutableSet
from typing import AbstractSet, Any, TypeVar, cast

from pants.engine.internals.native_engine import FrozenOrderedSet as FrozenOrderedSet  # noqa: F401

T = TypeVar("T")
T_co = TypeVar("T_co", covariant=True)
_TAbstractOrderedSet = TypeVar("_TAbstractOrderedSet", bound="_AbstractOrderedSet")


class _AbstractOrderedSet(AbstractSet[T]):
    """Common functionality shared between OrderedSet and FrozenOrderedSet."""

    def __init__(self, iterable: Iterable[T] | None = None) -> None:
        # Using a dictionary, rather than using the recipe's original `self |= iterable`, results
        # in a ~20% performance increase for the constructor.
        #
        # NB: Dictionaries are ordered in Python 3.7+.
        self._items: dict[T, None] = dict.fromkeys(iterable) if iterable else {}

    def __len__(self) -> int:
        """Returns the number of unique elements in the set."""
        return len(self._items)

    def __copy__(self: _TAbstractOrderedSet) -> _TAbstractOrderedSet:
        """Return a shallow copy of this object."""
        return self.__class__(self)

    def __contains__(self, key: Any) -> bool:
        """Test if the item is in this ordered set."""
        return key in self._items

    def __iter__(self) -> Iterator[T]:
        return iter(self._items)

    def __reversed__(self) -> Iterator[T]:
        return reversed(tuple(self._items.keys()))

    def __repr__(self) -> str:
        name = self.__class__.__name__
        if not self:
            return f"{name}()"
        return f"{name}({list(self)!r})"

    def __eq__(self, other: Any) -> bool:
        """Returns True if other is the same type with the same elements and same order."""
        if not isinstance(other, self.__class__):
            return NotImplemented
        return len(self._items) == len(other._items) and all(
            x == y for x, y in zip(self._items, other._items)
        )

    def __or__(self: _TAbstractOrderedSet, other: Iterable[T]) -> _TAbstractOrderedSet:  # type: ignore[override]
        return self.union(other)

    def union(self: _TAbstractOrderedSet, *others: Iterable[T]) -> _TAbstractOrderedSet:
        """Combines all unique items.

        Each item's order is defined by its first appearance.
        """
        # Differences with AbstractSet: our set union forces "other" to have the same type. That
        # is, while AbstractSet allows {1, 2, 3} | {(True, False)} resulting in
        # set[int | tuple[bool, bool]], the analogous for descendants  of _TAbstractOrderedSet is
        # not allowed.
        #
        # GOTCHA: given _TAbstractOrderedSet[S]:
        #   if T is a subclass of S => _TAbstractOrderedSet[S] => *appears* to perform
        #     unification but it doesn't
        #   if S is a subclass of T => type error (while AbstractSet would resolve to
        #     AbstractSet[T])
        merged_iterables = itertools.chain([cast(Iterable[T], self)], others)
        return self.__class__(itertools.chain.from_iterable(merged_iterables))

    def __and__(self: _TAbstractOrderedSet, other: Iterable[T]) -> _TAbstractOrderedSet:
        # The parent class's implementation of this is backwards.
        return self.intersection(other)

    def intersection(self: _TAbstractOrderedSet, *others: Iterable[T]) -> _TAbstractOrderedSet:
        """Returns elements in common between all sets.

        Order is defined only by the first set.
        """
        cls = self.__class__
        if not others:
            return cls(self)
        common = set.intersection(*(set(other) for other in others))
        return cls(item for item in self if item in common)

    def difference(self: _TAbstractOrderedSet, *others: Iterable[T]) -> _TAbstractOrderedSet:
        """Returns all elements that are in this set but not the others."""
        cls = self.__class__
        if not others:
            return cls(self)
        other = set.union(*(set(other) for other in others))
        return cls(item for item in self if item not in other)

    def issubset(self, other: Iterable[T]) -> bool:
        """Report whether another set contains this set."""
        try:
            # Fast check for obvious cases
            if len(self) > len(other):  # type: ignore[arg-type]
                return False
        except TypeError:
            pass
        return all(item in other for item in self)

    def issuperset(self, other: Iterable[T]) -> bool:
        """Report whether this set contains another set."""
        try:
            # Fast check for obvious cases
            if len(self) < len(other):  # type: ignore[arg-type]
                return False
        except TypeError:
            pass
        return all(item in self for item in other)

    def __xor__(self: _TAbstractOrderedSet, other: Iterable[T]) -> _TAbstractOrderedSet:  # type: ignore[override]
        return self.symmetric_difference(other)

    def symmetric_difference(
        self: _TAbstractOrderedSet, other: Iterable[T]
    ) -> _TAbstractOrderedSet:
        """Return the symmetric difference of this OrderedSet and another set as a new OrderedSet.
        That is, the new set will contain all elements that are in exactly one of the sets.

        Their order will be preserved, with elements from `self` preceding elements from `other`.
        """
        cls = self.__class__
        diff1 = cls(self).difference(other)
        diff2 = cls(other).difference(self)
        return diff1.union(diff2)


class OrderedSet(_AbstractOrderedSet[T], MutableSet[T]):
    """A mutable set that retains its order.

    This is not safe to use with the V2 engine.
    """

    def add(self, key: T) -> None:
        """Add `key` as an item to this OrderedSet."""
        self._items[key] = None

    def update(self, iterable: Iterable[T]) -> None:
        """Update the set with the given iterable sequence."""
        for item in iterable:
            self.add(item)

    def discard(self, key: T) -> None:
        """Remove an element. Do not raise an exception if absent.

        The MutableSet mixin uses this to implement the .remove() method, which
        *does* raise an error when asked to remove a non-existent item.
        """
        self._items.pop(key, None)

    def clear(self) -> None:
        """Remove all items from this OrderedSet."""
        self._items.clear()

    def difference_update(self, *others: Iterable[T]) -> None:
        """Update this OrderedSet to remove items from one or more other sets."""
        items_to_remove: set[T] = set()
        for other in others:
            items_as_set = set(other)
            items_to_remove |= items_as_set
        self._items = {item: None for item in self._items.keys() if item not in items_to_remove}

    def intersection_update(self, other: Iterable[T]) -> None:
        """Update this OrderedSet to keep only items in another set, preserving their order in this
        set."""
        other = set(other)
        self._items = {item: None for item in self._items.keys() if item in other}

    def symmetric_difference_update(self, other: Iterable[T]) -> None:
        """Update this OrderedSet to remove items from another set, then add items from the other
        set that were not present in this set."""
        items_to_add = [item for item in other if item not in self]
        items_to_remove = cast(set[T], set(other))
        self._items = {item: None for item in self._items.keys() if item not in items_to_remove}
        for item in items_to_add:
            self._items[item] = None

1	# Copyright 2020 Pants project contributors (see CONTRIBUTORS.md).
2	# Licensed under the Apache License, Version 2.0 (see LICENSE).
3
4	"""An OrderedSet is a set that remembers its insertion order, and a FrozenOrderedSet is one that is
5	also immutable.
6
7	Based on the library `ordered-set` developed by Robyn Speer and released under the MIT license:
8	https://github.com/LuminosoInsight/ordered-set.
9
10	The library `ordered-set` is itself originally based on a recipe originally posted to ActivateState
11	Recipes by Raymond Hettiger and released under the MIT license:
12	http://code.activestate.com/recipes/576694/.
13	"""
14
15	from __future__ import annotations	2✔
16
17	import itertools	2✔
18	from collections.abc import Iterable, Iterator, MutableSet	2✔
19	from typing import AbstractSet, Any, TypeVar, cast	2✔
20
21	from pants.engine.internals.native_engine import FrozenOrderedSet as FrozenOrderedSet # noqa: F401	2✔
22
23	T = TypeVar("T")	2✔
24	T_co = TypeVar("T_co", covariant=True)	2✔
25	_TAbstractOrderedSet = TypeVar("_TAbstractOrderedSet", bound="_AbstractOrderedSet")	2✔
26
27
28	class _AbstractOrderedSet(AbstractSet[T]):	2✔
29	"""Common functionality shared between OrderedSet and FrozenOrderedSet."""
30
31	def __init__(self, iterable: Iterable[T] \| None = None) -> None:	2✔
32	# Using a dictionary, rather than using the recipe's original `self \|= iterable`, results
33	# in a ~20% performance increase for the constructor.
34	#
35	# NB: Dictionaries are ordered in Python 3.7+.
36	self._items: dict[T, None] = dict.fromkeys(iterable) if iterable else {}	2✔
37
38	def __len__(self) -> int:	2✔
39	"""Returns the number of unique elements in the set."""
40	return len(self._items)	2✔
41
42	def __copy__(self: _TAbstractOrderedSet) -> _TAbstractOrderedSet:	2✔
43	"""Return a shallow copy of this object."""
UNCOV 44	return self.__class__(self)	×
45
46	def __contains__(self, key: Any) -> bool:	2✔
47	"""Test if the item is in this ordered set."""
48	return key in self._items	2✔
49
50	def __iter__(self) -> Iterator[T]:	2✔
51	return iter(self._items)	2✔
52
53	def __reversed__(self) -> Iterator[T]:	2✔
UNCOV 54	return reversed(tuple(self._items.keys()))	×
55
56	def __repr__(self) -> str:	2✔
UNCOV 57	name = self.__class__.__name__	×
UNCOV 58	if not self:	×
UNCOV 59	return f"{name}()"	×
UNCOV 60	return f"{name}({list(self)!r})"	×
61
62	def __eq__(self, other: Any) -> bool:	2✔
63	"""Returns True if other is the same type with the same elements and same order."""
UNCOV 64	if not isinstance(other, self.__class__):	×
UNCOV 65	return NotImplemented	×
UNCOV 66	return len(self._items) == len(other._items) and all(	×
67	x == y for x, y in zip(self._items, other._items)
68	)
69
70	def __or__(self: _TAbstractOrderedSet, other: Iterable[T]) -> _TAbstractOrderedSet: # type: ignore[override]	2✔
UNCOV 71	return self.union(other)	×
72
73	def union(self: _TAbstractOrderedSet, *others: Iterable[T]) -> _TAbstractOrderedSet:	2✔
74	"""Combines all unique items.
75
76	Each item's order is defined by its first appearance.
77	"""
78	# Differences with AbstractSet: our set union forces "other" to have the same type. That
79	# is, while AbstractSet allows {1, 2, 3} \| {(True, False)} resulting in
80	# set[int \| tuple[bool, bool]], the analogous for descendants of _TAbstractOrderedSet is
81	# not allowed.
82	#
83	# GOTCHA: given _TAbstractOrderedSet[S]:
84	# if T is a subclass of S => _TAbstractOrderedSet[S] => appears to perform
85	# unification but it doesn't
86	# if S is a subclass of T => type error (while AbstractSet would resolve to
87	# AbstractSet[T])
UNCOV 88	merged_iterables = itertools.chain([cast(Iterable[T], self)], others)	×
UNCOV 89	return self.__class__(itertools.chain.from_iterable(merged_iterables))	×
90
91	def __and__(self: _TAbstractOrderedSet, other: Iterable[T]) -> _TAbstractOrderedSet:	2✔
92	# The parent class's implementation of this is backwards.
UNCOV 93	return self.intersection(other)	×
94
95	def intersection(self: _TAbstractOrderedSet, *others: Iterable[T]) -> _TAbstractOrderedSet:	2✔
96	"""Returns elements in common between all sets.
97
98	Order is defined only by the first set.
99	"""
UNCOV 100	cls = self.__class__	×
UNCOV 101	if not others:	×
102	return cls(self)	×
UNCOV 103	common = set.intersection(*(set(other) for other in others))	×
UNCOV 104	return cls(item for item in self if item in common)	×
105
106	def difference(self: _TAbstractOrderedSet, *others: Iterable[T]) -> _TAbstractOrderedSet:	2✔
107	"""Returns all elements that are in this set but not the others."""
UNCOV 108	cls = self.__class__	×
UNCOV 109	if not others:	×
110	return cls(self)	×
UNCOV 111	other = set.union(*(set(other) for other in others))	×
UNCOV 112	return cls(item for item in self if item not in other)	×
113
114	def issubset(self, other: Iterable[T]) -> bool:	2✔
115	"""Report whether another set contains this set."""
UNCOV 116	try:	×
117	# Fast check for obvious cases
UNCOV 118	if len(self) > len(other): # type: ignore[arg-type]	×
UNCOV 119	return False	×
120	except TypeError:	×
121	pass	×
UNCOV 122	return all(item in other for item in self)	×
123
124	def issuperset(self, other: Iterable[T]) -> bool:	2✔
125	"""Report whether this set contains another set."""
UNCOV 126	try:	×
127	# Fast check for obvious cases
UNCOV 128	if len(self) < len(other): # type: ignore[arg-type]	×
UNCOV 129	return False	×
130	except TypeError:	×
131	pass	×
UNCOV 132	return all(item in self for item in other)	×
133
134	def __xor__(self: _TAbstractOrderedSet, other: Iterable[T]) -> _TAbstractOrderedSet: # type: ignore[override]	2✔
UNCOV 135	return self.symmetric_difference(other)	×
136
137	def symmetric_difference(	2✔
138	self: _TAbstractOrderedSet, other: Iterable[T]
139	) -> _TAbstractOrderedSet:
140	"""Return the symmetric difference of this OrderedSet and another set as a new OrderedSet.
141	That is, the new set will contain all elements that are in exactly one of the sets.
142
143	Their order will be preserved, with elements from `self` preceding elements from `other`.
144	"""
UNCOV 145	cls = self.__class__	×
UNCOV 146	diff1 = cls(self).difference(other)	×
UNCOV 147	diff2 = cls(other).difference(self)	×
UNCOV 148	return diff1.union(diff2)	×
149
150
151	class OrderedSet(_AbstractOrderedSet[T], MutableSet[T]):	2✔
152	"""A mutable set that retains its order.
153
154	This is not safe to use with the V2 engine.
155	"""
156
157	def add(self, key: T) -> None:	2✔
158	"""Add `key` as an item to this OrderedSet."""
159	self._items[key] = None	2✔
160
161	def update(self, iterable: Iterable[T]) -> None:	2✔
162	"""Update the set with the given iterable sequence."""
163	for item in iterable:	2✔
164	self.add(item)	2✔
165
166	def discard(self, key: T) -> None:	2✔
167	"""Remove an element. Do not raise an exception if absent.
168
169	The MutableSet mixin uses this to implement the .remove() method, which
170	does raise an error when asked to remove a non-existent item.
171	"""
172	self._items.pop(key, None)	2✔
173
174	def clear(self) -> None:	2✔
175	"""Remove all items from this OrderedSet."""
UNCOV 176	self._items.clear()	×
177
178	def difference_update(self, *others: Iterable[T]) -> None:	2✔
179	"""Update this OrderedSet to remove items from one or more other sets."""
180	items_to_remove: set[T] = set()	2✔
181	for other in others:	2✔
182	items_as_set = set(other)	2✔
183	items_to_remove \|= items_as_set	2✔
184	self._items = {item: None for item in self._items.keys() if item not in items_to_remove}	2✔
185
186	def intersection_update(self, other: Iterable[T]) -> None:	2✔
187	"""Update this OrderedSet to keep only items in another set, preserving their order in this
188	set."""
UNCOV 189	other = set(other)	×
UNCOV 190	self._items = {item: None for item in self._items.keys() if item in other}	×
191
192	def symmetric_difference_update(self, other: Iterable[T]) -> None:	2✔
193	"""Update this OrderedSet to remove items from another set, then add items from the other
194	set that were not present in this set."""
UNCOV 195	items_to_add = [item for item in other if item not in self]	×
UNCOV 196	items_to_remove = cast(set[T], set(other))	×
UNCOV 197	self._items = {item: None for item in self._items.keys() if item not in items_to_remove}	×
UNCOV 198	for item in items_to_add:	×
UNCOV 199	self._items[item] = None	×

pantsbuild / pants / 23715422062

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous