08921b1807d3d38d06648f7d8391eb9c1b51f754
[fur] / templates / program.c
1 #include <assert.h>
2 #include <inttypes.h>
3 #include <setjmp.h>
4 #include <stdbool.h>
5 #include <stdlib.h>
6 #include <string.h>
7
8 /* Some terminology used in function names:
9  * - initialize: These functions take a pointer and potentially some other arguments, and use those
10  *   to initialize the value pointed to by self. Initialize functions DO NOT allocate the function,
11  *   so they can be used to initialize stack-allocated variables.
12  * - construct: This allocates a value for a pointer, initializes it, and returns it. This is for
13  *   heap-allocated values. It may be as simple as allocating the memory, calling an initialize, and
14  *   returning it.
15  * - deinitialize: These functions dereference or free any objects pointed to by the self pointer's
16  *   value, but they don't actually free the self pointer. This is useful for stack-allocated objects
17  *   which point to heap-allocated objects.
18  * - destruct: This dereferences or frees memory pointed to by the self argument, and all the
19  *   pointers on the self argument.
20  */
21
22 {% for standard_library in standard_libraries %}
23 #include <{{standard_library}}>
24 {% endfor %}
25
26 enum Type;
27 typedef enum Type Type;
28 union Instance;
29 typedef union Instance Instance;
30 struct Object;
31 typedef struct Object Object;
32 struct EnvironmentNode;
33 typedef struct EnvironmentNode EnvironmentNode;
34 struct Environment;
35 typedef struct Environment Environment;
36 struct EnvironmentPool;
37 typedef struct EnvironmentPool EnvironmentPool;
38 struct Stack;
39 typedef struct Stack Stack;
40
41 const char* const STRING_LITERAL_LIST[] = {
42 {% for string_literal in string_literal_list %}
43   "{{ string_literal }}",
44 {% endfor %}
45 };
46
47 const char* const SYMBOL_LIST[] = {
48 {% for symbol in symbol_list %}
49   "{{ symbol }}",
50 {% endfor %}
51 };
52
53 enum Type
54 {
55   BOOLEAN,
56   CLOSURE,
57   INTEGER,
58   LIST,
59   STRING_CONCATENATION,
60   STRING_LITERAL,
61   STRUCTURE,
62   VOID
63 };
64
65 struct Closure;
66 typedef struct Closure Closure;
67 struct Closure
68 {
69   Environment* closed;
70   Object (*call)(EnvironmentPool*, Environment*, size_t, Stack*, jmp_buf);
71 };
72
73 struct List;
74 typedef struct List List;
75 struct List
76 {
77   size_t allocated;
78   size_t length;
79   Object* items;
80 };
81
82 struct StringConcatenation;
83 typedef struct StringConcatenation StringConcatenation;
84
85 struct Structure;
86 typedef struct Structure Structure;
87 struct Structure
88 {
89   size_t reference_count;
90   size_t length;
91   const char** symbol_list;
92   Object* value_list;
93 };
94
95 union Instance
96 {
97   bool boolean;
98   Closure closure;
99   int32_t integer;
100   List list;
101   StringConcatenation* string_concatenation;
102   const char* string_literal;
103   Structure* structure;
104 };
105
106 struct Object
107 {
108   Type type;
109   Instance instance;
110 };
111
112 const Object builtin$true = { BOOLEAN, (Instance)(bool){ true } };
113 const Object builtin$false = { BOOLEAN, (Instance)(bool){ false } };
114 const Object builtin$nil = { VOID, { 0 } };
115
116 struct StringConcatenation
117 {
118   size_t referenceCount;
119   Object left;
120   Object right;
121 };
122
123 Object List_construct(size_t allocate)
124 {
125   Object* items = malloc(sizeof(Object) * allocate);
126   Object result = { LIST, (Instance)(List){ allocate, 0, items } };
127   return result;
128 }
129
130 void List_append(Object* list, Object item)
131 {
132   assert(list->type == LIST);
133
134   if(list->instance.list.allocated == list->instance.list.length)
135   {
136     list->instance.list.allocated *= 2;
137     list->instance.list.items = realloc(
138       list->instance.list.items,
139       sizeof(Object) * list->instance.list.allocated
140     );
141   }
142
143   list->instance.list.items[list->instance.list.length] = item;
144   list->instance.list.length++;
145 }
146
147 Object List_get(Object* list, Object index)
148 {
149   assert(list->type == LIST);
150   assert(index.type == INTEGER);
151
152   return list->instance.list.items[index.instance.integer];
153 }
154
155 struct Stack
156 {
157   uint16_t length;
158   Object items[256];
159 };
160
161 void Stack_initialize(Stack* self)
162 {
163   self->length = 0;
164 }
165
166 void Stack_push(Stack* self, Object item)
167 {
168   assert(self->length < 256);
169   self->items[self->length] = item;
170   self->length++;
171 }
172
173 Object Stack_pop(Stack* self)
174 {
175   assert(self->length > 0);
176   self->length--;
177   return self->items[self->length];
178 }
179
180 Object Object_rereference(Object self)
181 {
182   switch(self.type)
183   {
184     case BOOLEAN:
185     case CLOSURE:
186     case INTEGER:
187     case STRING_LITERAL:
188     case VOID:
189       return self;
190
191     case STRING_CONCATENATION:
192       self.instance.string_concatenation->referenceCount++;
193       return self;
194
195     case STRUCTURE:
196       self.instance.structure->reference_count++;
197       return self;
198
199     default:
200       assert(false);
201   }
202 }
203
204 Object Structure_construct(size_t length, const char** symbol_list, Object* value_list)
205 {
206   Structure* structure = malloc(sizeof(Structure));
207   structure->reference_count = 1;
208   structure->length = length;
209   structure->symbol_list = malloc(sizeof(const char*) * length);
210   structure->value_list = malloc(sizeof(Object) * length);
211
212   // TODO Don't allow assignment of mutable structures, as this screws up reference counting
213   for(size_t i = 0; i < length; i++)
214   {
215     structure->symbol_list[i] = symbol_list[i];
216     structure->value_list[i] = Object_rereference(value_list[i]);
217   }
218
219   Object result = { STRUCTURE, (Instance)structure };
220
221   return result;
222 }
223
224 Object Structure_get(Object* self, const char* symbol)
225 {
226   assert(self->type == STRUCTURE);
227
228   for(size_t i = 0; i < self->instance.structure->length; i++)
229   {
230     if(self->instance.structure->symbol_list[i] == symbol)
231     {
232       return self->instance.structure->value_list[i];
233     }
234   }
235
236   assert(false);
237 }
238
239 struct EnvironmentNode
240 {
241   const char* key;
242   Object value;
243   EnvironmentNode* next;
244 };
245
246 struct Environment
247 {
248   bool mark;
249   bool live;
250
251   Environment* parent;
252   EnvironmentNode* root;
253 };
254
255 void Environment_initialize(Environment* self, Environment* parent)
256 {
257   self->parent = parent;
258   self->root = NULL;
259
260   // We are currently only ever initializing environments at the beginning of running functions, so
261   // for now at least we can assume that we want it to be live immediately.
262   self->live = true;
263 }
264
265 void Object_deinitialize(Object* self)
266 {
267   switch(self->type)
268   {
269     case BOOLEAN:
270       break;
271     case CLOSURE:
272       break;
273     case INTEGER:
274       break;
275     case STRING_LITERAL:
276       break;
277     case VOID:
278       break;
279
280     case LIST:
281       for(size_t i = 0; i < self->instance.list.length; i++) {
282         Object_deinitialize(&(self->instance.list.items[i]));
283       }
284
285       free(self->instance.list.items);
286       break;
287
288     case STRING_CONCATENATION:
289       self->instance.string_concatenation->referenceCount--;
290
291       if(self->instance.string_concatenation->referenceCount == 0)
292       {
293         Object_deinitialize(&(self->instance.string_concatenation->left));
294         Object_deinitialize(&(self->instance.string_concatenation->right));
295         free(self->instance.string_concatenation);
296       }
297       break;
298
299     case STRUCTURE:
300       self->instance.structure->reference_count--;
301
302       if(self->instance.structure->reference_count == 0)
303       {
304         for(size_t i = 0; i < self->instance.structure->length; i++)
305         {
306           Object_deinitialize(&(self->instance.structure->value_list[i]));
307         }
308         free(self->instance.structure->symbol_list);
309         free(self->instance.structure->value_list);
310         free(self->instance.structure);
311       }
312       break;
313
314     default:
315       assert(false);
316   }
317 }
318
319 void Environment_deinitialize(Environment* self)
320 {
321   EnvironmentNode* next;
322   for(EnvironmentNode* node = self->root; node != NULL; node = next)
323   {
324     next = node->next;
325     Object_deinitialize(&(node->value));
326     free(node);
327   }
328 }
329
330 void Environment_setLive(Environment* self, bool live)
331 {
332   self->live = live;
333 }
334
335 void Environment_mark(Environment* self)
336 {
337   if(self == NULL) return;
338   if(self->mark) return; // Prevents infinite recursion in the case of cycles
339
340   self->mark = true;
341
342   Environment_mark(self->parent);
343
344   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
345   {
346     switch(node->value.type)
347     {
348       case BOOLEAN:
349       case INTEGER:
350       case STRING_LITERAL:
351       case VOID:
352         break;
353
354       case CLOSURE:
355         Environment_mark(node->value.instance.closure.closed);
356         break;
357
358       default:
359         assert(false);
360     }
361   }
362 }
363
364 // This need not be thread safe because environments exist on one thread only
365 void Environment_set(Environment* self, const char* const key, Object value)
366 {
367   EnvironmentNode* node = malloc(sizeof(EnvironmentNode));
368   node->key = key;
369   node->value = value;
370   node->next = self->root;
371   self->root = node;
372 }
373
374 Object Environment_get(Environment* self, const char* const symbol)
375 {
376   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
377   {
378     // We can compare pointers because pointers are unique in the SYMBOL_LIST
379     if(node->key == symbol)
380     {
381       return node->value;
382     }
383   }
384
385   if(self->parent != NULL)
386   {
387     return Environment_get(self->parent, symbol);
388   }
389
390   // TODO Handle symbol errors
391   assert(false);
392 }
393
394 # define POOL_SIZE 64
395 struct EnvironmentPool
396 {
397   int8_t freeIndex;
398   bool allocatedFlags[POOL_SIZE];
399   Environment environments[POOL_SIZE];
400   EnvironmentPool* overflow;
401 };
402
403 EnvironmentPool* EnvironmentPool_construct();
404 void EnvironmentPool_initialize(EnvironmentPool*);
405 void EnvironmentPool_deinitialize(EnvironmentPool*);
406 void EnvironmentPool_destruct(EnvironmentPool*);
407
408 EnvironmentPool* EnvironmentPool_construct()
409 {
410   EnvironmentPool* result = malloc(sizeof(EnvironmentPool));
411   EnvironmentPool_initialize(result);
412   return result;
413 }
414
415 void EnvironmentPool_initialize(EnvironmentPool* self)
416 {
417   self->overflow = NULL;
418   self->freeIndex = 0;
419
420   for(size_t i = 0; i < POOL_SIZE; i++)
421   {
422     self->allocatedFlags[i] = false;
423     self->environments[i].live = false;
424   }
425 }
426
427 void EnvironmentPool_deinitialize(EnvironmentPool* self)
428 {
429   // We can assume if this is being called, none of the Environments are live
430   for(int8_t i = 0; i < POOL_SIZE; i++)
431   {
432     if(self->allocatedFlags[i]) Environment_deinitialize(&(self->environments[i]));
433   }
434
435   EnvironmentPool_destruct(self->overflow);
436 }
437
438 void EnvironmentPool_destruct(EnvironmentPool* self)
439 {
440   if(self == NULL) return;
441   EnvironmentPool_deinitialize(self);
442   free(self);
443 }
444
445 void EnvironmentPool_GC(EnvironmentPool* self)
446 {
447   // Unmark all the environments
448   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
449   {
450     for(int8_t i = 0; i < POOL_SIZE; i++)
451     {
452       current->environments[i].mark = false;
453     }
454   }
455
456   // Mark live enviroments and environments referenced by live environments
457   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
458   {
459     for(int8_t i = 0; i < POOL_SIZE; i++)
460     {
461       if(current->environments[i].live)
462       {
463         Environment_mark(&(current->environments[i]));
464       }
465     }
466   }
467
468   // TODO We never free pools until the very end--we could free a pool if two pools are empty
469   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
470   {
471     for(int8_t i = POOL_SIZE - 1; i >= 0; i--)
472     {
473       if(!current->environments[i].mark && current->allocatedFlags[i])
474       {
475         Environment_deinitialize(&(current->environments[i]));
476         current->allocatedFlags[i] = false;
477         current->freeIndex = i;
478       }
479     }
480   }
481 }
482
483 Environment* EnvironmentPool_allocate(EnvironmentPool* self)
484 {
485   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
486   {
487     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
488     {
489       if(!current->allocatedFlags[current->freeIndex])
490       {
491         current->allocatedFlags[current->freeIndex] = true;
492         return &(current->environments[current->freeIndex]);
493       }
494     }
495   }
496
497   EnvironmentPool_GC(self);
498
499   EnvironmentPool* previous;
500   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
501   {
502     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
503     {
504       if(!current->allocatedFlags[current->freeIndex])
505       {
506         current->allocatedFlags[current->freeIndex] = true;
507         return &(current->environments[current->freeIndex]);
508       }
509       else
510       {
511         previous = current;
512       }
513     }
514   }
515
516   previous->overflow = EnvironmentPool_construct();
517   return EnvironmentPool_allocate(previous->overflow);
518 }
519
520 Object integerLiteral(int32_t literal)
521 {
522   Object result;
523   result.type = INTEGER;
524   result.instance.integer = literal;
525   return result;
526 }
527
528 Object stringLiteral(const char* literal)
529 {
530   Object result;
531   result.type = STRING_LITERAL;
532   result.instance.string_literal = literal;
533   return result;
534 }
535
536 // TODO Make this conditionally added
537 Object operator$negate(Object input)
538 {
539   assert(input.type == INTEGER);
540
541   Object result;
542   result.type = INTEGER;
543   result.instance.integer = -input.instance.integer;
544   return result;
545 }
546
547 // TODO Make this conditionally added
548 Object operator$concatenate(Stack* stack, jmp_buf parent_jump, size_t line)
549 {
550   Object right = Stack_pop(stack);
551   Object left = Stack_pop(stack);
552
553   switch(left.type) {
554     case STRING_CONCATENATION:
555     case STRING_LITERAL:
556       break;
557
558     default:
559       assert(false);
560   }
561
562   switch(right.type) {
563     case STRING_CONCATENATION:
564     case STRING_LITERAL:
565       break;
566
567     default:
568       assert(false);
569   }
570
571   StringConcatenation* concatenation = malloc(sizeof(StringConcatenation));
572   concatenation->referenceCount = 1;
573   concatenation->left = Object_rereference(left);
574   concatenation->right = Object_rereference(right);
575
576   Object result = { STRING_CONCATENATION, (Instance)concatenation };
577   return result;
578 }
579
580 {% for id in infix_declarations %}
581 Object operator${{ id.name }}(Stack* stack, jmp_buf parent_jump, size_t line)
582 {
583   Object right = Stack_pop(stack);
584   Object left = Stack_pop(stack);
585
586   assert(left.type == {{ id.in_type.upper() }});
587   assert(right.type == {{ id.in_type.upper() }});
588
589   {% if id.name == 'integerDivide' or id.name == 'modularDivide' %}
590   if(right.instance.integer == 0)
591   {
592     fprintf(stderr, "DivisionByZeroError on line %zu\n", line);
593     longjmp(parent_jump, 1);
594   }
595   {% endif %}
596
597   Object result;
598   result.type = {{ id.out_type.upper() }};
599   result.instance.{{ id.out_type.lower() }} = left.instance.{{ id.in_type.lower() }} {{ id.operator }} right.instance.{{ id.in_type.lower() }};
600   return result;
601 }
602 {% endfor %}
603
604 {% if 'pow' in builtins %}
605 Object builtin$pow$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Stack* stack, jmp_buf parent_jump)
606 {
607   // Must unload items in reverse order
608   Object exponent = Stack_pop(stack);
609   Object base = Stack_pop(stack);
610
611   assert(base.type == INTEGER);
612   assert(exponent.type == INTEGER);
613
614   Object result;
615   result.type = INTEGER;
616   result.instance.integer = pow(base.instance.integer, exponent.instance.integer);
617   return result;
618 }
619
620 Object builtin$pow = { CLOSURE, (Instance)(Closure){ NULL, builtin$pow$implementation } };
621 {% endif %}
622
623 {% if 'print' in builtins %}
624 Object builtin$print$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Stack* stack, jmp_buf parent_jump)
625 {
626   Stack reverse_stack;
627   Stack_initialize(&reverse_stack);
628
629   for(size_t i = 0; i < argc; i++)
630   {
631     Stack_push(&reverse_stack, Stack_pop(stack));
632   }
633
634   while(reverse_stack.length > 0)
635   {
636     Object output = Stack_pop(&reverse_stack);
637     switch(output.type)
638     {
639       case BOOLEAN:
640         fputs(output.instance.boolean ? "true" : "false", stdout);
641         break;
642
643       case CLOSURE:
644         // TODO Print something better
645         printf("<Closure>");
646         break;
647
648       case INTEGER:
649         printf("%" PRId32, output.instance.integer);
650         break;
651
652       case STRING_CONCATENATION:
653         Stack_push(stack, output.instance.string_concatenation->left);
654         builtin$print$implementation(NULL, NULL, 1, stack, parent_jump);
655         Stack_push(stack, output.instance.string_concatenation->right);
656         builtin$print$implementation(NULL, NULL, 1, stack, parent_jump);
657         break;
658
659       case STRING_LITERAL:
660         // Using fwrite instead of printf to handle size_t length
661         printf("%s", output.instance.string_literal);
662         break;
663
664       case VOID:
665         printf("nil");
666         break;
667
668       default:
669         assert(false);
670     }
671     Object_deinitialize(&output);
672   }
673
674   // TODO Return something better
675   return builtin$false;
676 }
677
678 Object builtin$print = { CLOSURE, (Instance)(Closure){ NULL, builtin$print$implementation } };
679 {% endif %}
680 {% for function_definition in function_definition_list %}
681 {{ function_definition }}
682 {% endfor %}
683
684 int main(int argc, char** argv)
685 {
686   EnvironmentPool* environmentPool = EnvironmentPool_construct();
687   Environment* environment = EnvironmentPool_allocate(environmentPool);
688   Environment_initialize(environment, NULL);
689
690   Stack stackMemory;
691   Stack* stack = &stackMemory;
692   Stack_initialize(stack);
693
694   jmp_buf jump;
695   if(setjmp(jump) != 0)
696   {
697     fprintf(stderr, "\tin __main__\n");
698     Environment_setLive(environment, false);
699     EnvironmentPool_destruct(environmentPool);
700
701     // TODO We would like to return something nonzero here, but that messes up Valgrind so we couldn't catch memory leaks
702     return 0;
703   }
704
705   // TODO Use the symbol from SYMBOL_LIST
706   {% for builtin in builtins %}
707   Environment_set(environment, "{{ builtin }}", builtin${{ builtin }});
708   {% endfor %}
709
710   {% for statement in statements %}
711   {{ statement }}
712   {% endfor %}
713
714   Environment_setLive(environment, false);
715   EnvironmentPool_destruct(environmentPool);
716   return 0;
717 }