RopeByteString.java

Go to the documentation of this file.

// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
// https://developers.google.com/protocol-buffers/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
package com.google.protobuf;
 
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.OutputStream;
import java.nio.ByteBuffer;
import java.nio.charset.Charset;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
 
final class RopeByteString extends ByteString {
 
  static final int[] minLengthByDepth = {
    1,
    1,
    2,
    3,
    5,
    8,
    13,
    21,
    34,
    55,
    89,
    144,
    233,
    377,
    610,
    987,
    1597,
    2584,
    4181,
    6765,
    10946,
    17711,
    28657,
    46368,
    75025,
    121393,
    196418,
    317811,
    514229,
    832040,
    1346269,
    2178309,
    3524578,
    5702887,
    9227465,
    14930352,
    24157817,
    39088169,
    63245986,
    102334155,
    165580141,
    267914296,
    433494437,
    701408733,
    1134903170,
    1836311903,
    Integer.MAX_VALUE
  };
 
  private final int totalLength;
  private final ByteString left;
  private final ByteString right;
  private final int leftLength;
  private final int treeDepth;
 
  private RopeByteString(ByteString left, ByteString right) {
    this.left = left;
    this.right = right;
    leftLength = left.size();
    totalLength = leftLength + right.size();
    treeDepth = Math.max(left.getTreeDepth(), right.getTreeDepth()) + 1;
  }
 
  static ByteString concatenate(ByteString left, ByteString right) {
    if (right.size() == 0) {
      return left;
    }
 
    if (left.size() == 0) {
      return right;
    }
 
    final int newLength = left.size() + right.size();
    if (newLength < ByteString.CONCATENATE_BY_COPY_SIZE) {
      // Optimization from BAP95: For short (leaves in paper, but just short
      // here) total length, do a copy of data to a new leaf.
      return concatenateBytes(left, right);
    }
 
    if (left instanceof RopeByteString) {
      final RopeByteString leftRope = (RopeByteString) left;
      if (leftRope.right.size() + right.size() < CONCATENATE_BY_COPY_SIZE) {
        // Optimization from BAP95: As an optimization of the case where the
        // ByteString is constructed by repeated concatenate, recognize the case
        // where a short string is concatenated to a left-hand node whose
        // right-hand branch is short.  In the paper this applies to leaves, but
        // we just look at the length here. This has the advantage of shedding
        // references to unneeded data when substrings have been taken.
        //
        // When we recognize this case, we do a copy of the data and create a
        // new parent node so that the depth of the result is the same as the
        // given left tree.
        ByteString newRight = concatenateBytes(leftRope.right, right);
        return new RopeByteString(leftRope.left, newRight);
      }
 
      if (leftRope.left.getTreeDepth() > leftRope.right.getTreeDepth()
          && leftRope.getTreeDepth() > right.getTreeDepth()) {
        // Typically for concatenate-built strings the left-side is deeper than
        // the right.  This is our final attempt to concatenate without
        // increasing the tree depth.  We'll redo the node on the RHS.  This
        // is yet another optimization for building the string by repeatedly
        // concatenating on the right.
        ByteString newRight = new RopeByteString(leftRope.right, right);
        return new RopeByteString(leftRope.left, newRight);
      }
    }
 
    // Fine, we'll add a node and increase the tree depth--unless we rebalance ;^)
    int newDepth = Math.max(left.getTreeDepth(), right.getTreeDepth()) + 1;
    if (newLength >= minLengthByDepth[newDepth]) {
      // The tree is shallow enough, so don't rebalance
      return new RopeByteString(left, right);
    }
 
    return new Balancer().balance(left, right);
  }
 
  private static ByteString concatenateBytes(ByteString left, ByteString right) {
    int leftSize = left.size();
    int rightSize = right.size();
    byte[] bytes = new byte[leftSize + rightSize];
    left.copyTo(bytes, 0, 0, leftSize);
    right.copyTo(bytes, 0, leftSize, rightSize);
    return ByteString.wrap(bytes); // Constructor wraps bytes
  }
 
  static RopeByteString newInstanceForTest(ByteString left, ByteString right) {
    return new RopeByteString(left, right);
  }
 
  @Override
  public byte byteAt(int index) {
    checkIndex(index, totalLength);
    return internalByteAt(index);
  }
 
  @Override
  byte internalByteAt(int index) {
    // Find the relevant piece by recursive descent
    if (index < leftLength) {
      return left.internalByteAt(index);
    }
 
    return right.internalByteAt(index - leftLength);
  }
 
  @Override
  public int size() {
    return totalLength;
  }
 
  @Override
  public ByteIterator iterator() {
    return new AbstractByteIterator() {
      final PieceIterator pieces = new PieceIterator(RopeByteString.this);
      ByteIterator current = nextPiece();
 
      private ByteIterator nextPiece() {
        // NOTE: PieceIterator is guaranteed to return non-empty pieces, so this method will always
        // return non-empty iterators (or null)
        return pieces.hasNext() ? pieces.next().iterator() : null;
      }
 
      @Override
      public boolean hasNext() {
        return current != null;
      }
 
      @Override
      public byte nextByte() {
        if (current == null) {
          throw new NoSuchElementException();
        }
        byte b = current.nextByte();
        if (!current.hasNext()) {
          current = nextPiece();
        }
        return b;
      }
    };
  }
 
  // =================================================================
  // Pieces
 
  @Override
  protected int getTreeDepth() {
    return treeDepth;
  }
 
  @Override
  protected boolean isBalanced() {
    return totalLength >= minLengthByDepth[treeDepth];
  }
 
  @Override
  public ByteString substring(int beginIndex, int endIndex) {
    final int length = checkRange(beginIndex, endIndex, totalLength);
 
    if (length == 0) {
      // Empty substring
      return ByteString.EMPTY;
    }
 
    if (length == totalLength) {
      // The whole string
      return this;
    }
 
    // Proper substring
    if (endIndex <= leftLength) {
      // Substring on the left
      return left.substring(beginIndex, endIndex);
    }
 
    if (beginIndex >= leftLength) {
      // Substring on the right
      return right.substring(beginIndex - leftLength, endIndex - leftLength);
    }
 
    // Split substring
    ByteString leftSub = left.substring(beginIndex);
    ByteString rightSub = right.substring(0, endIndex - leftLength);
    // Intentionally not rebalancing, since in many cases these two
    // substrings will already be less deep than the top-level
    // RopeByteString we're taking a substring of.
    return new RopeByteString(leftSub, rightSub);
  }
 
  // =================================================================
  // ByteString -> byte[]
 
  @Override
  protected void copyToInternal(
      byte[] target, int sourceOffset, int targetOffset, int numberToCopy) {
    if (sourceOffset + numberToCopy <= leftLength) {
      left.copyToInternal(target, sourceOffset, targetOffset, numberToCopy);
    } else if (sourceOffset >= leftLength) {
      right.copyToInternal(target, sourceOffset - leftLength, targetOffset, numberToCopy);
    } else {
      int leftLength = this.leftLength - sourceOffset;
      left.copyToInternal(target, sourceOffset, targetOffset, leftLength);
      right.copyToInternal(target, 0, targetOffset + leftLength, numberToCopy - leftLength);
    }
  }
 
  @Override
  public void copyTo(ByteBuffer target) {
    left.copyTo(target);
    right.copyTo(target);
  }
 
  @Override
  public ByteBuffer asReadOnlyByteBuffer() {
    ByteBuffer byteBuffer = ByteBuffer.wrap(toByteArray());
    return byteBuffer.asReadOnlyBuffer();
  }
 
  @Override
  public List<ByteBuffer> asReadOnlyByteBufferList() {
    // Walk through the list of LeafByteString's that make up this
    // rope, and add each one as a read-only ByteBuffer.
    List<ByteBuffer> result = new ArrayList<ByteBuffer>();
    PieceIterator pieces = new PieceIterator(this);
    while (pieces.hasNext()) {
      LeafByteString byteString = pieces.next();
      result.add(byteString.asReadOnlyByteBuffer());
    }
    return result;
  }
 
  @Override
  public void writeTo(OutputStream outputStream) throws IOException {
    left.writeTo(outputStream);
    right.writeTo(outputStream);
  }
 
  @Override
  void writeToInternal(OutputStream out, int sourceOffset, int numberToWrite) throws IOException {
    if (sourceOffset + numberToWrite <= leftLength) {
      left.writeToInternal(out, sourceOffset, numberToWrite);
    } else if (sourceOffset >= leftLength) {
      right.writeToInternal(out, sourceOffset - leftLength, numberToWrite);
    } else {
      int numberToWriteInLeft = leftLength - sourceOffset;
      left.writeToInternal(out, sourceOffset, numberToWriteInLeft);
      right.writeToInternal(out, 0, numberToWrite - numberToWriteInLeft);
    }
  }
 
  @Override
  void writeTo(ByteOutput output) throws IOException {
    left.writeTo(output);
    right.writeTo(output);
  }
 
  @Override
  void writeToReverse(ByteOutput output) throws IOException {
    right.writeToReverse(output);
    left.writeToReverse(output);
  }
 
  @Override
  protected String toStringInternal(Charset charset) {
    return new String(toByteArray(), charset);
  }
 
  // =================================================================
  // UTF-8 decoding
 
  @Override
  public boolean isValidUtf8() {
    int leftPartial = left.partialIsValidUtf8(Utf8.COMPLETE, 0, leftLength);
    int state = right.partialIsValidUtf8(leftPartial, 0, right.size());
    return state == Utf8.COMPLETE;
  }
 
  @Override
  protected int partialIsValidUtf8(int state, int offset, int length) {
    int toIndex = offset + length;
    if (toIndex <= leftLength) {
      return left.partialIsValidUtf8(state, offset, length);
    } else if (offset >= leftLength) {
      return right.partialIsValidUtf8(state, offset - leftLength, length);
    } else {
      int leftLength = this.leftLength - offset;
      int leftPartial = left.partialIsValidUtf8(state, offset, leftLength);
      return right.partialIsValidUtf8(leftPartial, 0, length - leftLength);
    }
  }
 
  // =================================================================
  // equals() and hashCode()
 
  @Override
  public boolean equals(Object other) {
    if (other == this) {
      return true;
    }
    if (!(other instanceof ByteString)) {
      return false;
    }
 
    ByteString otherByteString = (ByteString) other;
    if (totalLength != otherByteString.size()) {
      return false;
    }
    if (totalLength == 0) {
      return true;
    }
 
    // You don't really want to be calling equals on long strings, but since
    // we cache the hashCode, we effectively cache inequality. We use the cached
    // hashCode if it's already computed.  It's arguable we should compute the
    // hashCode here, and if we're going to be testing a bunch of byteStrings,
    // it might even make sense.
    int thisHash = peekCachedHashCode();
    int thatHash = otherByteString.peekCachedHashCode();
    if (thisHash != 0 && thatHash != 0 && thisHash != thatHash) {
      return false;
    }
 
    return equalsFragments(otherByteString);
  }
 
  private boolean equalsFragments(ByteString other) {
    int thisOffset = 0;
    Iterator<LeafByteString> thisIter = new PieceIterator(this);
    LeafByteString thisString = thisIter.next();
 
    int thatOffset = 0;
    Iterator<LeafByteString> thatIter = new PieceIterator(other);
    LeafByteString thatString = thatIter.next();
 
    int pos = 0;
    while (true) {
      int thisRemaining = thisString.size() - thisOffset;
      int thatRemaining = thatString.size() - thatOffset;
      int bytesToCompare = Math.min(thisRemaining, thatRemaining);
 
      // At least one of the offsets will be zero
      boolean stillEqual =
          (thisOffset == 0)
              ? thisString.equalsRange(thatString, thatOffset, bytesToCompare)
              : thatString.equalsRange(thisString, thisOffset, bytesToCompare);
      if (!stillEqual) {
        return false;
      }
 
      pos += bytesToCompare;
      if (pos >= totalLength) {
        if (pos == totalLength) {
          return true;
        }
        throw new IllegalStateException();
      }
      // We always get to the end of at least one of the pieces
      if (bytesToCompare == thisRemaining) { // If reached end of this
        thisOffset = 0;
        thisString = thisIter.next();
      } else {
        thisOffset += bytesToCompare;
      }
      if (bytesToCompare == thatRemaining) { // If reached end of that
        thatOffset = 0;
        thatString = thatIter.next();
      } else {
        thatOffset += bytesToCompare;
      }
    }
  }
 
  @Override
  protected int partialHash(int h, int offset, int length) {
    int toIndex = offset + length;
    if (toIndex <= leftLength) {
      return left.partialHash(h, offset, length);
    } else if (offset >= leftLength) {
      return right.partialHash(h, offset - leftLength, length);
    } else {
      int leftLength = this.leftLength - offset;
      int leftPartial = left.partialHash(h, offset, leftLength);
      return right.partialHash(leftPartial, 0, length - leftLength);
    }
  }
 
  // =================================================================
  // Input stream
 
  @Override
  public CodedInputStream newCodedInput() {
    return CodedInputStream.newInstance(new RopeInputStream());
  }
 
  @Override
  public InputStream newInput() {
    return new RopeInputStream();
  }
 
  private static class Balancer {
    // Stack containing the part of the string, starting from the left, that
    // we've already traversed.  The final string should be the equivalent of
    // concatenating the strings on the stack from bottom to top.
    private final ArrayDeque<ByteString> prefixesStack = new ArrayDeque<>();
 
    private ByteString balance(ByteString left, ByteString right) {
      doBalance(left);
      doBalance(right);
 
      // Sweep stack to gather the result
      ByteString partialString = prefixesStack.pop();
      while (!prefixesStack.isEmpty()) {
        ByteString newLeft = prefixesStack.pop();
        partialString = new RopeByteString(newLeft, partialString);
      }
      // We should end up with a RopeByteString since at a minimum we will
      // create one from concatenating left and right
      return partialString;
    }
 
    private void doBalance(ByteString root) {
      // BAP95: Insert balanced subtrees whole. This means the result might not
      // be balanced, leading to repeated rebalancings on concatenate. However,
      // these rebalancings are shallow due to ignoring balanced subtrees, and
      // relatively few calls to insert() result.
      if (root.isBalanced()) {
        insert(root);
      } else if (root instanceof RopeByteString) {
        RopeByteString rbs = (RopeByteString) root;
        doBalance(rbs.left);
        doBalance(rbs.right);
      } else {
        throw new IllegalArgumentException(
            "Has a new type of ByteString been created? Found " + root.getClass());
      }
    }
 
    private void insert(ByteString byteString) {
      int depthBin = getDepthBinForLength(byteString.size());
      int binEnd = minLengthByDepth[depthBin + 1];
 
      // BAP95: Concatenate all trees occupying bins representing the length of
      // our new piece or of shorter pieces, to the extent that is possible.
      // The goal is to clear the bin which our piece belongs in, but that may
      // not be entirely possible if there aren't enough longer bins occupied.
      if (prefixesStack.isEmpty() || prefixesStack.peek().size() >= binEnd) {
        prefixesStack.push(byteString);
      } else {
        int binStart = minLengthByDepth[depthBin];
 
        // Concatenate the subtrees of shorter length
        ByteString newTree = prefixesStack.pop();
        while (!prefixesStack.isEmpty() && prefixesStack.peek().size() < binStart) {
          ByteString left = prefixesStack.pop();
          newTree = new RopeByteString(left, newTree);
        }
 
        // Concatenate the given string
        newTree = new RopeByteString(newTree, byteString);
 
        // Continue concatenating until we land in an empty bin
        while (!prefixesStack.isEmpty()) {
          depthBin = getDepthBinForLength(newTree.size());
          binEnd = minLengthByDepth[depthBin + 1];
          if (prefixesStack.peek().size() < binEnd) {
            ByteString left = prefixesStack.pop();
            newTree = new RopeByteString(left, newTree);
          } else {
            break;
          }
        }
        prefixesStack.push(newTree);
      }
    }
 
    private int getDepthBinForLength(int length) {
      int depth = Arrays.binarySearch(minLengthByDepth, length);
      if (depth < 0) {
        // It wasn't an exact match, so convert to the index of the containing
        // fragment, which is one less even than the insertion point.
        int insertionPoint = -(depth + 1);
        depth = insertionPoint - 1;
      }
 
      return depth;
    }
  }
 
  private static final class PieceIterator implements Iterator<LeafByteString> {
    private final ArrayDeque<RopeByteString> breadCrumbs;
    private LeafByteString next;
 
    private PieceIterator(ByteString root) {
      if (root instanceof RopeByteString) {
        RopeByteString rbs = (RopeByteString) root;
        breadCrumbs = new ArrayDeque<>(rbs.getTreeDepth());
        breadCrumbs.push(rbs);
        next = getLeafByLeft(rbs.left);
      } else {
        breadCrumbs = null;
        next = (LeafByteString) root;
      }
    }
 
    private LeafByteString getLeafByLeft(ByteString root) {
      ByteString pos = root;
      while (pos instanceof RopeByteString) {
        RopeByteString rbs = (RopeByteString) pos;
        breadCrumbs.push(rbs);
        pos = rbs.left;
      }
      return (LeafByteString) pos;
    }
 
    private LeafByteString getNextNonEmptyLeaf() {
      while (true) {
        // Almost always, we go through this loop exactly once.  However, if
        // we discover an empty string in the rope, we toss it and try again.
        if (breadCrumbs == null || breadCrumbs.isEmpty()) {
          return null;
        } else {
          LeafByteString result = getLeafByLeft(breadCrumbs.pop().right);
          if (!result.isEmpty()) {
            return result;
          }
        }
      }
    }
 
    @Override
    public boolean hasNext() {
      return next != null;
    }
 
    @Override
    public LeafByteString next() {
      if (next == null) {
        throw new NoSuchElementException();
      }
      LeafByteString result = next;
      next = getNextNonEmptyLeaf();
      return result;
    }
 
    @Override
    public void remove() {
      throw new UnsupportedOperationException();
    }
  }
 
  // =================================================================
  // Serializable
 
  private static final long serialVersionUID = 1L;
 
  Object writeReplace() {
    return ByteString.wrap(toByteArray());
  }
 
  private void readObject(@SuppressWarnings("unused") ObjectInputStream in) throws IOException {
    throw new InvalidObjectException("RopeByteStream instances are not to be serialized directly");
  }
 
  private class RopeInputStream extends InputStream {
    // Iterates through the pieces of the rope
    private PieceIterator pieceIterator;
    // The current piece
    private LeafByteString currentPiece;
    // The size of the current piece
    private int currentPieceSize;
    // The index of the next byte to read in the current piece
    private int currentPieceIndex;
    // The offset of the start of the current piece in the rope byte string
    private int currentPieceOffsetInRope;
    // Offset in the buffer at which user called mark();
    private int mark;
 
    public RopeInputStream() {
      initialize();
    }
 
    @Override
    public int read(byte[] b, int offset, int length) {
      if (b == null) {
        throw new NullPointerException();
      } else if (offset < 0 || length < 0 || length > b.length - offset) {
        throw new IndexOutOfBoundsException();
      }
      return readSkipInternal(b, offset, length);
    }
 
    @Override
    public long skip(long length) {
      if (length < 0) {
        throw new IndexOutOfBoundsException();
      } else if (length > Integer.MAX_VALUE) {
        length = Integer.MAX_VALUE;
      }
      return readSkipInternal(null, 0, (int) length);
    }
 
    private int readSkipInternal(byte[] b, int offset, int length) {
      int bytesRemaining = length;
      while (bytesRemaining > 0) {
        advanceIfCurrentPieceFullyRead();
        if (currentPiece == null) {
          if (bytesRemaining == length) {
            // We didn't manage to read anything
            return -1;
          }
          break;
        } else {
          // Copy the bytes from this piece.
          int currentPieceRemaining = currentPieceSize - currentPieceIndex;
          int count = Math.min(currentPieceRemaining, bytesRemaining);
          if (b != null) {
            currentPiece.copyTo(b, currentPieceIndex, offset, count);
            offset += count;
          }
          currentPieceIndex += count;
          bytesRemaining -= count;
        }
      }
      // Return the number of bytes read.
      return length - bytesRemaining;
    }
 
    @Override
    public int read() throws IOException {
      advanceIfCurrentPieceFullyRead();
      if (currentPiece == null) {
        return -1;
      } else {
        return currentPiece.byteAt(currentPieceIndex++) & 0xFF;
      }
    }
 
    @Override
    public int available() throws IOException {
      int bytesRead = currentPieceOffsetInRope + currentPieceIndex;
      return RopeByteString.this.size() - bytesRead;
    }
 
    @Override
    public boolean markSupported() {
      return true;
    }
 
    @Override
    public void mark(int readAheadLimit) {
      // Set the mark to our position in the byte string
      mark = currentPieceOffsetInRope + currentPieceIndex;
    }
 
    @Override
    public synchronized void reset() {
      // Just reinitialize and skip the specified number of bytes.
      initialize();
      readSkipInternal(null, 0, mark);
    }
 
    private void initialize() {
      pieceIterator = new PieceIterator(RopeByteString.this);
      currentPiece = pieceIterator.next();
      currentPieceSize = currentPiece.size();
      currentPieceIndex = 0;
      currentPieceOffsetInRope = 0;
    }
 
    private void advanceIfCurrentPieceFullyRead() {
      if (currentPiece != null && currentPieceIndex == currentPieceSize) {
        // Generally, we can only go through this loop at most once, since
        // empty strings can't end up in a rope.  But better to test.
        currentPieceOffsetInRope += currentPieceSize;
        currentPieceIndex = 0;
        if (pieceIterator.hasNext()) {
          currentPiece = pieceIterator.next();
          currentPieceSize = currentPiece.size();
        } else {
          currentPiece = null;
          currentPieceSize = 0;
        }
      }
    }
  }
}