search

frptools / collectable

High-performance immutable data structures for modern JavaScript and TypeScript applications. Functional interfaces, deep/composite operations API, mixed mutability API, TypeScript definitions, ES2015 module exports.
MIT License
273 stars 14 forks source link

Break potential infinite loop #71

Closed eliranek1 closed 3 years ago

eliranek1 commented 3 years ago

Summary There is a race condition case where we're reaching an infinite loop when rebalancing. This only happens sometimes so it's hard to repro.

Tracked down the issue to isActive always being true in the rebalance while loop so it never exits.

IsActive: Path !== PathNode.NONE Release: Set Path.Node = NONE & Path.Parent = Cache

However, what's happening in the repro is that there is a "next" branch set on the path which causes isActive to always return true and never get out of the loop.

Set a breakpoint in the isActive check in the while loop: image

Notice that next is set on both parent path and the this path despite it getting released.

axefrog commented 3 years ago

Hey there, thanks for the PR! As you can see, I haven't worked on this library in quite a few years. In fact I just noticed I accidentally missed the other PR as well (submitted in 2019). I am happy to merge yours, but I am wondering if you could take a quick look at the other PR and tell me if I should merge that one before I merge yours? I don't even have this repository checked out right now, and the code is definitely not fresh in my mind ;-)

eliranek1 commented 3 years ago

@axefrog, I took a look at the PR and it seems ok, I don't see a specific need for it though or what use case it's solving. Also, I would prefer to have UTs for this before it's checked in. I left a comment. I would prefer to hold off on that if it isn't required.

For now, do you mind doing a closer review of mine and merging in if you don't see any issues with setting next to branch none when we reset?

axefrog commented 3 years ago

I have merged. I'll try to find some time to deploy a new copy to npm. May I ask, are you using this library a lot? Or just for a task you are working on?

eliranek1 commented 3 years ago

Thank you! Yes, we are using it quite extensively in our datastore. Specifically, the RB Tree as the structure for our in-memory provider: https://github.com/microsoft/ObjectStoreProvider

axefrog commented 3 years ago

Ah cool! The reason I asked was that I'd be open to a co-maintainer on the project, seeing as I'm very inactive with it at present. I may have time for it in the future, but right now I am focused on another big project, and this one has fallen by the wayside, as you can tell by the project's inactivity over the past few years. No pressure, just throwing it out there...

eliranek1 commented 3 years ago

@axefrog, I would love to! 👍

By the way, I missed upgrading the semver in package.json so the update never got published. I'll send one out in a few mins and add my name to the authors list.

Thanks! Excited to work on this!

axefrog commented 3 years ago

Hey, sorry for the long delay in reply. There are other, quicker ways to contact me if you'd like. My username also works with Gmail, Google Chat/Hangouts and Skype. I'm also on Discord if you prefer. Anyway, I have just published to npm. Contact me on another medium and I can give you npm publishing credentials, and we can have a quick chat about the setup I was using, if it would help. Also should I add you as a collaborator to the collectable repository, or do you prefer to go about this another way?