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