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