ast.c

   1 /* indent-tabs-mode: nil */
   2 #include "internal.h"
   3 #include "internal/ruby_parser.h"
   4 #include "internal/symbol.h"
   5 #include "internal/warnings.h"
   6 #include "iseq.h"
   7 #include "node.h"
   8 #include "ruby.h"
   9 #include "ruby/encoding.h"
  10 #include "ruby/util.h"
  11 #include "vm_core.h"
  12
  13 #include "builtin.h"
  14
  15 static VALUE rb_mAST;
  16 static VALUE rb_cNode;
  17 static VALUE rb_cLocation;
  18
  19 struct ASTNodeData {
  20     VALUE ast_value;
  21     const NODE *node;
  22 };
  23
  24 static void
  25 node_gc_mark(void *ptr)
  26 {
  27     struct ASTNodeData *data = (struct ASTNodeData *)ptr;
  28     rb_gc_mark(data->ast_value);
  29 }
  30
  31 static size_t
  32 node_memsize(const void *ptr)
  33 {
  34     struct ASTNodeData *data = (struct ASTNodeData *)ptr;
  35     rb_ast_t *ast = rb_ruby_ast_data_get(data->ast_value);
  36
  37     return sizeof(struct ASTNodeData) + rb_ast_memsize(ast);
  38 }
  39
  40 static const rb_data_type_t rb_node_type = {
  41     "AST/node",
  42     {node_gc_mark, RUBY_TYPED_DEFAULT_FREE, node_memsize,},
  43     0, 0,
  44     RUBY_TYPED_FREE_IMMEDIATELY,
  45 };
  46
  47 struct ASTLocationData {
  48     int first_lineno;
  49     int first_column;
  50     int last_lineno;
  51     int last_column;
  52 };
  53
  54 static void
  55 location_gc_mark(void *ptr)
  56 {
  57 }
  58
  59 static size_t
  60 location_memsize(const void *ptr)
  61 {
  62     return sizeof(struct ASTLocationData);
  63 }
  64
  65 static const rb_data_type_t rb_location_type = {
  66     "AST/location",
  67     {location_gc_mark, RUBY_TYPED_DEFAULT_FREE, location_memsize,},
  68     0, 0,
  69     RUBY_TYPED_FREE_IMMEDIATELY,
  70 };
  71
  72
  73 static VALUE rb_ast_node_alloc(VALUE klass);
  74
  75 static void
  76 setup_node(VALUE obj, VALUE ast_value, const NODE *node)
  77 {
  78     struct ASTNodeData *data;
  79
  80     TypedData_Get_Struct(obj, struct ASTNodeData, &rb_node_type, data);
  81     data->ast_value = ast_value;
  82     data->node = node;
  83 }
  84
  85 static VALUE
  86 ast_new_internal(VALUE ast_value, const NODE *node)
  87 {
  88     VALUE obj;
  89
  90     obj = rb_ast_node_alloc(rb_cNode);
  91     setup_node(obj, ast_value, node);
  92
  93     return obj;
  94 }
  95
  96 static VALUE rb_ast_parse_str(VALUE str, VALUE keep_script_lines, VALUE error_tolerant, VALUE keep_tokens);
  97 static VALUE rb_ast_parse_file(VALUE path, VALUE keep_script_lines, VALUE error_tolerant, VALUE keep_tokens);
  98
  99 static VALUE
 100 ast_parse_new(void)
 101 {
 102     return rb_parser_set_context(rb_parser_new(), NULL, 0);
 103 }
 104
 105 static VALUE
 106 ast_parse_done(VALUE ast_value)
 107 {
 108     rb_ast_t *ast = rb_ruby_ast_data_get(ast_value);
 109
 110     if (!ast->body.root) {
 111         rb_ast_dispose(ast);
 112         rb_exc_raise(GET_EC()->errinfo);
 113     }
 114
 115     return ast_new_internal(ast_value, (NODE *)ast->body.root);
 116 }
 117
 118 static VALUE
 119 ast_s_parse(rb_execution_context_t *ec, VALUE module, VALUE str, VALUE keep_script_lines, VALUE error_tolerant, VALUE keep_tokens)
 120 {
 121     return rb_ast_parse_str(str, keep_script_lines, error_tolerant, keep_tokens);
 122 }
 123
 124 static VALUE
 125 rb_ast_parse_str(VALUE str, VALUE keep_script_lines, VALUE error_tolerant, VALUE keep_tokens)
 126 {
 127     VALUE ast_value;
 128
 129     StringValue(str);
 130     VALUE vparser = ast_parse_new();
 131     if (RTEST(keep_script_lines)) rb_parser_set_script_lines(vparser);
 132     if (RTEST(error_tolerant)) rb_parser_error_tolerant(vparser);
 133     if (RTEST(keep_tokens)) rb_parser_keep_tokens(vparser);
 134     ast_value = rb_parser_compile_string_path(vparser, Qnil, str, 1);
 135     return ast_parse_done(ast_value);
 136 }
 137
 138 static VALUE
 139 ast_s_parse_file(rb_execution_context_t *ec, VALUE module, VALUE path, VALUE keep_script_lines, VALUE error_tolerant, VALUE keep_tokens)
 140 {
 141     return rb_ast_parse_file(path, keep_script_lines, error_tolerant, keep_tokens);
 142 }
 143
 144 static VALUE
 145 rb_ast_parse_file(VALUE path, VALUE keep_script_lines, VALUE error_tolerant, VALUE keep_tokens)
 146 {
 147     VALUE f;
 148     VALUE ast_value = Qnil;
 149     rb_encoding *enc = rb_utf8_encoding();
 150
 151     f = rb_file_open_str(path, "r");
 152     rb_funcall(f, rb_intern("set_encoding"), 2, rb_enc_from_encoding(enc), rb_str_new_cstr("-"));
 153     VALUE vparser = ast_parse_new();
 154     if (RTEST(keep_script_lines)) rb_parser_set_script_lines(vparser);
 155     if (RTEST(error_tolerant))  rb_parser_error_tolerant(vparser);
 156     if (RTEST(keep_tokens))  rb_parser_keep_tokens(vparser);
 157     ast_value = rb_parser_compile_file_path(vparser, Qnil, f, 1);
 158     rb_io_close(f);
 159     return ast_parse_done(ast_value);
 160 }
 161
 162 static VALUE
 163 rb_ast_parse_array(VALUE array, VALUE keep_script_lines, VALUE error_tolerant, VALUE keep_tokens)
 164 {
 165     VALUE ast_value = Qnil;
 166
 167     array = rb_check_array_type(array);
 168     VALUE vparser = ast_parse_new();
 169     if (RTEST(keep_script_lines)) rb_parser_set_script_lines(vparser);
 170     if (RTEST(error_tolerant)) rb_parser_error_tolerant(vparser);
 171     if (RTEST(keep_tokens)) rb_parser_keep_tokens(vparser);
 172     ast_value = rb_parser_compile_array(vparser, Qnil, array, 1);
 173     return ast_parse_done(ast_value);
 174 }
 175
 176 static VALUE node_children(VALUE, const NODE*);
 177
 178 static VALUE
 179 node_find(VALUE self, const int node_id)
 180 {
 181     VALUE ary;
 182     long i;
 183     struct ASTNodeData *data;
 184     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 185
 186     if (nd_node_id(data->node) == node_id) return self;
 187
 188     ary = node_children(data->ast_value, data->node);
 189
 190     for (i = 0; i < RARRAY_LEN(ary); i++) {
 191         VALUE child = RARRAY_AREF(ary, i);
 192
 193         if (CLASS_OF(child) == rb_cNode) {
 194             VALUE result = node_find(child, node_id);
 195             if (RTEST(result)) return result;
 196         }
 197     }
 198
 199     return Qnil;
 200 }
 201
 202 extern VALUE rb_e_script;
 203
 204 static VALUE
 205 node_id_for_backtrace_location(rb_execution_context_t *ec, VALUE module, VALUE location)
 206 {
 207     int node_id;
 208
 209     if (!rb_frame_info_p(location)) {
 210         rb_raise(rb_eTypeError, "Thread::Backtrace::Location object expected");
 211     }
 212
 213     node_id = rb_get_node_id_from_frame_info(location);
 214     if (node_id == -1) {
 215         return Qnil;
 216     }
 217
 218     return INT2NUM(node_id);
 219 }
 220
 221 static VALUE
 222 ast_s_of(rb_execution_context_t *ec, VALUE module, VALUE body, VALUE keep_script_lines, VALUE error_tolerant, VALUE keep_tokens)
 223 {
 224     VALUE node, lines = Qnil;
 225     const rb_iseq_t *iseq;
 226     int node_id;
 227
 228     if (rb_frame_info_p(body)) {
 229         iseq = rb_get_iseq_from_frame_info(body);
 230         node_id = rb_get_node_id_from_frame_info(body);
 231     }
 232     else {
 233         iseq = NULL;
 234
 235         if (rb_obj_is_proc(body)) {
 236             iseq = vm_proc_iseq(body);
 237
 238             if (!rb_obj_is_iseq((VALUE)iseq)) return Qnil;
 239         }
 240         else {
 241             iseq = rb_method_iseq(body);
 242         }
 243         if (iseq) {
 244             node_id = ISEQ_BODY(iseq)->location.node_id;
 245         }
 246     }
 247
 248     if (!iseq) {
 249         return Qnil;
 250     }
 251
 252     if (ISEQ_BODY(iseq)->prism) {
 253         rb_raise(rb_eRuntimeError, "cannot get AST for ISEQ compiled by prism");
 254     }
 255
 256     lines = ISEQ_BODY(iseq)->variable.script_lines;
 257
 258     VALUE path = rb_iseq_path(iseq);
 259     int e_option = RSTRING_LEN(path) == 2 && memcmp(RSTRING_PTR(path), "-e", 2) == 0;
 260
 261     if (NIL_P(lines) && rb_iseq_from_eval_p(iseq) && !e_option) {
 262         rb_raise(rb_eArgError, "cannot get AST for method defined in eval");
 263     }
 264
 265     if (!NIL_P(lines)) {
 266         node = rb_ast_parse_array(lines, keep_script_lines, error_tolerant, keep_tokens);
 267     }
 268     else if (e_option) {
 269         node = rb_ast_parse_str(rb_e_script, keep_script_lines, error_tolerant, keep_tokens);
 270     }
 271     else {
 272         node = rb_ast_parse_file(path, keep_script_lines, error_tolerant, keep_tokens);
 273     }
 274
 275     return node_find(node, node_id);
 276 }
 277
 278 static VALUE
 279 rb_ast_node_alloc(VALUE klass)
 280 {
 281     struct ASTNodeData *data;
 282     VALUE obj = TypedData_Make_Struct(klass, struct ASTNodeData, &rb_node_type, data);
 283
 284     return obj;
 285 }
 286
 287 static const char*
 288 node_type_to_str(const NODE *node)
 289 {
 290     return (ruby_node_name(nd_type(node)) + rb_strlen_lit("NODE_"));
 291 }
 292
 293 static VALUE
 294 ast_node_type(rb_execution_context_t *ec, VALUE self)
 295 {
 296     struct ASTNodeData *data;
 297     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 298
 299     return rb_sym_intern_ascii_cstr(node_type_to_str(data->node));
 300 }
 301
 302 static VALUE
 303 ast_node_node_id(rb_execution_context_t *ec, VALUE self)
 304 {
 305     struct ASTNodeData *data;
 306     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 307
 308     return INT2FIX(nd_node_id(data->node));
 309 }
 310
 311 #define NEW_CHILD(ast_value, node) (node ? ast_new_internal(ast_value, node) : Qnil)
 312
 313 static VALUE
 314 rb_ary_new_from_node_args(VALUE ast_value, long n, ...)
 315 {
 316     va_list ar;
 317     VALUE ary;
 318     long i;
 319
 320     ary = rb_ary_new2(n);
 321
 322     va_start(ar, n);
 323     for (i=0; i<n; i++) {
 324         NODE *node;
 325         node = va_arg(ar, NODE *);
 326         rb_ary_push(ary, NEW_CHILD(ast_value, node));
 327     }
 328     va_end(ar);
 329     return ary;
 330 }
 331
 332 static VALUE
 333 dump_block(VALUE ast_value, const struct RNode_BLOCK *node)
 334 {
 335     VALUE ary = rb_ary_new();
 336     do {
 337         rb_ary_push(ary, NEW_CHILD(ast_value, node->nd_head));
 338     } while (node->nd_next &&
 339         nd_type_p(node->nd_next, NODE_BLOCK) &&
 340         (node = RNODE_BLOCK(node->nd_next), 1));
 341     if (node->nd_next) {
 342         rb_ary_push(ary, NEW_CHILD(ast_value, node->nd_next));
 343     }
 344
 345     return ary;
 346 }
 347
 348 static VALUE
 349 dump_array(VALUE ast_value, const struct RNode_LIST *node)
 350 {
 351     VALUE ary = rb_ary_new();
 352     rb_ary_push(ary, NEW_CHILD(ast_value, node->nd_head));
 353
 354     while (node->nd_next && nd_type_p(node->nd_next, NODE_LIST)) {
 355         node = RNODE_LIST(node->nd_next);
 356         rb_ary_push(ary, NEW_CHILD(ast_value, node->nd_head));
 357     }
 358     rb_ary_push(ary, NEW_CHILD(ast_value, node->nd_next));
 359
 360     return ary;
 361 }
 362
 363 static VALUE
 364 dump_parser_array(VALUE ast_value, rb_parser_ary_t *p_ary)
 365 {
 366     VALUE ary;
 367
 368     if (p_ary->data_type != PARSER_ARY_DATA_NODE) {
 369         rb_bug("unexpected rb_parser_ary_data_type: %d", p_ary->data_type);
 370     }
 371
 372     ary = rb_ary_new();
 373
 374     for (long i = 0; i < p_ary->len; i++) {
 375         rb_ary_push(ary, NEW_CHILD(ast_value, p_ary->data[i]));
 376     }
 377
 378     return ary;
 379 }
 380
 381 static VALUE
 382 var_name(ID id)
 383 {
 384     if (!id) return Qnil;
 385     if (!rb_id2str(id)) return Qnil;
 386     return ID2SYM(id);
 387 }
 388
 389 static VALUE
 390 no_name_rest(void)
 391 {
 392     ID rest;
 393     CONST_ID(rest, "NODE_SPECIAL_NO_NAME_REST");
 394     return ID2SYM(rest);
 395 }
 396
 397 static VALUE
 398 rest_arg(VALUE ast_value, const NODE *rest_arg)
 399 {
 400     return NODE_NAMED_REST_P(rest_arg) ? NEW_CHILD(ast_value, rest_arg) : no_name_rest();
 401 }
 402
 403 static VALUE
 404 node_children(VALUE ast_value, const NODE *node)
 405 {
 406     char name[sizeof("$") + DECIMAL_SIZE_OF(long)];
 407
 408     enum node_type type = nd_type(node);
 409     switch (type) {
 410       case NODE_BLOCK:
 411         return dump_block(ast_value, RNODE_BLOCK(node));
 412       case NODE_IF:
 413         return rb_ary_new_from_node_args(ast_value, 3, RNODE_IF(node)->nd_cond, RNODE_IF(node)->nd_body, RNODE_IF(node)->nd_else);
 414       case NODE_UNLESS:
 415         return rb_ary_new_from_node_args(ast_value, 3, RNODE_UNLESS(node)->nd_cond, RNODE_UNLESS(node)->nd_body, RNODE_UNLESS(node)->nd_else);
 416       case NODE_CASE:
 417         return rb_ary_new_from_node_args(ast_value, 2, RNODE_CASE(node)->nd_head, RNODE_CASE(node)->nd_body);
 418       case NODE_CASE2:
 419         return rb_ary_new_from_node_args(ast_value, 2, RNODE_CASE2(node)->nd_head, RNODE_CASE2(node)->nd_body);
 420       case NODE_CASE3:
 421         return rb_ary_new_from_node_args(ast_value, 2, RNODE_CASE3(node)->nd_head, RNODE_CASE3(node)->nd_body);
 422       case NODE_WHEN:
 423         return rb_ary_new_from_node_args(ast_value, 3, RNODE_WHEN(node)->nd_head, RNODE_WHEN(node)->nd_body, RNODE_WHEN(node)->nd_next);
 424       case NODE_IN:
 425         return rb_ary_new_from_node_args(ast_value, 3, RNODE_IN(node)->nd_head, RNODE_IN(node)->nd_body, RNODE_IN(node)->nd_next);
 426       case NODE_WHILE:
 427       case NODE_UNTIL:
 428         return rb_ary_push(rb_ary_new_from_node_args(ast_value, 2, RNODE_WHILE(node)->nd_cond, RNODE_WHILE(node)->nd_body),
 429                            RBOOL(RNODE_WHILE(node)->nd_state));
 430       case NODE_ITER:
 431       case NODE_FOR:
 432         return rb_ary_new_from_node_args(ast_value, 2, RNODE_ITER(node)->nd_iter, RNODE_ITER(node)->nd_body);
 433       case NODE_FOR_MASGN:
 434         return rb_ary_new_from_node_args(ast_value, 1, RNODE_FOR_MASGN(node)->nd_var);
 435       case NODE_BREAK:
 436         return rb_ary_new_from_node_args(ast_value, 1, RNODE_BREAK(node)->nd_stts);
 437       case NODE_NEXT:
 438         return rb_ary_new_from_node_args(ast_value, 1, RNODE_NEXT(node)->nd_stts);
 439       case NODE_RETURN:
 440         return rb_ary_new_from_node_args(ast_value, 1, RNODE_RETURN(node)->nd_stts);
 441       case NODE_REDO:
 442         return rb_ary_new_from_node_args(ast_value, 0);
 443       case NODE_RETRY:
 444         return rb_ary_new_from_node_args(ast_value, 0);
 445       case NODE_BEGIN:
 446         return rb_ary_new_from_node_args(ast_value, 1, RNODE_BEGIN(node)->nd_body);
 447       case NODE_RESCUE:
 448         return rb_ary_new_from_node_args(ast_value, 3, RNODE_RESCUE(node)->nd_head, RNODE_RESCUE(node)->nd_resq, RNODE_RESCUE(node)->nd_else);
 449       case NODE_RESBODY:
 450         return rb_ary_new_from_node_args(ast_value, 3, RNODE_RESBODY(node)->nd_args, RNODE_RESBODY(node)->nd_body, RNODE_RESBODY(node)->nd_next);
 451       case NODE_ENSURE:
 452         return rb_ary_new_from_node_args(ast_value, 2, RNODE_ENSURE(node)->nd_head, RNODE_ENSURE(node)->nd_ensr);
 453       case NODE_AND:
 454       case NODE_OR:
 455         {
 456             VALUE ary = rb_ary_new();
 457
 458             while (1) {
 459                 rb_ary_push(ary, NEW_CHILD(ast_value, RNODE_AND(node)->nd_1st));
 460                 if (!RNODE_AND(node)->nd_2nd || !nd_type_p(RNODE_AND(node)->nd_2nd, type))
 461                     break;
 462                 node = RNODE_AND(node)->nd_2nd;
 463             }
 464             rb_ary_push(ary, NEW_CHILD(ast_value, RNODE_AND(node)->nd_2nd));
 465             return ary;
 466         }
 467       case NODE_MASGN:
 468         if (NODE_NAMED_REST_P(RNODE_MASGN(node)->nd_args)) {
 469             return rb_ary_new_from_node_args(ast_value, 3, RNODE_MASGN(node)->nd_value, RNODE_MASGN(node)->nd_head, RNODE_MASGN(node)->nd_args);
 470         }
 471         else {
 472             return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_MASGN(node)->nd_value),
 473                                         NEW_CHILD(ast_value, RNODE_MASGN(node)->nd_head),
 474                                         no_name_rest());
 475         }
 476       case NODE_LASGN:
 477         if (NODE_REQUIRED_KEYWORD_P(RNODE_LASGN(node)->nd_value)) {
 478             return rb_ary_new_from_args(2, var_name(RNODE_LASGN(node)->nd_vid), ID2SYM(rb_intern("NODE_SPECIAL_REQUIRED_KEYWORD")));
 479         }
 480         return rb_ary_new_from_args(2, var_name(RNODE_LASGN(node)->nd_vid), NEW_CHILD(ast_value, RNODE_LASGN(node)->nd_value));
 481       case NODE_DASGN:
 482         if (NODE_REQUIRED_KEYWORD_P(RNODE_DASGN(node)->nd_value)) {
 483             return rb_ary_new_from_args(2, var_name(RNODE_DASGN(node)->nd_vid), ID2SYM(rb_intern("NODE_SPECIAL_REQUIRED_KEYWORD")));
 484         }
 485         return rb_ary_new_from_args(2, var_name(RNODE_DASGN(node)->nd_vid), NEW_CHILD(ast_value, RNODE_DASGN(node)->nd_value));
 486       case NODE_IASGN:
 487         return rb_ary_new_from_args(2, var_name(RNODE_IASGN(node)->nd_vid), NEW_CHILD(ast_value, RNODE_IASGN(node)->nd_value));
 488       case NODE_CVASGN:
 489         return rb_ary_new_from_args(2, var_name(RNODE_CVASGN(node)->nd_vid), NEW_CHILD(ast_value, RNODE_CVASGN(node)->nd_value));
 490       case NODE_GASGN:
 491         return rb_ary_new_from_args(2, var_name(RNODE_GASGN(node)->nd_vid), NEW_CHILD(ast_value, RNODE_GASGN(node)->nd_value));
 492       case NODE_CDECL:
 493         if (RNODE_CDECL(node)->nd_vid) {
 494             return rb_ary_new_from_args(2, ID2SYM(RNODE_CDECL(node)->nd_vid), NEW_CHILD(ast_value, RNODE_CDECL(node)->nd_value));
 495         }
 496         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_CDECL(node)->nd_else), ID2SYM(RNODE_COLON2(RNODE_CDECL(node)->nd_else)->nd_mid), NEW_CHILD(ast_value, RNODE_CDECL(node)->nd_value));
 497       case NODE_OP_ASGN1:
 498         return rb_ary_new_from_args(4, NEW_CHILD(ast_value, RNODE_OP_ASGN1(node)->nd_recv),
 499                                     ID2SYM(RNODE_OP_ASGN1(node)->nd_mid),
 500                                     NEW_CHILD(ast_value, RNODE_OP_ASGN1(node)->nd_index),
 501                                     NEW_CHILD(ast_value, RNODE_OP_ASGN1(node)->nd_rvalue));
 502       case NODE_OP_ASGN2:
 503         return rb_ary_new_from_args(5, NEW_CHILD(ast_value, RNODE_OP_ASGN2(node)->nd_recv),
 504                                     RBOOL(RNODE_OP_ASGN2(node)->nd_aid),
 505                                     ID2SYM(RNODE_OP_ASGN2(node)->nd_vid),
 506                                     ID2SYM(RNODE_OP_ASGN2(node)->nd_mid),
 507                                     NEW_CHILD(ast_value, RNODE_OP_ASGN2(node)->nd_value));
 508       case NODE_OP_ASGN_AND:
 509         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_OP_ASGN_AND(node)->nd_head), ID2SYM(idANDOP),
 510                                     NEW_CHILD(ast_value, RNODE_OP_ASGN_AND(node)->nd_value));
 511       case NODE_OP_ASGN_OR:
 512         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_OP_ASGN_OR(node)->nd_head), ID2SYM(idOROP),
 513                                     NEW_CHILD(ast_value, RNODE_OP_ASGN_OR(node)->nd_value));
 514       case NODE_OP_CDECL:
 515         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_OP_CDECL(node)->nd_head),
 516                                     ID2SYM(RNODE_OP_CDECL(node)->nd_aid),
 517                                     NEW_CHILD(ast_value, RNODE_OP_CDECL(node)->nd_value));
 518       case NODE_CALL:
 519         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_CALL(node)->nd_recv),
 520                                     ID2SYM(RNODE_CALL(node)->nd_mid),
 521                                     NEW_CHILD(ast_value, RNODE_CALL(node)->nd_args));
 522       case NODE_OPCALL:
 523         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_OPCALL(node)->nd_recv),
 524                                     ID2SYM(RNODE_OPCALL(node)->nd_mid),
 525                                     NEW_CHILD(ast_value, RNODE_OPCALL(node)->nd_args));
 526       case NODE_QCALL:
 527         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_QCALL(node)->nd_recv),
 528                                     ID2SYM(RNODE_QCALL(node)->nd_mid),
 529                                     NEW_CHILD(ast_value, RNODE_QCALL(node)->nd_args));
 530       case NODE_FCALL:
 531         return rb_ary_new_from_args(2, ID2SYM(RNODE_FCALL(node)->nd_mid),
 532                                     NEW_CHILD(ast_value, RNODE_FCALL(node)->nd_args));
 533       case NODE_VCALL:
 534         return rb_ary_new_from_args(1, ID2SYM(RNODE_VCALL(node)->nd_mid));
 535       case NODE_SUPER:
 536         return rb_ary_new_from_node_args(ast_value, 1, RNODE_SUPER(node)->nd_args);
 537       case NODE_ZSUPER:
 538         return rb_ary_new_from_node_args(ast_value, 0);
 539       case NODE_LIST:
 540         return dump_array(ast_value, RNODE_LIST(node));
 541       case NODE_ZLIST:
 542         return rb_ary_new_from_node_args(ast_value, 0);
 543       case NODE_HASH:
 544         return rb_ary_new_from_node_args(ast_value, 1, RNODE_HASH(node)->nd_head);
 545       case NODE_YIELD:
 546         return rb_ary_new_from_node_args(ast_value, 1, RNODE_YIELD(node)->nd_head);
 547       case NODE_LVAR:
 548         return rb_ary_new_from_args(1, var_name(RNODE_LVAR(node)->nd_vid));
 549       case NODE_DVAR:
 550         return rb_ary_new_from_args(1, var_name(RNODE_DVAR(node)->nd_vid));
 551       case NODE_IVAR:
 552         return rb_ary_new_from_args(1, ID2SYM(RNODE_IVAR(node)->nd_vid));
 553       case NODE_CONST:
 554         return rb_ary_new_from_args(1, ID2SYM(RNODE_CONST(node)->nd_vid));
 555       case NODE_CVAR:
 556         return rb_ary_new_from_args(1, ID2SYM(RNODE_CVAR(node)->nd_vid));
 557       case NODE_GVAR:
 558         return rb_ary_new_from_args(1, ID2SYM(RNODE_GVAR(node)->nd_vid));
 559       case NODE_NTH_REF:
 560         snprintf(name, sizeof(name), "$%ld", RNODE_NTH_REF(node)->nd_nth);
 561         return rb_ary_new_from_args(1, ID2SYM(rb_intern(name)));
 562       case NODE_BACK_REF:
 563         name[0] = '$';
 564         name[1] = (char)RNODE_BACK_REF(node)->nd_nth;
 565         name[2] = '\0';
 566         return rb_ary_new_from_args(1, ID2SYM(rb_intern(name)));
 567       case NODE_MATCH:
 568         return rb_ary_new_from_args(1, rb_node_regx_string_val(node));
 569       case NODE_MATCH2:
 570         if (RNODE_MATCH2(node)->nd_args) {
 571             return rb_ary_new_from_node_args(ast_value, 3, RNODE_MATCH2(node)->nd_recv, RNODE_MATCH2(node)->nd_value, RNODE_MATCH2(node)->nd_args);
 572         }
 573         return rb_ary_new_from_node_args(ast_value, 2, RNODE_MATCH2(node)->nd_recv, RNODE_MATCH2(node)->nd_value);
 574       case NODE_MATCH3:
 575         return rb_ary_new_from_node_args(ast_value, 2, RNODE_MATCH3(node)->nd_recv, RNODE_MATCH3(node)->nd_value);
 576       case NODE_STR:
 577       case NODE_XSTR:
 578         return rb_ary_new_from_args(1, rb_node_str_string_val(node));
 579       case NODE_INTEGER:
 580         return rb_ary_new_from_args(1, rb_node_integer_literal_val(node));
 581       case NODE_FLOAT:
 582         return rb_ary_new_from_args(1, rb_node_float_literal_val(node));
 583       case NODE_RATIONAL:
 584         return rb_ary_new_from_args(1, rb_node_rational_literal_val(node));
 585       case NODE_IMAGINARY:
 586         return rb_ary_new_from_args(1, rb_node_imaginary_literal_val(node));
 587       case NODE_REGX:
 588         return rb_ary_new_from_args(1, rb_node_regx_string_val(node));
 589       case NODE_ONCE:
 590         return rb_ary_new_from_node_args(ast_value, 1, RNODE_ONCE(node)->nd_body);
 591       case NODE_DSTR:
 592       case NODE_DXSTR:
 593       case NODE_DREGX:
 594       case NODE_DSYM:
 595         {
 596             struct RNode_LIST *n = RNODE_DSTR(node)->nd_next;
 597             VALUE head = Qnil, next = Qnil;
 598             if (n) {
 599                 head = NEW_CHILD(ast_value, n->nd_head);
 600                 next = NEW_CHILD(ast_value, n->nd_next);
 601             }
 602             return rb_ary_new_from_args(3, rb_node_dstr_string_val(node), head, next);
 603         }
 604       case NODE_SYM:
 605         return rb_ary_new_from_args(1, rb_node_sym_string_val(node));
 606       case NODE_EVSTR:
 607         return rb_ary_new_from_node_args(ast_value, 1, RNODE_EVSTR(node)->nd_body);
 608       case NODE_ARGSCAT:
 609         return rb_ary_new_from_node_args(ast_value, 2, RNODE_ARGSCAT(node)->nd_head, RNODE_ARGSCAT(node)->nd_body);
 610       case NODE_ARGSPUSH:
 611         return rb_ary_new_from_node_args(ast_value, 2, RNODE_ARGSPUSH(node)->nd_head, RNODE_ARGSPUSH(node)->nd_body);
 612       case NODE_SPLAT:
 613         return rb_ary_new_from_node_args(ast_value, 1, RNODE_SPLAT(node)->nd_head);
 614       case NODE_BLOCK_PASS:
 615         return rb_ary_new_from_node_args(ast_value, 2, RNODE_BLOCK_PASS(node)->nd_head, RNODE_BLOCK_PASS(node)->nd_body);
 616       case NODE_DEFN:
 617         return rb_ary_new_from_args(2, ID2SYM(RNODE_DEFN(node)->nd_mid), NEW_CHILD(ast_value, RNODE_DEFN(node)->nd_defn));
 618       case NODE_DEFS:
 619         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_DEFS(node)->nd_recv), ID2SYM(RNODE_DEFS(node)->nd_mid), NEW_CHILD(ast_value, RNODE_DEFS(node)->nd_defn));
 620       case NODE_ALIAS:
 621         return rb_ary_new_from_node_args(ast_value, 2, RNODE_ALIAS(node)->nd_1st, RNODE_ALIAS(node)->nd_2nd);
 622       case NODE_VALIAS:
 623         return rb_ary_new_from_args(2, ID2SYM(RNODE_VALIAS(node)->nd_alias), ID2SYM(RNODE_VALIAS(node)->nd_orig));
 624       case NODE_UNDEF:
 625         return rb_ary_new_from_args(1, dump_parser_array(ast_value, RNODE_UNDEF(node)->nd_undefs));
 626       case NODE_CLASS:
 627         return rb_ary_new_from_node_args(ast_value, 3, RNODE_CLASS(node)->nd_cpath, RNODE_CLASS(node)->nd_super, RNODE_CLASS(node)->nd_body);
 628       case NODE_MODULE:
 629         return rb_ary_new_from_node_args(ast_value, 2, RNODE_MODULE(node)->nd_cpath, RNODE_MODULE(node)->nd_body);
 630       case NODE_SCLASS:
 631         return rb_ary_new_from_node_args(ast_value, 2, RNODE_SCLASS(node)->nd_recv, RNODE_SCLASS(node)->nd_body);
 632       case NODE_COLON2:
 633         return rb_ary_new_from_args(2, NEW_CHILD(ast_value, RNODE_COLON2(node)->nd_head), ID2SYM(RNODE_COLON2(node)->nd_mid));
 634       case NODE_COLON3:
 635         return rb_ary_new_from_args(1, ID2SYM(RNODE_COLON3(node)->nd_mid));
 636       case NODE_DOT2:
 637       case NODE_DOT3:
 638       case NODE_FLIP2:
 639       case NODE_FLIP3:
 640         return rb_ary_new_from_node_args(ast_value, 2, RNODE_DOT2(node)->nd_beg, RNODE_DOT2(node)->nd_end);
 641       case NODE_SELF:
 642         return rb_ary_new_from_node_args(ast_value, 0);
 643       case NODE_NIL:
 644         return rb_ary_new_from_node_args(ast_value, 0);
 645       case NODE_TRUE:
 646         return rb_ary_new_from_node_args(ast_value, 0);
 647       case NODE_FALSE:
 648         return rb_ary_new_from_node_args(ast_value, 0);
 649       case NODE_ERRINFO:
 650         return rb_ary_new_from_node_args(ast_value, 0);
 651       case NODE_DEFINED:
 652         return rb_ary_new_from_node_args(ast_value, 1, RNODE_DEFINED(node)->nd_head);
 653       case NODE_POSTEXE:
 654         return rb_ary_new_from_node_args(ast_value, 1, RNODE_POSTEXE(node)->nd_body);
 655       case NODE_ATTRASGN:
 656         return rb_ary_new_from_args(3, NEW_CHILD(ast_value, RNODE_ATTRASGN(node)->nd_recv), ID2SYM(RNODE_ATTRASGN(node)->nd_mid), NEW_CHILD(ast_value, RNODE_ATTRASGN(node)->nd_args));
 657       case NODE_LAMBDA:
 658         return rb_ary_new_from_node_args(ast_value, 1, RNODE_LAMBDA(node)->nd_body);
 659       case NODE_OPT_ARG:
 660         return rb_ary_new_from_node_args(ast_value, 2, RNODE_OPT_ARG(node)->nd_body, RNODE_OPT_ARG(node)->nd_next);
 661       case NODE_KW_ARG:
 662         return rb_ary_new_from_node_args(ast_value, 2, RNODE_KW_ARG(node)->nd_body, RNODE_KW_ARG(node)->nd_next);
 663       case NODE_POSTARG:
 664         if (NODE_NAMED_REST_P(RNODE_POSTARG(node)->nd_1st)) {
 665             return rb_ary_new_from_node_args(ast_value, 2, RNODE_POSTARG(node)->nd_1st, RNODE_POSTARG(node)->nd_2nd);
 666         }
 667         return rb_ary_new_from_args(2, no_name_rest(),
 668                                     NEW_CHILD(ast_value, RNODE_POSTARG(node)->nd_2nd));
 669       case NODE_ARGS:
 670         {
 671             struct rb_args_info *ainfo = &RNODE_ARGS(node)->nd_ainfo;
 672             return rb_ary_new_from_args(10,
 673                                         INT2NUM(ainfo->pre_args_num),
 674                                         NEW_CHILD(ast_value, ainfo->pre_init),
 675                                         NEW_CHILD(ast_value, (NODE *)ainfo->opt_args),
 676                                         var_name(ainfo->first_post_arg),
 677                                         INT2NUM(ainfo->post_args_num),
 678                                         NEW_CHILD(ast_value, ainfo->post_init),
 679                                         (ainfo->rest_arg == NODE_SPECIAL_EXCESSIVE_COMMA
 680                                             ? ID2SYM(rb_intern("NODE_SPECIAL_EXCESSIVE_COMMA"))
 681                                             : var_name(ainfo->rest_arg)),
 682                                         (ainfo->no_kwarg ? Qfalse : NEW_CHILD(ast_value, (NODE *)ainfo->kw_args)),
 683                                         (ainfo->no_kwarg ? Qfalse : NEW_CHILD(ast_value, ainfo->kw_rest_arg)),
 684                                         var_name(ainfo->block_arg));
 685         }
 686       case NODE_SCOPE:
 687         {
 688             rb_ast_id_table_t *tbl = RNODE_SCOPE(node)->nd_tbl;
 689             int i, size = tbl ? tbl->size : 0;
 690             VALUE locals = rb_ary_new_capa(size);
 691             for (i = 0; i < size; i++) {
 692                 rb_ary_push(locals, var_name(tbl->ids[i]));
 693             }
 694             return rb_ary_new_from_args(3, locals, NEW_CHILD(ast_value, (NODE *)RNODE_SCOPE(node)->nd_args), NEW_CHILD(ast_value, RNODE_SCOPE(node)->nd_body));
 695         }
 696       case NODE_ARYPTN:
 697         {
 698             VALUE rest = rest_arg(ast_value, RNODE_ARYPTN(node)->rest_arg);
 699             return rb_ary_new_from_args(4,
 700                                         NEW_CHILD(ast_value, RNODE_ARYPTN(node)->nd_pconst),
 701                                         NEW_CHILD(ast_value, RNODE_ARYPTN(node)->pre_args),
 702                                         rest,
 703                                         NEW_CHILD(ast_value, RNODE_ARYPTN(node)->post_args));
 704         }
 705       case NODE_FNDPTN:
 706         {
 707             VALUE pre_rest = rest_arg(ast_value, RNODE_FNDPTN(node)->pre_rest_arg);
 708             VALUE post_rest = rest_arg(ast_value, RNODE_FNDPTN(node)->post_rest_arg);
 709             return rb_ary_new_from_args(4,
 710                                         NEW_CHILD(ast_value, RNODE_FNDPTN(node)->nd_pconst),
 711                                         pre_rest,
 712                                         NEW_CHILD(ast_value, RNODE_FNDPTN(node)->args),
 713                                         post_rest);
 714         }
 715       case NODE_HSHPTN:
 716         {
 717             VALUE kwrest = RNODE_HSHPTN(node)->nd_pkwrestarg == NODE_SPECIAL_NO_REST_KEYWORD ? ID2SYM(rb_intern("NODE_SPECIAL_NO_REST_KEYWORD")) :
 718                                                                                  NEW_CHILD(ast_value, RNODE_HSHPTN(node)->nd_pkwrestarg);
 719
 720             return rb_ary_new_from_args(3,
 721                                         NEW_CHILD(ast_value, RNODE_HSHPTN(node)->nd_pconst),
 722                                         NEW_CHILD(ast_value, RNODE_HSHPTN(node)->nd_pkwargs),
 723                                         kwrest);
 724         }
 725       case NODE_LINE:
 726         return rb_ary_new_from_args(1, rb_node_line_lineno_val(node));
 727       case NODE_FILE:
 728         return rb_ary_new_from_args(1, rb_node_file_path_val(node));
 729       case NODE_ENCODING:
 730         return rb_ary_new_from_args(1, rb_node_encoding_val(node));
 731       case NODE_ERROR:
 732         return rb_ary_new_from_node_args(ast_value, 0);
 733       case NODE_ARGS_AUX:
 734       case NODE_LAST:
 735         break;
 736     }
 737
 738     rb_bug("node_children: unknown node: %s", ruby_node_name(type));
 739 }
 740
 741 static VALUE
 742 ast_node_children(rb_execution_context_t *ec, VALUE self)
 743 {
 744     struct ASTNodeData *data;
 745     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 746
 747     return node_children(data->ast_value, data->node);
 748 }
 749
 750 static int
 751 null_loc_p(rb_code_location_t *loc)
 752 {
 753     return (loc->beg_pos.lineno == 0 && loc->beg_pos.column == -1 && loc->end_pos.lineno == 0 && loc->end_pos.column == -1);
 754 }
 755
 756 static VALUE
 757 location_new(rb_code_location_t *loc)
 758 {
 759     VALUE obj;
 760     struct ASTLocationData *data;
 761
 762     if (null_loc_p(loc)) return Qnil;
 763
 764     obj = TypedData_Make_Struct(rb_cLocation, struct ASTLocationData, &rb_location_type, data);
 765     data->first_lineno = loc->beg_pos.lineno;
 766     data->first_column = loc->beg_pos.column;
 767     data->last_lineno = loc->end_pos.lineno;
 768     data->last_column = loc->end_pos.column;
 769
 770     return obj;
 771 }
 772
 773 static VALUE
 774 node_locations(VALUE ast_value, const NODE *node)
 775 {
 776     enum node_type type = nd_type(node);
 777     switch (type) {
 778       case NODE_UNLESS:
 779         return rb_ary_new_from_args(4,
 780                                     location_new(nd_code_loc(node)),
 781                                     location_new(&RNODE_UNLESS(node)->keyword_loc),
 782                                     location_new(&RNODE_UNLESS(node)->then_keyword_loc),
 783                                     location_new(&RNODE_UNLESS(node)->end_keyword_loc));
 784       case NODE_ARGS_AUX:
 785       case NODE_LAST:
 786         break;
 787       default:
 788         return rb_ary_new_from_args(1, location_new(nd_code_loc(node)));
 789     }
 790
 791     rb_bug("node_locations: unknown node: %s", ruby_node_name(type));
 792 }
 793
 794 static VALUE
 795 ast_node_locations(rb_execution_context_t *ec, VALUE self)
 796 {
 797     struct ASTNodeData *data;
 798     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 799
 800     return node_locations(data->ast_value, data->node);
 801 }
 802
 803 static VALUE
 804 ast_node_first_lineno(rb_execution_context_t *ec, VALUE self)
 805 {
 806     struct ASTNodeData *data;
 807     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 808
 809     return INT2NUM(nd_first_lineno(data->node));
 810 }
 811
 812 static VALUE
 813 ast_node_first_column(rb_execution_context_t *ec, VALUE self)
 814 {
 815     struct ASTNodeData *data;
 816     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 817
 818     return INT2NUM(nd_first_column(data->node));
 819 }
 820
 821 static VALUE
 822 ast_node_last_lineno(rb_execution_context_t *ec, VALUE self)
 823 {
 824     struct ASTNodeData *data;
 825     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 826
 827     return INT2NUM(nd_last_lineno(data->node));
 828 }
 829
 830 static VALUE
 831 ast_node_last_column(rb_execution_context_t *ec, VALUE self)
 832 {
 833     struct ASTNodeData *data;
 834     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 835
 836     return INT2NUM(nd_last_column(data->node));
 837 }
 838
 839 static VALUE
 840 ast_node_all_tokens(rb_execution_context_t *ec, VALUE self)
 841 {
 842     long i;
 843     struct ASTNodeData *data;
 844     rb_ast_t *ast;
 845     rb_parser_ary_t *parser_tokens;
 846     rb_parser_ast_token_t *parser_token;
 847     VALUE str, loc, token, all_tokens;
 848
 849     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 850     ast = rb_ruby_ast_data_get(data->ast_value);
 851
 852     parser_tokens = ast->node_buffer->tokens;
 853     if (parser_tokens == NULL) {
 854         return Qnil;
 855     }
 856
 857     all_tokens = rb_ary_new2(parser_tokens->len);
 858     for (i = 0; i < parser_tokens->len; i++) {
 859         parser_token = parser_tokens->data[i];
 860         str = rb_str_new(parser_token->str->ptr, parser_token->str->len);
 861         loc = rb_ary_new_from_args(4,
 862             INT2FIX(parser_token->loc.beg_pos.lineno),
 863             INT2FIX(parser_token->loc.beg_pos.column),
 864             INT2FIX(parser_token->loc.end_pos.lineno),
 865             INT2FIX(parser_token->loc.end_pos.column)
 866         );
 867         token = rb_ary_new_from_args(4, INT2FIX(parser_token->id), ID2SYM(rb_intern(parser_token->type_name)), str, loc);
 868         rb_ary_push(all_tokens, token);
 869     }
 870     rb_ary_freeze(all_tokens);
 871
 872     return all_tokens;
 873 }
 874
 875 static VALUE
 876 ast_node_inspect(rb_execution_context_t *ec, VALUE self)
 877 {
 878     VALUE str;
 879     VALUE cname;
 880     struct ASTNodeData *data;
 881     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 882
 883     cname = rb_class_path(rb_obj_class(self));
 884     str = rb_str_new2("#<");
 885
 886     rb_str_append(str, cname);
 887     rb_str_catf(str, ":%s@%d:%d-%d:%d>",
 888                 node_type_to_str(data->node),
 889                 nd_first_lineno(data->node), nd_first_column(data->node),
 890                 nd_last_lineno(data->node), nd_last_column(data->node));
 891
 892     return str;
 893 }
 894
 895 static VALUE
 896 ast_node_script_lines(rb_execution_context_t *ec, VALUE self)
 897 {
 898     struct ASTNodeData *data;
 899     rb_ast_t *ast;
 900     TypedData_Get_Struct(self, struct ASTNodeData, &rb_node_type, data);
 901     ast = rb_ruby_ast_data_get(data->ast_value);
 902     rb_parser_ary_t *ret = ast->body.script_lines;
 903     return rb_parser_build_script_lines_from(ret);
 904 }
 905
 906 static VALUE
 907 ast_location_first_lineno(rb_execution_context_t *ec, VALUE self)
 908 {
 909     struct ASTLocationData *data;
 910     TypedData_Get_Struct(self, struct ASTLocationData, &rb_location_type, data);
 911
 912     return INT2NUM(data->first_lineno);
 913 }
 914
 915 static VALUE
 916 ast_location_first_column(rb_execution_context_t *ec, VALUE self)
 917 {
 918     struct ASTLocationData *data;
 919     TypedData_Get_Struct(self, struct ASTLocationData, &rb_location_type, data);
 920
 921     return INT2NUM(data->first_column);
 922 }
 923
 924 static VALUE
 925 ast_location_last_lineno(rb_execution_context_t *ec, VALUE self)
 926 {
 927     struct ASTLocationData *data;
 928     TypedData_Get_Struct(self, struct ASTLocationData, &rb_location_type, data);
 929
 930     return INT2NUM(data->last_lineno);
 931 }
 932
 933 static VALUE
 934 ast_location_last_column(rb_execution_context_t *ec, VALUE self)
 935 {
 936     struct ASTLocationData *data;
 937     TypedData_Get_Struct(self, struct ASTLocationData, &rb_location_type, data);
 938
 939     return INT2NUM(data->last_column);
 940 }
 941
 942 static VALUE
 943 ast_location_inspect(rb_execution_context_t *ec, VALUE self)
 944 {
 945     VALUE str;
 946     VALUE cname;
 947     struct ASTLocationData *data;
 948     TypedData_Get_Struct(self, struct ASTLocationData, &rb_location_type, data);
 949
 950     cname = rb_class_path(rb_obj_class(self));
 951     str = rb_str_new2("#<");
 952
 953     rb_str_append(str, cname);
 954     rb_str_catf(str, ":@%d:%d-%d:%d>",
 955                 data->first_lineno, data->first_column,
 956                 data->last_lineno, data->last_column);
 957
 958     return str;
 959 }
 960
 961 #include "ast.rbinc"
 962
 963 void
 964 Init_ast(void)
 965 {
 966     rb_mAST = rb_define_module_under(rb_cRubyVM, "AbstractSyntaxTree");
 967     rb_cNode = rb_define_class_under(rb_mAST, "Node", rb_cObject);
 968     rb_cLocation = rb_define_class_under(rb_mAST, "Location", rb_cObject);
 969     rb_undef_alloc_func(rb_cNode);
 970     rb_undef_alloc_func(rb_cLocation);
 971 }