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>(
 159     tcx: TyCtxt<'tcx, 'tcx>,
 160     def_id: DefId,
 161 ) -> Clauses<'tcx> {
 162     // FIXME(eddyb) this should only be using `def_kind`.
 163     match tcx.def_key(def_id).disambiguated_data.data {
 164         DefPathData::TypeNs(..) => match tcx.def_kind(def_id) {
 165             Some(DefKind::Trait)
 166             | Some(DefKind::TraitAlias) => program_clauses_for_trait(tcx, def_id),
 167             // FIXME(eddyb) deduplicate this `associated_item` call with
 168             // `program_clauses_for_associated_type_{value,def}`.
 169             Some(DefKind::AssocTy) => match tcx.associated_item(def_id).container {
 170                 ty::AssocItemContainer::ImplContainer(_) =>
 171                     program_clauses_for_associated_type_value(tcx, def_id),
 172                 ty::AssocItemContainer::TraitContainer(_) =>
 173                     program_clauses_for_associated_type_def(tcx, def_id)
 174             },
 175             Some(DefKind::Struct)
 176             | Some(DefKind::Enum)
 177             | Some(DefKind::TyAlias)
 178             | Some(DefKind::Union)
 179             | Some(DefKind::Existential) => program_clauses_for_type_def(tcx, def_id),
 180             _ => List::empty(),
 181         },
 182         DefPathData::Impl => program_clauses_for_impl(tcx, def_id),
 183         _ => List::empty(),
 184     }
 185 }
 186
 187 fn program_clauses_for_trait<'tcx>(
 188     tcx: TyCtxt<'tcx, 'tcx>,
 189     def_id: DefId,
 190 ) -> Clauses<'tcx> {
 191     // `trait Trait<P1..Pn> where WC { .. } // P0 == Self`
 192
 193     // Rule Implemented-From-Env (see rustc guide)
 194     //
 195     // ```
 196     // forall<Self, P1..Pn> {
 197     //   Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)
 198     // }
 199     // ```
 200
 201     let bound_vars = InternalSubsts::bound_vars_for_item(tcx, def_id);
 202
 203     // `Self: Trait<P1..Pn>`
 204     let trait_pred = ty::TraitPredicate {
 205         trait_ref: ty::TraitRef {
 206             def_id,
 207             substs: bound_vars,
 208         },
 209     };
 210
 211     // `Implemented(Self: Trait<P1..Pn>)`
 212     let impl_trait: DomainGoal<'_> = trait_pred.lower();
 213
 214     // `FromEnv(Self: Trait<P1..Pn>)`
 215     let from_env_goal = tcx.mk_goal(impl_trait.into_from_env_goal().into_goal());
 216     let hypotheses = tcx.intern_goals(&[from_env_goal]);
 217
 218     // `Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)`
 219     let implemented_from_env = ProgramClause {
 220         goal: impl_trait,
 221         hypotheses,
 222         category: ProgramClauseCategory::ImpliedBound,
 223     };
 224
 225     let implemented_from_env = Clause::ForAll(ty::Binder::bind(implemented_from_env));
 226
 227     let predicates = &tcx.predicates_defined_on(def_id).predicates;
 228
 229     // Warning: these where clauses are not substituted for bound vars yet,
 230     // so that we don't need to adjust binders in the `FromEnv` rules below
 231     // (see the FIXME).
 232     let where_clauses = &predicates
 233         .iter()
 234         .map(|(wc, _)| wc.lower())
 235         .collect::<Vec<_>>();
 236
 237     // Rule Implied-Bound-From-Trait
 238     //
 239     // For each where clause WC:
 240     // ```
 241     // forall<Self, P1..Pn> {
 242     //   FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn)
 243     // }
 244     // ```
 245
 246     // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`, for each where clause WC
 247     let implied_bound_clauses = where_clauses
 248         .iter()
 249         .cloned()
 250
 251         // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`
 252         .map(|wc| {
 253             // we move binders to the left
 254             wc.map_bound(|goal| ProgramClause {
 255                 // FIXME: As where clauses can only bind lifetimes for now, and that named
 256                 // bound regions have a def-id, it is safe to just inject `bound_vars` and
 257                 // `hypotheses` (which contain named vars bound at index `0`) into this
 258                 // binding level. This may change if we ever allow where clauses to bind
 259                 // types (e.g. for GATs things), because bound types only use a `BoundVar`
 260                 // index (no def-id).
 261                 goal: goal.subst(tcx, bound_vars).into_from_env_goal(),
 262                 hypotheses,
 263
 264                 category: ProgramClauseCategory::ImpliedBound,
 265             })
 266         })
 267         .map(Clause::ForAll);
 268
 269     // Rule WellFormed-TraitRef
 270     //
 271     // Here `WC` denotes the set of all where clauses:
 272     // ```
 273     // forall<Self, P1..Pn> {
 274     //   WellFormed(Self: Trait<P1..Pn>) :- Implemented(Self: Trait<P1..Pn>) && WellFormed(WC)
 275     // }
 276     // ```
 277
 278     // `WellFormed(WC)`
 279     let wf_conditions = where_clauses
 280         .into_iter()
 281         .map(|wc| wc.subst(tcx, bound_vars))
 282         .map(|wc| wc.map_bound(|goal| goal.into_well_formed_goal()));
 283
 284     // `WellFormed(Self: Trait<P1..Pn>) :- Implemented(Self: Trait<P1..Pn>) && WellFormed(WC)`
 285     let wf_clause = ProgramClause {
 286         goal: DomainGoal::WellFormed(WellFormed::Trait(trait_pred)),
 287         hypotheses: tcx.mk_goals(
 288             iter::once(tcx.mk_goal(GoalKind::DomainGoal(impl_trait))).chain(
 289                 wf_conditions.map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx)))
 290             )
 291         ),
 292         category: ProgramClauseCategory::WellFormed,
 293     };
 294     let wf_clause = Clause::ForAll(ty::Binder::bind(wf_clause));
 295
 296     tcx.mk_clauses(
 297         iter::once(implemented_from_env)
 298             .chain(implied_bound_clauses)
 299             .chain(iter::once(wf_clause))
 300     )
 301 }
 302
 303 fn program_clauses_for_impl(tcx: TyCtxt<'tcx, 'tcx>, def_id: DefId) -> Clauses<'tcx> {
 304     if let ImplPolarity::Negative = tcx.impl_polarity(def_id) {
 305         return List::empty();
 306     }
 307
 308     // Rule Implemented-From-Impl (see rustc guide)
 309     //
 310     // `impl<P0..Pn> Trait<A1..An> for A0 where WC { .. }`
 311     //
 312     // ```
 313     // forall<P0..Pn> {
 314     //   Implemented(A0: Trait<A1..An>) :- WC
 315     // }
 316     // ```
 317
 318     let bound_vars = InternalSubsts::bound_vars_for_item(tcx, def_id);
 319
 320     let trait_ref = tcx.impl_trait_ref(def_id)
 321         .expect("not an impl")
 322         .subst(tcx, bound_vars);
 323
 324     // `Implemented(A0: Trait<A1..An>)`
 325     let trait_pred = ty::TraitPredicate { trait_ref }.lower();
 326
 327     // `WC`
 328     let predicates = &tcx.predicates_of(def_id).predicates;
 329     let where_clauses = predicates
 330         .iter()
 331         .map(|(wc, _)| wc.lower())
 332         .map(|wc| wc.subst(tcx, bound_vars));
 333
 334     // `Implemented(A0: Trait<A1..An>) :- WC`
 335     let clause = ProgramClause {
 336         goal: trait_pred,
 337         hypotheses: tcx.mk_goals(
 338             where_clauses
 339                 .map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx))),
 340         ),
 341         category: ProgramClauseCategory::Other,
 342     };
 343     tcx.mk_clauses(iter::once(Clause::ForAll(ty::Binder::bind(clause))))
 344 }
 345
 346 pub fn program_clauses_for_type_def<'tcx>(
 347     tcx: TyCtxt<'tcx, 'tcx>,
 348     def_id: DefId,
 349 ) -> Clauses<'tcx> {
 350     // Rule WellFormed-Type
 351     //
 352     // `struct Ty<P1..Pn> where WC1, ..., WCm`
 353     //
 354     // ```
 355     // forall<P1..Pn> {
 356     //   WellFormed(Ty<...>) :- WellFormed(WC1), ..., WellFormed(WCm)`
 357     // }
 358     // ```
 359
 360     let bound_vars = InternalSubsts::bound_vars_for_item(tcx, def_id);
 361
 362     // `Ty<...>`
 363     let ty = tcx.type_of(def_id).subst(tcx, bound_vars);
 364
 365     // Warning: these where clauses are not substituted for bound vars yet,
 366     // so that we don't need to adjust binders in the `FromEnv` rules below
 367     // (see the FIXME).
 368     let where_clauses = tcx.predicates_of(def_id).predicates
 369         .iter()
 370         .map(|(wc, _)| wc.lower())
 371         .collect::<Vec<_>>();
 372
 373     // `WellFormed(Ty<...>) :- WellFormed(WC1), ..., WellFormed(WCm)`
 374     let well_formed_clause = ProgramClause {
 375         goal: DomainGoal::WellFormed(WellFormed::Ty(ty)),
 376         hypotheses: tcx.mk_goals(
 377             where_clauses
 378                 .iter()
 379                 .map(|wc| wc.subst(tcx, bound_vars))
 380                 .map(|wc| wc.map_bound(|bound| bound.into_well_formed_goal()))
 381                 .map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx))),
 382         ),
 383         category: ProgramClauseCategory::WellFormed,
 384     };
 385     let well_formed_clause = Clause::ForAll(ty::Binder::bind(well_formed_clause));
 386
 387     // Rule Implied-Bound-From-Type
 388     //
 389     // For each where clause `WC`:
 390     // ```
 391     // forall<P1..Pn> {
 392     //   FromEnv(WC) :- FromEnv(Ty<...>)
 393     // }
 394     // ```
 395
 396     // `FromEnv(Ty<...>)`
 397     let from_env_goal = tcx.mk_goal(DomainGoal::FromEnv(FromEnv::Ty(ty)).into_goal());
 398     let hypotheses = tcx.intern_goals(&[from_env_goal]);
 399
 400     // For each where clause `WC`:
 401     let from_env_clauses = where_clauses
 402         .into_iter()
 403
 404         // `FromEnv(WC) :- FromEnv(Ty<...>)`
 405         .map(|wc| {
 406             // move the binders to the left
 407             wc.map_bound(|goal| ProgramClause {
 408                 // FIXME: we inject `bound_vars` and `hypotheses` into this binding
 409                 // level, which may be incorrect in the future: see the FIXME in
 410                 // `program_clauses_for_trait`.
 411                 goal: goal.subst(tcx, bound_vars).into_from_env_goal(),
 412                 hypotheses,
 413
 414                 category: ProgramClauseCategory::ImpliedBound,
 415             })
 416         })
 417
 418         .map(Clause::ForAll);
 419
 420     tcx.mk_clauses(iter::once(well_formed_clause).chain(from_env_clauses))
 421 }
 422
 423 pub fn program_clauses_for_associated_type_def<'tcx>(
 424     tcx: TyCtxt<'tcx, 'tcx>,
 425     item_id: DefId,
 426 ) -> Clauses<'tcx> {
 427     // Rule ProjectionEq-Placeholder
 428     //
 429     // ```
 430     // trait Trait<P1..Pn> {
 431     //     type AssocType<Pn+1..Pm>;
 432     // }
 433     // ```
 434     //
 435     // `ProjectionEq` can succeed by skolemizing, see "associated type"
 436     // chapter for more:
 437     // ```
 438     // forall<Self, P1..Pn, Pn+1..Pm> {
 439     //     ProjectionEq(
 440     //         <Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> =
 441     //         (Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>
 442     //     )
 443     // }
 444     // ```
 445
 446     let item = tcx.associated_item(item_id);
 447     debug_assert_eq!(item.kind, ty::AssocKind::Type);
 448     let trait_id = match item.container {
 449         ty::AssocItemContainer::TraitContainer(trait_id) => trait_id,
 450         _ => bug!("not an trait container"),
 451     };
 452
 453     let trait_bound_vars = InternalSubsts::bound_vars_for_item(tcx, trait_id);
 454     let trait_ref = ty::TraitRef {
 455         def_id: trait_id,
 456         substs: trait_bound_vars,
 457     };
 458
 459     let projection_ty = ty::ProjectionTy::from_ref_and_name(tcx, trait_ref, item.ident);
 460     let placeholder_ty = tcx.mk_ty(ty::UnnormalizedProjection(projection_ty));
 461     let projection_eq = WhereClause::ProjectionEq(ty::ProjectionPredicate {
 462         projection_ty,
 463         ty: placeholder_ty,
 464     });
 465
 466     let projection_eq_clause = ProgramClause {
 467         goal: DomainGoal::Holds(projection_eq),
 468         hypotheses: ty::List::empty(),
 469         category: ProgramClauseCategory::Other,
 470     };
 471     let projection_eq_clause = Clause::ForAll(ty::Binder::bind(projection_eq_clause));
 472
 473     // Rule WellFormed-AssocTy
 474     // ```
 475     // forall<Self, P1..Pn, Pn+1..Pm> {
 476     //     WellFormed((Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>)
 477     //         :- WellFormed(Self: Trait<P1..Pn>)
 478     // }
 479     // ```
 480
 481     let trait_predicate = ty::TraitPredicate { trait_ref };
 482     let hypothesis = tcx.mk_goal(
 483         DomainGoal::WellFormed(WellFormed::Trait(trait_predicate)).into_goal()
 484     );
 485
 486     let wf_clause = ProgramClause {
 487         goal: DomainGoal::WellFormed(WellFormed::Ty(placeholder_ty)),
 488         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 489         category: ProgramClauseCategory::WellFormed,
 490     };
 491     let wf_clause = Clause::ForAll(ty::Binder::bind(wf_clause));
 492
 493     // Rule Implied-Trait-From-AssocTy
 494     // ```
 495     // forall<Self, P1..Pn, Pn+1..Pm> {
 496     //     FromEnv(Self: Trait<P1..Pn>)
 497     //         :- FromEnv((Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>)
 498     // }
 499     // ```
 500
 501     let hypothesis = tcx.mk_goal(
 502         DomainGoal::FromEnv(FromEnv::Ty(placeholder_ty)).into_goal()
 503     );
 504
 505     let from_env_clause = ProgramClause {
 506         goal: DomainGoal::FromEnv(FromEnv::Trait(trait_predicate)),
 507         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 508         category: ProgramClauseCategory::ImpliedBound,
 509     };
 510     let from_env_clause = Clause::ForAll(ty::Binder::bind(from_env_clause));
 511
 512     // Rule ProjectionEq-Normalize
 513     //
 514     // ProjectionEq can succeed by normalizing:
 515     // ```
 516     // forall<Self, P1..Pn, Pn+1..Pm, U> {
 517     //   ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U) :-
 518     //       Normalize(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> -> U)
 519     // }
 520     // ```
 521
 522     let offset = tcx.generics_of(trait_id).params
 523         .iter()
 524         .map(|p| p.index)
 525         .max()
 526         .unwrap_or(0);
 527     // Add a new type param after the existing ones (`U` in the comment above).
 528     let ty_var = ty::Bound(
 529         ty::INNERMOST,
 530         ty::BoundVar::from_u32(offset + 1).into()
 531     );
 532
 533     // `ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U)`
 534     let projection = ty::ProjectionPredicate {
 535         projection_ty,
 536         ty: tcx.mk_ty(ty_var),
 537     };
 538
 539     // `Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> U)`
 540     let hypothesis = tcx.mk_goal(
 541         DomainGoal::Normalize(projection).into_goal()
 542     );
 543
 544     //  ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U) :-
 545     //      Normalize(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> -> U)
 546     let normalize_clause = ProgramClause {
 547         goal: DomainGoal::Holds(WhereClause::ProjectionEq(projection)),
 548         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 549         category: ProgramClauseCategory::Other,
 550     };
 551     let normalize_clause = Clause::ForAll(ty::Binder::bind(normalize_clause));
 552
 553     let clauses = iter::once(projection_eq_clause)
 554         .chain(iter::once(wf_clause))
 555         .chain(iter::once(from_env_clause))
 556         .chain(iter::once(normalize_clause));
 557
 558     tcx.mk_clauses(clauses)
 559 }
 560
 561 pub fn program_clauses_for_associated_type_value<'tcx>(
 562     tcx: TyCtxt<'tcx, 'tcx>,
 563     item_id: DefId,
 564 ) -> Clauses<'tcx> {
 565     // Rule Normalize-From-Impl (see rustc guide)
 566     //
 567     // ```
 568     // impl<P0..Pn> Trait<A1..An> for A0 {
 569     //     type AssocType<Pn+1..Pm> = T;
 570     // }
 571     // ```
 572     //
 573     // FIXME: For the moment, we don't account for where clauses written on the associated
 574     // ty definition (i.e., in the trait def, as in `type AssocType<T> where T: Sized`).
 575     // ```
 576     // forall<P0..Pm> {
 577     //   forall<Pn+1..Pm> {
 578     //     Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T) :-
 579     //       Implemented(A0: Trait<A1..An>)
 580     //   }
 581     // }
 582     // ```
 583
 584     let item = tcx.associated_item(item_id);
 585     debug_assert_eq!(item.kind, ty::AssocKind::Type);
 586     let impl_id = match item.container {
 587         ty::AssocItemContainer::ImplContainer(impl_id) => impl_id,
 588         _ => bug!("not an impl container"),
 589     };
 590
 591     let impl_bound_vars = InternalSubsts::bound_vars_for_item(tcx, impl_id);
 592
 593     // `A0 as Trait<A1..An>`
 594     let trait_ref = tcx.impl_trait_ref(impl_id)
 595         .unwrap()
 596         .subst(tcx, impl_bound_vars);
 597
 598     // `T`
 599     let ty = tcx.type_of(item_id);
 600
 601     // `Implemented(A0: Trait<A1..An>)`
 602     let trait_implemented: DomainGoal<'_> = ty::TraitPredicate { trait_ref }.lower();
 603
 604     // `<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm>`
 605     let projection_ty = ty::ProjectionTy::from_ref_and_name(tcx, trait_ref, item.ident);
 606
 607     // `Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T)`
 608     let normalize_goal = DomainGoal::Normalize(ty::ProjectionPredicate { projection_ty, ty });
 609
 610     // `Normalize(... -> T) :- ...`
 611     let normalize_clause = ProgramClause {
 612         goal: normalize_goal,
 613         hypotheses: tcx.mk_goals(
 614             iter::once(tcx.mk_goal(GoalKind::DomainGoal(trait_implemented)))
 615         ),
 616         category: ProgramClauseCategory::Other,
 617     };
 618     let normalize_clause = Clause::ForAll(ty::Binder::bind(normalize_clause));
 619
 620     tcx.mk_clauses(iter::once(normalize_clause))
 621 }
 622
 623 pub fn dump_program_clauses<'tcx>(tcx: TyCtxt<'tcx, 'tcx>) {
 624     if !tcx.features().rustc_attrs {
 625         return;
 626     }
 627
 628     let mut visitor = ClauseDumper { tcx };
 629     tcx.hir()
 630         .krate()
 631         .visit_all_item_likes(&mut visitor.as_deep_visitor());
 632 }
 633
 634 struct ClauseDumper<'tcx> {
 635     tcx: TyCtxt<'tcx, 'tcx>,
 636 }
 637
 638 impl ClauseDumper<'tcx> {
 639     fn process_attrs(&mut self, hir_id: hir::HirId, attrs: &[ast::Attribute]) {
 640         let def_id = self.tcx.hir().local_def_id_from_hir_id(hir_id);
 641         for attr in attrs {
 642             let mut clauses = None;
 643
 644             if attr.check_name(sym::rustc_dump_program_clauses) {
 645                 clauses = Some(self.tcx.program_clauses_for(def_id));
 646             }
 647
 648             if attr.check_name(sym::rustc_dump_env_program_clauses) {
 649                 let environment = self.tcx.environment(def_id);
 650                 clauses = Some(self.tcx.program_clauses_for_env(environment));
 651             }
 652
 653             if let Some(clauses) = clauses {
 654                 let mut err = self
 655                     .tcx
 656                     .sess
 657                     .struct_span_err(attr.span, "program clause dump");
 658
 659                 let mut strings: Vec<_> = clauses
 660                     .iter()
 661                     .map(|clause| clause.to_string())
 662                     .collect();
 663
 664                 strings.sort();
 665
 666                 for string in strings {
 667                     err.note(&string);
 668                 }
 669
 670                 err.emit();
 671             }
 672         }
 673     }
 674 }
 675
 676 impl Visitor<'tcx> for ClauseDumper<'tcx> {
 677     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 678         NestedVisitorMap::OnlyBodies(&self.tcx.hir())
 679     }
 680
 681     fn visit_item(&mut self, item: &'tcx hir::Item) {
 682         self.process_attrs(item.hir_id, &item.attrs);
 683         intravisit::walk_item(self, item);
 684     }
 685
 686     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 687         self.process_attrs(trait_item.hir_id, &trait_item.attrs);
 688         intravisit::walk_trait_item(self, trait_item);
 689     }
 690
 691     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 692         self.process_attrs(impl_item.hir_id, &impl_item.attrs);
 693         intravisit::walk_impl_item(self, impl_item);
 694     }
 695
 696     fn visit_struct_field(&mut self, s: &'tcx hir::StructField) {
 697         self.process_attrs(s.hir_id, &s.attrs);
 698         intravisit::walk_struct_field(self, s);
 699     }
 700 }