vendor/chalk-ir/src/could_match.rs

   1 //! Fast matching check for zippable values.
   2
   3 use crate::interner::HasInterner;
   4 use crate::zip::{Zip, Zipper};
   5 use crate::*;
   6
   7 /// A fast check to see whether two things could ever possibly match.
   8 pub trait CouldMatch<T: ?Sized + HasInterner> {
   9     /// Checks whether `self` and `other` could possibly match.
  10     fn could_match(
  11         &self,
  12         interner: &T::Interner,
  13         db: &dyn UnificationDatabase<T::Interner>,
  14         other: &T,
  15     ) -> bool;
  16 }
  17
  18 #[allow(unreachable_code, unused_variables)]
  19 impl<T, I> CouldMatch<T> for T
  20 where
  21     T: Zip<I> + ?Sized + HasInterner<Interner = I>,
  22     I: Interner,
  23 {
  24     fn could_match(&self, interner: &I, db: &dyn UnificationDatabase<I>, other: &T) -> bool {
  25         return Zip::zip_with(
  26             &mut MatchZipper { interner, db },
  27             Variance::Invariant,
  28             self,
  29             other,
  30         )
  31         .is_ok();
  32
  33         struct MatchZipper<'i, I> {
  34             interner: &'i I,
  35             db: &'i dyn UnificationDatabase<I>,
  36         };
  37
  38         impl<'i, I: Interner> Zipper<'i, I> for MatchZipper<'i, I> {
  39             fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> {
  40                 let interner = self.interner;
  41                 let matches = |a: &Substitution<I>, b: &Substitution<I>| {
  42                     a.iter(interner)
  43                         .zip(b.iter(interner))
  44                         .all(|(p_a, p_b)| p_a.could_match(interner, self.db, &p_b))
  45                 };
  46                 let could_match = match (a.kind(interner), b.kind(interner)) {
  47                     (TyKind::Adt(id_a, substitution_a), TyKind::Adt(id_b, substitution_b)) => {
  48                         id_a == id_b
  49                             && self
  50                                 .zip_substs(
  51                                     variance,
  52                                     Some(self.unification_database().adt_variance(*id_a)),
  53                                     substitution_a.as_slice(interner),
  54                                     substitution_b.as_slice(interner),
  55                                 )
  56                                 .is_ok()
  57                     }
  58                     (
  59                         TyKind::AssociatedType(assoc_ty_a, substitution_a),
  60                         TyKind::AssociatedType(assoc_ty_b, substitution_b),
  61                     ) => assoc_ty_a == assoc_ty_b && matches(substitution_a, substitution_b),
  62                     (TyKind::Scalar(scalar_a), TyKind::Scalar(scalar_b)) => scalar_a == scalar_b,
  63                     (TyKind::Str, TyKind::Str) => true,
  64                     (
  65                         TyKind::Tuple(arity_a, substitution_a),
  66                         TyKind::Tuple(arity_b, substitution_b),
  67                     ) => arity_a == arity_b && matches(substitution_a, substitution_b),
  68                     (
  69                         TyKind::OpaqueType(opaque_ty_a, substitution_a),
  70                         TyKind::OpaqueType(opaque_ty_b, substitution_b),
  71                     ) => opaque_ty_a == opaque_ty_b && matches(substitution_a, substitution_b),
  72                     (TyKind::Slice(ty_a), TyKind::Slice(ty_b)) => {
  73                         ty_a.could_match(interner, self.db, ty_b)
  74                     }
  75                     (
  76                         TyKind::FnDef(fn_def_a, substitution_a),
  77                         TyKind::FnDef(fn_def_b, substitution_b),
  78                     ) => {
  79                         fn_def_a == fn_def_b
  80                             && self
  81                                 .zip_substs(
  82                                     variance,
  83                                     Some(self.unification_database().fn_def_variance(*fn_def_a)),
  84                                     substitution_a.as_slice(interner),
  85                                     substitution_b.as_slice(interner),
  86                                 )
  87                                 .is_ok()
  88                     }
  89                     (
  90                         TyKind::Ref(mutability_a, lifetime_a, ty_a),
  91                         TyKind::Ref(mutability_b, lifetime_b, ty_b),
  92                     ) => {
  93                         mutability_a == mutability_b
  94                             && lifetime_a.could_match(interner, self.db, &lifetime_b)
  95                             && ty_a.could_match(interner, self.db, &ty_b)
  96                     }
  97                     (TyKind::Raw(mutability_a, ty_a), TyKind::Raw(mutability_b, ty_b)) => {
  98                         mutability_a == mutability_b && ty_a.could_match(interner, self.db, &ty_b)
  99                     }
 100                     (TyKind::Never, TyKind::Never) => true,
 101                     (TyKind::Array(ty_a, const_a), TyKind::Array(ty_b, const_b)) => {
 102                         ty_a.could_match(interner, self.db, ty_b)
 103                             && const_a.could_match(interner, self.db, const_b)
 104                     }
 105                     (
 106                         TyKind::Closure(id_a, substitution_a),
 107                         TyKind::Closure(id_b, substitution_b),
 108                     ) => id_a == id_b && matches(substitution_a, substitution_b),
 109                     (
 110                         TyKind::Generator(generator_a, substitution_a),
 111                         TyKind::Generator(generator_b, substitution_b),
 112                     ) => {
 113                         generator_a == generator_b
 114                             && self
 115                                 .zip_substs(
 116                                     variance,
 117                                     None,
 118                                     substitution_a.as_slice(interner),
 119                                     substitution_b.as_slice(interner),
 120                                 )
 121                                 .is_ok()
 122                     }
 123                     (
 124                         TyKind::GeneratorWitness(generator_a, substitution_a),
 125                         TyKind::GeneratorWitness(generator_b, substitution_b),
 126                     ) => {
 127                         generator_a == generator_b
 128                             && self
 129                                 .zip_substs(
 130                                     variance,
 131                                     None,
 132                                     substitution_a.as_slice(interner),
 133                                     substitution_b.as_slice(interner),
 134                                 )
 135                                 .is_ok()
 136                     }
 137                     (TyKind::Foreign(foreign_ty_a), TyKind::Foreign(foreign_ty_b)) => {
 138                         foreign_ty_a == foreign_ty_b
 139                     }
 140                     (TyKind::Error, TyKind::Error) => true,
 141
 142                     _ => true,
 143                 };
 144
 145                 if could_match {
 146                     Ok(())
 147                 } else {
 148                     Err(NoSolution)
 149                 }
 150             }
 151
 152             fn zip_lifetimes(
 153                 &mut self,
 154                 variance: Variance,
 155                 _: &Lifetime<I>,
 156                 _: &Lifetime<I>,
 157             ) -> Fallible<()> {
 158                 Ok(())
 159             }
 160
 161             fn zip_consts(
 162                 &mut self,
 163                 variance: Variance,
 164                 _: &Const<I>,
 165                 _: &Const<I>,
 166             ) -> Fallible<()> {
 167                 Ok(())
 168             }
 169
 170             fn zip_binders<T>(
 171                 &mut self,
 172                 variance: Variance,
 173                 a: &Binders<T>,
 174                 b: &Binders<T>,
 175             ) -> Fallible<()>
 176             where
 177                 T: HasInterner + Zip<I>,
 178             {
 179                 Zip::zip_with(self, variance, &a.value, &b.value)
 180             }
 181
 182             fn interner(&self) -> &'i I {
 183                 self.interner
 184             }
 185
 186             fn unification_database(&self) -> &dyn UnificationDatabase<I> {
 187                 self.db
 188             }
 189         }
 190     }
 191 }
 192
 193 impl<I: Interner> CouldMatch<DomainGoal<I>> for ProgramClauseData<I> {
 194     fn could_match(
 195         &self,
 196         interner: &I,
 197         db: &dyn UnificationDatabase<I>,
 198         other: &DomainGoal<I>,
 199     ) -> bool {
 200         self.0.value.consequence.could_match(interner, db, other)
 201     }
 202 }
 203
 204 impl<I: Interner> CouldMatch<DomainGoal<I>> for ProgramClause<I> {
 205     fn could_match(
 206         &self,
 207         interner: &I,
 208         db: &dyn UnificationDatabase<I>,
 209         other: &DomainGoal<I>,
 210     ) -> bool {
 211         self.data(interner).could_match(interner, db, other)
 212     }
 213 }