1 // Type resolution: the phase that finds all the types in the AST with
2 // unresolved type variables and replaces "ty_var" types with their
5 use crate::check::FnCtxt;
6 use errors::DiagnosticBuilder;
8 use rustc::hir::def_id::{DefId, DefIndex};
9 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
10 use rustc::infer::InferCtxt;
11 use rustc::ty::adjustment::{Adjust, Adjustment, PointerCast};
12 use rustc::ty::fold::{TypeFoldable, TypeFolder};
13 use rustc::ty::{self, Ty, TyCtxt};
14 use rustc::util::nodemap::DefIdSet;
15 use rustc_data_structures::sync::Lrc;
17 use syntax::symbol::sym;
20 ///////////////////////////////////////////////////////////////////////////
23 // During type inference, partially inferred types are
24 // represented using Type variables (ty::Infer). These don't appear in
25 // the final TypeckTables since all of the types should have been
26 // inferred once typeck_tables_of is done.
27 // When type inference is running however, having to update the typeck
28 // tables every time a new type is inferred would be unreasonably slow,
29 // so instead all of the replacement happens at the end in
30 // resolve_type_vars_in_body, which creates a new TypeTables which
31 // doesn't contain any inference types.
32 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
33 pub fn resolve_type_vars_in_body(&self, body: &'tcx hir::Body) -> &'tcx ty::TypeckTables<'tcx> {
34 let item_id = self.tcx.hir().body_owner(body.id());
35 let item_def_id = self.tcx.hir().local_def_id(item_id);
37 // This attribute causes us to dump some writeback information
38 // in the form of errors, which is uSymbolfor unit tests.
39 let rustc_dump_user_substs = self.tcx.has_attr(item_def_id, sym::rustc_dump_user_substs);
41 let mut wbcx = WritebackCx::new(self, body, rustc_dump_user_substs);
42 for param in &body.params {
43 wbcx.visit_node_id(param.pat.span, param.hir_id);
45 // Type only exists for constants and statics, not functions.
46 match self.tcx.hir().body_owner_kind(item_id) {
47 hir::BodyOwnerKind::Const | hir::BodyOwnerKind::Static(_) => {
48 wbcx.visit_node_id(body.value.span, item_id);
50 hir::BodyOwnerKind::Closure | hir::BodyOwnerKind::Fn => (),
52 wbcx.visit_body(body);
53 wbcx.visit_upvar_capture_map();
54 wbcx.visit_closures();
55 wbcx.visit_liberated_fn_sigs();
56 wbcx.visit_fru_field_types();
57 wbcx.visit_opaque_types(body.value.span);
58 wbcx.visit_coercion_casts();
59 wbcx.visit_free_region_map();
60 wbcx.visit_user_provided_tys();
61 wbcx.visit_user_provided_sigs();
63 let used_trait_imports = mem::replace(
64 &mut self.tables.borrow_mut().used_trait_imports,
65 Lrc::new(DefIdSet::default()),
68 "used_trait_imports({:?}) = {:?}",
69 item_def_id, used_trait_imports
71 wbcx.tables.used_trait_imports = used_trait_imports;
73 wbcx.tables.upvar_list = mem::replace(
74 &mut self.tables.borrow_mut().upvar_list,
78 wbcx.tables.tainted_by_errors = self.is_tainted_by_errors();
81 "writeback: tables for {:?} are {:#?}",
82 item_def_id, wbcx.tables
85 self.tcx.arena.alloc(wbcx.tables)
89 ///////////////////////////////////////////////////////////////////////////
90 // The Writeback context. This visitor walks the AST, checking the
91 // fn-specific tables to find references to types or regions. It
92 // resolves those regions to remove inference variables and writes the
93 // final result back into the master tables in the tcx. Here and
94 // there, it applies a few ad-hoc checks that were not convenient to
97 struct WritebackCx<'cx, 'tcx> {
98 fcx: &'cx FnCtxt<'cx, 'tcx>,
100 tables: ty::TypeckTables<'tcx>,
102 body: &'tcx hir::Body,
104 rustc_dump_user_substs: bool,
107 impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
109 fcx: &'cx FnCtxt<'cx, 'tcx>,
110 body: &'tcx hir::Body,
111 rustc_dump_user_substs: bool,
112 ) -> WritebackCx<'cx, 'tcx> {
113 let owner = body.id().hir_id;
117 tables: ty::TypeckTables::empty(Some(DefId::local(owner.owner))),
119 rustc_dump_user_substs,
123 fn tcx(&self) -> TyCtxt<'tcx> {
127 fn write_ty_to_tables(&mut self, hir_id: hir::HirId, ty: Ty<'tcx>) {
128 debug!("write_ty_to_tables({:?}, {:?})", hir_id, ty);
129 assert!(!ty.needs_infer() && !ty.has_placeholders());
130 self.tables.node_types_mut().insert(hir_id, ty);
133 // Hacky hack: During type-checking, we treat *all* operators
134 // as potentially overloaded. But then, during writeback, if
135 // we observe that something like `a+b` is (known to be)
136 // operating on scalars, we clear the overload.
137 fn fix_scalar_builtin_expr(&mut self, e: &hir::Expr) {
139 hir::ExprKind::Unary(hir::UnNeg, ref inner)
140 | hir::ExprKind::Unary(hir::UnNot, ref inner) => {
141 let inner_ty = self.fcx.node_ty(inner.hir_id);
142 let inner_ty = self.fcx.resolve_vars_if_possible(&inner_ty);
144 if inner_ty.is_scalar() {
145 let mut tables = self.fcx.tables.borrow_mut();
146 tables.type_dependent_defs_mut().remove(e.hir_id);
147 tables.node_substs_mut().remove(e.hir_id);
150 hir::ExprKind::Binary(ref op, ref lhs, ref rhs)
151 | hir::ExprKind::AssignOp(ref op, ref lhs, ref rhs) => {
152 let lhs_ty = self.fcx.node_ty(lhs.hir_id);
153 let lhs_ty = self.fcx.resolve_vars_if_possible(&lhs_ty);
155 let rhs_ty = self.fcx.node_ty(rhs.hir_id);
156 let rhs_ty = self.fcx.resolve_vars_if_possible(&rhs_ty);
158 if lhs_ty.is_scalar() && rhs_ty.is_scalar() {
159 let mut tables = self.fcx.tables.borrow_mut();
160 tables.type_dependent_defs_mut().remove(e.hir_id);
161 tables.node_substs_mut().remove(e.hir_id);
164 hir::ExprKind::Binary(..) => {
165 if !op.node.is_by_value() {
166 let mut adjustments = tables.adjustments_mut();
167 adjustments.get_mut(lhs.hir_id).map(|a| a.pop());
168 adjustments.get_mut(rhs.hir_id).map(|a| a.pop());
171 hir::ExprKind::AssignOp(..) => {
185 // Similar to operators, indexing is always assumed to be overloaded
186 // Here, correct cases where an indexing expression can be simplified
187 // to use builtin indexing because the index type is known to be
189 fn fix_index_builtin_expr(&mut self, e: &hir::Expr) {
190 if let hir::ExprKind::Index(ref base, ref index) = e.node {
191 let mut tables = self.fcx.tables.borrow_mut();
193 // All valid indexing looks like this; might encounter non-valid indexes at this point
194 if let ty::Ref(_, base_ty, _) = tables.expr_ty_adjusted(&base).sty {
195 let index_ty = tables.expr_ty_adjusted(&index);
196 let index_ty = self.fcx.resolve_vars_if_possible(&index_ty);
198 if base_ty.builtin_index().is_some() && index_ty == self.fcx.tcx.types.usize {
199 // Remove the method call record
200 tables.type_dependent_defs_mut().remove(e.hir_id);
201 tables.node_substs_mut().remove(e.hir_id);
203 tables.adjustments_mut().get_mut(base.hir_id).map(|a| {
204 // Discard the need for a mutable borrow
206 // Extra adjustment made when indexing causes a drop
207 // of size information - we need to get rid of it
208 // Since this is "after" the other adjustment to be
209 // discarded, we do an extra `pop()`
211 kind: Adjust::Pointer(PointerCast::Unsize),
214 // So the borrow discard actually happens here
226 ///////////////////////////////////////////////////////////////////////////
227 // Impl of Visitor for Resolver
229 // This is the master code which walks the AST. It delegates most of
230 // the heavy lifting to the generic visit and resolve functions
231 // below. In general, a function is made into a `visitor` if it must
232 // traffic in node-ids or update tables in the type context etc.
234 impl<'cx, 'tcx> Visitor<'tcx> for WritebackCx<'cx, 'tcx> {
235 fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
236 NestedVisitorMap::None
239 fn visit_expr(&mut self, e: &'tcx hir::Expr) {
240 self.fix_scalar_builtin_expr(e);
241 self.fix_index_builtin_expr(e);
243 self.visit_node_id(e.span, e.hir_id);
246 hir::ExprKind::Closure(_, _, body, _, _) => {
247 let body = self.fcx.tcx.hir().body(body);
248 for param in &body.params {
249 self.visit_node_id(e.span, param.hir_id);
252 self.visit_body(body);
254 hir::ExprKind::Struct(_, ref fields, _) => {
255 for field in fields {
256 self.visit_field_id(field.hir_id);
259 hir::ExprKind::Field(..) => {
260 self.visit_field_id(e.hir_id);
265 intravisit::walk_expr(self, e);
268 fn visit_block(&mut self, b: &'tcx hir::Block) {
269 self.visit_node_id(b.span, b.hir_id);
270 intravisit::walk_block(self, b);
273 fn visit_pat(&mut self, p: &'tcx hir::Pat) {
275 hir::PatKind::Binding(..) => {
276 if let Some(&bm) = self.fcx.tables.borrow().pat_binding_modes().get(p.hir_id) {
277 self.tables.pat_binding_modes_mut().insert(p.hir_id, bm);
281 .delay_span_bug(p.span, "missing binding mode");
284 hir::PatKind::Struct(_, ref fields, _) => {
285 for field in fields {
286 self.visit_field_id(field.hir_id);
292 self.visit_pat_adjustments(p.span, p.hir_id);
294 self.visit_node_id(p.span, p.hir_id);
295 intravisit::walk_pat(self, p);
298 fn visit_local(&mut self, l: &'tcx hir::Local) {
299 intravisit::walk_local(self, l);
300 let var_ty = self.fcx.local_ty(l.span, l.hir_id).decl_ty;
301 let var_ty = self.resolve(&var_ty, &l.span);
302 self.write_ty_to_tables(l.hir_id, var_ty);
305 fn visit_ty(&mut self, hir_ty: &'tcx hir::Ty) {
306 intravisit::walk_ty(self, hir_ty);
307 let ty = self.fcx.node_ty(hir_ty.hir_id);
308 let ty = self.resolve(&ty, &hir_ty.span);
309 self.write_ty_to_tables(hir_ty.hir_id, ty);
313 impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
314 fn visit_upvar_capture_map(&mut self) {
315 for (upvar_id, upvar_capture) in self.fcx.tables.borrow().upvar_capture_map.iter() {
316 let new_upvar_capture = match *upvar_capture {
317 ty::UpvarCapture::ByValue => ty::UpvarCapture::ByValue,
318 ty::UpvarCapture::ByRef(ref upvar_borrow) => {
319 let r = upvar_borrow.region;
320 let r = self.resolve(&r, &upvar_id.var_path.hir_id);
321 ty::UpvarCapture::ByRef(ty::UpvarBorrow {
322 kind: upvar_borrow.kind,
328 "Upvar capture for {:?} resolved to {:?}",
329 upvar_id, new_upvar_capture
333 .insert(*upvar_id, new_upvar_capture);
337 fn visit_closures(&mut self) {
338 let fcx_tables = self.fcx.tables.borrow();
339 debug_assert_eq!(fcx_tables.local_id_root, self.tables.local_id_root);
340 let common_local_id_root = fcx_tables.local_id_root.unwrap();
342 for (&id, &origin) in fcx_tables.closure_kind_origins().iter() {
343 let hir_id = hir::HirId {
344 owner: common_local_id_root.index,
348 .closure_kind_origins_mut()
349 .insert(hir_id, origin);
353 fn visit_coercion_casts(&mut self) {
354 let fcx_tables = self.fcx.tables.borrow();
355 let fcx_coercion_casts = fcx_tables.coercion_casts();
356 debug_assert_eq!(fcx_tables.local_id_root, self.tables.local_id_root);
358 for local_id in fcx_coercion_casts {
359 self.tables.set_coercion_cast(*local_id);
363 fn visit_free_region_map(&mut self) {
364 self.tables.free_region_map = self.fcx.tables.borrow().free_region_map.clone();
365 debug_assert!(!self.tables.free_region_map.elements().any(|r| r.has_local_value()));
368 fn visit_user_provided_tys(&mut self) {
369 let fcx_tables = self.fcx.tables.borrow();
370 debug_assert_eq!(fcx_tables.local_id_root, self.tables.local_id_root);
371 let common_local_id_root = fcx_tables.local_id_root.unwrap();
373 let mut errors_buffer = Vec::new();
374 for (&local_id, c_ty) in fcx_tables.user_provided_types().iter() {
375 let hir_id = hir::HirId {
376 owner: common_local_id_root.index,
380 if cfg!(debug_assertions) && c_ty.has_local_value() {
382 hir_id.to_span(self.fcx.tcx),
383 "writeback: `{:?}` is a local value",
389 .user_provided_types_mut()
390 .insert(hir_id, c_ty.clone());
392 if let ty::UserType::TypeOf(_, user_substs) = c_ty.value {
393 if self.rustc_dump_user_substs {
394 // This is a unit-testing mechanism.
395 let span = self.tcx().hir().span(hir_id);
396 // We need to buffer the errors in order to guarantee a consistent
397 // order when emitting them.
398 let err = self.tcx().sess.struct_span_err(
400 &format!("user substs: {:?}", user_substs)
402 err.buffer(&mut errors_buffer);
407 if !errors_buffer.is_empty() {
408 errors_buffer.sort_by_key(|diag| diag.span.primary_span());
409 for diag in errors_buffer.drain(..) {
410 DiagnosticBuilder::new_diagnostic(self.tcx().sess.diagnostic(), diag).emit();
415 fn visit_user_provided_sigs(&mut self) {
416 let fcx_tables = self.fcx.tables.borrow();
417 debug_assert_eq!(fcx_tables.local_id_root, self.tables.local_id_root);
419 for (&def_id, c_sig) in fcx_tables.user_provided_sigs.iter() {
420 if cfg!(debug_assertions) && c_sig.has_local_value() {
422 self.fcx.tcx.hir().span_if_local(def_id).unwrap(),
423 "writeback: `{:?}` is a local value",
430 .insert(def_id, c_sig.clone());
434 fn visit_opaque_types(&mut self, span: Span) {
435 for (&def_id, opaque_defn) in self.fcx.opaque_types.borrow().iter() {
436 let hir_id = self.tcx().hir().as_local_hir_id(def_id).unwrap();
437 let instantiated_ty = self.resolve(&opaque_defn.concrete_ty, &hir_id);
439 debug_assert!(!instantiated_ty.has_escaping_bound_vars());
442 // * `fn foo<T>() -> Foo<T>`
443 // * `fn foo<T: Bound + Other>() -> Foo<T>`
444 // from being defining.
446 // Also replace all generic params with the ones from the opaque type
447 // definition so that
449 // type Foo<T> = impl Baz + 'static;
450 // fn foo<U>() -> Foo<U> { .. }
452 // figures out the concrete type with `U`, but the stored type is with `T`.
453 let definition_ty = self.fcx.infer_opaque_definition_from_instantiation(
454 def_id, opaque_defn, instantiated_ty, span);
456 let mut skip_add = false;
458 if let ty::Opaque(defin_ty_def_id, _substs) = definition_ty.sty {
459 if def_id == defin_ty_def_id {
460 debug!("Skipping adding concrete definition for opaque type {:?} {:?}",
461 opaque_defn, defin_ty_def_id);
466 if !opaque_defn.substs.has_local_value() {
467 // We only want to add an entry into `concrete_opaque_types`
468 // if we actually found a defining usage of this opaque type.
469 // Otherwise, we do nothing - we'll either find a defining usage
470 // in some other location, or we'll end up emitting an error due
471 // to the lack of defining usage
473 let new = ty::ResolvedOpaqueTy {
474 concrete_type: definition_ty,
475 substs: opaque_defn.substs,
478 let old = self.tables
479 .concrete_opaque_types
480 .insert(def_id, new);
481 if let Some(old) = old {
482 if old.concrete_type != definition_ty || old.substs != opaque_defn.substs {
485 "visit_opaque_types tried to write different types for the same \
486 opaque type: {:?}, {:?}, {:?}, {:?}",
496 self.tcx().sess.delay_span_bug(
498 "`opaque_defn` is a local value",
504 fn visit_field_id(&mut self, hir_id: hir::HirId) {
505 if let Some(index) = self.fcx
511 self.tables.field_indices_mut().insert(hir_id, index);
515 fn visit_node_id(&mut self, span: Span, hir_id: hir::HirId) {
516 // Export associated path extensions and method resolutions.
517 if let Some(def) = self.fcx
520 .type_dependent_defs_mut()
523 self.tables.type_dependent_defs_mut().insert(hir_id, def);
526 // Resolve any borrowings for the node with id `node_id`
527 self.visit_adjustments(span, hir_id);
529 // Resolve the type of the node with id `node_id`
530 let n_ty = self.fcx.node_ty(hir_id);
531 let n_ty = self.resolve(&n_ty, &span);
532 self.write_ty_to_tables(hir_id, n_ty);
533 debug!("node {:?} has type {:?}", hir_id, n_ty);
535 // Resolve any substitutions
536 if let Some(substs) = self.fcx.tables.borrow().node_substs_opt(hir_id) {
537 let substs = self.resolve(&substs, &span);
538 debug!("write_substs_to_tcx({:?}, {:?})", hir_id, substs);
539 assert!(!substs.needs_infer() && !substs.has_placeholders());
540 self.tables.node_substs_mut().insert(hir_id, substs);
544 fn visit_adjustments(&mut self, span: Span, hir_id: hir::HirId) {
545 let adjustment = self.fcx
552 debug!("no adjustments for node {:?}", hir_id);
555 Some(adjustment) => {
556 let resolved_adjustment = self.resolve(&adjustment, &span);
558 "adjustments for node {:?}: {:?}",
559 hir_id, resolved_adjustment
563 .insert(hir_id, resolved_adjustment);
568 fn visit_pat_adjustments(&mut self, span: Span, hir_id: hir::HirId) {
569 let adjustment = self.fcx
572 .pat_adjustments_mut()
576 debug!("no pat_adjustments for node {:?}", hir_id);
579 Some(adjustment) => {
580 let resolved_adjustment = self.resolve(&adjustment, &span);
582 "pat_adjustments for node {:?}: {:?}",
583 hir_id, resolved_adjustment
586 .pat_adjustments_mut()
587 .insert(hir_id, resolved_adjustment);
592 fn visit_liberated_fn_sigs(&mut self) {
593 let fcx_tables = self.fcx.tables.borrow();
594 debug_assert_eq!(fcx_tables.local_id_root, self.tables.local_id_root);
595 let common_local_id_root = fcx_tables.local_id_root.unwrap();
597 for (&local_id, fn_sig) in fcx_tables.liberated_fn_sigs().iter() {
598 let hir_id = hir::HirId {
599 owner: common_local_id_root.index,
602 let fn_sig = self.resolve(fn_sig, &hir_id);
604 .liberated_fn_sigs_mut()
605 .insert(hir_id, fn_sig.clone());
609 fn visit_fru_field_types(&mut self) {
610 let fcx_tables = self.fcx.tables.borrow();
611 debug_assert_eq!(fcx_tables.local_id_root, self.tables.local_id_root);
612 let common_local_id_root = fcx_tables.local_id_root.unwrap();
614 for (&local_id, ftys) in fcx_tables.fru_field_types().iter() {
615 let hir_id = hir::HirId {
616 owner: common_local_id_root.index,
619 let ftys = self.resolve(ftys, &hir_id);
620 self.tables.fru_field_types_mut().insert(hir_id, ftys);
624 fn resolve<T>(&self, x: &T, span: &dyn Locatable) -> T
626 T: TypeFoldable<'tcx>,
628 let x = x.fold_with(&mut Resolver::new(self.fcx, span, self.body));
629 if cfg!(debug_assertions) && x.has_local_value() {
631 span.to_span(self.fcx.tcx),
632 "writeback: `{:?}` is a local value",
641 fn to_span(&self, tcx: TyCtxt<'_>) -> Span;
644 impl Locatable for Span {
645 fn to_span(&self, _: TyCtxt<'_>) -> Span {
650 impl Locatable for DefIndex {
651 fn to_span(&self, tcx: TyCtxt<'_>) -> Span {
652 let hir_id = tcx.hir().def_index_to_hir_id(*self);
653 tcx.hir().span(hir_id)
657 impl Locatable for hir::HirId {
658 fn to_span(&self, tcx: TyCtxt<'_>) -> Span {
659 tcx.hir().span(*self)
663 ///////////////////////////////////////////////////////////////////////////
664 // The Resolver. This is the type folding engine that detects
665 // unresolved types and so forth.
667 struct Resolver<'cx, 'tcx> {
669 infcx: &'cx InferCtxt<'cx, 'tcx>,
670 span: &'cx dyn Locatable,
671 body: &'tcx hir::Body,
674 impl<'cx, 'tcx> Resolver<'cx, 'tcx> {
676 fcx: &'cx FnCtxt<'cx, 'tcx>,
677 span: &'cx dyn Locatable,
678 body: &'tcx hir::Body,
679 ) -> Resolver<'cx, 'tcx> {
688 fn report_error(&self, t: Ty<'tcx>) {
689 if !self.tcx.sess.has_errors() {
691 .need_type_info_err(Some(self.body.id()), self.span.to_span(self.tcx), t)
697 impl<'cx, 'tcx> TypeFolder<'tcx> for Resolver<'cx, 'tcx> {
698 fn tcx<'a>(&'a self) -> TyCtxt<'tcx> {
702 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
703 match self.infcx.fully_resolve(&t) {
707 "Resolver::fold_ty: input type `{:?}` not fully resolvable",
710 self.report_error(t);
716 // FIXME This should be carefully checked
717 // We could use `self.report_error` but it doesn't accept a ty::Region, right now.
718 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
719 self.infcx.fully_resolve(&r).unwrap_or(self.tcx.lifetimes.re_static)
722 fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
723 match self.infcx.fully_resolve(&ct) {
727 "Resolver::fold_const: input const `{:?}` not fully resolvable",
730 // FIXME: we'd like to use `self.report_error`, but it doesn't yet
731 // accept a &'tcx ty::Const.
732 self.tcx().consts.err
738 ///////////////////////////////////////////////////////////////////////////
739 // During type check, we store promises with the result of trait
740 // lookup rather than the actual results (because the results are not
741 // necessarily available immediately). These routines unwind the
742 // promises. It is expected that we will have already reported any
743 // errors that may be encountered, so if the promises store an error,
744 // a dummy result is returned.