blob: 084374ff5f04ad348030e0d9d5c3727a8b90cf58 [file] [log] [blame]
#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.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using Google.Protobuf.Reflection;
using Google.Protobuf.WellKnownTypes;
namespace Google.Protobuf
{
/// <summary>
/// <para>A tree representation of a FieldMask. Each leaf node in this tree represent
/// a field path in the FieldMask.</para>
///
/// <para>For example, FieldMask "foo.bar,foo.baz,bar.baz" as a tree will be:</para>
/// <code>
/// [root] -+- foo -+- bar
/// | |
/// | +- baz
/// |
/// +- bar --- baz
/// </code>
///
/// <para>By representing FieldMasks with this tree structure we can easily convert
/// a FieldMask to a canonical form, merge two FieldMasks, calculate the
/// intersection to two FieldMasks and traverse all fields specified by the
/// FieldMask in a message tree.</para>
/// </summary>
internal sealed class FieldMaskTree
{
private const char FIELD_PATH_SEPARATOR = '.';
internal sealed class Node
{
public Dictionary<string, Node> Children { get; } = new Dictionary<string, Node>();
}
private readonly Node root = new Node();
/// <summary>
/// Creates an empty FieldMaskTree.
/// </summary>
public FieldMaskTree()
{
}
/// <summary>
/// Creates a FieldMaskTree for a given FieldMask.
/// </summary>
public FieldMaskTree(FieldMask mask)
{
MergeFromFieldMask(mask);
}
public override string ToString()
{
return ToFieldMask().ToString();
}
/// <summary>
/// Adds a field path to the tree. In a FieldMask, every field path matches the
/// specified field as well as all its sub-fields. For example, a field path
/// "foo.bar" matches field "foo.bar" and also "foo.bar.baz", etc. When adding
/// a field path to the tree, redundant sub-paths will be removed. That is,
/// after adding "foo.bar" to the tree, "foo.bar.baz" will be removed if it
/// exists, which will turn the tree node for "foo.bar" to a leaf node.
/// Likewise, if the field path to add is a sub-path of an existing leaf node,
/// nothing will be changed in the tree.
/// </summary>
public FieldMaskTree AddFieldPath(string path)
{
var parts = path.Split(FIELD_PATH_SEPARATOR);
if (parts.Length == 0)
{
return this;
}
var node = root;
var createNewBranch = false;
// Find the matching node in the tree.
foreach (var part in parts)
{
// Check whether the path matches an existing leaf node.
if (!createNewBranch
&& node != root
&& node.Children.Count == 0)
{
// The path to add is a sub-path of an existing leaf node.
return this;
}
if (!node.Children.TryGetValue(part, out Node childNode))
{
createNewBranch = true;
childNode = new Node();
node.Children.Add(part, childNode);
}
node = childNode;
}
// Turn the matching node into a leaf node (i.e., remove sub-paths).
node.Children.Clear();
return this;
}
/// <summary>
/// Merges all field paths in a FieldMask into this tree.
/// </summary>
public FieldMaskTree MergeFromFieldMask(FieldMask mask)
{
foreach (var path in mask.Paths)
{
AddFieldPath(path);
}
return this;
}
/// <summary>
/// Converts this tree to a FieldMask.
/// </summary>
public FieldMask ToFieldMask()
{
var mask = new FieldMask();
if (root.Children.Count != 0)
{
var paths = new List<string>();
GetFieldPaths(root, "", paths);
mask.Paths.AddRange(paths);
}
return mask;
}
/// <summary>
/// Gathers all field paths in a sub-tree.
/// </summary>
private void GetFieldPaths(Node node, string path, List<string> paths)
{
if (node.Children.Count == 0)
{
paths.Add(path);
return;
}
foreach (var entry in node.Children)
{
var childPath = path.Length == 0 ? entry.Key : path + "." + entry.Key;
GetFieldPaths(entry.Value, childPath, paths);
}
}
/// <summary>
/// Adds the intersection of this tree with the given <paramref name="path"/> to <paramref name="output"/>.
/// </summary>
public void IntersectFieldPath(string path, FieldMaskTree output)
{
if (root.Children.Count == 0)
{
return;
}
var parts = path.Split(FIELD_PATH_SEPARATOR);
if (parts.Length == 0)
{
return;
}
var node = root;
foreach (var part in parts)
{
if (node != root
&& node.Children.Count == 0)
{
// The given path is a sub-path of an existing leaf node in the tree.
output.AddFieldPath(path);
return;
}
if (!node.Children.TryGetValue(part, out node))
{
return;
}
}
// We found a matching node for the path. All leaf children of this matching
// node is in the intersection.
var paths = new List<string>();
GetFieldPaths(node, path, paths);
foreach (var value in paths)
{
output.AddFieldPath(value);
}
}
/// <summary>
/// Merges all fields specified by this FieldMaskTree from <paramref name="source"/> to <paramref name="destination"/>.
/// </summary>
public void Merge(IMessage source, IMessage destination, FieldMask.MergeOptions options)
{
if (source.Descriptor != destination.Descriptor)
{
throw new InvalidProtocolBufferException("Cannot merge messages of different types.");
}
if (root.Children.Count == 0)
{
return;
}
Merge(root, "", source, destination, options);
}
/// <summary>
/// Merges all fields specified by a sub-tree from <paramref name="source"/> to <paramref name="destination"/>.
/// </summary>
private void Merge(
Node node,
string path,
IMessage source,
IMessage destination,
FieldMask.MergeOptions options)
{
if (source.Descriptor != destination.Descriptor)
{
throw new InvalidProtocolBufferException($"source ({source.Descriptor}) and destination ({destination.Descriptor}) descriptor must be equal");
}
var descriptor = source.Descriptor;
foreach (var entry in node.Children)
{
var field = descriptor.FindFieldByName(entry.Key);
if (field == null)
{
Debug.WriteLine($"Cannot find field \"{entry.Key}\" in message type \"{descriptor.FullName}\"");
continue;
}
if (entry.Value.Children.Count != 0)
{
if (field.IsRepeated
|| field.FieldType != FieldType.Message)
{
Debug.WriteLine($"Field \"{field.FullName}\" is not a singular message field and cannot have sub-fields.");
continue;
}
var sourceField = field.Accessor.GetValue(source);
var destinationField = field.Accessor.GetValue(destination);
if (sourceField == null
&& destinationField == null)
{
// If the message field is not present in both source and destination, skip recursing
// so we don't create unnecessary empty messages.
continue;
}
if (destinationField == null)
{
// If we have to merge but the destination does not contain the field, create it.
destinationField = field.MessageType.Parser.CreateTemplate();
field.Accessor.SetValue(destination, destinationField);
}
var childPath = path.Length == 0 ? entry.Key : path + "." + entry.Key;
Merge(entry.Value, childPath, (IMessage)sourceField, (IMessage)destinationField, options);
continue;
}
if (field.IsRepeated)
{
if (options.ReplaceRepeatedFields)
{
field.Accessor.Clear(destination);
}
var sourceField = (IList)field.Accessor.GetValue(source);
var destinationField = (IList)field.Accessor.GetValue(destination);
foreach (var element in sourceField)
{
destinationField.Add(element);
}
}
else
{
var sourceField = field.Accessor.GetValue(source);
if (field.FieldType == FieldType.Message)
{
if (options.ReplaceMessageFields)
{
if (sourceField == null)
{
field.Accessor.Clear(destination);
}
else
{
field.Accessor.SetValue(destination, sourceField);
}
}
else
{
if (sourceField != null)
{
// Well-known wrapper types are represented as nullable primitive types, so we do not "merge" them.
// Instead, any non-null value just overwrites the previous value directly.
if (field.MessageType.IsWrapperType)
{
field.Accessor.SetValue(destination, sourceField);
}
else
{
var sourceByteString = ((IMessage)sourceField).ToByteString();
var destinationValue = (IMessage)field.Accessor.GetValue(destination);
if (destinationValue != null)
{
destinationValue.MergeFrom(sourceByteString);
}
else
{
field.Accessor.SetValue(destination, field.MessageType.Parser.ParseFrom(sourceByteString));
}
}
}
}
}
else
{
if (sourceField != null
|| !options.ReplacePrimitiveFields)
{
field.Accessor.SetValue(destination, sourceField);
}
else
{
field.Accessor.Clear(destination);
}
}
}
}
}
}
}