array.c

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

  array.c -

  $Author$
  created at: Fri Aug  6 09:46:12 JST 1993

  Copyright (C) 1993-2007 Yukihiro Matsumoto
  Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
  Copyright (C) 2000  Information-technology Promotion Agency, Japan

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

#include "debug_counter.h"
#include "id.h"
#include "internal.h"
#include "internal/array.h"
#include "internal/compar.h"
#include "internal/enum.h"
#include "internal/gc.h"
#include "internal/hash.h"
#include "internal/numeric.h"
#include "internal/object.h"
#include "internal/proc.h"
#include "internal/rational.h"
#include "internal/vm.h"
#include "probes.h"
#include "ruby/encoding.h"
#include "ruby/st.h"
#include "ruby/util.h"
#include "transient_heap.h"
#include "builtin.h"

#if !ARRAY_DEBUG
# undef NDEBUG
# define NDEBUG
#endif
#include "ruby_assert.h"

VALUE rb_cArray;

/* for OPTIMIZED_CMP: */
#define id_cmp idCmp

#define ARY_DEFAULT_SIZE 16
#define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE))
#define SMALL_ARRAY_LEN 16

RBIMPL_ATTR_MAYBE_UNUSED()
static int
should_be_T_ARRAY(VALUE ary)
{
    return RB_TYPE_P(ary, T_ARRAY);
}

RBIMPL_ATTR_MAYBE_UNUSED()
static int
should_not_be_shared_and_embedded(VALUE ary)
{
    return !FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG);
}

#define ARY_SHARED_P(ary) \
  (assert(should_be_T_ARRAY((VALUE)(ary))), \
   assert(should_not_be_shared_and_embedded((VALUE)ary)), \
   FL_TEST_RAW((ary),ELTS_SHARED)!=0)

#define ARY_EMBED_P(ary) \
  (assert(should_be_T_ARRAY((VALUE)(ary))), \
   assert(should_not_be_shared_and_embedded((VALUE)ary)), \
   FL_TEST_RAW((ary), RARRAY_EMBED_FLAG) != 0)

#define ARY_HEAP_PTR(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.ptr)
#define ARY_HEAP_LEN(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.len)
#define ARY_HEAP_CAPA(a) (assert(!ARY_EMBED_P(a)), assert(!ARY_SHARED_ROOT_P(a)), \
                          RARRAY(a)->as.heap.aux.capa)

#define ARY_EMBED_PTR(a) (assert(ARY_EMBED_P(a)), RARRAY(a)->as.ary)
#define ARY_EMBED_LEN(a) \
    (assert(ARY_EMBED_P(a)), \
     (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
	 (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)))
#define ARY_HEAP_SIZE(a) (assert(!ARY_EMBED_P(a)), assert(ARY_OWNS_HEAP_P(a)), ARY_CAPA(a) * sizeof(VALUE))

#define ARY_OWNS_HEAP_P(a) (assert(should_be_T_ARRAY((VALUE)(a))), \
                            !FL_TEST_RAW((a), ELTS_SHARED|RARRAY_EMBED_FLAG))

#define FL_SET_EMBED(a) do { \
    assert(!ARY_SHARED_P(a)); \
    FL_SET((a), RARRAY_EMBED_FLAG); \
    RARY_TRANSIENT_UNSET(a); \
    ary_verify(a); \
} while (0)

#define FL_UNSET_EMBED(ary) FL_UNSET((ary), RARRAY_EMBED_FLAG|RARRAY_EMBED_LEN_MASK)
#define FL_SET_SHARED(ary) do { \
    assert(!ARY_EMBED_P(ary)); \
    FL_SET((ary), ELTS_SHARED); \
} while (0)
#define FL_UNSET_SHARED(ary) FL_UNSET((ary), ELTS_SHARED)

#define ARY_SET_PTR(ary, p) do { \
    assert(!ARY_EMBED_P(ary)); \
    assert(!OBJ_FROZEN(ary)); \
    RARRAY(ary)->as.heap.ptr = (p); \
} while (0)
#define ARY_SET_EMBED_LEN(ary, n) do { \
    long tmp_n = (n); \
    assert(ARY_EMBED_P(ary)); \
    assert(!OBJ_FROZEN(ary)); \
    RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK; \
    RBASIC(ary)->flags |= (tmp_n) << RARRAY_EMBED_LEN_SHIFT; \
} while (0)
#define ARY_SET_HEAP_LEN(ary, n) do { \
    assert(!ARY_EMBED_P(ary)); \
    RARRAY(ary)->as.heap.len = (n); \
} while (0)
#define ARY_SET_LEN(ary, n) do { \
    if (ARY_EMBED_P(ary)) { \
        ARY_SET_EMBED_LEN((ary), (n)); \
    } \
    else { \
        ARY_SET_HEAP_LEN((ary), (n)); \
    } \
    assert(RARRAY_LEN(ary) == (n)); \
} while (0)
#define ARY_INCREASE_PTR(ary, n) do  { \
    assert(!ARY_EMBED_P(ary)); \
    assert(!OBJ_FROZEN(ary)); \
    RARRAY(ary)->as.heap.ptr += (n); \
} while (0)
#define ARY_INCREASE_LEN(ary, n) do  { \
    assert(!OBJ_FROZEN(ary)); \
    if (ARY_EMBED_P(ary)) { \
        ARY_SET_EMBED_LEN((ary), RARRAY_LEN(ary)+(n)); \
    } \
    else { \
        RARRAY(ary)->as.heap.len += (n); \
    } \
} while (0)

#define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : \
                       ARY_SHARED_ROOT_P(ary) ? RARRAY_LEN(ary) : ARY_HEAP_CAPA(ary))
#define ARY_SET_CAPA(ary, n) do { \
    assert(!ARY_EMBED_P(ary)); \
    assert(!ARY_SHARED_P(ary)); \
    assert(!OBJ_FROZEN(ary)); \
    RARRAY(ary)->as.heap.aux.capa = (n); \
} while (0)

#define ARY_SHARED_ROOT(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared_root)
#define ARY_SET_SHARED(ary, value) do { \
    const VALUE _ary_ = (ary); \
    const VALUE _value_ = (value); \
    assert(!ARY_EMBED_P(_ary_)); \
    assert(ARY_SHARED_P(_ary_)); \
    assert(ARY_SHARED_ROOT_P(_value_)); \
    RB_OBJ_WRITE(_ary_, &RARRAY(_ary_)->as.heap.aux.shared_root, _value_); \
} while (0)
#define RARRAY_SHARED_ROOT_FLAG FL_USER5
#define ARY_SHARED_ROOT_P(ary) (assert(should_be_T_ARRAY((VALUE)(ary))), \
                                FL_TEST_RAW((ary), RARRAY_SHARED_ROOT_FLAG))
#define ARY_SHARED_ROOT_REFCNT(ary) \
    (assert(ARY_SHARED_ROOT_P(ary)), RARRAY(ary)->as.heap.aux.capa)
#define ARY_SHARED_ROOT_OCCUPIED(ary) (ARY_SHARED_ROOT_REFCNT(ary) == 1)
#define ARY_SET_SHARED_ROOT_REFCNT(ary, value) do { \
    assert(ARY_SHARED_ROOT_P(ary)); \
    RARRAY(ary)->as.heap.aux.capa = (value); \
} while (0)
#define FL_SET_SHARED_ROOT(ary) do { \
    assert(!ARY_EMBED_P(ary)); \
    assert(!RARRAY_TRANSIENT_P(ary)); \
    FL_SET((ary), RARRAY_SHARED_ROOT_FLAG); \
} while (0)

static inline void
ARY_SET(VALUE a, long i, VALUE v)
{
    assert(!ARY_SHARED_P(a));
    assert(!OBJ_FROZEN(a));

    RARRAY_ASET(a, i, v);
}
#undef RARRAY_ASET


#if ARRAY_DEBUG
#define ary_verify(ary) ary_verify_(ary, __FILE__, __LINE__)

static VALUE
ary_verify_(VALUE ary, const char *file, int line)
{
    assert(RB_TYPE_P(ary, T_ARRAY));

    if (FL_TEST(ary, ELTS_SHARED)) {
        VALUE root = RARRAY(ary)->as.heap.aux.shared_root;
        const VALUE *ptr = ARY_HEAP_PTR(ary);
        const VALUE *root_ptr = RARRAY_CONST_PTR_TRANSIENT(root);
        long len = ARY_HEAP_LEN(ary), root_len = RARRAY_LEN(root);
        assert(FL_TEST(root, RARRAY_SHARED_ROOT_FLAG));
        assert(root_ptr <= ptr && ptr + len <= root_ptr + root_len);
        ary_verify(root);
    }
    else if (ARY_EMBED_P(ary)) {
        assert(!RARRAY_TRANSIENT_P(ary));
        assert(!ARY_SHARED_P(ary));
        assert(RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX);
    }
    else {
#if 1
        const VALUE *ptr = RARRAY_CONST_PTR_TRANSIENT(ary);
        long i, len = RARRAY_LEN(ary);
        volatile VALUE v;
        if (len > 1) len = 1; /* check only HEAD */
        for (i=0; i<len; i++) {
            v = ptr[i]; /* access check */
        }
        v = v;
#endif
    }

#if USE_TRANSIENT_HEAP
    if (RARRAY_TRANSIENT_P(ary)) {
        assert(rb_transient_heap_managed_ptr_p(RARRAY_CONST_PTR_TRANSIENT(ary)));
    }
#endif

    rb_transient_heap_verify();

    return ary;
}

void
rb_ary_verify(VALUE ary)
{
    ary_verify(ary);
}
#else
#define ary_verify(ary) ((void)0)
#endif

VALUE *
rb_ary_ptr_use_start(VALUE ary)
{
#if ARRAY_DEBUG
    FL_SET_RAW(ary, RARRAY_PTR_IN_USE_FLAG);
#endif
    return (VALUE *)RARRAY_CONST_PTR_TRANSIENT(ary);
}

void
rb_ary_ptr_use_end(VALUE ary)
{
#if ARRAY_DEBUG
    FL_UNSET_RAW(ary, RARRAY_PTR_IN_USE_FLAG);
#endif
}

void
rb_mem_clear(VALUE *mem, long size)
{
    while (size--) {
	*mem++ = Qnil;
    }
}

static void
ary_mem_clear(VALUE ary, long beg, long size)
{
    RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
	rb_mem_clear(ptr + beg, size);
    });
}

static inline void
memfill(register VALUE *mem, register long size, register VALUE val)
{
    while (size--) {
	*mem++ = val;
    }
}

static void
ary_memfill(VALUE ary, long beg, long size, VALUE val)
{
    RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
	memfill(ptr + beg, size, val);
	RB_OBJ_WRITTEN(ary, Qundef, val);
    });
}

static void
ary_memcpy0(VALUE ary, long beg, long argc, const VALUE *argv, VALUE buff_owner_ary)
{
    assert(!ARY_SHARED_P(buff_owner_ary));

    if (argc > (int)(128/sizeof(VALUE)) /* is magic number (cache line size) */) {
        rb_gc_writebarrier_remember(buff_owner_ary);
        RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
            MEMCPY(ptr+beg, argv, VALUE, argc);
        });
    }
    else {
        int i;
        RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
            for (i=0; i<argc; i++) {
                RB_OBJ_WRITE(buff_owner_ary, &ptr[i+beg], argv[i]);
            }
        });
    }
}

static void
ary_memcpy(VALUE ary, long beg, long argc, const VALUE *argv)
{
    ary_memcpy0(ary, beg, argc, argv, ary);
}

static VALUE *
ary_heap_alloc(VALUE ary, size_t capa)
{
    VALUE *ptr = rb_transient_heap_alloc(ary, sizeof(VALUE) * capa);

    if (ptr != NULL) {
        RARY_TRANSIENT_SET(ary);
    }
    else {
        RARY_TRANSIENT_UNSET(ary);
        ptr = ALLOC_N(VALUE, capa);
    }

    return ptr;
}

static void
ary_heap_free_ptr(VALUE ary, const VALUE *ptr, long size)
{
    if (RARRAY_TRANSIENT_P(ary)) {
        /* ignore it */
    }
    else {
        ruby_sized_xfree((void *)ptr, size);
    }
}

static void
ary_heap_free(VALUE ary)
{
    if (RARRAY_TRANSIENT_P(ary)) {
        RARY_TRANSIENT_UNSET(ary);
    }
    else {
        ary_heap_free_ptr(ary, ARY_HEAP_PTR(ary), ARY_HEAP_SIZE(ary));
    }
}

static void
ary_heap_realloc(VALUE ary, size_t new_capa)
{
    size_t old_capa = ARY_HEAP_CAPA(ary);

    if (RARRAY_TRANSIENT_P(ary)) {
        if (new_capa <= old_capa) {
            /* do nothing */
        }
        else {
            VALUE *new_ptr = rb_transient_heap_alloc(ary, sizeof(VALUE) * new_capa);

            if (new_ptr == NULL) {
                new_ptr = ALLOC_N(VALUE, new_capa);
                RARY_TRANSIENT_UNSET(ary);
            }

            MEMCPY(new_ptr, ARY_HEAP_PTR(ary), VALUE, old_capa);
            ARY_SET_PTR(ary, new_ptr);
        }
    }
    else {
        SIZED_REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, new_capa, old_capa);
    }
    ary_verify(ary);
}

#if USE_TRANSIENT_HEAP
static inline void
rb_ary_transient_heap_evacuate_(VALUE ary, int transient, int promote)
{
    if (transient) {
        VALUE *new_ptr;
        const VALUE *old_ptr = ARY_HEAP_PTR(ary);
        long capa = ARY_HEAP_CAPA(ary);
        long len  = ARY_HEAP_LEN(ary);

        if (ARY_SHARED_ROOT_P(ary)) {
            capa = len;
        }

        assert(ARY_OWNS_HEAP_P(ary));
        assert(RARRAY_TRANSIENT_P(ary));
        assert(!ARY_PTR_USING_P(ary));

        if (promote) {
            new_ptr = ALLOC_N(VALUE, capa);
            RARY_TRANSIENT_UNSET(ary);
        }
        else {
            new_ptr = ary_heap_alloc(ary, capa);
        }

        MEMCPY(new_ptr, old_ptr, VALUE, capa);
        /* do not use ARY_SET_PTR() because they assert !frozen */
        RARRAY(ary)->as.heap.ptr = new_ptr;
    }

    ary_verify(ary);
}

void
rb_ary_transient_heap_evacuate(VALUE ary, int promote)
{
    rb_ary_transient_heap_evacuate_(ary, RARRAY_TRANSIENT_P(ary), promote);
}

void
rb_ary_detransient(VALUE ary)
{
    assert(RARRAY_TRANSIENT_P(ary));
    rb_ary_transient_heap_evacuate_(ary, TRUE, TRUE);
}
#else
void
rb_ary_detransient(VALUE ary)
{
    /* do nothing */
}
#endif

static void
ary_resize_capa(VALUE ary, long capacity)
{
    assert(RARRAY_LEN(ary) <= capacity);
    assert(!OBJ_FROZEN(ary));
    assert(!ARY_SHARED_P(ary));

    if (capacity > RARRAY_EMBED_LEN_MAX) {
        if (ARY_EMBED_P(ary)) {
            long len = ARY_EMBED_LEN(ary);
            VALUE *ptr = ary_heap_alloc(ary, capacity);

            MEMCPY(ptr, ARY_EMBED_PTR(ary), VALUE, len);
            FL_UNSET_EMBED(ary);
            ARY_SET_PTR(ary, ptr);
            ARY_SET_HEAP_LEN(ary, len);
        }
        else {
            ary_heap_realloc(ary, capacity);
        }
        ARY_SET_CAPA(ary, capacity);
    }
    else {
        if (!ARY_EMBED_P(ary)) {
            long len = ARY_HEAP_LEN(ary);
            long old_capa = ARY_HEAP_CAPA(ary);
            const VALUE *ptr = ARY_HEAP_PTR(ary);

            if (len > capacity) len = capacity;
            MEMCPY((VALUE *)RARRAY(ary)->as.ary, ptr, VALUE, len);
            ary_heap_free_ptr(ary, ptr, old_capa);

            FL_SET_EMBED(ary);
            ARY_SET_LEN(ary, len);
        }
    }

    ary_verify(ary);
}

static inline void
ary_shrink_capa(VALUE ary)
{
    long capacity = ARY_HEAP_LEN(ary);
    long old_capa = ARY_HEAP_CAPA(ary);
    assert(!ARY_SHARED_P(ary));
    assert(old_capa >= capacity);
    if (old_capa > capacity) ary_heap_realloc(ary, capacity);

    ary_verify(ary);
}

static void
ary_double_capa(VALUE ary, long min)
{
    long new_capa = ARY_CAPA(ary) / 2;

    if (new_capa < ARY_DEFAULT_SIZE) {
	new_capa = ARY_DEFAULT_SIZE;
    }
    if (new_capa >= ARY_MAX_SIZE - min) {
	new_capa = (ARY_MAX_SIZE - min) / 2;
    }
    new_capa += min;
    ary_resize_capa(ary, new_capa);

    ary_verify(ary);
}

static void
rb_ary_decrement_share(VALUE shared_root)
{
    if (shared_root) {
        long num = ARY_SHARED_ROOT_REFCNT(shared_root) - 1;
	if (num == 0) {
            rb_ary_free(shared_root);
            rb_gc_force_recycle(shared_root);
	}
	else if (num > 0) {
            ARY_SET_SHARED_ROOT_REFCNT(shared_root, num);
	}
    }
}

static void
rb_ary_unshare(VALUE ary)
{
    VALUE shared_root = RARRAY(ary)->as.heap.aux.shared_root;
    rb_ary_decrement_share(shared_root);
    FL_UNSET_SHARED(ary);
}

static inline void
rb_ary_unshare_safe(VALUE ary)
{
    if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
	rb_ary_unshare(ary);
    }
}

static VALUE
rb_ary_increment_share(VALUE shared_root)
{
    long num = ARY_SHARED_ROOT_REFCNT(shared_root);
    if (num >= 0) {
        ARY_SET_SHARED_ROOT_REFCNT(shared_root, num + 1);
    }
    return shared_root;
}

static void
rb_ary_set_shared(VALUE ary, VALUE shared_root)
{
    rb_ary_increment_share(shared_root);
    FL_SET_SHARED(ary);
    RB_DEBUG_COUNTER_INC(obj_ary_shared_create);
    ARY_SET_SHARED(ary, shared_root);
}

static inline void
rb_ary_modify_check(VALUE ary)
{
    rb_check_frozen(ary);
    ary_verify(ary);
}

void
rb_ary_modify(VALUE ary)
{
    rb_ary_modify_check(ary);
    if (ARY_SHARED_P(ary)) {
	long shared_len, len = RARRAY_LEN(ary);
        VALUE shared_root = ARY_SHARED_ROOT(ary);

        ary_verify(shared_root);

        if (len <= RARRAY_EMBED_LEN_MAX) {
	    const VALUE *ptr = ARY_HEAP_PTR(ary);
            FL_UNSET_SHARED(ary);
            FL_SET_EMBED(ary);
	    MEMCPY((VALUE *)ARY_EMBED_PTR(ary), ptr, VALUE, len);
            rb_ary_decrement_share(shared_root);
            ARY_SET_EMBED_LEN(ary, len);
        }
        else if (ARY_SHARED_ROOT_OCCUPIED(shared_root) && len > ((shared_len = RARRAY_LEN(shared_root))>>1)) {
            long shift = RARRAY_CONST_PTR_TRANSIENT(ary) - RARRAY_CONST_PTR_TRANSIENT(shared_root);
	    FL_UNSET_SHARED(ary);
            ARY_SET_PTR(ary, RARRAY_CONST_PTR_TRANSIENT(shared_root));
	    ARY_SET_CAPA(ary, shared_len);
            RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
		MEMMOVE(ptr, ptr+shift, VALUE, len);
	    });
            FL_SET_EMBED(shared_root);
            rb_ary_decrement_share(shared_root);
	}
        else {
            VALUE *ptr = ary_heap_alloc(ary, len);
            MEMCPY(ptr, ARY_HEAP_PTR(ary), VALUE, len);
            rb_ary_unshare(ary);
            ARY_SET_CAPA(ary, len);
            ARY_SET_PTR(ary, ptr);
        }

	rb_gc_writebarrier_remember(ary);
    }
    ary_verify(ary);
}

static VALUE
ary_ensure_room_for_push(VALUE ary, long add_len)
{
    long old_len = RARRAY_LEN(ary);
    long new_len = old_len + add_len;
    long capa;

    if (old_len > ARY_MAX_SIZE - add_len) {
	rb_raise(rb_eIndexError, "index %ld too big", new_len);
    }
    if (ARY_SHARED_P(ary)) {
	if (new_len > RARRAY_EMBED_LEN_MAX) {
            VALUE shared_root = ARY_SHARED_ROOT(ary);
            if (ARY_SHARED_ROOT_OCCUPIED(shared_root)) {
                if (ARY_HEAP_PTR(ary) - RARRAY_CONST_PTR_TRANSIENT(shared_root) + new_len <= RARRAY_LEN(shared_root)) {
		    rb_ary_modify_check(ary);

                    ary_verify(ary);
                    ary_verify(shared_root);
                    return shared_root;
		}
		else {
		    /* if array is shared, then it is likely it participate in push/shift pattern */
		    rb_ary_modify(ary);
		    capa = ARY_CAPA(ary);
		    if (new_len > capa - (capa >> 6)) {
			ary_double_capa(ary, new_len);
		    }
                    ary_verify(ary);
		    return ary;
		}
	    }
	}
        ary_verify(ary);
        rb_ary_modify(ary);
    }
    else {
	rb_ary_modify_check(ary);
    }
    capa = ARY_CAPA(ary);
    if (new_len > capa) {
	ary_double_capa(ary, new_len);
    }

    ary_verify(ary);
    return ary;
}

/*
 *  call-seq:
 *    array.freeze -> self
 *
 *  Freezes +self+; returns +self+:
 *    a = []
 *    a.frozen? # => false
 *    a.freeze
 *    a.frozen? # => true
 *
 *  An attempt to modify a frozen \Array raises FrozenError.
 */

VALUE
rb_ary_freeze(VALUE ary)
{
    return rb_obj_freeze(ary);
}

/* This can be used to take a snapshot of an array (with
   e.g. rb_ary_replace) and check later whether the array has been
   modified from the snapshot.  The snapshot is cheap, though if
   something does modify the array it will pay the cost of copying
   it.  If Array#pop or Array#shift has been called, the array will
   be still shared with the snapshot, but the array length will
   differ. */
VALUE
rb_ary_shared_with_p(VALUE ary1, VALUE ary2)
{
    if (!ARY_EMBED_P(ary1) && ARY_SHARED_P(ary1) &&
	!ARY_EMBED_P(ary2) && ARY_SHARED_P(ary2) &&
        RARRAY(ary1)->as.heap.aux.shared_root == RARRAY(ary2)->as.heap.aux.shared_root &&
	RARRAY(ary1)->as.heap.len == RARRAY(ary2)->as.heap.len) {
	return Qtrue;
    }
    return Qfalse;
}

static VALUE
ary_alloc(VALUE klass)
{
    NEWOBJ_OF(ary, struct RArray, klass, T_ARRAY | RARRAY_EMBED_FLAG | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0));
    /* Created array is:
     *   FL_SET_EMBED((VALUE)ary);
     *   ARY_SET_EMBED_LEN((VALUE)ary, 0);
     */
    return (VALUE)ary;
}

static VALUE
empty_ary_alloc(VALUE klass)
{
    RUBY_DTRACE_CREATE_HOOK(ARRAY, 0);
    return ary_alloc(klass);
}

static VALUE
ary_new(VALUE klass, long capa)
{
    VALUE ary,*ptr;

    if (capa < 0) {
	rb_raise(rb_eArgError, "negative array size (or size too big)");
    }
    if (capa > ARY_MAX_SIZE) {
	rb_raise(rb_eArgError, "array size too big");
    }

    RUBY_DTRACE_CREATE_HOOK(ARRAY, capa);

    ary = ary_alloc(klass);
    if (capa > RARRAY_EMBED_LEN_MAX) {
        ptr = ary_heap_alloc(ary, capa);
        FL_UNSET_EMBED(ary);
        ARY_SET_PTR(ary, ptr);
        ARY_SET_CAPA(ary, capa);
        ARY_SET_HEAP_LEN(ary, 0);
    }

    return ary;
}

VALUE
rb_ary_new_capa(long capa)
{
    return ary_new(rb_cArray, capa);
}

VALUE
rb_ary_new(void)
{
    return rb_ary_new2(RARRAY_EMBED_LEN_MAX);
}

VALUE
(rb_ary_new_from_args)(long n, ...)
{
    va_list ar;
    VALUE ary;
    long i;

    ary = rb_ary_new2(n);

    va_start(ar, n);
    for (i=0; i<n; i++) {
	ARY_SET(ary, i, va_arg(ar, VALUE));
    }
    va_end(ar);

    ARY_SET_LEN(ary, n);
    return ary;
}

MJIT_FUNC_EXPORTED VALUE
rb_ary_tmp_new_from_values(VALUE klass, long n, const VALUE *elts)
{
    VALUE ary;

    ary = ary_new(klass, n);
    if (n > 0 && elts) {
	ary_memcpy(ary, 0, n, elts);
	ARY_SET_LEN(ary, n);
    }

    return ary;
}

VALUE
rb_ary_new_from_values(long n, const VALUE *elts)
{
    return rb_ary_tmp_new_from_values(rb_cArray, n, elts);
}

VALUE
rb_ary_tmp_new(long capa)
{
    VALUE ary = ary_new(0, capa);
    rb_ary_transient_heap_evacuate(ary, TRUE);
    return ary;
}

VALUE
rb_ary_tmp_new_fill(long capa)
{
    VALUE ary = ary_new(0, capa);
    ary_memfill(ary, 0, capa, Qnil);
    ARY_SET_LEN(ary, capa);
    rb_ary_transient_heap_evacuate(ary, TRUE);
    return ary;
}

void
rb_ary_free(VALUE ary)
{
    if (ARY_OWNS_HEAP_P(ary)) {
        if (USE_DEBUG_COUNTER &&
            !ARY_SHARED_ROOT_P(ary) &&
            ARY_HEAP_CAPA(ary) > RARRAY_LEN(ary)) {
            RB_DEBUG_COUNTER_INC(obj_ary_extracapa);
        }

        if (RARRAY_TRANSIENT_P(ary)) {
            RB_DEBUG_COUNTER_INC(obj_ary_transient);
        }
        else {
            RB_DEBUG_COUNTER_INC(obj_ary_ptr);
            ary_heap_free(ary);
        }
    }
    else {
        RB_DEBUG_COUNTER_INC(obj_ary_embed);
    }

    if (ARY_SHARED_P(ary)) {
        RB_DEBUG_COUNTER_INC(obj_ary_shared);
    }
    if (ARY_SHARED_ROOT_P(ary) && ARY_SHARED_ROOT_OCCUPIED(ary)) {
        RB_DEBUG_COUNTER_INC(obj_ary_shared_root_occupied);
    }
}

RUBY_FUNC_EXPORTED size_t
rb_ary_memsize(VALUE ary)
{
    if (ARY_OWNS_HEAP_P(ary)) {
	return ARY_CAPA(ary) * sizeof(VALUE);
    }
    else {
	return 0;
    }
}

static inline void
ary_discard(VALUE ary)
{
    rb_ary_free(ary);
    RBASIC(ary)->flags |= RARRAY_EMBED_FLAG;
    RBASIC(ary)->flags &= ~(RARRAY_EMBED_LEN_MASK | RARRAY_TRANSIENT_FLAG);
}

static VALUE
ary_make_shared(VALUE ary)
{
    assert(!ARY_EMBED_P(ary));
    ary_verify(ary);

    if (ARY_SHARED_P(ary)) {
        return ARY_SHARED_ROOT(ary);
    }
    else if (ARY_SHARED_ROOT_P(ary)) {
	return ary;
    }
    else if (OBJ_FROZEN(ary)) {
        rb_ary_transient_heap_evacuate(ary, TRUE);
	ary_shrink_capa(ary);
	FL_SET_SHARED_ROOT(ary);
        ARY_SET_SHARED_ROOT_REFCNT(ary, 1);
	return ary;
    }
    else {
	long capa = ARY_CAPA(ary), len = RARRAY_LEN(ary);
        const VALUE *ptr;
	NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0));
        VALUE vshared = (VALUE)shared;

        rb_ary_transient_heap_evacuate(ary, TRUE);
        ptr = ARY_HEAP_PTR(ary);

        FL_UNSET_EMBED(vshared);
        ARY_SET_LEN(vshared, capa);
        ARY_SET_PTR(vshared, ptr);
        ary_mem_clear(vshared, len, capa - len);
        FL_SET_SHARED_ROOT(vshared);
        ARY_SET_SHARED_ROOT_REFCNT(vshared, 1);
	FL_SET_SHARED(ary);
        RB_DEBUG_COUNTER_INC(obj_ary_shared_create);
        ARY_SET_SHARED(ary, vshared);
        OBJ_FREEZE(vshared);

        ary_verify(vshared);
        ary_verify(ary);

        return vshared;
    }
}

static VALUE
ary_make_substitution(VALUE ary)
{
    long len = RARRAY_LEN(ary);

    if (len <= RARRAY_EMBED_LEN_MAX) {
	VALUE subst = rb_ary_new2(len);
        ary_memcpy(subst, 0, len, RARRAY_CONST_PTR_TRANSIENT(ary));
        ARY_SET_EMBED_LEN(subst, len);
        return subst;
    }
    else {
        return rb_ary_increment_share(ary_make_shared(ary));
    }
}

VALUE
rb_assoc_new(VALUE car, VALUE cdr)
{
    return rb_ary_new3(2, car, cdr);
}

VALUE
rb_to_array_type(VALUE ary)
{
    return rb_convert_type_with_id(ary, T_ARRAY, "Array", idTo_ary);
}
#define to_ary rb_to_array_type

VALUE
rb_check_array_type(VALUE ary)
{
    return rb_check_convert_type_with_id(ary, T_ARRAY, "Array", idTo_ary);
}

MJIT_FUNC_EXPORTED VALUE
rb_check_to_array(VALUE ary)
{
    return rb_check_convert_type_with_id(ary, T_ARRAY, "Array", idTo_a);
}

/*
 *  call-seq:
 *    Array.try_convert(object) -> object, new_array, or nil
 *
 *  If +object+ is an \Array object, returns +object+.
 *
 *  Otherwise if +object+ responds to <tt>:to_ary</tt>,
 *  calls <tt>object.to_ary</tt> and returns the result.
 *
 *  Returns +nil+ if +object+ does not respond to <tt>:to_ary</tt>
 *
 *  Raises an exception unless <tt>object.to_ary</tt> returns an \Array object.
 */

static VALUE
rb_ary_s_try_convert(VALUE dummy, VALUE ary)
{
    return rb_check_array_type(ary);
}

/*
 *  call-seq:
 *    Array.new -> new_empty_array
 *    Array.new(array) -> new_array
 *    Array.new(size) -> new_array
 *    Array.new(size, default_value) -> new_array
 *    Array.new(size) {|index| ... } -> new_array
 *
 *  Returns a new \Array.
 *
 *  With no block and no arguments, returns a new empty \Array object.
 *
 *  With no block and a single \Array argument +array+,
 *  returns a new \Array formed from +array+:
 *    a = Array.new([:foo, 'bar', 2])
 *    a.class # => Array
 *    a # => [:foo, "bar", 2]
 *
 *  With no block and a single \Integer argument +size+,
 *  returns a new \Array of the given size
 *  whose elements are all +nil+:
 *    a = Array.new(3)
 *    a # => [nil, nil, nil]
 *
 *  With no block and arguments +size+ and +default_value+,
 *  returns an \Array of the given size;
 *  each element is that same +default_value+:
 *    a = Array.new(3, 'x')
 *    a # => ['x', 'x', 'x']
 *
 *  With a block and argument +size+,
 *  returns an \Array of the given size;
 *  the block is called with each successive integer +index+;
 *  the element for that +index+ is the return value from the block:
 *    a = Array.new(3) {|index| "Element #{index}" }
 *    a # => ["Element 0", "Element 1", "Element 2"]
 *
 *  Raises ArgumentError if +size+ is negative.
 *
 *  With a block and no argument,