Avoid Stack Overflows during VirtualTree expansion

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

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 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';
 import 'package:observatory/src/elements/helpers/tag.dart';
 
 typedef HtmlElement VirtualTreeCreateCallback(
     toggle({bool autoToggleSingleChildNodes, bool autoToggleWholeTree}));
 typedef void VirtualTreeUpdateCallback(HtmlElement el, dynamic item, int depth);
 typedef Iterable<dynamic> VritualTreeGetChildrenCallback(dynamic value);
 
@@ skipping 65 matching lines @@
 
   bool isExpanded(item) {
     return _expanded.contains(item);
   }
 
   void expand(item,
       {bool autoExpandSingleChildNodes: false,
       bool autoExpandWholeTree: false}) {
     if (_expanded.add(item)) _r.dirty();
     if (autoExpandWholeTree) {
-      for (final child in _children(item)) {
-        expand(child, autoExpandWholeTree: true);
+      // The tree is potentially very deep, simple recursion can produce a
+      // Stack Overflow
+      Queue pendingNodes = new Queue();
+      pendingNodes.addAll(_children(item));
+      while (pendingNodes.isNotEmpty) {
+        final item = pendingNodes.removeFirst();
+        if (_expanded.add(item)) _r.dirty();
+        pendingNodes.addAll(_children(item));
       }
     } else if (autoExpandSingleChildNodes) {
       var children = _children(item);
       while (children.length == 1) {
         _expanded.add(children.first);
         children = _children(children.first);
       }
     }
   }
 
   void collapse(item,
       {bool autoCollapseSingleChildNodes: false,
       bool autoCollapseWholeTree: false}) {
     if (_expanded.remove(item)) _r.dirty();
     if (autoCollapseWholeTree) {
-      for (final child in _children(item)) {
-        collapse(child, autoCollapseWholeTree: true);
+      // The tree is potentially very deep, simple recursion can produce a
+      // Stack Overflow
+      Queue pendingNodes = new Queue();
+      pendingNodes.addAll(_children(item));
+      while (pendingNodes.isNotEmpty) {
+        final item = pendingNodes.removeFirst();
+        if (_expanded.remove(item)) _r.dirty();
+        pendingNodes.addAll(_children(item));
       }
     } else if (autoCollapseSingleChildNodes) {
       var children = _children(item);
       while (children.length == 1) {
         _expanded.remove(children.first);
         children = _children(children.first);
       }
     }
   }
 
   @override
   attached() {
     super.attached();
     _r.enable();
   }
 
   @override
   detached() {
     super.detached();
     _r.disable(notify: true);
     children = const [];
   }
 
   VirtualCollectionElement _collection;
 
   void render() {
     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));
+
+    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 [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);
-        }
-      }
-      return [depth];
-    }
-
-    _depths = _items.expand(_toDepth).toList();
+    _depths = depths;
+    _collection.items = items;
   }
 }