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