src/tools/linkchecker/main.rs

   1 //! Script to check the validity of `href` links in our HTML documentation.
   2 //!
   3 //! In the past we've been quite error prone to writing in broken links as most
   4 //! of them are manually rather than automatically added. As files move over
   5 //! time or apis change old links become stale or broken. The purpose of this
   6 //! script is to check all relative links in our documentation to make sure they
   7 //! actually point to a valid place.
   8 //!
   9 //! Currently this doesn't actually do any HTML parsing or anything fancy like
  10 //! that, it just has a simple "regex" to search for `href` and `id` tags.
  11 //! These values are then translated to file URLs if possible and then the
  12 //! destination is asserted to exist.
  13 //!
  14 //! A few exceptions are allowed as there's known bugs in rustdoc, but this
  15 //! should catch the majority of "broken link" cases.
  16
  17 use std::cell::RefCell;
  18 use std::collections::{HashMap, HashSet};
  19 use std::env;
  20 use std::fs;
  21 use std::io::ErrorKind;
  22 use std::path::{Component, Path, PathBuf};
  23 use std::rc::Rc;
  24 use std::time::Instant;
  25
  26 use once_cell::sync::Lazy;
  27 use regex::Regex;
  28
  29 // Add linkcheck exceptions here
  30 // If at all possible you should use intra-doc links to avoid linkcheck issues. These
  31 // are cases where that does not work
  32 // [(generated_documentation_page, &[broken_links])]
  33 #[rustfmt::skip]
  34 const LINKCHECK_EXCEPTIONS: &[(&str, &[&str])] = &[
  35     // These try to link to std::collections, but are defined in alloc
  36     // https://github.com/rust-lang/rust/issues/74481
  37     ("std/collections/btree_map/struct.BTreeMap.html", &["#insert-and-complex-keys"]),
  38     ("std/collections/btree_set/struct.BTreeSet.html", &["#insert-and-complex-keys"]),
  39     ("alloc/collections/btree_map/struct.BTreeMap.html", &["#insert-and-complex-keys"]),
  40     ("alloc/collections/btree_set/struct.BTreeSet.html", &["#insert-and-complex-keys"]),
  41
  42     // These try to link to various things in std, but are defined in core.
  43     // The docs in std::primitive use proper intra-doc links, so these seem fine to special-case.
  44     // Most these are broken because liballoc uses `#[lang_item]` magic to define things on
  45     // primitives that aren't available in core.
  46     ("alloc/slice/trait.Join.html", &["#method.join"]),
  47     ("alloc/slice/trait.Concat.html", &["#method.concat"]),
  48     ("alloc/slice/index.html", &["#method.concat", "#method.join"]),
  49     ("alloc/vec/struct.Vec.html", &["#method.sort_by_key", "#method.sort_by_cached_key"]),
  50     ("core/primitive.str.html", &["#method.to_ascii_uppercase", "#method.to_ascii_lowercase"]),
  51     ("core/primitive.slice.html", &["#method.to_ascii_uppercase", "#method.to_ascii_lowercase",
  52                                     "core/slice::sort_by_key", "core\\slice::sort_by_key",
  53                                     "#method.sort_by_cached_key"]),
  54 ];
  55
  56 #[rustfmt::skip]
  57 const INTRA_DOC_LINK_EXCEPTIONS: &[(&str, &[&str])] = &[
  58     // This will never have links that are not in other pages.
  59     // To avoid repeating the exceptions twice, an empty list means all broken links are allowed.
  60     ("reference/print.html", &[]),
  61     // All the reference 'links' are actually ENBF highlighted as code
  62     ("reference/comments.html", &[
  63          "/</code> <code>!",
  64          "*</code> <code>!",
  65     ]),
  66     ("reference/identifiers.html", &[
  67          "a</code>-<code>z</code> <code>A</code>-<code>Z",
  68          "a</code>-<code>z</code> <code>A</code>-<code>Z</code> <code>0</code>-<code>9</code> <code>_",
  69          "a</code>-<code>z</code> <code>A</code>-<code>Z</code>] [<code>a</code>-<code>z</code> <code>A</code>-<code>Z</code> <code>0</code>-<code>9</code> <code>_",
  70     ]),
  71     ("reference/tokens.html", &[
  72          "0</code>-<code>1",
  73          "0</code>-<code>7",
  74          "0</code>-<code>9",
  75          "0</code>-<code>9",
  76          "0</code>-<code>9</code> <code>a</code>-<code>f</code> <code>A</code>-<code>F",
  77     ]),
  78     ("reference/notation.html", &[
  79          "b</code> <code>B",
  80          "a</code>-<code>z",
  81     ]),
  82     // This is being used in the sense of 'inclusive range', not a markdown link
  83     ("core/ops/struct.RangeInclusive.html", &["begin</code>, <code>end"]),
  84     ("std/ops/struct.RangeInclusive.html", &["begin</code>, <code>end"]),
  85     ("core/slice/trait.SliceIndex.html", &["begin</code>, <code>end"]),
  86     ("alloc/slice/trait.SliceIndex.html", &["begin</code>, <code>end"]),
  87     ("std/slice/trait.SliceIndex.html", &["begin</code>, <code>end"]),
  88     ("core/primitive.str.html", &["begin</code>, <code>end"]),
  89     ("std/primitive.str.html", &["begin</code>, <code>end"]),
  90
  91 ];
  92
  93 static BROKEN_INTRA_DOC_LINK: Lazy<Regex> =
  94     Lazy::new(|| Regex::new(r#"\[<code>(.*)</code>\]"#).unwrap());
  95
  96 macro_rules! t {
  97     ($e:expr) => {
  98         match $e {
  99             Ok(e) => e,
 100             Err(e) => panic!("{} failed with {:?}", stringify!($e), e),
 101         }
 102     };
 103 }
 104
 105 fn main() {
 106     let docs = env::args_os().nth(1).expect("doc path should be first argument");
 107     let docs = env::current_dir().unwrap().join(docs);
 108     let mut checker = Checker { root: docs.clone(), cache: HashMap::new() };
 109     let mut report = Report {
 110         errors: 0,
 111         start: Instant::now(),
 112         html_files: 0,
 113         html_redirects: 0,
 114         links_checked: 0,
 115         links_ignored_external: 0,
 116         links_ignored_exception: 0,
 117         intra_doc_exceptions: 0,
 118     };
 119     checker.walk(&docs, &mut report);
 120     report.report();
 121     if report.errors != 0 {
 122         println!("found some broken links");
 123         std::process::exit(1);
 124     }
 125 }
 126
 127 struct Checker {
 128     root: PathBuf,
 129     cache: Cache,
 130 }
 131
 132 struct Report {
 133     errors: u32,
 134     start: Instant,
 135     html_files: u32,
 136     html_redirects: u32,
 137     links_checked: u32,
 138     links_ignored_external: u32,
 139     links_ignored_exception: u32,
 140     intra_doc_exceptions: u32,
 141 }
 142
 143 /// A cache entry.
 144 enum FileEntry {
 145     /// An HTML file.
 146     ///
 147     /// This includes the contents of the HTML file, and an optional set of
 148     /// HTML IDs. The IDs are used for checking fragments. They are computed
 149     /// as-needed. The source is discarded (replaced with an empty string)
 150     /// after the file has been checked, to conserve on memory.
 151     HtmlFile { source: Rc<String>, ids: RefCell<HashSet<String>> },
 152     /// This file is an HTML redirect to the given local path.
 153     Redirect { target: PathBuf },
 154     /// This is not an HTML file.
 155     OtherFile,
 156     /// This is a directory.
 157     Dir,
 158     /// The file doesn't exist.
 159     Missing,
 160 }
 161
 162 /// A cache to speed up file access.
 163 type Cache = HashMap<String, FileEntry>;
 164
 165 fn small_url_encode(s: &str) -> String {
 166     s.replace("<", "%3C")
 167         .replace(">", "%3E")
 168         .replace(" ", "%20")
 169         .replace("?", "%3F")
 170         .replace("'", "%27")
 171         .replace("&", "%26")
 172         .replace(",", "%2C")
 173         .replace(":", "%3A")
 174         .replace(";", "%3B")
 175         .replace("[", "%5B")
 176         .replace("]", "%5D")
 177         .replace("\"", "%22")
 178 }
 179
 180 impl Checker {
 181     /// Primary entry point for walking the filesystem to find HTML files to check.
 182     fn walk(&mut self, dir: &Path, report: &mut Report) {
 183         for entry in t!(dir.read_dir()).map(|e| t!(e)) {
 184             let path = entry.path();
 185             // Goes through symlinks
 186             let metadata = t!(fs::metadata(&path));
 187             if metadata.is_dir() {
 188                 self.walk(&path, report);
 189             } else {
 190                 self.check(&path, report);
 191             }
 192         }
 193     }
 194
 195     /// Checks a single file.
 196     fn check(&mut self, file: &Path, report: &mut Report) {
 197         let (pretty_path, entry) = self.load_file(file, report);
 198         let source = match entry {
 199             FileEntry::Missing => panic!("missing file {:?} while walking", file),
 200             FileEntry::Dir => unreachable!("never with `check` path"),
 201             FileEntry::OtherFile => return,
 202             FileEntry::Redirect { .. } => return,
 203             FileEntry::HtmlFile { source, ids } => {
 204                 parse_ids(&mut ids.borrow_mut(), &pretty_path, source, report);
 205                 source.clone()
 206             }
 207         };
 208
 209         // Search for anything that's the regex 'href[ ]*=[ ]*".*?"'
 210         with_attrs_in_source(&source, " href", |url, i, base| {
 211             // Ignore external URLs
 212             if url.starts_with("http:")
 213                 || url.starts_with("https:")
 214                 || url.starts_with("javascript:")
 215                 || url.starts_with("ftp:")
 216                 || url.starts_with("irc:")
 217                 || url.starts_with("data:")
 218                 || url.starts_with("mailto:")
 219             {
 220                 report.links_ignored_external += 1;
 221                 return;
 222             }
 223             report.links_checked += 1;
 224             let (url, fragment) = match url.split_once('#') {
 225                 None => (url, None),
 226                 Some((url, fragment)) => (url, Some(fragment)),
 227             };
 228             // NB: the `splitn` always succeeds, even if the delimiter is not present.
 229             let url = url.splitn(2, '?').next().unwrap();
 230
 231             // Once we've plucked out the URL, parse it using our base url and
 232             // then try to extract a file path.
 233             let mut path = file.to_path_buf();
 234             if !base.is_empty() || !url.is_empty() {
 235                 path.pop();
 236                 for part in Path::new(base).join(url).components() {
 237                     match part {
 238                         Component::Prefix(_) | Component::RootDir => {
 239                             // Avoid absolute paths as they make the docs not
 240                             // relocatable by making assumptions on where the docs
 241                             // are hosted relative to the site root.
 242                             report.errors += 1;
 243                             println!(
 244                                 "{}:{}: absolute path - {}",
 245                                 pretty_path,
 246                                 i + 1,
 247                                 Path::new(base).join(url).display()
 248                             );
 249                             return;
 250                         }
 251                         Component::CurDir => {}
 252                         Component::ParentDir => {
 253                             path.pop();
 254                         }
 255                         Component::Normal(s) => {
 256                             path.push(s);
 257                         }
 258                     }
 259                 }
 260             }
 261
 262             let (target_pretty_path, target_entry) = self.load_file(&path, report);
 263             let (target_source, target_ids) = match target_entry {
 264                 FileEntry::Missing => {
 265                     if is_exception(file, &target_pretty_path) {
 266                         report.links_ignored_exception += 1;
 267                     } else {
 268                         report.errors += 1;
 269                         println!(
 270                             "{}:{}: broken link - `{}`",
 271                             pretty_path,
 272                             i + 1,
 273                             target_pretty_path
 274                         );
 275                     }
 276                     return;
 277                 }
 278                 FileEntry::Dir => {
 279                     // Links to directories show as directory listings when viewing
 280                     // the docs offline so it's best to avoid them.
 281                     report.errors += 1;
 282                     println!(
 283                         "{}:{}: directory link to `{}` \
 284                          (directory links should use index.html instead)",
 285                         pretty_path,
 286                         i + 1,
 287                         target_pretty_path
 288                     );
 289                     return;
 290                 }
 291                 FileEntry::OtherFile => return,
 292                 FileEntry::Redirect { target } => {
 293                     let t = target.clone();
 294                     drop(target);
 295                     let (target, redir_entry) = self.load_file(&t, report);
 296                     match redir_entry {
 297                         FileEntry::Missing => {
 298                             report.errors += 1;
 299                             println!(
 300                                 "{}:{}: broken redirect from `{}` to `{}`",
 301                                 pretty_path,
 302                                 i + 1,
 303                                 target_pretty_path,
 304                                 target
 305                             );
 306                             return;
 307                         }
 308                         FileEntry::Redirect { target } => {
 309                             // Redirect to a redirect, this link checker
 310                             // currently doesn't support this, since it would
 311                             // require cycle checking, etc.
 312                             report.errors += 1;
 313                             println!(
 314                                 "{}:{}: redirect from `{}` to `{}` \
 315                                  which is also a redirect (not supported)",
 316                                 pretty_path,
 317                                 i + 1,
 318                                 target_pretty_path,
 319                                 target.display()
 320                             );
 321                             return;
 322                         }
 323                         FileEntry::Dir => {
 324                             report.errors += 1;
 325                             println!(
 326                                 "{}:{}: redirect from `{}` to `{}` \
 327                                  which is a directory \
 328                                  (directory links should use index.html instead)",
 329                                 pretty_path,
 330                                 i + 1,
 331                                 target_pretty_path,
 332                                 target
 333                             );
 334                             return;
 335                         }
 336                         FileEntry::OtherFile => return,
 337                         FileEntry::HtmlFile { source, ids } => (source, ids),
 338                     }
 339                 }
 340                 FileEntry::HtmlFile { source, ids } => (source, ids),
 341             };
 342
 343             // Alright, if we've found an HTML file for the target link. If
 344             // this is a fragment link, also check that the `id` exists.
 345             if let Some(ref fragment) = fragment {
 346                 // Fragments like `#1-6` are most likely line numbers to be
 347                 // interpreted by javascript, so we're ignoring these
 348                 if fragment.splitn(2, '-').all(|f| f.chars().all(|c| c.is_numeric())) {
 349                     return;
 350                 }
 351
 352                 parse_ids(&mut target_ids.borrow_mut(), &pretty_path, target_source, report);
 353
 354                 if target_ids.borrow().contains(*fragment) {
 355                     return;
 356                 }
 357
 358                 if is_exception(file, &format!("#{}", fragment)) {
 359                     report.links_ignored_exception += 1;
 360                 } else {
 361                     report.errors += 1;
 362                     print!("{}:{}: broken link fragment ", pretty_path, i + 1);
 363                     println!("`#{}` pointing to `{}`", fragment, target_pretty_path);
 364                 };
 365             }
 366         });
 367
 368         // Search for intra-doc links that rustdoc didn't warn about
 369         // FIXME(#77199, 77200) Rustdoc should just warn about these directly.
 370         // NOTE: only looks at one line at a time; in practice this should find most links
 371         for (i, line) in source.lines().enumerate() {
 372             for broken_link in BROKEN_INTRA_DOC_LINK.captures_iter(line) {
 373                 if is_intra_doc_exception(file, &broken_link[1]) {
 374                     report.intra_doc_exceptions += 1;
 375                 } else {
 376                     report.errors += 1;
 377                     print!("{}:{}: broken intra-doc link - ", pretty_path, i + 1);
 378                     println!("{}", &broken_link[0]);
 379                 }
 380             }
 381         }
 382         // we don't need the source anymore,
 383         // so drop to reduce memory-usage
 384         match self.cache.get_mut(&pretty_path).unwrap() {
 385             FileEntry::HtmlFile { source, .. } => *source = Rc::new(String::new()),
 386             _ => unreachable!("must be html file"),
 387         }
 388     }
 389
 390     /// Load a file from disk, or from the cache if available.
 391     fn load_file(&mut self, file: &Path, report: &mut Report) -> (String, &FileEntry) {
 392         // https://docs.microsoft.com/en-us/windows/win32/debug/system-error-codes--0-499-
 393         #[cfg(windows)]
 394         const ERROR_INVALID_NAME: i32 = 123;
 395
 396         let pretty_path =
 397             file.strip_prefix(&self.root).unwrap_or(&file).to_str().unwrap().to_string();
 398
 399         let entry =
 400             self.cache.entry(pretty_path.clone()).or_insert_with(|| match fs::metadata(file) {
 401                 Ok(metadata) if metadata.is_dir() => FileEntry::Dir,
 402                 Ok(_) => {
 403                     if file.extension().and_then(|s| s.to_str()) != Some("html") {
 404                         FileEntry::OtherFile
 405                     } else {
 406                         report.html_files += 1;
 407                         load_html_file(file, report)
 408                     }
 409                 }
 410                 Err(e) if e.kind() == ErrorKind::NotFound => FileEntry::Missing,
 411                 Err(e) => {
 412                     // If a broken intra-doc link contains `::`, on windows, it will cause `ERROR_INVALID_NAME` rather than `NotFound`.
 413                     // Explicitly check for that so that the broken link can be allowed in `LINKCHECK_EXCEPTIONS`.
 414                     #[cfg(windows)]
 415                     if e.raw_os_error() == Some(ERROR_INVALID_NAME)
 416                         && file.as_os_str().to_str().map_or(false, |s| s.contains("::"))
 417                     {
 418                         return FileEntry::Missing;
 419                     }
 420                     panic!("unexpected read error for {}: {}", file.display(), e);
 421                 }
 422             });
 423         (pretty_path, entry)
 424     }
 425 }
 426
 427 impl Report {
 428     fn report(&self) {
 429         println!("checked links in: {:.1}s", self.start.elapsed().as_secs_f64());
 430         println!("number of HTML files scanned: {}", self.html_files);
 431         println!("number of HTML redirects found: {}", self.html_redirects);
 432         println!("number of links checked: {}", self.links_checked);
 433         println!("number of links ignored due to external: {}", self.links_ignored_external);
 434         println!("number of links ignored due to exceptions: {}", self.links_ignored_exception);
 435         println!("number of intra doc links ignored: {}", self.intra_doc_exceptions);
 436         println!("errors found: {}", self.errors);
 437     }
 438 }
 439
 440 fn load_html_file(file: &Path, report: &mut Report) -> FileEntry {
 441     let source = match fs::read_to_string(file) {
 442         Ok(s) => Rc::new(s),
 443         Err(err) => {
 444             // This usually should not fail since `metadata` was already
 445             // called successfully on this file.
 446             panic!("unexpected read error for {}: {}", file.display(), err);
 447         }
 448     };
 449     match maybe_redirect(&source) {
 450         Some(target) => {
 451             report.html_redirects += 1;
 452             let target = file.parent().unwrap().join(target);
 453             FileEntry::Redirect { target }
 454         }
 455         None => FileEntry::HtmlFile { source: source.clone(), ids: RefCell::new(HashSet::new()) },
 456     }
 457 }
 458
 459 fn is_intra_doc_exception(file: &Path, link: &str) -> bool {
 460     if let Some(entry) = INTRA_DOC_LINK_EXCEPTIONS.iter().find(|&(f, _)| file.ends_with(f)) {
 461         entry.1.is_empty() || entry.1.contains(&link)
 462     } else {
 463         false
 464     }
 465 }
 466
 467 fn is_exception(file: &Path, link: &str) -> bool {
 468     if let Some(entry) = LINKCHECK_EXCEPTIONS.iter().find(|&(f, _)| file.ends_with(f)) {
 469         entry.1.contains(&link)
 470     } else {
 471         // FIXME(#63351): Concat trait in alloc/slice reexported in primitive page
 472         //
 473         // NOTE: This cannot be added to `LINKCHECK_EXCEPTIONS` because the resolved path
 474         // calculated in `check` function is outside `build/<triple>/doc` dir.
 475         // So the `strip_prefix` method just returns the old absolute broken path.
 476         if file.ends_with("std/primitive.slice.html") {
 477             if link.ends_with("primitive.slice.html") {
 478                 return true;
 479             }
 480         }
 481         false
 482     }
 483 }
 484
 485 /// If the given HTML file contents is an HTML redirect, this returns the
 486 /// destination path given in the redirect.
 487 fn maybe_redirect(source: &str) -> Option<String> {
 488     const REDIRECT_RUSTDOC: (usize, &str) = (7, "<p>Redirecting to <a href=");
 489     const REDIRECT_MDBOOK: (usize, &str) = (8 - 7, "<p>Redirecting to... <a href=");
 490
 491     let mut lines = source.lines();
 492
 493     let mut find_redirect = |(line_rel, redirect_pattern): (usize, &str)| {
 494         let redirect_line = lines.nth(line_rel)?;
 495
 496         redirect_line.find(redirect_pattern).map(|i| {
 497             let rest = &redirect_line[(i + redirect_pattern.len() + 1)..];
 498             let pos_quote = rest.find('"').unwrap();
 499             rest[..pos_quote].to_owned()
 500         })
 501     };
 502
 503     find_redirect(REDIRECT_RUSTDOC).or_else(|| find_redirect(REDIRECT_MDBOOK))
 504 }
 505
 506 fn with_attrs_in_source<F: FnMut(&str, usize, &str)>(source: &str, attr: &str, mut f: F) {
 507     let mut base = "";
 508     for (i, mut line) in source.lines().enumerate() {
 509         while let Some(j) = line.find(attr) {
 510             let rest = &line[j + attr.len()..];
 511             // The base tag should always be the first link in the document so
 512             // we can get away with using one pass.
 513             let is_base = line[..j].ends_with("<base");
 514             line = rest;
 515             let pos_equals = match rest.find('=') {
 516                 Some(i) => i,
 517                 None => continue,
 518             };
 519             if rest[..pos_equals].trim_start_matches(' ') != "" {
 520                 continue;
 521             }
 522
 523             let rest = &rest[pos_equals + 1..];
 524
 525             let pos_quote = match rest.find(&['"', '\''][..]) {
 526                 Some(i) => i,
 527                 None => continue,
 528             };
 529             let quote_delim = rest.as_bytes()[pos_quote] as char;
 530
 531             if rest[..pos_quote].trim_start_matches(' ') != "" {
 532                 continue;
 533             }
 534             let rest = &rest[pos_quote + 1..];
 535             let url = match rest.find(quote_delim) {
 536                 Some(i) => &rest[..i],
 537                 None => continue,
 538             };
 539             if is_base {
 540                 base = url;
 541                 continue;
 542             }
 543             f(url, i, base)
 544         }
 545     }
 546 }
 547
 548 fn parse_ids(ids: &mut HashSet<String>, file: &str, source: &str, report: &mut Report) {
 549     if ids.is_empty() {
 550         with_attrs_in_source(source, " id", |fragment, i, _| {
 551             let frag = fragment.trim_start_matches("#").to_owned();
 552             let encoded = small_url_encode(&frag);
 553             if !ids.insert(frag) {
 554                 report.errors += 1;
 555                 println!("{}:{}: id is not unique: `{}`", file, i, fragment);
 556             }
 557             // Just in case, we also add the encoded id.
 558             ids.insert(encoded);
 559         });
 560     }
 561 }