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