code.kerkeslager.com Git - fur/blob - 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 Stack* Stack_construct()
 167 {
 168   Stack* result = malloc(sizeof(Stack));
 169   Stack_initialize(result);
 170   return result;
 171 }
 172
 173 void Stack_destruct(Stack* self)
 174 {
 175   free(self);
 176 }
 177
 178 bool Stack_any(Stack* self)
 179 {
 180   return self->length > 0;
 181 }
 182
 183 void Stack_push(Stack* self, Object item)
 184 {
 185   assert(self->length < 256);
 186   self->items[self->length] = item;
 187   self->length++;
 188 }
 189
 190 Object Stack_pop(Stack* self)
 191 {
 192   assert(self->length > 0);
 193   self->length--;
 194   return self->items[self->length];
 195 }
 196
 197 Object Object_rereference(Object self)
 198 {
 199   switch(self.type)
 200   {
 201     case BOOLEAN:
 202     case CLOSURE:
 203     case INTEGER:
 204     case STRING_LITERAL:
 205     case VOID:
 206       return self;
 207
 208     case STRING_CONCATENATION:
 209       self.instance.string_concatenation->referenceCount++;
 210       return self;
 211
 212     case STRUCTURE:
 213       self.instance.structure->reference_count++;
 214       return self;
 215
 216     default:
 217       assert(false);
 218   }
 219 }
 220
 221 Object Structure_construct(size_t length, const char** symbol_list, Object* value_list)
 222 {
 223   Structure* structure = malloc(sizeof(Structure));
 224   structure->reference_count = 1;
 225   structure->length = length;
 226   structure->symbol_list = malloc(sizeof(const char*) * length);
 227   structure->value_list = malloc(sizeof(Object) * length);
 228
 229   // TODO Don't allow assignment of mutable structures, as this screws up reference counting
 230   for(size_t i = 0; i < length; i++)
 231   {
 232     structure->symbol_list[i] = symbol_list[i];
 233     structure->value_list[i] = Object_rereference(value_list[i]);
 234   }
 235
 236   Object result = { STRUCTURE, (Instance)structure };
 237
 238   return result;
 239 }
 240
 241 Object Structure_get(Object* self, const char* symbol)
 242 {
 243   assert(self->type == STRUCTURE);
 244
 245   for(size_t i = 0; i < self->instance.structure->length; i++)
 246   {
 247     if(self->instance.structure->symbol_list[i] == symbol)
 248     {
 249       return self->instance.structure->value_list[i];
 250     }
 251   }
 252
 253   assert(false);
 254 }
 255
 256 struct EnvironmentNode
 257 {
 258   const char* key;
 259   Object value;
 260   EnvironmentNode* next;
 261 };
 262
 263 struct Environment
 264 {
 265   bool mark;
 266   bool live;
 267
 268   Environment* parent;
 269   EnvironmentNode* root;
 270 };
 271
 272 void Environment_initialize(Environment* self, Environment* parent)
 273 {
 274   self->parent = parent;
 275   self->root = NULL;
 276
 277   // We are currently only ever initializing environments at the beginning of running functions, so
 278   // for now at least we can assume that we want it to be live immediately.
 279   self->live = true;
 280 }
 281
 282 void Object_deinitialize(Object* self)
 283 {
 284   switch(self->type)
 285   {
 286     case BOOLEAN:
 287       break;
 288     case CLOSURE:
 289       break;
 290     case INTEGER:
 291       break;
 292     case STRING_LITERAL:
 293       break;
 294     case VOID:
 295       break;
 296
 297     case LIST:
 298       for(size_t i = 0; i < self->instance.list.length; i++) {
 299         Object_deinitialize(&(self->instance.list.items[i]));
 300       }
 301
 302       free(self->instance.list.items);
 303       break;
 304
 305     case STRING_CONCATENATION:
 306       self->instance.string_concatenation->referenceCount--;
 307
 308       if(self->instance.string_concatenation->referenceCount == 0)
 309       {
 310         Object_deinitialize(&(self->instance.string_concatenation->left));
 311         Object_deinitialize(&(self->instance.string_concatenation->right));
 312         free(self->instance.string_concatenation);
 313       }
 314       break;
 315
 316     case STRUCTURE:
 317       self->instance.structure->reference_count--;
 318
 319       if(self->instance.structure->reference_count == 0)
 320       {
 321         for(size_t i = 0; i < self->instance.structure->length; i++)
 322         {
 323           Object_deinitialize(&(self->instance.structure->value_list[i]));
 324         }
 325         free(self->instance.structure->symbol_list);
 326         free(self->instance.structure->value_list);
 327         free(self->instance.structure);
 328       }
 329       break;
 330
 331     default:
 332       assert(false);
 333   }
 334 }
 335
 336 typedef uint32_t StackSnapshot;
 337
 338 StackSnapshot Stack_takeSnapshot(Stack* self)
 339 {
 340   return (StackSnapshot) self->length;
 341 }
 342
 343 void Stack_rewind(Stack* self, StackSnapshot snapshot)
 344 {
 345   while(self->length > snapshot)
 346   {
 347     Object item = Stack_pop(self);
 348     Object_deinitialize(&item);
 349   }
 350 }
 351
 352 void Environment_deinitialize(Environment* self)
 353 {
 354   EnvironmentNode* next;
 355   for(EnvironmentNode* node = self->root; node != NULL; node = next)
 356   {
 357     next = node->next;
 358     Object_deinitialize(&(node->value));
 359     free(node);
 360   }
 361 }
 362
 363 void Environment_setLive(Environment* self, bool live)
 364 {
 365   self->live = live;
 366 }
 367
 368 void Environment_mark(Environment* self)
 369 {
 370   if(self == NULL) return;
 371   if(self->mark) return; // Prevents infinite recursion in the case of cycles
 372
 373   self->mark = true;
 374
 375   Environment_mark(self->parent);
 376
 377   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
 378   {
 379     switch(node->value.type)
 380     {
 381       case BOOLEAN:
 382       case INTEGER:
 383       case STRING_LITERAL:
 384       case VOID:
 385         break;
 386
 387       case CLOSURE:
 388         Environment_mark(node->value.instance.closure.closed);
 389         break;
 390
 391       default:
 392         assert(false);
 393     }
 394   }
 395 }
 396
 397 // This need not be thread safe because environments exist on one thread only
 398 void Environment_set(Environment* self, const char* const key, Object value)
 399 {
 400   EnvironmentNode* node = malloc(sizeof(EnvironmentNode));
 401   node->key = key;
 402   node->value = value;
 403   node->next = self->root;
 404   self->root = node;
 405 }
 406
 407 Object Environment_get(Environment* self, const char* const symbol)
 408 {
 409   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
 410   {
 411     // We can compare pointers because pointers are unique in the SYMBOL_LIST
 412     if(node->key == symbol)
 413     {
 414       return node->value;
 415     }
 416   }
 417
 418   if(self->parent != NULL)
 419   {
 420     return Environment_get(self->parent, symbol);
 421   }
 422
 423   // TODO Handle symbol errors
 424   assert(false);
 425 }
 426
 427 # define POOL_SIZE 64
 428 struct EnvironmentPool
 429 {
 430   int8_t freeIndex;
 431   bool allocatedFlags[POOL_SIZE];
 432   Environment environments[POOL_SIZE];
 433   EnvironmentPool* overflow;
 434 };
 435
 436 EnvironmentPool* EnvironmentPool_construct();
 437 void EnvironmentPool_initialize(EnvironmentPool*);
 438 void EnvironmentPool_deinitialize(EnvironmentPool*);
 439 void EnvironmentPool_destruct(EnvironmentPool*);
 440
 441 EnvironmentPool* EnvironmentPool_construct()
 442 {
 443   EnvironmentPool* result = malloc(sizeof(EnvironmentPool));
 444   EnvironmentPool_initialize(result);
 445   return result;
 446 }
 447
 448 void EnvironmentPool_initialize(EnvironmentPool* self)
 449 {
 450   self->overflow = NULL;
 451   self->freeIndex = 0;
 452
 453   for(size_t i = 0; i < POOL_SIZE; i++)
 454   {
 455     self->allocatedFlags[i] = false;
 456     self->environments[i].live = false;
 457   }
 458 }
 459
 460 void EnvironmentPool_deinitialize(EnvironmentPool* self)
 461 {
 462   // We can assume if this is being called, none of the Environments are live
 463   for(int8_t i = 0; i < POOL_SIZE; i++)
 464   {
 465     if(self->allocatedFlags[i]) Environment_deinitialize(&(self->environments[i]));
 466   }
 467
 468   EnvironmentPool_destruct(self->overflow);
 469 }
 470
 471 void EnvironmentPool_destruct(EnvironmentPool* self)
 472 {
 473   if(self == NULL) return;
 474   EnvironmentPool_deinitialize(self);
 475   free(self);
 476 }
 477
 478 void EnvironmentPool_GC(EnvironmentPool* self)
 479 {
 480   // Unmark all the environments
 481   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 482   {
 483     for(int8_t i = 0; i < POOL_SIZE; i++)
 484     {
 485       current->environments[i].mark = false;
 486     }
 487   }
 488
 489   // Mark live enviroments and environments referenced by live environments
 490   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 491   {
 492     for(int8_t i = 0; i < POOL_SIZE; i++)
 493     {
 494       if(current->environments[i].live)
 495       {
 496         Environment_mark(&(current->environments[i]));
 497       }
 498     }
 499   }
 500
 501   // TODO We never free pools until the very end--we could free a pool if two pools are empty
 502   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 503   {
 504     for(int8_t i = POOL_SIZE - 1; i >= 0; i--)
 505     {
 506       if(!current->environments[i].mark && current->allocatedFlags[i])
 507       {
 508         Environment_deinitialize(&(current->environments[i]));
 509         current->allocatedFlags[i] = false;
 510         current->freeIndex = i;
 511       }
 512     }
 513   }
 514 }
 515
 516 Environment* EnvironmentPool_allocate(EnvironmentPool* self)
 517 {
 518   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 519   {
 520     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
 521     {
 522       if(!current->allocatedFlags[current->freeIndex])
 523       {
 524         current->allocatedFlags[current->freeIndex] = true;
 525         return &(current->environments[current->freeIndex]);
 526       }
 527     }
 528   }
 529
 530   EnvironmentPool_GC(self);
 531
 532   EnvironmentPool* previous;
 533   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 534   {
 535     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
 536     {
 537       if(!current->allocatedFlags[current->freeIndex])
 538       {
 539         current->allocatedFlags[current->freeIndex] = true;
 540         return &(current->environments[current->freeIndex]);
 541       }
 542       else
 543       {
 544         previous = current;
 545       }
 546     }
 547   }
 548
 549   previous->overflow = EnvironmentPool_construct();
 550   return EnvironmentPool_allocate(previous->overflow);
 551 }
 552
 553 Environment* Environment_construct(EnvironmentPool* environmentPool, Environment* parent)
 554 {
 555   Environment* environment = EnvironmentPool_allocate(environmentPool);
 556   Environment_initialize(environment, parent);
 557   return environment;
 558 }
 559
 560 Object integerLiteral(int32_t literal)
 561 {
 562   Object result;
 563   result.type = INTEGER;
 564   result.instance.integer = literal;
 565   return result;
 566 }
 567
 568 Object stringLiteral(const char* literal)
 569 {
 570   Object result;
 571   result.type = STRING_LITERAL;
 572   result.instance.string_literal = literal;
 573   return result;
 574 }
 575
 576 // TODO Make this conditionally added
 577 Object operator$negate(Object input)
 578 {
 579   assert(input.type == INTEGER);
 580
 581   Object result;
 582   result.type = INTEGER;
 583   result.instance.integer = -input.instance.integer;
 584   return result;
 585 }
 586
 587 // TODO Make this conditionally added
 588 Object operator$concatenate(Stack* stack, jmp_buf parentJump, size_t line)
 589 {
 590   Object right = Stack_pop(stack);
 591   Object left = Stack_pop(stack);
 592
 593   switch(left.type) {
 594     case STRING_CONCATENATION:
 595     case STRING_LITERAL:
 596       break;
 597
 598     default:
 599       assert(false);
 600   }
 601
 602   switch(right.type) {
 603     case STRING_CONCATENATION:
 604     case STRING_LITERAL:
 605       break;
 606
 607     default:
 608       assert(false);
 609   }
 610
 611   StringConcatenation* concatenation = malloc(sizeof(StringConcatenation));
 612   concatenation->referenceCount = 1;
 613   concatenation->left = Object_rereference(left);
 614   concatenation->right = Object_rereference(right);
 615
 616   Object result = { STRING_CONCATENATION, (Instance)concatenation };
 617   return result;
 618 }
 619
 620 {% for id in infix_declarations %}
 621 Object operator${{ id.name }}(Stack* stack, jmp_buf parentJump, size_t line)
 622 {
 623   Object right = Stack_pop(stack);
 624   Object left = Stack_pop(stack);
 625
 626   assert(left.type == {{ id.in_type.upper() }});
 627   assert(right.type == {{ id.in_type.upper() }});
 628
 629   {% if id.name == 'integerDivide' or id.name == 'modularDivide' %}
 630   if(right.instance.integer == 0)
 631   {
 632     fprintf(stderr, "DivisionByZeroError on line %zu\n", line);
 633     longjmp(parentJump, 1);
 634   }
 635   {% endif %}
 636
 637   Object result;
 638   result.type = {{ id.out_type.upper() }};
 639   result.instance.{{ id.out_type.lower() }} = left.instance.{{ id.in_type.lower() }} {{ id.operator }} right.instance.{{ id.in_type.lower() }};
 640   return result;
 641 }
 642 {% endfor %}
 643
 644 {% if 'pow' in builtins %}
 645 Object builtin$pow$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Stack* stack, jmp_buf parentJump)
 646 {
 647   // Must unload items in reverse order
 648   Object exponent = Stack_pop(stack);
 649   Object base = Stack_pop(stack);
 650
 651   assert(base.type == INTEGER);
 652   assert(exponent.type == INTEGER);
 653
 654   Object result;
 655   result.type = INTEGER;
 656   result.instance.integer = pow(base.instance.integer, exponent.instance.integer);
 657   return result;
 658 }
 659
 660 Object builtin$pow = { CLOSURE, (Instance)(Closure){ NULL, builtin$pow$implementation } };
 661 {% endif %}
 662
 663 {% if 'print' in builtins %}
 664 Object builtin$print$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Stack* stack, jmp_buf parentJump)
 665 {
 666   Stack reverse_stack;
 667   Stack_initialize(&reverse_stack);
 668
 669   for(size_t i = 0; i < argc; i++)
 670   {
 671     Stack_push(&reverse_stack, Stack_pop(stack));
 672   }
 673
 674   while(reverse_stack.length > 0)
 675   {
 676     Object output = Stack_pop(&reverse_stack);
 677     switch(output.type)
 678     {
 679       case BOOLEAN:
 680         fputs(output.instance.boolean ? "true" : "false", stdout);
 681         break;
 682
 683       case CLOSURE:
 684         // TODO Print something better
 685         printf("<Closure>");
 686         break;
 687
 688       case INTEGER:
 689         printf("%" PRId32, output.instance.integer);
 690         break;
 691
 692       case STRING_CONCATENATION:
 693         Stack_push(stack, output.instance.string_concatenation->left);
 694         builtin$print$implementation(NULL, NULL, 1, stack, parentJump);
 695         Stack_push(stack, output.instance.string_concatenation->right);
 696         builtin$print$implementation(NULL, NULL, 1, stack, parentJump);
 697         break;
 698
 699       case STRING_LITERAL:
 700         // Using fwrite instead of printf to handle size_t length
 701         printf("%s", output.instance.string_literal);
 702         break;
 703
 704       case VOID:
 705         printf("nil");
 706         break;
 707
 708       default:
 709         assert(false);
 710     }
 711     Object_deinitialize(&output);
 712   }
 713
 714   // TODO Return something better
 715   return builtin$false;
 716 }
 717
 718 Object builtin$print = { CLOSURE, (Instance)(Closure){ NULL, builtin$print$implementation } };
 719 {% endif %}
 720 {% for function_definition in function_definition_list %}
 721 {{ function_definition }}
 722 {% endfor %}
 723
 724 int main(int argc, char** argv)
 725 {
 726   EnvironmentPool* environmentPool = EnvironmentPool_construct();
 727   Environment* environment = EnvironmentPool_allocate(environmentPool);
 728   Environment_initialize(environment, NULL);
 729
 730   Stack stackMemory;
 731   Stack* stack = &stackMemory;
 732   Stack_initialize(stack);
 733
 734   jmp_buf jump;
 735   if(setjmp(jump) != 0)
 736   {
 737     fprintf(stderr, "\tin __main__\n");
 738
 739     while(Stack_any(stack))
 740     {
 741       Object item = Stack_pop(stack);
 742       Object_deinitialize(&item);
 743     }
 744     Environment_setLive(environment, false);
 745     EnvironmentPool_destruct(environmentPool);
 746
 747     // TODO We would like to return something nonzero here, but that messes up Valgrind so we couldn't catch memory leaks
 748     return 0;
 749   }
 750
 751   // TODO Use the symbol from SYMBOL_LIST
 752   {% for builtin in builtins %}
 753   Environment_set(environment, "{{ builtin }}", builtin${{ builtin }});
 754   {% endfor %}
 755
 756   {% for statement in statements %}
 757   {{ statement }}
 758   {% endfor %}
 759
 760   Environment_setLive(environment, false);
 761   EnvironmentPool_destruct(environmentPool);
 762   return 0;
 763 }