Mercurial > repos > tabletprog
view types.js @ 237:dae093baf36c
Optimized implementation of character classes
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Sun, 05 Jan 2014 17:00:33 -0800 |
parents | 09b65b364927 |
children |
line wrap: on
line source
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}; }