6 files changed, 575 insertions, 0 deletions

diff --git a/crates/vfs/Cargo.toml b/crates/vfs/Cargo.toml
new file mode 100644
index 000000000..b74cdb7ff
--- /dev/null
+++ b/crates/vfs/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+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
new file mode 100644
index 000000000..e5e2ef530
--- /dev/null
+++ b/crates/vfs/src/file_set.rs
@@ -0,0 +1,172 @@
+//! Partitions a list of files into disjoint subsets.
+//!
+//! Files which do not belong to any explicitly configured `FileSet` belong to
+//! the default `FileSet`.
+use std::fmt;
+
+use fst::{IntoStreamer, Streamer};
+use rustc_hash::FxHashMap;
+
+use crate::{FileId, Vfs, VfsPath};
+
+#[derive(Default, Clone, Eq, PartialEq)]
+pub struct FileSet {
+    files: FxHashMap<VfsPath, FileId>,
+    paths: FxHashMap<FileId, VfsPath>,
+}
+
+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();
+        let path = base.join(path)?;
+        let res = self.files.get(&path).copied();
+        res
+    }
+    pub fn insert(&mut self, file_id: FileId, path: VfsPath) {
+        self.files.insert(path.clone(), file_id);
+        self.paths.insert(file_id, path);
+    }
+    pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
+        self.paths.keys().copied()
+    }
+}
+
+impl fmt::Debug for FileSet {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("FileSet").field("n_files", &self.files.len()).finish()
+    }
+}
+
+#[derive(Debug)]
+pub struct FileSetConfig {
+    n_file_sets: usize,
+    map: fst::Map<Vec<u8>>,
+}
+
+impl Default for FileSetConfig {
+    fn default() -> Self {
+        FileSetConfig::builder().build()
+    }
+}
+
+impl FileSetConfig {
+    pub fn builder() -> FileSetConfigBuilder {
+        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, &mut scratch_space);
+            res[root].insert(file_id, path.clone())
+        }
+        res
+    }
+    fn len(&self) -> usize {
+        self.n_file_sets
+    }
+    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
+    }
+}
+
+pub struct FileSetConfigBuilder {
+    roots: Vec<Vec<VfsPath>>,
+}
+
+impl Default for FileSetConfigBuilder {
+    fn default() -> Self {
+        FileSetConfigBuilder { roots: Vec::new() }
+    }
+}
+
+impl FileSetConfigBuilder {
+    pub fn len(&self) -> usize {
+        self.roots.len()
+    }
+    pub fn add_file_set(&mut self, roots: Vec<VfsPath>) {
+        self.roots.push(roots)
+    }
+    pub fn build(self) -> FileSetConfig {
+        let n_file_sets = self.roots.len() + 1;
+        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
+        }
+    }
+}
+
+#[test]
+fn test_partitioning() {
+    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]);
+}
diff --git a/crates/vfs/src/lib.rs b/crates/vfs/src/lib.rs
new file mode 100644
index 000000000..cdf6f1fd0
--- /dev/null
+++ b/crates/vfs/src/lib.rs
@@ -0,0 +1,140 @@
+//! # Virtual File System
+//!
+//! VFS stores all files read by rust-analyzer. Reading file contents from VFS
+//! always returns the same contents, unless VFS was explicitly modified with
+//! `set_file_contents`. All changes to VFS are logged, and can be retrieved via
+//! `take_changes` method. The pack of changes is then pushed to `salsa` and
+//! triggers incremental recomputation.
+//!
+//! Files in VFS are identified with `FileId`s -- interned paths. The notion of
+//! the path, `VfsPath` is somewhat abstract: at the moment, it is represented
+//! as an `std::path::PathBuf` internally, but this is an implementation detail.
+//!
+//! VFS doesn't do IO or file watching itself. For that, see the `loader`
+//! module. `loader::Handle` is an object-safe trait which abstracts both file
+//! loading and file watching. `Handle` is dynamically configured with a set of
+//! directory entries which should be scanned and watched. `Handle` then
+//! asynchronously pushes file changes. Directory entries are configured in
+//! free-form via list of globs, it's up to the `Handle` to interpret the globs
+//! in any specific way.
+//!
+//! A simple `WalkdirLoaderHandle` is provided, which doesn't implement watching
+//! and just scans the directory using walkdir.
+//!
+//! VFS stores a flat list of files. `FileSet` can partition this list of files
+//! into disjoint sets of files. Traversal-like operations (including getting
+//! the neighbor file by the relative path) are handled by the `FileSet`.
+//! `FileSet`s are also pushed to salsa and cause it to re-check `mod foo;`
+//! declarations when files are created or deleted.
+//!
+//! `file_set::FileSet` and `loader::Entry` play similar, but different roles.
+//! Both specify the "set of paths/files", one is geared towards file watching,
+//! the other towards salsa changes. In particular, single `file_set::FileSet`
+//! may correspond to several `loader::Entry`. For example, a crate from
+//! crates.io which uses code generation would have two `Entries` -- for sources
+//! in `~/.cargo`, and for generated code in `./target/debug/build`. It will
+//! have a single `FileSet` which unions the two sources.
+mod vfs_path;
+mod path_interner;
+pub mod file_set;
+pub mod loader;
+
+use std::{fmt, mem};
+
+use crate::path_interner::PathInterner;
+
+pub use crate::vfs_path::VfsPath;
+pub use paths::{AbsPath, AbsPathBuf};
+
+#[derive(Copy, Clone, Debug, Ord, PartialOrd, Eq, PartialEq, Hash)]
+pub struct FileId(pub u32);
+
+#[derive(Default)]
+pub struct Vfs {
+    interner: PathInterner,
+    data: Vec<Option<Vec<u8>>>,
+    changes: Vec<ChangedFile>,
+}
+
+pub struct ChangedFile {
+    pub file_id: FileId,
+    pub change_kind: ChangeKind,
+}
+
+impl ChangedFile {
+    pub fn exists(&self) -> bool {
+        self.change_kind != ChangeKind::Delete
+    }
+    pub fn is_created_or_deleted(&self) -> bool {
+        matches!(self.change_kind, ChangeKind::Create | ChangeKind::Delete)
+    }
+}
+
+#[derive(Eq, PartialEq, Copy, Clone, Debug)]
+pub enum ChangeKind {
+    Create,
+    Modify,
+    Delete,
+}
+
+impl Vfs {
+    pub fn len(&self) -> usize {
+        self.data.len()
+    }
+    pub fn file_id(&self, path: &VfsPath) -> Option<FileId> {
+        self.interner.get(path).filter(|&it| self.get(it).is_some())
+    }
+    pub fn file_path(&self, file_id: FileId) -> VfsPath {
+        self.interner.lookup(file_id).clone()
+    }
+    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)> + '_ {
+        (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);
+                (file_id, path)
+            })
+    }
+    pub fn set_file_contents(&mut self, path: VfsPath, contents: Option<Vec<u8>>) {
+        let file_id = self.alloc_file_id(path);
+        let change_kind = match (&self.get(file_id), &contents) {
+            (None, None) => return,
+            (None, Some(_)) => ChangeKind::Create,
+            (Some(_), None) => ChangeKind::Delete,
+            (Some(old), Some(new)) if old == new => return,
+            (Some(_), Some(_)) => ChangeKind::Modify,
+        };
+
+        *self.get_mut(file_id) = contents;
+        self.changes.push(ChangedFile { file_id, change_kind })
+    }
+    pub fn has_changes(&self) -> bool {
+        !self.changes.is_empty()
+    }
+    pub fn take_changes(&mut self) -> Vec<ChangedFile> {
+        mem::take(&mut self.changes)
+    }
+    fn alloc_file_id(&mut self, path: VfsPath) -> FileId {
+        let file_id = self.interner.intern(path);
+        let idx = file_id.0 as usize;
+        let len = self.data.len().max(idx + 1);
+        self.data.resize_with(len, || None);
+        file_id
+    }
+    fn get(&self, file_id: FileId) -> &Option<Vec<u8>> {
+        &self.data[file_id.0 as usize]
+    }
+    fn get_mut(&mut self, file_id: FileId) -> &mut Option<Vec<u8>> {
+        &mut self.data[file_id.0 as usize]
+    }
+}
+
+impl fmt::Debug for Vfs {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("Vfs").field("n_files", &self.data.len()).finish()
+    }
+}
diff --git a/crates/vfs/src/loader.rs b/crates/vfs/src/loader.rs
new file mode 100644
index 000000000..6de2e5b3f
--- /dev/null
+++ b/crates/vfs/src/loader.rs
@@ -0,0 +1,71 @@
+//! Object safe interface for file watching and reading.
+use std::fmt;
+
+use paths::{AbsPath, AbsPathBuf};
+
+#[derive(Debug)]
+pub enum Entry {
+    Files(Vec<AbsPathBuf>),
+    Directory { path: AbsPathBuf, include: Vec<String> },
+}
+
+#[derive(Debug)]
+pub struct Config {
+    pub load: Vec<Entry>,
+    pub watch: Vec<usize>,
+}
+
+pub enum Message {
+    Progress { n_total: usize, n_done: usize },
+    Loaded { files: Vec<(AbsPathBuf, Option<Vec<u8>>)> },
+}
+
+pub type Sender = Box<dyn Fn(Message) + Send>;
+
+pub trait Handle: fmt::Debug {
+    fn spawn(sender: Sender) -> Self
+    where
+        Self: Sized;
+    fn set_config(&mut self, config: Config);
+    fn invalidate(&mut self, path: AbsPathBuf);
+    fn load_sync(&mut self, path: &AbsPath) -> Option<Vec<u8>>;
+}
+
+impl Entry {
+    pub fn rs_files_recursively(base: AbsPathBuf) -> Entry {
+        Entry::Directory { path: base, include: globs(&["*.rs", "!/.git/"]) }
+    }
+    pub fn local_cargo_package(base: AbsPathBuf) -> Entry {
+        Entry::Directory { path: base, include: globs(&["*.rs", "!/target/", "!/.git/"]) }
+    }
+    pub fn cargo_package_dependency(base: AbsPathBuf) -> Entry {
+        Entry::Directory {
+            path: base,
+            include: globs(&["*.rs", "!/tests/", "!/examples/", "!/benches/", "!/.git/"]),
+        }
+    }
+}
+
+fn globs(globs: &[&str]) -> Vec<String> {
+    globs.iter().map(|it| it.to_string()).collect()
+}
+
+impl fmt::Debug for Message {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Message::Loaded { files } => {
+                f.debug_struct("Loaded").field("n_files", &files.len()).finish()
+            }
+            Message::Progress { n_total, n_done } => f
+                .debug_struct("Progress")
+                .field("n_total", n_total)
+                .field("n_done", n_done)
+                .finish(),
+        }
+    }
+}
+
+#[test]
+fn handle_is_object_safe() {
+    fn _assert(_: &dyn Handle) {}
+}
diff --git a/crates/vfs/src/path_interner.rs b/crates/vfs/src/path_interner.rs
new file mode 100644
index 000000000..4f70d61e8
--- /dev/null
+++ b/crates/vfs/src/path_interner.rs
@@ -0,0 +1,31 @@
+//! Maps paths to compact integer ids. We don't care about clearings paths which
+//! no longer exist -- the assumption is total size of paths we ever look at is
+//! not too big.
+use rustc_hash::FxHashMap;
+
+use crate::{FileId, VfsPath};
+
+#[derive(Default)]
+pub(crate) struct PathInterner {
+    map: FxHashMap<VfsPath, FileId>,
+    vec: Vec<VfsPath>,
+}
+
+impl PathInterner {
+    pub(crate) fn get(&self, path: &VfsPath) -> Option<FileId> {
+        self.map.get(path).copied()
+    }
+    pub(crate) fn intern(&mut self, path: VfsPath) -> FileId {
+        if let Some(id) = self.get(&path) {
+            return id;
+        }
+        let id = FileId(self.vec.len() as u32);
+        self.map.insert(path.clone(), id);
+        self.vec.push(path);
+        id
+    }
+
+    pub(crate) fn lookup(&self, id: FileId) -> &VfsPath {
+        &self.vec[id.0 as usize]
+    }
+}
diff --git a/crates/vfs/src/vfs_path.rs b/crates/vfs/src/vfs_path.rs
new file mode 100644
index 000000000..04a42264e
--- /dev/null
+++ b/crates/vfs/src/vfs_path.rs
@@ -0,0 +1,146 @@
+//! Abstract-ish representation of paths for VFS.
+use std::fmt;
+
+use paths::{AbsPath, AbsPathBuf};
+
+/// Long-term, we want to support files which do not reside in the file-system,
+/// so we treat VfsPaths as opaque identifiers.
+#[derive(Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
+pub struct VfsPath(VfsPathRepr);
+
+impl VfsPath {
+    /// Creates an "in-memory" path from `/`-separates string.
+    /// This is most useful for testing, to avoid windows/linux differences
+    pub fn new_virtual_path(path: String) -> VfsPath {
+        assert!(path.starts_with('/'));
+        VfsPath(VfsPathRepr::VirtualPath(VirtualPath(path)))
+    }
+
+    pub fn as_path(&self) -> Option<&AbsPath> {
+        match &self.0 {
+            VfsPathRepr::PathBuf(it) => Some(it.as_path()),
+            VfsPathRepr::VirtualPath(_) => None,
+        }
+    }
+    pub fn join(&self, path: &str) -> Option<VfsPath> {
+        match &self.0 {
+            VfsPathRepr::PathBuf(it) => {
+                let res = it.join(path).normalize();
+                Some(VfsPath(VfsPathRepr::PathBuf(res)))
+            }
+            VfsPathRepr::VirtualPath(it) => {
+                let res = it.join(path)?;
+                Some(VfsPath(VfsPathRepr::VirtualPath(res)))
+            }
+        }
+    }
+    pub fn pop(&mut self) -> bool {
+        match &mut self.0 {
+            VfsPathRepr::PathBuf(it) => it.pop(),
+            VfsPathRepr::VirtualPath(it) => it.pop(),
+        }
+    }
+    pub fn starts_with(&self, other: &VfsPath) -> bool {
+        match (&self.0, &other.0) {
+            (VfsPathRepr::PathBuf(lhs), VfsPathRepr::PathBuf(rhs)) => lhs.starts_with(rhs),
+            (VfsPathRepr::PathBuf(_), _) => false,
+            (VfsPathRepr::VirtualPath(lhs), VfsPathRepr::VirtualPath(rhs)) => lhs.starts_with(rhs),
+            (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)]
+enum VfsPathRepr {
+    PathBuf(AbsPathBuf),
+    VirtualPath(VirtualPath),
+}
+
+impl From<AbsPathBuf> for VfsPath {
+    fn from(v: AbsPathBuf) -> Self {
+        VfsPath(VfsPathRepr::PathBuf(v.normalize()))
+    }
+}
+
+impl fmt::Display for VfsPath {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match &self.0 {
+            VfsPathRepr::PathBuf(it) => fmt::Display::fmt(&it.display(), f),
+            VfsPathRepr::VirtualPath(VirtualPath(it)) => fmt::Display::fmt(it, f),
+        }
+    }
+}
+
+impl fmt::Debug for VfsPath {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Debug::fmt(&self.0, f)
+    }
+}
+
+impl fmt::Debug for VfsPathRepr {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match &self {
+            VfsPathRepr::PathBuf(it) => fmt::Debug::fmt(&it.display(), f),
+            VfsPathRepr::VirtualPath(VirtualPath(it)) => fmt::Debug::fmt(&it, f),
+        }
+    }
+}
+
+#[derive(Debug, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
+struct VirtualPath(String);
+
+impl VirtualPath {
+    fn starts_with(&self, other: &VirtualPath) -> bool {
+        self.0.starts_with(&other.0)
+    }
+    fn pop(&mut self) -> bool {
+        let pos = match self.0.rfind('/') {
+            Some(pos) => pos,
+            None => return false,
+        };
+        self.0 = self.0[..pos].to_string();
+        true
+    }
+    fn join(&self, mut path: &str) -> Option<VirtualPath> {
+        let mut res = self.clone();
+        while path.starts_with("../") {
+            if !res.pop() {
+                return None;
+            }
+            path = &path["../".len()..]
+        }
+        res.0 = format!("{}/{}", res.0, path);
+        Some(res)
+    }
+}