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];
	}
	if (type.lazyinit) {
		type.lazyinit();
	}
	//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 (visisted === 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];
	}
	if (type.lazyinit) {
		type.lazyinit();
	}
	//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 || !this.params[i].satisfiedBy(type.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 (visisted === 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;
};

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 (a.messages !== undefined && b.messages !== undefined) {
			for (var msgname in a.messages) {
				if (msgname in b.messages) {
					this.messages[msgname] = mkunion(a.messages[msgname], b.messages[msgname]);
				}
			}
		}
		this.callable = false;
		if (a.callable && b.callable && a.params.length == b.params.length) {
			this.callable = true;
			this.params = [];
			for (var i = 0; i < a.params.length; i++) {
				this.params.push(mkunion(a.params[i], b.params[i]));
			}
			this.returntype = mkunion(a.returntype, b.returntype);
		}
	}
};

uniontype.prototype.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;
};

uniontype.prototype.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() + '\t' + indent + this.b.str() + indent + '}\n';
};

uniontype.prototype.replaceParams = function(paramtypes, visited) {
	if (visisted === 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;
};

uniontype.prototype.clone = function() {
	return new uniontype(this.a, this.b);
};


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;
}

withtparams.prototype.satisfiedBy = function(type) {
	return this.type.satisfiedBy(type);
};

withtparams.prototype.str = function(indent) {
	return this.type.str(indent) + indent + '<' + this.params.map(function(p) { return p.str(indent); }).join(', ') + '>';
};

withtparams.prototype.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;
		}
	}
	if (replaced) {
		var childptypes = {};
		for (var i in this.type.typeparams) {
			childptypes[this.type.typeparams[i]] = this.params[i]
		}
		this.type = this.type.replaceParams(childptypes, {});
	}
	return this;
};

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};
}