Skip to main content

decl_lang/qengine/
rounds.rs

1//! Reference-round reuse over the value layer; mirrors qengine/rounds.ts.
2use crate::ast::{walk_expr_tree, walk_type_exprs, Expr};
3use crate::engine::{Edge, Engine, Inst};
4use crate::qengine::graph::{QueryId, QueryPool};
5use crate::qengine::revisions::Revisions;
6use crate::semantics::*;
7use hashbrown::{hash_table::Entry, HashTable};
8use rustc_hash::{FxHashMap, FxHashSet};
9use std::borrow::Cow;
10use std::cell::{Cell, RefCell};
11use std::collections::{HashMap, HashSet};
12use std::rc::Rc;
13
14fn address(inst: &Inst) -> usize {
15    Rc::as_ptr(inst) as usize
16}
17
18type InvertedEdges<'a> = FxHashMap<&'a str, FxHashMap<String, Vec<&'a String>>>;
19
20// Edge maps stay immutable throughout classification. Only canonical target
21// spellings need owned storage; source paths and edge keys already have owners.
22fn invert_edges(all: &HashMap<String, Edge>) -> InvertedEdges<'_> {
23    let mut result = FxHashMap::default();
24    for (key, edge) in all {
25        let mut inv: FxHashMap<String, Vec<&String>> = FxHashMap::default();
26        for (source, (_, refs)) in edge {
27            for target in refs
28                .iter()
29                .map(|p| path_str(p, None))
30                .collect::<FxHashSet<_>>()
31            {
32                inv.entry(target).or_default().push(source);
33            }
34        }
35        for paths in inv.values_mut() {
36            paths.sort();
37        }
38        result.insert(key.as_str(), inv);
39    }
40    result
41}
42
43fn identity(v: &Value) -> Option<(u8, usize)> {
44    match v {
45        Value::Ref(p) => Some((0, Rc::as_ptr(p) as usize)),
46        Value::Arr(a) => Some((1, Rc::as_ptr(a) as usize)),
47        Value::Map(m) => Some((2, Rc::as_ptr(m) as usize)),
48        Value::Rec(r) => Some((3, address(r))),
49        _ => None,
50    }
51}
52
53// Freeze memo values have one fixed variant per source kind. Store their thin
54// owners directly instead of repeating a kind tag and a full Value per entry.
55// This scratch owns copied bodies only; it never changes the source graph.
56/// Whether a value holds only scalars, and arrays and maps of such. A record,
57/// a reference, a callable or anything still lazy makes it, and whatever holds
58/// it, not plain. So does nesting beyond `PLAIN_DEPTH`: a native caller can
59/// build an array that holds itself, and the copy that follows is the path
60/// that remembers what it has visited.
61fn plain(v: &Value) -> bool {
62    const PLAIN_DEPTH: usize = 64;
63    fn within(v: &Value, depth: usize) -> bool {
64        match v {
65            Value::Int(_)
66            | Value::Float(_)
67            | Value::Bool(_)
68            | Value::Str(_)
69            | Value::Null
70            | Value::Absent
71            | Value::Undef
72            | Value::Q(_)
73            | Value::Range(_) => true,
74            Value::Arr(_) | Value::Map(_) if depth == PLAIN_DEPTH => false,
75            Value::Arr(a) => a
76                .try_borrow()
77                .is_ok_and(|b| b.items.iter().all(|item| within(item, depth + 1))),
78            Value::Map(m) => m
79                .try_borrow()
80                .is_ok_and(|b| b.entries.values().all(|value| within(value, depth + 1))),
81            _ => false,
82        }
83    }
84    within(v, 0)
85}
86
87#[derive(Default)]
88struct CopyMemo {
89    records: FxHashMap<usize, Inst>,
90    // the record copies in the order they were made
91    order: Vec<Inst>,
92    arrays: FxHashMap<usize, Rc<RefCell<ArrV>>>,
93    maps: FxHashMap<usize, Rc<RefCell<MapV>>>,
94    refs: FxHashMap<usize, Rc<SegPath>>,
95}
96
97impl CopyMemo {
98    fn get(&self, value: &Value) -> Option<Value> {
99        match value {
100            Value::Rec(record) => self.records.get(&address(record)).cloned().map(Value::Rec),
101            Value::Arr(array) => self
102                .arrays
103                .get(&(Rc::as_ptr(array) as usize))
104                .cloned()
105                .map(Value::Arr),
106            Value::Map(map) => self
107                .maps
108                .get(&(Rc::as_ptr(map) as usize))
109                .cloned()
110                .map(Value::Map),
111            Value::Ref(path) => self
112                .refs
113                .get(&(Rc::as_ptr(path) as usize))
114                .cloned()
115                .map(Value::Ref),
116            _ => None,
117        }
118    }
119}
120
121/// The registered records by canonical spelling, for one invalidation walk:
122/// which records lie under a place. One text and one list of prefix lengths
123/// hold every path, and an order by spelling replaces a table entry per prefix
124/// per record: the records under a place are a run of that order.
125struct RecordPaths {
126    text: String,
127    // where record i's spelling starts in `text`; one more entry ends the last
128    starts: Vec<u32>,
129    // the length of every prefix of every spelling, record by record
130    ends: Vec<u32>,
131    // where record i's prefix lengths start in `ends`; one more entry ends the last
132    firsts: Vec<u32>,
133    // record indices by spelling
134    order: Vec<u32>,
135}
136
137impl RecordPaths {
138    /// `None` when the registry outgrows 32-bit offsets.
139    fn of(registry: &[Inst]) -> Option<Self> {
140        let count = u32::try_from(registry.len()).ok()?;
141        // Sized exactly: this index is live while the walk's other scratch is built.
142        let segments = registry.iter().map(|r| r.borrow().path.len()).sum();
143        let mut paths = Self {
144            text: String::new(),
145            starts: Vec::with_capacity(registry.len() + 1),
146            ends: Vec::with_capacity(segments),
147            firsts: Vec::with_capacity(registry.len() + 1),
148            order: (0..count).collect(),
149        };
150        for r in registry {
151            paths.starts.push(u32::try_from(paths.text.len()).ok()?);
152            paths.firsts.push(u32::try_from(paths.ends.len()).ok()?);
153            path_str_ends_into(&r.borrow().path, &mut paths.text, &mut paths.ends)?;
154        }
155        paths.starts.push(u32::try_from(paths.text.len()).ok()?);
156        paths.firsts.push(u32::try_from(paths.ends.len()).ok()?);
157        paths.text.shrink_to_fit();
158        let mut order = std::mem::take(&mut paths.order);
159        order.sort_unstable_by(|&a, &b| paths.spelling(a as usize).cmp(paths.spelling(b as usize)));
160        paths.order = order;
161        Some(paths)
162    }
163    fn spelling(&self, record: usize) -> &str {
164        &self.text[self.starts[record] as usize..self.starts[record + 1] as usize]
165    }
166    /// Whether no two records share a spelling.
167    fn distinct(&self) -> bool {
168        self.order
169            .windows(2)
170            .all(|pair| self.spelling(pair[0] as usize) != self.spelling(pair[1] as usize))
171    }
172    /// The records at or under a place: those whose spelling starts with the
173    /// place's and has a prefix ending there. Spellings that merely share the
174    /// text (a sibling with a longer name) sit in the same run and are skipped.
175    fn under<'a>(&'a self, place: &'a str) -> impl Iterator<Item = usize> + 'a {
176        let from = self
177            .order
178            .partition_point(|&i| self.spelling(i as usize) < place);
179        let length = u32::try_from(place.len()).ok();
180        self.order[from..]
181            .iter()
182            .map(|&i| i as usize)
183            .take_while(move |&i| self.spelling(i).starts_with(place))
184            .filter(move |&i| {
185                let ends = &self.ends[self.firsts[i] as usize..self.firsts[i + 1] as usize];
186                length.is_some_and(|length| ends.binary_search(&length).is_ok())
187            })
188    }
189}
190
191/// Readers by dependency for one invalidation walk: a chained link per read
192/// edge and one table entry per dependency, instead of a set per dependency.
193/// The table is entered by the hash a key caches for its text and compared by
194/// text: no spelling is hashed while the index is built, and a dependency is
195/// found by its spelling whichever pool interned it.
196struct Readers<'a> {
197    names: Vec<&'a QueryId>,
198    // (the dependency, the head of its chain: a link's index plus one)
199    heads: HashTable<(&'a QueryId, u32)>,
200    // (reader's index in `names`, the dependency's next link plus one; 0 ends)
201    links: Vec<(u32, u32)>,
202}
203
204impl<'a> Readers<'a> {
205    /// `None` when the graph outgrows the links' 32-bit indices.
206    fn with_capacity(readers: usize, edges: usize) -> Option<Self> {
207        (u32::try_from(readers).is_ok() && u32::try_from(edges).is_ok_and(|n| n < u32::MAX)).then(
208            || Self {
209                names: Vec::with_capacity(readers),
210                heads: HashTable::new(),
211                links: Vec::with_capacity(edges),
212            },
213        )
214    }
215    fn reader(&mut self, name: &'a QueryId) -> u32 {
216        self.names.push(name);
217        (self.names.len() - 1) as u32
218    }
219    fn insert(&mut self, dep: &'a QueryId, reader: u32) {
220        let next = self.links.len() as u32 + 1;
221        match self.heads.entry(
222            dep.text_hash(),
223            |(key, _)| *key == dep,
224            |(key, _)| key.text_hash(),
225        ) {
226            Entry::Occupied(mut entry) => {
227                let head = &mut entry.get_mut().1;
228                self.links.push((reader, *head));
229                *head = next;
230            }
231            Entry::Vacant(entry) => {
232                self.links.push((reader, 0));
233                entry.insert((dep, next));
234            }
235        }
236    }
237    fn of<'s>(&'s self, dep: &str) -> impl Iterator<Item = &'a str> + 's {
238        let mut next = self
239            .heads
240            .find(QueryPool::text_hash(dep), |(key, _)| key.as_str() == dep)
241            .map_or(0, |(_, head)| *head);
242        std::iter::from_fn(move || {
243            let (reader, following) = *self.links.get((next as usize).checked_sub(1)?)?;
244            next = following;
245            Some(self.names[reader as usize].as_str())
246        })
247    }
248}
249
250fn identical(a: &Value, b: &Value) -> bool {
251    match (identity(a), identity(b)) {
252        (Some(a), Some(b)) => a == b,
253        (None, None) => value_eq(a, b),
254        _ => false,
255    }
256}
257
258// Compare observed shapes, leaving independently read member values to the graph.
259fn same(a: &Value, b: &Value) -> bool {
260    if identity(a).is_some() && identity(a) == identity(b) {
261        return true;
262    }
263    match (a, b) {
264        (Value::Rec(a), Value::Rec(b)) => {
265            let (a, b) = (a.borrow(), b.borrow());
266            a.type_name == b.type_name
267                && Rc::ptr_eq(&a.rt, &b.rt)
268                && a.path == b.path
269                && a.slots.len() == b.slots.len()
270                && a.slots.iter().zip(&b.slots).all(|((an, av), (bn, bv))| {
271                    an == bn && av.kind == bv.kind && av.hidden == bv.hidden
272                })
273                && a.entry_order == b.entry_order
274                && a.extras.len() == b.extras.len()
275                && a.extras
276                    .iter()
277                    .zip(&b.extras)
278                    .all(|((ak, av), (bk, bv))| ak == bk && same(av, bv))
279        }
280        (Value::Arr(a), Value::Arr(b)) => {
281            let (a, b) = (a.borrow(), b.borrow());
282            a.path == b.path
283                && a.items.len() == b.items.len()
284                && a.items.iter().zip(&b.items).all(|(x, y)| same(x, y))
285        }
286        (Value::Map(a), Value::Map(b)) => {
287            let (a, b) = (a.borrow(), b.borrow());
288            a.path == b.path
289                && a.entries.len() == b.entries.len()
290                && a.entries
291                    .iter()
292                    .zip(b.entries.iter())
293                    .all(|((ak, av), (bk, bv))| ak == bk && same(av, bv))
294        }
295        (Value::Rec(_) | Value::Arr(_) | Value::Map(_), _)
296        | (_, Value::Rec(_) | Value::Arr(_) | Value::Map(_)) => false,
297        (Value::Absent, Value::Absent) => true,
298        _ => value_eq(a, b),
299    }
300}
301
302// A forwarded inverse reference or foreign record view depends on snapshot age,
303// even when its canonical path has not changed. Owned scalar-built records do not.
304fn snapshot_result(
305    v: &Value,
306    eng: &Engine,
307    prefix: &str,
308    seen: &mut FxHashSet<(u8, usize)>,
309) -> bool {
310    let Some(key) = identity(v) else {
311        return false;
312    };
313    if !seen.insert(key) {
314        return false;
315    }
316    match v {
317        Value::Ref(_) => {
318            eng.inverse_refs.borrow().contains_key(&key.1)
319                || eng.snap_refs.borrow().contains_key(&key.1)
320        }
321        Value::Arr(a) => a
322            .borrow()
323            .items
324            .iter()
325            .any(|v| snapshot_result(v, eng, prefix, seen)),
326        Value::Map(m) => m
327            .borrow()
328            .entries
329            .iter()
330            .any(|(_, v)| snapshot_result(v, eng, prefix, seen)),
331        Value::Rec(r) => {
332            if eng.owner_of(r).is_some() {
333                return true;
334            }
335            let r = r.borrow();
336            let path = path_str(&r.path, None);
337            if !(path == prefix
338                || path
339                    .strip_prefix(prefix)
340                    .is_some_and(|tail| tail.starts_with('.') || tail.starts_with('[')))
341            {
342                return true;
343            }
344            r.slots
345                .iter()
346                .any(|(_, s)| snapshot_result(&s.value, eng, prefix, seen))
347                || r.extras
348                    .iter()
349                    .any(|(_, v)| snapshot_result(v, eng, prefix, seen))
350        }
351        _ => false,
352    }
353}
354
355/// Retained round state. Values are memoized by member slots, without a second
356/// database copy; structural and reference reads use the same dependency graph.
357#[derive(Default)]
358pub struct RoundCache {
359    /// Revision verification for retained member slots.
360    pub revisions: Rc<Revisions>,
361    /// Successfully reused round transitions.
362    pub reused_rounds: Cell<usize>,
363    /// Sum of retained record counts across transitions.
364    pub retained_records: Cell<usize>,
365    /// Member computations invalidated across transitions.
366    pub invalidated_slots: Cell<usize>,
367    clean: RefCell<FxHashSet<usize>>,
368    rebased: RefCell<FxHashMap<(u8, usize), (Value, Value)>>,
369    // Every type name a `$referrers` expression of the universe names. A round
370    // reaches a snapshot only through an answer, and an answer names a
371    // registered record of such a type: the snapshot holds those records and
372    // what they contain, and nothing else.
373    types: FxHashSet<String>,
374}
375impl RoundCache {
376    /// The cache of a universe that asks for referrers; `None` when none does.
377    pub(crate) fn of(env: &Rc<Env>) -> Option<Self> {
378        fn visit(env: &Rc<Env>, seen: &mut HashSet<usize>, types: &mut FxHashSet<String>) {
379            if !seen.insert(Rc::as_ptr(env) as usize) {
380                return;
381            }
382            let mut mark = |e: &Rc<Expr>| {
383                if let Expr::Referrers { ty, .. } = &**e {
384                    types.insert(ty.clone());
385                }
386            };
387            for t in env.type_asts.borrow().values() {
388                walk_type_exprs(&t.ast, true, &mut mark);
389            }
390            for f in env.funcs.borrow().values() {
391                walk_expr_tree(&f.body, true, &mut mark);
392                if let Some(t) = &f.ret {
393                    walk_type_exprs(t, true, &mut mark);
394                }
395                for p in &f.params {
396                    if let Some(t) = &p.ty {
397                        walk_type_exprs(t, true, &mut mark);
398                    }
399                }
400            }
401            for c in env.consts.borrow().values() {
402                walk_expr_tree(&c.expr, true, &mut mark);
403                if let Some(t) = &c.ty {
404                    walk_type_exprs(t, true, &mut mark);
405                }
406            }
407            for (_, t, e) in env.outputs.borrow().iter() {
408                walk_type_exprs(t, true, &mut mark);
409                walk_expr_tree(e, true, &mut mark);
410            }
411            for (t, e) in env.inputs.borrow().values() {
412                walk_type_exprs(t, true, &mut mark);
413                if let Some(e) = e {
414                    walk_expr_tree(e, true, &mut mark);
415                }
416            }
417            for im in env.imports.borrow().values() {
418                visit(&im.env, seen, types);
419            }
420            for (env, _) in env.namespaces.borrow().values() {
421                visit(env, seen, types);
422            }
423        }
424        let mut types = FxHashSet::default();
425        visit(env, &mut HashSet::new(), &mut types);
426        (!types.is_empty()).then(|| Self {
427            types,
428            ..Self::default()
429        })
430    }
431
432    pub(crate) fn clean(&self, inst: &Inst) -> bool {
433        self.clean.borrow().contains(&address(inst))
434    }
435    /// Once evaluation has cleared prev, value() bypasses this epoch's memo.
436    /// A later evaluation installs a new RoundCache. Release both old value
437    /// owners and table capacity, retaining the clean and revision state.
438    pub(crate) fn release_rebased(&self) {
439        let rebased = std::mem::take(&mut *self.rebased.borrow_mut());
440        // Cached values can contain native captures whose destructors reenter
441        // evaluation. No memo borrow may survive into their destruction.
442        drop(rebased);
443    }
444    fn rebase_child<'a>(&self, v: &'a Value, eng: &Engine) -> Cow<'a, Value> {
445        match v {
446            Value::Ref(_) | Value::Arr(_) | Value::Map(_) => Cow::Owned(self.value(v, eng)),
447            // These variants pass through value unchanged. Keep the input's
448            // owner until a replacement container actually needs a clone.
449            _ => Cow::Borrowed(v),
450        }
451    }
452    pub(crate) fn value(&self, v: &Value, eng: &Engine) -> Value {
453        if eng.prev.borrow().is_none() {
454            return v.clone();
455        }
456        let Some(key) = identity(v) else {
457            return v.clone();
458        };
459        if key.0 == 3 {
460            return v.clone();
461        }
462        if let Some((_, cached)) = self.rebased.borrow().get(&key) {
463            return cached.clone();
464        }
465        let result = match v {
466            Value::Ref(p)
467                if eng
468                    .round_refs
469                    .borrow()
470                    .contains_key(&(Rc::as_ptr(p) as usize)) =>
471            {
472                let next = Rc::new((**p).clone());
473                if let Some(prev) = eng.prev.borrow().as_ref() {
474                    eng.snap_refs
475                        .borrow_mut()
476                        .insert(Rc::as_ptr(&next) as usize, (next.clone(), prev.clone()));
477                }
478                eng.round_refs
479                    .borrow_mut()
480                    .insert(Rc::as_ptr(&next) as usize, next.clone());
481                eng.inverse_refs
482                    .borrow_mut()
483                    .insert(Rc::as_ptr(&next) as usize, next.clone());
484                Value::Ref(next)
485            }
486            Value::Arr(a) => {
487                let a = a.borrow();
488                let mut replacement: Option<Vec<Value>> = None;
489                for (index, original) in a.items.iter().enumerate() {
490                    let next = self.rebase_child(original, eng);
491                    if replacement.is_none() && !identical(&next, original) {
492                        let mut items = Vec::with_capacity(a.items.len());
493                        items.extend_from_slice(&a.items[..index]);
494                        replacement = Some(items);
495                    }
496                    if let Some(items) = &mut replacement {
497                        items.push(next.into_owned());
498                    }
499                }
500                if let Some(items) = replacement {
501                    #[cfg(feature = "runtime-diagnostics")]
502                    crate::retention_diagnostics::array(
503                        crate::retention_diagnostics::ArraySite::Rebased,
504                        items.len(),
505                        items.capacity(),
506                    );
507                    Value::Arr(Rc::new(RefCell::new(ArrV {
508                        items,
509                        path: a.path.clone(),
510                    })))
511                } else {
512                    v.clone()
513                }
514            }
515            Value::Map(m) => {
516                let m = m.borrow();
517                if m.entries.is_shared() {
518                    let mut replacement: Option<Vec<Value>> = None;
519                    for (index, original) in m.entries.values().enumerate() {
520                        let next = self.rebase_child(original, eng);
521                        if replacement.is_none() && !identical(&next, original) {
522                            let mut values = Vec::with_capacity(m.entries.len());
523                            values.extend(m.entries.values().take(index).cloned());
524                            replacement = Some(values);
525                        }
526                        if let Some(values) = &mut replacement {
527                            values.push(next.into_owned());
528                        }
529                    }
530                    if let Some(values) = replacement {
531                        Value::Map(Rc::new(RefCell::new(MapV {
532                            entries: m.entries.with_values(values),
533                            path: m.path.clone(),
534                        })))
535                    } else {
536                        v.clone()
537                    }
538                } else {
539                    let mut replacement: Option<OrderedMap<Value>> = None;
540                    for (index, (key, original)) in m.entries.iter().enumerate() {
541                        let next = self.rebase_child(original, eng);
542                        if replacement.is_none() && !identical(&next, original) {
543                            let mut entries = OrderedMap::with_capacity_and_hasher(
544                                m.entries.len(),
545                                Default::default(),
546                            );
547                            entries.extend(
548                                m.entries
549                                    .iter()
550                                    .take(index)
551                                    .map(|(k, v)| (k.clone(), v.clone())),
552                            );
553                            replacement = Some(entries);
554                        }
555                        if let Some(entries) = &mut replacement {
556                            entries.insert(key.clone(), next.into_owned());
557                        }
558                    }
559                    if let Some(entries) = replacement {
560                        Value::Map(Rc::new(RefCell::new(MapV {
561                            entries: entries.into(),
562                            path: m.path.clone(),
563                        })))
564                    } else {
565                        v.clone()
566                    }
567                }
568            }
569            _ => v.clone(),
570        };
571        self.rebased
572            .borrow_mut()
573            .insert(key, (v.clone(), result.clone()));
574        result
575    }
576
577    pub(crate) fn advance(
578        &self,
579        eng: &Rc<Engine>,
580        edges: &HashMap<String, Edge>,
581    ) -> Option<Rc<Engine>> {
582        // Declared first so the terminal boundary includes destruction of the
583        // existing registry and invalidation scratch on success or fallback.
584        // The ordinal names the next reused transition, not a unique attempt.
585        #[cfg(feature = "runtime-diagnostics")]
586        let mut advance_diagnostic = crate::evaluation_diagnostics::AdvanceSpan::new(
587            self.reused_rounds.get().saturating_add(1),
588        );
589        let registry = eng.env.registry_snapshot();
590        if eng.env.diag_len() > 0
591            || registry.iter().any(|r| {
592                r.borrow()
593                    .slots
594                    .iter()
595                    .any(|(_, s)| !matches!(s.state, SlotState::Ok | SlotState::Absent))
596            })
597        {
598            return None;
599        }
600        let prior_records: FxHashMap<String, Inst> = eng
601            .prev
602            .borrow()
603            .as_ref()
604            .and_then(|p| p.frozen_registry.borrow().clone())
605            .unwrap_or_default()
606            .iter()
607            .map(|r| (path_str(&r.borrow().path, None), r.clone()))
608            .collect();
609        // Each prefix is a slice of its record's one canonical spelling. Store
610        // segment boundaries while formatting; parsing delimiters afterwards
611        // would be wrong for quoted keys and native bare root names.
612        let registry_paths = RecordPaths::of(&registry)?;
613        if !registry_paths.distinct() {
614            return None;
615        }
616        let snap = eng.snap.borrow();
617        let old_edges = snap
618            .as_ref()
619            .map(|s| invert_edges(&s.edges))
620            .unwrap_or_default();
621        let new_edges = invert_edges(edges);
622        // Classification and invalidation only inspect the dependency graph.
623        // Its key text can serve the temporary reverse index without copies.
624        let reads = eng.reads.borrow();
625        let mut reverse =
626            Readers::with_capacity(reads.len(), reads.values().map(|deps| deps.len()).sum())?;
627        let mut pending: Vec<Cow<'_, str>> = Vec::new();
628        for (reader, deps) in reads.iter() {
629            let index = reverse.reader(reader);
630            for dep in deps.iter() {
631                reverse.insert(dep, index);
632                if let Some(s) = dep.strip_prefix("edge:") {
633                    let mut parts = s.splitn(3, '|');
634                    let key = format!("{}|{}", parts.next()?, parts.next()?);
635                    let target = parts.next()?;
636                    let a = old_edges.get(key.as_str()).and_then(|i| i.get(target));
637                    let b = new_edges.get(key.as_str()).and_then(|i| i.get(target));
638                    if a.map(Vec::as_slice).unwrap_or(&[]) != b.map(Vec::as_slice).unwrap_or(&[]) {
639                        pending.push(Cow::Borrowed(dep.as_str()));
640                    }
641                } else if dep.as_str() == "round:nested" {
642                    pending.push(Cow::Borrowed(dep.as_str()));
643                } else if dep.as_str() == "round:reference" {
644                    let prefix = reader.strip_prefix("root:").unwrap_or(reader.as_str());
645                    let value = eng
646                        .slots_by_key
647                        .borrow()
648                        .get(reader)
649                        .and_then(|(r, n)| r.borrow().slot(n).map(|s| s.value.clone()))
650                        .or_else(|| eng.env.root(prefix));
651                    if reader.starts_with("const:")
652                        || value.as_ref().is_some_and(|v| {
653                            snapshot_result(v, eng, prefix, &mut FxHashSet::default())
654                        })
655                    {
656                        pending.push(Cow::Borrowed(reader.as_str()));
657                    }
658                } else if let Some(key) = dep.strip_prefix("snapshot:") {
659                    let current = eng.query_slot_shared(key);
660                    let equal = current.is_some_and(|(r, n)| {
661                        let r = r.borrow();
662                        let Some(old) = prior_records.get(&path_str(&r.path, None)) else {
663                            return false;
664                        };
665                        let old = old.borrow();
666                        match (old.slot(&n), r.slot(&n)) {
667                            (Some(a), Some(b)) => a.state == b.state && same(&a.value, &b.value),
668                            _ => false,
669                        }
670                    });
671                    if !equal {
672                        pending.push(Cow::Borrowed(dep.as_str()));
673                    }
674                }
675            }
676        }
677        // Classification is complete; these indices must not overlap the
678        // descendant index and the copied frozen value layer below.
679        drop(prior_records);
680        drop(old_edges);
681        drop(new_edges);
682        drop(snap);
683        let forced = pending.iter().map(|key| key.as_ref().to_owned()).collect();
684        let mut invalid = FxHashSet::default();
685        let mut dropped = FxHashSet::default();
686        let mut roots = HashSet::new();
687        let mut dirty = FxHashSet::default();
688        while let Some(key) = pending.pop() {
689            // Duplicate insertions can still grow the set before lookup. Keep
690            // that behavior: its later iteration determines reset/Drop order.
691            if !invalid.insert(key.as_ref().to_owned()) {
692                continue;
693            }
694            if key.starts_with("const:") {
695                return None;
696            }
697            pending.extend(reverse.of(key.as_ref()).map(Cow::Borrowed));
698            let prefix = if let Some(name) = key.strip_prefix("root:") {
699                roots.insert(name.to_string());
700                Some(path_str(&[Seg::Name(name.into())], None))
701            } else {
702                eng.query_slot_shared(&key).map(|(inst, name)| {
703                    let mut current = Some(inst.clone());
704                    while let Some(i) = current {
705                        dirty.insert(address(&i));
706                        current = i.borrow().parent.clone();
707                    }
708                    let member = Seg::Name(name);
709                    path_str_iter(
710                        inst.borrow().path.iter().chain(std::iter::once(&member)),
711                        None,
712                    )
713                })
714            };
715            if let Some(place) = prefix.as_deref() {
716                for inst in registry_paths.under(place).map(|i| &registry[i]) {
717                    if dropped.insert(address(inst)) {
718                        for (n, _) in &inst.borrow().slots {
719                            pending.push(Cow::Owned(Engine::slot_key(inst, n)));
720                        }
721                    }
722                }
723            }
724        }
725        // Keep the registry owner, but release classification scratch before
726        // freezing or replacing any dependencies for the next round.
727        drop(registry_paths);
728        drop(pending);
729        drop(reverse);
730        drop(reads);
731        let mut rebound = false;
732        for (name, _) in eng.env.roots_vec() {
733            rebound |= roots.contains(&name);
734            if rebound && !roots.contains(&name) {
735                return None;
736            }
737        }
738        #[cfg(feature = "runtime-diagnostics")]
739        advance_diagnostic.classified();
740        let snapshot = self.freeze(eng, &registry)?;
741        #[cfg(feature = "runtime-diagnostics")]
742        advance_diagnostic.frozen();
743        self.revisions.begin(eng, &invalid, &forced, &dropped);
744        for inst in &registry {
745            if dropped.contains(&address(inst)) {
746                for (n, _) in &inst.borrow().slots {
747                    let key = Engine::slot_key(inst, n);
748                    eng.remove_query_reads(&key);
749                    eng.remove_query_slot(&key);
750                }
751            }
752        }
753        for key in &invalid {
754            if let Some((inst, name)) = eng.query_slot_shared(key) {
755                let mut i = inst.borrow_mut();
756                let s = i.slot_mut(&name)?;
757                if s.compute.is_some() {
758                    s.state = SlotState::Unforced;
759                    s.value = Value::Undef;
760                    self.invalidated_slots.set(self.invalidated_slots.get() + 1);
761                }
762            }
763            eng.remove_query_reads(key);
764        }
765        eng.env.registry_retain(|r| !dropped.contains(&address(r)));
766        *self.clean.borrow_mut() = registry
767            .iter()
768            .map(address)
769            .filter(|id| !dirty.contains(id) && !dropped.contains(id))
770            .collect();
771        for root in &roots {
772            eng.env.remove_root(root);
773        }
774        *eng.round_roots.borrow_mut() = Some(roots);
775        eng.deferred_slots.borrow_mut().clear();
776        eng.deferred_roots.borrow_mut().clear();
777        eng.phase.set(1);
778        *eng.snap.borrow_mut() = None;
779        *eng.queried.borrow_mut() = eng
780            .reads
781            .borrow()
782            .values()
783            .flat_map(|deps| deps.iter())
784            .filter_map(|dep| {
785                let tail = dep.strip_prefix("edge:")?;
786                let mut parts = tail.splitn(3, '|');
787                Some(format!("{}|{}", parts.next()?, parts.next()?))
788            })
789            .collect();
790        eng.ref_index.borrow_mut().clear();
791        eng.computing_edges.borrow_mut().clear();
792        eng.edge_bases.borrow_mut().clear();
793        for reset in eng.round_resets.borrow().iter() {
794            reset();
795        }
796        self.rebased.borrow_mut().clear();
797        *eng.prev.borrow_mut() = Some(snapshot.clone());
798        for (name, value) in eng.env.roots_vec() {
799            eng.env.set_root(&name, self.value(&value, eng));
800        }
801        self.retained_records
802            .set(self.retained_records.get() + registry.len() - dropped.len());
803        self.reused_rounds.set(self.reused_rounds.get() + 1);
804        #[cfg(feature = "runtime-diagnostics")]
805        advance_diagnostic.accepted();
806        Some(snapshot)
807    }
808
809    /// The round as the next one can reach it. A round obtains a frozen record
810    /// only through a `$referrers` answer, which names a registered record of a
811    /// type some `$referrers` expression names; from there it reads that
812    /// record's values, down into the records it contains, and nothing else:
813    /// no member of a frozen record is evaluated, so no parent link is
814    /// followed, and an ordinary reference resolves in the live round. So
815    /// only those records are copied, without parents, and an answer's path is
816    /// looked up among them instead of walked from frozen roots.
817    fn freeze(&self, eng: &Rc<Engine>, registry: &[Inst]) -> Option<Rc<Engine>> {
818        let tagger = eng.env.tagger.borrow().clone();
819        let frozen = Engine::bare_with_queries(eng.env.clone(), eng.query_pool());
820        *eng.env.tagger.borrow_mut() = tagger;
821        *frozen.programs.borrow_mut() = eng.programs.borrow().clone();
822        *frozen.prev.borrow_mut() = eng.prev.borrow().clone();
823        *frozen.snap_refs.borrow_mut() = eng.snap_refs.borrow().clone();
824        *frozen.inverse_refs.borrow_mut() = eng.inverse_refs.borrow().clone();
825        let mut copies = CopyMemo::default();
826        for r in registry {
827            let named = r
828                .borrow()
829                .type_name
830                .as_ref()
831                .is_some_and(|t| self.types.contains(t));
832            if named {
833                self.copy(&Value::Rec(r.clone()), eng, &frozen, &mut copies)?;
834            }
835        }
836        // The copies in the order they were made: candidates in registry
837        // order, each followed by the records it contains.
838        let registry = copies.order;
839        let mut index = FxHashMap::default();
840        for r in &registry {
841            if index
842                .insert(path_str(&r.borrow().path, None), r.clone())
843                .is_some()
844            {
845                return None;
846            }
847        }
848        *frozen.frozen_roots.borrow_mut() = Some(vec![]);
849        *frozen.frozen_index.borrow_mut() = Some(index);
850        *frozen.frozen_set.borrow_mut() = registry.iter().map(address).collect();
851        // Snapshot navigation uses record slots directly. Only observed reads
852        // need comparison at a later boundary; no full field-key index here.
853        *frozen.frozen_registry.borrow_mut() = Some(registry);
854        Some(frozen)
855    }
856    fn copy(
857        &self,
858        raw: &Value,
859        eng: &Engine,
860        frozen: &Rc<Engine>,
861        copies: &mut CopyMemo,
862    ) -> Option<Value> {
863        let v = self.value(raw, eng);
864        if let Some(c) = copies.get(&v) {
865            return Some(c);
866        }
867        Some(match &v {
868            Value::Rec(inst) => {
869                if eng.owner_of(inst).is_some() {
870                    return Some(v);
871                }
872                let b = inst.borrow();
873                let r = record_instance(RecInst {
874                    type_name: b.type_name.clone(),
875                    rt: b.rt.clone(),
876                    path: b.path.clone(),
877                    ps: RefCell::new(None),
878                    parent: None,
879                    slots: Vec::new(),
880                    entry_order: b.entry_order.clone(),
881                    extras: Vec::new(),
882                    menv: b.menv.clone(),
883                });
884                copies.records.insert(address(inst), r.clone());
885                copies.order.push(r.clone());
886                let mut slots = Vec::with_capacity(b.slots.len());
887                for (name, s) in &b.slots {
888                    if !matches!(s.state, SlotState::Ok | SlotState::Absent) {
889                        return None;
890                    }
891                    slots.push((
892                        name.clone(),
893                        Slot {
894                            kind: s.kind,
895                            hidden: s.hidden,
896                            state: s.state,
897                            value: self.copy(&s.value, eng, frozen, copies)?,
898                            compute: None,
899                        },
900                    ));
901                }
902                let extras: Option<Vec<_>> = b
903                    .extras
904                    .iter()
905                    .map(|(k, v)| Some((k.clone(), self.copy(v, eng, frozen, copies)?)))
906                    .collect();
907                {
908                    let mut r = r.borrow_mut();
909                    r.slots = slots;
910                    r.extras = extras?;
911                }
912                Value::Rec(r)
913            }
914            // Nothing in a plain array or map can change or be re-identified in a
915            // later round, and nothing mutates one once it is built: the snapshot
916            // shares it instead of copying it.
917            Value::Arr(_) | Value::Map(_) if plain(&v) => v.clone(),
918            Value::Arr(a) => {
919                let b = a.borrow();
920                #[cfg(feature = "runtime-diagnostics")]
921                let diagnostic_array = crate::retention_diagnostics::ArrayAttempt::start(
922                    crate::retention_diagnostics::ArraySite::SnapshotCopy,
923                    Some(b.items.len()),
924                );
925                let r = Rc::new(RefCell::new(ArrV {
926                    items: vec![],
927                    path: b.path.clone(),
928                }));
929                copies.arrays.insert(Rc::as_ptr(a) as usize, r.clone());
930                let mut items = Vec::with_capacity(b.items.len());
931                for value in &b.items {
932                    items.push(self.copy(value, eng, frozen, copies)?);
933                }
934                r.borrow_mut().items = items;
935                #[cfg(feature = "runtime-diagnostics")]
936                {
937                    let a = r.borrow();
938                    diagnostic_array.finish(a.items.len(), a.items.capacity());
939                }
940                Value::Arr(r)
941            }
942            Value::Map(m) => {
943                let b = m.borrow();
944                let r = Rc::new(RefCell::new(MapV {
945                    entries: Default::default(),
946                    path: b.path.clone(),
947                }));
948                copies.maps.insert(Rc::as_ptr(m) as usize, r.clone());
949                if b.entries.is_shared() {
950                    let mut values = Vec::with_capacity(b.entries.len());
951                    for value in b.entries.values() {
952                        values.push(self.copy(value, eng, frozen, copies)?);
953                    }
954                    r.borrow_mut().entries = b.entries.with_values(values);
955                } else {
956                    let entries: Option<Vec<_>> = b
957                        .entries
958                        .iter()
959                        .map(|(k, v)| Some((k.clone(), self.copy(v, eng, frozen, copies)?)))
960                        .collect();
961                    r.borrow_mut().entries = entries?.into_iter().collect();
962                }
963                Value::Map(r)
964            }
965            Value::Ref(p)
966                if eng
967                    .round_refs
968                    .borrow()
969                    .contains_key(&(Rc::as_ptr(p) as usize)) =>
970            {
971                // A frozen answer has its own identity: live cache rebasing must
972                // never move it to the next round's owner.
973                let path = Rc::new(p.as_ref().clone());
974                if let Some((_, owner)) = eng.snap_refs.borrow().get(&(Rc::as_ptr(p) as usize)) {
975                    frozen
976                        .snap_refs
977                        .borrow_mut()
978                        .insert(Rc::as_ptr(&path) as usize, (path.clone(), owner.clone()));
979                }
980                frozen
981                    .inverse_refs
982                    .borrow_mut()
983                    .insert(Rc::as_ptr(&path) as usize, path.clone());
984                copies.refs.insert(Rc::as_ptr(p) as usize, path.clone());
985                Value::Ref(path)
986            }
987            Value::Ref(_)
988            | Value::JObj(_)
989            | Value::Int(_)
990            | Value::Float(_)
991            | Value::Bool(_)
992            | Value::Str(_)
993            | Value::Null
994            | Value::Absent
995            | Value::Undef
996            | Value::Q(_)
997            | Value::Range(_) => v.clone(),
998            _ => return None,
999        })
1000    }
1001}
1002
1003// Rust-native snapshot, callback and lifetime boundaries. Language behavior
1004// remains covered by the shared reference-round corpus.
1005#[cfg(test)]
1006#[path = "../../tests/private/round_advance_test.rs"]
1007mod tests;