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.line_splitting.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 | 9 | RuleSet(int numRules) : this._(new List(numRules));
|
22 | |
|
23 | 3 | RuleSet._(this._values);
|
24 | |
|
25 | | /// Returns `true` of [rule] is bound in this set.
|
26 | 2 | bool contains(Rule rule) {
|
27 | | // Treat hardened rules as implicitly bound.
|
28 | 2 | if (rule.isHardened) return true;
|
29 | |
|
30 | 6 | return _values[rule.index] != null;
|
31 | | }
|
32 | |
|
33 | | /// Gets the bound value for [rule] or [Rule.unsplit] if it is not bound.
|
34 | 3 | int getValue(Rule rule) {
|
35 | | // Hardened rules are implicitly bound.
|
36 | 5 | if (rule.isHardened) return rule.fullySplitValue;
|
37 | |
|
38 | 9 | var value = _values[rule.index];
|
39 | | if (value != null) return value;
|
40 | |
|
41 | | return Rule.unsplit;
|
42 | | }
|
43 | |
|
44 | | /// Invokes [callback] for each rule in [rules] with the rule's value, which
|
45 | | /// will be `null` if it is not bound.
|
46 | 3 | void forEach(List<Rule> rules, callback(Rule rule, int value)) {
|
47 | | var i = 0;
|
48 | 6 | for (var rule in rules) {
|
49 | 6 | var value = _values[i];
|
50 | 2 | if (value != null) callback(rule, value);
|
51 | 3 | i++;
|
52 | | }
|
53 | | }
|
54 | |
|
55 | | /// Creates a new [RuleSet] with the same bound rule values as this one.
|
56 | 8 | RuleSet clone() => new RuleSet._(_values.toList(growable: false));
|
57 | |
|
58 | | /// Binds [rule] to [value] then checks to see if that violates any
|
59 | | /// constraints.
|
60 | | ///
|
61 | | /// Returns `true` if all constraints between the bound rules are valid. Even
|
62 | | /// if not, this still modifies the [RuleSet].
|
63 | | ///
|
64 | | /// If an unbound rule gets constrained to `-1` (meaning it must split, but
|
65 | | /// can split any way it wants), invokes [onSplitRule] with it.
|
66 | 2 | bool tryBind(List<Rule> rules, Rule rule, int value, onSplitRule(Rule rule)) {
|
67 | 2 | assert(!rule.isHardened);
|
68 | |
|
69 | 6 | _values[rule.index] = value;
|
70 | |
|
71 | | // Test this rule against the other rules being bound.
|
72 | 4 | for (var other in rule.constrainedRules) {
|
73 | | var otherValue;
|
74 | | // Hardened rules are implicitly bound.
|
75 | 2 | if (other.isHardened) {
|
76 | 1 | otherValue = other.fullySplitValue;
|
77 | | } else {
|
78 | 6 | otherValue = _values[other.index];
|
79 | | }
|
80 | |
|
81 | 2 | var constraint = rule.constrain(value, other);
|
82 | |
|
83 | | if (otherValue == null) {
|
84 | | // The other rule is unbound, so see if we can constrain it eagerly to
|
85 | | // a value now.
|
86 | 2 | if (constraint == Rule.mustSplit) {
|
87 | | // If we know the rule has to split and there's only one way it can,
|
88 | | // just bind that.
|
89 | 2 | if (other.numValues == 2) {
|
90 | 1 | if (!tryBind(rules, other, 1, onSplitRule)) return false;
|
91 | | } else {
|
92 | 1 | onSplitRule(other);
|
93 | | }
|
94 | | } else if (constraint != null) {
|
95 | | // Bind the other rule to its value and recursively propagate its
|
96 | | // constraints.
|
97 | 2 | if (!tryBind(rules, other, constraint, onSplitRule)) return false;
|
98 | | }
|
99 | | } else {
|
100 | | // It's already bound, so see if the new rule's constraint disallows
|
101 | | // that value.
|
102 | 2 | if (constraint == Rule.mustSplit) {
|
103 | 0 | if (otherValue == Rule.unsplit) return false;
|
104 | | } else if (constraint != null) {
|
105 | 2 | if (otherValue != constraint) return false;
|
106 | | }
|
107 | |
|
108 | | // See if the other rule's constraint allows us to use this value.
|
109 | 2 | constraint = other.constrain(otherValue, rule);
|
110 | 2 | if (constraint == Rule.mustSplit) {
|
111 | 0 | if (value == Rule.unsplit) return false;
|
112 | | } else if (constraint != null) {
|
113 | 0 | if (value != constraint) return false;
|
114 | | }
|
115 | | }
|
116 | | }
|
117 | |
|
118 | | return true;
|
119 | | }
|
120 | |
|
121 | 0 | String toString() =>
|
122 | 0 | _values.map((value) => value == null ? "?" : value).join(" ");
|
123 | | }
|
124 | |
|
125 | | /// For each chunk, this tracks if it has been split and, if so, what the
|
126 | | /// chosen column is for the following line.
|
127 | | ///
|
128 | | /// Internally, this uses a list where each element corresponds to the column
|
129 | | /// of the chunk at that index in the chunk list, or `null` if that chunk did
|
130 | | /// not split. This had about a 10% perf improvement over using a [Set] of
|
131 | | /// splits.
|
132 | | class SplitSet {
|
133 | | List<int> _columns;
|
134 | |
|
135 | | /// The cost of the solution that led to these splits.
|
136 | 6 | int get cost => _cost;
|
137 | | int _cost;
|
138 | |
|
139 | | /// Creates a new empty split set for a line with [numChunks].
|
140 | 9 | SplitSet(int numChunks) : _columns = new List(numChunks - 1);
|
141 | |
|
142 | | /// Marks the line after chunk [index] as starting at [column].
|
143 | 2 | void add(int index, int column) {
|
144 | 4 | _columns[index] = column;
|
145 | | }
|
146 | |
|
147 | | /// Returns `true` if the chunk at [splitIndex] should be split.
|
148 | 3 | bool shouldSplitAt(int index) =>
|
149 | 15 | index < _columns.length && _columns[index] != null;
|
150 | |
|
151 | | /// Gets the zero-based starting column for the chunk at [index].
|
152 | 6 | int getColumn(int index) => _columns[index];
|
153 | |
|
154 | | /// Sets the resulting [cost] for the splits.
|
155 | | ///
|
156 | | /// This can only be called once.
|
157 | 3 | void setCost(int cost) {
|
158 | 3 | assert(_cost == null);
|
159 | 3 | _cost = cost;
|
160 | | }
|
161 | |
|
162 | 0 | String toString() {
|
163 | 0 | var result = [];
|
164 | 0 | for (var i = 0; i < _columns.length; i++) {
|
165 | 0 | if (_columns[i] != null) {
|
166 | 0 | result.add("$i:${_columns[i]}");
|
167 | | }
|
168 | | }
|
169 | |
|
170 | 0 | return result.join(" ");
|
171 | | }
|
172 | | }
|