content: // Protocol Buffers - Google's data interchange format
  // Copyright 2008 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.
  
  package com.google.protobuf.util;
  
  import com.google.protobuf.Descriptors.Descriptor;
  import com.google.protobuf.Descriptors.FieldDescriptor;
  import com.google.protobuf.FieldMask;
  import com.google.protobuf.Message;
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Map.Entry;
  import java.util.SortedMap;
  import java.util.TreeMap;
  import java.util.logging.Logger;
  
  /**
   * A tree representation of a FieldMask. Each leaf node in this tree represent
   * a field path in the FieldMask.
   *
   * <p>For example, FieldMask "foo.bar,foo.baz,bar.baz" as a tree will be:
   * <pre>
   *   [root] -+- foo -+- bar
   *           |       |
   *           |       +- baz
   *           |
   *           +- bar --- baz
   * </pre>
   *
   * <p>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.
   */
  final class FieldMaskTree {
    private static final Logger logger = Logger.getLogger(FieldMaskTree.class.getName());
  
    private static final String FIELD_PATH_SEPARATOR_REGEX = "\\.";
  
    private static final class Node {
      final SortedMap<String, Node> children = new TreeMap<String, Node>();
    }
  
    private final Node root = new Node();
  
    /**
     * Creates an empty FieldMaskTree.
     */
    FieldMaskTree() {}
  
    /**
     * Creates a FieldMaskTree for a given FieldMask.
     */
    FieldMaskTree(FieldMask mask) {
      mergeFromFieldMask(mask);
    }
  
    @Override
    public String toString() {
      return FieldMaskUtil.toString(toFieldMask());
    }
  
    /**
     * 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.
     */
    FieldMaskTree addFieldPath(String path) {
      String[] parts = path.split(FIELD_PATH_SEPARATOR_REGEX);
      if (parts.length == 0) {
        return this;
      }
      Node node = root;
      boolean createNewBranch = false;
      // Find the matching node in the tree.
      for (String part : parts) {
        // Check whether the path matches an existing leaf node.
        if (!createNewBranch && node != root && node.children.isEmpty()) {
          // The path to add is a sub-path of an existing leaf node.
          return this;
        }
        if (node.children.containsKey(part)) {
          node = node.children.get(part);
        } else {
          createNewBranch = true;
          Node tmp = new Node();
          node.children.put(part, tmp);
          node = tmp;
        }
      }
      // Turn the matching node into a leaf node (i.e., remove sub-paths).
      node.children.clear();
      return this;
    }
  
    /**
     * Merges all field paths in a FieldMask into this tree.
     */
    FieldMaskTree mergeFromFieldMask(FieldMask mask) {
      for (String path : mask.getPathsList()) {
        addFieldPath(path);
      }
      return this;
    }
  
    /**
     * Converts this tree to a FieldMask.
     */
    FieldMask toFieldMask() {
      if (root.children.isEmpty()) {
        return FieldMask.getDefaultInstance();
      }
      List<String> paths = new ArrayList<String>();
      getFieldPaths(root, "", paths);
      return FieldMask.newBuilder().addAllPaths(paths).build();
    }
  
    /**
     * Gathers all field paths in a sub-tree.
     */
    private void getFieldPaths(Node node, String path, List<String> paths) {
      if (node.children.isEmpty()) {
        paths.add(path);
        return;
      }
      for (Entry<String, Node> entry : node.children.entrySet()) {
        String childPath = path.isEmpty() ? entry.getKey() : path + "." + entry.getKey();
        getFieldPaths(entry.getValue(), childPath, paths);
      }
    }
  
    /**
     * Adds the intersection of this tree with the given {@code path} to {@code output}.
     */
    void intersectFieldPath(String path, FieldMaskTree output) {
      if (root.children.isEmpty()) {
        return;
      }
      String[] parts = path.split(FIELD_PATH_SEPARATOR_REGEX);
      if (parts.length == 0) {
        return;
      }
      Node node = root;
      for (String part : parts) {
        if (node != root && node.children.isEmpty()) {
          // The given path is a sub-path of an existing leaf node in the tree.
          output.addFieldPath(path);
          return;
        }
        if (node.children.containsKey(part)) {
          node = node.children.get(part);
        } else {
          return;
        }
      }
      // We found a matching node for the path. All leaf children of this matching
      // node is in the intersection.
      List<String> paths = new ArrayList<String>();
      getFieldPaths(node, path, paths);
      for (String value : paths) {
        output.addFieldPath(value);
      }
    }
  
    /**
     * Merges all fields specified by this FieldMaskTree from {@code source} to {@code destination}.
     */
    void merge(Message source, Message.Builder destination, FieldMaskUtil.MergeOptions options) {
      if (source.getDescriptorForType() != destination.getDescriptorForType()) {
        throw new IllegalArgumentException("Cannot merge messages of different types.");
      }
      if (root.children.isEmpty()) {
        return;
      }
      merge(root, "", source, destination, options);
    }
  
    /**
     * Merges all fields specified by a sub-tree from {@code source} to {@code destination}.
     */
    private void merge(
        Node node,
        String path,
        Message source,
        Message.Builder destination,
        FieldMaskUtil.MergeOptions options) {
      if (source.getDescriptorForType() != destination.getDescriptorForType()) {
        throw new IllegalArgumentException(
            String.format(
                "source (%s) and destination (%s) descriptor must be equal",
                source.getDescriptorForType(), destination.getDescriptorForType()));
      }
  
      Descriptor descriptor = source.getDescriptorForType();
      for (Entry<String, Node> entry : node.children.entrySet()) {
        FieldDescriptor field = descriptor.findFieldByName(entry.getKey());
        if (field == null) {
          logger.warning(
              "Cannot find field \""
                  + entry.getKey()
                  + "\" in message type "
                  + descriptor.getFullName());
          continue;
        }
        if (!entry.getValue().children.isEmpty()) {
          if (field.isRepeated() || field.getJavaType() != FieldDescriptor.JavaType.MESSAGE) {
            logger.warning(
                "Field \""
                    + field.getFullName()
                    + "\" is not a "
                    + "singluar message field and cannot have sub-fields.");
            continue;
          }
          if (!source.hasField(field) && !destination.hasField(field)) {
            // If the message field is not present in both source and destination, skip recursing
            // so we don't create unnecessary empty messages.
            continue;
          }
          String childPath = path.isEmpty() ? entry.getKey() : path + "." + entry.getKey();
          merge(
              entry.getValue(),
              childPath,
              (Message) source.getField(field),
              destination.getFieldBuilder(field),
              options);
          continue;
        }
        if (field.isRepeated()) {
          if (options.replaceRepeatedFields()) {
            destination.setField(field, source.getField(field));
          } else {
            for (Object element : (List) source.getField(field)) {
              destination.addRepeatedField(field, element);
            }
          }
        } else {
          if (field.getJavaType() == FieldDescriptor.JavaType.MESSAGE) {
            if (options.replaceMessageFields()) {
              if (!source.hasField(field)) {
                destination.clearField(field);
              } else {
                destination.setField(field, source.getField(field));
              }
            } else {
              if (source.hasField(field)) {
                destination.getFieldBuilder(field).mergeFrom((Message) source.getField(field));
              }
            }
          } else {
            if (source.hasField(field) || !options.replacePrimitiveFields()) {
              destination.setField(field, source.getField(field));
            } else {
              destination.clearField(field);
            }
          }
        }
      }
    }
  }
  