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 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)
 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)
 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\n");
 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 }