rustc_trait_selection/traits/specialize/
specialization_graph.rs

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