The general logic in this function is:
- Build a stack that contains all of the complete subtrees contained
within the iterator.
- Take nodes off the top of the stack, and combine them together with
each other and empty nodes until the resulting right-hand subtree is
larger than all remaining subtrees on the stack.
- Make a single pass over the stack from bottom to top, accumulating
subtrees and adding empty nodes on the left until a single tree is
obtained.
The bug was that the second step was not leaving the right-hand subtree
sufficiently large. The final single-pass step expects every subtree in
the stack to be no smaller than the accumulated tree up to that point,
and in particular the right-hand subtree must be the direct right child
of the final tree. Some specific sequences of leaves were leaving the
right-hand subtree in a state where it was the same size as the largest
individual subtree of the rest of the stack, but smaller than their
accumulated tree.
The solution is to pre-compute what the address of the final tree will
be, and then add empty nodes on the right to the right-hand subtree
until it is the direct right child.
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
The logic in `LocatedPrunableTree::from_iter` is violating an invariant
of the `unite` helper function. The new assertion prevents an invalid
tree state from being returned.
After correcting for differing levels, the tree distance between indices
within a level was being computed via `u64::abs_diff`. This had failures
in cases where the indices were numerically close but the nodes were
much farther apart in the tree (e.g. adjacent non-sibling leaves).
The XOR distance is the correct metric to use here: the leading prefix
bits corresponding to the path from the tree root to the common ancestor
will be identical and thus zeroed out; the number of bits after that
gives the level difference between the compared indices and their common
ancestor.
The previous logic had the non-obvious behaviour that if the inserted
subtree was a leaf, then the `.iter().all()` was not rejecting subtrees
with non-matching values, because `Node::annotation` returns `None` for
leaves. This didn't cause a bug, because this behaviour is actually
intentionally triggered by the previous `is_complete` branch of the
conditional (as leaves are by definition complete subtrees).
The simplified logic is more obvious, because `PrunableTree::node_value`
returns the value of leaves and the annotation of nodes (which are the
same type for `PrunableTree`). It does change how leaves are treated by
this branch of the conditional, so a test has been added to ensure that
the intended behaviour is preserved if the `is_complete` branch is
refactored in future.
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
If we have a retained checkpoint at the same position and with the same
flags as a pruned checkpoint, we need to preserve the flags on the node.
The flags are cleared when the last of the checkpoints at the position
is removed.
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
The intent of SHARD_HEIGHT is that each subtree should contain
2^SHARD_HEIGHT nodes. The `ShardTree::subtree_level` function was
incorrectly computing the level of the root address, and consequently
the resulting subtrees were too small.
Jack Grigg
Kris Nuttycombe
Hazel OHearn
zancas
Nate Wilcox