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
52namespace google {
53using protobuf_unittest::TestAllTypes;
54
55namespace protobuf {
56namespace {
57
58// Test operations on a small RepeatedField.
59TEST(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.
102TEST(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.
121TEST(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
147TEST(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
167TEST(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.
193static 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
202TEST(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
211TEST(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
221TEST(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
233TEST(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
249TEST(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
268TEST(RepeatedField, MergeFromSelf) {
269  RepeatedField<int> me;
270  me.Add(3);
271  EXPECT_DEATH(me.MergeFrom(me), "");
272}
273#endif  // PROTOBUF_HAS_DEATH_TEST
274
275TEST(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
290TEST(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
298TEST(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
310TEST(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
326TEST(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
341TEST(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
355TEST(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
365TEST(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
390TEST(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
429TEST(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
467TEST(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
485TEST(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
515TEST(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
536TEST(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
562static 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
571TEST(RepeatedPtrField, ReserveMoreThanDouble) {
572  RepeatedPtrField<string> field;
573  field.Reserve(20);
574
575  EXPECT_EQ(20, ReservedSpace(&field));
576}
577
578TEST(RepeatedPtrField, ReserveLessThanDouble) {
579  RepeatedPtrField<string> field;
580  field.Reserve(20);
581  field.Reserve(30);
582
583  EXPECT_EQ(40, ReservedSpace(&field));
584}
585
586TEST(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
596TEST(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.
610TEST(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().
650TEST(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
695TEST(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
714TEST(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
721TEST(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
736TEST(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
744TEST(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
756TEST(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
772TEST(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
791TEST(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
806TEST(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
820TEST(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
831TEST(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
898TEST(RepeatedPtrField, DeleteSubrange) {
899  // DeleteSubrange is a trivial extension of ExtendSubrange.
900}
901
902// ===================================================================
903
904// Iterator tests stolen from net/proto/proto-array_unittest.
905class 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
916TEST_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
923TEST_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
935TEST_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
947TEST_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
955class 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
966TEST_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
973TEST_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
984TEST_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
996TEST_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
1007TEST_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
1020TEST_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
1032TEST_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.
1046TEST_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
1055TEST_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
1073TEST_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
1081class 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
1094TEST_F(RepeatedPtrFieldPtrsIteratorTest, ConvertiblePtr) {
1095  RepeatedPtrField<string>::pointer_iterator iter =
1096      proto_array_.pointer_begin();
1097  static_cast<void>(iter);
1098}
1099
1100TEST_F(RepeatedPtrFieldPtrsIteratorTest, ConvertibleConstPtr) {
1101  RepeatedPtrField<string>::const_pointer_iterator iter =
1102      const_proto_array_->pointer_begin();
1103  static_cast<void>(iter);
1104}
1105
1106TEST_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
1118TEST_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
1130TEST_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
1143TEST_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
1156TEST_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
1170TEST_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.
1186TEST_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
1195TEST_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*.
1208struct 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
1215TEST_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
1250TEST_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
1268TEST_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
1294class 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
1353TEST_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
1362TEST_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
1371TEST_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
1377TEST_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
1393TEST_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
1401TEST_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
1420TEST_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
1443