Introspection

10 files changed, 299 insertions, 65 deletions

diff --git a/src/doc.rs b/src/doc.rs
index 93cae90f..2605bfc1 100644
--- a/src/doc.rs
+++ b/src/doc.rs
@@ -10,21 +10,14 @@ use crate::geom::{
     Abs, Align, Axes, Dir, Em, Numeric, Paint, Point, Shape, Size, Transform,
 };
 use crate::image::Image;
-use crate::model::{dict, Dict, Value};
+use crate::model::{dict, node, Content, Dict, Fold, StableId, StyleChain, Value};
 use crate::util::EcoString;
 
 /// A finished document with metadata and page frames.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Default, Clone)]
 pub struct Document {
-    /// The document's metadata.
-    pub metadata: Metadata,
     /// The page frames.
     pub pages: Vec<Frame>,
-}
-
-/// Document metadata.
-#[derive(Debug, Default, Clone, Eq, PartialEq)]
-pub struct Metadata {
     /// The document's title.
     pub title: Option<EcoString>,
     /// The document's author.
@@ -32,7 +25,7 @@ pub struct Metadata {
 }
 
 /// A partial layout result.
-#[derive(Clone, Eq, PartialEq)]
+#[derive(Clone)]
 pub struct Fragment(Vec<Frame>);
 
 impl Fragment {
@@ -113,7 +106,7 @@ impl<'a> IntoIterator for &'a mut Fragment {
 }
 
 /// A finished layout with elements at fixed positions.
-#[derive(Default, Clone, Eq, PartialEq)]
+#[derive(Default, Clone)]
 pub struct Frame {
     /// The size of the frame.
     size: Size,
@@ -336,9 +329,11 @@ impl Frame {
         }
     }
 
-    /// Link the whole frame to a resource.
-    pub fn link(&mut self, dest: Destination) {
-        self.push(Point::zero(), Element::Link(dest, self.size));
+    /// Attach the metadata from this style chain to the frame.
+    pub fn meta(&mut self, styles: StyleChain) {
+        for meta in styles.get(Meta::DATA) {
+            self.push(Point::zero(), Element::Meta(meta, self.size));
+        }
     }
 
     /// Arbitrarily transform the contents of the frame.
@@ -374,7 +369,7 @@ impl Debug for Frame {
 }
 
 /// The building block frames are composed of.
-#[derive(Clone, Eq, PartialEq)]
+#[derive(Clone)]
 pub enum Element {
     /// A group of elements.
     Group(Group),
@@ -384,8 +379,8 @@ pub enum Element {
     Shape(Shape),
     /// An image and its size.
     Image(Image, Size),
-    /// A link to an external resource and its trigger region.
-    Link(Destination, Size),
+    /// Meta information and the region it applies to.
+    Meta(Meta, Size),
 }
 
 impl Debug for Element {
@@ -395,13 +390,13 @@ impl Debug for Element {
             Self::Text(text) => write!(f, "{text:?}"),
             Self::Shape(shape) => write!(f, "{shape:?}"),
             Self::Image(image, _) => write!(f, "{image:?}"),
-            Self::Link(dest, _) => write!(f, "Link({dest:?})"),
+            Self::Meta(meta, _) => write!(f, "{meta:?}"),
         }
     }
 }
 
 /// A group of elements with optional clipping.
-#[derive(Clone, Eq, PartialEq)]
+#[derive(Clone)]
 pub struct Group {
     /// The group's frame.
     pub frame: Frame,
@@ -543,6 +538,33 @@ impl FromStr for Region {
     }
 }
 
+/// Meta information that isn't visible or renderable.
+#[derive(Debug, Clone, Hash)]
+pub enum Meta {
+    /// An internal or external link.
+    Link(Destination),
+    /// An identifiable piece of content that produces something within the
+    /// area this metadata is attached to.
+    Node(StableId, Content),
+}
+
+#[node]
+impl Meta {
+    /// Metadata that should be attached to all elements affected by this style
+    /// property.
+    #[property(fold, skip)]
+    pub const DATA: Vec<Meta> = vec![];
+}
+
+impl Fold for Vec<Meta> {
+    type Output = Self;
+
+    fn fold(mut self, outer: Self::Output) -> Self::Output {
+        self.extend(outer);
+        self
+    }
+}
+
 /// A link destination.
 #[derive(Debug, Clone, Eq, PartialEq, Hash)]
 pub enum Destination {
diff --git a/src/export/pdf/mod.rs b/src/export/pdf/mod.rs
index 8f9d9637..60cd4ea2 100644
--- a/src/export/pdf/mod.rs
+++ b/src/export/pdf/mod.rs
@@ -14,7 +14,7 @@ use pdf_writer::{Finish, Name, PdfWriter, Ref, TextStr};
 
 use self::outline::HeadingNode;
 use self::page::Page;
-use crate::doc::{Document, Lang, Metadata};
+use crate::doc::{Document, Lang};
 use crate::font::Font;
 use crate::geom::{Abs, Dir, Em};
 use crate::image::Image;
@@ -23,7 +23,7 @@ use crate::image::Image;
 ///
 /// Returns the raw bytes making up the PDF file.
 pub fn pdf(document: &Document) -> Vec<u8> {
-    let mut ctx = PdfContext::new(&document.metadata);
+    let mut ctx = PdfContext::new(document);
     page::construct_pages(&mut ctx, &document.pages);
     font::write_fonts(&mut ctx);
     image::write_images(&mut ctx);
@@ -38,7 +38,7 @@ const D65_GRAY: Name<'static> = Name(b"d65gray");
 
 /// Context for exporting a whole PDF document.
 pub struct PdfContext<'a> {
-    metadata: &'a Metadata,
+    document: &'a Document,
     writer: PdfWriter,
     pages: Vec<Page>,
     page_heights: Vec<f32>,
@@ -55,11 +55,11 @@ pub struct PdfContext<'a> {
 }
 
 impl<'a> PdfContext<'a> {
-    fn new(metadata: &'a Metadata) -> Self {
+    fn new(document: &'a Document) -> Self {
         let mut alloc = Ref::new(1);
         let page_tree_ref = alloc.bump();
         Self {
-            metadata,
+            document,
             writer: PdfWriter::new(),
             pages: vec![],
             page_heights: vec![],
@@ -116,10 +116,10 @@ fn write_catalog(ctx: &mut PdfContext) {
 
     // Write the document information.
     let mut info = ctx.writer.document_info(ctx.alloc.bump());
-    if let Some(title) = &ctx.metadata.title {
+    if let Some(title) = &ctx.document.title {
         info.title(TextStr(title));
     }
-    if let Some(author) = &ctx.metadata.author {
+    if let Some(author) = &ctx.document.author {
         info.author(TextStr(author));
     }
     info.creator(TextStr("Typst"));
diff --git a/src/export/pdf/page.rs b/src/export/pdf/page.rs
index fc714e7a..f2ab78e3 100644
--- a/src/export/pdf/page.rs
+++ b/src/export/pdf/page.rs
@@ -3,7 +3,7 @@ use pdf_writer::writers::ColorSpace;
 use pdf_writer::{Content, Filter, Finish, Name, Rect, Ref, Str};
 
 use super::{deflate, AbsExt, EmExt, PdfContext, RefExt, D65_GRAY, SRGB};
-use crate::doc::{Destination, Element, Frame, Group, Text};
+use crate::doc::{Destination, Element, Frame, Group, Meta, Text};
 use crate::font::Font;
 use crate::geom::{
     self, Abs, Color, Em, Geometry, Numeric, Paint, Point, Ratio, Shape, Size, Stroke,
@@ -287,7 +287,10 @@ fn write_frame(ctx: &mut PageContext, frame: &Frame) {
             Element::Text(text) => write_text(ctx, x, y, text),
             Element::Shape(shape) => write_shape(ctx, x, y, shape),
             Element::Image(image, size) => write_image(ctx, x, y, image, *size),
-            Element::Link(dest, size) => write_link(ctx, pos, dest, *size),
+            Element::Meta(meta, size) => match meta {
+                Meta::Link(dest) => write_link(ctx, pos, dest, *size),
+                _ => {}
+            },
         }
     }
 }
diff --git a/src/export/render.rs b/src/export/render.rs
index a61ff1be..68625e23 100644
--- a/src/export/render.rs
+++ b/src/export/render.rs
@@ -57,7 +57,7 @@ fn render_frame(
             Element::Image(image, size) => {
                 render_image(canvas, ts, mask, image, *size);
             }
-            Element::Link(_, _) => {}
+            Element::Meta(_, _) => {}
         }
     }
 }
diff --git a/src/model/cast.rs b/src/model/cast.rs
index 6a78eebd..bfde1bdd 100644
--- a/src/model/cast.rs
+++ b/src/model/cast.rs
@@ -255,18 +255,24 @@ castable! {
 }
 
 castable! {
-    Destination,
-    Expected: "string or dictionary with `page`, `x`, and `y` keys",
-    Value::Str(string) => Self::Url(string.into()),
+    Location,
+    Expected: "dictionary with `page`, `x`, and `y` keys",
     Value::Dict(dict) => {
         let page = dict.get("page")?.clone().cast()?;
         let x: Length = dict.get("x")?.clone().cast()?;
         let y: Length = dict.get("y")?.clone().cast()?;
-        Self::Internal(Location { page, pos: Point::new(x.abs, y.abs) })
+        Self { page, pos: Point::new(x.abs, y.abs) }
     },
 }
 
 castable! {
+    Destination,
+    Expected: "string or dictionary with `page`, `x`, and `y` keys",
+    Value::Str(string) => Self::Url(string.into()),
+    v @ Value::Dict(_) => Self::Internal(v.cast()?),
+}
+
+castable! {
     FontStyle,
     Expected: "string",
     Value::Str(string) => match string.as_str() {
diff --git a/src/model/content.rs b/src/model/content.rs
index 2f7e7671..f261f9b1 100644
--- a/src/model/content.rs
+++ b/src/model/content.rs
@@ -21,14 +21,16 @@ use crate::World;
 pub struct Content {
     obj: Arc<dyn Bounds>,
     span: Option<Span>,
-    meta: ThinVec<Meta>,
+    modifiers: ThinVec<Modifier>,
 }
 
-/// Metadata that can be attached to content.
+/// Modifiers that can be attached to content.
 #[derive(Debug, Clone, PartialEq, Hash)]
-enum Meta {
+enum Modifier {
+    Prepared,
     Guard(Guard),
     Label(Label),
+    Field(EcoString, Value),
 }
 
 impl Content {
@@ -62,17 +64,22 @@ impl Content {
 
     /// Attach a label to the content.
     pub fn labelled(mut self, label: Label) -> Self {
-        for meta in &mut self.meta {
-            if let Meta::Label(prev) = meta {
+        for modifier in &mut self.modifiers {
+            if let Modifier::Label(prev) = modifier {
                 *prev = label;
                 return self;
             }
         }
 
-        self.meta.push(Meta::Label(label));
+        self.modifiers.push(Modifier::Label(label));
         self
     }
 
+    /// Attach a field to the content.
+    pub fn push_field(&mut self, name: impl Into<EcoString>, value: Value) {
+        self.modifiers.push(Modifier::Field(name.into(), value));
+    }
+
     /// Style this content with a single style property.
     pub fn styled<K: Key>(self, key: K, value: K::Value) -> Self {
         self.styled_with_entry(Style::Property(Property::new(key, value)))
@@ -146,8 +153,8 @@ impl Content {
 
     /// The content's label.
     pub fn label(&self) -> Option<&Label> {
-        self.meta.iter().find_map(|meta| match meta {
-            Meta::Label(label) => Some(label),
+        self.modifiers.iter().find_map(|modifier| match modifier {
+            Modifier::Label(label) => Some(label),
             _ => None,
         })
     }
@@ -161,6 +168,14 @@ impl Content {
             });
         }
 
+        for modifier in &self.modifiers {
+            if let Modifier::Field(other, value) = modifier {
+                if name == other.as_str() {
+                    return Some(value.clone());
+                }
+            }
+        }
+
         self.obj.field(name)
     }
 
@@ -201,10 +216,23 @@ impl Content {
     /// Disable a show rule recipe.
     #[doc(hidden)]
     pub fn guarded(mut self, id: Guard) -> Self {
-        self.meta.push(Meta::Guard(id));
+        self.modifiers.push(Modifier::Guard(id));
         self
     }
 
+    /// Mark this content as prepared.
+    #[doc(hidden)]
+    pub fn prepared(mut self) -> Self {
+        self.modifiers.push(Modifier::Prepared);
+        self
+    }
+
+    /// Whether this node was prepared.
+    #[doc(hidden)]
+    pub fn is_prepared(&self) -> bool {
+        self.modifiers.contains(&Modifier::Prepared)
+    }
+
     /// Whether a label can be attached to the content.
     pub(super) fn labellable(&self) -> bool {
         !self.has::<dyn Unlabellable>()
@@ -212,18 +240,21 @@ impl Content {
 
     /// Whether no show rule was executed for this node so far.
     pub(super) fn is_pristine(&self) -> bool {
-        !self.meta.iter().any(|meta| matches!(meta, Meta::Guard(_)))
+        !self
+            .modifiers
+            .iter()
+            .any(|modifier| matches!(modifier, Modifier::Guard(_)))
     }
 
     /// Check whether a show rule recipe is disabled.
     pub(super) fn is_guarded(&self, id: Guard) -> bool {
-        self.meta.contains(&Meta::Guard(id))
+        self.modifiers.contains(&Modifier::Guard(id))
     }
 
-    /// Copy the metadata from other content.
-    pub(super) fn copy_meta(&mut self, from: &Content) {
+    /// Copy the modifiers from another piece of content.
+    pub(super) fn copy_modifiers(&mut self, from: &Content) {
         self.span = from.span;
-        self.meta = from.meta.clone();
+        self.modifiers = from.modifiers.clone();
     }
 }
 
@@ -239,12 +270,6 @@ impl Default for Content {
     }
 }
 
-impl PartialEq for Content {
-    fn eq(&self, other: &Self) -> bool {
-        (*self.obj).hash128() == (*other.obj).hash128()
-    }
-}
-
 impl Add for Content {
     type Output = Self;
 
@@ -371,7 +396,7 @@ pub trait Node: 'static + Capable {
         Content {
             obj: Arc::new(self),
             span: None,
-            meta: ThinVec::new(),
+            modifiers: ThinVec::new(),
         }
     }
 
diff --git a/src/model/ops.rs b/src/model/ops.rs
index 60b1c449..1a8dcb6b 100644
--- a/src/model/ops.rs
+++ b/src/model/ops.rs
@@ -309,7 +309,6 @@ pub fn equal(lhs: &Value, rhs: &Value) -> bool {
         (Color(a), Color(b)) => a == b,
         (Str(a), Str(b)) => a == b,
         (Label(a), Label(b)) => a == b,
-        (Content(a), Content(b)) => a == b,
         (Array(a), Array(b)) => a == b,
         (Dict(a), Dict(b)) => a == b,
         (Func(a), Func(b)) => a == b,
diff --git a/src/model/realize.rs b/src/model/realize.rs
index 46e0d678..abe20901 100644
--- a/src/model/realize.rs
+++ b/src/model/realize.rs
@@ -3,6 +3,10 @@ use crate::diag::SourceResult;
 
 /// Whether the target is affected by show rules in the given style chain.
 pub fn applicable(target: &Content, styles: StyleChain) -> bool {
+    if target.has::<dyn Prepare>() && !target.is_prepared() {
+        return true;
+    }
+
     // Find out how many recipes there are.
     let mut n = styles.recipes().count();
 
@@ -90,7 +94,7 @@ fn try_apply(
 
             let make = |s| {
                 let mut content = item!(text)(s);
-                content.copy_meta(&target);
+                content.copy_modifiers(&target);
                 content
             };
 
@@ -124,6 +128,13 @@ fn try_apply(
     }
 }
 
+/// Preparations before execution of any show rule.
+#[capability]
+pub trait Prepare {
+    /// Prepare the node for show rule application.
+    fn prepare(&self, vt: &mut Vt, this: Content, styles: StyleChain) -> Content;
+}
+
 /// The base recipe for a node.
 #[capability]
 pub trait Show {
diff --git a/src/model/styles.rs b/src/model/styles.rs
index 80ec0d1e..37596b8d 100644
--- a/src/model/styles.rs
+++ b/src/model/styles.rs
@@ -17,7 +17,7 @@ use crate::util::ReadableTypeId;
 use crate::World;
 
 /// A map of style properties.
-#[derive(Default, Clone, PartialEq, Hash)]
+#[derive(Default, Clone, Hash)]
 pub struct StyleMap(Vec<Style>);
 
 impl StyleMap {
@@ -117,7 +117,7 @@ impl Debug for StyleMap {
 }
 
 /// A single style property, recipe or barrier.
-#[derive(Clone, PartialEq, Hash)]
+#[derive(Clone, Hash)]
 pub enum Style {
     /// A style property originating from a set rule or constructor.
     Property(Property),
@@ -302,7 +302,7 @@ impl Debug for KeyId {
 }
 
 /// A show rule recipe.
-#[derive(Clone, PartialEq, Hash)]
+#[derive(Clone, Hash)]
 pub struct Recipe {
     /// The span errors are reported with.
     pub span: Span,
@@ -374,6 +374,11 @@ pub enum Selector {
 }
 
 impl Selector {
+    /// Define a simple node selector.
+    pub fn node<T: 'static>() -> Self {
+        Self::Node(NodeId::of::<T>(), None)
+    }
+
     /// Define a simple text selector.
     pub fn text(text: &str) -> Self {
         Self::Regex(Regex::new(&regex::escape(text)).unwrap())
@@ -399,7 +404,7 @@ impl Selector {
 }
 
 /// A show rule transformation that can be applied to a match.
-#[derive(Debug, Clone, PartialEq, Hash)]
+#[derive(Debug, Clone, Hash)]
 pub enum Transform {
     /// Replacement content.
     Content(Content),
diff --git a/src/model/typeset.rs b/src/model/typeset.rs
index b422e4b6..7af8094c 100644
--- a/src/model/typeset.rs
+++ b/src/model/typeset.rs
@@ -1,8 +1,15 @@
-use comemo::Tracked;
+use std::cell::RefCell;
+use std::collections::HashMap;
+use std::hash::Hash;
+use std::num::NonZeroUsize;
 
-use super::{Content, StyleChain};
+use comemo::{Track, Tracked, TrackedMut};
+
+use super::{Content, Selector, StyleChain, Value};
 use crate::diag::SourceResult;
-use crate::doc::Document;
+use crate::doc::{Document, Element, Frame, Location, Meta};
+use crate::geom::Transform;
+use crate::util::hash128;
 use crate::World;
 
 /// Typeset content into a fully layouted document.
@@ -10,8 +17,30 @@ use crate::World;
 pub fn typeset(world: Tracked<dyn World>, content: &Content) -> SourceResult<Document> {
     let library = world.library();
     let styles = StyleChain::new(&library.styles);
-    let mut vt = Vt { world };
-    (library.items.layout)(&mut vt, content, styles)
+
+    let mut document;
+    let mut iter = 0;
+    let mut introspector = Introspector::new();
+
+    // Relayout until all introspections stabilize.
+    // If that doesn't happen within five attempts, we give up.
+    loop {
+        let mut provider = StabilityProvider::new();
+        let mut vt = Vt {
+            world,
+            provider: provider.track_mut(),
+            introspector: introspector.track(),
+        };
+
+        document = (library.items.layout)(&mut vt, content, styles)?;
+        iter += 1;
+
+        if iter >= 5 || introspector.update(&document) {
+            break;
+        }
+    }
+
+    Ok(document)
 }
 
 /// A virtual typesetter.
@@ -22,6 +51,12 @@ pub struct Vt<'a> {
     /// The compilation environment.
     #[doc(hidden)]
     pub world: Tracked<'a, dyn World>,
+    /// Provides stable identities to nodes.
+    #[doc(hidden)]
+    pub provider: TrackedMut<'a, StabilityProvider>,
+    /// Provides access to information about the document.
+    #[doc(hidden)]
+    pub introspector: Tracked<'a, Introspector>,
 }
 
 impl<'a> Vt<'a> {
@@ -29,4 +64,132 @@ impl<'a> Vt<'a> {
     pub fn world(&self) -> Tracked<'a, dyn World> {
         self.world
     }
+
+    /// Produce a stable identifier for this call site.
+    ///
+    /// The key should be something that identifies the call site, but is not
+    /// necessarily unique. The stable marker incorporates the key's hash plus
+    /// additional disambiguation from other call sites with the same key.
+    ///
+    /// The returned id can be attached to content as metadata is the then
+    /// locatable through [`locate`](Self::locate).
+    pub fn identify<T: Hash>(&mut self, key: &T) -> StableId {
+        self.provider.identify(hash128(key))
+    }
+
+    /// Locate all metadata matches for the given selector.
+    pub fn locate(&self, selector: Selector) -> Vec<(StableId, &Content)> {
+        self.introspector.locate(selector)
+    }
+}
+
+/// Stably identifies a call site across multiple layout passes.
+///
+/// This struct is created by [`Vt::identify`].
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
+pub struct StableId(u128, u64);
+
+/// Provides stable identities to nodes.
+#[derive(Clone)]
+#[doc(hidden)]
+pub struct StabilityProvider(HashMap<u128, u64>);
+
+impl StabilityProvider {
+    /// Create a new stability provider.
+    fn new() -> Self {
+        Self(HashMap::new())
+    }
+}
+
+#[comemo::track]
+impl StabilityProvider {
+    /// Produce a stable identifier for this call site.
+    fn identify(&mut self, hash: u128) -> StableId {
+        let slot = self.0.entry(hash).or_default();
+        let id = StableId(hash, *slot);
+        *slot += 1;
+        id
+    }
+}
+
+/// Provides access to information about the document.
+#[doc(hidden)]
+pub struct Introspector {
+    nodes: Vec<(StableId, Content)>,
+    queries: RefCell<Vec<(Selector, u128)>>,
+}
+
+impl Introspector {
+    /// Create a new introspector.
+    fn new() -> Self {
+        Self { nodes: vec![], queries: RefCell::new(vec![]) }
+    }
+
+    /// Update the information given new frames and return whether we can stop
+    /// layouting.
+    fn update(&mut self, document: &Document) -> bool {
+        self.nodes.clear();
+
+        for (i, frame) in document.pages.iter().enumerate() {
+            let page = NonZeroUsize::new(1 + i).unwrap();
+            self.extract(frame, page, Transform::identity());
+        }
+
+        let queries = std::mem::take(&mut self.queries).into_inner();
+        for (selector, hash) in queries {
+            let nodes = self.locate_impl(&selector);
+            if hash128(&nodes) != hash {
+                return false;
+            }
+        }
+
+        true
+    }
+
+    /// Extract metadata from a frame.
+    fn extract(&mut self, frame: &Frame, page: NonZeroUsize, ts: Transform) {
+        for (pos, element) in frame.elements() {
+            match *element {
+                Element::Group(ref group) => {
+                    let ts = ts
+                        .pre_concat(Transform::translate(pos.x, pos.y))
+                        .pre_concat(group.transform);
+                    self.extract(&group.frame, page, ts);
+                }
+                Element::Meta(Meta::Node(id, ref content), _) => {
+                    if !self.nodes.iter().any(|&(prev, _)| prev == id) {
+                        let pos = pos.transform(ts);
+                        let mut node = content.clone();
+                        let loc = Location { page, pos };
+                        node.push_field("loc", Value::Dict(loc.encode()));
+                        self.nodes.push((id, node));
+                    }
+                }
+                _ => {}
+            }
+        }
+    }
+}
+
+#[comemo::track]
+impl Introspector {
+    /// Locate all metadata matches for the given selector.
+    fn locate(&self, selector: Selector) -> Vec<(StableId, &Content)> {
+        let nodes = self.locate_impl(&selector);
+        let mut queries = self.queries.borrow_mut();
+        if !queries.iter().any(|(prev, _)| prev == &selector) {
+            queries.push((selector, hash128(&nodes)));
+        }
+        nodes
+    }
+}
+
+impl Introspector {
+    fn locate_impl(&self, selector: &Selector) -> Vec<(StableId, &Content)> {
+        self.nodes
+            .iter()
+            .map(|(id, node)| (*id, node))
+            .filter(|(_, target)| selector.matches(target))
+            .collect()
+    }
 }