From f83e3229ea5c917dfb1bd1a59b1768fdcb882f9a Mon Sep 17 00:00:00 2001 From: Sergey Poznyakoff Date: Sat, 14 May 2011 19:00:52 +0300 Subject: Wildcard look-ups (initial implementation). * src/grecs-gram.y (union): New field. (IDENT): Change type to . All uses changed. * src/grecs-lex.l (ident): Initialize ident.locus. * src/grecs.h (GRECS_NODE_FLAG_NODESCEND): New flag. (grecs_match_buf_t): New data type. (grecs_match_first,grecs_match_next) (grecs_match_buf_free): New protos. (grecs_tree_first_node,grecs_next_node): New protos. * src/format.c (grecs_format_node): Handle GRECS_NODE_FLAG_NODESCEND flag. * src/lookup.c (grecs_match_buf): New struct. (grecs_match_first,grecs_match_next) (grecs_match_buf_free): New functions. (split_cfg_path): Fill in array of values, if given. (parse_tag): Remove. All uses updated. (node_finder): Use grecs_match_buf. * src/tree.c (grecs_tree_reduce): Fill config_keywords with 0s. (grecs_tree_first_node, grecs_next_node): New functions. * tests/.gitignore: Add gcfenum * tests/enum.at: New file. * tests/glob00.at: New file. * tests/glob01.at: New file. * tests/glob02.at: New file. * tests/gcfenum.c: New file. * tests/Makefile.am: Build gcfenum. Add enum.at test. * tests/testsuite.at: Include enum.at. * tests/gcfpeek.c: Implement -match option. --- src/format.c | 12 +-- src/grecs-gram.y | 23 +++-- src/grecs-lex.l | 3 +- src/grecs.h | 12 +++ src/lookup.c | 252 ++++++++++++++++++++++++++++++++++++++----------------- src/tree.c | 28 +++++++ 6 files changed, 240 insertions(+), 90 deletions(-) (limited to 'src') diff --git a/src/format.c b/src/format.c index b4a4340..1302520 100644 --- a/src/format.c +++ b/src/format.c @@ -271,12 +271,14 @@ grecs_format_node(struct grecs_node *node, int flags, FILE *fp) switch (node->type) { case grecs_node_root: case grecs_node_block: - for (node = node->down; node; node = node->next) { - grecs_format_node(node, flags, fp); - if (node->next) - fputc('\n', fp); + if (!(flags & GRECS_NODE_FLAG_NODESCEND)) { + for (node = node->down; node; node = node->next) { + grecs_format_node(node, flags, fp); + if (node->next) + fputc('\n', fp); + } + break; } - break; case grecs_node_stmt: if (flags & GRECS_NODE_FLAG_LOCUS) { diff --git a/src/grecs-gram.y b/src/grecs-gram.y index 960567e..9f8d000 100644 --- a/src/grecs-gram.y +++ b/src/grecs-gram.y @@ -34,14 +34,20 @@ int grecs_default_port = 0; %} %union { + struct { + grecs_locus_t locus; + char *string; + } ident; char *string; grecs_value_t svalue, *pvalue; struct grecs_list *list; struct grecs_node *node; + grecs_locus_t locus; struct { struct grecs_node *head, *tail; } node_list; } -%token IDENT STRING QSTRING MSTRING +%token IDENT +%token STRING QSTRING MSTRING %type string slist %type slist0 %type value @@ -78,15 +84,15 @@ stmt : simple simple : IDENT vallist ';' { $$ = grecs_node_create(grecs_node_stmt, - &grecs_current_locus); - $$->ident = $1; + &$1.locus); + $$->ident = $1.string; $$->v.value = $2; } | IDENT ';' { $$ = grecs_node_create(grecs_node_stmt, - &grecs_current_locus); - $$->ident = $1; + &$1.locus); + $$->ident = $1.string; $$->v.value = NULL; } ; @@ -94,8 +100,8 @@ simple : IDENT vallist ';' block : IDENT tag '{' stmtlist '}' opt_sc { $$ = grecs_node_create(grecs_node_block, - &grecs_current_locus); - $$->ident = $1; + &$1.locus); + $$->ident = $1.string; $$->v.value = $2; grecs_node_bind($$, $4.head, 1); } @@ -161,6 +167,9 @@ value : string string : STRING | IDENT + { + $$ = $1.string; + } | slist ; diff --git a/src/grecs-lex.l b/src/grecs-lex.l index a3cc7d8..4d491fe 100644 --- a/src/grecs-lex.l +++ b/src/grecs-lex.l @@ -411,7 +411,8 @@ ident() len = strlen(p); str = grecs_malloc(len + 1); strcpy(str, p); - yylval.string = str; + yylval.ident.locus = grecs_current_locus; + yylval.ident.string = str; return IDENT; } diff --git a/src/grecs.h b/src/grecs.h index 05eeff2..61a915b 100644 --- a/src/grecs.h +++ b/src/grecs.h @@ -273,6 +273,7 @@ void grecs_format_value(struct grecs_value *val, int flags, FILE *fp); #define GRECS_NODE_FLAG_QUOTE 0x0800 #define GRECS_NODE_FLAG_NOQUOTE 0x1000 #define GRECS_NODE_FLAG_QUOTE_HEX 0x2000 +#define GRECS_NODE_FLAG_NODESCEND 0x4000 #define GRECS_NODE_FLAG_DEFAULT \ (GRECS_NODE_FLAG_PATH|GRECS_NODE_FLAG_VALUE|GRECS_NODE_FLAG_QUOTE) void grecs_format_node(struct grecs_node *node, int flags, FILE *fp); @@ -354,8 +355,16 @@ int grecs_tree_join(struct grecs_node *dst, struct grecs_node *src); int grecs_tree_process(struct grecs_node *node, struct grecs_keyword *kwd); +typedef struct grecs_match_buf *grecs_match_buf_t; +struct grecs_node *grecs_match_first(struct grecs_node *tree, + const char *pattern, + grecs_match_buf_t *buf); +struct grecs_node *grecs_match_next(struct grecs_match_buf *buf); +void grecs_match_buf_free(struct grecs_match_buf *buf); + int grecs_value_eq(struct grecs_value *a, struct grecs_value *b); struct grecs_node *grecs_find_node(struct grecs_node *node, const char *path); + struct grecs_node *grecs_node_from_path(const char *path, const char *value); int grecs_tree_reduce(struct grecs_node *node, struct grecs_keyword *kwd, int flags); @@ -363,5 +372,8 @@ int grecs_tree_reduce(struct grecs_node *node, struct grecs_keyword *kwd, void grecs_tree_sort(struct grecs_node *node, int (*compare)(struct grecs_node const *, struct grecs_node const *)); + +struct grecs_node *grecs_tree_first_node(struct grecs_node *tree); +struct grecs_node *grecs_next_node(struct grecs_node *node); #endif diff --git a/src/lookup.c b/src/lookup.c index 09b7e85..d30d348 100644 --- a/src/lookup.c +++ b/src/lookup.c @@ -81,50 +81,34 @@ grecs_value_eq(struct grecs_value *a, struct grecs_value *b) } -static int -split_cfg_path(const char *path, int *pargc, char ***pargv) -{ +struct grecs_match_buf { int argc; char **argv; - char *delim = "."; - char static_delim[2] = { 0, 0 }; - - if (path[0] == '\\') { - argv = calloc(2, sizeof (*argv)); - if (!argv) - return ENOMEM; - argv[0] = strdup(path + 1); - if (!argv[0]) { - free(argv); - return ENOMEM; - } - argv[1] = NULL; - argc = 1; - } else { - struct wordsplit ws; - - if (ispunct(path[0])) { - delim = static_delim; - delim[0] = path[0]; - path++; - } - ws.ws_delim = delim; - - if (wordsplit(path, &ws, WRDSF_DEFFLAGS|WRDSF_DELIM)) - return errno; - argc = ws.ws_wordc; - argv = ws.ws_wordv; - ws.ws_wordc = 0; - ws.ws_wordv = NULL; - wordsplit_free(&ws); + int argi; + struct grecs_value **labelv; + struct grecs_node *node; +}; + +static void +grecs_match_buf_free_contents(struct grecs_match_buf *buf) +{ + size_t i; + for (i = 0; i < buf->argc; i++) { + free(buf->argv[i]); + grecs_value_free(buf->labelv[i]); } - - *pargc = argc; - *pargv = argv; - - return 0; + free(buf->argv); + free(buf->labelv); } +void +grecs_match_buf_free(struct grecs_match_buf *buf) +{ + grecs_match_buf_free_contents(buf); + free(buf); +} + + static struct grecs_value * parse_label(const char *str) { @@ -178,44 +162,81 @@ parse_label(const char *str) return val; } - -struct find_closure { +static int +split_cfg_path(const char *path, int *pargc, char ***pargv, + grecs_value_t ***pvalv) +{ int argc; char **argv; - int tag; - struct grecs_value *label; - struct grecs_node *node; -}; + char *delim = "."; + char static_delim[2] = { 0, 0 }; + + if (path[0] == '\\') { + argv = calloc(2, sizeof (*argv)); + if (!argv) + return ENOMEM; + argv[0] = strdup(path + 1); + if (!argv[0]) { + free(argv); + return ENOMEM; + } + argv[1] = NULL; + argc = 1; + } else { + struct wordsplit ws; + + if (ispunct(path[0])) { + delim = static_delim; + delim[0] = path[0]; + path++; + } + ws.ws_delim = delim; + + if (wordsplit(path, &ws, WRDSF_DEFFLAGS|WRDSF_DELIM)) + return errno; + argc = ws.ws_wordc; + argv = ws.ws_wordv; + ws.ws_wordc = 0; + ws.ws_wordv = NULL; + wordsplit_free(&ws); + } -static void -parse_tag(struct find_closure *fptr) -{ - char *p = strchr(fptr->argv[fptr->tag], '='); - if (p) { - *p++ = 0; - fptr->label = parse_label(p); + *pargv = argv; + *pargc = argc; + if (pvalv) { + int i; + grecs_value_t **valv; + + valv = grecs_calloc(argc, sizeof(valv[0])); + for (i = 0; i < argc; i++) { + char *p = strchr(argv[i], '='); + if (p) { + *p++ = 0; + valv[i] = parse_label(p); + } + } + *pvalv = valv; } - else - fptr->label = NULL; + return 0; } + static enum grecs_tree_recurse_res node_finder(enum grecs_tree_recurse_op op, struct grecs_node *node, void *data) { - struct find_closure *fdptr = data; + struct grecs_match_buf *buf = data; if (op == grecs_tree_recurse_post || node->type == grecs_node_root) return grecs_tree_recurse_ok; - if (strcmp(fdptr->argv[fdptr->tag], node->ident) == 0 - && (!fdptr->label || - grecs_value_eq(fdptr->label, node->v.value))) { - fdptr->tag++; - if (fdptr->tag == fdptr->argc) { - fdptr->node = node; + if (strcmp(buf->argv[buf->argi], node->ident) == 0 + && (!buf->labelv[buf->argi] || + grecs_value_eq(buf->labelv[buf->argi], node->v.value))) { + buf->argi++; + if (buf->argi == buf->argc) { + buf->node = node; return grecs_tree_recurse_stop; } - parse_tag(fdptr); return grecs_tree_recurse_ok; } @@ -226,22 +247,17 @@ node_finder(enum grecs_tree_recurse_op op, struct grecs_node *node, void *data) struct grecs_node * grecs_find_node(struct grecs_node *node, const char *path) { - int rc, i; - struct find_closure clos; + int rc; + struct grecs_match_buf buf; - rc = split_cfg_path(path, &clos.argc, &clos.argv); - if (rc || !clos.argc) + rc = split_cfg_path(path, &buf.argc, &buf.argv, &buf.labelv); + if (rc || !buf.argc) return NULL; - clos.tag = 0; - clos.label = NULL; - clos.node = NULL; - parse_tag(&clos); - grecs_tree_recurse(node, node_finder, &clos); - for (i = 0; i < clos.argc; i++) - free(clos.argv[i]); - free(clos.argv); - grecs_value_free(clos.label); - return clos.node; + buf.argi = 0; + buf.node = NULL; + grecs_tree_recurse(node, node_finder, &buf); + grecs_match_buf_free_contents(&buf); + return buf.node; } @@ -254,7 +270,7 @@ grecs_node_from_path(const char *path, const char *value) char **argv; struct grecs_node *dn = NULL; - rc = split_cfg_path(path, &argc, &argv); + rc = split_cfg_path(path, &argc, &argv, NULL); if (rc) return NULL; dn = grecs_node_create(grecs_node_stmt, NULL); @@ -297,3 +313,85 @@ grecs_node_from_path(const char *path, const char *value) return dn; } + +#define ISWC(c,w) ((c)[0] == (w) && (c)[1] == 0) + +static int +grecs_match(struct grecs_match_buf *buf) +{ + struct grecs_node *node; + int wcard = 0; + + buf->argi = buf->argc - 1; + node = buf->node; + + while (buf->argi >= 0) { + if (ISWC(buf->argv[buf->argi], '*')) { + wcard = 1; + if (buf->argi-- == 0) + return 1; + continue; + } + + if (strcmp(buf->argv[buf->argi], node->ident) == 0 + /* FIXME: */ + && (!buf->labelv[buf->argi] || + grecs_value_eq(buf->labelv[buf->argi], node->v.value))) { + wcard = 0; + node = node->up; + if (buf->argi-- == 0) + return !node || + node->type == grecs_node_root; + } else if (!wcard) + return 0; + else + node = node->up; + if (!node || node->type == grecs_node_root) + return ISWC(buf->argv[buf->argi], '*'); + } + return 0; +} + +struct grecs_node * +grecs_match_next(struct grecs_match_buf *buf) +{ + while (buf->node = grecs_next_node(buf->node)) + if (grecs_match(buf)) + break; + return buf->node; +} + +struct grecs_node * +grecs_match_first(struct grecs_node *tree, const char *pattern, + struct grecs_match_buf **pbuf) +{ + struct grecs_node *node; + struct grecs_match_buf *buf; + + if (tree->type != grecs_node_root) { + errno = EINVAL; + return NULL; + } + errno = 0; + + buf = grecs_zalloc(sizeof(*buf)); + if (split_cfg_path(pattern, &buf->argc, &buf->argv, &buf->labelv)) { + free(buf); + return NULL; + } + /* FIXME: Compress argv/argc by replacing contiguous sequences of *'s + with a single *. */ + buf->argi = 0; + buf->node = grecs_tree_first_node(tree); + *pbuf = buf; + if (grecs_match(buf)) + node = buf->node; + else + node = grecs_match_next(buf); + if (!node) { + grecs_match_buf_free(buf); + *pbuf = NULL; + } + return node; +} + diff --git a/src/tree.c b/src/tree.c index 3419de7..ceb6688 100644 --- a/src/tree.c +++ b/src/tree.c @@ -1072,6 +1072,7 @@ grecs_tree_reduce(struct grecs_node *node, struct grecs_keyword *kwd, struct nodeproc_closure clos; struct grecs_keyword config_keywords; + memset(&config_keywords, 0, sizeof(config_keywords)); config_keywords.kwd = kwd; if (kwd) { clos.cursect = &config_keywords; @@ -1085,3 +1086,30 @@ grecs_tree_reduce(struct grecs_node *node, struct grecs_keyword *kwd, grecs_list_free(clos.sections); return rc; } + + +struct grecs_node * +grecs_tree_first_node(struct grecs_node *tree) +{ + if (tree->type != grecs_node_root) { + errno = EINVAL; + return NULL; + } + errno = 0; + return tree->down; +} + +struct grecs_node * +grecs_next_node(struct grecs_node *node) +{ + if (!node) + return NULL; + if (node->down) + return node->down; + while (!node->next) { + node = node->up; + if (!node || node->type == grecs_node_root) + return NULL; + } + return node->next; +} -- cgit v1.2.1