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 }