ast.h - tomo

(494 lines)
   1 // Logic defining ASTs (abstract syntax trees) to represent code
   2 
   3 #pragma once
   4 
   5 #include <err.h>
   6 #include <gc.h>
   7 #include <stdbool.h>
   8 #include <stdint.h>
   9 
  10 #include "stdlib/datatypes.h"
  11 #include "stdlib/files.h"
  12 #include "stdlib/util.h"
  13 
  14 #define NewAST(_file, _start, _end, ast_tag, ...)                                                                      \
  15     (new (ast_t, .file = _file, .start = _start, .end = _end, .tag = ast_tag, .__data.ast_tag = {__VA_ARGS__}))
  16 #define NewTypeAST(_file, _start, _end, ast_tag, ...)                                                                  \
  17     (new (type_ast_t, .file = _file, .start = _start, .end = _end, .tag = ast_tag, .__data.ast_tag = {__VA_ARGS__}))
  18 #define FakeAST(ast_tag, ...) (new (ast_t, .tag = ast_tag, .__data.ast_tag = {__VA_ARGS__}))
  19 #define WrapAST(ast, ast_tag, ...)                                                                                     \
  20     (new (ast_t, .file = (ast)->file, .start = (ast)->start, .end = (ast)->end, .tag = ast_tag,                        \
  21           .__data.ast_tag = {__VA_ARGS__}))
  22 #define TextAST(ast, _str) WrapAST(ast, TextLiteral, .str = GC_strdup(_str))
  23 #define LiteralCode(code, ...)                                                                                         \
  24     new (ast_t, .tag = InlineCCode,                                                                                    \
  25          .__data.InlineCCode = {.chunks = new (ast_list_t, .ast = FakeAST(TextLiteral, code)), __VA_ARGS__})
  26 #define WrapLiteralCode(_ast, code, ...)                                                                               \
  27     new (ast_t, .tag = InlineCCode, .file = (_ast)->file, .start = (_ast)->start, .end = (_ast)->end,                  \
  28          .__data.InlineCCode = {.chunks = new (ast_list_t, .ast = WrapAST(_ast, TextLiteral, code)), __VA_ARGS__})
  29 #define Match(x, _tag)                                                                                                 \
  30     ((x)->tag == _tag ? &(x)->__data._tag                                                                              \
  31                       : (errx(1, __FILE__ ":%d This was supposed to be a " #_tag "\n", __LINE__), &(x)->__data._tag))
  32 #define DeclareMatch(var, x, _tag) __typeof((x)->__data._tag) *var = Match(x, _tag)
  33 #define BINARY_OPERANDS(ast)                                                                                           \
  34     ({                                                                                                                 \
  35         if (!is_binary_operation(ast)) errx(1, __FILE__ ":%d This is not a binary operation!", __LINE__);              \
  36         (ast)->__data.Plus;                                                                                            \
  37     })
  38 #define UPDATE_OPERANDS(ast)                                                                                           \
  39     ({                                                                                                                 \
  40         if (!is_update_assignment(ast)) errx(1, __FILE__ ":%d This is not an update assignment!", __LINE__);           \
  41         (ast)->__data.PlusUpdate;                                                                                      \
  42     })
  43 
  44 #define REVERSE_LIST(list)                                                                                             \
  45     do {                                                                                                               \
  46         __typeof(list) _prev = NULL;                                                                                   \
  47         __typeof(list) _next = NULL;                                                                                   \
  48         __typeof(list) _current = list;                                                                                \
  49         while (_current != NULL) {                                                                                     \
  50             _next = _current->next;                                                                                    \
  51             _current->next = _prev;                                                                                    \
  52             _prev = _current;                                                                                          \
  53             _current = _next;                                                                                          \
  54         }                                                                                                              \
  55         list = _prev;                                                                                                  \
  56     } while (0)
  57 
  58 struct binding_s;
  59 typedef struct type_ast_s type_ast_t;
  60 typedef struct ast_s ast_t;
  61 typedef struct {
  62     ast_t *lhs, *rhs;
  63 } binary_operands_t;
  64 
  65 typedef struct ast_list_s {
  66     ast_t *ast;
  67     struct ast_list_s *next;
  68 } ast_list_t;
  69 
  70 typedef struct arg_ast_s {
  71     file_t *file;
  72     const char *start, *end;
  73     const char *name, *alias;
  74     Text_t comment;
  75     type_ast_t *type;
  76     ast_t *value;
  77     struct arg_ast_s *next;
  78 } arg_ast_t;
  79 
  80 typedef struct when_clause_s {
  81     ast_t *pattern, *body;
  82     struct when_clause_s *next;
  83 } when_clause_t;
  84 
  85 typedef enum {
  86     UnknownTypeAST,
  87     VarTypeAST,
  88     PointerTypeAST,
  89     ListTypeAST,
  90     TableTypeAST,
  91     FunctionTypeAST,
  92     OptionalTypeAST,
  93     EnumTypeAST,
  94 } type_ast_e;
  95 
  96 typedef struct tag_ast_s {
  97     file_t *file;
  98     const char *start, *end;
  99     const char *name;
 100     arg_ast_t *fields;
 101     struct tag_ast_s *next;
 102     bool secret : 1;
 103 } tag_ast_t;
 104 
 105 struct type_ast_s {
 106     type_ast_e tag;
 107     file_t *file;
 108     const char *start, *end;
 109     union {
 110         struct {
 111         } UnknownTypeAST;
 112         struct {
 113             const char *name;
 114         } VarTypeAST;
 115         struct {
 116             type_ast_t *pointed;
 117             bool is_stack : 1;
 118         } PointerTypeAST;
 119         struct {
 120             type_ast_t *item;
 121         } ListTypeAST;
 122         struct {
 123             type_ast_t *key, *value /* value may be NULL */;
 124             ast_t *default_value;
 125         } TableTypeAST;
 126         struct {
 127             arg_ast_t *args;
 128             type_ast_t *ret;
 129         } FunctionTypeAST;
 130         struct {
 131             type_ast_t *type;
 132         } OptionalTypeAST;
 133         struct {
 134             Text_t name;
 135             tag_ast_t *tags;
 136         } EnumTypeAST;
 137     } __data;
 138 };
 139 
 140 #define BINOP_CASES                                                                                                    \
 141     Power:                                                                                                             \
 142     case Multiply:                                                                                                     \
 143     case Divide:                                                                                                       \
 144     case Mod:                                                                                                          \
 145     case Mod1:                                                                                                         \
 146     case Plus:                                                                                                         \
 147     case Minus:                                                                                                        \
 148     case Concat:                                                                                                       \
 149     case LeftShift:                                                                                                    \
 150     case UnsignedLeftShift:                                                                                            \
 151     case RightShift:                                                                                                   \
 152     case UnsignedRightShift:                                                                                           \
 153     case Equals:                                                                                                       \
 154     case NotEquals:                                                                                                    \
 155     case LessThan:                                                                                                     \
 156     case LessThanOrEquals:                                                                                             \
 157     case GreaterThan:                                                                                                  \
 158     case GreaterThanOrEquals:                                                                                          \
 159     case Compare:                                                                                                      \
 160     case And:                                                                                                          \
 161     case Or:                                                                                                           \
 162     case Xor:                                                                                                          \
 163     case PowerUpdate:                                                                                                  \
 164     case MultiplyUpdate:                                                                                               \
 165     case DivideUpdate:                                                                                                 \
 166     case ModUpdate:                                                                                                    \
 167     case Mod1Update:                                                                                                   \
 168     case PlusUpdate:                                                                                                   \
 169     case MinusUpdate:                                                                                                  \
 170     case ConcatUpdate:                                                                                                 \
 171     case LeftShiftUpdate:                                                                                              \
 172     case UnsignedLeftShiftUpdate:                                                                                      \
 173     case RightShiftUpdate:                                                                                             \
 174     case UnsignedRightShiftUpdate:                                                                                     \
 175     case AndUpdate:                                                                                                    \
 176     case OrUpdate:                                                                                                     \
 177     case XorUpdate
 178 #define UPDATE_CASES                                                                                                   \
 179     PowerUpdate:                                                                                                       \
 180     case MultiplyUpdate:                                                                                               \
 181     case DivideUpdate:                                                                                                 \
 182     case ModUpdate:                                                                                                    \
 183     case Mod1Update:                                                                                                   \
 184     case PlusUpdate:                                                                                                   \
 185     case MinusUpdate:                                                                                                  \
 186     case ConcatUpdate:                                                                                                 \
 187     case LeftShiftUpdate:                                                                                              \
 188     case UnsignedLeftShiftUpdate:                                                                                      \
 189     case RightShiftUpdate:                                                                                             \
 190     case UnsignedRightShiftUpdate:                                                                                     \
 191     case AndUpdate:                                                                                                    \
 192     case OrUpdate:                                                                                                     \
 193     case XorUpdate
 194 
 195 typedef enum {
 196     Unknown = 0,
 197     None,
 198     Bool,
 199     Var,
 200     Int,
 201     Num,
 202     TextLiteral,
 203     TextJoin,
 204     Path,
 205     Declare,
 206     Assign,
 207     Power,
 208     Multiply,
 209     Divide,
 210     Mod,
 211     Mod1,
 212     Plus,
 213     Minus,
 214     Concat,
 215     LeftShift,
 216     UnsignedLeftShift,
 217     RightShift,
 218     UnsignedRightShift,
 219     Equals,
 220     NotEquals,
 221     LessThan,
 222     LessThanOrEquals,
 223     GreaterThan,
 224     GreaterThanOrEquals,
 225     Compare,
 226     And,
 227     Or,
 228     Xor,
 229     PowerUpdate,
 230     MultiplyUpdate,
 231     DivideUpdate,
 232     ModUpdate,
 233     Mod1Update,
 234     PlusUpdate,
 235     MinusUpdate,
 236     ConcatUpdate,
 237     LeftShiftUpdate,
 238     UnsignedLeftShiftUpdate,
 239     RightShiftUpdate,
 240     UnsignedRightShiftUpdate,
 241     AndUpdate,
 242     OrUpdate,
 243     XorUpdate,
 244     Not,
 245     Negative,
 246     HeapAllocate,
 247     StackReference,
 248     Min,
 249     Max,
 250     List,
 251     Table,
 252     TableEntry,
 253     Comprehension,
 254     FunctionDef,
 255     Lambda,
 256     ConvertDef,
 257     FunctionCall,
 258     MethodCall,
 259     Block,
 260     For,
 261     While,
 262     If,
 263     When,
 264     Repeat,
 265     Reduction,
 266     Skip,
 267     Stop,
 268     Pass,
 269     Defer,
 270     Return,
 271     StructDef,
 272     EnumDef,
 273     LangDef,
 274     Index,
 275     FieldAccess,
 276     NonOptional,
 277     DebugLog,
 278     Assert,
 279     Use,
 280     InlineCCode,
 281     ExplicitlyTyped,
 282     Metadata,
 283 } ast_e;
 284 #define NUM_AST_TAGS (ExplicitlyTyped + 1)
 285 
 286 struct ast_s {
 287     ast_e tag;
 288     file_t *file;
 289     const char *start, *end;
 290     union {
 291         struct {
 292         } Unknown;
 293         struct {
 294             struct type_s *type;
 295         } None;
 296         struct {
 297             bool b;
 298         } Bool;
 299         struct {
 300             const char *name;
 301         } Var;
 302         struct {
 303             const char *str;
 304         } Int;
 305         struct {
 306             double n;
 307         } Num;
 308         struct {
 309             Text_t text;
 310         } TextLiteral;
 311         struct {
 312             const char *lang;
 313             ast_list_t *children;
 314             bool colorize : 1;
 315         } TextJoin;
 316         struct {
 317             const char *path;
 318         } Path;
 319         struct {
 320             ast_t *var;
 321             type_ast_t *type;
 322             ast_t *value;
 323             bool top_level : 1;
 324         } Declare;
 325         struct {
 326             ast_list_t *targets, *values;
 327         } Assign;
 328         binary_operands_t Power, Multiply, Divide, Mod, Mod1, Plus, Minus, Concat, LeftShift, UnsignedLeftShift,
 329             RightShift, UnsignedRightShift, Equals, NotEquals, LessThan, LessThanOrEquals, GreaterThan,
 330             GreaterThanOrEquals, Compare, And, Or, Xor, PowerUpdate, MultiplyUpdate, DivideUpdate, ModUpdate,
 331             Mod1Update, PlusUpdate, MinusUpdate, ConcatUpdate, LeftShiftUpdate, UnsignedLeftShiftUpdate,
 332             RightShiftUpdate, UnsignedRightShiftUpdate, AndUpdate, OrUpdate, XorUpdate;
 333         struct {
 334             ast_t *value;
 335         } Not, Negative, HeapAllocate, StackReference;
 336         struct {
 337             ast_t *lhs, *rhs, *key;
 338         } Min, Max;
 339         struct {
 340             ast_list_t *items;
 341         } List;
 342         struct {
 343             ast_t *default_value;
 344             ast_t *fallback;
 345             ast_list_t *entries;
 346         } Table;
 347         struct {
 348             ast_t *key, *value /* value may be NULL */;
 349         } TableEntry;
 350         struct {
 351             ast_list_t *vars;
 352             ast_t *expr, *iter, *filter;
 353         } Comprehension;
 354         struct {
 355             ast_t *name;
 356             arg_ast_t *args;
 357             type_ast_t *ret_type;
 358             ast_t *body;
 359             ast_t *cache;
 360             bool is_inline;
 361         } FunctionDef;
 362         struct {
 363             arg_ast_t *args;
 364             type_ast_t *ret_type;
 365             ast_t *body;
 366             ast_t *cache;
 367             bool is_inline;
 368         } ConvertDef;
 369         struct {
 370             arg_ast_t *args;
 371             type_ast_t *ret_type;
 372             ast_t *body;
 373             int64_t id;
 374         } Lambda;
 375         struct {
 376             ast_t *fn;
 377             arg_ast_t *args;
 378         } FunctionCall;
 379         struct {
 380             const char *name;
 381             ast_t *self;
 382             arg_ast_t *args;
 383         } MethodCall;
 384         struct {
 385             ast_list_t *statements;
 386         } Block;
 387         struct {
 388             ast_list_t *vars;
 389             ast_t *iter, *body, *empty;
 390         } For;
 391         struct {
 392             ast_t *condition, *body;
 393         } While;
 394         struct {
 395             ast_t *body;
 396         } Repeat;
 397         struct {
 398             ast_t *condition, *body, *else_body;
 399         } If;
 400         struct {
 401             ast_t *subject;
 402             when_clause_t *clauses;
 403             ast_t *else_body;
 404         } When;
 405         struct {
 406             ast_t *iter, *key;
 407             ast_e op;
 408         } Reduction;
 409         struct {
 410             const char *target;
 411         } Skip, Stop;
 412         struct {
 413         } Pass;
 414         struct {
 415             ast_t *body;
 416         } Defer;
 417         struct {
 418             ast_t *value;
 419         } Return;
 420         struct {
 421             const char *name;
 422             arg_ast_t *fields;
 423             ast_t *namespace;
 424             bool secret : 1, external : 1, opaque : 1;
 425         } StructDef;
 426         struct {
 427             const char *name;
 428             tag_ast_t *tags;
 429             ast_t *namespace;
 430         } EnumDef;
 431         struct {
 432             const char *name;
 433             ast_t *namespace;
 434         } LangDef;
 435         struct {
 436             ast_t *indexed, *index;
 437         } Index;
 438         struct {
 439             ast_t *fielded;
 440             const char *field;
 441         } FieldAccess;
 442         struct {
 443             ast_t *value;
 444         } NonOptional;
 445         struct {
 446             ast_list_t *values;
 447         } DebugLog;
 448         struct {
 449             ast_t *expr, *message;
 450         } Assert;
 451         struct {
 452             ast_t *var;
 453             const char *path;
 454             enum { USE_LOCAL, USE_PACKAGE, USE_SHARED_OBJECT, USE_HEADER, USE_C_CODE, USE_ASM } what;
 455         } Use;
 456         struct {
 457             ast_list_t *chunks;
 458             struct type_s *type;
 459             type_ast_t *type_ast;
 460         } InlineCCode;
 461         struct {
 462             ast_t *ast;
 463             struct type_s *type;
 464         } ExplicitlyTyped;
 465         struct {
 466             Text_t key, value;
 467         } Metadata;
 468     } __data;
 469 };
 470 
 471 extern const int op_tightness[NUM_AST_TAGS];
 472 
 473 typedef struct {
 474     const char *method_name;
 475     const char *operator;
 476 } binop_info_t;
 477 
 478 extern const binop_info_t binop_info[NUM_AST_TAGS];
 479 
 480 OptionalText_t ast_source(ast_t *ast);
 481 
 482 Text_t ast_to_sexp(ast_t *ast);
 483 const char *ast_to_sexp_str(ast_t *ast);
 484 Text_t type_ast_to_sexp(type_ast_t *ast);
 485 
 486 PUREFUNC bool is_idempotent(ast_t *ast);
 487 void visit_topologically(ast_list_t *ast, Closure_t fn);
 488 CONSTFUNC bool is_update_assignment(ast_t *ast);
 489 CONSTFUNC ast_e binop_tag(ast_e tag);
 490 CONSTFUNC bool is_binary_operation(ast_t *ast);
 491 typedef enum { VISIT_STOP, VISIT_PROCEED } visit_behavior_t;
 492 void ast_visit(ast_t *ast, visit_behavior_t (*visitor)(ast_t *, void *), void *userdata);
 493 void type_ast_visit(ast_t *ast, visit_behavior_t (*visitor)(type_ast_t *, void *), void *userdata);
 494 OptionalText_t ast_metadata(ast_t *ast, const char *key);