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