1#include <math.h>
2#include <stdarg.h>
3#include <stdio.h>
4#include <string.h>
5
6#include "wren.h"
7#include "wren_value.h"
8#include "wren_vm.h"
9
10#if WREN_DEBUG_TRACE_MEMORY
11 #include "wren_debug.h"
12#endif
13
14// TODO: Tune these.
15// The initial (and minimum) capacity of a non-empty list or map object.
16#define MIN_CAPACITY 16
17
18// The rate at which a collection's capacity grows when the size exceeds the
19// current capacity. The new capacity will be determined by *multiplying* the
20// old capacity by this. Growing geometrically is necessary to ensure that
21// adding to a collection has O(1) amortized complexity.
22#define GROW_FACTOR 2
23
24// The maximum percentage of map entries that can be filled before the map is
25// grown. A lower load takes more memory but reduces collisions which makes
26// lookup faster.
27#define MAP_LOAD_PERCENT 75
28
29// The number of call frames initially allocated when a fiber is created. Making
30// this smaller makes fibers use less memory (at first) but spends more time
31// reallocating when the call stack grows.
32#define INITIAL_CALL_FRAMES 4
33
34DEFINE_BUFFER(Value, Value);
35DEFINE_BUFFER(Method, Method);
36
37static void initObj(WrenVM* vm, Obj* obj, ObjType type, ObjClass* classObj)
38{
39 obj->type = type;
40 obj->isDark = false;
41 obj->classObj = classObj;
42 obj->next = vm->first;
43 vm->first = obj;
44}
45
46ObjClass* wrenNewSingleClass(WrenVM* vm, int numFields, ObjString* name)
47{
48 ObjClass* classObj = ALLOCATE(vm, ObjClass);
49 initObj(vm, &classObj->obj, OBJ_CLASS, NULL);
50 classObj->superclass = NULL;
51 classObj->numFields = numFields;
52 classObj->name = name;
53 classObj->attributes = NULL_VAL;
54
55 wrenPushRoot(vm, (Obj*)classObj);
56 wrenMethodBufferInit(&classObj->methods);
57 wrenPopRoot(vm);
58
59 return classObj;
60}
61
62void wrenBindSuperclass(WrenVM* vm, ObjClass* subclass, ObjClass* superclass)
63{
64 ASSERT(superclass != NULL, "Must have superclass.");
65
66 subclass->superclass = superclass;
67
68 // Include the superclass in the total number of fields.
69 if (subclass->numFields != -1)
70 {
71 subclass->numFields += superclass->numFields;
72 }
73 else
74 {
75 ASSERT(superclass->numFields == 0,
76 "A foreign class cannot inherit from a class with fields.");
77 }
78
79 // Inherit methods from its superclass.
80 for (int i = 0; i < superclass->methods.count; i++)
81 {
82 wrenBindMethod(vm, subclass, i, superclass->methods.data[i]);
83 }
84}
85
86ObjClass* wrenNewClass(WrenVM* vm, ObjClass* superclass, int numFields,
87 ObjString* name)
88{
89 // Create the metaclass.
90 Value metaclassName = wrenStringFormat(vm, "@ metaclass", OBJ_VAL(name));
91 wrenPushRoot(vm, AS_OBJ(metaclassName));
92
93 ObjClass* metaclass = wrenNewSingleClass(vm, 0, AS_STRING(metaclassName));
94 metaclass->obj.classObj = vm->classClass;
95
96 wrenPopRoot(vm);
97
98 // Make sure the metaclass isn't collected when we allocate the class.
99 wrenPushRoot(vm, (Obj*)metaclass);
100
101 // Metaclasses always inherit Class and do not parallel the non-metaclass
102 // hierarchy.
103 wrenBindSuperclass(vm, metaclass, vm->classClass);
104
105 ObjClass* classObj = wrenNewSingleClass(vm, numFields, name);
106
107 // Make sure the class isn't collected while the inherited methods are being
108 // bound.
109 wrenPushRoot(vm, (Obj*)classObj);
110
111 classObj->obj.classObj = metaclass;
112 wrenBindSuperclass(vm, classObj, superclass);
113
114 wrenPopRoot(vm);
115 wrenPopRoot(vm);
116
117 return classObj;
118}
119
120void wrenBindMethod(WrenVM* vm, ObjClass* classObj, int symbol, Method method)
121{
122 // Make sure the buffer is big enough to contain the symbol's index.
123 if (symbol >= classObj->methods.count)
124 {
125 Method noMethod;
126 noMethod.type = METHOD_NONE;
127 wrenMethodBufferFill(vm, &classObj->methods, noMethod,
128 symbol - classObj->methods.count + 1);
129 }
130
131 classObj->methods.data[symbol] = method;
132}
133
134ObjClosure* wrenNewClosure(WrenVM* vm, ObjFn* fn)
135{
136 ObjClosure* closure = ALLOCATE_FLEX(vm, ObjClosure,
137 ObjUpvalue*, fn->numUpvalues);
138 initObj(vm, &closure->obj, OBJ_CLOSURE, vm->fnClass);
139
140 closure->fn = fn;
141
142 // Clear the upvalue array. We need to do this in case a GC is triggered
143 // after the closure is created but before the upvalue array is populated.
144 for (int i = 0; i < fn->numUpvalues; i++) closure->upvalues[i] = NULL;
145
146 return closure;
147}
148
149ObjFiber* wrenNewFiber(WrenVM* vm, ObjClosure* closure)
150{
151 // Allocate the arrays before the fiber in case it triggers a GC.
152 CallFrame* frames = ALLOCATE_ARRAY(vm, CallFrame, INITIAL_CALL_FRAMES);
153
154 // Add one slot for the unused implicit receiver slot that the compiler
155 // assumes all functions have.
156 int stackCapacity = closure == NULL
157 ? 1
158 : wrenPowerOf2Ceil(closure->fn->maxSlots + 1);
159 Value* stack = ALLOCATE_ARRAY(vm, Value, stackCapacity);
160
161 ObjFiber* fiber = ALLOCATE(vm, ObjFiber);
162 initObj(vm, &fiber->obj, OBJ_FIBER, vm->fiberClass);
163
164 fiber->stack = stack;
165 fiber->stackTop = fiber->stack;
166 fiber->stackCapacity = stackCapacity;
167
168 fiber->frames = frames;
169 fiber->frameCapacity = INITIAL_CALL_FRAMES;
170 fiber->numFrames = 0;
171
172 fiber->openUpvalues = NULL;
173 fiber->caller = NULL;
174 fiber->error = NULL_VAL;
175 fiber->state = FIBER_OTHER;
176
177 if (closure != NULL)
178 {
179 // Initialize the first call frame.
180 wrenAppendCallFrame(vm, fiber, closure, fiber->stack);
181
182 // The first slot always holds the closure.
183 fiber->stackTop[0] = OBJ_VAL(closure);
184 fiber->stackTop++;
185 }
186
187 return fiber;
188}
189
190void wrenEnsureStack(WrenVM* vm, ObjFiber* fiber, int needed)
191{
192 if (fiber->stackCapacity >= needed) return;
193
194 int capacity = wrenPowerOf2Ceil(needed);
195
196 Value* oldStack = fiber->stack;
197 fiber->stack = (Value*)wrenReallocate(vm, fiber->stack,
198 sizeof(Value) * fiber->stackCapacity,
199 sizeof(Value) * capacity);
200 fiber->stackCapacity = capacity;
201
202 // If the reallocation moves the stack, then we need to recalculate every
203 // pointer that points into the old stack to into the same relative distance
204 // in the new stack. We have to be a little careful about how these are
205 // calculated because pointer subtraction is only well-defined within a
206 // single array, hence the slightly redundant-looking arithmetic below.
207 if (fiber->stack != oldStack)
208 {
209 // Top of the stack.
210 if (vm->apiStack >= oldStack && vm->apiStack <= fiber->stackTop)
211 {
212 vm->apiStack = fiber->stack + (vm->apiStack - oldStack);
213 }
214
215 // Stack pointer for each call frame.
216 for (int i = 0; i < fiber->numFrames; i++)
217 {
218 CallFrame* frame = &fiber->frames[i];
219 frame->stackStart = fiber->stack + (frame->stackStart - oldStack);
220 }
221
222 // Open upvalues.
223 for (ObjUpvalue* upvalue = fiber->openUpvalues;
224 upvalue != NULL;
225 upvalue = upvalue->next)
226 {
227 upvalue->value = fiber->stack + (upvalue->value - oldStack);
228 }
229
230 fiber->stackTop = fiber->stack + (fiber->stackTop - oldStack);
231 }
232}
233
234ObjForeign* wrenNewForeign(WrenVM* vm, ObjClass* classObj, size_t size)
235{
236 ObjForeign* object = ALLOCATE_FLEX(vm, ObjForeign, uint8_t, size);
237 initObj(vm, &object->obj, OBJ_FOREIGN, classObj);
238
239 // Zero out the bytes.
240 memset(object->data, 0, size);
241 return object;
242}
243
244ObjFn* wrenNewFunction(WrenVM* vm, ObjModule* module, int maxSlots)
245{
246 FnDebug* debug = ALLOCATE(vm, FnDebug);
247 debug->name = NULL;
248 wrenIntBufferInit(&debug->sourceLines);
249
250 ObjFn* fn = ALLOCATE(vm, ObjFn);
251 initObj(vm, &fn->obj, OBJ_FN, vm->fnClass);
252
253 wrenValueBufferInit(&fn->constants);
254 wrenByteBufferInit(&fn->code);
255 fn->module = module;
256 fn->maxSlots = maxSlots;
257 fn->numUpvalues = 0;
258 fn->arity = 0;
259 fn->debug = debug;
260
261 return fn;
262}
263
264void wrenFunctionBindName(WrenVM* vm, ObjFn* fn, const char* name, int length)
265{
266 fn->debug->name = ALLOCATE_ARRAY(vm, char, length + 1);
267 memcpy(fn->debug->name, name, length);
268 fn->debug->name[length] = '\0';
269}
270
271Value wrenNewInstance(WrenVM* vm, ObjClass* classObj)
272{
273 ObjInstance* instance = ALLOCATE_FLEX(vm, ObjInstance,
274 Value, classObj->numFields);
275 initObj(vm, &instance->obj, OBJ_INSTANCE, classObj);
276
277 // Initialize fields to null.
278 for (int i = 0; i < classObj->numFields; i++)
279 {
280 instance->fields[i] = NULL_VAL;
281 }
282
283 return OBJ_VAL(instance);
284}
285
286ObjList* wrenNewList(WrenVM* vm, uint32_t numElements)
287{
288 // Allocate this before the list object in case it triggers a GC which would
289 // free the list.
290 Value* elements = NULL;
291 if (numElements > 0)
292 {
293 elements = ALLOCATE_ARRAY(vm, Value, numElements);
294 }
295
296 ObjList* list = ALLOCATE(vm, ObjList);
297 initObj(vm, &list->obj, OBJ_LIST, vm->listClass);
298 list->elements.capacity = numElements;
299 list->elements.count = numElements;
300 list->elements.data = elements;
301 return list;
302}
303
304void wrenListInsert(WrenVM* vm, ObjList* list, Value value, uint32_t index)
305{
306 if (IS_OBJ(value)) wrenPushRoot(vm, AS_OBJ(value));
307
308 // Add a slot at the end of the list.
309 wrenValueBufferWrite(vm, &list->elements, NULL_VAL);
310
311 if (IS_OBJ(value)) wrenPopRoot(vm);
312
313 // Shift the existing elements down.
314 for (uint32_t i = list->elements.count - 1; i > index; i--)
315 {
316 list->elements.data[i] = list->elements.data[i - 1];
317 }
318
319 // Store the new element.
320 list->elements.data[index] = value;
321}
322
323int wrenListIndexOf(WrenVM* vm, ObjList* list, Value value)
324{
325 int count = list->elements.count;
326 for (int i = 0; i < count; i++)
327 {
328 Value item = list->elements.data[i];
329 if(wrenValuesEqual(item, value)) {
330 return i;
331 }
332 }
333 return -1;
334}
335
336Value wrenListRemoveAt(WrenVM* vm, ObjList* list, uint32_t index)
337{
338 Value removed = list->elements.data[index];
339
340 if (IS_OBJ(removed)) wrenPushRoot(vm, AS_OBJ(removed));
341
342 // Shift items up.
343 for (int i = index; i < list->elements.count - 1; i++)
344 {
345 list->elements.data[i] = list->elements.data[i + 1];
346 }
347
348 // If we have too much excess capacity, shrink it.
349 if (list->elements.capacity / GROW_FACTOR >= list->elements.count)
350 {
351 list->elements.data = (Value*)wrenReallocate(vm, list->elements.data,
352 sizeof(Value) * list->elements.capacity,
353 sizeof(Value) * (list->elements.capacity / GROW_FACTOR));
354 list->elements.capacity /= GROW_FACTOR;
355 }
356
357 if (IS_OBJ(removed)) wrenPopRoot(vm);
358
359 list->elements.count--;
360 return removed;
361}
362
363ObjMap* wrenNewMap(WrenVM* vm)
364{
365 ObjMap* map = ALLOCATE(vm, ObjMap);
366 initObj(vm, &map->obj, OBJ_MAP, vm->mapClass);
367 map->capacity = 0;
368 map->count = 0;
369 map->entries = NULL;
370 return map;
371}
372
373static inline uint32_t hashBits(uint64_t hash)
374{
375 // From v8's ComputeLongHash() which in turn cites:
376 // Thomas Wang, Integer Hash Functions.
377 // http://www.concentric.net/~Ttwang/tech/inthash.htm
378 hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1;
379 hash = hash ^ (hash >> 31);
380 hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4);
381 hash = hash ^ (hash >> 11);
382 hash = hash + (hash << 6);
383 hash = hash ^ (hash >> 22);
384 return (uint32_t)(hash & 0x3fffffff);
385}
386
387// Generates a hash code for [num].
388static inline uint32_t hashNumber(double num)
389{
390 // Hash the raw bits of the value.
391 return hashBits(wrenDoubleToBits(num));
392}
393
394// Generates a hash code for [object].
395static uint32_t hashObject(Obj* object)
396{
397 switch (object->type)
398 {
399 case OBJ_CLASS:
400 // Classes just use their name.
401 return hashObject((Obj*)((ObjClass*)object)->name);
402
403 // Allow bare (non-closure) functions so that we can use a map to find
404 // existing constants in a function's constant table. This is only used
405 // internally. Since user code never sees a non-closure function, they
406 // cannot use them as map keys.
407 case OBJ_FN:
408 {
409 ObjFn* fn = (ObjFn*)object;
410 return hashNumber(fn->arity) ^ hashNumber(fn->code.count);
411 }
412
413 case OBJ_RANGE:
414 {
415 ObjRange* range = (ObjRange*)object;
416 return hashNumber(range->from) ^ hashNumber(range->to);
417 }
418
419 case OBJ_STRING:
420 return ((ObjString*)object)->hash;
421
422 default:
423 ASSERT(false, "Only immutable objects can be hashed.");
424 return 0;
425 }
426}
427
428// Generates a hash code for [value], which must be one of the built-in
429// immutable types: null, bool, class, num, range, or string.
430static uint32_t hashValue(Value value)
431{
432 // TODO: We'll probably want to randomize this at some point.
433
434#if WREN_NAN_TAGGING
435 if (IS_OBJ(value)) return hashObject(AS_OBJ(value));
436
437 // Hash the raw bits of the unboxed value.
438 return hashBits(value);
439#else
440 switch (value.type)
441 {
442 case VAL_FALSE: return 0;
443 case VAL_NULL: return 1;
444 case VAL_NUM: return hashNumber(AS_NUM(value));
445 case VAL_TRUE: return 2;
446 case VAL_OBJ: return hashObject(AS_OBJ(value));
447 default: UNREACHABLE();
448 }
449
450 return 0;
451#endif
452}
453
454// Looks for an entry with [key] in an array of [capacity] [entries].
455//
456// If found, sets [result] to point to it and returns `true`. Otherwise,
457// returns `false` and points [result] to the entry where the key/value pair
458// should be inserted.
459static bool findEntry(MapEntry* entries, uint32_t capacity, Value key,
460 MapEntry** result)
461{
462 // If there is no entry array (an empty map), we definitely won't find it.
463 if (capacity == 0) return false;
464
465 // Figure out where to insert it in the table. Use open addressing and
466 // basic linear probing.
467 uint32_t startIndex = hashValue(key) % capacity;
468 uint32_t index = startIndex;
469
470 // If we pass a tombstone and don't end up finding the key, its entry will
471 // be re-used for the insert.
472 MapEntry* tombstone = NULL;
473
474 // Walk the probe sequence until we've tried every slot.
475 do
476 {
477 MapEntry* entry = &entries[index];
478
479 if (IS_UNDEFINED(entry->key))
480 {
481 // If we found an empty slot, the key is not in the table. If we found a
482 // slot that contains a deleted key, we have to keep looking.
483 if (IS_FALSE(entry->value))
484 {
485 // We found an empty slot, so we've reached the end of the probe
486 // sequence without finding the key. If we passed a tombstone, then
487 // that's where we should insert the item, otherwise, put it here at
488 // the end of the sequence.
489 *result = tombstone != NULL ? tombstone : entry;
490 return false;
491 }
492 else
493 {
494 // We found a tombstone. We need to keep looking in case the key is
495 // after it, but we'll use this entry as the insertion point if the
496 // key ends up not being found.
497 if (tombstone == NULL) tombstone = entry;
498 }
499 }
500 else if (wrenValuesEqual(entry->key, key))
501 {
502 // We found the key.
503 *result = entry;
504 return true;
505 }
506
507 // Try the next slot.
508 index = (index + 1) % capacity;
509 }
510 while (index != startIndex);
511
512 // If we get here, the table is full of tombstones. Return the first one we
513 // found.
514 ASSERT(tombstone != NULL, "Map should have tombstones or empty entries.");
515 *result = tombstone;
516 return false;
517}
518
519// Inserts [key] and [value] in the array of [entries] with the given
520// [capacity].
521//
522// Returns `true` if this is the first time [key] was added to the map.
523static bool insertEntry(MapEntry* entries, uint32_t capacity,
524 Value key, Value value)
525{
526 ASSERT(entries != NULL, "Should ensure capacity before inserting.");
527
528 MapEntry* entry;
529 if (findEntry(entries, capacity, key, &entry))
530 {
531 // Already present, so just replace the value.
532 entry->value = value;
533 return false;
534 }
535 else
536 {
537 entry->key = key;
538 entry->value = value;
539 return true;
540 }
541}
542
543// Updates [map]'s entry array to [capacity].
544static void resizeMap(WrenVM* vm, ObjMap* map, uint32_t capacity)
545{
546 // Create the new empty hash table.
547 MapEntry* entries = ALLOCATE_ARRAY(vm, MapEntry, capacity);
548 for (uint32_t i = 0; i < capacity; i++)
549 {
550 entries[i].key = UNDEFINED_VAL;
551 entries[i].value = FALSE_VAL;
552 }
553
554 // Re-add the existing entries.
555 if (map->capacity > 0)
556 {
557 for (uint32_t i = 0; i < map->capacity; i++)
558 {
559 MapEntry* entry = &map->entries[i];
560
561 // Don't copy empty entries or tombstones.
562 if (IS_UNDEFINED(entry->key)) continue;
563
564 insertEntry(entries, capacity, entry->key, entry->value);
565 }
566 }
567
568 // Replace the array.
569 DEALLOCATE(vm, map->entries);
570 map->entries = entries;
571 map->capacity = capacity;
572}
573
574Value wrenMapGet(ObjMap* map, Value key)
575{
576 MapEntry* entry;
577 if (findEntry(map->entries, map->capacity, key, &entry)) return entry->value;
578
579 return UNDEFINED_VAL;
580}
581
582void wrenMapSet(WrenVM* vm, ObjMap* map, Value key, Value value)
583{
584 // If the map is getting too full, make room first.
585 if (map->count + 1 > map->capacity * MAP_LOAD_PERCENT / 100)
586 {
587 // Figure out the new hash table size.
588 uint32_t capacity = map->capacity * GROW_FACTOR;
589 if (capacity < MIN_CAPACITY) capacity = MIN_CAPACITY;
590
591 resizeMap(vm, map, capacity);
592 }
593
594 if (insertEntry(map->entries, map->capacity, key, value))
595 {
596 // A new key was added.
597 map->count++;
598 }
599}
600
601void wrenMapClear(WrenVM* vm, ObjMap* map)
602{
603 DEALLOCATE(vm, map->entries);
604 map->entries = NULL;
605 map->capacity = 0;
606 map->count = 0;
607}
608
609Value wrenMapRemoveKey(WrenVM* vm, ObjMap* map, Value key)
610{
611 MapEntry* entry;
612 if (!findEntry(map->entries, map->capacity, key, &entry)) return NULL_VAL;
613
614 // Remove the entry from the map. Set this value to true, which marks it as a
615 // deleted slot. When searching for a key, we will stop on empty slots, but
616 // continue past deleted slots.
617 Value value = entry->value;
618 entry->key = UNDEFINED_VAL;
619 entry->value = TRUE_VAL;
620
621 if (IS_OBJ(value)) wrenPushRoot(vm, AS_OBJ(value));
622
623 map->count--;
624
625 if (map->count == 0)
626 {
627 // Removed the last item, so free the array.
628 wrenMapClear(vm, map);
629 }
630 else if (map->capacity > MIN_CAPACITY &&
631 map->count < map->capacity / GROW_FACTOR * MAP_LOAD_PERCENT / 100)
632 {
633 uint32_t capacity = map->capacity / GROW_FACTOR;
634 if (capacity < MIN_CAPACITY) capacity = MIN_CAPACITY;
635
636 // The map is getting empty, so shrink the entry array back down.
637 // TODO: Should we do this less aggressively than we grow?
638 resizeMap(vm, map, capacity);
639 }
640
641 if (IS_OBJ(value)) wrenPopRoot(vm);
642 return value;
643}
644
645ObjModule* wrenNewModule(WrenVM* vm, ObjString* name)
646{
647 ObjModule* module = ALLOCATE(vm, ObjModule);
648
649 // Modules are never used as first-class objects, so don't need a class.
650 initObj(vm, (Obj*)module, OBJ_MODULE, NULL);
651
652 wrenPushRoot(vm, (Obj*)module);
653
654 wrenSymbolTableInit(&module->variableNames);
655 wrenValueBufferInit(&module->variables);
656
657 module->name = name;
658
659 wrenPopRoot(vm);
660 return module;
661}
662
663Value wrenNewRange(WrenVM* vm, double from, double to, bool isInclusive)
664{
665 ObjRange* range = ALLOCATE(vm, ObjRange);
666 initObj(vm, &range->obj, OBJ_RANGE, vm->rangeClass);
667 range->from = from;
668 range->to = to;
669 range->isInclusive = isInclusive;
670
671 return OBJ_VAL(range);
672}
673
674// Creates a new string object with a null-terminated buffer large enough to
675// hold a string of [length] but does not fill in the bytes.
676//
677// The caller is expected to fill in the buffer and then calculate the string's
678// hash.
679static ObjString* allocateString(WrenVM* vm, size_t length)
680{
681 ObjString* string = ALLOCATE_FLEX(vm, ObjString, char, length + 1);
682 initObj(vm, &string->obj, OBJ_STRING, vm->stringClass);
683 string->length = (int)length;
684 string->value[length] = '\0';
685
686 return string;
687}
688
689// Calculates and stores the hash code for [string].
690static void hashString(ObjString* string)
691{
692 // FNV-1a hash. See: http://www.isthe.com/chongo/tech/comp/fnv/
693 uint32_t hash = 2166136261u;
694
695 // This is O(n) on the length of the string, but we only call this when a new
696 // string is created. Since the creation is also O(n) (to copy/initialize all
697 // the bytes), we allow this here.
698 for (uint32_t i = 0; i < string->length; i++)
699 {
700 hash ^= string->value[i];
701 hash *= 16777619;
702 }
703
704 string->hash = hash;
705}
706
707Value wrenNewString(WrenVM* vm, const char* text)
708{
709 return wrenNewStringLength(vm, text, strlen(text));
710}
711
712Value wrenNewStringLength(WrenVM* vm, const char* text, size_t length)
713{
714 // Allow NULL if the string is empty since byte buffers don't allocate any
715 // characters for a zero-length string.
716 ASSERT(length == 0 || text != NULL, "Unexpected NULL string.");
717
718 ObjString* string = allocateString(vm, length);
719
720 // Copy the string (if given one).
721 if (length > 0 && text != NULL) memcpy(string->value, text, length);
722
723 hashString(string);
724 return OBJ_VAL(string);
725}
726
727
728Value wrenNewStringFromRange(WrenVM* vm, ObjString* source, int start,
729 uint32_t count, int step)
730{
731 uint8_t* from = (uint8_t*)source->value;
732 int length = 0;
733 for (uint32_t i = 0; i < count; i++)
734 {
735 length += wrenUtf8DecodeNumBytes(from[start + i * step]);
736 }
737
738 ObjString* result = allocateString(vm, length);
739 result->value[length] = '\0';
740
741 uint8_t* to = (uint8_t*)result->value;
742 for (uint32_t i = 0; i < count; i++)
743 {
744 int index = start + i * step;
745 int codePoint = wrenUtf8Decode(from + index, source->length - index);
746
747 if (codePoint != -1)
748 {
749 to += wrenUtf8Encode(codePoint, to);
750 }
751 }
752
753 hashString(result);
754 return OBJ_VAL(result);
755}
756
757Value wrenNumToString(WrenVM* vm, double value)
758{
759 // Edge case: If the value is NaN or infinity, different versions of libc
760 // produce different outputs (some will format it signed and some won't). To
761 // get reliable output, handle it ourselves.
762 if (isnan(value)) return CONST_STRING(vm, "nan");
763 if (isinf(value))
764 {
765 if (value > 0.0)
766 {
767 return CONST_STRING(vm, "infinity");
768 }
769 else
770 {
771 return CONST_STRING(vm, "-infinity");
772 }
773 }
774
775 // This is large enough to hold any double converted to a string using
776 // "%.14g". Example:
777 //
778 // -1.12345678901234e-1022
779 //
780 // So we have:
781 //
782 // + 1 char for sign
783 // + 1 char for digit
784 // + 1 char for "."
785 // + 14 chars for decimal digits
786 // + 1 char for "e"
787 // + 1 char for "-" or "+"
788 // + 4 chars for exponent
789 // + 1 char for "\0"
790 // = 24
791 char buffer[24];
792 int length = sprintf(buffer, "%.14g", value);
793 return wrenNewStringLength(vm, buffer, length);
794}
795
796Value wrenStringFromCodePoint(WrenVM* vm, int value)
797{
798 int length = wrenUtf8EncodeNumBytes(value);
799 ASSERT(length != 0, "Value out of range.");
800
801 ObjString* string = allocateString(vm, length);
802
803 wrenUtf8Encode(value, (uint8_t*)string->value);
804 hashString(string);
805
806 return OBJ_VAL(string);
807}
808
809Value wrenStringFromByte(WrenVM *vm, uint8_t value)
810{
811 int length = 1;
812 ObjString* string = allocateString(vm, length);
813 string->value[0] = value;
814 hashString(string);
815 return OBJ_VAL(string);
816}
817
818Value wrenStringFormat(WrenVM* vm, const char* format, ...)
819{
820 va_list argList;
821
822 // Calculate the length of the result string. Do this up front so we can
823 // create the final string with a single allocation.
824 va_start(argList, format);
825 size_t totalLength = 0;
826 for (const char* c = format; *c != '\0'; c++)
827 {
828 switch (*c)
829 {
830 case '$':
831 totalLength += strlen(va_arg(argList, const char*));
832 break;
833
834 case '@':
835 totalLength += AS_STRING(va_arg(argList, Value))->length;
836 break;
837
838 default:
839 // Any other character is interpreted literally.
840 totalLength++;
841 }
842 }
843 va_end(argList);
844
845 // Concatenate the string.
846 ObjString* result = allocateString(vm, totalLength);
847
848 va_start(argList, format);
849 char* start = result->value;
850 for (const char* c = format; *c != '\0'; c++)
851 {
852 switch (*c)
853 {
854 case '$':
855 {
856 const char* string = va_arg(argList, const char*);
857 size_t length = strlen(string);
858 memcpy(start, string, length);
859 start += length;
860 break;
861 }
862
863 case '@':
864 {
865 ObjString* string = AS_STRING(va_arg(argList, Value));
866 memcpy(start, string->value, string->length);
867 start += string->length;
868 break;
869 }
870
871 default:
872 // Any other character is interpreted literally.
873 *start++ = *c;
874 }
875 }
876 va_end(argList);
877
878 hashString(result);
879
880 return OBJ_VAL(result);
881}
882
883Value wrenStringCodePointAt(WrenVM* vm, ObjString* string, uint32_t index)
884{
885 ASSERT(index < string->length, "Index out of bounds.");
886
887 int codePoint = wrenUtf8Decode((uint8_t*)string->value + index,
888 string->length - index);
889 if (codePoint == -1)
890 {
891 // If it isn't a valid UTF-8 sequence, treat it as a single raw byte.
892 char bytes[2];
893 bytes[0] = string->value[index];
894 bytes[1] = '\0';
895 return wrenNewStringLength(vm, bytes, 1);
896 }
897
898 return wrenStringFromCodePoint(vm, codePoint);
899}
900
901// Uses the Boyer-Moore-Horspool string matching algorithm.
902uint32_t wrenStringFind(ObjString* haystack, ObjString* needle, uint32_t start)
903{
904 // Edge case: An empty needle is always found.
905 if (needle->length == 0) return start;
906
907 // If the needle goes past the haystack it won't be found.
908 if (start + needle->length > haystack->length) return UINT32_MAX;
909
910 // If the startIndex is too far it also won't be found.
911 if (start >= haystack->length) return UINT32_MAX;
912
913 // Pre-calculate the shift table. For each character (8-bit value), we
914 // determine how far the search window can be advanced if that character is
915 // the last character in the haystack where we are searching for the needle
916 // and the needle doesn't match there.
917 uint32_t shift[UINT8_MAX];
918 uint32_t needleEnd = needle->length - 1;
919
920 // By default, we assume the character is not the needle at all. In that case
921 // case, if a match fails on that character, we can advance one whole needle
922 // width since.
923 for (uint32_t index = 0; index < UINT8_MAX; index++)
924 {
925 shift[index] = needle->length;
926 }
927
928 // Then, for every character in the needle, determine how far it is from the
929 // end. If a match fails on that character, we can advance the window such
930 // that it the last character in it lines up with the last place we could
931 // find it in the needle.
932 for (uint32_t index = 0; index < needleEnd; index++)
933 {
934 char c = needle->value[index];
935 shift[(uint8_t)c] = needleEnd - index;
936 }
937
938 // Slide the needle across the haystack, looking for the first match or
939 // stopping if the needle goes off the end.
940 char lastChar = needle->value[needleEnd];
941 uint32_t range = haystack->length - needle->length;
942
943 for (uint32_t index = start; index <= range; )
944 {
945 // Compare the last character in the haystack's window to the last character
946 // in the needle. If it matches, see if the whole needle matches.
947 char c = haystack->value[index + needleEnd];
948 if (lastChar == c &&
949 memcmp(haystack->value + index, needle->value, needleEnd) == 0)
950 {
951 // Found a match.
952 return index;
953 }
954
955 // Otherwise, slide the needle forward.
956 index += shift[(uint8_t)c];
957 }
958
959 // Not found.
960 return UINT32_MAX;
961}
962
963ObjUpvalue* wrenNewUpvalue(WrenVM* vm, Value* value)
964{
965 ObjUpvalue* upvalue = ALLOCATE(vm, ObjUpvalue);
966
967 // Upvalues are never used as first-class objects, so don't need a class.
968 initObj(vm, &upvalue->obj, OBJ_UPVALUE, NULL);
969
970 upvalue->value = value;
971 upvalue->closed = NULL_VAL;
972 upvalue->next = NULL;
973 return upvalue;
974}
975
976void wrenGrayObj(WrenVM* vm, Obj* obj)
977{
978 if (obj == NULL) return;
979
980 // Stop if the object is already darkened so we don't get stuck in a cycle.
981 if (obj->isDark) return;
982
983 // It's been reached.
984 obj->isDark = true;
985
986 // Add it to the gray list so it can be recursively explored for
987 // more marks later.
988 if (vm->grayCount >= vm->grayCapacity)
989 {
990 vm->grayCapacity = vm->grayCount * 2;
991 vm->gray = (Obj**)vm->config.reallocateFn(vm->gray,
992 vm->grayCapacity * sizeof(Obj*),
993 vm->config.userData);
994 }
995
996 vm->gray[vm->grayCount++] = obj;
997}
998
999void wrenGrayValue(WrenVM* vm, Value value)
1000{
1001 if (!IS_OBJ(value)) return;
1002 wrenGrayObj(vm, AS_OBJ(value));
1003}
1004
1005void wrenGrayBuffer(WrenVM* vm, ValueBuffer* buffer)
1006{
1007 for (int i = 0; i < buffer->count; i++)
1008 {
1009 wrenGrayValue(vm, buffer->data[i]);
1010 }
1011}
1012
1013static void blackenClass(WrenVM* vm, ObjClass* classObj)
1014{
1015 // The metaclass.
1016 wrenGrayObj(vm, (Obj*)classObj->obj.classObj);
1017
1018 // The superclass.
1019 wrenGrayObj(vm, (Obj*)classObj->superclass);
1020
1021 // Method function objects.
1022 for (int i = 0; i < classObj->methods.count; i++)
1023 {
1024 if (classObj->methods.data[i].type == METHOD_BLOCK)
1025 {
1026 wrenGrayObj(vm, (Obj*)classObj->methods.data[i].as.closure);
1027 }
1028 }
1029
1030 wrenGrayObj(vm, (Obj*)classObj->name);
1031
1032 if(!IS_NULL(classObj->attributes)) wrenGrayObj(vm, AS_OBJ(classObj->attributes));
1033
1034 // Keep track of how much memory is still in use.
1035 vm->bytesAllocated += sizeof(ObjClass);
1036 vm->bytesAllocated += classObj->methods.capacity * sizeof(Method);
1037}
1038
1039static void blackenClosure(WrenVM* vm, ObjClosure* closure)
1040{
1041 // Mark the function.
1042 wrenGrayObj(vm, (Obj*)closure->fn);
1043
1044 // Mark the upvalues.
1045 for (int i = 0; i < closure->fn->numUpvalues; i++)
1046 {
1047 wrenGrayObj(vm, (Obj*)closure->upvalues[i]);
1048 }
1049
1050 // Keep track of how much memory is still in use.
1051 vm->bytesAllocated += sizeof(ObjClosure);
1052 vm->bytesAllocated += sizeof(ObjUpvalue*) * closure->fn->numUpvalues;
1053}
1054
1055static void blackenFiber(WrenVM* vm, ObjFiber* fiber)
1056{
1057 // Stack functions.
1058 for (int i = 0; i < fiber->numFrames; i++)
1059 {
1060 wrenGrayObj(vm, (Obj*)fiber->frames[i].closure);
1061 }
1062
1063 // Stack variables.
1064 for (Value* slot = fiber->stack; slot < fiber->stackTop; slot++)
1065 {
1066 wrenGrayValue(vm, *slot);
1067 }
1068
1069 // Open upvalues.
1070 ObjUpvalue* upvalue = fiber->openUpvalues;
1071 while (upvalue != NULL)
1072 {
1073 wrenGrayObj(vm, (Obj*)upvalue);
1074 upvalue = upvalue->next;
1075 }
1076
1077 // The caller.
1078 wrenGrayObj(vm, (Obj*)fiber->caller);
1079 wrenGrayValue(vm, fiber->error);
1080
1081 // Keep track of how much memory is still in use.
1082 vm->bytesAllocated += sizeof(ObjFiber);
1083 vm->bytesAllocated += fiber->frameCapacity * sizeof(CallFrame);
1084 vm->bytesAllocated += fiber->stackCapacity * sizeof(Value);
1085}
1086
1087static void blackenFn(WrenVM* vm, ObjFn* fn)
1088{
1089 // Mark the constants.
1090 wrenGrayBuffer(vm, &fn->constants);
1091
1092 // Keep track of how much memory is still in use.
1093 vm->bytesAllocated += sizeof(ObjFn);
1094 vm->bytesAllocated += sizeof(uint8_t) * fn->code.capacity;
1095 vm->bytesAllocated += sizeof(Value) * fn->constants.capacity;
1096
1097 // The debug line number buffer.
1098 vm->bytesAllocated += sizeof(int) * fn->code.capacity;
1099 // TODO: What about the function name?
1100}
1101
1102static void blackenForeign(WrenVM* vm, ObjForeign* foreign)
1103{
1104 // TODO: Keep track of how much memory the foreign object uses. We can store
1105 // this in each foreign object, but it will balloon the size. We may not want
1106 // that much overhead. One option would be to let the foreign class register
1107 // a C function that returns a size for the object. That way the VM doesn't
1108 // always have to explicitly store it.
1109}
1110
1111static void blackenInstance(WrenVM* vm, ObjInstance* instance)
1112{
1113 wrenGrayObj(vm, (Obj*)instance->obj.classObj);
1114
1115 // Mark the fields.
1116 for (int i = 0; i < instance->obj.classObj->numFields; i++)
1117 {
1118 wrenGrayValue(vm, instance->fields[i]);
1119 }
1120
1121 // Keep track of how much memory is still in use.
1122 vm->bytesAllocated += sizeof(ObjInstance);
1123 vm->bytesAllocated += sizeof(Value) * instance->obj.classObj->numFields;
1124}
1125
1126static void blackenList(WrenVM* vm, ObjList* list)
1127{
1128 // Mark the elements.
1129 wrenGrayBuffer(vm, &list->elements);
1130
1131 // Keep track of how much memory is still in use.
1132 vm->bytesAllocated += sizeof(ObjList);
1133 vm->bytesAllocated += sizeof(Value) * list->elements.capacity;
1134}
1135
1136static void blackenMap(WrenVM* vm, ObjMap* map)
1137{
1138 // Mark the entries.
1139 for (uint32_t i = 0; i < map->capacity; i++)
1140 {
1141 MapEntry* entry = &map->entries[i];
1142 if (IS_UNDEFINED(entry->key)) continue;
1143
1144 wrenGrayValue(vm, entry->key);
1145 wrenGrayValue(vm, entry->value);
1146 }
1147
1148 // Keep track of how much memory is still in use.
1149 vm->bytesAllocated += sizeof(ObjMap);
1150 vm->bytesAllocated += sizeof(MapEntry) * map->capacity;
1151}
1152
1153static void blackenModule(WrenVM* vm, ObjModule* module)
1154{
1155 // Top-level variables.
1156 for (int i = 0; i < module->variables.count; i++)
1157 {
1158 wrenGrayValue(vm, module->variables.data[i]);
1159 }
1160
1161 wrenBlackenSymbolTable(vm, &module->variableNames);
1162
1163 wrenGrayObj(vm, (Obj*)module->name);
1164
1165 // Keep track of how much memory is still in use.
1166 vm->bytesAllocated += sizeof(ObjModule);
1167}
1168
1169static void blackenRange(WrenVM* vm, ObjRange* range)
1170{
1171 // Keep track of how much memory is still in use.
1172 vm->bytesAllocated += sizeof(ObjRange);
1173}
1174
1175static void blackenString(WrenVM* vm, ObjString* string)
1176{
1177 // Keep track of how much memory is still in use.
1178 vm->bytesAllocated += sizeof(ObjString) + string->length + 1;
1179}
1180
1181static void blackenUpvalue(WrenVM* vm, ObjUpvalue* upvalue)
1182{
1183 // Mark the closed-over object (in case it is closed).
1184 wrenGrayValue(vm, upvalue->closed);
1185
1186 // Keep track of how much memory is still in use.
1187 vm->bytesAllocated += sizeof(ObjUpvalue);
1188}
1189
1190static void blackenObject(WrenVM* vm, Obj* obj)
1191{
1192#if WREN_DEBUG_TRACE_MEMORY
1193 printf("mark ");
1194 wrenDumpValue(OBJ_VAL(obj));
1195 printf(" @ %p\n", obj);
1196#endif
1197
1198 // Traverse the object's fields.
1199 switch (obj->type)
1200 {
1201 case OBJ_CLASS: blackenClass( vm, (ObjClass*) obj); break;
1202 case OBJ_CLOSURE: blackenClosure( vm, (ObjClosure*) obj); break;
1203 case OBJ_FIBER: blackenFiber( vm, (ObjFiber*) obj); break;
1204 case OBJ_FN: blackenFn( vm, (ObjFn*) obj); break;
1205 case OBJ_FOREIGN: blackenForeign( vm, (ObjForeign*) obj); break;
1206 case OBJ_INSTANCE: blackenInstance(vm, (ObjInstance*)obj); break;
1207 case OBJ_LIST: blackenList( vm, (ObjList*) obj); break;
1208 case OBJ_MAP: blackenMap( vm, (ObjMap*) obj); break;
1209 case OBJ_MODULE: blackenModule( vm, (ObjModule*) obj); break;
1210 case OBJ_RANGE: blackenRange( vm, (ObjRange*) obj); break;
1211 case OBJ_STRING: blackenString( vm, (ObjString*) obj); break;
1212 case OBJ_UPVALUE: blackenUpvalue( vm, (ObjUpvalue*) obj); break;
1213 }
1214}
1215
1216void wrenBlackenObjects(WrenVM* vm)
1217{
1218 while (vm->grayCount > 0)
1219 {
1220 // Pop an item from the gray stack.
1221 Obj* obj = vm->gray[--vm->grayCount];
1222 blackenObject(vm, obj);
1223 }
1224}
1225
1226void wrenFreeObj(WrenVM* vm, Obj* obj)
1227{
1228#if WREN_DEBUG_TRACE_MEMORY
1229 printf("free ");
1230 wrenDumpValue(OBJ_VAL(obj));
1231 printf(" @ %p\n", obj);
1232#endif
1233
1234 switch (obj->type)
1235 {
1236 case OBJ_CLASS:
1237 wrenMethodBufferClear(vm, &((ObjClass*)obj)->methods);
1238 break;
1239
1240 case OBJ_FIBER:
1241 {
1242 ObjFiber* fiber = (ObjFiber*)obj;
1243 DEALLOCATE(vm, fiber->frames);
1244 DEALLOCATE(vm, fiber->stack);
1245 break;
1246 }
1247
1248 case OBJ_FN:
1249 {
1250 ObjFn* fn = (ObjFn*)obj;
1251 wrenValueBufferClear(vm, &fn->constants);
1252 wrenByteBufferClear(vm, &fn->code);
1253 wrenIntBufferClear(vm, &fn->debug->sourceLines);
1254 DEALLOCATE(vm, fn->debug->name);
1255 DEALLOCATE(vm, fn->debug);
1256 break;
1257 }
1258
1259 case OBJ_FOREIGN:
1260 wrenFinalizeForeign(vm, (ObjForeign*)obj);
1261 break;
1262
1263 case OBJ_LIST:
1264 wrenValueBufferClear(vm, &((ObjList*)obj)->elements);
1265 break;
1266
1267 case OBJ_MAP:
1268 DEALLOCATE(vm, ((ObjMap*)obj)->entries);
1269 break;
1270
1271 case OBJ_MODULE:
1272 wrenSymbolTableClear(vm, &((ObjModule*)obj)->variableNames);
1273 wrenValueBufferClear(vm, &((ObjModule*)obj)->variables);
1274 break;
1275
1276 case OBJ_CLOSURE:
1277 case OBJ_INSTANCE:
1278 case OBJ_RANGE:
1279 case OBJ_STRING:
1280 case OBJ_UPVALUE:
1281 break;
1282 }
1283
1284 DEALLOCATE(vm, obj);
1285}
1286
1287ObjClass* wrenGetClass(WrenVM* vm, Value value)
1288{
1289 return wrenGetClassInline(vm, value);
1290}
1291
1292bool wrenValuesEqual(Value a, Value b)
1293{
1294 if (wrenValuesSame(a, b)) return true;
1295
1296 // If we get here, it's only possible for two heap-allocated immutable objects
1297 // to be equal.
1298 if (!IS_OBJ(a) || !IS_OBJ(b)) return false;
1299
1300 Obj* aObj = AS_OBJ(a);
1301 Obj* bObj = AS_OBJ(b);
1302
1303 // Must be the same type.
1304 if (aObj->type != bObj->type) return false;
1305
1306 switch (aObj->type)
1307 {
1308 case OBJ_RANGE:
1309 {
1310 ObjRange* aRange = (ObjRange*)aObj;
1311 ObjRange* bRange = (ObjRange*)bObj;
1312 return aRange->from == bRange->from &&
1313 aRange->to == bRange->to &&
1314 aRange->isInclusive == bRange->isInclusive;
1315 }
1316
1317 case OBJ_STRING:
1318 {
1319 ObjString* aString = (ObjString*)aObj;
1320 ObjString* bString = (ObjString*)bObj;
1321 return aString->hash == bString->hash &&
1322 wrenStringEqualsCString(aString, bString->value, bString->length);
1323 }
1324
1325 default:
1326 // All other types are only equal if they are same, which they aren't if
1327 // we get here.
1328 return false;
1329 }
1330}
1331