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 the presence of multiple virtual arguments. 14 15 Synopsis of openmethods: 16 --- 17 18 import openmethods; // import lib 19 mixin(registerMethods); // mixin must be called after importing module 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 import std.stdio; 67 68 Animal hector = new Pitbull, snoopy = new Dog; 69 writeln("kick snoopy: ", kick(snoopy)); // bark 70 writeln("kick hector: ", kick(hector)); // bark and bite 71 72 Animal felix = new Cat, flipper = new Dolphin; 73 writeln("hector meets felix: ", meet(hector, felix)); // chase 74 writeln("hector meets snoopy: ", meet(hector, snoopy)); // wag tail 75 writeln("hector meets flipper: ", meet(hector, flipper)); // ignore 76 } 77 --- 78 79 Copyright: Copyright Jean-Louis Leroy 2017-2020 80 81 License: $(LINK2 http://boost.org/LICENSE_1_0.txt, Boost License 1.0). 82 83 Authors: Jean-Louis Leroy 84 +/ 85 86 module openmethods; 87 88 import std.algorithm; 89 import std.bitmanip; 90 import std.exception; 91 import std.format; 92 import std.meta; 93 import std.range; 94 import std.traits; 95 96 import rf = bolts.experimental.refraction; 97 static import bolts.experimental.refraction; 98 99 // ============================================================================ 100 // Public stuff 101 102 /++ 103 Mark a parameter as virtual, and declare a method. 104 105 A new function is introduced in the current scope. It has the same name as the 106 declared method; its parameter list consists of the declared parameters, 107 stripped from the `virtual!` qualifier. Calls to this function resolve to the 108 most specific method that matches the arguments. 109 110 The rules for determining the most specific function are exactly the same as 111 those that guide the resolution of function calls in presence of overloads - 112 only the resolution happens at run time, taking into account the argument's 113 $(I dynamic) type. In contrast, the normal function overload resolution is a 114 compile time mechanism that takes into account the $(I static) type of the 115 arguments. 116 117 Examples: 118 --- 119 Matrix times(double, virtual!Matrix); 120 Matrix a = new DiagonalMatrix(...); 121 auto result = times(2, a); 122 123 string fight(virtual!Character, virtual!Creature, virtual!Device); 124 fight(player, room.guardian, bag[item]); 125 --- 126 +/ 127 128 struct virtual(T) 129 { 130 } 131 132 /++ 133 Mark a parameter as covariant. 134 135 Marking a parameter as covariant makes it possible to override a method with 136 an override that has a type-compatible parameter in the same position. 137 Covariant parameters are not taken into account for override selection. The 138 arguments passed in covariant parameters are automatically cast to the types 139 required by the override. 140 141 `covariant` is useful when it is known for certain that the overrides will 142 always be called with arguments of the required type. This can help improve 143 performance and reduce the size of method dispatch tables. 144 145 Examples: 146 --- 147 class Container {} 148 class Bottle : Container {} 149 class Can : Container {} 150 class Tool {} 151 class Corkscrew : Tool {} 152 class CanOpener : Tool {} 153 154 void open(virtual!Container, covariant!Tool); 155 @method void _open(Bottle bottle, Corkscrew corkscrew) {} // 1 156 @method void _open(Can can, CanOpener opener) {} // 2 157 // ... 158 159 Container container = new Bottle(); 160 Tool tool = new Corkscrew(); 161 open(container, tool); 162 // override #1 is selected based solely on first argument's type 163 // second argument is cast to Corkscrew 164 // The following is illegal: 165 Tool wrongTool = new CanOpener(); 166 open(container, wrongTool); 167 // override #1 is called but is passed a CanOpener. 168 --- 169 +/ 170 171 struct covariant(T) 172 { 173 } 174 175 /++ 176 Attribute: Set the policy for storing and retrieving the method pointer (mptr). 177 178 Each class involved in method dispatch (either because it occurs as a virtual 179 parameter, or is derived from a class or an interface that occurs as a virtual 180 parameter) has an associated mptr. The first step of method dispatch consists 181 in retrieving the mptr for each virtual argument. 182 183 Two policies are supported: "deallocator": store the mptr in the deprecated 184 `deallocator` field of ClassInfo. This is the default, and delivers the best 185 performance. $(NOTE:) This policy is incompatible with classes that implement 186 the deprecated `operator delete`. 187 188 "hash": store the mptr in a hash table. The mptr is obtained by 189 applying a perfect hash function to the class' vptr. This policy is only 190 slightly slower than the deallocator policy. 191 192 Example: 193 --- 194 @mptr("hash") 195 string fight(virtual!Character, virtual!Creature, virtual!Device); 196 --- 197 +/ 198 199 struct mptr 200 { 201 string index; 202 } 203 204 /++ 205 Attribute: Add an override to a method. 206 207 If called without an argument, the function name must consist of a method 208 name, prefixed with an underscore. The function is added to the method as a 209 specialization. 210 211 If called with a string argument, the string indicates the name of the method 212 to specialize. The function name can then be any valid identifier. This is 213 useful to allow an override to call a specific override without going through 214 the dynamic dispatch mechanism. 215 216 Examples: 217 --- 218 @method 219 string _fight(Character x, Creature y, Axe z) 220 { 221 ... 222 } 223 224 @method("times") 225 Matrix doubleTimesDiagonal(double a, immutable(DiagonalMatrix) b) 226 { 227 ... 228 } 229 --- 230 231 +/ 232 233 struct method 234 { 235 string id; 236 } 237 238 /++ Call the _next most specialized override, if it exists. In other words, 239 call the override that would have been called if this one had not been 240 defined. 241 242 Examples: 243 --- 244 void inspect(virtual!Vehicle, virtual!Inspector); 245 246 @method 247 void _inspect(Vehicle v, Inspector i) 248 { 249 writeln("Inspect vehicle."); 250 } 251 252 @method 253 void _inspect(Car v, Inspector i) 254 { 255 next!inspect(v, i); 256 writeln("Inspect seat belts."); 257 } 258 259 @method 260 void _inspect(Car v, StateInspector i) 261 { 262 next!inspect(v, i); 263 writeln("Check insurance."); 264 } 265 266 ... 267 268 Vehicle car = new Car; 269 Inspector inspector = new StateInspector; 270 inspect(car, inspector); // Inspect vehicle. Inspect seat belts. Check insurance. 271 --- 272 +/ 273 274 auto next(alias F, T...)(T args) @trusted 275 { 276 alias TheMethod = typeof(F(MethodTag.init, T.init)); 277 alias Spec = TheMethod.ReturnType function(TheMethod.CallParams); 278 return (cast(Spec) TheMethod.nextPtr!T)(args); 279 } 280 281 /++ Used as a string mixin: register the method declarations and definitions in 282 the current module. 283 284 Examples: 285 --- 286 import openmethods; 287 mixin(registerMethods); 288 --- 289 +/ 290 291 auto registerMethods(string moduleName = __MODULE__) 292 { 293 return q{ 294 static import openmethods; 295 static import bolts.experimental.refraction; 296 mixin(openmethods.registrationMixture!(%s, "%s")); 297 }.format(moduleName, moduleName); 298 } 299 300 mixin template registerClasses(Classes...) { 301 shared static this() { 302 foreach (C; Classes) { 303 debug(explain) { 304 import std.stdio; 305 writefln("Registering class %s", C.stringof); 306 } 307 Runtime.additionalClasses ~= C.classinfo; 308 Runtime.needUpdate = true; 309 } 310 } 311 312 shared static ~this() 313 { 314 foreach (C; Classes) { 315 debug(explain) { 316 import std.stdio; 317 writefln("Unregistering class %s", C.stringof); 318 } 319 import std.algorithm, std.array; 320 Runtime.additionalClasses = 321 Runtime.additionalClasses.filter!(c => c != C.classinfo).array; 322 Runtime.needUpdate = true; 323 } 324 } 325 } 326 327 /++ 328 Update the runtime dispatch tables. Must be called after dynamically 329 loading or unloading a shared library. 330 +/ 331 332 Runtime.Metrics updateMethods() 333 { 334 Runtime rt; 335 return rt.update(); 336 } 337 338 void unregisterMethods() 339 { 340 Runtime rt; 341 rt.unregister; 342 } 343 344 shared static this() 345 { 346 updateMethods; 347 } 348 349 bool needUpdateMethods() 350 { 351 return Runtime.needUpdate; 352 } 353 354 /++ 355 Information passed to the error handler function. 356 357 +/ 358 359 class MethodError : Error 360 { 361 this(int reason, const(Runtime.MethodInfo)* meth) { 362 super(reason.stringof); 363 this.reason = reason; 364 this.meth = meth; 365 } 366 367 @property string functionName() { return meth.name; } 368 369 enum NotImplemented = 1, AmbiguousCall = 2, DeallocatorInUse = 3; 370 const Runtime.MethodInfo* meth; 371 int reason; 372 TypeInfo[] args; 373 } 374 375 void defaultMethodErrorHandler(MethodError error) 376 { 377 import std.stdio; 378 stderr.writefln("call to %s(%s) is %s, aborting...", 379 error.functionName, 380 error.args.map!(a => a.toString).join(", "), 381 error.reason == MethodError.NotImplemented 382 ? "not implemented" : "ambiguous"); 383 import core.stdc.stdlib : abort; 384 abort(); 385 } 386 387 alias MethodErrorHandler = void function(MethodError error); 388 389 MethodErrorHandler errorHandler = &defaultMethodErrorHandler; 390 391 /++ 392 Set the error handling function to be called if an open method cannot be 393 called with the provided arguments. The default is to `abort` the program. 394 +/ 395 396 MethodErrorHandler setMethodErrorHandler(MethodErrorHandler handler) 397 { 398 auto prev = errorHandler; 399 errorHandler = handler; 400 return prev; 401 } 402 403 // ============================================================================ 404 // Private parts. This doesn't exist. If you believe it does and use it, on 405 // your head be it. 406 407 version (GNU) { 408 import std.datetime; 409 } else { 410 import std.datetime.stopwatch; 411 } 412 413 debug (explain) { 414 import std.stdio; 415 416 void trace(T...)(T args) nothrow 417 { 418 try { 419 stderr.write(args); 420 } catch (Exception) { 421 } 422 } 423 424 void tracef(T...)(T args) nothrow 425 { 426 try { 427 stderr.writef(args); 428 } catch (Exception) { 429 } 430 } 431 432 void tracefln(T...)(T args) nothrow 433 { 434 try { 435 stderr.writefln(args); 436 } catch (Exception) { 437 } 438 } 439 } 440 441 // ---------------------------------------------------------------------------- 442 // Meta-programming helpers 443 444 private enum IsVirtual(T) = false; 445 private enum IsVirtual(T : virtual!U, U) = true; 446 private alias UnqualType(T) = T; 447 private alias UnqualType(T : virtual!U, U) = U; 448 449 private enum IsCovariant(T) = false; 450 private enum IsCovariant(T : covariant!U, U) = true; 451 private alias UnqualType(T : covariant!U, U) = U; 452 453 private template Format(alias F, A...) 454 { 455 enum Format = format!F(A); 456 } 457 458 // ============================================================================ 459 // Method 460 461 struct MethodTag { } 462 463 enum MptrInDeallocator = "deallocator"; 464 enum MptrViaHash = "hash"; 465 466 auto makeCallParams(rf.Parameter[] parameters) 467 { 468 return parameters.length.iota.map!( 469 i => parameters[i].setType("CallParams[%d]".format(i))).array; 470 } 471 472 auto removeStorageClasses(rf.Parameter[] parameters) 473 { 474 return parameters.map!(p => p.setStorage([])).array; 475 } 476 477 struct Method(alias module_, string name, int index) 478 { 479 alias Module = module_; 480 enum Name = name; 481 enum Index = index; 482 483 alias Declaration = __traits(getOverloads, Module, Name)[Index]; 484 alias QualParams = std.traits.Parameters!Declaration; 485 alias CallParams = staticMap!(UnqualType, QualParams); 486 alias ReturnType = std.traits.ReturnType!Declaration; 487 alias Word = Runtime.Word; 488 alias TheMethod = Method; 489 490 // ========================================================================== 491 // Meta-programming 492 493 enum Original = rf.refract!(Declaration, "Declaration"); 494 495 enum Editor = Original 496 .setStatic(true) 497 .setReturnType("ReturnType") // not really needed but helps debugging 498 .setParameters(makeCallParams(Original.parameters)); 499 500 static if (hasUDA!(Declaration, mptr)) { 501 static assert(getUDAs!(Declaration, mptr).length == 1, "only one @mptr allowed"); 502 enum Mptr = getUDAs!(Declaration, mptr)[0].index; 503 } else { 504 enum Mptr = "deallocator"; 505 } 506 507 enum isVirtualPosition(size_t I) = IsVirtual!(QualParams[I]); 508 enum virtualPositions = Filter!( 509 isVirtualPosition, aliasSeqOf!(QualParams.length.iota)); 510 511 enum virtualArgListCode = [ 512 staticMap!(ApplyLeft!(Format, "_%d"), virtualPositions) 513 ].join(", "); 514 515 static template castArgCode(QualParam, size_t i) 516 { 517 static if (IsVirtual!QualParam) { 518 static if (is(UnqualType!QualParam == interface)) { 519 enum castArgCode = "cast(SpecParams[%s]) _%d".format(i, i); 520 } else { 521 enum castArgCode = "cast(SpecParams[%s]) cast(void*) _%d".format(i, i); 522 } 523 } else static if (IsCovariant!QualParam) { 524 static if (is(UnqualType!QualParam == class)) { 525 debug { 526 enum castArgCode = "cast(SpecParams[%s]) _%d".format(i, i); 527 } else { 528 enum castArgCode = "cast(SpecParams[%s]) cast(void*) _%d".format(i, i); 529 } 530 } else { 531 static assert(is(UnqualType!QualParam == interface), 532 "covariant argument must be a class or an interface"); 533 enum castArgCode = "cast(SpecParams[%s]) _%d".format(i, i); 534 } 535 } else { 536 enum castArgCode = "_%d".format(i); 537 } 538 } 539 540 enum castArgListCode(alias Spec) = { 541 string[] casts; 542 foreach (i, qp; QualParams) { 543 casts ~= castArgCode!(qp, i); 544 } 545 return casts.join(", "); 546 }(); 547 548 enum Wrapper(alias Spec) = Editor 549 .setName("wrapper") 550 .setBody("{ return Spec(%s); }".format(castArgListCode!Spec)); 551 552 mixin( 553 "alias Spec = ", 554 Editor.setUdas([]).setName("function").mixture, 555 ";"); 556 557 // dispatcher 558 enum Dispatcher = 559 Editor 560 .setName("dispatcher") 561 .setBody( 562 "{ return resolve(%s)(%s); }".format( 563 virtualArgListCode, Editor.argumentMixture)); 564 mixin(Dispatcher.mixture); 565 566 // discriminator note that we do *not* carry parameter storage classes 567 // because we use CallParams[i].init to form an argument list when "calling" 568 // the discriminator to locate the method. 569 mixin( 570 Editor 571 .setReturnType("TheMethod") 572 .setName("discriminator") 573 .setParameters( 574 [ rf.Parameter().setType("openmethods.MethodTag") ] 575 ~ removeStorageClasses(Editor.parameters)) 576 .mixture); 577 578 enum aliases = q{ 579 alias %s = openmethods.Method!(%s, "%s", %d).dispatcher; 580 alias %s = openmethods.Method!(%s, "%s", %d).discriminator; 581 }.format( 582 Name, __traits(identifier, Module), Name, Index, 583 Name, __traits(identifier, Module), Name, Index); 584 585 // ========================================================================== 586 // Method Registration 587 588 __gshared Runtime.MethodInfo info; 589 alias genericNextPtr = void function(); 590 __gshared genericNextPtr nextPtr(QualParams...) = null; 591 592 static register() { 593 info = Runtime.MethodInfo.init; 594 info.name = Name; 595 596 debug(explain) { 597 writefln("registering method %s", info); 598 } 599 600 static if (Mptr == MptrInDeallocator) { 601 ++Runtime.methodsUsingDeallocator; 602 } else static if (Mptr == MptrViaHash) { 603 ++Runtime.methodsUsingHash; 604 } 605 606 info.ambiguousCallError = &ambiguousCallError; 607 info.notImplementedError = ¬ImplementedError; 608 609 foreach (QP; QualParams) { 610 int i = 0; 611 static if (IsVirtual!QP) { 612 info.vp ~= UnqualType!(QP).classinfo; 613 } 614 } 615 616 Runtime.methodInfos[&info] = &info; 617 Runtime.needUpdate = true; 618 } 619 620 static unregister() { 621 debug(explain) { 622 writefln("Unregistering %s", info); 623 } 624 625 info = Runtime.MethodInfo.init; 626 Runtime.needUpdate = true; 627 } 628 629 static template specRegistrar(alias Spec) { 630 alias SpecParams = std.traits.Parameters!Spec; 631 mixin(TheMethod.Wrapper!Spec.mixture); 632 633 __gshared openmethods.Runtime.SpecInfo si; 634 635 void register() { 636 si = openmethods.Runtime.SpecInfo.init; 637 si.pf = cast(void*) &wrapper; 638 639 debug(explain) { 640 tracefln( 641 "Registering override %s%s, pf = %s", 642 TheMethod.Name, SpecParams.stringof, &wrapper); 643 } 644 645 foreach (i; TheMethod.virtualPositions) { 646 si.vp ~= SpecParams[i].classinfo; 647 } 648 649 si.nextPtr = cast(void**) &TheMethod.nextPtr!SpecParams; 650 651 TheMethod.info.specInfos ~= &si; 652 openmethods.Runtime.needUpdate = true; 653 } 654 655 void unregister() 656 { 657 debug(explain) { 658 tracefln( 659 "Unregistering override %s%s, pf = %s", 660 TheMethod.Name, SpecParams.stringof, &wrapper); 661 } 662 si = openmethods.Runtime.SpecInfo.init; 663 Runtime.needUpdate = true; 664 } 665 } 666 667 // ========================================================================== 668 // Exceptions 669 670 static ReturnType notImplementedError(QualParams...) 671 { 672 import std.meta; 673 errorHandler(new MethodError(MethodError.NotImplemented, &info)); 674 static if (!is(ReturnType == void)) { 675 return ReturnType.init; 676 } 677 } 678 679 static ReturnType ambiguousCallError(QualParams...) 680 { 681 errorHandler(new MethodError(MethodError.AmbiguousCall, &info)); 682 static if (!is(ReturnType == void)) { 683 return ReturnType.init; 684 } 685 } 686 687 // ========================================================================== 688 // Dispatch 689 690 static auto getMptr(T)(T arg) @nogc @trusted nothrow 691 { 692 alias Word = Runtime.Word; 693 static if (Mptr == MptrInDeallocator) { 694 static if (is(T == class)) { 695 auto mptr = cast(const Word*) arg.classinfo.deallocator; 696 } else { 697 Object o = cast(Object) 698 (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 699 auto mptr = cast(const Word*) o.classinfo.deallocator; 700 } 701 } else static if (Mptr == MptrViaHash) { 702 static if (is(T == class)) { 703 auto mptr = Runtime.gv.ptr[Runtime.hash(*cast (void**) arg)].pw; 704 } else { 705 Object o = cast(Object) 706 (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 707 auto mptr = Runtime.gv.ptr[Runtime.hash(*cast (void**) o)].pw; 708 } 709 } 710 711 debug assert(mptr, "Cannot locate method table for " ~ T.classinfo.name); 712 713 return mptr; 714 } 715 716 static auto resolve(VP...)(VP args) @nogc @trusted nothrow 717 { 718 debug(traceCalls) { 719 import std.stdio; 720 trace(Name, VP.stringof); 721 } 722 723 static if (VP.length == 1) { 724 debug(traceCalls) { 725 tracef(" ", VP[0].stringof, ":"); 726 } 727 auto mptr = getMptr(args); 728 debug(traceCalls) { 729 tracef("%s %s", mptr, Method.info.slotStride.i); 730 } 731 auto pf = mptr[Method.info.slotStride.i].p; 732 } else { 733 assert(Method.info.slotStride.pw); 734 debug(traceCalls) { 735 trace("\n ", VP[0].stringof, ":"); 736 } 737 738 const (Word)* mtbl = getMptr(args[0]); 739 auto slotStride = Method.info.slotStride.pw; 740 auto slot = slotStride++.i; 741 auto dt = cast(const(Word)*) mtbl[slot].p; 742 debug(traceCalls) { 743 tracef(" mtbl = %s", mtbl); 744 tracef(" slot = %s", slot); 745 tracef(" dt = %s\n ", dt); 746 } 747 748 foreach (i, arg; args[1..$]) { 749 mtbl = getMptr(arg); 750 slot = slotStride++.i; 751 auto index = mtbl[slot].i; 752 auto stride = slotStride++.i; 753 debug(traceCalls) { 754 trace(VP[i + 1].stringof, ":"); 755 tracef(" mtbl = %s", mtbl); 756 tracef(" slot = %s", slot); 757 tracef(" index = %s", index); 758 tracef(" stride = %s", stride); 759 tracef(" : %s\n ", dt + index * stride); 760 } 761 dt += index * stride; 762 } 763 764 auto pf = dt.p; 765 } 766 767 debug(traceCalls) { 768 import std.stdio; 769 tracefln(" pf = %s", pf); 770 } 771 772 assert(pf); 773 774 return cast(Spec) pf; 775 } 776 } 777 778 // ============================================================================ 779 // Method Registration 780 781 interface Registrar 782 { 783 void registerMethods(); 784 void registerSpecs(); 785 void unregisterSpecs(); 786 void unregisterMethods(); 787 } 788 789 enum hasVirtualParameters(alias F) = 790 anySatisfy!(IsVirtual, std.traits.Parameters!F); 791 792 unittest 793 { 794 void meth(virtual!Object); 795 static assert(hasVirtualParameters!meth); 796 void nonmeth(Object); 797 static assert(!hasVirtualParameters!nonmeth); 798 } 799 800 string registrationMixture(alias MODULE, alias moduleName)() 801 { 802 import std.array; 803 804 string[] mixture; 805 806 foreach (m; __traits(allMembers, MODULE)) { 807 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 808 foreach (i, o; __traits(getOverloads, MODULE, m)) { 809 static if (hasVirtualParameters!(o)) { 810 mixture ~= openmethods.Method!(MODULE, m, i).aliases; 811 } 812 } 813 } 814 } 815 816 mixture ~= q{ 817 class __OpenMethodsRegistrar__ : openmethods.Registrar { 818 mixin openmethods.registrar!(%s, "%s"); 819 } 820 }.format(moduleName, moduleName); 821 822 return join(mixture, "\n"); 823 } 824 825 mixin template registrar(alias MODULE, alias ModuleName) 826 { 827 import openmethods; 828 import std.traits; 829 830 void registerMethods() 831 { 832 foreach (m; __traits(allMembers, MODULE)) { 833 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 834 foreach (i, o; __traits(getOverloads, MODULE, m)) { 835 static if (hasVirtualParameters!(o)) { 836 openmethods.Method!(MODULE, m, i).register; 837 } 838 } 839 } 840 } 841 } 842 843 void unregisterMethods() 844 { 845 foreach (m; __traits(allMembers, MODULE)) { 846 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 847 foreach (i, o; __traits(getOverloads, MODULE, m)) { 848 static if (hasVirtualParameters!(o)) { 849 openmethods.Method!(MODULE, m, i).unregister; 850 } 851 } 852 } 853 } 854 } 855 856 enum isNamedSpec(alias spec) = is( 857 typeof(getUDAs!(spec, method)[0]) == openmethods.method); 858 859 template specId(alias M, alias spec) 860 if (isNamedSpec!(spec)) { 861 enum specId = getUDAs!(spec, method)[0].id; 862 } 863 864 template specId(alias M, alias spec) 865 if (!isNamedSpec!(spec)) { 866 enum specId = __traits(identifier, spec)[1..$]; 867 } 868 869 void registerSpecs() { 870 foreach (m; __traits(allMembers, MODULE)) { 871 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 872 foreach (i, o; __traits(getOverloads, MODULE, m)) { 873 static if (hasUDA!(o, method)) { 874 static assert( 875 isNamedSpec!(o) || m[0] == '_', 876 m ~ ": method name must begin with an underscore, " 877 ~ "or be set in @method()"); 878 static assert( 879 !hasVirtualParameters!(o), 880 m ~ ": virtual! must not be used in method definitions"); 881 alias Method = typeof( 882 mixin(specId!(m, o))( 883 openmethods.MethodTag.init, Parameters!(o).init)); 884 Method.specRegistrar!(o).register; 885 } 886 } 887 } 888 } 889 } 890 891 void unregisterSpecs() { 892 foreach (m; __traits(allMembers, MODULE)) { 893 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 894 foreach (i, o; __traits(getOverloads, MODULE, m)) { 895 static if (hasUDA!(o, method)) { 896 alias Method = typeof( 897 mixin(specId!(m, o))( 898 openmethods.MethodTag.init, Parameters!(o).init)); 899 Method.specRegistrar!(o).unregister; 900 } 901 } 902 } 903 } 904 } 905 } 906 907 // ============================================================================ 908 // Method Table 909 910 struct Runtime 911 { 912 union Word 913 { 914 void* p; 915 Word* pw; 916 int i; 917 } 918 919 struct MethodInfo 920 { 921 string name; 922 ClassInfo[] vp; 923 SpecInfo*[] specInfos; 924 Word slotStride; 925 void* ambiguousCallError; 926 void* notImplementedError; 927 } 928 929 struct SpecInfo 930 { 931 void* pf; 932 ClassInfo[] vp; 933 void** nextPtr; 934 } 935 936 struct Method 937 { 938 MethodInfo* info; 939 Class*[] vp; 940 Spec*[] specs; 941 942 int[] slots; 943 int[] strides; 944 GroupMap[] groups; 945 void*[] dispatchTable; 946 Word* gvDispatchTable; 947 948 auto toString() const 949 { 950 return format("%s(%s)", info.name, vp.map!(c => c.name).join(", ")); 951 } 952 } 953 954 struct Spec 955 { 956 SpecInfo* info; 957 Class*[] params; 958 959 auto toString() const 960 { 961 return format("(%s)", params.map!(c => c.name).join(", ")); 962 } 963 } 964 965 struct Param 966 { 967 Method* method; 968 size_t param; 969 970 auto toString() const 971 { 972 return format("%s#%d", *method, param); 973 } 974 } 975 976 struct Class 977 { 978 ClassInfo info; 979 Class*[] directBases; 980 Class*[] directDerived; 981 Class*[Class*] conforming; 982 Param[] methodParams; 983 int nextSlot = 0; 984 int firstUsedSlot = -1; 985 int[] mtbl; 986 Word* gvMtbl; 987 988 989 @property auto name() const 990 { 991 return info.name.split(".")[$ - 1]; 992 } 993 994 @property auto isClass() 995 { 996 return info is Object.classinfo 997 || info.base is Object.classinfo 998 || info.base !is null; 999 } 1000 } 1001 1002 alias Registry = MethodInfo*[MethodInfo*]; 1003 1004 struct Metrics 1005 { 1006 size_t methodTableSize, dispatchTableSize, hashTableSize; 1007 ulong hashSearchAttempts; 1008 typeof(StopWatch.peek()) hashSearchTime; 1009 1010 auto toString() const 1011 { 1012 string hashMetrics; 1013 1014 if (hashSearchAttempts) { 1015 version (GNU) {} else { 1016 hashMetrics = format(", hash table size = %s, hash found after %s attempts and %g ms", hashTableSize, hashSearchAttempts, hashSearchTime.split!("nsecs").nsecs / 1000.); 1017 } 1018 } 1019 1020 return format("method table size: %s, dispatchTableSize: %s%s", 1021 methodTableSize, dispatchTableSize, hashMetrics); 1022 } 1023 } 1024 1025 __gshared Registry methodInfos; 1026 __gshared ClassInfo[] additionalClasses; 1027 __gshared Word[] gv; // Global Vector 1028 __gshared needUpdate = true; 1029 __gshared ulong hashMult; 1030 __gshared uint hashShift, hashSize; 1031 __gshared uint methodsUsingDeallocator; 1032 __gshared uint methodsUsingHash; 1033 1034 Method*[] methods; 1035 Class*[ClassInfo] classMap; 1036 Class*[] classes; 1037 Metrics metrics; 1038 1039 Metrics update() 1040 { 1041 if (!needUpdate) 1042 return Metrics(); 1043 1044 foreach (mod; ModuleInfo) { 1045 auto registrar = mod.name ~ "." ~ "__OpenMethodsRegistrar__"; 1046 foreach (c; mod.localClasses) { 1047 if (c.name == registrar) { 1048 (cast(Registrar) c.create()).registerMethods; 1049 } 1050 } 1051 } 1052 1053 foreach (mod; ModuleInfo) { 1054 auto registrar = mod.name ~ "." ~ "__OpenMethodsRegistrar__"; 1055 foreach (c; mod.localClasses) { 1056 if (c.name == registrar) { 1057 (cast(Registrar) c.create()).registerSpecs; 1058 } 1059 } 1060 } 1061 1062 // Create a Method object for each method. Create a Class object for all 1063 // the classes or interfaces that occur as virtual parameters in a method, 1064 // or were registered explicitly with 'registerClasses'. 1065 1066 seed(); 1067 1068 // Create a Class object for all the classes or interfaces that derive from 1069 // a class or interface that occur as virtual parameters in a method, 1070 // or were registered explicitly with 'registerClasses'. Also record in 1071 // each Class object all the method parameters that target it. 1072 1073 debug(explain) { 1074 tracefln("Scooping..."); 1075 } 1076 1077 foreach (mod; ModuleInfo) { 1078 foreach (c; mod.localClasses) { 1079 scoop(c); 1080 } 1081 } 1082 1083 // Fill the 'directBases' and 'directDerived' arrays in the Class objects. 1084 1085 initClasses(); 1086 1087 // Copy the Class objects to the 'classes' array, ensuring that derived 1088 // classes and interface come after their base class and interfaces, but as 1089 // close to them as possible. 1090 layer(); 1091 1092 // Fill the 'conforming' arrays, i.e. for each class record all the classes 1093 // and interfaces that are type compatible with it. Note that every class 1094 // is in its own 'conforming' array. 1095 1096 calculateInheritanceRelationships(); 1097 1098 // Check if there are classes that define the 'delete' operator. 1099 1100 checkDeallocatorConflicts(); 1101 1102 // For each method, reserve one slot per virtual parameter in the target 1103 // Class. 1104 1105 allocateSlots(); 1106 1107 // Build dispatch tables and install the global vectors. 1108 1109 buildTables(); 1110 1111 if (methodsUsingHash) { 1112 findHash(); 1113 } 1114 1115 installGlobalData(); 1116 1117 needUpdate = false; 1118 1119 return metrics; 1120 } 1121 1122 void unregister() 1123 { 1124 foreach (mod; ModuleInfo) { 1125 auto registrar = mod.name ~ "." ~ "__OpenMethodsRegistrar__"; 1126 foreach (c; mod.localClasses) { 1127 if (c.name == registrar) { 1128 (cast(Registrar) c.create()).unregisterSpecs; 1129 } 1130 } 1131 } 1132 1133 foreach (mod; ModuleInfo) { 1134 auto registrar = mod.name ~ "." ~ "__OpenMethodsRegistrar__"; 1135 foreach (c; mod.localClasses) { 1136 if (c.name == registrar) { 1137 (cast(Registrar) c.create()).unregisterMethods; 1138 } 1139 } 1140 } 1141 } 1142 1143 void seed() 1144 { 1145 debug(explain) { 1146 write("Seeding...\n roots:\n"); 1147 } 1148 1149 Class* upgrade(ClassInfo ci) 1150 { 1151 Class* c; 1152 if (ci in classMap) { 1153 c = classMap[ci]; 1154 } else { 1155 c = classMap[ci] = new Class(ci); 1156 debug(explain) { 1157 writef(" %s\n", c.name); 1158 } 1159 } 1160 return c; 1161 } 1162 1163 foreach (mi; methodInfos.values) { 1164 auto m = new Method(mi); 1165 methods ~= m; 1166 1167 foreach (size_t i, ci; mi.vp) { 1168 auto c = upgrade(ci); 1169 m.vp ~= c; 1170 c.methodParams ~= Runtime.Param(m, i); 1171 } 1172 1173 m.specs = mi.specInfos.map! 1174 (si => new Spec(si, 1175 si.vp.map! 1176 (ci => upgrade(ci)).array)).array; 1177 1178 } 1179 1180 debug(explain) { 1181 writeln(" manually registered:"); 1182 } 1183 1184 foreach (ci; additionalClasses) { 1185 if (ci !in classMap) { 1186 auto c = classMap[ci] = new Class(ci); 1187 debug(explain) { 1188 writeln(" ", c.name); 1189 } 1190 } 1191 } 1192 } 1193 1194 bool scoop(ClassInfo ci) 1195 { 1196 bool hasMethods; 1197 1198 foreach (i; ci.interfaces) { 1199 if (scoop(i.classinfo)) { 1200 hasMethods = true; 1201 } 1202 } 1203 1204 if (ci.base) { 1205 if (scoop(ci.base)) { 1206 hasMethods = true; 1207 } 1208 } 1209 1210 if (ci in classMap) { 1211 hasMethods = true; 1212 } else if (hasMethods) { 1213 if (ci !in classMap) { 1214 auto c = classMap[ci] = new Class(ci); 1215 debug(explain) { 1216 tracefln(" %s", c.name); 1217 } 1218 } 1219 } 1220 1221 return hasMethods; 1222 } 1223 1224 void initClasses() 1225 { 1226 foreach (ci, c; classMap) { 1227 foreach (i; ci.interfaces) { 1228 if (i.classinfo in classMap) { 1229 auto b = classMap[i.classinfo]; 1230 c.directBases ~= b; 1231 b.directDerived ~= c; 1232 } 1233 } 1234 1235 if (ci.base in classMap) { 1236 auto b = classMap[ci.base]; 1237 c.directBases ~= b; 1238 b.directDerived ~= c; 1239 } 1240 } 1241 } 1242 1243 void layer() 1244 { 1245 debug(explain) { 1246 tracefln("Layering..."); 1247 } 1248 1249 auto v = classMap.values.filter!(c => c.directBases.empty).array; 1250 auto m = assocArray(zip(v, v)); 1251 1252 while (!v.empty) { 1253 debug(explain) { 1254 tracefln(" %s", v.map!(c => c.name).join(" ")); 1255 } 1256 1257 v.sort!((a, b) => cmp(a.name, b.name) < 0); 1258 classes ~= v; 1259 1260 foreach (c; v) { 1261 classMap.remove(c.info); 1262 } 1263 1264 v = classMap.values.filter!(c => c.directBases.all!(b => b in m)).array; 1265 1266 foreach (c; v) { 1267 m[c] = c; 1268 } 1269 } 1270 } 1271 1272 void calculateInheritanceRelationships() 1273 { 1274 auto rclasses = classes.dup; 1275 reverse(rclasses); 1276 1277 foreach (c; rclasses) { 1278 c.conforming[c] = c; 1279 foreach (d; c.directDerived) { 1280 c.conforming[d] = d; 1281 foreach (dc; d.conforming) { 1282 c.conforming[dc] = dc; 1283 } 1284 } 1285 } 1286 } 1287 1288 void checkDeallocatorConflicts() 1289 { 1290 foreach (m; methods) { 1291 foreach (vp; m.vp) { 1292 foreach (c; vp.conforming) { 1293 if (c.info.deallocator 1294 && !(c.info.deallocator >= gv.ptr 1295 && c.info.deallocator < gv.ptr + gv.length)) { 1296 throw new MethodError(MethodError.DeallocatorInUse, m.info); 1297 } 1298 } 1299 } 1300 } 1301 } 1302 1303 void allocateSlots() 1304 { 1305 debug(explain) { 1306 writeln("Allocating slots..."); 1307 } 1308 1309 foreach (c; classes) { 1310 if (!c.methodParams.empty) { 1311 debug(explain) { 1312 tracefln(" %s...", c.name); 1313 } 1314 1315 foreach (mp; c.methodParams) { 1316 int slot = c.nextSlot++; 1317 1318 debug(explain) { 1319 writef(" for %s: allocate slot %d\n also in", mp, slot); 1320 } 1321 1322 if (mp.method.slots.length <= mp.param) { 1323 mp.method.slots.length = mp.param + 1; 1324 } 1325 1326 mp.method.slots[mp.param] = slot; 1327 1328 if (c.firstUsedSlot == -1) { 1329 c.firstUsedSlot = slot; 1330 } 1331 1332 bool [Class*] visited; 1333 visited[c] = true; 1334 1335 foreach (d; c.directDerived) { 1336 if (d !in visited) { 1337 allocateSlotDown(d, slot, visited); 1338 } 1339 } 1340 1341 debug(explain) { 1342 writeln(); 1343 } 1344 } 1345 } 1346 } 1347 foreach (c; classes) { 1348 c.mtbl.length = c.nextSlot; 1349 } 1350 } 1351 1352 void allocateSlotDown(Class* c, int slot, bool[Class*] visited) 1353 { 1354 debug(explain) { 1355 writef(" %s", c.name); 1356 } 1357 1358 visited[c] = true; 1359 1360 assert(slot >= c.nextSlot); 1361 1362 c.nextSlot = slot + 1; 1363 1364 if (c.firstUsedSlot == -1) { 1365 c.firstUsedSlot = slot; 1366 } 1367 1368 foreach (b; c.directBases) { 1369 if (b !in visited) { 1370 allocateSlotUp(b, slot, visited); 1371 } 1372 } 1373 1374 foreach (d; c.directDerived) { 1375 if (d !in visited) { 1376 allocateSlotDown(d, slot, visited); 1377 } 1378 } 1379 } 1380 1381 void allocateSlotUp(Class* c, int slot, bool[Class*] visited) 1382 { 1383 debug(explain) { 1384 writef(" %s", c.name); 1385 } 1386 1387 visited[c] = true; 1388 1389 assert(slot >= c.nextSlot); 1390 1391 c.nextSlot = slot + 1; 1392 1393 if (c.firstUsedSlot == -1) { 1394 c.firstUsedSlot = slot; 1395 } 1396 1397 foreach (b; c.directBases) { 1398 if (b !in visited) { 1399 allocateSlotUp(b, slot, visited); 1400 } 1401 } 1402 1403 foreach (d; c.directDerived) { 1404 if (d !in visited) { 1405 allocateSlotDown(d, slot, visited); 1406 } 1407 } 1408 } 1409 1410 static bool isMoreSpecific(Spec* a, Spec* b) 1411 { 1412 bool result = false; 1413 1414 for (int i = 0; i < a.params.length; i++) { 1415 if (a.params[i] !is b.params[i]) { 1416 if (a.params[i] in b.params[i].conforming) { 1417 result = true; 1418 } else if (b.params[i] in a.params[i].conforming) { 1419 return false; 1420 } 1421 } 1422 } 1423 1424 return result; 1425 } 1426 1427 static Spec*[] best(Spec*[] candidates) { 1428 Spec*[] best; 1429 1430 foreach (spec; candidates) { 1431 for (int i = 0; i != best.length; ) { 1432 if (isMoreSpecific(spec, best[i])) { 1433 best.remove(i); 1434 best.length -= 1; 1435 } else if (isMoreSpecific(best[i], spec)) { 1436 spec = null; 1437 break; 1438 } else { 1439 ++i; 1440 } 1441 } 1442 1443 if (spec) { 1444 best ~= spec; 1445 } 1446 } 1447 1448 return best; 1449 } 1450 1451 alias GroupMap = Class*[][BitArray]; 1452 1453 void buildTable(Method* m, size_t dim, GroupMap[] groups, BitArray candidates) 1454 { 1455 int groupIndex = 0; 1456 1457 foreach (mask, group; groups[dim]) { 1458 if (dim == 0) { 1459 auto finalMask = candidates & mask; 1460 Spec*[] applicable; 1461 1462 foreach (i, spec; m.specs) { 1463 if (finalMask[i]) { 1464 applicable ~= spec; 1465 } 1466 } 1467 1468 debug(explain) { 1469 tracefln("%*s dim %d group %d (%s): select best of %s", 1470 (m.vp.length - dim) * 2, "", 1471 dim, groupIndex, 1472 group.map!(c => c.name).join(", "), 1473 applicable.map!(spec => spec.toString).join(", ")); 1474 } 1475 1476 auto specs = best(applicable); 1477 1478 if (specs.length > 1) { 1479 m.dispatchTable ~= m.info.ambiguousCallError; 1480 } else if (specs.empty) { 1481 m.dispatchTable ~= m.info.notImplementedError; 1482 } else { 1483 m.dispatchTable ~= specs[0].info.pf; 1484 1485 debug(explain) { 1486 tracefln("%*s %s: pf = %s", 1487 (m.vp.length - dim) * 2, "", 1488 specs.map!(spec => spec.toString).join(", "), 1489 specs[0].info.pf); 1490 } 1491 } 1492 } else { 1493 debug(explain) { 1494 tracefln("%*s dim %d group %d (%s)", 1495 (m.vp.length - dim) * 2, "", 1496 dim, groupIndex, 1497 group.map!(c => c.name).join(", ")); 1498 } 1499 buildTable(m, dim - 1, groups, candidates & mask); 1500 } 1501 ++groupIndex; 1502 } 1503 } 1504 1505 void findHash() 1506 { 1507 import std.random, std.math; 1508 1509 void**[] vptrs; 1510 1511 foreach (c; classes) { 1512 if (c.info.vtbl.ptr) { 1513 vptrs ~= c.info.vtbl.ptr; 1514 } 1515 } 1516 1517 auto N = vptrs.length; 1518 StopWatch sw; 1519 sw.start(); 1520 1521 debug(explain) { 1522 tracefln(" finding hash factor for %s vptrs", N); 1523 } 1524 1525 int M; 1526 auto rnd = Random(unpredictableSeed); 1527 ulong totalAttempts; 1528 1529 M = 1; 1530 1531 while ((1 << M) < N) { 1532 ++M; 1533 } 1534 1535 for (int room = 2; room <= 6; ++room, ++M) { 1536 hashShift = 64 - M; 1537 hashSize = 1 << M; 1538 int[] buckets; 1539 buckets.length = hashSize; 1540 1541 debug(explain) { 1542 tracefln(" trying with M = %s, %s buckets", M, buckets.length); 1543 } 1544 1545 bool found; 1546 int attempts; 1547 1548 while (!found && attempts < 100_000) { 1549 ++attempts; 1550 ++totalAttempts; 1551 found = true; 1552 hashMult = rnd.uniform!ulong | 1; 1553 buckets[] = 0; 1554 foreach (vptr; vptrs) { 1555 auto h = hash(vptr); 1556 if (buckets[h]++) { 1557 found = false; 1558 break; 1559 } 1560 } 1561 } 1562 1563 metrics.hashSearchAttempts = totalAttempts; 1564 metrics.hashSearchTime = sw.peek(); 1565 metrics.hashTableSize = hashSize; 1566 1567 if (found) { 1568 debug(explain) { 1569 tracefln(" found %s after %s attempts and %s msecs", 1570 hashMult, totalAttempts, metrics.hashSearchTime.split!("msecs").msecs); 1571 } 1572 return; 1573 } 1574 } 1575 1576 throw new Error("cannot find hash factor"); 1577 } 1578 1579 static auto hash(void* p) { 1580 return cast(uint) ((hashMult * (cast(ulong) p)) >> hashShift); 1581 } 1582 1583 void buildTables() 1584 { 1585 foreach (m; methods) { 1586 debug(explain) { 1587 tracefln("Building dispatch table for %s", *m); 1588 } 1589 1590 auto dims = m.vp.length; 1591 m.groups.length = dims; 1592 1593 foreach (size_t dim, vp; m.vp) { 1594 debug(explain) { 1595 tracefln(" make groups for param #%s, class %s", dim, vp.name); 1596 } 1597 1598 foreach (conforming; vp.conforming) { 1599 if (conforming.isClass) { 1600 debug(explain) { 1601 tracefln(" specs applicable to %s", conforming.name); 1602 } 1603 1604 BitArray mask; 1605 mask.length = m.specs.length; 1606 1607 foreach (size_t specIndex, spec; m.specs) { 1608 if (conforming in spec.params[dim].conforming) { 1609 debug(explain) { 1610 tracefln(" %s", *spec); 1611 } 1612 mask[specIndex] = 1; 1613 } 1614 } 1615 1616 debug(explain) { 1617 tracefln(" bit mask = %s", mask); 1618 } 1619 1620 if (mask in m.groups[dim]) { 1621 debug(explain) { 1622 tracefln(" add class %s to existing group", conforming.name, mask); 1623 } 1624 m.groups[dim][mask] ~= conforming; 1625 } else { 1626 debug(explain) { 1627 tracefln(" create new group for %s", conforming.name); 1628 } 1629 m.groups[dim][mask] = [ conforming ]; 1630 } 1631 } 1632 } 1633 } 1634 1635 int stride = 1; 1636 m.strides.length = dims - 1; 1637 1638 foreach (size_t dim, vp; m.vp[1..$]) { 1639 debug(explain) { 1640 tracefln(" stride for dim %s = %s", dim + 1, stride); 1641 } 1642 stride *= m.groups[dim].length; 1643 m.strides[dim] = stride; 1644 } 1645 1646 BitArray none; 1647 none.length = m.specs.length; 1648 1649 debug(explain) { 1650 tracefln(" assign specs"); 1651 } 1652 1653 buildTable(m, dims - 1, m.groups, ~none); 1654 1655 debug(explain) { 1656 tracefln(" assign slots"); 1657 } 1658 1659 foreach (size_t dim, vp; m.vp) { 1660 debug(explain) { 1661 tracefln(" dim %s", dim); 1662 } 1663 1664 int i = 0; 1665 1666 foreach (group; m.groups[dim]) { 1667 debug(explain) { 1668 tracefln(" group %d (%s)", 1669 i, 1670 group.map!(c => c.name).join(", ")); 1671 } 1672 foreach (c; group) { 1673 c.mtbl[m.slots[dim]] = i; 1674 } 1675 1676 ++i; 1677 } 1678 } 1679 } 1680 } 1681 1682 void installGlobalData() 1683 { 1684 auto finalSize = hashSize; 1685 1686 foreach (m; methods) { 1687 if (m.vp.length > 1) { 1688 finalSize += m.slots.length + m.strides.length; 1689 finalSize += m.dispatchTable.length; 1690 } 1691 } 1692 1693 foreach (c; classes) { 1694 if (c.isClass) { 1695 finalSize += c.nextSlot - c.firstUsedSlot; 1696 } 1697 } 1698 1699 gv.length = 0; 1700 gv.reserve(finalSize); 1701 1702 debug(explain) { 1703 void trace(T...)(string format, T args) { 1704 writef("%4s %s: ", gv.length, gv.ptr + gv.length); 1705 writef(format, args); 1706 } 1707 } 1708 1709 debug(explain) { 1710 tracefln("Initializing global vector"); 1711 } 1712 1713 if (hashSize > 0) { 1714 debug(explain) 1715 trace("hash table\n"); 1716 gv.length = hashSize; 1717 } 1718 1719 Word word; 1720 1721 foreach (m; methods) { 1722 1723 if (m.info.vp.length > 1) { 1724 m.info.slotStride.pw = gv.ptr + gv.length; 1725 1726 debug(explain) { 1727 trace("slots and strides for %s\n", *m); 1728 } 1729 1730 int iSlot = 0; 1731 word.i = m.slots[iSlot++]; 1732 gv ~= word; 1733 1734 while (iSlot < m.slots.length) { 1735 word.i = m.slots[iSlot]; 1736 gv ~= word; 1737 word.i = m.strides[iSlot - 1]; 1738 gv ~= word; 1739 ++iSlot; 1740 } 1741 1742 m.gvDispatchTable = gv.ptr + gv.length; 1743 debug(explain) { 1744 trace( 1745 "and %d function pointers at %s\n", 1746 m.dispatchTable.length, m.gvDispatchTable); 1747 } 1748 foreach (p; m.dispatchTable) { 1749 word.p = p; 1750 gv ~= word; 1751 } 1752 } else { 1753 m.info.slotStride.i = m.slots[0]; 1754 } 1755 } 1756 1757 enforce(gv.length <= finalSize, 1758 format("gv.length = %s > finalSize = %s", gv.length, finalSize)); 1759 1760 foreach (c; classes) { 1761 if (c.isClass) { 1762 1763 c.gvMtbl = gv.ptr + gv.length - c.firstUsedSlot; 1764 1765 debug(explain) { 1766 trace("method table for %s\n", c.name); 1767 } 1768 1769 if (methodsUsingDeallocator) { 1770 c.info.deallocator = c.gvMtbl; 1771 debug(explain) { 1772 tracefln(" -> %s.deallocator", c.name); 1773 } 1774 } 1775 1776 if (hashSize > 0) { 1777 auto h = hash(c.info.vtbl.ptr); 1778 debug(explain) { 1779 tracefln(" -> %s hashTable[%d]", c.name, h); 1780 } 1781 gv[h].p = c.gvMtbl; 1782 } 1783 1784 gv.length += c.nextSlot - c.firstUsedSlot; 1785 } 1786 } 1787 1788 enforce(gv.length <= finalSize, 1789 format("gv.length = %s > finalSize = %s", gv.length, finalSize)); 1790 1791 foreach (m; methods) { 1792 auto slot = m.slots[0]; 1793 if (m.info.vp.length == 1) { 1794 debug(explain) { 1795 tracefln(" %s: 1-method, storing fp in mtbl, slot = %s", *m, slot); 1796 } 1797 int i = 0; 1798 foreach (group; m.groups[0]) { 1799 foreach (c; group) { 1800 Word* index = c.gvMtbl + slot; 1801 index.p = m.dispatchTable[i]; 1802 debug(explain) { 1803 tracefln(" group %s pf = %s %s", i, index.p, c.name); 1804 } 1805 } 1806 ++i; 1807 } 1808 } else { 1809 debug(explain) { 1810 tracefln( 1811 " %s: %s-method, storing col* in mtbl, slot = %s", 1812 *m, m.vp.length, slot); 1813 } 1814 1815 foreach (size_t dim, vp; m.vp) { 1816 debug(explain) { 1817 tracefln(" dim %s", dim); 1818 } 1819 1820 int groupIndex = 0; 1821 1822 foreach (group; m.groups[dim]) { 1823 debug(explain) { 1824 tracefln( 1825 " group %d (%s)", 1826 groupIndex, 1827 group.map!(c => c.name).join(", ")); 1828 } 1829 1830 if (dim == 0) { 1831 debug(explain) { 1832 tracefln( 1833 " [%s] <- %s", 1834 m.slots[dim], 1835 m.gvDispatchTable + groupIndex); 1836 } 1837 foreach (c; group) { 1838 c.gvMtbl[m.slots[dim]].p = m.gvDispatchTable + groupIndex; 1839 } 1840 } else { 1841 debug(explain) { 1842 tracefln( 1843 " [%s] <- %s", 1844 m.slots[dim], 1845 groupIndex); 1846 } 1847 foreach (c; group) { 1848 c.gvMtbl[m.slots[dim]].i = groupIndex; 1849 } 1850 } 1851 ++groupIndex; 1852 } 1853 } 1854 } 1855 1856 foreach (spec; m.specs) { 1857 auto nextSpec = findNext(spec, m.specs); 1858 *spec.info.nextPtr = nextSpec ? nextSpec.info.pf : null; 1859 } 1860 } 1861 1862 enforce( 1863 gv.length == finalSize, 1864 format("gv.length = %s <> finalSize = %s", gv.length, finalSize)); 1865 } 1866 1867 static auto findNext(Spec* spec, Spec*[] specs) 1868 { 1869 auto candidates = 1870 best(specs.filter!(other => isMoreSpecific(spec, other)).array); 1871 return candidates.length == 1 ? candidates.front : null; 1872 } 1873 1874 version (unittest) { 1875 int[] slots(alias MX)() 1876 { 1877 return methods.find!(m => m.info == &MX.TheMethod.info)[0].slots; 1878 } 1879 1880 Class* getClass(C)() 1881 { 1882 return classes.find!(c => c.info == C.classinfo)[0]; 1883 } 1884 } 1885 }