src/librustdoc/clean/auto_trait.rs

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