Skip to main content

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}