Skip to content

Commit

Permalink
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Merge branch 'truffle-ropes-2' into truffle-ropes-on-head
Browse files Browse the repository at this point in the history
nirvdrum committed Jan 22, 2016
2 parents bb00f74 + 422acae commit 89451de
Showing 10 changed files with 508 additions and 148 deletions.
291 changes: 291 additions & 0 deletions truffle/src/main/java/org/jruby/truffle/nodes/core/RopeNodes.java
Original file line number Diff line number Diff line change
@@ -0,0 +1,291 @@
/*
* 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.nodes.core;


import com.oracle.truffle.api.CompilerDirectives;
import com.oracle.truffle.api.dsl.Cached;
import com.oracle.truffle.api.dsl.ImportStatic;
import com.oracle.truffle.api.dsl.NodeChild;
import com.oracle.truffle.api.dsl.NodeChildren;
import com.oracle.truffle.api.dsl.Specialization;
import com.oracle.truffle.api.frame.VirtualFrame;
import com.oracle.truffle.api.source.SourceSection;
import com.oracle.truffle.api.utilities.ConditionProfile;
import org.jcodings.Encoding;
import org.jruby.truffle.nodes.RubyNode;
import org.jruby.truffle.runtime.RubyContext;
import org.jruby.truffle.runtime.rope.AsciiOnlyLeafRope;
import org.jruby.truffle.runtime.rope.ConcatRope;
import org.jruby.truffle.runtime.rope.InvalidLeafRope;
import org.jruby.truffle.runtime.rope.LeafRope;
import org.jruby.truffle.runtime.rope.Rope;
import org.jruby.truffle.runtime.rope.RopeOperations;
import org.jruby.truffle.runtime.rope.SubstringRope;
import org.jruby.truffle.runtime.rope.ValidLeafRope;
import org.jruby.util.StringSupport;

public abstract class RopeNodes {

@NodeChildren({
@NodeChild(type = RubyNode.class, value = "base"),
@NodeChild(type = RubyNode.class, value = "offset"),
@NodeChild(type = RubyNode.class, value = "byteLength")
})
public abstract static class MakeSubstringNode extends RubyNode {

public MakeSubstringNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
}

public abstract Rope executeMake(Rope base, int offset, int byteLength);

@Specialization(guards = "byteLength == 0")
public Rope substringZeroLength(Rope base, int offset, int byteLength) {
return RopeOperations.withEncoding(RopeOperations.EMPTY_UTF8_ROPE, base.getEncoding());
}

@Specialization(guards = { "byteLength > 0", "sameAsBase(base, offset, byteLength)" })
public Rope substringSameAsBase(Rope base, int offset, int byteLength) {
return base;
}

@Specialization(guards = { "byteLength > 0", "!sameAsBase(base, offset, byteLength)", "isLeafRope(base)" })
public Rope substringLeafRope(LeafRope base, int offset, int byteLength,
@Cached("createBinaryProfile()") ConditionProfile is7BitProfile) {
return makeSubstring(base, offset, byteLength, is7BitProfile);
}

@Specialization(guards = { "byteLength > 0", "!sameAsBase(base, offset, byteLength)", "isSubstringRope(base)" })
public Rope substringSubstringRope(SubstringRope base, int offset, int byteLength,
@Cached("createBinaryProfile()") ConditionProfile is7BitProfile) {
return makeSubstring(base.getChild(), offset + base.getOffset(), byteLength, is7BitProfile);
}

@Specialization(guards = { "byteLength > 0", "!sameAsBase(base, offset, byteLength)", "isConcatRope(base)" })
public Rope substringConcatRope(ConcatRope base, int offset, int byteLength,
@Cached("createBinaryProfile()") ConditionProfile is7BitProfile) {
Rope root = base;

while (root instanceof ConcatRope) {
ConcatRope concatRoot = (ConcatRope) root;
Rope left = concatRoot.getLeft();
Rope right = concatRoot.getRight();

// CASE 1: Fits in left.
if (offset + byteLength <= left.byteLength()) {
root = left;
continue;
}

// CASE 2: Fits in right.
if (offset >= left.byteLength()) {
offset -= left.byteLength();
root = right;
continue;
}

// CASE 3: Spans left and right.
if (byteLength == root.byteLength()) {
return root;
} else {
return makeSubstring(root, offset, byteLength, is7BitProfile);
}
}

return executeMake(root, offset, byteLength);
}

private Rope makeSubstring(Rope base, int offset, int byteLength, ConditionProfile is7BitProfile) {
if (is7BitProfile.profile(base.getCodeRange() == StringSupport.CR_7BIT)) {
return new SubstringRope(base, offset, byteLength, byteLength, StringSupport.CR_7BIT);
}

return makeSubstringNon7Bit(base, offset, byteLength);
}

@CompilerDirectives.TruffleBoundary
private Rope makeSubstringNon7Bit(Rope base, int offset, int byteLength) {
final long packedLengthAndCodeRange = RopeOperations.calculateCodeRangeAndLength(base.getEncoding(), base.getBytes(), offset, offset + byteLength);
final int codeRange = StringSupport.unpackArg(packedLengthAndCodeRange);
final int characterLength = StringSupport.unpackResult(packedLengthAndCodeRange);

return new SubstringRope(base, offset, byteLength, characterLength, codeRange);
}

protected static boolean sameAsBase(Rope base, int offset, int byteLength) {
return (byteLength - offset) == base.byteLength();
}

protected static boolean is7Bit(Rope base) {
return base.getCodeRange() == StringSupport.CR_7BIT;
}

protected static boolean isLeafRope(Rope rope) {
return (rope instanceof LeafRope);
}

protected static boolean isSubstringRope(Rope rope) {
return (rope instanceof SubstringRope);
}

protected static boolean isConcatRope(Rope rope) {
return (rope instanceof ConcatRope);
}

}

@NodeChildren({
@NodeChild(type = RubyNode.class, value = "left"),
@NodeChild(type = RubyNode.class, value = "right"),
@NodeChild(type = RubyNode.class, value = "encoding")
})
public abstract static class MakeConcatNode extends RubyNode {

public MakeConcatNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
}

public abstract Rope executeMake(Rope left, Rope right, Encoding encoding);

@Specialization(guards = { "left.isEmpty()", "right.getEncoding() == encoding" })
public Rope concatEmptyLeftSameEncoding(Rope left, Rope right, Encoding encoding) {
return right;
}

@Specialization(guards = { "left.isEmpty()", "right.getEncoding() != encoding" })
public Rope concatEmptyLeftDifferentEncoding(Rope left, Rope right, Encoding encoding) {
return RopeOperations.withEncoding(right, encoding);
}

@Specialization(guards = { "right.isEmpty()", "left.getEncoding() == encoding" })
public Rope concatEmptyRightSameEncoding(Rope left, Rope right, Encoding encoding) {
return left;
}

@Specialization(guards = { "right.isEmpty()", "left.getEncoding() != encoding" })
public Rope concatEmptyRightDifferentEncoding(Rope left, Rope right, Encoding encoding) {
return RopeOperations.withEncoding(left, encoding);
}

@Specialization(guards = { "!left.isEmpty()", "!right.isEmpty()" })
public Rope concat(Rope left, Rope right, Encoding encoding,
@Cached("createBinaryProfile()") ConditionProfile sameCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile brokenCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile,
@Cached("createBinaryProfile()") ConditionProfile leftDepthGreaterThanRightProfile) {
return new ConcatRope(left, right, encoding,
commonCodeRange(left.getCodeRange(), right.getCodeRange(), sameCodeRangeProfile, brokenCodeRangeProfile),
isSingleByteOptimizable(left, right, isLeftSingleByteOptimizableProfile),
depth(left, right, leftDepthGreaterThanRightProfile));
}

private int commonCodeRange(int first, int second,
ConditionProfile sameCodeRangeProfile,
ConditionProfile brokenCodeRangeProfile) {
if (sameCodeRangeProfile.profile(first == second)) {
return first;
}

if (brokenCodeRangeProfile.profile((first == StringSupport.CR_BROKEN) || (second == StringSupport.CR_BROKEN))) {
return StringSupport.CR_BROKEN;
}

// If we get this far, one must be CR_7BIT and the other must be CR_VALID, so promote to the more general code range.
return StringSupport.CR_VALID;
}

private boolean isSingleByteOptimizable(Rope left, Rope right, ConditionProfile isLeftSingleByteOptimizableProfile) {
if (isLeftSingleByteOptimizableProfile.profile(left.isSingleByteOptimizable())) {
return right.isSingleByteOptimizable();
}

return false;
}

private int depth(Rope left, Rope right, ConditionProfile leftDepthGreaterThanRightProfile) {
if (leftDepthGreaterThanRightProfile.profile(left.depth() >= right.depth())) {
return left.depth() + 1;
}

return right.depth() + 1;
}

}


@NodeChildren({
@NodeChild(type = RubyNode.class, value = "bytes"),
@NodeChild(type = RubyNode.class, value = "encoding"),
@NodeChild(type = RubyNode.class, value = "codeRange")
})
public abstract static class MakeLeafRopeNode extends RubyNode {

public MakeLeafRopeNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
}

public abstract LeafRope executeMake(byte[] bytes, Encoding encoding, int codeRange);

@Specialization(guards = "is7Bit(codeRange)")
public LeafRope makeAsciiOnlyLeafRope(byte[] bytes, Encoding encoding, int codeRange) {
return new AsciiOnlyLeafRope(bytes, encoding);
}

@Specialization(guards = "isValid(codeRange)")
public LeafRope makeValidLeafRope(byte[] bytes, Encoding encoding, int codeRange) {
final int characterLength = RopeOperations.strLength(encoding, bytes, 0, bytes.length);

return new ValidLeafRope(bytes, encoding, characterLength);
}

@Specialization(guards = "isBroken(codeRange)")
public LeafRope makeInvalidLeafRope(byte[] bytes, Encoding encoding, int codeRange) {
return new InvalidLeafRope(bytes, encoding);
}

@Specialization(guards = "isUnknown(codeRange)")
public LeafRope makeUnknownLeafRope(byte[] bytes, Encoding encoding, int codeRange,
@Cached("createBinaryProfile()") ConditionProfile discovered7BitProfile,
@Cached("createBinaryProfile()") ConditionProfile discoveredValidProfile) {
final long packedLengthAndCodeRange = RopeOperations.calculateCodeRangeAndLength(encoding, bytes, 0, bytes.length);
final int newCodeRange = StringSupport.unpackArg(packedLengthAndCodeRange);
final int characterLength = StringSupport.unpackResult(packedLengthAndCodeRange);

if (discovered7BitProfile.profile(newCodeRange == StringSupport.CR_7BIT)) {
return new AsciiOnlyLeafRope(bytes, encoding);
}

if (discoveredValidProfile.profile(newCodeRange == StringSupport.CR_VALID)) {
return new ValidLeafRope(bytes, encoding, characterLength);
}

return new InvalidLeafRope(bytes, encoding);
}


protected static boolean is7Bit(int codeRange) {
return codeRange == StringSupport.CR_7BIT;
}

protected static boolean isValid(int codeRange) {
return codeRange == StringSupport.CR_VALID;
}

protected static boolean isBroken(int codeRange) {
return codeRange == StringSupport.CR_BROKEN;
}

protected static boolean isUnknown(int codeRange) {
return codeRange == StringSupport.CR_UNKNOWN;
}
}
}
140 changes: 106 additions & 34 deletions truffle/src/main/java/org/jruby/truffle/nodes/core/StringNodes.java

Large diffs are not rendered by default.

Original file line number Diff line number Diff line change
@@ -72,7 +72,7 @@ protected final boolean guardName(Object methodName) {
// TODO(CS, 11-Jan-15) this just repeats the above guard...
return cachedName == methodName;
} else if (RubyGuards.isRubyString(cachedName)) {
return (RubyGuards.isRubyString(methodName)) && StringOperations.getByteListReadOnly((DynamicObject) cachedName).equal(StringOperations.getByteListReadOnly((DynamicObject) methodName));
return (RubyGuards.isRubyString(methodName)) && StringOperations.rope((DynamicObject) cachedName).equals(StringOperations.rope((DynamicObject) methodName));
} else {
throw new UnsupportedOperationException();
}
Original file line number Diff line number Diff line change
@@ -23,6 +23,8 @@
import org.jcodings.transcode.EConvResult;
import org.jruby.truffle.nodes.RubyGuards;
import org.jruby.truffle.nodes.core.EncodingConverterNodes;
import org.jruby.truffle.nodes.core.RopeNodes;
import org.jruby.truffle.nodes.core.RopeNodesFactory;
import org.jruby.truffle.nodes.dispatch.CallDispatchHeadNode;
import org.jruby.truffle.nodes.dispatch.DispatchHeadNodeFactory;
import org.jruby.truffle.runtime.NotProvided;
@@ -57,8 +59,11 @@ public Object encodingConverterAllocate(DynamicObject encodingConverterClass, No
@RubiniusPrimitive(name = "encoding_converter_primitive_convert")
public static abstract class PrimitiveConvertNode extends RubiniusPrimitiveNode {

@Child private RopeNodes.MakeSubstringNode makeSubstringNode;

public PrimitiveConvertNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
makeSubstringNode = RopeNodesFactory.MakeSubstringNodeGen.create(context, sourceSection, null, null, null);
}

@Specialization(guards = {"isRubyString(source)", "isRubyString(target)", "isRubyHash(options)"})
@@ -141,7 +146,7 @@ private Object primitiveConvertHelper(DynamicObject encodingConverter, DynamicOb
outBytes.setRealSize(outPtr.p - outBytes.begin());

if (nonNullSource) {
sourceRope = RopeOperations.substring(sourceRope, inPtr.p, sourceRope.byteLength() - inPtr.p);
sourceRope = makeSubstringNode.executeMake(sourceRope, inPtr.p, sourceRope.byteLength() - inPtr.p);
Layouts.STRING.setRope(source, sourceRope);
}

Original file line number Diff line number Diff line change
@@ -21,6 +21,8 @@
import org.jruby.truffle.nodes.core.CoreClass;
import org.jruby.truffle.nodes.core.CoreMethod;
import org.jruby.truffle.nodes.core.CoreMethodArrayArgumentsNode;
import org.jruby.truffle.nodes.core.RopeNodes;
import org.jruby.truffle.nodes.core.RopeNodesFactory;
import org.jruby.truffle.nodes.objects.AllocateObjectNode;
import org.jruby.truffle.nodes.objects.AllocateObjectNodeGen;
import org.jruby.truffle.runtime.RubyContext;
@@ -698,8 +700,11 @@ public int rmdir(DynamicObject path) {
@CoreMethod(names = "getcwd", isModuleFunction = true, required = 2)
public abstract static class GetcwdNode extends CoreMethodArrayArgumentsNode {

@Child private RopeNodes.MakeLeafRopeNode makeLeafRopeNode;

public GetcwdNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
makeLeafRopeNode = RopeNodesFactory.MakeLeafRopeNodeGen.create(context, sourceSection, null, null, null);
}

@CompilerDirectives.TruffleBoundary
@@ -708,7 +713,7 @@ public DynamicObject getcwd(DynamicObject resultPath, int maxSize) {
// We just ignore maxSize - I think this is ok

final String path = getContext().getRuntime().getCurrentDirectory();
Layouts.STRING.setRope(resultPath, RopeOperations.create(path.getBytes(StandardCharsets.UTF_8), Layouts.STRING.getRope(resultPath).getEncoding(), StringSupport.CR_UNKNOWN));
Layouts.STRING.setRope(resultPath, makeLeafRopeNode.executeMake(path.getBytes(StandardCharsets.UTF_8), Layouts.STRING.getRope(resultPath).getEncoding(), StringSupport.CR_UNKNOWN));
return resultPath;
}

Large diffs are not rendered by default.

Original file line number Diff line number Diff line change
@@ -230,23 +230,6 @@ public static int byteLength(DynamicObject object) {
return Layouts.STRING.getRope(object).byteLength();
}

public static int commonCodeRange(int first, int second) {
if (first == second) {
return first;
}

if ((first == StringSupport.CR_UNKNOWN) || (second == StringSupport.CR_UNKNOWN)) {
return StringSupport.CR_UNKNOWN;
}

if ((first == StringSupport.CR_BROKEN) || (second == StringSupport.CR_BROKEN)) {
return StringSupport.CR_BROKEN;
}

// If we get this far, one must be CR_7BIT and the other must be CR_VALID, so promote to the more general code range.
return StringSupport.CR_VALID;
}

public static Rope ropeFromByteList(ByteList byteList) {
return RopeOperations.create(byteList.bytes(), byteList.getEncoding(), StringSupport.CR_UNKNOWN);
}
Original file line number Diff line number Diff line change
@@ -11,7 +11,6 @@

import com.oracle.truffle.api.CompilerDirectives.TruffleBoundary;
import org.jcodings.Encoding;
import org.jruby.truffle.runtime.core.StringOperations;

public class ConcatRope extends Rope {

@@ -20,13 +19,13 @@ public class ConcatRope extends Rope {

private byte[] bytes;

public ConcatRope(Rope left, Rope right, Encoding encoding) {
public ConcatRope(Rope left, Rope right, Encoding encoding, int codeRange, boolean singleByteOptimizable, int depth) {
super(encoding,
StringOperations.commonCodeRange(left.getCodeRange(), right.getCodeRange()),
left.isSingleByteOptimizable() && right.isSingleByteOptimizable(),
codeRange,
singleByteOptimizable,
left.byteLength() + right.byteLength(),
left.characterLength() + right.characterLength(),
Math.max(left.depth(), right.depth()) + 1);
depth);

this.left = left;
this.right = right;
Original file line number Diff line number Diff line change
@@ -23,7 +23,7 @@ public abstract class Rope {
private final int byteLength;
private final int characterLength;
private final int ropeDepth;
@CompilationFinal private int hashCode = -1;
private int hashCode = 0;

protected Rope(Encoding encoding, int codeRange, boolean singleByteOptimizable, int byteLength, int characterLength, int ropeDepth) {
this.encoding = encoding;
@@ -96,7 +96,7 @@ public int getRealSize() {

@Override
public int hashCode() {
if (hashCode == -1) {
if (hashCode == 0) {
hashCode = RopeOperations.hashForRange(this, 1, 0, byteLength);
}

@@ -112,6 +112,10 @@ public boolean equals(Object o) {
if (o instanceof Rope) {
final Rope other = (Rope) o;

if ((hashCode != 0) && (other.hashCode != 0) && (hashCode != other.hashCode)) {
return false;
}

// TODO (nirvdrum 21-Jan-16): We really should be taking the encoding into account here. We're currenly not because it breaks the symbol table.
return byteLength() == other.byteLength() && Arrays.equals(getBytes(), other.getBytes());
}
Original file line number Diff line number Diff line change
@@ -54,69 +54,6 @@ public static LeafRope create(byte[] bytes, Encoding encoding, int codeRange) {
}
}

@TruffleBoundary
public static Rope concat(Rope left, Rope right, Encoding encoding) {
if (right.isEmpty()) {
return withEncoding(left, encoding);
}

if (left.isEmpty()) {
return withEncoding(right, encoding);
}

return new ConcatRope(left, right, encoding);
}

public static Rope substring(Rope base, int offset, int byteLength) {
if (byteLength == 0) {
return withEncoding(EMPTY_UTF8_ROPE, base.getEncoding());
}

if (byteLength - offset == base.byteLength()) {
return base;
}

if (base instanceof SubstringRope) {
return substringSubstringRope((SubstringRope) base, offset, byteLength);
} else if (base instanceof ConcatRope) {
return substringConcatRope((ConcatRope) base, offset, byteLength);
}

return makeSubstring(base, offset, byteLength);
}

private static Rope substringSubstringRope(SubstringRope base, int offset, int byteLength) {
return makeSubstring(base.getChild(), offset + base.getOffset(), byteLength);
}

@TruffleBoundary
private static Rope substringConcatRope(ConcatRope base, int offset, int byteLength) {
if (offset + byteLength <= base.getLeft().byteLength()) {
return substring(base.getLeft(), offset, byteLength);
} else if (offset >= base.getLeft().byteLength()) {
return substring(base.getRight(), offset - base.getLeft().byteLength(), byteLength);
}

return makeSubstring(base, offset, byteLength);
}

private static Rope makeSubstring(Rope base, int offset, int byteLength) {
if (base.getCodeRange() == StringSupport.CR_7BIT) {
return new SubstringRope(base, offset, byteLength, byteLength, StringSupport.CR_7BIT);
}

return makeSubstringNon7Bit(base, offset, byteLength);
}

@TruffleBoundary
private static Rope makeSubstringNon7Bit(Rope base, int offset, int byteLength) {
final long packedLengthAndCodeRange = calculateCodeRangeAndLength(base.getEncoding(), base.getBytes(), offset, offset + byteLength);
final int codeRange = StringSupport.unpackArg(packedLengthAndCodeRange);
final int characterLength = StringSupport.unpackResult(packedLengthAndCodeRange);

return new SubstringRope(base, offset, byteLength, characterLength, codeRange);
}

public static Rope withEncoding(Rope originalRope, Encoding newEncoding, int newCodeRange) {
if ((originalRope.getEncoding() == newEncoding) && (originalRope.getCodeRange() == newCodeRange)) {
return originalRope;
@@ -125,7 +62,6 @@ public static Rope withEncoding(Rope originalRope, Encoding newEncoding, int new
return create(originalRope.getBytes(), newEncoding, newCodeRange);
}

@TruffleBoundary
public static Rope withEncoding(Rope originalRope, Encoding newEncoding) {
return withEncoding(originalRope, newEncoding, originalRope.getCodeRange());
}
@@ -178,7 +114,7 @@ public static Encoding STR_ENC_GET(Rope rope) {
}

@TruffleBoundary
private static long calculateCodeRangeAndLength(Encoding encoding, byte[] bytes, int start, int end) {
public static long calculateCodeRangeAndLength(Encoding encoding, byte[] bytes, int start, int end) {
if (bytes.length == 0) {
return StringSupport.pack(0, encoding.isAsciiCompatible() ? StringSupport.CR_7BIT : StringSupport.CR_VALID);
} else if (encoding.isAsciiCompatible()) {

0 comments on commit 89451de

Please sign in to comment.