vendor/chalk-solve-0.55.0/src/infer/unify.rs

   1 use super::var::*;
   2 use super::*;
   3 use crate::debug_span;
   4 use chalk_ir::cast::Cast;
   5 use chalk_ir::fold::{Fold, Folder};
   6 use chalk_ir::interner::{HasInterner, Interner};
   7 use chalk_ir::zip::{Zip, Zipper};
   8 use chalk_ir::UnificationDatabase;
   9 use std::fmt::Debug;
  10 use tracing::{debug, instrument};
  11
  12 impl<I: Interner> InferenceTable<I> {
  13     pub fn relate<T>(
  14         &mut self,
  15         interner: &I,
  16         db: &dyn UnificationDatabase<I>,
  17         environment: &Environment<I>,
  18         variance: Variance,
  19         a: &T,
  20         b: &T,
  21     ) -> Fallible<RelationResult<I>>
  22     where
  23         T: ?Sized + Zip<I>,
  24     {
  25         let snapshot = self.snapshot();
  26         match Unifier::new(interner, db, self, environment).relate(variance, a, b) {
  27             Ok(r) => {
  28                 self.commit(snapshot);
  29                 Ok(r)
  30             }
  31             Err(e) => {
  32                 self.rollback_to(snapshot);
  33                 Err(e)
  34             }
  35         }
  36     }
  37 }
  38
  39 struct Unifier<'t, I: Interner> {
  40     table: &'t mut InferenceTable<I>,
  41     environment: &'t Environment<I>,
  42     goals: Vec<InEnvironment<Goal<I>>>,
  43     interner: &'t I,
  44     db: &'t dyn UnificationDatabase<I>,
  45 }
  46
  47 #[derive(Debug)]
  48 pub struct RelationResult<I: Interner> {
  49     pub goals: Vec<InEnvironment<Goal<I>>>,
  50 }
  51
  52 impl<'t, I: Interner> Unifier<'t, I> {
  53     fn new(
  54         interner: &'t I,
  55         db: &'t dyn UnificationDatabase<I>,
  56         table: &'t mut InferenceTable<I>,
  57         environment: &'t Environment<I>,
  58     ) -> Self {
  59         Unifier {
  60             environment,
  61             table,
  62             goals: vec![],
  63             interner,
  64             db,
  65         }
  66     }
  67
  68     /// The main entry point for the `Unifier` type and really the
  69     /// only type meant to be called externally. Performs a
  70     /// relation of `a` and `b` and returns the Unification Result.
  71     #[instrument(level = "debug", skip(self))]
  72     fn relate<T>(mut self, variance: Variance, a: &T, b: &T) -> Fallible<RelationResult<I>>
  73     where
  74         T: ?Sized + Zip<I>,
  75     {
  76         Zip::zip_with(&mut self, variance, a, b)?;
  77         let interner = self.interner();
  78         let mut goals = self.goals;
  79         let table = self.table;
  80         // Sometimes we'll produce a lifetime outlives goal which we later solve by unification
  81         // Technically, these *will* get canonicalized to the same bound var and so that will end up
  82         // as a goal like `^0.0 <: ^0.0`, which is trivially true. But, we remove those *here*, which
  83         // might help caching.
  84         goals.retain(|g| match g.goal.data(interner) {
  85             GoalData::SubtypeGoal(SubtypeGoal { a, b }) => {
  86                 let n_a = table.ty_root(interner, a);
  87                 let n_b = table.ty_root(interner, b);
  88                 let a = n_a.as_ref().unwrap_or(a);
  89                 let b = n_b.as_ref().unwrap_or(b);
  90                 a != b
  91             }
  92             _ => true,
  93         });
  94         Ok(RelationResult { goals })
  95     }
  96
  97     /// Relate `a`, `b` with the variance such that if `variance = Covariant`, `a` is
  98     /// a subtype of `b`.
  99     fn relate_ty_ty(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> {
 100         let interner = self.interner;
 101
 102         let n_a = self.table.normalize_ty_shallow(interner, a);
 103         let n_b = self.table.normalize_ty_shallow(interner, b);
 104         let a = n_a.as_ref().unwrap_or(a);
 105         let b = n_b.as_ref().unwrap_or(b);
 106
 107         debug_span!("relate_ty_ty", ?variance, ?a, ?b);
 108
 109         if a.kind(interner) == b.kind(interner) {
 110             return Ok(());
 111         }
 112
 113         match (a.kind(interner), b.kind(interner)) {
 114             // Relating two inference variables:
 115             // First, if either variable is a float or int kind, then we always
 116             // unify if they match. This is because float and ints don't have
 117             // subtype relationships.
 118             // If both kinds are general then:
 119             // If `Invariant`, unify them in the underlying ena table.
 120             // If `Covariant` or `Contravariant`, push `SubtypeGoal`
 121             (&TyKind::InferenceVar(var1, kind1), &TyKind::InferenceVar(var2, kind2)) => {
 122                 if matches!(kind1, TyVariableKind::General)
 123                     && matches!(kind2, TyVariableKind::General)
 124                 {
 125                     // Both variable kinds are general; so unify if invariant, otherwise push subtype goal
 126                     match variance {
 127                         Variance::Invariant => self.unify_var_var(var1, var2),
 128                         Variance::Covariant => {
 129                             self.push_subtype_goal(a.clone(), b.clone());
 130                             Ok(())
 131                         }
 132                         Variance::Contravariant => {
 133                             self.push_subtype_goal(b.clone(), a.clone());
 134                             Ok(())
 135                         }
 136                     }
 137                 } else if kind1 == kind2 {
 138                     // At least one kind is not general, but they match, so unify
 139                     self.unify_var_var(var1, var2)
 140                 } else if kind1 == TyVariableKind::General {
 141                     // First kind is general, second isn't, unify
 142                     self.unify_general_var_specific_ty(var1, b.clone())
 143                 } else if kind2 == TyVariableKind::General {
 144                     // Second kind is general, first isn't, unify
 145                     self.unify_general_var_specific_ty(var2, a.clone())
 146                 } else {
 147                     debug!(
 148                         "Tried to unify mis-matching inference variables: {:?} and {:?}",
 149                         kind1, kind2
 150                     );
 151                     Err(NoSolution)
 152                 }
 153             }
 154
 155             // Unifying `forall<X> { T }` with some other forall type `forall<X> { U }`
 156             (&TyKind::Function(ref fn1), &TyKind::Function(ref fn2)) => {
 157                 if fn1.sig == fn2.sig {
 158                     Zip::zip_with(
 159                         self,
 160                         variance,
 161                         &fn1.clone().into_binders(interner),
 162                         &fn2.clone().into_binders(interner),
 163                     )
 164                 } else {
 165                     Err(NoSolution)
 166                 }
 167             }
 168
 169             (&TyKind::Placeholder(ref p1), &TyKind::Placeholder(ref p2)) => {
 170                 Zip::zip_with(self, variance, p1, p2)
 171             }
 172
 173             // Unifying two dyn is possible if they have the same bounds.
 174             (&TyKind::Dyn(ref qwc1), &TyKind::Dyn(ref qwc2)) => {
 175                 Zip::zip_with(self, variance, qwc1, qwc2)
 176             }
 177
 178             (TyKind::BoundVar(_), _) | (_, TyKind::BoundVar(_)) => panic!(
 179                 "unification encountered bound variable: a={:?} b={:?}",
 180                 a, b
 181             ),
 182
 183             // Unifying an alias type with some other type `U`.
 184             (_, &TyKind::Alias(ref alias)) => self.relate_alias_ty(variance.invert(), alias, a),
 185             (&TyKind::Alias(ref alias), _) => self.relate_alias_ty(variance, alias, b),
 186
 187             (&TyKind::InferenceVar(var, kind), ty_data @ _) => {
 188                 let ty = ty_data.clone().intern(interner);
 189                 self.relate_var_ty(variance, var, kind, &ty)
 190             }
 191             (ty_data @ _, &TyKind::InferenceVar(var, kind)) => {
 192                 // We need to invert the variance if inference var is `b` because we pass it in
 193                 // as `a` to relate_var_ty
 194                 let ty = ty_data.clone().intern(interner);
 195                 self.relate_var_ty(variance.invert(), var, kind, &ty)
 196             }
 197
 198             // This would correspond to unifying a `fn` type with a non-fn
 199             // type in Rust; error.
 200             (&TyKind::Function(_), _) | (_, &TyKind::Function(_)) => Err(NoSolution),
 201
 202             // Cannot unify (e.g.) some struct type `Foo` and a placeholder like `T`
 203             (_, &TyKind::Placeholder(_)) | (&TyKind::Placeholder(_), _) => Err(NoSolution),
 204
 205             // Cannot unify `dyn Trait` with things like structs or placeholders
 206             (_, &TyKind::Dyn(_)) | (&TyKind::Dyn(_), _) => Err(NoSolution),
 207
 208             (TyKind::Adt(id_a, substitution_a), TyKind::Adt(id_b, substitution_b)) => {
 209                 if id_a != id_b {
 210                     return Err(NoSolution);
 211                 }
 212                 self.zip_substs(
 213                     variance,
 214                     Some(self.unification_database().adt_variance(*id_a)),
 215                     substitution_a.as_slice(interner),
 216                     substitution_b.as_slice(interner),
 217                 )
 218             }
 219             (
 220                 TyKind::AssociatedType(id_a, substitution_a),
 221                 TyKind::AssociatedType(id_b, substitution_b),
 222             ) => {
 223                 if id_a != id_b {
 224                     return Err(NoSolution);
 225                 }
 226                 self.zip_substs(
 227                     variance,
 228                     None, // TODO: AssociatedType variances?
 229                     substitution_a.as_slice(interner),
 230                     substitution_b.as_slice(interner),
 231                 )
 232             }
 233             (TyKind::Scalar(scalar_a), TyKind::Scalar(scalar_b)) => {
 234                 Zip::zip_with(self, variance, scalar_a, scalar_b)
 235             }
 236             (TyKind::Str, TyKind::Str) => Ok(()),
 237             (TyKind::Tuple(arity_a, substitution_a), TyKind::Tuple(arity_b, substitution_b)) => {
 238                 if arity_a != arity_b {
 239                     return Err(NoSolution);
 240                 }
 241                 self.zip_substs(
 242                     variance,
 243                     Some(Variances::from_iter(
 244                         &self.interner,
 245                         std::iter::repeat(Variance::Covariant).take(*arity_a),
 246                     )),
 247                     substitution_a.as_slice(interner),
 248                     substitution_b.as_slice(interner),
 249                 )
 250             }
 251             (
 252                 TyKind::OpaqueType(id_a, substitution_a),
 253                 TyKind::OpaqueType(id_b, substitution_b),
 254             ) => {
 255                 if id_a != id_b {
 256                     return Err(NoSolution);
 257                 }
 258                 self.zip_substs(
 259                     variance,
 260                     None,
 261                     substitution_a.as_slice(interner),
 262                     substitution_b.as_slice(interner),
 263                 )
 264             }
 265             (TyKind::Slice(ty_a), TyKind::Slice(ty_b)) => Zip::zip_with(self, variance, ty_a, ty_b),
 266             (TyKind::FnDef(id_a, substitution_a), TyKind::FnDef(id_b, substitution_b)) => {
 267                 if id_a != id_b {
 268                     return Err(NoSolution);
 269                 }
 270                 self.zip_substs(
 271                     variance,
 272                     Some(self.unification_database().fn_def_variance(*id_a)),
 273                     substitution_a.as_slice(interner),
 274                     substitution_b.as_slice(interner),
 275                 )
 276             }
 277             (
 278                 TyKind::Ref(mutability_a, lifetime_a, ty_a),
 279                 TyKind::Ref(mutability_b, lifetime_b, ty_b),
 280             ) => {
 281                 if mutability_a != mutability_b {
 282                     return Err(NoSolution);
 283                 }
 284                 // The lifetime is `Contravariant`
 285                 Zip::zip_with(
 286                     self,
 287                     variance.xform(Variance::Contravariant),
 288                     lifetime_a,
 289                     lifetime_b,
 290                 )?;
 291                 // The type is `Covariant` when not mut, `Invariant` otherwise
 292                 let output_variance = match mutability_a {
 293                     Mutability::Not => Variance::Covariant,
 294                     Mutability::Mut => Variance::Invariant,
 295                 };
 296                 Zip::zip_with(self, variance.xform(output_variance), ty_a, ty_b)
 297             }
 298             (TyKind::Raw(mutability_a, ty_a), TyKind::Raw(mutability_b, ty_b)) => {
 299                 if mutability_a != mutability_b {
 300                     return Err(NoSolution);
 301                 }
 302                 let ty_variance = match mutability_a {
 303                     Mutability::Not => Variance::Covariant,
 304                     Mutability::Mut => Variance::Invariant,
 305                 };
 306                 Zip::zip_with(self, variance.xform(ty_variance), ty_a, ty_b)
 307             }
 308             (TyKind::Never, TyKind::Never) => Ok(()),
 309             (TyKind::Array(ty_a, const_a), TyKind::Array(ty_b, const_b)) => {
 310                 Zip::zip_with(self, variance, ty_a, ty_b)?;
 311                 Zip::zip_with(self, variance, const_a, const_b)
 312             }
 313             (TyKind::Closure(id_a, substitution_a), TyKind::Closure(id_b, substitution_b)) => {
 314                 if id_a != id_b {
 315                     return Err(NoSolution);
 316                 }
 317                 self.zip_substs(
 318                     variance,
 319                     None,
 320                     substitution_a.as_slice(interner),
 321                     substitution_b.as_slice(interner),
 322                 )
 323             }
 324             (TyKind::Generator(id_a, substitution_a), TyKind::Generator(id_b, substitution_b)) => {
 325                 if id_a != id_b {
 326                     return Err(NoSolution);
 327                 }
 328                 self.zip_substs(
 329                     variance,
 330                     None,
 331                     substitution_a.as_slice(interner),
 332                     substitution_b.as_slice(interner),
 333                 )
 334             }
 335             (
 336                 TyKind::GeneratorWitness(id_a, substitution_a),
 337                 TyKind::GeneratorWitness(id_b, substitution_b),
 338             ) => {
 339                 if id_a != id_b {
 340                     return Err(NoSolution);
 341                 }
 342                 self.zip_substs(
 343                     variance,
 344                     None,
 345                     substitution_a.as_slice(interner),
 346                     substitution_b.as_slice(interner),
 347                 )
 348             }
 349             (TyKind::Foreign(id_a), TyKind::Foreign(id_b)) => {
 350                 Zip::zip_with(self, variance, id_a, id_b)
 351             }
 352             (TyKind::Error, TyKind::Error) => Ok(()),
 353
 354             (_, _) => Err(NoSolution),
 355         }
 356     }
 357
 358     /// Unify two inference variables
 359     #[instrument(level = "debug", skip(self))]
 360     fn unify_var_var(&mut self, a: InferenceVar, b: InferenceVar) -> Fallible<()> {
 361         let var1 = EnaVariable::from(a);
 362         let var2 = EnaVariable::from(b);
 363         Ok(self
 364             .table
 365             .unify
 366             .unify_var_var(var1, var2)
 367             .expect("unification of two unbound variables cannot fail"))
 368     }
 369
 370     /// Unify a general inference variable with a specific inference variable
 371     /// (type kind is not `General`). For example, unify a `TyVariableKind::General`
 372     /// inference variable with a `TyVariableKind::Integer` variable, resulting in the
 373     /// general inference variable narrowing to an integer variable.
 374
 375     #[instrument(level = "debug", skip(self))]
 376     fn unify_general_var_specific_ty(
 377         &mut self,
 378         general_var: InferenceVar,
 379         specific_ty: Ty<I>,
 380     ) -> Fallible<()> {
 381         self.table
 382             .unify
 383             .unify_var_value(
 384                 general_var,
 385                 InferenceValue::from_ty(self.interner, specific_ty),
 386             )
 387             .unwrap();
 388
 389         Ok(())
 390     }
 391
 392     #[instrument(level = "debug", skip(self))]
 393     fn relate_binders<'a, T, R>(
 394         &mut self,
 395         variance: Variance,
 396         a: &Binders<T>,
 397         b: &Binders<T>,
 398     ) -> Fallible<()>
 399     where
 400         T: Clone + Fold<I, Result = R> + HasInterner<Interner = I>,
 401         R: Zip<I> + Fold<I, Result = R>,
 402         't: 'a,
 403     {
 404         // for<'a...> T == for<'b...> U
 405         //
 406         // if:
 407         //
 408         // for<'a...> exists<'b...> T == U &&
 409         // for<'b...> exists<'a...> T == U
 410
 411         // for<'a...> T <: for<'b...> U
 412         //
 413         // if
 414         //
 415         // for<'b...> exists<'a...> T <: U
 416
 417         let interner = self.interner;
 418
 419         if let Variance::Invariant | Variance::Contravariant = variance {
 420             let a_universal = self
 421                 .table
 422                 .instantiate_binders_universally(interner, a.clone());
 423             let b_existential = self
 424                 .table
 425                 .instantiate_binders_existentially(interner, b.clone());
 426             Zip::zip_with(self, Variance::Contravariant, &a_universal, &b_existential)?;
 427         }
 428
 429         if let Variance::Invariant | Variance::Covariant = variance {
 430             let b_universal = self
 431                 .table
 432                 .instantiate_binders_universally(interner, b.clone());
 433             let a_existential = self
 434                 .table
 435                 .instantiate_binders_existentially(interner, a.clone());
 436             Zip::zip_with(self, Variance::Covariant, &a_existential, &b_universal)?;
 437         }
 438
 439         Ok(())
 440     }
 441
 442     /// Relate an alias like `<T as Trait>::Item` or `impl Trait` with some other
 443     /// type `ty`. If the variance is `Invariant`, creates a goal like
 444     ///
 445     /// ```notrust
 446     /// AliasEq(<T as Trait>::Item = U) // associated type projection
 447     /// AliasEq(impl Trait = U) // impl trait
 448     /// ```
 449     /// Otherwise, this creates a new variable `?X`, creates a goal like
 450     /// ```notrust
 451     /// AliasEq(Alias = ?X)
 452     /// ```
 453     /// and relates `?X` and `ty`.
 454     #[instrument(level = "debug", skip(self))]
 455     fn relate_alias_ty(
 456         &mut self,
 457         variance: Variance,
 458         alias: &AliasTy<I>,
 459         ty: &Ty<I>,
 460     ) -> Fallible<()> {
 461         let interner = self.interner;
 462         match variance {
 463             Variance::Invariant => {
 464                 self.goals.push(InEnvironment::new(
 465                     self.environment,
 466                     AliasEq {
 467                         alias: alias.clone(),
 468                         ty: ty.clone(),
 469                     }
 470                     .cast(interner),
 471                 ));
 472                 Ok(())
 473             }
 474             Variance::Covariant | Variance::Contravariant => {
 475                 let var = self
 476                     .table
 477                     .new_variable(UniverseIndex::root())
 478                     .to_ty(interner);
 479                 self.goals.push(InEnvironment::new(
 480                     self.environment,
 481                     AliasEq {
 482                         alias: alias.clone(),
 483                         ty: var.clone(),
 484                     }
 485                     .cast(interner),
 486                 ));
 487                 self.relate_ty_ty(variance, &var, ty)
 488             }
 489         }
 490     }
 491
 492     #[instrument(level = "debug", skip(self))]
 493     fn generalize_ty(
 494         &mut self,
 495         ty: &Ty<I>,
 496         universe_index: UniverseIndex,
 497         variance: Variance,
 498     ) -> Ty<I> {
 499         let interner = self.interner;
 500         match ty.kind(interner) {
 501             TyKind::Adt(id, substitution) => {
 502                 let variances = if matches!(variance, Variance::Invariant) {
 503                     None
 504                 } else {
 505                     Some(self.unification_database().adt_variance(*id))
 506                 };
 507                 let get_variance = |i| {
 508                     variances
 509                         .as_ref()
 510                         .map(|v| v.as_slice(interner)[i])
 511                         .unwrap_or(Variance::Invariant)
 512                 };
 513                 TyKind::Adt(
 514                     *id,
 515                     self.generalize_substitution(substitution, universe_index, get_variance),
 516                 )
 517                 .intern(interner)
 518             }
 519             TyKind::AssociatedType(id, substitution) => TyKind::AssociatedType(
 520                 *id,
 521                 self.generalize_substitution(substitution, universe_index, |_| variance),
 522             )
 523             .intern(interner),
 524             TyKind::Scalar(scalar) => TyKind::Scalar(*scalar).intern(interner),
 525             TyKind::Str => TyKind::Str.intern(interner),
 526             TyKind::Tuple(arity, substitution) => TyKind::Tuple(
 527                 *arity,
 528                 self.generalize_substitution(substitution, universe_index, |_| variance),
 529             )
 530             .intern(interner),
 531             TyKind::OpaqueType(id, substitution) => TyKind::OpaqueType(
 532                 *id,
 533                 self.generalize_substitution(substitution, universe_index, |_| variance),
 534             )
 535             .intern(interner),
 536             TyKind::Slice(ty) => {
 537                 TyKind::Slice(self.generalize_ty(ty, universe_index, variance)).intern(interner)
 538             }
 539             TyKind::FnDef(id, substitution) => {
 540                 let variances = if matches!(variance, Variance::Invariant) {
 541                     None
 542                 } else {
 543                     Some(self.unification_database().fn_def_variance(*id))
 544                 };
 545                 let get_variance = |i| {
 546                     variances
 547                         .as_ref()
 548                         .map(|v| v.as_slice(interner)[i])
 549                         .unwrap_or(Variance::Invariant)
 550                 };
 551                 TyKind::FnDef(
 552                     *id,
 553                     self.generalize_substitution(substitution, universe_index, get_variance),
 554                 )
 555                 .intern(interner)
 556             }
 557             TyKind::Ref(mutability, lifetime, ty) => {
 558                 let lifetime_variance = variance.xform(Variance::Contravariant);
 559                 let ty_variance = match mutability {
 560                     Mutability::Not => Variance::Covariant,
 561                     Mutability::Mut => Variance::Invariant,
 562                 };
 563                 TyKind::Ref(
 564                     *mutability,
 565                     self.generalize_lifetime(lifetime, universe_index, lifetime_variance),
 566                     self.generalize_ty(ty, universe_index, ty_variance),
 567                 )
 568                 .intern(interner)
 569             }
 570             TyKind::Raw(mutability, ty) => {
 571                 let ty_variance = match mutability {
 572                     Mutability::Not => Variance::Covariant,
 573                     Mutability::Mut => Variance::Invariant,
 574                 };
 575                 TyKind::Raw(
 576                     *mutability,
 577                     self.generalize_ty(ty, universe_index, ty_variance),
 578                 )
 579                 .intern(interner)
 580             }
 581             TyKind::Never => TyKind::Never.intern(interner),
 582             TyKind::Array(ty, const_) => TyKind::Array(
 583                 self.generalize_ty(ty, universe_index, variance),
 584                 self.generalize_const(const_, universe_index),
 585             )
 586             .intern(interner),
 587             TyKind::Closure(id, substitution) => TyKind::Closure(
 588                 *id,
 589                 self.generalize_substitution(substitution, universe_index, |_| variance),
 590             )
 591             .intern(interner),
 592             TyKind::Generator(id, substitution) => TyKind::Generator(
 593                 *id,
 594                 self.generalize_substitution(substitution, universe_index, |_| variance),
 595             )
 596             .intern(interner),
 597             TyKind::GeneratorWitness(id, substitution) => TyKind::GeneratorWitness(
 598                 *id,
 599                 self.generalize_substitution(substitution, universe_index, |_| variance),
 600             )
 601             .intern(interner),
 602             TyKind::Foreign(id) => TyKind::Foreign(*id).intern(interner),
 603             TyKind::Error => TyKind::Error.intern(interner),
 604             TyKind::Dyn(dyn_ty) => {
 605                 let DynTy { bounds, lifetime } = dyn_ty;
 606                 let lifetime = self.generalize_lifetime(
 607                     lifetime,
 608                     universe_index,
 609                     variance.xform(Variance::Contravariant),
 610                 );
 611
 612                 let bounds = bounds.map_ref(|value| {
 613                     let iter = value.iter(interner).map(|sub_var| {
 614                         sub_var.map_ref(|clause| {
 615                             match clause {
 616                                 WhereClause::Implemented(trait_ref) => {
 617                                     let TraitRef {
 618                                         ref substitution,
 619                                         trait_id,
 620                                     } = *trait_ref;
 621                                     let substitution = self.generalize_substitution_skip_self(
 622                                         substitution,
 623                                         universe_index,
 624                                         |_| Some(variance),
 625                                     );
 626                                     WhereClause::Implemented(TraitRef {
 627                                         substitution,
 628                                         trait_id,
 629                                     })
 630                                 }
 631                                 WhereClause::AliasEq(alias_eq) => {
 632                                     let AliasEq { alias, ty: _ } = alias_eq;
 633                                     let alias = match alias {
 634                                         AliasTy::Opaque(opaque_ty) => {
 635                                             let OpaqueTy {
 636                                                 ref substitution,
 637                                                 opaque_ty_id,
 638                                             } = *opaque_ty;
 639                                             let substitution = self.generalize_substitution(
 640                                                 substitution,
 641                                                 universe_index,
 642                                                 |_| variance,
 643                                             );
 644                                             AliasTy::Opaque(OpaqueTy {
 645                                                 substitution,
 646                                                 opaque_ty_id,
 647                                             })
 648                                         }
 649                                         AliasTy::Projection(projection_ty) => {
 650                                             let ProjectionTy {
 651                                                 ref substitution,
 652                                                 associated_ty_id,
 653                                             } = *projection_ty;
 654                                             // TODO: We should be skipping "self", which
 655                                             // would be the first element of
 656                                             // "trait_params" if we had a
 657                                             // `RustIrDatabase` to call
 658                                             // `split_projection` on...
 659                                             // let (assoc_ty_datum, trait_params, assoc_type_params) = s.db().split_projection(&self);
 660                                             let substitution = self.generalize_substitution(
 661                                                 substitution,
 662                                                 universe_index,
 663                                                 |_| variance,
 664                                             );
 665                                             AliasTy::Projection(ProjectionTy {
 666                                                 substitution,
 667                                                 associated_ty_id,
 668                                             })
 669                                         }
 670                                     };
 671                                     let ty =
 672                                         self.table.new_variable(universe_index).to_ty(interner);
 673                                     WhereClause::AliasEq(AliasEq { alias, ty })
 674                                 }
 675                                 WhereClause::TypeOutlives(_) => {
 676                                     let lifetime_var = self.table.new_variable(universe_index);
 677                                     let lifetime = lifetime_var.to_lifetime(interner);
 678                                     let ty_var = self.table.new_variable(universe_index);
 679                                     let ty = ty_var.to_ty(interner);
 680                                     WhereClause::TypeOutlives(TypeOutlives {
 681                                         ty: ty,
 682                                         lifetime: lifetime,
 683                                     })
 684                                 }
 685                                 WhereClause::LifetimeOutlives(_) => {
 686                                     unreachable!("dyn Trait never contains LifetimeOutlive bounds")
 687                                 }
 688                             }
 689                         })
 690                     });
 691                     QuantifiedWhereClauses::from_iter(interner, iter)
 692                 });
 693
 694                 TyKind::Dyn(DynTy { bounds, lifetime }).intern(interner)
 695             }
 696             TyKind::Function(fn_ptr) => {
 697                 let FnPointer {
 698                     num_binders,
 699                     sig,
 700                     ref substitution,
 701                 } = *fn_ptr;
 702
 703                 let len = substitution.0.len(interner);
 704                 let vars = substitution.0.iter(interner).enumerate().map(|(i, var)| {
 705                     if i < len - 1 {
 706                         self.generalize_generic_var(
 707                             var,
 708                             universe_index,
 709                             variance.xform(Variance::Contravariant),
 710                         )
 711                     } else {
 712                         self.generalize_generic_var(
 713                             substitution.0.as_slice(interner).last().unwrap(),
 714                             universe_index,
 715                             variance,
 716                         )
 717                     }
 718                 });
 719
 720                 let substitution = FnSubst(Substitution::from_iter(interner, vars));
 721
 722                 TyKind::Function(FnPointer {
 723                     num_binders,
 724                     sig,
 725                     substitution,
 726                 })
 727                 .intern(interner)
 728             }
 729             TyKind::Placeholder(_) | TyKind::BoundVar(_) => {
 730                 debug!("just generalizing to the ty itself: {:?}", ty);
 731                 // BoundVar and PlaceHolder have no internal values to be
 732                 // generic over, so we just relate directly to it
 733                 ty.clone()
 734             }
 735             TyKind::Alias(_) => {
 736                 let ena_var = self.table.new_variable(universe_index);
 737                 ena_var.to_ty(interner)
 738             }
 739             TyKind::InferenceVar(_var, kind) => {
 740                 if matches!(kind, TyVariableKind::Integer | TyVariableKind::Float) {
 741                     ty.clone()
 742                 } else if let Some(ty) = self.table.normalize_ty_shallow(interner, ty) {
 743                     self.generalize_ty(&ty, universe_index, variance)
 744                 } else if matches!(variance, Variance::Invariant) {
 745                     ty.clone()
 746                 } else {
 747                     let ena_var = self.table.new_variable(universe_index);
 748                     ena_var.to_ty(interner)
 749                 }
 750             }
 751         }
 752     }
 753
 754     #[instrument(level = "debug", skip(self))]
 755     fn generalize_lifetime(
 756         &mut self,
 757         lifetime: &Lifetime<I>,
 758         universe_index: UniverseIndex,
 759         variance: Variance,
 760     ) -> Lifetime<I> {
 761         let interner = self.interner;
 762         match lifetime.data(&interner) {
 763             LifetimeData::BoundVar(_) => {
 764                 return lifetime.clone();
 765             }
 766             _ => {
 767                 if matches!(variance, Variance::Invariant) {
 768                     lifetime.clone()
 769                 } else {
 770                     let ena_var = self.table.new_variable(universe_index);
 771                     ena_var.to_lifetime(interner)
 772                 }
 773             }
 774         }
 775     }
 776
 777     #[instrument(level = "debug", skip(self))]
 778     fn generalize_const(&mut self, const_: &Const<I>, universe_index: UniverseIndex) -> Const<I> {
 779         let interner = self.interner;
 780         let data = const_.data(&interner);
 781         match data.value {
 782             ConstValue::BoundVar(_) => {
 783                 return const_.clone();
 784             }
 785             _ => {
 786                 let ena_var = self.table.new_variable(universe_index);
 787                 ena_var.to_const(interner, data.ty.clone())
 788             }
 789         }
 790     }
 791
 792     fn generalize_generic_var(
 793         &mut self,
 794         sub_var: &GenericArg<I>,
 795         universe_index: UniverseIndex,
 796         variance: Variance,
 797     ) -> GenericArg<I> {
 798         let interner = self.interner;
 799         (match sub_var.data(interner) {
 800             GenericArgData::Ty(ty) => {
 801                 GenericArgData::Ty(self.generalize_ty(ty, universe_index, variance))
 802             }
 803             GenericArgData::Lifetime(lifetime) => GenericArgData::Lifetime(
 804                 self.generalize_lifetime(lifetime, universe_index, variance),
 805             ),
 806             GenericArgData::Const(const_value) => {
 807                 GenericArgData::Const(self.generalize_const(const_value, universe_index))
 808             }
 809         })
 810         .intern(interner)
 811     }
 812
 813     /// Generalizes all but the first
 814     #[instrument(level = "debug", skip(self, get_variance))]
 815     fn generalize_substitution_skip_self<F: Fn(usize) -> Option<Variance>>(
 816         &mut self,
 817         substitution: &Substitution<I>,
 818         universe_index: UniverseIndex,
 819         get_variance: F,
 820     ) -> Substitution<I> {
 821         let interner = self.interner;
 822         let vars = substitution.iter(interner).enumerate().map(|(i, sub_var)| {
 823             if i == 0 {
 824                 sub_var.clone()
 825             } else {
 826                 let variance = get_variance(i).unwrap_or(Variance::Invariant);
 827                 self.generalize_generic_var(sub_var, universe_index, variance)
 828             }
 829         });
 830         Substitution::from_iter(interner, vars)
 831     }
 832
 833     #[instrument(level = "debug", skip(self, get_variance))]
 834     fn generalize_substitution<F: Fn(usize) -> Variance>(
 835         &mut self,
 836         substitution: &Substitution<I>,
 837         universe_index: UniverseIndex,
 838         get_variance: F,
 839     ) -> Substitution<I> {
 840         let interner = self.interner;
 841         let vars = substitution.iter(interner).enumerate().map(|(i, sub_var)| {
 842             let variance = get_variance(i);
 843             self.generalize_generic_var(sub_var, universe_index, variance)
 844         });
 845
 846         Substitution::from_iter(interner, vars)
 847     }
 848
 849     /// Unify an inference variable `var` with some non-inference
 850     /// variable `ty`, just bind `var` to `ty`. But we must enforce two conditions:
 851     ///
 852     /// - `var` does not appear inside of `ty` (the standard `OccursCheck`)
 853     /// - `ty` does not reference anything in a lifetime that could not be named in `var`
 854     ///   (the extended `OccursCheck` created to handle universes)
 855     #[instrument(level = "debug", skip(self))]
 856     fn relate_var_ty(
 857         &mut self,
 858         variance: Variance,
 859         var: InferenceVar,
 860         var_kind: TyVariableKind,
 861         ty: &Ty<I>,
 862     ) -> Fallible<()> {
 863         let interner = self.interner;
 864
 865         match (var_kind, ty.is_integer(interner), ty.is_float(interner)) {
 866             // General inference variables can unify with any type
 867             (TyVariableKind::General, _, _)
 868             // Integer inference variables can only unify with integer types
 869             | (TyVariableKind::Integer, true, _)
 870             // Float inference variables can only unify with float types
 871             | (TyVariableKind::Float, _, true) => {
 872             },
 873             _ => return Err(NoSolution),
 874         }
 875
 876         let var = EnaVariable::from(var);
 877
 878         // Determine the universe index associated with this
 879         // variable. This is basically a count of the number of
 880         // `forall` binders that had been introduced at the point
 881         // this variable was created -- though it may change over time
 882         // as the variable is unified.
 883         let universe_index = self.table.universe_of_unbound_var(var);
 884         // let universe_index = self.table.max_universe();
 885
 886         debug!("relate_var_ty: universe index of var: {:?}", universe_index);
 887
 888         debug!("trying fold_with on {:?}", ty);
 889         let ty1 = ty
 890             .clone()
 891             .fold_with(
 892                 &mut OccursCheck::new(self, var, universe_index),
 893                 DebruijnIndex::INNERMOST,
 894             )
 895             .map_err(|e| {
 896                 debug!("failed to fold {:?}", ty);
 897                 e
 898             })?;
 899
 900         // "Generalize" types. This ensures that we aren't accidentally forcing
 901         // too much onto `var`. Instead of directly setting `var` equal to `ty`,
 902         // we just take the outermost structure we _know_ `var` holds, and then
 903         // apply that to `ty`. This involves creating new inference vars for
 904         // everything inside `var`, then calling `relate_ty_ty` to relate those
 905         // inference vars to the things they generalized with the correct
 906         // variance.
 907
 908         // The main problem this solves is that lifetime relationships are
 909         // relationships, not just eq ones. So when solving &'a u32 <: U,
 910         // generalizing we would end up with U = &'a u32. Instead, we want
 911         // U = &'b u32, with a lifetime constraint 'a <: 'b. This matters
 912         // especially when solving multiple constraints - for example, &'a u32
 913         // <: U, &'b u32 <: U (where without generalizing, we'd end up with 'a
 914         // <: 'b, where we really want 'a <: 'c, 'b <: 'c for some 'c).
 915
 916         // Example operation: consider `ty` as `&'x SomeType`. To generalize
 917         // this, we create two new vars `'0` and `1`. Then we relate `var` with
 918         // `&'0 1` and `&'0 1` with `&'x SomeType`. The second relation will
 919         // recurse, and we'll end up relating `'0` with `'x` and `1` with `SomeType`.
 920         let generalized_val = self.generalize_ty(&ty1, universe_index, variance);
 921
 922         debug!("var {:?} generalized to {:?}", var, generalized_val);
 923
 924         self.table
 925             .unify
 926             .unify_var_value(
 927                 var,
 928                 InferenceValue::from_ty(interner, generalized_val.clone()),
 929             )
 930             .unwrap();
 931         debug!("var {:?} set to {:?}", var, generalized_val);
 932
 933         self.relate_ty_ty(variance, &generalized_val, &ty1)?;
 934
 935         debug!(
 936             "generalized version {:?} related to original {:?}",
 937             generalized_val, ty1
 938         );
 939
 940         Ok(())
 941     }
 942
 943     fn relate_lifetime_lifetime(
 944         &mut self,
 945         variance: Variance,
 946         a: &Lifetime<I>,
 947         b: &Lifetime<I>,
 948     ) -> Fallible<()> {
 949         let interner = self.interner;
 950
 951         let n_a = self.table.normalize_lifetime_shallow(interner, a);
 952         let n_b = self.table.normalize_lifetime_shallow(interner, b);
 953         let a = n_a.as_ref().unwrap_or(a);
 954         let b = n_b.as_ref().unwrap_or(b);
 955
 956         debug_span!("relate_lifetime_lifetime", ?variance, ?a, ?b);
 957
 958         match (a.data(interner), b.data(interner)) {
 959             (&LifetimeData::InferenceVar(var_a), &LifetimeData::InferenceVar(var_b)) => {
 960                 let var_a = EnaVariable::from(var_a);
 961                 let var_b = EnaVariable::from(var_b);
 962                 debug!(?var_a, ?var_b);
 963                 self.table.unify.unify_var_var(var_a, var_b).unwrap();
 964                 Ok(())
 965             }
 966
 967             (
 968                 &LifetimeData::InferenceVar(a_var),
 969                 &LifetimeData::Placeholder(PlaceholderIndex { ui, .. }),
 970             )
 971             | (&LifetimeData::InferenceVar(a_var), &LifetimeData::Empty(ui)) => {
 972                 self.unify_lifetime_var(variance, a_var, b, ui)
 973             }
 974
 975             (
 976                 &LifetimeData::Placeholder(PlaceholderIndex { ui, .. }),
 977                 &LifetimeData::InferenceVar(b_var),
 978             )
 979             | (&LifetimeData::Empty(ui), &LifetimeData::InferenceVar(b_var)) => {
 980                 self.unify_lifetime_var(variance.invert(), b_var, a, ui)
 981             }
 982
 983             (&LifetimeData::InferenceVar(a_var), &LifetimeData::Erased)
 984             | (&LifetimeData::InferenceVar(a_var), &LifetimeData::Static) => {
 985                 self.unify_lifetime_var(variance, a_var, b, UniverseIndex::root())
 986             }
 987
 988             (&LifetimeData::Erased, &LifetimeData::InferenceVar(b_var))
 989             | (&LifetimeData::Static, &LifetimeData::InferenceVar(b_var)) => {
 990                 self.unify_lifetime_var(variance.invert(), b_var, a, UniverseIndex::root())
 991             }
 992
 993             (&LifetimeData::Static, &LifetimeData::Static)
 994             | (&LifetimeData::Erased, &LifetimeData::Erased) => Ok(()),
 995
 996             (&LifetimeData::Static, &LifetimeData::Placeholder(_))
 997             | (&LifetimeData::Static, &LifetimeData::Empty(_))
 998             | (&LifetimeData::Static, &LifetimeData::Erased)
 999             | (&LifetimeData::Placeholder(_), &LifetimeData::Static)
1000             | (&LifetimeData::Placeholder(_), &LifetimeData::Placeholder(_))
1001             | (&LifetimeData::Placeholder(_), &LifetimeData::Empty(_))
1002             | (&LifetimeData::Placeholder(_), &LifetimeData::Erased)
1003             | (&LifetimeData::Empty(_), &LifetimeData::Static)
1004             | (&LifetimeData::Empty(_), &LifetimeData::Placeholder(_))
1005             | (&LifetimeData::Empty(_), &LifetimeData::Empty(_))
1006             | (&LifetimeData::Empty(_), &LifetimeData::Erased)
1007             | (&LifetimeData::Erased, &LifetimeData::Static)
1008             | (&LifetimeData::Erased, &LifetimeData::Placeholder(_))
1009             | (&LifetimeData::Erased, &LifetimeData::Empty(_)) => {
1010                 if a != b {
1011                     Ok(self.push_lifetime_outlives_goals(variance, a.clone(), b.clone()))
1012                 } else {
1013                     Ok(())
1014                 }
1015             }
1016
1017             (LifetimeData::BoundVar(_), _) | (_, LifetimeData::BoundVar(_)) => panic!(
1018                 "unification encountered bound variable: a={:?} b={:?}",
1019                 a, b
1020             ),
1021
1022             (LifetimeData::Phantom(..), _) | (_, LifetimeData::Phantom(..)) => unreachable!(),
1023         }
1024     }
1025
1026     #[instrument(level = "debug", skip(self))]
1027     fn unify_lifetime_var(
1028         &mut self,
1029         variance: Variance,
1030         var: InferenceVar,
1031         value: &Lifetime<I>,
1032         value_ui: UniverseIndex,
1033     ) -> Fallible<()> {
1034         let var = EnaVariable::from(var);
1035         let var_ui = self.table.universe_of_unbound_var(var);
1036         if var_ui.can_see(value_ui) && matches!(variance, Variance::Invariant) {
1037             debug!("{:?} in {:?} can see {:?}; unifying", var, var_ui, value_ui);
1038             self.table
1039                 .unify
1040                 .unify_var_value(
1041                     var,
1042                     InferenceValue::from_lifetime(&self.interner, value.clone()),
1043                 )
1044                 .unwrap();
1045             Ok(())
1046         } else {
1047             debug!(
1048                 "{:?} in {:?} cannot see {:?}; pushing constraint",
1049                 var, var_ui, value_ui
1050             );
1051             Ok(self.push_lifetime_outlives_goals(
1052                 variance,
1053                 var.to_lifetime(&self.interner),
1054                 value.clone(),
1055             ))
1056         }
1057     }
1058
1059     fn relate_const_const<'a>(
1060         &mut self,
1061         variance: Variance,
1062         a: &'a Const<I>,
1063         b: &'a Const<I>,
1064     ) -> Fallible<()> {
1065         let interner = self.interner;
1066
1067         let n_a = self.table.normalize_const_shallow(interner, a);
1068         let n_b = self.table.normalize_const_shallow(interner, b);
1069         let a = n_a.as_ref().unwrap_or(a);
1070         let b = n_b.as_ref().unwrap_or(b);
1071
1072         debug_span!("relate_const_const", ?variance, ?a, ?b);
1073
1074         let ConstData {
1075             ty: a_ty,
1076             value: a_val,
1077         } = a.data(interner);
1078         let ConstData {
1079             ty: b_ty,
1080             value: b_val,
1081         } = b.data(interner);
1082
1083         self.relate_ty_ty(variance, a_ty, b_ty)?;
1084
1085         match (a_val, b_val) {
1086             // Unifying two inference variables: unify them in the underlying
1087             // ena table.
1088             (&ConstValue::InferenceVar(var1), &ConstValue::InferenceVar(var2)) => {
1089                 debug!(?var1, ?var2, "relate_ty_ty");
1090                 let var1 = EnaVariable::from(var1);
1091                 let var2 = EnaVariable::from(var2);
1092                 Ok(self
1093                     .table
1094                     .unify
1095                     .unify_var_var(var1, var2)
1096                     .expect("unification of two unbound variables cannot fail"))
1097             }
1098
1099             // Unifying an inference variables with a non-inference variable.
1100             (&ConstValue::InferenceVar(var), &ConstValue::Concrete(_))
1101             | (&ConstValue::InferenceVar(var), &ConstValue::Placeholder(_)) => {
1102                 debug!(?var, ty=?b, "unify_var_ty");
1103                 self.unify_var_const(var, b)
1104             }
1105
1106             (&ConstValue::Concrete(_), &ConstValue::InferenceVar(var))
1107             | (&ConstValue::Placeholder(_), &ConstValue::InferenceVar(var)) => {
1108                 debug!(?var, ty=?a, "unify_var_ty");
1109                 self.unify_var_const(var, a)
1110             }
1111
1112             (&ConstValue::Placeholder(p1), &ConstValue::Placeholder(p2)) => {
1113                 Zip::zip_with(self, variance, &p1, &p2)
1114             }
1115
1116             (&ConstValue::Concrete(ref ev1), &ConstValue::Concrete(ref ev2)) => {
1117                 if ev1.const_eq(a_ty, ev2, interner) {
1118                     Ok(())
1119                 } else {
1120                     Err(NoSolution)
1121                 }
1122             }
1123
1124             (&ConstValue::Concrete(_), &ConstValue::Placeholder(_))
1125             | (&ConstValue::Placeholder(_), &ConstValue::Concrete(_)) => Err(NoSolution),
1126
1127             (ConstValue::BoundVar(_), _) | (_, ConstValue::BoundVar(_)) => panic!(
1128                 "unification encountered bound variable: a={:?} b={:?}",
1129                 a, b
1130             ),
1131         }
1132     }
1133
1134     #[instrument(level = "debug", skip(self))]
1135     fn unify_var_const(&mut self, var: InferenceVar, c: &Const<I>) -> Fallible<()> {
1136         let interner = self.interner;
1137         let var = EnaVariable::from(var);
1138
1139         // Determine the universe index associated with this
1140         // variable. This is basically a count of the number of
1141         // `forall` binders that had been introduced at the point
1142         // this variable was created -- though it may change over time
1143         // as the variable is unified.
1144         let universe_index = self.table.universe_of_unbound_var(var);
1145
1146         let c1 = c.clone().fold_with(
1147             &mut OccursCheck::new(self, var, universe_index),
1148             DebruijnIndex::INNERMOST,
1149         )?;
1150
1151         debug!("unify_var_const: var {:?} set to {:?}", var, c1);
1152         self.table
1153             .unify
1154             .unify_var_value(var, InferenceValue::from_const(interner, c1))
1155             .unwrap();
1156
1157         Ok(())
1158     }
1159
1160     /// Relate `a`, `b` such that if `variance = Covariant`, `a` is a subtype of
1161     /// `b` and thus `a` must outlive `b`.
1162     fn push_lifetime_outlives_goals(&mut self, variance: Variance, a: Lifetime<I>, b: Lifetime<I>) {
1163         debug!(
1164             "pushing lifetime outlives goals for a={:?} b={:?} with variance {:?}",
1165             a, b, variance
1166         );
1167         if matches!(variance, Variance::Invariant | Variance::Contravariant) {
1168             self.goals.push(InEnvironment::new(
1169                 self.environment,
1170                 WhereClause::LifetimeOutlives(LifetimeOutlives {
1171                     a: a.clone(),
1172                     b: b.clone(),
1173                 })
1174                 .cast(self.interner),
1175             ));
1176         }
1177         if matches!(variance, Variance::Invariant | Variance::Covariant) {
1178             self.goals.push(InEnvironment::new(
1179                 self.environment,
1180                 WhereClause::LifetimeOutlives(LifetimeOutlives { a: b, b: a }).cast(self.interner),
1181             ));
1182         }
1183     }
1184
1185     /// Pushes a goal of `a` being a subtype of `b`.
1186     fn push_subtype_goal(&mut self, a: Ty<I>, b: Ty<I>) {
1187         let subtype_goal = GoalData::SubtypeGoal(SubtypeGoal { a, b }).intern(self.interner());
1188         self.goals
1189             .push(InEnvironment::new(self.environment, subtype_goal));
1190     }
1191 }
1192
1193 impl<'i, I: Interner> Zipper<'i, I> for Unifier<'i, I> {
1194     fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> {
1195         debug!("zip_tys {:?}, {:?}, {:?}", variance, a, b);
1196         self.relate_ty_ty(variance, a, b)
1197     }
1198
1199     fn zip_lifetimes(
1200         &mut self,
1201         variance: Variance,
1202         a: &Lifetime<I>,
1203         b: &Lifetime<I>,
1204     ) -> Fallible<()> {
1205         self.relate_lifetime_lifetime(variance, a, b)
1206     }
1207
1208     fn zip_consts(&mut self, variance: Variance, a: &Const<I>, b: &Const<I>) -> Fallible<()> {
1209         self.relate_const_const(variance, a, b)
1210     }
1211
1212     fn zip_binders<T>(&mut self, variance: Variance, a: &Binders<T>, b: &Binders<T>) -> Fallible<()>
1213     where
1214         T: Clone + HasInterner<Interner = I> + Zip<I> + Fold<I, Result = T>,
1215     {
1216         // The binders that appear in types (apart from quantified types, which are
1217         // handled in `unify_ty`) appear as part of `dyn Trait` and `impl Trait` types.
1218         //
1219         // They come in two varieties:
1220         //
1221         // * The existential binder from `dyn Trait` / `impl Trait`
1222         //   (representing the hidden "self" type)
1223         // * The `for<..>` binders from higher-ranked traits.
1224         //
1225         // In both cases we can use the same `relate_binders` routine.
1226
1227         self.relate_binders(variance, a, b)
1228     }
1229
1230     fn interner(&self) -> &'i I {
1231         self.interner
1232     }
1233
1234     fn unification_database(&self) -> &dyn UnificationDatabase<I> {
1235         self.db
1236     }
1237 }
1238
1239 struct OccursCheck<'u, 't, I: Interner> {
1240     unifier: &'u mut Unifier<'t, I>,
1241     var: EnaVariable<I>,
1242     universe_index: UniverseIndex,
1243 }
1244
1245 impl<'u, 't, I: Interner> OccursCheck<'u, 't, I> {
1246     fn new(
1247         unifier: &'u mut Unifier<'t, I>,
1248         var: EnaVariable<I>,
1249         universe_index: UniverseIndex,
1250     ) -> Self {
1251         OccursCheck {
1252             unifier,
1253             var,
1254             universe_index,
1255         }
1256     }
1257 }
1258
1259 impl<'i, I: Interner> Folder<'i, I> for OccursCheck<'_, 'i, I>
1260 where
1261     I: 'i,
1262 {
1263     fn as_dyn(&mut self) -> &mut dyn Folder<'i, I> {
1264         self
1265     }
1266
1267     fn fold_free_placeholder_ty(
1268         &mut self,
1269         universe: PlaceholderIndex,
1270         _outer_binder: DebruijnIndex,
1271     ) -> Fallible<Ty<I>> {
1272         let interner = self.interner();
1273         if self.universe_index < universe.ui {
1274             debug!(
1275                 "OccursCheck aborting because self.universe_index ({:?}) < universe.ui ({:?})",
1276                 self.universe_index, universe.ui
1277             );
1278             Err(NoSolution)
1279         } else {
1280             Ok(universe.to_ty(interner)) // no need to shift, not relative to depth
1281         }
1282     }
1283
1284     fn fold_free_placeholder_const(
1285         &mut self,
1286         ty: Ty<I>,
1287         universe: PlaceholderIndex,
1288         _outer_binder: DebruijnIndex,
1289     ) -> Fallible<Const<I>> {
1290         let interner = self.interner();
1291         if self.universe_index < universe.ui {
1292             Err(NoSolution)
1293         } else {
1294             Ok(universe.to_const(interner, ty.clone())) // no need to shift, not relative to depth
1295         }
1296     }
1297
1298     #[instrument(level = "debug", skip(self))]
1299     fn fold_free_placeholder_lifetime(
1300         &mut self,
1301         ui: PlaceholderIndex,
1302         _outer_binder: DebruijnIndex,
1303     ) -> Fallible<Lifetime<I>> {
1304         let interner = self.interner();
1305         if self.universe_index < ui.ui {
1306             // Scenario is like:
1307             //
1308             // exists<T> forall<'b> ?T = Foo<'b>
1309             //
1310             // unlike with a type variable, this **might** be
1311             // ok.  Ultimately it depends on whether the
1312             // `forall` also introduced relations to lifetimes
1313             // nameable in T. To handle that, we introduce a
1314             // fresh region variable `'x` in same universe as `T`
1315             // and add a side-constraint that `'x = 'b`:
1316             //
1317             // exists<'x> forall<'b> ?T = Foo<'x>, where 'x = 'b
1318
1319             let tick_x = self.unifier.table.new_variable(self.universe_index);
1320             self.unifier.push_lifetime_outlives_goals(
1321                 Variance::Invariant,
1322                 tick_x.to_lifetime(interner),
1323                 ui.to_lifetime(interner),
1324             );
1325             Ok(tick_x.to_lifetime(interner))
1326         } else {
1327             // If the `ui` is higher than `self.universe_index`, then we can name
1328             // this lifetime, no problem.
1329             Ok(ui.to_lifetime(interner)) // no need to shift, not relative to depth
1330         }
1331     }
1332
1333     fn fold_inference_ty(
1334         &mut self,
1335         var: InferenceVar,
1336         kind: TyVariableKind,
1337         _outer_binder: DebruijnIndex,
1338     ) -> Fallible<Ty<I>> {
1339         let interner = self.interner();
1340         let var = EnaVariable::from(var);
1341         match self.unifier.table.unify.probe_value(var) {
1342             // If this variable already has a value, fold over that value instead.
1343             InferenceValue::Bound(normalized_ty) => {
1344                 let normalized_ty = normalized_ty.assert_ty_ref(interner);
1345                 let normalized_ty = normalized_ty
1346                     .clone()
1347                     .fold_with(self, DebruijnIndex::INNERMOST)?;
1348                 assert!(!normalized_ty.needs_shift(interner));
1349                 Ok(normalized_ty)
1350             }
1351
1352             // Otherwise, check the universe of the variable, and also
1353             // check for cycles with `self.var` (which this will soon
1354             // become the value of).
1355             InferenceValue::Unbound(ui) => {
1356                 if self.unifier.table.unify.unioned(var, self.var) {
1357                     debug!(
1358                         "OccursCheck aborting because {:?} unioned with {:?}",
1359                         var, self.var,
1360                     );
1361                     return Err(NoSolution);
1362                 }
1363
1364                 if self.universe_index < ui {
1365                     // Scenario is like:
1366                     //
1367                     // ?A = foo(?B)
1368                     //
1369                     // where ?A is in universe 0 and ?B is in universe 1.
1370                     // This is OK, if ?B is promoted to universe 0.
1371                     self.unifier
1372                         .table
1373                         .unify
1374                         .unify_var_value(var, InferenceValue::Unbound(self.universe_index))
1375                         .unwrap();
1376                 }
1377
1378                 Ok(var.to_ty_with_kind(interner, kind))
1379             }
1380         }
1381     }
1382
1383     fn fold_inference_const(
1384         &mut self,
1385         ty: Ty<I>,
1386         var: InferenceVar,
1387         _outer_binder: DebruijnIndex,
1388     ) -> Fallible<Const<I>> {
1389         let interner = self.interner();
1390         let var = EnaVariable::from(var);
1391         match self.unifier.table.unify.probe_value(var) {
1392             // If this variable already has a value, fold over that value instead.
1393             InferenceValue::Bound(normalized_const) => {
1394                 let normalized_const = normalized_const.assert_const_ref(interner);
1395                 let normalized_const = normalized_const
1396                     .clone()
1397                     .fold_with(self, DebruijnIndex::INNERMOST)?;
1398                 assert!(!normalized_const.needs_shift(interner));
1399                 Ok(normalized_const)
1400             }
1401
1402             // Otherwise, check the universe of the variable, and also
1403             // check for cycles with `self.var` (which this will soon
1404             // become the value of).
1405             InferenceValue::Unbound(ui) => {
1406                 if self.unifier.table.unify.unioned(var, self.var) {
1407                     return Err(NoSolution);
1408                 }
1409
1410                 if self.universe_index < ui {
1411                     // Scenario is like:
1412                     //
1413                     // forall<const A> exists<const B> ?C = Foo<B>
1414                     //
1415                     // where A is in universe 0 and B is in universe 1.
1416                     // This is OK, if B is promoted to universe 0.
1417                     self.unifier
1418                         .table
1419                         .unify
1420                         .unify_var_value(var, InferenceValue::Unbound(self.universe_index))
1421                         .unwrap();
1422                 }
1423
1424                 Ok(var.to_const(interner, ty))
1425             }
1426         }
1427     }
1428
1429     fn fold_inference_lifetime(
1430         &mut self,
1431         var: InferenceVar,
1432         outer_binder: DebruijnIndex,
1433     ) -> Fallible<Lifetime<I>> {
1434         // a free existentially bound region; find the
1435         // inference variable it corresponds to
1436         let interner = self.interner();
1437         let var = EnaVariable::from(var);
1438         match self.unifier.table.unify.probe_value(var) {
1439             InferenceValue::Unbound(ui) => {
1440                 if self.universe_index < ui {
1441                     // Scenario is like:
1442                     //
1443                     // exists<T> forall<'b> exists<'a> ?T = Foo<'a>
1444                     //
1445                     // where ?A is in universe 0 and `'b` is in universe 1.
1446                     // This is OK, if `'b` is promoted to universe 0.
1447                     self.unifier
1448                         .table
1449                         .unify
1450                         .unify_var_value(var, InferenceValue::Unbound(self.universe_index))
1451                         .unwrap();
1452                 }
1453                 Ok(var.to_lifetime(interner))
1454             }
1455
1456             InferenceValue::Bound(l) => {
1457                 let l = l.assert_lifetime_ref(interner);
1458                 let l = l.clone().fold_with(self, outer_binder)?;
1459                 assert!(!l.needs_shift(interner));
1460                 Ok(l)
1461             }
1462         }
1463     }
1464
1465     fn forbid_free_vars(&self) -> bool {
1466         true
1467     }
1468
1469     fn interner(&self) -> &'i I {
1470         self.unifier.interner
1471     }
1472 }