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