Implement explicit text caching in the widget state tree

8 files changed, 305 insertions, 152 deletions

diff --git a/core/src/element.rs b/core/src/element.rs
index d2c6358b..0d23a9e7 100644
--- a/core/src/element.rs
+++ b/core/src/element.rs
@@ -306,10 +306,11 @@ where
 
     fn layout(
         &self,
+        tree: &Tree,
         renderer: &Renderer,
         limits: &layout::Limits,
     ) -> layout::Node {
-        self.widget.layout(renderer, limits)
+        self.widget.layout(tree, renderer, limits)
     }
 
     fn operate(
@@ -491,10 +492,11 @@ where
 
     fn layout(
         &self,
+        tree: &Tree,
         renderer: &Renderer,
         limits: &layout::Limits,
     ) -> layout::Node {
-        self.element.widget.layout(renderer, limits)
+        self.element.widget.layout(tree, renderer, limits)
     }
 
     fn operate(
diff --git a/core/src/layout.rs b/core/src/layout.rs
index 04954fb9..50ccf1f4 100644
--- a/core/src/layout.rs
+++ b/core/src/layout.rs
@@ -7,7 +7,7 @@ pub mod flex;
 pub use limits::Limits;
 pub use node::Node;
 
-use crate::{Point, Rectangle, Vector};
+use crate::{Point, Rectangle, Size, Vector};
 
 /// The bounds of a [`Node`] and its children, using absolute coordinates.
 #[derive(Debug, Clone, Copy)]
@@ -63,3 +63,29 @@ impl<'a> Layout<'a> {
         })
     }
 }
+
+/// Produces a [`Node`] with two children nodes one right next to each other.
+pub fn next_to_each_other(
+    limits: &Limits,
+    spacing: f32,
+    left: impl FnOnce(&Limits) -> Node,
+    right: impl FnOnce(&Limits) -> Node,
+) -> Node {
+    let left_node = left(limits);
+    let left_size = left_node.size();
+
+    let right_limits = limits.shrink(Size::new(left_size.width + spacing, 0.0));
+
+    let mut right_node = right(&right_limits);
+    let right_size = right_node.size();
+
+    right_node.move_to(Point::new(left_size.width + spacing, 0.0));
+
+    Node::with_children(
+        Size::new(
+            left_size.width + spacing + right_size.width,
+            left_size.height.max(right_size.height),
+        ),
+        vec![left_node, right_node],
+    )
+}
diff --git a/core/src/layout/flex.rs b/core/src/layout/flex.rs
index 8b967849..86b1a45b 100644
--- a/core/src/layout/flex.rs
+++ b/core/src/layout/flex.rs
@@ -19,6 +19,7 @@
 use crate::Element;
 
 use crate::layout::{Limits, Node};
+use crate::widget;
 use crate::{Alignment, Padding, Point, Size};
 
 /// The main axis of a flex layout.
@@ -66,6 +67,7 @@ pub fn resolve<Message, Renderer>(
     spacing: f32,
     align_items: Alignment,
     items: &[Element<'_, Message, Renderer>],
+    trees: &[widget::Tree],
 ) -> Node
 where
     Renderer: crate::Renderer,
@@ -81,7 +83,7 @@ where
     let mut nodes: Vec<Node> = Vec::with_capacity(items.len());
     nodes.resize(items.len(), Node::default());
 
-    for (i, child) in items.iter().enumerate() {
+    for (i, (child, tree)) in items.iter().zip(trees).enumerate() {
         let fill_factor = match axis {
             Axis::Horizontal => child.as_widget().width(),
             Axis::Vertical => child.as_widget().height(),
@@ -94,7 +96,8 @@ where
             let child_limits =
                 Limits::new(Size::ZERO, Size::new(max_width, max_height));
 
-            let layout = child.as_widget().layout(renderer, &child_limits);
+            let layout =
+                child.as_widget().layout(tree, renderer, &child_limits);
             let size = layout.size();
 
             available -= axis.main(size);
@@ -108,7 +111,7 @@ where
 
     let remaining = available.max(0.0);
 
-    for (i, child) in items.iter().enumerate() {
+    for (i, (child, tree)) in items.iter().zip(trees).enumerate() {
         let fill_factor = match axis {
             Axis::Horizontal => child.as_widget().width(),
             Axis::Vertical => child.as_widget().height(),
@@ -133,7 +136,8 @@ where
                 Size::new(max_width, max_height),
             );
 
-            let layout = child.as_widget().layout(renderer, &child_limits);
+            let layout =
+                child.as_widget().layout(tree, renderer, &child_limits);
             cross = cross.max(axis.cross(layout.size()));
 
             nodes[i] = layout;
diff --git a/core/src/renderer.rs b/core/src/renderer.rs
index 7c73d2e4..1b327e56 100644
--- a/core/src/renderer.rs
+++ b/core/src/renderer.rs
@@ -5,26 +5,13 @@ mod null;
 #[cfg(debug_assertions)]
 pub use null::Null;
 
-use crate::layout;
-use crate::{Background, BorderRadius, Color, Element, Rectangle, Vector};
+use crate::{Background, BorderRadius, Color, Rectangle, Vector};
 
 /// A component that can be used by widgets to draw themselves on a screen.
 pub trait Renderer: Sized {
     /// The supported theme of the [`Renderer`].
     type Theme;
 
-    /// Lays out the elements of a user interface.
-    ///
-    /// You should override this if you need to perform any operations before or
-    /// after layouting. For instance, trimming the measurements cache.
-    fn layout<Message>(
-        &mut self,
-        element: &Element<'_, Message, Self>,
-        limits: &layout::Limits,
-    ) -> layout::Node {
-        element.as_widget().layout(self, limits)
-    }
-
     /// Draws the primitives recorded in the given closure in a new layer.
     ///
     /// The layer will clip its contents to the provided `bounds`.
diff --git a/core/src/renderer/null.rs b/core/src/renderer/null.rs
index 5d49699e..55d58a59 100644
--- a/core/src/renderer/null.rs
+++ b/core/src/renderer/null.rs
@@ -1,6 +1,7 @@
+use crate::alignment;
 use crate::renderer::{self, Renderer};
 use crate::text::{self, Text};
-use crate::{Background, Font, Point, Rectangle, Size, Vector};
+use crate::{Background, Color, Font, Pixels, Point, Rectangle, Size, Vector};
 
 use std::borrow::Cow;
 
@@ -41,6 +42,7 @@ impl Renderer for Null {
 
 impl text::Renderer for Null {
     type Font = Font;
+    type Paragraph = ();
 
     const ICON_FONT: Font = Font::DEFAULT;
     const CHECKMARK_ICON: char = '0';
@@ -50,37 +52,83 @@ impl text::Renderer for Null {
         Font::default()
     }
 
-    fn default_size(&self) -> f32 {
-        16.0
+    fn default_size(&self) -> Pixels {
+        Pixels(16.0)
     }
 
     fn load_font(&mut self, _font: Cow<'static, [u8]>) {}
 
-    fn measure(
-        &self,
-        _content: &str,
-        _size: f32,
-        _line_height: text::LineHeight,
-        _font: Font,
-        _bounds: Size,
-        _shaping: text::Shaping,
-    ) -> Size {
-        Size::new(0.0, 20.0)
+    fn create_paragraph(&self, _text: Text<'_, Self::Font>) -> Self::Paragraph {
     }
 
-    fn hit_test(
+    fn resize_paragraph(
         &self,
-        _contents: &str,
-        _size: f32,
-        _line_height: text::LineHeight,
-        _font: Self::Font,
-        _bounds: Size,
-        _shaping: text::Shaping,
-        _point: Point,
-        _nearest_only: bool,
-    ) -> Option<text::Hit> {
+        _paragraph: &mut Self::Paragraph,
+        _new_bounds: Size,
+    ) {
+    }
+
+    fn fill_paragraph(
+        &mut self,
+        _paragraph: &Self::Paragraph,
+        _position: Point,
+        _color: Color,
+    ) {
+    }
+
+    fn fill_text(
+        &mut self,
+        _paragraph: Text<'_, Self::Font>,
+        _position: Point,
+        _color: Color,
+    ) {
+    }
+}
+
+impl text::Paragraph for () {
+    type Font = Font;
+
+    fn content(&self) -> &str {
+        ""
+    }
+
+    fn text_size(&self) -> Pixels {
+        Pixels(16.0)
+    }
+
+    fn font(&self) -> Self::Font {
+        Font::default()
+    }
+
+    fn line_height(&self) -> text::LineHeight {
+        text::LineHeight::default()
+    }
+
+    fn shaping(&self) -> text::Shaping {
+        text::Shaping::default()
+    }
+
+    fn horizontal_alignment(&self) -> alignment::Horizontal {
+        alignment::Horizontal::Left
+    }
+
+    fn vertical_alignment(&self) -> alignment::Vertical {
+        alignment::Vertical::Top
+    }
+
+    fn grapheme_position(&self, _line: usize, _index: usize) -> Option<Point> {
         None
     }
 
-    fn fill_text(&mut self, _text: Text<'_, Self::Font>) {}
+    fn bounds(&self) -> Size {
+        Size::ZERO
+    }
+
+    fn min_bounds(&self) -> Size {
+        Size::ZERO
+    }
+
+    fn hit_test(&self, _point: Point) -> Option<text::Hit> {
+        None
+    }
 }
diff --git a/core/src/text.rs b/core/src/text.rs
index fc8aa20e..c59c683a 100644
--- a/core/src/text.rs
+++ b/core/src/text.rs
@@ -1,6 +1,6 @@
 //! Draw and interact with text.
 use crate::alignment;
-use crate::{Color, Pixels, Point, Rectangle, Size};
+use crate::{Color, Pixels, Point, Size};
 
 use std::borrow::Cow;
 use std::hash::{Hash, Hasher};
@@ -12,17 +12,14 @@ pub struct Text<'a, Font> {
     pub content: &'a str,
 
     /// The bounds of the paragraph.
-    pub bounds: Rectangle,
+    pub bounds: Size,
 
     /// The size of the [`Text`] in logical pixels.
-    pub size: f32,
+    pub size: Pixels,
 
     /// The line height of the [`Text`].
     pub line_height: LineHeight,
 
-    /// The color of the [`Text`].
-    pub color: Color,
-
     /// The font of the [`Text`].
     pub font: Font,
 
@@ -132,7 +129,10 @@ impl Hit {
 /// A renderer capable of measuring and drawing [`Text`].
 pub trait Renderer: crate::Renderer {
     /// The font type used.
-    type Font: Copy;
+    type Font: Copy + PartialEq;
+
+    /// The [`Paragraph`] of this [`Renderer`].
+    type Paragraph: Paragraph<Font = Self::Font> + 'static;
 
     /// The icon font of the backend.
     const ICON_FONT: Self::Font;
@@ -151,62 +151,107 @@ pub trait Renderer: crate::Renderer {
     fn default_font(&self) -> Self::Font;
 
     /// Returns the default size of [`Text`].
-    fn default_size(&self) -> f32;
+    fn default_size(&self) -> Pixels;
 
-    /// Measures the text in the given bounds and returns the minimum boundaries
-    /// that can fit the contents.
-    fn measure(
+    /// Loads a [`Self::Font`] from its bytes.
+    fn load_font(&mut self, font: Cow<'static, [u8]>);
+
+    /// Creates a new [`Paragraph`] laid out with the given [`Text`].
+    fn create_paragraph(&self, text: Text<'_, Self::Font>) -> Self::Paragraph;
+
+    /// Lays out the given [`Paragraph`] with some new boundaries.
+    fn resize_paragraph(
         &self,
-        content: &str,
-        size: f32,
-        line_height: LineHeight,
-        font: Self::Font,
-        bounds: Size,
-        shaping: Shaping,
-    ) -> Size;
-
-    /// Measures the width of the text as if it were laid out in a single line.
-    fn measure_width(
+        paragraph: &mut Self::Paragraph,
+        new_bounds: Size,
+    );
+
+    /// Updates a [`Paragraph`] to match the given [`Text`], if needed.
+    fn update_paragraph(
         &self,
-        content: &str,
-        size: f32,
-        font: Self::Font,
-        shaping: Shaping,
-    ) -> f32 {
-        let bounds = self.measure(
-            content,
-            size,
-            LineHeight::Absolute(Pixels(size)),
-            font,
-            Size::INFINITY,
-            shaping,
-        );
-
-        bounds.width
+        paragraph: &mut Self::Paragraph,
+        text: Text<'_, Self::Font>,
+    ) {
+        if paragraph.content() != text.content
+            || paragraph.text_size() != text.size
+            || paragraph.line_height().to_absolute(text.size)
+                != text.line_height.to_absolute(text.size)
+            || paragraph.font() != text.font
+            || paragraph.shaping() != text.shaping
+            || paragraph.horizontal_alignment() != text.horizontal_alignment
+            || paragraph.vertical_alignment() != text.vertical_alignment
+        {
+            *paragraph = self.create_paragraph(text);
+        } else if paragraph.bounds() != text.bounds {
+            self.resize_paragraph(paragraph, text.bounds);
+        }
     }
 
-    /// Tests whether the provided point is within the boundaries of text
-    /// laid out with the given parameters, returning information about
-    /// the nearest character.
-    ///
-    /// If `nearest_only` is true, the hit test does not consider whether the
-    /// the point is interior to any glyph bounds, returning only the character
-    /// with the nearest centeroid.
-    fn hit_test(
-        &self,
-        contents: &str,
-        size: f32,
-        line_height: LineHeight,
-        font: Self::Font,
-        bounds: Size,
-        shaping: Shaping,
-        point: Point,
-        nearest_only: bool,
-    ) -> Option<Hit>;
+    /// Draws the given [`Paragraph`] at the given position and with the given
+    /// [`Color`].
+    fn fill_paragraph(
+        &mut self,
+        text: &Self::Paragraph,
+        position: Point,
+        color: Color,
+    );
+
+    /// Draws the given [`Text`] at the given position and with the given
+    /// [`Color`].
+    fn fill_text(
+        &mut self,
+        text: Text<'_, Self::Font>,
+        position: Point,
+        color: Color,
+    );
+}
+/// A text paragraph.
+pub trait Paragraph: Default {
+    /// The font of this [`Paragraph`].
+    type Font;
 
-    /// Loads a [`Self::Font`] from its bytes.
-    fn load_font(&mut self, font: Cow<'static, [u8]>);
+    /// Returns the content of the [`Paragraph`].
+    fn content(&self) -> &str;
 
-    /// Draws the given [`Text`].
-    fn fill_text(&mut self, text: Text<'_, Self::Font>);
+    /// Returns the text size of the [`Paragraph`].
+    fn text_size(&self) -> Pixels;
+
+    /// Returns the [`LineHeight`] of the [`Paragraph`].
+    fn line_height(&self) -> LineHeight;
+
+    /// Returns the [`Font`] of the [`Paragraph`].
+    fn font(&self) -> Self::Font;
+
+    /// Returns the [`Shaping`] strategy of the [`Paragraph`].
+    fn shaping(&self) -> Shaping;
+
+    /// Returns the horizontal alignment of the [`Paragraph`].
+    fn horizontal_alignment(&self) -> alignment::Horizontal;
+
+    /// Returns the vertical alignment of the [`Paragraph`].
+    fn vertical_alignment(&self) -> alignment::Vertical;
+
+    /// Returns the boundaries of the [`Paragraph`].
+    fn bounds(&self) -> Size;
+
+    /// Returns the minimum boundaries that can fit the contents of the
+    /// [`Paragraph`].
+    fn min_bounds(&self) -> Size;
+
+    /// Tests whether the provided point is within the boundaries of the
+    /// [`Paragraph`], returning information about the nearest character.
+    fn hit_test(&self, point: Point) -> Option<Hit>;
+
+    /// Returns the distance to the given grapheme index in the [`Paragraph`].
+    fn grapheme_position(&self, line: usize, index: usize) -> Option<Point>;
+
+    /// Returns the minimum width that can fit the contents of the [`Paragraph`].
+    fn min_width(&self) -> f32 {
+        self.min_bounds().width
+    }
+
+    /// Returns the minimum height that can fit the contents of the [`Paragraph`].
+    fn min_height(&self) -> f32 {
+        self.min_bounds().height
+    }
 }
diff --git a/core/src/widget.rs b/core/src/widget.rs
index d6a99208..70328ff7 100644
--- a/core/src/widget.rs
+++ b/core/src/widget.rs
@@ -55,6 +55,7 @@ where
     /// user interface.
     fn layout(
         &self,
+        tree: &Tree,
         renderer: &Renderer,
         limits: &layout::Limits,
     ) -> layout::Node;
@@ -62,7 +63,7 @@ where
     /// Draws the [`Widget`] using the associated `Renderer`.
     fn draw(
         &self,
-        state: &Tree,
+        tree: &Tree,
         renderer: &mut Renderer,
         theme: &Renderer::Theme,
         style: &renderer::Style,
diff --git a/core/src/widget/text.rs b/core/src/widget/text.rs
index 79df2b02..0405537b 100644
--- a/core/src/widget/text.rs
+++ b/core/src/widget/text.rs
@@ -3,11 +3,12 @@ use crate::alignment;
 use crate::layout;
 use crate::mouse;
 use crate::renderer;
-use crate::text;
-use crate::widget::Tree;
-use crate::{Color, Element, Layout, Length, Pixels, Rectangle, Widget};
+use crate::text::{self, Paragraph as _};
+use crate::widget::tree::{self, Tree};
+use crate::{Color, Element, Layout, Length, Pixels, Point, Rectangle, Widget};
 
 use std::borrow::Cow;
+use std::cell::RefCell;
 
 pub use text::{LineHeight, Shaping};
 
@@ -19,7 +20,7 @@ where
     Renderer::Theme: StyleSheet,
 {
     content: Cow<'a, str>,
-    size: Option<f32>,
+    size: Option<Pixels>,
     line_height: LineHeight,
     width: Length,
     height: Length,
@@ -53,7 +54,7 @@ where
 
     /// Sets the size of the [`Text`].
     pub fn size(mut self, size: impl Into<Pixels>) -> Self {
-        self.size = Some(size.into().0);
+        self.size = Some(size.into());
         self
     }
 
@@ -117,11 +118,23 @@ where
     }
 }
 
+/// The internal state of a [`Text`] widget.
+#[derive(Debug, Default)]
+pub struct State<T>(RefCell<T>);
+
 impl<'a, Message, Renderer> Widget<Message, Renderer> for Text<'a, Renderer>
 where
     Renderer: text::Renderer,
     Renderer::Theme: StyleSheet,
 {
+    fn tag(&self) -> tree::Tag {
+        tree::Tag::of::<State<Renderer::Paragraph>>()
+    }
+
+    fn state(&self) -> tree::State {
+        tree::State::new(State(RefCell::new(Renderer::Paragraph::default())))
+    }
+
     fn width(&self) -> Length {
         self.width
     }
@@ -132,30 +145,29 @@ where
 
     fn layout(
         &self,
+        tree: &Tree,
         renderer: &Renderer,
         limits: &layout::Limits,
     ) -> layout::Node {
-        let limits = limits.width(self.width).height(self.height);
-
-        let size = self.size.unwrap_or_else(|| renderer.default_size());
-
-        let bounds = renderer.measure(
+        layout(
+            tree.state.downcast_ref::<State<Renderer::Paragraph>>(),
+            renderer,
+            limits,
+            self.width,
+            self.height,
             &self.content,
-            size,
             self.line_height,
-            self.font.unwrap_or_else(|| renderer.default_font()),
-            limits.max(),
+            self.size,
+            self.font,
+            self.horizontal_alignment,
+            self.vertical_alignment,
             self.shaping,
-        );
-
-        let size = limits.resolve(bounds);
-
-        layout::Node::new(size)
+        )
     }
 
     fn draw(
         &self,
-        _state: &Tree,
+        tree: &Tree,
         renderer: &mut Renderer,
         theme: &Renderer::Theme,
         style: &renderer::Style,
@@ -163,22 +175,63 @@ where
         _cursor_position: mouse::Cursor,
         _viewport: &Rectangle,
     ) {
+        let state = tree.state.downcast_ref::<State<Renderer::Paragraph>>();
+
         draw(
             renderer,
             style,
             layout,
-            &self.content,
-            self.size,
-            self.line_height,
-            self.font,
+            state,
             theme.appearance(self.style.clone()),
-            self.horizontal_alignment,
-            self.vertical_alignment,
-            self.shaping,
         );
     }
 }
 
+/// Produces the [`layout::Node`] of a [`Text`] widget.
+pub fn layout<Renderer>(
+    state: &State<Renderer::Paragraph>,
+    renderer: &Renderer,
+    limits: &layout::Limits,
+    width: Length,
+    height: Length,
+    content: &str,
+    line_height: LineHeight,
+    size: Option<Pixels>,
+    font: Option<Renderer::Font>,
+    horizontal_alignment: alignment::Horizontal,
+    vertical_alignment: alignment::Vertical,
+    shaping: Shaping,
+) -> layout::Node
+where
+    Renderer: text::Renderer,
+{
+    let limits = limits.width(width).height(height);
+    let bounds = limits.max();
+
+    let size = size.unwrap_or_else(|| renderer.default_size());
+    let font = font.unwrap_or_else(|| renderer.default_font());
+
+    let mut paragraph = state.0.borrow_mut();
+
+    renderer.update_paragraph(
+        &mut paragraph,
+        text::Text {
+            content,
+            bounds,
+            size,
+            line_height,
+            font,
+            shaping,
+            horizontal_alignment,
+            vertical_alignment,
+        },
+    );
+
+    let size = limits.resolve(paragraph.min_bounds());
+
+    layout::Node::new(size)
+}
+
 /// Draws text using the same logic as the [`Text`] widget.
 ///
 /// Specifically:
@@ -193,44 +246,31 @@ pub fn draw<Renderer>(
     renderer: &mut Renderer,
     style: &renderer::Style,
     layout: Layout<'_>,
-    content: &str,
-    size: Option<f32>,
-    line_height: LineHeight,
-    font: Option<Renderer::Font>,
+    state: &State<Renderer::Paragraph>,
     appearance: Appearance,
-    horizontal_alignment: alignment::Horizontal,
-    vertical_alignment: alignment::Vertical,
-    shaping: Shaping,
 ) where
     Renderer: text::Renderer,
 {
+    let paragraph = state.0.borrow();
     let bounds = layout.bounds();
 
-    let x = match horizontal_alignment {
+    let x = match paragraph.horizontal_alignment() {
         alignment::Horizontal::Left => bounds.x,
         alignment::Horizontal::Center => bounds.center_x(),
         alignment::Horizontal::Right => bounds.x + bounds.width,
     };
 
-    let y = match vertical_alignment {
+    let y = match paragraph.vertical_alignment() {
         alignment::Vertical::Top => bounds.y,
         alignment::Vertical::Center => bounds.center_y(),
         alignment::Vertical::Bottom => bounds.y + bounds.height,
     };
 
-    let size = size.unwrap_or_else(|| renderer.default_size());
-
-    renderer.fill_text(crate::Text {
-        content,
-        size,
-        line_height,
-        bounds: Rectangle { x, y, ..bounds },
-        color: appearance.color.unwrap_or(style.text_color),
-        font: font.unwrap_or_else(|| renderer.default_font()),
-        horizontal_alignment,
-        vertical_alignment,
-        shaping,
-    });
+    renderer.fill_paragraph(
+        &paragraph,
+        Point::new(x, y),
+        appearance.color.unwrap_or(style.text_color),
+    );
 }
 
 impl<'a, Message, Renderer> From<Text<'a, Renderer>>