LVM2/libdm/regex parse_rx.c

LVM2/libdm/regex parse_rx.c

[thornber]

CVSROOT:	/cvs/lvm2
Module name:	LVM2
Changes by:	thornber@sourceware.org	2010-08-09 10:29:42

Modified files:
	libdm/regex    : parse_rx.c 

Log message:
	[REGEX] Parse regexes that contain chars with value > 0x80
	
	This is a long standing issue.  Fixed by casting a char value to
	unsigned char before using it as an index into a bitset.

Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.12&r2=1.13

--- LVM2/libdm/regex/parse_rx.c	2010/07/21 11:58:49	1.12
+++ LVM2/libdm/regex/parse_rx.c	2010/08/09 10:29:42	1.13
@@ -271,7 +271,7 @@
 		ps->type = 0;
 		ps->cursor = ptr + 1;
 		dm_bit_clear_all(ps->charset);
-		dm_bit_set(ps->charset, (int) *ptr);
+		dm_bit_set(ps->charset, (int) (unsigned char) *ptr);
 		break;
 	}
 

LVM2/libdm/regex parse_rx.c

[agk]

CVSROOT:	/cvs/lvm2
Module name:	LVM2
Changes by:	agk@sourceware.org	2010-11-02 20:10:35

Modified files:
	libdm/regex    : parse_rx.c 

Log message:
	lost line

Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.14&r2=1.15

--- LVM2/libdm/regex/parse_rx.c	2010/11/02 19:56:33	1.14
+++ LVM2/libdm/regex/parse_rx.c	2010/11/02 20:10:35	1.15
@@ -574,6 +574,7 @@
 		if (!(r->left = _pass(mem, r->left, changed)))
 			return_NULL;
 
+		break;
 	case OR:
 		/* It's important we optimise sub nodes first */
 		if (!(r->left = _pass(mem, r->left, changed)))

LVM2/libdm/regex parse_rx.c

[agk]

CVSROOT:	/cvs/lvm2
Module name:	LVM2
Changes by:	agk@sourceware.org	2010-04-22 20:15:01

Modified files:
	libdm/regex    : parse_rx.c 

Log message:
	avoid ORs rightmost

Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.9&r2=1.10

--- LVM2/libdm/regex/parse_rx.c	2010/04/22 17:42:38	1.9
+++ LVM2/libdm/regex/parse_rx.c	2010/04/22 20:15:00	1.10
@@ -421,16 +421,10 @@
 static unsigned _depth(struct rx_node *r, unsigned leftmost)
 {
 	int count = 1;
-	int or_count = 0;
 
-	while (r->type != CHARSET && LEFT(r)) {
+	while (r->type != CHARSET && LEFT(r) && (leftmost || r->type != OR)) {
 		count++;
 		r = LEFT(r);
-		/* Stop if we pass another OR */
-		if (or_count)
-			break;
-		if (r->type == OR)
-			or_count++;
 	}
 
 	return count;

LVM2/libdm/regex parse_rx.c

[agk]

CVSROOT:	/cvs/lvm2
Module name:	LVM2
Changes by:	agk@sourceware.org	2010-04-22 14:33:16

Modified files:
	libdm/regex    : parse_rx.c 

Log message:
	Don't walk rightmost through NULL pointers.

Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.7&r2=1.8

--- LVM2/libdm/regex/parse_rx.c	2010/04/22 13:42:34	1.7
+++ LVM2/libdm/regex/parse_rx.c	2010/04/22 14:33:14	1.8
@@ -16,8 +16,6 @@
 #include "dmlib.h"
 #include "parse_rx.h"
 
-#include <ctype.h>
-
 struct parse_sp {		/* scratch pad for the parsing process */
 	struct dm_pool *mem;
 	int type;		/* token type, 0 indicates a charset */
@@ -345,7 +343,7 @@
 {
 	int count = 1;
 
-	while (r->type != CHARSET) {
+	while (r->type != CHARSET && LEFT(r)) {
 		count++;
 		r = LEFT(r);
 	}

LVM2/libdm/regex parse_rx.c

[agk]

CVSROOT:	/cvs/lvm2
Module name:	LVM2
Changes by:	agk@sourceware.org	2010-04-22 13:42:34

Modified files:
	libdm/regex    : parse_rx.c 

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

Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.6&r2=1.7

--- LVM2/libdm/regex/parse_rx.c	2010/04/22 13:18:27	1.6
+++ LVM2/libdm/regex/parse_rx.c	2010/04/22 13:42:34	1.7
@@ -333,7 +333,9 @@
 
 /*----------------------------------------------------------------*/
 
-#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 @@
 
 	while (r->type != CHARSET) {
 		count++;
-		r = L_OR_R(r);
+		r = LEFT(r);
 	}
 
 	return count;
@@ -390,46 +392,54 @@
 	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;
+	struct rx_node *old_node;
 
-	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;
+	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 @@
 {
 	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 @@
 		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;

LVM2/libdm/regex parse_rx.c

[agk]

CVSROOT:	/cvs/lvm2
Module name:	LVM2
Changes by:	agk@sourceware.org	2010-04-22 13:18:27

Modified files:
	libdm/regex    : parse_rx.c 

Log message:
	fix leftmost rotation

Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.5&r2=1.6

--- LVM2/libdm/regex/parse_rx.c	2010/04/22 03:24:24	1.5
+++ LVM2/libdm/regex/parse_rx.c	2010/04/22 13:18:27	1.6
@@ -16,6 +16,8 @@
 #include "dmlib.h"
 #include "parse_rx.h"
 
+#include <ctype.h>
+
 struct parse_sp {		/* scratch pad for the parsing process */
 	struct dm_pool *mem;
 	int type;		/* token type, 0 indicates a charset */
@@ -413,24 +415,36 @@
 	return 0;
 }
 
-static struct rx_node *_exchange_nodes(struct dm_pool *mem, struct rx_node *r, struct rx_node *left_cat, struct rx_node *right_cat, unsigned leftmost)
+/* If top node is OR, rotate from ((ab)|((ac)|d)) to (((ab)|(ac))|d) */
+static int _rotate_ors(struct rx_node *r)
+{
+	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;
+	}
+
+	return 0;
+}
+
+static struct rx_node *_exchange_nodes(struct dm_pool *mem, struct rx_node *r,
+				       struct rx_node *left_cat, struct rx_node *right_cat,
+				       unsigned leftmost)
 {
-	struct rx_node *new_r, *new_cat;
+	struct rx_node *new_r;
 
-	/* FIXME Clean up leftmost */
 	if (leftmost) {
-		new_r = r->right;
-		new_cat = _node(mem, CAT, left_cat->left, r);
-		if (!new_cat)
+		new_r = _node(mem, CAT, left_cat->left, r);
+		if (!new_r)
 			return_NULL;
-		new_r->left = new_cat;
 
 		memcpy(left_cat, left_cat->right, sizeof(*left_cat));
-		r->right = right_cat->right;
-
-		/* FIXME Avoid this */
-		if (new_r->right == right_cat->right)
-			new_r = new_r->left;
+		memcpy(right_cat, right_cat->right, sizeof(*right_cat));
 	} else {
 		new_r = _node(mem, CAT, r, right_cat->right);
 		if (!new_r)
@@ -447,6 +461,8 @@
                              struct rx_node *r,
                              int *changed)
 {
+	struct rx_node *left, *right;
+
 	/*
 	 * walk the tree, optimising every 'or' node.
 	 */
@@ -475,18 +491,17 @@
 		if (!(r->right = _pass(mem, r->right, changed)))
 			return_NULL;
 
-		{
-			struct rx_node *left, *right;
-
-			if (_find_leftmost_common(r, &left, &right, 1)) {
+		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))
 				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);
-
-				*changed = 1;
-			}
+			*changed = 1;
+		} else if (_find_leftmost_common(r, &left, &right, 0)) {
+			r = _exchange_nodes(mem, r, left, right, 0);
+			*changed = 1;
 		}
 		break;
 

LVM2/libdm/regex parse_rx.c

[agk]

CVSROOT:	/cvs/lvm2
Module name:	LVM2
Changes by:	agk@sourceware.org	2010-04-22 03:24:25

Modified files:
	libdm/regex    : parse_rx.c 

Log message:
	Still not satisfactory...

Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.4&r2=1.5

--- LVM2/libdm/regex/parse_rx.c	2010/04/20 22:31:22	1.4
+++ LVM2/libdm/regex/parse_rx.c	2010/04/22 03:24:24	1.5
@@ -331,17 +331,19 @@
 
 /*----------------------------------------------------------------*/
 
+#define L_OR_R(a) (leftmost ? (a)->left : (a)->right)
+
 /*
  * The optimiser spots common prefixes on either side of an 'or' node, and
  * lifts them outside the 'or' with a 'cat'.
  */
-static unsigned _leftmost_depth(struct rx_node *r)
+static unsigned _depth(struct rx_node *r, unsigned leftmost)
 {
 	int count = 1;
 
 	while (r->type != CHARSET) {
 		count++;
-		r = r->left;
+		r = L_OR_R(r);
 	}
 
 	return count;
@@ -378,38 +380,69 @@
 
 static int _find_leftmost_common(struct rx_node *or,
                                  struct rx_node **l,
-                                 struct rx_node **r)
+                                 struct rx_node **r,
+				 unsigned leftmost)
 {
 	struct rx_node *left = or->left, *right = or->right;
-	unsigned left_depth = _leftmost_depth(left);
-	unsigned right_depth = _leftmost_depth(right);
+	unsigned left_depth = _depth(left, leftmost);
+	unsigned right_depth = _depth(right, leftmost);
 
 	while (left_depth > right_depth) {
-		left = left->left;
+		left = L_OR_R(left);
 		left_depth--;
 	}
 
 	while (right_depth > left_depth) {
-		right = right->left;
+		right = L_OR_R(right);
 		right_depth--;
 	}
 
 	while (left_depth) {
 		if (left->type == CAT && right->type == CAT) {
-			if (_nodes_equal(left->left, right->left)) {
+			if (_nodes_equal(L_OR_R(left), L_OR_R(right))) {
 				*l = left;
 				*r = right;
 				return 1;
 			}
 		}
-		left = left->left;
-		right = right->left;
+		left = L_OR_R(left);
+		right = L_OR_R(right);
 		left_depth--;
 	}
 
 	return 0;
 }
 
+static struct rx_node *_exchange_nodes(struct dm_pool *mem, struct rx_node *r, struct rx_node *left_cat, struct rx_node *right_cat, unsigned leftmost)
+{
+	struct rx_node *new_r, *new_cat;
+
+	/* FIXME Clean up leftmost */
+	if (leftmost) {
+		new_r = r->right;
+		new_cat = _node(mem, CAT, left_cat->left, r);
+		if (!new_cat)
+			return_NULL;
+		new_r->left = new_cat;
+
+		memcpy(left_cat, left_cat->right, sizeof(*left_cat));
+		r->right = right_cat->right;
+
+		/* FIXME Avoid this */
+		if (new_r->right == right_cat->right)
+			new_r = new_r->left;
+	} else {
+		new_r = _node(mem, CAT, r, right_cat->right);
+		if (!new_r)
+			return_NULL;
+
+		memcpy(left_cat, left_cat->left, sizeof(*left_cat));
+		memcpy(right_cat, right_cat->left, sizeof(*right_cat));
+	}
+
+	return new_r;
+}
+
 static struct rx_node *_pass(struct dm_pool *mem,
                              struct rx_node *r,
                              int *changed)
@@ -445,16 +478,12 @@
 		{
 			struct rx_node *left, *right;
 
-			if (_find_leftmost_common(r, &left, &right)) {
-				struct rx_node *new_r = _node(mem, CAT, left->left, r);
+			if (_find_leftmost_common(r, &left, &right, 1)) {
+				r = _exchange_nodes(mem, r, left, right, 1);
 
-				if (!new_r)
-					return_NULL;
-
-				memcpy(left, left->right, sizeof(*left));
-				memcpy(right, right->right, sizeof(*right));
-
-				r = new_r;
+				*changed = 1;
+			} else if (_find_leftmost_common(r, &left, &right, 0)) {
+				r = _exchange_nodes(mem, r, left, right, 0);
 
 				*changed = 1;
 			}
@@ -473,6 +502,8 @@
 	/*
 	 * We're looking for (or (... (cat <foo> a)) (... (cat <foo> b)))
 	 * and want to turn it into (cat <foo> (or (... a) (... b)))
+	 *
+	 * (fa)|(fb) becomes f(a|b)
 	 */
 
 	/*

LVM2/libdm/regex parse_rx.c

[agk]

CVSROOT:	/cvs/lvm2
Module name:	LVM2
Changes by:	agk@sourceware.org	2010-04-20 22:31:22

Modified files:
	libdm/regex    : parse_rx.c 

Log message:
	Add a regex optimisation pass for shared character prefixes.

Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/parse_rx.c.diff?cvsroot=lvm2&r1=1.3&r2=1.4

--- LVM2/libdm/regex/parse_rx.c	2008/11/03 18:59:59	1.3
+++ LVM2/libdm/regex/parse_rx.c	2010/04/20 22:31:22	1.4
@@ -329,19 +329,182 @@
 	return n;
 }
 
+/*----------------------------------------------------------------*/
+
+/*
+ * The optimiser spots common prefixes on either side of an 'or' node, and
+ * lifts them outside the 'or' with a 'cat'.
+ */
+static unsigned _leftmost_depth(struct rx_node *r)
+{
+	int count = 1;
+
+	while (r->type != CHARSET) {
+		count++;
+		r = r->left;
+	}
+
+	return count;
+}
+
+/*
+ * FIXME: a unique key could be built up as part of the parse, to make the
+ * comparison quick.  Alternatively we could use cons-hashing, and then
+ * this would simply be a pointer comparison.
+ */
+static int _nodes_equal(struct rx_node *l, struct rx_node *r)
+{
+	if (l->type != r->type)
+		return 0;
+
+	switch (l->type) {
+	case CAT:
+	case OR:
+		return _nodes_equal(l->left, r->left) &&
+			_nodes_equal(l->right, r->right);
+
+	case STAR:
+	case PLUS:
+	case QUEST:
+		return _nodes_equal(l->left, r->left);
+
+	case CHARSET:
+		return dm_bitset_equal(l->charset, r->charset);
+	}
+
+	/* NOTREACHED */
+	return_0;
+}
+
+static int _find_leftmost_common(struct rx_node *or,
+                                 struct rx_node **l,
+                                 struct rx_node **r)
+{
+	struct rx_node *left = or->left, *right = or->right;
+	unsigned left_depth = _leftmost_depth(left);
+	unsigned right_depth = _leftmost_depth(right);
+
+	while (left_depth > right_depth) {
+		left = left->left;
+		left_depth--;
+	}
+
+	while (right_depth > left_depth) {
+		right = right->left;
+		right_depth--;
+	}
+
+	while (left_depth) {
+		if (left->type == CAT && right->type == CAT) {
+			if (_nodes_equal(left->left, right->left)) {
+				*l = left;
+				*r = right;
+				return 1;
+			}
+		}
+		left = left->left;
+		right = right->left;
+		left_depth--;
+	}
+
+	return 0;
+}
+
+static struct rx_node *_pass(struct dm_pool *mem,
+                             struct rx_node *r,
+                             int *changed)
+{
+	/*
+	 * walk the tree, optimising every 'or' node.
+	 */
+	switch (r->type) {
+	case CAT:
+		if (!(r->left = _pass(mem, r->left, changed)))
+			return_NULL;
+
+		if (!(r->right = _pass(mem, r->right, changed)))
+			return_NULL;
+
+		break;
+
+	case STAR:
+	case PLUS:
+	case QUEST:
+		if (!(r->left = _pass(mem, r->left, changed)))
+			return_NULL;
+		break;
+
+	case OR:
+		/* It's important we optimise sub nodes first */
+		if (!(r->left = _pass(mem, r->left, changed)))
+			return_NULL;
+
+		if (!(r->right = _pass(mem, r->right, changed)))
+			return_NULL;
+
+		{
+			struct rx_node *left, *right;
+
+			if (_find_leftmost_common(r, &left, &right)) {
+				struct rx_node *new_r = _node(mem, CAT, left->left, r);
+
+				if (!new_r)
+					return_NULL;
+
+				memcpy(left, left->right, sizeof(*left));
+				memcpy(right, right->right, sizeof(*right));
+
+				r = new_r;
+
+				*changed = 1;
+			}
+		}
+		break;
+
+	case CHARSET:
+		break;
+	}
+
+	return r;
+}
+
+static struct rx_node *_optimise(struct dm_pool *mem, struct rx_node *r)
+{
+	/*
+	 * We're looking for (or (... (cat <foo> a)) (... (cat <foo> b)))
+	 * and want to turn it into (cat <foo> (or (... a) (... b)))
+	 */
+
+	/*
+	 * Initially done as an inefficient multipass algorithm.
+	 */
+	int changed;
+
+	do {
+		changed = 0;
+		r = _pass(mem, r, &changed);
+	} while (r && changed);
+
+	return r;
+}
+
+/*----------------------------------------------------------------*/
+
 struct rx_node *rx_parse_tok(struct dm_pool *mem,
 			     const char *begin, const char *end)
 {
 	struct rx_node *r;
 	struct parse_sp *ps = dm_pool_zalloc(mem, sizeof(*ps));
 
-	if (!ps) {
-		stack;
-		return NULL;
-	}
+	if (!ps)
+		return_NULL;
 
 	ps->mem = mem;
-	ps->charset = dm_bitset_create(mem, 256);
+	if (!(ps->charset = dm_bitset_create(mem, 256))) {
+		log_error("Regex charset allocation failed");
+		dm_pool_free(mem, ps);
+		return NULL;
+	}
 	ps->cursor = begin;
 	ps->rx_end = end;
 	_rx_get_token(ps);		/* load the first token */
@@ -349,6 +512,13 @@
 	if (!(r = _or_term(ps))) {
 		log_error("Parse error in regex");
 		dm_pool_free(mem, ps);
+		return NULL;
+	}
+
+	if (!(r = _optimise(mem, r))) {
+		log_error("Regex optimisation error");
+		dm_pool_free(mem, ps);
+		return NULL;
 	}
 
 	return r;