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 }