1// Protocol Buffers - Google's data interchange format
2// Copyright 2008 Google Inc.  All rights reserved.
3// https://developers.google.com/protocol-buffers/
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are
7// met:
8//
9//     * Redistributions of source code must retain the above copyright
10// notice, this list of conditions and the following disclaimer.
11//     * Redistributions in binary form must reproduce the above
12// copyright notice, this list of conditions and the following disclaimer
13// in the documentation and/or other materials provided with the
14// distribution.
15//     * Neither the name of Google Inc. nor the names of its
16// contributors may be used to endorse or promote products derived from
17// this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31package com.google.protobuf.util;
32
33import com.google.protobuf.Descriptors.Descriptor;
34import com.google.protobuf.Descriptors.FieldDescriptor;
35import com.google.protobuf.FieldMask;
36import com.google.protobuf.Message;
37
38import java.util.ArrayList;
39import java.util.List;
40import java.util.Map.Entry;
41import java.util.TreeMap;
42import java.util.logging.Logger;
43
44/**
45 * A tree representation of a FieldMask. Each leaf node in this tree represent
46 * a field path in the FieldMask.
47 *
48 * <p>For example, FieldMask "foo.bar,foo.baz,bar.baz" as a tree will be:
49 * <pre>
50 *   [root] -+- foo -+- bar
51 *           |       |
52 *           |       +- baz
53 *           |
54 *           +- bar --- baz
55 * </pre>
56 *
57 * <p>By representing FieldMasks with this tree structure we can easily convert
58 * a FieldMask to a canonical form, merge two FieldMasks, calculate the
59 * intersection to two FieldMasks and traverse all fields specified by the
60 * FieldMask in a message tree.
61 */
62class FieldMaskTree {
63  private static final Logger logger = Logger.getLogger(FieldMaskTree.class.getName());
64
65  private static final String FIELD_PATH_SEPARATOR_REGEX = "\\.";
66
67  private static class Node {
68    public TreeMap<String, Node> children = new TreeMap<String, Node>();
69  }
70
71  private final Node root = new Node();
72
73  /** Creates an empty FieldMaskTree. */
74  public FieldMaskTree() {}
75
76  /** Creates a FieldMaskTree for a given FieldMask. */
77  public FieldMaskTree(FieldMask mask) {
78    mergeFromFieldMask(mask);
79  }
80
81  @Override
82  public String toString() {
83    return FieldMaskUtil.toString(toFieldMask());
84  }
85
86  /**
87   * Adds a field path to the tree. In a FieldMask, every field path matches the
88   * specified field as well as all its sub-fields. For example, a field path
89   * "foo.bar" matches field "foo.bar" and also "foo.bar.baz", etc. When adding
90   * a field path to the tree, redundant sub-paths will be removed. That is,
91   * after adding "foo.bar" to the tree, "foo.bar.baz" will be removed if it
92   * exists, which will turn the tree node for "foo.bar" to a leaf node.
93   * Likewise, if the field path to add is a sub-path of an existing leaf node,
94   * nothing will be changed in the tree.
95   */
96  public FieldMaskTree addFieldPath(String path) {
97    String[] parts = path.split(FIELD_PATH_SEPARATOR_REGEX);
98    if (parts.length == 0) {
99      return this;
100    }
101    Node node = root;
102    boolean createNewBranch = false;
103    // Find the matching node in the tree.
104    for (String part : parts) {
105      // Check whether the path matches an existing leaf node.
106      if (!createNewBranch && node != root && node.children.isEmpty()) {
107        // The path to add is a sub-path of an existing leaf node.
108        return this;
109      }
110      if (node.children.containsKey(part)) {
111        node = node.children.get(part);
112      } else {
113        createNewBranch = true;
114        Node tmp = new Node();
115        node.children.put(part, tmp);
116        node = tmp;
117      }
118    }
119    // Turn the matching node into a leaf node (i.e., remove sub-paths).
120    node.children.clear();
121    return this;
122  }
123
124  /**
125   * Merges all field paths in a FieldMask into this tree.
126   */
127  public FieldMaskTree mergeFromFieldMask(FieldMask mask) {
128    for (String path : mask.getPathsList()) {
129      addFieldPath(path);
130    }
131    return this;
132  }
133
134  /** Converts this tree to a FieldMask. */
135  public FieldMask toFieldMask() {
136    if (root.children.isEmpty()) {
137      return FieldMask.getDefaultInstance();
138    }
139    List<String> paths = new ArrayList<String>();
140    getFieldPaths(root, "", paths);
141    return FieldMask.newBuilder().addAllPaths(paths).build();
142  }
143
144  /** Gathers all field paths in a sub-tree. */
145  private void getFieldPaths(Node node, String path, List<String> paths) {
146    if (node.children.isEmpty()) {
147      paths.add(path);
148      return;
149    }
150    for (Entry<String, Node> entry : node.children.entrySet()) {
151      String childPath = path.isEmpty() ? entry.getKey() : path + "." + entry.getKey();
152      getFieldPaths(entry.getValue(), childPath, paths);
153    }
154  }
155
156  /**
157   * Adds the intersection of this tree with the given {@code path} to
158   * {@code output}.
159   */
160  public void intersectFieldPath(String path, FieldMaskTree output) {
161    if (root.children.isEmpty()) {
162      return;
163    }
164    String[] parts = path.split(FIELD_PATH_SEPARATOR_REGEX);
165    if (parts.length == 0) {
166      return;
167    }
168    Node node = root;
169    for (String part : parts) {
170      if (node != root && node.children.isEmpty()) {
171        // The given path is a sub-path of an existing leaf node in the tree.
172        output.addFieldPath(path);
173        return;
174      }
175      if (node.children.containsKey(part)) {
176        node = node.children.get(part);
177      } else {
178        return;
179      }
180    }
181    // We found a matching node for the path. All leaf children of this matching
182    // node is in the intersection.
183    List<String> paths = new ArrayList<String>();
184    getFieldPaths(node, path, paths);
185    for (String value : paths) {
186      output.addFieldPath(value);
187    }
188  }
189
190  /**
191   * Merges all fields specified by this FieldMaskTree from {@code source} to
192   * {@code destination}.
193   */
194  public void merge(
195      Message source, Message.Builder destination, FieldMaskUtil.MergeOptions options) {
196    if (source.getDescriptorForType() != destination.getDescriptorForType()) {
197      throw new IllegalArgumentException("Cannot merge messages of different types.");
198    }
199    if (root.children.isEmpty()) {
200      return;
201    }
202    merge(root, "", source, destination, options);
203  }
204
205  /** Merges all fields specified by a sub-tree from {@code source} to
206   * {@code destination}.
207   */
208  private void merge(
209      Node node,
210      String path,
211      Message source,
212      Message.Builder destination,
213      FieldMaskUtil.MergeOptions options) {
214    assert source.getDescriptorForType() == destination.getDescriptorForType();
215
216    Descriptor descriptor = source.getDescriptorForType();
217    for (Entry<String, Node> entry : node.children.entrySet()) {
218      FieldDescriptor field = descriptor.findFieldByName(entry.getKey());
219      if (field == null) {
220        logger.warning(
221            "Cannot find field \""
222                + entry.getKey()
223                + "\" in message type "
224                + descriptor.getFullName());
225        continue;
226      }
227      if (!entry.getValue().children.isEmpty()) {
228        if (field.isRepeated() || field.getJavaType() != FieldDescriptor.JavaType.MESSAGE) {
229          logger.warning(
230              "Field \""
231                  + field.getFullName()
232                  + "\" is not a "
233                  + "singluar message field and cannot have sub-fields.");
234          continue;
235        }
236        String childPath = path.isEmpty() ? entry.getKey() : path + "." + entry.getKey();
237        merge(
238            entry.getValue(),
239            childPath,
240            (Message) source.getField(field),
241            destination.getFieldBuilder(field),
242            options);
243        continue;
244      }
245      if (field.isRepeated()) {
246        if (options.replaceRepeatedFields()) {
247          destination.setField(field, source.getField(field));
248        } else {
249          for (Object element : (List) source.getField(field)) {
250            destination.addRepeatedField(field, element);
251          }
252        }
253      } else {
254        if (field.getJavaType() == FieldDescriptor.JavaType.MESSAGE) {
255          if (options.replaceMessageFields()) {
256            if (!source.hasField(field)) {
257              destination.clearField(field);
258            } else {
259              destination.setField(field, source.getField(field));
260            }
261          } else {
262            if (source.hasField(field)) {
263              destination.getFieldBuilder(field).mergeFrom((Message) source.getField(field));
264            }
265          }
266        } else {
267          if (source.hasField(field) || !options.replacePrimitiveFields()) {
268            destination.setField(field, source.getField(field));
269          } else {
270            destination.clearField(field);
271          }
272        }
273      }
274    }
275  }
276}
277