src/librustc_traits/lowering/mod.rs

   1 // Copyright 2018 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 mod environment;
  12
  13 use rustc::hir::def_id::DefId;
  14 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
  15 use rustc::hir::map::definitions::DefPathData;
  16 use rustc::hir::{self, ImplPolarity};
  17 use rustc::traits::{
  18     Clause,
  19     Clauses,
  20     DomainGoal,
  21     FromEnv,
  22     GoalKind,
  23     PolyDomainGoal,
  24     ProgramClause,
  25     ProgramClauseCategory,
  26     WellFormed,
  27     WhereClause,
  28 };
  29 use rustc::ty::query::Providers;
  30 use rustc::ty::{self, List, TyCtxt};
  31 use rustc::ty::subst::{Subst, Substs};
  32 use syntax::ast;
  33
  34 use std::iter;
  35
  36 crate fn provide(p: &mut Providers) {
  37     *p = Providers {
  38         program_clauses_for,
  39         program_clauses_for_env: environment::program_clauses_for_env,
  40         environment: environment::environment,
  41         ..*p
  42     };
  43 }
  44
  45 crate trait Lower<T> {
  46     /// Lower a rustc construct (e.g. `ty::TraitPredicate`) to a chalk-like type.
  47     fn lower(&self) -> T;
  48 }
  49
  50 impl<T, U> Lower<Vec<U>> for Vec<T>
  51 where
  52     T: Lower<U>,
  53 {
  54     fn lower(&self) -> Vec<U> {
  55         self.iter().map(|item| item.lower()).collect()
  56     }
  57 }
  58
  59 impl<'tcx> Lower<WhereClause<'tcx>> for ty::TraitPredicate<'tcx> {
  60     fn lower(&self) -> WhereClause<'tcx> {
  61         WhereClause::Implemented(*self)
  62     }
  63 }
  64
  65 impl<'tcx> Lower<WhereClause<'tcx>> for ty::ProjectionPredicate<'tcx> {
  66     fn lower(&self) -> WhereClause<'tcx> {
  67         WhereClause::ProjectionEq(*self)
  68     }
  69 }
  70
  71 impl<'tcx> Lower<WhereClause<'tcx>> for ty::RegionOutlivesPredicate<'tcx> {
  72     fn lower(&self) -> WhereClause<'tcx> {
  73         WhereClause::RegionOutlives(*self)
  74     }
  75 }
  76
  77 impl<'tcx> Lower<WhereClause<'tcx>> for ty::TypeOutlivesPredicate<'tcx> {
  78     fn lower(&self) -> WhereClause<'tcx> {
  79         WhereClause::TypeOutlives(*self)
  80     }
  81 }
  82
  83 impl<'tcx, T> Lower<DomainGoal<'tcx>> for T
  84 where
  85     T: Lower<WhereClause<'tcx>>,
  86 {
  87     fn lower(&self) -> DomainGoal<'tcx> {
  88         DomainGoal::Holds(self.lower())
  89     }
  90 }
  91
  92 /// `ty::Binder` is used for wrapping a rustc construction possibly containing generic
  93 /// lifetimes, e.g. `for<'a> T: Fn(&'a i32)`. Instead of representing higher-ranked things
  94 /// in that leaf-form (i.e. `Holds(Implemented(Binder<TraitPredicate>))` in the previous
  95 /// example), we model them with quantified domain goals, e.g. as for the previous example:
  96 /// `forall<'a> { T: Fn(&'a i32) }` which corresponds to something like
  97 /// `Binder<Holds(Implemented(TraitPredicate))>`.
  98 impl<'tcx, T> Lower<PolyDomainGoal<'tcx>> for ty::Binder<T>
  99 where
 100     T: Lower<DomainGoal<'tcx>> + ty::fold::TypeFoldable<'tcx>,
 101 {
 102     fn lower(&self) -> PolyDomainGoal<'tcx> {
 103         self.map_bound_ref(|p| p.lower())
 104     }
 105 }
 106
 107 impl<'tcx> Lower<PolyDomainGoal<'tcx>> for ty::Predicate<'tcx> {
 108     fn lower(&self) -> PolyDomainGoal<'tcx> {
 109         use rustc::ty::Predicate;
 110
 111         match self {
 112             Predicate::Trait(predicate) => predicate.lower(),
 113             Predicate::RegionOutlives(predicate) => predicate.lower(),
 114             Predicate::TypeOutlives(predicate) => predicate.lower(),
 115             Predicate::Projection(predicate) => predicate.lower(),
 116
 117             Predicate::WellFormed(..) |
 118             Predicate::ObjectSafe(..) |
 119             Predicate::ClosureKind(..) |
 120             Predicate::Subtype(..) |
 121             Predicate::ConstEvaluatable(..) => {
 122                 bug!("unexpected predicate {}", self)
 123             }
 124         }
 125     }
 126 }
 127
 128 /// Used for implied bounds related rules (see rustc guide).
 129 trait IntoFromEnvGoal {
 130     /// Transforms an existing goal into a `FromEnv` goal.
 131     fn into_from_env_goal(self) -> Self;
 132 }
 133
 134 /// Used for well-formedness related rules (see rustc guide).
 135 trait IntoWellFormedGoal {
 136     /// Transforms an existing goal into a `WellFormed` goal.
 137     fn into_well_formed_goal(self) -> Self;
 138 }
 139
 140 impl<'tcx> IntoFromEnvGoal for DomainGoal<'tcx> {
 141     fn into_from_env_goal(self) -> DomainGoal<'tcx> {
 142         use self::WhereClause::*;
 143
 144         match self {
 145             DomainGoal::Holds(Implemented(trait_ref)) => {
 146                 DomainGoal::FromEnv(FromEnv::Trait(trait_ref))
 147             }
 148             other => other,
 149         }
 150     }
 151 }
 152
 153 impl<'tcx> IntoWellFormedGoal for DomainGoal<'tcx> {
 154     fn into_well_formed_goal(self) -> DomainGoal<'tcx> {
 155         use self::WhereClause::*;
 156
 157         match self {
 158             DomainGoal::Holds(Implemented(trait_ref)) => {
 159                 DomainGoal::WellFormed(WellFormed::Trait(trait_ref))
 160             }
 161             other => other,
 162         }
 163     }
 164 }
 165
 166 crate fn program_clauses_for<'a, 'tcx>(
 167     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 168     def_id: DefId,
 169 ) -> Clauses<'tcx> {
 170     match tcx.def_key(def_id).disambiguated_data.data {
 171         DefPathData::Trait(_) => program_clauses_for_trait(tcx, def_id),
 172         DefPathData::Impl => program_clauses_for_impl(tcx, def_id),
 173         DefPathData::AssocTypeInImpl(..) => program_clauses_for_associated_type_value(tcx, def_id),
 174         DefPathData::AssocTypeInTrait(..) => program_clauses_for_associated_type_def(tcx, def_id),
 175         DefPathData::TypeNs(..) => program_clauses_for_type_def(tcx, def_id),
 176         _ => List::empty(),
 177     }
 178 }
 179
 180 fn program_clauses_for_trait<'a, 'tcx>(
 181     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 182     def_id: DefId,
 183 ) -> Clauses<'tcx> {
 184     // `trait Trait<P1..Pn> where WC { .. } // P0 == Self`
 185
 186     // Rule Implemented-From-Env (see rustc guide)
 187     //
 188     // ```
 189     // forall<Self, P1..Pn> {
 190     //   Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)
 191     // }
 192     // ```
 193
 194     let bound_vars = Substs::bound_vars_for_item(tcx, def_id);
 195
 196     // `Self: Trait<P1..Pn>`
 197     let trait_pred = ty::TraitPredicate {
 198         trait_ref: ty::TraitRef {
 199             def_id,
 200             substs: bound_vars,
 201         },
 202     };
 203
 204     // `Implemented(Self: Trait<P1..Pn>)`
 205     let impl_trait: DomainGoal = trait_pred.lower();
 206
 207     // `FromEnv(Self: Trait<P1..Pn>)`
 208     let from_env_goal = tcx.mk_goal(impl_trait.into_from_env_goal().into_goal());
 209     let hypotheses = tcx.intern_goals(&[from_env_goal]);
 210
 211     // `Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)`
 212     let implemented_from_env = ProgramClause {
 213         goal: impl_trait,
 214         hypotheses,
 215         category: ProgramClauseCategory::ImpliedBound,
 216     };
 217
 218     let implemented_from_env = Clause::ForAll(ty::Binder::bind(implemented_from_env));
 219
 220     let predicates = &tcx.predicates_defined_on(def_id).predicates;
 221     let where_clauses = &predicates
 222         .iter()
 223         .map(|(wc, _)| wc.lower())
 224         .map(|wc| wc.subst(tcx, bound_vars))
 225         .collect::<Vec<_>>();
 226
 227     // Rule Implied-Bound-From-Trait
 228     //
 229     // For each where clause WC:
 230     // ```
 231     // forall<Self, P1..Pn> {
 232     //   FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn)
 233     // }
 234     // ```
 235
 236     // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`, for each where clause WC
 237     let implied_bound_clauses = where_clauses
 238         .iter()
 239         .cloned()
 240
 241         // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`
 242         .map(|wc| {
 243             // we move binders to the left
 244             wc.map_bound(|goal| ProgramClause {
 245                 goal: goal.into_from_env_goal(),
 246
 247                 // FIXME: As where clauses can only bind lifetimes for now,
 248                 // and that named bound regions have a def-id, it is safe
 249                 // to just inject `hypotheses` (which contains named vars bound at index `0`)
 250                 // into this binding level. This may change if we ever allow where clauses
 251                 // to bind types (e.g. for GATs things), because bound types only use a `BoundVar`
 252                 // index (no def-id).
 253                 hypotheses,
 254
 255                 category: ProgramClauseCategory::ImpliedBound,
 256             })
 257         })
 258         .map(Clause::ForAll);
 259
 260     // Rule WellFormed-TraitRef
 261     //
 262     // Here `WC` denotes the set of all where clauses:
 263     // ```
 264     // forall<Self, P1..Pn> {
 265     //   WellFormed(Self: Trait<P1..Pn>) :- Implemented(Self: Trait<P1..Pn>) && WellFormed(WC)
 266     // }
 267     // ```
 268
 269     // `WellFormed(WC)`
 270     let wf_conditions = where_clauses
 271         .into_iter()
 272         .map(|wc| wc.map_bound(|goal| goal.into_well_formed_goal()));
 273
 274     // `WellFormed(Self: Trait<P1..Pn>) :- Implemented(Self: Trait<P1..Pn>) && WellFormed(WC)`
 275     let wf_clause = ProgramClause {
 276         goal: DomainGoal::WellFormed(WellFormed::Trait(trait_pred)),
 277         hypotheses: tcx.mk_goals(
 278             iter::once(tcx.mk_goal(GoalKind::DomainGoal(impl_trait))).chain(
 279                 wf_conditions.map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx)))
 280             )
 281         ),
 282         category: ProgramClauseCategory::WellFormed,
 283     };
 284     let wf_clause = Clause::ForAll(ty::Binder::bind(wf_clause));
 285
 286     tcx.mk_clauses(
 287         iter::once(implemented_from_env)
 288             .chain(implied_bound_clauses)
 289             .chain(iter::once(wf_clause))
 290     )
 291 }
 292
 293 fn program_clauses_for_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> Clauses<'tcx> {
 294     if let ImplPolarity::Negative = tcx.impl_polarity(def_id) {
 295         return List::empty();
 296     }
 297
 298     // Rule Implemented-From-Impl (see rustc guide)
 299     //
 300     // `impl<P0..Pn> Trait<A1..An> for A0 where WC { .. }`
 301     //
 302     // ```
 303     // forall<P0..Pn> {
 304     //   Implemented(A0: Trait<A1..An>) :- WC
 305     // }
 306     // ```
 307
 308     let bound_vars = Substs::bound_vars_for_item(tcx, def_id);
 309
 310     let trait_ref = tcx.impl_trait_ref(def_id)
 311         .expect("not an impl")
 312         .subst(tcx, bound_vars);
 313
 314     // `Implemented(A0: Trait<A1..An>)`
 315     let trait_pred = ty::TraitPredicate { trait_ref }.lower();
 316
 317     // `WC`
 318     let predicates = &tcx.predicates_of(def_id).predicates;
 319     let where_clauses = predicates
 320         .iter()
 321         .map(|(wc, _)| wc.lower())
 322         .map(|wc| wc.subst(tcx, bound_vars));
 323
 324     // `Implemented(A0: Trait<A1..An>) :- WC`
 325     let clause = ProgramClause {
 326         goal: trait_pred,
 327         hypotheses: tcx.mk_goals(
 328             where_clauses
 329                 .map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx))),
 330         ),
 331         category: ProgramClauseCategory::Other,
 332     };
 333     tcx.mk_clauses(iter::once(Clause::ForAll(ty::Binder::bind(clause))))
 334 }
 335
 336 pub fn program_clauses_for_type_def<'a, 'tcx>(
 337     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 338     def_id: DefId,
 339 ) -> Clauses<'tcx> {
 340     // Rule WellFormed-Type
 341     //
 342     // `struct Ty<P1..Pn> where WC1, ..., WCm`
 343     //
 344     // ```
 345     // forall<P1..Pn> {
 346     //   WellFormed(Ty<...>) :- WC1, ..., WCm`
 347     // }
 348     // ```
 349
 350     let bound_vars = Substs::bound_vars_for_item(tcx, def_id);
 351
 352     // `Ty<...>`
 353     let ty = tcx.type_of(def_id).subst(tcx, bound_vars);
 354
 355     // `WC`
 356     let where_clauses = tcx.predicates_of(def_id).predicates
 357         .iter()
 358         .map(|(wc, _)| wc.lower())
 359         .map(|wc| wc.subst(tcx, bound_vars))
 360         .collect::<Vec<_>>();
 361
 362     // `WellFormed(Ty<...>) :- WC1, ..., WCm`
 363     let well_formed_clause = ProgramClause {
 364         goal: DomainGoal::WellFormed(WellFormed::Ty(ty)),
 365         hypotheses: tcx.mk_goals(
 366             where_clauses
 367                 .iter()
 368                 .cloned()
 369                 .map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx))),
 370         ),
 371         category: ProgramClauseCategory::WellFormed,
 372     };
 373     let well_formed_clause = Clause::ForAll(ty::Binder::bind(well_formed_clause));
 374
 375     // Rule Implied-Bound-From-Type
 376     //
 377     // For each where clause `WC`:
 378     // ```
 379     // forall<P1..Pn> {
 380     //   FromEnv(WC) :- FromEnv(Ty<...>)
 381     // }
 382     // ```
 383
 384     // `FromEnv(Ty<...>)`
 385     let from_env_goal = tcx.mk_goal(DomainGoal::FromEnv(FromEnv::Ty(ty)).into_goal());
 386     let hypotheses = tcx.intern_goals(&[from_env_goal]);
 387
 388     // For each where clause `WC`:
 389     let from_env_clauses = where_clauses
 390         .into_iter()
 391
 392         // `FromEnv(WC) :- FromEnv(Ty<...>)`
 393         .map(|wc| {
 394             // move the binders to the left
 395             wc.map_bound(|goal| ProgramClause {
 396                 goal: goal.into_from_env_goal(),
 397
 398                 // FIXME: we inject `hypotheses` into this binding level,
 399                 // which may be incorrect in the future: see the FIXME in
 400                 // `program_clauses_for_trait`
 401                 hypotheses,
 402
 403                 category: ProgramClauseCategory::ImpliedBound,
 404             })
 405         })
 406
 407         .map(Clause::ForAll);
 408
 409     tcx.mk_clauses(iter::once(well_formed_clause).chain(from_env_clauses))
 410 }
 411
 412 pub fn program_clauses_for_associated_type_def<'a, 'tcx>(
 413     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 414     item_id: DefId,
 415 ) -> Clauses<'tcx> {
 416     // Rule ProjectionEq-Placeholder
 417     //
 418     // ```
 419     // trait Trait<P1..Pn> {
 420     //     type AssocType<Pn+1..Pm>;
 421     // }
 422     // ```
 423     //
 424     // `ProjectionEq` can succeed by skolemizing, see "associated type"
 425     // chapter for more:
 426     // ```
 427     // forall<Self, P1..Pn, Pn+1..Pm> {
 428     //     ProjectionEq(
 429     //         <Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> =
 430     //         (Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>
 431     //     )
 432     // }
 433     // ```
 434
 435     let item = tcx.associated_item(item_id);
 436     debug_assert_eq!(item.kind, ty::AssociatedKind::Type);
 437     let trait_id = match item.container {
 438         ty::AssociatedItemContainer::TraitContainer(trait_id) => trait_id,
 439         _ => bug!("not an trait container"),
 440     };
 441
 442     let trait_bound_vars = Substs::bound_vars_for_item(tcx, trait_id);
 443     let trait_ref = ty::TraitRef {
 444         def_id: trait_id,
 445         substs: trait_bound_vars,
 446     };
 447
 448     let projection_ty = ty::ProjectionTy::from_ref_and_name(tcx, trait_ref, item.ident);
 449     let placeholder_ty = tcx.mk_ty(ty::UnnormalizedProjection(projection_ty));
 450     let projection_eq = WhereClause::ProjectionEq(ty::ProjectionPredicate {
 451         projection_ty,
 452         ty: placeholder_ty,
 453     });
 454
 455     let projection_eq_clause = ProgramClause {
 456         goal: DomainGoal::Holds(projection_eq),
 457         hypotheses: ty::List::empty(),
 458         category: ProgramClauseCategory::Other,
 459     };
 460     let projection_eq_clause = Clause::ForAll(ty::Binder::bind(projection_eq_clause));
 461
 462     // Rule WellFormed-AssocTy
 463     // ```
 464     // forall<Self, P1..Pn, Pn+1..Pm> {
 465     //     WellFormed((Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>)
 466     //         :- Implemented(Self: Trait<P1..Pn>)
 467     // }
 468     // ```
 469
 470     let trait_predicate = ty::TraitPredicate { trait_ref };
 471     let hypothesis = tcx.mk_goal(
 472         DomainGoal::Holds(WhereClause::Implemented(trait_predicate)).into_goal()
 473     );
 474
 475     let wf_clause = ProgramClause {
 476         goal: DomainGoal::WellFormed(WellFormed::Ty(placeholder_ty)),
 477         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 478         category: ProgramClauseCategory::WellFormed,
 479     };
 480     let wf_clause = Clause::ForAll(ty::Binder::bind(wf_clause));
 481
 482     // Rule Implied-Trait-From-AssocTy
 483     // ```
 484     // forall<Self, P1..Pn, Pn+1..Pm> {
 485     //     FromEnv(Self: Trait<P1..Pn>)
 486     //         :- FromEnv((Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>)
 487     // }
 488     // ```
 489
 490     let hypothesis = tcx.mk_goal(
 491         DomainGoal::FromEnv(FromEnv::Ty(placeholder_ty)).into_goal()
 492     );
 493
 494     let from_env_clause = ProgramClause {
 495         goal: DomainGoal::FromEnv(FromEnv::Trait(trait_predicate)),
 496         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 497         category: ProgramClauseCategory::ImpliedBound,
 498     };
 499     let from_env_clause = Clause::ForAll(ty::Binder::bind(from_env_clause));
 500
 501     // Rule ProjectionEq-Normalize
 502     //
 503     // ProjectionEq can succeed by normalizing:
 504     // ```
 505     // forall<Self, P1..Pn, Pn+1..Pm, U> {
 506     //   ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U) :-
 507     //       Normalize(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> -> U)
 508     // }
 509     // ```
 510
 511     let offset = tcx.generics_of(trait_id).params
 512         .iter()
 513         .map(|p| p.index)
 514         .max()
 515         .unwrap_or(0);
 516     // Add a new type param after the existing ones (`U` in the comment above).
 517     let ty_var = ty::Bound(
 518         ty::INNERMOST,
 519         ty::BoundVar::from_u32(offset + 1).into()
 520     );
 521
 522     // `ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U)`
 523     let projection = ty::ProjectionPredicate {
 524         projection_ty,
 525         ty: tcx.mk_ty(ty_var),
 526     };
 527
 528     // `Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> U)`
 529     let hypothesis = tcx.mk_goal(
 530         DomainGoal::Normalize(projection).into_goal()
 531     );
 532
 533     //  ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U) :-
 534     //      Normalize(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> -> U)
 535     let normalize_clause = ProgramClause {
 536         goal: DomainGoal::Holds(WhereClause::ProjectionEq(projection)),
 537         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 538         category: ProgramClauseCategory::Other,
 539     };
 540     let normalize_clause = Clause::ForAll(ty::Binder::bind(normalize_clause));
 541
 542     let clauses = iter::once(projection_eq_clause)
 543         .chain(iter::once(wf_clause))
 544         .chain(iter::once(from_env_clause))
 545         .chain(iter::once(normalize_clause));
 546
 547     tcx.mk_clauses(clauses)
 548 }
 549
 550 pub fn program_clauses_for_associated_type_value<'a, 'tcx>(
 551     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 552     item_id: DefId,
 553 ) -> Clauses<'tcx> {
 554     // Rule Normalize-From-Impl (see rustc guide)
 555     //
 556     // ```
 557     // impl<P0..Pn> Trait<A1..An> for A0 {
 558     //     type AssocType<Pn+1..Pm> = T;
 559     // }
 560     // ```
 561     //
 562     // FIXME: For the moment, we don't account for where clauses written on the associated
 563     // ty definition (i.e. in the trait def, as in `type AssocType<T> where T: Sized`).
 564     // ```
 565     // forall<P0..Pm> {
 566     //   forall<Pn+1..Pm> {
 567     //     Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T) :-
 568     //       Implemented(A0: Trait<A1..An>)
 569     //   }
 570     // }
 571     // ```
 572
 573     let item = tcx.associated_item(item_id);
 574     debug_assert_eq!(item.kind, ty::AssociatedKind::Type);
 575     let impl_id = match item.container {
 576         ty::AssociatedItemContainer::ImplContainer(impl_id) => impl_id,
 577         _ => bug!("not an impl container"),
 578     };
 579
 580     let impl_bound_vars = Substs::bound_vars_for_item(tcx, impl_id);
 581
 582     // `A0 as Trait<A1..An>`
 583     let trait_ref = tcx.impl_trait_ref(impl_id)
 584         .unwrap()
 585         .subst(tcx, impl_bound_vars);
 586
 587     // `T`
 588     let ty = tcx.type_of(item_id);
 589
 590     // `Implemented(A0: Trait<A1..An>)`
 591     let trait_implemented: DomainGoal = ty::TraitPredicate { trait_ref }.lower();
 592
 593     // `<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm>`
 594     let projection_ty = ty::ProjectionTy::from_ref_and_name(tcx, trait_ref, item.ident);
 595
 596     // `Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T)`
 597     let normalize_goal = DomainGoal::Normalize(ty::ProjectionPredicate { projection_ty, ty });
 598
 599     // `Normalize(... -> T) :- ...`
 600     let normalize_clause = ProgramClause {
 601         goal: normalize_goal,
 602         hypotheses: tcx.mk_goals(
 603             iter::once(tcx.mk_goal(GoalKind::DomainGoal(trait_implemented)))
 604         ),
 605         category: ProgramClauseCategory::Other,
 606     };
 607     let normalize_clause = Clause::ForAll(ty::Binder::bind(normalize_clause));
 608
 609     tcx.mk_clauses(iter::once(normalize_clause))
 610 }
 611
 612 pub fn dump_program_clauses<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
 613     if !tcx.features().rustc_attrs {
 614         return;
 615     }
 616
 617     let mut visitor = ClauseDumper { tcx };
 618     tcx.hir()
 619         .krate()
 620         .visit_all_item_likes(&mut visitor.as_deep_visitor());
 621 }
 622
 623 struct ClauseDumper<'a, 'tcx: 'a> {
 624     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 625 }
 626
 627 impl<'a, 'tcx> ClauseDumper<'a, 'tcx> {
 628     fn process_attrs(&mut self, node_id: ast::NodeId, attrs: &[ast::Attribute]) {
 629         let def_id = self.tcx.hir().local_def_id(node_id);
 630         for attr in attrs {
 631             let mut clauses = None;
 632
 633             if attr.check_name("rustc_dump_program_clauses") {
 634                 clauses = Some(self.tcx.program_clauses_for(def_id));
 635             }
 636
 637             if attr.check_name("rustc_dump_env_program_clauses") {
 638                 let environment = self.tcx.environment(def_id);
 639                 clauses = Some(self.tcx.program_clauses_for_env(*environment.skip_binder()));
 640             }
 641
 642             if let Some(clauses) = clauses {
 643                 let mut err = self
 644                     .tcx
 645                     .sess
 646                     .struct_span_err(attr.span, "program clause dump");
 647
 648                 let mut strings: Vec<_> = clauses
 649                     .iter()
 650                     .map(|clause| clause.to_string())
 651                     .collect();
 652
 653                 strings.sort();
 654
 655                 for string in strings {
 656                     err.note(&string);
 657                 }
 658
 659                 err.emit();
 660             }
 661         }
 662     }
 663 }
 664
 665 impl<'a, 'tcx> Visitor<'tcx> for ClauseDumper<'a, 'tcx> {
 666     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 667         NestedVisitorMap::OnlyBodies(&self.tcx.hir())
 668     }
 669
 670     fn visit_item(&mut self, item: &'tcx hir::Item) {
 671         self.process_attrs(item.id, &item.attrs);
 672         intravisit::walk_item(self, item);
 673     }
 674
 675     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 676         self.process_attrs(trait_item.id, &trait_item.attrs);
 677         intravisit::walk_trait_item(self, trait_item);
 678     }
 679
 680     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 681         self.process_attrs(impl_item.id, &impl_item.attrs);
 682         intravisit::walk_impl_item(self, impl_item);
 683     }
 684
 685     fn visit_struct_field(&mut self, s: &'tcx hir::StructField) {
 686         self.process_attrs(s.id, &s.attrs);
 687         intravisit::walk_struct_field(self, s);
 688     }
 689 }