1use crate::directory::entry::DirectoryEntry;
12use crate::directory::helper::DirectlyMutable;
13use crate::directory::immutable::Simple;
14
15use fidl_fuchsia_io as fio;
16use itertools::Itertools;
17use std::collections::HashMap;
18use std::fmt;
19use std::marker::PhantomData;
20use std::slice::Iter;
21use std::sync::Arc;
22use thiserror::Error;
23
24pub struct Path<'components, Impl>
41where
42 Impl: AsRef<[&'components str]>,
43{
44 path: Impl,
45 _components: PhantomData<&'components str>,
46}
47
48impl<'components, Impl> Path<'components, Impl>
49where
50 Impl: AsRef<[&'components str]>,
51{
52 fn iter<'path>(&'path self) -> Iter<'path, &'components str>
53 where
54 'components: 'path,
55 {
56 self.path.as_ref().iter()
57 }
58}
59
60impl<'component> From<&'component str> for Path<'component, Vec<&'component str>> {
61 fn from(component: &'component str) -> Self {
62 Path { path: vec![component], _components: PhantomData }
63 }
64}
65
66impl<'components, Impl> From<Impl> for Path<'components, Impl>
67where
68 Impl: AsRef<[&'components str]>,
69{
70 fn from(path: Impl) -> Self {
71 Path { path, _components: PhantomData }
72 }
73}
74
75impl<'components, Impl> fmt::Display for Path<'components, Impl>
76where
77 Impl: AsRef<[&'components str]>,
78{
79 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
80 write!(f, "{}", self.iter().format("/"))
81 }
82}
83
84pub enum TreeBuilder {
85 Directory(HashMap<String, TreeBuilder>),
86 Leaf(Arc<dyn DirectoryEntry>),
87}
88
89impl TreeBuilder {
99 pub fn empty_dir() -> Self {
102 TreeBuilder::Directory(HashMap::new())
103 }
104
105 pub fn add_entry<'components, P: 'components, PathImpl>(
109 &mut self,
110 path: P,
111 entry: Arc<dyn DirectoryEntry>,
112 ) -> Result<(), Error>
113 where
114 P: Into<Path<'components, PathImpl>>,
115 PathImpl: AsRef<[&'components str]>,
116 {
117 let path = path.into();
118 let traversed = vec![];
119 let mut rest = path.iter();
120 match rest.next() {
121 None => Err(Error::EmptyPath),
122 Some(name) => self.add_path(
123 &path,
124 traversed,
125 name,
126 rest,
127 |entries, name, full_path, _traversed| match entries
128 .insert(name.to_string(), TreeBuilder::Leaf(entry))
129 {
130 None => Ok(()),
131 Some(TreeBuilder::Directory(_)) => {
132 Err(Error::LeafOverDirectory { path: full_path.to_string() })
133 }
134 Some(TreeBuilder::Leaf(_)) => {
135 Err(Error::LeafOverLeaf { path: full_path.to_string() })
136 }
137 },
138 ),
139 }
140 }
141
142 pub fn add_empty_dir<'components, P: 'components, PathImpl>(
170 &mut self,
171 path: P,
172 ) -> Result<(), Error>
173 where
174 P: Into<Path<'components, PathImpl>>,
175 PathImpl: AsRef<[&'components str]>,
176 {
177 let path = path.into();
178 let traversed = vec![];
179 let mut rest = path.iter();
180 match rest.next() {
181 None => Err(Error::EmptyPath),
182 Some(name) => self.add_path(
183 &path,
184 traversed,
185 name,
186 rest,
187 |entries, name, full_path, traversed| match entries
188 .entry(name.to_string())
189 .or_insert_with(|| TreeBuilder::Directory(HashMap::new()))
190 {
191 TreeBuilder::Directory(_) => Ok(()),
192 TreeBuilder::Leaf(_) => Err(Error::EntryInsideLeaf {
193 path: full_path.to_string(),
194 traversed: traversed.iter().join("/"),
195 }),
196 },
197 ),
198 }
199 }
200
201 fn add_path<'path, 'components: 'path, PathImpl, Inserter>(
202 &mut self,
203 full_path: &'path Path<'components, PathImpl>,
204 mut traversed: Vec<&'components str>,
205 name: &'components str,
206 mut rest: Iter<'path, &'components str>,
207 inserter: Inserter,
208 ) -> Result<(), Error>
209 where
210 PathImpl: AsRef<[&'components str]>,
211 Inserter: FnOnce(
212 &mut HashMap<String, TreeBuilder>,
213 &str,
214 &Path<'components, PathImpl>,
215 Vec<&'components str>,
216 ) -> Result<(), Error>,
217 {
218 if name.len() as u64 >= fio::MAX_NAME_LENGTH {
219 return Err(Error::ComponentNameTooLong {
220 path: full_path.to_string(),
221 component: name.to_string(),
222 component_len: name.len(),
223 max_len: (fio::MAX_NAME_LENGTH - 1) as usize,
224 });
225 }
226
227 if name.contains('/') {
228 return Err(Error::SlashInComponent {
229 path: full_path.to_string(),
230 component: name.to_string(),
231 });
232 }
233
234 match self {
235 TreeBuilder::Directory(entries) => match rest.next() {
236 None => inserter(entries, name, full_path, traversed),
237 Some(next_component) => {
238 traversed.push(name);
239 match entries.get_mut(name) {
240 None => {
241 let mut child = TreeBuilder::Directory(HashMap::new());
242 child.add_path(full_path, traversed, next_component, rest, inserter)?;
243 let existing = entries.insert(name.to_string(), child);
244 assert!(existing.is_none());
245 Ok(())
246 }
247 Some(children) => {
248 children.add_path(full_path, traversed, next_component, rest, inserter)
249 }
250 }
251 }
252 },
253 TreeBuilder::Leaf(_) => Err(Error::EntryInsideLeaf {
254 path: full_path.to_string(),
255 traversed: traversed.iter().join("/"),
256 }),
257 }
258 }
259
260 pub fn build(self) -> Arc<Simple> {
263 let mut generator = |_| -> u64 { fio::INO_UNKNOWN };
264 self.build_with_inode_generator(&mut generator)
265 }
266
267 pub fn build_with_inode_generator(
272 self,
273 get_inode: &mut impl FnMut(String) -> u64,
274 ) -> Arc<Simple> {
275 match self {
276 TreeBuilder::Directory(mut entries) => {
277 let res = Simple::new_with_inode(get_inode(".".to_string()));
278 for (name, child) in entries.drain() {
279 res.clone()
280 .add_entry(&name, child.build_dyn(name.clone(), get_inode))
281 .map_err(|status| format!("Status: {}", status))
282 .expect(
283 "Internal error. We have already checked all the entry names. \
284 There should be no collisions, nor overly long names.",
285 );
286 }
287 res
288 }
289 TreeBuilder::Leaf(_) => {
290 panic!("Leaf nodes should not be buildable through the public API.")
291 }
292 }
293 }
294
295 fn build_dyn(
296 self,
297 dir: String,
298 get_inode: &mut impl FnMut(String) -> u64,
299 ) -> Arc<dyn DirectoryEntry> {
300 match self {
301 TreeBuilder::Directory(mut entries) => {
302 let res = Simple::new_with_inode(get_inode(dir));
303 for (name, child) in entries.drain() {
304 res.clone()
305 .add_entry(&name, child.build_dyn(name.clone(), get_inode))
306 .map_err(|status| format!("Status: {}", status))
307 .expect(
308 "Internal error. We have already checked all the entry names. \
309 There should be no collisions, nor overly long names.",
310 );
311 }
312 res
313 }
314 TreeBuilder::Leaf(entry) => entry,
315 }
316 }
317}
318
319#[derive(Debug, Error, PartialEq, Eq)]
320pub enum Error {
321 #[error("`add_entry` requires a non-empty path")]
322 EmptyPath,
323
324 #[error(
325 "Path component contains a forward slash.\n\
326 Path: {}\n\
327 Component: '{}'",
328 path,
329 component
330 )]
331 SlashInComponent { path: String, component: String },
332
333 #[error(
334 "Path component name is too long - {} characters. Maximum is {}.\n\
335 Path: {}\n\
336 Component: '{}'",
337 component_len,
338 max_len,
339 path,
340 component
341 )]
342 ComponentNameTooLong { path: String, component: String, component_len: usize, max_len: usize },
343
344 #[error(
345 "Trying to insert a leaf over an existing directory.\n\
346 Path: {}",
347 path
348 )]
349 LeafOverDirectory { path: String },
350
351 #[error(
352 "Trying to overwrite one leaf with another.\n\
353 Path: {}",
354 path
355 )]
356 LeafOverLeaf { path: String },
357
358 #[error(
359 "Trying to insert an entry inside a leaf.\n\
360 Leaf path: {}\n\
361 Path been inserted: {}",
362 path,
363 traversed
364 )]
365 EntryInsideLeaf { path: String, traversed: String },
366}
367
368#[cfg(test)]
369mod tests {
370 use super::{Error, Simple, TreeBuilder};
371
372 use crate::{assert_close, assert_read};
374
375 use crate::directory::serve;
376 use crate::file;
377
378 use fidl_fuchsia_io as fio;
379 use fuchsia_fs::directory::{open_directory, readdir, DirEntry, DirentKind};
380 use vfs_macros::pseudo_directory;
381
382 async fn assert_open_file_contents(
383 root: &fio::DirectoryProxy,
384 path: &str,
385 flags: fio::Flags,
386 expected_contents: &str,
387 ) {
388 let file = fuchsia_fs::directory::open_file(&root, path, flags).await.unwrap();
389 assert_read!(file, expected_contents);
390 assert_close!(file);
391 }
392
393 async fn get_id_of_path(root: &fio::DirectoryProxy, path: &str) -> u64 {
394 let (proxy, server) = fidl::endpoints::create_proxy::<fio::NodeMarker>();
395 root.open(path, fio::PERM_READABLE, &Default::default(), server.into_channel())
396 .expect("failed to call open");
397 let (_, immutable_attrs) = proxy
398 .get_attributes(fio::NodeAttributesQuery::ID)
399 .await
400 .expect("FIDL call failed")
401 .expect("GetAttributes failed");
402 immutable_attrs.id.expect("ID missing from GetAttributes response")
403 }
404
405 #[fuchsia::test]
406 async fn vfs_with_custom_inodes() {
407 let mut tree = TreeBuilder::empty_dir();
408 tree.add_entry(&["a", "b", "file"], file::read_only(b"A content")).unwrap();
409 tree.add_entry(&["a", "c", "file"], file::read_only(b"B content")).unwrap();
410
411 let mut get_inode = |name: String| -> u64 {
412 match &name[..] {
413 "a" => 1,
414 "b" => 2,
415 "c" => 3,
416 _ => fio::INO_UNKNOWN,
417 }
418 };
419 let root = tree.build_with_inode_generator(&mut get_inode);
420 let root = serve(root, fio::PERM_READABLE);
421 assert_eq!(get_id_of_path(&root, "a").await, 1);
422 assert_eq!(get_id_of_path(&root, "a/b").await, 2);
423 assert_eq!(get_id_of_path(&root, "a/c").await, 3);
424 }
425
426 #[fuchsia::test]
427 async fn two_files() {
428 let mut tree = TreeBuilder::empty_dir();
429 tree.add_entry("a", file::read_only(b"A content")).unwrap();
430 tree.add_entry("b", file::read_only(b"B content")).unwrap();
431
432 let root = tree.build();
433 let root = serve(root, fio::PERM_READABLE);
434
435 assert_eq!(
436 readdir(&root).await.unwrap(),
437 vec![
438 DirEntry { name: String::from("a"), kind: DirentKind::File },
439 DirEntry { name: String::from("b"), kind: DirentKind::File },
440 ]
441 );
442 assert_open_file_contents(&root, "a", fio::PERM_READABLE, "A content").await;
443 assert_open_file_contents(&root, "b", fio::PERM_READABLE, "B content").await;
444
445 assert_close!(root);
446 }
447
448 #[fuchsia::test]
449 async fn overlapping_paths() {
450 let mut tree = TreeBuilder::empty_dir();
451 tree.add_entry(&["one", "two"], file::read_only(b"A")).unwrap();
452 tree.add_entry(&["one", "three"], file::read_only(b"B")).unwrap();
453 tree.add_entry("four", file::read_only(b"C")).unwrap();
454
455 let root = tree.build();
456 let root = serve(root, fio::PERM_READABLE);
457
458 assert_eq!(
459 readdir(&root).await.unwrap(),
460 vec![
461 DirEntry { name: String::from("four"), kind: DirentKind::File },
462 DirEntry { name: String::from("one"), kind: DirentKind::Directory },
463 ]
464 );
465 let one_dir = open_directory(&root, "one", fio::PERM_READABLE).await.unwrap();
466 assert_eq!(
467 readdir(&one_dir).await.unwrap(),
468 vec![
469 DirEntry { name: String::from("three"), kind: DirentKind::File },
470 DirEntry { name: String::from("two"), kind: DirentKind::File },
471 ]
472 );
473 assert_close!(one_dir);
474
475 assert_open_file_contents(&root, "one/two", fio::PERM_READABLE, "A").await;
476 assert_open_file_contents(&root, "one/three", fio::PERM_READABLE, "B").await;
477 assert_open_file_contents(&root, "four", fio::PERM_READABLE, "C").await;
478
479 assert_close!(root);
480 }
481
482 #[fuchsia::test]
483 async fn directory_leaf() {
484 let etc = pseudo_directory! {
485 "fstab" => file::read_only(b"/dev/fs /"),
486 "ssh" => pseudo_directory! {
487 "sshd_config" => file::read_only(b"# Empty"),
488 },
489 };
490
491 let mut tree = TreeBuilder::empty_dir();
492 tree.add_entry("etc", etc).unwrap();
493 tree.add_entry("uname", file::read_only(b"Fuchsia")).unwrap();
494
495 let root = tree.build();
496 let root = serve(root, fio::PERM_READABLE);
497
498 assert_eq!(
499 readdir(&root).await.unwrap(),
500 vec![
501 DirEntry { name: String::from("etc"), kind: DirentKind::Directory },
502 DirEntry { name: String::from("uname"), kind: DirentKind::File },
503 ]
504 );
505 let etc_dir = open_directory(&root, "etc", fio::PERM_READABLE).await.unwrap();
506 assert_eq!(
507 readdir(&etc_dir).await.unwrap(),
508 vec![
509 DirEntry { name: String::from("fstab"), kind: DirentKind::File },
510 DirEntry { name: String::from("ssh"), kind: DirentKind::Directory },
511 ]
512 );
513 assert_close!(etc_dir);
514 let ssh_dir = open_directory(&root, "etc/ssh", fio::PERM_READABLE).await.unwrap();
515 assert_eq!(
516 readdir(&ssh_dir).await.unwrap(),
517 vec![DirEntry { name: String::from("sshd_config"), kind: DirentKind::File }]
518 );
519 assert_close!(ssh_dir);
520
521 assert_open_file_contents(&root, "etc/fstab", fio::PERM_READABLE, "/dev/fs /").await;
522 assert_open_file_contents(&root, "etc/ssh/sshd_config", fio::PERM_READABLE, "# Empty")
523 .await;
524 assert_open_file_contents(&root, "uname", fio::PERM_READABLE, "Fuchsia").await;
525
526 assert_close!(root);
527 }
528
529 #[fuchsia::test]
530 async fn add_empty_dir_populate_later() {
531 let mut tree = TreeBuilder::empty_dir();
532 tree.add_empty_dir(&["one", "two"]).unwrap();
533 tree.add_entry(&["one", "two", "three"], file::read_only(b"B")).unwrap();
534
535 let root = tree.build();
536 let root = serve(root, fio::PERM_READABLE);
537
538 assert_eq!(
539 readdir(&root).await.unwrap(),
540 vec![DirEntry { name: String::from("one"), kind: DirentKind::Directory }]
541 );
542 let one_dir = open_directory(&root, "one", fio::PERM_READABLE).await.unwrap();
543 assert_eq!(
544 readdir(&one_dir).await.unwrap(),
545 vec![DirEntry { name: String::from("two"), kind: DirentKind::Directory }]
546 );
547 assert_close!(one_dir);
548 let two_dir = open_directory(&root, "one/two", fio::PERM_READABLE).await.unwrap();
549 assert_eq!(
550 readdir(&two_dir).await.unwrap(),
551 vec![DirEntry { name: String::from("three"), kind: DirentKind::File }]
552 );
553 assert_close!(two_dir);
554
555 assert_open_file_contents(&root, "one/two/three", fio::PERM_READABLE, "B").await;
556
557 assert_close!(root);
558 }
559
560 #[fuchsia::test]
561 async fn add_empty_dir_already_exists() {
562 let mut tree = TreeBuilder::empty_dir();
563 tree.add_entry(&["one", "two", "three"], file::read_only(b"B")).unwrap();
564 tree.add_empty_dir(&["one", "two"]).unwrap();
565
566 let root = tree.build();
567 let root = serve(root, fio::PERM_READABLE);
568
569 assert_eq!(
570 readdir(&root).await.unwrap(),
571 vec![DirEntry { name: String::from("one"), kind: DirentKind::Directory }]
572 );
573
574 let one_dir = open_directory(&root, "one", fio::PERM_READABLE).await.unwrap();
575 assert_eq!(
576 readdir(&one_dir).await.unwrap(),
577 vec![DirEntry { name: String::from("two"), kind: DirentKind::Directory }]
578 );
579 assert_close!(one_dir);
580
581 let two_dir = open_directory(&root, "one/two", fio::PERM_READABLE).await.unwrap();
582 assert_eq!(
583 readdir(&two_dir).await.unwrap(),
584 vec![DirEntry { name: String::from("three"), kind: DirentKind::File }]
585 );
586 assert_close!(two_dir);
587
588 assert_open_file_contents(&root, "one/two/three", fio::PERM_READABLE, "B").await;
589
590 assert_close!(root);
591 }
592
593 #[fuchsia::test]
594 async fn lone_add_empty_dir() {
595 let mut tree = TreeBuilder::empty_dir();
596 tree.add_empty_dir(&["just-me"]).unwrap();
597
598 let root = tree.build();
599 let root = serve(root, fio::PERM_READABLE);
600
601 assert_eq!(
602 readdir(&root).await.unwrap(),
603 vec![DirEntry { name: String::from("just-me"), kind: DirentKind::Directory }]
604 );
605 let just_me_dir = open_directory(&root, "just-me", fio::PERM_READABLE).await.unwrap();
606 assert_eq!(readdir(&just_me_dir).await.unwrap(), Vec::new());
607
608 assert_close!(just_me_dir);
609 assert_close!(root);
610 }
611
612 #[fuchsia::test]
613 async fn add_empty_dir_inside_add_empty_dir() {
614 let mut tree = TreeBuilder::empty_dir();
615 tree.add_empty_dir(&["container"]).unwrap();
616 tree.add_empty_dir(&["container", "nested"]).unwrap();
617
618 let root = tree.build();
619 let root = serve(root, fio::PERM_READABLE);
620
621 assert_eq!(
622 readdir(&root).await.unwrap(),
623 vec![DirEntry { name: String::from("container"), kind: DirentKind::Directory }]
624 );
625
626 let container_dir = open_directory(&root, "container", fio::PERM_READABLE).await.unwrap();
627 assert_eq!(
628 readdir(&container_dir).await.unwrap(),
629 vec![DirEntry { name: String::from("nested"), kind: DirentKind::Directory }]
630 );
631 assert_close!(container_dir);
632
633 let nested_dir =
634 open_directory(&root, "container/nested", fio::PERM_READABLE).await.unwrap();
635 assert_eq!(readdir(&nested_dir).await.unwrap(), Vec::new());
636 assert_close!(nested_dir);
637
638 assert_close!(root);
639 }
640
641 #[fuchsia::test]
642 fn error_empty_path_in_add_entry() {
643 let mut tree = TreeBuilder::empty_dir();
644 let err = tree
645 .add_entry(vec![], file::read_only(b"Invalid"))
646 .expect_err("Empty paths are not allowed.");
647 assert_eq!(err, Error::EmptyPath);
648 }
649
650 #[fuchsia::test]
651 fn error_slash_in_component() {
652 let mut tree = TreeBuilder::empty_dir();
653 let err = tree
654 .add_entry("a/b", file::read_only(b"Invalid"))
655 .expect_err("Slash in path component name.");
656 assert_eq!(
657 err,
658 Error::SlashInComponent { path: "a/b".to_string(), component: "a/b".to_string() }
659 );
660 }
661
662 #[fuchsia::test]
663 fn error_slash_in_second_component() {
664 let mut tree = TreeBuilder::empty_dir();
665 let err = tree
666 .add_entry(&["a", "b/c"], file::read_only(b"Invalid"))
667 .expect_err("Slash in path component name.");
668 assert_eq!(
669 err,
670 Error::SlashInComponent { path: "a/b/c".to_string(), component: "b/c".to_string() }
671 );
672 }
673
674 #[fuchsia::test]
675 fn error_component_name_too_long() {
676 let mut tree = TreeBuilder::empty_dir();
677
678 let long_component = "abcdefghij".repeat(fio::MAX_NAME_LENGTH as usize / 10 + 1);
679
680 let path: &[&str] = &["a", &long_component, "b"];
681 let err = tree
682 .add_entry(path, file::read_only(b"Invalid"))
683 .expect_err("Individual component names may not exceed MAX_FILENAME bytes.");
684 assert_eq!(
685 err,
686 Error::ComponentNameTooLong {
687 path: format!("a/{}/b", long_component),
688 component: long_component.clone(),
689 component_len: long_component.len(),
690 max_len: (fio::MAX_NAME_LENGTH - 1) as usize,
691 }
692 );
693 }
694
695 #[fuchsia::test]
696 fn error_leaf_over_directory() {
697 let mut tree = TreeBuilder::empty_dir();
698
699 tree.add_entry(&["top", "nested", "file"], file::read_only(b"Content")).unwrap();
700 let err = tree
701 .add_entry(&["top", "nested"], file::read_only(b"Invalid"))
702 .expect_err("A leaf may not be constructed over a directory.");
703 assert_eq!(err, Error::LeafOverDirectory { path: "top/nested".to_string() });
704 }
705
706 #[fuchsia::test]
707 fn error_leaf_over_leaf() {
708 let mut tree = TreeBuilder::empty_dir();
709
710 tree.add_entry(&["top", "nested", "file"], file::read_only(b"Content")).unwrap();
711 let err = tree
712 .add_entry(&["top", "nested", "file"], file::read_only(b"Invalid"))
713 .expect_err("A leaf may not be constructed over another leaf.");
714 assert_eq!(err, Error::LeafOverLeaf { path: "top/nested/file".to_string() });
715 }
716
717 #[fuchsia::test]
718 fn error_entry_inside_leaf() {
719 let mut tree = TreeBuilder::empty_dir();
720
721 tree.add_entry(&["top", "file"], file::read_only(b"Content")).unwrap();
722 let err = tree
723 .add_entry(&["top", "file", "nested"], file::read_only(b"Invalid"))
724 .expect_err("A leaf may not be constructed over another leaf.");
725 assert_eq!(
726 err,
727 Error::EntryInsideLeaf {
728 path: "top/file/nested".to_string(),
729 traversed: "top/file".to_string()
730 }
731 );
732 }
733
734 #[fuchsia::test]
735 fn error_entry_inside_leaf_directory() {
736 let mut tree = TreeBuilder::empty_dir();
737
738 tree.add_entry(&["top", "file"], Simple::new()).unwrap();
740 let err = tree
741 .add_entry(&["top", "file", "nested"], file::read_only(b"Invalid"))
742 .expect_err("A leaf may not be constructed over another leaf.");
743 assert_eq!(
744 err,
745 Error::EntryInsideLeaf {
746 path: "top/file/nested".to_string(),
747 traversed: "top/file".to_string()
748 }
749 );
750 }
751}