Ruby  3.4.0dev (2024-11-23 revision b4d13fac3dd5420475aa1e14fdad8137da7e3ee0)
node.c (b4d13fac3dd5420475aa1e14fdad8137da7e3ee0)
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 
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 parser_nodes_free(rb_ast_t *ast, rb_parser_ary_t *nodes)
167 {
168  /* Do nothing for nodes because nodes are freed when rb_ast_t is freed */
169  xfree(nodes->data);
170  xfree(nodes);
171 }
172 
173 static void
174 free_ast_value(rb_ast_t *ast, void *ctx, NODE *node)
175 {
176  switch (nd_type(node)) {
177  case NODE_STR:
178  parser_string_free(ast, RNODE_STR(node)->string);
179  break;
180  case NODE_DSTR:
181  parser_string_free(ast, RNODE_DSTR(node)->string);
182  break;
183  case NODE_XSTR:
184  parser_string_free(ast, RNODE_XSTR(node)->string);
185  break;
186  case NODE_DXSTR:
187  parser_string_free(ast, RNODE_DXSTR(node)->string);
188  break;
189  case NODE_SYM:
190  parser_string_free(ast, RNODE_SYM(node)->string);
191  break;
192  case NODE_REGX:
193  case NODE_MATCH:
194  parser_string_free(ast, RNODE_REGX(node)->string);
195  break;
196  case NODE_DSYM:
197  parser_string_free(ast, RNODE_DSYM(node)->string);
198  break;
199  case NODE_DREGX:
200  parser_string_free(ast, RNODE_DREGX(node)->string);
201  break;
202  case NODE_FILE:
203  parser_string_free(ast, RNODE_FILE(node)->path);
204  break;
205  case NODE_INTEGER:
206  xfree(RNODE_INTEGER(node)->val);
207  break;
208  case NODE_FLOAT:
209  xfree(RNODE_FLOAT(node)->val);
210  break;
211  case NODE_RATIONAL:
212  xfree(RNODE_RATIONAL(node)->val);
213  break;
214  case NODE_IMAGINARY:
215  xfree(RNODE_IMAGINARY(node)->val);
216  break;
217  case NODE_UNDEF:
218  parser_nodes_free(ast, RNODE_UNDEF(node)->nd_undefs);
219  break;
220  default:
221  break;
222  }
223 }
224 
225 static void
226 rb_node_buffer_free(rb_ast_t *ast, node_buffer_t *nb)
227 {
228  if (nb && nb->tokens) {
229  parser_tokens_free(ast, nb->tokens);
230  }
231  iterate_node_values(ast, &nb->buffer_list, free_ast_value, NULL);
232  node_buffer_list_free(ast, &nb->buffer_list);
233  struct rb_ast_local_table_link *local_table = nb->local_tables;
234  while (local_table) {
235  struct rb_ast_local_table_link *next_table = local_table->next;
236  xfree(local_table);
237  local_table = next_table;
238  }
239  xfree(nb);
240 }
241 
242 #define buf_add_offset(nbe, offset) ((char *)(nbe->buf) + (offset))
243 
244 static NODE *
245 ast_newnode_in_bucket(rb_ast_t *ast, node_buffer_list_t *nb, size_t size, size_t alignment)
246 {
247  size_t padding;
248  NODE *ptr;
249 
250  padding = alignment - (size_t)buf_add_offset(nb->head, nb->head->used) % alignment;
251  padding = padding == alignment ? 0 : padding;
252 
253  if (nb->head->used + size + padding > nb->head->allocated) {
254  size_t n = nb->head->allocated * 2;
255  node_buffer_elem_t *nbe;
256  nbe = rb_xmalloc_mul_add(n, sizeof(char *), offsetof(node_buffer_elem_t, buf));
257  init_node_buffer_elem(nbe, n, ruby_xmalloc);
258  nbe->next = nb->head;
259  nb->head = nbe;
260  padding = 0; /* malloc returns aligned address then no need to add padding */
261  }
262 
263  ptr = (NODE *)buf_add_offset(nb->head, nb->head->used + padding);
264  nb->head->used += (size + padding);
265  nb->head->nodes[nb->head->len++] = ptr;
266  return ptr;
267 }
268 
269 NODE *
270 rb_ast_newnode(rb_ast_t *ast, enum node_type type, size_t size, size_t alignment)
271 {
272  node_buffer_t *nb = ast->node_buffer;
273  node_buffer_list_t *bucket = &nb->buffer_list;
274  return ast_newnode_in_bucket(ast, bucket, size, alignment);
275 }
276 
278 rb_ast_new_local_table(rb_ast_t *ast, int size)
279 {
280  size_t alloc_size = sizeof(struct rb_ast_local_table_link) + size * sizeof(ID);
281  struct rb_ast_local_table_link *link = ruby_xmalloc(alloc_size);
282  link->next = ast->node_buffer->local_tables;
283  ast->node_buffer->local_tables = link;
284  link->size = size;
285 
286  return (rb_ast_id_table_t *) &link->size;
287 }
288 
290 rb_ast_resize_latest_local_table(rb_ast_t *ast, int size)
291 {
292  struct rb_ast_local_table_link *link = ast->node_buffer->local_tables;
293  size_t alloc_size = sizeof(struct rb_ast_local_table_link) + size * sizeof(ID);
294  link = ruby_xrealloc(link, alloc_size);
295  ast->node_buffer->local_tables = link;
296  link->size = size;
297 
298  return (rb_ast_id_table_t *) &link->size;
299 }
300 
301 void
302 rb_ast_delete_node(rb_ast_t *ast, NODE *n)
303 {
304  (void)ast;
305  (void)n;
306  /* should we implement freelist? */
307 }
308 
309 #ifdef UNIVERSAL_PARSER
310 rb_ast_t *
311 rb_ast_new(const rb_parser_config_t *config)
312 {
313  node_buffer_t *nb = rb_node_buffer_new(config);
314  rb_ast_t *ast = (rb_ast_t *)config->calloc(1, sizeof(rb_ast_t));
315  ast->config = config;
316  ast->node_buffer = nb;
317  return ast;
318 }
319 #else
320 rb_ast_t *
321 rb_ast_new(void)
322 {
323  node_buffer_t *nb = rb_node_buffer_new();
324  rb_ast_t *ast = ruby_xcalloc(1, sizeof(rb_ast_t));
325  ast->node_buffer = nb;
326  return ast;
327 }
328 #endif
329 
330 static void
331 iterate_buffer_elements(rb_ast_t *ast, node_buffer_elem_t *nbe, long len, node_itr_t *func, void *ctx)
332 {
333  long cursor;
334  for (cursor = 0; cursor < len; cursor++) {
335  func(ast, ctx, nbe->nodes[cursor]);
336  }
337 }
338 
339 static void
340 iterate_node_values(rb_ast_t *ast, node_buffer_list_t *nb, node_itr_t * func, void *ctx)
341 {
342  node_buffer_elem_t *nbe = nb->head;
343 
344  while (nbe) {
345  iterate_buffer_elements(ast, nbe, nbe->len, func, ctx);
346  nbe = nbe->next;
347  }
348 }
349 
350 static void
351 script_lines_free(rb_ast_t *ast, rb_parser_ary_t *script_lines)
352 {
353  if (!script_lines) return;
354  for (long i = 0; i < script_lines->len; i++) {
355  parser_string_free(ast, (rb_parser_string_t *)script_lines->data[i]);
356  }
357  xfree(script_lines->data);
358  xfree(script_lines);
359 }
360 
361 void
362 rb_ast_free(rb_ast_t *ast)
363 {
364  rb_ast_dispose(ast);
365  xfree(ast);
366 }
367 
368 static size_t
369 buffer_list_size(node_buffer_list_t *nb)
370 {
371  size_t size = 0;
372  node_buffer_elem_t *nbe = nb->head;
373  while (nbe != nb->last) {
374  size += offsetof(node_buffer_elem_t, buf) + nbe->used;
375  nbe = nbe->next;
376  }
377  return size;
378 }
379 
380 size_t
381 rb_ast_memsize(const rb_ast_t *ast)
382 {
383  size_t size = sizeof(rb_ast_t);
384  node_buffer_t *nb = ast->node_buffer;
385  rb_parser_ary_t *tokens = NULL;
386  struct rb_ast_local_table_link *link = NULL;
387  rb_parser_ary_t *script_lines = ast->body.script_lines;
388 
389  long i;
390 
391  if (nb) {
392  size += sizeof(node_buffer_t);
393  size += buffer_list_size(&nb->buffer_list);
394  link = nb->local_tables;
395  tokens = nb->tokens;
396  }
397 
398  while (link) {
399  size += sizeof(struct rb_ast_local_table_link);
400  size += link->size * sizeof(ID);
401  link = link->next;
402  }
403 
404  if (tokens) {
405  size += sizeof(rb_parser_ary_t);
406  for (i = 0; i < tokens->len; i++) {
407  size += sizeof(rb_parser_ast_token_t);
408  rb_parser_ast_token_t *token = tokens->data[i];
409  size += sizeof(rb_parser_string_t);
410  size += token->str->len + 1;
411  }
412  }
413 
414  if (script_lines) {
415  size += sizeof(rb_parser_ary_t);
416  for (i = 0; i < script_lines->len; i++) {
417  size += sizeof(rb_parser_string_t);
418  size += ((rb_parser_string_t *)script_lines->data[i])->len + 1;
419  }
420  }
421 
422  return size;
423 }
424 
425 void
426 rb_ast_dispose(rb_ast_t *ast)
427 {
428  if (ast && ast->node_buffer) {
429  script_lines_free(ast, ast->body.script_lines);
430  ast->body.script_lines = NULL;
431  rb_node_buffer_free(ast, ast->node_buffer);
432  ast->node_buffer = 0;
433  }
434 }
435 
436 VALUE
437 rb_node_set_type(NODE *n, enum node_type t)
438 {
439  return nd_init_type(n, t);
440 }
#define xfree
Old name of ruby_xfree.
Definition: xmalloc.h:58
#define xmalloc
Old name of ruby_xmalloc.
Definition: xmalloc.h:53
void rb_bug(const char *fmt,...)
Interpreter panic switch.
Definition: error.c:1089
char * ptr
Pointer to the underlying memory region, of at least capa bytes.
Definition: io.h:2
int len
Length of the buffer.
Definition: io.h:8
VALUE type(ANYARGS)
ANYARGS-ed function type.
Definition: cxxanyargs.hpp:56
uintptr_t ID
Type that represents a Ruby identifier such as a variable name.
Definition: value.h:52
uintptr_t VALUE
Type that represents a Ruby object.
Definition: value.h:40
void * ruby_xmalloc(size_t size)
Allocates a storage instance.
Definition: gc.c:4215
void * ruby_xcalloc(size_t nelems, size_t elemsiz)
Identical to ruby_xmalloc2(), except it returns a zero-filled storage instance.
Definition: gc.c:4239
void * ruby_xrealloc(void *ptr, size_t newsiz)
Resize the storage instance.
Definition: gc.c:4258