OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. |
| 4 |
| 5 library dart_style.src.rule_set; |
| 6 |
| 7 import 'rule/rule.dart'; |
| 8 |
| 9 /// An optimized data structure for storing a set of values for some rules. |
| 10 /// |
| 11 /// This conceptually behaves roughly like a `Map<Rule, int>`, but is much |
| 12 /// faster since it avoids hashing. Instead, it assumes the line splitter has |
| 13 /// provided an ordered list of [Rule]s and that each rule's [index] field has |
| 14 /// been set to point to the rule in the list. |
| 15 /// |
| 16 /// Internally, this then just stores the values in a sparse list whose indices |
| 17 /// are the indices of the rules. |
| 18 class RuleSet { |
| 19 List<int> _values; |
| 20 |
| 21 RuleSet(int numRules) : this._(new List(numRules)); |
| 22 |
| 23 RuleSet._(this._values); |
| 24 |
| 25 /// Returns `true` of [rule] is bound in this set. |
| 26 bool contains(Rule rule) => _values[rule.index] != null; |
| 27 |
| 28 /// Gets the bound value for [rule] or `0` if it is not bound. |
| 29 int getValue(Rule rule) { |
| 30 var value = _values[rule.index]; |
| 31 if (value != null) return value; |
| 32 |
| 33 return 0; |
| 34 } |
| 35 |
| 36 /// Invokes [callback] for each rule in [rules] with the rule's value, which |
| 37 /// will be `null` if it is not bound. |
| 38 void forEach(List<Rule> rules, callback(Rule rule, int value)) { |
| 39 var i = 0; |
| 40 for (var rule in rules) { |
| 41 var value = _values[i]; |
| 42 if (value != null) callback(rule, value); |
| 43 i++; |
| 44 } |
| 45 } |
| 46 |
| 47 /// Creates a new [RuleSet] with the same bound rule values as this one. |
| 48 RuleSet clone() => new RuleSet._(_values.toList(growable: false)); |
| 49 |
| 50 /// Binds [rule] to [value] then checks to see if that violates any |
| 51 /// constraints. |
| 52 /// |
| 53 /// Returns `true` if all constraints between the bound rules are valid. Even |
| 54 /// if not, this still modifies the [RuleSet]. |
| 55 /// |
| 56 /// If an unbound rule gets constrained to `-1` (meaning it must split, but |
| 57 /// can split any way it wants), invokes [onSplitRule] with it. |
| 58 bool tryBind(List<Rule> rules, Rule rule, int value, onSplitRule(Rule rule)) { |
| 59 _values[rule.index] = value; |
| 60 |
| 61 // Test this rule against the other rules being bound. |
| 62 for (var other in rules) { |
| 63 if (rule == other) continue; |
| 64 |
| 65 var otherValue = _values[other.index]; |
| 66 var constraint = rule.constrain(value, other); |
| 67 |
| 68 if (otherValue == null) { |
| 69 // The other rule is unbound, so see if we can constrain it eagerly to |
| 70 // a value now. |
| 71 if (constraint == -1) { |
| 72 // If we know the rule has to split and there's only one way it can, |
| 73 // just bind that. |
| 74 if (other.numValues == 2) { |
| 75 if (!tryBind(rules, other, 1, onSplitRule)) return false; |
| 76 } else { |
| 77 onSplitRule(other); |
| 78 } |
| 79 } else if (constraint != null) { |
| 80 // Bind the other rule to its value and recursively propagate its |
| 81 // constraints. |
| 82 if (!tryBind(rules, other, constraint, onSplitRule)) return false; |
| 83 } |
| 84 } else { |
| 85 // It's already bound, so see if the new rule's constraint disallows |
| 86 // that value. |
| 87 if (constraint == -1) { |
| 88 if (otherValue == 0) return false; |
| 89 } else if (constraint != null) { |
| 90 if (otherValue != constraint) return false; |
| 91 } |
| 92 |
| 93 // See if the other rule's constraint allows us to use this value. |
| 94 constraint = other.constrain(otherValue, rule); |
| 95 if (constraint == -1) { |
| 96 if (value == 0) return false; |
| 97 } else if (constraint != null) { |
| 98 if (value != constraint) return false; |
| 99 } |
| 100 } |
| 101 } |
| 102 |
| 103 return true; |
| 104 } |
| 105 |
| 106 String toString() => |
| 107 _values.map((value) => value == null ? "?" : value).join(" "); |
| 108 } |
| 109 |
| 110 /// For each chunk, this tracks if it has been split and, if so, what the |
| 111 /// chosen column is for the following line. |
| 112 /// |
| 113 /// Internally, this uses a list where each element corresponds to the column |
| 114 /// of the chunk at that index in the chunk list, or `null` if that chunk did |
| 115 /// not split. This had about a 10% perf improvement over using a [Set] of |
| 116 /// splits. |
| 117 class SplitSet { |
| 118 List<int> _columns; |
| 119 |
| 120 /// The cost of the solution that led to these splits. |
| 121 int get cost => _cost; |
| 122 int _cost; |
| 123 |
| 124 /// Creates a new empty split set for a line with [numChunks]. |
| 125 SplitSet(int numChunks) : _columns = new List(numChunks - 1); |
| 126 |
| 127 /// Marks the line after chunk [index] as starting at [column]. |
| 128 void add(int index, int column) { |
| 129 _columns[index] = column; |
| 130 } |
| 131 |
| 132 /// Returns `true` if the chunk at [splitIndex] should be split. |
| 133 bool shouldSplitAt(int index) => |
| 134 index < _columns.length && _columns[index] != null; |
| 135 |
| 136 /// Gets the zero-based starting column for the chunk at [index]. |
| 137 int getColumn(int index) => _columns[index]; |
| 138 |
| 139 /// Sets the resulting [cost] for the splits. |
| 140 /// |
| 141 /// This can only be called once. |
| 142 void setCost(int cost) { |
| 143 assert(_cost == null); |
| 144 _cost = cost; |
| 145 } |
| 146 |
| 147 String toString() { |
| 148 var result = []; |
| 149 for (var i = 0; i < _columns.length; i++) { |
| 150 if (_columns[i] != null) { |
| 151 result.add("$i:${_columns[i]}"); |
| 152 } |
| 153 } |
| 154 |
| 155 return result.join(" "); |
| 156 } |
| 157 } |
OLD | NEW |