#include "all.h"
#include "vec.h"
#include <linux/limits.h>
#include <stdint.h>
#include <stdlib.h>
#include <strings.h>

/***********/
/** Lexer **/
/***********/

static u8
chr(struct parser *P) {
   int c;
   if (P->peekchr >= 0) {
      c = P->peekchr;
      P->peekchr = -1;
   } else {
      c = fgetc(P->fp);
   }
   P->curspan.idx++;
   P->curspan.col++;
   if (c == '\n') {
      P->curspan.col = 1;
      P->curspan.line++;
   }
   if (c == EOF || !c) {
      P->eof = 1;
      return 0;
   }
   return c;
}

static u8
chrpeek(struct parser *P) {
   int c;
   if (P->peekchr >= 0)
      return P->peekchr;
   c = fgetc(P->fp);
   return P->peekchr = c == EOF ? 0 : (u8)c;
}

static bool
chrmatch(struct parser *P, u8 c) {
   if (chrpeek(P) == c) {
      chr(P);
      return 1;
   }
   return 0;
}

static bool
aisspace(char c) {
   switch (c)
   case  ' ': case '\t': case '\n':
   case '\r': case '\v': case '\f':
      return 1;
   return 0;
}

static bool
aisdigit(char c) {
   return c >= '0' && c <= '9';
}

static bool
aisxdigit(char c) {
   return (c >= '0' && c <= '9')
       || (c >= 'A' && c <= 'F')
       || (c >= 'a' && c <= 'f') ;
}

static bool
aisalpha(char c) {
   return (c >= 'a' && c <= 'z')
       || (c >= 'A' && c <= 'Z');
}

static bool
aissep(char c) {
   if (aisspace(c))
      return 1;
   switch (c)
   case '(': case ')': case '[': case ']':
   case '{': case '}': case '.': case ',':
   case ';': case '?': case '+': case '-':
   case '*': case '/': case '&': case '|':
   case '^': case '~': case '=': case '\'':
   case '"': case '<': case '>': case ':':
   case '@': case '#': case '%': case '\\':
   case '`':
      return 1;
   return 0;
}

static void
eatspaces(struct parser *P) {
   for (;; chr(P)) {
      if (aisspace(chrpeek(P)))
         continue;
      else
         break;
   }
}

static int
readtilsep(struct parser *P, char *buf, int n, bool dot) {
   int i = 0;
   u8 c;
   while (!aissep((c = chrpeek(P))) || (dot && c == '.')) {
      chr(P);
      if (i >= n - 1)
         return -1;
      buf[i++] = c;
   }
   buf[i++] = 0;
   return i;
}

static bool
aishsep(char c) {
   if (aisspace(c))
      return 1;
   switch (c)
   case '(': case ')': case '[': case ']':
   case '{': case '}': case '.': case ',':
   case ';': case '"':
      return 1;
   return 0;
}

static int
readtilhsep(struct parser *P, char *buf, int n, bool dot) {
   int i = 0;
   bool (*pred)(char) = aishsep;
   u8 c;
   while (!pred((c = chrpeek(P))) || (dot && c == '.')) {
      chr(P);
      if (!aissep(c))
         pred = aissep;
      if (i >= n - 1)
         return -1;
      buf[i++] = c;
   }
   buf[i++] = 0;
   return i;
}

const char *keyword2str[] = {
#define KWSTR(kw) #kw,
   LIST_KEYWORDS(KWSTR)
#undef KWSTR
};
// #define NUM_KEYWORDS (sizeof keyword2str / sizeof *keyword2str)

static int
str2keyword(const char *s) {
   int i = 0, j = NUM_KEYWORDS - 1;
   while (i <= j) {
      int k = (j + i) / 2;
      int cmp = strcmp(keyword2str[k], s);
      if (!cmp) {
         return k;
      } else if (cmp < 0) {
         i = k + 1;
      } else {
         j = k - 1;
      }
   }
   return -1;
}
 
static bool
readnumber(struct tok *res, const char *s) {
   char c;
   u64 acc = 0;
   double accf = 0.0;
   double fmul = 0.1;
   int base = 10;
   bool flt = 0;
   int nused = 0;
   const char *suffix = NULL;

   for (int i = 0; (c = s[i]); ++i) {
      extern int tolower(int);

      if (i == 0 && c == '0')
         --nused;

      if (i == 1 && tolower(c) == 'x') {
         base = 16;
         continue;
      }
      if (!flt && c == '.' && base == 10) {
         flt = 1;
         accf = acc;
         continue;
      }
      
      if (nused > 0 && c == '_')
         continue;

      if ((base == 16 && !aisxdigit(c))
       || (base != 16 && (c < '0' || c > '0' + base - 1))) {
         suffix = s + i;
         break;
      }

      ++nused;
      if (flt) {
         accf = accf + (c - '0') * fmul;
         fmul *= 0.1;
      } else {
         c = tolower(c);
         acc = acc * base + (c <= '9' ? c - '0' : c - 'a' + 10);
      }
   }
   memset(res, 0, sizeof *res);
   if (flt) {
      res->t = TKflolit;
      res->flit.f = accf;

      if (!suffix) ;
      else if (!strcasecmp(suffix,   "f")) res->flit.ty = ty_f32;
      else if (!strcasecmp(suffix, "f32")) res->flit.ty = ty_f32;
      else if (!strcasecmp(suffix, "f64")) res->flit.ty = ty_f64;
      else return 0;
   } else {
      res->t = TKintlit;
      res->ilit.i = acc;

      if (!suffix) ;
      else if (!strcasecmp(suffix,   "u")) res->ilit.ty = ty_uint;
      else if (!strcasecmp(suffix , "u8")) res->ilit.ty = ty_u8;
      else if (!strcasecmp(suffix , "i8")) res->ilit.ty = ty_i8;
      else if (!strcasecmp(suffix, "u16")) res->ilit.ty = ty_u16;
      else if (!strcasecmp(suffix, "i16")) res->ilit.ty = ty_i16;
      else if (!strcasecmp(suffix, "u32")) res->ilit.ty = ty_u32;
      else if (!strcasecmp(suffix, "i32")) res->ilit.ty = ty_i32;
      else if (!strcasecmp(suffix, "u64")) res->ilit.ty = ty_u64;
      else if (!strcasecmp(suffix, "i64")) res->ilit.ty = ty_i64;
      else if (!strcasecmp(suffix,   "z")) res->ilit.ty = ty_usize;
      else if (!strcasecmp(suffix,  "zs")) res->ilit.ty = ty_isize;
      else if (!strcasecmp(suffix,   "p")) res->ilit.ty = ty_uptrint;
      else if (!strcasecmp(suffix,  "ps")) res->ilit.ty = ty_iptrint;
      else return 0;
   }
   return 1;
}

static size_t
readstrlit(struct parser *P, u8 delim, char *s, size_t n) {
   u8 c;
   size_t i = 0;
   while ((c = chr(P)) != delim) {
      if (!c || c == '\n')
         fatal(P, P->tokspan, "unterminated %s literal",
               delim == '"' ? "string" : "character");
      if (i == n - 1)
         assert(0 && "too long string/charliteral");

      if (c != '\\')
         s[i++] = c;
      else switch ((c = chr(P))) {
      case 0: case '\n':
         fatal(P, P->tokspan, "unterminated %s literal",
               delim == '"' ? "string" : "character");
      case '\'': s[i++] = '\''; break;
      case '\\': s[i++] = '\\'; break;
      case '"': s[i++] = '"'; break;
      case 'n': s[i++] = '\n'; break;
      case 'r': s[i++] = '\r'; break;
      case 't': s[i++] = '\t'; break;
      case 'v': s[i++] = '\v'; break;
      case 'f': s[i++] = '\f'; break;
      case 'e': s[i++] = '\x1b'; break;
      case '0': s[i++] = '\0'; break;
      default:
         fatal(P, P->tokspan, "unknown escape sequence '\\%c'", c);
      }
   }
   s[i++] = 0;
   return i - 1;
}

#define MAX_MACROEXPAND_ITER 100

static struct tok
lex(struct parser *P) {
   u8 c;
   struct tok tok;

   if (P->have_peektok) {
      tok = P->peektok;
      P->have_peektok = 0;
      return tok;
   }

   if (P->expanno > MAX_MACROEXPAND_ITER) {
      fatal(P, P->curspan,
            "maximum number of nested macro expansions reached (infinite recursion?)");
   }

   if (P->curexpan) {
      struct expan *ep = P->curexpan;
      if (ep->idx == ep->toks.n) {
         // end of macro expansion
         --P->expanno;
         free(ep->args.d);
         P->curexpan = ep->prev;
         P->have_peektok = ep->have_peektok;
         P->peektok = ep->peektok;
         free(ep);
         return lex(P);
      }
      tok = ep->toks.d[ep->idx++];
      // expand macro arg?
      if (tok.t == TKmacident) {
         for (struct expan *ep = P->curexpan; ep; ep = ep->prev) {
            for (int i = 0; i < ep->args.n; ++i) {
               if (!strcmp(tok.str, ep->args.d[i].name)) {
                  ++P->expanno;
                  P->curexpan = memcpy(xmalloc(sizeof *ep), &(struct expan) {
                     P->curexpan, {0}, ep->args.d[i].toks,
                  }, sizeof *ep);
                  return lex(P);
               }
            }
         }
      } else if (tok.t == '#FIL' || tok.t == '#LIN') {
         struct expan *ep;
         for (ep = P->curexpan; ep->prev; ep = ep->prev)
            ;
         if (tok.t == '#FIL') {
            return (struct tok) { TKstrlit, tok.span,
               .str = fileid2path(ep->span.fileid),
               .strlen = strlen(fileid2path(ep->span.fileid))  };
         } else {
            return (struct tok) { TKintlit, tok.span,
               .ilit.i = ep->span.line };
         }
      }
      return tok;
   }

   eatspaces(P);
   tok.span = P->tokspan = P->curspan;
   if (aisdigit((c = chrpeek(P)))) {
      char s[80];

      if (readtilsep(P, s, sizeof s, 1) < 0)
         fatal(P, P->tokspan, "number literal too long");
      if (!readnumber(&tok, s))
         fatal(P, P->tokspan, "invalid number literal %q", s);
      tok.span = P->tokspan;
      return tok;
   } else if (aisalpha(c) || c == '_' || c == '$') {
      char s[100];
      int t;

      if (readtilsep(P, s, sizeof s, 0) < 0)
         fatal(P, P->tokspan, "identifier too long");
      if ((t = str2keyword(s)) >= 0) {
         tok.t = t;
      } else if (c == '$') {
         tok.t = TKgensym;
         tok.str = xstrdup(s + 1); 
      } else { 
         tok.t = TKident;
         tok.str = xstrdup(s); 
      }
      return tok;
   } else if (c == '#') {
      char s[100];

      if (readtilhsep(P, s, sizeof s, 0) < 0) {
         fatal(P, P->tokspan, "invalid #keyword");
      } else if (!strcmp(s, "#") && chrpeek(P) == '{') {
         chr(P);
         int bal = 1;
         while (bal != 0) {
            switch (lex(P).t) {
            case '{': ++bal; break;
            case '}': --bal; break;
            case TKeof: fatal(P, tok.span, "unterminated comment");
            }
         }
         return lex(P);
      } else if (!strcmp(s, "#")) {
         tok.t = '#';
      } else if (!strcmp(s, "#t") || !strcmp(s, "#f")) {
         tok.t = TKboolit;
         tok.boolit = s[1] == 't';
      } else if (!strcmp(s, "#null")) {
         tok.t = TKnullit;
      } else if (!strcmp(s, "##")) {
         tok.t = '##';
      } else if (!strcmp(s, "#len")) {
         tok.t = '#len';
      } else if (!strcmp(s, "#ptr")) {
         tok.t = '#ptr';
      } else if (!strcmp(s, "#when")) {
         tok.t = TKhwhen;
      } else if (!strcmp(s, "#tag")) {
         tok.t = '#tag';
      } else if (!strcmp(s, "#?")) {
         tok.t = '#?';
      } else if (!strncmp(s, "#'", 2)) {
         tok.t = TKlabel;
         tok.str = xstrdup(s);
      } else if (!strcmp(s, "#FILE")) {
         tok.t = '#FIL';
      } else if (!strcmp(s, "#LINE")) {
         tok.t = '#LIN';
      } else {
         fatal(P, P->tokspan, "invalid #keyword");
      } 
      return tok;
   } else if (c == '\'' || c == '"') {
      u8 delim = c;
      char s[1000];
      size_t n;
      chr(P);
      tok.span = P->tokspan = P->curspan;
      n = readstrlit(P, delim, s, sizeof s); 
      if (delim == '"') {
         tok.t = TKstrlit;
         tok.str = memcpy(xmalloc(n + 1), s, n + 1);
         tok.strlen = n;
      } else {
         if (n == 0)
            fatal(P, P->tokspan, "empty char literal");
         if (n > 8)
            fatal(P, P->tokspan, "too long multichar literal '%s'", s);
         tok.t = TKchrlit;
         tok.ilit.i = 0;
         tok.ilit.ty = NULL;
         for (int j = 0; j < n; ++j)
            tok.ilit.i = (tok.ilit.i << 8) | (u8)s[j];
      }
      return tok;
   }
   switch ((c = chr(P))) {
   case '(': case ')': case '[': case ']':
   case '{': case '}': case ',':
   case ';': case '~':
      tok.t = c;
      return tok;
   case '?':
      if (chrmatch(P, '?')) tok.t = '\?\?';
      else                  tok.t = '?';
      return tok;
   case '.':
      if (chrmatch(P, '.')) {
         if (chr(P) != '.')
            fatal(P, P->tokspan, "invalid token '..'");
         tok.t = '...';
      } else {
         tok.t = c;
      }
      return tok;
   case '*':
      if (chrmatch(P, '=')) tok.t = '*=';
      else                  tok.t = '*';
      return tok;
   case '/':
      if      (chrmatch(P, '=')) tok.t = '/=';
      else if (chrmatch(P, '/')) {
         while ((c = chr(P)) != 0 && c != '\n')
            ;
         return lex(P);
      }
      else                  tok.t = '/';
      return tok;
   case '%':
      if (chrmatch(P, '=')) tok.t = '%=';
      else                  tok.t = '%';
      return tok;
   case '+':
      if      (chrmatch(P, '=')) tok.t = '+=';
      else if (chrmatch(P, '+')) tok.t = '++';
      else                       tok.t = '+';
      return tok;
   case '-':
      if      (chrmatch(P, '=')) tok.t = '-=';
      else if (chrmatch(P, '-')) tok.t = '--';
      else if (chrmatch(P, '>')) tok.t = '->';
      else                       tok.t = '-';
      return tok;
   case '&':
      if (chrmatch(P, '=')) tok.t = '&=';
      else                  tok.t = '&';
      return tok;
   case '|':
      if (chrmatch(P, '=')) tok.t = '|=';
      else                  tok.t = '|';
      return tok;
   case '^':
      if (chrmatch(P, '=')) tok.t = '^=';
      else                  tok.t = '^';
      return tok;
   case ':':
      if      (chrmatch(P, '=')) tok.t = ':=';
      else if (chrmatch(P, ':')) tok.t = '::';
      else                       tok.t = ':';
      return tok;
   case '=':
      if (chrmatch(P, '=')) tok.t = '==';
      else                  tok.t = '=';
      return tok;
   case '!':
      if (chrmatch(P, '=')) tok.t = '!=';
      else                  tok.t = '!';
      return tok;
   case '<':
      if (chrmatch(P, '=')) tok.t = '<=';
      else if (chrmatch(P, '<')) {
         if (chrmatch(P, '=')) tok.t = '<<=';
         else                  tok.t = '<<';
      } else tok.t = '<';
      return tok;
   case '>':
      if (chrmatch(P, '=')) tok.t = '>=';
      else if (chrmatch(P, '>')) {
         if (chrmatch(P, '=')) tok.t = '>>=';
         else                  tok.t = '>>';
      } else tok.t = '>';
      return tok;
   case 0:
      tok.t = TKeof;
      return tok;
   }
   fatal(P, P->tokspan, "unexpected character '%c'", c);
}

static struct tok
lexpeek(struct parser *P) {
   struct tok tok;

   if (P->have_peektok)
      return P->peektok;
   tok = lex(P);
   P->peektok = tok;
   P->have_peektok = 1;
   return tok;
}

static bool
lexmatch(struct parser *P, struct tok *tokp, int t) {
   struct tok tok = lexpeek(P);

   if (tokp)
      *tokp = tok;
   if (tok.t == t) {
      lex(P);
      return 1;
   }
   return 0;
}

static struct tok
lexexpects(struct parser *P, int t, const char *what) {
   struct tok tok;
   if (!lexmatch(P, &tok, t))
      fatal(P, tok.span, "expected %s (near %T)",
            what ? what : tokt2str(t), tok);
   return tok;
}
#define lexexpect(P, t) lexexpects(P, t, NULL)

/************/
/** Parser **/
/************/

static void
pushenv(struct parser *P, struct env *env) {
   assert(P->curenv == env->parent);
   P->curenv = env;
}

static void
popenv(struct parser *P) {
   P->curenv = P->curenv->parent;
   assert(P->curenv);
}

static struct decl *
putdecl(struct parser *P, struct span espan, const struct decl *decl) {
   struct decl *ret;
   if (envfind(P->primenv, INT_MAX, decl->name))
      fatal(P, espan, "cannot shadow primitive `%s'", decl->name);
   if (!(ret = envput(P->curenv, decl)))
      fatal(P, decl->span,
            "cannot shadow earlier incompatible declaration of `%s'", decl->name);
   if (!P->save_envage)
      P->envage = MAX(P->envage, ret->age);
   return ret;
}

static const struct decl *
finddecl(struct parser *P, const char *name) {
   const struct decl *decl;
   if ((decl = envfind(P->primenv, INT_MAX, name)))
      return decl;
   return envfind(P->curenv, P->envage, name);
}

static struct expr parseexpr(struct parser *P);


static const struct type *xident2type(struct parser *P, struct tok tok);
static const struct type *parsetype(struct parser *P);

static const struct type *
parsefntype(struct parser *P) {
   struct type ty = {TYfn, 0, g_targ.sizesize};
   vec_t(const struct type *) params = {0};
   struct tok tok;

   lexexpect(P, '(');
   while (!lexmatch(P, &tok, ')')) {
      if (lexmatch(P, &tok, '...')) {
         ty.fn.variadic = 1;
      } else {
         const struct type *param ;
         if (lexmatch(P, &tok, TKident)) {
            if (lexpeek(P).t == ',' || lexpeek(P).t == ')')
               param = xident2type(P, tok); 
            else
               param = parsetype(P);
         } else {
            param = parsetype(P);
         }
         if (!completetype(param))
            fatal(P, tok.span, "parameter type is incomplete (%t)",
                  param);
         vec_push(&params, param);
      }
      if (!lexmatch(P, &tok, ',')) {
         lexexpect(P, ')');
         break;
      } else if (ty.fn.variadic) {
         lexexpect(P, ')');
         break;
      }
   }
   vec_slice_cpy(&ty.fn.params, &params);
   ty.fn.retty = unconstify(parsetype(P));
   if (ty.fn.retty != ty_void && !completetype(ty.fn.retty)) {
      fatal(P, tok.span, "return type is incomplete (%t)",
            ty.fn.retty);
   }

   return interntype(ty);
}

static const struct type *
mkslicetype(const struct type *child) {
   int align = MAX(g_targ.ptrsize, g_targ.sizesize);
   return interntype((struct type) {
         TYslice, ALIGNUP(g_targ.ptrsize + g_targ.sizesize, align), align,
         .child = child
   });
}

static struct expr *
exprdup(struct expr ex) {
   return memcpy(xmalloc(sizeof ex), &ex, sizeof ex);
}

static const struct type *parseagg(struct parser *P, const char *name, int kind, struct decl **retdecl);
static const struct type *parseenum(struct parser *P, const char *name, struct attr);

static const struct type *
parseexpandtepl(struct parser *P, struct tepl *tepl) {
   struct expanarg *args = xcalloc(tepl->params.n, sizeof *args);
   struct expan expan = { P->curexpan, .name = tepl->name };
   struct tok tok;
   const struct type *ty = NULL; 
   int i = 0;

   lexexpect(P, '<');
   expan.span = container_of(tepl, struct decl, tepl)->span;
   expan.tepl = 1;
   while (!lexmatch(P, &tok, '>')) {
      struct teplparam *par = tepl->params.d + i;
      struct toktree toks = {{ xmalloc(sizeof (struct tok)), 1 }};
   
      if (par->typ) {
         toks.d->span = P->curspan;
         const struct type *ty = parsetype(P);
         toks.d->t = TKtype;
         toks.d->ty = ty;
      } else {
         struct expr ex = parseexpr(P);
         if (!fold(&ex))
            fatal(P, ex.span, "template parameter is not constant expression");
         toks.d->span = P->tokspan;
         toks.d->t = TKexpr;
         toks.d->ex = exprdup(ex);
      }

      args[i].name = par->name;
      args[i].toks = toks;

      ++i;
      if (!lexmatch(P, &tok, ',')) {
         lexexpect(P, '>');
         break;
      }
   }
   if (i != tepl->params.n)
      fatal(P, tok.span, "invalid argument count for template `%s'", tepl->name);

   slice_t(struct teplarg) tpargs = {
      xmalloc(tepl->params.n * sizeof(struct teplarg)),
      tepl->params.n
   };
   struct teplcache *cache;
 
   for (int i = 0; i < tepl->params.n; ++i) {
      if (tepl->params.d[i].typ) {
         tpargs.d[i].typ = 1;
         tpargs.d[i].ty = args[i].toks.d[0].ty;
      } else {
         assert(0);
      }
   }

   // TODO hashmap ?
   for (cache = tepl->cache; cache; cache = cache->next) {
      for (int i = 0; i < tepl->params.n; ++i) {
         if (tepl->params.d[i].typ) {
            if (cache->args.d[i].ty != tpargs.d[i].ty)
               goto next;
         } else {
            assert(0);
         }
      }
      free(tpargs.d);
      return cache->ty;
   next:;
   }

   struct env env = { tepl->env };

   WITH_TMPCHANGE(struct env *, P->curenv, &env) {
      struct decl *decl;
      expan.args.d = args;
      expan.args.n = i;
      expan.toks = tepl->toks;
      ++P->expanno;
      P->curexpan = memcpy(xmalloc(sizeof expan), &expan, sizeof expan);
      WITH_TMPCHANGE(int, P->envage, tepl->envage)
         WITH_TMPCHANGE(int, P->save_envage, 1)
            ty = parseagg(P, tepl->name, tepl->tkind, &decl);
   }
   free(env.decls);
   memcpy(&((struct type *)ty)->agg.tpargs, &tpargs, sizeof tpargs);
   cache = xcalloc(sizeof *cache, 1);
   cache->next = tepl->cache;
   memcpy(&cache->args, &tpargs, sizeof tpargs);
   cache->ty = ty;
   tepl->cache = cache;

   return ty;
}

static const struct type *
xident2type(struct parser *P, struct tok tok) {
   const struct decl *decl = finddecl(P, tok.str);
   if (!decl)
      fatal(P, P->tokspan, "%T is not defined", tok);
   if (decl->t == Dtype) {
      return decl->ty;
   } else if (decl->t == Dtepl && decl->tepl.t == Dtype) {
      return parseexpandtepl(P, (struct tepl *)&decl->tepl);         
   } else
      fatal(P, P->tokspan, "%T is not a type", tok);
}

static const struct type *
parsetype(struct parser *P) {
   struct tok tok;
   if (lexmatch(P, &tok, '*')) {
      const struct type *child = parsetype(P);
      return interntype((struct type) {
            TYptr, g_targ.ptrsize, g_targ.ptrsize,
            .child = child,
      });
   } else if (lexmatch(P, &tok, '[')) {
      i64 length = -1;
      bool slice = 0;
      const struct type *child;

      if (lexmatch(P, &tok, '#')) {
         slice = 1;
         lexexpect(P, ']');
      } else if (!lexmatch(P, &tok, ']')) {
         struct expr ex = parseexpr(P);
         if (!fold(&ex) || (ex.t != Eintlit && !(ex.t == Eenumval && ex.ty->enu.lax)))
            fatal(P, ex.span,
                  "array length should be a compile-time integral expression");
         if ((length = ex.i) < 0)
            fatal(P, ex.span, "negative array length");
         lexexpect(P, ']');
      }
      child = parsetype(P);
      if (!slice && !completetype(child))
         fatal(P, tok.span, "array of incomplete type (%t)", child);
      if (slice)
         return mkslicetype(child);
      else
         return interntype((struct type) {
               TYarr, length * child->size, child->align,
               .child = child, .length = length
         });
   } else if (lexmatch(P, &tok, TKkw_const)) {
      return constify(parsetype(P));
   } else if (lexmatch(P, &tok, TKkw_struct)) {
      struct decl *_decl;
      return parseagg(P, NULL, TYstruct, &_decl);
   } else if (lexmatch(P, &tok, TKkw_union)) {
      struct decl *_decl;
      return parseagg(P, NULL, TYunion, &_decl);
   } else if (lexmatch(P, &tok, TKkw_enum)) {
      struct decl *_decl;
      if (lexmatch(P, NULL, TKkw_union))
            return parseagg(P, NULL, TYeunion, &_decl);
      return parseenum(P, NULL, (struct attr){0});
   } else if (lexmatch(P, &tok, TKkw_typeof)) {
      const struct type *ty = NULL, *ty2, *ty0;
      lexexpect(P, '(');
      do {
         ty2 = parseexpr(P).ty;
         ty0 = ty;
         ty = ty ? typeof2(ty, ty2) : ty2;
         if (!ty)
            fatal(P, tok.span, "incompatible types in typeof(...): %t and %t",
                  ty0, ty2);
         if (!lexmatch(P, &tok, ',')) {
            lexexpect(P, ')');
            break;
         }
      } while (!lexmatch(P, &tok, ')'));
      return ty;
   } else if (lexmatch(P, &tok, TKident)) {
      return xident2type(P, tok);
   } else if (lexmatch(P, &tok, TKkw_fn)) {
      return parsefntype(P);
   } else if (lexmatch(P, &tok, TKtype)) {
      return tok.ty;
   }
   fatal(P, P->tokspan, "expected type (near %T)", tok);
}

static const struct type *
ilittype(u64 n) {
   if (n <= INT_MAX)
      return ty_int;
   if (n <= INT32_MAX)
      return ty_i32;
   if (n <= INT64_MAX)
      return ty_i64;
   return ty_u64;
}

static const struct type *
numpromote(const struct type *ty) {
   int r = numtype2rank(ty);
   if (r < 0)
      return NULL;
   return rank2numtype(r);
}

static bool
islvalue(const struct expr *ex) {
   if (ex->t == Ename)
      return 1;
   if (ex->t == Eprefix && ex->unop.op == '*')
      return 1;
   if (ex->t == Eindex || ex->t == Eget || ex->t == Eeutag)
      return 1;
   if (ex->t == Eini)
      return 1;
   return 0;
}

/** Expression parsing **/

static struct blockstmt parseblock0(struct parser *P);
static struct stmt parseblock(struct parser *P);
static void parseexpandmacro(struct parser *P, const struct macro *macro);
static const struct type *
mkarraytype(const struct type *child, size_t n) {
   return interntype((struct type) {
      TYarr, n * child->size, 1, 0,
      .child = child, .length = n
   });
}

static struct aggfield *
structidx2fld(const struct type *ty, int idx) {
   if (idx < 0 || idx >= ty->agg.flds.n)
      return NULL;
   return &ty->agg.flds.d[idx];
}

static int
aggfldnam2idx(const struct type *ty, const char *name) {
   assert(name);
   if (ty->t != TYunion && ty->t != TYstruct && ty->t != TYeunion)
      return -1;
   for (int i = 0; i < ty->agg.flds.n; ++i)
      if (!strcmp(name, ty->agg.flds.d[i].name))
         return i;
   return -1;
}

static struct aggfield *
findaggfield(const struct type *ty, const char *name) {
   int i = aggfldnam2idx(ty, name);
   return i < 0 ? NULL : &ty->agg.flds.d[i];
}

static struct decl *
findaggdecl(const struct type *ty, const char *name) {
   assert(name);
   for (int i = 0; i < ty->agg.decls.n; ++i)
      if (!strcmp(name, ty->agg.decls.d[i]->name))
         return ty->agg.decls.d[i];
   return NULL;
}

static bool
typematchestarg(const struct type *targ, const struct type *ty) {
   if (!typeof2(targ, ty))
      return 0;
   if (targ->t == TYptr || ty->t == TYptr)
      if (!targ->child->konst && ty->child->konst)
         return 0;
   return 1;
}

static struct expr
parsestructini(struct parser *P, const struct type *ty) {
   struct expr ex = {Eini};
   struct tok tok;
   vec_t(struct iniarg) args = {0};
   int idx = 0;
   struct aggfield *fld;
   const char *kind = ty->t == TYstruct ? "struct" : "union";

   ex.span = lexpeek(P).span;

   while (!lexmatch(P, &tok, '}')) {
      struct expr e;
      
      if (lexmatch(P, &tok, '.')) {
         const char *fnam = (tok = lexexpect(P, TKident)).str;
         lexexpect(P, ':');
         idx = aggfldnam2idx(ty, fnam);
         if (idx < 0)
            fatal(P, tok.span, "%s %t has no field `%s'", kind, ty, fnam);
      }

      fld = structidx2fld(ty, idx++);
      if (!fld)
         fatal(P, P->tokspan,
               "excess elements in struct initializer");
      P->targty = fld->ty;
      e = parseexpr(P);
      if (!typematchestarg(fld->ty, e.ty))
         fatal(P, e.span,
               "incompatible element `%s` type in %s initializer (%t, expected %t)",
               fld->name, kind, e.ty, fld->ty);

      vec_push(&args, ((struct iniarg) {
         .fld = fld->name,
         e
      }));

      if (!lexmatch(P, &tok, ',')) {
         lexexpect(P, '}');
         break;
      }
   }

   ex.ty = ty;
   vec_slice_cpy(&ex.ini.args, &args);
   return ex;
}

static struct expr
parsearrini(struct parser *P, const struct type *ty) {
   struct expr ex = {Eini};
   struct tok tok;
   vec_t(struct iniarg) args = {0};
   i64 iota = 0;

   ex.span = lexpeek(P).span;

   while (!lexmatch(P, &tok, '}')) {
      struct expr e;
      
      if (lexmatch(P, &tok, '[')) {
         struct expr i = parseexpr(P);
         if (!fold(&i) || i.t != Eintlit)
            fatal(P, i.span,
                  "array initializer element index not a compile-time integer");
         iota = i.i;
         if (iota < 0)
            fatal(P, i.span, "array initializer element index is negative");
         lexexpect(P, ']');
         lexexpect(P, '=');
      }
      
      P->targty = ty->child;
      e = parseexpr(P);
      if (!typematchestarg(ty->child, e.ty))
         fatal(P, e.span,
               "incompatible element type in array initializer (%t, expected %t)",
               e.ty, ty->child);
      if (ty->length >= 0 && iota >= ty->length)
         fatal(P, e.span,
               "excess elements in array initializer");
      vec_push(&args, ((struct iniarg) { .idx = iota++, e }));      
      ex.ini.maxn = MAX(ex.ini.maxn, iota - 1);

      if (!lexmatch(P, &tok, ',')) {
         lexexpect(P, '}');
         break;
      }
   }
   
   ex.ty = ty;
   vec_slice_cpy(&ex.ini.args, &args);
   return ex;
}

static const struct type *
fntype(const struct fn *fn) {
   struct type ty = { TYfn, 0, g_targ.sizesize };
   if (fn->selfty)
      return fn->selfty;
   vec_t(const struct type *) params = {0};
   ty.fn.retty = fn->retty;
   for (int i = 0; i < fn->params.n; ++i)
      vec_push(&params, fn->params.d[i].ty);
   vec_slice_cpy(&ty.fn.params, &params);
   ty.fn.variadic = fn->variadic;
   return interntype(ty);
}

static struct expr
pexprimary(struct parser *P) {
   struct expr ex = {0};
   struct tok tok;
   const struct type *ty;

   P->used_targty = 0;

   if (lexmatch(P, &tok, TKintlit) || lexmatch(P, &tok, TKchrlit)) {
      ex.t = Eintlit;
      ex.span = tok.span;
      ex.i = tok.ilit.i;
      ex.ty = tok.ilit.ty ? tok.ilit.ty : ilittype(ex.u);
   } else if (lexmatch(P, &tok, TKflolit)) {
      ex.t = Eflolit;
      ex.span = tok.span;
      ex.f = tok.flit.f;
      ex.ty = tok.flit.ty ? tok.flit.ty : ty_f64;
   } else if (lexmatch(P, &tok, TKstrlit)) {
      ex.t = Estrlit;
      ex.span = tok.span;
      ex.strlit.d = tok.str;
      ex.strlit.n = tok.strlen;
      while (lexmatch(P, &tok, TKstrlit)) {
         ex.strlit.d = xrealloc((char *)ex.strlit.d, ex.strlit.n + tok.strlen + 1);
         memcpy((char *)ex.strlit.d + ex.strlit.n, tok.str, tok.strlen + 1);
         free((char *)tok.str);
         ex.strlit.n += tok.strlen;
      }
      ex.ty = mkarraytype(constify(ty_u8), ex.strlit.n + 1);
   } else if (lexmatch(P, &tok, TKboolit)) {
      ex.t = Eboolit;
      ex.span = tok.span;
      ex.i = tok.boolit;
      ex.ty = ty_bool;
   } else if (lexmatch(P, &tok, TKnullit)) {
      ex.t = Enullit;
      ex.span = tok.span;
      ex.i = tok.boolit;
      ex.ty = interntype((struct type) {
            TYptr, g_targ.ptrsize, .child = ty_void
      });
   } else if (lexmatch(P, &tok, TKident)) {
      const struct decl *decl;

      decl = finddecl(P, tok.str);
   decl:
      if (!decl)
         fatal(P, tok.span, "%T is not defined", tok);
      if (decl->t == Dtype) {
         ty = decl->ty;
      typedecl:
         if (ty->t == TYenum || ty->t == TYeunion) {
            lexexpect(P, ':');
            P->targty = ty;
            goto variant;
         } else if (ty->t == TYstruct || ty->t == TYunion) {
            if (lexmatch(P, &tok, ':')) {
               const char *nam = (tok = lexexpect(P, TKident)).str;
               for (int i = 0; i < ty->agg.decls.n; ++i) {
                  if (!strcmp(ty->agg.decls.d[i]->name, nam)) {
                     decl = ty->agg.decls.d[i];
                     goto decl;
                  }
               }
               fatal(P, tok.span, "no such declaration %t:%bs", ty, nam);
            } else { 
               lexexpects(P, '{', "`{' or `:'");
               P->targty = ty;
               goto aggini;
            }
         } else {
            goto experr;
         }
      } else if (decl->t == Dmacro) {
         parseexpandmacro(P, &decl->macro);
         ex = parseexpr(P);
      } else if (decl->t == Dtepl) {
         ty = parseexpandtepl(P, (struct tepl *)&decl->tepl);
         goto typedecl;
      } else {
         ex.t = Ename;
         ex.span = tok.span;
         ex.ref = decl;
         if (decl->t == Dlet) {
            if (decl->var.fnid != P->curfn->id)
               fatal(P, tok.span,
                     "cannot access local variable `%s' belonging to outer function",
                     tok.str);
            ex.ty = decl->var.ty;
         } else if (decl->t == Dstatic) {
            ex.ty = decl->var.ty;
         } else if (decl->t == Ddef) {
            ex = *decl->var.ini;
         } else if (decl->t == Dfn) {
            if (!decl->fn.selfty)
               ((struct decl *)decl)->fn.selfty = fntype(&decl->fn);
            ex.ty = decl->fn.selfty;
         } else assert(0);
      }
   } else if (lexmatch(P, &tok, TKtype)) {
      ty = tok.ty;
      goto typedecl;
   } else if (lexmatch(P, &tok, '(')) {
      if (lexpeek(P).t == TKkw_do) {
         struct blockstmt block;
         lex(P);
         block = parseblock0(P);
         ex.t = Eblock;
         ex.block = block;
         ex.ty = ty_void;
         if (ex.block.stmts.n > 0) {
            struct stmt *last = &block.stmts.d[block.stmts.n - 1];
            if (last->t == Sexpr)
               ex.ty = last->expr.ty;
         }
      } else {
         ex = parseexpr(P);
         P->used_targty = 0;
      }
      lexexpect(P, ')');
   } else if (lexmatch(P, &tok, ':')) {
      const char *vname;
      int i;
   variant:
      vname = (tok = lexexpect(P, TKident)).str;
      if (!(ex.ty = P->targty) || (ex.ty->t != TYenum && ex.ty->t != TYeunion))
         fatal(P, tok.span, "cannot infer type for enum literal `:%s'", vname);
      if (ex.ty->t == TYenum) {
         for (i = 0; i < ex.ty->enu.vals.n; ++i)
            if (!strcmp(ex.ty->enu.vals.d[i].name, vname))
               goto found;
         fatal(P, tok.span, "enum %t contains no variant `%s'", ex.ty, vname);
         found:
         P->used_targty = 1;
         ex.t = Eenumval;
         ex.span = tok.span;
         ex.enu.vname = vname;
         ex.enu.i = ex.ty->enu.vals.d[i].i;
      } else {
         const struct aggfield *fld;
         for (i = 0; i < ex.ty->agg.flds.n; ++i)
            if (!strcmp((fld = &ex.ty->agg.flds.d[i])->name, vname)) {
               goto found1;
            }
         fatal(P, tok.span, "tagged union %t contains no variant `%s'", ex.ty, vname);
      found1:
         P->used_targty = 1;
         ex.t = Eeuini;
         ex.span = tok.span;
         ex.euini.fnam = fld->name;
         ex.euini.tag = ex.ty->agg.enumty->enu.vals.d[i].i;
         P->targty = fld->ty;
         if (lexmatch(P, &tok, '(') || lexpeek(P).t == '{') {
            ex.euini.ini = exprdup(parseexpr(P));
            if (tok.t == '(')
               lexexpect(P, ')');
         }
         if (!!ex.euini.ini != !!fld->ty)
            fatal(P, tok.span, "invalid tagged union initializer");
    }
   } else if (lexmatch(P, &tok, '{')) {
   aggini:
      P->used_targty = 1;
      if (!P->targty)
        fatal(P, tok.span, "cannot infer type for compound initializer");
      if (lexmatch(P, NULL, '}'))
         ex.t = Ezeroini, ex.ty = P->targty;
      else if (P->targty->t == TYstruct || P->targty->t == TYunion)
         ex = parsestructini(P, P->targty);
      else if (P->targty->t == TYarr)
         ex = parsearrini(P, P->targty);
      ex.span = tok.span;
   } else if (lexmatch(P, &tok, TKkw_sizeof)) {
      ex.t = Eintlit;
      ex.ty = ty_usize;
      if (lexmatch(P, &tok, '(')) {
         struct expr exp = parseexpr(P);
         ex.i = exp.ty->size;
         lexexpect(P, ')');
      } else {
         const struct type *ty = parsetype(P);
         ex.i = ty->size;
      }
   } else if (lexmatch(P, &tok, TKkw_alignof)) {
      ex.t = Eintlit;
      ex.ty = ty_usize;
      if (lexmatch(P, &tok, '(')) {
         struct expr exp = parseexpr(P);
         ex.i = exp.ty->align;
         lexexpect(P, ')');
      } else {
         const struct type *ty = parsetype(P);
         ex.i = ty->align;
      }
   } else if (lexmatch(P, &tok, TKkw_offsetof)) {
      lexexpect(P, '(');
      const struct type *ty = parsetype(P);
      lexexpect(P, ',');
      size_t off = 0;
      for (;;) {
         const char *name = (tok = lexexpect(P, TKident)).str;
         struct aggfield *fld = findaggfield(ty, name);
         if (!fld) {
            fatal(P, tok.span, "%t has no such field %T", ty, tok);
         }
         off += fld->off;
         ty = fld->ty;
         if (!lexmatch(P, &tok, '.')) {
            lexmatch(P, &tok, ',');
            lexexpect(P, ')');
            break;
         }
      }
      ex.t = Eintlit;
      ex.ty = ty_usize;
      ex.u = off;

   } else {
      experr:
      fatal(P, tok.span, "expected expression (near %s)", tok2str(tok));
   }

   P->targty = NULL;
   return ex;
}

static struct expr
pexpostfix(struct parser *P) {
   struct expr ex = pexprimary(P);
   struct tok tok;
   struct fn *met = NULL;

   if (P->used_targty) return ex;

   for (;;) if (lexmatch(P, &tok, '(')) {
      vec_t(struct expr) args = {0};
      const struct type *ty = ex.ty;
      int i = 0;

      if (met) {
         ++i;
         ty = met->selfty = fntype(met);
         vec_push(&args, ex);
      }

      if (ty->t == TYptr)
         ty = ty->child;

      if (ty->t != TYfn)
         fatal(P, ex.span, "callee is not a function (is %t)", ty);
      while (!lexmatch(P, NULL, ')')) {
         int n = ty->fn.params.n;
         struct expr arg;
         const struct type **pty = &ty->fn.params.d[i];
         
         if (i == n && ! ty->fn.variadic)
            fatal(P, arg.span, "too many args for call: (expected %d)", n);
         if (i < n)
            P->targty = ty->fn.params.d[i];
         arg = parseexpr(P);
         if (i < n && !typematchestarg(*pty, arg.ty))
            fatal(P, arg.span,
                  "call argument #%d type mismatch (%t, expected %t)",
                  i, arg.ty, ty->fn.params.d[i]);
         if (i >= n && (arg.ty->t == TYstruct || arg.ty->t == TYunion || arg.ty->t == TYeunion || arg.ty->t == TYslice)) {
            fatal(P, arg.span, "cannot pass aggregate value as variadic argument");
         }

         ++i;
         vec_push(&args, arg);
         if (!lexmatch(P, NULL, ',')) {
            lexexpect(P, ')');
            break;
         }
      }
      if (met) {
         ex.t = Emcall;
         ex.mcall.met = met;
         ex.ty = ty->fn.retty;
         vec_slice_cpy(&ex.mcall.args, &args);
      } else {
         ex.call.callee = exprdup(ex);
         ex.t = Ecall;
         ex.span = tok.span;
         ex.ty = ty->fn.retty;
         vec_slice_cpy(&ex.call.args, &args);
      }
   } else if (lexmatch(P, &tok, '[')) {
      struct expr lhs = ex,
                  rhs = parseexpr(P),
                  *end = NULL;
      bool slice = 0;
      if (lhs.ty->t != TYarr && lhs.ty->t != TYptr && lhs.ty->t != TYslice)
         fatal(P, lhs.span, "indexee is not array or pointer type (%t)",
               lhs.ty);
      if (rhs.ty->t != TYint && !(rhs.ty->t == TYenum && rhs.ty->enu.lax))
         fatal(P, lhs.span, "index expression type is not integral (%t)",
               rhs.ty);
      if (lexmatch(P, NULL, '::')) {
         slice = 1;
         if (!lexmatch(P, NULL, ']')) {
            end = exprdup(parseexpr(P));
            if (end->ty->t != TYint)
               fatal(P, lhs.span,
                     "slice range end expression type is not integral (%t)", end->ty);
            lexexpect(P, ']');
         } else if (lhs.ty->t == TYarr) {
            end = exprdup((struct expr) {
               Eintlit, .ty = ty_usize, .i = lhs.ty->length
            });
         } else {
            fatal(P, tok.span, "missing end of slice range");
         }
      } else {
         lexexpect(P, ']');
      }
      if (slice) {
         ex.t = Eslice;
         ex.span = tok.span;
         ex.ty = mkslicetype(lhs.ty->child);
         ex.slice.lhs = exprdup(lhs);
         ex.slice.start = exprdup(rhs);
         ex.slice.end = end;
      } else {
         ex.t = Eindex;
         ex.span = tok.span;
         ex.ty = lhs.ty->child;
         ex.index.lhs = exprdup(lhs);
         ex.index.rhs = exprdup(rhs);
      }
   } else if (lexmatch(P, &tok, '++') || lexmatch(P, &tok, '--')) {
      if (!isnumtype(ex.ty) && ex.ty->t != TYptr)
         fatal(P, ex.span, "invalid %t operand to postfix operator %T: not numeric",
               ex.ty, tok);
      if (!islvalue(&ex))
         fatal(P, ex.span, "left operand to postfix %T operator is not lvalue",
               tok);
      if (ex.ty->konst)
         fatal(P, ex.span, "left operand to postfix %T operator is const",
               tok);
      ex = (struct expr) {
         Epostfix, tok.span, ex.ty, .unop = {
            tok.t, exprdup(ex)
         }
      };
   } else if (lexmatch(P, &tok, '.')) {
      if (lexmatch(P, &tok, '#len')) {
         const struct type *ty = ex.ty;
         if (ty->t == TYptr)
            ty = ty->child;
         if (ty->t == TYarr) {
            assert(ty->length >= 0);
            ex.t = Eintlit;
            ex.ty = ty->konst ? constify(ty_isize) : ty_isize;
            ex.span = tok.span;
            ex.i = ty->length;
         } else if (ty->t == TYslice) {
            ex.child = exprdup(ex);
            ex.t = Elen;
            ex.ty = ty->konst ? constify(ty_isize) : ty_isize;
            ex.span = tok.span;
         } else {
            fatal(P, ex.span, "invalid operand to `.#len' (%t)", ex.ty);
         }
      } else if (lexmatch(P, &tok, '#ptr')) {
         const struct type *ty = ex.ty;
         const struct expr lhs = ex;
         bool ptr = 0;
         if (ty->t == TYptr) {
            ty = ty->child;
            ptr = 1;
         }
         if (ty->t == TYarr) {
            ex.ty = interntype((struct type) {
               TYptr, g_targ.ptrsize, .child = ty->child
            });
            ex.span = tok.span;
            if (ptr) {
               ex.t = Eprefix;
               ex.unop.op = '*';
               ex.unop.child = exprdup(lhs);
            }
         } else if (ty->t == TYslice) {
            ex.ty = interntype((struct type) {
               TYptr, g_targ.ptrsize, .child = ty->child
            });
            ex = (struct expr) {
               Eptr, tok.span, ex.ty, .child = exprdup(lhs)
            };
         } else {
            fatal(P, ex.span, "invalid operand to `.#ptr' (%t)", ex.ty);
         }
      } else if (lexmatch (P, &tok, '#tag')) {
         const struct type *ty = ex.ty;
         if (ty->t == TYptr)
            ty = ty->child;
         if (ty->t != TYeunion)
            fatal(P, ex.span, "invalid operand to `.#tag' (%t)", ex.ty);
         ex.child = exprdup(ex);
         ex.t = Eeutag;
         ex.ty = ty->konst ? constify(ty->agg.enumty) : ty->agg.enumty;
         ex.span = tok.span;
      } else {
         const char *fnam = (tok = lexexpect(P, TKident)).str;
         const struct type *ty = ex.ty;
         if (ty->t == TYptr)
            ty = ty->child;
         bool konst = ty->konst;
         ty = unconstify(ty);
         if (ty->t == TYstruct || ty->t == TYunion || ty->t == TYeunion) {
            int idx = aggfldnam2idx(ty, fnam);
            struct aggfield *fld = &ty->agg.flds.d[idx];
            if (idx < 0)
               fatal(P, tok.span, "%t has no such field `%s'", ty, fnam);
            if (!fld->ty)
               fatal(P, tok.span, "%t variant `%s' is empty", ty, fnam);
            
            ex.get.lhs = exprdup(ex);
            ex.t = Eget;
            ex.span = tok.span;
            ex.ty = konst ? constify(fld->ty) : fld->ty;
            ex.get.fld = fnam;
         } else {
            fatal(P, tok.span, "cannot access `%s': left-hand-side is not an aggregate (%t)",
                  fnam, ex.ty);
         }
      }
   } else if (lexmatch(P, &tok, '->')) {
      const char *fnam = (tok = lexexpect(P, TKident)).str;
      const struct type *ty = ex.ty;
      bool exptr = 0, metptr = 0;

      if ((exptr = ty->t == TYptr))
         ty = ty->child;
      if (ty->t == TYstruct || ty->t == TYunion || ty->t == TYeunion) {
         struct decl *decl = findaggdecl(unconstify(ty), fnam);
         if (!decl)
            fatal(P, tok.span, "%t has no such method `%s'", ty, fnam);
         if (decl->t != Dfn)
            fatal(P, tok.span, "%t:%bs is not a function", ty, fnam);
         met = &decl->fn;
         if (met->params.n == 0)
            fatal(P, tok.span,
                  "cannot call `->%s', it takes zero arguments",
                  fnam);

         const struct type *recv0 = met->params.d[0].ty,
                           *recv = recv0;
         if ((metptr = recv->t == TYptr))
            recv = recv->child;
         if (unconstify(ty) != unconstify(recv))
            fatal(P, tok.span,
                  "method receiver type mismatch for `->%s' (%t vs %t)",
                  fnam, ty, recv);
         if (!exptr && !metptr) {
            ;
         } else if (exptr && !metptr) {
            ex = (struct expr) {
               Eprefix, ex.span, ty, .unop = { '*', exprdup(ex) }
            };
         } else if (!exptr && metptr) {
            struct type pty = {TYptr, g_targ.ptrsize, 0, 0, .child = ty};
            if (!islvalue(&ex))
               fatal(P, tok.span, "cannot call `->%s' by reference: left-hand-side is not"
                     "an lvalue", fnam);
            else if (ty->konst && !recv->konst)
               fatal(P, tok.span, "constness mismatch: method takes %t but subject is %t",
                     recv0, ex.ty);
            ex = (struct expr) {
               Eprefix, ex.span, interntype(pty), .unop = { '&', exprdup(ex) }
            };
         } else if (exptr && metptr) {
            if (ty->konst && !recv->konst)
               fatal(P, tok.span, "constness mismatch: method takes %t but subject is %t",
                     recv0, ex.ty);
         }

         if (lexpeek(P).t != '(')
            lexexpect(P, '(');
      } else if (ex.ty->t == TYvalist) {
         if (!strcmp(fnam, "start")) {
            lexexpect(P, '(');
            struct expr ex2 = parseexpr(P);
            lexexpect(P, ')');
            ex = (struct expr) {
               Evastart, ex.span, ty_void,
                  .binop.lhs = exprdup(ex),
                  .binop.rhs = exprdup(ex2)
            };
         } else if (!strcmp(fnam, "arg")) {
            lexexpect(P, '(');
            ty = parsetype(P);
            lexexpect(P, ')');
            ex = (struct expr) {
               Evaarg, ex.span, ty, .child = exprdup(ex)
            };
         } else if (!strcmp(fnam, "end")) {
            lexexpect(P, '(');
            lexexpect(P, ')');
            ex = (struct expr) {
               Evaend, ex.span, ty_void, .child = exprdup(ex)
            };
         } else goto badmet;
      } else {
      badmet:
         fatal(P, tok.span, "cannot call `->%s': left-hand-side is not an aggregate (%t)",
               fnam, ex.ty);
      }
   } else {
      P->used_targty = 0;
      break;
   }

   return ex;
}

static struct expr
pexprefix(struct parser *P) {
   struct tok tok;

   if (lexmatch(P, &tok, '-') || lexmatch(P, &tok, '~')) {
      struct expr ex = pexprefix(P);
      const struct type *ty = numpromote(ex.ty);
      
      if (!ty)
         fatal(P, ex.span, "invalid %t operand to unary operator %T: not numeric",
               ex.ty, tok);
      if (ty->t != TYint && tok.t == '~')
         fatal(P, ex.span, "invalid %t operand to unary operator %T: not integral",
               ty, tok);
      return (struct expr) {
         Eprefix, tok.span, ty, .unop = {
            tok.t, exprdup(ex)
         }
      };
   } else if (lexmatch(P, &tok, '++') || lexmatch(P, &tok, '--')) {
      struct expr ex = pexprefix(P);
      
      if (!isnumtype(ex.ty) && ex.ty->t != TYptr)
         fatal(P, ex.span, "invalid %t operand to unary operator %T: not numeric",
               ex.ty, tok);
      if (!islvalue(&ex))
         fatal(P, ex.span, "left operand to prefix %T operator is not lvalue",
               ex.ty, tok);
      if (ex.ty->konst)
         fatal(P, ex.span, "left operand to prefix %T operator is const",
               ex.ty, tok);
      return (struct expr) {
         Eprefix, tok.span, ex.ty, .unop = {
            tok.t, exprdup(ex)
         }
      };
   } else if (lexmatch(P, &tok, '!')) {
      struct expr ex = pexprefix(P);

      if (ex.ty->t != TYbool)
         fatal(P, ex.span, "invalid %t operand to unary operator %T: not boolean",
               ex.ty, tok);
      return (struct expr) {
         Eprefix, tok.span, ty_bool, .unop = {
            '!', exprdup(ex)
         }
      };
   } else if (lexmatch(P, &tok, '*')) {
      struct expr ex = pexprefix(P);
      if (ex.ty->t != TYptr)
         fatal(P, ex.span, "invalid %t operand to dereference, not pointer", ex.ty);
      if (!completetype(ex.ty->child) && ex.ty->child->t != TYfn)
         fatal(P, ex.span, "invalid %t operand to dereference, incomplete");
      return (struct expr) {
         Eprefix, tok.span, ex.ty->child, .unop = {
            '*', exprdup(ex)
         }
      };
   } else if (lexmatch(P, &tok, '&')) {
      struct expr ex = pexprefix(P);
      struct type ty2 = { TYptr, g_targ.ptrsize, .child = ex.ty};
      if (!islvalue(&ex) && !(ex.t == Ename && ex.ref->t == Dfn) && !(ex.t == Ezeroini || ex.t == Eini))
         fatal(P, ex.span, "invalid operand to `&': not an lvalue");
      return (struct expr) {
         Eprefix, tok.span, interntype(ty2), .unop = {
            '&', exprdup(ex)
         }
      };
   } else if (lexmatch(P, &tok, TKkw_as)) {
      const struct type *to, *from;
      struct expr ex;
      lexexpect(P, '(');
      to = parsetype(P);
      lexexpect(P, ')');
      P->targty = to;
      ex = pexprefix(P);
      from = ex.ty;

      if (to->t == TYarr && to->length < 0 && ex.t == Eini) {
         ex.ty = to = mkarraytype(to->child, ex.ini.maxn + 1);
      }
      else if (typeof2(to, from)) ;
      else if (to->t == TYint && from->t == TYptr && to->size == from->size) ;
      else if (from->t == TYint && to->t == TYptr && to->size == from->size) ;
      else if (from->t == TYptr && to->t == TYptr) ;
      else if (from->t == TYbool && to->t == TYint) ;
      else if (from->t == TYint && to->t == TYbool) ;
      else if (from->t == TYenum && to->t == TYint) ;
      else if (from->t == TYint && to->t == TYenum) ;
      else
         fatal(P, tok.span, "invalid cast from %t to %t", from, to);

      P->targty = to;
      return (struct expr) {
         Eas, tok.span, to, .child = exprdup(ex)
      };
   }

   return pexpostfix(P);
}

static bool
peeksbitarithop(struct parser *P, struct tok* tokp) {
   struct tok tok = lexpeek(P);

   if (tokp)
      *tokp = tok;
   switch (tok.t) {
   case '+': case '-': case '*': case '/':
      return 1;
    case '%': case '&': case '|':
    case '^': case '<<': case '>>': 
      return 2;   
   case '##':
      return 3;
   }
   return 0;
}

static struct expr
pexbitarith(struct parser *P) {
   struct expr ex;
   struct tok tok;
   int tokt;
   int oret;

   ex = pexprefix(P);
   if (P->used_targty) return ex;
   if (!(oret = peeksbitarithop(P, &tok)))
      return ex;
   tokt = tok.t;
   
   while (lexmatch(P, &tok, tokt)) {
      struct expr rhs = pexprefix(P);
      const struct type *ty = typeof2(ex.ty, rhs.ty);
      if (!ty) {
         if ((tokt == '+' || tokt == '-')
          && ((ex.ty->t == TYptr && rhs.ty->t == TYint)
           || (ex.ty->t == TYint && rhs.ty->t == TYptr)))
         {
            ty = ex.ty->t == TYptr ? ex.ty : rhs.ty;
         } else {
            goto err;
         }
      } else if (tokt == '-' && ex.ty->t == TYptr && rhs.ty->t == TYptr) {
         ty = ty_isize;
      } else if (tokt != '##' && !isnumtype(ty)) {
         err:
         fatal(P, tok.span, "invalid operands %t and %t to binary operator %k",
               ex.ty, rhs.ty, tokt);
      }
      if (oret == 2 && ty->t == TYfloat)
         fatal(P, tok.span,
               "invalid operands %t and %t to bitwise operator %k: not integral",
               ex.ty, rhs.ty, tokt);
      if (tokt != '##') {
         ex = (struct expr) {
            Ebinop, tok.span, ty, .binop = {
               tokt, exprdup(ex), exprdup(rhs)
            }
         };
      } else {
         char *s;
         size_t n = ex.strlit.n + rhs.strlit.n;

         /// TODO fold
         if (ex.t != Estrlit || rhs.t != Estrlit)
            fatal(P, tok.span,
                  "operands to `##' operator are not string literals");
         s = xmalloc(n + 1);
         memcpy(s, ex.strlit.d, ex.strlit.n);
         memcpy(s + ex.strlit.n, rhs.strlit.d, rhs.strlit.n + 1);
         ex = (struct expr) {
            Estrlit, tok.span, mkarraytype(constify(ty_u8), n + 1),
            .strlit.d = s, .strlit.n = n,
         };
      }

   }

   return ex;
}

static bool
matchcmpop(struct parser *P, struct tok *tokp) {
   struct tok tok = lexpeek(P);

   if (tokp)
      *tokp = tok;
   switch (tok.t) {
   case '==': case '<=': case '>=':
   case '<': case '>': case '!=':
      lex(P);
      return 1;   
   }
   return 0;
}

static struct expr
pexcmp(struct parser *P) {
   struct expr ex;
   struct tok tok;

   ex = pexbitarith(P);
   if (P->used_targty) return ex;
   if (matchcmpop(P, &tok)) {
      P->targty = ex.ty;
      struct expr rhs = pexbitarith(P);
      P->used_targty = 0;
      P->targty = NULL;
      if (!typeof2(ex.ty, rhs.ty))
         fatal(P, tok.span, "incompatible operands %t and %t to binary operator %T",
               ex.ty, rhs.ty, tok);
      if (tok.t != '==' && tok.t != '!=' && !isnumtype(typeof2(ex.ty, rhs.ty)))
         fatal(P, tok.span,
               "invalid operands %t and %t to relational operator %T: not numeric",
               ex.ty, rhs.ty, tok);
      ex = (struct expr) {
         Ebinop, tok.span, ty_bool, .binop = {
            tok.t, exprdup(ex), exprdup(rhs)
         }
      };
   }
   return ex;
}

static struct expr
pexlog(struct parser *P) {
   struct expr ex;
   struct tok tok;
   int tokt;

   ex = pexcmp(P);
   if (P->used_targty) return ex;
   tok = lexpeek(P);
   tokt = tok.t;
   if (tokt != TKkw_and && tokt != TKkw_or && tokt != '?\?')
      return ex;
   
   while (lexmatch(P, &tok, tokt)) {
      struct expr rhs = pexcmp(P);
      if (tokt == '?\?') {
         const struct type *ty = typeof2(ex.ty, rhs.ty);
         if (!(ex.ty->t == TYptr || rhs.ty->t == TYptr) || !ty)
            fatal(P, tok.span,
                  "invalid operands %t and %t to binary operator %k",
               ex.ty, rhs.ty, tok.t);
         ex = (struct expr) {
            Ebinop, tok.span, ty, .binop = {
               '?\?', exprdup(ex), exprdup(rhs)
            }
         };
      } else {
         if (ex.ty->t != TYbool || rhs.ty->t != TYbool)
            fatal(P, tok.span,
                  "invalid operands %t and %t to binary operator %k",
               ex.ty, rhs.ty, tok.t);
         ex = (struct expr) {
            Ebinop, tok.span, ty_bool, .binop = {
               tokt == TKkw_and ? 'and' : 'or', exprdup(ex), exprdup(rhs)
            }
         };
      }

   }

   return ex;
}

static struct expr
pexcond(struct parser *P) {
   struct expr ex;
   struct tok tok;
   const struct type *targty = P->targty;

   ex = pexlog(P);
   if (P->used_targty) return ex;
   if (lexmatch(P, &tok, '?')) {
      P->targty = targty;
      struct expr ex2 = parseexpr(P);
      struct expr ex3;
      const struct type *ty;

      if (ex.ty->t != TYbool && ex.ty->t != TYptr)
         fatal(P, ex.span, "invalid test operand %t to conditional operator", ex.ty);

      lexexpect(P, ':');
      P->targty = targty;
      ex3 = pexcond(P);
      if (!(ty = typeof2(ex2.ty, ex3.ty)))
         fatal(P, tok.span,
               "conditional operator branches have incompatible types %t and %t",
               ex2.ty, ex3.ty);
      ex = (struct expr) {
         Econd, tok.span, ty, .cond = {
            exprdup(ex), exprdup(ex2), exprdup(ex3)
         }
      };
   }
   return ex;
}

static int
matchassignop(struct parser *P, struct tok *tokp) {
   struct tok tok = lexpeek(P);
   if (tokp)
      *tokp = tok;
   switch (tok.t) {
   case '=':
      lex(P);
      return 1;
   case '+=': case '-=': case '*=': case '/=': 
      lex(P);
      return 2;
   case '%=': case '&=': case '|=': case '^=': case '<<=': case '>>=':
      lex(P);
      return 3;   
   }
   return 0;
}

static struct expr
pexassign(struct parser *P) {
   struct expr ex;
   struct tok tok;
   int oret;

   ex = pexcond(P);
   if (P->used_targty) return ex;
   if ((oret = matchassignop(P, &tok))) {
      struct expr rhs;
      if (oret == 1)
         P->targty = ex.ty;
      rhs = pexcond(P);
      if (!islvalue(&ex))
         fatal(P, ex.span,
               "left operand to assignment operator %T is not an lvalue",
               tok);
      if (!typeof2(ex.ty, rhs.ty)
        && !(ex.ty->t == TYptr && rhs.ty->t == TYint
           && (tok.t == '+=' || tok.t == '-=')))
         fatal(P, ex.span,
               "operands %t and %t to assignment operator %T have incompatible types",
               ex.ty, rhs.ty, tok);
      if (ex.ty->konst)
         fatal(P, ex.span,
               "left operand to assignment operator %T is const",
               tok);
      ex = (struct expr) {
         Ebinop, tok.span, ex.ty, .binop = {
            tok.t, exprdup(ex), exprdup(rhs)
         }
      };
   }

   return ex;
}

static struct expr
parseexpr(struct parser *P) {
   return pexassign(P);
}

/** Statements and declarations parsing  **/

static struct stmt *
stmtdup(struct stmt st) {
   return memcpy(xmalloc(sizeof st), &st, sizeof st);
}

typedef void (*decl_yielder_t)(struct decl *, void *);
static void parsedecl(decl_yielder_t, void *, struct parser *, bool toplevel);

static void
parsevardecl(decl_yielder_t yield, void *yarg, struct parser *P, bool let, bool externp) {
   struct tok tok;
   
   do {
      struct decl decl = {0};
      const char *name;
      const struct type *ty = NULL;
      struct expr *ini = NULL;
      bool konst = 0;

      if (lexmatch(P, NULL, TKkw_const))
         konst = 1;

      tok = lexexpect(P, TKident);
      name = tok.str;

      if (lexmatch(P, NULL, '=')) {
         ini = exprdup(parseexpr(P));
         ty = unconstify(ini->ty);
      } else {
         ty = parsetype(P);
         if (lexmatch(P, NULL, '=')) {
            P->targty = ty;
            ini = exprdup(parseexpr(P));
         } else if (let && lexmatch(P, NULL, '#?')) {
            ini = NULL;
         } else if (decl.t == Dlet) {
            fatal(P, tok.span, "variable %T must be initialized", tok);
         }
      }

      // TODO static initialzier constants are a superset of folded constants
      // if (ini && decl.t == Dstatic && !fold(ini))
      //   fatal(P, ini->span, "static initializer isn't constant");

      if (ini && !typematchestarg(ty, ini->ty))
         fatal(P, tok.span, "incompatible initializer type (%t, expected %t)",
               ini->ty, ty);

      if (ini && ty->t == TYarr && ty->length < 0) {
         struct type ty2 = *ty;
         if (ini->t == Ezeroini) {
            ty2.length = 0;
         } else if (ini->t == Eini) {
            ty2.length = ini->ini.maxn + 1;
         } else {
            fatal(P, ini->span,
                  "initializer of inferred-length array must be compound literal");
         }
         ty2.size = ty->child->size * ty2.length;
         ty2.align = ty->child->align;
         uninterntype(ty);
         ty = ini->ty = interntype(ty2);
      }

      if (!completetype(ty) && !(!let && externp))
         fatal(P, tok.span, "%s `%s': variable type %t is incomplete",
               let ? "let" : "static", name, ty);

      if (konst)
         ty = constify(ty);

      assert(ty);
      decl.name = name;
      decl.span = tok.span;
      decl.var.ty = ty;
      decl.var.ini = ini;
      decl.var.id = P->varid++;
      decl.var.fnid = P->curfn ? P->curfn->id : -1;
      yield(memcpy(xmalloc(sizeof decl), &decl, sizeof decl), yarg);
      if (!lexmatch(P, &tok, ',')) {
         lexexpect(P, ';');
         break;
      }
   } while (!lexmatch(P, &tok, ';'));
}

typedef void (*stmt_yielder_t)(struct stmt *, void *);

struct letstmtyarg {
   struct parser *P;
   void *stmt_yarg;
   stmt_yielder_t yield;
};

static void
letstmtyield(struct decl *decl, void *arg) {
   struct letstmtyarg *a = arg;
   struct stmt st = { Sdecl };
   decl->t = Dlet;
   putdecl(a->P, decl->span, decl);
   st.decl = *decl;
   st.span = decl->span;
   a->yield(&st, a->stmt_yarg);
}

static void
pstlet(stmt_yielder_t yield, void *yarg, struct parser *P) {
   struct letstmtyarg arg = {
      P, yarg, yield
   };
   parsevardecl(letstmtyield, &arg, P, 1, 0);
}

static struct stmt
pstifelse(struct parser *P) {
   struct stmt st = {Sifelse};

   st.ifelse.test = parseexpr(P);
   if (st.ifelse.test.ty->t != TYbool && st.ifelse.test.ty->t != TYptr)
      fatal(P, st.ifelse.test.span,
            "if statement condition must be bool or pointer (%t)",
            st.ifelse.test.ty);
   lexexpect(P, '{');
   st.ifelse.t = parseblock(P).block;
   if (lexmatch(P, NULL, TKkw_else)) {
      if (lexmatch(P, NULL, TKkw_if))
         st.ifelse.f = stmtdup(pstifelse(P));
      else {
         lexexpect(P, '{');
         st.ifelse.f = stmtdup(parseblock(P));
      }
   }

   return st;
}

static void
pstforletyield(struct stmt *st, void *arg) {
   vec_t(struct stmt) *sts = arg;
   vec_push(sts, *st);
}

static struct stmt
pstfor(struct parser *P, const char *label) {
   struct stmt st = {Sfor};
   struct tok tok;

   if (lexmatch(P, NULL, TKkw_let)) {
      vec_t(struct stmt) sts = {0};
      pstlet(pstforletyield, &sts, P);
      vec_slice_cpy(&st.loop.ini, &sts);
   } else if (lexmatch(P, NULL, ';')) {
      // pass
   } else {
      st.loop.ini.d = stmtdup((struct stmt) {
         Sexpr, .expr = parseexpr(P)
      });
      st.loop.ini.n = 1;
      lexexpect(P, ';');
   }

   if (lexmatch(P, &tok, ';')) {
      // for (...; ; ...;) -> for (...; #t; ...;)
      st.loop.test = (struct expr) { Eboolit, tok.span, ty_bool, .i = 1 };
   } else {
      st.loop.test = parseexpr(P);
      lexexpect(P, ';');
   }

   if (st.loop.test.ty->t != TYbool && st.loop.test.ty->t != TYptr)
      fatal(P, st.loop.test.span,
            "for statement condition must be bool or pointer (%t)",
            st.loop.test.ty);

   if (!lexmatch(P, &tok, '{')) {
      st.loop.next = exprdup(parseexpr(P));
      lexexpect(P, '{');
   }
   st.loop.id = P->loopid++;
   struct env env = {P->curenv};
   if (label) {
      pushenv(P, &env);
      putdecl(P, tok.span, &(struct decl) { Dlabel, label, .loopid = st.loop.id });
   }
   WITH_TMPCHANGE(int, P->curloop, st.loop.id)
      st.loop.body = parseblock(P).block;
   if (label) {
      free(env.decls);
      popenv(P);
   }
   return st;
}

static void parsestmt(stmt_yielder_t yield, void *yarg, struct parser *P);

static struct stmt
pstiswitch(struct parser *P, const struct expr *test) {
   struct stmt st = {Siswitch};
   struct tok tok;
   vec_t(struct iswitchcase) cs = {0};
   struct blockstmt *f = NULL;

   lexexpect(P, '{');
   while (!lexmatch(P, &tok, '}')) {
      struct iswitchcase c;
      vec_t(struct expr) es = {0};
      
      lexexpect(P, TKkw_case);

      if (lexmatch(P, &tok, TKkw_else)) {
         if (f)
            fatal(P, tok.span, "duplicate 'case else' block");
         f = malloc(sizeof *f);
         *f = parseblock0(P);
      } else {
         do {
            struct expr ex;
            P->targty = test->ty;
            ex = parseexpr(P);
            if (!fold(&ex))
               fatal(P, ex.span, "case expression is not constant");
            if (!typeof2(ex.ty, test->ty))
               fatal(P, ex.span, "case expression has incorrect type (%t, expected %t)",
                     ex.ty, test->ty);
            vec_push(&es, ex);
            if (!lexmatch(P, &tok, ',')) {
               lexexpect(P, ';');
               break;
            }
         } while (!lexmatch(P, &tok, ';')) ;
         vec_slice_cpy(&c.es, &es);
         c.t = parseblock0(P);
         vec_push(&cs, c);
      }
   }
   
   st.iswitch.test = *test;
   vec_slice_cpy(&st.iswitch.cs, &cs);
   st.iswitch.f = f;
   return st;
}

static struct stmt
psteuswitch(struct parser *P, const struct expr *test) {
   struct stmt st = {Seuswitch};
   struct tok tok;
   vec_t(struct euswitchcase) cs = {0};
   struct blockstmt *f = NULL;

   lexexpect(P, '{');
   while (!lexmatch(P, &tok, '}')) {
      struct euswitchcase c = {0};
      
      lexexpect(P, TKkw_case);

      if (lexmatch(P, &tok, TKkw_else)) {
         if (f)
            fatal(P, tok.span, "duplicate 'case else' block");
         f = malloc(sizeof *f);
         *f = parseblock0(P);
      } else {
         const char *vname = (tok = lexexpect(P, TKident)).str;
         c.fld = findaggfield(test->ty, vname);
         c.vval = c.fld - test->ty->agg.flds.d;
         if (!c.fld)
            fatal(P, tok.span, "%t has no such variant %T", test->ty, tok);
         if (c.fld->ty && lexmatch(P, &tok, '*')) {
            if (!islvalue(test)) {
               fatal(P, tok.span, "cannot capture by pointer, test expression is not lvalue");
            }
            c.captptr = 1;
            st.euswitch.byptr = 1;
            if (lexpeek(P).t != TKident)
               lexexpect(P, TKident);
         }
         struct env env = {P->curenv};
         if (c.fld->ty && lexmatch(P, &tok, TKident)) {
            const struct type *ty = c.fld->ty;

            c.capt = tok.str;
            if (c.captptr) {
               ty = interntype((struct type) {
                  TYptr, g_targ.ptrsize, .child = test->ty->konst ? constify(ty) : ty
               });
            }
            pushenv(P, &env);
            putdecl(P, tok.span, &(struct decl) {
               Dlet, c.capt, .span = tok.span, .var = {
                  c.captty = ty, NULL, c.captid = P->varid++, P->curfn->id
               }
            });
         }
         lexexpect(P, ';');
         c.t = parseblock0(P);
         if (c.capt)
            popenv(P);
         vec_push(&cs, c);
      }
   }
   
   st.iswitch.test = *test;
   vec_slice_cpy(&st.euswitch.cs, &cs);
   st.iswitch.f = f;
   return st;
}

static struct stmt
pstcswitch(struct parser *P) {
   struct stmt st = {Scswitch};
   struct tok tok;
   vec_t(struct cswitchcase) cs = {0};
   struct blockstmt *f = NULL;

   while (!lexmatch(P, &tok, '}')) {
      struct cswitchcase c = {0};
      
      lexexpect(P, TKkw_case);

      if (lexmatch(P, &tok, TKkw_else)) {
         if (f)
            fatal(P, tok.span, "duplicate 'case else' block");
         f = malloc(sizeof *f);
         *f = parseblock0(P);
      } else {
         c.test = parseexpr(P);
         lexexpect(P, ';');
         c.t = parseblock0(P);
         vec_push(&cs, c);
      }
   }
   
   vec_slice_cpy(&st.cswitch.cs, &cs);
   st.cswitch.f = f;
   return st;

}

static struct stmt
pstswitch(struct parser *P) {
   struct tok tok;
   struct expr test;

   if (!lexmatch(P, &tok, '{')) {
      test = parseexpr(P);
      if (test.ty->t == TYint || test.ty->t == TYenum)
         return pstiswitch(P, &test);
      else if (test.ty->t == TYeunion)
         return psteuswitch(P, &test);
      else
         fatal(P, test.span, "bad switch test expression (%t)", test.ty);
   } else {
      return pstcswitch(P);
   }
}

static bool
isdecltokt(int tokt) {
   switch (tokt)
   case TKkw_extern: case TKkw_fn: case TKkw_typedef:
   case TKkw_defmacro: case TKkw_static: case TKkw_enum:
   case TKkw_struct: case TKkw_union: case TKkw_def:
      return 1;
   return 0;
}

static void
mergetoktrees(struct toktree *dst, int n) {
   size_t total = 0;
   for (int i = 0; i < n; ++i) {
      total += dst[i].n;
      if (i > 0)
         ++total;
   }
   dst->d = xrealloc(dst->d, total * sizeof (struct tok));
   for (int i = 1; i < n; ++i) {
      dst->d[dst->n++] = (struct tok) { ',' };
      memcpy(dst->d + dst->n, dst[i].d, dst[i].n * sizeof (struct tok));
      dst->n += dst[i].n;
   }
   assert(dst->n == total);
}

static void
parseexpandmacro(struct parser *P, const struct macro *macro) {
   vec_t(struct toktree) args = {0};
   struct tok tok;
   struct expan expan = {0};
   struct expanarg *expanargs;
   struct macrocase c;

   expan.span = lexpeek(P).span;
   lexexpect(P, '(');
   while (!lexmatch(P, &tok, ')')) {
      int pabal = 0, // ( ) parens balance
          bkbal = 0, // [ ] brackets ..
          bcbal = 0; // { } braces ..
      struct span espan = tok.span;
      vec_t(struct tok) toks = {0};
      struct toktree ttoks;

      for (;;) { 
         tok = lex(P);
         switch (tok.t) {
         case '[': ++bkbal; break; case ']': --bkbal; break;
         case '{': ++bcbal; break; case '}': --bcbal; break;
         case '(': ++pabal; break;
         case ')':
            if (--pabal >= 0)
               break;
            goto arg_done;
         case ',':
            if (!pabal && !bkbal && !bcbal)
               goto arg_done;
            break;
         case TKeof:
            fatal(P, espan, "unterminated macro `%s' invokation", macro->name);
         }
         vec_push(&toks, tok);
      }
      arg_done:

      vec_slice_cpy(&ttoks, &toks);
      vec_push(&args, ttoks);

      if (tok.t != ',') {
         assert(tok.t == ')');
         break;
      }
   }
   if (lexpeek(P).t == '{') {
      for (int i = 0; i < macro->cs.n; ++i) {
         c = macro->cs.d[i];
         if (args.length == c.params.n - 1 && c.bodyarg) {
            goto bodyarg;
         }
      }
      goto not_bodyarg;
   bodyarg:;
      int bal = 0;
      struct span espan = tok.span;
      vec_t(struct tok) toks = {0};
      struct toktree ttoks;
      do {
         tok = lex(P);
         switch (tok.t) {
         case '{': ++bal; break; case '}': --bal; break;
         case TKeof:
            fatal(P, espan, "unterminated macro `%s' invokation", macro->name);
         }
         vec_push(&toks, tok);
      } while (bal != 0);

      vec_slice_cpy(&ttoks, &toks);
      vec_push(&args, ttoks);
      goto ok;
   }
   not_bodyarg:

   for (int i = 0; i < macro->cs.n; ++i) {
      c = macro->cs.d[i];
      if (!c.variadic && args.length == c.params.n) {
         goto ok;
      } else if (c.variadic && args.length >= c.params.n - 1) {
         int n = args.length - (c.params.n - 1);
         if (n == 0) {
            vec_push(&args, (struct toktree){0});
         } else {
            mergetoktrees(args.data + c.params.n - 1, n);
         }
         goto ok;
      }
   }
   fatal(P, tok.span, "no match for invoking macro `%s' with %d arguments",
         macro->name, args.length);
ok:
   expanargs = xcalloc(c.params.n, sizeof *expanargs);
   for (int i = 0; i < c.params.n; ++i) {
      expanargs[i].name = c.params.d[i];
      expanargs[i].toks = args.data[i];
   }
   expan.prev = P->curexpan;
   expan.name = macro->name;
   expan.args.d = expanargs;
   expan.args.n = c.params.n;
   expan.peektok = P->peektok;
   expan.have_peektok = P->have_peektok;
   P->have_peektok = 0;
   expan.toks = c.body;
   ++P->expanno;
   P->curexpan = memcpy(xmalloc(sizeof expan), &expan, sizeof expan);
}

static void
yieldstdecl(struct decl *d0, void *arg) {
   struct decl *decl = arg;
   *decl = *d0;
}

struct stmtletyarg {
   stmt_yielder_t yield;
   void *yarg;
};

static void
stmtletyield(struct stmt *stmt, void *arg) {
   struct stmtletyarg *a = arg;
   stmt->t = Sdecl;
   a->yield(stmt, a->yarg);
}

static void
parsestmt(stmt_yielder_t yield, void *yarg, struct parser *P) {
   struct stmt st = {0};
   struct tok tok;
   const char *label = NULL;
   static int deferage;

   if (lexmatch(P, &tok, '{')) {
      st.span = tok.span;
      st = parseblock(P);
   } else if (lexmatch(P, &tok, TKkw_let)) {
      pstlet(stmtletyield, &(struct stmtletyarg) { yield, yarg }, P);
      return;
   } else if (lexmatch(P, &tok, TKkw_if)) {
      st.span = tok.span;
      st = pstifelse(P);
   } else if (lexmatch(P, &tok, TKlabel)) {
      label = tok.str;
      if (lexmatch(P, &tok, TKkw_while))
         goto whilel;
      else if (lexmatch(P, &tok, TKkw_do))
         goto dowhilel;
      else if (lexmatch(P, &tok, TKkw_for))
         goto forl;
      else
         fatal(P, tok.span, "cannot use label for this statement");
   } else if (lexmatch(P, &tok, TKkw_while)) {
   whilel:
      st.t = Swhile;
      st.span = tok.span;
      st.loop.test = parseexpr(P);
      if (st.loop.test.ty->t != TYbool && st.loop.test.ty->t != TYptr)
         fatal(P, st.loop.test.span,
               "while statement condition must be bool or pointer (%t)",
               st.loop.test.ty);
      lexexpect(P, '{');
      st.loop.id = P->loopid++;
      struct env env = { P->curenv };
      if (label) {
         pushenv(P, &env);
         putdecl(P, tok.span, &(struct decl) { Dlabel, label, .loopid = st.loop.id });
      }
      WITH_TMPCHANGE(int, P->curloop, st.loop.id)
         st.loop.body = parseblock(P).block;
      if (label) {
         free(env.decls);
         popenv(P);
      }
   } else if (lexmatch(P, &tok, TKkw_do)) {
   dowhilel:
      st.t = Sdowhile;
      st.span = tok.span;
      lexexpect(P, '{');
      st.loop.id = P->loopid++;
      struct env env = { P->curenv };
      if (label) {
         pushenv(P, &env);
         putdecl(P, tok.span, &(struct decl) { Dlabel, label, .loopid = st.loop.id });
      }
      WITH_TMPCHANGE(int, P->curloop, st.loop.id)
         st.loop.body = parseblock(P).block;
      if (label) {
         free(env.decls);
         popenv(P);
      }
      lexexpect(P, TKkw_while);
      st.loop.test = parseexpr(P);
      if (st.loop.test.ty->t != TYbool && st.loop.test.ty->t != TYptr)
         fatal(P, st.loop.test.span,
               "do-while statement condition must be bool or pointer (%t)",
               st.loop.test.ty);
      lexexpect(P, ';');
   } else if (lexmatch(P, &tok, TKkw_for)) {
   forl:
      st.span = tok.span;
      st = pstfor(P, label);
   } else if (lexmatch(P, &tok, TKkw_switch)) {
      st = pstswitch(P);
      st.span = tok.span;
   } else if (lexmatch(P, &tok, TKkw_return)) {
      if (!P->curfn)
         fatal(P, tok.span, "return disallowed here");
      st.t = Sreturn;
      st.ret.deferage = deferage;
      st.span = tok.span;
      if (!lexmatch(P, &tok, ';')) {
         P->targty = P->curfn->retty;
         st.ret.ex = exprdup(parseexpr(P));
         lexexpect(P, ';');
         if (!typematchestarg(P->curfn->retty, st.ret.ex->ty))
            fatal(P, st.ret.ex->span,
                  "incompatible type in return statement (%t, expected %t)",
                  st.ret.ex->ty, P->curfn->retty);
      } else if (P->curfn->retty != ty_void) {
         fatal(P, tok.span,
               "return statement in non-void function must return a value");
      }
   } else if (lexmatch(P, &tok, TKkw_break)) {
      if (P->curloop < 0)
         fatal(P, tok.span, "break outside loop");
      st.t = Sbreak;
      st.brkcon.id = P->curloop;
      if (lexmatch(P, &tok, TKlabel)) {
         const struct decl *decl = finddecl(P, tok.str);
         if (!decl)
            fatal(P, tok.span, "no such label %T", tok);
         assert(decl->t == Dlabel);
         st.brkcon.id = decl->loopid;
      }
      lexexpect(P, ';');
   } else if (lexmatch(P, &tok, TKkw_continue)) {
      if (P->curloop < 0)
         fatal(P, tok.span, "continue outside loop");
      st.t = Scontinue;
      st.brkcon.id = P->curloop;
      if (lexmatch(P, &tok, TKlabel)) {
         const struct decl *decl = finddecl(P, tok.str);
         if (!decl)
            fatal(P, tok.span, "no such label %T", tok);
         assert(decl->t == Dlabel);
         st.brkcon.id = decl->loopid;
      }
      lexexpect(P, ';');
   } else if (lexmatch(P, &tok, TKkw_defer)) {
      struct expr ex = parseexpr(P);
      struct blockstmt *block = P->curblock;
      struct defer *defer = malloc(sizeof *defer);
      lexexpect(P, ';');
      assert(block != NULL && "defer outside block");
      defer->age = deferage++;
      defer->ex = ex;
      defer->blockid = P->curblock->id;
      defer->next = block->defers;
      block->defers = defer;
      st.t = Sblock;
      st.block = (struct blockstmt){0};
   } else if (isdecltokt((tok = lexpeek(P)).t)) {
      st.t = Sdecl;
      st.span = tok.span;
      parsedecl(yieldstdecl, &st.decl, P, 0);
      if (st.decl.t == Dfn && !st.decl.externp && !st.decl.fn.body)
         fatal(P, tok.span,
               "cannot forward-declare non-external function inside another function");

      if (st.decl.t == Dfn && st.decl.externp && st.decl.fn.body)
         fatal(P, tok.span,
               "cannot define external function inside another function");
   } else {
      struct expr ex;
      st.span = tok.span;
      
      if ((tok = lexpeek(P)).t == TKident) {
         const struct decl *decl;
         if ((decl = finddecl(P, tok.str)) && decl->t == Dmacro) {
            lex(P);
            parseexpandmacro(P, &decl->macro);
            return parsestmt(yield, yarg, P);
         }
      }

      ex = parseexpr(P);

      lexexpect(P, ';');
      st.t = Sexpr;
      st.expr = ex;
   }
   yield(&st, yarg);
}

static void
parseblockstyield(struct stmt *st, void *arg) {
   vec_t(struct stmt) *stmts = arg;
   vec_push(stmts, *st);
}

static struct blockstmt
parseblock0(struct parser *P) {
   vec_t(struct stmt) stmts = {0};
   struct blockstmt block = {0};
   int tokt;
   static int id;

   block.env.parent = P->curenv;
   pushenv(P, &block.env);
   block.defers = P->curblock ? P->curblock->defers : NULL;
   block.id = id++;
   WITH_TMPCHANGE(struct blockstmt *, P->curblock, &block) {
      while ((tokt = lexpeek(P).t) != '}' && tokt != TKkw_case && tokt != ')') {
         if (lexmatch(P, NULL, ';'))
            continue;
         parsestmt(parseblockstyield, &stmts, P);
      }
   }

   vec_slice_cpy(&block.stmts, &stmts);

   popenv(P);
   return block;
}

static struct stmt
parseblock(struct parser *P) {
   struct stmt st = { Sblock };
   st.block = parseblock0(P);
   lexexpect(P, '}');
   return st;
}

static void
parsefn(struct decl *decl, struct parser *P) {
   vec_t(struct fnparam) params = {0};
   struct tok tok;
   struct fn *fn = &decl->fn;
   const char *name = fn->name;
   static int id;

   memset(fn, 0, sizeof *fn);
   fn->name = name;

   lexexpect(P, '(');
   while (!lexmatch(P, &tok, ')')) {
      struct fnparam param = {0};
      if (lexmatch(P, &tok, '...')) {
         fn->variadic = 1;
      } else {
         if (lexmatch(P, &tok, TKident)) {
            if (lexpeek(P).t == ',' || lexpeek(P).t == ')') {
              param.ty = xident2type(P, tok); 
            } else {
               param.name = tok.str;
               param.ty = parsetype(P);
            }
         } else {
            param.ty = parsetype(P);
         }
         if (!completetype(param.ty))
            fatal(P, tok.span, "parameter type is incomplete (%t)",
                  param.ty);
         vec_push(&params, param);
      }
      if (!lexmatch(P, &tok, ',')) {
         lexexpect(P, ')');
         break;
      } else if (fn->variadic) {
         lexexpect(P, ')');
         break;
      }
   }
   vec_slice_cpy(&fn->params, &params);
   fn->retty = unconstify(parsetype(P));
   if (fn->retty != ty_void && !completetype(fn->retty)) {
      fatal(P, tok.span, "return type is incomplete (%t)",
            fn->retty);
   }
   fn->id = id++;
   if (!lexmatch(P, &tok, ';')) {
      struct env *env = xcalloc(1, sizeof *env);
      lexexpect(P, '{');
      env->parent = P->curenv;

      WITH_TMPCHANGE(struct blockstmt *, P->curblock, NULL) // do not inherit defers
      WITH_TMPCHANGE(struct fn *, P->curfn, fn) {
         pushenv(P, env);
         putdecl(P, tok.span, &(struct decl) {
            Dfn, fn->name, .fn = *fn, ._cname = decl->_cname
         });
         for (int i = 0; i < params.length; ++i) {
            if (!params.data[i].name)
               continue;
            struct decl decl = {
               Dlet, params.data[i].name, .var = {
                  .ty = params.data[i].ty,
                  .fnid = fn->id,
                  .id = -1,
               }
            };
            putdecl(P, tok.span, &decl);
         }
         fn->body = xcalloc(1, sizeof *fn->body);
         WITH_TMPCHANGE(int, P->curloop, -1) WITH_TMPCHANGE(int, P->loopid, 0)
            WITH_TMPCHANGE(int, P->varid, 0)
               *fn->body = parseblock(P);
         popenv(P);
      }
   }
   fn->selfty = fntype(fn);
}

static struct macrocase
parsemacrocase(struct parser *P) {
   struct macrocase c = {0};
   vec_t(const char *) params = {0};
   vec_t(struct tok) body = {0};
   struct tok tok;
   int pabal = 0, // ( ) parens balance
       bkbal = 1, // [ ] brackets ..
       bcbal = 0; // { } braces ..
   struct span espan;
   static int gensymid;
   struct gensyms {
      struct gensyms *next;
      const char *name;
      struct tok tok;
   } *gensyms = NULL;
   
   lexexpect(P, '(');
   while (!lexmatch(P, &tok, ')')) {
      if (lexmatch(P, &tok, '...')) {
         vec_push(&params, lexexpects(P, TKident, "parameter name").str);      
         c.variadic = 1;
         lexmatch(P, &tok, ',');
         lexexpect(P, ')');
         break;
      } else if (lexmatch(P, &tok, '&')) {
         vec_push(&params, lexexpects(P, TKident, "parameter name").str);      
         c.bodyarg = 1;
         lexmatch(P, &tok, ',');
         lexexpect(P, ')');
         break;
      } else {
         vec_push(&params, lexexpects(P, TKident, "parameter name").str);      
         if (!lexmatch(P, &tok, ',')) {
            lexexpect(P, ')');
            break;
         }
      }
   }

   espan = tok.span;

   lexexpect(P, '[');
   while (bkbal || pabal || bcbal) {
      tok = lex(P);
      switch (tok.t) {
      case '(': ++pabal; break; case ')': --pabal; break;
      case '[': ++bkbal; break; case ']': --bkbal; break;
      case '{': ++bcbal; break; case '}': --bcbal; break;
      case TKeof:
         fatal(P, espan, "unterminated macro definition");
      }
      if (tok.t == TKident) {
         for (int i = 0; i < params.length; ++i)
            if (!strcmp(params.data[i], tok.str))
               tok.t = TKmacident;
      } else if (tok.t == TKgensym) {
         struct gensyms *gs;
         for (gs = gensyms; gs; gs = gs->next) {
            if (!strcmp(gs->name, tok.str)) {
               tok = gs->tok;
               goto found;
            }
         }
         gs = xcalloc(1, sizeof *gs);
         gs->name = tok.str;
         gs->tok.t = TKident;
         gs->tok.span = tok.span;
         gs->tok.str = xasprintf("__fG%s_%d", tok.str, gensymid++);
         tok = gs->tok;
         gs->next = gensyms;
         gensyms = gs;
      }
      found:
      vec_push(&body, tok);
   }
   (void)vec_pop(&body);

   for (struct gensyms *gs = gensyms, *next; gs; gs = next) {
      next = gs->next;
      free((char *)gs->name);
      free(gs);
   }

   vec_slice_cpy(&c.params, &params);
   vec_slice_cpy(&c.body, &body);
   return c;
}

static struct macro
parsemacro(struct parser *P) {
   struct tok tok;
   struct macro macro;
   vec_t(struct macrocase) cs = {0};

   if (lexpeek(P).t == '(') {
      vec_push(&cs, parsemacrocase(P));      
   } else {
      lexexpect(P, '{');
      while (!lexmatch(P, &tok, '}')) {
         vec_push(&cs, parsemacrocase(P));      
         if (!lexmatch(P, &tok, ',')) {
            lexexpect(P, '}');
            break;
         }
      }
   }
   
   if (cs.length == 0)
      fatal(P, tok.span, "macro must have at least one case");

   vec_slice_cpy(&macro.cs, &cs);
   return macro;
}

static const struct type *
parseenum(struct parser *P, const char *name, struct attr attr) {
   struct tok tok;
   struct type ty = {TYenum};
   static int id = 0;
   i64 iota = 0, max = 0, min = 0;
   vec_t(struct enumval) vals = {0};
   ty.enu.lax = attr.lax;

   if (lexmatch(P, &tok, ':')) {
      ty.enu.intty = unconstify(parsetype(P));
      if (ty.enu.intty->t != TYint) 
         fatal(P, tok.span, "enum backing type is not integral (%t)",
               ty.enu.intty);
   }

   lexexpect(P, '{');
   while (!lexmatch(P, &tok, '}')) {
      const char *fnam = lexexpect(P, TKident).str;
      i64 val; 

      if (lexmatch(P, &tok, '=')) {
         struct expr ex = parseexpr(P);
         if (!fold(&ex) || ex.t != Eintlit)
            fatal(P, ex.span,
                  "enum initializer must be compile-time integral constant");
         assert(ex.ty != ty_u64 || ex.u <= INT64_MAX);
         val = ex.i;
      } else {
         val = iota;
      }
      if (val < min)
         min = val;
      if (val > max)
         max = val;
      iota = val + 1;
      vec_push(&vals, ((struct enumval) { fnam, val }));

      if (!lexmatch(P, &tok, ',')) {
         lexexpect(P, '}');
         break;
      }
   }
   
   if (!ty.enu.intty) {
      if (min >= 0)
        ty.enu.intty = ilittype(max);
      else {
         if (min >= INT_MIN && max <= INT_MAX) ty.enu.intty = ty_int;
         if (min >= INT32_MIN && max <= INT32_MAX) ty.enu.intty = ty_int;
         if (min >= INT64_MIN && max <= INT64_MAX) ty.enu.intty = ty_int;
      }
   }

   ty.size = ty.enu.intty->size;
   ty.align = ty.enu.intty->align;

   ty.enu.name = name;
   ty.enu.id = id++;
   vec_slice_cpy(&ty.enu.vals, &vals);
   return interntype(ty);
}

struct aggdeclyarg {
   vec_t(struct decl *) *decls;
   struct parser *P;
   const struct type *aggty;
};

static void
aggdeclyield(struct decl *decl, void *arg) {
   struct aggdeclyarg *a = arg;

   if (decl->t == Dtype && decl->ty == a->aggty)
      ;
   else if ((decl->t == Dfn && !decl->externp) || decl->t == Ddef || decl->t == Dmacro)
      vec_push(a->decls, decl);
   else
      fatal(a->P, decl->span, "this kind of declaration is disallowed inside aggregates");
}

static const struct type *
parseagg(struct parser *P, const char *name, int kind, struct decl **retdecl) {
   struct tok tok;
   struct type ty = {kind};
   const struct type *pty = NULL;
   static int id = 0;
   size_t size = 0, align = 1;
   i64 f0align = -1;
   bool decls = 0;
   vec_t(struct aggfield) flds = {0};

   ty.agg.name = name;
   if (lexmatch(P, &tok, ';')) {
      ty.agg.fwd = 1;
      ty.agg.id = id++;
      return interntype(ty);
   } else {
      if (name) {
         struct env env_noparent = *P->curenv;
         env_noparent.parent = NULL;
         struct decl *decl = (struct decl *)envfind(&env_noparent, P->envage, name);
         if (decl && decl->t == Dtype && decl->ty->t == kind) {
            pty = decl->ty;
            *(bool *)&pty->agg.fwd = 0;
         } else {
            pty = interntype((struct type) {
               kind, .agg.name = name, .agg.id = id++
            });
         }

         *retdecl = decl = putdecl(P, P->tokspan, &(struct decl) {
            Dtype, name, .span = P->tokspan, .ty = pty });
      } else {
         pty = interntype((struct type) {
            kind, .agg.name = name, .agg.id = id++
         });
      }
      tok = lexexpect(P, '{');
      while (!lexmatch(P, &tok, '}')) {
         if (isdecltokt(lexpeek(P).t)) {
            decls = 1;
            break;
         }

         const char *fnam = (tok = lexexpect(P, TKident)).str;
         const struct type *ty = NULL;
         size_t off = size;
         if (kind != TYeunion || ((tok = lexpeek(P)).t != ',' && tok.t != '}' && tok.t != TKkw_fn)) {
               ty = parsetype(P);
               if (f0align < 0)
                  f0align = ty->align;
               off = kind != TYstruct ? 0 : ALIGNUP(size, ty->align);
         }

         int i; struct aggfield fld;
         vec_foreach(&flds, fld, i)
            if (!strcmp(fnam, fld.name))
               fatal(P, tok.span, "duplicate field %T", tok);

         if (ty && !completetype(ty))
            fatal(P, tok.span, "aggregate field `%s' is of incomplete type (%t)",
                  fnam, ty);

         if (ty) {
            align = MAX(align, ty->align);
            if (kind == TYstruct)
               size = off + ty->size;
            else
               size = MAX(size, ty->size);
         }

         vec_push(&flds, ((struct aggfield) {
            off, fnam, ty
         }));

         if (!lexmatch(P, &tok, ',')) {
            lexexpect(P, '}');
            break;
         }
      }

      if (!flds.length && kind == TYeunion)
         fatal(P, tok.span, "enum union must have at least 1 variant");

      struct type *ppty = (struct type *)pty;
      ppty->size = size ? ALIGNUP(size, align) : 1;
      ppty->align = align;
      vec_slice_cpy(&ppty->agg.flds, &flds);

      if (kind == TYeunion) {
         struct type enumty = {TYenum, .enu.id = id++};
         int n = flds.length;

         enumty.enu.name = name;
         enumty.enu.vals.d = xmalloc(n * sizeof(struct enumval));
         enumty.enu.vals.n = n;
         if (n < 256)
            enumty.enu.intty = ty_u8;
         else if (n < 65536)
            enumty.enu.intty = ty_u16;
         else assert(0);
         enumty.size = enumty.enu.intty->size; 
         enumty.align = enumty.enu.intty->align; 

         int i; struct aggfield fld;
         vec_foreach(&flds, fld, i) {
            struct enumval *ev = &enumty.enu.vals.d[i];
            ev->name = fld.name;
            ev->i = i;
         }
         ppty->agg.enumty = interntype(enumty);

         size_t off = f0align < 0 ? 0 : ALIGNUP(enumty.size, f0align);
         ppty->size += off;
         align = MAX(align, enumty.align);
         ppty->size = ALIGNUP(ppty->size, align);

         for (int i = 0; i < ppty->agg.flds.n; ++i)
            ppty->agg.flds.d[i].off += off;
      }

      if (!decls)
         return pty;
      else {
         vec_t(struct decl *) decls = {0};
         struct env env = {.parent = P->curenv};

         struct aggdeclyarg yarg = {
            (void *)&decls, P, pty
         };

         pushenv(P, &env);
         P->container = pty;
         while (!lexmatch(P, &tok, '}')) {
            ppty->agg.decls.d = decls.data;
            ppty->agg.decls.n = decls.length;
            parsedecl(aggdeclyield, &yarg, P, 0);
         }
         P->container = NULL;

         vec_slice_cpy(&ppty->agg.decls, &decls);
         popenv(P);
         return pty;
      }
   }
}

static const char *
getbasedir(const char *path) {
   static char res[PATH_MAX];
   int i;
   for (i = strlen(path); i > 0 && path[i] != '/'; --i)
      ;
   if (!i)
      return ".";
   memcpy(res, path, i);
   res[i] = '\0';
   return res;
}

static struct comfile
doimport(struct parser *P, const char *path) {
   static vec_t(struct entry { const char *s; struct comfile cf; bool wip; }) seen;
   char path2[PATH_MAX], _rpath[PATH_MAX], *rpath;
   struct comfile cf = {0};
   struct parser P2;
   const char *basedir = getbasedir(P->curfile);
   snprintf(path2, sizeof path2 - 1, "%s/%s", basedir, path);

   if (!(rpath = realpath(path2, _rpath)))
      fatal(P, P->tokspan, "import %q: %s", path, strerror(errno));
   for (int i = 0; i < seen.length; ++i) {
      if (!strcmp(seen.data[i].s, rpath)) {
         if (seen.data[i].wip) {
            // epri("warning: \"%s\": circular import detected: \"%s\" being processed\n",
            //      P->curfile, path);
         }
         return seen.data[i].cf;
      }
   }

   rpath = xstrdup(rpath);
   // P2.primenv = P->primenv;
   initparser(&P2, rpath);
   P2.is_header = 1;
   vec_push(&seen, ((struct entry) { rpath, cf, 1 }));
   parse(&cf, &P2);
   seen.data[seen.length - 1].wip = 0;
   seen.data[seen.length - 1].cf = cf;
   return cf;    
}

static struct tepl
parseaggtepl(struct parser *P, int kind, const char *name) {
   struct tepl tepl = {Dtype, kind, name};
   vec_t(struct teplparam) params = {0};
   struct tok tok;
   vec_t(struct tok) toks = {0};

   while (!lexmatch(P, &tok, '>')) {
      struct teplparam p;
      const char *name = lexexpects(P, TKident, "parameter name").str;

      p.name = name;
      if ((tok = lexpeek(P)).t == '>' || tok.t == ',') {
         p.typ = 1;
      } else {
         assert(0);
      }

      vec_push(&params, p);
      
      if (!lexmatch(P, NULL, ',')) {
         lexexpect(P, '>');
         break;
      }
   }
   lexexpect(P, '{');
   vec_push(&toks, (struct tok){'{'});

   int pabal = 0, // ( ) parens balance
       bkbal = 0, // [ ] brackets ..
       bcbal = 1; // { } braces ..

  while (pabal || bkbal || bcbal) { 
      tok = lex(P);
      switch (tok.t) {
      case '[': ++bkbal; break; case ']': --bkbal; break;
      case '{': ++bcbal; break; case '}': --bcbal; break;
      case '(': ++pabal; break; case ')': --pabal; break;
      }
      if (tok.t == TKident)
         for (int i = 0; i < params.length; ++i)
            if (!strcmp(params.data[i].name, tok.str))
               tok.t = TKmacident;
      vec_push(&toks, tok);
   }

   tepl.env = P->curenv;
   tepl.envage = P->envage;
   vec_slice_cpy(&tepl.params, &params);
   vec_slice_cpy(&tepl.toks, &toks);
   return tepl;
}

struct staticvaryarg {
   struct parser *P;
   bool externp, toplevel;
   struct span espan;
   decl_yielder_t yield;
   void *yarg;
};

static void
staticvaryield(struct decl *decl, void *arg) {
   struct staticvaryarg *a = arg;
   decl->t = Dstatic;
   decl->externp = a->externp;
   decl->_cname = xcalloc(1, sizeof (char *));
   decl->span = a->espan;
   if (!a->toplevel && !a->externp && !decl->var.ini)
      fatal(a->P, decl->span,
            "static variable not in toplevel cannot be forward-declared");
   if (!a->toplevel && a->externp && decl->var.ini)
      fatal(a->P, decl->span,
            "extern static variable not in toplevel cannot be initialized");
   if (a->P->is_header && a->externp && decl->var.ini)
      fatal(a->P, decl->span,
            "cannot define extern variable in header");
   putdecl(a->P, decl->span, decl);
   if (a->yield)
      a->yield(decl, a->yarg);
}

struct defyarg {
   struct parser *P;
   struct span espan;
   decl_yielder_t yield;
   void *yarg;
};

static void
defyield(struct decl *decl, void *arg) {
   struct defyarg *a = arg;
   decl->t = Ddef;
   decl->span = a->espan;
   assert(decl->name);
   if (!decl->var.ini)
      fatal(a->P, decl->span, "def must have a value");
   fold(decl->var.ini);
   if (!fold(decl->var.ini))
      fatal(a->P, decl->var.ini->span, "def initializer must be constant expression");
   putdecl(a->P, decl->span, decl);
   if (a->yield)
      a->yield(decl, a->yarg);
}

static void
parsedecl(decl_yielder_t yield, void *yarg, struct parser *P, bool toplevel) {
   struct tok tok = { .span = P->tokspan };
   bool externp = 0;
   const char *name;
   int kind;
   struct decl decl = {0};
   struct decl* decl2  = NULL;
   struct attr attr = {0};
   decl.container = P->container;

   if (lexmatch(P, &tok, TKhwhen)) {
      struct expr test = parseexpr(P);
      if (!fold(&test) || test.ty->t != TYbool)
         fatal(P, test.span, "#when test is not a constant bool expression");
      assert(test.t == Eboolit);
      lexexpect(P, '{');
      if (test.i) {
         while (!lexmatch(P, &tok, '}'))
            parsedecl(yield, yarg, P, toplevel);
      } else {
         int pabal = 0, // ( ) parens balance
             bkbal = 0, // [ ] brackets ..
             bcbal = 1; // { } braces ..

         while (pabal || bkbal || bcbal) { 
            tok = lex(P);
            switch (tok.t) {
            case '[': ++bkbal; break; case ']': --bkbal; break;
            case '{': ++bcbal; break; case '}': --bcbal; break;
            case '(': ++pabal; break; case ')': --pabal; break;
            }
         }
      }
      return;
   }

   if (lexmatch(P, &tok, '#')) {
      lexexpect(P, '[');
      while (!lexmatch(P, NULL, ']')) {
         const char *a = (tok = lexexpect(P, TKident)).str;
         if (!strcmp(a, "lax"))
            attr.lax = 1;
         else
            fatal(P, tok.span, "unknown attribute %T", tok);
      }
   }

   if (lexmatch(P, &tok, TKkw_extern))
      externp = 1;

   if (lexmatch(P, &tok, TKkw_fn)) {
      name = lexexpects(P, TKident, "function name").str;

      decl.t = Dfn;
      decl.name = decl.fn.name = name;
      decl._cname = xcalloc(1, sizeof (char *));
      decl.span = tok.span;
      parsefn(&decl, P);
      decl.externp = externp;
      if (P->is_header && externp && decl.fn.body)
         fatal(P, decl.span,
               "cannot define extern function in header");
   } else if (lexmatch(P, &tok, TKkw_static)) {
      parsevardecl(staticvaryield, &(struct staticvaryarg) {
            P, externp, toplevel, tok.span, yield, yarg
      }, P, 0, externp);
      return;
   } else if (lexmatch(P, &tok, TKkw_def)) {
      if (externp) fatal(P, tok.span, "def cannot be `extern'");
      parsevardecl(defyield, &(struct defyarg) {
            P, tok.span, yield, yarg
      }, P, 0, 0);
      return;
   } else if (lexmatch(P, &tok, TKkw_typedef)) {
      if (externp) fatal(P, tok.span, "typedef cannot be `extern'");
      decl.t = Dtype;
      decl.name = lexexpects(P, TKident, "typedef name").str;
      decl.ty = parsetype(P);
      decl._cname = xcalloc(1, sizeof(char *));
      lexexpect(P, ';');         
   } else if (lexmatch(P, &tok, TKkw_defmacro)) {
      if (externp) fatal(P, tok.span, "macro cannot be `extern'");
      name = lexexpects(P, TKident, "macro name").str;
      if (lexmatch(P, &tok, '=')) {
         // defmacro name = expr
         struct expr ex = parseexpr(P);
         decl.t = Ddef;
         decl.name = name;
         decl.var.ini = exprdup(ex);
         decl.var.ty = ex.ty;
         lexexpect(P, ';');
      } else {
         decl.t = Dmacro;
         decl.name = name;
         decl.macro = parsemacro(P);
         decl.macro.name = name;
      }
   } else if (lexmatch(P, &tok, TKkw_enum)) {
      decl.t = Dtype;
      if (lexmatch(P, &tok, TKkw_union)) {
         if (externp) fatal(P, tok.span, "enum union cannot be `extern'");
         kind = TYeunion;
         goto agg;
      } else {
         if (externp) fatal(P, tok.span, "enum cannot be `extern'");
         decl.name = lexexpects(P, TKident, "enum name").str;
         decl.ty = parseenum(P, decl.name, attr);
      }
   } else if (lexmatch(P, &tok, TKkw_struct)) {
      kind = TYstruct;
      if (externp) fatal(P, tok.span, "struct cannot be `extern'");
   agg:
      decl.span = tok.span;
      decl.name = lexexpects(P, TKident, "type name").str;
      if (!lexmatch(P, NULL, '<')) {
         decl.t = Dtype;
         decl.ty = parseagg(P, decl.name, kind, &decl2);
      } else {
         if (!toplevel)
            fatal(P, tok.span, "template definition inside function");
         decl.t = Dtepl;
         decl.tepl = parseaggtepl(P, kind, decl.name);
      }
      if (decl2) goto noput;
   } else if (lexmatch(P, &tok, TKkw_union)) {
      if (externp) fatal(P, tok.span, "union cannot be `extern'");
      kind = TYunion;
      goto agg;
   } else if (lexmatch(P, &tok, TKkw_import)) {
      const char *path;
      struct comfile cf;
      assert(toplevel);
      path = (tok = lexexpect(P, TKstrlit)).str;
      cf = doimport(P, path);
      free((void *)path);
      for (int i = 0; i < cf.decls.n; ++i) {
         struct decl *decl = putdecl(P, tok.span, cf.decls.d[i]);
         if (yield)
            yield(decl, yarg);
      }
      lexexpect(P, ';');
      return;
   } else if (lexmatch(P, &tok, TKident)) {
      const struct decl *dm = finddecl(P, tok.str);
      if (!dm || dm->t != Dmacro)
         goto err;
      parseexpandmacro(P, &dm->macro);
      return parsedecl(yield, yarg, P, toplevel);
   } else {
   err:
      fatal(P, tok.span, "expected declaration (near %s)",
            tok2str(tok));
   }

   decl2 = putdecl(P, tok.span, &decl);
noput:
   if (yield)
      yield(decl2 ? decl2 : &decl, yarg);
}

static void
yieldexdecl(struct decl *decl, void *arg) {
   vec_t(struct decl *) *decls = arg;
   vec_push(decls, decl);
}

void
parse(struct comfile *cf, struct parser *P) {
   vec_t(struct decl *) decls = {0};
   while (!P->eof && lexpeek(P).t != TKeof)
      parsedecl(yieldexdecl, &decls, P, 1);
   vec_slice_cpy(&cf->decls, &decls);
}

void
initparser(struct parser *P, const char *fname) {
   assert(NUM_KEYWORDS - 1 < '!');
   memset(P, 0, sizeof *P);
   P->curfile = fname;
   if (!(P->fp = fopen(fname, "r")))
      perror(fname), exit(1);
   P->tokspan = P->curspan = (struct span) { addfilepath(fname), 0, 1, 1 };
   P->peekchr = -1;
   P->curenv = P->tlenv = xcalloc(1, sizeof *P->tlenv);
   P->primenv = xcalloc(1, sizeof *P->primenv);
   putprimtypes(P->primenv);
}