Consider use of IndexMap::(swap_)remove and IndexSet::(swap_)remove

[clubby789]

#120454 (comment)

indexmap 2.2.0 made the remove methods deprecated, as they forward directly to swap_remove. #120454 will update these callsites to use swap_remove, but we should consider if this is the correct behaviour. Alternatives are shift_remove (invalidating existing indexes) or using a different map.

[RalfJung]

For the map that appears in the interpreter, this used to be an FxHashMap but someone made it an IndexMap... it is a map we need to remove from though. I don't think we care about iteration order as long as it is deterministic, so why do we care about swap_remove vs shift_remove?

[cuviper]

If you only care about determinism, then either method will work, and swap is faster.

But some people were surprised by the change in order -- see: indexmap-rs/indexmap#241

[cuviper]

Another idea: if there are cases that do care about order but don't want to pay the price for shift_remove, or they need unperturbed indices, we could consider adding a wrapper to rustc_data_structures that removes by replacing with tombstones. I'd be happy to prototype that if there's a use case for it.

[Mark-Simulacrum]

If you only care about determinism, then either method will work, and swap is faster.

But some people were surprised by the change in order -- see: indexmap-rs/indexmap#241

I think shift has fewer requirements on determinism, right? Removal order doesn't need to be deterministic to preserve order amongst remaining elements in particular.

[cuviper]

Yeah, I suppose that's true -- shift_remove can happen in any order and still get the same remaining order.
(Assuming you're not mixing those removals with the otherwise deterministic inserts.)