18 files changed, 486 insertions, 138 deletions

diff --git a/crates/ra_hir/src/arena.rs b/crates/ra_hir/src/arena.rs
deleted file mode 100644
index d4f9d9cb9..000000000
--- a/crates/ra_hir/src/arena.rs
+++ /dev/null
@@ -1,66 +0,0 @@
-//! A simple id-based arena, similar to https://github.com/fitzgen/id-arena.
-//! We use our own version for more compact id's and to allow inherent impls
-//! on Ids.
-
-use std::{
-    fmt,
-    hash::{Hash, Hasher},
-    marker::PhantomData,
-};
-
-pub struct Id<T> {
-    idx: u32,
-    _ty: PhantomData<fn() -> T>,
-}
-
-impl<T> fmt::Debug for Id<T> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        f.debug_tuple("Id").field(&self.idx).finish()
-    }
-}
-impl<T> Copy for Id<T> {}
-impl<T> Clone for Id<T> {
-    fn clone(&self) -> Id<T> {
-        *self
-    }
-}
-
-impl<T> PartialEq for Id<T> {
-    fn eq(&self, other: &Id<T>) -> bool {
-        self.idx == other.idx
-    }
-}
-
-impl<T> Eq for Id<T> {}
-
-impl<T> Hash for Id<T> {
-    fn hash<H: Hasher>(&self, h: &mut H) {
-        self.idx.hash(h);
-    }
-}
-
-#[derive(Debug, PartialEq, Eq)]
-pub(crate) struct ArenaBehavior<T> {
-    _ty: PhantomData<T>,
-}
-
-impl<T> id_arena::ArenaBehavior for ArenaBehavior<T> {
-    type Id = Id<T>;
-    fn new_arena_id() -> u32 {
-        0
-    }
-    fn new_id(_arena_id: u32, index: usize) -> Id<T> {
-        Id {
-            idx: index as u32,
-            _ty: PhantomData,
-        }
-    }
-    fn index(id: Id<T>) -> usize {
-        id.idx as usize
-    }
-    fn arena_id(_id: Id<T>) -> u32 {
-        0
-    }
-}
-
-pub(crate) type Arena<T> = id_arena::Arena<T, ArenaBehavior<T>>;
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 73a4cdc5c..58296fc6f 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -13,6 +13,7 @@ use crate::{
     nameres::{ItemMap, InputModuleItems}},
     ty::{InferenceResult, Ty},
     adt::{StructData, EnumData},
+    impl_block::ModuleImplBlocks,
 };
 
 salsa::query_group! {
@@ -87,6 +88,11 @@ pub trait HirDatabase: SyntaxDatabase
         type ModuleTreeQuery;
         use fn crate::module::imp::module_tree;
     }
+
+    fn impls_in_module(source_root_id: SourceRootId, module_id: ModuleId) -> Cancelable<Arc<ModuleImplBlocks>> {
+        type ImplsInModuleQuery;
+        use fn crate::impl_block::impls_in_module;
+    }
 }
 
 }
diff --git a/crates/ra_hir/src/function.rs b/crates/ra_hir/src/function.rs
index 5a44132fc..75ef308ae 100644
--- a/crates/ra_hir/src/function.rs
+++ b/crates/ra_hir/src/function.rs
@@ -11,11 +11,11 @@ use ra_syntax::{
     ast::{self, AstNode, DocCommentsOwner, NameOwner},
 };
 
-use crate::{DefId, DefKind, HirDatabase, ty::InferenceResult, Module};
+use crate::{DefId, DefKind, HirDatabase, ty::InferenceResult, Module, Crate, impl_block::ImplBlock};
 
 pub use self::scope::FnScopes;
 
-#[derive(Debug)]
+#[derive(Debug, Clone, PartialEq, Eq)]
 pub struct Function {
     def_id: DefId,
 }
@@ -25,6 +25,10 @@ impl Function {
         Function { def_id }
     }
 
+    pub fn def_id(&self) -> DefId {
+        self.def_id
+    }
+
     pub fn syntax(&self, db: &impl HirDatabase) -> ast::FnDefNode {
         let def_loc = self.def_id.loc(db);
         assert!(def_loc.kind == DefKind::Function);
@@ -48,6 +52,15 @@ impl Function {
     pub fn module(&self, db: &impl HirDatabase) -> Cancelable<Module> {
         self.def_id.module(db)
     }
+
+    pub fn krate(&self, db: &impl HirDatabase) -> Cancelable<Option<Crate>> {
+        self.def_id.krate(db)
+    }
+
+    /// The containing impl block, if this is a method.
+    pub fn impl_block(&self, db: &impl HirDatabase) -> Cancelable<Option<ImplBlock>> {
+        self.def_id.impl_block(db)
+    }
 }
 
 #[derive(Debug, Clone)]
diff --git a/crates/ra_hir/src/function/scope.rs b/crates/ra_hir/src/function/scope.rs
index 3e4cfad0c..42bfe4f32 100644
--- a/crates/ra_hir/src/function/scope.rs
+++ b/crates/ra_hir/src/function/scope.rs
@@ -5,19 +5,19 @@ use ra_syntax::{
     algo::generate,
     ast::{self, ArgListOwner, LoopBodyOwner, NameOwner},
 };
+use ra_arena::{Arena, RawId, impl_arena_id};
 use ra_db::LocalSyntaxPtr;
 
-use crate::{
-    arena::{Arena, Id},
-    Name, AsName,
-};
+use crate::{Name, AsName};
 
-pub(crate) type ScopeId = Id<ScopeData>;
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct ScopeId(RawId);
+impl_arena_id!(ScopeId);
 
 #[derive(Debug, PartialEq, Eq)]
 pub struct FnScopes {
     pub self_param: Option<LocalSyntaxPtr>,
-    scopes: Arena<ScopeData>,
+    scopes: Arena<ScopeId, ScopeData>,
     scope_for: FxHashMap<LocalSyntaxPtr, ScopeId>,
 }
 
diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs
index a09dee8b1..4d6378e02 100644
--- a/crates/ra_hir/src/ids.rs
+++ b/crates/ra_hir/src/ids.rs
@@ -1,10 +1,8 @@
 use ra_db::{SourceRootId, LocationIntener, Cancelable, FileId};
 use ra_syntax::{SourceFileNode, SyntaxKind, SyntaxNode, SyntaxNodeRef, SourceFile, AstNode, ast};
+use ra_arena::{Arena, RawId, impl_arena_id};
 
-use crate::{
-    HirDatabase, PerNs, ModuleId, Module, Def, Function, Struct, Enum,
-    arena::{Arena, Id},
-};
+use crate::{HirDatabase, PerNs, ModuleId, Module, Def, Function, Struct, Enum, ImplBlock, Crate};
 
 /// hir makes a heavy use of ids: integer (u32) handlers to various things. You
 /// can think of id as a pointer (but without a lifetime) or a file descriptor
@@ -48,6 +46,13 @@ impl HirFileId {
         }
     }
 
+    pub(crate) fn as_macro_call_id(self) -> Option<MacroCallId> {
+        match self.0 {
+            HirFileIdRepr::Macro(it) => Some(it),
+            _ => None,
+        }
+    }
+
     pub(crate) fn hir_source_file(db: &impl HirDatabase, file_id: HirFileId) -> SourceFileNode {
         match file_id.0 {
             HirFileIdRepr::File(file_id) => db.source_file(file_id),
@@ -172,6 +177,18 @@ impl DefId {
         let loc = self.loc(db);
         Module::new(db, loc.source_root_id, loc.module_id)
     }
+
+    /// Returns the containing crate.
+    pub fn krate(&self, db: &impl HirDatabase) -> Cancelable<Option<Crate>> {
+        Ok(self.module(db)?.krate(db))
+    }
+
+    /// Returns the containing impl block, if this is an impl item.
+    pub fn impl_block(self, db: &impl HirDatabase) -> Cancelable<Option<ImplBlock>> {
+        let loc = self.loc(db);
+        let module_impls = db.impls_in_module(loc.source_root_id, loc.module_id)?;
+        Ok(ImplBlock::containing(module_impls, self))
+    }
 }
 
 impl DefLoc {
@@ -199,7 +216,9 @@ impl DefKind {
 
 /// Identifier of item within a specific file. This is stable over reparses, so
 /// it's OK to use it as a salsa key/value.
-pub(crate) type SourceFileItemId = Id<SyntaxNode>;
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct SourceFileItemId(RawId);
+impl_arena_id!(SourceFileItemId);
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct SourceItemId {
@@ -212,7 +231,7 @@ pub struct SourceItemId {
 #[derive(Debug, PartialEq, Eq)]
 pub struct SourceFileItems {
     file_id: HirFileId,
-    arena: Arena<SyntaxNode>,
+    arena: Arena<SourceFileItemId, SyntaxNode>,
 }
 
 impl SourceFileItems {
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
new file mode 100644
index 000000000..01afa84c4
--- /dev/null
+++ b/crates/ra_hir/src/impl_block.rs
@@ -0,0 +1,180 @@
+use std::sync::Arc;
+use rustc_hash::FxHashMap;
+
+use ra_arena::{Arena, RawId, impl_arena_id};
+use ra_syntax::ast::{self, AstNode};
+use ra_db::{LocationIntener, Cancelable, SourceRootId};
+
+use crate::{
+    DefId, DefLoc, DefKind, SourceItemId, SourceFileItems,
+    Module, Function,
+    db::HirDatabase,
+    type_ref::TypeRef,
+    module::{ModuleSourceNode, ModuleId},
+};
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct ImplBlock {
+    module_impl_blocks: Arc<ModuleImplBlocks>,
+    impl_id: ImplId,
+}
+
+impl ImplBlock {
+    pub(crate) fn containing(
+        module_impl_blocks: Arc<ModuleImplBlocks>,
+        def_id: DefId,
+    ) -> Option<ImplBlock> {
+        let impl_id = *module_impl_blocks.impls_by_def.get(&def_id)?;
+        Some(ImplBlock {
+            module_impl_blocks,
+            impl_id,
+        })
+    }
+
+    fn impl_data(&self) -> &ImplData {
+        &self.module_impl_blocks.impls[self.impl_id]
+    }
+
+    pub fn target_trait(&self) -> Option<&TypeRef> {
+        self.impl_data().target_trait.as_ref()
+    }
+
+    pub fn target_type(&self) -> &TypeRef {
+        &self.impl_data().target_type
+    }
+
+    pub fn items(&self) -> &[ImplItem] {
+        &self.impl_data().items
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct ImplData {
+    target_trait: Option<TypeRef>,
+    target_type: TypeRef,
+    items: Vec<ImplItem>,
+}
+
+impl ImplData {
+    pub(crate) fn from_ast(
+        db: &impl AsRef<LocationIntener<DefLoc, DefId>>,
+        file_items: &SourceFileItems,
+        module: &Module,
+        node: ast::ImplBlock,
+    ) -> Self {
+        let target_trait = node.target_type().map(TypeRef::from_ast);
+        let target_type = TypeRef::from_ast_opt(node.target_type());
+        let file_id = module.source().file_id();
+        let items = if let Some(item_list) = node.item_list() {
+            item_list
+                .impl_items()
+                .map(|item_node| {
+                    let kind = match item_node {
+                        ast::ImplItem::FnDef(..) => DefKind::Function,
+                        ast::ImplItem::ConstDef(..) => DefKind::Item,
+                        ast::ImplItem::TypeDef(..) => DefKind::Item,
+                    };
+                    let item_id = file_items.id_of_unchecked(item_node.syntax());
+                    let def_loc = DefLoc {
+                        kind,
+                        source_root_id: module.source_root_id,
+                        module_id: module.module_id,
+                        source_item_id: SourceItemId {
+                            file_id,
+                            item_id: Some(item_id),
+                        },
+                    };
+                    let def_id = def_loc.id(db);
+                    match item_node {
+                        ast::ImplItem::FnDef(..) => ImplItem::Method(Function::new(def_id)),
+                        ast::ImplItem::ConstDef(..) => ImplItem::Const(def_id),
+                        ast::ImplItem::TypeDef(..) => ImplItem::Type(def_id),
+                    }
+                })
+                .collect()
+        } else {
+            Vec::new()
+        };
+        ImplData {
+            target_trait,
+            target_type,
+            items,
+        }
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum ImplItem {
+    Method(Function),
+    // these don't have their own types yet
+    Const(DefId),
+    Type(DefId),
+    // Existential
+}
+
+impl ImplItem {
+    pub fn def_id(&self) -> DefId {
+        match self {
+            ImplItem::Method(f) => f.def_id(),
+            ImplItem::Const(def_id) => *def_id,
+            ImplItem::Type(def_id) => *def_id,
+        }
+    }
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct ImplId(pub RawId);
+impl_arena_id!(ImplId);
+
+/// Collection of impl blocks is a two-step process: First we collect the blocks
+/// per-module; then we build an index of all impl blocks in the crate. This
+/// way, we avoid having to do this process for the whole crate whenever someone
+/// types in any file; as long as the impl blocks in the file don't change, we
+/// don't need to do the second step again.
+///
+/// (The second step does not yet exist currently.)
+#[derive(Debug, PartialEq, Eq)]
+pub struct ModuleImplBlocks {
+    impls: Arena<ImplId, ImplData>,
+    impls_by_def: FxHashMap<DefId, ImplId>,
+}
+
+impl ModuleImplBlocks {
+    fn new() -> Self {
+        ModuleImplBlocks {
+            impls: Arena::default(),
+            impls_by_def: FxHashMap::default(),
+        }
+    }
+
+    fn collect(&mut self, db: &impl HirDatabase, module: Module) -> Cancelable<()> {
+        let module_source_node = module.source().resolve(db);
+        let node = match &module_source_node {
+            ModuleSourceNode::SourceFile(node) => node.borrowed().syntax(),
+            ModuleSourceNode::Module(node) => node.borrowed().syntax(),
+        };
+
+        let source_file_items = db.file_items(module.source().file_id());
+
+        for impl_block_ast in node.children().filter_map(ast::ImplBlock::cast) {
+            let impl_block = ImplData::from_ast(db, &source_file_items, &module, impl_block_ast);
+            let id = self.impls.alloc(impl_block);
+            for impl_item in &self.impls[id].items {
+                self.impls_by_def.insert(impl_item.def_id(), id);
+            }
+        }
+
+        Ok(())
+    }
+}
+
+pub(crate) fn impls_in_module(
+    db: &impl HirDatabase,
+    source_root_id: SourceRootId,
+    module_id: ModuleId,
+) -> Cancelable<Arc<ModuleImplBlocks>> {
+    let mut result = ModuleImplBlocks::new();
+    let module = Module::new(db, source_root_id, module_id)?;
+    result.collect(db, module)?;
+    Ok(Arc::new(result))
+}
diff --git a/crates/ra_hir/src/krate.rs b/crates/ra_hir/src/krate.rs
index a0821d15d..5194e280b 100644
--- a/crates/ra_hir/src/krate.rs
+++ b/crates/ra_hir/src/krate.rs
@@ -5,7 +5,7 @@ use crate::{HirDatabase, Module, Name, AsName, HirFileId};
 /// hir::Crate describes a single crate. It's the main inteface with which
 /// crate's dependencies interact. Mostly, it should be just a proxy for the
 /// root module.
-#[derive(Debug)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct Crate {
     crate_id: CrateId,
 }
diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index 8ee52a466..2abcec441 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -19,7 +19,6 @@ pub mod db;
 mod mock;
 mod query_definitions;
 mod path;
-mod arena;
 pub mod source_binder;
 
 mod ids;
@@ -32,6 +31,7 @@ mod function;
 mod adt;
 mod type_ref;
 mod ty;
+mod impl_block;
 
 use crate::{
     db::HirDatabase,
@@ -49,6 +49,7 @@ pub use self::{
     function::{Function, FnScopes},
     adt::{Struct, Enum},
     ty::Ty,
+    impl_block::{ImplBlock, ImplItem},
 };
 
 pub use self::function::FnSignatureInfo;
diff --git a/crates/ra_hir/src/macros.rs b/crates/ra_hir/src/macros.rs
index b7b75e702..1b378c977 100644
--- a/crates/ra_hir/src/macros.rs
+++ b/crates/ra_hir/src/macros.rs
@@ -21,6 +21,7 @@ use crate::{HirDatabase, MacroCallId};
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum MacroDef {
     CTry,
+    Vec,
     QueryGroup,
 }
 
@@ -40,6 +41,8 @@ impl MacroDef {
             let name_ref = path.segment()?.name_ref()?;
             if name_ref.text() == "ctry" {
                 MacroDef::CTry
+            } else if name_ref.text() == "vec" {
+                MacroDef::Vec
             } else if name_ref.text() == "query_group" {
                 MacroDef::QueryGroup
             } else {
@@ -59,6 +62,7 @@ impl MacroDef {
     fn expand(self, input: MacroInput) -> Option<MacroExpansion> {
         match self {
             MacroDef::CTry => self.expand_ctry(input),
+            MacroDef::Vec => self.expand_vec(input),
             MacroDef::QueryGroup => self.expand_query_group(input),
         }
     }
@@ -86,6 +90,20 @@ impl MacroDef {
         };
         Some(res)
     }
+    fn expand_vec(self, input: MacroInput) -> Option<MacroExpansion> {
+        let text = format!(r"fn dummy() {{ {}; }}", input.text);
+        let file = SourceFileNode::parse(&text);
+        let array_expr = file.syntax().descendants().find_map(ast::ArrayExpr::cast)?;
+        let ptr = LocalSyntaxPtr::new(array_expr.syntax());
+        let src_range = TextRange::offset_len(0.into(), TextUnit::of_str(&input.text));
+        let ranges_map = vec![(src_range, array_expr.syntax().range())];
+        let res = MacroExpansion {
+            text,
+            ranges_map,
+            ptr,
+        };
+        Some(res)
+    }
     fn expand_query_group(self, input: MacroInput) -> Option<MacroExpansion> {
         let anchor = "trait ";
         let pos = input.text.find(anchor)? + anchor.len();
diff --git a/crates/ra_hir/src/mock.rs b/crates/ra_hir/src/mock.rs
index 89b18194a..a9db932ff 100644
--- a/crates/ra_hir/src/mock.rs
+++ b/crates/ra_hir/src/mock.rs
@@ -30,6 +30,10 @@ impl MockDatabase {
         let file_id = db.add_file(&mut source_root, "/main.rs", text);
         db.query_mut(ra_db::SourceRootQuery)
             .set(WORKSPACE, Arc::new(source_root.clone()));
+
+        let mut crate_graph = CrateGraph::default();
+        crate_graph.add_crate_root(file_id);
+        db.set_crate_graph(crate_graph);
         (db, source_root, file_id)
     }
 
@@ -203,6 +207,7 @@ salsa::database_storage! {
             fn type_for_field() for db::TypeForFieldQuery;
             fn struct_data() for db::StructDataQuery;
             fn enum_data() for db::EnumDataQuery;
+            fn impls_in_module() for db::ImplsInModuleQuery;
         }
     }
 }
diff --git a/crates/ra_hir/src/module.rs b/crates/ra_hir/src/module.rs
index a53b69d20..b9821115c 100644
--- a/crates/ra_hir/src/module.rs
+++ b/crates/ra_hir/src/module.rs
@@ -9,6 +9,7 @@ use ra_syntax::{
     ast::{self, AstNode, NameOwner},
     SyntaxNode,
 };
+use ra_arena::{Arena, RawId, impl_arena_id};
 use ra_db::{SourceRootId, FileId, Cancelable};
 use relative_path::RelativePathBuf;
 
@@ -16,7 +17,6 @@ use crate::{
     Def, DefKind, DefLoc, DefId,
     Name, Path, PathKind, HirDatabase, SourceItemId, SourceFileItemId, Crate,
     HirFileId,
-    arena::{Arena, Id},
 };
 
 pub use self::nameres::{ModuleScope, Resolution, Namespace, PerNs};
@@ -71,6 +71,21 @@ impl Module {
         })
     }
 
+    /// Returns an iterator of all children of this module.
+    pub fn children<'a>(&'a self) -> impl Iterator<Item = (Name, Module)> + 'a {
+        self.module_id
+            .children(&self.tree)
+            .map(move |(name, module_id)| {
+                (
+                    name,
+                    Module {
+                        module_id,
+                        ..self.clone()
+                    },
+                )
+            })
+    }
+
     /// Returns the crate this module is part of.
     pub fn krate(&self, db: &impl HirDatabase) -> Option<Crate> {
         let root_id = self.module_id.crate_root(&self.tree);
@@ -173,6 +188,14 @@ impl Module {
     }
 }
 
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct ModuleId(RawId);
+impl_arena_id!(ModuleId);
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct LinkId(RawId);
+impl_arena_id!(LinkId);
+
 /// Physically, rust source is organized as a set of files, but logically it is
 /// organized as a tree of modules. Usually, a single file corresponds to a
 /// single module, but it is not nessary the case.
@@ -182,8 +205,8 @@ impl Module {
 /// always have one parent).
 #[derive(Default, Debug, PartialEq, Eq)]
 pub struct ModuleTree {
-    mods: Arena<ModuleData>,
-    links: Arena<LinkData>,
+    mods: Arena<ModuleId, ModuleData>,
+    links: Arena<LinkId, LinkData>,
 }
 
 impl ModuleTree {
@@ -210,9 +233,6 @@ pub(crate) enum ModuleSourceNode {
     Module(ast::ModuleNode),
 }
 
-pub type ModuleId = Id<ModuleData>;
-type LinkId = Id<LinkData>;
-
 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
 pub enum Problem {
     UnresolvedModule {
diff --git a/crates/ra_hir/src/module/nameres.rs b/crates/ra_hir/src/module/nameres.rs
index 40aa33ffa..3c6851a0a 100644
--- a/crates/ra_hir/src/module/nameres.rs
+++ b/crates/ra_hir/src/module/nameres.rs
@@ -64,14 +64,14 @@ impl ModuleScope {
 /// running name resolution.
 #[derive(Debug, Default, PartialEq, Eq)]
 pub struct InputModuleItems {
-    items: Vec<ModuleItem>,
+    pub(crate) items: Vec<ModuleItem>,
     imports: Vec<Import>,
 }
 
 #[derive(Debug, PartialEq, Eq)]
-struct ModuleItem {
-    id: SourceItemId,
-    name: Name,
+pub(crate) struct ModuleItem {
+    pub(crate) id: SourceItemId,
+    pub(crate) name: Name,
     kind: SyntaxKind,
     vis: Vis,
 }
@@ -233,7 +233,7 @@ impl InputModuleItems {
             ast::ModuleItem::TypeDef(it) => {
                 self.items.push(ModuleItem::new(file_id, file_items, it)?)
             }
-            ast::ModuleItem::ImplItem(_) => {
+            ast::ModuleItem::ImplBlock(_) => {
                 // impls don't define items
             }
             ast::ModuleItem::UseItem(it) => self.add_use_item(file_items, it),
diff --git a/crates/ra_hir/src/name.rs b/crates/ra_hir/src/name.rs
index 51e8b3da8..017caf442 100644
--- a/crates/ra_hir/src/name.rs
+++ b/crates/ra_hir/src/name.rs
@@ -51,6 +51,7 @@ impl Name {
             "u128" => KnownName::U128,
             "f32" => KnownName::F32,
             "f64" => KnownName::F64,
+            "Self" => KnownName::Self_,
             _ => return None,
         };
         Some(name)
@@ -84,7 +85,7 @@ impl AsName for ra_db::Dependency {
 // const ISIZE: Name = Name::new("isize")
 // ```
 // but const-fn is not that powerful yet.
-#[derive(Debug)]
+#[derive(Debug, PartialEq, Eq)]
 pub(crate) enum KnownName {
     Isize,
     I8,
@@ -102,4 +103,6 @@ pub(crate) enum KnownName {
 
     F32,
     F64,
+
+    Self_,
 }
diff --git a/crates/ra_hir/src/path.rs b/crates/ra_hir/src/path.rs
index 93f7203fe..9fdfa0d13 100644
--- a/crates/ra_hir/src/path.rs
+++ b/crates/ra_hir/src/path.rs
@@ -70,6 +70,11 @@ impl Path {
         self.kind == PathKind::Plain && self.segments.len() == 1
     }
 
+    /// `true` if this path is just a standalone `self`
+    pub fn is_self(&self) -> bool {
+        self.kind == PathKind::Self_ && self.segments.len() == 0
+    }
+
     /// If this path is a single identifier, like `foo`, return its name.
     pub fn as_ident(&self) -> Option<&Name> {
         if self.kind != PathKind::Plain || self.segments.len() > 1 {
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index 24490d119..85bd84469 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -8,8 +8,8 @@
 use ra_db::{FileId, FilePosition, Cancelable};
 use ra_editor::find_node_at_offset;
 use ra_syntax::{
+    SmolStr, TextRange, SyntaxNodeRef,
     ast::{self, AstNode, NameOwner},
-    SyntaxNodeRef,
 };
 
 use crate::{
@@ -126,3 +126,40 @@ pub fn function_from_child_node(
     let fn_def = ctry!(node.ancestors().find_map(ast::FnDef::cast));
     function_from_source(db, file_id, fn_def)
 }
+
+pub fn macro_symbols(
+    db: &impl HirDatabase,
+    file_id: FileId,
+) -> Cancelable<Vec<(SmolStr, TextRange)>> {
+    let module = match module_from_file_id(db, file_id)? {
+        Some(it) => it,
+        None => return Ok(Vec::new()),
+    };
+    let items = db.input_module_items(module.source_root_id, module.module_id)?;
+    let mut res = Vec::new();
+
+    for macro_call_id in items
+        .items
+        .iter()
+        .filter_map(|it| it.id.file_id.as_macro_call_id())
+    {
+        if let Some(exp) = db.expand_macro_invocation(macro_call_id) {
+            let loc = macro_call_id.loc(db);
+            let syntax = db.file_item(loc.source_item_id);
+            let syntax = syntax.borrowed();
+            let macro_call = ast::MacroCall::cast(syntax).unwrap();
+            let off = macro_call.token_tree().unwrap().syntax().range().start();
+            let file = exp.file();
+            for trait_def in file.syntax().descendants().filter_map(ast::TraitDef::cast) {
+                if let Some(name) = trait_def.name() {
+                    let dst_range = name.syntax().range();
+                    if let Some(src_range) = exp.map_range_back(dst_range) {
+                        res.push((name.text(), src_range + off))
+                    }
+                }
+            }
+        }
+    }
+
+    Ok(res)
+}
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 719b3f7cd..e33762e0d 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -31,9 +31,10 @@ use ra_syntax::{
 };
 
 use crate::{
-    Def, DefId, FnScopes, Module, Function, Struct, Enum, Path, Name, AsName,
+    Def, DefId, FnScopes, Module, Function, Struct, Enum, Path, Name, AsName, ImplBlock,
     db::HirDatabase,
     type_ref::{TypeRef, Mutability},
+    name::KnownName,
 };
 
 /// The ID of a type variable.
@@ -235,6 +236,7 @@ impl Ty {
     pub(crate) fn from_hir(
         db: &impl HirDatabase,
         module: &Module,
+        impl_block: Option<&ImplBlock>,
         type_ref: &TypeRef,
     ) -> Cancelable<Self> {
         Ok(match type_ref {
@@ -242,29 +244,29 @@ impl Ty {
             TypeRef::Tuple(inner) => {
                 let inner_tys = inner
                     .iter()
-                    .map(|tr| Ty::from_hir(db, module, tr))
+                    .map(|tr| Ty::from_hir(db, module, impl_block, tr))
                     .collect::<Cancelable<Vec<_>>>()?;
                 Ty::Tuple(inner_tys.into())
             }
-            TypeRef::Path(path) => Ty::from_hir_path(db, module, path)?,
+            TypeRef::Path(path) => Ty::from_hir_path(db, module, impl_block, path)?,
             TypeRef::RawPtr(inner, mutability) => {
-                let inner_ty = Ty::from_hir(db, module, inner)?;
+                let inner_ty = Ty::from_hir(db, module, impl_block, inner)?;
                 Ty::RawPtr(Arc::new(inner_ty), *mutability)
             }
             TypeRef::Array(_inner) => Ty::Unknown, // TODO
             TypeRef::Slice(inner) => {
-                let inner_ty = Ty::from_hir(db, module, inner)?;
+                let inner_ty = Ty::from_hir(db, module, impl_block, inner)?;
                 Ty::Slice(Arc::new(inner_ty))
             }
             TypeRef::Reference(inner, mutability) => {
-                let inner_ty = Ty::from_hir(db, module, inner)?;
+                let inner_ty = Ty::from_hir(db, module, impl_block, inner)?;
                 Ty::Ref(Arc::new(inner_ty), *mutability)
             }
             TypeRef::Placeholder => Ty::Unknown,
             TypeRef::Fn(params) => {
                 let mut inner_tys = params
                     .iter()
-                    .map(|tr| Ty::from_hir(db, module, tr))
+                    .map(|tr| Ty::from_hir(db, module, impl_block, tr))
                     .collect::<Cancelable<Vec<_>>>()?;
                 let return_ty = inner_tys
                     .pop()
@@ -279,9 +281,21 @@ impl Ty {
         })
     }
 
+    pub(crate) fn from_hir_opt(
+        db: &impl HirDatabase,
+        module: &Module,
+        impl_block: Option<&ImplBlock>,
+        type_ref: Option<&TypeRef>,
+    ) -> Cancelable<Self> {
+        type_ref
+            .map(|t| Ty::from_hir(db, module, impl_block, t))
+            .unwrap_or(Ok(Ty::Unknown))
+    }
+
     pub(crate) fn from_hir_path(
         db: &impl HirDatabase,
         module: &Module,
+        impl_block: Option<&ImplBlock>,
         path: &Path,
     ) -> Cancelable<Self> {
         if let Some(name) = path.as_ident() {
@@ -291,6 +305,8 @@ impl Ty {
                 return Ok(Ty::Uint(uint_ty));
             } else if let Some(float_ty) = primitive::FloatTy::from_name(name) {
                 return Ok(Ty::Float(float_ty));
+            } else if name.as_known_name() == Some(KnownName::Self_) {
+                return Ty::from_hir_opt(db, module, None, impl_block.map(|i| i.target_type()));
             }
         }
 
@@ -308,18 +324,20 @@ impl Ty {
     pub(crate) fn from_ast_opt(
         db: &impl HirDatabase,
         module: &Module,
+        impl_block: Option<&ImplBlock>,
         node: Option<ast::TypeRef>,
     ) -> Cancelable<Self> {
-        node.map(|n| Ty::from_ast(db, module, n))
+        node.map(|n| Ty::from_ast(db, module, impl_block, n))
             .unwrap_or(Ok(Ty::Unknown))
     }
 
     pub(crate) fn from_ast(
         db: &impl HirDatabase,
         module: &Module,
+        impl_block: Option<&ImplBlock>,
         node: ast::TypeRef,
     ) -> Cancelable<Self> {
-        Ty::from_hir(db, module, &TypeRef::from_ast(node))
+        Ty::from_hir(db, module, impl_block, &TypeRef::from_ast(node))
     }
 
     pub fn unit() -> Self {
@@ -402,18 +420,19 @@ impl fmt::Display for Ty {
 fn type_for_fn(db: &impl HirDatabase, f: Function) -> Cancelable<Ty> {
     let syntax = f.syntax(db);
     let module = f.module(db)?;
+    let impl_block = f.impl_block(db)?;
     let node = syntax.borrowed();
     // TODO we ignore type parameters for now
     let input = node
         .param_list()
         .map(|pl| {
             pl.params()
-                .map(|p| Ty::from_ast_opt(db, &module, p.type_ref()))
+                .map(|p| Ty::from_ast_opt(db, &module, impl_block.as_ref(), p.type_ref()))
                 .collect()
         })
         .unwrap_or_else(|| Ok(Vec::new()))?;
     let output = if let Some(type_ref) = node.ret_type().and_then(|rt| rt.type_ref()) {
-        Ty::from_ast(db, &module, type_ref)?
+        Ty::from_ast(db, &module, impl_block.as_ref(), type_ref)?
     } else {
         Ty::unit()
     };
@@ -467,12 +486,13 @@ pub(super) fn type_for_field(db: &impl HirDatabase, def_id: DefId, field: Name)
         ),
     };
     let module = def_id.module(db)?;
+    let impl_block = def_id.impl_block(db)?;
     let type_ref = if let Some(tr) = variant_data.get_field_type_ref(&field) {
         tr
     } else {
         return Ok(Ty::Unknown);
     };
-    Ty::from_hir(db, &module, &type_ref)
+    Ty::from_hir(db, &module, impl_block.as_ref(), &type_ref)
 }
 
 /// The result of type inference: A mapping from expressions and patterns to types.
@@ -496,19 +516,32 @@ impl InferenceResult {
 struct InferenceContext<'a, D: HirDatabase> {
     db: &'a D,
     scopes: Arc<FnScopes>,
+    /// The self param for the current method, if it exists.
+    self_param: Option<LocalSyntaxPtr>,
     module: Module,
+    impl_block: Option<ImplBlock>,
     var_unification_table: InPlaceUnificationTable<TypeVarId>,
     type_of: FxHashMap<LocalSyntaxPtr, Ty>,
+    /// The return type of the function being inferred.
+    return_ty: Ty,
 }
 
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
-    fn new(db: &'a D, scopes: Arc<FnScopes>, module: Module) -> Self {
+    fn new(
+        db: &'a D,
+        scopes: Arc<FnScopes>,
+        module: Module,
+        impl_block: Option<ImplBlock>,
+    ) -> Self {
         InferenceContext {
             type_of: FxHashMap::default(),
             var_unification_table: InPlaceUnificationTable::new(),
+            self_param: None,       // set during parameter typing
+            return_ty: Ty::Unknown, // set in collect_fn_signature
             db,
             scopes,
             module,
+            impl_block,
         }
     }
 
@@ -525,6 +558,14 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         self.type_of.insert(LocalSyntaxPtr::new(node), ty);
     }
 
+    fn make_ty(&self, type_ref: &TypeRef) -> Cancelable<Ty> {
+        Ty::from_hir(self.db, &self.module, self.impl_block.as_ref(), type_ref)
+    }
+
+    fn make_ty_opt(&self, type_ref: Option<&TypeRef>) -> Cancelable<Ty> {
+        Ty::from_hir_opt(self.db, &self.module, self.impl_block.as_ref(), type_ref)
+    }
+
     fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
         match (ty1, ty2) {
             (Ty::Unknown, ..) => true,
@@ -628,6 +669,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 let ty = self.resolve_ty_as_possible(ty.clone());
                 return Ok(Some(ty));
             };
+        } else if path.is_self() {
+            // resolve `self` param
+            let self_param = ctry!(self.self_param);
+            let ty = ctry!(self.type_of.get(&self_param));
+            let ty = self.resolve_ty_as_possible(ty.clone());
+            return Ok(Some(ty));
         };
 
         // resolve in module
@@ -826,7 +873,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             }
             ast::Expr::CastExpr(e) => {
                 let _inner_ty = self.infer_expr_opt(e.expr(), &Expectation::none())?;
-                let cast_ty = Ty::from_ast_opt(self.db, &self.module, e.type_ref())?;
+                let cast_ty = Ty::from_ast_opt(
+                    self.db,
+                    &self.module,
+                    self.impl_block.as_ref(),
+                    e.type_ref(),
+                )?;
                 let cast_ty = self.insert_type_vars(cast_ty);
                 // TODO do the coercion...
                 cast_ty
@@ -880,7 +932,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         for stmt in node.statements() {
             match stmt {
                 ast::Stmt::LetStmt(stmt) => {
-                    let decl_ty = Ty::from_ast_opt(self.db, &self.module, stmt.type_ref())?;
+                    let decl_ty = Ty::from_ast_opt(
+                        self.db,
+                        &self.module,
+                        self.impl_block.as_ref(),
+                        stmt.type_ref(),
+                    )?;
                     let decl_ty = self.insert_type_vars(decl_ty);
                     let ty = if let Some(expr) = stmt.initializer() {
                         let expr_ty = self.infer_expr(expr, &Expectation::has_type(decl_ty))?;
@@ -906,46 +963,71 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         self.write_ty(node.syntax(), ty.clone());
         Ok(ty)
     }
+
+    fn collect_fn_signature(&mut self, node: ast::FnDef) -> Cancelable<()> {
+        if let Some(param_list) = node.param_list() {
+            if let Some(self_param) = param_list.self_param() {
+                let self_type = if let Some(type_ref) = self_param.type_ref() {
+                    let ty = self.make_ty(&TypeRef::from_ast(type_ref))?;
+                    self.insert_type_vars(ty)
+                } else {
+                    // TODO this should be handled by desugaring during HIR conversion
+                    let ty = self.make_ty_opt(self.impl_block.as_ref().map(|i| i.target_type()))?;
+                    let ty = match self_param.flavor() {
+                        ast::SelfParamFlavor::Owned => ty,
+                        ast::SelfParamFlavor::Ref => Ty::Ref(Arc::new(ty), Mutability::Shared),
+                        ast::SelfParamFlavor::MutRef => Ty::Ref(Arc::new(ty), Mutability::Mut),
+                    };
+                    self.insert_type_vars(ty)
+                };
+                if let Some(self_kw) = self_param.self_kw() {
+                    let self_param = LocalSyntaxPtr::new(self_kw.syntax());
+                    self.self_param = Some(self_param);
+                    self.type_of.insert(self_param, self_type);
+                }
+            }
+            for param in param_list.params() {
+                let pat = if let Some(pat) = param.pat() {
+                    pat
+                } else {
+                    continue;
+                };
+                let ty = if let Some(type_ref) = param.type_ref() {
+                    let ty = self.make_ty(&TypeRef::from_ast(type_ref))?;
+                    self.insert_type_vars(ty)
+                } else {
+                    // missing type annotation
+                    self.new_type_var()
+                };
+                self.type_of.insert(LocalSyntaxPtr::new(pat.syntax()), ty);
+            }
+        }
+
+        self.return_ty = if let Some(type_ref) = node.ret_type().and_then(|n| n.type_ref()) {
+            let ty = self.make_ty(&TypeRef::from_ast(type_ref))?;
+            self.insert_type_vars(ty)
+        } else {
+            Ty::unit()
+        };
+
+        Ok(())
+    }
 }
 
 pub fn infer(db: &impl HirDatabase, def_id: DefId) -> Cancelable<Arc<InferenceResult>> {
     let function = Function::new(def_id); // TODO: consts also need inference
     let scopes = function.scopes(db);
     let module = function.module(db)?;
-    let mut ctx = InferenceContext::new(db, scopes, module);
+    let impl_block = function.impl_block(db)?;
+    let mut ctx = InferenceContext::new(db, scopes, module, impl_block);
 
     let syntax = function.syntax(db);
     let node = syntax.borrowed();
 
-    if let Some(param_list) = node.param_list() {
-        for param in param_list.params() {
-            let pat = if let Some(pat) = param.pat() {
-                pat
-            } else {
-                continue;
-            };
-            if let Some(type_ref) = param.type_ref() {
-                let ty = Ty::from_ast(db, &ctx.module, type_ref)?;
-                let ty = ctx.insert_type_vars(ty);
-                ctx.type_of.insert(LocalSyntaxPtr::new(pat.syntax()), ty);
-            } else {
-                // TODO self param
-                let type_var = ctx.new_type_var();
-                ctx.type_of
-                    .insert(LocalSyntaxPtr::new(pat.syntax()), type_var);
-            };
-        }
-    }
-
-    let ret_ty = if let Some(type_ref) = node.ret_type().and_then(|n| n.type_ref()) {
-        let ty = Ty::from_ast(db, &ctx.module, type_ref)?;
-        ctx.insert_type_vars(ty)
-    } else {
-        Ty::unit()
-    };
+    ctx.collect_fn_signature(node)?;
 
     if let Some(block) = node.body() {
-        ctx.infer_block(block, &Expectation::has_type(ret_ty))?;
+        ctx.infer_block(block, &Expectation::has_type(ctx.return_ty.clone()))?;
     }
 
     Ok(Arc::new(ctx.resolve_all()))
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 93bf431c4..fb53fcf0b 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -134,6 +134,25 @@ fn test() -> &mut &f64 {
     );
 }
 
+#[test]
+fn infer_self() {
+    check_inference(
+        r#"
+struct S;
+
+impl S {
+    fn test(&self) {
+        self;
+    }
+    fn test2(self: &Self) {
+        self;
+    }
+}
+"#,
+        "0007_self.txt",
+    );
+}
+
 fn infer(content: &str) -> String {
     let (db, _, file_id) = MockDatabase::with_single_file(content);
     let source_file = db.source_file(file_id);
diff --git a/crates/ra_hir/src/ty/tests/data/0007_self.txt b/crates/ra_hir/src/ty/tests/data/0007_self.txt
new file mode 100644
index 000000000..db4ba17d0
--- /dev/null
+++ b/crates/ra_hir/src/ty/tests/data/0007_self.txt
@@ -0,0 +1,6 @@
+[50; 54) 'self': &S
+[34; 38) 'self': &S
+[40; 61) '{     ...     }': ()
+[88; 109) '{     ...     }': ()
+[98; 102) 'self': &S
+[75; 79) 'self': &S