#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 Google.Protobuf.Reflection;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using Google.Protobuf.Compatibility;
namespace Google.Protobuf.Collections
{
///
/// Representation of a map field in a Protocol Buffer message.
///
/// Key type in the map. Must be a type supported by Protocol Buffer map keys.
/// Value type in the map. Must be a type supported by Protocol Buffers.
///
/// 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 .
///
public sealed class MapField : IDeepCloneable>, IDictionary, IEquatable>, IDictionary
{
// TODO: Don't create the map/list until we have an entry. (Assume many maps will be empty.)
private readonly bool allowNullValues;
private readonly Dictionary>> map =
new Dictionary>>();
private readonly LinkedList> list = new LinkedList>();
///
/// Constructs a new map field, defaulting the value nullability to only allow null values for message types
/// and non-nullable value types.
///
public MapField() : this(typeof(IMessage).IsAssignableFrom(typeof(TValue)) || Nullable.GetUnderlyingType(typeof(TValue)) != null)
{
}
///
/// Constructs a new map field, overriding the choice of whether null values are permitted in the map.
/// This is used by wrapper types, where maps with string and bytes wrappers as the value types
/// support null values.
///
/// Whether null values are permitted in the map or not.
public MapField(bool allowNullValues)
{
if (allowNullValues && typeof(TValue).IsValueType() && Nullable.GetUnderlyingType(typeof(TValue)) == null)
{
throw new ArgumentException("allowNullValues", "Non-nullable value types do not support null values");
}
this.allowNullValues = allowNullValues;
}
///
/// Creates a deep clone of this object.
///
///
/// A deep clone of this object.
///
public MapField Clone()
{
var clone = new MapField(allowNullValues);
// Keys are never cloneable. Values might be.
if (typeof(IDeepCloneable).IsAssignableFrom(typeof(TValue)))
{
foreach (var pair in list)
{
clone.Add(pair.Key, pair.Value == null ? pair.Value : ((IDeepCloneable)pair.Value).Clone());
}
}
else
{
// Nothing is cloneable, so we don't need to worry.
clone.Add(this);
}
return clone;
}
///
/// Adds the specified key/value pair to the map.
///
///
/// This operation fails if the key already exists in the map. To replace an existing entry, use the indexer.
///
/// The key to add
/// The value to add.
/// The given key already exists in map.
public void Add(TKey key, TValue value)
{
// Validation of arguments happens in ContainsKey and the indexer
if (ContainsKey(key))
{
throw new ArgumentException("Key already exists in map", "key");
}
this[key] = value;
}
///
/// Determines whether the specified key is present in the map.
///
/// The key to check.
/// true if the map contains the given key; false otherwise.
public bool ContainsKey(TKey key)
{
Preconditions.CheckNotNullUnconstrained(key, "key");
return map.ContainsKey(key);
}
private bool ContainsValue(TValue value)
{
var comparer = EqualityComparer.Default;
return list.Any(pair => comparer.Equals(pair.Value, value));
}
///
/// Removes the entry identified by the given key from the map.
///
/// The key indicating the entry to remove from the map.
/// true if the map contained the given key before the entry was removed; false otherwise.
public bool Remove(TKey key)
{
Preconditions.CheckNotNullUnconstrained(key, "key");
LinkedListNode> node;
if (map.TryGetValue(key, out node))
{
map.Remove(key);
node.List.Remove(node);
return true;
}
else
{
return false;
}
}
///
/// Gets the value associated with the specified key.
///
/// The key whose value to get.
/// When this method returns, the value associated with the specified key, if the key is found;
/// otherwise, the default value for the type of the parameter.
/// This parameter is passed uninitialized.
/// true if the map contains an element with the specified key; otherwise, false.
public bool TryGetValue(TKey key, out TValue value)
{
LinkedListNode> node;
if (map.TryGetValue(key, out node))
{
value = node.Value.Value;
return true;
}
else
{
value = default(TValue);
return false;
}
}
///
/// Gets or sets the value associated with the specified key.
///
/// The key of the value to get or set.
/// The property is retrieved and key does not exist in the collection.
/// The value associated with the specified key. If the specified key is not found,
/// a get operation throws a , and a set operation creates a new element with the specified key.
public TValue this[TKey key]
{
get
{
Preconditions.CheckNotNullUnconstrained(key, "key");
TValue value;
if (TryGetValue(key, out value))
{
return value;
}
throw new KeyNotFoundException();
}
set
{
Preconditions.CheckNotNullUnconstrained(key, "key");
// value == null check here is redundant, but avoids boxing.
if (value == null && !allowNullValues)
{
Preconditions.CheckNotNullUnconstrained(value, "value");
}
LinkedListNode> node;
var pair = new KeyValuePair(key, value);
if (map.TryGetValue(key, out node))
{
node.Value = pair;
}
else
{
node = list.AddLast(pair);
map[key] = node;
}
}
}
///
/// Gets a collection containing the keys in the map.
///
public ICollection Keys { get { return new MapView(this, pair => pair.Key, ContainsKey); } }
///
/// Gets a collection containing the values in the map.
///
public ICollection Values { get { return new MapView(this, pair => pair.Value, ContainsValue); } }
///
/// Adds the specified entries to the map.
///
/// The entries to add to the map.
public void Add(IDictionary entries)
{
Preconditions.CheckNotNull(entries, "entries");
foreach (var pair in entries)
{
Add(pair.Key, pair.Value);
}
}
///
/// Returns an enumerator that iterates through the collection.
///
///
/// An enumerator that can be used to iterate through the collection.
///
public IEnumerator> GetEnumerator()
{
return list.GetEnumerator();
}
///
/// Returns an enumerator that iterates through a collection.
///
///
/// An object that can be used to iterate through the collection.
///
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
///
/// Adds the specified item to the map.
///
/// The item to add to the map.
void ICollection>.Add(KeyValuePair item)
{
Add(item.Key, item.Value);
}
///
/// Removes all items from the map.
///
public void Clear()
{
list.Clear();
map.Clear();
}
///
/// Determines whether map contains an entry equivalent to the given key/value pair.
///
/// The key/value pair to find.
///
bool ICollection>.Contains(KeyValuePair item)
{
TValue value;
return TryGetValue(item.Key, out value)
&& EqualityComparer.Default.Equals(item.Value, value);
}
///
/// Copies the key/value pairs in this map to an array.
///
/// The array to copy the entries into.
/// The index of the array at which to start copying values.
void ICollection>.CopyTo(KeyValuePair[] array, int arrayIndex)
{
list.CopyTo(array, arrayIndex);
}
///
/// Removes the specified key/value pair from the map.
///
/// Both the key and the value must be found for the entry to be removed.
/// The key/value pair to remove.
/// true if the key/value pair was found and removed; false otherwise.
bool ICollection>.Remove(KeyValuePair item)
{
if (item.Key == null)
{
throw new ArgumentException("Key is null", "item");
}
LinkedListNode> node;
if (map.TryGetValue(item.Key, out node) &&
EqualityComparer.Default.Equals(item.Value, node.Value.Value))
{
map.Remove(item.Key);
node.List.Remove(node);
return true;
}
else
{
return false;
}
}
///
/// Returns whether or not this map allows values to be null.
///
public bool AllowsNullValues { get { return allowNullValues; } }
///
/// Gets the number of elements contained in the map.
///
public int Count { get { return list.Count; } }
///
/// Gets a value indicating whether the map is read-only.
///
public bool IsReadOnly { get { return false; } }
///
/// Determines whether the specified , is equal to this instance.
///
/// The to compare with this instance.
///
/// true if the specified is equal to this instance; otherwise, false.
///
public override bool Equals(object other)
{
return Equals(other as MapField);
}
///
/// Returns a hash code for this instance.
///
///
/// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table.
///
public override int GetHashCode()
{
var valueComparer = EqualityComparer.Default;
int hash = 0;
foreach (var pair in list)
{
hash ^= pair.Key.GetHashCode() * 31 + valueComparer.GetHashCode(pair.Value);
}
return hash;
}
///
/// Compares this map with another for equality.
///
///
/// The order of the key/value pairs in the maps is not deemed significant in this comparison.
///
/// The map to compare this with.
/// true if refers to an equal map; false otherwise.
public bool Equals(MapField other)
{
if (other == null)
{
return false;
}
if (other == this)
{
return true;
}
if (other.Count != this.Count)
{
return false;
}
var valueComparer = EqualityComparer.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;
}
///
/// Adds entries to the map from the given stream.
///
///
/// It is assumed that the stream is initially positioned after the tag specified by the codec.
/// This method will continue reading entries from the stream until the end is reached, or
/// a different tag is encountered.
///
/// Stream to read from
/// Codec describing how the key/value pairs are encoded
public void AddEntriesFrom(CodedInputStream input, Codec codec)
{
var adapter = new Codec.MessageAdapter(codec);
do
{
adapter.Reset();
input.ReadMessage(adapter);
this[adapter.Key] = adapter.Value;
} while (input.MaybeConsumeTag(codec.MapTag));
}
///
/// Writes the contents of this map to the given coded output stream, using the specified codec
/// to encode each entry.
///
/// The output stream to write to.
/// The codec to use for each entry.
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);
}
}
///
/// Calculates the size of this map based on the given entry codec.
///
/// The codec to use to encode each entry.
///
public int CalculateSize(Codec codec)
{
if (Count == 0)
{
return 0;
}
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;
}
#region IDictionary explicit interface implementation
void IDictionary.Add(object key, object value)
{
Add((TKey)key, (TValue)value);
}
bool IDictionary.Contains(object key)
{
if (!(key is TKey))
{
return false;
}
return ContainsKey((TKey)key);
}
IDictionaryEnumerator IDictionary.GetEnumerator()
{
return new DictionaryEnumerator(GetEnumerator());
}
void IDictionary.Remove(object key)
{
Preconditions.CheckNotNull(key, "key");
if (!(key is TKey))
{
return;
}
Remove((TKey)key);
}
void ICollection.CopyTo(Array array, int index)
{
// This is ugly and slow as heck, but with any luck it will never be used anyway.
ICollection temp = this.Select(pair => new DictionaryEntry(pair.Key, pair.Value)).ToList();
temp.CopyTo(array, index);
}
bool IDictionary.IsFixedSize { get { return false; } }
ICollection IDictionary.Keys { get { return (ICollection)Keys; } }
ICollection IDictionary.Values { get { return (ICollection)Values; } }
bool ICollection.IsSynchronized { get { return false; } }
object ICollection.SyncRoot { get { return this; } }
object IDictionary.this[object key]
{
get
{
Preconditions.CheckNotNull(key, "key");
if (!(key is TKey))
{
return null;
}
TValue value;
TryGetValue((TKey)key, out value);
return value;
}
set
{
this[(TKey)key] = (TValue)value;
}
}
#endregion
private class DictionaryEnumerator : IDictionaryEnumerator
{
private readonly IEnumerator> enumerator;
internal DictionaryEnumerator(IEnumerator> enumerator)
{
this.enumerator = enumerator;
}
public bool MoveNext()
{
return enumerator.MoveNext();
}
public void Reset()
{
enumerator.Reset();
}
public object Current { get { return Entry; } }
public DictionaryEntry Entry { get { return new DictionaryEntry(Key, Value); } }
public object Key { get { return enumerator.Current.Key; } }
public object Value { get { return enumerator.Current.Value; } }
}
///
/// A codec for a specific map field. This contains all the information required to encode and
/// decode the nested messages.
///
public sealed class Codec
{
private readonly FieldCodec keyCodec;
private readonly FieldCodec valueCodec;
private readonly uint mapTag;
///
/// Creates a new entry codec based on a separate key codec and value codec,
/// and the tag to use for each map entry.
///
/// The key codec.
/// The value codec.
/// The map tag to use to introduce each map entry.
public Codec(FieldCodec keyCodec, FieldCodec valueCodec, uint mapTag)
{
this.keyCodec = keyCodec;
this.valueCodec = valueCodec;
this.mapTag = mapTag;
}
///
/// The tag used in the enclosing message to indicate map entries.
///
internal uint MapTag { get { return mapTag; } }
///
/// A mutable message class, used for parsing and serializing. This
/// delegates the work to a codec, but implements the interface
/// for interop with and .
/// 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.
///
internal class MessageAdapter : IMessage
{
private readonly Codec codec;
internal TKey Key { get; set; }
internal TValue Value { 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 ((tag = input.ReadTag()) != 0)
{
if (tag == codec.keyCodec.Tag)
{
Key = codec.keyCodec.Read(input);
}
else if (tag == codec.valueCodec.Tag)
{
Value = codec.valueCodec.Read(input);
}
else
{
input.SkipLastField();
}
}
}
public void WriteTo(CodedOutputStream output)
{
codec.keyCodec.WriteTagAndValue(output, Key);
codec.valueCodec.WriteTagAndValue(output, Value);
}
public int CalculateSize()
{
return codec.keyCodec.CalculateSizeWithTag(Key) + codec.valueCodec.CalculateSizeWithTag(Value);
}
MessageDescriptor IMessage.Descriptor { get { return null; } }
}
}
private class MapView : ICollection, ICollection
{
private readonly MapField parent;
private readonly Func, T> projection;
private readonly Func containsCheck;
internal MapView(
MapField parent,
Func, T> projection,
Func containsCheck)
{
this.parent = parent;
this.projection = projection;
this.containsCheck = containsCheck;
}
public int Count { get { return parent.Count; } }
public bool IsReadOnly { get { return true; } }
public bool IsSynchronized { get { return false; } }
public object SyncRoot { get { return parent; } }
public void Add(T item)
{
throw new NotSupportedException();
}
public void Clear()
{
throw new NotSupportedException();
}
public bool Contains(T item)
{
return containsCheck(item);
}
public void CopyTo(T[] array, int arrayIndex)
{
if (arrayIndex < 0)
{
throw new ArgumentOutOfRangeException("arrayIndex");
}
if (arrayIndex + Count >= array.Length)
{
throw new ArgumentException("Not enough space in the array", "array");
}
foreach (var item in this)
{
array[arrayIndex++] = item;
}
}
public IEnumerator GetEnumerator()
{
return parent.list.Select(projection).GetEnumerator();
}
public bool Remove(T item)
{
throw new NotSupportedException();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public void CopyTo(Array array, int index)
{
throw new NotImplementedException();
}
}
}
}