Widget Identifiers

[dhardy]

The WidgetId type is currently a simple numeric identifier assigned to widgets in a depth-first search. It is widely used and should ideally have all of these properties:

• small, fixed-size type
• be robust against view / resizing adjustments (i.e. not a coordinate)
• allow O(1) tests of whether a widget is an ancestor of a given identifier (this could be achieved by giving widgets an identifier range, instead of just the last id in that range)
• allow O(log n) identification of which child is the ancestor of an id given n children (hard in the general case when children can have different numbers of descendants; guesses assuming equal numbers of descendants may be enough)
• allow widgets with dynamic content (e.g. List) to add/remove children without having to re-enumerate all widgets

Currently things are "fast enough" with a few thousand widgets on a decent machine (even a few hundred thousand in an optimised build, ignoring other issues like calculating size requirements and notifying all subscribed radio boxes) so this isn't a priority, but being able to scale well is a goal (e.g. for spreadsheets where each cell is a widget).

I have some additional notes offline, but no real solution.

[dhardy]

Another possible goal:

• allow widgets to be added or removed robustly during the configure step

Making the above robust implies:

1. it does not trigger a full regconfigure (which might cause the responsible widget to add/remove widgets again)
2. that new widgets get assigned IDs and configured

[dhardy]

As noted above, I have a few potential solutions:

Paths (e.g. [1u8, 3, 6, 2])

This has several issues:

• ideally each element of the path is small, but using a u8 or even u16 is quite restrictive
• it's not a fixed-size type except with external storage, e.g. SmallVec<[u8; 24]>

Sub-maps

Allow sub-maps allocated elsewhere (e.g. a resizable list places its children into a different ID space). Complex and it's not obvious how to identify an ancestor.

Use a range

(This appears the most viable, so I include additional details.)

Leaf widgets and single-child wrappers will always use a single ID; other parents store a range (first and last child identifier, optionally pushing the end-point back to allow spare IDs).

Configure happens recursively as now, except that widgets implementing configure_recurse may choose their own "last ID" based on their current children. Use some heuristic to select an end-point allowing a few children to be added, but without eating up the space of available IDs too fast (could be a problem when multiple expandable-parents are embedded inside each other). Tell children the maximum ID available so that it is more likely that a child can fit in existing gap when the child itself wants to allow spare IDs.

Some type of localised reconfigure is required, and when this fails we must either resort to a full reconfigure or implement ID remapping.

Notes:

• Any widget can be identified with a single identifier (number), but parents must store two (the range)
• Parents can identify whether a given identifier is a (potential) descendant in O(1)
• Finding "the" ID of the common parent of two arbitrary identifiers requires walking the widget tree (O(d) where d is max depth), but for partial updates affecting k arbitrary identifiers one can simply use the range encompassing these (O(k))

Open questions:

• Use 32-bit or 64-bit identifiers? Probably better to use 64-bit to be less sensitive to poor allocation heuristics.
• Store both ends of the range for all WidgetIds even though many widgets use only one? Or have different types for LeafId and ParentId?
• Which heuristic to use for over-allocation? Is it worth basing the result on any history? (This is similar to the re-allocation problem for vectors, but with different costs since over-allocation is free provided we don't exhaust the ID space and re-allocation may be more expensive.) Perhaps simply parents can divide all available IDs equally between children when configuring, but children use only what they need if they have fixed number, allowing the space to be divided between "dynamic" widgets.
• How exactly partial-reconfigure happens (when adding children from events).

---

Note: implementing a solution is low priority since this is an optimisation we don't necessarily need, but this does influence the design of other aspects of KAS (the assumption that we can have a fast test for "am I an ancestor of X", and how partial reconfigure/resize/redraw updates might work).

[dhardy]

#243 brings up an issue which I really should have spotted earlier: WidgetId identifies a widget, not a data item under a view such as ListView, thus when one of the "viewing widgets" is reassigned to a different data entry, external identifiers used e.g. for Tab focus will follow the reassigned widget, not the data entry. Fixing this requires that at least some uses of WidgetId instead use a data-identifier.

The best solution I can think of right now: use index-paths like above (e.g.TinyVec<[u8; 24]>), but supporting multi-byte values using the high bit(s) (something like how UTF-8 works):

• advantage: finding a widget by path is just a series of look-ups instead of the current logic for working out which child is represented
• disadvantage: identifiers are larger, may be behind an allocation, and may require extra processing

[dhardy]

This was mostly solved in #264 and #265. Remaining: support localised reconfigure.

[dhardy]

Local reconfigure was implemented in #276.