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-2020 82 83 License: $(LINK2 http://boost.org/LICENSE_1_0.txt, Boost License 1.0). 84 85 Authors: Jean-Louis Leroy 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 static template specRegistrar(alias Spec) { 682 alias SpecParams = Parameters!Spec; 683 mixin(TheMethod.wrapperCode!Spec); 684 685 __gshared openmethods.Runtime.SpecInfo si; 686 687 void register() { 688 si.pf = cast(void*) &wrapper; 689 690 debug(explain) { 691 tracefln( 692 "Registering override %s%s, pf = %s", 693 TheMethod.Name, SpecParams.stringof, &wrapper); 694 } 695 696 foreach ( 697 cls; 698 openmethods.staticSlice!( 699 openmethods.AliasPack!(SpecParams), 700 openmethods.AliasPack!(TheMethod.virtualPositions)).Unpack) { 701 si.vp ~= cls.classinfo; 702 } 703 704 si.nextPtr = cast(void**) &TheMethod.nextPtr!SpecParams; 705 706 TheMethod.info.specInfos ~= &si; 707 openmethods.Runtime.needUpdate = true; 708 } 709 710 void unregister() 711 { 712 debug(explain) { 713 tracefln( 714 "Unregistering override %s%s, pf = %s", 715 TheMethod.Name, SpecParams.stringof, &wrapper); 716 } 717 718 import std.algorithm, std.array; 719 TheMethod.info.specInfos = TheMethod.info.specInfos.filter!(p => p != &si).array; 720 Runtime.needUpdate = true; 721 } 722 } 723 724 // ========================================================================== 725 // Exceptions 726 727 static R notImplementedError(QualParams...) 728 { 729 import std.meta; 730 errorHandler(new MethodError(MethodError.NotImplemented, &info)); 731 static if (!is(R == void)) { 732 return R.init; 733 } 734 } 735 736 static R ambiguousCallError(QualParams...) 737 { 738 errorHandler(new MethodError(MethodError.AmbiguousCall, &info)); 739 static if (!is(R == void)) { 740 return R.init; 741 } 742 } 743 744 // ========================================================================== 745 // Dispatch 746 747 static auto getMptr(T)(T arg) @nogc @trusted nothrow 748 { 749 alias Word = Runtime.Word; 750 static if (Mptr == MptrInDeallocator) { 751 static if (is(T == class)) { 752 auto mptr = cast(const Word*) arg.classinfo.deallocator; 753 } else { 754 Object o = cast(Object) 755 (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 756 auto mptr = cast(const Word*) o.classinfo.deallocator; 757 } 758 } else static if (Mptr == MptrViaHash) { 759 static if (is(T == class)) { 760 auto mptr = Runtime.gv.ptr[Runtime.hash(*cast (void**) arg)].pw; 761 } else { 762 Object o = cast(Object) 763 (cast(void*) arg - (cast(Interface*) **cast(void***) arg).offset); 764 auto mptr = Runtime.gv.ptr[Runtime.hash(*cast (void**) o)].pw; 765 } 766 } 767 768 debug assert(mptr, "Cannot locate method table for " ~ T.classinfo.name); 769 770 return mptr; 771 } 772 773 static auto resolve(VP...)(VP args) @nogc @trusted nothrow 774 { 775 debug(traceCalls) { 776 import std.stdio; 777 trace(Name, VP.stringof); 778 } 779 780 static if (VP.length == 1) { 781 debug(traceCalls) { 782 tracef(" ", VP[0].stringof, ":"); 783 } 784 auto mptr = getMptr(args); 785 debug(traceCalls) { 786 tracef("%s %s", mptr, Method.info.slotStride.i); 787 } 788 auto pf = mptr[Method.info.slotStride.i].p; 789 } else { 790 assert(Method.info.slotStride.pw); 791 debug(traceCalls) { 792 trace("\n ", VP[0].stringof, ":"); 793 } 794 795 const (Word)* mtbl = getMptr(args[0]); 796 auto slotStride = Method.info.slotStride.pw; 797 auto slot = slotStride++.i; 798 auto dt = cast(const(Word)*) mtbl[slot].p; 799 debug(traceCalls) { 800 tracef(" mtbl = %s", mtbl); 801 tracef(" slot = %s", slot); 802 tracef(" dt = %s\n ", dt); 803 } 804 805 foreach (i, arg; args[1..$]) { 806 mtbl = getMptr(arg); 807 slot = slotStride++.i; 808 auto index = mtbl[slot].i; 809 auto stride = slotStride++.i; 810 debug(traceCalls) { 811 trace(VP[i + 1].stringof, ":"); 812 tracef(" mtbl = %s", mtbl); 813 tracef(" slot = %s", slot); 814 tracef(" index = %s", index); 815 tracef(" stride = %s", stride); 816 tracef(" : %s\n ", dt + index * stride); 817 } 818 dt += index * stride; 819 } 820 821 auto pf = dt.p; 822 } 823 824 debug(traceCalls) { 825 import std.stdio; 826 tracefln(" pf = %s", pf); 827 } 828 829 assert(pf); 830 831 return cast(Spec) pf; 832 } 833 } 834 835 unittest 836 { 837 ref string foo(virtual!Object, lazy int, out real, virtual!Object) @safe; 838 alias M = MethodOf!foo; 839 static assert(M.argListCode == "a0, a1, a2, a3"); 840 static assert(M.isVirtualPosition!0); 841 static assert(!M.isVirtualPosition!1); 842 static assert(!M.isVirtualPosition!2); 843 static assert(M.isVirtualPosition!3); 844 static assert(M.virtualPositions == AliasSeq!(0, 3)); 845 static assert( 846 M.paramListCode == 847 " TheMethod.CallParams[0] a0, lazy TheMethod.CallParams[1] a1," ~ 848 " out TheMethod.CallParams[2] a2, TheMethod.CallParams[3] a3"); 849 assert(M.virtualArgListCode == "a0, a3"); 850 static assert(M.returnTypeCode == "ref ReturnType"); 851 static assert(M.functionPostfixCode == " @safe"); 852 } 853 854 // ============================================================================ 855 // Module Method Registration 856 857 enum hasVirtualParameters(alias F) = anySatisfy!(IsVirtual, Parameters!F); 858 859 unittest 860 { 861 void meth(virtual!Object); 862 static assert(hasVirtualParameters!meth); 863 void nonmeth(Object); 864 static assert(!hasVirtualParameters!nonmeth); 865 } 866 867 private template ConcatStorageClassModifiers(Modifiers...) 868 { 869 static if (Modifiers.length == 0) { 870 enum ConcatStorageClassModifiers = ""; 871 } else static if (Modifiers.length == 1) { 872 enum ConcatStorageClassModifiers = Modifiers[0]; 873 } else { 874 enum ConcatStorageClassModifiers = 875 Modifiers[0] ~ " " ~ ConcatStorageClassModifiers!(Modifiers[1..$]); 876 } 877 } 878 879 private template StorageClassModifiers(alias Func) 880 { 881 template Helper(int i) 882 { 883 static if (i == Parameters!(Func).length) { 884 enum Helper = []; 885 } else { 886 enum Helper = [ ConcatStorageClassModifiers!(__traits(getParameterStorageClasses, Func, i)) ] 887 ~ Helper!(i + 1); 888 } 889 } 890 enum StorageClassModifiers = Helper!0; 891 } 892 893 template MethodOf(alias Fun) { 894 static assert(hasVirtualParameters!Fun); 895 static if (hasUDA!(Fun, openmethods.mptr)) { 896 static assert(getUDAs!(Fun, openmethods.mptr).length == 1, "only une @mptr allowed"); 897 immutable index = getUDAs!(Fun, openmethods.mptr)[0].index; 898 } else { 899 immutable index = "deallocator"; 900 } 901 902 alias MethodOf = Method!(index, 903 ReturnType!Fun, 904 __traits(identifier, Fun), 905 functionAttributes!Fun, 906 StorageClassModifiers!Fun, 907 Parameters!Fun); 908 } 909 910 string _registerMethods(alias MODULE)() 911 { 912 import std.array; 913 914 string[] code; 915 916 foreach (m; __traits(allMembers, MODULE)) { 917 static if (is(typeof(__traits(getOverloads, MODULE, m)))) { 918 foreach (o; __traits(getOverloads, MODULE, m)) { 919 static if (hasVirtualParameters!o) { 920 code ~= openmethods.MethodOf!o.code; 921 } 922 } 923 } 924 } 925 926 return join(code, "\n"); 927 } 928 929 enum _isNamedSpec(alias spec) = is(typeof(getUDAs!(spec, method)[0]) == method); 930 931 template _specId(alias M, alias spec) 932 if (_isNamedSpec!(spec)) { 933 enum _specId = getUDAs!(spec, method)[0].id; 934 } 935 936 template _specId(alias M, alias spec) 937 if (!_isNamedSpec!(spec)) { 938 enum _specId = __traits(identifier, spec)[1..$]; 939 } 940 941 mixin template _registerSpecs(alias Module) 942 { 943 import openmethods; 944 import std.traits; 945 946 static this() { 947 foreach (_openmethods_m_; __traits(allMembers, Module)) { 948 static if (is(typeof(__traits(getOverloads, Module, _openmethods_m_)))) { 949 foreach (_openmethods_o_; __traits(getOverloads, Module, _openmethods_m_)) { 950 static if (hasUDA!(_openmethods_o_, method)) { 951 static assert(getUDAs!(_openmethods_o_, method).length == 1, "only one @method attribute is allowed"); 952 static assert(_isNamedSpec!(_openmethods_o_) || _openmethods_m_[0] == '_', 953 _openmethods_m_ ~ ": method name must begin with an underscore, " 954 ~ "or be set in @method()"); 955 static assert(!hasVirtualParameters!_openmethods_o_, 956 _openmethods_m_ ~ ": virtual! must not be used in method definitions"); 957 alias Method = typeof( 958 mixin(openmethods._specId!(_openmethods_m_, _openmethods_o_))( 959 openmethods.MethodTag.init, Parameters!(_openmethods_o_).init)); 960 Method.specRegistrar!_openmethods_o_.register; 961 } 962 } 963 } 964 } 965 } 966 967 static ~this() { 968 foreach (_openmethods_m_; __traits(allMembers, Module)) { 969 static if (is(typeof(__traits(getOverloads, Module, _openmethods_m_)))) { 970 foreach (_openmethods_o_; __traits(getOverloads, Module, _openmethods_m_)) { 971 static if (hasUDA!(_openmethods_o_, method)) { 972 static assert(getUDAs!(_openmethods_o_, method).length == 1, "only one @method attribute is allowed"); 973 static assert(_isNamedSpec!(_openmethods_o_) || _openmethods_m_[0] == '_', 974 _openmethods_m_ ~ ": method name must begin with an underscore, " 975 ~ "or be set in @method()"); 976 static assert(!hasVirtualParameters!_openmethods_o_, 977 _openmethods_m_ ~ ": virtual! must not be used in method definitions"); 978 alias Method = typeof( 979 mixin(openmethods._specId!(_openmethods_m_, _openmethods_o_))( 980 openmethods.MethodTag.init, Parameters!(_openmethods_o_).init)); 981 Method.specRegistrar!_openmethods_o_.unregister; 982 } 983 } 984 } 985 } 986 }} 987 988 // ============================================================================ 989 // Method Table 990 991 struct Runtime 992 { 993 union Word 994 { 995 void* p; 996 Word* pw; 997 int i; 998 } 999 1000 struct MethodInfo 1001 { 1002 string name; 1003 ClassInfo[] vp; 1004 SpecInfo*[] specInfos; 1005 Word slotStride; 1006 void* ambiguousCallError; 1007 void* notImplementedError; 1008 } 1009 1010 struct SpecInfo 1011 { 1012 void* pf; 1013 ClassInfo[] vp; 1014 void** nextPtr; 1015 } 1016 1017 struct Method 1018 { 1019 MethodInfo* info; 1020 Class*[] vp; 1021 Spec*[] specs; 1022 1023 int[] slots; 1024 int[] strides; 1025 GroupMap[] groups; 1026 void*[] dispatchTable; 1027 Word* gvDispatchTable; 1028 1029 auto toString() const 1030 { 1031 return format("%s(%s)", info.name, vp.map!(c => c.name).join(", ")); 1032 } 1033 } 1034 1035 struct Spec 1036 { 1037 SpecInfo* info; 1038 Class*[] params; 1039 1040 auto toString() const 1041 { 1042 return format("(%s)", params.map!(c => c.name).join(", ")); 1043 } 1044 } 1045 1046 struct Param 1047 { 1048 Method* method; 1049 size_t param; 1050 1051 auto toString() const 1052 { 1053 return format("%s#%d", *method, param); 1054 } 1055 } 1056 1057 struct Class 1058 { 1059 ClassInfo info; 1060 Class*[] directBases; 1061 Class*[] directDerived; 1062 Class*[Class*] conforming; 1063 Param[] methodParams; 1064 int nextSlot = 0; 1065 int firstUsedSlot = -1; 1066 int[] mtbl; 1067 Word* gvMtbl; 1068 1069 1070 @property auto name() const 1071 { 1072 return info.name.split(".")[$ - 1]; 1073 } 1074 1075 @property auto isClass() 1076 { 1077 return info is Object.classinfo 1078 || info.base is Object.classinfo 1079 || info.base !is null; 1080 } 1081 } 1082 1083 alias Registry = MethodInfo*[MethodInfo*]; 1084 1085 struct Metrics 1086 { 1087 size_t methodTableSize, dispatchTableSize, hashTableSize; 1088 ulong hashSearchAttempts; 1089 typeof(StopWatch.peek()) hashSearchTime; 1090 1091 auto toString() const 1092 { 1093 string hashMetrics; 1094 1095 if (hashSearchAttempts) { 1096 version (GNU) {} else { 1097 hashMetrics = format(", hash table size = %s, hash found after %s attempts and %g ms", hashTableSize, hashSearchAttempts, hashSearchTime.split!("nsecs").nsecs / 1000.); 1098 } 1099 } 1100 1101 return format("method table size: %s, dispatchTableSize: %s%s", 1102 methodTableSize, dispatchTableSize, hashMetrics); 1103 } 1104 } 1105 1106 __gshared Registry methodInfos; 1107 __gshared ClassInfo[] additionalClasses; 1108 __gshared Word[] gv; // Global Vector 1109 __gshared needUpdate = true; 1110 __gshared ulong hashMult; 1111 __gshared uint hashShift, hashSize; 1112 __gshared uint methodsUsingDeallocator; 1113 __gshared uint methodsUsingHash; 1114 1115 Method*[] methods; 1116 Class*[ClassInfo] classMap; 1117 Class*[] classes; 1118 Metrics metrics; 1119 1120 Metrics update() 1121 { 1122 // Create a Method object for each method. Create a Class object for all 1123 // the classes or interfaces that occur as virtual parameters in a method, 1124 // or were registered explicitly with 'registerClasses'. 1125 1126 seed(); 1127 1128 // Create a Class object for all the classes or interfaces that derive from 1129 // a class or interface that occur as virtual parameters in a method, 1130 // or were registered explicitly with 'registerClasses'. Also record in 1131 // each Class object all the method parameters that target it. 1132 1133 debug(explain) { 1134 tracefln("Scooping..."); 1135 } 1136 1137 foreach (mod; ModuleInfo) { 1138 foreach (c; mod.localClasses) { 1139 scoop(c); 1140 } 1141 } 1142 1143 // Fill the 'directBases' and 'directDerived' arrays in the Class objects. 1144 1145 initClasses(); 1146 1147 // Copy the Class objects to the 'classes' array, ensuring that derived 1148 // classes and interface come after their base class and interfaces, but as 1149 // close to them as possible. 1150 layer(); 1151 1152 // Fill the 'conforming' arrays, i.e. for each class record all the classes 1153 // and interfaces that are type compatible with it. Note that every class 1154 // is in its own 'conforming' array. 1155 1156 calculateInheritanceRelationships(); 1157 1158 // Check if there are classes that define the 'delete' operator. 1159 1160 checkDeallocatorConflicts(); 1161 1162 // For each method, reserve one slot per virtual parameter in the target 1163 // Class. 1164 1165 allocateSlots(); 1166 1167 // Build dispatch tables and install the global vectors. 1168 1169 buildTables(); 1170 1171 if (methodsUsingHash) { 1172 findHash(); 1173 } 1174 1175 installGlobalData(); 1176 1177 needUpdate = false; 1178 1179 return metrics; 1180 } 1181 1182 void seed() 1183 { 1184 debug(explain) { 1185 write("Seeding...\n "); 1186 } 1187 1188 Class* upgrade(ClassInfo ci) 1189 { 1190 Class* c; 1191 if (ci in classMap) { 1192 c = classMap[ci]; 1193 } else { 1194 c = classMap[ci] = new Class(ci); 1195 debug(explain) { 1196 writef(" %s", c.name); 1197 } 1198 } 1199 return c; 1200 } 1201 1202 foreach (mi; methodInfos.values) { 1203 auto m = new Method(mi); 1204 methods ~= m; 1205 1206 foreach (size_t i, ci; mi.vp) { 1207 auto c = upgrade(ci); 1208 m.vp ~= c; 1209 c.methodParams ~= Runtime.Param(m, i); 1210 } 1211 1212 m.specs = mi.specInfos.map! 1213 (si => new Spec(si, 1214 si.vp.map! 1215 (ci => upgrade(ci)).array)).array; 1216 1217 } 1218 1219 debug(explain) { 1220 writeln(); 1221 } 1222 1223 foreach (ci; additionalClasses) { 1224 if (ci !in classMap) { 1225 auto c = classMap[ci] = new Class(ci); 1226 debug(explain) { 1227 tracefln(" %s", c.name); 1228 } 1229 } 1230 } 1231 } 1232 1233 bool scoop(ClassInfo ci) 1234 { 1235 bool hasMethods; 1236 1237 foreach (i; ci.interfaces) { 1238 if (scoop(i.classinfo)) { 1239 hasMethods = true; 1240 } 1241 } 1242 1243 if (ci.base) { 1244 if (scoop(ci.base)) { 1245 hasMethods = true; 1246 } 1247 } 1248 1249 if (ci in classMap) { 1250 hasMethods = true; 1251 } else if (hasMethods) { 1252 if (ci !in classMap) { 1253 auto c = classMap[ci] = new Class(ci); 1254 debug(explain) { 1255 tracefln(" %s", c.name); 1256 } 1257 } 1258 } 1259 1260 return hasMethods; 1261 } 1262 1263 void initClasses() 1264 { 1265 foreach (ci, c; classMap) { 1266 foreach (i; ci.interfaces) { 1267 if (i.classinfo in classMap) { 1268 auto b = classMap[i.classinfo]; 1269 c.directBases ~= b; 1270 b.directDerived ~= c; 1271 } 1272 } 1273 1274 if (ci.base in classMap) { 1275 auto b = classMap[ci.base]; 1276 c.directBases ~= b; 1277 b.directDerived ~= c; 1278 } 1279 } 1280 } 1281 1282 void layer() 1283 { 1284 debug(explain) { 1285 tracefln("Layering..."); 1286 } 1287 1288 auto v = classMap.values.filter!(c => c.directBases.empty).array; 1289 auto m = assocArray(zip(v, v)); 1290 1291 while (!v.empty) { 1292 debug(explain) { 1293 tracefln(" %s", v.map!(c => c.name).join(" ")); 1294 } 1295 1296 v.sort!((a, b) => cmp(a.name, b.name) < 0); 1297 classes ~= v; 1298 1299 foreach (c; v) { 1300 classMap.remove(c.info); 1301 } 1302 1303 v = classMap.values.filter!(c => c.directBases.all!(b => b in m)).array; 1304 1305 foreach (c; v) { 1306 m[c] = c; 1307 } 1308 } 1309 } 1310 1311 void calculateInheritanceRelationships() 1312 { 1313 auto rclasses = classes.dup; 1314 reverse(rclasses); 1315 1316 foreach (c; rclasses) { 1317 c.conforming[c] = c; 1318 foreach (d; c.directDerived) { 1319 c.conforming[d] = d; 1320 foreach (dc; d.conforming) { 1321 c.conforming[dc] = dc; 1322 } 1323 } 1324 } 1325 } 1326 1327 void checkDeallocatorConflicts() 1328 { 1329 foreach (m; methods) { 1330 foreach (vp; m.vp) { 1331 foreach (c; vp.conforming) { 1332 if (c.info.deallocator 1333 && !(c.info.deallocator >= gv.ptr 1334 && c.info.deallocator < gv.ptr + gv.length)) { 1335 throw new MethodError(MethodError.DeallocatorInUse, m.info); 1336 } 1337 } 1338 } 1339 } 1340 } 1341 1342 void allocateSlots() 1343 { 1344 debug(explain) { 1345 writeln("Allocating slots..."); 1346 } 1347 1348 foreach (c; classes) { 1349 if (!c.methodParams.empty) { 1350 debug(explain) { 1351 tracefln(" %s...", c.name); 1352 } 1353 1354 foreach (mp; c.methodParams) { 1355 int slot = c.nextSlot++; 1356 1357 debug(explain) { 1358 writef(" for %s: allocate slot %d\n also in", mp, slot); 1359 } 1360 1361 if (mp.method.slots.length <= mp.param) { 1362 mp.method.slots.length = mp.param + 1; 1363 } 1364 1365 mp.method.slots[mp.param] = slot; 1366 1367 if (c.firstUsedSlot == -1) { 1368 c.firstUsedSlot = slot; 1369 } 1370 1371 bool [Class*] visited; 1372 visited[c] = true; 1373 1374 foreach (d; c.directDerived) { 1375 if (d !in visited) { 1376 allocateSlotDown(d, slot, visited); 1377 } 1378 } 1379 1380 debug(explain) { 1381 writeln(); 1382 } 1383 } 1384 } 1385 } 1386 foreach (c; classes) { 1387 c.mtbl.length = c.nextSlot; 1388 } 1389 } 1390 1391 void allocateSlotDown(Class* c, int slot, bool[Class*] visited) 1392 { 1393 debug(explain) { 1394 writef(" %s", c.name); 1395 } 1396 1397 visited[c] = true; 1398 1399 assert(slot >= c.nextSlot); 1400 1401 c.nextSlot = slot + 1; 1402 1403 if (c.firstUsedSlot == -1) { 1404 c.firstUsedSlot = slot; 1405 } 1406 1407 foreach (b; c.directBases) { 1408 if (b !in visited) { 1409 allocateSlotUp(b, slot, visited); 1410 } 1411 } 1412 1413 foreach (d; c.directDerived) { 1414 if (d !in visited) { 1415 allocateSlotDown(d, slot, visited); 1416 } 1417 } 1418 } 1419 1420 void allocateSlotUp(Class* c, int slot, bool[Class*] visited) 1421 { 1422 debug(explain) { 1423 writef(" %s", c.name); 1424 } 1425 1426 visited[c] = true; 1427 1428 assert(slot >= c.nextSlot); 1429 1430 c.nextSlot = slot + 1; 1431 1432 if (c.firstUsedSlot == -1) { 1433 c.firstUsedSlot = slot; 1434 } 1435 1436 foreach (b; c.directBases) { 1437 if (b !in visited) { 1438 allocateSlotUp(b, slot, visited); 1439 } 1440 } 1441 1442 foreach (d; c.directDerived) { 1443 if (d !in visited) { 1444 allocateSlotDown(d, slot, visited); 1445 } 1446 } 1447 } 1448 1449 static bool isMoreSpecific(Spec* a, Spec* b) 1450 { 1451 bool result = false; 1452 1453 for (int i = 0; i < a.params.length; i++) { 1454 if (a.params[i] !is b.params[i]) { 1455 if (a.params[i] in b.params[i].conforming) { 1456 result = true; 1457 } else if (b.params[i] in a.params[i].conforming) { 1458 return false; 1459 } 1460 } 1461 } 1462 1463 return result; 1464 } 1465 1466 static Spec*[] best(Spec*[] candidates) { 1467 Spec*[] best; 1468 1469 foreach (spec; candidates) { 1470 for (int i = 0; i != best.length; ) { 1471 if (isMoreSpecific(spec, best[i])) { 1472 best.remove(i); 1473 best.length -= 1; 1474 } else if (isMoreSpecific(best[i], spec)) { 1475 spec = null; 1476 break; 1477 } else { 1478 ++i; 1479 } 1480 } 1481 1482 if (spec) { 1483 best ~= spec; 1484 } 1485 } 1486 1487 return best; 1488 } 1489 1490 alias GroupMap = Class*[][BitArray]; 1491 1492 void buildTable(Method* m, size_t dim, GroupMap[] groups, BitArray candidates) 1493 { 1494 int groupIndex = 0; 1495 1496 foreach (mask, group; groups[dim]) { 1497 if (dim == 0) { 1498 auto finalMask = candidates & mask; 1499 Spec*[] applicable; 1500 1501 foreach (i, spec; m.specs) { 1502 if (finalMask[i]) { 1503 applicable ~= spec; 1504 } 1505 } 1506 1507 debug(explain) { 1508 tracefln("%*s dim %d group %d (%s): select best of %s", 1509 (m.vp.length - dim) * 2, "", 1510 dim, groupIndex, 1511 group.map!(c => c.name).join(", "), 1512 applicable.map!(spec => spec.toString).join(", ")); 1513 } 1514 1515 auto specs = best(applicable); 1516 1517 if (specs.length > 1) { 1518 m.dispatchTable ~= m.info.ambiguousCallError; 1519 } else if (specs.empty) { 1520 m.dispatchTable ~= m.info.notImplementedError; 1521 } else { 1522 m.dispatchTable ~= specs[0].info.pf; 1523 1524 debug(explain) { 1525 tracefln("%*s %s: pf = %s", 1526 (m.vp.length - dim) * 2, "", 1527 specs.map!(spec => spec.toString).join(", "), 1528 specs[0].info.pf); 1529 } 1530 } 1531 } else { 1532 debug(explain) { 1533 tracefln("%*s dim %d group %d (%s)", 1534 (m.vp.length - dim) * 2, "", 1535 dim, groupIndex, 1536 group.map!(c => c.name).join(", ")); 1537 } 1538 buildTable(m, dim - 1, groups, candidates & mask); 1539 } 1540 ++groupIndex; 1541 } 1542 } 1543 1544 void findHash() 1545 { 1546 import std.random, std.math; 1547 1548 void**[] vptrs; 1549 1550 foreach (c; classes) { 1551 if (c.info.vtbl.ptr) { 1552 vptrs ~= c.info.vtbl.ptr; 1553 } 1554 } 1555 1556 auto N = vptrs.length; 1557 StopWatch sw; 1558 sw.start(); 1559 1560 debug(explain) { 1561 tracefln(" finding hash factor for %s vptrs", N); 1562 } 1563 1564 int M; 1565 auto rnd = Random(unpredictableSeed); 1566 ulong totalAttempts; 1567 1568 for (int room = 2; room <= 6; ++room) { 1569 M = 1; 1570 1571 while ((1 << M) < room * N / 2) { 1572 ++M; 1573 } 1574 1575 hashShift = 64 - M; 1576 hashSize = 1 << M; 1577 int[] buckets; 1578 buckets.length = hashSize; 1579 1580 debug(explain) { 1581 tracefln(" trying with M = %s, %s buckets", M, buckets.length); 1582 } 1583 1584 bool found; 1585 int attempts; 1586 1587 while (!found && attempts < 100_000) { 1588 ++attempts; 1589 ++totalAttempts; 1590 found = true; 1591 hashMult = rnd.uniform!ulong | 1; 1592 buckets[] = 0; 1593 foreach (vptr; vptrs) { 1594 auto h = hash(vptr); 1595 if (buckets[h]++) { 1596 found = false; 1597 break; 1598 } 1599 } 1600 } 1601 1602 metrics.hashSearchAttempts = totalAttempts; 1603 metrics.hashSearchTime = sw.peek(); 1604 metrics.hashTableSize = hashSize; 1605 1606 if (found) { 1607 debug(explain) { 1608 tracefln(" found %s after %s attempts and %s msecs", 1609 hashMult, totalAttempts, metrics.hashSearchTime.split!("msecs").msecs); 1610 } 1611 return; 1612 } 1613 } 1614 1615 throw new Error("cannot find hash factor"); 1616 } 1617 1618 static auto hash(void* p) { 1619 return cast(uint) ((hashMult * (cast(ulong) p)) >> hashShift); 1620 } 1621 1622 void buildTables() 1623 { 1624 foreach (m; methods) { 1625 debug(explain) { 1626 tracefln("Building dispatch table for %s", *m); 1627 } 1628 1629 auto dims = m.vp.length; 1630 m.groups.length = dims; 1631 1632 foreach (size_t dim, vp; m.vp) { 1633 debug(explain) { 1634 tracefln(" make groups for param #%s, class %s", dim, vp.name); 1635 } 1636 1637 foreach (conforming; vp.conforming) { 1638 if (conforming.isClass) { 1639 debug(explain) { 1640 tracefln(" specs applicable to %s", conforming.name); 1641 } 1642 1643 BitArray mask; 1644 mask.length = m.specs.length; 1645 1646 foreach (size_t specIndex, spec; m.specs) { 1647 if (conforming in spec.params[dim].conforming) { 1648 debug(explain) { 1649 tracefln(" %s", *spec); 1650 } 1651 mask[specIndex] = 1; 1652 } 1653 } 1654 1655 debug(explain) { 1656 tracefln(" bit mask = %s", mask); 1657 } 1658 1659 if (mask in m.groups[dim]) { 1660 debug(explain) { 1661 tracefln(" add class %s to existing group", conforming.name, mask); 1662 } 1663 m.groups[dim][mask] ~= conforming; 1664 } else { 1665 debug(explain) { 1666 tracefln(" create new group for %s", conforming.name); 1667 } 1668 m.groups[dim][mask] = [ conforming ]; 1669 } 1670 } 1671 } 1672 } 1673 1674 int stride = 1; 1675 m.strides.length = dims - 1; 1676 1677 foreach (size_t dim, vp; m.vp[1..$]) { 1678 debug(explain) { 1679 tracefln(" stride for dim %s = %s", dim + 1, stride); 1680 } 1681 stride *= m.groups[dim].length; 1682 m.strides[dim] = stride; 1683 } 1684 1685 BitArray none; 1686 none.length = m.specs.length; 1687 1688 debug(explain) { 1689 tracefln(" assign specs"); 1690 } 1691 1692 buildTable(m, dims - 1, m.groups, ~none); 1693 1694 debug(explain) { 1695 tracefln(" assign slots"); 1696 } 1697 1698 foreach (size_t dim, vp; m.vp) { 1699 debug(explain) { 1700 tracefln(" dim %s", dim); 1701 } 1702 1703 int i = 0; 1704 1705 foreach (group; m.groups[dim]) { 1706 debug(explain) { 1707 tracefln(" group %d (%s)", 1708 i, 1709 group.map!(c => c.name).join(", ")); 1710 } 1711 foreach (c; group) { 1712 c.mtbl[m.slots[dim]] = i; 1713 } 1714 1715 ++i; 1716 } 1717 } 1718 } 1719 } 1720 1721 void installGlobalData() 1722 { 1723 auto finalSize = hashSize; 1724 1725 foreach (m; methods) { 1726 if (m.vp.length > 1) { 1727 finalSize += m.slots.length + m.strides.length; 1728 finalSize += m.dispatchTable.length; 1729 } 1730 } 1731 1732 foreach (c; classes) { 1733 if (c.isClass) { 1734 finalSize += c.nextSlot - c.firstUsedSlot; 1735 } 1736 } 1737 1738 gv.length = 0; 1739 gv.reserve(finalSize); 1740 1741 debug(explain) { 1742 void trace(T...)(string format, T args) { 1743 writef("%4s %s: ", gv.length, gv.ptr + gv.length); 1744 writef(format, args); 1745 } 1746 } 1747 1748 debug(explain) { 1749 tracefln("Initializing global vector"); 1750 } 1751 1752 if (hashSize > 0) { 1753 debug(explain) 1754 trace("hash table\n"); 1755 gv.length = hashSize; 1756 } 1757 1758 Word word; 1759 1760 foreach (m; methods) { 1761 1762 if (m.info.vp.length > 1) { 1763 m.info.slotStride.pw = gv.ptr + gv.length; 1764 1765 debug(explain) { 1766 trace("slots and strides for %s\n", *m); 1767 } 1768 1769 int iSlot = 0; 1770 word.i = m.slots[iSlot++]; 1771 gv ~= word; 1772 1773 while (iSlot < m.slots.length) { 1774 word.i = m.slots[iSlot]; 1775 gv ~= word; 1776 word.i = m.strides[iSlot - 1]; 1777 gv ~= word; 1778 ++iSlot; 1779 } 1780 1781 m.gvDispatchTable = gv.ptr + gv.length; 1782 debug(explain) { 1783 trace("and %d function pointers at %s\n", 1784 m.dispatchTable.length, m.gvDispatchTable); 1785 } 1786 foreach (p; m.dispatchTable) { 1787 word.p = p; 1788 gv ~= word; 1789 } 1790 } else { 1791 m.info.slotStride.i = m.slots[0]; 1792 } 1793 } 1794 1795 enforce(gv.length <= finalSize, 1796 format("gv.length = %s > finalSize = %s", gv.length, finalSize)); 1797 1798 foreach (c; classes) { 1799 if (c.isClass) { 1800 1801 c.gvMtbl = gv.ptr + gv.length - c.firstUsedSlot; 1802 1803 debug(explain) { 1804 trace("method table for %s\n", c.name); 1805 } 1806 1807 if (methodsUsingDeallocator) { 1808 c.info.deallocator = c.gvMtbl; 1809 debug(explain) { 1810 tracefln(" -> %s.deallocator", c.name); 1811 } 1812 } 1813 1814 if (hashSize > 0) { 1815 auto h = hash(c.info.vtbl.ptr); 1816 debug(explain) { 1817 tracefln(" -> %s hashTable[%d]", c.name, h); 1818 } 1819 gv[h].p = c.gvMtbl; 1820 } 1821 1822 gv.length += c.nextSlot - c.firstUsedSlot; 1823 } 1824 } 1825 1826 enforce(gv.length <= finalSize, 1827 format("gv.length = %s > finalSize = %s", gv.length, finalSize)); 1828 1829 foreach (m; methods) { 1830 auto slot = m.slots[0]; 1831 if (m.info.vp.length == 1) { 1832 debug(explain) { 1833 tracefln(" %s: 1-method, storing fp in mtbl, slot = %s", *m, slot); 1834 } 1835 int i = 0; 1836 foreach (group; m.groups[0]) { 1837 foreach (c; group) { 1838 Word* index = c.gvMtbl + slot; 1839 index.p = m.dispatchTable[i]; 1840 debug(explain) { 1841 tracefln(" group %s pf = %s %s", i, index.p, c.name); 1842 } 1843 } 1844 ++i; 1845 } 1846 } else { 1847 debug(explain) { 1848 tracefln(" %s: %s-method, storing col* in mtbl, slot = %s", 1849 *m, m.vp.length, slot); 1850 } 1851 1852 foreach (size_t dim, vp; m.vp) { 1853 debug(explain) { 1854 tracefln(" dim %s", dim); 1855 } 1856 1857 int groupIndex = 0; 1858 1859 foreach (group; m.groups[dim]) { 1860 debug(explain) { 1861 tracefln(" group %d (%s)", 1862 groupIndex, 1863 group.map!(c => c.name).join(", ")); 1864 } 1865 1866 if (dim == 0) { 1867 debug(explain) { 1868 tracefln(" [%s] <- %s", 1869 m.slots[dim], 1870 m.gvDispatchTable + groupIndex); 1871 } 1872 foreach (c; group) { 1873 c.gvMtbl[m.slots[dim]].p = m.gvDispatchTable + groupIndex; 1874 } 1875 } else { 1876 debug(explain) { 1877 tracefln(" [%s] <- %s", 1878 m.slots[dim], 1879 groupIndex); 1880 } 1881 foreach (c; group) { 1882 c.gvMtbl[m.slots[dim]].i = groupIndex; 1883 } 1884 } 1885 ++groupIndex; 1886 } 1887 } 1888 } 1889 1890 foreach (spec; m.specs) { 1891 auto nextSpec = findNext(spec, m.specs); 1892 *spec.info.nextPtr = nextSpec ? nextSpec.info.pf : null; 1893 } 1894 } 1895 1896 enforce(gv.length == finalSize, 1897 format("gv.length = %s <> finalSize = %s", gv.length, finalSize)); 1898 } 1899 1900 static auto findNext(Spec* spec, Spec*[] specs) 1901 { 1902 auto candidates = 1903 best(specs.filter!(other => isMoreSpecific(spec, other)).array); 1904 return candidates.length == 1 ? candidates.front : null; 1905 } 1906 1907 version (unittest) { 1908 int[] slots(alias MX)() 1909 { 1910 return methods.find!(m => m.info == &MX.TheMethod.info)[0].slots; 1911 } 1912 1913 Class* getClass(C)() 1914 { 1915 return classes.find!(c => c.info == C.classinfo)[0]; 1916 } 1917 } 1918 } 1919 1920 // string interpolation 1921 // Copied from https://github.com/Abscissa/scriptlike 1922 1923 private string interp(string str)() 1924 { 1925 static import std.conv; 1926 enum State 1927 { 1928 normal, 1929 dollar, 1930 code, 1931 } 1932 1933 auto state = State.normal; 1934 1935 string buf; 1936 buf ~= '`'; 1937 1938 foreach(char c; str) 1939 final switch(state) 1940 { 1941 case State.normal: 1942 if(c == '$') 1943 // Delay copying the $ until we find out whether it's 1944 // the start of an escape sequence. 1945 state = State.dollar; 1946 else if(c == '`') { 1947 buf ~= "`~\"`\"~`"; 1948 // "`~\"`\"~`" 1949 } else 1950 buf ~= c; 1951 break; 1952 1953 case State.dollar: 1954 if(c == '{') 1955 { 1956 state = State.code; 1957 buf ~= "`~_interp_text("; 1958 } 1959 else if(c == '$') 1960 buf ~= '$'; // Copy the previous $ 1961 else 1962 { 1963 buf ~= '$'; // Copy the previous $ 1964 buf ~= c; 1965 state = State.normal; 1966 } 1967 break; 1968 1969 case State.code: 1970 if(c == '}') 1971 { 1972 buf ~= ")~`"; 1973 state = State.normal; 1974 } 1975 else 1976 buf ~= c; 1977 break; 1978 } 1979 1980 // Finish up 1981 final switch(state) 1982 { 1983 case State.normal: 1984 buf ~= '`'; 1985 break; 1986 1987 case State.dollar: 1988 buf ~= "$`"; // Copy the previous $ 1989 break; 1990 1991 case State.code: 1992 throw new Exception( 1993 "Interpolated string contains an unterminated expansion. "~ 1994 "You're missing a closing curly brace." 1995 ); 1996 } 1997 1998 return buf; 1999 } 2000 2001 private string _interp_text(T...)(T args) 2002 { 2003 static import std.conv; 2004 static if(T.length == 0) 2005 return null; 2006 else 2007 return std.conv.text(args); 2008 }