2bc41aeb8602
lookups.rs
//! The batched lookups ([`Document::index_paths`], `node_at`, `node_mut_at`, `ancestry_at`) agree
//! with the one-id ones on nested trees with missing and duplicated ids, and the edits of many nodes
//! ([`Document::remove_many`], `wrap`, `insert_beside`) leave the tree that `remove`, `insert` and
//! `move_node` leave one node at a time.
use crate::*;
use vectorcraft_geom::shapes;
/// Layers with paths and groups nested `depth` deep; every 7th id is reused (a damaged file), so
/// first-in-tree-order matters.
fn tree(seed: u64) -> (Document, Vec<NodeId>) {
let mut d = Document::new(612.0, 792.0);
let mut r = seed | 1;
let mut next = |n: u64| {
r ^= r << 13;
r ^= r >> 7;
r ^= r << 17;
r % n
};
let mut ids = vec![];
let leaf = |d: &mut Document, ids: &mut Vec<NodeId>| {
let id = if ids.len() % 7 == 6 { ids[ids.len() / 2] } else { d.alloc_id() };
ids.push(id);
Arc::new(Node::path(id, shapes::rectangle(Rect::new(0.0, 0.0, 5.0, 5.0)), Appearance::default_art()))
};
for l in 0..3 {
let lid = d.alloc_id();
let mut layer = Node::layer(lid, &format!("L{l}"), LayerColor::Preset(0));
ids.push(lid);
for _ in 0..(5 + next(10)) {
let child = if next(3) == 0 {
let mut inner: Vec<Arc<Node>> = (0..(1 + next(4))).map(|_| leaf(&mut d, &mut ids)).collect();
for _ in 0..next(3) {
let gid = d.alloc_id();
ids.push(gid);
inner = vec![Arc::new(Node::group(gid, inner))];
}
let gid = d.alloc_id();
ids.push(gid);
Arc::new(Node::group(gid, inner))
} else {
leaf(&mut d, &mut ids)
};
if let Some(ch) = layer.children_mut() {
ch.push(child);
}
}
d.layers.push(Arc::new(layer));
}
ids.push(NodeId(999_999)); // not in the tree
(d, ids)
}
#[test]
fn batched_lookups_match_one_at_a_time() {
for seed in 1..40 {
let (d, ids) = tree(seed);
let paths = d.index_paths(ids.iter().copied());
for id in &ids {
assert_eq!(paths.get(id).cloned(), d.index_path(*id), "seed {seed} id {id:?}");
let p = paths.get(id);
assert_eq!(p.and_then(|p| d.node_at(p)).map(|n| n as *const Node), d.node(*id).map(|n| n as *const Node), "seed {seed} node {id:?}");
assert_eq!(p.and_then(|p| d.ancestry_at(p)), d.ancestry(*id), "seed {seed} ancestry {id:?}");
}
// A subset, and nothing.
let some: Vec<NodeId> = ids.iter().copied().step_by(3).collect();
let sub = d.index_paths(some.iter().copied());
assert!(some.iter().all(|id| sub.get(id).cloned() == d.index_path(*id)));
assert!(d.index_paths(std::iter::empty()).is_empty());
// Mutable access reaches the same node as node_mut, copy-on-write.
let mut a = d.clone();
let mut b = d.clone();
for id in ids.iter().step_by(5) {
if let Some(n) = a.node_mut(*id) {
n.opacity = 0.25;
}
if let Some(n) = d.index_path(*id).and_then(|p| b.node_mut_at(&p)) {
n.opacity = 0.25;
}
}
assert_eq!(serde_json::to_string(&a).ok(), serde_json::to_string(&b).ok(), "seed {seed}");
}
}
/// What a walk of the tree gives for every id, checked against the cached lookups.
fn agree(d: &Document, ids: &[NodeId], what: &str) {
agree_except(d, ids, None, what);
}
/// [`agree`], except for `dup`, an id given a second node after the cache was built: lookups of it
/// may return either of its nodes (see `id_index`), but always one with that id.
fn agree_except(d: &Document, ids: &[NodeId], dup: Option<NodeId>, what: &str) {
if let Some(dup) = dup {
assert_eq!(d.node(dup).map(|n| n.id), Some(dup), "{what}: node {dup:?} has its id");
}
let ids: Vec<NodeId> = ids.iter().copied().filter(|id| Some(*id) != dup).collect();
let ids = &ids[..];
for id in ids {
let walked = d.walk_index_path(*id);
assert_eq!(d.index_path(*id), walked, "{what}: index_path {id:?}");
let by_walk = walked.as_deref().and_then(|p| d.node_at(p)).map(|n| n as *const Node);
assert_eq!(d.node(*id).map(|n| n as *const Node), by_walk, "{what}: node {id:?}");
}
let batched = d.index_paths(ids.iter().copied());
for id in ids {
assert_eq!(batched.get(id).cloned(), d.walk_index_path(*id), "{what}: index_paths {id:?}");
}
}
/// The id cache never answers differently from a walk, however the tree is changed behind its
/// back (through the public fields), including in a clone that shares the cache.
#[test]
fn cached_lookups_follow_any_edit_of_the_tree() {
for seed in 1..30 {
let (mut d, ids) = tree(seed);
agree(&d, &ids, "fresh");
let snapshot = d.clone(); // shares the cache
// Insert at the front of the first layer: every path in it shifts.
let extra = d.alloc_id();
let leaf = Arc::new(Node::path(extra, shapes::rectangle(Rect::new(0.0, 0.0, 1.0, 1.0)), Appearance::default_art()));
if let Some(ch) = Arc::make_mut(&mut d.layers[0]).children_mut() {
ch.insert(0, leaf.clone());
}
let mut all = ids.clone();
all.push(extra);
agree(&d, &all, "inserted at the front");
// Remove a child, swap two, and move one into another layer.
if let Some(ch) = Arc::make_mut(&mut d.layers[1]).children_mut()
&& ch.len() > 3
{
ch.remove(1);
ch.swap(0, 2);
}
let moved = Arc::make_mut(&mut d.layers[2]).children_mut().and_then(|ch| (!ch.is_empty()).then(|| ch.remove(0)));
if let Some(m) = moved
&& let Some(ch) = Arc::make_mut(&mut d.layers[0]).children_mut()
{
ch.push(m);
}
agree(&d, &all, "removed, swapped and moved");
// A new duplicate of an existing id, earlier in tree order than the original.
let dup = ids[ids.len() / 3];
let copy = Arc::new(Node::path(dup, shapes::rectangle(Rect::new(0.0, 0.0, 2.0, 2.0)), Appearance::default_art()));
if let Some(ch) = Arc::make_mut(&mut d.layers[0]).children_mut() {
ch.insert(0, copy);
}
agree_except(&d, &all, Some(dup), "a duplicate inserted earlier");
// Delete a whole layer, then look everything up again, missing ids included.
d.layers.remove(1);
agree_except(&d, &all, Some(dup), "a layer deleted");
// A rebuilt cache (as after loading a file) knows the duplicate and walks for it.
let mut fresh = d.clone();
fresh.layers = d.layers.clone();
fresh.index = Default::default();
agree(&fresh, &all, "a damaged tree, cached afresh");
// The clone made before all this still answers for its own tree.
agree(&snapshot, &ids, "the earlier clone");
}
}
/// Every node whose id is in `ids`, by walking the tree.
fn every_node(d: &Document, ids: &[NodeId]) -> Vec<*const Node> {
let mut out = vec![];
d.walk(|n| {
if ids.contains(&n.id) {
out.push(n as *const Node);
}
});
out
}
/// [`Document::nodes_in_order`] gives every node with each id in tree order, repeated ids
/// included, with the cache built and without it, for a few ids (cached paths) and for many (a
/// walk).
#[test]
fn nodes_in_order_match_a_walk() {
for seed in 1..40 {
let (d, ids) = tree(seed);
let few: Vec<NodeId> = ids.iter().copied().step_by(17).collect();
for cold in [true, false] {
if cold {
d.drop_lookup_cache();
} else {
d.node(ids[0]);
}
for list in [&ids[..], &few[..], &ids[ids.len() / 2..ids.len() / 2 + 1], &[]] {
let found: Vec<*const Node> = d.nodes_in_order(list.iter().copied()).into_iter().map(|n| n as *const Node).collect();
assert_eq!(found, every_node(&d, list), "seed {seed}, cold {cold}, {list:?}");
}
}
// An id that the tree repeats: every node with it.
let Some(dup) = ids.iter().enumerate().find(|(i, id)| ids[..*i].contains(id)).map(|(_, id)| *id) else { continue };
assert!(d.nodes_in_order([dup]).len() >= 2, "seed {seed}: {dup:?} is in the tree more than once");
// A second node given an id once held once, after the cache was built: the lookup finds the
// cached node, which has that id; with the cache built afresh, both.
let mut d = d;
let once = ids.iter().copied().find(|id| every_node(&d, &[*id]).len() == 1 && d.node(*id).is_some_and(|n| !n.is_layer()));
let Some(once) = once else { continue };
d.node(once);
let copy = Arc::new(Node::path(once, shapes::rectangle(Rect::new(0.0, 0.0, 2.0, 2.0)), Appearance::default_art()));
if let Some(ch) = Arc::make_mut(&mut d.layers[0]).children_mut() {
ch.insert(0, copy);
}
let found = d.nodes_in_order([once]);
assert!(!found.is_empty() && found.iter().all(|n| n.id == once), "seed {seed}: {once:?}");
d.drop_lookup_cache();
d.node(once);
let found: Vec<*const Node> = d.nodes_in_order([once]).into_iter().map(|n| n as *const Node).collect();
assert_eq!(found, every_node(&d, &[once]), "seed {seed}: {once:?} cached afresh");
}
}
/// Nodes of `d` picked and ordered by `seed`. None lies inside another, and each of them, and each
/// node it is in, appears in the tree once.
fn picks(d: &Document, seed: u64) -> Vec<NodeId> {
let mut count = std::collections::HashMap::<NodeId, usize>::new();
d.walk(|n| *count.entry(n.id).or_default() += 1);
let once = |id: &NodeId| count.get(id) == Some(&1);
let mut found: Vec<(Vec<usize>, NodeId)> = count
.keys()
.filter(|id| !(id.0 + seed).is_multiple_of(3))
.filter_map(|id| d.index_path(*id).map(|p| (p, *id)))
.filter(|(p, _)| d.ancestry_at(p).is_some_and(|a| a.iter().all(once)))
.collect();
found.sort();
let mut kept: Vec<(Vec<usize>, NodeId)> = vec![];
for (p, id) in found {
if !kept.iter().any(|(q, _)| p.starts_with(q)) {
kept.push((p, id));
}
}
let mut out: Vec<NodeId> = kept.into_iter().map(|(_, id)| id).collect();
out.sort_by_key(|id| id.0.wrapping_mul(0x9e37_79b9_7f4a_7c15) ^ seed);
out
}
/// `a` and `b` hold the same tree, and their lookups agree with each other and with a walk.
fn same(a: &Document, b: &Document, ids: &[NodeId], what: &str) {
assert_eq!(serde_json::to_string(a).ok(), serde_json::to_string(b).ok(), "{what}");
for id in ids {
assert_eq!(a.index_path(*id), b.index_path(*id), "{what}: {id:?}");
}
agree(b, ids, what);
}
/// A 1 pt square with a new id.
fn square(d: &mut Document) -> Node {
Node::path(d.alloc_id(), shapes::rectangle(Rect::new(0.0, 0.0, 1.0, 1.0)), Appearance::default_art())
}
#[test]
fn remove_many_matches_removing_one_at_a_time() {
for seed in 1..40 {
let (d, ids) = tree(seed);
let picked = picks(&d, seed);
let (mut a, mut b) = (d.clone(), d.clone());
let one: Vec<Arc<Node>> = picked.iter().map(|id| a.remove(*id).unwrap()).collect();
let many = b.remove_many(&picked).unwrap();
assert_eq!(many.len(), one.len(), "seed {seed}");
assert!(one.iter().zip(&many).all(|(x, y)| Arc::ptr_eq(x, y)), "seed {seed}: the same nodes, in the order of the list");
same(&a, &b, &ids, &format!("seed {seed}"));
}
}
#[test]
fn insert_beside_matches_inserting_one_at_a_time() {
for seed in 1..40 {
for replace in [false, true] {
let (mut d, mut ids) = tree(seed);
let picked = picks(&d, seed);
// None to three new nodes for each anchor.
let items: Vec<(NodeId, Vec<Node>)> =
picked.iter().enumerate().map(|(k, id)| (*id, (0..k % 4).map(|_| square(&mut d)).collect())).collect();
ids.extend(items.iter().flat_map(|(_, new)| new.iter().map(|n| n.id)));
let (mut a, mut b) = (d.clone(), d.clone());
for (id, new) in items.clone() {
let (parent, at, _) = a.position(id).unwrap();
let at = if replace {
a.remove(id).unwrap();
at
} else {
at + 1
};
for (k, n) in new.into_iter().enumerate() {
a.insert(parent, at + k, n).unwrap();
}
}
b.insert_beside(items, replace).unwrap();
same(&a, &b, &ids, &format!("seed {seed}, replace {replace}"));
}
}
}
#[test]
fn wrap_matches_inserting_a_group_and_moving_the_nodes_into_it_one_at_a_time() {
for seed in 1..40 {
let (mut d, mut ids) = tree(seed);
let picked = picks(&d, seed);
let Some(&last) = picked.last() else { continue };
let group = d.alloc_id();
ids.push(group);
let (mut a, mut b) = (d.clone(), d.clone());
let (parent, at, _) = a.position(last).unwrap();
a.insert(parent, at + 1, Node::group(group, vec![])).unwrap();
for id in &picked {
a.move_node(*id, Some(group), usize::MAX).unwrap();
}
assert_eq!(b.wrap(&picked, |nodes| Node::group(group, nodes)), Ok(group), "seed {seed}");
same(&a, &b, &ids, &format!("seed {seed}"));
}
}
/// An id not in the tree, listed twice, or inside another listed node fails with `NoNode`, and the
/// document stays as it was.
#[test]
fn edits_of_many_refuse_missing_repeated_and_nested_ids() {
let mut d = Document::new(612.0, 792.0);
let layer = d.layers[0].id;
let (x, y, z) = (square(&mut d), square(&mut d), square(&mut d));
let (inner, other) = (y.id, z.id);
let group = d.alloc_id();
d.insert(Some(layer), 0, Node::group(group, vec![Arc::new(x), Arc::new(y)])).unwrap();
d.insert(Some(layer), 1, z).unwrap();
let saved = serde_json::to_string(&d).ok();
let missing = NodeId(999_999);
for (list, bad) in [(vec![other, missing], missing), (vec![other, other], other), (vec![group, inner], inner), (vec![inner, group], inner)] {
let what = format!("{list:?}");
let mut b = d.clone();
assert_eq!(b.remove_many(&list).err(), Some(DocError::NoNode(bad)), "{what}");
assert_eq!(b.wrap(&list, |nodes| Node::group(NodeId(1_000_000), nodes)).err(), Some(DocError::NoNode(bad)), "{what}");
for replace in [false, true] {
let items = list.iter().map(|id| (*id, vec![])).collect();
assert_eq!(b.insert_beside(items, replace).err(), Some(DocError::NoNode(bad)), "{what}");
}
assert_eq!(serde_json::to_string(&b).ok(), saved, "{what}: the document stays as it was");
}
}
/// The nearest node passing `pred` at or above `id`, as `ancestry` read from the end with `node`
/// for each id finds it.
fn nearest_by_ancestry(d: &Document, id: NodeId, pred: impl Fn(&Node) -> bool) -> Option<*const Node> {
d.ancestry(id).unwrap_or_default().into_iter().rev().find_map(|a| d.node(a).filter(|n| pred(n))).map(|n| n as *const Node)
}
/// [`Document::nearest_finder`] gives what [`nearest_by_ancestry`] gives for every id, on a clone
/// each, so both start from the same cache.
fn nearest_agrees(d: &Document, ids: &[NodeId], what: &str) {
type Pred = fn(&Node) -> bool;
let preds: [(&str, Pred); 5] = [
("group", |n| matches!(n.kind, NodeKind::Group { .. })),
("layer", |n| n.is_layer()),
("any", |_| true),
("none", |_| false),
("id divisible by 3", |n| n.id.0 % 3 == 0),
];
for (name, pred) in preds {
let (a, b) = (d.clone(), d.clone());
let want: Vec<_> = ids.iter().map(|id| nearest_by_ancestry(&a, *id, pred)).collect();
let mut find = b.nearest_finder();
let got: Vec<_> = ids.iter().map(|id| find.nearest(*id, pred).map(|n| n as *const Node)).collect();
assert_eq!(got, want, "{what}: {name}");
}
}
#[test]
fn nearest_finder_matches_the_ancestry_walk() {
for seed in 1..30 {
let (mut d, ids) = tree(seed);
nearest_agrees(&d, &ids, "no cache");
d.node(ids[0]);
nearest_agrees(&d, &ids, "cached");
// Every path in the first layer shifts: the cache is stale there.
let extra = d.alloc_id();
let leaf = Arc::new(Node::path(extra, shapes::rectangle(Rect::new(0.0, 0.0, 1.0, 1.0)), Appearance::default_art()));
if let Some(ch) = Arc::make_mut(&mut d.layers[0]).children_mut() {
ch.insert(0, leaf);
}
nearest_agrees(&d, &ids, "a stale cache");
// A group with the id of a node in the last layer, earlier in tree order than it, put in
// after the cache was built.
d.drop_lookup_cache();
d.node(ids[0]);
let last = d.layers.len() - 1;
let dup = d.layers[last].children().and_then(|c| c.last()).map(|n| n.id);
if let Some(dup) = dup
&& let Some(ch) = Arc::make_mut(&mut d.layers[0]).children_mut()
{
ch.insert(0, Arc::new(Node::group(dup, vec![])));
}
nearest_agrees(&d, &ids, "a duplicate put in after the cache was built");
d.drop_lookup_cache();
nearest_agrees(&d, &ids, "a duplicate, cached afresh");
}
}
/// An id on the path that an earlier node of another kind also has: the earlier node is the one
/// tested, as `node` gives it.
#[test]
fn nearest_finder_tests_the_first_node_with_a_repeated_id() {
let mut d = Document::new(612.0, 792.0);
let layer = d.layers[0].id;
let leaf = |id: u64| Arc::new(Node::path(NodeId(id), shapes::rectangle(Rect::new(0.0, 0.0, 5.0, 5.0)), Appearance::default_art()));
d.insert(Some(layer), 0, Node::group(NodeId(500), vec![leaf(501)])).unwrap();
d.insert(Some(layer), 1, Node::path(NodeId(600), shapes::rectangle(Rect::new(0.0, 0.0, 5.0, 5.0)), Appearance::default_art())).unwrap();
// A group that has the path's id, after the path in tree order.
d.insert(Some(layer), 2, Node::group(NodeId(600), vec![leaf(601)])).unwrap();
let is_group = |n: &Node| matches!(n.kind, NodeKind::Group { .. });
for cached in [false, true] {
d.drop_lookup_cache();
if cached {
d.node(layer);
}
let mut find = d.nearest_finder();
assert_eq!(find.nearest(NodeId(501), is_group).map(|n| n.id), Some(NodeId(500)), "cached {cached}");
assert_eq!(find.nearest(NodeId(601), is_group).map(|n| n.id), None, "cached {cached}: id 600 is the path");
assert_eq!(find.nearest(NodeId(999_999), is_group).map(|n| n.id), None, "cached {cached}: not in the tree");
}
}
/// With the cache built, finding the nearest group of every object of a large tree looks no id up
/// and walks the tree no time.
#[test]
fn nearest_finder_reads_one_path_per_object() {
let mut d = Document::new(612.0, 792.0);
let layer = d.layers[0].id;
let mut leaves = vec![];
for g in 0..2_000 {
let kids: Vec<Arc<Node>> = (0..3)
.map(|_| {
let id = d.alloc_id();
leaves.push(id);
Arc::new(Node::path(id, shapes::rectangle(Rect::new(0.0, 0.0, 5.0, 5.0)), Appearance::default_art()))
})
.collect();
let gid = d.alloc_id();
d.insert(Some(layer), g, Node::group(gid, kids)).unwrap();
}
d.drop_lookup_cache();
d.node(layer);
let (lookups, walks) = (path_lookups(), tree_walks());
let mut find = d.nearest_finder();
let found = leaves.iter().filter(|id| find.nearest(**id, |n| matches!(n.kind, NodeKind::Group { .. })).is_some()).count();
assert_eq!(found, leaves.len());
assert_eq!(path_lookups() - lookups, 0, "lookups by id");
assert_eq!(tree_walks() - walks, 0, "walks of the tree");
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.