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 }