]>
Commit | Line | Data |
---|---|---|
ea8adc8c | 1 | use super::OverlapError; |
54a0048b | 2 | |
9fa01778 | 3 | use crate::traits; |
74b04a01 | 4 | use rustc_hir::def_id::DefId; |
5e7ed085 | 5 | use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams}; |
064997fb | 6 | use rustc_middle::ty::{self, TyCtxt, TypeVisitable}; |
54a0048b | 7 | |
ba9703b0 | 8 | pub use rustc_middle::traits::specialization_graph::*; |
54a0048b | 9 | |
0731742a XL |
10 | #[derive(Copy, Clone, Debug)] |
11 | pub enum FutureCompatOverlapErrorKind { | |
0731742a | 12 | Issue33140, |
74b04a01 | 13 | LeakCheck, |
0731742a XL |
14 | } |
15 | ||
16 | #[derive(Debug)] | |
487cf647 FG |
17 | pub struct FutureCompatOverlapError<'tcx> { |
18 | pub error: OverlapError<'tcx>, | |
dfeec247 | 19 | pub kind: FutureCompatOverlapErrorKind, |
0731742a XL |
20 | } |
21 | ||
54a0048b | 22 | /// The result of attempting to insert an impl into a group of children. |
487cf647 | 23 | enum Inserted<'tcx> { |
54a0048b | 24 | /// The impl was inserted as a new child in this group of children. |
487cf647 | 25 | BecameNewSibling(Option<FutureCompatOverlapError<'tcx>>), |
54a0048b | 26 | |
a1dfa0c6 XL |
27 | /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc. |
28 | ReplaceChildren(Vec<DefId>), | |
54a0048b SL |
29 | |
30 | /// The impl is a specialization of an existing child. | |
31 | ShouldRecurseOn(DefId), | |
54a0048b SL |
32 | } |
33 | ||
a2a8927a | 34 | trait ChildrenExt<'tcx> { |
74b04a01 XL |
35 | fn insert_blindly(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId); |
36 | fn remove_existing(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId); | |
37 | ||
38 | fn insert( | |
39 | &mut self, | |
40 | tcx: TyCtxt<'tcx>, | |
41 | impl_def_id: DefId, | |
42 | simplified_self: Option<SimplifiedType>, | |
5099ac24 | 43 | overlap_mode: OverlapMode, |
487cf647 | 44 | ) -> Result<Inserted<'tcx>, OverlapError<'tcx>>; |
74b04a01 XL |
45 | } |
46 | ||
487cf647 | 47 | impl<'tcx> ChildrenExt<'tcx> for Children { |
0731742a | 48 | /// Insert an impl into this set of children without comparing to any existing impls. |
487cf647 | 49 | fn insert_blindly(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId) { |
54a0048b | 50 | let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); |
923072b8 | 51 | if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer) |
5e7ed085 | 52 | { |
e74abb32 | 53 | debug!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id, st); |
c295e0f8 | 54 | self.non_blanket_impls.entry(st).or_default().push(impl_def_id) |
54a0048b | 55 | } else { |
e74abb32 | 56 | debug!("insert_blindly: impl_def_id={:?} st=None", impl_def_id); |
54a0048b SL |
57 | self.blanket_impls.push(impl_def_id) |
58 | } | |
59 | } | |
60 | ||
9fa01778 | 61 | /// Removes an impl from this set of children. Used when replacing |
8faf50e0 XL |
62 | /// an impl with a parent. The impl must be present in the list of |
63 | /// children already. | |
487cf647 | 64 | fn remove_existing(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId) { |
8faf50e0 XL |
65 | let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); |
66 | let vec: &mut Vec<DefId>; | |
923072b8 | 67 | if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer) |
5e7ed085 | 68 | { |
e74abb32 | 69 | debug!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id, st); |
c295e0f8 | 70 | vec = self.non_blanket_impls.get_mut(&st).unwrap(); |
8faf50e0 | 71 | } else { |
e74abb32 | 72 | debug!("remove_existing: impl_def_id={:?} st=None", impl_def_id); |
8faf50e0 XL |
73 | vec = &mut self.blanket_impls; |
74 | } | |
75 | ||
76 | let index = vec.iter().position(|d| *d == impl_def_id).unwrap(); | |
77 | vec.remove(index); | |
78 | } | |
79 | ||
54a0048b | 80 | /// Attempt to insert an impl into this set of children, while comparing for |
3b2f2976 | 81 | /// specialization relationships. |
dc9dc135 XL |
82 | fn insert( |
83 | &mut self, | |
487cf647 | 84 | tcx: TyCtxt<'tcx>, |
dc9dc135 XL |
85 | impl_def_id: DefId, |
86 | simplified_self: Option<SimplifiedType>, | |
5099ac24 | 87 | overlap_mode: OverlapMode, |
487cf647 | 88 | ) -> Result<Inserted<'tcx>, OverlapError<'tcx>> { |
ff7c6d11 | 89 | let mut last_lint = None; |
a1dfa0c6 | 90 | let mut replace_children = Vec::new(); |
ff7c6d11 | 91 | |
dfeec247 | 92 | debug!("insert(impl_def_id={:?}, simplified_self={:?})", impl_def_id, simplified_self,); |
8faf50e0 | 93 | |
0731742a | 94 | let possible_siblings = match simplified_self { |
74b04a01 XL |
95 | Some(st) => PotentialSiblings::Filtered(filtered_children(self, st)), |
96 | None => PotentialSiblings::Unfiltered(iter_children(self)), | |
0731742a XL |
97 | }; |
98 | ||
99 | for possible_sibling in possible_siblings { | |
8faf50e0 XL |
100 | debug!( |
101 | "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}", | |
dfeec247 | 102 | impl_def_id, simplified_self, possible_sibling, |
8faf50e0 | 103 | ); |
54a0048b | 104 | |
487cf647 | 105 | let create_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>| { |
ff7c6d11 XL |
106 | let trait_ref = overlap.impl_header.trait_ref.unwrap(); |
107 | let self_ty = trait_ref.self_ty(); | |
74b04a01 | 108 | |
487cf647 FG |
109 | OverlapError { |
110 | with_impl: possible_sibling, | |
111 | trait_ref, | |
112 | // Only report the `Self` type if it has at least | |
113 | // some outer concrete shell; otherwise, it's | |
114 | // not adding much information. | |
115 | self_ty: if self_ty.has_concrete_skeleton() { Some(self_ty) } else { None }, | |
116 | intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes, | |
117 | involves_placeholder: overlap.involves_placeholder, | |
118 | } | |
ff7c6d11 XL |
119 | }; |
120 | ||
487cf647 | 121 | let report_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>, |
74b04a01 XL |
122 | last_lint: &mut _| { |
123 | // Found overlap, but no specialization; error out or report future-compat warning. | |
124 | ||
125 | // Do we *still* get overlap if we disable the future-incompatible modes? | |
126 | let should_err = traits::overlapping_impls( | |
127 | tcx, | |
128 | possible_sibling, | |
129 | impl_def_id, | |
130 | traits::SkipLeakCheck::default(), | |
5099ac24 | 131 | overlap_mode, |
2b03887a FG |
132 | ) |
133 | .is_some(); | |
74b04a01 XL |
134 | |
135 | let error = create_overlap_error(overlap); | |
136 | ||
137 | if should_err { | |
138 | Err(error) | |
139 | } else { | |
140 | *last_lint = Some(FutureCompatOverlapError { | |
141 | error, | |
142 | kind: FutureCompatOverlapErrorKind::LeakCheck, | |
143 | }); | |
144 | ||
145 | Ok((false, false)) | |
146 | } | |
147 | }; | |
148 | ||
149 | let last_lint_mut = &mut last_lint; | |
ff7c6d11 XL |
150 | let (le, ge) = traits::overlapping_impls( |
151 | tcx, | |
152 | possible_sibling, | |
153 | impl_def_id, | |
74b04a01 | 154 | traits::SkipLeakCheck::Yes, |
5099ac24 | 155 | overlap_mode, |
2b03887a FG |
156 | ) |
157 | .map_or(Ok((false, false)), |overlap| { | |
158 | if let Some(overlap_kind) = | |
159 | tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) | |
160 | { | |
161 | match overlap_kind { | |
162 | ty::ImplOverlapKind::Permitted { marker: _ } => {} | |
163 | ty::ImplOverlapKind::Issue33140 => { | |
164 | *last_lint_mut = Some(FutureCompatOverlapError { | |
165 | error: create_overlap_error(overlap), | |
166 | kind: FutureCompatOverlapErrorKind::Issue33140, | |
167 | }); | |
0731742a | 168 | } |
cc61c64b XL |
169 | } |
170 | ||
2b03887a FG |
171 | return Ok((false, false)); |
172 | } | |
173 | ||
174 | let le = tcx.specializes((impl_def_id, possible_sibling)); | |
175 | let ge = tcx.specializes((possible_sibling, impl_def_id)); | |
a7813a04 | 176 | |
2b03887a FG |
177 | if le == ge { report_overlap_error(overlap, last_lint_mut) } else { Ok((le, ge)) } |
178 | })?; | |
54a0048b | 179 | |
a7813a04 | 180 | if le && !ge { |
dfeec247 XL |
181 | debug!( |
182 | "descending as child of TraitRef {:?}", | |
183 | tcx.impl_trait_ref(possible_sibling).unwrap() | |
184 | ); | |
54a0048b | 185 | |
0731742a | 186 | // The impl specializes `possible_sibling`. |
a7813a04 XL |
187 | return Ok(Inserted::ShouldRecurseOn(possible_sibling)); |
188 | } else if ge && !le { | |
dfeec247 XL |
189 | debug!( |
190 | "placing as parent of TraitRef {:?}", | |
191 | tcx.impl_trait_ref(possible_sibling).unwrap() | |
192 | ); | |
54a0048b | 193 | |
a1dfa0c6 | 194 | replace_children.push(possible_sibling); |
a7813a04 | 195 | } else { |
74b04a01 XL |
196 | // Either there's no overlap, or the overlap was already reported by |
197 | // `overlap_error`. | |
54a0048b SL |
198 | } |
199 | } | |
200 | ||
a1dfa0c6 XL |
201 | if !replace_children.is_empty() { |
202 | return Ok(Inserted::ReplaceChildren(replace_children)); | |
203 | } | |
204 | ||
0731742a | 205 | // No overlap with any potential siblings, so add as a new sibling. |
54a0048b SL |
206 | debug!("placing as new sibling"); |
207 | self.insert_blindly(tcx, impl_def_id); | |
ff7c6d11 | 208 | Ok(Inserted::BecameNewSibling(last_lint)) |
54a0048b | 209 | } |
74b04a01 | 210 | } |
54a0048b | 211 | |
74b04a01 | 212 | fn iter_children(children: &mut Children) -> impl Iterator<Item = DefId> + '_ { |
c295e0f8 | 213 | let nonblanket = children.non_blanket_impls.iter().flat_map(|(_, v)| v.iter()); |
74b04a01 XL |
214 | children.blanket_impls.iter().chain(nonblanket).cloned() |
215 | } | |
54a0048b | 216 | |
74b04a01 XL |
217 | fn filtered_children( |
218 | children: &mut Children, | |
219 | st: SimplifiedType, | |
220 | ) -> impl Iterator<Item = DefId> + '_ { | |
c295e0f8 | 221 | let nonblanket = children.non_blanket_impls.entry(st).or_default().iter(); |
74b04a01 | 222 | children.blanket_impls.iter().chain(nonblanket).cloned() |
0731742a XL |
223 | } |
224 | ||
225 | // A custom iterator used by Children::insert | |
226 | enum PotentialSiblings<I, J> | |
dfeec247 XL |
227 | where |
228 | I: Iterator<Item = DefId>, | |
229 | J: Iterator<Item = DefId>, | |
0731742a XL |
230 | { |
231 | Unfiltered(I), | |
dfeec247 | 232 | Filtered(J), |
0731742a XL |
233 | } |
234 | ||
235 | impl<I, J> Iterator for PotentialSiblings<I, J> | |
dfeec247 XL |
236 | where |
237 | I: Iterator<Item = DefId>, | |
238 | J: Iterator<Item = DefId>, | |
0731742a XL |
239 | { |
240 | type Item = DefId; | |
241 | ||
242 | fn next(&mut self) -> Option<Self::Item> { | |
243 | match *self { | |
244 | PotentialSiblings::Unfiltered(ref mut iter) => iter.next(), | |
dfeec247 | 245 | PotentialSiblings::Filtered(ref mut iter) => iter.next(), |
0731742a | 246 | } |
54a0048b SL |
247 | } |
248 | } | |
249 | ||
487cf647 | 250 | pub trait GraphExt<'tcx> { |
74b04a01 XL |
251 | /// Insert a local impl into the specialization graph. If an existing impl |
252 | /// conflicts with it (has overlap, but neither specializes the other), | |
253 | /// information about the area of overlap is returned in the `Err`. | |
254 | fn insert( | |
255 | &mut self, | |
487cf647 | 256 | tcx: TyCtxt<'tcx>, |
74b04a01 | 257 | impl_def_id: DefId, |
5099ac24 | 258 | overlap_mode: OverlapMode, |
487cf647 | 259 | ) -> Result<Option<FutureCompatOverlapError<'tcx>>, OverlapError<'tcx>>; |
74b04a01 XL |
260 | |
261 | /// Insert cached metadata mapping from a child impl back to its parent. | |
487cf647 | 262 | fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'tcx>, parent: DefId, child: DefId); |
74b04a01 | 263 | } |
54a0048b | 264 | |
487cf647 | 265 | impl<'tcx> GraphExt<'tcx> for Graph { |
54a0048b SL |
266 | /// Insert a local impl into the specialization graph. If an existing impl |
267 | /// conflicts with it (has overlap, but neither specializes the other), | |
268 | /// information about the area of overlap is returned in the `Err`. | |
74b04a01 | 269 | fn insert( |
dc9dc135 | 270 | &mut self, |
487cf647 | 271 | tcx: TyCtxt<'tcx>, |
dc9dc135 | 272 | impl_def_id: DefId, |
5099ac24 | 273 | overlap_mode: OverlapMode, |
487cf647 | 274 | ) -> Result<Option<FutureCompatOverlapError<'tcx>>, OverlapError<'tcx>> { |
54a0048b SL |
275 | assert!(impl_def_id.is_local()); |
276 | ||
277 | let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); | |
278 | let trait_def_id = trait_ref.def_id; | |
279 | ||
dfeec247 XL |
280 | debug!( |
281 | "insert({:?}): inserting TraitRef {:?} into specialization graph", | |
282 | impl_def_id, trait_ref | |
283 | ); | |
54a0048b | 284 | |
0731742a | 285 | // If the reference itself contains an earlier error (e.g., due to a |
54a0048b | 286 | // resolution failure), then we just insert the impl at the top level of |
3b2f2976 | 287 | // the graph and claim that there's no overlap (in order to suppress |
54a0048b SL |
288 | // bogus errors). |
289 | if trait_ref.references_error() { | |
dfeec247 XL |
290 | debug!( |
291 | "insert: inserting dummy node for erroneous TraitRef {:?}, \ | |
74b04a01 | 292 | impl_def_id={:?}, trait_def_id={:?}", |
dfeec247 XL |
293 | trait_ref, impl_def_id, trait_def_id |
294 | ); | |
54a0048b SL |
295 | |
296 | self.parent.insert(impl_def_id, trait_def_id); | |
dfeec247 | 297 | self.children.entry(trait_def_id).or_default().insert_blindly(tcx, impl_def_id); |
ff7c6d11 | 298 | return Ok(None); |
54a0048b SL |
299 | } |
300 | ||
301 | let mut parent = trait_def_id; | |
ff7c6d11 | 302 | let mut last_lint = None; |
923072b8 | 303 | let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer); |
54a0048b | 304 | |
0731742a | 305 | // Descend the specialization tree, where `parent` is the current parent node. |
54a0048b | 306 | loop { |
a7813a04 | 307 | use self::Inserted::*; |
54a0048b | 308 | |
5099ac24 FG |
309 | let insert_result = self.children.entry(parent).or_default().insert( |
310 | tcx, | |
311 | impl_def_id, | |
312 | simplified, | |
313 | overlap_mode, | |
314 | )?; | |
54a0048b SL |
315 | |
316 | match insert_result { | |
ff7c6d11 XL |
317 | BecameNewSibling(opt_lint) => { |
318 | last_lint = opt_lint; | |
54a0048b SL |
319 | break; |
320 | } | |
a1dfa0c6 | 321 | ReplaceChildren(grand_children_to_be) => { |
8faf50e0 XL |
322 | // We currently have |
323 | // | |
324 | // P | |
325 | // | | |
326 | // G | |
327 | // | |
328 | // and we are inserting the impl N. We want to make it: | |
329 | // | |
330 | // P | |
331 | // | | |
332 | // N | |
333 | // | | |
334 | // G | |
335 | ||
336 | // Adjust P's list of children: remove G and then add N. | |
337 | { | |
dfeec247 | 338 | let siblings = self.children.get_mut(&parent).unwrap(); |
a1dfa0c6 XL |
339 | for &grand_child_to_be in &grand_children_to_be { |
340 | siblings.remove_existing(tcx, grand_child_to_be); | |
341 | } | |
8faf50e0 XL |
342 | siblings.insert_blindly(tcx, impl_def_id); |
343 | } | |
344 | ||
0731742a | 345 | // Set G's parent to N and N's parent to P. |
a1dfa0c6 XL |
346 | for &grand_child_to_be in &grand_children_to_be { |
347 | self.parent.insert(grand_child_to_be, impl_def_id); | |
348 | } | |
8faf50e0 XL |
349 | self.parent.insert(impl_def_id, parent); |
350 | ||
351 | // Add G as N's child. | |
a1dfa0c6 | 352 | for &grand_child_to_be in &grand_children_to_be { |
dfeec247 XL |
353 | self.children |
354 | .entry(impl_def_id) | |
355 | .or_default() | |
a1dfa0c6 XL |
356 | .insert_blindly(tcx, grand_child_to_be); |
357 | } | |
54a0048b SL |
358 | break; |
359 | } | |
360 | ShouldRecurseOn(new_parent) => { | |
361 | parent = new_parent; | |
362 | } | |
54a0048b SL |
363 | } |
364 | } | |
365 | ||
366 | self.parent.insert(impl_def_id, parent); | |
ff7c6d11 | 367 | Ok(last_lint) |
54a0048b SL |
368 | } |
369 | ||
370 | /// Insert cached metadata mapping from a child impl back to its parent. | |
487cf647 | 371 | fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'tcx>, parent: DefId, child: DefId) { |
54a0048b | 372 | if self.parent.insert(child, parent).is_some() { |
dfeec247 XL |
373 | bug!( |
374 | "When recording an impl from the crate store, information about its parent \ | |
74b04a01 | 375 | was already present." |
dfeec247 | 376 | ); |
54a0048b SL |
377 | } |
378 | ||
b7449926 | 379 | self.children.entry(parent).or_default().insert_blindly(tcx, child); |
54a0048b | 380 | } |
ea8adc8c | 381 | } |