2 files changed, 640 insertions, 0 deletions

diff --git a/crates/ra_hir/src/function/mod.rs b/crates/ra_hir/src/function/mod.rs
new file mode 100644
index 000000000..a3ed00f02
--- /dev/null
+++ b/crates/ra_hir/src/function/mod.rs
@@ -0,0 +1,190 @@
+mod scope;
+
+use std::{
+    cmp::{max, min},
+    sync::Arc,
+};
+
+use ra_syntax::{
+    TextRange, TextUnit, SyntaxNodeRef,
+    ast::{self, AstNode, DocCommentsOwner, NameOwner},
+};
+use ra_db::FileId;
+
+use crate::{
+    FnId, HirDatabase, SourceItemId,
+};
+
+pub(crate) use self::scope::FnScopes;
+
+impl FnId {
+    pub(crate) fn get(db: &impl HirDatabase, file_id: FileId, fn_def: ast::FnDef) -> FnId {
+        let file_items = db.file_items(file_id);
+        let item_id = file_items.id_of(fn_def.syntax());
+        let item_id = SourceItemId { file_id, item_id };
+        FnId::from_loc(db, &item_id)
+    }
+}
+
+pub(crate) struct Function {
+    fn_id: FnId,
+}
+
+impl Function {
+    pub(crate) fn guess_from_source(
+        db: &impl HirDatabase,
+        file_id: FileId,
+        fn_def: ast::FnDef,
+    ) -> Function {
+        let fn_id = FnId::get(db, file_id, fn_def);
+        Function { fn_id }
+    }
+
+    pub(crate) fn guess_for_name_ref(
+        db: &impl HirDatabase,
+        file_id: FileId,
+        name_ref: ast::NameRef,
+    ) -> Option<Function> {
+        Function::guess_for_node(db, file_id, name_ref.syntax())
+    }
+
+    pub(crate) fn guess_for_bind_pat(
+        db: &impl HirDatabase,
+        file_id: FileId,
+        bind_pat: ast::BindPat,
+    ) -> Option<Function> {
+        Function::guess_for_node(db, file_id, bind_pat.syntax())
+    }
+
+    fn guess_for_node(
+        db: &impl HirDatabase,
+        file_id: FileId,
+        node: SyntaxNodeRef,
+    ) -> Option<Function> {
+        let fn_def = node.ancestors().find_map(ast::FnDef::cast)?;
+        let res = Function::guess_from_source(db, file_id, fn_def);
+        Some(res)
+    }
+
+    pub(crate) fn scope(&self, db: &impl HirDatabase) -> Arc<FnScopes> {
+        db.fn_scopes(self.fn_id)
+    }
+
+    pub(crate) fn signature_info(&self, db: &impl HirDatabase) -> Option<FnSignatureInfo> {
+        let syntax = db.fn_syntax(self.fn_id);
+        FnSignatureInfo::new(syntax.borrowed())
+    }
+}
+
+#[derive(Debug, Clone)]
+pub struct FnSignatureInfo {
+    pub name: String,
+    pub label: String,
+    pub ret_type: Option<String>,
+    pub params: Vec<String>,
+    pub doc: Option<String>,
+}
+
+impl FnSignatureInfo {
+    fn new(node: ast::FnDef) -> Option<Self> {
+        let name = node.name()?.text().to_string();
+
+        let mut doc = None;
+
+        // Strip the body out for the label.
+        let mut label: String = if let Some(body) = node.body() {
+            let body_range = body.syntax().range();
+            let label: String = node
+                .syntax()
+                .children()
+                .filter(|child| !child.range().is_subrange(&body_range))
+                .map(|node| node.text().to_string())
+                .collect();
+            label
+        } else {
+            node.syntax().text().to_string()
+        };
+
+        if let Some((comment_range, docs)) = FnSignatureInfo::extract_doc_comments(node) {
+            let comment_range = comment_range
+                .checked_sub(node.syntax().range().start())
+                .unwrap();
+            let start = comment_range.start().to_usize();
+            let end = comment_range.end().to_usize();
+
+            // Remove the comment from the label
+            label.replace_range(start..end, "");
+
+            // Massage markdown
+            let mut processed_lines = Vec::new();
+            let mut in_code_block = false;
+            for line in docs.lines() {
+                if line.starts_with("```") {
+                    in_code_block = !in_code_block;
+                }
+
+                let line = if in_code_block && line.starts_with("```") && !line.contains("rust") {
+                    "```rust".into()
+                } else {
+                    line.to_string()
+                };
+
+                processed_lines.push(line);
+            }
+
+            if !processed_lines.is_empty() {
+                doc = Some(processed_lines.join("\n"));
+            }
+        }
+
+        let params = FnSignatureInfo::param_list(node);
+        let ret_type = node.ret_type().map(|r| r.syntax().text().to_string());
+
+        Some(FnSignatureInfo {
+            name,
+            ret_type,
+            params,
+            label: label.trim().to_owned(),
+            doc,
+        })
+    }
+
+    fn extract_doc_comments(node: ast::FnDef) -> Option<(TextRange, String)> {
+        if node.doc_comments().count() == 0 {
+            return None;
+        }
+
+        let comment_text = node.doc_comment_text();
+
+        let (begin, end) = node
+            .doc_comments()
+            .map(|comment| comment.syntax().range())
+            .map(|range| (range.start().to_usize(), range.end().to_usize()))
+            .fold((std::usize::MAX, std::usize::MIN), |acc, range| {
+                (min(acc.0, range.0), max(acc.1, range.1))
+            });
+
+        let range = TextRange::from_to(TextUnit::from_usize(begin), TextUnit::from_usize(end));
+
+        Some((range, comment_text))
+    }
+
+    fn param_list(node: ast::FnDef) -> Vec<String> {
+        let mut res = vec![];
+        if let Some(param_list) = node.param_list() {
+            if let Some(self_param) = param_list.self_param() {
+                res.push(self_param.syntax().text().to_string())
+            }
+
+            // Maybe use param.pat here? See if we can just extract the name?
+            //res.extend(param_list.params().map(|p| p.syntax().text().to_string()));
+            res.extend(
+                param_list
+                    .params()
+                    .filter_map(|p| p.pat())
+                    .map(|pat| pat.syntax().text().to_string()),
+            );
+        }
+        res
+    }
+}
diff --git a/crates/ra_hir/src/function/scope.rs b/crates/ra_hir/src/function/scope.rs
new file mode 100644
index 000000000..c8b6b1934
--- /dev/null
+++ b/crates/ra_hir/src/function/scope.rs
@@ -0,0 +1,450 @@
+use rustc_hash::{FxHashMap, FxHashSet};
+
+use ra_syntax::{
+    AstNode, SmolStr, SyntaxNodeRef, TextRange,
+    algo::generate,
+    ast::{self, ArgListOwner, LoopBodyOwner, NameOwner},
+};
+use ra_db::LocalSyntaxPtr;
+
+use crate::{
+    arena::{Arena, Id},
+};
+
+pub(crate) type ScopeId = Id<ScopeData>;
+
+#[derive(Debug, PartialEq, Eq)]
+pub struct FnScopes {
+    pub(crate) self_param: Option<LocalSyntaxPtr>,
+    scopes: Arena<ScopeData>,
+    scope_for: FxHashMap<LocalSyntaxPtr, ScopeId>,
+}
+
+#[derive(Debug, PartialEq, Eq)]
+pub struct ScopeEntry {
+    name: SmolStr,
+    ptr: LocalSyntaxPtr,
+}
+
+#[derive(Debug, PartialEq, Eq)]
+pub(crate) struct ScopeData {
+    parent: Option<ScopeId>,
+    entries: Vec<ScopeEntry>,
+}
+
+impl FnScopes {
+    pub(crate) fn new(fn_def: ast::FnDef) -> FnScopes {
+        let mut scopes = FnScopes {
+            self_param: fn_def
+                .param_list()
+                .and_then(|it| it.self_param())
+                .map(|it| LocalSyntaxPtr::new(it.syntax())),
+            scopes: Arena::default(),
+            scope_for: FxHashMap::default(),
+        };
+        let root = scopes.root_scope();
+        scopes.add_params_bindings(root, fn_def.param_list());
+        if let Some(body) = fn_def.body() {
+            compute_block_scopes(body, &mut scopes, root)
+        }
+        scopes
+    }
+    pub(crate) fn entries(&self, scope: ScopeId) -> &[ScopeEntry] {
+        &self.scopes[scope].entries
+    }
+    pub fn scope_chain<'a>(&'a self, node: SyntaxNodeRef) -> impl Iterator<Item = ScopeId> + 'a {
+        generate(self.scope_for(node), move |&scope| {
+            self.scopes[scope].parent
+        })
+    }
+    pub(crate) fn resolve_local_name<'a>(
+        &'a self,
+        name_ref: ast::NameRef,
+    ) -> Option<&'a ScopeEntry> {
+        let mut shadowed = FxHashSet::default();
+        let ret = self
+            .scope_chain(name_ref.syntax())
+            .flat_map(|scope| self.entries(scope).iter())
+            .filter(|entry| shadowed.insert(entry.name()))
+            .filter(|entry| entry.name() == &name_ref.text())
+            .nth(0);
+        ret
+    }
+
+    pub fn find_all_refs(&self, pat: ast::BindPat) -> Vec<ReferenceDescriptor> {
+        let fn_def = pat.syntax().ancestors().find_map(ast::FnDef::cast).unwrap();
+        let name_ptr = LocalSyntaxPtr::new(pat.syntax());
+        let refs: Vec<_> = fn_def
+            .syntax()
+            .descendants()
+            .filter_map(ast::NameRef::cast)
+            .filter(|name_ref| match self.resolve_local_name(*name_ref) {
+                None => false,
+                Some(entry) => entry.ptr() == name_ptr,
+            })
+            .map(|name_ref| ReferenceDescriptor {
+                name: name_ref.syntax().text().to_string(),
+                range: name_ref.syntax().range(),
+            })
+            .collect();
+
+        refs
+    }
+
+    fn root_scope(&mut self) -> ScopeId {
+        self.scopes.alloc(ScopeData {
+            parent: None,
+            entries: vec![],
+        })
+    }
+    fn new_scope(&mut self, parent: ScopeId) -> ScopeId {
+        self.scopes.alloc(ScopeData {
+            parent: Some(parent),
+            entries: vec![],
+        })
+    }
+    fn add_bindings(&mut self, scope: ScopeId, pat: ast::Pat) {
+        let entries = pat
+            .syntax()
+            .descendants()
+            .filter_map(ast::BindPat::cast)
+            .filter_map(ScopeEntry::new);
+        self.scopes[scope].entries.extend(entries);
+    }
+    fn add_params_bindings(&mut self, scope: ScopeId, params: Option<ast::ParamList>) {
+        params
+            .into_iter()
+            .flat_map(|it| it.params())
+            .filter_map(|it| it.pat())
+            .for_each(|it| self.add_bindings(scope, it));
+    }
+    fn set_scope(&mut self, node: SyntaxNodeRef, scope: ScopeId) {
+        self.scope_for.insert(LocalSyntaxPtr::new(node), scope);
+    }
+    fn scope_for(&self, node: SyntaxNodeRef) -> Option<ScopeId> {
+        node.ancestors()
+            .map(LocalSyntaxPtr::new)
+            .filter_map(|it| self.scope_for.get(&it).map(|&scope| scope))
+            .next()
+    }
+}
+
+impl ScopeEntry {
+    fn new(pat: ast::BindPat) -> Option<ScopeEntry> {
+        let name = pat.name()?;
+        let res = ScopeEntry {
+            name: name.text(),
+            ptr: LocalSyntaxPtr::new(pat.syntax()),
+        };
+        Some(res)
+    }
+    pub(crate) fn name(&self) -> &SmolStr {
+        &self.name
+    }
+    pub(crate) fn ptr(&self) -> LocalSyntaxPtr {
+        self.ptr
+    }
+}
+
+fn compute_block_scopes(block: ast::Block, scopes: &mut FnScopes, mut scope: ScopeId) {
+    for stmt in block.statements() {
+        match stmt {
+            ast::Stmt::LetStmt(stmt) => {
+                if let Some(expr) = stmt.initializer() {
+                    scopes.set_scope(expr.syntax(), scope);
+                    compute_expr_scopes(expr, scopes, scope);
+                }
+                scope = scopes.new_scope(scope);
+                if let Some(pat) = stmt.pat() {
+                    scopes.add_bindings(scope, pat);
+                }
+            }
+            ast::Stmt::ExprStmt(expr_stmt) => {
+                if let Some(expr) = expr_stmt.expr() {
+                    scopes.set_scope(expr.syntax(), scope);
+                    compute_expr_scopes(expr, scopes, scope);
+                }
+            }
+        }
+    }
+    if let Some(expr) = block.expr() {
+        scopes.set_scope(expr.syntax(), scope);
+        compute_expr_scopes(expr, scopes, scope);
+    }
+}
+
+fn compute_expr_scopes(expr: ast::Expr, scopes: &mut FnScopes, scope: ScopeId) {
+    match expr {
+        ast::Expr::IfExpr(e) => {
+            let cond_scope = e
+                .condition()
+                .and_then(|cond| compute_cond_scopes(cond, scopes, scope));
+            if let Some(block) = e.then_branch() {
+                compute_block_scopes(block, scopes, cond_scope.unwrap_or(scope));
+            }
+            if let Some(block) = e.else_branch() {
+                compute_block_scopes(block, scopes, scope);
+            }
+        }
+        ast::Expr::BlockExpr(e) => {
+            if let Some(block) = e.block() {
+                compute_block_scopes(block, scopes, scope);
+            }
+        }
+        ast::Expr::LoopExpr(e) => {
+            if let Some(block) = e.loop_body() {
+                compute_block_scopes(block, scopes, scope);
+            }
+        }
+        ast::Expr::WhileExpr(e) => {
+            let cond_scope = e
+                .condition()
+                .and_then(|cond| compute_cond_scopes(cond, scopes, scope));
+            if let Some(block) = e.loop_body() {
+                compute_block_scopes(block, scopes, cond_scope.unwrap_or(scope));
+            }
+        }
+        ast::Expr::ForExpr(e) => {
+            if let Some(expr) = e.iterable() {
+                compute_expr_scopes(expr, scopes, scope);
+            }
+            let mut scope = scope;
+            if let Some(pat) = e.pat() {
+                scope = scopes.new_scope(scope);
+                scopes.add_bindings(scope, pat);
+            }
+            if let Some(block) = e.loop_body() {
+                compute_block_scopes(block, scopes, scope);
+            }
+        }
+        ast::Expr::LambdaExpr(e) => {
+            let scope = scopes.new_scope(scope);
+            scopes.add_params_bindings(scope, e.param_list());
+            if let Some(body) = e.body() {
+                scopes.set_scope(body.syntax(), scope);
+                compute_expr_scopes(body, scopes, scope);
+            }
+        }
+        ast::Expr::CallExpr(e) => {
+            compute_call_scopes(e.expr(), e.arg_list(), scopes, scope);
+        }
+        ast::Expr::MethodCallExpr(e) => {
+            compute_call_scopes(e.expr(), e.arg_list(), scopes, scope);
+        }
+        ast::Expr::MatchExpr(e) => {
+            if let Some(expr) = e.expr() {
+                compute_expr_scopes(expr, scopes, scope);
+            }
+            for arm in e.match_arm_list().into_iter().flat_map(|it| it.arms()) {
+                let scope = scopes.new_scope(scope);
+                for pat in arm.pats() {
+                    scopes.add_bindings(scope, pat);
+                }
+                if let Some(expr) = arm.expr() {
+                    compute_expr_scopes(expr, scopes, scope);
+                }
+            }
+        }
+        _ => expr
+            .syntax()
+            .children()
+            .filter_map(ast::Expr::cast)
+            .for_each(|expr| compute_expr_scopes(expr, scopes, scope)),
+    };
+
+    fn compute_call_scopes(
+        receiver: Option<ast::Expr>,
+        arg_list: Option<ast::ArgList>,
+        scopes: &mut FnScopes,
+        scope: ScopeId,
+    ) {
+        arg_list
+            .into_iter()
+            .flat_map(|it| it.args())
+            .chain(receiver)
+            .for_each(|expr| compute_expr_scopes(expr, scopes, scope));
+    }
+
+    fn compute_cond_scopes(
+        cond: ast::Condition,
+        scopes: &mut FnScopes,
+        scope: ScopeId,
+    ) -> Option<ScopeId> {
+        if let Some(expr) = cond.expr() {
+            compute_expr_scopes(expr, scopes, scope);
+        }
+        if let Some(pat) = cond.pat() {
+            let s = scopes.new_scope(scope);
+            scopes.add_bindings(s, pat);
+            Some(s)
+        } else {
+            None
+        }
+    }
+}
+
+#[derive(Debug)]
+pub struct ReferenceDescriptor {
+    pub range: TextRange,
+    pub name: String,
+}
+
+#[cfg(test)]
+mod tests {
+    use ra_editor::find_node_at_offset;
+    use ra_syntax::SourceFileNode;
+    use test_utils::extract_offset;
+
+    use super::*;
+
+    fn do_check(code: &str, expected: &[&str]) {
+        let (off, code) = extract_offset(code);
+        let code = {
+            let mut buf = String::new();
+            let off = u32::from(off) as usize;
+            buf.push_str(&code[..off]);
+            buf.push_str("marker");
+            buf.push_str(&code[off..]);
+            buf
+        };
+        let file = SourceFileNode::parse(&code);
+        let marker: ast::PathExpr = find_node_at_offset(file.syntax(), off).unwrap();
+        let fn_def: ast::FnDef = find_node_at_offset(file.syntax(), off).unwrap();
+        let scopes = FnScopes::new(fn_def);
+        let actual = scopes
+            .scope_chain(marker.syntax())
+            .flat_map(|scope| scopes.entries(scope))
+            .map(|it| it.name())
+            .collect::<Vec<_>>();
+        assert_eq!(actual.as_slice(), expected);
+    }
+
+    #[test]
+    fn test_lambda_scope() {
+        do_check(
+            r"
+            fn quux(foo: i32) {
+                let f = |bar, baz: i32| {
+                    <|>
+                };
+            }",
+            &["bar", "baz", "foo"],
+        );
+    }
+
+    #[test]
+    fn test_call_scope() {
+        do_check(
+            r"
+            fn quux() {
+                f(|x| <|> );
+            }",
+            &["x"],
+        );
+    }
+
+    #[test]
+    fn test_metod_call_scope() {
+        do_check(
+            r"
+            fn quux() {
+                z.f(|x| <|> );
+            }",
+            &["x"],
+        );
+    }
+
+    #[test]
+    fn test_loop_scope() {
+        do_check(
+            r"
+            fn quux() {
+                loop {
+                    let x = ();
+                    <|>
+                };
+            }",
+            &["x"],
+        );
+    }
+
+    #[test]
+    fn test_match() {
+        do_check(
+            r"
+            fn quux() {
+                match () {
+                    Some(x) => {
+                        <|>
+                    }
+                };
+            }",
+            &["x"],
+        );
+    }
+
+    #[test]
+    fn test_shadow_variable() {
+        do_check(
+            r"
+            fn foo(x: String) {
+                let x : &str = &x<|>;
+            }",
+            &["x"],
+        );
+    }
+
+    fn do_check_local_name(code: &str, expected_offset: u32) {
+        let (off, code) = extract_offset(code);
+        let file = SourceFileNode::parse(&code);
+        let fn_def: ast::FnDef = find_node_at_offset(file.syntax(), off).unwrap();
+        let name_ref: ast::NameRef = find_node_at_offset(file.syntax(), off).unwrap();
+
+        let scopes = FnScopes::new(fn_def);
+
+        let local_name_entry = scopes.resolve_local_name(name_ref).unwrap();
+        let local_name = local_name_entry.ptr().resolve(&file);
+        let expected_name =
+            find_node_at_offset::<ast::Name>(file.syntax(), expected_offset.into()).unwrap();
+        assert_eq!(local_name.range(), expected_name.syntax().range());
+    }
+
+    #[test]
+    fn test_resolve_local_name() {
+        do_check_local_name(
+            r#"
+            fn foo(x: i32, y: u32) {
+                {
+                    let z = x * 2;
+                }
+                {
+                    let t = x<|> * 3;
+                }
+            }"#,
+            21,
+        );
+    }
+
+    #[test]
+    fn test_resolve_local_name_declaration() {
+        do_check_local_name(
+            r#"
+            fn foo(x: String) {
+                let x : &str = &x<|>;
+            }"#,
+            21,
+        );
+    }
+
+    #[test]
+    fn test_resolve_local_name_shadow() {
+        do_check_local_name(
+            r"
+        fn foo(x: String) {
+            let x : &str = &x;
+            x<|>
+        }",
+            46,
+        );
+    }
+}