[associative] Unexpected behavior when setting new values for a SortedMap created with initial values

[alexlurvey]

I noticed that calling 'set' on a SortedMap will have different behavior depending on whether or not the map was created with initial entries. For maps with initial entries, 'set' will sometimes apply the value to another key. It doesn't always do this, but you should notice different results in the example sandbox after running it a few times.

https://codesandbox.io/s/condescending-bell-vsbpyq?file=/src/index.ts

[postspectacular]

Thank you for spotting this @alexlurvey (also the sandbox is super helpful!) It's been a few years since I wrote that Skip-List impl, but will take a look asap!

[postspectacular]

@alexlurvey - I just finished a major rewrite of the .set() & .delete() methods, using an easier internal node structure and also easier to follow/debug now... Did a bunch of testing in the REPL, and will add some more tests. Right now it all seems to work reliably (also your example). Will release ASAP!

[alexlurvey]

@postspectacular Thank you. I appreciate all the effort. Everything checks out on my end after working with the new implementation. And, agreed, the new code is much easier to follow - I've got a decent grasp on how skip lists work now :)

[postspectacular]

Great! Meanwhile I also added a few more comments & released everything - thanks again! :)

https://github.com/thi-ng/umbrella/blob/develop/packages/associative/CHANGELOG.md

[alexlurvey]

@postspectacular I think I did find something else that's not quite right. Calling values() or entries() after updating some keys won't always produce the latest values: https://codesandbox.io/s/xenodochial-cache-22l2z2?file=/src/index.ts

[postspectacular]

@alexlurvey Hmm... so sorry, just proves that all the tests are still not sufficient... I will take another look ASAP, and I might after all implement the graphviz export to visualize the node structures (something I almost did in that last round, to help me debug)

[postspectacular]

I think I've fixed it (for real)! As you can see from the attached diagram, an update of an existing key currently only updated the first matching node in any of the "exress lane" skip lists, but not propagate the value to the lower levels.

So in this particular (random) configuration, if I update the "one" or "three" keys, it would only update the 2 bright green nodes (here with values 10 & 30), but not the ones connected via down links (e.g. the pale green nodes, which still have value 1). Updating the "two" key would work fine here, since this one is only stored on the lowest level...

I've already pushed the fix (see commit above), would be grateful if you could also test some more before I release...

[alexlurvey]

@postspectacular thanks for the explanation & diagram. I'll do some more through testing later today and report back. I'll also plan on filling out those test with some of my use cases.

[postspectacular]

@alexlurvey Noice & look forward hearing back! :)

[alexlurvey]

@postspectacular I think we're golden. I wired it up to the test fixture I'm working on (a list of UI inputs that can add or remove items depending on the selected value) and didn't experience any missing values.

[alexlurvey]

@postspectacular Hello again 😬 I think I may have found another item to fix after writing some more unit tests. I occasionally see TypeError: Cannot read properties of undefined (reading 'up') when calling 'set'. That's coming from this portion of the code (line 229):

// find nearest predecessor with up link
while (!node!.up) node = node!.prev;
node = node!.up;

When I change that to this, I'm able to run my test suite 100 times without failure:

while (node!.prev && !node!.up) {
    if (node!.prev) node = node!.prev;
}
node = node?.up ?? node;

I was trying to get branch setup to reproduce, but when running this in packages/associative I eventually get an "Unable to compile TypeScript" error with some issues in the sorted-map TS file. Probably a local issue though.

for i in {1..100}; do yarn test; if [[ "$?" != 0 ]]; then echo "Failed after $i attempts" && break; fi; done

[postspectacular]

@alexlurvey - mon dieu! :) Thank you for this - I think that insertion logic is fine as is since each lane should always have at least its heads vertically connected. Also I cannot reproduce the issue when only every calling .set(). It only seems to appear when you also delete keys, which means there's something wrong with the .delete() implementation, i.e. it's somewhere corrupting lanes to have no more head nodes... will be looking into it later today!

[postspectacular]

@alexlurvey one more round (please) & also added another fuzz test myself...

[alexlurvey]

@postspectacular this is working fine against my tests. I just ran them all 200 times - all green. Thanks!

[postspectacular]

Yeah, thank you for the speedy reply - that means I can push the new release(s) in the next 30 mins! 🚀

[postspectacular]

@alexlurvey Just in case you haven't seen it yet, I released the new version ~4h ago: https://mastodon.thi.ng/@toxi/109841142601682573

Thank you again for helping with fixing this! Gonna need that class soon myself again!