Validate (and fix) the RedBlackTree invariants#9326
Validate (and fix) the RedBlackTree invariants#9326mkeskells wants to merge 4 commits intoscala:2.12.xfrom
Conversation
1e4d1a7 to
5b8d9ae
Compare
|
is this a 2.12.13 blocker? (cc @retronym) |
I don't think that this has changed. We could test it in 2.12.12 release |
|
We believe this is a long standing behaviour. I'll look into it more today to confirm this -- if so it isn't a regression and wouldn't block 2.12.13. I'll also try to see if there it can actually manifest as incorrect behaviour. |
|
Okay, now I've refreshed my memory on Red Black Trees, I believe that the user-facing impact is "only" a potential performance problem where the worst case depth of the tree could be deeper than the guaranteed So far, @mkeskells has the "red cannot have a red parent" invariant can be broken in |
|
So I'm happy to defer a full investigation and fix for this until after 2.12.13. |
If we just use the invariants from retronyms memory there are more problems in the tree. The additional in the current code and the other references is that the top
In these (very limited tests) I don't see the "black-height" invariant broken (changing the root colour would not affect this). This is strange, as this was what I expected to see when I wrote the test as when looking at removal of an absent key. It looked from https://github.com/scala/scala/pull/9316/files#diff-84e7a7e45217aae6451467950e17274e241e1a672df4ad572334fd0e7104df98L1069 that the colour of the but this still allocates, so I added the identity check. This presumes that the colour of the leaf node was previously changing, which I am not seeing in the current test so either the tests are not good enough , or the presumption was wrong. My guess is the former |
|
I've added a pretty-printer for the internal structure of the RedBlack tree and some diagnostic code the record an ID and the creation stack trace of each node. These give a fuller picture of what the errant final tree looks like and what line of code created the errant subtree. Notice that the "bad' tree structural shares part of the original input tree. This might be the motivation for weakening the invariants for |
Looking at the code path here - this doesn't change the colour of the |
fix where the tree was invalid
5b8d9ae to
b962cf2
Compare
Example:
```
val s1 = TreeSet((1 to 64): _*)
s1.range(2, 63 + 1).tree.debugToString(Some(s1.tree))
```
```
BlackTree(32)
BlackTree(24)
RedTree(16)
BlackTree(12)
RedTree(8)
BlackTree(6)
RedTree(4)
BlackTree(3)
RedTree(2)
Empty
Empty
Empty
BlackTree(5) [shared]
Empty
Empty
BlackTree(7) [shared]
Empty
Empty
BlackTree(10) [shared]
BlackTree(9) [shared]
Empty
Empty
BlackTree(11) [shared]
Empty
Empty
BlackTree(14) [shared]
BlackTree(13) [shared]
Empty
Empty
BlackTree(15) [shared]
Empty
Empty
BlackTree(20) [shared]
BlackTree(18) [shared]
BlackTree(17) [shared]
Empty
Empty
BlackTree(19) [shared]
Empty
Empty
BlackTree(22) [shared]
BlackTree(21) [shared]
Empty
Empty
BlackTree(23) [shared]
Empty
Empty
BlackTree(28) [shared]
BlackTree(26) [shared]
BlackTree(25) [shared]
Empty
Empty
BlackTree(27) [shared]
Empty
Empty
BlackTree(30) [shared]
BlackTree(29) [shared]
Empty
Empty
BlackTree(31) [shared]
Empty
Empty
RedTree(48)
BlackTree(40)
BlackTree(36) [shared]
BlackTree(34) [shared]
BlackTree(33) [shared]
Empty
Empty
BlackTree(35) [shared]
Empty
Empty
BlackTree(38) [shared]
BlackTree(37) [shared]
Empty
Empty
BlackTree(39) [shared]
Empty
Empty
BlackTree(44) [shared]
BlackTree(42) [shared]
BlackTree(41) [shared]
Empty
Empty
BlackTree(43) [shared]
Empty
Empty
BlackTree(46) [shared]
BlackTree(45) [shared]
Empty
Empty
BlackTree(47) [shared]
Empty
Empty
BlackTree(56)
BlackTree(52)
BlackTree(50) [shared]
BlackTree(49) [shared]
Empty
Empty
BlackTree(51) [shared]
Empty
Empty
BlackTree(54) [shared]
BlackTree(53) [shared]
Empty
Empty
BlackTree(55) [shared]
Empty
Empty
BlackTree(60)
BlackTree(58)
BlackTree(57) [shared]
Empty
Empty
BlackTree(59) [shared]
Empty
Empty
BlackTree(62)
BlackTree(61)
Empty
Empty
BlackTree(63)
Empty
Empty
```
|
@mkeskells As discussed, I've pushed a commit that highlights structural sharing. I have also used this in a test case to pin down the amount of sharing we expect from |
468d315 to
f831c6f
Compare
f831c6f to
41d12d9
Compare
|
So where does this PR stand now? @retronym can you review the tail of this, or should we look for another reviewer? |
|
Oh, and it conflicts now, probably with something we merged just now. |
|
closing for inactivity — we can reopen if activity resumes |
@scala/collections anyone interested in (at minimum) opening a scala/bug ticket characterizing the issue, and/or (more ambitiously) resuming work on this...? enough time has passed that it's looking unlikely that either Mike or Jason will return to it |
It seems that we were generating invalid RedBlack trees
This PR add validation to test RedBlackTrees against the rules, fixes the trees that were invalid, and adds some debug support for detecting errors during development (commented out)
Other PRs will optimise these generated trees
Thanks to @retronym I have incorporated some of the debugging utilities from retronym#107