Skip to content

Commit

Permalink
Showing 11 changed files with 181 additions and 118 deletions.
53 changes: 53 additions & 0 deletions spec/truffle/specs/truffle/digest.rb
Original file line number Diff line number Diff line change
@@ -0,0 +1,53 @@
# Copyright (c) 2016 Oracle and/or its affiliates. All rights reserved. This
# code is released under a tri EPL/GPL/LGPL license. You can use it,
# redistribute it and/or modify it under the terms of the:
#
# Eclipse Public License version 1.0
# GNU General Public License version 2
# GNU Lesser General Public License version 2.1

require_relative '../../../ruby/spec_helper'

require 'digest'

describe "digest updating" do

# These tests are here as a convienent way to check we're iterating over ropes correctly when doing IO

it "works on leaf ropes" do
Digest::MD5.hexdigest('foo').should == 'acbd18db4cc2f85cedef654fccc4a4d8'
end

it "works on concat ropes" do
Digest::MD5.hexdigest('foo' + 'bar').should == '3858f62230ac3c915f300c664312c63f'
end

it "works on substring ropes" do
Digest::MD5.hexdigest('foo'[1...-1]).should == 'd95679752134a2d9eb61dbd7b91c4bcc'
end

it "works on substring ropes that cross a concat rope" do
Digest::MD5.hexdigest(('foo' + 'bar')[2...-2]).should == '99faee4e1a331a7595932b7c18f9f5f6'
end

it "works on substring ropes that only use the left of a concat rope" do
Digest::MD5.hexdigest(('foo' + 'bar')[1...2]).should == 'd95679752134a2d9eb61dbd7b91c4bcc'
end

it "works on substring ropes that only use the right of a concat rope" do
Digest::MD5.hexdigest(('foo' + 'bar')[4...5]).should == '0cc175b9c0f1b6a831c399e269772661'
end

it "works on repeating ropes that only use the first repetition" do
Digest::MD5.hexdigest(('foo' * 2)[1...2]).should == 'd95679752134a2d9eb61dbd7b91c4bcc'
end

it "works on repeating ropes that only use the second repetition" do
Digest::MD5.hexdigest(('foo' * 2)[4...5]).should == 'd95679752134a2d9eb61dbd7b91c4bcc'
end

it "works on repeating ropes that cross two repetitions" do
Digest::MD5.hexdigest(('foo' * 2)[2...-2]).should == '8bf8854bebe108183caeb845c7676ae4'
end

end
Original file line number Diff line number Diff line change
@@ -0,0 +1,16 @@
/*
* Copyright (c) 2016 Oracle and/or its affiliates. All rights reserved. This
* code is released under a tri EPL/GPL/LGPL license. You can use it,
* redistribute it and/or modify it under the terms of the:
*
* Eclipse Public License version 1.0
* GNU General Public License version 2
* GNU Lesser General Public License version 2.1
*/
package org.jruby.truffle.core.rope;

public interface BytesVisitor {

void accept(byte[] bytes, int offset, int length);

}
Original file line number Diff line number Diff line change
@@ -12,6 +12,7 @@
import com.oracle.truffle.api.CompilerDirectives;
import com.oracle.truffle.api.CompilerDirectives.TruffleBoundary;
import org.jcodings.Encoding;
import org.jruby.util.func.Function1;

public class ConcatRope extends Rope {

@@ -55,47 +56,6 @@ public byte getByteSlow(int index) {
return right.getByteSlow(index - left.byteLength());
}

@Override
@TruffleBoundary
public byte[] extractRange(int offset, int length) {
assert length <= this.byteLength();

if (getRawBytes() != null) {
final byte[] ret = new byte[length];
System.arraycopy(getRawBytes(), offset, ret, 0, length);

return ret;
}

byte[] leftBytes;
byte[] rightBytes;
final int leftLength = left.byteLength();

if (offset < leftLength) {
// The left branch might not be large enough to extract the full byte range we want. In that case,
// we'll extract what we can and extract the difference from the right side.
if (offset + length > leftLength) {
leftBytes = left.extractRange(offset, leftLength - offset);
} else {
leftBytes = left.extractRange(offset, length);
}

if (leftBytes.length < length) {
rightBytes = right.extractRange(0, length - leftBytes.length);

final byte[] ret = new byte[length];
System.arraycopy(leftBytes, 0, ret, 0, leftBytes.length);
System.arraycopy(rightBytes, 0, ret, leftBytes.length, rightBytes.length);

return ret;
} else {
return leftBytes;
}
}

return right.extractRange(offset - leftLength, length);
}

public Rope getLeft() {
return left;
}
12 changes: 0 additions & 12 deletions truffle/src/main/java/org/jruby/truffle/core/rope/LeafRope.java
Original file line number Diff line number Diff line change
@@ -22,18 +22,6 @@ public byte getByteSlow(int index) {
return getRawBytes()[index];
}

@Override
public byte[] extractRange(int offset, int length) {
assert offset + length <= byteLength();

final int trueLength = Math.min(length, byteLength());
final byte[] ret = new byte[trueLength];

System.arraycopy(getRawBytes(), offset, ret, 0, trueLength);

return ret;
}

@Override
public String toString() {
// This should be used for debugging only.
Original file line number Diff line number Diff line change
@@ -41,11 +41,6 @@ public byte getByteSlow(int index) {
return (byte) byteList.get(index);
}

@Override
public byte[] extractRange(int offset, int length) {
return new ByteList(byteList, offset, length).bytes();
}

public ByteList getByteList() {
return byteList;
}
Original file line number Diff line number Diff line change
@@ -33,43 +33,6 @@ protected byte getByteSlow(int index) {
return child.getByteSlow(index % child.byteLength());
}

@Override
public byte[] extractRange(int offset, int length) {
assert length <= this.byteLength();

final byte[] ret = new byte[length];

if (getRawBytes() != null) {
System.arraycopy(getRawBytes(), offset, ret, 0, length);
} else {
final int start = offset % child.byteLength();
final byte[] firstPart = child.extractRange(start, child.byteLength() - start);
final int lengthMinusFirstPart = length - firstPart.length;
final int remainingEnd = lengthMinusFirstPart % child.byteLength();

System.arraycopy(firstPart, 0, ret, 0, firstPart.length);

if (lengthMinusFirstPart >= child.byteLength()) {
final byte[] secondPart = child.getBytes();

final int repeatPartCount = lengthMinusFirstPart / child.byteLength();
for (int i = 0; i < repeatPartCount; i++) {
System.arraycopy(secondPart, 0, ret, firstPart.length + (secondPart.length * i), secondPart.length);
}

if (remainingEnd > 0) {
final byte[] thirdPart = child.extractRange(0, remainingEnd);
System.arraycopy(thirdPart, 0, ret, length - thirdPart.length, thirdPart.length);
}
} else {
final byte[] secondPart = child.extractRange(0, remainingEnd);
System.arraycopy(secondPart, 0, ret, length - secondPart.length, secondPart.length);
}
}

return ret;
}

public Rope getChild() {
return child;
}
2 changes: 0 additions & 2 deletions truffle/src/main/java/org/jruby/truffle/core/rope/Rope.java
Original file line number Diff line number Diff line change
@@ -66,8 +66,6 @@ public byte[] getBytesCopy() {
return getBytes().clone();
}

public abstract byte[] extractRange(int offset, int length);

public final Encoding getEncoding() {
return encoding;
}
Original file line number Diff line number Diff line change
@@ -176,7 +176,7 @@ private Rope makeSubstring(Rope base, int offset, int byteLength, ConditionProfi
if (getContext().getOptions().ROPE_LAZY_SUBSTRINGS) {
return new SubstringRope(base, offset, byteLength, byteLength, CR_7BIT);
} else {
return new AsciiOnlyLeafRope(base.extractRange(offset, byteLength), base.getEncoding());
return new AsciiOnlyLeafRope(RopeOperations.extractRange(base, offset, byteLength), base.getEncoding());
}
}

@@ -186,7 +186,7 @@ private Rope makeSubstring(Rope base, int offset, int byteLength, ConditionProfi
if (getContext().getOptions().ROPE_LAZY_SUBSTRINGS) {
return new SubstringRope(base, offset, byteLength, byteLength, CR_VALID);
} else {
return new ValidLeafRope(base.extractRange(offset, byteLength), base.getEncoding(), byteLength);
return new ValidLeafRope(RopeOperations.extractRange(base, offset, byteLength), base.getEncoding(), byteLength);
}
}

@@ -213,7 +213,7 @@ private Rope makeSubstringNon7Bit(Rope base, int offset, int byteLength) {
makeLeafRopeNode = insert(RopeNodesFactory.MakeLeafRopeNodeGen.create(getContext(), getSourceSection(), null, null, null, null));
}

final byte[] bytes = base.extractRange(offset, byteLength);
final byte[] bytes = RopeOperations.extractRange(base, offset, byteLength);

return makeLeafRopeNode.executeMake(bytes, base.getEncoding(), codeRange, characterLength);
}
Original file line number Diff line number Diff line change
@@ -30,6 +30,7 @@
import org.jruby.Ruby;
import org.jruby.RubyEncoding;
import org.jruby.util.ByteList;
import org.jruby.util.Memo;
import org.jruby.util.StringSupport;
import org.jruby.util.io.EncodingUtils;

@@ -208,6 +209,101 @@ public static LeafRope flatten(Rope rope) {
return create(flattenBytes(rope), rope.getEncoding(), rope.getCodeRange());
}

public static void visitBytes(Rope rope, BytesVisitor visitor) {
visitBytes(rope, visitor, 0, rope.byteLength());
}

@TruffleBoundary
public static void visitBytes(Rope rope, BytesVisitor visitor, int offset, int length) {
/*
* TODO: CS-7-Apr-16 rewrite this to be iterative as flattenBytes is, but with new logic for offset and length
* creating a range, then write flattenBytes in terms of visitBytes.
*/

assert length <= rope.byteLength();

if (rope.getRawBytes() != null) {
visitor.accept(rope.getRawBytes(), rope.begin() + offset, length);
} else if (rope instanceof ConcatRope) {
final ConcatRope concat = (ConcatRope) rope;

final int leftLength = concat.getLeft().byteLength();

if (offset < leftLength) {
/*
* The left branch might not be large enough to extract the full byte range we want. In that case,
* we'll extract what we can and extract the difference from the right side.
*/

final int leftUsed;

if (offset + length > leftLength) {
leftUsed = leftLength - offset;
} else {
leftUsed = length;
}

visitBytes(concat.getLeft(), visitor, offset, leftUsed);

if (leftUsed < length) {
visitBytes(concat.getRight(), visitor, 0, length - leftUsed);
}
} else {
visitBytes(concat.getRight(), visitor, offset - leftLength, length);
}
} else if (rope instanceof SubstringRope) {
final SubstringRope substring = (SubstringRope) rope;

visitBytes(substring.getChild(), visitor, substring.getOffset() + offset, length);
} else if (rope instanceof RepeatingRope) {
final RepeatingRope repeating = (RepeatingRope) rope;
final Rope child = repeating.getChild();

final int start = offset % child.byteLength();
final int firstPartLength = child.byteLength() - start;
visitBytes(child, visitor, start, firstPartLength);
final int lengthMinusFirstPart = length - firstPartLength;
final int remainingEnd = lengthMinusFirstPart % child.byteLength();

if (lengthMinusFirstPart >= child.byteLength()) {
final byte[] secondPart = child.getBytes();

final int repeatPartCount = lengthMinusFirstPart / child.byteLength();
for (int i = 0; i < repeatPartCount; i++) {
visitBytes(child, visitor, 0, secondPart.length);
}

if (remainingEnd > 0) {
visitBytes(child, visitor, 0, remainingEnd);
}
} else {
visitBytes(child, visitor, 0, remainingEnd);
}
} else {
throw new UnsupportedOperationException("Don't know how to visit rope of type: " + rope.getClass().getName());
}
}

@TruffleBoundary
public static byte[] extractRange(Rope rope, int offset, int length) {
final byte[] result = new byte[length];

final Memo<Integer> resultPosition = new Memo<>(0);

visitBytes(rope, new BytesVisitor() {

@Override
public void accept(byte[] bytes, int offset, int length) {
final int resultPositionValue = resultPosition.get();
System.arraycopy(bytes, offset, result, resultPositionValue, length);
resultPosition.set(resultPositionValue + length);
}

}, offset, length);

return result;
}

/**
* Performs an iterative depth first search of the Rope tree to calculate its byte[] without needing to populate
* the byte[] for each level beneath. Every LeafRope has its byte[] populated by definition. The goal is to determine
@@ -387,7 +483,6 @@ public static byte[] flattenBytes(Rope rope) {
}
}
} else {
CompilerDirectives.transferToInterpreter();
throw new UnsupportedOperationException("Don't know how to flatten rope of type: " + rope.getClass().getName());
}
}
Original file line number Diff line number Diff line change
@@ -46,21 +46,6 @@ public byte getByteSlow(int index) {
return child.getByteSlow(index + offset);
}

@Override
@TruffleBoundary
public byte[] extractRange(int offset, int length) {
assert length <= this.byteLength();

if (getRawBytes() != null) {
final byte[] ret = new byte[length];
System.arraycopy(getRawBytes(), offset, ret, 0, length);

return ret;
}

return child.extractRange(this.offset + offset, length);
}

public Rope getChild() {
return child;
}
14 changes: 12 additions & 2 deletions truffle/src/main/java/org/jruby/truffle/stdlib/DigestNodes.java
Original file line number Diff line number Diff line change
@@ -19,7 +19,9 @@
import org.jruby.truffle.core.CoreMethod;
import org.jruby.truffle.core.CoreMethodArrayArgumentsNode;
import org.jruby.truffle.core.Layouts;
import org.jruby.truffle.core.rope.BytesVisitor;
import org.jruby.truffle.core.rope.Rope;
import org.jruby.truffle.core.rope.RopeOperations;
import org.jruby.truffle.core.string.StringOperations;
import org.jruby.util.ByteList;

@@ -146,9 +148,17 @@ public UpdateNode(RubyContext context, SourceSection sourceSection) {
@TruffleBoundary
@Specialization(guards = "isRubyString(message)")
public DynamicObject update(DynamicObject digestObject, DynamicObject message) {
final Rope rope = StringOperations.rope(message);
final MessageDigest digest = DigestLayoutImpl.INSTANCE.getDigest(digestObject);

RopeOperations.visitBytes(StringOperations.rope(message), new BytesVisitor() {

@Override
public void accept(byte[] bytes, int offset, int length) {
digest.update(bytes, offset, length);
}

});

DigestLayoutImpl.INSTANCE.getDigest(digestObject).update(rope.getBytes(), rope.begin(), rope.byteLength());
return digestObject;
}

0 comments on commit 69132ce

Please sign in to comment.