Next steps for tree structure tracking

[raphlinus]

This is an outline for how I think we should track tree structure in the widget tree.

A number of operations on the view side can change the widget tree structure. The widget tree doesn't change structure by itself, but only in response to mutations from the view side. Those operations are, roughly: an AnyView changing view type, and Option<V> switching between None and Some, and a variable length implementor of ViewSequence (such as Vec) changing length. The goal is for those view operations to mark the tree precisely, then for a traversal of the tree to update accessibility and internal invariants.

Tree marking

The desired result of tree marking is as follows: every container that has had its list of children changed is marked with PodFlags::TREE_CHANGED, and all of its ancestors are marked with the corresponding upward flag; we could create a new one, or use UPDATE for this purpose.

Any ViewSequence implementation that changes its count should signal ChangeFlags::TREE, as should AnyView on type change. The tree marking is currently done by the rebuild method in the blanket impl of ViewSequence for V: View, though this plumbing is in a state of flux. We should not propagate TREE_CHANGED or TREE upward (it is currently in UPWARD_FLAGS) but should instead propagate the corresponding upward flag.

Accessibility

A container generally needs to update its accessibility node in several cases: its geometry changed or its children changed. Probably the best way to do this is to have the framework set REQUEST_ACCESSIBILITY (and the corresponding upward flag) in both these cases, so widgets don't have to have this logic themselves.

Open question: should that be done during tree marking, or perhaps in a separate traversal? The update traversal would be a natural place, but it's not obvious we're going to keep that.

WidgetAdded

Druid sends a WidgetAdded lifecycle event to widgets newly added to the tree. This is propagated from several different traversals. I think it's likely we'll want to send such a lifecycle event also (though I'm not 100% sure it's still needed). We need to figure out which traversal it is. Druid uses the presence of the data field; we'll either need a flag in PodFlags indicating whether the widget has been initialized, or make use of structure tracking.

Druid also adds children to the Bloom filter at the same time. The way Bloom filters work, widgets can't be removed (I believe this is a bug in the existing xilem code, but haven't validated it carefully).

Structure tracking

One thing Druid does not do, that I think we should, is track the precise parent/child tree structure in the framework. I propose we have two hash tables, one from child widget ids to parent, and another from parent widget id to a Vec of child widget ids. This would be accessible from most contexts, and mutable from the context that propagates tree changes (in my mind, this is most naturally the update context, but my mind can be changed).

Generally it is the responsibility of container widgets to call a set_children() method on the context when the children have changed (using essentially the same logic as for accessibility), but it's possible we'll also want to have delta methods such as add_child or remove_child.

This could also be the locus from which WidgetAdded is generated.

Structure tracking would obviate the need for Bloom filters, and those should go away. For example, when propagating an accessibility event, the widget id provided in that event can be expanded to an id path using that structure info (basically following the path through the parent chain up to the root), and used to dispatch precisely.

I haven't analyzed the focus chain logic closely, but I think a lot of that could be downstream of precisely tracked structure, rather than relying on the existing children_changed / register_child / register_for_focus mechanism. I think we're already paying much of the cost in both runtime and code complexity for doing this tracking, just not getting the full benefit.

[raphlinus]

For reference, there's code to track tree structure in the lasagna branch of Druid. The actual data structure can likely be adapted from that.

[xarvic]

should that be done during tree marking, or perhaps in a separate traversal?

I think this should happen during tree marking. The Pod could also set ACCESSIBILITY if ChangeFlags contains TREE_CHANGED.

Druid sends a WidgetAdded lifecycle event to widgets newly added to the tree. This is propagated from several different traversals. I think it's likely we'll want to send such a lifecycle event also (though I'm not 100% sure it's still needed). We need to figure out which traversal it is. Druid uses the presence of the data field; we'll either need a flag in PodFlags indicating whether the widget has been initialized, or make use of structure tracking.

I guess we could send the TREE_CHANGED event also to all newly added widgets.

The way Bloom filters work, widgets can't be removed (I believe this is a bug in the existing xilem code, but haven't validated it carefully).

I think this should work currently. The Pod clears the BloomFliter before passing the TREE_CHANGED event to its children.

[raphlinus]

I think this should work currently. The Pod clears the BloomFliter before passing the TREE_CHANGED event to its children.

Ah yes. I went over this more carefully, and I see that it's quite fine. In fact, the code is in pretty good shape. The only things that really needs improvement is that all ancestors of a container with TREE_CHANGED will also have their accessibility nodes re-generated (and these are of course exactly the ones that need their Bloom filters re-computed). That's not terrible in the grand scheme of things, but I think can be improved.

So at this point, I prefer doing finer grained tracking as proposed here, but I don't think it's absolutely required, and not doing it (or planning to do it later) would be less of a diff against the Druid code.

[Philipp-M]

@raphlinus Can you please clarify what you mean with the following (as I'm currently investigating the whole topic a little bit):

We should not propagate TREE_CHANGED or TREE upward (it is currently in UPWARD_FLAGS) but should instead propagate the corresponding upward flag.

[raphlinus]

For sure. The specific goal I'm addressing is to distinguish the cases where the vector of a node's immediate children have changed, as opposed to the case where the tree structure has changed of any of the descendants. The latter is needed so we can reach all changes in a recursive traversal, but (I think) there is valuable work to be saved by not recalculating anything based on the immediate children vector in that case.

The general pattern to achieve this is to have two separate flags, and only one of them in the UPWARD_FLAGS mask. The REQUESTED_ACCESSIBILITY and DESCENDANT_REQUESTED_ACCESSIBILITY flags show the pattern, where the latter is in UPWARD_FLAGS but the former is not.