1 // Copyright 2012-2013 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 // Coherence phase
12 //
13 // The job of the coherence phase of typechecking is to ensure that each trait
14 // has at most one implementation for each type. Then we build a mapping from
15 // each trait in the system to its implementations.
16
17
18 use metadata::csearch::{each_impl, get_impl_trait, each_implementation_for_trait};
19 use metadata::csearch;
20 use middle::ty::get;
21 use middle::ty::{ImplContainer, lookup_item_type, subst};
22 use middle::ty::{substs, t, ty_bool, ty_char, ty_bot, ty_box, ty_enum, ty_err};
23 use middle::ty::{ty_str, ty_vec, ty_float, ty_infer, ty_int, ty_nil};
24 use middle::ty::{ty_param, ty_param_bounds_and_ty, ty_ptr};
25 use middle::ty::{ty_rptr, ty_self, ty_struct, ty_trait, ty_tup};
26 use middle::ty::{ty_uint, ty_uniq, ty_bare_fn, ty_closure};
27 use middle::ty::type_is_ty_var;
28 use middle::subst::Subst;
29 use middle::ty;
30 use middle::typeck::CrateCtxt;
31 use middle::typeck::infer::combine::Combine;
32 use middle::typeck::infer::InferCtxt;
33 use middle::typeck::infer::{new_infer_ctxt, resolve_ivar, resolve_type};
34 use middle::typeck::infer;
35 use util::ppaux::Repr;
36 use syntax::ast::{Crate, DefId, DefStruct, DefTy};
37 use syntax::ast::{Item, ItemEnum, ItemImpl, ItemMod, ItemStruct};
38 use syntax::ast::{LOCAL_CRATE, TraitRef, TyPath};
39 use syntax::ast;
40 use syntax::ast_map::NodeItem;
41 use syntax::ast_map;
42 use syntax::ast_util::{def_id_of_def, local_def};
43 use syntax::codemap::Span;
44 use syntax::owned_slice::OwnedSlice;
45 use syntax::parse::token;
46 use syntax::visit;
47
48 use collections::HashSet;
49 use std::cell::RefCell;
50 use std::rc::Rc;
51
52 struct UniversalQuantificationResult {
53 monotype: t,
54 type_variables: Vec<ty::t> ,
55 type_param_defs: Rc<Vec<ty::TypeParameterDef> >
56 }
57
58 fn get_base_type(inference_context: &InferCtxt,
59 span: Span,
60 original_type: t)
61 -> Option<t> {
62 let resolved_type;
63 match resolve_type(inference_context,
64 original_type,
65 resolve_ivar) {
66 Ok(resulting_type) if !type_is_ty_var(resulting_type) => {
67 resolved_type = resulting_type;
68 }
69 _ => {
70 inference_context.tcx.sess.span_fatal(span,
71 "the type of this value must be known in order \
72 to determine the base type");
73 }
74 }
75
76 match get(resolved_type).sty {
77 ty_enum(..) | ty_trait(..) | ty_struct(..) => {
78 debug!("(getting base type) found base type");
79 Some(resolved_type)
80 }
81
82 ty_nil | ty_bot | ty_bool | ty_char | ty_int(..) | ty_uint(..) | ty_float(..) |
83 ty_str(..) | ty_vec(..) | ty_bare_fn(..) | ty_closure(..) | ty_tup(..) |
84 ty_infer(..) | ty_param(..) | ty_self(..) | ty_err |
85 ty_box(_) | ty_uniq(_) | ty_ptr(_) | ty_rptr(_, _) => {
86 debug!("(getting base type) no base type; found {:?}",
87 get(original_type).sty);
88 None
89 }
90 }
91 }
92
93 fn type_is_defined_in_local_crate(original_type: t) -> bool {
94 /*!
95 *
96 * For coherence, when we have `impl Trait for Type`, we need to
97 * guarantee that `Type` is "local" to the
98 * crate. For our purposes, this means that it must contain
99 * some nominal type defined in this crate.
100 */
101
102 let mut found_nominal = false;
103 ty::walk_ty(original_type, |t| {
104 match get(t).sty {
105 ty_enum(def_id, _) |
106 ty_trait(box ty::TyTrait { def_id, .. }) |
107 ty_struct(def_id, _) => {
108 if def_id.krate == ast::LOCAL_CRATE {
109 found_nominal = true;
110 }
111 }
112
113 _ => { }
114 }
115 });
116 return found_nominal;
117 }
118
119 // Returns the def ID of the base type, if there is one.
120 fn get_base_type_def_id(inference_context: &InferCtxt,
121 span: Span,
122 original_type: t)
123 -> Option<DefId> {
124 match get_base_type(inference_context, span, original_type) {
125 None => {
126 return None;
127 }
128 Some(base_type) => {
129 match get(base_type).sty {
130 ty_enum(def_id, _) |
131 ty_struct(def_id, _) |
132 ty_trait(box ty::TyTrait { def_id, .. }) => {
133 return Some(def_id);
134 }
135 _ => {
136 fail!("get_base_type() returned a type that wasn't an \
137 enum, struct, or trait");
138 }
139 }
140 }
141 }
142 }
143
144 struct CoherenceChecker<'a> {
145 crate_context: &'a CrateCtxt<'a>,
146 inference_context: InferCtxt<'a>,
147 }
148
149 struct CoherenceCheckVisitor<'a> {
150 cc: &'a CoherenceChecker<'a>
151 }
152
153 impl<'a> visit::Visitor<()> for CoherenceCheckVisitor<'a> {
154 fn visit_item(&mut self, item: &Item, _: ()) {
155
156 //debug!("(checking coherence) item '{}'", token::get_ident(item.ident));
157
158 match item.node {
159 ItemImpl(_, ref opt_trait, _, _) => {
160 match opt_trait.clone() {
161 Some(opt_trait) => {
162 self.cc.check_implementation(item, [opt_trait]);
163 }
164 None => self.cc.check_implementation(item, [])
165 }
166 }
167 _ => {
168 // Nothing to do.
169 }
170 };
171
172 visit::walk_item(self, item, ());
173 }
174 }
175
176 struct PrivilegedScopeVisitor<'a> { cc: &'a CoherenceChecker<'a> }
177
178 impl<'a> visit::Visitor<()> for PrivilegedScopeVisitor<'a> {
179 fn visit_item(&mut self, item: &Item, _: ()) {
180
181 match item.node {
182 ItemMod(ref module_) => {
183 // Then visit the module items.
184 visit::walk_mod(self, module_, ());
185 }
186 ItemImpl(_, None, ast_ty, _) => {
187 if !self.cc.ast_type_is_defined_in_local_crate(ast_ty) {
188 // This is an error.
189 let session = &self.cc.crate_context.tcx.sess;
190 session.span_err(item.span,
191 "cannot associate methods with a type outside the \
192 crate the type is defined in; define and implement \
193 a trait or new type instead");
194 }
195 }
196 ItemImpl(_, Some(ref trait_ref), _, _) => {
197 // `for_ty` is `Type` in `impl Trait for Type`
198 let for_ty =
199 ty::node_id_to_type(self.cc.crate_context.tcx,
200 item.id);
201 if !type_is_defined_in_local_crate(for_ty) {
202 // This implementation is not in scope of its base
203 // type. This still might be OK if the trait is
204 // defined in the same crate.
205
206 let trait_def_id =
207 self.cc.trait_ref_to_trait_def_id(trait_ref);
208
209 if trait_def_id.krate != LOCAL_CRATE {
210 let session = &self.cc.crate_context.tcx.sess;
211 session.span_err(item.span,
212 "cannot provide an extension implementation \
213 where both trait and type are not defined in this crate");
214 }
215 }
216
217 visit::walk_item(self, item, ());
218 }
219 _ => {
220 visit::walk_item(self, item, ());
221 }
222 }
223 }
224 }
225
226 impl<'a> CoherenceChecker<'a> {
227 fn check(&self, krate: &Crate) {
228 // Check implementations and traits. This populates the tables
229 // containing the inherent methods and extension methods. It also
230 // builds up the trait inheritance table.
231 let mut visitor = CoherenceCheckVisitor { cc: self };
232 visit::walk_crate(&mut visitor, krate, ());
233
234 // Check that there are no overlapping trait instances
235 self.check_implementation_coherence();
236
237 // Check whether traits with base types are in privileged scopes.
238 self.check_privileged_scopes(krate);
239
240 // Bring in external crates. It's fine for this to happen after the
241 // coherence checks, because we ensure by construction that no errors
242 // can happen at link time.
243 self.add_external_crates();
244
245 // Populate the table of destructors. It might seem a bit strange to
246 // do this here, but it's actually the most convenient place, since
247 // the coherence tables contain the trait -> type mappings.
248 self.populate_destructor_table();
249 }
250
251 fn check_implementation(&self, item: &Item,
252 associated_traits: &[TraitRef]) {
253 let tcx = self.crate_context.tcx;
254 let impl_did = local_def(item.id);
255 let self_type = ty::lookup_item_type(tcx, impl_did);
256
257 // If there are no traits, then this implementation must have a
258 // base type.
259
260 if associated_traits.len() == 0 {
261 debug!("(checking implementation) no associated traits for item '{}'",
262 token::get_ident(item.ident));
263
264 match get_base_type_def_id(&self.inference_context,
265 item.span,
266 self_type.ty) {
267 None => {
268 let session = &self.crate_context.tcx.sess;
269 session.span_err(item.span,
270 "no base type found for inherent implementation; \
271 implement a trait or new type instead");
272 }
273 Some(_) => {
274 // Nothing to do.
275 }
276 }
277 }
278
279 let impl_methods = self.create_impl_from_item(item);
280
281 for associated_trait in associated_traits.iter() {
282 let trait_ref = ty::node_id_to_trait_ref(
283 self.crate_context.tcx, associated_trait.ref_id);
284 debug!("(checking implementation) adding impl for trait '{}', item '{}'",
285 trait_ref.repr(self.crate_context.tcx),
286 token::get_ident(item.ident));
287
288 self.add_trait_impl(trait_ref.def_id, impl_did);
289 }
290
291 // Add the implementation to the mapping from implementation to base
292 // type def ID, if there is a base type for this implementation and
293 // the implementation does not have any associated traits.
294 match get_base_type_def_id(&self.inference_context,
295 item.span,
296 self_type.ty) {
297 None => {
298 // Nothing to do.
299 }
300 Some(base_type_def_id) => {
301 // FIXME: Gather up default methods?
302 if associated_traits.len() == 0 {
303 self.add_inherent_impl(base_type_def_id, impl_did);
304 }
305 }
306 }
307
308 tcx.impl_methods.borrow_mut().insert(impl_did, impl_methods);
309 }
310
311 // Creates default method IDs and performs type substitutions for an impl
312 // and trait pair. Then, for each provided method in the trait, inserts a
313 // `ProvidedMethodInfo` instance into the `provided_method_sources` map.
314 fn instantiate_default_methods(&self, impl_id: DefId,
315 trait_ref: &ty::TraitRef,
316 all_methods: &mut Vec<DefId>) {
317 let tcx = self.crate_context.tcx;
318 debug!("instantiate_default_methods(impl_id={:?}, trait_ref={})",
319 impl_id, trait_ref.repr(tcx));
320
321 let impl_poly_type = ty::lookup_item_type(tcx, impl_id);
322
323 let prov = ty::provided_trait_methods(tcx, trait_ref.def_id);
324 for trait_method in prov.iter() {
325 // Synthesize an ID.
326 let new_id = tcx.sess.next_node_id();
327 let new_did = local_def(new_id);
328
329 debug!("new_did={:?} trait_method={}", new_did, trait_method.repr(tcx));
330
331 // Create substitutions for the various trait parameters.
332 let new_method_ty =
333 Rc::new(subst_receiver_types_in_method_ty(
334 tcx,
335 impl_id,
336 trait_ref,
337 new_did,
338 &**trait_method,
339 Some(trait_method.def_id)));
340
341 debug!("new_method_ty={}", new_method_ty.repr(tcx));
342 all_methods.push(new_did);
343
344 // construct the polytype for the method based on the method_ty
345 let new_generics = ty::Generics {
346 type_param_defs:
347 Rc::new(Vec::from_slice(impl_poly_type.generics.type_param_defs()).append(
348 new_method_ty.generics.type_param_defs())),
349 region_param_defs:
350 Rc::new(Vec::from_slice(impl_poly_type.generics.region_param_defs()).append(
351 new_method_ty.generics.region_param_defs()))
352 };
353 let new_polytype = ty::ty_param_bounds_and_ty {
354 generics: new_generics,
355 ty: ty::mk_bare_fn(tcx, new_method_ty.fty.clone())
356 };
357 debug!("new_polytype={}", new_polytype.repr(tcx));
358
359 tcx.tcache.borrow_mut().insert(new_did, new_polytype);
360 tcx.methods.borrow_mut().insert(new_did, new_method_ty);
361
362 // Pair the new synthesized ID up with the
363 // ID of the method.
364 self.crate_context.tcx.provided_method_sources.borrow_mut()
365 .insert(new_did, trait_method.def_id);
366 }
367 }
368
369 fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
370 let tcx = self.crate_context.tcx;
371 match tcx.inherent_impls.borrow().find(&base_def_id) {
372 Some(implementation_list) => {
373 implementation_list.borrow_mut().push(impl_def_id);
374 return;
375 }
376 None => {}
377 }
378
379 tcx.inherent_impls.borrow_mut().insert(base_def_id,
380 Rc::new(RefCell::new(vec!(impl_def_id))));
381 }
382
383 fn add_trait_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
384 ty::record_trait_implementation(self.crate_context.tcx,
385 base_def_id,
386 impl_def_id);
387 }
388
389 fn check_implementation_coherence(&self) {
390 for &trait_id in self.crate_context.tcx.trait_impls.borrow().keys() {
391 self.check_implementation_coherence_of(trait_id);
392 }
393 }
394
395 fn check_implementation_coherence_of(&self, trait_def_id: DefId) {
396 // Unify pairs of polytypes.
397 self.iter_impls_of_trait_local(trait_def_id, |impl_a| {
398 let polytype_a =
399 self.get_self_type_for_implementation(impl_a);
400
401 // "We have an impl of trait <trait_def_id> for type <polytype_a>,
402 // and that impl is <impl_a>"
403 self.iter_impls_of_trait(trait_def_id, |impl_b| {
404
405 // An impl is coherent with itself
406 if impl_a != impl_b {
407 let polytype_b = self.get_self_type_for_implementation(
408 impl_b);
409
410 if self.polytypes_unify(polytype_a.clone(), polytype_b) {
411 let session = &self.crate_context.tcx.sess;
412 session.span_err(
413 self.span_of_impl(impl_a),
414 format!("conflicting implementations for trait `{}`",
415 ty::item_path_str(self.crate_context.tcx,
416 trait_def_id)));
417 if impl_b.krate == LOCAL_CRATE {
418 session.span_note(self.span_of_impl(impl_b),
419 "note conflicting implementation here");
420 } else {
421 let crate_store = &self.crate_context.tcx.sess.cstore;
422 let cdata = crate_store.get_crate_data(impl_b.krate);
423 session.note(
424 "conflicting implementation in crate `" + cdata.name + "`");
425 }
426 }
427 }
428 })
429 })
430 }
431
432 fn iter_impls_of_trait(&self, trait_def_id: DefId, f: |DefId|) {
433 self.iter_impls_of_trait_local(trait_def_id, |x| f(x));
434
435 if trait_def_id.krate == LOCAL_CRATE {
436 return;
437 }
438
439 let crate_store = &self.crate_context.tcx.sess.cstore;
440 csearch::each_implementation_for_trait(crate_store, trait_def_id, |impl_def_id| {
441 // Is this actually necessary?
442 let _ = lookup_item_type(self.crate_context.tcx, impl_def_id);
443 f(impl_def_id);
444 });
445 }
446
447 fn iter_impls_of_trait_local(&self, trait_def_id: DefId, f: |DefId|) {
448 match self.crate_context.tcx.trait_impls.borrow().find(&trait_def_id) {
449 Some(impls) => {
450 for &impl_did in impls.borrow().iter() {
451 f(impl_did);
452 }
453 }
454 None => { /* no impls? */ }
455 }
456 }
457
458 fn polytypes_unify(&self,
459 polytype_a: ty_param_bounds_and_ty,
460 polytype_b: ty_param_bounds_and_ty)
461 -> bool {
462 let universally_quantified_a =
463 self.universally_quantify_polytype(polytype_a);
464 let universally_quantified_b =
465 self.universally_quantify_polytype(polytype_b);
466
467 return self.can_unify_universally_quantified(
468 &universally_quantified_a, &universally_quantified_b) ||
469 self.can_unify_universally_quantified(
470 &universally_quantified_b, &universally_quantified_a);
471 }
472
473 // Converts a polytype to a monotype by replacing all parameters with
474 // type variables. Returns the monotype and the type variables created.
475 fn universally_quantify_polytype(&self, polytype: ty_param_bounds_and_ty)
476 -> UniversalQuantificationResult {
477 let region_parameters =
478 polytype.generics.region_param_defs().iter()
479 .map(|d| self.inference_context.next_region_var(
480 infer::BoundRegionInCoherence(d.name)))
481 .collect();
482
483 let bounds_count = polytype.generics.type_param_defs().len();
484 let type_parameters = self.inference_context.next_ty_vars(bounds_count);
485
486 let substitutions = substs {
487 regions: ty::NonerasedRegions(region_parameters),
488 self_ty: None,
489 tps: type_parameters
490 };
491 let monotype = subst(self.crate_context.tcx,
492 &substitutions,
493 polytype.ty);
494
495 UniversalQuantificationResult {
496 monotype: monotype,
497 type_variables: substitutions.tps,
498 type_param_defs: polytype.generics.type_param_defs.clone()
499 }
500 }
501
502 fn can_unify_universally_quantified<'a>(&self,
503 a: &'a UniversalQuantificationResult,
504 b: &'a UniversalQuantificationResult)
505 -> bool {
506 infer::can_mk_subty(&self.inference_context,
507 a.monotype,
508 b.monotype).is_ok()
509 }
510
511 fn get_self_type_for_implementation(&self, impl_did: DefId)
512 -> ty_param_bounds_and_ty {
513 self.crate_context.tcx.tcache.borrow().get_copy(&impl_did)
514 }
515
516 // Privileged scope checking
517 fn check_privileged_scopes(&self, krate: &Crate) {
518 let mut visitor = PrivilegedScopeVisitor{ cc: self };
519 visit::walk_crate(&mut visitor, krate, ());
520 }
521
522 fn trait_ref_to_trait_def_id(&self, trait_ref: &TraitRef) -> DefId {
523 let def_map = &self.crate_context.tcx.def_map;
524 let trait_def = def_map.borrow().get_copy(&trait_ref.ref_id);
525 let trait_id = def_id_of_def(trait_def);
526 return trait_id;
527 }
528
529 /// For coherence, when we have `impl Type`, we need to guarantee that
530 /// `Type` is "local" to the crate. For our purposes, this means that it
531 /// must precisely name some nominal type defined in this crate.
532 fn ast_type_is_defined_in_local_crate(&self, original_type: &ast::Ty) -> bool {
533 match original_type.node {
534 TyPath(_, _, path_id) => {
535 match self.crate_context.tcx.def_map.borrow().get_copy(&path_id) {
536 DefTy(def_id) | DefStruct(def_id) => {
537 if def_id.krate != LOCAL_CRATE {
538 return false;
539 }
540
541 // Make sure that this type precisely names a nominal
542 // type.
543 match self.crate_context.tcx.map.find(def_id.node) {
544 None => {
545 self.crate_context.tcx.sess.span_bug(
546 original_type.span,
547 "resolve didn't resolve this type?!");
548 }
549 Some(NodeItem(item)) => {
550 match item.node {
551 ItemStruct(..) | ItemEnum(..) => true,
552 _ => false,
553 }
554 }
555 Some(_) => false,
556 }
557 }
558 _ => false
559 }
560 }
561 _ => false
562 }
563 }
564
565 // Converts an implementation in the AST to a vector of methods.
566 fn create_impl_from_item(&self, item: &Item) -> Vec<DefId> {
567 match item.node {
568 ItemImpl(_, ref trait_refs, _, ref ast_methods) => {
569 let mut methods: Vec<DefId> = ast_methods.iter().map(|ast_method| {
570 local_def(ast_method.id)
571 }).collect();
572
573 for trait_ref in trait_refs.iter() {
574 let ty_trait_ref = ty::node_id_to_trait_ref(
575 self.crate_context.tcx,
576 trait_ref.ref_id);
577
578 self.instantiate_default_methods(local_def(item.id),
579 &*ty_trait_ref,
580 &mut methods);
581 }
582
583 methods
584 }
585 _ => {
586 self.crate_context.tcx.sess.span_bug(item.span,
587 "can't convert a non-impl to an impl");
588 }
589 }
590 }
591
592 fn span_of_impl(&self, impl_did: DefId) -> Span {
593 assert_eq!(impl_did.krate, LOCAL_CRATE);
594 self.crate_context.tcx.map.span(impl_did.node)
595 }
596
597 // External crate handling
598
599 fn add_external_impl(&self,
600 impls_seen: &mut HashSet<DefId>,
601 impl_def_id: DefId) {
602 let tcx = self.crate_context.tcx;
603 let methods = csearch::get_impl_methods(&tcx.sess.cstore, impl_def_id);
604
605 // Make sure we don't visit the same implementation multiple times.
606 if !impls_seen.insert(impl_def_id) {
607 // Skip this one.
608 return
609 }
610 // Good. Continue.
611
612 let _ = lookup_item_type(tcx, impl_def_id);
613 let associated_traits = get_impl_trait(tcx, impl_def_id);
614
615 // Do a sanity check.
616 assert!(associated_traits.is_some());
617
618 // Record all the trait methods.
619 for trait_ref in associated_traits.iter() {
620 self.add_trait_impl(trait_ref.def_id, impl_def_id);
621 }
622
623 // For any methods that use a default implementation, add them to
624 // the map. This is a bit unfortunate.
625 for &method_def_id in methods.iter() {
626 for &source in ty::method(tcx, method_def_id).provided_source.iter() {
627 tcx.provided_method_sources.borrow_mut().insert(method_def_id, source);
628 }
629 }
630
631 tcx.impl_methods.borrow_mut().insert(impl_def_id, methods);
632 }
633
634 // Adds implementations and traits from external crates to the coherence
635 // info.
636 fn add_external_crates(&self) {
637 let mut impls_seen = HashSet::new();
638
639 let crate_store = &self.crate_context.tcx.sess.cstore;
640 crate_store.iter_crate_data(|crate_number, _crate_metadata| {
641 each_impl(crate_store, crate_number, |def_id| {
642 assert_eq!(crate_number, def_id.krate);
643 self.add_external_impl(&mut impls_seen, def_id)
644 })
645 })
646 }
647
648 //
649 // Destructors
650 //
651
652 fn populate_destructor_table(&self) {
653 let tcx = self.crate_context.tcx;
654 let drop_trait = match tcx.lang_items.drop_trait() {
655 Some(id) => id, None => { return }
656 };
657
658 let impl_methods = tcx.impl_methods.borrow();
659 let trait_impls = match tcx.trait_impls.borrow().find_copy(&drop_trait) {
660 None => return, // No types with (new-style) dtors present.
661 Some(found_impls) => found_impls
662 };
663
664 for &impl_did in trait_impls.borrow().iter() {
665 let methods = impl_methods.get(&impl_did);
666 if methods.len() < 1 {
667 // We'll error out later. For now, just don't ICE.
668 continue;
669 }
670 let method_def_id = *methods.get(0);
671
672 let self_type = self.get_self_type_for_implementation(impl_did);
673 match ty::get(self_type.ty).sty {
674 ty::ty_enum(type_def_id, _) |
675 ty::ty_struct(type_def_id, _) => {
676 tcx.destructor_for_type.borrow_mut().insert(type_def_id,
677 method_def_id);
678 tcx.destructors.borrow_mut().insert(method_def_id);
679 }
680 _ => {
681 // Destructors only work on nominal types.
682 if impl_did.krate == ast::LOCAL_CRATE {
683 {
684 match tcx.map.find(impl_did.node) {
685 Some(ast_map::NodeItem(item)) => {
686 tcx.sess.span_err((*item).span,
687 "the Drop trait may \
688 only be implemented \
689 on structures");
690 }
691 _ => {
692 tcx.sess.bug("didn't find impl in ast \
693 map");
694 }
695 }
696 }
697 } else {
698 tcx.sess.bug("found external impl of Drop trait on \
699 something other than a struct");
700 }
701 }
702 }
703 }
704 }
705 }
706
707 pub fn make_substs_for_receiver_types(tcx: &ty::ctxt,
708 impl_id: ast::DefId,
709 trait_ref: &ty::TraitRef,
710 method: &ty::Method)
711 -> ty::substs {
712 /*!
713 * Substitutes the values for the receiver's type parameters
714 * that are found in method, leaving the method's type parameters
715 * intact. This is in fact a mildly complex operation,
716 * largely because of the hokey way that we concatenate the
717 * receiver and method generics.
718 */
719
720 let impl_polytype = ty::lookup_item_type(tcx, impl_id);
721 let num_impl_tps = impl_polytype.generics.type_param_defs().len();
722 let num_impl_regions = impl_polytype.generics.region_param_defs().len();
723 let meth_tps: Vec<ty::t> =
724 method.generics.type_param_defs().iter().enumerate()
725 .map(|(i, t)| ty::mk_param(tcx, i + num_impl_tps, t.def_id))
726 .collect();
727 let meth_regions: Vec<ty::Region> =
728 method.generics.region_param_defs().iter().enumerate()
729 .map(|(i, l)| ty::ReEarlyBound(l.def_id.node, i + num_impl_regions, l.name))
730 .collect();
731 let mut combined_tps = trait_ref.substs.tps.clone();
732 combined_tps.push_all_move(meth_tps);
733 let combined_regions = match &trait_ref.substs.regions {
734 &ty::ErasedRegions =>
735 fail!("make_substs_for_receiver_types: unexpected ErasedRegions"),
736
737 &ty::NonerasedRegions(ref rs) => {
738 let mut rs = rs.clone().into_vec();
739 rs.push_all_move(meth_regions);
740 ty::NonerasedRegions(OwnedSlice::from_vec(rs))
741 }
742 };
743
744 ty::substs {
745 regions: combined_regions,
746 self_ty: trait_ref.substs.self_ty,
747 tps: combined_tps
748 }
749 }
750
751 fn subst_receiver_types_in_method_ty(tcx: &ty::ctxt,
752 impl_id: ast::DefId,
753 trait_ref: &ty::TraitRef,
754 new_def_id: ast::DefId,
755 method: &ty::Method,
756 provided_source: Option<ast::DefId>)
757 -> ty::Method {
758
759 let combined_substs = make_substs_for_receiver_types(
760 tcx, impl_id, trait_ref, method);
761
762 ty::Method::new(
763 method.ident,
764
765 // method types *can* appear in the generic bounds
766 method.generics.subst(tcx, &combined_substs),
767
768 // method types *can* appear in the fty
769 method.fty.subst(tcx, &combined_substs),
770
771 method.explicit_self,
772 method.vis,
773 new_def_id,
774 ImplContainer(impl_id),
775 provided_source
776 )
777 }
778
779 pub fn check_coherence(crate_context: &CrateCtxt, krate: &Crate) {
780 CoherenceChecker {
781 crate_context: crate_context,
782 inference_context: new_infer_ctxt(crate_context.tcx),
783 }.check(krate);
784 }
librustc/middle/typeck/coherence.rs:706:1-706:1 -fn- definition:
pub fn make_substs_for_receiver_types(tcx: &ty::ctxt,
impl_id: ast::DefId,
trait_ref: &ty::TraitRef,
references:- 2759: let combined_substs = make_substs_for_receiver_types(
760: tcx, impl_id, trait_ref, method);
librustc/middle/trans/callee.rs:
319: // Compute the first substitution
320: let first_subst = make_substs_for_receiver_types(
321: tcx, impl_id, &*trait_ref, &*method);
librustc/middle/typeck/coherence.rs:148:1-148:1 -struct- definition:
struct CoherenceCheckVisitor<'a> {
cc: &'a CoherenceChecker<'a>
}
references:- 2153: impl<'a> visit::Visitor<()> for CoherenceCheckVisitor<'a> {
154: fn visit_item(&mut self, item: &Item, _: ()) {
--
230: // builds up the trait inheritance table.
231: let mut visitor = CoherenceCheckVisitor { cc: self };
232: visit::walk_crate(&mut visitor, krate, ());
librustc/middle/typeck/coherence.rs:119:57-119:57 -fn- definition:
// Returns the def ID of the base type, if there is one.
fn get_base_type_def_id(inference_context: &InferCtxt,
span: Span,
references:- 2293: // the implementation does not have any associated traits.
294: match get_base_type_def_id(&self.inference_context,
295: item.span,
librustc/middle/typeck/coherence.rs:51:1-51:1 -struct- definition:
struct UniversalQuantificationResult {
monotype: t,
type_variables: Vec<ty::t> ,
references:- 4495: UniversalQuantificationResult {
496: monotype: monotype,
--
503: a: &'a UniversalQuantificationResult,
504: b: &'a UniversalQuantificationResult)
505: -> bool {
librustc/middle/typeck/coherence.rs:175:1-175:1 -struct- definition:
struct PrivilegedScopeVisitor<'a> { cc: &'a CoherenceChecker<'a> }
impl<'a> visit::Visitor<()> for PrivilegedScopeVisitor<'a> {
fn visit_item(&mut self, item: &Item, _: ()) {
references:- 2517: fn check_privileged_scopes(&self, krate: &Crate) {
518: let mut visitor = PrivilegedScopeVisitor{ cc: self };
519: visit::walk_crate(&mut visitor, krate, ());
librustc/middle/typeck/coherence.rs:143:1-143:1 -struct- definition:
struct CoherenceChecker<'a> {
crate_context: &'a CrateCtxt<'a>,
inference_context: InferCtxt<'a>,
references:- 4779: pub fn check_coherence(crate_context: &CrateCtxt, krate: &Crate) {
780: CoherenceChecker {
781: crate_context: crate_context,