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 #[deriving(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) -> uint {
  37         self.entries.iter().filter(|e| e.level == level).count()
  38     }
  39 }
  40
  41 #[deriving(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 #[deriving(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 *is* in `chain` then is is
  59     /// 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 realise 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 = String::from_str(entry.sec_number
 149                                                        .as_slice());
 150                     sec_number.push_str(".");
 151                     (entry.level, &entry.children)
 152                 }
 153             };
 154             // fill in any missing zeros, e.g. for
 155             // # Foo (1)
 156             // ### Bar (1.0.1)
 157             for _ in range(toc_level, level - 1) {
 158                 sec_number.push_str("0.");
 159             }
 160             let number = toc.count_entries_with_level(level);
 161             sec_number.push_str(format!("{}", number + 1).as_slice())
 162         }
 163
 164         self.chain.push(TocEntry {
 165             level: level,
 166             name: name,
 167             sec_number: sec_number,
 168             id: id,
 169             children: Toc { entries: Vec::new() }
 170         });
 171
 172         // get the thing we just pushed, so we can borrow the string
 173         // out of it with the right lifetime
 174         let just_inserted = self.chain.last_mut().unwrap();
 175         just_inserted.sec_number.as_slice()
 176     }
 177 }
 178
 179 impl fmt::Show for Toc {
 180     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 181         try!(write!(fmt, "<ul>"));
 182         for entry in self.entries.iter() {
 183             // recursively format this table of contents (the
 184             // `{children}` is the key).
 185             try!(write!(fmt,
 186                         "\n<li><a href=\"#{id}\">{num} {name}</a>{children}</li>",
 187                         id = entry.id,
 188                         num = entry.sec_number, name = entry.name,
 189                         children = entry.children))
 190         }
 191         write!(fmt, "</ul>")
 192     }
 193 }
 194
 195 #[cfg(test)]
 196 mod test {
 197     use super::{TocBuilder, Toc, TocEntry};
 198
 199     #[test]
 200     fn builder_smoke() {
 201         let mut builder = TocBuilder::new();
 202
 203         // this is purposely not using a fancy macro like below so
 204         // that we're sure that this is doing the correct thing, and
 205         // there's been no macro mistake.
 206         macro_rules! push {
 207             ($level: expr, $name: expr) => {
 208                 assert_eq!(builder.push($level,
 209                                         $name.to_string(),
 210                                         "".to_string()),
 211                            $name);
 212             }
 213         }
 214         push!(2, "0.1");
 215         push!(1, "1");
 216         {
 217             push!(2, "1.1");
 218             {
 219                 push!(3, "1.1.1");
 220                 push!(3, "1.1.2");
 221             }
 222             push!(2, "1.2");
 223             {
 224                 push!(3, "1.2.1");
 225                 push!(3, "1.2.2");
 226             }
 227         }
 228         push!(1, "2");
 229         push!(1, "3");
 230         {
 231             push!(4, "3.0.0.1");
 232             {
 233                 push!(6, "3.0.0.1.0.1");
 234             }
 235             push!(4, "3.0.0.2");
 236             push!(2, "3.1");
 237             {
 238                 push!(4, "3.1.0.1");
 239             }
 240         }
 241
 242         macro_rules! toc {
 243             ($(($level: expr, $name: expr, $(($sub: tt))* )),*) => {
 244                 Toc {
 245                     entries: vec!(
 246                         $(
 247                             TocEntry {
 248                                 level: $level,
 249                                 name: $name.to_string(),
 250                                 sec_number: $name.to_string(),
 251                                 id: "".to_string(),
 252                                 children: toc!($($sub),*)
 253                             }
 254                             ),*
 255                         )
 256                 }
 257             }
 258         }
 259         let expected = toc!(
 260             (2, "0.1", ),
 261
 262             (1, "1",
 263              ((2, "1.1", ((3, "1.1.1", )) ((3, "1.1.2", ))))
 264              ((2, "1.2", ((3, "1.2.1", )) ((3, "1.2.2", ))))
 265              ),
 266
 267             (1, "2", ),
 268
 269             (1, "3",
 270              ((4, "3.0.0.1", ((6, "3.0.0.1.0.1", ))))
 271              ((4, "3.0.0.2", ))
 272              ((2, "3.1", ((4, "3.1.0.1", ))))
 273              )
 274             );
 275         assert_eq!(expected, builder.into_toc());
 276     }
 277 }