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.
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.
11 use rustc
::hir
::def_id
::DefId
;
12 use rustc
::hir
::intravisit
::{self, NestedVisitorMap, Visitor}
;
13 use rustc
::hir
::map
::definitions
::DefPathData
;
14 use rustc
::hir
::{self, ImplPolarity}
;
15 use rustc
::traits
::{Clause
, Clauses
, DomainGoal
, Goal
, PolyDomainGoal
, ProgramClause
,
17 use rustc
::ty
::subst
::Substs
;
18 use rustc
::ty
::{self, Slice, TyCtxt}
;
19 use rustc_data_structures
::fx
::FxHashSet
;
25 crate trait Lower
<T
> {
26 /// Lower a rustc construction (e.g. `ty::TraitPredicate`) to a chalk-like type.
30 impl<T
, U
> Lower
<Vec
<U
>> for Vec
<T
>
34 fn lower(&self) -> Vec
<U
> {
35 self.iter().map(|item
| item
.lower()).collect()
39 impl<'tcx
> Lower
<WhereClauseAtom
<'tcx
>> for ty
::TraitPredicate
<'tcx
> {
40 fn lower(&self) -> WhereClauseAtom
<'tcx
> {
41 WhereClauseAtom
::Implemented(*self)
45 impl<'tcx
> Lower
<WhereClauseAtom
<'tcx
>> for ty
::ProjectionPredicate
<'tcx
> {
46 fn lower(&self) -> WhereClauseAtom
<'tcx
> {
47 WhereClauseAtom
::ProjectionEq(*self)
51 impl<'tcx
, T
> Lower
<DomainGoal
<'tcx
>> for T
53 T
: Lower
<WhereClauseAtom
<'tcx
>>,
55 fn lower(&self) -> DomainGoal
<'tcx
> {
56 DomainGoal
::Holds(self.lower())
60 impl<'tcx
> Lower
<DomainGoal
<'tcx
>> for ty
::RegionOutlivesPredicate
<'tcx
> {
61 fn lower(&self) -> DomainGoal
<'tcx
> {
62 DomainGoal
::RegionOutlives(*self)
66 impl<'tcx
> Lower
<DomainGoal
<'tcx
>> for ty
::TypeOutlivesPredicate
<'tcx
> {
67 fn lower(&self) -> DomainGoal
<'tcx
> {
68 DomainGoal
::TypeOutlives(*self)
72 /// `ty::Binder` is used for wrapping a rustc construction possibly containing generic
73 /// lifetimes, e.g. `for<'a> T: Fn(&'a i32)`. Instead of representing higher-ranked things
74 /// in that leaf-form (i.e. `Holds(Implemented(Binder<TraitPredicate>))` in the previous
75 /// example), we model them with quantified domain goals, e.g. as for the previous example:
76 /// `forall<'a> { T: Fn(&'a i32) }` which corresponds to something like
77 /// `Binder<Holds(Implemented(TraitPredicate))>`.
78 impl<'tcx
, T
> Lower
<PolyDomainGoal
<'tcx
>> for ty
::Binder
<T
>
80 T
: Lower
<DomainGoal
<'tcx
>> + ty
::fold
::TypeFoldable
<'tcx
>,
82 fn lower(&self) -> PolyDomainGoal
<'tcx
> {
83 self.map_bound_ref(|p
| p
.lower())
87 impl<'tcx
> Lower
<PolyDomainGoal
<'tcx
>> for ty
::Predicate
<'tcx
> {
88 fn lower(&self) -> PolyDomainGoal
<'tcx
> {
89 use rustc
::ty
::Predicate
::*;
92 Trait(predicate
) => predicate
.lower(),
93 RegionOutlives(predicate
) => predicate
.lower(),
94 TypeOutlives(predicate
) => predicate
.lower(),
95 Projection(predicate
) => predicate
.lower(),
96 WellFormed(ty
) => ty
::Binder
::dummy(DomainGoal
::WellFormedTy(*ty
)),
97 ObjectSafe(..) | ClosureKind(..) | Subtype(..) | ConstEvaluatable(..) => {
104 /// Transforms an existing goal into a FromEnv goal.
106 /// Used for lowered where clauses (see rustc guide).
107 trait IntoFromEnvGoal
{
108 fn into_from_env_goal(self) -> Self;
111 impl<'tcx
> IntoFromEnvGoal
for DomainGoal
<'tcx
> {
112 fn into_from_env_goal(self) -> DomainGoal
<'tcx
> {
113 use self::DomainGoal
::*;
115 Holds(wc_atom
) => FromEnv(wc_atom
),
116 WellFormed(..) | FromEnv(..) | WellFormedTy(..) | FromEnvTy(..) | Normalize(..)
117 | RegionOutlives(..) | TypeOutlives(..) => self,
122 crate fn program_clauses_for
<'a
, 'tcx
>(
123 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
126 match tcx
.def_key(def_id
).disambiguated_data
.data
{
127 DefPathData
::Trait(_
) => program_clauses_for_trait(tcx
, def_id
),
128 DefPathData
::Impl
=> program_clauses_for_impl(tcx
, def_id
),
129 DefPathData
::AssocTypeInImpl(..) => program_clauses_for_associated_type_value(tcx
, def_id
),
134 crate fn program_clauses_for_env
<'a
, 'tcx
>(
135 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
136 param_env
: ty
::ParamEnv
<'tcx
>,
138 debug
!("program_clauses_for_env(param_env={:?})", param_env
);
140 let mut last_round
= FxHashSet();
145 .flat_map(|&p
| predicate_def_id(p
)),
148 let mut closure
= last_round
.clone();
149 let mut next_round
= FxHashSet();
150 while !last_round
.is_empty() {
155 tcx
.predicates_of(def_id
)
156 .instantiate_identity(tcx
)
159 .flat_map(|p
| predicate_def_id(p
))
160 .filter(|&def_id
| closure
.insert(def_id
)),
162 mem
::swap(&mut next_round
, &mut last_round
);
165 debug
!("program_clauses_for_env: closure = {:#?}", closure
);
167 return tcx
.mk_clauses(
170 .flat_map(|def_id
| tcx
.program_clauses_for(def_id
).iter().cloned()),
173 /// Given that `predicate` is in the environment, returns the
174 /// def-id of something (e.g., a trait, associated item, etc)
175 /// whose predicates can also be assumed to be true. We will
176 /// compute the transitive closure of such things.
177 fn predicate_def_id
<'tcx
>(predicate
: ty
::Predicate
<'tcx
>) -> Option
<DefId
> {
179 ty
::Predicate
::Trait(predicate
) => Some(predicate
.def_id()),
181 ty
::Predicate
::Projection(projection
) => Some(projection
.item_def_id()),
183 ty
::Predicate
::WellFormed(..)
184 | ty
::Predicate
::RegionOutlives(..)
185 | ty
::Predicate
::TypeOutlives(..)
186 | ty
::Predicate
::ObjectSafe(..)
187 | ty
::Predicate
::ClosureKind(..)
188 | ty
::Predicate
::Subtype(..)
189 | ty
::Predicate
::ConstEvaluatable(..) => None
,
194 fn program_clauses_for_trait
<'a
, 'tcx
>(
195 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
198 // `trait Trait<P1..Pn> where WC { .. } // P0 == Self`
200 // Rule Implemented-From-Env (see rustc guide)
203 // forall<Self, P1..Pn> {
204 // Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)
208 // `Self: Trait<P1..Pn>`
209 let trait_pred
= ty
::TraitPredicate
{
210 trait_ref
: ty
::TraitRef
{
212 substs
: Substs
::identity_for_item(tcx
, def_id
),
215 // `FromEnv(Self: Trait<P1..Pn>)`
216 let from_env
= Goal
::from(DomainGoal
::FromEnv(trait_pred
.lower()));
217 // `Implemented(Self: Trait<P1..Pn>)`
218 let impl_trait
= DomainGoal
::Holds(WhereClauseAtom
::Implemented(trait_pred
));
220 // `Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)`
221 let implemented_from_env
= ProgramClause
{
223 hypotheses
: tcx
.intern_goals(&[from_env
]),
225 let clauses
= iter
::once(Clause
::ForAll(ty
::Binder
::dummy(implemented_from_env
)));
227 // Rule Implied-Bound-From-Trait
229 // For each where clause WC:
231 // forall<Self, P1..Pn> {
232 // FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn)
236 // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`, for each where clause WC
237 // FIXME: Remove the [1..] slice; this is a hack because the query
238 // predicates_of currently includes the trait itself (`Self: Trait<P1..Pn>`).
239 let where_clauses
= &tcx
.predicates_of(def_id
).predicates
;
240 let implied_bound_clauses
= where_clauses
[1..]
242 .map(|wc
| implied_bound_from_trait(tcx
, trait_pred
, wc
));
244 tcx
.mk_clauses(clauses
.chain(implied_bound_clauses
))
247 /// For a given `where_clause`, returns a clause `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`.
248 fn implied_bound_from_trait
<'a
, 'tcx
>(
249 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
250 trait_pred
: ty
::TraitPredicate
<'tcx
>,
251 where_clause
: &ty
::Predicate
<'tcx
>,
253 // `FromEnv(Self: Trait<P1..Pn>)`
254 let impl_trait
= DomainGoal
::FromEnv(WhereClauseAtom
::Implemented(trait_pred
));
256 // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`
257 Clause
::ForAll(where_clause
.lower().map_bound(|goal
| ProgramClause
{
258 goal
: goal
.into_from_env_goal(),
259 hypotheses
: tcx
.intern_goals(&[Goal
::from(impl_trait
)]),
263 fn program_clauses_for_impl
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>, def_id
: DefId
) -> Clauses
<'tcx
> {
264 if let ImplPolarity
::Negative
= tcx
.impl_polarity(def_id
) {
265 return Slice
::empty();
268 // Rule Implemented-From-Impl (see rustc guide)
270 // `impl<P0..Pn> Trait<A1..An> for A0 where WC { .. }`
274 // Implemented(A0: Trait<A1..An>) :- WC
278 let trait_ref
= tcx
.impl_trait_ref(def_id
).unwrap();
279 // `Implemented(A0: Trait<A1..An>)`
280 let trait_pred
= ty
::TraitPredicate { trait_ref }
.lower();
282 let where_clauses
= tcx
.predicates_of(def_id
).predicates
.lower();
284 // `Implemented(A0: Trait<A1..An>) :- WC`
285 let clause
= ProgramClause
{
287 hypotheses
: tcx
.mk_goals(
290 .map(|wc
| Goal
::from_poly_domain_goal(wc
, tcx
)),
293 tcx
.intern_clauses(&[Clause
::ForAll(ty
::Binder
::dummy(clause
))])
296 pub fn program_clauses_for_associated_type_value
<'a
, 'tcx
>(
297 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
300 // Rule Normalize-From-Impl (see rustc guide)
302 // ```impl<P0..Pn> Trait<A1..An> for A0
304 // type AssocType<Pn+1..Pm> where WC = T;
309 // forall<Pn+1..Pm> {
310 // Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T) :-
311 // Implemented(A0: Trait<A1..An>) && WC
316 let item
= tcx
.associated_item(item_id
);
317 debug_assert_eq
!(item
.kind
, ty
::AssociatedKind
::Type
);
318 let impl_id
= if let ty
::AssociatedItemContainer
::ImplContainer(impl_id
) = item
.container
{
323 // `A0 as Trait<A1..An>`
324 let trait_ref
= tcx
.impl_trait_ref(impl_id
).unwrap();
326 let ty
= tcx
.type_of(item_id
);
327 // `Implemented(A0: Trait<A1..An>)`
328 let trait_implemented
= ty
::Binder
::dummy(ty
::TraitPredicate { trait_ref }
.lower());
330 let item_where_clauses
= tcx
.predicates_of(item_id
).predicates
.lower();
331 // `Implemented(A0: Trait<A1..An>) && WC`
332 let mut where_clauses
= vec
![trait_implemented
];
333 where_clauses
.extend(item_where_clauses
);
334 // `<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm>`
335 let projection_ty
= ty
::ProjectionTy
::from_ref_and_name(tcx
, trait_ref
, item
.name
);
336 // `Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T)`
337 let normalize_goal
= DomainGoal
::Normalize(ty
::ProjectionPredicate { projection_ty, ty }
);
338 // `Normalize(... -> T) :- ...`
339 let clause
= ProgramClause
{
340 goal
: normalize_goal
,
341 hypotheses
: tcx
.mk_goals(
344 .map(|wc
| Goal
::from_poly_domain_goal(wc
, tcx
)),
347 tcx
.intern_clauses(&[Clause
::ForAll(ty
::Binder
::dummy(clause
))])
350 pub fn dump_program_clauses
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>) {
351 if !tcx
.features().rustc_attrs
{
355 let mut visitor
= ClauseDumper { tcx }
;
358 .visit_all_item_likes(&mut visitor
.as_deep_visitor());
361 struct ClauseDumper
<'a
, 'tcx
: 'a
> {
362 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
365 impl<'a
, 'tcx
> ClauseDumper
<'a
, 'tcx
> {
366 fn process_attrs(&mut self, node_id
: ast
::NodeId
, attrs
: &[ast
::Attribute
]) {
367 let def_id
= self.tcx
.hir
.local_def_id(node_id
);
369 let mut clauses
= None
;
371 if attr
.check_name("rustc_dump_program_clauses") {
372 clauses
= Some(self.tcx
.program_clauses_for(def_id
));
375 if attr
.check_name("rustc_dump_env_program_clauses") {
376 let param_env
= self.tcx
.param_env(def_id
);
377 clauses
= Some(self.tcx
.program_clauses_for_env(param_env
));
380 if let Some(clauses
) = clauses
{
381 let mut err
= self.tcx
383 .struct_span_err(attr
.span
, "program clause dump");
385 let mut strings
: Vec
<_
> = clauses
388 // Skip the top-level binder for a less verbose output
389 let program_clause
= match clause
{
390 Clause
::Implies(program_clause
) => program_clause
,
391 Clause
::ForAll(program_clause
) => program_clause
.skip_binder(),
393 format
!("{}", program_clause
)
399 for string
in strings
{
409 impl<'a
, 'tcx
> Visitor
<'tcx
> for ClauseDumper
<'a
, 'tcx
> {
410 fn nested_visit_map
<'this
>(&'this
mut self) -> NestedVisitorMap
<'this
, 'tcx
> {
411 NestedVisitorMap
::OnlyBodies(&self.tcx
.hir
)
414 fn visit_item(&mut self, item
: &'tcx hir
::Item
) {
415 self.process_attrs(item
.id
, &item
.attrs
);
416 intravisit
::walk_item(self, item
);
419 fn visit_trait_item(&mut self, trait_item
: &'tcx hir
::TraitItem
) {
420 self.process_attrs(trait_item
.id
, &trait_item
.attrs
);
421 intravisit
::walk_trait_item(self, trait_item
);
424 fn visit_impl_item(&mut self, impl_item
: &'tcx hir
::ImplItem
) {
425 self.process_attrs(impl_item
.id
, &impl_item
.attrs
);
426 intravisit
::walk_impl_item(self, impl_item
);
429 fn visit_struct_field(&mut self, s
: &'tcx hir
::StructField
) {
430 self.process_attrs(s
.id
, &s
.attrs
);
431 intravisit
::walk_struct_field(self, s
);