compiler/rustc_trait_selection/src/traits/specialize/mod.rs

   1 //! Logic and data structures related to impl specialization, explained in
   2 //! greater detail below.
   3 //!
   4 //! At the moment, this implementation support only the simple "chain" rule:
   5 //! If any two impls overlap, one must be a strict subset of the other.
   6 //!
   7 //! See the [rustc dev guide] for a bit more detail on how specialization
   8 //! fits together with the rest of the trait machinery.
   9 //!
  10 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/specialization.html
  11
  12 pub mod specialization_graph;
  13 use specialization_graph::GraphExt;
  14
  15 use crate::errors::NegativePositiveConflict;
  16 use crate::infer::{InferCtxt, InferOk, TyCtxtInferExt};
  17 use crate::traits::select::IntercrateAmbiguityCause;
  18 use crate::traits::{
  19     self, coherence, FutureCompatOverlapErrorKind, ObligationCause, ObligationCtxt,
  20 };
  21 use rustc_data_structures::fx::FxIndexSet;
  22 use rustc_errors::{error_code, DelayDm, Diagnostic};
  23 use rustc_hir::def_id::{DefId, LocalDefId};
  24 use rustc_middle::ty::{self, ImplSubject, Ty, TyCtxt};
  25 use rustc_middle::ty::{InternalSubsts, SubstsRef};
  26 use rustc_session::lint::builtin::COHERENCE_LEAK_CHECK;
  27 use rustc_session::lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS;
  28 use rustc_span::{Span, DUMMY_SP};
  29
  30 use super::util;
  31 use super::SelectionContext;
  32
  33 /// Information pertinent to an overlapping impl error.
  34 #[derive(Debug)]
  35 pub struct OverlapError<'tcx> {
  36     pub with_impl: DefId,
  37     pub trait_ref: ty::TraitRef<'tcx>,
  38     pub self_ty: Option<Ty<'tcx>>,
  39     pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause>,
  40     pub involves_placeholder: bool,
  41 }
  42
  43 /// Given a subst for the requested impl, translate it to a subst
  44 /// appropriate for the actual item definition (whether it be in that impl,
  45 /// a parent impl, or the trait).
  46 ///
  47 /// When we have selected one impl, but are actually using item definitions from
  48 /// a parent impl providing a default, we need a way to translate between the
  49 /// type parameters of the two impls. Here the `source_impl` is the one we've
  50 /// selected, and `source_substs` is a substitution of its generics.
  51 /// And `target_node` is the impl/trait we're actually going to get the
  52 /// definition from. The resulting substitution will map from `target_node`'s
  53 /// generics to `source_impl`'s generics as instantiated by `source_subst`.
  54 ///
  55 /// For example, consider the following scenario:
  56 ///
  57 /// ```ignore (illustrative)
  58 /// trait Foo { ... }
  59 /// impl<T, U> Foo for (T, U) { ... }  // target impl
  60 /// impl<V> Foo for (V, V) { ... }     // source impl
  61 /// ```
  62 ///
  63 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
  64 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
  65 ///
  66 /// where-clauses add some trickiness here, because they can be used to "define"
  67 /// an argument indirectly:
  68 ///
  69 /// ```ignore (illustrative)
  70 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
  71 ///    where I: Iterator<Item = &'a T>, T: Clone
  72 /// ```
  73 ///
  74 /// In a case like this, the substitution for `T` is determined indirectly,
  75 /// through associated type projection. We deal with such cases by using
  76 /// *fulfillment* to relate the two impls, requiring that all projections are
  77 /// resolved.
  78 pub fn translate_substs<'tcx>(
  79     infcx: &InferCtxt<'tcx>,
  80     param_env: ty::ParamEnv<'tcx>,
  81     source_impl: DefId,
  82     source_substs: SubstsRef<'tcx>,
  83     target_node: specialization_graph::Node,
  84 ) -> SubstsRef<'tcx> {
  85     debug!(
  86         "translate_substs({:?}, {:?}, {:?}, {:?})",
  87         param_env, source_impl, source_substs, target_node
  88     );
  89     let source_trait_ref =
  90         infcx.tcx.impl_trait_ref(source_impl).unwrap().subst(infcx.tcx, &source_substs);
  91
  92     // translate the Self and Param parts of the substitution, since those
  93     // vary across impls
  94     let target_substs = match target_node {
  95         specialization_graph::Node::Impl(target_impl) => {
  96             // no need to translate if we're targeting the impl we started with
  97             if source_impl == target_impl {
  98                 return source_substs;
  99             }
 100
 101             fulfill_implication(infcx, param_env, source_trait_ref, target_impl).unwrap_or_else(
 102                 |_| {
 103                     bug!(
 104                         "When translating substitutions for specialization, the expected \
 105                          specialization failed to hold"
 106                     )
 107                 },
 108             )
 109         }
 110         specialization_graph::Node::Trait(..) => source_trait_ref.substs,
 111     };
 112
 113     // directly inherent the method generics, since those do not vary across impls
 114     source_substs.rebase_onto(infcx.tcx, source_impl, target_substs)
 115 }
 116
 117 /// Is `impl1` a specialization of `impl2`?
 118 ///
 119 /// Specialization is determined by the sets of types to which the impls apply;
 120 /// `impl1` specializes `impl2` if it applies to a subset of the types `impl2` applies
 121 /// to.
 122 #[instrument(skip(tcx), level = "debug")]
 123 pub(super) fn specializes(tcx: TyCtxt<'_>, (impl1_def_id, impl2_def_id): (DefId, DefId)) -> bool {
 124     // The feature gate should prevent introducing new specializations, but not
 125     // taking advantage of upstream ones.
 126     let features = tcx.features();
 127     let specialization_enabled = features.specialization || features.min_specialization;
 128     if !specialization_enabled && (impl1_def_id.is_local() || impl2_def_id.is_local()) {
 129         return false;
 130     }
 131
 132     // We determine whether there's a subset relationship by:
 133     //
 134     // - replacing bound vars with placeholders in impl1,
 135     // - assuming the where clauses for impl1,
 136     // - instantiating impl2 with fresh inference variables,
 137     // - unifying,
 138     // - attempting to prove the where clauses for impl2
 139     //
 140     // The last three steps are encapsulated in `fulfill_implication`.
 141     //
 142     // See RFC 1210 for more details and justification.
 143
 144     // Currently we do not allow e.g., a negative impl to specialize a positive one
 145     if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
 146         return false;
 147     }
 148
 149     // create a parameter environment corresponding to a (placeholder) instantiation of impl1
 150     let penv = tcx.param_env(impl1_def_id);
 151     let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap().subst_identity();
 152
 153     // Create an infcx, taking the predicates of impl1 as assumptions:
 154     let infcx = tcx.infer_ctxt().build();
 155     let impl1_trait_ref =
 156         match traits::fully_normalize(&infcx, ObligationCause::dummy(), penv, impl1_trait_ref) {
 157             Ok(impl1_trait_ref) => impl1_trait_ref,
 158             Err(_errors) => {
 159                 tcx.sess.delay_span_bug(
 160                     tcx.def_span(impl1_def_id),
 161                     format!("failed to fully normalize {impl1_trait_ref}"),
 162                 );
 163                 impl1_trait_ref
 164             }
 165         };
 166
 167     // Attempt to prove that impl2 applies, given all of the above.
 168     fulfill_implication(&infcx, penv, impl1_trait_ref, impl2_def_id).is_ok()
 169 }
 170
 171 /// Attempt to fulfill all obligations of `target_impl` after unification with
 172 /// `source_trait_ref`. If successful, returns a substitution for *all* the
 173 /// generics of `target_impl`, including both those needed to unify with
 174 /// `source_trait_ref` and those whose identity is determined via a where
 175 /// clause in the impl.
 176 fn fulfill_implication<'tcx>(
 177     infcx: &InferCtxt<'tcx>,
 178     param_env: ty::ParamEnv<'tcx>,
 179     source_trait_ref: ty::TraitRef<'tcx>,
 180     target_impl: DefId,
 181 ) -> Result<SubstsRef<'tcx>, ()> {
 182     debug!(
 183         "fulfill_implication({:?}, trait_ref={:?} |- {:?} applies)",
 184         param_env, source_trait_ref, target_impl
 185     );
 186
 187     let source_trait = ImplSubject::Trait(source_trait_ref);
 188
 189     let selcx = &mut SelectionContext::new(&infcx);
 190     let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl);
 191     let (target_trait, obligations) =
 192         util::impl_subject_and_oblig(selcx, param_env, target_impl, target_substs);
 193
 194     // do the impls unify? If not, no specialization.
 195     let Ok(InferOk { obligations: more_obligations, .. }) =
 196         infcx.at(&ObligationCause::dummy(), param_env).eq(source_trait, target_trait)
 197     else {
 198         debug!(
 199             "fulfill_implication: {:?} does not unify with {:?}",
 200             source_trait, target_trait
 201         );
 202         return Err(());
 203     };
 204
 205     // Needs to be `in_snapshot` because this function is used to rebase
 206     // substitutions, which may happen inside of a select within a probe.
 207     let ocx = ObligationCtxt::new_in_snapshot(infcx);
 208     // attempt to prove all of the predicates for impl2 given those for impl1
 209     // (which are packed up in penv)
 210     ocx.register_obligations(obligations.chain(more_obligations));
 211
 212     let errors = ocx.select_all_or_error();
 213     if !errors.is_empty() {
 214         // no dice!
 215         debug!(
 216             "fulfill_implication: for impls on {:?} and {:?}, \
 217                  could not fulfill: {:?} given {:?}",
 218             source_trait,
 219             target_trait,
 220             errors,
 221             param_env.caller_bounds()
 222         );
 223         return Err(());
 224     }
 225
 226     debug!("fulfill_implication: an impl for {:?} specializes {:?}", source_trait, target_trait);
 227
 228     // Now resolve the *substitution* we built for the target earlier, replacing
 229     // the inference variables inside with whatever we got from fulfillment.
 230     Ok(infcx.resolve_vars_if_possible(target_substs))
 231 }
 232
 233 /// Query provider for `specialization_graph_of`.
 234 pub(super) fn specialization_graph_provider(
 235     tcx: TyCtxt<'_>,
 236     trait_id: DefId,
 237 ) -> specialization_graph::Graph {
 238     let mut sg = specialization_graph::Graph::new();
 239     let overlap_mode = specialization_graph::OverlapMode::get(tcx, trait_id);
 240
 241     let mut trait_impls: Vec<_> = tcx.all_impls(trait_id).collect();
 242
 243     // The coherence checking implementation seems to rely on impls being
 244     // iterated over (roughly) in definition order, so we are sorting by
 245     // negated `CrateNum` (so remote definitions are visited first) and then
 246     // by a flattened version of the `DefIndex`.
 247     trait_impls
 248         .sort_unstable_by_key(|def_id| (-(def_id.krate.as_u32() as i64), def_id.index.index()));
 249
 250     for impl_def_id in trait_impls {
 251         if let Some(impl_def_id) = impl_def_id.as_local() {
 252             // This is where impl overlap checking happens:
 253             let insert_result = sg.insert(tcx, impl_def_id.to_def_id(), overlap_mode);
 254             // Report error if there was one.
 255             let (overlap, used_to_be_allowed) = match insert_result {
 256                 Err(overlap) => (Some(overlap), None),
 257                 Ok(Some(overlap)) => (Some(overlap.error), Some(overlap.kind)),
 258                 Ok(None) => (None, None),
 259             };
 260
 261             if let Some(overlap) = overlap {
 262                 report_overlap_conflict(tcx, overlap, impl_def_id, used_to_be_allowed, &mut sg);
 263             }
 264         } else {
 265             let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
 266             sg.record_impl_from_cstore(tcx, parent, impl_def_id)
 267         }
 268     }
 269
 270     sg
 271 }
 272
 273 // This function is only used when
 274 // encountering errors and inlining
 275 // it negatively impacts perf.
 276 #[cold]
 277 #[inline(never)]
 278 fn report_overlap_conflict<'tcx>(
 279     tcx: TyCtxt<'tcx>,
 280     overlap: OverlapError<'tcx>,
 281     impl_def_id: LocalDefId,
 282     used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
 283     sg: &mut specialization_graph::Graph,
 284 ) {
 285     let impl_polarity = tcx.impl_polarity(impl_def_id.to_def_id());
 286     let other_polarity = tcx.impl_polarity(overlap.with_impl);
 287     match (impl_polarity, other_polarity) {
 288         (ty::ImplPolarity::Negative, ty::ImplPolarity::Positive) => {
 289             report_negative_positive_conflict(
 290                 tcx,
 291                 &overlap,
 292                 impl_def_id,
 293                 impl_def_id.to_def_id(),
 294                 overlap.with_impl,
 295                 sg,
 296             );
 297         }
 298
 299         (ty::ImplPolarity::Positive, ty::ImplPolarity::Negative) => {
 300             report_negative_positive_conflict(
 301                 tcx,
 302                 &overlap,
 303                 impl_def_id,
 304                 overlap.with_impl,
 305                 impl_def_id.to_def_id(),
 306                 sg,
 307             );
 308         }
 309
 310         _ => {
 311             report_conflicting_impls(tcx, overlap, impl_def_id, used_to_be_allowed, sg);
 312         }
 313     }
 314 }
 315
 316 fn report_negative_positive_conflict<'tcx>(
 317     tcx: TyCtxt<'tcx>,
 318     overlap: &OverlapError<'tcx>,
 319     local_impl_def_id: LocalDefId,
 320     negative_impl_def_id: DefId,
 321     positive_impl_def_id: DefId,
 322     sg: &mut specialization_graph::Graph,
 323 ) {
 324     let mut err = tcx.sess.create_err(NegativePositiveConflict {
 325         impl_span: tcx.def_span(local_impl_def_id),
 326         trait_desc: overlap.trait_ref,
 327         self_ty: overlap.self_ty,
 328         negative_impl_span: tcx.span_of_impl(negative_impl_def_id),
 329         positive_impl_span: tcx.span_of_impl(positive_impl_def_id),
 330     });
 331     sg.has_errored = Some(err.emit());
 332 }
 333
 334 fn report_conflicting_impls<'tcx>(
 335     tcx: TyCtxt<'tcx>,
 336     overlap: OverlapError<'tcx>,
 337     impl_def_id: LocalDefId,
 338     used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
 339     sg: &mut specialization_graph::Graph,
 340 ) {
 341     let impl_span = tcx.def_span(impl_def_id);
 342
 343     // Work to be done after we've built the DiagnosticBuilder. We have to define it
 344     // now because the struct_lint methods don't return back the DiagnosticBuilder
 345     // that's passed in.
 346     fn decorate<'tcx>(
 347         tcx: TyCtxt<'tcx>,
 348         overlap: &OverlapError<'tcx>,
 349         impl_span: Span,
 350         err: &mut Diagnostic,
 351     ) {
 352         match tcx.span_of_impl(overlap.with_impl) {
 353             Ok(span) => {
 354                 err.span_label(span, "first implementation here");
 355
 356                 err.span_label(
 357                     impl_span,
 358                     format!(
 359                         "conflicting implementation{}",
 360                         overlap.self_ty.map_or_else(String::new, |ty| format!(" for `{}`", ty))
 361                     ),
 362                 );
 363             }
 364             Err(cname) => {
 365                 let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
 366                     Some(s) => {
 367                         format!("conflicting implementation in crate `{}`:\n- {}", cname, s)
 368                     }
 369                     None => format!("conflicting implementation in crate `{}`", cname),
 370                 };
 371                 err.note(&msg);
 372             }
 373         }
 374
 375         for cause in &overlap.intercrate_ambiguity_causes {
 376             cause.add_intercrate_ambiguity_hint(err);
 377         }
 378
 379         if overlap.involves_placeholder {
 380             coherence::add_placeholder_note(err);
 381         }
 382     }
 383
 384     let msg = DelayDm(|| {
 385         format!(
 386             "conflicting implementations of trait `{}`{}{}",
 387             overlap.trait_ref.print_only_trait_path(),
 388             overlap.self_ty.map_or_else(String::new, |ty| format!(" for type `{ty}`")),
 389             match used_to_be_allowed {
 390                 Some(FutureCompatOverlapErrorKind::Issue33140) => ": (E0119)",
 391                 _ => "",
 392             }
 393         )
 394     });
 395
 396     match used_to_be_allowed {
 397         None => {
 398             let reported = if overlap.with_impl.is_local()
 399                 || tcx.orphan_check_impl(impl_def_id).is_ok()
 400             {
 401                 let mut err = tcx.sess.struct_span_err(impl_span, msg);
 402                 err.code(error_code!(E0119));
 403                 decorate(tcx, &overlap, impl_span, &mut err);
 404                 Some(err.emit())
 405             } else {
 406                 Some(tcx.sess.delay_span_bug(impl_span, "impl should have failed the orphan check"))
 407             };
 408             sg.has_errored = reported;
 409         }
 410         Some(kind) => {
 411             let lint = match kind {
 412                 FutureCompatOverlapErrorKind::Issue33140 => ORDER_DEPENDENT_TRAIT_OBJECTS,
 413                 FutureCompatOverlapErrorKind::LeakCheck => COHERENCE_LEAK_CHECK,
 414             };
 415             tcx.struct_span_lint_hir(
 416                 lint,
 417                 tcx.hir().local_def_id_to_hir_id(impl_def_id),
 418                 impl_span,
 419                 msg,
 420                 |err| {
 421                     decorate(tcx, &overlap, impl_span, err);
 422                     err
 423                 },
 424             );
 425         }
 426     };
 427 }
 428
 429 /// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a
 430 /// string.
 431 pub(crate) fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option<String> {
 432     use std::fmt::Write;
 433
 434     let trait_ref = tcx.impl_trait_ref(impl_def_id)?.subst_identity();
 435     let mut w = "impl".to_owned();
 436
 437     let substs = InternalSubsts::identity_for_item(tcx, impl_def_id);
 438
 439     // FIXME: Currently only handles ?Sized.
 440     //        Needs to support ?Move and ?DynSized when they are implemented.
 441     let mut types_without_default_bounds = FxIndexSet::default();
 442     let sized_trait = tcx.lang_items().sized_trait();
 443
 444     if !substs.is_empty() {
 445         types_without_default_bounds.extend(substs.types());
 446         w.push('<');
 447         w.push_str(
 448             &substs
 449                 .iter()
 450                 .map(|k| k.to_string())
 451                 .filter(|k| k != "'_")
 452                 .collect::<Vec<_>>()
 453                 .join(", "),
 454         );
 455         w.push('>');
 456     }
 457
 458     write!(w, " {} for {}", trait_ref.print_only_trait_path(), tcx.type_of(impl_def_id)).unwrap();
 459
 460     // The predicates will contain default bounds like `T: Sized`. We need to
 461     // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
 462     let predicates = tcx.predicates_of(impl_def_id).predicates;
 463     let mut pretty_predicates =
 464         Vec::with_capacity(predicates.len() + types_without_default_bounds.len());
 465
 466     for (mut p, _) in predicates {
 467         if let Some(poly_trait_ref) = p.to_opt_poly_trait_pred() {
 468             if Some(poly_trait_ref.def_id()) == sized_trait {
 469                 types_without_default_bounds.remove(&poly_trait_ref.self_ty().skip_binder());
 470                 continue;
 471             }
 472
 473             if ty::BoundConstness::ConstIfConst == poly_trait_ref.skip_binder().constness {
 474                 let new_trait_pred = poly_trait_ref.map_bound(|mut trait_pred| {
 475                     trait_pred.constness = ty::BoundConstness::NotConst;
 476                     trait_pred
 477                 });
 478
 479                 p = tcx.mk_predicate(
 480                     new_trait_pred.map_bound(|p| ty::PredicateKind::Clause(ty::Clause::Trait(p))),
 481                 )
 482             }
 483         }
 484         pretty_predicates.push(p.to_string());
 485     }
 486
 487     pretty_predicates
 488         .extend(types_without_default_bounds.iter().map(|ty| format!("{}: ?Sized", ty)));
 489
 490     if !pretty_predicates.is_empty() {
 491         write!(w, "\n  where {}", pretty_predicates.join(", ")).unwrap();
 492     }
 493
 494     w.push(';');
 495     Some(w)
 496 }