Regarding comments from the original pull request:

This now has me wondering: Don't we need to do this for all keys, not just globalkeys? If a keyed widget changes slots, it should be matched with the element from the previous slot it was in?

The documentation seems to suggest that should be the case:

/// A key that is not a [GlobalKey].
///
/// Keys must be unique amongst the [Element]s with the same parent. By
/// contrast, [GlobalKey]s must be unique across the entire app.

But I feel it to an extent overlaps the idea of the children being "slotted"

I was under the impression that to be able to use a local key the children have to be somewhat homogeneous, like in a list view or a column, but that doesn't seem to be true according to the documentation.

Replaced GlobalKey with Key.

nit: throw in an assert that slot != oldSlot?

I dislike that we call childForSlot twice for unkeyed widgets. While the API doesn't make any promises how often this gets called, it my be expensive to construct the widget for a slot, so we should avoid this duplication...

Caching would be one option. We may also be able to do this in one pass as long as we don't match existing keyed widget with new unkeyed ones in case the keyed ones move to a new slot further down the line...

as long as we don't match existing keyed widget with new unkeyed ones

There's nothing that prevents this I think?

Also I think the type parameter S should extend Object?

Also I think the type parameter S should extend Object?

Why?

Regarding the one-pass, I was thinking we could do something like this (pseudo-code):

for (final S slot in slottedMultiChildRenderObjectWidgetMixin.slots) {
  final Widget? widget = slottedMultiChildRenderObjectWidgetMixin.childForSlot(slot);
  if (widget.key != null) {
    var oldChild = oldKeyToElement.remove(widget.key);
    if (oldChild == null) {
      oldChild = _slotToChild[slot].widget.key != null : _slotToChild[slot] : null;
    } else if (oldChild == _slotToChild[oldChild.slot]) {
       _slotToChild.remove(oldChild.slot);
    }
    var newChild = updateChild(oldChild, widget, slot);
    _slotToChild[slot] = newChild;
  } else {
   var oldChild = _slotToChild[slot].widget.key == null ? _slotToChild[slot] : null;
   var newChild = updateChild(oldChild, widget, slot);
   _slotToChild[slot] = newChild;
  }
}
// TODO: match the remaining children in oldKeyToElement to null with `updateChild`.

I am sure I messed up some details in that code, but something like that?

Why?

With that Key to S map I'm making the assumption that S cannot be null (https://master-api.flutter.dev/flutter/dart-core/Map/operator_get.html) so if people use null as a slot it could mess up the key to slot lookup. I can use containsKey but it will be a bit hard to read.

one-pass

Ahh I see if oldWidget.key != null and newWidget.key == null Widget.canUpdate will return false and we'll inflate a new element anyways. But if that happens and the old keyed Elemenent doesn't end up getting updated by a new widget we'll have to call deactivate on it manually, so we kinda need a new collection to do the bookkeeping anyway?

so if people use null as a slot it could mess up the key to slot lookup.

Good point. In theory, null is a valid slot value, which I think the current implementation fully supports. However, if changing this isn't breaking anything (and it really simplifies the implementation a lot - which I am not fully convinced yet) I would be ok with changing this and documenting that limitation.

But if that happens and the old keyed Element doesn't end up getting updated by a new widget we'll have to call deactivate on it manually, so we kinda need a new collection to do the bookkeeping anyway?

Not sure I understand. If we pass an Element to updateChild it will either get re-used or properly deactivated.

Oh, but I think I missed a case in my code above (maybe that's the one you meant): When a keyed child moves into a slot previously occupied by an unkeyed child, we need to deactivate that child by calling updateChild(unkeyedChild, null, slot) for it before updating the slot of the keyed child. But I think we can just do that right before the first var newChild = updateChild(oldChild, widget, slot); occurence in the code above?

Updated. Also tried to avoid using S as map value type.

nit: assert that widget has a key?

inlined the method.

This assert should probably get a better error message telling the user that duplicated keys are not allowed and giving them some information what the widgets with duplicated keys are. We have a duplicated key error elsewhere, that you could probably reuse here.

Why do we need the indirection via slotToKeyedChild? Could these just be added to _slotToChild?

Can this just be a map? Maybe a LinkedHashMap if insert order needs to be preserved.

Couldn't this (combined with some of the other comments) just re-use the logic in _updateChild?

(We probably have to remove the assert in that method that wasn't valid anyways since you have to delete the justification comment there...)

Also I think the type parameter S should extend Object?

Why?

Why can we just use slot as fromSlot? Isn't it possible that slot contains another keyed widget that might move to another slot behind slot? E.g. what if we have
slots A, B
keyed widget K1, K2
unkeyed widget W

We start out with the following slot occupancy:

A: K1
B: W

In the next frame we want to go to:

A: K2
B: K1

I believe the current code would match (via updateChild) K1 with K2, which means K2 is not actually moved to B. Instead, a new element is created for K1 in slot B.

Yeah the updated test caught this, the elements were not reused.

These tests need to assert that the elements backing the widgets are still the same after the swap/move. That's the main indicator that something was actually moved and not just destroyed and recreated.

Regarding the one-pass, I was thinking we could do something like this (pseudo-code):

for (final S slot in slottedMultiChildRenderObjectWidgetMixin.slots) {
  final Widget? widget = slottedMultiChildRenderObjectWidgetMixin.childForSlot(slot);
  if (widget.key != null) {
    var oldChild = oldKeyToElement.remove(widget.key);
    if (oldChild == null) {
      oldChild = _slotToChild[slot].widget.key != null : _slotToChild[slot] : null;
    } else if (oldChild == _slotToChild[oldChild.slot]) {
       _slotToChild.remove(oldChild.slot);
    }
    var newChild = updateChild(oldChild, widget, slot);
    _slotToChild[slot] = newChild;
  } else {
   var oldChild = _slotToChild[slot].widget.key == null ? _slotToChild[slot] : null;
   var newChild = updateChild(oldChild, widget, slot);
   _slotToChild[slot] = newChild;
  }
}
// TODO: match the remaining children in oldKeyToElement to null with `updateChild`.

I am sure I messed up some details in that code, but something like that?

had to change this part as a result of the delayed deactivateChild call.

nit: for added clarity you could optionally use the same matcher here.