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(Symbol::intern(&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![
 264                         hir::PathSegment::from_name(Symbol::intern(&param.name))
 265                     ]),
 266                 }),
 267             )),
 268             span: DUMMY_SP,
 269             hir_id: hir::DUMMY_HIR_ID,
 270         }
 271     }
 272
 273     fn find_auto_trait_generics(
 274         &self,
 275         did: DefId,
 276         trait_did: DefId,
 277         generics: &ty::Generics,
 278     ) -> AutoTraitResult {
 279         let tcx = self.cx.tcx;
 280         let ty = self.cx.tcx.type_of(did);
 281
 282         let orig_params = tcx.param_env(did);
 283
 284         let trait_ref = ty::TraitRef {
 285             def_id: trait_did,
 286             substs: tcx.mk_substs_trait(ty, &[]),
 287         };
 288
 289         let trait_pred = ty::Binder::bind(trait_ref);
 290
 291         let bail_out = tcx.infer_ctxt().enter(|infcx| {
 292             let mut selcx = SelectionContext::with_negative(&infcx, true);
 293             let result = selcx.select(&Obligation::new(
 294                 ObligationCause::dummy(),
 295                 orig_params,
 296                 trait_pred.to_poly_trait_predicate(),
 297             ));
 298             match result {
 299                 Ok(Some(Vtable::VtableImpl(_))) => {
 300                     debug!(
 301                         "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): \
 302                          manual impl found, bailing out",
 303                         did, trait_did, generics
 304                     );
 305                     return true;
 306                 }
 307                 _ => return false,
 308             };
 309         });
 310
 311         // If an explicit impl exists, it always takes priority over an auto impl
 312         if bail_out {
 313             return AutoTraitResult::ExplicitImpl;
 314         }
 315
 316         return tcx.infer_ctxt().enter(|mut infcx| {
 317             let mut fresh_preds = FxHashSet();
 318
 319             // Due to the way projections are handled by SelectionContext, we need to run
 320             // evaluate_predicates twice: once on the original param env, and once on the result of
 321             // the first evaluate_predicates call.
 322             //
 323             // The problem is this: most of rustc, including SelectionContext and traits::project,
 324             // are designed to work with a concrete usage of a type (e.g. Vec<u8>
 325             // fn<T>() { Vec<T> }. This information will generally never change - given
 326             // the 'T' in fn<T>() { ... }, we'll never know anything else about 'T'.
 327             // If we're unable to prove that 'T' implements a particular trait, we're done -
 328             // there's nothing left to do but error out.
 329             //
 330             // However, synthesizing an auto trait impl works differently. Here, we start out with
 331             // a set of initial conditions - the ParamEnv of the struct/enum/union we're dealing
 332             // with - and progressively discover the conditions we need to fulfill for it to
 333             // implement a certain auto trait. This ends up breaking two assumptions made by trait
 334             // selection and projection:
 335             //
 336             // * We can always cache the result of a particular trait selection for the lifetime of
 337             // an InfCtxt
 338             // * Given a projection bound such as '<T as SomeTrait>::SomeItem = K', if 'T:
 339             // SomeTrait' doesn't hold, then we don't need to care about the 'SomeItem = K'
 340             //
 341             // We fix the first assumption by manually clearing out all of the InferCtxt's caches
 342             // in between calls to SelectionContext.select. This allows us to keep all of the
 343             // intermediate types we create bound to the 'tcx lifetime, rather than needing to lift
 344             // them between calls.
 345             //
 346             // We fix the second assumption by reprocessing the result of our first call to
 347             // evaluate_predicates. Using the example of '<T as SomeTrait>::SomeItem = K', our first
 348             // pass will pick up 'T: SomeTrait', but not 'SomeItem = K'. On our second pass,
 349             // traits::project will see that 'T: SomeTrait' is in our ParamEnv, allowing
 350             // SelectionContext to return it back to us.
 351
 352             let (new_env, user_env) = match self.evaluate_predicates(
 353                 &mut infcx,
 354                 did,
 355                 trait_did,
 356                 ty,
 357                 orig_params.clone(),
 358                 orig_params,
 359                 &mut fresh_preds,
 360                 false,
 361             ) {
 362                 Some(e) => e,
 363                 None => return AutoTraitResult::NegativeImpl,
 364             };
 365
 366             let (full_env, full_user_env) = self.evaluate_predicates(
 367                 &mut infcx,
 368                 did,
 369                 trait_did,
 370                 ty,
 371                 new_env.clone(),
 372                 user_env,
 373                 &mut fresh_preds,
 374                 true,
 375             ).unwrap_or_else(|| {
 376                 panic!(
 377                     "Failed to fully process: {:?} {:?} {:?}",
 378                     ty, trait_did, orig_params
 379                 )
 380             });
 381
 382             debug!(
 383                 "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): fulfilling \
 384                  with {:?}",
 385                 did, trait_did, generics, full_env
 386             );
 387             infcx.clear_caches();
 388
 389             // At this point, we already have all of the bounds we need. FulfillmentContext is used
 390             // to store all of the necessary region/lifetime bounds in the InferContext, as well as
 391             // an additional sanity check.
 392             let mut fulfill = FulfillmentContext::new();
 393             fulfill.register_bound(
 394                 &infcx,
 395                 full_env,
 396                 ty,
 397                 trait_did,
 398                 ObligationCause::misc(DUMMY_SP, ast::DUMMY_NODE_ID),
 399             );
 400             fulfill.select_all_or_error(&infcx).unwrap_or_else(|e| {
 401                 panic!(
 402                     "Unable to fulfill trait {:?} for '{:?}': {:?}",
 403                     trait_did, ty, e
 404                 )
 405             });
 406
 407             let names_map: FxHashMap<String, Lifetime> = generics
 408                 .regions
 409                 .iter()
 410                 .map(|l| (l.name.to_string(), l.clean(self.cx)))
 411                 .collect();
 412
 413             let body_ids: FxHashSet<_> = infcx
 414                 .region_obligations
 415                 .borrow()
 416                 .iter()
 417                 .map(|&(id, _)| id)
 418                 .collect();
 419
 420             for id in body_ids {
 421                 infcx.process_registered_region_obligations(&[], None, full_env.clone(), id);
 422             }
 423
 424             let region_data = infcx
 425                 .borrow_region_constraints()
 426                 .region_constraint_data()
 427                 .clone();
 428
 429             let lifetime_predicates = self.handle_lifetimes(&region_data, &names_map);
 430             let vid_to_region = self.map_vid_to_region(&region_data);
 431
 432             debug!(
 433                 "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): computed \
 434                  lifetime information '{:?}' '{:?}'",
 435                 did, trait_did, generics, lifetime_predicates, vid_to_region
 436             );
 437
 438             let new_generics = self.param_env_to_generics(
 439                 infcx.tcx,
 440                 did,
 441                 full_user_env,
 442                 generics.clone(),
 443                 lifetime_predicates,
 444                 vid_to_region,
 445             );
 446             debug!(
 447                 "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): finished with \
 448                  {:?}",
 449                 did, trait_did, generics, new_generics
 450             );
 451             return AutoTraitResult::PositiveImpl(new_generics);
 452         });
 453     }
 454
 455     fn clean_pred<'c, 'd, 'cx>(
 456         &self,
 457         infcx: &InferCtxt<'c, 'd, 'cx>,
 458         p: ty::Predicate<'cx>,
 459     ) -> ty::Predicate<'cx> {
 460         infcx.freshen(p)
 461     }
 462
 463     fn evaluate_nested_obligations<'b, 'c, 'd, 'cx,
 464                                     T: Iterator<Item = Obligation<'cx, ty::Predicate<'cx>>>>(
 465         &self,
 466         ty: ty::Ty,
 467         nested: T,
 468         computed_preds: &'b mut FxHashSet<ty::Predicate<'cx>>,
 469         fresh_preds: &'b mut FxHashSet<ty::Predicate<'cx>>,
 470         predicates: &'b mut VecDeque<ty::PolyTraitPredicate<'cx>>,
 471         select: &mut traits::SelectionContext<'c, 'd, 'cx>,
 472         only_projections: bool,
 473     ) -> bool {
 474         let dummy_cause = ObligationCause::misc(DUMMY_SP, ast::DUMMY_NODE_ID);
 475
 476         for (obligation, predicate) in nested
 477             .filter(|o| o.recursion_depth == 1)
 478             .map(|o| (o.clone(), o.predicate.clone()))
 479         {
 480             let is_new_pred =
 481                 fresh_preds.insert(self.clean_pred(select.infcx(), predicate.clone()));
 482
 483             match &predicate {
 484                 &ty::Predicate::Trait(ref p) => {
 485                     let substs = &p.skip_binder().trait_ref.substs;
 486
 487                     if self.is_of_param(substs) && !only_projections && is_new_pred {
 488                         computed_preds.insert(predicate);
 489                     }
 490                     predicates.push_back(p.clone());
 491                 }
 492                 &ty::Predicate::Projection(p) => {
 493                     // If the projection isn't all type vars, then
 494                     // we don't want to add it as a bound
 495                     if self.is_of_param(p.skip_binder().projection_ty.substs) && is_new_pred {
 496                         computed_preds.insert(predicate);
 497                     } else {
 498                         match traits::poly_project_and_unify_type(
 499                             select,
 500                             &obligation.with(p.clone()),
 501                         ) {
 502                             Err(e) => {
 503                                 debug!(
 504                                     "evaluate_nested_obligations: Unable to unify predicate \
 505                                      '{:?}' '{:?}', bailing out",
 506                                     ty, e
 507                                 );
 508                                 return false;
 509                             }
 510                             Ok(Some(v)) => {
 511                                 if !self.evaluate_nested_obligations(
 512                                     ty,
 513                                     v.clone().iter().cloned(),
 514                                     computed_preds,
 515                                     fresh_preds,
 516                                     predicates,
 517                                     select,
 518                                     only_projections,
 519                                 ) {
 520                                     return false;
 521                                 }
 522                             }
 523                             Ok(None) => {
 524                                 panic!("Unexpected result when selecting {:?} {:?}", ty, obligation)
 525                             }
 526                         }
 527                     }
 528                 }
 529                 &ty::Predicate::RegionOutlives(ref binder) => {
 530                     if let Err(_) = select
 531                         .infcx()
 532                         .region_outlives_predicate(&dummy_cause, binder)
 533                     {
 534                         return false;
 535                     }
 536                 }
 537                 &ty::Predicate::TypeOutlives(ref binder) => {
 538                     match (
 539                         binder.no_late_bound_regions(),
 540                         binder.map_bound_ref(|pred| pred.0).no_late_bound_regions(),
 541                     ) {
 542                         (None, Some(t_a)) => {
 543                             select.infcx().register_region_obligation(
 544                                 ast::DUMMY_NODE_ID,
 545                                 RegionObligation {
 546                                     sup_type: t_a,
 547                                     sub_region: select.infcx().tcx.types.re_static,
 548                                     cause: dummy_cause.clone(),
 549                                 },
 550                             );
 551                         }
 552                         (Some(ty::OutlivesPredicate(t_a, r_b)), _) => {
 553                             select.infcx().register_region_obligation(
 554                                 ast::DUMMY_NODE_ID,
 555                                 RegionObligation {
 556                                     sup_type: t_a,
 557                                     sub_region: r_b,
 558                                     cause: dummy_cause.clone(),
 559                                 },
 560                             );
 561                         }
 562                         _ => {}
 563                     };
 564                 }
 565                 _ => panic!("Unexpected predicate {:?} {:?}", ty, predicate),
 566             };
 567         }
 568         return true;
 569     }
 570
 571     // The core logic responsible for computing the bounds for our synthesized impl.
 572     //
 573     // To calculate the bounds, we call SelectionContext.select in a loop. Like FulfillmentContext,
 574     // we recursively select the nested obligations of predicates we encounter. However, whenver we
 575     // encounter an UnimplementedError involving a type parameter, we add it to our ParamEnv. Since
 576     // our goal is to determine when a particular type implements an auto trait, Unimplemented
 577     // errors tell us what conditions need to be met.
 578     //
 579     // This method ends up working somewhat similary to FulfillmentContext, but with a few key
 580     // differences. FulfillmentContext works under the assumption that it's dealing with concrete
 581     // user code. According, it considers all possible ways that a Predicate could be met - which
 582     // isn't always what we want for a synthesized impl. For example, given the predicate 'T:
 583     // Iterator', FulfillmentContext can end up reporting an Unimplemented error for T:
 584     // IntoIterator - since there's an implementation of Iteratpr where T: IntoIterator,
 585     // FulfillmentContext will drive SelectionContext to consider that impl before giving up. If we
 586     // were to rely on FulfillmentContext's decision, we might end up synthesizing an impl like
 587     // this:
 588     // 'impl<T> Send for Foo<T> where T: IntoIterator'
 589     //
 590     // While it might be technically true that Foo implements Send where T: IntoIterator,
 591     // the bound is overly restrictive - it's really only necessary that T: Iterator.
 592     //
 593     // For this reason, evaluate_predicates handles predicates with type variables specially. When
 594     // we encounter an Unimplemented error for a bound such as 'T: Iterator', we immediately add it
 595     // to our ParamEnv, and add it to our stack for recursive evaluation. When we later select it,
 596     // we'll pick up any nested bounds, without ever inferring that 'T: IntoIterator' needs to
 597     // hold.
 598     //
 599     // One additonal consideration is supertrait bounds. Normally, a ParamEnv is only ever
 600     // consutrcted once for a given type. As part of the construction process, the ParamEnv will
 601     // have any supertrait bounds normalized - e.g. if we have a type 'struct Foo<T: Copy>', the
 602     // ParamEnv will contain 'T: Copy' and 'T: Clone', since 'Copy: Clone'. When we construct our
 603     // own ParamEnv, we need to do this outselves, through traits::elaborate_predicates, or else
 604     // SelectionContext will choke on the missing predicates. However, this should never show up in
 605     // the final synthesized generics: we don't want our generated docs page to contain something
 606     // like 'T: Copy + Clone', as that's redundant. Therefore, we keep track of a separate
 607     // 'user_env', which only holds the predicates that will actually be displayed to the user.
 608     fn evaluate_predicates<'b, 'gcx, 'c>(
 609         &self,
 610         infcx: &mut InferCtxt<'b, 'tcx, 'c>,
 611         ty_did: DefId,
 612         trait_did: DefId,
 613         ty: ty::Ty<'c>,
 614         param_env: ty::ParamEnv<'c>,
 615         user_env: ty::ParamEnv<'c>,
 616         fresh_preds: &mut FxHashSet<ty::Predicate<'c>>,
 617         only_projections: bool,
 618     ) -> Option<(ty::ParamEnv<'c>, ty::ParamEnv<'c>)> {
 619         let tcx = infcx.tcx;
 620
 621         let mut select = traits::SelectionContext::new(&infcx);
 622
 623         let mut already_visited = FxHashSet();
 624         let mut predicates = VecDeque::new();
 625         predicates.push_back(ty::Binder::bind(ty::TraitPredicate {
 626             trait_ref: ty::TraitRef {
 627                 def_id: trait_did,
 628                 substs: infcx.tcx.mk_substs_trait(ty, &[]),
 629             },
 630         }));
 631
 632         let mut computed_preds: FxHashSet<_> = param_env.caller_bounds.iter().cloned().collect();
 633         let mut user_computed_preds: FxHashSet<_> =
 634             user_env.caller_bounds.iter().cloned().collect();
 635
 636         let mut new_env = param_env.clone();
 637         let dummy_cause = ObligationCause::misc(DUMMY_SP, ast::DUMMY_NODE_ID);
 638
 639         while let Some(pred) = predicates.pop_front() {
 640             infcx.clear_caches();
 641
 642             if !already_visited.insert(pred.clone()) {
 643                 continue;
 644             }
 645
 646             let result = select.select(&Obligation::new(dummy_cause.clone(), new_env, pred));
 647
 648             match &result {
 649                 &Ok(Some(ref vtable)) => {
 650                     let obligations = vtable.clone().nested_obligations().into_iter();
 651
 652                     if !self.evaluate_nested_obligations(
 653                         ty,
 654                         obligations,
 655                         &mut user_computed_preds,
 656                         fresh_preds,
 657                         &mut predicates,
 658                         &mut select,
 659                         only_projections,
 660                     ) {
 661                         return None;
 662                     }
 663                 }
 664                 &Ok(None) => {}
 665                 &Err(SelectionError::Unimplemented) => {
 666                     if self.is_of_param(pred.skip_binder().trait_ref.substs) {
 667                         already_visited.remove(&pred);
 668                         user_computed_preds.insert(ty::Predicate::Trait(pred.clone()));
 669                         predicates.push_back(pred);
 670                     } else {
 671                         debug!(
 672                             "evaluate_nested_obligations: Unimplemented found, bailing: {:?} {:?} \
 673                              {:?}",
 674                             ty,
 675                             pred,
 676                             pred.skip_binder().trait_ref.substs
 677                         );
 678                         return None;
 679                     }
 680                 }
 681                 _ => panic!("Unexpected error for '{:?}': {:?}", ty, result),
 682             };
 683
 684             computed_preds.extend(user_computed_preds.iter().cloned());
 685             let normalized_preds =
 686                 traits::elaborate_predicates(tcx, computed_preds.clone().into_iter().collect());
 687             new_env = ty::ParamEnv::new(
 688                 tcx.mk_predicates(normalized_preds),
 689                 param_env.reveal,
 690             );
 691         }
 692
 693         let final_user_env = ty::ParamEnv::new(
 694             tcx.mk_predicates(user_computed_preds.into_iter()),
 695             user_env.reveal,
 696         );
 697         debug!(
 698             "evaluate_nested_obligations(ty_did={:?}, trait_did={:?}): succeeded with '{:?}' \
 699              '{:?}'",
 700             ty_did, trait_did, new_env, final_user_env
 701         );
 702
 703         return Some((new_env, final_user_env));
 704     }
 705
 706     fn is_of_param(&self, substs: &Substs) -> bool {
 707         if substs.is_noop() {
 708             return false;
 709         }
 710
 711         return match substs.type_at(0).sty {
 712             ty::TyParam(_) => true,
 713             ty::TyProjection(p) => self.is_of_param(p.substs),
 714             _ => false,
 715         };
 716     }
 717
 718     fn get_lifetime(&self, region: Region, names_map: &FxHashMap<String, Lifetime>) -> Lifetime {
 719         self.region_name(region)
 720             .map(|name| {
 721                 names_map.get(&name).unwrap_or_else(|| {
 722                     panic!("Missing lifetime with name {:?} for {:?}", name, region)
 723                 })
 724             })
 725             .unwrap_or(&Lifetime::statik())
 726             .clone()
 727     }
 728
 729     fn region_name(&self, region: Region) -> Option<String> {
 730         match region {
 731             &ty::ReEarlyBound(r) => Some(r.name.to_string()),
 732             _ => None,
 733         }
 734     }
 735
 736     // This is very similar to handle_lifetimes. However, instead of matching ty::Region's
 737     // to each other, we match ty::RegionVid's to ty::Region's
 738     fn map_vid_to_region<'cx>(
 739         &self,
 740         regions: &RegionConstraintData<'cx>,
 741     ) -> FxHashMap<ty::RegionVid, ty::Region<'cx>> {
 742         let mut vid_map: FxHashMap<RegionTarget<'cx>, RegionDeps<'cx>> = FxHashMap();
 743         let mut finished_map = FxHashMap();
 744
 745         for constraint in regions.constraints.keys() {
 746             match constraint {
 747                 &Constraint::VarSubVar(r1, r2) => {
 748                     {
 749                         let deps1 = vid_map
 750                             .entry(RegionTarget::RegionVid(r1))
 751                             .or_insert_with(|| Default::default());
 752                         deps1.larger.insert(RegionTarget::RegionVid(r2));
 753                     }
 754
 755                     let deps2 = vid_map
 756                         .entry(RegionTarget::RegionVid(r2))
 757                         .or_insert_with(|| Default::default());
 758                     deps2.smaller.insert(RegionTarget::RegionVid(r1));
 759                 }
 760                 &Constraint::RegSubVar(region, vid) => {
 761                     {
 762                         let deps1 = vid_map
 763                             .entry(RegionTarget::Region(region))
 764                             .or_insert_with(|| Default::default());
 765                         deps1.larger.insert(RegionTarget::RegionVid(vid));
 766                     }
 767
 768                     let deps2 = vid_map
 769                         .entry(RegionTarget::RegionVid(vid))
 770                         .or_insert_with(|| Default::default());
 771                     deps2.smaller.insert(RegionTarget::Region(region));
 772                 }
 773                 &Constraint::VarSubReg(vid, region) => {
 774                     finished_map.insert(vid, region);
 775                 }
 776                 &Constraint::RegSubReg(r1, r2) => {
 777                     {
 778                         let deps1 = vid_map
 779                             .entry(RegionTarget::Region(r1))
 780                             .or_insert_with(|| Default::default());
 781                         deps1.larger.insert(RegionTarget::Region(r2));
 782                     }
 783
 784                     let deps2 = vid_map
 785                         .entry(RegionTarget::Region(r2))
 786                         .or_insert_with(|| Default::default());
 787                     deps2.smaller.insert(RegionTarget::Region(r1));
 788                 }
 789             }
 790         }
 791
 792         while !vid_map.is_empty() {
 793             let target = vid_map.keys().next().expect("Keys somehow empty").clone();
 794             let deps = vid_map.remove(&target).expect("Entry somehow missing");
 795
 796             for smaller in deps.smaller.iter() {
 797                 for larger in deps.larger.iter() {
 798                     match (smaller, larger) {
 799                         (&RegionTarget::Region(_), &RegionTarget::Region(_)) => {
 800                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 801                                 let smaller_deps = v.into_mut();
 802                                 smaller_deps.larger.insert(*larger);
 803                                 smaller_deps.larger.remove(&target);
 804                             }
 805
 806                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 807                                 let larger_deps = v.into_mut();
 808                                 larger_deps.smaller.insert(*smaller);
 809                                 larger_deps.smaller.remove(&target);
 810                             }
 811                         }
 812                         (&RegionTarget::RegionVid(v1), &RegionTarget::Region(r1)) => {
 813                             finished_map.insert(v1, r1);
 814                         }
 815                         (&RegionTarget::Region(_), &RegionTarget::RegionVid(_)) => {
 816                             // Do nothing - we don't care about regions that are smaller than vids
 817                         }
 818                         (&RegionTarget::RegionVid(_), &RegionTarget::RegionVid(_)) => {
 819                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 820                                 let smaller_deps = v.into_mut();
 821                                 smaller_deps.larger.insert(*larger);
 822                                 smaller_deps.larger.remove(&target);
 823                             }
 824
 825                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 826                                 let larger_deps = v.into_mut();
 827                                 larger_deps.smaller.insert(*smaller);
 828                                 larger_deps.smaller.remove(&target);
 829                             }
 830                         }
 831                     }
 832                 }
 833             }
 834         }
 835         finished_map
 836     }
 837
 838     // This method calculates two things: Lifetime constraints of the form 'a: 'b,
 839     // and region constraints of the form ReVar: 'a
 840     //
 841     // This is essentially a simplified version of lexical_region_resolve. However,
 842     // handle_lifetimes determines what *needs be* true in order for an impl to hold.
 843     // lexical_region_resolve, along with much of the rest of the compiler, is concerned
 844     // with determining if a given set up constraints/predicates *are* met, given some
 845     // starting conditions (e.g. user-provided code). For this reason, it's easier
 846     // to perform the calculations we need on our own, rather than trying to make
 847     // existing inference/solver code do what we want.
 848     fn handle_lifetimes<'cx>(
 849         &self,
 850         regions: &RegionConstraintData<'cx>,
 851         names_map: &FxHashMap<String, Lifetime>,
 852     ) -> Vec<WherePredicate> {
 853         // Our goal is to 'flatten' the list of constraints by eliminating
 854         // all intermediate RegionVids. At the end, all constraints should
 855         // be between Regions (aka region variables). This gives us the information
 856         // we need to create the Generics.
 857         let mut finished = FxHashMap();
 858
 859         let mut vid_map: FxHashMap<RegionTarget, RegionDeps> = FxHashMap();
 860
 861         // Flattening is done in two parts. First, we insert all of the constraints
 862         // into a map. Each RegionTarget (either a RegionVid or a Region) maps
 863         // to its smaller and larger regions. Note that 'larger' regions correspond
 864         // to sub-regions in Rust code (e.g. in 'a: 'b, 'a is the larger region).
 865         for constraint in regions.constraints.keys() {
 866             match constraint {
 867                 &Constraint::VarSubVar(r1, r2) => {
 868                     {
 869                         let deps1 = vid_map
 870                             .entry(RegionTarget::RegionVid(r1))
 871                             .or_insert_with(|| Default::default());
 872                         deps1.larger.insert(RegionTarget::RegionVid(r2));
 873                     }
 874
 875                     let deps2 = vid_map
 876                         .entry(RegionTarget::RegionVid(r2))
 877                         .or_insert_with(|| Default::default());
 878                     deps2.smaller.insert(RegionTarget::RegionVid(r1));
 879                 }
 880                 &Constraint::RegSubVar(region, vid) => {
 881                     let deps = vid_map
 882                         .entry(RegionTarget::RegionVid(vid))
 883                         .or_insert_with(|| Default::default());
 884                     deps.smaller.insert(RegionTarget::Region(region));
 885                 }
 886                 &Constraint::VarSubReg(vid, region) => {
 887                     let deps = vid_map
 888                         .entry(RegionTarget::RegionVid(vid))
 889                         .or_insert_with(|| Default::default());
 890                     deps.larger.insert(RegionTarget::Region(region));
 891                 }
 892                 &Constraint::RegSubReg(r1, r2) => {
 893                     // The constraint is already in the form that we want, so we're done with it
 894                     // Desired order is 'larger, smaller', so flip then
 895                     if self.region_name(r1) != self.region_name(r2) {
 896                         finished
 897                             .entry(self.region_name(r2).unwrap())
 898                             .or_insert_with(|| Vec::new())
 899                             .push(r1);
 900                     }
 901                 }
 902             }
 903         }
 904
 905         // Here, we 'flatten' the map one element at a time.
 906         // All of the element's sub and super regions are connected
 907         // to each other. For example, if we have a graph that looks like this:
 908         //
 909         // (A, B) - C - (D, E)
 910         // Where (A, B) are subregions, and (D,E) are super-regions
 911         //
 912         // then after deleting 'C', the graph will look like this:
 913         //  ... - A - (D, E ...)
 914         //  ... - B - (D, E, ...)
 915         //  (A, B, ...) - D - ...
 916         //  (A, B, ...) - E - ...
 917         //
 918         //  where '...' signifies the existing sub and super regions of an entry
 919         //  When two adjacent ty::Regions are encountered, we've computed a final
 920         //  constraint, and add it to our list. Since we make sure to never re-add
 921         //  deleted items, this process will always finish.
 922         while !vid_map.is_empty() {
 923             let target = vid_map.keys().next().expect("Keys somehow empty").clone();
 924             let deps = vid_map.remove(&target).expect("Entry somehow missing");
 925
 926             for smaller in deps.smaller.iter() {
 927                 for larger in deps.larger.iter() {
 928                     match (smaller, larger) {
 929                         (&RegionTarget::Region(r1), &RegionTarget::Region(r2)) => {
 930                             if self.region_name(r1) != self.region_name(r2) {
 931                                 finished
 932                                     .entry(self.region_name(r2).unwrap())
 933                                     .or_insert_with(|| Vec::new())
 934                                     .push(r1) // Larger, smaller
 935                             }
 936                         }
 937                         (&RegionTarget::RegionVid(_), &RegionTarget::Region(_)) => {
 938                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 939                                 let smaller_deps = v.into_mut();
 940                                 smaller_deps.larger.insert(*larger);
 941                                 smaller_deps.larger.remove(&target);
 942                             }
 943                         }
 944                         (&RegionTarget::Region(_), &RegionTarget::RegionVid(_)) => {
 945                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 946                                 let deps = v.into_mut();
 947                                 deps.smaller.insert(*smaller);
 948                                 deps.smaller.remove(&target);
 949                             }
 950                         }
 951                         (&RegionTarget::RegionVid(_), &RegionTarget::RegionVid(_)) => {
 952                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 953                                 let smaller_deps = v.into_mut();
 954                                 smaller_deps.larger.insert(*larger);
 955                                 smaller_deps.larger.remove(&target);
 956                             }
 957
 958                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 959                                 let larger_deps = v.into_mut();
 960                                 larger_deps.smaller.insert(*smaller);
 961                                 larger_deps.smaller.remove(&target);
 962                             }
 963                         }
 964                     }
 965                 }
 966             }
 967         }
 968
 969         let lifetime_predicates = names_map
 970             .iter()
 971             .flat_map(|(name, lifetime)| {
 972                 let empty = Vec::new();
 973                 let bounds: FxHashSet<Lifetime> = finished
 974                     .get(name)
 975                     .unwrap_or(&empty)
 976                     .iter()
 977                     .map(|region| self.get_lifetime(region, names_map))
 978                     .collect();
 979
 980                 if bounds.is_empty() {
 981                     return None;
 982                 }
 983                 Some(WherePredicate::RegionPredicate {
 984                     lifetime: lifetime.clone(),
 985                     bounds: bounds.into_iter().collect(),
 986                 })
 987             })
 988             .collect();
 989
 990         lifetime_predicates
 991     }
 992
 993     fn extract_for_generics<'b, 'c, 'd>(
 994         &self,
 995         tcx: TyCtxt<'b, 'c, 'd>,
 996         pred: ty::Predicate<'d>,
 997     ) -> FxHashSet<GenericParam> {
 998         pred.walk_tys()
 999             .flat_map(|t| {
1000                 let mut regions = FxHashSet();
1001                 tcx.collect_regions(&t, &mut regions);
1002
1003                 regions.into_iter().flat_map(|r| {
1004                     match r {
1005                         // We only care about late bound regions, as we need to add them
1006                         // to the 'for<>' section
1007                         &ty::ReLateBound(_, ty::BoundRegion::BrNamed(_, name)) => {
1008                             Some(GenericParam::Lifetime(Lifetime(name.to_string())))
1009                         }
1010                         &ty::ReVar(_) | &ty::ReEarlyBound(_) => None,
1011                         _ => panic!("Unexpected region type {:?}", r),
1012                     }
1013                 })
1014             })
1015             .collect()
1016     }
1017
1018     fn make_final_bounds<'b, 'c, 'cx>(
1019         &self,
1020         ty_to_bounds: FxHashMap<Type, FxHashSet<TyParamBound>>,
1021         ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)>,
1022         lifetime_to_bounds: FxHashMap<Lifetime, FxHashSet<Lifetime>>,
1023     ) -> Vec<WherePredicate> {
1024         ty_to_bounds
1025             .into_iter()
1026             .flat_map(|(ty, mut bounds)| {
1027                 if let Some(data) = ty_to_fn.get(&ty) {
1028                     let (poly_trait, output) =
1029                         (data.0.as_ref().unwrap().clone(), data.1.as_ref().cloned());
1030                     let new_ty = match &poly_trait.trait_ {
1031                         &Type::ResolvedPath {
1032                             ref path,
1033                             ref typarams,
1034                             ref did,
1035                             ref is_generic,
1036                         } => {
1037                             let mut new_path = path.clone();
1038                             let last_segment = new_path.segments.pop().unwrap();
1039
1040                             let (old_input, old_output) = match last_segment.params {
1041                                 PathParameters::AngleBracketed { types, .. } => (types, None),
1042                                 PathParameters::Parenthesized { inputs, output, .. } => {
1043                                     (inputs, output)
1044                                 }
1045                             };
1046
1047                             if old_output.is_some() && old_output != output {
1048                                 panic!(
1049                                     "Output mismatch for {:?} {:?} {:?}",
1050                                     ty, old_output, data.1
1051                                 );
1052                             }
1053
1054                             let new_params = PathParameters::Parenthesized {
1055                                 inputs: old_input,
1056                                 output,
1057                             };
1058
1059                             new_path.segments.push(PathSegment {
1060                                 name: last_segment.name,
1061                                 params: new_params,
1062                             });
1063
1064                             Type::ResolvedPath {
1065                                 path: new_path,
1066                                 typarams: typarams.clone(),
1067                                 did: did.clone(),
1068                                 is_generic: *is_generic,
1069                             }
1070                         }
1071                         _ => panic!("Unexpected data: {:?}, {:?}", ty, data),
1072                     };
1073                     bounds.insert(TyParamBound::TraitBound(
1074                         PolyTrait {
1075                             trait_: new_ty,
1076                             generic_params: poly_trait.generic_params,
1077                         },
1078                         hir::TraitBoundModifier::None,
1079                     ));
1080                 }
1081                 if bounds.is_empty() {
1082                     return None;
1083                 }
1084
1085                 let mut bounds_vec = bounds.into_iter().collect();
1086                 self.sort_where_bounds(&mut bounds_vec);
1087
1088                 Some(WherePredicate::BoundPredicate {
1089                     ty,
1090                     bounds: bounds_vec,
1091                 })
1092             })
1093             .chain(
1094                 lifetime_to_bounds
1095                     .into_iter()
1096                     .filter(|&(_, ref bounds)| !bounds.is_empty())
1097                     .map(|(lifetime, bounds)| {
1098                         let mut bounds_vec = bounds.into_iter().collect();
1099                         self.sort_where_lifetimes(&mut bounds_vec);
1100                         WherePredicate::RegionPredicate {
1101                             lifetime,
1102                             bounds: bounds_vec,
1103                         }
1104                     }),
1105             )
1106             .collect()
1107     }
1108
1109     // Converts the calculated ParamEnv and lifetime information to a clean::Generics, suitable for
1110     // display on the docs page. Cleaning the Predicates produces sub-optimal WherePredicate's,
1111     // so we fix them up:
1112     //
1113     // * Multiple bounds for the same type are coalesced into one: e.g. 'T: Copy', 'T: Debug'
1114     // becomes 'T: Copy + Debug'
1115     // * Fn bounds are handled specially - instead of leaving it as 'T: Fn(), <T as Fn::Output> =
1116     // K', we use the dedicated syntax 'T: Fn() -> K'
1117     // * We explcitly add a '?Sized' bound if we didn't find any 'Sized' predicates for a type
1118     fn param_env_to_generics<'b, 'c, 'cx>(
1119         &self,
1120         tcx: TyCtxt<'b, 'c, 'cx>,
1121         did: DefId,
1122         param_env: ty::ParamEnv<'cx>,
1123         type_generics: ty::Generics,
1124         mut existing_predicates: Vec<WherePredicate>,
1125         vid_to_region: FxHashMap<ty::RegionVid, ty::Region<'cx>>,
1126     ) -> Generics {
1127         debug!(
1128             "param_env_to_generics(did={:?}, param_env={:?}, type_generics={:?}, \
1129              existing_predicates={:?})",
1130             did, param_env, type_generics, existing_predicates
1131         );
1132
1133         // The `Sized` trait must be handled specially, since we only only display it when
1134         // it is *not* required (i.e. '?Sized')
1135         let sized_trait = self.cx
1136             .tcx
1137             .require_lang_item(lang_items::SizedTraitLangItem);
1138
1139         let mut replacer = RegionReplacer {
1140             vid_to_region: &vid_to_region,
1141             tcx,
1142         };
1143
1144         let orig_bounds: FxHashSet<_> = self.cx.tcx.param_env(did).caller_bounds.iter().collect();
1145         let clean_where_predicates = param_env
1146             .caller_bounds
1147             .iter()
1148             .filter(|p| {
1149                 !orig_bounds.contains(p) || match p {
1150                     &&ty::Predicate::Trait(pred) => pred.def_id() == sized_trait,
1151                     _ => false,
1152                 }
1153             })
1154             .map(|p| {
1155                 let replaced = p.fold_with(&mut replacer);
1156                 (replaced.clone(), replaced.clean(self.cx))
1157             });
1158
1159         let full_generics = (&type_generics, &tcx.predicates_of(did));
1160         let Generics {
1161             params: mut generic_params,
1162             ..
1163         } = full_generics.clean(self.cx);
1164
1165         let mut has_sized = FxHashSet();
1166         let mut ty_to_bounds = FxHashMap();
1167         let mut lifetime_to_bounds = FxHashMap();
1168         let mut ty_to_traits: FxHashMap<Type, FxHashSet<Type>> = FxHashMap();
1169
1170         let mut ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)> = FxHashMap();
1171
1172         for (orig_p, p) in clean_where_predicates {
1173             match p {
1174                 WherePredicate::BoundPredicate { ty, mut bounds } => {
1175                     // Writing a projection trait bound of the form
1176                     // <T as Trait>::Name : ?Sized
1177                     // is illegal, because ?Sized bounds can only
1178                     // be written in the (here, nonexistant) definition
1179                     // of the type.
1180                     // Therefore, we make sure that we never add a ?Sized
1181                     // bound for projections
1182                     match &ty {
1183                         &Type::QPath { .. } => {
1184                             has_sized.insert(ty.clone());
1185                         }
1186                         _ => {}
1187                     }
1188
1189                     if bounds.is_empty() {
1190                         continue;
1191                     }
1192
1193                     let mut for_generics = self.extract_for_generics(tcx, orig_p.clone());
1194
1195                     assert!(bounds.len() == 1);
1196                     let mut b = bounds.pop().unwrap();
1197
1198                     if b.is_sized_bound(self.cx) {
1199                         has_sized.insert(ty.clone());
1200                     } else if !b.get_trait_type()
1201                         .and_then(|t| {
1202                             ty_to_traits
1203                                 .get(&ty)
1204                                 .map(|bounds| bounds.contains(&strip_type(t.clone())))
1205                         })
1206                         .unwrap_or(false)
1207                     {
1208                         // If we've already added a projection bound for the same type, don't add
1209                         // this, as it would be a duplicate
1210
1211                         // Handle any 'Fn/FnOnce/FnMut' bounds specially,
1212                         // as we want to combine them with any 'Output' qpaths
1213                         // later
1214
1215                         let is_fn = match &mut b {
1216                             &mut TyParamBound::TraitBound(ref mut p, _) => {
1217                                 // Insert regions into the for_generics hash map first, to ensure
1218                                 // that we don't end up with duplicate bounds (e.g. for<'b, 'b>)
1219                                 for_generics.extend(p.generic_params.clone());
1220                                 p.generic_params = for_generics.into_iter().collect();
1221                                 self.is_fn_ty(&tcx, &p.trait_)
1222                             }
1223                             _ => false,
1224                         };
1225
1226                         let poly_trait = b.get_poly_trait().unwrap();
1227
1228                         if is_fn {
1229                             ty_to_fn
1230                                 .entry(ty.clone())
1231                                 .and_modify(|e| *e = (Some(poly_trait.clone()), e.1.clone()))
1232                                 .or_insert(((Some(poly_trait.clone())), None));
1233
1234                             ty_to_bounds
1235                                 .entry(ty.clone())
1236                                 .or_insert_with(|| FxHashSet());
1237                         } else {
1238                             ty_to_bounds
1239                                 .entry(ty.clone())
1240                                 .or_insert_with(|| FxHashSet())
1241                                 .insert(b.clone());
1242                         }
1243                     }
1244                 }
1245                 WherePredicate::RegionPredicate { lifetime, bounds } => {
1246                     lifetime_to_bounds
1247                         .entry(lifetime)
1248                         .or_insert_with(|| FxHashSet())
1249                         .extend(bounds);
1250                 }
1251                 WherePredicate::EqPredicate { lhs, rhs } => {
1252                     match &lhs {
1253                         &Type::QPath {
1254                             name: ref left_name,
1255                             ref self_type,
1256                             ref trait_,
1257                         } => {
1258                             let ty = &*self_type;
1259                             match **trait_ {
1260                                 Type::ResolvedPath {
1261                                     path: ref trait_path,
1262                                     ref typarams,
1263                                     ref did,
1264                                     ref is_generic,
1265                                 } => {
1266                                     let mut new_trait_path = trait_path.clone();
1267
1268                                     if self.is_fn_ty(&tcx, trait_) && left_name == FN_OUTPUT_NAME {
1269                                         ty_to_fn
1270                                             .entry(*ty.clone())
1271                                             .and_modify(|e| *e = (e.0.clone(), Some(rhs.clone())))
1272                                             .or_insert((None, Some(rhs)));
1273                                         continue;
1274                                     }
1275
1276                                     // FIXME: Remove this scope when NLL lands
1277                                     {
1278                                         let params =
1279                                             &mut new_trait_path.segments.last_mut().unwrap().params;
1280
1281                                         match params {
1282                                             // Convert somethiung like '<T as Iterator::Item> = u8'
1283                                             // to 'T: Iterator<Item=u8>'
1284                                             &mut PathParameters::AngleBracketed {
1285                                                 ref mut bindings,
1286                                                 ..
1287                                             } => {
1288                                                 bindings.push(TypeBinding {
1289                                                     name: left_name.clone(),
1290                                                     ty: rhs,
1291                                                 });
1292                                             }
1293                                             &mut PathParameters::Parenthesized { .. } => {
1294                                                 existing_predicates.push(
1295                                                     WherePredicate::EqPredicate {
1296                                                         lhs: lhs.clone(),
1297                                                         rhs,
1298                                                     },
1299                                                 );
1300                                                 continue; // If something other than a Fn ends up
1301                                                           // with parenthesis, leave it alone
1302                                             }
1303                                         }
1304                                     }
1305
1306                                     let bounds = ty_to_bounds
1307                                         .entry(*ty.clone())
1308                                         .or_insert_with(|| FxHashSet());
1309
1310                                     bounds.insert(TyParamBound::TraitBound(
1311                                         PolyTrait {
1312                                             trait_: Type::ResolvedPath {
1313                                                 path: new_trait_path,
1314                                                 typarams: typarams.clone(),
1315                                                 did: did.clone(),
1316                                                 is_generic: *is_generic,
1317                                             },
1318                                             generic_params: Vec::new(),
1319                                         },
1320                                         hir::TraitBoundModifier::None,
1321                                     ));
1322
1323                                     // Remove any existing 'plain' bound (e.g. 'T: Iterator`) so
1324                                     // that we don't see a
1325                                     // duplicate bound like `T: Iterator + Iterator<Item=u8>`
1326                                     // on the docs page.
1327                                     bounds.remove(&TyParamBound::TraitBound(
1328                                         PolyTrait {
1329                                             trait_: *trait_.clone(),
1330                                             generic_params: Vec::new(),
1331                                         },
1332                                         hir::TraitBoundModifier::None,
1333                                     ));
1334                                     // Avoid creating any new duplicate bounds later in the outer
1335                                     // loop
1336                                     ty_to_traits
1337                                         .entry(*ty.clone())
1338                                         .or_insert_with(|| FxHashSet())
1339                                         .insert(*trait_.clone());
1340                                 }
1341                                 _ => panic!("Unexpected trait {:?} for {:?}", trait_, did),
1342                             }
1343                         }
1344                         _ => panic!("Unexpected LHS {:?} for {:?}", lhs, did),
1345                     }
1346                 }
1347             };
1348         }
1349
1350         let final_bounds = self.make_final_bounds(ty_to_bounds, ty_to_fn, lifetime_to_bounds);
1351
1352         existing_predicates.extend(final_bounds);
1353
1354         for p in generic_params.iter_mut() {
1355             match p {
1356                 &mut GenericParam::Type(ref mut ty) => {
1357                     // We never want something like 'impl<T=Foo>'
1358                     ty.default.take();
1359
1360                     let generic_ty = Type::Generic(ty.name.clone());
1361
1362                     if !has_sized.contains(&generic_ty) {
1363                         ty.bounds.insert(0, TyParamBound::maybe_sized(self.cx));
1364                     }
1365                 }
1366                 _ => {}
1367             }
1368         }
1369
1370         self.sort_where_predicates(&mut existing_predicates);
1371
1372         Generics {
1373             params: generic_params,
1374             where_predicates: existing_predicates,
1375         }
1376     }
1377
1378     // Ensure that the predicates are in a consistent order. The precise
1379     // ordering doesn't actually matter, but it's important that
1380     // a given set of predicates always appears in the same order -
1381     // both for visual consistency between 'rustdoc' runs, and to
1382     // make writing tests much easier
1383     #[inline]
1384     fn sort_where_predicates(&self, mut predicates: &mut Vec<WherePredicate>) {
1385         // We should never have identical bounds - and if we do,
1386         // they're visually identical as well. Therefore, using
1387         // an unstable sort is fine.
1388         self.unstable_debug_sort(&mut predicates);
1389     }
1390
1391     // Ensure that the bounds are in a consistent order. The precise
1392     // ordering doesn't actually matter, but it's important that
1393     // a given set of bounds always appears in the same order -
1394     // both for visual consistency between 'rustdoc' runs, and to
1395     // make writing tests much easier
1396     #[inline]
1397     fn sort_where_bounds(&self, mut bounds: &mut Vec<TyParamBound>) {
1398         // We should never have identical bounds - and if we do,
1399         // they're visually identical as well. Therefore, using
1400         // an unstable sort is fine.
1401         self.unstable_debug_sort(&mut bounds);
1402     }
1403
1404     #[inline]
1405     fn sort_where_lifetimes(&self, mut bounds: &mut Vec<Lifetime>) {
1406         // We should never have identical bounds - and if we do,
1407         // they're visually identical as well. Therefore, using
1408         // an unstable sort is fine.
1409         self.unstable_debug_sort(&mut bounds);
1410     }
1411
1412     // This might look horrendously hacky, but it's actually not that bad.
1413     //
1414     // For performance reasons, we use several different FxHashMaps
1415     // in the process of computing the final set of where predicates.
1416     // However, the iteration order of a HashMap is completely unspecified.
1417     // In fact, the iteration of an FxHashMap can even vary between platforms,
1418     // since FxHasher has different behavior for 32-bit and 64-bit platforms.
1419     //
1420     // Obviously, it's extremely undesireable for documentation rendering
1421     // to be depndent on the platform it's run on. Apart from being confusing
1422     // to end users, it makes writing tests much more difficult, as predicates
1423     // can appear in any order in the final result.
1424     //
1425     // To solve this problem, we sort WherePredicates and TyParamBounds
1426     // by their Debug string. The thing to keep in mind is that we don't really
1427     // care what the final order is - we're synthesizing an impl or bound
1428     // ourselves, so any order can be considered equally valid. By sorting the
1429     // predicates and bounds, however, we ensure that for a given codebase, all
1430     // auto-trait impls always render in exactly the same way.
1431     //
1432     // Using the Debug impementation for sorting prevents us from needing to
1433     // write quite a bit of almost entirely useless code (e.g. how should two
1434     // Types be sorted relative to each other). It also allows us to solve the
1435     // problem for both WherePredicates and TyParamBounds at the same time. This
1436     // approach is probably somewhat slower, but the small number of items
1437     // involved (impls rarely have more than a few bounds) means that it
1438     // shouldn't matter in practice.
1439     fn unstable_debug_sort<T: Debug>(&self, vec: &mut Vec<T>) {
1440         vec.sort_by_cached_key(|x| format!("{:?}", x))
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 }