1 //! Table-of-contents creation. 2 3 /// A (recursive) table of contents 4 #[derive(Debug, PartialEq)] 5 crate struct Toc { 6 /// The levels are strictly decreasing, i.e. 7 /// 8 /// `entries[0].level >= entries[1].level >= ...` 9 /// 10 /// Normally they are equal, but can differ in cases like A and B, 11 /// both of which end up in the same `Toc` as they have the same 12 /// parent (Main). 13 /// 14 /// ```text 15 /// # Main 16 /// ### A 17 /// ## B 18 /// ``` 19 entries: Vec<TocEntry>, 20 } 21 22 impl Toc { count_entries_with_level(&self, level: u32) -> usize23 fn count_entries_with_level(&self, level: u32) -> usize { 24 self.entries.iter().filter(|e| e.level == level).count() 25 } 26 } 27 28 #[derive(Debug, PartialEq)] 29 crate struct TocEntry { 30 level: u32, 31 sec_number: String, 32 name: String, 33 id: String, 34 children: Toc, 35 } 36 37 /// Progressive construction of a table of contents. 38 #[derive(PartialEq)] 39 crate struct TocBuilder { 40 top_level: Toc, 41 /// The current hierarchy of parent headings, the levels are 42 /// strictly increasing (i.e., `chain[0].level < chain[1].level < 43 /// ...`) with each entry being the most recent occurrence of a 44 /// heading with that level (it doesn't include the most recent 45 /// occurrences of every level, just, if it *is* in `chain` then 46 /// it is the most recent one). 47 /// 48 /// We also have `chain[0].level <= top_level.entries[last]`. 49 chain: Vec<TocEntry>, 50 } 51 52 impl TocBuilder { new() -> TocBuilder53 crate fn new() -> TocBuilder { 54 TocBuilder { top_level: Toc { entries: Vec::new() }, chain: Vec::new() } 55 } 56 57 /// Converts into a true `Toc` struct. into_toc(mut self) -> Toc58 crate fn into_toc(mut self) -> Toc { 59 // we know all levels are >= 1. 60 self.fold_until(0); 61 self.top_level 62 } 63 64 /// Collapse the chain until the first heading more important than 65 /// `level` (i.e., lower level) 66 /// 67 /// Example: 68 /// 69 /// ```text 70 /// ## A 71 /// # B 72 /// # C 73 /// ## D 74 /// ## E 75 /// ### F 76 /// #### G 77 /// ### H 78 /// ``` 79 /// 80 /// If we are considering H (i.e., level 3), then A and B are in 81 /// self.top_level, D is in C.children, and C, E, F, G are in 82 /// self.chain. 83 /// 84 /// When we attempt to push H, we realize that first G is not the 85 /// parent (level is too high) so it is popped from chain and put 86 /// into F.children, then F isn't the parent (level is equal, aka 87 /// sibling), so it's also popped and put into E.children. 88 /// 89 /// This leaves us looking at E, which does have a smaller level, 90 /// and, by construction, it's the most recent thing with smaller 91 /// level, i.e., it's the immediate parent of H. fold_until(&mut self, level: u32)92 fn fold_until(&mut self, level: u32) { 93 let mut this = None; 94 loop { 95 match self.chain.pop() { 96 Some(mut next) => { 97 next.children.entries.extend(this); 98 if next.level < level { 99 // this is the parent we want, so return it to 100 // its rightful place. 101 self.chain.push(next); 102 return; 103 } else { 104 this = Some(next); 105 } 106 } 107 None => { 108 self.top_level.entries.extend(this); 109 return; 110 } 111 } 112 } 113 } 114 115 /// Push a level `level` heading into the appropriate place in the 116 /// hierarchy, returning a string containing the section number in 117 /// `<num>.<num>.<num>` format. push(&mut self, level: u32, name: String, id: String) -> &str118 crate fn push(&mut self, level: u32, name: String, id: String) -> &str { 119 assert!(level >= 1); 120 121 // collapse all previous sections into their parents until we 122 // get to relevant heading (i.e., the first one with a smaller 123 // level than us) 124 self.fold_until(level); 125 126 let mut sec_number; 127 { 128 let (toc_level, toc) = match self.chain.last() { 129 None => { 130 sec_number = String::new(); 131 (0, &self.top_level) 132 } 133 Some(entry) => { 134 sec_number = entry.sec_number.clone(); 135 sec_number.push('.'); 136 (entry.level, &entry.children) 137 } 138 }; 139 // fill in any missing zeros, e.g., for 140 // # Foo (1) 141 // ### Bar (1.0.1) 142 for _ in toc_level..level - 1 { 143 sec_number.push_str("0."); 144 } 145 let number = toc.count_entries_with_level(level); 146 sec_number.push_str(&(number + 1).to_string()) 147 } 148 149 self.chain.push(TocEntry { 150 level, 151 name, 152 sec_number, 153 id, 154 children: Toc { entries: Vec::new() }, 155 }); 156 157 // get the thing we just pushed, so we can borrow the string 158 // out of it with the right lifetime 159 let just_inserted = self.chain.last_mut().unwrap(); 160 &just_inserted.sec_number 161 } 162 } 163 164 impl Toc { print_inner(&self, v: &mut String)165 fn print_inner(&self, v: &mut String) { 166 v.push_str("<ul>"); 167 for entry in &self.entries { 168 // recursively format this table of contents 169 v.push_str(&format!( 170 "\n<li><a href=\"#{id}\">{num} {name}</a>", 171 id = entry.id, 172 num = entry.sec_number, 173 name = entry.name 174 )); 175 entry.children.print_inner(&mut *v); 176 v.push_str("</li>"); 177 } 178 v.push_str("</ul>"); 179 } print(&self) -> String180 crate fn print(&self) -> String { 181 let mut v = String::new(); 182 self.print_inner(&mut v); 183 v 184 } 185 } 186 187 #[cfg(test)] 188 mod tests; 189