Skip to content

join / join_into panic when a DenseByteNode holds a dangling (empty-sentinel) child #81

Description

@adamv-symbolica

Version: master 4082402 (pathmap 0.4.0), debug build. Also present on PR #31's branch.

Summary. A no-prune remove_branches leaves a dangling path whose child slot is the empty sentinel
node. If the parent later upgrades to a DenseByteNode, the sentinel is carried into a CoFree rec, and
joining anything into that byte calls make_mut on the sentinel, which asserts. Dangling paths are a
documented feature (path_exists() stays true), so this is reachable from ordinary use.

Reproduction

use pathmap::PathMap;
use pathmap::zipper::*;

let mut m = PathMap::<()>::new();
for k in [b"ca".as_slice(), b"cb", b"d"] { m.set_val_at(k, ()); }
{ let mut wz = m.write_zipper(); wz.descend_to(b"c"); wz.remove_branches(false); } // "c" is now dangling
m.set_val_at(b"e", ());                     // root LineListNode upgrades to a DenseByteNode,
m.set_val_at(b"f", ());                     // carrying the sentinel child along

let mut other = PathMap::<()>::new();
other.set_val_at(b"ca", ());

let joined = m.join(&other);                // panics
// same via a write zipper:
// m.write_zipper().join_into(&other.read_zipper());

Expected: joined contains {ca, d, e, f} (4 values); join_into leaves m with the same content.

Actual:

panicked at src/trie_node.rs:3063:13:
Attempted to make_unique on an empty sentinel node

Frames: ByteNode::join_into_dynTrieNodeODRc::make_mutmake_unique
(reached via ByteNode::join_child_into / join_payload_into / merge_from_list_node from pjoin_dyn).

Notes. Without the upgrade (root still a LineListNode), the same join works, and meet / subtract handle
the sentinel in both node types — only the dense join path dereferences it as a real child.

Suggested fix. In the dense join path (ByteNode::join_child_intoTrieNodeODRc::join_into), treat an
empty-sentinel existing child as absent: replace it with the incoming subtrie instead of make_mut-ing it.
More generally, every make_mut on a child reached through a CoFree rec should be guarded by
!child.is_empty(), since remove_subtries (prune = false) deliberately installs the sentinel to represent a
dangling path.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions