scc

commit 8520ba859462224688f0afc7d3495afa7e44a5b2
parent de55e87b768afada683c7203c451ff9f2975d085
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date:   Mon,  7 Oct 2013 19:38:06 +0200

Merge branch 'tree'

Conflicts:
	flow.c

Diffstat:
M
decl.c
 | 
30
++++++++++++++++--------------
M
expr.c
 | 
35
++++++++++++++++++-----------------
M
flow.c
 | 
37
+++++++++++++++++++++----------------
M
syntax.h
 | 
22
+++++++++++++---------
M
tree.c
 | 
289
+++++++++++++++++++++++++++++--------------------------------------------------

5 files changed, 172 insertions(+), 241 deletions(-)
diff --git a/decl.c b/decl.c
@@ -288,27 +288,29 @@ declarator(struct ctype *tp, unsigned char ns)
 static struct node *
 initializer(register struct ctype *tp)
 {
-	register struct node *np;
-
 	if (accept('{')) {
-		np = nodecomp();
-		addstmt(np, initializer(tp));
+		struct compound c;
+
+		c.tree = NULL;
+		addstmt(&c, initializer(tp));
 		while (accept(',')) {
 			if (accept('}'))
-				return np;
-			addstmt(np, initializer(tp));
+				return c.tree;
+			addstmt(&c, initializer(tp));
 		}
 		expect('}');
+		return c.tree;
 	} else {
-		np = expr();
+		return expr();
 	}
-	return np;
 }
 
 static struct node *
 listdcl(struct ctype *base)
 {
-	struct node *lp = nodecomp();
+	struct compound c;
+
+	c.tree = NULL;
 
 	do {
 		struct node *sp, *np;
@@ -322,15 +324,15 @@ listdcl(struct ctype *base)
 
 		sp = nodesym(cursym);
 		if (tp->type == FTN && yytoken == '{') {
-			np  = node2(ODEF, sp, function(cursym));
-			return addstmt(lp, np);
+			np  = node(ODEF, sp, function(cursym));
+			return addstmt(&c, np);
 		}
-		np = node2(ODEF, sp, accept('=') ? initializer(tp) : NULL);
-		lp = addstmt(lp, np);
+		np = node(ODEF, sp, accept('=') ? initializer(tp) : NULL);
+		addstmt(&c, np);
 	} while (accept(','));
 	expect(';');
 
-	return lp;
+	return c.tree;
 }
 
 struct node *
diff --git a/expr.c b/expr.c
@@ -63,15 +63,15 @@ postfix(void)
 		default:    return np1;
 		}
 	node_2_childs:
-		np1 = node2(op, np1, np2);
+		np1 = node(op, np1, np2);
 		continue;
 	expect_iden:
 		next();
 		expect(IDEN);
-		np1 = node2(op, np1, nodesym(yyval.sym));
+		np1 = node(op, np1, nodesym(yyval.sym));
 		continue;
 	next:
-		np1 = node1(op, np1);
+		np1 = node(op, np1, NULL);
 		next();
 		continue;
 	}
@@ -107,11 +107,11 @@ unary(void)
 
 call_cast:
 	next();
-	return node1(op, cast());
+	return node(op, cast(), NULL);
 
 call_unary:
 	next();
-	return node1(op, unary());
+	return node(op, unary(), NULL);
 }
 
 static struct node *
@@ -139,7 +139,7 @@ mul(void)
 		default:  return np;
 		}
 		next();
-		np = node2(op, np, cast());
+		np = node(op, np, cast());
 	}
 }
 
@@ -157,7 +157,7 @@ add(void)
 		default:  return np;
 		}
 		next();
-		np = node2(op, np, mul());
+		np = node(op, np, mul());
 	}
 }
 
@@ -175,7 +175,7 @@ shift(void)
 		default:  return np;
 		}
 		next();
-		np = node2(op, np, add());
+		np = node(op, np, add());
 	}
 }
 
@@ -195,7 +195,7 @@ relational(void)
 		default:  return np;
 		}
 		next();
-		np = node2(op, np, shift());
+		np = node(op, np, shift());
 	}
 }
 
@@ -213,7 +213,7 @@ eq(void)
 		default: return np;
 		}
 		next();
-		np = node2(op, np, relational());
+		np = node(op, np, relational());
 	}
 }
 
@@ -225,7 +225,7 @@ bit_and(void)
 	np = eq();
 	while (yytoken == '&') {
 		next();
-		np = node2(OBAND, np, eq());
+		np = node(OBAND, np, eq());
 	}
 	return np;
 }
@@ -238,7 +238,7 @@ bit_xor(void)
 	np = bit_and();
 	while (yytoken == '^') {
 		next();
-		np = node2(OBXOR, np, bit_and());
+		np = node(OBXOR, np, bit_and());
 	}
 	return np;
 }
@@ -251,7 +251,7 @@ bit_or(void)
 	np = bit_xor();
 	while (yytoken == '|') {
 		next();
-		np = node2(OBOR, np, bit_xor());
+		np = node(OBOR, np, bit_xor());
 	}
 	return np;
 }
@@ -264,7 +264,7 @@ and(void)
 	np = bit_or();
 	while (yytoken == AND) {
 		next();
-		np = node2(OAND, np, bit_or());
+		np = node(OAND, np, bit_or());
 	}
 	return np;
 }
@@ -277,7 +277,7 @@ or(void)
 	np = and();
 	while (yytoken == OR) {
 		next();
-		np = node2(OOR, np, and());
+		np = node(OOR, np, and());
 	}
 	return np;
 }
@@ -291,7 +291,8 @@ cond(void)
 	while (yytoken == '?') {
 		aux = expr();
 		expect(':');
-		np = node3(OTERN, np, aux, or());
+		np = node(OTERN, np,
+		          node(O2EXP, aux, or()));
 	}
 	return np;
 }
@@ -319,7 +320,7 @@ assign(void)
 		default:  goto return_np;
 		}
 		next();
-		np = node2(op, np, assign());
+		np = node(op, np, assign());
 	}
 return_np:
 	return np;
diff --git a/flow.c b/flow.c
@@ -59,7 +59,7 @@ _goto(void)
 	sym = yyval.sym;
 	if (sym->ns != NS_LABEL)
 		sym = newlabel(sym, yytext);
-	np = node1(OGOTO, nodesym(sym));
+	np = node(OGOTO, nodesym(sym), NULL);
 	expect(';');
 
 	return np;
@@ -75,7 +75,7 @@ _while(void)
 	cond = expr();
 	expect(')');
 	push(OWHILE);
-	np = node2(OWHILE, cond, stmt());
+	np = node(OWHILE, cond, stmt());
 	pop();
 	return np;
 }
@@ -94,7 +94,7 @@ _do(void)
 	expect(';');
 
 	push(ODO);
-	np = node2(ODO, body, cond);
+	np = node(ODO, body, cond);
 	pop();
 	return np;
 }
@@ -115,7 +115,9 @@ _for(void)
 	expect(')');
 
 	push(OFOR);
-	np = node2(OFOR, node3(OFEXP, exp1, exp2, exp3), stmt());
+	np = node(OFOR, exp1,
+	          node(O2EXP, exp2,
+	               node(O2EXP, exp3, stmt())));
 	pop();
 	return np;
 }
@@ -131,7 +133,8 @@ _if(void)
 	expect(')');
 	body = stmt();
 
-	return node3(OIF, cond, body, (accept(ELSE)) ? stmt() : NULL);
+	return node(OIF, cond,
+	            node(O2EXP, body, (accept(ELSE)) ? stmt() : NULL));
 }
 
 static struct node *
@@ -145,7 +148,7 @@ _switch(void)
 	expect(')');
 
 	push(OSWITCH);
-	np = node2(OSWITCH, cond, stmt());
+	np = node(OSWITCH, cond, stmt());
 	pop();
 	return np;
 }
@@ -157,7 +160,7 @@ label(void)
 
 	sym = newlabel(sym, yytext);
 	next(), next();  	/* skip IDEN and ':' */
-	return node2(OLABEL, nodesym(sym), stmt());
+	return node(OLABEL, nodesym(sym), stmt());
 }
 
 static struct node *
@@ -167,7 +170,7 @@ _break(void)
 	expect(';');
 	if (blockp == blocks)
 		error("break statement not within loop or switch");
-	return node1(OBREAK, NULL);
+	return node(OBREAK, NULL, NULL);
 }
 
 static struct node *
@@ -183,7 +186,7 @@ _continue(void)
 	if (bp == blockp)
 		error("continue statement not within loop");
 
-	return node1(OCONT, NULL);
+	return node(OCONT, NULL, NULL);
 }
 
 static struct node *
@@ -195,7 +198,7 @@ _return(void)
 	np = expr();
 	expect(';');
 
-	return node1(ORETURN, np);
+	return node(ORETURN, np, NULL);
 }
 
 static struct node *
@@ -212,7 +215,7 @@ _case(void)
 		; /* nothing */
 	if (bp == blockp)
 		error("case statement not within switch");
-	np = node1(OCASE, exp);
+	np = node(OCASE, exp, NULL);
 	expect(':');
 	return np;
 }
@@ -228,15 +231,17 @@ _default(void)
 	if (bp == blockp)
 		error("default statement not within switch");
 	expect(':');
-	return node1(ODEFAULT, NULL);
+	return node(ODEFAULT, NULL, NULL);
 }
 
 static struct node *
 compound(void)
 {
-	register struct node *lp = nodecomp(), *np;
+	register struct node *np;
 	unsigned char nodecl = 0;
+	struct compound c;
 
+	c.tree = NULL;
 	expect('{');
 	new_ctx();
 	while (!accept('}')) {
@@ -249,11 +254,11 @@ compound(void)
 			np = stmt();
 			nodecl = 1;
 		}
-		addstmt(lp, np);
+		addstmt(&c, np);
 	}
 	del_ctx();
 
-	return lp;
+	return c.tree;
 }
 
 static struct node *
@@ -285,7 +290,7 @@ struct node *
 function(register struct symbol *sym)
 {
 	curfun = sym;
-	return node1(OFTN, compound());
+	return node(OFTN, compound(), NULL);
 }
 
 void
diff --git a/syntax.h b/syntax.h
@@ -1,6 +1,10 @@
 #ifndef SYNTAX_H
 #define SYNTAX_H
 
+#if ! __bool_true_false_are_defined
+# include <stdbool.h>
+#endif
+
 extern unsigned char curctx;
 
 enum opcode {
@@ -12,26 +16,26 @@ enum opcode {
 	OA_MOD, OA_ADD, OA_SUB, OA_SHL, OA_SHR, OA_AND,
 	OA_XOR, OA_OR, OSYM, OCOMP, OSWITCH, OIF, OFOR,
 	OFEXP, ODO, OWHILE, OLABEL, OGOTO, OBREAK, OCONT,
-	ORETURN, OCASE, ODEFAULT, OFTN, ODEF
+	ORETURN, OCASE, ODEFAULT, OFTN, ODEF, O2EXP
 };
 
 struct node;
 struct symbol;
 
+struct compound {
+	struct node *tree;
+	struct node_op2 *last;
+};
+
 extern struct node *expr(void);
 extern struct node *decl(void);
 extern void type_name(void);
 extern struct node *function(struct symbol *sym);
 
-extern struct node *node3(unsigned char op,
-			  struct node *l, struct node *i, struct node *r);
-extern struct node *node2(unsigned char op, struct node *l, struct node *r);
-extern struct node *node1(unsigned char op, struct node *i);
-
+extern struct node *node(unsigned char op, struct node *l, struct node *r);
 extern struct node *nodesym(struct symbol *sym);
-extern struct node *nodecomp(void);
-extern struct node *addstmt(struct node *np, struct node *stmt);
-
+extern struct node *addstmt(struct compound *p, struct node *np);
+extern bool walk(register struct node *np, bool (*fun)(struct node *));
 extern void prtree(register struct node *np);
 
 #endif
diff --git a/tree.c b/tree.c
@@ -1,8 +1,6 @@
 
 #include <assert.h>
-#include <stddef.h>
 #include <stdio.h>
-#include <stdint.h>
 
 #include "cc.h"
 #include "syntax.h"
@@ -12,43 +10,22 @@ struct node {
 	unsigned char op;
 };
 
-struct node_op1 {
-	struct node base;
-	struct node *infix;
-};
-
 struct node_op2 {
 	struct node base;
 	struct node *left;
-	struct node *rigth;
-};
-
-struct node_op3 {
-	struct node base;
-	struct node *left;
-	struct node *infix;
-	struct node *rigth;
+	struct node *right;
 };
 
-struct node_sym {
+struct nodesym {
 	struct node base;
 	struct symbol *sym;
 };
 
-struct node_comp {
-	struct node base;
-	uint8_t nr, alloc;
-	struct node **body;
-};
-
-
-static unsigned char indent;  /* used for pretty printing the tree*/
-
 
 struct node *
 nodesym(struct symbol *sym)
 {
-	register struct node_sym *np = xmalloc(sizeof(*np));
+	register struct nodesym *np = xmalloc(sizeof(*np));
 
 	np->base.op = OSYM;
 	np->sym = sym;
@@ -56,193 +33,135 @@ nodesym(struct symbol *sym)
 }
 
 struct node *
-node3(unsigned char op, struct node *l, struct node *i, struct node *r)
-{
-	register struct node_op3 *np = xmalloc(sizeof(*np));
-
-	np->base.op = op;
-	np->left = l;
-	np->infix = i;
-	np->rigth = r;
-
-	return (struct node *) np;
-}
-
-struct node *
-node2(unsigned char op, struct node *l, struct node *r)
+node(unsigned char op, struct node *l, struct node *r)
 {
 	register struct node_op2 *np = xmalloc(sizeof(*np));
 
 	np->base.op = op;
 	np->left = l;
-	np->rigth = r;
-
-	return (struct node *) np;
-}
-
-struct node *
-node1(unsigned char op, struct node *i)
-{
-	register struct node_op1 *np = xmalloc(sizeof(*np));
-
-	np->base.op = op;
-	np->infix = i;
+	np->right = r;
 
 	return (struct node *) np;
 }
 
 struct node *
-nodecomp(void)
+addstmt(struct compound *p, struct node *np)
 {
-	register struct node_comp *np = xmalloc(sizeof(*np));
-
-	np->base.op = OCOMP;
-	np->alloc = np->nr = 0;
-	np->body = NULL;
+	if (!p->tree) {
+		p->tree = node(OCOMP, NULL, NULL);
+		p->last = (struct node_op2 *) p->tree;
+		p->last->right = np;
+	} else {
+		p->last = (struct node_op2 *)
+		   (p->last->left = node(O2EXP, NULL, np));
+	}
 
-	return (struct node *) np;
+	return p->tree;
 }
 
-struct node *
-addstmt(struct node *p, struct node *stmt)
+bool
+walk(register struct node *np, bool (*fun)(struct node *))
 {
-	register uint8_t nr, alloc;
-	register struct node_comp *np = (struct node_comp *) p;
+	struct node_op2 *p;
 
-	assert(np && np->base.op == OCOMP);
-	nr = ++np->nr, alloc = np->alloc;
+	if (!np || np->op == OSYM)
+		return 1;
 
-#define alloc_nr(x) ((((x)+16)*3)/2)
-	if (nr > alloc) {
-		alloc = alloc_nr(nr);
-		np->body = xrealloc(np->body, alloc * sizeof(*np->body));
-	}
-#undef alloc_nr
-
-	np->body[nr - 1] = stmt;
-	np->alloc = alloc;
-	return p;
+	p = (struct node_op2 *) np;
+	return (*fun)(np) && walk(p->left, fun) && walk(p->right, fun);
 }
 
-static void
-prtree_helper(register struct node *np)
+void
+prtree(register struct node *np)
 {
-	static struct optab {
-		unsigned char nchild;
-		const char *txt;
-	} *bp, optab [] = {
-		[OCALL] = {1, "()"},
-		[OARY] = {2, "[]"},
-		[OFIELD] = {2, "."},
-		[OPTR] = {2, "->"},
-		[OPOSTINC] = {1, ".++"},
-		[OPOSTDEC] = {1, ".--"},
-		[OPREINC] = {1, "++."},
-		[OPREDEC] = {1, "--."},
-		[OADDR] = {1, "&."},
-		[OINDIR] = {1, "[*]"},
-		[OMINUS] = {1, "-."},
-		[OPLUS] = {1, "+."},
-		[OCPL] = {1, "~"},
-		[ONEG] = {1, "!"},
-		[OMUL] = {2, "*"},
-		[ODIV] = {2, "/"},
-		[OMOD] = {2, "%"},
-		[OADD] = {2, "+"},
-		[OSUB] = {2, "-"},
-		[OSHL] = {2, "<<"},
-		[OSHR] = {2, ">>"},
-		[OLT] = {2, "<"},
-		[OGT] = {2, ">"},
-		[OGE] = {2, ">="},
-		[OLE] = {2, "<="},
-		[OEQ] = {2, "=="},
-		[ONE] = {2, "!="},
-		[OBAND] = {2, "&"},
-		[OBXOR] = {2, "^"},
-		[OBOR] = {2, "|"},
-		[OAND] = {2, "&&"},
-		[OOR] = {2, "||"},
-		[OTERN] = {3, "?"},
-		[OASSIGN] = {2, "="},
-		[OA_MUL] = {2, "*="},
-		[OA_DIV] = {2, "/="},
-		[OA_MOD] = {2, "%="},
-		[OA_ADD] = {2, "+="},
-		[OA_SUB] = {2, "-="},
-		[OA_SHL] = {2, "<<="},
-		[OA_SHR] = {2, ">>="},
-		[OA_AND] = {2, "&="},
-		[OA_XOR] = {2, "^="},
-		[OA_OR] = {2, "|="},
-		[OSYM] = {0, "sym"},
-		[OCOMP] = {255, "comp"},
-		[OSWITCH] = {2, "switch"},
-		[OIF] = {3, "if"},
-		[OFOR] = {2, "for"},
-		[OFEXP] = {3, "efor"},
-		[ODO] = {2, "do"},
-		[OWHILE] = {2, "while"},
-		[OLABEL] = {2, "label"},
-		[OGOTO] = {1, "goto"},
-		[OBREAK] = {1, "break"},
-		[OCONT] = {1, "cont"},
-		[ORETURN] = {1, "return"},
-		[OCASE] = {1, "case"},
-		[ODEFAULT] = {1, "default"},
-		[OFTN] = {1, "function"},
-		[ODEF] = {2, "def"}
+	static unsigned char indent;
+	register unsigned char i;
+	static char *optab[] = {
+		[OCALL] = "()",
+		[OARY] = "[]",
+		[OFIELD] = ".",
+		[OPTR] = "->",
+		[OPOSTINC] = ".++",
+		[OPOSTDEC] = ".--",
+		[OPREINC] = "++.",
+		[OPREDEC] = "--.",
+		[OADDR] = "&.",
+		[OINDIR] = "[*]",
+		[OMINUS] = "-.",
+		[OPLUS] = "+.",
+		[OCPL] = "~",
+		[ONEG] = "!",
+		[OMUL] = "*",
+		[ODIV] = "/",
+		[OMOD] = "%",
+		[OADD] = "+",
+		[OSUB] = "-",
+		[OSHL] = "<<",
+		[OSHR] = ">>",
+		[OLT] = "<",
+		[OGT] = ">",
+		[OGE] = ">=",
+		[OLE] = "<=",
+		[OEQ] = "==",
+		[ONE] = "!=",
+		[OBAND] = "&",
+		[OBXOR] = "^",
+		[OBOR] = "|",
+		[OAND] = "&&",
+		[OOR] = "||",
+		[OTERN] = "?",
+		[OASSIGN] = "=",
+		[OA_MUL] = "*=",
+		[OA_DIV] = "/=",
+		[OA_MOD] = "%=",
+		[OA_ADD] = "+=",
+		[OA_SUB] = "-=",
+		[OA_SHL] = "<<=",
+		[OA_SHR] = ">>=",
+		[OA_AND] = "&=",
+		[OA_XOR] = "^=",
+		[OA_OR] = "|=",
+		[OSYM] = "sym",
+		[OCOMP] = "comp",
+		[OSWITCH] = "switch",
+		[OIF] = "if",
+		[OFOR] = "for",
+		[OFEXP] = "efor",
+		[ODO] = "do",
+		[OWHILE] = "while",
+		[OLABEL] = "label",
+		[OGOTO] = "goto",
+		[OBREAK] = "break",
+		[OCONT] = "cont",
+		[ORETURN] = "return",
+		[OCASE] = "case",
+		[ODEFAULT] = "default",
+		[OFTN] = "function",
+		[O2EXP] = ":",
+		[ODEF] = "def"
 	};
+
 	if (!np) {
 		fputs(" nil", stdout);
 		return;
 	}
-	assert(np->op < ARRAY_SIZE(optab));
-	bp = &optab[np->op];
-	if (bp->nchild) {
-		register unsigned char i;
-		putchar('\n');
-		for (i = indent; i != 0; --i)
-			putchar(' ');
-		printf("(%s", bp->txt);
-		indent += 2;
-	}
-	switch (bp->nchild) {
-	case 0: {
-		register struct symbol *sym = ((struct node_sym *) np)->sym;
-		putchar(' ');
-		fputs((sym->name) ? sym->name : ".", stdout);
+	if (np->op == OSYM) {
+		const char *s = ((struct nodesym *) np)->sym->name;
+
+		printf(" %s", s ? s : ".");
 		return;
 	}
-	case 1:
-		prtree_helper(((struct node_op1 *) np)->infix);
-		break;
-	case 2:
-		prtree_helper(((struct node_op2 *) np)->left);
-		prtree_helper(((struct node_op2 *) np)->rigth);
-		break;
-	case 3:
-		prtree_helper(((struct node_op3 *) np)->left);
-		prtree_helper(((struct node_op3 *) np)->infix);
-		prtree_helper(((struct node_op3 *) np)->rigth);
-		break;
-	case 255: {
-		register struct node **bp, **lim;
-
-		bp = ((struct node_comp *) np)->body;
-		lim = bp + ((struct node_comp *) np)->nr;
-		while (bp < lim)
-			prtree_helper(*bp++);
-		break;
-	}
-	}
+
+	putchar('\n');
+	for (i = indent; i != 0; --i)
+		putchar(' ');
+
+	indent += 2;
+	assert(np->op < ARRAY_SIZE(optab));
+	printf("(%s", optab[np->op]);
+	prtree(((struct node_op2 *)np)->right);
+	prtree(((struct node_op2 *)np)->left);
 	putchar(')');
 	indent -= 2;
 }
 
-void
-prtree(register struct node *np)
-{
-	indent = 0;
-	prtree_helper(np);
-}