src/librustdoc/html/toc.rs

   1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Table-of-contents creation.
  12
  13 use std::fmt;
  14 use std::string::String;
  15
  16 /// A (recursive) table of contents
  17 #[derive(PartialEq)]
  18 pub struct Toc {
  19     /// The levels are strictly decreasing, i.e.
  20     ///
  21     /// entries[0].level >= entries[1].level >= ...
  22     ///
  23     /// Normally they are equal, but can differ in cases like A and B,
  24     /// both of which end up in the same `Toc` as they have the same
  25     /// parent (Main).
  26     ///
  27     /// ```text
  28     /// # Main
  29     /// ### A
  30     /// ## B
  31     /// ```
  32     entries: Vec<TocEntry>
  33 }
  34
  35 impl Toc {
  36     fn count_entries_with_level(&self, level: u32) -> usize {
  37         self.entries.iter().filter(|e| e.level == level).count()
  38     }
  39 }
  40
  41 #[derive(PartialEq)]
  42 pub struct TocEntry {
  43     level: u32,
  44     sec_number: String,
  45     name: String,
  46     id: String,
  47     children: Toc,
  48 }
  49
  50 /// Progressive construction of a table of contents.
  51 #[derive(PartialEq)]
  52 pub struct TocBuilder {
  53     top_level: Toc,
  54     /// The current hierarchy of parent headings, the levels are
  55     /// strictly increasing (i.e. chain[0].level < chain[1].level <
  56     /// ...) with each entry being the most recent occurrence of a
  57     /// heading with that level (it doesn't include the most recent
  58     /// occurrences of every level, just, if it *is* in `chain` then
  59     /// it is the most recent one).
  60     ///
  61     /// We also have `chain[0].level <= top_level.entries[last]`.
  62     chain: Vec<TocEntry>
  63 }
  64
  65 impl TocBuilder {
  66     pub fn new() -> TocBuilder {
  67         TocBuilder { top_level: Toc { entries: Vec::new() }, chain: Vec::new() }
  68     }
  69
  70
  71     /// Convert into a true `Toc` struct.
  72     pub fn into_toc(mut self) -> Toc {
  73         // we know all levels are >= 1.
  74         self.fold_until(0);
  75         self.top_level
  76     }
  77
  78     /// Collapse the chain until the first heading more important than
  79     /// `level` (i.e. lower level)
  80     ///
  81     /// Example:
  82     ///
  83     /// ```text
  84     /// ## A
  85     /// # B
  86     /// # C
  87     /// ## D
  88     /// ## E
  89     /// ### F
  90     /// #### G
  91     /// ### H
  92     /// ```
  93     ///
  94     /// If we are considering H (i.e. level 3), then A and B are in
  95     /// self.top_level, D is in C.children, and C, E, F, G are in
  96     /// self.chain.
  97     ///
  98     /// When we attempt to push H, we realize that first G is not the
  99     /// parent (level is too high) so it is popped from chain and put
 100     /// into F.children, then F isn't the parent (level is equal, aka
 101     /// sibling), so it's also popped and put into E.children.
 102     ///
 103     /// This leaves us looking at E, which does have a smaller level,
 104     /// and, by construction, it's the most recent thing with smaller
 105     /// level, i.e. it's the immediate parent of H.
 106     fn fold_until(&mut self, level: u32) {
 107         let mut this = None;
 108         loop {
 109             match self.chain.pop() {
 110                 Some(mut next) => {
 111                     this.map(|e| next.children.entries.push(e));
 112                     if next.level < level {
 113                         // this is the parent we want, so return it to
 114                         // its rightful place.
 115                         self.chain.push(next);
 116                         return
 117                     } else {
 118                         this = Some(next);
 119                     }
 120                 }
 121                 None => {
 122                     this.map(|e| self.top_level.entries.push(e));
 123                     return
 124                 }
 125             }
 126         }
 127     }
 128
 129     /// Push a level `level` heading into the appropriate place in the
 130     /// hierarchy, returning a string containing the section number in
 131     /// `<num>.<num>.<num>` format.
 132     pub fn push<'a>(&'a mut self, level: u32, name: String, id: String) -> &'a str {
 133         assert!(level >= 1);
 134
 135         // collapse all previous sections into their parents until we
 136         // get to relevant heading (i.e. the first one with a smaller
 137         // level than us)
 138         self.fold_until(level);
 139
 140         let mut sec_number;
 141         {
 142             let (toc_level, toc) = match self.chain.last() {
 143                 None => {
 144                     sec_number = String::new();
 145                     (0, &self.top_level)
 146                 }
 147                 Some(entry) => {
 148                     sec_number = entry.sec_number.clone();
 149                     sec_number.push_str(".");
 150                     (entry.level, &entry.children)
 151                 }
 152             };
 153             // fill in any missing zeros, e.g. for
 154             // # Foo (1)
 155             // ### Bar (1.0.1)
 156             for _ in toc_level..level - 1 {
 157                 sec_number.push_str("0.");
 158             }
 159             let number = toc.count_entries_with_level(level);
 160             sec_number.push_str(&(number + 1).to_string())
 161         }
 162
 163         self.chain.push(TocEntry {
 164             level,
 165             name,
 166             sec_number,
 167             id,
 168             children: Toc { entries: Vec::new() }
 169         });
 170
 171         // get the thing we just pushed, so we can borrow the string
 172         // out of it with the right lifetime
 173         let just_inserted = self.chain.last_mut().unwrap();
 174         &just_inserted.sec_number
 175     }
 176 }
 177
 178 impl fmt::Debug for Toc {
 179     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 180         fmt::Display::fmt(self, f)
 181     }
 182 }
 183
 184 impl fmt::Display for Toc {
 185     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 186         write!(fmt, "<ul>")?;
 187         for entry in &self.entries {
 188             // recursively format this table of contents (the
 189             // `{children}` is the key).
 190             write!(fmt,
 191                    "\n<li><a href=\"#{id}\">{num} {name}</a>{children}</li>",
 192                    id = entry.id,
 193                    num = entry.sec_number, name = entry.name,
 194                    children = entry.children)?
 195         }
 196         write!(fmt, "</ul>")
 197     }
 198 }
 199
 200 #[cfg(test)]
 201 mod tests {
 202     use super::{TocBuilder, Toc, TocEntry};
 203
 204     #[test]
 205     fn builder_smoke() {
 206         let mut builder = TocBuilder::new();
 207
 208         // this is purposely not using a fancy macro like below so
 209         // that we're sure that this is doing the correct thing, and
 210         // there's been no macro mistake.
 211         macro_rules! push {
 212             ($level: expr, $name: expr) => {
 213                 assert_eq!(builder.push($level,
 214                                         $name.to_string(),
 215                                         "".to_string()),
 216                            $name);
 217             }
 218         }
 219         push!(2, "0.1");
 220         push!(1, "1");
 221         {
 222             push!(2, "1.1");
 223             {
 224                 push!(3, "1.1.1");
 225                 push!(3, "1.1.2");
 226             }
 227             push!(2, "1.2");
 228             {
 229                 push!(3, "1.2.1");
 230                 push!(3, "1.2.2");
 231             }
 232         }
 233         push!(1, "2");
 234         push!(1, "3");
 235         {
 236             push!(4, "3.0.0.1");
 237             {
 238                 push!(6, "3.0.0.1.0.1");
 239             }
 240             push!(4, "3.0.0.2");
 241             push!(2, "3.1");
 242             {
 243                 push!(4, "3.1.0.1");
 244             }
 245         }
 246
 247         macro_rules! toc {
 248             ($(($level: expr, $name: expr, $(($sub: tt))* )),*) => {
 249                 Toc {
 250                     entries: vec![
 251                         $(
 252                             TocEntry {
 253                                 level: $level,
 254                                 name: $name.to_string(),
 255                                 sec_number: $name.to_string(),
 256                                 id: "".to_string(),
 257                                 children: toc!($($sub),*)
 258                             }
 259                             ),*
 260                         ]
 261                 }
 262             }
 263         }
 264         let expected = toc!(
 265             (2, "0.1", ),
 266
 267             (1, "1",
 268              ((2, "1.1", ((3, "1.1.1", )) ((3, "1.1.2", ))))
 269              ((2, "1.2", ((3, "1.2.1", )) ((3, "1.2.2", ))))
 270              ),
 271
 272             (1, "2", ),
 273
 274             (1, "3",
 275              ((4, "3.0.0.1", ((6, "3.0.0.1.0.1", ))))
 276              ((4, "3.0.0.2", ))
 277              ((2, "3.1", ((4, "3.1.0.1", ))))
 278              )
 279             );
 280         assert_eq!(expected, builder.into_toc());
 281     }
 282 }