]>
Commit | Line | Data |
---|---|---|
dfeec247 XL |
1 | use rustc_data_structures::fx::FxHashSet; |
2 | use rustc_hir as hir; | |
3dfed10e | 3 | use rustc_hir::lang_items::LangItem; |
ba9703b0 XL |
4 | use rustc_middle::ty::{self, Region, RegionVid, TypeFoldable}; |
5 | use rustc_trait_selection::traits::auto_trait::{self, AutoTraitResult}; | |
60c5eb7d | 6 | |
0531ce1d | 7 | use std::fmt::Debug; |
b7449926 | 8 | |
0531ce1d XL |
9 | use super::*; |
10 | ||
60c5eb7d XL |
11 | #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)] |
12 | enum RegionTarget<'tcx> { | |
13 | Region(Region<'tcx>), | |
dfeec247 | 14 | RegionVid(RegionVid), |
60c5eb7d XL |
15 | } |
16 | ||
17 | #[derive(Default, Debug, Clone)] | |
18 | struct RegionDeps<'tcx> { | |
19 | larger: FxHashSet<RegionTarget<'tcx>>, | |
dfeec247 | 20 | smaller: FxHashSet<RegionTarget<'tcx>>, |
60c5eb7d XL |
21 | } |
22 | ||
fc512014 | 23 | crate struct AutoTraitFinder<'a, 'tcx> { |
6a06907d | 24 | crate cx: &'a mut core::DocContext<'tcx>, |
0531ce1d XL |
25 | } |
26 | ||
532ac7d7 | 27 | impl<'a, 'tcx> AutoTraitFinder<'a, 'tcx> { |
6a06907d XL |
28 | crate fn new(cx: &'a mut core::DocContext<'tcx>) -> Self { |
29 | AutoTraitFinder { cx } | |
94b46f34 XL |
30 | } |
31 | ||
6a06907d XL |
32 | fn generate_for_trait( |
33 | &mut self, | |
34 | ty: Ty<'tcx>, | |
35 | trait_def_id: DefId, | |
36 | param_env: ty::ParamEnv<'tcx>, | |
37 | item_def_id: DefId, | |
38 | f: &auto_trait::AutoTraitFinder<'tcx>, | |
39 | // If this is set, show only negative trait implementations, not positive ones. | |
40 | discard_positive_impl: bool, | |
41 | ) -> Option<Item> { | |
42 | let tcx = self.cx.tcx; | |
43 | let trait_ref = ty::TraitRef { def_id: trait_def_id, substs: tcx.mk_substs_trait(ty, &[]) }; | |
44 | if !self.cx.generated_synthetics.insert((ty, trait_def_id)) { | |
45 | debug!("get_auto_trait_impl_for({:?}): already generated, aborting", trait_ref); | |
46 | return None; | |
47 | } | |
48663c56 | 48 | |
6a06907d XL |
49 | let result = f.find_auto_trait_generics(ty, param_env, trait_def_id, |info| { |
50 | let region_data = info.region_data; | |
51 | ||
52 | let names_map = tcx | |
53 | .generics_of(item_def_id) | |
54 | .params | |
55 | .iter() | |
56 | .filter_map(|param| match param.kind { | |
57 | ty::GenericParamDefKind::Lifetime => Some(param.name), | |
58 | _ => None, | |
59 | }) | |
60 | .map(|name| (name, Lifetime(name))) | |
61 | .collect(); | |
62 | let lifetime_predicates = Self::handle_lifetimes(®ion_data, &names_map); | |
63 | let new_generics = self.param_env_to_generics( | |
64 | item_def_id, | |
65 | info.full_user_env, | |
66 | lifetime_predicates, | |
67 | info.vid_to_region, | |
68 | ); | |
69 | ||
70 | debug!( | |
71 | "find_auto_trait_generics(item_def_id={:?}, trait_def_id={:?}): \ | |
72 | finished with {:?}", | |
73 | item_def_id, trait_def_id, new_generics | |
74 | ); | |
75 | ||
76 | new_generics | |
77 | }); | |
78 | ||
79 | let negative_polarity; | |
80 | let new_generics = match result { | |
81 | AutoTraitResult::PositiveImpl(new_generics) => { | |
82 | negative_polarity = false; | |
83 | if discard_positive_impl { | |
dfeec247 XL |
84 | return None; |
85 | } | |
6a06907d XL |
86 | new_generics |
87 | } | |
88 | AutoTraitResult::NegativeImpl => { | |
89 | negative_polarity = true; | |
90 | ||
91 | // For negative impls, we use the generic params, but *not* the predicates, | |
92 | // from the original type. Otherwise, the displayed impl appears to be a | |
93 | // conditional negative impl, when it's really unconditional. | |
94 | // | |
95 | // For example, consider the struct Foo<T: Copy>(*mut T). Using | |
96 | // the original predicates in our impl would cause us to generate | |
97 | // `impl !Send for Foo<T: Copy>`, which makes it appear that Foo | |
98 | // implements Send where T is not copy. | |
99 | // | |
100 | // Instead, we generate `impl !Send for Foo<T>`, which better | |
101 | // expresses the fact that `Foo<T>` never implements `Send`, | |
102 | // regardless of the choice of `T`. | |
103 | let params = (tcx.generics_of(item_def_id), ty::GenericPredicates::default()) | |
104 | .clean(self.cx) | |
105 | .params; | |
106 | ||
107 | Generics { params, where_predicates: Vec::new() } | |
108 | } | |
109 | AutoTraitResult::ExplicitImpl => return None, | |
110 | }; | |
0531ce1d | 111 | |
6a06907d | 112 | Some(Item { |
6a06907d XL |
113 | name: None, |
114 | attrs: Default::default(), | |
115 | visibility: Inherited, | |
136023e0 | 116 | def_id: ItemId::Auto { trait_: trait_def_id, for_: item_def_id }, |
6a06907d | 117 | kind: box ImplItem(Impl { |
cdc7bbd5 | 118 | span: Span::dummy(), |
6a06907d XL |
119 | unsafety: hir::Unsafety::Normal, |
120 | generics: new_generics, | |
6a06907d XL |
121 | trait_: Some(trait_ref.clean(self.cx).get_trait_type().unwrap()), |
122 | for_: ty.clean(self.cx), | |
123 | items: Vec::new(), | |
124 | negative_polarity, | |
125 | synthetic: true, | |
126 | blanket_impl: None, | |
127 | }), | |
cdc7bbd5 | 128 | cfg: None, |
6a06907d XL |
129 | }) |
130 | } | |
131 | ||
132 | crate fn get_auto_trait_impls(&mut self, item_def_id: DefId) -> Vec<Item> { | |
133 | let tcx = self.cx.tcx; | |
134 | let param_env = tcx.param_env(item_def_id); | |
135 | let ty = tcx.type_of(item_def_id); | |
136 | let f = auto_trait::AutoTraitFinder::new(tcx); | |
137 | ||
138 | debug!("get_auto_trait_impls({:?})", ty); | |
139 | let auto_traits: Vec<_> = self.cx.auto_traits.iter().cloned().collect(); | |
140 | let mut auto_traits: Vec<Item> = auto_traits | |
141 | .into_iter() | |
142 | .filter_map(|trait_def_id| { | |
143 | self.generate_for_trait(ty, trait_def_id, param_env, item_def_id, &f, false) | |
48663c56 | 144 | }) |
6a06907d XL |
145 | .collect(); |
146 | // We are only interested in case the type *doesn't* implement the Sized trait. | |
147 | if !ty.is_sized(tcx.at(rustc_span::DUMMY_SP), param_env) { | |
148 | // In case `#![no_core]` is used, `sized_trait` returns nothing. | |
149 | if let Some(item) = tcx.lang_items().sized_trait().and_then(|sized_trait_did| { | |
150 | self.generate_for_trait(ty, sized_trait_did, param_env, item_def_id, &f, true) | |
151 | }) { | |
152 | auto_traits.push(item); | |
153 | } | |
154 | } | |
155 | auto_traits | |
0531ce1d XL |
156 | } |
157 | ||
6a06907d XL |
158 | fn get_lifetime(region: Region<'_>, names_map: &FxHashMap<Symbol, Lifetime>) -> Lifetime { |
159 | region_name(region) | |
0531ce1d XL |
160 | .map(|name| { |
161 | names_map.get(&name).unwrap_or_else(|| { | |
fc512014 | 162 | panic!("Missing lifetime with name {:?} for {:?}", name.as_str(), region) |
0531ce1d XL |
163 | }) |
164 | }) | |
165 | .unwrap_or(&Lifetime::statik()) | |
166 | .clone() | |
167 | } | |
168 | ||
0531ce1d XL |
169 | // This method calculates two things: Lifetime constraints of the form 'a: 'b, |
170 | // and region constraints of the form ReVar: 'a | |
171 | // | |
172 | // This is essentially a simplified version of lexical_region_resolve. However, | |
173 | // handle_lifetimes determines what *needs be* true in order for an impl to hold. | |
174 | // lexical_region_resolve, along with much of the rest of the compiler, is concerned | |
175 | // with determining if a given set up constraints/predicates *are* met, given some | |
0731742a | 176 | // starting conditions (e.g., user-provided code). For this reason, it's easier |
0531ce1d XL |
177 | // to perform the calculations we need on our own, rather than trying to make |
178 | // existing inference/solver code do what we want. | |
179 | fn handle_lifetimes<'cx>( | |
0531ce1d | 180 | regions: &RegionConstraintData<'cx>, |
fc512014 | 181 | names_map: &FxHashMap<Symbol, Lifetime>, |
0531ce1d XL |
182 | ) -> Vec<WherePredicate> { |
183 | // Our goal is to 'flatten' the list of constraints by eliminating | |
184 | // all intermediate RegionVids. At the end, all constraints should | |
185 | // be between Regions (aka region variables). This gives us the information | |
186 | // we need to create the Generics. | |
0bf4aa26 | 187 | let mut finished: FxHashMap<_, Vec<_>> = Default::default(); |
0531ce1d | 188 | |
9fa01778 | 189 | let mut vid_map: FxHashMap<RegionTarget<'_>, RegionDeps<'_>> = Default::default(); |
0531ce1d XL |
190 | |
191 | // Flattening is done in two parts. First, we insert all of the constraints | |
192 | // into a map. Each RegionTarget (either a RegionVid or a Region) maps | |
193 | // to its smaller and larger regions. Note that 'larger' regions correspond | |
0731742a | 194 | // to sub-regions in Rust code (e.g., in 'a: 'b, 'a is the larger region). |
0531ce1d XL |
195 | for constraint in regions.constraints.keys() { |
196 | match constraint { | |
197 | &Constraint::VarSubVar(r1, r2) => { | |
198 | { | |
dfeec247 | 199 | let deps1 = vid_map.entry(RegionTarget::RegionVid(r1)).or_default(); |
0531ce1d XL |
200 | deps1.larger.insert(RegionTarget::RegionVid(r2)); |
201 | } | |
202 | ||
dfeec247 | 203 | let deps2 = vid_map.entry(RegionTarget::RegionVid(r2)).or_default(); |
0531ce1d XL |
204 | deps2.smaller.insert(RegionTarget::RegionVid(r1)); |
205 | } | |
206 | &Constraint::RegSubVar(region, vid) => { | |
dfeec247 | 207 | let deps = vid_map.entry(RegionTarget::RegionVid(vid)).or_default(); |
0531ce1d XL |
208 | deps.smaller.insert(RegionTarget::Region(region)); |
209 | } | |
210 | &Constraint::VarSubReg(vid, region) => { | |
dfeec247 | 211 | let deps = vid_map.entry(RegionTarget::RegionVid(vid)).or_default(); |
0531ce1d XL |
212 | deps.larger.insert(RegionTarget::Region(region)); |
213 | } | |
214 | &Constraint::RegSubReg(r1, r2) => { | |
215 | // The constraint is already in the form that we want, so we're done with it | |
216 | // Desired order is 'larger, smaller', so flip then | |
6a06907d | 217 | if region_name(r1) != region_name(r2) { |
0531ce1d | 218 | finished |
6a06907d | 219 | .entry(region_name(r2).expect("no region_name found")) |
b7449926 | 220 | .or_default() |
0531ce1d XL |
221 | .push(r1); |
222 | } | |
223 | } | |
224 | } | |
225 | } | |
226 | ||
227 | // Here, we 'flatten' the map one element at a time. | |
228 | // All of the element's sub and super regions are connected | |
229 | // to each other. For example, if we have a graph that looks like this: | |
230 | // | |
231 | // (A, B) - C - (D, E) | |
232 | // Where (A, B) are subregions, and (D,E) are super-regions | |
233 | // | |
234 | // then after deleting 'C', the graph will look like this: | |
235 | // ... - A - (D, E ...) | |
236 | // ... - B - (D, E, ...) | |
237 | // (A, B, ...) - D - ... | |
238 | // (A, B, ...) - E - ... | |
239 | // | |
240 | // where '...' signifies the existing sub and super regions of an entry | |
241 | // When two adjacent ty::Regions are encountered, we've computed a final | |
242 | // constraint, and add it to our list. Since we make sure to never re-add | |
243 | // deleted items, this process will always finish. | |
244 | while !vid_map.is_empty() { | |
dfeec247 | 245 | let target = *vid_map.keys().next().expect("Keys somehow empty"); |
0531ce1d XL |
246 | let deps = vid_map.remove(&target).expect("Entry somehow missing"); |
247 | ||
248 | for smaller in deps.smaller.iter() { | |
249 | for larger in deps.larger.iter() { | |
250 | match (smaller, larger) { | |
251 | (&RegionTarget::Region(r1), &RegionTarget::Region(r2)) => { | |
6a06907d | 252 | if region_name(r1) != region_name(r2) { |
0531ce1d | 253 | finished |
6a06907d | 254 | .entry(region_name(r2).expect("no region name found")) |
b7449926 | 255 | .or_default() |
0531ce1d XL |
256 | .push(r1) // Larger, smaller |
257 | } | |
258 | } | |
259 | (&RegionTarget::RegionVid(_), &RegionTarget::Region(_)) => { | |
260 | if let Entry::Occupied(v) = vid_map.entry(*smaller) { | |
261 | let smaller_deps = v.into_mut(); | |
262 | smaller_deps.larger.insert(*larger); | |
263 | smaller_deps.larger.remove(&target); | |
264 | } | |
265 | } | |
266 | (&RegionTarget::Region(_), &RegionTarget::RegionVid(_)) => { | |
267 | if let Entry::Occupied(v) = vid_map.entry(*larger) { | |
268 | let deps = v.into_mut(); | |
269 | deps.smaller.insert(*smaller); | |
270 | deps.smaller.remove(&target); | |
271 | } | |
272 | } | |
273 | (&RegionTarget::RegionVid(_), &RegionTarget::RegionVid(_)) => { | |
274 | if let Entry::Occupied(v) = vid_map.entry(*smaller) { | |
275 | let smaller_deps = v.into_mut(); | |
276 | smaller_deps.larger.insert(*larger); | |
277 | smaller_deps.larger.remove(&target); | |
278 | } | |
279 | ||
280 | if let Entry::Occupied(v) = vid_map.entry(*larger) { | |
281 | let larger_deps = v.into_mut(); | |
282 | larger_deps.smaller.insert(*smaller); | |
283 | larger_deps.smaller.remove(&target); | |
284 | } | |
285 | } | |
286 | } | |
287 | } | |
288 | } | |
289 | } | |
290 | ||
291 | let lifetime_predicates = names_map | |
292 | .iter() | |
293 | .flat_map(|(name, lifetime)| { | |
294 | let empty = Vec::new(); | |
dfeec247 XL |
295 | let bounds: FxHashSet<GenericBound> = finished |
296 | .get(name) | |
297 | .unwrap_or(&empty) | |
298 | .iter() | |
6a06907d | 299 | .map(|region| GenericBound::Outlives(Self::get_lifetime(region, names_map))) |
0531ce1d XL |
300 | .collect(); |
301 | ||
302 | if bounds.is_empty() { | |
303 | return None; | |
304 | } | |
305 | Some(WherePredicate::RegionPredicate { | |
306 | lifetime: lifetime.clone(), | |
307 | bounds: bounds.into_iter().collect(), | |
308 | }) | |
309 | }) | |
310 | .collect(); | |
311 | ||
312 | lifetime_predicates | |
313 | } | |
314 | ||
6a06907d | 315 | fn extract_for_generics(&self, pred: ty::Predicate<'tcx>) -> FxHashSet<GenericParamDef> { |
5869c6ff | 316 | let bound_predicate = pred.kind(); |
6a06907d | 317 | let tcx = self.cx.tcx; |
29967ef6 | 318 | let regions = match bound_predicate.skip_binder() { |
5869c6ff | 319 | ty::PredicateKind::Trait(poly_trait_pred, _) => { |
29967ef6 | 320 | tcx.collect_referenced_late_bound_regions(&bound_predicate.rebind(poly_trait_pred)) |
ba9703b0 | 321 | } |
5869c6ff | 322 | ty::PredicateKind::Projection(poly_proj_pred) => { |
29967ef6 | 323 | tcx.collect_referenced_late_bound_regions(&bound_predicate.rebind(poly_proj_pred)) |
ba9703b0 XL |
324 | } |
325 | _ => return FxHashSet::default(), | |
326 | }; | |
327 | ||
328 | regions | |
329 | .into_iter() | |
330 | .filter_map(|br| { | |
331 | match br { | |
332 | // We only care about named late bound regions, as we need to add them | |
333 | // to the 'for<>' section | |
fc512014 XL |
334 | ty::BrNamed(_, name) => { |
335 | Some(GenericParamDef { name, kind: GenericParamDefKind::Lifetime }) | |
336 | } | |
ba9703b0 XL |
337 | _ => None, |
338 | } | |
0531ce1d XL |
339 | }) |
340 | .collect() | |
341 | } | |
342 | ||
dc9dc135 | 343 | fn make_final_bounds( |
0531ce1d | 344 | &self, |
8faf50e0 | 345 | ty_to_bounds: FxHashMap<Type, FxHashSet<GenericBound>>, |
0531ce1d | 346 | ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)>, |
8faf50e0 | 347 | lifetime_to_bounds: FxHashMap<Lifetime, FxHashSet<GenericBound>>, |
0531ce1d XL |
348 | ) -> Vec<WherePredicate> { |
349 | ty_to_bounds | |
350 | .into_iter() | |
351 | .flat_map(|(ty, mut bounds)| { | |
352 | if let Some(data) = ty_to_fn.get(&ty) { | |
353 | let (poly_trait, output) = | |
b7449926 | 354 | (data.0.as_ref().expect("as_ref failed").clone(), data.1.as_ref().cloned()); |
5869c6ff | 355 | let new_ty = match poly_trait.trait_ { |
136023e0 | 356 | Type::ResolvedPath { ref path, ref did, ref is_generic } => { |
0531ce1d | 357 | let mut new_path = path.clone(); |
dfeec247 XL |
358 | let last_segment = |
359 | new_path.segments.pop().expect("segments were empty"); | |
0531ce1d | 360 | |
8faf50e0 | 361 | let (old_input, old_output) = match last_segment.args { |
532ac7d7 | 362 | GenericArgs::AngleBracketed { args, .. } => { |
dfeec247 XL |
363 | let types = args |
364 | .iter() | |
365 | .filter_map(|arg| match arg { | |
366 | GenericArg::Type(ty) => Some(ty.clone()), | |
367 | _ => None, | |
368 | }) | |
369 | .collect(); | |
532ac7d7 XL |
370 | (types, None) |
371 | } | |
8faf50e0 | 372 | GenericArgs::Parenthesized { inputs, output, .. } => { |
0531ce1d XL |
373 | (inputs, output) |
374 | } | |
375 | }; | |
376 | ||
377 | if old_output.is_some() && old_output != output { | |
378 | panic!( | |
379 | "Output mismatch for {:?} {:?} {:?}", | |
380 | ty, old_output, data.1 | |
381 | ); | |
382 | } | |
383 | ||
dfeec247 XL |
384 | let new_params = |
385 | GenericArgs::Parenthesized { inputs: old_input, output }; | |
0531ce1d | 386 | |
dfeec247 XL |
387 | new_path |
388 | .segments | |
389 | .push(PathSegment { name: last_segment.name, args: new_params }); | |
0531ce1d XL |
390 | |
391 | Type::ResolvedPath { | |
392 | path: new_path, | |
dfeec247 | 393 | did: *did, |
0531ce1d XL |
394 | is_generic: *is_generic, |
395 | } | |
396 | } | |
397 | _ => panic!("Unexpected data: {:?}, {:?}", ty, data), | |
398 | }; | |
8faf50e0 | 399 | bounds.insert(GenericBound::TraitBound( |
dfeec247 | 400 | PolyTrait { trait_: new_ty, generic_params: poly_trait.generic_params }, |
0531ce1d XL |
401 | hir::TraitBoundModifier::None, |
402 | )); | |
403 | } | |
404 | if bounds.is_empty() { | |
405 | return None; | |
406 | } | |
407 | ||
408 | let mut bounds_vec = bounds.into_iter().collect(); | |
409 | self.sort_where_bounds(&mut bounds_vec); | |
410 | ||
136023e0 XL |
411 | Some(WherePredicate::BoundPredicate { |
412 | ty, | |
413 | bounds: bounds_vec, | |
414 | bound_params: Vec::new(), | |
415 | }) | |
0531ce1d XL |
416 | }) |
417 | .chain( | |
dfeec247 XL |
418 | lifetime_to_bounds.into_iter().filter(|&(_, ref bounds)| !bounds.is_empty()).map( |
419 | |(lifetime, bounds)| { | |
0531ce1d | 420 | let mut bounds_vec = bounds.into_iter().collect(); |
8faf50e0 | 421 | self.sort_where_bounds(&mut bounds_vec); |
dfeec247 XL |
422 | WherePredicate::RegionPredicate { lifetime, bounds: bounds_vec } |
423 | }, | |
424 | ), | |
0531ce1d XL |
425 | ) |
426 | .collect() | |
427 | } | |
428 | ||
429 | // Converts the calculated ParamEnv and lifetime information to a clean::Generics, suitable for | |
3dfed10e | 430 | // display on the docs page. Cleaning the Predicates produces sub-optimal `WherePredicate`s, |
0531ce1d XL |
431 | // so we fix them up: |
432 | // | |
0731742a | 433 | // * Multiple bounds for the same type are coalesced into one: e.g., 'T: Copy', 'T: Debug' |
0531ce1d XL |
434 | // becomes 'T: Copy + Debug' |
435 | // * Fn bounds are handled specially - instead of leaving it as 'T: Fn(), <T as Fn::Output> = | |
436 | // K', we use the dedicated syntax 'T: Fn() -> K' | |
3dfed10e | 437 | // * We explicitly add a '?Sized' bound if we didn't find any 'Sized' predicates for a type |
dc9dc135 | 438 | fn param_env_to_generics( |
6a06907d XL |
439 | &mut self, |
440 | item_def_id: DefId, | |
dc9dc135 | 441 | param_env: ty::ParamEnv<'tcx>, |
0531ce1d | 442 | mut existing_predicates: Vec<WherePredicate>, |
dc9dc135 | 443 | vid_to_region: FxHashMap<ty::RegionVid, ty::Region<'tcx>>, |
0531ce1d XL |
444 | ) -> Generics { |
445 | debug!( | |
6a06907d | 446 | "param_env_to_generics(item_def_id={:?}, param_env={:?}, \ |
0531ce1d | 447 | existing_predicates={:?})", |
6a06907d | 448 | item_def_id, param_env, existing_predicates |
0531ce1d XL |
449 | ); |
450 | ||
6a06907d XL |
451 | let tcx = self.cx.tcx; |
452 | ||
0731742a XL |
453 | // The `Sized` trait must be handled specially, since we only display it when |
454 | // it is *not* required (i.e., '?Sized') | |
6a06907d | 455 | let sized_trait = tcx.require_lang_item(LangItem::Sized, None); |
0531ce1d | 456 | |
dfeec247 | 457 | let mut replacer = RegionReplacer { vid_to_region: &vid_to_region, tcx }; |
0531ce1d | 458 | |
6a06907d | 459 | let orig_bounds: FxHashSet<_> = tcx.param_env(item_def_id).caller_bounds().iter().collect(); |
0531ce1d | 460 | let clean_where_predicates = param_env |
f035d41b | 461 | .caller_bounds() |
0531ce1d XL |
462 | .iter() |
463 | .filter(|p| { | |
dfeec247 | 464 | !orig_bounds.contains(p) |
5869c6ff XL |
465 | || match p.kind().skip_binder() { |
466 | ty::PredicateKind::Trait(pred, _) => pred.def_id() == sized_trait, | |
dfeec247 XL |
467 | _ => false, |
468 | } | |
0531ce1d | 469 | }) |
6a06907d | 470 | .map(|p| p.fold_with(&mut replacer)); |
0531ce1d | 471 | |
dfeec247 | 472 | let mut generic_params = |
6a06907d | 473 | (tcx.generics_of(item_def_id), tcx.explicit_predicates_of(item_def_id)) |
dfeec247 XL |
474 | .clean(self.cx) |
475 | .params; | |
0531ce1d | 476 | |
6a06907d | 477 | debug!("param_env_to_generics({:?}): generic_params={:?}", item_def_id, generic_params); |
3dfed10e | 478 | |
0bf4aa26 XL |
479 | let mut has_sized = FxHashSet::default(); |
480 | let mut ty_to_bounds: FxHashMap<_, FxHashSet<_>> = Default::default(); | |
481 | let mut lifetime_to_bounds: FxHashMap<_, FxHashSet<_>> = Default::default(); | |
482 | let mut ty_to_traits: FxHashMap<Type, FxHashSet<Type>> = Default::default(); | |
0531ce1d | 483 | |
0bf4aa26 | 484 | let mut ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)> = Default::default(); |
0531ce1d | 485 | |
6a06907d XL |
486 | for p in clean_where_predicates { |
487 | let (orig_p, p) = (p, p.clean(self.cx)); | |
9fa01778 XL |
488 | if p.is_none() { |
489 | continue; | |
490 | } | |
491 | let p = p.unwrap(); | |
0531ce1d | 492 | match p { |
136023e0 | 493 | WherePredicate::BoundPredicate { ty, mut bounds, .. } => { |
0531ce1d XL |
494 | // Writing a projection trait bound of the form |
495 | // <T as Trait>::Name : ?Sized | |
496 | // is illegal, because ?Sized bounds can only | |
74b04a01 | 497 | // be written in the (here, nonexistent) definition |
0531ce1d XL |
498 | // of the type. |
499 | // Therefore, we make sure that we never add a ?Sized | |
500 | // bound for projections | |
ba9703b0 XL |
501 | if let Type::QPath { .. } = ty { |
502 | has_sized.insert(ty.clone()); | |
0531ce1d XL |
503 | } |
504 | ||
505 | if bounds.is_empty() { | |
506 | continue; | |
507 | } | |
508 | ||
6a06907d | 509 | let mut for_generics = self.extract_for_generics(orig_p); |
0531ce1d XL |
510 | |
511 | assert!(bounds.len() == 1); | |
b7449926 | 512 | let mut b = bounds.pop().expect("bounds were empty"); |
0531ce1d XL |
513 | |
514 | if b.is_sized_bound(self.cx) { | |
515 | has_sized.insert(ty.clone()); | |
dfeec247 XL |
516 | } else if !b |
517 | .get_trait_type() | |
0531ce1d XL |
518 | .and_then(|t| { |
519 | ty_to_traits | |
520 | .get(&ty) | |
521 | .map(|bounds| bounds.contains(&strip_type(t.clone()))) | |
522 | }) | |
523 | .unwrap_or(false) | |
524 | { | |
525 | // If we've already added a projection bound for the same type, don't add | |
526 | // this, as it would be a duplicate | |
527 | ||
528 | // Handle any 'Fn/FnOnce/FnMut' bounds specially, | |
529 | // as we want to combine them with any 'Output' qpaths | |
530 | // later | |
531 | ||
532 | let is_fn = match &mut b { | |
8faf50e0 | 533 | &mut GenericBound::TraitBound(ref mut p, _) => { |
0531ce1d | 534 | // Insert regions into the for_generics hash map first, to ensure |
0731742a | 535 | // that we don't end up with duplicate bounds (e.g., for<'b, 'b>) |
0531ce1d XL |
536 | for_generics.extend(p.generic_params.clone()); |
537 | p.generic_params = for_generics.into_iter().collect(); | |
6a06907d | 538 | self.is_fn_ty(&p.trait_) |
0531ce1d XL |
539 | } |
540 | _ => false, | |
541 | }; | |
542 | ||
b7449926 | 543 | let poly_trait = b.get_poly_trait().expect("Cannot get poly trait"); |
0531ce1d XL |
544 | |
545 | if is_fn { | |
546 | ty_to_fn | |
547 | .entry(ty.clone()) | |
548 | .and_modify(|e| *e = (Some(poly_trait.clone()), e.1.clone())) | |
549 | .or_insert(((Some(poly_trait.clone())), None)); | |
550 | ||
dfeec247 | 551 | ty_to_bounds.entry(ty.clone()).or_default(); |
0531ce1d | 552 | } else { |
dfeec247 | 553 | ty_to_bounds.entry(ty.clone()).or_default().insert(b.clone()); |
0531ce1d XL |
554 | } |
555 | } | |
556 | } | |
557 | WherePredicate::RegionPredicate { lifetime, bounds } => { | |
dfeec247 | 558 | lifetime_to_bounds.entry(lifetime).or_default().extend(bounds); |
0531ce1d XL |
559 | } |
560 | WherePredicate::EqPredicate { lhs, rhs } => { | |
dfeec247 | 561 | match lhs { |
17df50a5 | 562 | Type::QPath { name: left_name, ref self_type, ref trait_, .. } => { |
0531ce1d XL |
563 | let ty = &*self_type; |
564 | match **trait_ { | |
565 | Type::ResolvedPath { | |
566 | path: ref trait_path, | |
0531ce1d XL |
567 | ref did, |
568 | ref is_generic, | |
569 | } => { | |
570 | let mut new_trait_path = trait_path.clone(); | |
571 | ||
6a06907d | 572 | if self.is_fn_ty(trait_) && left_name == sym::Output { |
0531ce1d XL |
573 | ty_to_fn |
574 | .entry(*ty.clone()) | |
575 | .and_modify(|e| *e = (e.0.clone(), Some(rhs.clone()))) | |
576 | .or_insert((None, Some(rhs))); | |
577 | continue; | |
578 | } | |
579 | ||
dfeec247 XL |
580 | let args = &mut new_trait_path |
581 | .segments | |
582 | .last_mut() | |
583 | .expect("segments were empty") | |
584 | .args; | |
585 | ||
586 | match args { | |
3dfed10e | 587 | // Convert something like '<T as Iterator::Item> = u8' |
dfeec247 XL |
588 | // to 'T: Iterator<Item=u8>' |
589 | GenericArgs::AngleBracketed { | |
590 | ref mut bindings, .. | |
591 | } => { | |
592 | bindings.push(TypeBinding { | |
5869c6ff | 593 | name: left_name, |
dfeec247 XL |
594 | kind: TypeBindingKind::Equality { ty: rhs }, |
595 | }); | |
596 | } | |
597 | GenericArgs::Parenthesized { .. } => { | |
598 | existing_predicates.push(WherePredicate::EqPredicate { | |
599 | lhs: lhs.clone(), | |
600 | rhs, | |
601 | }); | |
602 | continue; // If something other than a Fn ends up | |
603 | // with parenthesis, leave it alone | |
0531ce1d XL |
604 | } |
605 | } | |
606 | ||
dfeec247 | 607 | let bounds = ty_to_bounds.entry(*ty.clone()).or_default(); |
0531ce1d | 608 | |
8faf50e0 | 609 | bounds.insert(GenericBound::TraitBound( |
0531ce1d XL |
610 | PolyTrait { |
611 | trait_: Type::ResolvedPath { | |
612 | path: new_trait_path, | |
dfeec247 | 613 | did: *did, |
0531ce1d XL |
614 | is_generic: *is_generic, |
615 | }, | |
616 | generic_params: Vec::new(), | |
617 | }, | |
618 | hir::TraitBoundModifier::None, | |
619 | )); | |
620 | ||
0731742a | 621 | // Remove any existing 'plain' bound (e.g., 'T: Iterator`) so |
0531ce1d XL |
622 | // that we don't see a |
623 | // duplicate bound like `T: Iterator + Iterator<Item=u8>` | |
624 | // on the docs page. | |
8faf50e0 | 625 | bounds.remove(&GenericBound::TraitBound( |
0531ce1d XL |
626 | PolyTrait { |
627 | trait_: *trait_.clone(), | |
628 | generic_params: Vec::new(), | |
629 | }, | |
630 | hir::TraitBoundModifier::None, | |
631 | )); | |
632 | // Avoid creating any new duplicate bounds later in the outer | |
633 | // loop | |
634 | ty_to_traits | |
635 | .entry(*ty.clone()) | |
b7449926 | 636 | .or_default() |
0531ce1d XL |
637 | .insert(*trait_.clone()); |
638 | } | |
6a06907d | 639 | _ => panic!("Unexpected trait {:?} for {:?}", trait_, item_def_id), |
0531ce1d XL |
640 | } |
641 | } | |
6a06907d | 642 | _ => panic!("Unexpected LHS {:?} for {:?}", lhs, item_def_id), |
0531ce1d XL |
643 | } |
644 | } | |
645 | }; | |
646 | } | |
647 | ||
648 | let final_bounds = self.make_final_bounds(ty_to_bounds, ty_to_fn, lifetime_to_bounds); | |
649 | ||
650 | existing_predicates.extend(final_bounds); | |
651 | ||
8faf50e0 XL |
652 | for param in generic_params.iter_mut() { |
653 | match param.kind { | |
654 | GenericParamDefKind::Type { ref mut default, ref mut bounds, .. } => { | |
655 | // We never want something like `impl<T=Foo>`. | |
656 | default.take(); | |
5869c6ff | 657 | let generic_ty = Type::Generic(param.name); |
0531ce1d | 658 | if !has_sized.contains(&generic_ty) { |
8faf50e0 | 659 | bounds.insert(0, GenericBound::maybe_sized(self.cx)); |
0531ce1d XL |
660 | } |
661 | } | |
8faf50e0 | 662 | GenericParamDefKind::Lifetime => {} |
17df50a5 XL |
663 | GenericParamDefKind::Const { ref mut default, .. } => { |
664 | // We never want something like `impl<const N: usize = 10>` | |
665 | default.take(); | |
666 | } | |
0531ce1d XL |
667 | } |
668 | } | |
669 | ||
670 | self.sort_where_predicates(&mut existing_predicates); | |
671 | ||
dfeec247 | 672 | Generics { params: generic_params, where_predicates: existing_predicates } |
0531ce1d XL |
673 | } |
674 | ||
675 | // Ensure that the predicates are in a consistent order. The precise | |
676 | // ordering doesn't actually matter, but it's important that | |
677 | // a given set of predicates always appears in the same order - | |
678 | // both for visual consistency between 'rustdoc' runs, and to | |
679 | // make writing tests much easier | |
680 | #[inline] | |
681 | fn sort_where_predicates(&self, mut predicates: &mut Vec<WherePredicate>) { | |
682 | // We should never have identical bounds - and if we do, | |
683 | // they're visually identical as well. Therefore, using | |
684 | // an unstable sort is fine. | |
685 | self.unstable_debug_sort(&mut predicates); | |
686 | } | |
687 | ||
688 | // Ensure that the bounds are in a consistent order. The precise | |
689 | // ordering doesn't actually matter, but it's important that | |
690 | // a given set of bounds always appears in the same order - | |
691 | // both for visual consistency between 'rustdoc' runs, and to | |
692 | // make writing tests much easier | |
693 | #[inline] | |
8faf50e0 | 694 | fn sort_where_bounds(&self, mut bounds: &mut Vec<GenericBound>) { |
0531ce1d XL |
695 | // We should never have identical bounds - and if we do, |
696 | // they're visually identical as well. Therefore, using | |
697 | // an unstable sort is fine. | |
698 | self.unstable_debug_sort(&mut bounds); | |
699 | } | |
700 | ||
701 | // This might look horrendously hacky, but it's actually not that bad. | |
702 | // | |
703 | // For performance reasons, we use several different FxHashMaps | |
704 | // in the process of computing the final set of where predicates. | |
705 | // However, the iteration order of a HashMap is completely unspecified. | |
706 | // In fact, the iteration of an FxHashMap can even vary between platforms, | |
707 | // since FxHasher has different behavior for 32-bit and 64-bit platforms. | |
708 | // | |
b7449926 | 709 | // Obviously, it's extremely undesirable for documentation rendering |
3dfed10e | 710 | // to be dependent on the platform it's run on. Apart from being confusing |
0531ce1d XL |
711 | // to end users, it makes writing tests much more difficult, as predicates |
712 | // can appear in any order in the final result. | |
713 | // | |
8faf50e0 | 714 | // To solve this problem, we sort WherePredicates and GenericBounds |
0531ce1d XL |
715 | // by their Debug string. The thing to keep in mind is that we don't really |
716 | // care what the final order is - we're synthesizing an impl or bound | |
717 | // ourselves, so any order can be considered equally valid. By sorting the | |
718 | // predicates and bounds, however, we ensure that for a given codebase, all | |
719 | // auto-trait impls always render in exactly the same way. | |
720 | // | |
b7449926 | 721 | // Using the Debug implementation for sorting prevents us from needing to |
0731742a | 722 | // write quite a bit of almost entirely useless code (e.g., how should two |
0531ce1d | 723 | // Types be sorted relative to each other). It also allows us to solve the |
8faf50e0 | 724 | // problem for both WherePredicates and GenericBounds at the same time. This |
0531ce1d XL |
725 | // approach is probably somewhat slower, but the small number of items |
726 | // involved (impls rarely have more than a few bounds) means that it | |
727 | // shouldn't matter in practice. | |
728 | fn unstable_debug_sort<T: Debug>(&self, vec: &mut Vec<T>) { | |
83c7162d | 729 | vec.sort_by_cached_key(|x| format!("{:?}", x)) |
0531ce1d XL |
730 | } |
731 | ||
6a06907d XL |
732 | fn is_fn_ty(&self, ty: &Type) -> bool { |
733 | let tcx = self.cx.tcx; | |
5869c6ff XL |
734 | match ty { |
735 | &Type::ResolvedPath { did, .. } => { | |
736 | did == tcx.require_lang_item(LangItem::Fn, None) | |
737 | || did == tcx.require_lang_item(LangItem::FnMut, None) | |
738 | || did == tcx.require_lang_item(LangItem::FnOnce, None) | |
0531ce1d XL |
739 | } |
740 | _ => false, | |
741 | } | |
742 | } | |
0531ce1d XL |
743 | } |
744 | ||
6a06907d XL |
745 | fn region_name(region: Region<'_>) -> Option<Symbol> { |
746 | match region { | |
747 | &ty::ReEarlyBound(r) => Some(r.name), | |
748 | _ => None, | |
749 | } | |
750 | } | |
751 | ||
0531ce1d | 752 | // Replaces all ReVars in a type with ty::Region's, using the provided map |
dc9dc135 | 753 | struct RegionReplacer<'a, 'tcx> { |
0531ce1d | 754 | vid_to_region: &'a FxHashMap<ty::RegionVid, ty::Region<'tcx>>, |
dc9dc135 | 755 | tcx: TyCtxt<'tcx>, |
0531ce1d XL |
756 | } |
757 | ||
dc9dc135 XL |
758 | impl<'a, 'tcx> TypeFolder<'tcx> for RegionReplacer<'a, 'tcx> { |
759 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { | |
0531ce1d XL |
760 | self.tcx |
761 | } | |
762 | ||
763 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { | |
764 | (match r { | |
765 | &ty::ReVar(vid) => self.vid_to_region.get(&vid).cloned(), | |
766 | _ => None, | |
dfeec247 XL |
767 | }) |
768 | .unwrap_or_else(|| r.super_fold_with(self)) | |
0531ce1d XL |
769 | } |
770 | } |