Fix rightmost rotation, and use LEFT and RIGHT to make symmetry more obvious.

1 files changed, 46 insertions, 38 deletions

diff --git a/libdm/regex/parse_rx.c b/libdm/regex/parse_rx.c
index 66e16a35a..d642cee22 100644
--- a/libdm/regex/parse_rx.c
+++ b/libdm/regex/parse_rx.c
@@ -333,7 +333,9 @@ static struct rx_node *_or_term(struct parse_sp *ps)
 
 /*----------------------------------------------------------------*/
 
-#define L_OR_R(a) (leftmost ? (a)->left : (a)->right)
+/* Macros for left and right nodes.  Inverted if 'leftmost' is set. */
+#define LEFT(a) (leftmost ? (a)->left : (a)->right)
+#define RIGHT(a) (leftmost ? (a)->right : (a)->left)
 
 /*
  * The optimiser spots common prefixes on either side of an 'or' node, and
@@ -345,7 +347,7 @@ static unsigned _depth(struct rx_node *r, unsigned leftmost)
 
 	while (r->type != CHARSET) {
 		count++;
-		r = L_OR_R(r);
+		r = LEFT(r);
 	}
 
 	return count;
@@ -390,46 +392,54 @@ static int _find_leftmost_common(struct rx_node *or,
 	unsigned right_depth = _depth(right, leftmost);
 
 	while (left_depth > right_depth) {
-		left = L_OR_R(left);
+		left = LEFT(left);
 		left_depth--;
 	}
 
 	while (right_depth > left_depth) {
-		right = L_OR_R(right);
+		right = LEFT(right);
 		right_depth--;
 	}
 
 	while (left_depth) {
 		if (left->type == CAT && right->type == CAT) {
-			if (_nodes_equal(L_OR_R(left), L_OR_R(right))) {
+			if (_nodes_equal(LEFT(left), LEFT(right))) {
 				*l = left;
 				*r = right;
 				return 1;
 			}
 		}
-		left = L_OR_R(left);
-		right = L_OR_R(right);
+		left = LEFT(left);
+		right = LEFT(right);
 		left_depth--;
 	}
 
 	return 0;
 }
 
-/* If top node is OR, rotate from ((ab)|((ac)|d)) to (((ab)|(ac))|d) */
-static int _rotate_ors(struct rx_node *r)
+/* If top node is OR, rotate (leftmost example) from ((ab)|((ac)|d)) to (((ab)|(ac))|d) */
+static int _rotate_ors(struct rx_node *r, unsigned leftmost)
 {
-	struct rx_node *old_r_right;
-
-	if (r->type == OR && r->right->type == OR) {
-		old_r_right = r->right;
-		r->right = old_r_right->right;
-		old_r_right->right = old_r_right->left;
-		old_r_right->left = r->left;
-		r->left = old_r_right;
-		return 1;
+	struct rx_node *old_node;
+
+	if (r->type != OR || RIGHT(r)->type != OR)
+		return 0;
+
+	old_node = RIGHT(r);
+
+	if (leftmost) {
+		r->right = RIGHT(old_node);
+		old_node->right = LEFT(old_node);
+		old_node->left = LEFT(r);
+		r->left = old_node;
+	} else {
+		r->left = RIGHT(old_node);
+		old_node->left = LEFT(old_node);
+		old_node->right = LEFT(r);
+		r->right = old_node;
 	}
 
-	return 0;
+	return 1;
 }
 
 static struct rx_node *_exchange_nodes(struct dm_pool *mem, struct rx_node *r,
@@ -438,21 +448,16 @@ static struct rx_node *_exchange_nodes(struct dm_pool *mem, struct rx_node *r,
 {
 	struct rx_node *new_r;
 
-	if (leftmost) {
-		new_r = _node(mem, CAT, left_cat->left, r);
-		if (!new_r)
-			return_NULL;
+	if (leftmost)
+		new_r = _node(mem, CAT, LEFT(left_cat), r);
+	else
+		new_r = _node(mem, CAT, r, LEFT(right_cat));
 
-		memcpy(left_cat, left_cat->right, sizeof(*left_cat));
-		memcpy(right_cat, right_cat->right, sizeof(*right_cat));
-	} else {
-		new_r = _node(mem, CAT, r, right_cat->right);
-		if (!new_r)
-			return_NULL;
+	if (!new_r)
+		return_NULL;
 
-		memcpy(left_cat, left_cat->left, sizeof(*left_cat));
-		memcpy(right_cat, right_cat->left, sizeof(*right_cat));
-	}
+	memcpy(left_cat, RIGHT(left_cat), sizeof(*left_cat));
+	memcpy(right_cat, RIGHT(right_cat), sizeof(*right_cat));
 
 	return new_r;
 }
@@ -491,16 +496,19 @@ static struct rx_node *_pass(struct dm_pool *mem,
 		if (!(r->right = _pass(mem, r->right, changed)))
 			return_NULL;
 
+		/*
+		 * If rotate_ors changes the tree, left and right are stale,
+		 * so just set 'changed' to repeat the search.
+		 *
+		 * FIXME Check we can't 'bounce' between left and right rotations here.
+		 */
 		if (_find_leftmost_common(r, &left, &right, 1)) {
-			/*
-			 * If rotate_ors changes the tree, left and right are stale,
-			 * so just set 'changed' to repeat the search.
-			 */
-			if (!_rotate_ors(r))
+			if (!_rotate_ors(r, 1))
 				r = _exchange_nodes(mem, r, left, right, 1);
 			*changed = 1;
 		} else if (_find_leftmost_common(r, &left, &right, 0)) {
-			r = _exchange_nodes(mem, r, left, right, 0);
+			if (!_rotate_ors(r, 0))
+				r = _exchange_nodes(mem, r, left, right, 0);
 			*changed = 1;
 		}
 		break;