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 
31 package com.google.protobuf.util;
32 
33 import com.google.protobuf.Descriptors.Descriptor;
34 import com.google.protobuf.Descriptors.FieldDescriptor;
35 import com.google.protobuf.FieldMask;
36 import com.google.protobuf.Message;
37 
38 import java.util.ArrayList;
39 import java.util.List;
40 import java.util.Map.Entry;
41 import java.util.SortedMap;
42 import java.util.TreeMap;
43 import java.util.logging.Logger;
44 
45 /**
46  * A tree representation of a FieldMask. Each leaf node in this tree represent
47  * a field path in the FieldMask.
48  *
49  * <p>For example, FieldMask "foo.bar,foo.baz,bar.baz" as a tree will be:
50  * <pre>
51  *   [root] -+- foo -+- bar
52  *           |       |
53  *           |       +- baz
54  *           |
55  *           +- bar --- baz
56  * </pre>
57  *
58  * <p>By representing FieldMasks with this tree structure we can easily convert
59  * a FieldMask to a canonical form, merge two FieldMasks, calculate the
60  * intersection to two FieldMasks and traverse all fields specified by the
61  * FieldMask in a message tree.
62  */
63 final class FieldMaskTree {
64   private static final Logger logger = Logger.getLogger(FieldMaskTree.class.getName());
65 
66   private static final String FIELD_PATH_SEPARATOR_REGEX = "\\.";
67 
68   private static final class Node {
69     final SortedMap<String, Node> children = new TreeMap<String, Node>();
70   }
71 
72   private final Node root = new Node();
73 
74   /**
75    * Creates an empty FieldMaskTree.
76    */
FieldMaskTree()77   FieldMaskTree() {}
78 
79   /**
80    * Creates a FieldMaskTree for a given FieldMask.
81    */
FieldMaskTree(FieldMask mask)82   FieldMaskTree(FieldMask mask) {
83     mergeFromFieldMask(mask);
84   }
85 
86   @Override
toString()87   public String toString() {
88     return FieldMaskUtil.toString(toFieldMask());
89   }
90 
91   /**
92    * Adds a field path to the tree. In a FieldMask, every field path matches the
93    * specified field as well as all its sub-fields. For example, a field path
94    * "foo.bar" matches field "foo.bar" and also "foo.bar.baz", etc. When adding
95    * a field path to the tree, redundant sub-paths will be removed. That is,
96    * after adding "foo.bar" to the tree, "foo.bar.baz" will be removed if it
97    * exists, which will turn the tree node for "foo.bar" to a leaf node.
98    * Likewise, if the field path to add is a sub-path of an existing leaf node,
99    * nothing will be changed in the tree.
100    */
addFieldPath(String path)101   FieldMaskTree addFieldPath(String path) {
102     String[] parts = path.split(FIELD_PATH_SEPARATOR_REGEX);
103     if (parts.length == 0) {
104       return this;
105     }
106     Node node = root;
107     boolean createNewBranch = false;
108     // Find the matching node in the tree.
109     for (String part : parts) {
110       // Check whether the path matches an existing leaf node.
111       if (!createNewBranch && node != root && node.children.isEmpty()) {
112         // The path to add is a sub-path of an existing leaf node.
113         return this;
114       }
115       if (node.children.containsKey(part)) {
116         node = node.children.get(part);
117       } else {
118         createNewBranch = true;
119         Node tmp = new Node();
120         node.children.put(part, tmp);
121         node = tmp;
122       }
123     }
124     // Turn the matching node into a leaf node (i.e., remove sub-paths).
125     node.children.clear();
126     return this;
127   }
128 
129   /**
130    * Merges all field paths in a FieldMask into this tree.
131    */
mergeFromFieldMask(FieldMask mask)132   FieldMaskTree mergeFromFieldMask(FieldMask mask) {
133     for (String path : mask.getPathsList()) {
134       addFieldPath(path);
135     }
136     return this;
137   }
138 
139   /**
140    * Converts this tree to a FieldMask.
141    */
toFieldMask()142   FieldMask toFieldMask() {
143     if (root.children.isEmpty()) {
144       return FieldMask.getDefaultInstance();
145     }
146     List<String> paths = new ArrayList<String>();
147     getFieldPaths(root, "", paths);
148     return FieldMask.newBuilder().addAllPaths(paths).build();
149   }
150 
151   /**
152    * Gathers all field paths in a sub-tree.
153    */
getFieldPaths(Node node, String path, List<String> paths)154   private void getFieldPaths(Node node, String path, List<String> paths) {
155     if (node.children.isEmpty()) {
156       paths.add(path);
157       return;
158     }
159     for (Entry<String, Node> entry : node.children.entrySet()) {
160       String childPath = path.isEmpty() ? entry.getKey() : path + "." + entry.getKey();
161       getFieldPaths(entry.getValue(), childPath, paths);
162     }
163   }
164 
165   /**
166    * Adds the intersection of this tree with the given {@code path} to {@code output}.
167    */
intersectFieldPath(String path, FieldMaskTree output)168   void intersectFieldPath(String path, FieldMaskTree output) {
169     if (root.children.isEmpty()) {
170       return;
171     }
172     String[] parts = path.split(FIELD_PATH_SEPARATOR_REGEX);
173     if (parts.length == 0) {
174       return;
175     }
176     Node node = root;
177     for (String part : parts) {
178       if (node != root && node.children.isEmpty()) {
179         // The given path is a sub-path of an existing leaf node in the tree.
180         output.addFieldPath(path);
181         return;
182       }
183       if (node.children.containsKey(part)) {
184         node = node.children.get(part);
185       } else {
186         return;
187       }
188     }
189     // We found a matching node for the path. All leaf children of this matching
190     // node is in the intersection.
191     List<String> paths = new ArrayList<String>();
192     getFieldPaths(node, path, paths);
193     for (String value : paths) {
194       output.addFieldPath(value);
195     }
196   }
197 
198   /**
199    * Merges all fields specified by this FieldMaskTree from {@code source} to {@code destination}.
200    */
merge(Message source, Message.Builder destination, FieldMaskUtil.MergeOptions options)201   void merge(Message source, Message.Builder destination, FieldMaskUtil.MergeOptions options) {
202     if (source.getDescriptorForType() != destination.getDescriptorForType()) {
203       throw new IllegalArgumentException("Cannot merge messages of different types.");
204     }
205     if (root.children.isEmpty()) {
206       return;
207     }
208     merge(root, "", source, destination, options);
209   }
210 
211   /**
212    * Merges all fields specified by a sub-tree from {@code source} to {@code destination}.
213    */
merge( Node node, String path, Message source, Message.Builder destination, FieldMaskUtil.MergeOptions options)214   private void merge(
215       Node node,
216       String path,
217       Message source,
218       Message.Builder destination,
219       FieldMaskUtil.MergeOptions options) {
220     assert source.getDescriptorForType() == destination.getDescriptorForType();
221 
222     Descriptor descriptor = source.getDescriptorForType();
223     for (Entry<String, Node> entry : node.children.entrySet()) {
224       FieldDescriptor field = descriptor.findFieldByName(entry.getKey());
225       if (field == null) {
226         logger.warning(
227             "Cannot find field \""
228                 + entry.getKey()
229                 + "\" in message type "
230                 + descriptor.getFullName());
231         continue;
232       }
233       if (!entry.getValue().children.isEmpty()) {
234         if (field.isRepeated() || field.getJavaType() != FieldDescriptor.JavaType.MESSAGE) {
235           logger.warning(
236               "Field \""
237                   + field.getFullName()
238                   + "\" is not a "
239                   + "singluar message field and cannot have sub-fields.");
240           continue;
241         }
242         String childPath = path.isEmpty() ? entry.getKey() : path + "." + entry.getKey();
243         merge(
244             entry.getValue(),
245             childPath,
246             (Message) source.getField(field),
247             destination.getFieldBuilder(field),
248             options);
249         continue;
250       }
251       if (field.isRepeated()) {
252         if (options.replaceRepeatedFields()) {
253           destination.setField(field, source.getField(field));
254         } else {
255           for (Object element : (List) source.getField(field)) {
256             destination.addRepeatedField(field, element);
257           }
258         }
259       } else {
260         if (field.getJavaType() == FieldDescriptor.JavaType.MESSAGE) {
261           if (options.replaceMessageFields()) {
262             if (!source.hasField(field)) {
263               destination.clearField(field);
264             } else {
265               destination.setField(field, source.getField(field));
266             }
267           } else {
268             if (source.hasField(field)) {
269               destination.getFieldBuilder(field).mergeFrom((Message) source.getField(field));
270             }
271           }
272         } else {
273           if (source.hasField(field) || !options.replacePrimitiveFields()) {
274             destination.setField(field, source.getField(field));
275           } else {
276             destination.clearField(field);
277           }
278         }
279       }
280     }
281   }
282 }
283