1 files changed, 446 insertions, 0 deletions
diff --git a/node.c b/node.c
new file mode 100644
index 0000000000..5d00823eb6
--- /dev/null
+++ b/node.c
@@ -0,0 +1,446 @@
+/**********************************************************************
+
+  node.c - ruby node tree
+
+  $Author: mame $
+  created at: 09/12/06 21:23:44 JST
+
+  Copyright (C) 2009 Yusuke Endoh
+
+**********************************************************************/
+
+#ifdef UNIVERSAL_PARSER
+#include <stddef.h>
+#include "node.h"
+#include "rubyparser.h"
+#endif
+
+#include "internal/variable.h"
+
+#define NODE_BUF_DEFAULT_SIZE (sizeof(struct RNode) * 16)
+
+static void
+init_node_buffer_elem(node_buffer_elem_t *nbe, size_t allocated, void *xmalloc(size_t))
+{
+    nbe->allocated = allocated;
+    nbe->used = 0;
+    nbe->len = 0;
+    nbe->nodes = xmalloc(allocated / sizeof(struct RNode) * sizeof(struct RNode *)); /* All node requires at least RNode */
+}
+
+static void
+init_node_buffer_list(node_buffer_list_t *nb, node_buffer_elem_t *head, void *xmalloc(size_t))
+{
+    init_node_buffer_elem(head, NODE_BUF_DEFAULT_SIZE, xmalloc);
+    nb->head = nb->last = head;
+    nb->head->next = NULL;
+}
+
+#ifdef UNIVERSAL_PARSER
+#define ruby_xmalloc config->malloc
+#endif
+
+#ifdef UNIVERSAL_PARSER
+static node_buffer_t *
+rb_node_buffer_new(const rb_parser_config_t *config)
+#else
+static node_buffer_t *
+rb_node_buffer_new(void)
+#endif
+{
+    const size_t bucket_size = offsetof(node_buffer_elem_t, buf) + NODE_BUF_DEFAULT_SIZE;
+    const size_t alloc_size = sizeof(node_buffer_t) + (bucket_size);
+    STATIC_ASSERT(
+        integer_overflow,
+        offsetof(node_buffer_elem_t, buf) + NODE_BUF_DEFAULT_SIZE
+        > sizeof(node_buffer_t) + sizeof(node_buffer_elem_t));
+    node_buffer_t *nb = ruby_xmalloc(alloc_size);
+    init_node_buffer_list(&nb->buffer_list, (node_buffer_elem_t*)&nb[1], ruby_xmalloc);
+    nb->local_tables = 0;
+    nb->tokens = 0;
+    return nb;
+}
+
+#ifdef UNIVERSAL_PARSER
+#undef ruby_xmalloc
+#define ruby_xmalloc ast->config->malloc
+#undef xfree
+#define xfree ast->config->free
+#define rb_xmalloc_mul_add ast->config->xmalloc_mul_add
+#define ruby_xrealloc(var,size) (ast->config->realloc_n((void *)var, 1, size))
+#endif
+
+typedef void node_itr_t(rb_ast_t *ast, void *ctx, NODE *node);
+static void iterate_node_values(rb_ast_t *ast, node_buffer_list_t *nb, node_itr_t * func, void *ctx);
+
+void
+rb_node_init(NODE *n, enum node_type type)
+{
+    RNODE(n)->flags = 0;
+    nd_init_type(RNODE(n), type);
+    RNODE(n)->nd_loc.beg_pos.lineno = 0;
+    RNODE(n)->nd_loc.beg_pos.column = 0;
+    RNODE(n)->nd_loc.end_pos.lineno = 0;
+    RNODE(n)->nd_loc.end_pos.column = 0;
+    RNODE(n)->node_id = -1;
+}
+
+const char *
+rb_node_name(int node)
+{
+    switch (node) {
+#include "node_name.inc"
+      default:
+        return 0;
+    }
+}
+
+#ifdef UNIVERSAL_PARSER
+const char *
+ruby_node_name(int node)
+{
+    return rb_node_name(node);
+}
+#else
+const char *
+ruby_node_name(int node)
+{
+    const char *name = rb_node_name(node);
+
+    if (!name) rb_bug("unknown node: %d", node);
+    return name;
+}
+#endif
+
+static void
+node_buffer_list_free(rb_ast_t *ast, node_buffer_list_t * nb)
+{
+    node_buffer_elem_t *nbe = nb->head;
+    while (nbe != nb->last) {
+        void *buf = nbe;
+        xfree(nbe->nodes);
+        nbe = nbe->next;
+        xfree(buf);
+    }
+
+    /* The last node_buffer_elem_t is allocated in the node_buffer_t, so we
+     * only need to free the nodes. */
+    xfree(nbe->nodes);
+}
+
+struct rb_ast_local_table_link {
+    struct rb_ast_local_table_link *next;
+    // struct rb_ast_id_table {
+    int size;
+    ID ids[FLEX_ARY_LEN];
+    // }
+};
+
+static void
+parser_string_free(rb_ast_t *ast, rb_parser_string_t *str)
+{
+    if (!str) return;
+    xfree(str->ptr);
+    xfree(str);
+}
+
+static void
+parser_ast_token_free(rb_ast_t *ast, rb_parser_ast_token_t *token)
+{
+    if (!token) return;
+    parser_string_free(ast, token->str);
+    xfree(token);
+}
+
+static void
+parser_tokens_free(rb_ast_t *ast, rb_parser_ary_t *tokens)
+{
+    for (long i = 0; i < tokens->len; i++) {
+        parser_ast_token_free(ast, tokens->data[i]);
+    }
+    xfree(tokens->data);
+    xfree(tokens);
+}
+
+static void
+parser_nodes_free(rb_ast_t *ast, rb_parser_ary_t *nodes)
+{
+    /* Do nothing for nodes because nodes are freed when rb_ast_t is freed */
+    xfree(nodes->data);
+    xfree(nodes);
+}
+
+static void
+free_ast_value(rb_ast_t *ast, void *ctx, NODE *node)
+{
+    switch (nd_type(node)) {
+      case NODE_STR:
+        parser_string_free(ast, RNODE_STR(node)->string);
+        break;
+      case NODE_DSTR:
+        parser_string_free(ast, RNODE_DSTR(node)->string);
+        break;
+      case NODE_XSTR:
+        parser_string_free(ast, RNODE_XSTR(node)->string);
+        break;
+      case NODE_DXSTR:
+        parser_string_free(ast, RNODE_DXSTR(node)->string);
+        break;
+      case NODE_SYM:
+        parser_string_free(ast, RNODE_SYM(node)->string);
+        break;
+      case NODE_REGX:
+      case NODE_MATCH:
+        parser_string_free(ast, RNODE_REGX(node)->string);
+        break;
+      case NODE_DSYM:
+        parser_string_free(ast, RNODE_DSYM(node)->string);
+        break;
+      case NODE_DREGX:
+        parser_string_free(ast, RNODE_DREGX(node)->string);
+        break;
+      case NODE_FILE:
+        parser_string_free(ast, RNODE_FILE(node)->path);
+        break;
+      case NODE_INTEGER:
+        xfree(RNODE_INTEGER(node)->val);
+        break;
+      case NODE_FLOAT:
+        xfree(RNODE_FLOAT(node)->val);
+        break;
+      case NODE_RATIONAL:
+        xfree(RNODE_RATIONAL(node)->val);
+        break;
+      case NODE_IMAGINARY:
+        xfree(RNODE_IMAGINARY(node)->val);
+        break;
+      case NODE_UNDEF:
+        parser_nodes_free(ast, RNODE_UNDEF(node)->nd_undefs);
+        break;
+      default:
+        break;
+    }
+}
+
+static void
+rb_node_buffer_free(rb_ast_t *ast, node_buffer_t *nb)
+{
+    if (nb->tokens) {
+        parser_tokens_free(ast, nb->tokens);
+    }
+    iterate_node_values(ast, &nb->buffer_list, free_ast_value, NULL);
+    node_buffer_list_free(ast, &nb->buffer_list);
+    struct rb_ast_local_table_link *local_table = nb->local_tables;
+    while (local_table) {
+        struct rb_ast_local_table_link *next_table = local_table->next;
+        xfree(local_table);
+        local_table = next_table;
+    }
+    xfree(nb);
+}
+
+#define buf_add_offset(nbe, offset) ((char *)(nbe->buf) + (offset))
+
+static NODE *
+ast_newnode_in_bucket(rb_ast_t *ast, node_buffer_list_t *nb, size_t size, size_t alignment)
+{
+    size_t padding;
+    NODE *ptr;
+
+    padding = alignment - (size_t)buf_add_offset(nb->head, nb->head->used) % alignment;
+    padding = padding == alignment ? 0 : padding;
+
+    if (nb->head->used + size + padding > nb->head->allocated) {
+        size_t n = nb->head->allocated * 2;
+        node_buffer_elem_t *nbe;
+        nbe = rb_xmalloc_mul_add(n, sizeof(char *), offsetof(node_buffer_elem_t, buf));
+        init_node_buffer_elem(nbe, n, ruby_xmalloc);
+        nbe->next = nb->head;
+        nb->head = nbe;
+        padding = 0; /* malloc returns aligned address then no need to add padding */
+    }
+
+    ptr = (NODE *)buf_add_offset(nb->head, nb->head->used + padding);
+    nb->head->used += (size + padding);
+    nb->head->nodes[nb->head->len++] = ptr;
+    return ptr;
+}
+
+NODE *
+rb_ast_newnode(rb_ast_t *ast, enum node_type type, size_t size, size_t alignment)
+{
+    node_buffer_t *nb = ast->node_buffer;
+    node_buffer_list_t *bucket = &nb->buffer_list;
+    return ast_newnode_in_bucket(ast, bucket, size, alignment);
+}
+
+rb_ast_id_table_t *
+rb_ast_new_local_table(rb_ast_t *ast, int size)
+{
+    size_t alloc_size = sizeof(struct rb_ast_local_table_link) + size * sizeof(ID);
+    struct rb_ast_local_table_link *link = ruby_xmalloc(alloc_size);
+    link->next = ast->node_buffer->local_tables;
+    ast->node_buffer->local_tables = link;
+    link->size = size;
+
+    return (rb_ast_id_table_t *) &link->size;
+}
+
+rb_ast_id_table_t *
+rb_ast_resize_latest_local_table(rb_ast_t *ast, int size)
+{
+    struct rb_ast_local_table_link *link = ast->node_buffer->local_tables;
+    size_t alloc_size = sizeof(struct rb_ast_local_table_link) + size * sizeof(ID);
+    link = ruby_xrealloc(link, alloc_size);
+    ast->node_buffer->local_tables = link;
+    link->size = size;
+
+    return (rb_ast_id_table_t *) &link->size;
+}
+
+void
+rb_ast_delete_node(rb_ast_t *ast, NODE *n)
+{
+    (void)ast;
+    (void)n;
+    /* should we implement freelist? */
+}
+
+#ifdef UNIVERSAL_PARSER
+rb_ast_t *
+rb_ast_new(const rb_parser_config_t *config)
+{
+    node_buffer_t *nb = rb_node_buffer_new(config);
+    rb_ast_t *ast = (rb_ast_t *)config->calloc(1, sizeof(rb_ast_t));
+    ast->config = config;
+    ast->node_buffer = nb;
+    return ast;
+}
+#else
+rb_ast_t *
+rb_ast_new(void)
+{
+    node_buffer_t *nb = rb_node_buffer_new();
+    rb_ast_t *ast = ruby_xcalloc(1, sizeof(rb_ast_t));
+    ast->node_buffer = nb;
+    return ast;
+}
+#endif
+
+static void
+iterate_buffer_elements(rb_ast_t *ast, node_buffer_elem_t *nbe, long len, node_itr_t *func, void *ctx)
+{
+    long cursor;
+    for (cursor = 0; cursor < len; cursor++) {
+        func(ast, ctx, nbe->nodes[cursor]);
+    }
+}
+
+static void
+iterate_node_values(rb_ast_t *ast, node_buffer_list_t *nb, node_itr_t * func, void *ctx)
+{
+    node_buffer_elem_t *nbe = nb->head;
+
+    while (nbe) {
+        iterate_buffer_elements(ast, nbe, nbe->len, func, ctx);
+        nbe = nbe->next;
+    }
+}
+
+static void
+script_lines_free(rb_ast_t *ast, rb_parser_ary_t *script_lines)
+{
+    if (!script_lines) return;
+    for (long i = 0; i < script_lines->len; i++) {
+        parser_string_free(ast, (rb_parser_string_t *)script_lines->data[i]);
+    }
+    xfree(script_lines->data);
+    xfree(script_lines);
+}
+
+void
+rb_ast_free(rb_ast_t *ast)
+{
+    rb_ast_dispose(ast);
+    xfree(ast);
+}
+
+static size_t
+buffer_list_size(node_buffer_list_t *nb)
+{
+    size_t size = 0;
+    node_buffer_elem_t *nbe = nb->head;
+    while (nbe != nb->last) {
+        size += offsetof(node_buffer_elem_t, buf) + nbe->used;
+        nbe = nbe->next;
+    }
+    return size;
+}
+
+size_t
+rb_ast_memsize(const rb_ast_t *ast)
+{
+    size_t size = sizeof(rb_ast_t);
+    node_buffer_t *nb = ast->node_buffer;
+    rb_parser_ary_t *tokens = NULL;
+    struct rb_ast_local_table_link *link = NULL;
+    rb_parser_ary_t *script_lines = ast->body.script_lines;
+
+    long i;
+
+    if (nb) {
+        size += sizeof(node_buffer_t);
+        size += buffer_list_size(&nb->buffer_list);
+        link = nb->local_tables;
+        tokens = nb->tokens;
+    }
+
+    while (link) {
+        size += sizeof(struct rb_ast_local_table_link);
+        size += link->size * sizeof(ID);
+        link = link->next;
+    }
+
+    if (tokens) {
+        size += sizeof(rb_parser_ary_t);
+        for (i = 0; i < tokens->len; i++) {
+            size += sizeof(rb_parser_ast_token_t);
+            rb_parser_ast_token_t *token = tokens->data[i];
+            size += sizeof(rb_parser_string_t);
+            size += token->str->len + 1;
+        }
+    }
+
+    if (script_lines) {
+        size += sizeof(rb_parser_ary_t);
+        for (i = 0; i < script_lines->len; i++) {
+            size += sizeof(rb_parser_string_t);
+            size += ((rb_parser_string_t *)script_lines->data[i])->len + 1;
+        }
+    }
+
+    return size;
+}
+
+void
+rb_ast_dispose(rb_ast_t *ast)
+{
+    if (ast && ast->node_buffer) {
+        script_lines_free(ast, ast->body.script_lines);
+        ast->body.script_lines = NULL;
+        rb_node_buffer_free(ast, ast->node_buffer);
+        ast->node_buffer = 0;
+    }
+}
+
+VALUE
+rb_node_set_type(NODE *n, enum node_type t)
+{
+    return nd_init_type(n, t);
+}
+
+enum node_type
+rb_node_get_type(const NODE *n)
+{
+    return (enum node_type)nd_type(n);
+}