Heading numbering and outline

4 files changed, 216 insertions, 4 deletions

diff --git a/library/src/basics/heading.rs b/library/src/basics/heading.rs
index d1ea9da6..58d0d3bf 100644
--- a/library/src/basics/heading.rs
+++ b/library/src/basics/heading.rs
@@ -1,8 +1,9 @@
 use typst::font::FontWeight;
 
+use crate::compute::NumberingPattern;
 use crate::layout::{BlockNode, VNode};
 use crate::prelude::*;
-use crate::text::{TextNode, TextSize};
+use crate::text::{SpaceNode, TextNode, TextSize};
 
 /// A section heading.
 #[derive(Debug, Hash)]
@@ -14,8 +15,15 @@ pub struct HeadingNode {
     pub body: Content,
 }
 
-#[node(Show, Finalize)]
+#[node(Prepare, Show, Finalize)]
 impl HeadingNode {
+    /// How to number the heading.
+    #[property(referenced)]
+    pub const NUMBERING: Option<NumberingPattern> = None;
+
+    /// Whether the heading should appear in the outline.
+    pub const OUTLINED: bool = true;
+
     fn construct(_: &Vm, args: &mut Args) -> SourceResult<Content> {
         Ok(Self {
             body: args.expect("body")?,
@@ -33,9 +41,42 @@ impl HeadingNode {
     }
 }
 
+impl Prepare for HeadingNode {
+    fn prepare(&self, vt: &mut Vt, mut this: Content, styles: StyleChain) -> Content {
+        let my_id = vt.identify(&this);
+
+        let mut counter = HeadingCounter::new();
+        for (node_id, node) in vt.locate(Selector::node::<HeadingNode>()) {
+            if node_id == my_id {
+                break;
+            }
+
+            if matches!(node.field("numbers"), Some(Value::Str(_))) {
+                let heading = node.to::<Self>().unwrap();
+                counter.advance(heading);
+            }
+        }
+
+        let mut numbers = Value::None;
+        if let Some(pattern) = styles.get(Self::NUMBERING) {
+            numbers = Value::Str(pattern.apply(counter.advance(self)).into());
+        }
+
+        this.push_field("outlined", Value::Bool(styles.get(Self::OUTLINED)));
+        this.push_field("numbers", numbers);
+
+        let meta = Meta::Node(my_id, this.clone());
+        this.styled(Meta::DATA, vec![meta])
+    }
+}
+
 impl Show for HeadingNode {
-    fn show(&self, _: &mut Vt, _: &Content, _: StyleChain) -> Content {
-        BlockNode(self.body.clone()).pack()
+    fn show(&self, _: &mut Vt, this: &Content, _: StyleChain) -> Content {
+        let mut realized = self.body.clone();
+        if let Some(Value::Str(numbering)) = this.field("numbers") {
+            realized = TextNode::packed(numbering) + SpaceNode.pack() + realized;
+        }
+        BlockNode(realized).pack()
     }
 }
 
@@ -60,3 +101,29 @@ impl Finalize for HeadingNode {
         realized.styled_with_map(map)
     }
 }
+
+/// Counters through headings with different levels.
+pub struct HeadingCounter(Vec<NonZeroUsize>);
+
+impl HeadingCounter {
+    /// Create a new heading counter.
+    pub fn new() -> Self {
+        Self(vec![])
+    }
+
+    /// Advance the counter and return the numbers for the given heading.
+    pub fn advance(&mut self, heading: &HeadingNode) -> &[NonZeroUsize] {
+        let level = heading.level.get();
+
+        if self.0.len() >= level {
+            self.0[level - 1] = self.0[level - 1].saturating_add(1);
+            self.0.truncate(level);
+        }
+
+        while self.0.len() < level {
+            self.0.push(NonZeroUsize::new(1).unwrap());
+        }
+
+        &self.0
+    }
+}
diff --git a/library/src/lib.rs b/library/src/lib.rs
index e1540133..3543a672 100644
--- a/library/src/lib.rs
+++ b/library/src/lib.rs
@@ -92,6 +92,7 @@ fn scope() -> Scope {
     std.def_node::<meta::DocumentNode>("document");
     std.def_node::<meta::RefNode>("ref");
     std.def_node::<meta::LinkNode>("link");
+    std.def_node::<meta::OutlineNode>("outline");
 
     // Compute.
     std.def_fn("type", compute::type_);
diff --git a/library/src/meta/mod.rs b/library/src/meta/mod.rs
index 31a69ccc..4612274c 100644
--- a/library/src/meta/mod.rs
+++ b/library/src/meta/mod.rs
@@ -3,7 +3,9 @@
 mod document;
 mod link;
 mod reference;
+mod outline;
 
 pub use self::document::*;
+pub use self::outline::*;
 pub use self::link::*;
 pub use self::reference::*;
diff --git a/library/src/meta/outline.rs b/library/src/meta/outline.rs
new file mode 100644
index 00000000..b680a1ac
--- /dev/null
+++ b/library/src/meta/outline.rs
@@ -0,0 +1,142 @@
+use crate::basics::HeadingNode;
+use crate::layout::{BlockNode, HNode, HideNode, RepeatNode, Spacing};
+use crate::prelude::*;
+use crate::text::{LinebreakNode, SpaceNode, TextNode};
+
+/// A section outline (table of contents).
+#[derive(Debug, Hash)]
+pub struct OutlineNode;
+
+#[node(Prepare, Show)]
+impl OutlineNode {
+    /// The title of the outline.
+    #[property(referenced)]
+    pub const TITLE: Option<Smart<Content>> = Some(Smart::Auto);
+
+    /// The maximum depth up to which headings are included in the outline.
+    pub const DEPTH: Option<NonZeroUsize> = None;
+
+    /// Whether to indent the subheadings to match their parents.
+    pub const INDENT: bool = false;
+
+    /// The fill symbol.
+    #[property(referenced)]
+    pub const FILL: Option<EcoString> = Some('.'.into());
+
+    fn construct(_: &Vm, _: &mut Args) -> SourceResult<Content> {
+        Ok(Self.pack())
+    }
+}
+
+impl Prepare for OutlineNode {
+    fn prepare(&self, vt: &mut Vt, mut this: Content, _: StyleChain) -> Content {
+        let headings = vt
+            .locate(Selector::node::<HeadingNode>())
+            .into_iter()
+            .map(|(_, node)| node)
+            .filter(|node| node.field("outlined").unwrap() == Value::Bool(true))
+            .map(|node| Value::Content(node.clone()))
+            .collect();
+
+        this.push_field("headings", Value::Array(Array::from_vec(headings)));
+        this
+    }
+}
+
+impl Show for OutlineNode {
+    fn show(&self, vt: &mut Vt, _: &Content, styles: StyleChain) -> Content {
+        let mut seq = vec![];
+        if let Some(title) = styles.get(Self::TITLE) {
+            let body = title.clone().unwrap_or_else(|| {
+                TextNode::packed(match styles.get(TextNode::LANG) {
+                    Lang::GERMAN => "Inhaltsverzeichnis",
+                    Lang::ENGLISH | _ => "Contents",
+                })
+            });
+
+            seq.push(
+                HeadingNode { body, level: NonZeroUsize::new(1).unwrap() }
+                    .pack()
+                    .styled(HeadingNode::NUMBERING, None)
+                    .styled(HeadingNode::OUTLINED, false),
+            );
+        }
+
+        let indent = styles.get(Self::INDENT);
+        let depth = styles.get(Self::DEPTH);
+
+        let mut ancestors: Vec<&Content> = vec![];
+        for (_, node) in vt.locate(Selector::node::<HeadingNode>()) {
+            if node.field("outlined").unwrap() != Value::Bool(true) {
+                continue;
+            }
+
+            let heading = node.to::<HeadingNode>().unwrap();
+            if let Some(depth) = depth {
+                if depth < heading.level {
+                    continue;
+                }
+            }
+
+            while ancestors.last().map_or(false, |last| {
+                last.to::<HeadingNode>().unwrap().level >= heading.level
+            }) {
+                ancestors.pop();
+            }
+
+            // Adjust the link destination a bit to the topleft so that the
+            // heading is fully visible.
+            let mut loc = node.field("loc").unwrap().cast::<Location>().unwrap();
+            loc.pos -= Point::splat(Abs::pt(10.0));
+
+            // Add hidden ancestors numberings to realize the indent.
+            if indent {
+                let text = ancestors
+                    .iter()
+                    .filter_map(|node| match node.field("numbers").unwrap() {
+                        Value::Str(numbering) => {
+                            Some(EcoString::from(numbering) + ' '.into())
+                        }
+                        _ => None,
+                    })
+                    .collect::<EcoString>();
+
+                if !text.is_empty() {
+                    seq.push(HideNode(TextNode::packed(text)).pack());
+                    seq.push(SpaceNode.pack());
+                }
+            }
+
+            // Format the numbering.
+            let numbering = match node.field("numbers").unwrap() {
+                Value::Str(numbering) => {
+                    TextNode::packed(EcoString::from(numbering) + ' '.into())
+                }
+                _ => Content::empty(),
+            };
+
+            // Add the numbering and section name.
+            let start = numbering + heading.body.clone();
+            seq.push(start.linked(Destination::Internal(loc)));
+
+            // Add filler symbols between the section name and page number.
+            if let Some(filler) = styles.get(Self::FILL) {
+                seq.push(SpaceNode.pack());
+                seq.push(RepeatNode(TextNode::packed(filler.clone())).pack());
+                seq.push(SpaceNode.pack());
+            } else {
+                let amount = Spacing::Fractional(Fr::one());
+                seq.push(HNode { amount, weak: false }.pack());
+            }
+
+            // Add the page number and linebreak.
+            let end = TextNode::packed(format_eco!("{}", loc.page));
+            seq.push(end.linked(Destination::Internal(loc)));
+            seq.push(LinebreakNode { justify: false }.pack());
+
+            ancestors.push(node);
+        }
+
+        BlockNode(Content::sequence(seq)).pack()
+    }
+}