SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.
use solidcore_record::Vec3;
use super::OccurrenceTree;
use crate::*;
/// `placements` as it walked before the tree: a scan of every occurrence for each component
/// visited. The tree must give exactly this, in this order, for every document.
fn scanning_placements(doc: &Document) -> Vec<(u64, Vec<u64>, Mat)> {
let mut out = vec![(0, Vec::new(), IDENTITY)];
let mut stack: Vec<(u64, Vec<u64>, Mat)> = vec![(0, Vec::new(), IDENTITY)];
while let Some((comp, path, m)) = stack.pop() {
if out.len() > MAX_PLACEMENTS {
break;
}
if path.len() > MAX_PLACEMENT_DEPTH {
continue;
}
for o in doc.occurrences.iter().filter(|o| o.parent == comp) {
let mut p = path.clone();
p.push(o.id);
let w = mat_mul(&m, &o.transform);
out.push((o.component, p.clone(), w));
stack.push((o.component, p, w));
}
}
out
}
/// `inside_component`'s walk as it was before the tree: is `parent` placed anywhere below `component`?
fn scanning_inside(doc: &Document, parent: u64, component: u64) -> bool {
if doc.component_within(parent, component) {
return true;
}
let mut stack = vec![component];
let mut seen = std::collections::BTreeSet::new();
while let Some(c) = stack.pop() {
if !seen.insert(c) || seen.len() > MAX_PLACEMENTS {
continue;
}
for o in doc.occurrences.iter().filter(|o| o.parent == c) {
if o.component == parent {
return true;
}
stack.push(o.component);
}
}
false
}
/// Every (parent, component) pair over the ids a document names, and one id it doesn't.
fn same_inside(doc: &Document) -> std::result::Result<(), String> {
let mut ids: Vec<u64> = doc.occurrences.iter().flat_map(|o| [o.parent, o.component]).chain([0, 999]).collect();
ids.sort_unstable();
ids.dedup();
for &parent in &ids {
for &component in &ids {
if doc.inside_component(parent, component) != scanning_inside(doc, parent, component) {
return Err(format!("inside_component({parent}, {component})"));
}
}
}
Ok(())
}
/// An occurrence of `component` in `parent`, moved by its id so every path's transform differs.
fn occurrence(id: u64, component: u64, parent: u64) -> Occurrence {
let t = Vec3::new(id as f64, (id % 7) as f64, 0.5 * (id % 3) as f64);
Occurrence {
id,
component,
parent,
name: format!("C{component}:{id}"),
transform: rigid(t, Vec3::ZERO, Vec3::Z, 0.01 * id as f64),
grounded: false,
}
}
fn with(occurrences: Vec<Occurrence>) -> Document {
let mut doc = Document::new("tree");
doc.occurrences = occurrences;
doc
}
/// Component `k` placed once in component `k - 1`, `depth` levels below the root.
fn chain(depth: u64) -> Document {
with((1..=depth).map(|k| occurrence(k, k, k - 1)).collect())
}
/// The documents whose walks must not move: the walk's boundaries and the hostile shapes a file
/// can hold.
fn shapes() -> Vec<(&'static str, Document)> {
// 2 under the root, each holding 400 of component 3, each holding 150 of component 4: past
// MAX_PLACEMENTS, so the walk stops part way.
let mut wide = vec![occurrence(1, 1, 0), occurrence(2, 1, 0)];
wide.extend((0..400).map(|i| occurrence(10 + i, 3, 1)));
wide.extend((0..150).map(|i| occurrence(1000 + i, 4, 3)));
vec![
("empty", with(Vec::new())),
("one level", with(vec![occurrence(1, 1, 0), occurrence(2, 2, 0), occurrence(3, 1, 0)])),
("depth 63", chain(63)),
("depth 64", chain(64)),
("depth 65", chain(65)),
("depth 66", chain(66)),
("a component twice under one parent", with(vec![occurrence(1, 1, 0), occurrence(2, 2, 1), occurrence(3, 2, 1), occurrence(4, 3, 2)])),
("an occurrence whose parent is missing", with(vec![occurrence(1, 1, 0), occurrence(2, 2, 99), occurrence(3, 3, 2)])),
("a cycle", with(vec![occurrence(1, 1, 0), occurrence(2, 2, 1), occurrence(3, 1, 2)])),
("a component inside itself", with(vec![occurrence(1, 1, 0), occurrence(2, 1, 1)])),
("duplicated occurrence ids", with(vec![occurrence(1, 1, 0), occurrence(1, 2, 0), occurrence(2, 3, 1), occurrence(2, 3, 2)])),
("children listed out of order", with(vec![occurrence(5, 2, 1), occurrence(1, 1, 0), occurrence(4, 3, 2), occurrence(2, 2, 1)])),
("past MAX_PLACEMENTS", with(wide)),
]
}
#[test]
fn the_walk_is_the_scanning_walk_for_every_shape() {
for (name, doc) in shapes() {
let walked = doc.placements();
assert_eq!(walked, scanning_placements(&doc), "{name}");
assert_eq!(OccurrenceTree::new(&doc).placements_with(|o| o.transform), walked, "{name}");
if doc.occurrences.len() < 100 {
assert_eq!(same_inside(&doc), Ok(()), "{name}");
}
}
}
#[test]
fn the_walk_stops_at_its_caps_as_before() {
let deepest = |doc: &Document| doc.placements().iter().map(|(_, path, _)| path.len()).max();
// A branch is walked to MAX_PLACEMENT_DEPTH levels and one past it (today's 65-id path), no further.
assert_eq!(deepest(&chain(64)), Some(64));
assert_eq!(deepest(&chain(66)), Some(MAX_PLACEMENT_DEPTH + 1));
let (_, wide) = shapes().pop().unwrap();
let n = wide.placements().len();
assert!(n > MAX_PLACEMENTS && n <= MAX_PLACEMENTS + 400, "stops once past the cap: {n}");
// A cycle ends at the depth cap, not in a loop.
let (_, cycle) = shapes().into_iter().find(|(name, _)| *name == "a cycle").unwrap();
assert_eq!(deepest(&cycle), Some(MAX_PLACEMENT_DEPTH + 1));
}
#[test]
fn children_are_listed_in_document_order() {
let doc = with(vec![occurrence(5, 2, 1), occurrence(1, 1, 0), occurrence(4, 3, 1), occurrence(2, 2, 1), occurrence(3, 9, 7)]);
let tree = OccurrenceTree::new(&doc);
let ids = |c: u64| tree.children(c).iter().map(|o| o.id).collect::<Vec<_>>();
assert_eq!(ids(1), [5, 4, 2]);
assert_eq!(ids(0), [1]);
assert_eq!(ids(7), [3], "an occurrence under a missing parent is still its child");
assert!(ids(2).is_empty());
}
#[test]
fn a_walk_uses_the_transform_it_is_given() {
let doc = with(vec![occurrence(1, 1, 0), occurrence(2, 2, 1)]);
let moved = rigid(Vec3::new(0.0, 0.0, 9.0), Vec3::ZERO, Vec3::Z, 0.0);
let walked = OccurrenceTree::new(&doc).placements_with(|o| if o.id == 1 { moved } else { o.transform });
let child = &doc.occurrences[1].transform;
assert_eq!(walked[1], (1, vec![1], moved));
assert_eq!(walked[2], (2, vec![1, 2], mat_mul(&moved, child)));
}
/// splitmix64, so each run makes the same documents.
fn next(state: &mut u64) -> u64 {
*state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = *state;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
#[test]
fn hostile_documents_walk_as_before() {
// Few component ids and parents drawn from them, so repeats, missing parents, cycles and
// duplicated ids all come up.
let mut state = 4032;
for round in 0..300 {
let n = next(&mut state) % 40;
let components = 1 + next(&mut state) % 12;
let occurrences = (0..n)
.map(|i| {
let id = if next(&mut state).is_multiple_of(9) { i / 2 } else { i + 1 };
let component = 1 + next(&mut state) % components;
let parent = next(&mut state) % (components + 2);
occurrence(id, component, parent)
})
.collect();
let doc = with(occurrences);
assert_eq!(doc.placements(), scanning_placements(&doc), "round {round}");
assert_eq!(same_inside(&doc), Ok(()), "round {round}");
}
}
/// A generated assembly of `top` modules, each holding `parts` parts, each part holding `pins`
/// pins: the shape of a large imported board.
fn assembly(top: u64, parts: u64, pins: u64) -> Document {
let mut occurrences = Vec::new();
let mut id = 0;
let mut add = |component: u64, parent: u64, n: u64| {
for _ in 0..n {
id += 1;
occurrences.push(occurrence(id, component, parent));
}
};
add(1, 0, top);
for part in 0..parts {
add(10 + part, 1, 1);
add(5, 10 + part, pins);
}
with(occurrences)
}
#[test]
#[ignore = "manual optimized walk microbenchmark; no timing assertion"]
fn benchmark_placements_walk() {
// About 10,000 and 97,500 placements, under MAX_PLACEMENTS.
for (top, parts, pins) in [(10, 100, 9), (39, 250, 9)] {
let doc = assembly(top, parts, pins);
let time = |walk: &dyn Fn() -> Vec<(u64, Vec<u64>, Mat)>| {
let start = std::time::Instant::now();
let walked = walk();
let elapsed = start.elapsed().as_secs_f64() * 1000.;
std::hint::black_box(walked);
elapsed
};
let median = |mut ms: Vec<f64>| {
ms.sort_by(f64::total_cmp);
ms[ms.len() / 2]
};
let walked = doc.placements();
assert_eq!(walked, scanning_placements(&doc));
let (scan, tree) = (|| scanning_placements(&doc), || doc.placements());
// Each order in turn, so neither walk always runs on a cache the other warmed.
for scanning_first in [true, false] {
let (mut old, mut new) = (Vec::new(), Vec::new());
for _ in 0..9 {
if scanning_first {
old.push(time(&scan));
new.push(time(&tree));
} else {
new.push(time(&tree));
old.push(time(&scan));
}
}
eprintln!(
"{} occurrences, {} placements, {} first: scanning={:.3}ms tree={:.3}ms (median of 9, tree includes building it)",
doc.occurrences.len(),
walked.len(),
if scanning_first { "scanning" } else { "tree" },
median(old),
median(new)
);
}
}
}