updateChildren method

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;
}