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::{TypeFolder, TypeVisitor};
   5 use rustc_middle::ty::{self, Const, InferConst, Ty, TyCtxt, TypeFoldable};
   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<'a, 'tcx>,
  19 }
  20
  21 impl<'a, 'tcx> OpportunisticVarResolver<'a, 'tcx> {
  22     #[inline]
  23     pub fn new(infcx: &'a InferCtxt<'a, '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_infer_types_or_consts() {
  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: &'tcx Const<'tcx>) -> &'tcx Const<'tcx> {
  43         if !ct.has_infer_types_or_consts() {
  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     fn fold_mir_const(&mut self, constant: mir::ConstantKind<'tcx>) -> mir::ConstantKind<'tcx> {
  52         constant.super_fold_with(self)
  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 /// normlizing 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<'a, 'tcx>,
  65 }
  66
  67 impl<'a, 'tcx> OpportunisticRegionResolver<'a, 'tcx> {
  68     pub fn new(infcx: &'a InferCtxt<'a, '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                 self.tcx().reuse_or_mk_region(r, ty::ReVar(resolved))
  96             }
  97             _ => r,
  98         }
  99     }
 100
 101     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'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 UnresolvedTypeFinder<'a, 'tcx> {
 118     infcx: &'a InferCtxt<'a, 'tcx>,
 119 }
 120
 121 impl<'a, 'tcx> UnresolvedTypeFinder<'a, 'tcx> {
 122     pub fn new(infcx: &'a InferCtxt<'a, 'tcx>) -> Self {
 123         UnresolvedTypeFinder { infcx }
 124     }
 125 }
 126
 127 impl<'a, 'tcx> TypeVisitor<'tcx> for UnresolvedTypeFinder<'a, 'tcx> {
 128     type BreakTy = (Ty<'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 t.has_infer_types() {
 132             if let ty::Infer(infer_ty) = *t.kind() {
 133                 // Since we called `shallow_resolve` above, this must
 134                 // be an (as yet...) unresolved inference variable.
 135                 let ty_var_span = if let ty::TyVar(ty_vid) = infer_ty {
 136                     let mut inner = self.infcx.inner.borrow_mut();
 137                     let ty_vars = &inner.type_variables();
 138                     if let TypeVariableOrigin {
 139                         kind: TypeVariableOriginKind::TypeParameterDefinition(_, _),
 140                         span,
 141                     } = *ty_vars.var_origin(ty_vid)
 142                     {
 143                         Some(span)
 144                     } else {
 145                         None
 146                     }
 147                 } else {
 148                     None
 149                 };
 150                 ControlFlow::Break((t, ty_var_span))
 151             } else {
 152                 // Otherwise, visit its contents.
 153                 t.super_visit_with(self)
 154             }
 155         } else {
 156             // All type variables in inference types must already be resolved,
 157             // - no need to visit the contents, continue visiting.
 158             ControlFlow::CONTINUE
 159         }
 160     }
 161 }
 162
 163 ///////////////////////////////////////////////////////////////////////////
 164 // FULL TYPE RESOLUTION
 165
 166 /// Full type resolution replaces all type and region variables with
 167 /// their concrete results. If any variable cannot be replaced (never unified, etc)
 168 /// then an `Err` result is returned.
 169 pub fn fully_resolve<'a, 'tcx, T>(infcx: &InferCtxt<'a, 'tcx>, value: T) -> FixupResult<'tcx, T>
 170 where
 171     T: TypeFoldable<'tcx>,
 172 {
 173     let mut full_resolver = FullTypeResolver { infcx, err: None };
 174     let result = value.fold_with(&mut full_resolver);
 175     match full_resolver.err {
 176         None => Ok(result),
 177         Some(e) => Err(e),
 178     }
 179 }
 180
 181 // N.B. This type is not public because the protocol around checking the
 182 // `err` field is not enforceable otherwise.
 183 struct FullTypeResolver<'a, 'tcx> {
 184     infcx: &'a InferCtxt<'a, 'tcx>,
 185     err: Option<FixupError<'tcx>>,
 186 }
 187
 188 impl<'a, 'tcx> TypeFolder<'tcx> for FullTypeResolver<'a, 'tcx> {
 189     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 190         self.infcx.tcx
 191     }
 192
 193     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 194         if !t.needs_infer() {
 195             t // micro-optimize -- if there is nothing in this type that this fold affects...
 196         } else {
 197             let t = self.infcx.shallow_resolve(t);
 198             match *t.kind() {
 199                 ty::Infer(ty::TyVar(vid)) => {
 200                     self.err = Some(FixupError::UnresolvedTy(vid));
 201                     self.tcx().ty_error()
 202                 }
 203                 ty::Infer(ty::IntVar(vid)) => {
 204                     self.err = Some(FixupError::UnresolvedIntTy(vid));
 205                     self.tcx().ty_error()
 206                 }
 207                 ty::Infer(ty::FloatVar(vid)) => {
 208                     self.err = Some(FixupError::UnresolvedFloatTy(vid));
 209                     self.tcx().ty_error()
 210                 }
 211                 ty::Infer(_) => {
 212                     bug!("Unexpected type in full type resolver: {:?}", t);
 213                 }
 214                 _ => t.super_fold_with(self),
 215             }
 216         }
 217     }
 218
 219     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 220         match *r {
 221             ty::ReVar(rid) => self
 222                 .infcx
 223                 .lexical_region_resolutions
 224                 .borrow()
 225                 .as_ref()
 226                 .expect("region resolution not performed")
 227                 .resolve_var(rid),
 228             _ => r,
 229         }
 230     }
 231
 232     fn fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 233         if !c.needs_infer() {
 234             c // micro-optimize -- if there is nothing in this const that this fold affects...
 235         } else {
 236             let c = self.infcx.shallow_resolve(c);
 237             match c.val {
 238                 ty::ConstKind::Infer(InferConst::Var(vid)) => {
 239                     self.err = Some(FixupError::UnresolvedConst(vid));
 240                     return self.tcx().const_error(c.ty);
 241                 }
 242                 ty::ConstKind::Infer(InferConst::Fresh(_)) => {
 243                     bug!("Unexpected const in full const resolver: {:?}", c);
 244                 }
 245                 _ => {}
 246             }
 247             c.super_fold_with(self)
 248         }
 249     }
 250 }