grove
grove/src/objects.rs
at @10
1//! Objects: file contents (blobs) and directories (trees), stored by the hash of their bytes.
2//!
3//! An object's file holds exactly the bytes its id is the hash of: a type prefix
4//! (`grove blob\0` or `grove tree\0`) and the content. So any object can be checked by hashing
5//! its file, and a blob and a tree can never share an id.
6//!
7//! Writing: temporary file, flush, rename into place, flush the directory. An object either
8//! exists completely or not at all, and is never rewritten.
9
10use crate::blake3::Hasher;
11use crate::hex;
12use crate::log::sync_parent;
13use std::fs::{self, File};
14use std::io::{self, Write};
15use std::path::{Path, PathBuf};
16
17pub type Id = [u8; 32];
18
19const BLOB: &[u8] = b"grove blob\0";
20const TREE: &[u8] = b"grove tree\0";
21
22#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
23pub enum Kind {
24 File,
25 Exec,
26 Link,
27 Dir,
28}
29
30impl Kind {
31 fn byte(self) -> u8 {
32 match self {
33 Kind::File => b'f',
34 Kind::Exec => b'x',
35 Kind::Link => b'l',
36 Kind::Dir => b'd',
37 }
38 }
39 fn from_byte(b: u8) -> Option<Kind> {
40 Some(match b {
41 b'f' => Kind::File,
42 b'x' => Kind::Exec,
43 b'l' => Kind::Link,
44 b'd' => Kind::Dir,
45 _ => return None,
46 })
47 }
48}
49
50#[derive(Clone, Debug, PartialEq, Eq)]
51pub struct Entry {
52 pub name: String,
53 pub kind: Kind,
54 pub id: Id,
55}
56
57#[derive(Debug)]
58pub enum Error {
59 Io(io::Error),
60 Missing(Id),
61 Corrupt(Id),
62 BadName(String),
63}
64
65impl std::fmt::Display for Error {
66 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
67 match self {
68 Error::Io(e) => write!(f, "{e}"),
69 Error::Missing(id) => write!(f, "object {} is missing", hex::encode(id)),
70 Error::Corrupt(id) => write!(f, "object {} is corrupt", hex::encode(id)),
71 Error::BadName(n) => write!(f, "invalid file name {n:?}"),
72 }
73 }
74}
75
76impl From<io::Error> for Error {
77 fn from(e: io::Error) -> Self {
78 Error::Io(e)
79 }
80}
81
82pub type Result<T> = std::result::Result<T, Error>;
83
84/// Names must be usable as one path component everywhere.
85pub fn valid_name(name: &str) -> bool {
86 !name.is_empty() && name != "." && name != ".." && !name.contains('/') && !name.contains('\0')
87}
88
89fn id_of(prefix: &[u8], content: &[u8]) -> Id {
90 let mut h = Hasher::new();
91 h.update(prefix).update(content);
92 h.finalize()
93}
94
95pub fn blob_id(content: &[u8]) -> Id {
96 id_of(BLOB, content)
97}
98
99/// Canonical tree bytes: entries sorted by name, each `kind, name length (u32 LE), name, id`.
100pub fn encode_tree(entries: &[Entry]) -> Result<Vec<u8>> {
101 let mut sorted: Vec<&Entry> = entries.iter().collect();
102 sorted.sort_by(|a, b| a.name.as_bytes().cmp(b.name.as_bytes()));
103 let mut out = Vec::new();
104 for (i, e) in sorted.iter().enumerate() {
105 if !valid_name(&e.name) {
106 return Err(Error::BadName(e.name.clone()));
107 }
108 if i > 0 && sorted[i - 1].name == e.name {
109 return Err(Error::BadName(format!("{} (twice)", e.name)));
110 }
111 out.push(e.kind.byte());
112 out.extend_from_slice(&(e.name.len() as u32).to_le_bytes());
113 out.extend_from_slice(e.name.as_bytes());
114 out.extend_from_slice(&e.id);
115 }
116 Ok(out)
117}
118
119fn decode_tree(id: &Id, mut bytes: &[u8]) -> Result<Vec<Entry>> {
120 let corrupt = || Error::Corrupt(*id);
121 let mut entries = Vec::new();
122 while !bytes.is_empty() {
123 let kind = Kind::from_byte(bytes[0]).ok_or_else(corrupt)?;
124 let len = u32::from_le_bytes(bytes.get(1..5).ok_or_else(corrupt)?.try_into().unwrap()) as usize;
125 let name = std::str::from_utf8(bytes.get(5..5 + len).ok_or_else(corrupt)?).map_err(|_| corrupt())?;
126 let id_bytes = bytes.get(5 + len..5 + len + 32).ok_or_else(corrupt)?;
127 entries.push(Entry { name: name.to_string(), kind, id: id_bytes.try_into().unwrap() });
128 bytes = &bytes[5 + len + 32..];
129 }
130 Ok(entries)
131}
132
133pub struct Objects {
134 root: PathBuf,
135}
136
137impl Objects {
138 pub fn open(root: &Path) -> Result<Objects> {
139 fs::create_dir_all(root.join("tmp"))?;
140 Ok(Objects { root: root.to_path_buf() })
141 }
142
143 fn path(&self, id: &Id) -> PathBuf {
144 let h = hex::encode(id);
145 self.root.join(&h[..2]).join(&h[2..])
146 }
147
148 pub fn has(&self, id: &Id) -> bool {
149 self.path(id).is_file()
150 }
151
152 fn put(&self, prefix: &[u8], content: &[u8]) -> Result<Id> {
153 let id = id_of(prefix, content);
154 let path = self.path(&id);
155 if path.is_file() {
156 return Ok(id);
157 }
158 fs::create_dir_all(path.parent().unwrap())?;
159 let tmp = self.root.join("tmp").join(format!("{}-{}", hex::encode(&id[..8]), crate::random::hex(8)));
160 {
161 let mut f = File::create(&tmp)?;
162 f.write_all(prefix)?;
163 f.write_all(content)?;
164 f.sync_all()?;
165 }
166 fs::rename(&tmp, &path)?;
167 sync_parent(&path)?;
168 Ok(id)
169 }
170
171 /// Read an object's content, checking that it hashes to its id.
172 fn get(&self, prefix: &[u8], id: &Id) -> Result<Vec<u8>> {
173 let bytes = match fs::read(self.path(id)) {
174 Ok(b) => b,
175 Err(e) if e.kind() == io::ErrorKind::NotFound => return Err(Error::Missing(*id)),
176 Err(e) => return Err(e.into()),
177 };
178 if !bytes.starts_with(prefix) || crate::blake3::hash(&bytes) != *id {
179 return Err(Error::Corrupt(*id));
180 }
181 Ok(bytes[prefix.len()..].to_vec())
182 }
183
184 pub fn put_blob(&self, content: &[u8]) -> Result<Id> {
185 self.put(BLOB, content)
186 }
187
188 pub fn get_blob(&self, id: &Id) -> Result<Vec<u8>> {
189 self.get(BLOB, id)
190 }
191
192 pub fn put_tree(&self, entries: &[Entry]) -> Result<Id> {
193 self.put(TREE, &encode_tree(entries)?)
194 }
195
196 /// Entries sorted by name.
197 pub fn get_tree(&self, id: &Id) -> Result<Vec<Entry>> {
198 let bytes = self.get(TREE, id)?;
199 decode_tree(id, &bytes)
200 }
201
202 /// The id of an empty tree, stored.
203 pub fn empty_tree(&self) -> Result<Id> {
204 self.put_tree(&[])
205 }
206
207 /// Every file under a tree, as (path, kind, blob id), sorted by path.
208 pub fn flatten(&self, tree: &Id) -> Result<Vec<(String, Kind, Id)>> {
209 let mut out = Vec::new();
210 self.flatten_into(tree, "", &mut out)?;
211 Ok(out)
212 }
213
214 fn flatten_into(&self, tree: &Id, prefix: &str, out: &mut Vec<(String, Kind, Id)>) -> Result<()> {
215 for e in self.get_tree(tree)? {
216 let path = format!("{prefix}{}", e.name);
217 if e.kind == Kind::Dir {
218 self.flatten_into(&e.id, &format!("{path}/"), out)?;
219 } else {
220 out.push((path, e.kind, e.id));
221 }
222 }
223 Ok(())
224 }
225
226 /// An object's stored bytes (type prefix and content), checked against its id. For transfer.
227 pub fn get_raw(&self, id: &Id) -> Result<Vec<u8>> {
228 let bytes = match fs::read(self.path(id)) {
229 Ok(b) => b,
230 Err(e) if e.kind() == io::ErrorKind::NotFound => return Err(Error::Missing(*id)),
231 Err(e) => return Err(e.into()),
232 };
233 if crate::blake3::hash(&bytes) != *id {
234 return Err(Error::Corrupt(*id));
235 }
236 Ok(bytes)
237 }
238
239 /// Store an object received from elsewhere. Its id is the hash of its bytes; the bytes must
240 /// be a blob, or a tree that decodes.
241 pub fn put_raw(&self, bytes: &[u8]) -> Result<Id> {
242 let id = crate::blake3::hash(bytes);
243 if let Some(content) = bytes.strip_prefix(BLOB) {
244 return self.put(BLOB, content).map(|_| id);
245 }
246 if let Some(content) = bytes.strip_prefix(TREE) {
247 decode_tree(&id, content)?;
248 return self.put(TREE, content).map(|_| id);
249 }
250 Err(Error::Corrupt(id))
251 }
252
253 /// Every object id under a tree (trees and blobs), the tree itself first.
254 pub fn ids_under(&self, tree: &Id) -> Result<Vec<Id>> {
255 let mut out = vec![*tree];
256 let mut seen = std::collections::HashSet::new();
257 seen.insert(*tree);
258 let mut i = 0;
259 while i < out.len() {
260 let id = out[i];
261 i += 1;
262 // Only trees have children; blobs fail to decode as trees and are skipped.
263 let Ok(bytes) = self.get_raw(&id) else { return Err(Error::Missing(id)) };
264 if let Some(content) = bytes.strip_prefix(TREE) {
265 for e in decode_tree(&id, content)? {
266 if seen.insert(e.id) {
267 out.push(e.id);
268 }
269 }
270 }
271 }
272 Ok(out)
273 }
274
275 /// Confirm every object under a tree exists and matches its id.
276 pub fn verify_tree(&self, tree: &Id) -> Result<usize> {
277 let mut count = 1;
278 for e in self.get_tree(tree)? {
279 count += if e.kind == Kind::Dir { self.verify_tree(&e.id)? } else { self.get_blob(&e.id).map(|_| 1)? };
280 }
281 Ok(count)
282 }
283}
284
285#[cfg(test)]
286mod tests {
287 use super::*;
288 use crate::testdir::TestDir;
289
290 #[test]
291 fn blobs_round_trip_and_dedupe() {
292 let dir = TestDir::new("objects-blobs");
293 let objects = Objects::open(dir.path()).unwrap();
294 let a = objects.put_blob(b"hello").unwrap();
295 assert_eq!(objects.put_blob(b"hello").unwrap(), a);
296 assert_ne!(objects.put_blob(b"hello!").unwrap(), a);
297 assert_eq!(objects.get_blob(&a).unwrap(), b"hello");
298 assert_eq!(a, blob_id(b"hello"));
299 assert!(objects.has(&a));
300 }
301
302 #[test]
303 fn trees_are_canonical() {
304 let dir = TestDir::new("objects-trees");
305 let objects = Objects::open(dir.path()).unwrap();
306 let f = objects.put_blob(b"x").unwrap();
307 let e = |name: &str| Entry { name: name.into(), kind: Kind::File, id: f };
308 let t1 = objects.put_tree(&[e("b"), e("a")]).unwrap();
309 let t2 = objects.put_tree(&[e("a"), e("b")]).unwrap();
310 assert_eq!(t1, t2, "order of input doesn't matter");
311 let entries = objects.get_tree(&t1).unwrap();
312 assert_eq!(entries.iter().map(|e| e.name.as_str()).collect::<Vec<_>>(), ["a", "b"]);
313 // A tree and a blob with identical bytes still differ.
314 assert_ne!(objects.empty_tree().unwrap(), objects.put_blob(b"").unwrap());
315 }
316
317 #[test]
318 fn rejects_bad_names() {
319 let dir = TestDir::new("objects-names");
320 let objects = Objects::open(dir.path()).unwrap();
321 let f = objects.put_blob(b"x").unwrap();
322 for bad in ["", ".", "..", "a/b", "nul\0"] {
323 let e = Entry { name: bad.into(), kind: Kind::File, id: f };
324 assert!(matches!(objects.put_tree(&[e]), Err(Error::BadName(_))), "{bad:?}");
325 }
326 let e = Entry { name: "same".into(), kind: Kind::File, id: f };
327 assert!(objects.put_tree(&[e.clone(), e]).is_err());
328 }
329
330 #[test]
331 fn corruption_and_absence_are_detected() {
332 let dir = TestDir::new("objects-corrupt");
333 let objects = Objects::open(dir.path()).unwrap();
334 let id = objects.put_blob(b"precious").unwrap();
335 std::fs::write(objects.path(&id), b"grove blob\0tampered").unwrap();
336 assert!(matches!(objects.get_blob(&id), Err(Error::Corrupt(_))));
337 assert!(matches!(objects.get_blob(&blob_id(b"never stored")), Err(Error::Missing(_))));
338 }
339
340 #[test]
341 fn flatten_and_verify() {
342 let dir = TestDir::new("objects-flatten");
343 let objects = Objects::open(dir.path()).unwrap();
344 let a = objects.put_blob(b"a").unwrap();
345 let b = objects.put_blob(b"b").unwrap();
346 let sub = objects.put_tree(&[Entry { name: "inner.txt".into(), kind: Kind::File, id: b }]).unwrap();
347 let root = objects
348 .put_tree(&[
349 Entry { name: "run.sh".into(), kind: Kind::Exec, id: a },
350 Entry { name: "dir".into(), kind: Kind::Dir, id: sub },
351 ])
352 .unwrap();
353 let files = objects.flatten(&root).unwrap();
354 assert_eq!(files, vec![("dir/inner.txt".into(), Kind::File, b), ("run.sh".into(), Kind::Exec, a)]);
355 assert_eq!(objects.verify_tree(&root).unwrap(), 4);
356 }
357}