Coverage report for lib/src/line_splitting/solve_state.dart

// Copyright (c) 2015, 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_splitting.solve_state;

import '../debug.dart' as debug;

import '../nesting_level.dart';

import '../rule/rule.dart';

import '../whitespace.dart';

import 'line_splitter.dart';

import 'rule_set.dart';

/// A possibly incomplete solution in the line splitting search space.

///

/// A single [SolveState] binds some subset of the rules to values while

/// leaving the rest unbound. If every rule is bound, the solve state describes

/// a complete solution to the line splitting problem. Even if rules are

/// unbound, a state can also usually be used as a solution by treating all

/// unbound rules as unsplit. (The usually is because a state that constrains

/// an unbound rule to split can't be used with that rule unsplit.)

///

/// From a given solve state, we can explore the search tree to more refined

/// solve states by producing new ones that add more bound rules to the current

/// state.

class SolveState {

  final LineSplitter _splitter;

  final RuleSet _ruleValues;

  /// The set of [Rule]s that are bound by [_ruleValues].

  ///

  /// Cached by [_ensureConstraints] for use by [_ensureUnboundConstraints].

  Set<Rule> _boundRules;

  /// The set of [Rule]s that are not bound by [_ruleValues].

  ///

  /// Cached by [_ensureConstraints] for use by [_ensureUnboundConstraints].

  Set<Rule> _unboundRules;

  /// The unbound rules in this state that can be bound to produce new more

  /// refined states.

  ///

  /// Keeping this set small is the key to make the entire line splitter

  /// perform well. If we consider too many rules at each state, our

  /// exploration of the solution space is too branchy and we waste time on

  /// dead end solutions.

  ///

  /// Here is the key insight. The line splitter treats any unbound rule as

  /// being unsplit. This means refining a solution always means taking a rule

  /// that is unsplit and making it split. That monotonically increases the

  /// cost, but may help fit the solution inside the page.

  ///

  /// We want to keep the cost low, so the only reason to consider making a

  /// rule split is if it reduces an overflowing line. It's also the case that

  /// splitting an earlier rule will often reshuffle the rest of the line.

  ///

  /// Taking that into account, the only rules we consider binding to extend a

  /// solve state are *unbound rules inside the first line that is overflowing*.

  /// Even if a line has dozens of rules, this generally keeps the branching

  /// down to a few. It also means rules inside lines that already fit are

  /// never touched.

  ///

  /// There is one other set of rules that go in here. Sometimes a bound rule

  /// in the solve state constrains some other unbound rule to split. In that

  /// case, we also consider that active so we know to not leave it at zero.

  final _liveRules = new Set<Rule>();

  /// The set of splits chosen for this state.

  SplitSet _splits;

  /// The number of characters that do not fit inside the page with this set of

  /// splits.

  int _overflowChars;

  /// Whether we can treat this state as a complete solution by leaving its

  /// unbound rules unsplit.

  ///

  /// This is generally true but will be false if the state contains any

  /// unbound rules that are constrained to not be zero by other bound rules.

  /// This avoids picking a solution that leaves those rules at zero when they

  /// aren't allowed to be.

  bool _isComplete = true;

  /// The constraints the bound rules in this state have on the remaining

  /// unbound rules.

  Map<Rule, int> _constraints;

  /// The unbound rule values that are disallowed because they would place

  /// invalid constraints on the currently bound values.

  ///

  /// For example, say rule A is bound to 1 and B is unbound. If B has value

  /// 1, it constrains A to be 1. Likewise, if B is 2, it constrains A to be

  /// 2 as well. Since we already know A is 1, that means we know B cannot be

  /// bound to value 2. This means B is more limited in this state than it

  /// might be in another state that binds A to a different value.

  ///

  /// It's important to track this, because we can't allow to states to overlap

  /// if one permits more values for some unbound rule than the other does.

  Map<Rule, Set<int>> _unboundConstraints;

  /// The bound rules that appear inside lines also containing unbound rules.

  ///

  /// By appearing in the same line, it means these bound rules may affect the

  /// results of binding those unbound rules. This is used to tell if two

  /// states may diverge by binding unbound rules or not.

  Set<Rule> _boundRulesInUnboundLines;

  }

  /// Gets the value to use for [rule], either the bound value or

  /// [Rule.unsplit] if it isn't bound.

  /// Returns `true` if this state is a better solution to use as the final

  /// result than [other].

    // If this state contains an unbound rule that we know can't be left

    // unsplit, we can't pick this as a solution.

    // Anything is better than nothing.

    if (other == null) return true;

    // Prefer the solution that fits the most in the page.

    }

    // Otherwise, prefer the best cost.

  }

  /// Determines if this state "overlaps" [other].

  ///

  /// Two states overlap if they currently have the same score and we can tell

  /// for certain that they won't diverge as their unbound rules are bound. If

  /// that's the case, then whichever state is better now (based on their

  /// currently bound rule values) is the one that will always win, regardless

  /// of how they get expanded.

  ///

  /// In other words, their entire expanded solution trees also overlap. In

  /// that case, there's no point in expanding both, so we can just pick the

  /// winner now and discard the other.

  ///

  /// For this to be true, we need to prove that binding an unbound rule won't

  /// affect one state differently from the other. We have to show that they

  /// are parallel.

  ///

  /// Two things could cause this *not* to be the case.

  ///

  /// 1. If one state's bound rules place different constraints on the unbound

  ///    rules than the other.

  ///

  /// 2. If one state's different bound rules are in the same line as an

  ///    unbound rule. That affects the indentation and length of the line,

  ///    which affects the context where the unbound rule is being chosen.

  ///

  /// If neither of these is the case, the states overlap. Returns `<0` if this

  /// state is better, or `>0` if [other] wins. If the states do not overlap,

  /// returns `0`.

    // They do overlap, so see which one wins.

    }

    // The way SolveStates are expanded should guarantee that we never generate

    // the exact same state twice. Getting here implies that that failed.

    throw "unreachable";

  }

  /// Enqueues more solve states to consider based on this one.

  ///

  /// For each unbound rule in this state that occurred in the first long line,

  /// enqueue solve states that bind that rule to each value it can have and

  /// bind all previous rules to zero. (In other words, try all subsolutions

  /// where that rule becomes the first new rule to split at.)

    // Walk down the rules looking for unbound ones to try.

    var triedRules = 0;

        // We found one worth trying, so try all of its values.

          List<Rule> mustSplitRules;

          });

          // Make sure we don't violate the constraints of the bound rules.

          if (!valid) continue;

          // If some unbound rules are constrained to split, remember that.

          if (mustSplitRules != null) {

          }

        }

        // Stop once we've tried all of the ones we can.

      }

      // Fill in previous unbound rules with zero.

        // Pass a dummy callback because zero will never fail. (If it would

        // have, that rule would already be bound to some other value.)

          break;

        }

      }

    }

  }

  /// Returns `true` if [other] overlaps this state.

    // Lines that contain both bound and unbound rules must have the same

    // bound values.

      return false;

    }

        return false;

      }

    }

    }

      return false;

    }

      }

    }

    return true;

  }

  /// Calculates the [SplitSet] for this solve state, assuming any unbound

  /// rules are set to zero.

    // Figure out which expression nesting levels got split and need to be

    // assigned columns.

      }

    }

    }

        var indent = 0;

          // Add in the chunk's indent.

          // And any expression nesting.

        }

      }

    }

  }

  /// Evaluates the cost (i.e. the relative "badness") of splitting the line

  /// into [lines] physical lines based on the current set of rules.

    // Calculate the length of each line and apply the cost of any spans that

    // get split.

    var cost = 0;

    // The unbound rules in use by the current line. This will be null after

    // the first long line has completed.

    var foundOverflowRules = false;

    var start = 0;

      // Track lines that went over the length. It is only rules contained in

      // long lines that we may want to split.

        // Only try rules that are in the first long line, since we know at

        // least one of them *will* be split.

        if (!foundOverflowRules) {

              foundOverflowRules = true;

            }

          }

        }

      }

      start = end;

    }

    // 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.

    // The nesting level of the chunk that ended the previous line.

    var previousNesting;

      // Ignore the split after the last chunk.

        // Include the cost of the nested block.

        }

        // Do not allow sequential lines to have the same indentation but for

        // different reasons. In other words, don't allow different expressions

        // to claim the same nesting level on subsequent lines.

        //

        // A contrived example would be:

        //

        //     function(inner(

        //         argument), second(

        //         another);

        //

        // For the most part, we prevent this by the constraints on splits.

        // For example, the above can't happen because the split before

        // "argument", forces the split before "second".

        //

        // But there are a couple of squirrely cases where it's hard to prevent

        // by construction. Instead, this outlaws it by penalizing it very

        // heavily if it happens to get this far.

        if (previousNesting != null &&

        }

        // Start the new line.

      } else {

        // Include the nested block inline, if any.

      }

    }

    // Add the costs for the rules that have any splits.

    });

    // Add the costs for the spans containing splits.

    // Finish the last line.

  }

  /// Adds [rule] and all of the rules it constrains to the set of [_liveRules].

  ///

  /// Only does this if [rule] is a valid soft rule. Returns `true` if any new

  /// live rules were added.

    if (rule == null) return false;

    var added = false;

      added = true;

    }

    return added;

  }

  /// Lazily initializes the [_boundInUnboundLines], which is needed to compare

  /// two states for overlap.

  ///

  /// We do this lazily because the calculation is a bit slow, and is only

  /// needed when we have two states with the same score.

    var hasUnbound = false;

        hasUnbound = false;

      }

      if (rule != null) {

        } else {

          hasUnbound = true;

        }

      }

    }

  }

  /// Lazily initializes the [_constraints], which is needed to compare two

  /// states for overlap.

  ///

  /// We do this lazily because the calculation is a bit slow, and is only

  /// needed when we have two states with the same score.

      } else {

      }

    }

        if (constraint != null) {

        }

      }

    }

  }

  /// Lazily initializes the [_unboundConstraints], which is needed to compare

  /// two states for overlap.

  ///

  /// We do this lazily because the calculation is a bit slow, and is only

  /// needed when we have two states with the same score.

    // _ensureConstraints should be called first which initializes these.

      Set<int> disallowedValues;

          // If the unbound rule doesn't place any constraint on this bound

          // rule, we're fine.

          if (constraint == null) continue;

          // If the bound rule's value already meets the constraint it applies,

          // we don't need to track it. This way, two states that have the

          // same bound value, one of which has a satisfied constraint, are

          // still allowed to overlap.

            continue;

          }

          if (disallowedValues == null) {

          }

        }

      }

    }

  }

      var value = "?";

      }

      } else {

      }

      return value;

    }), " ");

  }

}