function anytype() {};
anytype.prototype.satisfiedBy = function(type) {
	return true;
};
anytype.prototype.str = function(indent) {
	if (indent === undefined) {
		indent = '';
	}
	return indent + 'any\n';
};
anytype.prototype.id = 0;
anytype.prototype.callable = true;
anytype.prototype.replaceParams = function() { return this; };
var any = new anytype();

function typeparam(name, base)
{
	this.name = name;
	this.base = base;
	this.callable = base.callable;
}
typeparam.prototype.replaceParams = function(paramtypes) {
	if (!(this.name in paramtypes)) {
		return this;
	}
	if (!this.base.satisfiedBy(paramtypes[this.name])) {
		throw new Error('param ' + this.name + ' has base type ' + this.base.str() + ' which is not satisfied by ' + paramtypes[this.name].str());
	}
	return paramtypes[this.name];
};
typeparam.prototype.satisfiedBy = function(type) {
	return this.base.satisfiedBy(type);
};
typeparam.prototype.str = function(indent) {
	return indent + 'param ' + this.name + '\n';
};

var nexttypeid = 1;

function objecttype()
{
	this.messages = {};
	this.id = nexttypeid++;
	this.typeparams = [];
	this.satisfies_cache = {};
	this.satisfies_cache[this.id] = true;
}

objecttype.prototype.callable = false;

objecttype.prototype.addMessage = function(name, type)
{
	this.messages[name] = type;
};

objecttype.prototype.satisfiedBy = function(type) {
	if (type.id in this.satisfies_cache) {
		return this.satisfies_cache[type.id];
	}
	//temporarily set cache entry to true to prevent infinite recursion
	this.satisfies_cache[type.id] = true;
	var ret = true;
	if (type.messages === undefined) {
		ret = false;
	}
	if (ret) {
		for (var msgname in this.messages) {
			if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) {
				ret = false;
				break;
			}
		}
	}
	this.satisfies_cache[type.id] = ret;
	return ret;
};

objecttype.prototype.str = function(indent) {
	if (indent === undefined) {
		indent = '';
	}
	if (indent.length > 6) {
		return 'max depth reached\n';
	}
	var newindent = indent + '\t';
	var childindent = newindent + '\t'
	var ret = indent + 'objectype {\n';
	for (var msgname in this.messages) {
		ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent)
	}
	return ret + indent + '}\n';
};

objecttype.prototype.replaceParams = function(paramtypes, visited) {
	if (visited === undefined) {
		visited = {};
	}
	if (this.id in visited) {
		return visited[this.id];
	}
	var me = visited[this.id] = this.clone();
	for (var msgname in this.messages) {
		me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited);
	}
	return me;
};

objecttype.prototype.clone = function() {
	var clone = new objecttype();
	for (var msgname in this.messages) {
		clone.messages[msgname] = this.messages[msgname];
	}
	clone.typeparams = this.typeparams;
	return clone;
};

function lambdatype()
{
	this.id = nexttypeid++;
	this.messages = {};
	this.params = [];
	this.paramlu = {};
	this.typeparams = [];
	this.returntype = any;
	this.satisfies_cache = {};
	this.satisfies_cache[this.id] = true;
}

lambdatype.prototype.callable = true;

lambdatype.prototype.addParam = function(name) {
	this.paramlu[name] = this.params.length;
	this.params.push(any);
};

lambdatype.prototype.paramType = function(name, type) {
	this.params[this.paramlu[name]] = type;
};

lambdatype.prototype.addMessage = function(name, type)
{
	this.messages[name] = type;
};

lambdatype.prototype.satisfiedBy = function(type) {
	if (type.id in this.satisfies_cache) {
		return this.satisfies_cache[type.id];
	}
	//temporarily set cache entry to true to prevent infinite recursion
	this.satisfies_cache[type.id] = true;
	var ret = true;
	if (!(type.callable) || this.params.length != type.params.length) {
		ret = false;
	}
	if (ret) {
		for (var i in this.params) {
			if (i >= type.params.length || !type.params[i].satisfiedBy(this.params[i])) {
				ret = false;
				break;
			}
		}
	}
	if (ret) {
		for (var msgname in this.messages) {
			if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) {
				ret = false;
				break;
			}
		}
	}
	ret = ret && this.returntype.satisfiedBy(type.returntype);
	this.satisfies_cache[type.id] = ret;
	return ret;
}

lambdatype.prototype.str = function(indent) {
	if (indent === undefined) {
		indent = '';
	}
	if (indent.length > 6) {
		return 'max depth reached\n';
	}
	var newindent = indent + '\t';
	var childindent = newindent + '\t'
	var ret = indent + 'lambdatype {\n' + newindent + 'params: {\n';
	for (var i = 0; i < this.params.length; i++) {
		ret += childindent + i + ':\n' + this.params[i].str(childindent + '\t');
	}
	ret += newindent + '}\n' + newindent + 'returntype:\n' + this.returntype.str(childindent);
	
	for (var msgname in this.messages) {
		ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent)
	}
	return ret + indent + '}\n';
};

lambdatype.prototype.replaceParams = function(paramtypes, visited) {
	if (visited === undefined) {
		visited = {};
	}
	if (this.id in visited) {
		return visited[this.id];
	}
	var me = visited[this.id] = this.clone();
	for (var msgname in me.messages) {
		me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited);
	}
	for (var i in me.params) {
		me.params[i] = me.params[i].replaceParams(paramtypes, visited);
	}
	me.returntype = me.returntype.replaceParams(paramtypes, visited);
	return me;
};

lambdatype.prototype.clone = function() {
	var clone = new lambdatype();
	for (var msgname in this.messages) {
		clone.messages[msgname] = this.messages[msgname];
	}
	clone.paramlu = this.paramlu;
	clone.params = this.params.slice(0, this.params.length);
	clone.returntype = this.returntype;
	clone.typeparams = this.typeparams;
	return clone;
};

function uniontype(a, b)
{
	this.a = a;
	this.b = b;
	this.id = nexttypeid++;
	this.satisfies_cache = null;
}

uniontype.prototype = {
	lazyinit: function() {
		if (this.satisfies_cache == null) {
			this.satisfies_cache = {};
			this.satisfies_cache[this.id] = true;
			this._messages = {};
			if (this.a.messages !== undefined && this.b.messages !== undefined) {
				for (var msgname in this.a.messages) {
					if (msgname in this.b.messages) {
						this._messages[msgname] = mkunion(this.a.messages[msgname], this.b.messages[msgname]);
					}
				}
			}
			this._callable = false;
			if (this.a.callable && this.b.callable && this.a.params.length == this.b.params.length) {
				this._callable = true;
				this._params = [];
				for (var i = 0; i < this.a.params.length; i++) {
					this._params.push(mkunion(this.a.params[i], this.b.params[i]));
				}
				this._returntype = mkunion(this.a.returntype, this.b.returntype);
			}
		}
	},
	satisfiedBy: function(type)
	{
		this.lazyinit();
		if (type.id in this.satisfies_cache) {
			return this.satisfies_cache[type.id];
		}
		this.satisfies_cache[type.id] = true;
		var ret = this.a.satisfiedBy(type) || this.b.satisfiedBy(type);
		this.satisfies_cache[type.id] = ret;
		return ret;
	},
	str: function(indent)
	{
		if (indent === undefined) {
			indent = '';
		}
		if (indent.length > 6) {
			return 'max depth reached\n';
		}
		return indent + 'Union {\n\t' + indent + this.a.str(indent+'\t') + '\t' + indent + this.b.str(indent+'\t') + indent + '}\n';
	},
	replaceParams: function(paramtypes, visited) {
		if (visited === undefined) {
			visited = {};
		}
		if (this.id in visited) {
			return visited[this.id];
		}
		var me = visited[this.id] = this.clone();
		me.a = me.a.replaceParams(paramtypes, visited);
		me.b = me.b.replaceParams(paramtypes, visited);
		return me;
	},
	clone: function() {
		return new uniontype(this.a, this.b);
	},
	get messages() {
		this.lazyinit();
		return this._messages;
	},
	get params() {
		this.lazyinit();
		return this._params;
	},
	get returntype() {
		this.lazyinit();
		return this._returntype;
	},
	get callable() {
		this.lazyinit();
		return this._callable;
	}
};


function mkunion(a, b)
{
	//if b is a subtype of a, then a | b is equivalent to a
	if (a.satisfiedBy(b)) {
		return a;
	}
	//if a is a subtype of b, then a | b is equivalent to b
	if (b.satisfiedBy(a)) {
		return b;
	}
	return new uniontype(a, b);
}

function withtparams(type, params)
{
	this.type = type;
	this.params = params;
	this.replaced = false;
}

withtparams.prototype = {
	satisfiedBy: function(type) {
		this.lazyinit();
		return this.type.satisfiedBy(type);
	},
	str: function(indent) {
		if (indent === undefined) {
			indent = '';
		}
		if (indent.length > 6) {
			return 'max depth reached\n';
		}
		return this.type.str(indent) + indent + '<' + this.params.map(function(p) { return p.str(indent); }).join(', ') + '>';
	},
	replaceParams: function(paramtypes) {
		var replaced = false;
		for (var i in this.params) {
			var newp = this.params[i].replaceParams(paramtypes);
			if (newp != this.params[i]) {
				replaced = true;
				this.params[i] = newp;
			}
		}
		return this;
	},
	lazyinit: function() {
		if (!this.replaced) {
			var childptypes = {};
			for (var i in this.type.typeparams) {
				childptypes[this.type.typeparams[i]] = this.params[i]
			}
			this.type = this.type.replaceParams(childptypes, {});
			this.replaced = true;
		}
	},
	get messages() {
		this.lazyinit();
		return this.type.messages;
	}
};

object.prototype.toType = function(parent) {
	var me = new objecttype();
	for (var i in this.messages) {
		this.messages[i].toObjectType(me);
	}
	return me;
};

lambda.prototype.toType = function(parent) {
	var me = new lambdatype();
	for (var i in this.args) {
		me.addParam(this.args[i].cleanName());
	}
	for (var i in this.expressions) {
		this.expressions[i].toType(me);
	}
	return me;
};

funcall.prototype.toType = function(parent) {
	var name = this.name[this.name.length-1] == ':' ? this.name.substr(0, this.name.length-1) : this.name;
	switch(name)
	{
	case 'typeParam':
		break;
	case 'isa':
		break;
};

assignment.prototype.toObjectType = function(parent) {
	if (this.expression.instanceof lambda) {
		parent.addMessage(this.symbol.name, this.expression.toType(parent));
	} else {
		var valtype = this.expression.toType(parent);
		var getter = new lambdatype();
		getter.returntype = valtype;
		var setter = new lambdatype();
		setter.addParam('val');
		setter.paramType('val', valtype);
		setter.returntype = parent;
		parent.addMessage(this.symbol.name, setter);
	}
};

function typetest()
{
	var foo = new objecttype();
	var msgtype = new lambdatype();
	msgtype.addParam('fo');
	msgtype.returntype = foo;
	foo.addMessage('bar', msgtype);
	var baz = new objecttype();
	var msgtype2 = new lambdatype();
	msgtype2.addParam('fo');
	msgtype2.paramType('fo', foo);
	msgtype2.returntype = baz;
	baz.addMessage('bar', msgtype2);
	baz.addMessage('qux', msgtype);
	var shizzle = new objecttype();
	shizzle.addMessage('bar', msgtype);
	shizzle.addMessage('boo', msgtype);
	return {foo: foo, baz: baz, shizzle: shizzle};
}

function paramtypetest()
{
	var empty = new objecttype();
	var tlnode = new objecttype();
	tlnode.typeparams = ['T'];
	var t = new typeparam('T', any);
	var q = new typeparam('Q', any);
	var head = new lambdatype();
	head.returntype = t;
	tlnode.addMessage('head', head);
	var tail = new lambdatype();
	var econs = new lambdatype();
	econs.addParam('val');
	econs.typeparams = ['Q'];
	econs.paramType('val', q);
	econs.returntype = new withtparams(tlnode, [q]);
	empty.addMessage('cons', econs);
	tail.returntype = new uniontype(new withtparams(tlnode, [t]), empty);
	tlnode.addMessage('tail', tail);
	var cons = new lambdatype();
	cons.addParam('val');
	cons.paramType('val', t);
	cons.returntype = new withtparams(tlnode, [t]);
	tlnode.addMessage('cons', cons);
	return {empty: empty, tlnode: tlnode};
}