sh: Use iteration instead of recursion to evaluate semicolon lists.

This reduces CPU and memory usage when executing long lists (such
as long functions).

2 files changed, 27 insertions, 15 deletions

diff --git a/bin/sh/eval.c b/bin/sh/eval.c
index ed6d717..cfb9e06 100644
--- a/bin/sh/eval.c
+++ b/bin/sh/eval.c
@@ -196,6 +196,7 @@ void
 evaltree(union node *n, int flags)
 {
 	int do_etest;
+	union node *next;
 
 	do_etest = 0;
 	if (n == NULL) {
@@ -203,6 +204,8 @@ evaltree(union node *n, int flags)
 		exitstatus = 0;
 		goto out;
 	}
+	do {
+	next = NULL;
 #ifndef NO_HISTORY
 	displayhist = 1;	/* show history substitutions done with fc */
 #endif
@@ -212,20 +215,20 @@ evaltree(union node *n, int flags)
 		evaltree(n->nbinary.ch1, flags & ~EV_EXIT);
 		if (evalskip)
 			goto out;
-		evaltree(n->nbinary.ch2, flags);
+		next = n->nbinary.ch2;
 		break;
 	case NAND:
 		evaltree(n->nbinary.ch1, EV_TESTED);
 		if (evalskip || exitstatus != 0) {
 			goto out;
 		}
-		evaltree(n->nbinary.ch2, flags);
+		next = n->nbinary.ch2;
 		break;
 	case NOR:
 		evaltree(n->nbinary.ch1, EV_TESTED);
 		if (evalskip || exitstatus == 0)
 			goto out;
-		evaltree(n->nbinary.ch2, flags);
+		next = n->nbinary.ch2;
 		break;
 	case NREDIR:
 		evalredir(n, flags);
@@ -242,9 +245,9 @@ evaltree(union node *n, int flags)
 		if (evalskip)
 			goto out;
 		if (exitstatus == 0)
-			evaltree(n->nif.ifpart, flags);
+			next = n->nif.ifpart;
 		else if (n->nif.elsepart)
-			evaltree(n->nif.elsepart, flags);
+			next = n->nif.elsepart;
 		else
 			exitstatus = 0;
 		break;
@@ -281,6 +284,8 @@ evaltree(union node *n, int flags)
 		flushout(&output);
 		break;
 	}
+	n = next;
+	} while (n != NULL);
 out:
 	if (pendingsigs)
 		dotrap();
diff --git a/bin/sh/parser.c b/bin/sh/parser.c
index 329e2e3..23db5e7 100644
--- a/bin/sh/parser.c
+++ b/bin/sh/parser.c
@@ -227,13 +227,13 @@ parsecmd(int interact)
 static union node *
 list(int nlflag, int erflag)
 {
-	union node *n1, *n2, *n3;
+	union node *ntop, *n1, *n2, *n3;
 	int tok;
 
 	checkkwd = 2;
 	if (!nlflag && !erflag && tokendlist[peektoken()])
 		return NULL;
-	n1 = NULL;
+	ntop = n1 = NULL;
 	for (;;) {
 		n2 = andor();
 		tok = readtoken();
@@ -250,14 +250,21 @@ list(int nlflag, int erflag)
 				n2 = n3;
 			}
 		}
-		if (n1 == NULL) {
-			n1 = n2;
+		if (ntop == NULL)
+			ntop = n2;
+		else if (n1 == NULL) {
+			n1 = (union node *)stalloc(sizeof (struct nbinary));
+			n1->type = NSEMI;
+			n1->nbinary.ch1 = ntop;
+			n1->nbinary.ch2 = n2;
+			ntop = n1;
 		}
 		else {
 			n3 = (union node *)stalloc(sizeof (struct nbinary));
 			n3->type = NSEMI;
-			n3->nbinary.ch1 = n1;
+			n3->nbinary.ch1 = n1->nbinary.ch2;
 			n3->nbinary.ch2 = n2;
+			n1->nbinary.ch2 = n3;
 			n1 = n3;
 		}
 		switch (tok) {
@@ -269,28 +276,28 @@ list(int nlflag, int erflag)
 			if (tok == TNL) {
 				parseheredoc();
 				if (nlflag)
-					return n1;
+					return ntop;
 			} else if (tok == TEOF && nlflag) {
 				parseheredoc();
-				return n1;
+				return ntop;
 			} else {
 				tokpushback++;
 			}
 			checkkwd = 2;
 			if (!nlflag && !erflag && tokendlist[peektoken()])
-				return n1;
+				return ntop;
 			break;
 		case TEOF:
 			if (heredoclist)
 				parseheredoc();
 			else
 				pungetc();		/* push back EOF on input */
-			return n1;
+			return ntop;
 		default:
 			if (nlflag || erflag)
 				synexpect(-1);
 			tokpushback++;
-			return n1;
+			return ntop;
 		}
 	}
 }