Skip to content

join_k_path_into leaves two values on one key when shortened keys collide #84

Description

@adamv-symbolica

LineListNode::drop_head_dyn (line_list_node.rs ~2610): when byte_cnt is shorter than both keys, the node is
reused with both keys shortened in place — with no check that the shortened keys are now equal. Two value
slots end up on the same key: a path with two values.

map = {aaaa, acaa}
map.write_zipper().join_k_path_into(3, false);
map.iter()      -> ["a"]      // iteration visits the path once
map.val_count() -> 2          // both slots are counted

Downstream, PR #31's recursive cata hits its Case 7 debug_assert!(key1.len() > 1) on such nodes (that is how
the edit program found it); validate_node does not reject two value slots with identical keys, only two
children. The child/child and value/child collisions are handled correctly.

Fix: when the shortened keys coincide and both slots are the same kind, merge them — pjoin the two values
(or the two children) into a single slot; a value and a child on one key is the legal representation and is left
alone. Consider also teaching validate_node to reject two value slots on one key.

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