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.
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
Expected: the head byte is dropped from every downstream path (dangling paths included, or documented as
pruned); no panic.
Actual:
In (b) the merge of the downstream produced an empty node and
join_k_path_intohanded it tograft_internal(Some(..)); release builds skip the assert and graft the sentinel as a child, violating theinvariant
graft_internalrelies on.Suggested fix. (a)
ByteNode::drop_head_dynmust skip (or treat as absent) children that are the emptysentinel rather than
make_mut-ing them. (b)WriteZipperCore::join_k_path_intoshould route an empty mergeresult to
graft_internal(None)(i.e.remove_branches) instead ofgraft_internal(Some(empty)).Related.
lean/FINDINGS.md§5 covers onlyjoin_k_path_into(0); §12 and §16 cover other dangling-pathfailures, 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 (joinon the LineListNode variant,meet/subtracton both) is available.