[RFC] Thoughts on a persistent widget tree

[twitchyliquid64]

This issue attempts to condense discussions (on the zulip chat) over the last week into a single set of requirements, and a proposal for implementing a widget tree.

For context, it seems that a persistent (keeps state across layout/update/draw cycles) widget tree is necessary or ideal to implement a number of core features: animations, incremental draw/layout, retained-mode, and accessibility integration.

Requirements

• Motion (every frame) animations: Widgets need to be able to indicate that they need to be drawn every frame (ie: something fading in). Ideally, draw() would only be called on the widgets which need it: This will help us scale to large numbers of widgets.
• Periodic (scheduled) animations: Widgets need to be able to schedule periodic updates at roughly some moment in the future (ie: blinking cursor). See Animations #31 for more details on both of these.
• Retained-mode primitives: For each widget, keep track of the display list, and whether the display list needs to be re-computed. This information can be used to cull the number of invocations to draw() on the widget, and in the future keep objects in GPU memory live.
• Accessibility: We need a stable concept of widget identity (to communicate/key with an external, platform-specific API), children / parent widgets, and the ability to associate additional data with a widget for accessibility reasons (ie: A custom widget could markup logically-related widgets).
• Tab/keyboard selection: The widget tree needs to keep track of sequential widgets so tab can advance through widgets.

Proposal

I'll finish up a proper proposal tomorrow as its almost midnight. But this is what I have in mind so far:

The 'root' of a widget tree is a UI struct:

pub struct UI<'a> {
  root: Node<'a>,
  timers: Vec<Timer>, // sorted by soonest
}

And Node is a DOM-style doubly-linked tree of widgets (parent / next child / prev child / next sibling / prev sibling):

type Node<'a> = rctree::Node<Widget<'a>>;

(See rctree for more information on this tree scheme - such a well-connected structure seems ideal given the kinds of mutations and iterations we need to support.)

A Widget contains all the persistent state represented by a widget in the tree:

struct Widget<'a> {
  widget: Element<'a>,
  display_list: Option<Vec<Primitive>>,

  needs_draw: bool,
  children_need_draw: bool,

  needs_animation_tick: bool,
  child_needs_animation_tick: bool,

  needs_layout: bool, // also set if any children need layout
  layout: Option<Rectangle>,
}

Stable widget identity

The existing API (where everything gets wired into the window through a simple view() method and a few simple tidbits) is awesome, we should try and keep this as much as possible. @hecrj mentioned the #![track_caller] macro, which is a new stable trait that would give us an idea of call location, and I like the idea of using that.

Concretely, we would extent the Widget trait that all the widgets implement to also have a fn widget_key() -> u64. We would expect implementations to use #![track_caller] on their public new() methods, combined with the type, to compute this key.

We will also need a way to mutate this key with user-provided data (for instance if a number of Label widgets were created by an iterator, their call sites would be the same, hence there needs to be some wrapper to augment the key with something derived from iteration). I imagine a wrapper type will work well here.

We would also need a new method for a widget to indicate its children.

Changes to existing Widget methods (draw(), layout(), update() etc)

1. layout() needs to be changed so that instead of returning a Layout::Node, it composes layout information into the widget tree.
2. draw() semantics needs to be changed to only return Vec<Primitive> for the current Widget and not its children.
3. update() gets a new parameter which allows the widget to setup state in the widget tree. Specifically, setting the needs_draw, needs_layout, or animations flags/timers. I imagine this parameter will be some kind of context object, like how druid does it.

Reconciliation

I think it's sufficient to use the widget_key() to detect if a widget in the tree has mutated and update it accordingly. Basically, the approach outlined by raphlinus. Lets start with something - we can refine the heuristics later.

Event cycle

As a consequence of the above, the UI cycle now becomes:

1. tree update - The view is walked and compared against the current tree using their keys. Any changes result in a corresponding change in the widget tree.
2. updates - Event updates/messages are drained and delievered to widgets.
3. layout - Any new widget nodes, or widgets which have indicated needs_layout are laid out (and their children).
4. draw - Any new widget nodes, or widgets which have invalidated their display lists via needs_draw have their display lists regenerated. These display lists are iterated in sibling order and flushed to the graphics backends.