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 ref auto next(alias F, T...)(auto return ref scope T args) @trusted 275 { 276 alias TheMethod = typeof(F(MethodTag.init, args)); 277 return (cast(TheMethod.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 static import bolts.experimental.refraction; 295 mixin(openmethods.registrationMixture!(%s, "%s")); 296 }.format(moduleName, moduleName); 297 } 298 299 mixin template registerClasses(Classes...) { 300 shared static this() { 301 foreach (C; Classes) { 302 debug(explain) { 303 import std.stdio; 304 writefln("Registering class %s", C.stringof); 305 } 306 Runtime.additionalClasses ~= C.classinfo; 307 Runtime.needUpdate = true; 308 } 309 } 310 311 shared static ~this() 312 { 313 foreach (C; Classes) { 314 debug(explain) { 315 import std.stdio; 316 writefln("Unregistering class %s", C.stringof); 317 } 318 import std.algorithm, std.array; 319 Runtime.additionalClasses = 320 Runtime.additionalClasses.filter!(c => c != C.classinfo).array; 321 Runtime.needUpdate = true; 322 } 323 } 324 } 325 326 /++ 327 Update the runtime dispatch tables. Must be called after dynamically 328 loading or unloading a shared library. 329 +/ 330 331 Runtime.Metrics updateMethods() 332 { 333 Runtime rt; 334 rt.reset(); 335 return rt.update(); 336 } 337 338 void resetMethods() 339 { 340 Runtime rt; 341 rt.reset; 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 void trace(T...)(T args) nothrow 416 { 417 try { 418 stderr.write(args); 419 } catch (Exception) { 420 } 421 } 422 423 void tracef(T...)(T args) nothrow 424 { 425 try { 426 stderr.writef(args); 427 } catch (Exception) { 428 } 429 } 430 431 void tracefln(T...)(T args) nothrow 432 { 433 try { 434 stderr.writefln(args); 435 } catch (Exception) { 436 } 437 } 438 } 439 440 // ---------------------------------------------------------------------------- 441 // Meta-programming helpers 442 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 // ============================================================================ 451 // Method 452 453 struct MethodTag { } 454 455 enum MptrInDeallocator = "deallocator"; 456 enum MptrViaHash = "hash"; 457 458 private auto makeCallParams(rf.Parameter[] parameters) 459 { 460 return parameters.length.iota.map!( 461 i => parameters[i].withType("CallParams[%d]".format(i))).array; 462 } 463 464 private auto removeStorageClasses(rf.Parameter[] parameters) 465 { 466 return parameters.map!(p => p.withStorageClasses([])).array; 467 } 468 469 template isVirtual(alias Fun, uint i) 470 { 471 static if (is(FunctionTypeOf!(Fun) parameters == __parameters)) { 472 alias p = parameters[i..i+1]; 473 static if (isInstanceOf!(virtual, p)) { 474 enum isVirtual = true; 475 } else static if (__traits(compiles, __traits(getAttributes, p))) { 476 static foreach (a; __traits(getAttributes, p)) { 477 static if (__traits(isSame, a, virtual)) { 478 enum isVirtual = true; 479 } 480 } 481 } 482 } 483 484 static if (!__traits(compiles, { auto b = isVirtual; })) { 485 enum isVirtual = false; 486 } 487 } 488 489 class Method( 490 alias Module, string name, int index) : Method!( 491 __traits(getOverloads, Module, name)[index], name) 492 { 493 enum methodMixture = `alias %s = openmethods.Method!(%s, "%s", %d)`.format( 494 name, __traits(identifier, Module), name, index); 495 enum aliases = q{ 496 %s.dispatcher; 497 %s.discriminator; 498 }.format(methodMixture, methodMixture); 499 } 500 501 class Method(alias Declaration, string name = __traits(identifier, Declaration)) 502 { 503 enum Name = name; 504 505 alias QualParams = std.traits.Parameters!Declaration; 506 alias CallParams = staticMap!(UnqualType, QualParams); 507 alias ReturnType = std.traits.ReturnType!Declaration; 508 alias Word = Runtime.Word; 509 alias TheMethod = Method; 510 enum Arity = QualParams.length; 511 512 // ========================================================================== 513 // Meta-programming 514 515 enum Original = rf.refract!(Declaration, "Declaration"); 516 517 enum Editor = Original 518 .withReturnType("ReturnType") // not really needed but helps debugging 519 .withParameters(makeCallParams(Original.parameters)); 520 521 enum Mptr = "deallocator"; 522 523 alias isVirtual(uint i) = .isVirtual!(Declaration, i); 524 525 enum virtualPositions = Filter!( 526 isVirtual, aliasSeqOf!(Arity.iota)); 527 528 enum argumentMixture(uint i) = Editor.argumentMixtureArray[i]; 529 530 //pragma(msg, Declaration); 531 enum virtualArgListCode = 532 [staticMap!(argumentMixture, virtualPositions)].join(", "); 533 534 static template castArgCode(QualParam, size_t i) 535 { 536 static if (isVirtual!i) { 537 static if (is(UnqualType!QualParam == interface)) { 538 enum castArgCode = "cast(SpecParams[%s]) _%d".format(i, i); 539 } else { 540 enum castArgCode = "cast(SpecParams[%s]) cast(void*) _%d".format(i, i); 541 } 542 } else static if (IsCovariant!QualParam) { 543 static if (is(UnqualType!QualParam == class)) { 544 debug { 545 enum castArgCode = "cast(SpecParams[%s]) _%d".format(i, i); 546 } else { 547 enum castArgCode = "cast(SpecParams[%s]) cast(void*) _%d".format(i, i); 548 } 549 } else { 550 static assert(is(UnqualType!QualParam == interface), 551 "covariant argument must be a class or an interface"); 552 enum castArgCode = "cast(SpecParams[%s]) _%d".format(i, i); 553 } 554 } else { 555 enum castArgCode = "_%d".format(i); 556 } 557 } 558 559 enum castArgListCode(alias Spec) = { 560 string[] casts; 561 foreach (i, qp; QualParams) { 562 casts ~= castArgCode!(qp, i); 563 } 564 return casts.join(", "); 565 }(); 566 567 enum Wrapper(alias Spec) = Editor 568 .withStatic(true) 569 .withName("wrapper") 570 .withBody("{ return Spec(%s); }".format(castArgListCode!Spec)); 571 572 mixin( 573 "alias Spec = ", 574 Editor.withUdas([]).withName("function").mixture); 575 576 // dispatcher 577 enum Dispatcher = 578 Editor 579 .withStatic(true) 580 .withName("dispatcher") 581 .withBody( 582 "{ return resolve(%s)(%s); }".format( 583 virtualArgListCode, Editor.argumentMixture)); 584 mixin(Dispatcher.mixture); 585 586 // discriminator note that we do *not* carry parameter storage classes 587 // because we use CallParams[i].init to form an argument list when "calling" 588 // the discriminator to locate the method. 589 mixin( 590 Editor 591 .withStatic(true) 592 .withReturnType("TheMethod") 593 .withName("discriminator") 594 .withParameters( 595 [ rf.Parameter().withType("openmethods.MethodTag") ] 596 ~ Editor.parameters) 597 .mixture); 598 599 // ========================================================================== 600 // Method Registration 601 602 __gshared Runtime.MethodInfo info; 603 alias genericNextPtr = void function(); 604 __gshared genericNextPtr nextPtr(QualParams...) = null; 605 606 static register() { 607 if (info.registered > 0) 608 return; 609 610 ++info.registered; 611 612 info.name = Name; 613 614 debug(explain) { 615 writefln("Registering method %s - %s", info, TheMethod.stringof); 616 } 617 618 static if (Mptr == MptrInDeallocator) { 619 ++Runtime.methodsUsingDeallocator; 620 } else static if (Mptr == MptrViaHash) { 621 ++Runtime.methodsUsingHash; 622 } 623 624 info.ambiguousCallError = &ambiguousCallError; 625 info.notImplementedError = ¬ImplementedError; 626 627 foreach (i, QP; QualParams) { 628 static if (isVirtual!(i)) { 629 info.vp ~= UnqualType!(QP).classinfo; 630 } 631 } 632 633 Runtime.methodInfos[&info] = &info; 634 Runtime.needUpdate = true; 635 } 636 637 static reset() { 638 debug(explain) { 639 writefln("resetting %s", info); 640 } 641 642 info = Runtime.MethodInfo.init; 643 Runtime.needUpdate = true; 644 } 645 646 static template specRegistrar(alias Spec) { 647 alias SpecParams = std.traits.Parameters!Spec; 648 mixin(TheMethod.Wrapper!Spec.mixture); 649 650 __gshared openmethods.Runtime.SpecInfo si; 651 652 void register() { 653 si = openmethods.Runtime.SpecInfo.init; 654 si.pf = cast(void*) &wrapper; 655 656 debug(explain) { 657 tracefln( 658 "Registering override %s%s, pf = %s", 659 TheMethod.Name, SpecParams.stringof, &wrapper); 660 } 661 662 foreach (i; TheMethod.virtualPositions) { 663 si.vp ~= SpecParams[i].classinfo; 664 } 665 666 si.nextPtr = cast(void**) &TheMethod.nextPtr!SpecParams; 667 668 TheMethod.info.specInfos ~= &si; 669 openmethods.Runtime.needUpdate = true; 670 } 671 } 672 673 // ========================================================================== 674 // Exceptions 675 676 static ReturnType notImplementedError(QualParams...) 677 { 678 import std.meta; 679 errorHandler(new MethodError(MethodError.NotImplemented, &info)); 680 static if (!is(ReturnType == void)) { 681 return ReturnType.init; 682 } 683 } 684 685 static ReturnType ambiguousCallError(QualParams...) 686 { 687 errorHandler(new MethodError(MethodError.AmbiguousCall, &info)); 688 static if (!is(ReturnType == void)) { 689 return ReturnType.init; 690 } 691 } 692 693 // ========================================================================== 694 // Dispatch 695 696 static auto getMptr(T)(T arg) @nogc @trusted nothrow 697 { 698 alias Word = Runtime.Word; 699 static if (Mptr == MptrInDeallocator) { 700 static if (is(T == class)) { 701 auto mptr = cast(const Word*) arg.classinfo.deallocator; 702 } else { 703 Object o = cast(Object) 704 (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 705 auto mptr = cast(const Word*) o.classinfo.deallocator; 706 } 707 } else static if (Mptr == MptrViaHash) { 708 static if (is(T == class)) { 709 auto mptr = Runtime.gv.ptr[Runtime.hash(*cast (void**) arg)].pw; 710 } else { 711 Object o = cast(Object) 712 (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 713 auto mptr = Runtime.gv.ptr[Runtime.hash(*cast (void**) o)].pw; 714 } 715 } 716 717 debug assert(mptr, "Cannot locate method table for " ~ T.classinfo.name); 718 719 return mptr; 720 } 721 722 static auto resolve(VP...)(VP args) @nogc @trusted nothrow 723 { 724 debug(traceCalls) { 725 import std.stdio; 726 trace(Name, VP.stringof); 727 } 728 729 static if (VP.length == 1) { 730 debug(traceCalls) { 731 tracef(" ", VP[0].stringof, ":"); 732 } 733 auto mptr = getMptr(args); 734 debug(traceCalls) { 735 tracef("%s %s", mptr, Method.info.slotStride.i); 736 } 737 auto pf = mptr[Method.info.slotStride.i].p; 738 } else { 739 assert(Method.info.slotStride.pw); 740 debug(traceCalls) { 741 trace("\n ", VP[0].stringof, ":"); 742 } 743 744 const (Word)* mtbl = getMptr(args[0]); 745 auto slotStride = Method.info.slotStride.pw; 746 auto slot = slotStride++.i; 747 auto dt = cast(const(Word)*) mtbl[slot].p; 748 debug(traceCalls) { 749 tracef(" mtbl = %s", mtbl); 750 tracef(" slot = %s", slot); 751 tracef(" dt = %s\n ", dt); 752 } 753 754 foreach (i, arg; args[1..$]) { 755 mtbl = getMptr(arg); 756 slot = slotStride++.i; 757 auto index = mtbl[slot].i; 758 auto stride = slotStride++.i; 759 debug(traceCalls) { 760 trace(VP[i + 1].stringof, ":"); 761 tracef(" mtbl = %s", mtbl); 762 tracef(" slot = %s", slot); 763 tracef(" index = %s", index); 764 tracef(" stride = %s", stride); 765 tracef(" : %s\n ", dt + index * stride); 766 } 767 dt += index * stride; 768 } 769 770 auto pf = dt.p; 771 } 772 773 debug(traceCalls) { 774 import std.stdio; 775 tracefln(" pf = %s", pf); 776 } 777 778 assert(pf); 779 780 return cast(Spec) pf; 781 } 782 } 783 784 alias methodDispatcher(alias Fun) = Method!(Fun).dispatcher; 785 786 auto methodLocator(alias Fun, T...)(MethodTag, T args) 787 { 788 return Method!(Fun).discriminator; 789 } 790 791 // ============================================================================ 792 // Method Registration 793 794 interface Registrar 795 { 796 void reset(); 797 void registerMethods(); 798 void registerSpecs(); 799 } 800 801 enum hasVirtualParameters(alias F) = 802 anySatisfy!( 803 ApplyLeft!(isVirtual, F), 804 aliasSeqOf!(arity!F.iota)); 805 806 unittest 807 { 808 void meth(virtual!Object); 809 static assert(hasVirtualParameters!meth); 810 void nonmeth(Object); 811 static assert(!hasVirtualParameters!nonmeth); 812 } 813 814 string registrationMixture(alias MODULE, alias moduleName)() 815 { 816 import std.array; 817 818 string[] mixture; 819 820 foreach (m; __traits(allMembers, MODULE)) { 821 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 822 foreach (i, o; __traits(getOverloads, MODULE, m)) { 823 static if (hasVirtualParameters!(o)) { 824 mixture ~= openmethods.Method!(MODULE, m, i).aliases; 825 } 826 } 827 } 828 } 829 830 mixture ~= q{ 831 class __OpenMethodsRegistrar__ : openmethods.Registrar { 832 mixin openmethods.registrar!(%s, "%s"); 833 } 834 }.format(moduleName, moduleName); 835 836 return join(mixture, "\n"); 837 } 838 839 mixin template registrar(alias MODULE, alias ModuleName) 840 { 841 import openmethods; 842 import std.traits; 843 844 void reset() 845 { 846 debug(explain) { 847 tracefln("Resetting %s", ModuleName); 848 } 849 foreach (m; __traits(allMembers, MODULE)) { 850 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 851 foreach (i, o; __traits(getOverloads, MODULE, m)) { 852 static if (hasVirtualParameters!(o)) { 853 openmethods.Method!(MODULE, m, i).reset; 854 } 855 } 856 } 857 } 858 } 859 860 void registerMethods() 861 { 862 foreach (m; __traits(allMembers, MODULE)) { 863 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 864 foreach (i, o; __traits(getOverloads, MODULE, m)) { 865 static if (hasVirtualParameters!(o)) { 866 //openmethods.Method!(MODULE, m, i).register; 867 } 868 } 869 } 870 } 871 } 872 873 enum isNamedSpec(alias spec) = is( 874 typeof(getUDAs!(spec, method)[0]) == openmethods.method); 875 876 template specId(alias M, alias spec) 877 if (isNamedSpec!(spec)) { 878 enum specId = getUDAs!(spec, method)[0].id; 879 } 880 881 template specId(alias M, alias spec) 882 if (!isNamedSpec!(spec)) { 883 enum specId = __traits(identifier, spec)[1..$]; 884 } 885 886 void registerSpecs() { 887 foreach (m; __traits(allMembers, MODULE)) { 888 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 889 foreach (i, o; __traits(getOverloads, MODULE, m)) { 890 static if (hasUDA!(o, method)) { 891 static assert( 892 isNamedSpec!(o) || m[0] == '_', 893 m ~ ": method name must begin with an underscore, " 894 ~ "or be set in @method()"); 895 static assert( 896 !hasVirtualParameters!(o), 897 m ~ ": virtual! must not be used in method definitions"); 898 Parameters!(o) args; 899 alias Method = typeof( 900 mixin(specId!(m, o))( 901 openmethods.MethodTag.init, args)); 902 Method.register; 903 Method.specRegistrar!(o).register; 904 } 905 } 906 } 907 } 908 } 909 } 910 911 // ============================================================================ 912 // Method Table 913 914 struct Runtime 915 { 916 union Word 917 { 918 void* p; 919 Word* pw; 920 int i; 921 } 922 923 struct MethodInfo 924 { 925 int registered; 926 string name; 927 ClassInfo[] vp; 928 SpecInfo*[] specInfos; 929 Word slotStride; 930 void* ambiguousCallError; 931 void* notImplementedError; 932 } 933 934 struct SpecInfo 935 { 936 void* pf; 937 ClassInfo[] vp; 938 void** nextPtr; 939 } 940 941 struct Method 942 { 943 MethodInfo* info; 944 Class*[] vp; 945 Spec*[] specs; 946 947 int[] slots; 948 int[] strides; 949 GroupMap[] groups; 950 void*[] dispatchTable; 951 Word* gvDispatchTable; 952 953 auto toString() const 954 { 955 return format("%s(%s)", info.name, vp.map!(c => c.name).join(", ")); 956 } 957 } 958 959 struct Spec 960 { 961 SpecInfo* info; 962 Class*[] params; 963 964 auto toString() const 965 { 966 return format("(%s)", params.map!(c => c.name).join(", ")); 967 } 968 } 969 970 struct Param 971 { 972 Method* method; 973 size_t param; 974 975 auto toString() const 976 { 977 return format("%s#%d", *method, param); 978 } 979 } 980 981 struct Class 982 { 983 ClassInfo info; 984 Class*[] directBases; 985 Class*[] directDerived; 986 Class*[Class*] conforming; 987 Param[] methodParams; 988 int nextSlot = 0; 989 int firstUsedSlot = -1; 990 int[] mtbl; 991 Word* gvMtbl; 992 993 994 @property auto name() const 995 { 996 return info.name.split(".")[$ - 1]; 997 } 998 999 @property auto isClass() 1000 { 1001 return info is Object.classinfo 1002 || info.base is Object.classinfo 1003 || info.base !is null; 1004 } 1005 } 1006 1007 alias Registry = MethodInfo*[MethodInfo*]; 1008 1009 struct Metrics 1010 { 1011 size_t methodTableSize, dispatchTableSize, hashTableSize; 1012 ulong hashSearchAttempts; 1013 typeof(StopWatch.peek()) hashSearchTime; 1014 1015 auto toString() const 1016 { 1017 string hashMetrics; 1018 1019 if (hashSearchAttempts) { 1020 version (GNU) {} else { 1021 hashMetrics = format(", hash table size = %s, hash found after %s attempts and %g ms", hashTableSize, hashSearchAttempts, hashSearchTime.split!("nsecs").nsecs / 1000.); 1022 } 1023 } 1024 1025 return format("method table size: %s, dispatchTableSize: %s%s", 1026 methodTableSize, dispatchTableSize, hashMetrics); 1027 } 1028 } 1029 1030 __gshared Registry methodInfos; 1031 __gshared ClassInfo[] additionalClasses; 1032 __gshared Word[] gv; // Global Vector 1033 __gshared needUpdate = true; 1034 __gshared ulong hashMult; 1035 __gshared uint hashShift, hashSize; 1036 __gshared uint methodsUsingDeallocator; 1037 __gshared uint methodsUsingHash; 1038 1039 Method*[] methods; 1040 Class*[ClassInfo] classMap; 1041 Class*[] classes; 1042 Metrics metrics; 1043 1044 Metrics update() 1045 { 1046 if (!needUpdate) 1047 return Metrics(); 1048 1049 foreach (mod; ModuleInfo) { 1050 auto registrarClassName = mod.name ~ "." ~ "__OpenMethodsRegistrar__"; 1051 foreach (c; mod.localClasses) { 1052 if (c.name == registrarClassName) { 1053 auto registrar = (cast(Registrar) c.create()); 1054 (cast(Registrar) c.create()).registerMethods; 1055 } 1056 } 1057 } 1058 1059 foreach (mod; ModuleInfo) { 1060 auto registrar = mod.name ~ "." ~ "__OpenMethodsRegistrar__"; 1061 foreach (c; mod.localClasses) { 1062 if (c.name == registrar) { 1063 (cast(Registrar) c.create()).registerSpecs; 1064 } 1065 } 1066 } 1067 1068 // Create a Method object for each method. Create a Class object for all 1069 // the classes or interfaces that occur as virtual parameters in a method, 1070 // or were registered explicitly with 'registerClasses'. 1071 1072 seed(); 1073 1074 // Create a Class object for all the classes or interfaces that derive from 1075 // a class or interface that occur as virtual parameters in a method, 1076 // or were registered explicitly with 'registerClasses'. Also record in 1077 // each Class object all the method parameters that target it. 1078 1079 debug(explain) { 1080 tracefln("Scooping..."); 1081 } 1082 1083 foreach (mod; ModuleInfo) { 1084 foreach (c; mod.localClasses) { 1085 scoop(c); 1086 } 1087 } 1088 1089 // Fill the 'directBases' and 'directDerived' arrays in the Class objects. 1090 1091 initClasses(); 1092 1093 // Copy the Class objects to the 'classes' array, ensuring that derived 1094 // classes and interface come after their base class and interfaces, but as 1095 // close to them as possible. 1096 layer(); 1097 1098 // Fill the 'conforming' arrays, i.e. for each class record all the classes 1099 // and interfaces that are type compatible with it. Note that every class 1100 // is in its own 'conforming' array. 1101 1102 calculateInheritanceRelationships(); 1103 1104 // Check if there are classes that define the 'delete' operator. 1105 1106 checkDeallocatorConflicts(); 1107 1108 // For each method, reserve one slot per virtual parameter in the target 1109 // Class. 1110 1111 allocateSlots(); 1112 1113 // Build dispatch tables and install the global vectors. 1114 1115 buildTables(); 1116 1117 if (methodsUsingHash) { 1118 findHash(); 1119 } 1120 1121 installGlobalData(); 1122 1123 needUpdate = false; 1124 1125 return metrics; 1126 } 1127 1128 void reset() 1129 { 1130 foreach (methodInfo; Runtime.methodInfos) { 1131 methodInfo.specInfos = []; 1132 } 1133 } 1134 1135 void seed() 1136 { 1137 debug(explain) { 1138 write("Seeding...\n roots:\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\n", 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(" manually registered:"); 1174 } 1175 1176 foreach (ci; additionalClasses) { 1177 if (ci !in classMap) { 1178 auto c = classMap[ci] = new Class(ci); 1179 debug(explain) { 1180 writeln(" ", 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 debug(explain) { 1472 writefln( 1473 " warning: ambiguous: %d applicable methods", specs.length); 1474 } 1475 m.dispatchTable ~= m.info.ambiguousCallError; 1476 } else if (specs.empty) { 1477 debug(explain) { 1478 writeln(" warning: not implemented"); 1479 } 1480 m.dispatchTable ~= m.info.notImplementedError; 1481 } else { 1482 m.dispatchTable ~= specs[0].info.pf; 1483 1484 debug(explain) { 1485 tracefln("%*s %s: pf = %s", 1486 (m.vp.length - dim) * 2, "", 1487 specs.map!(spec => spec.toString).join(", "), 1488 specs[0].info.pf); 1489 } 1490 } 1491 } else { 1492 debug(explain) { 1493 tracefln("%*s dim %d group %d (%s)", 1494 (m.vp.length - dim) * 2, "", 1495 dim, groupIndex, 1496 group.map!(c => c.name).join(", ")); 1497 } 1498 buildTable(m, dim - 1, groups, candidates & mask); 1499 } 1500 ++groupIndex; 1501 } 1502 } 1503 1504 void findHash() 1505 { 1506 import std.random, std.math; 1507 1508 void**[] vptrs; 1509 1510 foreach (c; classes) { 1511 if (c.info.vtbl.ptr) { 1512 vptrs ~= c.info.vtbl.ptr; 1513 } 1514 } 1515 1516 auto N = vptrs.length; 1517 StopWatch sw; 1518 sw.start(); 1519 1520 debug(explain) { 1521 tracefln(" finding hash factor for %s vptrs", N); 1522 } 1523 1524 int M; 1525 auto rnd = Random(unpredictableSeed); 1526 ulong totalAttempts; 1527 1528 M = 1; 1529 1530 while ((1 << M) < N) { 1531 ++M; 1532 } 1533 1534 for (int room = 2; room <= 6; ++room, ++M) { 1535 hashShift = 64 - M; 1536 hashSize = 1 << M; 1537 int[] buckets; 1538 buckets.length = hashSize; 1539 1540 debug(explain) { 1541 tracefln(" trying with M = %s, %s buckets", M, buckets.length); 1542 } 1543 1544 bool found; 1545 int attempts; 1546 1547 while (!found && attempts < 100_000) { 1548 ++attempts; 1549 ++totalAttempts; 1550 found = true; 1551 hashMult = rnd.uniform!ulong | 1; 1552 buckets[] = 0; 1553 foreach (vptr; vptrs) { 1554 auto h = hash(vptr); 1555 if (buckets[h]++) { 1556 found = false; 1557 break; 1558 } 1559 } 1560 } 1561 1562 metrics.hashSearchAttempts = totalAttempts; 1563 metrics.hashSearchTime = sw.peek(); 1564 metrics.hashTableSize = hashSize; 1565 1566 if (found) { 1567 debug(explain) { 1568 tracefln(" found %s after %s attempts and %s msecs", 1569 hashMult, totalAttempts, metrics.hashSearchTime.split!("msecs").msecs); 1570 } 1571 return; 1572 } 1573 } 1574 1575 throw new Error("cannot find hash factor"); 1576 } 1577 1578 static auto hash(void* p) { 1579 return cast(uint) ((hashMult * (cast(ulong) p)) >> hashShift); 1580 } 1581 1582 void buildTables() 1583 { 1584 foreach (m; methods) { 1585 debug(explain) { 1586 tracefln("Building dispatch table for %s", *m); 1587 } 1588 1589 auto dims = m.vp.length; 1590 m.groups.length = dims; 1591 1592 foreach (size_t dim, vp; m.vp) { 1593 debug(explain) { 1594 tracefln(" make groups for param #%s, class %s", dim, vp.name); 1595 } 1596 1597 foreach (conforming; vp.conforming) { 1598 if (conforming.isClass) { 1599 debug(explain) { 1600 tracefln(" specs applicable to %s", conforming.name); 1601 } 1602 1603 BitArray mask; 1604 mask.length = m.specs.length; 1605 1606 foreach (size_t specIndex, spec; m.specs) { 1607 if (conforming in spec.params[dim].conforming) { 1608 debug(explain) { 1609 tracefln(" %s", *spec); 1610 } 1611 mask[specIndex] = 1; 1612 } 1613 } 1614 1615 debug(explain) { 1616 tracefln(" bit mask = %s", mask); 1617 } 1618 1619 if (mask in m.groups[dim]) { 1620 debug(explain) { 1621 tracefln(" add class %s to existing group", conforming.name, mask); 1622 } 1623 m.groups[dim][mask] ~= conforming; 1624 } else { 1625 debug(explain) { 1626 tracefln(" create new group for %s", conforming.name); 1627 } 1628 m.groups[dim][mask] = [ conforming ]; 1629 } 1630 } 1631 } 1632 } 1633 1634 int stride = 1; 1635 m.strides.length = dims - 1; 1636 1637 foreach (size_t dim, vp; m.vp[1..$]) { 1638 debug(explain) { 1639 tracefln(" stride for dim %s = %s", dim + 1, stride); 1640 } 1641 stride *= m.groups[dim].length; 1642 m.strides[dim] = stride; 1643 } 1644 1645 BitArray none; 1646 none.length = m.specs.length; 1647 1648 debug(explain) { 1649 tracefln(" assign specs"); 1650 } 1651 1652 buildTable(m, dims - 1, m.groups, ~none); 1653 1654 debug(explain) { 1655 tracefln(" assign slots"); 1656 } 1657 1658 foreach (size_t dim, vp; m.vp) { 1659 debug(explain) { 1660 tracefln(" dim %s", dim); 1661 } 1662 1663 int i = 0; 1664 1665 foreach (group; m.groups[dim]) { 1666 debug(explain) { 1667 tracefln(" group %d (%s)", 1668 i, 1669 group.map!(c => c.name).join(", ")); 1670 } 1671 foreach (c; group) { 1672 c.mtbl[m.slots[dim]] = i; 1673 } 1674 1675 ++i; 1676 } 1677 } 1678 } 1679 } 1680 1681 void installGlobalData() 1682 { 1683 auto finalSize = hashSize; 1684 1685 foreach (m; methods) { 1686 if (m.vp.length > 1) { 1687 finalSize += m.slots.length + m.strides.length; 1688 finalSize += m.dispatchTable.length; 1689 } 1690 } 1691 1692 foreach (c; classes) { 1693 if (c.isClass) { 1694 finalSize += c.nextSlot - c.firstUsedSlot; 1695 } 1696 } 1697 1698 gv.length = 0; 1699 gv.reserve(finalSize); 1700 1701 debug(explain) { 1702 void trace(T...)(string format, T args) { 1703 writef("%4s %s: ", gv.length, gv.ptr + gv.length); 1704 writef(format, args); 1705 } 1706 } 1707 1708 debug(explain) { 1709 tracefln("Initializing global vector"); 1710 } 1711 1712 if (hashSize > 0) { 1713 debug(explain) 1714 trace("hash table\n"); 1715 gv.length = hashSize; 1716 } 1717 1718 Word word; 1719 1720 foreach (m; methods) { 1721 1722 if (m.info.vp.length > 1) { 1723 m.info.slotStride.pw = gv.ptr + gv.length; 1724 1725 debug(explain) { 1726 trace("slots and strides for %s\n", *m); 1727 } 1728 1729 int iSlot = 0; 1730 word.i = m.slots[iSlot++]; 1731 gv ~= word; 1732 1733 while (iSlot < m.slots.length) { 1734 word.i = m.slots[iSlot]; 1735 gv ~= word; 1736 word.i = m.strides[iSlot - 1]; 1737 gv ~= word; 1738 ++iSlot; 1739 } 1740 1741 m.gvDispatchTable = gv.ptr + gv.length; 1742 debug(explain) { 1743 trace( 1744 "and %d function pointers at %s\n", 1745 m.dispatchTable.length, m.gvDispatchTable); 1746 } 1747 foreach (p; m.dispatchTable) { 1748 word.p = p; 1749 gv ~= word; 1750 } 1751 } else { 1752 m.info.slotStride.i = m.slots[0]; 1753 } 1754 } 1755 1756 enforce(gv.length <= finalSize, 1757 format("gv.length = %s > finalSize = %s", gv.length, finalSize)); 1758 1759 foreach (c; classes) { 1760 if (c.isClass) { 1761 1762 c.gvMtbl = gv.ptr + gv.length - c.firstUsedSlot; 1763 1764 debug(explain) { 1765 trace("method table for %s\n", c.name); 1766 } 1767 1768 if (methodsUsingDeallocator) { 1769 c.info.deallocator = c.gvMtbl; 1770 debug(explain) { 1771 tracefln(" -> %s.deallocator", c.name); 1772 } 1773 } 1774 1775 if (hashSize > 0) { 1776 auto h = hash(c.info.vtbl.ptr); 1777 debug(explain) { 1778 tracefln(" -> %s hashTable[%d]", c.name, h); 1779 } 1780 gv[h].p = c.gvMtbl; 1781 } 1782 1783 gv.length += c.nextSlot - c.firstUsedSlot; 1784 } 1785 } 1786 1787 enforce(gv.length <= finalSize, 1788 format("gv.length = %s > finalSize = %s", gv.length, finalSize)); 1789 1790 foreach (m; methods) { 1791 auto slot = m.slots[0]; 1792 if (m.info.vp.length == 1) { 1793 debug(explain) { 1794 tracefln(" %s: 1-method, storing fp in mtbl, slot = %s", *m, slot); 1795 } 1796 int i = 0; 1797 foreach (group; m.groups[0]) { 1798 foreach (c; group) { 1799 Word* index = c.gvMtbl + slot; 1800 index.p = m.dispatchTable[i]; 1801 debug(explain) { 1802 tracefln(" group %s pf = %s %s", i, index.p, c.name); 1803 } 1804 } 1805 ++i; 1806 } 1807 } else { 1808 debug(explain) { 1809 tracefln( 1810 " %s: %s-method, storing col* in mtbl, slot = %s", 1811 *m, m.vp.length, slot); 1812 } 1813 1814 foreach (size_t dim, vp; m.vp) { 1815 debug(explain) { 1816 tracefln(" dim %s", dim); 1817 } 1818 1819 int groupIndex = 0; 1820 1821 foreach (group; m.groups[dim]) { 1822 debug(explain) { 1823 tracefln( 1824 " group %d (%s)", 1825 groupIndex, 1826 group.map!(c => c.name).join(", ")); 1827 } 1828 1829 if (dim == 0) { 1830 debug(explain) { 1831 tracefln( 1832 " [%s] <- %s", 1833 m.slots[dim], 1834 m.gvDispatchTable + groupIndex); 1835 } 1836 foreach (c; group) { 1837 c.gvMtbl[m.slots[dim]].p = m.gvDispatchTable + groupIndex; 1838 } 1839 } else { 1840 debug(explain) { 1841 tracefln( 1842 " [%s] <- %s", 1843 m.slots[dim], 1844 groupIndex); 1845 } 1846 foreach (c; group) { 1847 c.gvMtbl[m.slots[dim]].i = groupIndex; 1848 } 1849 } 1850 ++groupIndex; 1851 } 1852 } 1853 } 1854 1855 foreach (spec; m.specs) { 1856 auto nextSpec = findNext(spec, m.specs); 1857 *spec.info.nextPtr = nextSpec ? nextSpec.info.pf : null; 1858 } 1859 } 1860 1861 enforce( 1862 gv.length == finalSize, 1863 format("gv.length = %s <> finalSize = %s", gv.length, finalSize)); 1864 } 1865 1866 static auto findNext(Spec* spec, Spec*[] specs) 1867 { 1868 auto candidates = 1869 best(specs.filter!(other => isMoreSpecific(spec, other)).array); 1870 return candidates.length == 1 ? candidates.front : null; 1871 } 1872 1873 version (unittest) { 1874 int[] slots(alias MX)() 1875 { 1876 return methods.find!(m => m.info == &MX.TheMethod.info)[0].slots; 1877 } 1878 1879 Class* getClass(C)() 1880 { 1881 return classes.find!(c => c.info == C.classinfo)[0]; 1882 } 1883 } 1884 }