Represent code as list structure (i.e. traditional LISP lists built from pairs), rather than tuple structure.

Remove unused/crufty depoly stage.
Remove cps from AST interface (but keep cps.cpp code around for later).
Improved command line interface for compilation stages (options -T -L -S).


git-svn-id: http://svn.drobilla.net/resp/resp@277 ad02d1e2-f140-0410-9f75-f8b11f17cedd

1 files changed, 196 insertions, 58 deletions

diff --git a/src/resp.hpp b/src/resp.hpp
index 3f73f2f..26038b6 100644
--- a/src/resp.hpp
+++ b/src/resp.hpp
@@ -204,9 +204,7 @@ struct AST : public Object {
 	virtual bool operator==(const AST& o) const = 0;
 	virtual bool contains(const AST* child) const { return false; }
 	virtual void constrain(TEnv& tenv, Constraints& c) const throw(Error) {}
-	virtual AST* cps(TEnv& tenv, AST* cont) const;
 	virtual AST* lift(CEnv& cenv, Code& code) throw() { return this; }
-	virtual AST* depoly(CEnv& cenv, Code& code) throw() { return this; }
 	virtual CVal compile(CEnv& env) const throw() = 0;
 	string str() const { ostringstream ss; ss << this; return ss.str(); }
 	template<typename T> T       to()       { return dynamic_cast<T>(this); }
@@ -280,42 +278,148 @@ struct ATuple : public AST {
 		_vec = (AST**)malloc(sizeof(AST*) * _len);
 		memcpy(_vec, exp._vec, sizeof(AST*) * _len);
 	}
+	ATuple(AST* first, AST* rest, Cursor c=Cursor()) : AST(c), _len(2) {
+		_vec = (AST**)malloc(sizeof(AST*) * _len);
+		_vec[0] = first;
+		_vec[1] = rest;
+	}
 	ATuple(Cursor c, AST* ast, va_list args) : AST(c), _len(0), _vec(0) {
 		if (!ast) return;
-		push_back(ast);
-		for (AST* a = va_arg(args, AST*); a; a = va_arg(args, AST*))
-			push_back(a);
+		
+		_len = 2;
+		_vec = (AST**)malloc(sizeof(AST*) * _len);
+		_vec[0] = ast;
+		_vec[1] = NULL;
+
+		ATuple* tail = this;
+		for (AST* a = va_arg(args, AST*); a; a = va_arg(args, AST*)) {
+			ATuple* tup = new ATuple(a, NULL);
+			tail->last(tup);
+			tail = tup;
+		}
 	}
+	
 	~ATuple() { free(_vec); }
-	void push_back(AST* ast) {
-		AST** newvec = (AST**)realloc(_vec, sizeof(AST*) * (_len + 1));
-		newvec[_len++] = ast;
-		_vec = newvec;
-	}
-	void push_front(AST* ast) {
-		AST** newvec = (AST**)malloc(sizeof(AST*) * (_len + 1));
-		newvec[0] = ast;
-		memcpy(newvec + 1, _vec, sizeof(AST*) * _len++);
-		_vec = newvec;
-	}
 	const AST* head()  const { assert(_len > 0); return _vec[0]; }
-	AST*       head()        { assert(_len > 0); return _vec[0]; }
+	AST*&      head()        { assert(_len > 0); return _vec[0]; }
 	const AST* last()  const { return _vec[_len - 1]; }
-	AST*       last()        { return _vec[_len - 1]; }
-	size_t     size()  const { return _len; }
+	AST*&      last()        { return _vec[_len - 1]; }
 	bool       empty() const { return _len == 0; }
 
-	typedef AST**       iterator;
-	typedef AST* const* const_iterator;
-	const_iterator begin() const { return _vec; }
-	iterator       begin()       { return _vec; }
-	const_iterator end()   const { return _vec + _len; }
-	iterator       end()         { return _vec + _len; }
+	size_t tup_len() const { return _len; }
+	size_t list_len() const {
+		size_t ret = 0;
+		for (const_iterator i = begin(); i != end(); ++i, ++ret) {}
+		return ret;
+	}
+
+	const AST* list_last() const {
+		for (const_iterator i = begin(); i != end();) {
+			const_iterator next = i;
+			++next;
+
+			if (next == end())
+				return *i;
 
+			i = next;
+		}
+
+		return NULL;
+	}
+
+	void last(AST* ast) { _vec[_len - 1] = ast; }
+	
+	struct iterator {
+		iterator(ATuple* n) : node(n) {
+			assert(!n || n->tup_len() == 0 || n->tup_len() == 2);
+			if (!n || n->tup_len() == 0)
+				node = NULL;
+		}
+		inline void increment() {
+			if (node->last())
+				node = node->last()->as<ATuple*>();
+			else
+				node = NULL;
+		}
+		inline iterator& operator++() {
+			assert(node);
+			increment();
+			return *this;
+		}
+		inline iterator operator++(int) {
+			assert(node);
+			const iterator ret(node);
+			increment();
+			return ret;
+		}
+		inline bool operator==(const iterator& i) const { return node == i.node; }
+		inline bool operator!=(const iterator& i) const { return node != i.node; }
+		AST*& operator*() { return node->head(); }
+		ATuple* node;
+	};
+
+	struct const_iterator {
+		const_iterator(const ATuple* n) : node(n) {
+			assert(!n || n->tup_len() == 0 || n->tup_len() == 2);
+			if (!n || n->tup_len() == 0)
+				node = NULL;
+		}
+		const_iterator(const iterator& i) : node(i.node) {}
+		inline void increment() {
+			if (node->last())
+				node = node->last()->as<const ATuple*>();
+			else
+				node = NULL;
+		}
+		inline const_iterator& operator++() {
+			assert(node);
+			increment();
+			return *this;
+		}
+		inline const_iterator operator++(int) {
+			assert(node);
+			const const_iterator ret(node);
+			increment();
+			return ret;
+		}
+		inline bool operator==(const const_iterator& i) const {
+			return node == i.node || (!node && i.node->tup_len() == 0);
+		}
+		inline bool operator!=(const const_iterator& i) const {
+			return !operator==(i);
+		}
+		const AST* operator*() { return node->head(); }
+		const ATuple* node;
+	};
+		
+	const_iterator begin() const { assert(_len == 0 || _len == 2); return const_iterator(this); }
+	iterator       begin()       { assert(_len == 0 || _len == 2); return iterator(this); }
+	const_iterator end()   const { return const_iterator(NULL); }
+	iterator       end()         { return iterator(NULL); }
+
+	const_iterator iter_at(unsigned index) const {
+		const_iterator i = begin();
+		for (unsigned idx = 0; idx != index; ++i, ++idx) {
+			assert(i != end());
+		}
+		return i;
+	}
+
+	iterator iter_at(unsigned index) {
+		iterator i = begin();
+		for (unsigned idx = 0; idx != index; ++i, ++idx) {
+			assert(i != end());
+		}
+		return i;
+	}
+			
+	AST*&      list_ref(unsigned index)       { return *iter_at(index); }
+	const AST* list_ref(unsigned index) const { return *iter_at(index); }
+	
 	bool value() const { return false; }
 	bool operator==(const AST& rhs) const {
 		const ATuple* rt = rhs.to<const ATuple*>();
-		if (!rt || rt->size() != size()) return false;
+		if (!rt || rt->tup_len() != tup_len()) return false;
 		const_iterator l = begin();
 		FOREACHP(const_iterator, r, rt)
 			if (!(*(*l++) == *(*r)))
@@ -331,8 +435,6 @@ struct ATuple : public AST {
 	}
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
 	AST* lift(CEnv& cenv, Code& code) throw();
-	AST* depoly(CEnv& cenv, Code& code) throw();
-
 	CVal compile(CEnv& env) const throw();
 
 private:
@@ -340,17 +442,21 @@ private:
 	AST**  _vec;
 };
 
+
 /// Type Expression, e.g. "Int", "(Fn (Int Int) Float)"
 struct AType : public ATuple {
 	enum Kind { VAR, NAME, PRIM, EXPR, DOTS };
-	AType(ASymbol* s, Kind k) : ATuple(s->loc), kind(k), id(0) { push_back(s); }
+	AType(ASymbol* s, Kind k) : ATuple(s, NULL, s->loc), kind(k), id(0) {}
 	AType(Cursor c, unsigned i) : ATuple(c), kind(VAR), id(i) {}
 	AType(Cursor c, Kind k=EXPR) : ATuple(c), kind(k), id(0) {}
 	AType(Cursor c, AST* ast, va_list args) : ATuple(c, ast, args), kind(EXPR), id(0) {}
-	AType(const AType& copy) : ATuple(copy), kind(copy.kind), id(copy.id) { }
+	AType(AST* first, AST* rest, Cursor c) : ATuple(first, rest, c), kind(EXPR), id(0) {}
+	AType(const AType& copy) : ATuple(copy), kind(copy.kind), id(copy.id) {}
 	CVal compile(CEnv& cenv) const throw();
-	const ATuple* prot() const { assert(kind == EXPR); return (*(begin() + 1))->to<const ATuple*>(); }
-	ATuple*       prot()       { assert(kind == EXPR); return (*(begin() + 1))->to<ATuple*>(); }
+	const ATuple* prot() const { assert(kind == EXPR); return list_ref(1)->to<const ATuple*>(); }
+	ATuple*       prot()       { assert(kind == EXPR); return list_ref(1)->to<ATuple*>(); }
+	void          prot(ATuple* prot) { assert(kind == EXPR); *iter_at(1) = prot; }
+
 	bool concrete() const {
 		switch (kind) {
 		case VAR:  return false;
@@ -358,7 +464,7 @@ struct AType : public ATuple {
 		case PRIM: return head()->str() != "Nothing";
 		case EXPR:
 			FOREACHP(const_iterator, t, this) {
-				AType* kid = (*t)->to<AType*>();
+				const AType* kid = (*t)->to<const AType*>();
 				if (kid && !kid->concrete())
 					return false;
 			}
@@ -385,18 +491,54 @@ struct AType : public ATuple {
 	unsigned id;
 };
 
+// Utility class for easily building lists from left to right
+template<typename CT, typename ET> // ConsType, ElementType
+struct List {
+	List(CT* h=0) : head(h), tail(0) {}
+	List(Cursor c, ET* ast, ...) : head(0), tail(0) {
+		push_back(ast);
+		assert(*head->begin() == ast);
+		head->loc = c;
+		va_list args;
+		va_start(args, ast);
+		for (ET* a = va_arg(args, ET*); a; a = va_arg(args, ET*))
+			push_back(a);
+		va_end(args);
+	}
+	void push_back(ET* ast) {
+		if (!head) {
+			head = new CT(ast, NULL, Cursor());
+		} else if (!tail) {
+			CT* node = new CT(ast, NULL, Cursor());
+			head->last(node);
+			tail = node;
+		} else {
+			CT* node = new CT(ast, NULL, Cursor());
+			tail->last(node);
+			tail = node;
+		}
+	}
+	void push_front(ET* ast) {
+		head = new CT(ast, head, Cursor());
+	}
+	operator CT*() const { return head; }
+	CT* head;
+	CT* tail;
+};
+
+typedef List<AType,  AType> TList;
+
 /// Fn (first-class function with captured lexical bindings)
 struct AFn : public ATuple {
 	AFn(const ATuple* exp) : ATuple(*exp) {}
 	AFn(Cursor c, AST* ast, va_list args) : ATuple(c, ast, args) {}
 	bool operator==(const AST& rhs) const { return this == &rhs; }
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
-	AST* cps(TEnv& tenv, AST* cont) const;
 	AST* lift(CEnv& cenv, Code& code) throw();
-	AST* depoly(CEnv& cenv, Code& code) throw();
 	CVal compile(CEnv& env) const throw();
-	const ATuple* prot() const { return (*(begin() + 1))->to<const ATuple*>(); }
-	ATuple*       prot()       { return (*(begin() + 1))->to<ATuple*>(); }
+	const ATuple* prot() const { return list_ref(1)->to<const ATuple*>(); }
+	ATuple*       prot()       { return list_ref(1)->to<ATuple*>(); }
+	void          prot(ATuple* prot) { *iter_at(1) = prot; }
 	string name;
 };
 
@@ -404,10 +546,9 @@ struct AFn : public ATuple {
 struct ACall : public ATuple {
 	ACall(const ATuple* exp) : ATuple(*exp) {}
 	ACall(Cursor c, AST* ast, va_list args) : ATuple(c, ast, args) {}
+	ACall(AST* first, AST* rest, Cursor c) : ATuple(first, rest, c) {}
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
-	AST* cps(TEnv& tenv, AST* cont) const;
 	AST* lift(CEnv& cenv, Code& code) throw();
-	AST* depoly(CEnv& cenv, Code& code) throw();
 	CVal compile(CEnv& env) const throw();
 };
 
@@ -415,8 +556,9 @@ struct ACall : public ATuple {
 struct ADef : public ACall {
 	ADef(const ATuple* exp) : ACall(exp) {}
 	ADef(Cursor c, AST* ast, va_list args) : ACall(c, ast, args) {}
+	ADef(AST* first, AST* rest, Cursor c) : ACall(first, rest, c) {}
 	const ASymbol* sym() const {
-		const AST*     name = *(begin() + 1);
+		const AST*     name = list_ref(1);
 		const ASymbol* sym  = name->to<const ASymbol*>();
 		if (!sym) {
 			const ATuple* tup = name->to<const ATuple*>();
@@ -425,33 +567,29 @@ struct ADef : public ACall {
 		}
 		return sym;
 	}
-	const AST* body() const { return *(begin() + 2); }
-	AST*       body()       { return *(begin() + 2); }
+	const AST* body() const { return list_ref(2); }
+	AST*       body()       { return list_ref(2); }
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
-	AST* cps(TEnv& tenv, AST* cont) const;
 	AST* lift(CEnv& cenv, Code& code) throw();
-	AST* depoly(CEnv& cenv, Code& code) throw();
 	CVal compile(CEnv& env) const throw();
 };
 
 struct ADefType : public ACall {
 	ADefType(const ATuple* exp) : ACall(exp) {}
 	ADefType(Cursor c, AST* ast, va_list args) : ACall(c, ast, args) {}
-	const ASymbol* sym() const { return (*(begin() + 1))->as<const ASymbol*>(); }
+	ADefType(AST* first, AST* rest, Cursor c) : ACall(first, rest, c) {}
+	const ASymbol* sym() const { return list_ref(1)->as<const ASymbol*>(); }
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
-	AST* cps(TEnv& tenv, AST* cont) const;
 	AST* lift(CEnv& cenv, Code& code) throw() { return this; }
-	AST* depoly(CEnv& cenv, Code& code) throw() { return this; }
 	CVal compile(CEnv& env) const throw() { return NULL; }
 };
 
 struct AMatch : public ACall {
 	AMatch(const ATuple* exp) : ACall(exp) {}
 	AMatch(Cursor c, AST* ast, va_list args) : ACall(c, ast, args) {}
+	AMatch(AST* first, AST* rest, Cursor c) : ACall(first, rest, c) {}
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
-	AST* cps(TEnv& tenv, AST* cont) const;
 	AST* lift(CEnv& cenv, Code& code) throw() { return this; }
-	AST* depoly(CEnv& cenv, Code& code) throw() { return this; }
 	CVal compile(CEnv& env) const throw();
 };
 
@@ -459,34 +597,34 @@ struct AMatch : public ACall {
 struct AIf : public ACall {
 	AIf(const ATuple* exp) : ACall(exp) {}
 	AIf(Cursor c, AST* ast, va_list args) : ACall(c, ast, args) {}
+	AIf(AST* first, AST* rest, Cursor c) : ACall(first, rest, c) {}
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
-	AST* cps(TEnv& tenv, AST* cont) const;
 	AST* lift(CEnv& cenv, Code& code) throw();
-	AST* depoly(CEnv& cenv, Code& code) throw();
 	CVal compile(CEnv& env) const throw();
 };
 
 struct ACons : public ACall {
 	ACons(const ATuple* exp) : ACall(exp) {}
 	ACons(Cursor c, AST* ast, va_list args) : ACall(c, ast, args) {}
+	ACons(AST* first, AST* rest, Cursor c) : ACall(first, rest, c) {}
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
 	AST* lift(CEnv& cenv, Code& code) throw();
-	AST* depoly(CEnv& cenv, Code& code) throw();
 	CVal compile(CEnv& env) const throw();
 };
 
 struct ADot : public ACall {
 	ADot(const ATuple* exp) : ACall(exp) {}
 	ADot(Cursor c, AST* ast, va_list args) : ACall(c, ast, args) {}
+	ADot(AST* first, AST* rest, Cursor c) : ACall(first, rest, c) {}
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
 	AST* lift(CEnv& cenv, Code& code) throw();
-	AST* depoly(CEnv& cenv, Code& code) throw();
 	CVal compile(CEnv& env) const throw();
 };
 
 /// Primitive (builtin arithmetic function), e.g. "(+ 2 3)"
 struct APrimitive : public ACall {
 	APrimitive(const ATuple* exp) : ACall(exp) {}
+	APrimitive(AST* first, AST* rest, Cursor c) : ACall(first, rest, c) {}
 	bool value() const {
 		ATuple::const_iterator i = begin();
 		for (++i; i != end(); ++i)
@@ -495,14 +633,13 @@ struct APrimitive : public ACall {
 		return true;
 	}
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
-	AST* cps(TEnv& tenv, AST* cont) const;
 	AST* lift(CEnv& cenv, Code& code) throw();
-	AST* depoly(CEnv& cenv, Code& code) throw();
 	CVal compile(CEnv& env) const throw();
 };
 
 struct AQuote : public ACall {
 	AQuote(const ATuple* exp) : ACall(exp) {}
+	AQuote(AST* first, AST* rest, Cursor c) : ACall(first, rest, c) {}
 	void constrain(TEnv& tenv, Constraints& c) const throw(Error);
 	AST* lift(CEnv& cenv, Code& code) throw();
 	CVal compile(CEnv& env) const throw();
@@ -579,10 +716,11 @@ struct Subst : public list<Constraint> {
 	}
 	const AType* apply(const AType* in) const {
 		if (in->kind == AType::EXPR) {
-			AType* out = tup<AType>(in->loc, NULL);
+			TList out;
 			for (ATuple::const_iterator i = in->begin(); i != in->end(); ++i)
-				out->push_back(const_cast<AType*>(apply((*i)->as<AType*>())));
-			return out;
+				out.push_back(const_cast<AType*>(apply((*i)->as<const AType*>())));
+			out.head->loc = in->loc;
+			return out.head;
 		} else {
 			const_iterator i = find(in);
 			if (i != end()) {