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     infcx: &'a InferCtxt<'tcx>,
  20 }
  21
  22 impl<'a, 'tcx> OpportunisticVarResolver<'a, 'tcx> {
  23     #[inline]
  24     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
  25         OpportunisticVarResolver { infcx }
  26     }
  27 }
  28
  29 impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticVarResolver<'a, 'tcx> {
  30     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
  31         self.infcx.tcx
  32     }
  33
  34     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  35         if !t.has_non_region_infer() {
  36             t // micro-optimize -- if there is nothing in this type that this fold affects...
  37         } else {
  38             let t = self.infcx.shallow_resolve(t);
  39             t.super_fold_with(self)
  40         }
  41     }
  42
  43     fn fold_const(&mut self, ct: Const<'tcx>) -> Const<'tcx> {
  44         if !ct.has_non_region_infer() {
  45             ct // micro-optimize -- if there is nothing in this const that this fold affects...
  46         } else {
  47             let ct = self.infcx.shallow_resolve(ct);
  48             ct.super_fold_with(self)
  49         }
  50     }
  51 }
  52
  53 /// The opportunistic region resolver opportunistically resolves regions
  54 /// variables to the variable with the least variable id. It is used when
  55 /// normalizing projections to avoid hitting the recursion limit by creating
  56 /// many versions of a predicate for types that in the end have to unify.
  57 ///
  58 /// If you want to resolve type and const variables as well, call
  59 /// [InferCtxt::resolve_vars_if_possible] first.
  60 pub struct OpportunisticRegionResolver<'a, 'tcx> {
  61     infcx: &'a InferCtxt<'tcx>,
  62 }
  63
  64 impl<'a, 'tcx> OpportunisticRegionResolver<'a, 'tcx> {
  65     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
  66         OpportunisticRegionResolver { infcx }
  67     }
  68 }
  69
  70 impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticRegionResolver<'a, 'tcx> {
  71     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
  72         self.infcx.tcx
  73     }
  74
  75     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  76         if !t.has_infer_regions() {
  77             t // micro-optimize -- if there is nothing in this type that this fold affects...
  78         } else {
  79             t.super_fold_with(self)
  80         }
  81     }
  82
  83     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
  84         match *r {
  85             ty::ReVar(rid) => {
  86                 let resolved = self
  87                     .infcx
  88                     .inner
  89                     .borrow_mut()
  90                     .unwrap_region_constraints()
  91                     .opportunistic_resolve_var(rid);
  92                 TypeFolder::tcx(self).reuse_or_mk_region(r, ty::ReVar(resolved))
  93             }
  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<'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<'tcx, T>
 196 where
 197     T: TypeFoldable<'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<'tcx> for FullTypeResolver<'a, 'tcx> {
 209     type Error = FixupError<'tcx>;
 210
 211     fn tcx<'b>(&'b 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.needs_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.needs_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 }