Automatic frame merging

7 files changed, 158 insertions, 45 deletions

diff --git a/src/frame.rs b/src/frame.rs
index bda9307f..5ee6e77e 100644
--- a/src/frame.rs
+++ b/src/frame.rs
@@ -1,6 +1,6 @@
 //! Finished layouts.
 
-use std::fmt::{self, Debug, Formatter};
+use std::fmt::{self, Debug, Formatter, Write};
 use std::sync::Arc;
 
 use crate::font::FaceId;
@@ -8,6 +8,7 @@ use crate::geom::{
     Align, Em, Length, Numeric, Paint, Path, Point, Size, Spec, Stroke, Transform,
 };
 use crate::image::ImageId;
+use crate::util::{EcoString, MaybeShared};
 
 /// A finished layout with elements at fixed positions.
 #[derive(Default, Clone, Eq, PartialEq)]
@@ -57,20 +58,15 @@ impl Frame {
         self.elements.insert(layer, (pos, element));
     }
 
-    /// Add a group element.
-    pub fn push_frame(&mut self, pos: Point, frame: Arc<Self>) {
-        self.elements.push((pos, Element::Group(Group::new(frame))));
-    }
-
-    /// Add all elements of another frame, placing them relative to the given
-    /// position.
-    pub fn merge_frame(&mut self, pos: Point, subframe: Self) {
-        if pos == Point::zero() && self.elements.is_empty() {
-            self.elements = subframe.elements;
+    /// Add a frame.
+    ///
+    /// Automatically decides whether to inline the frame or to include it as a
+    /// group based on the number of elements in the frame.
+    pub fn push_frame(&mut self, pos: Point, frame: impl FrameRepr) {
+        if self.elements.is_empty() || frame.as_ref().elements.len() <= 5 {
+            frame.inline(self, pos);
         } else {
-            for (subpos, child) in subframe.elements {
-                self.elements.push((pos + subpos, child));
-            }
+            self.elements.push((pos, Element::Group(Group::new(frame.share()))));
         }
     }
 
@@ -122,30 +118,86 @@ impl Frame {
     }
 
     /// Link the whole frame to a resource.
-    pub fn link(&mut self, url: impl Into<String>) {
-        self.push(Point::zero(), Element::Link(url.into(), self.size));
+    pub fn link(&mut self, url: EcoString) {
+        self.push(Point::zero(), Element::Link(url, self.size));
     }
 }
 
 impl Debug for Frame {
     fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        f.debug_struct("Frame")
-            .field("size", &self.size)
-            .field("baseline", &self.baseline)
-            .field(
-                "children",
-                &crate::util::debug(|f| {
-                    f.debug_map()
-                        .entries(self.elements.iter().map(|(k, v)| (k, v)))
-                        .finish()
-                }),
-            )
+        f.debug_list()
+            .entries(self.elements.iter().map(|(_, element)| element))
             .finish()
     }
 }
 
+impl AsRef<Frame> for Frame {
+    fn as_ref(&self) -> &Frame {
+        self
+    }
+}
+
+/// A representational form of a frame (owned, shared or maybe shared).
+pub trait FrameRepr: AsRef<Frame> {
+    /// Transform into a shared representation.
+    fn share(self) -> Arc<Frame>;
+
+    /// Inline `self` into the sink frame.
+    fn inline(self, sink: &mut Frame, offset: Point);
+}
+
+impl FrameRepr for Frame {
+    fn share(self) -> Arc<Frame> {
+        Arc::new(self)
+    }
+
+    fn inline(self, sink: &mut Frame, offset: Point) {
+        if offset.is_zero() {
+            if sink.elements.is_empty() {
+                sink.elements = self.elements;
+            } else {
+                sink.elements.extend(self.elements);
+            }
+        } else {
+            sink.elements
+                .extend(self.elements.into_iter().map(|(p, e)| (p + offset, e)));
+        }
+    }
+}
+
+impl FrameRepr for Arc<Frame> {
+    fn share(self) -> Arc<Frame> {
+        self
+    }
+
+    fn inline(self, sink: &mut Frame, offset: Point) {
+        match Arc::try_unwrap(self) {
+            Ok(frame) => frame.inline(sink, offset),
+            Err(rc) => sink
+                .elements
+                .extend(rc.elements.iter().cloned().map(|(p, e)| (p + offset, e))),
+        }
+    }
+}
+
+impl FrameRepr for MaybeShared<Frame> {
+    fn share(self) -> Arc<Frame> {
+        match self {
+            Self::Owned(owned) => owned.share(),
+            Self::Shared(shared) => shared.share(),
+        }
+    }
+
+    fn inline(self, sink: &mut Frame, offset: Point) {
+        match self {
+            Self::Owned(owned) => owned.inline(sink, offset),
+            Self::Shared(shared) => shared.inline(sink, offset),
+        }
+    }
+}
+
 /// The building block frames are composed of.
-#[derive(Debug, Clone, Eq, PartialEq)]
+#[derive(Clone, Eq, PartialEq)]
 pub enum Element {
     /// A group of elements.
     Group(Group),
@@ -156,11 +208,23 @@ pub enum Element {
     /// An image and its size.
     Image(ImageId, Size),
     /// A link to an external resource and its trigger region.
-    Link(String, Size),
+    Link(EcoString, Size),
+}
+
+impl Debug for Element {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        match self {
+            Self::Group(group) => group.fmt(f),
+            Self::Text(text) => write!(f, "{text:?}"),
+            Self::Shape(shape) => write!(f, "{shape:?}"),
+            Self::Image(image, _) => write!(f, "{image:?}"),
+            Self::Link(url, _) => write!(f, "Link({url:?})"),
+        }
+    }
 }
 
 /// A group of elements with optional clipping.
-#[derive(Debug, Clone, Eq, PartialEq)]
+#[derive(Clone, Eq, PartialEq)]
 pub struct Group {
     /// The group's frame.
     pub frame: Arc<Frame>,
@@ -181,8 +245,15 @@ impl Group {
     }
 }
 
+impl Debug for Group {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        f.write_str("Group ")?;
+        self.frame.fmt(f)
+    }
+}
+
 /// A run of shaped text.
-#[derive(Debug, Clone, Eq, PartialEq)]
+#[derive(Clone, Eq, PartialEq)]
 pub struct Text {
     /// The font face the glyphs are contained in.
     pub face_id: FaceId,
@@ -201,6 +272,19 @@ impl Text {
     }
 }
 
+impl Debug for Text {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        // This is only a rough approxmiation of the source text.
+        f.write_str("Text(\"")?;
+        for glyph in &self.glyphs {
+            for c in glyph.c.escape_debug() {
+                f.write_char(c)?;
+            }
+        }
+        f.write_str("\")")
+    }
+}
+
 /// A glyph in a run of shaped text.
 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
 pub struct Glyph {
@@ -210,6 +294,8 @@ pub struct Glyph {
     pub x_advance: Em,
     /// The horizontal offset of the glyph.
     pub x_offset: Em,
+    /// The first character of the glyph's cluster.
+    pub c: char,
 }
 
 /// A geometric shape with optional fill and stroke.
diff --git a/src/library/graphics/image.rs b/src/library/graphics/image.rs
index 193dc60e..ee854130 100644
--- a/src/library/graphics/image.rs
+++ b/src/library/graphics/image.rs
@@ -83,7 +83,7 @@ impl Layout for ImageNode {
 
         // Apply link if it exists.
         if let Some(url) = styles.get(TextNode::LINK) {
-            frame.link(url);
+            frame.link(url.clone());
         }
 
         Ok(vec![Arc::new(frame)])
diff --git a/src/library/graphics/shape.rs b/src/library/graphics/shape.rs
index 236406c0..e4c832f0 100644
--- a/src/library/graphics/shape.rs
+++ b/src/library/graphics/shape.rs
@@ -132,7 +132,7 @@ impl<const S: ShapeKind> Layout for ShapeNode<S> {
 
         // Apply link if it exists.
         if let Some(url) = styles.get(TextNode::LINK) {
-            frame.link(url);
+            frame.link(url.clone());
         }
 
         Ok(frames)
diff --git a/src/library/layout/grid.rs b/src/library/layout/grid.rs
index ad6323d5..4908d4d8 100644
--- a/src/library/layout/grid.rs
+++ b/src/library/layout/grid.rs
@@ -551,7 +551,7 @@ impl<'a> GridLayouter<'a> {
             };
 
             let height = frame.size.y;
-            output.merge_frame(pos, frame);
+            output.push_frame(pos, frame);
             pos.y += height;
         }
 
diff --git a/src/library/text/par.rs b/src/library/text/par.rs
index 9f45a411..17fcea75 100644
--- a/src/library/text/par.rs
+++ b/src/library/text/par.rs
@@ -8,7 +8,7 @@ use super::{shape, Lang, Quoter, Quotes, RepeatNode, ShapedText, TextNode};
 use crate::font::FontStore;
 use crate::library::layout::Spacing;
 use crate::library::prelude::*;
-use crate::util::{ArcExt, EcoString};
+use crate::util::{EcoString, MaybeShared};
 
 /// Arrange text, spacing and inline-level nodes into a paragraph.
 #[derive(Hash)]
@@ -283,7 +283,7 @@ enum Item<'a> {
     /// Fractional spacing between other items.
     Fractional(Fraction),
     /// A layouted child node.
-    Frame(Frame),
+    Frame(Arc<Frame>),
     /// A repeating node.
     Repeat(&'a RepeatNode, StyleChain<'a>),
 }
@@ -522,7 +522,7 @@ fn prepare<'a>(
                     let size = Size::new(regions.first.x, regions.base.y);
                     let pod = Regions::one(size, regions.base, Spec::splat(false));
                     let frame = node.layout(ctx, &pod, styles)?.remove(0);
-                    items.push(Item::Frame(Arc::take(frame)));
+                    items.push(Item::Frame(frame));
                 }
             }
         }
@@ -1041,7 +1041,7 @@ fn stack(
 
         let pos = Point::with_y(output.size.y);
         output.size.y += height;
-        output.merge_frame(pos, frame);
+        output.push_frame(pos, frame);
 
         regions.first.y -= height + p.leading;
         first = false;
@@ -1111,7 +1111,7 @@ fn commit(
     // Build the frames and determine the height and baseline.
     let mut frames = vec![];
     for item in reordered {
-        let mut push = |offset: &mut Length, frame: Frame| {
+        let mut push = |offset: &mut Length, frame: MaybeShared<Frame>| {
             let width = frame.size.x;
             top.set_max(frame.baseline());
             bottom.set_max(frame.size.y - frame.baseline());
@@ -1127,10 +1127,11 @@ fn commit(
                 offset += v.share(fr, remaining);
             }
             Item::Text(shaped) => {
-                push(&mut offset, shaped.build(&mut ctx.fonts, justification));
+                let frame = shaped.build(&mut ctx.fonts, justification);
+                push(&mut offset, MaybeShared::Owned(frame));
             }
             Item::Frame(frame) => {
-                push(&mut offset, frame.clone());
+                push(&mut offset, MaybeShared::Shared(frame.clone()));
             }
             Item::Repeat(node, styles) => {
                 let before = offset;
@@ -1146,7 +1147,7 @@ fn commit(
                 }
                 if frame.size.x > Length::zero() {
                     for _ in 0 .. (count as usize).min(1000) {
-                        push(&mut offset, frame.as_ref().clone());
+                        push(&mut offset, MaybeShared::Shared(frame.clone()));
                         offset += apart;
                     }
                 }
@@ -1168,7 +1169,7 @@ fn commit(
     for (offset, frame) in frames {
         let x = offset + p.align.position(remaining);
         let y = top - frame.baseline();
-        output.merge_frame(Point::new(x, y), frame);
+        output.push_frame(Point::new(x, y), frame);
     }
 
     Ok(output)
diff --git a/src/library/text/shaping.rs b/src/library/text/shaping.rs
index 055761df..80f1b17d 100644
--- a/src/library/text/shaping.rs
+++ b/src/library/text/shaping.rs
@@ -100,6 +100,7 @@ impl<'a> ShapedText<'a> {
                             Em::zero()
                         },
                     x_offset: glyph.x_offset,
+                    c: glyph.c,
                 })
                 .collect();
 
@@ -118,7 +119,7 @@ impl<'a> ShapedText<'a> {
 
         // Apply link if it exists.
         if let Some(url) = self.styles.get(TextNode::LINK) {
-            frame.link(url);
+            frame.link(url.clone());
         }
 
         frame
diff --git a/src/util/mod.rs b/src/util/mod.rs
index d898f545..3bc13bac 100644
--- a/src/util/mod.rs
+++ b/src/util/mod.rs
@@ -11,7 +11,7 @@ pub use prehashed::Prehashed;
 
 use std::cmp::Ordering;
 use std::fmt::{self, Debug, Formatter};
-use std::ops::Range;
+use std::ops::{Deref, Range};
 use std::path::{Component, Path, PathBuf};
 use std::sync::Arc;
 
@@ -101,6 +101,31 @@ where
     }
 }
 
+/// Either owned or shared.
+pub enum MaybeShared<T> {
+    /// Owned data.
+    Owned(T),
+    /// Shared data.
+    Shared(Arc<T>),
+}
+
+impl<T> AsRef<T> for MaybeShared<T> {
+    fn as_ref(&self) -> &T {
+        self
+    }
+}
+
+impl<T> Deref for MaybeShared<T> {
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        match self {
+            Self::Owned(owned) => owned,
+            Self::Shared(shared) => shared,
+        }
+    }
+}
+
 /// Additional methods for slices.
 pub trait SliceExt<T> {
     /// Split a slice into consecutive runs with the same key and yield for