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     const char *node_type() { return "tuple"; }
 664
 665     virtual void mark_live() {
 666         if (!allocator->mark_live(this, sizeof(*this))) {
 667             for (size_t i = 0; i < this->items.size(); i++)
 668                 this->items[i]->mark_live();
 669         }
 670     }
 671
 672     int_t index(int_t base) {
 673         if (base < 0)
 674             base = items.size() + base;
 675         return base;
 676     }
 677
 678     virtual bool bool_value() { return this->len() != 0; }
 679
 680     virtual node *__contains__(node *key) {
 681         bool found = false;
 682         for (size_t i = 0; i < this->items.size(); i++)
 683             if (this->items[i]->_eq(key)) {
 684                 found = true;
 685                 break;
 686             }
 687         return create_bool_const(found);
 688     }
 689     virtual node *__getitem__(int idx) {
 690         return this->items[this->index(idx)];
 691     }
 692     virtual node *__getitem__(node *rhs) {
 693         if (!rhs->is_int_const()) {
 694             error("getitem unimplemented");
 695             return NULL;
 696         }
 697         return this->__getitem__(rhs->int_value());
 698     }
 699     virtual int_t len() {
 700         return this->items.size();
 701     }
 702     virtual std::string repr() {
 703         std::string new_string = "(";
 704         bool first = true;
 705         for (node_list::iterator i = this->items.begin(); i != this->items.end(); i++) {
 706             if (!first)
 707                 new_string += ", ";
 708             first = false;
 709             new_string += (*i)->repr();
 710         }
 711         if (this->items.size() == 1)
 712             new_string += ",";
 713         new_string += ")";
 714         return new_string;
 715     }
 716     virtual node *__iter__() { return new(allocator) tuple_iter(this); }
 717 };
 718
 719 class dict : public node {
 720 private:
 721     class dict_iter: public node {
 722     private:
 723         dict *parent;
 724         node_dict::iterator it;
 725
 726     public:
 727         dict_iter(dict *d) {
 728             this->parent = d;
 729             it = d->items.begin();
 730         }
 731         const char *node_type() { return "dict_iter"; }
 732
 733         virtual void mark_live() {
 734             if (!allocator->mark_live(this, sizeof(*this)))
 735                 this->parent->mark_live();
 736         }
 737
 738         virtual node *next() {
 739             if (this->it == this->parent->items.end())
 740                 return NULL;
 741             node *ret = this->it->second.first;
 742             ++this->it;
 743             return ret;
 744         }
 745     };
 746
 747     node_dict items;
 748
 749 public:
 750     dict() { }
 751     const char *node_type() { return "dict"; }
 752
 753     virtual void mark_live() {
 754         if (!allocator->mark_live(this, sizeof(*this))) {
 755             for (node_dict::iterator i = this->items.begin(); i != this->items.end(); i++) {
 756                 i->second.first->mark_live();
 757                 i->second.second->mark_live();
 758             }
 759         }
 760     }
 761
 762     node *lookup(node *key) {
 763         int_t hashkey;
 764         if (key->is_int_const())
 765             hashkey = key->int_value();
 766         else
 767             hashkey = key->hash();
 768         node_dict::const_iterator v = this->items.find(hashkey);
 769         if (v == this->items.end())
 770             return NULL;
 771         node *k = v->second.first;
 772         if (!k->_eq(key))
 773             return NULL;
 774         return v->second.second;
 775     }
 776     node_dict::iterator begin() { return items.begin(); }
 777     node_dict::iterator end() { return items.end(); }
 778
 779     virtual bool is_dict() { return true; }
 780     virtual bool bool_value() { return this->len() != 0; }
 781
 782     virtual node *__contains__(node *key) {
 783         return create_bool_const(this->lookup(key) != NULL);
 784     }
 785     virtual node *__getitem__(node *key) {
 786         node *value = this->lookup(key);
 787         if (value == NULL)
 788             error("cannot find %s in dict", key->repr().c_str());
 789         return value;
 790     }
 791     virtual int_t len() {
 792         return this->items.size();
 793     }
 794     virtual void __setitem__(node *key, node *value) {
 795         int_t hashkey;
 796         if (key->is_int_const())
 797             hashkey = key->int_value();
 798         else
 799             hashkey = key->hash();
 800         items[hashkey] = node_pair(key, value);
 801     }
 802     virtual std::string repr() {
 803         std::string new_string = "{";
 804         bool first = true;
 805         for (node_dict::iterator i = this->items.begin(); i != this->items.end(); i++) {
 806             if (!first)
 807                 new_string += ", ";
 808             first = false;
 809             new_string += i->second.first->repr() + ": " + i->second.second->repr();
 810         }
 811         new_string += "}";
 812         return new_string;
 813     }
 814     virtual node *getattr(const char *key);
 815     virtual node *__iter__() { return new(allocator) dict_iter(this); }
 816 };
 817
 818 class set : public node {
 819 private:
 820     class set_iter: public node {
 821     private:
 822         set *parent;
 823         node_set::iterator it;
 824
 825     public:
 826         set_iter(set *s) {
 827             this->parent = s;
 828             it = s->items.begin();
 829         }
 830         const char *node_type() { return "set_iter"; }
 831
 832         virtual void mark_live() {
 833             if (!allocator->mark_live(this, sizeof(*this)))
 834                 this->parent->mark_live();
 835         }
 836
 837         virtual node *next() {
 838             if (this->it == this->parent->items.end())
 839                 return NULL;
 840             node *ret = this->it->second;
 841             ++this->it;
 842             return ret;
 843         }
 844     };
 845
 846     node_set items;
 847
 848 public:
 849     set() { }
 850     const char *node_type() { return "set"; }
 851
 852     virtual void mark_live() {
 853         if (!allocator->mark_live(this, sizeof(*this))) {
 854             for (node_set::iterator i = this->items.begin(); i != this->items.end(); i++)
 855                 i->second->mark_live();
 856         }
 857     }
 858
 859     node *lookup(node *key) {
 860         int_t hashkey;
 861         if (key->is_int_const())
 862             hashkey = key->int_value();
 863         else
 864             hashkey = key->hash();
 865         node_set::const_iterator v = this->items.find(hashkey);
 866         if (v == this->items.end() || !v->second->_eq(key))
 867             return NULL;
 868         return v->second;
 869     }
 870     void add(node *key) {
 871         int_t hashkey;
 872         if (key->is_int_const())
 873             hashkey = key->int_value();
 874         else
 875             hashkey = key->hash();
 876         items[hashkey] = key;
 877     }
 878
 879     virtual bool is_set() { return true; }
 880     virtual bool bool_value() { return this->len() != 0; }
 881
 882     virtual node *__contains__(node *key) {
 883         return create_bool_const(this->lookup(key) != NULL);
 884     }
 885     virtual int_t len() {
 886         return this->items.size();
 887     }
 888     virtual std::string repr() {
 889         if (!this->items.size())
 890             return "set()";
 891         std::string new_string = "{";
 892         bool first = true;
 893         for (node_set::iterator i = this->items.begin(); i != this->items.end(); i++) {
 894             if (!first)
 895                 new_string += ", ";
 896             first = false;
 897             new_string += i->second->repr();
 898         }
 899         new_string += "}";
 900         return new_string;
 901     }
 902     virtual node *getattr(const char *key);
 903     virtual node *__iter__() { return new(allocator) set_iter(this); }
 904 };
 905
 906 class object : public node {
 907 private:
 908     dict *items;
 909
 910 public:
 911     object() {
 912         this->items = new(allocator) dict();
 913     }
 914     const char *node_type() { return "object"; }
 915
 916     virtual void mark_live() {
 917         if (!allocator->mark_live(this, sizeof(*this)))
 918             this->items->mark_live();
 919     }
 920
 921     virtual bool bool_value() { return true; }
 922
 923     virtual node *getattr(const char *key) {
 924         return items->__getitem__(new(allocator) string_const(key));
 925     }
 926     virtual void __setattr__(node *key, node *value) {
 927         items->__setitem__(key, value);
 928     }
 929     virtual bool _eq(node *rhs) {
 930         return this == rhs;
 931     }
 932 };
 933
 934 class file : public node {
 935 private:
 936     FILE *f;
 937
 938 public:
 939     file(const char *path, const char *mode) {
 940         f = fopen(path, mode);
 941         if (!f)
 942             error("%s: file not found", path);
 943     }
 944     const char *node_type() { return "file"; }
 945
 946     MARK_LIVE_FN
 947
 948     node *read(int_t len) {
 949         static char buf[64*1024];
 950         size_t ret = fread(buf, 1, len, this->f);
 951         std::string s(buf, ret);
 952         return new(allocator) string_const(s);
 953     }
 954
 955     virtual bool is_file() { return true; }
 956 };
 957
 958 class range: public node {
 959 private:
 960     class range_iter: public node {
 961     private:
 962         int_t start, end, step;
 963
 964     public:
 965         range_iter(range *r) {
 966             this->start = r->start;
 967             this->end = r->end;
 968             this->step = r->step;
 969         }
 970         const char *node_type() { return "range_iter"; }
 971
 972         MARK_LIVE_FN
 973
 974         virtual node *next() {
 975             if (step > 0) {
 976                 if (this->start >= this->end)
 977                     return NULL;
 978             }
 979             else {
 980                 if (this->start <= this->end)
 981                     return NULL;
 982             }
 983             node *ret = new(allocator) int_const(this->start);
 984             this->start += this->step;
 985             return ret;
 986         }
 987     };
 988
 989     int_t start, end, step;
 990
 991 public:
 992     range(int_t start, int_t end, int_t step) {
 993         this->start = start;
 994         this->end = end;
 995         this->step = step;
 996     }
 997     const char *node_type() { return "range"; }
 998
 999     MARK_LIVE_FN
1000
1001     virtual node *__iter__() { return new(allocator) range_iter(this); }
1002
1003     virtual std::string repr() {
1004         char buf[128];
1005         if (step == 1) {
1006             sprintf(buf, "range(%ld, %ld)", this->start, this->end);
1007         }
1008         else {
1009             sprintf(buf, "range(%ld, %ld, %ld)", this->start, this->end, this->step);
1010         }
1011         return buf;
1012     }
1013 };
1014
1015 typedef node *(*fptr)(context *globals, context *parent_ctx, list *args, dict *kwargs);
1016
1017 class bound_method : public node {
1018 private:
1019     node *self;
1020     node *function;
1021
1022 public:
1023     bound_method(node *self, node *function) {
1024         this->self = self;
1025         this->function = function;
1026     }
1027     const char *node_type() { return "bound_method"; }
1028
1029     virtual void mark_live() {
1030         if (!allocator->mark_live(this, sizeof(*this))) {
1031             this->self->mark_live();
1032             this->function->mark_live();
1033         }
1034     }
1035
1036     virtual bool is_function() { return true; } // XXX is it?
1037
1038     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1039         if (!args->is_list())
1040             error("call with non-list args?");
1041         ((list *)args)->prepend(this->self);
1042         return this->function->__call__(globals, ctx, args, kwargs);
1043     }
1044 };
1045
1046 class function_def : public node {
1047 private:
1048     fptr base_function;
1049
1050 public:
1051     function_def(fptr base_function) {
1052         this->base_function = base_function;
1053     }
1054     const char *node_type() { return "function"; }
1055
1056     MARK_LIVE_FN
1057
1058     virtual bool is_function() { return true; }
1059
1060     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1061         return this->base_function(globals, ctx, args, kwargs);
1062     }
1063 };
1064
1065 class class_def : public node {
1066 private:
1067     std::string name;
1068     dict *items;
1069
1070 public:
1071     class_def(std::string name, void (*creator)(class_def *)) {
1072         this->name = name;
1073         this->items = new(allocator) dict();
1074         creator(this);
1075     }
1076     const char *node_type() { return "class"; }
1077
1078     virtual void mark_live() {
1079         if (!allocator->mark_live(this, sizeof(*this)))
1080             this->items->mark_live();
1081     }
1082
1083     node *load(const char *name) {
1084         return items->__getitem__(new(allocator) string_const(name));
1085     }
1086     void store(const char *name, node *value) {
1087         items->__setitem__(new(allocator) string_const(name), value);
1088     }
1089
1090     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1091         node *init = this->load("__init__");
1092         node *obj = new(allocator) object();
1093
1094         obj->__setattr__(new(allocator) string_const("__class__"), this);
1095
1096         // Create bound methods
1097         for (node_dict::iterator i = items->begin(); i != items->end(); i++)
1098             if (i->second.second->is_function())
1099                 obj->__setattr__(i->second.first, new(allocator) bound_method(obj, i->second.second));
1100
1101         ((list *)args)->prepend(obj);
1102         context *call_ctx = new(allocator) context(ctx);
1103         init->__call__(globals, call_ctx, args, kwargs);
1104         return obj;
1105     }
1106     virtual node *getattr(const char *attr) {
1107         return this->load(attr);
1108     }
1109     virtual std::string repr() {
1110         return std::string("<class '") + this->name + "'>";
1111     }
1112 };
1113
1114 bool_const bool_singleton_True(true);
1115 bool_const bool_singleton_False(false);
1116 none_const none_singleton(0);
1117
1118 inline node *create_bool_const(bool b) {
1119     return b ? &bool_singleton_True : &bool_singleton_False;
1120 }
1121
1122 #define NO_KWARGS_N_ARGS(name, n_args) \
1123     if (kwargs->len()) \
1124         error(name "() does not take keyword arguments"); \
1125     if (args->len() != n_args) \
1126         error("wrong number of arguments to " name "()")
1127
1128 #define NO_KWARGS_MAX_ARGS(name, max_args) \
1129     if (kwargs->len()) \
1130         error(name "() does not take keyword arguments"); \
1131     if (args->len() > max_args) \
1132         error("too many arguments to " name "()")
1133
1134 // Builtin classes
1135 #define LIST_BUILTIN_CLASSES(x) \
1136     x(bool) \
1137     x(dict) \
1138     x(enumerate) \
1139     x(int) \
1140     x(list) \
1141     x(range) \
1142     x(reversed) \
1143     x(set) \
1144     x(str) \
1145     x(tuple) \
1146     x(zip) \
1147
1148 void _dummy__create_(class_def *ctx) {}
1149
1150 class builtin_class_def_singleton: public class_def {
1151 public:
1152     builtin_class_def_singleton(std::string name): class_def(name, _dummy__create_) {}
1153
1154     MARK_LIVE_SINGLETON_FN
1155 };
1156
1157 class bool_class_def_singleton: public builtin_class_def_singleton {
1158 public:
1159     bool_class_def_singleton(): builtin_class_def_singleton("bool") {}
1160
1161     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1162         NO_KWARGS_MAX_ARGS("bool", 1);
1163         if (!args->len())
1164             return &bool_singleton_False;
1165         node *arg = args->__getitem__(0);
1166         return create_bool_const(arg->bool_value());
1167     }
1168 };
1169
1170 class dict_class_def_singleton: public builtin_class_def_singleton {
1171 public:
1172     dict_class_def_singleton(): builtin_class_def_singleton("dict") {}
1173
1174     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1175         NO_KWARGS_N_ARGS("dict", 0);
1176         return new(allocator) dict();
1177     }
1178 };
1179
1180 class enumerate_class_def_singleton: public builtin_class_def_singleton {
1181 public:
1182     enumerate_class_def_singleton(): builtin_class_def_singleton("enumerate") {}
1183
1184     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1185         NO_KWARGS_N_ARGS("enumerate", 1);
1186         node *arg = args->__getitem__(0);
1187         node *iter = arg->__iter__();
1188         list *ret = new(allocator) list;
1189         int i = 0;
1190         for (node *item = iter->next(); item; item = iter->next(), i++) {
1191             node_list sub_list;
1192             sub_list.push_back(new(allocator) int_const(i));
1193             sub_list.push_back(item);
1194             ret->append(new(allocator) tuple(sub_list));
1195         }
1196         return ret;
1197     }
1198 };
1199
1200 class int_class_def_singleton: public builtin_class_def_singleton {
1201 public:
1202     int_class_def_singleton(): builtin_class_def_singleton("int") {}
1203
1204     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1205         NO_KWARGS_MAX_ARGS("int", 1);
1206         if (!args->len())
1207             return new(allocator) int_const(0);
1208         node *arg = args->__getitem__(0);
1209         if (arg->is_int_const())
1210             return arg;
1211         if (arg->is_string()) {
1212             std::string s = arg->string_value();
1213             return new(allocator) int_const(atoi(s.c_str()));
1214         }
1215         error("don't know how to handle argument to int()");
1216     }
1217 };
1218
1219 class list_class_def_singleton: public builtin_class_def_singleton {
1220 public:
1221     list_class_def_singleton(): builtin_class_def_singleton("list") {}
1222
1223     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1224         NO_KWARGS_MAX_ARGS("list", 1);
1225         list *ret = new(allocator) list();
1226         if (!args->len())
1227             return ret;
1228         node *arg = args->__getitem__(0);
1229         node *iter = arg->__iter__();
1230         for (node *item = iter->next(); item; item = iter->next())
1231             ret->append(item);
1232         return ret;
1233     }
1234 };
1235
1236 class range_class_def_singleton: public builtin_class_def_singleton {
1237 public:
1238     range_class_def_singleton(): builtin_class_def_singleton("range") {}
1239
1240     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1241         int_t start = 0, end, step = 1;
1242
1243         if (args->len() == 1)
1244             end = args->__getitem__(0)->int_value();
1245         else if (args->len() == 2) {
1246             start = args->__getitem__(0)->int_value();
1247             end = args->__getitem__(1)->int_value();
1248         }
1249         else if (args->len() == 3) {
1250             start = args->__getitem__(0)->int_value();
1251             end = args->__getitem__(1)->int_value();
1252             step = args->__getitem__(2)->int_value();
1253         }
1254         else
1255             error("too many arguments to range()");
1256
1257         return new(allocator) range(start, end, step);
1258     }
1259 };
1260
1261 class reversed_class_def_singleton: public builtin_class_def_singleton {
1262 public:
1263     reversed_class_def_singleton(): builtin_class_def_singleton("reversed") {}
1264
1265     node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1266         NO_KWARGS_N_ARGS("reversed", 1);
1267         node *item = args->__getitem__(0);
1268         if (!item->is_list())
1269             error("cannot call reversed on non-list");
1270         list *plist = (list *)item;
1271         // sigh, I hate c++
1272         node_list new_list;
1273         new_list.resize(plist->len());
1274         std::reverse_copy(plist->begin(), plist->end(), new_list.begin());
1275
1276         return new(allocator) list(new_list);
1277     }
1278 };
1279
1280 class set_class_def_singleton: public builtin_class_def_singleton {
1281 public:
1282     set_class_def_singleton(): builtin_class_def_singleton("set") {}
1283
1284     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1285         NO_KWARGS_MAX_ARGS("set", 1);
1286         set *ret = new(allocator) set();
1287         if (!args->len())
1288             return ret;
1289         node *arg = args->__getitem__(0);
1290         node *iter = arg->__iter__();
1291         for (node *item = iter->next(); item; item = iter->next())
1292             ret->add(item);
1293         return ret;
1294     }
1295 };
1296
1297 class str_class_def_singleton: public builtin_class_def_singleton {
1298 public:
1299     str_class_def_singleton(): builtin_class_def_singleton("str") {}
1300
1301     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1302         NO_KWARGS_MAX_ARGS("str", 1);
1303         if (!args->len())
1304             return new(allocator) string_const("");
1305         node *arg = args->__getitem__(0);
1306         return arg->__str__();
1307     }
1308 };
1309
1310 class tuple_class_def_singleton: public builtin_class_def_singleton {
1311 public:
1312     tuple_class_def_singleton(): builtin_class_def_singleton("tuple") {}
1313
1314     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1315         NO_KWARGS_MAX_ARGS("tuple", 1);
1316         if (!args->len())
1317             return new(allocator) tuple;
1318         node *arg = args->__getitem__(0);
1319         node *iter = arg->__iter__();
1320         node_list l;
1321         for (node *item = iter->next(); item; item = iter->next())
1322             l.push_back(item);
1323         return new(allocator) tuple(l);
1324     }
1325 };
1326
1327 class zip_class_def_singleton: public builtin_class_def_singleton {
1328 public:
1329     zip_class_def_singleton(): builtin_class_def_singleton("zip") {}
1330
1331     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
1332         NO_KWARGS_N_ARGS("zip", 2);
1333         node *list1 = args->__getitem__(0);
1334         node *list2 = args->__getitem__(1);
1335
1336         if (!list1->is_list() || !list2->is_list() || list1->len() != list2->len())
1337             error("bad arguments to zip()");
1338
1339         list *plist = new(allocator) list();
1340         for (int_t i = 0; i < list1->len(); i++) {
1341             node_list pair;
1342             pair.push_back(list1->__getitem__(i));
1343             pair.push_back(list2->__getitem__(i));
1344             plist->append(new(allocator) tuple(pair));
1345         }
1346
1347         return plist;
1348     }
1349 };
1350
1351 #define BUILTIN_CLASS(name) name##_class_def_singleton builtin_class_##name;
1352 LIST_BUILTIN_CLASSES(BUILTIN_CLASS)
1353 #undef BUILTIN_CLASS
1354
1355 node *node::__getattr__(node *key) {
1356     if (!key->is_string())
1357         error("getattr with non-string");
1358     return this->getattr(key->string_value().c_str());
1359 }
1360
1361 node *node::__hash__() {
1362     return new(allocator) int_const(this->hash());
1363 }
1364
1365 node *node::__len__() {
1366     return new(allocator) int_const(this->len());
1367 }
1368
1369 node *node::__not__() {
1370     return create_bool_const(!this->bool_value());
1371 }
1372
1373 node *node::__is__(node *rhs) {
1374     return create_bool_const(this == rhs);
1375 }
1376
1377 node *node::__isnot__(node *rhs) {
1378     return create_bool_const(this != rhs);
1379 }
1380
1381 node *node::__repr__() {
1382     return new(allocator) string_const(this->repr());
1383 }
1384
1385 node *node::__str__() {
1386     return new(allocator) string_const(this->str());
1387 }
1388
1389 bool none_const::_eq(node *rhs) {
1390     return (this == rhs);
1391 }
1392
1393 node *int_const::getattr(const char *key) {
1394     if (!strcmp(key, "__class__"))
1395         return &builtin_class_int;
1396     error("int has no attribute %s", key);
1397     return NULL;
1398 }
1399
1400 std::string int_const::repr() {
1401     char buf[32];
1402     sprintf(buf, "%" PRId64, this->value);
1403     return std::string(buf);
1404 }
1405
1406 std::string bool_const::repr() {
1407     return std::string(this->value ? "True" : "False");
1408 }
1409
1410 node *list::__add__(node *rhs) {
1411     if (!rhs->is_list())
1412         error("list add error");
1413     list *plist = new(allocator) list();
1414     node_list *rhs_list = rhs->list_value();
1415     for (node_list::iterator i = this->begin(); i != this->end(); i++)
1416         plist->append(*i);
1417     for (node_list::iterator i = rhs_list->begin(); i != rhs_list->end(); i++)
1418         plist->append(*i);
1419     return plist;
1420 }
1421
1422 node *list::__mul__(node *rhs) {
1423     if (!rhs->is_int_const())
1424         error("list mul error");
1425     list *plist = new(allocator) list();
1426     for (int_t x = rhs->int_value(); x > 0; x--)
1427         for (node_list::iterator i = this->begin(); i != this->end(); i++)
1428             plist->append(*i);
1429     return plist;
1430 }
1431
1432 node *list::getattr(const char *key) {
1433     if (!strcmp(key, "append"))
1434         return new(allocator) bound_method(this, new(allocator) function_def(builtin_list_append));
1435     else if (!strcmp(key, "index"))
1436         return new(allocator) bound_method(this, new(allocator) function_def(builtin_list_index));
1437     else if (!strcmp(key, "pop"))
1438         return new(allocator) bound_method(this, new(allocator) function_def(builtin_list_pop));
1439     error("list has no attribute %s", key);
1440     return NULL;
1441 }
1442
1443 node *dict::getattr(const char *key) {
1444     if (!strcmp(key, "get"))
1445         return new(allocator) bound_method(this, new(allocator) function_def(builtin_dict_get));
1446     else if (!strcmp(key, "keys"))
1447         return new(allocator) bound_method(this, new(allocator) function_def(builtin_dict_keys));
1448     error("dict has no attribute %s", key);
1449     return NULL;
1450 }
1451
1452 node *set::getattr(const char *key) {
1453     if (!strcmp(key, "add"))
1454         return new(allocator) bound_method(this, new(allocator) function_def(builtin_set_add));
1455     error("set has no attribute %s", key);
1456     return NULL;
1457 }
1458
1459 node *string_const::getattr(const char *key) {
1460     if (!strcmp(key, "__class__"))
1461         return &builtin_class_str;
1462     else if (!strcmp(key, "join"))
1463         return new(allocator) bound_method(this, new(allocator) function_def(builtin_str_join));
1464     else if (!strcmp(key, "split"))
1465         return new(allocator) bound_method(this, new(allocator) function_def(builtin_str_split));
1466     else if (!strcmp(key, "upper"))
1467         return new(allocator) bound_method(this, new(allocator) function_def(builtin_str_upper));
1468     else if (!strcmp(key, "startswith"))
1469         return new(allocator) bound_method(this, new(allocator) function_def(builtin_str_startswith));
1470     error("str has no attribute %s", key);
1471     return NULL;
1472 }
1473
1474 // This entire function is very stupidly implemented.
1475 node *string_const::__mod__(node *rhs) {
1476     std::ostringstream new_string;
1477     // HACK for now...
1478     if (!rhs->is_list()) {
1479         list *l = new(allocator) list();
1480         l->append(rhs);
1481         rhs = l;
1482     }
1483     int_t args = 0;
1484     for (const char *c = value.c_str(); *c; c++) {
1485         if (*c == '%') {
1486             char fmt_buf[64], buf[64];
1487             char *fmt = fmt_buf;
1488             *fmt++ = '%';
1489             c++;
1490             // Copy over formatting data: only numbers allowed as modifiers now
1491             while (*c && isdigit(*c))
1492                 *fmt++ = *c++;
1493
1494             if ((unsigned)(fmt - fmt_buf) >= sizeof(buf))
1495                 error("I do believe you've made a terrible mistake whilst formatting a string!");
1496             if (args >= rhs->len())
1497                 error("not enough arguments for string format");
1498             node *arg = rhs->__getitem__(args++);
1499             if (*c == 's') {
1500                 *fmt++ = 's';
1501                 *fmt = 0;
1502                 sprintf(buf, fmt_buf, arg->str().c_str());
1503             }
1504             else if (*c == 'd' || *c == 'i' || *c == 'X') {
1505                 *fmt++ = 'l';
1506                 *fmt++ = 'l';
1507                 *fmt++ = *c;
1508                 *fmt = 0;
1509                 sprintf(buf, fmt_buf, arg->int_value());
1510             }
1511             else if (*c == 'c') {
1512                 *fmt++ = 'c';
1513                 *fmt = 0;
1514                 int_t char_value;
1515                 if (arg->is_string())
1516                     char_value = (unsigned char)arg->string_value()[0];
1517                 else
1518                     char_value = arg->int_value();
1519                 sprintf(buf, fmt_buf, char_value);
1520             }
1521             else
1522                 error("bad format specifier '%c' in \"%s\"", *c, value.c_str());
1523             new_string << buf;
1524         }
1525         else
1526             new_string << *c;
1527     }
1528     return new(allocator) string_const(new_string.str());
1529 }
1530
1531 node *string_const::__add__(node *rhs) {
1532     if (!rhs->is_string())
1533         error("bad argument to str.add");
1534     std::string new_string = this->value + rhs->string_value();
1535     return new(allocator) string_const(new_string);
1536 }
1537
1538 node *string_const::__mul__(node *rhs) {
1539     if (!rhs->is_int_const() || rhs->int_value() < 0)
1540         error("bad argument to str.mul");
1541     std::string new_string;
1542     for (int_t i = 0; i < rhs->int_value(); i++)
1543         new_string += this->value;
1544     return new(allocator) string_const(new_string);
1545 }
1546
1547 ////////////////////////////////////////////////////////////////////////////////
1548 // Builtins ////////////////////////////////////////////////////////////////////
1549 ////////////////////////////////////////////////////////////////////////////////
1550
1551 class builtin_function_def: public function_def {
1552 private:
1553     const char *name;
1554
1555 public:
1556     builtin_function_def(const char *name, fptr base_function): function_def(base_function) {
1557         this->name = name;
1558     }
1559     const char *node_type() { return "builtin_function"; }
1560
1561     MARK_LIVE_SINGLETON_FN
1562
1563     virtual std::string repr() {
1564         return std::string("<built-in function ") + this->name + ">";
1565     }
1566 };
1567
1568 #define LIST_BUILTIN_FUNCTIONS(x) \
1569     x(fread) \
1570     x(isinstance) \
1571     x(len) \
1572     x(open) \
1573     x(ord) \
1574     x(print) \
1575     x(print_nonl) \
1576     x(repr) \
1577     x(sorted) \
1578
1579 node *builtin_dict_get(context *globals, context *ctx, list *args, dict *kwargs) {
1580     NO_KWARGS_N_ARGS("dict.get", 3);
1581     node *self = args->__getitem__(0);
1582     node *key = args->__getitem__(1);
1583
1584     node *value = ((dict *)self)->lookup(key);
1585     if (!value)
1586         value = args->__getitem__(2);
1587
1588     return value;
1589 }
1590
1591 node *builtin_dict_keys(context *globals, context *ctx, list *args, dict *kwargs) {
1592     NO_KWARGS_N_ARGS("dict.keys", 1);
1593     dict *self = (dict *)args->__getitem__(0);
1594
1595     list *plist = new(allocator) list();
1596     for (node_dict::iterator i = self->begin(); i != self->end(); i++)
1597         plist->append(i->second.first);
1598
1599     return plist;
1600 }
1601
1602 node *builtin_fread(context *globals, context *ctx, list *args, dict *kwargs) {
1603     NO_KWARGS_N_ARGS("fread", 2);
1604     node *f = args->__getitem__(0);
1605     node *len = args->__getitem__(1);
1606     if (!f->is_file() || !len->is_int_const())
1607         error("bad arguments to fread()");
1608     return ((file *)f)->read(len->int_value());
1609 }
1610
1611 node *builtin_isinstance(context *globals, context *ctx, list *args, dict *kwargs) {
1612     NO_KWARGS_N_ARGS("isinstance", 2);
1613     node *obj = args->__getitem__(0);
1614     node *arg_class = args->__getitem__(1);
1615
1616     node *obj_class = obj->getattr("__class__");
1617     return create_bool_const(obj_class == arg_class);
1618 }
1619
1620 node *builtin_len(context *globals, context *ctx, list *args, dict *kwargs) {
1621     NO_KWARGS_N_ARGS("len", 1);
1622     return args->__getitem__(0)->__len__();
1623 }
1624
1625 node *builtin_list_append(context *globals, context *ctx, list *args, dict *kwargs) {
1626     NO_KWARGS_N_ARGS("list.append", 2);
1627     node *self = args->__getitem__(0);
1628     node *item = args->__getitem__(1);
1629
1630     ((list *)self)->append(item);
1631
1632     return &none_singleton;
1633 }
1634
1635 node *builtin_list_index(context *globals, context *ctx, list *args, dict *kwargs) {
1636     NO_KWARGS_N_ARGS("list.index", 2);
1637     node *self = args->__getitem__(0);
1638     node *key = args->__getitem__(1);
1639
1640     for (int_t i = 0; i < self->len(); i++)
1641         if (self->__getitem__(i)->_eq(key))
1642             return new(allocator) int_const(i);
1643     error("item not found in list");
1644     return &none_singleton;
1645 }
1646
1647 node *builtin_list_pop(context *globals, context *ctx, list *args, dict *kwargs) {
1648     NO_KWARGS_N_ARGS("pop", 1);
1649     list *self = (list *)args->__getitem__(0);
1650
1651     return self->pop();
1652 }
1653
1654 node *builtin_open(context *globals, context *ctx, list *args, dict *kwargs) {
1655     NO_KWARGS_N_ARGS("open", 2);
1656     node *path = args->__getitem__(0);
1657     node *mode = args->__getitem__(1);
1658     if (!path->is_string() || !mode->is_string())
1659         error("bad arguments to open()");
1660     file *f = new(allocator) file(path->string_value().c_str(), mode->string_value().c_str());
1661     return f;
1662 }
1663
1664 node *builtin_ord(context *globals, context *ctx, list *args, dict *kwargs) {
1665     NO_KWARGS_N_ARGS("ord", 1);
1666     node *arg = args->__getitem__(0);
1667     if (!arg->is_string() || arg->len() != 1)
1668         error("bad arguments to ord()");
1669     return new(allocator) int_const((unsigned char)arg->string_value()[0]);
1670 }
1671
1672 node *builtin_print(context *globals, context *ctx, list *args, dict *kwargs) {
1673     std::string new_string;
1674     for (int_t i = 0; i < args->len(); i++) {
1675         if (i)
1676             new_string += " ";
1677         node *s = args->__getitem__(i);
1678         new_string += s->str();
1679     }
1680     printf("%s\n", new_string.c_str());
1681     return &none_singleton;
1682 }
1683
1684 node *builtin_print_nonl(context *globals, context *ctx, list *args, dict *kwargs) {
1685     NO_KWARGS_N_ARGS("print_nonl", 1);
1686     node *s = args->__getitem__(0);
1687     printf("%s", s->str().c_str());
1688     return &none_singleton;
1689 }
1690
1691 node *builtin_repr(context *globals, context *ctx, list *args, dict *kwargs) {
1692     NO_KWARGS_N_ARGS("repr", 1);
1693     node *arg = args->__getitem__(0);
1694     return arg->__repr__();
1695 }
1696
1697 node *builtin_set_add(context *globals, context *ctx, list *args, dict *kwargs) {
1698     NO_KWARGS_N_ARGS("set.add", 2);
1699     node *self = args->__getitem__(0);
1700     node *item = args->__getitem__(1);
1701
1702     ((set *)self)->add(item);
1703
1704     return &none_singleton;
1705 }
1706
1707 bool compare_nodes(node *lhs, node *rhs) {
1708     return lhs->_lt(rhs);
1709 }
1710
1711 node *builtin_sorted(context *globals, context *ctx, list *args, dict *kwargs) {
1712     NO_KWARGS_N_ARGS("sorted", 1);
1713     node *item = args->__getitem__(0);
1714     if (!item->is_list())
1715         error("cannot call sorted on non-list");
1716     list *plist = (list *)item;
1717     // sigh, I hate c++
1718     node_list new_list;
1719     new_list.resize(plist->len());
1720     std::copy(plist->begin(), plist->end(), new_list.begin());
1721     std::stable_sort(new_list.begin(), new_list.end(), compare_nodes);
1722
1723     return new(allocator) list(new_list);
1724 }
1725
1726 node *builtin_str_join(context *globals, context *ctx, list *args, dict *kwargs) {
1727     NO_KWARGS_N_ARGS("str.join", 2);
1728     node *self = args->__getitem__(0);
1729     node *item = args->__getitem__(1);
1730     if (!self->is_string() || !item->is_list())
1731         error("bad arguments to str.join()");
1732
1733     list *joined = (list *)item;
1734     std::string s;
1735     for (node_list::iterator i = joined->begin(); i != joined->end(); i++) {
1736         s += (*i)->str();
1737         if (i + 1 != joined->end())
1738             s += self->string_value();
1739     }
1740     return new(allocator) string_const(s);
1741 }
1742
1743 node *builtin_str_split(context *globals, context *ctx, list *args, dict *kwargs) {
1744     NO_KWARGS_N_ARGS("str.split", 2);
1745     node *self = args->__getitem__(0);
1746     node *item = args->__getitem__(1);
1747     if (!self->is_string() || !item->is_string() || (item->len() != 1))
1748         error("bad argument to str.upper()");
1749     string_const *str = (string_const *)self;
1750     char split = item->string_value()[0];
1751     list *ret = new(allocator) list;
1752     std::string s;
1753     for (std::string::iterator c = str->begin(); c != str->end(); ++c) {
1754         if (*c == split) {
1755             ret->append(new(allocator) string_const(s));
1756             s.clear();
1757         }
1758         else {
1759             s += *c;
1760         }
1761     }
1762     ret->append(new(allocator) string_const(s));
1763     return ret;
1764 }
1765
1766 node *builtin_str_upper(context *globals, context *ctx, list *args, dict *kwargs) {
1767     NO_KWARGS_N_ARGS("str.upper", 1);
1768     node *self = args->__getitem__(0);
1769     if (!self->is_string())
1770         error("bad argument to str.upper()");
1771     string_const *str = (string_const *)self;
1772
1773     std::string new_string;
1774     for (std::string::iterator c = str->begin(); c != str->end(); c++)
1775         new_string += toupper(*c);
1776
1777     return new(allocator) string_const(new_string);
1778 }
1779
1780 node *builtin_str_startswith(context *globals, context *ctx, list *args, dict *kwargs) {
1781     NO_KWARGS_N_ARGS("str.startswith", 2);
1782     node *self = args->__getitem__(0);
1783     node *prefix = args->__getitem__(1);
1784     if (!self->is_string() || !prefix->is_string())
1785         error("bad arguments to str.startswith()");
1786
1787     std::string s1 = self->string_value();
1788     std::string s2 = prefix->string_value();
1789     return create_bool_const(s1.compare(0, s2.size(), s2) == 0);
1790 }
1791
1792 #define BUILTIN_FUNCTION(name) builtin_function_def builtin_function_##name(#name, builtin_##name);
1793 LIST_BUILTIN_FUNCTIONS(BUILTIN_FUNCTION)
1794 #undef BUILTIN_FUNCTION
1795
1796 void init_context(context *ctx, int_t argc, char **argv) {
1797 #define BUILTIN_FUNCTION(name) ctx->store(#name, &builtin_function_##name);
1798 LIST_BUILTIN_FUNCTIONS(BUILTIN_FUNCTION)
1799 #undef BUILTIN_FUNCTION
1800
1801 #define BUILTIN_CLASS(name) ctx->store(#name, &builtin_class_##name);
1802 LIST_BUILTIN_CLASSES(BUILTIN_CLASS)
1803 #undef BUILTIN_CLASS
1804
1805     ctx->store("__name__", new(allocator) string_const("__main__"));
1806     list *plist = new(allocator) list();
1807     for (int_t a = 0; a < argc; a++)
1808         plist->append(new(allocator) string_const(argv[a]));
1809     ctx->store("__args__", plist);
1810 }
1811
1812 void collect_garbage(context *ctx, node *ret_val) {
1813     static int gc_tick = 0;
1814     if (++gc_tick > 128) {
1815         gc_tick = 0;
1816
1817         allocator->mark_dead();
1818
1819         ctx->mark_live(ret_val != NULL);
1820
1821         if (ret_val)
1822             ret_val->mark_live();
1823     }
1824 }