[Dctrl-tools-devel] [SCM] Debian control file query tools branch, master, updated. 2.18-22-g0705462
Antti-Juhani Kaijanaho
ajk at debian.org
Wed Oct 19 21:25:06 UTC 2011
The following commit has been merged in the master branch:
commit 0705462df7b3d490ede928a45586cd1159798e0e
Author: Antti-Juhani Kaijanaho <ajk at debian.org>
Date: Thu Oct 20 00:24:49 2011 +0300
Rewrite the paragraph logic to use a tree structure.
Signed-off-by: Antti-Juhani Kaijanaho <ajk at debian.org>
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 at 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 at debian.org> Wed, 19 Oct 2011 21:09:47 +0300
+ -- Antti-Juhani Kaijanaho <ajk at 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(¶);
if (para_eof(&pp)) break;
if ((args.invert_match
- || !does_para_satisfy(&args.p, ¶))
+ || !does_para_satisfy(args.p, ¶))
&& (!args.invert_match
- || does_para_satisfy(&args.p, ¶))) {
+ || does_para_satisfy(args.p, ¶))) {
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 */
--
Debian control file query tools
More information about the Dctrl-tools-devel
mailing list