| 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.line_splitting.solve_state; | |
| 6 | |
| 7 import '../debug.dart' as debug; | |
| 8 import '../rule/rule.dart'; | |
| 9 import 'line_splitter.dart'; | |
| 10 import 'rule_set.dart'; | |
| 11 | |
| 12 /// A possibly incomplete solution in the line splitting search space. | |
| 13 /// | |
| 14 /// A single [SolveState] binds some subset of the rules to values while | |
| 15 /// leaving the rest unbound. If every rule is bound, the solve state describes | |
| 16 /// a complete solution to the line splitting problem. Even if rules are | |
| 17 /// unbound, a state can also usually be used as a solution by treating all | |
| 18 /// unbound rules as unsplit. (The usually is because a state that constrains | |
| 19 /// an unbound rule to split can't be used with that rule unsplit.) | |
| 20 /// | |
| 21 /// From a given solve state, we can explore the search tree to more refined | |
| 22 /// solve states by producing new ones that add more bound rules to the current | |
| 23 /// state. | |
| 24 class SolveState { | |
| 25 final LineSplitter _splitter; | |
| 26 final RuleSet _ruleValues; | |
| 27 | |
| 28 /// The unbound rules in this state that can be bound to produce new more | |
| 29 /// refined states. | |
| 30 /// | |
| 31 /// Keeping this set small is the key to make the entire line splitter | |
| 32 /// perform well. If we consider too make rules at each state, our | |
| 33 /// exploration of the solution space is too branchy and we waste time on | |
| 34 /// dead end solutions. | |
| 35 /// | |
| 36 /// Here is the key insight. The line splitter treats any unbound rule as | |
| 37 /// being unsplit. This means refining a solution always means taking a rule | |
| 38 /// that is unsplit and making it split. That monotonically increases the | |
| 39 /// cost, but may help fit the solution inside the page. | |
| 40 /// | |
| 41 /// We want to keep the cost low, so the only reason to consider making a | |
| 42 /// rule split is if it reduces an overflowing line. It's also the case that | |
| 43 /// splitting an earlier rule will often reshuffle the rest of the line. | |
| 44 /// | |
| 45 /// Taking that into account, the only rules we consider binding to extend a | |
| 46 /// solve state are *unbound rules inside the first line that is overflowing*. | |
| 47 /// Even if a line has dozens of rules, this generally keeps the branching | |
| 48 /// down to a few. It also means rules inside lines that already fit are | |
| 49 /// never touched. | |
| 50 /// | |
| 51 /// There is one other set of rules that go in here. Sometimes a bound rule | |
| 52 /// in the solve state constrains some other unbound rule to split. In that | |
| 53 /// case, we also consider that active so we know to not leave it at zero. | |
| 54 final _liveRules = new Set<Rule>(); | |
| 55 | |
| 56 /// The set of splits chosen for this state. | |
| 57 SplitSet get splits => _splits; | |
| 58 SplitSet _splits; | |
| 59 | |
| 60 /// The number of characters that do not fit inside the page with this set of | |
| 61 /// splits. | |
| 62 int get overflowChars => _overflowChars; | |
| 63 int _overflowChars; | |
| 64 | |
| 65 /// Whether we can treat this state as a complete solution by leaving its | |
| 66 /// unbound rules unsplit. | |
| 67 /// | |
| 68 /// This is generally true but will be false if the state contains any | |
| 69 /// unbound rules that are constrained to not be zero by other bound rules. | |
| 70 /// This avoids picking a solution that leaves those rules at zero when they | |
| 71 /// aren't allowed to be. | |
| 72 bool _isComplete = true; | |
| 73 | |
| 74 /// The constraints the bound rules in this state have on the remaining | |
| 75 /// unbound rules. | |
| 76 Map<Rule, int> _constraints; | |
| 77 | |
| 78 /// The bound rules that appear inside lines also containing unbound rules. | |
| 79 /// | |
| 80 /// By appearing in the same line, it means these bound rules may affect the | |
| 81 /// results of binding those unbound rules. This is used to tell if two | |
| 82 /// states may diverge by binding unbound rules or not. | |
| 83 Set<Rule> _boundRulesInUnboundLines; | |
| 84 | |
| 85 SolveState(this._splitter, this._ruleValues) { | |
| 86 _calculateSplits(); | |
| 87 _calculateCost(); | |
| 88 } | |
| 89 | |
| 90 /// Gets the value to use for [rule], either the bound value or `0` if it | |
| 91 /// isn't bound. | |
| 92 int getValue(Rule rule) { | |
| 93 if (rule is HardSplitRule) return 0; | |
| 94 | |
| 95 return _ruleValues.getValue(rule); | |
| 96 } | |
| 97 | |
| 98 /// Returns `true` if this state is a better solution to use as the final | |
| 99 /// result than [other]. | |
| 100 bool isBetterThan(SolveState other) { | |
| 101 // If this state contains an unbound rule that we know can't be left | |
| 102 // unsplit, we can't pick this as a solution. | |
| 103 if (!_isComplete) return false; | |
| 104 | |
| 105 // Anything is better than nothing. | |
| 106 if (other == null) return true; | |
| 107 | |
| 108 // Prefer the solution that fits the most in the page. | |
| 109 if (overflowChars != other.overflowChars) { | |
| 110 return overflowChars < other.overflowChars; | |
| 111 } | |
| 112 | |
| 113 // Otherwise, prefer the best cost. | |
| 114 return splits.cost < other.splits.cost; | |
| 115 } | |
| 116 | |
| 117 /// Determines if this state "overlaps" [other]. | |
| 118 /// | |
| 119 /// Two states overlap if they currently have the same score and we can tell | |
| 120 /// for certain that they won't diverge as their unbound rules are bound. If | |
| 121 /// that's the case, then whichever state is better now (based on their | |
| 122 /// currently bound rule values) is the one that will always win, regardless | |
| 123 /// of how they get expanded. | |
| 124 /// | |
| 125 /// In other words, their entire expanded solution trees also overlap. In | |
| 126 /// that case, there's no point in expanding both, so we can just pick the | |
| 127 /// winner now and discard the other. | |
| 128 /// | |
| 129 /// For this to be true, we need to prove that binding an unbound rule won't | |
| 130 /// affect one state differently from the other. We have to show that they | |
| 131 /// are parallel. | |
| 132 /// | |
| 133 /// Two things could cause this *not* to be the case. | |
| 134 /// | |
| 135 /// 1. If one state's bound rules place different constraints on the unbound | |
| 136 /// rules than the other. | |
| 137 /// | |
| 138 /// 2. If one state's different bound rules are in the same line as an | |
| 139 /// unbound rule. That affects the indentation and length of the line, | |
| 140 /// which affects the context where the unbound rule is being chosen. | |
| 141 /// | |
| 142 /// If neither of these is the case, the states overlap. Returns `<0` if this | |
| 143 /// state is better, or `>0` if [other] wins. If the states do not overlap, | |
| 144 /// returns `0`. | |
| 145 int compareOverlap(SolveState other) { | |
| 146 if (!_isOverlapping(other)) return 0; | |
| 147 | |
| 148 // They do overlap, so see which one wins. | |
| 149 for (var rule in _splitter.rules) { | |
| 150 var value = _ruleValues.getValue(rule); | |
| 151 var otherValue = other._ruleValues.getValue(rule); | |
| 152 | |
| 153 if (value != otherValue) return value.compareTo(otherValue); | |
| 154 } | |
| 155 | |
| 156 // The way SolveStates are expanded should guarantee that we never generate | |
| 157 // the exact same state twice. Getting here implies that that failed. | |
| 158 throw "unreachable"; | |
| 159 } | |
| 160 | |
| 161 /// Enqueues more solve states to consider based on this one. | |
| 162 /// | |
| 163 /// For each unbound rule in this state that occurred in the first long line, | |
| 164 /// enqueue solve states that bind that rule to each value it can have and | |
| 165 /// bind all previous rules to zero. (In other words, try all subsolutions | |
| 166 /// where that rule becomes the first new rule to split at.) | |
| 167 void expand() { | |
| 168 var unsplitRules = _ruleValues.clone(); | |
| 169 | |
| 170 // Walk down the rules looking for unbound ones to try. | |
| 171 var triedRules = 0; | |
| 172 for (var rule in _splitter.rules) { | |
| 173 if (_liveRules.contains(rule)) { | |
| 174 // We found one worth trying, so try all of its values. | |
| 175 for (var value = 1; value < rule.numValues; value++) { | |
| 176 var boundRules = unsplitRules.clone(); | |
| 177 | |
| 178 var mustSplitRules; | |
| 179 var valid = boundRules.tryBind(_splitter.rules, rule, value, (rule) { | |
| 180 if (mustSplitRules == null) mustSplitRules = []; | |
| 181 mustSplitRules.add(rule); | |
| 182 }); | |
| 183 | |
| 184 // Make sure we don't violate the constraints of the bound rules. | |
| 185 if (!valid) continue; | |
| 186 | |
| 187 var state = new SolveState(_splitter, boundRules); | |
| 188 | |
| 189 // If some unbound rules are constrained to split, remember that. | |
| 190 if (mustSplitRules != null) { | |
| 191 state._isComplete = false; | |
| 192 state._liveRules.addAll(mustSplitRules); | |
| 193 } | |
| 194 | |
| 195 _splitter.enqueue(state); | |
| 196 } | |
| 197 | |
| 198 // Stop once we've tried all of the ones we can. | |
| 199 if (++triedRules == _liveRules.length) break; | |
| 200 } | |
| 201 | |
| 202 // Fill in previous unbound rules with zero. | |
| 203 if (!_ruleValues.contains(rule)) { | |
| 204 // Pass a dummy callback because zero will never fail. (If it would | |
| 205 // have, that rule would already be bound to some other value.) | |
| 206 if (!unsplitRules.tryBind(_splitter.rules, rule, 0, (_) {})) { | |
| 207 break; | |
| 208 } | |
| 209 } | |
| 210 } | |
| 211 } | |
| 212 | |
| 213 /// Returns `true` if [other] overlaps this state. | |
| 214 bool _isOverlapping(SolveState other) { | |
| 215 _ensureOverlapFields(); | |
| 216 other._ensureOverlapFields(); | |
| 217 | |
| 218 // Lines that contain both bound and unbound rules must have the same | |
| 219 // bound values. | |
| 220 if (_boundRulesInUnboundLines.length != | |
| 221 other._boundRulesInUnboundLines.length) { | |
| 222 return false; | |
| 223 } | |
| 224 | |
| 225 for (var rule in _boundRulesInUnboundLines) { | |
| 226 if (!other._boundRulesInUnboundLines.contains(rule)) return false; | |
| 227 if (_ruleValues.getValue(rule) != other._ruleValues.getValue(rule)) { | |
| 228 return false; | |
| 229 } | |
| 230 } | |
| 231 | |
| 232 if (_constraints.length != other._constraints.length) return false; | |
| 233 | |
| 234 for (var rule in _constraints.keys) { | |
| 235 if (_constraints[rule] != other._constraints[rule]) return false; | |
| 236 } | |
| 237 | |
| 238 return true; | |
| 239 } | |
| 240 | |
| 241 /// Calculates the [SplitSet] for this solve state, assuming any unbound | |
| 242 /// rules are set to zero. | |
| 243 void _calculateSplits() { | |
| 244 // Figure out which expression nesting levels got split and need to be | |
| 245 // assigned columns. | |
| 246 var usedNestingLevels = new Set(); | |
| 247 for (var i = 0; i < _splitter.chunks.length - 1; i++) { | |
| 248 var chunk = _splitter.chunks[i]; | |
| 249 if (chunk.rule.isSplit(getValue(chunk.rule), chunk)) { | |
| 250 usedNestingLevels.add(chunk.nesting); | |
| 251 chunk.nesting.clearTotalUsedIndent(); | |
| 252 } | |
| 253 } | |
| 254 | |
| 255 for (var nesting in usedNestingLevels) { | |
| 256 nesting.refreshTotalUsedIndent(usedNestingLevels); | |
| 257 } | |
| 258 | |
| 259 _splits = new SplitSet(_splitter.chunks.length); | |
| 260 for (var i = 0; i < _splitter.chunks.length - 1; i++) { | |
| 261 var chunk = _splitter.chunks[i]; | |
| 262 if (chunk.rule.isSplit(getValue(chunk.rule), chunk)) { | |
| 263 var indent = 0; | |
| 264 if (!chunk.flushLeftAfter) { | |
| 265 // Add in the chunk's indent. | |
| 266 indent = _splitter.blockIndentation + chunk.indent; | |
| 267 | |
| 268 // And any expression nesting. | |
| 269 indent += chunk.nesting.totalUsedIndent; | |
| 270 } | |
| 271 | |
| 272 _splits.add(i, indent); | |
| 273 } | |
| 274 } | |
| 275 } | |
| 276 | |
| 277 /// Evaluates the cost (i.e. the relative "badness") of splitting the line | |
| 278 /// into [lines] physical lines based on the current set of rules. | |
| 279 void _calculateCost() { | |
| 280 assert(_splits != null); | |
| 281 | |
| 282 // Calculate the length of each line and apply the cost of any spans that | |
| 283 // get split. | |
| 284 var cost = 0; | |
| 285 _overflowChars = 0; | |
| 286 | |
| 287 var length = _splitter.firstLineIndent; | |
| 288 | |
| 289 // The unbound rules in use by the current line. This will be null after | |
| 290 // the first long line has completed. | |
| 291 var currentLineRules = []; | |
| 292 | |
| 293 endLine(int end) { | |
| 294 // Track lines that went over the length. It is only rules contained in | |
| 295 // long lines that we may want to split. | |
| 296 if (length > _splitter.writer.pageWidth) { | |
| 297 _overflowChars += length - _splitter.writer.pageWidth; | |
| 298 | |
| 299 // Only try rules that are in the first long line, since we know at | |
| 300 // least one of them *will* be split. | |
| 301 if (currentLineRules != null && currentLineRules.isNotEmpty) { | |
| 302 _liveRules.addAll(currentLineRules); | |
| 303 currentLineRules = null; | |
| 304 } | |
| 305 } else { | |
| 306 // The line fit, so don't keep track of its rules. | |
| 307 if (currentLineRules != null) { | |
| 308 currentLineRules.clear(); | |
| 309 } | |
| 310 } | |
| 311 } | |
| 312 | |
| 313 // The set of spans that contain chunks that ended up splitting. We store | |
| 314 // these in a set so a span's cost doesn't get double-counted if more than | |
| 315 // one split occurs in it. | |
| 316 var splitSpans = new Set(); | |
| 317 | |
| 318 for (var i = 0; i < _splitter.chunks.length; i++) { | |
| 319 var chunk = _splitter.chunks[i]; | |
| 320 | |
| 321 length += chunk.text.length; | |
| 322 | |
| 323 // Ignore the split after the last chunk. | |
| 324 if (i == _splitter.chunks.length - 1) break; | |
| 325 | |
| 326 if (_splits.shouldSplitAt(i)) { | |
| 327 endLine(i); | |
| 328 | |
| 329 splitSpans.addAll(chunk.spans); | |
| 330 | |
| 331 // Include the cost of the nested block. | |
| 332 if (chunk.blockChunks.isNotEmpty) { | |
| 333 cost += | |
| 334 _splitter.writer.formatBlock(chunk, _splits.getColumn(i)).cost; | |
| 335 } | |
| 336 | |
| 337 // Start the new line. | |
| 338 length = _splits.getColumn(i); | |
| 339 } else { | |
| 340 if (chunk.spaceWhenUnsplit) length++; | |
| 341 | |
| 342 // Include the nested block inline, if any. | |
| 343 length += chunk.unsplitBlockLength; | |
| 344 | |
| 345 // If we might be in the first overly long line, keep track of any | |
| 346 // unbound rules we encounter. These are ones that we'll want to try to | |
| 347 // bind to shorten the long line. | |
| 348 if (currentLineRules != null && | |
| 349 chunk.rule != null && | |
| 350 !chunk.isHardSplit && | |
| 351 !_ruleValues.contains(chunk.rule)) { | |
| 352 currentLineRules.add(chunk.rule); | |
| 353 } | |
| 354 } | |
| 355 } | |
| 356 | |
| 357 // Add the costs for the rules that split. | |
| 358 _ruleValues.forEach(_splitter.rules, (rule, value) { | |
| 359 // A rule may be bound to zero if another rule constrains it to not split. | |
| 360 if (value != 0) cost += rule.cost; | |
| 361 }); | |
| 362 | |
| 363 // Add the costs for the spans containing splits. | |
| 364 for (var span in splitSpans) cost += span.cost; | |
| 365 | |
| 366 // Finish the last line. | |
| 367 endLine(_splitter.chunks.length); | |
| 368 | |
| 369 _splits.setCost(cost); | |
| 370 } | |
| 371 | |
| 372 /// Lazily initializes the fields needed to compare two states for overlap. | |
| 373 /// | |
| 374 /// We do this lazily because the calculation is a bit slow, and is only | |
| 375 /// needed when we have two states with the same score. | |
| 376 void _ensureOverlapFields() { | |
| 377 if (_constraints != null) return; | |
| 378 | |
| 379 _calculateConstraints(); | |
| 380 _calculateBoundRulesInUnboundLines(); | |
| 381 } | |
| 382 | |
| 383 /// Initializes [_constraints] with any constraints the bound rules place on | |
| 384 /// the unbound rules. | |
| 385 void _calculateConstraints() { | |
| 386 _constraints = {}; | |
| 387 | |
| 388 var unboundRules = []; | |
| 389 var boundRules = []; | |
| 390 | |
| 391 for (var rule in _splitter.rules) { | |
| 392 if (_ruleValues.contains(rule)) { | |
| 393 boundRules.add(rule); | |
| 394 } else { | |
| 395 unboundRules.add(rule); | |
| 396 } | |
| 397 } | |
| 398 | |
| 399 for (var bound in boundRules) { | |
| 400 var value = _ruleValues.getValue(bound); | |
| 401 | |
| 402 for (var unbound in unboundRules) { | |
| 403 var constraint = bound.constrain(value, unbound); | |
| 404 if (constraint != null) { | |
| 405 _constraints[unbound] = constraint; | |
| 406 } | |
| 407 } | |
| 408 } | |
| 409 } | |
| 410 | |
| 411 void _calculateBoundRulesInUnboundLines() { | |
| 412 _boundRulesInUnboundLines = new Set(); | |
| 413 | |
| 414 var boundInLine = new Set(); | |
| 415 var hasUnbound = false; | |
| 416 | |
| 417 for (var i = 0; i < _splitter.chunks.length - 1; i++) { | |
| 418 if (splits.shouldSplitAt(i)) { | |
| 419 if (hasUnbound) _boundRulesInUnboundLines.addAll(boundInLine); | |
| 420 | |
| 421 boundInLine.clear(); | |
| 422 hasUnbound = false; | |
| 423 } | |
| 424 | |
| 425 var rule = _splitter.chunks[i].rule; | |
| 426 if (rule != null && rule is! HardSplitRule) { | |
| 427 if (_ruleValues.contains(rule)) { | |
| 428 boundInLine.add(rule); | |
| 429 } else { | |
| 430 hasUnbound = true; | |
| 431 } | |
| 432 } | |
| 433 } | |
| 434 | |
| 435 if (hasUnbound) _boundRulesInUnboundLines.addAll(boundInLine); | |
| 436 } | |
| 437 | |
| 438 String toString() { | |
| 439 var buffer = new StringBuffer(); | |
| 440 | |
| 441 buffer.writeAll(_splitter.rules.map((rule) { | |
| 442 var valueLength = "${rule.fullySplitValue}".length; | |
| 443 | |
| 444 var value = "?"; | |
| 445 if (_ruleValues.contains(rule)) { | |
| 446 value = "${_ruleValues.getValue(rule)}"; | |
| 447 } | |
| 448 | |
| 449 value = value.padLeft(valueLength); | |
| 450 if (_liveRules.contains(rule)) { | |
| 451 value = debug.bold(value); | |
| 452 } else { | |
| 453 value = debug.gray(value); | |
| 454 } | |
| 455 | |
| 456 return value; | |
| 457 }), " "); | |
| 458 | |
| 459 buffer.write(" \$${splits.cost}"); | |
| 460 | |
| 461 if (overflowChars > 0) buffer.write(" (${overflowChars} over)"); | |
| 462 if (!_isComplete) buffer.write(" (incomplete)"); | |
| 463 if (splits == null) buffer.write(" invalid"); | |
| 464 | |
| 465 return buffer.toString(); | |
| 466 } | |
| 467 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1400473008:
Roll Observatory packages and add a roll script (Closed)
Base URL: git@github.com:dart-lang/observatory_pub_packages.git@master