Skip to main content

dive_core/
key.rs

1//! Bounded mathematical keys for closed canonical state rows.
2//!
3//! Keys contain values, never Store coordinates or construction authority. This
4//! read-only traversal cannot normalize an original receiver or invoke a provider.
5
6use crate::handle::Tag;
7use crate::node::{Kind, flags};
8use crate::{Handle, Heap};
9
10/// Why a canonical-key traversal did not complete.
11#[derive(Clone, Debug, PartialEq, Eq)]
12pub enum KeyError {
13    /// The key would exceed its explicit byte/workspace policy.
14    Limit(String),
15    /// A value has no admitted closed mathematical encoding.
16    Unsupported(String),
17    /// The actual run owner cancelled the traversal.
18    Interrupted,
19    /// An invalid internal value was supplied.
20    Internal(String),
21}
22
23enum Task {
24    Value(Handle),
25    Integer(i64),
26}
27
28struct Writer {
29    bytes: Vec<u8>,
30    limit: usize,
31}
32
33impl Writer {
34    fn put(&mut self, bytes: &[u8]) -> Result<(), KeyError> {
35        if self
36            .bytes
37            .len()
38            .checked_add(bytes.len())
39            .is_none_or(|n| n > self.limit)
40        {
41            return Err(KeyError::Limit("canonical seen key byte limit".into()));
42        }
43        if self.bytes.capacity() < self.bytes.len() + bytes.len() {
44            let target = self
45                .bytes
46                .capacity()
47                .saturating_mul(2)
48                .max(self.bytes.len() + bytes.len())
49                .min(self.limit);
50            self.bytes
51                .try_reserve_exact(target - self.bytes.len())
52                .map_err(|_| KeyError::Limit("canonical seen key allocation".into()))?;
53        }
54        self.bytes.extend_from_slice(bytes);
55        Ok(())
56    }
57
58    fn len(&mut self, len: usize) -> Result<(), KeyError> {
59        self.put(&(len as u64).to_le_bytes())
60    }
61
62    fn integer(&mut self, bytes: &[u8]) -> Result<(), KeyError> {
63        self.put(&[2])?;
64        self.len(bytes.len())?;
65        self.put(bytes)
66    }
67}
68
69/// Encodes complete mathematical identities without converting to reference values.
70///
71/// The row must already be canonical and closed. Integer-domain functions,
72/// general functions, records and tuples share one function encoding. String
73/// and model-value identities use their text, independently of Store tokens.
74/// Work and workspace are bounded by `max_bytes`, and the actual owner is
75/// checked every 128 values. Original/history values are refused, not normalized.
76///
77/// ```
78/// use std::sync::Arc;
79/// use dive_core::{Handle, Heap, Store};
80/// let heap = Heap::new(Arc::new(Store::default()), true, false);
81/// let bytes = dive_core::key::canonical(&heap, &[Handle::TRUE], 1024, &|| true)?;
82/// assert!(bytes.starts_with(b"DIVECK01"));
83/// # Ok::<(), dive_core::key::KeyError>(())
84/// ```
85///
86/// # Errors
87/// [`KeyError`] distinguishes cancellation, explicit limits, unimplemented values
88/// and invalid internal handles. No partial key is returned.
89pub fn canonical(
90    heap: &Heap,
91    row: &[Handle],
92    max_bytes: usize,
93    proceed: &(dyn Fn() -> bool + Sync),
94) -> Result<Vec<u8>, KeyError> {
95    if !proceed() {
96        return Err(KeyError::Interrupted);
97    }
98    let mut out = Writer {
99        bytes: Vec::new(),
100        limit: max_bytes,
101    };
102    out.put(b"DIVECK01")?;
103    out.len(row.len())?;
104    let mut stack = Vec::new();
105    push(
106        &mut stack,
107        row.iter().rev().copied().map(Task::Value),
108        max_bytes,
109        proceed,
110    )?;
111    let mut steps = 0usize;
112    while let Some(task) = stack.pop() {
113        if steps.is_multiple_of(128) && !proceed() {
114            return Err(KeyError::Interrupted);
115        }
116        steps = steps.saturating_add(1);
117        let h = match task {
118            Task::Value(h) => h,
119            Task::Integer(n) => {
120                let mut bytes = n.to_le_bytes().to_vec();
121                while bytes.len() > 1 {
122                    let last = bytes[bytes.len() - 1];
123                    let next = bytes[bytes.len() - 2];
124                    if (last == 0 && next & 128 == 0) || (last == 255 && next & 128 != 0) {
125                        bytes.pop();
126                    } else {
127                        break;
128                    }
129                }
130                out.integer(&bytes)?;
131                continue;
132            }
133        };
134        if heap.is_int(h) {
135            let value = heap
136                .big(h)
137                .ok_or_else(|| KeyError::Internal("integer without magnitude".into()))?;
138            out.integer(&value.to_signed_bytes_le())?;
139            continue;
140        }
141        encode_value(heap, h, &mut out, &mut stack, max_bytes, proceed)?;
142    }
143    if heap.poisoned() {
144        return Err(KeyError::Internal("poisoned canonical seen value".into()));
145    }
146    Ok(out.bytes)
147}
148
149fn encode_value(
150    heap: &Heap,
151    h: Handle,
152    out: &mut Writer,
153    stack: &mut Vec<Task>,
154    max_bytes: usize,
155    proceed: &(dyn Fn() -> bool + Sync),
156) -> Result<(), KeyError> {
157    match h.tag() {
158        Tag::Bool => out.put(&[1, u8::from(h == Handle::TRUE)])?,
159        Tag::Str | Tag::Model => {
160            let id = h
161                .as_str_id()
162                .or_else(|| h.as_model_id())
163                .ok_or_else(|| KeyError::Internal("name without token".into()))?;
164            let text = heap
165                .store()
166                .strings()
167                .text(id)
168                .ok_or_else(|| KeyError::Internal("unknown name token".into()))?;
169            out.put(&[if h.as_str_id().is_some() { 3 } else { 4 }])?;
170            out.len(text.len())?;
171            out.put(text.as_bytes())?;
172        }
173        Tag::Persistent => {
174            let v = heap.view(h);
175            if v.flags & (flags::VIEW | flags::LAZY) != 0 {
176                return Err(KeyError::Unsupported(
177                    "noncanonical or deferred seen key".into(),
178                ));
179            }
180            match v.kind {
181                Kind::Set => {
182                    out.put(&[5])?;
183                    out.len(v.data.len())?;
184                    push(
185                        stack,
186                        v.data.iter().rev().copied().map(Task::Value),
187                        max_bytes,
188                        proceed,
189                    )?;
190                }
191                Kind::IntFcn => {
192                    out.put(&[6])?;
193                    out.len(v.data.len())?;
194                    for (i, &value) in v.data.iter().enumerate().rev() {
195                        let index = i64::try_from(i)
196                            .ok()
197                            .and_then(|i| v.lo.checked_add(i))
198                            .ok_or_else(|| KeyError::Internal("integer domain overflow".into()))?;
199                        push(
200                            stack,
201                            [Task::Value(value), Task::Integer(index)],
202                            max_bytes,
203                            proceed,
204                        )?;
205                    }
206                }
207                Kind::Fcn => {
208                    if !v.data.len().is_multiple_of(2) {
209                        return Err(KeyError::Internal("odd function data".into()));
210                    }
211                    let n = v.data.len() / 2;
212                    out.put(&[6])?;
213                    out.len(n)?;
214                    for i in (0..n).rev() {
215                        push(
216                            stack,
217                            [Task::Value(v.data[n + i]), Task::Value(v.data[i])],
218                            max_bytes,
219                            proceed,
220                        )?;
221                    }
222                }
223                _ => {
224                    return Err(KeyError::Unsupported(format!(
225                        "symbolic {:?} in disk seen key",
226                        v.kind
227                    )));
228                }
229            }
230        }
231        _ => {
232            return Err(KeyError::Internal(
233                "transient, empty or invalid canonical seen value".into(),
234            ));
235        }
236    }
237    Ok(())
238}
239
240fn push(
241    stack: &mut Vec<Task>,
242    tasks: impl IntoIterator<Item = Task>,
243    max: usize,
244    proceed: &(dyn Fn() -> bool + Sync),
245) -> Result<(), KeyError> {
246    for task in tasks {
247        if stack.len().is_multiple_of(128) && !proceed() {
248            return Err(KeyError::Interrupted);
249        }
250        if stack
251            .len()
252            .checked_add(1)
253            .and_then(|n| n.checked_mul(std::mem::size_of::<Task>()))
254            .is_none_or(|n| n > max)
255        {
256            return Err(KeyError::Limit(
257                "canonical seen key traversal workspace".into(),
258            ));
259        }
260        if stack.capacity() == stack.len() {
261            let cap = max / std::mem::size_of::<Task>();
262            let target = stack
263                .capacity()
264                .saturating_mul(2)
265                .max(stack.len() + 1)
266                .min(cap);
267            stack
268                .try_reserve_exact(target - stack.len())
269                .map_err(|_| KeyError::Limit("canonical seen key traversal allocation".into()))?;
270        }
271        stack.push(task);
272    }
273    Ok(())
274}