path: root/bootstrap/bootstrap.h

/*

  bootstrap.h -- Header file for cross-file calls/types for bootstrap parser

  Copyright © 2020 Samuel Lidén Borell <samuel@kodafritt.se>

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  THE SOFTWARE.

*/
#ifndef LRL_BOOTSTRAP_H
#define LRL_BOOTSTRAP_H

#include <stdio.h>

/* Type for pointer comparison */
#if !defined(__STDC_VERSION__) ||  __STDC_VERSION__ < 199901L
#if defined(_WIN64)
typedef unsigned long long uintptr_t;
#elif defined(__arm__)
typedef unsigned int uintptr_t;
#else
typedef unsigned long uintptr_t;
#endif
typedef int static_assert_uintptr_size1[1+sizeof(uintptr_t)-sizeof(void*)];
typedef int static_assert_uintptr_size2[1+sizeof(void*)-sizeof(uintptr_t)];
#else
#include <stdint.h>
#endif

/* noreturn qualifier for functions */
#if defined(__GNUC__) || defined(__clang__)
#    define NORETURN __attribute__((__noreturn__))
#else
#    define NORETURN
#endif


enum TokenType {
    /* Long tokens */
    Number = 1,
    Identifier,
    GotoTarget,
    String,
    /* Parentheses */
    LParen,
    RParen,
    LSquare,
    RSquare,
    LCurly,
    RCurly,
    /* Operators that allow can be combined with =, like += >= etc */
    /* TODO not equals operator */
    Plus,
    Minus,
    Asterisk,
    Slash,
    Less,
    Assign,
    Greater,
    /* Misc */
    Comma,
    Dot,
    Question,
    Colon,
    Semicolon,
    /* Multi-character operators */
    PlusAssign,
    MinusAssign,
    MultiplyAssign,
    DivideAssign,
    LessEqual,
    Equal,
    GreaterEqual,
    NotEqual,
    /* Keyword operators */
    KW_Not,
    KW_And,
    KW_Or,
    /*  Keywords - Top levels */
    KW_Data,
    KW_Func,
    KW_Type,
    /* Keywords - Elementary types */
    KW_Void,
    KW_Bool,
    KW_USize,
    KW_SSize,
    /*KW_UOffs,*/
    KW_FileOffs,
    KW_Char,
    /* TODO int8 and wuint8? */
    KW_Byte,
    KW_Short,
    KW_UShort,
    KW_WUShort,
    KW_Int,
    KW_UInt,
    KW_WUInt,
    KW_Long,
    KW_ULong,
    KW_WULong,
    KW_Int32,
    KW_UInt32,
    KW_WUInt32,
    /*KW_Int64,
    KW_UInt64,
    KW_WUInt64,*/
    /* Keywords - Other types */
    KW_Ref,
    /*KW_RWRef,
    KW_WORef,*/
    KW_Addr,
    KW_MergedRef,
    KW_NoReturn,
    KW_Struct,
    KW_Enum,
    /* Keywords - Qualifiers */
    KW_Var,
    KW_WriteOnly,
    KW_Own,
    /*KW_RAlias,
    KW_WAlias,
    KW_RWAlias,
    KW_RShared,
    KW_WShared,
    KW_RWShared,*/
    KW_Aliased,
    KW_Threaded,
    /* Keywords - Builtin values */
    KW_None,
    KW_Undef,
    /* Keywords - Control statements */
    KW_If,
    KW_Else,
    KW_While,
    KW_Do,
    KW_For,
    KW_In,
    KW_LoopEnd,
    KW_LoopEmpty,
    KW_Switch,
    KW_Case,
    KW_With,
    KW_Default,
    KW_Assert,
    KW_Break,
    KW_Continue,
    KW_Goto,
    KW_Return
};

#define ASSIGN_2CHAR_DELTA (PlusAssign-Plus)
#define KEYWORD_TO_BUILTIN(keyword) ((keyword)-KW_Void)
#define MAX_KEYWORD_LEN 10 /* TODO */

/** Maximum length of identifiers, strings, etc. */
#define MAX_TOKLEN 4096

struct Token {
    enum TokenType type;
    int line, column;
    int size;
    unsigned int hash;
    char data[MAX_TOKLEN]; /* null terminated */
};

#define D_NESTEDTYPE 0
#define D_TYPEDEF  1
#define D_FUNCDEF  2
#define D_DATADEF  3
#define D_MARKED   D_DATADEF /* temporary flag during typedef translation */

#define T_REF      1
#define T_ARRAY    2
#define T_STRUCT   3
#define T_ENUM     4
#define T_OPTIONAL 5
#define T_IDENT    6
#define T_ELMNTRY  7
#define T_FUNC     8
#define T_BITS     9
/*#define TF_PRIVATE   10
#define T_ANY       11*/ /* maybe TF_PRIVATE and TF_ANY can be merged into TF_ELMNTRY? */
/* TODO
#define T_PARAM     12
#define T_CLASS     13
#define T_DISJOINT  14
#define T_JAGGED    15*/

#define Q_VAR       0x01
#define Q_WRONLY    0x02 /* perhaps it can be merged with var in bootstrap compiler */
#define Q_ALIASED   0x04
#define Q_THREADED  0x08 /* perhaps this and aliases can be merged in bootstrap compiler */
#define Q_OWN       0x10

#define M_LONG_ARR_LENGTH    0xFFFF
#define M_UNKNOWN_ARR_LENGTH 0xFFFE

enum BuiltinType {
    BT_BOOL,
    BT_USIZE,
    BT_INT
    /* TODO */
};
#define BT_NUMTYPES (BT_INT+1)

struct Type {
    unsigned deftype : 2;
    unsigned type : 4;
    unsigned quals : 5;
    unsigned misc : 16;
    union {
        struct Type *nested;
        struct Ident *ident;
        struct FieldOrParamList *fields;
        struct EnumType *enu;
        struct FunctionType *func;
        struct ArrayType *arr; /* if length doesn't fit in "misc" */
        enum BuiltinType builtin;
    } kind;
    /* TODO */
    /*
       array:      *(length+elemtype), or [small length in flags] (elemtype)
       enum:       *(basetype+*values)
       struct:     *members
       bitfield:   *members
       class struct: *classes(enumvalue+*members)
       elementary: id
       pointer:    targetype
       private
       any
       function:   *(return, *arguments)
       identref:   identref (identifier or name). alternatively, store the identref elsewhere and have a pointer back here.
       parametric: *(identref+typeparams)

       qualifiers and optional types can be stored in the flags
    */
};

struct TypeRef {
    struct Type *type;
    void *prm; /* TODO */
    unsigned quals; /* TODO */
};

/** Member of a struct or a function parameter. */
struct FieldOrParam {
    struct FieldOrParam *list_next;
    struct FieldOrParam *bucket_next;
    unsigned int hash;
    char *name;
    struct Type type;
};

struct FieldOrParamList {
    size_t count, num_buckets;
    struct FieldOrParam *first;
    struct FieldOrParam **buckets;
};

struct EnumValue {
    struct EnumValue *next;
    unsigned int hash;
    char *name;
    struct Expr *value;
};

struct EnumType {
    struct Type *base;
    struct EnumValue *values;
};

struct FunctionType {
    struct Type returntype;
    struct FieldOrParamList params;
};

struct ArrayType {
    struct Type elemtype;
    struct Expr *lengthexpr;
};

#define E_UNARYOP     1
#define E_BINARYOP    2
#define E_CONDITIONAL 3
#define E_CONDCHOICES 4
#define E_LOCALIDENT  5   /* FIXME what is a local enum type? local or global? */
#define E_GLOBALIDENT 6
#define E_NUMBER      7
#define E_STRING      8
#define E_NONE        9
#define E_UNDEF      10
#define E_ARRAY      11
#define E_STRUCT     12
#define E_INDEX      13
#define E_CALL       14

enum OpNum {
    /* Unary operators */
    OP_INC = 0,
    OP_DEC,
    /* Binary operators */
    OP_ADD,
    OP_SUB,
    OP_MUL,
    OP_DIV,
    OP_MOD,
    OP_NOT,
    OP_AND,
    OP_OR,
    OP_EQ,
    OP_NOTEQ,
    OP_LESS,
    OP_LEQ,
    OP_GREATER,
    OP_GEQ,
    OP_ASSIGN,
    OP_ADDASSIGN,
    OP_SUBASSIGN,
    OP_MULASSIGN,
    OP_DIVASSIGN,
    OP_MEMBER,
    /* Ternary operators */
    OP_CONDITIONAL
};

struct LiteralValue {
    size_t length;
    char *data;
};

struct Expr {
    unsigned type : 4;
    unsigned op : 8;
    union {
        struct Expr *expr;
        struct LiteralValue *value;
        struct ExprList *exprlist;
        struct CondChoices *condchoices; /* TODO or general "select" expr? i.e. for any enum type */
        struct LocalIdent *localident;
        struct Ident *ident;
    } a;
    union {
        struct Expr *expr;
    } b;
    /* Temporary state */
    union {
        struct Expr *rpnnext;
        struct TypeRef tr;
    } tmp;
};

enum RPNContext {
    RC_TERMINAL,  /* no arguments follow because it's a terminal symbol */
    RC_OP,        /* number of arguments depends on the operator type */
    RC_UNARY,     /* a single argument follows (used for unary +/-) */
    RC_ARGLIST,   /* function call or array index access */
    RC_GROUPING,  /* grouping, e.g. (x+x)*2 */
    RC_ELEMLIST,  /* structs and arrays */
    RC_LOCALIDENT /* local identifier (subcategory of RC_TERMINAL) */
};

struct RPNEntry {
    union {
        struct {
            unsigned tokentype : 8;
            unsigned context : 4;
            size_t length; /* number of arguments -or- size of data */
            struct RPNEntry *next;
            union {
                char *pointer;
                struct Ident *ident;
                struct LocalIdent *localident;
            } data;
        } rpn;
        struct Expr expr;
    } stage;
};

struct ExprElement {
    struct ExprElement *next;
    struct Expr *expr;
};

struct ExprList {
    size_t length;
    struct ExprElement first;
};

struct CondChoices {
    struct Expr trueexpr;
    struct Expr falseexpr;
};

struct Decl {
    struct Type type;
    /*union {
        struct Expr *initval;
        struct Block *funcbody;
    } kind;*/
};

/*
 algorithm for ordering definitions (see also ident.c)
  - first all types, as follows:
  -- try to define the next remaining type
  -- if there are undefined dependencies
  --- simple solution O(n^2): put it last
  --- optimization, if there is only one undefined dependency:
  ---- create this identifier (in undef state) and add a "reverse-depends".
       when it is defined, we can then process the reverse-depends.
  - second, data-decls and functions (in no particular order, as they cannot reference each other)

 compile time constants need to be evaluated (should not need to take ordering into account)
 - enum values
 - data initial/constant values

 special cases:
 - enum values or data value with sizeof(some other data,which might not yet be defined)
 -- can we simply disallow this?
*/
struct Ident {
    struct Decl decl;
    char *name;
    struct Ident *chain_next;
    struct Ident *bucket_next; /* could perhaps be overloaded for rdepends also */
    unsigned int hash;
    short namelength;
};

#define S_BLOCK    0
#define S_DECL     1
#define S_EXPR     2
/*#define S_ASSIGN   3*/
#define S_RETURN   4
#define S_BREAK    5
#define S_CONT     6
#define S_GOTO     7
#define S_IF       8
#define S_WHILE    9
#define S_DOWHILE 10
#define S_FOR     11
#define S_SWITCH  12
#define S_ASSERT  13
#define S_LABEL   14
#define S_UNREACH 15
#define S_NOP     16 /* No operation. Hack for blank blocks */
/* TODO typeassert statement/expression? */

struct LocalIdent {
    struct LocalIdent *lower, *higher/*, *base, *level_next*/;
    /* FIXME we need to be able to reference the idents... but we already have fields and function parameters that don't use the Ident type.
             Alternatively, use two different literal types for identifiers, one for local and another one for non global.
             (or even GlobalIdent, ParamIdent and LocalIdent) */
    /*struct Ident ident;*/
    unsigned int hash;
    char *name;
    struct Type type;
    struct Expr *initval;
};

struct Stmt {
    unsigned type : 5;
    struct Stmt *next;
    /* TODO */
    union {
        struct Expr *expr;
        struct LocalIdent *localvar;
        struct GotoIdent *gotoident;
        struct Block *block;
        struct CtlIf *ifstm;
        struct CtlWhile *whilestm;
        struct CtlFor *forstm;
        struct CtlSwitch *switchstm;
        struct LoopInfo *loopinfo;
    } kind;
};

struct Block {
    struct Block *base;
    struct Stmt stmt;
    struct LocalIdent *idents;
};

struct LoopInfo {
    struct LoopInfo *base;
    unsigned long gotoid;
    int has_break;
};

struct CtlIf {
    struct Expr *cond;
    struct Block true_block;
    struct Block *false_block;
};

struct CtlWhile {
    struct Expr *cond;
    struct Block block;
    struct Block *empty;
    struct Block *end;
    struct LoopInfo loopinfo;
};

struct CtlFor {
    /* TODO */
    struct LocalIdent loopvar;
    struct Expr *loopexpr;
    struct Block block;
    struct Block *empty;
    struct Block *end;
    struct LoopInfo loopinfo;
};

struct CaseValue {
    struct CaseValue *next;
    struct Expr *expr; /* null for default case */
    struct Block *withblock;
};

struct SwitchCase {
    struct SwitchCase *next;
    struct CaseValue values;
    struct Block block;
};

struct CtlSwitch {
    struct Expr *cond;
    struct SwitchCase *cases;
};

struct GotoIdent {
    struct GotoIdent *lower, *higher;
    unsigned int hash;
    char *name;
    int declared;
    /* TODO */
};

struct FunctionState {
    struct GotoIdent *gotoidents;
};

extern struct TypeRef builtin_tr[];


void error_tok(const struct Token *tok, const char *s);
void error_linecol(int line, int column, const char *s);
NORETURN void out_of_memory(void);
NORETURN void internal_error(int error_id);

int parse_file(FILE *sourcefile, int decls_only);
void output_set_file(FILE *outfile);
int output_dependencies(void);
int output_funcbody(struct Ident *ident, struct Block *funcbody);
int output_initval(struct Ident *ident, struct Expr *initval);

struct Ident *ident_insert(unsigned flags, const struct Token *token);
void identarena_new(void);
void identarena_free(void);
struct Ident *ident_list(unsigned deftype);

int localident_insert(struct Block *block, struct LocalIdent *ident,
                      const struct Token *token);
struct LocalIdent *localident_find(struct Block *block,
                                   const struct Token *token);
struct GotoIdent *gotoident(struct FunctionState *funcstate,
                             const struct Token *token);

#define ARR_ELEM_TYPE(arrtype) \
    ((arrtype)->misc >= M_UNKNOWN_ARR_LENGTH ? \
        &(arrtype)->kind.arr->elemtype : \
        (arrtype)->kind.nested)
void init_builtins(void);
void require_tr(const struct Expr *expr, const char *errmsg);
struct TypeRef root_tr(struct Type *type);
struct TypeRef nested_tr(struct Type *type, struct TypeRef *wrappedby);
struct TypeRef get_elem_tr(struct TypeRef *tr);
int check_compat(const char *itemname,
                 struct TypeRef *tr, struct TypeRef *target);
struct TypeRef require_expr_type(struct Expr *expr, unsigned type);


void arena_new(void);
void arena_free(void);
void *aalloc(size_t size, size_t align);

#endif