src/librustc_traits/lowering.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 use rustc::hir::{self, ImplPolarity};
  12 use rustc::hir::def_id::DefId;
  13 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
  14 use rustc::ty::{self, Slice, TyCtxt};
  15 use rustc::ty::subst::Substs;
  16 use rustc::traits::{WhereClauseAtom, PolyDomainGoal, DomainGoal, ProgramClause, Clause, Goal};
  17 use syntax::ast;
  18 use rustc_data_structures::sync::Lrc;
  19
  20 use std::iter;
  21
  22 trait Lower<T> {
  23     /// Lower a rustc construction (e.g. `ty::TraitPredicate`) to a chalk-like type.
  24     fn lower(&self) -> T;
  25 }
  26
  27 impl<T, U> Lower<Vec<U>> for Vec<T> where T: Lower<U> {
  28     fn lower(&self) -> Vec<U> {
  29         self.iter().map(|item| item.lower()).collect()
  30     }
  31 }
  32
  33 impl<'tcx> Lower<WhereClauseAtom<'tcx>> for ty::TraitPredicate<'tcx> {
  34     fn lower(&self) -> WhereClauseAtom<'tcx> {
  35         WhereClauseAtom::Implemented(*self)
  36     }
  37 }
  38
  39 impl<'tcx> Lower<WhereClauseAtom<'tcx>> for ty::ProjectionPredicate<'tcx> {
  40     fn lower(&self) -> WhereClauseAtom<'tcx> {
  41         WhereClauseAtom::ProjectionEq(*self)
  42     }
  43 }
  44
  45 impl<'tcx, T> Lower<DomainGoal<'tcx>> for T where T: Lower<WhereClauseAtom<'tcx>> {
  46     fn lower(&self) -> DomainGoal<'tcx> {
  47         DomainGoal::Holds(self.lower())
  48     }
  49 }
  50
  51 impl<'tcx> Lower<DomainGoal<'tcx>> for ty::RegionOutlivesPredicate<'tcx> {
  52     fn lower(&self) -> DomainGoal<'tcx> {
  53         DomainGoal::RegionOutlives(*self)
  54     }
  55 }
  56
  57 impl<'tcx> Lower<DomainGoal<'tcx>> for ty::TypeOutlivesPredicate<'tcx> {
  58     fn lower(&self) -> DomainGoal<'tcx> {
  59         DomainGoal::TypeOutlives(*self)
  60     }
  61 }
  62
  63 /// `ty::Binder` is used for wrapping a rustc construction possibly containing generic
  64 /// lifetimes, e.g. `for<'a> T: Fn(&'a i32)`. Instead of representing higher-ranked things
  65 /// in that leaf-form (i.e. `Holds(Implemented(Binder<TraitPredicate>))` in the previous
  66 /// example), we model them with quantified domain goals, e.g. as for the previous example:
  67 /// `forall<'a> { T: Fn(&'a i32) }` which corresponds to something like
  68 /// `Binder<Holds(Implemented(TraitPredicate))>`.
  69 impl<'tcx, T> Lower<PolyDomainGoal<'tcx>> for ty::Binder<T>
  70     where T: Lower<DomainGoal<'tcx>> + ty::fold::TypeFoldable<'tcx>
  71 {
  72     fn lower(&self) -> PolyDomainGoal<'tcx> {
  73         self.map_bound_ref(|p| p.lower())
  74     }
  75 }
  76
  77 impl<'tcx> Lower<PolyDomainGoal<'tcx>> for ty::Predicate<'tcx> {
  78     fn lower(&self) -> PolyDomainGoal<'tcx> {
  79         use rustc::ty::Predicate::*;
  80
  81         match self {
  82             Trait(predicate) => predicate.lower(),
  83             RegionOutlives(predicate) => predicate.lower(),
  84             TypeOutlives(predicate) => predicate.lower(),
  85             Projection(predicate) => predicate.lower(),
  86             WellFormed(ty) => ty::Binder::dummy(DomainGoal::WellFormedTy(*ty)),
  87             ObjectSafe(..) |
  88             ClosureKind(..) |
  89             Subtype(..) |
  90             ConstEvaluatable(..) => unimplemented!(),
  91         }
  92     }
  93 }
  94
  95 /// Transforms an existing goal into a FromEnv goal.
  96 ///
  97 /// Used for lowered where clauses (see rustc guide).
  98 trait IntoFromEnvGoal {
  99     fn into_from_env_goal(self) -> Self;
 100 }
 101
 102 impl<'tcx> IntoFromEnvGoal for DomainGoal<'tcx> {
 103     fn into_from_env_goal(self) -> DomainGoal<'tcx> {
 104         use self::DomainGoal::*;
 105         match self {
 106             Holds(wc_atom) => FromEnv(wc_atom),
 107             WellFormed(..) |
 108             FromEnv(..) |
 109             WellFormedTy(..) |
 110             FromEnvTy(..) |
 111             RegionOutlives(..) |
 112             TypeOutlives(..) => self,
 113         }
 114     }
 115 }
 116
 117 crate fn program_clauses_for<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
 118                                        -> Lrc<&'tcx Slice<Clause<'tcx>>>
 119 {
 120     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 121     let node = tcx.hir.find(node_id).unwrap();
 122     match node {
 123         hir::map::Node::NodeItem(item) => match item.node {
 124             hir::ItemTrait(..) => program_clauses_for_trait(tcx, def_id),
 125             hir::ItemImpl(..) => program_clauses_for_impl(tcx, def_id),
 126             _ => Lrc::new(vec![]),
 127         }
 128         hir::map::Node::NodeImplItem(item) => {
 129             if let hir::ImplItemKind::Type(..) = item.node {
 130                 program_clauses_for_associated_type_value(tcx, def_id)
 131             } else {
 132                 Lrc::new(vec![])
 133             }
 134         },
 135
 136         // FIXME: other constructions e.g. traits, associated types...
 137         _ => Lrc::new(tcx.mk_clauses(iter::empty::<Clause>())),
 138     }
 139 }
 140
 141 fn program_clauses_for_trait<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
 142                                        -> Lrc<&'tcx Slice<Clause<'tcx>>>
 143 {
 144     // `trait Trait<P1..Pn> where WC { .. } // P0 == Self`
 145
 146     // Rule Implemented-From-Env (see rustc guide)
 147     //
 148     // ```
 149     // forall<Self, P1..Pn> {
 150     //   Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)
 151     // }
 152     // ```
 153
 154     // `Self: Trait<P1..Pn>`
 155     let trait_pred = ty::TraitPredicate {
 156         trait_ref: ty::TraitRef {
 157             def_id,
 158             substs: Substs::identity_for_item(tcx, def_id)
 159         }
 160     };
 161     // `FromEnv(Self: Trait<P1..Pn>)`
 162     let from_env = Goal::from(DomainGoal::FromEnv(trait_pred.lower()));
 163     // `Implemented(Self: Trait<P1..Pn>)`
 164     let impl_trait = DomainGoal::Holds(WhereClauseAtom::Implemented(trait_pred));
 165
 166     // `Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)`
 167     let implemented_from_env = ProgramClause {
 168         goal: impl_trait,
 169         hypotheses: tcx.mk_goals(iter::once(from_env)),
 170     };
 171     let clauses = iter::once(
 172         Clause::ForAll(ty::Binder::dummy(implemented_from_env))
 173     );
 174
 175     // Rule Implied-Bound-From-Trait
 176     //
 177     // For each where clause WC:
 178     // ```
 179     // forall<Self, P1..Pn> {
 180     //   FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn)
 181     // }
 182     // ```
 183
 184     // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`, for each where clause WC
 185     // FIXME: Remove the [1..] slice; this is a hack because the query
 186     // predicates_of currently includes the trait itself (`Self: Trait<P1..Pn>`).
 187     let where_clauses = &tcx.predicates_of(def_id).predicates;
 188     let implied_bound_clauses =
 189         where_clauses[1..].into_iter()
 190         .map(|wc| implied_bound_from_trait(tcx, trait_pred, wc));
 191
 192     Lrc::new(tcx.mk_clauses(clauses.chain(implied_bound_clauses)))
 193 }
 194
 195 /// For a given `where_clause`, returns a clause `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`.
 196 fn implied_bound_from_trait<'a, 'tcx>(
 197     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 198     trait_pred: ty::TraitPredicate<'tcx>,
 199     where_clause: &ty::Predicate<'tcx>,
 200 ) -> Clause<'tcx> {
 201     // `FromEnv(Self: Trait<P1..Pn>)`
 202     let impl_trait = DomainGoal::FromEnv(WhereClauseAtom::Implemented(trait_pred));
 203
 204     // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`
 205     Clause::ForAll(
 206         where_clause.lower().map_bound(|goal| ProgramClause {
 207             goal: goal.into_from_env_goal(),
 208             hypotheses: tcx.mk_goals(iter::once(Goal::from(impl_trait))),
 209         })
 210     )
 211 }
 212
 213 fn program_clauses_for_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
 214                                       -> Lrc<&'tcx Slice<Clause<'tcx>>>
 215 {
 216     if let ImplPolarity::Negative = tcx.impl_polarity(def_id) {
 217         return Lrc::new(tcx.mk_clauses(iter::empty::<Clause>()));
 218     }
 219
 220     // Rule Implemented-From-Impl (see rustc guide)
 221     //
 222     // `impl<P0..Pn> Trait<A1..An> for A0 where WC { .. }`
 223     //
 224     // ```
 225     // forall<P0..Pn> {
 226     //   Implemented(A0: Trait<A1..An>) :- WC
 227     // }
 228     // ```
 229
 230     let trait_ref = tcx.impl_trait_ref(def_id).unwrap();
 231     // `Implemented(A0: Trait<A1..An>)`
 232     let trait_pred = ty::TraitPredicate { trait_ref }.lower();
 233      // `WC`
 234     let where_clauses = tcx.predicates_of(def_id).predicates.lower();
 235
 236      // `Implemented(A0: Trait<A1..An>) :- WC`
 237     let clause = ProgramClause {
 238         goal: trait_pred,
 239         hypotheses: tcx.mk_goals(
 240             where_clauses.into_iter().map(|wc| Goal::from_poly_domain_goal(wc, tcx))
 241         )
 242     };
 243     Lrc::new(tcx.mk_clauses(iter::once(Clause::ForAll(ty::Binder::dummy(clause)))))
 244 }
 245
 246 pub fn program_clauses_for_associated_type_value<'a, 'tcx>(
 247     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 248     item_id: DefId,
 249 ) -> Lrc<Vec<Clause<'tcx>>> {
 250     // Rule Normalize-From-Impl (see rustc guide)
 251     //
 252     // ```impl<P0..Pn> Trait<A1..An> for A0
 253     // where WC
 254     // {
 255     //     type AssocType<Pn+1..Pm> where WC1 = T;
 256     // }```
 257     //
 258     // ```
 259     // forall<P0..Pm> {
 260     //   forall<Pn+1..Pm> {
 261     //     Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T) :-
 262     //       WC && WC1
 263     //   }
 264     // }
 265     // ```
 266
 267     let item = tcx.associated_item(item_id);
 268     debug_assert_eq!(item.kind, ty::AssociatedKind::Type);
 269     let impl_id = if let ty::AssociatedItemContainer::ImplContainer(impl_id) = item.container {
 270         impl_id
 271     } else {
 272         bug!()
 273     };
 274     // `A0 as Trait<A1..An>`
 275     let trait_ref = tcx.impl_trait_ref(impl_id).unwrap();
 276     // `T`
 277     let ty = tcx.type_of(item_id);
 278     // `WC`
 279     let impl_where_clauses = tcx.predicates_of(impl_id).predicates.lower();
 280     // `WC1`
 281     let item_where_clauses = tcx.predicates_of(item_id).predicates.lower();
 282     // `WC && WC1`
 283     let mut where_clauses = vec![];
 284     where_clauses.extend(impl_where_clauses);
 285     where_clauses.extend(item_where_clauses);
 286     // `<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm>`
 287     let projection_ty = ty::ProjectionTy::from_ref_and_name(tcx, trait_ref, item.name);
 288     // `Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T)`
 289     let normalize_goal = DomainGoal::Normalize(ty::ProjectionPredicate { projection_ty, ty });
 290     // `Normalize(... -> T) :- WC && WC1`
 291     let clause = Clause::Implies(where_clauses, normalize_goal);
 292     Lrc::new(vec![clause])
 293 }
 294
 295 pub fn dump_program_clauses<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
 296     if !tcx.features().rustc_attrs {
 297         return;
 298     }
 299
 300     let mut visitor = ClauseDumper { tcx };
 301     tcx.hir.krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
 302 }
 303
 304 struct ClauseDumper<'a, 'tcx: 'a> {
 305     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 306 }
 307
 308 impl<'a, 'tcx> ClauseDumper<'a, 'tcx > {
 309     fn process_attrs(&mut self, node_id: ast::NodeId, attrs: &[ast::Attribute]) {
 310         let def_id = self.tcx.hir.local_def_id(node_id);
 311         for attr in attrs {
 312             if attr.check_name("rustc_dump_program_clauses") {
 313                 let clauses = self.tcx.program_clauses_for(def_id);
 314                 for clause in *clauses {
 315                     // Skip the top-level binder for a less verbose output
 316                     let program_clause = match clause {
 317                         Clause::Implies(program_clause) => program_clause,
 318                         Clause::ForAll(program_clause) => program_clause.skip_binder(),
 319                     };
 320                     self.tcx.sess.struct_span_err(attr.span, &format!("{}", program_clause)).emit();
 321                 }
 322             }
 323         }
 324     }
 325 }
 326
 327 impl<'a, 'tcx> Visitor<'tcx> for ClauseDumper<'a, 'tcx> {
 328     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 329         NestedVisitorMap::OnlyBodies(&self.tcx.hir)
 330     }
 331
 332     fn visit_item(&mut self, item: &'tcx hir::Item) {
 333         self.process_attrs(item.id, &item.attrs);
 334         intravisit::walk_item(self, item);
 335     }
 336
 337     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 338         self.process_attrs(trait_item.id, &trait_item.attrs);
 339         intravisit::walk_trait_item(self, trait_item);
 340     }
 341
 342     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 343         self.process_attrs(impl_item.id, &impl_item.attrs);
 344         intravisit::walk_impl_item(self, impl_item);
 345     }
 346
 347     fn visit_struct_field(&mut self, s: &'tcx hir::StructField) {
 348         self.process_attrs(s.id, &s.attrs);
 349         intravisit::walk_struct_field(self, s);
 350     }
 351 }