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