node.c

   1 /**********************************************************************
   2
   3   node.c - ruby node tree
   4
   5   $Author: mame $
   6   created at: 09/12/06 21:23:44 JST
   7
   8   Copyright (C) 2009 Yusuke Endoh
   9
  10 **********************************************************************/
  11
  12 #ifdef UNIVERSAL_PARSER
  13 #include <stddef.h>
  14 #include "node.h"
  15 #include "rubyparser.h"
  16 #endif
  17
  18 #include "internal/variable.h"
  19
  20 #define NODE_BUF_DEFAULT_SIZE (sizeof(struct RNode) * 16)
  21
  22 static void
  23 init_node_buffer_elem(node_buffer_elem_t *nbe, size_t allocated, void *xmalloc(size_t))
  24 {
  25     nbe->allocated = allocated;
  26     nbe->used = 0;
  27     nbe->len = 0;
  28     nbe->nodes = xmalloc(allocated / sizeof(struct RNode) * sizeof(struct RNode *)); /* All node requires at least RNode */
  29 }
  30
  31 static void
  32 init_node_buffer_list(node_buffer_list_t *nb, node_buffer_elem_t *head, void *xmalloc(size_t))
  33 {
  34     init_node_buffer_elem(head, NODE_BUF_DEFAULT_SIZE, xmalloc);
  35     nb->head = nb->last = head;
  36     nb->head->next = NULL;
  37 }
  38
  39 #ifdef UNIVERSAL_PARSER
  40 #define ruby_xmalloc config->malloc
  41 #endif
  42
  43 #ifdef UNIVERSAL_PARSER
  44 static node_buffer_t *
  45 rb_node_buffer_new(const rb_parser_config_t *config)
  46 #else
  47 static node_buffer_t *
  48 rb_node_buffer_new(void)
  49 #endif
  50 {
  51     const size_t bucket_size = offsetof(node_buffer_elem_t, buf) + NODE_BUF_DEFAULT_SIZE;
  52     const size_t alloc_size = sizeof(node_buffer_t) + (bucket_size);
  53     STATIC_ASSERT(
  54         integer_overflow,
  55         offsetof(node_buffer_elem_t, buf) + NODE_BUF_DEFAULT_SIZE
  56         > sizeof(node_buffer_t) + sizeof(node_buffer_elem_t));
  57     node_buffer_t *nb = ruby_xmalloc(alloc_size);
  58     init_node_buffer_list(&nb->buffer_list, (node_buffer_elem_t*)&nb[1], ruby_xmalloc);
  59     nb->local_tables = 0;
  60     nb->tokens = 0;
  61     return nb;
  62 }
  63
  64 #ifdef UNIVERSAL_PARSER
  65 #undef ruby_xmalloc
  66 #define ruby_xmalloc ast->config->malloc
  67 #undef xfree
  68 #define xfree ast->config->free
  69 #define rb_xmalloc_mul_add ast->config->xmalloc_mul_add
  70 #define ruby_xrealloc(var,size) (ast->config->realloc_n((void *)var, 1, size))
  71 #endif
  72
  73 typedef void node_itr_t(rb_ast_t *ast, void *ctx, NODE *node);
  74 static void iterate_node_values(rb_ast_t *ast, node_buffer_list_t *nb, node_itr_t * func, void *ctx);
  75
  76 void
  77 rb_node_init(NODE *n, enum node_type type)
  78 {
  79     RNODE(n)->flags = 0;
  80     nd_init_type(RNODE(n), type);
  81     RNODE(n)->nd_loc.beg_pos.lineno = 0;
  82     RNODE(n)->nd_loc.beg_pos.column = 0;
  83     RNODE(n)->nd_loc.end_pos.lineno = 0;
  84     RNODE(n)->nd_loc.end_pos.column = 0;
  85     RNODE(n)->node_id = -1;
  86 }
  87
  88 const char *
  89 rb_node_name(int node)
  90 {
  91     switch (node) {
  92 #include "node_name.inc"
  93       default:
  94         return 0;
  95     }
  96 }
  97
  98 #ifdef UNIVERSAL_PARSER
  99 const char *
 100 ruby_node_name(int node)
 101 {
 102     return rb_node_name(node);
 103 }
 104 #else
 105 const char *
 106 ruby_node_name(int node)
 107 {
 108     const char *name = rb_node_name(node);
 109
 110     if (!name) rb_bug("unknown node: %d", node);
 111     return name;
 112 }
 113 #endif
 114
 115 static void
 116 node_buffer_list_free(rb_ast_t *ast, node_buffer_list_t * nb)
 117 {
 118     node_buffer_elem_t *nbe = nb->head;
 119     while (nbe != nb->last) {
 120         void *buf = nbe;
 121         xfree(nbe->nodes);
 122         nbe = nbe->next;
 123         xfree(buf);
 124     }
 125
 126     /* The last node_buffer_elem_t is allocated in the node_buffer_t, so we
 127      * only need to free the nodes. */
 128     xfree(nbe->nodes);
 129 }
 130
 131 struct rb_ast_local_table_link {
 132     struct rb_ast_local_table_link *next;
 133     // struct rb_ast_id_table {
 134     int size;
 135     ID ids[FLEX_ARY_LEN];
 136     // }
 137 };
 138
 139 static void
 140 parser_string_free(rb_ast_t *ast, rb_parser_string_t *str)
 141 {
 142     if (!str) return;
 143     xfree(str->ptr);
 144     xfree(str);
 145 }
 146
 147 static void
 148 parser_ast_token_free(rb_ast_t *ast, rb_parser_ast_token_t *token)
 149 {
 150     if (!token) return;
 151     parser_string_free(ast, token->str);
 152     xfree(token);
 153 }
 154
 155 static void
 156 parser_tokens_free(rb_ast_t *ast, rb_parser_ary_t *tokens)
 157 {
 158     for (long i = 0; i < tokens->len; i++) {
 159         parser_ast_token_free(ast, tokens->data[i]);
 160     }
 161     xfree(tokens->data);
 162     xfree(tokens);
 163 }
 164
 165 static void
 166 free_ast_value(rb_ast_t *ast, void *ctx, NODE *node)
 167 {
 168     switch (nd_type(node)) {
 169       case NODE_STR:
 170         parser_string_free(ast, RNODE_STR(node)->string);
 171         break;
 172       case NODE_DSTR:
 173         parser_string_free(ast, RNODE_DSTR(node)->string);
 174         break;
 175       case NODE_XSTR:
 176         parser_string_free(ast, RNODE_XSTR(node)->string);
 177         break;
 178       case NODE_DXSTR:
 179         parser_string_free(ast, RNODE_DXSTR(node)->string);
 180         break;
 181       case NODE_SYM:
 182         parser_string_free(ast, RNODE_SYM(node)->string);
 183         break;
 184       case NODE_REGX:
 185       case NODE_MATCH:
 186         parser_string_free(ast, RNODE_REGX(node)->string);
 187         break;
 188       case NODE_DSYM:
 189         parser_string_free(ast, RNODE_DSYM(node)->string);
 190         break;
 191       case NODE_DREGX:
 192         parser_string_free(ast, RNODE_DREGX(node)->string);
 193         break;
 194       case NODE_FILE:
 195         parser_string_free(ast, RNODE_FILE(node)->path);
 196         break;
 197       case NODE_INTEGER:
 198         xfree(RNODE_INTEGER(node)->val);
 199         break;
 200       case NODE_FLOAT:
 201         xfree(RNODE_FLOAT(node)->val);
 202         break;
 203       case NODE_RATIONAL:
 204         xfree(RNODE_RATIONAL(node)->val);
 205         break;
 206       case NODE_IMAGINARY:
 207         xfree(RNODE_IMAGINARY(node)->val);
 208         break;
 209       default:
 210         break;
 211     }
 212 }
 213
 214 static void
 215 rb_node_buffer_free(rb_ast_t *ast, node_buffer_t *nb)
 216 {
 217     if (nb && nb->tokens) {
 218         parser_tokens_free(ast, nb->tokens);
 219     }
 220     iterate_node_values(ast, &nb->buffer_list, free_ast_value, NULL);
 221     node_buffer_list_free(ast, &nb->buffer_list);
 222     struct rb_ast_local_table_link *local_table = nb->local_tables;
 223     while (local_table) {
 224         struct rb_ast_local_table_link *next_table = local_table->next;
 225         xfree(local_table);
 226         local_table = next_table;
 227     }
 228     xfree(nb);
 229 }
 230
 231 #define buf_add_offset(nbe, offset) ((char *)(nbe->buf) + (offset))
 232
 233 static NODE *
 234 ast_newnode_in_bucket(rb_ast_t *ast, node_buffer_list_t *nb, size_t size, size_t alignment)
 235 {
 236     size_t padding;
 237     NODE *ptr;
 238
 239     padding = alignment - (size_t)buf_add_offset(nb->head, nb->head->used) % alignment;
 240     padding = padding == alignment ? 0 : padding;
 241
 242     if (nb->head->used + size + padding > nb->head->allocated) {
 243         size_t n = nb->head->allocated * 2;
 244         node_buffer_elem_t *nbe;
 245         nbe = rb_xmalloc_mul_add(n, sizeof(char *), offsetof(node_buffer_elem_t, buf));
 246         init_node_buffer_elem(nbe, n, ruby_xmalloc);
 247         nbe->next = nb->head;
 248         nb->head = nbe;
 249         padding = 0; /* malloc returns aligned address then no need to add padding */
 250     }
 251
 252     ptr = (NODE *)buf_add_offset(nb->head, nb->head->used + padding);
 253     nb->head->used += (size + padding);
 254     nb->head->nodes[nb->head->len++] = ptr;
 255     return ptr;
 256 }
 257
 258 NODE *
 259 rb_ast_newnode(rb_ast_t *ast, enum node_type type, size_t size, size_t alignment)
 260 {
 261     node_buffer_t *nb = ast->node_buffer;
 262     node_buffer_list_t *bucket = &nb->buffer_list;
 263     return ast_newnode_in_bucket(ast, bucket, size, alignment);
 264 }
 265
 266 rb_ast_id_table_t *
 267 rb_ast_new_local_table(rb_ast_t *ast, int size)
 268 {
 269     size_t alloc_size = sizeof(struct rb_ast_local_table_link) + size * sizeof(ID);
 270     struct rb_ast_local_table_link *link = ruby_xmalloc(alloc_size);
 271     link->next = ast->node_buffer->local_tables;
 272     ast->node_buffer->local_tables = link;
 273     link->size = size;
 274
 275     return (rb_ast_id_table_t *) &link->size;
 276 }
 277
 278 rb_ast_id_table_t *
 279 rb_ast_resize_latest_local_table(rb_ast_t *ast, int size)
 280 {
 281     struct rb_ast_local_table_link *link = ast->node_buffer->local_tables;
 282     size_t alloc_size = sizeof(struct rb_ast_local_table_link) + size * sizeof(ID);
 283     link = ruby_xrealloc(link, alloc_size);
 284     ast->node_buffer->local_tables = link;
 285     link->size = size;
 286
 287     return (rb_ast_id_table_t *) &link->size;
 288 }
 289
 290 void
 291 rb_ast_delete_node(rb_ast_t *ast, NODE *n)
 292 {
 293     (void)ast;
 294     (void)n;
 295     /* should we implement freelist? */
 296 }
 297
 298 #ifdef UNIVERSAL_PARSER
 299 rb_ast_t *
 300 rb_ast_new(const rb_parser_config_t *config)
 301 {
 302     node_buffer_t *nb = rb_node_buffer_new(config);
 303     rb_ast_t *ast = (rb_ast_t *)config->calloc(1, sizeof(rb_ast_t));
 304     ast->config = config;
 305     ast->node_buffer = nb;
 306     return ast;
 307 }
 308 #else
 309 rb_ast_t *
 310 rb_ast_new(void)
 311 {
 312     node_buffer_t *nb = rb_node_buffer_new();
 313     rb_ast_t *ast = ruby_xcalloc(1, sizeof(rb_ast_t));
 314     ast->node_buffer = nb;
 315     return ast;
 316 }
 317 #endif
 318
 319 static void
 320 iterate_buffer_elements(rb_ast_t *ast, node_buffer_elem_t *nbe, long len, node_itr_t *func, void *ctx)
 321 {
 322     long cursor;
 323     for (cursor = 0; cursor < len; cursor++) {
 324         func(ast, ctx, nbe->nodes[cursor]);
 325     }
 326 }
 327
 328 static void
 329 iterate_node_values(rb_ast_t *ast, node_buffer_list_t *nb, node_itr_t * func, void *ctx)
 330 {
 331     node_buffer_elem_t *nbe = nb->head;
 332
 333     while (nbe) {
 334         iterate_buffer_elements(ast, nbe, nbe->len, func, ctx);
 335         nbe = nbe->next;
 336     }
 337 }
 338
 339 static void
 340 script_lines_free(rb_ast_t *ast, rb_parser_ary_t *script_lines)
 341 {
 342     if (!script_lines) return;
 343     for (long i = 0; i < script_lines->len; i++) {
 344         parser_string_free(ast, (rb_parser_string_t *)script_lines->data[i]);
 345     }
 346     xfree(script_lines->data);
 347     xfree(script_lines);
 348 }
 349
 350 void
 351 rb_ast_free(rb_ast_t *ast)
 352 {
 353     rb_ast_dispose(ast);
 354     xfree(ast);
 355 }
 356
 357 static size_t
 358 buffer_list_size(node_buffer_list_t *nb)
 359 {
 360     size_t size = 0;
 361     node_buffer_elem_t *nbe = nb->head;
 362     while (nbe != nb->last) {
 363         size += offsetof(node_buffer_elem_t, buf) + nbe->used;
 364         nbe = nbe->next;
 365     }
 366     return size;
 367 }
 368
 369 size_t
 370 rb_ast_memsize(const rb_ast_t *ast)
 371 {
 372     size_t size = sizeof(rb_ast_t);
 373     node_buffer_t *nb = ast->node_buffer;
 374     rb_parser_ary_t *tokens = NULL;
 375     struct rb_ast_local_table_link *link = NULL;
 376     rb_parser_ary_t *script_lines = ast->body.script_lines;
 377
 378     long i;
 379
 380     if (nb) {
 381         size += sizeof(node_buffer_t);
 382         size += buffer_list_size(&nb->buffer_list);
 383         link = nb->local_tables;
 384         tokens = nb->tokens;
 385     }
 386
 387     while (link) {
 388         size += sizeof(struct rb_ast_local_table_link);
 389         size += link->size * sizeof(ID);
 390         link = link->next;
 391     }
 392
 393     if (tokens) {
 394         size += sizeof(rb_parser_ary_t);
 395         for (i = 0; i < tokens->len; i++) {
 396             size += sizeof(rb_parser_ast_token_t);
 397             rb_parser_ast_token_t *token = tokens->data[i];
 398             size += sizeof(rb_parser_string_t);
 399             size += token->str->len + 1;
 400         }
 401     }
 402
 403     if (script_lines) {
 404         size += sizeof(rb_parser_ary_t);
 405         for (i = 0; i < script_lines->len; i++) {
 406             size += sizeof(rb_parser_string_t);
 407             size += ((rb_parser_string_t *)script_lines->data[i])->len + 1;
 408         }
 409     }
 410
 411     return size;
 412 }
 413
 414 void
 415 rb_ast_dispose(rb_ast_t *ast)
 416 {
 417     if (ast && ast->node_buffer) {
 418         script_lines_free(ast, ast->body.script_lines);
 419         ast->body.script_lines = NULL;
 420         rb_node_buffer_free(ast, ast->node_buffer);
 421         ast->node_buffer = 0;
 422     }
 423 }
 424
 425 VALUE
 426 rb_node_set_type(NODE *n, enum node_type t)
 427 {
 428     return nd_init_type(n, t);
 429 }