1use std::cmp::Ordering;
6use std::sync::Arc;
7
8use crate::Error;
9use crate::arena::{Arena, Mark};
10use crate::handle::{Handle, K_FCN, K_SET, K_SYM, Tag, fin, int_hash, mix2, mix64, scalar_hash};
11use crate::node::{Kind, View, flags};
12use crate::store::Store;
13
14pub const MAX_MATERIALIZE: usize = 1 << 24;
16
17pub const MAX_CONSTANT_DOMAIN: usize = 1 << 16;
20
21pub const MAX_CONSTANT_DOMAIN_WORDS: usize = 1 << 20;
26
27pub const MAX_LOCAL_CLOSE_ENTRIES: usize = 65_536;
29pub const MAX_LOCAL_CLOSE_SCRATCH_BYTES: usize = 64 * 1024 * 1024;
31
32#[derive(Default)]
33struct LocalClose {
34 visited: std::collections::HashMap<Handle, Handle>,
35 scratch: usize,
36}
37
38impl LocalClose {
39 fn remember(&mut self, source: Handle, closed: Handle) -> Result<(), Error> {
40 if !self.visited.contains_key(&source) {
41 if self.visited.len() >= MAX_LOCAL_CLOSE_ENTRIES {
42 return Err(Error::unsupported(
43 "candidate identity closure visited-node bound",
44 ));
45 }
46 self.visited
47 .try_reserve(1)
48 .map_err(|_| Error::unsupported("candidate identity closure map allocation"))?;
49 }
50 self.visited.insert(source, closed);
51 Ok(())
52 }
53}
54
55static EMPTY_DATA: [Handle; 0] = [];
56
57#[derive(Debug)]
60pub struct Heap {
61 pub(crate) store: Arc<Store>,
62 pub(crate) arena: Arena,
63 pub(crate) defer_reclamation: bool,
64 pub(crate) speculative: bool,
66 strings: StringMode,
69 poisoned: std::cell::Cell<bool>,
70 pub(crate) full_hash: bool,
72 pub(crate) int_mode: crate::int::IntMode,
74 materialized: std::collections::HashMap<Handle, Handle>,
77 constant_domains: std::collections::HashMap<Handle, Option<Handle>>,
80 pub(crate) sym_images: crate::symmetry::ImageCache,
84 work_control: Option<Arc<dyn crate::eval::WorkControl>>,
85 work_steps: std::cell::Cell<u32>,
86 work_interrupted: std::cell::Cell<bool>,
87 names: std::cell::RefCell<Names>,
91 pub(crate) cache: crate::store::InternCache,
94}
95
96impl Drop for Heap {
97 fn drop(&mut self) {
98 self.store.flush_hits(&mut self.cache);
99 }
100}
101
102#[derive(Debug, Default)]
110struct Names {
111 texts: Vec<Arc<str>>,
112 ranks: Arc<[u32]>,
113}
114
115impl Names {
116 fn sync(&mut self, strings: &crate::strings::Strings, id: u32) {
119 if (id as usize) < self.texts.len() {
120 return;
121 }
122 let more = strings.texts_from(self.texts.len());
123 if more.is_empty() {
124 return;
125 }
126 self.texts.extend(more);
127 self.ranks = strings.ranks();
128 }
129}
130
131#[derive(Clone, Copy, Debug)]
133pub struct Closure<'a> {
134 pub kind: Kind,
136 pub id: u32,
138 pub domain: Handle,
140 pub captures: &'a [Handle],
142}
143
144#[must_use]
146pub fn set_hash(len: usize, sum: u64) -> u64 {
147 fin(K_SET, len as u64, sum)
148}
149
150#[must_use]
152pub fn fcn_hash(len: usize, sum: u64) -> u64 {
153 fin(K_FCN, len as u64, sum)
154}
155
156impl Heap {
157 #[must_use]
159 pub fn new(store: Arc<Store>, heap_arena: bool, full_hash: bool) -> Self {
160 let int_mode = store.int_mode();
161 Self {
162 store,
163 arena: Arena::new(heap_arena),
164 defer_reclamation: false,
165 speculative: false,
166 strings: StringMode::Intern,
167 poisoned: std::cell::Cell::new(false),
168 full_hash,
169 int_mode,
170 materialized: std::collections::HashMap::new(),
171 constant_domains: std::collections::HashMap::new(),
172 sym_images: crate::symmetry::ImageCache::default(),
173 work_control: None,
174 work_steps: std::cell::Cell::new(0),
175 work_interrupted: std::cell::Cell::new(false),
176 names: std::cell::RefCell::new(Names::default()),
177 cache: crate::store::InternCache::default(),
178 }
179 }
180
181 #[inline]
185 pub(crate) fn str_cmp(&self, a: u32, b: u32) -> Ordering {
186 if a == b {
187 return Ordering::Equal;
188 }
189 {
190 let names = self.names.borrow();
191 if let (Some(x), Some(y)) = (names.ranks.get(a as usize), names.ranks.get(b as usize)) {
192 return x.cmp(y);
193 }
194 }
195 self.str_cmp_unranked(a, b)
196 }
197
198 #[inline(never)]
201 fn str_cmp_unranked(&self, a: u32, b: u32) -> Ordering {
202 let strings = self.store.strings();
203 let mut names = self.names.borrow_mut();
204 names.sync(strings, a.max(b));
205 if let (Some(x), Some(y)) = (names.ranks.get(a as usize), names.ranks.get(b as usize)) {
206 return x.cmp(y);
207 }
208 if strings.order() == crate::strings::StringOrder::Token {
209 return a.cmp(&b);
210 }
211 match (names.texts.get(a as usize), names.texts.get(b as usize)) {
212 (Some(x), Some(y)) => x.cmp(y),
213 _ => a.cmp(&b),
214 }
215 }
216
217 #[inline]
219 pub(crate) fn known_name(&self, id: u32) -> bool {
220 if (id as usize) < self.names.borrow().texts.len() {
221 return true;
222 }
223 let mut names = self.names.borrow_mut();
224 names.sync(self.store.strings(), id);
225 (id as usize) < names.texts.len()
226 }
227
228 pub(crate) fn model_type(&self, id: u32) -> Option<u16> {
231 let mut names = self.names.borrow_mut();
232 names.sync(self.store.strings(), id);
233 let mut units = names.texts.get(id as usize)?.encode_utf16();
234 let (first, second) = (units.next()?, units.next()?);
235 (second == u16::from(b'_') && units.next().is_some()).then_some(first)
236 }
237
238 #[must_use]
240 pub fn store(&self) -> &Arc<Store> {
241 &self.store
242 }
243
244 #[must_use]
246 pub fn arena(&self) -> &Arena {
247 &self.arena
248 }
249
250 pub fn reset(&mut self) {
252 self.arena.reset();
253 self.store.flush_hits(&mut self.cache);
254 }
255
256 #[must_use]
258 pub fn mark(&self) -> Mark {
259 self.arena.mark()
260 }
261
262 pub fn rollback(&mut self, mark: Mark) {
266 if !self.defer_reclamation {
267 self.arena.rollback(mark);
268 }
269 }
270
271 #[must_use]
277 pub fn poisoned(&self) -> bool {
278 self.poisoned.get() || self.arena.stale() || self.store.poisoned()
279 }
280
281 #[must_use]
284 #[inline]
285 pub fn view(&self, h: Handle) -> View<'_> {
286 if h.is_persistent() {
287 return self.store.view(h);
288 }
289 if h.is_transient()
290 && let Some(v) = self.arena.lookup(h)
291 {
292 return v;
293 }
294 self.poison_view()
295 }
296
297 #[cold]
298 fn poison_view(&self) -> View<'_> {
299 self.poisoned.set(true);
300 View {
301 kind: Kind::Set,
302 lo: 0,
303 hash: 0,
304 sum: 0,
305 flags: 0,
306 data: &EMPTY_DATA,
307 }
308 }
309
310 #[cold]
313 fn lazy_misuse(&self) {
314 self.poisoned.set(true);
315 }
316
317 #[inline]
319 fn child(&self, h: Handle) -> (u64, u8) {
320 if let Some(s) = scalar_hash(h) {
321 return (s, 0);
322 }
323 let v = self.view(h);
324 let hash = if self.full_hash {
325 self.deep_hash(h)
326 } else {
327 v.hash
328 };
329 (
330 hash,
331 (v.flags & flags::LAZY) | (v.flags & flags::NESTED_VIEW),
332 )
333 }
334
335 #[inline]
339 fn concrete_child(&self, h: Handle) -> bool {
340 if !h.is_compound() {
341 return h
342 .as_str_id()
343 .or_else(|| h.as_model_id())
344 .is_none_or(|id| self.known_name(id));
345 }
346 let v = self.view(h);
347 v.flags & flags::CONCRETE != 0 || (v.kind == Kind::BigInt && !v.is_lazy())
348 }
349
350 fn concrete_bit(&self, children: &[Handle]) -> u8 {
352 if children.iter().all(|&c| self.concrete_child(c)) {
353 flags::CONCRETE
354 } else {
355 0
356 }
357 }
358
359 #[must_use]
368 pub fn proved_concrete(&self, h: Handle) -> bool {
369 if h.is_empty() || h.is_transient() {
370 return false;
371 }
372 if !h.is_compound() {
373 return h
374 .as_str_id()
375 .or_else(|| h.as_model_id())
376 .is_none_or(|id| self.known_name(id));
377 }
378 let v = self.view(h);
379 !v.is_lazy()
380 && v.flags & flags::UNNORM == 0
381 && (v.flags & flags::CONCRETE != 0 || v.kind == Kind::BigInt)
382 }
383
384 #[must_use]
396 pub fn materialized_within(
397 &self,
398 roots: &[Handle],
399 nodes: usize,
400 name_bytes: Option<usize>,
401 ) -> bool {
402 let mut pending = Vec::new();
403 if pending.try_reserve(roots.len()).is_err() {
404 return false;
405 }
406 pending.extend_from_slice(roots);
407 let (mut work, mut bytes) = (0usize, 0usize);
408 while let Some(h) = pending.pop() {
409 work += 1;
410 if work > nodes || h.is_empty() || h.is_transient() {
411 return false;
412 }
413 if !h.is_compound() {
414 let Some(id) = h.as_str_id().or_else(|| h.as_model_id()) else {
415 continue;
416 };
417 if !self.known_name(id) {
418 return false;
419 }
420 if let Some(limit) = name_bytes {
421 let Some(len) = self.names.borrow().texts.get(id as usize).map(|t| t.len())
422 else {
423 return false;
424 };
425 bytes = bytes.saturating_add(len);
426 if bytes > limit {
427 return false;
428 }
429 }
430 continue;
431 }
432 let v = self.view(h);
433 if v.is_lazy() || v.flags & flags::UNNORM != 0 {
434 return false;
435 }
436 if name_bytes.is_none() && v.flags & flags::CONCRETE != 0 {
437 continue;
438 }
439 match v.kind {
440 Kind::BigInt => continue,
441 Kind::Set | Kind::IntFcn | Kind::Fcn => {}
442 _ => return false,
443 }
444 if v.data.len() > nodes.saturating_sub(work).saturating_sub(pending.len())
445 || pending.try_reserve(v.data.len()).is_err()
446 {
447 return false;
448 }
449 pending.extend_from_slice(v.data);
450 }
451 !self.poisoned()
452 }
453
454 #[must_use]
457 pub fn is_lazy(&self, h: Handle) -> bool {
458 h.is_compound() && self.view(h).is_lazy()
459 }
460
461 #[must_use]
463 pub fn kind(&self, h: Handle) -> Option<Kind> {
464 h.is_compound().then(|| self.view(h).kind)
465 }
466
467 #[must_use]
470 pub fn hash(&self, h: Handle) -> u64 {
471 if let Some(s) = scalar_hash(h) {
472 return s;
473 }
474 let v = self.view(h);
475 if v.is_lazy() {
476 self.lazy_misuse();
477 }
478 if self.full_hash {
479 return self.deep_hash(h);
480 }
481 v.hash
482 }
483
484 #[must_use]
487 pub fn deep_hash(&self, h: Handle) -> u64 {
488 if let Some(s) = scalar_hash(h) {
489 return s;
490 }
491 let v = self.view(h);
492 match v.kind {
493 Kind::Set => {
494 let sum = v
495 .data
496 .iter()
497 .fold(0u64, |a, &e| a.wrapping_add(self.deep_hash(e)));
498 set_hash(v.data.len(), sum)
499 }
500 Kind::IntFcn => {
501 let mut sum = 0u64;
502 for (i, &x) in v.data.iter().enumerate() {
503 #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
504 let k = v.lo + i as i64;
505 sum = sum.wrapping_add(mix2(int_hash(k), self.deep_hash(x)));
506 }
507 fcn_hash(v.data.len(), sum)
508 }
509 Kind::Fcn => {
510 let mut sum = 0u64;
511 for (&k, &x) in v.keys().iter().zip(v.values()) {
512 sum = sum.wrapping_add(mix2(self.deep_hash(k), self.deep_hash(x)));
513 }
514 fcn_hash(v.len(), sum)
515 }
516 _ => v.hash,
517 }
518 }
519
520 #[must_use]
526 pub fn eq(&self, a: Handle, b: Handle) -> bool {
527 if a == b {
528 return true;
529 }
530 if !a.is_compound() || !b.is_compound() {
531 return false;
532 }
533 if a.is_persistent()
534 && b.is_persistent()
535 && self.store.hashcons()
536 && !a.is_lazy_persistent()
537 && !b.is_lazy_persistent()
538 {
539 return false;
540 }
541 let (va, vb) = (self.view(a), self.view(b));
542 if va.is_lazy() || vb.is_lazy() {
543 self.lazy_misuse();
544 return false;
545 }
546 if va.hash != vb.hash
547 || va.kind != vb.kind
548 || (va.kind != Kind::Set && va.lo != vb.lo)
549 || va.data.len() != vb.data.len()
550 {
551 return false;
552 }
553 va.data.iter().zip(vb.data).all(|(&x, &y)| self.eq(x, y))
554 }
555
556 fn scalar_rank(h: Handle) -> u8 {
559 match h.tag() {
560 Tag::Empty => 0,
561 Tag::Model => 1,
562 Tag::Bool => 2,
563 Tag::Int => 3,
564 Tag::Str => 4,
565 Tag::Persistent | Tag::Transient => 5,
566 }
567 }
568
569 fn kind_rank(k: Kind) -> u8 {
570 match k {
571 Kind::Set => 4,
572 Kind::IntFcn | Kind::Fcn => 5,
573 _ => 6,
574 }
575 }
576
577 #[must_use]
583 pub fn cmp(&self, a: Handle, b: Handle) -> Ordering {
584 if a == b {
585 return Ordering::Equal;
586 }
587 let (mut ra, mut rb) = (Self::scalar_rank(a), Self::scalar_rank(b));
588 if ra != rb {
589 if a.is_compound() && self.view(a).kind == Kind::BigInt {
591 ra = 3;
592 }
593 if b.is_compound() && self.view(b).kind == Kind::BigInt {
594 rb = 3;
595 }
596 if ra != rb {
597 return ra.cmp(&rb);
598 }
599 return self.int_cmp(a, b).unwrap_or(Ordering::Equal);
600 }
601 match a.tag() {
602 Tag::Bool => a.as_bool().cmp(&b.as_bool()),
603 Tag::Int => a.as_int().cmp(&b.as_int()),
604 Tag::Str => match (a.as_str_id(), b.as_str_id()) {
605 (Some(x), Some(y)) => self.str_cmp(x, y),
606 _ => Ordering::Equal,
607 },
608 Tag::Model => match (a.as_model_id(), b.as_model_id()) {
610 (Some(x), Some(y)) => self.str_cmp(x, y),
611 _ => Ordering::Equal,
612 },
613 Tag::Persistent | Tag::Transient => self.cmp_compound(a, b),
614 Tag::Empty => Ordering::Equal,
615 }
616 }
617
618 fn cmp_compound(&self, a: Handle, b: Handle) -> Ordering {
619 let (va, vb) = (self.view(a), self.view(b));
620 if va.is_lazy() || vb.is_lazy() {
621 self.lazy_misuse();
622 return Ordering::Equal;
623 }
624 if va.kind == Kind::BigInt || vb.kind == Kind::BigInt {
625 return match (va.kind == Kind::BigInt, vb.kind == Kind::BigInt) {
626 (true, true) => self.int_cmp(a, b).unwrap_or(Ordering::Equal),
627 (true, false) => Ordering::Less,
628 _ => Ordering::Greater,
629 };
630 }
631 let (ra, rb) = (Self::kind_rank(va.kind), Self::kind_rank(vb.kind));
632 if ra != rb {
633 return ra.cmp(&rb);
634 }
635 match (va.kind, vb.kind) {
636 (Kind::Set, Kind::Set) => va.data.len().cmp(&vb.data.len()).then_with(|| {
637 for (&x, &y) in va.data.iter().zip(vb.data) {
638 let c = self.cmp(x, y);
639 if c != Ordering::Equal {
640 return c;
641 }
642 }
643 Ordering::Equal
644 }),
645 (Kind::IntFcn, Kind::IntFcn) if va.lo == vb.lo && va.data.len() == vb.data.len() => {
648 for (&x, &y) in va.data.iter().zip(vb.data) {
649 let c = self.cmp(x, y);
650 if c != Ordering::Equal {
651 return c;
652 }
653 }
654 Ordering::Equal
655 }
656 (ka, kb) if ka.is_fcn() && kb.is_fcn() => {
657 let n = va.len();
658 n.cmp(&vb.len()).then_with(|| {
659 for i in 0..n {
660 let c = self.cmp(fcn_key(&va, i), fcn_key(&vb, i));
661 if c != Ordering::Equal {
662 return c;
663 }
664 }
665 for (&x, &y) in va.values().iter().zip(vb.values()) {
666 let c = self.cmp(x, y);
667 if c != Ordering::Equal {
668 return c;
669 }
670 }
671 Ordering::Equal
672 })
673 }
674 (ka, kb) => (ka as u8)
675 .cmp(&(kb as u8))
676 .then(va.lo.cmp(&vb.lo))
677 .then(va.data.len().cmp(&vb.data.len()))
678 .then_with(|| {
679 for (&x, &y) in va.data.iter().zip(vb.data) {
680 let c = self.cmp(x, y);
681 if c != Ordering::Equal {
682 return c;
683 }
684 }
685 Ordering::Equal
686 }),
687 }
688 }
689
690 pub fn set_from(&mut self, elems: &mut Vec<Handle>) -> Handle {
696 if elems.len() > 1 {
697 elems.sort_unstable_by(|&a, &b| self.cmp(a, b));
698 elems.dedup_by(|a, b| self.eq(*a, *b));
699 }
700 self.set_sorted(elems)
701 }
702
703 pub fn set_sorted(&mut self, elems: &[Handle]) -> Handle {
706 let mut sum = 0u64;
707 let mut lazy = 0;
708 for &e in elems {
709 let (h, f) = self.child(e);
710 sum = sum.wrapping_add(h);
711 lazy |= f;
712 }
713 if lazy & flags::LAZY != 0 {
714 self.lazy_misuse();
715 }
716 let concrete = self.concrete_bit(elems);
717 self.arena.alloc(
718 Kind::Set,
719 concrete,
720 0,
721 set_hash(elems.len(), sum),
722 sum,
723 elems,
724 )
725 }
726
727 pub fn empty_set(&mut self) -> Handle {
729 self.set_sorted(&[])
730 }
731
732 pub fn int_fcn(&mut self, lo: i64, vals: &[Handle]) -> Handle {
734 self.int_fcn_as(lo, vals, 0)
735 }
736
737 pub(crate) fn int_fcn_as(&mut self, lo: i64, vals: &[Handle], view: u8) -> Handle {
738 let lo = if vals.is_empty() { 1 } else { lo };
739 let mut sum = 0u64;
740 let mut fl = 0;
741 for (i, &v) in vals.iter().enumerate() {
742 #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
743 let k = lo + i as i64;
744 let (h, f) = self.child(v);
745 sum = sum.wrapping_add(mix2(int_hash(k), h));
746 fl |= f;
747 }
748 if fl & flags::LAZY == 0 {
749 fl |= self.concrete_bit(vals);
750 }
751 self.arena.alloc(
752 Kind::IntFcn,
753 fl | view,
754 lo,
755 fcn_hash(vals.len(), sum),
756 sum,
757 vals,
758 )
759 }
760
761 pub fn tuple(&mut self, vals: &[Handle]) -> Handle {
763 self.int_fcn(1, vals)
764 }
765
766 pub fn tuple_literal(&mut self, vals: &[Handle]) -> Handle {
769 self.int_fcn_as(1, vals, flags::TUPLE)
770 }
771
772 pub fn fcn_sorted(&mut self, keys: &[Handle], vals: &[Handle]) -> Handle {
775 self.fcn_sorted_as(keys, vals, 0)
776 }
777
778 pub(crate) fn fcn_sorted_as(&mut self, keys: &[Handle], vals: &[Handle], view: u8) -> Handle {
779 if let Some(lo) = contiguous_ints(keys) {
780 return self.int_fcn(lo, vals);
781 }
782 let mut sum = 0u64;
783 let mut fl = 0;
784 for (&k, &v) in keys.iter().zip(vals) {
785 let (kh, kf) = self.child(k);
786 let (vh, vf) = self.child(v);
787 if kf & flags::LAZY != 0 {
791 self.lazy_misuse();
792 }
793 sum = sum.wrapping_add(mix2(kh, vh));
794 fl |= kf | vf;
795 }
796 let mut data = Vec::with_capacity(keys.len() * 2);
797 data.extend_from_slice(keys);
798 data.extend_from_slice(vals);
799 if fl & flags::LAZY == 0 {
800 fl |= self.concrete_bit(&data);
801 }
802 self.arena.alloc(
803 Kind::Fcn,
804 fl | view,
805 0,
806 fcn_hash(keys.len(), sum),
807 sum,
808 &data,
809 )
810 }
811
812 pub fn fcn_from_pairs(&mut self, pairs: &mut [(Handle, Handle)]) -> Handle {
814 pairs.sort_unstable_by(|a, b| self.cmp(a.0, b.0));
815 let keys: Vec<Handle> = pairs.iter().map(|p| p.0).collect();
816 let vals: Vec<Handle> = pairs.iter().map(|p| p.1).collect();
817 self.fcn_sorted(&keys, &vals)
818 }
819
820 pub fn record(&mut self, keys: &[Handle], vals: &[Handle]) -> Handle {
825 self.fcn_sorted_as(keys, vals, flags::RECORD)
826 }
827
828 #[cfg(test)]
829 pub(crate) fn canonical_test_set(&mut self, elems: &[Handle]) -> Result<Handle, Error> {
830 crate::compare::require_materialized(self, elems)?;
831 Ok(self.set_from(&mut elems.to_vec()))
832 }
833
834 pub fn set_enum(&mut self, elems: &[Handle]) -> Handle {
840 self.symbolic(Kind::SetEnum, 0, elems)
841 }
842
843 #[allow(
846 clippy::many_single_char_names,
847 reason = "short names for the hash algebra"
848 )]
849 pub fn fcn_with(&mut self, f: Handle, i: usize, new: Handle) -> Handle {
850 let v = self.view(f);
851 let (kind, lo, sum, n, was_lazy) = (v.kind, v.lo, v.sum, v.len(), v.is_lazy());
852 let was_concrete = v.flags & flags::CONCRETE != 0;
853 let record = v.flags & (flags::RECORD | flags::TUPLE);
855 let mut data = v.data.to_vec();
856 let (key_hash, slot) = match kind {
857 Kind::IntFcn => {
858 #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
859 let k = lo + i as i64;
860 (int_hash(k), i)
861 }
862 _ => (self.child(data[i]).0, n + i),
863 };
864 let old = data[slot];
865 data[slot] = new;
866 let fl = if was_lazy {
868 let vals = if kind == Kind::IntFcn {
869 &data[..]
870 } else {
871 &data[n..]
872 };
873 vals.iter().fold(0, |a, &x| a | self.child(x).1)
874 } else {
875 (v.flags & flags::NESTED_VIEW) | self.child(new).1
876 };
877 let sum = if self.full_hash {
878 let mut s = 0u64;
880 for j in 0..n {
881 let (kh, x) = match kind {
882 Kind::IntFcn => {
883 #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
884 let k = lo + j as i64;
885 (int_hash(k), data[j])
886 }
887 _ => (self.child(data[j]).0, data[n + j]),
888 };
889 s = s.wrapping_add(mix2(kh, self.child(x).0));
890 }
891 s
892 } else {
893 sum.wrapping_sub(mix2(key_hash, self.child(old).0))
894 .wrapping_add(mix2(key_hash, self.child(new).0))
895 };
896 let concrete = if was_concrete && fl & flags::LAZY == 0 && self.concrete_child(new) {
897 flags::CONCRETE
898 } else {
899 0
900 };
901 self.arena.alloc(
902 kind,
903 fl | record | concrete,
904 lo,
905 fcn_hash(n, sum),
906 sum,
907 &data,
908 )
909 }
910
911 pub fn symbolic(&mut self, kind: Kind, lo: i64, data: &[Handle]) -> Handle {
914 let mut h = mix64(K_SYM ^ (kind as u64) ^ lo.cast_unsigned().rotate_left(17));
915 let mut fl = if kind.is_lazy() { flags::LAZY } else { 0 };
916 for &d in data {
917 let (dh, df) = self.child(d);
918 h = mix2(h, dh);
919 fl |= df;
920 }
921 if kind == Kind::SetEnum {
922 if fl & flags::LAZY != 0 {
923 self.lazy_misuse();
924 }
925 fl |= flags::UNNORM;
926 }
927 self.arena.alloc(kind, fl, lo, h, 0, data)
928 }
929
930 pub fn lambda(&mut self, closure: u32, domain: Handle, captures: &[Handle]) -> Handle {
933 self.closure_node(Kind::Lambda, closure, domain, captures)
934 }
935
936 pub fn set_pred(&mut self, closure: u32, base: Handle, captures: &[Handle]) -> Handle {
939 self.closure_node(Kind::SetPred, closure, base, captures)
940 }
941
942 fn closure_node(&mut self, kind: Kind, id: u32, first: Handle, captures: &[Handle]) -> Handle {
943 let mut data = Vec::with_capacity(captures.len() + 1);
944 data.push(first);
945 data.extend_from_slice(captures);
946 self.symbolic(kind, i64::from(id), &data)
947 }
948
949 pub fn union(&mut self, a: Handle, b: Handle) -> Handle {
952 self.symbolic(Kind::Union, 0, &[a, b])
953 }
954
955 #[must_use]
957 pub fn closure(&self, h: Handle) -> Option<Closure<'_>> {
958 if !h.is_compound() {
959 return None;
960 }
961 let v = self.view(h);
962 if !v.kind.is_lazy() {
963 return None;
964 }
965 let (&first, captures) = v.data.split_first()?;
966 Some(Closure {
967 kind: v.kind,
968 id: u32::try_from(v.lo).ok()?,
969 domain: first,
970 captures,
971 })
972 }
973
974 pub fn rebuild(&mut self, h: Handle, data: &[Handle]) -> Handle {
980 if !h.is_compound() {
981 return h;
982 }
983 let v = self.view(h);
984 let (kind, lo, n) = (v.kind, v.lo, v.data.len());
985 if data.len() != n {
986 self.lazy_misuse();
987 return h;
988 }
989 match kind {
990 Kind::Set => self.set_from(&mut data.to_vec()),
991 Kind::IntFcn => self.int_fcn(lo, data),
992 Kind::Fcn => {
993 let (keys, vals) = data.split_at(n / 2);
994 self.fcn_sorted(keys, vals)
995 }
996 _ => self.symbolic(kind, lo, data),
997 }
998 }
999
1000 pub fn interval(&mut self, lo: i64, hi: i64) -> Handle {
1002 let hi_h = Handle::int(hi).unwrap_or(Handle::EMPTY);
1003 self.symbolic(Kind::Interval, lo, &[hi_h])
1004 }
1005
1006 #[must_use]
1012 pub fn is_finite(&self, h: Handle) -> bool {
1013 if !h.is_compound() {
1014 return true;
1015 }
1016 let v = self.view(h);
1017 match v.kind {
1018 Kind::Set
1019 | Kind::IntFcn
1020 | Kind::Fcn
1021 | Kind::Lambda
1022 | Kind::BigInt
1023 | Kind::Interval
1024 | Kind::SetEnum => true,
1025 Kind::Nat | Kind::Int => false,
1026 Kind::SeqSet => self.view_is_empty_set(v.data[0]),
1027 Kind::Subset | Kind::FcnSet | Kind::Product => {
1028 v.data.iter().all(|&d| self.is_finite(d))
1029 }
1030 Kind::RecSet => v.data[v.data.len() / 2..]
1031 .iter()
1032 .all(|&d| self.is_finite(d)),
1033 Kind::Union => v.data.iter().all(|&d| self.is_finite(d)),
1034 Kind::SetPred => self.is_finite(v.data[0]),
1035 }
1036 }
1037
1038 fn view_is_empty_set(&self, h: Handle) -> bool {
1039 h.is_compound() && {
1040 let v = self.view(h);
1041 v.kind == Kind::Set && v.data.is_empty()
1042 }
1043 }
1044
1045 pub fn norm(&mut self, h: Handle) -> Result<Handle, Error> {
1051 if !h.is_compound() {
1052 return Ok(h);
1053 }
1054 let v = self.view(h);
1055 if !v.kind.is_symbolic() || v.is_lazy() || !self.is_finite(h) {
1056 return Ok(h);
1057 }
1058 self.materialize(h)
1059 }
1060
1061 pub fn materialize(&mut self, h: Handle) -> Result<Handle, Error> {
1067 self.materialize_fresh(h)
1068 }
1069
1070 pub fn materialize_cached(&mut self, h: Handle) -> Result<Handle, Error> {
1078 if h.is_persistent() && !self.speculative {
1079 if let Some(&m) = self.materialized.get(&h) {
1080 return Ok(m);
1081 }
1082 let m = self.materialize_fresh(h)?;
1083 let m = self.intern(m)?;
1084 self.materialized.insert(h, m);
1085 return Ok(m);
1086 }
1087 self.materialize_fresh(h)
1088 }
1089
1090 pub fn enumerate_constant(&mut self, h: Handle) -> Result<Handle, Error> {
1105 if !h.is_compound() || !h.is_persistent() || self.speculative {
1106 return self.norm(h);
1107 }
1108 let kept = self.constant_domains.get(&h).copied();
1109 if let Some(Some(m)) = kept {
1110 return Ok(m);
1111 }
1112 let v = self.view(h);
1113 if !v.kind.is_symbolic() || v.is_lazy() || !self.is_finite(h) {
1114 return Ok(h);
1115 }
1116 let m = self.materialize_fresh(h)?;
1117 if kept.is_some() {
1118 return Ok(m);
1119 }
1120 let exact = if self.view(m).data.len() > MAX_CONSTANT_DOMAIN
1124 || !self.within_transient_words(m, MAX_CONSTANT_DOMAIN_WORDS)
1125 || !crate::compare::materialized(self, m, 0)?
1126 {
1127 None
1128 } else {
1129 match (self.intern_exact(m), self.intern(m)) {
1130 (Ok(exact), Ok(canonical)) if exact == canonical => Some(exact),
1131 _ => None,
1132 }
1133 };
1134 self.constant_domains.insert(h, exact);
1135 Ok(exact.unwrap_or(m))
1136 }
1137
1138 fn within_transient_words(&self, h: Handle, budget: usize) -> bool {
1143 let mut left = budget;
1144 let mut stack = vec![h];
1145 while let Some(n) = stack.pop() {
1146 if !n.is_compound() || !n.is_transient() {
1147 continue;
1148 }
1149 let data = self.view(n).data;
1150 let Some(rest) = left.checked_sub(1 + data.len()) else {
1151 return false;
1152 };
1153 left = rest;
1154 stack.extend(data.iter().copied().filter(|d| d.is_transient()));
1155 }
1156 true
1157 }
1158
1159 fn materialize_fresh(&mut self, h: Handle) -> Result<Handle, Error> {
1160 let mut cur = self.cursor(h)?;
1161 let mut out = Vec::new();
1162 while let Some(e) = cur.next(self)? {
1163 if out.len() >= MAX_MATERIALIZE {
1164 return Err(Error::unsupported(
1165 "materializing a set of more than 2^24 elements",
1166 ));
1167 }
1168 out.push(e);
1169 }
1170 Ok(self.set_sorted(&out))
1171 }
1172
1173 pub fn elements(&mut self, h: Handle) -> Result<Vec<Handle>, Error> {
1178 if h.is_compound() {
1179 let v = self.view(h);
1180 if v.kind == Kind::Set {
1181 return Ok(v.data.to_vec());
1182 }
1183 }
1184 let mut cur = self.cursor(h)?;
1185 let mut out = Vec::new();
1186 while let Some(e) = cur.next(self)? {
1187 if out.len() >= MAX_MATERIALIZE {
1188 return Err(Error::unsupported(
1189 "enumerating a set of more than 2^24 elements",
1190 ));
1191 }
1192 out.push(e);
1193 }
1194 Ok(out)
1195 }
1196
1197 pub(crate) fn product_empty(&self, h: Handle) -> Result<(Option<bool>, usize), Error> {
1201 let mut work = 0;
1202 let result = self.concrete_product_empty(h, 0, &mut work)?;
1203 Ok((result, work))
1204 }
1205
1206 fn concrete_product_empty(
1207 &self,
1208 h: Handle,
1209 depth: u8,
1210 work: &mut usize,
1211 ) -> Result<Option<bool>, Error> {
1212 self.work_poll()?;
1213 *work = work.saturating_add(1);
1214 if depth >= 64 || !h.is_compound() {
1215 return Ok(None);
1216 }
1217 let view = self.view(h);
1218 match view.kind {
1219 Kind::Set | Kind::SetEnum => Ok(Some(view.data.is_empty())),
1220 Kind::Interval => Ok(view.data.first().and_then(|h| h.as_int()).and_then(|hi| {
1221 if hi < view.lo {
1222 Some(true)
1223 } else {
1224 hi.checked_sub(view.lo)
1225 .and_then(|n| n.checked_add(1))
1226 .filter(|&n| n <= i64::from(i32::MAX))
1227 .map(|_| false)
1228 }
1229 })),
1230 Kind::Product => {
1231 for &axis in view.data {
1232 match self.concrete_product_empty(axis, depth + 1, work)? {
1233 Some(false) => {}
1234 empty => return Ok(empty),
1235 }
1236 }
1237 Ok(Some(false))
1238 }
1239 _ => Ok(None),
1240 }
1241 }
1242
1243 pub fn cursor(&mut self, h: Handle) -> Result<Cursor, Error> {
1248 if !h.is_compound() {
1249 return Err(Error::eval(
1250 "attempted to enumerate a value that is not a set",
1251 ));
1252 }
1253 let v = self.view(h);
1254 let (kind, lo, data) = (v.kind, v.lo, v.data.to_vec());
1255 Ok(match kind {
1256 Kind::Set => Cursor::Array { set: h, i: 0 },
1257 Kind::Interval => Cursor::Range {
1258 cur: lo,
1259 hi: data[0].as_int().unwrap_or(lo - 1),
1260 },
1261 Kind::Product => {
1262 if self.product_empty(h)?.0 == Some(true) {
1266 return Ok(Cursor::Array {
1267 set: self.empty_set(),
1268 i: 0,
1269 });
1270 }
1271 let comps = data
1272 .iter()
1273 .map(|&s| {
1274 let s = self.norm(s)?;
1275 self.elements(s)
1276 })
1277 .collect::<Result<Vec<_>, Error>>()?;
1278 Cursor::odometer(Shape::Tuple, comps)
1279 }
1280 Kind::FcnSet => {
1281 let dom = self.norm(data[0])?;
1282 let keys = self.elements(dom)?;
1283 let rng = self.norm(data[1])?;
1284 let r = self.elements(rng)?;
1285 let comps = vec![r; keys.len()];
1286 Cursor::odometer(Shape::Fcn(keys), comps)
1287 }
1288 Kind::RecSet => {
1289 let n = data.len() / 2;
1290 let names = data[..n].to_vec();
1291 let comps = data[n..]
1292 .iter()
1293 .map(|&s| {
1294 let s = self.norm(s)?;
1295 self.elements(s)
1296 })
1297 .collect::<Result<Vec<_>, Error>>()?;
1298 Cursor::odometer(Shape::Fcn(names), comps)
1299 }
1300 Kind::Subset => {
1301 let base = self.norm(data[0])?;
1302 let elems = self.elements(base)?;
1303 if elems.len() > 24 {
1304 return Err(Error::unsupported(
1305 "enumerating SUBSET of a set of more than 24 elements",
1306 ));
1307 }
1308 Cursor::Subset {
1309 elems,
1310 k: 0,
1311 combo: Vec::new(),
1312 started: false,
1313 }
1314 }
1315 Kind::SetEnum => {
1316 let mut v = data;
1317 let set = self.set_from(&mut v);
1318 Cursor::Array { set, i: 0 }
1319 }
1320 Kind::Union => {
1321 let (a, b) = (self.norm(data[0])?, self.norm(data[1])?);
1322 let mut v = self.elements(a)?;
1323 v.extend(self.elements(b)?);
1324 let set = self.set_from(&mut v);
1325 Cursor::Array { set, i: 0 }
1326 }
1327 Kind::Nat | Kind::Int | Kind::SeqSet => {
1328 return Err(Error::eval("attempted to enumerate an infinite set"));
1329 }
1330 Kind::IntFcn | Kind::Fcn | Kind::Lambda => {
1331 return Err(Error::eval("attempted to enumerate a function as a set"));
1332 }
1333 Kind::BigInt => {
1334 return Err(Error::eval(
1335 "attempted to enumerate a value that is not a set",
1336 ));
1337 }
1338 Kind::SetPred => {
1339 return Err(Error::internal(
1340 "a set predicate reached the heap's enumeration; the evaluator closes it",
1341 ));
1342 }
1343 })
1344 }
1345
1346 pub fn cardinality(&mut self, h: Handle) -> Result<u64, Error> {
1351 if !h.is_compound() {
1352 return Err(Error::eval("Cardinality of a value that is not a set"));
1353 }
1354 let v = self.view(h);
1355 if v.is_lazy() {
1356 return Err(Error::internal(
1357 "Cardinality of an unclosed lazy value; the evaluator closes it",
1358 ));
1359 }
1360 match v.kind {
1361 Kind::Set => Ok(v.data.len() as u64),
1362 #[allow(clippy::cast_sign_loss, reason = "checked non-negative")]
1363 Kind::Interval => {
1364 let hi = v.data[0].as_int().unwrap_or(v.lo - 1);
1365 Ok(if hi < v.lo { 0 } else { (hi - v.lo + 1) as u64 })
1366 }
1367 _ => {
1368 let m = self.norm(h)?;
1369 if m == h {
1370 return Err(Error::eval("Cardinality of an infinite set"));
1371 }
1372 self.cardinality(m)
1373 }
1374 }
1375 }
1376
1377 pub fn set_speculative(&mut self, enabled: bool) -> bool {
1386 std::mem::replace(&mut self.speculative, enabled)
1387 }
1388
1389 #[must_use]
1391 pub const fn is_speculative(&self) -> bool {
1392 self.speculative
1393 }
1394
1395 pub fn state_identity(&mut self, h: Handle) -> Result<Handle, Error> {
1400 if self.speculative {
1401 self.close_identity_local(h)
1402 } else {
1403 self.intern(h)
1404 }
1405 }
1406
1407 pub fn close_identity_local(&mut self, h: Handle) -> Result<Handle, Error> {
1416 let h = self.close_local(h, 0, &mut LocalClose::default())?;
1417 crate::compare::require_materialized(self, &[h])?;
1418 Ok(h)
1419 }
1420
1421 pub fn close_identity_row_local(&mut self, roots: &[Handle]) -> Result<Vec<Handle>, Error> {
1429 if std::mem::size_of_val(roots) > MAX_LOCAL_CLOSE_SCRATCH_BYTES {
1430 return Err(Error::unsupported(
1431 "candidate identity root-row workspace bound",
1432 ));
1433 }
1434 let mut out = Vec::new();
1435 out.try_reserve_exact(roots.len())
1436 .map_err(|_| Error::unsupported("candidate identity root-row allocation"))?;
1437 let mut close = LocalClose::default();
1438 for &root in roots {
1439 let root = self.close_local(root, 0, &mut close)?;
1440 crate::compare::require_materialized(self, &[root])?;
1441 out.push(root);
1442 }
1443 Ok(out)
1444 }
1445
1446 fn close_local(
1447 &mut self,
1448 source: Handle,
1449 depth: usize,
1450 close: &mut LocalClose,
1451 ) -> Result<Handle, Error> {
1452 let h = source;
1453 if !h.is_compound() {
1454 return Ok(h);
1455 }
1456 if let Some(&closed) = close.visited.get(&h) {
1457 return Ok(closed);
1458 }
1459 if depth >= 128 {
1460 return Err(Error::unsupported("candidate identity nesting exceeds 128"));
1461 }
1462 self.work_poll()?;
1463 if let Some(&closed) = close.visited.get(&h) {
1464 close.remember(source, closed)?;
1465 return Ok(closed);
1466 }
1467 let view = self.view(h);
1468 if view.is_lazy() {
1469 return Err(Error::internal("closing an unclosed lazy candidate value"));
1470 }
1471 if view.kind.is_symbolic() && self.is_finite(h) {
1472 let materialized = self.materialize(h)?;
1473 let closed = self.close_local(materialized, depth + 1, close)?;
1474 close.remember(source, closed)?;
1475 close.remember(h, closed)?;
1476 return Ok(closed);
1477 }
1478 if view.kind.is_symbolic() {
1479 return Err(Error::unsupported(
1480 "mathematical identity of a symbolic state value",
1481 ));
1482 }
1483 if view.kind == Kind::Fcn {
1484 crate::compare::require_materialized(self, &view.data[..view.data.len() / 2])?;
1487 }
1488 if h.is_persistent()
1490 && view.flags & flags::VIEW == 0
1491 && crate::compare::materialized(self, h, 0)?
1492 {
1493 return Ok(h);
1494 }
1495 let lo = if view.kind == Kind::Set { 0 } else { view.lo };
1496 let bytes = std::mem::size_of_val(view.data);
1497 if bytes > MAX_LOCAL_CLOSE_SCRATCH_BYTES.saturating_sub(close.scratch) {
1498 return Err(Error::unsupported(
1499 "candidate identity closure child workspace bound",
1500 ));
1501 }
1502 let mut children = Vec::new();
1503 children
1504 .try_reserve_exact(view.data.len())
1505 .map_err(|_| Error::unsupported("candidate identity closure child allocation"))?;
1506 let bytes = children.capacity() * size_of::<Handle>();
1507 if bytes > MAX_LOCAL_CLOSE_SCRATCH_BYTES.saturating_sub(close.scratch) {
1508 return Err(Error::unsupported(
1509 "candidate identity closure child workspace bound",
1510 ));
1511 }
1512 close.scratch += bytes;
1513 for chunk in view.data.chunks(64) {
1514 self.work_poll()?;
1515 children.extend_from_slice(chunk);
1516 }
1517 for child in &mut children {
1518 *child = self.close_local(*child, depth + 1, close)?;
1519 }
1520 let unchanged = self.view(h).data == children;
1521 let closed =
1522 if unchanged && self.view(h).flags & !flags::CONCRETE == 0 && self.view(h).lo == lo {
1523 h
1524 } else if unchanged && h.is_transient() {
1525 self.arena
1526 .project(h, 0, lo)
1527 .ok_or_else(|| Error::internal("candidate identity projection owner"))?
1528 } else {
1529 self.rebuild(h, &children)
1532 };
1533 close.scratch -= bytes;
1534 close.remember(source, closed)?;
1535 close.remember(h, closed)?;
1536 Ok(closed)
1537 }
1538
1539 pub fn intern(&mut self, h: Handle) -> Result<Handle, Error> {
1545 if crate::compare::materialized(self, h, 0)? {
1546 self.intern_materialized(h)
1547 } else {
1548 let h = self.close_identity_local(h)?;
1549 self.intern_materialized(h)
1550 }
1551 }
1552
1553 fn intern_materialized(&mut self, h: Handle) -> Result<Handle, Error> {
1554 match h.tag() {
1555 Tag::Transient => {}
1556 Tag::Persistent => {
1557 if h.is_lazy_persistent() {
1558 let v = self.view(h);
1559 if v.is_lazy() {
1560 return Err(Error::internal("interning an unclosed lazy value"));
1561 }
1562 if !v.kind.is_symbolic() {
1563 let (kind, lo, hash, sum) = (
1566 v.kind,
1567 if v.kind == Kind::Set { 0 } else { v.lo },
1568 v.hash,
1569 v.sum,
1570 );
1571 let mut data = v.data.to_vec();
1572 for d in &mut data {
1573 *d = self.intern_materialized(*d)?;
1574 }
1575 let concrete = self.concrete_identity(kind, &data);
1576 return Ok(self.store.intern(
1577 &mut self.cache,
1578 kind,
1579 concrete,
1580 lo,
1581 hash,
1582 sum,
1583 &data,
1584 ));
1585 }
1586 }
1587 let k = self.view(h).kind;
1588 if k.is_symbolic() && self.is_finite(h) {
1589 let m = self.materialize(h)?;
1590 return self.intern_materialized(m);
1591 }
1592 return Ok(h);
1593 }
1594 _ => return Ok(h),
1595 }
1596 let Some(idx) = self.arena.index(h) else {
1597 self.arena.mark_stale();
1598 return Ok(Handle::EMPTY);
1599 };
1600 let done = self.arena.interned[idx];
1601 if !done.is_empty() {
1602 return Ok(done);
1603 }
1604 let v = self.view(h);
1605 if v.is_lazy() {
1606 return Err(Error::internal(
1607 "interning an unclosed lazy value; the evaluator closes it first",
1608 ));
1609 }
1610 if v.kind.is_symbolic() && self.is_finite(h) {
1611 let m = self.materialize(h)?;
1612 let p = self.intern_materialized(m)?;
1613 self.arena.interned[idx] = p;
1614 return Ok(p);
1615 }
1616 let (kind, lo, hash, sum) = (
1617 v.kind,
1618 if v.kind == Kind::Set { 0 } else { v.lo },
1619 v.hash,
1620 v.sum,
1621 );
1622 let mut data = v.data.to_vec();
1623 for d in &mut data {
1624 if d.is_compound() {
1625 *d = self.intern_materialized(*d)?;
1626 }
1627 }
1628 let concrete = self.concrete_identity(kind, &data);
1629 let p = self
1630 .store
1631 .intern(&mut self.cache, kind, concrete, lo, hash, sum, &data);
1632 self.arena.interned[idx] = p;
1633 Ok(p)
1634 }
1635
1636 fn concrete_identity(&self, kind: Kind, data: &[Handle]) -> u8 {
1638 if matches!(kind, Kind::Set | Kind::IntFcn | Kind::Fcn) {
1639 self.concrete_bit(data)
1640 } else {
1641 0
1642 }
1643 }
1644
1645 pub fn intern_const(&mut self, h: Handle) -> Result<Handle, Error> {
1654 if !h.is_transient() {
1655 return Ok(h);
1656 }
1657 self.intern_structural(h)
1658 }
1659
1660 fn intern_structural(&mut self, h: Handle) -> Result<Handle, Error> {
1664 let v = self.view(h);
1665 let (kind, mut fl, lo, hash, sum) = (v.kind, v.flags, v.lo, v.hash, v.sum);
1666 let mut data = v.data.to_vec();
1667 for d in &mut data {
1668 *d = self.intern_const(*d)?;
1669 if d.is_compound() && self.view(*d).flags & flags::VIEW != 0 {
1670 fl |= flags::NESTED_VIEW;
1671 }
1672 }
1673 Ok(self
1674 .store
1675 .intern(&mut self.cache, kind, fl, lo, hash, sum, &data))
1676 }
1677
1678 pub fn intern_exact(&mut self, h: Handle) -> Result<Handle, Error> {
1689 if !h.is_transient() {
1690 return Ok(h);
1691 }
1692 let v = self.view(h);
1693 if v.is_lazy() {
1694 return Err(Error::internal("interning an unclosed lazy value"));
1695 }
1696 let (kind, mut fl, lo, hash, sum) = (v.kind, v.flags, v.lo, v.hash, v.sum);
1697 let mut data = v.data.to_vec();
1698 for d in &mut data {
1699 if d.is_transient() {
1700 *d = self.intern_exact(*d)?;
1701 }
1702 if d.is_compound() && self.view(*d).flags & flags::VIEW != 0 {
1703 fl |= flags::NESTED_VIEW;
1704 }
1705 }
1706 Ok(self
1707 .store
1708 .intern(&mut self.cache, kind, fl, lo, hash, sum, &data))
1709 }
1710
1711 pub fn intern_view(&mut self, h: Handle) -> Result<(Handle, Handle), Error> {
1721 let view = if !h.is_compound() {
1722 Handle::EMPTY
1723 } else if self.view(h).kind.is_symbolic() {
1724 self.intern_const(h)?
1725 } else if self.view(h).flags & flags::VIEW != 0 {
1726 if h.is_transient() {
1727 self.intern_structural(h)?
1728 } else {
1729 h
1730 }
1731 } else {
1732 Handle::EMPTY
1733 };
1734 Ok((self.intern(h)?, view))
1735 }
1736
1737 pub(crate) fn set_work_control(&mut self, control: Option<Arc<dyn crate::eval::WorkControl>>) {
1738 self.work_control = control;
1739 }
1740
1741 pub(crate) fn mark_work_interrupted(&self) {
1742 self.work_interrupted.set(true);
1743 }
1744
1745 #[must_use]
1747 pub fn work_interrupted(&self) -> bool {
1748 self.work_interrupted.get()
1749 }
1750
1751 pub(crate) fn work_poll(&self) -> Result<(), Error> {
1752 let steps = self.work_steps.get();
1753 self.work_steps.set(steps.wrapping_add(1));
1754 if steps.trailing_zeros() >= 6 && self.work_control.as_ref().is_some_and(|c| !c.proceed()) {
1755 self.mark_work_interrupted();
1756 return Err(Error::stop());
1757 }
1758 Ok(())
1759 }
1760
1761 pub fn string(&self, text: &str) -> Result<Handle, Error> {
1767 if self.strings == StringMode::ExistingOnly {
1768 return self
1769 .store
1770 .strings()
1771 .lookup(text)
1772 .map(Handle::string)
1773 .ok_or_else(|| {
1774 Error::unsupported(
1775 "a string this optional evaluation would add to the shared string table",
1776 )
1777 });
1778 }
1779 Ok(Handle::string(self.store.strings().intern(text)?))
1780 }
1781
1782 pub fn set_existing_strings_only(&mut self, enabled: bool) -> bool {
1794 let mode = if enabled {
1795 StringMode::ExistingOnly
1796 } else {
1797 StringMode::Intern
1798 };
1799 std::mem::replace(&mut self.strings, mode) == StringMode::ExistingOnly
1800 }
1801}
1802
1803#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1805enum StringMode {
1806 Intern,
1808 ExistingOnly,
1810}
1811
1812pub(crate) fn fcn_key(v: &View<'_>, i: usize) -> Handle {
1814 match v.kind {
1815 #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
1816 Kind::IntFcn => Handle::int(v.lo + i as i64).unwrap_or(Handle::EMPTY),
1817 _ => v.data[i],
1818 }
1819}
1820
1821fn contiguous_ints(keys: &[Handle]) -> Option<i64> {
1823 let Some(first) = keys.first() else {
1825 return Some(1);
1826 };
1827 let lo = first.as_int()?;
1828 for (i, k) in keys.iter().enumerate() {
1829 #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
1830 if k.as_int()? != lo + i as i64 {
1831 return None;
1832 }
1833 }
1834 Some(lo)
1835}
1836
1837#[derive(Clone, Debug)]
1839pub enum Shape {
1840 Tuple,
1842 Fcn(Vec<Handle>),
1844}
1845
1846#[derive(Clone, Debug)]
1848pub enum Cursor {
1849 Array {
1851 set: Handle,
1853 i: usize,
1855 },
1856 Range {
1858 cur: i64,
1860 hi: i64,
1862 },
1863 Odometer {
1866 shape: Shape,
1868 comps: Vec<Vec<Handle>>,
1870 idx: Vec<usize>,
1872 done: bool,
1874 },
1875 Subset {
1877 elems: Vec<Handle>,
1879 k: usize,
1881 combo: Vec<usize>,
1883 started: bool,
1885 },
1886}
1887
1888impl Cursor {
1889 fn odometer(shape: Shape, comps: Vec<Vec<Handle>>) -> Self {
1890 let done = comps.iter().any(Vec::is_empty);
1891 let n = comps.len();
1892 Self::Odometer {
1893 shape,
1894 comps,
1895 idx: vec![0; n],
1896 done,
1897 }
1898 }
1899
1900 pub fn next(&mut self, heap: &mut Heap) -> Result<Option<Handle>, Error> {
1905 match self {
1906 Self::Array { set, i } => {
1907 let v = heap.view(*set);
1908 let r = v.data.get(*i).copied();
1909 *i += 1;
1910 Ok(r)
1911 }
1912 Self::Range { cur, hi } => {
1913 if *cur > *hi {
1914 return Ok(None);
1915 }
1916 let r = Handle::int(*cur);
1917 *cur += 1;
1918 r.map(Some)
1919 .ok_or_else(|| Error::unsupported("integer outside the 61-bit range"))
1920 }
1921 Self::Odometer {
1922 shape,
1923 comps,
1924 idx,
1925 done,
1926 } => {
1927 if *done {
1928 return Ok(None);
1929 }
1930 let vals: Vec<Handle> = idx.iter().zip(comps.iter()).map(|(&i, c)| c[i]).collect();
1931 let out = match shape {
1932 Shape::Tuple => heap.tuple(&vals),
1933 Shape::Fcn(keys) => heap.fcn_sorted(keys, &vals),
1934 };
1935 let mut p = idx.len();
1937 loop {
1938 if p == 0 {
1939 *done = true;
1940 break;
1941 }
1942 p -= 1;
1943 idx[p] += 1;
1944 if idx[p] < comps[p].len() {
1945 break;
1946 }
1947 idx[p] = 0;
1948 }
1949 Ok(Some(out))
1950 }
1951 Self::Subset {
1952 elems,
1953 k,
1954 combo,
1955 started,
1956 } => {
1957 let n = elems.len();
1958 if *started {
1959 let mut i = *k;
1961 let mut advanced = false;
1962 while i > 0 {
1963 i -= 1;
1964 if combo[i] < n - *k + i {
1965 combo[i] += 1;
1966 for j in i + 1..*k {
1967 combo[j] = combo[j - 1] + 1;
1968 }
1969 advanced = true;
1970 break;
1971 }
1972 }
1973 if !advanced {
1974 *k += 1;
1975 if *k > n {
1976 return Ok(None);
1977 }
1978 *combo = (0..*k).collect();
1979 }
1980 } else {
1981 *started = true;
1982 *combo = Vec::new();
1983 }
1984 let mut sub: Vec<Handle> = combo.iter().map(|&i| elems[i]).collect();
1985 Ok(Some(heap.set_from(&mut sub)))
1986 }
1987 }
1988 }
1989}
1990
1991#[cfg(test)]
1992impl Heap {
1993 pub(crate) fn unmarked_copy(&mut self, t: Handle) -> Handle {
1996 let v = self.view(t);
1997 let (kind, fl, lo, hash, sum) = (v.kind, v.flags & !flags::CONCRETE, v.lo, v.hash, v.sum);
1998 let data = v.data.to_vec();
1999 self.store
2000 .intern(&mut self.cache, kind, fl, lo, hash, sum, &data)
2001 }
2002}
2003
2004#[cfg(test)]
2005#[allow(clippy::many_single_char_names, reason = "short value names in tests")]
2006mod tests {
2007 use super::*;
2008
2009 fn int(v: i64) -> Handle {
2010 Handle::int(v).unwrap_or(Handle::EMPTY)
2011 }
2012
2013 fn heap(full: bool) -> Heap {
2014 Heap::new(Arc::new(Store::default()), false, full)
2015 }
2016
2017 #[test]
2018 fn mathematical_state_identity_refuses_nested_symbolic_values() {
2019 let mut h = heap(false);
2020 let empty = h.empty_set();
2021 let naturals = h.symbolic(Kind::Nat, 0, &[]);
2022 let product = h.symbolic(Kind::Product, 0, &[empty, naturals]);
2023 let range = h.interval(1, 1);
2024 let sequence = h.symbolic(Kind::SeqSet, 0, &[range]);
2025 for symbolic in [sequence, product] {
2026 let tuple = h.tuple(&[symbolic]);
2027 let function_key = h.fcn_sorted(&[symbolic], &[int(1)]);
2028 let function_value = h.fcn_sorted(&[int(0)], &[symbolic]);
2029 let singleton = h.set_sorted(&[tuple]);
2030 for value in [symbolic, tuple, function_key, function_value, singleton] {
2031 let before = h.store().stats().nodes;
2032 assert!(
2033 matches!(h.intern(value), Err(error) if error.kind() == crate::ErrorKind::Unsupported)
2034 );
2035 assert!(
2036 matches!(h.close_identity_local(value), Err(error) if error.kind() == crate::ErrorKind::Unsupported)
2037 );
2038 assert!(
2039 matches!(h.close_identity_row_local(&[value]), Err(error) if error.kind() == crate::ErrorKind::Unsupported)
2040 );
2041 assert_eq!(h.store().stats().nodes, before);
2042 }
2043 }
2044 }
2045
2046 #[test]
2047 fn product_materialization_checks_empty_axes_before_normalization() -> Result<(), Error> {
2048 for semantics in [crate::Semantics::default(), crate::Semantics::tlc()] {
2049 let mut h = Heap::new(
2050 Arc::new(Store::with_semantics(true, semantics)),
2051 false,
2052 false,
2053 );
2054 let empty_interval = h.interval(3, 2);
2055 let mixed = h.set_from(&mut vec![int(0), Handle::TRUE]);
2056 let product = h.symbolic(Kind::Product, 0, &[empty_interval, mixed, int(0)]);
2057 let nested = h.symbolic(Kind::Product, 0, &[product, mixed]);
2058 for value in [product, nested] {
2059 let materialized = h.materialize(value)?;
2060 assert_eq!(h.view(materialized).kind, Kind::Set);
2061 assert_eq!(h.view(materialized).data, []);
2062 }
2063 let earlier_scalar = h.symbolic(Kind::Product, 0, &[int(0), empty_interval]);
2065 assert!(h.materialize(earlier_scalar).is_err());
2066 let one = h.set_from(&mut vec![int(0)]);
2067 let demanded = h.symbolic(Kind::Product, 0, &[one, mixed]);
2068 let materialized = h.materialize(demanded)?;
2069 assert_eq!(h.view(materialized).data.len(), 2);
2070 assert!(!h.poisoned());
2071 }
2072 Ok(())
2073 }
2074
2075 #[test]
2078 fn string_comparison_follows_the_table_as_it_grows() {
2079 let h = heap(false);
2080 let t = h.store().strings();
2081 let id = |s: &str| t.intern(s).unwrap_or(u32::MAX);
2082 let (b, a) = (id("b"), id("a"));
2083 assert_eq!(h.str_cmp(b, a), Ordering::Greater);
2084 let (c, aa) = (id("c"), id("aa"));
2085 for (x, y) in [(a, b), (b, c), (aa, a), (aa, b), (c, aa), (c, c)] {
2086 assert_eq!(h.str_cmp(x, y), t.cmp(x, y), "{x} {y}");
2087 }
2088 }
2089
2090 #[test]
2093 fn string_comparison_covers_strings_past_the_ranks() {
2094 let h = heap(false);
2095 let t = h.store().strings();
2096 let id = |s: &str| t.intern(s).unwrap_or(u32::MAX);
2097 let ranked: Vec<u32> = (0..1500).map(|n| id(&format!("k{n:04}"))).collect();
2098 assert_eq!(h.str_cmp(ranked[1], ranked[0]), Ordering::Greater);
2099 let late = [id("k0500x"), id("a"), id("zz")];
2100 assert!(t.ranks().len() < t.len(), "the late strings stay unranked");
2101 for &x in late.iter().chain(&ranked[495..505]) {
2102 for &y in late.iter().chain(&ranked[495..505]) {
2103 assert_eq!(h.str_cmp(x, y), t.cmp(x, y), "{x} {y}");
2104 }
2105 }
2106 }
2107
2108 #[test]
2109 fn model_types_follow_utf16_names_across_append_and_reset() {
2110 use crate::strings::StringOrder;
2111
2112 for order in [StringOrder::Text, StringOrder::Token] {
2113 let mut h = Heap::new(
2114 Arc::new(Store::with_string_order(true, order)),
2115 false,
2116 false,
2117 );
2118 for names in [
2119 ["", "a", "A_", "A_x", "_x", "n1", "รฉ_x", "๐_x"],
2120 ["รฉ_๐", "๐_x", "A_รฉ", "A_๐", "__x", "_", "๐", "x_y"],
2121 ] {
2122 for name in names {
2123 let id = h.store.strings().intern(name).unwrap_or(u32::MAX);
2124 let units: Vec<_> = name.encode_utf16().collect();
2125 let expected = if units.len() > 2 && units[1] == u16::from(b'_') {
2126 Some(units[0])
2127 } else {
2128 None
2129 };
2130 for _ in 0..2 {
2131 assert_eq!(h.model_type(id), expected, "{order:?} {name:?}");
2132 assert_eq!(crate::compare::mv_type(&h, Handle::model(id)), expected);
2133 h.reset();
2134 }
2135 }
2136 }
2137 assert_eq!(h.model_type(u32::MAX), None);
2138 assert_eq!(crate::compare::mv_type(&h, Handle::TRUE), None);
2139 h.store.strings().seal();
2140 assert_eq!(h.model_type(3), Some(u16::from(b'A')));
2141 }
2142 }
2143
2144 #[test]
2145 fn incremental_except_hash_equals_the_full_hash() {
2146 for full in [false, true] {
2147 let mut h = heap(full);
2148 let f = h.int_fcn(1, &[int(1), int(2), int(3)]);
2149 let inner = h.set_from(&mut vec![int(7), int(5)]);
2150 let g = h.fcn_with(f, 1, inner);
2151 let direct = h.int_fcn(1, &[int(1), inner, int(3)]);
2152 assert!(h.eq(g, direct));
2153 assert_eq!(h.hash(g), h.hash(direct));
2154 assert_eq!(h.hash(g), h.deep_hash(direct));
2155 let (a, b) = (
2157 h.string("a").unwrap_or(Handle::EMPTY),
2158 h.string("b").unwrap_or(Handle::EMPTY),
2159 );
2160 let r = h.fcn_from_pairs(&mut [(b, int(1)), (a, int(2))]);
2161 let r2 = h.fcn_with(r, 0, int(9));
2162 let r3 = h.fcn_with(r2, 0, int(2));
2163 assert_eq!(h.hash(r3), h.deep_hash(r));
2164 assert!(h.eq(r3, r));
2165 }
2166 }
2167
2168 #[test]
2169 fn interning_is_hash_consed_and_preserves_hashes() {
2170 let mut h = heap(false);
2171 let a = h.set_from(&mut vec![int(3), int(1), int(2)]);
2172 let b = h.interval(1, 3);
2173 let b = h.norm(b).unwrap_or(Handle::EMPTY);
2174 assert!(h.eq(a, b));
2175 let pa = h.intern(a).unwrap_or(Handle::EMPTY);
2176 let pb = h.intern(b).unwrap_or(Handle::EMPTY);
2177 assert_eq!(pa, pb);
2178 assert_eq!(h.hash(pa), h.hash(a));
2179 let t = h.tuple(&[a, int(4)]);
2180 let pt = h.intern(t).unwrap_or(Handle::EMPTY);
2181 h.reset();
2182 let v = h.view(pt);
2184 assert_eq!(v.data.first().copied(), Some(pa));
2185 assert!(!h.poisoned());
2186 let st = h.store().stats();
2187 assert!(st.hits >= 1, "{st:?}");
2188 }
2189
2190 #[test]
2191 fn stale_transient_handles_poison_the_heap() {
2192 let mut h = heap(false);
2193 let a = h.set_from(&mut vec![int(1)]);
2194 h.reset();
2195 let _ = h.view(a);
2196 assert!(h.poisoned());
2197 }
2198
2199 #[test]
2200 fn rollback_frees_candidates_and_stale_reads_poison() {
2201 let mut h = heap(false);
2202 let kept = h.set_from(&mut vec![int(1)]);
2203 for i in 0..1000 {
2204 let m = h.mark();
2205 let c = h.tuple(&[int(i), kept]);
2206 if i % 10 == 0 {
2207 continue;
2208 }
2209 assert!(h.eq(h.view(c).data[1], kept));
2210 h.rollback(m);
2211 }
2212 assert_eq!(h.arena().len(), 101);
2214 assert!(!h.poisoned());
2215 let m = h.mark();
2216 let gone = h.tuple(&[int(7)]);
2217 h.rollback(m);
2218 let _ = h.tuple(&[int(8)]);
2219 let _ = h.view(gone);
2220 assert!(h.poisoned(), "a handle freed by rollback must not resolve");
2221 }
2222
2223 #[test]
2224 fn lazy_values_carry_their_closure_and_propagate() {
2225 let mut h = heap(false);
2226 let dom = h.interval(1, 3);
2227 let f = h.lambda(7, dom, &[int(5)]);
2228 assert!(h.is_lazy(f));
2229 let c = h
2230 .closure(f)
2231 .map(|c| (c.kind, c.id, c.domain, c.captures.to_vec()));
2232 assert_eq!(c, Some((Kind::Lambda, 7, dom, vec![int(5)])));
2233 let a = h.string("a").unwrap_or(Handle::EMPTY);
2235 let r = h.fcn_sorted(&[a], &[f]);
2236 assert!(h.is_lazy(r));
2237 let closed = h.fcn_sorted(&[a], &[int(1)]);
2238 assert!(!h.is_lazy(closed));
2239 assert!(!h.poisoned());
2240 assert!(h.intern(r).is_err());
2242 assert!(!h.poisoned());
2243 let r2 = h.fcn_with(r, 0, int(1));
2245 assert!(!h.is_lazy(r2));
2246 assert!(h.eq(r2, closed));
2247 let p = h.set_pred(2, dom, &[]);
2248 assert!(h.is_lazy(p));
2249 assert_eq!(h.norm(p).ok(), Some(p), "only the evaluator enumerates it");
2250 assert!(h.cursor(p).is_err());
2251 assert!(!h.poisoned());
2252 }
2253
2254 #[test]
2255 fn lazy_values_in_closed_positions_poison() {
2256 for op in 0..3 {
2257 let mut h = heap(false);
2258 let dom = h.interval(1, 3);
2259 let f = h.lambda(0, dom, &[]);
2260 match op {
2261 0 => {
2262 let _ = h.hash(f);
2263 }
2264 1 => {
2265 let _ = h.set_sorted(&[f]);
2266 }
2267 _ => {
2268 let g = h.lambda(1, dom, &[]);
2269 let _ = h.eq(f, g);
2270 }
2271 }
2272 assert!(h.poisoned(), "op {op}");
2273 }
2274 }
2275
2276 #[test]
2277 fn rebuild_closes_a_value_bottom_up() {
2278 let mut h = heap(false);
2279 let dom = h.interval(1, 2);
2280 let f = h.lambda(0, dom, &[]);
2281 let t = h.tuple(&[int(9), f]);
2282 let m = h.int_fcn(1, &[int(10), int(20)]);
2284 let data = h.view(t).data.to_vec();
2285 let closed = h.rebuild(t, &[data[0], m]);
2286 assert!(!h.is_lazy(closed));
2287 let direct = h.tuple(&[int(9), m]);
2288 assert!(h.eq(closed, direct));
2289 assert_eq!(h.hash(closed), h.hash(direct));
2290 assert!(h.intern(closed).is_ok());
2291 let s = h.set_from(&mut vec![int(1), int(2)]);
2293 let s2 = h.rebuild(s, &[int(5), int(3)]);
2294 assert_eq!(h.view(s2).data, &[int(3), int(5)]);
2295 assert!(!h.poisoned());
2296 }
2297
2298 #[test]
2299 fn lazy_constants_stay_lazy_and_are_never_compared_by_handle() {
2300 let mut h = heap(false);
2301 let nat = h.symbolic(Kind::Nat, 0, &[]);
2302 let f = h.lambda(3, nat, &[]);
2303 let p = h.intern_const(f).unwrap_or(Handle::EMPTY);
2304 assert!(p.is_lazy_persistent());
2305 h.reset();
2306 assert_eq!(h.closure(p).map(|c| c.id), Some(3));
2307 assert!(h.intern(p).is_err());
2308 let nat = h.symbolic(Kind::Nat, 0, &[]);
2309 let g = h.lambda(4, nat, &[]);
2310 let q = h.intern_const(g).unwrap_or(Handle::EMPTY);
2311 assert!(!h.poisoned());
2312 let _ = h.eq(p, q);
2313 assert!(h.poisoned(), "two lazy constants cannot be compared");
2314 }
2315
2316 #[test]
2317 fn nested_function_views_never_claim_canonical_identity() -> Result<(), Error> {
2318 for hashcons in [true, false] {
2319 for exact in [false, true] {
2320 let store = Arc::new(Store::new(hashcons));
2321 let mut h = Heap::new(store, false, false);
2322 let a = h.string("a")?;
2323 let record = h.record(&[a], &[int(0)]);
2324 let general = h.fcn_sorted(&[a], &[int(0)]);
2325 let left = h.fcn_sorted(&[int(1)], &[record]);
2326 let right = h.fcn_sorted(&[int(1)], &[general]);
2327 let left = h.fcn_sorted(&[int(1)], &[left]);
2328 let right = h.fcn_sorted(&[int(1)], &[right]);
2329 let (left, right) = if exact {
2330 (h.intern_exact(left)?, h.intern_exact(right)?)
2331 } else {
2332 (h.intern_const(left)?, h.intern_const(right)?)
2333 };
2334 h.reset();
2335 assert!(
2336 h.eq(left, right),
2337 "equal values cannot be rejected by the persistent identity fast path"
2338 );
2339 assert!(
2340 left.is_lazy_persistent(),
2341 "nested representation is structural"
2342 );
2343 assert_eq!(
2344 h.view(left).flags & flags::TUPLE,
2345 0,
2346 "the parent is still a general function"
2347 );
2348 assert_ne!(left, right, "representations remain distinct");
2349 assert_eq!(h.hash(left), h.hash(right));
2350 let a = h.intern(left)?;
2351 let b = h.intern(right)?;
2352 assert!(!a.is_lazy_persistent());
2353 assert!(h.eq(a, b));
2354 if hashcons {
2355 assert_eq!(a, b, "canonical identity is unchanged");
2356 }
2357 }
2358 }
2359 Ok(())
2360 }
2361
2362 #[test]
2363 fn unions_stay_symbolic_until_normalized() {
2364 let mut h = heap(false);
2365 let a = h.interval(1, 3);
2366 let b = h.set_from(&mut vec![int(0), int(2), int(7)]);
2367 let u = h.union(a, b);
2368 assert_eq!(h.kind(u), Some(Kind::Union));
2369 assert!(h.is_finite(u));
2370 assert_eq!(h.cardinality(u).ok(), Some(5));
2371 let n = h.norm(u).unwrap_or(Handle::EMPTY);
2372 assert_eq!(h.view(n).data, &[int(0), int(1), int(2), int(3), int(7)]);
2373 let nat = h.symbolic(Kind::Nat, 0, &[]);
2374 let inf = h.union(nat, b);
2375 assert!(!h.is_finite(inf));
2376 assert_eq!(h.norm(inf).ok(), Some(inf));
2377 assert!(!h.poisoned());
2378 }
2379
2380 #[test]
2381 fn intern_view_keeps_the_representation_beside_the_identity() {
2382 let mut h = heap(false);
2383 let iv = h.interval(1, 3);
2384 let (id, view) = h.intern_view(iv).unwrap_or((Handle::EMPTY, Handle::EMPTY));
2385 assert_eq!(h.kind(id), Some(Kind::Set));
2386 assert_eq!(h.kind(view), Some(Kind::Interval));
2387 let e = h.set_from(&mut vec![int(3), int(2), int(1)]);
2388 let (id2, none) = h.intern_view(e).unwrap_or((Handle::EMPTY, Handle::TRUE));
2389 assert_eq!(id, id2, "identity is extensional");
2390 assert!(none.is_empty());
2391 assert!(!h.poisoned());
2392 }
2393
2394 #[test]
2395 fn sets_of_strings_follow_the_store_order() {
2396 use crate::strings::StringOrder;
2397 for (order, want) in [
2398 (StringOrder::Text, ["a", "b"]),
2399 (StringOrder::Token, ["b", "a"]),
2400 ] {
2401 let store = Arc::new(Store::with_string_order(true, order));
2402 assert!(store.strings().preload(["b", "a"]).is_ok());
2403 let mut h = Heap::new(store, false, false);
2404 let (a, b) = (
2405 h.string("a").unwrap_or(Handle::EMPTY),
2406 h.string("b").unwrap_or(Handle::EMPTY),
2407 );
2408 let set = h.set_from(&mut vec![a, b]);
2409 let got: Vec<String> = h
2410 .view(set)
2411 .data
2412 .iter()
2413 .filter_map(|e| e.as_str_id())
2414 .filter_map(|id| h.store().strings().text(id))
2415 .map(|t| t.to_string())
2416 .collect();
2417 assert_eq!(got, want, "{order:?}");
2418 }
2419 }
2420
2421 #[test]
2422 fn an_exact_copy_keeps_every_view_bit_and_symbolic_set() {
2423 let mut h = heap(false);
2424 let (a, b) = (
2425 h.string("a").unwrap_or(Handle::EMPTY),
2426 h.string("b").unwrap_or(Handle::EMPTY),
2427 );
2428 let span = h.interval(1, 3);
2429 let inner = h.record(&[a], &[int(1)]);
2430 let lit = h.record(&[a, b], &[inner, span]);
2431 let exact = h.intern_exact(lit).unwrap_or(Handle::EMPTY);
2432 assert!(exact.is_persistent());
2433 let v = h.view(exact);
2434 assert!(v.is_record_literal());
2435 let (first, second) = (v.values()[0], v.values()[1]);
2436 assert!(h.view(first).is_record_literal(), "nested bits are kept");
2437 assert_eq!(h.view(second).kind, Kind::Interval, "symbolic sets stay");
2438 assert!(h.eq(exact, lit));
2439 let inner2 = h.record(&[a], &[int(1)]);
2441 let span2 = h.interval(1, 3);
2442 let lit2 = h.record(&[a, b], &[inner2, span2]);
2443 assert_eq!(h.intern_exact(lit2).ok(), Some(exact));
2444 let fcn = h.fcn_sorted(&[a, b], &[inner2, span2]);
2445 assert_ne!(h.intern_exact(fcn).ok(), Some(exact));
2446 }
2447
2448 #[test]
2453 fn a_closed_view_is_a_function_key() {
2454 let mut h = heap(false);
2455 let a = h.string("a").unwrap_or(Handle::EMPTY);
2456 let rec = h.record(&[a], &[int(1)]);
2457 let seq = h.tuple_literal(&[rec]);
2458 let key = h.intern_exact(seq).unwrap_or(Handle::EMPTY);
2459 assert_ne!(h.view(key).flags & flags::NESTED_VIEW, 0);
2460 let f = h.fcn_sorted(&[key, a], &[int(1), int(2)]);
2461 assert!(!h.poisoned());
2462 assert_ne!(h.view(f).flags & flags::NESTED_VIEW, 0, "the view is kept");
2463 let plain = h.tuple(&[rec]);
2464 let g = h.fcn_sorted(&[plain, a], &[int(1), int(2)]);
2465 assert!(h.eq(f, g));
2466 let dom = h.interval(1, 2);
2467 let lazy = h.set_pred(0, dom, &[]);
2468 let _ = h.fcn_sorted(&[lazy], &[int(1)]);
2469 assert!(h.poisoned(), "a lazy key is still a misuse");
2470 }
2471
2472 #[test]
2473 fn a_record_literal_bit_is_a_view_bit() {
2474 let mut h = heap(false);
2475 let (a, b) = (
2476 h.string("a").unwrap_or(Handle::EMPTY),
2477 h.string("b").unwrap_or(Handle::EMPTY),
2478 );
2479 let (keys, vals) = ([a, b], [int(1), int(2)]);
2480 let lit = h.record(&keys, &vals);
2481 let fcn = h.fcn_sorted(&keys, &vals);
2482 assert!(h.view(lit).is_record_literal());
2483 assert!(!h.view(fcn).is_record_literal());
2484 assert!(h.eq(lit, fcn), "equality ignores the bit");
2485 assert_eq!(h.hash(lit), h.hash(fcn));
2486 assert_eq!(h.cmp(lit, fcn), Ordering::Equal);
2487 let changed = h.fcn_with(lit, 0, int(9));
2488 assert!(h.view(changed).is_record_literal(), "EXCEPT keeps it");
2489
2490 let id_lit = h.intern(lit).unwrap_or(Handle::EMPTY);
2492 let id_fcn = h.intern(fcn).unwrap_or(Handle::TRUE);
2493 assert_eq!(id_lit, id_fcn);
2494 assert!(!h.view(id_lit).is_record_literal());
2495 let lit2 = h.record(&keys, &vals);
2496 let (id, view) = h
2497 .intern_view(lit2)
2498 .unwrap_or((Handle::EMPTY, Handle::EMPTY));
2499 assert_eq!(id, id_fcn);
2500 assert!(h.view(view).is_record_literal());
2501 assert_ne!(view, id, "the view is interned apart from the identity");
2502 assert!(h.eq(view, id));
2503 assert_eq!(h.intern(view).ok(), Some(id));
2504 let again = h.record(&keys, &vals);
2505 let (_, view2) = h
2506 .intern_view(again)
2507 .unwrap_or((Handle::EMPTY, Handle::EMPTY));
2508 assert_eq!(view2, view, "views are hash-consed among themselves");
2509 let k = h.record(&keys, &vals);
2510 let constant = h.intern_const(k).unwrap_or(Handle::EMPTY);
2511 assert!(h.view(constant).is_record_literal());
2512 assert_eq!(
2513 h.intern(constant).ok(),
2514 Some(id),
2515 "identity remains canonical"
2516 );
2517 let set = h.set_from(&mut vec![view, id]);
2519 assert_eq!(h.view(set).data.len(), 1);
2520 let t = h.tuple_literal(&[int(1), int(2)]);
2522 let plain = h.tuple(&[int(1), int(2)]);
2523 assert!(h.view(t).is_tuple_literal() && !h.view(plain).is_tuple_literal());
2524 assert!(h.eq(t, plain));
2525 let t2 = h.fcn_with(t, 1, int(5));
2526 assert!(h.view(t2).is_tuple_literal());
2527 let (tid, tview) = h.intern_view(t).unwrap_or((Handle::EMPTY, Handle::EMPTY));
2528 assert_eq!(h.intern(plain).ok(), Some(tid));
2529 assert!(h.view(tview).is_tuple_literal() && !h.view(tid).is_tuple_literal());
2530 assert!(!h.poisoned());
2531 }
2532
2533 #[test]
2534 fn a_set_enumeration_keeps_tlc_construction_order_as_a_view() {
2535 let mut h = heap(false);
2536 let e = h.set_enum(&[int(3), int(1), int(3), int(2)]);
2537 let v = h.view(e);
2538 assert_eq!(v.kind, Kind::SetEnum);
2539 assert!(!v.is_norm());
2540 assert_eq!(v.data, &[int(3), int(1), int(3), int(2)]);
2541 assert!(h.is_finite(e));
2542 assert_eq!(h.cardinality(e).ok(), Some(3));
2543 let n = h.norm(e).unwrap_or(Handle::EMPTY);
2544 assert!(h.view(n).is_norm());
2545 assert_eq!(h.view(n).data, &[int(1), int(2), int(3)]);
2546 let plain = h.set_from(&mut vec![int(1), int(2), int(3)]);
2547 let id_plain = h.intern(plain).unwrap_or(Handle::EMPTY);
2548 let (id, view) = h.intern_view(e).unwrap_or((Handle::EMPTY, Handle::EMPTY));
2549 assert_eq!(id, id_plain);
2550 assert_eq!(h.kind(view), Some(Kind::SetEnum));
2551 assert!(!h.view(view).is_norm());
2552 assert_eq!(h.intern(view).ok(), Some(id));
2553 assert!(!h.poisoned());
2554 }
2555
2556 #[test]
2557 fn subset_cursor_is_in_canonical_order() {
2558 let mut h = heap(false);
2559 let base = h.set_from(&mut vec![int(1), int(2)]);
2560 let s = h.symbolic(Kind::Subset, 0, &[base]);
2561 let elems = h.elements(s).unwrap_or_default();
2562 assert_eq!(elems.len(), 4);
2563 for w in elems.windows(2) {
2564 assert_eq!(h.cmp(w[0], w[1]), Ordering::Less);
2565 }
2566 }
2567
2568 #[test]
2569 fn constant_domains_are_enumerated_once_into_equal_persistent_elements() {
2570 let mut h = heap(false);
2571 let ints = h.interval(1, 2);
2572 let names = h.set_from(&mut vec![int(7), int(8)]);
2573 let product = h.symbolic(Kind::Product, 0, &[ints, names]);
2574 let subset = h.symbolic(Kind::Subset, 0, &[product]);
2575 let domain = h.intern_exact(subset).unwrap_or(Handle::EMPTY);
2576 assert!(domain.is_persistent());
2577 let fresh = h.norm(domain).unwrap_or(Handle::EMPTY);
2578 let kept = h.enumerate_constant(domain).unwrap_or(Handle::EMPTY);
2579 assert!(kept.is_persistent());
2580 assert_eq!(h.enumerate_constant(domain).ok(), Some(kept));
2581 let fresh_elems = h.elements(fresh).unwrap_or_default();
2582 let kept_elems = h.elements(kept).unwrap_or_default();
2583 assert_eq!(kept_elems.len(), 16);
2584 assert_eq!(fresh_elems.len(), kept_elems.len());
2585 for (&a, &b) in fresh_elems.iter().zip(&kept_elems) {
2586 assert!(b.is_persistent());
2587 assert_eq!(h.cmp(a, b), Ordering::Equal);
2588 assert_eq!(h.intern(a).ok(), Some(b));
2589 }
2590 let big = h.interval(1, 17);
2592 let big = h.symbolic(Kind::Subset, 0, &[big]);
2593 let big = h.intern_exact(big).unwrap_or(Handle::EMPTY);
2594 for _ in 0..2 {
2595 let m = h.enumerate_constant(big).unwrap_or(Handle::EMPTY);
2596 assert!(m.is_transient());
2597 assert_eq!(h.view(m).data.len(), 1 << 17);
2598 }
2599 let fresh = h.norm(domain).unwrap_or(Handle::EMPTY);
2602 assert!(h.within_transient_words(fresh, 1 << 12));
2603 assert!(!h.within_transient_words(fresh, 16));
2605 assert!(h.within_transient_words(kept, 0));
2606 let set = h.set_from(&mut vec![int(1)]);
2608 assert_eq!(h.enumerate_constant(set).ok(), Some(set));
2609 assert!(!h.poisoned());
2610 }
2611
2612 fn unmarked(h: &mut Heap, t: Handle) -> Handle {
2613 h.unmarked_copy(t)
2614 }
2615
2616 #[test]
2617 fn concrete_proofs_trust_the_bit_and_the_bounded_walk_decides_without_it() {
2618 let mut h = heap(false);
2619 let name = h.string("abcd").unwrap_or(Handle::EMPTY);
2620 let model = Handle::model(h.store().strings().intern("m").unwrap_or(0));
2621 for scalar in [Handle::TRUE, int(-3), name, model] {
2622 assert!(h.proved_concrete(scalar));
2623 assert!(h.materialized_within(&[scalar], 1, None));
2624 }
2625 let unknown = Handle::string(1 << 20);
2626 for refused in [Handle::EMPTY, unknown, Handle::model(1 << 20)] {
2627 assert!(!h.proved_concrete(refused));
2628 assert!(!h.materialized_within(&[refused], 8, None));
2629 }
2630 let tuple = h.tuple_literal(&[name, model]);
2632 let set = h.set_from(&mut vec![tuple, int(1), model]);
2633 assert!(!h.proved_concrete(set), "a transient is never proved");
2634 assert!(!h.materialized_within(&[set], 64, None));
2635 let marked = h.intern_exact(set).unwrap_or(Handle::EMPTY);
2636 assert!(h.proved_concrete(marked));
2637 assert!(h.materialized_within(&[marked], 1, None));
2638 assert!(h.materialized_within(&[marked], 64, Some(6)));
2640 assert!(!h.materialized_within(&[marked], 64, Some(5)));
2641 assert!(!h.materialized_within(&[marked], 3, Some(64)));
2642 let inner = h.tuple_literal(&[int(7), name]);
2644 let inner = unmarked(&mut h, inner);
2645 let outer = h.set_from(&mut vec![inner, Handle::FALSE]);
2646 let outer = unmarked(&mut h, outer);
2647 assert_eq!(h.view(outer).flags & flags::CONCRETE, 0);
2648 assert!(!h.proved_concrete(outer));
2649 assert!(h.materialized_within(&[outer], 5, None));
2650 assert!(!h.materialized_within(&[outer], 4, None));
2651 let interval = h.interval(1, 3);
2653 let raw = h.set_enum(&[int(2), int(1)]);
2654 let raw = h.intern_exact(raw).unwrap_or(Handle::EMPTY);
2655 for symbolic in [interval, raw] {
2656 let symbolic = h.intern_exact(symbolic).unwrap_or(Handle::EMPTY);
2657 let nested = h.tuple(&[symbolic]);
2658 let nested = unmarked(&mut h, nested);
2659 for value in [symbolic, nested] {
2660 assert!(!h.proved_concrete(value));
2661 assert!(!h.materialized_within(&[value], 64, None));
2662 }
2663 }
2664 let big = h.int_from_big(&(num_bigint::BigInt::from(1) << 80u32));
2665 if big.is_compound() {
2666 let big = h.intern_exact(big).unwrap_or(Handle::EMPTY);
2667 assert!(h.proved_concrete(big));
2668 assert!(h.materialized_within(&[big], 1, None));
2669 }
2670 assert!(!h.poisoned());
2671 let _ = h.view(Handle::EMPTY);
2672 assert!(
2673 !h.materialized_within(&[int(1)], 1, None),
2674 "current poison declines"
2675 );
2676 }
2677}