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