[augeas-devel] [PATCH] Flatten the tree of lenses

[David Lutterkort]

3 files changed, 109 insertions(+), 13 deletions(-)
src/lens.c   |   74 +++++++++++++++++++++++++++++++++++++++++++++++-----------
src/regexp.c |   42 ++++++++++++++++++++++++++++++++
src/syntax.h |    6 ++++


# HG changeset patch
# User David Lutterkort <dlutter at redhat.com>
# Date 1216919484 25200
# Node ID 27f24cafe6ec2a075a75ef5e89d06831c4554924
# Parent  57f0a0894bf42dcaa1f5b90b5378cbd614ad07d9
Flatten the tree of lenses

For union and concat, we used to store multiple unions/concats in a binary
tree. Now, the tree is flattened and a string of concats is stored as one
lens.

diff -r 57f0a0894bf4 -r 27f24cafe6ec src/lens.c
--- a/src/lens.c	Thu Jul 24 10:08:26 2008 -0700
+++ b/src/lens.c	Thu Jul 24 10:11:24 2008 -0700
@@ -59,16 +59,68 @@
     return lens;
 }
 
+typedef struct regexp *regexp_combinator(struct info *, int, struct regexp **);
+
 static struct lens *make_lens_binop(enum lens_tag tag, struct info *info,
-                                    struct lens *l1, struct lens *l2) {
+                                    struct lens *l1, struct lens *l2,
+                                    regexp_combinator *combinator) {
     struct lens *lens = make_lens(tag, info);
-    CALLOC(lens->children, 2);
-    lens->nchildren = 2;
-    lens->children[0] = l1;
-    lens->children[1] = l2;
-    lens->value = l1->value || l2->value;
-    lens->key = l1->key || l2->key;
+    int n1 = (l1->tag == tag) ? l1->nchildren : 1;
+    struct regexp **types = NULL;
+
+    if (lens == NULL)
+        goto error;
+
+    lens->nchildren = n1;
+    lens->nchildren += (l2->tag == tag) ? l2->nchildren : 1;
+
+    if (ALLOC_N(lens->children, lens->nchildren) < 0) {
+        lens->nchildren = 0;
+        goto error;
+    }
+
+    if (l1->tag == tag) {
+        for (int i=0; i < l1->nchildren; i++)
+            lens->children[i] = ref(l1->children[i]);
+        unref(l1, lens);
+    } else {
+        lens->children[0] = l1;
+    }
+
+    if (l2->tag == tag) {
+        for (int i=0; i < l2->nchildren; i++)
+            lens->children[n1 + i] = ref(l2->children[i]);
+        unref(l2, lens);
+    } else {
+        lens->children[n1] = l2;
+    }
+
+    for (int i=0; i < lens->nchildren; i++) {
+        lens->value = lens->value || lens->children[i]->value;
+        lens->key = lens->key || lens->children[i]->key;
+    }
+
+    if (ALLOC_N(types, lens->nchildren) < 0)
+        goto error;
+
+    for (int i=0; i < lens->nchildren; i++)
+        types[i] = lens->children[i]->ctype;
+    lens->ctype = (*combinator)(info, lens->nchildren, types);
+
+    for (int i=0; i < lens->nchildren; i++)
+        types[i] = lens->children[i]->atype;
+    lens->atype = (*combinator)(info, lens->nchildren, types);
+
+    FREE(types);
+
+    for (int i=0; i < lens->nchildren; i++)
+        assert(tag != lens->children[i]->tag);
+
     return lens;
+ error:
+    unref(lens, lens);
+    FREE(types);
+    return NULL;
 }
 
 static struct value *make_lens_value(struct lens *lens) {
@@ -88,9 +140,7 @@
             return exn;
     }
 
-    lens = make_lens_binop(L_UNION, info, l1, l2);
-    lens->ctype = regexp_union(info, l1->ctype, l2->ctype);
-    lens->atype = regexp_union(info, l1->atype, l2->atype);
+    lens = make_lens_binop(L_UNION, info, l1, l2, regexp_union_n);
     return make_lens_value(lens);
 }
 
@@ -111,9 +161,7 @@
         return make_exn_value(info, "Multiple keys/labels in concat");
     }
 
-    lens = make_lens_binop(L_CONCAT, info, l1, l2);
-    lens->ctype = regexp_concat(info, l1->ctype, l2->ctype);
-    lens->atype = regexp_concat(info, l1->atype, l2->atype);
+    lens = make_lens_binop(L_CONCAT, info, l1, l2, regexp_concat_n);
     return make_lens_value(lens);
 }
 
diff -r 57f0a0894bf4 -r 27f24cafe6ec src/regexp.c
--- a/src/regexp.c	Thu Jul 24 10:08:26 2008 -0700
+++ b/src/regexp.c	Thu Jul 24 10:11:24 2008 -0700
@@ -102,6 +102,28 @@
 }
 
 struct regexp *
+regexp_union_n(struct info *info, int n, struct regexp **r) {
+    size_t len = 0;
+    char *pat, *p;
+
+    for (int i=0; i < n; i++)
+        len += strlen(r[i]->pattern->str) + 2;
+
+    if (ALLOC_N(pat, len + (n-1) + 1) < 0)
+        return NULL;
+
+    p = pat;
+    for (int i=0; i < n; i++) {
+        if (i > 0)
+            *p++ = '|';
+        *p++ = '(';
+        p = stpcpy(p, r[i]->pattern->str);
+        *p++ = ')';
+    }
+    return make_regexp(info, pat);
+}
+
+struct regexp *
 regexp_concat(struct info *info, struct regexp *r1, struct regexp *r2) {
     const char *p1 = r1->pattern->str;
     const char *p2 = r2->pattern->str;
@@ -110,6 +132,26 @@
     if (asprintf(&s, "(%s)(%s)", p1, p2) == -1)
         return NULL;
     return make_regexp(info, s);
+}
+
+struct regexp *
+regexp_concat_n(struct info *info, int n, struct regexp **r) {
+    size_t len = 0;
+    char *pat, *p;
+
+    for (int i=0; i < n; i++)
+        len += strlen(r[i]->pattern->str) + 2;
+
+    if (ALLOC_N(pat, len+1) < 0)
+        return NULL;
+
+    p = pat;
+    for (int i=0; i < n; i++) {
+        *p++ = '(';
+        p = stpcpy(p, r[i]->pattern->str);
+        *p++ = ')';
+    }
+    return make_regexp(info, pat);
 }
 
 struct regexp *
diff -r 57f0a0894bf4 -r 27f24cafe6ec src/syntax.h
--- a/src/syntax.h	Thu Jul 24 10:08:26 2008 -0700
+++ b/src/syntax.h	Thu Jul 24 10:11:24 2008 -0700
@@ -178,6 +178,12 @@
 
 struct regexp *
 regexp_concat(struct info *, struct regexp *r1, struct regexp *r2);
+
+struct regexp *
+regexp_union_n(struct info *, int n, struct regexp **r);
+
+struct regexp *
+regexp_concat_n(struct info *, int n, struct regexp **r);
 
 struct regexp *
 regexp_iter(struct info *info, struct regexp *r, int min, int max);