src/google/protobuf/repeated_field_unittest.cc

   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 // Author: kenton@google.com (Kenton Varda)
  32 //  Based on original Protocol Buffers design by
  33 //  Sanjay Ghemawat, Jeff Dean, and others.
  34 //
  35 // TODO(kenton):  Improve this unittest to bring it up to the standards of
  36 //   other proto2 unittests.
  37
  38 #include <algorithm>
  39 #include <limits>
  40 #include <list>
  41 #include <vector>
  42
  43 #include <google/protobuf/repeated_field.h>
  44
  45 #include <google/protobuf/stubs/common.h>
  46 #include <google/protobuf/unittest.pb.h>
  47 #include <google/protobuf/stubs/strutil.h>
  48 #include <google/protobuf/testing/googletest.h>
  49 #include <gtest/gtest.h>
  50 #include <google/protobuf/stubs/stl_util.h>
  51
  52 namespace google {
  53 using protobuf_unittest::TestAllTypes;
  54
  55 namespace protobuf {
  56 namespace {
  57
  58 // Test operations on a small RepeatedField.
  59 TEST(RepeatedField, Small) {
  60   RepeatedField<int> field;
  61
  62   EXPECT_TRUE(field.empty());
  63   EXPECT_EQ(field.size(), 0);
  64
  65   field.Add(5);
  66
  67   EXPECT_FALSE(field.empty());
  68   EXPECT_EQ(field.size(), 1);
  69   EXPECT_EQ(field.Get(0), 5);
  70
  71   field.Add(42);
  72
  73   EXPECT_FALSE(field.empty());
  74   EXPECT_EQ(field.size(), 2);
  75   EXPECT_EQ(field.Get(0), 5);
  76   EXPECT_EQ(field.Get(1), 42);
  77
  78   field.Set(1, 23);
  79
  80   EXPECT_FALSE(field.empty());
  81   EXPECT_EQ(field.size(), 2);
  82   EXPECT_EQ(field.Get(0), 5);
  83   EXPECT_EQ(field.Get(1), 23);
  84
  85   field.RemoveLast();
  86
  87   EXPECT_FALSE(field.empty());
  88   EXPECT_EQ(field.size(), 1);
  89   EXPECT_EQ(field.Get(0), 5);
  90
  91   field.Clear();
  92
  93   EXPECT_TRUE(field.empty());
  94   EXPECT_EQ(field.size(), 0);
  95   int expected_usage = 4 * sizeof(int);
  96   EXPECT_EQ(field.SpaceUsedExcludingSelf(), expected_usage);
  97 }
  98
  99
 100 // Test operations on a RepeatedField which is large enough to allocate a
 101 // separate array.
 102 TEST(RepeatedField, Large) {
 103   RepeatedField<int> field;
 104
 105   for (int i = 0; i < 16; i++) {
 106     field.Add(i * i);
 107   }
 108
 109   EXPECT_FALSE(field.empty());
 110   EXPECT_EQ(field.size(), 16);
 111
 112   for (int i = 0; i < 16; i++) {
 113     EXPECT_EQ(field.Get(i), i * i);
 114   }
 115
 116   int expected_usage = 16 * sizeof(int);
 117   EXPECT_GE(field.SpaceUsedExcludingSelf(), expected_usage);
 118 }
 119
 120 // Test swapping between various types of RepeatedFields.
 121 TEST(RepeatedField, SwapSmallSmall) {
 122   RepeatedField<int> field1;
 123   RepeatedField<int> field2;
 124
 125   field1.Add(5);
 126   field1.Add(42);
 127
 128   EXPECT_FALSE(field1.empty());
 129   EXPECT_EQ(field1.size(), 2);
 130   EXPECT_EQ(field1.Get(0), 5);
 131   EXPECT_EQ(field1.Get(1), 42);
 132
 133   EXPECT_TRUE(field2.empty());
 134   EXPECT_EQ(field2.size(), 0);
 135
 136   field1.Swap(&field2);
 137
 138   EXPECT_TRUE(field1.empty());
 139   EXPECT_EQ(field1.size(), 0);
 140
 141   EXPECT_FALSE(field2.empty());
 142   EXPECT_EQ(field2.size(), 2);
 143   EXPECT_EQ(field2.Get(0), 5);
 144   EXPECT_EQ(field2.Get(1), 42);
 145 }
 146
 147 TEST(RepeatedField, SwapLargeSmall) {
 148   RepeatedField<int> field1;
 149   RepeatedField<int> field2;
 150
 151   for (int i = 0; i < 16; i++) {
 152     field1.Add(i * i);
 153   }
 154   field2.Add(5);
 155   field2.Add(42);
 156   field1.Swap(&field2);
 157
 158   EXPECT_EQ(field1.size(), 2);
 159   EXPECT_EQ(field1.Get(0), 5);
 160   EXPECT_EQ(field1.Get(1), 42);
 161   EXPECT_EQ(field2.size(), 16);
 162   for (int i = 0; i < 16; i++) {
 163     EXPECT_EQ(field2.Get(i), i * i);
 164   }
 165 }
 166
 167 TEST(RepeatedField, SwapLargeLarge) {
 168   RepeatedField<int> field1;
 169   RepeatedField<int> field2;
 170
 171   field1.Add(5);
 172   field1.Add(42);
 173   for (int i = 0; i < 16; i++) {
 174     field1.Add(i);
 175     field2.Add(i * i);
 176   }
 177   field2.Swap(&field1);
 178
 179   EXPECT_EQ(field1.size(), 16);
 180   for (int i = 0; i < 16; i++) {
 181     EXPECT_EQ(field1.Get(i), i * i);
 182   }
 183   EXPECT_EQ(field2.size(), 18);
 184   EXPECT_EQ(field2.Get(0), 5);
 185   EXPECT_EQ(field2.Get(1), 42);
 186   for (int i = 2; i < 18; i++) {
 187     EXPECT_EQ(field2.Get(i), i - 2);
 188   }
 189 }
 190
 191 // Determines how much space was reserved by the given field by adding elements
 192 // to it until it re-allocates its space.
 193 static int ReservedSpace(RepeatedField<int>* field) {
 194   const int* ptr = field->data();
 195   do {
 196     field->Add(0);
 197   } while (field->data() == ptr);
 198
 199   return field->size() - 1;
 200 }
 201
 202 TEST(RepeatedField, ReserveMoreThanDouble) {
 203   // Reserve more than double the previous space in the field and expect the
 204   // field to reserve exactly the amount specified.
 205   RepeatedField<int> field;
 206   field.Reserve(20);
 207
 208   EXPECT_EQ(20, ReservedSpace(&field));
 209 }
 210
 211 TEST(RepeatedField, ReserveLessThanDouble) {
 212   // Reserve less than double the previous space in the field and expect the
 213   // field to grow by double instead.
 214   RepeatedField<int> field;
 215   field.Reserve(20);
 216   field.Reserve(30);
 217
 218   EXPECT_EQ(40, ReservedSpace(&field));
 219 }
 220
 221 TEST(RepeatedField, ReserveLessThanExisting) {
 222   // Reserve less than the previous space in the field and expect the
 223   // field to not re-allocate at all.
 224   RepeatedField<int> field;
 225   field.Reserve(20);
 226   const int* previous_ptr = field.data();
 227   field.Reserve(10);
 228
 229   EXPECT_EQ(previous_ptr, field.data());
 230   EXPECT_EQ(20, ReservedSpace(&field));
 231 }
 232
 233 TEST(RepeatedField, Resize) {
 234   RepeatedField<int> field;
 235   field.Resize(2, 1);
 236   EXPECT_EQ(2, field.size());
 237   field.Resize(5, 2);
 238   EXPECT_EQ(5, field.size());
 239   field.Resize(4, 3);
 240   ASSERT_EQ(4, field.size());
 241   EXPECT_EQ(1, field.Get(0));
 242   EXPECT_EQ(1, field.Get(1));
 243   EXPECT_EQ(2, field.Get(2));
 244   EXPECT_EQ(2, field.Get(3));
 245   field.Resize(0, 4);
 246   EXPECT_TRUE(field.empty());
 247 }
 248
 249 TEST(RepeatedField, MergeFrom) {
 250   RepeatedField<int> source, destination;
 251   source.Add(4);
 252   source.Add(5);
 253   destination.Add(1);
 254   destination.Add(2);
 255   destination.Add(3);
 256
 257   destination.MergeFrom(source);
 258
 259   ASSERT_EQ(5, destination.size());
 260   EXPECT_EQ(1, destination.Get(0));
 261   EXPECT_EQ(2, destination.Get(1));
 262   EXPECT_EQ(3, destination.Get(2));
 263   EXPECT_EQ(4, destination.Get(3));
 264   EXPECT_EQ(5, destination.Get(4));
 265 }
 266
 267 #ifdef PROTOBUF_HAS_DEATH_TEST
 268 TEST(RepeatedField, MergeFromSelf) {
 269   RepeatedField<int> me;
 270   me.Add(3);
 271   EXPECT_DEATH(me.MergeFrom(me), "");
 272 }
 273 #endif  // PROTOBUF_HAS_DEATH_TEST
 274
 275 TEST(RepeatedField, CopyFrom) {
 276   RepeatedField<int> source, destination;
 277   source.Add(4);
 278   source.Add(5);
 279   destination.Add(1);
 280   destination.Add(2);
 281   destination.Add(3);
 282
 283   destination.CopyFrom(source);
 284
 285   ASSERT_EQ(2, destination.size());
 286   EXPECT_EQ(4, destination.Get(0));
 287   EXPECT_EQ(5, destination.Get(1));
 288 }
 289
 290 TEST(RepeatedField, CopyFromSelf) {
 291   RepeatedField<int> me;
 292   me.Add(3);
 293   me.CopyFrom(me);
 294   ASSERT_EQ(1, me.size());
 295   EXPECT_EQ(3, me.Get(0));
 296 }
 297
 298 TEST(RepeatedField, CopyConstruct) {
 299   RepeatedField<int> source;
 300   source.Add(1);
 301   source.Add(2);
 302
 303   RepeatedField<int> destination(source);
 304
 305   ASSERT_EQ(2, destination.size());
 306   EXPECT_EQ(1, destination.Get(0));
 307   EXPECT_EQ(2, destination.Get(1));
 308 }
 309
 310 TEST(RepeatedField, IteratorConstruct) {
 311   vector<int> values;
 312   values.push_back(1);
 313   values.push_back(2);
 314
 315   RepeatedField<int> field(values.begin(), values.end());
 316   ASSERT_EQ(values.size(), field.size());
 317   EXPECT_EQ(values[0], field.Get(0));
 318   EXPECT_EQ(values[1], field.Get(1));
 319
 320   RepeatedField<int> other(field.begin(), field.end());
 321   ASSERT_EQ(values.size(), other.size());
 322   EXPECT_EQ(values[0], other.Get(0));
 323   EXPECT_EQ(values[1], other.Get(1));
 324 }
 325
 326 TEST(RepeatedField, CopyAssign) {
 327   RepeatedField<int> source, destination;
 328   source.Add(4);
 329   source.Add(5);
 330   destination.Add(1);
 331   destination.Add(2);
 332   destination.Add(3);
 333
 334   destination = source;
 335
 336   ASSERT_EQ(2, destination.size());
 337   EXPECT_EQ(4, destination.Get(0));
 338   EXPECT_EQ(5, destination.Get(1));
 339 }
 340
 341 TEST(RepeatedField, SelfAssign) {
 342   // Verify that assignment to self does not destroy data.
 343   RepeatedField<int> source, *p;
 344   p = &source;
 345   source.Add(7);
 346   source.Add(8);
 347
 348   *p = source;
 349
 350   ASSERT_EQ(2, source.size());
 351   EXPECT_EQ(7, source.Get(0));
 352   EXPECT_EQ(8, source.Get(1));
 353 }
 354
 355 TEST(RepeatedField, MutableDataIsMutable) {
 356   RepeatedField<int> field;
 357   field.Add(1);
 358   EXPECT_EQ(1, field.Get(0));
 359   // The fact that this line compiles would be enough, but we'll check the
 360   // value anyway.
 361   *field.mutable_data() = 2;
 362   EXPECT_EQ(2, field.Get(0));
 363 }
 364
 365 TEST(RepeatedField, Truncate) {
 366   RepeatedField<int> field;
 367
 368   field.Add(12);
 369   field.Add(34);
 370   field.Add(56);
 371   field.Add(78);
 372   EXPECT_EQ(4, field.size());
 373
 374   field.Truncate(3);
 375   EXPECT_EQ(3, field.size());
 376
 377   field.Add(90);
 378   EXPECT_EQ(4, field.size());
 379   EXPECT_EQ(90, field.Get(3));
 380
 381   // Truncations that don't change the size are allowed, but growing is not
 382   // allowed.
 383   field.Truncate(field.size());
 384 #ifdef PROTOBUF_HAS_DEATH_TEST
 385   EXPECT_DEBUG_DEATH(field.Truncate(field.size() + 1), "new_size");
 386 #endif
 387 }
 388
 389
 390 TEST(RepeatedField, ExtractSubrange) {
 391   // Exhaustively test every subrange in arrays of all sizes from 0 through 9.
 392   for (int sz = 0; sz < 10; ++sz) {
 393     for (int num = 0; num <= sz; ++num) {
 394       for (int start = 0; start < sz - num; ++start) {
 395         // Create RepeatedField with sz elements having values 0 through sz-1.
 396         RepeatedField<int32> field;
 397         for (int i = 0; i < sz; ++i)
 398           field.Add(i);
 399         EXPECT_EQ(field.size(), sz);
 400
 401         // Create a catcher array and call ExtractSubrange.
 402         int32 catcher[10];
 403         for (int i = 0; i < 10; ++i)
 404           catcher[i] = -1;
 405         field.ExtractSubrange(start, num, catcher);
 406
 407         // Does the resulting array have the right size?
 408         EXPECT_EQ(field.size(), sz - num);
 409
 410         // Were the removed elements extracted into the catcher array?
 411         for (int i = 0; i < num; ++i)
 412           EXPECT_EQ(catcher[i], start + i);
 413         EXPECT_EQ(catcher[num], -1);
 414
 415         // Does the resulting array contain the right values?
 416         for (int i = 0; i < start; ++i)
 417           EXPECT_EQ(field.Get(i), i);
 418         for (int i = start; i < field.size(); ++i)
 419           EXPECT_EQ(field.Get(i), i + num);
 420       }
 421     }
 422   }
 423 }
 424
 425 // ===================================================================
 426 // RepeatedPtrField tests.  These pretty much just mirror the RepeatedField
 427 // tests above.
 428
 429 TEST(RepeatedPtrField, Small) {
 430   RepeatedPtrField<string> field;
 431
 432   EXPECT_TRUE(field.empty());
 433   EXPECT_EQ(field.size(), 0);
 434
 435   field.Add()->assign("foo");
 436
 437   EXPECT_FALSE(field.empty());
 438   EXPECT_EQ(field.size(), 1);
 439   EXPECT_EQ(field.Get(0), "foo");
 440
 441   field.Add()->assign("bar");
 442
 443   EXPECT_FALSE(field.empty());
 444   EXPECT_EQ(field.size(), 2);
 445   EXPECT_EQ(field.Get(0), "foo");
 446   EXPECT_EQ(field.Get(1), "bar");
 447
 448   field.Mutable(1)->assign("baz");
 449
 450   EXPECT_FALSE(field.empty());
 451   EXPECT_EQ(field.size(), 2);
 452   EXPECT_EQ(field.Get(0), "foo");
 453   EXPECT_EQ(field.Get(1), "baz");
 454
 455   field.RemoveLast();
 456
 457   EXPECT_FALSE(field.empty());
 458   EXPECT_EQ(field.size(), 1);
 459   EXPECT_EQ(field.Get(0), "foo");
 460
 461   field.Clear();
 462
 463   EXPECT_TRUE(field.empty());
 464   EXPECT_EQ(field.size(), 0);
 465 }
 466
 467 TEST(RepeatedPtrField, Large) {
 468   RepeatedPtrField<string> field;
 469
 470   for (int i = 0; i < 16; i++) {
 471     *field.Add() += 'a' + i;
 472   }
 473
 474   EXPECT_EQ(field.size(), 16);
 475
 476   for (int i = 0; i < 16; i++) {
 477     EXPECT_EQ(field.Get(i).size(), 1);
 478     EXPECT_EQ(field.Get(i)[0], 'a' + i);
 479   }
 480
 481   int min_expected_usage = 16 * sizeof(string);
 482   EXPECT_GE(field.SpaceUsedExcludingSelf(), min_expected_usage);
 483 }
 484
 485 TEST(RepeatedPtrField, SwapSmallSmall) {
 486   RepeatedPtrField<string> field1;
 487   RepeatedPtrField<string> field2;
 488
 489   EXPECT_TRUE(field1.empty());
 490   EXPECT_EQ(field1.size(), 0);
 491   EXPECT_TRUE(field2.empty());
 492   EXPECT_EQ(field2.size(), 0);
 493
 494   field1.Add()->assign("foo");
 495   field1.Add()->assign("bar");
 496
 497   EXPECT_FALSE(field1.empty());
 498   EXPECT_EQ(field1.size(), 2);
 499   EXPECT_EQ(field1.Get(0), "foo");
 500   EXPECT_EQ(field1.Get(1), "bar");
 501
 502   EXPECT_TRUE(field2.empty());
 503   EXPECT_EQ(field2.size(), 0);
 504
 505   field1.Swap(&field2);
 506
 507   EXPECT_TRUE(field1.empty());
 508   EXPECT_EQ(field1.size(), 0);
 509
 510   EXPECT_EQ(field2.size(), 2);
 511   EXPECT_EQ(field2.Get(0), "foo");
 512   EXPECT_EQ(field2.Get(1), "bar");
 513 }
 514
 515 TEST(RepeatedPtrField, SwapLargeSmall) {
 516   RepeatedPtrField<string> field1;
 517   RepeatedPtrField<string> field2;
 518
 519   field2.Add()->assign("foo");
 520   field2.Add()->assign("bar");
 521   for (int i = 0; i < 16; i++) {
 522     *field1.Add() += 'a' + i;
 523   }
 524   field1.Swap(&field2);
 525
 526   EXPECT_EQ(field1.size(), 2);
 527   EXPECT_EQ(field1.Get(0), "foo");
 528   EXPECT_EQ(field1.Get(1), "bar");
 529   EXPECT_EQ(field2.size(), 16);
 530   for (int i = 0; i < 16; i++) {
 531     EXPECT_EQ(field2.Get(i).size(), 1);
 532     EXPECT_EQ(field2.Get(i)[0], 'a' + i);
 533   }
 534 }
 535
 536 TEST(RepeatedPtrField, SwapLargeLarge) {
 537   RepeatedPtrField<string> field1;
 538   RepeatedPtrField<string> field2;
 539
 540   field1.Add()->assign("foo");
 541   field1.Add()->assign("bar");
 542   for (int i = 0; i < 16; i++) {
 543     *field1.Add() += 'A' + i;
 544     *field2.Add() += 'a' + i;
 545   }
 546   field2.Swap(&field1);
 547
 548   EXPECT_EQ(field1.size(), 16);
 549   for (int i = 0; i < 16; i++) {
 550     EXPECT_EQ(field1.Get(i).size(), 1);
 551     EXPECT_EQ(field1.Get(i)[0], 'a' + i);
 552   }
 553   EXPECT_EQ(field2.size(), 18);
 554   EXPECT_EQ(field2.Get(0), "foo");
 555   EXPECT_EQ(field2.Get(1), "bar");
 556   for (int i = 2; i < 18; i++) {
 557     EXPECT_EQ(field2.Get(i).size(), 1);
 558     EXPECT_EQ(field2.Get(i)[0], 'A' + i - 2);
 559   }
 560 }
 561
 562 static int ReservedSpace(RepeatedPtrField<string>* field) {
 563   const string* const* ptr = field->data();
 564   do {
 565     field->Add();
 566   } while (field->data() == ptr);
 567
 568   return field->size() - 1;
 569 }
 570
 571 TEST(RepeatedPtrField, ReserveMoreThanDouble) {
 572   RepeatedPtrField<string> field;
 573   field.Reserve(20);
 574
 575   EXPECT_EQ(20, ReservedSpace(&field));
 576 }
 577
 578 TEST(RepeatedPtrField, ReserveLessThanDouble) {
 579   RepeatedPtrField<string> field;
 580   field.Reserve(20);
 581   field.Reserve(30);
 582
 583   EXPECT_EQ(40, ReservedSpace(&field));
 584 }
 585
 586 TEST(RepeatedPtrField, ReserveLessThanExisting) {
 587   RepeatedPtrField<string> field;
 588   field.Reserve(20);
 589   const string* const* previous_ptr = field.data();
 590   field.Reserve(10);
 591
 592   EXPECT_EQ(previous_ptr, field.data());
 593   EXPECT_EQ(20, ReservedSpace(&field));
 594 }
 595
 596 TEST(RepeatedPtrField, ReserveDoesntLoseAllocated) {
 597   // Check that a bug is fixed:  An earlier implementation of Reserve()
 598   // failed to copy pointers to allocated-but-cleared objects, possibly
 599   // leading to segfaults.
 600   RepeatedPtrField<string> field;
 601   string* first = field.Add();
 602   field.RemoveLast();
 603
 604   field.Reserve(20);
 605   EXPECT_EQ(first, field.Add());
 606 }
 607
 608 // Clearing elements is tricky with RepeatedPtrFields since the memory for
 609 // the elements is retained and reused.
 610 TEST(RepeatedPtrField, ClearedElements) {
 611   RepeatedPtrField<string> field;
 612
 613   string* original = field.Add();
 614   *original = "foo";
 615
 616   EXPECT_EQ(field.ClearedCount(), 0);
 617
 618   field.RemoveLast();
 619   EXPECT_TRUE(original->empty());
 620   EXPECT_EQ(field.ClearedCount(), 1);
 621
 622   EXPECT_EQ(field.Add(), original);  // Should return same string for reuse.
 623
 624   EXPECT_EQ(field.ReleaseLast(), original);  // We take ownership.
 625   EXPECT_EQ(field.ClearedCount(), 0);
 626
 627   EXPECT_NE(field.Add(), original);  // Should NOT return the same string.
 628   EXPECT_EQ(field.ClearedCount(), 0);
 629
 630   field.AddAllocated(original);  // Give ownership back.
 631   EXPECT_EQ(field.ClearedCount(), 0);
 632   EXPECT_EQ(field.Mutable(1), original);
 633
 634   field.Clear();
 635   EXPECT_EQ(field.ClearedCount(), 2);
 636   EXPECT_EQ(field.ReleaseCleared(), original);  // Take ownership again.
 637   EXPECT_EQ(field.ClearedCount(), 1);
 638   EXPECT_NE(field.Add(), original);
 639   EXPECT_EQ(field.ClearedCount(), 0);
 640   EXPECT_NE(field.Add(), original);
 641   EXPECT_EQ(field.ClearedCount(), 0);
 642
 643   field.AddCleared(original);  // Give ownership back, but as a cleared object.
 644   EXPECT_EQ(field.ClearedCount(), 1);
 645   EXPECT_EQ(field.Add(), original);
 646   EXPECT_EQ(field.ClearedCount(), 0);
 647 }
 648
 649 // Test all code paths in AddAllocated().
 650 TEST(RepeatedPtrField, AddAlocated) {
 651   RepeatedPtrField<string> field;
 652   while (field.size() < field.Capacity()) {
 653     field.Add()->assign("filler");
 654   }
 655
 656   int index = field.size();
 657
 658   // First branch:  Field is at capacity with no cleared objects.
 659   string* foo = new string("foo");
 660   field.AddAllocated(foo);
 661   EXPECT_EQ(index + 1, field.size());
 662   EXPECT_EQ(0, field.ClearedCount());
 663   EXPECT_EQ(foo, &field.Get(index));
 664
 665   // Last branch:  Field is not at capacity and there are no cleared objects.
 666   string* bar = new string("bar");
 667   field.AddAllocated(bar);
 668   ++index;
 669   EXPECT_EQ(index + 1, field.size());
 670   EXPECT_EQ(0, field.ClearedCount());
 671   EXPECT_EQ(bar, &field.Get(index));
 672
 673   // Third branch:  Field is not at capacity and there are no cleared objects.
 674   field.RemoveLast();
 675   string* baz = new string("baz");
 676   field.AddAllocated(baz);
 677   EXPECT_EQ(index + 1, field.size());
 678   EXPECT_EQ(1, field.ClearedCount());
 679   EXPECT_EQ(baz, &field.Get(index));
 680
 681   // Second branch:  Field is at capacity but has some cleared objects.
 682   while (field.size() < field.Capacity()) {
 683     field.Add()->assign("filler2");
 684   }
 685   field.RemoveLast();
 686   index = field.size();
 687   string* qux = new string("qux");
 688   field.AddAllocated(qux);
 689   EXPECT_EQ(index + 1, field.size());
 690   // We should have discarded the cleared object.
 691   EXPECT_EQ(0, field.ClearedCount());
 692   EXPECT_EQ(qux, &field.Get(index));
 693 }
 694
 695 TEST(RepeatedPtrField, MergeFrom) {
 696   RepeatedPtrField<string> source, destination;
 697   source.Add()->assign("4");
 698   source.Add()->assign("5");
 699   destination.Add()->assign("1");
 700   destination.Add()->assign("2");
 701   destination.Add()->assign("3");
 702
 703   destination.MergeFrom(source);
 704
 705   ASSERT_EQ(5, destination.size());
 706   EXPECT_EQ("1", destination.Get(0));
 707   EXPECT_EQ("2", destination.Get(1));
 708   EXPECT_EQ("3", destination.Get(2));
 709   EXPECT_EQ("4", destination.Get(3));
 710   EXPECT_EQ("5", destination.Get(4));
 711 }
 712
 713 #ifdef PROTOBUF_HAS_DEATH_TEST
 714 TEST(RepeatedPtrField, MergeFromSelf) {
 715   RepeatedPtrField<string> me;
 716   me.Add()->assign("1");
 717   EXPECT_DEATH(me.MergeFrom(me), "");
 718 }
 719 #endif  // PROTOBUF_HAS_DEATH_TEST
 720
 721 TEST(RepeatedPtrField, CopyFrom) {
 722   RepeatedPtrField<string> source, destination;
 723   source.Add()->assign("4");
 724   source.Add()->assign("5");
 725   destination.Add()->assign("1");
 726   destination.Add()->assign("2");
 727   destination.Add()->assign("3");
 728
 729   destination.CopyFrom(source);
 730
 731   ASSERT_EQ(2, destination.size());
 732   EXPECT_EQ("4", destination.Get(0));
 733   EXPECT_EQ("5", destination.Get(1));
 734 }
 735
 736 TEST(RepeatedPtrField, CopyFromSelf) {
 737   RepeatedPtrField<string> me;
 738   me.Add()->assign("1");
 739   me.CopyFrom(me);
 740   ASSERT_EQ(1, me.size());
 741   EXPECT_EQ("1", me.Get(0));
 742 }
 743
 744 TEST(RepeatedPtrField, CopyConstruct) {
 745   RepeatedPtrField<string> source;
 746   source.Add()->assign("1");
 747   source.Add()->assign("2");
 748
 749   RepeatedPtrField<string> destination(source);
 750
 751   ASSERT_EQ(2, destination.size());
 752   EXPECT_EQ("1", destination.Get(0));
 753   EXPECT_EQ("2", destination.Get(1));
 754 }
 755
 756 TEST(RepeatedPtrField, IteratorConstruct_String) {
 757   vector<string> values;
 758   values.push_back("1");
 759   values.push_back("2");
 760
 761   RepeatedPtrField<string> field(values.begin(), values.end());
 762   ASSERT_EQ(values.size(), field.size());
 763   EXPECT_EQ(values[0], field.Get(0));
 764   EXPECT_EQ(values[1], field.Get(1));
 765
 766   RepeatedPtrField<string> other(field.begin(), field.end());
 767   ASSERT_EQ(values.size(), other.size());
 768   EXPECT_EQ(values[0], other.Get(0));
 769   EXPECT_EQ(values[1], other.Get(1));
 770 }
 771
 772 TEST(RepeatedPtrField, IteratorConstruct_Proto) {
 773   typedef TestAllTypes::NestedMessage Nested;
 774   vector<Nested> values;
 775   values.push_back(Nested());
 776   values.back().set_bb(1);
 777   values.push_back(Nested());
 778   values.back().set_bb(2);
 779
 780   RepeatedPtrField<Nested> field(values.begin(), values.end());
 781   ASSERT_EQ(values.size(), field.size());
 782   EXPECT_EQ(values[0].bb(), field.Get(0).bb());
 783   EXPECT_EQ(values[1].bb(), field.Get(1).bb());
 784
 785   RepeatedPtrField<Nested> other(field.begin(), field.end());
 786   ASSERT_EQ(values.size(), other.size());
 787   EXPECT_EQ(values[0].bb(), other.Get(0).bb());
 788   EXPECT_EQ(values[1].bb(), other.Get(1).bb());
 789 }
 790
 791 TEST(RepeatedPtrField, CopyAssign) {
 792   RepeatedPtrField<string> source, destination;
 793   source.Add()->assign("4");
 794   source.Add()->assign("5");
 795   destination.Add()->assign("1");
 796   destination.Add()->assign("2");
 797   destination.Add()->assign("3");
 798
 799   destination = source;
 800
 801   ASSERT_EQ(2, destination.size());
 802   EXPECT_EQ("4", destination.Get(0));
 803   EXPECT_EQ("5", destination.Get(1));
 804 }
 805
 806 TEST(RepeatedPtrField, SelfAssign) {
 807   // Verify that assignment to self does not destroy data.
 808   RepeatedPtrField<string> source, *p;
 809   p = &source;
 810   source.Add()->assign("7");
 811   source.Add()->assign("8");
 812
 813   *p = source;
 814
 815   ASSERT_EQ(2, source.size());
 816   EXPECT_EQ("7", source.Get(0));
 817   EXPECT_EQ("8", source.Get(1));
 818 }
 819
 820 TEST(RepeatedPtrField, MutableDataIsMutable) {
 821   RepeatedPtrField<string> field;
 822   *field.Add() = "1";
 823   EXPECT_EQ("1", field.Get(0));
 824   // The fact that this line compiles would be enough, but we'll check the
 825   // value anyway.
 826   string** data = field.mutable_data();
 827   **data = "2";
 828   EXPECT_EQ("2", field.Get(0));
 829 }
 830
 831 TEST(RepeatedPtrField, ExtractSubrange) {
 832   // Exhaustively test every subrange in arrays of all sizes from 0 through 9
 833   // with 0 through 3 cleared elements at the end.
 834   for (int sz = 0; sz < 10; ++sz) {
 835     for (int num = 0; num <= sz; ++num) {
 836       for (int start = 0; start < sz - num; ++start) {
 837         for (int extra = 0; extra < 4; ++extra) {
 838           vector<string*> subject;
 839
 840           // Create an array with "sz" elements and "extra" cleared elements.
 841           RepeatedPtrField<string> field;
 842           for (int i = 0; i < sz + extra; ++i) {
 843             subject.push_back(new string());
 844             field.AddAllocated(subject[i]);
 845           }
 846           EXPECT_EQ(field.size(), sz + extra);
 847           for (int i = 0; i < extra; ++i)
 848             field.RemoveLast();
 849           EXPECT_EQ(field.size(), sz);
 850           EXPECT_EQ(field.ClearedCount(), extra);
 851
 852           // Create a catcher array and call ExtractSubrange.
 853           string* catcher[10];
 854           for (int i = 0; i < 10; ++i)
 855             catcher[i] = NULL;
 856           field.ExtractSubrange(start, num, catcher);
 857
 858           // Does the resulting array have the right size?
 859           EXPECT_EQ(field.size(), sz - num);
 860
 861           // Were the removed elements extracted into the catcher array?
 862           for (int i = 0; i < num; ++i)
 863             EXPECT_EQ(catcher[i], subject[start + i]);
 864           EXPECT_EQ(NULL, catcher[num]);
 865
 866           // Does the resulting array contain the right values?
 867           for (int i = 0; i < start; ++i)
 868             EXPECT_EQ(field.Mutable(i), subject[i]);
 869           for (int i = start; i < field.size(); ++i)
 870             EXPECT_EQ(field.Mutable(i), subject[i + num]);
 871
 872           // Reinstate the cleared elements.
 873           EXPECT_EQ(field.ClearedCount(), extra);
 874           for (int i = 0; i < extra; ++i)
 875             field.Add();
 876           EXPECT_EQ(field.ClearedCount(), 0);
 877           EXPECT_EQ(field.size(), sz - num + extra);
 878
 879           // Make sure the extra elements are all there (in some order).
 880           for (int i = sz; i < sz + extra; ++i) {
 881             int count = 0;
 882             for (int j = sz; j < sz + extra; ++j) {
 883               if (field.Mutable(j - num) == subject[i])
 884                 count += 1;
 885             }
 886             EXPECT_EQ(count, 1);
 887           }
 888
 889           // Release the caught elements.
 890           for (int i = 0; i < num; ++i)
 891             delete catcher[i];
 892         }
 893       }
 894     }
 895   }
 896 }
 897
 898 TEST(RepeatedPtrField, DeleteSubrange) {
 899   // DeleteSubrange is a trivial extension of ExtendSubrange.
 900 }
 901
 902 // ===================================================================
 903
 904 // Iterator tests stolen from net/proto/proto-array_unittest.
 905 class RepeatedFieldIteratorTest : public testing::Test {
 906  protected:
 907   virtual void SetUp() {
 908     for (int i = 0; i < 3; ++i) {
 909       proto_array_.Add(i);
 910     }
 911   }
 912
 913   RepeatedField<int> proto_array_;
 914 };
 915
 916 TEST_F(RepeatedFieldIteratorTest, Convertible) {
 917   RepeatedField<int>::iterator iter = proto_array_.begin();
 918   RepeatedField<int>::const_iterator c_iter = iter;
 919   RepeatedField<int>::value_type value = *c_iter;
 920   EXPECT_EQ(0, value);
 921 }
 922
 923 TEST_F(RepeatedFieldIteratorTest, MutableIteration) {
 924   RepeatedField<int>::iterator iter = proto_array_.begin();
 925   EXPECT_EQ(0, *iter);
 926   ++iter;
 927   EXPECT_EQ(1, *iter++);
 928   EXPECT_EQ(2, *iter);
 929   ++iter;
 930   EXPECT_TRUE(proto_array_.end() == iter);
 931
 932   EXPECT_EQ(2, *(proto_array_.end() - 1));
 933 }
 934
 935 TEST_F(RepeatedFieldIteratorTest, ConstIteration) {
 936   const RepeatedField<int>& const_proto_array = proto_array_;
 937   RepeatedField<int>::const_iterator iter = const_proto_array.begin();
 938   EXPECT_EQ(0, *iter);
 939   ++iter;
 940   EXPECT_EQ(1, *iter++);
 941   EXPECT_EQ(2, *iter);
 942   ++iter;
 943   EXPECT_TRUE(proto_array_.end() == iter);
 944   EXPECT_EQ(2, *(proto_array_.end() - 1));
 945 }
 946
 947 TEST_F(RepeatedFieldIteratorTest, Mutation) {
 948   RepeatedField<int>::iterator iter = proto_array_.begin();
 949   *iter = 7;
 950   EXPECT_EQ(7, proto_array_.Get(0));
 951 }
 952
 953 // -------------------------------------------------------------------
 954
 955 class RepeatedPtrFieldIteratorTest : public testing::Test {
 956  protected:
 957   virtual void SetUp() {
 958     proto_array_.Add()->assign("foo");
 959     proto_array_.Add()->assign("bar");
 960     proto_array_.Add()->assign("baz");
 961   }
 962
 963   RepeatedPtrField<string> proto_array_;
 964 };
 965
 966 TEST_F(RepeatedPtrFieldIteratorTest, Convertible) {
 967   RepeatedPtrField<string>::iterator iter = proto_array_.begin();
 968   RepeatedPtrField<string>::const_iterator c_iter = iter;
 969   RepeatedPtrField<string>::value_type value = *c_iter;
 970   EXPECT_EQ("foo", value);
 971 }
 972
 973 TEST_F(RepeatedPtrFieldIteratorTest, MutableIteration) {
 974   RepeatedPtrField<string>::iterator iter = proto_array_.begin();
 975   EXPECT_EQ("foo", *iter);
 976   ++iter;
 977   EXPECT_EQ("bar", *(iter++));
 978   EXPECT_EQ("baz", *iter);
 979   ++iter;
 980   EXPECT_TRUE(proto_array_.end() == iter);
 981   EXPECT_EQ("baz", *(--proto_array_.end()));
 982 }
 983
 984 TEST_F(RepeatedPtrFieldIteratorTest, ConstIteration) {
 985   const RepeatedPtrField<string>& const_proto_array = proto_array_;
 986   RepeatedPtrField<string>::const_iterator iter = const_proto_array.begin();
 987   EXPECT_EQ("foo", *iter);
 988   ++iter;
 989   EXPECT_EQ("bar", *(iter++));
 990   EXPECT_EQ("baz", *iter);
 991   ++iter;
 992   EXPECT_TRUE(const_proto_array.end() == iter);
 993   EXPECT_EQ("baz", *(--const_proto_array.end()));
 994 }
 995
 996 TEST_F(RepeatedPtrFieldIteratorTest, MutableReverseIteration) {
 997   RepeatedPtrField<string>::reverse_iterator iter = proto_array_.rbegin();
 998   EXPECT_EQ("baz", *iter);
 999   ++iter;
1000   EXPECT_EQ("bar", *(iter++));
1001   EXPECT_EQ("foo", *iter);
1002   ++iter;
1003   EXPECT_TRUE(proto_array_.rend() == iter);
1004   EXPECT_EQ("foo", *(--proto_array_.rend()));
1005 }
1006
1007 TEST_F(RepeatedPtrFieldIteratorTest, ConstReverseIteration) {
1008   const RepeatedPtrField<string>& const_proto_array = proto_array_;
1009   RepeatedPtrField<string>::const_reverse_iterator iter
1010       = const_proto_array.rbegin();
1011   EXPECT_EQ("baz", *iter);
1012   ++iter;
1013   EXPECT_EQ("bar", *(iter++));
1014   EXPECT_EQ("foo", *iter);
1015   ++iter;
1016   EXPECT_TRUE(const_proto_array.rend() == iter);
1017   EXPECT_EQ("foo", *(--const_proto_array.rend()));
1018 }
1019
1020 TEST_F(RepeatedPtrFieldIteratorTest, RandomAccess) {
1021   RepeatedPtrField<string>::iterator iter = proto_array_.begin();
1022   RepeatedPtrField<string>::iterator iter2 = iter;
1023   ++iter2;
1024   ++iter2;
1025   EXPECT_TRUE(iter + 2 == iter2);
1026   EXPECT_TRUE(iter == iter2 - 2);
1027   EXPECT_EQ("baz", iter[2]);
1028   EXPECT_EQ("baz", *(iter + 2));
1029   EXPECT_EQ(3, proto_array_.end() - proto_array_.begin());
1030 }
1031
1032 TEST_F(RepeatedPtrFieldIteratorTest, Comparable) {
1033   RepeatedPtrField<string>::const_iterator iter = proto_array_.begin();
1034   RepeatedPtrField<string>::const_iterator iter2 = iter + 1;
1035   EXPECT_TRUE(iter == iter);
1036   EXPECT_TRUE(iter != iter2);
1037   EXPECT_TRUE(iter < iter2);
1038   EXPECT_TRUE(iter <= iter2);
1039   EXPECT_TRUE(iter <= iter);
1040   EXPECT_TRUE(iter2 > iter);
1041   EXPECT_TRUE(iter2 >= iter);
1042   EXPECT_TRUE(iter >= iter);
1043 }
1044
1045 // Uninitialized iterator does not point to any of the RepeatedPtrField.
1046 TEST_F(RepeatedPtrFieldIteratorTest, UninitializedIterator) {
1047   RepeatedPtrField<string>::iterator iter;
1048   EXPECT_TRUE(iter != proto_array_.begin());
1049   EXPECT_TRUE(iter != proto_array_.begin() + 1);
1050   EXPECT_TRUE(iter != proto_array_.begin() + 2);
1051   EXPECT_TRUE(iter != proto_array_.begin() + 3);
1052   EXPECT_TRUE(iter != proto_array_.end());
1053 }
1054
1055 TEST_F(RepeatedPtrFieldIteratorTest, STLAlgorithms_lower_bound) {
1056   proto_array_.Clear();
1057   proto_array_.Add()->assign("a");
1058   proto_array_.Add()->assign("c");
1059   proto_array_.Add()->assign("d");
1060   proto_array_.Add()->assign("n");
1061   proto_array_.Add()->assign("p");
1062   proto_array_.Add()->assign("x");
1063   proto_array_.Add()->assign("y");
1064
1065   string v = "f";
1066   RepeatedPtrField<string>::const_iterator it =
1067       lower_bound(proto_array_.begin(), proto_array_.end(), v);
1068
1069   EXPECT_EQ(*it, "n");
1070   EXPECT_TRUE(it == proto_array_.begin() + 3);
1071 }
1072
1073 TEST_F(RepeatedPtrFieldIteratorTest, Mutation) {
1074   RepeatedPtrField<string>::iterator iter = proto_array_.begin();
1075   *iter = "qux";
1076   EXPECT_EQ("qux", proto_array_.Get(0));
1077 }
1078
1079 // -------------------------------------------------------------------
1080
1081 class RepeatedPtrFieldPtrsIteratorTest : public testing::Test {
1082  protected:
1083   virtual void SetUp() {
1084     proto_array_.Add()->assign("foo");
1085     proto_array_.Add()->assign("bar");
1086     proto_array_.Add()->assign("baz");
1087     const_proto_array_ = &proto_array_;
1088   }
1089
1090   RepeatedPtrField<string> proto_array_;
1091   const RepeatedPtrField<string>* const_proto_array_;
1092 };
1093
1094 TEST_F(RepeatedPtrFieldPtrsIteratorTest, ConvertiblePtr) {
1095   RepeatedPtrField<string>::pointer_iterator iter =
1096       proto_array_.pointer_begin();
1097   static_cast<void>(iter);
1098 }
1099
1100 TEST_F(RepeatedPtrFieldPtrsIteratorTest, ConvertibleConstPtr) {
1101   RepeatedPtrField<string>::const_pointer_iterator iter =
1102       const_proto_array_->pointer_begin();
1103   static_cast<void>(iter);
1104 }
1105
1106 TEST_F(RepeatedPtrFieldPtrsIteratorTest, MutablePtrIteration) {
1107   RepeatedPtrField<string>::pointer_iterator iter =
1108       proto_array_.pointer_begin();
1109   EXPECT_EQ("foo", **iter);
1110   ++iter;
1111   EXPECT_EQ("bar", **(iter++));
1112   EXPECT_EQ("baz", **iter);
1113   ++iter;
1114   EXPECT_TRUE(proto_array_.pointer_end() == iter);
1115   EXPECT_EQ("baz", **(--proto_array_.pointer_end()));
1116 }
1117
1118 TEST_F(RepeatedPtrFieldPtrsIteratorTest, MutableConstPtrIteration) {
1119   RepeatedPtrField<string>::const_pointer_iterator iter =
1120       const_proto_array_->pointer_begin();
1121   EXPECT_EQ("foo", **iter);
1122   ++iter;
1123   EXPECT_EQ("bar", **(iter++));
1124   EXPECT_EQ("baz", **iter);
1125   ++iter;
1126   EXPECT_TRUE(const_proto_array_->pointer_end() == iter);
1127   EXPECT_EQ("baz", **(--const_proto_array_->pointer_end()));
1128 }
1129
1130 TEST_F(RepeatedPtrFieldPtrsIteratorTest, RandomPtrAccess) {
1131   RepeatedPtrField<string>::pointer_iterator iter =
1132       proto_array_.pointer_begin();
1133   RepeatedPtrField<string>::pointer_iterator iter2 = iter;
1134   ++iter2;
1135   ++iter2;
1136   EXPECT_TRUE(iter + 2 == iter2);
1137   EXPECT_TRUE(iter == iter2 - 2);
1138   EXPECT_EQ("baz", *iter[2]);
1139   EXPECT_EQ("baz", **(iter + 2));
1140   EXPECT_EQ(3, proto_array_.end() - proto_array_.begin());
1141 }
1142
1143 TEST_F(RepeatedPtrFieldPtrsIteratorTest, RandomConstPtrAccess) {
1144   RepeatedPtrField<string>::const_pointer_iterator iter =
1145       const_proto_array_->pointer_begin();
1146   RepeatedPtrField<string>::const_pointer_iterator iter2 = iter;
1147   ++iter2;
1148   ++iter2;
1149   EXPECT_TRUE(iter + 2 == iter2);
1150   EXPECT_TRUE(iter == iter2 - 2);
1151   EXPECT_EQ("baz", *iter[2]);
1152   EXPECT_EQ("baz", **(iter + 2));
1153   EXPECT_EQ(3, const_proto_array_->end() - const_proto_array_->begin());
1154 }
1155
1156 TEST_F(RepeatedPtrFieldPtrsIteratorTest, ComparablePtr) {
1157   RepeatedPtrField<string>::pointer_iterator iter =
1158       proto_array_.pointer_begin();
1159   RepeatedPtrField<string>::pointer_iterator iter2 = iter + 1;
1160   EXPECT_TRUE(iter == iter);
1161   EXPECT_TRUE(iter != iter2);
1162   EXPECT_TRUE(iter < iter2);
1163   EXPECT_TRUE(iter <= iter2);
1164   EXPECT_TRUE(iter <= iter);
1165   EXPECT_TRUE(iter2 > iter);
1166   EXPECT_TRUE(iter2 >= iter);
1167   EXPECT_TRUE(iter >= iter);
1168 }
1169
1170 TEST_F(RepeatedPtrFieldPtrsIteratorTest, ComparableConstPtr) {
1171   RepeatedPtrField<string>::const_pointer_iterator iter =
1172       const_proto_array_->pointer_begin();
1173   RepeatedPtrField<string>::const_pointer_iterator iter2 = iter + 1;
1174   EXPECT_TRUE(iter == iter);
1175   EXPECT_TRUE(iter != iter2);
1176   EXPECT_TRUE(iter < iter2);
1177   EXPECT_TRUE(iter <= iter2);
1178   EXPECT_TRUE(iter <= iter);
1179   EXPECT_TRUE(iter2 > iter);
1180   EXPECT_TRUE(iter2 >= iter);
1181   EXPECT_TRUE(iter >= iter);
1182 }
1183
1184 // Uninitialized iterator does not point to any of the RepeatedPtrOverPtrs.
1185 // Dereferencing an uninitialized iterator crashes the process.
1186 TEST_F(RepeatedPtrFieldPtrsIteratorTest, UninitializedPtrIterator) {
1187   RepeatedPtrField<string>::pointer_iterator iter;
1188   EXPECT_TRUE(iter != proto_array_.pointer_begin());
1189   EXPECT_TRUE(iter != proto_array_.pointer_begin() + 1);
1190   EXPECT_TRUE(iter != proto_array_.pointer_begin() + 2);
1191   EXPECT_TRUE(iter != proto_array_.pointer_begin() + 3);
1192   EXPECT_TRUE(iter != proto_array_.pointer_end());
1193 }
1194
1195 TEST_F(RepeatedPtrFieldPtrsIteratorTest, UninitializedConstPtrIterator) {
1196   RepeatedPtrField<string>::const_pointer_iterator iter;
1197   EXPECT_TRUE(iter != const_proto_array_->pointer_begin());
1198   EXPECT_TRUE(iter != const_proto_array_->pointer_begin() + 1);
1199   EXPECT_TRUE(iter != const_proto_array_->pointer_begin() + 2);
1200   EXPECT_TRUE(iter != const_proto_array_->pointer_begin() + 3);
1201   EXPECT_TRUE(iter != const_proto_array_->pointer_end());
1202 }
1203
1204 // This comparison functor is required by the tests for RepeatedPtrOverPtrs.
1205 // They operate on strings and need to compare strings as strings in
1206 // any stl algorithm, even though the iterator returns a pointer to a string
1207 // - i.e. *iter has type string*.
1208 struct StringLessThan {
1209   bool operator()(const string* z, const string& y) {
1210     return *z < y;
1211   }
1212   bool operator()(const string* z, const string* y) const { return *z < *y; }
1213 };
1214
1215 TEST_F(RepeatedPtrFieldPtrsIteratorTest, PtrSTLAlgorithms_lower_bound) {
1216   proto_array_.Clear();
1217   proto_array_.Add()->assign("a");
1218   proto_array_.Add()->assign("c");
1219   proto_array_.Add()->assign("d");
1220   proto_array_.Add()->assign("n");
1221   proto_array_.Add()->assign("p");
1222   proto_array_.Add()->assign("x");
1223   proto_array_.Add()->assign("y");
1224
1225   {
1226     string v = "f";
1227     RepeatedPtrField<string>::pointer_iterator it =
1228         lower_bound(proto_array_.pointer_begin(), proto_array_.pointer_end(),
1229                     &v, StringLessThan());
1230
1231     GOOGLE_CHECK(*it != NULL);
1232
1233     EXPECT_EQ(**it, "n");
1234     EXPECT_TRUE(it == proto_array_.pointer_begin() + 3);
1235   }
1236   {
1237     string v = "f";
1238     RepeatedPtrField<string>::const_pointer_iterator it =
1239         lower_bound(const_proto_array_->pointer_begin(),
1240                     const_proto_array_->pointer_end(),
1241                     &v, StringLessThan());
1242
1243     GOOGLE_CHECK(*it != NULL);
1244
1245     EXPECT_EQ(**it, "n");
1246     EXPECT_TRUE(it == const_proto_array_->pointer_begin() + 3);
1247   }
1248 }
1249
1250 TEST_F(RepeatedPtrFieldPtrsIteratorTest, PtrMutation) {
1251   RepeatedPtrField<string>::pointer_iterator iter =
1252       proto_array_.pointer_begin();
1253   **iter = "qux";
1254   EXPECT_EQ("qux", proto_array_.Get(0));
1255
1256   EXPECT_EQ("bar", proto_array_.Get(1));
1257   EXPECT_EQ("baz", proto_array_.Get(2));
1258   ++iter;
1259   delete *iter;
1260   *iter = new string("a");
1261   ++iter;
1262   delete *iter;
1263   *iter = new string("b");
1264   EXPECT_EQ("a", proto_array_.Get(1));
1265   EXPECT_EQ("b", proto_array_.Get(2));
1266 }
1267
1268 TEST_F(RepeatedPtrFieldPtrsIteratorTest, Sort) {
1269   proto_array_.Add()->assign("c");
1270   proto_array_.Add()->assign("d");
1271   proto_array_.Add()->assign("n");
1272   proto_array_.Add()->assign("p");
1273   proto_array_.Add()->assign("a");
1274   proto_array_.Add()->assign("y");
1275   proto_array_.Add()->assign("x");
1276   EXPECT_EQ("foo", proto_array_.Get(0));
1277   EXPECT_EQ("n", proto_array_.Get(5));
1278   EXPECT_EQ("x", proto_array_.Get(9));
1279   sort(proto_array_.pointer_begin(),
1280        proto_array_.pointer_end(),
1281        StringLessThan());
1282   EXPECT_EQ("a", proto_array_.Get(0));
1283   EXPECT_EQ("baz", proto_array_.Get(2));
1284   EXPECT_EQ("y", proto_array_.Get(9));
1285 }
1286
1287
1288 // -----------------------------------------------------------------------------
1289 // Unit-tests for the insert iterators
1290 // google::protobuf::RepeatedFieldBackInserter,
1291 // google::protobuf::AllocatedRepeatedPtrFieldBackInserter
1292 // Ported from util/gtl/proto-array-iterators_unittest.
1293
1294 class RepeatedFieldInsertionIteratorsTest : public testing::Test {
1295  protected:
1296   std::list<double> halves;
1297   std::list<int> fibonacci;
1298   std::vector<string> words;
1299   typedef TestAllTypes::NestedMessage Nested;
1300   Nested nesteds[2];
1301   std::vector<Nested*> nested_ptrs;
1302   TestAllTypes protobuffer;
1303
1304   virtual void SetUp() {
1305     fibonacci.push_back(1);
1306     fibonacci.push_back(1);
1307     fibonacci.push_back(2);
1308     fibonacci.push_back(3);
1309     fibonacci.push_back(5);
1310     fibonacci.push_back(8);
1311     std::copy(fibonacci.begin(), fibonacci.end(),
1312               RepeatedFieldBackInserter(protobuffer.mutable_repeated_int32()));
1313
1314     halves.push_back(1.0);
1315     halves.push_back(0.5);
1316     halves.push_back(0.25);
1317     halves.push_back(0.125);
1318     halves.push_back(0.0625);
1319     std::copy(halves.begin(), halves.end(),
1320               RepeatedFieldBackInserter(protobuffer.mutable_repeated_double()));
1321
1322     words.push_back("Able");
1323     words.push_back("was");
1324     words.push_back("I");
1325     words.push_back("ere");
1326     words.push_back("I");
1327     words.push_back("saw");
1328     words.push_back("Elba");
1329     std::copy(words.begin(), words.end(),
1330               RepeatedFieldBackInserter(protobuffer.mutable_repeated_string()));
1331
1332     nesteds[0].set_bb(17);
1333     nesteds[1].set_bb(4711);
1334     std::copy(&nesteds[0], &nesteds[2],
1335               RepeatedFieldBackInserter(
1336                   protobuffer.mutable_repeated_nested_message()));
1337
1338     nested_ptrs.push_back(new Nested);
1339     nested_ptrs.back()->set_bb(170);
1340     nested_ptrs.push_back(new Nested);
1341     nested_ptrs.back()->set_bb(47110);
1342     std::copy(nested_ptrs.begin(), nested_ptrs.end(),
1343               RepeatedFieldBackInserter(
1344                   protobuffer.mutable_repeated_nested_message()));
1345
1346   }
1347
1348   virtual void TearDown() {
1349     STLDeleteContainerPointers(nested_ptrs.begin(), nested_ptrs.end());
1350   }
1351 };
1352
1353 TEST_F(RepeatedFieldInsertionIteratorsTest, Fibonacci) {
1354   EXPECT_TRUE(std::equal(fibonacci.begin(),
1355                          fibonacci.end(),
1356                          protobuffer.repeated_int32().begin()));
1357   EXPECT_TRUE(std::equal(protobuffer.repeated_int32().begin(),
1358                          protobuffer.repeated_int32().end(),
1359                          fibonacci.begin()));
1360 }
1361
1362 TEST_F(RepeatedFieldInsertionIteratorsTest, Halves) {
1363   EXPECT_TRUE(std::equal(halves.begin(),
1364                          halves.end(),
1365                          protobuffer.repeated_double().begin()));
1366   EXPECT_TRUE(std::equal(protobuffer.repeated_double().begin(),
1367                          protobuffer.repeated_double().end(),
1368                          halves.begin()));
1369 }
1370
1371 TEST_F(RepeatedFieldInsertionIteratorsTest, Words) {
1372   ASSERT_EQ(words.size(), protobuffer.repeated_string_size());
1373   for (int i = 0; i < words.size(); ++i)
1374     EXPECT_EQ(words.at(i), protobuffer.repeated_string(i));
1375 }
1376
1377 TEST_F(RepeatedFieldInsertionIteratorsTest, Words2) {
1378   words.clear();
1379   words.push_back("sing");
1380   words.push_back("a");
1381   words.push_back("song");
1382   words.push_back("of");
1383   words.push_back("six");
1384   words.push_back("pence");
1385   protobuffer.mutable_repeated_string()->Clear();
1386   std::copy(words.begin(), words.end(), RepeatedPtrFieldBackInserter(
1387       protobuffer.mutable_repeated_string()));
1388   ASSERT_EQ(words.size(), protobuffer.repeated_string_size());
1389   for (int i = 0; i < words.size(); ++i)
1390     EXPECT_EQ(words.at(i), protobuffer.repeated_string(i));
1391 }
1392
1393 TEST_F(RepeatedFieldInsertionIteratorsTest, Nesteds) {
1394   ASSERT_EQ(protobuffer.repeated_nested_message_size(), 4);
1395   EXPECT_EQ(protobuffer.repeated_nested_message(0).bb(), 17);
1396   EXPECT_EQ(protobuffer.repeated_nested_message(1).bb(), 4711);
1397   EXPECT_EQ(protobuffer.repeated_nested_message(2).bb(), 170);
1398   EXPECT_EQ(protobuffer.repeated_nested_message(3).bb(), 47110);
1399 }
1400
1401 TEST_F(RepeatedFieldInsertionIteratorsTest,
1402        AllocatedRepeatedPtrFieldWithStringIntData) {
1403   vector<Nested*> data;
1404   TestAllTypes goldenproto;
1405   for (int i = 0; i < 10; ++i) {
1406     Nested* new_data = new Nested;
1407     new_data->set_bb(i);
1408     data.push_back(new_data);
1409
1410     new_data = goldenproto.add_repeated_nested_message();
1411     new_data->set_bb(i);
1412   }
1413   TestAllTypes testproto;
1414   copy(data.begin(), data.end(),
1415        AllocatedRepeatedPtrFieldBackInserter(
1416            testproto.mutable_repeated_nested_message()));
1417   EXPECT_EQ(testproto.DebugString(), goldenproto.DebugString());
1418 }
1419
1420 TEST_F(RepeatedFieldInsertionIteratorsTest,
1421        AllocatedRepeatedPtrFieldWithString) {
1422   vector<string*> data;
1423   TestAllTypes goldenproto;
1424   for (int i = 0; i < 10; ++i) {
1425     string* new_data = new string;
1426     *new_data = "name-" + SimpleItoa(i);
1427     data.push_back(new_data);
1428
1429     new_data = goldenproto.add_repeated_string();
1430     *new_data = "name-" + SimpleItoa(i);
1431   }
1432   TestAllTypes testproto;
1433   copy(data.begin(), data.end(),
1434        AllocatedRepeatedPtrFieldBackInserter(
1435            testproto.mutable_repeated_string()));
1436   EXPECT_EQ(testproto.DebugString(), goldenproto.DebugString());
1437 }
1438
1439 }  // namespace
1440
1441 }  // namespace protobuf
1442 }  // namespace google