Skip to main content

raf_source/tree/
memory.rs

1// SPDX-FileCopyrightText: 2026 Blackcat InformaticsĀ® Inc. <paudley@blackcatinformatics.ca>
2// SPDX-License-Identifier: MIT OR Apache-2.0 OR MulanPSL-2.0
3
4//! A tree that lives in memory, for fixtures that need no disk.
5
6use std::collections::BTreeMap;
7
8use super::{Entry, EntryKind, FileId, Opened, Tree};
9use crate::error::TreeError;
10use crate::path::RelPath;
11
12/// Why a set of keys is not a tree.
13#[derive(Debug, Clone, PartialEq, Eq)]
14enum Fault {
15    /// A key is absolute or climbs above the root.
16    Outside { key: String },
17    /// A key is a file and also a directory holding other keys.
18    FileAsDirectory { key: String },
19    /// A key names a path that an earlier key already holds.
20    Duplicate { key: String },
21}
22
23impl Fault {
24    fn to_error(&self) -> TreeError {
25        match self {
26            Self::Outside { key } => TreeError::OutsideRoot { path: key.clone() },
27            Self::FileAsDirectory { key } => TreeError::NotRegular { path: key.clone() },
28            Self::Duplicate { key } => TreeError::DuplicatePath { path: key.clone() },
29        }
30    }
31}
32
33/// A tree of files held in memory: a map of path to text.
34///
35/// Directories are inferred from the keys. There are no symlinks and no
36/// special files. A key is normalised like a [`RelPath`], and a `..` segment
37/// is applied to the keys' own directories.
38///
39/// [`MemoryTree::try_from_iter`] refuses a bad key with a [`TreeError`]. The
40/// infallible `From` and `FromIterator` conversions cannot return one, so a
41/// tree built from a bad key reports that same error from every call and
42/// never serves a partial tree.
43#[derive(Debug, Clone, Default, PartialEq, Eq)]
44pub struct MemoryTree {
45    // OrderedTable::try_clone requires admission-owned storage and shallow
46    // allocation-free payload clones. This existing backend instead exposes
47    // infallible Clone/Eq over owned strings; retaining its sorted map preserves
48    // that contract without hiding a native allocation refusal.
49    files: BTreeMap<String, String>,
50    fault: Option<Fault>,
51}
52
53/// The lexical form of a path: `..` applied against its own segments.
54fn collapse(path: &RelPath) -> String {
55    let mut kept: Vec<&str> = Vec::new();
56    for segment in path.segments() {
57        if segment == ".." {
58            kept.pop();
59        } else {
60            kept.push(segment);
61        }
62    }
63    kept.join("/")
64}
65
66impl MemoryTree {
67    /// Create a file exclusively, inferring its directories as for construction.
68    ///
69    /// # Errors
70    /// Returns the tree's original construction fault, `WrongAuthority` for a
71    /// foreign path, `DuplicatePath` for an existing file, or `NotRegular` for
72    /// a directory destination or a file used as an ancestor. Refusal changes
73    /// nothing. File identities remain the normalised keys.
74    pub fn create_new(&mut self, path: &RelPath, text: String) -> Result<(), TreeError> {
75        super::require_first_party(path)?;
76        self.check()?;
77        let key = collapse(path);
78        self.check_ancestors(&key)?;
79        if self.files.contains_key(&key) {
80            return Err(TreeError::DuplicatePath { path: key });
81        }
82        if self.is_directory(&key) {
83            return Err(TreeError::NotRegular { path: key });
84        }
85        self.files.insert(key, text);
86        Ok(())
87    }
88
89    fn check_ancestors(&self, key: &str) -> Result<(), TreeError> {
90        if !key.is_empty() && self.files.contains_key("") {
91            return Err(TreeError::NotRegular {
92                path: String::new(),
93            });
94        }
95        let mut ancestor = key;
96        while let Some((parent, _)) = ancestor.rsplit_once('/') {
97            if self.files.contains_key(parent) {
98                return Err(TreeError::NotRegular {
99                    path: parent.to_owned(),
100                });
101            }
102            ancestor = parent;
103        }
104        Ok(())
105    }
106
107    /// Replace an existing regular file as one change, preserving its identity.
108    ///
109    /// # Errors
110    /// As [`MemoryTree::create_new`], except a missing file is `NotFound` and
111    /// an existing file is required. Refusal preserves the entire tree.
112    pub fn replace(&mut self, path: &RelPath, text: String) -> Result<(), TreeError> {
113        super::require_first_party(path)?;
114        self.check()?;
115        let key = collapse(path);
116        self.check_ancestors(&key)?;
117        let Some(previous) = self.files.get_mut(&key) else {
118            return Err(if self.is_directory(&key) {
119                TreeError::NotRegular { path: key }
120            } else {
121                TreeError::NotFound { path: key }
122            });
123        };
124        *previous = text;
125        Ok(())
126    }
127
128    /// Build a tree from `(path, text)` pairs.
129    ///
130    /// # Errors
131    ///
132    /// Returns [`TreeError::OutsideRoot`] naming a key that is absolute or
133    /// climbs above the root, and [`TreeError::NotRegular`] naming a key that
134    /// is a file and also holds other keys below it, and
135    /// [`TreeError::DuplicatePath`] naming a key whose normalised path an
136    /// earlier key already holds.
137    pub fn try_from_iter<I, K, V>(entries: I) -> Result<Self, TreeError>
138    where
139        I: IntoIterator<Item = (K, V)>,
140        K: AsRef<str>,
141        V: Into<String>,
142    {
143        Self::build(entries).map_err(|fault| fault.to_error())
144    }
145
146    fn build<I, K, V>(entries: I) -> Result<Self, Fault>
147    where
148        I: IntoIterator<Item = (K, V)>,
149        K: AsRef<str>,
150        V: Into<String>,
151    {
152        let mut files = BTreeMap::new();
153        for (key, text) in entries {
154            let key = key.as_ref();
155            let path = RelPath::new(key).map_err(|_| Fault::Outside {
156                key: key.to_owned(),
157            })?;
158            if files.insert(collapse(&path), text.into()).is_some() {
159                return Err(Fault::Duplicate {
160                    key: key.to_owned(),
161                });
162            }
163        }
164        for key in files.keys() {
165            let mut prefix = String::new();
166            for segment in key.split('/') {
167                if !prefix.is_empty() {
168                    prefix.push('/');
169                }
170                prefix.push_str(segment);
171                if prefix != *key && files.contains_key(&prefix) {
172                    return Err(Fault::FileAsDirectory { key: prefix });
173                }
174            }
175        }
176        Ok(Self { files, fault: None })
177    }
178
179    fn check(&self) -> Result<(), TreeError> {
180        self.fault
181            .as_ref()
182            .map_or(Ok(()), |fault| Err(fault.to_error()))
183    }
184
185    /// True when some key lies below `directory` (the root when empty).
186    fn is_directory(&self, directory: &str) -> bool {
187        directory.is_empty() || self.keys_below(directory).next().is_some()
188    }
189
190    fn keys_below<'a>(&'a self, directory: &'a str) -> impl Iterator<Item = &'a str> {
191        self.files.keys().filter_map(move |key| {
192            if directory.is_empty() {
193                Some(key.as_str())
194            } else {
195                key.strip_prefix(directory)
196                    .and_then(|rest| rest.strip_prefix('/'))
197            }
198        })
199    }
200}
201
202impl<K: AsRef<str>, V: Into<String>> FromIterator<(K, V)> for MemoryTree {
203    fn from_iter<I: IntoIterator<Item = (K, V)>>(entries: I) -> Self {
204        match Self::build(entries) {
205            Ok(tree) => tree,
206            Err(fault) => Self {
207                files: BTreeMap::new(),
208                fault: Some(fault),
209            },
210        }
211    }
212}
213
214impl<const N: usize> From<[(&str, &str); N]> for MemoryTree {
215    fn from(entries: [(&str, &str); N]) -> Self {
216        entries.into_iter().collect()
217    }
218}
219
220impl Tree for MemoryTree {
221    fn read(&self, path: &RelPath, max_bytes: u64) -> Result<String, TreeError> {
222        super::require_first_party(path)?;
223        self.check()?;
224        let key = collapse(path);
225        match self.files.get(&key) {
226            Some(text) => {
227                if u64::try_from(text.len()).map_or(true, |len| len > max_bytes) {
228                    Err(TreeError::TooLarge {
229                        path: path.to_string(),
230                        limit: max_bytes,
231                    })
232                } else {
233                    Ok(text.clone())
234                }
235            }
236            None if self.is_directory(&key) => Err(TreeError::NotRegular {
237                path: path.to_string(),
238            }),
239            None => Err(TreeError::NotFound {
240                path: path.to_string(),
241            }),
242        }
243    }
244
245    /// The memory tree holds text, so its bytes are the UTF-8 of that text.
246    fn read_bytes(&self, path: &RelPath, max_bytes: u64) -> Result<Vec<u8>, TreeError> {
247        self.read(path, max_bytes).map(String::into_bytes)
248    }
249
250    fn read_unseen(
251        &self,
252        path: &RelPath,
253        max_bytes: u64,
254        seen: &dyn Fn(&FileId) -> bool,
255    ) -> Result<Opened, TreeError> {
256        super::require_first_party(path)?;
257        self.check()?;
258        let key = collapse(path);
259        if self.files.contains_key(&key) {
260            let id = FileId::from_key(&key);
261            if seen(&id) {
262                return Ok(Opened::Seen(id));
263            }
264            Ok(Opened::Read {
265                id,
266                text: self.read(path, max_bytes)?,
267            })
268        } else if self.is_directory(&key) {
269            Err(TreeError::NotRegular {
270                path: path.to_string(),
271            })
272        } else {
273            Err(TreeError::NotFound {
274                path: path.to_string(),
275            })
276        }
277    }
278
279    fn list(&self, path: &RelPath) -> Result<Vec<Entry>, TreeError> {
280        super::require_first_party(path)?;
281        self.check()?;
282        let key = collapse(path);
283        if self.files.contains_key(&key) {
284            return Err(TreeError::NotRegular {
285                path: path.to_string(),
286            });
287        }
288        if !self.is_directory(&key) {
289            return Err(TreeError::NotFound {
290                path: path.to_string(),
291            });
292        }
293        let mut found: BTreeMap<&str, EntryKind> = BTreeMap::new();
294        for rest in self.keys_below(&key) {
295            match rest.split_once('/') {
296                Some((name, _)) => found.insert(name, EntryKind::Dir),
297                None => found.insert(rest, EntryKind::File),
298            };
299        }
300        Ok(found
301            .into_iter()
302            .map(|(name, kind)| Entry {
303                name: name.to_owned(),
304                kind,
305            })
306            .collect())
307    }
308
309    fn entry(&self, path: &RelPath) -> Result<Option<EntryKind>, TreeError> {
310        super::require_first_party(path)?;
311        self.check()?;
312        let key = collapse(path);
313        if self.files.contains_key(&key) {
314            Ok(Some(EntryKind::File))
315        } else if self.is_directory(&key) {
316            Ok(Some(EntryKind::Dir))
317        } else {
318            Ok(None)
319        }
320    }
321}