1 // Copyright 2012-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.
4 //
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.
10
11
12 use middle::ty;
13 use middle::ty::{AutoAddEnv, AutoDerefRef, AutoObject, param_ty};
14 use middle::ty_fold::TypeFolder;
15 use middle::typeck::astconv::AstConv;
16 use middle::typeck::check::{FnCtxt, impl_self_ty};
17 use middle::typeck::check::{structurally_resolved_type};
18 use middle::typeck::infer::fixup_err_to_str;
19 use middle::typeck::infer::{resolve_and_force_all_but_regions, resolve_type};
20 use middle::typeck::infer;
21 use middle::typeck::{vtable_origin, vtable_res, vtable_param_res};
22 use middle::typeck::{vtable_static, vtable_param, impl_res};
23 use middle::typeck::{param_numbered, param_self, param_index};
24 use middle::typeck::MethodCall;
25 use middle::subst::Subst;
26 use util::common::indenter;
27 use util::ppaux;
28 use util::ppaux::Repr;
29
30 use std::rc::Rc;
31 use collections::HashSet;
32 use syntax::ast;
33 use syntax::ast_util;
34 use syntax::codemap::Span;
35 use syntax::print::pprust::expr_to_str;
36 use syntax::visit;
37 use syntax::visit::Visitor;
38
39 // vtable resolution looks for places where trait bounds are
40 // substituted in and figures out which vtable is used. There is some
41 // extra complication thrown in to support early "opportunistic"
42 // vtable resolution. This is a hacky mechanism that is invoked while
43 // typechecking function calls (after typechecking non-closure
44 // arguments and before typechecking closure arguments) in the hope of
45 // solving for the trait parameters from the impl. (For example,
46 // determining that if a parameter bounded by BaseIter<A> is
47 // instantiated with Option<int>, that A = int.)
48 //
49 // In early resolution mode, no vtables are recorded, and a number of
50 // errors are ignored. Early resolution only works if a type is
51 // *fully* resolved. (We could be less restrictive than that, but it
52 // would require much more care, and this seems to work decently in
53 // practice.)
54 //
55 // While resolution on a single type requires the type to be fully
56 // resolved, when resolving a substitution against a list of bounds,
57 // we do not require all of the types to be resolved in advance.
58 // Furthermore, we process substitutions in reverse order, which
59 // allows resolution on later parameters to give information on
60 // earlier params referenced by the typeclass bounds.
61 // It may be better to do something more clever, like processing fully
62 // resolved types first.
63
64 /// A vtable context includes an inference context, a crate context, and a
65 /// callback function to call in case of type error.
66 pub struct VtableContext<'a> {
67 pub infcx: &'a infer::InferCtxt<'a>,
68 pub param_env: &'a ty::ParameterEnvironment,
69 }
70
71 impl<'a> VtableContext<'a> {
72 pub fn tcx(&self) -> &'a ty::ctxt { self.infcx.tcx }
73 }
74
75 fn has_trait_bounds(type_param_defs: &[ty::TypeParameterDef]) -> bool {
76 type_param_defs.iter().any(
77 |type_param_def| !type_param_def.bounds.trait_bounds.is_empty())
78 }
79
80 fn lookup_vtables(vcx: &VtableContext,
81 span: Span,
82 type_param_defs: &[ty::TypeParameterDef],
83 substs: &ty::substs,
84 is_early: bool) -> vtable_res {
85 debug!("lookup_vtables(span={:?}, \
86 type_param_defs={}, \
87 substs={}",
88 span,
89 type_param_defs.repr(vcx.tcx()),
90 substs.repr(vcx.tcx()));
91
92 // We do this backwards for reasons discussed above.
93 assert_eq!(substs.tps.len(), type_param_defs.len());
94 let mut result: Vec<vtable_param_res> =
95 substs.tps.iter()
96 .rev()
97 .zip(type_param_defs.iter().rev())
98 .map(|(ty, def)|
99 lookup_vtables_for_param(vcx, span, Some(substs),
100 &*def.bounds, *ty, is_early))
101 .collect();
102 result.reverse();
103
104 assert_eq!(substs.tps.len(), result.len());
105 debug!("lookup_vtables result(\
106 span={:?}, \
107 type_param_defs={}, \
108 substs={}, \
109 result={})",
110 span,
111 type_param_defs.repr(vcx.tcx()),
112 substs.repr(vcx.tcx()),
113 result.repr(vcx.tcx()));
114 result
115 }
116
117 fn lookup_vtables_for_param(vcx: &VtableContext,
118 span: Span,
119 // None for substs means the identity
120 substs: Option<&ty::substs>,
121 type_param_bounds: &ty::ParamBounds,
122 ty: ty::t,
123 is_early: bool) -> vtable_param_res {
124 let tcx = vcx.tcx();
125
126 // ty is the value supplied for the type parameter A...
127 let mut param_result = Vec::new();
128
129 ty::each_bound_trait_and_supertraits(tcx,
130 type_param_bounds.trait_bounds
131 .as_slice(),
132 |trait_ref| {
133 // ...and here trait_ref is each bound that was declared on A,
134 // expressed in terms of the type parameters.
135
136 ty::populate_implementations_for_trait_if_necessary(tcx,
137 trait_ref.def_id);
138
139 // Substitute the values of the type parameters that may
140 // appear in the bound.
141 let trait_ref = substs.as_ref().map_or(trait_ref.clone(), |substs| {
142 debug!("about to subst: {}, {}",
143 trait_ref.repr(tcx), substs.repr(tcx));
144 trait_ref.subst(tcx, *substs)
145 });
146
147 debug!("after subst: {}", trait_ref.repr(tcx));
148
149 match lookup_vtable(vcx, span, ty, trait_ref.clone(), is_early) {
150 Some(vtable) => param_result.push(vtable),
151 None => {
152 vcx.tcx().sess.span_fatal(span,
153 format!("failed to find an implementation of \
154 trait {} for {}",
155 vcx.infcx.trait_ref_to_str(&*trait_ref),
156 vcx.infcx.ty_to_str(ty)));
157 }
158 }
159 true
160 });
161
162 debug!("lookup_vtables_for_param result(\
163 span={:?}, \
164 type_param_bounds={}, \
165 ty={}, \
166 result={})",
167 span,
168 type_param_bounds.repr(vcx.tcx()),
169 ty.repr(vcx.tcx()),
170 param_result.repr(vcx.tcx()));
171
172 param_result
173 }
174
175 fn relate_trait_refs(vcx: &VtableContext,
176 span: Span,
177 act_trait_ref: Rc<ty::TraitRef>,
178 exp_trait_ref: Rc<ty::TraitRef>) {
179 /*!
180 *
181 * Checks that an implementation of `act_trait_ref` is suitable
182 * for use where `exp_trait_ref` is required and reports an
183 * error otherwise.
184 */
185
186 match infer::mk_sub_trait_refs(vcx.infcx,
187 false,
188 infer::RelateTraitRefs(span),
189 act_trait_ref.clone(),
190 exp_trait_ref.clone()) {
191 Ok(()) => {} // Ok.
192 Err(ref err) => {
193 // There is an error, but we need to do some work to make
194 // the message good.
195 // Resolve any type vars in the trait refs
196 let r_act_trait_ref =
197 vcx.infcx.resolve_type_vars_in_trait_ref_if_possible(&*act_trait_ref);
198 let r_exp_trait_ref =
199 vcx.infcx.resolve_type_vars_in_trait_ref_if_possible(&*exp_trait_ref);
200 // Only print the message if there aren't any previous type errors
201 // inside the types.
202 if !ty::trait_ref_contains_error(&r_act_trait_ref) &&
203 !ty::trait_ref_contains_error(&r_exp_trait_ref)
204 {
205 let tcx = vcx.tcx();
206 tcx.sess.span_err(span,
207 format!("expected {}, but found {} ({})",
208 ppaux::trait_ref_to_str(tcx, &r_exp_trait_ref),
209 ppaux::trait_ref_to_str(tcx, &r_act_trait_ref),
210 ty::type_err_to_str(tcx, err)));
211 }
212 }
213 }
214 }
215
216 // Look up the vtable implementing the trait `trait_ref` at type `t`
217 fn lookup_vtable(vcx: &VtableContext,
218 span: Span,
219 ty: ty::t,
220 trait_ref: Rc<ty::TraitRef>,
221 is_early: bool)
222 -> Option<vtable_origin> {
223 debug!("lookup_vtable(ty={}, trait_ref={})",
224 vcx.infcx.ty_to_str(ty),
225 vcx.infcx.trait_ref_to_str(&*trait_ref));
226 let _i = indenter();
227
228 let ty = match fixup_ty(vcx, span, ty, is_early) {
229 Some(ty) => ty,
230 None => {
231 // fixup_ty can only fail if this is early resolution
232 assert!(is_early);
233 // The type has unconstrained type variables in it, so we can't
234 // do early resolution on it. Return some completely bogus vtable
235 // information: we aren't storing it anyways.
236 return Some(vtable_param(param_self, 0));
237 }
238 };
239
240 // If the type is self or a param, we look at the trait/supertrait
241 // bounds to see if they include the trait we are looking for.
242 let vtable_opt = match ty::get(ty).sty {
243 ty::ty_param(param_ty {idx: n, ..}) => {
244 let env_bounds = &vcx.param_env.type_param_bounds;
245 if env_bounds.len() > n {
246 let type_param_bounds: &[Rc<ty::TraitRef>] =
247 env_bounds.get(n).trait_bounds.as_slice();
248 lookup_vtable_from_bounds(vcx, span,
249 type_param_bounds,
250 param_numbered(n),
251 trait_ref.clone())
252 } else {
253 None
254 }
255 }
256
257 ty::ty_self(_) => {
258 let self_param_bound = vcx.param_env.self_param_bound.clone().unwrap();
259 lookup_vtable_from_bounds(vcx, span,
260 [self_param_bound],
261 param_self,
262 trait_ref.clone())
263 }
264
265 // Default case just falls through
266 _ => None
267 };
268
269 if vtable_opt.is_some() { return vtable_opt; }
270
271 // If we aren't a self type or param, or it was, but we didn't find it,
272 // do a search.
273 search_for_vtable(vcx, span, ty, trait_ref, is_early)
274 }
275
276 // Given a list of bounds on a type, search those bounds to see if any
277 // of them are the vtable we are looking for.
278 fn lookup_vtable_from_bounds(vcx: &VtableContext,
279 span: Span,
280 bounds: &[Rc<ty::TraitRef>],
281 param: param_index,
282 trait_ref: Rc<ty::TraitRef>)
283 -> Option<vtable_origin> {
284 let tcx = vcx.tcx();
285
286 let mut n_bound = 0;
287 let mut ret = None;
288 ty::each_bound_trait_and_supertraits(tcx, bounds, |bound_trait_ref| {
289 debug!("checking bounds trait {}",
290 bound_trait_ref.repr(vcx.tcx()));
291
292 if bound_trait_ref.def_id == trait_ref.def_id {
293 relate_trait_refs(vcx, span, bound_trait_ref, trait_ref.clone());
294 let vtable = vtable_param(param, n_bound);
295 debug!("found param vtable: {:?}",
296 vtable);
297 ret = Some(vtable);
298 false
299 } else {
300 n_bound += 1;
301 true
302 }
303 });
304 ret
305 }
306
307 fn search_for_vtable(vcx: &VtableContext,
308 span: Span,
309 ty: ty::t,
310 trait_ref: Rc<ty::TraitRef>,
311 is_early: bool)
312 -> Option<vtable_origin> {
313 let tcx = vcx.tcx();
314
315 let mut found = Vec::new();
316 let mut impls_seen = HashSet::new();
317
318 // Load the implementations from external metadata if necessary.
319 ty::populate_implementations_for_trait_if_necessary(tcx,
320 trait_ref.def_id);
321
322 let impls = match tcx.trait_impls.borrow().find_copy(&trait_ref.def_id) {
323 Some(impls) => impls,
324 None => {
325 return None;
326 }
327 };
328 // impls is the list of all impls in scope for trait_ref.
329 for &impl_did in impls.borrow().iter() {
330 // im is one specific impl of trait_ref.
331
332 // First, ensure we haven't processed this impl yet.
333 if impls_seen.contains(&impl_did) {
334 continue;
335 }
336 impls_seen.insert(impl_did);
337
338 // ty::impl_traits gives us the trait im implements.
339 //
340 // If foo implements a trait t, and if t is the same trait as
341 // trait_ref, we need to unify it with trait_ref in order to
342 // get all the ty vars sorted out.
343 let r = ty::impl_trait_ref(tcx, impl_did);
344 let of_trait_ref = r.expect("trait_ref missing on trait impl");
345 if of_trait_ref.def_id != trait_ref.def_id { continue; }
346
347 // At this point, we know that of_trait_ref is the same trait
348 // as trait_ref, but possibly applied to different substs.
349 //
350 // Next, we check whether the "for" ty in the impl is
351 // compatible with the type that we're casting to a
352 // trait. That is, if im is:
353 //
354 // impl<T> some_trait<T> for self_ty<T> { ... }
355 //
356 // we check whether self_ty<T> is the type of the thing that
357 // we're trying to cast to some_trait. If not, then we try
358 // the next impl.
359 //
360 // FIXME: document a bit more what this means
361 //
362 // FIXME(#5781) this should be mk_eqty not mk_subty
363 let ty::ty_param_substs_and_ty {
364 substs: substs,
365 ty: for_ty
366 } = impl_self_ty(vcx, span, impl_did);
367 match infer::mk_subty(vcx.infcx,
368 false,
369 infer::RelateSelfType(span),
370 ty,
371 for_ty) {
372 Err(_) => continue,
373 Ok(()) => ()
374 }
375
376 // Now, in the previous example, for_ty is bound to
377 // the type self_ty, and substs is bound to [T].
378 debug!("The self ty is {} and its substs are {}",
379 vcx.infcx.ty_to_str(for_ty),
380 vcx.infcx.tys_to_str(substs.tps.as_slice()));
381
382 // Next, we unify trait_ref -- the type that we want to cast
383 // to -- with of_trait_ref -- the trait that im implements. At
384 // this point, we require that they be unifiable with each
385 // other -- that's what relate_trait_refs does.
386 //
387 // For example, in the above example, of_trait_ref would be
388 // some_trait<T>, so we would be unifying trait_ref<U> (for
389 // some value of U) with some_trait<T>. This would fail if T
390 // and U weren't compatible.
391
392 debug!("(checking vtable) \\#2 relating trait \
393 ty {} to of_trait_ref {}",
394 vcx.infcx.trait_ref_to_str(&*trait_ref),
395 vcx.infcx.trait_ref_to_str(&*of_trait_ref));
396
397 let of_trait_ref = of_trait_ref.subst(tcx, &substs);
398 relate_trait_refs(vcx, span, of_trait_ref, trait_ref.clone());
399
400
401 // Recall that trait_ref -- the trait type we're casting to --
402 // is the trait with id trait_ref.def_id applied to the substs
403 // trait_ref.substs.
404
405 // Resolve any sub bounds. Note that there still may be free
406 // type variables in substs. This might still be OK: the
407 // process of looking up bounds might constrain some of them.
408 let im_generics =
409 ty::lookup_item_type(tcx, impl_did).generics;
410 let subres = lookup_vtables(vcx, span,
411 im_generics.type_param_defs(), &substs,
412 is_early);
413
414
415 // substs might contain type variables, so we call
416 // fixup_substs to resolve them.
417 let substs_f = match fixup_substs(vcx, span,
418 trait_ref.def_id,
419 substs,
420 is_early) {
421 Some(ref substs) => (*substs).clone(),
422 None => {
423 assert!(is_early);
424 // Bail out with a bogus answer
425 return Some(vtable_param(param_self, 0));
426 }
427 };
428
429 debug!("The fixed-up substs are {} - \
430 they will be unified with the bounds for \
431 the target ty, {}",
432 vcx.infcx.tys_to_str(substs_f.tps.as_slice()),
433 vcx.infcx.trait_ref_to_str(&*trait_ref));
434
435 // Next, we unify the fixed-up substitutions for the impl self
436 // ty with the substitutions from the trait type that we're
437 // trying to cast to. connect_trait_tps requires these lists
438 // of types to unify pairwise.
439 // I am a little confused about this, since it seems to be
440 // very similar to the relate_trait_refs we already do,
441 // but problems crop up if it is removed, so... -sully
442 connect_trait_tps(vcx, span, &substs_f, trait_ref.clone(), impl_did);
443
444 // Finally, we register that we found a matching impl, and
445 // record the def ID of the impl as well as the resolved list
446 // of type substitutions for the target trait.
447 found.push(vtable_static(impl_did, substs_f.tps.clone(), subres));
448 }
449
450 match found.len() {
451 0 => { return None }
452 1 => return Some(found.get(0).clone()),
453 _ => {
454 if !is_early {
455 vcx.tcx().sess.span_err(span, "multiple applicable methods in scope");
456 }
457 return Some(found.get(0).clone());
458 }
459 }
460 }
461
462
463 fn fixup_substs(vcx: &VtableContext,
464 span: Span,
465 id: ast::DefId,
466 substs: ty::substs,
467 is_early: bool)
468 -> Option<ty::substs> {
469 let tcx = vcx.tcx();
470 // use a dummy type just to package up the substs that need fixing up
471 let t = ty::mk_trait(tcx,
472 id, substs,
473 ty::RegionTraitStore(ty::ReStatic, ast::MutImmutable),
474 ty::EmptyBuiltinBounds());
475 fixup_ty(vcx, span, t, is_early).map(|t_f| {
476 match ty::get(t_f).sty {
477 ty::ty_trait(ref inner) => inner.substs.clone(),
478 _ => fail!("t_f should be a trait")
479 }
480 })
481 }
482
483 fn fixup_ty(vcx: &VtableContext,
484 span: Span,
485 ty: ty::t,
486 is_early: bool)
487 -> Option<ty::t> {
488 let tcx = vcx.tcx();
489 match resolve_type(vcx.infcx, ty, resolve_and_force_all_but_regions) {
490 Ok(new_type) => Some(new_type),
491 Err(e) if !is_early => {
492 tcx.sess.span_fatal(span,
493 format!("cannot determine a type \
494 for this bounded type parameter: {}",
495 fixup_err_to_str(e)))
496 }
497 Err(_) => {
498 None
499 }
500 }
501 }
502
503 fn connect_trait_tps(vcx: &VtableContext,
504 span: Span,
505 impl_substs: &ty::substs,
506 trait_ref: Rc<ty::TraitRef>,
507 impl_did: ast::DefId) {
508 let tcx = vcx.tcx();
509
510 let impl_trait_ref = match ty::impl_trait_ref(tcx, impl_did) {
511 Some(t) => t,
512 None => vcx.tcx().sess.span_bug(span,
513 "connect_trait_tps invoked on a type impl")
514 };
515
516 let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
517 relate_trait_refs(vcx, span, impl_trait_ref, trait_ref);
518 }
519
520 fn insert_vtables(fcx: &FnCtxt, vtable_key: MethodCall, vtables: vtable_res) {
521 debug!("insert_vtables(vtable_key={}, vtables={:?})",
522 vtable_key, vtables.repr(fcx.tcx()));
523 fcx.inh.vtable_map.borrow_mut().insert(vtable_key, vtables);
524 }
525
526 pub fn early_resolve_expr(ex: &ast::Expr, fcx: &FnCtxt, is_early: bool) {
527 debug!("vtable: early_resolve_expr() ex with id {:?} (early: {}): {}",
528 ex.id, is_early, expr_to_str(ex));
529 let _indent = indenter();
530
531 let cx = fcx.ccx;
532 let resolve_object_cast = |src: &ast::Expr, target_ty: ty::t| {
533 match ty::get(target_ty).sty {
534 // Bounds of type's contents are not checked here, but in kind.rs.
535 ty::ty_trait(box ty::TyTrait {
536 def_id: target_def_id, substs: ref target_substs, store, ..
537 }) => {
538 fn mutability_allowed(a_mutbl: ast::Mutability,
539 b_mutbl: ast::Mutability) -> bool {
540 a_mutbl == b_mutbl ||
541 (a_mutbl == ast::MutMutable && b_mutbl == ast::MutImmutable)
542 }
543 // Look up vtables for the type we're casting to,
544 // passing in the source and target type. The source
545 // must be a pointer type suitable to the object sigil,
546 // e.g.: `&x as &Trait` or `box x as Box<Trait>`
547 let ty = structurally_resolved_type(fcx, ex.span,
548 fcx.expr_ty(src));
549 match (&ty::get(ty).sty, store) {
550 (&ty::ty_rptr(_, mt), ty::RegionTraitStore(_, mutbl))
551 if !mutability_allowed(mt.mutbl, mutbl) => {
552 fcx.tcx().sess.span_err(ex.span,
553 format!("types differ in mutability"));
554 }
555
556 (&ty::ty_uniq(..), ty::UniqTraitStore) |
557 (&ty::ty_rptr(..), ty::RegionTraitStore(..)) => {
558 let typ = match &ty::get(ty).sty {
559 &ty::ty_box(typ) | &ty::ty_uniq(typ) => typ,
560 &ty::ty_rptr(_, mt) => mt.ty,
561 _ => fail!("shouldn't get here"),
562 };
563
564 let vcx = fcx.vtable_context();
565 let target_trait_ref = Rc::new(ty::TraitRef {
566 def_id: target_def_id,
567 substs: ty::substs {
568 tps: target_substs.tps.clone(),
569 regions: target_substs.regions.clone(),
570 self_ty: Some(typ)
571 }
572 });
573
574 let param_bounds = ty::ParamBounds {
575 builtin_bounds: ty::EmptyBuiltinBounds(),
576 trait_bounds: vec!(target_trait_ref)
577 };
578 let vtables =
579 lookup_vtables_for_param(&vcx,
580 ex.span,
581 None,
582 ¶m_bounds,
583 typ,
584 is_early);
585
586 if !is_early {
587 insert_vtables(fcx, MethodCall::expr(ex.id), vec!(vtables));
588 }
589
590 // Now, if this is &trait, we need to link the
591 // regions.
592 match (&ty::get(ty).sty, store) {
593 (&ty::ty_rptr(ra, _),
594 ty::RegionTraitStore(rb, _)) => {
595 infer::mk_subr(fcx.infcx(),
596 false,
597 infer::RelateObjectBound(
598 ex.span),
599 rb,
600 ra);
601 }
602 _ => {}
603 }
604 }
605
606 (_, ty::UniqTraitStore) => {
607 fcx.ccx.tcx.sess.span_err(
608 ex.span,
609 format!("can only cast an boxed pointer \
610 to a boxed object, not a {}",
611 ty::ty_sort_str(fcx.tcx(), ty)));
612 }
613
614 (_, ty::RegionTraitStore(..)) => {
615 fcx.ccx.tcx.sess.span_err(
616 ex.span,
617 format!("can only cast an &-pointer \
618 to an &-object, not a {}",
619 ty::ty_sort_str(fcx.tcx(), ty)));
620 }
621 }
622 }
623 _ => { /* not a cast to a trait; ignore */ }
624 }
625 };
626 match ex.node {
627 ast::ExprPath(..) => {
628 fcx.opt_node_ty_substs(ex.id, |substs| {
629 debug!("vtable resolution on parameter bounds for expr {}",
630 ex.repr(fcx.tcx()));
631 let def = cx.tcx.def_map.borrow().get_copy(&ex.id);
632 let did = ast_util::def_id_of_def(def);
633 let item_ty = ty::lookup_item_type(cx.tcx, did);
634 debug!("early resolve expr: def {:?} {:?}, {:?}, {}", ex.id, did, def,
635 fcx.infcx().ty_to_str(item_ty.ty));
636 if has_trait_bounds(item_ty.generics.type_param_defs()) {
637 debug!("early_resolve_expr: looking up vtables for type params {}",
638 item_ty.generics.type_param_defs().repr(fcx.tcx()));
639 let vcx = fcx.vtable_context();
640 let vtbls = lookup_vtables(&vcx, ex.span,
641 item_ty.generics.type_param_defs(),
642 substs, is_early);
643 if !is_early {
644 insert_vtables(fcx, MethodCall::expr(ex.id), vtbls);
645 }
646 }
647 });
648 }
649
650 // Must resolve bounds on methods with bounded params
651 ast::ExprBinary(_, _, _) |
652 ast::ExprUnary(_, _) |
653 ast::ExprAssignOp(_, _, _) |
654 ast::ExprIndex(_, _) |
655 ast::ExprMethodCall(_, _, _) => {
656 match fcx.inh.method_map.borrow().find(&MethodCall::expr(ex.id)) {
657 Some(method) => {
658 debug!("vtable resolution on parameter bounds for method call {}",
659 ex.repr(fcx.tcx()));
660 let type_param_defs = ty::method_call_type_param_defs(cx.tcx, method.origin);
661 if has_trait_bounds(type_param_defs.as_slice()) {
662 let substs = fcx.method_ty_substs(ex.id);
663 let vcx = fcx.vtable_context();
664 let vtbls = lookup_vtables(&vcx, ex.span,
665 type_param_defs.as_slice(),
666 &substs, is_early);
667 if !is_early {
668 insert_vtables(fcx, MethodCall::expr(ex.id), vtbls);
669 }
670 }
671 }
672 None => {}
673 }
674 }
675 ast::ExprCast(src, _) => {
676 debug!("vtable resolution on expr {}", ex.repr(fcx.tcx()));
677 let target_ty = fcx.expr_ty(ex);
678 resolve_object_cast(src, target_ty);
679 }
680 _ => ()
681 }
682
683 // Search for auto-adjustments to find trait coercions
684 match fcx.inh.adjustments.borrow().find(&ex.id) {
685 Some(adjustment) => {
686 match *adjustment {
687 AutoDerefRef(adj) => {
688 for autoderef in range(0, adj.autoderefs) {
689 let method_call = MethodCall::autoderef(ex.id, autoderef as u32);
690 match fcx.inh.method_map.borrow().find(&method_call) {
691 Some(method) => {
692 debug!("vtable resolution on parameter bounds for autoderef {}",
693 ex.repr(fcx.tcx()));
694 let type_param_defs =
695 ty::method_call_type_param_defs(cx.tcx, method.origin);
696 if has_trait_bounds(type_param_defs.deref().as_slice()) {
697 let vcx = fcx.vtable_context();
698 let vtbls = lookup_vtables(&vcx, ex.span,
699 type_param_defs.deref()
700 .as_slice(),
701 &method.substs, is_early);
702 if !is_early {
703 insert_vtables(fcx, method_call, vtbls);
704 }
705 }
706 }
707 None => {}
708 }
709 }
710 }
711 AutoObject(store,
712 bounds,
713 def_id,
714 ref substs) => {
715 debug!("doing trait adjustment for expr {} {} \
716 (early? {})",
717 ex.id,
718 ex.repr(fcx.tcx()),
719 is_early);
720
721 let object_ty = ty::mk_trait(cx.tcx, def_id,
722 substs.clone(),
723 store, bounds);
724 resolve_object_cast(ex, object_ty);
725 }
726 AutoAddEnv(..) => {}
727 }
728 }
729 None => {}
730 }
731 }
732
733 pub fn resolve_impl(tcx: &ty::ctxt,
734 impl_item: &ast::Item,
735 impl_generics: &ty::Generics,
736 impl_trait_ref: &ty::TraitRef) {
737 let param_env = ty::construct_parameter_environment(
738 tcx,
739 None,
740 impl_generics.type_param_defs(),
741 [],
742 impl_generics.region_param_defs(),
743 [],
744 impl_item.id);
745
746 let impl_trait_ref = impl_trait_ref.subst(tcx, ¶m_env.free_substs);
747
748 let infcx = &infer::new_infer_ctxt(tcx);
749 let vcx = VtableContext { infcx: infcx, param_env: ¶m_env };
750
751 // First, check that the impl implements any trait bounds
752 // on the trait.
753 let trait_def = ty::lookup_trait_def(tcx, impl_trait_ref.def_id);
754 let vtbls = lookup_vtables(&vcx, impl_item.span,
755 trait_def.generics.type_param_defs(),
756 &impl_trait_ref.substs,
757 false);
758
759 // Now, locate the vtable for the impl itself. The real
760 // purpose of this is to check for supertrait impls,
761 // but that falls out of doing this.
762 let param_bounds = ty::ParamBounds {
763 builtin_bounds: ty::EmptyBuiltinBounds(),
764 trait_bounds: vec!(Rc::new(impl_trait_ref))
765 };
766 let t = ty::node_id_to_type(tcx, impl_item.id);
767 let t = t.subst(tcx, ¶m_env.free_substs);
768 debug!("=== Doing a self lookup now.");
769
770 // Right now, we don't have any place to store this.
771 // We will need to make one so we can use this information
772 // for compiling default methods that refer to supertraits.
773 let self_vtable_res =
774 lookup_vtables_for_param(&vcx, impl_item.span, None,
775 ¶m_bounds, t, false);
776
777
778 let res = impl_res {
779 trait_vtables: vtbls,
780 self_vtables: self_vtable_res
781 };
782 let impl_def_id = ast_util::local_def(impl_item.id);
783
784 tcx.impl_vtables.borrow_mut().insert(impl_def_id, res);
785 }
786
787 /// Resolve vtables for a method call after typeck has finished.
788 /// Used by trans to monomorphize artificial method callees (e.g. drop).
789 pub fn trans_resolve_method(tcx: &ty::ctxt, id: ast::NodeId,
790 substs: &ty::substs) -> Option<vtable_res> {
791 let generics = ty::lookup_item_type(tcx, ast_util::local_def(id)).generics;
792 let type_param_defs = &*generics.type_param_defs;
793 if has_trait_bounds(type_param_defs.as_slice()) {
794 let vcx = VtableContext {
795 infcx: &infer::new_infer_ctxt(tcx),
796 param_env: &ty::construct_parameter_environment(tcx, None, [], [], [], [], id)
797 };
798
799 Some(lookup_vtables(&vcx,
800 tcx.map.span(id),
801 type_param_defs.as_slice(),
802 substs,
803 false))
804 } else {
805 None
806 }
807 }
808
809 impl<'a, 'b> visit::Visitor<()> for &'a FnCtxt<'b> {
810 fn visit_expr(&mut self, ex: &ast::Expr, _: ()) {
811 early_resolve_expr(ex, *self, false);
812 visit::walk_expr(self, ex, ());
813 }
814 fn visit_item(&mut self, _: &ast::Item, _: ()) {
815 // no-op
816 }
817 }
818
819 // Detect points where a trait-bounded type parameter is
820 // instantiated, resolve the impls for the parameters.
821 pub fn resolve_in_block(mut fcx: &FnCtxt, bl: &ast::Block) {
822 visit::walk_block(&mut fcx, bl, ());
823 }
librustc/middle/typeck/check/vtable.rs:525:1-525:1 -fn- definition:
pub fn early_resolve_expr(ex: &ast::Expr, fcx: &FnCtxt, is_early: bool) {
debug!("vtable: early_resolve_expr() ex with id {:?} (early: {}): {}",
ex.id, is_early, expr_to_str(ex));
references:- 2810: fn visit_expr(&mut self, ex: &ast::Expr, _: ()) {
811: early_resolve_expr(ex, *self, false);
812: visit::walk_expr(self, ex, ());
librustc/middle/typeck/check/mod.rs:
1806: if check_blocks {
1807: vtable::early_resolve_expr(callee_expr, fcx, true);
1808: }
librustc/middle/typeck/check/vtable.rs:65:53-65:53 -struct- definition:
/// callback function to call in case of type error.
pub struct VtableContext<'a> {
pub infcx: &'a infer::InferCtxt<'a>,
references:- 15748: let infcx = &infer::new_infer_ctxt(tcx);
749: let vcx = VtableContext { infcx: infcx, param_env: ¶m_env };
--
793: if has_trait_bounds(type_param_defs.as_slice()) {
794: let vcx = VtableContext {
795: infcx: &infer::new_infer_ctxt(tcx),
librustc/middle/typeck/check/mod.rs:
1074: pub fn vtable_context<'a>(&'a self) -> VtableContext<'a> {
1075: VtableContext {
1076: infcx: self.infcx(),
--
1480: // variables.
1481: pub fn impl_self_ty(vcx: &VtableContext,
1482: span: Span, // (potential) receiver for this impl
librustc/middle/typeck/check/vtable.rs:
216: // Look up the vtable implementing the trait `trait_ref` at type `t`
217: fn lookup_vtable(vcx: &VtableContext,
218: span: Span,
librustc/middle/typeck/check/vtable.rs:174:1-174:1 -fn- definition:
fn relate_trait_refs(vcx: &VtableContext,
span: Span,
act_trait_ref: Rc<ty::TraitRef>,
references:- 3292: if bound_trait_ref.def_id == trait_ref.def_id {
293: relate_trait_refs(vcx, span, bound_trait_ref, trait_ref.clone());
294: let vtable = vtable_param(param, n_bound);
--
397: let of_trait_ref = of_trait_ref.subst(tcx, &substs);
398: relate_trait_refs(vcx, span, of_trait_ref, trait_ref.clone());
--
516: let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
517: relate_trait_refs(vcx, span, impl_trait_ref, trait_ref);
518: }
librustc/middle/typeck/check/vtable.rs:79:1-79:1 -fn- definition:
fn lookup_vtables(vcx: &VtableContext,
span: Span,
type_param_defs: &[ty::TypeParameterDef],
references:- 6409: ty::lookup_item_type(tcx, impl_did).generics;
410: let subres = lookup_vtables(vcx, span,
411: im_generics.type_param_defs(), &substs,
--
753: let trait_def = ty::lookup_trait_def(tcx, impl_trait_ref.def_id);
754: let vtbls = lookup_vtables(&vcx, impl_item.span,
755: trait_def.generics.type_param_defs(),
--
799: Some(lookup_vtables(&vcx,
800: tcx.map.span(id),
librustc/middle/typeck/check/vtable.rs:74:1-74:1 -fn- definition:
fn has_trait_bounds(type_param_defs: &[ty::TypeParameterDef]) -> bool {
type_param_defs.iter().any(
|type_param_def| !type_param_def.bounds.trait_bounds.is_empty())
references:- 4695: ty::method_call_type_param_defs(cx.tcx, method.origin);
696: if has_trait_bounds(type_param_defs.deref().as_slice()) {
697: let vcx = fcx.vtable_context();
--
792: let type_param_defs = &*generics.type_param_defs;
793: if has_trait_bounds(type_param_defs.as_slice()) {
794: let vcx = VtableContext {
librustc/middle/typeck/check/vtable.rs:482:1-482:1 -fn- definition:
fn fixup_ty(vcx: &VtableContext,
span: Span,
ty: ty::t,
references:- 2474: ty::EmptyBuiltinBounds());
475: fixup_ty(vcx, span, t, is_early).map(|t_f| {
476: match ty::get(t_f).sty {
librustc/middle/typeck/check/vtable.rs:519:1-519:1 -fn- definition:
fn insert_vtables(fcx: &FnCtxt, vtable_key: MethodCall, vtables: vtable_res) {
debug!("insert_vtables(vtable_key={}, vtables={:?})",
vtable_key, vtables.repr(fcx.tcx()));
references:- 4702: if !is_early {
703: insert_vtables(fcx, method_call, vtbls);
704: }
librustc/middle/typeck/check/vtable.rs:116:1-116:1 -fn- definition:
fn lookup_vtables_for_param(vcx: &VtableContext,
span: Span,
// None for substs means the identity
references:- 3578: let vtables =
579: lookup_vtables_for_param(&vcx,
580: ex.span,
--
773: let self_vtable_res =
774: lookup_vtables_for_param(&vcx, impl_item.span, None,
775: ¶m_bounds, t, false);
librustc/middle/typeck/check/vtable.rs:277:46-277:46 -fn- definition:
// of them are the vtable we are looking for.
fn lookup_vtable_from_bounds(vcx: &VtableContext,
span: Span,
references:- 2247: env_bounds.get(n).trait_bounds.as_slice();
248: lookup_vtable_from_bounds(vcx, span,
249: type_param_bounds,
--
258: let self_param_bound = vcx.param_env.self_param_bound.clone().unwrap();
259: lookup_vtable_from_bounds(vcx, span,
260: [self_param_bound],