jruby · Nov 29, 2016 · Nov 29, 2016 · Nov 29, 2016 · Nov 29, 2016 · Nov 29, 2016
Showing with 86 additions and 22 deletions.

+1 −0 spec/truffle/specs/truffle/ropes/complex_structure_spec.rb

+34 −22 truffle/src/main/java/org/jruby/truffle/core/rope/RopeOperations.java

+51 −0 truffle/src/main/java/org/jruby/truffle/core/rope/TruffleRopesNodes.java
diff --git a/spec/truffle/specs/truffle/ropes/complex_structure_spec.rb b/spec/truffle/specs/truffle/ropes/complex_structure_spec.rb
@@ -17,6 +17,7 @@
       [(('abcd'*3)[1..-3]+('ABCD')), 'bcdabcdabABCD'],
       [(('abcd'*3)[1..-4]+('ABCD')), 'bcdabcdaABCD'],
       [(('abcd'*3)[1..-5]+('ABCD')), 'bcdabcdABCD'],
+      [(('ab'*4)+'0123456789')[1..-2]+'cd', 'bababab012345678cd']
   ].each_with_index do |(a, b), i|
     it format('%d: %s', i, b) do
       a.should == b

diff --git a/truffle/src/main/java/org/jruby/truffle/core/rope/RopeOperations.java b/truffle/src/main/java/org/jruby/truffle/core/rope/RopeOperations.java
@@ -330,11 +330,6 @@ public static byte[] flattenBytes(Rope rope) {
             } else if (current instanceof SubstringRope) {
                 final SubstringRope substringRope = (SubstringRope) current;
 
-                // If this SubstringRope is a descendant of another SubstringRope, we need to increment the offset
-                // so that when we finally reach a rope with its byte[] filled, we're extracting bytes from the correct
-                // location.
-                offset += substringRope.getOffset();
-
                 workStack.push(substringRope.getChild());
 
                 // Either we haven't seen another SubstringRope or it's been cleared off the work queue. In either case,
@@ -344,7 +339,7 @@ public static byte[] flattenBytes(Rope rope) {
                 } else {
                     // Since we may be taking a substring of a substring, we need to note that we're not extracting the
                     // entirety of the current SubstringRope.
-                    final int adjustedByteLength = substringRope.byteLength() - (offset - substringRope.getOffset());
+                    final int adjustedByteLength = substringRope.byteLength() - offset;
 
                     // We have to do some bookkeeping once we encounter multiple SubstringRopes along the same ancestry
                     // chain. The top of the stack always indicates the number of bytes to extract from any descendants.
@@ -370,30 +365,33 @@ public static byte[] flattenBytes(Rope rope) {
                         substringLengths.push(adjustedByteLength);
                     }
                 }
+
+                // If this SubstringRope is a descendant of another SubstringRope, we need to increment the offset
+                // so that when we finally reach a rope with its byte[] filled, we're extracting bytes from the correct
+                // location.
+                offset += substringRope.getOffset();
             } else if (current instanceof RepeatingRope) {
                 final RepeatingRope repeatingRope = (RepeatingRope) current;
+                final Rope child = repeatingRope.getChild();
 
                 // In the absence of any SubstringRopes, we always take the full contents of the RepeatingRope.
                 if (substringLengths.isEmpty()) {
                     // TODO (nirvdrum 06-Apr-16) Rather than process the same child over and over, there may be opportunity to re-use the results from a single pass.
                     for (int i = 0; i < repeatingRope.getTimes(); i++) {
-                        workStack.push(repeatingRope.getChild());
+                        workStack.push(child);
                     }
                 } else {
                     final int bytesToCopy = substringLengths.peek();
-                    final int patternLength = repeatingRope.getChild().byteLength();
+                    final int patternLength = child.byteLength();
 
                     // Fix the offset to be appropriate for a given child. The offset is reset the first time it is
                     // consumed, so there's no need to worry about adversely affecting anything by adjusting it here.
-                    offset %= repeatingRope.getChild().byteLength();
+                    offset %= child.byteLength();
 
-                    // The loopCount has to be precisely determined so every repetion has at least some parts used.
-                    // It has to account for the begging we don't need (offset), has to reach the end but, and must not
-                    // have extra repetitions.
-                    int loopCount = (offset + bytesToCopy + patternLength - 1 ) / patternLength;
+                    final int loopCount = computeLoopCount(offset, repeatingRope.getTimes(), bytesToCopy, patternLength);
 
                     // TODO (nirvdrum 25-Aug-2016): Flattening the rope with CR_VALID will cause a character length recalculation, even though we already know what it is. That operation should be made more optimal.
-                    final Rope flattenedChild = flatten(repeatingRope.getChild());
+                    final Rope flattenedChild = flatten(child);
                     for (int i = 0; i < loopCount; i++) {
                         workStack.push(flattenedChild);
                     }
@@ -406,6 +404,18 @@ public static byte[] flattenBytes(Rope rope) {
         return buffer;
     }
 
+    private static int computeLoopCount(int offset, int times, int length, int patternLength) {
+        // The loopCount has to be precisely determined so every repetition has at least some parts used.
+        // It has to account for the beginning we don't need (offset), has to reach the end but, and must not
+        // have extra repetitions. However it cannot be ever longer then repeatingRope.getTimes()
+        return Integer.min(
+                times,
+                (offset
+                        + patternLength * length / patternLength
+                        + patternLength - 1
+                ) / patternLength);
+    }
+
     public static int hashCodeForLeafRope(byte[] bytes, int startingHashCode, int offset, int length) {
         assert offset <= bytes.length;
         assert length <= bytes.length;
@@ -454,21 +464,23 @@ public static int hashForRange(Rope rope, int startingHashCode, int offset, int
             final RepeatingRope repeatingRope = (RepeatingRope) rope;
             final Rope child = repeatingRope.getChild();
 
-            int remainingLength = length;
+            int bytesToHash = length;
             final int patternLength = child.byteLength();
-            int loopCount = (length + patternLength - 1) / patternLength;
 
+            // Fix the offset to be appropriate for a given child. The offset is reset the first time it is
+            // consumed, so there's no need to worry about adversely affecting anything by adjusting it here.
             offset %= child.byteLength();
 
-            // Adjust the loop count in case we're straddling two boundaries.
-            if (offset > 0 && ((length - (patternLength - offset)) % patternLength) > 0) {
-                loopCount++;
-            }
+            final int loopCount = computeLoopCount(offset, repeatingRope.getTimes(), bytesToHash, patternLength);
 
             int hash = startingHashCode;
             for (int i = 0; i < loopCount; i++) {
-                hash = hashForRange(child, hash, offset, remainingLength >= child.byteLength() ? child.byteLength() : remainingLength % child.byteLength());
-                remainingLength = child.byteLength() - offset;
+                hash = hashForRange(
+                        child,
+                        hash,
+                        offset,
+                        bytesToHash >= child.byteLength() ? child.byteLength() : bytesToHash % child.byteLength());
+                bytesToHash = child.byteLength() - offset;
                 offset = 0;
             }
 

diff --git a/truffle/src/main/java/org/jruby/truffle/core/rope/TruffleRopesNodes.java b/truffle/src/main/java/org/jruby/truffle/core/rope/TruffleRopesNodes.java
@@ -102,6 +102,57 @@ public DynamicObject debugPrint(DynamicObject string, boolean printString) {
 
             return debugPrintRopeNode.executeDebugPrint(StringOperations.rope(string), 0, printString);
         }
+    }
+
+    /**
+     * The returned string (when evaluated) will create a string with the same
+     * Rope structure as the string which is passed as argument.
+     */
+    @CoreMethod(names = "debug_get_structure_creation", onSingleton = true, required = 1)
+    public abstract static class DebugGetStructureCreationNode extends CoreMethodArrayArgumentsNode {
+
+
+        public DebugGetStructureCreationNode(RubyContext context, SourceSection sourceSection) {
+            super(context, sourceSection);
+        }
+
+        @TruffleBoundary
+        @Specialization(guards = "isRubyString(string)")
+        public DynamicObject getStructure(DynamicObject string) {
+            Rope rope = StringOperations.rope(string);
+            String result = getStructure(rope);
+            return createString(RopeOperations.create(result.getBytes(), rope.getEncoding(), CodeRange.CR_7BIT));
+        }
+
+        protected static String getStructure(Rope rope) {
+            if (rope instanceof LeafRope) {
+                return getStructure((LeafRope) rope);
+            } else if (rope instanceof ConcatRope) {
+                return getStructure((ConcatRope) rope);
+            } else if (rope instanceof SubstringRope) {
+                return getStructure((SubstringRope) rope);
+            } else if (rope instanceof RepeatingRope) {
+                return getStructure((RepeatingRope) rope);
+            } else {
+                return "(unknown rope class: " + rope.getClass() + ")";
+            }
+        }
+
+        private static String getStructure(LeafRope rope) {
+            return "\"" + rope.toString() + "\"";
+        }
+
+        private static String getStructure(ConcatRope rope) {
+            return "(" + getStructure(rope.getLeft()) + " + " + getStructure(rope.getRight()) + ")";
+        }
+
+        private static String getStructure(SubstringRope rope) {
+            return getStructure(rope.getChild()) + "[" + rope.getOffset() + ", " + rope.characterLength() + "]";
+        }
+
+        private static String getStructure(RepeatingRope rope) {
+            return "(" + getStructure(rope.getChild()) + "*" + rope.getTimes() + ")";
+        }
 
     }