Source

arana-main / arana / compile.c

Full commit
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
/*
 * compile.h
 *
 * (c) Copyright 2009 by Armin Ronacher, Georg Brandl.
 */

#include "arana.h"
#include "_astmap.h"

/* helper macros for the compiler */
#define COMPILER_SIG AR_SIG, ArCompiler *compiler
#define COMPILER_ISIG AR_ISIG, compiler
#define VISIT(node) arana_compiler_visit(COMPILER_ISIG, (ArAstNode *)node)
#define ON(x) case AR_AST_##x

#define OP1(x) arana_compiler_add_op(COMPILER_ISIG, AR_OP_##x, 0)
#define OP2(x, y) arana_compiler_add_op(COMPILER_ISIG, AR_OP_##x, y)
#define SETOP1(i, x) (compiler->unit->ops[i].op = AR_OP_##x)
#define SETOP2(i, x, y) (SETOP1(i, x), compiler->unit->ops[i].arg = y)
#define CONST(v) arana_compiler_register_constant(COMPILER_ISIG, v)
#define NEXTINSTR compiler->unit->op_count
#define CURINSTR (NEXTINSTR - 1)
#define LOCAL(name) arana_compiler_register_local(COMPILER_ISIG, name)
#define MAKEJUMP(t, o, p) SETOP2(o, t, p)
#define TMPOP() (OP1(UNSET), CURINSTR)

static void arana_compiler_visit(COMPILER_SIG, ArAstNode *node);


static ArCodeUnit *
arana_new_code_unit(COMPILER_SIG, const char *filename)
{
    ArCodeUnit *unit = AR_ALLOCT(ArCodeUnit);
    if (!unit)
        AR_RAISE_OOM();
    unit->filename = filename;
    unit->ops_allocated = 32;
    unit->ops = AR_ALLOCTN(ArOp, unit->ops_allocated);
    if (!unit->ops) {
        AR_FREE(unit);
        AR_RAISE_OOM();
    }
    unit->op_count = 0;
    unit->consts = AR_LIST();
    unit->vars = AR_STRINGMAP();
    return unit;
}

static AR
arana_compiler_make_localtuple(AR_SIG, AR vars)
{
    Ar_size_t index;
    ArStringMap *stringmap = (ArStringMap *)vars;
    AR result = AR_TUPLE(AR_STRINGMAP_SIZE(vars));
    /* TODO: use a unified iteration API here */
    khiter_t k;
    for (k = kh_begin(stringmap->kh); k != kh_end(stringmap->kh); ++k) {
        if (!kh_exist(stringmap->kh, k))
            continue;
        index = AR_AS_SIZET(kh_value(stringmap->kh, k));
        AR_TUPLE_PUT(result, index, AR_STRING(kh_key(stringmap->kh, k)));
    }
    return result;
}

static Ar_size_t
arana_compiler_get_stack_size(AR_SIG, ArCodeUnit *unit)
{
    ArOp op;
    Ar_size_t depth = 0, max_depth = 0;

#define ON_OPCODE(x) case AR_OP_##x
#define RECORD(x) \
    depth += x; \
    if (depth > max_depth) max_depth = depth; \
    break

    for (Ar_size_t i = 0; i < unit->op_count; i++)
        switch ((op = unit->ops[i]).op) {
        ON_OPCODE(LOAD_CONST):
        ON_OPCODE(LOAD_FAST):
        ON_OPCODE(ITER_NEXT):
            RECORD(+1);
        ON_OPCODE(MAKE_STRING):
        ON_OPCODE(MAKE_TUPLE):
        ON_OPCODE(MAKE_LIST):
            RECORD(1 - op.arg);
        ON_OPCODE(CALL_METHOD):
            RECORD(-2);
        ON_OPCODE(STORE_FAST):
        ON_OPCODE(POS):
        ON_OPCODE(NEG):
        ON_OPCODE(NOT):
        ON_OPCODE(GET_ITERATOR):
            RECORD(0);
        ON_OPCODE(CONCAT):
        ON_OPCODE(ADD):
        ON_OPCODE(SUB):
        ON_OPCODE(MUL):
        ON_OPCODE(DIV):
        ON_OPCODE(MOD):
        ON_OPCODE(POW):
        ON_OPCODE(JUMP_IF_FALSE):
        ON_OPCODE(JUMP_ALWAYS):
        ON_OPCODE(POP_TOP):
        ON_OPCODE(CALL):
        ON_OPCODE(GET_ATTRIBUTE):
        ON_OPCODE(GET_SUBSCRIPT):
            RECORD(-1);
        }

    return max_depth;
}

static ArCode *
arana_compiler_make_code(COMPILER_SIG)
{
    ArCode *code = AR_ALLOCT(ArCode);
    if (!code)
        AR_RAISE_OOM();
    code->consts = AR_TUPLE_FROM_LIST(compiler->unit->consts);
    code->filename = compiler->unit->filename;
    code->vars = arana_compiler_make_localtuple(AR_ISIG, compiler->unit->vars);
    code->ops = compiler->unit->ops;
    code->stack_size = arana_compiler_get_stack_size(AR_ISIG, compiler->unit);
    return code;
}

static void
arana_compiler_add_op(COMPILER_SIG, int opcode, Ar_size_t arg)
{
    ArOp *op;
    ArCodeUnit *unit = compiler->unit;
    if (unit->op_count >= unit->ops_allocated) {
        Ar_size_t new_size = unit->ops_allocated * 1.3;
        void *tmp = AR_REALLOCTN(unit->ops, ArOp, new_size);
        if (!tmp)
            AR_RAISE_OOM();
        unit->ops = tmp;
        unit->ops_allocated = new_size;
    }
    op = &unit->ops[unit->op_count++];
    op->op = (unsigned char)opcode;
    op->arg = (unsigned int)arg;
}

static Ar_size_t
arana_compiler_register_constant(COMPILER_SIG, AR value)
{
    Ar_size_t index = AR_LIST_SIZE(compiler->unit->consts);
    AR_LIST_APPEND(compiler->unit->consts, value);
    return index;
}

static Ar_size_t
arana_compiler_register_local(COMPILER_SIG, const char *name)
{
    AR value = AR_STRINGMAP_GET(compiler->unit->vars, name);
    if (!value) {
        Ar_size_t index = AR_STRINGMAP_SIZE(compiler->unit->vars);
        AR_STRINGMAP_SET(compiler->unit->vars, name, AR_INTEGER(index));
        return index;
    }
    return AR_AS_SIZET(value);
}

/* visitor functions for individual nodes */

static void
arana_compile_module(COMPILER_SIG, ArToplevelNode *node)
{
    Ar_size_t index;
    for (index = 0; index < node->v.Module.stmts->count; index++)
        VISIT(node->v.Module.stmts->items[index]);
}


static void
arana_compile_compound_stmt(COMPILER_SIG, ArStmtNode *node)
{
    Ar_size_t index;
    for (index = 0; index < node->v.Compound.stmts->count; index++)
        VISIT(node->v.Compound.stmts->items[index]);
}

static void
arana_compile_expr_stmt(COMPILER_SIG, ArStmtNode *node)
{
    VISIT(node->v.ExprStmt.expr);
    OP1(POP_TOP);
}

static void
arana_compile_if_stmt(COMPILER_SIG, ArStmtNode *node)
{
    Ar_size_t jump1, jump2;
    VISIT(node->v.If.test);
    jump1 = TMPOP();
    OP1(POP_TOP);
    VISIT(node->v.If.body);
    /* if there is a else section we have to jump another instruction
       ahead to skip the jump that skips the else which is only
       inserted if there is an else section. */
    MAKEJUMP(JUMP_IF_FALSE, jump1, NEXTINSTR + !!node->v.If.else_);
    if (node->v.If.else_) {
        jump2 = TMPOP();
        OP1(POP_TOP);
        VISIT(node->v.If.else_);
        MAKEJUMP(JUMP_ALWAYS, jump2, NEXTINSTR);
    }
}

static void
arana_compile_for_stmt(COMPILER_SIG, ArStmtNode *node)
{
    Ar_size_t next_pos, next_jump, iter_jump;
    VISIT(node->v.For.seq);
    iter_jump = TMPOP();
    OP1(GET_ITERATOR);
    next_pos = NEXTINSTR;
    OP1(ITER_NEXT);
    VISIT(node->v.For.target);
    VISIT(node->v.For.body);
    OP1(POP_TOP);
    next_jump = TMPOP();
    MAKEJUMP(JUMP_ALWAYS, next_jump, next_pos);
    MAKEJUMP(SETUP_LOOP, iter_jump, NEXTINSTR);
}


static void
arana_compile_assign(COMPILER_SIG, ArExprNode *node)
{
    VISIT(node->v.Assign.expr);
    VISIT(node->v.Assign.target);
}

enum ArOpcode augops[] = {
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    AR_OP_CONCAT,
    AR_OP_ADD,
    AR_OP_SUB,
    AR_OP_MUL,
    AR_OP_DIV,
    AR_OP_MOD,
    AR_OP_POW,
    0,
    0,
    0
};

static void
arana_compile_augassign(COMPILER_SIG, ArExprNode *node)
{
    ArExprNode *new;
    switch (node->v.AugAssign.target->type) {
    ON(Name):
        new = AR_AST(Name, node->v.AugAssign.target->v.Name.ident, AR_CTX_Load);
        break;
    default:
        AR_FATAL("arana_compile_augassign: unhandled target node type %s\n",
                 AR_ASTMAP[node->v.AugAssign.target->type]);
    }
    VISIT(new);
    VISIT(node->v.AugAssign.expr);
    arana_compiler_add_op(COMPILER_ISIG, augops[node->v.AugAssign.op], 0);
    VISIT(node->v.AugAssign.target);
}

static void
arana_compile_binary(COMPILER_SIG, ArExprNode *node)
{
    VISIT(node->v.BinaryOp.left);
    VISIT(node->v.BinaryOp.right);
    switch (node->v.BinaryOp.op) {
    case AR_ASTOP_AND:    OP1(AND);     break;
    case AR_ASTOP_OR:     OP1(OR);      break;
    case AR_ASTOP_CONCAT: OP1(CONCAT);  break;
    case AR_ASTOP_ADD:    OP1(ADD);     break;
    case AR_ASTOP_SUB:    OP1(SUB);     break;
    case AR_ASTOP_MUL:    OP1(MUL);     break;
    case AR_ASTOP_DIV:    OP1(DIV);     break;
    case AR_ASTOP_MOD:    OP1(MOD);     break;
    case AR_ASTOP_POW:    OP1(POW);     break;
    default: AR_FATAL("arana_compile_binary: unhandled operator %s\n",
                      AR_ASTOPMAP[node->v.BinaryOp.op]);
    }
}

static void
arana_compile_unary(COMPILER_SIG, ArExprNode *node)
{
    VISIT(node->v.UnaryOp.expr);
    switch (node->v.UnaryOp.op) {
    case AR_ASTOP_POS:    OP1(POS); break;
    case AR_ASTOP_NEG:    OP1(NEG); break;
    case AR_ASTOP_NOT:    OP1(NOT); break;
    default: AR_FATAL("arana_compile_unary: unhandled operator %s\n",
                      AR_ASTOPMAP[node->v.UnaryOp.op]);
    }
}

static void
arana_compile_call(COMPILER_SIG, ArExprNode *node)
{
    /* we're calling a method */
    if (AR_AST_IS(node->v.Call.expr, Attribute)) {
        VISIT(node->v.Call.expr->v.Attribute.expr);
        VISIT(node->v.Call.expr->v.Attribute.attr);
        VISIT(node->v.Call.args);
        OP1(CALL_METHOD);
    }
    /* regular call */
    else {
        VISIT(node->v.Call.expr);
        VISIT(node->v.Call.args);
        OP1(CALL);
    }
}

static void
arana_compile_attribute(COMPILER_SIG, ArExprNode *node)
{
    VISIT(node->v.Attribute.expr);
    VISIT(node->v.Attribute.attr);
    switch (node->v.Attribute.ctx) {
    case AR_CTX_Load:
        OP1(GET_ATTRIBUTE);
        break;
    case AR_CTX_Store:
        OP1(SET_ATTRIBUTE);
        break;
    }
}

static void
arana_compile_subscript(COMPILER_SIG, ArExprNode *node)
{
    VISIT(node->v.Subscript.expr);
    VISIT(node->v.Subscript.index);
    switch (node->v.Subscript.ctx) {
    case AR_CTX_Load:
        OP1(GET_SUBSCRIPT);
        break;
    case AR_CTX_Store:
        OP1(SET_SUBSCRIPT);
        break;
    }
}

static void
arana_compile_list(COMPILER_SIG, ArExprNode *node)
{
    int index, count;
    if (node->v.List.items == NULL) {
        count = 0;
    } else {
        count = node->v.List.items->count;
        /* put the items onto the stack in reverse order, so that
           the tuple builder can directly pop and append them */
        for (index = count-1; index >= 0; index--) {
            VISIT(node->v.List.items->items[index]);
        }
    }
    OP2(MAKE_LIST, count);
}

static void
arana_compile_tuple(COMPILER_SIG, ArExprNode *node)
{
    int index, count;
    if (node->v.Tuple.items == NULL) {
        count = 0;
    } else {
        count = node->v.Tuple.items->count;
        /* put the items onto the stack in reverse order, so that
           the tuple builder can directly pop and append them */
        for (index = count-1; index >= 0; index--) {
            VISIT(node->v.Tuple.items->items[index]);
        }
    }
    OP2(MAKE_TUPLE, count);
}

static void
arana_compile_interpolation(COMPILER_SIG, ArExprNode *node)
{
    int index;
    ArExprSeq *items = node->v.Interpolation.items;
    if (items->count == 1 && AR_AST_IS(items->items[0], Literal)) {
        VISIT(items->items[0]);
    } else {
        /* put the items onto the stack in reverse order, so that
           the string builder can directly pop and append them */
        for (index = items->count-1; index >= 0; index--) {
            VISIT(items->items[index]);
        }
        OP2(MAKE_STRING, items->count);
    }
}

static void
arana_compile_name(COMPILER_SIG, ArExprNode *node)
{
    Ar_size_t index = LOCAL(node->v.Name.ident);
    if (node->v.Name.ctx == AR_CTX_Store)
        OP2(STORE_FAST, index);
    else
        OP2(LOAD_FAST, index);
}

static void
arana_compile_literal(COMPILER_SIG, ArExprNode *node)
{
    Ar_size_t index = CONST(node->v.Literal.value);
    OP2(LOAD_CONST, index);
}


static void
arana_compiler_visit(COMPILER_SIG, ArAstNode *node)
{

#define COMPILE(func, type) \
    arana_compile_##func(COMPILER_ISIG, (type *)node); \
    break

    switch (node->type) {
    ON(Module):         COMPILE(module, ArToplevelNode);
    ON(Compound):       COMPILE(compound_stmt, ArStmtNode);
    ON(ExprStmt):       COMPILE(expr_stmt, ArStmtNode);
    ON(If):             COMPILE(if_stmt, ArStmtNode);
    ON(For):            COMPILE(for_stmt, ArStmtNode);
    ON(Assign):         COMPILE(assign, ArExprNode);
    ON(AugAssign):      COMPILE(augassign, ArExprNode);
    ON(BinaryOp):       COMPILE(binary, ArExprNode);
    ON(UnaryOp):        COMPILE(unary, ArExprNode);
    ON(Call):           COMPILE(call, ArExprNode);
    ON(Attribute):      COMPILE(attribute, ArExprNode);
    ON(Subscript):      COMPILE(subscript, ArExprNode);
    ON(List):           COMPILE(list, ArExprNode);
    ON(Tuple):          COMPILE(tuple, ArExprNode);
    ON(Interpolation):  COMPILE(interpolation, ArExprNode);
    ON(Name):           COMPILE(name, ArExprNode);
    ON(Literal):        COMPILE(literal, ArExprNode);
    default:
        AR_FATAL("arana_compiler_visit: unhandled AST node type %s\n",
                 AR_ASTMAP[node->type]);
    }
}

ArCode *
arana_compile(AR_SIG, ArAstNode *node, const char *filename)
{
    ArCompiler compiler;
    compiler.unit = arana_new_code_unit(AR_ISIG, &compiler, filename);
    arana_compiler_visit(AR_ISIG, &compiler, node);
    arana_compiler_add_op(AR_ISIG, &compiler, AR_OP_STOP, 0);
    return arana_compiler_make_code(AR_ISIG, &compiler);
}