Skip to main content

dive_core/
candidate_codec.rs

1//! Owned, bounded candidate DAG records tied to one live Store.
2//!
3//! Transient payloads are copied before Arena rollback without interning them.
4//! Only ordered consumption imports nodes into the
5//! Store. This is transient working storage, not a checkpoint or trace proof.
6
7use crate::handle::Tag;
8use crate::node::{Kind, flags};
9use crate::{Error, Handle, Heap, Store};
10use std::collections::HashMap;
11use std::sync::Arc;
12use std::sync::atomic::{AtomicU64, Ordering};
13
14const MAGIC: &[u8; 8] = b"DIVECD01";
15const HEADER: usize = 32;
16const NODE_HEADER: usize = 42;
17const REFERENCE: usize = 9;
18const MAX_DEPTH: usize = 128;
19/// Legacy report limit retained for schema stability; canonical records use zero.
20pub const MAX_ORIGIN_INDEX_BYTES: usize = 1024 * 1024;
21static NEXT: AtomicU64 = AtomicU64::new(1);
22
23fn invalid(message: impl std::fmt::Display) -> Error {
24    Error::internal(format!("native candidate payload: {message}"))
25}
26
27/// A private lifetime-bound transport for one source's ordered candidate rows.
28#[derive(Debug)]
29pub struct CandidateCodec {
30    store: Arc<Store>,
31    token: u64,
32    source_arena: Arc<()>,
33}
34
35impl CandidateCodec {
36    /// Retains the source's live Store and issues a nonreused lifetime token.
37    ///
38    /// # Errors
39    /// The process lifetime token space is exhausted.
40    pub fn new(heap: &Heap) -> Result<Self, Error> {
41        let token = NEXT
42            .try_update(Ordering::Relaxed, Ordering::Relaxed, |n| n.checked_add(1))
43            .map_err(|_| invalid("lifetime tokens exhausted"))?;
44        Ok(Self {
45            store: Arc::clone(heap.store()),
46            token,
47            source_arena: Arc::clone(&heap.arena.cache_owner),
48        })
49    }
50
51    /// Copies closed local roots into an owned child-first DAG without promotion.
52    ///
53    /// Existing persistent subtrees remain checked references to this live Store.
54    /// Byte limits bound traversal/deduplication scratch. No new evaluation,
55    /// normalization demand or persistent origin allocation is performed.
56    ///
57    /// # Errors
58    /// A foreign/stale/lazy value, legacy history, nesting/byte limit or allocation.
59    pub fn encode(
60        &self,
61        heap: &mut Heap,
62        roots: &[Handle],
63        limit: usize,
64    ) -> Result<Vec<u8>, Error> {
65        self.owner(heap)?;
66        if !Arc::ptr_eq(&self.source_arena, &heap.arena.cache_owner) {
67            return Err(invalid("foreign encoding Arena"));
68        }
69        if roots
70            .len()
71            .checked_mul(REFERENCE)
72            .and_then(|n| n.checked_add(HEADER))
73            .is_none_or(|n| n > limit)
74        {
75            return Err(Error::unsupported(
76                "candidate root row exceeds its record bound",
77            ));
78        }
79        let mut out = Write {
80            bytes: Vec::new(),
81            limit,
82            nodes: HashMap::new(),
83            scratch: 0,
84        };
85        out.put(MAGIC)?;
86        out.word(self.token)?;
87        out.word(0)?;
88        out.word(roots.len() as u64)?;
89        let mut refs = Vec::new();
90        refs.try_reserve_exact(roots.len()).map_err(invalid)?;
91        for &root in roots {
92            refs.push(out.visit(heap, root, 0)?);
93        }
94        out.bytes[16..24].copy_from_slice(&(out.nodes.len() as u64).to_le_bytes());
95        for reference in refs {
96            out.reference(reference)?;
97        }
98        self.owner(heap)?;
99        Ok(out.bytes)
100    }
101
102    /// Imports one unchanged record only when ordered commit consumes it.
103    ///
104    /// Shared children retain their aliases. Legacy constructor origins are refused.
105    ///
106    /// # Errors
107    /// Invalid format, owner, shape, reference, allocation or construction origin.
108    pub fn decode(
109        &mut self,
110        heap: &mut Heap,
111        bytes: &[u8],
112        limit: usize,
113    ) -> Result<Vec<Handle>, Error> {
114        self.owner(heap)?;
115        if bytes.len() > limit {
116            return Err(invalid("record exceeds byte bound"));
117        }
118        let mut input = Read { bytes, at: 0 };
119        if input.take(8)? != MAGIC || input.word()? != self.token {
120            return Err(invalid("version or lifetime owner mismatch"));
121        }
122        let count = input.count(NODE_HEADER)?;
123        let roots = input.count(REFERENCE)?;
124        // Reject obsolete metadata across the whole record before any valid
125        // prefix can promote nodes. The normal pass retains shape/reference checks.
126        let mut metadata = Read {
127            bytes,
128            at: input.at,
129        };
130        for _ in 0..count {
131            heap.work_poll()?;
132            metadata.take(1)?; // kind
133            let fl = metadata.take(1)?[0];
134            metadata.take(3 * 8)?; // lo, hash, sum
135            let origin = metadata.word()?;
136            if fl & flags::HISTORY != 0 || origin != 0 {
137                return Err(invalid("legacy construction history"));
138            }
139            let len = metadata.count(REFERENCE)?;
140            metadata.take(len * REFERENCE)?;
141        }
142        metadata.take(roots * REFERENCE)?;
143        if metadata.at != bytes.len() {
144            return Err(invalid("trailing bytes"));
145        }
146        let mut nodes = Vec::new();
147        nodes.try_reserve_exact(count).map_err(invalid)?;
148        for _ in 0..count {
149            heap.work_poll()?;
150            let kind = kind(input.take(1)?[0])?;
151            let fl = input.take(1)?[0];
152            let lo = input.word()?.cast_signed();
153            let hash = input.word()?;
154            let sum = input.word()?;
155            let origin = input.word()?;
156            let len = input.count(REFERENCE)?;
157            let mut children = Vec::new();
158            children.try_reserve_exact(len).map_err(invalid)?;
159            for _ in 0..len {
160                heap.work_poll()?;
161                children.push(input.reference(&self.store, &nodes)?);
162            }
163            shape(kind, fl, lo, origin, &children)?;
164            let handle = self
165                .store
166                .intern(&mut heap.cache, kind, fl, lo, hash, sum, &children);
167            nodes.push(handle);
168        }
169        let mut values = Vec::new();
170        values.try_reserve_exact(roots).map_err(invalid)?;
171        for _ in 0..roots {
172            heap.work_poll()?;
173            values.push(input.reference(&self.store, &nodes)?);
174        }
175        if input.at != bytes.len() {
176            return Err(invalid("trailing bytes"));
177        }
178        self.owner(heap)?;
179        Ok(values)
180    }
181
182    /// Retained legacy report metric. Canonical candidates allocate no origins.
183    #[must_use]
184    pub const fn origin_index_bytes(&self) -> usize {
185        0
186    }
187
188    fn owner(&self, heap: &Heap) -> Result<(), Error> {
189        if !Arc::ptr_eq(&self.store, heap.store()) || heap.poisoned() || self.store.poisoned() {
190            Err(invalid("foreign or poisoned owner"))
191        } else {
192            Ok(())
193        }
194    }
195}
196
197#[derive(Clone, Copy)]
198struct Reference {
199    local: bool,
200    value: u64,
201}
202
203struct Write {
204    bytes: Vec<u8>,
205    limit: usize,
206    nodes: HashMap<Handle, u64>,
207    scratch: usize,
208}
209
210impl Write {
211    fn put(&mut self, bytes: &[u8]) -> Result<(), Error> {
212        let end = self
213            .bytes
214            .len()
215            .checked_add(bytes.len())
216            .filter(|&n| n <= self.limit)
217            .ok_or_else(|| Error::unsupported("candidate payload exceeds its record bound"))?;
218        if self.bytes.capacity() < end {
219            let capacity = end
220                .max(self.bytes.capacity().saturating_mul(2))
221                .min(self.limit);
222            self.bytes
223                .try_reserve_exact(capacity - self.bytes.len())
224                .map_err(invalid)?;
225        }
226        self.bytes.extend_from_slice(bytes);
227        Ok(())
228    }
229    fn word(&mut self, value: u64) -> Result<(), Error> {
230        self.put(&value.to_le_bytes())
231    }
232    fn reference(&mut self, reference: Reference) -> Result<(), Error> {
233        self.put(&[u8::from(reference.local)])?;
234        self.word(reference.value)
235    }
236    fn visit(&mut self, heap: &mut Heap, value: Handle, depth: usize) -> Result<Reference, Error> {
237        heap.work_poll()?;
238        if !value.is_transient() {
239            checked(&heap.store, value.bits())?;
240            return Ok(Reference {
241                local: false,
242                value: value.bits(),
243            });
244        }
245        if depth >= MAX_DEPTH {
246            return Err(Error::unsupported("candidate payload nesting exceeds 128"));
247        }
248        let origin = 0;
249        if let Some(&value) = self.nodes.get(&value) {
250            return Ok(Reference { local: true, value });
251        }
252        let view = heap
253            .arena
254            .lookup(value)
255            .ok_or_else(|| invalid("stale Arena value"))?;
256        if view.is_lazy() || view.kind.is_lazy() {
257            return Err(invalid("unclosed lazy value"));
258        }
259        if view.flags & flags::HISTORY != 0 {
260            return Err(invalid("unowned construction history"));
261        }
262        let scratch = view
263            .data
264            .len()
265            .checked_mul(size_of::<Handle>() + size_of::<Reference>())
266            .ok_or_else(|| invalid("traversal size overflow"))?;
267        if view
268            .data
269            .len()
270            .checked_mul(REFERENCE)
271            .and_then(|n| n.checked_add(NODE_HEADER))
272            .is_none_or(|n| n > self.limit.saturating_sub(self.bytes.len()))
273            || self.nodes.len() >= self.limit / NODE_HEADER
274            || scratch > self.limit.saturating_sub(self.scratch)
275        {
276            return Err(Error::unsupported("candidate DAG exceeds its record bound"));
277        }
278        self.scratch += scratch;
279        let (kind, fl, lo, hash, sum) = (
280            view.kind,
281            view.flags & !flags::CONCRETE,
282            view.lo,
283            view.hash,
284            view.sum,
285        );
286        let mut children = Vec::new();
287        children
288            .try_reserve_exact(view.data.len())
289            .map_err(invalid)?;
290        children.extend_from_slice(view.data);
291        let mut refs = Vec::new();
292        refs.try_reserve_exact(children.len()).map_err(invalid)?;
293        for child in children {
294            refs.push(self.visit(heap, child, depth + 1)?);
295        }
296        self.put(&[kind as u8, fl])?;
297        self.word(lo.cast_unsigned())?;
298        self.word(hash)?;
299        self.word(sum)?;
300        self.word(origin)?;
301        self.word(refs.len() as u64)?;
302        for reference in refs {
303            self.reference(reference)?;
304        }
305        self.scratch -= scratch;
306        let index = self.nodes.len() as u64;
307        self.nodes.try_reserve(1).map_err(invalid)?;
308        self.nodes.insert(value, index);
309        Ok(Reference {
310            local: true,
311            value: index,
312        })
313    }
314}
315
316struct Read<'a> {
317    bytes: &'a [u8],
318    at: usize,
319}
320impl<'a> Read<'a> {
321    fn take(&mut self, len: usize) -> Result<&'a [u8], Error> {
322        let end = self
323            .at
324            .checked_add(len)
325            .filter(|&n| n <= self.bytes.len())
326            .ok_or_else(|| invalid("truncated record"))?;
327        let bytes = &self.bytes[self.at..end];
328        self.at = end;
329        Ok(bytes)
330    }
331    fn word(&mut self) -> Result<u64, Error> {
332        let mut bytes = [0; 8];
333        bytes.copy_from_slice(self.take(8)?);
334        Ok(u64::from_le_bytes(bytes))
335    }
336    fn count(&mut self, unit: usize) -> Result<usize, Error> {
337        let count = usize::try_from(self.word()?).map_err(invalid)?;
338        if count
339            .checked_mul(unit)
340            .is_none_or(|n| n > self.bytes.len().saturating_sub(self.at))
341        {
342            return Err(invalid("declared count exceeds record"));
343        }
344        Ok(count)
345    }
346    fn reference(&mut self, store: &Store, nodes: &[Handle]) -> Result<Handle, Error> {
347        match self.take(1)?[0] {
348            0 => checked(store, self.word()?),
349            1 => usize::try_from(self.word()?)
350                .ok()
351                .and_then(|n| nodes.get(n))
352                .copied()
353                .ok_or_else(|| invalid("forward or missing local reference")),
354            _ => Err(invalid("reference tag")),
355        }
356    }
357}
358
359fn checked(store: &Store, bits: u64) -> Result<Handle, Error> {
360    let handle = Handle(bits);
361    match handle.tag() {
362        Tag::Int => Ok(handle),
363        Tag::Empty if handle == Handle::EMPTY => Ok(handle),
364        Tag::Bool if handle == Handle::TRUE || handle == Handle::FALSE => Ok(handle),
365        Tag::Str | Tag::Model
366            if u32::try_from(bits >> 3)
367                .ok()
368                .and_then(|id| store.strings().text(id))
369                .is_some() =>
370        {
371            Ok(handle)
372        }
373        Tag::Persistent => {
374            let view = store
375                .retained_view(handle)
376                .ok_or_else(|| invalid("unknown persistent coordinate"))?;
377            if view.is_lazy() || view.kind.is_lazy() || view.flags & flags::HISTORY != 0 {
378                Err(invalid("lazy or unowned persistent value"))
379            } else {
380                Ok(handle)
381            }
382        }
383        _ => Err(invalid("invalid or transient external reference")),
384    }
385}
386
387pub(crate) fn shape(
388    kind: Kind,
389    fl: u8,
390    lo: i64,
391    origin: u64,
392    data: &[Handle],
393) -> Result<(), Error> {
394    let len = data.len();
395    if data.iter().any(|h| h.is_empty())
396        || fl & !flags::VIEW != 0
397        || kind.is_lazy()
398        || matches!(kind, Kind::Fcn | Kind::RecSet) && !len.is_multiple_of(2)
399        || matches!(kind, Kind::Interval | Kind::Subset | Kind::SeqSet) && len != 1
400        || matches!(kind, Kind::FcnSet | Kind::Union) && len != 2
401        || matches!(kind, Kind::Nat | Kind::Int) && len != 0
402        || kind == Kind::SetEnum && fl & flags::UNNORM == 0
403        || fl & flags::TUPLE != 0 && (kind != Kind::IntFcn || lo != 1)
404        || fl & flags::RECORD != 0 && kind != Kind::Fcn
405        || fl & flags::UNNORM != 0 && kind != Kind::SetEnum
406        || fl & flags::HISTORY != 0
407        || origin != 0
408        || kind == Kind::BigInt
409            && (len == 0
410                || !matches!(lo, -1 | 1)
411                || data
412                    .iter()
413                    .any(|h| h.as_int().is_none_or(|n| u32::try_from(n).is_err()))
414                || data.last().and_then(|h| h.as_int()) == Some(0))
415    {
416        return Err(invalid("node shape or representation flags"));
417    }
418    Ok(())
419}
420
421pub(crate) fn kind(byte: u8) -> Result<Kind, Error> {
422    Ok(match byte {
423        0 => Kind::Set,
424        1 => Kind::IntFcn,
425        2 => Kind::Fcn,
426        3 => Kind::Interval,
427        4 => Kind::Subset,
428        5 => Kind::FcnSet,
429        6 => Kind::RecSet,
430        7 => Kind::SeqSet,
431        8 => Kind::Nat,
432        9 => Kind::Int,
433        10 => Kind::Product,
434        11 => Kind::Union,
435        14 => Kind::BigInt,
436        15 => Kind::SetEnum,
437        _ => return Err(invalid("unknown or lazy node kind")),
438    })
439}
440
441#[cfg(test)]
442#[allow(clippy::unwrap_used, reason = "owned transient payload controls")]
443mod tests {
444    use super::*;
445
446    #[test]
447    fn transient_dags_wait_for_consumption_and_preserve_shared_children() {
448        let store = Arc::new(Store::new(true));
449        let mut heap = Heap::new(Arc::clone(&store), false, false);
450        let mut codec = CandidateCodec::new(&heap).unwrap();
451        let values: Vec<_> = (0..1024).map(|n| Handle::int(n).unwrap()).collect();
452        let tuple = heap.tuple_literal(&values);
453        let parent = heap.tuple_literal(&[tuple, tuple]);
454        let before = store.stats();
455        let bytes = codec.encode(&mut heap, &[parent, parent], 1 << 20).unwrap();
456        assert_eq!(store.stats().nodes, before.nodes);
457        assert_eq!(store.stats().handles, before.handles);
458        assert!(bytes.len() < 12_000, "shared child encoded once");
459        heap.reset();
460        let roots = codec.decode(&mut heap, &bytes, 1 << 20).unwrap();
461        assert_eq!(roots[0], roots[1]);
462        assert_eq!(heap.view(roots[0]).flags & flags::TUPLE, flags::TUPLE);
463        let child = heap.view(roots[0]).data[0];
464        assert_eq!(child, heap.view(roots[0]).data[1]);
465        assert_eq!(heap.view(child).data, values);
466        assert_eq!(store.stats().nodes - before.nodes, 2);
467    }
468
469    #[test]
470    fn canonical_candidates_keep_zero_origins_and_reject_legacy_history() {
471        for semantics in [crate::Semantics::default(), crate::Semantics::tlc()] {
472            let store = Arc::new(Store::with_semantics(true, semantics));
473            let mut heap = Heap::new(Arc::clone(&store), false, false);
474            let mut codec = CandidateCodec::new(&heap).unwrap();
475            let one = Handle::int(1).unwrap();
476            let value = heap.canonical_test_set(&[one, Handle::TRUE, one]).unwrap();
477            let bytes = codec.encode(&mut heap, &[value, value], 4096).unwrap();
478            assert_eq!(&bytes[58..66], &[0; 8], "legacy origin field is zero");
479            heap.reset();
480            for (at, byte) in [(58, 1), (33, flags::HISTORY)] {
481                let mut forged = bytes.clone();
482                forged[at] = byte;
483                let before = store.stats().nodes;
484                assert!(codec.decode(&mut heap, &forged, 4096).is_err());
485                assert_eq!(
486                    store.stats().nodes,
487                    before,
488                    "invalid origin cannot promote nodes"
489                );
490            }
491            let roots = codec.decode(&mut heap, &bytes, 4096).unwrap();
492            assert_eq!(roots[0], roots[1]);
493            assert_eq!(heap.view(roots[0]).data, &[Handle::TRUE, one]);
494            assert_eq!(codec.origin_index_bytes(), 0);
495        }
496    }
497
498    #[test]
499    fn later_legacy_metadata_cannot_promote_an_earlier_valid_node() {
500        for semantics in [crate::Semantics::default(), crate::Semantics::tlc()] {
501            let store = Arc::new(Store::with_semantics(true, semantics));
502            let mut heap = Heap::new(Arc::clone(&store), false, false);
503            let mut codec = CandidateCodec::new(&heap).unwrap();
504            let one = Handle::int(1).unwrap();
505            let child = heap.canonical_test_set(&[one]).unwrap();
506            let root = heap.tuple_literal(&[child, child]);
507            let bytes = codec.encode(&mut heap, &[root], 4096).unwrap();
508            assert_eq!(&bytes[16..24], &2u64.to_le_bytes());
509            let second = HEADER + NODE_HEADER + REFERENCE;
510            heap.reset();
511            for (at, byte) in [
512                (second + 26, 1),
513                (second + 1, flags::TUPLE | flags::HISTORY),
514            ] {
515                let mut forged = bytes.clone();
516                forged[at] = byte;
517                let before = store.stats();
518                let error = codec.decode(&mut heap, &forged, 4096).unwrap_err();
519                assert!(error.message().contains("legacy construction history"));
520                assert_eq!(store.stats().nodes, before.nodes);
521                assert_eq!(store.stats().handles, before.handles);
522            }
523            let roots = codec.decode(&mut heap, &bytes, 4096).unwrap();
524            let row = heap.view(roots[0]);
525            assert!(row.is_tuple_literal());
526            assert_eq!(row.data[0], row.data[1]);
527            assert_eq!(heap.view(row.data[0]).data, &[one]);
528            assert_eq!(store.stats().nodes, 2);
529        }
530    }
531
532    #[test]
533    fn local_identity_and_materialization_do_not_promote_or_fill_persistent_cache() {
534        let store = Arc::new(Store::new(true));
535        let mut heap = Heap::new(Arc::clone(&store), false, false);
536        let interval = heap.interval(1, 128);
537        let interval = heap.intern_const(interval).unwrap();
538        let before = store.stats().nodes;
539        let old = heap.set_speculative(true);
540        let enumeration = heap.materialize_cached(interval).unwrap();
541        let tuple = heap.tuple_literal(&[interval, enumeration]);
542        let closed = heap.close_identity_local(tuple).unwrap();
543        let expected = heap.tuple(&[enumeration, enumeration]);
544        assert_eq!(heap.hash(closed), heap.hash(expected));
545        assert!(heap.eq(closed, expected));
546        assert!(enumeration.is_transient() && closed.is_transient());
547        assert_eq!(heap.view(closed).flags & !flags::CONCRETE, 0);
548        assert_eq!(store.stats().nodes, before);
549        heap.set_speculative(old);
550        let retained = heap.intern(closed).unwrap();
551        assert!(
552            retained.is_persistent(),
553            "explicit intern contract stays persistent"
554        );
555    }
556
557    #[test]
558    fn bounds_owner_corruption_lazy_and_stale_values_refuse() {
559        let store = Arc::new(Store::new(true));
560        let mut heap = Heap::new(Arc::clone(&store), false, false);
561        let mut codec = CandidateCodec::new(&heap).unwrap();
562        let tuple = heap.tuple_literal(&[Handle::TRUE; 1024]);
563        assert!(codec.encode(&mut heap, &[tuple], 100).is_err());
564        assert_eq!(store.stats().nodes, 0);
565        let bytes = codec.encode(&mut heap, &[tuple], 1 << 20).unwrap();
566        let mut other = Heap::new(Arc::clone(&store), false, false);
567        let other_tuple = other.tuple_literal(&[Handle::TRUE]);
568        assert!(codec.encode(&mut other, &[other_tuple], 1 << 20).is_err());
569        let mut foreign = CandidateCodec::new(&heap).unwrap();
570        assert!(foreign.decode(&mut heap, &bytes, 1 << 20).is_err());
571        for end in [0, 7, 16, 31, 50, bytes.len() - 1] {
572            assert!(codec.decode(&mut heap, &bytes[..end], 1 << 20).is_err());
573        }
574        let mut bad = bytes.clone();
575        bad[32] = 255;
576        assert!(codec.decode(&mut heap, &bad, 1 << 20).is_err());
577        let mut bad = bytes.clone();
578        let last = bad.len();
579        bad[last - 9] = 1;
580        bad[last - 8..].copy_from_slice(&u64::MAX.to_le_bytes());
581        assert!(codec.decode(&mut heap, &bad, 1 << 20).is_err());
582        heap.reset();
583        assert!(codec.encode(&mut heap, &[tuple], 1 << 20).is_err());
584    }
585    #[test]
586    fn speculative_step_memo_bypasses_promotion_even_when_general_memo_is_off() {
587        use crate::memo::Memo;
588        use crate::plan::{Code, MemoSite, Node};
589        let store = Arc::new(Store::new(true));
590        let opts = crate::Opts {
591            memo: false,
592            ..crate::Opts::default()
593        };
594        let mut machine = crate::Machine::new(Arc::clone(&store), 1, opts, Memo::new(&[1]));
595        let next = machine.heap.tuple_literal(&[Handle::TRUE; 32]);
596        machine.s1[0] = next;
597        let code = Code {
598            nodes: vec![
599                Node::Primed(0),
600                Node::Tuple(vec![0].into()),
601                Node::Memo { site: 0, body: 1 },
602            ],
603            sites: vec![MemoSite {
604                name: "step".into(),
605                vars: vec![].into(),
606                slots: vec![].into(),
607                primed: vec![0].into(),
608                step: true,
609                candidate: false,
610            }],
611            ..Code::default()
612        };
613        let before = store.stats().nodes;
614        machine.heap.set_speculative(true);
615        let value = machine.eval(&code, 2).unwrap();
616        assert!(value.is_transient());
617        assert_eq!(
618            store.stats().nodes,
619            before,
620            "step keys and results must not escape"
621        );
622        machine.heap.set_speculative(false);
623        let value = machine.eval(&code, 2).unwrap();
624        assert!(
625            value.is_persistent(),
626            "resident step memo still retains exact results"
627        );
628        assert!(store.stats().nodes > before);
629    }
630    #[test]
631    fn local_identity_preserves_shared_dags_and_reuses_closed_roots() {
632        for heap_mode in [false, true] {
633            let store = Arc::new(Store::new(true));
634            let mut heap = Heap::new(Arc::clone(&store), heap_mode, false);
635            let mut root = Handle::FALSE;
636            for _ in 0..20 {
637                root = heap.tuple_literal(&[root, root]);
638            }
639            let before = heap.arena().len();
640            let roots = heap.close_identity_row_local(&[root, root]).unwrap();
641            assert_eq!(roots[0], roots[1]);
642            let closed = roots[0];
643            assert_eq!(
644                heap.arena().len() - before,
645                20,
646                "one canonical header per original shared node"
647            );
648            let after = heap.arena().len();
649            assert_eq!(heap.close_identity_local(closed).unwrap(), closed);
650            assert_eq!(
651                heap.arena().len(),
652                after,
653                "already-closed DAG adds no nodes or payload"
654            );
655            let mut walk = closed;
656            for _ in 0..20 {
657                let view = heap.view(walk);
658                assert_eq!(view.flags, 0);
659                assert_eq!(view.data[0], view.data[1]);
660                walk = view.data[0];
661            }
662            let codec = CandidateCodec::new(&heap).unwrap();
663            let bytes = codec.encode(&mut heap, &[closed], 4096).unwrap();
664            assert!(
665                bytes.len() < 1500,
666                "twenty-node DAG must not become its expanded tree"
667            );
668            assert_eq!(store.stats().nodes, 0);
669        }
670    }
671
672    #[test]
673    fn local_closure_has_a_per_operation_visited_bound() {
674        let store = Arc::new(Store::new(true));
675        let mut heap = Heap::new(Arc::clone(&store), false, false);
676        let children: Vec<_> = (0..=crate::heap::MAX_LOCAL_CLOSE_ENTRIES)
677            .map(|_| heap.tuple_literal(&[Handle::TRUE]))
678            .collect();
679        let root = heap.tuple_literal(&children);
680        let error = heap.close_identity_local(root).unwrap_err();
681        assert!(error.message().contains("visited-node bound"));
682        assert_eq!(store.stats().nodes, 0);
683    }
684}