#ifndef MS_H
#define MS_H

#include <string>
#include <vector>
#include <list>
#include <stdint.h> // yucks
#include <iostream>
#include <cassert>
#include <sstream>

#define nullptr 0

namespace ms {
struct Value {
	enum Type {
		BOOLEAN,	// {bool}
		NIL,		// {}
		PAIR,		// {Value, Value}
		SYMBOL,		// {std::string}
		INTEGER,	// {intptr_t}
		STRING,		// {std::string}

		LAMBDA,		// {ASM, ENVIRON}
		CFUNC,		// {ptr, int(args)}
		CALLCC,		// {}
		CONT,		// {ptr(stack)}

		ASM,		// {vec, int(vars)}			internal
		ENVIRON,	// {ENVIRON(parent), vec<Value>}	internal
		VM,		// {}					internal
		ERROR,		// {std::string}			internal

		SHIELD,		// {vec<Value>}				internal
		FREE,		// {ptr(next)}				internal
	} type;
	void *p1, *p2;

	inline bool is_a(Value::Type type) const {
		return this->type == type;
	}

	inline bool test() const {
		return !(type == Value::BOOLEAN && !p1);
	}
};

struct Instruction {
	enum Type {
		NOP,
		PUSH,
		POP,
		DUP,
		GETVAR,
		SETVAR,
		LAMBDA,
		APPLY,
		APPLY_TAILCALL,
		RET,
		JUMP,
		JUMPUNLESS,
		JUMPIF,
	} type;

	uintptr_t arg;

	Instruction(Instruction::Type op, uintptr_t arg) :
		type(op), arg(arg) {
	}
};

// memory.cc
class Memory {
public:
	Memory(size_t block_size);
	Value *alloc(Value::Type type);
	void run_gc();
	void mark_object(const Value *v);

	struct ObjectFactory {
		ObjectFactory(Memory *mem) : mem(mem) {
		}

		virtual Value *new_object(Value::Type type) {
			Value *ret = mem->alloc(type);
			ret->p1 = ret->p2 = nullptr;
			return ret;
		}

		Value *new_nil() {
			return new_object(Value::NIL);
		}

		Value *new_bool(bool b) {
			Value *ret = new_object(Value::BOOLEAN);
			ret->p1 = b ? (void *)-1 : nullptr; // XXX
			return ret;
		}

		Value *new_number(intptr_t i) {
			Value *ret = new_object(Value::INTEGER);
			ret->p1 = reinterpret_cast<void *>(i);
			return ret;
		}

		Value *new_pair(Value *a, Value *b) {
			Value *ret = new_object(Value::PAIR);
			// assert(a && a->type != Value::FREE);
			// assert(!b || b->type != Value::FREE);
			ret->p1 = a;
			ret->p2 = b;
			return ret;
		}

		// TODO: REMOVE
		const Value *new_pair(const Value *a, const Value *b) {
			Value *ret = new_object(Value::PAIR);
			ret->p1 = (void *)a;
			ret->p2 = (void *)b;
			return ret;
		}

		Value *new_list(size_t num, Value **vs) {
			if (num == 0)
				return new_nil();
			Value *ret = new_pair(vs[0], nullptr),
			      *prev = ret;
			for (size_t i = 1; i < num; i++) {
				prev->p2 = new_pair(vs[i], nullptr);
				prev = static_cast<Value *>(prev->p2);
			}
			prev->p2 = new_nil();
			return ret;
		}

		Value *new_string(const std::string &s) {
			Value *ret = new_object(Value::STRING);
			ret->p1 = new std::string(s);
			return ret;
		}

		Value *new_string(std::string *s) {
			Value *ret = new_object(Value::STRING);
			ret->p1 = s;
			return ret;
		}

		Value *new_symbol(const std::string &s) {
			Value *ret = new_string(s);
			ret->type = Value::SYMBOL;
			return ret;
		}

		Value *new_error(const std::string &s) {
			Value *ret = new_string(s);
			ret->type = Value::ERROR;
			return ret;
		}

		Value *new_cfunc(Value *(*ptr)(int, Value **), int argc) {
			Value *v = new_object(Value::CFUNC);
			v->p1 = reinterpret_cast<void *>(ptr);
			v->p2 = reinterpret_cast<void *>(argc);
			return v;
		}

	protected:
		Memory *mem;
	};

	struct Shield : ObjectFactory {
		Shield(Memory *mem) : ObjectFactory(mem), vec() {
			shield = mem->alloc(Value::SHIELD);
			shield->p1 = &vec;
			shield->p2 = nullptr;

			mem->roots.push_back(shield);
		};

		~Shield() {
			mem->roots.remove(shield);
			shield->p1 = nullptr;
		}

		Value *new_object(Value::Type type) {
			Value *ret = ObjectFactory::new_object(type);
			return add(ret);
		}

		Value *add(Value *obj) {
			vec.push_back(obj);
			return obj;
		}

	private:
		Value *shield;
		std::vector<Value *> vec;
	};

private:
	struct Block {
		Block(size_t size);
		~Block();

		Value *slots;
		bool *bitmap;
	};
	void free_object(Value *v);

	size_t block_size;
	std::vector<Block *> blocks;
	Value *freelist;
public:
	std::list<Value *> roots;
	bool allow_gc;
};
Memory *get_memory();

static inline Memory::ObjectFactory &unshield() {
	static Memory::ObjectFactory oc(get_memory());
	return oc;
}


struct Assembly : Value {
	inline std::vector<Instruction> *seq() const {
		return static_cast<std::vector<Instruction> *>(p1);
	}

	inline void set_num_variables(int num, int args) {
		assert(!p2);
		p2 = new std::pair<int, int>(num, args);
	}

	inline size_t num_variables() const {
		return static_cast<std::pair<int, int> *>(p2)->first;
	}

	inline int num_args() const {
		return static_cast<std::pair<int, int> *>(p2)->second;
	}
};
struct Continuation : Value {
	inline const Value **copied_stack() const {
		return static_cast<const Value **>(p1);
	}

	inline size_t sp() const {
		return reinterpret_cast<size_t>(p2);
	}

	void mark(Memory &) const;
	void free();
};
// static asser: sizeof Value == sizeof Assembly



// sexp_parse.cc
Value *sexp_parse_toplevel(const std::string &);

// compile.cc
Assembly *compile(const Value *);

// builtin.cc
Value *get_cfunc(const std::string &id);

// eval.cc
class VM;
void vm_mark_objects(Memory &, const VM *);
void environ_mark(Memory &, const Value *);
void environ_free(Value *);
void asm_mark(Memory &, const Assembly *);
void asm_free(Assembly *);
Value *eval(const Assembly *assm, Value *env);


// utils
static inline const Value *car(const Value *p) {
	assert(p->type == Value::PAIR);
	return static_cast<const Value *>(p->p1);
}

static inline const Value *cdr(const Value *p) {
	assert(p->type == Value::PAIR);
	return static_cast<const Value *>(p->p2);
}

static inline Value *car(Value *p) {
	assert(p->type == Value::PAIR);
	return static_cast<Value *>(p->p1);
}

static inline Value *cdr(Value *p) {
	assert(p->type == Value::PAIR);
	return static_cast<Value *>(p->p2);
}

static inline void dump_s(const Assembly *, std::ostream &, size_t);
static inline void dump_s(const Value *v, std::ostream &os, size_t indent) {
	if (!v) {
		os << "<nullptr>";
		return;
	}
	switch (v->type) {
	case Value::BOOLEAN:
		os << (v->p1 ? "true" : "false");
		break;
	case Value::NIL:
		os << "<nil>";
		break;
	case Value::PAIR: {
		assert(v->p1);
		assert(v->p2);

		os << "(";
		dump_s(static_cast<const Value *>(v->p1), os, indent + 1);
		const Value *next = static_cast<const Value *>(v->p2);
		while (true) {
			if (next->is_a(Value::NIL)) {
				os << ")";
				break;
			} else if (next->is_a(Value::PAIR)) {
				os << " ";
				dump_s(static_cast<const Value *>(next->p1), os, indent + 1);
				next = static_cast<const Value *>(next->p2);
			} else {
				os << " . ";
				dump_s(next, os, indent + 1);
				os << ")";
				break;
			}
		}
		break;
	}
	case Value::SYMBOL:
		assert(!v->p2);
		os << *static_cast<const std::string *>(v->p1);
		break;
	case Value::INTEGER:
		assert(!v->p2);
		os << reinterpret_cast<intptr_t>(v->p1);
		break;
	case Value::STRING:
		assert(!v->p2);
		os << "<string " << *static_cast<const std::string *>(v->p1) << ">";
		break;
	case Value::LAMBDA:
		os << "<lambda ";
		dump_s(static_cast<const Value *>(v->p1), os, indent + 1);
		os << " ";
		dump_s(static_cast<const Value *>(v->p2), os, indent + 1);
		os << ">";
		break;
	case Value::CFUNC:
		os << "<cfunc " << v->p1 << ">";
		break;
	case Value::CALLCC:
		os << "<callcc>";
		break;
	case Value::CONT:
		os << "<continuation>";
		break;
	case Value::ENVIRON:
		os << "<environ>";
		break;
	case Value::VM:
		os << "<vm>";
		break;
	case Value::SHIELD:
		os << "<shield>";
		break;
	case Value::ASM:
		os << "<asm ";
		dump_s((const Assembly *)v, os, indent + 1);
		os << ">";
		break;
	case Value::ERROR:
		os << "<error: " << *static_cast<const std::string *>(v->p1) << ">";
		break;
	case Value::FREE:
		os << "<free>";
		break;
	}
}

static inline std::string dump_s(const Value *a) {
	std::ostringstream os;
	dump_s(a, os, 0);
	os << "\n";
	return os.str();
}

static inline void dump(const Value *a) {
	dump_s(a, std::cerr, 0);
	std::cerr << "\n";
}

static inline void dump_s(const Assembly *a, std::ostream &os, size_t indent) {
	os << "dump-asm: num_variables=" << a->num_variables() << ":num_args=" << a->num_args() << "\n";
	for (std::vector<Instruction>::const_iterator i = a->seq()->begin();
	     i != a->seq()->end(); i++) {
		os << std::string(indent, '\t');
		//os << "ins:" << i->type <<", arg:" << i->arg << std::endl;
		switch (i->type) {
		case Instruction::NOP:
			os << "NOP\n";
			break;
		case Instruction::PUSH:
			os << "PUSH\t\t";
			dump_s((const Value *)i->arg, os, indent + 1);
			os << "\n";
			break;
		case Instruction::POP:
			os << "POP\n";
			break;
		case Instruction::DUP:
			os << "DUP\n";
			break;
		case Instruction::GETVAR:
			os << "GETVAR\t\t" << i->arg << "\n";
			break;
		case Instruction::SETVAR:
			os << "SETVAR\t\t" << i->arg << "\n";
			break;
		case Instruction::LAMBDA:
			os << "LAMBDA\t\tasm=";
			dump_s((const Assembly *)i->arg, os, indent + 1);
			break;
		case Instruction::APPLY_TAILCALL:
			os << "APPLY_TAILCALL\targs=" << i->arg << "\n";
			break;
		case Instruction::APPLY:
			os << "APPLY\t\targs=" << i->arg << "\n";
			break;
		case Instruction::RET:
			os << "RET\n";
			break;
		case Instruction::JUMP:
			os << "JUMP\t\t+" << i->arg << "\n";
			break;
		case Instruction::JUMPUNLESS:
			os << "JUMPUNLESS\t+" << i->arg << "\n";
			break;
		case Instruction::JUMPIF:
			os << "JUMPIF\t\t+" << i->arg << "\n";
			break;
		}
	}
}

static inline std::string dump_s(const Assembly *a) {
	std::ostringstream os;
	dump_s(a, os, 0);
	os << "\n";
	return os.str();
}

static inline void dump(const Assembly *a) {
	dump_s(a, std::cerr, 0);
	std::cerr << "\n";
}

}

#endif