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