src/librustdoc/html/toc.rs

   1 //! Table-of-contents creation.
   2
   3 /// A (recursive) table of contents
   4 #[derive(Debug, PartialEq)]
   5 pub(crate) struct Toc {
   6     /// The levels are strictly decreasing, i.e.
   7     ///
   8     /// `entries[0].level >= entries[1].level >= ...`
   9     ///
  10     /// Normally they are equal, but can differ in cases like A and B,
  11     /// both of which end up in the same `Toc` as they have the same
  12     /// parent (Main).
  13     ///
  14     /// ```text
  15     /// # Main
  16     /// ### A
  17     /// ## B
  18     /// ```
  19     entries: Vec<TocEntry>,
  20 }
  21
  22 impl Toc {
  23     fn count_entries_with_level(&self, level: u32) -> usize {
  24         self.entries.iter().filter(|e| e.level == level).count()
  25     }
  26 }
  27
  28 #[derive(Debug, PartialEq)]
  29 pub(crate) struct TocEntry {
  30     level: u32,
  31     sec_number: String,
  32     name: String,
  33     id: String,
  34     children: Toc,
  35 }
  36
  37 /// Progressive construction of a table of contents.
  38 #[derive(PartialEq)]
  39 pub(crate) struct TocBuilder {
  40     top_level: Toc,
  41     /// The current hierarchy of parent headings, the levels are
  42     /// strictly increasing (i.e., `chain[0].level < chain[1].level <
  43     /// ...`) with each entry being the most recent occurrence of a
  44     /// heading with that level (it doesn't include the most recent
  45     /// occurrences of every level, just, if it *is* in `chain` then
  46     /// it is the most recent one).
  47     ///
  48     /// We also have `chain[0].level <= top_level.entries[last]`.
  49     chain: Vec<TocEntry>,
  50 }
  51
  52 impl TocBuilder {
  53     pub(crate) fn new() -> TocBuilder {
  54         TocBuilder { top_level: Toc { entries: Vec::new() }, chain: Vec::new() }
  55     }
  56
  57     /// Converts into a true `Toc` struct.
  58     pub(crate) fn into_toc(mut self) -> Toc {
  59         // we know all levels are >= 1.
  60         self.fold_until(0);
  61         self.top_level
  62     }
  63
  64     /// Collapse the chain until the first heading more important than
  65     /// `level` (i.e., lower level)
  66     ///
  67     /// Example:
  68     ///
  69     /// ```text
  70     /// ## A
  71     /// # B
  72     /// # C
  73     /// ## D
  74     /// ## E
  75     /// ### F
  76     /// #### G
  77     /// ### H
  78     /// ```
  79     ///
  80     /// If we are considering H (i.e., level 3), then A and B are in
  81     /// self.top_level, D is in C.children, and C, E, F, G are in
  82     /// self.chain.
  83     ///
  84     /// When we attempt to push H, we realize that first G is not the
  85     /// parent (level is too high) so it is popped from chain and put
  86     /// into F.children, then F isn't the parent (level is equal, aka
  87     /// sibling), so it's also popped and put into E.children.
  88     ///
  89     /// This leaves us looking at E, which does have a smaller level,
  90     /// and, by construction, it's the most recent thing with smaller
  91     /// level, i.e., it's the immediate parent of H.
  92     fn fold_until(&mut self, level: u32) {
  93         let mut this = None;
  94         loop {
  95             match self.chain.pop() {
  96                 Some(mut next) => {
  97                     next.children.entries.extend(this);
  98                     if next.level < level {
  99                         // this is the parent we want, so return it to
 100                         // its rightful place.
 101                         self.chain.push(next);
 102                         return;
 103                     } else {
 104                         this = Some(next);
 105                     }
 106                 }
 107                 None => {
 108                     self.top_level.entries.extend(this);
 109                     return;
 110                 }
 111             }
 112         }
 113     }
 114
 115     /// Push a level `level` heading into the appropriate place in the
 116     /// hierarchy, returning a string containing the section number in
 117     /// `<num>.<num>.<num>` format.
 118     pub(crate) fn push(&mut self, level: u32, name: String, id: String) -> &str {
 119         assert!(level >= 1);
 120
 121         // collapse all previous sections into their parents until we
 122         // get to relevant heading (i.e., the first one with a smaller
 123         // level than us)
 124         self.fold_until(level);
 125
 126         let mut sec_number;
 127         {
 128             let (toc_level, toc) = match self.chain.last() {
 129                 None => {
 130                     sec_number = String::new();
 131                     (0, &self.top_level)
 132                 }
 133                 Some(entry) => {
 134                     sec_number = entry.sec_number.clone();
 135                     sec_number.push('.');
 136                     (entry.level, &entry.children)
 137                 }
 138             };
 139             // fill in any missing zeros, e.g., for
 140             // # Foo (1)
 141             // ### Bar (1.0.1)
 142             for _ in toc_level..level - 1 {
 143                 sec_number.push_str("0.");
 144             }
 145             let number = toc.count_entries_with_level(level);
 146             sec_number.push_str(&(number + 1).to_string())
 147         }
 148
 149         self.chain.push(TocEntry {
 150             level,
 151             name,
 152             sec_number,
 153             id,
 154             children: Toc { entries: Vec::new() },
 155         });
 156
 157         // get the thing we just pushed, so we can borrow the string
 158         // out of it with the right lifetime
 159         let just_inserted = self.chain.last_mut().unwrap();
 160         &just_inserted.sec_number
 161     }
 162 }
 163
 164 impl Toc {
 165     fn print_inner(&self, v: &mut String) {
 166         use std::fmt::Write as _;
 167
 168         v.push_str("<ul>");
 169         for entry in &self.entries {
 170             // recursively format this table of contents
 171             let _ = write!(
 172                 v,
 173                 "\n<li><a href=\"#{id}\">{num} {name}</a>",
 174                 id = entry.id,
 175                 num = entry.sec_number,
 176                 name = entry.name
 177             );
 178             entry.children.print_inner(&mut *v);
 179             v.push_str("</li>");
 180         }
 181         v.push_str("</ul>");
 182     }
 183     pub(crate) fn print(&self) -> String {
 184         let mut v = String::new();
 185         self.print_inner(&mut v);
 186         v
 187     }
 188 }
 189
 190 #[cfg(test)]
 191 mod tests;