use std::sync::Arc;
use rayon::prelude::*;
use rustc_hash::FxHashMap;
use crate::bbox::Aabb;
use crate::expr::{MASK, NODE, NO_BOX};
use crate::grid::Octree;
use crate::model::{Model, NodeBox, Options};
type Digest = [u8; 16];
fn digest(bytes: &[u8]) -> Digest {
blake3::hash(bytes).as_bytes()[..16].try_into().unwrap()
}
fn shape_digests(m: &Model) -> Vec<Digest> {
m.shapes
.par_iter()
.map(|s| digest(&bitcode::serialize(s).expect("shapes serialize")))
.collect()
}
#[derive(Clone, Debug, Default)]
#[non_exhaustive]
pub struct Changed {
pub universes_rebuilt: Vec<i64>,
pub cells_changed: Vec<i64>,
pub cells_removed: Vec<i64>,
}
impl Changed {
pub fn between(old: &Model, new: &Model) -> Changed {
let (old_shapes, new_shapes) = rayon::join(|| shape_digests(old), || shape_digests(new));
let base = Base {
old,
old_shapes,
new_shapes,
unit_of: FxHashMap::default(),
};
let mut c = base.changes(new, &vec![true; new.units.len()]);
c.universes_rebuilt.clear();
c
}
pub(crate) fn everything(new: &Model, old: &Model) -> Changed {
let mut cells_changed: Vec<i64> = new.cells.iter().map(|c| c.id).collect();
let mut cells_removed: Vec<i64> = old
.cells
.iter()
.filter(|c| new.cell_index(c.id).is_none())
.map(|c| c.id)
.collect();
cells_changed.sort_unstable();
cells_removed.sort_unstable();
Changed {
universes_rebuilt: new.units.iter().map(|u| u.universe).collect(),
cells_changed,
cells_removed,
}
}
}
pub(crate) struct Base<'a> {
old: &'a Model,
old_shapes: Vec<Digest>,
new_shapes: Vec<Digest>,
unit_of: FxHashMap<i64, u32>,
}
impl<'a> Base<'a> {
pub(crate) fn new(old: &'a Model, new: &Model, opts: &Options) -> Option<Base<'a>> {
let half = opts.world_half_size;
let world = Aabb {
lo: [-half; 3],
hi: [half; 3],
};
let same = old.cut.is_none()
&& old.tolerance.to_bits() == opts.tolerance.to_bits()
&& same_box(&old.world, &world)
&& old.grid_options == (opts.grid, opts.residuals);
if !same {
return None;
}
let (old_shapes, new_shapes) = rayon::join(|| shape_digests(old), || shape_digests(new));
let unit_of = old
.units
.iter()
.enumerate()
.map(|(i, u)| (u.universe, i as u32))
.collect();
Some(Base {
old,
old_shapes,
new_shapes,
unit_of,
})
}
pub(crate) fn old_unit(&self, new: &Model, u: u32, roi: &Aabb) -> Option<u32> {
let unit = &new.units[u as usize];
let ou = *self.unit_of.get(&unit.universe)?;
let old_unit = &self.old.units[ou as usize];
if !same_box(&old_unit.roi, roi) {
return None;
}
self.remap(new, ou, u).map(|_| ou)
}
fn remap(&self, new: &Model, ou: u32, u: u32) -> Option<Remap> {
let a = &self.old.units[ou as usize].cells;
let b = &new.units[u as usize].cells;
if a.len() != b.len() || !a.is_sorted_by(|x, y| x < y) || !b.is_sorted_by(|x, y| x < y) {
return None;
}
let pairs: Vec<Vec<(u32, u32)>> = a
.par_iter()
.zip(b)
.map(|(&x, &y)| self.same_cell(new, x, y))
.collect::<Option<_>>()?;
let mut shapes: FxHashMap<u32, u32> = FxHashMap::default();
let mut back: FxHashMap<u32, u32> = FxHashMap::default();
for (s, t) in pairs.into_iter().flatten() {
if *shapes.entry(s).or_insert(t) != t || *back.entry(t).or_insert(s) != s {
return None;
}
}
Some(Remap {
cells: a.iter().copied().zip(b.iter().copied()).collect(),
shapes,
})
}
fn same_cell(&self, new: &Model, oc: u32, nc: u32) -> Option<Vec<(u32, u32)>> {
let (a, b) = (&self.old.cells[oc as usize], &new.cells[nc as usize]);
if a.id != b.id
|| a.code_len != b.code_len
|| a.unsupported.is_some() != b.unsupported.is_some()
|| self.old.is_lattice(oc) != new.is_lattice(nc)
{
return None;
}
let (x, y) = (self.old.code(oc), new.code(nc));
if b.unsupported.is_some() {
return (x == y).then(Vec::new);
}
let mut pairs = Vec::new();
let mut pos = 0;
while pos < x.len() {
let (v, w) = (x[pos], y[pos]);
if w & NODE != 0 {
if v != w {
return None;
}
pos += 2;
} else {
let (s, t) = (v & MASK, w & MASK);
if v & !MASK != w & !MASK
|| self.old_shapes[s as usize] != self.new_shapes[t as usize]
{
return None;
}
pairs.push((s, t));
pos += 1;
}
}
Some(pairs)
}
pub(crate) fn boxes(&self, ou: u32) -> Vec<(Aabb, Vec<NodeBox>)> {
let old = self.old;
old.units[ou as usize]
.cells
.par_iter()
.map(|&c| {
let cell = &old.cells[c as usize];
if cell.unsupported.is_some() {
return (cell.bbox, Vec::new());
}
let code = old.code(c);
let boxes = old.node_boxes_of(c);
let mut nodes: Vec<(u32, NodeBox)> = Vec::new();
let mut pos = 0;
while pos < code.len() {
if code[pos] & NODE != 0 {
let bw = code[pos + 1];
if bw != NO_BOX {
let k = bw & !NODE;
let [t, f] = boxes[k as usize];
nodes.push((k, (pos, t, f)));
}
pos += 2;
} else {
pos += 1;
}
}
nodes.sort_by_key(|n| n.0);
(
old.cells[c as usize].bbox,
nodes.into_iter().map(|n| n.1).collect(),
)
})
.collect()
}
pub(crate) fn take_grid(&self, new: &mut Model, u: u32, ou: u32) {
let old = &self.old.units[ou as usize];
let grid = match &old.grid {
Some(g) if !old.pending => {
let r = self.remap(new, ou, u).expect("a reused unit");
if r.is_identity() {
Some(g.clone())
} else {
Some(Arc::new(r.octree(g)))
}
}
_ => None,
};
let unit = &mut new.units[u as usize];
unit.grid = grid;
unit.pending = old.pending;
}
pub(crate) fn changes(&self, new: &Model, reused: &[bool]) -> Changed {
let universes_rebuilt = new
.units
.iter()
.zip(reused)
.filter(|(_, r)| !**r)
.map(|(u, _)| u.universe)
.collect();
let (old_cells, new_cells) = rayon::join(
|| cell_digests(self.old, &self.old_shapes),
|| cell_digests(new, &self.new_shapes),
);
let mut cells_changed: Vec<i64> = new
.cells
.par_iter()
.zip(&new_cells)
.filter(|(c, d)| {
self.old
.cell_index(c.id)
.is_none_or(|i| old_cells[i as usize] != **d)
})
.map(|(c, _)| c.id)
.collect();
let mut cells_removed: Vec<i64> = self
.old
.cells
.iter()
.filter(|c| new.cell_index(c.id).is_none())
.map(|c| c.id)
.collect();
cells_changed.sort_unstable();
cells_removed.sort_unstable();
Changed {
universes_rebuilt,
cells_changed,
cells_removed,
}
}
}
struct Remap {
cells: FxHashMap<u32, u32>,
shapes: FxHashMap<u32, u32>,
}
impl Remap {
fn is_identity(&self) -> bool {
self.cells.iter().all(|(a, b)| a == b) && self.shapes.iter().all(|(a, b)| a == b)
}
fn octree(&self, g: &Octree) -> Octree {
let items = g.items.par_iter().map(|c| self.cells[c]).collect();
let mut arena = g.arena.clone();
let mut pos = 0;
while pos < arena.len() {
let w = arena[pos];
if w & NODE != 0 {
pos += 2;
} else {
arena[pos] = (w & !MASK) | self.shapes[&(w & MASK)];
pos += 1;
}
}
Octree {
root: g.root,
nodes: g.nodes.clone(),
items,
progs: g.progs.clone(),
arena,
}
}
}
fn cell_digests(m: &Model, shapes: &[Digest]) -> Vec<Digest> {
(0..m.cells.len() as u32)
.into_par_iter()
.map(|c| {
let mut h = blake3::Hasher::new();
let cell = &m.cells[c as usize];
h.update(&[cell.unsupported.is_some() as u8, m.is_lattice(c) as u8]);
for v in cell.bbox.lo.iter().chain(&cell.bbox.hi) {
h.update(&v.to_bits().to_le_bytes());
}
let code = m.code(c);
if cell.unsupported.is_some() {
for w in code {
h.update(&w.to_le_bytes());
}
return h.finalize().as_bytes()[..16].try_into().unwrap();
}
let mut pos = 0;
while pos < code.len() {
let w = code[pos];
if w & NODE != 0 {
h.update(&w.to_le_bytes());
pos += 2;
} else {
h.update(&(w & !MASK).to_le_bytes());
h.update(&shapes[(w & MASK) as usize]);
pos += 1;
}
}
h.finalize().as_bytes()[..16].try_into().unwrap()
})
.collect()
}
fn same_box(a: &Aabb, b: &Aabb) -> bool {
(0..3).all(|i| a.lo[i].to_bits() == b.lo[i].to_bits() && a.hi[i].to_bits() == b.hi[i].to_bits())
}