[regression][8.2.2] KeyError sometimes crashes test collection on PyPy while reordering fixtures #13312

Activity

1. webknjaz

   added

   topic: collectionrelated to the collection phaserelated to the collection phase

   topic: fixturesanything involving fixtures directly or indirectlyanything involving fixtures directly or indirectly

   topic: parametrizerelated to @pytest.mark.parametrizerelated to @pytest.mark.parametrize

   topic: selectionrelated to test selection from the command linerelated to test selection from the command line

   type: bugproblem that needs to be addressedproblem that needs to be addressed

   type: regressionindicates a problem that was introduced in a release which was working previouslyindicates a problem that was introduced in a release which was working previously

   on Mar 19, 2025
2. webknjaz

   added this to 📅 Procrastinating in public 😵‍💫on Mar 19, 2025
3. webknjaz

   moved this to 🕵️ Rabbit hole maze 🕵 in 📅 Procrastinating in public 😵‍💫on Mar 19, 2025
4. webknjaz

   added a commit that references this issue on Mar 19, 2025

   🧪 Use Pytest 8.2.1 on PyPy

   ...

   9d55c9f
5. webknjaz

   changed the title [-][regression][8.2.2] `KeyError` sometimes crashes test collection on PyPy 3.9 while reordering fixtures[/-] [+][regression][8.2.2] `KeyError` sometimes crashes test collection on PyPy while reordering fixtures[/+] on Mar 19, 2025
6. RonnyPfannschmidt commented on Mar 20, 2025

   

   RonnyPfannschmidt

   on Mar 20, 2025

   Member

   More actions

   i believe we may need to report this to pypy as well

   👍React with 👍1Reacted by 🇺🇦 Sviatoslav Sydorenko (Святослав Сидоренко)
7. mgorny commented on Apr 1, 2025

   

   mgorny

   on Apr 1, 2025

   Contributor

   More actions

   CC @mattip, @cfbolz

   ❤️React with ❤️1Reacted by 🇺🇦 Sviatoslav Sydorenko (Святослав Сидоренко)
8. webknjaz commented on Apr 1, 2025

   

   webknjaz

   on Apr 1, 2025

   MemberAuthor

   More actions

   Oh, I forgot to notify PyPy 🤦‍♂️. Thanks for tagging them!
9. RonnyPfannschmidt commented on Apr 10, 2025

   

   RonnyPfannschmidt

   on Apr 10, 2025

   Member

   More actions

   i suspect the key differerenve is somewhere in https://github.com/pypy/pypy/blob/branches/release-pypy3.10-v7.x/pypy/module/_collections/app_odict.py
10. mgorny commented on Apr 10, 2025

    

    mgorny

    on Apr 10, 2025

    Contributor

    More actions

    Unfortunately, debugging RPython is above my pay grade. It would be interesting to find out when duplicate keys get introduced, but at least at a first glance, nothing stands out. Most of the code is calling into dict superclass, and move_to_end() is literally del + set again.

    👍React with 👍1Reacted by 🇺🇦 Sviatoslav Sydorenko (Святослав Сидоренко)
11. 5 remaining items

    Load more

12. cfbolz commented on Apr 11, 2025

    

    cfbolz

    on Apr 11, 2025

    More actions

    thanks everyone for trying to track this down! I'll try to understand what's going on and have two questions that would help me a lot:

    • is it correct that move_to_end is used, and that that leads to the bug somehow?
    • the keys are tuples of a number of strings and pytest internal types, correct?

    It's likely that the bug managed to hide for a long time because move_to_end is a relatively rare operations.

    👍React with 👍1Reacted by 🇺🇦 Sviatoslav Sydorenko (Святослав Сидоренко)
13. RonnyPfannschmidt commented on Apr 11, 2025

    

    RonnyPfannschmidt

    on Apr 11, 2025

    Member

    More actions

    move_to_end is used and the key is a pytest internal type

    we use a OrderedDict[Item, None] as a OrderedSet[Item]
14. webknjaz commented on Apr 11, 2025

    

    webknjaz

    on Apr 11, 2025

    MemberAuthor

    More actions

    is it correct that move_to_end is used, and that that leads to the bug somehow?

    @cfbolz it is used, but I'm not entirely sure that it is the underlying cause of the issue (unless you're implying that previous invocations of this method on the same object had effect at some point in the future). When I was running pdb, I was trying to access the problematic key through normal square brackets and it was giving me the same key error. And then I listed the keys, and noticed that the problematic one was duplicated.
15. mgorny commented on May 20, 2025

    

    mgorny

    on May 20, 2025

    Last edited by mgorny

    Contributor

    More actions

    Okay, I'm not sure if this is something you want to do upstream, but to unblock Gentoo for the time being I'm going to apply the following hack:

    diff --git a/src/_pytest/fixtures.py b/src/_pytest/fixtures.py
    index 6b882fa35..985e45ce3 100644
    --- a/src/_pytest/fixtures.py
    +++ b/src/_pytest/fixtures.py
    @@ -278,6 +278,12 @@ def reorder_items_atscope(
                         for other_scope in HIGH_SCOPES:
                             other_scoped_items_by_argkey = items_by_argkey[other_scope]
                             for argkey in argkeys_by_item[other_scope].get(i, ()):
    +                            if hasattr(sys, "pypy_version_info"):
    +                                # Gentoo workaround for https://github.com/pytest-dev/pytest/issues/13312
    +                                del other_scoped_items_by_argkey[argkey][i]
    +                                new_dict = OrderedDict({i: None})
    +                                new_dict.update(other_scoped_items_by_argkey[argkey])
    +                                continue
                                 other_scoped_items_by_argkey[argkey][i] = None
                                 other_scoped_items_by_argkey[argkey].move_to_end(
                                     i, last=False

    i.e. just inline move_to_end(last=False) (unless I messed the logic up).

    👀React with 👀1Reacted by 🇺🇦 Sviatoslav Sydorenko (Святослав Сидоренко)
16. gentoo-bot

    added a commit that references this issue on May 20, 2025

    dev-python/pytest: Workaround the PyPy OrderedDict.move_to_end bug

    ...

    98fd627
17. bluetech commented on May 25, 2025

    

    bluetech

    on May 25, 2025

    Member

    More actions

    Chasing the link to the PyPy code that @RonnyPfannschmidt linked, I think that move_to_end(last=False) ends up in this code:

    https://github.com/pypy/pypy/blob/f58a4aee085665550ee92f65930176d8284dae9c/rpython/rtyper/lltypesystem/rordereddict.py#L1537-L1621

    It is too complex for me to figure out quickly. But I do see it contains several assertions (ll_assert calls). I'm assuming these assertions are turned off in a production build of PyPy, but if the bug can be reproduced under an assertions-enabled build of PyPy maybe we get lucky and one the assertions will fail.

    If I get some time, I will also try to run some property tests for OrderedDict.move_to_end on PyPy, maybe we get lucky with this and find a bug...

    I am also trying to read reorder_items again to understand if the problem might be on the pytest side, but that code is a bit of a maze (it was much worse in the past!)...

    👀React with 👀1Reacted by 🇺🇦 Sviatoslav Sydorenko (Святослав Сидоренко)
18. cfbolz commented on May 25, 2025

    

    cfbolz

    on May 25, 2025

    More actions

    I found a shorter reproducer, see I the discussion pypy/pypy#5257

    I'm fairly close to solving it, basically move_to_first can break an invariant of the dict (which doesn't have an ll_assert 🙄).

    ❤️React with ❤️1Reacted by 🇺🇦 Sviatoslav Sydorenko (Святослав Сидоренко)
19. bluetech commented on May 25, 2025

    

    bluetech

    on May 25, 2025

    Member

    More actions

    @cfbolz Awesome!

    If I get some time, I will also try to run some property tests for OrderedDict.move_to_end on PyPy, maybe we get lucky with this and find a bug...

    Just for trivia, I did ask an LLM (Claude 4 Sonnet) to generate some Hypothesis tests for OrderedDict.move_to_end, it produced the beast below, however it doesn't find the bug on PyPy 7.3.19. 👍 for Humanity :)

    AI-generated Hypothesis tests

    # --- GENERATED BY AI (Claude 4 Sonnet) ---
    #
    # PROMPT: Create a file move_to_end_tests.py containing Hypothesis property
    # tests for the Python OrderedDict.move_to_end(last=False) function. Make it as
    # extensive and comprehensive as possible, covering as many edge cases as
    # possible.
    """
    Comprehensive Hypothesis property tests for OrderedDict.move_to_end(last=False) function.
    
    This test suite covers extensive edge cases and properties of the move_to_end method
    when called with last=False, which moves items to the beginning of the OrderedDict.
    
    TEST COVERAGE SUMMARY:
    ======================
    
    Core Functionality:
    - ✅ Key moves to beginning of OrderedDict
    - ✅ Value preservation during move operation
    - ✅ Relative order of other keys is maintained
    - ✅ Dictionary size remains unchanged
    - ✅ All key-value pairs are preserved
    
    Error Handling:
    - ✅ KeyError raised for non-existent keys
    - ✅ Dictionary unchanged when KeyError occurs
    - ✅ Empty dictionary KeyError behavior
    
    Edge Cases:
    - ✅ Single-item dictionary operations
    - ✅ Moving first key (no-op behavior)
    - ✅ Moving last key to first position
    - ✅ Moving middle keys to first position
    - ✅ Consecutive moves of same key (idempotent)
    - ✅ Moving all keys in reverse order
    
    Key Types Tested:
    - ✅ String keys (including empty, whitespace, unicode, emoji)
    - ✅ Integer keys (including edge values like sys.maxsize)
    - ✅ Float keys (including infinity)
    - ✅ Boolean keys (True/False)
    - ✅ None as key
    - ✅ Tuple keys
    - ✅ Frozenset keys
    - ✅ Custom objects with __hash__ and __eq__
    
    Value Types Tested:
    - ✅ Integers, floats, strings, booleans, None
    - ✅ Lists, dictionaries, nested data structures
    - ✅ Large values (memory efficiency)
    - ✅ Recursive/circular data structures
    - ✅ Duplicate values across different keys
    
    Advanced Scenarios:
    - ✅ Large dictionaries (performance testing)
    - ✅ OrderedDict subclass behavior
    - ✅ Iterator behavior after modification
    - ✅ Object identity preservation
    - ✅ Method signature validation
    - ✅ String representation correctness
    - ✅ Thread safety considerations (single-threaded)
    - ✅ Conversion from regular dict
    
    Property-Based Testing:
    - Uses Hypothesis to generate diverse test cases automatically
    - Custom strategies for OrderedDict generation with existing/missing keys
    - Comprehensive edge case exploration through randomized testing
    - 38 distinct test cases covering all major scenarios
    
    Total Tests: 38 passing
    Framework: pytest + Hypothesis
    """
    
    import pytest
    from collections import OrderedDict
    from hypothesis import given, strategies as st, assume, example, settings
    from hypothesis.strategies import composite
    import string
    import sys
    
    
    # Custom strategies for generating test data
    @composite
    def ordered_dict_with_key(draw, min_size=0, max_size=20):
        """Generate an OrderedDict and a key that exists in it."""
        # Generate keys first
        keys = draw(st.lists(
            st.text(alphabet=string.ascii_letters + string.digits, min_size=1, max_size=10),
            min_size=min_size + 1,
            max_size=max_size + 1,
            unique=True
        ))
    
        # Choose one key to be our target
        target_key = draw(st.sampled_from(keys))
    
        # Generate values for all keys
        values = draw(st.lists(
            st.one_of(
                st.integers(),
                st.text(),
                st.floats(allow_nan=False, allow_infinity=False),
                st.booleans(),
                st.none()
            ),
            min_size=len(keys),
            max_size=len(keys)
        ))
    
        # Create OrderedDict
        od = OrderedDict(zip(keys, values))
        return od, target_key
    
    
    @composite
    def ordered_dict_without_key(draw, min_size=0, max_size=20):
        """Generate an OrderedDict and a key that does NOT exist in it."""
        # Generate existing keys
        existing_keys = draw(st.lists(
            st.text(alphabet=string.ascii_letters + string.digits, min_size=1, max_size=10),
            min_size=min_size,
            max_size=max_size,
            unique=True
        ))
    
        # Generate a key that doesn't exist
        missing_key = draw(st.text(alphabet=string.ascii_letters + string.digits + "_!", min_size=1, max_size=10))
        assume(missing_key not in existing_keys)
    
        # Generate values
        values = draw(st.lists(
            st.one_of(
                st.integers(),
                st.text(),
                st.floats(allow_nan=False, allow_infinity=False),
                st.booleans(),
                st.none()
            ),
            min_size=len(existing_keys),
            max_size=len(existing_keys)
        ))
    
        # Create OrderedDict
        od = OrderedDict(zip(existing_keys, values))
        return od, missing_key
    
    
    class TestMoveToEndLastFalse:
        """Test suite for OrderedDict.move_to_end(last=False)."""
    
        @given(ordered_dict_with_key())
        def test_key_moves_to_beginning(self, od_and_key):
            """Test that move_to_end(last=False) moves the key to the beginning."""
            od, key = od_and_key
            original_value = od[key]
            original_keys = list(od.keys())
            original_values = list(od.values())
    
            od.move_to_end(key, last=False)
    
            new_keys = list(od.keys())
            new_values = list(od.values())
    
            # Key should be first
            assert new_keys[0] == key
            # Value should be preserved
            assert od[key] == original_value
            # All original keys should still be present
            assert set(new_keys) == set(original_keys)
            # All original values should still be present
            assert set(new_values) == set(original_values)
            # Length should be unchanged
            assert len(od) == len(original_keys)
    
        @given(ordered_dict_with_key())
        def test_value_preservation(self, od_and_key):
            """Test that the value associated with the key is preserved."""
            od, key = od_and_key
            original_value = od[key]
    
            od.move_to_end(key, last=False)
    
            assert od[key] == original_value
    
        @given(ordered_dict_with_key())
        def test_other_keys_order_preserved(self, od_and_key):
            """Test that the relative order of other keys is preserved."""
            od, key = od_and_key
            original_keys = list(od.keys())
    
            # Get the order of keys excluding the target key
            other_keys_original = [k for k in original_keys if k != key]
    
            od.move_to_end(key, last=False)
    
            new_keys = list(od.keys())
            other_keys_new = [k for k in new_keys if k != key]
    
            # Other keys should maintain their relative order
            assert other_keys_new == other_keys_original
    
        @given(ordered_dict_with_key())
        def test_dictionary_size_unchanged(self, od_and_key):
            """Test that the size of the dictionary remains unchanged."""
            od, key = od_and_key
            original_size = len(od)
    
            od.move_to_end(key, last=False)
    
            assert len(od) == original_size
    
        @given(ordered_dict_with_key())
        def test_all_items_preserved(self, od_and_key):
            """Test that all key-value pairs are preserved."""
            od, key = od_and_key
            original_items = set(od.items())
    
            od.move_to_end(key, last=False)
    
            new_items = set(od.items())
            assert new_items == original_items
    
        @given(ordered_dict_without_key())
        def test_keyerror_for_missing_key(self, od_and_key):
            """Test that KeyError is raised for non-existent keys."""
            od, missing_key = od_and_key
    
            with pytest.raises(KeyError):
                od.move_to_end(missing_key, last=False)
    
        @given(ordered_dict_without_key())
        def test_dictionary_unchanged_after_keyerror(self, od_and_key):
            """Test that the dictionary is unchanged when KeyError occurs."""
            od, missing_key = od_and_key
            original_items = list(od.items())
    
            try:
                od.move_to_end(missing_key, last=False)
            except KeyError:
                pass
    
            assert list(od.items()) == original_items
    
        def test_empty_dictionary_keyerror(self):
            """Test KeyError on empty dictionary."""
            od = OrderedDict()
    
            with pytest.raises(KeyError):
                od.move_to_end("any_key", last=False)
    
        @given(st.text(min_size=1, max_size=50))
        def test_single_item_dictionary(self, key):
            """Test move_to_end on single-item dictionary."""
            value = "test_value"
            od = OrderedDict([(key, value)])
    
            od.move_to_end(key, last=False)
    
            assert list(od.keys()) == [key]
            assert od[key] == value
    
        @given(ordered_dict_with_key(min_size=1))
        def test_first_key_already_first(self, od_and_key):
            """Test moving the first key to the beginning (should be no-op)."""
            od, _ = od_and_key
            first_key = next(iter(od))
            original_items = list(od.items())
    
            od.move_to_end(first_key, last=False)
    
            assert list(od.items()) == original_items
    
        @given(ordered_dict_with_key(min_size=2))
        def test_last_key_to_first(self, od_and_key):
            """Test moving the last key to the beginning."""
            od, _ = od_and_key
            keys = list(od.keys())
            last_key = keys[-1]
            original_value = od[last_key]
    
            od.move_to_end(last_key, last=False)
    
            new_keys = list(od.keys())
            assert new_keys[0] == last_key
            assert od[last_key] == original_value
            # Check that other keys maintain relative order
            assert new_keys[1:] == keys[:-1]
    
        @given(ordered_dict_with_key(min_size=3))
        def test_middle_key_to_first(self, od_and_key):
            """Test moving a middle key to the beginning."""
            od, _ = od_and_key
            keys = list(od.keys())
            assume(len(keys) >= 3)
    
            middle_key = keys[len(keys) // 2]
            original_value = od[middle_key]
    
            od.move_to_end(middle_key, last=False)
    
            new_keys = list(od.keys())
            assert new_keys[0] == middle_key
            assert od[middle_key] == original_value
    
        @given(ordered_dict_with_key())
        def test_consecutive_moves_to_beginning(self, od_and_key):
            """Test multiple consecutive moves to beginning."""
            od, key = od_and_key
            original_value = od[key]
    
            # Move the same key multiple times
            od.move_to_end(key, last=False)
            od.move_to_end(key, last=False)
            od.move_to_end(key, last=False)
    
            # Should still be at the beginning
            assert list(od.keys())[0] == key
            assert od[key] == original_value
    
        @given(ordered_dict_with_key(min_size=2))
        def test_move_all_keys_to_beginning_reverse_order(self, od_and_key):
            """Test moving all keys to beginning in reverse order."""
            od, _ = od_and_key
            original_keys = list(od.keys())
            original_items = dict(od)
    
            # Move each key to the beginning in reverse order
            for key in reversed(original_keys):
                od.move_to_end(key, last=False)
    
            # Final order should be the original order (each key moved to front,
            # but processing in reverse means the original first becomes last to be moved)
            expected_keys = original_keys
            assert list(od.keys()) == expected_keys
    
            # All values should be preserved
            for key in original_keys:
                assert od[key] == original_items[key]
    
        @given(st.lists(st.text(min_size=1, max_size=10), min_size=1, max_size=10, unique=True))
        def test_special_key_types(self, string_keys):
            """Test with various key types including edge cases."""
            # Test with different key types
            special_keys = [
                "",  # empty string
                " ",  # whitespace
                "\n",  # newline
                "\t",  # tab
                "key with spaces",
                "key_with_underscores",
                "key-with-hyphens",
                "KeyWithCaps",
                "123numeric",
                "🚀emoji",
                "ключ",  # non-ASCII
            ]
    
            # Filter out keys that might already be in string_keys
            unique_special_keys = [k for k in special_keys if k not in string_keys]
    
            if unique_special_keys:
                test_key = unique_special_keys[0]
                values = list(range(len(string_keys) + 1))
                od = OrderedDict(zip(string_keys + [test_key], values))
    
                od.move_to_end(test_key, last=False)
    
                assert list(od.keys())[0] == test_key
    
        @given(st.integers(), st.floats(allow_nan=False, allow_infinity=False), st.text())
        def test_various_value_types(self, int_val, float_val, str_val):
            """Test move_to_end with various value types."""
            od = OrderedDict([
                ("int_key", int_val),
                ("float_key", float_val),
                ("str_key", str_val),
                ("none_key", None),
                ("bool_key", True),
                ("list_key", [1, 2, 3]),
                ("dict_key", {"nested": "value"}),
            ])
    
            target_key = "float_key"
            original_value = od[target_key]
    
            od.move_to_end(target_key, last=False)
    
            assert list(od.keys())[0] == target_key
            assert od[target_key] == original_value
            assert od[target_key] == float_val
    
        @given(ordered_dict_with_key(max_size=100))
        @settings(max_examples=50)
        def test_large_dictionary_performance(self, od_and_key):
            """Test move_to_end on larger dictionaries."""
            od, key = od_and_key
            original_size = len(od)
            original_value = od[key]
    
            od.move_to_end(key, last=False)
    
            assert list(od.keys())[0] == key
            assert od[key] == original_value
            assert len(od) == original_size
    
        @given(st.tuples(st.integers(), st.text()))
        def test_tuple_keys(self, tuple_key):
            """Test move_to_end with tuple keys."""
            od = OrderedDict([
                (tuple_key, "tuple_value"),
                ("regular_key", "regular_value"),
                ((1, 2, 3), "another_tuple_value"),
            ])
    
            od.move_to_end(tuple_key, last=False)
    
            assert list(od.keys())[0] == tuple_key
            assert od[tuple_key] == "tuple_value"
    
        def test_frozen_set_keys(self):
            """Test move_to_end with frozenset keys."""
            key1 = frozenset([1, 2, 3])
            key2 = frozenset(['a', 'b'])
    
            od = OrderedDict([
                (key1, "frozenset1"),
                ("regular", "value"),
                (key2, "frozenset2"),
            ])
    
            od.move_to_end(key2, last=False)
    
            assert list(od.keys())[0] == key2
            assert od[key2] == "frozenset2"
    
        @given(ordered_dict_with_key())
        def test_idempotent_operations(self, od_and_key):
            """Test that applying move_to_end twice gives same result as applying once."""
            od, key = od_and_key
            od_copy = OrderedDict(od)
    
            # Apply once
            od.move_to_end(key, last=False)
            result_once = list(od.items())
    
            # Apply twice on copy
            od_copy.move_to_end(key, last=False)
            od_copy.move_to_end(key, last=False)
            result_twice = list(od_copy.items())
    
            assert result_once == result_twice
    
        def test_method_signature_validation(self):
            """Test that the method accepts the expected arguments."""
            od = OrderedDict([("a", 1), ("b", 2)])
    
            # Test default behavior (should work with just key)
            od.move_to_end("a")  # default last=True
    
            # Test explicit last=False
            od.move_to_end("b", last=False)
    
            # Test explicit last=True
            od.move_to_end("a", last=True)
    
            # Test keyword argument
            od.move_to_end(key="b", last=False)
    
        @given(ordered_dict_with_key())
        def test_iterator_invalidation(self, od_and_key):
            """Test behavior with iterators after move_to_end."""
            od, key = od_and_key
    
            # Create iterators before modification
            keys_iter = iter(od.keys())
            values_iter = iter(od.values())
            items_iter = iter(od.items())
    
            # Move key to beginning
            od.move_to_end(key, last=False)
    
            # Iterators should still work (though order may be different)
            # This tests that the operation doesn't break the underlying structure
            try:
                remaining_keys = list(keys_iter)
                remaining_values = list(values_iter)
                remaining_items = list(items_iter)
            except RuntimeError:
                # Some implementations may invalidate iterators, which is acceptable
                pass
    
        def test_subclass_behavior(self):
            """Test that move_to_end works correctly with OrderedDict subclasses."""
            class CustomOrderedDict(OrderedDict):
                def __setitem__(self, key, value):
                    super().__setitem__(key, f"custom_{value}")
    
            od = CustomOrderedDict([("a", "1"), ("b", "2"), ("c", "3")])
    
            od.move_to_end("b", last=False)
    
            assert list(od.keys())[0] == "b"
            assert od["b"] == "custom_2"
    
        @given(st.integers(min_value=0, max_value=1000))
        def test_numeric_keys_edge_cases(self, num_key):
            """Test move_to_end with numeric keys including edge cases."""
            od = OrderedDict([
                (0, "zero"),
                (num_key, "target"),
                (-1, "negative"),
                (sys.maxsize, "maxsize"),
                (float('inf'), "infinity") if num_key != float('inf') else (1.0, "one"),
            ])
    
            if num_key in od:
                od.move_to_end(num_key, last=False)
                assert list(od.keys())[0] == num_key
    
        def test_deeply_nested_values(self):
            """Test move_to_end with complex nested data structures as values."""
            complex_value = {
                "level1": {
                    "level2": {
                        "level3": [1, 2, {"level4": "deep"}]
                    }
                }
            }
    
            od = OrderedDict([
                ("simple", 1),
                ("complex", complex_value),
                ("list", [1, [2, [3, 4]]]),
            ])
    
            od.move_to_end("complex", last=False)
    
            assert list(od.keys())[0] == "complex"
            assert od["complex"] == complex_value
            assert od["complex"]["level1"]["level2"]["level3"][2]["level4"] == "deep"
    
        def test_none_as_key(self):
            """Test move_to_end with None as a key."""
            od = OrderedDict([
                (None, "none_value"),
                ("string_key", "string_value"),
                (42, "int_value"),
            ])
    
            od.move_to_end(None, last=False)
    
            assert list(od.keys())[0] is None
            assert od[None] == "none_value"
    
        @given(st.lists(st.integers(), min_size=1, max_size=50, unique=True))
        def test_all_integer_keys(self, int_keys):
            """Test move_to_end with all integer keys."""
            values = [f"value_{i}" for i in range(len(int_keys))]
            od = OrderedDict(zip(int_keys, values))
    
            target_key = int_keys[len(int_keys) // 2] if len(int_keys) > 1 else int_keys[0]
            original_value = od[target_key]
    
            od.move_to_end(target_key, last=False)
    
            assert list(od.keys())[0] == target_key
            assert od[target_key] == original_value
    
        def test_boolean_keys(self):
            """Test move_to_end with boolean keys."""
            od = OrderedDict([
                (True, "true_value"),
                (False, "false_value"),
                ("string", "string_value"),
            ])
    
            od.move_to_end(False, last=False)
    
            assert list(od.keys())[0] is False
            assert od[False] == "false_value"
    
        @given(st.text(min_size=0, max_size=1000))
        def test_very_long_string_keys(self, long_string):
            """Test move_to_end with very long string keys."""
            od = OrderedDict([
                ("short", "short_value"),
                (long_string, "long_value"),
                ("another", "another_value"),
            ])
    
            od.move_to_end(long_string, last=False)
    
            assert list(od.keys())[0] == long_string
            assert od[long_string] == "long_value"
    
        def test_duplicate_values_different_keys(self):
            """Test move_to_end when multiple keys have the same value."""
            same_value = "shared_value"
            od = OrderedDict([
                ("key1", same_value),
                ("key2", same_value),
                ("key3", "different_value"),
                ("key4", same_value),
            ])
    
            od.move_to_end("key2", last=False)
    
            assert list(od.keys())[0] == "key2"
            assert od["key2"] == same_value
            # Ensure other keys with same value are unchanged
            assert od["key1"] == same_value
            assert od["key4"] == same_value
    
        @given(ordered_dict_with_key(min_size=1))
        def test_move_to_end_preserves_identity(self, od_and_key):
            """Test that move_to_end preserves object identity of the OrderedDict."""
            od, key = od_and_key
            original_id = id(od)
    
            od.move_to_end(key, last=False)
    
            assert id(od) == original_id
    
        def test_key_with_special_methods(self):
            """Test move_to_end with keys that have special methods."""
            class SpecialKey:
                def __init__(self, value):
                    self.value = value
    
                def __hash__(self):
                    return hash(self.value)
    
                def __eq__(self, other):
                    return isinstance(other, SpecialKey) and self.value == other.value
    
                def __repr__(self):
                    return f"SpecialKey({self.value})"
    
            key1 = SpecialKey("first")
            key2 = SpecialKey("second")
    
            od = OrderedDict([
                (key1, "first_value"),
                ("regular", "regular_value"),
                (key2, "second_value"),
            ])
    
            od.move_to_end(key2, last=False)
    
            assert list(od.keys())[0] == key2
            assert od[key2] == "second_value"
    
        def test_recursive_data_structures(self):
            """Test move_to_end with recursive/circular data structures as values."""
            od = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
    
            # Create a circular reference
            circular_dict = {"self": None, "other": "value"}
            circular_dict["self"] = circular_dict
    
            od["circular"] = circular_dict
    
            od.move_to_end("circular", last=False)
    
            assert list(od.keys())[0] == "circular"
            assert od["circular"]["other"] == "value"
            assert od["circular"]["self"] is od["circular"]
    
        @given(st.floats(allow_nan=False, allow_infinity=True))
        def test_float_keys_with_infinity(self, float_key):
            """Test move_to_end with float keys including infinity."""
            od = OrderedDict([
                (1.0, "one"),
                (float_key, "target"),
                (2.0, "two"),
            ])
    
            if float_key in od:  # Handle potential duplicates
                od.move_to_end(float_key, last=False)
                assert list(od.keys())[0] == float_key
    
        def test_memory_efficiency_large_values(self):
            """Test that move_to_end doesn't unnecessarily copy large values."""
            large_value = list(range(10000))  # Large but not huge for test performance
    
            od = OrderedDict([
                ("small1", 1),
                ("large", large_value),
                ("small2", 2),
            ])
    
            # Store reference to check it's the same object
            original_large_value = od["large"]
    
            od.move_to_end("large", last=False)
    
            assert list(od.keys())[0] == "large"
            assert od["large"] is original_large_value  # Should be same object
    
        @given(st.dictionaries(
            st.text(min_size=1, max_size=10),
            st.integers(),
            min_size=1,
            max_size=20
        ))
        def test_from_regular_dict_conversion(self, regular_dict):
            """Test move_to_end after converting from regular dict."""
            od = OrderedDict(regular_dict)
    
            if od:  # Only test if not empty
                target_key = next(iter(od))
                original_value = od[target_key]
    
                od.move_to_end(target_key, last=False)
    
                assert list(od.keys())[0] == target_key
                assert od[target_key] == original_value
    
        def test_thread_safety_considerations(self):
            """Test basic thread safety considerations (single-threaded test)."""
            import threading
            import time
    
            od = OrderedDict([(i, f"value_{i}") for i in range(100)])
            results = []
            errors = []
    
            def move_keys():
                try:
                    for i in range(0, 100, 10):
                        od.move_to_end(i, last=False)
                        time.sleep(0.001)  # Small delay to increase chance of race conditions
                    results.append("success")
                except Exception as e:
                    errors.append(e)
    
            # Run single-threaded test to verify no internal errors
            move_keys()
    
            assert len(results) == 1
            assert len(errors) == 0
            assert 90 in od  # Verify dict is still intact
    
        def test_string_representation_after_move(self):
            """Test that string representation is correct after move_to_end."""
            od = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
    
            od.move_to_end("b", last=False)
    
            # Check that repr/str work and show correct order
            repr_str = repr(od)
            assert "'b'" in repr_str
    
            # Convert back to list to check order is maintained in representation
            items_from_repr = list(od.items())
            assert items_from_repr[0] == ("b", 2)

    🚀React with 🚀1Reacted by 🇺🇦 Sviatoslav Sydorenko (Святослав Сидоренко)
20. bluetech commented on May 26, 2025

    

    bluetech

    on May 26, 2025

    Member

    More actions

    So given there is a PyPy bug (still super surprised by this, this definitely goes on the pytest Wall of Bugs, along with this cpython crasher), maybe we should workaround it?

    @mgorny

    i.e. just inline move_to_end(last=False) (unless I messed the logic up).

    I'm afraid it is messed up - not doing anything with new_dict.

    Using the "new dict and assign" strategy is problematic because the type of other_scoped_items_by_argkey is Mapping which doesn't allow mutation (even though it's actually a dict, type checker will complain). This is a property I'd like to preserve. So I think we want a "backup, clear and update" strategy. That's a bit gruesome but I at least can't think of a more efficient alternative to move_to_end(last=False). I will send a PR.

    👀React with 👀1Reacted by Pierre Sassoulas
21. bluetech

    added 3 commits that reference this issue on May 26, 2025

    fixtures: workaround PyPy bug which sometimes causes a `KeyError` cra…

    ...

    This issue will close once commit 82ba788 is merged into the 'main' branch.

    82ba788

    fixtures: workaround PyPy bug which sometimes causes a `KeyError` cra…

    ...

    This issue will close once commit aff35e6 is merged into the 'main' branch.

    aff35e6

    fixtures: workaround PyPy bug which sometimes causes a `KeyError` cra…

    ...

    This issue will close once commit 1fdcf68 is merged into the 'main' branch.

    1fdcf68
22. bluetech

    closed this as completedin #13442on May 28, 2025
23. github-project-automation

    moved this from 🕵️ Rabbit hole maze 🕵 to 🌈 Done 🦄 in 📅 Procrastinating in public 😵‍💫on May 28, 2025
24. luketainton

    added a commit that references this issue on Jan 5, 2026

    chore(deps): update dependency pytest to v9 (#305)

    ...

    4b75154