OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library dart_style.src.line_splitter; | 5 library dart_style.src.line_splitter; |
6 | 6 |
7 import 'dart:math' as math; | 7 import 'dart:math' as math; |
8 | 8 |
9 import 'chunk.dart'; | 9 import 'chunk.dart'; |
10 import 'debug.dart'; | 10 import 'debug.dart'; |
11 import 'line_prefix.dart'; | 11 import 'line_prefix.dart'; |
12 | 12 |
13 /// The number of spaces in a single level of indentation. | 13 /// The number of spaces in a single level of indentation. |
14 const SPACES_PER_INDENT = 2; | 14 const spacesPerIndent = 2; |
15 | 15 |
16 /// The number of indentation levels in a single level of expression nesting. | 16 /// The number of indentation levels in a single level of expression nesting. |
17 const INDENTS_PER_NEST = 2; | 17 const indentsPerNest = 2; |
18 | 18 |
19 /// Cost or indent value used to indication no solution could be found. | 19 /// Cost or indent value used to indication no solution could be found. |
20 const INVALID_SPLITS = -1; | 20 const invalidSplits = -1; |
21 | 21 |
22 // TODO(rnystrom): This needs to be updated to take into account how it works | 22 // TODO(rnystrom): This needs to be updated to take into account how it works |
23 // now. | 23 // now. |
24 /// Takes a series of [Chunk]s and determines the best way to split them into | 24 /// Takes a series of [Chunk]s and determines the best way to split them into |
25 /// lines of output that fit within the page width (if possible). | 25 /// lines of output that fit within the page width (if possible). |
26 /// | 26 /// |
27 /// Trying all possible combinations is exponential in the number of | 27 /// Trying all possible combinations is exponential in the number of |
28 /// [SplitParam]s and expression nesting levels both of which can be quite large | 28 /// [SplitParam]s and expression nesting levels both of which can be quite large |
29 /// with things like long method chains containing function literals, lots of | 29 /// with things like long method chains containing function literals, lots of |
30 /// named parameters, etc. To tame that, this uses dynamic programming. The | 30 /// named parameters, etc. To tame that, this uses dynamic programming. The |
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
93 /// Convert the line to a [String] representation. | 93 /// Convert the line to a [String] representation. |
94 /// | 94 /// |
95 /// It will determine how best to split it into multiple lines of output and | 95 /// It will determine how best to split it into multiple lines of output and |
96 /// return a single string that may contain one or more newline characters. | 96 /// return a single string that may contain one or more newline characters. |
97 void apply(StringBuffer buffer) { | 97 void apply(StringBuffer buffer) { |
98 if (debugFormatter) dumpLine(_chunks, _indent); | 98 if (debugFormatter) dumpLine(_chunks, _indent); |
99 | 99 |
100 var splits = _findBestSplits(new LinePrefix()); | 100 var splits = _findBestSplits(new LinePrefix()); |
101 | 101 |
102 // Write each chunk and the split after it. | 102 // Write each chunk and the split after it. |
103 buffer.write(" " * (_indent * SPACES_PER_INDENT)); | 103 buffer.write(" " * (_indent * spacesPerIndent)); |
104 for (var i = 0; i < _chunks.length - 1; i++) { | 104 for (var i = 0; i < _chunks.length - 1; i++) { |
105 var chunk = _chunks[i]; | 105 var chunk = _chunks[i]; |
106 | 106 |
107 buffer.write(chunk.text); | 107 buffer.write(chunk.text); |
108 | 108 |
109 if (splits.shouldSplitAt(i)) { | 109 if (splits.shouldSplitAt(i)) { |
110 buffer.write(_lineEnding); | 110 buffer.write(_lineEnding); |
111 if (chunk.isDouble) buffer.write(_lineEnding); | 111 if (chunk.isDouble) buffer.write(_lineEnding); |
112 | 112 |
113 var indent = chunk.indent + splits.getNesting(i); | 113 var indent = chunk.indent + splits.getNesting(i); |
114 buffer.write(" " * (indent * SPACES_PER_INDENT)); | 114 buffer.write(" " * (indent * spacesPerIndent)); |
115 | 115 |
116 // Should have a valid set of splits when we get here. | 116 // Should have a valid set of splits when we get here. |
117 assert(indent != INVALID_SPLITS); | 117 assert(indent != invalidSplits); |
118 } else { | 118 } else { |
119 if (chunk.spaceWhenUnsplit) buffer.write(" "); | 119 if (chunk.spaceWhenUnsplit) buffer.write(" "); |
120 } | 120 } |
121 } | 121 } |
122 | 122 |
123 // Write the final chunk without any trailing newlines. | 123 // Write the final chunk without any trailing newlines. |
124 buffer.write(_chunks.last.text); | 124 buffer.write(_chunks.last.text); |
125 } | 125 } |
126 | 126 |
127 /// Finds the best set of splits to apply to the remainder of the line | 127 /// Finds the best set of splits to apply to the remainder of the line |
128 /// following [prefix]. | 128 /// following [prefix]. |
129 SplitSet _findBestSplits(LinePrefix prefix) { | 129 SplitSet _findBestSplits(LinePrefix prefix) { |
130 // Use the memoized result if we have it. | 130 // Use the memoized result if we have it. |
131 if (_bestSplits.containsKey(prefix)) return _bestSplits[prefix]; | 131 if (_bestSplits.containsKey(prefix)) return _bestSplits[prefix]; |
132 | 132 |
133 var indent = prefix.getNextLineIndent(_chunks, _indent); | 133 var indent = prefix.getNextLineIndent(_chunks, _indent); |
134 | 134 |
135 var bestSplits; | 135 var bestSplits; |
136 var lowestCost; | 136 var lowestCost; |
137 | 137 |
138 // If there are no required splits, consider not splitting any of the soft | 138 // If there are no required splits, consider not splitting any of the soft |
139 // splits (if there are any) as one possible solution. | 139 // splits (if there are any) as one possible solution. |
140 if (!_suffixContainsHardSplits(prefix)) { | 140 if (!_suffixContainsHardSplits(prefix)) { |
141 var splits = new SplitSet(); | 141 var splits = new SplitSet(); |
142 var cost = _evaluateCost(prefix, indent, splits); | 142 var cost = _evaluateCost(prefix, indent, splits); |
143 | 143 |
144 if (cost != INVALID_SPLITS) { | 144 if (cost != invalidSplits) { |
145 bestSplits = splits; | 145 bestSplits = splits; |
146 lowestCost = cost; | 146 lowestCost = cost; |
147 | 147 |
148 // If we fit the whole suffix without any splitting, that's going to be | 148 // If we fit the whole suffix without any splitting, that's going to be |
149 // the best solution, so don't bother trying any others. | 149 // the best solution, so don't bother trying any others. |
150 if (cost < Cost.OVERFLOW_CHAR) { | 150 if (cost < Cost.overflowChar) { |
151 _bestSplits[prefix] = bestSplits; | 151 _bestSplits[prefix] = bestSplits; |
152 return bestSplits; | 152 return bestSplits; |
153 } | 153 } |
154 } | 154 } |
155 } | 155 } |
156 | 156 |
157 // For each split in the suffix, calculate the best cost where that is the | 157 // For each split in the suffix, calculate the best cost where that is the |
158 // first split applied. This recurses so that for each split, we consider | 158 // first split applied. This recurses so that for each split, we consider |
159 // all of the possible sets of splits *after* it and determine the best | 159 // all of the possible sets of splits *after* it and determine the best |
160 // cost subset out of all of those. | 160 // cost subset out of all of those. |
161 var skippedParams = new Set(); | 161 var skippedParams = new Set(); |
162 | 162 |
163 var length = indent * SPACES_PER_INDENT; | 163 var length = indent * spacesPerIndent; |
164 | 164 |
165 // Don't consider the last chunk, since there's no point in splitting on it. | 165 // Don't consider the last chunk, since there's no point in splitting on it. |
166 for (var i = prefix.length; i < _chunks.length - 1; i++) { | 166 for (var i = prefix.length; i < _chunks.length - 1; i++) { |
167 var split = _chunks[i]; | 167 var split = _chunks[i]; |
168 | 168 |
169 // We must skip over this chunk if it cannot be split. | 169 // We must skip over this chunk if it cannot be split. |
170 if (_canSplit(prefix, split, skippedParams)) { | 170 if (_canSplit(prefix, split, skippedParams)) { |
171 var splitParams = _getSplitParams(prefix, i, split); | 171 var splitParams = _getSplitParams(prefix, i, split); |
172 | 172 |
173 // Find all the params we did *not* split in the prefix that appear in | 173 // Find all the params we did *not* split in the prefix that appear in |
(...skipping 16 matching lines...) Expand all Loading... |
190 | 190 |
191 // If it wasn't possible to split the suffix given this nesting stack, | 191 // If it wasn't possible to split the suffix given this nesting stack, |
192 // skip it. | 192 // skip it. |
193 if (remaining == null) continue; | 193 if (remaining == null) continue; |
194 | 194 |
195 var splits = remaining.add(i, longerPrefix.nestingIndent); | 195 var splits = remaining.add(i, longerPrefix.nestingIndent); |
196 var cost = _evaluateCost(prefix, indent, splits); | 196 var cost = _evaluateCost(prefix, indent, splits); |
197 | 197 |
198 // If the suffix is invalid (because of a mis-matching multisplit), | 198 // If the suffix is invalid (because of a mis-matching multisplit), |
199 // skip it. | 199 // skip it. |
200 if (cost == INVALID_SPLITS) continue; | 200 if (cost == invalidSplits) continue; |
201 | 201 |
202 if (lowestCost == null || | 202 if (lowestCost == null || |
203 cost < lowestCost || | 203 cost < lowestCost || |
204 (cost == lowestCost && splits.weight > bestSplits.weight)) { | 204 (cost == lowestCost && splits.weight > bestSplits.weight)) { |
205 lowestCost = cost; | 205 lowestCost = cost; |
206 bestSplits = splits; | 206 bestSplits = splits; |
207 } | 207 } |
208 } | 208 } |
209 } | 209 } |
210 | 210 |
211 // If we go past the end of the page and we've already found a solution | 211 // If we go past the end of the page and we've already found a solution |
212 // that fits, then no other solution that involves overflowing will beat | 212 // that fits, then no other solution that involves overflowing will beat |
213 // that, so stop. | 213 // that, so stop. |
214 length += split.text.length; | 214 length += split.text.length; |
215 if (split.spaceWhenUnsplit) length++; | 215 if (split.spaceWhenUnsplit) length++; |
216 if (length > _pageWidth && | 216 if (length > _pageWidth && |
217 lowestCost != null && | 217 lowestCost != null && |
218 lowestCost < Cost.OVERFLOW_CHAR) { | 218 lowestCost < Cost.overflowChar) { |
219 break; | 219 break; |
220 } | 220 } |
221 | 221 |
222 // If we can't leave this split unsplit (because it's hard or has a | 222 // If we can't leave this split unsplit (because it's hard or has a |
223 // param that the prefix already forced to split), then stop. | 223 // param that the prefix already forced to split), then stop. |
224 if (split.isHardSplit) break; | 224 if (split.isHardSplit) break; |
225 if (prefix.splitParams.contains(split.param)) break; | 225 if (prefix.splitParams.contains(split.param)) break; |
226 | 226 |
227 skippedParams.add(split.param); | 227 skippedParams.add(split.param); |
228 } | 228 } |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
322 } | 322 } |
323 | 323 |
324 /// Evaluates the cost (i.e. the relative "badness") of splitting the line | 324 /// Evaluates the cost (i.e. the relative "badness") of splitting the line |
325 /// into [lines] physical lines based on the current set of params. | 325 /// into [lines] physical lines based on the current set of params. |
326 int _evaluateCost(LinePrefix prefix, int indent, SplitSet splits) { | 326 int _evaluateCost(LinePrefix prefix, int indent, SplitSet splits) { |
327 assert(splits != null); | 327 assert(splits != null); |
328 | 328 |
329 // Calculate the length of each line and apply the cost of any spans that | 329 // Calculate the length of each line and apply the cost of any spans that |
330 // get split. | 330 // get split. |
331 var cost = 0; | 331 var cost = 0; |
332 var length = indent * SPACES_PER_INDENT; | 332 var length = indent * spacesPerIndent; |
333 | 333 |
334 var params = new Set(); | 334 var params = new Set(); |
335 | 335 |
336 var splitIndexes = []; | 336 var splitIndexes = []; |
337 | 337 |
338 endLine() { | 338 endLine() { |
339 // Punish lines that went over the length. We don't rule these out | 339 // Punish lines that went over the length. We don't rule these out |
340 // completely because it may be that the only solution still goes over | 340 // completely because it may be that the only solution still goes over |
341 // (for example with long string literals). | 341 // (for example with long string literals). |
342 if (length > _pageWidth) { | 342 if (length > _pageWidth) { |
343 cost += (length - _pageWidth) * Cost.OVERFLOW_CHAR; | 343 cost += (length - _pageWidth) * Cost.overflowChar; |
344 } | 344 } |
345 } | 345 } |
346 | 346 |
347 for (var i = prefix.length; i < _chunks.length; i++) { | 347 for (var i = prefix.length; i < _chunks.length; i++) { |
348 var chunk = _chunks[i]; | 348 var chunk = _chunks[i]; |
349 | 349 |
350 length += chunk.text.length; | 350 length += chunk.text.length; |
351 | 351 |
352 if (i < _chunks.length - 1) { | 352 if (i < _chunks.length - 1) { |
353 if (splits.shouldSplitAt(i)) { | 353 if (splits.shouldSplitAt(i)) { |
354 endLine(); | 354 endLine(); |
355 splitIndexes.add(i); | 355 splitIndexes.add(i); |
356 | 356 |
357 if (chunk.param != null && !params.contains(chunk.param)) { | 357 if (chunk.param != null && !params.contains(chunk.param)) { |
358 // Don't double-count params if multiple splits share the same | 358 // Don't double-count params if multiple splits share the same |
359 // param. | 359 // param. |
360 // TODO(rnystrom): Is this needed? Can we actually let splits that | 360 // TODO(rnystrom): Is this needed? Can we actually let splits that |
361 // share a param accumulate cost? | 361 // share a param accumulate cost? |
362 params.add(chunk.param); | 362 params.add(chunk.param); |
363 cost += chunk.param.cost; | 363 cost += chunk.param.cost; |
364 } | 364 } |
365 | 365 |
366 // Start the new line. | 366 // Start the new line. |
367 length = (chunk.indent + splits.getNesting(i)) * SPACES_PER_INDENT; | 367 length = (chunk.indent + splits.getNesting(i)) * spacesPerIndent; |
368 } else { | 368 } else { |
369 if (chunk.spaceWhenUnsplit) length++; | 369 if (chunk.spaceWhenUnsplit) length++; |
370 } | 370 } |
371 } | 371 } |
372 } | 372 } |
373 | 373 |
374 // See which spans got split. We avoid iterators here for performance. | 374 // See which spans got split. We avoid iterators here for performance. |
375 for (var i = 0; i < _spans.length; i++) { | 375 for (var i = 0; i < _spans.length; i++) { |
376 var span = _spans[i]; | 376 var span = _spans[i]; |
377 for (var j = 0; j < splitIndexes.length; j++) { | 377 for (var j = 0; j < splitIndexes.length; j++) { |
(...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
453 var result = []; | 453 var result = []; |
454 for (var i = 0; i < _splitNesting.length; i++) { | 454 for (var i = 0; i < _splitNesting.length; i++) { |
455 if (_splitNesting[i] != null) { | 455 if (_splitNesting[i] != null) { |
456 result.add("$i:${_splitNesting[i]}"); | 456 result.add("$i:${_splitNesting[i]}"); |
457 } | 457 } |
458 } | 458 } |
459 | 459 |
460 return result.join(" "); | 460 return result.join(" "); |
461 } | 461 } |
462 } | 462 } |
OLD | NEW |