From ca2051a26b74e1140cf2ca3ea0c82c1eed5bce28 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Jos=C3=A9=20Bollo?= <jose.bollo@iot.bzh>
Date: Thu, 6 Apr 2017 09:20:56 +0200
Subject: [PATCH] Reduce explicitely recursion
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

When evaluating permissions, the recursive
algorithm is replaced with an algorithm
that eliminates the tail recursion.

Change-Id: I3298c42fa658498a954f4bf7dedfad87f00ab736
Signed-off-by: José Bollo <jose.bollo@iot.bzh>
---
 src/afb-perm.c                  | 36 ++++++++++++++++--------------------
 src/tests/test-perm/test-perm.c | 13 ++++++++-----
 2 files changed, 24 insertions(+), 25 deletions(-)

diff --git a/src/afb-perm.c b/src/afb-perm.c
index b4d2b5e3..ca83c7a3 100644
--- a/src/afb-perm.c
+++ b/src/afb-perm.c
@@ -136,27 +136,23 @@ static void node_free(struct node *node)
  */
 static int node_check(struct node *node, int (*check)(void *closure, const char *name), void *closure)
 {
-	int rc;
-
-	switch (node->type) {
-	case Text:
-		rc = check(closure, node->text);
-		break;
-	case And:
-		rc = node_check(node->children[0], check, closure);
-		if (rc)
-			rc = node_check(node->children[1], check, closure);
-		break;
-	case Or:
-		rc = node_check(node->children[0], check, closure);
-		if (!rc)
-			rc = node_check(node->children[1], check, closure);
-		break;
-	case Not:
-		rc = !node_check(node->children[0], check, closure);
-		break;
+	for(;;) {
+		switch (node->type) {
+		case Text:
+			return check(closure, node->text);
+		case And:
+			if (!node_check(node->children[0], check, closure))
+				return 0;
+			break;
+		case Or:
+			if (node_check(node->children[0], check, closure))
+				return 1;
+			break;
+		case Not:
+			return !node_check(node->children[0], check, closure);
+		}
+		node = node->children[1];
 	}
-	return rc;
 }
 
 /*********************************************************************
diff --git a/src/tests/test-perm/test-perm.c b/src/tests/test-perm/test-perm.c
index 8d63e3c7..c9b60473 100644
--- a/src/tests/test-perm/test-perm.c
+++ b/src/tests/test-perm/test-perm.c
@@ -108,12 +108,13 @@ void mke(int value, int bits, char *buffer)
 		case 3: add(buffer, "(%c or not %c) ", c, c); break;
 		}
 	} else if (val0 != val1) {
+		if (val0 && val1)
+			add(buffer, "(");
 		if (val0) {
 			add(buffer, "not %c", c);
 			if (val0 != smask) {
-				add(buffer, " and (");
+				add(buffer, " and ");
 				mke(val0, bits - 1, buffer);
-				add(buffer, ")");
 			}
 		}
 		if (val0 && val1)
@@ -121,11 +122,12 @@ void mke(int value, int bits, char *buffer)
 		if (val1) {
 			add(buffer, "%c", c);
 			if (val1 != smask) {
-				add(buffer, " and (");
+				add(buffer, " and ");
 				mke(val1, bits - 1, buffer);
-				add(buffer, ")");
 			}
 		}
+		if (val0 && val1)
+			add(buffer, ")");
 	} else {
 		mke(val0, bits - 1, buffer);
 	}
@@ -150,10 +152,11 @@ int fulltest()
 	for (i = 0 ; i < 65536 ; i++) {
 		makeexpr(i, buffer);
 		j = test(buffer);
-		printf("[[[ %d %s %d ]]]\n", i, i==j?"==":"!=", j);
+		printf("[[[ %d %s %d ]]] %d %s\n", i, i==j?"==":"!=", j, (int)strlen(buffer), buffer);
 		if (i != j)
 			r = 1;
 	}
+	return r;
 }
 
 int main()
-- 
2.16.6