updateChildren method

  1. @protected
List<Element> updateChildren(
  1. List<Element> oldChildren,
  2. List<Widget> newWidgets, {
  3. Set<Element>? forgottenChildren,
  4. List<Object?>? slots,
})

Updates the children of this element to use new widgets.

Attempts to update the given old children list using the given new widgets, removing obsolete elements and introducing new ones as necessary, and then returns the new child list.

During this function the oldChildren list must not be modified. If the caller wishes to remove elements from oldChildren reentrantly while this function is on the stack, the caller can supply a forgottenChildren argument, which can be modified while this function is on the stack. Whenever this function reads from oldChildren, this function first checks whether the child is in forgottenChildren. If it is, the function acts as if the child was not in oldChildren.

This function is a convenience wrapper around updateChild, which updates each individual child. If slots is non-null, the value for the newSlot argument of updateChild is retrieved from that list using the index that the currently processed child corresponds to in the newWidgets list (newWidgets and slots must have the same length). If slots is null, an IndexedSlot<Element> is used as the value for the newSlot argument. In that case, IndexedSlot.index is set to the index that the currently processed child corresponds to in the newWidgets list and IndexedSlot.value is set to the Element of the previous widget in that list (or null if it is the first child).

When the slot value of an Element changes, its associated renderObject needs to move to a new position in the child list of its parents. If that RenderObject organizes its children in a linked list (as is done by the ContainerRenderObjectMixin) this can be implemented by re-inserting the child RenderObject into the list after the RenderObject associated with the Element provided as IndexedSlot.value in the slot object.

Using the previous sibling as a slot is not enough, though, because child RenderObjects are only moved around when the slot of their associated RenderObjectElements is updated. When the order of child Elements is changed, some elements in the list may move to a new index but still have the same previous sibling. For example, when [e1, e2, e3, e4] is changed to [e1, e3, e4, e2] the element e4 continues to have e3 as a previous sibling even though its index in the list has changed and its RenderObject needs to move to come before e2's RenderObject. In order to trigger this move, a new slot value needs to be assigned to its Element whenever its index in its parent's child list changes. Using an IndexedSlot<Element> achieves exactly that and also ensures that the underlying parent RenderObject knows where a child needs to move to in a linked list by providing its new previous sibling.

Implementation

@protected
List<Element> updateChildren(List<Element> oldChildren, List<Widget> newWidgets, { Set<Element>? forgottenChildren, List<Object?>? slots }) {
  assert(slots == null || newWidgets.length == slots.length);

  Element? replaceWithNullIfForgotten(Element child) {
    return forgottenChildren != null && forgottenChildren.contains(child) ? null : child;
  }

  Object? slotFor(int newChildIndex, Element? previousChild) {
    return slots != null
        ? slots[newChildIndex]
        : IndexedSlot<Element?>(newChildIndex, previousChild);
  }

  // This attempts to diff the new child list (newWidgets) with
  // the old child list (oldChildren), and produce a new list of elements to
  // be the new list of child elements of this element. The called of this
  // method is expected to update this render object accordingly.

  // The cases it tries to optimize for are:
  //  - the old list is empty
  //  - the lists are identical
  //  - there is an insertion or removal of one or more widgets in
  //    only one place in the list
  // If a widget with a key is in both lists, it will be synced.
  // Widgets without keys might be synced but there is no guarantee.

  // The general approach is to sync the entire new list backwards, as follows:
  // 1. Walk the lists from the top, syncing nodes, until you no longer have
  //    matching nodes.
  // 2. Walk the lists from the bottom, without syncing nodes, until you no
  //    longer have matching nodes. We'll sync these nodes at the end. We
  //    don't sync them now because we want to sync all the nodes in order
  //    from beginning to end.
  // At this point we narrowed the old and new lists to the point
  // where the nodes no longer match.
  // 3. Walk the narrowed part of the old list to get the list of
  //    keys and sync null with non-keyed items.
  // 4. Walk the narrowed part of the new list forwards:
  //     * Sync non-keyed items with null
  //     * Sync keyed items with the source if it exists, else with null.
  // 5. Walk the bottom of the list again, syncing the nodes.
  // 6. Sync null with any items in the list of keys that are still
  //    mounted.

  int newChildrenTop = 0;
  int oldChildrenTop = 0;
  int newChildrenBottom = newWidgets.length - 1;
  int oldChildrenBottom = oldChildren.length - 1;

  final List<Element> newChildren = List<Element>.filled(newWidgets.length, _NullElement.instance);

  Element? previousChild;

  // Update the top of the list.
  while ((oldChildrenTop <= oldChildrenBottom) && (newChildrenTop <= newChildrenBottom)) {
    final Element? oldChild = replaceWithNullIfForgotten(oldChildren[oldChildrenTop]);
    final Widget newWidget = newWidgets[newChildrenTop];
    assert(oldChild == null || oldChild._lifecycleState == _ElementLifecycle.active);
    if (oldChild == null || !Widget.canUpdate(oldChild.widget, newWidget)) {
      break;
    }
    final Element newChild = updateChild(oldChild, newWidget, slotFor(newChildrenTop, previousChild))!;
    assert(newChild._lifecycleState == _ElementLifecycle.active);
    newChildren[newChildrenTop] = newChild;
    previousChild = newChild;
    newChildrenTop += 1;
    oldChildrenTop += 1;
  }

  // Scan the bottom of the list.
  while ((oldChildrenTop <= oldChildrenBottom) && (newChildrenTop <= newChildrenBottom)) {
    final Element? oldChild = replaceWithNullIfForgotten(oldChildren[oldChildrenBottom]);
    final Widget newWidget = newWidgets[newChildrenBottom];
    assert(oldChild == null || oldChild._lifecycleState == _ElementLifecycle.active);
    if (oldChild == null || !Widget.canUpdate(oldChild.widget, newWidget)) {
      break;
    }
    oldChildrenBottom -= 1;
    newChildrenBottom -= 1;
  }

  // Scan the old children in the middle of the list.
  final bool haveOldChildren = oldChildrenTop <= oldChildrenBottom;
  Map<Key, Element>? oldKeyedChildren;
  if (haveOldChildren) {
    oldKeyedChildren = <Key, Element>{};
    while (oldChildrenTop <= oldChildrenBottom) {
      final Element? oldChild = replaceWithNullIfForgotten(oldChildren[oldChildrenTop]);
      assert(oldChild == null || oldChild._lifecycleState == _ElementLifecycle.active);
      if (oldChild != null) {
        if (oldChild.widget.key != null) {
          oldKeyedChildren[oldChild.widget.key!] = oldChild;
        } else {
          deactivateChild(oldChild);
        }
      }
      oldChildrenTop += 1;
    }
  }

  // Update the middle of the list.
  while (newChildrenTop <= newChildrenBottom) {
    Element? oldChild;
    final Widget newWidget = newWidgets[newChildrenTop];
    if (haveOldChildren) {
      final Key? key = newWidget.key;
      if (key != null) {
        oldChild = oldKeyedChildren![key];
        if (oldChild != null) {
          if (Widget.canUpdate(oldChild.widget, newWidget)) {
            // we found a match!
            // remove it from oldKeyedChildren so we don't unsync it later
            oldKeyedChildren.remove(key);
          } else {
            // Not a match, let's pretend we didn't see it for now.
            oldChild = null;
          }
        }
      }
    }
    assert(oldChild == null || Widget.canUpdate(oldChild.widget, newWidget));
    final Element newChild = updateChild(oldChild, newWidget, slotFor(newChildrenTop, previousChild))!;
    assert(newChild._lifecycleState == _ElementLifecycle.active);
    assert(oldChild == newChild || oldChild == null || oldChild._lifecycleState != _ElementLifecycle.active);
    newChildren[newChildrenTop] = newChild;
    previousChild = newChild;
    newChildrenTop += 1;
  }

  // We've scanned the whole list.
  assert(oldChildrenTop == oldChildrenBottom + 1);
  assert(newChildrenTop == newChildrenBottom + 1);
  assert(newWidgets.length - newChildrenTop == oldChildren.length - oldChildrenTop);
  newChildrenBottom = newWidgets.length - 1;
  oldChildrenBottom = oldChildren.length - 1;

  // Update the bottom of the list.
  while ((oldChildrenTop <= oldChildrenBottom) && (newChildrenTop <= newChildrenBottom)) {
    final Element oldChild = oldChildren[oldChildrenTop];
    assert(replaceWithNullIfForgotten(oldChild) != null);
    assert(oldChild._lifecycleState == _ElementLifecycle.active);
    final Widget newWidget = newWidgets[newChildrenTop];
    assert(Widget.canUpdate(oldChild.widget, newWidget));
    final Element newChild = updateChild(oldChild, newWidget, slotFor(newChildrenTop, previousChild))!;
    assert(newChild._lifecycleState == _ElementLifecycle.active);
    assert(oldChild == newChild || oldChild._lifecycleState != _ElementLifecycle.active);
    newChildren[newChildrenTop] = newChild;
    previousChild = newChild;
    newChildrenTop += 1;
    oldChildrenTop += 1;
  }

  // Clean up any of the remaining middle nodes from the old list.
  if (haveOldChildren && oldKeyedChildren!.isNotEmpty) {
    for (final Element oldChild in oldKeyedChildren.values) {
      if (forgottenChildren == null || !forgottenChildren.contains(oldChild)) {
        deactivateChild(oldChild);
      }
    }
  }
  assert(newChildren.every((Element element) => element is! _NullElement));
  return newChildren;
}