Skip to content

Commit

Permalink
Showing 6 changed files with 175 additions and 55 deletions.
63 changes: 63 additions & 0 deletions core/src/main/java/org/jruby/Ruby.java
Original file line number Diff line number Diff line change
@@ -4437,6 +4437,69 @@ private IRubyObject execRecursiveInternal(RecursiveFunction func, IRubyObject ob
}
}

ThreadLocal<Map<String, Map<IRubyObject, IRubyObject>>> symMap = new ThreadLocal<>();

public IRubyObject safeRecurse(RecursiveFunction func, IRubyObject obj, String name, boolean outer) {
Map<IRubyObject, IRubyObject> guards = safeRecurseGetGuards(name);

boolean outermost = outer && !guards.containsKey(recursiveKey);

// check guards
if (guards.containsKey(obj)) {
if (outer && !outermost) {
throw new RecursiveError(guards);
}
return func.call(obj, true);
} else {
if (outermost) {
return safeRecurseOutermost(func, obj, guards);
} else {
return safeRecurseInner(func, obj, guards);
}
}
}

private IRubyObject safeRecurseOutermost(RecursiveFunction func, IRubyObject obj, Map<IRubyObject, IRubyObject> guards) {
boolean recursed = false;
guards.put(recursiveKey, recursiveKey);

try {
return safeRecurseInner(func, obj, guards);
} catch (RecursiveError re) {
if (re.tag != guards) {
throw re;
}
recursed = true;
guards.remove(recursiveKey);
return func.call(obj, true);
} finally {
if (!recursed) guards.remove(recursiveKey);
}
}

private Map<IRubyObject, IRubyObject> safeRecurseGetGuards(String name) {
Map<String, Map<IRubyObject, IRubyObject>> symToGuards = symMap.get();
if (symToGuards == null) {
symToGuards = new HashMap<>();
symMap.set(symToGuards);
}

Map<IRubyObject, IRubyObject> guards = symToGuards.get(name);
if (guards == null) {
guards = new IdentityHashMap<>();
symToGuards.put(name, guards);
} return guards;
}

private IRubyObject safeRecurseInner(RecursiveFunction func, IRubyObject obj, Map<IRubyObject, IRubyObject> guards) {
try {
guards.put(obj, obj);
return func.call(obj, false);
} finally {
guards.remove(obj);
}
}

/**
* Perform a recursive walk on the given object using the given function.
*
55 changes: 25 additions & 30 deletions core/src/main/java/org/jruby/RubyArray.java
Original file line number Diff line number Diff line change
@@ -76,9 +76,10 @@

import static org.jruby.RubyEnumerator.enumeratorize;
import static org.jruby.RubyEnumerator.enumeratorizeWithSize;
import static org.jruby.runtime.Helpers.hashEnd;
import static org.jruby.runtime.Helpers.invokedynamic;
import static org.jruby.runtime.Helpers.murmurCombine;
import static org.jruby.runtime.Visibility.PRIVATE;
import static org.jruby.runtime.invokedynamic.MethodNames.HASH;
import static org.jruby.runtime.invokedynamic.MethodNames.OP_CMP;
import static org.jruby.RubyEnumerator.SizeFn;

@@ -676,25 +677,23 @@ public RubyFixnum hash19(ThreadContext context) {
*
*/
@JRubyMethod(name = "hash")
public RubyFixnum hash(final ThreadContext context) {
return (RubyFixnum) context.runtime.execRecursiveOuter(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
final Ruby runtime = context.runtime;
int begin = RubyArray.this.begin;
long h = realLength;
h ^= System.identityHashCode(RubyArray.class);
if (recur) {
h ^= h * 31 + RubyNumeric.num2long(invokedynamic(context, runtime.getArray(), HASH));
} else {
for (int i = begin; i < begin + realLength; i++) {
h = (h << 1) | (h < 0 ? 1 : 0);
final IRubyObject value = safeArrayRef(runtime, values, i);
h ^= h * 31 + RubyNumeric.num2long(invokedynamic(context, value, HASH));
}
}
return runtime.newFixnum(h);
}
}, RubyArray.this);
public RubyFixnum hash(ThreadContext context) {
Ruby runtime = context.runtime;

int begin = RubyArray.this.begin;
long h = Helpers.hashStart(runtime, realLength);

h = Helpers.murmurCombine(h, System.identityHashCode(RubyArray.class));

for (int i = begin; i < begin + realLength; i++) {
IRubyObject value = safeArrayRef(runtime, values, i);
RubyFixnum n = Helpers.safeHash(context, value);
h = murmurCombine(h, n.getLongValue());
}

h = hashEnd(h);

return runtime.newFixnum(h);
}

/** rb_ary_store
@@ -1765,15 +1764,15 @@ private void recursiveJoin(final ThreadContext context, final IRubyObject outVal

if (ary == this) throw runtime.newArgumentError("recursive array join");

runtime.execRecursive(new Ruby.RecursiveFunction() {
runtime.safeRecurse(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
if (recur) throw runtime.newArgumentError("recursive array join");

RubyArray recAry = ((RubyArray) ary);
recAry.joinAny(context, outValue, sep, recAry.begin, result);

return runtime.getNil();
}}, outValue);
}}, outValue, "join", true);
}

/** rb_ary_join
@@ -1799,15 +1798,11 @@ public IRubyObject join19(final ThreadContext context, IRubyObject sep) {
IRubyObject tmp = val.checkStringType19();
if (tmp.isNil() || tmp != val) {
len += ((begin + realLength) - i) * 10;
final RubyString result = (RubyString) RubyString.newStringLight(runtime, len, USASCIIEncoding.INSTANCE).infectBy(this);
final RubyString sepStringFinal = sepString;
final int iFinal = i;
RubyString result = (RubyString) RubyString.newStringLight(runtime, len, USASCIIEncoding.INSTANCE).infectBy(this);
RubyString sepStringFinal = sepString;
int iFinal = i;

return runtime.recursiveListOperation(new Callable<IRubyObject>() {
public IRubyObject call() {
return joinAny(context, RubyArray.this, sepStringFinal, iFinal, joinStrings(sepStringFinal, iFinal, result));
}
});
return joinAny(context, RubyArray.this, sepStringFinal, iFinal, joinStrings(sepStringFinal, iFinal, result));
}

len += ((RubyString) tmp).getByteList().length();
26 changes: 10 additions & 16 deletions core/src/main/java/org/jruby/RubyHash.java
Original file line number Diff line number Diff line change
@@ -1241,24 +1241,18 @@ public IRubyObject op_ge(ThreadContext context, IRubyObject other) {
@JRubyMethod(name = "hash")
public RubyFixnum hash() {
final Ruby runtime = getRuntime();
if (size == 0) return RubyFixnum.zero(runtime);
final ThreadContext context = runtime.getCurrentContext();
return (RubyFixnum) runtime.execRecursiveOuter(new Ruby.RecursiveFunction() {
@Override
public IRubyObject call(IRubyObject obj, boolean recur) {
if (recur) {
return invokedynamic(context, runtime.getHash(), HASH).convertToInteger();
final long[] hval = {Helpers.hashStart(runtime, size())};
if (size > 0) {
iteratorVisitAll(new Visitor() {
@Override
public void visit(IRubyObject key, IRubyObject value) {
hval[0] += Helpers.safeHash(context, key).convertToInteger().getLongValue()
^ Helpers.safeHash(context, value).convertToInteger().getLongValue();
}
final long[] h = new long[]{1};
visitAll(new Visitor() {
@Override
public void visit(IRubyObject key, IRubyObject value) {
h[0] += invokedynamic(context, key, HASH).convertToInteger().getLongValue() ^ invokedynamic(context, value, HASH).convertToInteger().getLongValue();
}
});
return runtime.newFixnum(h[0]);
}
}, this);
});
}
return runtime.newFixnum(hval[0]);
}

@Deprecated
12 changes: 4 additions & 8 deletions core/src/main/java/org/jruby/RubyStruct.java
Original file line number Diff line number Diff line change
@@ -586,15 +586,11 @@ public RubyString inspect(final ThreadContext context) {
final Ruby runtime = context.runtime;
final RubyStruct struct = this;
// recursion guard
return runtime.recursiveListOperation(new Callable<RubyString>() {
public RubyString call() {
return (RubyString) runtime.execRecursive(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
return inspectStruct(context, recur);
}
}, struct);
return (RubyString) runtime.safeRecurse(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
return inspectStruct(context, recur);
}
});
}, struct, "inspect", false);
}

@JRubyMethod(name = {"to_a", "values"})
72 changes: 72 additions & 0 deletions core/src/main/java/org/jruby/runtime/Helpers.java
Original file line number Diff line number Diff line change
@@ -34,6 +34,7 @@
import org.jruby.runtime.invokedynamic.MethodNames;
import org.jruby.util.ByteList;
import org.jruby.util.DefinedMessage;
import org.jruby.util.MurmurHash;
import org.jruby.util.TypeConverter;

import java.util.ArrayList;
@@ -48,7 +49,9 @@
import org.jcodings.specific.UTF8Encoding;
import org.jcodings.unicode.UnicodeEncoding;

import static org.jruby.runtime.Helpers.invokedynamic;
import static org.jruby.runtime.invokedynamic.MethodNames.EQL;
import static org.jruby.runtime.invokedynamic.MethodNames.HASH;
import static org.jruby.runtime.invokedynamic.MethodNames.OP_EQUAL;
import static org.jruby.util.CodegenUtils.sig;
import static org.jruby.util.StringSupport.EMPTY_STRING_ARRAY;
@@ -2714,6 +2717,75 @@ public static boolean isRequiredKeywordArgumentValueNode(Node asgnNode) {
return asgnNode.childNodes().get(0) instanceof RequiredKeywordArgumentValueNode;
}

// MRI: rb_hash_start
public static long hashStart(Ruby runtime, long value) {
long hash = value +
(runtime.isSiphashEnabled() ?
runtime.getHashSeedK1() :
runtime.getHashSeedK0());
return hash;
}

public static long hashEnd(long value) {
value = murmur_step(value, 10);
value = murmur_step(value, 17);
return value;
}

// MRI: rb_hash
public static RubyFixnum safeHash(final ThreadContext context, IRubyObject obj) {
final Ruby runtime = context.runtime;
IRubyObject hval = runtime.safeRecurse(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
if (recur) return RubyFixnum.zero(runtime);
return invokedynamic(context, obj, HASH);
}
}, obj, "hash", true);

while (!(hval instanceof RubyFixnum)) {
if (hval instanceof RubyBignum) {
// This is different from MRI because we don't have rb_integer_pack
return ((RubyBignum) hval).hash();
}
hval = hval.convertToInteger();
}

return (RubyFixnum) hval;
}

public static long murmurCombine(long h, long i)
{
long v = 0;
h += i;
v = murmur1(v + h);
v = murmur1(v + (h >>> 4*8));
return v;
}

public static long murmur(long h, long k, int r)
{
long m = MurmurHash.MURMUR2_MAGIC;
h += k;
h *= m;
h ^= h >> r;
return h;
}

public static long murmur_finish(long h)
{
h = murmur(h, 0, 10);
h = murmur(h, 0, 17);
return h;
}

public static long murmur_step(long h, long k) {
return murmur((h), (k), 16);
}

public static long murmur1(long h) {
return murmur_step(h, 16);
}

@Deprecated
public static String encodeParameterList(List<String[]> args) {
if (args.size() == 0) return "NONE";
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/util/MurmurHash.java
Original file line number Diff line number Diff line change
@@ -15,7 +15,7 @@ public class MurmurHash {

// 'm' and 'r' are mixing constants generated offline.
// They're not really 'magic', they just happen to work well.
private static final int MURMUR2_MAGIC = 0x5bd1e995;
public static final int MURMUR2_MAGIC = 0x5bd1e995;
// CRuby 1.9 uses 16 but original C++ implementation uses 24 with above Magic.
private static final int MURMUR2_R = 24;

0 comments on commit c4a013b

Please sign in to comment.