From 9bc90c371fb41a2d6dc08eb4673e5be15f829514 Mon Sep 17 00:00:00 2001
From: Laurenz <laurmaedje@gmail.com>
Date: Fri, 2 Dec 2022 15:41:39 +0100
Subject: Introspection

---
 src/model/cast.rs    |  14 +++--
 src/model/content.rs |  67 +++++++++++++-------
 src/model/ops.rs     |   1 -
 src/model/realize.rs |  13 +++-
 src/model/styles.rs  |  13 ++--
 src/model/typeset.rs | 173 +++++++++++++++++++++++++++++++++++++++++++++++++--
 6 files changed, 245 insertions(+), 36 deletions(-)

(limited to 'src/model')

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,17 +255,23 @@ 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",
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()
+    }
 }
-- 
cgit v1.2.3