content: /* Copyright (C) 2016-2018 Alibaba Group Holding Limited
  
  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at
  
      http://www.apache.org/licenses/LICENSE-2.0
  
  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the specific language governing permissions and
  limitations under the License.
  ==============================================================================*/
  
  // 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 unneccessary 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);
            }
          }
        }
      }
    }
  }
  