src/librustdoc/html/toc.rs

   1 //! Table-of-contents creation.
   2
   3 /// A (recursive) table of contents
   4 #[derive(Debug, PartialEq)]
   5 pub 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 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 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 fn new() -> TocBuilder {
  54         TocBuilder { top_level: Toc { entries: Vec::new() }, chain: Vec::new() }
  55     }
  56
  57
  58     /// Converts into a true `Toc` struct.
  59     pub fn into_toc(mut self) -> Toc {
  60         // we know all levels are >= 1.
  61         self.fold_until(0);
  62         self.top_level
  63     }
  64
  65     /// Collapse the chain until the first heading more important than
  66     /// `level` (i.e., lower level)
  67     ///
  68     /// Example:
  69     ///
  70     /// ```text
  71     /// ## A
  72     /// # B
  73     /// # C
  74     /// ## D
  75     /// ## E
  76     /// ### F
  77     /// #### G
  78     /// ### H
  79     /// ```
  80     ///
  81     /// If we are considering H (i.e., level 3), then A and B are in
  82     /// self.top_level, D is in C.children, and C, E, F, G are in
  83     /// self.chain.
  84     ///
  85     /// When we attempt to push H, we realize that first G is not the
  86     /// parent (level is too high) so it is popped from chain and put
  87     /// into F.children, then F isn't the parent (level is equal, aka
  88     /// sibling), so it's also popped and put into E.children.
  89     ///
  90     /// This leaves us looking at E, which does have a smaller level,
  91     /// and, by construction, it's the most recent thing with smaller
  92     /// level, i.e., it's the immediate parent of H.
  93     fn fold_until(&mut self, level: u32) {
  94         let mut this = None;
  95         loop {
  96             match self.chain.pop() {
  97                 Some(mut next) => {
  98                     this.map(|e| next.children.entries.push(e));
  99                     if next.level < level {
 100                         // this is the parent we want, so return it to
 101                         // its rightful place.
 102                         self.chain.push(next);
 103                         return
 104                     } else {
 105                         this = Some(next);
 106                     }
 107                 }
 108                 None => {
 109                     this.map(|e| self.top_level.entries.push(e));
 110                     return
 111                 }
 112             }
 113         }
 114     }
 115
 116     /// Push a level `level` heading into the appropriate place in the
 117     /// hierarchy, returning a string containing the section number in
 118     /// `<num>.<num>.<num>` format.
 119     pub fn push(&mut self, level: u32, name: String, id: String) -> &str {
 120         assert!(level >= 1);
 121
 122         // collapse all previous sections into their parents until we
 123         // get to relevant heading (i.e., the first one with a smaller
 124         // level than us)
 125         self.fold_until(level);
 126
 127         let mut sec_number;
 128         {
 129             let (toc_level, toc) = match self.chain.last() {
 130                 None => {
 131                     sec_number = String::new();
 132                     (0, &self.top_level)
 133                 }
 134                 Some(entry) => {
 135                     sec_number = entry.sec_number.clone();
 136                     sec_number.push_str(".");
 137                     (entry.level, &entry.children)
 138                 }
 139             };
 140             // fill in any missing zeros, e.g., for
 141             // # Foo (1)
 142             // ### Bar (1.0.1)
 143             for _ in toc_level..level - 1 {
 144                 sec_number.push_str("0.");
 145             }
 146             let number = toc.count_entries_with_level(level);
 147             sec_number.push_str(&(number + 1).to_string())
 148         }
 149
 150         self.chain.push(TocEntry {
 151             level,
 152             name,
 153             sec_number,
 154             id,
 155             children: Toc { entries: Vec::new() }
 156         });
 157
 158         // get the thing we just pushed, so we can borrow the string
 159         // out of it with the right lifetime
 160         let just_inserted = self.chain.last_mut().unwrap();
 161         &just_inserted.sec_number
 162     }
 163 }
 164
 165 impl Toc {
 166     fn print_inner(&self, v: &mut String) {
 167         v.push_str("<ul>");
 168         for entry in &self.entries {
 169             // recursively format this table of contents
 170             v.push_str(&format!("\n<li><a href=\"#{id}\">{num} {name}</a>",
 171                    id = entry.id,
 172                    num = entry.sec_number, name = entry.name));
 173             entry.children.print_inner(&mut *v);
 174             v.push_str("</li>");
 175         }
 176         v.push_str("</ul>");
 177     }
 178     crate fn print(&self) -> String {
 179         let mut v = String::new();
 180         self.print_inner(&mut v);
 181         v
 182     }
 183 }
 184
 185 #[cfg(test)]
 186 mod tests;