Optimize splitting lines with many rules.

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 '../rule/rule.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
@@ skipping 204 matching lines @@
     }
 
     _ensureConstraints();
     other._ensureConstraints();
     if (_constraints.length != other._constraints.length) return false;
 
     for (var rule in _constraints.keys) {
       if (_constraints[rule] != other._constraints[rule]) return false;
     }
 
+    _ensureUnboundConstraints();
+    other._ensureUnboundConstraints();
     if (_unboundConstraints.length != other._unboundConstraints.length) {
       return false;
     }
 
     for (var rule in _unboundConstraints.keys) {
       var disallowed = _unboundConstraints[rule];
       var otherDisallowed = other._unboundConstraints[rule];
 
       if (disallowed.length != otherDisallowed.length) return false;
       for (var value in disallowed) {
@@ skipping 158 matching lines @@
   /// 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.
   bool _addLiveRules(Rule rule) {
     if (rule == null) return false;
     if (rule is HardSplitRule) return false;
 
     var added = false;
     for (var constrained in rule.allConstrainedRules) {
-      // The rule may constrain some other rule that was already hardened and
-      // discarded. In that case, we can ignore it.
-      if (constrained.index == null) continue;
-
       if (_ruleValues.contains(constrained)) continue;
 
       _liveRules.add(constrained);
       added = true;
     }
 
     return added;
   }
 
   /// Lazily initializes the [_boundInUnboundLines], which is needed to compare
@@ skipping 31 matching lines @@
   }
 
   /// 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.
   void _ensureConstraints() {
     if (_constraints != null) return;
 
-    var unboundRules = [];
-    var boundRules = [];
+    _unboundRules = new Set();
+    _boundRules = new Set();
 
     for (var rule in _splitter.rules) {
       if (_ruleValues.contains(rule)) {
-        boundRules.add(rule);
+        _boundRules.add(rule);
       } else {
-        unboundRules.add(rule);
+        _unboundRules.add(rule);
       }
     }
 
     _constraints = {};

[kevmoo, 2015/11/09 23:40:46]

QQ: does order matter here? Would using HashMap from dart:collection improve
perf?

[Bob Nystrom, 2015/11/10 20:08:24]

Nope. No measurable improvement.

 
-    for (var unbound in unboundRules) {
-      for (var bound in boundRules) {
+    for (var bound in _boundRules) {
+      for (var unbound in bound.constrainedRules) {
+        if (!_unboundRules.contains(unbound)) continue;
+
         var value = _ruleValues.getValue(bound);
         var constraint = bound.constrain(value, unbound);
         if (constraint != null) {
           _constraints[unbound] = constraint;
         }
       }
     }
+  }
+
+  /// 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.
+  void _ensureUnboundConstraints() {
+    if (_unboundConstraints != null) return;
+
+    // _ensureConstraints should be called first which initializes these.
+    assert(_boundRules != null);
+    assert(_unboundRules != null);
 
     _unboundConstraints = {};

[kevmoo, 2015/11/09 23:40:46]

ditto RE HashMap

[Bob Nystrom, 2015/11/10 20:08:24]

Acknowledged.

 
-    for (var unbound in unboundRules) {
+    for (var unbound in _unboundRules) {
       var disallowedValues;
 
-      for (var value = 0; value < unbound.numValues; value++) {
-        for (var j = 0; j < boundRules.length; j++) {
-          var bound = boundRules[j];
+      for (var bound in unbound.constrainedRules) {
+        if (!_boundRules.contains(bound)) continue;
+
+        var boundValue = _ruleValues.getValue(bound);
+
+        for (var value = 0; value < unbound.numValues; value++) {
           var constraint = unbound.constrain(value, bound);
 
           // 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.
-          var boundValue = _ruleValues.getValue(bound);
           if (constraint == boundValue) continue;
           if (constraint == -1 && boundValue != 0) continue;
 
           if (disallowedValues == null) {
             disallowedValues = new Set();
             _unboundConstraints[unbound] = disallowedValues;
           }
 
           disallowedValues.add(value);
         }
@@ skipping 24 matching lines @@
 
     buffer.write("   \$${splits.cost}");
 
     if (overflowChars > 0) buffer.write(" (${overflowChars} over)");
     if (!_isComplete) buffer.write(" (incomplete)");
     if (splits == null) buffer.write(" invalid");
 
     return buffer.toString();
   }
 }