src/librustdoc/clean/auto_trait.rs

   1 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use rustc::ty::TypeFoldable;
  12 use std::fmt::Debug;
  13
  14 use super::*;
  15
  16 pub struct AutoTraitFinder<'a, 'tcx: 'a, 'rcx: 'a> {
  17     pub cx: &'a core::DocContext<'a, 'tcx, 'rcx>,
  18 }
  19
  20 impl<'a, 'tcx, 'rcx> AutoTraitFinder<'a, 'tcx, 'rcx> {
  21     pub fn get_with_def_id(&self, def_id: DefId) -> Vec<Item> {
  22         let ty = self.cx.tcx.type_of(def_id);
  23
  24         let def_ctor: fn(DefId) -> Def = match ty.sty {
  25             ty::TyAdt(adt, _) => match adt.adt_kind() {
  26                 AdtKind::Struct => Def::Struct,
  27                 AdtKind::Enum => Def::Enum,
  28                 AdtKind::Union => Def::Union,
  29             }
  30             _ => panic!("Unexpected type {:?}", def_id),
  31         };
  32
  33         self.get_auto_trait_impls(def_id, def_ctor, None)
  34     }
  35
  36     pub fn get_with_node_id(&self, id: ast::NodeId, name: String) -> Vec<Item> {
  37         let item = &self.cx.tcx.hir.expect_item(id).node;
  38         let did = self.cx.tcx.hir.local_def_id(id);
  39
  40         let def_ctor = match *item {
  41             hir::ItemStruct(_, _) => Def::Struct,
  42             hir::ItemUnion(_, _) => Def::Union,
  43             hir::ItemEnum(_, _) => Def::Enum,
  44             _ => panic!("Unexpected type {:?} {:?}", item, id),
  45         };
  46
  47         self.get_auto_trait_impls(did, def_ctor, Some(name))
  48     }
  49
  50     pub fn get_auto_trait_impls(
  51         &self,
  52         def_id: DefId,
  53         def_ctor: fn(DefId) -> Def,
  54         name: Option<String>,
  55     ) -> Vec<Item> {
  56         if self.cx
  57             .tcx
  58             .get_attrs(def_id)
  59             .lists("doc")
  60             .has_word("hidden")
  61         {
  62             debug!(
  63                 "get_auto_trait_impls(def_id={:?}, def_ctor={:?}): item has doc('hidden'), \
  64                  aborting",
  65                 def_id, def_ctor
  66             );
  67             return Vec::new();
  68         }
  69
  70         let tcx = self.cx.tcx;
  71         let generics = self.cx.tcx.generics_of(def_id);
  72
  73         debug!(
  74             "get_auto_trait_impls(def_id={:?}, def_ctor={:?}, generics={:?}",
  75             def_id, def_ctor, generics
  76         );
  77         let auto_traits: Vec<_> = self.cx
  78             .send_trait
  79             .and_then(|send_trait| {
  80                 self.get_auto_trait_impl_for(
  81                     def_id,
  82                     name.clone(),
  83                     generics.clone(),
  84                     def_ctor,
  85                     send_trait,
  86                 )
  87             })
  88             .into_iter()
  89             .chain(self.get_auto_trait_impl_for(
  90                 def_id,
  91                 name.clone(),
  92                 generics.clone(),
  93                 def_ctor,
  94                 tcx.require_lang_item(lang_items::SyncTraitLangItem),
  95             ).into_iter())
  96             .collect();
  97
  98         debug!(
  99             "get_auto_traits: type {:?} auto_traits {:?}",
 100             def_id, auto_traits
 101         );
 102         auto_traits
 103     }
 104
 105     fn get_auto_trait_impl_for(
 106         &self,
 107         def_id: DefId,
 108         name: Option<String>,
 109         generics: ty::Generics,
 110         def_ctor: fn(DefId) -> Def,
 111         trait_def_id: DefId,
 112     ) -> Option<Item> {
 113         if !self.cx
 114             .generated_synthetics
 115             .borrow_mut()
 116             .insert((def_id, trait_def_id))
 117         {
 118             debug!(
 119                 "get_auto_trait_impl_for(def_id={:?}, generics={:?}, def_ctor={:?}, \
 120                  trait_def_id={:?}): already generated, aborting",
 121                 def_id, generics, def_ctor, trait_def_id
 122             );
 123             return None;
 124         }
 125
 126         let result = self.find_auto_trait_generics(def_id, trait_def_id, &generics);
 127
 128         if result.is_auto() {
 129             let trait_ = hir::TraitRef {
 130                 path: get_path_for_type(self.cx.tcx, trait_def_id, hir::def::Def::Trait),
 131                 ref_id: ast::DUMMY_NODE_ID,
 132             };
 133
 134             let polarity;
 135
 136             let new_generics = match result {
 137                 AutoTraitResult::PositiveImpl(new_generics) => {
 138                     polarity = None;
 139                     new_generics
 140                 }
 141                 AutoTraitResult::NegativeImpl => {
 142                     polarity = Some(ImplPolarity::Negative);
 143
 144                     // For negative impls, we use the generic params, but *not* the predicates,
 145                     // from the original type. Otherwise, the displayed impl appears to be a
 146                     // conditional negative impl, when it's really unconditional.
 147                     //
 148                     // For example, consider the struct Foo<T: Copy>(*mut T). Using
 149                     // the original predicates in our impl would cause us to generate
 150                     // `impl !Send for Foo<T: Copy>`, which makes it appear that Foo
 151                     // implements Send where T is not copy.
 152                     //
 153                     // Instead, we generate `impl !Send for Foo<T>`, which better
 154                     // expresses the fact that `Foo<T>` never implements `Send`,
 155                     // regardless of the choice of `T`.
 156                     let real_generics = (&generics, &Default::default());
 157
 158                     // Clean the generics, but ignore the '?Sized' bounds generated
 159                     // by the `Clean` impl
 160                     let clean_generics = real_generics.clean(self.cx);
 161
 162                     Generics {
 163                         params: clean_generics.params,
 164                         where_predicates: Vec::new(),
 165                     }
 166                 }
 167                 _ => unreachable!(),
 168             };
 169
 170             let path = get_path_for_type(self.cx.tcx, def_id, def_ctor);
 171             let mut segments = path.segments.into_vec();
 172             let last = segments.pop().unwrap();
 173
 174             let real_name = name.map(|name| Symbol::intern(&name));
 175
 176             segments.push(hir::PathSegment::new(
 177                 real_name.unwrap_or(last.name),
 178                 self.generics_to_path_params(generics.clone()),
 179                 false,
 180             ));
 181
 182             let new_path = hir::Path {
 183                 span: path.span,
 184                 def: path.def,
 185                 segments: HirVec::from_vec(segments),
 186             };
 187
 188             let ty = hir::Ty {
 189                 id: ast::DUMMY_NODE_ID,
 190                 node: hir::Ty_::TyPath(hir::QPath::Resolved(None, P(new_path))),
 191                 span: DUMMY_SP,
 192                 hir_id: hir::DUMMY_HIR_ID,
 193             };
 194
 195             return Some(Item {
 196                 source: Span::empty(),
 197                 name: None,
 198                 attrs: Default::default(),
 199                 visibility: None,
 200                 def_id: self.next_def_id(def_id.krate),
 201                 stability: None,
 202                 deprecation: None,
 203                 inner: ImplItem(Impl {
 204                     unsafety: hir::Unsafety::Normal,
 205                     generics: new_generics,
 206                     provided_trait_methods: FxHashSet(),
 207                     trait_: Some(trait_.clean(self.cx)),
 208                     for_: ty.clean(self.cx),
 209                     items: Vec::new(),
 210                     polarity,
 211                     synthetic: true,
 212                 }),
 213             });
 214         }
 215         None
 216     }
 217
 218     fn generics_to_path_params(&self, generics: ty::Generics) -> hir::PathParameters {
 219         let lifetimes = HirVec::from_vec(
 220             generics
 221                 .regions
 222                 .iter()
 223                 .map(|p| {
 224                     let name = if p.name == "" {
 225                         hir::LifetimeName::Static
 226                     } else {
 227                         hir::LifetimeName::Name(p.name)
 228                     };
 229
 230                     hir::Lifetime {
 231                         id: ast::DUMMY_NODE_ID,
 232                         span: DUMMY_SP,
 233                         name,
 234                     }
 235                 })
 236                 .collect(),
 237         );
 238         let types = HirVec::from_vec(
 239             generics
 240                 .types
 241                 .iter()
 242                 .map(|p| P(self.ty_param_to_ty(p.clone())))
 243                 .collect(),
 244         );
 245
 246         hir::PathParameters {
 247             lifetimes: lifetimes,
 248             types: types,
 249             bindings: HirVec::new(),
 250             parenthesized: false,
 251         }
 252     }
 253
 254     fn ty_param_to_ty(&self, param: ty::TypeParameterDef) -> hir::Ty {
 255         debug!("ty_param_to_ty({:?}) {:?}", param, param.def_id);
 256         hir::Ty {
 257             id: ast::DUMMY_NODE_ID,
 258             node: hir::Ty_::TyPath(hir::QPath::Resolved(
 259                 None,
 260                 P(hir::Path {
 261                     span: DUMMY_SP,
 262                     def: Def::TyParam(param.def_id),
 263                     segments: HirVec::from_vec(vec![hir::PathSegment::from_name(param.name)]),
 264                 }),
 265             )),
 266             span: DUMMY_SP,
 267             hir_id: hir::DUMMY_HIR_ID,
 268         }
 269     }
 270
 271     fn find_auto_trait_generics(
 272         &self,
 273         did: DefId,
 274         trait_did: DefId,
 275         generics: &ty::Generics,
 276     ) -> AutoTraitResult {
 277         let tcx = self.cx.tcx;
 278         let ty = self.cx.tcx.type_of(did);
 279
 280         let orig_params = tcx.param_env(did);
 281
 282         let trait_ref = ty::TraitRef {
 283             def_id: trait_did,
 284             substs: tcx.mk_substs_trait(ty, &[]),
 285         };
 286
 287         let trait_pred = ty::Binder(trait_ref);
 288
 289         let bail_out = tcx.infer_ctxt().enter(|infcx| {
 290             let mut selcx = SelectionContext::with_negative(&infcx, true);
 291             let result = selcx.select(&Obligation::new(
 292                 ObligationCause::dummy(),
 293                 orig_params,
 294                 trait_pred.to_poly_trait_predicate(),
 295             ));
 296             match result {
 297                 Ok(Some(Vtable::VtableImpl(_))) => {
 298                     debug!(
 299                         "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): \
 300                          manual impl found, bailing out",
 301                         did, trait_did, generics
 302                     );
 303                     return true;
 304                 }
 305                 _ => return false,
 306             };
 307         });
 308
 309         // If an explicit impl exists, it always takes priority over an auto impl
 310         if bail_out {
 311             return AutoTraitResult::ExplicitImpl;
 312         }
 313
 314         return tcx.infer_ctxt().enter(|mut infcx| {
 315             let mut fresh_preds = FxHashSet();
 316
 317             // Due to the way projections are handled by SelectionContext, we need to run
 318             // evaluate_predicates twice: once on the original param env, and once on the result of
 319             // the first evaluate_predicates call.
 320             //
 321             // The problem is this: most of rustc, including SelectionContext and traits::project,
 322             // are designed to work with a concrete usage of a type (e.g. Vec<u8>
 323             // fn<T>() { Vec<T> }. This information will generally never change - given
 324             // the 'T' in fn<T>() { ... }, we'll never know anything else about 'T'.
 325             // If we're unable to prove that 'T' implements a particular trait, we're done -
 326             // there's nothing left to do but error out.
 327             //
 328             // However, synthesizing an auto trait impl works differently. Here, we start out with
 329             // a set of initial conditions - the ParamEnv of the struct/enum/union we're dealing
 330             // with - and progressively discover the conditions we need to fulfill for it to
 331             // implement a certain auto trait. This ends up breaking two assumptions made by trait
 332             // selection and projection:
 333             //
 334             // * We can always cache the result of a particular trait selection for the lifetime of
 335             // an InfCtxt
 336             // * Given a projection bound such as '<T as SomeTrait>::SomeItem = K', if 'T:
 337             // SomeTrait' doesn't hold, then we don't need to care about the 'SomeItem = K'
 338             //
 339             // We fix the first assumption by manually clearing out all of the InferCtxt's caches
 340             // in between calls to SelectionContext.select. This allows us to keep all of the
 341             // intermediate types we create bound to the 'tcx lifetime, rather than needing to lift
 342             // them between calls.
 343             //
 344             // We fix the second assumption by reprocessing the result of our first call to
 345             // evaluate_predicates. Using the example of '<T as SomeTrait>::SomeItem = K', our first
 346             // pass will pick up 'T: SomeTrait', but not 'SomeItem = K'. On our second pass,
 347             // traits::project will see that 'T: SomeTrait' is in our ParamEnv, allowing
 348             // SelectionContext to return it back to us.
 349
 350             let (new_env, user_env) = match self.evaluate_predicates(
 351                 &mut infcx,
 352                 did,
 353                 trait_did,
 354                 ty,
 355                 orig_params.clone(),
 356                 orig_params,
 357                 &mut fresh_preds,
 358                 false,
 359             ) {
 360                 Some(e) => e,
 361                 None => return AutoTraitResult::NegativeImpl,
 362             };
 363
 364             let (full_env, full_user_env) = self.evaluate_predicates(
 365                 &mut infcx,
 366                 did,
 367                 trait_did,
 368                 ty,
 369                 new_env.clone(),
 370                 user_env,
 371                 &mut fresh_preds,
 372                 true,
 373             ).unwrap_or_else(|| {
 374                 panic!(
 375                     "Failed to fully process: {:?} {:?} {:?}",
 376                     ty, trait_did, orig_params
 377                 )
 378             });
 379
 380             debug!(
 381                 "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): fulfilling \
 382                  with {:?}",
 383                 did, trait_did, generics, full_env
 384             );
 385             infcx.clear_caches();
 386
 387             // At this point, we already have all of the bounds we need. FulfillmentContext is used
 388             // to store all of the necessary region/lifetime bounds in the InferContext, as well as
 389             // an additional sanity check.
 390             let mut fulfill = FulfillmentContext::new();
 391             fulfill.register_bound(
 392                 &infcx,
 393                 full_env,
 394                 ty,
 395                 trait_did,
 396                 ObligationCause::misc(DUMMY_SP, ast::DUMMY_NODE_ID),
 397             );
 398             fulfill.select_all_or_error(&infcx).unwrap_or_else(|e| {
 399                 panic!(
 400                     "Unable to fulfill trait {:?} for '{:?}': {:?}",
 401                     trait_did, ty, e
 402                 )
 403             });
 404
 405             let names_map: FxHashMap<String, Lifetime> = generics
 406                 .regions
 407                 .iter()
 408                 .map(|l| (l.name.as_str().to_string(), l.clean(self.cx)))
 409                 .collect();
 410
 411             let body_ids: FxHashSet<_> = infcx
 412                 .region_obligations
 413                 .borrow()
 414                 .iter()
 415                 .map(|&(id, _)| id)
 416                 .collect();
 417
 418             for id in body_ids {
 419                 infcx.process_registered_region_obligations(&[], None, full_env.clone(), id);
 420             }
 421
 422             let region_data = infcx
 423                 .borrow_region_constraints()
 424                 .region_constraint_data()
 425                 .clone();
 426
 427             let lifetime_predicates = self.handle_lifetimes(&region_data, &names_map);
 428             let vid_to_region = self.map_vid_to_region(&region_data);
 429
 430             debug!(
 431                 "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): computed \
 432                  lifetime information '{:?}' '{:?}'",
 433                 did, trait_did, generics, lifetime_predicates, vid_to_region
 434             );
 435
 436             let new_generics = self.param_env_to_generics(
 437                 infcx.tcx,
 438                 did,
 439                 full_user_env,
 440                 generics.clone(),
 441                 lifetime_predicates,
 442                 vid_to_region,
 443             );
 444             debug!(
 445                 "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): finished with \
 446                  {:?}",
 447                 did, trait_did, generics, new_generics
 448             );
 449             return AutoTraitResult::PositiveImpl(new_generics);
 450         });
 451     }
 452
 453     fn clean_pred<'c, 'd, 'cx>(
 454         &self,
 455         infcx: &InferCtxt<'c, 'd, 'cx>,
 456         p: ty::Predicate<'cx>,
 457     ) -> ty::Predicate<'cx> {
 458         infcx.freshen(p)
 459     }
 460
 461     fn evaluate_nested_obligations<'b, 'c, 'd, 'cx,
 462                                     T: Iterator<Item = Obligation<'cx, ty::Predicate<'cx>>>>(
 463         &self,
 464         ty: ty::Ty,
 465         nested: T,
 466         computed_preds: &'b mut FxHashSet<ty::Predicate<'cx>>,
 467         fresh_preds: &'b mut FxHashSet<ty::Predicate<'cx>>,
 468         predicates: &'b mut VecDeque<ty::PolyTraitPredicate<'cx>>,
 469         select: &mut traits::SelectionContext<'c, 'd, 'cx>,
 470         only_projections: bool,
 471     ) -> bool {
 472         let dummy_cause = ObligationCause::misc(DUMMY_SP, ast::DUMMY_NODE_ID);
 473
 474         for (obligation, predicate) in nested
 475             .filter(|o| o.recursion_depth == 1)
 476             .map(|o| (o.clone(), o.predicate.clone()))
 477         {
 478             let is_new_pred =
 479                 fresh_preds.insert(self.clean_pred(select.infcx(), predicate.clone()));
 480
 481             match &predicate {
 482                 &ty::Predicate::Trait(ref p) => {
 483                     let substs = &p.skip_binder().trait_ref.substs;
 484
 485                     if self.is_of_param(substs) && !only_projections && is_new_pred {
 486                         computed_preds.insert(predicate);
 487                     }
 488                     predicates.push_back(p.clone());
 489                 }
 490                 &ty::Predicate::Projection(p) => {
 491                     // If the projection isn't all type vars, then
 492                     // we don't want to add it as a bound
 493                     if self.is_of_param(p.skip_binder().projection_ty.substs) && is_new_pred {
 494                         computed_preds.insert(predicate);
 495                     } else {
 496                         match traits::poly_project_and_unify_type(
 497                             select,
 498                             &obligation.with(p.clone()),
 499                         ) {
 500                             Err(e) => {
 501                                 debug!(
 502                                     "evaluate_nested_obligations: Unable to unify predicate \
 503                                      '{:?}' '{:?}', bailing out",
 504                                     ty, e
 505                                 );
 506                                 return false;
 507                             }
 508                             Ok(Some(v)) => {
 509                                 if !self.evaluate_nested_obligations(
 510                                     ty,
 511                                     v.clone().iter().cloned(),
 512                                     computed_preds,
 513                                     fresh_preds,
 514                                     predicates,
 515                                     select,
 516                                     only_projections,
 517                                 ) {
 518                                     return false;
 519                                 }
 520                             }
 521                             Ok(None) => {
 522                                 panic!("Unexpected result when selecting {:?} {:?}", ty, obligation)
 523                             }
 524                         }
 525                     }
 526                 }
 527                 &ty::Predicate::RegionOutlives(ref binder) => {
 528                     if let Err(_) = select
 529                         .infcx()
 530                         .region_outlives_predicate(&dummy_cause, binder)
 531                     {
 532                         return false;
 533                     }
 534                 }
 535                 &ty::Predicate::TypeOutlives(ref binder) => {
 536                     match (
 537                         binder.no_late_bound_regions(),
 538                         binder.map_bound_ref(|pred| pred.0).no_late_bound_regions(),
 539                     ) {
 540                         (None, Some(t_a)) => {
 541                             select.infcx().register_region_obligation(
 542                                 ast::DUMMY_NODE_ID,
 543                                 RegionObligation {
 544                                     sup_type: t_a,
 545                                     sub_region: select.infcx().tcx.types.re_static,
 546                                     cause: dummy_cause.clone(),
 547                                 },
 548                             );
 549                         }
 550                         (Some(ty::OutlivesPredicate(t_a, r_b)), _) => {
 551                             select.infcx().register_region_obligation(
 552                                 ast::DUMMY_NODE_ID,
 553                                 RegionObligation {
 554                                     sup_type: t_a,
 555                                     sub_region: r_b,
 556                                     cause: dummy_cause.clone(),
 557                                 },
 558                             );
 559                         }
 560                         _ => {}
 561                     };
 562                 }
 563                 _ => panic!("Unexpected predicate {:?} {:?}", ty, predicate),
 564             };
 565         }
 566         return true;
 567     }
 568
 569     // The core logic responsible for computing the bounds for our synthesized impl.
 570     //
 571     // To calculate the bounds, we call SelectionContext.select in a loop. Like FulfillmentContext,
 572     // we recursively select the nested obligations of predicates we encounter. However, whenver we
 573     // encounter an UnimplementedError involving a type parameter, we add it to our ParamEnv. Since
 574     // our goal is to determine when a particular type implements an auto trait, Unimplemented
 575     // errors tell us what conditions need to be met.
 576     //
 577     // This method ends up working somewhat similary to FulfillmentContext, but with a few key
 578     // differences. FulfillmentContext works under the assumption that it's dealing with concrete
 579     // user code. According, it considers all possible ways that a Predicate could be met - which
 580     // isn't always what we want for a synthesized impl. For example, given the predicate 'T:
 581     // Iterator', FulfillmentContext can end up reporting an Unimplemented error for T:
 582     // IntoIterator - since there's an implementation of Iteratpr where T: IntoIterator,
 583     // FulfillmentContext will drive SelectionContext to consider that impl before giving up. If we
 584     // were to rely on FulfillmentContext's decision, we might end up synthesizing an impl like
 585     // this:
 586     // 'impl<T> Send for Foo<T> where T: IntoIterator'
 587     //
 588     // While it might be technically true that Foo implements Send where T: IntoIterator,
 589     // the bound is overly restrictive - it's really only necessary that T: Iterator.
 590     //
 591     // For this reason, evaluate_predicates handles predicates with type variables specially. When
 592     // we encounter an Unimplemented error for a bound such as 'T: Iterator', we immediately add it
 593     // to our ParamEnv, and add it to our stack for recursive evaluation. When we later select it,
 594     // we'll pick up any nested bounds, without ever inferring that 'T: IntoIterator' needs to
 595     // hold.
 596     //
 597     // One additonal consideration is supertrait bounds. Normally, a ParamEnv is only ever
 598     // consutrcted once for a given type. As part of the construction process, the ParamEnv will
 599     // have any supertrait bounds normalized - e.g. if we have a type 'struct Foo<T: Copy>', the
 600     // ParamEnv will contain 'T: Copy' and 'T: Clone', since 'Copy: Clone'. When we construct our
 601     // own ParamEnv, we need to do this outselves, through traits::elaborate_predicates, or else
 602     // SelectionContext will choke on the missing predicates. However, this should never show up in
 603     // the final synthesized generics: we don't want our generated docs page to contain something
 604     // like 'T: Copy + Clone', as that's redundant. Therefore, we keep track of a separate
 605     // 'user_env', which only holds the predicates that will actually be displayed to the user.
 606     fn evaluate_predicates<'b, 'gcx, 'c>(
 607         &self,
 608         infcx: &mut InferCtxt<'b, 'tcx, 'c>,
 609         ty_did: DefId,
 610         trait_did: DefId,
 611         ty: ty::Ty<'c>,
 612         param_env: ty::ParamEnv<'c>,
 613         user_env: ty::ParamEnv<'c>,
 614         fresh_preds: &mut FxHashSet<ty::Predicate<'c>>,
 615         only_projections: bool,
 616     ) -> Option<(ty::ParamEnv<'c>, ty::ParamEnv<'c>)> {
 617         let tcx = infcx.tcx;
 618
 619         let mut select = traits::SelectionContext::new(&infcx);
 620
 621         let mut already_visited = FxHashSet();
 622         let mut predicates = VecDeque::new();
 623         predicates.push_back(ty::Binder(ty::TraitPredicate {
 624             trait_ref: ty::TraitRef {
 625                 def_id: trait_did,
 626                 substs: infcx.tcx.mk_substs_trait(ty, &[]),
 627             },
 628         }));
 629
 630         let mut computed_preds: FxHashSet<_> = param_env.caller_bounds.iter().cloned().collect();
 631         let mut user_computed_preds: FxHashSet<_> =
 632             user_env.caller_bounds.iter().cloned().collect();
 633
 634         let mut new_env = param_env.clone();
 635         let dummy_cause = ObligationCause::misc(DUMMY_SP, ast::DUMMY_NODE_ID);
 636
 637         while let Some(pred) = predicates.pop_front() {
 638             infcx.clear_caches();
 639
 640             if !already_visited.insert(pred.clone()) {
 641                 continue;
 642             }
 643
 644             let result = select.select(&Obligation::new(dummy_cause.clone(), new_env, pred));
 645
 646             match &result {
 647                 &Ok(Some(ref vtable)) => {
 648                     let obligations = vtable.clone().nested_obligations().into_iter();
 649
 650                     if !self.evaluate_nested_obligations(
 651                         ty,
 652                         obligations,
 653                         &mut user_computed_preds,
 654                         fresh_preds,
 655                         &mut predicates,
 656                         &mut select,
 657                         only_projections,
 658                     ) {
 659                         return None;
 660                     }
 661                 }
 662                 &Ok(None) => {}
 663                 &Err(SelectionError::Unimplemented) => {
 664                     if self.is_of_param(pred.skip_binder().trait_ref.substs) {
 665                         already_visited.remove(&pred);
 666                         user_computed_preds.insert(ty::Predicate::Trait(pred.clone()));
 667                         predicates.push_back(pred);
 668                     } else {
 669                         debug!(
 670                             "evaluate_nested_obligations: Unimplemented found, bailing: {:?} {:?} \
 671                              {:?}",
 672                             ty,
 673                             pred,
 674                             pred.skip_binder().trait_ref.substs
 675                         );
 676                         return None;
 677                     }
 678                 }
 679                 _ => panic!("Unexpected error for '{:?}': {:?}", ty, result),
 680             };
 681
 682             computed_preds.extend(user_computed_preds.iter().cloned());
 683             let normalized_preds =
 684                 traits::elaborate_predicates(tcx, computed_preds.clone().into_iter().collect());
 685             new_env = ty::ParamEnv::new(
 686                 tcx.mk_predicates(normalized_preds),
 687                 param_env.reveal,
 688             );
 689         }
 690
 691         let final_user_env = ty::ParamEnv::new(
 692             tcx.mk_predicates(user_computed_preds.into_iter()),
 693             user_env.reveal,
 694         );
 695         debug!(
 696             "evaluate_nested_obligations(ty_did={:?}, trait_did={:?}): succeeded with '{:?}' \
 697              '{:?}'",
 698             ty_did, trait_did, new_env, final_user_env
 699         );
 700
 701         return Some((new_env, final_user_env));
 702     }
 703
 704     fn is_of_param(&self, substs: &Substs) -> bool {
 705         if substs.is_noop() {
 706             return false;
 707         }
 708
 709         return match substs.type_at(0).sty {
 710             ty::TyParam(_) => true,
 711             ty::TyProjection(p) => self.is_of_param(p.substs),
 712             _ => false,
 713         };
 714     }
 715
 716     fn get_lifetime(&self, region: Region, names_map: &FxHashMap<String, Lifetime>) -> Lifetime {
 717         self.region_name(region)
 718             .map(|name| {
 719                 names_map.get(&name).unwrap_or_else(|| {
 720                     panic!("Missing lifetime with name {:?} for {:?}", name, region)
 721                 })
 722             })
 723             .unwrap_or(&Lifetime::statik())
 724             .clone()
 725     }
 726
 727     fn region_name(&self, region: Region) -> Option<String> {
 728         match region {
 729             &ty::ReEarlyBound(r) => Some(r.name.as_str().to_string()),
 730             _ => None,
 731         }
 732     }
 733
 734     // This is very similar to handle_lifetimes. However, instead of matching ty::Region's
 735     // to each other, we match ty::RegionVid's to ty::Region's
 736     fn map_vid_to_region<'cx>(
 737         &self,
 738         regions: &RegionConstraintData<'cx>,
 739     ) -> FxHashMap<ty::RegionVid, ty::Region<'cx>> {
 740         let mut vid_map: FxHashMap<RegionTarget<'cx>, RegionDeps<'cx>> = FxHashMap();
 741         let mut finished_map = FxHashMap();
 742
 743         for constraint in regions.constraints.keys() {
 744             match constraint {
 745                 &Constraint::VarSubVar(r1, r2) => {
 746                     {
 747                         let deps1 = vid_map
 748                             .entry(RegionTarget::RegionVid(r1))
 749                             .or_insert_with(|| Default::default());
 750                         deps1.larger.insert(RegionTarget::RegionVid(r2));
 751                     }
 752
 753                     let deps2 = vid_map
 754                         .entry(RegionTarget::RegionVid(r2))
 755                         .or_insert_with(|| Default::default());
 756                     deps2.smaller.insert(RegionTarget::RegionVid(r1));
 757                 }
 758                 &Constraint::RegSubVar(region, vid) => {
 759                     {
 760                         let deps1 = vid_map
 761                             .entry(RegionTarget::Region(region))
 762                             .or_insert_with(|| Default::default());
 763                         deps1.larger.insert(RegionTarget::RegionVid(vid));
 764                     }
 765
 766                     let deps2 = vid_map
 767                         .entry(RegionTarget::RegionVid(vid))
 768                         .or_insert_with(|| Default::default());
 769                     deps2.smaller.insert(RegionTarget::Region(region));
 770                 }
 771                 &Constraint::VarSubReg(vid, region) => {
 772                     finished_map.insert(vid, region);
 773                 }
 774                 &Constraint::RegSubReg(r1, r2) => {
 775                     {
 776                         let deps1 = vid_map
 777                             .entry(RegionTarget::Region(r1))
 778                             .or_insert_with(|| Default::default());
 779                         deps1.larger.insert(RegionTarget::Region(r2));
 780                     }
 781
 782                     let deps2 = vid_map
 783                         .entry(RegionTarget::Region(r2))
 784                         .or_insert_with(|| Default::default());
 785                     deps2.smaller.insert(RegionTarget::Region(r1));
 786                 }
 787             }
 788         }
 789
 790         while !vid_map.is_empty() {
 791             let target = vid_map.keys().next().expect("Keys somehow empty").clone();
 792             let deps = vid_map.remove(&target).expect("Entry somehow missing");
 793
 794             for smaller in deps.smaller.iter() {
 795                 for larger in deps.larger.iter() {
 796                     match (smaller, larger) {
 797                         (&RegionTarget::Region(_), &RegionTarget::Region(_)) => {
 798                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 799                                 let smaller_deps = v.into_mut();
 800                                 smaller_deps.larger.insert(*larger);
 801                                 smaller_deps.larger.remove(&target);
 802                             }
 803
 804                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 805                                 let larger_deps = v.into_mut();
 806                                 larger_deps.smaller.insert(*smaller);
 807                                 larger_deps.smaller.remove(&target);
 808                             }
 809                         }
 810                         (&RegionTarget::RegionVid(v1), &RegionTarget::Region(r1)) => {
 811                             finished_map.insert(v1, r1);
 812                         }
 813                         (&RegionTarget::Region(_), &RegionTarget::RegionVid(_)) => {
 814                             // Do nothing - we don't care about regions that are smaller than vids
 815                         }
 816                         (&RegionTarget::RegionVid(_), &RegionTarget::RegionVid(_)) => {
 817                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 818                                 let smaller_deps = v.into_mut();
 819                                 smaller_deps.larger.insert(*larger);
 820                                 smaller_deps.larger.remove(&target);
 821                             }
 822
 823                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 824                                 let larger_deps = v.into_mut();
 825                                 larger_deps.smaller.insert(*smaller);
 826                                 larger_deps.smaller.remove(&target);
 827                             }
 828                         }
 829                     }
 830                 }
 831             }
 832         }
 833         finished_map
 834     }
 835
 836     // This method calculates two things: Lifetime constraints of the form 'a: 'b,
 837     // and region constraints of the form ReVar: 'a
 838     //
 839     // This is essentially a simplified version of lexical_region_resolve. However,
 840     // handle_lifetimes determines what *needs be* true in order for an impl to hold.
 841     // lexical_region_resolve, along with much of the rest of the compiler, is concerned
 842     // with determining if a given set up constraints/predicates *are* met, given some
 843     // starting conditions (e.g. user-provided code). For this reason, it's easier
 844     // to perform the calculations we need on our own, rather than trying to make
 845     // existing inference/solver code do what we want.
 846     fn handle_lifetimes<'cx>(
 847         &self,
 848         regions: &RegionConstraintData<'cx>,
 849         names_map: &FxHashMap<String, Lifetime>,
 850     ) -> Vec<WherePredicate> {
 851         // Our goal is to 'flatten' the list of constraints by eliminating
 852         // all intermediate RegionVids. At the end, all constraints should
 853         // be between Regions (aka region variables). This gives us the information
 854         // we need to create the Generics.
 855         let mut finished = FxHashMap();
 856
 857         let mut vid_map: FxHashMap<RegionTarget, RegionDeps> = FxHashMap();
 858
 859         // Flattening is done in two parts. First, we insert all of the constraints
 860         // into a map. Each RegionTarget (either a RegionVid or a Region) maps
 861         // to its smaller and larger regions. Note that 'larger' regions correspond
 862         // to sub-regions in Rust code (e.g. in 'a: 'b, 'a is the larger region).
 863         for constraint in regions.constraints.keys() {
 864             match constraint {
 865                 &Constraint::VarSubVar(r1, r2) => {
 866                     {
 867                         let deps1 = vid_map
 868                             .entry(RegionTarget::RegionVid(r1))
 869                             .or_insert_with(|| Default::default());
 870                         deps1.larger.insert(RegionTarget::RegionVid(r2));
 871                     }
 872
 873                     let deps2 = vid_map
 874                         .entry(RegionTarget::RegionVid(r2))
 875                         .or_insert_with(|| Default::default());
 876                     deps2.smaller.insert(RegionTarget::RegionVid(r1));
 877                 }
 878                 &Constraint::RegSubVar(region, vid) => {
 879                     let deps = vid_map
 880                         .entry(RegionTarget::RegionVid(vid))
 881                         .or_insert_with(|| Default::default());
 882                     deps.smaller.insert(RegionTarget::Region(region));
 883                 }
 884                 &Constraint::VarSubReg(vid, region) => {
 885                     let deps = vid_map
 886                         .entry(RegionTarget::RegionVid(vid))
 887                         .or_insert_with(|| Default::default());
 888                     deps.larger.insert(RegionTarget::Region(region));
 889                 }
 890                 &Constraint::RegSubReg(r1, r2) => {
 891                     // The constraint is already in the form that we want, so we're done with it
 892                     // Desired order is 'larger, smaller', so flip then
 893                     if self.region_name(r1) != self.region_name(r2) {
 894                         finished
 895                             .entry(self.region_name(r2).unwrap())
 896                             .or_insert_with(|| Vec::new())
 897                             .push(r1);
 898                     }
 899                 }
 900             }
 901         }
 902
 903         // Here, we 'flatten' the map one element at a time.
 904         // All of the element's sub and super regions are connected
 905         // to each other. For example, if we have a graph that looks like this:
 906         //
 907         // (A, B) - C - (D, E)
 908         // Where (A, B) are subregions, and (D,E) are super-regions
 909         //
 910         // then after deleting 'C', the graph will look like this:
 911         //  ... - A - (D, E ...)
 912         //  ... - B - (D, E, ...)
 913         //  (A, B, ...) - D - ...
 914         //  (A, B, ...) - E - ...
 915         //
 916         //  where '...' signifies the existing sub and super regions of an entry
 917         //  When two adjacent ty::Regions are encountered, we've computed a final
 918         //  constraint, and add it to our list. Since we make sure to never re-add
 919         //  deleted items, this process will always finish.
 920         while !vid_map.is_empty() {
 921             let target = vid_map.keys().next().expect("Keys somehow empty").clone();
 922             let deps = vid_map.remove(&target).expect("Entry somehow missing");
 923
 924             for smaller in deps.smaller.iter() {
 925                 for larger in deps.larger.iter() {
 926                     match (smaller, larger) {
 927                         (&RegionTarget::Region(r1), &RegionTarget::Region(r2)) => {
 928                             if self.region_name(r1) != self.region_name(r2) {
 929                                 finished
 930                                     .entry(self.region_name(r2).unwrap())
 931                                     .or_insert_with(|| Vec::new())
 932                                     .push(r1) // Larger, smaller
 933                             }
 934                         }
 935                         (&RegionTarget::RegionVid(_), &RegionTarget::Region(_)) => {
 936                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 937                                 let smaller_deps = v.into_mut();
 938                                 smaller_deps.larger.insert(*larger);
 939                                 smaller_deps.larger.remove(&target);
 940                             }
 941                         }
 942                         (&RegionTarget::Region(_), &RegionTarget::RegionVid(_)) => {
 943                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 944                                 let deps = v.into_mut();
 945                                 deps.smaller.insert(*smaller);
 946                                 deps.smaller.remove(&target);
 947                             }
 948                         }
 949                         (&RegionTarget::RegionVid(_), &RegionTarget::RegionVid(_)) => {
 950                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 951                                 let smaller_deps = v.into_mut();
 952                                 smaller_deps.larger.insert(*larger);
 953                                 smaller_deps.larger.remove(&target);
 954                             }
 955
 956                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 957                                 let larger_deps = v.into_mut();
 958                                 larger_deps.smaller.insert(*smaller);
 959                                 larger_deps.smaller.remove(&target);
 960                             }
 961                         }
 962                     }
 963                 }
 964             }
 965         }
 966
 967         let lifetime_predicates = names_map
 968             .iter()
 969             .flat_map(|(name, lifetime)| {
 970                 let empty = Vec::new();
 971                 let bounds: FxHashSet<Lifetime> = finished
 972                     .get(name)
 973                     .unwrap_or(&empty)
 974                     .iter()
 975                     .map(|region| self.get_lifetime(region, names_map))
 976                     .collect();
 977
 978                 if bounds.is_empty() {
 979                     return None;
 980                 }
 981                 Some(WherePredicate::RegionPredicate {
 982                     lifetime: lifetime.clone(),
 983                     bounds: bounds.into_iter().collect(),
 984                 })
 985             })
 986             .collect();
 987
 988         lifetime_predicates
 989     }
 990
 991     fn extract_for_generics<'b, 'c, 'd>(
 992         &self,
 993         tcx: TyCtxt<'b, 'c, 'd>,
 994         pred: ty::Predicate<'d>,
 995     ) -> FxHashSet<GenericParam> {
 996         pred.walk_tys()
 997             .flat_map(|t| {
 998                 let mut regions = FxHashSet();
 999                 tcx.collect_regions(&t, &mut regions);
1000
1001                 regions.into_iter().flat_map(|r| {
1002                     match r {
1003                         // We only care about late bound regions, as we need to add them
1004                         // to the 'for<>' section
1005                         &ty::ReLateBound(_, ty::BoundRegion::BrNamed(_, name)) => {
1006                             Some(GenericParam::Lifetime(Lifetime(name.as_str().to_string())))
1007                         }
1008                         &ty::ReVar(_) | &ty::ReEarlyBound(_) => None,
1009                         _ => panic!("Unexpected region type {:?}", r),
1010                     }
1011                 })
1012             })
1013             .collect()
1014     }
1015
1016     fn make_final_bounds<'b, 'c, 'cx>(
1017         &self,
1018         ty_to_bounds: FxHashMap<Type, FxHashSet<TyParamBound>>,
1019         ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)>,
1020         lifetime_to_bounds: FxHashMap<Lifetime, FxHashSet<Lifetime>>,
1021     ) -> Vec<WherePredicate> {
1022         ty_to_bounds
1023             .into_iter()
1024             .flat_map(|(ty, mut bounds)| {
1025                 if let Some(data) = ty_to_fn.get(&ty) {
1026                     let (poly_trait, output) =
1027                         (data.0.as_ref().unwrap().clone(), data.1.as_ref().cloned());
1028                     let new_ty = match &poly_trait.trait_ {
1029                         &Type::ResolvedPath {
1030                             ref path,
1031                             ref typarams,
1032                             ref did,
1033                             ref is_generic,
1034                         } => {
1035                             let mut new_path = path.clone();
1036                             let last_segment = new_path.segments.pop().unwrap();
1037
1038                             let (old_input, old_output) = match last_segment.params {
1039                                 PathParameters::AngleBracketed { types, .. } => (types, None),
1040                                 PathParameters::Parenthesized { inputs, output, .. } => {
1041                                     (inputs, output)
1042                                 }
1043                             };
1044
1045                             if old_output.is_some() && old_output != output {
1046                                 panic!(
1047                                     "Output mismatch for {:?} {:?} {:?}",
1048                                     ty, old_output, data.1
1049                                 );
1050                             }
1051
1052                             let new_params = PathParameters::Parenthesized {
1053                                 inputs: old_input,
1054                                 output,
1055                             };
1056
1057                             new_path.segments.push(PathSegment {
1058                                 name: last_segment.name,
1059                                 params: new_params,
1060                             });
1061
1062                             Type::ResolvedPath {
1063                                 path: new_path,
1064                                 typarams: typarams.clone(),
1065                                 did: did.clone(),
1066                                 is_generic: *is_generic,
1067                             }
1068                         }
1069                         _ => panic!("Unexpected data: {:?}, {:?}", ty, data),
1070                     };
1071                     bounds.insert(TyParamBound::TraitBound(
1072                         PolyTrait {
1073                             trait_: new_ty,
1074                             generic_params: poly_trait.generic_params,
1075                         },
1076                         hir::TraitBoundModifier::None,
1077                     ));
1078                 }
1079                 if bounds.is_empty() {
1080                     return None;
1081                 }
1082
1083                 let mut bounds_vec = bounds.into_iter().collect();
1084                 self.sort_where_bounds(&mut bounds_vec);
1085
1086                 Some(WherePredicate::BoundPredicate {
1087                     ty,
1088                     bounds: bounds_vec,
1089                 })
1090             })
1091             .chain(
1092                 lifetime_to_bounds
1093                     .into_iter()
1094                     .filter(|&(_, ref bounds)| !bounds.is_empty())
1095                     .map(|(lifetime, bounds)| {
1096                         let mut bounds_vec = bounds.into_iter().collect();
1097                         self.sort_where_lifetimes(&mut bounds_vec);
1098                         WherePredicate::RegionPredicate {
1099                             lifetime,
1100                             bounds: bounds_vec,
1101                         }
1102                     }),
1103             )
1104             .collect()
1105     }
1106
1107     // Converts the calculated ParamEnv and lifetime information to a clean::Generics, suitable for
1108     // display on the docs page. Cleaning the Predicates produces sub-optimal WherePredicate's,
1109     // so we fix them up:
1110     //
1111     // * Multiple bounds for the same type are coalesced into one: e.g. 'T: Copy', 'T: Debug'
1112     // becomes 'T: Copy + Debug'
1113     // * Fn bounds are handled specially - instead of leaving it as 'T: Fn(), <T as Fn::Output> =
1114     // K', we use the dedicated syntax 'T: Fn() -> K'
1115     // * We explcitly add a '?Sized' bound if we didn't find any 'Sized' predicates for a type
1116     fn param_env_to_generics<'b, 'c, 'cx>(
1117         &self,
1118         tcx: TyCtxt<'b, 'c, 'cx>,
1119         did: DefId,
1120         param_env: ty::ParamEnv<'cx>,
1121         type_generics: ty::Generics,
1122         mut existing_predicates: Vec<WherePredicate>,
1123         vid_to_region: FxHashMap<ty::RegionVid, ty::Region<'cx>>,
1124     ) -> Generics {
1125         debug!(
1126             "param_env_to_generics(did={:?}, param_env={:?}, type_generics={:?}, \
1127              existing_predicates={:?})",
1128             did, param_env, type_generics, existing_predicates
1129         );
1130
1131         // The `Sized` trait must be handled specially, since we only only display it when
1132         // it is *not* required (i.e. '?Sized')
1133         let sized_trait = self.cx
1134             .tcx
1135             .require_lang_item(lang_items::SizedTraitLangItem);
1136
1137         let mut replacer = RegionReplacer {
1138             vid_to_region: &vid_to_region,
1139             tcx,
1140         };
1141
1142         let orig_bounds: FxHashSet<_> = self.cx.tcx.param_env(did).caller_bounds.iter().collect();
1143         let clean_where_predicates = param_env
1144             .caller_bounds
1145             .iter()
1146             .filter(|p| {
1147                 !orig_bounds.contains(p) || match p {
1148                     &&ty::Predicate::Trait(pred) => pred.def_id() == sized_trait,
1149                     _ => false,
1150                 }
1151             })
1152             .map(|p| {
1153                 let replaced = p.fold_with(&mut replacer);
1154                 (replaced.clone(), replaced.clean(self.cx))
1155             });
1156
1157         let full_generics = (&type_generics, &tcx.predicates_of(did));
1158         let Generics {
1159             params: mut generic_params,
1160             ..
1161         } = full_generics.clean(self.cx);
1162
1163         let mut has_sized = FxHashSet();
1164         let mut ty_to_bounds = FxHashMap();
1165         let mut lifetime_to_bounds = FxHashMap();
1166         let mut ty_to_traits: FxHashMap<Type, FxHashSet<Type>> = FxHashMap();
1167
1168         let mut ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)> = FxHashMap();
1169
1170         for (orig_p, p) in clean_where_predicates {
1171             match p {
1172                 WherePredicate::BoundPredicate { ty, mut bounds } => {
1173                     // Writing a projection trait bound of the form
1174                     // <T as Trait>::Name : ?Sized
1175                     // is illegal, because ?Sized bounds can only
1176                     // be written in the (here, nonexistant) definition
1177                     // of the type.
1178                     // Therefore, we make sure that we never add a ?Sized
1179                     // bound for projections
1180                     match &ty {
1181                         &Type::QPath { .. } => {
1182                             has_sized.insert(ty.clone());
1183                         }
1184                         _ => {}
1185                     }
1186
1187                     if bounds.is_empty() {
1188                         continue;
1189                     }
1190
1191                     let mut for_generics = self.extract_for_generics(tcx, orig_p.clone());
1192
1193                     assert!(bounds.len() == 1);
1194                     let mut b = bounds.pop().unwrap();
1195
1196                     if b.is_sized_bound(self.cx) {
1197                         has_sized.insert(ty.clone());
1198                     } else if !b.get_trait_type()
1199                         .and_then(|t| {
1200                             ty_to_traits
1201                                 .get(&ty)
1202                                 .map(|bounds| bounds.contains(&strip_type(t.clone())))
1203                         })
1204                         .unwrap_or(false)
1205                     {
1206                         // If we've already added a projection bound for the same type, don't add
1207                         // this, as it would be a duplicate
1208
1209                         // Handle any 'Fn/FnOnce/FnMut' bounds specially,
1210                         // as we want to combine them with any 'Output' qpaths
1211                         // later
1212
1213                         let is_fn = match &mut b {
1214                             &mut TyParamBound::TraitBound(ref mut p, _) => {
1215                                 // Insert regions into the for_generics hash map first, to ensure
1216                                 // that we don't end up with duplicate bounds (e.g. for<'b, 'b>)
1217                                 for_generics.extend(p.generic_params.clone());
1218                                 p.generic_params = for_generics.into_iter().collect();
1219                                 self.is_fn_ty(&tcx, &p.trait_)
1220                             }
1221                             _ => false,
1222                         };
1223
1224                         let poly_trait = b.get_poly_trait().unwrap();
1225
1226                         if is_fn {
1227                             ty_to_fn
1228                                 .entry(ty.clone())
1229                                 .and_modify(|e| *e = (Some(poly_trait.clone()), e.1.clone()))
1230                                 .or_insert(((Some(poly_trait.clone())), None));
1231
1232                             ty_to_bounds
1233                                 .entry(ty.clone())
1234                                 .or_insert_with(|| FxHashSet());
1235                         } else {
1236                             ty_to_bounds
1237                                 .entry(ty.clone())
1238                                 .or_insert_with(|| FxHashSet())
1239                                 .insert(b.clone());
1240                         }
1241                     }
1242                 }
1243                 WherePredicate::RegionPredicate { lifetime, bounds } => {
1244                     lifetime_to_bounds
1245                         .entry(lifetime)
1246                         .or_insert_with(|| FxHashSet())
1247                         .extend(bounds);
1248                 }
1249                 WherePredicate::EqPredicate { lhs, rhs } => {
1250                     match &lhs {
1251                         &Type::QPath {
1252                             name: ref left_name,
1253                             ref self_type,
1254                             ref trait_,
1255                         } => {
1256                             let ty = &*self_type;
1257                             match **trait_ {
1258                                 Type::ResolvedPath {
1259                                     path: ref trait_path,
1260                                     ref typarams,
1261                                     ref did,
1262                                     ref is_generic,
1263                                 } => {
1264                                     let mut new_trait_path = trait_path.clone();
1265
1266                                     if self.is_fn_ty(&tcx, trait_) && left_name == FN_OUTPUT_NAME {
1267                                         ty_to_fn
1268                                             .entry(*ty.clone())
1269                                             .and_modify(|e| *e = (e.0.clone(), Some(rhs.clone())))
1270                                             .or_insert((None, Some(rhs)));
1271                                         continue;
1272                                     }
1273
1274                                     // FIXME: Remove this scope when NLL lands
1275                                     {
1276                                         let params =
1277                                             &mut new_trait_path.segments.last_mut().unwrap().params;
1278
1279                                         match params {
1280                                             // Convert somethiung like '<T as Iterator::Item> = u8'
1281                                             // to 'T: Iterator<Item=u8>'
1282                                             &mut PathParameters::AngleBracketed {
1283                                                 ref mut bindings,
1284                                                 ..
1285                                             } => {
1286                                                 bindings.push(TypeBinding {
1287                                                     name: left_name.clone(),
1288                                                     ty: rhs,
1289                                                 });
1290                                             }
1291                                             &mut PathParameters::Parenthesized { .. } => {
1292                                                 existing_predicates.push(
1293                                                     WherePredicate::EqPredicate {
1294                                                         lhs: lhs.clone(),
1295                                                         rhs,
1296                                                     },
1297                                                 );
1298                                                 continue; // If something other than a Fn ends up
1299                                                           // with parenthesis, leave it alone
1300                                             }
1301                                         }
1302                                     }
1303
1304                                     let bounds = ty_to_bounds
1305                                         .entry(*ty.clone())
1306                                         .or_insert_with(|| FxHashSet());
1307
1308                                     bounds.insert(TyParamBound::TraitBound(
1309                                         PolyTrait {
1310                                             trait_: Type::ResolvedPath {
1311                                                 path: new_trait_path,
1312                                                 typarams: typarams.clone(),
1313                                                 did: did.clone(),
1314                                                 is_generic: *is_generic,
1315                                             },
1316                                             generic_params: Vec::new(),
1317                                         },
1318                                         hir::TraitBoundModifier::None,
1319                                     ));
1320
1321                                     // Remove any existing 'plain' bound (e.g. 'T: Iterator`) so
1322                                     // that we don't see a
1323                                     // duplicate bound like `T: Iterator + Iterator<Item=u8>`
1324                                     // on the docs page.
1325                                     bounds.remove(&TyParamBound::TraitBound(
1326                                         PolyTrait {
1327                                             trait_: *trait_.clone(),
1328                                             generic_params: Vec::new(),
1329                                         },
1330                                         hir::TraitBoundModifier::None,
1331                                     ));
1332                                     // Avoid creating any new duplicate bounds later in the outer
1333                                     // loop
1334                                     ty_to_traits
1335                                         .entry(*ty.clone())
1336                                         .or_insert_with(|| FxHashSet())
1337                                         .insert(*trait_.clone());
1338                                 }
1339                                 _ => panic!("Unexpected trait {:?} for {:?}", trait_, did),
1340                             }
1341                         }
1342                         _ => panic!("Unexpected LHS {:?} for {:?}", lhs, did),
1343                     }
1344                 }
1345             };
1346         }
1347
1348         let final_bounds = self.make_final_bounds(ty_to_bounds, ty_to_fn, lifetime_to_bounds);
1349
1350         existing_predicates.extend(final_bounds);
1351
1352         for p in generic_params.iter_mut() {
1353             match p {
1354                 &mut GenericParam::Type(ref mut ty) => {
1355                     // We never want something like 'impl<T=Foo>'
1356                     ty.default.take();
1357
1358                     let generic_ty = Type::Generic(ty.name.clone());
1359
1360                     if !has_sized.contains(&generic_ty) {
1361                         ty.bounds.insert(0, TyParamBound::maybe_sized(self.cx));
1362                     }
1363                 }
1364                 _ => {}
1365             }
1366         }
1367
1368         self.sort_where_predicates(&mut existing_predicates);
1369
1370         Generics {
1371             params: generic_params,
1372             where_predicates: existing_predicates,
1373         }
1374     }
1375
1376     // Ensure that the predicates are in a consistent order. The precise
1377     // ordering doesn't actually matter, but it's important that
1378     // a given set of predicates always appears in the same order -
1379     // both for visual consistency between 'rustdoc' runs, and to
1380     // make writing tests much easier
1381     #[inline]
1382     fn sort_where_predicates(&self, mut predicates: &mut Vec<WherePredicate>) {
1383         // We should never have identical bounds - and if we do,
1384         // they're visually identical as well. Therefore, using
1385         // an unstable sort is fine.
1386         self.unstable_debug_sort(&mut predicates);
1387     }
1388
1389     // Ensure that the bounds are in a consistent order. The precise
1390     // ordering doesn't actually matter, but it's important that
1391     // a given set of bounds always appears in the same order -
1392     // both for visual consistency between 'rustdoc' runs, and to
1393     // make writing tests much easier
1394     #[inline]
1395     fn sort_where_bounds(&self, mut bounds: &mut Vec<TyParamBound>) {
1396         // We should never have identical bounds - and if we do,
1397         // they're visually identical as well. Therefore, using
1398         // an unstable sort is fine.
1399         self.unstable_debug_sort(&mut bounds);
1400     }
1401
1402     #[inline]
1403     fn sort_where_lifetimes(&self, mut bounds: &mut Vec<Lifetime>) {
1404         // We should never have identical bounds - and if we do,
1405         // they're visually identical as well. Therefore, using
1406         // an unstable sort is fine.
1407         self.unstable_debug_sort(&mut bounds);
1408     }
1409
1410     // This might look horrendously hacky, but it's actually not that bad.
1411     //
1412     // For performance reasons, we use several different FxHashMaps
1413     // in the process of computing the final set of where predicates.
1414     // However, the iteration order of a HashMap is completely unspecified.
1415     // In fact, the iteration of an FxHashMap can even vary between platforms,
1416     // since FxHasher has different behavior for 32-bit and 64-bit platforms.
1417     //
1418     // Obviously, it's extremely undesireable for documentation rendering
1419     // to be depndent on the platform it's run on. Apart from being confusing
1420     // to end users, it makes writing tests much more difficult, as predicates
1421     // can appear in any order in the final result.
1422     //
1423     // To solve this problem, we sort WherePredicates and TyParamBounds
1424     // by their Debug string. The thing to keep in mind is that we don't really
1425     // care what the final order is - we're synthesizing an impl or bound
1426     // ourselves, so any order can be considered equally valid. By sorting the
1427     // predicates and bounds, however, we ensure that for a given codebase, all
1428     // auto-trait impls always render in exactly the same way.
1429     //
1430     // Using the Debug impementation for sorting prevents us from needing to
1431     // write quite a bit of almost entirely useless code (e.g. how should two
1432     // Types be sorted relative to each other). It also allows us to solve the
1433     // problem for both WherePredicates and TyParamBounds at the same time. This
1434     // approach is probably somewhat slower, but the small number of items
1435     // involved (impls rarely have more than a few bounds) means that it
1436     // shouldn't matter in practice.
1437     fn unstable_debug_sort<T: Debug>(&self, vec: &mut Vec<T>) {
1438         vec.sort_unstable_by(|first, second| {
1439             format!("{:?}", first).cmp(&format!("{:?}", second))
1440         });
1441     }
1442
1443     fn is_fn_ty(&self, tcx: &TyCtxt, ty: &Type) -> bool {
1444         match &ty {
1445             &&Type::ResolvedPath { ref did, .. } => {
1446                 *did == tcx.require_lang_item(lang_items::FnTraitLangItem)
1447                     || *did == tcx.require_lang_item(lang_items::FnMutTraitLangItem)
1448                     || *did == tcx.require_lang_item(lang_items::FnOnceTraitLangItem)
1449             }
1450             _ => false,
1451         }
1452     }
1453
1454     // This is an ugly hack, but it's the simplest way to handle synthetic impls without greatly
1455     // refactoring either librustdoc or librustc. In particular, allowing new DefIds to be
1456     // registered after the AST is constructed would require storing the defid mapping in a
1457     // RefCell, decreasing the performance for normal compilation for very little gain.
1458     //
1459     // Instead, we construct 'fake' def ids, which start immediately after the last DefId in
1460     // DefIndexAddressSpace::Low. In the Debug impl for clean::Item, we explicitly check for fake
1461     // def ids, as we'll end up with a panic if we use the DefId Debug impl for fake DefIds
1462     fn next_def_id(&self, crate_num: CrateNum) -> DefId {
1463         let start_def_id = {
1464             let next_id = if crate_num == LOCAL_CRATE {
1465                 self.cx
1466                     .tcx
1467                     .hir
1468                     .definitions()
1469                     .def_path_table()
1470                     .next_id(DefIndexAddressSpace::Low)
1471             } else {
1472                 self.cx
1473                     .cstore
1474                     .def_path_table(crate_num)
1475                     .next_id(DefIndexAddressSpace::Low)
1476             };
1477
1478             DefId {
1479                 krate: crate_num,
1480                 index: next_id,
1481             }
1482         };
1483
1484         let mut fake_ids = self.cx.fake_def_ids.borrow_mut();
1485
1486         let def_id = fake_ids.entry(crate_num).or_insert(start_def_id).clone();
1487         fake_ids.insert(
1488             crate_num,
1489             DefId {
1490                 krate: crate_num,
1491                 index: DefIndex::from_array_index(
1492                     def_id.index.as_array_index() + 1,
1493                     def_id.index.address_space(),
1494                 ),
1495             },
1496         );
1497
1498         MAX_DEF_ID.with(|m| {
1499             m.borrow_mut()
1500                 .entry(def_id.krate.clone())
1501                 .or_insert(start_def_id);
1502         });
1503
1504         self.cx.all_fake_def_ids.borrow_mut().insert(def_id);
1505
1506         def_id.clone()
1507     }
1508 }
1509
1510 // Replaces all ReVars in a type with ty::Region's, using the provided map
1511 struct RegionReplacer<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
1512     vid_to_region: &'a FxHashMap<ty::RegionVid, ty::Region<'tcx>>,
1513     tcx: TyCtxt<'a, 'gcx, 'tcx>,
1514 }
1515
1516 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> {
1517     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
1518         self.tcx
1519     }
1520
1521     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
1522         (match r {
1523             &ty::ReVar(vid) => self.vid_to_region.get(&vid).cloned(),
1524             _ => None,
1525         }).unwrap_or_else(|| r.super_fold_with(self))
1526     }
1527 }