Insert the item rather than its key in bisect.insort - #8565

• This PR follows our AI policy

Summary

bisect.insort with a key stores what the key returned instead of the object it was given:

>>> words = ["a", "ccc"]
>>> bisect.insort(words, "bb", key=len)
>>> words
['a', 2, 'ccc']                 # CPython: ['a', 'bb', 'ccc']

>>> pairs = [(1, "a"), (3, "b")]
>>> bisect.insort(pairs, (2, "x"), key=lambda pair: pair[0])
>>> pairs
[(1, 'a'), 2, (3, 'b')]         # CPython: [(1, 'a'), (2, 'x'), (3, 'b')]

The item is not misplaced, it is gone. A list of strings comes back holding an int, a list of tuples comes back holding the field the key read, and key=abs quietly turns -2 into 2.

insort_left and insort_right in crates/stdlib/src/bisect.rs rebind x to key(x) and then pass that same value to the search and to a.insert. CPython computes the key for the search and inserts the original object. insort is insort_right, so all three names carry it.

The key is still called once on the new item, which is what CPython does too.

Why the suite is green

Lib/test/test_bisect.py passes on main. test_insort uses abs as its key function and asserts only that the target list stays sorted by that key. Since abs(abs(x)) == abs(x), inserting the key instead of the item preserves the property the test measures, and nothing there ever compares the elements against what was passed in.

Test Plan

Built in a Debian container on rustc 1.98.0.

• New snippet extra_tests/snippets/stdlib_bisect.py. It fails on main at the first assertion, with AssertionError: ('insort_right', ['a', 2, 'ccc']), and passes with this change. Verified both ways by stashing only the Rust file and rebuilding.
• pytest test_snippets.py -k stdlib_bisect in extra_tests, both legs green: the snippet runs under CPython 3.14.7 and under this build.
• cargo run --release -- -m test test_bisect: 46 tests, SUCCESS.
• cargo clippy with the flags from CI, clean, and cargo fmt --check clean. ruff format --check and ruff check --select I clean on the snippet.
• cargo test --workspace --exclude rustpython_wasm --exclude rustpython-venvlauncher --exclude rustpython-capi: no failures.

The clippy and WASM jobs are red here for the reason in #8564, which is unrelated to this change.

Summary by CodeRabbit

• Bug Fixes

  • Improved keyed insertion so objects are searched using their key while preserving the original object during insertion.
  • Ensured insertion keys are evaluated only once.
  • Preserved stable left/right placement for equal values and correct behavior for bounded or descending searches.

• Tests

  • Added coverage for keyed and plain insertion, bisect operations, ordering, and key evaluation behavior.