src/librustc_traits/lowering/mod.rs

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