src/librustdoc/passes/collect_intra_doc_links.rs

   1 use rustc_ast as ast;
   2 use rustc_data_structures::stable_set::FxHashSet;
   3 use rustc_errors::{Applicability, DiagnosticBuilder};
   4 use rustc_expand::base::SyntaxExtensionKind;
   5 use rustc_hir as hir;
   6 use rustc_hir::def::{
   7     DefKind,
   8     Namespace::{self, *},
   9     PerNS, Res,
  10 };
  11 use rustc_hir::def_id::DefId;
  12 use rustc_middle::ty;
  13 use rustc_resolve::ParentScope;
  14 use rustc_session::lint;
  15 use rustc_span::hygiene::MacroKind;
  16 use rustc_span::symbol::Ident;
  17 use rustc_span::symbol::Symbol;
  18 use rustc_span::DUMMY_SP;
  19 use smallvec::{smallvec, SmallVec};
  20
  21 use std::borrow::Cow;
  22 use std::cell::Cell;
  23 use std::ops::Range;
  24
  25 use crate::clean::*;
  26 use crate::core::DocContext;
  27 use crate::fold::DocFolder;
  28 use crate::html::markdown::markdown_links;
  29 use crate::passes::Pass;
  30
  31 use super::span_of_attrs;
  32
  33 pub const COLLECT_INTRA_DOC_LINKS: Pass = Pass {
  34     name: "collect-intra-doc-links",
  35     run: collect_intra_doc_links,
  36     description: "reads a crate's documentation to resolve intra-doc-links",
  37 };
  38
  39 pub fn collect_intra_doc_links(krate: Crate, cx: &DocContext<'_>) -> Crate {
  40     let mut coll = LinkCollector::new(cx);
  41     coll.fold_crate(krate)
  42 }
  43
  44 enum ErrorKind<'a> {
  45     Resolve(Box<ResolutionFailure<'a>>),
  46     AnchorFailure(AnchorFailure),
  47 }
  48
  49 impl<'a> From<ResolutionFailure<'a>> for ErrorKind<'a> {
  50     fn from(err: ResolutionFailure<'a>) -> Self {
  51         ErrorKind::Resolve(box err)
  52     }
  53 }
  54
  55 #[derive(Debug)]
  56 enum ResolutionFailure<'a> {
  57     /// This resolved, but with the wrong namespace.
  58     /// `Namespace` is the expected namespace (as opposed to the actual).
  59     WrongNamespace(Res, Namespace),
  60     /// The link failed to resolve. `resolution_failure` should look to see if there's
  61     /// a more helpful error that can be given.
  62     NotResolved { module_id: DefId, partial_res: Option<Res>, unresolved: Cow<'a, str> },
  63     /// should not ever happen
  64     NoParentItem,
  65     /// used to communicate that this should be ignored, but shouldn't be reported to the user
  66     Dummy,
  67 }
  68
  69 impl ResolutionFailure<'a> {
  70     // This resolved fully (not just partially) but is erroneous for some other reason
  71     fn full_res(&self) -> Option<Res> {
  72         match self {
  73             Self::WrongNamespace(res, _) => Some(*res),
  74             _ => None,
  75         }
  76     }
  77 }
  78
  79 enum AnchorFailure {
  80     MultipleAnchors,
  81     RustdocAnchorConflict(Res),
  82 }
  83
  84 struct LinkCollector<'a, 'tcx> {
  85     cx: &'a DocContext<'tcx>,
  86     // NOTE: this may not necessarily be a module in the current crate
  87     mod_ids: Vec<DefId>,
  88     /// This is used to store the kind of associated items,
  89     /// because `clean` and the disambiguator code expect them to be different.
  90     /// See the code for associated items on inherent impls for details.
  91     kind_side_channel: Cell<Option<(DefKind, DefId)>>,
  92 }
  93
  94 impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
  95     fn new(cx: &'a DocContext<'tcx>) -> Self {
  96         LinkCollector { cx, mod_ids: Vec::new(), kind_side_channel: Cell::new(None) }
  97     }
  98
  99     fn variant_field(
 100         &self,
 101         path_str: &'path str,
 102         current_item: &Option<String>,
 103         module_id: DefId,
 104     ) -> Result<(Res, Option<String>), ErrorKind<'path>> {
 105         let cx = self.cx;
 106         let no_res = || ResolutionFailure::NotResolved {
 107             module_id,
 108             partial_res: None,
 109             unresolved: path_str.into(),
 110         };
 111
 112         debug!("looking for enum variant {}", path_str);
 113         let mut split = path_str.rsplitn(3, "::");
 114         let (variant_field_str, variant_field_name) = split
 115             .next()
 116             .map(|f| (f, Symbol::intern(f)))
 117             .expect("fold_item should ensure link is non-empty");
 118         let (variant_str, variant_name) =
 119             // we're not sure this is a variant at all, so use the full string
 120             // If there's no second component, the link looks like `[path]`.
 121             // So there's no partial res and we should say the whole link failed to resolve.
 122             split.next().map(|f| (f, Symbol::intern(f))).ok_or_else(no_res)?;
 123         let path = split
 124             .next()
 125             .map(|f| {
 126                 if f == "self" || f == "Self" {
 127                     if let Some(name) = current_item.as_ref() {
 128                         return name.clone();
 129                     }
 130                 }
 131                 f.to_owned()
 132             })
 133             // If there's no third component, we saw `[a::b]` before and it failed to resolve.
 134             // So there's no partial res.
 135             .ok_or_else(no_res)?;
 136         let ty_res = cx
 137             .enter_resolver(|resolver| {
 138                 resolver.resolve_str_path_error(DUMMY_SP, &path, TypeNS, module_id)
 139             })
 140             .map(|(_, res)| res)
 141             .unwrap_or(Res::Err);
 142         if let Res::Err = ty_res {
 143             return Err(no_res().into());
 144         }
 145         let ty_res = ty_res.map_id(|_| panic!("unexpected node_id"));
 146         match ty_res {
 147             Res::Def(DefKind::Enum, did) => {
 148                 if cx
 149                     .tcx
 150                     .inherent_impls(did)
 151                     .iter()
 152                     .flat_map(|imp| cx.tcx.associated_items(*imp).in_definition_order())
 153                     .any(|item| item.ident.name == variant_name)
 154                 {
 155                     // This is just to let `fold_item` know that this shouldn't be considered;
 156                     // it's a bug for the error to make it to the user
 157                     return Err(ResolutionFailure::Dummy.into());
 158                 }
 159                 match cx.tcx.type_of(did).kind() {
 160                     ty::Adt(def, _) if def.is_enum() => {
 161                         if def.all_fields().any(|item| item.ident.name == variant_field_name) {
 162                             Ok((
 163                                 ty_res,
 164                                 Some(format!(
 165                                     "variant.{}.field.{}",
 166                                     variant_str, variant_field_name
 167                                 )),
 168                             ))
 169                         } else {
 170                             Err(ResolutionFailure::NotResolved {
 171                                 module_id,
 172                                 partial_res: Some(Res::Def(DefKind::Enum, def.did)),
 173                                 unresolved: variant_field_str.into(),
 174                             }
 175                             .into())
 176                         }
 177                     }
 178                     _ => unreachable!(),
 179                 }
 180             }
 181             _ => Err(ResolutionFailure::NotResolved {
 182                 module_id,
 183                 partial_res: Some(ty_res),
 184                 unresolved: variant_str.into(),
 185             }
 186             .into()),
 187         }
 188     }
 189
 190     /// Resolves a string as a macro.
 191     fn macro_resolve(
 192         &self,
 193         path_str: &'a str,
 194         module_id: DefId,
 195     ) -> Result<Res, ResolutionFailure<'a>> {
 196         let cx = self.cx;
 197         let path = ast::Path::from_ident(Ident::from_str(path_str));
 198         cx.enter_resolver(|resolver| {
 199             if let Ok((Some(ext), res)) = resolver.resolve_macro_path(
 200                 &path,
 201                 None,
 202                 &ParentScope::module(resolver.graph_root()),
 203                 false,
 204                 false,
 205             ) {
 206                 if let SyntaxExtensionKind::LegacyBang { .. } = ext.kind {
 207                     return Ok(res.map_id(|_| panic!("unexpected id")));
 208                 }
 209             }
 210             if let Some(res) = resolver.all_macros().get(&Symbol::intern(path_str)) {
 211                 return Ok(res.map_id(|_| panic!("unexpected id")));
 212             }
 213             debug!("resolving {} as a macro in the module {:?}", path_str, module_id);
 214             if let Ok((_, res)) =
 215                 resolver.resolve_str_path_error(DUMMY_SP, path_str, MacroNS, module_id)
 216             {
 217                 // don't resolve builtins like `#[derive]`
 218                 if let Res::Def(..) = res {
 219                     let res = res.map_id(|_| panic!("unexpected node_id"));
 220                     return Ok(res);
 221                 }
 222             }
 223             Err(ResolutionFailure::NotResolved {
 224                 module_id,
 225                 partial_res: None,
 226                 unresolved: path_str.into(),
 227             })
 228         })
 229     }
 230
 231     /// Resolves a string as a path within a particular namespace. Also returns an optional
 232     /// URL fragment in the case of variants and methods.
 233     fn resolve<'path>(
 234         &self,
 235         path_str: &'path str,
 236         ns: Namespace,
 237         current_item: &Option<String>,
 238         module_id: DefId,
 239         extra_fragment: &Option<String>,
 240     ) -> Result<(Res, Option<String>), ErrorKind<'path>> {
 241         let cx = self.cx;
 242
 243         let result = cx.enter_resolver(|resolver| {
 244             resolver.resolve_str_path_error(DUMMY_SP, &path_str, ns, module_id)
 245         });
 246         debug!("{} resolved to {:?} in namespace {:?}", path_str, result, ns);
 247         let result = match result {
 248             Ok((_, Res::Err)) => Err(()),
 249             x => x,
 250         };
 251
 252         if let Ok((_, res)) = result {
 253             let res = res.map_id(|_| panic!("unexpected node_id"));
 254             // In case this is a trait item, skip the
 255             // early return and try looking for the trait.
 256             let value = match res {
 257                 Res::Def(DefKind::AssocFn | DefKind::AssocConst, _) => true,
 258                 Res::Def(DefKind::AssocTy, _) => false,
 259                 Res::Def(DefKind::Variant, _) => {
 260                     return handle_variant(cx, res, extra_fragment);
 261                 }
 262                 // Not a trait item; just return what we found.
 263                 Res::PrimTy(ty) => {
 264                     if extra_fragment.is_some() {
 265                         return Err(ErrorKind::AnchorFailure(
 266                             AnchorFailure::RustdocAnchorConflict(res),
 267                         ));
 268                     }
 269                     return Ok((res, Some(ty.name_str().to_owned())));
 270                 }
 271                 Res::Def(DefKind::Mod, _) => {
 272                     return Ok((res, extra_fragment.clone()));
 273                 }
 274                 _ => {
 275                     return Ok((res, extra_fragment.clone()));
 276                 }
 277             };
 278
 279             if value != (ns == ValueNS) {
 280                 return Err(ResolutionFailure::WrongNamespace(res, ns).into());
 281             }
 282         // FIXME: why is this necessary?
 283         } else if let Some((path, prim)) = is_primitive(path_str, ns) {
 284             if extra_fragment.is_some() {
 285                 return Err(ErrorKind::AnchorFailure(AnchorFailure::RustdocAnchorConflict(prim)));
 286             }
 287             return Ok((prim, Some(path.to_owned())));
 288         }
 289
 290         // Try looking for methods and associated items.
 291         let mut split = path_str.rsplitn(2, "::");
 292         // this can be an `unwrap()` because we ensure the link is never empty
 293         let (item_str, item_name) = split.next().map(|i| (i, Symbol::intern(i))).unwrap();
 294         let path_root = split
 295             .next()
 296             .map(|f| {
 297                 if f == "self" || f == "Self" {
 298                     if let Some(name) = current_item.as_ref() {
 299                         return name.clone();
 300                     }
 301                 }
 302                 f.to_owned()
 303             })
 304             // If there's no `::`, it's not an associated item.
 305             // So we can be sure that `rustc_resolve` was accurate when it said it wasn't resolved.
 306             .ok_or_else(|| {
 307                 debug!("found no `::`, assumming {} was correctly not in scope", item_name);
 308                 ResolutionFailure::NotResolved {
 309                     module_id,
 310                     partial_res: None,
 311                     unresolved: item_str.into(),
 312                 }
 313             })?;
 314
 315         if let Some((path, prim)) = is_primitive(&path_root, TypeNS) {
 316             let impls =
 317                 primitive_impl(cx, &path).ok_or_else(|| ResolutionFailure::NotResolved {
 318                     module_id,
 319                     partial_res: Some(prim),
 320                     unresolved: item_str.into(),
 321                 })?;
 322             for &impl_ in impls {
 323                 let link = cx
 324                     .tcx
 325                     .associated_items(impl_)
 326                     .find_by_name_and_namespace(
 327                         cx.tcx,
 328                         Ident::with_dummy_span(item_name),
 329                         ns,
 330                         impl_,
 331                     )
 332                     .map(|item| match item.kind {
 333                         ty::AssocKind::Fn => "method",
 334                         ty::AssocKind::Const => "associatedconstant",
 335                         ty::AssocKind::Type => "associatedtype",
 336                     })
 337                     .map(|out| (prim, Some(format!("{}#{}.{}", path, out, item_str))));
 338                 if let Some(link) = link {
 339                     return Ok(link);
 340                 }
 341             }
 342             debug!(
 343                 "returning primitive error for {}::{} in {} namespace",
 344                 path,
 345                 item_name,
 346                 ns.descr()
 347             );
 348             return Err(ResolutionFailure::NotResolved {
 349                 module_id,
 350                 partial_res: Some(prim),
 351                 unresolved: item_str.into(),
 352             }
 353             .into());
 354         }
 355
 356         let ty_res = cx
 357             .enter_resolver(|resolver| {
 358                 // only types can have associated items
 359                 resolver.resolve_str_path_error(DUMMY_SP, &path_root, TypeNS, module_id)
 360             })
 361             .map(|(_, res)| res);
 362         let ty_res = match ty_res {
 363             Err(()) | Ok(Res::Err) => {
 364                 return if ns == Namespace::ValueNS {
 365                     self.variant_field(path_str, current_item, module_id)
 366                 } else {
 367                     Err(ResolutionFailure::NotResolved {
 368                         module_id,
 369                         partial_res: None,
 370                         unresolved: path_root.into(),
 371                     }
 372                     .into())
 373                 };
 374             }
 375             Ok(res) => res,
 376         };
 377         let ty_res = ty_res.map_id(|_| panic!("unexpected node_id"));
 378         let res = match ty_res {
 379             Res::Def(DefKind::Struct | DefKind::Union | DefKind::Enum | DefKind::TyAlias, did) => {
 380                 debug!("looking for associated item named {} for item {:?}", item_name, did);
 381                 // Checks if item_name belongs to `impl SomeItem`
 382                 let assoc_item = cx
 383                     .tcx
 384                     .inherent_impls(did)
 385                     .iter()
 386                     .flat_map(|&imp| {
 387                         cx.tcx.associated_items(imp).find_by_name_and_namespace(
 388                             cx.tcx,
 389                             Ident::with_dummy_span(item_name),
 390                             ns,
 391                             imp,
 392                         )
 393                     })
 394                     .map(|item| (item.kind, item.def_id))
 395                     // There should only ever be one associated item that matches from any inherent impl
 396                     .next()
 397                     // Check if item_name belongs to `impl SomeTrait for SomeItem`
 398                     // This gives precedence to `impl SomeItem`:
 399                     // Although having both would be ambiguous, use impl version for compat. sake.
 400                     // To handle that properly resolve() would have to support
 401                     // something like [`ambi_fn`](<SomeStruct as SomeTrait>::ambi_fn)
 402                     .or_else(|| {
 403                         let kind =
 404                             resolve_associated_trait_item(did, module_id, item_name, ns, &self.cx);
 405                         debug!("got associated item kind {:?}", kind);
 406                         kind
 407                     });
 408
 409                 if let Some((kind, id)) = assoc_item {
 410                     let out = match kind {
 411                         ty::AssocKind::Fn => "method",
 412                         ty::AssocKind::Const => "associatedconstant",
 413                         ty::AssocKind::Type => "associatedtype",
 414                     };
 415                     Some(if extra_fragment.is_some() {
 416                         Err(ErrorKind::AnchorFailure(AnchorFailure::RustdocAnchorConflict(ty_res)))
 417                     } else {
 418                         // HACK(jynelson): `clean` expects the type, not the associated item.
 419                         // but the disambiguator logic expects the associated item.
 420                         // Store the kind in a side channel so that only the disambiguator logic looks at it.
 421                         self.kind_side_channel.set(Some((kind.as_def_kind(), id)));
 422                         Ok((ty_res, Some(format!("{}.{}", out, item_str))))
 423                     })
 424                 } else if ns == Namespace::ValueNS {
 425                     debug!("looking for variants or fields named {} for {:?}", item_name, did);
 426                     match cx.tcx.type_of(did).kind() {
 427                         ty::Adt(def, _) => {
 428                             let field = if def.is_enum() {
 429                                 def.all_fields().find(|item| item.ident.name == item_name)
 430                             } else {
 431                                 def.non_enum_variant()
 432                                     .fields
 433                                     .iter()
 434                                     .find(|item| item.ident.name == item_name)
 435                             };
 436                             field.map(|item| {
 437                                 if extra_fragment.is_some() {
 438                                     let res = Res::Def(
 439                                         if def.is_enum() {
 440                                             DefKind::Variant
 441                                         } else {
 442                                             DefKind::Field
 443                                         },
 444                                         item.did,
 445                                     );
 446                                     Err(ErrorKind::AnchorFailure(
 447                                         AnchorFailure::RustdocAnchorConflict(res),
 448                                     ))
 449                                 } else {
 450                                     Ok((
 451                                         ty_res,
 452                                         Some(format!(
 453                                             "{}.{}",
 454                                             if def.is_enum() { "variant" } else { "structfield" },
 455                                             item.ident
 456                                         )),
 457                                     ))
 458                                 }
 459                             })
 460                         }
 461                         _ => None,
 462                     }
 463                 } else {
 464                     // We already know this isn't in ValueNS, so no need to check variant_field
 465                     return Err(ResolutionFailure::NotResolved {
 466                         module_id,
 467                         partial_res: Some(ty_res),
 468                         unresolved: item_str.into(),
 469                     }
 470                     .into());
 471                 }
 472             }
 473             Res::Def(DefKind::Trait, did) => cx
 474                 .tcx
 475                 .associated_items(did)
 476                 .find_by_name_and_namespace(cx.tcx, Ident::with_dummy_span(item_name), ns, did)
 477                 .map(|item| {
 478                     let kind = match item.kind {
 479                         ty::AssocKind::Const => "associatedconstant",
 480                         ty::AssocKind::Type => "associatedtype",
 481                         ty::AssocKind::Fn => {
 482                             if item.defaultness.has_value() {
 483                                 "method"
 484                             } else {
 485                                 "tymethod"
 486                             }
 487                         }
 488                     };
 489
 490                     if extra_fragment.is_some() {
 491                         Err(ErrorKind::AnchorFailure(AnchorFailure::RustdocAnchorConflict(ty_res)))
 492                     } else {
 493                         let res = Res::Def(item.kind.as_def_kind(), item.def_id);
 494                         Ok((res, Some(format!("{}.{}", kind, item_str))))
 495                     }
 496                 }),
 497             _ => None,
 498         };
 499         res.unwrap_or_else(|| {
 500             if ns == Namespace::ValueNS {
 501                 self.variant_field(path_str, current_item, module_id)
 502             } else {
 503                 Err(ResolutionFailure::NotResolved {
 504                     module_id,
 505                     partial_res: Some(ty_res),
 506                     unresolved: item_str.into(),
 507                 }
 508                 .into())
 509             }
 510         })
 511     }
 512
 513     /// Used for reporting better errors.
 514     ///
 515     /// Returns whether the link resolved 'fully' in another namespace.
 516     /// 'fully' here means that all parts of the link resolved, not just some path segments.
 517     /// This returns the `Res` even if it was erroneous for some reason
 518     /// (such as having invalid URL fragments or being in the wrong namespace).
 519     fn check_full_res(
 520         &self,
 521         ns: Namespace,
 522         path_str: &str,
 523         module_id: DefId,
 524         current_item: &Option<String>,
 525         extra_fragment: &Option<String>,
 526     ) -> Option<Res> {
 527         let check_full_res_inner = |this: &Self, result: Result<Res, ErrorKind<'_>>| {
 528             let res = match result {
 529                 Ok(res) => Some(res),
 530                 Err(ErrorKind::Resolve(box kind)) => kind.full_res(),
 531                 Err(ErrorKind::AnchorFailure(AnchorFailure::RustdocAnchorConflict(res))) => {
 532                     Some(res)
 533                 }
 534                 Err(ErrorKind::AnchorFailure(AnchorFailure::MultipleAnchors)) => None,
 535             };
 536             this.kind_side_channel.take().map(|(kind, id)| Res::Def(kind, id)).or(res)
 537         };
 538         // cannot be used for macro namespace
 539         let check_full_res = |this: &Self, ns| {
 540             let result = this.resolve(path_str, ns, current_item, module_id, extra_fragment);
 541             check_full_res_inner(this, result.map(|(res, _)| res))
 542         };
 543         let check_full_res_macro = |this: &Self| {
 544             let result = this.macro_resolve(path_str, module_id);
 545             check_full_res_inner(this, result.map_err(ErrorKind::from))
 546         };
 547         match ns {
 548             Namespace::MacroNS => check_full_res_macro(self),
 549             Namespace::TypeNS | Namespace::ValueNS => check_full_res(self, ns),
 550         }
 551     }
 552 }
 553
 554 fn resolve_associated_trait_item(
 555     did: DefId,
 556     module: DefId,
 557     item_name: Symbol,
 558     ns: Namespace,
 559     cx: &DocContext<'_>,
 560 ) -> Option<(ty::AssocKind, DefId)> {
 561     let ty = cx.tcx.type_of(did);
 562     // First consider automatic impls: `impl From<T> for T`
 563     let implicit_impls = crate::clean::get_auto_trait_and_blanket_impls(cx, ty, did);
 564     let mut candidates: Vec<_> = implicit_impls
 565         .flat_map(|impl_outer| {
 566             match impl_outer.inner {
 567                 ImplItem(impl_) => {
 568                     debug!("considering auto or blanket impl for trait {:?}", impl_.trait_);
 569                     // Give precedence to methods that were overridden
 570                     if !impl_.provided_trait_methods.contains(&*item_name.as_str()) {
 571                         let mut items = impl_.items.into_iter().filter_map(|assoc| {
 572                             if assoc.name.as_deref() != Some(&*item_name.as_str()) {
 573                                 return None;
 574                             }
 575                             let kind = assoc
 576                                 .inner
 577                                 .as_assoc_kind()
 578                                 .expect("inner items for a trait should be associated items");
 579                             if kind.namespace() != ns {
 580                                 return None;
 581                             }
 582
 583                             trace!("considering associated item {:?}", assoc.inner);
 584                             // We have a slight issue: normal methods come from `clean` types,
 585                             // but provided methods come directly from `tcx`.
 586                             // Fortunately, we don't need the whole method, we just need to know
 587                             // what kind of associated item it is.
 588                             Some((kind, assoc.def_id))
 589                         });
 590                         let assoc = items.next();
 591                         debug_assert_eq!(items.count(), 0);
 592                         assoc
 593                     } else {
 594                         // These are provided methods or default types:
 595                         // ```
 596                         // trait T {
 597                         //   type A = usize;
 598                         //   fn has_default() -> A { 0 }
 599                         // }
 600                         // ```
 601                         let trait_ = impl_.trait_.unwrap().def_id().unwrap();
 602                         cx.tcx
 603                             .associated_items(trait_)
 604                             .find_by_name_and_namespace(
 605                                 cx.tcx,
 606                                 Ident::with_dummy_span(item_name),
 607                                 ns,
 608                                 trait_,
 609                             )
 610                             .map(|assoc| (assoc.kind, assoc.def_id))
 611                     }
 612                 }
 613                 _ => panic!("get_impls returned something that wasn't an impl"),
 614             }
 615         })
 616         .collect();
 617
 618     // Next consider explicit impls: `impl MyTrait for MyType`
 619     // Give precedence to inherent impls.
 620     if candidates.is_empty() {
 621         let traits = traits_implemented_by(cx, did, module);
 622         debug!("considering traits {:?}", traits);
 623         candidates.extend(traits.iter().filter_map(|&trait_| {
 624             cx.tcx
 625                 .associated_items(trait_)
 626                 .find_by_name_and_namespace(cx.tcx, Ident::with_dummy_span(item_name), ns, trait_)
 627                 .map(|assoc| (assoc.kind, assoc.def_id))
 628         }));
 629     }
 630     // FIXME: warn about ambiguity
 631     debug!("the candidates were {:?}", candidates);
 632     candidates.pop()
 633 }
 634
 635 /// Given a type, return all traits in scope in `module` implemented by that type.
 636 ///
 637 /// NOTE: this cannot be a query because more traits could be available when more crates are compiled!
 638 /// So it is not stable to serialize cross-crate.
 639 fn traits_implemented_by(cx: &DocContext<'_>, type_: DefId, module: DefId) -> FxHashSet<DefId> {
 640     let mut cache = cx.module_trait_cache.borrow_mut();
 641     let in_scope_traits = cache.entry(module).or_insert_with(|| {
 642         cx.enter_resolver(|resolver| {
 643             resolver.traits_in_scope(module).into_iter().map(|candidate| candidate.def_id).collect()
 644         })
 645     });
 646
 647     let ty = cx.tcx.type_of(type_);
 648     let iter = in_scope_traits.iter().flat_map(|&trait_| {
 649         trace!("considering explicit impl for trait {:?}", trait_);
 650         let mut saw_impl = false;
 651         // Look at each trait implementation to see if it's an impl for `did`
 652         cx.tcx.for_each_relevant_impl(trait_, ty, |impl_| {
 653             // FIXME: this is inefficient, find a way to short-circuit for_each_* so this doesn't take as long
 654             if saw_impl {
 655                 return;
 656             }
 657
 658             let trait_ref = cx.tcx.impl_trait_ref(impl_).expect("this is not an inherent impl");
 659             // Check if these are the same type.
 660             let impl_type = trait_ref.self_ty();
 661             trace!(
 662                 "comparing type {} with kind {:?} against type {:?}",
 663                 impl_type,
 664                 impl_type.kind(),
 665                 type_
 666             );
 667             // Fast path: if this is a primitive simple `==` will work
 668             saw_impl = impl_type == ty
 669                 || match impl_type.kind() {
 670                     // Check if these are the same def_id
 671                     ty::Adt(def, _) => {
 672                         debug!("adt def_id: {:?}", def.did);
 673                         def.did == type_
 674                     }
 675                     ty::Foreign(def_id) => *def_id == type_,
 676                     _ => false,
 677                 };
 678         });
 679         if saw_impl { Some(trait_) } else { None }
 680     });
 681     iter.collect()
 682 }
 683
 684 /// Check for resolve collisions between a trait and its derive
 685 ///
 686 /// These are common and we should just resolve to the trait in that case
 687 fn is_derive_trait_collision<T>(ns: &PerNS<Result<(Res, T), ResolutionFailure<'_>>>) -> bool {
 688     if let PerNS {
 689         type_ns: Ok((Res::Def(DefKind::Trait, _), _)),
 690         macro_ns: Ok((Res::Def(DefKind::Macro(MacroKind::Derive), _), _)),
 691         ..
 692     } = *ns
 693     {
 694         true
 695     } else {
 696         false
 697     }
 698 }
 699
 700 impl<'a, 'tcx> DocFolder for LinkCollector<'a, 'tcx> {
 701     fn fold_item(&mut self, mut item: Item) -> Option<Item> {
 702         use rustc_middle::ty::DefIdTree;
 703
 704         let parent_node = if item.is_fake() {
 705             // FIXME: is this correct?
 706             None
 707         // If we're documenting the crate root itself, it has no parent. Use the root instead.
 708         } else if item.def_id.is_top_level_module() {
 709             Some(item.def_id)
 710         } else {
 711             let mut current = item.def_id;
 712             // The immediate parent might not always be a module.
 713             // Find the first parent which is.
 714             loop {
 715                 if let Some(parent) = self.cx.tcx.parent(current) {
 716                     if self.cx.tcx.def_kind(parent) == DefKind::Mod {
 717                         break Some(parent);
 718                     }
 719                     current = parent;
 720                 } else {
 721                     debug!(
 722                         "{:?} has no parent (kind={:?}, original was {:?})",
 723                         current,
 724                         self.cx.tcx.def_kind(current),
 725                         item.def_id
 726                     );
 727                     break None;
 728                 }
 729             }
 730         };
 731
 732         if parent_node.is_some() {
 733             trace!("got parent node for {:?} {:?}, id {:?}", item.type_(), item.name, item.def_id);
 734         }
 735
 736         let current_item = match item.inner {
 737             ModuleItem(..) => {
 738                 if item.attrs.inner_docs {
 739                     if item.def_id.is_top_level_module() { item.name.clone() } else { None }
 740                 } else {
 741                     match parent_node.or(self.mod_ids.last().copied()) {
 742                         Some(parent) if !parent.is_top_level_module() => {
 743                             // FIXME: can we pull the parent module's name from elsewhere?
 744                             Some(self.cx.tcx.item_name(parent).to_string())
 745                         }
 746                         _ => None,
 747                     }
 748                 }
 749             }
 750             ImplItem(Impl { ref for_, .. }) => {
 751                 for_.def_id().map(|did| self.cx.tcx.item_name(did).to_string())
 752             }
 753             // we don't display docs on `extern crate` items anyway, so don't process them.
 754             ExternCrateItem(..) => {
 755                 debug!("ignoring extern crate item {:?}", item.def_id);
 756                 return self.fold_item_recur(item);
 757             }
 758             ImportItem(Import::Simple(ref name, ..)) => Some(name.clone()),
 759             MacroItem(..) => None,
 760             _ => item.name.clone(),
 761         };
 762
 763         if item.is_mod() && item.attrs.inner_docs {
 764             self.mod_ids.push(item.def_id);
 765         }
 766
 767         let dox = item.attrs.collapsed_doc_value().unwrap_or_else(String::new);
 768         trace!("got documentation '{}'", dox);
 769
 770         // find item's parent to resolve `Self` in item's docs below
 771         let parent_name = self.cx.as_local_hir_id(item.def_id).and_then(|item_hir| {
 772             let parent_hir = self.cx.tcx.hir().get_parent_item(item_hir);
 773             let item_parent = self.cx.tcx.hir().find(parent_hir);
 774             match item_parent {
 775                 Some(hir::Node::Item(hir::Item {
 776                     kind:
 777                         hir::ItemKind::Impl {
 778                             self_ty:
 779                                 hir::Ty {
 780                                     kind:
 781                                         hir::TyKind::Path(hir::QPath::Resolved(
 782                                             _,
 783                                             hir::Path { segments, .. },
 784                                         )),
 785                                     ..
 786                                 },
 787                             ..
 788                         },
 789                     ..
 790                 })) => segments.first().map(|seg| seg.ident.to_string()),
 791                 Some(hir::Node::Item(hir::Item {
 792                     ident, kind: hir::ItemKind::Enum(..), ..
 793                 }))
 794                 | Some(hir::Node::Item(hir::Item {
 795                     ident, kind: hir::ItemKind::Struct(..), ..
 796                 }))
 797                 | Some(hir::Node::Item(hir::Item {
 798                     ident, kind: hir::ItemKind::Union(..), ..
 799                 }))
 800                 | Some(hir::Node::Item(hir::Item {
 801                     ident, kind: hir::ItemKind::Trait(..), ..
 802                 })) => Some(ident.to_string()),
 803                 _ => None,
 804             }
 805         });
 806
 807         for (ori_link, link_range) in markdown_links(&dox) {
 808             self.resolve_link(
 809                 &mut item,
 810                 &dox,
 811                 &current_item,
 812                 parent_node,
 813                 &parent_name,
 814                 ori_link,
 815                 link_range,
 816             );
 817         }
 818
 819         if item.is_mod() && !item.attrs.inner_docs {
 820             self.mod_ids.push(item.def_id);
 821         }
 822
 823         if item.is_mod() {
 824             let ret = self.fold_item_recur(item);
 825
 826             self.mod_ids.pop();
 827
 828             ret
 829         } else {
 830             self.fold_item_recur(item)
 831         }
 832     }
 833 }
 834
 835 impl LinkCollector<'_, '_> {
 836     fn resolve_link(
 837         &self,
 838         item: &mut Item,
 839         dox: &str,
 840         current_item: &Option<String>,
 841         parent_node: Option<DefId>,
 842         parent_name: &Option<String>,
 843         ori_link: String,
 844         link_range: Option<Range<usize>>,
 845     ) {
 846         trace!("considering link '{}'", ori_link);
 847
 848         // Bail early for real links.
 849         if ori_link.contains('/') {
 850             return;
 851         }
 852
 853         // [] is mostly likely not supposed to be a link
 854         if ori_link.is_empty() {
 855             return;
 856         }
 857
 858         let cx = self.cx;
 859         let link = ori_link.replace("`", "");
 860         let parts = link.split('#').collect::<Vec<_>>();
 861         let (link, extra_fragment) = if parts.len() > 2 {
 862             anchor_failure(cx, &item, &link, dox, link_range, AnchorFailure::MultipleAnchors);
 863             return;
 864         } else if parts.len() == 2 {
 865             if parts[0].trim().is_empty() {
 866                 // This is an anchor to an element of the current page, nothing to do in here!
 867                 return;
 868             }
 869             (parts[0], Some(parts[1].to_owned()))
 870         } else {
 871             (parts[0], None)
 872         };
 873         let resolved_self;
 874         let link_text;
 875         let mut path_str;
 876         let disambiguator;
 877         let (mut res, mut fragment) = {
 878             path_str = if let Ok((d, path)) = Disambiguator::from_str(&link) {
 879                 disambiguator = Some(d);
 880                 path
 881             } else {
 882                 disambiguator = None;
 883                 &link
 884             }
 885             .trim();
 886
 887             if path_str.contains(|ch: char| !(ch.is_alphanumeric() || ch == ':' || ch == '_')) {
 888                 return;
 889             }
 890
 891             // We stripped `()` and `!` when parsing the disambiguator.
 892             // Add them back to be displayed, but not prefix disambiguators.
 893             link_text = disambiguator
 894                 .map(|d| d.display_for(path_str))
 895                 .unwrap_or_else(|| path_str.to_owned());
 896
 897             // In order to correctly resolve intra-doc-links we need to
 898             // pick a base AST node to work from.  If the documentation for
 899             // this module came from an inner comment (//!) then we anchor
 900             // our name resolution *inside* the module.  If, on the other
 901             // hand it was an outer comment (///) then we anchor the name
 902             // resolution in the parent module on the basis that the names
 903             // used are more likely to be intended to be parent names.  For
 904             // this, we set base_node to None for inner comments since
 905             // we've already pushed this node onto the resolution stack but
 906             // for outer comments we explicitly try and resolve against the
 907             // parent_node first.
 908             let base_node = if item.is_mod() && item.attrs.inner_docs {
 909                 self.mod_ids.last().copied()
 910             } else {
 911                 parent_node
 912             };
 913
 914             let module_id = if let Some(id) = base_node {
 915                 id
 916             } else {
 917                 debug!("attempting to resolve item without parent module: {}", path_str);
 918                 let err_kind = ResolutionFailure::NoParentItem.into();
 919                 resolution_failure(
 920                     self,
 921                     &item,
 922                     path_str,
 923                     disambiguator,
 924                     dox,
 925                     link_range,
 926                     smallvec![err_kind],
 927                 );
 928                 return;
 929             };
 930
 931             // replace `Self` with suitable item's parent name
 932             if path_str.starts_with("Self::") {
 933                 if let Some(ref name) = parent_name {
 934                     resolved_self = format!("{}::{}", name, &path_str[6..]);
 935                     path_str = &resolved_self;
 936                 }
 937             }
 938
 939             match self.resolve_with_disambiguator(
 940                 disambiguator,
 941                 item,
 942                 dox,
 943                 path_str,
 944                 current_item,
 945                 module_id,
 946                 extra_fragment,
 947                 &ori_link,
 948                 link_range.clone(),
 949             ) {
 950                 Some(x) => x,
 951                 None => return,
 952             }
 953         };
 954
 955         // Check for a primitive which might conflict with a module
 956         // Report the ambiguity and require that the user specify which one they meant.
 957         // FIXME: could there ever be a primitive not in the type namespace?
 958         if matches!(
 959             disambiguator,
 960             None | Some(Disambiguator::Namespace(Namespace::TypeNS) | Disambiguator::Primitive)
 961         ) && !matches!(res, Res::PrimTy(_))
 962         {
 963             if let Some((path, prim)) = is_primitive(path_str, TypeNS) {
 964                 // `prim@char`
 965                 if matches!(disambiguator, Some(Disambiguator::Primitive)) {
 966                     if fragment.is_some() {
 967                         anchor_failure(
 968                             cx,
 969                             &item,
 970                             path_str,
 971                             dox,
 972                             link_range,
 973                             AnchorFailure::RustdocAnchorConflict(prim),
 974                         );
 975                         return;
 976                     }
 977                     res = prim;
 978                     fragment = Some(path.to_owned());
 979                 } else {
 980                     // `[char]` when a `char` module is in scope
 981                     let candidates = vec![res, prim];
 982                     ambiguity_error(cx, &item, path_str, dox, link_range, candidates);
 983                     return;
 984                 }
 985             }
 986         }
 987
 988         let report_mismatch = |specified: Disambiguator, resolved: Disambiguator| {
 989             // The resolved item did not match the disambiguator; give a better error than 'not found'
 990             let msg = format!("incompatible link kind for `{}`", path_str);
 991             report_diagnostic(cx, &msg, &item, dox, &link_range, |diag, sp| {
 992                 let note = format!(
 993                     "this link resolved to {} {}, which is not {} {}",
 994                     resolved.article(),
 995                     resolved.descr(),
 996                     specified.article(),
 997                     specified.descr()
 998                 );
 999                 diag.note(&note);
1000                 suggest_disambiguator(resolved, diag, path_str, dox, sp, &link_range);
1001             });
1002         };
1003         if let Res::PrimTy(..) = res {
1004             match disambiguator {
1005                 Some(Disambiguator::Primitive | Disambiguator::Namespace(_)) | None => {
1006                     item.attrs.links.push(ItemLink {
1007                         link: ori_link,
1008                         link_text,
1009                         did: None,
1010                         fragment,
1011                     });
1012                 }
1013                 Some(other) => {
1014                     report_mismatch(other, Disambiguator::Primitive);
1015                     return;
1016                 }
1017             }
1018         } else {
1019             debug!("intra-doc link to {} resolved to {:?}", path_str, res);
1020
1021             // Disallow e.g. linking to enums with `struct@`
1022             if let Res::Def(kind, _) = res {
1023                 debug!("saw kind {:?} with disambiguator {:?}", kind, disambiguator);
1024                 match (self.kind_side_channel.take().map(|(kind, _)| kind).unwrap_or(kind), disambiguator) {
1025                     | (DefKind::Const | DefKind::ConstParam | DefKind::AssocConst | DefKind::AnonConst, Some(Disambiguator::Kind(DefKind::Const)))
1026                     // NOTE: this allows 'method' to mean both normal functions and associated functions
1027                     // This can't cause ambiguity because both are in the same namespace.
1028                     | (DefKind::Fn | DefKind::AssocFn, Some(Disambiguator::Kind(DefKind::Fn)))
1029                     // These are namespaces; allow anything in the namespace to match
1030                     | (_, Some(Disambiguator::Namespace(_)))
1031                     // If no disambiguator given, allow anything
1032                     | (_, None)
1033                     // All of these are valid, so do nothing
1034                     => {}
1035                     (actual, Some(Disambiguator::Kind(expected))) if actual == expected => {}
1036                     (_, Some(specified @ Disambiguator::Kind(_) | specified @ Disambiguator::Primitive)) => {
1037                         report_mismatch(specified, Disambiguator::Kind(kind));
1038                         return;
1039                     }
1040                 }
1041             }
1042
1043             // item can be non-local e.g. when using #[doc(primitive = "pointer")]
1044             if let Some((src_id, dst_id)) = res
1045                 .opt_def_id()
1046                 .and_then(|def_id| def_id.as_local())
1047                 .and_then(|dst_id| item.def_id.as_local().map(|src_id| (src_id, dst_id)))
1048             {
1049                 use rustc_hir::def_id::LOCAL_CRATE;
1050
1051                 let hir_src = self.cx.tcx.hir().local_def_id_to_hir_id(src_id);
1052                 let hir_dst = self.cx.tcx.hir().local_def_id_to_hir_id(dst_id);
1053
1054                 if self.cx.tcx.privacy_access_levels(LOCAL_CRATE).is_exported(hir_src)
1055                     && !self.cx.tcx.privacy_access_levels(LOCAL_CRATE).is_exported(hir_dst)
1056                 {
1057                     privacy_error(cx, &item, &path_str, dox, link_range);
1058                     return;
1059                 }
1060             }
1061             let id = register_res(cx, res);
1062             item.attrs.links.push(ItemLink { link: ori_link, link_text, did: Some(id), fragment });
1063         }
1064     }
1065
1066     fn resolve_with_disambiguator(
1067         &self,
1068         disambiguator: Option<Disambiguator>,
1069         item: &mut Item,
1070         dox: &str,
1071         path_str: &str,
1072         current_item: &Option<String>,
1073         base_node: DefId,
1074         extra_fragment: Option<String>,
1075         ori_link: &str,
1076         link_range: Option<Range<usize>>,
1077     ) -> Option<(Res, Option<String>)> {
1078         match disambiguator.map(Disambiguator::ns) {
1079             Some(ns @ (ValueNS | TypeNS)) => {
1080                 match self.resolve(path_str, ns, &current_item, base_node, &extra_fragment) {
1081                     Ok(res) => Some(res),
1082                     Err(ErrorKind::Resolve(box mut kind)) => {
1083                         // We only looked in one namespace. Try to give a better error if possible.
1084                         if kind.full_res().is_none() {
1085                             let other_ns = if ns == ValueNS { TypeNS } else { ValueNS };
1086                             // FIXME: really it should be `resolution_failure` that does this, not `resolve_with_disambiguator`
1087                             // See https://github.com/rust-lang/rust/pull/76955#discussion_r493953382 for a good approach
1088                             for &new_ns in &[other_ns, MacroNS] {
1089                                 if let Some(res) = self.check_full_res(
1090                                     new_ns,
1091                                     path_str,
1092                                     base_node,
1093                                     &current_item,
1094                                     &extra_fragment,
1095                                 ) {
1096                                     kind = ResolutionFailure::WrongNamespace(res, ns);
1097                                     break;
1098                                 }
1099                             }
1100                         }
1101                         resolution_failure(
1102                             self,
1103                             &item,
1104                             path_str,
1105                             disambiguator,
1106                             dox,
1107                             link_range,
1108                             smallvec![kind],
1109                         );
1110                         // This could just be a normal link or a broken link
1111                         // we could potentially check if something is
1112                         // "intra-doc-link-like" and warn in that case.
1113                         return None;
1114                     }
1115                     Err(ErrorKind::AnchorFailure(msg)) => {
1116                         anchor_failure(self.cx, &item, &ori_link, dox, link_range, msg);
1117                         return None;
1118                     }
1119                 }
1120             }
1121             None => {
1122                 // Try everything!
1123                 let mut candidates = PerNS {
1124                     macro_ns: self
1125                         .macro_resolve(path_str, base_node)
1126                         .map(|res| (res, extra_fragment.clone())),
1127                     type_ns: match self.resolve(
1128                         path_str,
1129                         TypeNS,
1130                         &current_item,
1131                         base_node,
1132                         &extra_fragment,
1133                     ) {
1134                         Ok(res) => {
1135                             debug!("got res in TypeNS: {:?}", res);
1136                             Ok(res)
1137                         }
1138                         Err(ErrorKind::AnchorFailure(msg)) => {
1139                             anchor_failure(self.cx, &item, ori_link, dox, link_range, msg);
1140                             return None;
1141                         }
1142                         Err(ErrorKind::Resolve(box kind)) => Err(kind),
1143                     },
1144                     value_ns: match self.resolve(
1145                         path_str,
1146                         ValueNS,
1147                         &current_item,
1148                         base_node,
1149                         &extra_fragment,
1150                     ) {
1151                         Ok(res) => Ok(res),
1152                         Err(ErrorKind::AnchorFailure(msg)) => {
1153                             anchor_failure(self.cx, &item, ori_link, dox, link_range, msg);
1154                             return None;
1155                         }
1156                         Err(ErrorKind::Resolve(box kind)) => Err(kind),
1157                     }
1158                     .and_then(|(res, fragment)| {
1159                         // Constructors are picked up in the type namespace.
1160                         match res {
1161                             Res::Def(DefKind::Ctor(..), _) | Res::SelfCtor(..) => {
1162                                 Err(ResolutionFailure::WrongNamespace(res, TypeNS))
1163                             }
1164                             _ => match (fragment, extra_fragment) {
1165                                 (Some(fragment), Some(_)) => {
1166                                     // Shouldn't happen but who knows?
1167                                     Ok((res, Some(fragment)))
1168                                 }
1169                                 (fragment, None) | (None, fragment) => Ok((res, fragment)),
1170                             },
1171                         }
1172                     }),
1173                 };
1174
1175                 let len = candidates.iter().filter(|res| res.is_ok()).count();
1176
1177                 if len == 0 {
1178                     resolution_failure(
1179                         self,
1180                         &item,
1181                         path_str,
1182                         disambiguator,
1183                         dox,
1184                         link_range,
1185                         candidates.into_iter().filter_map(|res| res.err()).collect(),
1186                     );
1187                     // this could just be a normal link
1188                     return None;
1189                 }
1190
1191                 if len == 1 {
1192                     Some(candidates.into_iter().filter_map(|res| res.ok()).next().unwrap())
1193                 } else if len == 2 && is_derive_trait_collision(&candidates) {
1194                     Some(candidates.type_ns.unwrap())
1195                 } else {
1196                     if is_derive_trait_collision(&candidates) {
1197                         candidates.macro_ns = Err(ResolutionFailure::Dummy);
1198                     }
1199                     // If we're reporting an ambiguity, don't mention the namespaces that failed
1200                     let candidates = candidates.map(|candidate| candidate.ok().map(|(res, _)| res));
1201                     ambiguity_error(
1202                         self.cx,
1203                         &item,
1204                         path_str,
1205                         dox,
1206                         link_range,
1207                         candidates.present_items().collect(),
1208                     );
1209                     return None;
1210                 }
1211             }
1212             Some(MacroNS) => {
1213                 match self.macro_resolve(path_str, base_node) {
1214                     Ok(res) => Some((res, extra_fragment)),
1215                     Err(mut kind) => {
1216                         // `macro_resolve` only looks in the macro namespace. Try to give a better error if possible.
1217                         for &ns in &[TypeNS, ValueNS] {
1218                             if let Some(res) = self.check_full_res(
1219                                 ns,
1220                                 path_str,
1221                                 base_node,
1222                                 &current_item,
1223                                 &extra_fragment,
1224                             ) {
1225                                 kind = ResolutionFailure::WrongNamespace(res, MacroNS);
1226                                 break;
1227                             }
1228                         }
1229                         resolution_failure(
1230                             self,
1231                             &item,
1232                             path_str,
1233                             disambiguator,
1234                             dox,
1235                             link_range,
1236                             smallvec![kind],
1237                         );
1238                         return None;
1239                     }
1240                 }
1241             }
1242         }
1243     }
1244 }
1245
1246 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
1247 enum Disambiguator {
1248     Primitive,
1249     Kind(DefKind),
1250     Namespace(Namespace),
1251 }
1252
1253 impl Disambiguator {
1254     /// The text that should be displayed when the path is rendered as HTML.
1255     ///
1256     /// NOTE: `path` is not the original link given by the user, but a name suitable for passing to `resolve`.
1257     fn display_for(&self, path: &str) -> String {
1258         match self {
1259             // FIXME: this will have different output if the user had `m!()` originally.
1260             Self::Kind(DefKind::Macro(MacroKind::Bang)) => format!("{}!", path),
1261             Self::Kind(DefKind::Fn) => format!("{}()", path),
1262             _ => path.to_owned(),
1263         }
1264     }
1265
1266     /// (disambiguator, path_str)
1267     fn from_str(link: &str) -> Result<(Self, &str), ()> {
1268         use Disambiguator::{Kind, Namespace as NS, Primitive};
1269
1270         let find_suffix = || {
1271             let suffixes = [
1272                 ("!()", DefKind::Macro(MacroKind::Bang)),
1273                 ("()", DefKind::Fn),
1274                 ("!", DefKind::Macro(MacroKind::Bang)),
1275             ];
1276             for &(suffix, kind) in &suffixes {
1277                 if link.ends_with(suffix) {
1278                     return Ok((Kind(kind), link.trim_end_matches(suffix)));
1279                 }
1280             }
1281             Err(())
1282         };
1283
1284         if let Some(idx) = link.find('@') {
1285             let (prefix, rest) = link.split_at(idx);
1286             let d = match prefix {
1287                 "struct" => Kind(DefKind::Struct),
1288                 "enum" => Kind(DefKind::Enum),
1289                 "trait" => Kind(DefKind::Trait),
1290                 "union" => Kind(DefKind::Union),
1291                 "module" | "mod" => Kind(DefKind::Mod),
1292                 "const" | "constant" => Kind(DefKind::Const),
1293                 "static" => Kind(DefKind::Static),
1294                 "function" | "fn" | "method" => Kind(DefKind::Fn),
1295                 "derive" => Kind(DefKind::Macro(MacroKind::Derive)),
1296                 "type" => NS(Namespace::TypeNS),
1297                 "value" => NS(Namespace::ValueNS),
1298                 "macro" => NS(Namespace::MacroNS),
1299                 "prim" | "primitive" => Primitive,
1300                 _ => return find_suffix(),
1301             };
1302             Ok((d, &rest[1..]))
1303         } else {
1304             find_suffix()
1305         }
1306     }
1307
1308     /// WARNING: panics on `Res::Err`
1309     fn from_res(res: Res) -> Self {
1310         match res {
1311             Res::Def(kind, _) => Disambiguator::Kind(kind),
1312             Res::PrimTy(_) => Disambiguator::Primitive,
1313             _ => Disambiguator::Namespace(res.ns().expect("can't call `from_res` on Res::err")),
1314         }
1315     }
1316
1317     fn suggestion(self) -> Suggestion {
1318         let kind = match self {
1319             Disambiguator::Primitive => return Suggestion::Prefix("prim"),
1320             Disambiguator::Kind(kind) => kind,
1321             Disambiguator::Namespace(_) => panic!("display_for cannot be used on namespaces"),
1322         };
1323         if kind == DefKind::Macro(MacroKind::Bang) {
1324             return Suggestion::Macro;
1325         } else if kind == DefKind::Fn || kind == DefKind::AssocFn {
1326             return Suggestion::Function;
1327         }
1328
1329         let prefix = match kind {
1330             DefKind::Struct => "struct",
1331             DefKind::Enum => "enum",
1332             DefKind::Trait => "trait",
1333             DefKind::Union => "union",
1334             DefKind::Mod => "mod",
1335             DefKind::Const | DefKind::ConstParam | DefKind::AssocConst | DefKind::AnonConst => {
1336                 "const"
1337             }
1338             DefKind::Static => "static",
1339             DefKind::Macro(MacroKind::Derive) => "derive",
1340             // Now handle things that don't have a specific disambiguator
1341             _ => match kind
1342                 .ns()
1343                 .expect("tried to calculate a disambiguator for a def without a namespace?")
1344             {
1345                 Namespace::TypeNS => "type",
1346                 Namespace::ValueNS => "value",
1347                 Namespace::MacroNS => "macro",
1348             },
1349         };
1350
1351         Suggestion::Prefix(prefix)
1352     }
1353
1354     fn ns(self) -> Namespace {
1355         match self {
1356             Self::Namespace(n) => n,
1357             Self::Kind(k) => {
1358                 k.ns().expect("only DefKinds with a valid namespace can be disambiguators")
1359             }
1360             Self::Primitive => TypeNS,
1361         }
1362     }
1363
1364     fn article(self) -> &'static str {
1365         match self {
1366             Self::Namespace(_) => panic!("article() doesn't make sense for namespaces"),
1367             Self::Kind(k) => k.article(),
1368             Self::Primitive => "a",
1369         }
1370     }
1371
1372     fn descr(self) -> &'static str {
1373         match self {
1374             Self::Namespace(n) => n.descr(),
1375             // HACK(jynelson): by looking at the source I saw the DefId we pass
1376             // for `expected.descr()` doesn't matter, since it's not a crate
1377             Self::Kind(k) => k.descr(DefId::local(hir::def_id::DefIndex::from_usize(0))),
1378             Self::Primitive => "builtin type",
1379         }
1380     }
1381 }
1382
1383 enum Suggestion {
1384     Prefix(&'static str),
1385     Function,
1386     Macro,
1387 }
1388
1389 impl Suggestion {
1390     fn descr(&self) -> Cow<'static, str> {
1391         match self {
1392             Self::Prefix(x) => format!("prefix with `{}@`", x).into(),
1393             Self::Function => "add parentheses".into(),
1394             Self::Macro => "add an exclamation mark".into(),
1395         }
1396     }
1397
1398     fn as_help(&self, path_str: &str) -> String {
1399         // FIXME: if this is an implied shortcut link, it's bad style to suggest `@`
1400         match self {
1401             Self::Prefix(prefix) => format!("{}@{}", prefix, path_str),
1402             Self::Function => format!("{}()", path_str),
1403             Self::Macro => format!("{}!", path_str),
1404         }
1405     }
1406 }
1407
1408 /// Reports a diagnostic for an intra-doc link.
1409 ///
1410 /// If no link range is provided, or the source span of the link cannot be determined, the span of
1411 /// the entire documentation block is used for the lint. If a range is provided but the span
1412 /// calculation fails, a note is added to the diagnostic pointing to the link in the markdown.
1413 ///
1414 /// The `decorate` callback is invoked in all cases to allow further customization of the
1415 /// diagnostic before emission. If the span of the link was able to be determined, the second
1416 /// parameter of the callback will contain it, and the primary span of the diagnostic will be set
1417 /// to it.
1418 fn report_diagnostic(
1419     cx: &DocContext<'_>,
1420     msg: &str,
1421     item: &Item,
1422     dox: &str,
1423     link_range: &Option<Range<usize>>,
1424     decorate: impl FnOnce(&mut DiagnosticBuilder<'_>, Option<rustc_span::Span>),
1425 ) {
1426     let hir_id = match cx.as_local_hir_id(item.def_id) {
1427         Some(hir_id) => hir_id,
1428         None => {
1429             // If non-local, no need to check anything.
1430             info!("ignoring warning from parent crate: {}", msg);
1431             return;
1432         }
1433     };
1434
1435     let attrs = &item.attrs;
1436     let sp = span_of_attrs(attrs).unwrap_or(item.source.span());
1437
1438     cx.tcx.struct_span_lint_hir(lint::builtin::BROKEN_INTRA_DOC_LINKS, hir_id, sp, |lint| {
1439         let mut diag = lint.build(msg);
1440
1441         let span = link_range
1442             .as_ref()
1443             .and_then(|range| super::source_span_for_markdown_range(cx, dox, range, attrs));
1444
1445         if let Some(link_range) = link_range {
1446             if let Some(sp) = span {
1447                 diag.set_span(sp);
1448             } else {
1449                 // blah blah blah\nblah\nblah [blah] blah blah\nblah blah
1450                 //                       ^     ~~~~
1451                 //                       |     link_range
1452                 //                       last_new_line_offset
1453                 let last_new_line_offset = dox[..link_range.start].rfind('\n').map_or(0, |n| n + 1);
1454                 let line = dox[last_new_line_offset..].lines().next().unwrap_or("");
1455
1456                 // Print the line containing the `link_range` and manually mark it with '^'s.
1457                 diag.note(&format!(
1458                     "the link appears in this line:\n\n{line}\n\
1459                      {indicator: <before$}{indicator:^<found$}",
1460                     line = line,
1461                     indicator = "",
1462                     before = link_range.start - last_new_line_offset,
1463                     found = link_range.len(),
1464                 ));
1465             }
1466         }
1467
1468         decorate(&mut diag, span);
1469
1470         diag.emit();
1471     });
1472 }
1473
1474 fn resolution_failure(
1475     collector: &LinkCollector<'_, '_>,
1476     item: &Item,
1477     path_str: &str,
1478     disambiguator: Option<Disambiguator>,
1479     dox: &str,
1480     link_range: Option<Range<usize>>,
1481     kinds: SmallVec<[ResolutionFailure<'_>; 3]>,
1482 ) {
1483     report_diagnostic(
1484         collector.cx,
1485         &format!("unresolved link to `{}`", path_str),
1486         item,
1487         dox,
1488         &link_range,
1489         |diag, sp| {
1490             let item = |res: Res| {
1491                 format!(
1492                     "the {} `{}`",
1493                     res.descr(),
1494                     collector.cx.tcx.item_name(res.def_id()).to_string()
1495                 )
1496             };
1497             let assoc_item_not_allowed = |res: Res| {
1498                 let def_id = res.def_id();
1499                 let name = collector.cx.tcx.item_name(def_id);
1500                 format!(
1501                     "`{}` is {} {}, not a module or type, and cannot have associated items",
1502                     name,
1503                     res.article(),
1504                     res.descr()
1505                 )
1506             };
1507             // ignore duplicates
1508             let mut variants_seen = SmallVec::<[_; 3]>::new();
1509             for mut failure in kinds {
1510                 let variant = std::mem::discriminant(&failure);
1511                 if variants_seen.contains(&variant) {
1512                     continue;
1513                 }
1514                 variants_seen.push(variant);
1515
1516                 if let ResolutionFailure::NotResolved { module_id, partial_res, unresolved } =
1517                     &mut failure
1518                 {
1519                     use DefKind::*;
1520
1521                     let module_id = *module_id;
1522                     // FIXME(jynelson): this might conflict with my `Self` fix in #76467
1523                     // FIXME: maybe use itertools `collect_tuple` instead?
1524                     fn split(path: &str) -> Option<(&str, &str)> {
1525                         let mut splitter = path.rsplitn(2, "::");
1526                         splitter.next().and_then(|right| splitter.next().map(|left| (left, right)))
1527                     }
1528
1529                     // Check if _any_ parent of the path gets resolved.
1530                     // If so, report it and say the first which failed; if not, say the first path segment didn't resolve.
1531                     let mut name = path_str;
1532                     'outer: loop {
1533                         let (start, end) = if let Some(x) = split(name) {
1534                             x
1535                         } else {
1536                             // avoid bug that marked [Quux::Z] as missing Z, not Quux
1537                             if partial_res.is_none() {
1538                                 *unresolved = name.into();
1539                             }
1540                             break;
1541                         };
1542                         name = start;
1543                         for &ns in &[TypeNS, ValueNS, MacroNS] {
1544                             if let Some(res) =
1545                                 collector.check_full_res(ns, &start, module_id, &None, &None)
1546                             {
1547                                 debug!("found partial_res={:?}", res);
1548                                 *partial_res = Some(res);
1549                                 *unresolved = end.into();
1550                                 break 'outer;
1551                             }
1552                         }
1553                         *unresolved = end.into();
1554                     }
1555
1556                     let last_found_module = match *partial_res {
1557                         Some(Res::Def(DefKind::Mod, id)) => Some(id),
1558                         None => Some(module_id),
1559                         _ => None,
1560                     };
1561                     // See if this was a module: `[path]` or `[std::io::nope]`
1562                     if let Some(module) = last_found_module {
1563                         let module_name = collector.cx.tcx.item_name(module);
1564                         let note = format!(
1565                             "the module `{}` contains no item named `{}`",
1566                             module_name, unresolved
1567                         );
1568                         if let Some(span) = sp {
1569                             diag.span_label(span, &note);
1570                         } else {
1571                             diag.note(&note);
1572                         }
1573                         // If the link has `::` in it, assume it was meant to be an intra-doc link.
1574                         // Otherwise, the `[]` might be unrelated.
1575                         // FIXME: don't show this for autolinks (`<>`), `()` style links, or reference links
1576                         if !path_str.contains("::") {
1577                             diag.help(r#"to escape `[` and `]` characters, add '\' before them like `\[` or `\]`"#);
1578                         }
1579                         continue;
1580                     }
1581
1582                     // Otherwise, it must be an associated item or variant
1583                     let res = partial_res.expect("None case was handled by `last_found_module`");
1584                     let diagnostic_name;
1585                     let (kind, name) = match res {
1586                         Res::Def(kind, def_id) => {
1587                             diagnostic_name = collector.cx.tcx.item_name(def_id).as_str();
1588                             (Some(kind), &*diagnostic_name)
1589                         }
1590                         Res::PrimTy(ty) => (None, ty.name_str()),
1591                         _ => unreachable!("only ADTs and primitives are in scope at module level"),
1592                     };
1593                     let path_description = if let Some(kind) = kind {
1594                         match kind {
1595                             Mod | ForeignMod => "inner item",
1596                             Struct => "field or associated item",
1597                             Enum | Union => "variant or associated item",
1598                             Variant
1599                             | Field
1600                             | Closure
1601                             | Generator
1602                             | AssocTy
1603                             | AssocConst
1604                             | AssocFn
1605                             | Fn
1606                             | Macro(_)
1607                             | Const
1608                             | ConstParam
1609                             | ExternCrate
1610                             | Use
1611                             | LifetimeParam
1612                             | Ctor(_, _)
1613                             | AnonConst => {
1614                                 let note = assoc_item_not_allowed(res);
1615                                 if let Some(span) = sp {
1616                                     diag.span_label(span, &note);
1617                                 } else {
1618                                     diag.note(&note);
1619                                 }
1620                                 return;
1621                             }
1622                             Trait | TyAlias | ForeignTy | OpaqueTy | TraitAlias | TyParam
1623                             | Static => "associated item",
1624                             Impl | GlobalAsm => unreachable!("not a path"),
1625                         }
1626                     } else {
1627                         "associated item"
1628                     };
1629                     let note = format!(
1630                         "the {} `{}` has no {} named `{}`",
1631                         res.descr(),
1632                         name,
1633                         disambiguator.map_or(path_description, |d| d.descr()),
1634                         unresolved,
1635                     );
1636                     if let Some(span) = sp {
1637                         diag.span_label(span, &note);
1638                     } else {
1639                         diag.note(&note);
1640                     }
1641
1642                     continue;
1643                 }
1644                 let note = match failure {
1645                     ResolutionFailure::NotResolved { .. } => unreachable!("handled above"),
1646                     ResolutionFailure::Dummy => continue,
1647                     ResolutionFailure::WrongNamespace(res, expected_ns) => {
1648                         if let Res::Def(kind, _) = res {
1649                             let disambiguator = Disambiguator::Kind(kind);
1650                             suggest_disambiguator(
1651                                 disambiguator,
1652                                 diag,
1653                                 path_str,
1654                                 dox,
1655                                 sp,
1656                                 &link_range,
1657                             )
1658                         }
1659
1660                         format!(
1661                             "this link resolves to {}, which is not in the {} namespace",
1662                             item(res),
1663                             expected_ns.descr()
1664                         )
1665                     }
1666                     ResolutionFailure::NoParentItem => {
1667                         diag.level = rustc_errors::Level::Bug;
1668                         "all intra doc links should have a parent item".to_owned()
1669                     }
1670                 };
1671                 if let Some(span) = sp {
1672                     diag.span_label(span, &note);
1673                 } else {
1674                     diag.note(&note);
1675                 }
1676             }
1677         },
1678     );
1679 }
1680
1681 fn anchor_failure(
1682     cx: &DocContext<'_>,
1683     item: &Item,
1684     path_str: &str,
1685     dox: &str,
1686     link_range: Option<Range<usize>>,
1687     failure: AnchorFailure,
1688 ) {
1689     let msg = match failure {
1690         AnchorFailure::MultipleAnchors => format!("`{}` contains multiple anchors", path_str),
1691         AnchorFailure::RustdocAnchorConflict(res) => format!(
1692             "`{}` contains an anchor, but links to {kind}s are already anchored",
1693             path_str,
1694             kind = res.descr(),
1695         ),
1696     };
1697
1698     report_diagnostic(cx, &msg, item, dox, &link_range, |diag, sp| {
1699         if let Some(sp) = sp {
1700             diag.span_label(sp, "contains invalid anchor");
1701         }
1702     });
1703 }
1704
1705 fn ambiguity_error(
1706     cx: &DocContext<'_>,
1707     item: &Item,
1708     path_str: &str,
1709     dox: &str,
1710     link_range: Option<Range<usize>>,
1711     candidates: Vec<Res>,
1712 ) {
1713     let mut msg = format!("`{}` is ", path_str);
1714
1715     match candidates.as_slice() {
1716         [first_def, second_def] => {
1717             msg += &format!(
1718                 "both {} {} and {} {}",
1719                 first_def.article(),
1720                 first_def.descr(),
1721                 second_def.article(),
1722                 second_def.descr(),
1723             );
1724         }
1725         _ => {
1726             let mut candidates = candidates.iter().peekable();
1727             while let Some(res) = candidates.next() {
1728                 if candidates.peek().is_some() {
1729                     msg += &format!("{} {}, ", res.article(), res.descr());
1730                 } else {
1731                     msg += &format!("and {} {}", res.article(), res.descr());
1732                 }
1733             }
1734         }
1735     }
1736
1737     report_diagnostic(cx, &msg, item, dox, &link_range, |diag, sp| {
1738         if let Some(sp) = sp {
1739             diag.span_label(sp, "ambiguous link");
1740         } else {
1741             diag.note("ambiguous link");
1742         }
1743
1744         for res in candidates {
1745             let disambiguator = Disambiguator::from_res(res);
1746             suggest_disambiguator(disambiguator, diag, path_str, dox, sp, &link_range);
1747         }
1748     });
1749 }
1750
1751 fn suggest_disambiguator(
1752     disambiguator: Disambiguator,
1753     diag: &mut DiagnosticBuilder<'_>,
1754     path_str: &str,
1755     dox: &str,
1756     sp: Option<rustc_span::Span>,
1757     link_range: &Option<Range<usize>>,
1758 ) {
1759     let suggestion = disambiguator.suggestion();
1760     let help = format!("to link to the {}, {}", disambiguator.descr(), suggestion.descr());
1761
1762     if let Some(sp) = sp {
1763         let link_range = link_range.as_ref().expect("must have a link range if we have a span");
1764         let msg = if dox.bytes().nth(link_range.start) == Some(b'`') {
1765             format!("`{}`", suggestion.as_help(path_str))
1766         } else {
1767             suggestion.as_help(path_str)
1768         };
1769
1770         diag.span_suggestion(sp, &help, msg, Applicability::MaybeIncorrect);
1771     } else {
1772         diag.help(&format!("{}: {}", help, suggestion.as_help(path_str)));
1773     }
1774 }
1775
1776 fn privacy_error(
1777     cx: &DocContext<'_>,
1778     item: &Item,
1779     path_str: &str,
1780     dox: &str,
1781     link_range: Option<Range<usize>>,
1782 ) {
1783     let item_name = item.name.as_deref().unwrap_or("<unknown>");
1784     let msg =
1785         format!("public documentation for `{}` links to private item `{}`", item_name, path_str);
1786
1787     report_diagnostic(cx, &msg, item, dox, &link_range, |diag, sp| {
1788         if let Some(sp) = sp {
1789             diag.span_label(sp, "this item is private");
1790         }
1791
1792         let note_msg = if cx.render_options.document_private {
1793             "this link resolves only because you passed `--document-private-items`, but will break without"
1794         } else {
1795             "this link will resolve properly if you pass `--document-private-items`"
1796         };
1797         diag.note(note_msg);
1798     });
1799 }
1800
1801 /// Given an enum variant's res, return the res of its enum and the associated fragment.
1802 fn handle_variant(
1803     cx: &DocContext<'_>,
1804     res: Res,
1805     extra_fragment: &Option<String>,
1806 ) -> Result<(Res, Option<String>), ErrorKind<'static>> {
1807     use rustc_middle::ty::DefIdTree;
1808
1809     if extra_fragment.is_some() {
1810         return Err(ErrorKind::AnchorFailure(AnchorFailure::RustdocAnchorConflict(res)));
1811     }
1812     let parent = if let Some(parent) = cx.tcx.parent(res.def_id()) {
1813         parent
1814     } else {
1815         return Err(ResolutionFailure::NoParentItem.into());
1816     };
1817     let parent_def = Res::Def(DefKind::Enum, parent);
1818     let variant = cx.tcx.expect_variant_res(res);
1819     Ok((parent_def, Some(format!("variant.{}", variant.ident.name))))
1820 }
1821
1822 const PRIMITIVES: &[(&str, Res)] = &[
1823     ("u8", Res::PrimTy(hir::PrimTy::Uint(rustc_ast::UintTy::U8))),
1824     ("u16", Res::PrimTy(hir::PrimTy::Uint(rustc_ast::UintTy::U16))),
1825     ("u32", Res::PrimTy(hir::PrimTy::Uint(rustc_ast::UintTy::U32))),
1826     ("u64", Res::PrimTy(hir::PrimTy::Uint(rustc_ast::UintTy::U64))),
1827     ("u128", Res::PrimTy(hir::PrimTy::Uint(rustc_ast::UintTy::U128))),
1828     ("usize", Res::PrimTy(hir::PrimTy::Uint(rustc_ast::UintTy::Usize))),
1829     ("i8", Res::PrimTy(hir::PrimTy::Int(rustc_ast::IntTy::I8))),
1830     ("i16", Res::PrimTy(hir::PrimTy::Int(rustc_ast::IntTy::I16))),
1831     ("i32", Res::PrimTy(hir::PrimTy::Int(rustc_ast::IntTy::I32))),
1832     ("i64", Res::PrimTy(hir::PrimTy::Int(rustc_ast::IntTy::I64))),
1833     ("i128", Res::PrimTy(hir::PrimTy::Int(rustc_ast::IntTy::I128))),
1834     ("isize", Res::PrimTy(hir::PrimTy::Int(rustc_ast::IntTy::Isize))),
1835     ("f32", Res::PrimTy(hir::PrimTy::Float(rustc_ast::FloatTy::F32))),
1836     ("f64", Res::PrimTy(hir::PrimTy::Float(rustc_ast::FloatTy::F64))),
1837     ("str", Res::PrimTy(hir::PrimTy::Str)),
1838     ("bool", Res::PrimTy(hir::PrimTy::Bool)),
1839     ("true", Res::PrimTy(hir::PrimTy::Bool)),
1840     ("false", Res::PrimTy(hir::PrimTy::Bool)),
1841     ("char", Res::PrimTy(hir::PrimTy::Char)),
1842 ];
1843
1844 fn is_primitive(path_str: &str, ns: Namespace) -> Option<(&'static str, Res)> {
1845     if ns == TypeNS {
1846         PRIMITIVES
1847             .iter()
1848             .filter(|x| x.0 == path_str)
1849             .copied()
1850             .map(|x| if x.0 == "true" || x.0 == "false" { ("bool", x.1) } else { x })
1851             .next()
1852     } else {
1853         None
1854     }
1855 }
1856
1857 fn primitive_impl(cx: &DocContext<'_>, path_str: &str) -> Option<&'static SmallVec<[DefId; 4]>> {
1858     Some(PrimitiveType::from_symbol(Symbol::intern(path_str))?.impls(cx.tcx))
1859 }