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 void Environment_deinitialize(Environment* self)
 337 {
 338   EnvironmentNode* next;
 339   for(EnvironmentNode* node = self->root; node != NULL; node = next)
 340   {
 341     next = node->next;
 342     Object_deinitialize(&(node->value));
 343     free(node);
 344   }
 345 }
 346
 347 void Environment_setLive(Environment* self, bool live)
 348 {
 349   self->live = live;
 350 }
 351
 352 void Environment_mark(Environment* self)
 353 {
 354   if(self == NULL) return;
 355   if(self->mark) return; // Prevents infinite recursion in the case of cycles
 356
 357   self->mark = true;
 358
 359   Environment_mark(self->parent);
 360
 361   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
 362   {
 363     switch(node->value.type)
 364     {
 365       case BOOLEAN:
 366       case INTEGER:
 367       case STRING_LITERAL:
 368       case VOID:
 369         break;
 370
 371       case CLOSURE:
 372         Environment_mark(node->value.instance.closure.closed);
 373         break;
 374
 375       default:
 376         assert(false);
 377     }
 378   }
 379 }
 380
 381 // This need not be thread safe because environments exist on one thread only
 382 void Environment_set(Environment* self, const char* const key, Object value)
 383 {
 384   EnvironmentNode* node = malloc(sizeof(EnvironmentNode));
 385   node->key = key;
 386   node->value = value;
 387   node->next = self->root;
 388   self->root = node;
 389 }
 390
 391 Object Environment_get(Environment* self, const char* const symbol)
 392 {
 393   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
 394   {
 395     // We can compare pointers because pointers are unique in the SYMBOL_LIST
 396     if(node->key == symbol)
 397     {
 398       return node->value;
 399     }
 400   }
 401
 402   if(self->parent != NULL)
 403   {
 404     return Environment_get(self->parent, symbol);
 405   }
 406
 407   // TODO Handle symbol errors
 408   assert(false);
 409 }
 410
 411 # define POOL_SIZE 64
 412 struct EnvironmentPool
 413 {
 414   int8_t freeIndex;
 415   bool allocatedFlags[POOL_SIZE];
 416   Environment environments[POOL_SIZE];
 417   EnvironmentPool* overflow;
 418 };
 419
 420 EnvironmentPool* EnvironmentPool_construct();
 421 void EnvironmentPool_initialize(EnvironmentPool*);
 422 void EnvironmentPool_deinitialize(EnvironmentPool*);
 423 void EnvironmentPool_destruct(EnvironmentPool*);
 424
 425 EnvironmentPool* EnvironmentPool_construct()
 426 {
 427   EnvironmentPool* result = malloc(sizeof(EnvironmentPool));
 428   EnvironmentPool_initialize(result);
 429   return result;
 430 }
 431
 432 void EnvironmentPool_initialize(EnvironmentPool* self)
 433 {
 434   self->overflow = NULL;
 435   self->freeIndex = 0;
 436
 437   for(size_t i = 0; i < POOL_SIZE; i++)
 438   {
 439     self->allocatedFlags[i] = false;
 440     self->environments[i].live = false;
 441   }
 442 }
 443
 444 void EnvironmentPool_deinitialize(EnvironmentPool* self)
 445 {
 446   // We can assume if this is being called, none of the Environments are live
 447   for(int8_t i = 0; i < POOL_SIZE; i++)
 448   {
 449     if(self->allocatedFlags[i]) Environment_deinitialize(&(self->environments[i]));
 450   }
 451
 452   EnvironmentPool_destruct(self->overflow);
 453 }
 454
 455 void EnvironmentPool_destruct(EnvironmentPool* self)
 456 {
 457   if(self == NULL) return;
 458   EnvironmentPool_deinitialize(self);
 459   free(self);
 460 }
 461
 462 void EnvironmentPool_GC(EnvironmentPool* self)
 463 {
 464   // Unmark all the environments
 465   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 466   {
 467     for(int8_t i = 0; i < POOL_SIZE; i++)
 468     {
 469       current->environments[i].mark = false;
 470     }
 471   }
 472
 473   // Mark live enviroments and environments referenced by live environments
 474   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 475   {
 476     for(int8_t i = 0; i < POOL_SIZE; i++)
 477     {
 478       if(current->environments[i].live)
 479       {
 480         Environment_mark(&(current->environments[i]));
 481       }
 482     }
 483   }
 484
 485   // TODO We never free pools until the very end--we could free a pool if two pools are empty
 486   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 487   {
 488     for(int8_t i = POOL_SIZE - 1; i >= 0; i--)
 489     {
 490       if(!current->environments[i].mark && current->allocatedFlags[i])
 491       {
 492         Environment_deinitialize(&(current->environments[i]));
 493         current->allocatedFlags[i] = false;
 494         current->freeIndex = i;
 495       }
 496     }
 497   }
 498 }
 499
 500 Environment* EnvironmentPool_allocate(EnvironmentPool* self)
 501 {
 502   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 503   {
 504     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
 505     {
 506       if(!current->allocatedFlags[current->freeIndex])
 507       {
 508         current->allocatedFlags[current->freeIndex] = true;
 509         return &(current->environments[current->freeIndex]);
 510       }
 511     }
 512   }
 513
 514   EnvironmentPool_GC(self);
 515
 516   EnvironmentPool* previous;
 517   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 518   {
 519     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
 520     {
 521       if(!current->allocatedFlags[current->freeIndex])
 522       {
 523         current->allocatedFlags[current->freeIndex] = true;
 524         return &(current->environments[current->freeIndex]);
 525       }
 526       else
 527       {
 528         previous = current;
 529       }
 530     }
 531   }
 532
 533   previous->overflow = EnvironmentPool_construct();
 534   return EnvironmentPool_allocate(previous->overflow);
 535 }
 536
 537 Environment* Environment_construct(EnvironmentPool* environmentPool, Environment* parent)
 538 {
 539   Environment* environment = EnvironmentPool_allocate(environmentPool);
 540   Environment_initialize(environment, parent);
 541   return environment;
 542 }
 543
 544 Object integerLiteral(int32_t literal)
 545 {
 546   Object result;
 547   result.type = INTEGER;
 548   result.instance.integer = literal;
 549   return result;
 550 }
 551
 552 Object stringLiteral(const char* literal)
 553 {
 554   Object result;
 555   result.type = STRING_LITERAL;
 556   result.instance.string_literal = literal;
 557   return result;
 558 }
 559
 560 // TODO Make this conditionally added
 561 Object operator$negate(Object input)
 562 {
 563   assert(input.type == INTEGER);
 564
 565   Object result;
 566   result.type = INTEGER;
 567   result.instance.integer = -input.instance.integer;
 568   return result;
 569 }
 570
 571 // TODO Make this conditionally added
 572 Object operator$concatenate(Stack* stack, jmp_buf parentJump, size_t line)
 573 {
 574   Object right = Stack_pop(stack);
 575   Object left = Stack_pop(stack);
 576
 577   switch(left.type) {
 578     case STRING_CONCATENATION:
 579     case STRING_LITERAL:
 580       break;
 581
 582     default:
 583       assert(false);
 584   }
 585
 586   switch(right.type) {
 587     case STRING_CONCATENATION:
 588     case STRING_LITERAL:
 589       break;
 590
 591     default:
 592       assert(false);
 593   }
 594
 595   StringConcatenation* concatenation = malloc(sizeof(StringConcatenation));
 596   concatenation->referenceCount = 1;
 597   concatenation->left = Object_rereference(left);
 598   concatenation->right = Object_rereference(right);
 599
 600   Object result = { STRING_CONCATENATION, (Instance)concatenation };
 601   return result;
 602 }
 603
 604 {% for id in infix_declarations %}
 605 Object operator${{ id.name }}(Stack* stack, jmp_buf parentJump, size_t line)
 606 {
 607   Object right = Stack_pop(stack);
 608   Object left = Stack_pop(stack);
 609
 610   assert(left.type == {{ id.in_type.upper() }});
 611   assert(right.type == {{ id.in_type.upper() }});
 612
 613   {% if id.name == 'integerDivide' or id.name == 'modularDivide' %}
 614   if(right.instance.integer == 0)
 615   {
 616     fprintf(stderr, "DivisionByZeroError on line %zu\n", line);
 617     longjmp(parentJump, 1);
 618   }
 619   {% endif %}
 620
 621   Object result;
 622   result.type = {{ id.out_type.upper() }};
 623   result.instance.{{ id.out_type.lower() }} = left.instance.{{ id.in_type.lower() }} {{ id.operator }} right.instance.{{ id.in_type.lower() }};
 624   return result;
 625 }
 626 {% endfor %}
 627
 628 {% if 'pow' in builtins %}
 629 Object builtin$pow$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Stack* stack, jmp_buf parentJump)
 630 {
 631   // Must unload items in reverse order
 632   Object exponent = Stack_pop(stack);
 633   Object base = Stack_pop(stack);
 634
 635   assert(base.type == INTEGER);
 636   assert(exponent.type == INTEGER);
 637
 638   Object result;
 639   result.type = INTEGER;
 640   result.instance.integer = pow(base.instance.integer, exponent.instance.integer);
 641   return result;
 642 }
 643
 644 Object builtin$pow = { CLOSURE, (Instance)(Closure){ NULL, builtin$pow$implementation } };
 645 {% endif %}
 646
 647 {% if 'print' in builtins %}
 648 Object builtin$print$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Stack* stack, jmp_buf parentJump)
 649 {
 650   Stack reverse_stack;
 651   Stack_initialize(&reverse_stack);
 652
 653   for(size_t i = 0; i < argc; i++)
 654   {
 655     Stack_push(&reverse_stack, Stack_pop(stack));
 656   }
 657
 658   while(reverse_stack.length > 0)
 659   {
 660     Object output = Stack_pop(&reverse_stack);
 661     switch(output.type)
 662     {
 663       case BOOLEAN:
 664         fputs(output.instance.boolean ? "true" : "false", stdout);
 665         break;
 666
 667       case CLOSURE:
 668         // TODO Print something better
 669         printf("<Closure>");
 670         break;
 671
 672       case INTEGER:
 673         printf("%" PRId32, output.instance.integer);
 674         break;
 675
 676       case STRING_CONCATENATION:
 677         Stack_push(stack, output.instance.string_concatenation->left);
 678         builtin$print$implementation(NULL, NULL, 1, stack, parentJump);
 679         Stack_push(stack, output.instance.string_concatenation->right);
 680         builtin$print$implementation(NULL, NULL, 1, stack, parentJump);
 681         break;
 682
 683       case STRING_LITERAL:
 684         // Using fwrite instead of printf to handle size_t length
 685         printf("%s", output.instance.string_literal);
 686         break;
 687
 688       case VOID:
 689         printf("nil");
 690         break;
 691
 692       default:
 693         assert(false);
 694     }
 695     Object_deinitialize(&output);
 696   }
 697
 698   // TODO Return something better
 699   return builtin$false;
 700 }
 701
 702 Object builtin$print = { CLOSURE, (Instance)(Closure){ NULL, builtin$print$implementation } };
 703 {% endif %}
 704 {% for function_definition in function_definition_list %}
 705 {{ function_definition }}
 706 {% endfor %}
 707
 708 int main(int argc, char** argv)
 709 {
 710   EnvironmentPool* environmentPool = EnvironmentPool_construct();
 711   Environment* environment = EnvironmentPool_allocate(environmentPool);
 712   Environment_initialize(environment, NULL);
 713
 714   Stack stackMemory;
 715   Stack* stack = &stackMemory;
 716   Stack_initialize(stack);
 717
 718   jmp_buf jump;
 719   if(setjmp(jump) != 0)
 720   {
 721     fprintf(stderr, "\tin __main__\n");
 722
 723     while(Stack_any(stack))
 724     {
 725       Object item = Stack_pop(stack);
 726       Object_deinitialize(&item);
 727     }
 728     Environment_setLive(environment, false);
 729     EnvironmentPool_destruct(environmentPool);
 730
 731     // TODO We would like to return something nonzero here, but that messes up Valgrind so we couldn't catch memory leaks
 732     return 0;
 733   }
 734
 735   // TODO Use the symbol from SYMBOL_LIST
 736   {% for builtin in builtins %}
 737   Environment_set(environment, "{{ builtin }}", builtin${{ builtin }});
 738   {% endfor %}
 739
 740   {% for statement in statements %}
 741   {{ statement }}
 742   {% endfor %}
 743
 744   Environment_setLive(environment, false);
 745   EnvironmentPool_destruct(environmentPool);
 746   return 0;
 747 }