Avoid Stack Overflows during VirtualTree expansion

runtime/observatory/lib/src/elements/containers/virtual_tree.dart

Index: runtime/observatory/lib/src/elements/containers/virtual_tree.dart
diff --git a/runtime/observatory/lib/src/elements/containers/virtual_tree.dart b/runtime/observatory/lib/src/elements/containers/virtual_tree.dart
index 45972483287f4deb2242b374cce2841226284f82..a1026bc31321cb40ba00c53fd4fa9ed39b3e26c2 100644
--- a/runtime/observatory/lib/src/elements/containers/virtual_tree.dart
+++ b/runtime/observatory/lib/src/elements/containers/virtual_tree.dart
@@ -4,6 +4,7 @@
 
 import 'dart:async';
 import 'dart:html';
+import 'dart:collection';
 import 'dart:math' as Math;
 import 'package:observatory/src/elements/containers/virtual_collection.dart';
 import 'package:observatory/src/elements/helpers/rendering_scheduler.dart';
@@ -89,8 +90,12 @@ class VirtualTreeElement extends HtmlElement implements Renderable {
       bool autoExpandWholeTree: false}) {
     if (_expanded.add(item)) _r.dirty();
     if (autoExpandWholeTree) {
-      for (final child in _children(item)) {
-        expand(child, autoExpandWholeTree: true);
+      Queue toDo = new Queue();

[rmacnak, 2017/07/06 00:10:20]

Maybe add a note here that the tree is potentially very deep so no one looks at
this later and switches it back to simple recursion.

Consider "pendingNodes" instead of "toDo"

[cbernaschina, 2017/07/06 00:33:46]

Done.

+      toDo.addAll(_children(item));
+      while (toDo.isNotEmpty) {
+        final item = toDo.removeFirst();
+        if (_expanded.add(item)) _r.dirty();
+        toDo.addAll(_children(item));
       }
     } else if (autoExpandSingleChildNodes) {
       var children = _children(item);
@@ -106,8 +111,12 @@ class VirtualTreeElement extends HtmlElement implements Renderable {
       bool autoCollapseWholeTree: false}) {
     if (_expanded.remove(item)) _r.dirty();
     if (autoCollapseWholeTree) {
-      for (final child in _children(item)) {
-        collapse(child, autoCollapseWholeTree: true);
+      Queue toDo = new Queue();
+      toDo.addAll(_children(item));
+      while (toDo.isNotEmpty) {
+        final item = toDo.removeFirst();
+        if (_expanded.remove(item)) _r.dirty();
+        toDo.addAll(_children(item));
       }
     } else if (autoCollapseSingleChildNodes) {
       var children = _children(item);
@@ -137,29 +146,32 @@ class VirtualTreeElement extends HtmlElement implements Renderable {
     if (children.length == 0) {
       children = [_collection];
     }
-    Iterable _toList(item) {
-      if (isExpanded(item)) {
-        Iterable children = _children(item);
-        if (children.isNotEmpty) {
-          return [item]..addAll(children.expand(_toList));
-        }
-      }
-      return [item];
-    }
 
-    _collection.items = _items.expand(_toList);
-    var depth = 0;
-    Iterable _toDepth(item) {
-      if (isExpanded(item)) {
-        Iterable children = _children(item);
-        if (children.isNotEmpty) {
-          depth++;
-          return children.expand(_toDepth).toList()..insert(0, --depth);
+    final items = [];
+    final depths = new List.filled(_items.length, 0, growable: true);
+
+    {
+      final toDo = new Queue();
+
+      toDo.addAll(_items);
+      while (toDo.isNotEmpty) {
+        final item = toDo.removeFirst();
+
+        items.add(item);
+        if (isExpanded(item)) {
+          final children = _children(item);
+          children
+              .toList(growable: false)
+              .reversed
+              .forEach((c) => toDo.addFirst(c));
+          final depth = depths[items.length - 1];
+          depths.insertAll(
+              items.length, new List.filled(children.length, depth + 1));
         }
       }
-      return [depth];
     }
 
-    _depths = _items.expand(_toDepth).toList();
+    _depths = depths;
+    _collection.items = items;
   }
 }