Mercurial > repos > tabletprog

comparison types.js @ 126:a2d2d8e09291

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge
author Mike Pavone <pavone@retrodev.com>
date Mon, 05 Aug 2013 23:37:17 -0700
parents 182c311a9fed
children 09b65b364927
comparison
equal deleted inserted replaced
125:6f8d868e8da0 126:a2d2d8e09291
1 function anytype() {};
2 anytype.prototype.satisfiedBy = function(type) {
3 return true;
4 };
5 anytype.prototype.str = function(indent) {
6 if (indent === undefined) {
7 indent = '';
8 }
9 return indent + 'any\n';
10 };
11 anytype.prototype.id = 0;
12 anytype.prototype.callable = true;
13 anytype.prototype.replaceParams = function() { return this; };
14 var any = new anytype();
15
16 function typeparam(name, base)
17 {
18 this.name = name;
19 this.base = base;
20 this.callable = base.callable;
21 }
22 typeparam.prototype.replaceParams = function(paramtypes) {
23 if (!(this.name in paramtypes)) {
24 return this;
25 }
26 if (!this.base.satisfiedBy(paramtypes[this.name])) {
27 throw new Error('param ' + this.name + ' has base type ' + this.base.str() + ' which is not satisfied by ' + paramtypes[this.name].str());
28 }
29 return paramtypes[this.name];
30 };
31 typeparam.prototype.satisfiedBy = function(type) {
32 return this.base.satisfiedBy(type);
33 };
34 typeparam.prototype.str = function(indent) {
35 return indent + 'param ' + this.name + '\n';
36 };
37
38 var nexttypeid = 1;
39
40 function objecttype()
41 {
42 this.messages = {};
43 this.id = nexttypeid++;
44 this.typeparams = [];
45 this.satisfies_cache = {};
46 this.satisfies_cache[this.id] = true;
47 }
48
49 objecttype.prototype.callable = false;
50
51 objecttype.prototype.addMessage = function(name, type)
52 {
53 this.messages[name] = type;
54 };
55
56 objecttype.prototype.satisfiedBy = function(type) {
57 if (type.id in this.satisfies_cache) {
58 return this.satisfies_cache[type.id];
59 }
60 //temporarily set cache entry to true to prevent infinite recursion
61 this.satisfies_cache[type.id] = true;
62 var ret = true;
63 if (type.messages === undefined) {
64 ret = false;
65 }
66 if (ret) {
67 for (var msgname in this.messages) {
68 if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) {
69 ret = false;
70 break;
71 }
72 }
73 }
74 this.satisfies_cache[type.id] = ret;
75 return ret;
76 };
77
78 objecttype.prototype.str = function(indent) {
79 if (indent === undefined) {
80 indent = '';
81 }
82 if (indent.length > 6) {
83 return 'max depth reached\n';
84 }
85 var newindent = indent + '\t';
86 var childindent = newindent + '\t'
87 var ret = indent + 'objectype {\n';
88 for (var msgname in this.messages) {
89 ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent)
90 }
91 return ret + indent + '}\n';
92 };
93
94 objecttype.prototype.replaceParams = function(paramtypes, visited) {
95 if (visited === undefined) {
96 visited = {};
97 }
98 if (this.id in visited) {
99 return visited[this.id];
100 }
101 var me = visited[this.id] = this.clone();
102 for (var msgname in this.messages) {
103 me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited);
104 }
105 return me;
106 };
107
108 objecttype.prototype.clone = function() {
109 var clone = new objecttype();
110 for (var msgname in this.messages) {
111 clone.messages[msgname] = this.messages[msgname];
112 }
113 clone.typeparams = this.typeparams;
114 return clone;
115 };
116
117 function lambdatype()
118 {
119 this.id = nexttypeid++;
120 this.messages = {};
121 this.params = [];
122 this.paramlu = {};
123 this.typeparams = [];
124 this.returntype = any;
125 this.satisfies_cache = {};
126 this.satisfies_cache[this.id] = true;
127 }
128
129 lambdatype.prototype.callable = true;
130
131 lambdatype.prototype.addParam = function(name) {
132 this.paramlu[name] = this.params.length;
133 this.params.push(any);
134 };
135
136 lambdatype.prototype.paramType = function(name, type) {
137 this.params[this.paramlu[name]] = type;
138 };
139
140 lambdatype.prototype.addMessage = function(name, type)
141 {
142 this.messages[name] = type;
143 };
144
145 lambdatype.prototype.satisfiedBy = function(type) {
146 if (type.id in this.satisfies_cache) {
147 return this.satisfies_cache[type.id];
148 }
149 //temporarily set cache entry to true to prevent infinite recursion
150 this.satisfies_cache[type.id] = true;
151 var ret = true;
152 if (!(type.callable) || this.params.length != type.params.length) {
153 ret = false;
154 }
155 if (ret) {
156 for (var i in this.params) {
157 if (i >= type.params.length || !type.params[i].satisfiedBy(this.params[i])) {
158 ret = false;
159 break;
160 }
161 }
162 }
163 if (ret) {
164 for (var msgname in this.messages) {
165 if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) {
166 ret = false;
167 break;
168 }
169 }
170 }
171 ret = ret && this.returntype.satisfiedBy(type.returntype);
172 this.satisfies_cache[type.id] = ret;
173 return ret;
174 }
175
176 lambdatype.prototype.str = function(indent) {
177 if (indent === undefined) {
178 indent = '';
179 }
180 if (indent.length > 6) {
181 return 'max depth reached\n';
182 }
183 var newindent = indent + '\t';
184 var childindent = newindent + '\t'
185 var ret = indent + 'lambdatype {\n' + newindent + 'params: {\n';
186 for (var i = 0; i < this.params.length; i++) {
187 ret += childindent + i + ':\n' + this.params[i].str(childindent + '\t');
188 }
189 ret += newindent + '}\n' + newindent + 'returntype:\n' + this.returntype.str(childindent);
190
191 for (var msgname in this.messages) {
192 ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent)
193 }
194 return ret + indent + '}\n';
195 };
196
197 lambdatype.prototype.replaceParams = function(paramtypes, visited) {
198 if (visited === undefined) {
199 visited = {};
200 }
201 if (this.id in visited) {
202 return visited[this.id];
203 }
204 var me = visited[this.id] = this.clone();
205 for (var msgname in me.messages) {
206 me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited);
207 }
208 for (var i in me.params) {
209 me.params[i] = me.params[i].replaceParams(paramtypes, visited);
210 }
211 me.returntype = me.returntype.replaceParams(paramtypes, visited);
212 return me;
213 };
214
215 lambdatype.prototype.clone = function() {
216 var clone = new lambdatype();
217 for (var msgname in this.messages) {
218 clone.messages[msgname] = this.messages[msgname];
219 }
220 clone.paramlu = this.paramlu;
221 clone.params = this.params.slice(0, this.params.length);
222 clone.returntype = this.returntype;
223 clone.typeparams = this.typeparams;
224 return clone;
225 };
226
227 function uniontype(a, b)
228 {
229 this.a = a;
230 this.b = b;
231 this.id = nexttypeid++;
232 this.satisfies_cache = null;
233 }
234
235 uniontype.prototype = {
236 lazyinit: function() {
237 if (this.satisfies_cache == null) {
238 this.satisfies_cache = {};
239 this.satisfies_cache[this.id] = true;
240 this._messages = {};
241 if (this.a.messages !== undefined && this.b.messages !== undefined) {
242 for (var msgname in this.a.messages) {
243 if (msgname in this.b.messages) {
244 this._messages[msgname] = mkunion(this.a.messages[msgname], this.b.messages[msgname]);
245 }
246 }
247 }
248 this._callable = false;
249 if (this.a.callable && this.b.callable && this.a.params.length == this.b.params.length) {
250 this._callable = true;
251 this._params = [];
252 for (var i = 0; i < this.a.params.length; i++) {
253 this._params.push(mkunion(this.a.params[i], this.b.params[i]));
254 }
255 this._returntype = mkunion(this.a.returntype, this.b.returntype);
256 }
257 }
258 },
259 satisfiedBy: function(type)
260 {
261 this.lazyinit();
262 if (type.id in this.satisfies_cache) {
263 return this.satisfies_cache[type.id];
264 }
265 this.satisfies_cache[type.id] = true;
266 var ret = this.a.satisfiedBy(type) || this.b.satisfiedBy(type);
267 this.satisfies_cache[type.id] = ret;
268 return ret;
269 },
270 str: function(indent)
271 {
272 if (indent === undefined) {
273 indent = '';
274 }
275 if (indent.length > 6) {
276 return 'max depth reached\n';
277 }
278 return indent + 'Union {\n\t' + indent + this.a.str(indent+'\t') + '\t' + indent + this.b.str(indent+'\t') + indent + '}\n';
279 },
280 replaceParams: function(paramtypes, visited) {
281 if (visited === undefined) {
282 visited = {};
283 }
284 if (this.id in visited) {
285 return visited[this.id];
286 }
287 var me = visited[this.id] = this.clone();
288 me.a = me.a.replaceParams(paramtypes, visited);
289 me.b = me.b.replaceParams(paramtypes, visited);
290 return me;
291 },
292 clone: function() {
293 return new uniontype(this.a, this.b);
294 },
295 get messages() {
296 this.lazyinit();
297 return this._messages;
298 },
299 get params() {
300 this.lazyinit();
301 return this._params;
302 },
303 get returntype() {
304 this.lazyinit();
305 return this._returntype;
306 },
307 get callable() {
308 this.lazyinit();
309 return this._callable;
310 }
311 };
312
313
314 function mkunion(a, b)
315 {
316 //if b is a subtype of a, then a | b is equivalent to a
317 if (a.satisfiedBy(b)) {
318 return a;
319 }
320 //if a is a subtype of b, then a | b is equivalent to b
321 if (b.satisfiedBy(a)) {
322 return b;
323 }
324 return new uniontype(a, b);
325 }
326
327 function withtparams(type, params)
328 {
329 this.type = type;
330 this.params = params;
331 this.replaced = false;
332 }
333
334 withtparams.prototype = {
335 satisfiedBy: function(type) {
336 this.lazyinit();
337 return this.type.satisfiedBy(type);
338 },
339 str: function(indent) {
340 if (indent === undefined) {
341 indent = '';
342 }
343 if (indent.length > 6) {
344 return 'max depth reached\n';
345 }
346 return this.type.str(indent) + indent + '<' + this.params.map(function(p) { return p.str(indent); }).join(', ') + '>';
347 },
348 replaceParams: function(paramtypes) {
349 var replaced = false;
350 for (var i in this.params) {
351 var newp = this.params[i].replaceParams(paramtypes);
352 if (newp != this.params[i]) {
353 replaced = true;
354 this.params[i] = newp;
355 }
356 }
357 return this;
358 },
359 lazyinit: function() {
360 if (!this.replaced) {
361 var childptypes = {};
362 for (var i in this.type.typeparams) {
363 childptypes[this.type.typeparams[i]] = this.params[i]
364 }
365 this.type = this.type.replaceParams(childptypes, {});
366 this.replaced = true;
367 }
368 },
369 get messages() {
370 this.lazyinit();
371 return this.type.messages;
372 }
373 };
374
375 function typetest()
376 {
377 var foo = new objecttype();
378 var msgtype = new lambdatype();
379 msgtype.addParam('fo');
380 msgtype.returntype = foo;
381 foo.addMessage('bar', msgtype);
382 var baz = new objecttype();
383 var msgtype2 = new lambdatype();
384 msgtype2.addParam('fo');
385 msgtype2.paramType('fo', foo);
386 msgtype2.returntype = baz;
387 baz.addMessage('bar', msgtype2);
388 baz.addMessage('qux', msgtype);
389 var shizzle = new objecttype();
390 shizzle.addMessage('bar', msgtype);
391 shizzle.addMessage('boo', msgtype);
392 return {foo: foo, baz: baz, shizzle: shizzle};
393 }
394
395 function paramtypetest()
396 {
397 var empty = new objecttype();
398 var tlnode = new objecttype();
399 tlnode.typeparams = ['T'];
400 var t = new typeparam('T', any);
401 var q = new typeparam('Q', any);
402 var head = new lambdatype();
403 head.returntype = t;
404 tlnode.addMessage('head', head);
405 var tail = new lambdatype();
406 var econs = new lambdatype();
407 econs.addParam('val');
408 econs.typeparams = ['Q'];
409 econs.paramType('val', q);
410 econs.returntype = new withtparams(tlnode, [q]);
411 empty.addMessage('cons', econs);
412 tail.returntype = new uniontype(new withtparams(tlnode, [t]), empty);
413 tlnode.addMessage('tail', tail);
414 var cons = new lambdatype();
415 cons.addParam('val');
416 cons.paramType('val', t);
417 cons.returntype = new withtparams(tlnode, [t]);
418 tlnode.addMessage('cons', cons);
419 return {empty: empty, tlnode: tlnode};
420 }
421