1use std::cmp::Ordering;
10use std::collections::HashMap;
11use std::fmt;
12use std::hash::{Hash, Hasher};
13use std::sync::{Arc, Mutex, PoisonError};
14
15use crate::ctx::ValueOrder;
16
17impl crate::Value {
18 #[must_use]
38 pub fn flat_cache_heap_bytes(
39 &self,
40 names: &Interner,
41 proceed: &mut dyn FnMut() -> bool,
42 ) -> Option<usize> {
43 use crate::value::{FcnInner, FcnRepr};
44 if !proceed() {
45 return None;
46 }
47 let immediate = |value: &Self| matches!(value, Self::Bool(_) | Self::Int(_));
48 match self {
49 Self::Bool(_) | Self::Int(_) => Some(0),
50 Self::Fcn(function) => {
51 let payload = match &function.0.repr {
52 FcnRepr::Tuple(elements) => {
53 for value in elements {
54 if !proceed() || !immediate(value) {
55 return None;
56 }
57 }
58 std::mem::size_of_val(elements.as_ref())
59 }
60 FcnRepr::Record(fields) => {
61 for (name, value) in fields {
62 if !proceed()
63 || !immediate(value)
64 || !names
65 .resolve(name.tok())
66 .is_some_and(|known| Arc::ptr_eq(&name.0, &known.0))
67 {
68 return None;
69 }
70 }
71 std::mem::size_of_val(fields.as_ref())
72 }
73 FcnRepr::General(_) => return None,
74 };
75 std::mem::size_of::<FcnInner>().checked_add(payload)
76 }
77 _ => None,
78 }
79 }
80
81 #[must_use]
108 pub fn closed_function_cache_heap_bytes(
109 &self,
110 names: &Interner,
111 proceed: &mut dyn FnMut() -> bool,
112 ) -> Option<usize> {
113 closed_cache_bytes(self, names, &mut 4096, 0, false, proceed)
114 }
115
116 #[must_use]
136 pub fn closed_cache_heap_bytes(
137 &self,
138 names: &Interner,
139 proceed: &mut dyn FnMut() -> bool,
140 ) -> Option<usize> {
141 closed_cache_bytes(self, names, &mut 4096, 0, true, proceed)
142 }
143}
144
145fn run_owned(name: &Atom, names: &Interner) -> bool {
146 names
147 .resolve(name.tok())
148 .is_some_and(|known| Arc::ptr_eq(&name.0, &known.0))
149}
150
151fn closed_cache_bytes(
152 value: &crate::Value,
153 names: &Interner,
154 remaining: &mut usize,
155 depth: usize,
156 sets: bool,
157 proceed: &mut dyn FnMut() -> bool,
158) -> Option<usize> {
159 use crate::Value;
160 use crate::function_domain::DomainInner;
161 use crate::value::{FcnInner, FcnRepr, SetInner, SetRepr};
162 *remaining = remaining.checked_sub(1)?;
163 if !proceed() {
164 return None;
165 }
166 match value {
167 Value::Bool(_) | Value::Int(_) => Some(0),
168 Value::Str(name) if run_owned(name, names) => Some(0),
169 Value::Set(set) if sets && depth < 64 && matches!(set.0.repr, SetRepr::Enum) => {
170 let elements = set.0.elems.get()?;
171 let mut bytes = std::mem::size_of::<SetInner>()
172 .checked_add(std::mem::size_of_val(elements.as_ref()))?;
173 for child in elements.as_ref() {
174 bytes = bytes.checked_add(closed_cache_bytes(
175 child,
176 names,
177 remaining,
178 depth + 1,
179 sets,
180 proceed,
181 )?)?;
182 }
183 Some(bytes)
184 }
185 Value::Fcn(function) if depth < 64 => {
186 let mut bytes = std::mem::size_of::<FcnInner>();
187 match &function.0.repr {
188 FcnRepr::Tuple(elements) => {
189 bytes = bytes.checked_add(std::mem::size_of_val(elements.as_ref()))?;
190 for child in elements {
191 bytes = bytes.checked_add(closed_cache_bytes(
192 child,
193 names,
194 remaining,
195 depth + 1,
196 sets,
197 proceed,
198 )?)?;
199 }
200 }
201 FcnRepr::Record(fields) => {
202 bytes = bytes.checked_add(std::mem::size_of_val(fields.as_ref()))?;
203 for (name, child) in fields {
204 if !proceed() || !run_owned(name, names) {
205 return None;
206 }
207 bytes = bytes.checked_add(closed_cache_bytes(
208 child,
209 names,
210 remaining,
211 depth + 1,
212 sets,
213 proceed,
214 )?)?;
215 }
216 }
217 FcnRepr::General(general) => {
218 bytes = bytes.checked_add(std::mem::size_of::<DomainInner>())?;
219 bytes =
220 bytes.checked_add(std::mem::size_of_val(general.domain.keys.as_ref()))?;
221 bytes = bytes.checked_add(std::mem::size_of_val(general.values.as_ref()))?;
222 bytes = bytes.checked_add(
226 general
227 .domain
228 .keys
229 .len()
230 .checked_mul(std::mem::size_of::<usize>())?,
231 )?;
232 for key in &general.domain.keys {
233 if !matches!(key, Value::Bool(_) | Value::Int(_) | Value::Str(_)) {
234 return None;
235 }
236 bytes = bytes.checked_add(closed_cache_bytes(
237 key,
238 names,
239 remaining,
240 depth + 1,
241 sets,
242 proceed,
243 )?)?;
244 }
245 for child in &general.values {
246 bytes = bytes.checked_add(closed_cache_bytes(
247 child,
248 names,
249 remaining,
250 depth + 1,
251 sets,
252 proceed,
253 )?)?;
254 }
255 }
256 }
257 Some(bytes)
258 }
259 _ => None,
260 }
261}
262
263#[derive(Clone)]
268pub struct Atom(Arc<AtomInner>);
269
270struct AtomInner {
271 text: Box<str>,
272 tok: u32,
273 hash: u64,
274 utf16_len: u32,
275 mv_type: u16,
278}
279
280impl Atom {
281 fn new(text: &str, tok: u32) -> Self {
282 let units: Vec<u16> = text.encode_utf16().collect();
283 let mv_type = if units.len() > 2 && units[1] == u16::from(b'_') {
284 units[0]
285 } else {
286 0
287 };
288 Self(Arc::new(AtomInner {
289 text: text.into(),
290 tok,
291 hash: text_hash(text),
292 utf16_len: u32::try_from(units.len()).unwrap_or(u32::MAX),
293 mv_type,
294 }))
295 }
296
297 #[must_use]
299 pub fn as_str(&self) -> &str {
300 &self.0.text
301 }
302
303 #[must_use]
305 pub fn tok(&self) -> u32 {
306 self.0.tok
307 }
308
309 #[must_use]
311 pub fn utf16_len(&self) -> u32 {
312 self.0.utf16_len
313 }
314
315 #[must_use]
318 pub fn mv_type(&self) -> Option<u16> {
319 (self.0.mv_type != 0).then_some(self.0.mv_type)
320 }
321
322 #[must_use]
324 pub fn text_hash(&self) -> u64 {
325 self.0.hash
326 }
327
328 #[must_use]
330 pub fn cmp_with(&self, other: &Self, order: ValueOrder) -> Ordering {
331 if Arc::ptr_eq(&self.0, &other.0) {
332 return Ordering::Equal;
333 }
334 match order {
335 ValueOrder::Tlc => self
336 .0
337 .tok
338 .cmp(&other.0.tok)
339 .then_with(|| self.0.text.cmp(&other.0.text)),
340 ValueOrder::Canonical => self.0.text.cmp(&other.0.text),
341 }
342 }
343}
344
345impl PartialEq for Atom {
346 fn eq(&self, other: &Self) -> bool {
347 Arc::ptr_eq(&self.0, &other.0)
348 || (self.0.hash == other.0.hash && self.0.text == other.0.text)
349 }
350}
351
352impl Eq for Atom {}
353
354impl Hash for Atom {
355 fn hash<H: Hasher>(&self, state: &mut H) {
356 state.write_u64(self.0.hash);
357 }
358}
359
360impl fmt::Debug for Atom {
361 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
362 write!(f, "{:?}#{}", self.as_str(), self.tok())
363 }
364}
365
366impl fmt::Display for Atom {
367 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
368 f.write_str(self.as_str())
369 }
370}
371
372pub(crate) fn text_hash(text: &str) -> u64 {
374 let mut h: u64 = 0xcbf2_9ce4_8422_2325;
375 for b in text.bytes() {
376 h ^= u64::from(b);
377 h = h.wrapping_mul(0x0100_0000_01b3);
378 }
379 mix64(h)
380}
381
382pub(crate) const fn mix64(mut z: u64) -> u64 {
384 z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
385 z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
386 z ^ (z >> 31)
387}
388
389#[derive(Default)]
404pub struct Interner {
405 table: Mutex<Table>,
406}
407
408#[derive(Default)]
409struct Table {
410 by_text: HashMap<Box<str>, Atom>,
411 by_tok: Vec<Atom>,
413}
414
415impl Interner {
416 #[must_use]
418 pub fn new() -> Self {
419 Self::default()
420 }
421
422 pub fn intern(&self, text: &str) -> Atom {
424 let mut table = self.table.lock().unwrap_or_else(PoisonError::into_inner);
425 if let Some(atom) = table.by_text.get(text) {
426 return atom.clone();
427 }
428 let tok = u32::try_from(table.by_tok.len()).unwrap_or(u32::MAX);
429 let atom = Atom::new(text, tok);
430 table.by_text.insert(text.into(), atom.clone());
431 table.by_tok.push(atom.clone());
432 atom
433 }
434
435 #[must_use]
448 pub fn resolve(&self, tok: u32) -> Option<Atom> {
449 let table = self.table.lock().unwrap_or_else(PoisonError::into_inner);
450 usize::try_from(tok)
451 .ok()
452 .and_then(|t| table.by_tok.get(t))
453 .cloned()
454 }
455
456 #[must_use]
458 pub fn get(&self, text: &str) -> Option<Atom> {
459 let table = self.table.lock().unwrap_or_else(PoisonError::into_inner);
460 table.by_text.get(text).cloned()
461 }
462
463 #[must_use]
465 pub fn len(&self) -> usize {
466 self.table
467 .lock()
468 .unwrap_or_else(PoisonError::into_inner)
469 .by_tok
470 .len()
471 }
472
473 #[must_use]
475 pub fn is_empty(&self) -> bool {
476 self.len() == 0
477 }
478}
479
480impl fmt::Debug for Interner {
481 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
482 f.debug_struct("Interner")
483 .field("len", &self.len())
484 .finish()
485 }
486}
487
488#[cfg(test)]
489#[allow(
490 clippy::expect_used,
491 reason = "flat-cache storage and ownership fixtures"
492)]
493mod flat_cache_tests {
494 use super::*;
495 use crate::{Ctx, Value};
496
497 #[test]
498 fn only_flat_immediates_with_run_owned_names_receive_known_payload_charge() {
499 let names = Interner::new();
500 let key = names.intern("x");
501 let record =
502 Value::record(vec![(key.clone(), Value::Int(1))], Ctx::dive()).expect("record");
503 let general =
504 Value::fcn(vec![(Value::Str(key), Value::Int(1))], Ctx::dive()).expect("function");
505 let expected =
506 std::mem::size_of::<crate::value::FcnInner>() + std::mem::size_of::<(Atom, Value)>();
507 assert_eq!(
508 record.flat_cache_heap_bytes(&names, &mut || true),
509 Some(expected)
510 );
511 assert_eq!(
512 general.flat_cache_heap_bytes(&names, &mut || true),
513 Some(expected)
514 );
515 let tuple = Value::tuple(vec![Value::Int(1), Value::Bool(true)]);
516 assert_eq!(
517 tuple.flat_cache_heap_bytes(&names, &mut || true),
518 Some(std::mem::size_of::<crate::value::FcnInner>() + 2 * std::mem::size_of::<Value>())
519 );
520 let foreign = Interner::new();
521 let other = Value::record(vec![(foreign.intern("x"), Value::Int(1))], Ctx::dive())
522 .expect("foreign record");
523 assert_eq!(other.flat_cache_heap_bytes(&names, &mut || true), None);
524 for unsupported in [
525 Value::tuple(vec![tuple]),
526 Value::string(&names, "x"),
527 Value::empty_set(Ctx::dive()),
528 Value::fcn(vec![(Value::Int(0), Value::Int(1))], Ctx::dive()).expect("general domain"),
529 ] {
530 assert_eq!(
531 unsupported.flat_cache_heap_bytes(&names, &mut || true),
532 None
533 );
534 }
535 assert_eq!(record.flat_cache_heap_bytes(&names, &mut || false), None);
536 assert_eq!(
537 Value::Int(1).flat_cache_heap_bytes(&names, &mut || true),
538 Some(0)
539 );
540 }
541
542 #[test]
543 fn closed_function_charge_covers_nested_arrays_and_future_domain_order() {
544 use crate::function_domain::DomainInner;
545 use crate::value::{FcnInner, FcnRepr};
546 for ctx in [Ctx::dive(), Ctx::tlc()] {
547 let names = Interner::new();
548 let child = Value::record(
549 vec![(
550 names.intern("message"),
551 Value::tuple(vec![Value::string(&names, "tok"), Value::Int(3)]),
552 )],
553 ctx,
554 )
555 .expect("record");
556 let child_bytes = child
557 .closed_function_cache_heap_bytes(&names, &mut || true)
558 .expect("closed child");
559 let value = Value::fcn(
560 vec![(Value::Int(0), child.clone()), (Value::Int(1), child)],
561 ctx,
562 )
563 .expect("integer-domain function");
564 let expected = std::mem::size_of::<FcnInner>()
565 + std::mem::size_of::<DomainInner>()
566 + 4 * std::mem::size_of::<Value>()
567 + 2 * std::mem::size_of::<usize>()
568 + 2 * child_bytes;
569 assert_eq!(
570 value.closed_function_cache_heap_bytes(&names, &mut || true),
571 Some(expected)
572 );
573 let repr = &value.as_fcn().expect("function").0.repr;
574 assert!(matches!(repr, FcnRepr::General(_)));
575 if let FcnRepr::General(general) = repr {
576 assert_eq!(
577 general.domain.checked_index(&Value::Int(1)),
578 crate::DomainLookup::Found(1)
579 );
580 assert_eq!(general.domain.tlc_order().expect("pure order").len(), 2);
581 }
582 assert_eq!(
583 value.closed_function_cache_heap_bytes(&names, &mut || true),
584 Some(expected),
585 "lazy header facts/order allocation were prepaid"
586 );
587 }
588 }
589
590 #[test]
591 fn closed_inspection_declines_history_foreign_names_and_product_keys_without_effects() {
592 let names = Interner::new();
593 let foreign = Interner::new();
594 for leaf in [
595 Value::empty_set(Ctx::dive()),
596 Value::set_raw(vec![Value::Int(1)], Ctx::dive()),
597 Value::string(&foreign, "foreign"),
598 Value::model(&names, "model"),
599 Value::int(crate::Int::from_big(num_bigint::BigInt::from(1u64) << 80)),
600 ] {
601 let tree = Value::tuple(vec![leaf]);
602 assert_eq!(
603 tree.closed_function_cache_heap_bytes(&names, &mut || true),
604 None
605 );
606 }
607 let key = Value::tuple(vec![Value::Int(0)]);
608 let product =
609 Value::fcn(vec![(key, Value::Int(1))], Ctx::dive()).expect("product-domain function");
610 assert_eq!(
611 product.closed_function_cache_heap_bytes(&names, &mut || true),
612 None
613 );
614 let value = Value::tuple(vec![Value::Int(1)]);
615 assert_eq!(
616 value.closed_function_cache_heap_bytes(&names, &mut || false),
617 None
618 );
619 let mut deep = Value::Int(0);
620 for _ in 0..65 {
621 deep = Value::tuple(vec![deep]);
622 }
623 assert_eq!(
624 deep.closed_function_cache_heap_bytes(&names, &mut || true),
625 None
626 );
627 let wide = Value::tuple(vec![Value::Int(0); 4096]);
628 assert_eq!(
629 wide.closed_function_cache_heap_bytes(&names, &mut || true),
630 None
631 );
632 assert!(
633 Value::tuple(vec![Value::Int(0); 4095])
634 .closed_function_cache_heap_bytes(&names, &mut || true)
635 .is_some()
636 );
637 }
638
639 #[test]
640 fn concrete_set_charge_includes_headers_arrays_and_repeated_closed_children() {
641 use crate::value::{FcnInner, SetInner};
642 let names = Interner::new();
643 for ctx in [Ctx::dive(), Ctx::tlc()] {
644 let leaf = Value::set(vec![Value::Int(1)], ctx).expect("set");
645 let leaf_bytes = std::mem::size_of::<SetInner>() + std::mem::size_of::<Value>();
646 assert_eq!(
647 leaf.closed_cache_heap_bytes(&names, &mut || true),
648 Some(leaf_bytes)
649 );
650 assert_eq!(
651 leaf.closed_function_cache_heap_bytes(&names, &mut || true),
652 None
653 );
654 let tree = Value::tuple(vec![leaf.clone(), leaf]);
655 assert_eq!(
656 tree.closed_cache_heap_bytes(&names, &mut || true),
657 Some(
658 std::mem::size_of::<FcnInner>()
659 + 2 * std::mem::size_of::<Value>()
660 + 2 * leaf_bytes
661 )
662 );
663 let record = Value::record(vec![(names.intern("items"), tree)], ctx).expect("record");
664 let outer = Value::set(vec![record], ctx).expect("outer set");
665 assert!(
666 outer
667 .closed_cache_heap_bytes(&names, &mut || true)
668 .is_some()
669 );
670 assert_eq!(outer.closed_cache_heap_bytes(&names, &mut || false), None);
671 }
672 }
673
674 #[test]
675 fn set_cache_inspection_keeps_symbolic_raw_foreign_and_depth_boundaries() {
676 use crate::value::{Set, SetRepr};
677 let names = Interner::new();
678 let foreign = Interner::new();
679 for ctx in [Ctx::dive(), Ctx::tlc()] {
680 let raw = Value::set_raw(vec![Value::Int(1)], ctx);
681 let interval = Value::interval(1.into(), 2.into(), ctx);
682 interval
683 .as_set()
684 .expect("interval")
685 .elements(ctx)
686 .expect("cached elements");
687 for value in [
688 raw,
689 interval,
690 Value::nat(ctx),
691 Value::subset(Value::empty_set(ctx), ctx),
692 Value::Set(Set::new(ctx.order, SetRepr::Enum)),
693 Value::tuple(vec![Value::string(&foreign, "foreign")]),
694 Value::tuple(vec![Value::model(&names, "model")]),
695 ] {
696 assert_eq!(value.closed_cache_heap_bytes(&names, &mut || true), None);
697 }
698 let mut deep = Value::Int(0);
699 for _ in 0..65 {
700 deep = Value::set(vec![deep], ctx).expect("nested set");
701 }
702 assert_eq!(deep.closed_cache_heap_bytes(&names, &mut || true), None);
703 let wide = Value::set((0..4096).map(Value::Int).collect(), ctx).expect("wide set");
704 assert_eq!(wide.closed_cache_heap_bytes(&names, &mut || true), None);
705 }
706 }
707
708 #[test]
709 fn concrete_cache_inspection_never_calls_even_an_already_materialized_provider() {
710 use std::sync::atomic::{AtomicUsize, Ordering};
711 #[derive(Debug)]
712 struct Probe(Arc<AtomicUsize>);
713 impl crate::DeferredSet for Probe {
714 fn kind(&self) -> crate::DeferredKind {
715 self.0.fetch_add(1, Ordering::Relaxed);
716 crate::DeferredKind::Filter
717 }
718 fn elements(&self, _ctx: Ctx) -> crate::Result<Vec<Value>> {
719 self.0.fetch_add(1, Ordering::Relaxed);
720 Ok(vec![Value::Int(1)])
721 }
722 fn member(&self, _value: &Value, _ctx: Ctx) -> Option<crate::Result<bool>> {
723 self.0.fetch_add(1, Ordering::Relaxed);
724 Some(Ok(true))
725 }
726 }
727 let names = Interner::new();
728 for ctx in [Ctx::dive(), Ctx::tlc()] {
729 let calls = Arc::new(AtomicUsize::new(0));
730 let value = Value::deferred(Arc::new(Probe(calls.clone())), ctx);
731 assert_eq!(value.closed_cache_heap_bytes(&names, &mut || true), None);
732 assert_eq!(calls.load(Ordering::Relaxed), 0);
733 let set = value.as_set().expect("provider set");
734 set.elements(ctx)
735 .expect("deliberately materialize provider");
736 assert!(set.has_cached_elements());
737 let before = calls.load(Ordering::Relaxed);
738 assert_eq!(value.closed_cache_heap_bytes(&names, &mut || true), None);
739 assert_eq!(calls.load(Ordering::Relaxed), before);
740 }
741 }
742}