[Architecture] Support specifying a key for each widget to help Reconciler understand intent from update to update

[twop]

DO you have a code snippet in mind that illustrates the idea? I'm curious what do you have in mind for this :)

[TimLariviere]

Like pretty much all other frameworks (React, SwiftUI, Flutter?), we have the concept of key at the widget level. This allows the diffing algorithm to match 2 widgets between 2 updates that are the same in the developer's mind.

StackLayout([
    if model.Toggle then
        Button("Hello", ClickedHello)

    Button("World", ClickedWorld)
])

In this example, if we toggle the model, the Reconciler will think we added (or removed) a button at the end of the list where in fact we added it at the start of the list.

In iOS, this also leads to an issue where an animation plays every time the text of a button is changed. In this example, it shouldn't because we're not changing the text of the 1st button, we're adding or removing the button itself.

In v1, we went the same way than React.

StackLayout([
    if model.Toggle then
        Button("Hello", ClickedHello)

    Button("World", ClickedWorld)
        .key("WorldButton")
])

Now the Reconciler can first try to match same key widgets before comparing the index. That way, it will find that the 1st Button has been added/removed instead of 1st button name changed and added/removed 2nd button.

See more info in https://fsprojects.github.io/Fabulous/Fabulous.XamarinForms/view-a-performance.html

[TimLariviere]

This is also crucial for virtualized list I believe

[twop]

Right, I got myself confused with terms.

I think one of the ways to do that is to incorporate a small numeric key into the Widget. e.g.

type Widget = {
  WidgetKey: u16
  Key: u16 // <--- fixed size, easy to compare
}

I think most of the time we can get away with just an index (like in virtual list example), at worst were can hash a string.

I'm concerned if we declare it like so:

type Widget = {
  WidgetKey: u16
  Key: obj // <--- untyped
}

Then we don't know can we check just a reference (if key is a ref type) or we need to unbox it.

So my ideal (from perf point of view) is to have Key be u16(or int32/uint32) and then we can efficiently reconcile children without chasing pointers.

@TimLariviere do you think it is reasonable to restrict Key to a numeric value? we can also provide a convenience method for strings in the future.

[TimLariviere]

Not as efficient, but what would it mean to make it u16 voption instead?

I guess we can go with numeric for now, the string was mostly for conveniency.

But requiring the key all the time (with key: u16) would be very inconvenient for the developers. The only moment it should be mandatory is for list like SwiftUI does it (and React also recommends it).

It can also be useful to set it outside lists to help the Reconciler, but most of the time it won't be necessary.

Edit: Or using key = 0 means no key?

[twop]

Edit: Or using key = 0 means no key?

Right, sorry I should have elaborated on that. Yes, either 0 or uint.max can represent no value.

[twop]

BTW to expand on this a bit further.

I think we want to reserve some space in WidgetKey for some internal needs. Like so

// assuming u16
k, k, .... k(12), r, r, r, r

So the actual WidgetKey bits are represented as 12 bits ("k") and the last 4 bits are reserved ("r").

Then when adding a Key attribute will also set a flag Keyed that will be stored in the last 4 bits. Then Key available to the user will not need any special cases like key = 0 or key = uint.max.

Note that this approach can also be applied to traversing MapMsg tree hierarchy. E.g. we can set a flag when a widget has MapMsg attribute. I don't think it is worth it (at least not yet). But I do like the idea of reserving some space at the end of WidgetKey

[twop]

@TimLariviere I can take that one next, it might be related to virtualized collections but still makes sense in a Stack-like things.

Thoughts?

[TimLariviere]

@twop In the end, I implemented virtualized collection without needing diffing so keys are not necessary. But it would definitely be improving performance in layout controls

[TimLariviere]

Some thoughts about key implementation: we can go the same way than Elm, given we follow most of their patterns (lazy, map, no dispatch, etc.)

View.keyed "the-key" (
    Label("Hello")
)

This is the implementation of keyed nodes diffing of Elm: https://github.com/elm/virtual-dom/blob/5a5bcf48720bc7d53461b3cd42a9f19f119c5503/src/Elm/Kernel/VirtualDom.js#L980

For information, this is the diffing function for non-virtualised collections: https://github.com/TimLariviere/Fabulous-new/blob/main/src/Fabulous/WidgetDiff.fs#L487-L525