[augeas-devel] augeas: master - Calculate if a lens's ctype is nullable
David Lutterkort
lutter at fedoraproject.org
Fri Jan 15 01:31:28 UTC 2010
Gitweb: http://git.fedorahosted.org/git/augeas.git?p=augeas.git;a=commitdiff;h=841eb40bd79d878bb7d5a95dc98d6acfd89178cc
Commit: 841eb40bd79d878bb7d5a95dc98d6acfd89178cc
Parent: d3be16488c0990d7cc397099eca1539585ab25c9
Author: David Lutterkort <lutter at redhat.com>
AuthorDate: Thu Dec 17 18:03:53 2009 -0800
Committer: David Lutterkort <lutter at redhat.com>
CommitterDate: Thu Jan 14 14:48:38 2010 -0800
Calculate if a lens's ctype is nullable
---
src/lens.c | 96 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
src/lens.h | 1 +
2 files changed, 97 insertions(+), 0 deletions(-)
diff --git a/src/lens.c b/src/lens.c
index 184c94c..67d23d1 100644
--- a/src/lens.c
+++ b/src/lens.c
@@ -218,6 +218,7 @@ struct value *lns_make_union(struct info *info,
struct lens *lens = NULL;
int consumes_value = l1->consumes_value && l2->consumes_value;
int recursive = l1->recursive || l2->recursive;
+ int ctype_nullable = l1->ctype_nullable || l2->ctype_nullable;
if (check && !recursive) {
struct value *exn = typecheck_union(info, l1, l2);
@@ -227,6 +228,8 @@ struct value *lns_make_union(struct info *info,
lens = make_lens_binop(L_UNION, info, l1, l2, regexp_union_n);
lens->consumes_value = consumes_value;
+ if (! recursive)
+ lens->ctype_nullable = ctype_nullable;
return make_lens_value(lens);
}
@@ -235,6 +238,7 @@ struct value *lns_make_concat(struct info *info,
struct lens *lens = NULL;
int consumes_value = l1->consumes_value || l2->consumes_value;
int recursive = l1->recursive || l2->recursive;
+ int ctype_nullable = l1->ctype_nullable && l2->ctype_nullable;
if (check && !recursive) {
struct value *exn = typecheck_concat(info, l1, l2);
@@ -251,6 +255,8 @@ struct value *lns_make_concat(struct info *info,
lens = make_lens_binop(L_CONCAT, info, l1, l2, regexp_concat_n);
lens->consumes_value = consumes_value;
+ if (! recursive)
+ lens->ctype_nullable = ctype_nullable;
return make_lens_value(lens);
}
@@ -307,6 +313,8 @@ struct value *lns_make_subtree(struct info *info, struct lens *l) {
lens->atype = subtree_atype(info, l->ktype, l->vtype);
lens->value = lens->key = 0;
lens->recursive = l->recursive;
+ if (! l->recursive)
+ lens->ctype_nullable = l->ctype_nullable;
return make_lens_value(lens);
}
@@ -331,6 +339,7 @@ struct value *lns_make_star(struct info *info, struct lens *l, int check) {
ltype(lens, t) = regexp_iter(info, ltype(l, t), 0, -1);
}
lens->recursive = l->recursive;
+ lens->ctype_nullable = 1;
return make_lens_value(lens);
}
@@ -361,6 +370,7 @@ struct value *lns_make_maybe(struct info *info, struct lens *l, int check) {
lens->value = l->value;
lens->key = l->key;
lens->recursive = l->recursive;
+ lens->ctype_nullable = 1;
return make_lens_value(lens);
}
@@ -468,12 +478,15 @@ struct value *lns_make_prim(enum lens_tag tag, struct info *info,
/* Set the ctype */
if (tag == L_DEL || tag == L_STORE || tag == L_KEY) {
lens->ctype = ref(regexp);
+ lens->ctype_nullable = regexp_matches_empty(lens->ctype);
} else if (tag == L_LABEL || tag == L_SEQ || tag == L_COUNTER) {
lens->ctype = regexp_make_empty(info);
+ lens->ctype_nullable = 1;
} else {
assert(0);
}
+
/* Set the ktype */
if (tag == L_SEQ) {
lens->ktype =
@@ -1844,6 +1857,83 @@ static struct value *rtn_approx(struct lens *rec, enum lens_type lt) {
goto done;
}
+static struct value *
+exn_multiple_epsilons(struct lens *lens,
+ struct lens *l1, struct lens *l2) {
+ char *fi = NULL;
+ struct value *exn = NULL;
+
+ exn = make_exn_value(ref(lens->info),
+ "more than one nullable branch in a union");
+ fi = format_info(l1->info);
+ exn_printf_line(exn, "First nullable lens: %s", fi);
+ FREE(fi);
+
+ fi = format_info(l2->info);
+ exn_printf_line(exn, "Second nullable lens: %s", fi);
+ FREE(fi);
+
+ return exn;
+}
+
+/* Update lens->ctype_nullable and return 1 if there was a change,
+ * 0 if there was none */
+static int ctype_nullable(struct lens *lens, struct value **exn) {
+ int nullable = 0;
+ int ret = 0;
+ struct lens *null_lens = NULL;
+
+ if (! lens->recursive)
+ return 0;
+
+ switch(lens->tag) {
+ case L_CONCAT:
+ nullable = 1;
+ for (int i=0; i < lens->nchildren; i++) {
+ if (ctype_nullable(lens->children[i], exn))
+ ret = 1;
+ if (! lens->children[i]->ctype_nullable)
+ nullable = 0;
+ }
+ break;
+ case L_UNION:
+ for (int i=0; i < lens->nchildren; i++) {
+ if (ctype_nullable(lens->children[i], exn))
+ ret = 1;
+ if (lens->children[i]->ctype_nullable) {
+ if (nullable) {
+ *exn = exn_multiple_epsilons(lens, null_lens,
+ lens->children[i]);
+ return 0;
+ }
+ nullable = 1;
+ null_lens = lens->children[i];
+ }
+ }
+ break;
+ case L_SUBTREE:
+ ret = ctype_nullable(lens->child, exn);
+ nullable = lens->child->ctype_nullable;
+ break;
+ case L_STAR:
+ case L_MAYBE:
+ nullable = 1;
+ break;
+ case L_REC:
+ nullable = lens->body->ctype_nullable;
+ break;
+ default:
+ assert(0);
+ }
+ if (*exn != NULL)
+ return 0;
+ if (nullable != lens->ctype_nullable) {
+ ret = 1;
+ lens->ctype_nullable = nullable;
+ }
+ return ret;
+}
+
struct value *lns_check_rec(struct info *info,
struct lens *body, struct lens *rec,
int check) {
@@ -1881,6 +1971,11 @@ struct value *lns_check_rec(struct info *info,
rec->value = rec->body->value;
rec->consumes_value = rec->body->consumes_value;
+ while(ctype_nullable(rec->body, &result));
+ if (result != NULL)
+ goto error;
+ rec->ctype_nullable = rec->body->ctype_nullable;
+
result = typecheck(rec->body, check);
if (result != NULL)
goto error;
@@ -1892,6 +1987,7 @@ struct value *lns_check_rec(struct info *info,
top->value = rec->value;
top->key = rec->key;
top->consumes_value = rec->consumes_value;
+ top->ctype_nullable = rec->ctype_nullable;
top->body = ref(body);
top->alias = rec;
rec->alias = top;
diff --git a/src/lens.h b/src/lens.h
index c5d4a55..8d2cf3f 100644
--- a/src/lens.h
+++ b/src/lens.h
@@ -78,6 +78,7 @@ struct lens {
unsigned int consumes_value : 1;
/* Flag to help avoid cycles in recursive lenses */
unsigned int rec_internal : 1;
+ unsigned int ctype_nullable : 1;
union {
/* Primitive lenses */
struct { /* L_DEL uses both */
More information about the augeas-devel
mailing list