1 // Written in the D programming language. 2 3 /++ 4 This module implements fast open multi-_methods. 5 6 Open _methods are like virtual functions, except that they are free functions, 7 living outside of any class. Multi-_methods can take into account the dynamic 8 types of more than one argument to select the most specialized variant of the 9 function. 10 11 This implementation uses compressed dispatch tables to deliver a performance 12 similar to ordinary virtual function calls, while minimizing the size of the 13 dispatch tables in presence of multiple virtual arguments. 14 15 $(B CAVEAT): this module uses the deprecated `deallocator` field in the 16 `ClassInfo` structure to store a pointer similar to a `vptr` . It is thus 17 incompatible with classes that define a `delete` member, and with modules 18 that use this field for their own purpose. 19 20 Synopsis of openmethods: 21 --- 22 23 import openmethods; // import lib 24 mixin(registerMethods); // once per module - don't forget! 25 26 interface Animal {} 27 class Dog : Animal {} 28 class Pitbull : Dog {} 29 class Cat : Animal {} 30 class Dolphin : Animal {} 31 32 // open method with single argument <=> virtual function "from outside" 33 string kick(virtual!Animal); 34 35 @method // implement 'kick' for dogs 36 string _kick(Dog x) // note the underscore 37 { 38 return "bark"; 39 } 40 41 @method("kick") // use a different name for specialization 42 string notGoodIdea(Pitbull x) 43 { 44 return next!kick(x) ~ " and bite"; // aka call 'super' 45 } 46 47 // multi-method 48 string meet(virtual!Animal, virtual!Animal); 49 50 // 'meet' implementations 51 @method 52 string _meet(Animal, Animal) 53 { 54 return "ignore"; 55 } 56 57 @method 58 string _meet(Dog, Dog) 59 { 60 return "wag tail"; 61 } 62 63 @method 64 string _meet(Dog, Cat) 65 { 66 return "chase"; 67 } 68 69 void main() 70 { 71 updateMethods(); // once per process - don't forget! 72 73 import std.stdio; 74 75 Animal rex = new Pitbull, snoopy = new Dog; 76 writeln("kick snoopy: ", kick(snoopy)); // bark 77 writeln("kick rex: ", kick(rex)); // bark and bite 78 79 Animal felix = new Cat, flipper = new Dolphin; 80 writeln("rex meets felix: ", meet(rex, felix)); // chase 81 writeln("rex meets snoopy: ", meet(rex, snoopy)); // wag tail 82 writeln("rex meets flipper: ", meet(rex, flipper)); // ignore 83 } 84 --- 85 86 Copyright: Copyright Jean-Louis Leroy 2017 87 88 License: $(LINK2 http://boost.org/LICENSE_1_0.txt, Boost License 1.0). 89 90 Authors: Jean-Louis Leroy 2017 91 +/ 92 93 module openmethods; 94 95 import std.traits; 96 import std.format; 97 import std.meta; 98 import std.algorithm; 99 import std.algorithm.iteration; 100 import std.range; 101 import std.bitmanip; 102 103 version (explain) { 104 import std.stdio; 105 } 106 107 version (traceCalls) { 108 import std.stdio; 109 } 110 111 // ============================================================================ 112 // Pubic stuff 113 114 /++ 115 Mark a parameter as virtual, and declare a method. 116 117 A new function is introduced in the current scope. It has the same name as the 118 declared method; its parameter consists in the declared parameters, stripped 119 from the `virtual!` qualifier. Calls to this function resolve to the most 120 specific method that matches the arguments. 121 122 The rules for determining the most specific function are exactly the same as 123 those that guide the resolution of function calls in presence of overloads - 124 only the resolution happens at run time, taking into account the argument's 125 $(I dynamic) type. In contrast, the normal function overload resolution is a 126 compile time mechanism that takes into account the $(I static) type of the 127 arguments. 128 129 Examples: 130 --- 131 Matrix times(double, virtual!Matrix); 132 string fight(virtual!Character, virtual!Creature, virtual!Device); 133 134 Matrix a = new DiagonalMatrix(...); 135 auto result = times(2, a); 136 137 fight(player, room.guardian, bag[item]); 138 --- 139 +/ 140 141 class virtual(T) 142 { 143 } 144 145 /++ 146 Used as an attribute: add an override to a method. 147 148 If called without argument, the function name must consist in a method name, 149 prefixed with an underscore. The function is added to the method as a 150 specialization. 151 152 If called with a string argument, it is interpreted as the name of the method 153 to specialize. The function name can then be any valid identifier. This is 154 useful to allow one override to call a specific override without going through 155 the dynamic dispatch mechanism. 156 157 Examples: 158 --- 159 @method 160 string _fight(Character x, Creature y, Axe z) 161 { 162 ... 163 } 164 165 @method("times") 166 Matrix doubleTimesDiagonal(double a, immutable(DiagonalMatrix) b) 167 { 168 ... 169 } 170 --- 171 172 +/ 173 174 struct method 175 { 176 this(string name) 177 { 178 id = name; 179 } 180 181 string id; 182 } 183 184 /++ Call the _next most specialized override if it exists. In other words, call 185 the override that would have been called if this one had not been defined. 186 187 Examples: 188 --- 189 void inspect(virtual!Vehicle, virtual!Inspector); 190 191 @method 192 void _inspect(Vehicle v, Inspector i) 193 { 194 writeln("Inspect vehicle."); 195 } 196 197 @method 198 void _inspect(Car v, Inspector i) 199 { 200 next!inspect(v, i); 201 writeln("Inspect seat belts."); 202 } 203 204 @method 205 void _inspect(Car v, StateInspector i) 206 { 207 next!inspect(v, i); 208 writeln("Check insurance."); 209 } 210 211 ... 212 213 Vehicle car = new Car; 214 Inspector inspector = new StateInspector; 215 inspect(car, inspector); // Inspect vehicle. Inspect seat belts. Check insurance. 216 --- 217 +/ 218 219 auto next(alias F, T...)(T args) 220 { 221 alias M = typeof(F(MethodTag.init, T.init)); 222 return M.nextPtr!(T)(args); 223 } 224 225 /++ Used as a string mixin: register the methods declaration and definitions in 226 the current module. 227 228 Examples: 229 --- 230 import openmethods; 231 mixin(registerMethods); 232 --- 233 +/ 234 235 string registerMethods(string moduleName = __MODULE__) 236 { 237 return format("mixin(_registerMethods!%s);\nmixin _registerSpecs!%s;\n", 238 moduleName, moduleName); 239 } 240 241 /++ 242 Update the runtime dispatch tables. Must be called once before calling any method. Typically this is done at the beginning of `main`. 243 +/ 244 245 void updateMethods() 246 { 247 Runtime rt; 248 rt.update(); 249 } 250 251 bool needUpdateMethods() 252 { 253 return Runtime.needUpdate; 254 } 255 256 /++ 257 Information passed to the error handler function. 258 259 +/ 260 261 struct MethodError 262 { 263 enum { NotImplemented = 1, AmbiguousCall }; 264 int reason; 265 string functionName; 266 TypeInfo[] args; 267 } 268 269 void defaultMethodErrorHandler(MethodError error) 270 { 271 import std.stdio; 272 stderr.writefln("call to %s(%s) is %s, aborting...", 273 error.functionName, 274 error.args.map!(a => a.toString).join(", "), 275 error.reason == MethodError.NotImplemented 276 ? "not implemented" : "ambiguous"); 277 import core.stdc.stdlib : abort; 278 abort(); 279 } 280 281 alias MethodErrorHandler = void function(MethodError error); 282 283 MethodErrorHandler errorHandler = &defaultMethodErrorHandler; 284 285 /++ 286 Set the function that is called if a method cannot be called with the 287 arguments. Default is to `abort` the program. 288 +/ 289 290 void function(MethodError error) 291 setMethodErrorHandler(void function(MethodError error) handler) 292 { 293 auto prev = errorHandler; 294 errorHandler = handler; 295 return prev; 296 } 297 298 // ============================================================================ 299 // Private parts. This doesn't exist. If you believe it does and use it, on 300 // your head be it. 301 302 enum IsVirtual(T) = false; 303 enum IsVirtual(T : virtual!U, U) = true; 304 305 alias VirtualType(T : virtual!U, U) = U; 306 307 // enum VirtualArity(QP...) = 1 + VirtualArity!(QP[1..$]) 308 // if IsVirtual!(QP[0]); 309 310 // enum VirtualArity(QP...) = VirtualArity!(QP[1..$]) 311 // if !IsVirtual!(QP[0]); 312 313 // enum VirtualArity(QP...) = 0 314 // if QP.length == 0; 315 316 template VirtualArity(QP...) 317 { 318 static if (QP.length == 0) { 319 enum VirtualArity = 0; 320 } else static if (IsVirtual!(QP[0])) { 321 enum VirtualArity = 1 + VirtualArity!(QP[1..$]); 322 } else { 323 enum VirtualArity = VirtualArity!(QP[1..$]); 324 } 325 } 326 327 template CallParams(T...) 328 { 329 static if (T.length == 0) { 330 alias CallParams = AliasSeq!(); 331 } else { 332 static if (IsVirtual!(T[0])) { 333 alias CallParams = AliasSeq!(VirtualType!(T[0]), CallParams!(T[1..$])); 334 } else { 335 alias CallParams = AliasSeq!(T[0], CallParams!(T[1..$])); 336 } 337 } 338 } 339 340 template castArgs(T...) 341 { 342 import std.typecons : tuple; 343 static if (T.length) { 344 template To(S...) 345 { 346 auto arglist(A...)(A args) { 347 alias QP = T[0]; 348 static if (IsVirtual!QP) { 349 static if (is(VirtualType!QP == class)) { 350 auto arg = cast(S[0]) cast(void*) args[0]; 351 } else { 352 static assert(is(VirtualType!QP == interface), 353 "virtual argument must be a class or an interface"); 354 auto arg = cast(S[0]) args[0]; 355 } 356 } else { 357 auto arg = args[0]; 358 } 359 return 360 tuple(arg, 361 castArgs!(T[1..$]).To!(S[1..$]).arglist(args[1..$]).expand); 362 } 363 } 364 } else { 365 template To(X...) 366 { 367 auto arglist() { 368 return tuple(); 369 } 370 } 371 } 372 } 373 374 auto TypeIds(T...)() 375 { 376 TypeInfo[] result; 377 foreach (A; T) { 378 result ~= typeid(A); 379 } 380 return result; 381 } 382 383 private immutable useDeallocator = "deallocator"; 384 private immutable useHash = "hash"; 385 386 struct Method(string id, string index, R, T...) 387 { 388 alias QualParams = T; 389 alias Params = CallParams!T; 390 alias R function(Params) Spec; 391 alias ReturnType = R; 392 alias Word = Runtime.Word; 393 394 static __gshared Runtime.MethodInfo info; 395 396 static R notImplementedError(T...) 397 { 398 import std.meta; 399 errorHandler(MethodError(MethodError.NotImplemented, id, TypeIds!(Params)())); 400 static if (!is(R == void)) { 401 return R.init; 402 } 403 } 404 405 static R ambiguousCallError(T...) 406 { 407 errorHandler(MethodError(MethodError.AmbiguousCall, id, TypeIds!(Params)())); 408 static if (!is(R == void)) { 409 return R.init; 410 } 411 } 412 413 static Method discriminator(MethodTag, CallParams!T); 414 415 static if (index == useDeallocator) { 416 static auto getIndexTable(T)(T arg) 417 { 418 alias Word = Runtime.Word; 419 static if (is(T == class)) { 420 return cast(const Word*) arg.classinfo.deallocator; 421 } else { 422 // Object o = cast(Object) 423 // (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 424 // return cast(const Word*) o.classinfo.deallocator; 425 import std.stdio; 426 //writeln((cast(Object) arg).classinfo.deallocator); 427 return cast(const Word*) (cast(Object) arg).classinfo.deallocator; 428 } 429 } 430 } else static if (index == useHash) { 431 static auto getIndexTable(T)(T arg) { 432 alias Word = Runtime.Word; 433 static if (is(T == class)) { 434 return Runtime.hashTable[Runtime.hash(*cast (void**) arg)].pw; 435 } else { 436 Object o = cast(Object) 437 (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 438 return Runtime.hashTable[Runtime.hash(*cast (void**) o)].pw; 439 } 440 } 441 } 442 443 template Indexer(Q...) 444 { 445 static const(Word)* move(P...)(const(Word)* slots, const(Word)* strides, P args) 446 { 447 alias Q0 = Q[0]; 448 version (traceCalls) { 449 stderr.write(" | ", Q0.stringof, ":"); 450 } 451 static if (IsVirtual!Q0) { 452 alias arg = args[0]; 453 const (Word)* indexes = getIndexTable(arg); 454 version (traceCalls) { 455 stderr.writef(" %s ", indexes); 456 stderr.writef(" %s ", slots.i); 457 stderr.writef(" %s ", indexes[slots.i].p); 458 } 459 return Indexer!(Q[1..$]) 460 .moveNext(cast(const(Word)*) indexes[slots.i].p, 461 slots + 1, 462 strides, // stride for dim 0 is 1, not stored 463 args[1..$]); 464 } else { 465 return Indexer!(Q[1..$]).move(slots, strides, args[1..$]); 466 } 467 } 468 469 static const(Word)* moveNext(P...)(const(Word)* dt, const(Word)* slots, const(Word)* strides, P args) 470 { 471 static if (Q.length > 0) { 472 alias Q0 = Q[0]; 473 version (traceCalls) { 474 stderr.write(" | ", Q0.stringof, ":"); 475 } 476 static if (IsVirtual!Q0) { 477 alias arg = args[0]; 478 const (Word)* indexes = getIndexTable(arg); 479 version (traceCalls) { 480 stderr.writef(" %s, %s, %s", indexes, slots.i, indexes[slots.i].p); 481 } 482 return Indexer!(Q[1..$]) 483 .moveNext(dt + indexes[slots.i].i * strides.i, 484 slots + 1, 485 strides + 1, 486 args[1..$]); 487 } else { 488 return Indexer!(Q[1..$]).moveNext(dt, slots, strides, args[1..$]); 489 } 490 } else { 491 return dt; 492 } 493 } 494 495 static const(Word)* unary(P...)(P args) 496 { 497 alias Q0 = Q[0]; 498 version (traceCalls) { 499 stderr.write(" | ", Q0.stringof, ":"); 500 } 501 static if (IsVirtual!Q0) { 502 return getIndexTable(args[0]); 503 } else { 504 return Indexer!(Q[1..$]).unary(args[1..$]); 505 } 506 } 507 } 508 509 static auto dispatcher(CallParams!T args) 510 { 511 version (traceCalls) { 512 stderr.write(info.name); 513 } 514 515 alias Word = Runtime.Word; 516 assert(info.vp.length == 1 || info.dispatchTable, "updateMethods not called"); 517 assert(info.vp.length == 1 || info.slots); 518 assert(info.vp.length == 1 || info.strides); 519 520 static if (VirtualArity!QualParams == 1) { 521 version (traceCalls) { 522 stderr.writef("%s %s", Indexer!(QualParams).unary(args), info.slots[0].i); 523 } 524 auto pf = cast(Spec) Indexer!(QualParams).unary(args)[info.slots[0].i].p; 525 } else { 526 auto pf = 527 cast(Spec) Indexer!(QualParams).move(info.slots, info.strides, args).p; 528 } 529 530 version (traceCalls) { 531 writefln(" pf = %s", pf); 532 } 533 534 assert(pf); 535 536 static if (is(R == void)) { 537 pf(args); 538 } else { 539 return pf(args); 540 } 541 } 542 543 static this() { 544 info.name = id; 545 info.useHash = index == useHash; 546 info.ambiguousCallError = &ambiguousCallError; 547 info.notImplementedError = ¬ImplementedError; 548 foreach (QP; QualParams) { 549 int i = 0; 550 static if (IsVirtual!QP) { 551 info.vp ~= VirtualType!(QP).classinfo; 552 } 553 } 554 555 Runtime.register(&info); 556 Runtime.needUpdate = true; 557 } 558 559 static class Specialization(alias fun) 560 { 561 alias Parameters!fun SpecParams; 562 static this() { 563 auto wrapper = function ReturnType(Params args) { 564 static if (is(ReturnType == void)) { 565 fun(castArgs!(T).To!(SpecParams).arglist(args).expand); 566 } else { 567 return fun(castArgs!(T).To!(SpecParams).arglist(args).expand); 568 } 569 }; 570 571 static __gshared Runtime.SpecInfo si; 572 si.pf = cast(void*) wrapper; 573 574 575 foreach (i, QP; QualParams) { 576 static if (IsVirtual!QP) { 577 si.vp ~= SpecParams[i].classinfo; 578 } 579 } 580 info.specInfos ~= &si; 581 si.nextPtr = cast(void**) &nextPtr!SpecParams; 582 583 Runtime.needUpdate = true; 584 } 585 } 586 587 static Spec nextPtr(T...) = null; 588 } 589 590 struct MethodTag { } 591 592 struct Runtime 593 { 594 union Word 595 { 596 void* p; 597 Word* pw; 598 int i; 599 } 600 601 struct MethodInfo 602 { 603 string name; 604 ClassInfo[] vp; 605 SpecInfo*[] specInfos; 606 bool useHash; 607 Word* slots; 608 Word* strides; 609 Word* dispatchTable; 610 void* ambiguousCallError; 611 void* notImplementedError; 612 } 613 614 struct SpecInfo 615 { 616 void* pf; 617 ClassInfo[] vp; 618 void** nextPtr; 619 } 620 621 struct Method 622 { 623 MethodInfo* info; 624 Class*[] vp; 625 Spec*[] specs; 626 627 int[] slots; 628 int[] strides; 629 void*[] dispatchTable; 630 GroupMap firstDim; 631 632 auto toString() const 633 { 634 return format("%s(%s)", info.name, vp.map!(c => c.name).join(", ")); 635 } 636 } 637 638 struct Spec 639 { 640 SpecInfo* info; 641 Class*[] params; 642 643 auto toString() const 644 { 645 return format("(%s)", params.map!(c => c.name).join(", ")); 646 } 647 } 648 649 struct Param 650 { 651 Method* method; 652 int param; 653 654 auto toString() const 655 { 656 return format("%s#%d", *method, param); 657 } 658 } 659 660 struct Class 661 { 662 ClassInfo info; 663 Class*[] directBases; 664 Class*[] directDerived; 665 Class*[Class*] conforming; 666 Param[] methodParams; 667 int nextSlot = 0; 668 int firstUsedSlot = -1; 669 670 @property auto name() const 671 { 672 return info.name.split(".")[$ - 1]; 673 } 674 675 @property auto isClass() 676 { 677 return info is Object.classinfo 678 || info.base is Object.classinfo 679 || info.base !is null; 680 } 681 } 682 683 alias Registry = MethodInfo*[MethodInfo*]; 684 685 struct HashInfo 686 { 687 ulong hashMult; 688 uint hashShift, hashSize; 689 Word* hashTable; 690 } 691 692 static __gshared Registry methodInfos; 693 static __gshared Word[] giv; // Global Index Vector 694 static __gshared Word[] gdv; // Global Dispatch Vector 695 static __gshared needUpdate = true; 696 static __gshared ulong hashMult; 697 static __gshared uint hashShift, hashSize; 698 static __gshared Word* hashTable; 699 Method*[] methods; 700 Class*[ClassInfo] classMap; 701 Class*[] classes; 702 Word*[Class*] mtbls; 703 704 static void register(MethodInfo* mi) 705 { 706 version (explain) { 707 writefln("registering %s", *mi); 708 } 709 710 methodInfos[mi] = mi; 711 } 712 713 void seed() 714 { 715 version (explain) { 716 write("Seeding...\n "); 717 } 718 719 Class* upgrade(ClassInfo ci) 720 { 721 Class* c; 722 if (ci in classMap) { 723 c = classMap[ci]; 724 } else { 725 c = classMap[ci] = new Class(ci); 726 version (explain) { 727 writef(" %s", c.name); 728 } 729 } 730 return c; 731 } 732 733 foreach (mi; methodInfos.values) { 734 auto m = new Method(mi); 735 methods ~= m; 736 737 foreach (int i, ci; mi.vp) { 738 auto c = upgrade(ci); 739 m.vp ~= c; 740 c.methodParams ~= Runtime.Param(m, i); 741 } 742 743 m.specs = mi.specInfos.map! 744 (si => new Spec(si, 745 si.vp.map! 746 (ci => upgrade(ci)).array)).array; 747 748 } 749 750 version (explain) { 751 writeln(); 752 } 753 } 754 755 bool scoop(ClassInfo ci) 756 { 757 bool hasMethods; 758 759 foreach (i; ci.interfaces) { 760 if (scoop(i.classinfo)) { 761 hasMethods = true; 762 } 763 } 764 765 if (ci.base) { 766 if (scoop(ci.base)) { 767 hasMethods = true; 768 } 769 } 770 771 if (ci in classMap) { 772 hasMethods = true; 773 } else if (hasMethods) { 774 if (ci !in classMap) { 775 auto c = classMap[ci] = new Class(ci); 776 version (explain) { 777 writefln(" %s", c.name); 778 } 779 } 780 } 781 782 return hasMethods; 783 } 784 785 void initClasses() 786 { 787 foreach (ci, c; classMap) { 788 foreach (i; ci.interfaces) { 789 if (i.classinfo in classMap) { 790 auto b = classMap[i.classinfo]; 791 c.directBases ~= b; 792 b.directDerived ~= c; 793 } 794 } 795 if (ci.base in classMap) { 796 auto b = classMap[ci.base]; 797 c.directBases ~= b; 798 b.directDerived ~= c; 799 } 800 } 801 } 802 803 void layer() 804 { 805 version (explain) { 806 writefln("Layering..."); 807 } 808 809 auto v = classMap.values.filter!(c => c.directBases.empty).array; 810 auto m = assocArray(zip(v, v)); 811 812 while (!v.empty) { 813 version (explain) { 814 writefln(" %s", v.map!(c => c.name).join(" ")); 815 } 816 817 v.sort!((a, b) => cmp(a.name, b.name) < 0); 818 classes ~= v; 819 820 foreach (c; v) { 821 classMap.remove(c.info); 822 } 823 824 v = classMap.values.filter!(c => c.directBases.all!(b => b in m)).array; 825 826 foreach (c; v) { 827 m[c] = c; 828 } 829 } 830 } 831 832 void calculateInheritanceRelationships() 833 { 834 auto rclasses = classes.dup; 835 reverse(rclasses); 836 837 foreach (c; rclasses) { 838 c.conforming[c] = c; 839 foreach (d; c.directDerived) { 840 c.conforming[d] = d; 841 foreach (dc; d.conforming) { 842 c.conforming[dc] = dc; 843 } 844 845 } 846 } 847 } 848 849 void allocateSlots() 850 { 851 version (explain) { 852 writeln("Allocating slots..."); 853 } 854 855 foreach (c; classes) { 856 if (!c.methodParams.empty) { 857 version (explain) { 858 writefln(" %s...", c.name); 859 } 860 861 foreach (mp; c.methodParams) { 862 int slot = c.nextSlot++; 863 864 version (explain) { 865 writef(" for %s: allocate slot %d\n also in", mp, slot); 866 } 867 868 if (mp.method.slots.length <= mp.param) { 869 mp.method.slots.length = mp.param + 1; 870 } 871 872 mp.method.slots[mp.param] = slot; 873 874 if (c.firstUsedSlot == -1) { 875 c.firstUsedSlot = slot; 876 } 877 878 bool [Class*] visited; 879 visited[c] = true; 880 881 foreach (d; c.directDerived) { 882 allocateSlotDown(d, slot, visited); 883 } 884 885 version (explain) { 886 writeln(); 887 } 888 } 889 } 890 } 891 892 version (explain) { 893 writeln("Initializing the global index vector..."); 894 } 895 896 auto givLength = 897 classes.filter!(c => c.isClass).map!(c => c.nextSlot - c.firstUsedSlot).sum 898 + methods.map!(m => m.vp.length).sum; 899 900 bool useHash = methods.any!(c => c.info.useHash); 901 902 if (useHash) { 903 findHash(); 904 givLength += hashSize; 905 } 906 907 giv.length = givLength; 908 909 Word* sp = giv.ptr; 910 911 version (explain) { 912 writefln(" giv size: %d", giv.length); 913 } 914 915 if (useHash) { 916 hashTable = sp; 917 sp += hashSize; 918 version (explain) { 919 writefln(" reserved %d entries for hash table", hashSize); 920 } 921 } 922 923 version (explain) { 924 writeln(" slots:"); 925 } 926 927 foreach (m; methods) { 928 version (explain) { 929 writefln(" %s %02d-%02d %s", 930 sp, sp - giv.ptr, sp - giv.ptr + m.vp.length, *m); 931 } 932 m.info.slots = sp; 933 foreach (slot; m.slots) { 934 sp++.i = slot; 935 } 936 } 937 938 version (explain) { 939 writeln(" indexes:"); 940 } 941 942 foreach (c; classes) { 943 if (c.isClass) { 944 version (explain) { 945 writefln(" %s %02d-%02d %s", 946 sp, c.firstUsedSlot, c.nextSlot, c.name); 947 } 948 auto mptr = sp - c.firstUsedSlot; 949 mtbls[c] = mptr; 950 c.info.deallocator = mptr; 951 if (useHash) { 952 auto h = hash(c.info.vtbl.ptr); 953 version (explain) { 954 writefln(" -> hashTable[%d]", h); 955 } 956 hashTable[h].p = mptr; 957 } 958 sp += c.nextSlot - c.firstUsedSlot; 959 } 960 } 961 } 962 963 void allocateSlotDown(Class* c, int slot, bool[Class*] visited) 964 { 965 if (c in visited) 966 return; 967 968 version (explain) { 969 writef(" %s", c.name); 970 } 971 972 visited[c] = true; 973 974 assert(slot >= c.nextSlot); 975 976 c.nextSlot = slot + 1; 977 978 if (c.firstUsedSlot == -1) { 979 c.firstUsedSlot = slot; 980 } 981 982 foreach (b; c.directBases) { 983 allocateSlotUp(b, slot, visited); 984 } 985 986 foreach (d; c.directDerived) { 987 allocateSlotDown(d, slot, visited); 988 } 989 } 990 991 void allocateSlotUp(Class* c, int slot, bool[Class*] visited) 992 { 993 if (c in visited) 994 return; 995 996 version (explain) { 997 writef(" %s", c.name); 998 } 999 1000 visited[c] = true; 1001 1002 assert(slot >= c.nextSlot); 1003 1004 c.nextSlot = slot + 1; 1005 1006 if (c.firstUsedSlot == -1) { 1007 c.firstUsedSlot = slot; 1008 } 1009 1010 foreach (d; c.directBases) { 1011 allocateSlotUp(d, slot, visited); 1012 } 1013 } 1014 1015 static bool isMoreSpecific(Spec* a, Spec* b) 1016 { 1017 bool result = false; 1018 1019 for (int i = 0; i < a.params.length; i++) { 1020 if (a.params[i] !is b.params[i]) { 1021 if (a.params[i] in b.params[i].conforming) { 1022 result = true; 1023 } else if (b.params[i] in a.params[i].conforming) { 1024 return false; 1025 } 1026 } 1027 } 1028 1029 return result; 1030 } 1031 1032 static Spec*[] best(Spec*[] candidates) { 1033 Spec*[] best; 1034 1035 foreach (spec; candidates) { 1036 for (int i = 0; i != best.length; ) { 1037 if (isMoreSpecific(spec, best[i])) { 1038 best.remove(i); 1039 best.length -= 1; 1040 } else if (isMoreSpecific(best[i], spec)) { 1041 spec = null; 1042 break; 1043 } else { 1044 ++i; 1045 } 1046 } 1047 1048 if (spec) { 1049 best ~= spec; 1050 } 1051 } 1052 1053 return best; 1054 } 1055 1056 alias GroupMap = Class*[][BitArray]; 1057 1058 void buildTable(Method* m, ulong dim, GroupMap[] groups, BitArray candidates) 1059 { 1060 int groupIndex = 0; 1061 1062 foreach (mask, group; groups[dim]) { 1063 if (dim == 0) { 1064 auto finalMask = candidates & mask; 1065 Spec*[] applicable; 1066 1067 foreach (i, spec; m.specs) { 1068 if (finalMask[i]) { 1069 applicable ~= spec; 1070 } 1071 } 1072 1073 version (explain) { 1074 writefln("%*s dim %d group %d (%s): select best of %s", 1075 (m.vp.length - dim) * 2, "", 1076 dim, groupIndex, 1077 group.map!(c => c.name).join(", "), 1078 applicable.map!(spec => spec.toString).join(", ")); 1079 } 1080 1081 auto specs = best(applicable); 1082 1083 if (specs.length > 1) { 1084 m.dispatchTable ~= m.info.ambiguousCallError; 1085 } else if (specs.empty) { 1086 m.dispatchTable ~= m.info.notImplementedError; 1087 } else { 1088 import std.stdio; 1089 m.dispatchTable ~= specs[0].info.pf; 1090 1091 version (explain) { 1092 writefln("%*s %s: pf = %s", 1093 (m.vp.length - dim) * 2, "", 1094 specs.map!(spec => spec.toString).join(", "), 1095 specs[0].info.pf); 1096 } 1097 } 1098 } else { 1099 version (explain) { 1100 writefln("%*s dim %d group %d (%s)", 1101 (m.vp.length - dim) * 2, "", 1102 dim, groupIndex, 1103 group.map!(c => c.name).join(", ")); 1104 } 1105 buildTable(m, dim - 1, groups, candidates & mask); 1106 } 1107 ++groupIndex; 1108 } 1109 } 1110 1111 void findHash() 1112 { 1113 import std.random, std.math; 1114 1115 void**[] vptrs; 1116 1117 foreach (c; classes) { 1118 if (c.info.vtbl.ptr) { 1119 vptrs ~= c.info.vtbl.ptr; 1120 } 1121 } 1122 1123 auto N = vptrs.length; 1124 1125 version (explain) { 1126 writefln(" finding hash factor for %s vptrs", N); 1127 import std.datetime; 1128 StopWatch sw; 1129 sw.start(); 1130 } 1131 1132 int M; 1133 auto rnd = Random(unpredictableSeed); 1134 ulong totalAttempts; 1135 1136 for (int room = 2; room <= 6; ++room) { 1137 M = 0; 1138 1139 while ((1 << M) < room * N / 2) { 1140 ++M; 1141 } 1142 1143 hashShift = 64 - M; 1144 hashSize = 1 << M; 1145 int[] buckets; 1146 buckets.length = hashSize; 1147 1148 version (explain) { 1149 writefln(" trying with M = %s, %s buckets", M, buckets.length); 1150 } 1151 1152 bool found; 1153 int attempts; 1154 1155 while (!found && attempts < 100_000) { 1156 ++attempts; 1157 ++totalAttempts; 1158 found = true; 1159 hashMult = rnd.uniform!ulong | 1; 1160 buckets[] = 0; 1161 foreach (vptr; vptrs) { 1162 auto h = hash(vptr); 1163 if (buckets[h]++) { 1164 found = false; 1165 break; 1166 } 1167 } 1168 } 1169 1170 if (found) { 1171 version (explain) { 1172 writefln(" found %s after %s attempts and %s msecs", 1173 hashMult, totalAttempts, sw.peek().msecs); 1174 } 1175 return; 1176 } 1177 } 1178 1179 throw new Error("cannot find hash factor"); 1180 } 1181 1182 static auto hash(void* p) { 1183 return (hashMult * (cast(ulong) p)) >> hashShift; 1184 } 1185 1186 void buildTables() 1187 { 1188 foreach (m; methods) { 1189 version (explain) { 1190 writefln("Building dispatch table for %s", *m); 1191 } 1192 1193 auto dims = m.vp.length; 1194 GroupMap[] groups; 1195 groups.length = dims; 1196 1197 foreach (int dim, vp; m.vp) { 1198 version (explain) { 1199 writefln(" make groups for param #%s, class %s", dim, vp.name); 1200 } 1201 1202 foreach (conforming; vp.conforming) { 1203 if (conforming.isClass) { 1204 version (explain) { 1205 writefln(" specs applicable to %s", conforming.name); 1206 } 1207 1208 BitArray mask; 1209 mask.length = m.specs.length; 1210 1211 foreach (int specIndex, spec; m.specs) { 1212 if (conforming in spec.params[dim].conforming) { 1213 version (explain) { 1214 writefln(" %s", *spec); 1215 } 1216 mask[specIndex] = 1; 1217 } 1218 } 1219 1220 version (explain) { 1221 writefln(" bit mask = %s", mask); 1222 } 1223 1224 if (mask in groups[dim]) { 1225 version (explain) { 1226 writefln(" add class %s to existing group", conforming.name, mask); 1227 } 1228 groups[dim][mask] ~= conforming; 1229 } else { 1230 version (explain) { 1231 writefln(" create new group for %s", conforming.name); 1232 } 1233 groups[dim][mask] = [ conforming ]; 1234 } 1235 } 1236 } 1237 } 1238 1239 int stride = 1; 1240 m.strides.length = dims - 1; 1241 1242 foreach (int dim, vp; m.vp[1..$]) { 1243 version (explain) { 1244 writefln(" stride for dim %s = %s", dim + 1, stride); 1245 } 1246 stride *= groups[dim].length; 1247 m.strides[dim] = stride; 1248 } 1249 1250 BitArray none; 1251 none.length = m.specs.length; 1252 1253 version (explain) { 1254 writefln(" assign specs"); 1255 } 1256 1257 buildTable(m, dims - 1, groups, ~none); 1258 1259 version (explain) { 1260 writefln(" assign slots"); 1261 } 1262 1263 foreach (int dim, vp; m.vp) { 1264 version (explain) { 1265 writefln(" dim %s", dim); 1266 } 1267 1268 int i = 0; 1269 1270 foreach (group; groups[dim]) { 1271 version (explain) { 1272 writefln(" group %d (%s)", 1273 i, 1274 group.map!(c => c.name).join(", ")); 1275 } 1276 foreach (c; group) { 1277 (cast(Word*) c.info.deallocator)[m.slots[dim] - c.firstUsedSlot].i = i; 1278 } 1279 1280 ++i; 1281 } 1282 } 1283 1284 m.firstDim = groups[0]; 1285 } 1286 1287 auto gdvLength = methods.filter!(m => m.vp.length > 1).map! 1288 (m => m.dispatchTable.length + m.slots.length + m.strides.length).sum; 1289 1290 gdv.length = gdvLength; 1291 Word* mp = gdv.ptr; 1292 1293 version (explain) { 1294 writefln("Initializing global dispatch table - %d words", gdv.length); 1295 } 1296 1297 foreach (m; methods) { 1298 if (m.info.vp.length > 1) { 1299 version (explain) { 1300 writefln(" %s:", *m); 1301 writefln(" %s: %d strides: %s", mp, m.strides.length, m.strides); 1302 } 1303 m.info.strides = mp; 1304 foreach (stride; m.strides) { 1305 mp++.i = stride; 1306 } 1307 version (explain) { 1308 writefln(" %s: %d functions", mp, m.dispatchTable.length); 1309 } 1310 m.info.dispatchTable = mp; 1311 foreach (p; m.dispatchTable) { 1312 version (explain) { 1313 writefln(" %s", p); 1314 } 1315 mp++.p = cast(void*) p; 1316 } 1317 } 1318 } 1319 1320 foreach (m; methods) { 1321 auto slot = m.slots[0]; 1322 if (m.info.vp.length == 1) { 1323 version (explain) { 1324 writefln(" %s:", *m); 1325 writefln(" 1-method, storing fp in indexes, slot = %s", slot); 1326 } 1327 int i = 0; 1328 foreach (group; m.firstDim) { 1329 foreach (c; group) { 1330 Word* index = mtbls[c] + slot; 1331 index.p = m.dispatchTable[i]; 1332 version (explain) { 1333 writefln(" %s %s", i, index.p); 1334 } 1335 } 1336 ++i; 1337 } 1338 } else { 1339 foreach (group; m.firstDim) { 1340 foreach (c; group) { 1341 Word* index = mtbls[c] + slot; 1342 index.p = m.info.dispatchTable + index.i; 1343 } 1344 } 1345 } 1346 foreach (spec; m.specs) { 1347 auto nextSpec = findNext(spec, m.specs); 1348 *spec.info.nextPtr = nextSpec ? nextSpec.info.pf : null; 1349 } 1350 } 1351 } 1352 1353 static auto findNext(Spec* spec, Spec*[] specs) 1354 { 1355 auto candidates = 1356 best(specs.filter!(other => isMoreSpecific(spec, other)).array); 1357 return candidates.length == 1 ? candidates.front : null; 1358 } 1359 1360 void update() 1361 { 1362 seed(); 1363 1364 version (explain) { 1365 writefln("Scooping..."); 1366 } 1367 1368 foreach (mod; ModuleInfo) { 1369 foreach (c; mod.localClasses) { 1370 scoop(c); 1371 } 1372 } 1373 1374 initClasses(); 1375 layer(); 1376 allocateSlots(); 1377 calculateInheritanceRelationships(); 1378 buildTables(); 1379 1380 needUpdate = false; 1381 } 1382 1383 version (unittest) { 1384 int[] slots(alias MX)() 1385 { 1386 return methods.find!(m => m.info == &MX.ThisMethod.info)[0].slots; 1387 } 1388 1389 Class* getClass(C)() 1390 { 1391 return classes.find!(c => c.info == C.classinfo)[0]; 1392 } 1393 } 1394 } 1395 1396 immutable bool hasVirtualParameters(alias F) = anySatisfy!(IsVirtual, Parameters!F); 1397 1398 unittest 1399 { 1400 void meth(virtual!Object); 1401 static assert(hasVirtualParameters!meth); 1402 void nonmeth(Object); 1403 static assert(!hasVirtualParameters!nonmeth); 1404 } 1405 1406 struct mptr 1407 { 1408 string index; 1409 } 1410 1411 string _registerMethods(alias MODULE)() 1412 { 1413 import std.array; 1414 string[] code; 1415 foreach (m; __traits(allMembers, MODULE)) { 1416 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 1417 foreach (o; __traits(getOverloads, MODULE, m)) { 1418 static if (hasVirtualParameters!o) { 1419 static if (hasUDA!(o, mptr)) { 1420 static assert(getUDAs!(o, mptr).length == 1, 1421 "only une @mptr allowed"); 1422 immutable index = getUDAs!(o, mptr)[0].index; 1423 } else { 1424 immutable index = "deallocator"; 1425 } 1426 auto meth = 1427 format(`Method!("%s", "%s", %s, %s)`, 1428 m, 1429 index, 1430 ReturnType!o.stringof, 1431 Parameters!o.stringof[1..$-1]); 1432 code ~= format(`alias %s = %s.dispatcher;`, m, meth); 1433 code ~= format(`alias %s = %s.discriminator;`, m, meth); 1434 } 1435 } 1436 } 1437 } 1438 return join(code, "\n"); 1439 } 1440 1441 mixin template _registerSpecs(alias MODULE) 1442 { 1443 static void wrap(T)() 1444 { 1445 static __gshared T spec; 1446 } 1447 1448 import std.traits; 1449 1450 static this() { 1451 foreach (_openmethods_m_; __traits(allMembers, MODULE)) { 1452 static if (is(typeof(__traits(getOverloads, MODULE, _openmethods_m_)))) { 1453 foreach (_openmethods_o_; __traits(getOverloads, MODULE, _openmethods_m_)) { 1454 static if (hasUDA!(_openmethods_o_, method)) { 1455 version (GNU) { 1456 immutable _openmethods_id_ = _openmethods_m_[1..$]; 1457 } else { 1458 static if (is(typeof(getUDAs!(_openmethods_o_, method)[0]) == method)) { 1459 immutable _openmethods_id_ = getUDAs!(_openmethods_o_, method)[0].id; 1460 } else { 1461 static assert(_openmethods_m_[0] == '_', 1462 m ~ ": method name must begin with an underscore, " 1463 ~ "or be set in @method()"); 1464 immutable _openmethods_id_ = _openmethods_m_[1..$]; 1465 } 1466 } 1467 wrap!(typeof(mixin(_openmethods_id_)(MethodTag.init, Parameters!(_openmethods_o_).init)) 1468 .Specialization!(_openmethods_o_))(); 1469 } 1470 } 1471 } 1472 } 1473 } 1474 } 1475 1476 version (unittest) { 1477 1478 mixin template _method(string name, R, A...) 1479 { 1480 alias ThisMethod = Method!(name, useDeallocator, R, A); 1481 mixin("alias " ~ name ~ " = ThisMethod.discriminator;"); 1482 mixin("alias " ~ name ~ " = ThisMethod.dispatcher;"); 1483 } 1484 1485 mixin template implement(alias M, alias S) 1486 { 1487 import std.traits; 1488 static __gshared typeof(M(MethodTag.init, Parameters!(S).init)).Specialization!(S) spec; 1489 } 1490 1491 struct Restriction 1492 { 1493 Runtime.Registry saved; 1494 1495 static auto save(M...)() 1496 { 1497 Runtime.Registry temp; 1498 bool[ClassInfo] keep; 1499 1500 foreach (mi; M) { 1501 keep[mi.classinfo] = true; 1502 } 1503 1504 foreach (mi; Runtime.methodInfos.values) { 1505 if (mi.vp.any!(vp => vp in keep)) { 1506 temp[mi] = mi; 1507 } 1508 } 1509 1510 Restriction save = Restriction(Runtime.methodInfos); 1511 Runtime.methodInfos = temp; 1512 1513 return save; 1514 } 1515 1516 ~this() 1517 { 1518 Runtime.methodInfos = saved; 1519 } 1520 } 1521 1522 private auto names(S)(S seq) 1523 { 1524 return seq.map!(c => c.name).join(","); 1525 } 1526 1527 private auto sortedNames(S)(S seq) 1528 { 1529 string[] names = seq.map!(c => c.name).array; 1530 sort(names); 1531 return names.join(","); 1532 } 1533 1534 mixin template Restrict(M...) 1535 { 1536 auto guard = Restriction.save!(M)(); 1537 } 1538 } 1539 1540 unittest 1541 { 1542 // A* C* 1543 // \ / \ 1544 // B* D 1545 // | | 1546 // X Y 1547 1548 // A* C* 1549 // | / \ 1550 // B* / D 1551 // | / | 1552 // X Y 1553 1554 interface A { } 1555 interface C { } 1556 interface D : C { } 1557 interface B : A, C { } 1558 class X : B { } 1559 class Y : D { } 1560 1561 mixin _method!("a", void, virtual!A) aA; 1562 mixin _method!("c", void, virtual!C) cC; 1563 mixin _method!("b", void, virtual!B) bB; 1564 1565 Runtime rt; 1566 mixin Restrict!(A, B, C, D, X, Y); 1567 1568 rt.seed(); 1569 assert(rt.classMap.length == 3); 1570 assert(A.classinfo in rt.classMap); 1571 assert(B.classinfo in rt.classMap); 1572 assert(C.classinfo in rt.classMap); 1573 1574 version (explain) { 1575 writefln("Scooping X..."); 1576 } 1577 1578 rt.scoop(X.classinfo); 1579 assert(rt.classMap.length == 4); 1580 assert(X.classinfo in rt.classMap); 1581 1582 version (explain) { 1583 writefln("Scooping Y..."); 1584 } 1585 1586 rt.scoop(Y.classinfo); 1587 assert(Y.classinfo in rt.classMap); 1588 assert(D.classinfo in rt.classMap); 1589 assert(rt.classMap.length == 6); 1590 1591 int target = 2; 1592 int[] a = [ 1, 2, 3 ]; 1593 assert(a.any!(x => x == target)); 1594 1595 rt.initClasses(); 1596 assert(rt.classMap[A.classinfo].directBases.empty); 1597 assert(rt.classMap[C.classinfo].directBases.empty); 1598 assert(rt.classMap[B.classinfo].directBases.names == "A,C"); 1599 assert(rt.classMap[D.classinfo].directBases.names == "C"); 1600 1601 assert(A.classinfo.base is null); 1602 assert(Object.classinfo.base is null); 1603 assert(X.classinfo.base !is null); 1604 assert(!rt.classMap[A.classinfo].isClass); 1605 assert(rt.classMap[X.classinfo].isClass); 1606 1607 rt.layer(); 1608 assert(rt.classes.names == "A,C,B,D,X,Y"); 1609 1610 rt.allocateSlots(); 1611 1612 assert(rt.slots!aA == [ 0 ]); 1613 assert(rt.slots!cC == [ 1 ]); 1614 assert(rt.slots!bB == [ 2 ]); 1615 1616 rt.calculateInheritanceRelationships(); 1617 assert(rt.getClass!(A).conforming.values.sortedNames == "A,B,X"); 1618 assert(rt.getClass!(B).conforming.values.sortedNames == "B,X"); 1619 assert(rt.getClass!(C).conforming.values.sortedNames == "B,C,D,X,Y"); 1620 assert(rt.getClass!(D).conforming.values.sortedNames == "D,Y"); 1621 assert(rt.getClass!(Y).conforming.values.sortedNames == "Y"); 1622 1623 rt.buildTables(); 1624 } 1625 1626 unittest 1627 { 1628 // A* 1629 // | 1630 // B 1631 // | 1632 // C* 1633 // | 1634 // D 1635 1636 interface A { } 1637 interface B : A { } 1638 interface C : B { } 1639 class D : C { } 1640 1641 mixin _method!("a", void, virtual!A); 1642 mixin _method!("c", void, virtual!C); 1643 1644 Runtime rt; 1645 mixin Restrict!(A, B, C); 1646 assert(rt.methodInfos.length == 2); 1647 1648 rt.seed(); 1649 assert(rt.classMap.length == 2); 1650 1651 version (explain) { 1652 writefln("Scooping D..."); 1653 } 1654 1655 rt.scoop(D.classinfo); 1656 assert(A.classinfo in rt.classMap); 1657 assert(B.classinfo in rt.classMap); 1658 assert(C.classinfo in rt.classMap); 1659 assert(D.classinfo in rt.classMap); 1660 1661 rt.initClasses(); 1662 rt.layer(); 1663 rt.allocateSlots(); 1664 } 1665 1666 unittest 1667 { 1668 interface Matrix { } 1669 class DenseMatrix : Matrix { } 1670 class DiagonalMatrix : Matrix { } 1671 1672 mixin _method!("plus", void, virtual!(immutable Matrix), virtual!(immutable Matrix)); 1673 1674 mixin implement!(plus, function void(immutable Matrix a, immutable Matrix b) { }); 1675 mixin implement!(plus, function void(immutable Matrix a, immutable DiagonalMatrix b) { }); 1676 mixin implement!(plus, function void(immutable DiagonalMatrix a, immutable Matrix b) { }); 1677 mixin implement!(plus, function void(immutable DiagonalMatrix a, immutable DiagonalMatrix b) { }); 1678 1679 Runtime rt; 1680 mixin Restrict!(Matrix, DenseMatrix, DiagonalMatrix); 1681 1682 rt.seed(); 1683 1684 version (explain) { 1685 writefln("Scooping..."); 1686 } 1687 1688 rt.scoop(DenseMatrix.classinfo); 1689 rt.scoop(DiagonalMatrix.classinfo); 1690 1691 rt.initClasses(); 1692 rt.layer(); 1693 rt.allocateSlots(); 1694 rt.calculateInheritanceRelationships(); 1695 1696 auto specs = rt.methods[0].specs; 1697 1698 foreach (a; 0..3) { 1699 foreach (b; 0..3) { 1700 bool expected = a > b && !(a == 1 && b == 2 || a == 2 && b == 1); 1701 assert(Runtime.isMoreSpecific(specs[a], specs[b]) == expected, 1702 format("a = %d, b = %d: expected %s", a, b, expected)); 1703 } 1704 } 1705 1706 assert(Runtime.findNext(specs[0], specs) == null); 1707 assert(Runtime.findNext(specs[1], specs) == specs[0]); 1708 assert(Runtime.findNext(specs[2], specs) == specs[0]); 1709 assert(Runtime.findNext(specs[3], specs) == null); 1710 1711 rt.buildTables(); 1712 }