nectar_mantaray/
node.rs

1//! Node and Fork types for the mantaray trie.
2
3use std::collections::BTreeMap;
4
5use crate::error::{MantarayError, Result};
6use crate::mode::NodeEntry;
7use crate::obfuscation::ObfuscationKey;
8use crate::{PATH_SEPARATOR, PREFIX_MAX_LEN};
9use bytes::Bytes;
10use nectar_primitives::chunk::{Chunk, ChunkAddress, ContentChunk};
11use nectar_primitives::store::{SyncChunkGet, SyncChunkPut};
12
13/// Inline-only byte buffer for fork prefixes (max 30 bytes).
14///
15/// Always stores data inline — no heap allocation, no branching.
16/// 31 bytes total (1 len + 30 data).
17#[derive(Clone, PartialEq, Eq)]
18pub struct Prefix {
19    len: u8,
20    data: [u8; PREFIX_MAX_LEN],
21}
22
23impl Default for Prefix {
24    #[inline]
25    fn default() -> Self {
26        Self::new()
27    }
28}
29
30impl Prefix {
31    /// Maximum prefix length in bytes (constrained by the fork pre-reference region).
32    pub const MAX_LEN: usize = PREFIX_MAX_LEN;
33
34    /// Create an empty prefix.
35    #[inline]
36    pub const fn new() -> Self {
37        Self {
38            len: 0,
39            data: [0u8; PREFIX_MAX_LEN],
40        }
41    }
42
43    /// Create a prefix from a byte slice. Panics if `src.len() > 30`.
44    #[inline]
45    pub fn from_slice(src: &[u8]) -> Self {
46        debug_assert!(src.len() <= PREFIX_MAX_LEN);
47        let mut data = [0u8; PREFIX_MAX_LEN];
48        data[..src.len()].copy_from_slice(src);
49        Self {
50            len: src.len() as u8,
51            data,
52        }
53    }
54
55    /// Returns the prefix length in bytes.
56    #[inline]
57    pub const fn len(&self) -> usize {
58        self.len as usize
59    }
60
61    /// Returns true if the prefix is empty.
62    #[inline]
63    pub const fn is_empty(&self) -> bool {
64        self.len == 0
65    }
66
67    /// Returns the full 30-byte backing array (zero-padded beyond `len`).
68    #[inline]
69    pub const fn padded_bytes(&self) -> &[u8; PREFIX_MAX_LEN] {
70        &self.data
71    }
72}
73
74impl std::ops::Deref for Prefix {
75    type Target = [u8];
76
77    #[inline]
78    fn deref(&self) -> &[u8] {
79        &self.data[..self.len as usize]
80    }
81}
82
83impl std::fmt::Debug for Prefix {
84    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
85        write!(f, "Prefix({:?})", &**self)
86    }
87}
88
89bitflags::bitflags! {
90    /// Bitflags encoding the kind of a mantaray node.
91    #[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
92    pub struct NodeType: u8 {
93        /// Node stores a value (has an entry).
94        const VALUE = 2;
95        /// Node has child forks.
96        const EDGE = 4;
97        /// Path contains a "/" separator.
98        const PATH_SEPARATOR = 8;
99        /// Node has metadata key-value pairs.
100        const METADATA = 16;
101    }
102}
103
104/// A node in the mantaray trie.
105#[derive(Debug, Clone, PartialEq, Eq)]
106pub struct Node<E: NodeEntry = ChunkAddress> {
107    /// Bitflags encoding the node kind (value, edge, path-separator, metadata).
108    pub(crate) node_type: NodeType,
109    /// XOR obfuscation key for binary serialisation.
110    pub(crate) obfuscation_key: ObfuscationKey,
111    /// Content-addressed reference for this node (None if not yet persisted).
112    pub(crate) reference: Option<ChunkAddress>,
113    /// The typed entry stored at this node (the chunk reference this path maps to).
114    pub(crate) entry: Option<E>,
115    /// Metadata key-value pairs attached to this node.
116    pub(crate) metadata: BTreeMap<String, String>,
117    /// Child forks keyed by the first byte of their prefix.
118    pub(crate) forks: BTreeMap<u8, Fork<E>>,
119    /// Whether this node's forks have been loaded from storage.
120    pub(crate) loaded: bool,
121}
122
123impl<E: NodeEntry> Default for Node<E> {
124    fn default() -> Self {
125        Self {
126            node_type: NodeType::empty(),
127            obfuscation_key: ObfuscationKey::ZERO,
128            reference: None,
129            entry: None,
130            metadata: BTreeMap::new(),
131            forks: BTreeMap::new(),
132            loaded: false,
133        }
134    }
135}
136
137/// A fork in the mantaray trie, consisting of a prefix and a child node.
138#[derive(Debug, Clone, PartialEq, Eq)]
139pub struct Fork<E: NodeEntry = ChunkAddress> {
140    /// Inline-only prefix (max 30 bytes). No heap allocation, no branching.
141    pub(crate) prefix: Prefix,
142    /// The child node.
143    pub(crate) node: Node<E>,
144}
145
146impl<E: NodeEntry> Default for Fork<E> {
147    fn default() -> Self {
148        Self {
149            prefix: Prefix::new(),
150            node: Node::default(),
151        }
152    }
153}
154
155impl<E: NodeEntry> Fork<E> {
156    /// The prefix bytes for this fork edge.
157    pub fn prefix(&self) -> &[u8] {
158        &self.prefix
159    }
160
161    /// The child node.
162    pub const fn node(&self) -> &Node<E> {
163        &self.node
164    }
165
166    /// Mutable access to the child node.
167    pub const fn node_mut(&mut self) -> &mut Node<E> {
168        &mut self.node
169    }
170}
171
172/// Return the length of the common prefix of two byte slices.
173fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
174    a.iter().zip(b.iter()).take_while(|(x, y)| x == y).count()
175}
176
177impl<E: NodeEntry> Node<E> {
178    /// Create a new node with a zeroed obfuscation key (unencrypted).
179    pub fn new_unencrypted() -> Self {
180        Self {
181            obfuscation_key: ObfuscationKey::ZERO,
182            ..Default::default()
183        }
184    }
185
186    /// Create a node that references persisted data.
187    pub fn from_reference(reference: ChunkAddress) -> Self {
188        Self {
189            reference: Some(reference),
190            ..Default::default()
191        }
192    }
193
194    /// The typed entry stored at this node.
195    pub const fn entry(&self) -> Option<&E> {
196        self.entry.as_ref()
197    }
198
199    /// Metadata key-value pairs attached to this node.
200    pub const fn metadata(&self) -> &BTreeMap<String, String> {
201        &self.metadata
202    }
203
204    /// Mutable access to metadata for in-place modification.
205    pub(crate) const fn metadata_mut(&mut self) -> &mut BTreeMap<String, String> {
206        &mut self.metadata
207    }
208
209    /// Content-addressed reference for this node.
210    pub const fn reference(&self) -> Option<&ChunkAddress> {
211        self.reference.as_ref()
212    }
213
214    /// Child forks keyed by the first byte of their prefix.
215    pub const fn forks(&self) -> &BTreeMap<u8, Fork<E>> {
216        &self.forks
217    }
218
219    /// XOR obfuscation key for binary serialisation.
220    pub const fn obfuscation_key(&self) -> &ObfuscationKey {
221        &self.obfuscation_key
222    }
223
224    /// Check if the node has a value (entry).
225    pub const fn is_value(&self) -> bool {
226        self.node_type.contains(NodeType::VALUE)
227    }
228
229    /// Set the value flag.
230    pub(crate) const fn make_value(&mut self) {
231        self.node_type = self.node_type.union(NodeType::VALUE);
232    }
233
234    /// Check if the node has child forks.
235    pub const fn is_edge(&self) -> bool {
236        self.node_type.contains(NodeType::EDGE)
237    }
238
239    /// Set the edge flag.
240    pub(crate) const fn make_edge(&mut self) {
241        self.node_type = self.node_type.union(NodeType::EDGE);
242    }
243
244    /// Check if the path contains a separator.
245    pub const fn is_with_path_separator(&self) -> bool {
246        self.node_type.contains(NodeType::PATH_SEPARATOR)
247    }
248
249    /// Check if the node has metadata.
250    pub const fn is_with_metadata(&self) -> bool {
251        self.node_type.contains(NodeType::METADATA)
252    }
253
254    /// Set the metadata flag.
255    pub(crate) const fn make_with_metadata(&mut self) {
256        self.node_type = self.node_type.union(NodeType::METADATA);
257    }
258
259    fn update_is_with_path_separator(&mut self, path: &[u8]) {
260        let sep = PATH_SEPARATOR.as_bytes()[0];
261        if path.iter().skip(1).any(|&b| b == sep) {
262            self.node_type = self.node_type.union(NodeType::PATH_SEPARATOR);
263        } else {
264            self.node_type = self.node_type.difference(NodeType::PATH_SEPARATOR);
265        }
266    }
267
268    /// Clear persisted reference, marking this node for re-serialization on next save.
269    pub(crate) const fn mark_dirty(&mut self) {
270        self.reference = None;
271    }
272
273    /// Load forks from storage if the node hasn't been loaded yet.
274    fn ensure_loaded<S: SyncChunkGet<BS>, const BS: usize>(&mut self, store: &S) -> Result<()> {
275        if !self.loaded {
276            self.load(store)?;
277        }
278        Ok(())
279    }
280
281    /// Load this node from storage by its reference.
282    pub(crate) fn load<S: SyncChunkGet<BS>, const BS: usize>(&mut self, store: &S) -> Result<()> {
283        let address = match self.reference {
284            Some(addr) => addr,
285            None => {
286                self.loaded = true;
287                return Ok(());
288            }
289        };
290
291        let chunk = store.get(&address).map_err(|e| MantarayError::StoreGet {
292            source: std::sync::Arc::new(e),
293        })?;
294        let mut loaded = Self::try_from(chunk.data().as_ref())?;
295        loaded.reference = Some(address);
296        // Preserve fields that live in the parent's fork data, not in this node's chunk:
297        // node_type flags and metadata key-value pairs.
298        loaded.node_type |= self.node_type;
299        loaded.metadata = core::mem::take(&mut self.metadata);
300        *self = loaded;
301        Ok(())
302    }
303
304    /// Look up the node at the given path, loading from storage as needed.
305    pub(crate) fn lookup_node<S: SyncChunkGet<BS>, const BS: usize>(
306        &mut self,
307        path: &[u8],
308        store: &S,
309    ) -> Result<&mut Self> {
310        self.ensure_loaded(store)?;
311
312        if path.is_empty() {
313            return Ok(self);
314        }
315
316        let first = path[0];
317        let fork = self
318            .forks
319            .get_mut(&first)
320            .ok_or_else(|| MantarayError::NoForkFound {
321                reference: self.reference,
322            })?;
323
324        let c = common_prefix_len(&fork.prefix, path);
325        if c == fork.prefix.len() {
326            fork.node.lookup_node(&path[c..], store)
327        } else {
328            Err(MantarayError::NoForkFound {
329                reference: self.reference,
330            })
331        }
332    }
333
334    /// Look up the entry at the given path, loading from storage as needed.
335    #[cfg(test)]
336    pub(crate) fn lookup<S: SyncChunkGet<BS>, const BS: usize>(
337        &mut self,
338        path: &[u8],
339        store: &S,
340    ) -> Result<Option<&E>> {
341        let node = self.lookup_node(path, store)?;
342        if !node.is_value() && !path.is_empty() {
343            return Err(MantarayError::NoEntryFound {
344                reference: node.reference,
345            });
346        }
347        Ok(node.entry.as_ref())
348    }
349
350    /// Add an entry at the given path with optional metadata, loading from storage as needed.
351    pub(crate) fn add<S: SyncChunkGet<BS>, const BS: usize>(
352        &mut self,
353        path: &[u8],
354        entry: Option<E>,
355        metadata: BTreeMap<String, String>,
356        store: &S,
357    ) -> Result<()> {
358        // empty path — set this node as a value
359        if path.is_empty() {
360            self.entry = entry;
361            self.make_value();
362
363            if !metadata.is_empty() {
364                self.metadata = metadata;
365                self.make_with_metadata();
366            }
367
368            self.mark_dirty();
369            return Ok(());
370        }
371
372        // load forks if needed
373        if !self.loaded {
374            self.load(store)?;
375            self.mark_dirty();
376        }
377
378        if !self.forks.contains_key(&path[0]) {
379            // no existing fork for this byte — create a new one
380            let mut nn = Self {
381                obfuscation_key: self.obfuscation_key,
382                ..Default::default()
383            };
384
385            if path.len() > PREFIX_MAX_LEN {
386                let (prefix, rest) = path.split_at(PREFIX_MAX_LEN);
387                nn.add(rest, entry, metadata, store)?;
388                nn.update_is_with_path_separator(prefix);
389                self.forks.insert(
390                    path[0],
391                    Fork {
392                        prefix: Prefix::from_slice(prefix),
393                        node: nn,
394                    },
395                );
396                self.make_edge();
397                return Ok(());
398            }
399
400            nn.entry = entry;
401            if !metadata.is_empty() {
402                nn.metadata = metadata;
403                nn.make_with_metadata();
404            }
405            nn.make_value();
406            nn.update_is_with_path_separator(path);
407
408            self.forks.insert(
409                path[0],
410                Fork {
411                    prefix: Prefix::from_slice(path),
412                    node: nn,
413                },
414            );
415            self.make_edge();
416            return Ok(());
417        }
418
419        // existing fork — need to split or extend
420        let fork = self.forks.get(&path[0]).expect("checked above");
421        let c = common_prefix_len(&fork.prefix, path);
422        let rest = Prefix::from_slice(&fork.prefix[c..]);
423        let common_prefix = Prefix::from_slice(&fork.prefix[..c]);
424
425        // Take ownership — avoids cloning the entire node subtree
426        let old_fork = self.forks.remove(&path[0]).expect("checked above");
427
428        let mut nn = if rest.is_empty() {
429            old_fork.node
430        } else {
431            // split: create intermediate node
432            let mut intermediate = Self {
433                obfuscation_key: self.obfuscation_key,
434                ..Default::default()
435            };
436
437            let mut old_fork_node = old_fork.node;
438            old_fork_node.update_is_with_path_separator(&rest);
439            intermediate.forks.insert(
440                rest[0],
441                Fork {
442                    prefix: rest,
443                    node: old_fork_node,
444                },
445            );
446            intermediate.make_edge();
447
448            if c == path.len() {
449                intermediate.make_value();
450            }
451            intermediate
452        };
453
454        nn.update_is_with_path_separator(path);
455        nn.add(&path[c..], entry, metadata, store)?;
456
457        self.forks.insert(
458            path[0],
459            Fork {
460                prefix: common_prefix,
461                node: nn,
462            },
463        );
464        self.make_edge();
465
466        Ok(())
467    }
468
469    /// Remove the entry at the given path, loading from storage as needed.
470    pub(crate) fn remove<S: SyncChunkGet<BS>, const BS: usize>(
471        &mut self,
472        path: &[u8],
473        store: &S,
474    ) -> Result<()> {
475        if path.is_empty() {
476            return Err(MantarayError::EmptyPath);
477        }
478
479        self.ensure_loaded(store)?;
480
481        let first = path[0];
482
483        // Clone prefix to release the borrow on self.forks
484        let prefix = match self.forks.get(&first) {
485            Some(f) => f.prefix.clone(),
486            None => {
487                return Err(MantarayError::PathPrefixNotFound {
488                    prefix: String::from_utf8_lossy(&[first]).to_string(),
489                });
490            }
491        };
492
493        if !path.starts_with(&prefix) {
494            return Err(MantarayError::PathPrefixNotFound {
495                prefix: String::from_utf8_lossy(path).to_string(),
496            });
497        }
498
499        let rest = &path[prefix.len()..];
500        let result = if rest.is_empty() {
501            self.forks.remove(&first);
502            Ok(())
503        } else {
504            let fork = self.forks.get_mut(&first).expect("checked above");
505            fork.node.remove(rest, store)
506        };
507
508        // Always clear reference so the node gets re-saved (matches Go's defer pattern)
509        self.mark_dirty();
510        result
511    }
512
513    /// Test whether a prefix exists in the trie, loading from storage as needed.
514    pub(crate) fn has_prefix<S: SyncChunkGet<BS>, const BS: usize>(
515        &mut self,
516        path: &[u8],
517        store: &S,
518    ) -> Result<bool> {
519        if path.is_empty() {
520            return Ok(true);
521        }
522
523        self.ensure_loaded(store)?;
524
525        let fork = match self.forks.get_mut(&path[0]) {
526            Some(f) => f,
527            None => return Ok(false),
528        };
529
530        let c = common_prefix_len(&fork.prefix, path);
531
532        if c == fork.prefix.len() {
533            return fork.node.has_prefix(&path[c..], store);
534        }
535
536        if fork.prefix.starts_with(path) {
537            return Ok(true);
538        }
539
540        Ok(false)
541    }
542
543    /// Recursively save this node and all children to storage.
544    ///
545    /// Uses BMT content-addressing via `ContentChunk`.
546    pub(crate) fn save<S: SyncChunkPut<BS>, const BS: usize>(&mut self, store: &S) -> Result<()> {
547        if self.reference.is_some() {
548            return Ok(());
549        }
550
551        for fork in self.forks.values_mut() {
552            fork.node.save(store)?;
553        }
554
555        let data = Vec::<u8>::try_from(&*self)?;
556        let chunk = ContentChunk::<BS>::new(Bytes::from(data))?;
557        let address = *chunk.address();
558        store
559            .put(chunk.into())
560            .map_err(|e| MantarayError::StorePut {
561                source: std::sync::Arc::new(e),
562            })?;
563        self.reference = Some(address);
564        self.forks.clear();
565        self.loaded = false;
566
567        Ok(())
568    }
569
570    /// Walk all nodes depth-first, calling `f` for each node with its path.
571    pub(crate) fn walk<S: SyncChunkGet<BS>, const BS: usize, F>(
572        &mut self,
573        store: &S,
574        f: &mut F,
575    ) -> Result<()>
576    where
577        F: FnMut(&[u8], &Self) -> Result<()>,
578    {
579        let mut path_buf = Vec::new();
580        walk_inner(&mut path_buf, self, store, f)
581    }
582
583    /// Walk the subtree at `root`, calling `f` for each node.
584    pub(crate) fn walk_from<S: SyncChunkGet<BS>, const BS: usize, F>(
585        &mut self,
586        root: &[u8],
587        store: &S,
588        f: &mut F,
589    ) -> Result<()>
590    where
591        F: FnMut(&[u8], &Self) -> Result<()>,
592    {
593        let mut path_buf = root.to_vec();
594        if root.is_empty() {
595            return walk_inner(&mut path_buf, self, store, f);
596        }
597
598        let target = self.lookup_node(root, store)?;
599        walk_inner(&mut path_buf, target, store, f)
600    }
601}
602
603fn walk_inner<E: NodeEntry, S: SyncChunkGet<BS>, const BS: usize, F>(
604    path_buf: &mut Vec<u8>,
605    node: &mut Node<E>,
606    store: &S,
607    f: &mut F,
608) -> Result<()>
609where
610    F: FnMut(&[u8], &Node<E>) -> Result<()>,
611{
612    node.ensure_loaded(store)?;
613
614    f(path_buf, node)?;
615
616    // collect keys to avoid borrow conflict
617    let keys: Vec<u8> = node.forks.keys().copied().collect();
618    for key in keys {
619        let fork = node
620            .forks
621            .get_mut(&key)
622            .ok_or_else(|| MantarayError::NoForkFound {
623                reference: node.reference,
624            })?;
625        let prev_len = path_buf.len();
626        path_buf.extend_from_slice(&fork.prefix);
627        walk_inner(path_buf, &mut fork.node, store, f)?;
628        path_buf.truncate(prev_len);
629    }
630
631    Ok(())
632}
633
634#[cfg(test)]
635mod tests {
636    use super::*;
637    use nectar_primitives::bmt::DEFAULT_BODY_SIZE;
638    use nectar_primitives::store::{MemoryStore, NullLoader};
639
640    struct TestCase {
641        _name: &'static str,
642        items: Vec<&'static str>,
643    }
644
645    #[derive(Default, Clone)]
646    struct RemoveTestCaseItem {
647        path: String,
648        metadata: BTreeMap<String, String>,
649    }
650
651    #[derive(Clone)]
652    struct RemoveTestCase {
653        _name: &'static str,
654        items: Vec<RemoveTestCaseItem>,
655        remove: Vec<String>,
656    }
657
658    #[derive(Clone)]
659    struct HasPrefixTestCase {
660        _name: &'static str,
661        paths: Vec<String>,
662        test_paths: Vec<String>,
663        should_exist: Vec<bool>,
664    }
665
666    fn test_case_data() -> [TestCase; 6] {
667        [
668            TestCase {
669                _name: "a",
670                items: vec![
671                    "aaaaaa", "aaaaab", "abbbb", "abbba", "bbbbba", "bbbaaa", "bbbaab", "aa", "b",
672                ],
673            },
674            TestCase {
675                _name: "simple",
676                items: vec!["/", "index.html", "img/1.png", "img/2.png", "robots.txt"],
677            },
678            TestCase {
679                _name: "nested-value-node-is-recognized",
680                items: vec![
681                    "..............................@",
682                    "..............................",
683                ],
684            },
685            TestCase {
686                _name: "nested-prefix-is-not-collapsed",
687                items: vec![
688                    "index.html",
689                    "img/1.png",
690                    "img/2/test1.png",
691                    "img/2/test2.png",
692                    "robots.txt",
693                ],
694            },
695            TestCase {
696                _name: "conflicting-path",
697                items: vec!["app.js.map", "app.js"],
698            },
699            TestCase {
700                _name: "spa-website",
701                items: vec![
702                    "css/",
703                    "css/app.css",
704                    "favicon.ico",
705                    "img/",
706                    "img/logo.png",
707                    "index.html",
708                    "js/",
709                    "js/chunk-vendors.js.map",
710                    "js/chunk-vendors.js",
711                    "js/app.js.map",
712                    "js/app.js",
713                ],
714            },
715        ]
716    }
717
718    fn remove_test_case_data() -> Vec<RemoveTestCase> {
719        vec![
720            RemoveTestCase {
721                _name: "simple",
722                items: vec![
723                    RemoveTestCaseItem {
724                        path: "/".to_string(),
725                        metadata: serde_json::from_str(r#"{"index-document": "index.html"}"#)
726                            .unwrap(),
727                    },
728                    RemoveTestCaseItem {
729                        path: "index.html".to_string(),
730                        ..Default::default()
731                    },
732                    RemoveTestCaseItem {
733                        path: "img/1.png".to_string(),
734                        ..Default::default()
735                    },
736                    RemoveTestCaseItem {
737                        path: "img/2.png".to_string(),
738                        ..Default::default()
739                    },
740                    RemoveTestCaseItem {
741                        path: "robots.txt".to_string(),
742                        ..Default::default()
743                    },
744                ],
745                remove: vec!["img/2.png".to_string()],
746            },
747            RemoveTestCase {
748                _name: "nested-prefix-is-not-collapsed",
749                items: vec![
750                    RemoveTestCaseItem {
751                        path: "index.html".to_string(),
752                        ..Default::default()
753                    },
754                    RemoveTestCaseItem {
755                        path: "img/1.png".to_string(),
756                        ..Default::default()
757                    },
758                    RemoveTestCaseItem {
759                        path: "img/2/test1.png".to_string(),
760                        ..Default::default()
761                    },
762                    RemoveTestCaseItem {
763                        path: "img/2/test2.png".to_string(),
764                        ..Default::default()
765                    },
766                    RemoveTestCaseItem {
767                        path: "robots.txt".to_string(),
768                        ..Default::default()
769                    },
770                ],
771                remove: vec!["img/2/test1.png".to_string()],
772            },
773        ]
774    }
775
776    fn has_prefix_test_case_data() -> Vec<HasPrefixTestCase> {
777        vec![
778            HasPrefixTestCase {
779                _name: "simple",
780                paths: vec![
781                    "index.html".to_string(),
782                    "img/1.png".to_string(),
783                    "img/2.png".to_string(),
784                    "robots.txt".to_string(),
785                ],
786                test_paths: vec!["img/".to_string(), "images/".to_string()],
787                should_exist: vec![true, false],
788            },
789            HasPrefixTestCase {
790                _name: "nested-single",
791                paths: vec!["some-path/file.ext".to_string()],
792                test_paths: vec![
793                    "some-path".to_string(),
794                    "some-path/file".to_string(),
795                    "some-other-path/".to_string(),
796                ],
797                should_exist: vec![true, true, false],
798            },
799        ]
800    }
801
802    const NL: NullLoader = NullLoader;
803    const BS: usize = DEFAULT_BODY_SIZE;
804
805    /// Create a 32-byte ChunkAddress from a string, left-padded with zeroes.
806    fn make_entry(s: &str) -> ChunkAddress {
807        let bytes = s.as_bytes();
808        let mut buf = [0u8; 32];
809        let start = 32 - bytes.len();
810        buf[start..].copy_from_slice(bytes);
811        ChunkAddress::from(buf)
812    }
813
814    /// In-memory add: delegates to `add` with NullLoader.
815    fn node_add(n: &mut Node, path: &[u8], entry: ChunkAddress, meta: BTreeMap<String, String>) {
816        n.add::<NullLoader, BS>(path, Some(entry), meta, &NL)
817            .unwrap();
818    }
819
820    /// In-memory lookup: delegates to `lookup` with NullLoader.
821    fn node_lookup<'n>(n: &'n mut Node, path: &[u8]) -> Result<Option<&'n ChunkAddress>> {
822        n.lookup::<NullLoader, BS>(path, &NL)
823    }
824
825    /// In-memory lookup_node: delegates to `lookup_node` with NullLoader.
826    fn node_lookup_node<'n>(n: &'n mut Node, path: &[u8]) -> Result<&'n mut Node> {
827        n.lookup_node::<NullLoader, BS>(path, &NL)
828    }
829
830    /// In-memory remove: delegates to `remove` with NullLoader.
831    fn node_remove(n: &mut Node, path: &[u8]) -> Result<()> {
832        n.remove::<NullLoader, BS>(path, &NL)
833    }
834
835    /// In-memory has_prefix: delegates to `has_prefix` with NullLoader.
836    fn node_has_prefix(n: &mut Node, path: &[u8]) -> Result<bool> {
837        n.has_prefix::<NullLoader, BS>(path, &NL)
838    }
839
840    /// In-memory walk: delegates to `walk` with NullLoader.
841    fn node_walk<F>(n: &mut Node, f: &mut F) -> Result<()>
842    where
843        F: FnMut(&[u8], &Node) -> Result<()>,
844    {
845        n.walk::<NullLoader, BS, _>(&NL, f)
846    }
847
848    /// In-memory walk_node: delegates to `walk_from` with NullLoader.
849    fn node_walk_node<F>(n: &mut Node, root: &[u8], f: &mut F) -> Result<()>
850    where
851        F: FnMut(&[u8], &Node) -> Result<()>,
852    {
853        n.walk_from::<NullLoader, BS, _>(root, &NL, f)
854    }
855
856    #[test]
857    fn nil_path() {
858        let mut n = Node::default();
859        assert!(node_lookup(&mut n, b"").is_ok());
860    }
861
862    #[test]
863    fn add_and_lookup() {
864        let mut n = Node::default();
865        let items = &test_case_data()[0].items;
866
867        for (i, c) in items.iter().enumerate() {
868            let e = make_entry(c);
869            node_add(&mut n, c.as_bytes(), e, BTreeMap::new());
870
871            for &d in items.iter().take(i) {
872                let r = node_lookup(&mut n, d.as_bytes()).unwrap();
873                assert_eq!(r, Some(&make_entry(d)));
874            }
875        }
876    }
877
878    fn run_add_and_lookup_node(items: &[&str]) {
879        let mut n = Node::default();
880
881        for (i, c) in items.iter().enumerate() {
882            let e = make_entry(c);
883            node_add(&mut n, c.as_bytes(), e, BTreeMap::new());
884
885            for &d in items.iter().take(i) {
886                let node = node_lookup_node(&mut n, d.as_bytes()).unwrap();
887                assert!(node.is_value());
888                assert_eq!(node.entry(), Some(&make_entry(d)));
889            }
890        }
891    }
892
893    #[test]
894    fn add_and_lookup_node_a() {
895        run_add_and_lookup_node(&test_case_data()[0].items);
896    }
897
898    #[test]
899    fn add_and_lookup_node_simple() {
900        run_add_and_lookup_node(&test_case_data()[1].items);
901    }
902
903    #[test]
904    fn add_and_lookup_node_nested_value() {
905        run_add_and_lookup_node(&test_case_data()[2].items);
906    }
907
908    #[test]
909    fn add_and_lookup_node_nested_prefix() {
910        run_add_and_lookup_node(&test_case_data()[3].items);
911    }
912
913    #[test]
914    fn add_and_lookup_node_conflicting_path() {
915        run_add_and_lookup_node(&test_case_data()[4].items);
916    }
917
918    #[test]
919    fn add_and_lookup_node_spa_website() {
920        run_add_and_lookup_node(&test_case_data()[5].items);
921    }
922
923    fn run_add_and_lookup_with_load_save(items: &[&str]) {
924        let mut n = Node::default();
925
926        for c in items {
927            let e = make_entry(c);
928            node_add(&mut n, c.as_bytes(), e, BTreeMap::new());
929        }
930
931        let store = MemoryStore::<{ DEFAULT_BODY_SIZE }>::new();
932        n.save(&store).unwrap();
933
934        let mut n2: Node = Node::from_reference(n.reference.unwrap());
935
936        for &d in items {
937            let node = n2.lookup_node(d.as_bytes(), &store).unwrap();
938            assert!(node.is_value());
939            assert_eq!(node.entry(), Some(&make_entry(d)));
940        }
941    }
942
943    #[test]
944    fn add_and_lookup_with_load_save_a() {
945        run_add_and_lookup_with_load_save(&test_case_data()[0].items);
946    }
947
948    #[test]
949    fn add_and_lookup_with_load_save_simple() {
950        run_add_and_lookup_with_load_save(&test_case_data()[1].items);
951    }
952
953    #[test]
954    fn add_and_lookup_with_load_save_nested_value() {
955        run_add_and_lookup_with_load_save(&test_case_data()[2].items);
956    }
957
958    #[test]
959    fn add_and_lookup_with_load_save_nested_prefix() {
960        run_add_and_lookup_with_load_save(&test_case_data()[3].items);
961    }
962
963    #[test]
964    fn add_and_lookup_with_load_save_conflicting_path() {
965        run_add_and_lookup_with_load_save(&test_case_data()[4].items);
966    }
967
968    #[test]
969    fn add_and_lookup_with_load_save_spa_website() {
970        run_add_and_lookup_with_load_save(&test_case_data()[5].items);
971    }
972
973    fn run_remove(tc: RemoveTestCase) {
974        let mut n = Node::default();
975
976        for (i, c) in tc.items.iter().enumerate() {
977            let e = make_entry(&c.path);
978            node_add(&mut n, c.path.as_bytes(), e, c.metadata.clone());
979
980            for item in tc.items.iter().take(i) {
981                let r = node_lookup(&mut n, item.path.as_bytes()).unwrap();
982                assert_eq!(r, Some(&make_entry(&item.path)));
983            }
984        }
985
986        for c in &tc.remove {
987            node_remove(&mut n, c.as_bytes()).unwrap();
988            assert!(node_lookup(&mut n, c.as_bytes()).is_err());
989        }
990    }
991
992    #[test]
993    fn remove_simple() {
994        run_remove(remove_test_case_data()[0].clone());
995    }
996
997    #[test]
998    fn remove_nested_prefix() {
999        run_remove(remove_test_case_data()[1].clone());
1000    }
1001
1002    fn run_has_prefix(tc: HasPrefixTestCase) {
1003        let mut n = Node::default();
1004
1005        for c in &tc.paths {
1006            let e = make_entry(c);
1007            node_add(&mut n, c.as_bytes(), e, BTreeMap::default());
1008        }
1009
1010        for (i, test_prefix) in tc.test_paths.iter().enumerate() {
1011            assert_eq!(
1012                node_has_prefix(&mut n, test_prefix.as_bytes()).unwrap(),
1013                tc.should_exist[i],
1014            );
1015        }
1016    }
1017
1018    #[test]
1019    fn has_prefix_simple() {
1020        run_has_prefix(has_prefix_test_case_data()[0].clone());
1021    }
1022
1023    #[test]
1024    fn has_prefix_nested_single() {
1025        run_has_prefix(has_prefix_test_case_data()[1].clone());
1026    }
1027
1028    // Tests save->reload->remove->save->reload->verify-removed cycle.
1029
1030    fn run_persist_remove(tc: RemoveTestCase) {
1031        let store = MemoryStore::<{ DEFAULT_BODY_SIZE }>::new();
1032
1033        // add entries and persist
1034        let mut n = Node::default();
1035        for c in &tc.items {
1036            let e = make_entry(&c.path);
1037            n.add(c.path.as_bytes(), Some(e), c.metadata.clone(), &store)
1038                .unwrap();
1039        }
1040        n.save(&store).unwrap();
1041        let ref_ = n.reference.unwrap();
1042
1043        // reload and remove
1044        let mut nn: Node = Node::from_reference(ref_);
1045        for path in &tc.remove {
1046            nn.remove(path.as_bytes(), &store).unwrap();
1047        }
1048        nn.save(&store).unwrap();
1049        let ref2 = nn.reference.unwrap();
1050
1051        // reload and verify removed paths are gone
1052        let mut nnn: Node = Node::from_reference(ref2);
1053        for path in &tc.remove {
1054            let result = nnn.lookup_node(path.as_bytes(), &store);
1055            assert!(
1056                result.is_err(),
1057                "expected removed path '{path}' to be not found"
1058            );
1059        }
1060    }
1061
1062    #[test]
1063    fn persist_remove_simple() {
1064        run_persist_remove(remove_test_case_data()[0].clone());
1065    }
1066
1067    #[test]
1068    fn persist_remove_nested_prefix() {
1069        run_persist_remove(remove_test_case_data()[1].clone());
1070    }
1071
1072    fn make_entry_bytes(s: &[u8]) -> ChunkAddress {
1073        let mut buf = [0u8; 32];
1074        let start = 32 - s.len();
1075        buf[start..].copy_from_slice(s);
1076        ChunkAddress::from(buf)
1077    }
1078
1079    #[test]
1080    fn walk_visits_all_nodes() {
1081        let mut root = Node::default();
1082
1083        let paths = &["index.html", "img/1.png", "img/2.png", "robots.txt"];
1084        for &p in paths {
1085            let entry = make_entry_bytes(p.as_bytes());
1086            node_add(&mut root, p.as_bytes(), entry, BTreeMap::new());
1087        }
1088
1089        let mut visited: Vec<(Vec<u8>, bool)> = Vec::new();
1090        node_walk(&mut root, &mut |path, node| {
1091            visited.push((path.to_vec(), node.is_value()));
1092            Ok(())
1093        })
1094        .unwrap();
1095
1096        for &p in paths {
1097            assert!(
1098                visited
1099                    .iter()
1100                    .any(|(vp, is_val)| vp == p.as_bytes() && *is_val),
1101                "path {p} not visited as value"
1102            );
1103        }
1104    }
1105
1106    #[test]
1107    fn walk_node_exact_order() {
1108        let to_add: &[&[u8]] = &[
1109            b"index.html.backup",
1110            b"index.html",
1111            b"img/test/oho.png",
1112            b"img/test/old/test.png.backup",
1113            b"img/test/old/test.png",
1114            b"img/2.png",
1115            b"img/1.png",
1116            b"robots.txt",
1117        ];
1118
1119        let expected: &[&[u8]] = &[
1120            b"",
1121            b"i",
1122            b"img/",
1123            b"img/1.png",
1124            b"img/2.png",
1125            b"img/test/o",
1126            b"img/test/oho.png",
1127            b"img/test/old/test.png",
1128            b"img/test/old/test.png.backup",
1129            b"index.html",
1130            b"index.html.backup",
1131            b"robots.txt",
1132        ];
1133
1134        let mut n = Node::default();
1135        for &path in to_add {
1136            let entry = make_entry_bytes(path);
1137            node_add(&mut n, path, entry, BTreeMap::new());
1138        }
1139
1140        let mut walked: Vec<Vec<u8>> = Vec::new();
1141        node_walk_node(&mut n, b"", &mut |path, _node| {
1142            walked.push(path.to_vec());
1143            Ok(())
1144        })
1145        .unwrap();
1146
1147        assert_eq!(
1148            walked.len(),
1149            expected.len(),
1150            "expected {} nodes, got {}",
1151            expected.len(),
1152            walked.len()
1153        );
1154
1155        for (i, (got, &want)) in walked.iter().zip(expected.iter()).enumerate() {
1156            assert_eq!(
1157                got.as_slice(),
1158                want,
1159                "walk step {i}: expected {:?}, got {:?}",
1160                core::str::from_utf8(want).unwrap_or("<non-utf8>"),
1161                core::str::from_utf8(got).unwrap_or("<non-utf8>"),
1162            );
1163        }
1164    }
1165
1166    #[test]
1167    fn walk_node_from_subtree() {
1168        let to_add: &[&[u8]] = &[b"index.html", b"img/1.png", b"img/2.png", b"robots.txt"];
1169
1170        let mut n = Node::default();
1171        for &path in to_add {
1172            let entry = make_entry_bytes(path);
1173            node_add(&mut n, path, entry, BTreeMap::new());
1174        }
1175
1176        let mut walked: Vec<Vec<u8>> = Vec::new();
1177        node_walk_node(&mut n, b"img/", &mut |path, _node| {
1178            walked.push(path.to_vec());
1179            Ok(())
1180        })
1181        .unwrap();
1182
1183        assert!(walked.iter().any(|p| p == b"img/1.png"));
1184        assert!(walked.iter().any(|p| p == b"img/2.png"));
1185        assert!(!walked.iter().any(|p| p == b"index.html"));
1186        assert!(!walked.iter().any(|p| p == b"robots.txt"));
1187    }
1188
1189    #[test]
1190    fn walk_node_exact_order_with_load_save() {
1191        let to_add: &[&[u8]] = &[
1192            b"index.html.backup",
1193            b"index.html",
1194            b"img/test/oho.png",
1195            b"img/test/old/test.png.backup",
1196            b"img/test/old/test.png",
1197            b"img/2.png",
1198            b"img/1.png",
1199            b"robots.txt",
1200        ];
1201
1202        let expected: &[&[u8]] = &[
1203            b"",
1204            b"i",
1205            b"img/",
1206            b"img/1.png",
1207            b"img/2.png",
1208            b"img/test/o",
1209            b"img/test/oho.png",
1210            b"img/test/old/test.png",
1211            b"img/test/old/test.png.backup",
1212            b"index.html",
1213            b"index.html.backup",
1214            b"robots.txt",
1215        ];
1216
1217        let mut n = Node::default();
1218        for &path in to_add {
1219            let entry = make_entry_bytes(path);
1220            node_add(&mut n, path, entry, BTreeMap::new());
1221        }
1222
1223        let store = MemoryStore::<{ DEFAULT_BODY_SIZE }>::new();
1224        n.save(&store).unwrap();
1225
1226        let mut n2: Node = Node::from_reference(n.reference.unwrap());
1227
1228        let mut walked: Vec<Vec<u8>> = Vec::new();
1229        n2.walk_from(b"", &store, &mut |path: &[u8], _node: &Node| {
1230            walked.push(path.to_vec());
1231            Ok(())
1232        })
1233        .unwrap();
1234
1235        assert_eq!(
1236            walked.len(),
1237            expected.len(),
1238            "expected {} nodes, got {}",
1239            expected.len(),
1240            walked.len()
1241        );
1242
1243        for (i, (got, &want)) in walked.iter().zip(expected.iter()).enumerate() {
1244            assert_eq!(
1245                got.as_slice(),
1246                want,
1247                "walk step {i}: expected {:?}, got {:?}",
1248                core::str::from_utf8(want).unwrap_or("<non-utf8>"),
1249                core::str::from_utf8(got).unwrap_or("<non-utf8>"),
1250            );
1251        }
1252    }
1253}
nectar_mantaray/node.rs

nectar_mantaray/
node.rs
