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