src/librustdoc/clean/auto_trait.rs

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