feat: insert a Table of Contents into generated HTML

Signed-off-by: Lars Wirzenius <liw@liw.fi>
Sponsored-by: author

3 files changed, 257 insertions, 6 deletions

diff --git a/src/doc.rs b/src/doc.rs
index e448051..f3f9641 100644
--- a/src/doc.rs
+++ b/src/doc.rs
@@ -1,6 +1,7 @@
 use crate::bindings::CaptureType;
 use crate::generate_test_program;
 use crate::get_basedir_from;
+use crate::html::Attribute;
 use crate::html::HtmlPage;
 use crate::html::{Content, Element, ElementTag};
 use crate::md::Markdown;
@@ -14,6 +15,7 @@ use crate::SubplotError;
 use crate::{Metadata, YamlMetadata};
 use crate::{Warning, Warnings};
 
+use std::cmp::Ordering;
 use std::collections::HashSet;
 use std::default::Default;
 use std::fmt::Debug;
@@ -138,30 +140,153 @@ impl Document {
 
     /// Return Document as an HTML page serialized into HTML text
     pub fn to_html(&mut self, date: &str) -> Result<String, SubplotError> {
+        const CSS: &str = r#"
+            div.toc ol {
+                list-style-type: none;
+                padding: 0;
+                padding-inline-start: 2ch;
+            }
+        "#;
+
         let mut head = Element::new(crate::html::ElementTag::Head);
         let mut title = Element::new(crate::html::ElementTag::Title);
         title.push_child(crate::html::Content::Text(self.meta().title().into()));
         head.push_child(crate::html::Content::Elt(title));
 
+        let mut css = Element::new(ElementTag::Style);
+        css.push_child(Content::Text(CSS.into()));
+        head.push_child(Content::Elt(css));
+
         self.meta.set_date(date.into());
 
-        let mut body = self.typeset_meta();
+        let mut body_content = Element::new(crate::html::ElementTag::Div);
         for md in self.markdowns.iter() {
-            body.push_child(Content::Elt(md.root_element().clone()));
+            body_content.push_child(Content::Elt(md.root_element().clone()));
         }
+
+        let mut body = Element::new(crate::html::ElementTag::Div);
+        body.push_child(Content::Elt(self.typeset_meta()));
+        body.push_child(Content::Elt(self.typeset_toc(&body_content)));
+        body.push_child(Content::Elt(body_content));
+
         let page = HtmlPage::new(head, body);
         page.serialize().map_err(SubplotError::ParseMarkdown)
     }
 
+    fn typeset_toc(&self, body: &Element) -> Element {
+        let mut toc = Element::new(ElementTag::Div);
+        toc.push_attribute(Attribute::new("class", "toc"));
+
+        let mut heading = Element::new(ElementTag::H1);
+        heading.push_child(Content::Text("Table of Contents".into()));
+        toc.push_child(Content::Elt(heading));
+
+        let heading_elements: Vec<&Element> = crate::md::Markdown::visit(body)
+            .iter()
+            .filter(|e| {
+                matches!(
+                    e.tag(),
+                    ElementTag::H1
+                        | ElementTag::H2
+                        | ElementTag::H3
+                        | ElementTag::H4
+                        | ElementTag::H5
+                        | ElementTag::H6
+                )
+            })
+            .cloned()
+            .collect();
+
+        let mut headings = vec![];
+        for e in heading_elements {
+            let id = e
+                .attr("id")
+                .expect("heading has id")
+                .value()
+                .expect("id attribute has value");
+            match e.tag() {
+                ElementTag::H1 => headings.push((1, e.content(), id)),
+                ElementTag::H2 => headings.push((2, e.content(), id)),
+                ElementTag::H3 => headings.push((3, e.content(), id)),
+                ElementTag::H4 => headings.push((4, e.content(), id)),
+                ElementTag::H5 => headings.push((5, e.content(), id)),
+                ElementTag::H6 => headings.push((6, e.content(), id)),
+                _ => (),
+            }
+        }
+
+        let mut stack = vec![];
+        let mut numberer = HeadingNumberer::default();
+        for (level, text, id) in headings {
+            assert!(level >= 1);
+            assert!(level <= 6);
+
+            let mut number = Element::new(ElementTag::Span);
+            number.push_child(Content::Text(numberer.number(level)));
+
+            let mut a = Element::new(ElementTag::A);
+            a.push_attribute(crate::html::Attribute::new("href", &format!("#{}", id)));
+            a.push_child(Content::Elt(number));
+            a.push_child(Content::Text(" ".into()));
+            a.push_child(Content::Text(text));
+
+            let mut li = Element::new(ElementTag::Li);
+            li.push_child(Content::Elt(a));
+
+            match level.cmp(&stack.len()) {
+                Ordering::Equal => (),
+                Ordering::Greater => stack.push(Element::new(ElementTag::Ol)),
+                Ordering::Less => {
+                    assert!(!stack.is_empty());
+                    let child = stack.pop().unwrap();
+                    assert!(child.tag() == ElementTag::Ol);
+                    let mut li = Element::new(ElementTag::Li);
+                    li.push_child(Content::Elt(child));
+                    assert!(!stack.is_empty());
+                    let mut parent = stack.pop().unwrap();
+                    parent.push_child(Content::Elt(li));
+                    stack.push(parent);
+                }
+            }
+
+            assert!(!stack.is_empty());
+            let mut ol = stack.pop().unwrap();
+            ol.push_child(Content::Elt(li));
+            stack.push(ol);
+        }
+
+        while stack.len() > 1 {
+            let child = stack.pop().unwrap();
+            assert!(child.tag() == ElementTag::Ol);
+            let mut li = Element::new(ElementTag::Li);
+            li.push_child(Content::Elt(child));
+
+            let mut parent = stack.pop().unwrap();
+            parent.push_child(Content::Elt(li));
+            stack.push(parent);
+        }
+
+        assert!(stack.len() <= 1);
+        if let Some(ol) = stack.pop() {
+            toc.push_child(Content::Elt(ol));
+        }
+
+        toc
+    }
+
     fn typeset_meta(&self) -> Element {
         let mut div = Element::new(ElementTag::Div);
+
         div.push_child(Content::Elt(Self::title(self.meta.title())));
+
         if let Some(authors) = self.meta.authors() {
             div.push_child(Content::Elt(Self::authors(authors)));
         }
+
         if let Some(date) = self.meta.date() {
             div.push_child(Content::Elt(Self::date(date)));
         }
+
         div
     }
 
@@ -609,3 +734,57 @@ impl CodegenOutput {
         Self { template, doc }
     }
 }
+
+#[derive(Debug, Default)]
+struct HeadingNumberer {
+    prev: Vec<usize>,
+}
+
+impl HeadingNumberer {
+    fn number(&mut self, level: usize) -> String {
+        match level.cmp(&self.prev.len()) {
+            Ordering::Equal => {
+                if let Some(n) = self.prev.pop() {
+                    self.prev.push(n + 1);
+                } else {
+                    self.prev.push(1);
+                }
+            }
+            Ordering::Greater => {
+                self.prev.push(1);
+            }
+            Ordering::Less => {
+                assert!(!self.prev.is_empty());
+                self.prev.pop();
+                if let Some(n) = self.prev.pop() {
+                    self.prev.push(n + 1);
+                } else {
+                    self.prev.push(1);
+                }
+            }
+        }
+
+        let mut s = String::new();
+        for i in self.prev.iter() {
+            if !s.is_empty() {
+                s.push('.');
+            }
+            s.push_str(&i.to_string());
+        }
+        s
+    }
+}
+
+#[cfg(test)]
+mod test_numberer {
+    use super::HeadingNumberer;
+
+    #[test]
+    fn numbering() {
+        let mut n = HeadingNumberer::default();
+        assert_eq!(n.number(1), "1");
+        assert_eq!(n.number(2), "1.1");
+        assert_eq!(n.number(1), "2");
+        assert_eq!(n.number(2), "2.1");
+    }
+}
diff --git a/src/html.rs b/src/html.rs
index 1e0dafa..2cb8f3c 100644
--- a/src/html.rs
+++ b/src/html.rs
@@ -7,7 +7,7 @@ use line_col::LineColLookup;
 use log::{debug, trace};
 use pulldown_cmark::{CodeBlockKind, Event, HeadingLevel, Options, Parser, Tag};
 use serde::{Deserialize, Serialize};
-use std::collections::HashMap;
+use std::collections::{HashMap, HashSet};
 use std::fmt::Write as _;
 use std::io::Write;
 use std::path::{Path, PathBuf};
@@ -89,6 +89,7 @@ pub fn parse(filename: &Path, markdown: &str) -> Result<Element, HtmlError> {
     let linecol = LineColLookup::new(markdown);
     let mut stack = Stack::new();
     stack.push(Element::new(ElementTag::Div));
+    let mut slugs = Slugs::default();
     for (event, loc) in p {
         trace!("event {:?}", event);
         let (line, col) = linecol.get(loc.start);
@@ -108,6 +109,7 @@ pub fn parse(filename: &Path, markdown: &str) -> Result<Element, HtmlError> {
                     let mut h = Element::new(tag).with_location(loc);
                     if let Some(id) = id {
                         h.push_attribute(Attribute::new("id", id));
+                        slugs.remember(id);
                     }
                     if !classes.is_empty() {
                         let mut names = String::new();
@@ -174,8 +176,16 @@ pub fn parse(filename: &Path, markdown: &str) -> Result<Element, HtmlError> {
                     }
                     stack.append_child(Content::Elt(e));
                 }
-                Tag::Heading(_, _, _)
-                | Tag::List(_)
+                Tag::Heading(_, _, _) => {
+                    let mut e = stack.pop();
+                    if e.attr("id").is_none() {
+                        let slug = slugs.unique(&e.heading_slug());
+                        let id = Attribute::new("id", &slug);
+                        e.push_attribute(id);
+                    }
+                    stack.append_child(Content::Elt(e));
+                }
+                Tag::List(_)
                 | Tag::Item
                 | Tag::Link(_, _, _)
                 | Tag::Image(_, _, _)
@@ -318,6 +328,19 @@ impl Element {
             > 0
     }
 
+    fn heading_slug(&self) -> String {
+        const SAFE: &str = "abcdefghijklmnopqrstuvwxyz";
+        let mut slug = String::new();
+        for s in self.content().to_lowercase().split_whitespace() {
+            for c in s.chars() {
+                if SAFE.contains(c) {
+                    slug.push(c);
+                }
+            }
+        }
+        slug
+    }
+
     /// Return the concatenated text content of direct children,
     /// ignoring any elements.
     pub fn content(&self) -> String {
@@ -426,6 +449,7 @@ pub enum ElementTag {
     Ol,
     Ul,
     Li,
+    Link,
     Blockquote,
     Pre,
     Em,
@@ -441,6 +465,8 @@ pub enum ElementTag {
     Br,
     Hr,
     Code,
+    Span,
+    Style,
 }
 
 impl ElementTag {
@@ -462,6 +488,7 @@ impl ElementTag {
             Self::Ol => "ol",
             Self::Ul => "ul",
             Self::Li => "li",
+            Self::Link => "link",
             Self::Blockquote => "blockquote",
             Self::Pre => "pre",
             Self::Em => "em",
@@ -477,6 +504,8 @@ impl ElementTag {
             Self::Br => "br",
             Self::Hr => "hr",
             Self::Code => "code",
+            Self::Span => "span",
+            Self::Style => "style",
         }
     }
 
@@ -844,3 +873,45 @@ mod test_block_attr {
         );
     }
 }
+
+#[derive(Debug, Default)]
+struct Slugs {
+    slugs: HashSet<String>,
+}
+
+impl Slugs {
+    const MAX: usize = 8;
+
+    fn remember(&mut self, slug: &str) {
+        self.slugs.insert(slug.into());
+    }
+
+    fn unique(&mut self, candidate: &str) -> String {
+        let slug = self.helper(candidate);
+        self.remember(&slug);
+        slug
+    }
+
+    fn helper(&mut self, candidate: &str) -> String {
+        let mut slug0 = String::new();
+        for c in candidate.chars() {
+            if slug0.len() >= Self::MAX {
+                break;
+            }
+            slug0.push(c);
+        }
+
+        if !self.slugs.contains(&slug0) {
+            return slug0.to_string();
+        }
+
+        let mut i = 0;
+        loop {
+            i += 1;
+            let slug = format!("{}{}", slug0, i);
+            if !self.slugs.contains(&slug) {
+                return slug;
+            }
+        }
+    }
+}
diff --git a/src/md.rs b/src/md.rs
index 8573167..64cfc44 100644
--- a/src/md.rs
+++ b/src/md.rs
@@ -54,7 +54,8 @@ impl Markdown {
         names
     }
 
-    fn visit(e: &Element) -> Vec<&Element> {
+    /// Turn an element tree into a flat vector.
+    pub fn visit(e: &Element) -> Vec<&Element> {
         let mut elements = vec![];
         Self::visit_helper(e, &mut elements);
         elements