code.kerkeslager.com Git - fur/blob - templates/program.c

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