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