name = "sortedcontainers"
description = "Pure-Python sorted collections (SortedList, SortedDict, SortedSet) — bug fixes mined from upstream history."
language = "python"
strategies = ["hypothesis", "crosshair"]
crate = "sortedcontainers"
base_commit = "3ac358631f58c1347f1d6d2d92784117db0f38ed"

# ---------------------------------------------------------------------------
# Variant: ior_uses_union_94b7d8f_1
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["ior_uses_union_94b7d8f_1"]

[tasks.source]
repo = "https://github.com/grantjenks/python-sortedcontainers"
commits = ["94b7d8f6e1e3514db0a315e840677c1d99f0bf98"]
commit_subjects = ["Bug Fix: SortedSet.__ior__ should call update, not union"]
origin = "internal"
summary = "SortedSet.__ior__ was bound to ``union`` instead of ``update``. ``s |= x`` therefore returned a brand-new SortedSet, leaving any aliased reference to ``s`` pointing at the original (un-updated) set instead of mutating in place."

[tasks.injection]
kind = "patch"
files = ["src/sortedcontainers/sortedset.py"]
locations = [{ file = "src/sortedcontainers/sortedset.py", line = 659, symbol = "SortedSet.__ior__" }]
patch = "patches/ior_uses_union_94b7d8f_1.patch"

[tasks.bug]
short_name = "ior_uses_union"
invariant = "After ``s |= x`` every reference that previously aliased ``s`` continues to refer to the same SortedSet object, and that object's contents equal the union of ``s``'s previous contents and ``x``."
how_triggered = "The mutation re-binds ``__ior__`` to ``union``, which constructs and returns a new SortedSet. Python's ``|=`` rewrites the local name to that new object, but other references still point at the original — they observe stale contents."

[[tasks.tasks]]
property = "IorPreservesIdentity"
witnesses = [
  { test_fn = "witness_ior_preserves_identity_case_basic", note = "[1,2,3] |= [4,5] aliasing check" },
]

# ---------------------------------------------------------------------------
# Variant: fromkeys_no_cls_a0dfdd8_1
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["fromkeys_no_cls_a0dfdd8_1"]

[tasks.source]
repo = "https://github.com/grantjenks/python-sortedcontainers"
commits = ["a0dfdd88ac62d4ca4629a924d522582bf9c998a7"]
commit_subjects = ["Fix SortedDict.fromkeys to use cls"]
origin = "internal"
summary = "``SortedDict.fromkeys`` constructed a plain ``SortedDict`` instead of using ``cls``. Subclasses calling ``Subclass.fromkeys(...)`` therefore got a ``SortedDict`` instance back, breaking subclass polymorphism."

[tasks.injection]
kind = "patch"
files = ["src/sortedcontainers/sorteddict.py"]
locations = [{ file = "src/sortedcontainers/sorteddict.py", line = 319, symbol = "SortedDict.fromkeys" }]
patch = "patches/fromkeys_no_cls_a0dfdd8_1.patch"

[tasks.bug]
short_name = "fromkeys_no_cls"
invariant = "For any subclass ``S`` of ``SortedDict``, ``S.fromkeys(seq, value)`` returns an instance whose runtime type is exactly ``S``."
how_triggered = "The mutation hard-codes ``SortedDict(...)`` instead of ``cls(...)`` inside the classmethod, so subclass dispatch is bypassed and the returned instance is always a plain ``SortedDict``."

[[tasks.tasks]]
property = "FromkeysUsesCls"
witnesses = [
  { test_fn = "witness_fromkeys_uses_cls_case_basic", note = "Subclass.fromkeys returns Subclass instance" },
]

# ---------------------------------------------------------------------------
# Variant: shallow_copy_aliases_set_970f93f_1
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["shallow_copy_aliases_set_970f93f_1"]

[tasks.source]
repo = "https://github.com/grantjenks/python-sortedcontainers"
commits = ["970f93fbc5c98d24c0b5ace481ce91a1286ad078"]
commit_subjects = ["Fix shallow copy definitions"]
origin = "internal"
summary = "``SortedSet.copy`` aliased the underlying ``_set`` and ``_list`` attributes from the original instance, so mutating one set silently mutated its copy. Fixed by constructing a new backing ``set`` in ``copy``."

[tasks.injection]
kind = "patch"
files = ["src/sortedcontainers/sortedset.py"]
locations = [{ file = "src/sortedcontainers/sortedset.py", line = 351, symbol = "SortedSet.copy" }]
patch = "patches/shallow_copy_aliases_set_970f93f_1.patch"

[tasks.bug]
short_name = "shallow_copy_aliases_set"
invariant = "After ``c = s.copy()``, mutating ``s`` (e.g. ``s.add(x)``) does not affect ``c``: ``c`` still equals the snapshot of ``s`` at the moment of copy."
how_triggered = "The mutation re-binds the new SortedSet's ``_set`` and ``_list`` attributes to the originals, so subsequent additions to either object are observable through both."

[[tasks.tasks]]
property = "CopyDoesNotAliasSet"
witnesses = [
  { test_fn = "witness_copy_does_not_alias_set_case_basic", note = "add to original; copy must be unchanged" },
]

# ---------------------------------------------------------------------------
# Variant: shallow_copy_aliases_dict_970f93f_1
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["shallow_copy_aliases_dict_970f93f_1"]

[tasks.source]
repo = "https://github.com/grantjenks/python-sortedcontainers"
commits = ["970f93fbc5c98d24c0b5ace481ce91a1286ad078"]
commit_subjects = ["Fix shallow copy definitions"]
origin = "internal"
summary = "``SortedDict.copy`` aliased the original instance's ``_list`` (and the values were copied via ``dict.__setitem__`` without re-adding to ``_list``), so the copy's sorted-keys view was inconsistent with its dict contents and mutations to one dict bled into the other."

[tasks.injection]
kind = "patch"
files = ["src/sortedcontainers/sorteddict.py"]
locations = [{ file = "src/sortedcontainers/sorteddict.py", line = 295, symbol = "SortedDict.copy" }]
patch = "patches/shallow_copy_aliases_dict_970f93f_1.patch"

[tasks.bug]
short_name = "shallow_copy_aliases_dict"
invariant = "After ``c = d.copy()``, mutating ``d`` (e.g. ``d[k] = v``) does not affect ``c``: ``c`` still equals the snapshot of ``d`` at the moment of copy."
how_triggered = "The mutation re-binds the copy's ``_list`` to the original's, and uses raw ``dict.__setitem__`` for the values without going through SortedDict's ``__setitem__``. Mutations made later to either dict propagate to both."

[[tasks.tasks]]
property = "CopyDoesNotAliasDict"
witnesses = [
  { test_fn = "witness_copy_does_not_alias_dict_case_basic", note = "add to original; copy must be unchanged" },
]

# ---------------------------------------------------------------------------
# Variant: update_ordering_inconsistent_7dc426c_1
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["update_ordering_inconsistent_7dc426c_1"]

[tasks.source]
repo = "https://github.com/grantjenks/python-sortedcontainers"
commits = ["7dc426c95a0c329d5514e6198d92080f1ffc1e5e"]
commit_subjects = ["Fix update() ordering to be more consistent with add() ordering (#159)"]
prs = [159]
summary = "When the bulk-update path was taken, ``SortedKeyList.update`` extended the freshly-sorted *new* values with the existing values, which placed new values *before* existing values for tie-keys. The subsequent stable sort therefore produced an order that disagreed with calling ``add`` element-by-element."

[tasks.injection]
kind = "patch"
files = ["src/sortedcontainers/sortedlist.py"]
locations = [{ file = "src/sortedcontainers/sortedlist.py", line = 1779, symbol = "SortedKeyList.update" }]
patch = "patches/update_ordering_inconsistent_7dc426c_1.patch"

[tasks.bug]
short_name = "update_ordering_inconsistent"
invariant = "For any starting ``SortedKeyList`` ``A`` and iterable ``vs``, ``A.update(vs)`` produces the same final ordering as calling ``A.add(v)`` for each ``v`` in ``vs`` in turn."
how_triggered = "The mutation reverts the bulk-update branch to ``values.extend(chain.from_iterable(_lists))``, which prepends new data to existing data instead of appending it. Because the subsequent ``values.sort(key=...)`` is stable, tie-key elements end up in the wrong order."

[[tasks.tasks]]
property = "UpdateMatchesAdd"
witnesses = [
  { test_fn = "witness_update_matches_add_case_basic", note = "Modulo-10 key with tie collisions on existing and new" },
]

# ---------------------------------------------------------------------------
# Dropped candidates (terminal reasons)
# ---------------------------------------------------------------------------
[[dropped]]
commit = "8100a8f"
subject = "Fix bug in SortedSet.setitem when ValueError occurs"
reason = "surface removed: SortedSet no longer defines __setitem__"

[[dropped]]
commit = "501d4a9"
subject = "Fix SortedList.__setitem__ to support slices with stop less than start and step equal one"
reason = "surface removed: SortedList.__setitem__ raises NotImplementedError in v2"

[[dropped]]
commit = "bc44999"
subject = "fix setitem to support slices that alias itself"
reason = "surface removed: SortedList.__setitem__ raises NotImplementedError in v2"

[[dropped]]
commit = "367c64a"
subject = "Bug fix: setitem must update _maxes"
reason = "surface removed: SortedList.__setitem__ raises NotImplementedError in v2"

[[dropped]]
commit = "1d91579"
subject = "Apply aliasing fix to SortedListWithKey.__setitem__"
reason = "surface removed: SortedKeyList.__setitem__ raises NotImplementedError in v2"

[[dropped]]
commit = "780e50b"
subject = "Fix sortedlist when setting slice with empty iterable"
reason = "surface removed: SortedList.__setitem__ raises NotImplementedError in v2"

[[dropped]]
commit = "53ab610"
subject = "Test and bug fix for SortedList.extend with empty iterable"
reason = "surface removed: SortedList.extend raises NotImplementedError in v2; SortedList.update handles empty iterables natively"

[[dropped]]
commit = "1c6a43a"
subject = "Fix sortedset setitem and improve tests"
reason = "surface removed: SortedSet no longer defines __setitem__"

[[dropped]]
commit = "be06d8d"
subject = "Pickle fix for SortedSet on py27"
reason = "Python 2 only — bug not reachable on Python 3"

[[dropped]]
commit = "fe780f5"
subject = "Fixes for Python 2.6, 3.2, 3.3, and 3.4"
reason = "Python 2 / legacy Python 3 only — not reachable on supported toolchains"

[[dropped]]
commit = "9ba1980"
subject = "Fix relative import for python 3 in sortedlistwithkey"
reason = "Python 2/3 import-style fix; surface removed (sortedlistwithkey module deleted)"

[[dropped]]
commit = "3367ea5"
subject = "Make iteritems, iterkeys, itervalues, viewitems, viewkeys, viewvalues raise AttributeError"
reason = "Python 2 cleanup — modern Python does not expose these names; behavior is now provided by inherited dict semantics"

[[dropped]]
commit = "2b03703"
subject = "Fix for issue #147 -- Stop caching dict methods using super"
reason = "memory/GC pause regression; not expressible as a pure functional invariant"

[[dropped]]
commit = "a04f4a6"
subject = "Fix bug in SortedDict comparison (possible KeyError)"
reason = "surface changed: SortedDict in v2 inherits from dict and uses dict.__eq__/__ne__, so the buggy iteration path no longer exists"

[[dropped]]
commit = "4ce5210"
subject = "Fix SortedDict.update to accept dict type"
reason = "surface changed: modern SortedDict.update accepts dict types via inherited dict.update path"

[[dropped]]
commit = "0962877"
subject = "Fix lte/gte to le/ge for sortedset"
reason = "no observable public invariant: SortedSet inherits __le__/__ge__ from MutableSet via collections.abc, so renaming the SortedSet-defined methods to nonsense names still yields correct subset/superset comparisons through inheritance"

[[dropped]]
commit = "b3cae10"
subject = "Fix index check when child exceeds length"
reason = "internal-only: bug is in SortedList._check (an O(n) invariant validator that user code typically never calls); the public API never observes the assertion failure"

[[dropped]]
commit = "a37f243"
subject = "Fix comment on SortedList.index"
reason = "comment-only change — no behavioral effect"

[[dropped]]
commit = "9b2d38c"
subject = "Correct SortedValuesView docstring"
reason = "docstring-only change — no behavioral effect"

[[dropped]]
commit = "15b8165"
subject = "Fix typo in doc for SortedList comparison methods"
reason = "docstring-only change — no behavioral effect"

[[dropped]]
commit = "9ff3270"
subject = "change the documentation of SortedValuesViews"
reason = "docs-only change — no behavioral effect"

[[dropped]]
commit = "ff966d1"
subject = "Fix import formatting"
reason = "code-formatting only — no behavioral effect"

[[dropped]]
commit = "a13ac31"
subject = "Add support for Python 3.11 and 3.12"
reason = "compatibility / packaging change — not a bug fix to library logic"

[[dropped]]
commit = "ca44935"
subject = "Add Cython and GitHub actions workflow for integration"
reason = "feature/build-config addition — not a bug fix"

[[dropped]]
commit = "2678a78"
subject = "Implement SortedDict methods: __or__, __ror__, and __ior__"
reason = "feature addition — not a bug fix"

[[dropped]]
commit = "66c39a1"
subject = "Bump version to 0.9.1"
reason = "version bump — no behavioral effect"

[[dropped]]
commit = "dcba212"
subject = "Bump version to 0.8.1 after SortedDict comparison fix"
reason = "version bump — no behavioral effect"

[[dropped]]
commit = "dc9cf97"
subject = "Revert \"Fix SortedListWithKey w/ incomparable values on Python 3\""
reason = "revert commit; underlying surface (sortedlistwithkey module) removed in v2"

[[dropped]]
commit = "59a358c"
subject = "Fix SortedListWithKey w/ incomparable values on Python 3"
reason = "subsequently reverted by dc9cf97; surface (sortedlistwithkey module) removed in v2"

[[dropped]]
commit = "9e81697"
subject = "Improve coverage for sorteddict and fix bugs"
reason = "vague catch-all commit; the underlying SortedDict (MutableMapping-based) was rewritten in v2 to inherit from dict, so the specific defects addressed here no longer exist on the modern surface"

[[dropped]]
commit = "4887276"
subject = "Coverage, stress, and bug fixes."
reason = "primarily test/coverage churn against an obsolete SortedList implementation that was rewritten in v2"

[[dropped]]
commit = "1fa4168"
subject = "Fix self._dict reference in ValuesView.count"
reason = "surface changed: SortedDict in v2 uses SortedValuesView (subclass of collections.abc.ValuesView) which inherits .count from Sequence; the buggy custom .count method no longer exists"
