Skip to main content

dive_value/
names.rs

1//! Non-evaluating name-table integrity checks for public typed values.
2
3use std::fmt;
4
5use crate::value::{FcnRepr, SetRepr};
6use crate::{Atom, Interner, Value, ValueOrder};
7
8/// Why a typed value's name tokens cannot be trusted in a given name table.
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub enum NameError {
11    /// An atom's text and token do not identify the same name in the table.
12    ForeignAtom,
13    /// An opaque deferred set would require caller code to inspect its names.
14    OpaqueDeferred,
15    /// A set, record or function is sorted in another value order than the
16    /// one it is checked against.
17    ForeignOrder,
18}
19
20impl fmt::Display for NameError {
21    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
22        write!(
23            f,
24            "{}: {}",
25            self.code(),
26            match self {
27                Self::ForeignAtom => "typed value contains a name token from another name table",
28                Self::OpaqueDeferred =>
29                    "typed value contains an opaque deferred set whose names cannot be checked without evaluating it",
30                Self::ForeignOrder =>
31                    "typed value contains a set, record or function sorted in another value order",
32            }
33        )
34    }
35}
36
37impl NameError {
38    /// The stable diagnostic code for typed value name integrity.
39    #[must_use]
40    pub const fn code(self) -> &'static str {
41        match self {
42            Self::ForeignAtom => "DIVE-V0041",
43            Self::OpaqueDeferred => "DIVE-V0042",
44            Self::ForeignOrder => "DIVE-V0043",
45        }
46    }
47}
48
49impl std::error::Error for NameError {}
50
51fn check_atom(atom: &Atom, names: &Interner) -> Result<(), NameError> {
52    if names
53        .resolve(atom.tok())
54        .is_some_and(|known| known.as_str() == atom.as_str())
55    {
56        Ok(())
57    } else {
58        Err(NameError::ForeignAtom)
59    }
60}
61
62impl Value {
63    /// Checks every stored string, model value and record-field name against
64    /// `names`, including symbolic set components. Text and token must both
65    /// match. This iterative walk does not intern names, normalize or enumerate
66    /// sets, or invoke callbacks; it accepts any stored nesting depth.
67    ///
68    /// ```
69    /// use dive_value::{Interner, NameError, Value};
70    /// let names = Interner::new();
71    /// let owned = Value::string(&names, "a");
72    /// assert_eq!(owned.validate_names(&names), Ok(()));
73    /// let foreign = Interner::new();
74    /// foreign.intern("padding");
75    /// let wrong_token = Value::string(&foreign, "a");
76    /// assert_eq!(wrong_token.validate_names(&names), Err(NameError::ForeignAtom));
77    /// ```
78    ///
79    /// # Errors
80    /// A foreign name token or an opaque deferred set. Even a deferred set
81    /// with cached elements is refused because its source may contain names
82    /// the cache does not expose.
83    pub fn validate_names(&self, names: &Interner) -> Result<(), NameError> {
84        self.walk_names(names, None)
85    }
86
87    /// [`Self::validate_names`], and also checks that every stored set,
88    /// record and non-tuple function is sorted in `order`: a value built under
89    /// another run's order would be read in the wrong order by operations
90    /// that rely on normalization (`CHOOSE`, enumeration, merging).
91    ///
92    /// ```
93    /// use dive_value::{Ctx, Interner, NameError, Value};
94    /// let names = Interner::new();
95    /// let set = Value::set(vec![Value::string(&names, "a")], Ctx::dive()).expect("set");
96    /// assert_eq!(set.validate_names_in(&names, Ctx::dive().order), Ok(()));
97    /// assert_eq!(
98    ///     set.validate_names_in(&names, Ctx::tlc().order),
99    ///     Err(NameError::ForeignOrder)
100    /// );
101    /// ```
102    ///
103    /// # Errors
104    /// As [`Self::validate_names`], or a value sorted in another order.
105    pub fn validate_names_in(&self, names: &Interner, order: ValueOrder) -> Result<(), NameError> {
106        self.walk_names(names, Some(order))
107    }
108
109    fn walk_names(&self, names: &Interner, order: Option<ValueOrder>) -> Result<(), NameError> {
110        let mut work = vec![self];
111        while let Some(value) = work.pop() {
112            match value {
113                Self::Str(atom) | Self::Model(atom) => check_atom(atom, names)?,
114                Self::Fcn(fcn) => match &fcn.0.repr {
115                    FcnRepr::Tuple(values) => work.extend(values.iter()),
116                    _ if order.is_some_and(|o| fcn.order() != o) => {
117                        return Err(NameError::ForeignOrder);
118                    }
119                    FcnRepr::Record(fields) => {
120                        for (atom, value) in fields {
121                            check_atom(atom, names)?;
122                            work.push(value);
123                        }
124                    }
125                    FcnRepr::General(pairs) => {
126                        for (key, value) in pairs {
127                            work.push(key);
128                            work.push(value);
129                        }
130                    }
131                },
132                Self::Set(set) => {
133                    // An opaque deferred set is refused as such whatever its order.
134                    if matches!(set.repr(), SetRepr::Deferred(_)) {
135                        return Err(NameError::OpaqueDeferred);
136                    }
137                    if order.is_some_and(|o| set.order() != o) {
138                        return Err(NameError::ForeignOrder);
139                    }
140                    match set.repr() {
141                        SetRepr::Deferred(_) => return Err(NameError::OpaqueDeferred),
142                        SetRepr::Raw(values) | SetRepr::Product(values) => {
143                            work.extend(values.iter());
144                        }
145                        SetRepr::Subset(base) | SetRepr::Seq(base) => work.push(base),
146                        SetRepr::FcnSet(domain, range) => {
147                            work.push(domain);
148                            work.push(range);
149                        }
150                        SetRepr::RcdSet(fields) => {
151                            for (atom, value) in fields {
152                                check_atom(atom, names)?;
153                                work.push(value);
154                            }
155                        }
156                        SetRepr::Enum
157                        | SetRepr::Interval(_, _)
158                        | SetRepr::Nat
159                        | SetRepr::Int
160                        | SetRepr::Strings => {}
161                    }
162                    if let Some(values) = set.0.elems.get() {
163                        work.extend(values.iter());
164                    }
165                }
166                Self::Bool(_) | Self::Int(_) | Self::BigInt(_) => {}
167            }
168        }
169        Ok(())
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    #![allow(clippy::expect_used, reason = "test construction")]
176
177    use std::sync::Arc;
178    use std::sync::atomic::{AtomicUsize, Ordering};
179
180    use super::*;
181    use crate::{Ctx, DeferredKind, DeferredSet};
182
183    #[test]
184    fn every_stored_and_symbolic_name_position_is_checked_without_interning() {
185        for ctx in [Ctx::tlc(), Ctx::default()] {
186            let known = Interner::new();
187            known.intern("padding");
188            known.intern("name");
189            let foreign = Interner::new();
190            foreign.intern("name");
191            for (names, expected) in [(&known, Ok(())), (&foreign, Err(NameError::ForeignAtom))] {
192                let atom = names.intern("name");
193                let string = Value::Str(atom.clone());
194                let values = [
195                    string.clone(),
196                    Value::Model(atom.clone()),
197                    Value::tuple(vec![string.clone()]),
198                    Value::record(vec![(atom.clone(), Value::Int(0))], ctx).expect("record"),
199                    Value::fcn(vec![(string.clone(), Value::Int(0))], ctx)
200                        .expect("function domain"),
201                    Value::fcn(vec![(Value::Int(9), string.clone())], ctx).expect("function range"),
202                    Value::set(vec![string.clone()], ctx).expect("set"),
203                    Value::set_raw(vec![string.clone()], ctx),
204                    Value::subset(string.clone(), ctx),
205                    Value::fcn_set(string.clone(), Value::Int(0), ctx),
206                    Value::fcn_set(Value::Int(0), string.clone(), ctx),
207                    Value::record_set(vec![(atom, Value::Int(0))], ctx).expect("record set"),
208                    Value::product(vec![string.clone()], ctx),
209                    Value::seq_set(string, ctx),
210                ];
211                for value in values {
212                    assert_eq!(value.validate_names(&known), expected);
213                }
214            }
215            assert_eq!(known.len(), 2);
216        }
217    }
218
219    #[derive(Debug, Default)]
220    struct Opaque(AtomicUsize);
221
222    impl DeferredSet for Opaque {
223        fn kind(&self) -> DeferredKind {
224            DeferredKind::Map
225        }
226        fn elements(&self, _: Ctx) -> crate::Result<Vec<Value>> {
227            self.0.fetch_add(1, Ordering::Relaxed);
228            Ok(Vec::new())
229        }
230        fn member(&self, _: &Value, _: Ctx) -> Option<crate::Result<bool>> {
231            None
232        }
233    }
234
235    #[test]
236    fn opaque_values_are_refused_without_callbacks_and_deep_values_are_iterative() {
237        let names = Interner::new();
238        let source = Arc::new(Opaque::default());
239        let value = Value::deferred(source.clone(), Ctx::tlc());
240        assert_eq!(value.validate_names(&names), Err(NameError::OpaqueDeferred));
241        assert_eq!(source.0.load(Ordering::Relaxed), 0);
242        let mut deep = Value::string(&names, "owned");
243        for _ in 0..2000 {
244            deep = Value::tuple(vec![deep]);
245        }
246        assert_eq!(deep.validate_names(&names), Ok(()));
247    }
248}