1 #include <u.h>
2 #include <libc.h>
3 #include <bio.h>
4 #include <mach.h>
5 #include <ctype.h>
6 #include "dat.h"
7 
8 char *prefix = "";
9 
10 static TypeList *thash[1021];
11 static TypeList *namehash[1021];
12 static TypeList *alltypes;
13 
14 static uint
15 hash(uint num, uint num1)
16 {
17 	return (num*1009 + num1*1013) % nelem(thash);
18 }
19 
20 static uint
21 shash(char *s)
22 {
23 	uint h;
24 
25 	h = 0;
26 	for(; *s; s++)
27 		h = 37*h + *s;
28 	return h%nelem(namehash);
29 }
30 
31 void
32 addnamehash(Type *t)
33 {
34 	uint h;
35 
36 	if(t->name){
37 		h = shash(t->name);
38 		namehash[h] = mktl(t, namehash[h]);
39 	}
40 }
41 
42 static void
43 addhash(Type *t)
44 {
45 	uint h;
46 
47 	if(t->n1 || t->n2){
48 		h = hash(t->n1, t->n2);
49 		thash[h] = mktl(t, thash[h]);
50 	}
51 	if(t->name)
52 		addnamehash(t);
53 }
54 
55 Type*
56 typebysue(char sue, char *name)
57 {
58 	Type *t;
59 	TypeList *tl;
60 
61 	for(tl=namehash[shash(name)]; tl; tl=tl->tl){
62 		t = tl->hd;
63 		if(t->sue==sue && t->suename && strcmp(name, t->suename)==0)
64 			return t;
65 	}
66 	t = newtype();
67 	if(sue=='e')
68 		t->ty = Enum;
69 	else
70 		t->ty = Aggr;
71 	if(sue=='u')
72 		t->isunion = 1;
73 	t->sue = sue;
74 	t->suename = name;
75 	addnamehash(t);
76 	return t;
77 }
78 
79 Type*
80 typebynum(uint n1, uint n2)
81 {
82 	Type *t;
83 	TypeList *tl;
84 
85 	if(n1 || n2){
86 		for(tl=thash[hash(n1, n2)]; tl; tl=tl->tl){
87 			t = tl->hd;
88 			if(t->n1==n1 && t->n2==n2)
89 				return t;
90 		}
91 	}
92 
93 	t = newtype();
94 	t->n1 = n1;
95 	t->n2 = n2;
96 	addhash(t);
97 	return t;
98 }	
99 
100 Type*
101 newtype(void)
102 {
103 	Type *t;
104 	static int gen;
105 
106 	t = emalloc(sizeof *t);
107 	t->gen = ++gen;
108 	alltypes = mktl(t, alltypes);
109 	return t;
110 }
111 
112 struct {
113 	char *old;
114 	char *new;
115 } fixes[] = { /* Font Tab 4 */
116 	"append",		"$append",
117 	"builtin",		"$builtin",
118 	"complex",		"$complex",
119 	"delete",		"$delete",
120 	"do",			"$do",
121 	"else",			"$else",
122 	"eval",			"$eval",
123 	"fmt",			"$fmt",
124 	"fn",			"$fn",
125 	"head",			"$head",
126 	"if",			"$if",
127 	"local",		"$local",
128 	"loop",			"$loop",
129 	"ret",			"$ret",
130 	"tail",			"$tail",
131 	"then",			"$then",
132 	"whatis",			"$whatis",
133 	"while",		"$while",
134 };
135 
136 char*
137 fixname(char *name)
138 {
139 	int i;
140 
141 	if(name == nil)
142 		return nil;
143 	for(i=0; i<nelem(fixes); i++)
144 		if(name[0]==fixes[i].old[0] && strcmp(name, fixes[i].old)==0)
145 			return fixes[i].new;
146 	return name;
147 }
148 
149 void
150 denumber(void)
151 {
152 	memset(thash, 0, sizeof thash);
153 	memset(namehash, 0, sizeof namehash);
154 }
155 
156 void
157 renumber(TypeList *tl, uint n1)
158 {
159 	Type *t;
160 
161 	for(; tl; tl=tl->tl){
162 		t = tl->hd;
163 		t->n1 = n1;
164 		addhash(t);
165 	}
166 }
167 
168 Type*
169 defer(Type *t)
170 {
171 	Type *u, *oldt;
172 	int n;
173 
174 	u = t;
175 	n = 0;
176 	oldt = t;
177 	while(t && (t->ty == Defer || t->ty == Typedef)){
178 		if(n++%2)
179 			u = u->sub;
180 		t = t->sub;
181 		if(t == u)	/* cycle */
182 			goto cycle;
183 	}
184 	return t;
185 
186 cycle:
187 	fprint(2, "cycle\n");
188 	t = oldt;
189 	n = 0;
190 	while(t && (t->ty==Defer || t->ty==Typedef)){
191 		fprint(2, "t %p/%d %s\n", t, t->ty, t->name);
192 		if(t == u && n++ == 2)
193 			break;
194 		t = t->sub;
195 	}
196 	return u;
197 }
198 
199 static void
200 dotypedef(Type *t)
201 {
202 	if(t->ty != Typedef && t->ty != Defer)
203 		return;
204 
205 	if(t->didtypedef)
206 		return;
207 
208 	t->didtypedef = 1;
209 	if(t->sub == nil)
210 		return;
211 
212 	/* push names downward to remove anonymity */
213 	if(t->name && t->sub->name == nil)
214 		t->sub->name = t->name;
215 
216 	dotypedef(t->sub);
217 }
218 
219 static int
220 countbytes(uvlong x)
221 {
222 	int n;
223 
224 	for(n=0; x; n++)
225 		x>>=8;
226 	return n;
227 }
228 
229 static void
230 dorange(Type *t)
231 {
232 	Type *tt;
233 
234 	if(t->ty != Range)
235 		return;
236 	if(t->didrange)
237 		return;
238 	t->didrange = 1;
239 	tt = defer(t->sub);
240 	if(tt == nil)
241 		return;
242 	dorange(tt);
243 	if(t != tt && tt->ty != Base)
244 		return;
245 	t->ty = Base;
246 	t->xsizeof = tt->xsizeof;
247 	if(t->lo == 0)
248 		t->printfmt = 'x';
249 	else
250 		t->printfmt = 'd';
251 	if(t->xsizeof == 0)
252 		t->xsizeof = countbytes(t->hi);
253 }
254 
255 
256 char*
257 nameof(Type *t, int doanon)
258 {
259 	static char buf[1024];
260 	char *p;
261 
262 	if(t->name)
263 		strcpy(buf, fixname(t->name));
264 	else if(t->suename)
265 		snprint(buf, sizeof buf, "%s_%s", t->isunion ? "union" : "struct", t->suename);
266 	else if(doanon)
267 		snprint(buf, sizeof buf, "%s_%lud_", prefix, t->gen);
268 	else
269 		return "";
270 	for(p=buf; *p; p++)
271 		if(isspace(*p))
272 			*p = '_';
273 	return buf;
274 }
275 
276 static char
277 basecharof(Type *t)	//XXX
278 {
279 	switch(t->xsizeof){
280 	default:
281 		return 'X';
282 	case 1:
283 		return 'b';
284 	case 2:
285 		if(t->printfmt=='d')
286 			return 'd';
287 		else
288 			return 'x';
289 	case 4:
290 		if(t->printfmt=='d')
291 			return 'D';
292 		else if(t->printfmt=='f')
293 			return 'f';
294 		else
295 			return 'X';
296 	case 8:
297 		if(t->printfmt=='d')
298 			return 'V';
299 		else if(t->printfmt=='f')
300 			return 'F';
301 		else
302 			return 'Y';
303 	}
304 }
305 
306 static int
307 nilstrcmp(char *a, char *b)
308 {
309 	if(a == b)
310 		return 0;
311 	if(a == nil)
312 		return -1;
313 	if(b == nil)
314 		return 1;
315 	return strcmp(a, b);
316 }
317 
318 static int
319 typecmp(Type *t, Type *u)
320 {
321 	int i;
322 
323 	if(t == u)
324 		return 0;
325 	if(t == nil)
326 		return -1;
327 	if(u == nil)
328 		return 1;
329 
330 	if(t->ty < u->ty)
331 		return -1;
332 	if(t->ty > u->ty)
333 		return 1;
334 
335 	if(t->isunion != u->isunion)
336 		return t->isunion - u->isunion;
337 
338 	i = nilstrcmp(t->name, u->name);
339 	if(i)
340 		return i;
341 
342 	i = nilstrcmp(t->suename, u->suename);
343 	if(i)
344 		return i;
345 
346 	if(t->name || t->suename)
347 		return 0;
348 
349 	if(t->ty==Enum){
350 		if(t->n < u->n)
351 			return -1;
352 		if(t->n > u->n)
353 			return 1;
354 		if(t->n == 0)
355 			return 0;
356 		i = strcmp(t->tname[0], u->tname[0]);
357 		return i;
358 	}
359 	if(t < u)
360 		return -1;
361 	if(t > u)
362 		return 1;
363 	return 0;
364 }
365 
366 static int
367 qtypecmp(const void *va, const void *vb)
368 {
369 	Type *t, *u;
370 
371 	t = *(Type**)va;
372 	u = *(Type**)vb;
373 	return typecmp(t, u);
374 }
375 
376 void
377 printtype(Biobuf *b, Type *t)
378 {
379 	char *name;
380 	int j, nprint;
381 	Type *tt, *ttt;
382 
383 	if(t->printed)
384 		return;
385 	t->printed = 1;
386 	switch(t->ty){
387 	case Aggr:
388 		name = nameof(t, 1);
389 		Bprint(b, "sizeof%s = %lud;\n", name, t->xsizeof);
390 		Bprint(b, "aggr %s {\n", name);
391 		nprint = 0;
392 		for(j=0; j<t->n; j++){
393 			tt = defer(t->t[j]);
394 			if(tt && tt->equiv)
395 				tt = tt->equiv;
396 			if(tt == nil){
397 				Bprint(b, "// oops: nil type\n");
398 				continue;
399 			}
400 			switch(tt->ty){
401 			default:
402 				Bprint(b, "// oops: unknown type %d for %p/%s (%d,%d; %c,%s; %p)\n",
403 					tt->ty, tt, fixname(t->tname[j]),
404 					tt->n1, tt->n2, tt->sue ? tt->sue : '.', tt->suename, tt->sub);
405 Bprint(b, "// t->t[j] = %p\n", ttt=t->t[j]);
406 while(ttt){
407 Bprint(b, "// %s %d (%d,%d) sub %p\n", ttt->name, ttt->ty, ttt->n1, ttt->n2, ttt->sub);
408 ttt=ttt->sub;
409 }
410 			case Base:
411 			case Pointer:
412 			case Enum:
413 			case Array:
414 			case Function:
415 				nprint++;
416 				Bprint(b, "\t'%c' %lud %s;\n", basecharof(tt), t->val[j], fixname(t->tname[j]));
417 				break;
418 			case Aggr:
419 				nprint++;
420 				Bprint(b, "\t%s %lud %s;\n", nameof(tt, 1), t->val[j], fixname(t->tname[j]));
421 				break;
422 			}
423 		}
424 		if(nprint == 0)
425 			Bprint(b, "\t'X' 0 __dummy;\n");
426 		Bprint(b, "};\n\n");
427 	
428 		name = nameof(t, 1);	/* might have smashed it */
429 		Bprint(b, "defn %s(addr) { indent_%s(addr, \"\"); }\n", name, name);
430 		Bprint(b, "defn\nindent_%s(addr, indent) {\n", name);
431 		Bprint(b, "\tcomplex %s addr;\n", name);
432 		for(j=0; j<t->n; j++){
433 			name = fixname(t->tname[j]);
434 			tt = defer(t->t[j]);
435 			if(tt == nil){
436 				Bprint(b, "// oops nil %s\n", name);
437 				continue;
438 			}
439 			switch(tt->ty){
440 			case Base:
441 			base:
442 				Bprint(b, "\tprint(indent, \"%s\t\", addr.%s, \"\\n\");\n",
443 					name, name);
444 				break;
445 			case Pointer:
446 				ttt = defer(tt->sub);
447 				if(ttt && ttt->ty == Aggr)
448 					Bprint(b, "\tprint(indent, \"%s\t%s(\", addr.%s, \")\\n\");\n",
449 						name, nameof(ttt, 1), name);
450 				else
451 					goto base;
452 				break;
453 			case Array:
454 				Bprint(b, "\tprint(indent, \"%s\t\", addr.%s\\X, \"\\n\");\n",
455 					name, name);
456 				break;
457 			case Enum:
458 				Bprint(b, "\tprint(indent, \"%s\t\", addr.%s, \" \", %s(addr.%s), \"\\n\");\n",
459 					name, name, nameof(tt, 1), name);
460 				break;
461 			case Aggr:
462 				Bprint(b, "\tprint(indent, \"%s\t%s{\\n\");\n",
463 					name, nameof(tt, 0));
464 				Bprint(b, "\tindent_%s(addr+%lud, indent+\"  \");\n",
465 					nameof(tt, 1), t->val[j]);
466 				Bprint(b, "\tprint(indent, \"}\\n\");\n");
467 				break;
468 			}
469 		}
470 		Bprint(b, "};\n\n");
471 		break;
472 	
473 	case Enum:
474 		name = nameof(t, 1);
475 		Bprint(b, "// enum %s\n", name);
476 		for(j=0; j<t->n; j++)
477 			Bprint(b, "%s = %ld;\n", fixname(t->tname[j]), t->val[j]);
478 	
479 		Bprint(b, "vals_%s = {\n", name);
480 		for(j=0; j<t->n; j++)
481 			Bprint(b, "\t%lud,\n", t->val[j]);
482 		Bprint(b, "};\n");
483 		Bprint(b, "names_%s = {\n", name);
484 		for(j=0; j<t->n; j++)
485 			Bprint(b, "\t\"%s\",\n", fixname(t->tname[j]));
486 		Bprint(b, "};\n");
487 		Bprint(b, "defn\n%s(val) {\n", name);
488 		Bprint(b, "\tlocal i;\n");
489 		Bprint(b, "\ti = match(val, vals_%s);\n", name);
490 		Bprint(b, "\tif i >= 0 then return names_%s[i];\n", name);
491 		Bprint(b, "\treturn \"???\";\n");
492 		Bprint(b, "};\n");
493 		break;
494 	}
495 }
496 
497 void
498 printtypes(Biobuf *b)
499 {
500 	int i, n, nn;
501 	Type *t, *tt, **all;
502 	TypeList *tl;
503 
504 	/* check that pointer resolved */
505 	for(tl=alltypes; tl; tl=tl->tl){
506 		t = tl->hd;
507 		if(t->ty==None){
508 			if(t->n1 || t->n2)
509 				warn("type %d,%d referenced but not defined", t->n1, t->n2);
510 			else if(t->sue && t->suename)
511 				warn("%s %s referenced but not defined",
512 					t->sue=='s' ? "struct" :
513 					t->sue=='u' ? "union" :
514 					t->sue=='e' ? "enum" : "???", t->suename);
515 		}
516 	}
517 
518 	/* push typedefs down, base types up */
519 	n = 0;
520 	for(tl=alltypes; tl; tl=tl->tl){
521 		n++;
522 		t = tl->hd;
523 		if(t->ty == Typedef || t->ty == Defer)
524 			dotypedef(t);
525 	}
526 
527 	/* push ranges around */
528 	for(tl=alltypes; tl; tl=tl->tl)
529 		dorange(tl->hd);
530 
531 	/*
532 	 * only take one type of a given name; acid is going to do this anyway,
533 	 * and this will reduce the amount of code we output considerably.
534 	 * we could run a DFA equivalence relaxation sort of algorithm
535 	 * to find the actual equivalence classes, and then rename types 
536 	 * appropriately, but this will do for now.
537 	 */
538 	all = emalloc(n*sizeof(all[0]));
539 	n = 0;
540 	for(tl=alltypes; tl; tl=tl->tl)
541 		all[n++] = tl->hd;
542 
543 	qsort(all, n, sizeof(all[0]), qtypecmp);
544 
545 	nn = 0;
546 	for(i=0; i<n; i++){
547 		if(i==0 || typecmp(all[i-1], all[i]) != 0)
548 			all[nn++] = all[i];
549 		else
550 			all[i]->equiv = all[nn-1];
551 	}
552 
553 	for(tl=alltypes; tl; tl=tl->tl){
554 		t = tl->hd;
555 		tt = defer(t);
556 		if(tt && tt->equiv)
557 			t->equiv = tt->equiv;
558 	}
559 
560 	for(i=0; i<nn; i++)
561 		printtype(b, all[i]);
562 
563 	free(all);
564 }
565 
566 void
567 freetypes(void)
568 {
569 	memset(thash, 0, sizeof(thash));
570 	memset(namehash, 0, sizeof namehash);
571 }