Merge pull request #71 from typst/pins

5 files changed, 411 insertions, 16 deletions

diff --git a/src/model/content.rs b/src/model/content.rs
index c09979d5..21bf8369 100644
--- a/src/model/content.rs
+++ b/src/model/content.rs
@@ -7,8 +7,8 @@ use std::ops::{Add, AddAssign};
 use typed_arena::Arena;
 
 use super::{
-    Barrier, CollapsingBuilder, Interruption, Key, Layout, LayoutNode, Property, Show,
-    ShowNode, StyleEntry, StyleMap, StyleVecBuilder, Target,
+    Barrier, CollapsingBuilder, Interruption, Key, Layout, LayoutNode, LocateNode,
+    Property, Show, ShowNode, StyleEntry, StyleMap, StyleVecBuilder, Target,
 };
 use crate::diag::StrResult;
 use crate::library::layout::{FlowChild, FlowNode, PageNode, PlaceNode, Spacing};
@@ -20,7 +20,33 @@ use crate::library::text::{
 use crate::util::EcoString;
 
 /// Layout content into a collection of pages.
+///
+/// Relayouts until all pinned locations are converged.
 pub fn layout(ctx: &mut Context, content: &Content) -> TypResult<Vec<Arc<Frame>>> {
+    let mut pass = 0;
+    let mut frames;
+
+    loop {
+        let prev = ctx.pins.clone();
+        let result = layout_once(ctx, content);
+        ctx.pins.reset();
+        frames = result?;
+        pass += 1;
+
+        ctx.pins.locate(&frames);
+
+        // Quit if we're done or if we've had five passes.
+        let unresolved = ctx.pins.unresolved(&prev);
+        if unresolved == 0 || pass >= 5 {
+            break;
+        }
+    }
+
+    Ok(frames)
+}
+
+/// Layout content into a collection of pages once.
+fn layout_once(ctx: &mut Context, content: &Content) -> TypResult<Vec<Arc<Frame>>> {
     let copy = ctx.config.styles.clone();
     let styles = StyleChain::with_root(&copy);
     let scratch = Scratch::default();
@@ -88,6 +114,10 @@ pub enum Content {
     /// A node that can be realized with styles, optionally with attached
     /// properties.
     Show(ShowNode, Option<Dict>),
+    /// A node that can be realized with its location on the page.
+    Locate(LocateNode),
+    /// A pin identified by index.
+    Pin(usize),
     /// Content with attached styles.
     Styled(Arc<(Self, StyleMap)>),
     /// A sequence of multiple nodes.
@@ -272,6 +302,8 @@ impl Debug for Content {
             Self::Pagebreak { weak } => write!(f, "Pagebreak({weak})"),
             Self::Page(page) => page.fmt(f),
             Self::Show(node, _) => node.fmt(f),
+            Self::Locate(node) => node.fmt(f),
+            Self::Pin(idx) => write!(f, "Pin({idx})"),
             Self::Styled(styled) => {
                 let (sub, map) = styled.as_ref();
                 map.fmt(f)?;
@@ -388,6 +420,7 @@ impl<'a, 'ctx> Builder<'a, 'ctx> {
             }
 
             Content::Show(node, _) => return self.show(node, styles),
+            Content::Locate(node) => return self.locate(node, styles),
             Content::Styled(styled) => return self.styled(styled, styles),
             Content::Sequence(seq) => return self.sequence(seq, styles),
 
@@ -436,6 +469,12 @@ impl<'a, 'ctx> Builder<'a, 'ctx> {
         Ok(())
     }
 
+    fn locate(&mut self, node: &LocateNode, styles: StyleChain<'a>) -> TypResult<()> {
+        let realized = node.realize(self.ctx)?;
+        let stored = self.scratch.templates.alloc(realized);
+        self.accept(stored, styles)
+    }
+
     fn styled(
         &mut self,
         (content, map): &'a (Content, StyleMap),
@@ -641,6 +680,9 @@ impl<'a> ParBuilder<'a> {
             Content::Inline(node) => {
                 self.0.supportive(ParChild::Node(node.clone()), styles);
             }
+            &Content::Pin(idx) => {
+                self.0.ignorant(ParChild::Pin(idx), styles);
+            }
             _ => return false,
         }
 
@@ -660,7 +702,7 @@ impl<'a> ParBuilder<'a> {
             && children
                 .items()
                 .find_map(|child| match child {
-                    ParChild::Spacing(_) => None,
+                    ParChild::Spacing(_) | ParChild::Pin(_) => None,
                     ParChild::Text(_) | ParChild::Quote { .. } => Some(true),
                     ParChild::Node(_) => Some(false),
                 })
diff --git a/src/model/layout.rs b/src/model/layout.rs
index 6dfbcb90..92d73977 100644
--- a/src/model/layout.rs
+++ b/src/model/layout.rs
@@ -221,13 +221,20 @@ impl Layout for LayoutNode {
         regions: &Regions,
         styles: StyleChain,
     ) -> TypResult<Vec<Arc<Frame>>> {
-        crate::memo::memoized(
-            (self, ctx, regions, styles),
+        let (result, at, pins) = crate::memo::memoized(
+            (self, &mut *ctx, regions, styles),
             |(node, ctx, regions, styles)| {
+                let at = ctx.pins.cursor();
                 let entry = StyleEntry::Barrier(Barrier::new(node.id()));
-                node.0.layout(ctx, regions, entry.chain(&styles))
+                let result = node.0.layout(ctx, regions, entry.chain(&styles));
+                (result, at, ctx.pins.from(at))
             },
-        )
+        );
+
+        // Replay the side effect in case of caching. This should currently be
+        // more or less the only relevant side effect on the context.
+        ctx.pins.replay(at, pins);
+        result
     }
 
     fn pack(self) -> LayoutNode {
diff --git a/src/model/locate.rs b/src/model/locate.rs
new file mode 100644
index 00000000..97c14034
--- /dev/null
+++ b/src/model/locate.rs
@@ -0,0 +1,342 @@
+use std::fmt::{self, Debug, Formatter};
+use std::sync::Arc;
+
+use super::Content;
+use crate::diag::TypResult;
+use crate::eval::{Args, Array, Dict, Func, Value};
+use crate::frame::{Element, Frame, Location};
+use crate::geom::{Point, Transform};
+use crate::syntax::Spanned;
+use crate::util::EcoString;
+use crate::Context;
+
+/// A group of locatable elements.
+#[derive(Clone, Eq, PartialEq, Hash)]
+pub struct Group(EcoString);
+
+impl Group {
+    /// Create a group of elements that is identified by a string key.
+    pub fn new(key: EcoString) -> Self {
+        Self(key)
+    }
+
+    /// Add an entry to the group.
+    pub fn entry(&self, recipe: Spanned<Func>, value: Option<Value>) -> LocateNode {
+        LocateNode::entry(self.clone(), recipe, value)
+    }
+
+    /// Do something with all entries of a group.
+    pub fn all(&self, recipe: Spanned<Func>) -> LocateNode {
+        LocateNode::all(self.clone(), recipe)
+    }
+}
+
+impl Debug for Group {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "group({:?})", self.0)
+    }
+}
+
+/// A node that can be realized with pinned document locations.
+#[derive(Debug, Clone, PartialEq, Hash)]
+pub struct LocateNode(Arc<Repr>);
+
+impl LocateNode {
+    /// Create a new locatable single node.
+    pub fn single(recipe: Spanned<Func>) -> Self {
+        Self(Arc::new(Repr::Single(SingleNode(recipe))))
+    }
+
+    /// Create a new locatable group entry node.
+    pub fn entry(group: Group, recipe: Spanned<Func>, value: Option<Value>) -> Self {
+        Self(Arc::new(Repr::Entry(EntryNode { group, recipe, value })))
+    }
+
+    /// Create a new node with access to a group's members.
+    pub fn all(group: Group, recipe: Spanned<Func>) -> Self {
+        Self(Arc::new(Repr::All(AllNode { group, recipe })))
+    }
+
+    /// Realize the node.
+    pub fn realize(&self, ctx: &mut Context) -> TypResult<Content> {
+        match self.0.as_ref() {
+            Repr::Single(single) => single.realize(ctx),
+            Repr::Entry(entry) => entry.realize(ctx),
+            Repr::All(all) => all.realize(ctx),
+        }
+    }
+}
+
+/// The different kinds of locate nodes.
+#[derive(Debug, Clone, PartialEq, Hash)]
+enum Repr {
+    /// A single `locate(me => ...)`.
+    Single(SingleNode),
+    /// A locatable group entry.
+    Entry(EntryNode),
+    /// A recipe for all entries of a group.
+    All(AllNode),
+}
+
+/// An ungrouped locatable node.
+#[derive(Debug, Clone, PartialEq, Hash)]
+struct SingleNode(Spanned<Func>);
+
+impl SingleNode {
+    fn realize(&self, ctx: &mut Context) -> TypResult<Content> {
+        let idx = ctx.pins.cursor();
+        let pin = ctx.pins.get_or_create(None, None);
+        let dict = pin.encode(None);
+        let args = Args::new(self.0.span, [Value::Dict(dict)]);
+        Ok(Content::Pin(idx) + self.0.v.call_detached(ctx, args)?.display())
+    }
+}
+
+/// A locatable grouped node which can interact with its peers' details.
+#[derive(Debug, Clone, PartialEq, Hash)]
+struct EntryNode {
+    /// Which group the node belongs to.
+    group: Group,
+    /// The recipe to execute.
+    recipe: Spanned<Func>,
+    /// An arbitrary attached value.
+    value: Option<Value>,
+}
+
+impl EntryNode {
+    fn realize(&self, ctx: &mut Context) -> TypResult<Content> {
+        let idx = ctx.pins.cursor();
+        let pin = ctx.pins.get_or_create(Some(self.group.clone()), self.value.clone());
+
+        // Determine the index among the peers.
+        let index = ctx
+            .pins
+            .iter()
+            .enumerate()
+            .filter(|&(k, other)| {
+                other.is_in(&self.group)
+                    && if k < idx {
+                        other.flow <= pin.flow
+                    } else {
+                        other.flow < pin.flow
+                    }
+            })
+            .count();
+
+        // Prepare first argument.
+        let dict = pin.encode(Some(index));
+        let mut args = Args::new(self.recipe.span, [Value::Dict(dict)]);
+
+        // Collect all group members if second argument is requested.
+        if self.recipe.v.argc() == Some(2) {
+            let all = ctx.pins.encode_group(&self.group);
+            args.push(self.recipe.span, Value::Array(all))
+        }
+
+        Ok(Content::Pin(idx) + self.recipe.v.call_detached(ctx, args)?.display())
+    }
+}
+
+/// A node with access to a group's members.
+#[derive(Debug, Clone, PartialEq, Hash)]
+struct AllNode {
+    /// Which group the node has access to.
+    group: Group,
+    /// The recipe to execute.
+    recipe: Spanned<Func>,
+}
+
+impl AllNode {
+    fn realize(&self, ctx: &mut Context) -> TypResult<Content> {
+        let all = ctx.pins.encode_group(&self.group);
+        let args = Args::new(self.recipe.span, [Value::Array(all)]);
+        Ok(self.recipe.v.call_detached(ctx, args)?.display())
+    }
+}
+
+/// Manages document pins.
+#[derive(Debug, Clone, Hash)]
+pub struct PinBoard {
+    /// All currently active pins.
+    list: Vec<Pin>,
+    /// The index of the next pin, in order.
+    cursor: usize,
+    /// If larger than zero, the board is frozen and the cursor will not be
+    /// advanced. This is used to disable pinning during measure-only layouting.
+    frozen: usize,
+}
+
+impl PinBoard {
+    /// Create an empty pin board.
+    pub fn new() -> Self {
+        Self { list: vec![], cursor: 0, frozen: 0 }
+    }
+
+    /// The current cursor.
+    pub fn cursor(&self) -> usize {
+        self.cursor
+    }
+
+    /// All pins from `prev` to the current cursor.
+    pub fn from(&self, prev: usize) -> Vec<Pin> {
+        self.list[prev .. self.cursor].to_vec()
+    }
+
+    /// Add the given pins at the given location and set the cursor behind them.
+    pub fn replay(&mut self, at: usize, pins: Vec<Pin>) {
+        if !self.frozen() {
+            self.cursor = at + pins.len();
+            let end = self.cursor.min(self.list.len());
+            self.list.splice(at .. end, pins);
+        }
+    }
+
+    /// Freeze the board to prevent modifications.
+    pub fn freeze(&mut self) {
+        self.frozen += 1;
+    }
+
+    /// Freeze the board to prevent modifications.
+    pub fn unfreeze(&mut self) {
+        self.frozen -= 1;
+    }
+
+    /// Whether the board is currently frozen.
+    pub fn frozen(&self) -> bool {
+        self.frozen > 0
+    }
+
+    /// Reset the cursor and remove all unused pins.
+    pub fn reset(&mut self) {
+        self.list.truncate(self.cursor);
+        self.cursor = 0;
+    }
+
+    /// Locate all pins in the frames.
+    pub fn locate(&mut self, frames: &[Arc<Frame>]) {
+        let mut flow = 0;
+        for (i, frame) in frames.iter().enumerate() {
+            locate_in_frame(
+                &mut self.list,
+                &mut flow,
+                1 + i,
+                frame,
+                Transform::identity(),
+            );
+        }
+    }
+
+    /// How many pins are unresolved in comparison to an earlier snapshot.
+    pub fn unresolved(&self, prev: &Self) -> usize {
+        self.list.len() - self.list.iter().zip(&prev.list).filter(|(a, b)| a == b).count()
+    }
+
+    /// Access or create the next pin.
+    fn get_or_create(&mut self, group: Option<Group>, value: Option<Value>) -> Pin {
+        if self.frozen() {
+            return Pin::default();
+        }
+
+        let cursor = self.cursor;
+        self.cursor += 1;
+        if self.cursor >= self.list.len() {
+            self.list.resize(self.cursor, Pin::default());
+        }
+
+        let pin = &mut self.list[cursor];
+        pin.group = group;
+        pin.value = value;
+        pin.clone()
+    }
+
+    /// Iterate over all pins on the board.
+    fn iter(&self) -> std::slice::Iter<Pin> {
+        self.list.iter()
+    }
+
+    /// Encode a group into a user-facing array.
+    fn encode_group(&self, group: &Group) -> Array {
+        let mut all: Vec<_> = self.iter().filter(|pin| pin.is_in(group)).collect();
+        all.sort_by_key(|pin| pin.flow);
+        all.iter()
+            .enumerate()
+            .map(|(index, member)| Value::Dict(member.encode(Some(index))))
+            .collect()
+    }
+}
+
+/// Locate all pins in a frame.
+fn locate_in_frame(
+    pins: &mut [Pin],
+    flow: &mut usize,
+    page: usize,
+    frame: &Frame,
+    ts: Transform,
+) {
+    for &(pos, ref element) in &frame.elements {
+        match element {
+            Element::Group(group) => {
+                let ts = ts
+                    .pre_concat(Transform::translate(pos.x, pos.y))
+                    .pre_concat(group.transform);
+                locate_in_frame(pins, flow, page, &group.frame, ts);
+            }
+
+            Element::Pin(idx) => {
+                let pin = &mut pins[*idx];
+                pin.loc.page = page;
+                pin.loc.pos = pos.transform(ts);
+                pin.flow = *flow;
+                *flow += 1;
+            }
+
+            _ => {}
+        }
+    }
+}
+
+/// A document pin.
+#[derive(Debug, Clone, PartialEq, Hash)]
+pub struct Pin {
+    /// The physical location of the pin in the document.
+    loc: Location,
+    /// The flow index.
+    flow: usize,
+    /// The group the pin belongs to, if any.
+    group: Option<Group>,
+    /// An arbitrary attached value.
+    value: Option<Value>,
+}
+
+impl Pin {
+    /// Whether the pin is part of the given group.
+    fn is_in(&self, group: &Group) -> bool {
+        self.group.as_ref() == Some(group)
+    }
+
+    /// Encode into a user-facing dictionary.
+    fn encode(&self, index: Option<usize>) -> Dict {
+        let mut dict = self.loc.encode();
+
+        if let Some(value) = &self.value {
+            dict.insert("value".into(), value.clone());
+        }
+
+        if let Some(index) = index {
+            dict.insert("index".into(), Value::Int(index as i64));
+        }
+
+        dict
+    }
+}
+
+impl Default for Pin {
+    fn default() -> Self {
+        Self {
+            loc: Location { page: 0, pos: Point::zero() },
+            flow: 0,
+            group: None,
+            value: None,
+        }
+    }
+}
diff --git a/src/model/mod.rs b/src/model/mod.rs
index 5c8b82c0..379b633f 100644
--- a/src/model/mod.rs
+++ b/src/model/mod.rs
@@ -5,6 +5,7 @@ mod styles;
 mod collapse;
 mod content;
 mod layout;
+mod locate;
 mod property;
 mod recipe;
 mod show;
@@ -12,6 +13,7 @@ mod show;
 pub use collapse::*;
 pub use content::*;
 pub use layout::*;
+pub use locate::*;
 pub use property::*;
 pub use recipe::*;
 pub use show::*;
diff --git a/src/model/recipe.rs b/src/model/recipe.rs
index e4417adf..6261e704 100644
--- a/src/model/recipe.rs
+++ b/src/model/recipe.rs
@@ -4,7 +4,7 @@ use super::{Content, Interruption, NodeId, Show, ShowNode, StyleChain, StyleEntr
 use crate::diag::TypResult;
 use crate::eval::{Args, Func, Regex, Value};
 use crate::library::structure::{EnumNode, ListNode};
-use crate::syntax::Span;
+use crate::syntax::Spanned;
 use crate::Context;
 
 /// A show rule recipe.
@@ -13,9 +13,7 @@ pub struct Recipe {
     /// The patterns to customize.
     pub pattern: Pattern,
     /// The function that defines the recipe.
-    pub func: Func,
-    /// The span to report all erros with.
-    pub span: Span,
+    pub func: Spanned<Func>,
 }
 
 impl Recipe {
@@ -81,13 +79,13 @@ impl Recipe {
     where
         F: FnOnce() -> Value,
     {
-        let args = if self.func.argc() == Some(0) {
-            Args::new(self.span, [])
+        let args = if self.func.v.argc() == Some(0) {
+            Args::new(self.func.span, [])
         } else {
-            Args::new(self.span, [arg()])
+            Args::new(self.func.span, [arg()])
         };
 
-        Ok(self.func.call_detached(ctx, args)?.display())
+        Ok(self.func.v.call_detached(ctx, args)?.display())
     }
 
     /// What kind of structure the property interrupts.
@@ -104,7 +102,11 @@ impl Recipe {
 
 impl Debug for Recipe {
     fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        write!(f, "Recipe matching {:?} from {:?}", self.pattern, self.span)
+        write!(
+            f,
+            "Recipe matching {:?} from {:?}",
+            self.pattern, self.func.span
+        )
     }
 }