]>
Commit | Line | Data |
---|---|---|
0531ce1d XL |
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 | ||
0531ce1d XL |
11 | use rustc::hir::def_id::DefId; |
12 | use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor}; | |
83c7162d XL |
13 | use rustc::hir::map::definitions::DefPathData; |
14 | use rustc::hir::{self, ImplPolarity}; | |
15 | use rustc::traits::{Clause, Clauses, DomainGoal, Goal, PolyDomainGoal, ProgramClause, | |
16 | WhereClauseAtom}; | |
0531ce1d | 17 | use rustc::ty::subst::Substs; |
83c7162d XL |
18 | use rustc::ty::{self, Slice, TyCtxt}; |
19 | use rustc_data_structures::fx::FxHashSet; | |
20 | use std::mem; | |
0531ce1d | 21 | use syntax::ast; |
83c7162d XL |
22 | |
23 | use std::iter; | |
0531ce1d | 24 | |
94b46f34 | 25 | crate trait Lower<T> { |
0531ce1d XL |
26 | /// Lower a rustc construction (e.g. `ty::TraitPredicate`) to a chalk-like type. |
27 | fn lower(&self) -> T; | |
28 | } | |
29 | ||
83c7162d XL |
30 | impl<T, U> Lower<Vec<U>> for Vec<T> |
31 | where | |
32 | T: Lower<U>, | |
33 | { | |
0531ce1d XL |
34 | fn lower(&self) -> Vec<U> { |
35 | self.iter().map(|item| item.lower()).collect() | |
36 | } | |
37 | } | |
38 | ||
39 | impl<'tcx> Lower<WhereClauseAtom<'tcx>> for ty::TraitPredicate<'tcx> { | |
40 | fn lower(&self) -> WhereClauseAtom<'tcx> { | |
41 | WhereClauseAtom::Implemented(*self) | |
42 | } | |
43 | } | |
44 | ||
45 | impl<'tcx> Lower<WhereClauseAtom<'tcx>> for ty::ProjectionPredicate<'tcx> { | |
46 | fn lower(&self) -> WhereClauseAtom<'tcx> { | |
47 | WhereClauseAtom::ProjectionEq(*self) | |
48 | } | |
49 | } | |
50 | ||
83c7162d XL |
51 | impl<'tcx, T> Lower<DomainGoal<'tcx>> for T |
52 | where | |
53 | T: Lower<WhereClauseAtom<'tcx>>, | |
54 | { | |
0531ce1d XL |
55 | fn lower(&self) -> DomainGoal<'tcx> { |
56 | DomainGoal::Holds(self.lower()) | |
57 | } | |
58 | } | |
59 | ||
60 | impl<'tcx> Lower<DomainGoal<'tcx>> for ty::RegionOutlivesPredicate<'tcx> { | |
61 | fn lower(&self) -> DomainGoal<'tcx> { | |
62 | DomainGoal::RegionOutlives(*self) | |
63 | } | |
64 | } | |
65 | ||
66 | impl<'tcx> Lower<DomainGoal<'tcx>> for ty::TypeOutlivesPredicate<'tcx> { | |
67 | fn lower(&self) -> DomainGoal<'tcx> { | |
68 | DomainGoal::TypeOutlives(*self) | |
69 | } | |
70 | } | |
71 | ||
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 | |
83c7162d | 75 | /// example), we model them with quantified domain goals, e.g. as for the previous example: |
0531ce1d XL |
76 | /// `forall<'a> { T: Fn(&'a i32) }` which corresponds to something like |
77 | /// `Binder<Holds(Implemented(TraitPredicate))>`. | |
83c7162d XL |
78 | impl<'tcx, T> Lower<PolyDomainGoal<'tcx>> for ty::Binder<T> |
79 | where | |
80 | T: Lower<DomainGoal<'tcx>> + ty::fold::TypeFoldable<'tcx>, | |
0531ce1d | 81 | { |
83c7162d XL |
82 | fn lower(&self) -> PolyDomainGoal<'tcx> { |
83 | self.map_bound_ref(|p| p.lower()) | |
0531ce1d XL |
84 | } |
85 | } | |
86 | ||
83c7162d XL |
87 | impl<'tcx> Lower<PolyDomainGoal<'tcx>> for ty::Predicate<'tcx> { |
88 | fn lower(&self) -> PolyDomainGoal<'tcx> { | |
0531ce1d XL |
89 | use rustc::ty::Predicate::*; |
90 | ||
91 | match self { | |
92 | Trait(predicate) => predicate.lower(), | |
93 | RegionOutlives(predicate) => predicate.lower(), | |
94 | TypeOutlives(predicate) => predicate.lower(), | |
95 | Projection(predicate) => predicate.lower(), | |
83c7162d XL |
96 | WellFormed(ty) => ty::Binder::dummy(DomainGoal::WellFormedTy(*ty)), |
97 | ObjectSafe(..) | ClosureKind(..) | Subtype(..) | ConstEvaluatable(..) => { | |
98 | unimplemented!() | |
99 | } | |
0531ce1d XL |
100 | } |
101 | } | |
102 | } | |
103 | ||
83c7162d XL |
104 | /// Transforms an existing goal into a FromEnv goal. |
105 | /// | |
106 | /// Used for lowered where clauses (see rustc guide). | |
107 | trait IntoFromEnvGoal { | |
108 | fn into_from_env_goal(self) -> Self; | |
109 | } | |
0531ce1d | 110 | |
83c7162d XL |
111 | impl<'tcx> IntoFromEnvGoal for DomainGoal<'tcx> { |
112 | fn into_from_env_goal(self) -> DomainGoal<'tcx> { | |
113 | use self::DomainGoal::*; | |
114 | match self { | |
115 | Holds(wc_atom) => FromEnv(wc_atom), | |
116 | WellFormed(..) | FromEnv(..) | WellFormedTy(..) | FromEnvTy(..) | Normalize(..) | |
117 | | RegionOutlives(..) | TypeOutlives(..) => self, | |
118 | } | |
0531ce1d XL |
119 | } |
120 | } | |
121 | ||
83c7162d XL |
122 | crate fn program_clauses_for<'a, 'tcx>( |
123 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
124 | def_id: DefId, | |
125 | ) -> Clauses<'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), | |
130 | _ => Slice::empty(), | |
131 | } | |
132 | } | |
133 | ||
134 | crate fn program_clauses_for_env<'a, 'tcx>( | |
135 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
136 | param_env: ty::ParamEnv<'tcx>, | |
137 | ) -> Clauses<'tcx> { | |
138 | debug!("program_clauses_for_env(param_env={:?})", param_env); | |
139 | ||
140 | let mut last_round = FxHashSet(); | |
141 | last_round.extend( | |
142 | param_env | |
143 | .caller_bounds | |
144 | .iter() | |
145 | .flat_map(|&p| predicate_def_id(p)), | |
146 | ); | |
147 | ||
148 | let mut closure = last_round.clone(); | |
149 | let mut next_round = FxHashSet(); | |
150 | while !last_round.is_empty() { | |
151 | next_round.extend( | |
152 | last_round | |
153 | .drain() | |
154 | .flat_map(|def_id| { | |
155 | tcx.predicates_of(def_id) | |
156 | .instantiate_identity(tcx) | |
157 | .predicates | |
158 | }) | |
159 | .flat_map(|p| predicate_def_id(p)) | |
160 | .filter(|&def_id| closure.insert(def_id)), | |
161 | ); | |
162 | mem::swap(&mut next_round, &mut last_round); | |
163 | } | |
164 | ||
165 | debug!("program_clauses_for_env: closure = {:#?}", closure); | |
166 | ||
167 | return tcx.mk_clauses( | |
168 | closure | |
169 | .into_iter() | |
170 | .flat_map(|def_id| tcx.program_clauses_for(def_id).iter().cloned()), | |
171 | ); | |
172 | ||
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> { | |
178 | match predicate { | |
179 | ty::Predicate::Trait(predicate) => Some(predicate.def_id()), | |
180 | ||
181 | ty::Predicate::Projection(projection) => Some(projection.item_def_id()), | |
182 | ||
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, | |
190 | } | |
191 | } | |
192 | } | |
193 | ||
194 | fn program_clauses_for_trait<'a, 'tcx>( | |
195 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
196 | def_id: DefId, | |
197 | ) -> Clauses<'tcx> { | |
0531ce1d | 198 | // `trait Trait<P1..Pn> where WC { .. } // P0 == Self` |
83c7162d XL |
199 | |
200 | // Rule Implemented-From-Env (see rustc guide) | |
0531ce1d XL |
201 | // |
202 | // ``` | |
203 | // forall<Self, P1..Pn> { | |
204 | // Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>) | |
205 | // } | |
206 | // ``` | |
207 | ||
208 | // `Self: Trait<P1..Pn>` | |
209 | let trait_pred = ty::TraitPredicate { | |
210 | trait_ref: ty::TraitRef { | |
211 | def_id, | |
83c7162d XL |
212 | substs: Substs::identity_for_item(tcx, def_id), |
213 | }, | |
0531ce1d XL |
214 | }; |
215 | // `FromEnv(Self: Trait<P1..Pn>)` | |
83c7162d | 216 | let from_env = Goal::from(DomainGoal::FromEnv(trait_pred.lower())); |
0531ce1d XL |
217 | // `Implemented(Self: Trait<P1..Pn>)` |
218 | let impl_trait = DomainGoal::Holds(WhereClauseAtom::Implemented(trait_pred)); | |
219 | ||
220 | // `Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)` | |
83c7162d XL |
221 | let implemented_from_env = ProgramClause { |
222 | goal: impl_trait, | |
94b46f34 | 223 | hypotheses: tcx.intern_goals(&[from_env]), |
83c7162d XL |
224 | }; |
225 | let clauses = iter::once(Clause::ForAll(ty::Binder::dummy(implemented_from_env))); | |
226 | ||
227 | // Rule Implied-Bound-From-Trait | |
228 | // | |
229 | // For each where clause WC: | |
230 | // ``` | |
231 | // forall<Self, P1..Pn> { | |
232 | // FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn) | |
233 | // } | |
234 | // ``` | |
235 | ||
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..] | |
241 | .into_iter() | |
242 | .map(|wc| implied_bound_from_trait(tcx, trait_pred, wc)); | |
243 | ||
244 | tcx.mk_clauses(clauses.chain(implied_bound_clauses)) | |
0531ce1d XL |
245 | } |
246 | ||
83c7162d XL |
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>, | |
252 | ) -> Clause<'tcx> { | |
253 | // `FromEnv(Self: Trait<P1..Pn>)` | |
254 | let impl_trait = DomainGoal::FromEnv(WhereClauseAtom::Implemented(trait_pred)); | |
255 | ||
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(), | |
94b46f34 | 259 | hypotheses: tcx.intern_goals(&[Goal::from(impl_trait)]), |
83c7162d XL |
260 | })) |
261 | } | |
262 | ||
263 | fn program_clauses_for_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> Clauses<'tcx> { | |
0531ce1d | 264 | if let ImplPolarity::Negative = tcx.impl_polarity(def_id) { |
83c7162d | 265 | return Slice::empty(); |
0531ce1d XL |
266 | } |
267 | ||
268 | // Rule Implemented-From-Impl (see rustc guide) | |
269 | // | |
270 | // `impl<P0..Pn> Trait<A1..An> for A0 where WC { .. }` | |
271 | // | |
272 | // ``` | |
273 | // forall<P0..Pn> { | |
274 | // Implemented(A0: Trait<A1..An>) :- WC | |
275 | // } | |
276 | // ``` | |
277 | ||
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(); | |
83c7162d | 281 | // `WC` |
0531ce1d XL |
282 | let where_clauses = tcx.predicates_of(def_id).predicates.lower(); |
283 | ||
83c7162d XL |
284 | // `Implemented(A0: Trait<A1..An>) :- WC` |
285 | let clause = ProgramClause { | |
286 | goal: trait_pred, | |
287 | hypotheses: tcx.mk_goals( | |
288 | where_clauses | |
289 | .into_iter() | |
290 | .map(|wc| Goal::from_poly_domain_goal(wc, tcx)), | |
291 | ), | |
292 | }; | |
94b46f34 | 293 | tcx.intern_clauses(&[Clause::ForAll(ty::Binder::dummy(clause))]) |
83c7162d XL |
294 | } |
295 | ||
296 | pub fn program_clauses_for_associated_type_value<'a, 'tcx>( | |
297 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
298 | item_id: DefId, | |
299 | ) -> Clauses<'tcx> { | |
300 | // Rule Normalize-From-Impl (see rustc guide) | |
301 | // | |
302 | // ```impl<P0..Pn> Trait<A1..An> for A0 | |
303 | // { | |
304 | // type AssocType<Pn+1..Pm> where WC = T; | |
305 | // }``` | |
306 | // | |
307 | // ``` | |
308 | // forall<P0..Pm> { | |
309 | // forall<Pn+1..Pm> { | |
310 | // Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T) :- | |
311 | // Implemented(A0: Trait<A1..An>) && WC | |
312 | // } | |
313 | // } | |
314 | // ``` | |
315 | ||
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 { | |
319 | impl_id | |
320 | } else { | |
321 | bug!() | |
322 | }; | |
323 | // `A0 as Trait<A1..An>` | |
324 | let trait_ref = tcx.impl_trait_ref(impl_id).unwrap(); | |
325 | // `T` | |
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()); | |
329 | // `WC` | |
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( | |
342 | where_clauses | |
343 | .into_iter() | |
344 | .map(|wc| Goal::from_poly_domain_goal(wc, tcx)), | |
345 | ), | |
346 | }; | |
94b46f34 | 347 | tcx.intern_clauses(&[Clause::ForAll(ty::Binder::dummy(clause))]) |
0531ce1d XL |
348 | } |
349 | ||
350 | pub fn dump_program_clauses<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { | |
351 | if !tcx.features().rustc_attrs { | |
352 | return; | |
353 | } | |
354 | ||
355 | let mut visitor = ClauseDumper { tcx }; | |
83c7162d XL |
356 | tcx.hir |
357 | .krate() | |
358 | .visit_all_item_likes(&mut visitor.as_deep_visitor()); | |
0531ce1d XL |
359 | } |
360 | ||
361 | struct ClauseDumper<'a, 'tcx: 'a> { | |
362 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
363 | } | |
364 | ||
83c7162d | 365 | impl<'a, 'tcx> ClauseDumper<'a, 'tcx> { |
0531ce1d XL |
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); | |
368 | for attr in attrs { | |
83c7162d XL |
369 | let mut clauses = None; |
370 | ||
0531ce1d | 371 | if attr.check_name("rustc_dump_program_clauses") { |
83c7162d XL |
372 | clauses = Some(self.tcx.program_clauses_for(def_id)); |
373 | } | |
374 | ||
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)); | |
378 | } | |
379 | ||
380 | if let Some(clauses) = clauses { | |
381 | let mut err = self.tcx | |
382 | .sess | |
383 | .struct_span_err(attr.span, "program clause dump"); | |
384 | ||
385 | let mut strings: Vec<_> = clauses | |
386 | .iter() | |
387 | .map(|clause| { | |
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(), | |
392 | }; | |
393 | format!("{}", program_clause) | |
394 | }) | |
395 | .collect(); | |
396 | ||
397 | strings.sort(); | |
398 | ||
399 | for string in strings { | |
400 | err.note(&string); | |
0531ce1d | 401 | } |
83c7162d XL |
402 | |
403 | err.emit(); | |
0531ce1d XL |
404 | } |
405 | } | |
406 | } | |
407 | } | |
408 | ||
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) | |
412 | } | |
413 | ||
414 | fn visit_item(&mut self, item: &'tcx hir::Item) { | |
415 | self.process_attrs(item.id, &item.attrs); | |
416 | intravisit::walk_item(self, item); | |
417 | } | |
418 | ||
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); | |
422 | } | |
423 | ||
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); | |
427 | } | |
428 | ||
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); | |
432 | } | |
433 | } |