@lrytz deprecated overriding of SeqMap#keys may have been hasty. IF it is useful (a big IF), it is usefully specialized. WDYT?

#10544

FWIW the deprecation has been mildly inconvenient for us:
https://github.com/scala-js/scala-js/blob/28366eab2923a5807f02d421871eeb1dfaaf0ae3/project/Build.scala#L1789
https://github.com/scala-js/scala-js/blob/28366eab2923a5807f02d421871eeb1dfaaf0ae3/library/src/main/scala-new-collections/scala/scalajs/js/WrappedDictionary.scala#L102

I think either keys is an alais of keySet, or we guarantee additional properties. I assume these would be "strict copy" and "same iteration order for ordered / sorted maps"? Maybe we can add overrides that reutrn Seq after SIP-51, but even without that the properties can be expressed in scaladoc and tests, and it's clear whether something is a bug or not.

Doing something in between can probably avoid some surprises but not really prevent bugs.

Not sure if lrytz agreed to undeprecate, so I pushed it as a separate commit, unsquashed. Sorry, Jenkins.

To be clear, this PR was motivated by Ichoran's endorsement on the ticket, that even if keys is not (yet) Seq, go ahead and change it to return one anyway, as nobody could possibly be relying on the current behavior.

with nobody being the wiser for it

I can report that I do not feel wiser.

I see the point that returning a Seq doesn't hurt and can prevent surprises.

But if we don't actually guarantee anything then the value is very limited, surprises when using keys are just delayed.

I think either keys should be a final / deprecatedOverriding alias, or it should have documented properties that clients can rely on, anything in between is useful only by accident. But changing keys to always return a strict Seq copy is a (performance) breaking change, so it's not clear whether we can do that.

This is only for SeqMaps that don't yet override. It could be restricted further to SeqMap1..4, to be more conservative.

Then we can sort whether it's useful API etc under SIP-51.

Otherwise, I'll have to at-notify Ichoran.

it's not clear what the API intends:

      assertEquals(/*"Expect the same keys to appear in the join taken either way around.",*/
        ourChanges.mergeByKey(theirChangesRedux).keySet,
        theirChangesRedux.mergeByKey(ourChanges).keys,
      )

@som-snytt where does this stand, in your opinion?

also interested in @scala/collections opinions

Doing something in between can probably avoid some surprises but not really prevent bugs.

This standard is too high for me.

I'm pretty sure I've mentioned this before somewhere, but I'd personally prefer that keys be of the as-yet-nonexistent type SeqSet.

I would also like keys in general to be an alias of keySet (maybe eventually the primary and later only method!)

I don't remember why I reopened, but probably because Seth said

if anyone else cares enough

which is nerd-sniping as moral imperative.

I'll refresh my memory and the branch.

I see the trouble began with this spurious override in VectorMap:

override def keys: Vector[K] = keysIterator.toVector

The override would make sense on grounds of efficiency, but per the docs, anyone who wants this behavior should write it out.

Lukas's comment is that the doc for keys must specify its guarantee.

If keys are ordered,

c.keys.iterator.sameElements(c.keySet.iterator)

Addtionally, keySet is ordered if the collection is sorted.

It is a non-goal of this PR to guarantee that keys returns a Set. That is what keySet is for. If you want a set that preserves iteration order, then the doc could show how to build that, too.

As an example, ListMap yields a list of keys. If you want an unordered set, use keys.toSet, or keySet for ordered keys.

The only reason to prefer keys.iterator to keySet.iterator is when it's more efficient for unsorted keys. (Speculation.)

I see the ticket is about checking equality. That is an especially weak expectation. Rex suggests the solution in this PR, just make keys return a Seq. But if the purpose of keys is "give me cheap iteration order", then producing a Seq is not desirable. That is Lukas's point about a performance regression, which would be severe for large maps. (The ticket is about tiny maps.)

When I touch the code, perhaps my perspective will change, and I'll note that here.

The Ichoranism on scala/bug#12808

promise less, but make it work

That is just java.io.IOException: No space left on device

This PR will be squashable: it reverts the deprecated overriding, adds clarifying doc, and also slips in the Ichoranist "make it work" because why not. That calls for a mima exception for the private object, which I did not drill into during this expedition.

Note to self: I ran sbt:scala2> library/mimaReportBinaryIssues locally but was somehow careless and thought it said I was OK without an exclusion (because I had changed the signature?). Now I see the correct report, so I don't know what my mistake was.

I gave it some thought again, because what else are the winter holidays for, and I wavered a moment about whether to keep the deprecation of keys. Also, I noticed that in Java, Dictionary has keys (an Enumeration) but Map has keySet.

There is no justification for keys in the standard library, assuming ListMap is always small. The important optimization via retronym is to override keysIterator and avoid Map#iterator which produces (k,v).

The clever pattern is that keySet delegates to keysIterator, which could be protected, if you guarantee keySet.iterator preserves order. Maybe the thinking was that unsorted set does not let you make that guarantee?

It occurs to me that SeqMap could be a SortedMap with an Ordering that reports arrival order, which would solve this API question. That would be for a future version.

Is there a big risk that existing custom maps would violate the new iteration order guarantee?

as far as I can see, it should be sufficient to release-note it to give custom map implementers the heads-up

@som-snytt mind giving the PR title and description your best user-facing, included-in-release notes effort?

The reading list is my discursive comment from the winter holiday followed by my archeological investigation from the Thanksgiving break.

Edit: I feel the need to add, "But don't tell them I told you that."

Ah, I didn't read far enough back in the discussion.

I only re-opened because Seth

#10766 (comment)

but it's impossible to meet the standard set by

#10766 (comment)

My opinion would have been just to revert the deprecation, but I don't have actual opinions like Ichoran and NthPortal.

#10766 (comment)

This is way too much discussion driven by one user misusing the API (which may be open to abuse).

I may also have re-opened just for trailing karma.