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