# HG changeset patch
# User Mike Pavone <pavone@retrodev.com>
# Date 1344407361 25200
# Node ID b58b19c455ecbf8a12c42e2166a86da28e3d6f95
# Parent  094227f2f64e2c233c9be3f3abe687048e730de6
Initial work on type system

diff -r 094227f2f64e -r b58b19c455ec compiler.js
--- a/compiler.js	Thu Jul 26 23:41:54 2012 -0700
+++ b/compiler.js	Tue Aug 07 23:29:21 2012 -0700
@@ -448,3 +448,4 @@
 	this.fun = fun;
 }
 getter.prototype.args = [new symbol('self')];
+
diff -r 094227f2f64e -r b58b19c455ec types.js
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/types.js	Tue Aug 07 23:29:21 2012 -0700
@@ -0,0 +1,394 @@
+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};
+}
+