Removing an element from a red-black tree sometimes modifies the remaining key-value pairs

[not-an-aardvark]

Using @collectable/red-black-tree@3.7.0 with Node 8.1.3:

const RBT = require("@collectable/red-black-tree");
let tree = RBT.empty();
tree = RBT.set(1, 'one', tree);
tree = RBT.set(3, 'three', tree);
tree = RBT.set(2, 'two', tree);
tree = RBT.remove(2, tree);

console.log(RBT.get(3, tree));

Expected output:

three

Actual output:

two

[axefrog]

Hey there, thanks for the pull requests! Interest in the library was relatively lacking, but I've actually got a tonne of fixes and a significant overhaul to the mutation API already implemented. Rather than committing them here though, I've been iterating more quickly via a copy of the code in a private repo in which it's being used, in order to iterate faster.

I can take some time to update the repo now that I know there's some genuine interest though, if you like. May I ask how you're planning on using it?

[not-an-aardvark]

Thanks for the response!

I've been working on a performance improvement to ESLint's indent rule. The improved version of the rule requires a balanced BST, but I've found surprisingly few good balanced BST implementations out there. I'm currently using functional-red-black-tree, but this isn't ideal because (a) it seems to be unmaintained, and (b) it only supports an immutable API, which is unnecessarily slow for my use case since I don't need immutability.

This library seems to be very well-written, and it would be great if I could use it in ESLint. In order for that to happen, I would need:

• ...Removing the last element from a mutable red-black tree results in incorrect behavior #43 and Removing an element from a red-black tree sometimes modifies the remaining key-value pairs #44 to be fixed.

  I originally noticed these issues because they were causing some of the indent tests to fail. With the patches from RBT(fix): update size when removing final node; fixes #43 #45 and RBT(fix): update node values when swapping contents; fixes #44 #46 applied, all the tests are passing, and there is a noticable performance improvement over functional-red-black-tree.

• ...this library to support Node 4.

  ESLint currently supports Node 4, so all of its dependencies would have to as well. There 5 places in the public version of the @collectable/red-black-tree package where default parameters or destructuring are used, which doesn't work in Node 4. Fixing these cases is basically a one-line addition, and I can make a PR for that if you'd like. (There are 42 such places in the entire collectable package. For ESLint I would only need @collectable/red-black-tree, but it might be convenient to have consistent Node version support across all the packages in this repo.)

[axefrog]

The Node 4 compatibility changes you mentioned shouldn't be an issue, though I'm curious about the rationale behind new ESLint development needing to support Node 4, given that even Node.js itself is up to version 6 for LTS. Shouldn't legacy users simply continue to use an older version of the ESLint npm package?

I've started moving my changes over to the Collectable repo, though there are some things that I've been putting off; specifically to do with updating Set, SortedSet, SortedMap and List to use the new mutation API, and updating the deep operations API to match all the changes I've made across the board. I could easily just push up RBT for you, but there is a chain of dependencies (collectable/core, frptools/core) that are affected as well, and the tooling I have set up is designed to update everything in tandem, which means manually updating/publishing RBT is somewhat more of a fiddly process to execute without inadavertently forgetting one step or another.

[not-an-aardvark]

The Node 4 compatibility changes you mentioned shouldn't be an issue, though I'm curious about the rationale behind new ESLint development needing to support Node 4, given that even Node.js itself is up to version 6 for LTS. Shouldn't legacy users simply continue to use an older version of the ESLint npm package?

The rationale is mostly due to timing -- I think Node 4 was still in LTS when we started working on prereleases for ESLint 4. There's a good chance we'll drop support for Node 4 in ESLint 5, but since the stable release of ESLint 4 just came out a month ago, we'll probably be supporting Node 4 for at least a few months until ESLint 5 comes out. (We try not to do major releases too frequently, since it's annoying for users to have to upgrade.)

I've started moving my changes over to the Collectable repo, though there are some things that I've been putting off; specifically to do with updating Set, SortedSet, SortedMap and List to use the new mutation API, and updating the deep operations API to match all the changes I've made across the board.

Thanks!

[axefrog]

I'll keep you posted. Feel free to bug me about it :-)

[axefrog]

Oh, I'm not sure how relevant this is to you, but the new version of RedBlackTree has a heavily upgraded iterator to allow fast-tracking traversal from one location to another, such as "next, where the key is greater than X". There is also a diffing function that you can use for easily performing set operations (intersect/subtract/union), and there are a few other handy functions as well.

[not-an-aardvark]

Sounds useful! Would that allow a faster way of deleting all nodes in a given range? Currently, I'm doing the equivalent of

let nextNode = RBT.find('gte', rangeStart, myTree);

while (nextNode.key < rangeEnd) {
    RBT.remove(nextNode.key, myTree);
    nextNode = RBT.find('gte', rangeStart, myTree);
}

But it seems like using iterators would be faster because I wouldn't have to do a bunch of repeated .find calls on the tree.

[axefrog]

Yes and no; you should not modify a mutable structure while iterating through it, however the persistent/immutable side of things would fit your use case nicely here. The internals of an immutable structure are shared by reference as much as possible, which means you can freeze the old version, clone it to a mutable copy, then iterate through the old one safely and use it as the basis for applying mutations to the copy. The freezing/copying process is very lightweight and does not incur the overhead that you'd normally have to think about when cloning a normal mutable data structure.

I've converted all of the collections now, and only have the deep mutations API left to fix.

[not-an-aardvark]

That makes sense. Out of interest, would it also work to avoid the iteration/mutation issue by storing a list of keys beforehand?

const keysToRemove = [];

for (const entry of /* entries starting with rangeStart */) {
    if (entry.key >= rangeEnd) {
        break;
    }
    keysToRemove.push(entry.key);
}

keysToRemove.forEach(key => RBT.remove(key, myTree));

[axefrog]

That would work, but it'd be less efficient because you'd be performing two iterations instead of one; first to iterate and find the keys to remove, and second to iterate and perform the removals.

[axefrog]

Ok it's all in, with new packages published. Readme files and so forth have not been updated at this stage. Let me know if you have any questions, and feel free to revise your pull requests after updating your code.

[not-an-aardvark]

Thanks!

Hmm, when I install @collectable/red-black-tree I get this error:

> require('@collectable/red-black-tree')

exports.NONE = new Node(core_1.Mutation.immutable(), anyVoid, anyVoid, false, anyVoid, anyVoid, 0);
                                       ^

TypeError: Cannot read property 'immutable' of undefined
    at Object.<anonymous> (/Users/tkatz/code/eslint/node_modules/@collectable/red-black-tree/lib/commonjs/internals/node.js:21:40)
    at Module._compile (module.js:569:30)
    at Object.Module._extensions..js (module.js:580:10)
    at Module.load (module.js:503:32)
    at tryModuleLoad (module.js:466:12)
    at Function.Module._load (module.js:458:3)
    at Module.require (module.js:513:17)
    at require (internal/module.js:11:18)
    at Object.<anonymous> (/Users/tkatz/code/eslint/node_modules/@collectable/red-black-tree/lib/commonjs/internals/RedBlackTree.js:4:16)
    at Module._compile (module.js:569:30)

I have the following installed:

├─┬ @collectable/red-black-tree@4.0.0
│ └─┬ @collectable/core@4.0.0
│   └── @frptools/core@2.4.0

[axefrog]

Yeah the dependencies seem to be out of sync. I'm fixing now.

[axefrog]

The packages are supposedly fixed, published and usable via npm... do you have any experience with Travis? For the life of me I can't figure out why it's trying to build with outdated dependencies, and all my attempts to reproduce the issue locally have failed.

https://travis-ci.org/frptools/collectable/jobs/252331327

[not-an-aardvark]

I'm not sure -- for what it's worth, I was able to build from a clean install using the same node and yarn version. Is it possible Travis is caching things somehow?

[not-an-aardvark]

When I tried installing on a machine where I'd previously built the old version, I ended up getting similar errors. I was able to fix these by running rm -rf .build/ packages/**/.build and building again.

I'm not sure why the .build folders would be present beforehand on the Travis server, though.

[axefrog]

Travis still failing. Going to try this suggestion and see if I can figure it out.

[axefrog]

Hey, I noticed you went with functional-red-black-tree in the end. If the reason for that is related to some aspect of my implementation, I'd welcome any feedback you have. Be as blunt as you like :D

[not-an-aardvark]

Hi, sorry about disappearing. There were a few reasons I ended up going with functional-red-black-tree:

• The original implementation of the PR from before I discovered this repo had used functional-red-black-tree, and I couldn't switch yet because there are still a few dependencies of @collectable/red-black-tree that fail with Node 4 (due to my error from ALL(style): support Node 4 #48 (comment)).
• I found an issue with the way I had been using functional-red-black-tree which caused the performance to be slower. After correcting it, the performance between functional-red-black-tree and @collectable/red-black-tree was about the same.
• I was a bit worried that switching to the new APIs from @collectable/red-black-tree would be confusing for other maintainers because the docs were out of date (for example, RedBlackTree.emptyWithNumericKeys wasn't documented yet).

As before, functional-red-black-tree isn't maintained, so I still think it would be nice to switch to @collectable/red-black-tree at some point (and I tried to use functional-red-black-tree in a way where it would be easy to change the underlying implementation). All of these reasons could be addressed with a bit of work, but I had limited time, so I decided to use functional-red-black-tree for the time being since it wasn't causing any problems.

[axefrog]

Ah ok, no worries, thanks for the feedback :-)

fwiw, my implementation of RBT is a first run at it. There may be numerous opportunities for performance optimisation that remain unexplored, should you ever be looking for a faster version. Fair points otherwise.

[axefrog]

Travis finally building. Node.js 4 removed from the build due to an external build dependency issue, though I think the reason for wanting to support Node.js 4 has gone away now anyway...