1use crate::handle::Tag;
7use crate::node::{Kind, flags};
8use crate::{Handle, Heap};
9
10#[derive(Clone, Debug, PartialEq, Eq)]
12pub enum KeyError {
13 Limit(String),
15 Unsupported(String),
17 Interrupted,
19 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
69pub 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}