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