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