Automatically harden splits containing too much nesting. Fix #108.

lib/src/line_splitter.dart

 // Copyright (c) 2014, 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.
 
 library dart_style.src.line_splitter;
 
 import 'dart:math' as math;
 
 import 'chunk.dart';
 import 'debug.dart';
@@ skipping 85 matching lines @@
   /// return a single string that may contain one or more newline characters.
   ///
   /// Returns a two-element list. The first element will be an [int] indicating
   /// where in [buffer] the selection start point should appear if it was
   /// contained in the formatted list of chunks. Otherwise it will be `null`.
   /// Likewise, the second element will be non-`null` if the selection endpoint
   /// is within the list of chunks.
   List<int> apply(StringBuffer buffer) {
     if (debugFormatter) dumpLine(_chunks, _indent);
 
-    _flattenNestingLevels();
+    var nestingDepth = _flattenNestingLevels();
+
+    // Hack. The formatter doesn't handle formatting very deeply nested code
+    // well. It can make performance spiral into a pit of sadness. Fortunately,
+    // we only tend to see expressions pathologically deeply nested in
+    // generated code that isn't read by humans much anyway. To avoid burning
+    // too much time on these, harden any splits containing more than a certain
+    // level of nesting.
+    //
+    // The number here was chosen empirically based on formatting the repo. It
+    // was picked to get the best performance while affecting the minimum amount
+    // of results.
+    // TODO(rnystrom): Do something smarter.

[pquitslund, 2015/03/11 00:09:50]

Best comment I've read all year.

[Bob Nystrom, 2015/03/11 00:14:17]

:D

+    if (nestingDepth > 9) {
+      for (var chunk in _chunks) {
+        if (chunk.param != null && nestingDepth - chunk.nesting > 9) {
+          chunk.harden();
+        }
+      }
+    }
 
     var splits = _findBestSplits(new LinePrefix());
+
     var selection = [null, null];
 
     // Write each chunk and the split after it.
     buffer.write(" " * (_indent * spacesPerIndent));
     for (var i = 0; i < _chunks.length; i++) {
       var chunk = _chunks[i];
 
       // If this chunk contains one of the selection markers, tell the writer
       // where it ended up in the final output.
       if (chunk.selectionStart != null) {
@@ skipping 35 matching lines @@
   /// It's fairly common for a nesting level to not actually appear at the
   /// boundary of a chunk. The source visitor may enter more than one level of
   /// nesting at a point where a split cannot happen. In that case, there's no
   /// point in trying to assign an indentation level to that nesting level. It
   /// will never be used because no line will begin at that level of
   /// indentation.
   ///
   /// Worse, if the splitter *does* consider these levels, it can dramatically
   /// increase solving time. To avoid that, this renumbers all of the nesting
   /// levels in the chunks to not have any of these unused gaps.
-  void _flattenNestingLevels() {
+  ///
+  /// Returns the number of distinct nesting levels remaining after flattening.
+  /// This may be zero if the chunks have no nesting (i.e. just statement-level
+  /// indentation).
+  int _flattenNestingLevels() {
     var nestingLevels = _chunks
         .map((chunk) => chunk.nesting)
         .where((nesting) => nesting != -1)
         .toSet()
         .toList();
     nestingLevels.sort();
 
     var nestingMap = {-1: -1};
     for (var i = 0; i < nestingLevels.length; i++) {
       nestingMap[nestingLevels[i]] = i;
     }
 
     for (var chunk in _chunks) {
       chunk.nesting = nestingMap[chunk.nesting];
     }
+
+    return nestingLevels.length;
   }
 
   /// Finds the best set of splits to apply to the remainder of the line
   /// following [prefix].
   SplitSet _findBestSplits(LinePrefix prefix) {
     // Use the memoized result if we have it.
     if (_bestSplits.containsKey(prefix)) return _bestSplits[prefix];
 
     var indent = prefix.getNextLineIndent(_chunks, _indent);
 
@@ skipping 318 matching lines @@
     var result = [];
     for (var i = 0; i < _splitNesting.length; i++) {
       if (_splitNesting[i] != null) {
         result.add("$i:${_splitNesting[i]}");
       }
     }
 
     return result.join(" ");
   }
 }