crates/vfs/src/file_set.rs

   1 //! Partitions a list of files into disjoint subsets.
   2 //!
   3 //! Files which do not belong to any explicitly configured `FileSet` belong to
   4 //! the default `FileSet`.
   5 use std::fmt;
   6
   7 use fst::{IntoStreamer, Streamer};
   8 use rustc_hash::FxHashMap;
   9
  10 use crate::{AnchoredPath, FileId, Vfs, VfsPath};
  11
  12 /// A set of [`VfsPath`]s identified by [`FileId`]s.
  13 #[derive(Default, Clone, Eq, PartialEq)]
  14 pub struct FileSet {
  15     files: FxHashMap<VfsPath, FileId>,
  16     paths: FxHashMap<FileId, VfsPath>,
  17 }
  18
  19 impl FileSet {
  20     /// Returns the number of stored paths.
  21     pub fn len(&self) -> usize {
  22         self.files.len()
  23     }
  24
  25     /// Get the id of the file corresponding to `path`.
  26     ///
  27     /// If either `path`'s [`anchor`](AnchoredPath::anchor) or the resolved path is not in
  28     /// the set, returns [`None`].
  29     pub fn resolve_path(&self, path: AnchoredPath<'_>) -> Option<FileId> {
  30         let mut base = self.paths[&path.anchor].clone();
  31         base.pop();
  32         let path = base.join(path.path)?;
  33         self.files.get(&path).copied()
  34     }
  35
  36     /// Get the id corresponding to `path` if it exists in the set.
  37     pub fn file_for_path(&self, path: &VfsPath) -> Option<&FileId> {
  38         self.files.get(path)
  39     }
  40
  41     /// Get the path corresponding to `file` if it exists in the set.
  42     pub fn path_for_file(&self, file: &FileId) -> Option<&VfsPath> {
  43         self.paths.get(file)
  44     }
  45
  46     /// Insert the `file_id, path` pair into the set.
  47     ///
  48     /// # Note
  49     /// Multiple [`FileId`] can be mapped to the same [`VfsPath`], and vice-versa.
  50     pub fn insert(&mut self, file_id: FileId, path: VfsPath) {
  51         self.files.insert(path.clone(), file_id);
  52         self.paths.insert(file_id, path);
  53     }
  54
  55     /// Iterate over this set's ids.
  56     pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
  57         self.paths.keys().copied()
  58     }
  59 }
  60
  61 impl fmt::Debug for FileSet {
  62     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  63         f.debug_struct("FileSet").field("n_files", &self.files.len()).finish()
  64     }
  65 }
  66
  67 /// This contains path prefixes to partition a [`Vfs`] into [`FileSet`]s.
  68 ///
  69 /// # Example
  70 /// ```rust
  71 /// # use vfs::{file_set::FileSetConfigBuilder, VfsPath, Vfs};
  72 /// let mut builder = FileSetConfigBuilder::default();
  73 /// builder.add_file_set(vec![VfsPath::new_virtual_path("/src".to_string())]);
  74 /// let config = builder.build();
  75 /// let mut file_system = Vfs::default();
  76 /// file_system.set_file_contents(VfsPath::new_virtual_path("/src/main.rs".to_string()), Some(vec![]));
  77 /// file_system.set_file_contents(VfsPath::new_virtual_path("/src/lib.rs".to_string()), Some(vec![]));
  78 /// file_system.set_file_contents(VfsPath::new_virtual_path("/build.rs".to_string()), Some(vec![]));
  79 /// // contains the sets :
  80 /// // { "/src/main.rs", "/src/lib.rs" }
  81 /// // { "build.rs" }
  82 /// let sets = config.partition(&file_system);
  83 /// ```
  84 #[derive(Debug)]
  85 pub struct FileSetConfig {
  86     /// Number of sets that `self` can partition a [`Vfs`] into.
  87     ///
  88     /// This should be the number of sets in `self.map` + 1 for files that don't fit in any
  89     /// defined set.
  90     n_file_sets: usize,
  91     /// Map from encoded paths to the set they belong to.
  92     map: fst::Map<Vec<u8>>,
  93 }
  94
  95 impl Default for FileSetConfig {
  96     fn default() -> Self {
  97         FileSetConfig::builder().build()
  98     }
  99 }
 100
 101 impl FileSetConfig {
 102     /// Returns a builder for `FileSetConfig`.
 103     pub fn builder() -> FileSetConfigBuilder {
 104         FileSetConfigBuilder::default()
 105     }
 106
 107     /// Partition `vfs` into `FileSet`s.
 108     ///
 109     /// Creates a new [`FileSet`] for every set of prefixes in `self`.
 110     pub fn partition(&self, vfs: &Vfs) -> Vec<FileSet> {
 111         let mut scratch_space = Vec::new();
 112         let mut res = vec![FileSet::default(); self.len()];
 113         for (file_id, path) in vfs.iter() {
 114             let root = self.classify(path, &mut scratch_space);
 115             res[root].insert(file_id, path.clone())
 116         }
 117         res
 118     }
 119
 120     /// Number of sets that `self` can partition a [`Vfs`] into.
 121     fn len(&self) -> usize {
 122         self.n_file_sets
 123     }
 124
 125     /// Returns the set index for the given `path`.
 126     ///
 127     /// `scratch_space` is used as a buffer and will be entirely replaced.
 128     fn classify(&self, path: &VfsPath, scratch_space: &mut Vec<u8>) -> usize {
 129         scratch_space.clear();
 130         path.encode(scratch_space);
 131         let automaton = PrefixOf::new(scratch_space.as_slice());
 132         let mut longest_prefix = self.len() - 1;
 133         let mut stream = self.map.search(automaton).into_stream();
 134         while let Some((_, v)) = stream.next() {
 135             longest_prefix = v as usize;
 136         }
 137         longest_prefix
 138     }
 139 }
 140
 141 /// Builder for [`FileSetConfig`].
 142 pub struct FileSetConfigBuilder {
 143     roots: Vec<Vec<VfsPath>>,
 144 }
 145
 146 impl Default for FileSetConfigBuilder {
 147     fn default() -> Self {
 148         FileSetConfigBuilder { roots: Vec::new() }
 149     }
 150 }
 151
 152 impl FileSetConfigBuilder {
 153     /// Returns the number of sets currently held.
 154     pub fn len(&self) -> usize {
 155         self.roots.len()
 156     }
 157
 158     /// Add a new set of paths prefixes.
 159     pub fn add_file_set(&mut self, roots: Vec<VfsPath>) {
 160         self.roots.push(roots)
 161     }
 162
 163     /// Build the `FileSetConfig`.
 164     pub fn build(self) -> FileSetConfig {
 165         let n_file_sets = self.roots.len() + 1;
 166         let map = {
 167             let mut entries = Vec::new();
 168             for (i, paths) in self.roots.into_iter().enumerate() {
 169                 for p in paths {
 170                     let mut buf = Vec::new();
 171                     p.encode(&mut buf);
 172                     entries.push((buf, i as u64));
 173                 }
 174             }
 175             entries.sort();
 176             entries.dedup_by(|(a, _), (b, _)| a == b);
 177             fst::Map::from_iter(entries).unwrap()
 178         };
 179         FileSetConfig { n_file_sets, map }
 180     }
 181 }
 182
 183 /// Implements [`fst::Automaton`]
 184 ///
 185 /// It will match if `prefix_of` is a prefix of the given data.
 186 struct PrefixOf<'a> {
 187     prefix_of: &'a [u8],
 188 }
 189
 190 impl<'a> PrefixOf<'a> {
 191     /// Creates a new `PrefixOf` from the given slice.
 192     fn new(prefix_of: &'a [u8]) -> Self {
 193         Self { prefix_of }
 194     }
 195 }
 196
 197 impl fst::Automaton for PrefixOf<'_> {
 198     type State = usize;
 199     fn start(&self) -> usize {
 200         0
 201     }
 202     fn is_match(&self, &state: &usize) -> bool {
 203         state != !0
 204     }
 205     fn can_match(&self, &state: &usize) -> bool {
 206         state != !0
 207     }
 208     fn accept(&self, &state: &usize, byte: u8) -> usize {
 209         if self.prefix_of.get(state) == Some(&byte) {
 210             state + 1
 211         } else {
 212             !0
 213         }
 214     }
 215 }
 216
 217 #[cfg(test)]
 218 mod tests;