> But regardless, doing the checks on the ktypes (and possibly vtypes) > first, and then on the atype, should obviate the need for the > atype_complete flag.
Here is the updated patch, all tests pass, but I know few issues with some new features. I don't see other way to properly detect what exactly needs to be typechecked without atype_complete flag. I tought at first to use a condition on primitive lens, but it fail because L_CONCAT, L_UNION, L_STAR and some others may be applied inside or outside subtree. Cheer, Francis
>From afde2a661bf92f5e63845c401d8795f276856d38 Mon Sep 17 00:00:00 2001 From: Francis Giraldeau <[email protected]> Date: Sun, 24 Oct 2010 15:07:50 -0400 Subject: [PATCH] Add support for multipart keys Multipart keys are keys composed of multiple key and label lenses. In the get direction, the node label is the concatenation of all keys and labels of the subtree. In the put direction, the node label is split between each keys and labels inside the tree. The labels are added in the get direction and removed in the put direction. Multipart keys require typechecking on ktype and vtype, and atype must be done only on complete atype, compiled by subtree. This patch replaces checks for multiple keys inside a subtree from fail to pass. Primitive lenses have a default ktype and vtype set to the empty pattern to make key matching correspond to the lens structure in the put direction, and avoid corner cases in typechecking. * src/get.c : build the node label by concatenating keys and labels * src/lens.c : perform typecheck on complete atype, add typecheck on ktype and vtype. Add default value to ktype and vtype for all primary lens, to handle all typechecking situations. * src/lens.h : add flag to keep track of the atype is ready for typechecking * src/put.c : parse the node label against the ktype of a subtree child, add a regs to state to store the matching result and keep track of the current matching group * src/regexp.c : handle passing NULL values to various functions This patch includes the lens debug output patch and tests in tests/modules. --- src/get.c | 45 +++++++- src/lens.c | 150 +++++++++++++++++++++++++-- src/lens.h | 5 + src/put.c | 64 +++++++++++- src/regexp.c | 2 + tests/modules/fail_key_concat_ambig.aug | 3 + tests/modules/fail_key_union_ambig.aug | 3 + tests/modules/fail_multi_key_concat.aug | 3 - tests/modules/fail_multi_key_iter.aug | 4 - tests/modules/fail_recursion_multi_keys.aug | 4 - tests/modules/pass_multipart_key.aug | 10 ++ 11 files changed, 267 insertions(+), 26 deletions(-) create mode 100644 tests/modules/fail_key_concat_ambig.aug create mode 100644 tests/modules/fail_key_union_ambig.aug delete mode 100644 tests/modules/fail_multi_key_concat.aug delete mode 100644 tests/modules/fail_multi_key_iter.aug delete mode 100644 tests/modules/fail_recursion_multi_keys.aug create mode 100644 tests/modules/pass_multipart_key.aug diff --git a/src/get.c b/src/get.c index 11ea5de..3bb7bf6 100644 --- a/src/get.c +++ b/src/get.c @@ -433,10 +433,30 @@ static struct skel *parse_value(struct lens *lens, static struct tree *get_key(struct lens *lens, struct state *state) { ensure0(lens->tag == L_KEY, state->info); - if (! REG_MATCHED(state)) + int r; + char *tok; + + if (! REG_MATCHED(state)) { no_match_error(state, lens); - else - state->key = token(state); + return NULL; + } + tok = token(state); + if (tok == NULL) { + // FIXME: get_error will likely crash and burn on OOM + get_error(state, lens, "Out of memory"); + return NULL; + } + if (state->key == NULL) { + state->key = tok; + } else { + r = REALLOC_N(state->key, strlen(state->key) + strlen(tok) + 1); + if (r < 0) { + get_error(state, lens, "Out of memory"); + return NULL; + } + strcat(state->key, tok); + FREE(tok); + } return NULL; } @@ -447,7 +467,24 @@ static struct skel *parse_key(struct lens *lens, struct state *state) { static struct tree *get_label(struct lens *lens, struct state *state) { ensure0(lens->tag == L_LABEL, state->info); - state->key = strdup(lens->string->str); + int r; + char *str = strdup(lens->string->str); + if (str == NULL) { + // FIXME: get_error will likely crash and burn on OOM + get_error(state, lens, "Out of memory"); + return NULL; + } + if (state->key == NULL) { + state->key = str; + } else { + r = REALLOC_N(state->key, strlen(state->key) + strlen(str) + 1); + if (r < 0) { + get_error(state, lens, "Out of memory"); + return NULL; + } + strcat(state->key, str); + FREE(str); + } return NULL; } diff --git a/src/lens.c b/src/lens.c index 29859f5..6475ea1 100644 --- a/src/lens.c +++ b/src/lens.c @@ -26,6 +26,7 @@ #include "lens.h" #include "memory.h" #include "errcode.h" +#include "internal.h" /* This enum must be kept in sync with type_offs and ntypes */ enum lens_type { @@ -59,6 +60,8 @@ static const char *const tags[] = { "subtree", "star", "maybe", "rec" }; +#define ltag(lens) (tags[lens->tag - L_DEL]) + static const struct string digits_string = { .ref = REF_MAX, .str = (char *) "[0123456789]+" }; @@ -250,6 +253,7 @@ struct value *lns_make_union(struct info *info, lens->consumes_value = consumes_value; if (! recursive) lens->ctype_nullable = ctype_nullable; + lens->atype_complete = l1->atype_complete || l2->atype_complete; return make_lens_value(lens); } @@ -268,14 +272,13 @@ struct value *lns_make_concat(struct info *info, if (l1->value && l2->value) { return make_exn_value(info, "Multiple stores in concat"); } - if (l1->key && l2->key) { - return make_exn_value(info, "Multiple keys/labels in concat"); - } lens = make_lens_binop(L_CONCAT, info, l1, l2, regexp_concat_n); lens->consumes_value = consumes_value; if (! recursive) lens->ctype_nullable = ctype_nullable; + lens->atype_complete = l1->atype_complete || l2->atype_complete; + return make_lens_value(lens); } @@ -335,6 +338,7 @@ struct value *lns_make_subtree(struct info *info, struct lens *l) { lens->rec_internal = l->rec_internal; if (! l->recursive) lens->ctype_nullable = l->ctype_nullable; + lens->atype_complete = true; return make_lens_value(lens); } @@ -349,9 +353,6 @@ struct value *lns_make_star(struct info *info, struct lens *l, int check) { if (l->value) { return make_exn_value(info, "Multiple stores in iteration"); } - if (l->key) { - return make_exn_value(info, "Multiple keys/labels in iteration"); - } lens = make_lens_unop(L_STAR, info, l); for (int t = 0; t < ntypes; t++) { @@ -360,6 +361,7 @@ struct value *lns_make_star(struct info *info, struct lens *l, int check) { lens->recursive = l->recursive; lens->rec_internal = l->rec_internal; lens->ctype_nullable = 1; + lens->atype_complete = l->atype_complete; return make_lens_value(lens); } @@ -391,6 +393,7 @@ struct value *lns_make_maybe(struct info *info, struct lens *l, int check) { lens->recursive = l->recursive; lens->rec_internal = l->rec_internal; lens->ctype_nullable = 1; + lens->atype_complete = l->atype_complete; return make_lens_value(lens); } @@ -498,6 +501,7 @@ struct value *lns_make_prim(enum lens_tag tag, struct info *info, lens->value = (tag == L_STORE || tag == L_VALUE); lens->consumes_value = (tag == L_STORE || tag == L_VALUE); lens->atype = regexp_make_empty(info); + lens->atype_complete = false; /* Set the ctype */ if (tag == L_DEL || tag == L_STORE || tag == L_KEY) { lens->ctype = ref(regexp); @@ -524,6 +528,8 @@ struct value *lns_make_prim(enum lens_tag tag, struct info *info, lens->ktype = make_regexp_literal(info, lens->string->str); if (lens->ktype == NULL) goto error; + } else if (tag == L_STORE || tag == L_VALUE || tag == L_COUNTER || tag == L_DEL) { + lens->ktype = regexp_make_empty(info); } /* Set the vtype */ @@ -531,6 +537,9 @@ struct value *lns_make_prim(enum lens_tag tag, struct info *info, lens->vtype = restrict_regexp(lens->regexp); } else if (tag == L_VALUE) { lens->vtype = make_regexp_literal(info, lens->string->str); + } else if (tag == L_KEY || tag == L_COUNTER || tag == L_LABEL || + tag == L_SEQ || tag == L_DEL) { + lens->vtype = regexp_make_empty(info); } return make_lens_value(lens); @@ -596,9 +605,25 @@ static struct value *disjoint_check(struct info *info, bool is_get, static struct value *typecheck_union(struct info *info, struct lens *l1, struct lens *l2) { struct value *exn = NULL; + struct value *ktype_exn = NULL; + struct value *vtype_exn = NULL; + int atype_complete = l1->atype_complete && l2->atype_complete; exn = disjoint_check(info, true, l1->ctype, l2->ctype); - if (exn == NULL) { + + // FIXME: must adapt disjoint_check to make union.put ambig on ktype and vtype + if (exn == NULL && !l1->atype_complete && !l2->atype_complete) { + ktype_exn = disjoint_check(info, true, l1->ktype, l2->ktype); + vtype_exn = disjoint_check(info, true, l1->vtype, l2->vtype); + if (ktype_exn != NULL && vtype_exn != NULL) { + exn = ktype_exn; + unref(vtype_exn, value); + } else { + unref(ktype_exn, value); + unref(vtype_exn, value); + } + } + if (exn == NULL && l1->atype_complete && l2->atype_complete) { exn = disjoint_check(info, false, l1->atype, l2->atype); } if (exn != NULL) { @@ -707,10 +732,19 @@ ambig_concat_check(struct info *info, const char *msg, static struct value *typecheck_concat(struct info *info, struct lens *l1, struct lens *l2) { struct value *result = NULL; + int atype_complete = l1->atype_complete && l2->atype_complete; result = ambig_concat_check(info, "ambiguous concatenation", CTYPE, l1, l2); - if (result == NULL) { + if (result == NULL && !atype_complete) { + result = ambig_concat_check(info, "ambigous label concatenation", + KTYPE, l1, l2); + } + if (result == NULL && !atype_complete) { + result = ambig_concat_check(info, "ambigous value concatenation", + VTYPE, l1, l2); + } + if (result == NULL && atype_complete) { result = ambig_concat_check(info, "ambiguous tree concatenation", ATYPE, l1, l2); } @@ -794,6 +828,8 @@ void free_lens(struct lens *lens) { return; ensure(lens->ref == 0, lens->info); + if (debugging("lenses")) + dump_lens_tree(lens); switch (lens->tag) { case L_DEL: unref(lens->regexp, regexp); @@ -1885,8 +1921,6 @@ static struct value *typecheck(struct lens *l, int check) { exn = typecheck_iter(l->info, l->child); if (exn == NULL && l->value) exn = make_exn_value(l->info, "Multiple stores in iteration"); - if (exn == NULL && l->key) - exn = make_exn_value(l->info, "Multiple keys/labels in iteration"); break; case L_MAYBE: if (check) @@ -2092,6 +2126,102 @@ struct value *lns_check_rec(struct info *info, return result; } +#if ENABLE_DEBUG +void dump_lens_tree(struct lens *lens){ + static int count = 0; + FILE *fp; + + fp = debug_fopen("lens_%02d_%s.dot", count++, ltag(lens)); + if (fp == NULL) + return; + + fprintf(fp, "digraph \"%s\" {\n", "lens"); + dump_lens(fp, lens); + fprintf(fp, "}\n"); + + fclose(fp); +} + +void dump_lens(FILE *out, struct lens *lens){ + int i = 0; + struct regexp *re; + + fprintf(out, "\"%p\" [ shape = box, label = \"%s\\n", lens, ltag(lens)); + + for (int t=0; t < ntypes; t++) { + re = ltype(lens, t); + if (re == NULL) + continue; + fprintf(out, "%s=%s\\n",lens_type_names[t], re->pattern->str); + } + + fprintf(out, "atype_complete=%x\\n", lens->atype_complete); + fprintf(out, "recursive=%x\\n", lens->recursive); + fprintf(out, "rec_internal=%x\\n", lens->rec_internal); + fprintf(out, "consumes_value=%x\\n", lens->consumes_value); + fprintf(out, "ctype_nullable=%x\\n", lens->ctype_nullable); + fprintf(out, "\"];\n"); + switch(lens->tag){ + case L_DEL: + break; + case L_STORE: + break; + case L_VALUE: + break; + case L_KEY: + break; + case L_LABEL: + break; + case L_SEQ: + break; + case L_COUNTER: + break; + case L_CONCAT: + for(i = 0; i<lens->nchildren;i++){ + fprintf(out, "\"%p\" -> \"%p\"\n", lens, lens->children[i]); + dump_lens(out, lens->children[i]); + } + break; + case L_UNION: + for(i = 0; i<lens->nchildren;i++){ + fprintf(out, "\"%p\" -> \"%p\"\n", lens, lens->children[i]); + dump_lens(out, lens->children[i]); + } + break; + case L_SUBTREE: + fprintf(out, "\"%p\" -> \"%p\"\n", lens, lens->child); + dump_lens(out, lens->child); + break; + case L_STAR: + fprintf(out, "\"%p\" -> \"%p\"\n", lens, lens->child); + dump_lens(out, lens->child); + + break; + case L_MAYBE: + fprintf(out, "\"%p\" -> \"%p\"\n", lens, lens->child); + dump_lens(out, lens->child); + + break; + case L_REC: + if (lens->rec_internal == 0){ + fprintf(out, "\"%p\" -> \"%p\"\n", lens, lens->child); + dump_lens(out, lens->body); + } + break; + /* uncomment for square lens */ + /* + case L_SQUARE: + fprintf(out, "\"%p\" -> \"%p\"\n", lens, lens->child); + dump_lens(out, lens->child); + break; + */ + default: + fprintf(out, "ERROR\n"); + break; + } +} +#endif + /* * Local variables: * indent-tabs-mode: nil diff --git a/src/lens.h b/src/lens.h index 7c2b6ce..f8bab47 100644 --- a/src/lens.h +++ b/src/lens.h @@ -85,6 +85,8 @@ struct lens { /* Whether we are inside a recursive lens or outside */ unsigned int rec_internal : 1; unsigned int ctype_nullable : 1; + /* Set if the lens has atype ready to typecheck */ + unsigned int atype_complete : 1; union { /* Primitive lenses */ struct { /* L_DEL uses both */ @@ -240,6 +242,9 @@ void free_lens(struct lens *lens); */ char *enc_format(const char *e, size_t len); +void dump_lens_tree(struct lens *lens); +void dump_lens(FILE *out, struct lens *lens); + #endif diff --git a/src/put.c b/src/put.c index d592420..67b6774 100644 --- a/src/put.c +++ b/src/put.c @@ -64,6 +64,12 @@ struct state { char *path; /* Position in the tree, for errors */ size_t pos; struct lns_error *error; + /* We keep a register to hold the parse of a key in the case of multiple + * keys and labels inside subtree. KREGS is the register that hold the match + * of the subtree's key and KNREGS is updated as we traverse lenses in a + * subtree */ + struct re_registers *kregs; + uint knreg; }; static void create_lens(struct lens *lens, struct state *state); @@ -427,17 +433,28 @@ static int skel_instance_of(struct lens *lens, struct skel *skel) { return 0; } +// FIXME: this function is duplicated with get.c, should be factorized +static void free_regs(struct state *state) { + if (state->kregs != NULL) { + free(state->kregs->start); + free(state->kregs->end); + FREE(state->kregs); + } +} + /* * put */ static void put_subtree(struct lens *lens, struct state *state) { assert(lens->tag == L_SUBTREE); + int count; struct state oldstate = *state; struct split oldsplit = *state->split; size_t oldpathlen = strlen(state->path); struct tree *tree = state->split->tree; struct split *split = NULL; + int need_free = false; state->key = tree->label; state->value = tree->value; @@ -446,6 +463,28 @@ static void put_subtree(struct lens *lens, struct state *state) { split = make_split(tree->children); set_split(state, split); + if (state->key == NULL) { + need_free = true; + state->key = strdup(""); + if (state->key == NULL) { + // get_error Out of memory + return; + } + } + if (ALLOC(state->kregs) < 0) { + // FIXME: appropriate error handling + //get_error(state, lens, "Out of memory"); + return; + } + count = regexp_match(lens->child->ktype, state->key, + strlen(state->key), 0, state->kregs); + if (count < -1) { + regexp_match_error(state, lens, count, split); + free_regs(state); + // FIXME: return error + } + state->knreg = 0; + dict_lookup(tree->label, state->dict, &state->skel, &state->dict); if (state->skel == NULL || ! skel_instance_of(lens->child, state->skel)) { create_lens(lens->child, state); @@ -454,6 +493,9 @@ static void put_subtree(struct lens *lens, struct state *state) { } assert(state->error != NULL || state->split->next == NULL); + free_regs(state); + if (need_free) + FREE(state->key); oldstate.error = state->error; oldstate.path = state->path; *state = oldstate; @@ -481,6 +523,8 @@ static void put_union(struct lens *lens, struct state *state) { create_lens(l, state); return; } + if (lens->children[i]->ktype != NULL) + state->knreg += 1 + regexp_nsub(lens->children[i]->ktype); } put_error(state, lens, "None of the alternatives in the union match"); } @@ -494,6 +538,7 @@ static void put_concat(struct lens *lens, struct state *state) { state->skel = state->skel->skels; set_split(state, split); + state->knreg += 1; for (int i=0; i < lens->nchildren; i++) { if (state->split == NULL) { put_error(state, lens, @@ -504,6 +549,8 @@ static void put_concat(struct lens *lens, struct state *state) { put_lens(lens->children[i], state); state->skel = state->skel->next; next_split(state); + if (lens->children[i]->ktype != NULL) + state->knreg += 1 + regexp_nsub(lens->children[i]->ktype); } list_free(split); set_split(state, oldsplit); @@ -540,6 +587,8 @@ static void put_quant_star(struct lens *lens, struct state *state) { state->skel = state->skel->skels; set_split(state, split); last_split = state->split; + if (lens->ktype != NULL) + state->knreg += 1; while (state->split != NULL && state->skel != NULL) { put_lens(lens->child, state); state->skel = state->skel->next; @@ -562,6 +611,8 @@ static void put_quant_maybe(struct lens *lens, struct state *state) { assert(lens->tag == L_MAYBE); struct lens *child = lens->child; + if (lens->ktype != NULL) + state->knreg += 1; if (applies(child, state)) { if (skel_instance_of(child, state->skel)) put_lens(child, state); @@ -590,6 +641,14 @@ static void put_rec(struct lens *lens, struct state *state) { put_lens(lens->body, state); } +static void put_key(struct lens *lens, struct state *state) { + assert(state->knreg < state->kregs->num_regs); + assert(state->kregs->start[state->knreg] != -1); + char *tok = strndup(state->key, state->kregs->end[state->knreg] - state->kregs->start[state->knreg]); + fprintf(state->out, "%s", tok); + FREE(tok); +} + static void put_lens(struct lens *lens, struct state *state) { if (state->error != NULL) return; @@ -602,7 +661,7 @@ static void put_lens(struct lens *lens, struct state *state) { put_store(lens, state); break; case L_KEY: - fprintf(state->out, "%s", state->key); + put_key(lens, state); break; case L_LABEL: case L_VALUE: @@ -784,12 +843,15 @@ void lns_put(FILE *out, struct lens *lens, struct tree *tree, state.out = out; state.split = make_split(tree); state.key = tree->label; + if (ALLOC(state.kregs) < 0) + return; put_lens(lens, &state); free(state.path); free_split(state.split); free_skel(state.skel); free_dict(state.dict); + free_regs(&state); if (err != NULL) { *err = state.error; } else { diff --git a/src/regexp.c b/src/regexp.c index 14020af..8e41103 100644 --- a/src/regexp.c +++ b/src/regexp.c @@ -474,6 +474,8 @@ int regexp_matches_empty(struct regexp *r) { } int regexp_nsub(struct regexp *r) { + if (r == NULL) + return 0; if (r->re == NULL) if (regexp_compile(r) == -1) return -1; diff --git a/tests/modules/fail_key_concat_ambig.aug b/tests/modules/fail_key_concat_ambig.aug new file mode 100644 index 0000000..4b5a32d --- /dev/null +++ b/tests/modules/fail_key_concat_ambig.aug @@ -0,0 +1,3 @@ +module Fail_key_concat_ambig = + + let lns = key /(a)(x)?/ . key /(x)?(b)/ diff --git a/tests/modules/fail_key_union_ambig.aug b/tests/modules/fail_key_union_ambig.aug new file mode 100644 index 0000000..182355c --- /dev/null +++ b/tests/modules/fail_key_union_ambig.aug @@ -0,0 +1,3 @@ +module Fail_key_union_ambig = + + let lns = key "a" | label "a" diff --git a/tests/modules/fail_multi_key_concat.aug b/tests/modules/fail_multi_key_concat.aug deleted file mode 100644 index 7a3b147..0000000 --- a/tests/modules/fail_multi_key_concat.aug +++ /dev/null @@ -1,3 +0,0 @@ -module Fail_multi_key_concat = - - let lns = key /a/ . key /b/ diff --git a/tests/modules/fail_multi_key_iter.aug b/tests/modules/fail_multi_key_iter.aug deleted file mode 100644 index c333626..0000000 --- a/tests/modules/fail_multi_key_iter.aug +++ /dev/null @@ -1,4 +0,0 @@ -module Fail_multi_key_iter = - - let lns = ( key /a/ ) * - diff --git a/tests/modules/fail_recursion_multi_keys.aug b/tests/modules/fail_recursion_multi_keys.aug deleted file mode 100644 index f6d0c3c..0000000 --- a/tests/modules/fail_recursion_multi_keys.aug +++ /dev/null @@ -1,4 +0,0 @@ -module Fail_recursion_multi_keys = - -(* This is the same as (key "a")* . store "x" *) -let rec l = key "a" . l | store "x" diff --git a/tests/modules/pass_multipart_key.aug b/tests/modules/pass_multipart_key.aug new file mode 100644 index 0000000..97b7887 --- /dev/null +++ b/tests/modules/pass_multipart_key.aug @@ -0,0 +1,10 @@ +module Pass_multipart_key = + + (* check multi key concat *) + let l1 = key /a/ . key /b/ + let l2 = ( key /a/ ) * + let rec l3 = [ key "a" . l3? ] + + (* union typecheck *) + let l4 = ([ key "a" ] . del "y" "y" ) | del "x" "x" + -- 1.7.1
_______________________________________________ augeas-devel mailing list [email protected] https://www.redhat.com/mailman/listinfo/augeas-devel
