Ref count the frames

9 files changed, 111 insertions, 49 deletions

diff --git a/src/layout/background.rs b/src/layout/background.rs
index 41138bdf..8390a756 100644
--- a/src/layout/background.rs
+++ b/src/layout/background.rs
@@ -23,10 +23,11 @@ impl Layout for BackgroundNode {
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
-    ) -> Vec<Constrained<Frame>> {
+    ) -> Vec<Constrained<Rc<Frame>>> {
         let mut frames = self.child.layout(ctx, regions);
-
         for frame in &mut frames {
+            let mut new = Frame::new(frame.size, frame.baseline);
+
             let (point, shape) = match self.shape {
                 BackgroundShape::Rect => (Point::zero(), Shape::Rect(frame.size)),
                 BackgroundShape::Ellipse => {
@@ -35,9 +36,13 @@ impl Layout for BackgroundNode {
             };
 
             let element = Element::Geometry(shape, self.fill);
-            frame.item.elements.insert(0, (point, element));
-        }
+            new.push(point, element);
 
+            let prev = std::mem::take(&mut frame.item);
+            new.push_frame(Point::zero(), prev);
+
+            *Rc::make_mut(&mut frame.item) = new;
+        }
         frames
     }
 }
diff --git a/src/layout/fixed.rs b/src/layout/fixed.rs
index 19876987..73235168 100644
--- a/src/layout/fixed.rs
+++ b/src/layout/fixed.rs
@@ -16,7 +16,7 @@ impl Layout for FixedNode {
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
-    ) -> Vec<Constrained<Frame>> {
+    ) -> Vec<Constrained<Rc<Frame>>> {
         let Regions { current, base, .. } = regions;
         let mut constraints = Constraints::new(regions.expand);
         constraints.set_base_using_linears(Spec::new(self.width, self.height), &regions);
diff --git a/src/layout/frame.rs b/src/layout/frame.rs
index 5e5bcfe8..b6cf4645 100644
--- a/src/layout/frame.rs
+++ b/src/layout/frame.rs
@@ -1,3 +1,5 @@
+use std::rc::Rc;
+
 use serde::{Deserialize, Serialize};
 
 use super::{Constrained, Constraints};
@@ -14,37 +16,93 @@ pub struct Frame {
     /// The baseline of the frame measured from the top.
     pub baseline: Length,
     /// The elements composing this layout.
-    pub elements: Vec<(Point, Element)>,
+    children: Vec<(Point, Child)>,
+}
+
+/// An iterator over all elements in a frame, alongside with their positions.
+#[derive(Debug, Clone)]
+pub struct ElementIter<'a> {
+    stack: Vec<(usize, Point, &'a Frame)>,
+}
+
+impl<'a> Iterator for ElementIter<'a> {
+    type Item = (Point, &'a Element);
+
+    /// Get the next element, if any.
+    fn next(&mut self) -> Option<Self::Item> {
+        let (cursor, offset, frame) = self.stack.last_mut()?;
+        match frame.children.get(*cursor) {
+            Some((pos, Child::Frame(f))) => {
+                let new_offset = *offset + *pos;
+                self.stack.push((0, new_offset, f.as_ref()));
+                self.next()
+            }
+            Some((pos, Child::Element(e))) => {
+                *cursor += 1;
+                Some((*offset + *pos, e))
+            }
+            None => {
+                self.stack.pop();
+                if let Some((cursor, _, _)) = self.stack.last_mut() {
+                    *cursor += 1;
+                }
+                self.next()
+            }
+        }
+    }
 }
 
 impl Frame {
     /// Create a new, empty frame.
     pub fn new(size: Size, baseline: Length) -> Self {
         assert!(size.is_finite());
-        Self { size, baseline, elements: vec![] }
+        Self { size, baseline, children: vec![] }
     }
 
-    /// Add an element at a position.
+    /// Add an element at a position in the foreground.
     pub fn push(&mut self, pos: Point, element: Element) {
-        self.elements.push((pos, element));
+        self.children.push((pos, Child::Element(element)));
+    }
+
+    /// Add an element at a position in the background.
+    pub fn prepend(&mut self, pos: Point, element: Element) {
+        self.children.insert(0, (pos, Child::Element(element)))
+    }
+
+    /// Add a frame element.
+    pub fn push_frame(&mut self, pos: Point, subframe: Rc<Self>) {
+        self.children.push((pos, Child::Frame(subframe)))
     }
 
     /// Add all elements of another frame, placing them relative to the given
     /// position.
-    pub fn push_frame(&mut self, pos: Point, subframe: Self) {
-        if pos == Point::zero() && self.elements.is_empty() {
-            self.elements = subframe.elements;
+    pub fn merge_frame(&mut self, pos: Point, subframe: Self) {
+        if pos == Point::zero() && self.children.is_empty() {
+            self.children = subframe.children;
         } else {
-            for (subpos, element) in subframe.elements {
-                self.push(pos + subpos, element);
+            for (subpos, child) in subframe.children {
+                self.children.push((pos + subpos, child));
             }
         }
     }
 
     /// Wraps the frame with constraints.
-    pub fn constrain(self, constraints: Constraints) -> Constrained<Self> {
-        Constrained { item: self, constraints }
+    pub fn constrain(self, constraints: Constraints) -> Constrained<Rc<Self>> {
+        Constrained { item: Rc::new(self), constraints }
     }
+
+    /// Returns an iterator over all elements in the frame and its children.
+    pub fn elements(&self) -> ElementIter {
+        ElementIter { stack: vec![(0, Point::zero(), self)] }
+    }
+}
+
+/// A frame can contain multiple children: elements or other frames, complete
+/// with their children.
+#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
+enum Child {
+    Element(Element),
+    Frame(Rc<Frame>),
 }
 
 /// The building block frames are composed of.
diff --git a/src/layout/grid.rs b/src/layout/grid.rs
index e426d695..d2976502 100644
--- a/src/layout/grid.rs
+++ b/src/layout/grid.rs
@@ -32,7 +32,7 @@ impl Layout for GridNode {
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
-    ) -> Vec<Constrained<Frame>> {
+    ) -> Vec<Constrained<Rc<Frame>>> {
         // Prepare grid layout by unifying content and gutter tracks.
         let mut layouter = GridLayouter::new(self, regions.clone());
 
@@ -78,7 +78,7 @@ struct GridLayouter<'a> {
     /// Constraints for the active region.
     constraints: Constraints,
     /// Frames for finished regions.
-    finished: Vec<Constrained<Frame>>,
+    finished: Vec<Constrained<Rc<Frame>>>,
 }
 
 /// Produced by initial row layout, auto and linear rows are already finished,
@@ -314,7 +314,7 @@ impl<'a> GridLayouter<'a> {
     }
 
     /// Layout the grid row-by-row.
-    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Constrained<Frame>> {
+    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Constrained<Rc<Frame>>> {
         for y in 0 .. self.rows.len() {
             match self.rows[y] {
                 TrackSizing::Auto => {
@@ -497,7 +497,7 @@ impl<'a> GridLayouter<'a> {
             };
 
             let main = frame.size.get(self.main);
-            output.push_frame(pos.to_point(self.main), frame);
+            output.merge_frame(pos.to_point(self.main), frame);
             pos.main += main;
         }
 
diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs
index 7857f33c..a5c3cea3 100644
--- a/src/layout/incremental.rs
+++ b/src/layout/incremental.rs
@@ -26,7 +26,7 @@ impl LayoutCache {
     where
         F: FnMut(usize) -> bool,
     {
-        self.frames.retain(|_, b| f(b.level));
+        self.frames.retain(|_, entry| f(entry.level));
     }
 
     /// Amount of items in the cache.
@@ -39,14 +39,14 @@ impl LayoutCache {
 /// Cached frames from past layouting.
 pub struct FramesEntry {
     /// The cached frames for a node.
-    pub frames: Vec<Constrained<Frame>>,
+    pub frames: Vec<Constrained<Rc<Frame>>>,
     /// How nested the frame was in the context is was originally appearing in.
     pub level: usize,
 }
 
 impl FramesEntry {
     /// Checks if the cached [`Frame`] is valid for the given regions.
-    pub fn check(&self, mut regions: Regions) -> Option<Vec<Constrained<Frame>>> {
+    pub fn check(&self, mut regions: Regions) -> Option<Vec<Constrained<Rc<Frame>>>> {
         for (i, frame) in self.frames.iter().enumerate() {
             if (i != 0 && !regions.next()) || !frame.constraints.check(&regions) {
                 return None;
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index 28e83da9..f1ae3e2a 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -23,6 +23,7 @@ pub use stack::*;
 use std::any::Any;
 use std::fmt::{self, Debug, Formatter};
 use std::hash::{Hash, Hasher};
+use std::rc::Rc;
 
 use fxhash::FxHasher64;
 
@@ -31,7 +32,7 @@ use crate::geom::*;
 use crate::loading::Loader;
 
 /// Layout a tree into a collection of frames.
-pub fn layout(loader: &mut dyn Loader, cache: &mut Cache, tree: &Tree) -> Vec<Frame> {
+pub fn layout(loader: &mut dyn Loader, cache: &mut Cache, tree: &Tree) -> Vec<Rc<Frame>> {
     tree.layout(&mut LayoutContext { loader, cache, level: 0 })
 }
 
@@ -44,7 +45,7 @@ pub struct Tree {
 
 impl Tree {
     /// Layout the tree into a collection of frames.
-    pub fn layout(&self, ctx: &mut LayoutContext) -> Vec<Frame> {
+    pub fn layout(&self, ctx: &mut LayoutContext) -> Vec<Rc<Frame>> {
         self.runs.iter().flat_map(|run| run.layout(ctx)).collect()
     }
 }
@@ -61,7 +62,7 @@ pub struct PageRun {
 
 impl PageRun {
     /// Layout the page run.
-    pub fn layout(&self, ctx: &mut LayoutContext) -> Vec<Frame> {
+    pub fn layout(&self, ctx: &mut LayoutContext) -> Vec<Rc<Frame>> {
         // When one of the lengths is infinite the page fits its content along
         // that axis.
         let Size { width, height } = self.size;
@@ -97,7 +98,7 @@ impl Layout for AnyNode {
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
-    ) -> Vec<Constrained<Frame>> {
+    ) -> Vec<Constrained<Rc<Frame>>> {
         ctx.level += 1;
         let frames = ctx
             .cache
@@ -179,7 +180,7 @@ pub trait Layout {
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
-    ) -> Vec<Constrained<Frame>>;
+    ) -> Vec<Constrained<Rc<Frame>>>;
 }
 
 /// The context for layouting.
@@ -188,7 +189,7 @@ pub struct LayoutContext<'a> {
     pub loader: &'a mut dyn Loader,
     /// A cache for loaded fonts and artifacts from past layouting.
     pub cache: &'a mut Cache,
-    /// How deeply nested is the current layout tree position.
+    /// How deeply nested the current layout tree position is.
     pub level: usize,
 }
 
diff --git a/src/layout/pad.rs b/src/layout/pad.rs
index c212ec8a..9d432e79 100644
--- a/src/layout/pad.rs
+++ b/src/layout/pad.rs
@@ -14,21 +14,19 @@ impl Layout for PadNode {
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
-    ) -> Vec<Constrained<Frame>> {
+    ) -> Vec<Constrained<Rc<Frame>>> {
         let mut regions = regions.map(|size| size - self.padding.resolve(size).size());
 
         let mut frames = self.child.layout(ctx, &regions);
+
         for frame in &mut frames {
             let padded = solve(self.padding, frame.size);
             let padding = self.padding.resolve(padded);
             let origin = Point::new(padding.left, padding.top);
 
-            frame.item.size = padded;
-            frame.item.baseline += origin.y;
-
-            for (point, _) in &mut frame.item.elements {
-                *point += origin;
-            }
+            let mut new = Frame::new(padded, frame.baseline + origin.y);
+            let prev = std::mem::take(&mut frame.item);
+            new.push_frame(origin, prev);
 
             frame.constraints.mutate(padding.size() * -1.0);
 
@@ -40,8 +38,8 @@ impl Layout for PadNode {
             }
 
             regions.next();
+            *Rc::make_mut(&mut frame.item) = new;
         }
-
         frames
     }
 }
diff --git a/src/layout/par.rs b/src/layout/par.rs
index 814f88ed..2208f9ee 100644
--- a/src/layout/par.rs
+++ b/src/layout/par.rs
@@ -37,7 +37,7 @@ impl Layout for ParNode {
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
-    ) -> Vec<Constrained<Frame>> {
+    ) -> Vec<Constrained<Rc<Frame>>> {
         // Collect all text into one string used for BiDi analysis.
         let text = self.collect_text();
 
@@ -169,7 +169,7 @@ impl<'a> ParLayouter<'a> {
         self,
         ctx: &mut LayoutContext,
         regions: Regions,
-    ) -> Vec<Constrained<Frame>> {
+    ) -> Vec<Constrained<Rc<Frame>>> {
         let mut stack = LineStack::new(self.line_spacing, regions);
 
         // The current line attempt.
@@ -277,7 +277,7 @@ enum ParItem<'a> {
     /// A shaped text run with consistent direction.
     Text(ShapedText<'a>, Align),
     /// A layouted child node.
-    Frame(Frame, Align),
+    Frame(Rc<Frame>, Align),
 }
 
 impl ParItem<'_> {
@@ -306,7 +306,7 @@ struct LineStack<'a> {
     regions: Regions,
     size: Size,
     lines: Vec<LineLayout<'a>>,
-    finished: Vec<Constrained<Frame>>,
+    finished: Vec<Constrained<Rc<Frame>>>,
     constraints: Constraints,
 }
 
@@ -357,7 +357,7 @@ impl<'a> LineStack<'a> {
             }
 
             offset += frame.size.height + self.line_spacing;
-            output.push_frame(pos, frame);
+            output.merge_frame(pos, frame);
         }
 
         self.finished.push(output.constrain(self.constraints));
@@ -367,7 +367,7 @@ impl<'a> LineStack<'a> {
     }
 
     /// Finish the last region and return the built frames.
-    fn finish(mut self, ctx: &LayoutContext) -> Vec<Constrained<Frame>> {
+    fn finish(mut self, ctx: &LayoutContext) -> Vec<Constrained<Rc<Frame>>> {
         self.finish_region(ctx);
         self.finished
     }
@@ -504,7 +504,7 @@ impl<'a> LineLayout<'a> {
                 }
                 ParItem::Text(ref shaped, align) => {
                     ruler = ruler.max(align);
-                    shaped.build(ctx)
+                    Rc::new(shaped.build(ctx))
                 }
                 ParItem::Frame(ref frame, align) => {
                     ruler = ruler.max(align);
diff --git a/src/layout/stack.rs b/src/layout/stack.rs
index b45adcb2..2a0b2806 100644
--- a/src/layout/stack.rs
+++ b/src/layout/stack.rs
@@ -32,7 +32,7 @@ impl Layout for StackNode {
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
-    ) -> Vec<Constrained<Frame>> {
+    ) -> Vec<Constrained<Rc<Frame>>> {
         StackLayouter::new(self, regions.clone()).layout(ctx)
     }
 }
@@ -64,9 +64,9 @@ struct StackLayouter<'a> {
     constraints: Constraints,
     /// Offset, alignment and frame for all children that fit into the current
     /// region. The exact positions are not known yet.
-    frames: Vec<(Length, Gen<Align>, Frame)>,
+    frames: Vec<(Length, Gen<Align>, Rc<Frame>)>,
     /// Finished frames for previous regions.
-    finished: Vec<Constrained<Frame>>,
+    finished: Vec<Constrained<Rc<Frame>>>,
 }
 
 impl<'a> StackLayouter<'a> {
@@ -98,7 +98,7 @@ impl<'a> StackLayouter<'a> {
     }
 
     /// Layout all children.
-    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Constrained<Frame>> {
+    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Constrained<Rc<Frame>>> {
         for child in &self.stack.children {
             match *child {
                 StackChild::Spacing(amount) => self.space(amount),
@@ -133,7 +133,7 @@ impl<'a> StackLayouter<'a> {
 
     /// Push a frame into the current or next fitting region, finishing regions
     /// if necessary.
-    fn push_frame(&mut self, frame: Frame, aligns: Gen<Align>) {
+    fn push_frame(&mut self, frame: Rc<Frame>, aligns: Gen<Align>) {
         let size = frame.size.to_gen(self.main);
 
         // Don't allow `Start` after `End` in the same region.