10 files changed, 227 insertions, 63 deletions

diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
index 9ce154593..222a36a9f 100644
--- a/crates/ra_hir_ty/src/db.rs
+++ b/crates/ra_hir_ty/src/db.rs
@@ -11,7 +11,7 @@ use ra_db::{salsa, CrateId};
 use crate::{
     method_resolution::CrateImplBlocks,
     traits::{AssocTyValue, Impl},
-    CallableDef, FnSig, GenericPredicate, ImplTy, InferenceResult, Substs, Ty, TyDefId, TypeCtor,
+    CallableDef, FnSig, GenericPredicate, InferenceResult, Substs, TraitRef, Ty, TyDefId, TypeCtor,
     ValueTyDefId,
 };
 
@@ -22,13 +22,18 @@ pub trait HirDatabase: DefDatabase {
     fn infer(&self, def: DefWithBodyId) -> Arc<InferenceResult>;
 
     #[salsa::invoke(crate::lower::ty_query)]
+    #[salsa::cycle(crate::lower::ty_recover)]
     fn ty(&self, def: TyDefId) -> Ty;
 
     #[salsa::invoke(crate::lower::value_ty_query)]
     fn value_ty(&self, def: ValueTyDefId) -> Ty;
 
-    #[salsa::invoke(crate::lower::impl_ty_query)]
-    fn impl_ty(&self, def: ImplId) -> ImplTy;
+    #[salsa::invoke(crate::lower::impl_self_ty_query)]
+    #[salsa::cycle(crate::lower::impl_self_ty_recover)]
+    fn impl_self_ty(&self, def: ImplId) -> Ty;
+
+    #[salsa::invoke(crate::lower::impl_trait_query)]
+    fn impl_trait(&self, def: ImplId) -> Option<TraitRef>;
 
     #[salsa::invoke(crate::lower::field_types_query)]
     fn field_types(&self, var: VariantId) -> Arc<ArenaMap<LocalStructFieldId, Ty>>;
@@ -37,6 +42,7 @@ pub trait HirDatabase: DefDatabase {
     fn callable_item_signature(&self, def: CallableDef) -> FnSig;
 
     #[salsa::invoke(crate::lower::generic_predicates_for_param_query)]
+    #[salsa::cycle(crate::lower::generic_predicates_for_param_recover)]
     fn generic_predicates_for_param(
         &self,
         def: GenericDefId,
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs
index f6283ab6d..fe259371f 100644
--- a/crates/ra_hir_ty/src/infer.rs
+++ b/crates/ra_hir_ty/src/infer.rs
@@ -577,6 +577,42 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
         Some(struct_.into())
     }
+
+    fn resolve_range_full(&self) -> Option<AdtId> {
+        let path = known::std_ops_range_full();
+        let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
+        Some(struct_.into())
+    }
+
+    fn resolve_range(&self) -> Option<AdtId> {
+        let path = known::std_ops_range();
+        let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
+        Some(struct_.into())
+    }
+
+    fn resolve_range_inclusive(&self) -> Option<AdtId> {
+        let path = known::std_ops_range_inclusive();
+        let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
+        Some(struct_.into())
+    }
+
+    fn resolve_range_from(&self) -> Option<AdtId> {
+        let path = known::std_ops_range_from();
+        let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
+        Some(struct_.into())
+    }
+
+    fn resolve_range_to(&self) -> Option<AdtId> {
+        let path = known::std_ops_range_to();
+        let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
+        Some(struct_.into())
+    }
+
+    fn resolve_range_to_inclusive(&self) -> Option<AdtId> {
+        let path = known::std_ops_range_to_inclusive();
+        let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
+        Some(struct_.into())
+    }
 }
 
 /// The ID of a type variable.
diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
index 719a0f395..064993d34 100644
--- a/crates/ra_hir_ty/src/infer/coerce.rs
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -8,7 +8,7 @@ use hir_def::{lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutabilit
 use rustc_hash::FxHashMap;
 use test_utils::tested_by;
 
-use crate::{autoderef, db::HirDatabase, ImplTy, Substs, Ty, TypeCtor, TypeWalk};
+use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk};
 
 use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue};
 
@@ -54,10 +54,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         impls
             .iter()
             .filter_map(|&impl_id| {
-                let trait_ref = match db.impl_ty(impl_id) {
-                    ImplTy::TraitRef(it) => it,
-                    ImplTy::Inherent(_) => return None,
-                };
+                let trait_ref = db.impl_trait(impl_id)?;
 
                 // `CoerseUnsized` has one generic parameter for the target type.
                 let cur_from_ty = trait_ref.substs.0.get(0)?;
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
index 2f9ca4bbb..4014f4732 100644
--- a/crates/ra_hir_ty/src/infer/expr.rs
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -12,6 +12,7 @@ use hir_def::{
     AdtId, ContainerId, Lookup, StructFieldId,
 };
 use hir_expand::name::{self, Name};
+use ra_syntax::ast::RangeOp;
 
 use crate::{
     autoderef, db::HirDatabase, method_resolution, op, traits::InEnvironment, utils::variant_data,
@@ -415,6 +416,44 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
                 _ => Ty::Unknown,
             },
+            Expr::Range { lhs, rhs, range_type } => {
+                let lhs_ty = lhs.map(|e| self.infer_expr(e, &Expectation::none()));
+                let rhs_expect = lhs_ty
+                    .as_ref()
+                    .map_or_else(Expectation::none, |ty| Expectation::has_type(ty.clone()));
+                let rhs_ty = rhs.map(|e| self.infer_expr(e, &rhs_expect));
+                match (range_type, lhs_ty, rhs_ty) {
+                    (RangeOp::Exclusive, None, None) => match self.resolve_range_full() {
+                        Some(adt) => Ty::simple(TypeCtor::Adt(adt)),
+                        None => Ty::Unknown,
+                    },
+                    (RangeOp::Exclusive, None, Some(ty)) => match self.resolve_range_to() {
+                        Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                        None => Ty::Unknown,
+                    },
+                    (RangeOp::Inclusive, None, Some(ty)) => {
+                        match self.resolve_range_to_inclusive() {
+                            Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                            None => Ty::Unknown,
+                        }
+                    }
+                    (RangeOp::Exclusive, Some(_), Some(ty)) => match self.resolve_range() {
+                        Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                        None => Ty::Unknown,
+                    },
+                    (RangeOp::Inclusive, Some(_), Some(ty)) => {
+                        match self.resolve_range_inclusive() {
+                            Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                            None => Ty::Unknown,
+                        }
+                    }
+                    (RangeOp::Exclusive, Some(ty), None) => match self.resolve_range_from() {
+                        Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                        None => Ty::Unknown,
+                    },
+                    (RangeOp::Inclusive, _, None) => Ty::Unknown,
+                }
+            }
             Expr::Index { base, index } => {
                 let _base_ty = self.infer_expr(*base, &Expectation::none());
                 let _index_ty = self.infer_expr(*index, &Expectation::none());
diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs
index 14be66836..bbf146418 100644
--- a/crates/ra_hir_ty/src/infer/path.rs
+++ b/crates/ra_hir_ty/src/infer/path.rs
@@ -244,7 +244,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 ContainerId::ImplId(it) => it,
                 _ => return None,
             };
-            let self_ty = self.db.impl_ty(impl_id).self_type().clone();
+            let self_ty = self.db.impl_self_ty(impl_id).clone();
             let self_ty_substs = self_ty.substs()?;
             let actual_substs = actual_def_ty.substs()?;
 
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index b45c8f82f..3c1f738df 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -486,21 +486,6 @@ impl TypeWalk for TraitRef {
     }
 }
 
-#[derive(Clone, PartialEq, Eq, Debug)]
-pub enum ImplTy {
-    Inherent(Ty),
-    TraitRef(TraitRef),
-}
-
-impl ImplTy {
-    pub(crate) fn self_type(&self) -> &Ty {
-        match self {
-            ImplTy::Inherent(it) => it,
-            ImplTy::TraitRef(tr) => &tr.substs[0],
-        }
-    }
-}
-
 /// Like `generics::WherePredicate`, but with resolved types: A condition on the
 /// parameters of a generic item.
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index 091c60f4f..32569ac66 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -27,8 +27,8 @@ use crate::{
         all_super_traits, associated_type_by_name_including_super_traits, make_mut_slice,
         variant_data,
     },
-    FnSig, GenericPredicate, ImplTy, ProjectionPredicate, ProjectionTy, Substs, TraitEnvironment,
-    TraitRef, Ty, TypeCtor, TypeWalk,
+    FnSig, GenericPredicate, ProjectionPredicate, ProjectionTy, Substs, TraitEnvironment, TraitRef,
+    Ty, TypeCtor, TypeWalk,
 };
 
 impl Ty {
@@ -179,7 +179,7 @@ impl Ty {
                 let name = resolved_segment.name.clone();
                 Ty::Param { idx, name }
             }
-            TypeNs::SelfType(impl_id) => db.impl_ty(impl_id).self_type().clone(),
+            TypeNs::SelfType(impl_id) => db.impl_self_ty(impl_id).clone(),
             TypeNs::AdtSelfType(adt) => db.ty(adt.into()),
 
             TypeNs::AdtId(it) => Ty::from_hir_path_inner(db, resolver, resolved_segment, it.into()),
@@ -532,6 +532,15 @@ pub(crate) fn generic_predicates_for_param_query(
         .collect()
 }
 
+pub(crate) fn generic_predicates_for_param_recover(
+    _db: &impl HirDatabase,
+    _cycle: &[String],
+    _def: &GenericDefId,
+    _param_idx: &u32,
+) -> Arc<[GenericPredicate]> {
+    Arc::new([])
+}
+
 impl TraitEnvironment {
     pub fn lower(db: &impl HirDatabase, resolver: &Resolver) -> Arc<TraitEnvironment> {
         let predicates = resolver
@@ -733,6 +742,11 @@ pub(crate) fn ty_query(db: &impl HirDatabase, def: TyDefId) -> Ty {
         TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
     }
 }
+
+pub(crate) fn ty_recover(_db: &impl HirDatabase, _cycle: &[String], _def: &TyDefId) -> Ty {
+    Ty::Unknown
+}
+
 pub(crate) fn value_ty_query(db: &impl HirDatabase, def: ValueTyDefId) -> Ty {
     match def {
         ValueTyDefId::FunctionId(it) => type_for_fn(db, it),
@@ -743,17 +757,24 @@ pub(crate) fn value_ty_query(db: &impl HirDatabase, def: ValueTyDefId) -> Ty {
     }
 }
 
-pub(crate) fn impl_ty_query(db: &impl HirDatabase, impl_id: ImplId) -> ImplTy {
+pub(crate) fn impl_self_ty_query(db: &impl HirDatabase, impl_id: ImplId) -> Ty {
     let impl_data = db.impl_data(impl_id);
     let resolver = impl_id.resolver(db);
-    let self_ty = Ty::from_hir(db, &resolver, &impl_data.target_type);
-    match impl_data.target_trait.as_ref() {
-        Some(trait_ref) => {
-            match TraitRef::from_hir(db, &resolver, trait_ref, Some(self_ty.clone())) {
-                Some(it) => ImplTy::TraitRef(it),
-                None => ImplTy::Inherent(self_ty),
-            }
-        }
-        None => ImplTy::Inherent(self_ty),
-    }
+    Ty::from_hir(db, &resolver, &impl_data.target_type)
+}
+
+pub(crate) fn impl_self_ty_recover(
+    _db: &impl HirDatabase,
+    _cycle: &[String],
+    _impl_id: &ImplId,
+) -> Ty {
+    Ty::Unknown
+}
+
+pub(crate) fn impl_trait_query(db: &impl HirDatabase, impl_id: ImplId) -> Option<TraitRef> {
+    let impl_data = db.impl_data(impl_id);
+    let resolver = impl_id.resolver(db);
+    let self_ty = db.impl_self_ty(impl_id);
+    let target_trait = impl_data.target_trait.as_ref()?;
+    TraitRef::from_hir(db, &resolver, target_trait, Some(self_ty.clone()))
 }
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index ee1936b0e..2bded3dbd 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -19,7 +19,7 @@ use crate::{
     db::HirDatabase,
     primitive::{FloatBitness, Uncertain},
     utils::all_super_traits,
-    Canonical, ImplTy, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor,
+    Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor,
 };
 
 /// This is used as a key for indexing impls.
@@ -58,11 +58,12 @@ impl CrateImplBlocks {
         let crate_def_map = db.crate_def_map(krate);
         for (_module_id, module_data) in crate_def_map.modules.iter() {
             for &impl_id in module_data.impls.iter() {
-                match db.impl_ty(impl_id) {
-                    ImplTy::TraitRef(tr) => {
+                match db.impl_trait(impl_id) {
+                    Some(tr) => {
                         res.impls_by_trait.entry(tr.trait_).or_default().push(impl_id);
                     }
-                    ImplTy::Inherent(self_ty) => {
+                    None => {
+                        let self_ty = db.impl_self_ty(impl_id);
                         if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty) {
                             res.impls.entry(self_ty_fp).or_default().push(impl_id);
                         }
diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs
index 3766ab981..a3cc5cf95 100644
--- a/crates/ra_hir_ty/src/tests.rs
+++ b/crates/ra_hir_ty/src/tests.rs
@@ -222,6 +222,56 @@ mod collections {
 }
 
 #[test]
+fn infer_ranges() {
+    let (db, pos) = TestDB::with_position(
+        r#"
+//- /main.rs crate:main deps:std
+fn test() {
+    let a = ..;
+    let b = 1..;
+    let c = ..2u32;
+    let d = 1..2usize;
+    let e = ..=10;
+    let f = 'a'..='z';
+
+    let t = (a, b, c, d, e, f);
+    t<|>;
+}
+
+//- /std.rs crate:std
+#[prelude_import] use prelude::*;
+mod prelude {}
+
+pub mod ops {
+    pub struct Range<Idx> {
+        pub start: Idx,
+        pub end: Idx,
+    }
+    pub struct RangeFrom<Idx> {
+        pub start: Idx,
+    }
+    struct RangeFull;
+    pub struct RangeInclusive<Idx> {
+        start: Idx,
+        end: Idx,
+        is_empty: u8,
+    }
+    pub struct RangeTo<Idx> {
+        pub end: Idx,
+    }
+    pub struct RangeToInclusive<Idx> {
+        pub end: Idx,
+    }
+}
+"#,
+    );
+    assert_eq!(
+        "(RangeFull, RangeFrom<i32>, RangeTo<u32>, Range<usize>, RangeToInclusive<i32>, RangeInclusive<char>)",
+        type_at_pos(&db, pos),
+    );
+}
+
+#[test]
 fn infer_while_let() {
     let (db, pos) = TestDB::with_position(
         r#"
@@ -2104,7 +2154,6 @@ fn test(x: Foo, y: Bar<&str>, z: Baz<i8, u8>) {
 }
 
 #[test]
-#[should_panic] // we currently can't handle this
 fn recursive_type_alias() {
     assert_snapshot!(
         infer(r#"
@@ -2113,7 +2162,10 @@ type Foo = Foo;
 type Bar = A<Bar>;
 fn test(x: Foo) {}
 "#),
-        @""
+        @r###"
+    [59; 60) 'x': {unknown}
+    [67; 69) '{}': ()
+    "###
     )
 }
 
@@ -4662,10 +4714,48 @@ fn test<T, U>() where T::Item: Trait2, T: Trait<U::Item>, U: Trait<()> {
 }
 
 #[test]
-// FIXME this is currently a Salsa panic; it would be nicer if it just returned
-// in Unknown, and we should be able to do that once Salsa allows us to handle
-// the cycle. But at least it doesn't overflow for now.
-#[should_panic]
+fn trait_impl_self_ty() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait<T> {
+   fn foo(&self);
+}
+
+struct S;
+
+impl Trait<Self> for S {}
+
+fn test() {
+    S.foo()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "()");
+}
+
+#[test]
+fn trait_impl_self_ty_cycle() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait {
+   fn foo(&self);
+}
+
+struct S<T>;
+
+impl Trait for S<Self> {}
+
+fn test() {
+    S.foo()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "{unknown}");
+}
+
+#[test]
 fn unselected_projection_in_trait_env_cycle_1() {
     let t = type_at(
         r#"
@@ -4686,10 +4776,6 @@ fn test<T: Trait>() where T: Trait2<T::Item> {
 }
 
 #[test]
-// FIXME this is currently a Salsa panic; it would be nicer if it just returned
-// in Unknown, and we should be able to do that once Salsa allows us to handle
-// the cycle. But at least it doesn't overflow for now.
-#[should_panic]
 fn unselected_projection_in_trait_env_cycle_2() {
     let t = type_at(
         r#"
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index 35de37e6b..104346ada 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -20,8 +20,8 @@ use ra_db::salsa::{InternId, InternKey};
 
 use super::{AssocTyValue, Canonical, ChalkContext, Impl, Obligation};
 use crate::{
-    db::HirDatabase, display::HirDisplay, ApplicationTy, GenericPredicate, ImplTy, ProjectionTy,
-    Substs, TraitRef, Ty, TypeCtor, TypeWalk,
+    db::HirDatabase, display::HirDisplay, ApplicationTy, GenericPredicate, ProjectionTy, Substs,
+    TraitRef, Ty, TypeCtor, TypeWalk,
 };
 
 /// This represents a trait whose name we could not resolve.
@@ -630,10 +630,7 @@ fn impl_block_datum(
     chalk_id: chalk_ir::ImplId,
     impl_id: ImplId,
 ) -> Option<Arc<ImplDatum<ChalkIr>>> {
-    let trait_ref = match db.impl_ty(impl_id) {
-        ImplTy::TraitRef(it) => it,
-        ImplTy::Inherent(_) => return None,
-    };
+    let trait_ref = db.impl_trait(impl_id)?;
     let impl_data = db.impl_data(impl_id);
 
     let generic_params = db.generic_params(impl_id.into());
@@ -787,11 +784,7 @@ fn type_alias_associated_ty_value(
         _ => panic!("assoc ty value should be in impl"),
     };
 
-    let trait_ref = match db.impl_ty(impl_id) {
-        ImplTy::TraitRef(it) => it,
-        // we don't return any assoc ty values if the impl'd trait can't be resolved
-        ImplTy::Inherent(_) => panic!("assoc ty value should not exist"),
-    };
+    let trait_ref = db.impl_trait(impl_id).expect("assoc ty value should not exist"); // we don't return any assoc ty values if the impl'd trait can't be resolved
 
     let assoc_ty = db
         .trait_data(trait_ref.trait_)