Rewrite the paragraph logic to use a tree structure.

Signed-off-by: Antti-Juhani Kaijanaho <ajk@debian.org>

5 files changed, 193 insertions, 171 deletions

diff --git a/debian/changelog b/debian/changelog
index d566927..b8dbfd8 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -19,8 +19,9 @@ dctrl-tools (2.19) UNRELEASED; urgency=low
     Closes: #209134 (keyword case shouldn't be influenced by -s)
     Reported by Dan Jacobson <jidanni@jidanni.org>.
   * grep-dctrl/grep-dctrl.c: Clean up some dead code.
+  * grep-dctrl: Rewrite predicate code to use a tree instead of a bytecode.
 
- -- Antti-Juhani Kaijanaho <ajk@debian.org>  Wed, 19 Oct 2011 21:09:47 +0300
+ -- Antti-Juhani Kaijanaho <ajk@debian.org>  Thu, 20 Oct 2011 00:24:39 +0300
 
 dctrl-tools (2.18ubuntu1) oneiric; urgency=low
 
diff --git a/grep-dctrl/grep-dctrl.c b/grep-dctrl/grep-dctrl.c
index 26a1d79..545d1df 100644
--- a/grep-dctrl/grep-dctrl.c
+++ b/grep-dctrl/grep-dctrl.c
@@ -180,7 +180,7 @@ struct arguments {
 	/**/
 	size_t num_show_fields;
 	/* A machine-readable representation of the predicate.  */
-	struct predicate p;
+	struct predicate * p;
 	/* Configuration file name */
 	char const * rcname;
 	/* Ignore parse errors? */
@@ -203,8 +203,6 @@ struct arguments {
 	size_t toks_np;
         /* Token read position. */
 	size_t toks_pos;
-	/* Pattern error? */
-	bool pattern_error;
 	/* Token stream for the predicate parser. */
 	int toks[MAX_TOKS];
         /* The string value, if any, of each token*/
@@ -327,7 +325,7 @@ static error_t parse_opt (int key, char * arg, struct argp_state * state)
 		break;
 	case 'o':
 		debug_message("parse_opt: o", 0);
-		APPTOK(I_OR);
+		APPTOK(TOK_OR);
 		break;
         case 'S':
                 debug_message("parse_opt: S", 0);
@@ -447,30 +445,9 @@ static error_t parse_opt (int key, char * arg, struct argp_state * state)
 
 static void dump_args(struct arguments * args)
 {
-	size_t i;
-	printf("num_atoms = %zi\n", args->p.num_atoms);
-	for (i = 0; i < args->p.num_atoms; i++) {
-		printf("atoms[%zi].field_name = %s\n", i, args->p.atoms[i].field_name);
-		printf("atoms[%zi].mode = %i\n", i, args->p.atoms[i].mode);
-		printf("atoms[%zi].ignore_case = %i\n", i, args->p.atoms[i].ignore_case);
-		printf("atoms[%zi].whole_pkg = %i\n", i, args->p.atoms[i].whole_pkg);
-		printf("atoms[%zi].pat = %s\n", i, args->p.atoms[i].pat);
-	}
-	printf("proglen = %zi\n", args->p.proglen);
-	for (i = 0; i < args->p.proglen; i++) {
-		int op = args->p.program[i];
-		printf("program[%zi] = ", i);
-		switch (op) {
-		case I_NOP:  puts("NOP"); break;
-		case I_NEG:  puts("NEG"); break;
-		case I_AND:  puts("AND"); break;
-		case I_OR:   puts("OR"); break;
-		default:
-			printf("PUSH(%i)\n", op - I_PUSH(0));
-		}
-	}
+        predicate_print(args->p);
 	printf("num_fnames = %zi\n", args->num_fnames);
-	for (i = 0; i < args->num_fnames; i++) {
+	for (size_t i = 0; i < args->num_fnames; i++) {
 		printf("fname[%zi].mode = %s, fname[%zi].s = %s\n",
 		       i, ifile_modes[args->fname[i].mode],
 		       i, args->fname[i].s);
@@ -567,18 +544,18 @@ static void unexpected(int tok)
 	}
 }
 
-static void parse_conj(struct arguments * args);
+static struct predicate * parse_conj(struct arguments * args);
 
-static void parse_prim(struct arguments * args)
+static struct predicate * parse_prim(struct arguments * args)
 {
 	if (peek_token(args) == TOK_LP) {
 		get_token(args);
-		parse_conj(args);
+		struct predicate * rv = parse_conj(args);
 		if (get_token(args) != TOK_RP) {
 			message(L_FATAL, 0, _("missing ')' in command line"));
 			fail();
 		}
-		return;
+		return rv;
 	}
 
         char *pattern = 0;
@@ -670,21 +647,19 @@ static void parse_prim(struct arguments * args)
          }
 
          if (pattern == 0) {
-                 args->pattern_error = true;
-                 return;
+                 message(L_FATAL, 0, _("A pattern is mandatory"));
+                 fail();
          }
 
          if (num_fields == 0) {
                  num_fields = 1;
                  fields[0] = 0;
          }
-         if (args->p.num_atoms + num_fields > MAX_ATOMS) {
-                 message(L_FATAL, 0, _("predicate is too complex"));
-                 fail();
-         }
+         
+         struct predicate *rv = 0;
          for (size_t i = 0; i < num_fields; i++) {
-                 size_t ati = args->p.num_atoms++;
-                 struct atom * atom = &args->p.atoms[ati];
+                 struct atom * atom = malloc(sizeof *atom);
+                 if (atom == 0) enomem(0);
                  atom->field_name = fields[i];
                  atom->field_inx = -1;
                  atom->mode = mm;
@@ -693,51 +668,55 @@ static void parse_prim(struct arguments * args)
                  atom->pat = pattern;
                  atom->patlen = strlen(pattern);
                  atom_finish(atom);
-                 addinsn(&args->p, I_PUSH(ati));
-                 if (i > 0) addinsn(&args->p, I_OR);
+                 struct predicate *tmp = predicate_ATOM(atom);
+                 rv = rv != 0 ? predicate_OR(rv, tmp) : tmp;
          }
 
-        return;
+        return rv;
 failmode:
         message(L_FATAL, 0, _("inconsistent atom modifiers")); 
-        fail(); 
+        fail();
+        return 0;
 }
 
-static void parse_neg(struct arguments * args)
+static struct predicate * parse_neg(struct arguments * args)
 {
 	bool neg = false;
 	if (peek_token(args) == TOK_NOT) {
 		neg = true;
 		get_token(args);
 	}
-	parse_prim(args);
-	if (neg) addinsn(&args->p, I_NEG);
+	struct predicate * rv = parse_prim(args);
+	if (neg) rv = predicate_NOT(rv);
+        return rv;
 }
 
-static void parse_disj(struct arguments * args)
+static struct predicate * parse_disj(struct arguments * args)
 {
-	parse_neg(args);
+	struct predicate * rv = parse_neg(args);
 	while (peek_token(args) == TOK_OR) {
 		get_token(args);
-		parse_neg(args);
-		addinsn(&args->p, I_OR);
+		struct predicate * tmp = parse_neg(args);
+                rv = predicate_OR(rv, tmp);
 	}
+        return rv;
 }
 
-static void parse_conj(struct arguments * args)
+static struct predicate * parse_conj(struct arguments * args)
 {
-	parse_disj(args);
+	struct predicate * rv = parse_disj(args);
 	while (peek_token(args) == TOK_AND) {
 		get_token(args);
-		parse_disj(args);
-		addinsn(&args->p, I_AND);
+		struct predicate * tmp = parse_disj(args);
+                rv = predicate_AND(rv, tmp);
 	}
+        return rv;
 }
 
 static void parse_predicate(struct arguments * args)
 {
 	args->toks_pos = 0;
-	parse_conj(args);
+	args->p = parse_conj(args);
         while (peek_token(args) == TOK_STR) {
                 if (args->num_fnames >= MAX_FNAMES) {
                         message(L_FATAL, 0, _("too many file names"));
@@ -806,26 +785,16 @@ int main (int argc, char * argv[])
 	static struct arguments args;
 	args.show_field_name = true;
 	msg_set_progname(argv[0]);
-	init_predicate(&args.p);
 	description_attr = fieldtrie_insert(description);
 	argp_parse (&argp, argc, argv, ARGP_IN_ORDER, 0, &args);
 #ifdef BANNER
 	banner(true);
 #endif
 	parse_predicate(&args);
-	if (args.pattern_error) {
-		message(L_FATAL, 0, _("A pattern is mandatory"));
-		fail();
-	}
 
 	if (debug_optparse) { dump_args(&args); return 0; }
 
-	if (args.p.num_atoms == 0) {
-		message(L_FATAL, 0, _("a predicate is required"));
-		fail();
-	}
-
-	if (!check_predicate(&args.p)) {
+	if (!check_predicate(args.p)) {
 		message(L_FATAL, 0, _("malformed predicate"));
 		fail();
 	}
@@ -890,9 +859,9 @@ int main (int argc, char * argv[])
 			para_parse_next(&para);
 			if (para_eof(&pp)) break;
 			if ((args.invert_match 
-			     || !does_para_satisfy(&args.p, &para))
+			     || !does_para_satisfy(args.p, &para))
 			    && (!args.invert_match 
-				|| does_para_satisfy(&args.p, &para))) {
+				|| does_para_satisfy(args.p, &para))) {
 				continue;
 			}
 			if (args.quiet) {
diff --git a/lib/msg.h b/lib/msg.h
index e61b3a4..cfabc7f 100644
--- a/lib/msg.h
+++ b/lib/msg.h
@@ -1,5 +1,5 @@
 /*  dctrl-tools - Debian control file inspection tools
-    Copyright © 1999, 2008 Antti-Juhani Kaijanaho
+    Copyright © 1999, 2008, 2011 Antti-Juhani Kaijanaho
 
     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
@@ -27,6 +27,8 @@
 #include <string.h>
 #include "i18n.h"
 
+static void fail(void) __attribute__((noreturn));
+
 static inline
 void fail(void) { exit(2); }
 
diff --git a/lib/predicate.c b/lib/predicate.c
index cf78796..5d10b5d 100644
--- a/lib/predicate.c
+++ b/lib/predicate.c
@@ -28,85 +28,161 @@
 #include "strutil.h"
 #include "version.h"
 
-void init_predicate(struct predicate * p)
+typedef bool (*eval_t)(struct predicate *, para_t * para);
+
+struct predicate_vtbl {
+        bool (*eval)(struct predicate *, para_t *);
+        void (*print)(struct predicate *, size_t indent);
+};
+
+struct predicate {
+        const struct predicate_vtbl *vtbl;
+};
+
+static void print(struct predicate *p, size_t indent)
+{
+        p->vtbl->print(p, indent);
+}
+
+struct unary_predicate {
+        struct predicate super;
+        struct predicate *rand;
+};
+
+struct binary_predicate {
+        struct predicate super;
+        struct predicate *lrand;
+        struct predicate *rrand;
+};
+
+struct atomary_predicate {
+        struct predicate super;
+        struct atom *atom;
+};
+
+static bool eval_AND(struct predicate *base_p, para_t * para)
+{
+        struct binary_predicate *p = (struct binary_predicate *)base_p;
+        if (!does_para_satisfy(p->lrand, para)) return false;
+        return does_para_satisfy(p->rrand, para);
+}
+
+static void print_AND(struct predicate *base_p, size_t indent)
+{
+        struct binary_predicate *p = (struct binary_predicate *)base_p;
+        for (int i = 0; i < indent; i++) putchar(' ');
+        puts("AND");
+        print(p->lrand, indent+1);
+        print(p->rrand, indent+1);
+}
+
+static bool eval_OR(struct predicate *base_p, para_t * para)
+{
+        struct binary_predicate *p = (struct binary_predicate *)base_p;
+        if (does_para_satisfy(p->lrand, para)) return true;
+        return does_para_satisfy(p->rrand, para);
+}
+
+static void print_OR(struct predicate *base_p, size_t indent)
+{
+        struct binary_predicate *p = (struct binary_predicate *)base_p;
+        for (int i = 0; i < indent; i++) putchar(' ');
+        puts("OR");
+        print(p->lrand, indent+1);
+        print(p->rrand, indent+1);
+}
+
+static bool eval_NOT(struct predicate *base_p, para_t * para)
 {
-	p->num_atoms = 0;
-	p->proglen = 0;
-        p->atoms = malloc(MAX_ATOMS * sizeof p->atoms[0]);
-        if (p->atoms == 0) enomem(0);
+        struct unary_predicate *p = (struct unary_predicate *)base_p;
+        return !does_para_satisfy(p->rand, para);
 }
 
-void addinsn(struct predicate * p, int insn)
+static void print_NOT(struct predicate *base_p, size_t indent)
 {
-	if (insn == I_NOP) return;
-	if (p->proglen >= MAX_OPS) {
-		message(L_FATAL, 0, _("predicate is too complex"));
-		fail();
-	}
-	p->program[p->proglen++] = insn;
+        struct unary_predicate *p = (struct unary_predicate *)base_p;
+        for (int i = 0; i < indent; i++) putchar(' ');
+        puts("NOT");
+        print(p->rand, indent+1);
+}
+
+
+static bool eval_ATOM(struct predicate *base_p, para_t * para)
+{
+        struct atomary_predicate *p = (struct atomary_predicate *)base_p;
+        return atom_verify(p->atom, para);
+}
+
+static void print_ATOM(struct predicate *base_p, size_t indent)
+{
+        struct atomary_predicate *p = (struct atomary_predicate *)base_p;
+        char ind[indent+1];
+        for (int i = 0; i < indent; i++) ind[i] = ' ';
+        ind[indent] = '\0';
+        printf("%sATOM", ind);
+        printf("%s field_name = %s\n", ind, p->atom->field_name);
+        printf("%s mode = %i\n", ind, p->atom->mode);
+        printf("%s ignore_case = %i\n", ind, p->atom->ignore_case);
+        printf("%s whole_pkg = %i\n", ind, p->atom->whole_pkg);
+        printf("%s pat = %s\n", ind, p->atom->pat);
+}
+
+struct predicate *binary_predicate(const struct predicate_vtbl *vtbl,
+                                   struct predicate *pl, struct predicate *pr){
+        struct binary_predicate *rv = malloc(sizeof *rv);
+        if (rv == 0) enomem(0);
+        rv->super.vtbl = vtbl;
+        rv->lrand= pl;
+        rv->rrand = pr;
+        return &rv->super;
+}
+struct predicate *predicate_AND(struct predicate *pl, struct predicate *pr)
+{
+        static const struct predicate_vtbl vtbl =
+                { .eval = eval_AND, .print = print_AND };
+        return binary_predicate(&vtbl, pl, pr);
+}
+struct predicate *predicate_OR(struct predicate *pl, struct predicate *pr)
+{
+        static const struct predicate_vtbl vtbl =
+                { .eval = eval_OR, .print = print_OR };
+        return binary_predicate(&vtbl, pl, pr);
+}
+struct predicate *predicate_NOT(struct predicate *p)
+{
+        static const struct predicate_vtbl vtbl =
+                { .eval = eval_NOT, .print = print_NOT };
+        struct unary_predicate *rv = malloc(sizeof *rv);
+        if (rv == 0) enomem(0);
+        rv->super.vtbl = &vtbl;
+        rv->rand = p;
+        return &rv->super;
+}
+struct predicate *predicate_ATOM(struct atom *at)
+{
+        static const struct predicate_vtbl vtbl =
+                { .eval = eval_ATOM, .print = print_ATOM };
+        struct atomary_predicate *rv = malloc(sizeof *rv);
+        if (rv == 0) enomem(0);
+        rv->super.vtbl = &vtbl;
+        rv->atom = at;
+        return &rv->super;
 }
 
 
 bool check_predicate(struct predicate * p)
 {
-	size_t sp = 0;
-	/* Simulate the program. */
-	for (size_t i = 0; i < p->proglen; i++) {
-		switch (p->program[i]) {
-		case I_NOP: break;
-		case I_NEG:
-			if (sp == 0) return false;
-			break;
-		case I_AND: case I_OR:
-			if (sp < 2) return false;
-			--sp;
-			break;
-		default:
-			++sp;
-		}
-	}
-	if (sp != 1) return false;
-	return true;
+        // static checking of predicate
+        // currently no operation
+        return true;
 }
 
 bool does_para_satisfy(struct predicate * p, para_t * para)
 {
-	bool sat_atom[MAX_ATOMS];
-	bool stack[MAX_OPS];
-	size_t sp = 0;
-
-	/* Verify atoms. */
-	for (size_t i = 0; i < p->num_atoms; i++) {
-		sat_atom[i] = atom_verify(&p->atoms[i], para);
-	}
-
-	/* Run the program. */
-	for (size_t i = 0; i < p->proglen; i++) {
-		switch (p->program[i]) {
-		case I_NOP: break;
-		case I_NEG:
-			assert(sp >= 1);
-			stack[sp-1] = !stack[sp-1];
-			break;
-		case I_AND:
-			assert(sp >= 2);
-			stack[sp-2] = stack[sp-2] && stack[sp-1];
-			--sp;
-			break;
-		case I_OR:
-			assert(sp >= 2);
-			stack[sp-2] = stack[sp-2] || stack[sp-1];
-			--sp;
-			break;
-		default:
-		{
-			int atom = p->program[i] - I_PUSH(0);
-			assert(atom <= p->num_atoms);
-			stack[sp] = sat_atom[atom];
-			++sp;
-		}
-		}
-	}
-	assert(sp == 1);
-	return stack[0];
+        return p->vtbl->eval(p, para);
+}
+
+void predicate_print(struct predicate *p)
+{
+        print(p, 0);
 }
diff --git a/lib/predicate.h b/lib/predicate.h
index 47d700c..82bf76d 100644
--- a/lib/predicate.h
+++ b/lib/predicate.h
@@ -21,44 +21,18 @@
 
 #include "paragraph.h"
 
-#define MAX_OPS 4096
-#define MAX_ATOMS 4096
-
-#define I_NOP  0
-#define I_NEG  1 /* --not; 1-1 */
-#define I_AND  2 /* --and; 2-1 */
-#define I_OR   3 /* --or;  2-1 */
-#define I_PUSH(n) (4+(n)) /* push result of nth atomic proposition */
-
 struct atom;
+struct predicate;
 
-/* A predicate is represented as a set of atomic predicates and a
- * program - a sequence of stack-based "bytecode" instructions - that
- * specifies the structure of the combined predicate.  */
-struct predicate {
-	/* Number of atomic predicates.  */
-	size_t num_atoms;
-	/* Length of the program */
-	size_t proglen;
-	/* The program */
-	int program[MAX_OPS];
-	/* The atomic predicates */
-	struct atom *atoms;
-};
-
-void init_predicate(struct predicate * p);
-
-static inline
-struct atom * get_current_atom(struct predicate * p)
-{
-	assert(p->num_atoms > 0);
-	return &p->atoms[p->num_atoms-1];
-}
-
-void addinsn(struct predicate * p, int insn);
+struct predicate *predicate_AND(struct predicate *, struct predicate *);
+struct predicate *predicate_OR(struct predicate *, struct predicate *);
+struct predicate *predicate_NOT(struct predicate *);
+struct predicate *predicate_ATOM(struct atom *);
 
 bool does_para_satisfy(struct predicate * p, para_t *);
 
 bool check_predicate(struct predicate * p);
 
+void predicate_print(struct predicate *p);
+
 #endif /* PREDICATE_H */