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<'a>(&'a mut self, level: u32, name: String, id: String) -> &'a 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 {
 192     use super::{TocBuilder, Toc, TocEntry};
 193
 194     #[test]
 195     fn builder_smoke() {
 196         let mut builder = TocBuilder::new();
 197
 198         // this is purposely not using a fancy macro like below so
 199         // that we're sure that this is doing the correct thing, and
 200         // there's been no macro mistake.
 201         macro_rules! push {
 202             ($level: expr, $name: expr) => {
 203                 assert_eq!(builder.push($level,
 204                                         $name.to_string(),
 205                                         "".to_string()),
 206                            $name);
 207             }
 208         }
 209         push!(2, "0.1");
 210         push!(1, "1");
 211         {
 212             push!(2, "1.1");
 213             {
 214                 push!(3, "1.1.1");
 215                 push!(3, "1.1.2");
 216             }
 217             push!(2, "1.2");
 218             {
 219                 push!(3, "1.2.1");
 220                 push!(3, "1.2.2");
 221             }
 222         }
 223         push!(1, "2");
 224         push!(1, "3");
 225         {
 226             push!(4, "3.0.0.1");
 227             {
 228                 push!(6, "3.0.0.1.0.1");
 229             }
 230             push!(4, "3.0.0.2");
 231             push!(2, "3.1");
 232             {
 233                 push!(4, "3.1.0.1");
 234             }
 235         }
 236
 237         macro_rules! toc {
 238             ($(($level: expr, $name: expr, $(($sub: tt))* )),*) => {
 239                 Toc {
 240                     entries: vec![
 241                         $(
 242                             TocEntry {
 243                                 level: $level,
 244                                 name: $name.to_string(),
 245                                 sec_number: $name.to_string(),
 246                                 id: "".to_string(),
 247                                 children: toc!($($sub),*)
 248                             }
 249                             ),*
 250                         ]
 251                 }
 252             }
 253         }
 254         let expected = toc!(
 255             (2, "0.1", ),
 256
 257             (1, "1",
 258              ((2, "1.1", ((3, "1.1.1", )) ((3, "1.1.2", ))))
 259              ((2, "1.2", ((3, "1.2.1", )) ((3, "1.2.2", ))))
 260              ),
 261
 262             (1, "2", ),
 263
 264             (1, "3",
 265              ((4, "3.0.0.1", ((6, "3.0.0.1.0.1", ))))
 266              ((4, "3.0.0.2", ))
 267              ((2, "3.1", ((4, "3.1.0.1", ))))
 268              )
 269             );
 270         assert_eq!(expected, builder.into_toc());
 271     }
 272 }