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::mir;
   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     fn fold_mir_const(&mut self, constant: mir::ConstantKind<'tcx>) -> mir::ConstantKind<'tcx> {
  53         constant.super_fold_with(self)
  54     }
  55 }
  56
  57 /// The opportunistic region resolver opportunistically resolves regions
  58 /// variables to the variable with the least variable id. It is used when
  59 /// normalizing projections to avoid hitting the recursion limit by creating
  60 /// many versions of a predicate for types that in the end have to unify.
  61 ///
  62 /// If you want to resolve type and const variables as well, call
  63 /// [InferCtxt::resolve_vars_if_possible] first.
  64 pub struct OpportunisticRegionResolver<'a, 'tcx> {
  65     infcx: &'a InferCtxt<'tcx>,
  66 }
  67
  68 impl<'a, 'tcx> OpportunisticRegionResolver<'a, 'tcx> {
  69     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
  70         OpportunisticRegionResolver { infcx }
  71     }
  72 }
  73
  74 impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticRegionResolver<'a, 'tcx> {
  75     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
  76         self.infcx.tcx
  77     }
  78
  79     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  80         if !t.has_infer_regions() {
  81             t // micro-optimize -- if there is nothing in this type that this fold affects...
  82         } else {
  83             t.super_fold_with(self)
  84         }
  85     }
  86
  87     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
  88         match *r {
  89             ty::ReVar(rid) => {
  90                 let resolved = self
  91                     .infcx
  92                     .inner
  93                     .borrow_mut()
  94                     .unwrap_region_constraints()
  95                     .opportunistic_resolve_var(rid);
  96                 TypeFolder::tcx(self).reuse_or_mk_region(r, ty::ReVar(resolved))
  97             }
  98             _ => r,
  99         }
 100     }
 101
 102     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 103         if !ct.has_infer_regions() {
 104             ct // micro-optimize -- if there is nothing in this const that this fold affects...
 105         } else {
 106             ct.super_fold_with(self)
 107         }
 108     }
 109 }
 110
 111 ///////////////////////////////////////////////////////////////////////////
 112 // UNRESOLVED TYPE FINDER
 113
 114 /// The unresolved type **finder** walks a type searching for
 115 /// type variables that don't yet have a value. The first unresolved type is stored.
 116 /// It does not construct the fully resolved type (which might
 117 /// involve some hashing and so forth).
 118 pub struct UnresolvedTypeFinder<'a, 'tcx> {
 119     infcx: &'a InferCtxt<'tcx>,
 120 }
 121
 122 impl<'a, 'tcx> UnresolvedTypeFinder<'a, 'tcx> {
 123     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
 124         UnresolvedTypeFinder { infcx }
 125     }
 126 }
 127
 128 impl<'a, 'tcx> TypeVisitor<'tcx> for UnresolvedTypeFinder<'a, 'tcx> {
 129     type BreakTy = (Ty<'tcx>, Option<Span>);
 130     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 131         let t = self.infcx.shallow_resolve(t);
 132         if t.has_infer_types() {
 133             if let ty::Infer(infer_ty) = *t.kind() {
 134                 // Since we called `shallow_resolve` above, this must
 135                 // be an (as yet...) unresolved inference variable.
 136                 let ty_var_span = if let ty::TyVar(ty_vid) = infer_ty {
 137                     let mut inner = self.infcx.inner.borrow_mut();
 138                     let ty_vars = &inner.type_variables();
 139                     if let TypeVariableOrigin {
 140                         kind: TypeVariableOriginKind::TypeParameterDefinition(_, _),
 141                         span,
 142                     } = *ty_vars.var_origin(ty_vid)
 143                     {
 144                         Some(span)
 145                     } else {
 146                         None
 147                     }
 148                 } else {
 149                     None
 150                 };
 151                 ControlFlow::Break((t, ty_var_span))
 152             } else {
 153                 // Otherwise, visit its contents.
 154                 t.super_visit_with(self)
 155             }
 156         } else {
 157             // All type variables in inference types must already be resolved,
 158             // - no need to visit the contents, continue visiting.
 159             ControlFlow::CONTINUE
 160         }
 161     }
 162 }
 163
 164 ///////////////////////////////////////////////////////////////////////////
 165 // FULL TYPE RESOLUTION
 166
 167 /// Full type resolution replaces all type and region variables with
 168 /// their concrete results. If any variable cannot be replaced (never unified, etc)
 169 /// then an `Err` result is returned.
 170 pub fn fully_resolve<'tcx, T>(infcx: &InferCtxt<'tcx>, value: T) -> FixupResult<'tcx, T>
 171 where
 172     T: TypeFoldable<'tcx>,
 173 {
 174     value.try_fold_with(&mut FullTypeResolver { infcx })
 175 }
 176
 177 // N.B. This type is not public because the protocol around checking the
 178 // `err` field is not enforceable otherwise.
 179 struct FullTypeResolver<'a, 'tcx> {
 180     infcx: &'a InferCtxt<'tcx>,
 181 }
 182
 183 impl<'a, 'tcx> FallibleTypeFolder<'tcx> for FullTypeResolver<'a, 'tcx> {
 184     type Error = FixupError<'tcx>;
 185
 186     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 187         self.infcx.tcx
 188     }
 189
 190     fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 191         if !t.needs_infer() {
 192             Ok(t) // micro-optimize -- if there is nothing in this type that this fold affects...
 193         } else {
 194             let t = self.infcx.shallow_resolve(t);
 195             match *t.kind() {
 196                 ty::Infer(ty::TyVar(vid)) => Err(FixupError::UnresolvedTy(vid)),
 197                 ty::Infer(ty::IntVar(vid)) => Err(FixupError::UnresolvedIntTy(vid)),
 198                 ty::Infer(ty::FloatVar(vid)) => Err(FixupError::UnresolvedFloatTy(vid)),
 199                 ty::Infer(_) => {
 200                     bug!("Unexpected type in full type resolver: {:?}", t);
 201                 }
 202                 _ => t.try_super_fold_with(self),
 203             }
 204         }
 205     }
 206
 207     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 208         match *r {
 209             ty::ReVar(_) => Ok(self
 210                 .infcx
 211                 .lexical_region_resolutions
 212                 .borrow()
 213                 .as_ref()
 214                 .expect("region resolution not performed")
 215                 .resolve_region(self.infcx.tcx, r)),
 216             _ => Ok(r),
 217         }
 218     }
 219
 220     fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> {
 221         if !c.needs_infer() {
 222             Ok(c) // micro-optimize -- if there is nothing in this const that this fold affects...
 223         } else {
 224             let c = self.infcx.shallow_resolve(c);
 225             match c.kind() {
 226                 ty::ConstKind::Infer(InferConst::Var(vid)) => {
 227                     return Err(FixupError::UnresolvedConst(vid));
 228                 }
 229                 ty::ConstKind::Infer(InferConst::Fresh(_)) => {
 230                     bug!("Unexpected const in full const resolver: {:?}", c);
 231                 }
 232                 _ => {}
 233             }
 234             c.try_super_fold_with(self)
 235         }
 236     }
 237 }