Skip to content

Don't check key equality in RedBlackTree#8783

Merged
lrytz merged 1 commit intoscala:2.13.xfrom
szeiger:wip/rbt-key-equality
Apr 3, 2020
Merged

Don't check key equality in RedBlackTree#8783
lrytz merged 1 commit intoscala:2.13.xfrom
szeiger:wip/rbt-key-equality

Conversation

@szeiger
Copy link
Contributor

@szeiger szeiger commented Mar 3, 2020

This was left over from 2.12 when they old key would be overwritten.
The behavior changed in #7481 to
comply with the new map/set rules in
scala/bug#10415 (comment).

I would also call it wrong in 2.12 because equality should be defined
exclusively by the Ordering, but we should keep the current behavior
for compatibility reasons.

@szeiger
Don't check key equality in RedBlackTree
529e0e4 
This was left over from 2.12 when they old key would be overwritten.
The behavior changed in scala#7481 to
comply with the new map/set rules in
scala/bug#10415 (comment).

I would also call it wrong in 2.12 because equality should be defined
exclusively by the Ordering, but we should keep the current behavior
for compatibility reasons.
@scala-jenkins scala-jenkins added this to the 2.13.3 milestone Mar 3, 2020
@szeiger
Copy link
Contributor Author

szeiger commented Mar 3, 2020

based on a chat with @mkeskells who noticed the change when backporting the new RedBlackTree code

@mkeskells
Copy link
Contributor

mkeskells commented Mar 3, 2020

should this me marked [nomerge] or similar to avoid an automatic merge to 2.12 in the future?

@szeiger
Copy link
Contributor Author

szeiger commented Mar 6, 2020

We only merge forward, not backward.

@diesalbla diesalbla added the library:collections PRs involving changes to the standard collection library label Mar 17, 2020
@lrytz lrytz modified the milestones: 2.13.3, 2.13.2 Mar 30, 2020
@SethTisue
Copy link
Member

SethTisue commented Mar 31, 2020

this looks plausible, but I don't know the code well enough to easily do a proper review. is Mike's implied signoff enough? (and, should there be a test?)

@lrytz
Copy link
Member

lrytz commented Apr 3, 2020

This PR is only a cleanup, it doesn't change behavior. In 2.13.1:

scala> collection.immutable.TreeMap.apply(2 -> 2)(Ordering.by(x => x/2)).updated(3, 3)
res0: scala.collection.immutable.TreeMap[Int,Int] = TreeMap(2 -> 3)

Same with this PR:

scala> collection.immutable.TreeMap.apply(2 -> 2)(Ordering.by(x => x/2)).updated(3, 3)
val res0: scala.collection.immutable.TreeMap[Int,Int] = TreeMap(2 -> 3)

Whereas in 2.12.11

scala> collection.immutable.TreeMap.apply(2 -> 2)(Ordering.by(x => x/2)).updated(3, 3)
res0: scala.collection.immutable.TreeMap[Int,Int] = Map(3 -> 3)

@lrytz lrytz merged commit b51377f into scala:2.13.x Apr 3, 2020
@lrytz
Copy link
Member

lrytz commented Apr 3, 2020

The observable change is this:

scala> val s = collection.immutable.TreeSet(2)(Ordering.by(x => x/2))
val s: scala.collection.immutable.TreeSet[Int] = TreeSet(2)

scala> s eq (s + 3)
val res2: Boolean = true

in 2.13.1 this was false.

retronym added a commit to retronym/scala that referenced this pull request May 20, 2020
@retronym
Fixup RedBlackTree.upd merging error
c7927f4 
Erroneous commit was:

```
commit 2c620a7
Merge: abcde58 8270221
Author: Jason Zaugg <jzaugg@gmail.com>
Date:   Thu May 14 11:17:30 2020 +1000

    Merge commit '8270221567' into merge/2.12.x-to-2.13.x-20200514
```

According to scala#8783, which removed `|| k != tree.key`,
there was no behaviour change in 2.13.x, this was just a cleanup.
retronym added a commit to retronym/scala that referenced this pull request May 20, 2020
@retronym
[nomerge] Revert backported RBTree changes that are 2.13.x only
8e95fea 
Changes from:

   scala#7481
   scala#8783

Backported in:

scala@b87dd51#diff-f99536a3327e638dcf239518f2c3f0ceR195
scala@93afae7#diff-f99536a3327e638dcf239518f2c3f0ceL214

... are reverted. I've added a test for the legacy behaviour
that we don't want to break.
@retronym retronym mentioned this pull request May 20, 2020
Merged
hamzaremmal pushed a commit to hamzaremmal/scala3 that referenced this pull request May 2, 2025
@lrytz
Merge pull request scala/scala#8783 from szeiger/wip/rbt-key-equality
b88a6cb 
Don't check key equality in RedBlackTree
hamzaremmal pushed a commit to hamzaremmal/scala3 that referenced this pull request May 2, 2025
@retronym
Fixup RedBlackTree.upd merging error
4593b1e 
Erroneous commit was:

```
commit b42349c
Merge: 481bb48 a41e72c
Author: Jason Zaugg <jzaugg@gmail.com>
Date:   Thu May 14 11:17:30 2020 +1000

    Merge commit 'a41e72c988' into merge/2.12.x-to-2.13.x-20200514
```

According to scala/scala#8783, which removed `|| k != tree.key`,
there was no behaviour change in 2.13.x, this was just a cleanup.
hamzaremmal pushed a commit to hamzaremmal/scala3 that referenced this pull request May 2, 2025
@retronym
[nomerge] Revert backported RBTree changes that are 2.13.x only
00c31a7 
Changes from:

   scala/scala#7481
   scala/scala#8783

Backported in:

scala/scala@3b637df#diff-f99536a3327e638dcf239518f2c3f0ceR195
scala/scala@1b39caf#diff-f99536a3327e638dcf239518f2c3f0ceL214

... are reverted. I've added a test for the legacy behaviour
that we don't want to break.
hamzaremmal pushed a commit to scala/scala3 that referenced this pull request May 7, 2025
@lrytz
Merge pull request scala/scala#8783 from szeiger/wip/rbt-key-equality
0a9ecfd 
Don't check key equality in RedBlackTree
hamzaremmal pushed a commit to scala/scala3 that referenced this pull request May 7, 2025
@retronym
Fixup RedBlackTree.upd merging error
3040f8a 
Erroneous commit was:

```
commit 3bb47b3
Merge: b3ffa32 35910d2
Author: Jason Zaugg <jzaugg@gmail.com>
Date:   Thu May 14 11:17:30 2020 +1000

    Merge commit '35910d2a8a' into merge/2.12.x-to-2.13.x-20200514
```

According to scala/scala#8783, which removed `|| k != tree.key`,
there was no behaviour change in 2.13.x, this was just a cleanup.
hamzaremmal pushed a commit to scala/scala3 that referenced this pull request May 7, 2025
@retronym
[nomerge] Revert backported RBTree changes that are 2.13.x only
d93c379 
Changes from:

   scala/scala#7481
   scala/scala#8783

Backported in:

scala/scala@9bfb183#diff-f99536a3327e638dcf239518f2c3f0ceR195
scala/scala@48809df#diff-f99536a3327e638dcf239518f2c3f0ceL214

... are reverted. I've added a test for the legacy behaviour
that we don't want to break.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

library:collections PRs involving changes to the standard collection library

Projects

None yet

Milestone

2.13.2

Development

Successfully merging this pull request may close these issues.

6 participants

@szeiger @mkeskells @SethTisue @lrytz @scala-jenkins @diesalbla