class.c

Go to the documentation of this file.

/**********************************************************************

  class.c -

  $Author: nagachika $
  created at: Tue Aug 10 15:05:44 JST 1993

  Copyright (C) 1993-2007 Yukihiro Matsumoto

**********************************************************************/

#include "ruby/ruby.h"
#include "ruby/st.h"
#include "method.h"
#include "constant.h"
#include "vm_core.h"
#include "internal.h"
#include <ctype.h>

int rb_vm_add_root_module(ID id, VALUE module);


#define id_attached id__attached__

void
rb_class_subclass_add(VALUE super, VALUE klass)
{
    rb_subclass_entry_t *entry, *head;

    if (super && super != Qundef) {
        entry = xmalloc(sizeof(*entry));
        entry->klass = klass;
        entry->next = NULL;

        head = RCLASS_EXT(super)->subclasses;
        if (head) {
            entry->next = head;
            RCLASS_EXT(head->klass)->parent_subclasses = &entry->next;
        }

        RCLASS_EXT(super)->subclasses = entry;
        RCLASS_EXT(klass)->parent_subclasses = &RCLASS_EXT(super)->subclasses;
    }
}

static void
rb_module_add_to_subclasses_list(VALUE module, VALUE iclass)
{
    rb_subclass_entry_t *entry, *head;

    entry = xmalloc(sizeof(*entry));
    entry->klass = iclass;
    entry->next = NULL;

    head = RCLASS_EXT(module)->subclasses;
    if (head) {
        entry->next = head;
        RCLASS_EXT(head->klass)->module_subclasses = &entry->next;
    }

    RCLASS_EXT(module)->subclasses = entry;
    RCLASS_EXT(iclass)->module_subclasses = &RCLASS_EXT(module)->subclasses;
}

void
rb_class_remove_from_super_subclasses(VALUE klass)
{
    rb_subclass_entry_t *entry;

    if (RCLASS_EXT(klass)->parent_subclasses) {
        entry = *RCLASS_EXT(klass)->parent_subclasses;

        *RCLASS_EXT(klass)->parent_subclasses = entry->next;
        if (entry->next) {
            RCLASS_EXT(entry->next->klass)->parent_subclasses = RCLASS_EXT(klass)->parent_subclasses;
        }
        xfree(entry);
    }

    RCLASS_EXT(klass)->parent_subclasses = NULL;
}

void
rb_class_remove_from_module_subclasses(VALUE klass)
{
    rb_subclass_entry_t *entry;

    if (RCLASS_EXT(klass)->module_subclasses) {
        entry = *RCLASS_EXT(klass)->module_subclasses;
        *RCLASS_EXT(klass)->module_subclasses = entry->next;

        if (entry->next) {
            RCLASS_EXT(entry->next->klass)->module_subclasses = RCLASS_EXT(klass)->module_subclasses;
        }

        xfree(entry);
    }

    RCLASS_EXT(klass)->module_subclasses = NULL;
}

void
rb_class_foreach_subclass(VALUE klass, void(*f)(VALUE))
{
    rb_subclass_entry_t *cur = RCLASS_EXT(klass)->subclasses;

    /* do not be tempted to simplify this loop into a for loop, the order of
       operations is important here if `f` modifies the linked list */
    while (cur) {
        VALUE curklass = cur->klass;
        cur = cur->next;
        f(curklass);
    }
}

void
rb_class_detach_subclasses(VALUE klass)
{
    rb_class_foreach_subclass(klass, rb_class_remove_from_super_subclasses);
}

void
rb_class_detach_module_subclasses(VALUE klass)
{
    rb_class_foreach_subclass(klass, rb_class_remove_from_module_subclasses);
}

static VALUE
class_alloc(VALUE flags, VALUE klass)
{
    NEWOBJ_OF(obj, struct RClass, klass, (flags & T_MASK) | (RGENGC_WB_PROTECTED_CLASS ? FL_WB_PROTECTED : 0));
    obj->ptr = ALLOC(rb_classext_t);
    RCLASS_IV_TBL(obj) = 0;
    RCLASS_CONST_TBL(obj) = 0;
    RCLASS_M_TBL_WRAPPER(obj) = 0;
    RCLASS_SET_SUPER((VALUE)obj, 0);
    RCLASS_ORIGIN(obj) = (VALUE)obj;
    RCLASS_IV_INDEX_TBL(obj) = 0;

    RCLASS_EXT(obj)->subclasses = NULL;
    RCLASS_EXT(obj)->parent_subclasses = NULL;
    RCLASS_EXT(obj)->module_subclasses = NULL;
    RCLASS_SERIAL(obj) = rb_next_class_serial();

    RCLASS_REFINED_CLASS(obj) = Qnil;
    RCLASS_EXT(obj)->allocator = 0;
    return (VALUE)obj;
}


VALUE
rb_class_boot(VALUE super)
{
    VALUE klass = class_alloc(T_CLASS, rb_cClass);

    RCLASS_SET_SUPER(klass, super);
    RCLASS_M_TBL_INIT(klass);

    OBJ_INFECT(klass, super);
    return (VALUE)klass;
}


void
rb_check_inheritable(VALUE super)
{
    if (!RB_TYPE_P(super, T_CLASS)) {
        rb_raise(rb_eTypeError, "superclass must be a Class (%s given)",
                 rb_obj_classname(super));
    }
    if (RBASIC(super)->flags & FL_SINGLETON) {
        rb_raise(rb_eTypeError, "can't make subclass of singleton class");
    }
    if (super == rb_cClass) {
        rb_raise(rb_eTypeError, "can't make subclass of Class");
    }
}


VALUE
rb_class_new(VALUE super)
{
    Check_Type(super, T_CLASS);
    rb_check_inheritable(super);
    return rb_class_boot(super);
}

static void
rewrite_cref_stack(NODE *node, VALUE old_klass, VALUE new_klass, NODE **new_cref_ptr)
{
    NODE *new_node;
    while (node) {
        if (node->nd_clss == old_klass) {
            new_node = NEW_CREF(new_klass);
            RB_OBJ_WRITE(new_node, &new_node->nd_next, node->nd_next);
            *new_cref_ptr = new_node;
            return;
        }
        new_node = NEW_CREF(node->nd_clss);
        node = node->nd_next;
        *new_cref_ptr = new_node;
        new_cref_ptr = &new_node->nd_next;
    }
    *new_cref_ptr = NULL;
}

static void
clone_method(VALUE klass, ID mid, const rb_method_entry_t *me)
{
    VALUE newiseqval;
    if (me->def && me->def->type == VM_METHOD_TYPE_ISEQ) {
        rb_iseq_t *iseq;
        NODE *new_cref;
        newiseqval = rb_iseq_clone(me->def->body.iseq->self, klass);
        GetISeqPtr(newiseqval, iseq);
        rewrite_cref_stack(me->def->body.iseq->cref_stack, me->klass, klass, &new_cref);
        RB_OBJ_WRITE(iseq->self, &iseq->cref_stack, new_cref);
        rb_add_method(klass, mid, VM_METHOD_TYPE_ISEQ, iseq, me->flag);
        RB_GC_GUARD(newiseqval);
    }
    else {
        rb_method_entry_set(klass, mid, me, me->flag);
    }
}

static int
clone_method_i(st_data_t key, st_data_t value, st_data_t data)
{
    clone_method((VALUE)data, (ID)key, (const rb_method_entry_t *)value);
    return ST_CONTINUE;
}

struct clone_const_arg {
    VALUE klass;
    st_table *tbl;
};

static int
clone_const(ID key, const rb_const_entry_t *ce, struct clone_const_arg *arg)
{
    rb_const_entry_t *nce = ALLOC(rb_const_entry_t);
    MEMCPY(nce, ce, rb_const_entry_t, 1);
    RB_OBJ_WRITTEN(arg->klass, Qundef, ce->value);
    RB_OBJ_WRITTEN(arg->klass, Qundef, ce->file);

    st_insert(arg->tbl, key, (st_data_t)nce);
    return ST_CONTINUE;
}

static int
clone_const_i(st_data_t key, st_data_t value, st_data_t data)
{
    return clone_const((ID)key, (const rb_const_entry_t *)value, (struct clone_const_arg *)data);
}

static void
class_init_copy_check(VALUE clone, VALUE orig)
{
    if (orig == rb_cBasicObject) {
        rb_raise(rb_eTypeError, "can't copy the root class");
    }
    if (RCLASS_SUPER(clone) != 0 || clone == rb_cBasicObject) {
        rb_raise(rb_eTypeError, "already initialized class");
    }
    if (FL_TEST(orig, FL_SINGLETON)) {
        rb_raise(rb_eTypeError, "can't copy singleton class");
    }
}

/* :nodoc: */
VALUE
rb_mod_init_copy(VALUE clone, VALUE orig)
{
    if (RB_TYPE_P(clone, T_CLASS)) {
        class_init_copy_check(clone, orig);
    }
    if (!OBJ_INIT_COPY(clone, orig)) return clone;
    if (!FL_TEST(CLASS_OF(clone), FL_SINGLETON)) {
        RBASIC_SET_CLASS(clone, rb_singleton_class_clone(orig));
        rb_singleton_class_attached(RBASIC(clone)->klass, (VALUE)clone);
    }
    RCLASS_SET_SUPER(clone, RCLASS_SUPER(orig));
    RCLASS_EXT(clone)->allocator = RCLASS_EXT(orig)->allocator;
    if (RCLASS_IV_TBL(clone)) {
        st_free_table(RCLASS_IV_TBL(clone));
        RCLASS_IV_TBL(clone) = 0;
    }
    if (RCLASS_CONST_TBL(clone)) {
        rb_free_const_table(RCLASS_CONST_TBL(clone));
        RCLASS_CONST_TBL(clone) = 0;
    }
    if (RCLASS_M_TBL_WRAPPER(clone)) {
        rb_free_m_tbl_wrapper(RCLASS_M_TBL_WRAPPER(clone));
        RCLASS_M_TBL_WRAPPER(clone) = 0;
    }
    if (RCLASS_IV_TBL(orig)) {
        st_data_t id;

        RCLASS_IV_TBL(clone) = rb_st_copy(clone, RCLASS_IV_TBL(orig));
        CONST_ID(id, "__tmp_classpath__");
        st_delete(RCLASS_IV_TBL(clone), &id, 0);
        CONST_ID(id, "__classpath__");
        st_delete(RCLASS_IV_TBL(clone), &id, 0);
        CONST_ID(id, "__classid__");
        st_delete(RCLASS_IV_TBL(clone), &id, 0);
    }
    if (RCLASS_CONST_TBL(orig)) {
        struct clone_const_arg arg;

        RCLASS_CONST_TBL(clone) = st_init_numtable();
        arg.klass = clone;
        arg.tbl = RCLASS_CONST_TBL(clone);
        st_foreach(RCLASS_CONST_TBL(orig), clone_const_i, (st_data_t)&arg);
    }
    if (RCLASS_M_TBL(orig)) {
        RCLASS_M_TBL_INIT(clone);
        st_foreach(RCLASS_M_TBL(orig), clone_method_i, (st_data_t)clone);
    }

    return clone;
}

VALUE
rb_singleton_class_clone(VALUE obj)
{
    return rb_singleton_class_clone_and_attach(obj, Qundef);
}

VALUE
rb_singleton_class_clone_and_attach(VALUE obj, VALUE attach)
{
    VALUE klass = RBASIC(obj)->klass;

    if (!FL_TEST(klass, FL_SINGLETON))
        return klass;
    else {
        /* copy singleton(unnamed) class */
        VALUE clone = class_alloc(RBASIC(klass)->flags, 0);

        if (BUILTIN_TYPE(obj) == T_CLASS) {
            RBASIC_SET_CLASS(clone, clone);
        }
        else {
            RBASIC_SET_CLASS(clone, rb_singleton_class_clone(klass));
        }

        RCLASS_SET_SUPER(clone, RCLASS_SUPER(klass));
        RCLASS_EXT(clone)->allocator = RCLASS_EXT(klass)->allocator;
        if (RCLASS_IV_TBL(klass)) {
            RCLASS_IV_TBL(clone) = rb_st_copy(clone, RCLASS_IV_TBL(klass));
        }
        if (RCLASS_CONST_TBL(klass)) {
            struct clone_const_arg arg;
            RCLASS_CONST_TBL(clone) = st_init_numtable();
            arg.klass = clone;
            arg.tbl = RCLASS_CONST_TBL(clone);
            st_foreach(RCLASS_CONST_TBL(klass), clone_const_i, (st_data_t)&arg);
        }
        if (attach != Qundef) {
            rb_singleton_class_attached(clone, attach);
        }
        RCLASS_M_TBL_INIT(clone);
        st_foreach(RCLASS_M_TBL(klass), clone_method_i, (st_data_t)clone);
        rb_singleton_class_attached(RBASIC(clone)->klass, clone);
        FL_SET(clone, FL_SINGLETON);

        return clone;
    }
}

void
rb_singleton_class_attached(VALUE klass, VALUE obj)
{
    if (FL_TEST(klass, FL_SINGLETON)) {
        if (!RCLASS_IV_TBL(klass)) {
            RCLASS_IV_TBL(klass) = st_init_numtable();
        }
        rb_st_insert_id_and_value(klass, RCLASS_IV_TBL(klass), id_attached, obj);
    }
}



#define METACLASS_OF(k) RBASIC(k)->klass
#define SET_METACLASS_OF(k, cls) RBASIC_SET_CLASS(k, cls)

#define META_CLASS_OF_CLASS_CLASS_P(k)  (METACLASS_OF(k) == (k))

#define HAVE_METACLASS_P(k) \
    (FL_TEST(METACLASS_OF(k), FL_SINGLETON) && \
     rb_ivar_get(METACLASS_OF(k), id_attached) == (k))

#define ENSURE_EIGENCLASS(klass) \
    (HAVE_METACLASS_P(klass) ? METACLASS_OF(klass) : make_metaclass(klass))


static inline VALUE
make_metaclass(VALUE klass)
{
    VALUE super;
    VALUE metaclass = rb_class_boot(Qundef);

    FL_SET(metaclass, FL_SINGLETON);
    rb_singleton_class_attached(metaclass, klass);

    if (META_CLASS_OF_CLASS_CLASS_P(klass)) {
        SET_METACLASS_OF(klass, metaclass);
        SET_METACLASS_OF(metaclass, metaclass);
    }
    else {
        VALUE tmp = METACLASS_OF(klass); /* for a meta^(n)-class klass, tmp is meta^(n)-class of Class class */
        SET_METACLASS_OF(klass, metaclass);
        SET_METACLASS_OF(metaclass, ENSURE_EIGENCLASS(tmp));
    }

    super = RCLASS_SUPER(klass);
    while (RB_TYPE_P(super, T_ICLASS)) super = RCLASS_SUPER(super);
    RCLASS_SET_SUPER(metaclass, super ? ENSURE_EIGENCLASS(super) : rb_cClass);

    OBJ_INFECT(metaclass, RCLASS_SUPER(metaclass));

    return metaclass;
}

static inline VALUE
make_singleton_class(VALUE obj)
{
    VALUE orig_class = RBASIC(obj)->klass;
    VALUE klass = rb_class_boot(orig_class);

    FL_SET(klass, FL_SINGLETON);
    RBASIC_SET_CLASS(obj, klass);
    rb_singleton_class_attached(klass, obj);

    SET_METACLASS_OF(klass, METACLASS_OF(rb_class_real(orig_class)));
    return klass;
}


static VALUE
boot_defclass(const char *name, VALUE super)
{
    VALUE obj = rb_class_boot(super);
    ID id = rb_intern(name);

    rb_name_class(obj, id);
    rb_const_set((rb_cObject ? rb_cObject : obj), id, obj);
    return obj;
}

void
Init_class_hierarchy(void)
{
    rb_cBasicObject = boot_defclass("BasicObject", 0);
    rb_cObject = boot_defclass("Object", rb_cBasicObject);
    rb_cModule = boot_defclass("Module", rb_cObject);
    rb_cClass =  boot_defclass("Class",  rb_cModule);

    rb_const_set(rb_cObject, rb_intern("BasicObject"), rb_cBasicObject);
    RBASIC_SET_CLASS(rb_cClass, rb_cClass);
    RBASIC_SET_CLASS(rb_cModule, rb_cClass);
    RBASIC_SET_CLASS(rb_cObject, rb_cClass);
    RBASIC_SET_CLASS(rb_cBasicObject, rb_cClass);
}


VALUE
rb_make_metaclass(VALUE obj, VALUE unused)
{
    if (BUILTIN_TYPE(obj) == T_CLASS) {
        return make_metaclass(obj);
    }
    else {
        return make_singleton_class(obj);
    }
}


VALUE
rb_define_class_id(ID id, VALUE super)
{
    VALUE klass;

    if (!super) super = rb_cObject;
    klass = rb_class_new(super);
    rb_make_metaclass(klass, RBASIC(super)->klass);

    return klass;
}


VALUE
rb_class_inherited(VALUE super, VALUE klass)
{
    ID inherited;
    if (!super) super = rb_cObject;
    CONST_ID(inherited, "inherited");
    return rb_funcall(super, inherited, 1, klass);
}



VALUE
rb_define_class(const char *name, VALUE super)
{
    VALUE klass;
    ID id;

    id = rb_intern(name);
    if (rb_const_defined(rb_cObject, id)) {
        klass = rb_const_get(rb_cObject, id);
        if (!RB_TYPE_P(klass, T_CLASS)) {
            rb_raise(rb_eTypeError, "%s is not a class", name);
        }
        if (rb_class_real(RCLASS_SUPER(klass)) != super) {
            rb_raise(rb_eTypeError, "superclass mismatch for class %s", name);
        }
        return klass;
    }
    if (!super) {
        rb_warn("no super class for `%s', Object assumed", name);
    }
    klass = rb_define_class_id(id, super);
    rb_vm_add_root_module(id, klass);
    rb_name_class(klass, id);
    rb_const_set(rb_cObject, id, klass);
    rb_class_inherited(super, klass);

    return klass;
}


VALUE
rb_define_class_under(VALUE outer, const char *name, VALUE super)
{
    return rb_define_class_id_under(outer, rb_intern(name), super);
}


VALUE
rb_define_class_id_under(VALUE outer, ID id, VALUE super)
{
    VALUE klass;

    if (rb_const_defined_at(outer, id)) {
        klass = rb_const_get_at(outer, id);
        if (!RB_TYPE_P(klass, T_CLASS)) {
            rb_raise(rb_eTypeError, "%s is not a class", rb_id2name(id));
        }
        if (rb_class_real(RCLASS_SUPER(klass)) != super) {
            rb_name_error(id, "%s is already defined", rb_id2name(id));
        }
        return klass;
    }
    if (!super) {
        rb_warn("no super class for `%s::%s', Object assumed",
                rb_class2name(outer), rb_id2name(id));
    }
    klass = rb_define_class_id(id, super);
    rb_set_class_path_string(klass, outer, rb_id2str(id));
    rb_const_set(outer, id, klass);
    rb_class_inherited(super, klass);
    rb_gc_register_mark_object(klass);

    return klass;
}

VALUE
rb_module_new(void)
{
    VALUE mdl = class_alloc(T_MODULE, rb_cModule);
    RCLASS_M_TBL_INIT(mdl);
    return (VALUE)mdl;
}

VALUE
rb_define_module_id(ID id)
{
    VALUE mdl;

    mdl = rb_module_new();
    rb_name_class(mdl, id);

    return mdl;
}

VALUE
rb_define_module(const char *name)
{
    VALUE module;
    ID id;

    id = rb_intern(name);
    if (rb_const_defined(rb_cObject, id)) {
        module = rb_const_get(rb_cObject, id);
        if (RB_TYPE_P(module, T_MODULE))
            return module;
        rb_raise(rb_eTypeError, "%s is not a module", rb_obj_classname(module));
    }
    module = rb_define_module_id(id);
    rb_vm_add_root_module(id, module);
    rb_const_set(rb_cObject, id, module);

    return module;
}

VALUE
rb_define_module_under(VALUE outer, const char *name)
{
    return rb_define_module_id_under(outer, rb_intern(name));
}

VALUE
rb_define_module_id_under(VALUE outer, ID id)
{
    VALUE module;

    if (rb_const_defined_at(outer, id)) {
        module = rb_const_get_at(outer, id);
        if (RB_TYPE_P(module, T_MODULE))
            return module;
        rb_raise(rb_eTypeError, "%s::%s is not a module",
                 rb_class2name(outer), rb_obj_classname(module));
    }
    module = rb_define_module_id(id);
    rb_const_set(outer, id, module);
    rb_set_class_path_string(module, outer, rb_id2str(id));
    rb_gc_register_mark_object(module);

    return module;
}

VALUE
rb_include_class_new(VALUE module, VALUE super)
{
    VALUE klass = class_alloc(T_ICLASS, rb_cClass);

    if (BUILTIN_TYPE(module) == T_ICLASS) {
        module = RBASIC(module)->klass;
    }
    if (!RCLASS_IV_TBL(module)) {
        RCLASS_IV_TBL(module) = st_init_numtable();
    }
    if (!RCLASS_CONST_TBL(module)) {
        RCLASS_CONST_TBL(module) = st_init_numtable();
    }
    RCLASS_IV_TBL(klass) = RCLASS_IV_TBL(module);
    RCLASS_CONST_TBL(klass) = RCLASS_CONST_TBL(module);

    RCLASS_M_TBL_WRAPPER(OBJ_WB_UNPROTECT(klass)) =
        RCLASS_M_TBL_WRAPPER(OBJ_WB_UNPROTECT(RCLASS_ORIGIN(module)));

    RCLASS_SET_SUPER(klass, super);
    if (RB_TYPE_P(module, T_ICLASS)) {
        RBASIC_SET_CLASS(klass, RBASIC(module)->klass);
    }
    else {
        RBASIC_SET_CLASS(klass, module);
    }
    OBJ_INFECT(klass, module);
    OBJ_INFECT(klass, super);

    return (VALUE)klass;
}

static int include_modules_at(const VALUE klass, VALUE c, VALUE module);

void
rb_include_module(VALUE klass, VALUE module)
{
    int changed = 0;

    rb_frozen_class_p(klass);

    if (!RB_TYPE_P(module, T_MODULE)) {
        Check_Type(module, T_MODULE);
    }

    OBJ_INFECT(klass, module);

    changed = include_modules_at(klass, RCLASS_ORIGIN(klass), module);
    if (changed < 0)
        rb_raise(rb_eArgError, "cyclic include detected");
}

static int
add_refined_method_entry_i(st_data_t key, st_data_t value, st_data_t data)
{
    rb_add_refined_method_entry((VALUE) data, (ID) key);
    return ST_CONTINUE;
}

static int
include_modules_at(const VALUE klass, VALUE c, VALUE module)
{
    VALUE p, iclass;
    int method_changed = 0, constant_changed = 0;
    const st_table *const klass_m_tbl = RCLASS_M_TBL(RCLASS_ORIGIN(klass));

    while (module) {
        int superclass_seen = FALSE;

        if (RCLASS_ORIGIN(module) != module)
            goto skip;
        if (klass_m_tbl && klass_m_tbl == RCLASS_M_TBL(module))
            return -1;
        /* ignore if the module included already in superclasses */
        for (p = RCLASS_SUPER(klass); p; p = RCLASS_SUPER(p)) {
            switch (BUILTIN_TYPE(p)) {
              case T_ICLASS:
                if (RCLASS_M_TBL_WRAPPER(p) == RCLASS_M_TBL_WRAPPER(module)) {
                    if (!superclass_seen) {
                        c = p;  /* move insertion point */
                    }
                    goto skip;
                }
                break;
              case T_CLASS:
                superclass_seen = TRUE;
                break;
            }
        }
        iclass = rb_include_class_new(module, RCLASS_SUPER(c));
        c = RCLASS_SET_SUPER(c, iclass);

        if (BUILTIN_TYPE(module) == T_ICLASS) {
            rb_module_add_to_subclasses_list(RBASIC(module)->klass, iclass);
        } else {
            rb_module_add_to_subclasses_list(module, iclass);
        }

        if (FL_TEST(klass, RMODULE_IS_REFINEMENT)) {
            VALUE refined_class =
                rb_refinement_module_get_refined_class(klass);

            st_foreach(RMODULE_M_TBL(module), add_refined_method_entry_i,
                       (st_data_t) refined_class);
            FL_SET(c, RMODULE_INCLUDED_INTO_REFINEMENT);
        }
        if (RMODULE_M_TBL(module) && RMODULE_M_TBL(module)->num_entries)
            method_changed = 1;
        if (RMODULE_CONST_TBL(module) && RMODULE_CONST_TBL(module)->num_entries)
            constant_changed = 1;
      skip:
        module = RCLASS_SUPER(module);
    }

    if (method_changed) rb_clear_method_cache_by_class(klass);
    if (constant_changed) rb_clear_constant_cache();

    return method_changed;
}

static int
move_refined_method(st_data_t key, st_data_t value, st_data_t data)
{
    rb_method_entry_t *me = (rb_method_entry_t *) value;
    st_table *tbl = (st_table *) data;

    if (me->def->type == VM_METHOD_TYPE_REFINED) {
        if (me->def->body.orig_me) {
            rb_method_entry_t *orig_me = me->def->body.orig_me, *new_me;
            me->def->body.orig_me = NULL;
            new_me = ALLOC(rb_method_entry_t);
            *new_me = *me;
            st_add_direct(tbl, key, (st_data_t) new_me);
            *me = *orig_me;
            xfree(orig_me);
            return ST_CONTINUE;
        }
        else {
            st_add_direct(tbl, key, (st_data_t) me);
            return ST_DELETE;
        }
    }
    else {
        return ST_CONTINUE;
    }
}

void
rb_prepend_module(VALUE klass, VALUE module)
{
    void rb_vm_check_redefinition_by_prepend(VALUE klass);
    VALUE origin;
    int changed = 0;

    rb_frozen_class_p(klass);

    Check_Type(module, T_MODULE);

    OBJ_INFECT(klass, module);

    origin = RCLASS_ORIGIN(klass);
    if (origin == klass) {
        origin = class_alloc(T_ICLASS, klass);
        OBJ_WB_UNPROTECT(origin); /* TODO: conservertive shading. Need more survery. */
        RCLASS_SET_SUPER(origin, RCLASS_SUPER(klass));
        RCLASS_SET_SUPER(klass, origin);
        RCLASS_ORIGIN(klass) = origin;
        RCLASS_M_TBL_WRAPPER(origin) = RCLASS_M_TBL_WRAPPER(klass);
        RCLASS_M_TBL_INIT(klass);
        st_foreach(RCLASS_M_TBL(origin), move_refined_method,
                   (st_data_t) RCLASS_M_TBL(klass));
    }
    changed = include_modules_at(klass, klass, module);
    if (changed < 0)
        rb_raise(rb_eArgError, "cyclic prepend detected");
    if (changed) {
        rb_vm_check_redefinition_by_prepend(klass);
    }
}

/*
 *  call-seq:
 *     mod.included_modules -> array
 *
 *  Returns the list of modules included in <i>mod</i>.
 *
 *     module Mixin
 *     end
 *
 *     module Outer
 *       include Mixin
 *     end
 *
 *     Mixin.included_modules   #=> []
 *     Outer.included_modules   #=> [Mixin]
 */

VALUE
rb_mod_included_modules(VALUE mod)
{
    VALUE ary = rb_ary_new();
    VALUE p;
    VALUE origin = RCLASS_ORIGIN(mod);

    for (p = RCLASS_SUPER(mod); p; p = RCLASS_SUPER(p)) {
        if (p != origin && BUILTIN_TYPE(p) == T_ICLASS) {
            VALUE m = RBASIC(p)->klass;
            if (RB_TYPE_P(m, T_MODULE))
                rb_ary_push(ary, m);
        }
    }
    return ary;
}

/*
 *  call-seq:
 *     mod.include?(module)    -> true or false
 *
 *  Returns <code>true</code> if <i>module</i> is included in
 *  <i>mod</i> or one of <i>mod</i>'s ancestors.
 *
 *     module A
 *     end
 *     class B
 *       include A
 *     end
 *     class C < B
 *     end
 *     B.include?(A)   #=> true
 *     C.include?(A)   #=> true
 *     A.include?(A)   #=> false
 */

VALUE
rb_mod_include_p(VALUE mod, VALUE mod2)
{
    VALUE p;

    Check_Type(mod2, T_MODULE);
    for (p = RCLASS_SUPER(mod); p; p = RCLASS_SUPER(p)) {
        if (BUILTIN_TYPE(p) == T_ICLASS) {
            if (RBASIC(p)->klass == mod2) return Qtrue;
        }
    }
    return Qfalse;
}

/*
 *  call-seq:
 *     mod.ancestors -> array
 *
 *  Returns a list of modules included in <i>mod</i> (including
 *  <i>mod</i> itself).
 *
 *     module Mod
 *       include Math
 *       include Comparable
 *     end
 *
 *     Mod.ancestors    #=> [Mod, Comparable, Math]
 *     Math.ancestors   #=> [Math]
 */

VALUE
rb_mod_ancestors(VALUE mod)
{
    VALUE p, ary = rb_ary_new();

    for (p = mod; p; p = RCLASS_SUPER(p)) {
        if (BUILTIN_TYPE(p) == T_ICLASS) {
            rb_ary_push(ary, RBASIC(p)->klass);
        }
        else if (p == RCLASS_ORIGIN(p)) {
            rb_ary_push(ary, p);
        }
    }
    return ary;
}

#define VISI(x) ((x)&NOEX_MASK)
#define VISI_CHECK(x,f) (VISI(x) == (f))

static int
ins_methods_push(ID name, long type, VALUE ary, long visi)
{
    if (type == -1) return ST_CONTINUE;

    switch (visi) {
      case NOEX_PRIVATE:
      case NOEX_PROTECTED:
      case NOEX_PUBLIC:
        visi = (type == visi);
        break;
      default:
        visi = (type != NOEX_PRIVATE);
        break;
    }
    if (visi) {
        rb_ary_push(ary, ID2SYM(name));
    }
    return ST_CONTINUE;
}

static int
ins_methods_i(st_data_t name, st_data_t type, st_data_t ary)
{
    return ins_methods_push((ID)name, (long)type, (VALUE)ary, -1); /* everything but private */
}

static int
ins_methods_prot_i(st_data_t name, st_data_t type, st_data_t ary)
{
    return ins_methods_push((ID)name, (long)type, (VALUE)ary, NOEX_PROTECTED);
}

static int
ins_methods_priv_i(st_data_t name, st_data_t type, st_data_t ary)
{
    return ins_methods_push((ID)name, (long)type, (VALUE)ary, NOEX_PRIVATE);
}

static int
ins_methods_pub_i(st_data_t name, st_data_t type, st_data_t ary)
{
    return ins_methods_push((ID)name, (long)type, (VALUE)ary, NOEX_PUBLIC);
}

static int
method_entry_i(st_data_t key, st_data_t value, st_data_t data)
{
    const rb_method_entry_t *me = (const rb_method_entry_t *)value;
    st_table *list = (st_table *)data;
    long type;

    if (me && me->def->type == VM_METHOD_TYPE_REFINED) {
        me = rb_resolve_refined_method(Qnil, me, NULL);
        if (!me) return ST_CONTINUE;
    }
    if (!st_lookup(list, key, 0)) {
        if (UNDEFINED_METHOD_ENTRY_P(me)) {
            type = -1; /* none */
        }
        else {
            type = VISI(me->flag);
        }
        st_add_direct(list, key, type);
    }
    return ST_CONTINUE;
}

static VALUE
class_instance_method_list(int argc, VALUE *argv, VALUE mod, int obj, int (*func) (st_data_t, st_data_t, st_data_t))
{
    VALUE ary;
    int recur, prepended = 0;
    st_table *list;

    if (argc == 0) {
        recur = TRUE;
    }
    else {
        VALUE r;
        rb_scan_args(argc, argv, "01", &r);
        recur = RTEST(r);
    }

    if (!recur && RCLASS_ORIGIN(mod) != mod) {
        mod = RCLASS_ORIGIN(mod);
        prepended = 1;
    }

    list = st_init_numtable();
    for (; mod; mod = RCLASS_SUPER(mod)) {
        if (RCLASS_M_TBL(mod)) st_foreach(RCLASS_M_TBL(mod), method_entry_i, (st_data_t)list);
        if (BUILTIN_TYPE(mod) == T_ICLASS && !prepended) continue;
        if (obj && FL_TEST(mod, FL_SINGLETON)) continue;
        if (!recur) break;
    }
    ary = rb_ary_new();
    st_foreach(list, func, ary);
    st_free_table(list);

    return ary;
}

/*
 *  call-seq:
 *     mod.instance_methods(include_super=true)   -> array
 *
 *  Returns an array containing the names of the public and protected instance
 *  methods in the receiver. For a module, these are the public and protected methods;
 *  for a class, they are the instance (not singleton) methods. With no
 *  argument, or with an argument that is <code>false</code>, the
 *  instance methods in <i>mod</i> are returned, otherwise the methods
 *  in <i>mod</i> and <i>mod</i>'s superclasses are returned.
 *
 *     module A
 *       def method1()  end
 *     end
 *     class B
 *       def method2()  end
 *     end
 *     class C < B
 *       def method3()  end
 *     end
 *
 *     A.instance_methods                #=> [:method1]
 *     B.instance_methods(false)         #=> [:method2]
 *     C.instance_methods(false)         #=> [:method3]
 *     C.instance_methods(true).length   #=> 43
 */

VALUE
rb_class_instance_methods(int argc, VALUE *argv, VALUE mod)
{
    return class_instance_method_list(argc, argv, mod, 0, ins_methods_i);
}

/*
 *  call-seq:
 *     mod.protected_instance_methods(include_super=true)   -> array
 *
 *  Returns a list of the protected instance methods defined in
 *  <i>mod</i>. If the optional parameter is not <code>false</code>, the
 *  methods of any ancestors are included.
 */

VALUE
rb_class_protected_instance_methods(int argc, VALUE *argv, VALUE mod)
{
    return class_instance_method_list(argc, argv, mod, 0, ins_methods_prot_i);
}

/*
 *  call-seq:
 *     mod.private_instance_methods(include_super=true)    -> array
 *
 *  Returns a list of the private instance methods defined in
 *  <i>mod</i>. If the optional parameter is not <code>false</code>, the
 *  methods of any ancestors are included.
 *
 *     module Mod
 *       def method1()  end
 *       private :method1
 *       def method2()  end
 *     end
 *     Mod.instance_methods           #=> [:method2]
 *     Mod.private_instance_methods   #=> [:method1]
 */

VALUE
rb_class_private_instance_methods(int argc, VALUE *argv, VALUE mod)
{
    return class_instance_method_list(argc, argv, mod, 0, ins_methods_priv_i);
}

/*
 *  call-seq:
 *     mod.public_instance_methods(include_super=true)   -> array
 *
 *  Returns a list of the public instance methods defined in <i>mod</i>.
 *  If the optional parameter is not <code>false</code>, the methods of
 *  any ancestors are included.
 */

VALUE
rb_class_public_instance_methods(int argc, VALUE *argv, VALUE mod)
{
    return class_instance_method_list(argc, argv, mod, 0, ins_methods_pub_i);
}

/*
 *  call-seq:
 *     obj.methods(regular=true)    -> array
 *
 *  Returns a list of the names of public and protected methods of
 *  <i>obj</i>. This will include all the methods accessible in
 *  <i>obj</i>'s ancestors.
 *  If the <i>regular</i> parameter is set to <code>false</code>,
 *  Returns an array of obj's public and protected singleton methods,
 *  the array will not include methods in modules included in <i>obj</i>.
 *
 *     class Klass
 *       def klass_method()
 *       end
 *     end
 *     k = Klass.new
 *     k.methods[0..9]    #=> [:klass_method, :nil?, :===,
 *                        #    :==~, :!, :eql?
 *                        #    :hash, :<=>, :class, :singleton_class]
 *     k.methods.length   #=> 57
 *
 *     k.methods(false)   #=> []
 *     def k.singleton_method; end
 *     k.methods(false)   #=> [:singleton_method]
 *
 *     module M123; def m123; end end
 *     k.extend M123
 *     k.methods(false)   #=> [:singleton_method]
 */

VALUE
rb_obj_methods(int argc, VALUE *argv, VALUE obj)
{
  retry:
    if (argc == 0) {
        return class_instance_method_list(argc, argv, CLASS_OF(obj), 1, ins_methods_i);
    }
    else {
        VALUE recur;

        rb_scan_args(argc, argv, "1", &recur);
        if (RTEST(recur)) {
            argc = 0;
            goto retry;
        }
        return rb_obj_singleton_methods(argc, argv, obj);
    }
}

/*
 *  call-seq:
 *     obj.protected_methods(all=true)   -> array
 *
 *  Returns the list of protected methods accessible to <i>obj</i>. If
 *  the <i>all</i> parameter is set to <code>false</code>, only those methods
 *  in the receiver will be listed.
 */

VALUE
rb_obj_protected_methods(int argc, VALUE *argv, VALUE obj)
{
    return class_instance_method_list(argc, argv, CLASS_OF(obj), 1, ins_methods_prot_i);
}

/*
 *  call-seq:
 *     obj.private_methods(all=true)   -> array
 *
 *  Returns the list of private methods accessible to <i>obj</i>. If
 *  the <i>all</i> parameter is set to <code>false</code>, only those methods
 *  in the receiver will be listed.
 */

VALUE
rb_obj_private_methods(int argc, VALUE *argv, VALUE obj)
{
    return class_instance_method_list(argc, argv, CLASS_OF(obj), 1, ins_methods_priv_i);
}

/*
 *  call-seq:
 *     obj.public_methods(all=true)   -> array
 *
 *  Returns the list of public methods accessible to <i>obj</i>. If
 *  the <i>all</i> parameter is set to <code>false</code>, only those methods
 *  in the receiver will be listed.
 */

VALUE
rb_obj_public_methods(int argc, VALUE *argv, VALUE obj)
{
    return class_instance_method_list(argc, argv, CLASS_OF(obj), 1, ins_methods_pub_i);
}

/*
 *  call-seq:
 *     obj.singleton_methods(all=true)    -> array
 *
 *  Returns an array of the names of singleton methods for <i>obj</i>.
 *  If the optional <i>all</i> parameter is true, the list will include
 *  methods in modules included in <i>obj</i>.
 *  Only public and protected singleton methods are returned.
 *
 *     module Other
 *       def three() end
 *     end
 *
 *     class Single
 *       def Single.four() end
 *     end
 *
 *     a = Single.new
 *
 *     def a.one()
 *     end
 *
 *     class << a
 *       include Other
 *       def two()
 *       end
 *     end
 *
 *     Single.singleton_methods    #=> [:four]
 *     a.singleton_methods(false)  #=> [:two, :one]
 *     a.singleton_methods         #=> [:two, :one, :three]
 */

VALUE
rb_obj_singleton_methods(int argc, VALUE *argv, VALUE obj)
{
    VALUE recur, ary, klass, origin;
    st_table *list, *mtbl;

    if (argc == 0) {
        recur = Qtrue;
    }
    else {
        rb_scan_args(argc, argv, "01", &recur);
    }
    klass = CLASS_OF(obj);
    origin = RCLASS_ORIGIN(klass);
    list = st_init_numtable();
    if (klass && FL_TEST(klass, FL_SINGLETON)) {
        if ((mtbl = RCLASS_M_TBL(origin)) != 0)
            st_foreach(mtbl, method_entry_i, (st_data_t)list);
        klass = RCLASS_SUPER(klass);
    }
    if (RTEST(recur)) {
        while (klass && (FL_TEST(klass, FL_SINGLETON) || RB_TYPE_P(klass, T_ICLASS))) {
            if (klass != origin && (mtbl = RCLASS_M_TBL(klass)) != 0)
                st_foreach(mtbl, method_entry_i, (st_data_t)list);
            klass = RCLASS_SUPER(klass);
        }
    }
    ary = rb_ary_new();
    st_foreach(list, ins_methods_i, ary);
    st_free_table(list);

    return ary;
}

void
rb_define_method_id(VALUE klass, ID mid, VALUE (*func)(ANYARGS), int argc)
{
    rb_add_method_cfunc(klass, mid, func, argc, NOEX_PUBLIC);
}

void
rb_define_method(VALUE klass, const char *name, VALUE (*func)(ANYARGS), int argc)
{
    rb_add_method_cfunc(klass, rb_intern(name), func, argc, NOEX_PUBLIC);
}

void
rb_define_protected_method(VALUE klass, const char *name, VALUE (*func)(ANYARGS), int argc)
{
    rb_add_method_cfunc(klass, rb_intern(name), func, argc, NOEX_PROTECTED);
}

void
rb_define_private_method(VALUE klass, const char *name, VALUE (*func)(ANYARGS), int argc)
{
    rb_add_method_cfunc(klass, rb_intern(name), func, argc, NOEX_PRIVATE);
}

void
rb_undef_method(VALUE klass, const char *name)
{
    rb_add_method(klass, rb_intern(name), VM_METHOD_TYPE_UNDEF, 0, NOEX_UNDEF);
}

#define SPECIAL_SINGLETON(x,c) do {\
    if (obj == (x)) {\
        return (c);\
    }\
} while (0)

static inline VALUE
special_singleton_class_of(VALUE obj)
{
    SPECIAL_SINGLETON(Qnil, rb_cNilClass);
    SPECIAL_SINGLETON(Qfalse, rb_cFalseClass);
    SPECIAL_SINGLETON(Qtrue, rb_cTrueClass);
    return Qnil;
}

VALUE
rb_special_singleton_class(VALUE obj)
{
    return special_singleton_class_of(obj);
}

static VALUE
singleton_class_of(VALUE obj)
{
    VALUE klass;

    if (FIXNUM_P(obj) || FLONUM_P(obj) || SYMBOL_P(obj)) {
        rb_raise(rb_eTypeError, "can't define singleton");
    }
    if (SPECIAL_CONST_P(obj)) {
        klass = special_singleton_class_of(obj);
        if (NIL_P(klass))
            rb_bug("unknown immediate %p", (void *)obj);
        return klass;
    }
    else {
        enum ruby_value_type type = BUILTIN_TYPE(obj);
        if (type == T_FLOAT || type == T_BIGNUM) {
            rb_raise(rb_eTypeError, "can't define singleton");
        }
    }

    if (FL_TEST(RBASIC(obj)->klass, FL_SINGLETON) &&
        rb_ivar_get(RBASIC(obj)->klass, id_attached) == obj) {
        klass = RBASIC(obj)->klass;
    }
    else {
        klass = rb_make_metaclass(obj, RBASIC(obj)->klass);
    }

    if (OBJ_TAINTED(obj)) {
        OBJ_TAINT(klass);
    }
    else {
        FL_UNSET(klass, FL_TAINT);
    }
    if (OBJ_FROZEN(obj)) OBJ_FREEZE(klass);

    return klass;
}

VALUE
rb_singleton_class_get(VALUE obj)
{
    VALUE klass;

    if (SPECIAL_CONST_P(obj)) {
        return rb_special_singleton_class(obj);
    }
    klass = RBASIC(obj)->klass;
    if (!FL_TEST(klass, FL_SINGLETON)) return Qnil;
    if (rb_ivar_get(klass, id_attached) != obj) return Qnil;
    return klass;
}

VALUE
rb_singleton_class(VALUE obj)
{
    VALUE klass = singleton_class_of(obj);

    /* ensures an exposed class belongs to its own eigenclass */
    if (RB_TYPE_P(obj, T_CLASS)) (void)ENSURE_EIGENCLASS(klass);

    return klass;
}

void
rb_define_singleton_method(VALUE obj, const char *name, VALUE (*func)(ANYARGS), int argc)
{
    rb_define_method(singleton_class_of(obj), name, func, argc);
}



void
rb_define_module_function(VALUE module, const char *name, VALUE (*func)(ANYARGS), int argc)
{
    rb_define_private_method(module, name, func, argc);
    rb_define_singleton_method(module, name, func, argc);
}


void
rb_define_global_function(const char *name, VALUE (*func)(ANYARGS), int argc)
{
    rb_define_module_function(rb_mKernel, name, func, argc);
}


void
rb_define_alias(VALUE klass, const char *name1, const char *name2)
{
    rb_alias(klass, rb_intern(name1), rb_intern(name2));
}

void
rb_define_attr(VALUE klass, const char *name, int read, int write)
{
    rb_attr(klass, rb_intern(name), read, write, FALSE);
}

int
rb_obj_basic_to_s_p(VALUE obj)
{
    const rb_method_entry_t *me = rb_method_entry(CLASS_OF(obj), rb_intern("to_s"), 0);
    if (me && me->def && me->def->type == VM_METHOD_TYPE_CFUNC &&
        me->def->body.cfunc.func == rb_any_to_s)
        return 1;
    return 0;
}

#include <stdarg.h>

int
rb_scan_args(int argc, const VALUE *argv, const char *fmt, ...)
{
    int i;
    const char *p = fmt;
    VALUE *var;
    va_list vargs;
    int f_var = 0, f_hash = 0, f_block = 0;
    int n_lead = 0, n_opt = 0, n_trail = 0, n_mand;
    int argi = 0;
    VALUE hash = Qnil;

    if (ISDIGIT(*p)) {
        n_lead = *p - '0';
        p++;
        if (ISDIGIT(*p)) {
            n_opt = *p - '0';
            p++;
            if (ISDIGIT(*p)) {
                n_trail = *p - '0';
                p++;
                goto block_arg;
            }
        }
    }
    if (*p == '*') {
        f_var = 1;
        p++;
        if (ISDIGIT(*p)) {
            n_trail = *p - '0';
            p++;
        }
    }
  block_arg:
    if (*p == ':') {
        f_hash = 1;
        p++;
    }
    if (*p == '&') {
        f_block = 1;
        p++;
    }
    if (*p != '\0') {
        rb_fatal("bad scan arg format: %s", fmt);
    }
    n_mand = n_lead + n_trail;

    if (argc < n_mand)
        goto argc_error;

    va_start(vargs, fmt);

    /* capture an option hash - phase 1: pop */
    if (f_hash && n_mand < argc) {
        VALUE last = argv[argc - 1];

        if (NIL_P(last)) {
            /* nil is taken as an empty option hash only if it is not
               ambiguous; i.e. '*' is not specified and arguments are
               given more than sufficient */
            if (!f_var && n_mand + n_opt < argc)
                argc--;
        }
        else {
            hash = rb_check_hash_type(last);
            if (!NIL_P(hash)) {
                VALUE opts = rb_extract_keywords(&hash);
                if (!hash) argc--;
                hash = opts ? opts : Qnil;
            }
        }
    }
    /* capture leading mandatory arguments */
    for (i = n_lead; i-- > 0; ) {
        var = va_arg(vargs, VALUE *);
        if (var) *var = argv[argi];
        argi++;
    }
    /* capture optional arguments */
    for (i = n_opt; i-- > 0; ) {
        var = va_arg(vargs, VALUE *);
        if (argi < argc - n_trail) {
            if (var) *var = argv[argi];
            argi++;
        }
        else {
            if (var) *var = Qnil;
        }
    }
    /* capture variable length arguments */
    if (f_var) {
        int n_var = argc - argi - n_trail;

        var = va_arg(vargs, VALUE *);
        if (0 < n_var) {
            if (var) *var = rb_ary_new4(n_var, &argv[argi]);
            argi += n_var;
        }
        else {
            if (var) *var = rb_ary_new();
        }
    }
    /* capture trailing mandatory arguments */
    for (i = n_trail; i-- > 0; ) {
        var = va_arg(vargs, VALUE *);
        if (var) *var = argv[argi];
        argi++;
    }
    /* capture an option hash - phase 2: assignment */
    if (f_hash) {
        var = va_arg(vargs, VALUE *);
        if (var) *var = hash;
    }
    /* capture iterator block */
    if (f_block) {
        var = va_arg(vargs, VALUE *);
        if (rb_block_given_p()) {
            *var = rb_block_proc();
        }
        else {
            *var = Qnil;
        }
    }
    va_end(vargs);

    if (argi < argc) {
      argc_error:
        rb_error_arity(argc, n_mand, f_var ? UNLIMITED_ARGUMENTS : n_mand + n_opt);
    }

    return argc;
}

NORETURN(static void keyword_error(const char *error, VALUE keys));
static void
keyword_error(const char *error, VALUE keys)
{
    const char *msg = "";
    if (RARRAY_LEN(keys) == 1) {
        keys = RARRAY_AREF(keys, 0);
    }
    else {
        keys = rb_ary_join(keys, rb_usascii_str_new2(", "));
        msg = "s";
    }
    rb_raise(rb_eArgError, "%s keyword%s: %"PRIsVALUE, error, msg, keys);
}

NORETURN(static void unknown_keyword_error(VALUE hash, const ID *table, int keywords));
static void
unknown_keyword_error(VALUE hash, const ID *table, int keywords)
{
    VALUE keys;
    int i;
    for (i = 0; i < keywords; i++) {
        rb_hash_delete(hash, ID2SYM(table[i]));
    }
    keys = rb_funcall(hash, rb_intern("keys"), 0, 0);
    if (!RB_TYPE_P(keys, T_ARRAY)) rb_raise(rb_eArgError, "unknown keyword");
    keyword_error("unknown", keys);
}

static int
separate_symbol(st_data_t key, st_data_t value, st_data_t arg)
{
    VALUE *kwdhash = (VALUE *)arg;

    if (!SYMBOL_P(key)) kwdhash++;
    if (!*kwdhash) *kwdhash = rb_hash_new();
    rb_hash_aset(*kwdhash, (VALUE)key, (VALUE)value);
    return ST_CONTINUE;
}

VALUE
rb_extract_keywords(VALUE *orighash)
{
    VALUE parthash[2] = {0, 0};
    VALUE hash = *orighash;

    if (RHASH_EMPTY_P(hash)) {
        *orighash = 0;
        return hash;
    }
    st_foreach(rb_hash_tbl_raw(hash), separate_symbol, (st_data_t)&parthash);
    *orighash = parthash[1];
    return parthash[0];
}

int
rb_get_kwargs(VALUE keyword_hash, const ID *table, int required, int optional, VALUE *values)
{
    int i = 0, j;
    int rest = 0;
    VALUE missing = Qnil;
    st_data_t key;

#define extract_kwarg(keyword, val) \
    (key = (st_data_t)(keyword), values ? \
     st_delete(rb_hash_tbl_raw(keyword_hash), &key, (val)) : \
     st_lookup(rb_hash_tbl_raw(keyword_hash), key, (val)))

    if (optional < 0) {
        rest = 1;
        optional = -1-optional;
    }
    if (values) {
        for (j = 0; j < required + optional; j++) {
            values[j] = Qundef;
        }
    }
    if (required) {
        for (; i < required; i++) {
            VALUE keyword = ID2SYM(table[i]);
            if (keyword_hash) {
                st_data_t val;
                if (extract_kwarg(keyword, &val)) {
                    if (values) values[i] = (VALUE)val;
                    continue;
                }
            }
            if (NIL_P(missing)) missing = rb_ary_tmp_new(1);
            rb_ary_push(missing, keyword);
        }
        if (!NIL_P(missing)) {
            keyword_error("missing", missing);
        }
    }
    j = i;
    if (optional && keyword_hash) {
        for (i = 0; i < optional; i++) {
            st_data_t val;
            if (extract_kwarg(ID2SYM(table[required+i]), &val)) {
                if (values) values[required+i] = (VALUE)val;
                j++;
            }
        }
    }
    if (!rest && keyword_hash) {
        if (RHASH_SIZE(keyword_hash) > (unsigned int)j) {
            unknown_keyword_error(keyword_hash, table, required+optional);
        }
    }
    return j;
#undef extract_kwarg
}