]> git.proxmox.com Git - rustc.git/blob - src/librustdoc/html/toc.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / 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 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 = 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(&format!("{}", number + 1))
161 }
162
163 self.chain.push(TocEntry {
164 level: level,
165 name: name,
166 sec_number: sec_number,
167 id: 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 }