5 files changed, 62 insertions, 45 deletions

diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index e4407ff50..674e9e6f9 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -210,6 +210,7 @@ struct InferenceContext<'a> {
     table: unify::InferenceTable,
     trait_env: Arc<TraitEnvironment>,
     obligations: Vec<DomainGoal>,
+    last_obligations_check: Option<u32>,
     result: InferenceResult,
     /// The return type of the function being inferred, or the closure if we're
     /// currently within one.
@@ -245,6 +246,7 @@ impl<'a> InferenceContext<'a> {
             result: InferenceResult::default(),
             table: unify::InferenceTable::new(),
             obligations: Vec::default(),
+            last_obligations_check: None,
             return_ty: TyKind::Unknown.intern(&Interner), // set in collect_fn_signature
             trait_env: owner
                 .as_generic_def_id()
@@ -334,6 +336,13 @@ impl<'a> InferenceContext<'a> {
     }
 
     fn resolve_obligations_as_possible(&mut self) {
+        if self.last_obligations_check == Some(self.table.revision) {
+            // no change
+            return;
+        }
+        let _span = profile::span("resolve_obligations_as_possible");
+
+        self.last_obligations_check = Some(self.table.revision);
         let obligations = mem::replace(&mut self.obligations, Vec::new());
         for obligation in obligations {
             let in_env = InEnvironment::new(self.trait_env.env.clone(), obligation.clone());
@@ -360,6 +369,11 @@ impl<'a> InferenceContext<'a> {
         }
     }
 
+    fn push_obligation(&mut self, o: DomainGoal) {
+        self.obligations.push(o);
+        self.last_obligations_check = None;
+    }
+
     fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
         self.table.unify(ty1, ty2)
     }
@@ -408,8 +422,8 @@ impl<'a> InferenceContext<'a> {
                     }),
                     ty: ty.clone(),
                 };
-                self.obligations.push(trait_ref.cast(&Interner));
-                self.obligations.push(alias_eq.cast(&Interner));
+                self.push_obligation(trait_ref.cast(&Interner));
+                self.push_obligation(alias_eq.cast(&Interner));
                 self.resolve_ty_as_possible(ty)
             }
             None => self.err_ty(),
@@ -436,7 +450,7 @@ impl<'a> InferenceContext<'a> {
         let var = self.table.new_type_var();
         let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() };
         let obligation = alias_eq.cast(&Interner);
-        self.obligations.push(obligation);
+        self.push_obligation(obligation);
         var
     }
 
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 6279aa572..25ab3ea4c 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -99,7 +99,7 @@ impl<'a> InferenceContext<'a> {
             environment: trait_env,
         });
         if self.db.trait_solve(krate, goal.value).is_some() {
-            self.obligations.push(implements_fn_trait);
+            self.push_obligation(implements_fn_trait);
             let output_proj_ty = crate::ProjectionTy {
                 associated_ty_id: to_assoc_type_id(output_assoc_type),
                 substitution: substs,
@@ -964,7 +964,7 @@ impl<'a> InferenceContext<'a> {
                 let (predicate, binders) =
                     predicate.clone().subst(parameters).into_value_and_skipped_binders();
                 always!(binders == 0); // quantified where clauses not yet handled
-                self.obligations.push(predicate.cast(&Interner));
+                self.push_obligation(predicate.cast(&Interner));
             }
             // add obligation for trait implementation, if this is a trait method
             match def {
@@ -974,7 +974,7 @@ impl<'a> InferenceContext<'a> {
                         // construct a TraitRef
                         let substs =
                             parameters.prefix(generics(self.db.upcast(), trait_.into()).len());
-                        self.obligations.push(
+                        self.push_obligation(
                             TraitRef { trait_id: to_chalk_trait_id(trait_), substitution: substs }
                                 .cast(&Interner),
                         );
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index cefa38509..717738789 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -258,7 +258,7 @@ impl<'a> InferenceContext<'a> {
                             .push(ty.clone())
                             .fill(std::iter::repeat_with(|| self.table.new_type_var()))
                             .build();
-                        self.obligations.push(
+                        self.push_obligation(
                             TraitRef {
                                 trait_id: to_chalk_trait_id(trait_),
                                 substitution: trait_substs.clone(),
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index 6e7b0f5a6..5ea4b7481 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -231,6 +231,7 @@ pub(crate) struct TypeVariableData {
 pub(crate) struct InferenceTable {
     pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>,
     pub(super) type_variable_table: TypeVariableTable,
+    pub(super) revision: u32,
 }
 
 impl InferenceTable {
@@ -238,6 +239,7 @@ impl InferenceTable {
         InferenceTable {
             var_unification_table: InPlaceUnificationTable::new(),
             type_variable_table: TypeVariableTable { inner: Vec::new() },
+            revision: 0,
         }
     }
 
@@ -360,7 +362,10 @@ impl InferenceTable {
                 == self.type_variable_table.is_diverging(*tv2) =>
             {
                 // both type vars are unknown since we tried to resolve them
-                self.var_unification_table.union(tv1.to_inner(), tv2.to_inner());
+                if !self.var_unification_table.unioned(tv1.to_inner(), tv2.to_inner()) {
+                    self.var_unification_table.union(tv1.to_inner(), tv2.to_inner());
+                    self.revision += 1;
+                }
                 true
             }
 
@@ -398,6 +403,7 @@ impl InferenceTable {
                     tv.to_inner(),
                     TypeVarValue::Known(other.clone().intern(&Interner)),
                 );
+                self.revision += 1;
                 true
             }
 
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index a08f694d9..72ee060e0 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -146,7 +146,7 @@ impl<'a> TyLoweringContext<'a> {
         self.lower_ty_ext(type_ref).0
     }
 
-    fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
+    pub fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
         let mut res = None;
         let ty = match type_ref {
             TypeRef::Never => TyKind::Never.intern(&Interner),
@@ -821,24 +821,38 @@ pub fn associated_type_shorthand_candidates<R>(
     res: TypeNs,
     mut cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
 ) -> Option<R> {
-    let traits_from_env: Vec<_> = match res {
-        TypeNs::SelfType(impl_id) => match db.impl_trait(impl_id) {
-            None => vec![],
-            // FIXME: how to correctly handle higher-ranked bounds here?
-            Some(trait_ref) => vec![trait_ref.value.shift_bound_vars_out(DebruijnIndex::ONE)],
-        },
+    let mut search = |t| {
+        for t in all_super_trait_refs(db, t) {
+            let data = db.trait_data(t.hir_trait_id());
+
+            for (name, assoc_id) in &data.items {
+                if let AssocItemId::TypeAliasId(alias) = assoc_id {
+                    if let Some(result) = cb(name, &t, *alias) {
+                        return Some(result);
+                    }
+                }
+            }
+        }
+        None
+    };
+
+    match res {
+        // FIXME: how to correctly handle higher-ranked bounds here?
+        TypeNs::SelfType(impl_id) => {
+            search(db.impl_trait(impl_id)?.value.shift_bound_vars_out(DebruijnIndex::ONE))
+        }
         TypeNs::GenericParam(param_id) => {
             let predicates = db.generic_predicates_for_param(param_id);
-            let mut traits_: Vec<_> = predicates
-                .iter()
-                .filter_map(|pred| match &pred.value.value {
-                    // FIXME: how to correctly handle higher-ranked bounds here?
-                    WhereClause::Implemented(tr) => {
-                        Some(tr.clone().shift_bound_vars_out(DebruijnIndex::ONE))
-                    }
-                    _ => None,
-                })
-                .collect();
+            let res = predicates.iter().find_map(|pred| match &pred.value.value {
+                // FIXME: how to correctly handle higher-ranked bounds here?
+                WhereClause::Implemented(tr) => {
+                    search(tr.clone().shift_bound_vars_out(DebruijnIndex::ONE))
+                }
+                _ => None,
+            });
+            if let res @ Some(_) = res {
+                return res;
+            }
             // Handle `Self::Type` referring to own associated type in trait definitions
             if let GenericDefId::TraitId(trait_id) = param_id.parent {
                 let generics = generics(db.upcast(), trait_id.into());
@@ -849,30 +863,13 @@ pub fn associated_type_shorthand_candidates<R>(
                         trait_id: to_chalk_trait_id(trait_id),
                         substitution: Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST),
                     };
-                    traits_.push(trait_ref);
+                    return search(trait_ref);
                 }
             }
-            traits_
-        }
-        _ => vec![],
-    };
-
-    for t in traits_from_env.into_iter().flat_map(move |t| all_super_trait_refs(db, t)) {
-        let data = db.trait_data(t.hir_trait_id());
-
-        for (name, assoc_id) in &data.items {
-            match assoc_id {
-                AssocItemId::TypeAliasId(alias) => {
-                    if let Some(result) = cb(name, &t, *alias) {
-                        return Some(result);
-                    }
-                }
-                AssocItemId::FunctionId(_) | AssocItemId::ConstId(_) => {}
-            }
+            None
         }
+        _ => None,
     }
-
-    None
 }
 
 /// Build the type of all specific fields of a struct or enum variant.