backend.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Pythonc backend
   4 //
   5 // Copyright 2011 Zach Wegner
   6 //
   7 // Licensed under the Apache License, Version 2.0 (the "License");
   8 // you may not use this file except in compliance with the License.
   9 // You may obtain a copy of the License at
  10 //
  11 //   http://www.apache.org/licenses/LICENSE-2.0
  12 //
  13 // Unless required by applicable law or agreed to in writing, software
  14 // distributed under the License is distributed on an "AS IS" BASIS,
  15 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16 // See the License for the specific language governing permissions and
  17 // limitations under the License.
  18 //
  19 ////////////////////////////////////////////////////////////////////////////////
  20
  21 #define __STDC_FORMAT_MACROS
  22 #include <stdarg.h>
  23 #include <stdio.h>
  24 #include <stdint.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <inttypes.h>
  28 #include <algorithm>
  29 #include <map>
  30 #include <set>
  31 #include <sstream>
  32 #include <string>
  33 #include <vector>
  34
  35 #include "alloc.h"
  36
  37 __attribute((noreturn)) void error(const char *msg, ...) {
  38     va_list va;
  39     va_start(va, msg);
  40     vprintf(msg, va);
  41     va_end(va);
  42     puts("");
  43     fflush(stdout);
  44     exit(1);
  45 }
  46
  47 class node;
  48 class dict;
  49 class list;
  50 class context;
  51 class string_const;
  52
  53 typedef int64_t int_t;
  54
  55 typedef std::pair<node *, node *> node_pair;
  56 typedef std::map<const char *, node *> symbol_table;
  57 typedef std::map<int_t, node_pair> node_dict;
  58 typedef std::map<int_t, node *> node_set;
  59 typedef std::vector<node *> node_list;
  60
  61 node *builtin_dict_get(context *globals, context *ctx, list *args, dict *kwargs);
  62 node *builtin_dict_keys(context *globals, context *ctx, list *args, dict *kwargs);
  63 node *builtin_list_append(context *globals, context *ctx, list *args, dict *kwargs);
  64 node *builtin_list_index(context *globals, context *ctx, list *args, dict *kwargs);
  65 node *builtin_list_pop(context *globals, context *ctx, list *args, dict *kwargs);
  66 node *builtin_set_add(context *globals, context *ctx, list *args, dict *kwargs);
  67 node *builtin_str_join(context *globals, context *ctx, list *args, dict *kwargs);
  68 node *builtin_str_split(context *globals, context *ctx, list *args, dict *kwargs);
  69 node *builtin_str_upper(context *globals, context *ctx, list *args, dict *kwargs);
  70 node *builtin_str_startswith(context *globals, context *ctx, list *args, dict *kwargs);
  71
  72 inline node *create_bool_const(bool b);
  73
  74 class node {
  75 private:
  76 public:
  77     node() { }
  78     virtual const char *node_type() { return "node"; }
  79
  80     virtual void mark_live() { error("mark_live unimplemented for %s", this->node_type()); }
  81 #define MARK_LIVE_FN \
  82     virtual void mark_live() { allocator->mark_live(this, sizeof(*this)); }
  83 #define MARK_LIVE_SINGLETON_FN virtual void mark_live() { }
  84
  85     virtual bool is_bool() { return false; }
  86     virtual bool is_dict() { return false; }
  87     virtual bool is_file() { return false; }
  88     virtual bool is_function() { return false; }
  89     virtual bool is_int_const() { return false; }
  90     virtual bool is_list() { return false; }
  91     virtual bool is_none() { return false; }
  92     virtual bool is_set() { return false; }
  93     virtual bool is_string() { return false; }
  94     virtual bool bool_value() { error("bool_value unimplemented for %s", this->node_type()); return false; }
  95     virtual int_t int_value() { error("int_value unimplemented for %s", this->node_type()); return 0; }
  96     virtual std::string string_value() { error("string_value unimplemented for %s", this->node_type()); return NULL; }
  97     virtual node_list *list_value() { error("list_value unimplemented for %s", this->node_type()); return NULL; }
  98
  99 #define UNIMP_OP(NAME) \
 100     virtual node *__##NAME##__(node *rhs) { error(#NAME " unimplemented for %s", this->node_type()); return NULL; }
 101
 102     UNIMP_OP(add)
 103     UNIMP_OP(and)
 104     UNIMP_OP(divmod)
 105     UNIMP_OP(floordiv)
 106     UNIMP_OP(lshift)
 107     UNIMP_OP(mod)
 108     UNIMP_OP(mul)
 109     UNIMP_OP(or)
 110     UNIMP_OP(pow)
 111     UNIMP_OP(rshift)
 112     UNIMP_OP(sub)
 113     UNIMP_OP(truediv)
 114     UNIMP_OP(xor)
 115
 116 #define UNIMP_CMP_OP(NAME) \
 117     virtual bool _##NAME(node *rhs) { error(#NAME " unimplemented for %s", this->node_type()); return false; } \
 118     node *__##NAME##__(node *rhs) { return create_bool_const(this->_##NAME(rhs)); }
 119
 120     UNIMP_CMP_OP(eq)
 121     UNIMP_CMP_OP(ne)
 122     UNIMP_CMP_OP(lt)
 123     UNIMP_CMP_OP(le)
 124     UNIMP_CMP_OP(gt)
 125     UNIMP_CMP_OP(ge)
 126
 127     UNIMP_OP(contains)
 128
 129 #define UNIMP_UNOP(NAME) \
 130     virtual node *__##NAME##__() { error(#NAME " unimplemented for %s", this->node_type()); return NULL; }
 131
 132     UNIMP_UNOP(invert)
 133     UNIMP_UNOP(pos)
 134     UNIMP_UNOP(neg)
 135
 136     node *__len__();
 137     node *__hash__();
 138     node *__getattr__(node *rhs);
 139     node *__not__();
 140     node *__is__(node *rhs);
 141     node *__isnot__(node *rhs);
 142     node *__repr__();
 143     node *__str__();
 144
 145     virtual node *__ncontains__(node *rhs) { return this->__contains__(rhs)->__not__(); }
 146
 147     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) { error("call unimplemented for %s", this->node_type()); return NULL; }
 148     virtual void __delitem__(node *rhs) { error("delitem unimplemented for %s", this->node_type()); }
 149     virtual node *__getitem__(node *rhs) { error("getitem unimplemented for %s", this->node_type()); return NULL; }
 150     virtual node *__getitem__(int index) { error("getitem unimplemented for %s", this->node_type()); return NULL; }
 151     virtual node *__iter__() { error("iter unimplemented for %s", this->node_type()); }
 152     virtual node *next() { error("next unimplemented for %s", this->node_type()); }
 153     virtual void __setattr__(node *rhs, node *key) { error("setattr unimplemented for %s", this->node_type()); }
 154     virtual void __setitem__(node *key, node *value) { error("setitem unimplemented for %s", this->node_type()); }
 155     virtual node *__slice__(node *start, node *end, node *step) { error("slice unimplemented for %s", this->node_type()); return NULL; }
 156
 157     // unwrapped versions
 158     virtual int_t len() { error("len unimplemented for %s", this->node_type()); return 0; }
 159     virtual node *getattr(const char *rhs) { error("getattr unimplemented (%s) for %s", rhs, this->node_type()); return NULL; }
 160     virtual int_t hash() { error("hash unimplemented for %s", this->node_type()); return 0; }
 161     virtual std::string repr() { error("repr unimplemented for %s", this->node_type()); return NULL; }
 162     virtual std::string str() { return repr(); }
 163 };
 164
 165 class context {
 166 private:
 167     symbol_table symbols;
 168     context *parent_ctx;
 169
 170 public:
 171     context() {
 172         this->parent_ctx = NULL;
 173     }
 174     context(context *parent_ctx) {
 175         this->parent_ctx = parent_ctx;
 176     }
 177
 178     void mark_live(bool free_ctx) {
 179         if (!free_ctx)
 180             for (symbol_table::const_iterator i = this->symbols.begin(); i != this->symbols.end(); i++)
 181                 i->second->mark_live();
 182         if (this->parent_ctx)
 183             this->parent_ctx->mark_live(false);
 184     }
 185
 186     void store(const char *name, node *obj) {
 187         this->symbols[name] = obj;
 188     }
 189     node *load(const char *name) {
 190         symbol_table::const_iterator v = this->symbols.find(name);
 191         if (v == this->symbols.end())
 192             error("cannot find '%s' in symbol table", name);
 193         return v->second;
 194     }
 195     void dump() {
 196         for (symbol_table::const_iterator i = this->symbols.begin(); i != this->symbols.end(); i++)
 197             if (i->second->is_int_const())
 198                 printf("symbol['%s'] = int(%" PRId64 ");\n", i->first, i->second->int_value());
 199             else
 200                 printf("symbol['%s'] = %p;\n", i->first, i->second);
 201     }
 202 };
 203
 204 class none_const : public node {
 205 public:
 206     // For some reason this causes errors without an argument to the constructor...
 207     none_const(int_t value) { }
 208     const char *node_type() { return "none"; }
 209
 210     MARK_LIVE_SINGLETON_FN
 211
 212     virtual bool is_none() { return true; }
 213     virtual bool bool_value() { return false; }
 214
 215     virtual bool _eq(node *rhs);
 216     virtual int_t hash() { return 0; }
 217     virtual std::string repr() { return std::string("None"); }
 218 };
 219
 220 class int_const : public node {
 221 private:
 222     int_t value;
 223
 224 public:
 225     int_const(int_t value) {
 226         this->value = value;
 227     }
 228     const char *node_type() { return "int"; }
 229
 230     MARK_LIVE_FN
 231
 232     virtual bool is_int_const() { return true; }
 233     virtual int_t int_value() { return this->value; }
 234     virtual bool bool_value() { return this->value != 0; }
 235
 236 #define INT_OP(NAME, OP) \
 237     virtual int_t _##NAME(node *rhs) { \
 238         return this->int_value() OP rhs->int_value(); \
 239     } \
 240     virtual node *__##NAME##__(node *rhs) { \
 241         return new(allocator) int_const(this->_##NAME(rhs)); \
 242     }
 243     INT_OP(add, +)
 244     INT_OP(and, &)
 245     INT_OP(floordiv, /)
 246     INT_OP(lshift, <<)
 247     INT_OP(mod, %)
 248     INT_OP(mul, *)
 249     INT_OP(or, |)
 250     INT_OP(rshift, >>)
 251     INT_OP(sub, -)
 252     INT_OP(xor, ^)
 253
 254 #define CMP_OP(NAME, OP) \
 255     virtual bool _##NAME(node *rhs) { \
 256         return this->int_value() OP rhs->int_value(); \
 257     } \
 258
 259     CMP_OP(eq, ==)
 260     CMP_OP(ne, !=)
 261     CMP_OP(lt, <)
 262     CMP_OP(le, <=)
 263     CMP_OP(gt, >)
 264     CMP_OP(ge, >=)
 265
 266 #define INT_UNOP(NAME, OP) \
 267     virtual node *__##NAME##__() { \
 268         return new(allocator) int_const(OP this->int_value()); \
 269     }
 270     INT_UNOP(invert, ~)
 271     INT_UNOP(pos, +)
 272     INT_UNOP(neg, -)
 273
 274     virtual int_t hash() { return this->value; }
 275     virtual node *getattr(const char *key);
 276     virtual std::string repr();
 277 };
 278
 279 class int_const_singleton : public int_const {
 280 public:
 281     int_const_singleton(int_t value) : int_const(value) { }
 282
 283     MARK_LIVE_SINGLETON_FN
 284 };
 285
 286 class bool_const : public node {
 287 private:
 288     bool value;
 289
 290 public:
 291     bool_const(bool value) {
 292         this->value = value;
 293     }
 294     const char *node_type() { return "bool"; }
 295
 296     MARK_LIVE_SINGLETON_FN
 297
 298     virtual bool is_bool() { return true; }
 299     virtual bool bool_value() { return this->value; }
 300     virtual int_t int_value() { return (int_t)this->value; }
 301
 302 #define BOOL_AS_INT_OP(NAME, OP) \
 303     virtual node *__##NAME##__(node *rhs) { \
 304         if (rhs->is_int_const() || rhs->is_bool()) \
 305             return new(allocator) int_const(this->int_value() OP rhs->int_value()); \
 306         error(#NAME " error in bool"); \
 307         return NULL; \
 308     }
 309     BOOL_AS_INT_OP(add, +)
 310     BOOL_AS_INT_OP(floordiv, /)
 311     BOOL_AS_INT_OP(lshift, <<)
 312     BOOL_AS_INT_OP(mod, %)
 313     BOOL_AS_INT_OP(mul, *)
 314     BOOL_AS_INT_OP(rshift, >>)
 315     BOOL_AS_INT_OP(sub, -)
 316
 317 #define BOOL_INT_CHECK_OP(NAME, OP) \
 318     virtual node *__##NAME##__(node *rhs) { \
 319         if (rhs->is_bool()) \
 320             return new(allocator) bool_const((bool)(this->int_value() OP rhs->int_value())); \
 321         else if (rhs->is_int_const()) \
 322             return new(allocator) int_const(this->int_value() OP rhs->int_value()); \
 323         error(#NAME " error in bool"); \
 324         return NULL; \
 325     }
 326
 327     BOOL_INT_CHECK_OP(and, &)
 328     BOOL_INT_CHECK_OP(or, |)
 329     BOOL_INT_CHECK_OP(xor, ^)
 330
 331 #define BOOL_OP(NAME, OP) \
 332     virtual bool _##NAME(node *rhs) { \
 333         if (rhs->is_int_const() || rhs->is_bool()) \
 334             return this->int_value() OP rhs->int_value(); \
 335         error(#NAME " error in bool"); \
 336         return false; \
 337     }
 338     BOOL_OP(eq, ==)
 339     BOOL_OP(ne, !=)
 340     BOOL_OP(lt, <)
 341     BOOL_OP(le, <=)
 342     BOOL_OP(gt, >)
 343     BOOL_OP(ge, >=)
 344
 345     virtual int_t hash() { return (int_t)this->value; }
 346     virtual std::string repr();
 347 };
 348
 349 class string_const : public node {
 350 private:
 351     class str_iter: public node {
 352     private:
 353         string_const *parent;
 354         std::string::iterator it;
 355
 356     public:
 357         str_iter(string_const *s) {
 358             this->parent = s;
 359             it = s->value.begin();
 360         }
 361         const char *node_type() { return "str_iter"; }
 362
 363         virtual void mark_live() {
 364             if (!allocator->mark_live(this, sizeof(*this)))
 365                 this->parent->mark_live();
 366         }
 367
 368         virtual node *next() {
 369             if (this->it == this->parent->value.end())
 370                 return NULL;
 371             char ret[2];
 372             ret[0] = *this->it;
 373             ret[1] = 0;
 374             ++this->it;
 375             return new(allocator) string_const(ret);
 376         }
 377     };
 378
 379     std::string value;
 380
 381 public:
 382     string_const(std::string value) {
 383         this->value = value;
 384     }
 385     const char *node_type() { return "str"; }
 386
 387     MARK_LIVE_FN
 388
 389     virtual bool is_string() { return true; }
 390     virtual std::string string_value() { return this->value; }
 391     virtual bool bool_value() { return this->len() != 0; }
 392
 393     std::string::iterator begin() { return value.begin(); }
 394     std::string::iterator end() { return value.end(); }
 395
 396 #define STRING_OP(NAME, OP) \
 397     virtual bool _##NAME(node *rhs) { \
 398         if (rhs->is_string()) \
 399             return this->string_value() OP rhs->string_value(); \
 400         error(#NAME " unimplemented"); \
 401         return false; \
 402     } \
 403
 404     STRING_OP(eq, ==)
 405     STRING_OP(ne, !=)
 406     STRING_OP(lt, <)
 407     STRING_OP(le, <=)
 408     STRING_OP(gt, >)
 409     STRING_OP(ge, >=)
 410
 411     virtual node *__mod__(node *rhs);
 412     virtual node *__add__(node *rhs);
 413     virtual node *__mul__(node *rhs);
 414
 415     virtual node *getattr(const char *key);
 416
 417     virtual node *__getitem__(node *rhs) {
 418         if (!rhs->is_int_const()) {
 419             error("getitem unimplemented");
 420             return NULL;
 421         }
 422         return new(allocator) string_const(value.substr(rhs->int_value(), 1));
 423     }
 424     // FNV-1a algorithm
 425     virtual int_t hash() {
 426         int_t hashkey = 14695981039346656037ull;
 427         for (std::string::iterator c = this->begin(); c != this->end(); c++) {
 428             hashkey ^= *c;
 429             hashkey *= 1099511628211ll;
 430         }
 431         return hashkey;
 432     }
 433     virtual int_t len() {
 434         return value.length();
 435     }
 436     virtual node *__slice__(node *start, node *end, node *step) {
 437         if ((!start->is_none() && !start->is_int_const()) ||
 438             (!end->is_none() && !end->is_int_const()) ||
 439             (!step->is_none() && !step->is_int_const()))
 440             error("slice error");
 441         int_t lo = start->is_none() ? 0 : start->int_value();
 442         int_t hi = end->is_none() ? value.length() : end->int_value();
 443         int_t st = step->is_none() ? 1 : step->int_value();
 444         if (st != 1)
 445             error("slice step != 1 not supported for string");
 446         return new(allocator) string_const(this->value.substr(lo, hi - lo + 1));
 447     }
 448     virtual std::string repr() {
 449         bool has_single_quotes = false;
 450         bool has_double_quotes = false;
 451         for (std::string::iterator it = this->begin(); it != this->end(); ++it) {
 452             char c = *it;
 453             if (c == '\'')
 454                 has_single_quotes = true;
 455             else if (c == '"')
 456                 has_double_quotes = true;
 457         }
 458         bool use_double_quotes = has_single_quotes && !has_double_quotes;
 459         std::string s(use_double_quotes ? "\"" : "'");
 460         for (std::string::iterator it = this->begin(); it != this->end(); ++it) {
 461             char c = *it;
 462             if (c == '\n')
 463                 s += "\\n";
 464             else if (c == '\r')
 465                 s += "\\r";
 466             else if (c == '\t')
 467                 s += "\\t";
 468             else if (c == '\\')
 469                 s += "\\\\";
 470             else if ((c == '\'') && !use_double_quotes)
 471                 s += "\\'";
 472             else
 473                 s += c;
 474         }
 475         s += use_double_quotes ? "\"" : "'";
 476         return s;
 477     }
 478     virtual std::string str() { return this->value; }
 479     virtual node *__iter__() { return new(allocator) str_iter(this); }
 480 };
 481
 482 class string_const_singleton : public string_const {
 483 private:
 484     int_t hashkey;
 485
 486 public:
 487     string_const_singleton(std::string value, int_t hashkey) : string_const(value), hashkey(hashkey) { }
 488
 489     MARK_LIVE_SINGLETON_FN
 490
 491     virtual int_t hash() {
 492         return this->hashkey;
 493     }
 494 };
 495
 496 class list : public node {
 497 private:
 498     class list_iter: public node {
 499     private:
 500         list *parent;
 501         node_list::iterator it;
 502
 503     public:
 504         list_iter(list *l) {
 505             this->parent = l;
 506             it = l->items.begin();
 507         }
 508         const char *node_type() { return "list_iter"; }
 509
 510         virtual void mark_live() {
 511             if (!allocator->mark_live(this, sizeof(*this)))
 512                 this->parent->mark_live();
 513         }
 514
 515         virtual node *next() {
 516             if (this->it == this->parent->items.end())
 517                 return NULL;
 518             node *ret = *this->it;
 519             ++this->it;
 520             return ret;
 521         }
 522     };
 523
 524     node_list items;
 525
 526 public:
 527     list() { }
 528     list(node_list &l) : items(l) { }
 529     const char *node_type() { return "list"; }
 530
 531     virtual void mark_live() {
 532         if (!allocator->mark_live(this, sizeof(*this))) {
 533             for (size_t i = 0; i < this->items.size(); i++)
 534                 this->items[i]->mark_live();
 535         }
 536     }
 537
 538     void append(node *obj) {
 539         items.push_back(obj);
 540     }
 541     void prepend(node *obj) {
 542         items.insert(items.begin(), obj);
 543     }
 544     node *pop() {
 545         // would be nice if STL wasn't stupid, and this was one line...
 546         node *popped = items.back();
 547         items.pop_back();
 548         return popped;
 549     }
 550     node_list::iterator begin() { return items.begin(); }
 551     node_list::iterator end() { return items.end(); }
 552     int_t index(int_t base) {
 553         if (base < 0)
 554             base = items.size() + base;
 555         return base;
 556     }
 557
 558     virtual bool is_list() { return true; }
 559     virtual node_list *list_value() { return &items; }
 560     virtual bool bool_value() { return this->len() != 0; }
 561
 562     virtual node *__add__(node *rhs);
 563     virtual node *__mul__(node *rhs);
 564
 565     virtual node *__contains__(node *key) {
 566         bool found = false;
 567         for (size_t i = 0; i < this->items.size(); i++)
 568             if (this->items[i]->_eq(key)) {
 569                 found = true;
 570                 break;
 571             }
 572         return create_bool_const(found);
 573     }
 574     virtual void __delitem__(node *rhs) {
 575         if (!rhs->is_int_const()) {
 576             error("delitem unimplemented");
 577             return;
 578         }
 579         node_list::iterator f = items.begin() + this->index(rhs->int_value());
 580         items.erase(f);
 581     }
 582     virtual node *__getitem__(int idx) {
 583         return this->items[this->index(idx)];
 584     }
 585     virtual node *__getitem__(node *rhs) {
 586         if (!rhs->is_int_const()) {
 587             error("getitem unimplemented");
 588             return NULL;
 589         }
 590         return this->__getitem__(rhs->int_value());
 591     }
 592     virtual int_t len() {
 593         return this->items.size();
 594     }
 595     virtual void __setitem__(node *key, node *value) {
 596         if (!key->is_int_const())
 597             error("error in list.setitem");
 598         int_t idx = key->int_value();
 599         items[this->index(idx)] = value;
 600     }
 601     virtual node *__slice__(node *start, node *end, node *step) {
 602         if ((!start->is_none() && !start->is_int_const()) ||
 603             (!end->is_none() && !end->is_int_const()) ||
 604             (!step->is_none() && !step->is_int_const()))
 605             error("slice error");
 606         int_t lo = start->is_none() ? 0 : start->int_value();
 607         int_t hi = end->is_none() ? items.size() : end->int_value();
 608         int_t st = step->is_none() ? 1 : step->int_value();
 609         list *new_list = new(allocator) list();
 610         for (; st > 0 ? (lo < hi) : (lo > hi); lo += st)
 611             new_list->append(items[lo]);
 612         return new_list;
 613     }
 614     virtual std::string repr() {
 615         std::string new_string = "[";
 616         bool first = true;
 617         for (node_list::iterator i = this->items.begin(); i != this->items.end(); i++) {
 618             if (!first)
 619                 new_string += ", ";
 620             first = false;
 621             new_string += (*i)->repr();
 622         }
 623         new_string += "]";
 624         return new_string;
 625     }
 626     virtual node *getattr(const char *key);
 627     virtual node *__iter__() { return new(allocator) list_iter(this); }
 628 };
 629
 630 class tuple: public node {
 631 private:
 632     class tuple_iter: public node {
 633     private:
 634         tuple *parent;
 635         node_list::iterator it;
 636
 637     public:
 638         tuple_iter(tuple *t) {
 639             this->parent = t;
 640             it = t->items.begin();
 641         }
 642         const char *node_type() { return "tuple_iter"; }
 643
 644         virtual void mark_live() {
 645             if (!allocator->mark_live(this, sizeof(*this)))
 646                 this->parent->mark_live();
 647         }
 648
 649         virtual node *next() {
 650             if (this->it == this->parent->items.end())
 651                 return NULL;
 652             node *ret = *this->it;
 653             ++this->it;
 654             return ret;
 655         }
 656     };
 657
 658     node_list items;
 659
 660 public:
 661     tuple() { }
 662     tuple(node_list &l) : items(l) { }
 663     tuple(int_t n, node **items): items(n) {
 664         for (int_t i = 0; i < n; i++)
 665             this->items[i] = items[i];
 666     }
 667     const char *node_type() { return "tuple"; }
 668
 669     virtual void mark_live() {
 670         if (!allocator->mark_live(this, sizeof(*this))) {
 671             for (size_t i = 0; i < this->items.size(); i++)
 672                 this->items[i]->mark_live();
 673         }
 674     }
 675
 676     int_t index(int_t base) {
 677         if (base < 0)
 678             base = items.size() + base;
 679         return base;
 680     }
 681
 682     virtual bool bool_value() { return this->len() != 0; }
 683
 684     virtual node *__contains__(node *key) {
 685         bool found = false;
 686         for (size_t i = 0; i < this->items.size(); i++)
 687             if (this->items[i]->_eq(key)) {
 688                 found = true;
 689                 break;
 690             }
 691         return create_bool_const(found);
 692     }
 693     virtual node *__getitem__(int idx) {
 694         return this->items[this->index(idx)];
 695     }
 696     virtual node *__getitem__(node *rhs) {
 697         if (!rhs->is_int_const()) {
 698             error("getitem unimplemented");
 699             return NULL;
 700         }
 701         return this->__getitem__(rhs->int_value());
 702     }
 703     virtual int_t len() {
 704         return this->items.size();
 705     }
 706     virtual std::string repr() {
 707         std::string new_string = "(";
 708         bool first = true;
 709         for (node_list::iterator i = this->items.begin(); i != this->items.end(); i++) {
 710             if (!first)
 711                 new_string += ", ";
 712             first = false;
 713             new_string += (*i)->repr();
 714         }
 715         if (this->items.size() == 1)
 716             new_string += ",";
 717         new_string += ")";
 718         return new_string;
 719     }
 720     virtual node *__iter__() { return new(allocator) tuple_iter(this); }
 721 };
 722
 723 class dict : public node {
 724 private:
 725     class dict_iter: public node {
 726     private:
 727         dict *parent;
 728         node_dict::iterator it;
 729
 730     public:
 731         dict_iter(dict *d) {
 732             this->parent = d;
 733             it = d->items.begin();
 734         }
 735         const char *node_type() { return "dict_iter"; }
 736
 737         virtual void mark_live() {
 738             if (!allocator->mark_live(this, sizeof(*this)))
 739                 this->parent->mark_live();
 740         }
 741
 742         virtual node *next() {
 743             if (this->it == this->parent->items.end())
 744                 return NULL;
 745             node *ret = this->it->second.first;
 746             ++this->it;
 747             return ret;
 748         }
 749     };
 750
 751     node_dict items;
 752
 753 public:
 754     dict() { }
 755     const char *node_type() { return "dict"; }
 756
 757     virtual void mark_live() {
 758         if (!allocator->mark_live(this, sizeof(*this))) {
 759             for (node_dict::iterator i = this->items.begin(); i != this->items.end(); i++) {
 760                 i->second.first->mark_live();
 761                 i->second.second->mark_live();
 762             }
 763         }
 764     }
 765
 766     node *lookup(node *key) {
 767         int_t hashkey;
 768         if (key->is_int_const())
 769             hashkey = key->int_value();
 770         else
 771             hashkey = key->hash();
 772         node_dict::const_iterator v = this->items.find(hashkey);
 773         if (v == this->items.end())
 774             return NULL;
 775         node *k = v->second.first;
 776         if (!k->_eq(key))
 777             return NULL;
 778         return v->second.second;
 779     }
 780     node_dict::iterator begin() { return items.begin(); }
 781     node_dict::iterator end() { return items.end(); }
 782
 783     virtual bool is_dict() { return true; }
 784     virtual bool bool_value() { return this->len() != 0; }
 785
 786     virtual node *__contains__(node *key) {
 787         return create_bool_const(this->lookup(key) != NULL);
 788     }
 789     virtual node *__getitem__(node *key) {
 790         node *value = this->lookup(key);
 791         if (value == NULL)
 792             error("cannot find %s in dict", key->repr().c_str());
 793         return value;
 794     }
 795     virtual int_t len() {
 796         return this->items.size();
 797     }
 798     virtual void __setitem__(node *key, node *value) {
 799         int_t hashkey;
 800         if (key->is_int_const())
 801             hashkey = key->int_value();
 802         else
 803             hashkey = key->hash();
 804         items[hashkey] = node_pair(key, value);
 805     }
 806     virtual std::string repr() {
 807         std::string new_string = "{";
 808         bool first = true;
 809         for (node_dict::iterator i = this->items.begin(); i != this->items.end(); i++) {
 810             if (!first)
 811                 new_string += ", ";
 812             first = false;
 813             new_string += i->second.first->repr() + ": " + i->second.second->repr();
 814         }
 815         new_string += "}";
 816         return new_string;
 817     }
 818     virtual node *getattr(const char *key);
 819     virtual node *__iter__() { return new(allocator) dict_iter(this); }
 820 };
 821
 822 class set : public node {
 823 private:
 824     class set_iter: public node {
 825     private:
 826         set *parent;
 827         node_set::iterator it;
 828
 829     public:
 830         set_iter(set *s) {
 831             this->parent = s;
 832             it = s->items.begin();
 833         }
 834         const char *node_type() { return "set_iter"; }
 835
 836         virtual void mark_live() {
 837             if (!allocator->mark_live(this, sizeof(*this)))
 838                 this->parent->mark_live();
 839         }
 840
 841         virtual node *next() {
 842             if (this->it == this->parent->items.end())
 843                 return NULL;
 844             node *ret = this->it->second;
 845             ++this->it;
 846             return ret;
 847         }
 848     };
 849
 850     node_set items;
 851
 852 public:
 853     set() { }
 854     const char *node_type() { return "set"; }
 855
 856     virtual void mark_live() {
 857         if (!allocator->mark_live(this, sizeof(*this))) {
 858             for (node_set::iterator i = this->items.begin(); i != this->items.end(); i++)
 859                 i->second->mark_live();
 860         }
 861     }
 862
 863     node *lookup(node *key) {
 864         int_t hashkey;
 865         if (key->is_int_const())
 866             hashkey = key->int_value();
 867         else
 868             hashkey = key->hash();
 869         node_set::const_iterator v = this->items.find(hashkey);
 870         if (v == this->items.end() || !v->second->_eq(key))
 871             return NULL;
 872         return v->second;
 873     }
 874     void add(node *key) {
 875         int_t hashkey;
 876         if (key->is_int_const())
 877             hashkey = key->int_value();
 878         else
 879             hashkey = key->hash();
 880         items[hashkey] = key;
 881     }
 882
 883     virtual bool is_set() { return true; }
 884     virtual bool bool_value() { return this->len() != 0; }
 885
 886     virtual node *__contains__(node *key) {
 887         return create_bool_const(this->lookup(key) != NULL);
 888     }
 889     virtual int_t len() {
 890         return this->items.size();
 891     }
 892     virtual std::string repr() {
 893         if (!this->items.size())
 894             return "set()";
 895         std::string new_string = "{";
 896         bool first = true;
 897         for (node_set::iterator i = this->items.begin(); i != this->items.end(); i++) {
 898             if (!first)
 899                 new_string += ", ";
 900             first = false;
 901             new_string += i->second->repr();
 902         }
 903         new_string += "}";
 904         return new_string;
 905     }
 906     virtual node *getattr(const char *key);
 907     virtual node *__iter__() { return new(allocator) set_iter(this); }
 908 };
 909
 910 class object : public node {
 911 private:
 912     dict *items;
 913
 914 public:
 915     object() {
 916         this->items = new(allocator) dict();
 917     }
 918     const char *node_type() { return "object"; }
 919
 920     virtual void mark_live() {
 921         if (!allocator->mark_live(this, sizeof(*this)))
 922             this->items->mark_live();
 923     }
 924
 925     virtual bool bool_value() { return true; }
 926
 927     virtual node *getattr(const char *key) {
 928         return items->__getitem__(new(allocator) string_const(key));
 929     }
 930     virtual void __setattr__(node *key, node *value) {
 931         items->__setitem__(key, value);
 932     }
 933     virtual bool _eq(node *rhs) {
 934         return this == rhs;
 935     }
 936 };
 937
 938 class file : public node {
 939 private:
 940     FILE *f;
 941
 942 public:
 943     file(const char *path, const char *mode) {
 944         f = fopen(path, mode);
 945         if (!f)
 946             error("%s: file not found", path);
 947     }
 948     const char *node_type() { return "file"; }
 949
 950     MARK_LIVE_FN
 951
 952     node *read(int_t len) {
 953         static char buf[64*1024];
 954         size_t ret = fread(buf, 1, len, this->f);
 955         std::string s(buf, ret);
 956         return new(allocator) string_const(s);
 957     }
 958
 959     virtual bool is_file() { return true; }
 960 };
 961
 962 class range: public node {
 963 private:
 964     class range_iter: public node {
 965     private:
 966         int_t start, end, step;
 967
 968     public:
 969         range_iter(range *r) {
 970             this->start = r->start;
 971             this->end = r->end;
 972             this->step = r->step;
 973         }
 974         const char *node_type() { return "range_iter"; }
 975
 976         MARK_LIVE_FN
 977
 978         virtual node *next() {
 979             if (step > 0) {
 980                 if (this->start >= this->end)
 981                     return NULL;
 982             }
 983             else {
 984                 if (this->start <= this->end)
 985                     return NULL;
 986             }
 987             node *ret = new(allocator) int_const(this->start);
 988             this->start += this->step;
 989             return ret;
 990         }
 991     };
 992
 993     int_t start, end, step;
 994
 995 public:
 996     range(int_t start, int_t end, int_t step) {
 997         this->start = start;
 998         this->end = end;
 999         this->step = step;
1000     }
1001     const char *node_type() { return "range"; }
1002
1003     MARK_LIVE_FN
1004
1005     virtual node *__iter__() { return new(allocator) range_iter(this); }
1006
1007     virtual std::string repr() {
1008         char buf[128];
1009         if (step == 1) {
1010             sprintf(buf, "range(%ld, %ld)", this->start, this->end);
1011         }
1012         else {
1013             sprintf(buf, "range(%ld, %ld, %ld)", this->start, this->end, this->step);
1014         }
1015         return buf;
1016     }
1017 };
1018
1019 typedef node *(*fptr)(context *globals, context *parent_ctx, list *args, dict *kwargs);
1020
1021 class bound_method : public node {
1022 private:
1023     node *self;
1024     node *function;
1025
1026 public:
1027     bound_method(node *self, node *function) {
1028         this->self = self;
1029         this->function = function;
1030     }
1031     const char *node_type() { return "bound_method"; }
1032
1033     virtual void mark_live() {
1034         if (!allocator->mark_live(this, sizeof(*this))) {
1035             this->self->mark_live();
1036             this->function->mark_live();
1037         }
1038     }
1039
1040     virtual bool is_function() { return true; } // XXX is it?
1041
1042     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1043         if (!args->is_list())
1044             error("call with non-list args?");
1045         ((list *)args)->prepend(this->self);
1046         return this->function->__call__(globals, ctx, args, kwargs);
1047     }
1048 };
1049
1050 class function_def : public node {
1051 private:
1052     fptr base_function;
1053
1054 public:
1055     function_def(fptr base_function) {
1056         this->base_function = base_function;
1057     }
1058     const char *node_type() { return "function"; }
1059
1060     MARK_LIVE_FN
1061
1062     virtual bool is_function() { return true; }
1063
1064     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1065         return this->base_function(globals, ctx, args, kwargs);
1066     }
1067 };
1068
1069 class class_def : public node {
1070 private:
1071     std::string name;
1072     dict *items;
1073
1074 public:
1075     class_def(std::string name, void (*creator)(class_def *)) {
1076         this->name = name;
1077         this->items = new(allocator) dict();
1078         creator(this);
1079     }
1080     const char *node_type() { return "class"; }
1081
1082     virtual void mark_live() {
1083         if (!allocator->mark_live(this, sizeof(*this)))
1084             this->items->mark_live();
1085     }
1086
1087     node *load(const char *name) {
1088         return items->__getitem__(new(allocator) string_const(name));
1089     }
1090     void store(const char *name, node *value) {
1091         items->__setitem__(new(allocator) string_const(name), value);
1092     }
1093
1094     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1095         node *init = this->load("__init__");
1096         node *obj = new(allocator) object();
1097
1098         obj->__setattr__(new(allocator) string_const("__class__"), this);
1099
1100         // Create bound methods
1101         for (node_dict::iterator i = items->begin(); i != items->end(); i++)
1102             if (i->second.second->is_function())
1103                 obj->__setattr__(i->second.first, new(allocator) bound_method(obj, i->second.second));
1104
1105         ((list *)args)->prepend(obj);
1106         context *call_ctx = new(allocator) context(ctx);
1107         init->__call__(globals, call_ctx, args, kwargs);
1108         return obj;
1109     }
1110     virtual node *getattr(const char *attr) {
1111         return this->load(attr);
1112     }
1113     virtual std::string repr() {
1114         return std::string("<class '") + this->name + "'>";
1115     }
1116 };
1117
1118 bool_const bool_singleton_True(true);
1119 bool_const bool_singleton_False(false);
1120 none_const none_singleton(0);
1121
1122 inline node *create_bool_const(bool b) {
1123     return b ? &bool_singleton_True : &bool_singleton_False;
1124 }
1125
1126 #define NO_KWARGS_N_ARGS(name, n_args) \
1127     if (kwargs->len()) \
1128         error(name "() does not take keyword arguments"); \
1129     if (args->len() != n_args) \
1130         error("wrong number of arguments to " name "()")
1131
1132 #define NO_KWARGS_MAX_ARGS(name, max_args) \
1133     if (kwargs->len()) \
1134         error(name "() does not take keyword arguments"); \
1135     if (args->len() > max_args) \
1136         error("too many arguments to " name "()")
1137
1138 // Builtin classes
1139 #define LIST_BUILTIN_CLASSES(x) \
1140     x(bool) \
1141     x(dict) \
1142     x(enumerate) \
1143     x(int) \
1144     x(list) \
1145     x(range) \
1146     x(reversed) \
1147     x(set) \
1148     x(str) \
1149     x(tuple) \
1150     x(zip) \
1151
1152 #define LIST_BUILTIN_CLASS_METHODS(x) \
1153     x(dict, get) \
1154     x(dict, keys) \
1155     x(list, append) \
1156     x(list, index) \
1157     x(list, pop) \
1158     x(set, add) \
1159     x(str, join) \
1160     x(str, split) \
1161     x(str, upper) \
1162     x(str, startswith) \
1163
1164 class builtin_method_def: public function_def {
1165 public:
1166     builtin_method_def(fptr base_function): function_def(base_function) {}
1167
1168     MARK_LIVE_SINGLETON_FN
1169 };
1170
1171 #define BUILTIN_METHOD(class_name, method_name) builtin_method_def builtin_method_##class_name##_##method_name(builtin_##class_name##_##method_name);
1172 LIST_BUILTIN_CLASS_METHODS(BUILTIN_METHOD)
1173 #undef BUILTIN_METHOD
1174
1175 void _dummy__create_(class_def *ctx) {}
1176
1177 class builtin_class_def_singleton: public class_def {
1178 public:
1179     builtin_class_def_singleton(std::string name): class_def(name, _dummy__create_) {}
1180
1181     MARK_LIVE_SINGLETON_FN
1182 };
1183
1184 class bool_class_def_singleton: public builtin_class_def_singleton {
1185 public:
1186     bool_class_def_singleton(): builtin_class_def_singleton("bool") {}
1187
1188     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1189         NO_KWARGS_MAX_ARGS("bool", 1);
1190         if (!args->len())
1191             return &bool_singleton_False;
1192         node *arg = args->__getitem__(0);
1193         return create_bool_const(arg->bool_value());
1194     }
1195 };
1196
1197 class dict_class_def_singleton: public builtin_class_def_singleton {
1198 public:
1199     dict_class_def_singleton(): builtin_class_def_singleton("dict") {}
1200
1201     virtual node *getattr(const char *key) {
1202         if (!strcmp(key, "get"))
1203             return &builtin_method_dict_get;
1204         if (!strcmp(key, "keys"))
1205             return &builtin_method_dict_keys;
1206         error("dict has no attribute %s", key);
1207         return NULL;
1208     }
1209
1210     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1211         NO_KWARGS_N_ARGS("dict", 0);
1212         return new(allocator) dict();
1213     }
1214 };
1215
1216 class enumerate_class_def_singleton: public builtin_class_def_singleton {
1217 public:
1218     enumerate_class_def_singleton(): builtin_class_def_singleton("enumerate") {}
1219
1220     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1221         NO_KWARGS_N_ARGS("enumerate", 1);
1222         node *arg = args->__getitem__(0);
1223         node *iter = arg->__iter__();
1224         list *ret = new(allocator) list;
1225         int i = 0;
1226         for (node *item = iter->next(); item; item = iter->next(), i++) {
1227             node *pair[2];
1228             pair[0] = new(allocator) int_const(i);
1229             pair[1] = item;
1230             ret->append(new(allocator) tuple(2, pair));
1231         }
1232         return ret;
1233     }
1234 };
1235
1236 class int_class_def_singleton: public builtin_class_def_singleton {
1237 public:
1238     int_class_def_singleton(): builtin_class_def_singleton("int") {}
1239
1240     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1241         NO_KWARGS_MAX_ARGS("int", 1);
1242         if (!args->len())
1243             return new(allocator) int_const(0);
1244         node *arg = args->__getitem__(0);
1245         if (arg->is_int_const())
1246             return arg;
1247         if (arg->is_string()) {
1248             std::string s = arg->string_value();
1249             return new(allocator) int_const(atoi(s.c_str()));
1250         }
1251         error("don't know how to handle argument to int()");
1252     }
1253 };
1254
1255 class list_class_def_singleton: public builtin_class_def_singleton {
1256 public:
1257     list_class_def_singleton(): builtin_class_def_singleton("list") {}
1258
1259     virtual node *getattr(const char *key) {
1260         if (!strcmp(key, "append"))
1261             return &builtin_method_list_append;
1262         if (!strcmp(key, "index"))
1263             return &builtin_method_list_index;
1264         if (!strcmp(key, "pop"))
1265             return &builtin_method_list_pop;
1266         error("list has no attribute %s", key);
1267     }
1268
1269     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1270         NO_KWARGS_MAX_ARGS("list", 1);
1271         list *ret = new(allocator) list();
1272         if (!args->len())
1273             return ret;
1274         node *arg = args->__getitem__(0);
1275         node *iter = arg->__iter__();
1276         for (node *item = iter->next(); item; item = iter->next())
1277             ret->append(item);
1278         return ret;
1279     }
1280 };
1281
1282 class range_class_def_singleton: public builtin_class_def_singleton {
1283 public:
1284     range_class_def_singleton(): builtin_class_def_singleton("range") {}
1285
1286     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1287         int_t start = 0, end, step = 1;
1288
1289         if (args->len() == 1)
1290             end = args->__getitem__(0)->int_value();
1291         else if (args->len() == 2) {
1292             start = args->__getitem__(0)->int_value();
1293             end = args->__getitem__(1)->int_value();
1294         }
1295         else if (args->len() == 3) {
1296             start = args->__getitem__(0)->int_value();
1297             end = args->__getitem__(1)->int_value();
1298             step = args->__getitem__(2)->int_value();
1299         }
1300         else
1301             error("too many arguments to range()");
1302
1303         return new(allocator) range(start, end, step);
1304     }
1305 };
1306
1307 class reversed_class_def_singleton: public builtin_class_def_singleton {
1308 public:
1309     reversed_class_def_singleton(): builtin_class_def_singleton("reversed") {}
1310
1311     node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1312         NO_KWARGS_N_ARGS("reversed", 1);
1313         node *item = args->__getitem__(0);
1314         if (!item->is_list())
1315             error("cannot call reversed on non-list");
1316         list *plist = (list *)item;
1317         // sigh, I hate c++
1318         node_list new_list;
1319         new_list.resize(plist->len());
1320         std::reverse_copy(plist->begin(), plist->end(), new_list.begin());
1321
1322         return new(allocator) list(new_list);
1323     }
1324 };
1325
1326 class set_class_def_singleton: public builtin_class_def_singleton {
1327 public:
1328     set_class_def_singleton(): builtin_class_def_singleton("set") {}
1329
1330     virtual node *getattr(const char *key) {
1331         if (!strcmp(key, "add"))
1332             return &builtin_method_set_add;
1333         error("set has no attribute %s", key);
1334         return NULL;
1335     }
1336
1337     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1338         NO_KWARGS_MAX_ARGS("set", 1);
1339         set *ret = new(allocator) set();
1340         if (!args->len())
1341             return ret;
1342         node *arg = args->__getitem__(0);
1343         node *iter = arg->__iter__();
1344         for (node *item = iter->next(); item; item = iter->next())
1345             ret->add(item);
1346         return ret;
1347     }
1348 };
1349
1350 class str_class_def_singleton: public builtin_class_def_singleton {
1351 public:
1352     str_class_def_singleton(): builtin_class_def_singleton("str") {}
1353
1354     virtual node *getattr(const char *key) {
1355         if (!strcmp(key, "join"))
1356             return &builtin_method_str_join;
1357         if (!strcmp(key, "split"))
1358             return &builtin_method_str_split;
1359         if (!strcmp(key, "upper"))
1360             return &builtin_method_str_upper;
1361         if (!strcmp(key, "startswith"))
1362             return &builtin_method_str_startswith;
1363         error("str has no attribute %s", key);
1364     }
1365
1366     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1367         NO_KWARGS_MAX_ARGS("str", 1);
1368         if (!args->len())
1369             return new(allocator) string_const("");
1370         node *arg = args->__getitem__(0);
1371         return arg->__str__();
1372     }
1373 };
1374
1375 class tuple_class_def_singleton: public builtin_class_def_singleton {
1376 public:
1377     tuple_class_def_singleton(): builtin_class_def_singleton("tuple") {}
1378
1379     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1380         NO_KWARGS_MAX_ARGS("tuple", 1);
1381         if (!args->len())
1382             return new(allocator) tuple;
1383         node *arg = args->__getitem__(0);
1384         node *iter = arg->__iter__();
1385         node_list l;
1386         for (node *item = iter->next(); item; item = iter->next())
1387             l.push_back(item);
1388         return new(allocator) tuple(l);
1389     }
1390 };
1391
1392 class zip_class_def_singleton: public builtin_class_def_singleton {
1393 public:
1394     zip_class_def_singleton(): builtin_class_def_singleton("zip") {}
1395
1396     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1397         NO_KWARGS_N_ARGS("zip", 2);
1398         node *list1 = args->__getitem__(0);
1399         node *list2 = args->__getitem__(1);
1400
1401         if (!list1->is_list() || !list2->is_list() || list1->len() != list2->len())
1402             error("bad arguments to zip()");
1403
1404         list *plist = new(allocator) list();
1405         for (int_t i = 0; i < list1->len(); i++) {
1406             node *pair[2];
1407             pair[0] = list1->__getitem__(i);
1408             pair[1] = list2->__getitem__(i);
1409             plist->append(new(allocator) tuple(2, pair));
1410         }
1411
1412         return plist;
1413     }
1414 };
1415
1416 #define BUILTIN_CLASS(name) name##_class_def_singleton builtin_class_##name;
1417 LIST_BUILTIN_CLASSES(BUILTIN_CLASS)
1418 #undef BUILTIN_CLASS
1419
1420 node *node::__getattr__(node *key) {
1421     if (!key->is_string())
1422         error("getattr with non-string");
1423     return this->getattr(key->string_value().c_str());
1424 }
1425
1426 node *node::__hash__() {
1427     return new(allocator) int_const(this->hash());
1428 }
1429
1430 node *node::__len__() {
1431     return new(allocator) int_const(this->len());
1432 }
1433
1434 node *node::__not__() {
1435     return create_bool_const(!this->bool_value());
1436 }
1437
1438 node *node::__is__(node *rhs) {
1439     return create_bool_const(this == rhs);
1440 }
1441
1442 node *node::__isnot__(node *rhs) {
1443     return create_bool_const(this != rhs);
1444 }
1445
1446 node *node::__repr__() {
1447     return new(allocator) string_const(this->repr());
1448 }
1449
1450 node *node::__str__() {
1451     return new(allocator) string_const(this->str());
1452 }
1453
1454 bool none_const::_eq(node *rhs) {
1455     return (this == rhs);
1456 }
1457
1458 node *int_const::getattr(const char *key) {
1459     if (!strcmp(key, "__class__"))
1460         return &builtin_class_int;
1461     error("int has no attribute %s", key);
1462     return NULL;
1463 }
1464
1465 std::string int_const::repr() {
1466     char buf[32];
1467     sprintf(buf, "%" PRId64, this->value);
1468     return std::string(buf);
1469 }
1470
1471 std::string bool_const::repr() {
1472     return std::string(this->value ? "True" : "False");
1473 }
1474
1475 node *list::__add__(node *rhs) {
1476     if (!rhs->is_list())
1477         error("list add error");
1478     list *plist = new(allocator) list();
1479     node_list *rhs_list = rhs->list_value();
1480     for (node_list::iterator i = this->begin(); i != this->end(); i++)
1481         plist->append(*i);
1482     for (node_list::iterator i = rhs_list->begin(); i != rhs_list->end(); i++)
1483         plist->append(*i);
1484     return plist;
1485 }
1486
1487 node *list::__mul__(node *rhs) {
1488     if (!rhs->is_int_const())
1489         error("list mul error");
1490     list *plist = new(allocator) list();
1491     for (int_t x = rhs->int_value(); x > 0; x--)
1492         for (node_list::iterator i = this->begin(); i != this->end(); i++)
1493             plist->append(*i);
1494     return plist;
1495 }
1496
1497 node *list::getattr(const char *key) {
1498     if (!strcmp(key, "__class__"))
1499         return &builtin_class_list;
1500     return new(allocator) bound_method(this, builtin_class_list.getattr(key));
1501 }
1502
1503 node *dict::getattr(const char *key) {
1504     if (!strcmp(key, "__class__"))
1505         return &builtin_class_dict;
1506     return new(allocator) bound_method(this, builtin_class_dict.getattr(key));
1507 }
1508
1509 node *set::getattr(const char *key) {
1510     if (!strcmp(key, "__class__"))
1511         return &builtin_class_set;
1512     return new(allocator) bound_method(this, builtin_class_set.getattr(key));
1513 }
1514
1515 node *string_const::getattr(const char *key) {
1516     if (!strcmp(key, "__class__"))
1517         return &builtin_class_str;
1518     return new(allocator) bound_method(this, builtin_class_str.getattr(key));
1519 }
1520
1521 // This entire function is very stupidly implemented.
1522 node *string_const::__mod__(node *rhs) {
1523     std::ostringstream new_string;
1524     // HACK for now...
1525     if (!rhs->is_list()) {
1526         list *l = new(allocator) list();
1527         l->append(rhs);
1528         rhs = l;
1529     }
1530     int_t args = 0;
1531     for (const char *c = value.c_str(); *c; c++) {
1532         if (*c == '%') {
1533             char fmt_buf[64], buf[64];
1534             char *fmt = fmt_buf;
1535             *fmt++ = '%';
1536             c++;
1537             // Copy over formatting data: only numbers allowed as modifiers now
1538             while (*c && isdigit(*c))
1539                 *fmt++ = *c++;
1540
1541             if ((unsigned)(fmt - fmt_buf) >= sizeof(buf))
1542                 error("I do believe you've made a terrible mistake whilst formatting a string!");
1543             if (args >= rhs->len())
1544                 error("not enough arguments for string format");
1545             node *arg = rhs->__getitem__(args++);
1546             if (*c == 's') {
1547                 *fmt++ = 's';
1548                 *fmt = 0;
1549                 sprintf(buf, fmt_buf, arg->str().c_str());
1550             }
1551             else if (*c == 'd' || *c == 'i' || *c == 'X') {
1552                 *fmt++ = 'l';
1553                 *fmt++ = 'l';
1554                 *fmt++ = *c;
1555                 *fmt = 0;
1556                 sprintf(buf, fmt_buf, arg->int_value());
1557             }
1558             else if (*c == 'c') {
1559                 *fmt++ = 'c';
1560                 *fmt = 0;
1561                 int_t char_value;
1562                 if (arg->is_string())
1563                     char_value = (unsigned char)arg->string_value()[0];
1564                 else
1565                     char_value = arg->int_value();
1566                 sprintf(buf, fmt_buf, char_value);
1567             }
1568             else
1569                 error("bad format specifier '%c' in \"%s\"", *c, value.c_str());
1570             new_string << buf;
1571         }
1572         else
1573             new_string << *c;
1574     }
1575     return new(allocator) string_const(new_string.str());
1576 }
1577
1578 node *string_const::__add__(node *rhs) {
1579     if (!rhs->is_string())
1580         error("bad argument to str.add");
1581     std::string new_string = this->value + rhs->string_value();
1582     return new(allocator) string_const(new_string);
1583 }
1584
1585 node *string_const::__mul__(node *rhs) {
1586     if (!rhs->is_int_const() || rhs->int_value() < 0)
1587         error("bad argument to str.mul");
1588     std::string new_string;
1589     for (int_t i = 0; i < rhs->int_value(); i++)
1590         new_string += this->value;
1591     return new(allocator) string_const(new_string);
1592 }
1593
1594 ////////////////////////////////////////////////////////////////////////////////
1595 // Builtins ////////////////////////////////////////////////////////////////////
1596 ////////////////////////////////////////////////////////////////////////////////
1597
1598 class builtin_function_def: public function_def {
1599 private:
1600     const char *name;
1601
1602 public:
1603     builtin_function_def(const char *name, fptr base_function): function_def(base_function) {
1604         this->name = name;
1605     }
1606     const char *node_type() { return "builtin_function"; }
1607
1608     MARK_LIVE_SINGLETON_FN
1609
1610     virtual std::string repr() {
1611         return std::string("<built-in function ") + this->name + ">";
1612     }
1613 };
1614
1615 #define LIST_BUILTIN_FUNCTIONS(x) \
1616     x(fread) \
1617     x(isinstance) \
1618     x(len) \
1619     x(open) \
1620     x(ord) \
1621     x(print) \
1622     x(print_nonl) \
1623     x(repr) \
1624     x(sorted) \
1625
1626 node *builtin_dict_get(context *globals, context *ctx, list *args, dict *kwargs) {
1627     NO_KWARGS_N_ARGS("dict.get", 3);
1628     node *self = args->__getitem__(0);
1629     node *key = args->__getitem__(1);
1630
1631     node *value = ((dict *)self)->lookup(key);
1632     if (!value)
1633         value = args->__getitem__(2);
1634
1635     return value;
1636 }
1637
1638 node *builtin_dict_keys(context *globals, context *ctx, list *args, dict *kwargs) {
1639     NO_KWARGS_N_ARGS("dict.keys", 1);
1640     dict *self = (dict *)args->__getitem__(0);
1641
1642     list *plist = new(allocator) list();
1643     for (node_dict::iterator i = self->begin(); i != self->end(); i++)
1644         plist->append(i->second.first);
1645
1646     return plist;
1647 }
1648
1649 node *builtin_fread(context *globals, context *ctx, list *args, dict *kwargs) {
1650     NO_KWARGS_N_ARGS("fread", 2);
1651     node *f = args->__getitem__(0);
1652     node *len = args->__getitem__(1);
1653     if (!f->is_file() || !len->is_int_const())
1654         error("bad arguments to fread()");
1655     return ((file *)f)->read(len->int_value());
1656 }
1657
1658 node *builtin_isinstance(context *globals, context *ctx, list *args, dict *kwargs) {
1659     NO_KWARGS_N_ARGS("isinstance", 2);
1660     node *obj = args->__getitem__(0);
1661     node *arg_class = args->__getitem__(1);
1662
1663     node *obj_class = obj->getattr("__class__");
1664     return create_bool_const(obj_class == arg_class);
1665 }
1666
1667 node *builtin_len(context *globals, context *ctx, list *args, dict *kwargs) {
1668     NO_KWARGS_N_ARGS("len", 1);
1669     return args->__getitem__(0)->__len__();
1670 }
1671
1672 node *builtin_list_append(context *globals, context *ctx, list *args, dict *kwargs) {
1673     NO_KWARGS_N_ARGS("list.append", 2);
1674     node *self = args->__getitem__(0);
1675     node *item = args->__getitem__(1);
1676
1677     ((list *)self)->append(item);
1678
1679     return &none_singleton;
1680 }
1681
1682 node *builtin_list_index(context *globals, context *ctx, list *args, dict *kwargs) {
1683     NO_KWARGS_N_ARGS("list.index", 2);
1684     node *self = args->__getitem__(0);
1685     node *key = args->__getitem__(1);
1686
1687     for (int_t i = 0; i < self->len(); i++)
1688         if (self->__getitem__(i)->_eq(key))
1689             return new(allocator) int_const(i);
1690     error("item not found in list");
1691     return &none_singleton;
1692 }
1693
1694 node *builtin_list_pop(context *globals, context *ctx, list *args, dict *kwargs) {
1695     NO_KWARGS_N_ARGS("pop", 1);
1696     list *self = (list *)args->__getitem__(0);
1697
1698     return self->pop();
1699 }
1700
1701 node *builtin_open(context *globals, context *ctx, list *args, dict *kwargs) {
1702     NO_KWARGS_N_ARGS("open", 2);
1703     node *path = args->__getitem__(0);
1704     node *mode = args->__getitem__(1);
1705     if (!path->is_string() || !mode->is_string())
1706         error("bad arguments to open()");
1707     file *f = new(allocator) file(path->string_value().c_str(), mode->string_value().c_str());
1708     return f;
1709 }
1710
1711 node *builtin_ord(context *globals, context *ctx, list *args, dict *kwargs) {
1712     NO_KWARGS_N_ARGS("ord", 1);
1713     node *arg = args->__getitem__(0);
1714     if (!arg->is_string() || arg->len() != 1)
1715         error("bad arguments to ord()");
1716     return new(allocator) int_const((unsigned char)arg->string_value()[0]);
1717 }
1718
1719 node *builtin_print(context *globals, context *ctx, list *args, dict *kwargs) {
1720     std::string new_string;
1721     for (int_t i = 0; i < args->len(); i++) {
1722         if (i)
1723             new_string += " ";
1724         node *s = args->__getitem__(i);
1725         new_string += s->str();
1726     }
1727     printf("%s\n", new_string.c_str());
1728     return &none_singleton;
1729 }
1730
1731 node *builtin_print_nonl(context *globals, context *ctx, list *args, dict *kwargs) {
1732     NO_KWARGS_N_ARGS("print_nonl", 1);
1733     node *s = args->__getitem__(0);
1734     printf("%s", s->str().c_str());
1735     return &none_singleton;
1736 }
1737
1738 node *builtin_repr(context *globals, context *ctx, list *args, dict *kwargs) {
1739     NO_KWARGS_N_ARGS("repr", 1);
1740     node *arg = args->__getitem__(0);
1741     return arg->__repr__();
1742 }
1743
1744 node *builtin_set_add(context *globals, context *ctx, list *args, dict *kwargs) {
1745     NO_KWARGS_N_ARGS("set.add", 2);
1746     node *self = args->__getitem__(0);
1747     node *item = args->__getitem__(1);
1748
1749     ((set *)self)->add(item);
1750
1751     return &none_singleton;
1752 }
1753
1754 bool compare_nodes(node *lhs, node *rhs) {
1755     return lhs->_lt(rhs);
1756 }
1757
1758 node *builtin_sorted(context *globals, context *ctx, list *args, dict *kwargs) {
1759     NO_KWARGS_N_ARGS("sorted", 1);
1760     node *item = args->__getitem__(0);
1761     if (!item->is_list())
1762         error("cannot call sorted on non-list");
1763     list *plist = (list *)item;
1764     // sigh, I hate c++
1765     node_list new_list;
1766     new_list.resize(plist->len());
1767     std::copy(plist->begin(), plist->end(), new_list.begin());
1768     std::stable_sort(new_list.begin(), new_list.end(), compare_nodes);
1769
1770     return new(allocator) list(new_list);
1771 }
1772
1773 node *builtin_str_join(context *globals, context *ctx, list *args, dict *kwargs) {
1774     NO_KWARGS_N_ARGS("str.join", 2);
1775     node *self = args->__getitem__(0);
1776     node *item = args->__getitem__(1);
1777     if (!self->is_string() || !item->is_list())
1778         error("bad arguments to str.join()");
1779
1780     list *joined = (list *)item;
1781     std::string s;
1782     for (node_list::iterator i = joined->begin(); i != joined->end(); i++) {
1783         s += (*i)->str();
1784         if (i + 1 != joined->end())
1785             s += self->string_value();
1786     }
1787     return new(allocator) string_const(s);
1788 }
1789
1790 node *builtin_str_split(context *globals, context *ctx, list *args, dict *kwargs) {
1791     NO_KWARGS_N_ARGS("str.split", 2);
1792     node *self = args->__getitem__(0);
1793     node *item = args->__getitem__(1);
1794     if (!self->is_string() || !item->is_string() || (item->len() != 1))
1795         error("bad argument to str.upper()");
1796     string_const *str = (string_const *)self;
1797     char split = item->string_value()[0];
1798     list *ret = new(allocator) list;
1799     std::string s;
1800     for (std::string::iterator c = str->begin(); c != str->end(); ++c) {
1801         if (*c == split) {
1802             ret->append(new(allocator) string_const(s));
1803             s.clear();
1804         }
1805         else {
1806             s += *c;
1807         }
1808     }
1809     ret->append(new(allocator) string_const(s));
1810     return ret;
1811 }
1812
1813 node *builtin_str_upper(context *globals, context *ctx, list *args, dict *kwargs) {
1814     NO_KWARGS_N_ARGS("str.upper", 1);
1815     node *self = args->__getitem__(0);
1816     if (!self->is_string())
1817         error("bad argument to str.upper()");
1818     string_const *str = (string_const *)self;
1819
1820     std::string new_string;
1821     for (std::string::iterator c = str->begin(); c != str->end(); c++)
1822         new_string += toupper(*c);
1823
1824     return new(allocator) string_const(new_string);
1825 }
1826
1827 node *builtin_str_startswith(context *globals, context *ctx, list *args, dict *kwargs) {
1828     NO_KWARGS_N_ARGS("str.startswith", 2);
1829     node *self = args->__getitem__(0);
1830     node *prefix = args->__getitem__(1);
1831     if (!self->is_string() || !prefix->is_string())
1832         error("bad arguments to str.startswith()");
1833
1834     std::string s1 = self->string_value();
1835     std::string s2 = prefix->string_value();
1836     return create_bool_const(s1.compare(0, s2.size(), s2) == 0);
1837 }
1838
1839 #define BUILTIN_FUNCTION(name) builtin_function_def builtin_function_##name(#name, builtin_##name);
1840 LIST_BUILTIN_FUNCTIONS(BUILTIN_FUNCTION)
1841 #undef BUILTIN_FUNCTION
1842
1843 void init_context(context *ctx, int_t argc, char **argv) {
1844 #define BUILTIN_FUNCTION(name) ctx->store(#name, &builtin_function_##name);
1845 LIST_BUILTIN_FUNCTIONS(BUILTIN_FUNCTION)
1846 #undef BUILTIN_FUNCTION
1847
1848 #define BUILTIN_CLASS(name) ctx->store(#name, &builtin_class_##name);
1849 LIST_BUILTIN_CLASSES(BUILTIN_CLASS)
1850 #undef BUILTIN_CLASS
1851
1852     ctx->store("__name__", new(allocator) string_const("__main__"));
1853     list *plist = new(allocator) list();
1854     for (int_t a = 0; a < argc; a++)
1855         plist->append(new(allocator) string_const(argv[a]));
1856     ctx->store("__args__", plist);
1857 }
1858
1859 void collect_garbage(context *ctx, node *ret_val) {
1860     static int gc_tick = 0;
1861     if (++gc_tick > 128) {
1862         gc_tick = 0;
1863
1864         allocator->mark_dead();
1865
1866         ctx->mark_live(ret_val != NULL);
1867
1868         if (ret_val)
1869             ret_val->mark_live();
1870     }
1871 }