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