dive_core/node.rs
1//! Compound node kinds and the uniform view over both regions
2//! (`03-value-model.md` §4).
3//!
4//! Every compound is canonical when it is built:
5//!
6//! - a **set** is a sorted array of distinct element handles;
7//! - a **function** with a contiguous integer domain `lo..lo+n-1` is an
8//! `IntFcn` holding only its values; sequences and tuples are the case
9//! `lo = 1`, and the empty function is `IntFcn` with `lo = 1`;
10//! - any other function, records included, is a `Fcn`: its sorted keys, then
11//! its values.
12//!
13//! So equal values have equal node contents, and structural equality is a
14//! comparison of arrays. The remaining kinds are symbolic sets, kept for
15//! membership and streaming (S5); a finite symbolic set is materialized to a
16//! `Set` before it is hashed, compared or stored in a state.
17//!
18//! TLC's representation state that is observable under `--compat=tlc` is
19//! kept out of identity as view bits ([`flags`]): a set enumeration that is
20//! not yet normalized is a [`Kind::SetEnum`] node (flag [`flags::UNNORM`]),
21//! a record literal is a `Fcn` with [`flags::RECORD`], and a tuple literal
22//! an `IntFcn` with [`flags::TUPLE`] (`02-semantic-contract.md` C1, C2, C5).
23
24use crate::handle::Handle;
25
26/// The kind of a compound node.
27#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
28#[repr(u8)]
29pub enum Kind {
30 /// A finite set: sorted distinct elements.
31 Set,
32 /// A function over `lo..lo+len-1`: its values.
33 IntFcn,
34 /// Any other function: `len` sorted keys, then `len` values.
35 Fcn,
36 /// `lo..hi`: `data = [hi]`.
37 Interval,
38 /// `SUBSET S`: `data = [S]`.
39 Subset,
40 /// `[D -> R]`: `data = [D, R]`.
41 FcnSet,
42 /// `[f1 : S1, ...]`: `n` sorted field names, then `n` sets.
43 RecSet,
44 /// `Seq(S)`: `data = [S]`.
45 SeqSet,
46 /// `Nat`.
47 Nat,
48 /// `Int`.
49 Int,
50 /// `S1 \X ... \X Sn`: the factors.
51 Product,
52 /// `A \cup B`, kept lazy: `data = [A, B]`.
53 Union,
54 /// `[x \in D |-> e]` before it is materialized: `lo` is the closure id
55 /// (the evaluator's), `data = [D, captures...]`. Lazy.
56 Lambda,
57 /// `{x \in S : P}` before it is enumerated: `lo` is the closure id,
58 /// `data = [S, captures...]`. Lazy.
59 SetPred,
60 /// An integer outside the inline 61-bit range: `lo` is the sign, `data`
61 /// the magnitude's 32-bit digits (least significant first) as inline
62 /// integers. Not a set (`int.rs`).
63 BigInt,
64 /// A set enumeration that TLC has not normalized yet
65 /// (`SetEnumValue` with `isNorm` false): its elements in construction
66 /// order, duplicates kept. Carries [`flags::UNNORM`]. A view, never an
67 /// identity: it is normalized like any finite symbolic set
68 /// (`03-value-model.md` §8).
69 SetEnum,
70}
71
72/// [`View::flags`] bits. They describe a value's representation, never its
73/// identity: hashing, equality, order and interning ignore them
74/// (`03-value-model.md` §8, §11.5 rule 6).
75pub mod flags {
76 /// The value contains a [`super::Kind::Lambda`] or
77 /// [`super::Kind::SetPred`] node, so only the evaluator can close it.
78 pub const LAZY: u8 = 1;
79 /// TLC's `isNorm` is false: the node is a [`super::Kind::SetEnum`] in
80 /// construction order (`02-semantic-contract.md` C1).
81 pub const UNNORM: u8 = 2;
82 /// The function was built by a record literal (TLC's `RecordValue`),
83 /// not by `:>`, `@@` or a constructor (`FcnRcdValue`)
84 /// (`02-semantic-contract.md` C5). Set only on a `Fcn` node. Canonical
85 /// identity interning drops it; its absence there is not provenance.
86 pub const RECORD: u8 = 4;
87 /// The function was built by a tuple literal (TLC's `TupleValue`), not
88 /// as a function over `1..n` (`FcnRcdValue`) (`02-semantic-contract.md`
89 /// C2). Set only on an `IntFcn` node with `lo = 1`. An identity handle
90 /// without the bit is not proof of its original receiver class.
91 pub const TUPLE: u8 = 8;
92 /// A representation-preserving parent contains a child view. It belongs
93 /// to the structural persistent class even when it is itself a general
94 /// function. This is not a literal-class or normalization-history proof.
95 pub const NESTED_VIEW: u8 = 16;
96 /// The view bits: a node carrying one is a lazy view, so it is
97 /// interned apart from identities (`03-value-model.md` §11.3).
98 /// Retired: the construction-history bit of older Store images, worker
99 /// exchanges and candidate records (ADR0131). Nothing sets it; every
100 /// decoder refuses it by name ("legacy construction history").
101 pub const HISTORY: u8 = 32;
102 /// All observable representation bits.
103 pub const VIEW: u8 = UNNORM | RECORD | TUPLE | NESTED_VIEW | HISTORY;
104 /// A cached proof, set only by builders that checked every child: the
105 /// node is an eager `Set`, `IntFcn` or `Fcn` and every descendant is
106 /// materialized (`compare::materialized`). Its absence proves nothing;
107 /// the full check then runs. It is not representation or identity:
108 /// interning, codecs and exchange ignore it.
109 pub const CONCRETE: u8 = 64;
110}
111
112impl Kind {
113 /// Whether the kind is a set.
114 #[must_use]
115 pub const fn is_set(self) -> bool {
116 !matches!(self, Self::IntFcn | Self::Fcn | Self::Lambda | Self::BigInt)
117 }
118
119 /// Whether the kind is a function.
120 #[must_use]
121 pub const fn is_fcn(self) -> bool {
122 matches!(self, Self::IntFcn | Self::Fcn)
123 }
124
125 /// Whether the kind is a symbolic set that the heap can enumerate on its
126 /// own (not [`Kind::SetPred`], which needs the evaluator).
127 #[must_use]
128 pub const fn is_symbolic(self) -> bool {
129 !matches!(
130 self,
131 Self::Set | Self::IntFcn | Self::Fcn | Self::Lambda | Self::SetPred | Self::BigInt
132 )
133 }
134
135 /// Whether the kind is a closure the evaluator forces: a lazy function
136 /// or a set predicate.
137 #[must_use]
138 pub const fn is_lazy(self) -> bool {
139 matches!(self, Self::Lambda | Self::SetPred)
140 }
141}
142
143/// A read-only view of a compound, from either region.
144#[derive(Clone, Copy, Debug)]
145pub struct View<'a> {
146 /// The kind.
147 pub kind: Kind,
148 /// `IntFcn`: the domain's lower bound. `Interval`: its lower bound.
149 pub lo: i64,
150 /// The value hash.
151 pub hash: u64,
152 /// The raw additive sum the hash finalizes (sets and functions).
153 pub sum: u64,
154 /// Representation bits ([`flags`]); not part of identity.
155 pub flags: u8,
156 /// The contents.
157 pub data: &'a [Handle],
158}
159
160impl View<'_> {
161 /// Whether the value must be closed by the evaluator first
162 /// ([`flags::LAZY`]).
163 #[must_use]
164 pub fn is_lazy(&self) -> bool {
165 self.flags & flags::LAZY != 0
166 }
167
168 /// The representation's `isNorm` bit, not a certificate of construction
169 /// history. Selected local literal views use their arena-owned phase;
170 /// an alias can be normalized while retaining its original raw view.
171 #[must_use]
172 pub fn is_norm(&self) -> bool {
173 self.flags & flags::UNNORM == 0
174 }
175
176 /// Whether a function was built by a record literal ([`flags::RECORD`]).
177 #[must_use]
178 pub fn is_record_literal(&self) -> bool {
179 self.flags & flags::RECORD != 0
180 }
181
182 /// Whether a function was built by a tuple literal ([`flags::TUPLE`]).
183 #[must_use]
184 pub fn is_tuple_literal(&self) -> bool {
185 self.flags & flags::TUPLE != 0
186 }
187
188 /// The number of elements (sets) or entries (functions).
189 #[must_use]
190 pub fn len(&self) -> usize {
191 match self.kind {
192 Kind::Fcn | Kind::RecSet => self.data.len() / 2,
193 _ => self.data.len(),
194 }
195 }
196
197 /// Whether the set or function is empty.
198 #[must_use]
199 pub fn is_empty(&self) -> bool {
200 self.len() == 0
201 }
202
203 /// The values of a function.
204 #[must_use]
205 pub fn values(&self) -> &[Handle] {
206 match self.kind {
207 Kind::Fcn => &self.data[self.data.len() / 2..],
208 _ => self.data,
209 }
210 }
211
212 /// The keys of a `Fcn` (empty for other kinds).
213 #[must_use]
214 pub fn keys(&self) -> &[Handle] {
215 match self.kind {
216 Kind::Fcn => &self.data[..self.data.len() / 2],
217 _ => &[],
218 }
219 }
220}