backend.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Pythonc backend
   4 //
   5 // Copyright 2011 Zach Wegner
   6 //
   7 // Licensed under the Apache License, Version 2.0 (the "License");
   8 // you may not use this file except in compliance with the License.
   9 // You may obtain a copy of the License at
  10 //
  11 //   http://www.apache.org/licenses/LICENSE-2.0
  12 //
  13 // Unless required by applicable law or agreed to in writing, software
  14 // distributed under the License is distributed on an "AS IS" BASIS,
  15 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16 // See the License for the specific language governing permissions and
  17 // limitations under the License.
  18 //
  19 ////////////////////////////////////////////////////////////////////////////////
  20
  21 #define __STDC_FORMAT_MACROS
  22 #include <stdarg.h>
  23 #include <stdio.h>
  24 #include <stdint.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <inttypes.h>
  28 #include <algorithm>
  29 #include <map>
  30 #include <set>
  31 #include <sstream>
  32 #include <string>
  33 #include <vector>
  34
  35 #include "alloc.h"
  36
  37 __attribute((noreturn)) void error(const char *msg, ...) {
  38     va_list va;
  39     va_start(va, msg);
  40     vprintf(msg, va);
  41     va_end(va);
  42     puts("");
  43     fflush(stdout);
  44     exit(1);
  45 }
  46
  47 class node;
  48 class dict;
  49 class list;
  50 class context;
  51 class string_const;
  52
  53 typedef int64_t int_t;
  54
  55 typedef std::pair<node *, node *> node_pair;
  56 typedef std::map<const char *, node *> symbol_table;
  57 typedef std::map<int_t, node_pair> node_dict;
  58 typedef std::map<int_t, node *> node_set;
  59 typedef std::vector<node *> node_list;
  60
  61 node *builtin_dict(context *globals, context *ctx, list *args, dict *kwargs);
  62 node *builtin_dict_get(context *globals, context *ctx, list *args, dict *kwargs);
  63 node *builtin_dict_keys(context *globals, context *ctx, list *args, dict *kwargs);
  64 node *builtin_fread(context *globals, context *ctx, list *args, dict *kwargs);
  65 node *builtin_isinstance(context *globals, context *ctx, list *args, dict *kwargs);
  66 node *builtin_len(context *globals, context *ctx, list *args, dict *kwargs);
  67 node *builtin_list(context *globals, context *ctx, list *args, dict *kwargs);
  68 node *builtin_list_append(context *globals, context *ctx, list *args, dict *kwargs);
  69 node *builtin_list_index(context *globals, context *ctx, list *args, dict *kwargs);
  70 node *builtin_list_pop(context *globals, context *ctx, list *args, dict *kwargs);
  71 node *builtin_open(context *globals, context *ctx, list *args, dict *kwargs);
  72 node *builtin_ord(context *globals, context *ctx, list *args, dict *kwargs);
  73 node *builtin_print(context *globals, context *ctx, list *args, dict *kwargs);
  74 node *builtin_print_nonl(context *globals, context *ctx, list *args, dict *kwargs);
  75 node *builtin_range(context *globals, context *ctx, list *args, dict *kwargs);
  76 node *builtin_reversed(context *globals, context *ctx, list *args, dict *kwargs);
  77 node *builtin_set(context *globals, context *ctx, list *args, dict *kwargs);
  78 node *builtin_set_add(context *globals, context *ctx, list *args, dict *kwargs);
  79 node *builtin_sorted(context *globals, context *ctx, list *args, dict *kwargs);
  80 node *builtin_str_join(context *globals, context *ctx, list *args, dict *kwargs);
  81 node *builtin_str_upper(context *globals, context *ctx, list *args, dict *kwargs);
  82 node *builtin_str_startswith(context *globals, context *ctx, list *args, dict *kwargs);
  83 node *builtin_zip(context *globals, context *ctx, list *args, dict *kwargs);
  84
  85 inline node *create_bool_const(bool b);
  86
  87 class node {
  88 private:
  89 public:
  90     node() { }
  91     virtual const char *node_type() { return "node"; }
  92
  93     virtual void mark_live() { error("mark_live unimplemented for %s", this->node_type()); }
  94 #define MARK_LIVE_FN \
  95     virtual void mark_live() { allocator->mark_live(this, sizeof(*this)); }
  96 #define MARK_LIVE_SINGLETON_FN virtual void mark_live() { }
  97
  98     virtual bool is_bool() { return false; }
  99     virtual bool is_dict() { return false; }
 100     virtual bool is_file() { return false; }
 101     virtual bool is_function() { return false; }
 102     virtual bool is_int_const() { return false; }
 103     virtual bool is_list() { return false; }
 104     virtual bool is_none() { return false; }
 105     virtual bool is_set() { return false; }
 106     virtual bool is_string() { return false; }
 107     virtual bool bool_value() { error("bool_value unimplemented for %s", this->node_type()); return false; }
 108     virtual int_t int_value() { error("int_value unimplemented for %s", this->node_type()); return 0; }
 109     virtual std::string string_value() { error("string_value unimplemented for %s", this->node_type()); return NULL; }
 110     virtual node_list *list_value() { error("list_value unimplemented for %s", this->node_type()); return NULL; }
 111
 112 #define UNIMP_OP(NAME) \
 113     virtual node *__##NAME##__(node *rhs) { error(#NAME " unimplemented for %s", this->node_type()); return NULL; }
 114
 115     UNIMP_OP(add)
 116     UNIMP_OP(and)
 117     UNIMP_OP(divmod)
 118     UNIMP_OP(floordiv)
 119     UNIMP_OP(lshift)
 120     UNIMP_OP(mod)
 121     UNIMP_OP(mul)
 122     UNIMP_OP(or)
 123     UNIMP_OP(pow)
 124     UNIMP_OP(rshift)
 125     UNIMP_OP(sub)
 126     UNIMP_OP(truediv)
 127     UNIMP_OP(xor)
 128
 129 #define UNIMP_CMP_OP(NAME) \
 130     virtual bool _##NAME(node *rhs) { error(#NAME " unimplemented for %s", this->node_type()); return false; } \
 131     node *__##NAME##__(node *rhs) { return create_bool_const(this->_##NAME(rhs)); }
 132
 133     UNIMP_CMP_OP(eq)
 134     UNIMP_CMP_OP(ne)
 135     UNIMP_CMP_OP(lt)
 136     UNIMP_CMP_OP(le)
 137     UNIMP_CMP_OP(gt)
 138     UNIMP_CMP_OP(ge)
 139
 140     UNIMP_OP(contains)
 141
 142 #define UNIMP_UNOP(NAME) \
 143     virtual node *__##NAME##__() { error(#NAME " unimplemented for %s", this->node_type()); return NULL; }
 144
 145     UNIMP_UNOP(invert)
 146     UNIMP_UNOP(pos)
 147     UNIMP_UNOP(neg)
 148
 149     node *__len__();
 150     node *__hash__();
 151     node *__getattr__(node *rhs);
 152     node *__not__();
 153     node *__is__(node *rhs);
 154     node *__isnot__(node *rhs);
 155     node *__repr__();
 156     node *__str__();
 157
 158     virtual node *__ncontains__(node *rhs) { return this->__contains__(rhs)->__not__(); }
 159
 160     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) { error("call unimplemented for %s", this->node_type()); return NULL; }
 161     virtual void __delitem__(node *rhs) { error("delitem unimplemented for %s", this->node_type()); }
 162     virtual node *__getitem__(node *rhs) { error("getitem unimplemented for %s", this->node_type()); return NULL; }
 163     virtual node *__getitem__(int index) { error("getitem unimplemented for %s", this->node_type()); return NULL; }
 164     virtual void __setattr__(node *rhs, node *key) { error("setattr unimplemented for %s", this->node_type()); }
 165     virtual void __setitem__(node *key, node *value) { error("setitem unimplemented for %s", this->node_type()); }
 166     virtual node *__slice__(node *start, node *end, node *step) { error("slice unimplemented for %s", this->node_type()); return NULL; }
 167
 168     // unwrapped versions
 169     virtual int_t len() { error("len unimplemented for %s", this->node_type()); return 0; }
 170     virtual node *getattr(const char *rhs) { error("getattr unimplemented (%s) for %s", rhs, this->node_type()); return NULL; }
 171     virtual int_t hash() { error("hash unimplemented for %s", this->node_type()); return 0; }
 172     virtual std::string repr() { error("repr unimplemented for %s", this->node_type()); return NULL; }
 173     virtual std::string str() { return repr(); }
 174 };
 175
 176 class context {
 177 private:
 178     symbol_table symbols;
 179     context *parent_ctx;
 180
 181 public:
 182     context() {
 183         this->parent_ctx = NULL;
 184     }
 185     context(context *parent_ctx) {
 186         this->parent_ctx = parent_ctx;
 187     }
 188
 189     void mark_live(bool free_ctx) {
 190         if (!free_ctx)
 191             for (symbol_table::const_iterator i = this->symbols.begin(); i != this->symbols.end(); i++)
 192                 i->second->mark_live();
 193         if (this->parent_ctx)
 194             this->parent_ctx->mark_live(false);
 195     }
 196
 197     void store(const char *name, node *obj) {
 198         this->symbols[name] = obj;
 199     }
 200     node *load(const char *name) {
 201         symbol_table::const_iterator v = this->symbols.find(name);
 202         if (v == this->symbols.end())
 203             error("cannot find '%s' in symbol table", name);
 204         return v->second;
 205     }
 206     void dump() {
 207         for (symbol_table::const_iterator i = this->symbols.begin(); i != this->symbols.end(); i++)
 208             if (i->second->is_int_const())
 209                 printf("symbol['%s'] = int(%" PRId64 ");\n", i->first, i->second->int_value());
 210             else
 211                 printf("symbol['%s'] = %p;\n", i->first, i->second);
 212     }
 213 };
 214
 215 class none_const : public node {
 216 public:
 217     // For some reason this causes errors without an argument to the constructor...
 218     none_const(int_t value) { }
 219     const char *node_type() { return "none"; }
 220
 221     MARK_LIVE_SINGLETON_FN
 222
 223     virtual bool is_none() { return true; }
 224     virtual bool bool_value() { return false; }
 225
 226     virtual bool _eq(node *rhs);
 227     virtual int_t hash() { return 0; }
 228     virtual std::string repr() { return std::string("None"); }
 229 };
 230
 231 class int_const : public node {
 232 private:
 233     int_t value;
 234
 235 public:
 236     int_const(int_t value) {
 237         this->value = value;
 238     }
 239     const char *node_type() { return "int"; }
 240
 241     MARK_LIVE_FN
 242
 243     virtual bool is_int_const() { return true; }
 244     virtual int_t int_value() { return this->value; }
 245     virtual bool bool_value() { return this->value != 0; }
 246
 247 #define INT_OP(NAME, OP) \
 248     virtual int_t _##NAME(node *rhs) { \
 249         return this->int_value() OP rhs->int_value(); \
 250     } \
 251     virtual node *__##NAME##__(node *rhs) { \
 252         return new(allocator) int_const(this->_##NAME(rhs)); \
 253     }
 254     INT_OP(add, +)
 255     INT_OP(and, &)
 256     INT_OP(floordiv, /)
 257     INT_OP(lshift, <<)
 258     INT_OP(mod, %)
 259     INT_OP(mul, *)
 260     INT_OP(or, |)
 261     INT_OP(rshift, >>)
 262     INT_OP(sub, -)
 263     INT_OP(xor, ^)
 264
 265 #define CMP_OP(NAME, OP) \
 266     virtual bool _##NAME(node *rhs) { \
 267         return this->int_value() OP rhs->int_value(); \
 268     } \
 269
 270     CMP_OP(eq, ==)
 271     CMP_OP(ne, !=)
 272     CMP_OP(lt, <)
 273     CMP_OP(le, <=)
 274     CMP_OP(gt, >)
 275     CMP_OP(ge, >=)
 276
 277 #define INT_UNOP(NAME, OP) \
 278     virtual node *__##NAME##__() { \
 279         return new(allocator) int_const(OP this->int_value()); \
 280     }
 281     INT_UNOP(invert, ~)
 282     INT_UNOP(pos, +)
 283     INT_UNOP(neg, -)
 284
 285     virtual int_t hash() { return this->value; }
 286     virtual node *getattr(const char *key);
 287     virtual std::string repr();
 288 };
 289
 290 class int_const_singleton : public int_const {
 291 public:
 292     int_const_singleton(int_t value) : int_const(value) { }
 293
 294     MARK_LIVE_SINGLETON_FN
 295 };
 296
 297 class bool_const : public node {
 298 private:
 299     bool value;
 300
 301 public:
 302     bool_const(bool value) {
 303         this->value = value;
 304     }
 305     const char *node_type() { return "bool"; }
 306
 307     MARK_LIVE_SINGLETON_FN
 308
 309     virtual bool is_bool() { return true; }
 310     virtual bool bool_value() { return this->value; }
 311     virtual int_t int_value() { return (int_t)this->value; }
 312
 313 #define BOOL_AS_INT_OP(NAME, OP) \
 314     virtual node *__##NAME##__(node *rhs) { \
 315         if (rhs->is_int_const() || rhs->is_bool()) \
 316             return new(allocator) int_const(this->int_value() OP rhs->int_value()); \
 317         error(#NAME " error in bool"); \
 318         return NULL; \
 319     }
 320     BOOL_AS_INT_OP(add, +)
 321     BOOL_AS_INT_OP(floordiv, /)
 322     BOOL_AS_INT_OP(lshift, <<)
 323     BOOL_AS_INT_OP(mod, %)
 324     BOOL_AS_INT_OP(mul, *)
 325     BOOL_AS_INT_OP(rshift, >>)
 326     BOOL_AS_INT_OP(sub, -)
 327
 328 #define BOOL_INT_CHECK_OP(NAME, OP) \
 329     virtual node *__##NAME##__(node *rhs) { \
 330         if (rhs->is_bool()) \
 331             return new(allocator) bool_const((bool)(this->int_value() OP rhs->int_value())); \
 332         else if (rhs->is_int_const()) \
 333             return new(allocator) int_const(this->int_value() OP rhs->int_value()); \
 334         error(#NAME " error in bool"); \
 335         return NULL; \
 336     }
 337
 338     BOOL_INT_CHECK_OP(and, &)
 339     BOOL_INT_CHECK_OP(or, |)
 340     BOOL_INT_CHECK_OP(xor, ^)
 341
 342 #define BOOL_OP(NAME, OP) \
 343     virtual bool _##NAME(node *rhs) { \
 344         if (rhs->is_int_const() || rhs->is_bool()) \
 345             return this->int_value() OP rhs->int_value(); \
 346         error(#NAME " error in bool"); \
 347         return false; \
 348     }
 349     BOOL_OP(eq, ==)
 350     BOOL_OP(ne, !=)
 351     BOOL_OP(lt, <)
 352     BOOL_OP(le, <=)
 353     BOOL_OP(gt, >)
 354     BOOL_OP(ge, >=)
 355
 356     virtual int_t hash() { return (int_t)this->value; }
 357     virtual std::string repr();
 358 };
 359
 360 class string_const : public node {
 361 private:
 362     std::string value;
 363
 364 public:
 365     string_const(std::string value) {
 366         this->value = value;
 367     }
 368     const char *node_type() { return "str"; }
 369
 370     MARK_LIVE_FN
 371
 372     virtual bool is_string() { return true; }
 373     virtual std::string string_value() { return this->value; }
 374     virtual bool bool_value() { return this->len() != 0; }
 375
 376     std::string::iterator begin() { return value.begin(); }
 377     std::string::iterator end() { return value.end(); }
 378
 379 #define STRING_OP(NAME, OP) \
 380     virtual bool _##NAME(node *rhs) { \
 381         if (rhs->is_string()) \
 382             return this->string_value() OP rhs->string_value(); \
 383         error(#NAME " unimplemented"); \
 384         return false; \
 385     } \
 386
 387     STRING_OP(eq, ==)
 388     STRING_OP(ne, !=)
 389     STRING_OP(lt, <)
 390     STRING_OP(le, <=)
 391     STRING_OP(gt, >)
 392     STRING_OP(ge, >=)
 393
 394     virtual node *__mod__(node *rhs);
 395     virtual node *__add__(node *rhs);
 396     virtual node *__mul__(node *rhs);
 397
 398     virtual node *getattr(const char *key);
 399
 400     virtual node *__getitem__(node *rhs) {
 401         if (!rhs->is_int_const()) {
 402             error("getitem unimplemented");
 403             return NULL;
 404         }
 405         return new(allocator) string_const(value.substr(rhs->int_value(), 1));
 406     }
 407     // FNV-1a algorithm
 408     virtual int_t hash() {
 409         int_t hashkey = 14695981039346656037ull;
 410         for (std::string::iterator c = this->begin(); c != this->end(); c++) {
 411             hashkey ^= *c;
 412             hashkey *= 1099511628211ll;
 413         }
 414         return hashkey;
 415     }
 416     virtual int_t len() {
 417         return value.length();
 418     }
 419     virtual node *__slice__(node *start, node *end, node *step) {
 420         if ((!start->is_none() && !start->is_int_const()) ||
 421             (!end->is_none() && !end->is_int_const()) ||
 422             (!step->is_none() && !step->is_int_const()))
 423             error("slice error");
 424         int_t lo = start->is_none() ? 0 : start->int_value();
 425         int_t hi = end->is_none() ? value.length() : end->int_value();
 426         int_t st = step->is_none() ? 1 : step->int_value();
 427         if (st != 1)
 428             error("slice step != 1 not supported for string");
 429         return new(allocator) string_const(this->value.substr(lo, hi - lo + 1));
 430     }
 431     virtual std::string repr() {
 432         std::string s("'");
 433         s += this->value; // XXX Add proper quoting/escaping
 434         s += "'";
 435         return s;
 436     }
 437     virtual std::string str() { return this->value; }
 438 };
 439
 440 class string_const_singleton : public string_const {
 441 private:
 442     int_t hashkey;
 443
 444 public:
 445     string_const_singleton(std::string value, int_t hashkey) : string_const(value), hashkey(hashkey) { }
 446
 447     MARK_LIVE_SINGLETON_FN
 448
 449     virtual int_t hash() {
 450         return this->hashkey;
 451     }
 452 };
 453
 454 class list : public node {
 455 private:
 456     node_list items;
 457
 458 public:
 459     list() { }
 460     list(node_list &l) : items(l) { }
 461     const char *node_type() { return "list"; }
 462
 463     virtual void mark_live() {
 464         if (!allocator->mark_live(this, sizeof(*this))) {
 465             for (size_t i = 0; i < this->items.size(); i++)
 466                 this->items[i]->mark_live();
 467         }
 468     }
 469
 470     void append(node *obj) {
 471         items.push_back(obj);
 472     }
 473     void prepend(node *obj) {
 474         items.insert(items.begin(), obj);
 475     }
 476     node *pop() {
 477         // would be nice if STL wasn't stupid, and this was one line...
 478         node *popped = items.back();
 479         items.pop_back();
 480         return popped;
 481     }
 482     node_list::iterator begin() { return items.begin(); }
 483     node_list::iterator end() { return items.end(); }
 484     int_t index(int_t base) {
 485         if (base < 0)
 486             base = items.size() + base;
 487         return base;
 488     }
 489
 490     virtual bool is_list() { return true; }
 491     virtual node_list *list_value() { return &items; }
 492     virtual bool bool_value() { return this->len() != 0; }
 493
 494     virtual node *__add__(node *rhs);
 495     virtual node *__mul__(node *rhs);
 496
 497     virtual node *__contains__(node *key) {
 498         bool found = false;
 499         for (size_t i = 0; i < this->items.size(); i++)
 500             if (this->items[i]->_eq(key)) {
 501                 found = true;
 502                 break;
 503             }
 504         return create_bool_const(found);
 505     }
 506     virtual void __delitem__(node *rhs) {
 507         if (!rhs->is_int_const()) {
 508             error("delitem unimplemented");
 509             return;
 510         }
 511         node_list::iterator f = items.begin() + this->index(rhs->int_value());
 512         items.erase(f);
 513     }
 514     virtual node *__getitem__(int idx) {
 515         return this->items[this->index(idx)];
 516     }
 517     virtual node *__getitem__(node *rhs) {
 518         if (!rhs->is_int_const()) {
 519             error("getitem unimplemented");
 520             return NULL;
 521         }
 522         return this->__getitem__(rhs->int_value());
 523     }
 524     virtual int_t len() {
 525         return this->items.size();
 526     }
 527     virtual void __setitem__(node *key, node *value) {
 528         if (!key->is_int_const())
 529             error("error in list.setitem");
 530         int_t idx = key->int_value();
 531         items[this->index(idx)] = value;
 532     }
 533     virtual node *__slice__(node *start, node *end, node *step) {
 534         if ((!start->is_none() && !start->is_int_const()) ||
 535             (!end->is_none() && !end->is_int_const()) ||
 536             (!step->is_none() && !step->is_int_const()))
 537             error("slice error");
 538         int_t lo = start->is_none() ? 0 : start->int_value();
 539         int_t hi = end->is_none() ? items.size() : end->int_value();
 540         int_t st = step->is_none() ? 1 : step->int_value();
 541         list *new_list = new(allocator) list();
 542         for (; st > 0 ? (lo < hi) : (lo > hi); lo += st)
 543             new_list->append(items[lo]);
 544         return new_list;
 545     }
 546     virtual std::string repr() {
 547         std::string new_string = "[";
 548         bool first = true;
 549         for (node_list::iterator i = this->items.begin(); i != this->items.end(); i++) {
 550             if (!first)
 551                 new_string += ", ";
 552             first = false;
 553             new_string += (*i)->repr();
 554         }
 555         new_string += "]";
 556         return new_string;
 557     }
 558     virtual node *getattr(const char *key);
 559 };
 560
 561 class dict : public node {
 562 private:
 563     node_dict items;
 564
 565 public:
 566     dict() { }
 567     const char *node_type() { return "dict"; }
 568
 569     virtual void mark_live() {
 570         if (!allocator->mark_live(this, sizeof(*this))) {
 571             for (node_dict::iterator i = this->items.begin(); i != this->items.end(); i++) {
 572                 i->second.first->mark_live();
 573                 i->second.second->mark_live();
 574             }
 575         }
 576     }
 577
 578     node *lookup(node *key) {
 579         int_t hashkey;
 580         if (key->is_int_const())
 581             hashkey = key->int_value();
 582         else
 583             hashkey = key->hash();
 584         node_dict::const_iterator v = this->items.find(hashkey);
 585         if (v == this->items.end())
 586             return NULL;
 587         node *k = v->second.first;
 588         if (!k->_eq(key))
 589             return NULL;
 590         return v->second.second;
 591     }
 592     node_dict::iterator begin() { return items.begin(); }
 593     node_dict::iterator end() { return items.end(); }
 594
 595     virtual bool is_dict() { return true; }
 596     virtual bool bool_value() { return this->len() != 0; }
 597
 598     virtual node *__contains__(node *key) {
 599         return create_bool_const(this->lookup(key) != NULL);
 600     }
 601     virtual node *__getitem__(node *key) {
 602         node *value = this->lookup(key);
 603         if (value == NULL)
 604             error("cannot find %s in dict", key->repr().c_str());
 605         return value;
 606     }
 607     virtual int_t len() {
 608         return this->items.size();
 609     }
 610     virtual void __setitem__(node *key, node *value) {
 611         int_t hashkey;
 612         if (key->is_int_const())
 613             hashkey = key->int_value();
 614         else
 615             hashkey = key->hash();
 616         items[hashkey] = node_pair(key, value);
 617     }
 618     virtual std::string repr() {
 619         std::string new_string = "{";
 620         bool first = true;
 621         for (node_dict::iterator i = this->items.begin(); i != this->items.end(); i++) {
 622             if (!first)
 623                 new_string += ", ";
 624             first = false;
 625             new_string += i->second.first->repr() + ": " + i->second.second->repr();
 626         }
 627         new_string += "}";
 628         return new_string;
 629     }
 630     virtual node *getattr(const char *key);
 631 };
 632
 633 class set : public node {
 634 private:
 635     node_set items;
 636
 637 public:
 638     set() { }
 639     const char *node_type() { return "set"; }
 640
 641     virtual void mark_live() {
 642         if (!allocator->mark_live(this, sizeof(*this))) {
 643             for (node_set::iterator i = this->items.begin(); i != this->items.end(); i++)
 644                 i->second->mark_live();
 645         }
 646     }
 647
 648     node *lookup(node *key) {
 649         int_t hashkey;
 650         if (key->is_int_const())
 651             hashkey = key->int_value();
 652         else
 653             hashkey = key->hash();
 654         node_set::const_iterator v = this->items.find(hashkey);
 655         if (v == this->items.end() || !v->second->_eq(key))
 656             return NULL;
 657         return v->second;
 658     }
 659     void add(node *key) {
 660         int_t hashkey;
 661         if (key->is_int_const())
 662             hashkey = key->int_value();
 663         else
 664             hashkey = key->hash();
 665         items[hashkey] = key;
 666     }
 667
 668     virtual bool is_set() { return true; }
 669     virtual bool bool_value() { return this->len() != 0; }
 670
 671     virtual node *__contains__(node *key) {
 672         return create_bool_const(this->lookup(key) != NULL);
 673     }
 674     virtual int_t len() {
 675         return this->items.size();
 676     }
 677     virtual std::string repr() {
 678         if (!this->items.size())
 679             return "set()";
 680         std::string new_string = "{";
 681         bool first = true;
 682         for (node_set::iterator i = this->items.begin(); i != this->items.end(); i++) {
 683             if (!first)
 684                 new_string += ", ";
 685             first = false;
 686             new_string += i->second->repr();
 687         }
 688         new_string += "}";
 689         return new_string;
 690     }
 691     virtual node *getattr(const char *key);
 692 };
 693
 694 class object : public node {
 695 private:
 696     dict *items;
 697
 698 public:
 699     object() {
 700         this->items = new(allocator) dict();
 701     }
 702     const char *node_type() { return "object"; }
 703
 704     virtual void mark_live() {
 705         if (!allocator->mark_live(this, sizeof(*this)))
 706             this->items->mark_live();
 707     }
 708
 709     virtual bool bool_value() { return true; }
 710
 711     virtual node *getattr(const char *key) {
 712         return items->__getitem__(new(allocator) string_const(key));
 713     }
 714     virtual void __setattr__(node *key, node *value) {
 715         items->__setitem__(key, value);
 716     }
 717     virtual bool _eq(node *rhs) {
 718         return this == rhs;
 719     }
 720 };
 721
 722 class file : public node {
 723 private:
 724     FILE *f;
 725
 726 public:
 727     file(const char *path, const char *mode) {
 728         f = fopen(path, mode);
 729         if (!f)
 730             error("%s: file not found", path);
 731     }
 732     const char *node_type() { return "file"; }
 733
 734     MARK_LIVE_FN
 735
 736     node *read(int_t len) {
 737         static char buf[64*1024];
 738         size_t ret = fread(buf, 1, len, this->f);
 739         std::string s(buf, ret);
 740         return new(allocator) string_const(s);
 741     }
 742
 743     virtual bool is_file() { return true; }
 744 };
 745
 746 typedef node *(*fptr)(context *globals, context *parent_ctx, list *args, dict *kwargs);
 747
 748 class bound_method : public node {
 749 private:
 750     node *self;
 751     node *function;
 752
 753 public:
 754     bound_method(node *self, node *function) {
 755         this->self = self;
 756         this->function = function;
 757     }
 758     const char *node_type() { return "bound_method"; }
 759
 760     virtual void mark_live() {
 761         if (!allocator->mark_live(this, sizeof(*this))) {
 762             this->self->mark_live();
 763             this->function->mark_live();
 764         }
 765     }
 766
 767     virtual bool is_function() { return true; } // XXX is it?
 768
 769     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
 770         if (!args->is_list())
 771             error("call with non-list args?");
 772         ((list *)args)->prepend(this->self);
 773         return this->function->__call__(globals, ctx, args, kwargs);
 774     }
 775 };
 776
 777 class function_def : public node {
 778 private:
 779     fptr base_function;
 780
 781 public:
 782     function_def(fptr base_function) {
 783         this->base_function = base_function;
 784     }
 785     const char *node_type() { return "function"; }
 786
 787     MARK_LIVE_FN
 788
 789     virtual bool is_function() { return true; }
 790
 791     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
 792         return this->base_function(globals, ctx, args, kwargs);
 793     }
 794 };
 795
 796 class class_def : public node {
 797 private:
 798     std::string name;
 799     dict *items;
 800
 801 public:
 802     class_def(std::string name, void (*creator)(class_def *)) {
 803         this->name = name;
 804         this->items = new(allocator) dict();
 805         creator(this);
 806     }
 807     const char *node_type() { return "class"; }
 808
 809     virtual void mark_live() {
 810         if (!allocator->mark_live(this, sizeof(*this)))
 811             this->items->mark_live();
 812     }
 813
 814     node *load(const char *name) {
 815         return items->__getitem__(new(allocator) string_const(name));
 816     }
 817     void store(const char *name, node *value) {
 818         items->__setitem__(new(allocator) string_const(name), value);
 819     }
 820
 821     virtual node *__call__(context *globals, context *ctx, list *args, dict *kwargs) {
 822         node *init = this->load("__init__");
 823         node *obj = new(allocator) object();
 824
 825         obj->__setattr__(new(allocator) string_const("__class__"), this);
 826
 827         // Create bound methods
 828         for (node_dict::iterator i = items->begin(); i != items->end(); i++)
 829             if (i->second.second->is_function())
 830                 obj->__setattr__(i->second.first, new(allocator) bound_method(obj, i->second.second));
 831
 832         ((list *)args)->prepend(obj);
 833         context *call_ctx = new(allocator) context(ctx);
 834         init->__call__(globals, call_ctx, args, kwargs);
 835         return obj;
 836     }
 837     virtual node *getattr(const char *attr) {
 838         return this->load(attr);
 839     }
 840 };
 841
 842 class class_def_singleton : public class_def {
 843 public:
 844     class_def_singleton(std::string name, void (*creator)(class_def *)) : class_def(name, creator) { }
 845
 846     MARK_LIVE_SINGLETON_FN
 847 };
 848
 849 bool_const bool_singleton_True(true);
 850 bool_const bool_singleton_False(false);
 851 none_const none_singleton(0);
 852
 853 inline node *create_bool_const(bool b) {
 854     return b ? &bool_singleton_True : &bool_singleton_False;
 855 }
 856
 857 // Silly builtin classes
 858 void _int__create_(class_def *ctx) {
 859 }
 860
 861 void _str__create_(class_def *ctx) {
 862 }
 863
 864 class_def_singleton builtin_class_int("int", _int__create_);
 865 class_def_singleton builtin_class_str("str", _str__create_);
 866
 867 node *node::__getattr__(node *key) {
 868     if (!key->is_string())
 869         error("getattr with non-string");
 870     return this->getattr(key->string_value().c_str());
 871 }
 872
 873 node *node::__hash__() {
 874     return new(allocator) int_const(this->hash());
 875 }
 876
 877 node *node::__len__() {
 878     return new(allocator) int_const(this->len());
 879 }
 880
 881 node *node::__not__() {
 882     return create_bool_const(!this->bool_value());
 883 }
 884
 885 node *node::__is__(node *rhs) {
 886     return create_bool_const(this == rhs);
 887 }
 888
 889 node *node::__isnot__(node *rhs) {
 890     return create_bool_const(this != rhs);
 891 }
 892
 893 node *node::__repr__() {
 894     return new(allocator) string_const(this->repr());
 895 }
 896
 897 node *node::__str__() {
 898     return new(allocator) string_const(this->str());
 899 }
 900
 901 bool none_const::_eq(node *rhs) {
 902     return (this == rhs);
 903 }
 904
 905 node *int_const::getattr(const char *key) {
 906     if (!strcmp(key, "__class__"))
 907         return &builtin_class_int;
 908     error("int has no attribute %s", key);
 909     return NULL;
 910 }
 911
 912 std::string int_const::repr() {
 913     char buf[32];
 914     sprintf(buf, "%" PRId64, this->value);
 915     return std::string(buf);
 916 }
 917
 918 std::string bool_const::repr() {
 919     return std::string(this->value ? "True" : "False");
 920 }
 921
 922 node *list::__add__(node *rhs) {
 923     if (!rhs->is_list())
 924         error("list add error");
 925     list *plist = new(allocator) list();
 926     node_list *rhs_list = rhs->list_value();
 927     for (node_list::iterator i = this->begin(); i != this->end(); i++)
 928         plist->append(*i);
 929     for (node_list::iterator i = rhs_list->begin(); i != rhs_list->end(); i++)
 930         plist->append(*i);
 931     return plist;
 932 }
 933
 934 node *list::__mul__(node *rhs) {
 935     if (!rhs->is_int_const())
 936         error("list mul error");
 937     list *plist = new(allocator) list();
 938     for (int_t x = rhs->int_value(); x > 0; x--)
 939         for (node_list::iterator i = this->begin(); i != this->end(); i++)
 940             plist->append(*i);
 941     return plist;
 942 }
 943
 944 node *list::getattr(const char *key) {
 945     if (!strcmp(key, "append"))
 946         return new(allocator) bound_method(this, new(allocator) function_def(builtin_list_append));
 947     else if (!strcmp(key, "index"))
 948         return new(allocator) bound_method(this, new(allocator) function_def(builtin_list_index));
 949     else if (!strcmp(key, "pop"))
 950         return new(allocator) bound_method(this, new(allocator) function_def(builtin_list_pop));
 951     error("list has no attribute %s", key);
 952     return NULL;
 953 }
 954
 955 node *dict::getattr(const char *key) {
 956     if (!strcmp(key, "get"))
 957         return new(allocator) bound_method(this, new(allocator) function_def(builtin_dict_get));
 958     else if (!strcmp(key, "keys"))
 959         return new(allocator) bound_method(this, new(allocator) function_def(builtin_dict_keys));
 960     error("dict has no attribute %s", key);
 961     return NULL;
 962 }
 963
 964 node *set::getattr(const char *key) {
 965     if (!strcmp(key, "add"))
 966         return new(allocator) bound_method(this, new(allocator) function_def(builtin_set_add));
 967     error("set has no attribute %s", key);
 968     return NULL;
 969 }
 970
 971 node *string_const::getattr(const char *key) {
 972     if (!strcmp(key, "__class__"))
 973         return &builtin_class_str;
 974     else if (!strcmp(key, "join"))
 975         return new(allocator) bound_method(this, new(allocator) function_def(builtin_str_join));
 976     else if (!strcmp(key, "upper"))
 977         return new(allocator) bound_method(this, new(allocator) function_def(builtin_str_upper));
 978     else if (!strcmp(key, "startswith"))
 979         return new(allocator) bound_method(this, new(allocator) function_def(builtin_str_startswith));
 980     error("str has no attribute %s", key);
 981     return NULL;
 982 }
 983
 984 // This entire function is very stupidly implemented.
 985 node *string_const::__mod__(node *rhs) {
 986     std::ostringstream new_string;
 987     // HACK for now...
 988     if (!rhs->is_list()) {
 989         list *l = new(allocator) list();
 990         l->append(rhs);
 991         rhs = l;
 992     }
 993     int_t args = 0;
 994     for (const char *c = value.c_str(); *c; c++) {
 995         if (*c == '%') {
 996             char fmt_buf[64], buf[64];
 997             char *fmt = fmt_buf;
 998             *fmt++ = '%';
 999             c++;
1000             // Copy over formatting data: only numbers allowed as modifiers now
1001             while (*c && isdigit(*c))
1002                 *fmt++ = *c++;
1003
1004             if ((unsigned)(fmt - fmt_buf) >= sizeof(buf))
1005                 error("I do believe you've made a terrible mistake whilst formatting a string!");
1006             if (args >= rhs->len())
1007                 error("not enough arguments for string format");
1008             node *arg = rhs->__getitem__(args++);
1009             if (*c == 's') {
1010                 *fmt++ = 's';
1011                 *fmt = 0;
1012                 sprintf(buf, fmt_buf, arg->str().c_str());
1013             }
1014             else if (*c == 'd' || *c == 'i' || *c == 'X') {
1015                 *fmt++ = *c;
1016                 *fmt = 0;
1017                 sprintf(buf, fmt_buf, arg->int_value());
1018             }
1019             else if (*c == 'c') {
1020                 *fmt++ = 'c';
1021                 *fmt = 0;
1022                 int_t char_value;
1023                 if (arg->is_string())
1024                     char_value = (unsigned char)arg->string_value()[0];
1025                 else
1026                     char_value = arg->int_value();
1027                 sprintf(buf, fmt_buf, char_value);
1028             }
1029             else
1030                 error("bad format specifier '%c' in \"%s\"", *c, value.c_str());
1031             new_string << buf;
1032         }
1033         else
1034             new_string << *c;
1035     }
1036     return new(allocator) string_const(new_string.str());
1037 }
1038
1039 node *string_const::__add__(node *rhs) {
1040     if (!rhs->is_string())
1041         error("bad argument to str.add");
1042     std::string new_string = this->value + rhs->string_value();
1043     return new(allocator) string_const(new_string);
1044 }
1045
1046 node *string_const::__mul__(node *rhs) {
1047     if (!rhs->is_int_const() || rhs->int_value() < 0)
1048         error("bad argument to str.mul");
1049     std::string new_string;
1050     for (int_t i = 0; i < rhs->int_value(); i++)
1051         new_string += this->value;
1052     return new(allocator) string_const(new_string);
1053 }
1054
1055 #define NO_KWARGS(name) \
1056     if (kwargs->len()) \
1057         error(name "() does not take keyword arguments")
1058
1059 node *builtin_dict(context *globals, context *ctx, list *args, dict *kwargs) {
1060     NO_KWARGS("dict");
1061     if (args->len())
1062         error("too many arguments to dict()");
1063     return new(allocator) dict();
1064 }
1065
1066 node *builtin_dict_get(context *globals, context *ctx, list *args, dict *kwargs) {
1067     if (args->len() != 3) // just assume 3 args for now...
1068         error("bad number of arguments to dict.get()");
1069     node *self = args->__getitem__(0);
1070     node *key = args->__getitem__(1);
1071
1072     node *value = ((dict *)self)->lookup(key);
1073     if (!value)
1074         value = args->__getitem__(2);
1075
1076     return value;
1077 }
1078
1079 node *builtin_dict_keys(context *globals, context *ctx, list *args, dict *kwargs) {
1080     if (args->len() != 1)
1081         error("bad number of arguments to dict.keys()");
1082     dict *self = (dict *)args->__getitem__(0);
1083
1084     list *plist = new(allocator) list();
1085     for (node_dict::iterator i = self->begin(); i != self->end(); i++)
1086         plist->append(i->second.first);
1087
1088     return plist;
1089 }
1090
1091 node *builtin_fread(context *globals, context *ctx, list *args, dict *kwargs) {
1092     node *f = args->__getitem__(0);
1093     node *len = args->__getitem__(1);
1094     if (!f->is_file() || !len->is_int_const())
1095         error("bad arguments to fread()");
1096     return ((file *)f)->read(len->int_value());
1097 }
1098
1099 node *builtin_isinstance(context *globals, context *ctx, list *args, dict *kwargs) {
1100     node *obj = args->__getitem__(0);
1101     node *arg_class = args->__getitem__(1);
1102
1103     node *obj_class = obj->getattr("__class__");
1104     return create_bool_const(obj_class == arg_class);
1105 }
1106
1107 node *builtin_len(context *globals, context *ctx, list *args, dict *kwargs) {
1108     return args->__getitem__(0)->__len__();
1109 }
1110
1111 node *builtin_list(context *globals, context *ctx, list *args, dict *kwargs) {
1112     NO_KWARGS("list");
1113     if (args->len())
1114         error("too many arguments to list()");
1115     return new(allocator) list();
1116 }
1117
1118 node *builtin_list_append(context *globals, context *ctx, list *args, dict *kwargs) {
1119     node *self = args->__getitem__(0);
1120     node *item = args->__getitem__(1);
1121
1122     ((list *)self)->append(item);
1123
1124     return &none_singleton;
1125 }
1126
1127 node *builtin_list_index(context *globals, context *ctx, list *args, dict *kwargs) {
1128     if (args->len() != 2)
1129         error("bad number of arguments to list.index()");
1130     node *self = args->__getitem__(0);
1131     node *key = args->__getitem__(1);
1132
1133     for (int_t i = 0; i < self->len(); i++)
1134         if (self->__getitem__(i)->_eq(key))
1135             return new(allocator) int_const(i);
1136     error("item not found in list");
1137     return &none_singleton;
1138 }
1139
1140 node *builtin_list_pop(context *globals, context *ctx, list *args, dict *kwargs) {
1141     list *self = (list *)args->__getitem__(0);
1142
1143     return self->pop();
1144 }
1145
1146 node *builtin_open(context *globals, context *ctx, list *args, dict *kwargs) {
1147     node *path = args->__getitem__(0);
1148     node *mode = args->__getitem__(1);
1149     if (!path->is_string() || !mode->is_string())
1150         error("bad arguments to open()");
1151     file *f = new(allocator) file(path->string_value().c_str(), mode->string_value().c_str());
1152     return f;
1153 }
1154
1155 node *builtin_ord(context *globals, context *ctx, list *args, dict *kwargs) {
1156     node *arg = args->__getitem__(0);
1157     if (!arg->is_string() || arg->len() != 1)
1158         error("bad arguments to ord()");
1159     return new(allocator) int_const((unsigned char)arg->string_value()[0]);
1160 }
1161
1162 node *builtin_print(context *globals, context *ctx, list *args, dict *kwargs) {
1163     std::string new_string;
1164     for (int_t i = 0; i < args->len(); i++) {
1165         if (i)
1166             new_string += " ";
1167         node *s = args->__getitem__(i);
1168         new_string += s->str();
1169     }
1170     printf("%s\n", new_string.c_str());
1171     return &none_singleton;
1172 }
1173
1174 node *builtin_print_nonl(context *globals, context *ctx, list *args, dict *kwargs) {
1175     node *s = args->__getitem__(0);
1176     printf("%s", s->str().c_str());
1177     return &none_singleton;
1178 }
1179
1180 node *builtin_range(context *globals, context *ctx, list *args, dict *kwargs) {
1181     list *new_list = new(allocator) list();
1182     int_t start = 0, end, step = 1;
1183
1184     if (args->len() == 1)
1185         end = args->__getitem__(0)->int_value();
1186     else if (args->len() == 2) {
1187         start = args->__getitem__(0)->int_value();
1188         end = args->__getitem__(1)->int_value();
1189     }
1190     else if (args->len() == 3) {
1191         start = args->__getitem__(0)->int_value();
1192         end = args->__getitem__(1)->int_value();
1193         step = args->__getitem__(2)->int_value();
1194     }
1195     else
1196         error("too many arguments to range()");
1197
1198     for (int_t s = start; step > 0 ? (s < end) : (s > end); s += step)
1199         new_list->append(new(allocator) int_const(s));
1200     return new_list;
1201 }
1202
1203 node *builtin_reversed(context *globals, context *ctx, list *args, dict *kwargs) {
1204     node *item = args->__getitem__(0);
1205     if (!item->is_list())
1206         error("cannot call reversed on non-list");
1207     list *plist = (list *)item;
1208     // sigh, I hate c++
1209     node_list new_list;
1210     new_list.resize(plist->len());
1211     std::reverse_copy(plist->begin(), plist->end(), new_list.begin());
1212
1213     return new(allocator) list(new_list);
1214 }
1215
1216 node *builtin_set(context *globals, context *ctx, list *args, dict *kwargs) {
1217     NO_KWARGS("set");
1218     if (args->len())
1219         error("too many arguments to set()");
1220     return new(allocator) set();
1221 }
1222
1223 node *builtin_set_add(context *globals, context *ctx, list *args, dict *kwargs) {
1224     node *self = args->__getitem__(0);
1225     node *item = args->__getitem__(1);
1226
1227     ((set *)self)->add(item);
1228
1229     return &none_singleton;
1230 }
1231
1232 bool compare_nodes(node *lhs, node *rhs) {
1233     return lhs->_lt(rhs);
1234 }
1235
1236 node *builtin_sorted(context *globals, context *ctx, list *args, dict *kwargs) {
1237     node *item = args->__getitem__(0);
1238     if (!item->is_list())
1239         error("cannot call sorted on non-list");
1240     list *plist = (list *)item;
1241     // sigh, I hate c++
1242     node_list new_list;
1243     new_list.resize(plist->len());
1244     std::copy(plist->begin(), plist->end(), new_list.begin());
1245     std::stable_sort(new_list.begin(), new_list.end(), compare_nodes);
1246
1247     return new(allocator) list(new_list);
1248 }
1249
1250 node *builtin_str_join(context *globals, context *ctx, list *args, dict *kwargs) {
1251     node *self = args->__getitem__(0);
1252     node *item = args->__getitem__(1);
1253     if (!self->is_string() || !item->is_list())
1254         error("bad arguments to str.join()");
1255
1256     list *joined = (list *)item;
1257     std::string s;
1258     for (node_list::iterator i = joined->begin(); i != joined->end(); i++) {
1259         s += (*i)->str();
1260         if (i + 1 != joined->end())
1261             s += self->string_value();
1262     }
1263     return new(allocator) string_const(s);
1264 }
1265
1266 node *builtin_str_upper(context *globals, context *ctx, list *args, dict *kwargs) {
1267     node *self = args->__getitem__(0);
1268     if (!self->is_string())
1269         error("bad argument to str.upper()");
1270     string_const *str = (string_const *)self;
1271
1272     std::string new_string;
1273     for (std::string::iterator c = str->begin(); c != str->end(); c++)
1274         new_string += toupper(*c);
1275
1276     return new(allocator) string_const(new_string);
1277 }
1278
1279 node *builtin_str_startswith(context *globals, context *ctx, list *args, dict *kwargs) {
1280     node *self = args->__getitem__(0);
1281     node *prefix = args->__getitem__(1);
1282     if (!self->is_string() || !prefix->is_string())
1283         error("bad arguments to str.startswith()");
1284
1285     std::string s1 = self->string_value();
1286     std::string s2 = prefix->string_value();
1287     return create_bool_const(s1.compare(0, s2.size(), s2) == 0);
1288 }
1289
1290 node *builtin_zip(context *globals, context *ctx, list *args, dict *kwargs) {
1291     if (args->len() != 2)
1292         error("bad arguments to zip()");
1293     node *list1 = args->__getitem__(0);
1294     node *list2 = args->__getitem__(1);
1295
1296     if (!list1->is_list() || !list2->is_list() || list1->len() != list2->len())
1297         error("bad arguments to zip()");
1298
1299     list *plist = new(allocator) list();
1300     for (int_t i = 0; i < list1->len(); i++) {
1301         list *pair = new(allocator) list();
1302         pair->append(list1->__getitem__(i));
1303         pair->append(list2->__getitem__(i));
1304         plist->append(pair);
1305     }
1306
1307     return plist;
1308 }
1309
1310 void init_context(context *ctx, int_t argc, char **argv) {
1311     ctx->store("dict", new(allocator) function_def(builtin_dict));
1312     ctx->store("fread", new(allocator) function_def(builtin_fread));
1313     ctx->store("len", new(allocator) function_def(builtin_len));
1314     ctx->store("isinstance", new(allocator) function_def(builtin_isinstance));
1315     ctx->store("list", new(allocator) function_def(builtin_list));
1316     ctx->store("open", new(allocator) function_def(builtin_open));
1317     ctx->store("ord", new(allocator) function_def(builtin_ord));
1318     ctx->store("print", new(allocator) function_def(builtin_print));
1319     ctx->store("print_nonl", new(allocator) function_def(builtin_print_nonl));
1320     ctx->store("range", new(allocator) function_def(builtin_range));
1321     ctx->store("reversed", new(allocator) function_def(builtin_reversed));
1322     ctx->store("set", new(allocator) function_def(builtin_set));
1323     ctx->store("sorted", new(allocator) function_def(builtin_sorted));
1324     ctx->store("zip", new(allocator) function_def(builtin_zip));
1325
1326     ctx->store("int", &builtin_class_int);
1327     ctx->store("str", &builtin_class_str);
1328
1329     ctx->store("__name__", new(allocator) string_const("__main__"));
1330     list *plist = new(allocator) list();
1331     for (int_t a = 0; a < argc; a++)
1332         plist->append(new(allocator) string_const(argv[a]));
1333     ctx->store("__args__", plist);
1334 }
1335
1336 void collect_garbage(context *ctx, node *ret_val) {
1337     static int gc_tick = 0;
1338     if (++gc_tick > 128) {
1339         gc_tick = 0;
1340
1341         allocator->mark_dead();
1342
1343         ctx->mark_live(ret_val != NULL);
1344
1345         if (ret_val)
1346             ret_val->mark_live();
1347     }
1348 }