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