lib/src/line_splitter.dart - dart_style - Git at Google

 // 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' as debug;
 import 'line_prefix.dart';
 import 'line_writer.dart';
 import 'rule/rule.dart';

 /// Takes a series of [Chunk]s and determines the best way to split them into
 /// lines of output that fit within the page width (if possible).
 ///
 /// Imagine a naïve solution. You start at the first chunk in the list and work
 /// your way forward. For each chunk, you try every possible value of the rule
 /// that the chunk uses. Then, you ask the rule if that chunk should split or
 /// not when the rule has that value. If it does, then you try every possible
 /// way you could modify the expression nesting context at that point.
 ///
 /// For each of those possible results, you start with that as a partial
 /// solution. You move onto the next chunk and repeat the process, building on
 /// to that partial solution. When you reach the last chunk, you determine the
 /// cost of that set of rule values and keep track of the best one.
 ///
 /// Once you've tried every single possible permutation of rule values and
 /// nesting stacks, you will have exhaustively covered every possible way the
 /// line can be split and you'll know which one had the lowest cost. That's
 /// your result.
 ///
 /// The obvious problem is that this is exponential in the number of values for
 /// each rule and the expression nesting levels, both of which can be quite
 /// large with things like long method chains containing function literals,
 /// large collection literals, etc. To tame that, this uses dynamic programming.
 ///
 /// As the naïve solver is working its way down the chunks, it's building up a
 /// partial solution. This solution has:
 ///
 /// * A length—the number of chunks in it.
 /// * The set of rule values we have selected for the rules used by those
 ///   chunks.
 /// * The expression nesting stack that is currently active at the point where
 ///   the current chunk splits.
 ///
 /// We'll call this partial solution a [LinePrefix]. The naïve solution starts
 /// with an empty prefix (zero length, no rule values, no expression nesting).
 /// It grabs the next chunk after that prefix and says, OK, given this prefix
 /// what are all of the possible ways we can split that chunk (rule values and
 /// nesting stacks). Create a new, one-chunk-longer prefix for each of those
 /// and then recursively solve each of their suffixes.
 ///
 /// Normally, this would basically be a depth-first traversal of the entire
 /// possible solution space. However, there is a simple optimization we can
 /// make. When brute forcing the solution tree, we will often solve many
 /// prefixes with the same length.
 ///
 /// For example, if the first chunk's rule can take three different values, we
 /// will solve three line prefixes of length one, one for each rule value.
 /// Those in turn may have lots of permutations leading to even more solutions
 /// all with line prefixes of length two, and so on.
 ///
 /// In many cases, we have to treat these line prefixes separately. If two
 /// prefixes have the same length, but fix a different value for some rule, they
 /// may lead to different ways of splitting the suffix since that rule may
 /// appear in a later chunk too.
 ///
 /// But in many cases, the line prefixes are equivalent. For example, consider:
 ///
 ///     function(
 ///         first(arg, arg, arg, arg, arg, arg),
 ///         second,
 ///         third(arg, arg, arg, arg, arg, arg));
 ///
 /// The line splitter will try a number of different ways to split the argument
 /// list to `first`. For each of those, it then has to try all of the different
 /// ways it could split `third`. *However*, those two are unrelated. The way
 /// you split `first` has no impact on how you split `third`.
 ///
 /// The precise way to state that is that as the line prefix grows *past*
 /// `first()` and its argument list, it contains *less* state. It discards the
 /// rule value it selected for the argument list rule since that rule doesn't
 /// appear anywhere in the suffix and can't affect it. Any expression nesting
 /// inside the argument list has been popped off by the time we get to `second`.
 ///
 /// We'll try every possible way to split `first()`'s argument list and then
 /// recursively solve the remainder of the line for each of those possible
 /// splits. But each of those remainders will end up having identical prefixes.
 /// For any given [LinePrefix], there is a single best solution for the suffix.
 /// So, once we've found it, we can just reuse it the next time that same
 /// prefix comes up.
 ///
 /// In other words, we add a memoization table, [_bestSplits]. It is a map from
 /// [LinePrefix]es to [SplitSet]s. For each prefix, it stores the best set of
 /// splits to use for the following suffix. With this, instead of exploring the
 /// entire solution *tree*, which would be exponential, we just traverse the
 /// solution *graph* where entire branches of the tree that are identical
 /// collapse back together.
 ///
 /// The trick to making this work is storing the minimal amount of data in the
 /// line prefix to *uniquely* identify a suffix while still collapsing as many
 /// branches as possible. In practice, this means aggressively forgetting state
 /// when the prefix grows. In particular, we do not need to keep track of
 /// rule values we selected in the prefix if that rule does not affect anything
 /// in the suffix.
 ///
 /// There are a couple of other smaller scale optimizations too. If we ever hit
 /// a solution whose cost is zero, we know we won't do better, so we stop
 /// searching. If we make it to the end of the chunk list and we haven't gone
 /// past the end of the line, we know we don't need to split anywhere.
 ///
 /// But the memoization is the main thing that makes this tractable.
 class LineSplitter {
   final LineWriter _writer;

   /// The list of chunks being split.
   final List<Chunk> _chunks;

   /// The number of characters of additional indentation to apply to each line.
   ///
   /// This is used when formatting blocks to get the output into the right
   /// column based on where the block appears.
   final int _blockIndentation;

   /// Memoization table for the best set of splits for the remainder of the
   /// line following a given prefix.
   final _bestSplits = <LinePrefix, SplitSet>{};

   /// The rules that appear in the first `n` chunks of the line where `n` is
   /// the index into the list.
   final _prefixRules = <Set<Rule>>[];

   /// The rules that appear after the first `n` chunks of the line where `n` is
   /// the index into the list.
   final _suffixRules = <Set<Rule>>[];

   /// Creates a new splitter for [_writer] that tries to fit [chunks] into the
   /// page width.
   LineSplitter(this._writer, this._chunks, this._blockIndentation);

   /// Convert the line to a [String] representation.
   ///
   /// It will determine how best to split it into multiple lines of output and
   /// write the result to [writer].
   ///
   /// [firstLineIndent] is the number of characters of whitespace to prefix the
   /// first line of output with.
   SplitSolution apply(int firstLineIndent, {bool flushLeft}) {
     if (debug.traceSplitter) {
       debug.log(debug.green("\nSplitting:"));
       debug.dumpChunks(0, _chunks);
       debug.log();
     }

     // Ignore the trailing rule on the last chunk since it isn't used for
     // anything.
     var ruleChunks = _chunks.take(_chunks.length - 1);

     // Pre-calculate the set of rules appear before and after each length. We
     // use these frequently when creating [LinePrefix]es and they only depend
     // on the length, so we can cache them up front.
     for (var i = 0; i < _chunks.length; i++) {
       _prefixRules.add(ruleChunks.take(i).map((chunk) => chunk.rule).toSet());
       _suffixRules.add(ruleChunks.skip(i).map((chunk) => chunk.rule).toSet());
     }

     var prefix = new LinePrefix(firstLineIndent + _blockIndentation,
         flushLeft: flushLeft);
     var solution = new SplitSolution(prefix);
     _tryChunkRuleValues(solution, prefix);
     return solution;
   }

   /// Finds the best set of splits to apply to the remainder of the chunks
   /// following [prefix].
   ///
   /// This can only be called for a suffix that begins a new line. (In other
   /// words, the last chunk in the prefix cannot be unsplit.)
   SplitSet _findBestSplits(LinePrefix prefix) {
     // Use the memoized result if we have it.
     if (_bestSplits.containsKey(prefix)) {
       if (debug.traceSplitter) {
         debug.log("memoized splits for $prefix = ${_bestSplits[prefix]}");
       }
       return _bestSplits[prefix];
     }

     if (debug.traceSplitter) {
       debug.log("find splits for $prefix");
       debug.indent();
     }

     var solution = new SplitSolution(prefix);
     _tryChunkRuleValues(solution, prefix);

     if (debug.traceSplitter) {
       debug.unindent();
       debug.log("best splits for $prefix = ${solution.splits}");
     }

     return _bestSplits[prefix] = solution.splits;
   }

   /// Updates [solution] with the best rule value selection for the chunk
   /// immediately following [prefix].
   void _tryChunkRuleValues(SplitSolution solution, LinePrefix prefix) {
     // If we made it to the end, this prefix can be solved without splitting
     // any chunks.
     if (prefix.length == _chunks.length - 1) {
       solution.update(this, new SplitSet());
       return;
     }

     var chunk = _chunks[prefix.length];

     // See if we've already selected a value for the rule.
     var value = prefix.ruleValues[chunk.rule];

     if (value == null) {
       // No, so try every possible value for the rule.
       for (value = 0; value < chunk.rule.numValues; value++) {
         _tryRuleValue(solution, prefix, value);
       }
     } else if (value == -1) {
       // A -1 "value" means, "any non-zero value". In other words, the rule has
       // to split somehow, but can split however it chooses.
       for (value = 1; value < chunk.rule.numValues; value++) {
         _tryRuleValue(solution, prefix, value);
       }
     } else {
       // Otherwise, it's constrained to a single value, so use it.
       _tryRuleValue(solution, prefix, value);
     }
   }

   /// Updates [solution] with the best solution that can be found by setting
   /// the chunk after [prefix]'s rule to [value].
   void _tryRuleValue(SplitSolution solution, LinePrefix prefix, int value) {
     // If we already have an unbeatable solution, don't bother trying this one.
     if (solution.cost == 0) return;

     var chunk = _chunks[prefix.length];

     if (chunk.rule.isSplit(value, chunk)) {
       // The chunk is splitting in an expression, so try all of the possible
       // nesting combinations.
       var ruleValues = _advancePrefix(prefix, value);
       var longerPrefixes = prefix.split(chunk, _blockIndentation, ruleValues);
       for (var longerPrefix in longerPrefixes) {
         _tryLongerPrefix(solution, prefix, longerPrefix);

         // If we find an unbeatable solution, don't try any more.
         if (solution.cost == 0) break;
       }
     } else {
       // We didn't split here, so add this chunk and its rule value to the
       // prefix and continue on to the next.
       var extended = prefix.extend(_advancePrefix(prefix, value));
       _tryChunkRuleValues(solution, extended);
     }
   }

   /// Updates [solution] with the solution for [prefix] assuming it uses
   /// [longerPrefix] for the next chunk.
   void _tryLongerPrefix(
       SplitSolution solution, LinePrefix prefix, LinePrefix longerPrefix) {
     var remaining = _findBestSplits(longerPrefix);

     // If it wasn't possible to split the suffix given this nesting stack,
     // skip it.
     if (remaining == null) return;

     solution.update(this, remaining.add(prefix.length, longerPrefix.column));
   }

   /// Determines the set of rule values for a new [LinePrefix] one chunk longer
   /// than [prefix] whose rule on the new last chunk has [value].
   ///
   /// Returns a map of [Rule]s to values for those rules for the values that
   /// span the prefix and suffix of the [LinePrefix].
   Map<Rule, int> _advancePrefix(LinePrefix prefix, int value) {
     // Get the rules that appear in both in and after the new prefix. These are
     // the rules that already have values that the suffix needs to honor.
     var prefixRules = _prefixRules[prefix.length + 1];
     var suffixRules = _suffixRules[prefix.length + 1];

     var nextRule = _chunks[prefix.length].rule;
     var updatedValues = {};

     for (var prefixRule in prefixRules) {
       var ruleValue =
           prefixRule == nextRule ? value : prefix.ruleValues[prefixRule];

       if (suffixRules.contains(prefixRule)) {
         // If the same rule appears in both the prefix and suffix, then preserve
         // its exact value.
         updatedValues[prefixRule] = ruleValue;
       }

       // If we haven't specified any value for this rule in the prefix, it
       // doesn't place any constraint on the suffix.
       if (ruleValue == null) continue;

       // Enforce the constraints between rules.
       for (var suffixRule in suffixRules) {
         if (suffixRule == prefixRule) continue;

         // See if the prefix rule's value constrains any values in the suffix.
         var value = prefixRule.constrain(ruleValue, suffixRule);

         // Also consider the backwards case, where a later rule in the suffix
         // constrains a rule in the prefix.
         if (value == null) {
           value = suffixRule.reverseConstrain(ruleValue, prefixRule);
         }

         if (value != null) {
           updatedValues[prefixRule] = ruleValue;
           updatedValues[suffixRule] = value;
         }
       }
     }

     return updatedValues;
   }

   /// Evaluates the cost (i.e. the relative "badness") of splitting the line
   /// into [lines] physical lines based on the current set of rules.
   int _evaluateCost(LinePrefix prefix, SplitSet splits) {
     assert(splits != null);

     // Calculate the length of each line and apply the cost of any spans that
     // get split.
     var cost = 0;
     var length = prefix.column;

     var splitRules = new Set();

     endLine() {
       // Punish lines that went over the length. We don't rule these out
       // completely because it may be that the only solution still goes over
       // (for example with long string literals).
       if (length > _writer.pageWidth) {
         cost += (length - _writer.pageWidth) * Cost.overflowChar;
       }
     }

     // The set of spans that contain chunks that ended up splitting. We store
     // these in a set so a span's cost doesn't get double-counted if more than
     // one split occurs in it.
     var splitSpans = new Set();

     for (var i = prefix.length; i < _chunks.length; i++) {
       var chunk = _chunks[i];

       length += chunk.text.length;

       if (i < _chunks.length - 1) {
         if (splits.shouldSplitAt(i)) {
           endLine();

           splitSpans.addAll(chunk.spans);

           if (chunk.rule != null && !splitRules.contains(chunk.rule)) {
             // Don't double-count rules if multiple splits share the same
             // rule.
             splitRules.add(chunk.rule);
             cost += chunk.rule.cost;
           }

           // Include the cost of the nested block.
           if (chunk.blockChunks.isNotEmpty) {
             cost += _writer.formatBlock(chunk, splits.getColumn(i)).cost;
           }

           // Start the new line.
           length = splits.getColumn(i);
         } else {
           if (chunk.spaceWhenUnsplit) length++;

           // Include the nested block inline, if any.
           length += chunk.unsplitBlockLength;
         }
       }
     }

     // Add the costs for the spans containing splits.
     for (var span in splitSpans) cost += span.cost;

     // Finish the last line.
     endLine();

     return cost;
   }
 }

 /// Keeps track of the best set of splits found so far for a suffix of some
 /// prefix.
 class SplitSolution {
   /// The prefix whose suffix we are finding a solution for.
   final LinePrefix _prefix;

   /// The best set of splits currently found.
   SplitSet get splits => _bestSplits;
   SplitSet _bestSplits;

   /// The lowest cost currently found.
   int get cost => _lowestCost;
   int _lowestCost;

   /// Whether a solution that fits within a page has been found yet.
   bool get isAdequate => _lowestCost != null && _lowestCost < Cost.overflowChar;

   SplitSolution(this._prefix);

   /// Compares [splits] to the best solution found so far and keeps it if it's
   /// better.
   void update(LineSplitter splitter, SplitSet splits) {
     var cost = splitter._evaluateCost(_prefix, splits);

     if (_lowestCost == null || cost < _lowestCost) {
       _bestSplits = splits;
       _lowestCost = cost;
     }

     if (debug.traceSplitter) {
       var best = _bestSplits == splits ? " (best)" : "";
       debug.log(debug.gray("$_prefix $splits \$$cost$best"));
       debug.dumpLines(splitter._chunks, _prefix, splits);
       debug.log();
     }
   }
 }

 /// An immutable, persistent set of enabled split [Chunk]s.
 ///
 /// For each chunk, this tracks if it has been split and, if so, what the
 /// chosen column is for the following line.
 ///
 /// Internally, this uses a sparse parallel list where each element corresponds
 /// to the column of the chunk at that index in the chunk list, or `null` if
 /// there is no active split there. This had about a 10% perf improvement over
 /// using a [Set] of splits or a persistent linked list of split index/indent
 /// pairs.
 class SplitSet {
   List<int> _columns;

   /// Creates a new empty split set.
   SplitSet() : this._(const []);

   SplitSet._(this._columns);

   /// Returns a new [SplitSet] containing the union of this one and the split
   /// at [index] with next line starting at [column].
   SplitSet add(int index, int column) {
     var newIndents = new List(math.max(index + 1, _columns.length));
     newIndents.setAll(0, _columns);
     newIndents[index] = column;

     return new SplitSet._(newIndents);
   }

   /// Returns `true` if the chunk at [splitIndex] should be split.
   bool shouldSplitAt(int index) =>
       index < _columns.length && _columns[index] != null;

   /// Gets the zero-based starting column for the chunk at [index].
   int getColumn(int index) => _columns[index];

   String toString() {
     var result = [];
     for (var i = 0; i < _columns.length; i++) {
       if (_columns[i] != null) {
         result.add("$i:${_columns[i]}");
       }
     }

     return result.join(" ");
   }
 }
	// 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' as debug;
	import 'line_prefix.dart';
	import 'line_writer.dart';
	import 'rule/rule.dart';

	/// Takes a series of [Chunk]s and determines the best way to split them into
	/// lines of output that fit within the page width (if possible).
	///
	/// Imagine a naïve solution. You start at the first chunk in the list and work
	/// your way forward. For each chunk, you try every possible value of the rule
	/// that the chunk uses. Then, you ask the rule if that chunk should split or
	/// not when the rule has that value. If it does, then you try every possible
	/// way you could modify the expression nesting context at that point.
	///
	/// For each of those possible results, you start with that as a partial
	/// solution. You move onto the next chunk and repeat the process, building on
	/// to that partial solution. When you reach the last chunk, you determine the
	/// cost of that set of rule values and keep track of the best one.
	///
	/// Once you've tried every single possible permutation of rule values and
	/// nesting stacks, you will have exhaustively covered every possible way the
	/// line can be split and you'll know which one had the lowest cost. That's
	/// your result.
	///
	/// The obvious problem is that this is exponential in the number of values for
	/// each rule and the expression nesting levels, both of which can be quite
	/// large with things like long method chains containing function literals,
	/// large collection literals, etc. To tame that, this uses dynamic programming.
	///
	/// As the naïve solver is working its way down the chunks, it's building up a
	/// partial solution. This solution has:
	///
	/// * A length—the number of chunks in it.
	/// * The set of rule values we have selected for the rules used by those
	/// chunks.
	/// * The expression nesting stack that is currently active at the point where
	/// the current chunk splits.
	///
	/// We'll call this partial solution a [LinePrefix]. The naïve solution starts
	/// with an empty prefix (zero length, no rule values, no expression nesting).
	/// It grabs the next chunk after that prefix and says, OK, given this prefix
	/// what are all of the possible ways we can split that chunk (rule values and
	/// nesting stacks). Create a new, one-chunk-longer prefix for each of those
	/// and then recursively solve each of their suffixes.
	///
	/// Normally, this would basically be a depth-first traversal of the entire
	/// possible solution space. However, there is a simple optimization we can
	/// make. When brute forcing the solution tree, we will often solve many
	/// prefixes with the same length.
	///
	/// For example, if the first chunk's rule can take three different values, we
	/// will solve three line prefixes of length one, one for each rule value.
	/// Those in turn may have lots of permutations leading to even more solutions
	/// all with line prefixes of length two, and so on.
	///
	/// In many cases, we have to treat these line prefixes separately. If two
	/// prefixes have the same length, but fix a different value for some rule, they
	/// may lead to different ways of splitting the suffix since that rule may
	/// appear in a later chunk too.
	///
	/// But in many cases, the line prefixes are equivalent. For example, consider:
	///
	/// function(
	/// first(arg, arg, arg, arg, arg, arg),
	/// second,
	/// third(arg, arg, arg, arg, arg, arg));
	///
	/// The line splitter will try a number of different ways to split the argument
	/// list to `first`. For each of those, it then has to try all of the different
	/// ways it could split `third`. However, those two are unrelated. The way
	/// you split `first` has no impact on how you split `third`.
	///
	/// The precise way to state that is that as the line prefix grows past
	/// `first()` and its argument list, it contains less state. It discards the
	/// rule value it selected for the argument list rule since that rule doesn't
	/// appear anywhere in the suffix and can't affect it. Any expression nesting
	/// inside the argument list has been popped off by the time we get to `second`.
	///
	/// We'll try every possible way to split `first()`'s argument list and then
	/// recursively solve the remainder of the line for each of those possible
	/// splits. But each of those remainders will end up having identical prefixes.
	/// For any given [LinePrefix], there is a single best solution for the suffix.
	/// So, once we've found it, we can just reuse it the next time that same
	/// prefix comes up.
	///
	/// In other words, we add a memoization table, [_bestSplits]. It is a map from
	/// [LinePrefix]es to [SplitSet]s. For each prefix, it stores the best set of
	/// splits to use for the following suffix. With this, instead of exploring the
	/// entire solution tree, which would be exponential, we just traverse the
	/// solution graph where entire branches of the tree that are identical
	/// collapse back together.
	///
	/// The trick to making this work is storing the minimal amount of data in the
	/// line prefix to uniquely identify a suffix while still collapsing as many
	/// branches as possible. In practice, this means aggressively forgetting state
	/// when the prefix grows. In particular, we do not need to keep track of
	/// rule values we selected in the prefix if that rule does not affect anything
	/// in the suffix.
	///
	/// There are a couple of other smaller scale optimizations too. If we ever hit
	/// a solution whose cost is zero, we know we won't do better, so we stop
	/// searching. If we make it to the end of the chunk list and we haven't gone
	/// past the end of the line, we know we don't need to split anywhere.
	///
	/// But the memoization is the main thing that makes this tractable.
	class LineSplitter {
	final LineWriter _writer;

	/// The list of chunks being split.
	final List<Chunk> _chunks;

	/// The number of characters of additional indentation to apply to each line.
	///
	/// This is used when formatting blocks to get the output into the right
	/// column based on where the block appears.
	final int _blockIndentation;

	/// Memoization table for the best set of splits for the remainder of the
	/// line following a given prefix.
	final _bestSplits = <LinePrefix, SplitSet>{};

	/// The rules that appear in the first `n` chunks of the line where `n` is
	/// the index into the list.
	final _prefixRules = <Set<Rule>>[];

	/// The rules that appear after the first `n` chunks of the line where `n` is
	/// the index into the list.
	final _suffixRules = <Set<Rule>>[];

	/// Creates a new splitter for [_writer] that tries to fit [chunks] into the
	/// page width.
	LineSplitter(this._writer, this._chunks, this._blockIndentation);

	/// Convert the line to a [String] representation.
	///
	/// It will determine how best to split it into multiple lines of output and
	/// write the result to [writer].
	///
	/// [firstLineIndent] is the number of characters of whitespace to prefix the
	/// first line of output with.
	SplitSolution apply(int firstLineIndent, {bool flushLeft}) {
	if (debug.traceSplitter) {
	debug.log(debug.green("\nSplitting:"));
	debug.dumpChunks(0, _chunks);
	debug.log();
	}

	// Ignore the trailing rule on the last chunk since it isn't used for
	// anything.
	var ruleChunks = _chunks.take(_chunks.length - 1);

	// Pre-calculate the set of rules appear before and after each length. We
	// use these frequently when creating [LinePrefix]es and they only depend
	// on the length, so we can cache them up front.
	for (var i = 0; i < _chunks.length; i++) {
	_prefixRules.add(ruleChunks.take(i).map((chunk) => chunk.rule).toSet());
	_suffixRules.add(ruleChunks.skip(i).map((chunk) => chunk.rule).toSet());
	}

	var prefix = new LinePrefix(firstLineIndent + _blockIndentation,
	flushLeft: flushLeft);
	var solution = new SplitSolution(prefix);
	_tryChunkRuleValues(solution, prefix);
	return solution;
	}

	/// Finds the best set of splits to apply to the remainder of the chunks
	/// following [prefix].
	///
	/// This can only be called for a suffix that begins a new line. (In other
	/// words, the last chunk in the prefix cannot be unsplit.)
	SplitSet _findBestSplits(LinePrefix prefix) {
	// Use the memoized result if we have it.
	if (_bestSplits.containsKey(prefix)) {
	if (debug.traceSplitter) {
	debug.log("memoized splits for $prefix = ${_bestSplits[prefix]}");
	}
	return _bestSplits[prefix];
	}

	if (debug.traceSplitter) {
	debug.log("find splits for $prefix");
	debug.indent();
	}

	var solution = new SplitSolution(prefix);
	_tryChunkRuleValues(solution, prefix);

	if (debug.traceSplitter) {
	debug.unindent();
	debug.log("best splits for $prefix = ${solution.splits}");
	}

	return _bestSplits[prefix] = solution.splits;
	}

	/// Updates [solution] with the best rule value selection for the chunk
	/// immediately following [prefix].
	void _tryChunkRuleValues(SplitSolution solution, LinePrefix prefix) {
	// If we made it to the end, this prefix can be solved without splitting
	// any chunks.
	if (prefix.length == _chunks.length - 1) {
	solution.update(this, new SplitSet());
	return;
	}

	var chunk = _chunks[prefix.length];

	// See if we've already selected a value for the rule.
	var value = prefix.ruleValues[chunk.rule];

	if (value == null) {
	// No, so try every possible value for the rule.
	for (value = 0; value < chunk.rule.numValues; value++) {
	_tryRuleValue(solution, prefix, value);
	}
	} else if (value == -1) {
	// A -1 "value" means, "any non-zero value". In other words, the rule has
	// to split somehow, but can split however it chooses.
	for (value = 1; value < chunk.rule.numValues; value++) {
	_tryRuleValue(solution, prefix, value);
	}
	} else {
	// Otherwise, it's constrained to a single value, so use it.
	_tryRuleValue(solution, prefix, value);
	}
	}

	/// Updates [solution] with the best solution that can be found by setting
	/// the chunk after [prefix]'s rule to [value].
	void _tryRuleValue(SplitSolution solution, LinePrefix prefix, int value) {
	// If we already have an unbeatable solution, don't bother trying this one.
	if (solution.cost == 0) return;

	var chunk = _chunks[prefix.length];

	if (chunk.rule.isSplit(value, chunk)) {
	// The chunk is splitting in an expression, so try all of the possible
	// nesting combinations.
	var ruleValues = _advancePrefix(prefix, value);
	var longerPrefixes = prefix.split(chunk, _blockIndentation, ruleValues);
	for (var longerPrefix in longerPrefixes) {
	_tryLongerPrefix(solution, prefix, longerPrefix);

	// If we find an unbeatable solution, don't try any more.
	if (solution.cost == 0) break;
	}
	} else {
	// We didn't split here, so add this chunk and its rule value to the
	// prefix and continue on to the next.
	var extended = prefix.extend(_advancePrefix(prefix, value));
	_tryChunkRuleValues(solution, extended);
	}
	}

	/// Updates [solution] with the solution for [prefix] assuming it uses
	/// [longerPrefix] for the next chunk.
	void _tryLongerPrefix(
	SplitSolution solution, LinePrefix prefix, LinePrefix longerPrefix) {
	var remaining = _findBestSplits(longerPrefix);

	// If it wasn't possible to split the suffix given this nesting stack,
	// skip it.
	if (remaining == null) return;

	solution.update(this, remaining.add(prefix.length, longerPrefix.column));
	}

	/// Determines the set of rule values for a new [LinePrefix] one chunk longer
	/// than [prefix] whose rule on the new last chunk has [value].
	///
	/// Returns a map of [Rule]s to values for those rules for the values that
	/// span the prefix and suffix of the [LinePrefix].
	Map<Rule, int> _advancePrefix(LinePrefix prefix, int value) {
	// Get the rules that appear in both in and after the new prefix. These are
	// the rules that already have values that the suffix needs to honor.
	var prefixRules = _prefixRules[prefix.length + 1];
	var suffixRules = _suffixRules[prefix.length + 1];

	var nextRule = _chunks[prefix.length].rule;
	var updatedValues = {};

	for (var prefixRule in prefixRules) {
	var ruleValue =
	prefixRule == nextRule ? value : prefix.ruleValues[prefixRule];

	if (suffixRules.contains(prefixRule)) {
	// If the same rule appears in both the prefix and suffix, then preserve
	// its exact value.
	updatedValues[prefixRule] = ruleValue;
	}

	// If we haven't specified any value for this rule in the prefix, it
	// doesn't place any constraint on the suffix.
	if (ruleValue == null) continue;

	// Enforce the constraints between rules.
	for (var suffixRule in suffixRules) {
	if (suffixRule == prefixRule) continue;

	// See if the prefix rule's value constrains any values in the suffix.
	var value = prefixRule.constrain(ruleValue, suffixRule);

	// Also consider the backwards case, where a later rule in the suffix
	// constrains a rule in the prefix.
	if (value == null) {
	value = suffixRule.reverseConstrain(ruleValue, prefixRule);
	}

	if (value != null) {
	updatedValues[prefixRule] = ruleValue;
	updatedValues[suffixRule] = value;
	}
	}
	}

	return updatedValues;
	}

	/// Evaluates the cost (i.e. the relative "badness") of splitting the line
	/// into [lines] physical lines based on the current set of rules.
	int _evaluateCost(LinePrefix prefix, SplitSet splits) {
	assert(splits != null);

	// Calculate the length of each line and apply the cost of any spans that
	// get split.
	var cost = 0;
	var length = prefix.column;

	var splitRules = new Set();

	endLine() {
	// Punish lines that went over the length. We don't rule these out
	// completely because it may be that the only solution still goes over
	// (for example with long string literals).
	if (length > _writer.pageWidth) {
	cost += (length - _writer.pageWidth) * Cost.overflowChar;
	}
	}

	// The set of spans that contain chunks that ended up splitting. We store
	// these in a set so a span's cost doesn't get double-counted if more than
	// one split occurs in it.
	var splitSpans = new Set();

	for (var i = prefix.length; i < _chunks.length; i++) {
	var chunk = _chunks[i];

	length += chunk.text.length;

	if (i < _chunks.length - 1) {
	if (splits.shouldSplitAt(i)) {
	endLine();

	splitSpans.addAll(chunk.spans);

	if (chunk.rule != null && !splitRules.contains(chunk.rule)) {
	// Don't double-count rules if multiple splits share the same
	// rule.
	splitRules.add(chunk.rule);
	cost += chunk.rule.cost;
	}

	// Include the cost of the nested block.
	if (chunk.blockChunks.isNotEmpty) {
	cost += _writer.formatBlock(chunk, splits.getColumn(i)).cost;
	}

	// Start the new line.
	length = splits.getColumn(i);
	} else {
	if (chunk.spaceWhenUnsplit) length++;

	// Include the nested block inline, if any.
	length += chunk.unsplitBlockLength;
	}
	}
	}

	// Add the costs for the spans containing splits.
	for (var span in splitSpans) cost += span.cost;

	// Finish the last line.
	endLine();

	return cost;
	}
	}

	/// Keeps track of the best set of splits found so far for a suffix of some
	/// prefix.
	class SplitSolution {
	/// The prefix whose suffix we are finding a solution for.
	final LinePrefix _prefix;

	/// The best set of splits currently found.
	SplitSet get splits => _bestSplits;
	SplitSet _bestSplits;

	/// The lowest cost currently found.
	int get cost => _lowestCost;
	int _lowestCost;

	/// Whether a solution that fits within a page has been found yet.
	bool get isAdequate => _lowestCost != null && _lowestCost < Cost.overflowChar;

	SplitSolution(this._prefix);

	/// Compares [splits] to the best solution found so far and keeps it if it's
	/// better.
	void update(LineSplitter splitter, SplitSet splits) {
	var cost = splitter._evaluateCost(_prefix, splits);

	if (_lowestCost == null \|\| cost < _lowestCost) {
	_bestSplits = splits;
	_lowestCost = cost;
	}

	if (debug.traceSplitter) {
	var best = _bestSplits == splits ? " (best)" : "";
	debug.log(debug.gray("$_prefix $splits \$$cost$best"));
	debug.dumpLines(splitter._chunks, _prefix, splits);
	debug.log();
	}
	}
	}

	/// An immutable, persistent set of enabled split [Chunk]s.
	///
	/// For each chunk, this tracks if it has been split and, if so, what the
	/// chosen column is for the following line.
	///
	/// Internally, this uses a sparse parallel list where each element corresponds
	/// to the column of the chunk at that index in the chunk list, or `null` if
	/// there is no active split there. This had about a 10% perf improvement over
	/// using a [Set] of splits or a persistent linked list of split index/indent
	/// pairs.
	class SplitSet {
	List<int> _columns;

	/// Creates a new empty split set.
	SplitSet() : this._(const []);

	SplitSet._(this._columns);

	/// Returns a new [SplitSet] containing the union of this one and the split
	/// at [index] with next line starting at [column].
	SplitSet add(int index, int column) {
	var newIndents = new List(math.max(index + 1, _columns.length));
	newIndents.setAll(0, _columns);
	newIndents[index] = column;

	return new SplitSet._(newIndents);
	}

	/// Returns `true` if the chunk at [splitIndex] should be split.
	bool shouldSplitAt(int index) =>
	index < _columns.length && _columns[index] != null;

	/// Gets the zero-based starting column for the chunk at [index].
	int getColumn(int index) => _columns[index];

	String toString() {
	var result = [];
	for (var i = 0; i < _columns.length; i++) {
	if (_columns[i] != null) {
	result.add("$i:${_columns[i]}");
	}
	}

	return result.join(" ");
	}
	}