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, TypeVisitor};
   6 use rustc_middle::ty::{self, Const, InferConst, Ty, TyCtxt, TypeFoldable, TypeVisitable};
   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<'tcx> for OpportunisticVarResolver<'a, 'tcx> {
  32     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
  33         TypeFolder::tcx(&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<'tcx> for OpportunisticRegionResolver<'a, 'tcx> {
  74     fn tcx<'b>(&'b 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(rid) => {
  89                 let resolved = self
  90                     .infcx
  91                     .inner
  92                     .borrow_mut()
  93                     .unwrap_region_constraints()
  94                     .opportunistic_resolve_var(rid);
  95                 TypeFolder::tcx(self).reuse_or_mk_region(r, ty::ReVar(resolved))
  96             }
  97             _ => r,
  98         }
  99     }
 100
 101     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 102         if !ct.has_infer_regions() {
 103             ct // micro-optimize -- if there is nothing in this const that this fold affects...
 104         } else {
 105             ct.super_fold_with(self)
 106         }
 107     }
 108 }
 109
 110 ///////////////////////////////////////////////////////////////////////////
 111 // UNRESOLVED TYPE FINDER
 112
 113 /// The unresolved type **finder** walks a type searching for
 114 /// type variables that don't yet have a value. The first unresolved type is stored.
 115 /// It does not construct the fully resolved type (which might
 116 /// involve some hashing and so forth).
 117 pub struct UnresolvedTypeOrConstFinder<'a, 'tcx> {
 118     infcx: &'a InferCtxt<'tcx>,
 119 }
 120
 121 impl<'a, 'tcx> UnresolvedTypeOrConstFinder<'a, 'tcx> {
 122     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
 123         UnresolvedTypeOrConstFinder { infcx }
 124     }
 125 }
 126
 127 impl<'a, 'tcx> TypeVisitor<'tcx> for UnresolvedTypeOrConstFinder<'a, 'tcx> {
 128     type BreakTy = (ty::Term<'tcx>, Option<Span>);
 129     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 130         let t = self.infcx.shallow_resolve(t);
 131         if let ty::Infer(infer_ty) = *t.kind() {
 132             // Since we called `shallow_resolve` above, this must
 133             // be an (as yet...) unresolved inference variable.
 134             let ty_var_span = if let ty::TyVar(ty_vid) = infer_ty {
 135                 let mut inner = self.infcx.inner.borrow_mut();
 136                 let ty_vars = &inner.type_variables();
 137                 if let TypeVariableOrigin {
 138                     kind: TypeVariableOriginKind::TypeParameterDefinition(_, _),
 139                     span,
 140                 } = *ty_vars.var_origin(ty_vid)
 141                 {
 142                     Some(span)
 143                 } else {
 144                     None
 145                 }
 146             } else {
 147                 None
 148             };
 149             ControlFlow::Break((t.into(), ty_var_span))
 150         } else if !t.has_non_region_infer() {
 151             // All const/type variables in inference types must already be resolved,
 152             // no need to visit the contents.
 153             ControlFlow::Continue(())
 154         } else {
 155             // Otherwise, keep visiting.
 156             t.super_visit_with(self)
 157         }
 158     }
 159
 160     fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 161         let ct = self.infcx.shallow_resolve(ct);
 162         if let ty::ConstKind::Infer(i) = ct.kind() {
 163             // Since we called `shallow_resolve` above, this must
 164             // be an (as yet...) unresolved inference variable.
 165             let ct_var_span = if let ty::InferConst::Var(vid) = i {
 166                 let mut inner = self.infcx.inner.borrow_mut();
 167                 let ct_vars = &mut inner.const_unification_table();
 168                 if let ConstVariableOrigin {
 169                     span,
 170                     kind: ConstVariableOriginKind::ConstParameterDefinition(_, _),
 171                 } = ct_vars.probe_value(vid).origin
 172                 {
 173                     Some(span)
 174                 } else {
 175                     None
 176                 }
 177             } else {
 178                 None
 179             };
 180             ControlFlow::Break((ct.into(), ct_var_span))
 181         } else if !ct.has_non_region_infer() {
 182             // All const/type variables in inference types must already be resolved,
 183             // no need to visit the contents.
 184             ControlFlow::Continue(())
 185         } else {
 186             // Otherwise, keep visiting.
 187             ct.super_visit_with(self)
 188         }
 189     }
 190 }
 191
 192 ///////////////////////////////////////////////////////////////////////////
 193 // FULL TYPE RESOLUTION
 194
 195 /// Full type resolution replaces all type and region variables with
 196 /// their concrete results. If any variable cannot be replaced (never unified, etc)
 197 /// then an `Err` result is returned.
 198 pub fn fully_resolve<'tcx, T>(infcx: &InferCtxt<'tcx>, value: T) -> FixupResult<'tcx, T>
 199 where
 200     T: TypeFoldable<'tcx>,
 201 {
 202     value.try_fold_with(&mut FullTypeResolver { infcx })
 203 }
 204
 205 // N.B. This type is not public because the protocol around checking the
 206 // `err` field is not enforceable otherwise.
 207 struct FullTypeResolver<'a, 'tcx> {
 208     infcx: &'a InferCtxt<'tcx>,
 209 }
 210
 211 impl<'a, 'tcx> FallibleTypeFolder<'tcx> for FullTypeResolver<'a, 'tcx> {
 212     type Error = FixupError<'tcx>;
 213
 214     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 215         self.infcx.tcx
 216     }
 217
 218     fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 219         if !t.needs_infer() {
 220             Ok(t) // micro-optimize -- if there is nothing in this type that this fold affects...
 221         } else {
 222             let t = self.infcx.shallow_resolve(t);
 223             match *t.kind() {
 224                 ty::Infer(ty::TyVar(vid)) => Err(FixupError::UnresolvedTy(vid)),
 225                 ty::Infer(ty::IntVar(vid)) => Err(FixupError::UnresolvedIntTy(vid)),
 226                 ty::Infer(ty::FloatVar(vid)) => Err(FixupError::UnresolvedFloatTy(vid)),
 227                 ty::Infer(_) => {
 228                     bug!("Unexpected type in full type resolver: {:?}", t);
 229                 }
 230                 _ => t.try_super_fold_with(self),
 231             }
 232         }
 233     }
 234
 235     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 236         match *r {
 237             ty::ReVar(_) => Ok(self
 238                 .infcx
 239                 .lexical_region_resolutions
 240                 .borrow()
 241                 .as_ref()
 242                 .expect("region resolution not performed")
 243                 .resolve_region(self.infcx.tcx, r)),
 244             _ => Ok(r),
 245         }
 246     }
 247
 248     fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> {
 249         if !c.needs_infer() {
 250             Ok(c) // micro-optimize -- if there is nothing in this const that this fold affects...
 251         } else {
 252             let c = self.infcx.shallow_resolve(c);
 253             match c.kind() {
 254                 ty::ConstKind::Infer(InferConst::Var(vid)) => {
 255                     return Err(FixupError::UnresolvedConst(vid));
 256                 }
 257                 ty::ConstKind::Infer(InferConst::Fresh(_)) => {
 258                     bug!("Unexpected const in full const resolver: {:?}", c);
 259                 }
 260                 _ => {}
 261             }
 262             c.try_super_fold_with(self)
 263         }
 264     }
 265 }