6 files changed, 289 insertions, 74 deletions

diff --git a/crates/ra_hir_ty/src/_match.rs b/crates/ra_hir_ty/src/_match.rs
index c482cf619..a64be9848 100644
--- a/crates/ra_hir_ty/src/_match.rs
+++ b/crates/ra_hir_ty/src/_match.rs
@@ -289,7 +289,7 @@ impl PatStack {
         Self::from_slice(&self.0[1..])
     }
 
-    fn replace_head_with(&self, pat_ids: &[PatId]) -> PatStack {
+    fn replace_head_with<T: Into<PatIdOrWild> + Copy>(&self, pat_ids: &[T]) -> PatStack {
         let mut patterns: PatStackInner = smallvec![];
         for pat in pat_ids {
             patterns.push((*pat).into());
@@ -320,12 +320,14 @@ impl PatStack {
         constructor: &Constructor,
     ) -> MatchCheckResult<Option<PatStack>> {
         let result = match (self.head().as_pat(cx), constructor) {
-            (Pat::Tuple(ref pat_ids), Constructor::Tuple { arity }) => {
-                debug_assert_eq!(
-                    pat_ids.len(),
-                    *arity,
-                    "we type check before calling this code, so we should never hit this case",
-                );
+            (Pat::Tuple { args: ref pat_ids, ellipsis }, Constructor::Tuple { arity: _ }) => {
+                if ellipsis.is_some() {
+                    // If there are ellipsis here, we should add the correct number of
+                    // Pat::Wild patterns to `pat_ids`. We should be able to use the
+                    // constructors arity for this, but at the time of writing we aren't
+                    // correctly calculating this arity when ellipsis are present.
+                    return Err(MatchCheckErr::NotImplemented);
+                }
 
                 Some(self.replace_head_with(pat_ids))
             }
@@ -351,19 +353,47 @@ impl PatStack {
                     Some(self.to_tail())
                 }
             }
-            (Pat::TupleStruct { args: ref pat_ids, .. }, Constructor::Enum(enum_constructor)) => {
+            (
+                Pat::TupleStruct { args: ref pat_ids, ellipsis, .. },
+                Constructor::Enum(enum_constructor),
+            ) => {
                 let pat_id = self.head().as_id().expect("we know this isn't a wild");
                 if !enum_variant_matches(cx, pat_id, *enum_constructor) {
                     None
                 } else {
-                    // If the enum variant matches, then we need to confirm
-                    // that the number of patterns aligns with the expected
-                    // number of patterns for that enum variant.
-                    if pat_ids.len() != constructor.arity(cx)? {
-                        return Err(MatchCheckErr::MalformedMatchArm);
+                    let constructor_arity = constructor.arity(cx)?;
+                    if let Some(ellipsis_position) = ellipsis {
+                        // If there are ellipsis in the pattern, the ellipsis must take the place
+                        // of at least one sub-pattern, so `pat_ids` should be smaller than the
+                        // constructor arity.
+                        if pat_ids.len() < constructor_arity {
+                            let mut new_patterns: Vec<PatIdOrWild> = vec![];
+
+                            for pat_id in &pat_ids[0..ellipsis_position] {
+                                new_patterns.push((*pat_id).into());
+                            }
+
+                            for _ in 0..(constructor_arity - pat_ids.len()) {
+                                new_patterns.push(PatIdOrWild::Wild);
+                            }
+
+                            for pat_id in &pat_ids[ellipsis_position..pat_ids.len()] {
+                                new_patterns.push((*pat_id).into());
+                            }
+
+                            Some(self.replace_head_with(&new_patterns))
+                        } else {
+                            return Err(MatchCheckErr::MalformedMatchArm);
+                        }
+                    } else {
+                        // If there is no ellipsis in the tuple pattern, the number
+                        // of patterns must equal the constructor arity.
+                        if pat_ids.len() == constructor_arity {
+                            Some(self.replace_head_with(pat_ids))
+                        } else {
+                            return Err(MatchCheckErr::MalformedMatchArm);
+                        }
                     }
-
-                    Some(self.replace_head_with(pat_ids))
                 }
             }
             (Pat::Or(_), _) => return Err(MatchCheckErr::NotImplemented),
@@ -644,7 +674,11 @@ impl Constructor {
 fn pat_constructor(cx: &MatchCheckCtx, pat: PatIdOrWild) -> MatchCheckResult<Option<Constructor>> {
     let res = match pat.as_pat(cx) {
         Pat::Wild => None,
-        Pat::Tuple(pats) => Some(Constructor::Tuple { arity: pats.len() }),
+        // FIXME somehow create the Tuple constructor with the proper arity. If there are
+        // ellipsis, the arity is not equal to the number of patterns.
+        Pat::Tuple { args: pats, ellipsis } if ellipsis.is_none() => {
+            Some(Constructor::Tuple { arity: pats.len() })
+        }
         Pat::Lit(lit_expr) => match cx.body.exprs[lit_expr] {
             Expr::Literal(Literal::Bool(val)) => Some(Constructor::Bool(val)),
             _ => return Err(MatchCheckErr::NotImplemented),
@@ -1507,6 +1541,67 @@ mod tests {
     }
 
     #[test]
+    fn enum_tuple_partial_ellipsis_2_no_diagnostic() {
+        let content = r"
+            enum Either {
+                A(bool, bool, bool, bool),
+                B,
+            }
+            fn test_fn() {
+                match Either::B {
+                    Either::A(true, .., true) => {},
+                    Either::A(true, .., false) => {},
+                    Either::A(.., true) => {},
+                    Either::A(.., false) => {},
+                    Either::B => {},
+                }
+            }
+        ";
+
+        check_no_diagnostic(content);
+    }
+
+    #[test]
+    fn enum_tuple_partial_ellipsis_missing_arm() {
+        let content = r"
+            enum Either {
+                A(bool, bool, bool, bool),
+                B,
+            }
+            fn test_fn() {
+                match Either::B {
+                    Either::A(true, .., true) => {},
+                    Either::A(true, .., false) => {},
+                    Either::A(false, .., false) => {},
+                    Either::B => {},
+                }
+            }
+        ";
+
+        check_diagnostic(content);
+    }
+
+    #[test]
+    fn enum_tuple_partial_ellipsis_2_missing_arm() {
+        let content = r"
+            enum Either {
+                A(bool, bool, bool, bool),
+                B,
+            }
+            fn test_fn() {
+                match Either::B {
+                    Either::A(true, .., true) => {},
+                    Either::A(true, .., false) => {},
+                    Either::A(.., true) => {},
+                    Either::B => {},
+                }
+            }
+        ";
+
+        check_diagnostic(content);
+    }
+
+    #[test]
     fn enum_tuple_ellipsis_no_diagnostic() {
         let content = r"
             enum Either {
@@ -1645,11 +1740,7 @@ mod false_negatives {
         ";
 
         // This is a false negative.
-        // The `..` pattern is currently lowered to a single `Pat::Wild`
-        // no matter how many fields the `..` pattern is covering. This
-        // causes the match arm in this test not to type check against
-        // the match expression, which causes this diagnostic not to
-        // fire.
+        // We don't currently handle tuple patterns with ellipsis.
         check_no_diagnostic(content);
     }
 
@@ -1664,32 +1755,7 @@ mod false_negatives {
         ";
 
         // This is a false negative.
-        // See comments on `tuple_of_bools_with_ellipsis_at_end_missing_arm`.
-        check_no_diagnostic(content);
-    }
-
-    #[test]
-    fn enum_tuple_partial_ellipsis_missing_arm() {
-        let content = r"
-            enum Either {
-                A(bool, bool, bool, bool),
-                B,
-            }
-            fn test_fn() {
-                match Either::B {
-                    Either::A(true, .., true) => {},
-                    Either::A(true, .., false) => {},
-                    Either::A(false, .., false) => {},
-                    Either::B => {},
-                }
-            }
-        ";
-
-        // This is a false negative.
-        // The `..` pattern is currently lowered to a single `Pat::Wild`
-        // no matter how many fields the `..` pattern is covering. This
-        // causes us to return a `MatchCheckErr::MalformedMatchArm` in
-        // `Pat::specialize_constructor`.
+        // We don't currently handle tuple patterns with ellipsis.
         check_no_diagnostic(content);
     }
 }
diff --git a/crates/ra_hir_ty/src/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs
index 078476f76..8ec4d4ace 100644
--- a/crates/ra_hir_ty/src/infer/pat.rs
+++ b/crates/ra_hir_ty/src/infer/pat.rs
@@ -85,7 +85,7 @@ impl<'a> InferenceContext<'a> {
         let body = Arc::clone(&self.body); // avoid borrow checker problem
 
         let is_non_ref_pat = match &body[pat] {
-            Pat::Tuple(..)
+            Pat::Tuple { .. }
             | Pat::Or(..)
             | Pat::TupleStruct { .. }
             | Pat::Record { .. }
@@ -116,7 +116,7 @@ impl<'a> InferenceContext<'a> {
         let expected = expected;
 
         let ty = match &body[pat] {
-            Pat::Tuple(ref args) => {
+            Pat::Tuple { ref args, .. } => {
                 let expectations = match expected.as_tuple() {
                     Some(parameters) => &*parameters.0,
                     _ => &[],
@@ -155,7 +155,7 @@ impl<'a> InferenceContext<'a> {
                 let subty = self.infer_pat(*pat, expectation, default_bm);
                 Ty::apply_one(TypeCtor::Ref(*mutability), subty)
             }
-            Pat::TupleStruct { path: p, args: subpats } => {
+            Pat::TupleStruct { path: p, args: subpats, .. } => {
                 self.infer_tuple_struct_pat(p.as_ref(), subpats, expected, default_bm, pat)
             }
             Pat::Record { path: p, args: fields, ellipsis: _ } => {
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index 6c7bbc448..cc1ac8e3e 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -8,6 +8,8 @@
 use std::iter;
 use std::sync::Arc;
 
+use smallvec::SmallVec;
+
 use hir_def::{
     adt::StructKind,
     builtin_type::BuiltinType,
@@ -360,13 +362,23 @@ impl Ty {
             },
             Some(TypeNs::GenericParam(param_id)) => {
                 let predicates = ctx.db.generic_predicates_for_param(param_id);
-                predicates
+                let mut traits_: Vec<_> = predicates
                     .iter()
                     .filter_map(|pred| match &pred.value {
                         GenericPredicate::Implemented(tr) => Some(tr.trait_),
                         _ => None,
                     })
-                    .collect()
+                    .collect();
+                // Handle `Self::Type` referring to own associated type in trait definitions
+                if let GenericDefId::TraitId(trait_id) = param_id.parent {
+                    let generics = generics(ctx.db.upcast(), trait_id.into());
+                    if generics.params.types[param_id.local_id].provenance
+                        == TypeParamProvenance::TraitSelf
+                    {
+                        traits_.push(trait_id);
+                    }
+                }
+                traits_
             }
             _ => return Ty::Unknown,
         };
@@ -596,21 +608,35 @@ fn assoc_type_bindings_from_type_bound<'a>(
         .into_iter()
         .flat_map(|segment| segment.args_and_bindings.into_iter())
         .flat_map(|args_and_bindings| args_and_bindings.bindings.iter())
-        .map(move |(name, type_ref)| {
+        .flat_map(move |binding| {
             let associated_ty = associated_type_by_name_including_super_traits(
                 ctx.db.upcast(),
                 trait_ref.trait_,
-                &name,
+                &binding.name,
             );
             let associated_ty = match associated_ty {
-                None => return GenericPredicate::Error,
+                None => return SmallVec::<[GenericPredicate; 1]>::new(),
                 Some(t) => t,
             };
             let projection_ty =
                 ProjectionTy { associated_ty, parameters: trait_ref.substs.clone() };
-            let ty = Ty::from_hir(ctx, type_ref);
-            let projection_predicate = ProjectionPredicate { projection_ty, ty };
-            GenericPredicate::Projection(projection_predicate)
+            let mut preds = SmallVec::with_capacity(
+                binding.type_ref.as_ref().map_or(0, |_| 1) + binding.bounds.len(),
+            );
+            if let Some(type_ref) = &binding.type_ref {
+                let ty = Ty::from_hir(ctx, type_ref);
+                let projection_predicate =
+                    ProjectionPredicate { projection_ty: projection_ty.clone(), ty };
+                preds.push(GenericPredicate::Projection(projection_predicate));
+            }
+            for bound in &binding.bounds {
+                preds.extend(GenericPredicate::from_type_bound(
+                    ctx,
+                    bound,
+                    Ty::Projection(projection_ty.clone()),
+                ));
+            }
+            preds
         })
 }
 
diff --git a/crates/ra_hir_ty/src/tests/regression.rs b/crates/ra_hir_ty/src/tests/regression.rs
index 3402e0cb5..d69115a2f 100644
--- a/crates/ra_hir_ty/src/tests/regression.rs
+++ b/crates/ra_hir_ty/src/tests/regression.rs
@@ -451,8 +451,7 @@ pub mod str {
 "#,
     );
 
-    // should be Option<char>, but currently not because of Chalk ambiguity problem
-    assert_eq!("(Option<{unknown}>, Option<{unknown}>)", super::type_at_pos(&db, pos));
+    assert_eq!("(Option<char>, Option<char>)", super::type_at_pos(&db, pos));
 }
 
 #[test]
diff --git a/crates/ra_hir_ty/src/tests/traits.rs b/crates/ra_hir_ty/src/tests/traits.rs
index 22ae6ca90..81c5e6299 100644
--- a/crates/ra_hir_ty/src/tests/traits.rs
+++ b/crates/ra_hir_ty/src/tests/traits.rs
@@ -1803,7 +1803,7 @@ fn test<T, U>() where T::Item: Trait2, T: Trait<U::Item>, U: Trait<()> {
 }
 
 #[test]
-fn unselected_projection_on_trait_self() {
+fn unselected_projection_on_impl_self() {
     assert_snapshot!(infer(
         r#"
 //- /main.rs
@@ -1844,6 +1844,30 @@ impl Trait for S2 {
 }
 
 #[test]
+fn unselected_projection_on_trait_self() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait {
+    type Item;
+
+    fn f(&self) -> Self::Item { loop {} }
+}
+
+struct S;
+impl Trait for S {
+    type Item = u32;
+}
+
+fn test() {
+    S.f()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "u32");
+}
+
+#[test]
 fn trait_impl_self_ty() {
     let t = type_at(
         r#"
@@ -1924,6 +1948,53 @@ fn test<T, U>() where T: Trait<U::Item>, U: Trait<T::Item> {
 }
 
 #[test]
+fn inline_assoc_type_bounds_1() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Iterator {
+    type Item;
+}
+trait OtherTrait<T> {
+    fn foo(&self) -> T;
+}
+
+// workaround for Chalk assoc type normalization problems
+pub struct S<T>;
+impl<T: Iterator> Iterator for S<T> {
+    type Item = <T as Iterator>::Item;
+}
+
+fn test<I: Iterator<Item: OtherTrait<u32>>>() {
+    let x: <S<I> as Iterator>::Item;
+    x.foo()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "u32");
+}
+
+#[test]
+fn inline_assoc_type_bounds_2() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Iterator {
+    type Item;
+}
+
+fn test<I: Iterator<Item: Iterator<Item = u32>>>() {
+    let x: <<I as Iterator>::Item as Iterator>::Item;
+    x<|>;
+}
+"#,
+    );
+    // assert_eq!(t, "u32");
+    // doesn't currently work, Chalk #234
+    assert_eq!(t, "{unknown}");
+}
+
+#[test]
 fn unify_impl_trait() {
     assert_snapshot!(
         infer_with_mismatches(r#"
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index e05fea843..f6994a1f6 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -32,6 +32,9 @@ impl chalk_ir::interner::Interner for Interner {
     type InternedGoal = Arc<GoalData<Self>>;
     type InternedGoals = Vec<Goal<Self>>;
     type InternedSubstitution = Vec<Parameter<Self>>;
+    type InternedProgramClause = chalk_ir::ProgramClauseData<Self>;
+    type InternedProgramClauses = Vec<chalk_ir::ProgramClause<Self>>;
+    type InternedQuantifiedWhereClauses = Vec<chalk_ir::QuantifiedWhereClause<Self>>;
     type Identifier = TypeAliasId;
     type DefId = InternId;
 
@@ -181,6 +184,48 @@ impl chalk_ir::interner::Interner for Interner {
     ) -> &'a [Parameter<Self>] {
         substitution
     }
+
+    fn intern_program_clause(
+        &self,
+        data: chalk_ir::ProgramClauseData<Self>,
+    ) -> chalk_ir::ProgramClauseData<Self> {
+        data
+    }
+
+    fn program_clause_data<'a>(
+        &self,
+        clause: &'a chalk_ir::ProgramClauseData<Self>,
+    ) -> &'a chalk_ir::ProgramClauseData<Self> {
+        clause
+    }
+
+    fn intern_program_clauses(
+        &self,
+        data: impl IntoIterator<Item = chalk_ir::ProgramClause<Self>>,
+    ) -> Vec<chalk_ir::ProgramClause<Self>> {
+        data.into_iter().collect()
+    }
+
+    fn program_clauses_data<'a>(
+        &self,
+        clauses: &'a Vec<chalk_ir::ProgramClause<Self>>,
+    ) -> &'a [chalk_ir::ProgramClause<Self>] {
+        clauses
+    }
+
+    fn intern_quantified_where_clauses(
+        &self,
+        data: impl IntoIterator<Item = chalk_ir::QuantifiedWhereClause<Self>>,
+    ) -> Self::InternedQuantifiedWhereClauses {
+        data.into_iter().collect()
+    }
+
+    fn quantified_where_clauses_data<'a>(
+        &self,
+        clauses: &'a Self::InternedQuantifiedWhereClauses,
+    ) -> &'a [chalk_ir::QuantifiedWhereClause<Self>] {
+        clauses
+    }
 }
 
 impl chalk_ir::interner::HasInterner for Interner {
@@ -238,12 +283,10 @@ impl ToChalk for Ty {
             Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx).intern(&Interner),
             Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
             Ty::Dyn(predicates) => {
-                let where_clauses = predicates
-                    .iter()
-                    .filter(|p| !p.is_error())
-                    .cloned()
-                    .map(|p| p.to_chalk(db))
-                    .collect();
+                let where_clauses = chalk_ir::QuantifiedWhereClauses::from(
+                    &Interner,
+                    predicates.iter().filter(|p| !p.is_error()).cloned().map(|p| p.to_chalk(db)),
+                );
                 let bounded_ty = chalk_ir::DynTy { bounds: make_binders(where_clauses, 1) };
                 chalk_ir::TyData::Dyn(bounded_ty).intern(&Interner)
             }
@@ -281,8 +324,12 @@ impl ToChalk for Ty {
             chalk_ir::TyData::InferenceVar(_iv) => Ty::Unknown,
             chalk_ir::TyData::Dyn(where_clauses) => {
                 assert_eq!(where_clauses.bounds.binders.len(), 1);
-                let predicates =
-                    where_clauses.bounds.value.into_iter().map(|c| from_chalk(db, c)).collect();
+                let predicates = where_clauses
+                    .bounds
+                    .skip_binders()
+                    .iter(&Interner)
+                    .map(|c| from_chalk(db, c.clone()))
+                    .collect();
                 Ty::Dyn(predicates)
             }
         }
@@ -426,7 +473,7 @@ impl ToChalk for GenericPredicate {
     ) -> GenericPredicate {
         // we don't produce any where clauses with binders and can't currently deal with them
         match where_clause
-            .value
+            .skip_binders()
             .shifted_out(&Interner)
             .expect("unexpected bound vars in where clause")
         {
@@ -521,7 +568,7 @@ impl ToChalk for Arc<super::TraitEnvironment> {
                 pred.clone().to_chalk(db).cast(&Interner);
             clauses.push(program_clause.into_from_env_clause(&Interner));
         }
-        chalk_ir::Environment::new().add_clauses(clauses)
+        chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses)
     }
 
     fn from_chalk(
@@ -603,10 +650,10 @@ impl ToChalk for builtin::BuiltinImplAssocTyValueData {
 }
 
 fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
-    chalk_ir::Binders {
+    chalk_ir::Binders::new(
+        std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(),
         value,
-        binders: std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(),
-    }
+    )
 }
 
 fn convert_where_clauses(
@@ -696,6 +743,12 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
     fn interner(&self) -> &Interner {
         &Interner
     }
+    fn well_known_trait_id(
+        &self,
+        _well_known_trait: chalk_rust_ir::WellKnownTrait,
+    ) -> chalk_ir::TraitId<Interner> {
+        unimplemented!()
+    }
 }
 
 pub(crate) fn associated_ty_data_query(