updateChildren method

  1. @protected
List<Element> updateChildren (List<Element> oldChildren, List<Widget> newWidgets, { Set<Element> forgottenChildren })
@protected

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 re-entrantly 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. When calling updateChild, this function uses the previous element as the newSlot argument.

Implementation

@protected
List<Element> updateChildren(List<Element> oldChildren, List<Widget> newWidgets, { Set<Element> forgottenChildren }) {
  assert(oldChildren != null);
  assert(newWidgets != null);

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

  // 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 = oldChildren.length == newWidgets.length ?
      oldChildren : List<Element>(newWidgets.length);

  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._debugLifecycleState == _ElementLifecycle.active);
    if (oldChild == null || !Widget.canUpdate(oldChild.widget, newWidget))
      break;
    final Element newChild = updateChild(oldChild, newWidget, previousChild);
    assert(newChild._debugLifecycleState == _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._debugLifecycleState == _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._debugLifecycleState == _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, previousChild);
    assert(newChild._debugLifecycleState == _ElementLifecycle.active);
    assert(oldChild == newChild || oldChild == null || oldChild._debugLifecycleState != _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._debugLifecycleState == _ElementLifecycle.active);
    final Widget newWidget = newWidgets[newChildrenTop];
    assert(Widget.canUpdate(oldChild.widget, newWidget));
    final Element newChild = updateChild(oldChild, newWidget, previousChild);
    assert(newChild._debugLifecycleState == _ElementLifecycle.active);
    assert(oldChild == newChild || oldChild == null || oldChild._debugLifecycleState != _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 (Element oldChild in oldKeyedChildren.values) {
      if (forgottenChildren == null || !forgottenChildren.contains(oldChild))
        deactivateChild(oldChild);
    }
  }

  return newChildren;
}