1use std::collections::HashMap;
15
16use crate::writer::ByteWriter;
17
18#[derive(Clone, Debug, PartialEq, Eq)]
20pub struct NodeSpec {
21 pub level: u8,
23 pub ty: Vec<u8>,
25 pub name: Vec<u8>,
27 pub byte_size: i32,
29 pub version: i32,
31 pub type_flags: i32,
33 pub meta_flag: i32,
35 pub ref_type_hash: u64,
37 pub index: Option<i32>,
41}
42
43impl NodeSpec {
44 #[must_use]
46 pub fn new(level: u8, ty: &str, name: &str) -> Self {
47 Self {
48 level,
49 ty: ty.as_bytes().to_vec(),
50 name: name.as_bytes().to_vec(),
51 byte_size: 0,
52 version: 1,
53 type_flags: 0,
54 meta_flag: 0,
55 ref_type_hash: 0,
56 index: None,
57 }
58 }
59
60 #[must_use]
62 pub fn size(mut self, byte_size: i32) -> Self {
63 self.byte_size = byte_size;
64 self
65 }
66
67 #[must_use]
69 pub fn aligned(mut self) -> Self {
70 self.meta_flag |= 0x4000;
71 self
72 }
73}
74
75#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
77pub enum Strings {
78 #[default]
80 Local,
81 Common,
84}
85
86#[must_use]
93pub fn blob_tree(
94 nodes: &[NodeSpec],
95 format: u32,
96 big_endian: bool,
97 strings: Strings,
98 common: &[(u32, &[u8])],
99) -> Vec<u8> {
100 let mut buffer: Vec<u8> = Vec::new();
101 let mut local: HashMap<Vec<u8>, u32> = HashMap::new();
102 let mut offset = |s: &[u8]| -> u32 {
103 if strings == Strings::Common
104 && let Some((o, _)) = common.iter().find(|(_, c)| *c == s)
105 {
106 return o | 0x8000_0000;
107 }
108 if let Some(o) = local.get(s) {
109 return *o;
110 }
111 let o = u32::try_from(buffer.len()).unwrap_or(u32::MAX);
112 buffer.extend_from_slice(s);
113 buffer.push(0);
114 local.insert(s.to_vec(), o);
115 o
116 };
117 let offsets: Vec<(u32, u32)> = nodes
118 .iter()
119 .map(|n| {
120 let t = offset(&n.ty);
121 (t, offset(&n.name))
122 })
123 .collect();
124
125 let mut w = writer(big_endian);
126 w.i32(len_i32(nodes.len()));
127 w.i32(len_i32(buffer.len()));
128 for (i, (n, (ty, name))) in nodes.iter().zip(offsets).enumerate() {
129 w.i16(truncate_i16(n.version));
132 w.u8(n.level);
133 w.u8(n.type_flags.to_le_bytes()[0]);
134 w.u32(ty);
135 w.u32(name);
136 w.i32(n.byte_size);
137 w.i32(n.index.unwrap_or_else(|| len_i32(i)));
138 w.i32(n.meta_flag);
139 if format >= 19 {
140 w.u64(n.ref_type_hash);
141 }
142 }
143 w.bytes(&buffer);
144 w.into_inner()
145}
146
147#[must_use]
154pub fn old_tree(nodes: &[NodeSpec], format: u32, big_endian: bool) -> Vec<u8> {
155 let parents = parents(nodes);
156 let mut w = writer(big_endian);
157 for (i, n) in nodes.iter().enumerate() {
158 w.cstr(&n.ty);
159 w.cstr(&n.name);
160 w.i32(n.byte_size);
161 if format == 2 {
162 w.i32(0);
163 }
164 if format != 3 {
165 w.i32(n.index.unwrap_or_else(|| len_i32(i)));
166 }
167 w.i32(n.type_flags);
168 w.i32(n.version);
169 if format != 3 {
170 w.i32(n.meta_flag);
171 }
172 let children = parents.iter().filter(|p| **p == Some(i)).count();
173 w.i32(len_i32(children));
174 }
175 w.into_inner()
176}
177
178#[must_use]
184pub fn no_nul_blob(rows: usize, buffer: usize) -> Vec<u8> {
185 let mut w = ByteWriter::le();
186 w.i32(len_i32(rows)).i32(len_i32(buffer));
187 for i in 0..rows {
188 w.i16(1).u8(0).u8(0).u32(0).u32(0);
191 w.i32(-1).i32(len_i32(i)).i32(0).u64(0);
192 }
193 w.bytes(&vec![b'A'; buffer]);
194 w.into_inner()
195}
196
197fn parents(nodes: &[NodeSpec]) -> Vec<Option<usize>> {
202 let mut out = Vec::with_capacity(nodes.len());
203 let root: (Option<usize>, i32) = (None, -1);
205 let mut stack: Vec<(Option<usize>, i32)> = Vec::new();
206 let mut parent = root;
207 let mut prev = root;
208 for (i, n) in nodes.iter().enumerate() {
209 let level = i32::from(n.level);
210 if level > prev.1 {
211 stack.push(parent);
212 parent = prev;
213 } else if level < prev.1 {
214 while level <= parent.1 {
215 parent = stack.pop().unwrap_or(root);
216 if parent == root {
217 break;
218 }
219 }
220 }
221 out.push(parent.0);
222 prev = (Some(i), level);
223 }
224 out
225}
226
227fn writer(big_endian: bool) -> ByteWriter {
228 if big_endian {
229 ByteWriter::be()
230 } else {
231 ByteWriter::le()
232 }
233}
234
235fn len_i32(n: usize) -> i32 {
236 i32::try_from(n).unwrap_or(i32::MAX)
237}
238
239fn truncate_i16(v: i32) -> i16 {
240 let b = v.to_le_bytes();
241 i16::from_le_bytes([b[0], b[1]])
242}
243
244#[cfg(test)]
245mod tests {
246 use super::{NodeSpec, Strings, blob_tree, old_tree, parents};
247
248 fn tree() -> Vec<NodeSpec> {
249 vec![
250 NodeSpec::new(0, "Base", "Base"),
251 NodeSpec::new(1, "int", "a").size(4),
252 NodeSpec::new(1, "Sub", "s"),
253 NodeSpec::new(2, "UInt8", "b").size(1).aligned(),
254 NodeSpec::new(1, "int", "c").size(4),
255 ]
256 }
257
258 #[test]
259 fn a_blob_is_counts_rows_and_a_deduplicated_buffer() {
260 let b = blob_tree(&tree(), 17, false, Strings::Local, &[]);
261 assert_eq!(&b[..4], &5i32.to_le_bytes());
262 let buf = b"Base\0int\0a\0Sub\0s\0UInt8\0b\0c\0";
263 assert_eq!(&b[4..8], &i32::try_from(buf.len()).unwrap().to_le_bytes());
264 assert_eq!(b.len(), 8 + 5 * 24 + buf.len());
265 assert_eq!(&b[b.len() - buf.len()..], buf);
266 let row = &b[8 + 3 * 24..8 + 4 * 24];
269 assert_eq!(&row[..4], &[1, 0, 2, 0]);
270 assert_eq!(&row[4..8], &17u32.to_le_bytes());
271 assert_eq!(&row[8..12], &23u32.to_le_bytes());
272 assert_eq!(&row[16..20], &3i32.to_le_bytes());
273 assert_eq!(&row[20..24], &0x4000i32.to_le_bytes());
274 let b = blob_tree(&tree(), 19, true, Strings::Local, &[]);
276 assert_eq!(b.len(), 8 + 5 * 32 + buf.len());
277 assert_eq!(&b[..4], &5i32.to_be_bytes());
278 }
279
280 #[test]
281 fn common_strings_are_offsets_with_the_high_bit() {
282 let common: &[(u32, &[u8])] = &[(0, b"AABB"), (5, b"int")];
283 let b = blob_tree(&tree(), 17, false, Strings::Common, common);
284 let row = &b[8 + 24..8 + 48];
285 assert_eq!(&row[4..8], &0x8000_0005u32.to_le_bytes());
286 let buf = b"Base\0a\0Sub\0s\0UInt8\0b\0c\0";
288 assert_eq!(&b[b.len() - buf.len()..], buf);
289 }
290
291 #[test]
292 fn the_old_format_writes_child_counts_in_pre_order() {
293 let t = tree();
294 assert_eq!(parents(&t), [None, Some(0), Some(0), Some(2), Some(0)]);
295 let b = old_tree(&t, 9, false);
296 assert_eq!(&b[..10], b"Base\0Base\0");
298 assert_eq!(&b[10 + 20..10 + 24], &3i32.to_le_bytes());
299 let v3 = old_tree(&t[..1], 3, false);
301 assert_eq!(v3.len(), 10 + 16);
302 let v2 = old_tree(&t[..1], 2, false);
303 assert_eq!(v2.len(), 10 + 28);
304 let jump = [
307 NodeSpec::new(0, "A", "a"),
308 NodeSpec::new(2, "B", "b"),
309 NodeSpec::new(1, "C", "c"),
310 NodeSpec::new(0, "D", "d"),
311 ];
312 assert_eq!(parents(&jump), [None, Some(0), Some(0), None]);
313 }
314}