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