1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // Type resolution: the phase that finds all the types in the AST with
12 // unresolved type variables and replaces "ty_var" types with their
17 use rustc
::hir
::def_id
::{DefId, DefIndex}
;
18 use rustc
::hir
::intravisit
::{self, NestedVisitorMap, Visitor}
;
19 use rustc
::infer
::InferCtxt
;
20 use rustc
::ty
::{self, Ty, TyCtxt}
;
21 use rustc
::ty
::adjustment
::{Adjust, Adjustment}
;
22 use rustc
::ty
::fold
::{TypeFoldable, TypeFolder}
;
23 use rustc
::util
::nodemap
::DefIdSet
;
29 ///////////////////////////////////////////////////////////////////////////
32 impl<'a
, 'gcx
, 'tcx
> FnCtxt
<'a
, 'gcx
, 'tcx
> {
33 pub fn resolve_type_vars_in_body(&self, body
: &'gcx hir
::Body
) -> &'gcx ty
::TypeckTables
<'gcx
> {
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 let mut wbcx
= WritebackCx
::new(self, body
);
38 for arg
in &body
.arguments
{
39 wbcx
.visit_node_id(arg
.pat
.span
, arg
.hir_id
);
41 wbcx
.visit_body(body
);
42 wbcx
.visit_upvar_borrow_map();
43 wbcx
.visit_closures();
44 wbcx
.visit_liberated_fn_sigs();
45 wbcx
.visit_fru_field_types();
46 wbcx
.visit_anon_types();
47 wbcx
.visit_cast_types();
48 wbcx
.visit_free_region_map();
50 let used_trait_imports
= mem
::replace(
51 &mut self.tables
.borrow_mut().used_trait_imports
,
55 "used_trait_imports({:?}) = {:?}",
59 wbcx
.tables
.used_trait_imports
= used_trait_imports
;
61 wbcx
.tables
.tainted_by_errors
= self.is_tainted_by_errors();
64 "writeback: tables for {:?} are {:#?}",
69 self.tcx
.alloc_tables(wbcx
.tables
)
73 ///////////////////////////////////////////////////////////////////////////
74 // The Writerback context. This visitor walks the AST, checking the
75 // fn-specific tables to find references to types or regions. It
76 // resolves those regions to remove inference variables and writes the
77 // final result back into the master tables in the tcx. Here and
78 // there, it applies a few ad-hoc checks that were not convenient to
81 struct WritebackCx
<'cx
, 'gcx
: 'cx
+ 'tcx
, 'tcx
: 'cx
> {
82 fcx
: &'cx FnCtxt
<'cx
, 'gcx
, 'tcx
>,
84 tables
: ty
::TypeckTables
<'gcx
>,
86 body
: &'gcx hir
::Body
,
89 impl<'cx
, 'gcx
, 'tcx
> WritebackCx
<'cx
, 'gcx
, 'tcx
> {
91 fcx
: &'cx FnCtxt
<'cx
, 'gcx
, 'tcx
>,
92 body
: &'gcx hir
::Body
,
93 ) -> WritebackCx
<'cx
, 'gcx
, 'tcx
> {
94 let owner
= fcx
.tcx
.hir
.definitions().node_to_hir_id(body
.id().node_id
);
98 tables
: ty
::TypeckTables
::empty(Some(DefId
::local(owner
.owner
))),
103 fn tcx(&self) -> TyCtxt
<'cx
, 'gcx
, 'tcx
> {
107 fn write_ty_to_tables(&mut self, hir_id
: hir
::HirId
, ty
: Ty
<'gcx
>) {
108 debug
!("write_ty_to_tables({:?}, {:?})", hir_id
, ty
);
109 assert
!(!ty
.needs_infer());
110 self.tables
.node_types_mut().insert(hir_id
, ty
);
113 // Hacky hack: During type-checking, we treat *all* operators
114 // as potentially overloaded. But then, during writeback, if
115 // we observe that something like `a+b` is (known to be)
116 // operating on scalars, we clear the overload.
117 fn fix_scalar_builtin_expr(&mut self, e
: &hir
::Expr
) {
119 hir
::ExprUnary(hir
::UnNeg
, ref inner
) | hir
::ExprUnary(hir
::UnNot
, ref inner
) => {
120 let inner_ty
= self.fcx
.node_ty(inner
.hir_id
);
121 let inner_ty
= self.fcx
.resolve_type_vars_if_possible(&inner_ty
);
123 if inner_ty
.is_scalar() {
124 let mut tables
= self.fcx
.tables
.borrow_mut();
125 tables
.type_dependent_defs_mut().remove(e
.hir_id
);
126 tables
.node_substs_mut().remove(e
.hir_id
);
129 hir
::ExprBinary(ref op
, ref lhs
, ref rhs
)
130 | hir
::ExprAssignOp(ref op
, ref lhs
, ref rhs
) => {
131 let lhs_ty
= self.fcx
.node_ty(lhs
.hir_id
);
132 let lhs_ty
= self.fcx
.resolve_type_vars_if_possible(&lhs_ty
);
134 let rhs_ty
= self.fcx
.node_ty(rhs
.hir_id
);
135 let rhs_ty
= self.fcx
.resolve_type_vars_if_possible(&rhs_ty
);
137 if lhs_ty
.is_scalar() && rhs_ty
.is_scalar() {
138 let mut tables
= self.fcx
.tables
.borrow_mut();
139 tables
.type_dependent_defs_mut().remove(e
.hir_id
);
140 tables
.node_substs_mut().remove(e
.hir_id
);
143 hir
::ExprBinary(..) => {
144 if !op
.node
.is_by_value() {
145 let mut adjustments
= tables
.adjustments_mut();
146 adjustments
.get_mut(lhs
.hir_id
).map(|a
| a
.pop());
147 adjustments
.get_mut(rhs
.hir_id
).map(|a
| a
.pop());
150 hir
::ExprAssignOp(..) => {
164 // Similar to operators, indexing is always assumed to be overloaded
165 // Here, correct cases where an indexing expression can be simplified
166 // to use builtin indexing because the index type is known to be
168 fn fix_index_builtin_expr(&mut self, e
: &hir
::Expr
) {
169 if let hir
::ExprIndex(ref base
, ref index
) = e
.node
{
170 let mut tables
= self.fcx
.tables
.borrow_mut();
172 match tables
.expr_ty_adjusted(&base
).sty
{
173 // All valid indexing looks like this
174 ty
::TyRef(_
, ty
::TypeAndMut { ty: ref base_ty, .. }
) => {
175 let index_ty
= tables
.expr_ty_adjusted(&index
);
176 let index_ty
= self.fcx
.resolve_type_vars_if_possible(&index_ty
);
178 if base_ty
.builtin_index().is_some()
179 && index_ty
== self.fcx
.tcx
.types
.usize {
180 // Remove the method call record
181 tables
.type_dependent_defs_mut().remove(e
.hir_id
);
182 tables
.node_substs_mut().remove(e
.hir_id
);
184 tables
.adjustments_mut().get_mut(base
.hir_id
).map(|a
| {
185 // Discard the need for a mutable borrow
187 // Extra adjustment made when indexing causes a drop
188 // of size information - we need to get rid of it
189 // Since this is "after" the other adjustment to be
190 // discarded, we do an extra `pop()`
191 Some(Adjustment { kind: Adjust::Unsize, .. }
) => {
192 // So the borrow discard actually happens here
200 // Might encounter non-valid indexes at this point, so there
201 // has to be a fall-through
209 ///////////////////////////////////////////////////////////////////////////
210 // Impl of Visitor for Resolver
212 // This is the master code which walks the AST. It delegates most of
213 // the heavy lifting to the generic visit and resolve functions
214 // below. In general, a function is made into a `visitor` if it must
215 // traffic in node-ids or update tables in the type context etc.
217 impl<'cx
, 'gcx
, 'tcx
> Visitor
<'gcx
> for WritebackCx
<'cx
, 'gcx
, 'tcx
> {
218 fn nested_visit_map
<'this
>(&'this
mut self) -> NestedVisitorMap
<'this
, 'gcx
> {
219 NestedVisitorMap
::None
222 fn visit_expr(&mut self, e
: &'gcx hir
::Expr
) {
223 self.fix_scalar_builtin_expr(e
);
224 self.fix_index_builtin_expr(e
);
226 self.visit_node_id(e
.span
, e
.hir_id
);
228 if let hir
::ExprClosure(_
, _
, body
, _
, _
) = e
.node
{
229 let body
= self.fcx
.tcx
.hir
.body(body
);
230 for arg
in &body
.arguments
{
231 self.visit_node_id(e
.span
, arg
.hir_id
);
234 self.visit_body(body
);
237 intravisit
::walk_expr(self, e
);
240 fn visit_block(&mut self, b
: &'gcx hir
::Block
) {
241 self.visit_node_id(b
.span
, b
.hir_id
);
242 intravisit
::walk_block(self, b
);
245 fn visit_pat(&mut self, p
: &'gcx hir
::Pat
) {
247 hir
::PatKind
::Binding(..) => {
253 .expect("missing binding mode");
254 self.tables
.pat_binding_modes_mut().insert(p
.hir_id
, bm
);
259 self.visit_pat_adjustments(p
.span
, p
.hir_id
);
261 self.visit_node_id(p
.span
, p
.hir_id
);
262 intravisit
::walk_pat(self, p
);
265 fn visit_local(&mut self, l
: &'gcx hir
::Local
) {
266 intravisit
::walk_local(self, l
);
267 let var_ty
= self.fcx
.local_ty(l
.span
, l
.id
);
268 let var_ty
= self.resolve(&var_ty
, &l
.span
);
269 self.write_ty_to_tables(l
.hir_id
, var_ty
);
272 fn visit_ty(&mut self, hir_ty
: &'gcx hir
::Ty
) {
273 intravisit
::walk_ty(self, hir_ty
);
274 let ty
= self.fcx
.node_ty(hir_ty
.hir_id
);
275 let ty
= self.resolve(&ty
, &hir_ty
.span
);
276 self.write_ty_to_tables(hir_ty
.hir_id
, ty
);
280 impl<'cx
, 'gcx
, 'tcx
> WritebackCx
<'cx
, 'gcx
, 'tcx
> {
281 fn visit_upvar_borrow_map(&mut self) {
282 for (upvar_id
, upvar_capture
) in self.fcx
.tables
.borrow().upvar_capture_map
.iter() {
283 let new_upvar_capture
= match *upvar_capture
{
284 ty
::UpvarCapture
::ByValue
=> ty
::UpvarCapture
::ByValue
,
285 ty
::UpvarCapture
::ByRef(ref upvar_borrow
) => {
286 let r
= upvar_borrow
.region
;
287 let r
= self.resolve(&r
, &upvar_id
.var_id
);
288 ty
::UpvarCapture
::ByRef(ty
::UpvarBorrow
{
289 kind
: upvar_borrow
.kind
,
295 "Upvar capture for {:?} resolved to {:?}",
301 .insert(*upvar_id
, new_upvar_capture
);
305 fn visit_closures(&mut self) {
306 let fcx_tables
= self.fcx
.tables
.borrow();
307 debug_assert_eq
!(fcx_tables
.local_id_root
, self.tables
.local_id_root
);
308 let common_local_id_root
= fcx_tables
.local_id_root
.unwrap();
310 for (&id
, &origin
) in fcx_tables
.closure_kind_origins().iter() {
311 let hir_id
= hir
::HirId
{
312 owner
: common_local_id_root
.index
,
316 .closure_kind_origins_mut()
317 .insert(hir_id
, origin
);
321 fn visit_cast_types(&mut self) {
322 let fcx_tables
= self.fcx
.tables
.borrow();
323 let fcx_cast_kinds
= fcx_tables
.cast_kinds();
324 debug_assert_eq
!(fcx_tables
.local_id_root
, self.tables
.local_id_root
);
325 let mut self_cast_kinds
= self.tables
.cast_kinds_mut();
326 let common_local_id_root
= fcx_tables
.local_id_root
.unwrap();
328 for (&local_id
, &cast_kind
) in fcx_cast_kinds
.iter() {
329 let hir_id
= hir
::HirId
{
330 owner
: common_local_id_root
.index
,
333 self_cast_kinds
.insert(hir_id
, cast_kind
);
337 fn visit_free_region_map(&mut self) {
338 let free_region_map
= self.tcx()
339 .lift_to_global(&self.fcx
.tables
.borrow().free_region_map
);
340 let free_region_map
= free_region_map
.expect("all regions in free-region-map are global");
341 self.tables
.free_region_map
= free_region_map
;
344 fn visit_anon_types(&mut self) {
345 let gcx
= self.tcx().global_tcx();
346 for (&def_id
, anon_defn
) in self.fcx
.anon_types
.borrow().iter() {
347 let node_id
= gcx
.hir
.as_local_node_id(def_id
).unwrap();
348 let instantiated_ty
= self.resolve(&anon_defn
.concrete_ty
, &node_id
);
349 let definition_ty
= self.fcx
.infer_anon_definition_from_instantiation(
354 let hir_id
= self.tcx().hir
.node_to_hir_id(node_id
);
355 self.tables
.node_types_mut().insert(hir_id
, definition_ty
);
359 fn visit_node_id(&mut self, span
: Span
, hir_id
: hir
::HirId
) {
360 // Export associated path extensions and method resultions.
361 if let Some(def
) = self.fcx
364 .type_dependent_defs_mut()
367 self.tables
.type_dependent_defs_mut().insert(hir_id
, def
);
370 // Resolve any borrowings for the node with id `node_id`
371 self.visit_adjustments(span
, hir_id
);
373 // Resolve the type of the node with id `node_id`
374 let n_ty
= self.fcx
.node_ty(hir_id
);
375 let n_ty
= self.resolve(&n_ty
, &span
);
376 self.write_ty_to_tables(hir_id
, n_ty
);
377 debug
!("Node {:?} has type {:?}", hir_id
, n_ty
);
379 // Resolve any substitutions
380 if let Some(substs
) = self.fcx
.tables
.borrow().node_substs_opt(hir_id
) {
381 let substs
= self.resolve(&substs
, &span
);
382 debug
!("write_substs_to_tcx({:?}, {:?})", hir_id
, substs
);
383 assert
!(!substs
.needs_infer());
384 self.tables
.node_substs_mut().insert(hir_id
, substs
);
388 fn visit_adjustments(&mut self, span
: Span
, hir_id
: hir
::HirId
) {
389 let adjustment
= self.fcx
396 debug
!("No adjustments for node {:?}", hir_id
);
399 Some(adjustment
) => {
400 let resolved_adjustment
= self.resolve(&adjustment
, &span
);
402 "Adjustments for node {:?}: {:?}",
408 .insert(hir_id
, resolved_adjustment
);
413 fn visit_pat_adjustments(&mut self, span
: Span
, hir_id
: hir
::HirId
) {
414 let adjustment
= self.fcx
417 .pat_adjustments_mut()
421 debug
!("No pat_adjustments for node {:?}", hir_id
);
424 Some(adjustment
) => {
425 let resolved_adjustment
= self.resolve(&adjustment
, &span
);
427 "pat_adjustments for node {:?}: {:?}",
432 .pat_adjustments_mut()
433 .insert(hir_id
, resolved_adjustment
);
438 fn visit_liberated_fn_sigs(&mut self) {
439 let fcx_tables
= self.fcx
.tables
.borrow();
440 debug_assert_eq
!(fcx_tables
.local_id_root
, self.tables
.local_id_root
);
441 let common_local_id_root
= fcx_tables
.local_id_root
.unwrap();
443 for (&local_id
, fn_sig
) in fcx_tables
.liberated_fn_sigs().iter() {
444 let hir_id
= hir
::HirId
{
445 owner
: common_local_id_root
.index
,
448 let fn_sig
= self.resolve(fn_sig
, &hir_id
);
450 .liberated_fn_sigs_mut()
451 .insert(hir_id
, fn_sig
.clone());
455 fn visit_fru_field_types(&mut self) {
456 let fcx_tables
= self.fcx
.tables
.borrow();
457 debug_assert_eq
!(fcx_tables
.local_id_root
, self.tables
.local_id_root
);
458 let common_local_id_root
= fcx_tables
.local_id_root
.unwrap();
460 for (&local_id
, ftys
) in fcx_tables
.fru_field_types().iter() {
461 let hir_id
= hir
::HirId
{
462 owner
: common_local_id_root
.index
,
465 let ftys
= self.resolve(ftys
, &hir_id
);
466 self.tables
.fru_field_types_mut().insert(hir_id
, ftys
);
470 fn resolve
<T
>(&self, x
: &T
, span
: &Locatable
) -> T
::Lifted
472 T
: TypeFoldable
<'tcx
> + ty
::Lift
<'gcx
>,
474 let x
= x
.fold_with(&mut Resolver
::new(self.fcx
, span
, self.body
));
475 if let Some(lifted
) = self.tcx().lift_to_global(&x
) {
479 span
.to_span(&self.fcx
.tcx
),
480 "writeback: `{:?}` missing from the global type context",
488 fn to_span(&self, tcx
: &TyCtxt
) -> Span
;
491 impl Locatable
for Span
{
492 fn to_span(&self, _
: &TyCtxt
) -> Span
{
497 impl Locatable
for ast
::NodeId
{
498 fn to_span(&self, tcx
: &TyCtxt
) -> Span
{
503 impl Locatable
for DefIndex
{
504 fn to_span(&self, tcx
: &TyCtxt
) -> Span
{
505 let node_id
= tcx
.hir
.def_index_to_node_id(*self);
506 tcx
.hir
.span(node_id
)
510 impl Locatable
for hir
::HirId
{
511 fn to_span(&self, tcx
: &TyCtxt
) -> Span
{
512 let node_id
= tcx
.hir
.definitions().find_node_for_hir_id(*self);
513 tcx
.hir
.span(node_id
)
517 ///////////////////////////////////////////////////////////////////////////
518 // The Resolver. This is the type folding engine that detects
519 // unresolved types and so forth.
521 struct Resolver
<'cx
, 'gcx
: 'cx
+ 'tcx
, 'tcx
: 'cx
> {
522 tcx
: TyCtxt
<'cx
, 'gcx
, 'tcx
>,
523 infcx
: &'cx InferCtxt
<'cx
, 'gcx
, 'tcx
>,
524 span
: &'cx Locatable
,
525 body
: &'gcx hir
::Body
,
528 impl<'cx
, 'gcx
, 'tcx
> Resolver
<'cx
, 'gcx
, 'tcx
> {
530 fcx
: &'cx FnCtxt
<'cx
, 'gcx
, 'tcx
>,
531 span
: &'cx Locatable
,
532 body
: &'gcx hir
::Body
,
533 ) -> Resolver
<'cx
, 'gcx
, 'tcx
> {
542 fn report_error(&self, t
: Ty
<'tcx
>) {
543 if !self.tcx
.sess
.has_errors() {
545 .need_type_info(Some(self.body
.id()), self.span
.to_span(&self.tcx
), t
);
550 impl<'cx
, 'gcx
, 'tcx
> TypeFolder
<'gcx
, 'tcx
> for Resolver
<'cx
, 'gcx
, 'tcx
> {
551 fn tcx
<'a
>(&'a
self) -> TyCtxt
<'a
, 'gcx
, 'tcx
> {
555 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
556 match self.infcx
.fully_resolve(&t
) {
560 "Resolver::fold_ty: input type `{:?}` not fully resolvable",
563 self.report_error(t
);
569 // FIXME This should be carefully checked
570 // We could use `self.report_error` but it doesn't accept a ty::Region, right now.
571 fn fold_region(&mut self, r
: ty
::Region
<'tcx
>) -> ty
::Region
<'tcx
> {
572 match self.infcx
.fully_resolve(&r
) {
574 Err(_
) => self.tcx
.types
.re_static
,
579 ///////////////////////////////////////////////////////////////////////////
580 // During type check, we store promises with the result of trait
581 // lookup rather than the actual results (because the results are not
582 // necessarily available immediately). These routines unwind the
583 // promises. It is expected that we will have already reported any
584 // errors that may be encountered, so if the promises store an error,
585 // a dummy result is returned.