patricia: Insert loses an existing key when its proper prefix is inserted later

[sudeepdino008]

patricia.PatriciaTree.Insert loses an existing key when a proper prefix of it is inserted later:

var pt PatriciaTree
pt.Insert([]byte("0000"), []byte{48})
pt.Insert([]byte("0"), []byte{})
pt.root.get([]byte("0000")) // -> nil, false  (was inserted!)
pt.root.get([]byte("0"))    // -> [], true

All three MatchFinders walk the same tree, so the seg compressor silently drops dictionary patterns that have a shorter prefix-nested pattern inserted after them — slightly worse compression ratio, no corruption.

Repro: fuzz corpus entry db/seg/patricia/testdata/fuzz/FuzzLongestMatch/34174f1279b62c1e (added in #21625). The entry passes today only because the AC matcher is validated against a brute-force oracle instead of the tree-based matchers.

Found while working on #21625; the Aho-Corasick matcher introduced there is unaffected, but PatriciaTree.Insert itself (and MF1/MF2/MF3 consumers, e.g. pt.root.get) still has the bug.

[Sahil-4555]

Hey @sudeepdino008, I was going through this. Thought I'd share what I think i found.

So basically the issue is coming from pathWalker.insert - when a key ends in the middle of a compressed path (s.tail != 0), it calls s.diverge(0) to split the node. Now inside diverge, there's this check:

if divergence&0x80000000 == 0 {
    dn.p0 = divergence
    dn.p1 = s.tail

The thing is, when we're passing divergence == 0, this condition will always be true - 0 & 0x80000000 is always going to be 0. So the tail just blindly goes to p1 every single time, doesn't matter what the tail's leading bit actually is. Now if the tail starts with a 0-bit, it should naturally sit on p0, but nope - it gets shoved onto p1.

After this, when get tries to walk the tree for the longer key, it sees the next bit is 0, goes to check p0, finds nothing there, and gives up. The leaf node is actually still sitting in the tree - it's just that the path leading to it is on the wrong side. Key is there, but nobody can reach it.

I walked through the exact reproducer you gave - insert "0000" first, then "0". After the split, the intermediate node ends up with p0 = 0 (completely empty) and p1 = 0011000000110000001 (19 bits remaining from the longer path). But those 19 bits start with 0, so obviously any lookup would try p0 first. Nothing there. Done, key lost.

What I found interesting is - this only happens when the longer key goes in first and then the prefix comes later. If you do it the other way around (short key first, long key after), everything is fine because the tree builds top-down and diverge(0) never gets called in that case. And this is exactly the kind of pattern you'd see with prefix-nested dictionary entries during compression - the dictionary builder can easily produce a longer pattern before its prefix.

Also worth noting - diverge works perfectly fine for all non-zero divergence values. Those come from transition and represent actual bit-level divergences, so the side assignment logic makes complete sense there. The problem is only when insert passes 0, which isn't really a "divergence" - it's more like "just split here and keep the remaining path wherever it should go".

So one thing we could do is - instead of calling diverge(0) from insert, we handle the tail-splitting inline. Create the intermediate node directly and decide which side the tail goes on based on s.tail & 0x80000000 (the tail's own leading bit) rather than using the divergence value which is 0 and basically meaningless here. The rest of the bookkeeping (updating parent pointers, transferring the old child) stays similar to what diverge already does. No extra allocations, no special cases - just picking the right side. And diverge itself doesn't need touching since it works correctly for its actual callers.

About the impact - like you already mentioned in the issue, all three matchers walk the same broken tree, so MF1/MF2/MF3 all silently miss the lost patterns. This actually explains the mainnet difference you saw in #21625 - the AC matcher finds those prefix-nested patterns because it works directly on raw patterns and doesn't go through the tree's get path. Once the tree is fixed, both approaches should give the same results. No corruption risk though - compressor uses these patterns only as hints.

One small thing I also noticed - the existing FuzzPatricia test doesn't actually fail when ok == false for an inserted key. It only checks the value if ok is true. So even running the fuzzer for a long time wouldn't have caught this. Your fuzz corpus entry catches it only because the AC matcher gets validated against a brute-force oracle, not the tree-based matchers - nice catch there.

Happy to put up a PR for this if i am thinking in right direction. Let me know what you think.

cc: @awskii

[VBulikov]

yperbasis added Imp1 as Importance