Generate layout Nodes on demand in the rendering process

[ruifengx]

Note: After I finished writing all these, I realised it might be too complicated to have the idea actually implemented as-is in iced. But anyway it is just a rough idea, and I believe at least the motivating problem is worth some discussions.

---

Currently, a Node keeps all its children Nodes in a Vec. If, for instance (for a hypothetical Table widget), we have a long Column with a lot of children widgets (table rows), keeping all the children in memory is very inefficient.

Consider the following situation:

1. (in Widget::layout) Table measures the height of its children (the table rows), and generate the layout nodes;
2. (in Widget::draw) Table traverses the children Layout nodes, and draw only the children in the viewport;

Assuming all the children share the same size (which is often the case for tables; even if the assumption is not true, it is a reasonable approximation for optimisation), the layout nodes could be generated on the fly during the rendering process (i.e., in Widget::draw).

What if instead of a Vec<Node>, we store an iterator of Node (or more precisely, a function that returns an iterator, because it needs to repeatedly provide the same iterator to be traversed), and let the iterator generate the nodes on demand? Specifically, we replace children: Vec<Node> with the following:

pub trait NodeChildren {
    fn children(&self) -> Box<dyn Iterator<Item=Node> + ExactSizeIterator>;
    // fn children(&self) -> Box<dyn Iterator<Item=&Node> + ExactSizeIterator>;
    // fn children(&self) -> Box<dyn Iterator<Item=Cow<Node>> + ExactSizeIterator>;
}

#[derive(Debug, Clone, Default)]
pub struct Node {
    bounds: Rectangle,
    children: Box<dyn NodeChildren>,
    // children: Box<dyn Fn() -> Box<dyn Iterator<Item=Node>>>,
}

Original definition for Node (linked for reference):

iced/core/src/layout/node.rs

Lines 4 to 8 in b5f102c

	#[derive(Debug, Clone, Default)]
	pub struct Node {
	bounds: Rectangle,
	children: Vec<Node>,
	}

This is strictly more general than the current implementation: in the new strategy, we replace a vector xs with Box::new(VecChildren(xs)):

pub struct VecChildren(Vec<Node>);
impl NodeChildren {
    fn children(&self) -> Box<dyn Iterator<Item=Node> + ExactSizeIterator> {
        Box::new(self.0.iter().cloned())
    }
    // fn children(&self) -> Box<dyn Iterator<Item=&Node>> + ExactSizeIterator> {
    //     Box::new(self.0.iter())
    // }
    // fn children(&self) -> Box<dyn Iterator<Item=Cow<Node>>> + ExactSizeIterator> {
    //     Box::new(self.0.iter().map(Cow::Borrowed))
    // }
}

Using this approach, the layout logic and the rendering logic are still clearly separated, but the actual computation for the layout nodes are postponed to the rendering phase, and the layout nodes are discarded immediately after their use. The downside is the potential performance loss due to the use of trait objects.

Note: The Nodes generated on the fly are necessarily owned (therefore by-value); the Nodes from a Vec had better be borrowed instead of cloned (therefore by-reference). To unify them, we might need the version with Cow<Node>. From a different perspective, this dilemma could also be solved using a "lending iterator":

pub trait ChildSequence {
    fn next(&mut self) -> Option<&Node>;
}

pub struct IterSequence<I> {
    current: Option<Node>,
    iter: I,
}

impl<I> From<I> for IterSequence<I> {
    fn from(iter: I) -> Self { IterSequence { current: None, iter } }
}

impl<I: Iterator<Item=Node>> ChildSequence for IterSequence<I> {
    fn next(&mut self) -> Option<&Node> {
        self.current = self.iter.next();
        self.current.as_ref()
    }
}