Implement RepeatedField.AddRange (#1733)

* Improve exception throwing implementation in collections

* Implement RepeatedField.AddRange.

This fixes issue #1730.

* Optimize AddRange for sequences implementing ICollection

(Also fix a few more C# 6-isms.)

* Remove the overload for Add(RepeatedField<T>)

We now just perform the optimization within AddRange itself.

This is a breaking change in terms of "drop in the DLL", but is
source compatible, which should be fine.

3 files changed, 171 insertions, 63 deletions

diff --git a/csharp/src/Google.Protobuf.Test/Collections/RepeatedFieldTest.cs b/csharp/src/Google.Protobuf.Test/Collections/RepeatedFieldTest.cs
index 8ed54cfb..6852f75f 100644
--- a/csharp/src/Google.Protobuf.Test/Collections/RepeatedFieldTest.cs
+++ b/csharp/src/Google.Protobuf.Test/Collections/RepeatedFieldTest.cs
@@ -75,10 +75,96 @@ namespace Google.Protobuf.Collections
         }
 
         [Test]
-        public void Add_RepeatedField()
+        public void AddRange_SlowPath()
+        {
+            var list = new RepeatedField<string>();
+            list.AddRange(new[] { "foo", "bar" }.Select(x => x));
+            Assert.AreEqual(2, list.Count);
+            Assert.AreEqual("foo", list[0]);
+            Assert.AreEqual("bar", list[1]);
+        }
+
+        [Test]
+        public void AddRange_SlowPath_NullsProhibited_ReferenceType()
+        {
+            var list = new RepeatedField<string>();
+            // It's okay for this to throw ArgumentNullException if necessary.
+            // It's not ideal, but not awful.
+            Assert.Catch<ArgumentException>(() => list.AddRange(new[] { "foo", null }.Select(x => x)));
+        }
+
+        [Test]
+        public void AddRange_SlowPath_NullsProhibited_NullableValueType()
+        {
+            var list = new RepeatedField<int?>();
+            // It's okay for this to throw ArgumentNullException if necessary.
+            // It's not ideal, but not awful.
+            Assert.Catch<ArgumentException>(() => list.AddRange(new[] { 20, (int?)null }.Select(x => x)));
+        }
+
+        [Test]
+        public void AddRange_Optimized_NonNullableValueType()
+        {
+            var list = new RepeatedField<int>();
+            list.AddRange(new List<int> { 20, 30 });
+            Assert.AreEqual(2, list.Count);
+            Assert.AreEqual(20, list[0]);
+            Assert.AreEqual(30, list[1]);
+        }
+
+        [Test]
+        public void AddRange_Optimized_ReferenceType()
+        {
+            var list = new RepeatedField<string>();
+            list.AddRange(new List<string> { "foo", "bar" });
+            Assert.AreEqual(2, list.Count);
+            Assert.AreEqual("foo", list[0]);
+            Assert.AreEqual("bar", list[1]);
+        }
+
+        [Test]
+        public void AddRange_Optimized_NullableValueType()
+        {
+            var list = new RepeatedField<int?>();
+            list.AddRange(new List<int?> { 20, 30 });
+            Assert.AreEqual(2, list.Count);
+            Assert.AreEqual((int?) 20, list[0]);
+            Assert.AreEqual((int?) 30, list[1]);
+        }
+
+        [Test]
+        public void AddRange_Optimized_NullsProhibited_ReferenceType()
+        {
+            // We don't just trust that a collection with a nullable element type doesn't contain nulls
+            var list = new RepeatedField<string>();
+            // It's okay for this to throw ArgumentNullException if necessary.
+            // It's not ideal, but not awful.
+            Assert.Catch<ArgumentException>(() => list.AddRange(new List<string> { "foo", null }));
+        }
+
+        [Test]
+        public void AddRange_Optimized_NullsProhibited_NullableValueType()
+        {
+            // We don't just trust that a collection with a nullable element type doesn't contain nulls
+            var list = new RepeatedField<int?>();
+            // It's okay for this to throw ArgumentNullException if necessary.
+            // It's not ideal, but not awful.
+            Assert.Catch<ArgumentException>(() => list.AddRange(new List<int?> { 20, null }));
+        }
+
+        [Test]
+        public void AddRange_AlreadyNotEmpty()
+        {
+            var list = new RepeatedField<int> { 1, 2, 3 };
+            list.AddRange(new List<int> { 4, 5, 6 });
+            CollectionAssert.AreEqual(new[] { 1, 2, 3, 4, 5, 6 }, list);
+        }
+
+        [Test]
+        public void AddRange_RepeatedField()
         {
             var list = new RepeatedField<string> { "original" };
-            list.Add(new RepeatedField<string> { "foo", "bar" });
+            list.AddRange(new RepeatedField<string> { "foo", "bar" });
             Assert.AreEqual(3, list.Count);
             Assert.AreEqual("original", list[0]);
             Assert.AreEqual("foo", list[1]);
diff --git a/csharp/src/Google.Protobuf/Collections/MapField.cs b/csharp/src/Google.Protobuf/Collections/MapField.cs
index 053f7558..537ce261 100644
--- a/csharp/src/Google.Protobuf/Collections/MapField.cs
+++ b/csharp/src/Google.Protobuf/Collections/MapField.cs
@@ -30,14 +30,13 @@
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 #endregion
 
+using Google.Protobuf.Compatibility;
 using Google.Protobuf.Reflection;
 using System;
 using System.Collections;
 using System.Collections.Generic;
 using System.IO;
 using System.Linq;
-using System.Text;
-using Google.Protobuf.Compatibility;
 
 namespace Google.Protobuf.Collections
 {
@@ -113,7 +112,7 @@ namespace Google.Protobuf.Collections
             // Validation of arguments happens in ContainsKey and the indexer
             if (ContainsKey(key))
             {
-                throw new ArgumentException("Key already exists in map", "key");
+                throw new ArgumentException("Key already exists in map", nameof(key));
             }
             this[key] = value;
         }
@@ -125,7 +124,7 @@ namespace Google.Protobuf.Collections
         /// <returns><c>true</c> if the map contains the given key; <c>false</c> otherwise.</returns>
         public bool ContainsKey(TKey key)
         {
-            ProtoPreconditions.CheckNotNullUnconstrained(key, "key");
+            ProtoPreconditions.CheckNotNullUnconstrained(key, nameof(key));
             return map.ContainsKey(key);
         }
 
@@ -142,7 +141,7 @@ namespace Google.Protobuf.Collections
         /// <returns><c>true</c> if the map contained the given key before the entry was removed; <c>false</c> otherwise.</returns>
         public bool Remove(TKey key)
         {
-            ProtoPreconditions.CheckNotNullUnconstrained(key, "key");
+            ProtoPreconditions.CheckNotNullUnconstrained(key, nameof(key));
             LinkedListNode<KeyValuePair<TKey, TValue>> node;
             if (map.TryGetValue(key, out node))
             {
@@ -190,7 +189,7 @@ namespace Google.Protobuf.Collections
         {
             get
             {
-                ProtoPreconditions.CheckNotNullUnconstrained(key, "key");
+                ProtoPreconditions.CheckNotNullUnconstrained(key, nameof(key));
                 TValue value;
                 if (TryGetValue(key, out value))
                 {
@@ -200,11 +199,11 @@ namespace Google.Protobuf.Collections
             }
             set
             {
-                ProtoPreconditions.CheckNotNullUnconstrained(key, "key");
+                ProtoPreconditions.CheckNotNullUnconstrained(key, nameof(key));
                 // value == null check here is redundant, but avoids boxing.
                 if (value == null)
                 {
-                    ProtoPreconditions.CheckNotNullUnconstrained(value, "value");
+                    ProtoPreconditions.CheckNotNullUnconstrained(value, nameof(value));
                 }
                 LinkedListNode<KeyValuePair<TKey, TValue>> node;
                 var pair = new KeyValuePair<TKey, TValue>(key, value);
@@ -236,7 +235,7 @@ namespace Google.Protobuf.Collections
         /// <param name="entries">The entries to add to the map.</param>
         public void Add(IDictionary<TKey, TValue> entries)
         {
-            ProtoPreconditions.CheckNotNull(entries, "entries");
+            ProtoPreconditions.CheckNotNull(entries, nameof(entries));
             foreach (var pair in entries)
             {
                 Add(pair.Key, pair.Value);
@@ -315,7 +314,7 @@ namespace Google.Protobuf.Collections
         {
             if (item.Key == null)
             {
-                throw new ArgumentException("Key is null", "item");
+                throw new ArgumentException("Key is null", nameof(item));
             }
             LinkedListNode<KeyValuePair<TKey, TValue>> node;
             if (map.TryGetValue(item.Key, out node) &&
@@ -503,7 +502,7 @@ namespace Google.Protobuf.Collections
 
         void IDictionary.Remove(object key)
         {
-            ProtoPreconditions.CheckNotNull(key, "key");
+            ProtoPreconditions.CheckNotNull(key, nameof(key));
             if (!(key is TKey))
             {
                 return;
@@ -532,7 +531,7 @@ namespace Google.Protobuf.Collections
         {
             get
             {
-                ProtoPreconditions.CheckNotNull(key, "key");
+                ProtoPreconditions.CheckNotNull(key, nameof(key));
                 if (!(key is TKey))
                 {
                     return null;
@@ -714,11 +713,11 @@ namespace Google.Protobuf.Collections
             {
                 if (arrayIndex < 0)
                 {
-                    throw new ArgumentOutOfRangeException("arrayIndex");
+                    throw new ArgumentOutOfRangeException(nameof(arrayIndex));
                 }
                 if (arrayIndex + Count  >= array.Length)
                 {
-                    throw new ArgumentException("Not enough space in the array", "array");
+                    throw new ArgumentException("Not enough space in the array", nameof(array));
                 }
                 foreach (var item in this)
                 {
@@ -745,11 +744,11 @@ namespace Google.Protobuf.Collections
             {
                 if (index < 0)
                 {
-                    throw new ArgumentOutOfRangeException("index");
+                    throw new ArgumentOutOfRangeException(nameof(index));
                 }
                 if (index + Count >= array.Length)
                 {
-                    throw new ArgumentException("Not enough space in the array", "array");
+                    throw new ArgumentException("Not enough space in the array", nameof(array));
                 }
                 foreach (var item in this)
                 {
diff --git a/csharp/src/Google.Protobuf/Collections/RepeatedField.cs b/csharp/src/Google.Protobuf/Collections/RepeatedField.cs
index d1db856c..7bb56448 100644
--- a/csharp/src/Google.Protobuf/Collections/RepeatedField.cs
+++ b/csharp/src/Google.Protobuf/Collections/RepeatedField.cs
@@ -34,7 +34,6 @@ using System;
 using System.Collections;
 using System.Collections.Generic;
 using System.IO;
-using System.Text;
 
 namespace Google.Protobuf.Collections
 {
@@ -227,10 +226,7 @@ namespace Google.Protobuf.Collections
         /// <param name="item">The item to add.</param>
         public void Add(T item)
         {
-            if (item == null)
-            {
-                throw new ArgumentNullException("item");
-            }
+            ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
             EnsureSize(count + 1);
             array[count++] = item;
         }
@@ -285,46 +281,82 @@ namespace Google.Protobuf.Collections
         /// <summary>
         /// Gets the number of elements contained in the collection.
         /// </summary>
-        public int Count { get { return count; } }
+        public int Count => count;
 
         /// <summary>
         /// Gets a value indicating whether the collection is read-only.
         /// </summary>
-        public bool IsReadOnly { get { return false; } }
-
-        // TODO: Remove this overload and just handle it in the one below, at execution time?
+        public bool IsReadOnly => false;
 
         /// <summary>
         /// Adds all of the specified values into this collection.
         /// </summary>
         /// <param name="values">The values to add to this collection.</param>
-        public void Add(RepeatedField<T> values)
+        public void AddRange(IEnumerable<T> values)
         {
-            if (values == null)
+            ProtoPreconditions.CheckNotNull(values, nameof(values));
+
+            // Optimization 1: If the collection we're adding is already a RepeatedField<T>,
+            // we know the values are valid.
+            var otherRepeatedField = values as RepeatedField<T>;
+            if (otherRepeatedField != null)
             {
-                throw new ArgumentNullException("values");
+                EnsureSize(count + otherRepeatedField.count);
+                Array.Copy(otherRepeatedField.array, 0, array, count, otherRepeatedField.count);
+                count += otherRepeatedField.count;
+                return;
+            }
+
+            // Optimization 2: The collection is an ICollection, so we can expand
+            // just once and ask the collection to copy itself into the array.
+            var collection = values as ICollection;
+            if (collection != null)
+            {
+                var extraCount = collection.Count;
+                // For reference types and nullable value types, we need to check that there are no nulls
+                // present. (This isn't a thread-safe approach, but we don't advertise this is thread-safe.)
+                // We expect the JITter to optimize this test to true/false, so it's effectively conditional
+                // specialization.
+                if (default(T) == null)
+                {
+                    // TODO: Measure whether iterating once to check and then letting the collection copy
+                    // itself is faster or slower than iterating and adding as we go. For large
+                    // collections this will not be great in terms of cache usage... but the optimized
+                    // copy may be significantly faster than doing it one at a time.
+                    foreach (var item in collection)
+                    {
+                        if (item == null)
+                        {
+                            throw new ArgumentException("Sequence contained null element", nameof(values));
+                        }
+                    }
+                }
+                EnsureSize(count + extraCount);
+                collection.CopyTo(array, count);
+                count += extraCount;
+                return;
+            }
+
+            // We *could* check for ICollection<T> as well, but very very few collections implement
+            // ICollection<T> but not ICollection. (HashSet<T> does, for one...)
+
+            // Fall back to a slower path of adding items one at a time.
+            foreach (T item in values)
+            {
+                Add(item);
             }
-            EnsureSize(count + values.count);
-            // We know that all the values will be valid, because it's a RepeatedField.
-            Array.Copy(values.array, 0, array, count, values.count);
-            count += values.count;
         }
 
         /// <summary>
-        /// Adds all of the specified values into this collection.
+        /// Adds all of the specified values into this collection. This method is present to
+        /// allow repeated fields to be constructed from queries within collection initializers.
+        /// Within non-collection-initializer code, consider using the equivalent <see cref="AddRange"/>
+        /// method instead for clarity.
         /// </summary>
         /// <param name="values">The values to add to this collection.</param>
         public void Add(IEnumerable<T> values)
         {
-            if (values == null)
-            {
-                throw new ArgumentNullException("values");
-            }
-            // TODO: Check for ICollection and get the Count, to optimize?
-            foreach (T item in values)
-            {
-                Add(item);
-            }
+            AddRange(values);
         }
 
         /// <summary>
@@ -418,10 +450,7 @@ namespace Google.Protobuf.Collections
         /// <returns>The zero-based index of the item, or -1 if it is not found.</returns>
         public int IndexOf(T item)
         {
-            if (item == null)
-            {
-                throw new ArgumentNullException("item");
-            }
+            ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
             EqualityComparer<T> comparer = EqualityComparer<T>.Default;
             for (int i = 0; i < count; i++)
             {
@@ -440,13 +469,10 @@ namespace Google.Protobuf.Collections
         /// <param name="item">The item to insert.</param>
         public void Insert(int index, T item)
         {
-            if (item == null)
-            {
-                throw new ArgumentNullException("item");
-            }
+            ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
             if (index < 0 || index > count)
             {
-                throw new ArgumentOutOfRangeException("index");
+                throw new ArgumentOutOfRangeException(nameof(index));
             }
             EnsureSize(count + 1);
             Array.Copy(array, index, array, index + 1, count - index);
@@ -462,7 +488,7 @@ namespace Google.Protobuf.Collections
         {
             if (index < 0 || index >= count)
             {
-                throw new ArgumentOutOfRangeException("index");
+                throw new ArgumentOutOfRangeException(nameof(index));
             }
             Array.Copy(array, index + 1, array, index, count - index - 1);
             count--;
@@ -494,7 +520,7 @@ namespace Google.Protobuf.Collections
             {
                 if (index < 0 || index >= count)
                 {
-                    throw new ArgumentOutOfRangeException("index");
+                    throw new ArgumentOutOfRangeException(nameof(index));
                 }
                 return array[index];
             }
@@ -502,27 +528,24 @@ namespace Google.Protobuf.Collections
             {
                 if (index < 0 || index >= count)
                 {
-                    throw new ArgumentOutOfRangeException("index");
-                }
-                if (value == null)
-                {
-                    throw new ArgumentNullException("value");
+                    throw new ArgumentOutOfRangeException(nameof(index));
                 }
+                ProtoPreconditions.CheckNotNullUnconstrained(value, nameof(value));
                 array[index] = value;
             }
         }
 
         #region Explicit interface implementation for IList and ICollection.
-        bool IList.IsFixedSize { get { return false; } }
+        bool IList.IsFixedSize => false;
 
         void ICollection.CopyTo(Array array, int index)
         {
             Array.Copy(this.array, 0, array, index, count);
         }
 
-        bool ICollection.IsSynchronized { get { return false; } }
+        bool ICollection.IsSynchronized => false;
 
-        object ICollection.SyncRoot { get { return this; } }
+        object ICollection.SyncRoot => this;
 
         object IList.this[int index]
         {