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 #include <google/protobuf/util/field_mask_util.h> 32 33 #include <google/protobuf/stubs/strutil.h> 34 #include <google/protobuf/stubs/map_util.h> 35 36 namespace google { 37 namespace protobuf { 38 namespace util { 39 40 using google::protobuf::FieldMask; 41 42 string FieldMaskUtil::ToString(const FieldMask& mask) { 43 return Join(mask.paths(), ","); 44 } 45 46 void FieldMaskUtil::FromString(StringPiece str, FieldMask* out) { 47 out->Clear(); 48 vector<string> paths = Split(str, ","); 49 for (int i = 0; i < paths.size(); ++i) { 50 if (paths[i].empty()) continue; 51 out->add_paths(paths[i]); 52 } 53 } 54 55 bool FieldMaskUtil::SnakeCaseToCamelCase(StringPiece input, string* output) { 56 output->clear(); 57 bool after_underscore = false; 58 for (int i = 0; i < input.size(); ++i) { 59 if (input[i] >= 'A' && input[i] <= 'Z') { 60 // The field name must not contain uppercase letters. 61 return false; 62 } 63 if (after_underscore) { 64 if (input[i] >= 'a' && input[i] <= 'z') { 65 output->push_back(input[i] + 'A' - 'a'); 66 after_underscore = false; 67 } else { 68 // The character after a "_" must be a lowercase letter. 69 return false; 70 } 71 } else if (input[i] == '_') { 72 after_underscore = true; 73 } else { 74 output->push_back(input[i]); 75 } 76 } 77 if (after_underscore) { 78 // Trailing "_". 79 return false; 80 } 81 return true; 82 } 83 84 bool FieldMaskUtil::CamelCaseToSnakeCase(StringPiece input, string* output) { 85 output->clear(); 86 for (int i = 0; i < input.size(); ++i) { 87 if (input[i] == '_') { 88 // The field name must not contain "_"s. 89 return false; 90 } 91 if (input[i] >= 'A' && input[i] <= 'Z') { 92 output->push_back('_'); 93 output->push_back(input[i] + 'a' - 'A'); 94 } else { 95 output->push_back(input[i]); 96 } 97 } 98 return true; 99 } 100 101 bool FieldMaskUtil::ToJsonString(const FieldMask& mask, string* out) { 102 out->clear(); 103 for (int i = 0; i < mask.paths_size(); ++i) { 104 const string& path = mask.paths(i); 105 string camelcase_path; 106 if (!SnakeCaseToCamelCase(path, &camelcase_path)) { 107 return false; 108 } 109 if (i > 0) { 110 out->push_back(','); 111 } 112 out->append(camelcase_path); 113 } 114 return true; 115 } 116 117 bool FieldMaskUtil::FromJsonString(StringPiece str, FieldMask* out) { 118 out->Clear(); 119 vector<string> paths = Split(str, ","); 120 for (int i = 0; i < paths.size(); ++i) { 121 if (paths[i].empty()) continue; 122 string snakecase_path; 123 if (!CamelCaseToSnakeCase(paths[i], &snakecase_path)) { 124 return false; 125 } 126 out->add_paths(snakecase_path); 127 } 128 return true; 129 } 130 131 bool FieldMaskUtil::InternalIsValidPath(const Descriptor* descriptor, 132 StringPiece path) { 133 vector<string> parts = Split(path, "."); 134 for (int i = 0; i < parts.size(); ++i) { 135 const string& field_name = parts[i]; 136 if (descriptor == NULL) { 137 return false; 138 } 139 const FieldDescriptor* field = descriptor->FindFieldByName(field_name); 140 if (field == NULL) { 141 return false; 142 } 143 if (!field->is_repeated() && 144 field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) { 145 descriptor = field->message_type(); 146 } else { 147 descriptor = NULL; 148 } 149 } 150 return true; 151 } 152 153 void FieldMaskUtil::InternalGetFieldMaskForAllFields( 154 const Descriptor* descriptor, FieldMask* out) { 155 for (int i = 0; i < descriptor->field_count(); ++i) { 156 out->add_paths(descriptor->field(i)->name()); 157 } 158 } 159 160 namespace { 161 // A FieldMaskTree represents a FieldMask in a tree structure. For example, 162 // given a FieldMask "foo.bar,foo.baz,bar.baz", the FieldMaskTree will be: 163 // 164 // [root] -+- foo -+- bar 165 // | | 166 // | +- baz 167 // | 168 // +- bar --- baz 169 // 170 // In the tree, each leaf node represents a field path. 171 class FieldMaskTree { 172 public: 173 FieldMaskTree(); 174 ~FieldMaskTree(); 175 176 void MergeFromFieldMask(const FieldMask& mask); 177 void MergeToFieldMask(FieldMask* mask); 178 179 // Add a field path into the tree. In a FieldMask, each field path matches 180 // the specified field and also all its sub-fields. If the field path to 181 // add is a sub-path of an existing field path in the tree (i.e., a leaf 182 // node), it means the tree already matches the given path so nothing will 183 // be added to the tree. If the path matches an existing non-leaf node in the 184 // tree, that non-leaf node will be turned into a leaf node with all its 185 // children removed because the path matches all the node's children. 186 void AddPath(const string& path); 187 188 // Calculate the intersection part of a field path with this tree and add 189 // the intersection field path into out. 190 void IntersectPath(const string& path, FieldMaskTree* out); 191 192 // Merge all fields specified by this tree from one message to another. 193 void MergeMessage(const Message& source, 194 const FieldMaskUtil::MergeOptions& options, 195 Message* destination) { 196 // Do nothing if the tree is empty. 197 if (root_.children.empty()) { 198 return; 199 } 200 MergeMessage(&root_, source, options, destination); 201 } 202 203 private: 204 struct Node { 205 Node() {} 206 207 ~Node() { ClearChildren(); } 208 209 void ClearChildren() { 210 for (map<string, Node*>::iterator it = children.begin(); 211 it != children.end(); ++it) { 212 delete it->second; 213 } 214 children.clear(); 215 } 216 217 map<string, Node*> children; 218 219 private: 220 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(Node); 221 }; 222 223 // Merge a sub-tree to mask. This method adds the field paths represented 224 // by all leaf nodes descended from "node" to mask. 225 void MergeToFieldMask(const string& prefix, const Node* node, FieldMask* out); 226 227 // Merge all leaf nodes of a sub-tree to another tree. 228 void MergeLeafNodesToTree(const string& prefix, const Node* node, 229 FieldMaskTree* out); 230 231 // Merge all fields specified by a sub-tree from one message to another. 232 void MergeMessage(const Node* node, const Message& source, 233 const FieldMaskUtil::MergeOptions& options, 234 Message* destination); 235 236 Node root_; 237 238 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(FieldMaskTree); 239 }; 240 241 FieldMaskTree::FieldMaskTree() {} 242 243 FieldMaskTree::~FieldMaskTree() {} 244 245 void FieldMaskTree::MergeFromFieldMask(const FieldMask& mask) { 246 for (int i = 0; i < mask.paths_size(); ++i) { 247 AddPath(mask.paths(i)); 248 } 249 } 250 251 void FieldMaskTree::MergeToFieldMask(FieldMask* mask) { 252 MergeToFieldMask("", &root_, mask); 253 } 254 255 void FieldMaskTree::MergeToFieldMask(const string& prefix, const Node* node, 256 FieldMask* out) { 257 if (node->children.empty()) { 258 if (prefix.empty()) { 259 // This is the root node. 260 return; 261 } 262 out->add_paths(prefix); 263 return; 264 } 265 for (map<string, Node*>::const_iterator it = node->children.begin(); 266 it != node->children.end(); ++it) { 267 string current_path = prefix.empty() ? it->first : prefix + "." + it->first; 268 MergeToFieldMask(current_path, it->second, out); 269 } 270 } 271 272 void FieldMaskTree::AddPath(const string& path) { 273 vector<string> parts = Split(path, "."); 274 if (parts.empty()) { 275 return; 276 } 277 bool new_branch = false; 278 Node* node = &root_; 279 for (int i = 0; i < parts.size(); ++i) { 280 if (!new_branch && node != &root_ && node->children.empty()) { 281 // Path matches an existing leaf node. This means the path is already 282 // coverred by this tree (for example, adding "foo.bar.baz" to a tree 283 // which already contains "foo.bar"). 284 return; 285 } 286 const string& node_name = parts[i]; 287 Node*& child = node->children[node_name]; 288 if (child == NULL) { 289 new_branch = true; 290 child = new Node(); 291 } 292 node = child; 293 } 294 if (!node->children.empty()) { 295 node->ClearChildren(); 296 } 297 } 298 299 void FieldMaskTree::IntersectPath(const string& path, FieldMaskTree* out) { 300 vector<string> parts = Split(path, "."); 301 if (parts.empty()) { 302 return; 303 } 304 const Node* node = &root_; 305 for (int i = 0; i < parts.size(); ++i) { 306 if (node->children.empty()) { 307 if (node != &root_) { 308 out->AddPath(path); 309 } 310 return; 311 } 312 const string& node_name = parts[i]; 313 const Node* result = FindPtrOrNull(node->children, node_name); 314 if (result == NULL) { 315 // No intersection found. 316 return; 317 } 318 node = result; 319 } 320 // Now we found a matching node with the given path. Add all leaf nodes 321 // to out. 322 MergeLeafNodesToTree(path, node, out); 323 } 324 325 void FieldMaskTree::MergeLeafNodesToTree(const string& prefix, const Node* node, 326 FieldMaskTree* out) { 327 if (node->children.empty()) { 328 out->AddPath(prefix); 329 } 330 for (map<string, Node*>::const_iterator it = node->children.begin(); 331 it != node->children.end(); ++it) { 332 string current_path = prefix.empty() ? it->first : prefix + "." + it->first; 333 MergeLeafNodesToTree(current_path, it->second, out); 334 } 335 } 336 337 void FieldMaskTree::MergeMessage(const Node* node, const Message& source, 338 const FieldMaskUtil::MergeOptions& options, 339 Message* destination) { 340 GOOGLE_DCHECK(!node->children.empty()); 341 const Reflection* source_reflection = source.GetReflection(); 342 const Reflection* destination_reflection = destination->GetReflection(); 343 const Descriptor* descriptor = source.GetDescriptor(); 344 for (map<string, Node*>::const_iterator it = node->children.begin(); 345 it != node->children.end(); ++it) { 346 const string& field_name = it->first; 347 const Node* child = it->second; 348 const FieldDescriptor* field = descriptor->FindFieldByName(field_name); 349 if (field == NULL) { 350 GOOGLE_LOG(ERROR) << "Cannot find field \"" << field_name << "\" in message " 351 << descriptor->full_name(); 352 continue; 353 } 354 if (!child->children.empty()) { 355 // Sub-paths are only allowed for singular message fields. 356 if (field->is_repeated() || 357 field->cpp_type() != FieldDescriptor::CPPTYPE_MESSAGE) { 358 GOOGLE_LOG(ERROR) << "Field \"" << field_name << "\" in message " 359 << descriptor->full_name() 360 << " is not a singular message field and cannot " 361 << "have sub-fields."; 362 continue; 363 } 364 MergeMessage(child, source_reflection->GetMessage(source, field), options, 365 destination_reflection->MutableMessage(destination, field)); 366 continue; 367 } 368 if (!field->is_repeated()) { 369 switch (field->cpp_type()) { 370 #define COPY_VALUE(TYPE, Name) \ 371 case FieldDescriptor::CPPTYPE_##TYPE: { \ 372 destination_reflection->Set##Name( \ 373 destination, field, source_reflection->Get##Name(source, field)); \ 374 break; \ 375 } 376 COPY_VALUE(BOOL, Bool) 377 COPY_VALUE(INT32, Int32) 378 COPY_VALUE(INT64, Int64) 379 COPY_VALUE(UINT32, UInt32) 380 COPY_VALUE(UINT64, UInt64) 381 COPY_VALUE(FLOAT, Float) 382 COPY_VALUE(DOUBLE, Double) 383 COPY_VALUE(ENUM, Enum) 384 COPY_VALUE(STRING, String) 385 #undef COPY_VALUE 386 case FieldDescriptor::CPPTYPE_MESSAGE: { 387 if (options.replace_message_fields()) { 388 destination_reflection->ClearField(destination, field); 389 } 390 if (source_reflection->HasField(source, field)) { 391 destination_reflection->MutableMessage(destination, field) 392 ->MergeFrom(source_reflection->GetMessage(source, field)); 393 } 394 break; 395 } 396 } 397 } else { 398 if (options.replace_repeated_fields()) { 399 destination_reflection->ClearField(destination, field); 400 } 401 switch (field->cpp_type()) { 402 #define COPY_REPEATED_VALUE(TYPE, Name) \ 403 case FieldDescriptor::CPPTYPE_##TYPE: { \ 404 int size = source_reflection->FieldSize(source, field); \ 405 for (int i = 0; i < size; ++i) { \ 406 destination_reflection->Add##Name( \ 407 destination, field, \ 408 source_reflection->GetRepeated##Name(source, field, i)); \ 409 } \ 410 break; \ 411 } 412 COPY_REPEATED_VALUE(BOOL, Bool) 413 COPY_REPEATED_VALUE(INT32, Int32) 414 COPY_REPEATED_VALUE(INT64, Int64) 415 COPY_REPEATED_VALUE(UINT32, UInt32) 416 COPY_REPEATED_VALUE(UINT64, UInt64) 417 COPY_REPEATED_VALUE(FLOAT, Float) 418 COPY_REPEATED_VALUE(DOUBLE, Double) 419 COPY_REPEATED_VALUE(ENUM, Enum) 420 COPY_REPEATED_VALUE(STRING, String) 421 #undef COPY_REPEATED_VALUE 422 case FieldDescriptor::CPPTYPE_MESSAGE: { 423 int size = source_reflection->FieldSize(source, field); 424 for (int i = 0; i < size; ++i) { 425 destination_reflection->AddMessage(destination, field) 426 ->MergeFrom( 427 source_reflection->GetRepeatedMessage(source, field, i)); 428 } 429 break; 430 } 431 } 432 } 433 } 434 } 435 436 } // namespace 437 438 void FieldMaskUtil::ToCanonicalForm(const FieldMask& mask, FieldMask* out) { 439 FieldMaskTree tree; 440 tree.MergeFromFieldMask(mask); 441 out->Clear(); 442 tree.MergeToFieldMask(out); 443 } 444 445 void FieldMaskUtil::Union(const FieldMask& mask1, const FieldMask& mask2, 446 FieldMask* out) { 447 FieldMaskTree tree; 448 tree.MergeFromFieldMask(mask1); 449 tree.MergeFromFieldMask(mask2); 450 out->Clear(); 451 tree.MergeToFieldMask(out); 452 } 453 454 void FieldMaskUtil::Intersect(const FieldMask& mask1, const FieldMask& mask2, 455 FieldMask* out) { 456 FieldMaskTree tree, intersection; 457 tree.MergeFromFieldMask(mask1); 458 for (int i = 0; i < mask2.paths_size(); ++i) { 459 tree.IntersectPath(mask2.paths(i), &intersection); 460 } 461 out->Clear(); 462 intersection.MergeToFieldMask(out); 463 } 464 465 bool FieldMaskUtil::IsPathInFieldMask(StringPiece path, const FieldMask& mask) { 466 for (int i = 0; i < mask.paths_size(); ++i) { 467 const string& mask_path = mask.paths(i); 468 if (path == mask_path) { 469 return true; 470 } else if (mask_path.length() < path.length()) { 471 // Also check whether mask.paths(i) is a prefix of path. 472 if (path.substr(0, mask_path.length() + 1).compare(mask_path + ".") == 473 0) { 474 return true; 475 } 476 } 477 } 478 return false; 479 } 480 481 void FieldMaskUtil::MergeMessageTo(const Message& source, const FieldMask& mask, 482 const MergeOptions& options, 483 Message* destination) { 484 GOOGLE_CHECK(source.GetDescriptor() == destination->GetDescriptor()); 485 // Build a FieldMaskTree and walk through the tree to merge all specified 486 // fields. 487 FieldMaskTree tree; 488 tree.MergeFromFieldMask(mask); 489 tree.MergeMessage(source, options, destination); 490 } 491 492 } // namespace util 493 } // namespace protobuf 494 } // namespace google 495