Skip to content

join_k_path_into / drop_head panic over a dangling (empty-sentinel) child #82

Description

@adamv-symbolica

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

Summary. With the same dangling-child construction as the report above, dropping head bytes fails at two
different sites depending on the parent node type.

Reproduction

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

fn dangling_c() -> PathMap<()> {
    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); drop(wz);
    m
}

// (a) DenseByteNode parent
let mut m = dangling_c();
m.set_val_at(b"e", ()); m.set_val_at(b"f", ());
m.write_zipper().join_k_path_into(1, false);   // panics; `drop_head(1)` panics identically

// (b) LineListNode parent (no upgrade)
let mut m = dangling_c();
m.write_zipper().join_k_path_into(1, false);   // debug_assert fails

Expected: the head byte is dropped from every downstream path (dangling paths included, or documented as
pruned); no panic.

Actual:

(a) panicked at src/trie_node.rs:3063:13:
    Attempted to make_unique on an empty sentinel node
    ByteNode::drop_head_dyn -> TrieNodeODRc::make_mut -> make_unique

(b) panicked at src/write_zipper.rs:2313:17:
    debug_assert!(!src.as_tagged().node_is_empty())      // in WriteZipperCore::graft_internal
    WriteZipperCore::join_k_path_into -> graft_internal(Some(<empty node>))

In (b) the merge of the downstream produced an empty node and join_k_path_into handed it to
graft_internal(Some(..)); release builds skip the assert and graft the sentinel as a child, violating the
invariant graft_internal relies on.

Suggested fix. (a) ByteNode::drop_head_dyn must skip (or treat as absent) children that are the empty
sentinel rather than make_mut-ing them. (b) WriteZipperCore::join_k_path_into should route an empty merge
result to graft_internal(None) (i.e. remove_branches) instead of graft_internal(Some(empty)).

Related. lean/FINDINGS.md §5 covers only join_k_path_into(0); §12 and §16 cover other dangling-path
failures, but neither of the two sites above is listed. Both bugs were found by a randomized write-zipper edit
program; a tests/-style file with these repros plus passing controls (join on the LineListNode variant,
meet/subtract on both) is available.

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