1// Protocol Buffers - Google's data interchange format
2// Copyright 2008 Google Inc.  All rights reserved.
3// http://code.google.com/p/protobuf/
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are
7// met:
8//
9//     * Redistributions of source code must retain the above copyright
10// notice, this list of conditions and the following disclaimer.
11//     * Redistributions in binary form must reproduce the above
12// copyright notice, this list of conditions and the following disclaimer
13// in the documentation and/or other materials provided with the
14// distribution.
15//     * Neither the name of Google Inc. nor the names of its
16// contributors may be used to endorse or promote products derived from
17// this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31// 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 <list>
40#include <vector>
41
42#include <google/protobuf/repeated_field.h>
43
44#include <google/protobuf/stubs/common.h>
45#include <google/protobuf/unittest.pb.h>
46#include <google/protobuf/stubs/strutil.h>
47#include <google/protobuf/testing/googletest.h>
48#include <gtest/gtest.h>
49#include <google/protobuf/stubs/stl_util-inl.h>
50
51namespace google {
52using protobuf_unittest::TestAllTypes;
53
54namespace protobuf {
55namespace {
56
57// Test operations on a RepeatedField which is small enough that it does
58// not allocate a separate array for storage.
59TEST(RepeatedField, Small) {
60  RepeatedField<int> field;
61
62  EXPECT_EQ(field.size(), 0);
63
64  field.Add(5);
65
66  EXPECT_EQ(field.size(), 1);
67  EXPECT_EQ(field.Get(0), 5);
68
69  field.Add(42);
70
71  EXPECT_EQ(field.size(), 2);
72  EXPECT_EQ(field.Get(0), 5);
73  EXPECT_EQ(field.Get(1), 42);
74
75  field.Set(1, 23);
76
77  EXPECT_EQ(field.size(), 2);
78  EXPECT_EQ(field.Get(0), 5);
79  EXPECT_EQ(field.Get(1), 23);
80  EXPECT_EQ(field.SpaceUsedExcludingSelf(), 0);
81
82  field.RemoveLast();
83
84  EXPECT_EQ(field.size(), 1);
85  EXPECT_EQ(field.Get(0), 5);
86
87  field.Clear();
88
89  EXPECT_EQ(field.size(), 0);
90  EXPECT_EQ(field.SpaceUsedExcludingSelf(), 0);
91}
92
93// Test operations on a RepeatedField which is large enough to allocate a
94// separate array.
95TEST(RepeatedField, Large) {
96  RepeatedField<int> field;
97
98  for (int i = 0; i < 16; i++) {
99    field.Add(i * i);
100  }
101
102  EXPECT_EQ(field.size(), 16);
103
104  for (int i = 0; i < 16; i++) {
105    EXPECT_EQ(field.Get(i), i * i);
106  }
107
108  int expected_usage = 16 * sizeof(int);
109  EXPECT_GE(field.SpaceUsedExcludingSelf(), expected_usage);
110}
111
112// Test swapping between various types of RepeatedFields.
113TEST(RepeatedField, SwapSmallSmall) {
114  RepeatedField<int> field1;
115  RepeatedField<int> field2;
116
117  field1.Add(5);
118  field1.Add(42);
119
120  field1.Swap(&field2);
121
122  EXPECT_EQ(field1.size(), 0);
123  EXPECT_EQ(field2.size(), 2);
124  EXPECT_EQ(field2.Get(0), 5);
125  EXPECT_EQ(field2.Get(1), 42);
126}
127
128TEST(RepeatedField, SwapLargeSmall) {
129  RepeatedField<int> field1;
130  RepeatedField<int> field2;
131
132  for (int i = 0; i < 16; i++) {
133    field1.Add(i * i);
134  }
135  field2.Add(5);
136  field2.Add(42);
137  field1.Swap(&field2);
138
139  EXPECT_EQ(field1.size(), 2);
140  EXPECT_EQ(field1.Get(0), 5);
141  EXPECT_EQ(field1.Get(1), 42);
142  EXPECT_EQ(field2.size(), 16);
143  for (int i = 0; i < 16; i++) {
144    EXPECT_EQ(field2.Get(i), i * i);
145  }
146}
147
148TEST(RepeatedField, SwapLargeLarge) {
149  RepeatedField<int> field1;
150  RepeatedField<int> field2;
151
152  field1.Add(5);
153  field1.Add(42);
154  for (int i = 0; i < 16; i++) {
155    field1.Add(i);
156    field2.Add(i * i);
157  }
158  field2.Swap(&field1);
159
160  EXPECT_EQ(field1.size(), 16);
161  for (int i = 0; i < 16; i++) {
162    EXPECT_EQ(field1.Get(i), i * i);
163  }
164  EXPECT_EQ(field2.size(), 18);
165  EXPECT_EQ(field2.Get(0), 5);
166  EXPECT_EQ(field2.Get(1), 42);
167  for (int i = 2; i < 18; i++) {
168    EXPECT_EQ(field2.Get(i), i - 2);
169  }
170}
171
172// Determines how much space was reserved by the given field by adding elements
173// to it until it re-allocates its space.
174static int ReservedSpace(RepeatedField<int>* field) {
175  const int* ptr = field->data();
176  do {
177    field->Add(0);
178  } while (field->data() == ptr);
179
180  return field->size() - 1;
181}
182
183TEST(RepeatedField, ReserveMoreThanDouble) {
184  // Reserve more than double the previous space in the field and expect the
185  // field to reserve exactly the amount specified.
186  RepeatedField<int> field;
187  field.Reserve(20);
188
189  EXPECT_EQ(20, ReservedSpace(&field));
190}
191
192TEST(RepeatedField, ReserveLessThanDouble) {
193  // Reserve less than double the previous space in the field and expect the
194  // field to grow by double instead.
195  RepeatedField<int> field;
196  field.Reserve(20);
197  field.Reserve(30);
198
199  EXPECT_EQ(40, ReservedSpace(&field));
200}
201
202TEST(RepeatedField, ReserveLessThanExisting) {
203  // Reserve less than the previous space in the field and expect the
204  // field to not re-allocate at all.
205  RepeatedField<int> field;
206  field.Reserve(20);
207  const int* previous_ptr = field.data();
208  field.Reserve(10);
209
210  EXPECT_EQ(previous_ptr, field.data());
211  EXPECT_EQ(20, ReservedSpace(&field));
212}
213
214TEST(RepeatedField, MergeFrom) {
215  RepeatedField<int> source, destination;
216
217  source.Add(4);
218  source.Add(5);
219
220  destination.Add(1);
221  destination.Add(2);
222  destination.Add(3);
223
224  destination.MergeFrom(source);
225
226  ASSERT_EQ(5, destination.size());
227
228  EXPECT_EQ(1, destination.Get(0));
229  EXPECT_EQ(2, destination.Get(1));
230  EXPECT_EQ(3, destination.Get(2));
231  EXPECT_EQ(4, destination.Get(3));
232  EXPECT_EQ(5, destination.Get(4));
233}
234
235TEST(RepeatedField, MutableDataIsMutable) {
236  RepeatedField<int> field;
237  field.Add(1);
238  EXPECT_EQ(1, field.Get(0));
239  // The fact that this line compiles would be enough, but we'll check the
240  // value anyway.
241  *field.mutable_data() = 2;
242  EXPECT_EQ(2, field.Get(0));
243}
244
245TEST(RepeatedField, Truncate) {
246  RepeatedField<int> field;
247
248  field.Add(12);
249  field.Add(34);
250  field.Add(56);
251  field.Add(78);
252  EXPECT_EQ(4, field.size());
253
254  field.Truncate(3);
255  EXPECT_EQ(3, field.size());
256
257  field.Add(90);
258  EXPECT_EQ(4, field.size());
259  EXPECT_EQ(90, field.Get(3));
260
261  // Truncations that don't change the size are allowed, but growing is not
262  // allowed.
263  field.Truncate(field.size());
264#ifdef GTEST_HAS_DEATH_TEST
265  EXPECT_DEBUG_DEATH(field.Truncate(field.size() + 1), "new_size");
266#endif
267}
268
269
270// ===================================================================
271// RepeatedPtrField tests.  These pretty much just mirror the RepeatedField
272// tests above.
273
274TEST(RepeatedPtrField, Small) {
275  RepeatedPtrField<string> field;
276
277  EXPECT_EQ(field.size(), 0);
278
279  field.Add()->assign("foo");
280
281  EXPECT_EQ(field.size(), 1);
282  EXPECT_EQ(field.Get(0), "foo");
283
284  field.Add()->assign("bar");
285
286  EXPECT_EQ(field.size(), 2);
287  EXPECT_EQ(field.Get(0), "foo");
288  EXPECT_EQ(field.Get(1), "bar");
289
290  field.Mutable(1)->assign("baz");
291
292  EXPECT_EQ(field.size(), 2);
293  EXPECT_EQ(field.Get(0), "foo");
294  EXPECT_EQ(field.Get(1), "baz");
295
296  field.RemoveLast();
297
298  EXPECT_EQ(field.size(), 1);
299  EXPECT_EQ(field.Get(0), "foo");
300
301  field.Clear();
302
303  EXPECT_EQ(field.size(), 0);
304}
305
306TEST(RepeatedPtrField, Large) {
307  RepeatedPtrField<string> field;
308
309  for (int i = 0; i < 16; i++) {
310    *field.Add() += 'a' + i;
311  }
312
313  EXPECT_EQ(field.size(), 16);
314
315  for (int i = 0; i < 16; i++) {
316    EXPECT_EQ(field.Get(i).size(), 1);
317    EXPECT_EQ(field.Get(i)[0], 'a' + i);
318  }
319
320  int min_expected_usage = 16 * sizeof(string);
321  EXPECT_GE(field.SpaceUsedExcludingSelf(), min_expected_usage);
322}
323
324TEST(RepeatedPtrField, SwapSmallSmall) {
325  RepeatedPtrField<string> field1;
326  RepeatedPtrField<string> field2;
327
328  field1.Add()->assign("foo");
329  field1.Add()->assign("bar");
330  field1.Swap(&field2);
331
332  EXPECT_EQ(field1.size(), 0);
333  EXPECT_EQ(field2.size(), 2);
334  EXPECT_EQ(field2.Get(0), "foo");
335  EXPECT_EQ(field2.Get(1), "bar");
336}
337
338TEST(RepeatedPtrField, SwapLargeSmall) {
339  RepeatedPtrField<string> field1;
340  RepeatedPtrField<string> field2;
341
342  field2.Add()->assign("foo");
343  field2.Add()->assign("bar");
344  for (int i = 0; i < 16; i++) {
345    *field1.Add() += 'a' + i;
346  }
347  field1.Swap(&field2);
348
349  EXPECT_EQ(field1.size(), 2);
350  EXPECT_EQ(field1.Get(0), "foo");
351  EXPECT_EQ(field1.Get(1), "bar");
352  EXPECT_EQ(field2.size(), 16);
353  for (int i = 0; i < 16; i++) {
354    EXPECT_EQ(field2.Get(i).size(), 1);
355    EXPECT_EQ(field2.Get(i)[0], 'a' + i);
356  }
357}
358
359TEST(RepeatedPtrField, SwapLargeLarge) {
360  RepeatedPtrField<string> field1;
361  RepeatedPtrField<string> field2;
362
363  field1.Add()->assign("foo");
364  field1.Add()->assign("bar");
365  for (int i = 0; i < 16; i++) {
366    *field1.Add() += 'A' + i;
367    *field2.Add() += 'a' + i;
368  }
369  field2.Swap(&field1);
370
371  EXPECT_EQ(field1.size(), 16);
372  for (int i = 0; i < 16; i++) {
373    EXPECT_EQ(field1.Get(i).size(), 1);
374    EXPECT_EQ(field1.Get(i)[0], 'a' + i);
375  }
376  EXPECT_EQ(field2.size(), 18);
377  EXPECT_EQ(field2.Get(0), "foo");
378  EXPECT_EQ(field2.Get(1), "bar");
379  for (int i = 2; i < 18; i++) {
380    EXPECT_EQ(field2.Get(i).size(), 1);
381    EXPECT_EQ(field2.Get(i)[0], 'A' + i - 2);
382  }
383}
384
385static int ReservedSpace(RepeatedPtrField<string>* field) {
386  const string* const* ptr = field->data();
387  do {
388    field->Add();
389  } while (field->data() == ptr);
390
391  return field->size() - 1;
392}
393
394TEST(RepeatedPtrField, ReserveMoreThanDouble) {
395  RepeatedPtrField<string> field;
396  field.Reserve(20);
397
398  EXPECT_EQ(20, ReservedSpace(&field));
399}
400
401TEST(RepeatedPtrField, ReserveLessThanDouble) {
402  RepeatedPtrField<string> field;
403  field.Reserve(20);
404  field.Reserve(30);
405
406  EXPECT_EQ(40, ReservedSpace(&field));
407}
408
409TEST(RepeatedPtrField, ReserveLessThanExisting) {
410  RepeatedPtrField<string> field;
411  field.Reserve(20);
412  const string* const* previous_ptr = field.data();
413  field.Reserve(10);
414
415  EXPECT_EQ(previous_ptr, field.data());
416  EXPECT_EQ(20, ReservedSpace(&field));
417}
418
419TEST(RepeatedPtrField, ReserveDoesntLoseAllocated) {
420  // Check that a bug is fixed:  An earlier implementation of Reserve()
421  // failed to copy pointers to allocated-but-cleared objects, possibly
422  // leading to segfaults.
423  RepeatedPtrField<string> field;
424  string* first = field.Add();
425  field.RemoveLast();
426
427  field.Reserve(20);
428  EXPECT_EQ(first, field.Add());
429}
430
431// Clearing elements is tricky with RepeatedPtrFields since the memory for
432// the elements is retained and reused.
433TEST(RepeatedPtrField, ClearedElements) {
434  RepeatedPtrField<string> field;
435
436  string* original = field.Add();
437  *original = "foo";
438
439  EXPECT_EQ(field.ClearedCount(), 0);
440
441  field.RemoveLast();
442  EXPECT_TRUE(original->empty());
443  EXPECT_EQ(field.ClearedCount(), 1);
444
445  EXPECT_EQ(field.Add(), original);  // Should return same string for reuse.
446
447  EXPECT_EQ(field.ReleaseLast(), original);  // We take ownership.
448  EXPECT_EQ(field.ClearedCount(), 0);
449
450  EXPECT_NE(field.Add(), original);  // Should NOT return the same string.
451  EXPECT_EQ(field.ClearedCount(), 0);
452
453  field.AddAllocated(original);  // Give ownership back.
454  EXPECT_EQ(field.ClearedCount(), 0);
455  EXPECT_EQ(field.Mutable(1), original);
456
457  field.Clear();
458  EXPECT_EQ(field.ClearedCount(), 2);
459  EXPECT_EQ(field.ReleaseCleared(), original);  // Take ownership again.
460  EXPECT_EQ(field.ClearedCount(), 1);
461  EXPECT_NE(field.Add(), original);
462  EXPECT_EQ(field.ClearedCount(), 0);
463  EXPECT_NE(field.Add(), original);
464  EXPECT_EQ(field.ClearedCount(), 0);
465
466  field.AddCleared(original);  // Give ownership back, but as a cleared object.
467  EXPECT_EQ(field.ClearedCount(), 1);
468  EXPECT_EQ(field.Add(), original);
469  EXPECT_EQ(field.ClearedCount(), 0);
470}
471
472// Test all code paths in AddAllocated().
473TEST(RepeatedPtrField, AddAlocated) {
474  RepeatedPtrField<string> field;
475  while (field.size() < field.Capacity()) {
476    field.Add()->assign("filler");
477  }
478
479  int index = field.size();
480
481  // First branch:  Field is at capacity with no cleared objects.
482  string* foo = new string("foo");
483  field.AddAllocated(foo);
484  EXPECT_EQ(index + 1, field.size());
485  EXPECT_EQ(0, field.ClearedCount());
486  EXPECT_EQ(foo, &field.Get(index));
487
488  // Last branch:  Field is not at capacity and there are no cleared objects.
489  string* bar = new string("bar");
490  field.AddAllocated(bar);
491  ++index;
492  EXPECT_EQ(index + 1, field.size());
493  EXPECT_EQ(0, field.ClearedCount());
494  EXPECT_EQ(bar, &field.Get(index));
495
496  // Third branch:  Field is not at capacity and there are no cleared objects.
497  field.RemoveLast();
498  string* baz = new string("baz");
499  field.AddAllocated(baz);
500  EXPECT_EQ(index + 1, field.size());
501  EXPECT_EQ(1, field.ClearedCount());
502  EXPECT_EQ(baz, &field.Get(index));
503
504  // Second branch:  Field is at capacity but has some cleared objects.
505  while (field.size() < field.Capacity()) {
506    field.Add()->assign("filler2");
507  }
508  field.RemoveLast();
509  index = field.size();
510  string* qux = new string("qux");
511  field.AddAllocated(qux);
512  EXPECT_EQ(index + 1, field.size());
513  // We should have discarded the cleared object.
514  EXPECT_EQ(0, field.ClearedCount());
515  EXPECT_EQ(qux, &field.Get(index));
516}
517
518TEST(RepeatedPtrField, MergeFrom) {
519  RepeatedPtrField<string> source, destination;
520
521  source.Add()->assign("4");
522  source.Add()->assign("5");
523
524  destination.Add()->assign("1");
525  destination.Add()->assign("2");
526  destination.Add()->assign("3");
527
528  destination.MergeFrom(source);
529
530  ASSERT_EQ(5, destination.size());
531
532  EXPECT_EQ("1", destination.Get(0));
533  EXPECT_EQ("2", destination.Get(1));
534  EXPECT_EQ("3", destination.Get(2));
535  EXPECT_EQ("4", destination.Get(3));
536  EXPECT_EQ("5", destination.Get(4));
537}
538
539TEST(RepeatedPtrField, MutableDataIsMutable) {
540  RepeatedPtrField<string> field;
541  *field.Add() = "1";
542  EXPECT_EQ("1", field.Get(0));
543  // The fact that this line compiles would be enough, but we'll check the
544  // value anyway.
545  string** data = field.mutable_data();
546  **data = "2";
547  EXPECT_EQ("2", field.Get(0));
548}
549
550// ===================================================================
551
552// Iterator tests stolen from net/proto/proto-array_unittest.
553class RepeatedFieldIteratorTest : public testing::Test {
554 protected:
555  virtual void SetUp() {
556    for (int i = 0; i < 3; ++i) {
557      proto_array_.Add(i);
558    }
559  }
560
561  RepeatedField<int> proto_array_;
562};
563
564TEST_F(RepeatedFieldIteratorTest, Convertible) {
565  RepeatedField<int>::iterator iter = proto_array_.begin();
566  RepeatedField<int>::const_iterator c_iter = iter;
567  EXPECT_EQ(0, *c_iter);
568}
569
570TEST_F(RepeatedFieldIteratorTest, MutableIteration) {
571  RepeatedField<int>::iterator iter = proto_array_.begin();
572  EXPECT_EQ(0, *iter);
573  ++iter;
574  EXPECT_EQ(1, *iter++);
575  EXPECT_EQ(2, *iter);
576  ++iter;
577  EXPECT_TRUE(proto_array_.end() == iter);
578
579  EXPECT_EQ(2, *(proto_array_.end() - 1));
580}
581
582TEST_F(RepeatedFieldIteratorTest, ConstIteration) {
583  const RepeatedField<int>& const_proto_array = proto_array_;
584  RepeatedField<int>::const_iterator iter = const_proto_array.begin();
585  EXPECT_EQ(0, *iter);
586  ++iter;
587  EXPECT_EQ(1, *iter++);
588  EXPECT_EQ(2, *iter);
589  ++iter;
590  EXPECT_TRUE(proto_array_.end() == iter);
591  EXPECT_EQ(2, *(proto_array_.end() - 1));
592}
593
594TEST_F(RepeatedFieldIteratorTest, Mutation) {
595  RepeatedField<int>::iterator iter = proto_array_.begin();
596  *iter = 7;
597  EXPECT_EQ(7, proto_array_.Get(0));
598}
599
600// -------------------------------------------------------------------
601
602class RepeatedPtrFieldIteratorTest : public testing::Test {
603 protected:
604  virtual void SetUp() {
605    proto_array_.Add()->assign("foo");
606    proto_array_.Add()->assign("bar");
607    proto_array_.Add()->assign("baz");
608  }
609
610  RepeatedPtrField<string> proto_array_;
611};
612
613TEST_F(RepeatedPtrFieldIteratorTest, Convertible) {
614  RepeatedPtrField<string>::iterator iter = proto_array_.begin();
615  RepeatedPtrField<string>::const_iterator c_iter = iter;
616}
617
618TEST_F(RepeatedPtrFieldIteratorTest, MutableIteration) {
619  RepeatedPtrField<string>::iterator iter = proto_array_.begin();
620  EXPECT_EQ("foo", *iter);
621  ++iter;
622  EXPECT_EQ("bar", *(iter++));
623  EXPECT_EQ("baz", *iter);
624  ++iter;
625  EXPECT_TRUE(proto_array_.end() == iter);
626  EXPECT_EQ("baz", *(--proto_array_.end()));
627}
628
629TEST_F(RepeatedPtrFieldIteratorTest, ConstIteration) {
630  const RepeatedPtrField<string>& const_proto_array = proto_array_;
631  RepeatedPtrField<string>::const_iterator iter = const_proto_array.begin();
632  EXPECT_EQ("foo", *iter);
633  ++iter;
634  EXPECT_EQ("bar", *(iter++));
635  EXPECT_EQ("baz", *iter);
636  ++iter;
637  EXPECT_TRUE(const_proto_array.end() == iter);
638  EXPECT_EQ("baz", *(--const_proto_array.end()));
639}
640
641TEST_F(RepeatedPtrFieldIteratorTest, RandomAccess) {
642  RepeatedPtrField<string>::iterator iter = proto_array_.begin();
643  RepeatedPtrField<string>::iterator iter2 = iter;
644  ++iter2;
645  ++iter2;
646  EXPECT_TRUE(iter + 2 == iter2);
647  EXPECT_TRUE(iter == iter2 - 2);
648  EXPECT_EQ("baz", iter[2]);
649  EXPECT_EQ("baz", *(iter + 2));
650  EXPECT_EQ(3, proto_array_.end() - proto_array_.begin());
651}
652
653TEST_F(RepeatedPtrFieldIteratorTest, Comparable) {
654  RepeatedPtrField<string>::const_iterator iter = proto_array_.begin();
655  RepeatedPtrField<string>::const_iterator iter2 = iter + 1;
656  EXPECT_TRUE(iter == iter);
657  EXPECT_TRUE(iter != iter2);
658  EXPECT_TRUE(iter < iter2);
659  EXPECT_TRUE(iter <= iter2);
660  EXPECT_TRUE(iter <= iter);
661  EXPECT_TRUE(iter2 > iter);
662  EXPECT_TRUE(iter2 >= iter);
663  EXPECT_TRUE(iter >= iter);
664}
665
666// Uninitialized iterator does not point to any of the RepeatedPtrField.
667TEST_F(RepeatedPtrFieldIteratorTest, UninitializedIterator) {
668  RepeatedPtrField<string>::iterator iter;
669  EXPECT_TRUE(iter != proto_array_.begin());
670  EXPECT_TRUE(iter != proto_array_.begin() + 1);
671  EXPECT_TRUE(iter != proto_array_.begin() + 2);
672  EXPECT_TRUE(iter != proto_array_.begin() + 3);
673  EXPECT_TRUE(iter != proto_array_.end());
674}
675
676TEST_F(RepeatedPtrFieldIteratorTest, STLAlgorithms_lower_bound) {
677  proto_array_.Clear();
678  proto_array_.Add()->assign("a");
679  proto_array_.Add()->assign("c");
680  proto_array_.Add()->assign("d");
681  proto_array_.Add()->assign("n");
682  proto_array_.Add()->assign("p");
683  proto_array_.Add()->assign("x");
684  proto_array_.Add()->assign("y");
685
686  string v = "f";
687  RepeatedPtrField<string>::const_iterator it =
688      lower_bound(proto_array_.begin(), proto_array_.end(), v);
689
690  EXPECT_EQ(*it, "n");
691  EXPECT_TRUE(it == proto_array_.begin() + 3);
692}
693
694TEST_F(RepeatedPtrFieldIteratorTest, Mutation) {
695  RepeatedPtrField<string>::iterator iter = proto_array_.begin();
696  *iter = "qux";
697  EXPECT_EQ("qux", proto_array_.Get(0));
698}
699
700// -------------------------------------------------------------------
701
702class RepeatedPtrFieldPtrsIteratorTest : public testing::Test {
703 protected:
704  virtual void SetUp() {
705    proto_array_.Add()->assign("foo");
706    proto_array_.Add()->assign("bar");
707    proto_array_.Add()->assign("baz");
708  }
709
710  RepeatedPtrField<string> proto_array_;
711};
712
713TEST_F(RepeatedPtrFieldPtrsIteratorTest, ConvertiblePtr) {
714  RepeatedPtrField<string>::pointer_iterator iter =
715      proto_array_.pointer_begin();
716}
717
718TEST_F(RepeatedPtrFieldPtrsIteratorTest, MutablePtrIteration) {
719  RepeatedPtrField<string>::pointer_iterator iter =
720      proto_array_.pointer_begin();
721  EXPECT_EQ("foo", **iter);
722  ++iter;
723  EXPECT_EQ("bar", **(iter++));
724  EXPECT_EQ("baz", **iter);
725  ++iter;
726  EXPECT_TRUE(proto_array_.pointer_end() == iter);
727  EXPECT_EQ("baz", **(--proto_array_.pointer_end()));
728}
729
730TEST_F(RepeatedPtrFieldPtrsIteratorTest, RandomPtrAccess) {
731  RepeatedPtrField<string>::pointer_iterator iter =
732      proto_array_.pointer_begin();
733  RepeatedPtrField<string>::pointer_iterator iter2 = iter;
734  ++iter2;
735  ++iter2;
736  EXPECT_TRUE(iter + 2 == iter2);
737  EXPECT_TRUE(iter == iter2 - 2);
738  EXPECT_EQ("baz", *iter[2]);
739  EXPECT_EQ("baz", **(iter + 2));
740  EXPECT_EQ(3, proto_array_.end() - proto_array_.begin());
741}
742
743TEST_F(RepeatedPtrFieldPtrsIteratorTest, ComparablePtr) {
744  RepeatedPtrField<string>::pointer_iterator iter =
745      proto_array_.pointer_begin();
746  RepeatedPtrField<string>::pointer_iterator iter2 = iter + 1;
747  EXPECT_TRUE(iter == iter);
748  EXPECT_TRUE(iter != iter2);
749  EXPECT_TRUE(iter < iter2);
750  EXPECT_TRUE(iter <= iter2);
751  EXPECT_TRUE(iter <= iter);
752  EXPECT_TRUE(iter2 > iter);
753  EXPECT_TRUE(iter2 >= iter);
754  EXPECT_TRUE(iter >= iter);
755}
756
757// Uninitialized iterator does not point to any of the RepeatedPtrOverPtrs.
758// Dereferencing an uninitialized iterator crashes the process.
759TEST_F(RepeatedPtrFieldPtrsIteratorTest, UninitializedPtrIterator) {
760  RepeatedPtrField<string>::pointer_iterator iter;
761  EXPECT_TRUE(iter != proto_array_.pointer_begin());
762  EXPECT_TRUE(iter != proto_array_.pointer_begin() + 1);
763  EXPECT_TRUE(iter != proto_array_.pointer_begin() + 2);
764  EXPECT_TRUE(iter != proto_array_.pointer_begin() + 3);
765  EXPECT_TRUE(iter != proto_array_.pointer_end());
766}
767
768
769// This comparison functor is required by the tests for RepeatedPtrOverPtrs.
770// They operate on strings and need to compare strings as strings in
771// any stl algorithm, even though the iterator returns a pointer to a string
772// - i.e. *iter has type string*.
773struct StringLessThan {
774  bool operator()(const string* z, const string& y) {
775    return *z < y;
776  }
777  bool operator()(const string* z, const string* y) {
778    return *z < *y;
779  }
780};
781
782TEST_F(RepeatedPtrFieldPtrsIteratorTest, PtrSTLAlgorithms_lower_bound) {
783  proto_array_.Clear();
784  proto_array_.Add()->assign("a");
785  proto_array_.Add()->assign("c");
786  proto_array_.Add()->assign("d");
787  proto_array_.Add()->assign("n");
788  proto_array_.Add()->assign("p");
789  proto_array_.Add()->assign("x");
790  proto_array_.Add()->assign("y");
791
792  RepeatedPtrField<string>::pointer_iterator iter =
793      proto_array_.pointer_begin();
794  string v = "f";
795  RepeatedPtrField<string>::pointer_iterator it =
796      lower_bound(proto_array_.pointer_begin(), proto_array_.pointer_end(),
797                  &v, StringLessThan());
798
799  GOOGLE_CHECK(*it != NULL);
800
801  EXPECT_EQ(**it, "n");
802  EXPECT_TRUE(it == proto_array_.pointer_begin() + 3);
803}
804
805TEST_F(RepeatedPtrFieldPtrsIteratorTest, PtrMutation) {
806  RepeatedPtrField<string>::pointer_iterator iter =
807      proto_array_.pointer_begin();
808  **iter = "qux";
809  EXPECT_EQ("qux", proto_array_.Get(0));
810
811  EXPECT_EQ("bar", proto_array_.Get(1));
812  EXPECT_EQ("baz", proto_array_.Get(2));
813  ++iter;
814  delete *iter;
815  *iter = new string("a");
816  ++iter;
817  delete *iter;
818  *iter = new string("b");
819  EXPECT_EQ("a", proto_array_.Get(1));
820  EXPECT_EQ("b", proto_array_.Get(2));
821}
822
823TEST_F(RepeatedPtrFieldPtrsIteratorTest, Sort) {
824  proto_array_.Add()->assign("c");
825  proto_array_.Add()->assign("d");
826  proto_array_.Add()->assign("n");
827  proto_array_.Add()->assign("p");
828  proto_array_.Add()->assign("a");
829  proto_array_.Add()->assign("y");
830  proto_array_.Add()->assign("x");
831  EXPECT_EQ("foo", proto_array_.Get(0));
832  EXPECT_EQ("n", proto_array_.Get(5));
833  EXPECT_EQ("x", proto_array_.Get(9));
834  sort(proto_array_.pointer_begin(),
835       proto_array_.pointer_end(),
836       StringLessThan());
837  EXPECT_EQ("a", proto_array_.Get(0));
838  EXPECT_EQ("baz", proto_array_.Get(2));
839  EXPECT_EQ("y", proto_array_.Get(9));
840}
841
842
843// -----------------------------------------------------------------------------
844// Unit-tests for the insert iterators
845// google::protobuf::RepeatedFieldBackInserter,
846// google::protobuf::AllocatedRepeatedPtrFieldBackInserter
847// Ported from util/gtl/proto-array-iterators_unittest.
848
849class RepeatedFieldInsertionIteratorsTest : public testing::Test {
850 protected:
851  std::list<double> halves;
852  std::list<int> fibonacci;
853  std::vector<string> words;
854  typedef TestAllTypes::NestedMessage Nested;
855  Nested nesteds[2];
856  std::vector<Nested*> nested_ptrs;
857  TestAllTypes protobuffer;
858
859  virtual void SetUp() {
860    fibonacci.push_back(1);
861    fibonacci.push_back(1);
862    fibonacci.push_back(2);
863    fibonacci.push_back(3);
864    fibonacci.push_back(5);
865    fibonacci.push_back(8);
866    std::copy(fibonacci.begin(), fibonacci.end(),
867              RepeatedFieldBackInserter(protobuffer.mutable_repeated_int32()));
868
869    halves.push_back(1.0);
870    halves.push_back(0.5);
871    halves.push_back(0.25);
872    halves.push_back(0.125);
873    halves.push_back(0.0625);
874    std::copy(halves.begin(), halves.end(),
875              RepeatedFieldBackInserter(protobuffer.mutable_repeated_double()));
876
877    words.push_back("Able");
878    words.push_back("was");
879    words.push_back("I");
880    words.push_back("ere");
881    words.push_back("I");
882    words.push_back("saw");
883    words.push_back("Elba");
884    std::copy(words.begin(), words.end(),
885              RepeatedFieldBackInserter(protobuffer.mutable_repeated_string()));
886
887    nesteds[0].set_bb(17);
888    nesteds[1].set_bb(4711);
889    std::copy(&nesteds[0], &nesteds[2],
890              RepeatedFieldBackInserter(
891                  protobuffer.mutable_repeated_nested_message()));
892
893    nested_ptrs.push_back(new Nested);
894    nested_ptrs.back()->set_bb(170);
895    nested_ptrs.push_back(new Nested);
896    nested_ptrs.back()->set_bb(47110);
897    std::copy(nested_ptrs.begin(), nested_ptrs.end(),
898              RepeatedFieldBackInserter(
899                  protobuffer.mutable_repeated_nested_message()));
900
901  }
902
903  virtual void TearDown() {
904    STLDeleteContainerPointers(nested_ptrs.begin(), nested_ptrs.end());
905  }
906};
907
908TEST_F(RepeatedFieldInsertionIteratorsTest, Fibonacci) {
909  EXPECT_TRUE(std::equal(fibonacci.begin(),
910                         fibonacci.end(),
911                         protobuffer.repeated_int32().begin()));
912  EXPECT_TRUE(std::equal(protobuffer.repeated_int32().begin(),
913                         protobuffer.repeated_int32().end(),
914                         fibonacci.begin()));
915}
916
917TEST_F(RepeatedFieldInsertionIteratorsTest, Halves) {
918  EXPECT_TRUE(std::equal(halves.begin(),
919                         halves.end(),
920                         protobuffer.repeated_double().begin()));
921  EXPECT_TRUE(std::equal(protobuffer.repeated_double().begin(),
922                         protobuffer.repeated_double().end(),
923                         halves.begin()));
924}
925
926TEST_F(RepeatedFieldInsertionIteratorsTest, Words) {
927  ASSERT_EQ(words.size(), protobuffer.repeated_string_size());
928  EXPECT_EQ(words.at(0), protobuffer.repeated_string(0));
929  EXPECT_EQ(words.at(1), protobuffer.repeated_string(1));
930  EXPECT_EQ(words.at(2), protobuffer.repeated_string(2));
931  EXPECT_EQ(words.at(3), protobuffer.repeated_string(3));
932  EXPECT_EQ(words.at(4), protobuffer.repeated_string(4));
933  EXPECT_EQ(words.at(5), protobuffer.repeated_string(5));
934  EXPECT_EQ(words.at(6), protobuffer.repeated_string(6));
935}
936
937TEST_F(RepeatedFieldInsertionIteratorsTest, Nesteds) {
938  ASSERT_EQ(protobuffer.repeated_nested_message_size(), 4);
939  EXPECT_EQ(protobuffer.repeated_nested_message(0).bb(), 17);
940  EXPECT_EQ(protobuffer.repeated_nested_message(1).bb(), 4711);
941  EXPECT_EQ(protobuffer.repeated_nested_message(2).bb(), 170);
942  EXPECT_EQ(protobuffer.repeated_nested_message(3).bb(), 47110);
943}
944
945TEST_F(RepeatedFieldInsertionIteratorsTest,
946       AllocatedRepeatedPtrFieldWithStringIntData) {
947  vector<Nested*> data;
948  TestAllTypes goldenproto;
949  for (int i = 0; i < 10; ++i) {
950    Nested* new_data = new Nested;
951    new_data->set_bb(i);
952    data.push_back(new_data);
953
954    new_data = goldenproto.add_repeated_nested_message();
955    new_data->set_bb(i);
956  }
957  TestAllTypes testproto;
958  copy(data.begin(), data.end(),
959       AllocatedRepeatedPtrFieldBackInserter(
960           testproto.mutable_repeated_nested_message()));
961  EXPECT_EQ(testproto.DebugString(), goldenproto.DebugString());
962}
963
964TEST_F(RepeatedFieldInsertionIteratorsTest,
965       AllocatedRepeatedPtrFieldWithString) {
966  vector<string*> data;
967  TestAllTypes goldenproto;
968  for (int i = 0; i < 10; ++i) {
969    string* new_data = new string;
970    *new_data = "name-" + SimpleItoa(i);
971    data.push_back(new_data);
972
973    new_data = goldenproto.add_repeated_string();
974    *new_data = "name-" + SimpleItoa(i);
975  }
976  TestAllTypes testproto;
977  copy(data.begin(), data.end(),
978       AllocatedRepeatedPtrFieldBackInserter(
979           testproto.mutable_repeated_string()));
980  EXPECT_EQ(testproto.DebugString(), goldenproto.DebugString());
981}
982
983}  // namespace
984
985}  // namespace protobuf
986}  // namespace google
987