src/librustdoc/clean/auto_trait.rs

   1 use rustc::hir;
   2 use rustc::traits::auto_trait as auto;
   3 use rustc::ty::{self, TypeFoldable};
   4 use std::fmt::Debug;
   5
   6 use self::def_ctor::{get_def_from_def_id, get_def_from_hir_id};
   7
   8 use super::*;
   9
  10 pub struct AutoTraitFinder<'a, 'tcx> {
  11     pub cx: &'a core::DocContext<'tcx>,
  12     pub f: auto::AutoTraitFinder<'a, 'tcx>,
  13 }
  14
  15 impl<'a, 'tcx> AutoTraitFinder<'a, 'tcx> {
  16     pub fn new(cx: &'a core::DocContext<'tcx>) -> Self {
  17         let f = auto::AutoTraitFinder::new(&cx.tcx);
  18
  19         AutoTraitFinder { cx, f }
  20     }
  21
  22     pub fn get_with_def_id(&self, def_id: DefId) -> Vec<Item> {
  23         get_def_from_def_id(&self.cx, def_id, &|def_ctor| {
  24             self.get_auto_trait_impls(def_id, &def_ctor, None)
  25         })
  26     }
  27
  28     pub fn get_with_hir_id(&self, id: hir::HirId, name: String) -> Vec<Item> {
  29         get_def_from_hir_id(&self.cx, id, name, &|def_ctor, name| {
  30             let did = self.cx.tcx.hir().local_def_id_from_hir_id(id);
  31             self.get_auto_trait_impls(did, &def_ctor, Some(name))
  32         })
  33     }
  34
  35     pub fn get_auto_trait_impls<F>(
  36         &self,
  37         def_id: DefId,
  38         def_ctor: &F,
  39         name: Option<String>,
  40     ) -> Vec<Item>
  41     where F: Fn(DefId) -> Def {
  42         if self.cx
  43             .tcx
  44             .get_attrs(def_id)
  45             .lists("doc")
  46             .has_word("hidden")
  47         {
  48             debug!(
  49                 "get_auto_trait_impls(def_id={:?}, def_ctor=...): item has doc('hidden'), \
  50                  aborting",
  51                 def_id
  52             );
  53             return Vec::new();
  54         }
  55
  56         let tcx = self.cx.tcx;
  57         let generics = self.cx.tcx.generics_of(def_id);
  58
  59         debug!(
  60             "get_auto_trait_impls(def_id={:?}, def_ctor=..., generics={:?}",
  61             def_id, generics
  62         );
  63         let auto_traits: Vec<_> = self.cx
  64             .send_trait
  65             .and_then(|send_trait| {
  66                 self.get_auto_trait_impl_for(
  67                     def_id,
  68                     name.clone(),
  69                     generics.clone(),
  70                     def_ctor,
  71                     send_trait,
  72                 )
  73             })
  74             .into_iter()
  75             .chain(self.get_auto_trait_impl_for(
  76                 def_id,
  77                 name,
  78                 generics.clone(),
  79                 def_ctor,
  80                 tcx.require_lang_item(lang_items::SyncTraitLangItem),
  81             ).into_iter())
  82             .collect();
  83
  84         debug!(
  85             "get_auto_traits: type {:?} auto_traits {:?}",
  86             def_id, auto_traits
  87         );
  88         auto_traits
  89     }
  90
  91     fn get_auto_trait_impl_for<F>(
  92         &self,
  93         def_id: DefId,
  94         name: Option<String>,
  95         generics: ty::Generics,
  96         def_ctor: &F,
  97         trait_def_id: DefId,
  98     ) -> Option<Item>
  99     where F: Fn(DefId) -> Def {
 100         if !self.cx
 101             .generated_synthetics
 102             .borrow_mut()
 103             .insert((def_id, trait_def_id))
 104         {
 105             debug!(
 106                 "get_auto_trait_impl_for(def_id={:?}, generics={:?}, def_ctor=..., \
 107                  trait_def_id={:?}): already generated, aborting",
 108                 def_id, generics, trait_def_id
 109             );
 110             return None;
 111         }
 112
 113         let result = self.find_auto_trait_generics(def_id, trait_def_id, &generics);
 114
 115         if result.is_auto() {
 116             let trait_ = hir::TraitRef {
 117                 path: get_path_for_type(self.cx.tcx, trait_def_id, hir::def::Def::Trait),
 118                 hir_ref_id: hir::DUMMY_HIR_ID,
 119             };
 120
 121             let polarity;
 122
 123             let new_generics = match result {
 124                 AutoTraitResult::PositiveImpl(new_generics) => {
 125                     polarity = None;
 126                     new_generics
 127                 }
 128                 AutoTraitResult::NegativeImpl => {
 129                     polarity = Some(ImplPolarity::Negative);
 130
 131                     // For negative impls, we use the generic params, but *not* the predicates,
 132                     // from the original type. Otherwise, the displayed impl appears to be a
 133                     // conditional negative impl, when it's really unconditional.
 134                     //
 135                     // For example, consider the struct Foo<T: Copy>(*mut T). Using
 136                     // the original predicates in our impl would cause us to generate
 137                     // `impl !Send for Foo<T: Copy>`, which makes it appear that Foo
 138                     // implements Send where T is not copy.
 139                     //
 140                     // Instead, we generate `impl !Send for Foo<T>`, which better
 141                     // expresses the fact that `Foo<T>` never implements `Send`,
 142                     // regardless of the choice of `T`.
 143                     let real_generics = (&generics, &Default::default());
 144
 145                     // Clean the generics, but ignore the '?Sized' bounds generated
 146                     // by the `Clean` impl
 147                     let clean_generics = real_generics.clean(self.cx);
 148
 149                     Generics {
 150                         params: clean_generics.params,
 151                         where_predicates: Vec::new(),
 152                     }
 153                 }
 154                 _ => unreachable!(),
 155             };
 156             let real_name = name.map(|name| Ident::from_str(&name));
 157             let ty = self.cx.get_real_ty(def_id, def_ctor, &real_name, &generics);
 158
 159             return Some(Item {
 160                 source: Span::empty(),
 161                 name: None,
 162                 attrs: Default::default(),
 163                 visibility: None,
 164                 def_id: self.cx.next_def_id(def_id.krate),
 165                 stability: None,
 166                 deprecation: None,
 167                 inner: ImplItem(Impl {
 168                     unsafety: hir::Unsafety::Normal,
 169                     generics: new_generics,
 170                     provided_trait_methods: Default::default(),
 171                     trait_: Some(trait_.clean(self.cx)),
 172                     for_: ty.clean(self.cx),
 173                     items: Vec::new(),
 174                     polarity,
 175                     synthetic: true,
 176                     blanket_impl: None,
 177                 }),
 178             });
 179         }
 180         None
 181     }
 182
 183     fn find_auto_trait_generics(
 184         &self,
 185         did: DefId,
 186         trait_did: DefId,
 187         generics: &ty::Generics,
 188     ) -> AutoTraitResult {
 189         match self.f.find_auto_trait_generics(did, trait_did, generics,
 190                 |infcx, mut info| {
 191                     let region_data = info.region_data;
 192                     let names_map =
 193                         info.names_map
 194                             .drain()
 195                             .map(|name| (name.clone(), Lifetime(name)))
 196                             .collect();
 197                     let lifetime_predicates =
 198                         self.handle_lifetimes(&region_data, &names_map);
 199                     let new_generics = self.param_env_to_generics(
 200                         infcx.tcx,
 201                         did,
 202                         info.full_user_env,
 203                         generics.clone(),
 204                         lifetime_predicates,
 205                         info.vid_to_region,
 206                     );
 207
 208                     debug!(
 209                         "find_auto_trait_generics(did={:?}, trait_did={:?}, generics={:?}): \
 210                          finished with {:?}",
 211                         did, trait_did, generics, new_generics
 212                     );
 213
 214                     new_generics
 215                 }) {
 216             auto::AutoTraitResult::ExplicitImpl => AutoTraitResult::ExplicitImpl,
 217             auto::AutoTraitResult::NegativeImpl => AutoTraitResult::NegativeImpl,
 218             auto::AutoTraitResult::PositiveImpl(res) => AutoTraitResult::PositiveImpl(res),
 219         }
 220     }
 221
 222     fn get_lifetime(
 223         &self, region: Region<'_>,
 224         names_map: &FxHashMap<String, Lifetime>
 225     ) -> Lifetime {
 226         self.region_name(region)
 227             .map(|name| {
 228                 names_map.get(&name).unwrap_or_else(|| {
 229                     panic!("Missing lifetime with name {:?} for {:?}", name, region)
 230                 })
 231             })
 232             .unwrap_or(&Lifetime::statik())
 233             .clone()
 234     }
 235
 236     fn region_name(&self, region: Region<'_>) -> Option<String> {
 237         match region {
 238             &ty::ReEarlyBound(r) => Some(r.name.to_string()),
 239             _ => None,
 240         }
 241     }
 242
 243     // This method calculates two things: Lifetime constraints of the form 'a: 'b,
 244     // and region constraints of the form ReVar: 'a
 245     //
 246     // This is essentially a simplified version of lexical_region_resolve. However,
 247     // handle_lifetimes determines what *needs be* true in order for an impl to hold.
 248     // lexical_region_resolve, along with much of the rest of the compiler, is concerned
 249     // with determining if a given set up constraints/predicates *are* met, given some
 250     // starting conditions (e.g., user-provided code). For this reason, it's easier
 251     // to perform the calculations we need on our own, rather than trying to make
 252     // existing inference/solver code do what we want.
 253     fn handle_lifetimes<'cx>(
 254         &self,
 255         regions: &RegionConstraintData<'cx>,
 256         names_map: &FxHashMap<String, Lifetime>,
 257     ) -> Vec<WherePredicate> {
 258         // Our goal is to 'flatten' the list of constraints by eliminating
 259         // all intermediate RegionVids. At the end, all constraints should
 260         // be between Regions (aka region variables). This gives us the information
 261         // we need to create the Generics.
 262         let mut finished: FxHashMap<_, Vec<_>> = Default::default();
 263
 264         let mut vid_map: FxHashMap<RegionTarget<'_>, RegionDeps<'_>> = Default::default();
 265
 266         // Flattening is done in two parts. First, we insert all of the constraints
 267         // into a map. Each RegionTarget (either a RegionVid or a Region) maps
 268         // to its smaller and larger regions. Note that 'larger' regions correspond
 269         // to sub-regions in Rust code (e.g., in 'a: 'b, 'a is the larger region).
 270         for constraint in regions.constraints.keys() {
 271             match constraint {
 272                 &Constraint::VarSubVar(r1, r2) => {
 273                     {
 274                         let deps1 = vid_map
 275                             .entry(RegionTarget::RegionVid(r1))
 276                             .or_default();
 277                         deps1.larger.insert(RegionTarget::RegionVid(r2));
 278                     }
 279
 280                     let deps2 = vid_map
 281                         .entry(RegionTarget::RegionVid(r2))
 282                         .or_default();
 283                     deps2.smaller.insert(RegionTarget::RegionVid(r1));
 284                 }
 285                 &Constraint::RegSubVar(region, vid) => {
 286                     let deps = vid_map
 287                         .entry(RegionTarget::RegionVid(vid))
 288                         .or_default();
 289                     deps.smaller.insert(RegionTarget::Region(region));
 290                 }
 291                 &Constraint::VarSubReg(vid, region) => {
 292                     let deps = vid_map
 293                         .entry(RegionTarget::RegionVid(vid))
 294                         .or_default();
 295                     deps.larger.insert(RegionTarget::Region(region));
 296                 }
 297                 &Constraint::RegSubReg(r1, r2) => {
 298                     // The constraint is already in the form that we want, so we're done with it
 299                     // Desired order is 'larger, smaller', so flip then
 300                     if self.region_name(r1) != self.region_name(r2) {
 301                         finished
 302                             .entry(self.region_name(r2).expect("no region_name found"))
 303                             .or_default()
 304                             .push(r1);
 305                     }
 306                 }
 307             }
 308         }
 309
 310         // Here, we 'flatten' the map one element at a time.
 311         // All of the element's sub and super regions are connected
 312         // to each other. For example, if we have a graph that looks like this:
 313         //
 314         // (A, B) - C - (D, E)
 315         // Where (A, B) are subregions, and (D,E) are super-regions
 316         //
 317         // then after deleting 'C', the graph will look like this:
 318         //  ... - A - (D, E ...)
 319         //  ... - B - (D, E, ...)
 320         //  (A, B, ...) - D - ...
 321         //  (A, B, ...) - E - ...
 322         //
 323         //  where '...' signifies the existing sub and super regions of an entry
 324         //  When two adjacent ty::Regions are encountered, we've computed a final
 325         //  constraint, and add it to our list. Since we make sure to never re-add
 326         //  deleted items, this process will always finish.
 327         while !vid_map.is_empty() {
 328             let target = vid_map.keys().next().expect("Keys somehow empty").clone();
 329             let deps = vid_map.remove(&target).expect("Entry somehow missing");
 330
 331             for smaller in deps.smaller.iter() {
 332                 for larger in deps.larger.iter() {
 333                     match (smaller, larger) {
 334                         (&RegionTarget::Region(r1), &RegionTarget::Region(r2)) => {
 335                             if self.region_name(r1) != self.region_name(r2) {
 336                                 finished
 337                                     .entry(self.region_name(r2).expect("no region name found"))
 338                                     .or_default()
 339                                     .push(r1) // Larger, smaller
 340                             }
 341                         }
 342                         (&RegionTarget::RegionVid(_), &RegionTarget::Region(_)) => {
 343                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 344                                 let smaller_deps = v.into_mut();
 345                                 smaller_deps.larger.insert(*larger);
 346                                 smaller_deps.larger.remove(&target);
 347                             }
 348                         }
 349                         (&RegionTarget::Region(_), &RegionTarget::RegionVid(_)) => {
 350                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 351                                 let deps = v.into_mut();
 352                                 deps.smaller.insert(*smaller);
 353                                 deps.smaller.remove(&target);
 354                             }
 355                         }
 356                         (&RegionTarget::RegionVid(_), &RegionTarget::RegionVid(_)) => {
 357                             if let Entry::Occupied(v) = vid_map.entry(*smaller) {
 358                                 let smaller_deps = v.into_mut();
 359                                 smaller_deps.larger.insert(*larger);
 360                                 smaller_deps.larger.remove(&target);
 361                             }
 362
 363                             if let Entry::Occupied(v) = vid_map.entry(*larger) {
 364                                 let larger_deps = v.into_mut();
 365                                 larger_deps.smaller.insert(*smaller);
 366                                 larger_deps.smaller.remove(&target);
 367                             }
 368                         }
 369                     }
 370                 }
 371             }
 372         }
 373
 374         let lifetime_predicates = names_map
 375             .iter()
 376             .flat_map(|(name, lifetime)| {
 377                 let empty = Vec::new();
 378                 let bounds: FxHashSet<GenericBound> = finished.get(name).unwrap_or(&empty).iter()
 379                     .map(|region| GenericBound::Outlives(self.get_lifetime(region, names_map)))
 380                     .collect();
 381
 382                 if bounds.is_empty() {
 383                     return None;
 384                 }
 385                 Some(WherePredicate::RegionPredicate {
 386                     lifetime: lifetime.clone(),
 387                     bounds: bounds.into_iter().collect(),
 388                 })
 389             })
 390             .collect();
 391
 392         lifetime_predicates
 393     }
 394
 395     fn extract_for_generics<'b, 'c, 'd>(
 396         &self,
 397         tcx: TyCtxt<'b, 'c, 'd>,
 398         pred: ty::Predicate<'d>,
 399     ) -> FxHashSet<GenericParamDef> {
 400         pred.walk_tys()
 401             .flat_map(|t| {
 402                 let mut regions = FxHashSet::default();
 403                 tcx.collect_regions(&t, &mut regions);
 404
 405                 regions.into_iter().flat_map(|r| {
 406                     match r {
 407                         // We only care about late bound regions, as we need to add them
 408                         // to the 'for<>' section
 409                         &ty::ReLateBound(_, ty::BoundRegion::BrNamed(_, name)) => {
 410                             Some(GenericParamDef {
 411                                 name: name.to_string(),
 412                                 kind: GenericParamDefKind::Lifetime,
 413                             })
 414                         },
 415                         &ty::ReVar(_) | &ty::ReEarlyBound(_) | &ty::ReStatic => None,
 416                         _ => panic!("Unexpected region type {:?}", r),
 417                     }
 418                 })
 419             })
 420             .collect()
 421     }
 422
 423     fn make_final_bounds<'b, 'c, 'cx>(
 424         &self,
 425         ty_to_bounds: FxHashMap<Type, FxHashSet<GenericBound>>,
 426         ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)>,
 427         lifetime_to_bounds: FxHashMap<Lifetime, FxHashSet<GenericBound>>,
 428     ) -> Vec<WherePredicate> {
 429         ty_to_bounds
 430             .into_iter()
 431             .flat_map(|(ty, mut bounds)| {
 432                 if let Some(data) = ty_to_fn.get(&ty) {
 433                     let (poly_trait, output) =
 434                         (data.0.as_ref().expect("as_ref failed").clone(), data.1.as_ref().cloned());
 435                     let new_ty = match &poly_trait.trait_ {
 436                         &Type::ResolvedPath {
 437                             ref path,
 438                             ref param_names,
 439                             ref did,
 440                             ref is_generic,
 441                         } => {
 442                             let mut new_path = path.clone();
 443                             let last_segment = new_path.segments.pop()
 444                                                                 .expect("segments were empty");
 445
 446                             let (old_input, old_output) = match last_segment.args {
 447                                 GenericArgs::AngleBracketed { args, .. } => {
 448                                     let types = args.iter().filter_map(|arg| match arg {
 449                                         GenericArg::Type(ty) => Some(ty.clone()),
 450                                         _ => None,
 451                                     }).collect();
 452                                     (types, None)
 453                                 }
 454                                 GenericArgs::Parenthesized { inputs, output, .. } => {
 455                                     (inputs, output)
 456                                 }
 457                             };
 458
 459                             if old_output.is_some() && old_output != output {
 460                                 panic!(
 461                                     "Output mismatch for {:?} {:?} {:?}",
 462                                     ty, old_output, data.1
 463                                 );
 464                             }
 465
 466                             let new_params = GenericArgs::Parenthesized {
 467                                 inputs: old_input,
 468                                 output,
 469                             };
 470
 471                             new_path.segments.push(PathSegment {
 472                                 name: last_segment.name,
 473                                 args: new_params,
 474                             });
 475
 476                             Type::ResolvedPath {
 477                                 path: new_path,
 478                                 param_names: param_names.clone(),
 479                                 did: did.clone(),
 480                                 is_generic: *is_generic,
 481                             }
 482                         }
 483                         _ => panic!("Unexpected data: {:?}, {:?}", ty, data),
 484                     };
 485                     bounds.insert(GenericBound::TraitBound(
 486                         PolyTrait {
 487                             trait_: new_ty,
 488                             generic_params: poly_trait.generic_params,
 489                         },
 490                         hir::TraitBoundModifier::None,
 491                     ));
 492                 }
 493                 if bounds.is_empty() {
 494                     return None;
 495                 }
 496
 497                 let mut bounds_vec = bounds.into_iter().collect();
 498                 self.sort_where_bounds(&mut bounds_vec);
 499
 500                 Some(WherePredicate::BoundPredicate {
 501                     ty,
 502                     bounds: bounds_vec,
 503                 })
 504             })
 505             .chain(
 506                 lifetime_to_bounds
 507                     .into_iter()
 508                     .filter(|&(_, ref bounds)| !bounds.is_empty())
 509                     .map(|(lifetime, bounds)| {
 510                         let mut bounds_vec = bounds.into_iter().collect();
 511                         self.sort_where_bounds(&mut bounds_vec);
 512                         WherePredicate::RegionPredicate {
 513                             lifetime,
 514                             bounds: bounds_vec,
 515                         }
 516                     }),
 517             )
 518             .collect()
 519     }
 520
 521     // Converts the calculated ParamEnv and lifetime information to a clean::Generics, suitable for
 522     // display on the docs page. Cleaning the Predicates produces sub-optimal WherePredicate's,
 523     // so we fix them up:
 524     //
 525     // * Multiple bounds for the same type are coalesced into one: e.g., 'T: Copy', 'T: Debug'
 526     // becomes 'T: Copy + Debug'
 527     // * Fn bounds are handled specially - instead of leaving it as 'T: Fn(), <T as Fn::Output> =
 528     // K', we use the dedicated syntax 'T: Fn() -> K'
 529     // * We explcitly add a '?Sized' bound if we didn't find any 'Sized' predicates for a type
 530     fn param_env_to_generics<'b, 'c, 'cx>(
 531         &self,
 532         tcx: TyCtxt<'b, 'c, 'cx>,
 533         did: DefId,
 534         param_env: ty::ParamEnv<'cx>,
 535         type_generics: ty::Generics,
 536         mut existing_predicates: Vec<WherePredicate>,
 537         vid_to_region: FxHashMap<ty::RegionVid, ty::Region<'cx>>,
 538     ) -> Generics {
 539         debug!(
 540             "param_env_to_generics(did={:?}, param_env={:?}, type_generics={:?}, \
 541              existing_predicates={:?})",
 542             did, param_env, type_generics, existing_predicates
 543         );
 544
 545         // The `Sized` trait must be handled specially, since we only display it when
 546         // it is *not* required (i.e., '?Sized')
 547         let sized_trait = self.cx
 548             .tcx
 549             .require_lang_item(lang_items::SizedTraitLangItem);
 550
 551         let mut replacer = RegionReplacer {
 552             vid_to_region: &vid_to_region,
 553             tcx,
 554         };
 555
 556         let orig_bounds: FxHashSet<_> = self.cx.tcx.param_env(did).caller_bounds.iter().collect();
 557         let clean_where_predicates = param_env
 558             .caller_bounds
 559             .iter()
 560             .filter(|p| {
 561                 !orig_bounds.contains(p) || match p {
 562                     &&ty::Predicate::Trait(pred) => pred.def_id() == sized_trait,
 563                     _ => false,
 564                 }
 565             })
 566             .map(|p| {
 567                 let replaced = p.fold_with(&mut replacer);
 568                 (replaced.clone(), replaced.clean(self.cx))
 569             });
 570
 571         let full_generics = (&type_generics, &tcx.explicit_predicates_of(did));
 572         let Generics {
 573             params: mut generic_params,
 574             ..
 575         } = full_generics.clean(self.cx);
 576
 577         let mut has_sized = FxHashSet::default();
 578         let mut ty_to_bounds: FxHashMap<_, FxHashSet<_>> = Default::default();
 579         let mut lifetime_to_bounds: FxHashMap<_, FxHashSet<_>> = Default::default();
 580         let mut ty_to_traits: FxHashMap<Type, FxHashSet<Type>> = Default::default();
 581
 582         let mut ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)> = Default::default();
 583
 584         for (orig_p, p) in clean_where_predicates {
 585             if p.is_none() {
 586                 continue;
 587             }
 588             let p = p.unwrap();
 589             match p {
 590                 WherePredicate::BoundPredicate { ty, mut bounds } => {
 591                     // Writing a projection trait bound of the form
 592                     // <T as Trait>::Name : ?Sized
 593                     // is illegal, because ?Sized bounds can only
 594                     // be written in the (here, nonexistant) definition
 595                     // of the type.
 596                     // Therefore, we make sure that we never add a ?Sized
 597                     // bound for projections
 598                     match &ty {
 599                         &Type::QPath { .. } => {
 600                             has_sized.insert(ty.clone());
 601                         }
 602                         _ => {}
 603                     }
 604
 605                     if bounds.is_empty() {
 606                         continue;
 607                     }
 608
 609                     let mut for_generics = self.extract_for_generics(tcx, orig_p.clone());
 610
 611                     assert!(bounds.len() == 1);
 612                     let mut b = bounds.pop().expect("bounds were empty");
 613
 614                     if b.is_sized_bound(self.cx) {
 615                         has_sized.insert(ty.clone());
 616                     } else if !b.get_trait_type()
 617                         .and_then(|t| {
 618                             ty_to_traits
 619                                 .get(&ty)
 620                                 .map(|bounds| bounds.contains(&strip_type(t.clone())))
 621                         })
 622                         .unwrap_or(false)
 623                     {
 624                         // If we've already added a projection bound for the same type, don't add
 625                         // this, as it would be a duplicate
 626
 627                         // Handle any 'Fn/FnOnce/FnMut' bounds specially,
 628                         // as we want to combine them with any 'Output' qpaths
 629                         // later
 630
 631                         let is_fn = match &mut b {
 632                             &mut GenericBound::TraitBound(ref mut p, _) => {
 633                                 // Insert regions into the for_generics hash map first, to ensure
 634                                 // that we don't end up with duplicate bounds (e.g., for<'b, 'b>)
 635                                 for_generics.extend(p.generic_params.clone());
 636                                 p.generic_params = for_generics.into_iter().collect();
 637                                 self.is_fn_ty(&tcx, &p.trait_)
 638                             }
 639                             _ => false,
 640                         };
 641
 642                         let poly_trait = b.get_poly_trait().expect("Cannot get poly trait");
 643
 644                         if is_fn {
 645                             ty_to_fn
 646                                 .entry(ty.clone())
 647                                 .and_modify(|e| *e = (Some(poly_trait.clone()), e.1.clone()))
 648                                 .or_insert(((Some(poly_trait.clone())), None));
 649
 650                             ty_to_bounds
 651                                 .entry(ty.clone())
 652                                 .or_default();
 653                         } else {
 654                             ty_to_bounds
 655                                 .entry(ty.clone())
 656                                 .or_default()
 657                                 .insert(b.clone());
 658                         }
 659                     }
 660                 }
 661                 WherePredicate::RegionPredicate { lifetime, bounds } => {
 662                     lifetime_to_bounds
 663                         .entry(lifetime)
 664                         .or_default()
 665                         .extend(bounds);
 666                 }
 667                 WherePredicate::EqPredicate { lhs, rhs } => {
 668                     match &lhs {
 669                         &Type::QPath {
 670                             name: ref left_name,
 671                             ref self_type,
 672                             ref trait_,
 673                         } => {
 674                             let ty = &*self_type;
 675                             match **trait_ {
 676                                 Type::ResolvedPath {
 677                                     path: ref trait_path,
 678                                     ref param_names,
 679                                     ref did,
 680                                     ref is_generic,
 681                                 } => {
 682                                     let mut new_trait_path = trait_path.clone();
 683
 684                                     if self.is_fn_ty(&tcx, trait_) && left_name == FN_OUTPUT_NAME {
 685                                         ty_to_fn
 686                                             .entry(*ty.clone())
 687                                             .and_modify(|e| *e = (e.0.clone(), Some(rhs.clone())))
 688                                             .or_insert((None, Some(rhs)));
 689                                         continue;
 690                                     }
 691
 692                                     // FIXME: Remove this scope when NLL lands
 693                                     {
 694                                         let args =
 695                                             &mut new_trait_path.segments
 696                                                 .last_mut()
 697                                                 .expect("segments were empty")
 698                                                 .args;
 699
 700                                         match args {
 701                                             // Convert somethiung like '<T as Iterator::Item> = u8'
 702                                             // to 'T: Iterator<Item=u8>'
 703                                             &mut GenericArgs::AngleBracketed {
 704                                                 ref mut bindings,
 705                                                 ..
 706                                             } => {
 707                                                 bindings.push(TypeBinding {
 708                                                     name: left_name.clone(),
 709                                                     ty: rhs,
 710                                                 });
 711                                             }
 712                                             &mut GenericArgs::Parenthesized { .. } => {
 713                                                 existing_predicates.push(
 714                                                     WherePredicate::EqPredicate {
 715                                                         lhs: lhs.clone(),
 716                                                         rhs,
 717                                                     },
 718                                                 );
 719                                                 continue; // If something other than a Fn ends up
 720                                                           // with parenthesis, leave it alone
 721                                             }
 722                                         }
 723                                     }
 724
 725                                     let bounds = ty_to_bounds
 726                                         .entry(*ty.clone())
 727                                         .or_default();
 728
 729                                     bounds.insert(GenericBound::TraitBound(
 730                                         PolyTrait {
 731                                             trait_: Type::ResolvedPath {
 732                                                 path: new_trait_path,
 733                                                 param_names: param_names.clone(),
 734                                                 did: did.clone(),
 735                                                 is_generic: *is_generic,
 736                                             },
 737                                             generic_params: Vec::new(),
 738                                         },
 739                                         hir::TraitBoundModifier::None,
 740                                     ));
 741
 742                                     // Remove any existing 'plain' bound (e.g., 'T: Iterator`) so
 743                                     // that we don't see a
 744                                     // duplicate bound like `T: Iterator + Iterator<Item=u8>`
 745                                     // on the docs page.
 746                                     bounds.remove(&GenericBound::TraitBound(
 747                                         PolyTrait {
 748                                             trait_: *trait_.clone(),
 749                                             generic_params: Vec::new(),
 750                                         },
 751                                         hir::TraitBoundModifier::None,
 752                                     ));
 753                                     // Avoid creating any new duplicate bounds later in the outer
 754                                     // loop
 755                                     ty_to_traits
 756                                         .entry(*ty.clone())
 757                                         .or_default()
 758                                         .insert(*trait_.clone());
 759                                 }
 760                                 _ => panic!("Unexpected trait {:?} for {:?}", trait_, did),
 761                             }
 762                         }
 763                         _ => panic!("Unexpected LHS {:?} for {:?}", lhs, did),
 764                     }
 765                 }
 766             };
 767         }
 768
 769         let final_bounds = self.make_final_bounds(ty_to_bounds, ty_to_fn, lifetime_to_bounds);
 770
 771         existing_predicates.extend(final_bounds);
 772
 773         for param in generic_params.iter_mut() {
 774             match param.kind {
 775                 GenericParamDefKind::Type { ref mut default, ref mut bounds, .. } => {
 776                     // We never want something like `impl<T=Foo>`.
 777                     default.take();
 778                     let generic_ty = Type::Generic(param.name.clone());
 779                     if !has_sized.contains(&generic_ty) {
 780                         bounds.insert(0, GenericBound::maybe_sized(self.cx));
 781                     }
 782                 }
 783                 GenericParamDefKind::Lifetime => {}
 784                 GenericParamDefKind::Const { .. } => {}
 785             }
 786         }
 787
 788         self.sort_where_predicates(&mut existing_predicates);
 789
 790         Generics {
 791             params: generic_params,
 792             where_predicates: existing_predicates,
 793         }
 794     }
 795
 796     // Ensure that the predicates are in a consistent order. The precise
 797     // ordering doesn't actually matter, but it's important that
 798     // a given set of predicates always appears in the same order -
 799     // both for visual consistency between 'rustdoc' runs, and to
 800     // make writing tests much easier
 801     #[inline]
 802     fn sort_where_predicates(&self, mut predicates: &mut Vec<WherePredicate>) {
 803         // We should never have identical bounds - and if we do,
 804         // they're visually identical as well. Therefore, using
 805         // an unstable sort is fine.
 806         self.unstable_debug_sort(&mut predicates);
 807     }
 808
 809     // Ensure that the bounds are in a consistent order. The precise
 810     // ordering doesn't actually matter, but it's important that
 811     // a given set of bounds always appears in the same order -
 812     // both for visual consistency between 'rustdoc' runs, and to
 813     // make writing tests much easier
 814     #[inline]
 815     fn sort_where_bounds(&self, mut bounds: &mut Vec<GenericBound>) {
 816         // We should never have identical bounds - and if we do,
 817         // they're visually identical as well. Therefore, using
 818         // an unstable sort is fine.
 819         self.unstable_debug_sort(&mut bounds);
 820     }
 821
 822     // This might look horrendously hacky, but it's actually not that bad.
 823     //
 824     // For performance reasons, we use several different FxHashMaps
 825     // in the process of computing the final set of where predicates.
 826     // However, the iteration order of a HashMap is completely unspecified.
 827     // In fact, the iteration of an FxHashMap can even vary between platforms,
 828     // since FxHasher has different behavior for 32-bit and 64-bit platforms.
 829     //
 830     // Obviously, it's extremely undesirable for documentation rendering
 831     // to be depndent on the platform it's run on. Apart from being confusing
 832     // to end users, it makes writing tests much more difficult, as predicates
 833     // can appear in any order in the final result.
 834     //
 835     // To solve this problem, we sort WherePredicates and GenericBounds
 836     // by their Debug string. The thing to keep in mind is that we don't really
 837     // care what the final order is - we're synthesizing an impl or bound
 838     // ourselves, so any order can be considered equally valid. By sorting the
 839     // predicates and bounds, however, we ensure that for a given codebase, all
 840     // auto-trait impls always render in exactly the same way.
 841     //
 842     // Using the Debug implementation for sorting prevents us from needing to
 843     // write quite a bit of almost entirely useless code (e.g., how should two
 844     // Types be sorted relative to each other). It also allows us to solve the
 845     // problem for both WherePredicates and GenericBounds at the same time. This
 846     // approach is probably somewhat slower, but the small number of items
 847     // involved (impls rarely have more than a few bounds) means that it
 848     // shouldn't matter in practice.
 849     fn unstable_debug_sort<T: Debug>(&self, vec: &mut Vec<T>) {
 850         vec.sort_by_cached_key(|x| format!("{:?}", x))
 851     }
 852
 853     fn is_fn_ty(&self, tcx: &TyCtxt<'_, '_, '_>, ty: &Type) -> bool {
 854         match &ty {
 855             &&Type::ResolvedPath { ref did, .. } => {
 856                 *did == tcx.require_lang_item(lang_items::FnTraitLangItem)
 857                     || *did == tcx.require_lang_item(lang_items::FnMutTraitLangItem)
 858                     || *did == tcx.require_lang_item(lang_items::FnOnceTraitLangItem)
 859             }
 860             _ => false,
 861         }
 862     }
 863 }
 864
 865 // Replaces all ReVars in a type with ty::Region's, using the provided map
 866 struct RegionReplacer<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
 867     vid_to_region: &'a FxHashMap<ty::RegionVid, ty::Region<'tcx>>,
 868     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 869 }
 870
 871 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> {
 872     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
 873         self.tcx
 874     }
 875
 876     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 877         (match r {
 878             &ty::ReVar(vid) => self.vid_to_region.get(&vid).cloned(),
 879             _ => None,
 880         }).unwrap_or_else(|| r.super_fold_with(self))
 881     }
 882 }