1 /// DustMite, a D test case minimization tool
2 /// Written by Vladimir Panteleev <vladimir@thecybershadow.net>
3 /// Released into the Public Domain
4
5 module dustmite;
6
7 import std.algorithm;
8 import std.array;
9 import std.ascii;
10 import std.conv;
11 import std.datetime;
12 import std.datetime.stopwatch : StopWatch;
13 import std.exception;
14 import std.file;
15 import std.getopt;
16 import std.path;
17 import std.parallelism : totalCPUs;
18 import std.process;
19 import std.random;
20 import std.regex;
21 import std.stdio;
22 import std..string;
23
24 import splitter;
25
26 alias Splitter = splitter.Splitter;
27
28 // Issue 314 workarounds
29 alias std..string.join join;
30 alias std..string.startsWith startsWith;
31
32 string dir, resultDir, tester, globalCache;
33 string dirSuffix(string suffix) { return (dir.absolutePath().buildNormalizedPath() ~ "." ~ suffix).relativePath(); }
34
35 size_t maxBreadth;
36 Entity root;
37 size_t origDescendants;
38 int tests; bool foundAnything;
39 bool noSave, trace, noRedirect;
40 string strategy = "inbreadth";
41
42 struct Times { StopWatch total, load, testSave, resultSave, test, clean, cacheHash, globalCache, misc; }
43 Times times;
44 static this() { times.total.start(); times.misc.start(); }
45 void measure(string what)(void delegate() p)
46 {
47 times.misc.stop(); mixin("times."~what~".start();");
48 p();
49 mixin("times."~what~".stop();"); times.misc.start();
50 }
51
52 struct Reduction
53 {
54 enum Type { None, Remove, Unwrap, Concat, ReplaceWord }
55 Type type;
56
57 // Remove / Unwrap / Concat
58 size_t[] address;
59 Entity target;
60
61 // ReplaceWord
62 string from, to;
63 size_t index, total;
64
65 string toString()
66 {
67 string name = .to!string(type);
68
69 final switch (type)
70 {
71 case Reduction.Type.None:
72 return name;
73 case Reduction.Type.ReplaceWord:
74 return format(`%s [%d/%d: %s -> %s]`, name, index+1, total, from, to);
75 case Reduction.Type.Remove:
76 case Reduction.Type.Unwrap:
77 case Reduction.Type.Concat:
78 string[] segments = new string[address.length];
79 Entity e = root;
80 size_t progress;
81 bool binary = maxBreadth == 2;
82 foreach (i, a; address)
83 {
84 segments[i] = binary ? text(a) : format("%d/%d", e.children.length-a, e.children.length);
85 foreach (c; e.children[0..a])
86 progress += c.descendants;
87 progress++; // account for this node
88 e = e.children[a];
89 }
90 progress += e.descendants;
91 auto progressPM = (origDescendants-progress) * 1000 / origDescendants; // per-mille
92 return format("[%2d.%d%%] %s [%s]", progressPM/10, progressPM%10, name, segments.join(binary ? "" : ", "));
93 }
94 }
95 }
96
97 auto nullReduction = Reduction(Reduction.Type.None);
98
99 int main(string[] args)
100 {
101 bool force, dump, dumpHtml, showTimes, stripComments, obfuscate, keepLength, showHelp, noOptimize;
102 string coverageDir;
103 string[] reduceOnly, noRemoveStr, splitRules;
104 uint lookaheadCount;
105
106 args = args.filter!(
107 (arg)
108 {
109 if (arg.startsWith("-j"))
110 {
111 arg = arg[2..$];
112 lookaheadCount = arg.length ? arg.to!uint : totalCPUs;
113 return false;
114 }
115 return true;
116 }).array();
117
118 getopt(args,
119 "force", &force,
120 "reduceonly|reduce-only", &reduceOnly,
121 "noremove|no-remove", &noRemoveStr,
122 "strip-comments", &stripComments,
123 "coverage", &coverageDir,
124 "obfuscate", &obfuscate,
125 "keep-length", &keepLength,
126 "strategy", &strategy,
127 "split", &splitRules,
128 "dump", &dump,
129 "dump-html", &dumpHtml,
130 "times", &showTimes,
131 "noredirect|no-redirect", &noRedirect,
132 "cache", &globalCache, // for research
133 "trace", &trace, // for debugging
134 "nosave|no-save", &noSave, // for research
135 "nooptimize|no-optimize", &noOptimize, // for research
136 "h|help", &showHelp,
137 );
138
139 if (showHelp || args.length == 1 || args.length>3)
140 {
141 stderr.writef(q"EOS
142 Usage: %s [OPTION]... PATH TESTER
143 PATH should be a directory containing a clean copy of the file-set to reduce.
144 A file path can also be specified. NAME.EXT will be treated like NAME/NAME.EXT.
145 TESTER should be a shell command which returns 0 for a correct reduction,
146 and anything else otherwise.
147 Supported options:
148 --force Force reduction of unusual files
149 --reduce-only MASK Only reduce paths glob-matching MASK
150 (may be used multiple times)
151 --no-remove REGEXP Do not reduce blocks containing REGEXP
152 (may be used multiple times)
153 --strip-comments Attempt to remove comments from source code.
154 --coverage DIR Load .lst files corresponding to source files from DIR
155 --obfuscate Instead of reducing, obfuscate the input by replacing
156 words with random substitutions
157 --keep-length Preserve word length when obfuscating
158 --split MASK:MODE Parse and reduce files specified by MASK using the given
159 splitter. Can be repeated. MODE must be one of:
160 %-(%s, %)
161 --no-redirect Don't redirect stdout/stderr streams of test command.
162 -j[N] Use N look-ahead processes (%d by default)
163 EOS", args[0], splitterNames, totalCPUs);
164
165 if (!showHelp)
166 {
167 stderr.write(q"EOS
168 --help Show this message and some less interesting options
169 EOS");
170 }
171 else
172 {
173 stderr.write(q"EOS
174 --help Show this message
175 Less interesting options:
176 --strategy STRAT Set strategy (careful/lookback/pingpong/indepth/inbreadth)
177 --dump Dump parsed tree to DIR.dump file
178 --dump-html Dump parsed tree to DIR.html file
179 --times Display verbose spent time breakdown
180 --cache DIR Use DIR as persistent disk cache
181 (in addition to memory cache)
182 --trace Save all attempted reductions to DIR.trace
183 --no-save Disable saving in-progress results
184 --no-optimize Disable tree optimization step
185 (may be useful with --dump)
186 EOS");
187 }
188 stderr.write(q"EOS
189
190 Full documentation can be found on the GitHub wiki:
191 https://github.com/CyberShadow/DustMite/wiki
192 EOS");
193 return showHelp ? 0 : 64; // EX_USAGE
194 }
195
196 enforce(!(stripComments && coverageDir), "Sorry, --strip-comments is not compatible with --coverage");
197
198 dir = args[1];
199 if (isDirSeparator(dir[$-1]))
200 dir = dir[0..$-1];
201
202 if (args.length>=3)
203 tester = args[2];
204
205 bool isDotName(string fn) { return fn.startsWith(".") && !(fn=="." || fn==".."); }
206
207 if (!force && isDir(dir))
208 foreach (string path; dirEntries(dir, SpanMode.breadth))
209 if (isDotName(baseName(path)) || isDotName(baseName(dirName(path))) || extension(path)==".o" || extension(path)==".obj" || extension(path)==".exe")
210 {
211 stderr.writefln("Suspicious file found: %s\nYou should use a clean copy of the source tree.\nIf it was your intention to include this file in the file-set to be reduced,\nre-run dustmite with the --force option.", path);
212 return 1;
213 }
214
215 ParseRule parseSplitRule(string rule)
216 {
217 auto p = rule.lastIndexOf(':');
218 enforce(p > 0, "Invalid parse rule: " ~ rule);
219 auto pattern = rule[0..p];
220 auto splitterName = rule[p+1..$];
221 auto splitterIndex = splitterNames.countUntil(splitterName);
222 enforce(splitterIndex >= 0, "Unknown splitter: " ~ splitterName);
223 return ParseRule(pattern, cast(Splitter)splitterIndex);
224 }
225
226 ParseOptions parseOptions;
227 parseOptions.stripComments = stripComments;
228 parseOptions.mode = obfuscate ? ParseOptions.Mode.words : ParseOptions.Mode.source;
229 parseOptions.rules = splitRules.map!parseSplitRule().array();
230 measure!"load"({root = loadFiles(dir, parseOptions);});
231 enforce(root.children.length, "No files in specified directory");
232
233 applyNoRemoveMagic();
234 applyNoRemoveRegex(noRemoveStr, reduceOnly);
235 applyNoRemoveDeps();
236 if (coverageDir)
237 loadCoverage(coverageDir);
238 if (!obfuscate && !noOptimize)
239 optimize(root);
240 maxBreadth = getMaxBreadth(root);
241 countDescendants(root);
242 resetProgress();
243 assignID(root);
244
245 if (dump)
246 dumpSet(dirSuffix("dump"));
247 if (dumpHtml)
248 dumpToHtml(dirSuffix("html"));
249
250 if (tester is null)
251 {
252 writeln("No tester specified, exiting");
253 return 0;
254 }
255
256 resultDir = dirSuffix("reduced");
257 enforce(!exists(resultDir), "Result directory already exists");
258
259 if (!test(nullReduction))
260 {
261 auto testerFile = dir.buildNormalizedPath(tester);
262 version (Posix)
263 {
264 if (testerFile.exists && (testerFile.getAttributes() & octal!111) == 0)
265 writeln("Hint: test program seems to be a non-executable file, try: chmod +x " ~ testerFile.escapeShellFileName());
266 }
267 if (!testerFile.exists && tester.exists)
268 writeln("Hint: test program path should be relative to the source directory, try " ~
269 tester.absolutePath.relativePath(dir.absolutePath).escapeShellFileName() ~
270 " instead of " ~ tester.escapeShellFileName());
271 throw new Exception("Initial test fails" ~ (noRedirect ? "" : " (try using --no-redirect for details)"));
272 }
273
274 lookaheadProcesses = new Lookahead[lookaheadCount];
275
276 foundAnything = false;
277 if (obfuscate)
278 .obfuscate(keepLength);
279 else
280 reduce();
281
282 auto duration = times.total.peek();
283 duration = dur!"msecs"(duration.total!"msecs"); // truncate anything below ms, users aren't interested in that
284 if (foundAnything)
285 {
286 if (root.children.length)
287 {
288 if (noSave)
289 measure!"resultSave"({safeSave(resultDir);});
290 writefln("Done in %s tests and %s; reduced version is in %s", tests, duration, resultDir);
291 }
292 else
293 writefln("Done in %s tests and %s; reduced to empty set", tests, duration);
294 }
295 else
296 writefln("Done in %s tests and %s; no reductions found", tests, duration);
297
298 if (showTimes)
299 foreach (i, t; times.tupleof)
300 writefln("%s: %s", times.tupleof[i].stringof, times.tupleof[i].peek());
301
302 return 0;
303 }
304
305 size_t getMaxBreadth(Entity e)
306 {
307 size_t breadth = e.children.length;
308 foreach (child; e.children)
309 {
310 auto childBreadth = getMaxBreadth(child);
311 if (breadth < childBreadth)
312 breadth = childBreadth;
313 }
314 return breadth;
315 }
316
317 size_t countDescendants(Entity e)
318 {
319 size_t n = 1;
320 foreach (c; e.children)
321 n += countDescendants(c);
322 return e.descendants = n;
323 }
324
325 size_t checkDescendants(Entity e)
326 {
327 size_t n = 1;
328 foreach (c; e.children)
329 n += checkDescendants(c);
330 assert(e.descendants == n, "Wrong descendant count: expected %d, found %d".format(e.descendants, n));
331 return n;
332 }
333
334 size_t countFiles(Entity e)
335 {
336 if (e.isFile)
337 return 1;
338 else
339 {
340 size_t n = 0;
341 foreach (c; e.children)
342 n += countFiles(c);
343 return n;
344 }
345 }
346
347
348 struct ReductionIterator
349 {
350 Strategy strategy;
351
352 bool done = false;
353 bool concatPerformed;
354
355 Reduction.Type type = Reduction.Type.None;
356 Entity e;
357
358 this(Strategy strategy)
359 {
360 this.strategy = strategy;
361 next(false);
362
363 if (countFiles(root) < 2)
364 concatPerformed = true;
365 }
366
367 this(this)
368 {
369 strategy = strategy.dup;
370 }
371
372 @property Reduction front() { return Reduction(type, strategy.front, e); }
373
374 void next(bool success)
375 {
376 while (true)
377 {
378 final switch (type)
379 {
380 case Reduction.Type.None:
381 if (strategy.done)
382 {
383 done = true;
384 return;
385 }
386
387 e = entityAt(strategy.front);
388
389 if (e.noRemove)
390 {
391 strategy.next(false);
392 continue;
393 }
394
395 if (e is root && !root.children.length)
396 {
397 strategy.next(false);
398 continue;
399 }
400
401 // Try next reduction type
402 type = Reduction.Type.Remove;
403 return;
404
405 case Reduction.Type.Remove:
406 if (success)
407 {
408 // Next node
409 type = Reduction.Type.None;
410 strategy.next(true);
411 continue;
412 }
413
414 // Try next reduction type
415 type = Reduction.Type.Unwrap;
416
417 if (e.head.length && e.tail.length)
418 return; // Try this
419 else
420 {
421 success = false; // Skip
422 continue;
423 }
424
425 case Reduction.Type.Unwrap:
426 if (success)
427 {
428 // Next node
429 type = Reduction.Type.None;
430 strategy.next(true);
431 continue;
432 }
433
434 // Try next reduction type
435 type = Reduction.Type.Concat;
436
437 if (e.isFile && !concatPerformed)
438 return; // Try this
439 else
440 {
441 success = false; // Skip
442 continue;
443 }
444
445 case Reduction.Type.Concat:
446 if (success)
447 concatPerformed = true;
448
449 // Next node
450 type = Reduction.Type.None;
451 strategy.next(success);
452 continue;
453
454 case Reduction.Type.ReplaceWord:
455 assert(false);
456 }
457 }
458 }
459 }
460
461 void resetProgress()
462 {
463 origDescendants = root.descendants;
464 }
465
466 class Strategy
467 {
468 uint progressGeneration = 0;
469 bool done = false;
470
471 void copy(Strategy result) const
472 {
473 result.progressGeneration = this.progressGeneration;
474 result.done = this.done;
475 }
476
477 abstract @property size_t[] front();
478 abstract void next(bool success);
479 int getIteration() { return -1; }
480 int getDepth() { return -1; }
481
482 final Strategy dup()
483 {
484 auto result = cast(Strategy)this.classinfo.create();
485 copy(result);
486 return result;
487 }
488 }
489
490 class SimpleStrategy : Strategy
491 {
492 size_t[] address;
493
494 override void copy(Strategy target) const
495 {
496 super.copy(target);
497 auto result = cast(SimpleStrategy)target;
498 result.address = this.address.dup;
499 }
500
501 override @property size_t[] front()
502 {
503 assert(!done, "Done");
504 return address;
505 }
506
507 override void next(bool success)
508 {
509 assert(!done, "Done");
510 }
511 }
512
513 class IterativeStrategy : SimpleStrategy
514 {
515 int iteration = 0;
516 bool iterationChanged;
517
518 override int getIteration() { return iteration; }
519
520 override void copy(Strategy target) const
521 {
522 super.copy(target);
523 auto result = cast(IterativeStrategy)target;
524 result.iteration = this.iteration;
525 result.iterationChanged = this.iterationChanged;
526 }
527
528 override void next(bool success)
529 {
530 super.next(success);
531 iterationChanged |= success;
532 }
533
534 void nextIteration()
535 {
536 assert(iterationChanged, "Starting new iteration after no changes");
537 iteration++;
538 iterationChanged = false;
539 address = null;
540 progressGeneration++;
541 }
542 }
543
544 /// Find the first address at the depth of address.length,
545 /// and populate address[] accordingly.
546 /// Return false if no address at that level could be found.
547 bool findAddressAtLevel(size_t[] address, Entity root)
548 {
549 if (!address.length)
550 return true;
551 foreach_reverse (i, child; root.children)
552 {
553 if (findAddressAtLevel(address[1..$], child))
554 {
555 address[0] = i;
556 return true;
557 }
558 }
559 return false;
560 }
561
562 /// Find the next address at the depth of address.length,
563 /// and update address[] accordingly.
564 /// Return false if no more addresses at that level could be found.
565 bool nextAddressInLevel(size_t[] address, lazy Entity root)
566 {
567 if (!address.length)
568 return false;
569 if (nextAddressInLevel(address[1..$], root.children[address[0]]))
570 return true;
571 if (!address[0])
572 return false;
573
574 foreach_reverse (i; 0..address[0])
575 {
576 if (findAddressAtLevel(address[1..$], root.children[i]))
577 {
578 address[0] = i;
579 return true;
580 }
581 }
582 return false;
583 }
584
585 /// Find the next address, starting from the given one
586 /// (going depth-first). Update address accordingly.
587 /// If descend is false, then skip addresses under the given one.
588 /// Return false if no more addresses could be found.
589 bool nextAddress(ref size_t[] address, lazy Entity root, bool descend)
590 {
591 if (!address.length)
592 {
593 if (descend && root.children.length)
594 {
595 address ~= [root.children.length-1];
596 return true;
597 }
598 return false;
599 }
600
601 auto cdr = address[1..$];
602 if (nextAddress(cdr, root.children[address[0]], descend))
603 {
604 address = address[0] ~ cdr;
605 return true;
606 }
607
608 if (address[0])
609 {
610 address = [address[0] - 1];
611 return true;
612 }
613
614 return false;
615 }
616
617 void validateAddress(size_t[] address, Entity root = root)
618 {
619 if (!address.length)
620 return;
621 assert(address[0] < root.children.length);
622 validateAddress(address[1..$], root.children[address[0]]);
623 }
624
625 class LevelStrategy : IterativeStrategy
626 {
627 bool levelChanged;
628 bool invalid;
629
630 override int getDepth() { return cast(int)address.length; }
631
632 override void copy(Strategy target) const
633 {
634 super.copy(target);
635 auto result = cast(LevelStrategy)target;
636 result.levelChanged = this.levelChanged;
637 result.invalid = this.invalid;
638 }
639
640 override void next(bool success)
641 {
642 super.next(success);
643 levelChanged |= success;
644 }
645
646 override void nextIteration()
647 {
648 super.nextIteration();
649 invalid = false;
650 levelChanged = false;
651 }
652
653 final bool nextInLevel()
654 {
655 assert(!invalid, "Choose a level!");
656 if (nextAddressInLevel(address, root))
657 return true;
658 else
659 {
660 invalid = true;
661 return false;
662 }
663 }
664
665 final @property size_t currentLevel() const { return address.length; }
666
667 final bool setLevel(size_t level)
668 {
669 address.length = level;
670 if (findAddressAtLevel(address, root))
671 {
672 invalid = false;
673 levelChanged = false;
674 progressGeneration++;
675 return true;
676 }
677 else
678 return false;
679 }
680 }
681
682 /// Keep going deeper until we find a successful reduction.
683 /// When found, finish tests at current depth and restart from top depth (new iteration).
684 /// If we reach the bottom (depth with no nodes on it), we're done.
685 class CarefulStrategy : LevelStrategy
686 {
687 override void next(bool success)
688 {
689 super.next(success);
690
691 if (!nextInLevel())
692 {
693 // End of level
694 if (levelChanged)
695 {
696 nextIteration();
697 }
698 else
699 if (!setLevel(currentLevel + 1))
700 {
701 if (iterationChanged)
702 nextIteration();
703 else
704 done = true;
705 }
706 }
707 }
708 }
709
710 /// Keep going deeper until we find a successful reduction.
711 /// When found, go up a depth level.
712 /// Keep going up while we find new reductions. Repeat topmost depth level as necessary.
713 /// Once no new reductions are found at higher depths, jump to the next unvisited depth in this iteration.
714 /// If we reach the bottom (depth with no nodes on it), start a new iteration.
715 /// If we finish an iteration without finding any reductions, we're done.
716 class LookbackStrategy : LevelStrategy
717 {
718 size_t maxLevel = 0;
719
720 override void copy(Strategy target) const
721 {
722 super.copy(target);
723 auto result = cast(LookbackStrategy)target;
724 result.maxLevel = this.maxLevel;
725 }
726
727 override void nextIteration()
728 {
729 super.nextIteration();
730 maxLevel = 0;
731 }
732
733 override void next(bool success)
734 {
735 super.next(success);
736
737 if (!nextInLevel())
738 {
739 // End of level
740 if (levelChanged)
741 {
742 setLevel(currentLevel ? currentLevel - 1 : 0);
743 }
744 else
745 if (setLevel(maxLevel + 1))
746 {
747 maxLevel = currentLevel;
748 }
749 else
750 {
751 if (iterationChanged)
752 nextIteration();
753 else
754 done = true;
755 }
756 }
757 }
758 }
759
760 /// Keep going deeper until we find a successful reduction.
761 /// When found, go up a depth level.
762 /// Keep going up while we find new reductions. Repeat topmost depth level as necessary.
763 /// Once no new reductions are found at higher depths, start going downwards again.
764 /// If we reach the bottom (depth with no nodes on it), start a new iteration.
765 /// If we finish an iteration without finding any reductions, we're done.
766 class PingPongStrategy : LevelStrategy
767 {
768 override void next(bool success)
769 {
770 super.next(success);
771
772 if (!nextInLevel())
773 {
774 // End of level
775 if (levelChanged)
776 {
777 setLevel(currentLevel ? currentLevel - 1 : 0);
778 }
779 else
780 if (!setLevel(currentLevel + 1))
781 {
782 if (iterationChanged)
783 nextIteration();
784 else
785 done = true;
786 }
787 }
788 }
789 }
790
791 /// Keep going deeper.
792 /// If we reach the bottom (depth with no nodes on it), start a new iteration.
793 /// If we finish an iteration without finding any reductions, we're done.
794 class InBreadthStrategy : LevelStrategy
795 {
796 override void next(bool success)
797 {
798 super.next(success);
799
800 if (!nextInLevel())
801 {
802 // End of level
803 if (!setLevel(currentLevel + 1))
804 {
805 if (iterationChanged)
806 nextIteration();
807 else
808 done = true;
809 }
810 }
811 }
812 }
813
814 /// Look at every entity in the tree.
815 /// If we can reduce this entity, continue looking at its siblings.
816 /// Otherwise, recurse and look at its children.
817 /// End an iteration once we looked at an entire tree.
818 /// If we finish an iteration without finding any reductions, we're done.
819 class InDepthStrategy : IterativeStrategy
820 {
821 final bool nextAddress(bool descend)
822 {
823 return .nextAddress(address, root, descend);
824 }
825
826 override void next(bool success)
827 {
828 super.next(success);
829
830 if (!nextAddress(!success))
831 {
832 if (iterationChanged)
833 nextIteration();
834 else
835 done = true;
836 }
837 }
838 }
839
840 ReductionIterator iter;
841
842 void reduceByStrategy(Strategy strategy)
843 {
844 int lastIteration = -1;
845 int lastDepth = -1;
846 int lastProgressGeneration = -1;
847
848 iter = ReductionIterator(strategy);
849
850 while (!iter.done)
851 {
852 if (lastIteration != strategy.getIteration())
853 {
854 writefln("############### ITERATION %d ################", strategy.getIteration());
855 lastIteration = strategy.getIteration();
856 }
857 if (lastDepth != strategy.getDepth())
858 {
859 writefln("============= Depth %d =============", strategy.getDepth());
860 lastDepth = strategy.getDepth();
861 }
862 if (lastProgressGeneration != strategy.progressGeneration)
863 {
864 resetProgress();
865 lastProgressGeneration = strategy.progressGeneration;
866 }
867
868 auto result = tryReduction(iter.front);
869
870 iter.next(result);
871 }
872 }
873
874 void reduce()
875 {
876 switch (strategy)
877 {
878 case "careful":
879 return reduceByStrategy(new CarefulStrategy());
880 case "lookback":
881 return reduceByStrategy(new LookbackStrategy());
882 case "pingpong":
883 return reduceByStrategy(new PingPongStrategy());
884 case "indepth":
885 return reduceByStrategy(new InDepthStrategy());
886 case "inbreadth":
887 return reduceByStrategy(new InBreadthStrategy());
888 default:
889 throw new Exception("Unknown strategy");
890 }
891 }
892
893 Mt19937 rng;
894
895 void obfuscate(bool keepLength)
896 {
897 bool[string] wordSet;
898 string[] words; // preserve file order
899
900 foreach (f; root.children)
901 {
902 foreach (entity; parseToWords(f.filename) ~ f.children)
903 if (entity.head.length && !isDigit(entity.head[0]))
904 if (entity.head !in wordSet)
905 {
906 wordSet[entity.head] = true;
907 words ~= entity.head;
908 }
909 }
910
911 string idgen(size_t length)
912 {
913 static const first = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // use caps to avoid collisions with reserved keywords
914 static const other = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_";
915
916 if (keepLength)
917 {
918 auto result = new char[length];
919 foreach (i, ref c; result)
920 c = (i==0 ? first : other)[uniform(0, cast(uint)$, rng)];
921
922 return assumeUnique(result);
923 }
924 else
925 {
926 static int n;
927 int index = n++;
928
929 string result;
930 result ~= first[index % $];
931 index /= first.length;
932
933 while (index)
934 result ~= other[index % $],
935 index /= other.length;
936
937 return result;
938 }
939 }
940
941 auto r = Reduction(Reduction.Type.ReplaceWord);
942 r.total = words.length;
943 foreach (i, word; words)
944 {
945 r.index = i;
946 r.from = word;
947 int tries = 0;
948 do
949 r.to = idgen(word.length);
950 while (r.to in wordSet && tries++ < 10);
951 wordSet[r.to] = true;
952
953 tryReduction(r);
954 }
955 }
956
957 bool skipEntity(Entity e)
958 {
959 if (e.removed)
960 return true;
961 foreach (dependency; e.dependencies)
962 if (skipEntity(dependency))
963 return true;
964 return false;
965 }
966
967 void dump(Entity root, ref Reduction reduction, void delegate(string) handleFile, void delegate(string) handleText)
968 {
969 void dumpEntity(Entity e)
970 {
971 if (reduction.type == Reduction.Type.ReplaceWord)
972 {
973 if (e.isFile)
974 {
975 assert(e.head.length==0 && e.tail.length==0);
976 handleFile(applyReductionToPath(e.filename, reduction));
977 foreach (c; e.children)
978 dumpEntity(c);
979 }
980 else
981 if (e.head || e.tail)
982 {
983 assert(e.children.length==0);
984 if (e.head)
985 {
986 if (e.head == reduction.from)
987 handleText(reduction.to);
988 else
989 handleText(e.head);
990 }
991 handleText(e.tail);
992 }
993 else
994 foreach (c; e.children)
995 dumpEntity(c);
996 }
997 else
998 if (e is reduction.target)
999 {
1000 final switch (reduction.type)
1001 {
1002 case Reduction.Type.None:
1003 case Reduction.Type.ReplaceWord:
1004 assert(0);
1005 case Reduction.Type.Remove: // skip this entity
1006 return;
1007 case Reduction.Type.Unwrap: // skip head/tail
1008 foreach (c; e.children)
1009 dumpEntity(c);
1010 break;
1011 case Reduction.Type.Concat: // write contents of all files to this one; leave other files empty
1012 handleFile(e.filename);
1013
1014 void dumpFileContent(Entity e)
1015 {
1016 foreach (f; e.children)
1017 if (f.isFile)
1018 foreach (c; f.children)
1019 dumpEntity(c);
1020 else
1021 dumpFileContent(f);
1022 }
1023 dumpFileContent(root);
1024 break;
1025 }
1026 }
1027 else
1028 if (skipEntity(e))
1029 return;
1030 else
1031 if (e.isFile)
1032 {
1033 handleFile(e.filename);
1034 if (reduction.type == Reduction.Type.Concat) // not the target - writing an empty file
1035 return;
1036 foreach (c; e.children)
1037 dumpEntity(c);
1038 }
1039 else
1040 {
1041 if (e.head.length) handleText(e.head);
1042 foreach (c; e.children)
1043 dumpEntity(c);
1044 if (e.tail.length) handleText(e.tail);
1045 }
1046 }
1047
1048 debug verifyNotRemoved(root);
1049 if (reduction.type == Reduction.Type.Remove)
1050 markRemoved(reduction.target, true); // Needed for dependencies
1051
1052 dumpEntity(root);
1053
1054 if (reduction.type == Reduction.Type.Remove)
1055 markRemoved(reduction.target, false);
1056 debug verifyNotRemoved(root);
1057 }
1058
1059 void save(Reduction reduction, string savedir)
1060 {
1061 safeMkdir(savedir);
1062
1063 File o;
1064
1065 void handleFile(string fn)
1066 {
1067 auto path = buildPath(savedir, fn);
1068 if (!exists(dirName(path)))
1069 safeMkdir(dirName(path));
1070
1071 if (o.isOpen)
1072 o.close();
1073 o.open(path, "wb");
1074 }
1075
1076 dump(root, reduction, &handleFile, &o.write!string);
1077
1078 if (o.isOpen)
1079 o.close();
1080 }
1081
1082 Entity entityAt(size_t[] address)
1083 {
1084 Entity e = root;
1085 foreach (a; address)
1086 e = e.children[a];
1087 return e;
1088 }
1089
1090 /// Try specified reduction. If it succeeds, apply it permanently and save intermediate result.
1091 bool tryReduction(Reduction r)
1092 {
1093 if (test(r))
1094 {
1095 foundAnything = true;
1096 debug
1097 auto hashBefore = hash(r);
1098 applyReduction(r);
1099 debug
1100 {
1101 auto hashAfter = hash(nullReduction);
1102 assert(hashBefore == hashAfter, "Reduction preview/application mismatch");
1103 }
1104 saveResult();
1105 return true;
1106 }
1107 return false;
1108 }
1109
1110 void verifyNotRemoved(Entity e)
1111 {
1112 assert(!e.removed);
1113 foreach (c; e.children)
1114 verifyNotRemoved(c);
1115 }
1116
1117 void markRemoved(Entity e, bool value)
1118 {
1119 assert(e.removed == !value);
1120 e.removed = value;
1121 foreach (c; e.children)
1122 markRemoved(c, value);
1123 }
1124
1125 /// Permanently apply specified reduction to set.
1126 void applyReduction(ref Reduction r)
1127 {
1128 final switch (r.type)
1129 {
1130 case Reduction.Type.None:
1131 return;
1132 case Reduction.Type.ReplaceWord:
1133 {
1134 foreach (ref f; root.children)
1135 {
1136 f.filename = applyReductionToPath(f.filename, r);
1137 foreach (ref entity; f.children)
1138 if (entity.head == r.from)
1139 entity.head = r.to;
1140 }
1141 return;
1142 }
1143 case Reduction.Type.Remove:
1144 {
1145 debug verifyNotRemoved(root);
1146
1147 markRemoved(entityAt(r.address), true);
1148
1149 if (r.address.length)
1150 {
1151 auto casualties = entityAt(r.address).descendants;
1152 foreach (n; 0..r.address.length)
1153 entityAt(r.address[0..n]).descendants -= casualties;
1154
1155 auto p = entityAt(r.address[0..$-1]);
1156 p.children = remove(p.children, r.address[$-1]);
1157 }
1158 else
1159 {
1160 root = new Entity();
1161 root.descendants = 1;
1162 }
1163
1164 debug verifyNotRemoved(root);
1165 debug checkDescendants(root);
1166 return;
1167 }
1168 case Reduction.Type.Unwrap:
1169 with (entityAt(r.address))
1170 head = tail = null;
1171 return;
1172 case Reduction.Type.Concat:
1173 {
1174 Entity[] allData;
1175 void scan(Entity e)
1176 {
1177 if (e.isFile)
1178 {
1179 allData ~= e.children;
1180 e.children = null;
1181 }
1182 else
1183 foreach (c; e.children)
1184 scan(c);
1185 }
1186
1187 scan(root);
1188
1189 r.target.children = allData;
1190 optimize(r.target);
1191 countDescendants(root);
1192
1193 return;
1194 }
1195 }
1196 }
1197
1198 string applyReductionToPath(string path, Reduction reduction)
1199 {
1200 if (reduction.type == Reduction.Type.ReplaceWord)
1201 {
1202 Entity[] words = parseToWords(path);
1203 string result;
1204 foreach (i, word; words)
1205 {
1206 if (i > 0 && i == words.length-1 && words[i-1].tail.endsWith("."))
1207 result ~= word.head; // skip extension
1208 else
1209 if (word.head == reduction.from)
1210 result ~= reduction.to;
1211 else
1212 result ~= word.head;
1213 result ~= word.tail;
1214 }
1215 return result;
1216 }
1217 return path;
1218 }
1219
1220 void autoRetry(void delegate() fun, string operation)
1221 {
1222 while (true)
1223 try
1224 {
1225 fun();
1226 return;
1227 }
1228 catch (Exception e)
1229 {
1230 writeln("Error while attempting to " ~ operation ~ ": " ~ e.msg);
1231 import core.thread;
1232 Thread.sleep(dur!"seconds"(1));
1233 writeln("Retrying...");
1234 }
1235 }
1236
1237 /// Alternative way to check for file existence
1238 /// Files marked for deletion act as inexistant, but still prevent creation and appear in directory listings
1239 bool exists2(string path)
1240 {
1241 return array(dirEntries(dirName(path), baseName(path), SpanMode.shallow)).length > 0;
1242 }
1243
1244 void deleteAny(string path)
1245 {
1246 if (exists(path))
1247 {
1248 if (isDir(path))
1249 rmdirRecurse(path);
1250 else
1251 remove(path);
1252 }
1253 enforce(!exists(path) && !exists2(path), "Path still exists"); // Windows only marks locked directories for deletion
1254 }
1255
1256 void safeDelete(string path) { autoRetry({deleteAny(path);}, "delete " ~ path); }
1257 void safeRename(string src, string dst) { autoRetry({rename(src, dst);}, "rename " ~ src ~ " to " ~ dst); }
1258 void safeMkdir(string path) { autoRetry({mkdirRecurse(path);}, "mkdir " ~ path); }
1259
1260 void safeReplace(string path, void delegate(string path) creator)
1261 {
1262 auto tmpPath = path ~ ".inprogress";
1263 if (exists(tmpPath)) safeDelete(tmpPath);
1264 auto oldPath = path ~ ".old";
1265 if (exists(oldPath)) safeDelete(oldPath);
1266
1267 {
1268 scope(failure) safeDelete(tmpPath);
1269 creator(tmpPath);
1270 }
1271
1272 if (exists(path)) safeRename(path, oldPath);
1273 safeRename(tmpPath, path);
1274 if (exists(oldPath)) safeDelete(oldPath);
1275 }
1276
1277
1278 void safeSave(string savedir) { safeReplace(savedir, path => save(nullReduction, path)); }
1279
1280 void saveResult()
1281 {
1282 if (!noSave)
1283 measure!"resultSave"({safeSave(resultDir);});
1284 }
1285
1286 version(HAVE_AE)
1287 {
1288 // Use faster murmurhash from http://github.com/CyberShadow/ae
1289 // when compiled with -version=HAVE_AE
1290
1291 import ae.utils.digest;
1292 import ae.utils.textout;
1293
1294 alias MH3Digest128 HASH;
1295
1296 HASH hash(Reduction reduction)
1297 {
1298 static StringBuffer sb;
1299 sb.clear();
1300 auto writer = &sb.put!string;
1301 dump(root, reduction, writer, writer);
1302 return murmurHash3_128(sb.get());
1303 }
1304
1305 alias digestToStringMH3 formatHash;
1306 }
1307 else
1308 {
1309 import std.digest.md;
1310
1311 alias ubyte[16] HASH;
1312
1313 HASH hash(Reduction reduction)
1314 {
1315 ubyte[16] digest;
1316 MD5 context;
1317 context.start();
1318 auto writer = cast(void delegate(string))&context.put;
1319 dump(root, reduction, writer, writer);
1320 return context.finish();
1321 }
1322
1323 alias toHexString formatHash;
1324 }
1325
1326 struct Lookahead
1327 {
1328 Pid pid;
1329 string testdir;
1330 HASH digest;
1331 }
1332 Lookahead[] lookaheadProcesses;
1333
1334 bool[HASH] lookaheadResults;
1335
1336 bool lookaheadPredict() { return false; }
1337
1338 version (Windows)
1339 enum nullFileName = "nul";
1340 else
1341 enum nullFileName = "/dev/null";
1342
1343 bool[HASH] cache;
1344
1345 bool test(Reduction reduction)
1346 {
1347 write(reduction, " => "); stdout.flush();
1348
1349 HASH digest;
1350 measure!"cacheHash"({ digest = hash(reduction); });
1351
1352 bool ramCached(lazy bool fallback)
1353 {
1354 auto cacheResult = digest in cache;
1355 if (cacheResult)
1356 {
1357 // Note: as far as I can see, a cache hit for a positive reduction is not possible (except, perhaps, for a no-op reduction)
1358 writeln(*cacheResult ? "Yes" : "No", " (cached)");
1359 return *cacheResult;
1360 }
1361 auto result = fallback;
1362 return cache[digest] = result;
1363 }
1364
1365 bool diskCached(lazy bool fallback)
1366 {
1367 tests++;
1368
1369 if (globalCache)
1370 {
1371 if (!exists(globalCache)) mkdirRecurse(globalCache);
1372 string cacheBase = absolutePath(buildPath(globalCache, formatHash(digest))) ~ "-";
1373 bool found;
1374
1375 measure!"globalCache"({ found = exists(cacheBase~"0"); });
1376 if (found)
1377 {
1378 writeln("No (disk cache)");
1379 return false;
1380 }
1381 measure!"globalCache"({ found = exists(cacheBase~"1"); });
1382 if (found)
1383 {
1384 writeln("Yes (disk cache)");
1385 return true;
1386 }
1387 auto result = fallback;
1388 measure!"globalCache"({ autoRetry({ std.file.write(cacheBase ~ (result ? "1" : "0"), ""); }, "save result to disk cache"); });
1389 return result;
1390 }
1391 else
1392 return fallback;
1393 }
1394
1395 bool lookahead(lazy bool fallback)
1396 {
1397 if (iter.strategy)
1398 {
1399 // Handle existing lookahead jobs
1400
1401 bool reap(ref Lookahead process, int status)
1402 {
1403 safeDelete(process.testdir);
1404 process.pid = null;
1405 return lookaheadResults[process.digest] = status == 0;
1406 }
1407
1408 foreach (ref process; lookaheadProcesses)
1409 {
1410 if (process.pid)
1411 {
1412 auto waitResult = process.pid.tryWait();
1413 if (waitResult.terminated)
1414 reap(process, waitResult.status);
1415 }
1416 }
1417
1418 // Start new lookahead jobs
1419
1420 auto lookaheadIter = iter;
1421 if (!lookaheadIter.done)
1422 lookaheadIter.next(lookaheadPredict());
1423
1424 foreach (ref process; lookaheadProcesses)
1425 {
1426 if (!process.pid && !lookaheadIter.done)
1427 {
1428 auto initialReduction = lookaheadIter.front;
1429 bool first = true;
1430
1431 while (true)
1432 {
1433 auto reduction = lookaheadIter.front;
1434
1435 if (!first && reduction == initialReduction)
1436 break; // We've looped around using cached results
1437 first = false;
1438
1439 auto digest = hash(reduction);
1440
1441 if (digest in cache || digest in lookaheadResults || lookaheadProcesses[].canFind!(p => p.digest == digest))
1442 {
1443 bool prediction;
1444 if (digest in cache)
1445 prediction = cache[digest];
1446 else
1447 if (digest in lookaheadResults)
1448 prediction = lookaheadResults[digest];
1449 else
1450 prediction = lookaheadPredict();
1451 lookaheadIter.next(prediction);
1452 if (lookaheadIter.done)
1453 break;
1454 continue;
1455 }
1456
1457 process.digest = digest;
1458
1459 static int counter;
1460 process.testdir = dirSuffix("lookahead.%d".format(counter++));
1461 save(reduction, process.testdir);
1462
1463 auto nul = File(nullFileName, "w+");
1464 process.pid = spawnShell(tester, nul, nul, nul, null, Config.none, process.testdir);
1465
1466 lookaheadIter.next(lookaheadPredict());
1467 break;
1468 }
1469 }
1470 }
1471
1472 // Find a result for the current test.
1473
1474 auto plookaheadResult = digest in lookaheadResults;
1475 if (plookaheadResult)
1476 {
1477 writeln(*plookaheadResult ? "Yes" : "No", " (lookahead)");
1478 return *plookaheadResult;
1479 }
1480
1481 foreach (ref process; lookaheadProcesses)
1482 {
1483 if (process.pid && process.digest == digest)
1484 {
1485 // Current test is already being tested in the background, wait for its result.
1486
1487 auto exitCode = process.pid.wait();
1488
1489 auto result = reap(process, exitCode);
1490 writeln(result ? "Yes" : "No", " (lookahead-wait)");
1491 return result;
1492 }
1493 }
1494 }
1495
1496 return fallback;
1497 }
1498
1499 bool doTest()
1500 {
1501 string testdir = dirSuffix("test");
1502 measure!"testSave"({save(reduction, testdir);}); scope(exit) measure!"clean"({safeDelete(testdir);});
1503
1504 Pid pid;
1505 if (noRedirect)
1506 pid = spawnShell(tester, null, Config.none, testdir);
1507 else
1508 {
1509 auto nul = File(nullFileName, "w+");
1510 pid = spawnShell(tester, nul, nul, nul, null, Config.none, testdir);
1511 }
1512
1513 bool result;
1514 measure!"test"({result = pid.wait() == 0;});
1515 writeln(result ? "Yes" : "No");
1516 return result;
1517 }
1518
1519 auto result = ramCached(diskCached(lookahead(doTest())));
1520 if (trace) saveTrace(reduction, dirSuffix("trace"), result);
1521 return result;
1522 }
1523
1524 void saveTrace(Reduction reduction, string dir, bool result)
1525 {
1526 if (!exists(dir)) mkdir(dir);
1527 static size_t count;
1528 string countStr = format("%08d-#%08d-%d", count++, reduction.target ? reduction.target.id : 0, result ? 1 : 0);
1529 auto traceDir = buildPath(dir, countStr);
1530 save(reduction, traceDir);
1531 }
1532
1533 void applyNoRemoveMagic()
1534 {
1535 enum MAGIC_START = "DustMiteNoRemoveStart";
1536 enum MAGIC_STOP = "DustMiteNoRemoveStop";
1537
1538 bool state = false;
1539
1540 bool scanString(string s)
1541 {
1542 if (s.length == 0)
1543 return false;
1544 if (s.canFind(MAGIC_START))
1545 state = true;
1546 if (s.canFind(MAGIC_STOP))
1547 state = false;
1548 return state;
1549 }
1550
1551 bool scan(Entity e)
1552 {
1553 bool removeThis;
1554 removeThis = scanString(e.head);
1555 foreach (c; e.children)
1556 removeThis |= scan(c);
1557 removeThis |= scanString(e.tail);
1558 e.noRemove |= removeThis;
1559 return removeThis;
1560 }
1561
1562 scan(root);
1563 }
1564
1565 void applyNoRemoveRegex(string[] noRemoveStr, string[] reduceOnly)
1566 {
1567 auto noRemove = array(map!((string s) { return regex(s, "mg"); })(noRemoveStr));
1568
1569 void mark(Entity e)
1570 {
1571 e.noRemove = true;
1572 foreach (c; e.children)
1573 mark(c);
1574 }
1575
1576 auto files = root.isFile ? [root] : root.children;
1577
1578 foreach (f; files)
1579 {
1580 assert(f.isFile);
1581
1582 if
1583 (
1584 (reduceOnly.length && !reduceOnly.any!(mask => globMatch(f.filename, mask)))
1585 ||
1586 (noRemove.any!(a => !match(f.filename, a).empty))
1587 )
1588 {
1589 mark(f);
1590 root.noRemove = true;
1591 continue;
1592 }
1593
1594 immutable(char)*[] starts, ends;
1595
1596 foreach (r; noRemove)
1597 foreach (c; match(f.contents, r))
1598 {
1599 assert(c.hit.ptr >= f.contents.ptr && c.hit.ptr < f.contents.ptr+f.contents.length);
1600 starts ~= c.hit.ptr;
1601 ends ~= c.hit.ptr + c.hit.length;
1602 }
1603
1604 starts.sort();
1605 ends.sort();
1606
1607 int noRemoveLevel = 0;
1608
1609 bool scanString(string s)
1610 {
1611 if (!s.length)
1612 return noRemoveLevel > 0;
1613
1614 auto start = s.ptr;
1615 auto end = start + s.length;
1616 assert(start >= f.contents.ptr && end <= f.contents.ptr+f.contents.length);
1617
1618 while (starts.length && starts[0] < end)
1619 {
1620 noRemoveLevel++;
1621 starts = starts[1..$];
1622 }
1623 bool result = noRemoveLevel > 0;
1624 while (ends.length && ends[0] <= end)
1625 {
1626 noRemoveLevel--;
1627 ends = ends[1..$];
1628 }
1629 return result;
1630 }
1631
1632 bool scan(Entity e)
1633 {
1634 bool result = false;
1635 if (scanString(e.head))
1636 result = true;
1637 foreach (c; e.children)
1638 if (scan(c))
1639 result = true;
1640 if (scanString(e.tail))
1641 result = true;
1642 if (result)
1643 e.noRemove = root.noRemove = true;
1644 return result;
1645 }
1646
1647 scan(f);
1648 }
1649 }
1650
1651 void applyNoRemoveDeps()
1652 {
1653 static void applyDeps(Entity e)
1654 {
1655 e.noRemove = true;
1656 foreach (d; e.dependencies)
1657 applyDeps(d);
1658 }
1659
1660 static void scan(Entity e)
1661 {
1662 if (e.noRemove)
1663 applyDeps(e);
1664 foreach (c; e.children)
1665 scan(c);
1666 }
1667
1668 scan(root);
1669
1670 // Propagate upwards
1671 static bool fill(Entity e)
1672 {
1673 foreach (c; e.children)
1674 e.noRemove |= fill(c);
1675 return e.noRemove;
1676 }
1677
1678 fill(root);
1679 }
1680
1681 void loadCoverage(string dir)
1682 {
1683 void scanFile(Entity f)
1684 {
1685 auto fn = buildPath(dir, setExtension(baseName(f.filename), "lst"));
1686 if (!exists(fn))
1687 return;
1688 writeln("Loading coverage file ", fn);
1689
1690 static bool covered(string line)
1691 {
1692 enforce(line.length >= 8 && line[7]=='|', "Invalid syntax in coverage file");
1693 line = line[0..7];
1694 return line != "0000000" && line != " ";
1695 }
1696
1697 auto lines = map!covered(splitLines(readText(fn))[0..$-1]);
1698 uint line = 0;
1699
1700 bool coverString(string s)
1701 {
1702 bool result;
1703 foreach (char c; s)
1704 {
1705 result |= lines[line];
1706 if (c == '\n')
1707 line++;
1708 }
1709 return result;
1710 }
1711
1712 bool cover(ref Entity e)
1713 {
1714 bool result;
1715 result |= coverString(e.head);
1716 foreach (ref c; e.children)
1717 result |= cover(c);
1718 result |= coverString(e.tail);
1719
1720 e.noRemove |= result;
1721 return result;
1722 }
1723
1724 foreach (ref c; f.children)
1725 f.noRemove |= cover(c);
1726 }
1727
1728 void scanFiles(Entity e)
1729 {
1730 if (e.isFile)
1731 scanFile(e);
1732 else
1733 foreach (c; e.children)
1734 scanFiles(c);
1735 }
1736
1737 scanFiles(root);
1738 }
1739
1740 void assignID(Entity e)
1741 {
1742 static int counter;
1743 e.id = ++counter;
1744 foreach (c; e.children)
1745 assignID(c);
1746 }
1747
1748 void dumpSet(string fn)
1749 {
1750 auto f = File(fn, "wb");
1751
1752 string printable(string s) { return s is null ? "null" : `"` ~ s.replace("\\", `\\`).replace("\"", `\"`).replace("\r", `\r`).replace("\n", `\n`) ~ `"`; }
1753 string printableFN(string s) { return "/*** " ~ s ~ " ***/"; }
1754
1755 bool[int] dependents;
1756 void scanDependents(Entity e)
1757 {
1758 foreach (d; e.dependencies)
1759 dependents[d.id] = true;
1760 foreach (c; e.children)
1761 scanDependents(c);
1762 }
1763 scanDependents(root);
1764
1765 void print(Entity e, int depth)
1766 {
1767 auto prefix = replicate(" ", depth);
1768
1769 // if (!fileLevel) { f.writeln(prefix, "[ ... ]"); continue; }
1770
1771 f.write(prefix);
1772 if (e.children.length == 0)
1773 {
1774 f.write(
1775 "[",
1776 e.noRemove ? "!" : "",
1777 " ",
1778 e.isFile ? e.filename ? printableFN(e.filename) ~ " " : null : e.head ? printable(e.head) ~ " " : null,
1779 e.tail ? printable(e.tail) ~ " " : null,
1780 e.comment ? "/* " ~ e.comment ~ " */ " : null,
1781 "]"
1782 );
1783 }
1784 else
1785 {
1786 f.writeln("[", e.noRemove ? "!" : "", e.comment ? " // " ~ e.comment : null);
1787 if (e.isFile) f.writeln(prefix, " ", printableFN(e.filename));
1788 if (e.head) f.writeln(prefix, " ", printable(e.head));
1789 foreach (c; e.children)
1790 print(c, depth+1);
1791 if (e.tail) f.writeln(prefix, " ", printable(e.tail));
1792 f.write(prefix, "]");
1793 }
1794 if (e.id in dependents || trace)
1795 f.write(" =", e.id);
1796 if (e.dependencies.length)
1797 {
1798 f.write(" =>");
1799 foreach (d; e.dependencies)
1800 f.write(" ", d.id);
1801 }
1802 f.writeln();
1803 }
1804
1805 print(root, 0);
1806
1807 f.close();
1808 }
1809
1810 void dumpToHtml(string fn)
1811 {
1812 auto buf = appender!string();
1813
1814 void dumpText(string s)
1815 {
1816 foreach (c; s)
1817 switch (c)
1818 {
1819 case '<':
1820 buf.put("<");
1821 break;
1822 case '>':
1823 buf.put(">");
1824 break;
1825 case '&':
1826 buf.put("&");
1827 break;
1828 default:
1829 buf.put(c);
1830 }
1831 }
1832
1833 void dump(Entity e)
1834 {
1835 if (e.isFile)
1836 {
1837 buf.put("<h1>");
1838 dumpText(e.filename);
1839 buf.put("</h1><pre>");
1840 foreach (c; e.children)
1841 dump(c);
1842 buf.put("</pre>");
1843 }
1844 else
1845 {
1846 buf.put("<span>");
1847 dumpText(e.head);
1848 foreach (c; e.children)
1849 dump(c);
1850 dumpText(e.tail);
1851 buf.put("</span>");
1852 }
1853 }
1854
1855 buf.put(q"EOT
1856 <style> pre span:hover { outline: 1px solid rgba(0,0,0,0.2); background-color: rgba(100,100,100,0.1 ); } </style>
1857 EOT");
1858
1859 dump(root);
1860
1861 std.file.write(fn, buf.data());
1862 }
1863
1864 void dumpText(string fn, ref Reduction r = nullReduction)
1865 {
1866 auto f = File(fn, "wt");
1867 dump(root, r, (string) {}, &f.write!string);
1868 f.close();
1869 }