src/librustdoc/html/toc.rs

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