Merge #67

67: Salsa r=matklad a=matklad

The aim of this PR is to transition from rather ad-hock FileData and ModuleMap caching strategy to something resembling a general-purpose red-green engine. 

Ideally, we shouldn't recompute ModuleMap at all, unless the set of mod decls or files changes.



Co-authored-by: Aleksey Kladov <[email protected]>

11 files changed, 810 insertions, 449 deletions

diff --git a/crates/libanalysis/Cargo.toml b/crates/libanalysis/Cargo.toml
index 4d565e95f..88f29d7c8 100644
--- a/crates/libanalysis/Cargo.toml
+++ b/crates/libanalysis/Cargo.toml
@@ -11,8 +11,10 @@ parking_lot = "0.6.3"
 once_cell = "0.1.5"
 rayon = "1.0.2"
 fst = "0.3.1"
+im = "12.0.0"
 libsyntax2 = { path = "../libsyntax2" }
 libeditor = { path = "../libeditor" }
+salsa = { path = "../salsa" }
 
 [dev-dependencies]
 test_utils = { path = "../test_utils" }
diff --git a/crates/libanalysis/src/db/imp.rs b/crates/libanalysis/src/db/imp.rs
new file mode 100644
index 000000000..f26be1046
--- /dev/null
+++ b/crates/libanalysis/src/db/imp.rs
@@ -0,0 +1,152 @@
+use std::{
+    sync::Arc,
+    any::Any,
+    hash::{Hash, Hasher},
+    collections::hash_map::{DefaultHasher, HashMap},
+    iter,
+};
+use salsa;
+use {FileId, imp::FileResolverImp};
+use super::{State, Query, QueryCtx};
+
+pub(super) type Data = Arc<Any + Send + Sync + 'static>;
+
+#[derive(Debug)]
+pub(super) struct Db {
+    names: Arc<HashMap<salsa::QueryTypeId, &'static str>>,
+    pub(super) imp: salsa::Db<State, Data>,
+}
+
+impl Db {
+    pub(super) fn new(mut reg: QueryRegistry) -> Db {
+        let config = reg.config.take().unwrap();
+        Db {
+            names: Arc::new(reg.names),
+            imp: salsa::Db::new(config, State::default())
+        }
+    }
+    pub(crate) fn with_changes(&self, new_state: State, changed_files: &[FileId], resolver_changed: bool) -> Db {
+        let names = self.names.clone();
+        let mut invalidations = salsa::Invalidations::new();
+        invalidations.invalidate(FILE_TEXT, changed_files.iter().map(hash).map(salsa::InputFingerprint));
+        if resolver_changed {
+            invalidations.invalidate(FILE_SET, iter::once(salsa::InputFingerprint(hash(&()))));
+        } else {
+            invalidations.invalidate(FILE_SET, iter::empty());
+        }
+        let imp = self.imp.with_ground_data(
+            new_state,
+            invalidations,
+        );
+        Db { names, imp }
+    }
+    pub(super) fn extract_trace(&self, ctx: &salsa::QueryCtx<State, Data>) -> Vec<&'static str> {
+        ctx.trace().into_iter().map(|it| self.names[&it]).collect()
+    }
+}
+
+pub(crate) trait EvalQuery {
+    type Params;
+    type Output;
+    fn query_type(&self) -> salsa::QueryTypeId;
+    fn f(&self) -> salsa::QueryFn<State, Data>;
+    fn get(&self, &QueryCtx, Self::Params) -> Arc<Self::Output>;
+}
+
+impl<T, R> EvalQuery for Query<T, R>
+where
+    T: Hash + Send + Sync + 'static,
+    R: Hash + Send + Sync + 'static,
+{
+    type Params = T;
+    type Output = R;
+    fn query_type(&self) -> salsa::QueryTypeId {
+        salsa::QueryTypeId(self.0)
+    }
+    fn f(&self) -> salsa::QueryFn<State, Data> {
+        let f = self.1;
+        Box::new(move |ctx, data| {
+            let ctx = QueryCtx { imp: ctx };
+            let data: &T = data.downcast_ref().unwrap();
+            let res = f(ctx, data);
+            let h = hash(&res);
+            (Arc::new(res), salsa::OutputFingerprint(h))
+        })
+    }
+    fn get(&self, ctx: &QueryCtx, params: Self::Params) -> Arc<Self::Output> {
+        let query_id = salsa::QueryId(
+            self.query_type(),
+            salsa::InputFingerprint(hash(&params)),
+        );
+        let res = ctx.imp.get(query_id, Arc::new(params));
+        res.downcast().unwrap()
+    }
+}
+
+pub(super) struct QueryRegistry {
+    config: Option<salsa::QueryConfig<State, Data>>,
+    names: HashMap<salsa::QueryTypeId, &'static str>,
+}
+
+impl QueryRegistry {
+    pub(super) fn new() -> QueryRegistry {
+        let mut config = salsa::QueryConfig::<State, Data>::new();
+        config = config.with_ground_query(
+            FILE_TEXT, Box::new(|state, params| {
+                let file_id: &FileId = params.downcast_ref().unwrap();
+                let res = state.file_map[file_id].clone();
+                let fingerprint = salsa::OutputFingerprint(hash(&res));
+                (res, fingerprint)
+            })
+        );
+        config = config.with_ground_query(
+            FILE_SET, Box::new(|state, _params| {
+                let file_ids: Vec<FileId> = state.file_map.keys().cloned().collect();
+                let hash = hash(&file_ids);
+                let file_resolver = state.file_resolver.clone();
+                let res = (file_ids, file_resolver);
+                let fingerprint = salsa::OutputFingerprint(hash);
+                (Arc::new(res), fingerprint)
+            })
+        );
+        let mut names = HashMap::new();
+        names.insert(FILE_TEXT, "FILE_TEXT");
+        names.insert(FILE_SET, "FILE_SET");
+        QueryRegistry { config: Some(config), names }
+    }
+    pub(super) fn add<Q: EvalQuery>(&mut self, q: Q, name: &'static str) {
+        let id = q.query_type();
+        let prev = self.names.insert(id, name);
+        assert!(prev.is_none(), "duplicate query: {:?}", id);
+        let config = self.config.take().unwrap();
+        let config = config.with_query(id, q.f());
+        self.config= Some(config);
+    }
+}
+
+fn hash<T: Hash>(x: &T) -> u64 {
+    let mut hasher = DefaultHasher::new();
+    x.hash(&mut hasher);
+    hasher.finish()
+}
+
+const FILE_TEXT: salsa::QueryTypeId = salsa::QueryTypeId(0);
+pub(super) fn file_text(ctx: QueryCtx, file_id: FileId) -> Arc<String> {
+    let query_id = salsa::QueryId(
+        FILE_TEXT,
+        salsa::InputFingerprint(hash(&file_id)),
+    );
+    let res = ctx.imp.get(query_id, Arc::new(file_id));
+    res.downcast().unwrap()
+}
+
+const FILE_SET: salsa::QueryTypeId = salsa::QueryTypeId(1);
+pub(super) fn file_set(ctx: QueryCtx) -> Arc<(Vec<FileId>, FileResolverImp)> {
+    let query_id = salsa::QueryId(
+        FILE_SET,
+        salsa::InputFingerprint(hash(&())),
+    );
+    let res = ctx.imp.get(query_id, Arc::new(()));
+    res.downcast().unwrap()
+}
+
diff --git a/crates/libanalysis/src/db/mod.rs b/crates/libanalysis/src/db/mod.rs
new file mode 100644
index 000000000..22769d112
--- /dev/null
+++ b/crates/libanalysis/src/db/mod.rs
@@ -0,0 +1,85 @@
+mod imp;
+
+use std::{
+    sync::Arc,
+};
+use im;
+use salsa;
+use {FileId, imp::FileResolverImp};
+
+#[derive(Debug, Default, Clone)]
+pub(crate) struct State {
+    pub(crate) file_map: im::HashMap<FileId, Arc<String>>,
+    pub(crate) file_resolver: FileResolverImp
+}
+
+#[derive(Debug)]
+pub(crate) struct Db {
+    imp: imp::Db,
+}
+
+#[derive(Clone, Copy)]
+pub(crate) struct QueryCtx<'a> {
+    imp: &'a salsa::QueryCtx<State, imp::Data>,
+}
+
+pub(crate) struct Query<T, R>(pub(crate) u16, pub(crate) fn(QueryCtx, &T) -> R);
+
+pub(crate) struct QueryRegistry {
+    imp: imp::QueryRegistry,
+}
+
+impl Default for Db {
+    fn default() -> Db {
+        Db::new()
+    }
+}
+
+impl Db {
+    pub(crate) fn new() -> Db {
+        let reg = QueryRegistry::new();
+        Db { imp: imp::Db::new(reg.imp) }
+    }
+    pub(crate) fn state(&self) -> &State {
+        self.imp.imp.ground_data()
+    }
+    pub(crate) fn with_changes(&self, new_state: State, changed_files: &[FileId], resolver_changed: bool) -> Db {
+        Db { imp: self.imp.with_changes(new_state, changed_files, resolver_changed) }
+    }
+    pub(crate) fn make_query<F: FnOnce(QueryCtx) -> R, R>(&self, f: F) -> R {
+        let ctx = QueryCtx { imp: &self.imp.imp.query_ctx() };
+        f(ctx)
+    }
+    #[allow(unused)]
+    pub(crate) fn trace_query<F: FnOnce(QueryCtx) -> R, R>(&self, f: F) -> (R, Vec<&'static str>) {
+        let ctx = QueryCtx { imp: &self.imp.imp.query_ctx() };
+        let res = f(ctx);
+        let trace = self.imp.extract_trace(ctx.imp);
+        (res, trace)
+    }
+}
+
+impl<'a> QueryCtx<'a> {
+    pub(crate) fn get<Q: imp::EvalQuery>(&self, q: Q, params: Q::Params) -> Arc<Q::Output> {
+        q.get(self, params)
+    }
+}
+
+pub(crate) fn file_text(ctx: QueryCtx, file_id: FileId) -> Arc<String> {
+    imp::file_text(ctx, file_id)
+}
+
+pub(crate) fn file_set(ctx: QueryCtx) -> Arc<(Vec<FileId>, FileResolverImp)> {
+    imp::file_set(ctx)
+}
+impl QueryRegistry {
+    fn new() -> QueryRegistry {
+        let mut reg = QueryRegistry { imp: imp::QueryRegistry::new() };
+        ::queries::register_queries(&mut reg);
+        ::module_map::register_queries(&mut reg);
+        reg
+    }
+    pub(crate) fn add<Q: imp::EvalQuery>(&mut self, q: Q, name: &'static str) {
+        self.imp.add(q, name)
+    }
+}
diff --git a/crates/libanalysis/src/descriptors.rs b/crates/libanalysis/src/descriptors.rs
new file mode 100644
index 000000000..93a4158e4
--- /dev/null
+++ b/crates/libanalysis/src/descriptors.rs
@@ -0,0 +1,220 @@
+use std::{
+    collections::BTreeMap,
+};
+use relative_path::RelativePathBuf;
+use libsyntax2::{
+    SmolStr,
+    ast::{self, NameOwner},
+};
+use {
+    FileId,
+    imp::FileResolverImp,
+};
+
+#[derive(Debug, Hash)]
+pub struct ModuleDescriptor {
+    pub submodules: Vec<Submodule>
+}
+
+impl ModuleDescriptor {
+    pub fn new(root: ast::Root) -> ModuleDescriptor {
+        let submodules = modules(root)
+            .map(|(name, _)| Submodule { name })
+            .collect();
+
+        ModuleDescriptor { submodules } }
+}
+
+fn modules<'a>(root: ast::Root<'a>) -> impl Iterator<Item=(SmolStr, ast::Module<'a>)> {
+    root
+        .modules()
+        .filter_map(|module| {
+            let name = module.name()?.text();
+            if !module.has_semi() {
+                return None;
+            }
+            Some((name, module))
+        })
+}
+
+#[derive(Clone, Hash, PartialEq, Eq, Debug)]
+pub struct Submodule {
+    pub name: SmolStr,
+}
+
+#[derive(Hash, Debug)]
+pub(crate) struct ModuleTreeDescriptor {
+    nodes: Vec<NodeData>,
+    links: Vec<LinkData>,
+    file_id2node: BTreeMap<FileId, Node>,
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+struct Node(usize);
+#[derive(Hash, Debug)]
+struct NodeData {
+    file_id: FileId,
+    links: Vec<Link>,
+    parents: Vec<Link>
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+pub(crate) struct Link(usize);
+#[derive(Hash, Debug)]
+struct LinkData {
+    owner: Node,
+    name: SmolStr,
+    points_to: Vec<Node>,
+    problem: Option<Problem>,
+}
+
+
+#[derive(Clone, Debug, Hash)]
+pub enum Problem {
+    UnresolvedModule {
+        candidate: RelativePathBuf,
+    },
+    NotDirOwner {
+        move_to: RelativePathBuf,
+        candidate: RelativePathBuf,
+    }
+}
+
+impl ModuleTreeDescriptor {
+    pub(crate) fn new<'a>(
+        files: impl Iterator<Item=(FileId, &'a ModuleDescriptor)> + Clone,
+        file_resolver: &FileResolverImp,
+    ) -> ModuleTreeDescriptor {
+        let mut file_id2node = BTreeMap::new();
+        let mut nodes: Vec<NodeData> = files.clone().enumerate()
+            .map(|(idx, (file_id, _))| {
+                file_id2node.insert(file_id, Node(idx));
+                NodeData {
+                    file_id,
+                    links: Vec::new(),
+                    parents: Vec::new(),
+                }
+            })
+            .collect();
+        let mut links = Vec::new();
+
+        for (idx, (file_id, descr)) in files.enumerate() {
+            let owner = Node(idx);
+            for sub in descr.submodules.iter() {
+                let link = Link(links.len());
+                nodes[owner.0].links.push(link);
+                let (points_to, problem) = resolve_submodule(file_id, &sub.name, file_resolver);
+                let points_to = points_to
+                    .into_iter()
+                    .map(|file_id| {
+                        let node = file_id2node[&file_id];
+                        nodes[node.0].parents.push(link);
+                        node
+                    })
+                    .collect();
+
+                links.push(LinkData {
+                    owner,
+                    name: sub.name.clone(),
+                    points_to,
+                    problem,
+                })
+
+            }
+        }
+
+        ModuleTreeDescriptor {
+            nodes, links, file_id2node
+        }
+    }
+
+    pub(crate) fn parent_modules(&self, file_id: FileId) -> Vec<Link> {
+        let node = self.file_id2node[&file_id];
+        self.node(node)
+            .parents
+            .clone()
+    }
+    pub(crate) fn child_module_by_name(&self, file_id: FileId, name: &str) -> Vec<FileId> {
+        let node = self.file_id2node[&file_id];
+        self.node(node)
+            .links
+            .iter()
+            .filter(|it| it.name(self) == name)
+            .flat_map(|link| link.points_to(self).iter().map(|&node| self.node(node).file_id))
+            .collect()
+    }
+    pub(crate) fn problems<'a, 'b>(&'b self, file_id: FileId, root: ast::Root<'a>) -> Vec<(ast::Name<'a>, &'b Problem)> {
+        let node = self.file_id2node[&file_id];
+        self.node(node)
+            .links
+            .iter()
+            .filter_map(|&link| {
+                let problem = self.link(link).problem.as_ref()?;
+                let name = link.bind_source(self, root).name()?;
+                Some((name, problem))
+            })
+            .collect()
+    }
+
+    fn node(&self, node: Node) -> &NodeData {
+        &self.nodes[node.0]
+    }
+    fn link(&self, link: Link) -> &LinkData {
+        &self.links[link.0]
+    }
+}
+
+impl Link {
+    pub(crate) fn name(self, tree: &ModuleTreeDescriptor) -> SmolStr {
+        tree.link(self).name.clone()
+    }
+    pub(crate) fn owner(self, tree: &ModuleTreeDescriptor) -> FileId {
+        let owner = tree.link(self).owner;
+        tree.node(owner).file_id
+    }
+    fn points_to(self, tree: &ModuleTreeDescriptor) -> &[Node] {
+        &tree.link(self).points_to
+    }
+    pub(crate) fn bind_source<'a>(self, tree: &ModuleTreeDescriptor, root: ast::Root<'a>) -> ast::Module<'a> {
+        modules(root)
+            .filter(|(name, _)| name == &tree.link(self).name)
+            .next()
+            .unwrap()
+            .1
+    }
+}
+
+
+fn resolve_submodule(
+    file_id: FileId,
+    name: &SmolStr,
+    file_resolver: &FileResolverImp
+) -> (Vec<FileId>, Option<Problem>) {
+    let mod_name = file_resolver.file_stem(file_id);
+    let is_dir_owner =
+        mod_name == "mod" || mod_name == "lib" || mod_name == "main";
+
+    let file_mod = RelativePathBuf::from(format!("../{}.rs", name));
+    let dir_mod = RelativePathBuf::from(format!("../{}/mod.rs", name));
+    let points_to: Vec<FileId>;
+    let problem: Option<Problem>;
+    if is_dir_owner {
+        points_to = [&file_mod, &dir_mod].iter()
+            .filter_map(|path| file_resolver.resolve(file_id, path))
+            .collect();
+        problem = if points_to.is_empty() {
+            Some(Problem::UnresolvedModule {
+                candidate: file_mod,
+            })
+        } else {
+            None
+        }
+    } else {
+        points_to = Vec::new();
+        problem = Some(Problem::NotDirOwner {
+            move_to: RelativePathBuf::from(format!("../{}/mod.rs", mod_name)),
+            candidate: file_mod,
+        });
+    }
+    (points_to, problem)
+}
diff --git a/crates/libanalysis/src/imp.rs b/crates/libanalysis/src/imp.rs
index 3e65ee14a..6f3191fe7 100644
--- a/crates/libanalysis/src/imp.rs
+++ b/crates/libanalysis/src/imp.rs
@@ -5,6 +5,7 @@ use std::{
     },
     fmt,
     collections::{HashSet, VecDeque},
+    iter,
 };
 
 use relative_path::RelativePath;
@@ -18,8 +19,8 @@ use libsyntax2::{
 use {
     FileId, FileResolver, Query, Diagnostic, SourceChange, SourceFileEdit, Position, FileSystemEdit,
     JobToken, CrateGraph, CrateId,
-    module_map::{ModuleMap, Problem},
     roots::{SourceRoot, ReadonlySourceRoot, WritableSourceRoot},
+    descriptors::{ModuleTreeDescriptor, Problem},
 };
 
 
@@ -75,14 +76,12 @@ impl AnalysisHostImpl {
     }
     pub fn change_files(&mut self, changes: &mut dyn Iterator<Item=(FileId, Option<String>)>) {
         let data = self.data_mut();
-        for (file_id, text) in changes {
-            data.root.update(file_id, text);
-        }
+        data.root = Arc::new(data.root.apply_changes(changes, None));
     }
     pub fn set_file_resolver(&mut self, resolver: FileResolverImp) {
         let data = self.data_mut();
         data.file_resolver = resolver.clone();
-        data.root.set_file_resolver(resolver);
+        data.root = Arc::new(data.root.apply_changes(&mut iter::empty(), Some(resolver)));
     }
     pub fn set_crate_graph(&mut self, graph: CrateGraph) {
         let mut visited = HashSet::new();
@@ -124,18 +123,17 @@ impl Clone for AnalysisImpl {
 impl AnalysisImpl {
     fn root(&self, file_id: FileId) -> &SourceRoot {
         if self.data.root.contains(file_id) {
-            return &self.data.root;
+            return &*self.data.root;
         }
         &**self.data.libs.iter().find(|it| it.contains(file_id)).unwrap()
     }
-    pub fn file_syntax(&self, file_id: FileId) -> &File {
+    pub fn file_syntax(&self, file_id: FileId) -> File {
         self.root(file_id).syntax(file_id)
     }
-    pub fn file_line_index(&self, file_id: FileId) -> &LineIndex {
+    pub fn file_line_index(&self, file_id: FileId) -> Arc<LineIndex> {
         self.root(file_id).lines(file_id)
     }
     pub fn world_symbols(&self, query: Query, token: &JobToken) -> Vec<(FileId, FileSymbol)> {
-        self.reindex();
         let mut buf = Vec::new();
         if query.libs {
             self.data.libs.iter()
@@ -148,25 +146,24 @@ impl AnalysisImpl {
     }
     pub fn parent_module(&self, file_id: FileId) -> Vec<(FileId, FileSymbol)> {
         let root = self.root(file_id);
-        let module_map = root.module_map();
-        let id = module_map.file2module(file_id);
-        module_map
-            .parent_modules(id, &|file_id| root.syntax(file_id))
-            .into_iter()
-            .map(|(id, name, node)| {
-                let id = module_map.module2file(id);
+        let module_tree = root.module_tree();
+        module_tree.parent_modules(file_id)
+            .iter()
+            .map(|link| {
+                let file_id = link.owner(&module_tree);
+                let syntax = root.syntax(file_id);
+                let decl = link.bind_source(&module_tree, syntax.ast());
                 let sym = FileSymbol {
-                    name,
-                    node_range: node.range(),
+                    name: link.name(&module_tree),
+                    node_range: decl.syntax().range(),
                     kind: MODULE,
                 };
-                (id, sym)
+                (file_id, sym)
             })
             .collect()
     }
-
     pub fn crate_for(&self, file_id: FileId) -> Vec<CrateId> {
-        let module_map = self.root(file_id).module_map();
+        let module_tree = self.root(file_id).module_tree();
         let crate_graph = &self.data.crate_graph;
         let mut res = Vec::new();
         let mut work = VecDeque::new();
@@ -177,11 +174,10 @@ impl AnalysisImpl {
                 res.push(crate_id);
                 continue;
             }
-            let mid = module_map.file2module(id);
-            let parents = module_map
-                .parent_module_ids(mid, &|file_id| self.file_syntax(file_id))
+            let parents = module_tree
+                .parent_modules(id)
                 .into_iter()
-                .map(|id| module_map.module2file(id))
+                .map(|link| link.owner(&module_tree))
                 .filter(|&id| visited.insert(id));
             work.extend(parents);
         }
@@ -197,7 +193,7 @@ impl AnalysisImpl {
         token: &JobToken,
     ) -> Vec<(FileId, FileSymbol)> {
         let root = self.root(file_id);
-        let module_map = root.module_map();
+        let module_tree = root.module_tree();
         let file = root.syntax(file_id);
         let syntax = file.syntax();
         if let Some(name_ref) = find_node_at_offset::<ast::NameRef>(syntax, offset) {
@@ -206,7 +202,7 @@ impl AnalysisImpl {
         if let Some(name) = find_node_at_offset::<ast::Name>(syntax, offset) {
             if let Some(module) = name.syntax().parent().and_then(ast::Module::cast) {
                 if module.has_semi() {
-                    let file_ids = self.resolve_module(module_map, file_id, module);
+                    let file_ids = self.resolve_module(&*module_tree, file_id, module);
 
                     let res = file_ids.into_iter().map(|id| {
                         let name = module.name()
@@ -229,7 +225,7 @@ impl AnalysisImpl {
 
     pub fn diagnostics(&self, file_id: FileId) -> Vec<Diagnostic> {
         let root = self.root(file_id);
-        let module_map = root.module_map();
+        let module_tree  = root.module_tree();
         let syntax = root.syntax(file_id);
 
         let mut res = libeditor::diagnostics(&syntax)
@@ -237,47 +233,43 @@ impl AnalysisImpl {
             .map(|d| Diagnostic { range: d.range, message: d.msg, fix: None })
             .collect::<Vec<_>>();
 
-        module_map.problems(
-            file_id,
-            &|file_id| self.file_syntax(file_id),
-            |name_node, problem| {
-                let diag = match problem {
-                    Problem::UnresolvedModule { candidate } => {
-                        let create_file = FileSystemEdit::CreateFile {
-                            anchor: file_id,
-                            path: candidate.clone(),
-                        };
-                        let fix = SourceChange {
-                            label: "create module".to_string(),
-                            source_file_edits: Vec::new(),
-                            file_system_edits: vec![create_file],
-                            cursor_position: None,
-                        };
-                        Diagnostic {
-                            range: name_node.syntax().range(),
-                            message: "unresolved module".to_string(),
-                            fix: Some(fix),
-                        }
+        for (name_node, problem) in module_tree.problems(file_id, syntax.ast()) {
+            let diag = match problem {
+                Problem::UnresolvedModule { candidate } => {
+                    let create_file = FileSystemEdit::CreateFile {
+                        anchor: file_id,
+                        path: candidate.clone(),
+                    };
+                    let fix = SourceChange {
+                        label: "create module".to_string(),
+                        source_file_edits: Vec::new(),
+                        file_system_edits: vec![create_file],
+                        cursor_position: None,
+                    };
+                    Diagnostic {
+                        range: name_node.syntax().range(),
+                        message: "unresolved module".to_string(),
+                        fix: Some(fix),
                     }
-                    Problem::NotDirOwner { move_to, candidate } => {
-                        let move_file = FileSystemEdit::MoveFile { file: file_id, path: move_to.clone() };
-                        let create_file = FileSystemEdit::CreateFile { anchor: file_id, path: move_to.join(candidate) };
-                        let fix = SourceChange {
-                            label: "move file and create module".to_string(),
-                            source_file_edits: Vec::new(),
-                            file_system_edits: vec![move_file, create_file],
-                            cursor_position: None,
-                        };
-                        Diagnostic {
-                            range: name_node.syntax().range(),
-                            message: "can't declare module at this location".to_string(),
-                            fix: Some(fix),
-                        }
+                }
+                Problem::NotDirOwner { move_to, candidate } => {
+                    let move_file = FileSystemEdit::MoveFile { file: file_id, path: move_to.clone() };
+                    let create_file = FileSystemEdit::CreateFile { anchor: file_id, path: move_to.join(candidate) };
+                    let fix = SourceChange {
+                        label: "move file and create module".to_string(),
+                        source_file_edits: Vec::new(),
+                        file_system_edits: vec![move_file, create_file],
+                        cursor_position: None,
+                    };
+                    Diagnostic {
+                        range: name_node.syntax().range(),
+                        message: "can't declare module at this location".to_string(),
+                        fix: Some(fix),
                     }
-                };
-                res.push(diag)
-            }
-        );
+                }
+            };
+            res.push(diag)
+        }
         res
     }
 
@@ -307,26 +299,12 @@ impl AnalysisImpl {
         self.world_symbols(query, token)
     }
 
-    fn resolve_module(&self, module_map: &ModuleMap, file_id: FileId, module: ast::Module) -> Vec<FileId> {
+    fn resolve_module(&self, module_tree: &ModuleTreeDescriptor, file_id: FileId, module: ast::Module) -> Vec<FileId> {
         let name = match module.name() {
             Some(name) => name.text(),
             None => return Vec::new(),
         };
-        let id = module_map.file2module(file_id);
-        module_map
-            .child_module_by_name(
-                id, name.as_str(),
-                &|file_id| self.file_syntax(file_id),
-            )
-            .into_iter()
-            .map(|id| module_map.module2file(id))
-            .collect()
-    }
-
-    fn reindex(&self) {
-        if self.needs_reindex.compare_and_swap(true, false, SeqCst) {
-            self.data.root.reindex();
-        }
+        module_tree.child_module_by_name(file_id, name.as_str())
     }
 }
 
@@ -334,7 +312,7 @@ impl AnalysisImpl {
 struct WorldData {
     file_resolver: FileResolverImp,
     crate_graph: CrateGraph,
-    root: WritableSourceRoot,
+    root: Arc<WritableSourceRoot>,
     libs: Vec<Arc<ReadonlySourceRoot>>,
 }
 
diff --git a/crates/libanalysis/src/lib.rs b/crates/libanalysis/src/lib.rs
index 80cde079f..b4b7a6a30 100644
--- a/crates/libanalysis/src/lib.rs
+++ b/crates/libanalysis/src/lib.rs
@@ -9,12 +9,17 @@ extern crate rayon;
 extern crate relative_path;
 #[macro_use]
 extern crate crossbeam_channel;
+extern crate im;
+extern crate salsa;
 
 mod symbol_index;
 mod module_map;
 mod imp;
 mod job;
 mod roots;
+mod db;
+mod queries;
+mod descriptors;
 
 use std::{
     sync::Arc,
@@ -161,8 +166,8 @@ impl Analysis {
     pub fn file_syntax(&self, file_id: FileId) -> File {
         self.imp.file_syntax(file_id).clone()
     }
-    pub fn file_line_index(&self, file_id: FileId) -> LineIndex {
-        self.imp.file_line_index(file_id).clone()
+    pub fn file_line_index(&self, file_id: FileId) -> Arc<LineIndex> {
+        self.imp.file_line_index(file_id)
     }
     pub fn extend_selection(&self, file: &File, range: TextRange) -> TextRange {
         libeditor::extend_selection(file, range).unwrap_or(range)
@@ -172,19 +177,19 @@ impl Analysis {
     }
     pub fn syntax_tree(&self, file_id: FileId) -> String {
         let file = self.imp.file_syntax(file_id);
-        libeditor::syntax_tree(file)
+        libeditor::syntax_tree(&file)
     }
     pub fn join_lines(&self, file_id: FileId, range: TextRange) -> SourceChange {
         let file = self.imp.file_syntax(file_id);
-        SourceChange::from_local_edit(file_id, "join lines", libeditor::join_lines(file, range))
+        SourceChange::from_local_edit(file_id, "join lines", libeditor::join_lines(&file, range))
     }
     pub fn on_eq_typed(&self, file_id: FileId, offset: TextUnit) -> Option<SourceChange> {
         let file = self.imp.file_syntax(file_id);
-        Some(SourceChange::from_local_edit(file_id, "add semicolon", libeditor::on_eq_typed(file, offset)?))
+        Some(SourceChange::from_local_edit(file_id, "add semicolon", libeditor::on_eq_typed(&file, offset)?))
     }
     pub fn file_structure(&self, file_id: FileId) -> Vec<StructureNode> {
         let file = self.imp.file_syntax(file_id);
-        libeditor::file_structure(file)
+        libeditor::file_structure(&file)
     }
     pub fn symbol_search(&self, query: Query, token: &JobToken) -> Vec<(FileId, FileSymbol)> {
         self.imp.world_symbols(query, token)
@@ -203,15 +208,15 @@ impl Analysis {
     }
     pub fn runnables(&self, file_id: FileId) -> Vec<Runnable> {
         let file = self.imp.file_syntax(file_id);
-        libeditor::runnables(file)
+        libeditor::runnables(&file)
     }
     pub fn highlight(&self, file_id: FileId) -> Vec<HighlightedRange> {
         let file = self.imp.file_syntax(file_id);
-        libeditor::highlight(file)
+        libeditor::highlight(&file)
     }
     pub fn completions(&self, file_id: FileId, offset: TextUnit) -> Option<Vec<CompletionItem>> {
         let file = self.imp.file_syntax(file_id);
-        libeditor::scope_completion(file, offset)
+        libeditor::scope_completion(&file, offset)
     }
     pub fn assists(&self, file_id: FileId, range: TextRange) -> Vec<SourceChange> {
         self.imp.assists(file_id, range)
diff --git a/crates/libanalysis/src/module_map.rs b/crates/libanalysis/src/module_map.rs
index 9acebd6e2..a21f55fff 100644
--- a/crates/libanalysis/src/module_map.rs
+++ b/crates/libanalysis/src/module_map.rs
@@ -1,274 +1,157 @@
-use relative_path::RelativePathBuf;
-use parking_lot::{RwLock, RwLockReadGuard, RwLockWriteGuard};
-use libsyntax2::{
-    File,
-    ast::{self, AstNode, NameOwner},
-    SyntaxNode, SmolStr,
+use std::sync::Arc;
+use {
+    FileId,
+    db::{
+        Query, QueryRegistry, QueryCtx,
+        file_set
+    },
+    queries::file_syntax,
+    descriptors::{ModuleDescriptor, ModuleTreeDescriptor},
 };
-use {FileId, imp::FileResolverImp};
-
-type SyntaxProvider<'a> = dyn Fn(FileId) -> &'a File + 'a;
-
-#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
-pub struct ModuleId(FileId);
 
-#[derive(Debug, Default)]
-pub struct ModuleMap {
-    state: RwLock<State>,
+pub(crate) fn register_queries(reg: &mut QueryRegistry) {
+    reg.add(MODULE_DESCR, "MODULE_DESCR");
+    reg.add(MODULE_TREE, "MODULE_TREE");
 }
 
-#[derive(Debug, Clone, Copy, PartialEq, Eq)]
-pub enum ChangeKind {
-    Delete, Insert, Update
-}
-
-impl Clone for ModuleMap {
-    fn clone(&self) -> ModuleMap {
-        let state = self.state.read().clone();
-        ModuleMap { state: RwLock::new(state) }
-    }
+pub(crate) fn module_tree(ctx: QueryCtx) -> Arc<ModuleTreeDescriptor> {
+    ctx.get(MODULE_TREE, ())
 }
 
-#[derive(Clone, Debug, Default)]
-struct State {
-    file_resolver: FileResolverImp,
-    changes: Vec<(FileId, ChangeKind)>,
-    links: Vec<Link>,
-}
-
-#[derive(Clone, Debug)]
-struct Link {
-    owner: ModuleId,
-    syntax: SyntaxNode,
-    points_to: Vec<ModuleId>,
-    problem: Option<Problem>,
-}
-
-#[derive(Clone, Debug)]
-pub enum Problem {
-    UnresolvedModule {
-        candidate: RelativePathBuf,
-    },
-    NotDirOwner {
-        move_to: RelativePathBuf,
-        candidate: RelativePathBuf,
-    }
-}
-
-impl ModuleMap {
-    pub fn new() -> ModuleMap {
-        Default::default()
-    }
-    pub fn update_file(&mut self, file_id: FileId, change_kind: ChangeKind) {
-        self.state.get_mut().changes.push((file_id, change_kind));
-    }
-    pub(crate) fn set_file_resolver(&mut self, file_resolver: FileResolverImp) {
-        self.state.get_mut().file_resolver = file_resolver;
-    }
-    pub fn module2file(&self, m: ModuleId) -> FileId {
-        m.0
-    }
-    pub fn file2module(&self, file_id: FileId) -> ModuleId {
-        ModuleId(file_id)
-    }
-    pub fn child_module_by_name<'a>(
-        &self,
-        parent_mod: ModuleId,
-        child_mod: &str,
-        syntax_provider: &SyntaxProvider,
-    ) -> Vec<ModuleId> {
-        self.links(syntax_provider)
-            .links
-            .iter()
-            .filter(|link| link.owner == parent_mod)
-            .filter(|link| link.name() == child_mod)
-            .filter_map(|it| it.points_to.first())
-            .map(|&it| it)
-            .collect()
-    }
-
-    pub fn parent_modules(
-        &self,
-        m: ModuleId,
-        syntax_provider: &SyntaxProvider,
-    ) -> Vec<(ModuleId, SmolStr, SyntaxNode)> {
-        let mut res = Vec::new();
-        self.for_each_parent_link(m, syntax_provider, |link| {
-            res.push(
-                (link.owner, link.name().clone(), link.syntax.clone())
-            )
-        });
-        res
-    }
-
-    pub fn parent_module_ids(
-        &self,
-        m: ModuleId,
-        syntax_provider: &SyntaxProvider,
-    ) -> Vec<ModuleId> {
-        let mut res = Vec::new();
-        self.for_each_parent_link(m, syntax_provider, |link| res.push(link.owner));
-        res
-    }
-
-    fn for_each_parent_link(
-        &self,
-        m: ModuleId,
-        syntax_provider: &SyntaxProvider,
-        f: impl FnMut(&Link)
-    ) {
-        self.links(syntax_provider)
-            .links
-            .iter()
-            .filter(move |link| link.points_to.iter().any(|&it| it == m))
-            .for_each(f)
+const MODULE_DESCR: Query<FileId, ModuleDescriptor> = Query(30, |ctx, &file_id| {
+    let file = file_syntax(ctx, file_id);
+    ModuleDescriptor::new(file.ast())
+});
+
+const MODULE_TREE: Query<(), ModuleTreeDescriptor> = Query(31, |ctx, _| {
+    let file_set = file_set(ctx);
+    let mut files = Vec::new();
+    for &file_id in file_set.0.iter() {
+        let module_descr = ctx.get(MODULE_DESCR, file_id);
+        files.push((file_id, module_descr));
+    }
+    ModuleTreeDescriptor::new(files.iter().map(|(file_id, descr)| (*file_id, &**descr)), &file_set.1)
+});
+
+#[cfg(test)]
+mod tests {
+    use std::collections::HashMap;
+    use im;
+    use relative_path::{RelativePath, RelativePathBuf};
+    use {
+        db::{Db},
+        imp::FileResolverImp,
+        FileId, FileResolver,
+    };
+    use super::*;
+
+    #[derive(Debug)]
+    struct FileMap(im::HashMap<FileId, RelativePathBuf>);
+
+    impl FileResolver for FileMap {
+        fn file_stem(&self, file_id: FileId) -> String {
+            self.0[&file_id].file_stem().unwrap().to_string()
+        }
+        fn resolve(&self, file_id: FileId, rel: &RelativePath) -> Option<FileId> {
+            let path = self.0[&file_id].join(rel).normalize();
+            self.0.iter()
+                .filter_map(|&(id, ref p)| Some(id).filter(|_| p == &path))
+                .next()
+        }
     }
 
-    pub fn problems(
-        &self,
-        file: FileId,
-        syntax_provider: &SyntaxProvider,
-        mut cb: impl FnMut(ast::Name, &Problem),
-    ) {
-        let module = self.file2module(file);
-        let links = self.links(syntax_provider);
-        links
-            .links
-            .iter()
-            .filter(|link| link.owner == module)
-            .filter_map(|link| {
-                let problem = link.problem.as_ref()?;
-                Some((link, problem))
-            })
-            .for_each(|(link, problem)| cb(link.name_node(), problem))
+    struct Fixture {
+        next_file_id: u32,
+        fm: im::HashMap<FileId, RelativePathBuf>,
+        db: Db,
     }
 
-    fn links(
-        &self,
-        syntax_provider: &SyntaxProvider,
-    ) -> RwLockReadGuard<State> {
-        {
-            let guard = self.state.read();
-            if guard.changes.is_empty() {
-                return guard;
+    impl Fixture {
+        fn new() -> Fixture {
+            Fixture {
+                next_file_id: 1,
+                fm: im::HashMap::new(),
+                db: Db::new(),
             }
         }
-        let mut guard = self.state.write();
-        if !guard.changes.is_empty() {
-            guard.apply_changes(syntax_provider);
+        fn add_file(&mut self, path: &str, text: &str) -> FileId {
+            assert!(path.starts_with("/"));
+            let file_id = FileId(self.next_file_id);
+            self.next_file_id += 1;
+            self.fm.insert(file_id, RelativePathBuf::from(&path[1..]));
+            let mut new_state = self.db.state().clone();
+            new_state.file_map.insert(file_id, Arc::new(text.to_string()));
+            new_state.file_resolver = FileResolverImp::new(
+                Arc::new(FileMap(self.fm.clone()))
+            );
+            self.db = self.db.with_changes(new_state, &[file_id], true);
+            file_id
         }
-        assert!(guard.changes.is_empty());
-        RwLockWriteGuard::downgrade(guard)
-    }
-}
-
-impl State {
-    pub fn apply_changes(
-        &mut self,
-        syntax_provider: &SyntaxProvider,
-    ) {
-        let mut reresolve = false;
-        for (file_id, kind) in self.changes.drain(..) {
-            let mod_id = ModuleId(file_id);
-            self.links.retain(|link| link.owner != mod_id);
-            match kind {
-                ChangeKind::Delete => {
-                    for link in self.links.iter_mut() {
-                        link.points_to.retain(|&x| x != mod_id);
-                    }
-                }
-                ChangeKind::Insert => {
-                    let file = syntax_provider(file_id);
-                    self.links.extend(
-                        file
-                            .ast()
-                            .modules()
-                            .filter_map(|it| Link::new(mod_id, it))
-                    );
-                    reresolve = true;
-                }
-                ChangeKind::Update => {
-                    let file = syntax_provider(file_id);
-                    let resolver = &self.file_resolver;
-                    self.links.extend(
-                        file
-                            .ast()
-                            .modules()
-                            .filter_map(|it| Link::new(mod_id, it))
-                            .map(|mut link| {
-                                link.resolve(resolver);
-                                link
-                            })
-                    );
-                }
-            }
+        fn remove_file(&mut self, file_id: FileId) {
+            self.fm.remove(&file_id);
+            let mut new_state = self.db.state().clone();
+            new_state.file_map.remove(&file_id);
+            new_state.file_resolver = FileResolverImp::new(
+                Arc::new(FileMap(self.fm.clone()))
+            );
+            self.db = self.db.with_changes(new_state, &[file_id], true);
         }
-        if reresolve {
-            for link in self.links.iter_mut() {
-                link.resolve(&self.file_resolver)
-            }
+        fn change_file(&mut self, file_id: FileId, new_text: &str) {
+            let mut new_state = self.db.state().clone();
+            new_state.file_map.insert(file_id, Arc::new(new_text.to_string()));
+            self.db = self.db.with_changes(new_state, &[file_id], false);
         }
-    }
-}
+        fn check_parent_modules(
+            &self,
+            file_id: FileId,
+            expected: &[FileId],
+            queries: &[(&'static str, u64)]
+        ) {
+            let (tree, events) = self.db.trace_query(|ctx| module_tree(ctx));
+            let actual = tree.parent_modules(file_id)
+                .into_iter()
+                .map(|link| link.owner(&tree))
+                .collect::<Vec<_>>();
+            assert_eq!(actual.as_slice(), expected);
+            let mut counts = HashMap::new();
+            events.into_iter()
+               .for_each(|event| *counts.entry(event).or_insert(0) += 1);
+            for &(query_id, expected_count) in queries.iter() {
+                let actual_count = *counts.get(&query_id).unwrap_or(&0);
+                assert_eq!(
+                    actual_count,
+                    expected_count,
+                    "counts for {} differ",
+                    query_id,
+                )
+            }
 
-impl Link {
-    fn new(owner: ModuleId, module: ast::Module) -> Option<Link> {
-        if module.name().is_none() {
-            return None;
         }
-        let link = Link {
-            owner,
-            syntax: module.syntax().owned(),
-            points_to: Vec::new(),
-            problem: None,
-        };
-        Some(link)
     }
 
-    fn name(&self) -> SmolStr {
-        self.name_node().text()
-    }
+    #[test]
+    fn test_parent_module() {
+        let mut f = Fixture::new();
+        let foo = f.add_file("/foo.rs", "");
+        f.check_parent_modules(foo, &[], &[("MODULE_DESCR", 1)]);
 
-    fn name_node(&self) -> ast::Name {
-        self.ast().name().unwrap()
-    }
+        let lib = f.add_file("/lib.rs", "mod foo;");
+        f.check_parent_modules(foo, &[lib], &[("MODULE_DESCR", 1)]);
+        f.check_parent_modules(foo, &[lib], &[("MODULE_DESCR", 0)]);
 
-    fn ast(&self) -> ast::Module {
-        ast::Module::cast(self.syntax.borrowed())
-            .unwrap()
-    }
+        f.change_file(lib, "");
+        f.check_parent_modules(foo, &[], &[("MODULE_DESCR", 1)]);
 
-    fn resolve(&mut self, file_resolver: &FileResolverImp) {
-        if !self.ast().has_semi() {
-            self.problem = None;
-            self.points_to = Vec::new();
-            return;
-        }
+        f.change_file(lib, "mod foo;");
+        f.check_parent_modules(foo, &[lib], &[("MODULE_DESCR", 1)]);
 
-        let mod_name = file_resolver.file_stem(self.owner.0);
-        let is_dir_owner =
-            mod_name == "mod" || mod_name == "lib" || mod_name == "main";
+        f.change_file(lib, "mod bar;");
+        f.check_parent_modules(foo, &[], &[("MODULE_DESCR", 1)]);
 
-        let file_mod = RelativePathBuf::from(format!("../{}.rs", self.name()));
-        let dir_mod = RelativePathBuf::from(format!("../{}/mod.rs", self.name()));
-        if is_dir_owner {
-            self.points_to = [&file_mod, &dir_mod].iter()
-                .filter_map(|path| file_resolver.resolve(self.owner.0, path))
-                .map(ModuleId)
-                .collect();
-            self.problem = if self.points_to.is_empty() {
-                Some(Problem::UnresolvedModule {
-                    candidate: file_mod,
-                })
-            } else {
-                None
-            }
-        } else {
-            self.points_to = Vec::new();
-            self.problem = Some(Problem::NotDirOwner {
-                move_to: RelativePathBuf::from(format!("../{}/mod.rs", mod_name)),
-                candidate: file_mod,
-            });
-        }
+        f.change_file(lib, "mod foo;");
+        f.check_parent_modules(foo, &[lib], &[("MODULE_DESCR", 1)]);
+
+        f.remove_file(lib);
+        f.check_parent_modules(foo, &[], &[("MODULE_DESCR", 0)]);
     }
 }
diff --git a/crates/libanalysis/src/queries.rs b/crates/libanalysis/src/queries.rs
new file mode 100644
index 000000000..0b60316e6
--- /dev/null
+++ b/crates/libanalysis/src/queries.rs
@@ -0,0 +1,39 @@
+use std::sync::Arc;
+use libsyntax2::File;
+use libeditor::LineIndex;
+use {
+    FileId,
+    db::{Query, QueryCtx, QueryRegistry},
+    symbol_index::SymbolIndex,
+};
+
+pub(crate) use db::{file_text, file_set};
+
+pub(crate) fn file_syntax(ctx: QueryCtx, file_id: FileId) -> File {
+    (&*ctx.get(FILE_SYNTAX, file_id)).clone()
+}
+pub(crate) fn file_lines(ctx: QueryCtx, file_id: FileId) -> Arc<LineIndex> {
+    ctx.get(FILE_LINES, file_id)
+}
+pub(crate) fn file_symbols(ctx: QueryCtx, file_id: FileId) -> Arc<SymbolIndex> {
+    ctx.get(FILE_SYMBOLS, file_id)
+}
+
+const FILE_SYNTAX: Query<FileId, File> = Query(16, |ctx, file_id: &FileId| {
+    let text = file_text(ctx, *file_id);
+    File::parse(&*text)
+});
+const FILE_LINES: Query<FileId, LineIndex> = Query(17, |ctx, file_id: &FileId| {
+    let text = file_text(ctx, *file_id);
+    LineIndex::new(&*text)
+});
+const FILE_SYMBOLS: Query<FileId, SymbolIndex> = Query(18, |ctx, file_id: &FileId| {
+    let syntax = file_syntax(ctx, *file_id);
+    SymbolIndex::for_file(*file_id, syntax)
+});
+
+pub(crate) fn register_queries(reg: &mut QueryRegistry) {
+    reg.add(FILE_SYNTAX, "FILE_SYNTAX");
+    reg.add(FILE_LINES, "FILE_LINES");
+    reg.add(FILE_SYMBOLS, "FILE_SYMBOLS");
+}
diff --git a/crates/libanalysis/src/roots.rs b/crates/libanalysis/src/roots.rs
index 629a697c5..191d0d821 100644
--- a/crates/libanalysis/src/roots.rs
+++ b/crates/libanalysis/src/roots.rs
@@ -1,6 +1,5 @@
 use std::{
     collections::HashMap,
-    time::Instant,
     sync::Arc,
     panic,
 };
@@ -13,94 +12,82 @@ use libsyntax2::File;
 use {
     FileId,
     imp::FileResolverImp,
-    module_map::{ModuleMap, ChangeKind},
     symbol_index::SymbolIndex,
+    descriptors::{ModuleDescriptor, ModuleTreeDescriptor},
+    db::Db,
 };
 
 pub(crate) trait SourceRoot {
     fn contains(&self, file_id: FileId) -> bool;
-    fn module_map(&self) -> &ModuleMap;
-    fn lines(&self, file_id: FileId) -> &LineIndex;
-    fn syntax(&self, file_id: FileId) -> &File;
-    fn symbols<'a>(&'a self, acc: &mut Vec<&'a SymbolIndex>);
+    fn module_tree(&self) -> Arc<ModuleTreeDescriptor>;
+    fn lines(&self, file_id: FileId) -> Arc<LineIndex>;
+    fn syntax(&self, file_id: FileId) -> File;
+    fn symbols(&self, acc: &mut Vec<Arc<SymbolIndex>>);
 }
 
-#[derive(Clone, Default, Debug)]
+#[derive(Default, Debug)]
 pub(crate) struct WritableSourceRoot {
-    file_map: HashMap<FileId, Arc<(FileData, OnceCell<SymbolIndex>)>>,
-    module_map: ModuleMap,
+    db: Db,
 }
 
 impl WritableSourceRoot {
-    pub fn update(&mut self, file_id: FileId, text: Option<String>) {
-        let change_kind = if self.file_map.remove(&file_id).is_some() {
-            if text.is_some() {
-                ChangeKind::Update
-            } else {
-                ChangeKind::Delete
+    pub fn apply_changes(
+        &self,
+        changes: &mut dyn Iterator<Item=(FileId, Option<String>)>,
+        file_resolver: Option<FileResolverImp>,
+    ) -> WritableSourceRoot {
+        let resolver_changed = file_resolver.is_some();
+        let mut changed_files = Vec::new();
+        let mut new_state = self.db.state().clone();
+
+        for (file_id, text) in changes {
+            changed_files.push(file_id);
+            match text {
+                Some(text) => {
+                    new_state.file_map.insert(file_id, Arc::new(text));
+                },
+                None => {
+                    new_state.file_map.remove(&file_id);
+                }
             }
-        } else {
-            ChangeKind::Insert
-        };
-        self.module_map.update_file(file_id, change_kind);
-        self.file_map.remove(&file_id);
-        if let Some(text) = text {
-            let file_data = FileData::new(text);
-            self.file_map.insert(file_id, Arc::new((file_data, Default::default())));
         }
-    }
-    pub fn set_file_resolver(&mut self, file_resolver: FileResolverImp) {
-        self.module_map.set_file_resolver(file_resolver)
-    }
-    pub fn reindex(&self) {
-        let now = Instant::now();
-        self.file_map
-            .par_iter()
-            .for_each(|(&file_id, data)| {
-                symbols(file_id, data);
-            });
-        info!("parallel indexing took {:?}", now.elapsed());
-
-    }
-    fn data(&self, file_id: FileId) -> &FileData {
-        match self.file_map.get(&file_id) {
-            Some(data) => &data.0,
-            None => panic!("unknown file: {:?}", file_id),
+        if let Some(file_resolver) = file_resolver {
+            new_state.file_resolver = file_resolver
+        }
+        WritableSourceRoot {
+            db: self.db.with_changes(new_state, &changed_files, resolver_changed)
         }
     }
 }
 
 impl SourceRoot for WritableSourceRoot {
-    fn contains(&self, file_id: FileId) -> bool {
-        self.file_map.contains_key(&file_id)
+    fn module_tree(&self) -> Arc<ModuleTreeDescriptor> {
+        self.db.make_query(::module_map::module_tree)
     }
-    fn module_map(&self) -> &ModuleMap {
-        &self.module_map
+
+    fn contains(&self, file_id: FileId) -> bool {
+        self.db.state().file_map.contains_key(&file_id)
     }
-    fn lines(&self, file_id: FileId) -> &LineIndex {
-        self.data(file_id).lines()
+    fn lines(&self, file_id: FileId) -> Arc<LineIndex> {
+        self.db.make_query(|ctx| ::queries::file_lines(ctx, file_id))
     }
-    fn syntax(&self, file_id: FileId) -> &File {
-        self.data(file_id).syntax()
+    fn syntax(&self, file_id: FileId) -> File {
+        self.db.make_query(|ctx| ::queries::file_syntax(ctx, file_id))
     }
-    fn symbols<'a>(&'a self, acc: &mut Vec<&'a SymbolIndex>) {
-        acc.extend(
-            self.file_map
-                .iter()
-                .map(|(&file_id, data)| symbols(file_id, data))
-        )
+    fn symbols<'a>(&'a self, acc: &mut Vec<Arc<SymbolIndex>>) {
+        self.db.make_query(|ctx| {
+            let file_set = ::queries::file_set(ctx);
+            let syms = file_set.0.iter()
+                .map(|file_id| ::queries::file_symbols(ctx, *file_id));
+            acc.extend(syms);
+        });
     }
 }
 
-fn symbols(file_id: FileId, (data, symbols): &(FileData, OnceCell<SymbolIndex>)) -> &SymbolIndex {
-    let syntax = data.syntax_transient();
-    symbols.get_or_init(|| SymbolIndex::for_file(file_id, syntax))
-}
-
 #[derive(Debug)]
 struct FileData {
     text: String,
-    lines: OnceCell<LineIndex>,
+    lines: OnceCell<Arc<LineIndex>>,
     syntax: OnceCell<File>,
 }
 
@@ -112,8 +99,8 @@ impl FileData {
             lines: OnceCell::new(),
         }
     }
-    fn lines(&self) -> &LineIndex {
-        self.lines.get_or_init(|| LineIndex::new(&self.text))
+    fn lines(&self) -> &Arc<LineIndex> {
+        self.lines.get_or_init(|| Arc::new(LineIndex::new(&self.text)))
     }
     fn syntax(&self) -> &File {
         let text = &self.text;
@@ -126,40 +113,41 @@ impl FileData {
             }
         }
     }
-    fn syntax_transient(&self) -> File {
-        self.syntax.get().map(|s| s.clone())
-            .unwrap_or_else(|| File::parse(&self.text))
-    }
 }
 
 #[derive(Debug)]
 pub(crate) struct ReadonlySourceRoot {
-    symbol_index: SymbolIndex,
+    symbol_index: Arc<SymbolIndex>,
     file_map: HashMap<FileId, FileData>,
-    module_map: ModuleMap,
+    module_tree: Arc<ModuleTreeDescriptor>,
 }
 
 impl ReadonlySourceRoot {
     pub(crate) fn new(files: Vec<(FileId, String)>, file_resolver: FileResolverImp) -> ReadonlySourceRoot {
-        let mut module_map = ModuleMap::new();
-        module_map.set_file_resolver(file_resolver);
-        let symbol_index = SymbolIndex::for_files(
-            files.par_iter().map(|(file_id, text)| {
-                (*file_id, File::parse(text))
+        let modules = files.par_iter()
+            .map(|(file_id, text)| {
+                let syntax = File::parse(text);
+                let mod_descr = ModuleDescriptor::new(syntax.ast());
+                (*file_id, syntax, mod_descr)
             })
+            .collect::<Vec<_>>();
+        let module_tree = ModuleTreeDescriptor::new(
+            modules.iter().map(|it| (it.0, &it.2)),
+            &file_resolver,
+        );
+
+        let symbol_index = SymbolIndex::for_files(
+            modules.par_iter().map(|it| (it.0, it.1.clone()))
         );
         let file_map: HashMap<FileId, FileData> = files
             .into_iter()
-            .map(|(id, text)| {
-                module_map.update_file(id, ChangeKind::Insert);
-                (id, FileData::new(text))
-            })
+            .map(|(id, text)| (id, FileData::new(text)))
             .collect();
 
         ReadonlySourceRoot {
-            symbol_index,
+            symbol_index: Arc::new(symbol_index),
             file_map,
-            module_map,
+            module_tree: Arc::new(module_tree),
         }
     }
 
@@ -172,19 +160,19 @@ impl ReadonlySourceRoot {
 }
 
 impl SourceRoot for ReadonlySourceRoot {
+    fn module_tree(&self) -> Arc<ModuleTreeDescriptor> {
+        Arc::clone(&self.module_tree)
+    }
     fn contains(&self, file_id: FileId) -> bool {
         self.file_map.contains_key(&file_id)
     }
-    fn module_map(&self) -> &ModuleMap {
-        &self.module_map
-    }
-    fn lines(&self, file_id: FileId) -> &LineIndex {
-        self.data(file_id).lines()
+    fn lines(&self, file_id: FileId) -> Arc<LineIndex> {
+        Arc::clone(self.data(file_id).lines())
     }
-    fn syntax(&self, file_id: FileId) -> &File {
-        self.data(file_id).syntax()
+    fn syntax(&self, file_id: FileId) -> File {
+        self.data(file_id).syntax().clone()
     }
-    fn symbols<'a>(&'a self, acc: &mut Vec<&'a SymbolIndex>) {
-        acc.push(&self.symbol_index)
+    fn symbols(&self, acc: &mut Vec<Arc<SymbolIndex>>) {
+        acc.push(Arc::clone(&self.symbol_index))
     }
 }
diff --git a/crates/libanalysis/src/symbol_index.rs b/crates/libanalysis/src/symbol_index.rs
index 4c93761aa..d22187ac0 100644
--- a/crates/libanalysis/src/symbol_index.rs
+++ b/crates/libanalysis/src/symbol_index.rs
@@ -1,3 +1,7 @@
+use std::{
+    sync::Arc,
+    hash::{Hash, Hasher},
+};
 use libeditor::{FileSymbol, file_symbols};
 use libsyntax2::{
     File,
@@ -13,6 +17,12 @@ pub(crate) struct SymbolIndex {
     map: fst::Map,
 }
 
+impl Hash for SymbolIndex {
+    fn hash<H: Hasher>(&self, hasher: &mut H) {
+        self.symbols.hash(hasher)
+    }
+}
+
 impl SymbolIndex {
     pub(crate) fn for_files(files: impl ParallelIterator<Item=(FileId, File)>) -> SymbolIndex {
         let mut symbols = files
@@ -43,7 +53,7 @@ impl SymbolIndex {
 impl Query {
     pub(crate) fn search(
         self,
-        indices: &[&SymbolIndex],
+        indices: &[Arc<SymbolIndex>],
         token: &JobToken,
     ) -> Vec<(FileId, FileSymbol)> {
 
diff --git a/crates/libanalysis/tests/tests.rs b/crates/libanalysis/tests/tests.rs
index 00efe059c..547f85958 100644
--- a/crates/libanalysis/tests/tests.rs
+++ b/crates/libanalysis/tests/tests.rs
@@ -14,24 +14,6 @@ use test_utils::assert_eq_dbg;
 #[derive(Debug)]
 struct FileMap(Vec<(FileId, RelativePathBuf)>);
 
-fn analysis_host(files: &'static [(&'static str, &'static str)]) -> AnalysisHost {
-    let mut host = AnalysisHost::new();
-    let mut file_map = Vec::new();
-    for (id, &(path, contents)) in files.iter().enumerate() {
-        let file_id = FileId((id + 1) as u32);
-        assert!(path.starts_with('/'));
-        let path = RelativePathBuf::from_path(&path[1..]).unwrap();
-        host.change_file(file_id, Some(contents.to_string()));
-        file_map.push((file_id, path));
-    }
-    host.set_file_resolver(Arc::new(FileMap(file_map)));
-    host
-}
-
-fn analysis(files: &'static [(&'static str, &'static str)]) -> Analysis {
-    analysis_host(files).analysis()
-}
-
 impl FileMap {
     fn iter<'a>(&'a self) -> impl Iterator<Item=(FileId, &'a RelativePath)> + 'a {
         self.0.iter().map(|(id, path)| (*id, path.as_relative_path()))
@@ -56,6 +38,23 @@ impl FileResolver for FileMap {
     }
 }
 
+fn analysis_host(files: &'static [(&'static str, &'static str)]) -> AnalysisHost {
+    let mut host = AnalysisHost::new();
+    let mut file_map = Vec::new();
+    for (id, &(path, contents)) in files.iter().enumerate() {
+        let file_id = FileId((id + 1) as u32);
+        assert!(path.starts_with('/'));
+        let path = RelativePathBuf::from_path(&path[1..]).unwrap();
+        host.change_file(file_id, Some(contents.to_string()));
+        file_map.push((file_id, path));
+    }
+    host.set_file_resolver(Arc::new(FileMap(file_map)));
+    host
+}
+
+fn analysis(files: &'static [(&'static str, &'static str)]) -> Analysis {
+    analysis_host(files).analysis()
+}
 
 #[test]
 fn test_resolve_module() {