1 module zua.vm.engine; 2 import zua.vm.hashmap; 3 import zua.vm.std.coroutine; 4 import std.bitmanip; 5 import std.math; 6 import std.variant; 7 import std.conv; 8 import std.typecons; 9 import std.uuid; 10 import core.thread; 11 12 /** Represents a VM opcode */ 13 enum Opcode { 14 // 0 operands: 15 Add, 16 Sub, 17 Mul, 18 Div, 19 Exp, 20 Mod, 21 Unm, 22 Not, 23 Len, 24 Concat, 25 26 Eq, 27 Ne, 28 Lt, 29 Le, 30 Gt, 31 Ge, 32 33 Ret, 34 Getfenv, 35 Call, 36 NamecallPrep, 37 Namecall, 38 Drop, 39 Dup, 40 DupN, 41 LdNil, 42 LdFalse, 43 LdTrue, 44 LdArgs, 45 46 NewTable, 47 GetTable, 48 SetTable, 49 SetTableRev, 50 SetArray, 51 52 DropLoop, 53 54 // 1 integer operand: 55 LdStr, 56 Jmp, 57 JmpT, 58 JmpF, 59 JmpNil, 60 Pack, 61 Unpack, 62 UnpackD, 63 UnpackRev, 64 Mkhv, /// make heap variable 65 Get, 66 Set, 67 GetC, 68 SetC, 69 GetRef, 70 SetRef, 71 ForPrep, 72 Loop, 73 Introspect, // introspect 0 = dup 74 DropTuple, 75 76 // 1 double operand: 77 LdNum, 78 // AddK, 79 // SubK, 80 // MulK, 81 // DivK, 82 // ModK, 83 // PowK, 84 85 // misc: 86 LdFun, 87 } 88 89 /** A Lua exception */ 90 class LuaError : Exception { 91 /** The data packaged with this exception */ 92 Value data; 93 94 /** The call stack, as it was when this error occurred */ 95 Traceframe[] stack; 96 97 /** The call stack, as it $(I actually) was when this error occurred */ 98 package Stackframe[] fullstack; 99 100 /** Construct a new Lua exception */ 101 this(Value data) @safe nothrow { 102 super("A Lua-side exception has occurred"); 103 this.data = data; 104 105 Stackframe runningFrame; 106 runningFrame.ip = running.engine.ip; 107 runningFrame.id = running.engine.id; 108 runningFrame.func = running; 109 110 fullstack = callstack.dup ~ runningFrame; 111 112 foreach (f; callstack) { 113 Traceframe frame; 114 frame.ip = f.ip; 115 frame.id = f.id; 116 stack ~= frame; 117 } 118 119 Traceframe frame; 120 frame.ip = running.engine.ip; 121 frame.id = running.engine.id; 122 stack ~= frame; 123 } 124 } 125 126 /** Represents a single frame in a stack trace */ 127 struct Traceframe { 128 /** The current instruction pointer of the function */ 129 size_t ip; 130 131 /** The ID of the engine running this stack frame */ 132 UUID id; 133 } 134 135 /** Represents a single stack frame */ 136 struct Stackframe { 137 /** The function that is in charge of this stack frame */ 138 FunctionValue func; 139 140 /** The current instruction pointer of the function */ 141 size_t ip; 142 143 /** The ID of the engine running this stack frame */ 144 UUID id; 145 } 146 147 package Stackframe[] callstack; 148 package FunctionValue running; 149 150 package pragma(inline) void pushCallstack() { 151 Stackframe frame = { 152 func: running, 153 ip: running.engine.ip, 154 id: running.engine.id 155 }; 156 callstack.assumeSafeAppend ~= frame; 157 } 158 159 package pragma(inline) void popCallstack() { 160 callstack = callstack[0 .. $ - 1]; 161 } 162 163 /** Table contents of a Value */ 164 final class TableValue { 165 package Value[] array; 166 package ulong maxArrayIndex = ~0UL; 167 package HashTable hash; 168 169 /** Create a new TableValue */ 170 this() { 171 hash = new HashTable; 172 } 173 174 /** Get a raw value */ 175 pragma(inline) Value* rawget(Value key) { 176 if (key.type == ValueType.Number && key.num > 0) { 177 ulong index = cast(ulong) key.num; 178 if (cast(double) index == key.num) { 179 index--; 180 if (index >= array.length) { 181 return hash.lookup(key); 182 } 183 else { 184 return &array[index]; 185 } 186 } 187 } 188 189 return hash.lookup(key); 190 } 191 192 /** Set a raw value */ 193 pragma(inline) void rawset(Value key, Value val) { 194 if (key.type == ValueType.Number && key.num > 0) { 195 ulong index = cast(ulong) key.num; 196 if (cast(double) index == key.num) { 197 index--; 198 if (index < array.capacity + 64 && index < maxArrayIndex) { 199 if (index >= array.length) 200 array.length = index + 1; 201 array[index] = val; 202 return; 203 } 204 else if (index < maxArrayIndex) { 205 maxArrayIndex = index; 206 } 207 } 208 } 209 210 hash.insert(key, val); 211 } 212 213 /** The metatable attached to this table */ 214 TableValue metatable; 215 216 /** Get the length of this value */ 217 pragma(inline) Value length() { 218 ulong low = 1; 219 ulong high = 1; 220 while (rawhas(Value(high))) { 221 high *= 2; 222 } 223 224 if (!rawhas(Value(1))) { 225 return Value(0); 226 } 227 228 while (true) { 229 ulong mid = (low + high) / 2; 230 const bool midThere = rawhas(Value(mid)); 231 const bool boundary = midThere && !rawhas(Value(mid + 1)); 232 if (boundary) { 233 return mid.to!Value; 234 } 235 else if (midThere) { 236 low = mid; 237 } 238 else { 239 high = mid; 240 } 241 } 242 } 243 244 /** Check if the table has a key */ 245 pragma(inline) bool rawhas(Value key) { 246 Value* ptr = rawget(key); 247 return ptr && !ptr.isNil; 248 } 249 250 /** Get a key */ 251 pragma(inline) Value get(Value key) { 252 Value* ptr = rawget(key); 253 if (ptr && !ptr.isNil) { 254 return *ptr; 255 } 256 else if (metatable !is null) { 257 Value index = metatable.get(Value("__index")); 258 if (index.type == ValueType.Function) { 259 return Value.from(index.call([Value(this), key])); 260 } 261 else if (index.type != ValueType.Nil) { 262 return index.get(key); 263 } 264 } 265 266 if (key.type == ValueType.Nil) throw new LuaError(Value("table index is nil")); 267 return Value(); 268 } 269 270 /** Set a key */ 271 pragma(inline) void set(Value key, Value value) { 272 if (key.type == ValueType.Nil) throw new LuaError(Value("table index is nil")); 273 274 if (metatable !is null) { 275 Value* ptr = rawget(key); 276 if (ptr && !ptr.isNil) { 277 *ptr = value; 278 return; 279 } 280 else { 281 Value index = metatable.get(Value("__newindex")); 282 if (index.type != ValueType.Nil) { 283 index.call([Value(this), key, value]); 284 return; 285 } 286 } 287 } 288 289 rawset(key, value); 290 } 291 } 292 293 /** Represents a userdata value */ 294 final class UserdataValue { 295 /** Pointer to user-defined data */ 296 void* data; 297 298 /** A UUID that can be used to identify the owner of this userdata */ 299 UUID ownerId; 300 301 /** The metatable of this UserdataValue */ 302 TableValue metatable; 303 304 /** Creates a new UserdataValue */ 305 this(void* data, TableValue metatable) { 306 this.data = data; 307 this.metatable = metatable; 308 } 309 310 /** Creates a new UserdataValue */ 311 this(TableValue metatable) { 312 this.metatable = metatable; 313 } 314 } 315 316 /** Function contents of a Value */ 317 final class FunctionValue { 318 /** Denotes the implementation-defined position at which this function is found in the code */ 319 size_t ip; 320 321 /** The engine to use when calling this function */ 322 Engine engine; 323 324 /** A list of upvalues that partain to this function */ 325 Value*[] upvalues; 326 327 /** The environment of this function */ 328 TableValue env; 329 330 /** 331 332 Call this function value with the given parameters, running it in a toplevel thread. 333 334 Uses the function's environment for the new thread's environment. 335 336 */ 337 Value[] ccall(Value[] args) { 338 return runToplevel(env, this, args); 339 } 340 341 /** Call this function value with the given parameters in the current context. */ 342 package pragma(inline) Value[] rawcall(Value[] args) { 343 FunctionValue save = running; 344 const bool toplevel = running is null; 345 if (!toplevel) pushCallstack(); 346 scope(exit) { 347 running = save; 348 if (!toplevel) popCallstack(); 349 } 350 running = this; 351 return engine.callf(this, args); 352 } 353 } 354 355 /** An enum representing the status of a given coroutine */ 356 enum CoroutineStatus { 357 Running, 358 Suspended, 359 Normal, 360 Dead 361 } 362 363 /** Thread contents of a Value */ 364 final class ThreadValue { 365 /** The D fiber that corresponds to this Lua thread */ 366 Fiber fiber; 367 368 /** The environment of this thread */ 369 TableValue env; 370 371 /** The status of this thread */ 372 CoroutineStatus status; 373 } 374 375 /** A enum containing the various types of Lua values */ 376 enum ValueType { 377 Nil, 378 Boolean, 379 380 Number, 381 String, 382 383 Table, 384 Function, 385 Thread, 386 Userdata, 387 Heap, 388 389 Tuple, 390 } 391 392 private TableValue stringMetatable; 393 394 /** Represents a Lua value */ 395 struct Value { 396 /** The type of this Value */ 397 ValueType type = ValueType.Nil; 398 union { 399 bool boolean; /// The boolean component of this Value 400 double num; /// The number component of this Value 401 string str; /// The string component of this Value 402 TableValue table; /// The table component of this Value 403 FunctionValue func; /// The function component of this Value 404 ThreadValue thread; /// The thread component of this Value 405 UserdataValue userdata; /// The userdata component of this Value 406 407 Value* heap; /// The reference component of this Value 408 Value[] tuple; /// The tuple component of this Value 409 } 410 411 bool opEquals(const Value other) const { 412 if (type != other.type) return false; 413 switch (type) { 414 case ValueType.Nil: 415 return true; 416 case ValueType.Boolean: 417 return boolean == other.boolean; 418 case ValueType.Number: 419 return num == other.num; 420 case ValueType.String: 421 return str == other.str; 422 case ValueType.Table: 423 return table is other.table; 424 case ValueType.Userdata: 425 return userdata is other.userdata; 426 case ValueType.Function: 427 return func is other.func; 428 case ValueType.Thread: 429 return thread is other.thread; 430 default: assert(0); 431 } 432 } 433 434 size_t toHash() const nothrow @safe { 435 return () @trusted { 436 switch (type) { 437 case ValueType.Nil: 438 return null.hashOf; 439 case ValueType.Boolean: 440 return boolean.hashOf; 441 case ValueType.Number: 442 return num.hashOf; 443 case ValueType.String: 444 return str.hashOf; 445 case ValueType.Table: 446 return table.hashOf; 447 case ValueType.Userdata: 448 return userdata.hashOf; 449 case ValueType.Function: 450 return func.hashOf; 451 case ValueType.Thread: 452 return thread.hashOf; 453 default: assert(0); 454 } 455 }(); 456 } 457 458 string toString() { 459 switch (type) { 460 case ValueType.Nil: 461 return "nil"; 462 case ValueType.Boolean: 463 return boolean ? "true" : "false"; 464 case ValueType.Number: 465 return num.to!string; 466 case ValueType.String: 467 return str; 468 case ValueType.Table: 469 return "table: 0x" ~ table.toHash.toChars!16.to!string; 470 case ValueType.Userdata: 471 return "userdata: 0x" ~ table.toHash.toChars!16.to!string; 472 case ValueType.Function: 473 return "function: 0x" ~ func.toHash.toChars!16.to!string; 474 case ValueType.Thread: 475 return "thread: 0x" ~ thread.toHash.toChars!16.to!string; 476 case ValueType.Tuple: 477 return tuple.to!string; 478 case ValueType.Heap: 479 return "^" ~ heap.toString; 480 default: 481 return "??"; 482 } 483 } 484 485 /** Convert to a Lua "string" */ 486 Value luaToString() { 487 Nullable!(Value[]) res = metacall("__tostring", [this]); 488 if (!res.isNull) { 489 if (res.get.length == 0) { 490 return Value(); 491 } 492 else { 493 return res.get[0]; 494 } 495 } 496 return Value(toString); 497 } 498 499 /** Check if this Value is nil */ 500 pragma(inline) bool isNil() { 501 return type == ValueType.Nil; 502 } 503 504 /** Construct a new Value */ 505 this(long v) { 506 type = ValueType.Number; 507 num = cast(double) v; 508 } 509 510 /** Construct a new Value */ 511 this(int v) { 512 type = ValueType.Number; 513 num = cast(double) v; 514 } 515 516 /** Construct a new Value */ 517 this(bool v) { 518 type = ValueType.Boolean; 519 boolean = v; 520 } 521 522 /** Construct a new Value */ 523 this(double v) { 524 type = ValueType.Number; 525 num = v; 526 } 527 528 /** Construct a new Value */ 529 this(string v) { 530 type = ValueType.String; 531 str = v; 532 } 533 534 /** Construct a new Value */ 535 this(TableValue v) { 536 type = ValueType.Table; 537 table = v; 538 } 539 540 /** Construct a new Value */ 541 this(UserdataValue v) { 542 type = ValueType.Userdata; 543 userdata = v; 544 } 545 546 /** Construct a new Value */ 547 this(FunctionValue v) { 548 type = ValueType.Function; 549 func = v; 550 } 551 552 /** Construct a new Value */ 553 this(ThreadValue v) { 554 type = ValueType.Thread; 555 thread = v; 556 } 557 558 /** Construct a new heap Value */ 559 this(Value* v) { 560 type = ValueType.Heap; 561 heap = v; 562 } 563 564 /** 565 566 Construct a new tuple Value. 567 568 This is not a traditional constructor, as it performs non-trivial computation, and verbosity 569 may be seen as being inversely proportional to performance. 570 571 */ 572 pragma(inline) static Value makeTuple(Value[] v) { 573 Value res; 574 res.type = ValueType.Tuple; 575 if (v.length == 0) 576 return res; 577 foreach (val; v[0 .. $ - 1]) { 578 if (val.type == ValueType.Tuple) { 579 if (val.tuple.length == 0) { 580 res.tuple.assumeSafeAppend ~= Value(); 581 } 582 else { 583 res.tuple.assumeSafeAppend ~= val.tuple[0]; 584 } 585 } 586 else { 587 res.tuple.assumeSafeAppend ~= val; 588 } 589 } 590 if (v[$ - 1].type == ValueType.Tuple) { 591 res.tuple.assumeSafeAppend ~= v[$ - 1].tuple; 592 } 593 else { 594 res.tuple.assumeSafeAppend ~= v[$ - 1]; 595 } 596 return res; 597 } 598 599 /** 600 601 Construct a new tuple Value, without flattening the tuple whatsoever. 602 603 May lead to problems if not used correctly. 604 605 */ 606 pragma(inline) static Value rawTupleUnsafe(Value[] v) { 607 Value res; 608 res.type = ValueType.Tuple; 609 res.tuple = v; 610 return res; 611 } 612 613 /** Convert a tuple to a single value */ 614 static Value from(Value[] arr) { 615 if (arr.length == 0) { 616 return Value(); 617 } 618 else { 619 return arr[0]; 620 } 621 } 622 623 /** Get the metatable of this value, or null if N/A */ 624 pragma(inline) TableValue metatable() { 625 if (type == ValueType.Table) return table.metatable; 626 if (type == ValueType.Userdata) return userdata.metatable; 627 if (type == ValueType.String) { 628 if (!stringMetatable) { 629 import zua.vm.std.string : stringlib; 630 631 stringMetatable = new TableValue; 632 stringMetatable.set(Value("__index"), stringlib); 633 stringMetatable.set(Value("__metatable"), Value("The metatable is locked")); 634 } 635 636 return stringMetatable; 637 } 638 639 return null; 640 } 641 642 /** Call a metamethod on this value */ 643 pragma(inline) Nullable!(Value[]) metacall(string method, Value[] args) { 644 TableValue meta = metatable; 645 if (meta is null) 646 return Nullable!(Value[]).init; 647 Value metamethod = meta.get(Value(method)); 648 if (!metamethod.isNil) { 649 return metamethod.call(args).nullable; 650 } 651 else { 652 return Nullable!(Value[]).init; 653 } 654 } 655 656 /** Convert this value to a bool */ 657 pragma(inline) bool toBool() const { 658 if (type == ValueType.Boolean && boolean == false) 659 return false; 660 661 if (type == ValueType.Nil) 662 return false; 663 664 return true; 665 } 666 667 /** Get the length of this value */ 668 pragma(inline) Value length() { 669 if (type == ValueType.Table) return table.length; 670 if (type == ValueType.String) return Value(str.length); 671 672 throw new LuaError(Value("attempt to get length of a " ~ typeStr ~ " value")); 673 } 674 675 /** Get a key */ 676 pragma(inline) Value get(Value key) { 677 if (type == ValueType.Table) return table.get(key); 678 679 TableValue meta = metatable; 680 681 if (meta is null) 682 throw new LuaError(Value("attempt to index a " ~ typeStr ~ " value")); 683 684 Value index = meta.get(Value("__index")); 685 if (index.type == ValueType.Function) { 686 return Value.from(index.call([this, key])); 687 } 688 else if (index.type != ValueType.Nil) { 689 return index.get(key); 690 } 691 692 throw new LuaError(Value("attempt to index a " ~ typeStr ~ " value")); 693 } 694 695 /** Set a key */ 696 pragma(inline) void set(Value key, Value value) { 697 if (type == ValueType.Table) return table.set(key, value); 698 699 TableValue meta = metatable; 700 701 if (meta is null) 702 throw new LuaError(Value("attempt to index a " ~ typeStr ~ " value")); 703 704 Value newindex = meta.get(Value("__newindex")); 705 if (newindex.type != ValueType.Nil) { 706 Value.from(newindex.call([this, key, value])); 707 return; 708 } 709 710 throw new LuaError(Value("attempt to index a " ~ typeStr ~ " value")); 711 } 712 713 /** Call this value */ 714 pragma(inline) Value[] call(Value[] args) { 715 if (type == ValueType.Function) return func.rawcall(args); 716 717 TableValue meta = metatable; 718 719 if (meta is null) 720 throw new LuaError(Value("attempt to call a " ~ typeStr ~ " value")); 721 722 Value newindex = meta.get(Value("__call")); 723 if (newindex.type != ValueType.Nil) { 724 return newindex.call(this ~ args); 725 } 726 727 throw new LuaError(Value("attempt to call a " ~ typeStr ~ " value")); 728 } 729 730 /** Return a string describing both these objects' types */ 731 pragma(inline) string typeStr(Value o) { 732 if (type == o.type) { 733 return "two " ~ typeStr ~ " values"; 734 } 735 else { 736 return typeStr ~ " with " ~ o.typeStr; 737 } 738 } 739 740 /** Return a string describing this object's type */ 741 pragma(inline) string typeStr() { 742 switch (type) { 743 case ValueType.Nil: 744 return "nil"; 745 case ValueType.Boolean: 746 return "boolean"; 747 748 case ValueType.Number: 749 return "number"; 750 case ValueType.String: 751 return "string"; 752 753 case ValueType.Table: 754 return "table"; 755 case ValueType.Function: 756 return "function"; 757 case ValueType.Thread: 758 return "thread"; 759 case ValueType.Userdata: 760 return "userdata"; 761 762 default: 763 assert(0, "got " ~ type.to!string); 764 } 765 } 766 767 /** Check if this is less than that */ 768 pragma(inline) bool lessThan(Value b) { 769 alias a = this; 770 if (a.type == ValueType.String && b.type == a.type) { 771 return a.str < b.str; 772 } 773 else if (a.type == ValueType.Number && b.type == a.type) { 774 return a.num < b.num; 775 } 776 777 TableValue meta = a.metatable; 778 if (meta is null) 779 throw new LuaError(Value("attempt to compare " ~ a.typeStr(b))); 780 TableValue metaOther = b.metatable; 781 if (metaOther is null) 782 throw new LuaError(Value("attempt to compare " ~ a.typeStr(b))); 783 Value method = meta.get(Value("__lt")); 784 if (method.isNil) 785 throw new LuaError(Value("attempt to compare " ~ a.typeStr(b))); 786 const Value methodOther = metaOther.get(Value("__lt")); 787 if (method == methodOther) { 788 auto res = method.call([a, b]); 789 if (res.length == 0) { 790 return false; 791 } 792 else { 793 return res[0].toBool; 794 } 795 } 796 else { 797 throw new LuaError(Value("attempt to compare " ~ a.typeStr(b))); 798 } 799 } 800 801 /** Check if this is less than or equal to that */ 802 pragma(inline) bool lessOrEqual(Value b) { 803 alias a = this; 804 if (a.type == ValueType.String && b.type == a.type) { 805 return a.str <= b.str; 806 } 807 else if (a.type == ValueType.Number && b.type == a.type) { 808 return a.num <= b.num; 809 } 810 811 TableValue meta = a.metatable; 812 if (meta is null) 813 throw new LuaError(Value("attempt to compare " ~ a.typeStr(b))); 814 TableValue metaOther = b.metatable; 815 if (metaOther is null) 816 throw new LuaError(Value("attempt to compare " ~ a.typeStr(b))); 817 Value method = meta.get(Value("__le")); 818 if (method.isNil) 819 throw new LuaError(Value("attempt to compare " ~ a.typeStr(b))); 820 const Value methodOther = metaOther.get(Value("__le")); 821 if (method == methodOther) { 822 auto res = method.call([a, b]); 823 if (res.length == 0) { 824 return false; 825 } 826 else { 827 return res[0].toBool; 828 } 829 } 830 else { 831 throw new LuaError(Value("attempt to compare " ~ a.typeStr(b))); 832 } 833 } 834 835 /** Check if this equals that, invoking any necessary metamethods */ 836 pragma(inline) bool equals(Value b) { 837 alias a = this; 838 if (a == b) 839 return true; 840 841 TableValue meta = a.metatable; 842 if (meta is null) 843 return false; 844 TableValue metaOther = b.metatable; 845 if (metaOther is null) 846 return false; 847 Value method = meta.get(Value("__eq")); 848 if (method.isNil) 849 return false; 850 const Value methodOther = metaOther.get(Value("__eq")); 851 if (method == methodOther) { 852 auto res = method.call([a, b]); 853 if (res.length == 0) { 854 return false; 855 } 856 else { 857 return res[0].toBool; 858 } 859 } 860 else { 861 return false; 862 } 863 } 864 } 865 866 /** Denotes a virtualization engine */ 867 class Engine { 868 /** The current instruction pointer of this engine */ 869 size_t[Fiber] ipTable; 870 // size_t ipTable; 871 872 /** Get the current IP */ 873 pragma(inline) size_t ip() @safe nothrow { 874 size_t* res = Fiber.getThis in ipTable; 875 if (res) { 876 return *res; 877 } 878 else { 879 return 0; 880 } 881 // return ipTable; 882 } 883 884 /** Set the current IP */ 885 pragma(inline) void ip(size_t value) @safe nothrow { 886 ipTable[Fiber.getThis] = value; 887 // ipTable = value; 888 } 889 890 /** A unique identifier for this engine */ 891 UUID id; 892 893 /** Call a function value within this virtualization engine */ 894 abstract Value[] callf(FunctionValue func, Value[] args); 895 }