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::ty::fold::{FallibleTypeFolder, TypeFolder, TypeSuperFoldable};
   4 use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitor};
   5 use rustc_middle::ty::{self, Const, InferConst, Ty, TyCtxt, TypeFoldable, TypeVisitable};
   6
   7 use std::ops::ControlFlow;
   8
   9 ///////////////////////////////////////////////////////////////////////////
  10 // OPPORTUNISTIC VAR RESOLVER
  11
  12 /// The opportunistic resolver can be used at any time. It simply replaces
  13 /// type/const variables that have been unified with the things they have
  14 /// been unified with (similar to `shallow_resolve`, but deep). This is
  15 /// useful for printing messages etc but also required at various
  16 /// points for correctness.
  17 pub struct OpportunisticVarResolver<'a, 'tcx> {
  18     infcx: &'a InferCtxt<'tcx>,
  19 }
  20
  21 impl<'a, 'tcx> OpportunisticVarResolver<'a, 'tcx> {
  22     #[inline]
  23     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
  24         OpportunisticVarResolver { infcx }
  25     }
  26 }
  27
  28 impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticVarResolver<'a, 'tcx> {
  29     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
  30         self.infcx.tcx
  31     }
  32
  33     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  34         if !t.has_non_region_infer() {
  35             t // micro-optimize -- if there is nothing in this type that this fold affects...
  36         } else {
  37             let t = self.infcx.shallow_resolve(t);
  38             t.super_fold_with(self)
  39         }
  40     }
  41
  42     fn fold_const(&mut self, ct: Const<'tcx>) -> Const<'tcx> {
  43         if !ct.has_non_region_infer() {
  44             ct // micro-optimize -- if there is nothing in this const that this fold affects...
  45         } else {
  46             let ct = self.infcx.shallow_resolve(ct);
  47             ct.super_fold_with(self)
  48         }
  49     }
  50 }
  51
  52 /// The opportunistic region resolver opportunistically resolves regions
  53 /// variables to the variable with the least variable id. It is used when
  54 /// normalizing projections to avoid hitting the recursion limit by creating
  55 /// many versions of a predicate for types that in the end have to unify.
  56 ///
  57 /// If you want to resolve type and const variables as well, call
  58 /// [InferCtxt::resolve_vars_if_possible] first.
  59 pub struct OpportunisticRegionResolver<'a, 'tcx> {
  60     infcx: &'a InferCtxt<'tcx>,
  61 }
  62
  63 impl<'a, 'tcx> OpportunisticRegionResolver<'a, 'tcx> {
  64     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
  65         OpportunisticRegionResolver { infcx }
  66     }
  67 }
  68
  69 impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticRegionResolver<'a, 'tcx> {
  70     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
  71         self.infcx.tcx
  72     }
  73
  74     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  75         if !t.has_infer_regions() {
  76             t // micro-optimize -- if there is nothing in this type that this fold affects...
  77         } else {
  78             t.super_fold_with(self)
  79         }
  80     }
  81
  82     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
  83         match *r {
  84             ty::ReVar(rid) => {
  85                 let resolved = self
  86                     .infcx
  87                     .inner
  88                     .borrow_mut()
  89                     .unwrap_region_constraints()
  90                     .opportunistic_resolve_var(rid);
  91                 TypeFolder::tcx(self).reuse_or_mk_region(r, ty::ReVar(resolved))
  92             }
  93             _ => r,
  94         }
  95     }
  96
  97     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
  98         if !ct.has_infer_regions() {
  99             ct // micro-optimize -- if there is nothing in this const that this fold affects...
 100         } else {
 101             ct.super_fold_with(self)
 102         }
 103     }
 104 }
 105
 106 ///////////////////////////////////////////////////////////////////////////
 107 // UNRESOLVED TYPE FINDER
 108
 109 /// The unresolved type **finder** walks a type searching for
 110 /// type variables that don't yet have a value. The first unresolved type is stored.
 111 /// It does not construct the fully resolved type (which might
 112 /// involve some hashing and so forth).
 113 pub struct UnresolvedTypeFinder<'a, 'tcx> {
 114     infcx: &'a InferCtxt<'tcx>,
 115 }
 116
 117 impl<'a, 'tcx> UnresolvedTypeFinder<'a, 'tcx> {
 118     pub fn new(infcx: &'a InferCtxt<'tcx>) -> Self {
 119         UnresolvedTypeFinder { infcx }
 120     }
 121 }
 122
 123 impl<'a, 'tcx> TypeVisitor<'tcx> for UnresolvedTypeFinder<'a, 'tcx> {
 124     type BreakTy = (Ty<'tcx>, Option<Span>);
 125     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 126         let t = self.infcx.shallow_resolve(t);
 127         if t.has_infer_types() {
 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, ty_var_span))
 147             } else {
 148                 // Otherwise, visit its contents.
 149                 t.super_visit_with(self)
 150             }
 151         } else {
 152             // All type variables in inference types must already be resolved,
 153             // - no need to visit the contents, continue visiting.
 154             ControlFlow::CONTINUE
 155         }
 156     }
 157 }
 158
 159 ///////////////////////////////////////////////////////////////////////////
 160 // FULL TYPE RESOLUTION
 161
 162 /// Full type resolution replaces all type and region variables with
 163 /// their concrete results. If any variable cannot be replaced (never unified, etc)
 164 /// then an `Err` result is returned.
 165 pub fn fully_resolve<'tcx, T>(infcx: &InferCtxt<'tcx>, value: T) -> FixupResult<'tcx, T>
 166 where
 167     T: TypeFoldable<'tcx>,
 168 {
 169     value.try_fold_with(&mut FullTypeResolver { infcx })
 170 }
 171
 172 // N.B. This type is not public because the protocol around checking the
 173 // `err` field is not enforceable otherwise.
 174 struct FullTypeResolver<'a, 'tcx> {
 175     infcx: &'a InferCtxt<'tcx>,
 176 }
 177
 178 impl<'a, 'tcx> FallibleTypeFolder<'tcx> for FullTypeResolver<'a, 'tcx> {
 179     type Error = FixupError<'tcx>;
 180
 181     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 182         self.infcx.tcx
 183     }
 184
 185     fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 186         if !t.needs_infer() {
 187             Ok(t) // micro-optimize -- if there is nothing in this type that this fold affects...
 188         } else {
 189             let t = self.infcx.shallow_resolve(t);
 190             match *t.kind() {
 191                 ty::Infer(ty::TyVar(vid)) => Err(FixupError::UnresolvedTy(vid)),
 192                 ty::Infer(ty::IntVar(vid)) => Err(FixupError::UnresolvedIntTy(vid)),
 193                 ty::Infer(ty::FloatVar(vid)) => Err(FixupError::UnresolvedFloatTy(vid)),
 194                 ty::Infer(_) => {
 195                     bug!("Unexpected type in full type resolver: {:?}", t);
 196                 }
 197                 _ => t.try_super_fold_with(self),
 198             }
 199         }
 200     }
 201
 202     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 203         match *r {
 204             ty::ReVar(_) => Ok(self
 205                 .infcx
 206                 .lexical_region_resolutions
 207                 .borrow()
 208                 .as_ref()
 209                 .expect("region resolution not performed")
 210                 .resolve_region(self.infcx.tcx, r)),
 211             _ => Ok(r),
 212         }
 213     }
 214
 215     fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> {
 216         if !c.needs_infer() {
 217             Ok(c) // micro-optimize -- if there is nothing in this const that this fold affects...
 218         } else {
 219             let c = self.infcx.shallow_resolve(c);
 220             match c.kind() {
 221                 ty::ConstKind::Infer(InferConst::Var(vid)) => {
 222                     return Err(FixupError::UnresolvedConst(vid));
 223                 }
 224                 ty::ConstKind::Infer(InferConst::Fresh(_)) => {
 225                     bug!("Unexpected const in full const resolver: {:?}", c);
 226                 }
 227                 _ => {}
 228             }
 229             c.try_super_fold_with(self)
 230         }
 231     }
 232 }