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) -> uint {
  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 *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::Debug for Toc {
 180     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 181         fmt::Display::fmt(self, f)
 182     }
 183 }
 184
 185 impl fmt::Display for Toc {
 186     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 187         try!(write!(fmt, "<ul>"));
 188         for entry in self.entries.iter() {
 189             // recursively format this table of contents (the
 190             // `{children}` is the key).
 191             try!(write!(fmt,
 192                         "\n<li><a href=\"#{id}\">{num} {name}</a>{children}</li>",
 193                         id = entry.id,
 194                         num = entry.sec_number, name = entry.name,
 195                         children = entry.children))
 196         }
 197         write!(fmt, "</ul>")
 198     }
 199 }
 200
 201 #[cfg(test)]
 202 mod test {
 203     use super::{TocBuilder, Toc, TocEntry};
 204
 205     #[test]
 206     fn builder_smoke() {
 207         let mut builder = TocBuilder::new();
 208
 209         // this is purposely not using a fancy macro like below so
 210         // that we're sure that this is doing the correct thing, and
 211         // there's been no macro mistake.
 212         macro_rules! push {
 213             ($level: expr, $name: expr) => {
 214                 assert_eq!(builder.push($level,
 215                                         $name.to_string(),
 216                                         "".to_string()),
 217                            $name);
 218             }
 219         }
 220         push!(2, "0.1");
 221         push!(1, "1");
 222         {
 223             push!(2, "1.1");
 224             {
 225                 push!(3, "1.1.1");
 226                 push!(3, "1.1.2");
 227             }
 228             push!(2, "1.2");
 229             {
 230                 push!(3, "1.2.1");
 231                 push!(3, "1.2.2");
 232             }
 233         }
 234         push!(1, "2");
 235         push!(1, "3");
 236         {
 237             push!(4, "3.0.0.1");
 238             {
 239                 push!(6, "3.0.0.1.0.1");
 240             }
 241             push!(4, "3.0.0.2");
 242             push!(2, "3.1");
 243             {
 244                 push!(4, "3.1.0.1");
 245             }
 246         }
 247
 248         macro_rules! toc {
 249             ($(($level: expr, $name: expr, $(($sub: tt))* )),*) => {
 250                 Toc {
 251                     entries: vec!(
 252                         $(
 253                             TocEntry {
 254                                 level: $level,
 255                                 name: $name.to_string(),
 256                                 sec_number: $name.to_string(),
 257                                 id: "".to_string(),
 258                                 children: toc!($($sub),*)
 259                             }
 260                             ),*
 261                         )
 262                 }
 263             }
 264         }
 265         let expected = toc!(
 266             (2, "0.1", ),
 267
 268             (1, "1",
 269              ((2, "1.1", ((3, "1.1.1", )) ((3, "1.1.2", ))))
 270              ((2, "1.2", ((3, "1.2.1", )) ((3, "1.2.2", ))))
 271              ),
 272
 273             (1, "2", ),
 274
 275             (1, "3",
 276              ((4, "3.0.0.1", ((6, "3.0.0.1.0.1", ))))
 277              ((4, "3.0.0.2", ))
 278              ((2, "3.1", ((4, "3.1.0.1", ))))
 279              )
 280             );
 281         assert_eq!(expected, builder.into_toc());
 282     }
 283 }