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 #include "internal.h"
  13 #include "internal/hash.h"
  14 #include "internal/variable.h"
  15 #include "ruby/ruby.h"
  16 #include "vm_core.h"
  17
  18 #define NODE_BUF_DEFAULT_LEN 16
  19
  20 #define A(str) rb_str_cat2(buf, (str))
  21 #define AR(str) rb_str_concat(buf, (str))
  22
  23 #define A_INDENT add_indent(buf, indent)
  24 #define D_INDENT rb_str_cat2(indent, next_indent)
  25 #define D_DEDENT rb_str_resize(indent, RSTRING_LEN(indent) - 4)
  26 #define A_ID(id) add_id(buf, (id))
  27 #define A_INT(val) rb_str_catf(buf, "%d", (val))
  28 #define A_LONG(val) rb_str_catf(buf, "%ld", (val))
  29 #define A_LIT(lit) AR(rb_dump_literal(lit))
  30 #define A_NODE_HEADER(node, term) \
  31     rb_str_catf(buf, "@ %s (id: %d, line: %d, location: (%d,%d)-(%d,%d))%s"term, \
  32                 ruby_node_name(nd_type(node)), nd_node_id(node), nd_line(node), \
  33                 nd_first_lineno(node), nd_first_column(node), \
  34                 nd_last_lineno(node), nd_last_column(node), \
  35                 (node->flags & NODE_FL_NEWLINE ? "*" : ""))
  36 #define A_FIELD_HEADER(len, name, term) \
  37     rb_str_catf(buf, "+- %.*s:"term, (len), (name))
  38 #define D_FIELD_HEADER(len, name, term) (A_INDENT, A_FIELD_HEADER(len, name, term))
  39
  40 #define D_NULL_NODE (A_INDENT, A("(null node)\n"))
  41 #define D_NODE_HEADER(node) (A_INDENT, A_NODE_HEADER(node, "\n"))
  42
  43 #define COMPOUND_FIELD(len, name) \
  44     FIELD_BLOCK((D_FIELD_HEADER((len), (name), "\n"), D_INDENT), D_DEDENT)
  45
  46 #define COMPOUND_FIELD1(name, ann) \
  47     COMPOUND_FIELD(FIELD_NAME_LEN(name, ann), \
  48                    FIELD_NAME_DESC(name, ann))
  49
  50 #define FIELD_NAME_DESC(name, ann) name " (" ann ")"
  51 #define FIELD_NAME_LEN(name, ann) (int)( \
  52         comment ? \
  53         rb_strlen_lit(FIELD_NAME_DESC(name, ann)) : \
  54         rb_strlen_lit(name))
  55 #define SIMPLE_FIELD(len, name) \
  56     FIELD_BLOCK(D_FIELD_HEADER((len), (name), " "), A("\n"))
  57
  58 #define FIELD_BLOCK(init, reset) \
  59     for (init, field_flag = 1; \
  60          field_flag; /* should be optimized away */ \
  61          reset, field_flag = 0)
  62
  63 #define SIMPLE_FIELD1(name, ann)    SIMPLE_FIELD(FIELD_NAME_LEN(name, ann), FIELD_NAME_DESC(name, ann))
  64 #define F_CUSTOM1(name, ann)        SIMPLE_FIELD1(#name, ann)
  65 #define F_ID(name, ann)             SIMPLE_FIELD1(#name, ann) A_ID(node->name)
  66 #define F_GENTRY(name, ann)         SIMPLE_FIELD1(#name, ann) A_ID(node->name)
  67 #define F_INT(name, ann)            SIMPLE_FIELD1(#name, ann) A_INT(node->name)
  68 #define F_LONG(name, ann)           SIMPLE_FIELD1(#name, ann) A_LONG(node->name)
  69 #define F_LIT(name, ann)            SIMPLE_FIELD1(#name, ann) A_LIT(node->name)
  70 #define F_MSG(name, ann, desc)      SIMPLE_FIELD1(#name, ann) A(desc)
  71
  72 #define F_NODE(name, ann) \
  73     COMPOUND_FIELD1(#name, ann) {dump_node(buf, indent, comment, node->name);}
  74
  75 #define ANN(ann) \
  76     if (comment) { \
  77         A_INDENT; A("| # " ann "\n"); \
  78     }
  79
  80 #define LAST_NODE (next_indent = "    ")
  81
  82 VALUE
  83 rb_dump_literal(VALUE lit)
  84 {
  85     if (!RB_SPECIAL_CONST_P(lit)) {
  86         VALUE str;
  87         switch (RB_BUILTIN_TYPE(lit)) {
  88           case T_CLASS: case T_MODULE: case T_ICLASS:
  89             str = rb_class_path(lit);
  90             if (FL_TEST(lit, FL_SINGLETON)) {
  91                 str = rb_sprintf("<%"PRIsVALUE">", str);
  92             }
  93             return str;
  94           default:
  95             break;
  96         }
  97     }
  98     return rb_inspect(lit);
  99 }
 100
 101 static void
 102 add_indent(VALUE buf, VALUE indent)
 103 {
 104     AR(indent);
 105 }
 106
 107 static void
 108 add_id(VALUE buf, ID id)
 109 {
 110     if (id == 0) {
 111         A("(null)");
 112     }
 113     else {
 114         VALUE str = rb_id2str(id);
 115         if (str) {
 116             A(":"); AR(str);
 117         }
 118         else {
 119             rb_str_catf(buf, "(internal variable: 0x%"PRIsVALUE")", id);
 120         }
 121     }
 122 }
 123
 124 struct add_option_arg {
 125     VALUE buf, indent;
 126     st_index_t count;
 127 };
 128
 129 static void dump_node(VALUE, VALUE, int, const NODE *);
 130 static const char default_indent[] = "|   ";
 131
 132 static void
 133 dump_array(VALUE buf, VALUE indent, int comment, const NODE *node)
 134 {
 135     int field_flag;
 136     const char *next_indent = default_indent;
 137     F_LONG(nd_alen, "length");
 138     F_NODE(nd_head, "element");
 139     while (node->nd_next && nd_type_p(node->nd_next, NODE_LIST)) {
 140         node = node->nd_next;
 141         F_NODE(nd_head, "element");
 142     }
 143     LAST_NODE;
 144     F_NODE(nd_next, "next element");
 145 }
 146
 147 static void
 148 dump_node(VALUE buf, VALUE indent, int comment, const NODE * node)
 149 {
 150     int field_flag;
 151     int i;
 152     const char *next_indent = default_indent;
 153     enum node_type type;
 154
 155     if (!node) {
 156         D_NULL_NODE;
 157         return;
 158     }
 159
 160     D_NODE_HEADER(node);
 161
 162     type = nd_type(node);
 163     switch (type) {
 164       case NODE_BLOCK:
 165         ANN("statement sequence");
 166         ANN("format: [nd_head]; ...; [nd_next]");
 167         ANN("example: foo; bar");
 168         i = 0;
 169         do {
 170             A_INDENT;
 171             rb_str_catf(buf, "+- nd_head (%s%d):\n",
 172                         comment ? "statement #" : "", ++i);
 173             if (!node->nd_next) LAST_NODE;
 174             D_INDENT;
 175             dump_node(buf, indent, comment, node->nd_head);
 176             D_DEDENT;
 177         } while (node->nd_next &&
 178                  nd_type_p(node->nd_next, NODE_BLOCK) &&
 179                  (node = node->nd_next, 1));
 180         if (node->nd_next) {
 181             LAST_NODE;
 182             F_NODE(nd_next, "next block");
 183         }
 184         return;
 185
 186       case NODE_IF:
 187         ANN("if statement");
 188         ANN("format: if [nd_cond] then [nd_body] else [nd_else] end");
 189         ANN("example: if x == 1 then foo else bar end");
 190         F_NODE(nd_cond, "condition expr");
 191         F_NODE(nd_body, "then clause");
 192         LAST_NODE;
 193         F_NODE(nd_else, "else clause");
 194         return;
 195
 196       case NODE_UNLESS:
 197         ANN("unless statement");
 198         ANN("format: unless [nd_cond] then [nd_body] else [nd_else] end");
 199         ANN("example: unless x == 1 then foo else bar end");
 200         F_NODE(nd_cond, "condition expr");
 201         F_NODE(nd_body, "then clause");
 202         LAST_NODE;
 203         F_NODE(nd_else, "else clause");
 204         return;
 205
 206       case NODE_CASE:
 207         ANN("case statement");
 208         ANN("format: case [nd_head]; [nd_body]; end");
 209         ANN("example: case x; when 1; foo; when 2; bar; else baz; end");
 210         F_NODE(nd_head, "case expr");
 211         LAST_NODE;
 212         F_NODE(nd_body, "when clauses");
 213         return;
 214       case NODE_CASE2:
 215         ANN("case statement with no head");
 216         ANN("format: case; [nd_body]; end");
 217         ANN("example: case; when 1; foo; when 2; bar; else baz; end");
 218         F_NODE(nd_head, "case expr");
 219         LAST_NODE;
 220         F_NODE(nd_body, "when clauses");
 221         return;
 222       case NODE_CASE3:
 223         ANN("case statement (pattern matching)");
 224         ANN("format: case [nd_head]; [nd_body]; end");
 225         ANN("example: case x; in 1; foo; in 2; bar; else baz; end");
 226         F_NODE(nd_head, "case expr");
 227         LAST_NODE;
 228         F_NODE(nd_body, "in clauses");
 229         return;
 230
 231       case NODE_WHEN:
 232         ANN("when clause");
 233         ANN("format: when [nd_head]; [nd_body]; (when or else) [nd_next]");
 234         ANN("example: case x; when 1; foo; when 2; bar; else baz; end");
 235         F_NODE(nd_head, "when value");
 236         F_NODE(nd_body, "when body");
 237         LAST_NODE;
 238         F_NODE(nd_next, "next when clause");
 239         return;
 240
 241       case NODE_IN:
 242         ANN("in clause");
 243         ANN("format: in [nd_head]; [nd_body]; (in or else) [nd_next]");
 244         ANN("example: case x; in 1; foo; in 2; bar; else baz; end");
 245         F_NODE(nd_head, "in pattern");
 246         F_NODE(nd_body, "in body");
 247         LAST_NODE;
 248         F_NODE(nd_next, "next in clause");
 249         return;
 250
 251       case NODE_WHILE:
 252         ANN("while statement");
 253         ANN("format: while [nd_cond]; [nd_body]; end");
 254         ANN("example: while x == 1; foo; end");
 255         goto loop;
 256       case NODE_UNTIL:
 257         ANN("until statement");
 258         ANN("format: until [nd_cond]; [nd_body]; end");
 259         ANN("example: until x == 1; foo; end");
 260       loop:
 261         F_CUSTOM1(nd_state, "begin-end-while?") {
 262             A_INT((int)node->nd_state);
 263             A((node->nd_state == 1) ? " (while-end)" : " (begin-end-while)");
 264         }
 265         F_NODE(nd_cond, "condition");
 266         LAST_NODE;
 267         F_NODE(nd_body, "body");
 268         return;
 269
 270       case NODE_ITER:
 271         ANN("method call with block");
 272         ANN("format: [nd_iter] { [nd_body] }");
 273         ANN("example: 3.times { foo }");
 274         goto iter;
 275       case NODE_FOR:
 276         ANN("for statement");
 277         ANN("format: for * in [nd_iter] do [nd_body] end");
 278         ANN("example: for i in 1..3 do foo end");
 279       iter:
 280         F_NODE(nd_iter, "iteration receiver");
 281         LAST_NODE;
 282         F_NODE(nd_body, "body");
 283         return;
 284
 285       case NODE_FOR_MASGN:
 286         ANN("vars of for statement with masgn");
 287         ANN("format: for [nd_var] in ... do ... end");
 288         ANN("example: for x, y in 1..3 do foo end");
 289         LAST_NODE;
 290         F_NODE(nd_var, "var");
 291         return;
 292
 293       case NODE_BREAK:
 294         ANN("break statement");
 295         ANN("format: break [nd_stts]");
 296         ANN("example: break 1");
 297         goto jump;
 298       case NODE_NEXT:
 299         ANN("next statement");
 300         ANN("format: next [nd_stts]");
 301         ANN("example: next 1");
 302         goto jump;
 303       case NODE_RETURN:
 304         ANN("return statement");
 305         ANN("format: return [nd_stts]");
 306         ANN("example: return 1");
 307       jump:
 308         LAST_NODE;
 309         F_NODE(nd_stts, "value");
 310         return;
 311
 312       case NODE_REDO:
 313         ANN("redo statement");
 314         ANN("format: redo");
 315         ANN("example: redo");
 316         return;
 317
 318       case NODE_RETRY:
 319         ANN("retry statement");
 320         ANN("format: retry");
 321         ANN("example: retry");
 322         return;
 323
 324       case NODE_BEGIN:
 325         ANN("begin statement");
 326         ANN("format: begin; [nd_body]; end");
 327         ANN("example: begin; 1; end");
 328         LAST_NODE;
 329         F_NODE(nd_body, "body");
 330         return;
 331
 332       case NODE_RESCUE:
 333         ANN("rescue clause");
 334         ANN("format: begin; [nd_body]; (rescue) [nd_resq]; else [nd_else]; end");
 335         ANN("example: begin; foo; rescue; bar; else; baz; end");
 336         F_NODE(nd_head, "body");
 337         F_NODE(nd_resq, "rescue clause list");
 338         LAST_NODE;
 339         F_NODE(nd_else, "rescue else clause");
 340         return;
 341
 342       case NODE_RESBODY:
 343         ANN("rescue clause (cont'd)");
 344         ANN("format: rescue [nd_args]; [nd_body]; (rescue) [nd_head]");
 345         ANN("example: begin; foo; rescue; bar; else; baz; end");
 346         F_NODE(nd_args, "rescue exceptions");
 347         F_NODE(nd_body, "rescue clause");
 348         LAST_NODE;
 349         F_NODE(nd_head, "next rescue clause");
 350         return;
 351
 352       case NODE_ENSURE:
 353         ANN("ensure clause");
 354         ANN("format: begin; [nd_head]; ensure; [nd_ensr]; end");
 355         ANN("example: begin; foo; ensure; bar; end");
 356         F_NODE(nd_head, "body");
 357         LAST_NODE;
 358         F_NODE(nd_ensr, "ensure clause");
 359         return;
 360
 361       case NODE_AND:
 362         ANN("&& operator");
 363         ANN("format: [nd_1st] && [nd_2nd]");
 364         ANN("example: foo && bar");
 365         goto andor;
 366       case NODE_OR:
 367         ANN("|| operator");
 368         ANN("format: [nd_1st] || [nd_2nd]");
 369         ANN("example: foo || bar");
 370       andor:
 371         while (1) {
 372             F_NODE(nd_1st, "left expr");
 373             if (!node->nd_2nd || !nd_type_p(node->nd_2nd, type))
 374                 break;
 375             node = node->nd_2nd;
 376         }
 377         LAST_NODE;
 378         F_NODE(nd_2nd, "right expr");
 379         return;
 380
 381       case NODE_MASGN:
 382         ANN("multiple assignment");
 383         ANN("format: [nd_head], [nd_args] = [nd_value]");
 384         ANN("example: a, b = foo");
 385         F_NODE(nd_value, "rhsn");
 386         F_NODE(nd_head, "lhsn");
 387         if (NODE_NAMED_REST_P(node->nd_args)) {
 388             LAST_NODE;
 389             F_NODE(nd_args, "splatn");
 390         }
 391         else {
 392             F_MSG(nd_args, "splatn", "NODE_SPECIAL_NO_NAME_REST (rest argument without name)");
 393         }
 394         return;
 395
 396       case NODE_LASGN:
 397         ANN("local variable assignment");
 398         ANN("format: [nd_vid](lvar) = [nd_value]");
 399         ANN("example: x = foo");
 400         F_ID(nd_vid, "local variable");
 401         if (NODE_REQUIRED_KEYWORD_P(node)) {
 402             F_MSG(nd_value, "rvalue", "NODE_SPECIAL_REQUIRED_KEYWORD (required keyword argument)");
 403         }
 404         else {
 405             LAST_NODE;
 406             F_NODE(nd_value, "rvalue");
 407         }
 408         return;
 409       case NODE_DASGN:
 410         ANN("dynamic variable assignment");
 411         ANN("format: [nd_vid](dvar) = [nd_value]");
 412         ANN("example: x = nil; 1.times { x = foo }");
 413         ANN("example: 1.times { x = foo }");
 414         F_ID(nd_vid, "local variable");
 415         if (NODE_REQUIRED_KEYWORD_P(node)) {
 416             F_MSG(nd_value, "rvalue", "NODE_SPECIAL_REQUIRED_KEYWORD (required keyword argument)");
 417         }
 418         else {
 419             LAST_NODE;
 420             F_NODE(nd_value, "rvalue");
 421         }
 422         return;
 423       case NODE_IASGN:
 424         ANN("instance variable assignment");
 425         ANN("format: [nd_vid](ivar) = [nd_value]");
 426         ANN("example: @x = foo");
 427         F_ID(nd_vid, "instance variable");
 428         LAST_NODE;
 429         F_NODE(nd_value, "rvalue");
 430         return;
 431       case NODE_CVASGN:
 432         ANN("class variable assignment");
 433         ANN("format: [nd_vid](cvar) = [nd_value]");
 434         ANN("example: @@x = foo");
 435         F_ID(nd_vid, "class variable");
 436         LAST_NODE;
 437         F_NODE(nd_value, "rvalue");
 438         return;
 439       case NODE_GASGN:
 440         ANN("global variable assignment");
 441         ANN("format: [nd_entry](gvar) = [nd_value]");
 442         ANN("example: $x = foo");
 443         F_GENTRY(nd_entry, "global variable");
 444         LAST_NODE;
 445         F_NODE(nd_value, "rvalue");
 446         return;
 447
 448       case NODE_CDECL:
 449         ANN("constant declaration");
 450         ANN("format: [nd_else]::[nd_vid](constant) = [nd_value]");
 451         ANN("example: X = foo");
 452         if (node->nd_vid) {
 453             F_ID(nd_vid, "constant");
 454             F_MSG(nd_else, "extension", "not used");
 455         }
 456         else {
 457             F_MSG(nd_vid, "constant", "0 (see extension field)");
 458             F_NODE(nd_else, "extension");
 459         }
 460         LAST_NODE;
 461         F_NODE(nd_value, "rvalue");
 462         return;
 463
 464       case NODE_OP_ASGN1:
 465         ANN("array assignment with operator");
 466         ANN("format: [nd_recv] [ [nd_args->nd_head] ] [nd_mid]= [nd_args->nd_body]");
 467         ANN("example: ary[1] += foo");
 468         F_NODE(nd_recv, "receiver");
 469         F_ID(nd_mid, "operator");
 470         F_NODE(nd_args->nd_head, "index");
 471         LAST_NODE;
 472         F_NODE(nd_args->nd_body, "rvalue");
 473         return;
 474
 475       case NODE_OP_ASGN2:
 476         ANN("attr assignment with operator");
 477         ANN("format: [nd_recv].[attr] [nd_next->nd_mid]= [nd_value]");
 478         ANN("          where [attr]: [nd_next->nd_vid]");
 479         ANN("example: struct.field += foo");
 480         F_NODE(nd_recv, "receiver");
 481         F_CUSTOM1(nd_next->nd_vid, "attr") {
 482             if (node->nd_next->nd_aid) A("? ");
 483             A_ID(node->nd_next->nd_vid);
 484         }
 485         F_ID(nd_next->nd_mid, "operator");
 486         LAST_NODE;
 487         F_NODE(nd_value, "rvalue");
 488         return;
 489
 490       case NODE_OP_ASGN_AND:
 491         ANN("assignment with && operator");
 492         ANN("format: [nd_head] &&= [nd_value]");
 493         ANN("example: foo &&= bar");
 494         goto asgn_andor;
 495       case NODE_OP_ASGN_OR:
 496         ANN("assignment with || operator");
 497         ANN("format: [nd_head] ||= [nd_value]");
 498         ANN("example: foo ||= bar");
 499       asgn_andor:
 500         F_NODE(nd_head, "variable");
 501         LAST_NODE;
 502         F_NODE(nd_value, "rvalue");
 503         return;
 504
 505       case NODE_OP_CDECL:
 506         ANN("constant declaration with operator");
 507         ANN("format: [nd_head](constant) [nd_aid]= [nd_value]");
 508         ANN("example: A::B ||= 1");
 509         F_NODE(nd_head, "constant");
 510         F_ID(nd_aid, "operator");
 511         LAST_NODE;
 512         F_NODE(nd_value, "rvalue");
 513         return;
 514
 515       case NODE_CALL:
 516         ANN("method invocation");
 517         ANN("format: [nd_recv].[nd_mid]([nd_args])");
 518         ANN("example: obj.foo(1)");
 519         F_ID(nd_mid, "method id");
 520         F_NODE(nd_recv, "receiver");
 521         LAST_NODE;
 522         F_NODE(nd_args, "arguments");
 523         return;
 524
 525       case NODE_OPCALL:
 526         ANN("method invocation");
 527         ANN("format: [nd_recv] [nd_mid] [nd_args]");
 528         ANN("example: foo + bar");
 529         F_ID(nd_mid, "method id");
 530         F_NODE(nd_recv, "receiver");
 531         LAST_NODE;
 532         F_NODE(nd_args, "arguments");
 533         return;
 534
 535       case NODE_FCALL:
 536         ANN("function call");
 537         ANN("format: [nd_mid]([nd_args])");
 538         ANN("example: foo(1)");
 539         F_ID(nd_mid, "method id");
 540         LAST_NODE;
 541         F_NODE(nd_args, "arguments");
 542         return;
 543
 544       case NODE_VCALL:
 545         ANN("function call with no argument");
 546         ANN("format: [nd_mid]");
 547         ANN("example: foo");
 548         F_ID(nd_mid, "method id");
 549         return;
 550
 551       case NODE_QCALL:
 552         ANN("safe method invocation");
 553         ANN("format: [nd_recv]&.[nd_mid]([nd_args])");
 554         ANN("example: obj&.foo(1)");
 555         F_ID(nd_mid, "method id");
 556         F_NODE(nd_recv, "receiver");
 557         LAST_NODE;
 558         F_NODE(nd_args, "arguments");
 559         return;
 560
 561       case NODE_SUPER:
 562         ANN("super invocation");
 563         ANN("format: super [nd_args]");
 564         ANN("example: super 1");
 565         LAST_NODE;
 566         F_NODE(nd_args, "arguments");
 567         return;
 568
 569       case NODE_ZSUPER:
 570         ANN("super invocation with no argument");
 571         ANN("format: super");
 572         ANN("example: super");
 573         return;
 574
 575       case NODE_LIST:
 576         ANN("list constructor");
 577         ANN("format: [ [nd_head], [nd_next].. ] (length: [nd_alen])");
 578         ANN("example: [1, 2, 3]");
 579         goto ary;
 580       case NODE_VALUES:
 581         ANN("return arguments");
 582         ANN("format: [ [nd_head], [nd_next].. ] (length: [nd_alen])");
 583         ANN("example: return 1, 2, 3");
 584       ary:
 585         dump_array(buf, indent, comment, node);
 586         return;
 587
 588       case NODE_ZLIST:
 589         ANN("empty list constructor");
 590         ANN("format: []");
 591         ANN("example: []");
 592         return;
 593
 594       case NODE_HASH:
 595         if (!node->nd_brace) {
 596             ANN("keyword arguments");
 597             ANN("format: nd_head");
 598             ANN("example: a: 1, b: 2");
 599         }
 600         else {
 601             ANN("hash constructor");
 602             ANN("format: { [nd_head] }");
 603             ANN("example: { 1 => 2, 3 => 4 }");
 604         }
 605         F_CUSTOM1(nd_brace, "keyword arguments or hash literal") {
 606             switch (node->nd_brace) {
 607               case 0: A("0 (keyword argument)"); break;
 608               case 1: A("1 (hash literal)"); break;
 609             }
 610         }
 611         LAST_NODE;
 612         F_NODE(nd_head, "contents");
 613         return;
 614
 615       case NODE_YIELD:
 616         ANN("yield invocation");
 617         ANN("format: yield [nd_head]");
 618         ANN("example: yield 1");
 619         LAST_NODE;
 620         F_NODE(nd_head, "arguments");
 621         return;
 622
 623       case NODE_LVAR:
 624         ANN("local variable reference");
 625         ANN("format: [nd_vid](lvar)");
 626         ANN("example: x");
 627         F_ID(nd_vid, "local variable");
 628         return;
 629       case NODE_DVAR:
 630         ANN("dynamic variable reference");
 631         ANN("format: [nd_vid](dvar)");
 632         ANN("example: 1.times { x = 1; x }");
 633         F_ID(nd_vid, "local variable");
 634         return;
 635       case NODE_IVAR:
 636         ANN("instance variable reference");
 637         ANN("format: [nd_vid](ivar)");
 638         ANN("example: @x");
 639         F_ID(nd_vid, "instance variable");
 640         return;
 641       case NODE_CONST:
 642         ANN("constant reference");
 643         ANN("format: [nd_vid](constant)");
 644         ANN("example: X");
 645         F_ID(nd_vid, "constant");
 646         return;
 647       case NODE_CVAR:
 648         ANN("class variable reference");
 649         ANN("format: [nd_vid](cvar)");
 650         ANN("example: @@x");
 651         F_ID(nd_vid, "class variable");
 652         return;
 653
 654       case NODE_GVAR:
 655         ANN("global variable reference");
 656         ANN("format: [nd_entry](gvar)");
 657         ANN("example: $x");
 658         F_GENTRY(nd_entry, "global variable");
 659         return;
 660
 661       case NODE_NTH_REF:
 662         ANN("nth special variable reference");
 663         ANN("format: $[nd_nth]");
 664         ANN("example: $1, $2, ..");
 665         F_CUSTOM1(nd_nth, "variable") { A("$"); A_LONG(node->nd_nth); }
 666         return;
 667
 668       case NODE_BACK_REF:
 669         ANN("back special variable reference");
 670         ANN("format: $[nd_nth]");
 671         ANN("example: $&, $`, $', $+");
 672         F_CUSTOM1(nd_nth, "variable") {
 673             char name[3] = "$ ";
 674             name[1] = (char)node->nd_nth;
 675             A(name);
 676         }
 677         return;
 678
 679       case NODE_MATCH:
 680         ANN("match expression (against $_ implicitly)");
 681         ANN("format: [nd_lit] (in condition)");
 682         ANN("example: if /foo/; foo; end");
 683         F_LIT(nd_lit, "regexp");
 684         return;
 685
 686       case NODE_MATCH2:
 687         ANN("match expression (regexp first)");
 688         ANN("format: [nd_recv] =~ [nd_value]");
 689         ANN("example: /foo/ =~ 'foo'");
 690         F_NODE(nd_recv, "regexp (receiver)");
 691         if (!node->nd_args) LAST_NODE;
 692         F_NODE(nd_value, "string (argument)");
 693         if (node->nd_args) {
 694             LAST_NODE;
 695             F_NODE(nd_args, "named captures");
 696         }
 697         return;
 698
 699       case NODE_MATCH3:
 700         ANN("match expression (regexp second)");
 701         ANN("format: [nd_recv] =~ [nd_value]");
 702         ANN("example: 'foo' =~ /foo/");
 703         F_NODE(nd_recv, "string (receiver)");
 704         LAST_NODE;
 705         F_NODE(nd_value, "regexp (argument)");
 706         return;
 707
 708       case NODE_LIT:
 709         ANN("literal");
 710         ANN("format: [nd_lit]");
 711         ANN("example: 1, /foo/");
 712         goto lit;
 713       case NODE_STR:
 714         ANN("string literal");
 715         ANN("format: [nd_lit]");
 716         ANN("example: 'foo'");
 717         goto lit;
 718       case NODE_XSTR:
 719         ANN("xstring literal");
 720         ANN("format: [nd_lit]");
 721         ANN("example: `foo`");
 722       lit:
 723         F_LIT(nd_lit, "literal");
 724         return;
 725
 726       case NODE_ONCE:
 727         ANN("once evaluation");
 728         ANN("format: [nd_body]");
 729         ANN("example: /foo#{ bar }baz/o");
 730         LAST_NODE;
 731         F_NODE(nd_body, "body");
 732         return;
 733       case NODE_DSTR:
 734         ANN("string literal with interpolation");
 735         ANN("format: [nd_lit]");
 736         ANN("example: \"foo#{ bar }baz\"");
 737         goto dlit;
 738       case NODE_DXSTR:
 739         ANN("xstring literal with interpolation");
 740         ANN("format: [nd_lit]");
 741         ANN("example: `foo#{ bar }baz`");
 742         goto dlit;
 743       case NODE_DREGX:
 744         ANN("regexp literal with interpolation");
 745         ANN("format: [nd_lit]");
 746         ANN("example: /foo#{ bar }baz/");
 747         goto dlit;
 748       case NODE_DSYM:
 749         ANN("symbol literal with interpolation");
 750         ANN("format: [nd_lit]");
 751         ANN("example: :\"foo#{ bar }baz\"");
 752       dlit:
 753         F_LIT(nd_lit, "preceding string");
 754         if (!node->nd_next) return;
 755         F_NODE(nd_next->nd_head, "interpolation");
 756         LAST_NODE;
 757         F_NODE(nd_next->nd_next, "tailing strings");
 758         return;
 759
 760       case NODE_EVSTR:
 761         ANN("interpolation expression");
 762         ANN("format: \"..#{ [nd_lit] }..\"");
 763         ANN("example: \"foo#{ bar }baz\"");
 764         LAST_NODE;
 765         F_NODE(nd_body, "body");
 766         return;
 767
 768       case NODE_ARGSCAT:
 769         ANN("splat argument following arguments");
 770         ANN("format: ..(*[nd_head], [nd_body..])");
 771         ANN("example: foo(*ary, post_arg1, post_arg2)");
 772         F_NODE(nd_head, "preceding array");
 773         LAST_NODE;
 774         F_NODE(nd_body, "following array");
 775         return;
 776
 777       case NODE_ARGSPUSH:
 778         ANN("splat argument following one argument");
 779         ANN("format: ..(*[nd_head], [nd_body])");
 780         ANN("example: foo(*ary, post_arg)");
 781         F_NODE(nd_head, "preceding array");
 782         LAST_NODE;
 783         F_NODE(nd_body, "following element");
 784         return;
 785
 786       case NODE_SPLAT:
 787         ANN("splat argument");
 788         ANN("format: *[nd_head]");
 789         ANN("example: foo(*ary)");
 790         LAST_NODE;
 791         F_NODE(nd_head, "splat'ed array");
 792         return;
 793
 794       case NODE_BLOCK_PASS:
 795         ANN("arguments with block argument");
 796         ANN("format: ..([nd_head], &[nd_body])");
 797         ANN("example: foo(x, &blk)");
 798         F_NODE(nd_head, "other arguments");
 799         LAST_NODE;
 800         F_NODE(nd_body, "block argument");
 801         return;
 802
 803       case NODE_DEFN:
 804         ANN("method definition");
 805         ANN("format: def [nd_mid] [nd_defn]; end");
 806         ANN("example: def foo; bar; end");
 807         F_ID(nd_mid, "method name");
 808         LAST_NODE;
 809         F_NODE(nd_defn, "method definition");
 810         return;
 811
 812       case NODE_DEFS:
 813         ANN("singleton method definition");
 814         ANN("format: def [nd_recv].[nd_mid] [nd_defn]; end");
 815         ANN("example: def obj.foo; bar; end");
 816         F_NODE(nd_recv, "receiver");
 817         F_ID(nd_mid, "method name");
 818         LAST_NODE;
 819         F_NODE(nd_defn, "method definition");
 820         return;
 821
 822       case NODE_ALIAS:
 823         ANN("method alias statement");
 824         ANN("format: alias [nd_1st] [nd_2nd]");
 825         ANN("example: alias bar foo");
 826         F_NODE(nd_1st, "new name");
 827         LAST_NODE;
 828         F_NODE(nd_2nd, "old name");
 829         return;
 830
 831       case NODE_VALIAS:
 832         ANN("global variable alias statement");
 833         ANN("format: alias [nd_alias](gvar) [nd_orig](gvar)");
 834         ANN("example: alias $y $x");
 835         F_ID(nd_alias, "new name");
 836         F_ID(nd_orig, "old name");
 837         return;
 838
 839       case NODE_UNDEF:
 840         ANN("method undef statement");
 841         ANN("format: undef [nd_undef]");
 842         ANN("example: undef foo");
 843         LAST_NODE;
 844         F_NODE(nd_undef, "old name");
 845         return;
 846
 847       case NODE_CLASS:
 848         ANN("class definition");
 849         ANN("format: class [nd_cpath] < [nd_super]; [nd_body]; end");
 850         ANN("example: class C2 < C; ..; end");
 851         F_NODE(nd_cpath, "class path");
 852         F_NODE(nd_super, "superclass");
 853         LAST_NODE;
 854         F_NODE(nd_body, "class definition");
 855         return;
 856
 857       case NODE_MODULE:
 858         ANN("module definition");
 859         ANN("format: module [nd_cpath]; [nd_body]; end");
 860         ANN("example: module M; ..; end");
 861         F_NODE(nd_cpath, "module path");
 862         LAST_NODE;
 863         F_NODE(nd_body, "module definition");
 864         return;
 865
 866       case NODE_SCLASS:
 867         ANN("singleton class definition");
 868         ANN("format: class << [nd_recv]; [nd_body]; end");
 869         ANN("example: class << obj; ..; end");
 870         F_NODE(nd_recv, "receiver");
 871         LAST_NODE;
 872         F_NODE(nd_body, "singleton class definition");
 873         return;
 874
 875       case NODE_COLON2:
 876         ANN("scoped constant reference");
 877         ANN("format: [nd_head]::[nd_mid]");
 878         ANN("example: M::C");
 879         F_ID(nd_mid, "constant name");
 880         LAST_NODE;
 881         F_NODE(nd_head, "receiver");
 882         return;
 883
 884       case NODE_COLON3:
 885         ANN("top-level constant reference");
 886         ANN("format: ::[nd_mid]");
 887         ANN("example: ::Object");
 888         F_ID(nd_mid, "constant name");
 889         return;
 890
 891       case NODE_DOT2:
 892         ANN("range constructor (incl.)");
 893         ANN("format: [nd_beg]..[nd_end]");
 894         ANN("example: 1..5");
 895         goto dot;
 896       case NODE_DOT3:
 897         ANN("range constructor (excl.)");
 898         ANN("format: [nd_beg]...[nd_end]");
 899         ANN("example: 1...5");
 900         goto dot;
 901       case NODE_FLIP2:
 902         ANN("flip-flop condition (incl.)");
 903         ANN("format: [nd_beg]..[nd_end]");
 904         ANN("example: if (x==1)..(x==5); foo; end");
 905         goto dot;
 906       case NODE_FLIP3:
 907         ANN("flip-flop condition (excl.)");
 908         ANN("format: [nd_beg]...[nd_end]");
 909         ANN("example: if (x==1)...(x==5); foo; end");
 910       dot:
 911         F_NODE(nd_beg, "begin");
 912         LAST_NODE;
 913         F_NODE(nd_end, "end");
 914         return;
 915
 916       case NODE_SELF:
 917         ANN("self");
 918         ANN("format: self");
 919         ANN("example: self");
 920         return;
 921
 922       case NODE_NIL:
 923         ANN("nil");
 924         ANN("format: nil");
 925         ANN("example: nil");
 926         return;
 927
 928       case NODE_TRUE:
 929         ANN("true");
 930         ANN("format: true");
 931         ANN("example: true");
 932         return;
 933
 934       case NODE_FALSE:
 935         ANN("false");
 936         ANN("format: false");
 937         ANN("example: false");
 938         return;
 939
 940       case NODE_ERRINFO:
 941         ANN("virtual reference to $!");
 942         ANN("format: rescue => id");
 943         ANN("example: rescue => id");
 944         return;
 945
 946       case NODE_DEFINED:
 947         ANN("defined? expression");
 948         ANN("format: defined?([nd_head])");
 949         ANN("example: defined?(foo)");
 950         F_NODE(nd_head, "expr");
 951         return;
 952
 953       case NODE_POSTEXE:
 954         ANN("post-execution");
 955         ANN("format: END { [nd_body] }");
 956         ANN("example: END { foo }");
 957         LAST_NODE;
 958         F_NODE(nd_body, "END clause");
 959         return;
 960
 961       case NODE_ATTRASGN:
 962         ANN("attr assignment");
 963         ANN("format: [nd_recv].[nd_mid] = [nd_args]");
 964         ANN("example: struct.field = foo");
 965         F_NODE(nd_recv, "receiver");
 966         F_ID(nd_mid, "method name");
 967         LAST_NODE;
 968         F_NODE(nd_args, "arguments");
 969         return;
 970
 971       case NODE_LAMBDA:
 972         ANN("lambda expression");
 973         ANN("format: -> [nd_body]");
 974         ANN("example: -> { foo }");
 975         LAST_NODE;
 976         F_NODE(nd_body, "lambda clause");
 977         return;
 978
 979       case NODE_OPT_ARG:
 980         ANN("optional arguments");
 981         ANN("format: def method_name([nd_body=some], [nd_next..])");
 982         ANN("example: def foo(a, b=1, c); end");
 983         F_NODE(nd_body, "body");
 984         LAST_NODE;
 985         F_NODE(nd_next, "next");
 986         return;
 987
 988       case NODE_KW_ARG:
 989         ANN("keyword arguments");
 990         ANN("format: def method_name([nd_body=some], [nd_next..])");
 991         ANN("example: def foo(a:1, b:2); end");
 992         F_NODE(nd_body, "body");
 993         LAST_NODE;
 994         F_NODE(nd_next, "next");
 995         return;
 996
 997       case NODE_POSTARG:
 998         ANN("post arguments");
 999         ANN("format: *[nd_1st], [nd_2nd..] = ..");
1000         ANN("example: a, *rest, z = foo");
1001         if (NODE_NAMED_REST_P(node->nd_1st)) {
1002             F_NODE(nd_1st, "rest argument");
1003         }
1004         else {
1005             F_MSG(nd_1st, "rest argument", "NODE_SPECIAL_NO_NAME_REST (rest argument without name)");
1006         }
1007         LAST_NODE;
1008         F_NODE(nd_2nd, "post arguments");
1009         return;
1010
1011       case NODE_ARGS:
1012         ANN("method parameters");
1013         ANN("format: def method_name(.., [nd_ainfo->nd_optargs], *[nd_ainfo->rest_arg], [nd_ainfo->first_post_arg], .., [nd_ainfo->kw_args], **[nd_ainfo->kw_rest_arg], &[nd_ainfo->block_arg])");
1014         ANN("example: def foo(a, b, opt1=1, opt2=2, *rest, y, z, kw: 1, **kwrest, &blk); end");
1015         F_INT(nd_ainfo->pre_args_num, "count of mandatory (pre-)arguments");
1016         F_NODE(nd_ainfo->pre_init, "initialization of (pre-)arguments");
1017         F_INT(nd_ainfo->post_args_num, "count of mandatory post-arguments");
1018         F_NODE(nd_ainfo->post_init, "initialization of post-arguments");
1019         F_ID(nd_ainfo->first_post_arg, "first post argument");
1020         F_CUSTOM1(nd_ainfo->rest_arg, "rest argument") {
1021             if (node->nd_ainfo->rest_arg == NODE_SPECIAL_EXCESSIVE_COMMA) {
1022                 A("1 (excessed comma)");
1023             }
1024             else {
1025                 A_ID(node->nd_ainfo->rest_arg);
1026             }
1027         }
1028         F_ID(nd_ainfo->block_arg, "block argument");
1029         F_NODE(nd_ainfo->opt_args, "optional arguments");
1030         F_NODE(nd_ainfo->kw_args, "keyword arguments");
1031         LAST_NODE;
1032         F_NODE(nd_ainfo->kw_rest_arg, "keyword rest argument");
1033         return;
1034
1035       case NODE_SCOPE:
1036         ANN("new scope");
1037         ANN("format: [nd_tbl]: local table, [nd_args]: arguments, [nd_body]: body");
1038         F_CUSTOM1(nd_tbl, "local table") {
1039             rb_ast_id_table_t *tbl = node->nd_tbl;
1040             int i;
1041             int size = tbl ? tbl->size : 0;
1042             if (size == 0) A("(empty)");
1043             for (i = 0; i < size; i++) {
1044                 A_ID(tbl->ids[i]); if (i < size - 1) A(",");
1045             }
1046         }
1047         F_NODE(nd_args, "arguments");
1048         LAST_NODE;
1049         F_NODE(nd_body, "body");
1050         return;
1051
1052       case NODE_ARYPTN:
1053         ANN("array pattern");
1054         ANN("format: [nd_pconst]([pre_args], ..., *[rest_arg], [post_args], ...)");
1055         F_NODE(nd_pconst, "constant");
1056         F_NODE(nd_apinfo->pre_args, "pre arguments");
1057         if (NODE_NAMED_REST_P(node->nd_apinfo->rest_arg)) {
1058             F_NODE(nd_apinfo->rest_arg, "rest argument");
1059         }
1060         else {
1061             F_MSG(nd_apinfo->rest_arg, "rest argument", "NODE_SPECIAL_NO_NAME_REST (rest argument without name)");
1062         }
1063         LAST_NODE;
1064         F_NODE(nd_apinfo->post_args, "post arguments");
1065         return;
1066
1067       case NODE_FNDPTN:
1068         ANN("find pattern");
1069         ANN("format: [nd_pconst](*[pre_rest_arg], args, ..., *[post_rest_arg])");
1070         F_NODE(nd_pconst, "constant");
1071         if (NODE_NAMED_REST_P(node->nd_fpinfo->pre_rest_arg)) {
1072             F_NODE(nd_fpinfo->pre_rest_arg, "pre rest argument");
1073         }
1074         else {
1075             F_MSG(nd_fpinfo->pre_rest_arg, "pre rest argument", "NODE_SPECIAL_NO_NAME_REST (rest argument without name)");
1076         }
1077         F_NODE(nd_fpinfo->args, "arguments");
1078
1079         LAST_NODE;
1080         if (NODE_NAMED_REST_P(node->nd_fpinfo->post_rest_arg)) {
1081             F_NODE(nd_fpinfo->post_rest_arg, "post rest argument");
1082         }
1083         else {
1084             F_MSG(nd_fpinfo->post_rest_arg, "post rest argument", "NODE_SPECIAL_NO_NAME_REST (rest argument without name)");
1085         }
1086         return;
1087
1088       case NODE_HSHPTN:
1089         ANN("hash pattern");
1090         ANN("format: [nd_pconst]([nd_pkwargs], ..., **[nd_pkwrestarg])");
1091         F_NODE(nd_pconst, "constant");
1092         F_NODE(nd_pkwargs, "keyword arguments");
1093         LAST_NODE;
1094         if (node->nd_pkwrestarg == NODE_SPECIAL_NO_REST_KEYWORD) {
1095             F_MSG(nd_pkwrestarg, "keyword rest argument", "NODE_SPECIAL_NO_REST_KEYWORD (**nil)");
1096         }
1097         else {
1098             F_NODE(nd_pkwrestarg, "keyword rest argument");
1099         }
1100         return;
1101
1102       case NODE_ARGS_AUX:
1103       case NODE_LAST:
1104         break;
1105     }
1106
1107     rb_bug("dump_node: unknown node: %s", ruby_node_name(nd_type(node)));
1108 }
1109
1110 VALUE
1111 rb_parser_dump_tree(const NODE *node, int comment)
1112 {
1113     VALUE buf = rb_str_new_cstr(
1114         "###########################################################\n"
1115         "## Do NOT use this node dump for any purpose other than  ##\n"
1116         "## debug and research.  Compatibility is not guaranteed. ##\n"
1117         "###########################################################\n\n"
1118     );
1119     dump_node(buf, rb_str_new_cstr("# "), comment, node);
1120     return buf;
1121 }
1122
1123 /* Setup NODE structure.
1124  * NODE is not an object managed by GC, but it imitates an object
1125  * so that it can work with `RB_TYPE_P(obj, T_NODE)`.
1126  * This dirty hack is needed because Ripper jumbles NODEs and other type
1127  * objects.
1128  */
1129 void
1130 rb_node_init(NODE *n, enum node_type type, VALUE a0, VALUE a1, VALUE a2)
1131 {
1132     n->flags = T_NODE;
1133     nd_init_type(n, type);
1134     n->u1.value = a0;
1135     n->u2.value = a1;
1136     n->u3.value = a2;
1137     n->nd_loc.beg_pos.lineno = 0;
1138     n->nd_loc.beg_pos.column = 0;
1139     n->nd_loc.end_pos.lineno = 0;
1140     n->nd_loc.end_pos.column = 0;
1141 }
1142
1143 typedef struct node_buffer_elem_struct {
1144     struct node_buffer_elem_struct *next;
1145     long len;
1146     NODE buf[FLEX_ARY_LEN];
1147 } node_buffer_elem_t;
1148
1149 typedef struct {
1150     long idx, len;
1151     node_buffer_elem_t *head;
1152     node_buffer_elem_t *last;
1153 } node_buffer_list_t;
1154
1155 struct node_buffer_struct {
1156     node_buffer_list_t unmarkable;
1157     node_buffer_list_t markable;
1158     struct rb_ast_local_table_link *local_tables;
1159     VALUE mark_hash;
1160 };
1161
1162 static void
1163 init_node_buffer_list(node_buffer_list_t * nb, node_buffer_elem_t *head)
1164 {
1165     nb->idx = 0;
1166     nb->len = NODE_BUF_DEFAULT_LEN;
1167     nb->head = nb->last = head;
1168     nb->head->len = nb->len;
1169     nb->head->next = NULL;
1170 }
1171
1172 static node_buffer_t *
1173 rb_node_buffer_new(void)
1174 {
1175     const size_t bucket_size = offsetof(node_buffer_elem_t, buf) + NODE_BUF_DEFAULT_LEN * sizeof(NODE);
1176     const size_t alloc_size = sizeof(node_buffer_t) + (bucket_size * 2);
1177     STATIC_ASSERT(
1178         integer_overflow,
1179         offsetof(node_buffer_elem_t, buf) + NODE_BUF_DEFAULT_LEN * sizeof(NODE)
1180         > sizeof(node_buffer_t) + 2 * sizeof(node_buffer_elem_t));
1181     node_buffer_t *nb = ruby_xmalloc(alloc_size);
1182     init_node_buffer_list(&nb->unmarkable, (node_buffer_elem_t*)&nb[1]);
1183     init_node_buffer_list(&nb->markable, (node_buffer_elem_t*)((size_t)nb->unmarkable.head + bucket_size));
1184     nb->local_tables = 0;
1185     nb->mark_hash = Qnil;
1186     return nb;
1187 }
1188
1189 static void
1190 node_buffer_list_free(node_buffer_list_t * nb)
1191 {
1192     node_buffer_elem_t *nbe = nb->head;
1193
1194     while (nbe != nb->last) {
1195         void *buf = nbe;
1196         nbe = nbe->next;
1197         xfree(buf);
1198     }
1199 }
1200
1201 struct rb_ast_local_table_link {
1202     struct rb_ast_local_table_link *next;
1203     // struct rb_ast_id_table {
1204     int size;
1205     ID ids[FLEX_ARY_LEN];
1206     // }
1207 };
1208
1209 static void
1210 rb_node_buffer_free(node_buffer_t *nb)
1211 {
1212     node_buffer_list_free(&nb->unmarkable);
1213     node_buffer_list_free(&nb->markable);
1214     struct rb_ast_local_table_link *local_table = nb->local_tables;
1215     while (local_table) {
1216         struct rb_ast_local_table_link *next_table = local_table->next;
1217         xfree(local_table);
1218         local_table = next_table;
1219     }
1220     xfree(nb);
1221 }
1222
1223 static NODE *
1224 ast_newnode_in_bucket(node_buffer_list_t *nb)
1225 {
1226     if (nb->idx >= nb->len) {
1227         long n = nb->len * 2;
1228         node_buffer_elem_t *nbe;
1229         nbe = rb_xmalloc_mul_add(n, sizeof(NODE), offsetof(node_buffer_elem_t, buf));
1230         nbe->len = n;
1231         nb->idx = 0;
1232         nb->len = n;
1233         nbe->next = nb->head;
1234         nb->head = nbe;
1235     }
1236     return &nb->head->buf[nb->idx++];
1237 }
1238
1239 RBIMPL_ATTR_PURE()
1240 static bool
1241 nodetype_markable_p(enum node_type type)
1242 {
1243     switch (type) {
1244       case NODE_MATCH:
1245       case NODE_LIT:
1246       case NODE_STR:
1247       case NODE_XSTR:
1248       case NODE_DSTR:
1249       case NODE_DXSTR:
1250       case NODE_DREGX:
1251       case NODE_DSYM:
1252       case NODE_ARGS:
1253       case NODE_ARYPTN:
1254       case NODE_FNDPTN:
1255         return true;
1256       default:
1257         return false;
1258     }
1259 }
1260
1261 NODE *
1262 rb_ast_newnode(rb_ast_t *ast, enum node_type type)
1263 {
1264     node_buffer_t *nb = ast->node_buffer;
1265     node_buffer_list_t *bucket =
1266         (nodetype_markable_p(type) ? &nb->markable : &nb->unmarkable);
1267     return ast_newnode_in_bucket(bucket);
1268 }
1269
1270 void
1271 rb_ast_node_type_change(NODE *n, enum node_type type)
1272 {
1273     enum node_type old_type = nd_type(n);
1274     if (nodetype_markable_p(old_type) != nodetype_markable_p(type)) {
1275         rb_bug("node type changed: %s -> %s",
1276                ruby_node_name(old_type), ruby_node_name(type));
1277     }
1278 }
1279
1280 rb_ast_id_table_t *
1281 rb_ast_new_local_table(rb_ast_t *ast, int size)
1282 {
1283     size_t alloc_size = sizeof(struct rb_ast_local_table_link) + size * sizeof(ID);
1284     struct rb_ast_local_table_link *link = ruby_xmalloc(alloc_size);
1285     link->next = ast->node_buffer->local_tables;
1286     ast->node_buffer->local_tables = link;
1287     link->size = size;
1288
1289     return (rb_ast_id_table_t *) &link->size;
1290 }
1291
1292 rb_ast_id_table_t *
1293 rb_ast_resize_latest_local_table(rb_ast_t *ast, int size)
1294 {
1295     struct rb_ast_local_table_link *link = ast->node_buffer->local_tables;
1296     size_t alloc_size = sizeof(struct rb_ast_local_table_link) + size * sizeof(ID);
1297     link = ruby_xrealloc(link, alloc_size);
1298     ast->node_buffer->local_tables = link;
1299     link->size = size;
1300
1301     return (rb_ast_id_table_t *) &link->size;
1302 }
1303
1304 void
1305 rb_ast_delete_node(rb_ast_t *ast, NODE *n)
1306 {
1307     (void)ast;
1308     (void)n;
1309     /* should we implement freelist? */
1310 }
1311
1312 rb_ast_t *
1313 rb_ast_new(void)
1314 {
1315     node_buffer_t *nb = rb_node_buffer_new();
1316     rb_ast_t *ast = (rb_ast_t *)rb_imemo_new(imemo_ast, 0, 0, 0, (VALUE)nb);
1317     return ast;
1318 }
1319
1320 typedef void node_itr_t(void *ctx, NODE * node);
1321
1322 static void
1323 iterate_buffer_elements(node_buffer_elem_t *nbe, long len, node_itr_t *func, void *ctx)
1324 {
1325     long cursor;
1326     for (cursor = 0; cursor < len; cursor++) {
1327         func(ctx, &nbe->buf[cursor]);
1328     }
1329 }
1330
1331 static void
1332 iterate_node_values(node_buffer_list_t *nb, node_itr_t * func, void *ctx)
1333 {
1334     node_buffer_elem_t *nbe = nb->head;
1335
1336     /* iterate over the head first because it's not full */
1337     iterate_buffer_elements(nbe, nb->idx, func, ctx);
1338
1339     nbe = nbe->next;
1340     while (nbe) {
1341         iterate_buffer_elements(nbe, nbe->len, func, ctx);
1342         nbe = nbe->next;
1343     }
1344 }
1345
1346 static void
1347 mark_ast_value(void *ctx, NODE * node)
1348 {
1349     switch (nd_type(node)) {
1350       case NODE_ARGS:
1351         {
1352             struct rb_args_info *args = node->nd_ainfo;
1353             rb_gc_mark_movable(args->imemo);
1354             break;
1355         }
1356       case NODE_MATCH:
1357       case NODE_LIT:
1358       case NODE_STR:
1359       case NODE_XSTR:
1360       case NODE_DSTR:
1361       case NODE_DXSTR:
1362       case NODE_DREGX:
1363       case NODE_DSYM:
1364         rb_gc_mark_movable(node->nd_lit);
1365         break;
1366       case NODE_ARYPTN:
1367       case NODE_FNDPTN:
1368         rb_gc_mark_movable(node->nd_rval);
1369         break;
1370       default:
1371         rb_bug("unreachable node %s", ruby_node_name(nd_type(node)));
1372     }
1373 }
1374
1375 static void
1376 update_ast_value(void *ctx, NODE * node)
1377 {
1378     switch (nd_type(node)) {
1379       case NODE_ARGS:
1380         {
1381             struct rb_args_info *args = node->nd_ainfo;
1382             args->imemo = rb_gc_location(args->imemo);
1383             break;
1384         }
1385       case NODE_MATCH:
1386       case NODE_LIT:
1387       case NODE_STR:
1388       case NODE_XSTR:
1389       case NODE_DSTR:
1390       case NODE_DXSTR:
1391       case NODE_DREGX:
1392       case NODE_DSYM:
1393         node->nd_lit = rb_gc_location(node->nd_lit);
1394         break;
1395       case NODE_ARYPTN:
1396       case NODE_FNDPTN:
1397         node->nd_rval = rb_gc_location(node->nd_rval);
1398         break;
1399       default:
1400         rb_bug("unreachable");
1401     }
1402 }
1403
1404 void
1405 rb_ast_update_references(rb_ast_t *ast)
1406 {
1407     if (ast->node_buffer) {
1408         node_buffer_t *nb = ast->node_buffer;
1409
1410         iterate_node_values(&nb->markable, update_ast_value, NULL);
1411     }
1412 }
1413
1414 void
1415 rb_ast_mark(rb_ast_t *ast)
1416 {
1417     if (ast->node_buffer) rb_gc_mark(ast->node_buffer->mark_hash);
1418     if (ast->body.compile_option) rb_gc_mark(ast->body.compile_option);
1419     if (ast->node_buffer) {
1420         node_buffer_t *nb = ast->node_buffer;
1421
1422         iterate_node_values(&nb->markable, mark_ast_value, NULL);
1423     }
1424     if (ast->body.script_lines) rb_gc_mark(ast->body.script_lines);
1425 }
1426
1427 void
1428 rb_ast_free(rb_ast_t *ast)
1429 {
1430     if (ast->node_buffer) {
1431         rb_node_buffer_free(ast->node_buffer);
1432         ast->node_buffer = 0;
1433     }
1434 }
1435
1436 static size_t
1437 buffer_list_size(node_buffer_list_t *nb)
1438 {
1439     size_t size = 0;
1440     node_buffer_elem_t *nbe = nb->head;
1441     while (nbe != nb->last) {
1442         nbe = nbe->next;
1443         size += offsetof(node_buffer_elem_t, buf) + nb->len * sizeof(NODE);
1444     }
1445     return size;
1446 }
1447
1448 size_t
1449 rb_ast_memsize(const rb_ast_t *ast)
1450 {
1451     size_t size = 0;
1452     node_buffer_t *nb = ast->node_buffer;
1453
1454     if (nb) {
1455         size += sizeof(node_buffer_t) + offsetof(node_buffer_elem_t, buf) + NODE_BUF_DEFAULT_LEN * sizeof(NODE);
1456         size += buffer_list_size(&nb->unmarkable);
1457         size += buffer_list_size(&nb->markable);
1458     }
1459     return size;
1460 }
1461
1462 void
1463 rb_ast_dispose(rb_ast_t *ast)
1464 {
1465     rb_ast_free(ast);
1466 }
1467
1468 void
1469 rb_ast_add_mark_object(rb_ast_t *ast, VALUE obj)
1470 {
1471     if (NIL_P(ast->node_buffer->mark_hash)) {
1472         RB_OBJ_WRITE(ast, &ast->node_buffer->mark_hash, rb_ident_hash_new());
1473     }
1474     rb_hash_aset(ast->node_buffer->mark_hash, obj, Qtrue);
1475 }