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 debug(explain) { 104 import std.stdio; 105 } 106 107 debug(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 } 426 } 427 } else static if (index == useHash) { 428 static auto getIndexTable(T)(T arg) { 429 alias Word = Runtime.Word; 430 static if (is(T == class)) { 431 return Runtime.hashTable[Runtime.hash(*cast (void**) arg)].pw; 432 } else { 433 Object o = cast(Object) 434 (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 435 return Runtime.hashTable[Runtime.hash(*cast (void**) o)].pw; 436 } 437 } 438 } 439 440 template Indexer(Q...) 441 { 442 static const(Word)* move(P...)(const(Word)* slots, const(Word)* strides, P args) 443 { 444 alias Q0 = Q[0]; 445 debug(traceCalls) { 446 stderr.write(" | ", Q0.stringof, ":"); 447 } 448 static if (IsVirtual!Q0) { 449 alias arg = args[0]; 450 const (Word)* indexes = getIndexTable(arg); 451 debug(traceCalls) { 452 stderr.writef(" %s ", indexes); 453 stderr.writef(" %s ", slots.i); 454 stderr.writef(" %s ", indexes[slots.i].p); 455 } 456 return Indexer!(Q[1..$]) 457 .moveNext(cast(const(Word)*) indexes[slots.i].p, 458 slots + 1, 459 strides, // stride for dim 0 is 1, not stored 460 args[1..$]); 461 } else { 462 return Indexer!(Q[1..$]).move(slots, strides, args[1..$]); 463 } 464 } 465 466 static const(Word)* moveNext(P...)(const(Word)* dt, const(Word)* slots, const(Word)* strides, P args) 467 { 468 static if (Q.length > 0) { 469 alias Q0 = Q[0]; 470 debug(traceCalls) { 471 stderr.write(" | ", Q0.stringof, ":"); 472 } 473 static if (IsVirtual!Q0) { 474 alias arg = args[0]; 475 const (Word)* indexes = getIndexTable(arg); 476 debug(traceCalls) { 477 stderr.writef(" %s, %s, %s", indexes, slots.i, indexes[slots.i].p); 478 } 479 return Indexer!(Q[1..$]) 480 .moveNext(dt + indexes[slots.i].i * strides.i, 481 slots + 1, 482 strides + 1, 483 args[1..$]); 484 } else { 485 return Indexer!(Q[1..$]).moveNext(dt, slots, strides, args[1..$]); 486 } 487 } else { 488 return dt; 489 } 490 } 491 492 static const(Word)* unary(P...)(P args) 493 { 494 alias Q0 = Q[0]; 495 debug(traceCalls) { 496 stderr.write(" | ", Q0.stringof, ":"); 497 } 498 static if (IsVirtual!Q0) { 499 return getIndexTable(args[0]); 500 } else { 501 return Indexer!(Q[1..$]).unary(args[1..$]); 502 } 503 } 504 } 505 506 static auto dispatcher(CallParams!T args) 507 { 508 debug(traceCalls) { 509 stderr.write(info.name); 510 } 511 512 alias Word = Runtime.Word; 513 assert(info.vp.length == 1 || info.dispatchTable, "updateMethods not called"); 514 assert(info.vp.length == 1 || info.slots); 515 assert(info.vp.length == 1 || info.strides); 516 517 static if (VirtualArity!QualParams == 1) { 518 debug(traceCalls) { 519 stderr.writef("%s %s", Indexer!(QualParams).unary(args), info.slots[0].i); 520 } 521 auto pf = cast(Spec) Indexer!(QualParams).unary(args)[info.slots[0].i].p; 522 } else { 523 auto pf = 524 cast(Spec) Indexer!(QualParams).move(info.slots, info.strides, args).p; 525 } 526 527 debug(traceCalls) { 528 writefln(" pf = %s", pf); 529 } 530 531 assert(pf); 532 533 static if (is(R == void)) { 534 pf(args); 535 } else { 536 return pf(args); 537 } 538 } 539 540 static this() { 541 info.name = id; 542 info.useHash = index == useHash; 543 info.ambiguousCallError = &ambiguousCallError; 544 info.notImplementedError = ¬ImplementedError; 545 foreach (QP; QualParams) { 546 int i = 0; 547 static if (IsVirtual!QP) { 548 info.vp ~= VirtualType!(QP).classinfo; 549 } 550 } 551 552 Runtime.register(&info); 553 Runtime.needUpdate = true; 554 } 555 556 static class Specialization(alias fun) 557 { 558 alias Parameters!fun SpecParams; 559 static this() { 560 auto wrapper = function ReturnType(Params args) { 561 static if (is(ReturnType == void)) { 562 fun(castArgs!(T).To!(SpecParams).arglist(args).expand); 563 } else { 564 return fun(castArgs!(T).To!(SpecParams).arglist(args).expand); 565 } 566 }; 567 568 static __gshared Runtime.SpecInfo si; 569 si.pf = cast(void*) wrapper; 570 571 572 foreach (i, QP; QualParams) { 573 static if (IsVirtual!QP) { 574 si.vp ~= SpecParams[i].classinfo; 575 } 576 } 577 info.specInfos ~= &si; 578 si.nextPtr = cast(void**) &nextPtr!SpecParams; 579 580 Runtime.needUpdate = true; 581 } 582 } 583 584 static Spec nextPtr(T...) = null; 585 } 586 587 struct MethodTag { } 588 589 struct Runtime 590 { 591 union Word 592 { 593 void* p; 594 Word* pw; 595 int i; 596 } 597 598 struct MethodInfo 599 { 600 string name; 601 ClassInfo[] vp; 602 SpecInfo*[] specInfos; 603 bool useHash; 604 Word* slots; 605 Word* strides; 606 Word* dispatchTable; 607 void* ambiguousCallError; 608 void* notImplementedError; 609 } 610 611 struct SpecInfo 612 { 613 void* pf; 614 ClassInfo[] vp; 615 void** nextPtr; 616 } 617 618 struct Method 619 { 620 MethodInfo* info; 621 Class*[] vp; 622 Spec*[] specs; 623 624 int[] slots; 625 int[] strides; 626 void*[] dispatchTable; 627 GroupMap firstDim; 628 629 auto toString() const 630 { 631 return format("%s(%s)", info.name, vp.map!(c => c.name).join(", ")); 632 } 633 } 634 635 struct Spec 636 { 637 SpecInfo* info; 638 Class*[] params; 639 640 auto toString() const 641 { 642 return format("(%s)", params.map!(c => c.name).join(", ")); 643 } 644 } 645 646 struct Param 647 { 648 Method* method; 649 int param; 650 651 auto toString() const 652 { 653 return format("%s#%d", *method, param); 654 } 655 } 656 657 struct Class 658 { 659 ClassInfo info; 660 Class*[] directBases; 661 Class*[] directDerived; 662 Class*[Class*] conforming; 663 Param[] methodParams; 664 int nextSlot = 0; 665 int firstUsedSlot = -1; 666 667 @property auto name() const 668 { 669 return info.name.split(".")[$ - 1]; 670 } 671 672 @property auto isClass() 673 { 674 return info is Object.classinfo 675 || info.base is Object.classinfo 676 || info.base !is null; 677 } 678 } 679 680 alias Registry = MethodInfo*[MethodInfo*]; 681 682 struct HashInfo 683 { 684 ulong hashMult; 685 uint hashShift, hashSize; 686 Word* hashTable; 687 } 688 689 static __gshared Registry methodInfos; 690 static __gshared Word[] giv; // Global Index Vector 691 static __gshared Word[] gdv; // Global Dispatch Vector 692 static __gshared needUpdate = true; 693 static __gshared ulong hashMult; 694 static __gshared uint hashShift, hashSize; 695 static __gshared Word* hashTable; 696 Method*[] methods; 697 Class*[ClassInfo] classMap; 698 Class*[] classes; 699 Word*[Class*] mtbls; 700 701 static void register(MethodInfo* mi) 702 { 703 debug(explain) { 704 writefln("registering %s", *mi); 705 } 706 707 methodInfos[mi] = mi; 708 } 709 710 void seed() 711 { 712 debug(explain) { 713 write("Seeding...\n "); 714 } 715 716 Class* upgrade(ClassInfo ci) 717 { 718 Class* c; 719 if (ci in classMap) { 720 c = classMap[ci]; 721 } else { 722 c = classMap[ci] = new Class(ci); 723 debug(explain) { 724 writef(" %s", c.name); 725 } 726 } 727 return c; 728 } 729 730 foreach (mi; methodInfos.values) { 731 auto m = new Method(mi); 732 methods ~= m; 733 734 foreach (int i, ci; mi.vp) { 735 auto c = upgrade(ci); 736 m.vp ~= c; 737 c.methodParams ~= Runtime.Param(m, i); 738 } 739 740 m.specs = mi.specInfos.map! 741 (si => new Spec(si, 742 si.vp.map! 743 (ci => upgrade(ci)).array)).array; 744 745 } 746 747 debug(explain) { 748 writeln(); 749 } 750 } 751 752 bool scoop(ClassInfo ci) 753 { 754 bool hasMethods; 755 756 foreach (i; ci.interfaces) { 757 if (scoop(i.classinfo)) { 758 hasMethods = true; 759 } 760 } 761 762 if (ci.base) { 763 if (scoop(ci.base)) { 764 hasMethods = true; 765 } 766 } 767 768 if (ci in classMap) { 769 hasMethods = true; 770 } else if (hasMethods) { 771 if (ci !in classMap) { 772 auto c = classMap[ci] = new Class(ci); 773 debug(explain) { 774 writefln(" %s", c.name); 775 } 776 } 777 } 778 779 return hasMethods; 780 } 781 782 void initClasses() 783 { 784 foreach (ci, c; classMap) { 785 foreach (i; ci.interfaces) { 786 if (i.classinfo in classMap) { 787 auto b = classMap[i.classinfo]; 788 c.directBases ~= b; 789 b.directDerived ~= c; 790 } 791 } 792 if (ci.base in classMap) { 793 auto b = classMap[ci.base]; 794 c.directBases ~= b; 795 b.directDerived ~= c; 796 } 797 } 798 } 799 800 void layer() 801 { 802 debug(explain) { 803 writefln("Layering..."); 804 } 805 806 auto v = classMap.values.filter!(c => c.directBases.empty).array; 807 auto m = assocArray(zip(v, v)); 808 809 while (!v.empty) { 810 debug(explain) { 811 writefln(" %s", v.map!(c => c.name).join(" ")); 812 } 813 814 v.sort!((a, b) => cmp(a.name, b.name) < 0); 815 classes ~= v; 816 817 foreach (c; v) { 818 classMap.remove(c.info); 819 } 820 821 v = classMap.values.filter!(c => c.directBases.all!(b => b in m)).array; 822 823 foreach (c; v) { 824 m[c] = c; 825 } 826 } 827 } 828 829 void calculateInheritanceRelationships() 830 { 831 auto rclasses = classes.dup; 832 reverse(rclasses); 833 834 foreach (c; rclasses) { 835 c.conforming[c] = c; 836 foreach (d; c.directDerived) { 837 c.conforming[d] = d; 838 foreach (dc; d.conforming) { 839 c.conforming[dc] = dc; 840 } 841 842 } 843 } 844 } 845 846 void allocateSlots() 847 { 848 debug(explain) { 849 writeln("Allocating slots..."); 850 } 851 852 foreach (c; classes) { 853 if (!c.methodParams.empty) { 854 debug(explain) { 855 writefln(" %s...", c.name); 856 } 857 858 foreach (mp; c.methodParams) { 859 int slot = c.nextSlot++; 860 861 debug(explain) { 862 writef(" for %s: allocate slot %d\n also in", mp, slot); 863 } 864 865 if (mp.method.slots.length <= mp.param) { 866 mp.method.slots.length = mp.param + 1; 867 } 868 869 mp.method.slots[mp.param] = slot; 870 871 if (c.firstUsedSlot == -1) { 872 c.firstUsedSlot = slot; 873 } 874 875 bool [Class*] visited; 876 visited[c] = true; 877 878 foreach (d; c.directDerived) { 879 allocateSlotDown(d, slot, visited); 880 } 881 882 debug(explain) { 883 writeln(); 884 } 885 } 886 } 887 } 888 889 debug(explain) { 890 writeln("Initializing the global index vector..."); 891 } 892 893 auto givLength = 894 classes.filter!(c => c.isClass).map!(c => c.nextSlot - c.firstUsedSlot).sum 895 + methods.map!(m => m.vp.length).sum; 896 897 bool useHash = methods.any!(c => c.info.useHash); 898 899 if (useHash) { 900 findHash(); 901 givLength += hashSize; 902 } 903 904 giv.length = givLength; 905 906 Word* sp = giv.ptr; 907 908 debug(explain) { 909 writefln(" giv size: %d", giv.length); 910 } 911 912 if (useHash) { 913 hashTable = sp; 914 sp += hashSize; 915 debug(explain) { 916 writefln(" reserved %d entries for hash table", hashSize); 917 } 918 } 919 920 debug(explain) { 921 writeln(" slots:"); 922 } 923 924 foreach (m; methods) { 925 debug(explain) { 926 writefln(" %s %02d-%02d %s", 927 sp, sp - giv.ptr, sp - giv.ptr + m.vp.length, *m); 928 } 929 m.info.slots = sp; 930 foreach (slot; m.slots) { 931 sp++.i = slot; 932 } 933 } 934 935 debug(explain) { 936 writeln(" indexes:"); 937 } 938 939 foreach (c; classes) { 940 if (c.isClass) { 941 debug(explain) { 942 writefln(" %s %02d-%02d %s", 943 sp, c.firstUsedSlot, c.nextSlot, c.name); 944 } 945 auto mptr = sp - c.firstUsedSlot; 946 mtbls[c] = mptr; 947 c.info.deallocator = mptr; 948 if (useHash) { 949 auto h = hash(c.info.vtbl.ptr); 950 debug(explain) { 951 writefln(" -> hashTable[%d]", h); 952 } 953 hashTable[h].p = mptr; 954 } 955 sp += c.nextSlot - c.firstUsedSlot; 956 } 957 } 958 } 959 960 void allocateSlotDown(Class* c, int slot, bool[Class*] visited) 961 { 962 if (c in visited) 963 return; 964 965 debug(explain) { 966 writef(" %s", c.name); 967 } 968 969 visited[c] = true; 970 971 assert(slot >= c.nextSlot); 972 973 c.nextSlot = slot + 1; 974 975 if (c.firstUsedSlot == -1) { 976 c.firstUsedSlot = slot; 977 } 978 979 foreach (b; c.directBases) { 980 allocateSlotUp(b, slot, visited); 981 } 982 983 foreach (d; c.directDerived) { 984 allocateSlotDown(d, slot, visited); 985 } 986 } 987 988 void allocateSlotUp(Class* c, int slot, bool[Class*] visited) 989 { 990 if (c in visited) 991 return; 992 993 debug(explain) { 994 writef(" %s", c.name); 995 } 996 997 visited[c] = true; 998 999 assert(slot >= c.nextSlot); 1000 1001 c.nextSlot = slot + 1; 1002 1003 if (c.firstUsedSlot == -1) { 1004 c.firstUsedSlot = slot; 1005 } 1006 1007 foreach (d; c.directBases) { 1008 allocateSlotUp(d, slot, visited); 1009 } 1010 } 1011 1012 static bool isMoreSpecific(Spec* a, Spec* b) 1013 { 1014 bool result = false; 1015 1016 for (int i = 0; i < a.params.length; i++) { 1017 if (a.params[i] !is b.params[i]) { 1018 if (a.params[i] in b.params[i].conforming) { 1019 result = true; 1020 } else if (b.params[i] in a.params[i].conforming) { 1021 return false; 1022 } 1023 } 1024 } 1025 1026 return result; 1027 } 1028 1029 static Spec*[] best(Spec*[] candidates) { 1030 Spec*[] best; 1031 1032 foreach (spec; candidates) { 1033 for (int i = 0; i != best.length; ) { 1034 if (isMoreSpecific(spec, best[i])) { 1035 best.remove(i); 1036 best.length -= 1; 1037 } else if (isMoreSpecific(best[i], spec)) { 1038 spec = null; 1039 break; 1040 } else { 1041 ++i; 1042 } 1043 } 1044 1045 if (spec) { 1046 best ~= spec; 1047 } 1048 } 1049 1050 return best; 1051 } 1052 1053 alias GroupMap = Class*[][BitArray]; 1054 1055 void buildTable(Method* m, ulong dim, GroupMap[] groups, BitArray candidates) 1056 { 1057 int groupIndex = 0; 1058 1059 foreach (mask, group; groups[dim]) { 1060 if (dim == 0) { 1061 auto finalMask = candidates & mask; 1062 Spec*[] applicable; 1063 1064 foreach (i, spec; m.specs) { 1065 if (finalMask[i]) { 1066 applicable ~= spec; 1067 } 1068 } 1069 1070 debug(explain) { 1071 writefln("%*s dim %d group %d (%s): select best of %s", 1072 (m.vp.length - dim) * 2, "", 1073 dim, groupIndex, 1074 group.map!(c => c.name).join(", "), 1075 applicable.map!(spec => spec.toString).join(", ")); 1076 } 1077 1078 auto specs = best(applicable); 1079 1080 if (specs.length > 1) { 1081 m.dispatchTable ~= m.info.ambiguousCallError; 1082 } else if (specs.empty) { 1083 m.dispatchTable ~= m.info.notImplementedError; 1084 } else { 1085 import std.stdio; 1086 m.dispatchTable ~= specs[0].info.pf; 1087 1088 debug(explain) { 1089 writefln("%*s %s: pf = %s", 1090 (m.vp.length - dim) * 2, "", 1091 specs.map!(spec => spec.toString).join(", "), 1092 specs[0].info.pf); 1093 } 1094 } 1095 } else { 1096 debug(explain) { 1097 writefln("%*s dim %d group %d (%s)", 1098 (m.vp.length - dim) * 2, "", 1099 dim, groupIndex, 1100 group.map!(c => c.name).join(", ")); 1101 } 1102 buildTable(m, dim - 1, groups, candidates & mask); 1103 } 1104 ++groupIndex; 1105 } 1106 } 1107 1108 void findHash() 1109 { 1110 import std.random, std.math; 1111 1112 void**[] vptrs; 1113 1114 foreach (c; classes) { 1115 if (c.info.vtbl.ptr) { 1116 vptrs ~= c.info.vtbl.ptr; 1117 } 1118 } 1119 1120 auto N = vptrs.length; 1121 1122 debug(explain) { 1123 writefln(" finding hash factor for %s vptrs", N); 1124 import std.datetime; 1125 StopWatch sw; 1126 sw.start(); 1127 } 1128 1129 int M; 1130 auto rnd = Random(unpredictableSeed); 1131 ulong totalAttempts; 1132 1133 for (int room = 2; room <= 6; ++room) { 1134 M = 0; 1135 1136 while ((1 << M) < room * N / 2) { 1137 ++M; 1138 } 1139 1140 hashShift = 64 - M; 1141 hashSize = 1 << M; 1142 int[] buckets; 1143 buckets.length = hashSize; 1144 1145 debug(explain) { 1146 writefln(" trying with M = %s, %s buckets", M, buckets.length); 1147 } 1148 1149 bool found; 1150 int attempts; 1151 1152 while (!found && attempts < 100_000) { 1153 ++attempts; 1154 ++totalAttempts; 1155 found = true; 1156 hashMult = rnd.uniform!ulong | 1; 1157 buckets[] = 0; 1158 foreach (vptr; vptrs) { 1159 auto h = hash(vptr); 1160 if (buckets[h]++) { 1161 found = false; 1162 break; 1163 } 1164 } 1165 } 1166 1167 if (found) { 1168 debug(explain) { 1169 writefln(" found %s after %s attempts and %s msecs", 1170 hashMult, totalAttempts, sw.peek().msecs); 1171 } 1172 return; 1173 } 1174 } 1175 1176 throw new Error("cannot find hash factor"); 1177 } 1178 1179 static auto hash(void* p) { 1180 return (hashMult * (cast(ulong) p)) >> hashShift; 1181 } 1182 1183 void buildTables() 1184 { 1185 foreach (m; methods) { 1186 debug(explain) { 1187 writefln("Building dispatch table for %s", *m); 1188 } 1189 1190 auto dims = m.vp.length; 1191 GroupMap[] groups; 1192 groups.length = dims; 1193 1194 foreach (int dim, vp; m.vp) { 1195 debug(explain) { 1196 writefln(" make groups for param #%s, class %s", dim, vp.name); 1197 } 1198 1199 foreach (conforming; vp.conforming) { 1200 if (conforming.isClass) { 1201 debug(explain) { 1202 writefln(" specs applicable to %s", conforming.name); 1203 } 1204 1205 BitArray mask; 1206 mask.length = m.specs.length; 1207 1208 foreach (int specIndex, spec; m.specs) { 1209 if (conforming in spec.params[dim].conforming) { 1210 debug(explain) { 1211 writefln(" %s", *spec); 1212 } 1213 mask[specIndex] = 1; 1214 } 1215 } 1216 1217 debug(explain) { 1218 writefln(" bit mask = %s", mask); 1219 } 1220 1221 if (mask in groups[dim]) { 1222 debug(explain) { 1223 writefln(" add class %s to existing group", conforming.name, mask); 1224 } 1225 groups[dim][mask] ~= conforming; 1226 } else { 1227 debug(explain) { 1228 writefln(" create new group for %s", conforming.name); 1229 } 1230 groups[dim][mask] = [ conforming ]; 1231 } 1232 } 1233 } 1234 } 1235 1236 int stride = 1; 1237 m.strides.length = dims - 1; 1238 1239 foreach (int dim, vp; m.vp[1..$]) { 1240 debug(explain) { 1241 writefln(" stride for dim %s = %s", dim + 1, stride); 1242 } 1243 stride *= groups[dim].length; 1244 m.strides[dim] = stride; 1245 } 1246 1247 BitArray none; 1248 none.length = m.specs.length; 1249 1250 debug(explain) { 1251 writefln(" assign specs"); 1252 } 1253 1254 buildTable(m, dims - 1, groups, ~none); 1255 1256 debug(explain) { 1257 writefln(" assign slots"); 1258 } 1259 1260 foreach (int dim, vp; m.vp) { 1261 debug(explain) { 1262 writefln(" dim %s", dim); 1263 } 1264 1265 int i = 0; 1266 1267 foreach (group; groups[dim]) { 1268 debug(explain) { 1269 writefln(" group %d (%s)", 1270 i, 1271 group.map!(c => c.name).join(", ")); 1272 } 1273 foreach (c; group) { 1274 mtbls[c][m.slots[dim]].i = i; 1275 } 1276 1277 ++i; 1278 } 1279 } 1280 1281 m.firstDim = groups[0]; 1282 } 1283 1284 auto gdvLength = methods.filter!(m => m.vp.length > 1).map! 1285 (m => m.dispatchTable.length + m.slots.length + m.strides.length).sum; 1286 1287 gdv.length = gdvLength; 1288 Word* mp = gdv.ptr; 1289 1290 debug(explain) { 1291 writefln("Initializing global dispatch table - %d words", gdv.length); 1292 } 1293 1294 foreach (m; methods) { 1295 if (m.info.vp.length > 1) { 1296 debug(explain) { 1297 writefln(" %s:", *m); 1298 writefln(" %s: %d strides: %s", mp, m.strides.length, m.strides); 1299 } 1300 m.info.strides = mp; 1301 foreach (stride; m.strides) { 1302 mp++.i = stride; 1303 } 1304 debug(explain) { 1305 writefln(" %s: %d functions", mp, m.dispatchTable.length); 1306 } 1307 m.info.dispatchTable = mp; 1308 foreach (p; m.dispatchTable) { 1309 debug(explain) { 1310 writefln(" %s", p); 1311 } 1312 mp++.p = cast(void*) p; 1313 } 1314 } 1315 } 1316 1317 foreach (m; methods) { 1318 auto slot = m.slots[0]; 1319 if (m.info.vp.length == 1) { 1320 debug(explain) { 1321 writefln(" %s:", *m); 1322 writefln(" 1-method, storing fp in indexes, slot = %s", slot); 1323 } 1324 int i = 0; 1325 foreach (group; m.firstDim) { 1326 foreach (c; group) { 1327 Word* index = mtbls[c] + slot; 1328 index.p = m.dispatchTable[i]; 1329 debug(explain) { 1330 writefln(" %s %s", i, index.p); 1331 } 1332 } 1333 ++i; 1334 } 1335 } else { 1336 foreach (group; m.firstDim) { 1337 foreach (c; group) { 1338 Word* index = mtbls[c] + slot; 1339 index.p = m.info.dispatchTable + index.i; 1340 } 1341 } 1342 } 1343 foreach (spec; m.specs) { 1344 auto nextSpec = findNext(spec, m.specs); 1345 *spec.info.nextPtr = nextSpec ? nextSpec.info.pf : null; 1346 } 1347 } 1348 } 1349 1350 static auto findNext(Spec* spec, Spec*[] specs) 1351 { 1352 auto candidates = 1353 best(specs.filter!(other => isMoreSpecific(spec, other)).array); 1354 return candidates.length == 1 ? candidates.front : null; 1355 } 1356 1357 void update() 1358 { 1359 seed(); 1360 1361 debug(explain) { 1362 writefln("Scooping..."); 1363 } 1364 1365 foreach (mod; ModuleInfo) { 1366 foreach (c; mod.localClasses) { 1367 scoop(c); 1368 } 1369 } 1370 1371 initClasses(); 1372 layer(); 1373 allocateSlots(); 1374 calculateInheritanceRelationships(); 1375 buildTables(); 1376 1377 needUpdate = false; 1378 } 1379 1380 version (unittest) { 1381 int[] slots(alias MX)() 1382 { 1383 return methods.find!(m => m.info == &MX.ThisMethod.info)[0].slots; 1384 } 1385 1386 Class* getClass(C)() 1387 { 1388 return classes.find!(c => c.info == C.classinfo)[0]; 1389 } 1390 } 1391 } 1392 1393 immutable bool hasVirtualParameters(alias F) = anySatisfy!(IsVirtual, Parameters!F); 1394 1395 unittest 1396 { 1397 void meth(virtual!Object); 1398 static assert(hasVirtualParameters!meth); 1399 void nonmeth(Object); 1400 static assert(!hasVirtualParameters!nonmeth); 1401 } 1402 1403 struct mptr 1404 { 1405 string index; 1406 } 1407 1408 string _registerMethods(alias MODULE)() 1409 { 1410 import std.array; 1411 string[] code; 1412 foreach (m; __traits(allMembers, MODULE)) { 1413 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 1414 foreach (o; __traits(getOverloads, MODULE, m)) { 1415 static if (hasVirtualParameters!o) { 1416 static if (hasUDA!(o, mptr)) { 1417 static assert(getUDAs!(o, mptr).length == 1, 1418 "only une @mptr allowed"); 1419 immutable index = getUDAs!(o, mptr)[0].index; 1420 } else { 1421 immutable index = "deallocator"; 1422 } 1423 auto meth = 1424 format(`Method!("%s", "%s", %s, %s)`, 1425 m, 1426 index, 1427 ReturnType!o.stringof, 1428 Parameters!o.stringof[1..$-1]); 1429 code ~= format(`alias %s = %s.dispatcher;`, m, meth); 1430 code ~= format(`alias %s = %s.discriminator;`, m, meth); 1431 } 1432 } 1433 } 1434 } 1435 return join(code, "\n"); 1436 } 1437 1438 mixin template _registerSpecs(alias MODULE) 1439 { 1440 static void wrap(T)() 1441 { 1442 static __gshared T spec; 1443 } 1444 1445 import std.traits; 1446 1447 static this() { 1448 foreach (_openmethods_m_; __traits(allMembers, MODULE)) { 1449 static if (is(typeof(__traits(getOverloads, MODULE, _openmethods_m_)))) { 1450 foreach (_openmethods_o_; __traits(getOverloads, MODULE, _openmethods_m_)) { 1451 static if (hasUDA!(_openmethods_o_, method)) { 1452 version (GNU) { 1453 immutable _openmethods_id_ = _openmethods_m_[1..$]; 1454 } else { 1455 static if (is(typeof(getUDAs!(_openmethods_o_, method)[0]) == method)) { 1456 immutable _openmethods_id_ = getUDAs!(_openmethods_o_, method)[0].id; 1457 } else { 1458 static assert(_openmethods_m_[0] == '_', 1459 m ~ ": method name must begin with an underscore, " 1460 ~ "or be set in @method()"); 1461 immutable _openmethods_id_ = _openmethods_m_[1..$]; 1462 } 1463 } 1464 wrap!(typeof(mixin(_openmethods_id_)(MethodTag.init, Parameters!(_openmethods_o_).init)) 1465 .Specialization!(_openmethods_o_))(); 1466 } 1467 } 1468 } 1469 } 1470 } 1471 } 1472 1473 version (unittest) { 1474 1475 mixin template _method(string name, R, A...) 1476 { 1477 alias ThisMethod = Method!(name, useDeallocator, R, A); 1478 mixin("alias " ~ name ~ " = ThisMethod.discriminator;"); 1479 mixin("alias " ~ name ~ " = ThisMethod.dispatcher;"); 1480 } 1481 1482 mixin template implement(alias M, alias S) 1483 { 1484 import std.traits; 1485 static __gshared typeof(M(MethodTag.init, Parameters!(S).init)).Specialization!(S) spec; 1486 } 1487 1488 struct Restriction 1489 { 1490 Runtime.Registry saved; 1491 1492 static auto save(M...)() 1493 { 1494 Runtime.Registry temp; 1495 bool[ClassInfo] keep; 1496 1497 foreach (mi; M) { 1498 keep[mi.classinfo] = true; 1499 } 1500 1501 foreach (mi; Runtime.methodInfos.values) { 1502 if (mi.vp.any!(vp => vp in keep)) { 1503 temp[mi] = mi; 1504 } 1505 } 1506 1507 Restriction save = Restriction(Runtime.methodInfos); 1508 Runtime.methodInfos = temp; 1509 1510 return save; 1511 } 1512 1513 ~this() 1514 { 1515 Runtime.methodInfos = saved; 1516 } 1517 } 1518 1519 private auto names(S)(S seq) 1520 { 1521 return seq.map!(c => c.name).join(","); 1522 } 1523 1524 private auto sortedNames(S)(S seq) 1525 { 1526 string[] names = seq.map!(c => c.name).array; 1527 sort(names); 1528 return names.join(","); 1529 } 1530 1531 mixin template Restrict(M...) 1532 { 1533 auto guard = Restriction.save!(M)(); 1534 } 1535 } 1536 1537 unittest 1538 { 1539 // A* C* 1540 // \ / \ 1541 // B* D 1542 // | | 1543 // X Y 1544 1545 // A* C* 1546 // | / \ 1547 // B* / D 1548 // | / | 1549 // X Y 1550 1551 interface A { } 1552 interface C { } 1553 interface D : C { } 1554 interface B : A, C { } 1555 class X : B { } 1556 class Y : D { } 1557 1558 mixin _method!("a", void, virtual!A) aA; 1559 mixin _method!("c", void, virtual!C) cC; 1560 mixin _method!("b", void, virtual!B) bB; 1561 1562 Runtime rt; 1563 mixin Restrict!(A, B, C, D, X, Y); 1564 1565 rt.seed(); 1566 assert(rt.classMap.length == 3); 1567 assert(A.classinfo in rt.classMap); 1568 assert(B.classinfo in rt.classMap); 1569 assert(C.classinfo in rt.classMap); 1570 1571 debug(explain) { 1572 writefln("Scooping X..."); 1573 } 1574 1575 rt.scoop(X.classinfo); 1576 assert(rt.classMap.length == 4); 1577 assert(X.classinfo in rt.classMap); 1578 1579 debug(explain) { 1580 writefln("Scooping Y..."); 1581 } 1582 1583 rt.scoop(Y.classinfo); 1584 assert(Y.classinfo in rt.classMap); 1585 assert(D.classinfo in rt.classMap); 1586 assert(rt.classMap.length == 6); 1587 1588 int target = 2; 1589 int[] a = [ 1, 2, 3 ]; 1590 assert(a.any!(x => x == target)); 1591 1592 rt.initClasses(); 1593 assert(rt.classMap[A.classinfo].directBases.empty); 1594 assert(rt.classMap[C.classinfo].directBases.empty); 1595 assert(rt.classMap[B.classinfo].directBases.names == "A,C"); 1596 assert(rt.classMap[D.classinfo].directBases.names == "C"); 1597 1598 assert(A.classinfo.base is null); 1599 assert(Object.classinfo.base is null); 1600 assert(X.classinfo.base !is null); 1601 assert(!rt.classMap[A.classinfo].isClass); 1602 assert(rt.classMap[X.classinfo].isClass); 1603 1604 rt.layer(); 1605 assert(rt.classes.names == "A,C,B,D,X,Y"); 1606 1607 rt.allocateSlots(); 1608 1609 assert(rt.slots!aA == [ 0 ]); 1610 assert(rt.slots!cC == [ 1 ]); 1611 assert(rt.slots!bB == [ 2 ]); 1612 1613 rt.calculateInheritanceRelationships(); 1614 assert(rt.getClass!(A).conforming.values.sortedNames == "A,B,X"); 1615 assert(rt.getClass!(B).conforming.values.sortedNames == "B,X"); 1616 assert(rt.getClass!(C).conforming.values.sortedNames == "B,C,D,X,Y"); 1617 assert(rt.getClass!(D).conforming.values.sortedNames == "D,Y"); 1618 assert(rt.getClass!(Y).conforming.values.sortedNames == "Y"); 1619 1620 rt.buildTables(); 1621 } 1622 1623 unittest 1624 { 1625 // A* 1626 // | 1627 // B 1628 // | 1629 // C* 1630 // | 1631 // D 1632 1633 interface A { } 1634 interface B : A { } 1635 interface C : B { } 1636 class D : C { } 1637 1638 mixin _method!("a", void, virtual!A); 1639 mixin _method!("c", void, virtual!C); 1640 1641 Runtime rt; 1642 mixin Restrict!(A, B, C); 1643 assert(rt.methodInfos.length == 2); 1644 1645 rt.seed(); 1646 assert(rt.classMap.length == 2); 1647 1648 debug(explain) { 1649 writefln("Scooping D..."); 1650 } 1651 1652 rt.scoop(D.classinfo); 1653 assert(A.classinfo in rt.classMap); 1654 assert(B.classinfo in rt.classMap); 1655 assert(C.classinfo in rt.classMap); 1656 assert(D.classinfo in rt.classMap); 1657 1658 rt.initClasses(); 1659 rt.layer(); 1660 rt.allocateSlots(); 1661 } 1662 1663 unittest 1664 { 1665 interface Matrix { } 1666 class DenseMatrix : Matrix { } 1667 class DiagonalMatrix : Matrix { } 1668 1669 mixin _method!("plus", void, virtual!(immutable Matrix), virtual!(immutable Matrix)); 1670 1671 mixin implement!(plus, function void(immutable Matrix a, immutable Matrix b) { }); 1672 mixin implement!(plus, function void(immutable Matrix a, immutable DiagonalMatrix b) { }); 1673 mixin implement!(plus, function void(immutable DiagonalMatrix a, immutable Matrix b) { }); 1674 mixin implement!(plus, function void(immutable DiagonalMatrix a, immutable DiagonalMatrix b) { }); 1675 1676 Runtime rt; 1677 mixin Restrict!(Matrix, DenseMatrix, DiagonalMatrix); 1678 1679 rt.seed(); 1680 1681 debug(explain) { 1682 writefln("Scooping..."); 1683 } 1684 1685 rt.scoop(DenseMatrix.classinfo); 1686 rt.scoop(DiagonalMatrix.classinfo); 1687 1688 rt.initClasses(); 1689 rt.layer(); 1690 rt.allocateSlots(); 1691 rt.calculateInheritanceRelationships(); 1692 1693 auto specs = rt.methods[0].specs; 1694 1695 foreach (a; 0..3) { 1696 foreach (b; 0..3) { 1697 bool expected = a > b && !(a == 1 && b == 2 || a == 2 && b == 1); 1698 assert(Runtime.isMoreSpecific(specs[a], specs[b]) == expected, 1699 format("a = %d, b = %d: expected %s", a, b, expected)); 1700 } 1701 } 1702 1703 assert(Runtime.findNext(specs[0], specs) == null); 1704 assert(Runtime.findNext(specs[1], specs) == specs[0]); 1705 assert(Runtime.findNext(specs[2], specs) == specs[0]); 1706 assert(Runtime.findNext(specs[3], specs) == null); 1707 1708 rt.buildTables(); 1709 }