src/librustc/traits/util.rs

   1 use errors::DiagnosticBuilder;
   2 use smallvec::SmallVec;
   3 use syntax_pos::Span;
   4
   5 use crate::hir;
   6 use crate::hir::def_id::DefId;
   7 use crate::ty::{self, Ty, TyCtxt, ToPredicate, ToPolyTraitRef};
   8 use crate::ty::outlives::Component;
   9 use crate::ty::subst::{GenericArg, Subst, SubstsRef};
  10 use crate::util::nodemap::FxHashSet;
  11
  12 use super::{Obligation, ObligationCause, PredicateObligation, SelectionContext, Normalized};
  13
  14 fn anonymize_predicate<'tcx>(tcx: TyCtxt<'tcx>, pred: &ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
  15     match *pred {
  16         ty::Predicate::Trait(ref data) =>
  17             ty::Predicate::Trait(tcx.anonymize_late_bound_regions(data)),
  18
  19         ty::Predicate::RegionOutlives(ref data) =>
  20             ty::Predicate::RegionOutlives(tcx.anonymize_late_bound_regions(data)),
  21
  22         ty::Predicate::TypeOutlives(ref data) =>
  23             ty::Predicate::TypeOutlives(tcx.anonymize_late_bound_regions(data)),
  24
  25         ty::Predicate::Projection(ref data) =>
  26             ty::Predicate::Projection(tcx.anonymize_late_bound_regions(data)),
  27
  28         ty::Predicate::WellFormed(data) =>
  29             ty::Predicate::WellFormed(data),
  30
  31         ty::Predicate::ObjectSafe(data) =>
  32             ty::Predicate::ObjectSafe(data),
  33
  34         ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) =>
  35             ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind),
  36
  37         ty::Predicate::Subtype(ref data) =>
  38             ty::Predicate::Subtype(tcx.anonymize_late_bound_regions(data)),
  39
  40         ty::Predicate::ConstEvaluatable(def_id, substs) =>
  41             ty::Predicate::ConstEvaluatable(def_id, substs),
  42     }
  43 }
  44
  45 struct PredicateSet<'tcx> {
  46     tcx: TyCtxt<'tcx>,
  47     set: FxHashSet<ty::Predicate<'tcx>>,
  48 }
  49
  50 impl PredicateSet<'tcx> {
  51     fn new(tcx: TyCtxt<'tcx>) -> Self {
  52         Self { tcx: tcx, set: Default::default() }
  53     }
  54
  55     fn insert(&mut self, pred: &ty::Predicate<'tcx>) -> bool {
  56         // We have to be careful here because we want
  57         //
  58         //    for<'a> Foo<&'a int>
  59         //
  60         // and
  61         //
  62         //    for<'b> Foo<&'b int>
  63         //
  64         // to be considered equivalent. So normalize all late-bound
  65         // regions before we throw things into the underlying set.
  66         self.set.insert(anonymize_predicate(self.tcx, pred))
  67     }
  68 }
  69
  70 impl<T: AsRef<ty::Predicate<'tcx>>> Extend<T> for PredicateSet<'tcx> {
  71     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
  72         for pred in iter {
  73             self.insert(pred.as_ref());
  74         }
  75     }
  76 }
  77
  78 ///////////////////////////////////////////////////////////////////////////
  79 // `Elaboration` iterator
  80 ///////////////////////////////////////////////////////////////////////////
  81
  82 /// "Elaboration" is the process of identifying all the predicates that
  83 /// are implied by a source predicate. Currently, this basically means
  84 /// walking the "supertraits" and other similar assumptions. For example,
  85 /// if we know that `T: Ord`, the elaborator would deduce that `T: PartialOrd`
  86 /// holds as well. Similarly, if we have `trait Foo: 'static`, and we know that
  87 /// `T: Foo`, then we know that `T: 'static`.
  88 pub struct Elaborator<'tcx> {
  89     stack: Vec<ty::Predicate<'tcx>>,
  90     visited: PredicateSet<'tcx>,
  91 }
  92
  93 pub fn elaborate_trait_ref<'tcx>(
  94     tcx: TyCtxt<'tcx>,
  95     trait_ref: ty::PolyTraitRef<'tcx>,
  96 ) -> Elaborator<'tcx> {
  97     elaborate_predicates(tcx, vec![trait_ref.to_predicate()])
  98 }
  99
 100 pub fn elaborate_trait_refs<'tcx>(
 101     tcx: TyCtxt<'tcx>,
 102     trait_refs: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
 103 ) -> Elaborator<'tcx> {
 104     let predicates = trait_refs.map(|trait_ref| trait_ref.to_predicate()).collect();
 105     elaborate_predicates(tcx, predicates)
 106 }
 107
 108 pub fn elaborate_predicates<'tcx>(
 109     tcx: TyCtxt<'tcx>,
 110     mut predicates: Vec<ty::Predicate<'tcx>>,
 111 ) -> Elaborator<'tcx> {
 112     let mut visited = PredicateSet::new(tcx);
 113     predicates.retain(|pred| visited.insert(pred));
 114     Elaborator { stack: predicates, visited }
 115 }
 116
 117 impl Elaborator<'tcx> {
 118     pub fn filter_to_traits(self) -> FilterToTraits<Self> {
 119         FilterToTraits::new(self)
 120     }
 121
 122     fn elaborate(&mut self, predicate: &ty::Predicate<'tcx>) {
 123         let tcx = self.visited.tcx;
 124         match *predicate {
 125             ty::Predicate::Trait(ref data) => {
 126                 // Get predicates declared on the trait.
 127                 let predicates = tcx.super_predicates_of(data.def_id());
 128
 129                 let predicates = predicates.predicates
 130                     .iter()
 131                     .map(|(pred, _)| pred.subst_supertrait(tcx, &data.to_poly_trait_ref()));
 132                 debug!("super_predicates: data={:?} predicates={:?}",
 133                        data, predicates.clone());
 134
 135                 // Only keep those bounds that we haven't already seen.
 136                 // This is necessary to prevent infinite recursion in some
 137                 // cases. One common case is when people define
 138                 // `trait Sized: Sized { }` rather than `trait Sized { }`.
 139                 let visited = &mut self.visited;
 140                 let predicates = predicates.filter(|pred| visited.insert(pred));
 141
 142                 self.stack.extend(predicates);
 143             }
 144             ty::Predicate::WellFormed(..) => {
 145                 // Currently, we do not elaborate WF predicates,
 146                 // although we easily could.
 147             }
 148             ty::Predicate::ObjectSafe(..) => {
 149                 // Currently, we do not elaborate object-safe
 150                 // predicates.
 151             }
 152             ty::Predicate::Subtype(..) => {
 153                 // Currently, we do not "elaborate" predicates like `X <: Y`,
 154                 // though conceivably we might.
 155             }
 156             ty::Predicate::Projection(..) => {
 157                 // Nothing to elaborate in a projection predicate.
 158             }
 159             ty::Predicate::ClosureKind(..) => {
 160                 // Nothing to elaborate when waiting for a closure's kind to be inferred.
 161             }
 162             ty::Predicate::ConstEvaluatable(..) => {
 163                 // Currently, we do not elaborate const-evaluatable
 164                 // predicates.
 165             }
 166             ty::Predicate::RegionOutlives(..) => {
 167                 // Nothing to elaborate from `'a: 'b`.
 168             }
 169             ty::Predicate::TypeOutlives(ref data) => {
 170                 // We know that `T: 'a` for some type `T`. We can
 171                 // often elaborate this. For example, if we know that
 172                 // `[U]: 'a`, that implies that `U: 'a`. Similarly, if
 173                 // we know `&'a U: 'b`, then we know that `'a: 'b` and
 174                 // `U: 'b`.
 175                 //
 176                 // We can basically ignore bound regions here. So for
 177                 // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to
 178                 // `'a: 'b`.
 179
 180                 // Ignore `for<'a> T: 'a` -- we might in the future
 181                 // consider this as evidence that `T: 'static`, but
 182                 // I'm a bit wary of such constructions and so for now
 183                 // I want to be conservative. --nmatsakis
 184                 let ty_max = data.skip_binder().0;
 185                 let r_min = data.skip_binder().1;
 186                 if r_min.is_late_bound() {
 187                     return;
 188                 }
 189
 190                 let visited = &mut self.visited;
 191                 let mut components = smallvec![];
 192                 tcx.push_outlives_components(ty_max, &mut components);
 193                 self.stack.extend(
 194                     components
 195                         .into_iter()
 196                         .filter_map(|component| match component {
 197                             Component::Region(r) => if r.is_late_bound() {
 198                                 None
 199                             } else {
 200                                 Some(ty::Predicate::RegionOutlives(
 201                                     ty::Binder::dummy(ty::OutlivesPredicate(r, r_min))))
 202                             }
 203
 204                             Component::Param(p) => {
 205                                 let ty = tcx.mk_ty_param(p.index, p.name);
 206                                 Some(ty::Predicate::TypeOutlives(
 207                                     ty::Binder::dummy(ty::OutlivesPredicate(ty, r_min))))
 208                             }
 209
 210                             Component::UnresolvedInferenceVariable(_) => {
 211                                 None
 212                             }
 213
 214                             Component::Projection(_) |
 215                             Component::EscapingProjection(_) => {
 216                                 // We can probably do more here. This
 217                                 // corresponds to a case like `<T as
 218                                 // Foo<'a>>::U: 'b`.
 219                                 None
 220                             }
 221                         })
 222                         .filter(|p| visited.insert(p))
 223                 );
 224             }
 225         }
 226     }
 227 }
 228
 229 impl Iterator for Elaborator<'tcx> {
 230     type Item = ty::Predicate<'tcx>;
 231
 232     fn size_hint(&self) -> (usize, Option<usize>) {
 233         (self.stack.len(), None)
 234     }
 235
 236     fn next(&mut self) -> Option<ty::Predicate<'tcx>> {
 237         // Extract next item from top-most stack frame, if any.
 238         if let Some(pred) = self.stack.pop() {
 239             self.elaborate(&pred);
 240             Some(pred)
 241         } else {
 242             None
 243         }
 244     }
 245 }
 246
 247 ///////////////////////////////////////////////////////////////////////////
 248 // Supertrait iterator
 249 ///////////////////////////////////////////////////////////////////////////
 250
 251 pub type Supertraits<'tcx> = FilterToTraits<Elaborator<'tcx>>;
 252
 253 pub fn supertraits<'tcx>(
 254     tcx: TyCtxt<'tcx>,
 255     trait_ref: ty::PolyTraitRef<'tcx>,
 256 ) -> Supertraits<'tcx> {
 257     elaborate_trait_ref(tcx, trait_ref).filter_to_traits()
 258 }
 259
 260 pub fn transitive_bounds<'tcx>(
 261     tcx: TyCtxt<'tcx>,
 262     bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
 263 ) -> Supertraits<'tcx> {
 264     elaborate_trait_refs(tcx, bounds).filter_to_traits()
 265 }
 266
 267 ///////////////////////////////////////////////////////////////////////////
 268 // `TraitAliasExpander` iterator
 269 ///////////////////////////////////////////////////////////////////////////
 270
 271 /// "Trait alias expansion" is the process of expanding a sequence of trait
 272 /// references into another sequence by transitively following all trait
 273 /// aliases. e.g. If you have bounds like `Foo + Send`, a trait alias
 274 /// `trait Foo = Bar + Sync;`, and another trait alias
 275 /// `trait Bar = Read + Write`, then the bounds would expand to
 276 /// `Read + Write + Sync + Send`.
 277 /// Expansion is done via a DFS (depth-first search), and the `visited` field
 278 /// is used to avoid cycles.
 279 pub struct TraitAliasExpander<'tcx> {
 280     tcx: TyCtxt<'tcx>,
 281     stack: Vec<TraitAliasExpansionInfo<'tcx>>,
 282 }
 283
 284 /// Stores information about the expansion of a trait via a path of zero or more trait aliases.
 285 #[derive(Debug, Clone)]
 286 pub struct TraitAliasExpansionInfo<'tcx> {
 287     pub path: SmallVec<[(ty::PolyTraitRef<'tcx>, Span); 4]>,
 288 }
 289
 290 impl<'tcx> TraitAliasExpansionInfo<'tcx> {
 291     fn new(trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self {
 292         Self {
 293             path: smallvec![(trait_ref, span)]
 294         }
 295     }
 296
 297     /// Adds diagnostic labels to `diag` for the expansion path of a trait through all intermediate
 298     /// trait aliases.
 299     pub fn label_with_exp_info(&self,
 300         diag: &mut DiagnosticBuilder<'_>,
 301         top_label: &str,
 302         use_desc: &str
 303     ) {
 304         diag.span_label(self.top().1, top_label);
 305         if self.path.len() > 1 {
 306             for (_, sp) in self.path.iter().rev().skip(1).take(self.path.len() - 2) {
 307                 diag.span_label(*sp, format!("referenced here ({})", use_desc));
 308             }
 309         }
 310         diag.span_label(self.bottom().1,
 311             format!("trait alias used in trait object type ({})", use_desc));
 312     }
 313
 314     pub fn trait_ref(&self) -> &ty::PolyTraitRef<'tcx> {
 315         &self.top().0
 316     }
 317
 318     pub fn top(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
 319         self.path.last().unwrap()
 320     }
 321
 322     pub fn bottom(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
 323         self.path.first().unwrap()
 324     }
 325
 326     fn clone_and_push(&self, trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self {
 327         let mut path = self.path.clone();
 328         path.push((trait_ref, span));
 329
 330         Self {
 331             path
 332         }
 333     }
 334 }
 335
 336 pub fn expand_trait_aliases<'tcx>(
 337     tcx: TyCtxt<'tcx>,
 338     trait_refs: impl IntoIterator<Item = (ty::PolyTraitRef<'tcx>, Span)>,
 339 ) -> TraitAliasExpander<'tcx> {
 340     let items: Vec<_> = trait_refs
 341         .into_iter()
 342         .map(|(trait_ref, span)| TraitAliasExpansionInfo::new(trait_ref, span))
 343         .collect();
 344     TraitAliasExpander { tcx, stack: items }
 345 }
 346
 347 impl<'tcx> TraitAliasExpander<'tcx> {
 348     /// If `item` is a trait alias and its predicate has not yet been visited, then expands `item`
 349     /// to the definition, pushes the resulting expansion onto `self.stack`, and returns `false`.
 350     /// Otherwise, immediately returns `true` if `item` is a regular trait, or `false` if it is a
 351     /// trait alias.
 352     /// The return value indicates whether `item` should be yielded to the user.
 353     fn expand(&mut self, item: &TraitAliasExpansionInfo<'tcx>) -> bool {
 354         let tcx = self.tcx;
 355         let trait_ref = item.trait_ref();
 356         let pred = trait_ref.to_predicate();
 357
 358         debug!("expand_trait_aliases: trait_ref={:?}", trait_ref);
 359
 360         // Don't recurse if this bound is not a trait alias.
 361         let is_alias = tcx.is_trait_alias(trait_ref.def_id());
 362         if !is_alias {
 363             return true;
 364         }
 365
 366         // Don't recurse if this trait alias is already on the stack for the DFS search.
 367         let anon_pred = anonymize_predicate(tcx, &pred);
 368         if item.path.iter().rev().skip(1)
 369                 .any(|(tr, _)| anonymize_predicate(tcx, &tr.to_predicate()) == anon_pred) {
 370             return false;
 371         }
 372
 373         // Get components of trait alias.
 374         let predicates = tcx.super_predicates_of(trait_ref.def_id());
 375
 376         let items = predicates.predicates
 377             .iter()
 378             .rev()
 379             .filter_map(|(pred, span)| {
 380                 pred.subst_supertrait(tcx, &trait_ref)
 381                     .to_opt_poly_trait_ref()
 382                     .map(|trait_ref| item.clone_and_push(trait_ref, *span))
 383             });
 384         debug!("expand_trait_aliases: items={:?}", items.clone());
 385
 386         self.stack.extend(items);
 387
 388         false
 389     }
 390 }
 391
 392 impl<'tcx> Iterator for TraitAliasExpander<'tcx> {
 393     type Item = TraitAliasExpansionInfo<'tcx>;
 394
 395     fn size_hint(&self) -> (usize, Option<usize>) {
 396         (self.stack.len(), None)
 397     }
 398
 399     fn next(&mut self) -> Option<TraitAliasExpansionInfo<'tcx>> {
 400         while let Some(item) = self.stack.pop() {
 401             if self.expand(&item) {
 402                 return Some(item);
 403             }
 404         }
 405         None
 406     }
 407 }
 408
 409 ///////////////////////////////////////////////////////////////////////////
 410 // Iterator over def-IDs of supertraits
 411 ///////////////////////////////////////////////////////////////////////////
 412
 413 pub struct SupertraitDefIds<'tcx> {
 414     tcx: TyCtxt<'tcx>,
 415     stack: Vec<DefId>,
 416     visited: FxHashSet<DefId>,
 417 }
 418
 419 pub fn supertrait_def_ids(tcx: TyCtxt<'_>, trait_def_id: DefId) -> SupertraitDefIds<'_> {
 420     SupertraitDefIds {
 421         tcx,
 422         stack: vec![trait_def_id],
 423         visited: Some(trait_def_id).into_iter().collect(),
 424     }
 425 }
 426
 427 impl Iterator for SupertraitDefIds<'tcx> {
 428     type Item = DefId;
 429
 430     fn next(&mut self) -> Option<DefId> {
 431         let def_id = self.stack.pop()?;
 432         let predicates = self.tcx.super_predicates_of(def_id);
 433         let visited = &mut self.visited;
 434         self.stack.extend(
 435             predicates.predicates
 436                       .iter()
 437                       .filter_map(|(pred, _)| pred.to_opt_poly_trait_ref())
 438                       .map(|trait_ref| trait_ref.def_id())
 439                       .filter(|&super_def_id| visited.insert(super_def_id)));
 440         Some(def_id)
 441     }
 442 }
 443
 444 ///////////////////////////////////////////////////////////////////////////
 445 // Other
 446 ///////////////////////////////////////////////////////////////////////////
 447
 448 /// A filter around an iterator of predicates that makes it yield up
 449 /// just trait references.
 450 pub struct FilterToTraits<I> {
 451     base_iterator: I
 452 }
 453
 454 impl<I> FilterToTraits<I> {
 455     fn new(base: I) -> FilterToTraits<I> {
 456         FilterToTraits { base_iterator: base }
 457     }
 458 }
 459
 460 impl<'tcx, I: Iterator<Item = ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> {
 461     type Item = ty::PolyTraitRef<'tcx>;
 462
 463     fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> {
 464         while let Some(pred) = self.base_iterator.next() {
 465             if let ty::Predicate::Trait(data) = pred {
 466                 return Some(data.to_poly_trait_ref());
 467             }
 468         }
 469         None
 470     }
 471
 472     fn size_hint(&self) -> (usize, Option<usize>) {
 473         let (_, upper) = self.base_iterator.size_hint();
 474         (0, upper)
 475     }
 476 }
 477
 478 ///////////////////////////////////////////////////////////////////////////
 479 // Other
 480 ///////////////////////////////////////////////////////////////////////////
 481
 482 /// Instantiate all bound parameters of the impl with the given substs,
 483 /// returning the resulting trait ref and all obligations that arise.
 484 /// The obligations are closed under normalization.
 485 pub fn impl_trait_ref_and_oblig<'a, 'tcx>(
 486     selcx: &mut SelectionContext<'a, 'tcx>,
 487     param_env: ty::ParamEnv<'tcx>,
 488     impl_def_id: DefId,
 489     impl_substs: SubstsRef<'tcx>,
 490 ) -> (ty::TraitRef<'tcx>, Vec<PredicateObligation<'tcx>>) {
 491     let impl_trait_ref =
 492         selcx.tcx().impl_trait_ref(impl_def_id).unwrap();
 493     let impl_trait_ref =
 494         impl_trait_ref.subst(selcx.tcx(), impl_substs);
 495     let Normalized { value: impl_trait_ref, obligations: normalization_obligations1 } =
 496         super::normalize(selcx, param_env, ObligationCause::dummy(), &impl_trait_ref);
 497
 498     let predicates = selcx.tcx().predicates_of(impl_def_id);
 499     let predicates = predicates.instantiate(selcx.tcx(), impl_substs);
 500     let Normalized { value: predicates, obligations: normalization_obligations2 } =
 501         super::normalize(selcx, param_env, ObligationCause::dummy(), &predicates);
 502     let impl_obligations =
 503         predicates_for_generics(ObligationCause::dummy(), 0, param_env, &predicates);
 504
 505     let impl_obligations: Vec<_> =
 506         impl_obligations.into_iter()
 507         .chain(normalization_obligations1)
 508         .chain(normalization_obligations2)
 509         .collect();
 510
 511     (impl_trait_ref, impl_obligations)
 512 }
 513
 514 /// See [`super::obligations_for_generics`].
 515 pub fn predicates_for_generics<'tcx>(
 516     cause: ObligationCause<'tcx>,
 517     recursion_depth: usize,
 518     param_env: ty::ParamEnv<'tcx>,
 519     generic_bounds: &ty::InstantiatedPredicates<'tcx>,
 520 ) -> Vec<PredicateObligation<'tcx>> {
 521     debug!("predicates_for_generics(generic_bounds={:?})", generic_bounds);
 522
 523     generic_bounds.predicates.iter().map(|predicate| Obligation {
 524         cause: cause.clone(),
 525         recursion_depth,
 526         param_env,
 527         predicate: predicate.clone(),
 528     }).collect()
 529 }
 530
 531 pub fn predicate_for_trait_ref<'tcx>(
 532     cause: ObligationCause<'tcx>,
 533     param_env: ty::ParamEnv<'tcx>,
 534     trait_ref: ty::TraitRef<'tcx>,
 535     recursion_depth: usize)
 536     -> PredicateObligation<'tcx>
 537 {
 538     Obligation {
 539         cause,
 540         param_env,
 541         recursion_depth,
 542         predicate: trait_ref.to_predicate(),
 543     }
 544 }
 545
 546 impl<'tcx> TyCtxt<'tcx> {
 547     pub fn predicate_for_trait_def(self,
 548                                    param_env: ty::ParamEnv<'tcx>,
 549                                    cause: ObligationCause<'tcx>,
 550                                    trait_def_id: DefId,
 551                                    recursion_depth: usize,
 552                                    self_ty: Ty<'tcx>,
 553                                    params: &[GenericArg<'tcx>])
 554         -> PredicateObligation<'tcx>
 555     {
 556         let trait_ref = ty::TraitRef {
 557             def_id: trait_def_id,
 558             substs: self.mk_substs_trait(self_ty, params)
 559         };
 560         predicate_for_trait_ref(cause, param_env, trait_ref, recursion_depth)
 561     }
 562
 563     /// Casts a trait reference into a reference to one of its super
 564     /// traits; returns `None` if `target_trait_def_id` is not a
 565     /// supertrait.
 566     pub fn upcast_choices(self,
 567                           source_trait_ref: ty::PolyTraitRef<'tcx>,
 568                           target_trait_def_id: DefId)
 569                           -> Vec<ty::PolyTraitRef<'tcx>>
 570     {
 571         if source_trait_ref.def_id() == target_trait_def_id {
 572             return vec![source_trait_ref]; // Shortcut the most common case.
 573         }
 574
 575         supertraits(self, source_trait_ref)
 576             .filter(|r| r.def_id() == target_trait_def_id)
 577             .collect()
 578     }
 579
 580     /// Given a trait `trait_ref`, returns the number of vtable entries
 581     /// that come from `trait_ref`, excluding its supertraits. Used in
 582     /// computing the vtable base for an upcast trait of a trait object.
 583     pub fn count_own_vtable_entries(self, trait_ref: ty::PolyTraitRef<'tcx>) -> usize {
 584         let mut entries = 0;
 585         // Count number of methods and add them to the total offset.
 586         // Skip over associated types and constants.
 587         for trait_item in self.associated_items(trait_ref.def_id()) {
 588             if trait_item.kind == ty::AssocKind::Method {
 589                 entries += 1;
 590             }
 591         }
 592         entries
 593     }
 594
 595     /// Given an upcast trait object described by `object`, returns the
 596     /// index of the method `method_def_id` (which should be part of
 597     /// `object.upcast_trait_ref`) within the vtable for `object`.
 598     pub fn get_vtable_index_of_object_method<N>(self,
 599                                                 object: &super::VtableObjectData<'tcx, N>,
 600                                                 method_def_id: DefId) -> usize {
 601         // Count number of methods preceding the one we are selecting and
 602         // add them to the total offset.
 603         // Skip over associated types and constants.
 604         let mut entries = object.vtable_base;
 605         for trait_item in self.associated_items(object.upcast_trait_ref.def_id()) {
 606             if trait_item.def_id == method_def_id {
 607                 // The item with the ID we were given really ought to be a method.
 608                 assert_eq!(trait_item.kind, ty::AssocKind::Method);
 609                 return entries;
 610             }
 611             if trait_item.kind == ty::AssocKind::Method {
 612                 entries += 1;
 613             }
 614         }
 615
 616         bug!("get_vtable_index_of_object_method: {:?} was not found",
 617              method_def_id);
 618     }
 619
 620     pub fn closure_trait_ref_and_return_type(self,
 621         fn_trait_def_id: DefId,
 622         self_ty: Ty<'tcx>,
 623         sig: ty::PolyFnSig<'tcx>,
 624         tuple_arguments: TupleArgumentsFlag)
 625         -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>)>
 626     {
 627         let arguments_tuple = match tuple_arguments {
 628             TupleArgumentsFlag::No => sig.skip_binder().inputs()[0],
 629             TupleArgumentsFlag::Yes =>
 630                 self.intern_tup(sig.skip_binder().inputs()),
 631         };
 632         let trait_ref = ty::TraitRef {
 633             def_id: fn_trait_def_id,
 634             substs: self.mk_substs_trait(self_ty, &[arguments_tuple.into()]),
 635         };
 636         ty::Binder::bind((trait_ref, sig.skip_binder().output()))
 637     }
 638
 639     pub fn generator_trait_ref_and_outputs(self,
 640         fn_trait_def_id: DefId,
 641         self_ty: Ty<'tcx>,
 642         sig: ty::PolyGenSig<'tcx>)
 643         -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>)>
 644     {
 645         let trait_ref = ty::TraitRef {
 646             def_id: fn_trait_def_id,
 647             substs: self.mk_substs_trait(self_ty, &[]),
 648         };
 649         ty::Binder::bind((trait_ref, sig.skip_binder().yield_ty, sig.skip_binder().return_ty))
 650     }
 651
 652     pub fn impl_is_default(self, node_item_def_id: DefId) -> bool {
 653         match self.hir().as_local_hir_id(node_item_def_id) {
 654             Some(hir_id) => {
 655                 let item = self.hir().expect_item(hir_id);
 656                 if let hir::ItemKind::Impl(_, _, defaultness, ..) = item.kind {
 657                     defaultness.is_default()
 658                 } else {
 659                     false
 660                 }
 661             }
 662             None => {
 663                 self.impl_defaultness(node_item_def_id)
 664                     .is_default()
 665             }
 666         }
 667     }
 668
 669     pub fn impl_item_is_final(self, assoc_item: &ty::AssocItem) -> bool {
 670         assoc_item.defaultness.is_final() && !self.impl_is_default(assoc_item.container.id())
 671     }
 672 }
 673
 674 pub enum TupleArgumentsFlag { Yes, No }