5 files changed, 222 insertions, 33 deletions

diff --git a/crates/vfs/Cargo.toml b/crates/vfs/Cargo.toml
index 263069002..b74cdb7ff 100644
--- a/crates/vfs/Cargo.toml
+++ b/crates/vfs/Cargo.toml
@@ -3,8 +3,13 @@ name = "vfs"
 version = "0.1.0"
 authors = ["rust-analyzer developers"]
 edition = "2018"
+license = "MIT OR Apache-2.0"
+
+[lib]
+doctest = false
 
 [dependencies]
 rustc-hash = "1.0"
+fst = "0.4"
 
 paths = { path = "../paths" }
diff --git a/crates/vfs/src/file_set.rs b/crates/vfs/src/file_set.rs
index d0ddeafe7..e9196fcd2 100644
--- a/crates/vfs/src/file_set.rs
+++ b/crates/vfs/src/file_set.rs
@@ -2,8 +2,9 @@
 //!
 //! Files which do not belong to any explicitly configured `FileSet` belong to
 //! the default `FileSet`.
-use std::{fmt, iter};
+use std::fmt;
 
+use fst::{IntoStreamer, Streamer};
 use rustc_hash::FxHashMap;
 
 use crate::{FileId, Vfs, VfsPath};
@@ -15,6 +16,9 @@ pub struct FileSet {
 }
 
 impl FileSet {
+    pub fn len(&self) -> usize {
+        self.files.len()
+    }
     pub fn resolve_path(&self, anchor: FileId, path: &str) -> Option<FileId> {
         let mut base = self.paths[&anchor].clone();
         base.pop();
@@ -40,7 +44,7 @@ impl fmt::Debug for FileSet {
 #[derive(Debug)]
 pub struct FileSetConfig {
     n_file_sets: usize,
-    roots: Vec<(VfsPath, usize)>,
+    map: fst::Map<Vec<u8>>,
 }
 
 impl Default for FileSetConfig {
@@ -54,26 +58,27 @@ impl FileSetConfig {
         FileSetConfigBuilder::default()
     }
     pub fn partition(&self, vfs: &Vfs) -> Vec<FileSet> {
+        let mut scratch_space = Vec::new();
         let mut res = vec![FileSet::default(); self.len()];
         for (file_id, path) in vfs.iter() {
-            let root = self.classify(&path);
-            res[root].insert(file_id, path)
+            let root = self.classify(&path, &mut scratch_space);
+            res[root].insert(file_id, path.clone())
         }
         res
     }
     fn len(&self) -> usize {
         self.n_file_sets
     }
-    fn classify(&self, path: &VfsPath) -> usize {
-        let idx = match self.roots.binary_search_by(|(p, _)| p.cmp(path)) {
-            Ok(it) => it,
-            Err(it) => it.saturating_sub(1),
-        };
-        if path.starts_with(&self.roots[idx].0) {
-            self.roots[idx].1
-        } else {
-            self.len() - 1
+    fn classify(&self, path: &VfsPath, scratch_space: &mut Vec<u8>) -> usize {
+        scratch_space.clear();
+        path.encode(scratch_space);
+        let automaton = PrefixOf::new(scratch_space.as_slice());
+        let mut longest_prefix = self.len() - 1;
+        let mut stream = self.map.search(automaton).into_stream();
+        while let Some((_, v)) = stream.next() {
+            longest_prefix = v as usize;
         }
+        longest_prefix
     }
 }
 
@@ -96,13 +101,101 @@ impl FileSetConfigBuilder {
     }
     pub fn build(self) -> FileSetConfig {
         let n_file_sets = self.roots.len() + 1;
-        let mut roots: Vec<(VfsPath, usize)> = self
-            .roots
-            .into_iter()
-            .enumerate()
-            .flat_map(|(i, paths)| paths.into_iter().zip(iter::repeat(i)))
-            .collect();
-        roots.sort();
-        FileSetConfig { n_file_sets, roots }
+        let map = {
+            let mut entries = Vec::new();
+            for (i, paths) in self.roots.into_iter().enumerate() {
+                for p in paths {
+                    let mut buf = Vec::new();
+                    p.encode(&mut buf);
+                    entries.push((buf, i as u64));
+                }
+            }
+            entries.sort();
+            entries.dedup_by(|(a, _), (b, _)| a == b);
+            fst::Map::from_iter(entries).unwrap()
+        };
+        FileSetConfig { n_file_sets, map }
+    }
+}
+
+struct PrefixOf<'a> {
+    prefix_of: &'a [u8],
+}
+
+impl<'a> PrefixOf<'a> {
+    fn new(prefix_of: &'a [u8]) -> Self {
+        Self { prefix_of }
+    }
+}
+
+impl fst::Automaton for PrefixOf<'_> {
+    type State = usize;
+    fn start(&self) -> usize {
+        0
+    }
+    fn is_match(&self, &state: &usize) -> bool {
+        state != !0
+    }
+    fn can_match(&self, &state: &usize) -> bool {
+        state != !0
+    }
+    fn accept(&self, &state: &usize, byte: u8) -> usize {
+        if self.prefix_of.get(state) == Some(&byte) {
+            state + 1
+        } else {
+            !0
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn path_prefix() {
+        let mut file_set = FileSetConfig::builder();
+        file_set.add_file_set(vec![VfsPath::new_virtual_path("/foo".into())]);
+        file_set.add_file_set(vec![VfsPath::new_virtual_path("/foo/bar/baz".into())]);
+        let file_set = file_set.build();
+
+        let mut vfs = Vfs::default();
+        vfs.set_file_contents(
+            VfsPath::new_virtual_path("/foo/src/lib.rs".into()),
+            Some(Vec::new()),
+        );
+        vfs.set_file_contents(
+            VfsPath::new_virtual_path("/foo/src/bar/baz/lib.rs".into()),
+            Some(Vec::new()),
+        );
+        vfs.set_file_contents(
+            VfsPath::new_virtual_path("/foo/bar/baz/lib.rs".into()),
+            Some(Vec::new()),
+        );
+        vfs.set_file_contents(VfsPath::new_virtual_path("/quux/lib.rs".into()), Some(Vec::new()));
+
+        let partition = file_set.partition(&vfs).into_iter().map(|it| it.len()).collect::<Vec<_>>();
+        assert_eq!(partition, vec![2, 1, 1]);
+    }
+
+    #[test]
+    fn name_prefix() {
+        let mut file_set = FileSetConfig::builder();
+        file_set.add_file_set(vec![VfsPath::new_virtual_path("/foo".into())]);
+        file_set.add_file_set(vec![VfsPath::new_virtual_path("/foo-things".into())]);
+        let file_set = file_set.build();
+
+        let mut vfs = Vfs::default();
+        vfs.set_file_contents(
+            VfsPath::new_virtual_path("/foo/src/lib.rs".into()),
+            Some(Vec::new()),
+        );
+        vfs.set_file_contents(
+            VfsPath::new_virtual_path("/foo-things/src/lib.rs".into()),
+            Some(Vec::new()),
+        );
+
+        let partition = file_set.partition(&vfs).into_iter().map(|it| it.len()).collect::<Vec<_>>();
+        assert_eq!(partition, vec![1, 1, 0]);
     }
 }
diff --git a/crates/vfs/src/lib.rs b/crates/vfs/src/lib.rs
index 024e58018..cdf6f1fd0 100644
--- a/crates/vfs/src/lib.rs
+++ b/crates/vfs/src/lib.rs
@@ -70,7 +70,7 @@ impl ChangedFile {
     }
 }
 
-#[derive(Eq, PartialEq)]
+#[derive(Eq, PartialEq, Copy, Clone, Debug)]
 pub enum ChangeKind {
     Create,
     Modify,
@@ -90,12 +90,12 @@ impl Vfs {
     pub fn file_contents(&self, file_id: FileId) -> &[u8] {
         self.get(file_id).as_deref().unwrap()
     }
-    pub fn iter(&self) -> impl Iterator<Item = (FileId, VfsPath)> + '_ {
+    pub fn iter(&self) -> impl Iterator<Item = (FileId, &VfsPath)> + '_ {
         (0..self.data.len())
             .map(|it| FileId(it as u32))
             .filter(move |&file_id| self.get(file_id).is_some())
             .map(move |file_id| {
-                let path = self.interner.lookup(file_id).clone();
+                let path = self.interner.lookup(file_id);
                 (file_id, path)
             })
     }
diff --git a/crates/vfs/src/loader.rs b/crates/vfs/src/loader.rs
index 6de2e5b3f..40cf96020 100644
--- a/crates/vfs/src/loader.rs
+++ b/crates/vfs/src/loader.rs
@@ -3,10 +3,25 @@ use std::fmt;
 
 use paths::{AbsPath, AbsPathBuf};
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub enum Entry {
     Files(Vec<AbsPathBuf>),
-    Directory { path: AbsPathBuf, include: Vec<String> },
+    Directories(Directories),
+}
+
+/// Specifies a set of files on the file system.
+///
+/// A file is included if:
+///   * it has included extension
+///   * it is under an `include` path
+///   * it is not under `exclude` path
+///
+/// If many include/exclude paths match, the longest one wins.
+#[derive(Debug, Clone, Default)]
+pub struct Directories {
+    pub extensions: Vec<String>,
+    pub include: Vec<AbsPathBuf>,
+    pub exclude: Vec<AbsPathBuf>,
 }
 
 #[derive(Debug)]
@@ -33,21 +48,66 @@ pub trait Handle: fmt::Debug {
 
 impl Entry {
     pub fn rs_files_recursively(base: AbsPathBuf) -> Entry {
-        Entry::Directory { path: base, include: globs(&["*.rs", "!/.git/"]) }
+        Entry::Directories(dirs(base, &[".git"]))
     }
     pub fn local_cargo_package(base: AbsPathBuf) -> Entry {
-        Entry::Directory { path: base, include: globs(&["*.rs", "!/target/", "!/.git/"]) }
+        Entry::Directories(dirs(base, &[".git", "target"]))
     }
     pub fn cargo_package_dependency(base: AbsPathBuf) -> Entry {
-        Entry::Directory {
-            path: base,
-            include: globs(&["*.rs", "!/tests/", "!/examples/", "!/benches/", "!/.git/"]),
+        Entry::Directories(dirs(base, &[".git", "/tests", "/examples", "/benches"]))
+    }
+
+    pub fn contains_file(&self, path: &AbsPath) -> bool {
+        match self {
+            Entry::Files(files) => files.iter().any(|it| it == path),
+            Entry::Directories(dirs) => dirs.contains_file(path),
+        }
+    }
+    pub fn contains_dir(&self, path: &AbsPath) -> bool {
+        match self {
+            Entry::Files(_) => false,
+            Entry::Directories(dirs) => dirs.contains_dir(path),
+        }
+    }
+}
+
+impl Directories {
+    pub fn contains_file(&self, path: &AbsPath) -> bool {
+        let ext = path.extension().unwrap_or_default();
+        if self.extensions.iter().all(|it| it.as_str() != ext) {
+            return false;
+        }
+        self.includes_path(path)
+    }
+    pub fn contains_dir(&self, path: &AbsPath) -> bool {
+        self.includes_path(path)
+    }
+    fn includes_path(&self, path: &AbsPath) -> bool {
+        let mut include: Option<&AbsPathBuf> = None;
+        for incl in &self.include {
+            if path.starts_with(incl) {
+                include = Some(match include {
+                    Some(prev) if prev.starts_with(incl) => prev,
+                    _ => incl,
+                })
+            }
+        }
+        let include = match include {
+            Some(it) => it,
+            None => return false,
+        };
+        for excl in &self.exclude {
+            if path.starts_with(excl) && excl.starts_with(include) {
+                return false;
+            }
         }
+        true
     }
 }
 
-fn globs(globs: &[&str]) -> Vec<String> {
-    globs.iter().map(|it| it.to_string()).collect()
+fn dirs(base: AbsPathBuf, exclude: &[&str]) -> Directories {
+    let exclude = exclude.iter().map(|it| base.join(it)).collect::<Vec<_>>();
+    Directories { extensions: vec!["rs".to_string()], include: vec![base], exclude }
 }
 
 impl fmt::Debug for Message {
diff --git a/crates/vfs/src/vfs_path.rs b/crates/vfs/src/vfs_path.rs
index dc3031ada..04a42264e 100644
--- a/crates/vfs/src/vfs_path.rs
+++ b/crates/vfs/src/vfs_path.rs
@@ -48,6 +48,37 @@ impl VfsPath {
             (VfsPathRepr::VirtualPath(_), _) => false,
         }
     }
+
+    // Don't make this `pub`
+    pub(crate) fn encode(&self, buf: &mut Vec<u8>) {
+        let tag = match &self.0 {
+            VfsPathRepr::PathBuf(_) => 0,
+            VfsPathRepr::VirtualPath(_) => 1,
+        };
+        buf.push(tag);
+        match &self.0 {
+            VfsPathRepr::PathBuf(it) => {
+                let path: &std::ffi::OsStr = it.as_os_str();
+                #[cfg(windows)]
+                {
+                    use std::os::windows::ffi::OsStrExt;
+                    for wchar in path.encode_wide() {
+                        buf.extend(wchar.to_le_bytes().iter().copied());
+                    }
+                }
+                #[cfg(unix)]
+                {
+                    use std::os::unix::ffi::OsStrExt;
+                    buf.extend(path.as_bytes());
+                }
+                #[cfg(not(any(windows, unix)))]
+                {
+                    buf.extend(path.to_string_lossy().as_bytes());
+                }
+            }
+            VfsPathRepr::VirtualPath(VirtualPath(s)) => buf.extend(s.as_bytes()),
+        }
+    }
 }
 
 #[derive(Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]