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::strbuf::StrBuf;
  15
  16 /// A (recursive) table of contents
  17 #[deriving(Eq)]
  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     /// # Main
  28     /// ### A
  29     /// ## B
  30     entries: Vec<TocEntry>
  31 }
  32
  33 impl Toc {
  34     fn count_entries_with_level(&self, level: u32) -> uint {
  35         self.entries.iter().count(|e| e.level == level)
  36     }
  37 }
  38
  39 #[deriving(Eq)]
  40 pub struct TocEntry {
  41     level: u32,
  42     sec_number: ~str,
  43     name: ~str,
  44     id: ~str,
  45     children: Toc,
  46 }
  47
  48 /// Progressive construction of a table of contents.
  49 #[deriving(Eq)]
  50 pub struct TocBuilder {
  51     top_level: Toc,
  52     /// The current heirachy of parent headings, the levels are
  53     /// strictly increasing (i.e. chain[0].level < chain[1].level <
  54     /// ...) with each entry being the most recent occurance of a
  55     /// heading with that level (it doesn't include the most recent
  56     /// occurences of every level, just, if *is* in `chain` then is is
  57     /// the most recent one).
  58     ///
  59     /// We also have `chain[0].level <= top_level.entries[last]`.
  60     chain: Vec<TocEntry>
  61 }
  62
  63 impl TocBuilder {
  64     pub fn new() -> TocBuilder {
  65         TocBuilder { top_level: Toc { entries: Vec::new() }, chain: Vec::new() }
  66     }
  67
  68
  69     /// Convert into a true `Toc` struct.
  70     pub fn into_toc(mut self) -> Toc {
  71         // we know all levels are >= 1.
  72         self.fold_until(0);
  73         self.top_level
  74     }
  75
  76     /// Collapse the chain until the first heading more important than
  77     /// `level` (i.e. lower level)
  78     ///
  79     /// Example:
  80     ///
  81     /// ## A
  82     /// # B
  83     /// # C
  84     /// ## D
  85     /// ## E
  86     /// ### F
  87     /// #### G
  88     /// ### H
  89     ///
  90     /// If we are considering H (i.e. level 3), then A and B are in
  91     /// self.top_level, D is in C.children, and C, E, F, G are in
  92     /// self.chain.
  93     ///
  94     /// When we attempt to push H, we realise that first G is not the
  95     /// parent (level is too high) so it is popped from chain and put
  96     /// into F.children, then F isn't the parent (level is equal, aka
  97     /// sibling), so it's also popped and put into E.children.
  98     ///
  99     /// This leaves us looking at E, which does have a smaller level,
 100     /// and, by construction, it's the most recent thing with smaller
 101     /// level, i.e. it's the immediate parent of H.
 102     fn fold_until(&mut self, level: u32) {
 103         let mut this = None;
 104         loop {
 105             match self.chain.pop() {
 106                 Some(mut next) => {
 107                     this.map(|e| next.children.entries.push(e));
 108                     if next.level < level {
 109                         // this is the parent we want, so return it to
 110                         // its rightful place.
 111                         self.chain.push(next);
 112                         return
 113                     } else {
 114                         this = Some(next);
 115                     }
 116                 }
 117                 None => {
 118                     this.map(|e| self.top_level.entries.push(e));
 119                     return
 120                 }
 121             }
 122         }
 123     }
 124
 125     /// Push a level `level` heading into the appropriate place in the
 126     /// heirarchy, returning a string containing the section number in
 127     /// `<num>.<num>.<num>` format.
 128     pub fn push<'a>(&'a mut self, level: u32, name: ~str, id: ~str) -> &'a str {
 129         assert!(level >= 1);
 130
 131         // collapse all previous sections into their parents until we
 132         // get to relevant heading (i.e. the first one with a smaller
 133         // level than us)
 134         self.fold_until(level);
 135
 136         let mut sec_number;
 137         {
 138             let (toc_level, toc) = match self.chain.last() {
 139                 None => {
 140                     sec_number = StrBuf::new();
 141                     (0, &self.top_level)
 142                 }
 143                 Some(entry) => {
 144                     sec_number = StrBuf::from_str(entry.sec_number.clone());
 145                     sec_number.push_str(".");
 146                     (entry.level, &entry.children)
 147                 }
 148             };
 149             // fill in any missing zeros, e.g. for
 150             // # Foo (1)
 151             // ### Bar (1.0.1)
 152             for _ in range(toc_level, level - 1) {
 153                 sec_number.push_str("0.");
 154             }
 155             let number = toc.count_entries_with_level(level);
 156             sec_number.push_str(format!("{}", number + 1))
 157         }
 158
 159         self.chain.push(TocEntry {
 160             level: level,
 161             name: name,
 162             sec_number: sec_number.into_owned(),
 163             id: id,
 164             children: Toc { entries: Vec::new() }
 165         });
 166
 167         // get the thing we just pushed, so we can borrow the string
 168         // out of it with the right lifetime
 169         let just_inserted = self.chain.mut_last().unwrap();
 170         just_inserted.sec_number.as_slice()
 171     }
 172 }
 173
 174 impl fmt::Show for Toc {
 175     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 176         try!(write!(fmt.buf, "<ul>"));
 177         for entry in self.entries.iter() {
 178             // recursively format this table of contents (the
 179             // `{children}` is the key).
 180             try!(write!(fmt.buf,
 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.buf, "</ul>")
 187     }
 188 }
 189
 190 #[cfg(test)]
 191 mod test {
 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, $name.to_owned(), "".to_owned()), $name);
 204             }
 205         }
 206         push!(2, "0.1");
 207         push!(1, "1");
 208         {
 209             push!(2, "1.1");
 210             {
 211                 push!(3, "1.1.1");
 212                 push!(3, "1.1.2");
 213             }
 214             push!(2, "1.2");
 215             {
 216                 push!(3, "1.2.1");
 217                 push!(3, "1.2.2");
 218             }
 219         }
 220         push!(1, "2");
 221         push!(1, "3");
 222         {
 223             push!(4, "3.0.0.1");
 224             {
 225                 push!(6, "3.0.0.1.0.1");
 226             }
 227             push!(4, "3.0.0.2");
 228             push!(2, "3.1");
 229             {
 230                 push!(4, "3.1.0.1");
 231             }
 232         }
 233
 234         macro_rules! toc {
 235             ($(($level: expr, $name: expr, $(($sub: tt))* )),*) => {
 236                 Toc {
 237                     entries: vec!(
 238                         $(
 239                             TocEntry {
 240                                 level: $level,
 241                                 name: $name.to_owned(),
 242                                 sec_number: $name.to_owned(),
 243                                 id: "".to_owned(),
 244                                 children: toc!($($sub),*)
 245                             }
 246                             ),*
 247                         )
 248                 }
 249             }
 250         }
 251         let expected = toc!(
 252             (2, "0.1", ),
 253
 254             (1, "1",
 255              ((2, "1.1", ((3, "1.1.1", )) ((3, "1.1.2", ))))
 256              ((2, "1.2", ((3, "1.2.1", )) ((3, "1.2.2", ))))
 257              ),
 258
 259             (1, "2", ),
 260
 261             (1, "3",
 262              ((4, "3.0.0.1", ((6, "3.0.0.1.0.1", ))))
 263              ((4, "3.0.0.2", ))
 264              ((2, "3.1", ((4, "3.1.0.1", ))))
 265              )
 266             );
 267         assert_eq!(expected, builder.into_toc());
 268     }
 269 }