23 files changed, 319 insertions, 208 deletions

diff --git a/crates/ra_assists/src/assists/add_missing_impl_members.rs b/crates/ra_assists/src/assists/add_missing_impl_members.rs
index 23da1e65f..682455bce 100644
--- a/crates/ra_assists/src/assists/add_missing_impl_members.rs
+++ b/crates/ra_assists/src/assists/add_missing_impl_members.rs
@@ -100,12 +100,11 @@ fn strip_docstring(item: ast::ImplItem) -> ast::ImplItem {
 }
 
 fn add_body(fn_def: ast::FnDef) -> ast::FnDef {
-    let mut ast_editor = AstEditor::new(fn_def.clone());
     if fn_def.body().is_none() {
-        let body = make::block_from_expr(make::expr_unimplemented());
-        ast_editor.set_body(&body);
+        fn_def.with_body(make::block_from_expr(make::expr_unimplemented()))
+    } else {
+        fn_def
     }
-    ast_editor.ast().to_owned()
 }
 
 /// Given an `ast::ImplBlock`, resolves the target trait (the one being
@@ -332,5 +331,4 @@ impl Foo for S {
 }",
         )
     }
-
 }
diff --git a/crates/ra_assists/src/assists/auto_import.rs b/crates/ra_assists/src/assists/auto_import.rs
index 43c14ad23..419e93330 100644
--- a/crates/ra_assists/src/assists/auto_import.rs
+++ b/crates/ra_assists/src/assists/auto_import.rs
@@ -448,7 +448,6 @@ fn make_assist_add_in_tree_list(
         fmt_segments_raw(target, &mut buf);
         edit.insert(offset, buf);
     } else {
-
     }
 }
 
diff --git a/crates/ra_assists/src/ast_editor.rs b/crates/ra_assists/src/ast_editor.rs
index 2a685f26e..72c8c478a 100644
--- a/crates/ra_assists/src/ast_editor.rs
+++ b/crates/ra_assists/src/ast_editor.rs
@@ -6,7 +6,7 @@ use rustc_hash::FxHashMap;
 use ra_fmt::leading_indent;
 use ra_syntax::{
     algo,
-    ast::{self, TypeBoundsOwner},
+    ast::{self, make::tokens, TypeBoundsOwner},
     AstNode, Direction, InsertPosition, SyntaxElement,
     SyntaxKind::*,
     T,
@@ -229,26 +229,6 @@ impl AstEditor<ast::ImplItem> {
     }
 }
 
-impl AstEditor<ast::FnDef> {
-    pub fn set_body(&mut self, body: &ast::Block) {
-        let mut to_insert: ArrayVec<[SyntaxElement; 2]> = ArrayVec::new();
-        let old_body_or_semi: SyntaxElement = if let Some(old_body) = self.ast().body() {
-            old_body.syntax().clone().into()
-        } else if let Some(semi) = self.ast().semicolon_token() {
-            to_insert.push(tokens::single_space().into());
-            semi.into()
-        } else {
-            to_insert.push(tokens::single_space().into());
-            to_insert.push(body.syntax().clone().into());
-            self.ast = self.insert_children(InsertPosition::Last, to_insert.into_iter());
-            return;
-        };
-        to_insert.push(body.syntax().clone().into());
-        let replace_range = RangeInclusive::new(old_body_or_semi.clone(), old_body_or_semi);
-        self.ast = self.replace_children(replace_range, to_insert.into_iter())
-    }
-}
-
 impl AstEditor<ast::TypeParam> {
     pub fn remove_bounds(&mut self) -> &mut Self {
         let colon = match self.ast.colon_token() {
@@ -263,53 +243,3 @@ impl AstEditor<ast::TypeParam> {
         self
     }
 }
-
-mod tokens {
-    use once_cell::sync::Lazy;
-    use ra_syntax::{AstNode, Parse, SourceFile, SyntaxKind::*, SyntaxToken, T};
-
-    static SOURCE_FILE: Lazy<Parse<SourceFile>> = Lazy::new(|| SourceFile::parse(",\n; ;"));
-
-    pub(crate) fn comma() -> SyntaxToken {
-        SOURCE_FILE
-            .tree()
-            .syntax()
-            .descendants_with_tokens()
-            .filter_map(|it| it.into_token())
-            .find(|it| it.kind() == T![,])
-            .unwrap()
-    }
-
-    pub(crate) fn single_space() -> SyntaxToken {
-        SOURCE_FILE
-            .tree()
-            .syntax()
-            .descendants_with_tokens()
-            .filter_map(|it| it.into_token())
-            .find(|it| it.kind() == WHITESPACE && it.text().as_str() == " ")
-            .unwrap()
-    }
-
-    #[allow(unused)]
-    pub(crate) fn single_newline() -> SyntaxToken {
-        SOURCE_FILE
-            .tree()
-            .syntax()
-            .descendants_with_tokens()
-            .filter_map(|it| it.into_token())
-            .find(|it| it.kind() == WHITESPACE && it.text().as_str() == "\n")
-            .unwrap()
-    }
-
-    pub(crate) struct WsBuilder(SourceFile);
-
-    impl WsBuilder {
-        pub(crate) fn new(text: &str) -> WsBuilder {
-            WsBuilder(SourceFile::parse(text).ok().unwrap())
-        }
-        pub(crate) fn ws(&self) -> SyntaxToken {
-            self.0.syntax().first_child_or_token().unwrap().into_token().unwrap()
-        }
-    }
-
-}
diff --git a/crates/ra_assists/src/lib.rs b/crates/ra_assists/src/lib.rs
index 897af2b02..3ca3320f7 100644
--- a/crates/ra_assists/src/lib.rs
+++ b/crates/ra_assists/src/lib.rs
@@ -340,5 +340,4 @@ mod tests {
         assert_eq!(assists.next().expect("expected assist").0.label, "introduce variable");
         assert_eq!(assists.next().expect("expected assist").0.label, "replace with match");
     }
-
 }
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 20413cb3d..fd7afcbb6 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -339,10 +339,14 @@ pub struct Struct {
 }
 
 impl Struct {
-    pub fn module(self, db: &impl HirDatabase) -> Module {
+    pub fn module(self, db: &impl DefDatabase) -> Module {
         self.id.module(db)
     }
 
+    pub fn krate(self, db: &impl DefDatabase) -> Option<Crate> {
+        self.module(db).krate(db)
+    }
+
     pub fn name(self, db: &impl DefDatabase) -> Option<Name> {
         db.struct_data(self).name.clone()
     }
@@ -423,10 +427,14 @@ pub struct Enum {
 }
 
 impl Enum {
-    pub fn module(self, db: &impl HirDatabase) -> Module {
+    pub fn module(self, db: &impl DefDatabase) -> Module {
         self.id.module(db)
     }
 
+    pub fn krate(self, db: &impl DefDatabase) -> Option<Crate> {
+        self.module(db).krate(db)
+    }
+
     pub fn name(self, db: &impl DefDatabase) -> Option<Name> {
         db.enum_data(self).name.clone()
     }
@@ -514,7 +522,7 @@ impl Adt {
         }
     }
 
-    pub(crate) fn krate(self, db: &impl HirDatabase) -> Option<Crate> {
+    pub fn krate(self, db: &impl HirDatabase) -> Option<Crate> {
         match self {
             Adt::Struct(s) => s.module(db),
             Adt::Union(s) => s.module(db),
diff --git a/crates/ra_hir/src/marks.rs b/crates/ra_hir/src/marks.rs
index 72f76bb79..0fed46802 100644
--- a/crates/ra_hir/src/marks.rs
+++ b/crates/ra_hir/src/marks.rs
@@ -9,7 +9,6 @@ test_utils::marks!(
     glob_across_crates
     std_prelude
     match_ergonomics_ref
-    trait_resolution_on_fn_type
     infer_while_let
     macro_rules_from_other_crates_are_visible_with_macro_use
     prelude_is_macro_use
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index fae9c1e22..d161735e8 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -14,11 +14,11 @@ pub(crate) mod display;
 
 use std::ops::Deref;
 use std::sync::Arc;
-use std::{fmt, mem};
+use std::{fmt, iter, mem};
 
 use crate::{
-    db::HirDatabase, expr::ExprId, type_ref::Mutability, Adt, DefWithBody, GenericParams, Name,
-    Trait, TypeAlias,
+    db::HirDatabase, expr::ExprId, type_ref::Mutability, Adt, Crate, DefWithBody, GenericParams,
+    HasGenericParams, Name, Trait, TypeAlias,
 };
 use display::{HirDisplay, HirFormatter};
 
@@ -111,6 +111,81 @@ pub enum TypeCtor {
     Closure { def: DefWithBody, expr: ExprId },
 }
 
+impl TypeCtor {
+    pub fn num_ty_params(self, db: &impl HirDatabase) -> usize {
+        match self {
+            TypeCtor::Bool
+            | TypeCtor::Char
+            | TypeCtor::Int(_)
+            | TypeCtor::Float(_)
+            | TypeCtor::Str
+            | TypeCtor::Never => 0,
+            TypeCtor::Slice
+            | TypeCtor::Array
+            | TypeCtor::RawPtr(_)
+            | TypeCtor::Ref(_)
+            | TypeCtor::Closure { .. } // 1 param representing the signature of the closure
+            => 1,
+            TypeCtor::Adt(adt) => {
+                let generic_params = adt.generic_params(db);
+                generic_params.count_params_including_parent()
+            }
+            TypeCtor::FnDef(callable) => {
+                let generic_params = callable.generic_params(db);
+                generic_params.count_params_including_parent()
+            }
+            TypeCtor::AssociatedType(type_alias) => {
+                let generic_params = type_alias.generic_params(db);
+                generic_params.count_params_including_parent()
+            }
+            TypeCtor::FnPtr { num_args } => num_args as usize + 1,
+            TypeCtor::Tuple { cardinality } => cardinality as usize,
+        }
+    }
+
+    pub fn krate(self, db: &impl HirDatabase) -> Option<Crate> {
+        match self {
+            TypeCtor::Bool
+            | TypeCtor::Char
+            | TypeCtor::Int(_)
+            | TypeCtor::Float(_)
+            | TypeCtor::Str
+            | TypeCtor::Never
+            | TypeCtor::Slice
+            | TypeCtor::Array
+            | TypeCtor::RawPtr(_)
+            | TypeCtor::Ref(_)
+            | TypeCtor::FnPtr { .. }
+            | TypeCtor::Tuple { .. } => None,
+            TypeCtor::Closure { def, .. } => def.krate(db),
+            TypeCtor::Adt(adt) => adt.krate(db),
+            TypeCtor::FnDef(callable) => callable.krate(db),
+            TypeCtor::AssociatedType(type_alias) => type_alias.krate(db),
+        }
+    }
+
+    pub fn as_generic_def(self) -> Option<crate::generics::GenericDef> {
+        match self {
+            TypeCtor::Bool
+            | TypeCtor::Char
+            | TypeCtor::Int(_)
+            | TypeCtor::Float(_)
+            | TypeCtor::Str
+            | TypeCtor::Never
+            | TypeCtor::Slice
+            | TypeCtor::Array
+            | TypeCtor::RawPtr(_)
+            | TypeCtor::Ref(_)
+            | TypeCtor::FnPtr { .. }
+            | TypeCtor::Tuple { .. }
+            | TypeCtor::Closure { .. } => None,
+            TypeCtor::Adt(adt) => Some(adt.into()),
+            TypeCtor::FnDef(callable) => Some(callable.into()),
+            TypeCtor::AssociatedType(type_alias) => Some(type_alias.into()),
+        }
+    }
+}
+
 /// A nominal type with (maybe 0) type parameters. This might be a primitive
 /// type like `bool`, a struct, tuple, function pointer, reference or
 /// several other things.
@@ -271,11 +346,65 @@ impl Substs {
                 .into(),
         )
     }
+
+    pub fn build_for_def(
+        db: &impl HirDatabase,
+        def: impl crate::HasGenericParams,
+    ) -> SubstsBuilder {
+        let params = def.generic_params(db);
+        let param_count = params.count_params_including_parent();
+        Substs::builder(param_count)
+    }
+
+    pub fn build_for_generics(generic_params: &GenericParams) -> SubstsBuilder {
+        Substs::builder(generic_params.count_params_including_parent())
+    }
+
+    pub fn build_for_type_ctor(db: &impl HirDatabase, type_ctor: TypeCtor) -> SubstsBuilder {
+        Substs::builder(type_ctor.num_ty_params(db))
+    }
+
+    fn builder(param_count: usize) -> SubstsBuilder {
+        SubstsBuilder { vec: Vec::with_capacity(param_count), param_count }
+    }
+}
+
+#[derive(Debug, Clone)]
+pub struct SubstsBuilder {
+    vec: Vec<Ty>,
+    param_count: usize,
 }
 
-impl From<Vec<Ty>> for Substs {
-    fn from(v: Vec<Ty>) -> Self {
-        Substs(v.into())
+impl SubstsBuilder {
+    pub fn build(self) -> Substs {
+        assert_eq!(self.vec.len(), self.param_count);
+        Substs(self.vec.into())
+    }
+
+    pub fn push(mut self, ty: Ty) -> Self {
+        self.vec.push(ty);
+        self
+    }
+
+    fn remaining(&self) -> usize {
+        self.param_count - self.vec.len()
+    }
+
+    pub fn fill_with_bound_vars(mut self, starting_from: u32) -> Self {
+        self.vec.extend((starting_from..starting_from + self.remaining() as u32).map(Ty::Bound));
+        self
+    }
+
+    pub fn fill_with_unknown(mut self) -> Self {
+        self.vec.extend(iter::repeat(Ty::Unknown).take(self.remaining()));
+        self
+    }
+
+    pub fn use_parent_substs(mut self, parent_substs: &Substs) -> Self {
+        assert!(self.vec.is_empty());
+        assert!(parent_substs.len() <= self.param_count);
+        self.vec.extend(parent_substs.iter().cloned());
+        self
     }
 }
 
diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir/src/ty/autoderef.rs
index 94f8ecdc9..02492ca14 100644
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ b/crates/ra_hir/src/ty/autoderef.rs
@@ -7,7 +7,7 @@ use std::iter::successors;
 
 use log::{info, warn};
 
-use super::{traits::Solution, Canonical, Ty, TypeWalk};
+use super::{traits::Solution, Canonical, Substs, Ty, TypeWalk};
 use crate::{db::HirDatabase, name, HasGenericParams, Resolver};
 
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
@@ -44,7 +44,8 @@ fn deref_by_trait(
     };
     let target = deref_trait.associated_type_by_name(db, &name::TARGET_TYPE)?;
 
-    if target.generic_params(db).count_params_including_parent() != 1 {
+    let generic_params = target.generic_params(db);
+    if generic_params.count_params_including_parent() != 1 {
         // the Target type + Deref trait should only have one generic parameter,
         // namely Deref's Self type
         return None;
@@ -54,12 +55,13 @@ fn deref_by_trait(
 
     let env = super::lower::trait_env(db, resolver);
 
+    let parameters = Substs::build_for_generics(&generic_params)
+        .push(ty.value.clone().shift_bound_vars(1))
+        .build();
+
     let projection = super::traits::ProjectionPredicate {
         ty: Ty::Bound(0),
-        projection_ty: super::ProjectionTy {
-            associated_ty: target,
-            parameters: vec![ty.value.clone().shift_bound_vars(1)].into(),
-        },
+        projection_ty: super::ProjectionTy { associated_ty: target, parameters },
     };
 
     let obligation = super::Obligation::Projection(projection);
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index 8f92468e6..2e4a489a0 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -688,14 +688,13 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 };
                 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
 
-                let inner_tys: Substs = args
+                let inner_tys = args
                     .iter()
                     .zip(expectations_iter)
                     .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm))
-                    .collect::<Vec<_>>()
-                    .into();
+                    .collect();
 
-                Ty::apply(TypeCtor::Tuple { cardinality: inner_tys.len() as u16 }, inner_tys)
+                Ty::apply(TypeCtor::Tuple { cardinality: args.len() as u16 }, Substs(inner_tys))
             }
             Pat::Ref { pat, mutability } => {
                 let expectation = match expected.as_reference() {
@@ -1229,7 +1228,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                             ty: pat_ty.clone(),
                             projection_ty: ProjectionTy {
                                 associated_ty: into_iter_item_alias,
-                                parameters: vec![iterable_ty].into(),
+                                parameters: Substs::single(iterable_ty),
                             },
                         };
                         self.obligations.push(Obligation::Projection(projection));
@@ -1262,7 +1261,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 sig_tys.push(ret_ty.clone());
                 let sig_ty = Ty::apply(
                     TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 },
-                    sig_tys.into(),
+                    Substs(sig_tys.into()),
                 );
                 let closure_ty = Ty::apply_one(
                     TypeCtor::Closure { def: self.body.owner(), expr: tgt_expr },
@@ -1399,7 +1398,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                             ty: ty.clone(),
                             projection_ty: ProjectionTy {
                                 associated_ty: future_future_output_alias,
-                                parameters: vec![inner_ty].into(),
+                                parameters: Substs::single(inner_ty),
                             },
                         };
                         self.obligations.push(Obligation::Projection(projection));
@@ -1418,7 +1417,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                             ty: ty.clone(),
                             projection_ty: ProjectionTy {
                                 associated_ty: ops_try_ok_alias,
-                                parameters: vec![inner_ty].into(),
+                                parameters: Substs::single(inner_ty),
                             },
                         };
                         self.obligations.push(Obligation::Projection(projection));
diff --git a/crates/ra_hir/src/ty/infer/path.rs b/crates/ra_hir/src/ty/infer/path.rs
index feb7481b2..db979353a 100644
--- a/crates/ra_hir/src/ty/infer/path.rs
+++ b/crates/ra_hir/src/ty/infer/path.rs
@@ -158,13 +158,13 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             AssocItem::Const(c) => ValueNs::Const(c),
             AssocItem::TypeAlias(_) => unreachable!(),
         };
-        let generics = item.generic_params(self.db);
-        let mut substs = Vec::with_capacity(generics.count_params_including_parent());
-        substs.extend(trait_ref.substs.iter().cloned());
-        substs.extend(std::iter::repeat(Ty::Unknown).take(generics.params.len()));
+        let substs = Substs::build_for_def(self.db, item)
+            .use_parent_substs(&trait_ref.substs)
+            .fill_with_unknown()
+            .build();
 
         self.write_assoc_resolution(id, item);
-        Some((def, Some(substs.into())))
+        Some((def, Some(substs)))
     }
 
     fn resolve_ty_assoc_item(
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
index b6ebee3b1..d161aa6b3 100644
--- a/crates/ra_hir/src/ty/infer/unify.rs
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -3,7 +3,8 @@
 use super::{InferenceContext, Obligation};
 use crate::db::HirDatabase;
 use crate::ty::{
-    Canonical, InEnvironment, InferTy, ProjectionPredicate, ProjectionTy, TraitRef, Ty, TypeWalk,
+    Canonical, InEnvironment, InferTy, ProjectionPredicate, ProjectionTy, Substs, TraitRef, Ty,
+    TypeWalk,
 };
 
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
@@ -74,12 +75,9 @@ where
     }
 
     fn do_canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> TraitRef {
-        let substs = trait_ref
-            .substs
-            .iter()
-            .map(|ty| self.do_canonicalize_ty(ty.clone()))
-            .collect::<Vec<_>>();
-        TraitRef { trait_: trait_ref.trait_, substs: substs.into() }
+        let substs =
+            trait_ref.substs.iter().map(|ty| self.do_canonicalize_ty(ty.clone())).collect();
+        TraitRef { trait_: trait_ref.trait_, substs: Substs(substs) }
     }
 
     fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
@@ -90,12 +88,9 @@ where
     }
 
     fn do_canonicalize_projection_ty(&mut self, projection_ty: ProjectionTy) -> ProjectionTy {
-        let params = projection_ty
-            .parameters
-            .iter()
-            .map(|ty| self.do_canonicalize_ty(ty.clone()))
-            .collect::<Vec<_>>();
-        ProjectionTy { associated_ty: projection_ty.associated_ty, parameters: params.into() }
+        let params =
+            projection_ty.parameters.iter().map(|ty| self.do_canonicalize_ty(ty.clone())).collect();
+        ProjectionTy { associated_ty: projection_ty.associated_ty, parameters: Substs(params) }
     }
 
     fn do_canonicalize_projection_predicate(
@@ -153,8 +148,7 @@ impl<T> Canonicalized<T> {
         solution: Canonical<Vec<Ty>>,
     ) {
         // the solution may contain new variables, which we need to convert to new inference vars
-        let new_vars =
-            (0..solution.num_vars).map(|_| ctx.new_type_var()).collect::<Vec<_>>().into();
+        let new_vars = Substs((0..solution.num_vars).map(|_| ctx.new_type_var()).collect());
         for (i, ty) in solution.value.into_iter().enumerate() {
             let var = self.free_vars[i];
             ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index dd503d771..4b67c82e7 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -239,14 +239,10 @@ impl Ty {
         let traits = traits_from_env.flat_map(|t| t.all_super_traits(db));
         for t in traits {
             if let Some(associated_ty) = t.associated_type_by_name(db, &segment.name) {
-                let generics = t.generic_params(db);
-                let mut substs = Vec::new();
-                substs.push(self_ty.clone());
-                substs.extend(
-                    iter::repeat(Ty::Unknown).take(generics.count_params_including_parent() - 1),
-                );
+                let substs =
+                    Substs::build_for_def(db, t).push(self_ty.clone()).fill_with_unknown().build();
                 // FIXME handle type parameters on the segment
-                return Ty::Projection(ProjectionTy { associated_ty, parameters: substs.into() });
+                return Ty::Projection(ProjectionTy { associated_ty, parameters: substs });
             }
         }
         Ty::Unknown
@@ -766,6 +762,16 @@ pub enum CallableDef {
 }
 impl_froms!(CallableDef: Function, Struct, EnumVariant);
 
+impl CallableDef {
+    pub fn krate(self, db: &impl HirDatabase) -> Option<crate::Crate> {
+        match self {
+            CallableDef::Function(f) => f.krate(db),
+            CallableDef::Struct(s) => s.krate(db),
+            CallableDef::EnumVariant(e) => e.parent_enum(db).krate(db),
+        }
+    }
+}
+
 impl From<CallableDef> for GenericDef {
     fn from(def: CallableDef) -> GenericDef {
         match def {
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index 4b71b376f..ad2ab560d 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -10,7 +10,6 @@ use rustc_hash::FxHashMap;
 use super::{autoderef, lower, Canonical, InEnvironment, TraitEnvironment, TraitRef};
 use crate::{
     db::HirDatabase,
-    generics::HasGenericParams,
     impl_block::{ImplBlock, ImplId},
     nameres::CrateModuleId,
     resolve::Resolver,
@@ -331,20 +330,13 @@ fn generic_implements_goal(
     trait_: Trait,
     self_ty: Canonical<Ty>,
 ) -> Canonical<InEnvironment<super::Obligation>> {
-    let mut substs = Vec::new();
-    let generics = trait_.generic_params(db);
     let num_vars = self_ty.num_vars;
-    substs.push(self_ty.value);
-    substs.extend(
-        generics
-            .params_including_parent()
-            .into_iter()
-            .skip(1)
-            .enumerate()
-            .map(|(i, _p)| Ty::Bound((i + num_vars) as u32)),
-    );
+    let substs = super::Substs::build_for_def(db, trait_)
+        .push(self_ty.value)
+        .fill_with_bound_vars(num_vars as u32)
+        .build();
     let num_vars = substs.len() - 1 + self_ty.num_vars;
-    let trait_ref = TraitRef { trait_, substs: substs.into() };
+    let trait_ref = TraitRef { trait_, substs };
     let obligation = super::Obligation::Trait(trait_ref);
     Canonical { num_vars, value: InEnvironment::new(env, obligation) }
 }
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index bd2b07755..4df39c191 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -3354,7 +3354,6 @@ fn test() { S2.into()<|>; }
 
 #[test]
 fn method_resolution_encountering_fn_type() {
-    covers!(trait_resolution_on_fn_type);
     type_at(
         r#"
 //- /main.rs
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 538b4d3ec..2642a54bf 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -10,17 +10,13 @@ use chalk_ir::{
 use chalk_rust_ir::{AssociatedTyDatum, ImplDatum, StructDatum, TraitDatum};
 
 use ra_db::salsa::{InternId, InternKey};
-use test_utils::tested_by;
 
 use super::{Canonical, ChalkContext, Impl, Obligation};
 use crate::{
     db::HirDatabase,
     generics::GenericDef,
     ty::display::HirDisplay,
-    ty::{
-        ApplicationTy, CallableDef, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
-        TypeWalk,
-    },
+    ty::{ApplicationTy, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk},
     AssocItem, Crate, HasGenericParams, ImplBlock, Trait, TypeAlias,
 };
 
@@ -124,14 +120,15 @@ impl ToChalk for Substs {
     }
 
     fn from_chalk(db: &impl HirDatabase, parameters: Vec<chalk_ir::Parameter>) -> Substs {
-        parameters
+        let tys = parameters
             .into_iter()
             .map(|p| match p {
                 chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
                 chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
             })
             .collect::<Vec<_>>()
-            .into()
+            .into();
+        Substs(tys)
     }
 }
 
@@ -539,60 +536,18 @@ pub(crate) fn struct_datum_query(
     struct_id: chalk_ir::StructId,
 ) -> Arc<StructDatum> {
     debug!("struct_datum {:?}", struct_id);
-    let type_ctor = from_chalk(db, struct_id);
+    let type_ctor: TypeCtor = from_chalk(db, struct_id);
     debug!("struct {:?} = {:?}", struct_id, type_ctor);
-    // FIXME might be nicer if we can create a fake GenericParams for the TypeCtor
-    // FIXME extract this to a method on Ty
-    let (num_params, where_clauses, upstream) = match type_ctor {
-        TypeCtor::Bool
-        | TypeCtor::Char
-        | TypeCtor::Int(_)
-        | TypeCtor::Float(_)
-        | TypeCtor::Never
-        | TypeCtor::Str => (0, vec![], true),
-        TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => {
-            (1, vec![], true)
-        }
-        TypeCtor::FnPtr { num_args } => (num_args as usize + 1, vec![], true),
-        TypeCtor::Tuple { cardinality } => (cardinality as usize, vec![], true),
-        TypeCtor::FnDef(callable) => {
-            tested_by!(trait_resolution_on_fn_type);
-            let upstream = match callable {
-                CallableDef::Function(f) => f.module(db).krate(db),
-                CallableDef::Struct(s) => s.module(db).krate(db),
-                CallableDef::EnumVariant(v) => v.parent_enum(db).module(db).krate(db),
-            } != Some(krate);
-            let generic_def: GenericDef = callable.into();
+    let num_params = type_ctor.num_ty_params(db);
+    let upstream = type_ctor.krate(db) != Some(krate);
+    let where_clauses = type_ctor
+        .as_generic_def()
+        .map(|generic_def| {
             let generic_params = generic_def.generic_params(db);
             let bound_vars = Substs::bound_vars(&generic_params);
-            let where_clauses = convert_where_clauses(db, generic_def, &bound_vars);
-            (generic_params.count_params_including_parent(), where_clauses, upstream)
-        }
-        TypeCtor::Adt(adt) => {
-            let generic_params = adt.generic_params(db);
-            let bound_vars = Substs::bound_vars(&generic_params);
-            let where_clauses = convert_where_clauses(db, adt.into(), &bound_vars);
-            (
-                generic_params.count_params_including_parent(),
-                where_clauses,
-                adt.krate(db) != Some(krate),
-            )
-        }
-        TypeCtor::AssociatedType(type_alias) => {
-            let generic_params = type_alias.generic_params(db);
-            let bound_vars = Substs::bound_vars(&generic_params);
-            let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars);
-            (
-                generic_params.count_params_including_parent(),
-                where_clauses,
-                type_alias.krate(db) != Some(krate),
-            )
-        }
-        TypeCtor::Closure { def, .. } => {
-            let upstream = def.krate(db) != Some(krate);
-            (1, vec![], upstream)
-        }
-    };
+            convert_where_clauses(db, generic_def, &bound_vars)
+        })
+        .unwrap_or_else(Vec::new);
     let flags = chalk_rust_ir::StructFlags {
         upstream,
         // FIXME set fundamental flag correctly
@@ -729,17 +684,20 @@ fn closure_fn_trait_impl_datum(
 
     let arg_ty = Ty::apply(
         TypeCtor::Tuple { cardinality: num_args },
-        (0..num_args).map(|i| Ty::Bound(i.into())).collect::<Vec<_>>().into(),
+        Substs::builder(num_args as usize).fill_with_bound_vars(0).build(),
     );
     let output_ty = Ty::Bound(num_args.into());
     let sig_ty = Ty::apply(
         TypeCtor::FnPtr { num_args },
-        (0..num_args + 1).map(|i| Ty::Bound(i.into())).collect::<Vec<_>>().into(),
+        Substs::builder(num_args as usize + 1).fill_with_bound_vars(0).build(),
     );
 
     let self_ty = Ty::apply_one(TypeCtor::Closure { def: data.def, expr: data.expr }, sig_ty);
 
-    let trait_ref = TraitRef { trait_, substs: vec![self_ty, arg_ty].into() };
+    let trait_ref = TraitRef {
+        trait_,
+        substs: Substs::build_for_def(db, trait_).push(self_ty).push(arg_ty).build(),
+    };
 
     let output_ty_id = fn_once_trait.associated_type_by_name(db, &crate::name::OUTPUT_TYPE)?;
 
diff --git a/crates/ra_ide_api/src/line_index.rs b/crates/ra_ide_api/src/line_index.rs
index 71de8a928..5fedad696 100644
--- a/crates/ra_ide_api/src/line_index.rs
+++ b/crates/ra_ide_api/src/line_index.rs
@@ -278,5 +278,4 @@ const C: char = \"メ メ\";
 
         assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15));
     }
-
 }
diff --git a/crates/ra_ide_api/src/runnables.rs b/crates/ra_ide_api/src/runnables.rs
index 095ca56c4..8cf58fe79 100644
--- a/crates/ra_ide_api/src/runnables.rs
+++ b/crates/ra_ide_api/src/runnables.rs
@@ -229,5 +229,4 @@ mod tests {
         let runnables = analysis.runnables(pos.file_id).unwrap();
         assert!(runnables.is_empty())
     }
-
 }
diff --git a/crates/ra_lsp_server/src/markdown.rs b/crates/ra_lsp_server/src/markdown.rs
index c1eb0236a..3659edf8e 100644
--- a/crates/ra_lsp_server/src/markdown.rs
+++ b/crates/ra_lsp_server/src/markdown.rs
@@ -70,5 +70,4 @@ let a = 1;
             "```rust\nfn main(){}\n```\nSome comment.\n```rust\nlet a = 1;\n```"
         );
     }
-
 }
diff --git a/crates/ra_parser/src/grammar.rs b/crates/ra_parser/src/grammar.rs
index e2355aff9..6e9e212b7 100644
--- a/crates/ra_parser/src/grammar.rs
+++ b/crates/ra_parser/src/grammar.rs
@@ -135,7 +135,6 @@ pub(crate) mod fragments {
 
         m.complete(p, MACRO_STMTS);
     }
-
 }
 
 pub(crate) fn reparser(
diff --git a/crates/ra_syntax/Cargo.toml b/crates/ra_syntax/Cargo.toml
index 724c38e17..9bc85404a 100644
--- a/crates/ra_syntax/Cargo.toml
+++ b/crates/ra_syntax/Cargo.toml
@@ -12,6 +12,8 @@ itertools = "0.8.0"
 rowan = "0.6.1"
 rustc_lexer = "0.1.0"
 rustc-hash = "1.0.1"
+arrayvec = "0.4.10"
+once_cell = "1.2.0"
 
 # ideally, `serde` should be enabled by `ra_lsp_server`, but we enable it here
 # to reduce number of compilations
diff --git a/crates/ra_syntax/src/ast.rs b/crates/ra_syntax/src/ast.rs
index f464d6534..fdffd8cb1 100644
--- a/crates/ra_syntax/src/ast.rs
+++ b/crates/ra_syntax/src/ast.rs
@@ -5,6 +5,7 @@ mod traits;
 mod tokens;
 mod extensions;
 mod expr_extensions;
+mod edit;
 pub mod make;
 
 use std::marker::PhantomData;
diff --git a/crates/ra_syntax/src/ast/edit.rs b/crates/ra_syntax/src/ast/edit.rs
new file mode 100644
index 000000000..c65899812
--- /dev/null
+++ b/crates/ra_syntax/src/ast/edit.rs
@@ -0,0 +1,52 @@
+//! This module contains functions for editing syntax trees. As the trees are
+//! immutable, all function here return a fresh copy of the tree, instead of
+//! doing an in-place modification.
+
+use arrayvec::ArrayVec;
+use std::ops::RangeInclusive;
+
+use crate::{
+    algo,
+    ast::{self, make, AstNode},
+    InsertPosition, SyntaxElement,
+};
+
+impl ast::FnDef {
+    #[must_use]
+    pub fn with_body(&self, body: ast::Block) -> ast::FnDef {
+        let mut to_insert: ArrayVec<[SyntaxElement; 2]> = ArrayVec::new();
+        let old_body_or_semi: SyntaxElement = if let Some(old_body) = self.body() {
+            old_body.syntax().clone().into()
+        } else if let Some(semi) = self.semicolon_token() {
+            to_insert.push(make::tokens::single_space().into());
+            semi.into()
+        } else {
+            to_insert.push(make::tokens::single_space().into());
+            to_insert.push(body.syntax().clone().into());
+            return insert_children(self, InsertPosition::Last, to_insert.into_iter());
+        };
+        to_insert.push(body.syntax().clone().into());
+        let replace_range = RangeInclusive::new(old_body_or_semi.clone(), old_body_or_semi);
+        replace_children(self, replace_range, to_insert.into_iter())
+    }
+}
+
+#[must_use]
+fn insert_children<N: AstNode>(
+    parent: &N,
+    position: InsertPosition<SyntaxElement>,
+    mut to_insert: impl Iterator<Item = SyntaxElement>,
+) -> N {
+    let new_syntax = algo::insert_children(parent.syntax(), position, &mut to_insert);
+    N::cast(new_syntax).unwrap()
+}
+
+#[must_use]
+fn replace_children<N: AstNode>(
+    parent: &N,
+    to_replace: RangeInclusive<SyntaxElement>,
+    mut to_insert: impl Iterator<Item = SyntaxElement>,
+) -> N {
+    let new_syntax = algo::replace_children(parent.syntax(), to_replace, &mut to_insert);
+    N::cast(new_syntax).unwrap()
+}
diff --git a/crates/ra_syntax/src/ast/make.rs b/crates/ra_syntax/src/ast/make.rs
index c06c62b3b..287a40bee 100644
--- a/crates/ra_syntax/src/ast/make.rs
+++ b/crates/ra_syntax/src/ast/make.rs
@@ -133,3 +133,51 @@ fn ast_from_text<N: AstNode>(text: &str) -> N {
     let res = parse.tree().syntax().descendants().find_map(N::cast).unwrap();
     res
 }
+
+pub mod tokens {
+    use crate::{AstNode, Parse, SourceFile, SyntaxKind::*, SyntaxToken, T};
+    use once_cell::sync::Lazy;
+
+    static SOURCE_FILE: Lazy<Parse<SourceFile>> = Lazy::new(|| SourceFile::parse(",\n; ;"));
+
+    pub fn comma() -> SyntaxToken {
+        SOURCE_FILE
+            .tree()
+            .syntax()
+            .descendants_with_tokens()
+            .filter_map(|it| it.into_token())
+            .find(|it| it.kind() == T![,])
+            .unwrap()
+    }
+
+    pub fn single_space() -> SyntaxToken {
+        SOURCE_FILE
+            .tree()
+            .syntax()
+            .descendants_with_tokens()
+            .filter_map(|it| it.into_token())
+            .find(|it| it.kind() == WHITESPACE && it.text().as_str() == " ")
+            .unwrap()
+    }
+
+    pub fn single_newline() -> SyntaxToken {
+        SOURCE_FILE
+            .tree()
+            .syntax()
+            .descendants_with_tokens()
+            .filter_map(|it| it.into_token())
+            .find(|it| it.kind() == WHITESPACE && it.text().as_str() == "\n")
+            .unwrap()
+    }
+
+    pub struct WsBuilder(SourceFile);
+
+    impl WsBuilder {
+        pub fn new(text: &str) -> WsBuilder {
+            WsBuilder(SourceFile::parse(text).ok().unwrap())
+        }
+        pub fn ws(&self) -> SyntaxToken {
+            self.0.syntax().first_child_or_token().unwrap().into_token().unwrap()
+        }
+    }
+}