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