This was introduced in scala#23769 but it makes the following test fail: https://github.com/scala/scala3/blob/48bc891bd317a62956dc86297feb6e86a73083f6/tests/run/t4954.scala#L8

This was introduced in scala#23769 but it makes the following test fail: https://github.com/scala/scala3/blob/48bc891bd317a62956dc86297feb6e86a73083f6/tests/run/t4954.scala#L8

This was introduced in scala#23769 but it makes the following test fail: https://github.com/scala/scala3/blob/48bc891bd317a62956dc86297feb6e86a73083f6/tests/run/t4954.scala#L8

This was introduced in scala#23769 but it makes the following test fail: https://github.com/scala/scala3/blob/48bc891bd317a62956dc86297feb6e86a73083f6/tests/run/t4954.scala#L8

This was introduced in scala#23769 but it makes the following test fail: https://github.com/scala/scala3/blob/48bc891bd317a62956dc86297feb6e86a73083f6/tests/run/t4954.scala#L8

Fixed in #23769. Closes #23225.

Fixed in scala#23769. Closes scala#23225.

Fixed in scala#23769. Closes scala#23225.

…trict/lazy KeySet implementations (#24767)

Fixes #24749.

The PR contains two parts, one tiny and the other more involved.

## `KeySet` performance issues

Previously we use a `List[K]` to hold keys inside the strict KeySet, in
order to
keep 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 `KeySet` as a whole and use our private implementations
instead

As 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 to `MapOps.GenKeySet` in
#23769 was never
backwards-compatible -- it creates abstract getters and setters for the
`allKeys` val.**

This however clashes with how `.keySet` method was implemented: it
returns a `Set[K]`, but
provides _no_ guarantee on whether it is a lazy view over the underlying
data structure
(which _can_ be lazy, e.g. when you call `.keySet` from a `MapView`) 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 `.keySet` method
was called from an
already strict data-structure (which is the majority case) - returning a
thin-wrapper `LazyKeySet`
in 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.HashSet`
overrides `.keySet` with their own (protected!) classes, extending from
the previously-ambiguous
KeySet 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 `HashMap` to be extended with a custom
`KeySet`, and in the cases that
it does, it is not a problem to reimplement the missing 4-5 methods in
the most efficient way for your
extended data structure.