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