9 files changed, 190 insertions, 21 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 03b5794fa..42b8ce7c2 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1079,6 +1079,7 @@ dependencies = [
  "flexi_logger 0.11.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "insta 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "join_to_string 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "lalrpop-intern 0.15.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "once_cell 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "parking_lot 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
diff --git a/crates/ra_hir/Cargo.toml b/crates/ra_hir/Cargo.toml
index 12d849f37..aaace85e5 100644
--- a/crates/ra_hir/Cargo.toml
+++ b/crates/ra_hir/Cargo.toml
@@ -25,6 +25,7 @@ ra_prof = { path = "../ra_prof" }
 chalk-solve = { git = "https://github.com/flodiebold/chalk.git", branch = "fuel" }
 chalk-rust-ir = { git = "https://github.com/flodiebold/chalk.git", branch = "fuel" }
 chalk-ir = { git = "https://github.com/flodiebold/chalk.git", branch = "fuel" }
+lalrpop-intern = "0.15.1"
 
 [dev-dependencies]
 flexi_logger = "0.11.0"
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 830aea1f3..4fbb1fc8f 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -779,6 +779,19 @@ impl Trait {
         self.trait_data(db).items().to_vec()
     }
 
+    pub fn associated_type_by_name(self, db: &impl DefDatabase, name: Name) -> Option<TypeAlias> {
+        let trait_data = self.trait_data(db);
+        trait_data
+            .items()
+            .iter()
+            .filter_map(|item| match item {
+                TraitItem::TypeAlias(t) => Some(*t),
+                _ => None,
+            })
+            .filter(|t| t.name(db) == name)
+            .next()
+    }
+
     pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
         db.trait_data(self)
     }
@@ -831,8 +844,12 @@ impl TypeAlias {
         }
     }
 
-    pub fn type_ref(self, db: &impl DefDatabase) -> Arc<TypeRef> {
-        db.type_alias_ref(self)
+    pub fn type_ref(self, db: &impl DefDatabase) -> Option<TypeRef> {
+        db.type_alias_data(self).type_ref.clone()
+    }
+
+    pub fn name(self, db: &impl DefDatabase) -> Name {
+        db.type_alias_data(self).name.clone()
     }
 
     /// Builds a resolver for the type references in this type alias.
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index d2d6f95b7..651f0d4ca 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -16,9 +16,8 @@ use crate::{
     adt::{StructData, EnumData},
     impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock},
     generics::{GenericParams, GenericDef},
-    type_ref::TypeRef,
     traits::TraitData,
-    lang_item::{LangItems, LangItemTarget},
+    lang_item::{LangItems, LangItemTarget}, type_alias::TypeAliasData,
 };
 
 // This database has access to source code, so queries here are not really
@@ -113,8 +112,8 @@ pub trait DefDatabase: SourceDatabase {
     #[salsa::invoke(crate::FnSignature::fn_signature_query)]
     fn fn_signature(&self, func: Function) -> Arc<FnSignature>;
 
-    #[salsa::invoke(crate::type_alias::type_alias_ref_query)]
-    fn type_alias_ref(&self, typ: TypeAlias) -> Arc<TypeRef>;
+    #[salsa::invoke(crate::type_alias::type_alias_data_query)]
+    fn type_alias_data(&self, typ: TypeAlias) -> Arc<TypeAliasData>;
 
     #[salsa::invoke(crate::ConstSignature::const_signature_query)]
     fn const_signature(&self, konst: Const) -> Arc<ConstSignature>;
@@ -185,6 +184,13 @@ pub trait HirDatabase: DefDatabase + AstDatabase {
         krate: Crate,
         goal: crate::ty::Canonical<crate::ty::TraitRef>,
     ) -> Option<crate::ty::traits::Solution>;
+
+    #[salsa::invoke(crate::ty::traits::normalize)]
+    fn normalize(
+        &self,
+        krate: Crate,
+        goal: crate::ty::Canonical<crate::ty::traits::ProjectionPredicate>,
+    ) -> Option<crate::ty::traits::Solution>;
 }
 
 #[test]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 4a37e0268..d9a50b230 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -16,7 +16,7 @@ use std::sync::Arc;
 use std::ops::Deref;
 use std::{fmt, mem};
 
-use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams};
+use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams, TypeAlias};
 use display::{HirDisplay, HirFormatter};
 
 pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig, generic_predicates, generic_defaults};
@@ -100,6 +100,15 @@ pub struct ApplicationTy {
     pub parameters: Substs,
 }
 
+/// A "projection" type corresponds to an (unnormalized)
+/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
+/// trait and all its parameters are fully known.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct ProjectionTy {
+    pub associated_ty: TypeAlias,
+    pub parameters: Substs,
+}
+
 /// A type.
 ///
 /// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 26c213a41..300616a53 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -460,7 +460,7 @@ fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty {
     let resolver = t.resolver(db);
     let type_ref = t.type_ref(db);
     let substs = Substs::identity(&generics);
-    let inner = Ty::from_hir(db, &resolver, &type_ref);
+    let inner = Ty::from_hir(db, &resolver, &type_ref.unwrap_or(TypeRef::Error));
     inner.subst(&substs)
 }
 
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index fda7f9c04..f3e488403 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -8,7 +8,7 @@ use chalk_ir::cast::Cast;
 use ra_prof::profile;
 
 use crate::{Crate, Trait, db::HirDatabase, ImplBlock};
-use super::{TraitRef, Ty, Canonical};
+use super::{TraitRef, Ty, Canonical, ProjectionTy};
 
 use self::chalk::{ToChalk, from_chalk};
 
@@ -75,6 +75,13 @@ pub enum Obligation {
     /// Prove that a certain type implements a trait (the type is the `Self` type
     /// parameter to the `TraitRef`).
     Trait(TraitRef),
+    // Projection(ProjectionPredicate),
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct ProjectionPredicate {
+    projection_ty: ProjectionTy,
+    ty: Ty,
 }
 
 /// Check using Chalk whether trait is implemented for given parameters including `Self` type.
@@ -98,6 +105,30 @@ pub(crate) fn implements_query(
     solution.map(|solution| solution_from_chalk(db, solution))
 }
 
+pub(crate) fn normalize(
+    db: &impl HirDatabase,
+    krate: Crate,
+    projection: Canonical<ProjectionPredicate>,
+) -> Option<Solution> {
+    let goal: chalk_ir::Goal = chalk_ir::Normalize {
+        projection: projection.value.projection_ty.to_chalk(db),
+        ty: projection.value.ty.to_chalk(db),
+    }
+    .cast();
+    debug!("goal: {:?}", goal);
+    // FIXME unify with `implements`
+    let env = chalk_ir::Environment::new();
+    let in_env = chalk_ir::InEnvironment::new(&env, goal);
+    let parameter = chalk_ir::ParameterKind::Ty(chalk_ir::UniverseIndex::ROOT);
+    let canonical =
+        chalk_ir::Canonical { value: in_env, binders: vec![parameter; projection.num_vars] };
+    // We currently don't deal with universes (I think / hope they're not yet
+    // relevant for our use cases?)
+    let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
+    let solution = solve(db, krate, &u_canonical);
+    solution.map(|solution| solution_from_chalk(db, solution))
+}
+
 fn solution_from_chalk(db: &impl HirDatabase, solution: chalk_solve::Solution) -> Solution {
     let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution>| {
         let value = subst
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 1e4806db0..1e1b6f406 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -3,7 +3,7 @@ use std::sync::Arc;
 
 use log::debug;
 
-use chalk_ir::{TypeId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName};
+use chalk_ir::{TypeId, ImplId, TypeKindId, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName};
 use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum};
 
 use test_utils::tested_by;
@@ -12,9 +12,9 @@ use ra_db::salsa::{InternId, InternKey};
 use crate::{
     Trait, HasGenericParams, ImplBlock,
     db::HirDatabase,
-    ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate, CallableDef},
+    ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate, CallableDef, ProjectionTy},
     ty::display::HirDisplay,
-    generics::GenericDef,
+    generics::GenericDef, TypeAlias, ImplItem,
 };
 use super::ChalkContext;
 
@@ -156,6 +156,18 @@ impl ToChalk for ImplBlock {
     }
 }
 
+impl ToChalk for TypeAlias {
+    type Chalk = chalk_ir::TypeId;
+
+    fn to_chalk(self, _db: &impl HirDatabase) -> chalk_ir::TypeId {
+        self.id.into()
+    }
+
+    fn from_chalk(_db: &impl HirDatabase, impl_id: chalk_ir::TypeId) -> TypeAlias {
+        TypeAlias { id: impl_id.into() }
+    }
+}
+
 impl ToChalk for GenericPredicate {
     type Chalk = chalk_ir::QuantifiedWhereClause;
 
@@ -183,6 +195,24 @@ impl ToChalk for GenericPredicate {
     }
 }
 
+impl ToChalk for ProjectionTy {
+    type Chalk = chalk_ir::ProjectionTy;
+
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ProjectionTy {
+        chalk_ir::ProjectionTy {
+            associated_ty_id: self.associated_ty.to_chalk(db),
+            parameters: self.parameters.to_chalk(db),
+        }
+    }
+
+    fn from_chalk(db: &impl HirDatabase, projection_ty: chalk_ir::ProjectionTy) -> ProjectionTy {
+        ProjectionTy {
+            associated_ty: from_chalk(db, projection_ty.associated_ty_id),
+            parameters: from_chalk(db, projection_ty.parameters),
+        }
+    }
+}
+
 fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
     chalk_ir::Binders {
         value,
@@ -225,8 +255,28 @@ impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
 where
     DB: HirDatabase,
 {
-    fn associated_ty_data(&self, _ty: TypeId) -> Arc<AssociatedTyDatum> {
-        unimplemented!()
+    fn associated_ty_data(&self, id: TypeId) -> Arc<AssociatedTyDatum> {
+        debug!("associated_ty_data {:?}", id);
+        let type_alias: TypeAlias = from_chalk(self.db, id);
+        let trait_ = match type_alias.container(self.db) {
+            Some(crate::Container::Trait(t)) => t,
+            _ => panic!("associated type not in trait"),
+        };
+        let generic_params = type_alias.generic_params(self.db);
+        let parameter_kinds = generic_params
+            .params_including_parent()
+            .into_iter()
+            .map(|p| chalk_ir::ParameterKind::Ty(lalrpop_intern::intern(&p.name.to_string())))
+            .collect();
+        let datum = AssociatedTyDatum {
+            trait_id: trait_.to_chalk(self.db),
+            id,
+            name: lalrpop_intern::intern(&type_alias.name(self.db).to_string()),
+            parameter_kinds,
+            bounds: vec![],        // FIXME
+            where_clauses: vec![], // FIXME
+        };
+        Arc::new(datum)
     }
     fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> {
         debug!("trait_datum {:?}", trait_id);
@@ -260,7 +310,15 @@ where
             fundamental: false,
         };
         let where_clauses = convert_where_clauses(self.db, trait_.into(), &bound_vars);
-        let associated_ty_ids = Vec::new(); // FIXME add associated tys
+        let associated_ty_ids = trait_
+            .items(self.db)
+            .into_iter()
+            .filter_map(|trait_item| match trait_item {
+                crate::traits::TraitItem::TypeAlias(type_alias) => Some(type_alias),
+                _ => None,
+            })
+            .map(|type_alias| type_alias.to_chalk(self.db))
+            .collect();
         let trait_datum_bound =
             chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids };
         let trait_datum = TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()) };
@@ -359,7 +417,30 @@ where
             trait_ref.display(self.db),
             where_clauses
         );
+        let trait_ = trait_ref.trait_;
         let trait_ref = trait_ref.to_chalk(self.db);
+        let associated_ty_values = impl_block
+            .items(self.db)
+            .into_iter()
+            .filter_map(|item| match item {
+                ImplItem::TypeAlias(t) => Some(t),
+                _ => None,
+            })
+            .filter_map(|t| {
+                let assoc_ty = trait_.associated_type_by_name(self.db, t.name(self.db))?;
+                let ty = self.db.type_for_def(t.into(), crate::Namespace::Types).subst(&bound_vars);
+                debug!("ty = {}", ty.display(self.db));
+                Some(chalk_rust_ir::AssociatedTyValue {
+                    impl_id,
+                    associated_ty_id: assoc_ty.to_chalk(self.db),
+                    value: chalk_ir::Binders {
+                        value: chalk_rust_ir::AssociatedTyValueBound { ty: ty.to_chalk(self.db) },
+                        binders: vec![], // FIXME add generic params (generic associated types)
+                    },
+                })
+            })
+            .collect();
+
         let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
             trait_ref: if negative {
                 chalk_rust_ir::PolarizedTraitRef::Negative(trait_ref)
@@ -367,9 +448,10 @@ where
                 chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref)
             },
             where_clauses,
-            associated_ty_values: Vec::new(), // FIXME add associated type values
+            associated_ty_values,
             impl_type,
         };
+        debug!("impl_datum: {:?}", impl_datum_bound);
         let impl_datum = ImplDatum { binders: make_binders(impl_datum_bound, bound_vars.len()) };
         Arc::new(impl_datum)
     }
@@ -405,7 +487,7 @@ where
     }
     fn split_projection<'p>(
         &self,
-        projection: &'p ProjectionTy,
+        projection: &'p chalk_ir::ProjectionTy,
     ) -> (Arc<AssociatedTyDatum>, &'p [Parameter], &'p [Parameter]) {
         debug!("split_projection {:?}", projection);
         unimplemented!()
@@ -440,6 +522,18 @@ impl From<crate::ids::TraitId> for chalk_ir::TraitId {
     }
 }
 
+impl From<chalk_ir::TypeId> for crate::ids::TypeAliasId {
+    fn from(type_id: chalk_ir::TypeId) -> Self {
+        id_from_chalk(type_id.0)
+    }
+}
+
+impl From<crate::ids::TypeAliasId> for chalk_ir::TypeId {
+    fn from(type_id: crate::ids::TypeAliasId) -> Self {
+        chalk_ir::TypeId(id_to_chalk(type_id))
+    }
+}
+
 impl From<chalk_ir::StructId> for crate::ids::TypeCtorId {
     fn from(struct_id: chalk_ir::StructId) -> Self {
         id_from_chalk(struct_id.0)
diff --git a/crates/ra_hir/src/type_alias.rs b/crates/ra_hir/src/type_alias.rs
index 87b9caa8a..eada37274 100644
--- a/crates/ra_hir/src/type_alias.rs
+++ b/crates/ra_hir/src/type_alias.rs
@@ -2,12 +2,22 @@
 
 use std::sync::Arc;
 
-use crate::{TypeAlias, DefDatabase, AstDatabase, HasSource, type_ref::TypeRef};
+use ra_syntax::ast::NameOwner;
 
-pub(crate) fn type_alias_ref_query(
+use crate::{TypeAlias, db::{DefDatabase, AstDatabase}, type_ref::TypeRef, name::{Name, AsName}, HasSource};
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TypeAliasData {
+    pub(crate) name: Name,
+    pub(crate) type_ref: Option<TypeRef>,
+}
+
+pub(crate) fn type_alias_data_query(
     db: &(impl DefDatabase + AstDatabase),
     typ: TypeAlias,
-) -> Arc<TypeRef> {
+) -> Arc<TypeAliasData> {
     let node = typ.source(db).ast;
-    Arc::new(TypeRef::from_ast_opt(node.type_ref()))
+    let name = node.name().map_or_else(Name::missing, |n| n.as_name());
+    let type_ref = node.type_ref().map(TypeRef::from_ast);
+    Arc::new(TypeAliasData { name, type_ref })
 }