Discard unused nesting levels.

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 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.
@@ skipping 19 matching lines @@
         // Should have a valid set of splits when we get here.
         assert(indent != invalidSplits);
       } else {
         if (chunk.spaceWhenUnsplit) buffer.write(" ");
       }
     }
 
     return selection;
   }
 
+  /// Removes any unused nesting levels from the chunks.
+  ///
+  /// The line splitter considers every possible combination of mapping
+  /// indentation to nesting levels when trying to find the best solution. For
+  /// example, it may assign 4 spaces of indentation to level 1, 8 spaces to
+  /// level 3, etc.
+  ///
+  /// 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() {
+    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];
+    }
+  }
+
   /// 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);
 
     var bestSplits;
     var lowestCost;
@@ skipping 166 matching lines @@
     }
 
     return false;
   }
 
   /// Gets whether the suffix of the line after index [split] contains a soft
   /// split using [param].
   bool _suffixContainsParam(int split, SplitParam param) {
     if (param == null) return false;
 
+    // TODO(rnystrom): Consider caching the set of params that appear at every
+    // suffix.
     for (var i = split + 1; i < _chunks.length; i++) {
       if (_chunks[i].isSoftSplit && _chunks[i].param == param) {
         return true;
       }
     }
 
     return false;
   }
 
   /// Evaluates the cost (i.e. the relative "badness") of splitting the line
@@ skipping 128 matching lines @@
     var result = [];
     for (var i = 0; i < _splitNesting.length; i++) {
       if (_splitNesting[i] != null) {
         result.add("$i:${_splitNesting[i]}");
       }
     }
 
     return result.join(" ");
   }
 }