Deprecate MapOps.KeySet, replace with private (and more performant) strict/lazy KeySet implementations#24767
Conversation
|
It turns out that our change to I will make a commit that rolls back this change, add some |
|
Reference compiler is now 3.8.0-RC4 with #24273 backported, it should unblock this PR |
We need a data structure that both acts like a Set (queries membership efficiently), and has a stable iteration order. LinkedHashSet seems to fit this criteria.
LinkedHashMap's `keySet` has always been returning a LinkedKeySet, a private data structure that was extended from the generic MapOps.KeySet. Recently MapOps.KeySet was changed to a strict data structure, so we change the `keySet` method to use the lazy wrapper instead. Unfortunately we cannot change the hierarchy of `LinkedKeySet`, but the API never said we have to use it.
…base implementation This partially reverts `KeySet` and `GenKeySet` to their pre-capture-check implementation, with some unsafe annotations and a deprecation notice. This should cause MiMa to be happy with the previous implementations.
WojciechMazur
left a comment
There was a problem hiding this comment.
Looks good to me, but it would be nice to get second opinion from somebody more fluent with CC rules (@sjrd, @hamzaremmal)
It might be worth to create an issue for the remaining todo in collection.Map
Ah, ah, I don't speak CC at all. 🤣 |
| def contains(key: K): Boolean = | ||
| // TODO: I'm not sure what's happening here, need to investigate a bit further. | ||
| // But this check should be fine: we of course can use a MapOps here. | ||
| caps.unsafe.unsafeDiscardUses(this.get(key)).isDefined |
There was a problem hiding this comment.
@odersky could this be a compiler bug? Removing this unsafeDiscardUses will yield an use error on this, which is of course strange... But this error also only shows up after I added the unsafeDiscardUses on the current KeySet.
There was a problem hiding this comment.
I think the logic in the compiler is quite simple, probably a problem with setup. You could try to add a print to where discardUses is checked in markFree and see whether it triggers.
Fixes #24749.
The PR contains two parts, one tiny and the other more involved.
KeySetperformance issuesPreviously we use a
List[K]to hold keys inside the strict KeySet, in order tokeep iteration order stable. However this degrades performance of KeySet as a Set.
The fix is to simply use something that has both. Currently it means
mutable.LinkedHashSet,so we use it, even though we don't intend to mutate the set at all.
Deprecating
KeySetas a whole and use our private implementations insteadAs part of #23769 we categorised most data structures to be strict/pure (as in "not hiding any
computation as part of its structure"), which includes
Set. It turns out that our change toMapOps.GenKeySetin #23769 was never backwards-compatible -- it creates abstract getters and setters for theallKeysval.This however clashes with how
.keySetmethod was implemented: it returns aSet[K], butprovides no guarantee on whether it is a lazy view over the underlying data structure
(which can be lazy, e.g. when you call
.keySetfrom aMapView) or a strict set.With API compatibility in mind, we now create strict key sets (with a copy of the keys)
in the generic case, while trying to detect whether the
.keySetmethod was called from analready strict data-structure (which is the majority case) - returning a thin-wrapper
LazyKeySetin that case. As the LazyKeySet works like a view with no aggregation, applying it over a strict
data structure doesn't violate strictness.
This left a few holes however, which was overlooked: some data structures such as
mutable.HashSetoverrides
.keySetwith their own (protected!) classes, extending from the previously-ambiguousKeySet classes (that is now made strict), and accidentally ending up always using the strict version.
Unfortunately we cannot modify these extended classes (for TASTy compatibility), so similar versions
extending the thin wrapper are added instead, and the old classes deprecated.
To not shoot ourselves in the foot in the future, these classes are also made
private[collection]:We don't expect classes like
HashMapto be extended with a customKeySet, and in the cases thatit does, it is not a problem to reimplement the missing 4-5 methods in the most efficient way for your
extended data structure.