-
Notifications
You must be signed in to change notification settings - Fork 556
/
wren_value.h
609 lines (483 loc) · 18.2 KB
/
wren_value.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
#ifndef wren_value_h
#define wren_value_h
#include <stdbool.h>
#include <stdint.h>
#include "wren_common.h"
#include "wren.h"
#include "wren_utils.h"
// This defines the built-in types and their core representations in memory.
// Since Wren is dynamically typed, any variable can hold a value of any type,
// and the type can change at runtime. Implementing this efficiently is
// critical for performance.
//
// The main type exposed by this is [Value]. A C variable of that type is a
// storage location that can hold any Wren value. The stack, global variables,
// and instance fields are all implemented in C as variables of type Value.
//
// The built-in types for booleans, numbers, and null are unboxed: their value
// is stored directly in the Value, and copying a Value copies the value. Other
// types--classes, instances of classes, functions, lists, and strings--are all
// reference types. They are stored on the heap and the Value just stores a
// pointer to it. Copying the Value copies a reference to the same object. The
// Wren implementation calls these "Obj", or objects, though to a user, all
// values are objects.
//
// There are two supported Value representations. The main one uses a technique
// called "NaN tagging" (explained in detail below) to store a number, any of
// the value types, or a pointer all inside a single double-precision floating
// point value. A larger, slower, Value type that uses a struct to store these
// is also supported, and is useful for debugging the VM.
//
// The representation is controlled by the `NAN_TAGGING` define. If that's
// defined, Nan tagging is used.
// TODO: Make these externally controllable.
#define STACK_SIZE 1024
#define MAX_CALL_FRAMES 256
typedef enum
{
VAL_FALSE,
VAL_NULL,
VAL_NUM,
VAL_TRUE,
VAL_OBJ
} ValueType;
typedef enum {
OBJ_CLASS,
OBJ_CLOSURE,
OBJ_FIBER,
OBJ_FN,
OBJ_INSTANCE,
OBJ_LIST,
OBJ_RANGE,
OBJ_STRING,
OBJ_UPVALUE
} ObjType;
typedef enum
{
// The object has been marked during the mark phase of GC.
FLAG_MARKED = 0x01,
} ObjFlags;
typedef struct sObj
{
unsigned int type : 4; // ObjType.
unsigned int flags : 1; // ObjFlags.
// The next object in the linked list of all currently allocated objects.
struct sObj* next;
} Obj;
#if WREN_NAN_TAGGING
typedef union
{
double num;
uint64_t bits;
} Value;
#else
typedef struct
{
ValueType type;
double num;
Obj* obj;
} Value;
#endif
// The dynamically allocated data structure for a variable that has been used
// by a closure. Whenever a function accesses a variable declared in an
// enclosing function, it will get to it through this.
//
// An upvalue can be either "closed" or "open". An open upvalue points directly
// to a [Value] that is still stored on the fiber's stack because the local
// variable is still in scope in the function where it's declared.
//
// When that local variable goes out of scope, the upvalue pointing to it will
// be closed. When that happens, the value gets copied off the stack into the
// upvalue itself. That way, it can have a longer lifetime than the stack
// variable.
typedef struct sUpvalue
{
// The object header. Note that upvalues have this because they are garbage
// collected, but they are not first class Wren objects.
Obj obj;
// Pointer to the variable this upvalue is referencing.
Value* value;
// If the upvalue is closed (i.e. the local variable it was pointing too has
// been popped off the stack) then the closed-over value will be hoisted out
// of the stack into here. [value] will then be changed to point to this.
Value closed;
// Open upvalues are stored in a linked list by the fiber. This points to the
// next upvalue in that list.
struct sUpvalue* next;
} Upvalue;
typedef struct
{
// Pointer to the current (really next-to-be-executed) instruction in the
// function's bytecode.
uint8_t* ip;
// The function or closure being executed.
Obj* fn;
// Index of the first stack slot used by this call frame. This will contain
// the receiver, followed by the function's parameters, then local variables
// and temporaries.
int stackStart;
} CallFrame;
typedef struct sObjFiber
{
Obj obj;
Value stack[STACK_SIZE];
int stackSize;
CallFrame frames[MAX_CALL_FRAMES];
int numFrames;
// Pointer to the first node in the linked list of open upvalues that are
// pointing to values still on the stack. The head of the list will be the
// upvalue closest to the top of the stack, and then the list works downwards.
Upvalue* openUpvalues;
// The fiber that ran this one. If this fiber is yielded, control will resume
// to this one. May be `NULL`.
struct sObjFiber* caller;
} ObjFiber;
typedef enum
{
// A normal value has been returned.
PRIM_VALUE,
// A runtime error occurred.
PRIM_ERROR,
// A new callframe has been pushed.
PRIM_CALL,
// A fiber is being switched to.
PRIM_RUN_FIBER
} PrimitiveResult;
typedef struct
{
Obj obj;
char* value;
// TODO: Flexible array.
} ObjString;
typedef PrimitiveResult (*Primitive)(WrenVM* vm, ObjFiber* fiber, Value* args);
// Stores debugging information for a function used for things like stack
// traces.
typedef struct
{
// The name of the function. Heap allocated and owned by the ObjFn.
char* name;
// The name of the source file where this function was defined. An [ObjString]
// because this will be shared among all functions defined in the same file.
ObjString* sourcePath;
// An array of line numbers. There is one element in this array for each
// bytecode in the function's bytecode array. The value of that element is
// the line in the source code that generated that instruction.
int* sourceLines;
} FnDebug;
// A first-class function object. A raw ObjFn can be used and invoked directly
// if it has no upvalues (i.e. [numUpvalues] is zero). If it does use upvalues,
// it must be wrapped in an [ObjClosure] first. The compiler is responsible for
// emitting code to ensure that that happens.
typedef struct
{
Obj obj;
// TODO: Make one of these a flexible array? I tried each and it didn't seem
// to help perf, but it bears more investigation.
Value* constants;
uint8_t* bytecode;
int numUpvalues;
int numConstants;
int bytecodeLength;
FnDebug* debug;
} ObjFn;
// An instance of a first-class function and the environment it has closed over.
// Unlike [ObjFn], this has captured the upvalues that the function accesses.
typedef struct
{
Obj obj;
// The function that this closure is an instance of.
ObjFn* fn;
// The upvalues this function has closed over.
Upvalue* upvalues[];
} ObjClosure;
typedef enum
{
// TODO: Unify these three:
// A primitive method implemented in C that immediately returns a value.
METHOD_PRIMITIVE,
// A externally-defined C method.
METHOD_FOREIGN,
// A normal user-defined method.
METHOD_BLOCK,
// No method for the given symbol.
METHOD_NONE
} MethodType;
typedef struct
{
MethodType type;
// The method function itself. The [type] determines which field of the union
// is used.
union
{
Primitive primitive;
WrenForeignMethodFn foreign;
// May be a [ObjFn] or [ObjClosure].
Obj* fn;
};
} Method;
DECLARE_BUFFER(Method, Method);
typedef struct sObjClass
{
Obj obj;
struct sObjClass* metaclass;
struct sObjClass* superclass;
// The number of fields needed for an instance of this class, including all
// of its superclass fields.
int numFields;
// The table of methods that are defined in or inherited by this class.
// Methods are called by symbol, and the symbol directly maps to an index in
// this table. This makes method calls fast at the expense of empty cells in
// the list for methods the class doesn't support.
//
// You can think of it as a hash table that never has collisions but has a
// really low load factor. Since methods are pretty small (just a type and a
// pointer), this should be a worthwhile trade-off.
MethodBuffer methods;
} ObjClass;
typedef struct
{
Obj obj;
ObjClass* classObj;
Value fields[];
} ObjInstance;
typedef struct
{
Obj obj;
// The number of elements allocated.
int capacity;
// The number of items in the list.
int count;
// Pointer to a contiguous array of [capacity] elements.
Value* elements;
} ObjList;
typedef struct
{
Obj obj;
// The beginning of the range.
double from;
// The end of the range. May be greater or less than [from].
double to;
// True if [to] is included in the range.
bool isInclusive;
} ObjRange;
// Value -> ObjClass*.
#define AS_CLASS(value) ((ObjClass*)AS_OBJ(value))
// Value -> ObjClosure*.
#define AS_CLOSURE(value) ((ObjClosure*)AS_OBJ(value))
// Value -> ObjFiber*.
#define AS_FIBER(v) ((ObjFiber*)AS_OBJ(v))
// Value -> ObjFn*.
#define AS_FN(value) ((ObjFn*)AS_OBJ(value))
// Value -> ObjInstance*.
#define AS_INSTANCE(value) ((ObjInstance*)AS_OBJ(value))
// Value -> ObjList*.
#define AS_LIST(value) ((ObjList*)AS_OBJ(value))
// Value -> double.
#define AS_NUM(v) ((v).num)
// Value -> ObjRange*.
#define AS_RANGE(v) ((ObjRange*)AS_OBJ(v))
// Value -> ObjString*.
#define AS_STRING(v) ((ObjString*)AS_OBJ(v))
// Value -> const char*.
#define AS_CSTRING(v) (AS_STRING(v)->value)
// Convert [boolean] to a boolean [Value].
#define BOOL_VAL(boolean) (boolean ? TRUE_VAL : FALSE_VAL)
// Returns true if [value] is a bool.
#define IS_BOOL(value) (wrenIsBool(value))
// Returns true if [value] is a closure.
#define IS_CLOSURE(value) (wrenIsClosure(value))
// Returns true if [value] is a function object.
#define IS_FN(value) (wrenIsFn(value))
// Returns true if [value] is an instance.
#define IS_INSTANCE(value) (wrenIsInstance(value))
// Returns true if [value] is a range object.
#define IS_RANGE(value) (wrenIsRange(value))
// Returns true if [value] is a string object.
#define IS_STRING(value) (wrenIsString(value))
// An IEEE 754 double-precision float is a 64-bit value with bits laid out like:
//
// 1 Sign bit
// | 11 Exponent bits
// | | 52 Mantissa (i.e. fraction) bits
// | | |
// S(Exponent--)(Mantissa-----------------------------------------)
//
// The details of how these are used to represent numbers aren't really
// relevant here as long we don't interfere with them. The important bit is NaN.
//
// An IEEE double can represent a few magical values like NaN ("not a number"),
// Infinity, and -Infinity. A NaN is any value where all exponent bits are set:
//
// v--NaN bits
// -111111111111---------------------------------------------------
//
// Here, "-" means "doesn't matter". Any bit sequence that matches the above is
// a NaN. With all of those "-", it obvious there are a *lot* of different
// bit patterns that all mean the same thing. NaN tagging takes advantage of
// this. We'll use those available bit patterns to represent things other than
// numbers without giving up any valid numeric values.
//
// NaN values come in two flavors: "signalling" and "quiet". The former are
// intended to halt execution, while the latter just flow through arithmetic
// operations silently. We want the latter. Quiet NaNs are indicated by setting
// the highest mantissa bit:
//
// v--Mantissa bit
// -[NaN ]1--------------------------------------------------
//
// If all of the NaN bits are set, it's not a number. Otherwise, it is.
// That leaves all of the remaining bits as available for us to play with. We
// stuff a few different kinds of things here: special singleton values like
// "true", "false", and "null", and pointers to objects allocated on the heap.
// We'll use the sign bit to distinguish singleton values from pointers. If it's
// set, it's a pointer.
//
// v--Pointer or singleton?
// S[NaN ]1-----0--------------------------------------------
//
// For singleton values, we just to enumerate the different values. We'll use
// the low three bits of the mantissa for that, and only need a couple:
//
// 3 Type bits--v
// 0[NaN ]1------0----------------------------------------[T]
//
// For pointers, we are left with 48 bits of mantissa to store an address.
// That's more than enough room for a 32-bit address. Even 64-bit machines
// only actually use 48 bits for addresses, so we've got plenty. We just stuff
// the address right into the mantissa.
//
// Ta-da, double precision numbers, pointers, and a bunch of singleton values,
// all stuffed into a single 64-bit sequence. Even better, we don't have to
// do any masking or work to extract number values: they are unmodified. This
// means math on numbers is fast.
#if WREN_NAN_TAGGING
// A mask that selects the sign bit.
#define SIGN_BIT ((uint64_t)1 << 63)
// The bits that must be set to indicate a quiet NaN.
#define QNAN ((uint64_t)0x7ffc000000000000)
// If the NaN bits are set, it's not a number.
#define IS_NUM(value) (((value).bits & QNAN) != QNAN)
// Singleton values are NaN with the sign bit cleared. (This includes the
// normal value of the actual NaN value used in numeric arithmetic.)
#define IS_SINGLETON(value) (((value).bits & (QNAN | SIGN_BIT)) == QNAN)
// An object pointer is a NaN with a set sign bit.
#define IS_OBJ(value) (((value).bits & (QNAN | SIGN_BIT)) == (QNAN | SIGN_BIT))
#define IS_FALSE(value) ((value).bits == FALSE_VAL.bits)
#define IS_NULL(value) ((value).bits == (QNAN | TAG_NULL))
// Masks out the tag bits used to identify the singleton value.
#define MASK_TAG (7)
// Tag values for the different singleton values.
#define TAG_NAN (0)
#define TAG_NULL (1)
#define TAG_FALSE (2)
#define TAG_TRUE (3)
#define TAG_UNUSED1 (4)
#define TAG_UNUSED2 (5)
#define TAG_UNUSED3 (6)
#define TAG_UNUSED4 (7)
// double -> Value.
#define NUM_VAL(n) ((Value)(double)(n))
// Value -> 0 or 1.
#define AS_BOOL(value) ((value).bits == TRUE_VAL.bits)
// Value -> Obj*.
#define AS_OBJ(value) ((Obj*)((value).bits & ~(SIGN_BIT | QNAN)))
// Singleton values.
#define NULL_VAL ((Value)(uint64_t)(QNAN | TAG_NULL))
#define FALSE_VAL ((Value)(uint64_t)(QNAN | TAG_FALSE))
#define TRUE_VAL ((Value)(uint64_t)(QNAN | TAG_TRUE))
// Gets the singleton type tag for a Value (which must be a singleton).
#define GET_TAG(value) ((int)((value).bits & MASK_TAG))
// Converts a pointer to an Obj to a Value.
#define OBJ_VAL(obj) (wrenObjectToValue((Obj*)(obj)))
#else
// Value -> 0 or 1.
#define AS_BOOL(value) ((value).type == VAL_TRUE)
// Value -> Obj*.
#define AS_OBJ(v) ((v).obj)
// Determines if [value] is a garbage-collected object or not.
#define IS_OBJ(value) ((value).type == VAL_OBJ)
#define IS_FALSE(value) ((value).type == VAL_FALSE)
#define IS_NULL(value) ((value).type == VAL_NULL)
#define IS_NUM(value) ((value).type == VAL_NUM)
// Convert [obj], an `Obj*`, to a [Value].
#define OBJ_VAL(obj) (wrenObjectToValue((Obj*)(obj)))
// double -> Value.
#define NUM_VAL(n) ((Value){ VAL_NUM, n, NULL })
// Singleton values.
#define FALSE_VAL ((Value){ VAL_FALSE, 0.0, NULL })
#define NULL_VAL ((Value){ VAL_NULL, 0.0, NULL })
#define TRUE_VAL ((Value){ VAL_TRUE, 0.0, NULL })
#endif
// Creates a new "raw" class. It has no metaclass or superclass whatsoever.
// This is only used for bootstrapping the initial Object and Class classes,
// which are a little special.
ObjClass* wrenNewSingleClass(WrenVM* vm, int numFields);
// Makes [superclass] the superclass of [subclass], and causes subclass to
// inherit its methods. This should be called before any methods are defined
// on subclass.
void wrenBindSuperclass(WrenVM* vm, ObjClass* subclass, ObjClass* superclass);
// Creates a new class object as well as its associated metaclass.
ObjClass* wrenNewClass(WrenVM* vm, ObjClass* superclass, int numFields);
void wrenBindMethod(WrenVM* vm, ObjClass* classObj, int symbol, Method method);
// Creates a new closure object that invokes [fn]. Allocates room for its
// upvalues, but assumes outside code will populate it.
ObjClosure* wrenNewClosure(WrenVM* vm, ObjFn* fn);
// Creates a new fiber object that will invoke [fn], which can be a function or
// closure.
ObjFiber* wrenNewFiber(WrenVM* vm, Obj* fn);
// TODO: The argument list here is getting a bit gratuitous.
// Creates a new function object with the given code and constants. The new
// function will take over ownership of [bytecode] and [sourceLines]. It will
// copy [constants] into its own array.
ObjFn* wrenNewFunction(WrenVM* vm, Value* constants, int numConstants,
int numUpvalues, u_int8_t* bytecode, int bytecodeLength,
ObjString* debugSourcePath,
const char* debugName, int debugNameLength,
int* sourceLines);
// Creates a new instance of the given [classObj].
Value wrenNewInstance(WrenVM* vm, ObjClass* classObj);
// Creates a new list with [numElements] elements (which are left
// uninitialized.)
ObjList* wrenNewList(WrenVM* vm, int numElements);
// Adds [value] to [list], reallocating and growing its storage if needed.
void wrenListAdd(WrenVM* vm, ObjList* list, Value value);
// Inserts [value] in [list] at [index], shifting down the other elements.
void wrenListInsert(WrenVM* vm, ObjList* list, Value value, int index);
// Removes and returns the item at [index] from [list].
Value wrenListRemoveAt(WrenVM* vm, ObjList* list, int index);
// Creates a new range from [from] to [to].
Value wrenNewRange(WrenVM* vm, double from, double to, bool isInclusive);
// Creates a new string object and copies [text] into it.
Value wrenNewString(WrenVM* vm, const char* text, size_t length);
// Creates a new open upvalue pointing to [value] on the stack.
Upvalue* wrenNewUpvalue(WrenVM* vm, Value* value);
// Releases all memory owned by [obj], including [obj] itself.
void wrenFreeObj(WrenVM* vm, Obj* obj);
// Returns the class of [value].
ObjClass* wrenGetClass(WrenVM* vm, Value value);
// Returns true if [a] and [b] are strictly equal using built-in equality
// semantics. This is identity for object values, and value equality for others.
bool wrenValuesEqual(Value a, Value b);
// TODO: Need to decide if this is for user output of values, or for debug
// tracing.
void wrenPrintValue(Value value);
// TODO: Can these be inlined?
bool wrenIsBool(Value value);
bool wrenIsClosure(Value value);
bool wrenIsFiber(Value value);
bool wrenIsFn(Value value);
bool wrenIsInstance(Value value);
bool wrenIsRange(Value value);
bool wrenIsString(Value value);
inline Value wrenObjectToValue(Obj* obj)
{
#if WREN_NAN_TAGGING
return (Value)(SIGN_BIT | QNAN | (uint64_t)(obj));
#else
Value value;
value.type = VAL_OBJ;
value.obj = obj;
return value;
#endif
}
#endif