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 int careaboutaggrcount;
319 
320 static int
321 typecmp(Type *t, Type *u)
322 {
323 	int i;
324 
325 	if(t == u)
326 		return 0;
327 	if(t == nil)
328 		return -1;
329 	if(u == nil)
330 		return 1;
331 
332 	if(t->ty < u->ty)
333 		return -1;
334 	if(t->ty > u->ty)
335 		return 1;
336 
337 	if(t->isunion != u->isunion)
338 		return t->isunion - u->isunion;
339 
340 	i = nilstrcmp(t->name, u->name);
341 	if(i)
342 		return i;
343 
344 	i = nilstrcmp(t->suename, u->suename);
345 	if(i)
346 		return i;
347 
348 	if(careaboutaggrcount && t->ty == Aggr){
349 		if(t->n > u->n)
350 			return -1;
351 		if(t->n < u->n)
352 			return 1;
353 	}
354 
355 	if(t->name || t->suename)
356 		return 0;
357 
358 	if(t->ty==Enum){
359 		if(t->n < u->n)
360 			return -1;
361 		if(t->n > u->n)
362 			return 1;
363 		if(t->n == 0)
364 			return 0;
365 		i = strcmp(t->tname[0], u->tname[0]);
366 		return i;
367 	}
368 	if(t < u)
369 		return -1;
370 	if(t > u)
371 		return 1;
372 	return 0;
373 }
374 
375 static int
376 qtypecmp(const void *va, const void *vb)
377 {
378 	Type *t, *u;
379 
380 	t = *(Type**)va;
381 	u = *(Type**)vb;
382 	return typecmp(t, u);
383 }
384 
385 void
386 printtype(Biobuf *b, Type *t)
387 {
388 	char *name;
389 	int j, nprint;
390 	Type *tt, *ttt;
391 
392 	if(t->printed)
393 		return;
394 	t->printed = 1;
395 	switch(t->ty){
396 	case Aggr:
397 		name = nameof(t, 1);
398 		Bprint(b, "sizeof%s = %lud;\n", name, t->xsizeof);
399 		Bprint(b, "aggr %s {\n", name);
400 		nprint = 0;
401 		for(j=0; j<t->n; j++){
402 			tt = defer(t->t[j]);
403 			if(tt && tt->equiv)
404 				tt = tt->equiv;
405 			if(tt == nil){
406 				Bprint(b, "// oops: nil type\n");
407 				continue;
408 			}
409 			switch(tt->ty){
410 			default:
411 				Bprint(b, "// oops: unknown type %d for %p/%s (%d,%d; %c,%s; %p)\n",
412 					tt->ty, tt, fixname(t->tname[j]),
413 					tt->n1, tt->n2, tt->sue ? tt->sue : '.', tt->suename, tt->sub);
414 Bprint(b, "// t->t[j] = %p\n", ttt=t->t[j]);
415 while(ttt){
416 Bprint(b, "// %s %d (%d,%d) sub %p\n", ttt->name, ttt->ty, ttt->n1, ttt->n2, ttt->sub);
417 ttt=ttt->sub;
418 }
419 			case Base:
420 			case Pointer:
421 			case Enum:
422 			case Array:
423 			case Function:
424 				nprint++;
425 				Bprint(b, "\t'%c' %lud %s;\n", basecharof(tt), t->val[j], fixname(t->tname[j]));
426 				break;
427 			case Aggr:
428 				nprint++;
429 				Bprint(b, "\t%s %lud %s;\n", nameof(tt, 1), t->val[j], fixname(t->tname[j]));
430 				break;
431 			}
432 		}
433 		if(nprint == 0)
434 			Bprint(b, "\t'X' 0 __dummy;\n");
435 		Bprint(b, "};\n\n");
436 	
437 		name = nameof(t, 1);	/* might have smashed it */
438 		Bprint(b, "defn %s(addr) { indent_%s(addr, \"\"); }\n", name, name);
439 		Bprint(b, "defn\nindent_%s(addr, indent) {\n", name);
440 		Bprint(b, "\tcomplex %s addr;\n", name);
441 		for(j=0; j<t->n; j++){
442 			name = fixname(t->tname[j]);
443 			tt = defer(t->t[j]);
444 			if(tt == nil){
445 				Bprint(b, "// oops nil %s\n", name);
446 				continue;
447 			}
448 			switch(tt->ty){
449 			case Base:
450 			base:
451 				Bprint(b, "\tprint(indent, \"%s\t\", addr.%s, \"\\n\");\n",
452 					name, name);
453 				break;
454 			case Pointer:
455 				ttt = defer(tt->sub);
456 				if(ttt && ttt->ty == Aggr)
457 					Bprint(b, "\tprint(indent, \"%s\t(%s)\", addr.%s, \"\\n\");\n",
458 						name, nameof(ttt, 1), name);
459 				else
460 					goto base;
461 				break;
462 			case Array:
463 				Bprint(b, "\tprint(indent, \"%s\t\", addr.%s\\X, \"\\n\");\n",
464 					name, name);
465 				break;
466 			case Enum:
467 				Bprint(b, "\tprint(indent, \"%s\t\", addr.%s, \" \", %s(addr.%s), \"\\n\");\n",
468 					name, name, nameof(tt, 1), name);
469 				break;
470 			case Aggr:
471 				Bprint(b, "\tprint(indent, \"%s\t%s{\\n\");\n",
472 					name, nameof(tt, 0));
473 				Bprint(b, "\tindent_%s(addr+%lud, indent+\"  \");\n",
474 					nameof(tt, 1), t->val[j]);
475 				Bprint(b, "\tprint(indent, \"}\\n\");\n");
476 				break;
477 			}
478 		}
479 		Bprint(b, "};\n\n");
480 		break;
481 	
482 	case Enum:
483 		name = nameof(t, 1);
484 		Bprint(b, "// enum %s\n", name);
485 		for(j=0; j<t->n; j++)
486 			Bprint(b, "%s = %ld;\n", fixname(t->tname[j]), t->val[j]);
487 	
488 		Bprint(b, "vals_%s = {\n", name);
489 		for(j=0; j<t->n; j++)
490 			Bprint(b, "\t%lud,\n", t->val[j]);
491 		Bprint(b, "};\n");
492 		Bprint(b, "names_%s = {\n", name);
493 		for(j=0; j<t->n; j++)
494 			Bprint(b, "\t\"%s\",\n", fixname(t->tname[j]));
495 		Bprint(b, "};\n");
496 		Bprint(b, "defn\n%s(val) {\n", name);
497 		Bprint(b, "\tlocal i;\n");
498 		Bprint(b, "\ti = match(val, vals_%s);\n", name);
499 		Bprint(b, "\tif i >= 0 then return names_%s[i];\n", name);
500 		Bprint(b, "\treturn \"???\";\n");
501 		Bprint(b, "};\n");
502 		break;
503 	}
504 }
505 
506 void
507 printtypes(Biobuf *b)
508 {
509 	int i, n, nn;
510 	Type *t, *tt, **all;
511 	TypeList *tl;
512 
513 	/* check that pointer resolved */
514 	for(tl=alltypes; tl; tl=tl->tl){
515 		t = tl->hd;
516 		if(t->ty==None){
517 			if(t->n1 || t->n2)
518 				warn("type %d,%d referenced but not defined", t->n1, t->n2);
519 			else if(t->sue && t->suename)
520 				warn("%s %s referenced but not defined",
521 					t->sue=='s' ? "struct" :
522 					t->sue=='u' ? "union" :
523 					t->sue=='e' ? "enum" : "???", t->suename);
524 		}
525 	}
526 
527 	/* push typedefs down, base types up */
528 	n = 0;
529 	for(tl=alltypes; tl; tl=tl->tl){
530 		n++;
531 		t = tl->hd;
532 		if(t->ty == Typedef || t->ty == Defer)
533 			dotypedef(t);
534 	}
535 
536 	/* push ranges around */
537 	for(tl=alltypes; tl; tl=tl->tl)
538 		dorange(tl->hd);
539 
540 	/*
541 	 * only take one type of a given name; acid is going to do this anyway,
542 	 * and this will reduce the amount of code we output considerably.
543 	 * we could run a DFA equivalence relaxation sort of algorithm
544 	 * to find the actual equivalence classes, and then rename types 
545 	 * appropriately, but this will do for now.
546 	 */
547 	all = emalloc(n*sizeof(all[0]));
548 	n = 0;
549 	for(tl=alltypes; tl; tl=tl->tl)
550 		all[n++] = tl->hd;
551 
552 	careaboutaggrcount = 1;
553 	qsort(all, n, sizeof(all[0]), qtypecmp);
554 	careaboutaggrcount = 0;
555 
556 	nn = 0;
557 	for(i=0; i<n; i++){
558 		if(i==0 || typecmp(all[i-1], all[i]) != 0)
559 			all[nn++] = all[i];
560 		else
561 			all[i]->equiv = all[nn-1];
562 	}
563 
564 	for(tl=alltypes; tl; tl=tl->tl){
565 		t = tl->hd;
566 		tt = defer(t);
567 		if(tt && tt->equiv)
568 			t->equiv = tt->equiv;
569 	}
570 
571 	for(i=0; i<nn; i++)
572 		printtype(b, all[i]);
573 
574 	free(all);
575 }
576 
577 void
578 freetypes(void)
579 {
580 	memset(thash, 0, sizeof(thash));
581 	memset(namehash, 0, sizeof namehash);
582 }