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