First pass at map support.

More tests required. Generated code in next commit.

1 files changed, 400 insertions, 0 deletions

diff --git a/csharp/src/ProtocolBuffers/Collections/MapField.cs b/csharp/src/ProtocolBuffers/Collections/MapField.cs
new file mode 100644
index 00000000..2f5a741d
--- /dev/null
+++ b/csharp/src/ProtocolBuffers/Collections/MapField.cs
@@ -0,0 +1,400 @@
+#region Copyright notice and license
+// Protocol Buffers - Google's data interchange format
+// Copyright 2015 Google Inc.  All rights reserved.
+// https://developers.google.com/protocol-buffers/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+#endregion
+
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace Google.Protobuf.Collections
+{
+    /// <summary>
+    /// Representation of a map field in a Protocol Buffer message.
+    /// </summary>
+    /// <remarks>
+    /// This implementation preserves insertion order for simplicity of testing
+    /// code using maps fields. Overwriting an existing entry does not change the
+    /// position of that entry within the map. Equality is not order-sensitive.
+    /// For string keys, the equality comparison is provided by <see cref="StringComparer.Ordinal"/>.
+    /// </remarks>
+    /// <typeparam name="TKey">Key type in the map. Must be a type supported by Protocol Buffer map keys.</typeparam>
+    /// <typeparam name="TValue">Value type in the map. Must be a type supported by Protocol Buffers.</typeparam>
+    public sealed class MapField<TKey, TValue> : IDeepCloneable<MapField<TKey, TValue>>, IFreezable, IDictionary<TKey, TValue>, IEquatable<MapField<TKey, TValue>>
+    {
+        // TODO: Don't create the map/list until we have an entry. (Assume many maps will be empty.)
+        private bool frozen;
+        private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> map =
+            new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();
+        private readonly LinkedList<KeyValuePair<TKey, TValue>> list = new LinkedList<KeyValuePair<TKey, TValue>>();
+
+        public MapField<TKey, TValue> Clone()
+        {
+            var clone = new MapField<TKey, TValue>();
+            // Keys are never cloneable. Values might be.
+            if (typeof(IDeepCloneable<TValue>).IsAssignableFrom(typeof(TValue)))
+            {
+                foreach (var pair in list)
+                {
+                    clone.Add(pair.Key, pair.Value == null ? pair.Value : ((IDeepCloneable<TValue>) pair.Value).Clone());
+                }
+            }
+            else
+            {
+                // Nothing is cloneable, so we don't need to worry.
+                clone.Add(this);
+            }
+            return clone;
+        }
+
+        public void Add(TKey key, TValue value)
+        {
+            ThrowHelper.ThrowIfNull(key, "key");
+            this.CheckMutable();
+            if (ContainsKey(key))
+            {
+                throw new ArgumentException("Key already exists in map", "key");
+            }
+            this[key] = value;
+        }
+
+        public bool ContainsKey(TKey key)
+        {
+            return map.ContainsKey(key);
+        }
+
+        public bool Remove(TKey key)
+        {
+            this.CheckMutable();
+            LinkedListNode<KeyValuePair<TKey, TValue>> node;
+            if (map.TryGetValue(key, out node))
+            {
+                map.Remove(key);
+                node.List.Remove(node);
+                return true;
+            }
+            else
+            {
+                return false;
+            }
+        }
+
+        public bool TryGetValue(TKey key, out TValue value)
+        {
+            LinkedListNode<KeyValuePair<TKey, TValue>> node;
+            if (map.TryGetValue(key, out node))
+            {
+                value = node.Value.Value;
+                return true;
+            }
+            else
+            {
+                value = default(TValue);
+                return false;
+            }
+        }
+
+        public TValue this[TKey key]
+        {
+            get
+            {
+                TValue value;
+                if (TryGetValue(key, out value))
+                {
+                    return value;
+                }
+                throw new KeyNotFoundException();
+            }
+            set
+            {
+                this.CheckMutable();
+                LinkedListNode<KeyValuePair<TKey, TValue>> node;
+                var pair = new KeyValuePair<TKey, TValue>(key, value);
+                if (map.TryGetValue(key, out node))
+                {
+                    node.Value = pair;
+                }
+                else
+                {
+                    node = list.AddLast(pair);
+                    map[key] = node;
+                }
+            }
+        }
+
+        // TODO: Make these views?
+        public ICollection<TKey> Keys { get { return list.Select(t => t.Key).ToList(); } }
+        public ICollection<TValue> Values { get { return list.Select(t => t.Value).ToList(); } }
+
+        public void Add(IDictionary<TKey, TValue> entries)
+        {
+            foreach (var pair in entries)
+            {
+                Add(pair);
+            }
+        }
+
+        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
+        {
+            return list.GetEnumerator();
+        }
+
+        IEnumerator IEnumerable.GetEnumerator()
+        {
+            return GetEnumerator();
+        }
+
+        public void Add(KeyValuePair<TKey, TValue> item)
+        {
+            this.CheckMutable();
+            Add(item.Key, item.Value);
+        }
+
+        public void Clear()
+        {
+            this.CheckMutable();
+            list.Clear();
+            map.Clear();
+        }
+
+        public bool Contains(KeyValuePair<TKey, TValue> item)
+        {
+            TValue value;
+            return TryGetValue(item.Key, out value)
+                && EqualityComparer<TValue>.Default.Equals(item.Value, value);
+        }
+
+        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
+        {
+            list.CopyTo(array, arrayIndex);
+        }
+
+        public bool Remove(KeyValuePair<TKey, TValue> item)
+        {
+            this.CheckMutable();
+            return Remove(item.Key);
+        }
+
+        public int Count { get { return list.Count; } }
+        public bool IsReadOnly { get { return frozen; } }
+
+        public void Freeze()
+        {
+            if (IsFrozen)
+            {
+                return;
+            }
+            frozen = true;
+            // Only values can be frozen, as all the key types are simple.
+            // Everything can be done in-place, as we're just freezing objects.
+            if (typeof(IFreezable).IsAssignableFrom(typeof(TValue)))
+            {
+                for (var node = list.First; node != null; node = node.Next)
+                {
+                    var pair = node.Value;
+                    IFreezable freezableValue = pair.Value as IFreezable;
+                    if (freezableValue != null)
+                    {
+                        freezableValue.Freeze();
+                    }
+                }
+            }
+        }
+
+        public bool IsFrozen { get { return frozen; } }
+
+        public override bool Equals(object other)
+        {
+            return Equals(other as MapField<TKey, TValue>);
+        }
+
+        public override int GetHashCode()
+        {
+            var valueComparer = EqualityComparer<TValue>.Default;
+            int hash = 0;
+            foreach (var pair in list)
+            {
+                hash ^= pair.Key.GetHashCode() * 31 + valueComparer.GetHashCode(pair.Value);
+            }
+            return hash;
+        }
+
+        public bool Equals(MapField<TKey, TValue> other)
+        {
+            if (other == null)
+            {
+                return false;
+            }
+            if (other == this)
+            {
+                return true;
+            }
+            if (other.Count != this.Count)
+            {
+                return false;
+            }
+            var valueComparer = EqualityComparer<TValue>.Default;
+            foreach (var pair in this)
+            {
+                TValue value;
+                if (!other.TryGetValue(pair.Key, out value))
+                {
+                    return false;
+                }
+                if (!valueComparer.Equals(value, pair.Value))
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        public void AddEntriesFrom(CodedInputStream input, Codec codec)            
+        {
+            // TODO: Peek at the next tag and see if it's the same. If it is, we can reuse the entry object...
+            var adapter = new Codec.MessageAdapter(codec);
+            adapter.Reset();
+            input.ReadMessage(adapter);
+            this[adapter.Key] = adapter.Value;
+        }
+
+        public void WriteTo(CodedOutputStream output, Codec codec)
+        {
+            var message = new Codec.MessageAdapter(codec);
+            foreach (var entry in list)
+            {
+                message.Key = entry.Key;
+                message.Value = entry.Value;
+                output.WriteTag(codec.MapTag);
+                output.WriteMessage(message);
+            }
+        }
+
+        public int CalculateSize(Codec codec)
+        {
+            var message = new Codec.MessageAdapter(codec);
+            int size = 0;
+            foreach (var entry in list)
+            {
+                message.Key = entry.Key;
+                message.Value = entry.Value;
+                size += CodedOutputStream.ComputeRawVarint32Size(codec.MapTag);
+                size += CodedOutputStream.ComputeMessageSize(message);
+            }
+            return size;
+        }
+
+        /// <summary>
+        /// A codec for a specific map field. This contains all the information required to encoded and
+        /// decode the nested messages.
+        /// </summary>
+        public sealed class Codec
+        {
+            private readonly FieldCodec<TKey> keyCodec;
+            private readonly FieldCodec<TValue> valueCodec;
+            private readonly uint mapTag;
+
+            public Codec(FieldCodec<TKey> keyCodec, FieldCodec<TValue> valueCodec, uint mapTag)
+            {
+                this.keyCodec = keyCodec;
+                this.valueCodec = valueCodec;
+                this.mapTag = mapTag;
+            }
+
+            /// <summary>
+            /// The tag used in the enclosing message to indicate map entries.
+            /// </summary>
+            internal uint MapTag { get { return mapTag; } }
+
+            /// <summary>
+            /// A mutable message class, used for parsing and serializing. This
+            /// delegates the work to a codec, but implements the <see cref="IMessage"/> interface
+            /// for interop with <see cref="CodedInputStream"/> and <see cref="CodedOutputStream"/>.
+            /// This is nested inside Codec as it's tightly coupled to the associated codec,
+            /// and it's simpler if it has direct access to all its fields.
+            /// </summary>
+            internal class MessageAdapter : IMessage
+            {
+                private readonly Codec codec;
+                internal TKey Key { get; set; }
+                internal TValue Value { get; set; }
+                internal int Size { get; set; }
+
+                internal MessageAdapter(Codec codec)
+                {
+                    this.codec = codec;
+                }
+
+                internal void Reset()
+                {
+                    Key = codec.keyCodec.DefaultValue;
+                    Value = codec.valueCodec.DefaultValue;
+                }
+
+                public void MergeFrom(CodedInputStream input)
+                {
+                    uint tag;
+                    while (input.ReadTag(out tag))
+                    {
+                        if (tag == 0)
+                        {
+                            throw InvalidProtocolBufferException.InvalidTag();
+                        }
+                        if (tag == codec.keyCodec.Tag)
+                        {
+                            Key = codec.keyCodec.Read(input);
+                        }
+                        else if (tag == codec.valueCodec.Tag)
+                        {
+                            Value = codec.valueCodec.Read(input);
+                        }
+                        else if (WireFormat.IsEndGroupTag(tag))
+                        {
+                            // TODO(jonskeet): Do we need this? (Given that we don't support groups...)
+                            return;
+                        }
+                    }
+                }
+
+                public void WriteTo(CodedOutputStream output)
+                {
+                    codec.keyCodec.Write(output, Key);
+                    codec.valueCodec.Write(output, Value);
+                }
+
+                public int CalculateSize()
+                {
+                    return codec.keyCodec.CalculateSize(Key) + codec.valueCodec.CalculateSize(Value);
+                }
+            }
+        }
+    }
+}