Project

General

Profile

Download (7.51 KB)

Bug #1448 » recursion.patch

marcandre (Marc-Andre Lafortune), 05/09/2009 11:47 AM

View differences:

array.c (working copy)
recursive_equal(VALUE ary1, VALUE ary2, int recur)
{
long i;
if (recur) return Qfalse;
if (recur) return Qtrue; // Subtle!
for (i=0; i<RARRAY_LEN(ary1); i++) {
if (!rb_equal(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
return Qfalse;
......
return rb_equal(ary2, ary1);
}
if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
return rb_exec_recursive(recursive_equal, ary1, ary2);
return rb_exec_recursive_paired(recursive_equal, ary1, ary2);
}
static VALUE
......
{
long i;
if (recur) return Qfalse;
if (recur) return Qtrue; // Subtle!
for (i=0; i<RARRAY_LEN(ary1); i++) {
if (!rb_eql(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
return Qfalse;
......
if (ary1 == ary2) return Qtrue;
if (TYPE(ary2) != T_ARRAY) return Qfalse;
if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
return rb_exec_recursive(recursive_eql, ary1, ary2);
return rb_exec_recursive_paired(recursive_eql, ary1, ary2);
}
static VALUE
......
{
long i, len;
if (recur) return Qnil;
if (recur) return Qundef; // Subtle!
len = RARRAY_LEN(ary1);
if (len > RARRAY_LEN(ary2)) {
len = RARRAY_LEN(ary2);
......
ary2 = to_ary(ary2);
if (ary1 == ary2) return INT2FIX(0);
v = rb_exec_recursive(recursive_cmp, ary1, ary2);
v = rb_exec_recursive_paired(recursive_cmp, ary1, ary2);
if (v != Qundef) return v;
len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
if (len == 0) return INT2FIX(0);
include/ruby/intern.h (working copy)
void rb_thread_atfork(void);
void rb_thread_atfork_before_exec(void);
VALUE rb_exec_recursive(VALUE(*)(VALUE, VALUE, int),VALUE,VALUE);
VALUE rb_exec_recursive_paired(VALUE(*)(VALUE, VALUE, int),VALUE,VALUE);
/* file.c */
VALUE rb_file_s_expand_path(int, VALUE *);
VALUE rb_file_expand_path(VALUE, VALUE);
......
VALUE rb_hash(VALUE);
VALUE rb_hash_new(void);
VALUE rb_hash_dup(VALUE);
VALUE rb_hash_empty_p(VALUE);
VALUE rb_hash_freeze(VALUE);
VALUE rb_hash_aref(VALUE, VALUE);
VALUE rb_hash_lookup(VALUE, VALUE);
thread.c (working copy)
static ID recursive_key;
static VALUE
recursive_check(VALUE hash, VALUE obj)
recursive_check(VALUE hash, VALUE obj, VALUE paired_obj)
{
if (NIL_P(hash) || TYPE(hash) != T_HASH) {
return Qfalse;
}
else {
VALUE list = rb_hash_aref(hash, ID2SYM(rb_frame_this_func()));
VALUE sym = ID2SYM(rb_frame_this_func());
VALUE list = rb_hash_aref(hash, sym);
if (NIL_P(list) || TYPE(list) != T_HASH)
return Qfalse;
if (NIL_P(rb_hash_lookup(list, obj)))
VALUE pair_list = rb_hash_lookup2(list, obj, Qundef);
if (pair_list == Qundef)
return Qfalse;
if (paired_obj) {
if (TYPE(pair_list) != T_HASH) {
if (pair_list != paired_obj)
return Qfalse;
}
else {
if (NIL_P(rb_hash_lookup(pair_list, paired_obj)))
return Qfalse;
}
}
return Qtrue;
}
}
static VALUE
recursive_push(VALUE hash, VALUE obj)
recursive_push(VALUE hash, VALUE obj, VALUE paired_obj)
{
VALUE list, sym;
VALUE list, sym, pair_list;
sym = ID2SYM(rb_frame_this_func());
if (NIL_P(hash) || TYPE(hash) != T_HASH) {
......
list = rb_hash_new();
rb_hash_aset(hash, sym, list);
}
rb_hash_aset(list, obj, Qtrue);
if (!paired_obj) {
rb_hash_aset(list, obj, Qtrue);
}
else {
pair_list = rb_hash_lookup2(list, obj, Qundef);
if (pair_list == Qundef) {
rb_hash_aset(list, obj, paired_obj);
}
else {
if (TYPE(pair_list) != T_HASH){
VALUE other_paired_obj = pair_list;
pair_list = rb_hash_new();
rb_hash_aset(pair_list, other_paired_obj, Qtrue);
rb_hash_aset(list, obj, pair_list);
}
rb_hash_aset(pair_list, paired_obj, Qtrue);
}
}
return hash;
}
static void
recursive_pop(VALUE hash, VALUE obj)
recursive_pop(VALUE hash, VALUE obj, VALUE paired_obj)
{
VALUE list, sym;
VALUE list, sym, pair_list;
sym = ID2SYM(rb_frame_this_func());
if (NIL_P(hash) || TYPE(hash) != T_HASH) {
VALUE symname;
VALUE thrname;
symname = rb_inspect(sym);
thrname = rb_inspect(rb_thread_current());
VALUE symname = rb_inspect(sym);
VALUE thrname = rb_inspect(rb_thread_current());
rb_raise(rb_eTypeError, "invalid inspect_tbl hash for %s in %s",
StringValuePtr(symname), StringValuePtr(thrname));
StringValuePtr(symname), StringValuePtr(thrname));
}
list = rb_hash_aref(hash, sym);
if (NIL_P(list) || TYPE(list) != T_HASH) {
VALUE symname = rb_inspect(sym);
VALUE thrname = rb_inspect(rb_thread_current());
rb_raise(rb_eTypeError, "invalid inspect_tbl list for %s in %s",
StringValuePtr(symname), StringValuePtr(thrname));
StringValuePtr(symname), StringValuePtr(thrname));
}
if (paired_obj) {
pair_list = rb_hash_lookup2(list, obj, Qundef);
if (pair_list == Qundef) {
VALUE symname = rb_inspect(sym);
VALUE thrname = rb_inspect(rb_thread_current());
rb_raise(rb_eTypeError, "invalid inspect_tbl pair_list for %s in %s",
StringValuePtr(symname), StringValuePtr(thrname));
}
if (TYPE(pair_list) == T_HASH) {
rb_hash_delete(pair_list, obj);
if (rb_hash_empty_p(pair_list) == Qfalse) {
return; // keep hash until is empty
}
}
}
rb_hash_delete(list, obj);
}
VALUE
rb_exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
static VALUE
exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg, int pair_with_arg)
{
volatile VALUE hash = rb_thread_local_aref(rb_thread_current(), recursive_key);
VALUE objid = rb_obj_id(obj);
if (recursive_check(hash, objid)) {
VALUE pairid = 0;
if (pair_with_arg) {
pairid = rb_obj_id(arg);
}
if (recursive_check(hash, objid, pairid)) {
return (*func) (obj, arg, Qtrue);
}
else {
VALUE result = Qundef;
int state;
hash = recursive_push(hash, objid);
hash = recursive_push(hash, objid, pairid);
PUSH_TAG();
if ((state = EXEC_TAG()) == 0) {
result = (*func) (obj, arg, Qfalse);
}
POP_TAG();
recursive_pop(hash, objid);
recursive_pop(hash, objid, pairid);
if (state)
JUMP_TAG(state);
return result;
}
}
VALUE
rb_exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
{
return exec_recursive(func, obj, arg, 0);
}
VALUE
rb_exec_recursive_paired(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
{
return exec_recursive(func, obj, arg, 1);
}
/* tracer */
static rb_event_hook_t *
hash.c (working copy)
*
*/
static VALUE
VALUE
rb_hash_empty_p(VALUE hash)
{
return RHASH_EMPTY_P(hash) ? Qtrue : Qfalse;
......
data.tbl = RHASH(hash2)->ntbl;
data.eql = eql;
return rb_exec_recursive(recursive_eql, hash1, (VALUE)&data);
return rb_exec_recursive_paired(recursive_eql, hash1, (VALUE)&data);
}
/*
(1-1/2)