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