java/src/test/java/com/google/protobuf/ByteStringTest.java

   1 // Protocol Buffers - Google's data interchange format
   2 // Copyright 2008 Google Inc.  All rights reserved.
   3 // https://developers.google.com/protocol-buffers/
   4 //
   5 // Redistribution and use in source and binary forms, with or without
   6 // modification, are permitted provided that the following conditions are
   7 // met:
   8 //
   9 //     * Redistributions of source code must retain the above copyright
  10 // notice, this list of conditions and the following disclaimer.
  11 //     * Redistributions in binary form must reproduce the above
  12 // copyright notice, this list of conditions and the following disclaimer
  13 // in the documentation and/or other materials provided with the
  14 // distribution.
  15 //     * Neither the name of Google Inc. nor the names of its
  16 // contributors may be used to endorse or promote products derived from
  17 // this software without specific prior written permission.
  18 //
  19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30
  31 package com.google.protobuf;
  32
  33 import com.google.protobuf.ByteString.Output;
  34
  35 import junit.framework.TestCase;
  36
  37 import java.io.ByteArrayInputStream;
  38 import java.io.ByteArrayOutputStream;
  39 import java.io.IOException;
  40 import java.io.InputStream;
  41 import java.io.OutputStream;
  42 import java.io.UnsupportedEncodingException;
  43 import java.nio.ByteBuffer;
  44 import java.util.ArrayList;
  45 import java.util.Arrays;
  46 import java.util.Iterator;
  47 import java.util.List;
  48 import java.util.NoSuchElementException;
  49 import java.util.Random;
  50
  51 /**
  52  * Test methods with implementations in {@link ByteString}, plus do some top-level "integration"
  53  * tests.
  54  *
  55  * @author carlanton@google.com (Carl Haverl)
  56  */
  57 public class ByteStringTest extends TestCase {
  58
  59   private static final String UTF_16 = "UTF-16";
  60
  61   static byte[] getTestBytes(int size, long seed) {
  62     Random random = new Random(seed);
  63     byte[] result = new byte[size];
  64     random.nextBytes(result);
  65     return result;
  66   }
  67
  68   private byte[] getTestBytes(int size) {
  69     return getTestBytes(size, 445566L);
  70   }
  71
  72   private byte[] getTestBytes() {
  73     return getTestBytes(1000);
  74   }
  75
  76   // Compare the entire left array with a subset of the right array.
  77   private boolean isArrayRange(byte[] left, byte[] right, int rightOffset, int length) {
  78     boolean stillEqual = (left.length == length);
  79     for (int i = 0; (stillEqual && i < length); ++i) {
  80       stillEqual = (left[i] == right[rightOffset + i]);
  81     }
  82     return stillEqual;
  83   }
  84
  85   // Returns true only if the given two arrays have identical contents.
  86   private boolean isArray(byte[] left, byte[] right) {
  87     return left.length == right.length && isArrayRange(left, right, 0, left.length);
  88   }
  89
  90   public void testSubstring_BeginIndex() {
  91     byte[] bytes = getTestBytes();
  92     ByteString substring = ByteString.copyFrom(bytes).substring(500);
  93     assertTrue("substring must contain the tail of the string",
  94         isArrayRange(substring.toByteArray(), bytes, 500, bytes.length - 500));
  95   }
  96
  97   public void testCopyFrom_BytesOffsetSize() {
  98     byte[] bytes = getTestBytes();
  99     ByteString byteString = ByteString.copyFrom(bytes, 500, 200);
 100     assertTrue("copyFrom sub-range must contain the expected bytes",
 101         isArrayRange(byteString.toByteArray(), bytes, 500, 200));
 102   }
 103
 104   public void testCopyFrom_Bytes() {
 105     byte[] bytes = getTestBytes();
 106     ByteString byteString = ByteString.copyFrom(bytes);
 107     assertTrue("copyFrom must contain the expected bytes",
 108         isArray(byteString.toByteArray(), bytes));
 109   }
 110
 111   public void testCopyFrom_ByteBufferSize() {
 112     byte[] bytes = getTestBytes();
 113     ByteBuffer byteBuffer = ByteBuffer.allocate(bytes.length);
 114     byteBuffer.put(bytes);
 115     byteBuffer.position(500);
 116     ByteString byteString = ByteString.copyFrom(byteBuffer, 200);
 117     assertTrue("copyFrom byteBuffer sub-range must contain the expected bytes",
 118         isArrayRange(byteString.toByteArray(), bytes, 500, 200));
 119   }
 120
 121   public void testCopyFrom_ByteBuffer() {
 122     byte[] bytes = getTestBytes();
 123     ByteBuffer byteBuffer = ByteBuffer.allocate(bytes.length);
 124     byteBuffer.put(bytes);
 125     byteBuffer.position(500);
 126     ByteString byteString = ByteString.copyFrom(byteBuffer);
 127     assertTrue("copyFrom byteBuffer sub-range must contain the expected bytes",
 128         isArrayRange(byteString.toByteArray(), bytes, 500, bytes.length - 500));
 129   }
 130
 131   public void testCopyFrom_StringEncoding() throws UnsupportedEncodingException {
 132     String testString = "I love unicode \u1234\u5678 characters";
 133     ByteString byteString = ByteString.copyFrom(testString, UTF_16);
 134     byte[] testBytes = testString.getBytes(UTF_16);
 135     assertTrue("copyFrom string must respect the charset",
 136         isArrayRange(byteString.toByteArray(), testBytes, 0, testBytes.length));
 137   }
 138
 139   public void testCopyFrom_Utf8() throws UnsupportedEncodingException {
 140     String testString = "I love unicode \u1234\u5678 characters";
 141     ByteString byteString = ByteString.copyFromUtf8(testString);
 142     byte[] testBytes = testString.getBytes("UTF-8");
 143     assertTrue("copyFromUtf8 string must respect the charset",
 144         isArrayRange(byteString.toByteArray(), testBytes, 0, testBytes.length));
 145   }
 146
 147   public void testCopyFrom_Iterable() {
 148     byte[] testBytes = getTestBytes(77777, 113344L);
 149     final List<ByteString> pieces = makeConcretePieces(testBytes);
 150     // Call copyFrom() on a Collection
 151     ByteString byteString = ByteString.copyFrom(pieces);
 152     assertTrue("copyFrom a List must contain the expected bytes",
 153         isArrayRange(byteString.toByteArray(), testBytes, 0, testBytes.length));
 154     // Call copyFrom on an iteration that's not a collection
 155     ByteString byteStringAlt = ByteString.copyFrom(new Iterable<ByteString>() {
 156       public Iterator<ByteString> iterator() {
 157         return pieces.iterator();
 158       }
 159     });
 160     assertEquals("copyFrom from an Iteration must contain the expected bytes",
 161         byteString, byteStringAlt);
 162   }
 163
 164   public void testCopyTo_TargetOffset() {
 165     byte[] bytes = getTestBytes();
 166     ByteString byteString = ByteString.copyFrom(bytes);
 167     byte[] target = new byte[bytes.length + 1000];
 168     byteString.copyTo(target, 400);
 169     assertTrue("copyFrom byteBuffer sub-range must contain the expected bytes",
 170         isArrayRange(bytes, target, 400, bytes.length));
 171   }
 172
 173   public void testReadFrom_emptyStream() throws IOException {
 174     ByteString byteString =
 175         ByteString.readFrom(new ByteArrayInputStream(new byte[0]));
 176     assertSame("reading an empty stream must result in the EMPTY constant "
 177         + "byte string", ByteString.EMPTY, byteString);
 178   }
 179
 180   public void testReadFrom_smallStream() throws IOException {
 181     assertReadFrom(getTestBytes(10));
 182   }
 183
 184   public void testReadFrom_mutating() throws IOException {
 185     byte[] capturedArray = null;
 186     EvilInputStream eis = new EvilInputStream();
 187     ByteString byteString = ByteString.readFrom(eis);
 188
 189     capturedArray = eis.capturedArray;
 190     byte[] originalValue = byteString.toByteArray();
 191     for (int x = 0; x < capturedArray.length; ++x) {
 192       capturedArray[x] = (byte) 0;
 193     }
 194
 195     byte[] newValue = byteString.toByteArray();
 196     assertTrue("copyFrom byteBuffer must not grant access to underlying array",
 197         Arrays.equals(originalValue, newValue));
 198   }
 199
 200   // Tests sizes that are near the rope copy-out threshold.
 201   public void testReadFrom_mediumStream() throws IOException {
 202     assertReadFrom(getTestBytes(ByteString.CONCATENATE_BY_COPY_SIZE - 1));
 203     assertReadFrom(getTestBytes(ByteString.CONCATENATE_BY_COPY_SIZE));
 204     assertReadFrom(getTestBytes(ByteString.CONCATENATE_BY_COPY_SIZE + 1));
 205     assertReadFrom(getTestBytes(200));
 206   }
 207
 208   // Tests sizes that are over multi-segment rope threshold.
 209   public void testReadFrom_largeStream() throws IOException {
 210     assertReadFrom(getTestBytes(0x100));
 211     assertReadFrom(getTestBytes(0x101));
 212     assertReadFrom(getTestBytes(0x110));
 213     assertReadFrom(getTestBytes(0x1000));
 214     assertReadFrom(getTestBytes(0x1001));
 215     assertReadFrom(getTestBytes(0x1010));
 216     assertReadFrom(getTestBytes(0x10000));
 217     assertReadFrom(getTestBytes(0x10001));
 218     assertReadFrom(getTestBytes(0x10010));
 219   }
 220
 221   // Tests sizes that are near the read buffer size.
 222   public void testReadFrom_byteBoundaries() throws IOException {
 223     final int min = ByteString.MIN_READ_FROM_CHUNK_SIZE;
 224     final int max = ByteString.MAX_READ_FROM_CHUNK_SIZE;
 225
 226     assertReadFrom(getTestBytes(min - 1));
 227     assertReadFrom(getTestBytes(min));
 228     assertReadFrom(getTestBytes(min + 1));
 229
 230     assertReadFrom(getTestBytes(min * 2 - 1));
 231     assertReadFrom(getTestBytes(min * 2));
 232     assertReadFrom(getTestBytes(min * 2 + 1));
 233
 234     assertReadFrom(getTestBytes(min * 4 - 1));
 235     assertReadFrom(getTestBytes(min * 4));
 236     assertReadFrom(getTestBytes(min * 4 + 1));
 237
 238     assertReadFrom(getTestBytes(min * 8 - 1));
 239     assertReadFrom(getTestBytes(min * 8));
 240     assertReadFrom(getTestBytes(min * 8 + 1));
 241
 242     assertReadFrom(getTestBytes(max - 1));
 243     assertReadFrom(getTestBytes(max));
 244     assertReadFrom(getTestBytes(max + 1));
 245
 246     assertReadFrom(getTestBytes(max * 2 - 1));
 247     assertReadFrom(getTestBytes(max * 2));
 248     assertReadFrom(getTestBytes(max * 2 + 1));
 249   }
 250
 251   // Tests that IOExceptions propagate through ByteString.readFrom().
 252   public void testReadFrom_IOExceptions() {
 253     try {
 254       ByteString.readFrom(new FailStream());
 255       fail("readFrom must throw the underlying IOException");
 256
 257     } catch (IOException e) {
 258       assertEquals("readFrom must throw the expected exception",
 259                    "synthetic failure", e.getMessage());
 260     }
 261   }
 262
 263   // Tests that ByteString.readFrom works with streams that don't
 264   // always fill their buffers.
 265   public void testReadFrom_reluctantStream() throws IOException {
 266     final byte[] data = getTestBytes(0x1000);
 267
 268     ByteString byteString = ByteString.readFrom(new ReluctantStream(data));
 269     assertTrue("readFrom byte stream must contain the expected bytes",
 270         isArray(byteString.toByteArray(), data));
 271
 272     // Same test as above, but with some specific chunk sizes.
 273     assertReadFromReluctantStream(data, 100);
 274     assertReadFromReluctantStream(data, 248);
 275     assertReadFromReluctantStream(data, 249);
 276     assertReadFromReluctantStream(data, 250);
 277     assertReadFromReluctantStream(data, 251);
 278     assertReadFromReluctantStream(data, 0x1000);
 279     assertReadFromReluctantStream(data, 0x1001);
 280   }
 281
 282   // Fails unless ByteString.readFrom reads the bytes correctly from a
 283   // reluctant stream with the given chunkSize parameter.
 284   private void assertReadFromReluctantStream(byte[] bytes, int chunkSize)
 285       throws IOException {
 286     ByteString b = ByteString.readFrom(new ReluctantStream(bytes), chunkSize);
 287     assertTrue("readFrom byte stream must contain the expected bytes",
 288         isArray(b.toByteArray(), bytes));
 289   }
 290
 291   // Tests that ByteString.readFrom works with streams that implement
 292   // available().
 293   public void testReadFrom_available() throws IOException {
 294     final byte[] data = getTestBytes(0x1001);
 295
 296     ByteString byteString = ByteString.readFrom(new AvailableStream(data));
 297     assertTrue("readFrom byte stream must contain the expected bytes",
 298         isArray(byteString.toByteArray(), data));
 299   }
 300
 301   // Fails unless ByteString.readFrom reads the bytes correctly.
 302   private void assertReadFrom(byte[] bytes) throws IOException {
 303     ByteString byteString =
 304         ByteString.readFrom(new ByteArrayInputStream(bytes));
 305     assertTrue("readFrom byte stream must contain the expected bytes",
 306         isArray(byteString.toByteArray(), bytes));
 307   }
 308
 309   // A stream that fails when read.
 310   private static final class FailStream extends InputStream {
 311     @Override public int read() throws IOException {
 312       throw new IOException("synthetic failure");
 313     }
 314   }
 315
 316   // A stream that simulates blocking by only producing 250 characters
 317   // per call to read(byte[]).
 318   private static class ReluctantStream extends InputStream {
 319     protected final byte[] data;
 320     protected int pos = 0;
 321
 322     public ReluctantStream(byte[] data) {
 323       this.data = data;
 324     }
 325
 326     @Override public int read() {
 327       if (pos == data.length) {
 328         return -1;
 329       } else {
 330         return data[pos++];
 331       }
 332     }
 333
 334     @Override public int read(byte[] buf) {
 335       return read(buf, 0, buf.length);
 336     }
 337
 338     @Override public int read(byte[] buf, int offset, int size) {
 339       if (pos == data.length) {
 340         return -1;
 341       }
 342       int count = Math.min(Math.min(size, data.length - pos), 250);
 343       System.arraycopy(data, pos, buf, offset, count);
 344       pos += count;
 345       return count;
 346     }
 347   }
 348
 349   // Same as above, but also implements available().
 350   private static final class AvailableStream extends ReluctantStream {
 351     public AvailableStream(byte[] data) {
 352       super(data);
 353     }
 354
 355     @Override public int available() {
 356       return Math.min(250, data.length - pos);
 357     }
 358   }
 359
 360   // A stream which exposes the byte array passed into read(byte[], int, int).
 361   private static class EvilInputStream extends InputStream {
 362     public byte[] capturedArray = null;
 363
 364     @Override
 365     public int read(byte[] buf, int off, int len) {
 366       if (capturedArray != null) {
 367         return -1;
 368       } else {
 369         capturedArray = buf;
 370         for (int x = 0; x < len; ++x) {
 371           buf[x] = (byte) x;
 372         }
 373         return len;
 374       }
 375     }
 376
 377     @Override
 378     public int read() {
 379       // Purposefully do nothing.
 380       return -1;
 381     }
 382   }
 383
 384   // A stream which exposes the byte array passed into write(byte[], int, int).
 385   private static class EvilOutputStream extends OutputStream {
 386     public byte[] capturedArray = null;
 387
 388     @Override
 389     public void write(byte[] buf, int off, int len) {
 390       if (capturedArray == null) {
 391         capturedArray = buf;
 392       }
 393     }
 394
 395     @Override
 396     public void write(int ignored) {
 397       // Purposefully do nothing.
 398     }
 399   }
 400
 401   public void testToStringUtf8() throws UnsupportedEncodingException {
 402     String testString = "I love unicode \u1234\u5678 characters";
 403     byte[] testBytes = testString.getBytes("UTF-8");
 404     ByteString byteString = ByteString.copyFrom(testBytes);
 405     assertEquals("copyToStringUtf8 must respect the charset",
 406         testString, byteString.toStringUtf8());
 407   }
 408
 409   public void testNewOutput_InitialCapacity() throws IOException {
 410     byte[] bytes = getTestBytes();
 411     ByteString.Output output = ByteString.newOutput(bytes.length + 100);
 412     output.write(bytes);
 413     ByteString byteString = output.toByteString();
 414     assertTrue(
 415         "String built from newOutput(int) must contain the expected bytes",
 416         isArrayRange(bytes, byteString.toByteArray(), 0, bytes.length));
 417   }
 418
 419   // Test newOutput() using a variety of buffer sizes and a variety of (fixed)
 420   // write sizes
 421   public void testNewOutput_ArrayWrite() throws IOException {
 422     byte[] bytes = getTestBytes();
 423     int length = bytes.length;
 424     int[] bufferSizes = {128, 256, length / 2, length - 1, length, length + 1,
 425                          2 * length, 3 * length};
 426     int[] writeSizes = {1, 4, 5, 7, 23, bytes.length};
 427
 428     for (int bufferSize : bufferSizes) {
 429       for (int writeSize : writeSizes) {
 430         // Test writing the entire output writeSize bytes at a time.
 431         ByteString.Output output = ByteString.newOutput(bufferSize);
 432         for (int i = 0; i < length; i += writeSize) {
 433           output.write(bytes, i, Math.min(writeSize, length - i));
 434         }
 435         ByteString byteString = output.toByteString();
 436         assertTrue("String built from newOutput() must contain the expected bytes",
 437             isArrayRange(bytes, byteString.toByteArray(), 0, bytes.length));
 438       }
 439     }
 440   }
 441
 442   // Test newOutput() using a variety of buffer sizes, but writing all the
 443   // characters using write(byte);
 444   public void testNewOutput_WriteChar() throws IOException {
 445     byte[] bytes = getTestBytes();
 446     int length = bytes.length;
 447     int[] bufferSizes = {0, 1, 128, 256, length / 2,
 448                          length - 1, length, length + 1,
 449                          2 * length, 3 * length};
 450     for (int bufferSize : bufferSizes) {
 451       ByteString.Output output = ByteString.newOutput(bufferSize);
 452       for (byte byteValue : bytes) {
 453         output.write(byteValue);
 454       }
 455       ByteString byteString = output.toByteString();
 456       assertTrue("String built from newOutput() must contain the expected bytes",
 457           isArrayRange(bytes, byteString.toByteArray(), 0, bytes.length));
 458     }
 459   }
 460
 461   // Test newOutput() in which we write the bytes using a variety of methods
 462   // and sizes, and in which we repeatedly call toByteString() in the middle.
 463   public void testNewOutput_Mixed() throws IOException {
 464     Random rng = new Random(1);
 465     byte[] bytes = getTestBytes();
 466     int length = bytes.length;
 467     int[] bufferSizes = {0, 1, 128, 256, length / 2,
 468                          length - 1, length, length + 1,
 469                          2 * length, 3 * length};
 470
 471     for (int bufferSize : bufferSizes) {
 472       // Test writing the entire output using a mixture of write sizes and
 473       // methods;
 474       ByteString.Output output = ByteString.newOutput(bufferSize);
 475       int position = 0;
 476       while (position < bytes.length) {
 477         if (rng.nextBoolean()) {
 478           int count = 1 + rng.nextInt(bytes.length - position);
 479           output.write(bytes, position, count);
 480           position += count;
 481         } else {
 482           output.write(bytes[position]);
 483           position++;
 484         }
 485         assertEquals("size() returns the right value", position, output.size());
 486         assertTrue("newOutput() substring must have correct bytes",
 487             isArrayRange(output.toByteString().toByteArray(),
 488                 bytes, 0, position));
 489       }
 490       ByteString byteString = output.toByteString();
 491       assertTrue("String built from newOutput() must contain the expected bytes",
 492           isArrayRange(bytes, byteString.toByteArray(), 0, bytes.length));
 493     }
 494   }
 495
 496   public void testNewOutputEmpty() throws IOException {
 497     // Make sure newOutput() correctly builds empty byte strings
 498     ByteString byteString = ByteString.newOutput().toByteString();
 499     assertEquals(ByteString.EMPTY, byteString);
 500   }
 501
 502   public void testNewOutput_Mutating() throws IOException {
 503     Output os = ByteString.newOutput(5);
 504     os.write(new byte[] {1, 2, 3, 4, 5});
 505     EvilOutputStream eos = new EvilOutputStream();
 506     os.writeTo(eos);
 507     byte[] capturedArray = eos.capturedArray;
 508     ByteString byteString = os.toByteString();
 509     byte[] oldValue = byteString.toByteArray();
 510     Arrays.fill(capturedArray, (byte) 0);
 511     byte[] newValue = byteString.toByteArray();
 512     assertTrue("Output must not provide access to the underlying byte array",
 513         Arrays.equals(oldValue, newValue));
 514   }
 515
 516   public void testNewCodedBuilder() throws IOException {
 517     byte[] bytes = getTestBytes();
 518     ByteString.CodedBuilder builder = ByteString.newCodedBuilder(bytes.length);
 519     builder.getCodedOutput().writeRawBytes(bytes);
 520     ByteString byteString = builder.build();
 521     assertTrue("String built from newCodedBuilder() must contain the expected bytes",
 522         isArrayRange(bytes, byteString.toByteArray(), 0, bytes.length));
 523   }
 524
 525   public void testSubstringParity() {
 526     byte[] bigBytes = getTestBytes(2048 * 1024, 113344L);
 527     int start = 512 * 1024 - 3333;
 528     int end   = 512 * 1024 + 7777;
 529     ByteString concreteSubstring = ByteString.copyFrom(bigBytes).substring(start, end);
 530     boolean ok = true;
 531     for (int i = start; ok && i < end; ++i) {
 532       ok = (bigBytes[i] == concreteSubstring.byteAt(i - start));
 533     }
 534     assertTrue("Concrete substring didn't capture the right bytes", ok);
 535
 536     ByteString literalString = ByteString.copyFrom(bigBytes, start, end - start);
 537     assertTrue("Substring must be equal to literal string",
 538         concreteSubstring.equals(literalString));
 539     assertEquals("Substring must have same hashcode as literal string",
 540         literalString.hashCode(), concreteSubstring.hashCode());
 541   }
 542
 543   public void testCompositeSubstring() {
 544     byte[] referenceBytes = getTestBytes(77748, 113344L);
 545
 546     List<ByteString> pieces = makeConcretePieces(referenceBytes);
 547     ByteString listString = ByteString.copyFrom(pieces);
 548
 549     int from = 1000;
 550     int to = 40000;
 551     ByteString compositeSubstring = listString.substring(from, to);
 552     byte[] substringBytes = compositeSubstring.toByteArray();
 553     boolean stillEqual = true;
 554     for (int i = 0; stillEqual && i < to - from; ++i) {
 555       stillEqual = referenceBytes[from + i] == substringBytes[i];
 556     }
 557     assertTrue("Substring must return correct bytes", stillEqual);
 558
 559     stillEqual = true;
 560     for (int i = 0; stillEqual && i < to - from; ++i) {
 561       stillEqual = referenceBytes[from + i] == compositeSubstring.byteAt(i);
 562     }
 563     assertTrue("Substring must support byteAt() correctly", stillEqual);
 564
 565     ByteString literalSubstring = ByteString.copyFrom(referenceBytes, from, to - from);
 566     assertTrue("Composite substring must equal a literal substring over the same bytes",
 567         compositeSubstring.equals(literalSubstring));
 568     assertTrue("Literal substring must equal a composite substring over the same bytes",
 569         literalSubstring.equals(compositeSubstring));
 570
 571     assertEquals("We must get the same hashcodes for composite and literal substrings",
 572         literalSubstring.hashCode(), compositeSubstring.hashCode());
 573
 574     assertFalse("We can't be equal to a proper substring",
 575         compositeSubstring.equals(literalSubstring.substring(0, literalSubstring.size() - 1)));
 576   }
 577
 578   public void testCopyFromList() {
 579     byte[] referenceBytes = getTestBytes(77748, 113344L);
 580     ByteString literalString = ByteString.copyFrom(referenceBytes);
 581
 582     List<ByteString> pieces = makeConcretePieces(referenceBytes);
 583     ByteString listString = ByteString.copyFrom(pieces);
 584
 585     assertTrue("Composite string must be equal to literal string",
 586         listString.equals(literalString));
 587     assertEquals("Composite string must have same hashcode as literal string",
 588         literalString.hashCode(), listString.hashCode());
 589   }
 590
 591   public void testConcat() {
 592     byte[] referenceBytes = getTestBytes(77748, 113344L);
 593     ByteString literalString = ByteString.copyFrom(referenceBytes);
 594
 595     List<ByteString> pieces = makeConcretePieces(referenceBytes);
 596
 597     Iterator<ByteString> iter = pieces.iterator();
 598     ByteString concatenatedString = iter.next();
 599     while (iter.hasNext()) {
 600       concatenatedString = concatenatedString.concat(iter.next());
 601     }
 602
 603     assertTrue("Concatenated string must be equal to literal string",
 604         concatenatedString.equals(literalString));
 605     assertEquals("Concatenated string must have same hashcode as literal string",
 606         literalString.hashCode(), concatenatedString.hashCode());
 607   }
 608
 609   /**
 610    * Test the Rope implementation can deal with Empty nodes, even though we
 611    * guard against them. See also {@link LiteralByteStringTest#testConcat_empty()}.
 612    */
 613   public void testConcat_empty() {
 614     byte[] referenceBytes = getTestBytes(7748, 113344L);
 615     ByteString literalString = ByteString.copyFrom(referenceBytes);
 616
 617     ByteString duo = RopeByteString.newInstanceForTest(literalString, literalString);
 618     ByteString temp = RopeByteString.newInstanceForTest(
 619         RopeByteString.newInstanceForTest(literalString, ByteString.EMPTY),
 620         RopeByteString.newInstanceForTest(ByteString.EMPTY, literalString));
 621     ByteString quintet = RopeByteString.newInstanceForTest(temp, ByteString.EMPTY);
 622
 623     assertTrue("String with concatenated nulls must equal simple concatenate",
 624         duo.equals(quintet));
 625     assertEquals("String with concatenated nulls have same hashcode as simple concatenate",
 626         duo.hashCode(), quintet.hashCode());
 627
 628     ByteString.ByteIterator duoIter = duo.iterator();
 629     ByteString.ByteIterator quintetIter = quintet.iterator();
 630     boolean stillEqual = true;
 631     while (stillEqual && quintetIter.hasNext()) {
 632       stillEqual = (duoIter.nextByte() == quintetIter.nextByte());
 633     }
 634     assertTrue("We must get the same characters by iterating", stillEqual);
 635     assertFalse("Iterator must be exhausted", duoIter.hasNext());
 636     try {
 637       duoIter.nextByte();
 638       fail("Should have thrown an exception.");
 639     } catch (NoSuchElementException e) {
 640       // This is success
 641     }
 642     try {
 643       quintetIter.nextByte();
 644       fail("Should have thrown an exception.");
 645     } catch (NoSuchElementException e) {
 646       // This is success
 647     }
 648
 649     // Test that even if we force empty strings in as rope leaves in this
 650     // configuration, we always get a (possibly Bounded) LiteralByteString
 651     // for a length 1 substring.
 652     //
 653     // It is possible, using the testing factory method to create deeply nested
 654     // trees of empty leaves, to make a string that will fail this test.
 655     for (int i = 1; i < duo.size(); ++i) {
 656       assertTrue("Substrings of size() < 2 must not be RopeByteStrings",
 657           duo.substring(i - 1, i) instanceof LiteralByteString);
 658     }
 659     for (int i = 1; i < quintet.size(); ++i) {
 660       assertTrue("Substrings of size() < 2 must not be RopeByteStrings",
 661           quintet.substring(i - 1, i) instanceof LiteralByteString);
 662     }
 663   }
 664
 665   public void testStartsWith() {
 666     byte[] bytes = getTestBytes(1000, 1234L);
 667     ByteString string = ByteString.copyFrom(bytes);
 668     ByteString prefix = ByteString.copyFrom(bytes, 0, 500);
 669     ByteString suffix = ByteString.copyFrom(bytes, 400, 600);
 670     assertTrue(string.startsWith(ByteString.EMPTY));
 671     assertTrue(string.startsWith(string));
 672     assertTrue(string.startsWith(prefix));
 673     assertFalse(string.startsWith(suffix));
 674     assertFalse(prefix.startsWith(suffix));
 675     assertFalse(suffix.startsWith(prefix));
 676     assertFalse(ByteString.EMPTY.startsWith(prefix));
 677     assertTrue(ByteString.EMPTY.startsWith(ByteString.EMPTY));
 678   }
 679
 680   public void testEndsWith() {
 681     byte[] bytes = getTestBytes(1000, 1234L);
 682     ByteString string = ByteString.copyFrom(bytes);
 683     ByteString prefix = ByteString.copyFrom(bytes, 0, 500);
 684     ByteString suffix = ByteString.copyFrom(bytes, 400, 600);
 685     assertTrue(string.endsWith(ByteString.EMPTY));
 686     assertTrue(string.endsWith(string));
 687     assertTrue(string.endsWith(suffix));
 688     assertFalse(string.endsWith(prefix));
 689     assertFalse(suffix.endsWith(prefix));
 690     assertFalse(prefix.endsWith(suffix));
 691     assertFalse(ByteString.EMPTY.endsWith(suffix));
 692     assertTrue(ByteString.EMPTY.endsWith(ByteString.EMPTY));
 693   }
 694
 695   static List<ByteString> makeConcretePieces(byte[] referenceBytes) {
 696     List<ByteString> pieces = new ArrayList<ByteString>();
 697     // Starting length should be small enough that we'll do some concatenating by
 698     // copying if we just concatenate all these pieces together.
 699     for (int start = 0, length = 16; start < referenceBytes.length; start += length) {
 700       length = (length << 1) - 1;
 701       if (start + length > referenceBytes.length) {
 702         length = referenceBytes.length - start;
 703       }
 704       pieces.add(ByteString.copyFrom(referenceBytes, start, length));
 705     }
 706     return pieces;
 707   }
 708
 709   private byte[] substringUsingWriteTo(
 710       ByteString data, int offset, int length) throws IOException {
 711     ByteArrayOutputStream output = new ByteArrayOutputStream();
 712     data.writeTo(output, offset, length);
 713     return output.toByteArray();
 714   }
 715
 716   public void testWriteToOutputStream() throws Exception {
 717     // Choose a size large enough so when two ByteStrings are concatenated they
 718     // won't be merged into one byte array due to some optimizations.
 719     final int dataSize = ByteString.CONCATENATE_BY_COPY_SIZE + 1;
 720     byte[] data1 = new byte[dataSize];
 721     for (int i = 0; i < data1.length; i++) {
 722       data1[i] = (byte) 1;
 723     }
 724     data1[1] = (byte) 11;
 725     // Test LiteralByteString.writeTo(OutputStream,int,int)
 726     LiteralByteString left = new LiteralByteString(data1);
 727     byte[] result = substringUsingWriteTo(left, 1, 1);
 728     assertEquals(1, result.length);
 729     assertEquals((byte) 11, result[0]);
 730
 731     byte[] data2 = new byte[dataSize];
 732     for (int i = 0; i < data1.length; i++) {
 733       data2[i] = (byte) 2;
 734     }
 735     LiteralByteString right = new LiteralByteString(data2);
 736     // Concatenate two ByteStrings to create a RopeByteString.
 737     ByteString root = left.concat(right);
 738     // Make sure we are actually testing a RopeByteString with a simple tree
 739     // structure.
 740     assertEquals(1, root.getTreeDepth());
 741     // Write parts of the left node.
 742     result = substringUsingWriteTo(root, 0, dataSize);
 743     assertEquals(dataSize, result.length);
 744     assertEquals((byte) 1, result[0]);
 745     assertEquals((byte) 1, result[dataSize - 1]);
 746     // Write parts of the right node.
 747     result = substringUsingWriteTo(root, dataSize, dataSize);
 748     assertEquals(dataSize, result.length);
 749     assertEquals((byte) 2, result[0]);
 750     assertEquals((byte) 2, result[dataSize - 1]);
 751     // Write a segment of bytes that runs across both nodes.
 752     result = substringUsingWriteTo(root, dataSize / 2, dataSize);
 753     assertEquals(dataSize, result.length);
 754     assertEquals((byte) 1, result[0]);
 755     assertEquals((byte) 1, result[dataSize - dataSize / 2 - 1]);
 756     assertEquals((byte) 2, result[dataSize - dataSize / 2]);
 757     assertEquals((byte) 2, result[dataSize - 1]);
 758   }
 759 }