1 /**
2 Copyright: Copyright (c) 2020, Joakim Brännström. All rights reserved.
3 License: MPL-2
4 Author: Joakim Brännström (joakim.brannstrom@gmx.com)
5 
6 This Source Code Form is subject to the terms of the Mozilla Public License,
7 v.2.0. If a copy of the MPL was not distributed with this file, You can obtain
8 one at http://mozilla.org/MPL/2.0/.
9 
10 A language independent AST specific for generating mutants both via the plain
11 source code manipulation but also mutant schematas.
12 */
13 module dextool.plugin.mutate.backend.analyze.ast;
14 
15 import logger = std.experimental.logger;
16 import std.algorithm : map, filter, among;
17 import std.array : Appender, appender, empty;
18 import std.exception : collectException;
19 import std.format : formattedWrite, format;
20 import std.meta : AliasSeq;
21 import std.range : isOutputRange;
22 
23 import my.optional;
24 import sumtype;
25 
26 import dextool.type : AbsolutePath, Path;
27 
28 static import dextool.plugin.mutate.backend.type;
29 
30 @safe:
31 
32 struct Ast {
33     import std.experimental.allocator.mallocator : Mallocator;
34     import my.alloc.class_;
35 
36     /// The language the mutation AST is based on.
37     dextool.plugin.mutate.backend.type.Language lang;
38 
39     Location[Node] locs;
40 
41     // a node can have a type
42     TypeId[Node] nodeTypes;
43     Types types;
44 
45     // a node can have been resolved to a symbolic value.
46     SymbolId[Node] nodeSymbols;
47     Symbols symbols;
48 
49     Node root;
50 
51     // Change the path and thus string in the saved locations to reduce the used memory.
52     Dedup!AbsolutePath paths;
53 
54     private {
55         Bundle!Mallocator bundle;
56     }
57 
58     ~this() nothrow {
59         release;
60     }
61 
62     T make(T, Args...)(auto ref Args args) {
63         import std.functional : forward;
64 
65         return bundle.make!T(forward!args);
66     }
67 
68     /// Release all nodes by destroying them and releasing the memory
69     void release() nothrow @trusted {
70         if (!bundle.empty) {
71             if (auto v = root in locs)
72                 logger.tracef("released AST for %s with objects %s", v.file,
73                         bundle.length).collectException;
74             else
75                 logger.tracef("released AST with %s objects", bundle.length).collectException;
76         }
77         bundle.release;
78 
79         paths = typeof(paths).init;
80         nodeTypes = null;
81         nodeSymbols = null;
82         locs = null;
83         root = null;
84     }
85 
86     void releaseCache() {
87         paths.release;
88     }
89 
90     void accept(VisitorT)(VisitorT v) {
91         v.visit(root);
92     }
93 
94     void put(Node n, Location l) {
95         // TODO: deduplicate the path because it will otherwise take up so much
96         // memory.....
97         l.file = paths.dedup(l.file);
98         locs[n] = l;
99     }
100 
101     void put(Node n, TypeId id) {
102         nodeTypes[n] = id;
103     }
104 
105     void put(Node n, SymbolId id) {
106         nodeSymbols[n] = id;
107     }
108 
109     Location location(Node n) {
110         if (auto v = n in locs) {
111             return *v;
112         }
113         return Location.init;
114     }
115 
116     Type type(Node n) {
117         if (auto v = n in nodeTypes) {
118             return types.get(*v);
119         }
120         return null;
121     }
122 
123     Optional!TypeId typeId(Node n) {
124         if (auto v = n in nodeTypes) {
125             return some(*v);
126         }
127         return none!TypeId;
128     }
129 
130     Symbol symbol(Node n) {
131         if (auto v = n in nodeSymbols) {
132             return symbols.get(*v);
133         }
134         return null;
135     }
136 
137     string toString() @safe {
138         auto buf = appender!string;
139         toString(buf);
140         return buf.data;
141     }
142 
143     void toString(Writer)(ref Writer w) if (isOutputRange!(Writer, char)) {
144         import std.range : put;
145 
146         formattedWrite(w, "Source language: %s\n", lang);
147 
148         auto res = () @trusted {
149             auto dump = new AstPrintVisitor(&this);
150             this.accept(dump);
151             return dump.buf.data;
152         }();
153         put(w, res);
154 
155         put(w, "Types:");
156         put(w, "\n");
157         types.toString(w);
158         put(w, "Symbols:");
159         put(w, "\n");
160         symbols.toString(w);
161     }
162 }
163 
164 class AstPrintVisitor : DepthFirstVisitor {
165     import std.range : put, repeat;
166 
167     Appender!string buf;
168     int depth;
169     int prevDepth;
170     char[] indent;
171     Ast* ast;
172 
173     this(Ast* ast) {
174         this.ast = ast;
175     }
176 
177     void toBuf(Node n) {
178         import std.conv : to;
179         import colorlog : color, Color;
180 
181         if (depth == 0) {
182             indent = null;
183         } else if (depth == prevDepth) {
184         } else if (depth > prevDepth) {
185             const diff = (depth - prevDepth - 1) * 2;
186             if (indent.length == 0) {
187             } else if (indent[$ - 2] == '`') {
188                 indent[$ - 1] = ' ';
189                 indent[$ - 2] = ' ';
190             } else {
191                 indent[$ - 1] = ' ';
192             }
193 
194             foreach (_; 0 .. diff)
195                 indent ~= "  ";
196 
197             if (n.children.length <= 1)
198                 indent ~= "`-";
199             else
200                 indent ~= "|-";
201         } else {
202             const diff = (prevDepth - depth) * 2;
203             indent = indent[0 .. $ - diff];
204 
205             if (indent.length != 0 && indent[$ - 2 .. $] == "| ") {
206                 indent[$ - 1] = '-';
207             }
208         }
209         put(buf, indent);
210 
211         void printNode() {
212             auto bl = () {
213                 if (n.blacklist)
214                     return " blacklist".color(Color.magenta).toString;
215                 return "";
216             }();
217             auto schemaBl = () {
218                 if (n.schemaBlacklist)
219                     return " !schema".color(Color.magenta).toString;
220                 return "";
221             }();
222             auto covBl = () {
223                 if (n.covBlacklist)
224                     return " !cov".color(Color.magenta).toString;
225                 return "";
226             }();
227             formattedWrite(buf, "%s %s%s%s%s",
228                     n.kind.to!string.color(Color.lightGreen),
229                     n.id.to!string.color(Color.lightYellow), bl, schemaBl, covBl);
230         }
231 
232         void printTypeSymbol(Node n) {
233             if (auto tyId = n in ast.nodeTypes) {
234                 auto ty = ast.types.get(*tyId);
235                 formattedWrite(buf, " %X", tyId.value);
236             }
237             if (auto syId = n in ast.nodeSymbols) {
238                 auto sy = ast.symbols.get(*syId);
239                 formattedWrite(buf, " %X:%s", syId.value, sy.value);
240             }
241         }
242 
243         switch (n.kind) {
244         case Kind.Function:
245             printNode;
246             printTypeSymbol((cast(Function) n).return_);
247             break;
248         case Kind.VarDecl:
249             printNode;
250             if ((cast(VarDecl) n).isConst) {
251                 put(buf, " const");
252             }
253             break;
254         default:
255             printNode;
256             if (isExpression(n.kind)) {
257                 printTypeSymbol(n);
258             }
259         }
260 
261         if (auto tmp = cast(BinaryOp) n) {
262             if (tmp.lhs !is null)
263                 formattedWrite(buf, " l:%s", tmp.lhs.id);
264             if (tmp.rhs !is null)
265                 formattedWrite(buf, " r:%s", tmp.rhs.id);
266         }
267 
268         if (auto l = ast.location(n)) {
269             formattedWrite(buf, " <%s:%s>", l.file.color(Color.cyan), l.posToString);
270         }
271         put(buf, "\n");
272 
273         prevDepth = depth;
274     }
275 
276     static foreach (N; Nodes) {
277         override void visit(N n) {
278             toBuf(n);
279             ++depth;
280 
281             auto op = () @trusted {
282                 if (auto v = cast(BinaryOp) n) {
283                     return v.operator;
284                 } else if (auto v = cast(UnaryOp) n) {
285                     return v.operator;
286                 }
287                 return null;
288             }();
289             if (op !is null) {
290                 visit(op);
291             }
292 
293             accept(n, this);
294             --depth;
295         }
296     }
297 }
298 
299 /// The interval in bytes that the node occupy. It is a closed->open set.
300 alias Interval = dextool.plugin.mutate.backend.type.Offset;
301 alias SourceLoc = dextool.plugin.mutate.backend.type.SourceLoc;
302 alias SourceLocRange = dextool.plugin.mutate.backend.type.SourceLocRange;
303 
304 struct Location {
305     import std.range : isOutputRange;
306 
307     AbsolutePath file;
308     Interval interval;
309     SourceLocRange sloc;
310 
311     this(Path f, Interval i, SourceLocRange s) {
312         file = f;
313         interval = i;
314         sloc = s;
315     }
316 
317     T opCast(T : bool)() @safe pure const nothrow {
318         return !file.empty;
319     }
320 
321     // Convert only the position in the file to a string.
322     string posToString() @safe const {
323         return format!"[%s:%s-%s:%s]:[%s:%s]"(sloc.begin.line, sloc.begin.column,
324                 sloc.end.line, sloc.end.column, interval.begin, interval.end);
325     }
326 
327     string toString() @safe const {
328         auto buf = appender!string;
329         toString(buf);
330         return buf.data;
331     }
332 
333     void toString(Writer)(ref Writer w) const if (isOutputRange!(Writer, char)) {
334         import std.format : formattedWrite;
335 
336         formattedWrite!"%s:%s"(w, file, posToString);
337     }
338 }
339 
340 private ulong uniqueNodeId() {
341     static ulong next;
342     return next++;
343 }
344 
345 abstract class Node {
346     private enum Property {
347         blacklist = 0x1,
348         schemaBlacklist = 0x2,
349         covBlacklist = 0x4
350     }
351 
352     private ubyte prop;
353 
354     Kind kind() const;
355     ulong id() @safe pure nothrow const @nogc scope;
356 
357     Node[] children;
358 
359     /** If the node is blacklisted from being mutated. This is for example when
360      * the node covers a C macro.
361      */
362     bool blacklist() {
363         return Property.blacklist & prop;
364     }
365 
366     void blacklist(bool x) {
367         if (x)
368             prop |= Property.blacklist;
369         else
370             prop &= ~Property.blacklist;
371     }
372 
373     /** If the node should not be part of mutant schemata because it is highly
374      * likely to introduce compilation errors. It is for example likely when
375      * operators are overloaded.
376      */
377     bool schemaBlacklist() {
378         return (Property.schemaBlacklist & prop) != 0;
379     }
380 
381     void schemaBlacklist(bool x) {
382         if (x)
383             prop |= Property.schemaBlacklist;
384         else
385             prop &= ~Property.schemaBlacklist;
386     }
387 
388     /** Block nodes that have a high probability of failing from being coverage instrumented.
389      *
390      */
391     bool covBlacklist() {
392         return (Property.covBlacklist & prop) != 0;
393     }
394 
395     void covBlacklist(bool x) {
396         if (x)
397             prop |= Property.covBlacklist;
398         else
399             prop &= ~Property.covBlacklist;
400     }
401 
402     bool opEquals(Kind k) {
403         return kind == k;
404     }
405 
406     override bool opEquals(Object o) {
407         auto rhs = cast(const Node) o;
408         return (rhs && (id == rhs.id));
409     }
410 
411     override size_t toHash() @safe pure nothrow const @nogc scope {
412         return id.hashOf();
413     }
414 }
415 
416 /**
417  * It is optional to add the members visitPush/visitPop to push/pop the nodes that are visited.
418  * The parent will always have been the last pushed.
419  */
420 void accept(VisitorT)(Node n, VisitorT v) {
421     static string mixinSwitch() {
422         import std.conv : text;
423         import std.traits : EnumMembers;
424 
425         string s;
426         s ~= "final switch(c.kind) {\n";
427         foreach (kind; [EnumMembers!Kind]) {
428             const k = text(kind);
429             s ~= format!"case Kind." ~ k ~ ": v.visit(cast(" ~ k ~ ") c); break;\n";
430         }
431         s ~= "}";
432         return s;
433     }
434 
435     static if (__traits(hasMember, VisitorT, "visitPush"))
436         v.visitPush(n);
437     foreach (c; n.children) {
438         mixin(mixinSwitch);
439     }
440 
441     static if (__traits(hasMember, VisitorT, "visitPop"))
442         v.visitPop(n);
443 }
444 
445 /// All nodes that a visitor must be able to handle.
446 // must be sorted such that the leaf nodes are at the top.
447 // dfmt off
448 alias Nodes = AliasSeq!(
449     BinaryOp,
450     Block,
451     Branch,
452     BranchBundle,
453     Call,
454     Condition,
455     Constructor,
456     Expr,
457     Function,
458     Loop,
459     Node,
460     OpAdd,
461     OpAnd,
462     OpAndBitwise,
463     OpAssign,
464     OpAssignAdd,
465     OpAssignAndBitwise,
466     OpAssignDiv,
467     OpAssignMod,
468     OpAssignMul,
469     OpAssignOrBitwise,
470     OpAssignSub,
471     OpDiv,
472     OpEqual,
473     OpGreater,
474     OpGreaterEq,
475     OpLess,
476     OpLessEq,
477     OpMod,
478     OpMul,
479     OpNegate,
480     OpNotEqual,
481     OpOr,
482     OpOrBitwise,
483     OpSub,
484     Operator,
485     Poision,
486     Return,
487     Statement,
488     TranslationUnit,
489     UnaryOp,
490     VarDecl,
491     VarRef,
492     Literal,
493 );
494 
495 // It should be possible to generate the enum from Nodes. How?
496 enum Kind {
497     BinaryOp,
498     Block,
499     Branch,
500     BranchBundle,
501     Call,
502     Condition,
503     Constructor,
504     Expr,
505     Function,
506     Literal,
507     Loop,
508     Node,
509     OpAdd,
510     OpAnd,
511     OpAndBitwise,
512     OpAssign,
513     OpAssignAdd,
514     OpAssignAndBitwise,
515     OpAssignDiv,
516     OpAssignMod,
517     OpAssignMul,
518     OpAssignOrBitwise,
519     OpAssignSub,
520     OpDiv,
521     OpEqual,
522     OpGreater,
523     OpGreaterEq,
524     OpLess,
525     OpLessEq,
526     OpMod,
527     OpMul,
528     OpNegate,
529     OpNotEqual,
530     OpOr,
531     OpOrBitwise,
532     OpSub,
533     Operator,
534     Poision,
535     Return,
536     Statement,
537     TranslationUnit,
538     UnaryOp,
539     VarDecl,
540     VarRef,
541 }
542 
543 alias ExpressionKind = AliasSeq!(
544     Kind.BinaryOp,
545     Kind.Call,
546     Kind.Condition,
547     Kind.Constructor,
548     Kind.Expr,
549     Kind.OpAdd,
550     Kind.OpAnd,
551     Kind.OpAndBitwise,
552     Kind.OpAssign,
553     Kind.OpDiv,
554     Kind.OpEqual,
555     Kind.OpGreater,
556     Kind.OpGreaterEq,
557     Kind.OpLess,
558     Kind.OpLessEq,
559     Kind.OpMod,
560     Kind.OpMul,
561     Kind.OpNegate,
562     Kind.OpNotEqual,
563     Kind.OpOr,
564     Kind.OpOrBitwise,
565     Kind.OpSub,
566     Kind.Return,
567     Kind.UnaryOp,
568     Kind.VarDecl,
569     Kind.VarRef,
570     Kind.Literal,
571 );
572 // dfmt on
573 
574 bool isExpression(Kind k) @safe pure nothrow @nogc {
575     return k.among(ExpressionKind) != 0;
576 }
577 
578 interface Visitor {
579     static foreach (N; Nodes) {
580         void visit(N);
581     }
582 }
583 
584 // TODO: implement a breath first.
585 class DepthFirstVisitor : Visitor {
586     int visitDepth;
587 
588     void visitPush(Node n) {
589     }
590 
591     void visitPop(Node n) {
592     }
593 
594     static foreach (N; Nodes) {
595         override void visit(N n) {
596             ++visitDepth;
597             accept(n, this);
598             --visitDepth;
599         }
600     }
601 }
602 
603 /** A phantom node that carry semantic information about its children. It
604  * "poisons" all children.
605  */
606 class Poision : Node {
607     mixin(nodeImpl!(typeof(this)));
608 }
609 
610 class TranslationUnit : Node {
611     mixin(nodeImpl!(typeof(this)));
612 }
613 
614 class Statement : Node {
615     mixin(nodeImpl!(typeof(this)));
616 }
617 
618 class Loop : Node {
619     mixin(nodeImpl!(typeof(this)));
620 }
621 
622 class Expr : Node {
623     mixin(nodeImpl!(typeof(this)));
624 }
625 
626 /// A function definition.
627 class Function : Node {
628     mixin(nodeImpl!(typeof(this)));
629 
630     /// If the function has a return type it is associated with this expression.
631     Return return_;
632 }
633 
634 /// A constructor for a variable.
635 class Constructor : Expr {
636     mixin(nodeImpl!(typeof(this)));
637 }
638 
639 /// A function call.
640 class Call : Expr {
641     mixin(nodeImpl!(typeof(this)));
642 }
643 
644 /// A constant.
645 class Literal : Expr {
646     mixin(nodeImpl!(typeof(this)));
647 }
648 
649 /// The operator itself in a binary operator expression.
650 class Operator : Node {
651     mixin(nodeImpl!(typeof(this)));
652 }
653 
654 /** A block of code such such as a local scope enclosed by brackets, `{}`.
655  *
656  * It is intended to be possible to delete it. But it may need to be further
657  * analyzed for e.g. `Return` nodes.
658  */
659 class Block : Node {
660     mixin(nodeImpl!(typeof(this)));
661 }
662 
663 /** Multiple branches are contained in the bundle that can be e.g. deleted.
664  *
665  * This can, in C/C++, be either a whole if-statement or switch.
666  */
667 class BranchBundle : Node {
668     mixin(nodeImpl!(typeof(this)));
669 }
670 
671 /** The code for one of the branches resulting from a condition.
672  *
673  * It can be the branches in a if-else statement or a case branch for languages
674  * such as C/C++.
675  *
676  * The important aspect is that the branch is not an expression. It can't be
677  * evaluated to a value of a type.
678  */
679 class Branch : Node {
680     mixin(nodeImpl!(typeof(this)));
681 
682     // The inside of a branch node wherein code can be injected.
683     Block inside;
684 }
685 
686 /// Results in the bottom type or up.
687 class Return : Expr {
688     mixin(nodeImpl!(typeof(this)));
689 }
690 
691 /// A condition wraps "something" which always evaluates to a boolean.
692 class Condition : Expr {
693     mixin(nodeImpl!(typeof(this)));
694 }
695 
696 class VarDecl : Expr {
697     mixin(nodeImpl!(typeof(this)));
698     bool isConst;
699 }
700 
701 class VarRef : Expr {
702     mixin(nodeImpl!(typeof(this)));
703     // should always refer to something
704     VarDecl to;
705 
706     this(VarDecl to) {
707         this();
708         this.to = to;
709     }
710 
711     invariant {
712         assert(to !is null);
713     }
714 }
715 
716 class UnaryOp : Expr {
717     mixin(nodeImpl!(typeof(this)));
718 
719     Operator operator;
720     Expr expr;
721 
722     this(Operator op, Expr expr) {
723         this();
724         this.operator = op;
725         this.expr = expr;
726     }
727 }
728 
729 class OpNegate : UnaryOp {
730     mixin(nodeImpl!(typeof(this)));
731 }
732 
733 class BinaryOp : Expr {
734     mixin(nodeImpl!(typeof(this)));
735 
736     Operator operator;
737     Expr lhs;
738     Expr rhs;
739 
740     this(Operator op, Expr lhs, Expr rhs) {
741         this();
742         this.operator = op;
743         this.lhs = lhs;
744         this.rhs = rhs;
745     }
746 }
747 
748 class OpAssign : BinaryOp {
749     mixin(nodeImpl!(typeof(this)));
750 }
751 
752 class OpAssignAdd : BinaryOp {
753     mixin(nodeImpl!(typeof(this)));
754 }
755 
756 class OpAssignSub : BinaryOp {
757     mixin(nodeImpl!(typeof(this)));
758 }
759 
760 class OpAssignMul : BinaryOp {
761     mixin(nodeImpl!(typeof(this)));
762 }
763 
764 class OpAssignDiv : BinaryOp {
765     mixin(nodeImpl!(typeof(this)));
766 }
767 
768 class OpAssignMod : BinaryOp {
769     mixin(nodeImpl!(typeof(this)));
770 }
771 
772 class OpAssignAndBitwise : BinaryOp {
773     mixin(nodeImpl!(typeof(this)));
774 }
775 
776 class OpAssignOrBitwise : BinaryOp {
777     mixin(nodeImpl!(typeof(this)));
778 }
779 
780 class OpAdd : BinaryOp {
781     mixin(nodeImpl!(typeof(this)));
782 }
783 
784 class OpSub : BinaryOp {
785     mixin(nodeImpl!(typeof(this)));
786 }
787 
788 class OpMul : BinaryOp {
789     mixin(nodeImpl!(typeof(this)));
790 }
791 
792 class OpDiv : BinaryOp {
793     mixin(nodeImpl!(typeof(this)));
794 }
795 
796 class OpMod : BinaryOp {
797     mixin(nodeImpl!(typeof(this)));
798 }
799 
800 class OpAnd : BinaryOp {
801     mixin(nodeImpl!(typeof(this)));
802 }
803 
804 class OpAndBitwise : BinaryOp {
805     mixin(nodeImpl!(typeof(this)));
806 }
807 
808 class OpOr : BinaryOp {
809     mixin(nodeImpl!(typeof(this)));
810 }
811 
812 class OpOrBitwise : BinaryOp {
813     mixin(nodeImpl!(typeof(this)));
814 }
815 
816 class OpEqual : BinaryOp {
817     mixin(nodeImpl!(typeof(this)));
818 }
819 
820 class OpLess : BinaryOp {
821     mixin(nodeImpl!(typeof(this)));
822 }
823 
824 class OpGreater : BinaryOp {
825     mixin(nodeImpl!(typeof(this)));
826 }
827 
828 class OpLessEq : BinaryOp {
829     mixin(nodeImpl!(typeof(this)));
830 }
831 
832 class OpGreaterEq : BinaryOp {
833     mixin(nodeImpl!(typeof(this)));
834 }
835 
836 class OpNotEqual : BinaryOp {
837     mixin(nodeImpl!(typeof(this)));
838 }
839 
840 RetT makeId(RetT, T)(T data) {
841     import my.hash : makeCrc64Iso;
842 
843     auto a = makeCrc64Iso(cast(const(ubyte)[]) data);
844     return RetT(a.c0);
845 }
846 
847 RetT makeUniqueId(RetT)() {
848     import std.random : uniform;
849 
850     return RetT(uniform(long.min, long.max));
851 }
852 
853 class Type {
854     private const ulong id_;
855 
856     Range range;
857 
858     this() {
859         this(Range.makeInf);
860     }
861 
862     this(Range r) {
863         this.range = r;
864         id_ = uniqueNodeId;
865     }
866 
867     TypeKind kind() const {
868         return TypeKind.bottom;
869     }
870 
871     ulong id() @safe pure nothrow const @nogc scope {
872         return id_;
873     }
874 
875     override bool opEquals(Object o) {
876         auto rhs = cast(const Type) o;
877         return (rhs && (id == rhs.id));
878     }
879 
880     override size_t toHash() @safe pure nothrow const @nogc scope {
881         return id.hashOf();
882     }
883 }
884 
885 final class DiscreteType : Type {
886     this(Range r) {
887         super(r);
888     }
889 
890     override TypeKind kind() const {
891         return TypeKind.discrete;
892     }
893 }
894 
895 final class ContinuesType : Type {
896     this(Range r) {
897         super(r);
898     }
899 
900     override TypeKind kind() const {
901         return TypeKind.continues;
902     }
903 }
904 
905 final class UnorderedType : Type {
906     this(Range r) {
907         super(r);
908     }
909 
910     override TypeKind kind() const {
911         return TypeKind.unordered;
912     }
913 }
914 
915 final class BooleanType : Type {
916     this(Range r) {
917         super(r);
918     }
919 
920     override TypeKind kind() const {
921         return TypeKind.boolean;
922     }
923 }
924 
925 final class VoidType : Type {
926     this() {
927         super();
928     }
929 
930     override TypeKind kind() const {
931         return TypeKind.top;
932     }
933 }
934 
935 enum TypeKind {
936     // It can be anything, practically useless for mutation testing because it
937     // doesn't provide any logic that can be used to e.g. generate
938     // "intelligent" ROR mutants.
939     bottom,
940     /// integers, enums
941     discrete,
942     /// floating point values
943     continues,
944     /// no order exists between values in the type thus unable to do ROR
945     unordered,
946     ///
947     boolean,
948     /// a top type is nothing
949     top,
950 }
951 
952 struct Value {
953     import std.traits : TemplateArgsOf;
954 
955     static struct NegInf {
956     }
957 
958     static struct PosInf {
959     }
960 
961     static struct Int {
962         // TODO: change to BigInt?
963         long value;
964     }
965 
966     static struct Bool {
967         bool value;
968     }
969 
970     alias Value = SumType!(NegInf, PosInf, Int, Bool);
971     Value value;
972 
973     static foreach (T; TemplateArgsOf!Value) {
974         this(T a) {
975             value = Value(a);
976         }
977     }
978 
979     string toString() @safe pure const {
980         auto buf = appender!string;
981         toString(buf);
982         return buf.data;
983     }
984 
985     void toString(Writer)(ref Writer w) const if (isOutputRange!(Writer, char)) {
986         import std.conv : to;
987         import std.range : put;
988 
989         value.match!((const NegInf a) => put(w, "-inf"), (const PosInf a) => put(w,
990                 "+inf"), (const Int a) => put(w, a.value.to!string),
991                 (const Bool a) => put(w, a.value.to!string));
992     }
993 }
994 
995 struct Range {
996     static makeInf() {
997         return Range(Value(Value.NegInf.init), Value(Value.PosInf.init));
998     }
999 
1000     static makeBoolean() {
1001         return Range(Value(Value.Bool(false)), Value(Value.Bool(true)));
1002     }
1003 
1004     Value low;
1005     Value up;
1006 
1007     this(Value low, Value up) {
1008         this.low = low;
1009         this.up = up;
1010     }
1011 
1012     enum CompareResult {
1013         onLowerBound,
1014         onUpperBound,
1015         // the value and the range fully overlap each other. This happens when
1016         // the range is only one value.
1017         overlap,
1018         inside,
1019         outside
1020     }
1021 
1022     CompareResult compare(Value v) {
1023         CompareResult negInf() {
1024             return low.value.match!((Value.NegInf a) => CompareResult.onLowerBound,
1025                     (Value.PosInf a) => CompareResult.outside,
1026                     (Value.Int a) => CompareResult.outside, (Value.Bool a) => CompareResult.outside);
1027         }
1028 
1029         CompareResult posInf() {
1030             return up.value.match!((Value.NegInf a) => CompareResult.onUpperBound,
1031                     (Value.PosInf a) => CompareResult.outside,
1032                     (Value.Int a) => CompareResult.outside, (Value.Bool a) => CompareResult.outside);
1033         }
1034 
1035         CompareResult value(long v) {
1036             const l = low.value.match!((Value.NegInf a) => CompareResult.inside,
1037                     (Value.PosInf a) => CompareResult.outside, (Value.Int a) {
1038                 if (a.value < v)
1039                     return CompareResult.inside;
1040                 if (a.value == v)
1041                     return CompareResult.onLowerBound;
1042                 return CompareResult.outside;
1043             }, (Value.Bool a) => CompareResult.outside);
1044 
1045             const u = up.value.match!((Value.NegInf a) => CompareResult.outside,
1046                     (Value.PosInf a) => CompareResult.inside, (Value.Int a) {
1047                 if (a.value > v)
1048                     return CompareResult.inside;
1049                 if (a.value == v)
1050                     return CompareResult.onUpperBound;
1051                 return CompareResult.outside;
1052             }, (Value.Bool a) => CompareResult.outside);
1053 
1054             if (l == CompareResult.inside && u == CompareResult.inside)
1055                 return CompareResult.inside;
1056             if (l == CompareResult.onLowerBound && u == CompareResult.onUpperBound)
1057                 return CompareResult.overlap;
1058             if (l == CompareResult.onLowerBound)
1059                 return l;
1060             if (u == CompareResult.onUpperBound)
1061                 return u;
1062             assert(l == CompareResult.outside || u == CompareResult.outside);
1063             return CompareResult.outside;
1064         }
1065 
1066         CompareResult boolean(bool v) {
1067             // TODO: fix this
1068             return CompareResult.outside;
1069         }
1070 
1071         return v.value.match!((Value.NegInf a) => negInf,
1072                 (Value.PosInf a) => posInf, (Value.Int a) => value(a.value),
1073                 (Value.Bool a) => boolean(a.value));
1074     }
1075 
1076     string toString() @safe pure const {
1077         auto buf = appender!string;
1078         toString(buf);
1079         return buf.data;
1080     }
1081 
1082     void toString(Writer)(ref Writer w) const if (isOutputRange!(Writer, char)) {
1083         import std.range : put;
1084 
1085         put(w, "[");
1086         low.toString(w);
1087         put(w, ":");
1088         up.toString(w);
1089         put(w, "]");
1090     }
1091 }
1092 
1093 struct TypeId {
1094     ulong value;
1095 
1096     size_t toHash() @safe pure nothrow const @nogc {
1097         return value.hashOf;
1098     }
1099 }
1100 
1101 TypeId makeTypeId(T)(T data) {
1102     return makeId!TypeId(data);
1103 }
1104 
1105 TypeId makeUniqueTypeId() {
1106     return makeUniqueId!TypeId;
1107 }
1108 
1109 struct Types {
1110     Type[TypeId] types;
1111 
1112     void require(TypeId id, Type t) {
1113         if (id !in types) {
1114             types[id] = t;
1115         }
1116     }
1117 
1118     void set(TypeId id, Type t) {
1119         types[id] = t;
1120     }
1121 
1122     Type get(TypeId id) {
1123         if (auto v = id in types) {
1124             return *v;
1125         }
1126         return null;
1127     }
1128 
1129     bool hasId(TypeId id) {
1130         return (id in types) !is null;
1131     }
1132 
1133     string toString() @safe const {
1134         auto buf = appender!string;
1135         toString(buf);
1136         return buf.data;
1137     }
1138 
1139     void toString(Writer)(ref Writer w) const if (isOutputRange!(Writer, char)) {
1140         import std.format : formattedWrite;
1141         import std.range : put;
1142 
1143         foreach (kv; types.byKeyValue) {
1144             formattedWrite(w, "%X:%s:%s", kv.key.value, kv.value.kind, kv.value.range);
1145             put(w, "\n");
1146         }
1147     }
1148 }
1149 
1150 class Symbol {
1151     Value value;
1152 
1153     this() {
1154         this(Value(Value.PosInf.init));
1155     }
1156 
1157     this(Value v) {
1158         this.value = v;
1159     }
1160 
1161     SymbolKind kind() const {
1162         return SymbolKind.unknown;
1163     }
1164 }
1165 
1166 final class DiscretSymbol : Symbol {
1167     this(Value r) {
1168         super(r);
1169     }
1170 
1171     override SymbolKind kind() const {
1172         return SymbolKind.discret;
1173     }
1174 }
1175 
1176 final class ContinuesSymbol : Symbol {
1177     this(Value r) {
1178         super(r);
1179     }
1180 
1181     override SymbolKind kind() const {
1182         return SymbolKind.continues;
1183     }
1184 }
1185 
1186 final class BooleanSymbol : Symbol {
1187     this(Value r) {
1188         super(r);
1189     }
1190 
1191     override SymbolKind kind() const {
1192         return SymbolKind.boolean;
1193     }
1194 }
1195 
1196 enum SymbolKind {
1197     /// the symbol wasn't able to evaluate to something useful
1198     unknown,
1199     /// integers, enums
1200     discret,
1201     /// floating point values
1202     continues,
1203     ///
1204     boolean,
1205 }
1206 
1207 struct SymbolId {
1208     ulong value;
1209 
1210     size_t toHash() @safe pure nothrow const @nogc {
1211         return value.hashOf;
1212     }
1213 }
1214 
1215 SymbolId makeSymbolId(T)(T data) {
1216     return makeId!SymbolId(data);
1217 }
1218 
1219 SymbolId makeUniqueSymbolId() {
1220     return makeUniqueId!SymbolId;
1221 }
1222 
1223 struct Symbols {
1224     Symbol[SymbolId] symbols;
1225 
1226     void require(SymbolId id, Symbol s) {
1227         if (id !in symbols) {
1228             symbols[id] = s;
1229         }
1230     }
1231 
1232     void set(SymbolId id, Symbol s) {
1233         symbols[id] = s;
1234     }
1235 
1236     Symbol get(SymbolId id) {
1237         if (auto v = id in symbols) {
1238             return *v;
1239         }
1240         return null;
1241     }
1242 
1243     bool hasId(SymbolId id) {
1244         return (id in symbols) !is null;
1245     }
1246 
1247     string toString() @safe const {
1248         auto buf = appender!string;
1249         toString(buf);
1250         return buf.data;
1251     }
1252 
1253     void toString(Writer)(ref Writer w) const if (isOutputRange!(Writer, char)) {
1254         foreach (kv; symbols.byKeyValue) {
1255             formattedWrite(w, "%X:%s:%s\n", kv.key.value, kv.value.kind, kv.value.value);
1256         }
1257     }
1258 }
1259 
1260 /// Breath first visit of nodes.
1261 struct BreathFirstRange {
1262     import my.container.vector;
1263 
1264     Vector!Node nodes;
1265 
1266     this(Node n) {
1267         nodes.put(n);
1268     }
1269 
1270     Node front() @safe pure nothrow {
1271         assert(!empty, "Can't get front of an empty range");
1272         return nodes.front;
1273     }
1274 
1275     void popFront() @safe pure nothrow {
1276         assert(!empty, "Can't pop front of an empty range");
1277         nodes.put(nodes.front.children);
1278         nodes.popFront;
1279     }
1280 
1281     bool empty() @safe pure nothrow const @nogc {
1282         return nodes.empty;
1283     }
1284 }
1285 
1286 private:
1287 
1288 string nodeImpl(T)() {
1289     return `
1290     private const ulong id_;
1291 
1292     override ulong id() @safe pure nothrow const @nogc scope { return id_; }
1293 
1294     override Kind kind() const {
1295         return Kind.` ~ T.stringof ~ `;
1296     }
1297 
1298     this() {
1299         id_ = uniqueNodeId;
1300     }`;
1301 }
1302 
1303 string typeImpl() {
1304     return `
1305     private const ulong id_;
1306     override ulong id() @safe pure nothrow const @nogc scope { return id_; }
1307     this() {
1308         id_ = uniqueNodeId;
1309     }`;
1310 }
1311 
1312 /// Dedup the paths to reduce the required memory.
1313 struct Dedup(T) {
1314     T[ulong] cache;
1315     /// Number of deduplications.
1316     long count;
1317     /// ".length" accumulated of items deduplicated.
1318     long lengthAccum;
1319 
1320     T dedup(T p) {
1321         import std.traits : hasMember;
1322 
1323         const cs = p.toHash;
1324         if (auto v = cs in cache) {
1325             ++count;
1326             static if (hasMember!(T, "length"))
1327                 lengthAccum += p.length;
1328             return *v;
1329         }
1330 
1331         cache[cs] = p;
1332         return p;
1333     }
1334 
1335     void release() {
1336         cache = typeof(cache).init;
1337     }
1338 }