5 files changed, 597 insertions, 0 deletions

diff --git a/crates/ra_vfs/Cargo.toml b/crates/ra_vfs/Cargo.toml
new file mode 100644
index 000000000..ccea8a866
--- /dev/null
+++ b/crates/ra_vfs/Cargo.toml
@@ -0,0 +1,17 @@
+[package]
+edition = "2018"
+name = "ra_vfs"
+version = "0.1.0"
+authors = ["Aleksey Kladov <[email protected]>"]
+
+[dependencies]
+walkdir = "2.2.7"
+relative-path = "0.4.0"
+rustc-hash = "1.0"
+crossbeam-channel = "0.2.4"
+log = "0.4.6"
+
+thread_worker = { path = "../thread_worker" }
+
+[dev-dependencies]
+tempfile = "3"
diff --git a/crates/ra_vfs/src/arena.rs b/crates/ra_vfs/src/arena.rs
new file mode 100644
index 000000000..6b42ae26d
--- /dev/null
+++ b/crates/ra_vfs/src/arena.rs
@@ -0,0 +1,53 @@
+use std::{
+    marker::PhantomData,
+    ops::{Index, IndexMut},
+};
+
+#[derive(Clone, Debug)]
+pub(crate) struct Arena<ID: ArenaId, T> {
+    data: Vec<T>,
+    _ty: PhantomData<ID>,
+}
+
+pub(crate) trait ArenaId {
+    fn from_u32(id: u32) -> Self;
+    fn to_u32(self) -> u32;
+}
+
+impl<ID: ArenaId, T> Arena<ID, T> {
+    pub fn alloc(&mut self, value: T) -> ID {
+        let id = self.data.len() as u32;
+        self.data.push(value);
+        ID::from_u32(id)
+    }
+    pub fn iter<'a>(&'a self) -> impl Iterator<Item = (ID, &'a T)> {
+        self.data
+            .iter()
+            .enumerate()
+            .map(|(idx, value)| (ID::from_u32(idx as u32), value))
+    }
+}
+
+impl<ID: ArenaId, T> Default for Arena<ID, T> {
+    fn default() -> Arena<ID, T> {
+        Arena {
+            data: Vec::new(),
+            _ty: PhantomData,
+        }
+    }
+}
+
+impl<ID: ArenaId, T> Index<ID> for Arena<ID, T> {
+    type Output = T;
+    fn index(&self, idx: ID) -> &T {
+        let idx = idx.to_u32() as usize;
+        &self.data[idx]
+    }
+}
+
+impl<ID: ArenaId, T> IndexMut<ID> for Arena<ID, T> {
+    fn index_mut(&mut self, idx: ID) -> &mut T {
+        let idx = idx.to_u32() as usize;
+        &mut self.data[idx]
+    }
+}
diff --git a/crates/ra_vfs/src/io.rs b/crates/ra_vfs/src/io.rs
new file mode 100644
index 000000000..be400bae9
--- /dev/null
+++ b/crates/ra_vfs/src/io.rs
@@ -0,0 +1,76 @@
+use std::{
+    fmt,
+    fs,
+    path::{Path, PathBuf},
+};
+
+use walkdir::{DirEntry, WalkDir};
+use thread_worker::{WorkerHandle};
+use relative_path::RelativePathBuf;
+
+use crate::VfsRoot;
+
+pub(crate) struct Task {
+    pub(crate) root: VfsRoot,
+    pub(crate) path: PathBuf,
+    pub(crate) filter: Box<Fn(&DirEntry) -> bool + Send>,
+}
+
+pub struct TaskResult {
+    pub(crate) root: VfsRoot,
+    pub(crate) files: Vec<(RelativePathBuf, String)>,
+}
+
+impl fmt::Debug for TaskResult {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.write_str("TaskResult { ... }")
+    }
+}
+
+pub(crate) type Worker = thread_worker::Worker<Task, TaskResult>;
+
+pub(crate) fn start() -> (Worker, WorkerHandle) {
+    thread_worker::spawn("vfs", 128, |input_receiver, output_sender| {
+        input_receiver
+            .map(handle_task)
+            .for_each(|it| output_sender.send(it))
+    })
+}
+
+fn handle_task(task: Task) -> TaskResult {
+    let Task { root, path, filter } = task;
+    log::debug!("loading {} ...", path.as_path().display());
+    let files = load_root(path.as_path(), &*filter);
+    log::debug!("... loaded {}", path.as_path().display());
+    TaskResult { root, files }
+}
+
+fn load_root(root: &Path, filter: &dyn Fn(&DirEntry) -> bool) -> Vec<(RelativePathBuf, String)> {
+    let mut res = Vec::new();
+    for entry in WalkDir::new(root).into_iter().filter_entry(filter) {
+        let entry = match entry {
+            Ok(entry) => entry,
+            Err(e) => {
+                log::warn!("watcher error: {}", e);
+                continue;
+            }
+        };
+        if !entry.file_type().is_file() {
+            continue;
+        }
+        let path = entry.path();
+        if path.extension().and_then(|os| os.to_str()) != Some("rs") {
+            continue;
+        }
+        let text = match fs::read_to_string(path) {
+            Ok(text) => text,
+            Err(e) => {
+                log::warn!("watcher error: {}", e);
+                continue;
+            }
+        };
+        let path = RelativePathBuf::from_path(path.strip_prefix(root).unwrap()).unwrap();
+        res.push((path.to_owned(), text))
+    }
+    res
+}
diff --git a/crates/ra_vfs/src/lib.rs b/crates/ra_vfs/src/lib.rs
new file mode 100644
index 000000000..4de07b093
--- /dev/null
+++ b/crates/ra_vfs/src/lib.rs
@@ -0,0 +1,350 @@
+//! VFS stands for Virtual File System.
+//!
+//! When doing analysis, we don't want to do any IO, we want to keep all source
+//! code in memory. However, the actual source code is stored on disk, so you
+//! component which does this.
+//! need to get it into the memory in the first place somehow. VFS is the
+//!
+//! It also is responsible for watching the disk for changes, and for merging
+//! editor state (modified, unsaved files) with disk state.
+//!
+//! VFS is based on a concept of roots: a set of directories on the file system
+//! whihc are watched for changes. Typically, there will be a root for each
+//! Cargo package.
+mod arena;
+mod io;
+
+use std::{
+    fmt,
+    mem,
+    thread,
+    cmp::Reverse,
+    path::{Path, PathBuf},
+    ffi::OsStr,
+    sync::Arc,
+    fs,
+};
+
+use rustc_hash::{FxHashMap, FxHashSet};
+use relative_path::RelativePathBuf;
+use crossbeam_channel::Receiver;
+use walkdir::DirEntry;
+use thread_worker::{WorkerHandle};
+
+use crate::{
+    arena::{ArenaId, Arena},
+};
+
+pub use crate::io::TaskResult as VfsTask;
+
+/// `RootFilter` is a predicate that checks if a file can belong to a root. If
+/// several filters match a file (nested dirs), the most nested one wins.
+struct RootFilter {
+    root: PathBuf,
+    file_filter: fn(&Path) -> bool,
+}
+
+impl RootFilter {
+    fn new(root: PathBuf) -> RootFilter {
+        RootFilter {
+            root,
+            file_filter: has_rs_extension,
+        }
+    }
+    /// Check if this root can contain `path`. NB: even if this returns
+    /// true, the `path` might actually be conained in some nested root.
+    fn can_contain(&self, path: &Path) -> Option<RelativePathBuf> {
+        if !(self.file_filter)(path) {
+            return None;
+        }
+        if !(path.starts_with(&self.root)) {
+            return None;
+        }
+        let path = path.strip_prefix(&self.root).unwrap();
+        let path = RelativePathBuf::from_path(path).unwrap();
+        Some(path)
+    }
+}
+
+fn has_rs_extension(p: &Path) -> bool {
+    p.extension() == Some(OsStr::new("rs"))
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
+pub struct VfsRoot(pub u32);
+
+impl ArenaId for VfsRoot {
+    fn from_u32(idx: u32) -> VfsRoot {
+        VfsRoot(idx)
+    }
+    fn to_u32(self) -> u32 {
+        self.0
+    }
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
+pub struct VfsFile(pub u32);
+
+impl ArenaId for VfsFile {
+    fn from_u32(idx: u32) -> VfsFile {
+        VfsFile(idx)
+    }
+    fn to_u32(self) -> u32 {
+        self.0
+    }
+}
+
+struct VfsFileData {
+    root: VfsRoot,
+    path: RelativePathBuf,
+    text: Arc<String>,
+}
+
+pub struct Vfs {
+    roots: Arena<VfsRoot, RootFilter>,
+    files: Arena<VfsFile, VfsFileData>,
+    root2files: FxHashMap<VfsRoot, FxHashSet<VfsFile>>,
+    pending_changes: Vec<VfsChange>,
+    worker: io::Worker,
+    worker_handle: WorkerHandle,
+}
+
+impl fmt::Debug for Vfs {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.write_str("Vfs { ... }")
+    }
+}
+
+impl Vfs {
+    pub fn new(mut roots: Vec<PathBuf>) -> (Vfs, Vec<VfsRoot>) {
+        let (worker, worker_handle) = io::start();
+
+        let mut res = Vfs {
+            roots: Arena::default(),
+            files: Arena::default(),
+            root2files: FxHashMap::default(),
+            worker,
+            worker_handle,
+            pending_changes: Vec::new(),
+        };
+
+        // A hack to make nesting work.
+        roots.sort_by_key(|it| Reverse(it.as_os_str().len()));
+        for (i, path) in roots.iter().enumerate() {
+            let root = res.roots.alloc(RootFilter::new(path.clone()));
+            res.root2files.insert(root, Default::default());
+            let nested = roots[..i]
+                .iter()
+                .filter(|it| it.starts_with(path))
+                .map(|it| it.clone())
+                .collect::<Vec<_>>();
+            let filter = move |entry: &DirEntry| {
+                if entry.file_type().is_file() {
+                    has_rs_extension(entry.path())
+                } else {
+                    nested.iter().all(|it| it != entry.path())
+                }
+            };
+            let task = io::Task {
+                root,
+                path: path.clone(),
+                filter: Box::new(filter),
+            };
+            res.worker.inp.send(task);
+        }
+        let roots = res.roots.iter().map(|(id, _)| id).collect();
+        (res, roots)
+    }
+
+    pub fn root2path(&self, root: VfsRoot) -> PathBuf {
+        self.roots[root].root.clone()
+    }
+
+    pub fn path2file(&self, path: &Path) -> Option<VfsFile> {
+        if let Some((_root, _path, Some(file))) = self.find_root(path) {
+            return Some(file);
+        }
+        None
+    }
+
+    pub fn file2path(&self, file: VfsFile) -> PathBuf {
+        let rel_path = &self.files[file].path;
+        let root_path = &self.roots[self.files[file].root].root;
+        rel_path.to_path(root_path)
+    }
+
+    pub fn file_for_path(&self, path: &Path) -> Option<VfsFile> {
+        if let Some((_root, _path, Some(file))) = self.find_root(path) {
+            return Some(file);
+        }
+        None
+    }
+
+    pub fn load(&mut self, path: &Path) -> Option<VfsFile> {
+        if let Some((root, rel_path, file)) = self.find_root(path) {
+            return if let Some(file) = file {
+                Some(file)
+            } else {
+                let text = fs::read_to_string(path).unwrap_or_default();
+                let text = Arc::new(text);
+                let file = self.add_file(root, rel_path.clone(), Arc::clone(&text));
+                let change = VfsChange::AddFile {
+                    file,
+                    text,
+                    root,
+                    path: rel_path,
+                };
+                self.pending_changes.push(change);
+                Some(file)
+            };
+        }
+        None
+    }
+
+    pub fn task_receiver(&self) -> &Receiver<io::TaskResult> {
+        &self.worker.out
+    }
+
+    pub fn handle_task(&mut self, task: io::TaskResult) {
+        let mut files = Vec::new();
+        // While we were scanning the root in the backgound, a file might have
+        // been open in the editor, so we need to account for that.
+        let exising = self.root2files[&task.root]
+            .iter()
+            .map(|&file| (self.files[file].path.clone(), file))
+            .collect::<FxHashMap<_, _>>();
+        for (path, text) in task.files {
+            if let Some(&file) = exising.get(&path) {
+                let text = Arc::clone(&self.files[file].text);
+                files.push((file, path, text));
+                continue;
+            }
+            let text = Arc::new(text);
+            let file = self.add_file(task.root, path.clone(), Arc::clone(&text));
+            files.push((file, path, text));
+        }
+
+        let change = VfsChange::AddRoot {
+            root: task.root,
+            files,
+        };
+        self.pending_changes.push(change);
+    }
+
+    pub fn add_file_overlay(&mut self, path: &Path, text: String) -> Option<VfsFile> {
+        let mut res = None;
+        if let Some((root, path, file)) = self.find_root(path) {
+            let text = Arc::new(text);
+            let change = if let Some(file) = file {
+                res = Some(file);
+                self.change_file(file, Arc::clone(&text));
+                VfsChange::ChangeFile { file, text }
+            } else {
+                let file = self.add_file(root, path.clone(), Arc::clone(&text));
+                res = Some(file);
+                VfsChange::AddFile {
+                    file,
+                    text,
+                    root,
+                    path,
+                }
+            };
+            self.pending_changes.push(change);
+        }
+        res
+    }
+
+    pub fn change_file_overlay(&mut self, path: &Path, new_text: String) {
+        if let Some((_root, _path, file)) = self.find_root(path) {
+            let file = file.expect("can't change a file which wasn't added");
+            let text = Arc::new(new_text);
+            self.change_file(file, Arc::clone(&text));
+            let change = VfsChange::ChangeFile { file, text };
+            self.pending_changes.push(change);
+        }
+    }
+
+    pub fn remove_file_overlay(&mut self, path: &Path) -> Option<VfsFile> {
+        let mut res = None;
+        if let Some((root, path, file)) = self.find_root(path) {
+            let file = file.expect("can't remove a file which wasn't added");
+            res = Some(file);
+            let full_path = path.to_path(&self.roots[root].root);
+            let change = if let Ok(text) = fs::read_to_string(&full_path) {
+                let text = Arc::new(text);
+                self.change_file(file, Arc::clone(&text));
+                VfsChange::ChangeFile { file, text }
+            } else {
+                self.remove_file(file);
+                VfsChange::RemoveFile { root, file, path }
+            };
+            self.pending_changes.push(change);
+        }
+        res
+    }
+
+    pub fn commit_changes(&mut self) -> Vec<VfsChange> {
+        mem::replace(&mut self.pending_changes, Vec::new())
+    }
+
+    /// Sutdown the VFS and terminate the background watching thread.
+    pub fn shutdown(self) -> thread::Result<()> {
+        let _ = self.worker.shutdown();
+        self.worker_handle.shutdown()
+    }
+
+    fn add_file(&mut self, root: VfsRoot, path: RelativePathBuf, text: Arc<String>) -> VfsFile {
+        let data = VfsFileData { root, path, text };
+        let file = self.files.alloc(data);
+        self.root2files.get_mut(&root).unwrap().insert(file);
+        file
+    }
+
+    fn change_file(&mut self, file: VfsFile, new_text: Arc<String>) {
+        self.files[file].text = new_text;
+    }
+
+    fn remove_file(&mut self, file: VfsFile) {
+        //FIXME: use arena with removal
+        self.files[file].text = Default::default();
+        self.files[file].path = Default::default();
+        let root = self.files[file].root;
+        let removed = self.root2files.get_mut(&root).unwrap().remove(&file);
+        assert!(removed);
+    }
+
+    fn find_root(&self, path: &Path) -> Option<(VfsRoot, RelativePathBuf, Option<VfsFile>)> {
+        let (root, path) = self
+            .roots
+            .iter()
+            .find_map(|(root, data)| data.can_contain(path).map(|it| (root, it)))?;
+        let file = self.root2files[&root]
+            .iter()
+            .map(|&it| it)
+            .find(|&file| self.files[file].path == path);
+        Some((root, path, file))
+    }
+}
+
+#[derive(Debug, Clone)]
+pub enum VfsChange {
+    AddRoot {
+        root: VfsRoot,
+        files: Vec<(VfsFile, RelativePathBuf, Arc<String>)>,
+    },
+    AddFile {
+        root: VfsRoot,
+        file: VfsFile,
+        path: RelativePathBuf,
+        text: Arc<String>,
+    },
+    RemoveFile {
+        root: VfsRoot,
+        file: VfsFile,
+        path: RelativePathBuf,
+    },
+    ChangeFile {
+        file: VfsFile,
+        text: Arc<String>,
+    },
+}
diff --git a/crates/ra_vfs/tests/vfs.rs b/crates/ra_vfs/tests/vfs.rs
new file mode 100644
index 000000000..f56fc4603
--- /dev/null
+++ b/crates/ra_vfs/tests/vfs.rs
@@ -0,0 +1,101 @@
+use std::{
+    fs,
+    collections::HashSet,
+};
+
+use tempfile::tempdir;
+
+use ra_vfs::{Vfs, VfsChange};
+
+#[test]
+fn test_vfs_works() -> std::io::Result<()> {
+    let files = [
+        ("a/foo.rs", "hello"),
+        ("a/bar.rs", "world"),
+        ("a/b/baz.rs", "nested hello"),
+    ];
+
+    let dir = tempdir()?;
+    for (path, text) in files.iter() {
+        let file_path = dir.path().join(path);
+        fs::create_dir_all(file_path.parent().unwrap())?;
+        fs::write(file_path, text)?
+    }
+
+    let a_root = dir.path().join("a");
+    let b_root = dir.path().join("a/b");
+
+    let (mut vfs, _) = Vfs::new(vec![a_root, b_root]);
+    for _ in 0..2 {
+        let task = vfs.task_receiver().recv().unwrap();
+        vfs.handle_task(task);
+    }
+    {
+        let files = vfs
+            .commit_changes()
+            .into_iter()
+            .flat_map(|change| {
+                let files = match change {
+                    VfsChange::AddRoot { files, .. } => files,
+                    _ => panic!("unexpected change"),
+                };
+                files.into_iter().map(|(_id, path, text)| {
+                    let text: String = (&*text).clone();
+                    (format!("{}", path.display()), text)
+                })
+            })
+            .collect::<HashSet<_>>();
+
+        let expected_files = [
+            ("foo.rs", "hello"),
+            ("bar.rs", "world"),
+            ("baz.rs", "nested hello"),
+        ]
+        .iter()
+        .map(|(path, text)| (path.to_string(), text.to_string()))
+        .collect::<HashSet<_>>();
+
+        assert_eq!(files, expected_files);
+    }
+
+    vfs.add_file_overlay(&dir.path().join("a/b/baz.rs"), "quux".to_string());
+    let change = vfs.commit_changes().pop().unwrap();
+    match change {
+        VfsChange::ChangeFile { text, .. } => assert_eq!(&*text, "quux"),
+        _ => panic!("unexpected change"),
+    }
+
+    vfs.change_file_overlay(&dir.path().join("a/b/baz.rs"), "m".to_string());
+    let change = vfs.commit_changes().pop().unwrap();
+    match change {
+        VfsChange::ChangeFile { text, .. } => assert_eq!(&*text, "m"),
+        _ => panic!("unexpected change"),
+    }
+
+    vfs.remove_file_overlay(&dir.path().join("a/b/baz.rs"));
+    let change = vfs.commit_changes().pop().unwrap();
+    match change {
+        VfsChange::ChangeFile { text, .. } => assert_eq!(&*text, "nested hello"),
+        _ => panic!("unexpected change"),
+    }
+
+    vfs.add_file_overlay(&dir.path().join("a/b/spam.rs"), "spam".to_string());
+    let change = vfs.commit_changes().pop().unwrap();
+    match change {
+        VfsChange::AddFile { text, path, .. } => {
+            assert_eq!(&*text, "spam");
+            assert_eq!(path, "spam.rs");
+        }
+        _ => panic!("unexpected change"),
+    }
+
+    vfs.remove_file_overlay(&dir.path().join("a/b/spam.rs"));
+    let change = vfs.commit_changes().pop().unwrap();
+    match change {
+        VfsChange::RemoveFile { .. } => (),
+        _ => panic!("unexpected change"),
+    }
+
+    vfs.shutdown().unwrap();
+    Ok(())
+}