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))
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);
13 static void emit(struct Parser* p, int byte)
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;
22 p->cg->byteCode[p->cg->nBytes++] = (unsigned char)byte;
25 static void emitImmediate(struct Parser* p, int byte, int arg)
32 static void genBinOp(int op, struct Parser* p, struct Token* t)
34 if(!LEFT(t) || !RIGHT(t))
35 naParseError(p, "empty subexpression", t->line);
41 static int newConstant(struct Parser* p, naRef c)
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);
49 static naRef getConstant(struct Parser* p, int idx)
52 naHash_get(p->cg->consts, naNum(idx), &c);
56 // Interns a scalar (!) constant and returns its index
57 static int internConstant(struct Parser* p, naRef c)
60 naHash_get(p->cg->interned, c, &r);
64 int idx = newConstant(p, c);
65 naHash_set(p->cg->interned, c, naNum(idx));
70 static void genScalarConstant(struct Parser* p, struct Token* t)
73 ? naStr_fromdata(naNewString(p->context), t->str, t->strlen)
75 int idx = internConstant(p, c);
76 emitImmediate(p, OP_PUSHCONST, idx);
79 static int genLValue(struct Parser* p, struct Token* t)
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);
86 } else if(t->type == TOK_DOT && RIGHT(t) && RIGHT(t)->type == TOK_SYMBOL) {
88 genScalarConstant(p, RIGHT(t));
90 } else if(t->type == TOK_LBRA) {
95 naParseError(p, "bad lvalue", t->line);
100 static void genLambda(struct Parser* p, struct Token* t)
103 struct CodeGenerator* cgSave;
105 if(LEFT(t)->type != TOK_LCURL)
106 naParseError(p, "bad function definition", t->line);
108 // Save off the generator state while we do the new one
110 codeObj = naCodeGen(p, LEFT(LEFT(t)));
113 idx = newConstant(p, codeObj);
114 emitImmediate(p, OP_PUSHCONST, idx);
117 static void genList(struct Parser* p, struct Token* t)
119 if(t->type == TOK_COMMA) {
122 genList(p, RIGHT(t));
123 } else if(t->type == TOK_EMPTY) {
131 static void genHashElem(struct Parser* p, struct Token* t)
133 if(t->type == TOK_EMPTY)
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));
144 static void genHash(struct Parser* p, struct Token* t)
146 if(t->type == TOK_COMMA) {
147 genHashElem(p, LEFT(t));
148 genHash(p, RIGHT(t));
149 } else if(t->type != TOK_EMPTY) {
154 static void genFuncall(struct Parser* p, struct Token* t)
157 if(LEFT(t)->type == TOK_DOT) {
158 genExpr(p, LEFT(LEFT(t)));
160 genScalarConstant(p, RIGHT(LEFT(t)));
167 if(RIGHT(t)) genList(p, RIGHT(t));
171 static void pushLoop(struct Parser* p, struct Token* label)
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;
181 static void popLoop(struct Parser* p)
184 if(p->cg->loopTop < 0) naParseError(p, "BUG: loop stack underflow", -1);
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)
195 emit(p, 0xff); // dummy address
200 // Points a previous jump instruction at the current "end-of-bytecode"
201 static void fixJumpTarget(struct Parser* p, int spot)
203 p->cg->byteCode[spot] = p->cg->nBytes >> 8;
204 p->cg->byteCode[spot+1] = p->cg->nBytes & 0xff;
207 static void genShortCircuit(struct Parser* p, struct Token* t)
209 int jumpNext, jumpEnd, isAnd = (t->type == TOK_AND);
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);
221 static void genIf(struct Parser* p, struct Token* tif, struct Token* telse)
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);
230 if(telse->type == TOK_ELSIF) genIf(p, telse, telse->next);
231 else genExprList(p, telse->children->children);
235 fixJumpTarget(p, jumpEnd);
238 static void genIfElse(struct Parser* p, struct Token* t)
240 genIf(p, t, t->children->next->next);
243 static int countSemis(struct Token* t)
245 if(!t || t->type != TOK_SEMI) return 0;
246 return 1 + countSemis(RIGHT(t));
249 static void genLoop(struct Parser* p, struct Token* body,
250 struct Token* update, struct Token* label,
251 int loopTop, int jumpEnd)
253 int cont, jumpOverContinue;
255 p->cg->loops[p->cg->loopTop-1].breakIP = jumpEnd-1;
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);
262 genExprList(p, body);
264 fixJumpTarget(p, cont);
265 if(update) { genExpr(p, update); emit(p, OP_POP); }
266 emitImmediate(p, OP_JMP, loopTop);
267 fixJumpTarget(p, jumpEnd);
269 emit(p, OP_PUSHNIL); // Leave something on the stack
272 static void genForWhile(struct Parser* p, struct Token* init,
273 struct Token* test, struct Token* update,
274 struct Token* body, struct Token* label)
276 int loopTop, jumpEnd;
277 if(init) { genExpr(p, init); emit(p, OP_POP); }
279 loopTop = p->cg->nBytes;
281 jumpEnd = emitJump(p, OP_JIFNOT);
282 genLoop(p, body, update, label, loopTop, jumpEnd);
285 static void genWhile(struct Parser* p, struct Token* t)
287 struct Token *test=LEFT(t)->children, *body, *label=0;
288 int semis = countSemis(test);
291 if(!label || label->type != TOK_SYMBOL)
292 naParseError(p, "bad loop label", t->line);
296 naParseError(p, "too many semicolons in while test", t->line);
297 body = LEFT(RIGHT(t));
298 genForWhile(p, 0, test, 0, body, label);
301 static void genFor(struct Parser* p, struct Token* t)
303 struct Token *init, *test, *body, *update, *label=0;
304 struct Token *h = LEFT(t)->children;
305 int semis = countSemis(h);
307 if(!LEFT(h) || LEFT(h)->type != TOK_SYMBOL)
308 naParseError(p, "bad loop label", h->line);
311 } else if(semis != 2) {
312 naParseError(p, "wrong number of terms in for header", t->line);
315 // Parse tree hell :)
317 test = LEFT(RIGHT(h));
318 update = RIGHT(RIGHT(h));
319 body = RIGHT(t)->children;
320 genForWhile(p, init, test, update, body, label);
323 static void genForEach(struct Parser* p, struct Token* t)
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);
330 if(!LEFT(h) || LEFT(h)->type != TOK_SYMBOL)
331 naParseError(p, "bad loop label", h->line);
334 } else if (semis != 1) {
335 naParseError(p, "wrong number of terms in foreach header", t->line);
339 body = RIGHT(t)->children;
343 emit(p, OP_PUSHZERO);
344 loopTop = p->cg->nBytes;
346 jumpEnd = emitJump(p, OP_JIFNIL);
347 assignOp = genLValue(p, elem);
351 genLoop(p, body, 0, label, loopTop, jumpEnd);
354 static int tokMatch(struct Token* a, struct Token* b)
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;
363 static void genBreakContinue(struct Parser* p, struct Token* t)
365 int levels = 1, loop = -1, bp, cp, i;
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))
373 naParseError(p, "no match for break/continue label", t->line);
374 levels = p->cg->loopTop - loop;
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++)
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);
385 static void genExpr(struct Parser* p, struct Token* t)
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;
406 case TOK_BREAK: case TOK_CONTINUE:
407 genBreakContinue(p, t);
410 genExprList(p, LEFT(t));
416 if(BINARY(t) || !RIGHT(t)) genFuncall(p, t); // function invocation
417 else genExpr(p, LEFT(t)); // simple parenthesis
421 genBinOp(OP_EXTRACT, p, t); // a[i]
432 i = genLValue(p, LEFT(t));
433 genExpr(p, RIGHT(t));
434 emit(p, i); // use the op appropriate to the lvalue
437 if(RIGHT(t)) genExpr(p, RIGHT(t));
438 else emit(p, OP_PUSHNIL);
442 genExpr(p, RIGHT(t));
446 genScalarConstant(p, t);
450 genScalarConstant(p, 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));
459 genExpr(p, RIGHT(t)); // unary negation
464 genExpr(p, RIGHT(t)); // unary negation (see also TOK_MINUS!)
469 if(RIGHT(t)->type != TOK_SYMBOL)
470 naParseError(p, "object field not symbol", RIGHT(t)->line);
471 genScalarConstant(p, RIGHT(t));
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);
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;
490 naParseError(p, "parse error", t->line);
494 static void genExprList(struct Parser* p, struct Token* t)
496 if(t->type == TOK_SEMI) {
498 if(RIGHT(t) && RIGHT(t)->type != TOK_EMPTY) {
500 genExprList(p, RIGHT(t));
507 naRef naCodeGen(struct Parser* p, struct Token* t)
512 struct CodeGenerator cg;
515 cg.codeAlloced = 1024; // Start fairly big, this is a cheap allocation
516 cg.byteCode = naParseAlloc(p, cg.codeAlloced);
518 cg.consts = naNewHash(p->context);
519 cg.interned = naNewHash(p->context);
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);