simgear/nasal/codegen.c

   1 #include "parse.h"
   2 #include "code.h"
   3
   4 // These are more sensical predicate names in most contexts in this file
   5 #define LEFT(tok)   ((tok)->children)
   6 #define RIGHT(tok)  ((tok)->lastChild)
   7 #define BINARY(tok) (LEFT(tok) && RIGHT(tok) && LEFT(tok) != RIGHT(tok))
   8
   9 // Forward references for recursion
  10 static void genExpr(struct Parser* p, struct Token* t);
  11 static void genExprList(struct Parser* p, struct Token* t);
  12
  13 static void emit(struct Parser* p, int byte)
  14 {
  15     if(p->cg->nBytes >= p->cg->codeAlloced) {
  16         int i, sz = p->cg->codeAlloced * 2;
  17         unsigned char* buf = naParseAlloc(p, sz);
  18         for(i=0; i<p->cg->codeAlloced; i++) buf[i] = p->cg->byteCode[i];
  19         p->cg->byteCode = buf;
  20         p->cg->codeAlloced = sz;
  21     }
  22     p->cg->byteCode[p->cg->nBytes++] = (unsigned char)byte;
  23 }
  24
  25 static void emitImmediate(struct Parser* p, int byte, int arg)
  26 {
  27     emit(p, byte);
  28     emit(p, arg >> 8);
  29     emit(p, arg & 0xff);
  30 }
  31
  32 static void genBinOp(int op, struct Parser* p, struct Token* t)
  33 {
  34     if(!LEFT(t) || !RIGHT(t))
  35         naParseError(p, "empty subexpression", t->line);
  36     genExpr(p, LEFT(t));
  37     genExpr(p, RIGHT(t));
  38     emit(p, op);
  39 }
  40
  41 static int newConstant(struct Parser* p, naRef c)
  42 {
  43     int i = p->cg->nConsts++;
  44     if(i > 0xffff) naParseError(p, "too many constants in code block", 0);
  45     naHash_set(p->cg->consts, naNum(i), c);
  46     return i;
  47 }
  48
  49 static naRef getConstant(struct Parser* p, int idx)
  50 {
  51     naRef c;
  52     naHash_get(p->cg->consts, naNum(idx), &c);
  53     return c;
  54 }
  55
  56 // Interns a scalar (!) constant and returns its index
  57 static int internConstant(struct Parser* p, naRef c)
  58 {
  59     naRef r;
  60     naHash_get(p->cg->interned, c, &r);
  61     if(!IS_NIL(r)) {
  62         return (int)r.num;
  63     } else {
  64         int idx = newConstant(p, c);
  65         naHash_set(p->cg->interned, c, naNum(idx));
  66         return idx;
  67     }
  68 }
  69
  70 static void genScalarConstant(struct Parser* p, struct Token* t)
  71 {
  72     naRef c = (t->str
  73                ? naStr_fromdata(naNewString(p->context), t->str, t->strlen)
  74                : naNum(t->num));
  75     int idx = internConstant(p, c);
  76     emitImmediate(p, OP_PUSHCONST, idx);
  77 }
  78
  79 static int genLValue(struct Parser* p, struct Token* t)
  80 {
  81     if(t->type == TOK_LPAR) {
  82         return genLValue(p, LEFT(t)); // Handle stuff like "(a) = 1"
  83     } else if(t->type == TOK_SYMBOL) {
  84         genScalarConstant(p, t);
  85         return OP_SETLOCAL;
  86     } else if(t->type == TOK_DOT && RIGHT(t) && RIGHT(t)->type == TOK_SYMBOL) {
  87         genExpr(p, LEFT(t));
  88         genScalarConstant(p, RIGHT(t));
  89         return OP_SETMEMBER;
  90     } else if(t->type == TOK_LBRA) {
  91         genExpr(p, LEFT(t));
  92         genExpr(p, RIGHT(t));
  93         return OP_INSERT;
  94     } else {
  95         naParseError(p, "bad lvalue", t->line);
  96         return -1;
  97     }
  98 }
  99
 100 static void genLambda(struct Parser* p, struct Token* t)
 101 {
 102     int idx;
 103     struct CodeGenerator* cgSave;
 104     naRef codeObj;
 105     if(LEFT(t)->type != TOK_LCURL)
 106         naParseError(p, "bad function definition", t->line);
 107
 108     // Save off the generator state while we do the new one
 109     cgSave = p->cg;
 110     codeObj = naCodeGen(p, LEFT(LEFT(t)));
 111     p->cg = cgSave;
 112
 113     idx = newConstant(p, codeObj);
 114     emitImmediate(p, OP_PUSHCONST, idx);
 115 }
 116
 117 static void genList(struct Parser* p, struct Token* t)
 118 {
 119     if(t->type == TOK_COMMA) {
 120         genExpr(p, LEFT(t));
 121         emit(p, OP_VAPPEND);
 122         genList(p, RIGHT(t));
 123     } else if(t->type == TOK_EMPTY) {
 124         return;
 125     } else {
 126         genExpr(p, t);
 127         emit(p, OP_VAPPEND);
 128     }
 129 }
 130
 131 static void genHashElem(struct Parser* p, struct Token* t)
 132 {
 133     if(t->type == TOK_EMPTY)
 134         return;
 135     if(t->type != TOK_COLON)
 136         naParseError(p, "bad hash/object initializer", t->line);
 137     if(LEFT(t)->type == TOK_SYMBOL) genScalarConstant(p, LEFT(t));
 138     else if(LEFT(t)->type == TOK_LITERAL) genExpr(p, LEFT(t));
 139     else naParseError(p, "bad hash/object initializer", t->line);
 140     genExpr(p, RIGHT(t));
 141     emit(p, OP_HAPPEND);
 142 }
 143
 144 static void genHash(struct Parser* p, struct Token* t)
 145 {
 146     if(t->type == TOK_COMMA) {
 147         genHashElem(p, LEFT(t));
 148         genHash(p, RIGHT(t));
 149     } else if(t->type != TOK_EMPTY) {
 150         genHashElem(p, t);
 151     }
 152 }
 153
 154 static void genFuncall(struct Parser* p, struct Token* t)
 155 {
 156     int op = OP_FCALL;
 157     if(LEFT(t)->type == TOK_DOT) {
 158         genExpr(p, LEFT(LEFT(t)));
 159         emit(p, OP_DUP);
 160         genScalarConstant(p, RIGHT(LEFT(t)));
 161         emit(p, OP_MEMBER);
 162         op = OP_MCALL;
 163     } else {
 164         genExpr(p, LEFT(t));
 165     }
 166     emit(p, OP_NEWVEC);
 167     if(RIGHT(t)) genList(p, RIGHT(t));
 168     emit(p, op);
 169 }
 170
 171 static void pushLoop(struct Parser* p, struct Token* label)
 172 {
 173     int i = p->cg->loopTop;
 174     p->cg->loops[i].breakIP = 0xffffff;
 175     p->cg->loops[i].contIP = 0xffffff;
 176     p->cg->loops[i].label = label;
 177     p->cg->loopTop++;
 178     emit(p, OP_MARK);
 179 }
 180
 181 static void popLoop(struct Parser* p)
 182 {
 183     p->cg->loopTop--;
 184     if(p->cg->loopTop < 0) naParseError(p, "BUG: loop stack underflow", -1);
 185     emit(p, OP_UNMARK);
 186 }
 187
 188 // Emit a jump operation, and return the location of the address in
 189 // the bytecode for future fixup in fixJumpTarget
 190 static int emitJump(struct Parser* p, int op)
 191 {
 192     int ip;
 193     emit(p, op);
 194     ip = p->cg->nBytes;
 195     emit(p, 0xff); // dummy address
 196     emit(p, 0xff);
 197     return ip;
 198 }
 199
 200 // Points a previous jump instruction at the current "end-of-bytecode"
 201 static void fixJumpTarget(struct Parser* p, int spot)
 202 {
 203     p->cg->byteCode[spot]   = p->cg->nBytes >> 8;
 204     p->cg->byteCode[spot+1] = p->cg->nBytes & 0xff;
 205 }
 206
 207 static void genShortCircuit(struct Parser* p, struct Token* t)
 208 {
 209     int jumpNext, jumpEnd, isAnd = (t->type == TOK_AND);
 210     genExpr(p, LEFT(t));
 211     if(isAnd) emit(p, OP_NOT);
 212     jumpNext = emitJump(p, OP_JIFNOT);
 213     emit(p, isAnd ? OP_PUSHNIL : OP_PUSHONE);
 214     jumpEnd = emitJump(p, OP_JMP);
 215     fixJumpTarget(p, jumpNext);
 216     genExpr(p, RIGHT(t));
 217     fixJumpTarget(p, jumpEnd);
 218 }
 219
 220
 221 static void genIf(struct Parser* p, struct Token* tif, struct Token* telse)
 222 {
 223     int jumpNext, jumpEnd;
 224     genExpr(p, tif->children); // the test
 225     jumpNext = emitJump(p, OP_JIFNOT);
 226     genExprList(p, tif->children->next->children); // the body
 227     jumpEnd = emitJump(p, OP_JMP);
 228     fixJumpTarget(p, jumpNext);
 229     if(telse) {
 230         if(telse->type == TOK_ELSIF) genIf(p, telse, telse->next);
 231         else genExprList(p, telse->children->children);
 232     } else {
 233         emit(p, OP_PUSHNIL);
 234     }
 235     fixJumpTarget(p, jumpEnd);
 236 }
 237
 238 static void genIfElse(struct Parser* p, struct Token* t)
 239 {
 240     genIf(p, t, t->children->next->next);
 241 }
 242
 243 static int countSemis(struct Token* t)
 244 {
 245     if(!t || t->type != TOK_SEMI) return 0;
 246     return 1 + countSemis(RIGHT(t));
 247 }
 248
 249 static void genLoop(struct Parser* p, struct Token* body,
 250                     struct Token* update, struct Token* label,
 251                     int loopTop, int jumpEnd)
 252 {
 253     int cont, jumpOverContinue;
 254
 255     p->cg->loops[p->cg->loopTop-1].breakIP = jumpEnd-1;
 256
 257     jumpOverContinue = emitJump(p, OP_JMP);
 258     p->cg->loops[p->cg->loopTop-1].contIP = p->cg->nBytes;
 259     cont = emitJump(p, OP_JMP);
 260     fixJumpTarget(p, jumpOverContinue);
 261
 262     genExprList(p, body);
 263     emit(p, OP_POP);
 264     fixJumpTarget(p, cont);
 265     if(update) { genExpr(p, update); emit(p, OP_POP); }
 266     emitImmediate(p, OP_JMP, loopTop);
 267     fixJumpTarget(p, jumpEnd);
 268     popLoop(p);
 269     emit(p, OP_PUSHNIL); // Leave something on the stack
 270 }
 271
 272 static void genForWhile(struct Parser* p, struct Token* init,
 273                         struct Token* test, struct Token* update,
 274                         struct Token* body, struct Token* label)
 275 {
 276     int loopTop, jumpEnd;
 277     if(init) { genExpr(p, init); emit(p, OP_POP); }
 278     pushLoop(p, label);
 279     loopTop = p->cg->nBytes;
 280     genExpr(p, test);
 281     jumpEnd = emitJump(p, OP_JIFNOT);
 282     genLoop(p, body, update, label, loopTop, jumpEnd);
 283 }
 284
 285 static void genWhile(struct Parser* p, struct Token* t)
 286 {
 287     struct Token *test=LEFT(t)->children, *body, *label=0;
 288     int semis = countSemis(test);
 289     if(semis == 1) {
 290         label = LEFT(test);
 291         if(!label || label->type != TOK_SYMBOL)
 292             naParseError(p, "bad loop label", t->line);
 293         test = RIGHT(test);
 294     }
 295     else if(semis != 0)
 296         naParseError(p, "too many semicolons in while test", t->line);
 297     body = LEFT(RIGHT(t));
 298     genForWhile(p, 0, test, 0, body, label);
 299 }
 300
 301 static void genFor(struct Parser* p, struct Token* t)
 302 {
 303     struct Token *init, *test, *body, *update, *label=0;
 304     struct Token *h = LEFT(t)->children;
 305     int semis = countSemis(h);
 306     if(semis == 3) {
 307         if(!LEFT(h) || LEFT(h)->type != TOK_SYMBOL)
 308             naParseError(p, "bad loop label", h->line);
 309         label = LEFT(h);
 310         h=RIGHT(h);
 311     } else if(semis != 2) {
 312         naParseError(p, "wrong number of terms in for header", t->line);
 313     }
 314
 315     // Parse tree hell :)
 316     init = LEFT(h);
 317     test = LEFT(RIGHT(h));
 318     update = RIGHT(RIGHT(h));
 319     body = RIGHT(t)->children;
 320     genForWhile(p, init, test, update, body, label);
 321 }
 322
 323 static void genForEach(struct Parser* p, struct Token* t)
 324 {
 325     int loopTop, jumpEnd, assignOp;
 326     struct Token *elem, *body, *vec, *label=0;
 327     struct Token *h = LEFT(LEFT(t));
 328     int semis = countSemis(h);
 329     if(semis == 2) {
 330         if(!LEFT(h) || LEFT(h)->type != TOK_SYMBOL)
 331             naParseError(p, "bad loop label", h->line);
 332         label = LEFT(h);
 333         h = RIGHT(h);
 334     } else if (semis != 1) {
 335         naParseError(p, "wrong number of terms in foreach header", t->line);
 336     }
 337     elem = LEFT(h);
 338     vec = RIGHT(h);
 339     body = RIGHT(t)->children;
 340
 341     pushLoop(p, label);
 342     genExpr(p, vec);
 343     emit(p, OP_PUSHZERO);
 344     loopTop = p->cg->nBytes;
 345     emit(p, OP_EACH);
 346     jumpEnd = emitJump(p, OP_JIFNIL);
 347     assignOp = genLValue(p, elem);
 348     emit(p, OP_XCHG);
 349     emit(p, assignOp);
 350     emit(p, OP_POP);
 351     genLoop(p, body, 0, label, loopTop, jumpEnd);
 352 }
 353
 354 static int tokMatch(struct Token* a, struct Token* b)
 355 {
 356     int i, l = a->strlen;
 357     if(!a || !b) return 0;
 358     if(l != b->strlen) return 0;
 359     for(i=0; i<l; i++) if(a->str[i] != b->str[i]) return 0;
 360     return 1;
 361 }
 362
 363 static void genBreakContinue(struct Parser* p, struct Token* t)
 364 {
 365     int levels = 1, loop = -1, bp, cp, i;
 366     if(RIGHT(t)) {
 367         if(RIGHT(t)->type != TOK_SYMBOL)
 368             naParseError(p, "bad break/continue label", t->line);
 369         for(i=0; i<p->cg->loopTop; i++)
 370             if(tokMatch(RIGHT(t), p->cg->loops[i].label))
 371                 loop = i;
 372         if(loop == -1)
 373             naParseError(p, "no match for break/continue label", t->line);
 374         levels = p->cg->loopTop - loop;
 375     }
 376     bp = p->cg->loops[p->cg->loopTop - levels].breakIP;
 377     cp = p->cg->loops[p->cg->loopTop - levels].contIP;
 378     for(i=0; i<levels; i++)
 379         emit(p, OP_BREAK);
 380     if(t->type == TOK_BREAK)
 381         emit(p, OP_PUSHNIL); // breakIP is always a JIFNOT/JIFNIL!
 382     emitImmediate(p, OP_JMP, t->type == TOK_BREAK ? bp : cp);
 383 }
 384
 385 static void genExpr(struct Parser* p, struct Token* t)
 386 {
 387     int i;
 388     if(t == 0)
 389         naParseError(p, "BUG: null subexpression", -1);
 390     if(t->line != p->cg->lastLine)
 391         emitImmediate(p, OP_LINE, t->line);
 392     p->cg->lastLine = t->line;
 393     switch(t->type) {
 394     case TOK_IF:
 395         genIfElse(p, t);
 396         break;
 397     case TOK_WHILE:
 398         genWhile(p, t);
 399         break;
 400     case TOK_FOR:
 401         genFor(p, t);
 402         break;
 403     case TOK_FOREACH:
 404         genForEach(p, t);
 405         break;
 406     case TOK_BREAK: case TOK_CONTINUE:
 407         genBreakContinue(p, t);
 408         break;
 409     case TOK_TOP:
 410         genExprList(p, LEFT(t));
 411         break;
 412     case TOK_FUNC:
 413         genLambda(p, t);
 414         break;
 415     case TOK_LPAR:
 416         if(BINARY(t) || !RIGHT(t)) genFuncall(p, t); // function invocation
 417         else          genExpr(p, LEFT(t)); // simple parenthesis
 418         break;
 419     case TOK_LBRA:
 420         if(BINARY(t)) {
 421             genBinOp(OP_EXTRACT, p, t); // a[i]
 422         } else {
 423             emit(p, OP_NEWVEC);
 424             genList(p, LEFT(t));
 425         }
 426         break;
 427     case TOK_LCURL:
 428         emit(p, OP_NEWHASH);
 429         genHash(p, LEFT(t));
 430         break;
 431     case TOK_ASSIGN:
 432         i = genLValue(p, LEFT(t));
 433         genExpr(p, RIGHT(t));
 434         emit(p, i); // use the op appropriate to the lvalue
 435         break;
 436     case TOK_RETURN:
 437         if(RIGHT(t)) genExpr(p, RIGHT(t));
 438         else emit(p, OP_PUSHNIL);
 439         emit(p, OP_RETURN);
 440         break;
 441     case TOK_NOT:
 442         genExpr(p, RIGHT(t));
 443         emit(p, OP_NOT);
 444         break;
 445     case TOK_SYMBOL:
 446         genScalarConstant(p, t);
 447         emit(p, OP_LOCAL);
 448         break;
 449     case TOK_LITERAL:
 450         genScalarConstant(p, t);
 451         break;
 452     case TOK_MINUS:
 453         if(BINARY(t)) {
 454             genBinOp(OP_MINUS,  p, t);  // binary subtraction
 455         } else if(RIGHT(t)->type == TOK_LITERAL && !RIGHT(t)->str) {
 456             RIGHT(t)->num *= -1;        // Pre-negate constants
 457             genScalarConstant(p, RIGHT(t));
 458         } else {
 459             genExpr(p, RIGHT(t));       // unary negation
 460             emit(p, OP_NEG);
 461         }
 462         break;
 463     case TOK_NEG:
 464         genExpr(p, RIGHT(t)); // unary negation (see also TOK_MINUS!)
 465         emit(p, OP_NEG);
 466         break;
 467     case TOK_DOT:
 468         genExpr(p, LEFT(t));
 469         if(RIGHT(t)->type != TOK_SYMBOL)
 470             naParseError(p, "object field not symbol", RIGHT(t)->line);
 471         genScalarConstant(p, RIGHT(t));
 472         emit(p, OP_MEMBER);
 473         break;
 474     case TOK_EMPTY: case TOK_NIL:
 475         emit(p, OP_PUSHNIL); break; // *NOT* a noop!
 476     case TOK_AND: case TOK_OR:
 477         genShortCircuit(p, t);
 478         break;
 479     case TOK_MUL:   genBinOp(OP_MUL,    p, t); break;
 480     case TOK_PLUS:  genBinOp(OP_PLUS,   p, t); break;
 481     case TOK_DIV:   genBinOp(OP_DIV,    p, t); break;
 482     case TOK_CAT:   genBinOp(OP_CAT,    p, t); break;
 483     case TOK_LT:    genBinOp(OP_LT,     p, t); break;
 484     case TOK_LTE:   genBinOp(OP_LTE,    p, t); break;
 485     case TOK_EQ:    genBinOp(OP_EQ,     p, t); break;
 486     case TOK_NEQ:   genBinOp(OP_NEQ,    p, t); break;
 487     case TOK_GT:    genBinOp(OP_GT,     p, t); break;
 488     case TOK_GTE:   genBinOp(OP_GTE,    p, t); break;
 489     default:
 490         naParseError(p, "parse error", t->line);
 491     };
 492 }
 493
 494 static void genExprList(struct Parser* p, struct Token* t)
 495 {
 496     if(t->type == TOK_SEMI) {
 497         genExpr(p, LEFT(t));
 498         if(RIGHT(t) && RIGHT(t)->type != TOK_EMPTY) {
 499             emit(p, OP_POP);
 500             genExprList(p, RIGHT(t));
 501         }
 502     } else {
 503         genExpr(p, t);
 504     }
 505 }
 506
 507 naRef naCodeGen(struct Parser* p, struct Token* t)
 508 {
 509     int i;
 510     naRef codeObj;
 511     struct naCode* code;
 512     struct CodeGenerator cg;
 513
 514     cg.lastLine = 0;
 515     cg.codeAlloced = 1024; // Start fairly big, this is a cheap allocation
 516     cg.byteCode = naParseAlloc(p, cg.codeAlloced);
 517     cg.nBytes = 0;
 518     cg.consts = naNewHash(p->context);
 519     cg.interned = naNewHash(p->context);
 520     cg.nConsts = 0;
 521     cg.loopTop = 0;
 522     p->cg = &cg;
 523
 524     genExprList(p, t);
 525
 526     // Now make a code object
 527     codeObj = naNewCode(p->context);
 528     code = codeObj.ref.ptr.code;
 529     code->nBytes = cg.nBytes;
 530     code->byteCode = naAlloc(cg.nBytes);
 531     for(i=0; i < cg.nBytes; i++)
 532         code->byteCode[i] = cg.byteCode[i];
 533     code->nConstants = cg.nConsts;
 534     code->constants = naAlloc(code->nConstants * sizeof(naRef));
 535     code->srcFile = p->srcFile;
 536     for(i=0; i<code->nConstants; i++)
 537         code->constants[i] = getConstant(p, i);
 538
 539     return codeObj;
 540 }