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.