[augeas-devel] [PATCH 2/6] Build AST while visiting the parse

[Francis Giraldeau]

The AST records the structure of the parse according to the lens tree. The
indices of the text matched is recorded for later use.
---
 src/get.c |  118 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 118 insertions(+)

diff --git a/src/get.c b/src/get.c
index 734abf6..05663a4 100644
--- a/src/get.c
+++ b/src/get.c
@@ -90,6 +90,17 @@ struct frame {
 /* Used by recursive lenses in get_rec and parse_rec */
 enum mode_t { M_GET, M_PARSE };
 
+/* Abstract Syntax Tree for recursive parse */
+struct ast {
+    struct ast         *parent;
+    struct ast        **children;
+    uint                nchildren;
+    uint                capacity;
+    struct lens        *lens;
+    uint                start;
+    uint                end;
+};
+
 struct rec_state {
     enum mode_t          mode;
     struct state        *state;
@@ -98,6 +109,7 @@ struct rec_state {
     struct frame        *frames;
     size_t               start;
     uint                 lvl;  /* Debug only */
+    struct ast          *ast;
 };
 
 #define REG_START(state) ((state)->regs->start[(state)->nreg])
@@ -109,6 +121,102 @@ struct rec_state {
 #define REG_MATCHED(state) (REG_VALID(state)                            \
                             && (state)->regs->start[(state)->nreg] >= 0)
 
+/*
+ * AST utils
+ */
+static struct ast *make_ast(struct lens *lens) {
+    struct ast *ast = NULL;
+
+    if (ALLOC(ast) < 0)
+        return NULL;
+    ast->lens = lens;
+    ast->capacity = 4;
+    if (ALLOC_N(ast->children, ast->capacity) < 0) {
+        FREE(ast);
+        return NULL;
+    }
+    return ast;
+}
+
+/* recursively free the node and all it's descendants */
+static void free_ast(struct ast *ast) {
+    int i;
+    if (ast == NULL)
+        return;
+    for (i = 0; i < ast->nchildren; i++) {
+        free_ast(ast->children[i]);
+    }
+    if (ast->children != NULL)
+        FREE(ast->children);
+    FREE(ast);
+}
+
+static struct ast *ast_root(struct ast *ast) {
+    struct ast *root = ast;
+    while(root != NULL && root->parent != NULL)
+        root = root->parent;
+    return root;
+}
+
+/* append a child to the parent ast */
+ATTRIBUTE_RETURN_CHECK
+static int ast_add_child(struct ast *parent, struct ast *child) {
+    if (parent == NULL)
+        return 0;
+    if (parent->nchildren >= parent->capacity) {
+        int ret = REALLOC_N(parent->children, parent->capacity * 2);
+        if (ret < 0)
+            return -1;
+        parent->capacity = parent->capacity * 2;
+    }
+    parent->children[parent->nchildren++] = child;
+    child->parent = parent;
+    return 0;
+}
+
+static void ast_set(struct ast *ast, uint start, uint end) {
+    if (ast == NULL)
+        return;
+    ast->start = start;
+    ast->end = end;
+}
+
+static struct ast *ast_append(struct rec_state *rec_state, struct lens *lens,
+                           uint start, uint end) {
+    int ret;
+    struct ast *child;
+
+    child = make_ast(lens);
+    ERR_NOMEM(child == NULL, rec_state->state->info);
+    ast_set(child, start, end);
+    ret = ast_add_child(rec_state->ast, child);
+    ERR_NOMEM(ret < 0, rec_state->state->info)
+    return child;
+ error:
+    free_ast(child);
+    return NULL;
+}
+
+/* pop the ast from one level if parent is not null */
+static void ast_pop(struct rec_state *rec_state) {
+    if (rec_state->ast != NULL && rec_state->ast->parent != NULL)
+        rec_state->ast = rec_state->ast->parent;
+}
+
+static void print_ast(struct ast *ast, int lvl) {
+    int i;
+    char *lns;
+    if (ast == NULL)
+        return;
+    for (i = 0; i < lvl; i++) fputs(" ", stdout);
+    lns = format_lens(ast->lens);
+    printf("%d..%d %s\n", ast->start, ast->end, lns);
+    free(lns);
+    for (i = 0; i < ast->nchildren; i++) {
+        print_ast(ast->children[i], lvl + 1);
+    }
+}
+
 static void get_error(struct state *state, struct lens *lens,
                       const char *format, ...)
     ATTRIBUTE_FORMAT(printf, 3, 4);
@@ -871,6 +979,7 @@ static void visit_terminal(struct lens *lens, size_t start, size_t end,
         get_terminal(top, lens, state);
     else
         parse_terminal(top, lens, state);
+    ast_append(rec_state, lens, start, end);
     free_regs(state);
     state->regs = old_regs;
     state->nreg = old_nreg;
@@ -882,6 +991,7 @@ static void visit_enter(struct lens *lens,
                         void *data) {
     struct rec_state *rec_state = data;
     struct state *state = rec_state->state;
+    struct ast *child;
 
     if (state->error != NULL)
         return;
@@ -904,6 +1014,9 @@ static void visit_enter(struct lens *lens,
             ERR_NOMEM(state->span == NULL, state->info);
         }
     }
+    child = ast_append(rec_state, lens, start, end);
+    if (child != NULL)
+        rec_state->ast = child;
  error:
     return;
 }
@@ -1082,6 +1195,7 @@ static void visit_exit(struct lens *lens,
     } else {
         top_frame(rec_state)->lens = lens;
     }
+    ast_pop(rec_state);
  error:
     return;
 }
@@ -1151,12 +1265,16 @@ static struct frame *rec_process(enum mode_t mode, struct lens *lens,
     }
 
  done:
+    if (debugging("cf.get.ast"))
+        print_ast(rec_state.ast, 0);
     state->regs = old_regs;
     state->nreg = old_nreg;
     jmt_free_parse(visitor.parse);
+    free_ast(rec_state.ast);
     return rec_state.frames;
  error:
 
+    rec_state.ast = ast_root(rec_state.ast);
     for(i = 0; i < rec_state.fused; i++) {
         f = nth_frame(&rec_state, i);
         FREE(f->key);
-- 
1.7.9.5