]>
Commit | Line | Data |
---|---|---|
ea8adc8c | 1 | use super::OverlapError; |
54a0048b | 2 | |
9fa01778 XL |
3 | use crate::hir::def_id::DefId; |
4 | use crate::ich::{self, StableHashingContext}; | |
ea8adc8c XL |
5 | use rustc_data_structures::stable_hasher::{HashStable, StableHasher, |
6 | StableHasherResult}; | |
9fa01778 XL |
7 | use crate::traits; |
8 | use crate::ty::{self, TyCtxt, TypeFoldable}; | |
9 | use crate::ty::fast_reject::{self, SimplifiedType}; | |
0531ce1d | 10 | use rustc_data_structures::sync::Lrc; |
8faf50e0 | 11 | use syntax::ast::Ident; |
9fa01778 XL |
12 | use crate::util::captures::Captures; |
13 | use crate::util::nodemap::{DefIdMap, FxHashMap}; | |
54a0048b SL |
14 | |
15 | /// A per-trait graph of impls in specialization order. At the moment, this | |
16 | /// graph forms a tree rooted with the trait itself, with all other nodes | |
17 | /// representing impls, and parent-child relationships representing | |
18 | /// specializations. | |
19 | /// | |
20 | /// The graph provides two key services: | |
21 | /// | |
0731742a | 22 | /// - Construction. This implicitly checks for overlapping impls (i.e., impls |
54a0048b SL |
23 | /// that overlap but where neither specializes the other -- an artifact of the |
24 | /// simple "chain" rule. | |
25 | /// | |
26 | /// - Parent extraction. In particular, the graph can give you the *immediate* | |
27 | /// parents of a given specializing impl, which is needed for extracting | |
3b2f2976 | 28 | /// default items amongst other things. In the simple "chain" rule, every impl |
54a0048b | 29 | /// has at most one parent. |
0531ce1d | 30 | #[derive(RustcEncodable, RustcDecodable)] |
54a0048b | 31 | pub struct Graph { |
0731742a XL |
32 | // All impls have a parent; the "root" impls have as their parent the `def_id` |
33 | // of the trait. | |
54a0048b SL |
34 | parent: DefIdMap<DefId>, |
35 | ||
0731742a | 36 | // The "root" impls are found by looking up the trait's def_id. |
54a0048b SL |
37 | children: DefIdMap<Children>, |
38 | } | |
39 | ||
40 | /// Children of a given impl, grouped into blanket/non-blanket varieties as is | |
41 | /// done in `TraitDef`. | |
b7449926 | 42 | #[derive(Default, RustcEncodable, RustcDecodable)] |
54a0048b SL |
43 | struct Children { |
44 | // Impls of a trait (or specializations of a given impl). To allow for | |
45 | // quicker lookup, the impls are indexed by a simplified version of their | |
46 | // `Self` type: impls with a simplifiable `Self` are stored in | |
47 | // `nonblanket_impls` keyed by it, while all other impls are stored in | |
48 | // `blanket_impls`. | |
49 | // | |
50 | // A similar division is used within `TraitDef`, but the lists there collect | |
51 | // together *all* the impls for a trait, and are populated prior to building | |
52 | // the specialization graph. | |
53 | ||
54 | /// Impls of the trait. | |
476ff2be | 55 | nonblanket_impls: FxHashMap<fast_reject::SimplifiedType, Vec<DefId>>, |
54a0048b SL |
56 | |
57 | /// Blanket impls associated with the trait. | |
58 | blanket_impls: Vec<DefId>, | |
59 | } | |
60 | ||
0731742a XL |
61 | #[derive(Copy, Clone, Debug)] |
62 | pub enum FutureCompatOverlapErrorKind { | |
63 | Issue43355, | |
64 | Issue33140, | |
65 | } | |
66 | ||
67 | #[derive(Debug)] | |
68 | pub struct FutureCompatOverlapError { | |
69 | pub error: OverlapError, | |
70 | pub kind: FutureCompatOverlapErrorKind | |
71 | } | |
72 | ||
54a0048b | 73 | /// The result of attempting to insert an impl into a group of children. |
a7813a04 | 74 | enum Inserted { |
54a0048b | 75 | /// The impl was inserted as a new child in this group of children. |
0731742a | 76 | BecameNewSibling(Option<FutureCompatOverlapError>), |
54a0048b | 77 | |
a1dfa0c6 XL |
78 | /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc. |
79 | ReplaceChildren(Vec<DefId>), | |
54a0048b SL |
80 | |
81 | /// The impl is a specialization of an existing child. | |
82 | ShouldRecurseOn(DefId), | |
54a0048b SL |
83 | } |
84 | ||
a7813a04 | 85 | impl<'a, 'gcx, 'tcx> Children { |
0731742a | 86 | /// Insert an impl into this set of children without comparing to any existing impls. |
a7813a04 XL |
87 | fn insert_blindly(&mut self, |
88 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
89 | impl_def_id: DefId) { | |
54a0048b SL |
90 | let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); |
91 | if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) { | |
8faf50e0 | 92 | debug!("insert_blindly: impl_def_id={:?} sty={:?}", impl_def_id, sty); |
b7449926 | 93 | self.nonblanket_impls.entry(sty).or_default().push(impl_def_id) |
54a0048b | 94 | } else { |
8faf50e0 | 95 | debug!("insert_blindly: impl_def_id={:?} sty=None", impl_def_id); |
54a0048b SL |
96 | self.blanket_impls.push(impl_def_id) |
97 | } | |
98 | } | |
99 | ||
9fa01778 | 100 | /// Removes an impl from this set of children. Used when replacing |
8faf50e0 XL |
101 | /// an impl with a parent. The impl must be present in the list of |
102 | /// children already. | |
103 | fn remove_existing(&mut self, | |
104 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
105 | impl_def_id: DefId) { | |
106 | let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); | |
107 | let vec: &mut Vec<DefId>; | |
108 | if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) { | |
109 | debug!("remove_existing: impl_def_id={:?} sty={:?}", impl_def_id, sty); | |
110 | vec = self.nonblanket_impls.get_mut(&sty).unwrap(); | |
111 | } else { | |
112 | debug!("remove_existing: impl_def_id={:?} sty=None", impl_def_id); | |
113 | vec = &mut self.blanket_impls; | |
114 | } | |
115 | ||
116 | let index = vec.iter().position(|d| *d == impl_def_id).unwrap(); | |
117 | vec.remove(index); | |
118 | } | |
119 | ||
54a0048b | 120 | /// Attempt to insert an impl into this set of children, while comparing for |
3b2f2976 | 121 | /// specialization relationships. |
a7813a04 XL |
122 | fn insert(&mut self, |
123 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
124 | impl_def_id: DefId, | |
125 | simplified_self: Option<SimplifiedType>) | |
126 | -> Result<Inserted, OverlapError> | |
54a0048b | 127 | { |
ff7c6d11 | 128 | let mut last_lint = None; |
a1dfa0c6 | 129 | let mut replace_children = Vec::new(); |
ff7c6d11 | 130 | |
8faf50e0 XL |
131 | debug!( |
132 | "insert(impl_def_id={:?}, simplified_self={:?})", | |
133 | impl_def_id, | |
134 | simplified_self, | |
135 | ); | |
136 | ||
0731742a XL |
137 | let possible_siblings = match simplified_self { |
138 | Some(sty) => PotentialSiblings::Filtered(self.filtered(sty)), | |
139 | None => PotentialSiblings::Unfiltered(self.iter()), | |
140 | }; | |
141 | ||
142 | for possible_sibling in possible_siblings { | |
8faf50e0 XL |
143 | debug!( |
144 | "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}", | |
145 | impl_def_id, | |
146 | simplified_self, | |
147 | possible_sibling, | |
148 | ); | |
54a0048b | 149 | |
0bf4aa26 | 150 | let overlap_error = |overlap: traits::coherence::OverlapResult<'_>| { |
0731742a | 151 | // Found overlap, but no specialization; error out. |
ff7c6d11 XL |
152 | let trait_ref = overlap.impl_header.trait_ref.unwrap(); |
153 | let self_ty = trait_ref.self_ty(); | |
154 | OverlapError { | |
155 | with_impl: possible_sibling, | |
156 | trait_desc: trait_ref.to_string(), | |
0731742a | 157 | // Only report the `Self` type if it has at least |
ff7c6d11 XL |
158 | // some outer concrete shell; otherwise, it's |
159 | // not adding much information. | |
160 | self_desc: if self_ty.has_concrete_skeleton() { | |
161 | Some(self_ty.to_string()) | |
162 | } else { | |
163 | None | |
164 | }, | |
165 | intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes, | |
0731742a | 166 | involves_placeholder: overlap.involves_placeholder, |
ff7c6d11 XL |
167 | } |
168 | }; | |
169 | ||
a7813a04 | 170 | let tcx = tcx.global_tcx(); |
ff7c6d11 XL |
171 | let (le, ge) = traits::overlapping_impls( |
172 | tcx, | |
173 | possible_sibling, | |
174 | impl_def_id, | |
175 | traits::IntercrateMode::Issue43355, | |
176 | |overlap| { | |
0731742a XL |
177 | if let Some(overlap_kind) = |
178 | tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) | |
179 | { | |
180 | match overlap_kind { | |
181 | ty::ImplOverlapKind::Permitted => {} | |
182 | ty::ImplOverlapKind::Issue33140 => { | |
183 | last_lint = Some(FutureCompatOverlapError { | |
184 | error: overlap_error(overlap), | |
185 | kind: FutureCompatOverlapErrorKind::Issue33140 | |
186 | }); | |
187 | } | |
188 | } | |
189 | ||
cc61c64b XL |
190 | return Ok((false, false)); |
191 | } | |
192 | ||
ea8adc8c XL |
193 | let le = tcx.specializes((impl_def_id, possible_sibling)); |
194 | let ge = tcx.specializes((possible_sibling, impl_def_id)); | |
a7813a04 XL |
195 | |
196 | if le == ge { | |
ff7c6d11 | 197 | Err(overlap_error(overlap)) |
a7813a04 XL |
198 | } else { |
199 | Ok((le, ge)) | |
200 | } | |
ff7c6d11 XL |
201 | }, |
202 | || Ok((false, false)), | |
203 | )?; | |
54a0048b | 204 | |
a7813a04 XL |
205 | if le && !ge { |
206 | debug!("descending as child of TraitRef {:?}", | |
207 | tcx.impl_trait_ref(possible_sibling).unwrap()); | |
54a0048b | 208 | |
0731742a | 209 | // The impl specializes `possible_sibling`. |
a7813a04 XL |
210 | return Ok(Inserted::ShouldRecurseOn(possible_sibling)); |
211 | } else if ge && !le { | |
212 | debug!("placing as parent of TraitRef {:?}", | |
213 | tcx.impl_trait_ref(possible_sibling).unwrap()); | |
54a0048b | 214 | |
a1dfa0c6 | 215 | replace_children.push(possible_sibling); |
a7813a04 | 216 | } else { |
0731742a XL |
217 | if let None = tcx.impls_are_allowed_to_overlap( |
218 | impl_def_id, possible_sibling) | |
219 | { | |
220 | // do future-compat checks for overlap. Have issue #33140 | |
221 | // errors overwrite issue #43355 errors when both are present. | |
222 | ||
ff7c6d11 XL |
223 | traits::overlapping_impls( |
224 | tcx, | |
225 | possible_sibling, | |
226 | impl_def_id, | |
227 | traits::IntercrateMode::Fixed, | |
0731742a XL |
228 | |overlap| { |
229 | last_lint = Some(FutureCompatOverlapError { | |
230 | error: overlap_error(overlap), | |
231 | kind: FutureCompatOverlapErrorKind::Issue43355 | |
232 | }); | |
233 | }, | |
ff7c6d11 XL |
234 | || (), |
235 | ); | |
236 | } | |
237 | ||
a7813a04 | 238 | // no overlap (error bailed already via ?) |
54a0048b SL |
239 | } |
240 | } | |
241 | ||
a1dfa0c6 XL |
242 | if !replace_children.is_empty() { |
243 | return Ok(Inserted::ReplaceChildren(replace_children)); | |
244 | } | |
245 | ||
0731742a | 246 | // No overlap with any potential siblings, so add as a new sibling. |
54a0048b SL |
247 | debug!("placing as new sibling"); |
248 | self.insert_blindly(tcx, impl_def_id); | |
ff7c6d11 | 249 | Ok(Inserted::BecameNewSibling(last_lint)) |
54a0048b SL |
250 | } |
251 | ||
0731742a | 252 | fn iter(&mut self) -> impl Iterator<Item = DefId> + '_ { |
8faf50e0 | 253 | let nonblanket = self.nonblanket_impls.iter_mut().flat_map(|(_, v)| v.iter()); |
0731742a | 254 | self.blanket_impls.iter().chain(nonblanket).cloned() |
54a0048b SL |
255 | } |
256 | ||
0731742a | 257 | fn filtered(&mut self, sty: SimplifiedType) -> impl Iterator<Item = DefId> + '_ { |
b7449926 | 258 | let nonblanket = self.nonblanket_impls.entry(sty).or_default().iter(); |
0731742a XL |
259 | self.blanket_impls.iter().chain(nonblanket).cloned() |
260 | } | |
261 | } | |
262 | ||
263 | // A custom iterator used by Children::insert | |
264 | enum PotentialSiblings<I, J> | |
265 | where I: Iterator<Item = DefId>, | |
266 | J: Iterator<Item = DefId> | |
267 | { | |
268 | Unfiltered(I), | |
269 | Filtered(J) | |
270 | } | |
271 | ||
272 | impl<I, J> Iterator for PotentialSiblings<I, J> | |
273 | where I: Iterator<Item = DefId>, | |
274 | J: Iterator<Item = DefId> | |
275 | { | |
276 | type Item = DefId; | |
277 | ||
278 | fn next(&mut self) -> Option<Self::Item> { | |
279 | match *self { | |
280 | PotentialSiblings::Unfiltered(ref mut iter) => iter.next(), | |
281 | PotentialSiblings::Filtered(ref mut iter) => iter.next() | |
282 | } | |
54a0048b SL |
283 | } |
284 | } | |
285 | ||
a7813a04 | 286 | impl<'a, 'gcx, 'tcx> Graph { |
54a0048b SL |
287 | pub fn new() -> Graph { |
288 | Graph { | |
289 | parent: Default::default(), | |
290 | children: Default::default(), | |
291 | } | |
292 | } | |
293 | ||
294 | /// Insert a local impl into the specialization graph. If an existing impl | |
295 | /// conflicts with it (has overlap, but neither specializes the other), | |
296 | /// information about the area of overlap is returned in the `Err`. | |
a7813a04 XL |
297 | pub fn insert(&mut self, |
298 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
299 | impl_def_id: DefId) | |
0731742a | 300 | -> Result<Option<FutureCompatOverlapError>, OverlapError> { |
54a0048b SL |
301 | assert!(impl_def_id.is_local()); |
302 | ||
303 | let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); | |
304 | let trait_def_id = trait_ref.def_id; | |
305 | ||
306 | debug!("insert({:?}): inserting TraitRef {:?} into specialization graph", | |
307 | impl_def_id, trait_ref); | |
308 | ||
0731742a | 309 | // If the reference itself contains an earlier error (e.g., due to a |
54a0048b | 310 | // resolution failure), then we just insert the impl at the top level of |
3b2f2976 | 311 | // the graph and claim that there's no overlap (in order to suppress |
54a0048b SL |
312 | // bogus errors). |
313 | if trait_ref.references_error() { | |
314 | debug!("insert: inserting dummy node for erroneous TraitRef {:?}, \ | |
315 | impl_def_id={:?}, trait_def_id={:?}", | |
316 | trait_ref, impl_def_id, trait_def_id); | |
317 | ||
318 | self.parent.insert(impl_def_id, trait_def_id); | |
b7449926 | 319 | self.children.entry(trait_def_id).or_default() |
54a0048b | 320 | .insert_blindly(tcx, impl_def_id); |
ff7c6d11 | 321 | return Ok(None); |
54a0048b SL |
322 | } |
323 | ||
324 | let mut parent = trait_def_id; | |
ff7c6d11 | 325 | let mut last_lint = None; |
54a0048b SL |
326 | let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false); |
327 | ||
0731742a | 328 | // Descend the specialization tree, where `parent` is the current parent node. |
54a0048b | 329 | loop { |
a7813a04 | 330 | use self::Inserted::*; |
54a0048b | 331 | |
b7449926 | 332 | let insert_result = self.children.entry(parent).or_default() |
a7813a04 | 333 | .insert(tcx, impl_def_id, simplified)?; |
54a0048b SL |
334 | |
335 | match insert_result { | |
ff7c6d11 XL |
336 | BecameNewSibling(opt_lint) => { |
337 | last_lint = opt_lint; | |
54a0048b SL |
338 | break; |
339 | } | |
a1dfa0c6 | 340 | ReplaceChildren(grand_children_to_be) => { |
8faf50e0 XL |
341 | // We currently have |
342 | // | |
343 | // P | |
344 | // | | |
345 | // G | |
346 | // | |
347 | // and we are inserting the impl N. We want to make it: | |
348 | // | |
349 | // P | |
350 | // | | |
351 | // N | |
352 | // | | |
353 | // G | |
354 | ||
355 | // Adjust P's list of children: remove G and then add N. | |
356 | { | |
357 | let siblings = self.children | |
358 | .get_mut(&parent) | |
359 | .unwrap(); | |
a1dfa0c6 XL |
360 | for &grand_child_to_be in &grand_children_to_be { |
361 | siblings.remove_existing(tcx, grand_child_to_be); | |
362 | } | |
8faf50e0 XL |
363 | siblings.insert_blindly(tcx, impl_def_id); |
364 | } | |
365 | ||
0731742a | 366 | // Set G's parent to N and N's parent to P. |
a1dfa0c6 XL |
367 | for &grand_child_to_be in &grand_children_to_be { |
368 | self.parent.insert(grand_child_to_be, impl_def_id); | |
369 | } | |
8faf50e0 XL |
370 | self.parent.insert(impl_def_id, parent); |
371 | ||
372 | // Add G as N's child. | |
a1dfa0c6 XL |
373 | for &grand_child_to_be in &grand_children_to_be { |
374 | self.children.entry(impl_def_id).or_default() | |
375 | .insert_blindly(tcx, grand_child_to_be); | |
376 | } | |
54a0048b SL |
377 | break; |
378 | } | |
379 | ShouldRecurseOn(new_parent) => { | |
380 | parent = new_parent; | |
381 | } | |
54a0048b SL |
382 | } |
383 | } | |
384 | ||
385 | self.parent.insert(impl_def_id, parent); | |
ff7c6d11 | 386 | Ok(last_lint) |
54a0048b SL |
387 | } |
388 | ||
389 | /// Insert cached metadata mapping from a child impl back to its parent. | |
a7813a04 XL |
390 | pub fn record_impl_from_cstore(&mut self, |
391 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
392 | parent: DefId, | |
393 | child: DefId) { | |
54a0048b SL |
394 | if self.parent.insert(child, parent).is_some() { |
395 | bug!("When recording an impl from the crate store, information about its parent \ | |
396 | was already present."); | |
397 | } | |
398 | ||
b7449926 | 399 | self.children.entry(parent).or_default().insert_blindly(tcx, child); |
54a0048b SL |
400 | } |
401 | ||
9fa01778 | 402 | /// The parent of a given impl, which is the `DefId` of the trait when the |
54a0048b SL |
403 | /// impl is a "specialization root". |
404 | pub fn parent(&self, child: DefId) -> DefId { | |
405 | *self.parent.get(&child).unwrap() | |
406 | } | |
407 | } | |
408 | ||
409 | /// A node in the specialization graph is either an impl or a trait | |
410 | /// definition; either can serve as a source of item definitions. | |
411 | /// There is always exactly one trait definition node: the root. | |
412 | #[derive(Debug, Copy, Clone)] | |
413 | pub enum Node { | |
414 | Impl(DefId), | |
415 | Trait(DefId), | |
416 | } | |
417 | ||
a7813a04 | 418 | impl<'a, 'gcx, 'tcx> Node { |
54a0048b SL |
419 | pub fn is_from_trait(&self) -> bool { |
420 | match *self { | |
421 | Node::Trait(..) => true, | |
422 | _ => false, | |
423 | } | |
424 | } | |
425 | ||
426 | /// Iterate over the items defined directly by the given (impl or trait) node. | |
0531ce1d XL |
427 | pub fn items( |
428 | &self, | |
429 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
a1dfa0c6 | 430 | ) -> ty::AssociatedItemsIterator<'a, 'gcx, 'tcx> { |
476ff2be | 431 | tcx.associated_items(self.def_id()) |
54a0048b SL |
432 | } |
433 | ||
434 | pub fn def_id(&self) -> DefId { | |
435 | match *self { | |
436 | Node::Impl(did) => did, | |
437 | Node::Trait(did) => did, | |
438 | } | |
439 | } | |
440 | } | |
441 | ||
7cac9316 XL |
442 | pub struct Ancestors { |
443 | trait_def_id: DefId, | |
0531ce1d | 444 | specialization_graph: Lrc<Graph>, |
54a0048b SL |
445 | current_source: Option<Node>, |
446 | } | |
447 | ||
7cac9316 | 448 | impl Iterator for Ancestors { |
54a0048b SL |
449 | type Item = Node; |
450 | fn next(&mut self) -> Option<Node> { | |
451 | let cur = self.current_source.take(); | |
452 | if let Some(Node::Impl(cur_impl)) = cur { | |
7cac9316 | 453 | let parent = self.specialization_graph.parent(cur_impl); |
0bf4aa26 XL |
454 | |
455 | self.current_source = if parent == self.trait_def_id { | |
456 | Some(Node::Trait(parent)) | |
54a0048b | 457 | } else { |
0bf4aa26 XL |
458 | Some(Node::Impl(parent)) |
459 | }; | |
54a0048b SL |
460 | } |
461 | cur | |
462 | } | |
463 | } | |
464 | ||
465 | pub struct NodeItem<T> { | |
466 | pub node: Node, | |
467 | pub item: T, | |
468 | } | |
469 | ||
470 | impl<T> NodeItem<T> { | |
471 | pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> { | |
472 | NodeItem { | |
473 | node: self.node, | |
474 | item: f(self.item), | |
475 | } | |
476 | } | |
477 | } | |
478 | ||
7cac9316 | 479 | impl<'a, 'gcx, 'tcx> Ancestors { |
476ff2be SL |
480 | /// Search the items from the given ancestors, returning each definition |
481 | /// with the given name and the given kind. | |
0731742a XL |
482 | // FIXME(#35870): avoid closures being unexported due to `impl Trait`. |
483 | #[inline] | |
0531ce1d XL |
484 | pub fn defs( |
485 | self, | |
486 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
8faf50e0 | 487 | trait_item_name: Ident, |
0531ce1d XL |
488 | trait_item_kind: ty::AssociatedKind, |
489 | trait_def_id: DefId, | |
490 | ) -> impl Iterator<Item = NodeItem<ty::AssociatedItem>> + Captures<'gcx> + Captures<'tcx> + 'a { | |
476ff2be | 491 | self.flat_map(move |node| { |
9fa01778 | 492 | use crate::ty::AssociatedKind::*; |
8faf50e0 XL |
493 | node.items(tcx).filter(move |impl_item| match (trait_item_kind, impl_item.kind) { |
494 | | (Const, Const) | |
495 | | (Method, Method) | |
496 | | (Type, Type) | |
497 | | (Type, Existential) | |
498 | => tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id), | |
499 | ||
500 | | (Const, _) | |
501 | | (Method, _) | |
502 | | (Type, _) | |
503 | | (Existential, _) | |
504 | => false, | |
ea8adc8c | 505 | }).map(move |item| NodeItem { node: node, item: item }) |
476ff2be | 506 | }) |
54a0048b SL |
507 | } |
508 | } | |
509 | ||
510 | /// Walk up the specialization ancestors of a given impl, starting with that | |
511 | /// impl itself. | |
0bf4aa26 | 512 | pub fn ancestors(tcx: TyCtxt<'_, '_, '_>, |
7cac9316 XL |
513 | trait_def_id: DefId, |
514 | start_from_impl: DefId) | |
515 | -> Ancestors { | |
516 | let specialization_graph = tcx.specialization_graph_of(trait_def_id); | |
54a0048b | 517 | Ancestors { |
7cac9316 XL |
518 | trait_def_id, |
519 | specialization_graph, | |
54a0048b SL |
520 | current_source: Some(Node::Impl(start_from_impl)), |
521 | } | |
522 | } | |
ea8adc8c | 523 | |
0531ce1d | 524 | impl<'a> HashStable<StableHashingContext<'a>> for Children { |
ea8adc8c | 525 | fn hash_stable<W: StableHasherResult>(&self, |
0531ce1d | 526 | hcx: &mut StableHashingContext<'a>, |
ea8adc8c XL |
527 | hasher: &mut StableHasher<W>) { |
528 | let Children { | |
529 | ref nonblanket_impls, | |
530 | ref blanket_impls, | |
531 | } = *self; | |
532 | ||
533 | ich::hash_stable_trait_impls(hcx, hasher, blanket_impls, nonblanket_impls); | |
534 | } | |
535 | } | |
536 | ||
537 | impl_stable_hash_for!(struct self::Graph { | |
538 | parent, | |
539 | children | |
540 | }); |