Introduce `keyed::Column` widget

8 files changed, 490 insertions, 11 deletions

diff --git a/core/src/widget/tree.rs b/core/src/widget/tree.rs
index 0af40c33..202cca9a 100644
--- a/core/src/widget/tree.rs
+++ b/core/src/widget/tree.rs
@@ -107,6 +107,88 @@ impl Tree {
     }
 }
 
+/// Reconciliates the `current_children` with the provided list of widgets using
+/// custom logic both for diffing and creating new widget state.
+///
+/// The algorithm will try to minimize the impact of diffing by querying the
+/// `maybe_changed` closure.
+pub fn diff_children_custom_with_search<T>(
+    current_children: &mut Vec<Tree>,
+    new_children: &[T],
+    diff: impl Fn(&mut Tree, &T),
+    maybe_changed: impl Fn(usize) -> bool,
+    new_state: impl Fn(&T) -> Tree,
+) {
+    if new_children.is_empty() {
+        current_children.clear();
+        return;
+    }
+
+    if current_children.is_empty() {
+        current_children.extend(new_children.iter().map(new_state));
+        return;
+    }
+
+    let first_maybe_changed = maybe_changed(0);
+    let last_maybe_changed = maybe_changed(current_children.len() - 1);
+
+    if current_children.len() > new_children.len() {
+        if !first_maybe_changed && last_maybe_changed {
+            current_children.truncate(new_children.len());
+        } else {
+            let difference_index = if first_maybe_changed {
+                0
+            } else {
+                (1..current_children.len())
+                    .find(|&i| maybe_changed(i))
+                    .unwrap_or(0)
+            };
+
+            let _ = current_children.splice(
+                difference_index
+                    ..difference_index
+                        + (current_children.len() - new_children.len()),
+                std::iter::empty(),
+            );
+        }
+    }
+
+    if current_children.len() < new_children.len() {
+        let first_maybe_changed = maybe_changed(0);
+        let last_maybe_changed = maybe_changed(current_children.len() - 1);
+
+        if !first_maybe_changed && last_maybe_changed {
+            current_children.extend(
+                new_children[current_children.len()..].iter().map(new_state),
+            );
+        } else {
+            let difference_index = if first_maybe_changed {
+                0
+            } else {
+                (1..current_children.len())
+                    .find(|&i| maybe_changed(i))
+                    .unwrap_or(0)
+            };
+
+            let _ = current_children.splice(
+                difference_index..difference_index,
+                new_children[difference_index
+                    ..difference_index
+                        + (new_children.len() - current_children.len())]
+                    .iter()
+                    .map(new_state),
+            );
+        }
+    }
+
+    // TODO: Merge loop with extend logic (?)
+    for (child_state, new) in
+        current_children.iter_mut().zip(new_children.iter())
+    {
+        diff(child_state, new);
+    }
+}
+
 /// The identifier of some widget state.
 #[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
 pub struct Tag(any::TypeId);
diff --git a/examples/todos/Cargo.toml b/examples/todos/Cargo.toml
index 7ad4d558..4a35cfe6 100644
--- a/examples/todos/Cargo.toml
+++ b/examples/todos/Cargo.toml
@@ -7,9 +7,11 @@ publish = false
 
 [dependencies]
 iced = { path = "../..", features = ["async-std", "debug"] }
+uuid = { version = "1.0", features = ["v4", "fast-rng", "serde"] }
 serde = { version = "1.0", features = ["derive"] }
 serde_json = "1.0"
-once_cell = "1.15"
+once_cell = "1.0"
+tracing-subscriber = "0.3"
 
 [target.'cfg(not(target_arch = "wasm32"))'.dependencies]
 async-std = "1.0"
diff --git a/examples/todos/src/main.rs b/examples/todos/src/main.rs
index 6ad7b4fb..1dd8a307 100644
--- a/examples/todos/src/main.rs
+++ b/examples/todos/src/main.rs
@@ -5,8 +5,8 @@ use iced::keyboard::{self, KeyCode, Modifiers};
 use iced::subscription;
 use iced::theme::{self, Theme};
 use iced::widget::{
-    self, button, checkbox, column, container, row, scrollable, text,
-    text_input, Text,
+    self, button, checkbox, column, container, keyed_column, row, scrollable,
+    text, text_input, Text,
 };
 use iced::window;
 use iced::{Application, Element};
@@ -14,10 +14,13 @@ use iced::{Color, Command, Length, Settings, Subscription};
 
 use once_cell::sync::Lazy;
 use serde::{Deserialize, Serialize};
+use uuid::Uuid;
 
 static INPUT_ID: Lazy<text_input::Id> = Lazy::new(text_input::Id::unique);
 
 pub fn main() -> iced::Result {
+    tracing_subscriber::fmt::init();
+
     Todos::run(Settings {
         window: window::Settings {
             size: (500, 800),
@@ -222,17 +225,19 @@ impl Application for Todos {
                     tasks.iter().filter(|task| filter.matches(task));
 
                 let tasks: Element<_> = if filtered_tasks.count() > 0 {
-                    column(
+                    keyed_column(
                         tasks
                             .iter()
                             .enumerate()
                             .filter(|(_, task)| filter.matches(task))
                             .map(|(i, task)| {
-                                task.view(i).map(move |message| {
-                                    Message::TaskMessage(i, message)
-                                })
-                            })
-                            .collect(),
+                                (
+                                    task.id,
+                                    task.view(i).map(move |message| {
+                                        Message::TaskMessage(i, message)
+                                    }),
+                                )
+                            }),
                     )
                     .spacing(10)
                     .into()
@@ -295,6 +300,8 @@ impl Application for Todos {
 
 #[derive(Debug, Clone, Serialize, Deserialize)]
 struct Task {
+    #[serde(default = "Uuid::new_v4")]
+    id: Uuid,
     description: String,
     completed: bool,
 
@@ -330,6 +337,7 @@ impl Task {
 
     fn new(description: String) -> Self {
         Task {
+            id: Uuid::new_v4(),
             description,
             completed: false,
             state: TaskState::Idle,
diff --git a/graphics/src/text/paragraph.rs b/graphics/src/text/paragraph.rs
index d99b8412..ee7c04c8 100644
--- a/graphics/src/text/paragraph.rs
+++ b/graphics/src/text/paragraph.rs
@@ -27,6 +27,8 @@ impl Paragraph {
     }
 
     pub fn with_text(text: Text<'_, Font>, font_system: &FontSystem) -> Self {
+        log::trace!("\nAllocating paragraph: {}", text.content);
+
         let mut font_system = font_system.write();
 
         let mut buffer = cosmic_text::Buffer::new(
diff --git a/widget/src/helpers.rs b/widget/src/helpers.rs
index 9c3c83a9..c885d724 100644
--- a/widget/src/helpers.rs
+++ b/widget/src/helpers.rs
@@ -6,6 +6,7 @@ use crate::container::{self, Container};
 use crate::core;
 use crate::core::widget::operation;
 use crate::core::{Element, Length, Pixels};
+use crate::keyed;
 use crate::overlay;
 use crate::pick_list::{self, PickList};
 use crate::progress_bar::{self, ProgressBar};
@@ -63,14 +64,22 @@ where
 }
 
 /// Creates a new [`Column`] with the given children.
-///
-/// [`Column`]: widget::Column
 pub fn column<Message, Renderer>(
     children: Vec<Element<'_, Message, Renderer>>,
 ) -> Column<'_, Message, Renderer> {
     Column::with_children(children)
 }
 
+/// Creates a new [`keyed::Column`] with the given children.
+pub fn keyed_column<'a, Key, Message, Renderer>(
+    children: impl IntoIterator<Item = (Key, Element<'a, Message, Renderer>)>,
+) -> keyed::Column<'a, Key, Message, Renderer>
+where
+    Key: Copy + PartialEq,
+{
+    keyed::Column::with_children(children)
+}
+
 /// Creates a new [`Row`] with the given children.
 ///
 /// [`Row`]: widget::Row
diff --git a/widget/src/keyed.rs b/widget/src/keyed.rs
new file mode 100644
index 00000000..55019535
--- /dev/null
+++ b/widget/src/keyed.rs
@@ -0,0 +1,55 @@
+//! Use widgets that can provide hints to ensure continuity.
+//!
+//! # What is continuity?
+//! Continuity is the feeling of persistence of state.
+//!
+//! In a graphical user interface, users expect widgets to have a
+//! certain degree of continuous state. For instance, a text input
+//! that is focused should stay focused even if the widget tree
+//! changes slightly.
+//!
+//! Continuity is tricky in `iced` and the Elm Architecture because
+//! the whole widget tree is rebuilt during every `view` call. This is
+//! very convenient from a developer perspective because you can build
+//! extremely dynamic interfaces without worrying about changing state.
+//!
+//! However, the tradeoff is that determining what changed becomes hard
+//! for `iced`. If you have a list of things, adding an element at the
+//! top may cause a loss of continuity on every element on the list!
+//!
+//! # How can we keep continuity?
+//! The good news is that user interfaces generally have a static widget
+//! structure. This structure can be relied on to ensure some degree of
+//! continuity. `iced` already does this.
+//!
+//! However, sometimes you have a certain part of your interface that is
+//! quite dynamic. For instance, a list of things where items may be added
+//! or removed at any place.
+//!
+//! There are different ways to mitigate this during the reconciliation
+//! stage, but they involve comparing trees at certain depths and
+//! backtracking... Quite computationally expensive.
+//!
+//! One approach that is cheaper consists in letting the user provide some hints
+//! about the identities of the different widgets so that they can be compared
+//! directly without going deeper.
+//!
+//! The widgets in this module will all ask for a "hint" of some sort. In order
+//! to help them keep continuity, you need to make sure the hint stays the same
+//! for the same items in your user interface between `view` calls.
+pub mod column;
+
+pub use column::Column;
+
+/// Creates a [`Column`] with the given children.
+///
+/// [`Column`]: widget::Column
+#[macro_export]
+macro_rules! keyed_column {
+    () => (
+        $crate::Column::new()
+    );
+    ($($x:expr),+ $(,)?) => (
+        $crate::keyed::Column::with_children(vec![$($crate::core::Element::from($x)),+])
+    );
+}
diff --git a/widget/src/keyed/column.rs b/widget/src/keyed/column.rs
new file mode 100644
index 00000000..19016679
--- /dev/null
+++ b/widget/src/keyed/column.rs
@@ -0,0 +1,320 @@
+//! Distribute content vertically.
+use crate::core::event::{self, Event};
+use crate::core::layout;
+use crate::core::mouse;
+use crate::core::overlay;
+use crate::core::renderer;
+use crate::core::widget::tree::{self, Tree};
+use crate::core::widget::Operation;
+use crate::core::{
+    Alignment, Clipboard, Element, Layout, Length, Padding, Pixels, Rectangle,
+    Shell, Widget,
+};
+
+/// A container that distributes its contents vertically.
+#[allow(missing_debug_implementations)]
+pub struct Column<'a, Key, Message, Renderer = crate::Renderer>
+where
+    Key: Copy + PartialEq,
+{
+    spacing: f32,
+    padding: Padding,
+    width: Length,
+    height: Length,
+    max_width: f32,
+    align_items: Alignment,
+    keys: Vec<Key>,
+    children: Vec<Element<'a, Message, Renderer>>,
+}
+
+impl<'a, Key, Message, Renderer> Column<'a, Key, Message, Renderer>
+where
+    Key: Copy + PartialEq,
+{
+    /// Creates an empty [`Column`].
+    pub fn new() -> Self {
+        Self::with_children(Vec::new())
+    }
+
+    /// Creates a [`Column`] with the given elements.
+    pub fn with_children(
+        children: impl IntoIterator<Item = (Key, Element<'a, Message, Renderer>)>,
+    ) -> Self {
+        let (keys, children) = children.into_iter().fold(
+            (Vec::new(), Vec::new()),
+            |(mut keys, mut children), (key, child)| {
+                keys.push(key);
+                children.push(child);
+
+                (keys, children)
+            },
+        );
+
+        Column {
+            spacing: 0.0,
+            padding: Padding::ZERO,
+            width: Length::Shrink,
+            height: Length::Shrink,
+            max_width: f32::INFINITY,
+            align_items: Alignment::Start,
+            keys,
+            children,
+        }
+    }
+
+    /// Sets the vertical spacing _between_ elements.
+    ///
+    /// Custom margins per element do not exist in iced. You should use this
+    /// method instead! While less flexible, it helps you keep spacing between
+    /// elements consistent.
+    pub fn spacing(mut self, amount: impl Into<Pixels>) -> Self {
+        self.spacing = amount.into().0;
+        self
+    }
+
+    /// Sets the [`Padding`] of the [`Column`].
+    pub fn padding<P: Into<Padding>>(mut self, padding: P) -> Self {
+        self.padding = padding.into();
+        self
+    }
+
+    /// Sets the width of the [`Column`].
+    pub fn width(mut self, width: impl Into<Length>) -> Self {
+        self.width = width.into();
+        self
+    }
+
+    /// Sets the height of the [`Column`].
+    pub fn height(mut self, height: impl Into<Length>) -> Self {
+        self.height = height.into();
+        self
+    }
+
+    /// Sets the maximum width of the [`Column`].
+    pub fn max_width(mut self, max_width: impl Into<Pixels>) -> Self {
+        self.max_width = max_width.into().0;
+        self
+    }
+
+    /// Sets the horizontal alignment of the contents of the [`Column`] .
+    pub fn align_items(mut self, align: Alignment) -> Self {
+        self.align_items = align;
+        self
+    }
+
+    /// Adds an element to the [`Column`].
+    pub fn push(
+        mut self,
+        key: Key,
+        child: impl Into<Element<'a, Message, Renderer>>,
+    ) -> Self {
+        self.keys.push(key);
+        self.children.push(child.into());
+        self
+    }
+}
+
+impl<'a, Key, Message, Renderer> Default for Column<'a, Key, Message, Renderer>
+where
+    Key: Copy + PartialEq,
+{
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+struct State<Key>
+where
+    Key: Copy + PartialEq,
+{
+    keys: Vec<Key>,
+}
+
+impl<'a, Key, Message, Renderer> Widget<Message, Renderer>
+    for Column<'a, Key, Message, Renderer>
+where
+    Renderer: crate::core::Renderer,
+    Key: Copy + PartialEq + 'static,
+{
+    fn tag(&self) -> tree::Tag {
+        tree::Tag::of::<State<Key>>()
+    }
+
+    fn state(&self) -> tree::State {
+        tree::State::new(State {
+            keys: self.keys.clone(),
+        })
+    }
+
+    fn children(&self) -> Vec<Tree> {
+        self.children.iter().map(Tree::new).collect()
+    }
+
+    fn diff(&self, tree: &mut Tree) {
+        let Tree {
+            state, children, ..
+        } = tree;
+
+        let state = state.downcast_mut::<State<Key>>();
+
+        tree::diff_children_custom_with_search(
+            children,
+            &self.children,
+            |tree, child| child.as_widget().diff(tree),
+            |index| {
+                self.keys.get(index).or_else(|| self.keys.last()).copied()
+                    != Some(state.keys[index])
+            },
+            |child| Tree::new(child.as_widget()),
+        );
+
+        if state.keys != self.keys {
+            state.keys = self.keys.clone();
+        }
+    }
+
+    fn width(&self) -> Length {
+        self.width
+    }
+
+    fn height(&self) -> Length {
+        self.height
+    }
+
+    fn layout(
+        &self,
+        tree: &mut Tree,
+        renderer: &Renderer,
+        limits: &layout::Limits,
+    ) -> layout::Node {
+        let limits = limits
+            .max_width(self.max_width)
+            .width(self.width)
+            .height(self.height);
+
+        layout::flex::resolve(
+            layout::flex::Axis::Vertical,
+            renderer,
+            &limits,
+            self.padding,
+            self.spacing,
+            self.align_items,
+            &self.children,
+            &mut tree.children,
+        )
+    }
+
+    fn operate(
+        &self,
+        tree: &mut Tree,
+        layout: Layout<'_>,
+        renderer: &Renderer,
+        operation: &mut dyn Operation<Message>,
+    ) {
+        operation.container(None, layout.bounds(), &mut |operation| {
+            self.children
+                .iter()
+                .zip(&mut tree.children)
+                .zip(layout.children())
+                .for_each(|((child, state), layout)| {
+                    child
+                        .as_widget()
+                        .operate(state, layout, renderer, operation);
+                })
+        });
+    }
+
+    fn on_event(
+        &mut self,
+        tree: &mut Tree,
+        event: Event,
+        layout: Layout<'_>,
+        cursor: mouse::Cursor,
+        renderer: &Renderer,
+        clipboard: &mut dyn Clipboard,
+        shell: &mut Shell<'_, Message>,
+        viewport: &Rectangle,
+    ) -> event::Status {
+        self.children
+            .iter_mut()
+            .zip(&mut tree.children)
+            .zip(layout.children())
+            .map(|((child, state), layout)| {
+                child.as_widget_mut().on_event(
+                    state,
+                    event.clone(),
+                    layout,
+                    cursor,
+                    renderer,
+                    clipboard,
+                    shell,
+                    viewport,
+                )
+            })
+            .fold(event::Status::Ignored, event::Status::merge)
+    }
+
+    fn mouse_interaction(
+        &self,
+        tree: &Tree,
+        layout: Layout<'_>,
+        cursor: mouse::Cursor,
+        viewport: &Rectangle,
+        renderer: &Renderer,
+    ) -> mouse::Interaction {
+        self.children
+            .iter()
+            .zip(&tree.children)
+            .zip(layout.children())
+            .map(|((child, state), layout)| {
+                child.as_widget().mouse_interaction(
+                    state, layout, cursor, viewport, renderer,
+                )
+            })
+            .max()
+            .unwrap_or_default()
+    }
+
+    fn draw(
+        &self,
+        tree: &Tree,
+        renderer: &mut Renderer,
+        theme: &Renderer::Theme,
+        style: &renderer::Style,
+        layout: Layout<'_>,
+        cursor: mouse::Cursor,
+        viewport: &Rectangle,
+    ) {
+        for ((child, state), layout) in self
+            .children
+            .iter()
+            .zip(&tree.children)
+            .zip(layout.children())
+        {
+            child
+                .as_widget()
+                .draw(state, renderer, theme, style, layout, cursor, viewport);
+        }
+    }
+
+    fn overlay<'b>(
+        &'b mut self,
+        tree: &'b mut Tree,
+        layout: Layout<'_>,
+        renderer: &Renderer,
+    ) -> Option<overlay::Element<'b, Message, Renderer>> {
+        overlay::from_children(&mut self.children, tree, layout, renderer)
+    }
+}
+
+impl<'a, Key, Message, Renderer> From<Column<'a, Key, Message, Renderer>>
+    for Element<'a, Message, Renderer>
+where
+    Key: Copy + PartialEq + 'static,
+    Message: 'a,
+    Renderer: crate::core::Renderer + 'a,
+{
+    fn from(column: Column<'a, Key, Message, Renderer>) -> Self {
+        Self::new(column)
+    }
+}
diff --git a/widget/src/lib.rs b/widget/src/lib.rs
index 316e8829..707fec04 100644
--- a/widget/src/lib.rs
+++ b/widget/src/lib.rs
@@ -29,6 +29,7 @@ pub mod button;
 pub mod checkbox;
 pub mod combo_box;
 pub mod container;
+pub mod keyed;
 pub mod overlay;
 pub mod pane_grid;
 pub mod pick_list;