compiler/rustc_infer/src/infer/resolve.rs

   1 use super::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
   2 use super::{FixupError, FixupResult, InferCtxt, Span};
   3 use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
   4 use rustc_middle::ty::fold::{FallibleTypeFolder, TypeFolder, TypeSuperFoldable};
   5 use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitableExt, TypeVisitor};
   6 use rustc_middle::ty::{self, Const, InferConst, Ty, TyCtxt, TypeFoldable};
   7
   8 use std::ops::ControlFlow;
   9
  10 ///////////////////////////////////////////////////////////////////////////
  11 // OPPORTUNISTIC VAR RESOLVER
  12
  13 /// The opportunistic resolver can be used at any time. It simply replaces
  14 /// type/const variables that have been unified with the things they have
  15 /// been unified with (similar to `shallow_resolve`, but deep). This is
  16 /// useful for printing messages etc but also required at various
  17 /// points for correctness.
  18 pub struct OpportunisticVarResolver<'a, 'tcx> {
  19     // The shallow resolver is used to resolve inference variables at every
  20     // level of the type.
  21     shallow_resolver: crate::infer::ShallowResolver<'a, 'tcx>,
  22 }
  23
  24 impl<'a, 'tcx> OpportunisticVarResolver<'a, 'tcx> {
  25     #[inline]
  26     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
  27         OpportunisticVarResolver { shallow_resolver: crate::infer::ShallowResolver { infcx } }
  28     }
  29 }
  30
  31 impl<'a, 'tcx> TypeFolder<TyCtxt<'tcx>> for OpportunisticVarResolver<'a, 'tcx> {
  32     fn interner(&self) -> TyCtxt<'tcx> {
  33         TypeFolder::interner(&self.shallow_resolver)
  34     }
  35
  36     #[inline]
  37     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  38         if !t.has_non_region_infer() {
  39             t // micro-optimize -- if there is nothing in this type that this fold affects...
  40         } else {
  41             let t = self.shallow_resolver.fold_ty(t);
  42             t.super_fold_with(self)
  43         }
  44     }
  45
  46     fn fold_const(&mut self, ct: Const<'tcx>) -> Const<'tcx> {
  47         if !ct.has_non_region_infer() {
  48             ct // micro-optimize -- if there is nothing in this const that this fold affects...
  49         } else {
  50             let ct = self.shallow_resolver.fold_const(ct);
  51             ct.super_fold_with(self)
  52         }
  53     }
  54 }
  55
  56 /// The opportunistic region resolver opportunistically resolves regions
  57 /// variables to the variable with the least variable id. It is used when
  58 /// normalizing projections to avoid hitting the recursion limit by creating
  59 /// many versions of a predicate for types that in the end have to unify.
  60 ///
  61 /// If you want to resolve type and const variables as well, call
  62 /// [InferCtxt::resolve_vars_if_possible] first.
  63 pub struct OpportunisticRegionResolver<'a, 'tcx> {
  64     infcx: &'a InferCtxt<'tcx>,
  65 }
  66
  67 impl<'a, 'tcx> OpportunisticRegionResolver<'a, 'tcx> {
  68     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
  69         OpportunisticRegionResolver { infcx }
  70     }
  71 }
  72
  73 impl<'a, 'tcx> TypeFolder<TyCtxt<'tcx>> for OpportunisticRegionResolver<'a, 'tcx> {
  74     fn interner(&self) -> TyCtxt<'tcx> {
  75         self.infcx.tcx
  76     }
  77
  78     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  79         if !t.has_infer_regions() {
  80             t // micro-optimize -- if there is nothing in this type that this fold affects...
  81         } else {
  82             t.super_fold_with(self)
  83         }
  84     }
  85
  86     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
  87         match *r {
  88             ty::ReVar(vid) => self
  89                 .infcx
  90                 .inner
  91                 .borrow_mut()
  92                 .unwrap_region_constraints()
  93                 .opportunistic_resolve_var(TypeFolder::interner(self), vid),
  94             _ => r,
  95         }
  96     }
  97
  98     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
  99         if !ct.has_infer_regions() {
 100             ct // micro-optimize -- if there is nothing in this const that this fold affects...
 101         } else {
 102             ct.super_fold_with(self)
 103         }
 104     }
 105 }
 106
 107 ///////////////////////////////////////////////////////////////////////////
 108 // UNRESOLVED TYPE FINDER
 109
 110 /// The unresolved type **finder** walks a type searching for
 111 /// type variables that don't yet have a value. The first unresolved type is stored.
 112 /// It does not construct the fully resolved type (which might
 113 /// involve some hashing and so forth).
 114 pub struct UnresolvedTypeOrConstFinder<'a, 'tcx> {
 115     infcx: &'a InferCtxt<'tcx>,
 116 }
 117
 118 impl<'a, 'tcx> UnresolvedTypeOrConstFinder<'a, 'tcx> {
 119     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
 120         UnresolvedTypeOrConstFinder { infcx }
 121     }
 122 }
 123
 124 impl<'a, 'tcx> TypeVisitor<TyCtxt<'tcx>> for UnresolvedTypeOrConstFinder<'a, 'tcx> {
 125     type BreakTy = (ty::Term<'tcx>, Option<Span>);
 126     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 127         let t = self.infcx.shallow_resolve(t);
 128         if let ty::Infer(infer_ty) = *t.kind() {
 129             // Since we called `shallow_resolve` above, this must
 130             // be an (as yet...) unresolved inference variable.
 131             let ty_var_span = if let ty::TyVar(ty_vid) = infer_ty {
 132                 let mut inner = self.infcx.inner.borrow_mut();
 133                 let ty_vars = &inner.type_variables();
 134                 if let TypeVariableOrigin {
 135                     kind: TypeVariableOriginKind::TypeParameterDefinition(_, _),
 136                     span,
 137                 } = ty_vars.var_origin(ty_vid)
 138                 {
 139                     Some(span)
 140                 } else {
 141                     None
 142                 }
 143             } else {
 144                 None
 145             };
 146             ControlFlow::Break((t.into(), ty_var_span))
 147         } else if !t.has_non_region_infer() {
 148             // All const/type variables in inference types must already be resolved,
 149             // no need to visit the contents.
 150             ControlFlow::Continue(())
 151         } else {
 152             // Otherwise, keep visiting.
 153             t.super_visit_with(self)
 154         }
 155     }
 156
 157     fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 158         let ct = self.infcx.shallow_resolve(ct);
 159         if let ty::ConstKind::Infer(i) = ct.kind() {
 160             // Since we called `shallow_resolve` above, this must
 161             // be an (as yet...) unresolved inference variable.
 162             let ct_var_span = if let ty::InferConst::Var(vid) = i {
 163                 let mut inner = self.infcx.inner.borrow_mut();
 164                 let ct_vars = &mut inner.const_unification_table();
 165                 if let ConstVariableOrigin {
 166                     span,
 167                     kind: ConstVariableOriginKind::ConstParameterDefinition(_, _),
 168                 } = ct_vars.probe_value(vid).origin
 169                 {
 170                     Some(span)
 171                 } else {
 172                     None
 173                 }
 174             } else {
 175                 None
 176             };
 177             ControlFlow::Break((ct.into(), ct_var_span))
 178         } else if !ct.has_non_region_infer() {
 179             // All const/type variables in inference types must already be resolved,
 180             // no need to visit the contents.
 181             ControlFlow::Continue(())
 182         } else {
 183             // Otherwise, keep visiting.
 184             ct.super_visit_with(self)
 185         }
 186     }
 187 }
 188
 189 ///////////////////////////////////////////////////////////////////////////
 190 // FULL TYPE RESOLUTION
 191
 192 /// Full type resolution replaces all type and region variables with
 193 /// their concrete results. If any variable cannot be replaced (never unified, etc)
 194 /// then an `Err` result is returned.
 195 pub fn fully_resolve<'tcx, T>(infcx: &InferCtxt<'tcx>, value: T) -> FixupResult<T>
 196 where
 197     T: TypeFoldable<TyCtxt<'tcx>>,
 198 {
 199     value.try_fold_with(&mut FullTypeResolver { infcx })
 200 }
 201
 202 // N.B. This type is not public because the protocol around checking the
 203 // `err` field is not enforceable otherwise.
 204 struct FullTypeResolver<'a, 'tcx> {
 205     infcx: &'a InferCtxt<'tcx>,
 206 }
 207
 208 impl<'a, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for FullTypeResolver<'a, 'tcx> {
 209     type Error = FixupError;
 210
 211     fn interner(&self) -> TyCtxt<'tcx> {
 212         self.infcx.tcx
 213     }
 214
 215     fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 216         if !t.has_infer() {
 217             Ok(t) // micro-optimize -- if there is nothing in this type that this fold affects...
 218         } else {
 219             let t = self.infcx.shallow_resolve(t);
 220             match *t.kind() {
 221                 ty::Infer(ty::TyVar(vid)) => Err(FixupError::UnresolvedTy(vid)),
 222                 ty::Infer(ty::IntVar(vid)) => Err(FixupError::UnresolvedIntTy(vid)),
 223                 ty::Infer(ty::FloatVar(vid)) => Err(FixupError::UnresolvedFloatTy(vid)),
 224                 ty::Infer(_) => {
 225                     bug!("Unexpected type in full type resolver: {:?}", t);
 226                 }
 227                 _ => t.try_super_fold_with(self),
 228             }
 229         }
 230     }
 231
 232     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 233         match *r {
 234             ty::ReVar(_) => Ok(self
 235                 .infcx
 236                 .lexical_region_resolutions
 237                 .borrow()
 238                 .as_ref()
 239                 .expect("region resolution not performed")
 240                 .resolve_region(self.infcx.tcx, r)),
 241             _ => Ok(r),
 242         }
 243     }
 244
 245     fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> {
 246         if !c.has_infer() {
 247             Ok(c) // micro-optimize -- if there is nothing in this const that this fold affects...
 248         } else {
 249             let c = self.infcx.shallow_resolve(c);
 250             match c.kind() {
 251                 ty::ConstKind::Infer(InferConst::Var(vid)) => {
 252                     return Err(FixupError::UnresolvedConst(vid));
 253                 }
 254                 ty::ConstKind::Infer(InferConst::Fresh(_)) => {
 255                     bug!("Unexpected const in full const resolver: {:?}", c);
 256                 }
 257                 _ => {}
 258             }
 259             c.try_super_fold_with(self)
 260         }
 261     }
 262 }
 263
 264 ///////////////////////////////////////////////////////////////////////////
 265 // EAGER RESOLUTION
 266
 267 /// Resolves ty, region, and const vars to their inferred values or their root vars.
 268 pub struct EagerResolver<'a, 'tcx> {
 269     infcx: &'a InferCtxt<'tcx>,
 270 }
 271
 272 impl<'a, 'tcx> EagerResolver<'a, 'tcx> {
 273     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
 274         EagerResolver { infcx }
 275     }
 276 }
 277
 278 impl<'tcx> TypeFolder<TyCtxt<'tcx>> for EagerResolver<'_, 'tcx> {
 279     fn interner(&self) -> TyCtxt<'tcx> {
 280         self.infcx.tcx
 281     }
 282
 283     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 284         match *t.kind() {
 285             ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) {
 286                 Ok(t) => t.fold_with(self),
 287                 Err(_) => Ty::new_var(self.infcx.tcx, self.infcx.root_var(vid)),
 288             },
 289             ty::Infer(ty::IntVar(vid)) => self.infcx.opportunistic_resolve_int_var(vid),
 290             ty::Infer(ty::FloatVar(vid)) => self.infcx.opportunistic_resolve_float_var(vid),
 291             _ => {
 292                 if t.has_infer() {
 293                     t.super_fold_with(self)
 294                 } else {
 295                     t
 296                 }
 297             }
 298         }
 299     }
 300
 301     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 302         match *r {
 303             ty::ReVar(vid) => self
 304                 .infcx
 305                 .inner
 306                 .borrow_mut()
 307                 .unwrap_region_constraints()
 308                 .opportunistic_resolve_var(self.infcx.tcx, vid),
 309             _ => r,
 310         }
 311     }
 312
 313     fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> {
 314         match c.kind() {
 315             ty::ConstKind::Infer(ty::InferConst::Var(vid)) => {
 316                 // FIXME: we need to fold the ty too, I think.
 317                 match self.infcx.probe_const_var(vid) {
 318                     Ok(c) => c.fold_with(self),
 319                     Err(_) => {
 320                         ty::Const::new_var(self.infcx.tcx, self.infcx.root_const_var(vid), c.ty())
 321                     }
 322                 }
 323             }
 324             ty::ConstKind::Infer(ty::InferConst::EffectVar(vid)) => {
 325                 debug_assert_eq!(c.ty(), self.infcx.tcx.types.bool);
 326                 match self.infcx.probe_effect_var(vid) {
 327                     Some(c) => c.as_const(self.infcx.tcx),
 328                     None => ty::Const::new_infer(
 329                         self.infcx.tcx,
 330                         ty::InferConst::EffectVar(self.infcx.root_effect_var(vid)),
 331                         self.infcx.tcx.types.bool,
 332                     ),
 333                 }
 334             }
 335             _ => {
 336                 if c.has_infer() {
 337                     c.super_fold_with(self)
 338                 } else {
 339                     c
 340                 }
 341             }
 342         }
 343     }
 344 }