1 module format.span; 2 3 import format.chunk; 4 import format.writer; 5 6 class Span { 7 Span parent = null; 8 9 this(Span parent) { 10 this.parent = parent; 11 } 12 13 ulong getState(const ref SolveState s) const { 14 return 0; 15 } 16 17 uint getCost(const ref SolveState s) const { 18 return 10; 19 } 20 21 // lhs < rhs => rhs.opCmp(rhs) < 0 22 final int opCmp(const Span rhs) const { 23 auto lhsPtr = cast(void*) this; 24 auto rhsPtr = cast(void*) rhs; 25 26 return (lhsPtr > rhsPtr) - (lhsPtr < rhsPtr); 27 } 28 29 @trusted 30 final override size_t toHash() const { 31 return cast(size_t) cast(void*) this; 32 } 33 34 static string print(const Span span) { 35 if (span is null) { 36 return "null"; 37 } 38 39 return span.toString(); 40 } 41 42 override string toString() const { 43 import std.conv; 44 return typeid(this).toString() ~ "(" ~ print(parent) ~ ")"; 45 } 46 47 protected: 48 bool matchLevel(const Span s) const { 49 return false; 50 } 51 52 enum Split { 53 No, 54 Can, 55 Must, 56 } 57 58 uint computeIndent(const ref SolveState s, size_t i) const { 59 return s.isUsed(this) ? 1 : 0; 60 } 61 62 size_t computeAlignIndex(const ref SolveState s, size_t i) const { 63 return 0; 64 } 65 66 Split computeSplit(const ref SolveState s, size_t i) const { 67 return Split.Can; 68 } 69 } 70 71 Span getTop(Span span) { 72 Span top = span; 73 74 while (span !is null) { 75 top = span; 76 span = span.parent; 77 } 78 79 return top; 80 } 81 82 bool contains(const Span span, const Span s) { 83 if (span is null) { 84 return false; 85 } 86 87 if (span is s) { 88 return true; 89 } 90 91 return span.parent.contains(s); 92 } 93 94 bool isSameLevel(const Span a, const Span b) { 95 if (a is b) { 96 return true; 97 } 98 99 if (a !is null && a.matchLevel(b)) { 100 return true; 101 } 102 103 if (b !is null && b.matchLevel(a)) { 104 return true; 105 } 106 107 return false; 108 } 109 110 uint getIndent(const Span span, const ref SolveState s, size_t i) { 111 if (span is null) { 112 return 0; 113 } 114 115 return span.computeIndent(s, i) + span.parent.getIndent(s, i); 116 } 117 118 uint getExtraIndent(const Span span, const Span base, const ref SolveState s, 119 size_t i) { 120 if (base is null) { 121 return span.getIndent(s, i); 122 } 123 124 if (span is null || span is base || span is base.parent) { 125 return 0; 126 } 127 128 const current = span.computeIndent(s, i); 129 if (current == 0) { 130 return span.parent.getExtraIndent(base, s, i); 131 } 132 133 /** 134 * We have some extra indentation. We want to count only 135 * the indentation that has not already been accounted for 136 * in base. Doign so require to find the common ancestor 137 * between span and base. 138 */ 139 140 // Try to early bail. 141 if (span.parent is null || span.parent is base 142 || span.parent is base.parent) { 143 return current; 144 } 145 146 static uint getDepth(const Span s) { 147 return s is null ? 0 : 1 + getDepth(s.parent); 148 } 149 150 auto baseDepth = getDepth(base); 151 auto depth = getDepth(span); 152 153 static const(Span) popTo(const Span s, uint sDepth, uint target) { 154 return sDepth > target ? popTo(s.parent, sDepth - 1, target) : s; 155 } 156 157 const rebaseDepth = depth < baseDepth ? depth : baseDepth; 158 const rebase = popTo(base, baseDepth, depth); 159 if (span is rebase) { 160 return 0; 161 } 162 163 static finalize(const Span a, const Span b, const ref SolveState s, 164 size_t i) { 165 if (a is b) { 166 return 0; 167 } 168 169 return a.computeIndent(s, i) + finalize(a.parent, b.parent, s, i); 170 } 171 172 static sum(const Span a, uint aDepth, const Span b, uint bDepth, 173 const ref SolveState s, size_t i) { 174 if (aDepth == bDepth) { 175 return finalize(a, b, s, i); 176 } 177 178 if (bDepth > aDepth) { 179 return sum(a, aDepth, b.parent, bDepth - 1, s, i); 180 } 181 182 return 183 a.computeIndent(s, i) + sum(a.parent, aDepth - 1, b, bDepth, s, i); 184 } 185 186 return current + sum(span.parent, depth - 1, rebase, rebaseDepth, s, i); 187 } 188 189 size_t getAlignIndex(const Span span, const ref SolveState s, size_t i) { 190 if (span is null) { 191 return 0; 192 } 193 194 auto ci = span.computeAlignIndex(s, i); 195 if (ci > 0 && ci != i) { 196 return ci; 197 } 198 199 if (auto pi = span.parent.getAlignIndex(s, i)) { 200 return pi; 201 } 202 203 return ci; 204 } 205 206 bool canSplit(const Span span, const ref SolveState s, size_t i) { 207 if (span is null) { 208 return true; 209 } 210 211 final switch (span.computeSplit(s, i)) with (Span.Split) { 212 case No: 213 return false; 214 215 case Must: 216 return true; 217 218 case Can: 219 break; 220 } 221 222 return span.parent.canSplit(s, i); 223 } 224 225 bool mustSplit(const Span span, const ref SolveState s, size_t i) { 226 if (span is null) { 227 return false; 228 } 229 230 final switch (span.computeSplit(s, i)) with (Span.Split) { 231 case No: 232 return false; 233 234 case Must: 235 return true; 236 237 case Can: 238 return span.parent.mustSplit(s, i); 239 } 240 } 241 242 /** 243 * Span state management utilities. 244 */ 245 private mixin template CachedState() { 246 import format.rulevalues; 247 RuleValues __cachedSolveRuleValue; 248 ulong __cachedState; 249 250 final override ulong getState(const ref SolveState s) const { 251 if (__cachedSolveRuleValue == s.ruleValues) { 252 return __cachedState; 253 } 254 255 auto state = computeState(s); 256 257 auto t = cast() this; 258 t.__cachedSolveRuleValue = s.ruleValues.clone(); 259 t.__cachedState = state; 260 261 return state; 262 } 263 } 264 265 /** 266 * This span can indent multiple times. 267 */ 268 final class IndentSpan : Span { 269 uint indent; 270 271 this(Span parent, uint indent) { 272 super(parent); 273 274 this.indent = indent; 275 } 276 277 override uint computeIndent(const ref SolveState s, size_t i) const { 278 return super.computeIndent(s, i) ? indent : 0; 279 } 280 } 281 282 /** 283 * This span only has a cost when directly broken. 284 */ 285 final class PrefixSpan : Span { 286 this(Span parent) { 287 super(parent); 288 } 289 290 override uint getCost(const ref SolveState s) const { 291 return s.isUsed(this) ? 15 : 0; 292 } 293 } 294 295 /** 296 * Span that ensure breaks are aligned with the start of the span. 297 */ 298 final class AlignedSpan : Span { 299 size_t first = size_t.max; 300 301 this(Span parent) { 302 super(parent); 303 } 304 305 void alignOn(size_t i) { 306 first = i; 307 } 308 309 override size_t computeAlignIndex(const ref SolveState s, size_t i) const { 310 return first; 311 } 312 } 313 314 /** 315 * Span ensuring lists of items are formatted as expected. 316 */ 317 abstract class ListSpan : Span { 318 size_t[] elements; 319 size_t trailingSplit = size_t.max; 320 321 this(Span parent) { 322 super(parent); 323 } 324 325 final: 326 @property 327 bool hasTrailingSplit() const { 328 return trailingSplit != size_t.max; 329 } 330 331 void registerElement(size_t i) in { 332 assert(elements.length == 0 || elements[$ - 1] < i); 333 assert(!hasTrailingSplit); 334 } do { 335 elements ~= i; 336 } 337 338 void registerTrailingSplit(size_t i) in { 339 assert(elements[$ - 1] < i); 340 assert(!hasTrailingSplit); 341 } do { 342 trailingSplit = i; 343 } 344 345 bool isActive(const ref SolveState s) const { 346 return s.isSplit(elements[0]) || !s.isUsed(this); 347 } 348 349 bool mustExplode(const ref SolveState s) const { 350 return getState(s) == -1; 351 } 352 353 bool mustSplit(const ref SolveState s, size_t start, size_t stop) const { 354 return s.isSplit(start, stop) || mustExplode(s); 355 } 356 357 override uint computeIndent(const ref SolveState s, size_t i) const { 358 if (i >= trailingSplit) { 359 return 0; 360 } 361 362 return (s.isSplit(elements[0]) && s.isUsed(this)) ? 1 : 0; 363 } 364 365 override size_t computeAlignIndex(const ref SolveState s, size_t i) const { 366 if (i < elements[0] || i >= trailingSplit) { 367 return 0; 368 } 369 370 return isActive(s) ? 0 : elements[0]; 371 } 372 373 override Split computeSplit(const ref SolveState s, size_t i) const { 374 if (i < elements[0] || i > trailingSplit) { 375 return Split.Can; 376 } 377 378 if (i == trailingSplit) { 379 return mustExplode(s) ? Split.Must : Split.No; 380 } 381 382 size_t previous = elements[0]; 383 foreach (p; elements) { 384 if (previous > i) { 385 // We went past the index we are interested in. 386 break; 387 } 388 389 if (p < i) { 390 // We have not reached our goal, move on to the next param. 391 previous = p; 392 continue; 393 } 394 395 if (p > i) { 396 // We can only split within an element 397 // if the element itself is split. 398 return s.isSplit(previous) ? Split.Can : Split.No; 399 } 400 401 return mustSplit(s, previous + 1, p) ? Split.Must : Split.Can; 402 } 403 404 return Split.Can; 405 } 406 } 407 408 final class CompactListSpan : ListSpan { 409 this(Span parent) { 410 super(parent); 411 } 412 413 override uint getCost(const ref SolveState s) const { 414 // If there is just one element, make it slitghtly more exepensive to split. 415 if (elements.length <= 1) { 416 return 15; 417 } 418 419 if (!isActive(s)) { 420 return 13; 421 } 422 423 foreach (p; elements[1 .. $]) { 424 if (s.isSplit(p)) { 425 return 14; 426 } 427 } 428 429 return 13; 430 } 431 432 mixin CachedState; 433 ulong computeState(const ref SolveState s) const { 434 // If more than 2/3 of the element split, just explode. 435 const max = 2 * (elements.length + 1) / 3; 436 437 ulong count = 0; 438 foreach (p; elements) { 439 count += s.isSplit(p); 440 441 if (count > max) { 442 return -1; 443 } 444 } 445 446 return (count << 1) | s.isSplit(elements[0]); 447 } 448 } 449 450 final class ExpandingListSpan : ListSpan { 451 this(Span parent) { 452 super(parent); 453 } 454 455 override uint getCost(const ref SolveState s) const { 456 // If there is just one element, make it slitghtly more exepensive to split. 457 if (elements.length <= 1) { 458 return 15; 459 } 460 461 if (s.isSplit(elements[0])) { 462 return 14; 463 } 464 465 return 13; 466 } 467 468 mixin CachedState; 469 ulong computeState(const ref SolveState s) const { 470 // If the last element is broken, expand the whole thing. 471 if (hasTrailingSplit 472 && s.isSplit(elements[$ - 1] + 1, trailingSplit + 1)) { 473 return -1; 474 } 475 476 ulong state = s.isSplit(elements[0]); 477 478 size_t previous = elements[0]; 479 foreach (k, p; elements[1 .. $]) { 480 scope(success) { 481 previous = p; 482 } 483 484 if (!s.isSplit(previous + 1, p + 1)) { 485 continue; 486 } 487 488 if (state > 1) { 489 return -1; 490 } 491 492 state |= (k + 1) << 1; 493 } 494 495 // For length 1 and 2, we won't trip the explode state earlier, 496 // so we push the trigger now if apropriate. 497 auto splitCount = (state & 0x01) + (state > 1); 498 if (elements.length <= splitCount) { 499 return -1; 500 } 501 502 return state; 503 } 504 } 505 506 /** 507 * Span used to format Condition expression, of the form: 508 * condition ? ifTrue : ifFalse 509 */ 510 final class ConditionalSpan : Span { 511 size_t questionMarkIndex = size_t.max; 512 size_t colonIndex = size_t.max; 513 514 ConditionalSpan parentConditional = null; 515 516 this(Span parent) { 517 super(parent); 518 } 519 520 void setQuestionMarkIndex(size_t i) { 521 questionMarkIndex = i; 522 523 // Use the opportinity to detect if this is a nested conditional. 524 static ConditionalSpan findParentConditional(const Span s, size_t i) { 525 auto p = s.parent; 526 if (p is null) { 527 return null; 528 } 529 530 if (auto c = cast(ConditionalSpan) p) { 531 // Skip over if we are in the parent's condition rather than nested. 532 if (c.questionMarkIndex < i) { 533 return c; 534 } 535 } 536 537 return findParentConditional(p, i); 538 } 539 540 parentConditional = findParentConditional(this, i); 541 } 542 543 void setColonIndex(size_t i) { 544 colonIndex = i; 545 } 546 547 override Split computeSplit(const ref SolveState s, size_t i) const { 548 if (i == questionMarkIndex && parentConditional !is null) { 549 auto pi = parentConditional.questionMarkIndex; 550 return s.isSplit(pi) ? Split.Can : Split.No; 551 } 552 553 if (i == colonIndex) { 554 return s.isSplit(questionMarkIndex) ? Split.Must : Split.No; 555 } 556 557 return Split.Can; 558 } 559 } 560 561 /** 562 * Span that do not cause any indentation and is cheap to break. 563 */ 564 final class StorageClassSpan : Span { 565 this(Span parent) { 566 super(parent); 567 } 568 569 override uint getCost(const ref SolveState s) const { 570 return 5; 571 } 572 573 override uint computeIndent(const ref SolveState s, size_t i) const { 574 return 0; 575 } 576 577 override bool matchLevel(const Span s) const { 578 return parent.isSameLevel(s); 579 } 580 }