1/* 2 Copyright (c) 2009-2017 Dave Gamble and cJSON contributors 3 4 Permission is hereby granted, free of charge, to any person obtaining a copy 5 of this software and associated documentation files (the "Software"), to deal 6 in the Software without restriction, including without limitation the rights 7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8 copies of the Software, and to permit persons to whom the Software is 9 furnished to do so, subject to the following conditions: 10 11 The above copyright notice and this permission notice shall be included in 12 all copies or substantial portions of the Software. 13 14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20 THE SOFTWARE. 21*/ 22 23/* disable warnings about old C89 functions in MSVC */ 24#if !defined(_CRT_SECURE_NO_DEPRECATE) && defined(_MSC_VER) 25#define _CRT_SECURE_NO_DEPRECATE 26#endif 27 28#ifdef __GNUCC__ 29#pragma GCC visibility push(default) 30#endif 31#if defined(_MSC_VER) 32#pragma warning (push) 33/* disable warning about single line comments in system headers */ 34#pragma warning (disable : 4001) 35#endif 36 37#include <ctype.h> 38#include <string.h> 39#include <stdlib.h> 40#include <stdio.h> 41#include <limits.h> 42#include <math.h> 43#include <float.h> 44#include <math.h> 45 46#if defined(_MSC_VER) 47#pragma warning (pop) 48#endif 49#ifdef __GNUCC__ 50#pragma GCC visibility pop 51#endif 52 53#include "cJSON_Utils.h" 54 55/* define our own boolean type */ 56#ifdef true 57#undef true 58#endif 59#define true ((cJSON_bool)1) 60 61#ifdef false 62#undef false 63#endif 64#define false ((cJSON_bool)0) 65 66static unsigned char* cJSONUtils_strdup(const unsigned char* const string) 67{ 68 size_t length = 0; 69 unsigned char *copy = NULL; 70 71 length = strlen((const char*)string) + sizeof(""); 72 copy = (unsigned char*) cJSON_malloc(length); 73 if (copy == NULL) 74 { 75 return NULL; 76 } 77 memcpy(copy, string, length); 78 79 return copy; 80} 81 82/* string comparison which doesn't consider NULL pointers equal */ 83static int compare_strings(const unsigned char *string1, const unsigned char *string2, const cJSON_bool case_sensitive) 84{ 85 if ((string1 == NULL) || (string2 == NULL)) 86 { 87 return 1; 88 } 89 90 if (string1 == string2) 91 { 92 return 0; 93 } 94 95 if (case_sensitive) 96 { 97 return strcmp((const char*)string1, (const char*)string2); 98 } 99 100 for(; tolower(*string1) == tolower(*string2); (void)string1++, string2++) 101 { 102 if (*string1 == '\0') 103 { 104 return 0; 105 } 106 } 107 108 return tolower(*string1) - tolower(*string2); 109} 110 111/* securely comparison of floating-point variables */ 112static cJSON_bool compare_double(double a, double b) 113{ 114 double maxVal = fabs(a) > fabs(b) ? fabs(a) : fabs(b); 115 return (fabs(a - b) <= maxVal * DBL_EPSILON); 116} 117 118 119/* Compare the next path element of two JSON pointers, two NULL pointers are considered unequal: */ 120static cJSON_bool compare_pointers(const unsigned char *name, const unsigned char *pointer, const cJSON_bool case_sensitive) 121{ 122 if ((name == NULL) || (pointer == NULL)) 123 { 124 return false; 125 } 126 127 for (; (*name != '\0') && (*pointer != '\0') && (*pointer != '/'); (void)name++, pointer++) /* compare until next '/' */ 128 { 129 if (*pointer == '~') 130 { 131 /* check for escaped '~' (~0) and '/' (~1) */ 132 if (((pointer[1] != '0') || (*name != '~')) && ((pointer[1] != '1') || (*name != '/'))) 133 { 134 /* invalid escape sequence or wrong character in *name */ 135 return false; 136 } 137 else 138 { 139 pointer++; 140 } 141 } 142 else if ((!case_sensitive && (tolower(*name) != tolower(*pointer))) || (case_sensitive && (*name != *pointer))) 143 { 144 return false; 145 } 146 } 147 if (((*pointer != 0) && (*pointer != '/')) != (*name != 0)) 148 { 149 /* one string has ended, the other not */ 150 return false;; 151 } 152 153 return true; 154} 155 156/* calculate the length of a string if encoded as JSON pointer with ~0 and ~1 escape sequences */ 157static size_t pointer_encoded_length(const unsigned char *string) 158{ 159 size_t length; 160 for (length = 0; *string != '\0'; (void)string++, length++) 161 { 162 /* character needs to be escaped? */ 163 if ((*string == '~') || (*string == '/')) 164 { 165 length++; 166 } 167 } 168 169 return length; 170} 171 172/* copy a string while escaping '~' and '/' with ~0 and ~1 JSON pointer escape codes */ 173static void encode_string_as_pointer(unsigned char *destination, const unsigned char *source) 174{ 175 for (; source[0] != '\0'; (void)source++, destination++) 176 { 177 if (source[0] == '/') 178 { 179 destination[0] = '~'; 180 destination[1] = '1'; 181 destination++; 182 } 183 else if (source[0] == '~') 184 { 185 destination[0] = '~'; 186 destination[1] = '0'; 187 destination++; 188 } 189 else 190 { 191 destination[0] = source[0]; 192 } 193 } 194 195 destination[0] = '\0'; 196} 197 198CJSON_PUBLIC(char *) cJSONUtils_FindPointerFromObjectTo(const cJSON * const object, const cJSON * const target) 199{ 200 size_t child_index = 0; 201 cJSON *current_child = 0; 202 203 if ((object == NULL) || (target == NULL)) 204 { 205 return NULL; 206 } 207 208 if (object == target) 209 { 210 /* found */ 211 return (char*)cJSONUtils_strdup((const unsigned char*)""); 212 } 213 214 /* recursively search all children of the object or array */ 215 for (current_child = object->child; current_child != NULL; (void)(current_child = current_child->next), child_index++) 216 { 217 unsigned char *target_pointer = (unsigned char*)cJSONUtils_FindPointerFromObjectTo(current_child, target); 218 /* found the target? */ 219 if (target_pointer != NULL) 220 { 221 if (cJSON_IsArray(object)) 222 { 223 /* reserve enough memory for a 64 bit integer + '/' and '\0' */ 224 unsigned char *full_pointer = (unsigned char*)cJSON_malloc(strlen((char*)target_pointer) + 20 + sizeof("/")); 225 /* check if conversion to unsigned long is valid 226 * This should be eliminated at compile time by dead code elimination 227 * if size_t is an alias of unsigned long, or if it is bigger */ 228 if (child_index > ULONG_MAX) 229 { 230 cJSON_free(target_pointer); 231 cJSON_free(full_pointer); 232 return NULL; 233 } 234 sprintf((char*)full_pointer, "/%lu%s", (unsigned long)child_index, target_pointer); /* /<array_index><path> */ 235 cJSON_free(target_pointer); 236 237 return (char*)full_pointer; 238 } 239 240 if (cJSON_IsObject(object)) 241 { 242 unsigned char *full_pointer = (unsigned char*)cJSON_malloc(strlen((char*)target_pointer) + pointer_encoded_length((unsigned char*)current_child->string) + 2); 243 full_pointer[0] = '/'; 244 encode_string_as_pointer(full_pointer + 1, (unsigned char*)current_child->string); 245 strcat((char*)full_pointer, (char*)target_pointer); 246 cJSON_free(target_pointer); 247 248 return (char*)full_pointer; 249 } 250 251 /* reached leaf of the tree, found nothing */ 252 cJSON_free(target_pointer); 253 return NULL; 254 } 255 } 256 257 /* not found */ 258 return NULL; 259} 260 261/* non broken version of cJSON_GetArrayItem */ 262static cJSON *get_array_item(const cJSON *array, size_t item) 263{ 264 cJSON *child = array ? array->child : NULL; 265 while ((child != NULL) && (item > 0)) 266 { 267 item--; 268 child = child->next; 269 } 270 271 return child; 272} 273 274static cJSON_bool decode_array_index_from_pointer(const unsigned char * const pointer, size_t * const index) 275{ 276 size_t parsed_index = 0; 277 size_t position = 0; 278 279 if ((pointer[0] == '0') && ((pointer[1] != '\0') && (pointer[1] != '/'))) 280 { 281 /* leading zeroes are not permitted */ 282 return 0; 283 } 284 285 for (position = 0; (pointer[position] >= '0') && (pointer[0] <= '9'); position++) 286 { 287 parsed_index = (10 * parsed_index) + (size_t)(pointer[position] - '0'); 288 289 } 290 291 if ((pointer[position] != '\0') && (pointer[position] != '/')) 292 { 293 return 0; 294 } 295 296 *index = parsed_index; 297 298 return 1; 299} 300 301static cJSON *get_item_from_pointer(cJSON * const object, const char * pointer, const cJSON_bool case_sensitive) 302{ 303 cJSON *current_element = object; 304 305 if (pointer == NULL) 306 { 307 return NULL; 308 } 309 310 /* follow path of the pointer */ 311 while ((pointer[0] == '/') && (current_element != NULL)) 312 { 313 pointer++; 314 if (cJSON_IsArray(current_element)) 315 { 316 size_t index = 0; 317 if (!decode_array_index_from_pointer((const unsigned char*)pointer, &index)) 318 { 319 return NULL; 320 } 321 322 current_element = get_array_item(current_element, index); 323 } 324 else if (cJSON_IsObject(current_element)) 325 { 326 current_element = current_element->child; 327 /* GetObjectItem. */ 328 while ((current_element != NULL) && !compare_pointers((unsigned char*)current_element->string, (const unsigned char*)pointer, case_sensitive)) 329 { 330 current_element = current_element->next; 331 } 332 } 333 else 334 { 335 return NULL; 336 } 337 338 /* skip to the next path token or end of string */ 339 while ((pointer[0] != '\0') && (pointer[0] != '/')) 340 { 341 pointer++; 342 } 343 } 344 345 return current_element; 346} 347 348CJSON_PUBLIC(cJSON *) cJSONUtils_GetPointer(cJSON * const object, const char *pointer) 349{ 350 return get_item_from_pointer(object, pointer, false); 351} 352 353CJSON_PUBLIC(cJSON *) cJSONUtils_GetPointerCaseSensitive(cJSON * const object, const char *pointer) 354{ 355 return get_item_from_pointer(object, pointer, true); 356} 357 358/* JSON Patch implementation. */ 359static void decode_pointer_inplace(unsigned char *string) 360{ 361 unsigned char *decoded_string = string; 362 363 if (string == NULL) { 364 return; 365 } 366 367 for (; *string; (void)decoded_string++, string++) 368 { 369 if (string[0] == '~') 370 { 371 if (string[1] == '0') 372 { 373 decoded_string[0] = '~'; 374 } 375 else if (string[1] == '1') 376 { 377 decoded_string[1] = '/'; 378 } 379 else 380 { 381 /* invalid escape sequence */ 382 return; 383 } 384 385 string++; 386 } 387 } 388 389 decoded_string[0] = '\0'; 390} 391 392/* non-broken cJSON_DetachItemFromArray */ 393static cJSON *detach_item_from_array(cJSON *array, size_t which) 394{ 395 cJSON *c = array->child; 396 while (c && (which > 0)) 397 { 398 c = c->next; 399 which--; 400 } 401 if (!c) 402 { 403 /* item doesn't exist */ 404 return NULL; 405 } 406 if (c != array->child) 407 { 408 /* not the first element */ 409 c->prev->next = c->next; 410 } 411 if (c->next) 412 { 413 c->next->prev = c->prev; 414 } 415 if (c == array->child) 416 { 417 array->child = c->next; 418 } 419 else if (c->next == NULL) 420 { 421 array->child->prev = c->prev; 422 } 423 /* make sure the detached item doesn't point anywhere anymore */ 424 c->prev = c->next = NULL; 425 426 return c; 427} 428 429/* detach an item at the given path */ 430static cJSON *detach_path(cJSON *object, const unsigned char *path, const cJSON_bool case_sensitive) 431{ 432 unsigned char *parent_pointer = NULL; 433 unsigned char *child_pointer = NULL; 434 cJSON *parent = NULL; 435 cJSON *detached_item = NULL; 436 437 /* copy path and split it in parent and child */ 438 parent_pointer = cJSONUtils_strdup(path); 439 if (parent_pointer == NULL) { 440 goto cleanup; 441 } 442 443 child_pointer = (unsigned char*)strrchr((char*)parent_pointer, '/'); /* last '/' */ 444 if (child_pointer == NULL) 445 { 446 goto cleanup; 447 } 448 /* split strings */ 449 child_pointer[0] = '\0'; 450 child_pointer++; 451 452 parent = get_item_from_pointer(object, (char*)parent_pointer, case_sensitive); 453 decode_pointer_inplace(child_pointer); 454 455 if (cJSON_IsArray(parent)) 456 { 457 size_t index = 0; 458 if (!decode_array_index_from_pointer(child_pointer, &index)) 459 { 460 goto cleanup; 461 } 462 detached_item = detach_item_from_array(parent, index); 463 } 464 else if (cJSON_IsObject(parent)) 465 { 466 detached_item = cJSON_DetachItemFromObject(parent, (char*)child_pointer); 467 } 468 else 469 { 470 /* Couldn't find object to remove child from. */ 471 goto cleanup; 472 } 473 474cleanup: 475 if (parent_pointer != NULL) 476 { 477 cJSON_free(parent_pointer); 478 } 479 480 return detached_item; 481} 482 483/* sort lists using mergesort */ 484static cJSON *sort_list(cJSON *list, const cJSON_bool case_sensitive) 485{ 486 cJSON *first = list; 487 cJSON *second = list; 488 cJSON *current_item = list; 489 cJSON *result = list; 490 cJSON *result_tail = NULL; 491 492 if ((list == NULL) || (list->next == NULL)) 493 { 494 /* One entry is sorted already. */ 495 return result; 496 } 497 498 while ((current_item != NULL) && (current_item->next != NULL) && (compare_strings((unsigned char*)current_item->string, (unsigned char*)current_item->next->string, case_sensitive) < 0)) 499 { 500 /* Test for list sorted. */ 501 current_item = current_item->next; 502 } 503 if ((current_item == NULL) || (current_item->next == NULL)) 504 { 505 /* Leave sorted lists unmodified. */ 506 return result; 507 } 508 509 /* reset pointer to the beginning */ 510 current_item = list; 511 while (current_item != NULL) 512 { 513 /* Walk two pointers to find the middle. */ 514 second = second->next; 515 current_item = current_item->next; 516 /* advances current_item two steps at a time */ 517 if (current_item != NULL) 518 { 519 current_item = current_item->next; 520 } 521 } 522 if ((second != NULL) && (second->prev != NULL)) 523 { 524 /* Split the lists */ 525 second->prev->next = NULL; 526 second->prev = NULL; 527 } 528 529 /* Recursively sort the sub-lists. */ 530 first = sort_list(first, case_sensitive); 531 second = sort_list(second, case_sensitive); 532 result = NULL; 533 534 /* Merge the sub-lists */ 535 while ((first != NULL) && (second != NULL)) 536 { 537 cJSON *smaller = NULL; 538 if (compare_strings((unsigned char*)first->string, (unsigned char*)second->string, case_sensitive) < 0) 539 { 540 smaller = first; 541 } 542 else 543 { 544 smaller = second; 545 } 546 547 if (result == NULL) 548 { 549 /* start merged list with the smaller element */ 550 result_tail = smaller; 551 result = smaller; 552 } 553 else 554 { 555 /* add smaller element to the list */ 556 result_tail->next = smaller; 557 smaller->prev = result_tail; 558 result_tail = smaller; 559 } 560 561 if (first == smaller) 562 { 563 first = first->next; 564 } 565 else 566 { 567 second = second->next; 568 } 569 } 570 571 if (first != NULL) 572 { 573 /* Append rest of first list. */ 574 if (result == NULL) 575 { 576 return first; 577 } 578 result_tail->next = first; 579 first->prev = result_tail; 580 } 581 if (second != NULL) 582 { 583 /* Append rest of second list */ 584 if (result == NULL) 585 { 586 return second; 587 } 588 result_tail->next = second; 589 second->prev = result_tail; 590 } 591 592 return result; 593} 594 595static void sort_object(cJSON * const object, const cJSON_bool case_sensitive) 596{ 597 if (object == NULL) 598 { 599 return; 600 } 601 object->child = sort_list(object->child, case_sensitive); 602} 603 604static cJSON_bool compare_json(cJSON *a, cJSON *b, const cJSON_bool case_sensitive) 605{ 606 if ((a == NULL) || (b == NULL) || ((a->type & 0xFF) != (b->type & 0xFF))) 607 { 608 /* mismatched type. */ 609 return false; 610 } 611 switch (a->type & 0xFF) 612 { 613#ifdef __CJSON_USE_INT64 614 case cJSON_Number: 615 /* numeric mismatch. */ 616 if ((a->valueint != b->valueint) || (!compare_double(a->valuedouble, b->valuedouble))) 617 { 618 return false; 619 } 620 621 if ((a->type & cJSON_IsInt64) != (b->type & cJSON_IsInt64)) 622 { 623 /* cJSON_IsInt64 should also be considered */ 624 return false; 625 } 626 627 return true; 628#else 629 case cJSON_Number: 630 /* numeric mismatch. */ 631 if ((a->valueint != b->valueint) || (!compare_double(a->valuedouble, b->valuedouble))) 632 { 633 return false; 634 } 635 else 636 { 637 return true; 638 } 639#endif /* __CJSON_USE_INT64 */ 640 641 case cJSON_String: 642 /* string mismatch. */ 643 if (strcmp(a->valuestring, b->valuestring) != 0) 644 { 645 return false; 646 } 647 else 648 { 649 return true; 650 } 651 652 case cJSON_Array: 653 for ((void)(a = a->child), b = b->child; (a != NULL) && (b != NULL); (void)(a = a->next), b = b->next) 654 { 655 cJSON_bool identical = compare_json(a, b, case_sensitive); 656 if (!identical) 657 { 658 return false; 659 } 660 } 661 662 /* array size mismatch? (one of both children is not NULL) */ 663 if ((a != NULL) || (b != NULL)) 664 { 665 return false; 666 } 667 else 668 { 669 return true; 670 } 671 672 case cJSON_Object: 673 sort_object(a, case_sensitive); 674 sort_object(b, case_sensitive); 675 for ((void)(a = a->child), b = b->child; (a != NULL) && (b != NULL); (void)(a = a->next), b = b->next) 676 { 677 cJSON_bool identical = false; 678 /* compare object keys */ 679 if (compare_strings((unsigned char*)a->string, (unsigned char*)b->string, case_sensitive)) 680 { 681 /* missing member */ 682 return false; 683 } 684 identical = compare_json(a, b, case_sensitive); 685 if (!identical) 686 { 687 return false; 688 } 689 } 690 691 /* object length mismatch (one of both children is not null) */ 692 if ((a != NULL) || (b != NULL)) 693 { 694 return false; 695 } 696 else 697 { 698 return true; 699 } 700 701 default: 702 break; 703 } 704 705 /* null, true or false */ 706 return true; 707} 708 709/* non broken version of cJSON_InsertItemInArray */ 710static cJSON_bool insert_item_in_array(cJSON *array, size_t which, cJSON *newitem) 711{ 712 cJSON *child = array->child; 713 while (child && (which > 0)) 714 { 715 child = child->next; 716 which--; 717 } 718 if (which > 0) 719 { 720 /* item is after the end of the array */ 721 return 0; 722 } 723 if (child == NULL) 724 { 725 cJSON_AddItemToArray(array, newitem); 726 return 1; 727 } 728 729 /* insert into the linked list */ 730 newitem->next = child; 731 newitem->prev = child->prev; 732 child->prev = newitem; 733 734 /* was it at the beginning */ 735 if (child == array->child) 736 { 737 array->child = newitem; 738 } 739 else 740 { 741 newitem->prev->next = newitem; 742 } 743 744 return 1; 745} 746 747static cJSON *get_object_item(const cJSON * const object, const char* name, const cJSON_bool case_sensitive) 748{ 749 if (case_sensitive) 750 { 751 return cJSON_GetObjectItemCaseSensitive(object, name); 752 } 753 754 return cJSON_GetObjectItem(object, name); 755} 756 757enum patch_operation { INVALID, ADD, REMOVE, REPLACE, MOVE, COPY, TEST }; 758 759static enum patch_operation decode_patch_operation(const cJSON * const patch, const cJSON_bool case_sensitive) 760{ 761 cJSON *operation = get_object_item(patch, "op", case_sensitive); 762 if (!cJSON_IsString(operation)) 763 { 764 return INVALID; 765 } 766 767 if (strcmp(operation->valuestring, "add") == 0) 768 { 769 return ADD; 770 } 771 772 if (strcmp(operation->valuestring, "remove") == 0) 773 { 774 return REMOVE; 775 } 776 777 if (strcmp(operation->valuestring, "replace") == 0) 778 { 779 return REPLACE; 780 } 781 782 if (strcmp(operation->valuestring, "move") == 0) 783 { 784 return MOVE; 785 } 786 787 if (strcmp(operation->valuestring, "copy") == 0) 788 { 789 return COPY; 790 } 791 792 if (strcmp(operation->valuestring, "test") == 0) 793 { 794 return TEST; 795 } 796 797 return INVALID; 798} 799 800/* overwrite and existing item with another one and free resources on the way */ 801static void overwrite_item(cJSON * const root, const cJSON replacement) 802{ 803 if (root == NULL) 804 { 805 return; 806 } 807 808 if (root->string != NULL) 809 { 810 cJSON_free(root->string); 811 } 812 if (root->valuestring != NULL) 813 { 814 cJSON_free(root->valuestring); 815 } 816 if (root->child != NULL) 817 { 818 cJSON_Delete(root->child); 819 } 820 821 memcpy(root, &replacement, sizeof(cJSON)); 822} 823 824static int apply_patch(cJSON *object, const cJSON *patch, const cJSON_bool case_sensitive) 825{ 826 cJSON *path = NULL; 827 cJSON *value = NULL; 828 cJSON *parent = NULL; 829 enum patch_operation opcode = INVALID; 830 unsigned char *parent_pointer = NULL; 831 unsigned char *child_pointer = NULL; 832 int status = 0; 833 834 path = get_object_item(patch, "path", case_sensitive); 835 if (!cJSON_IsString(path)) 836 { 837 /* malformed patch. */ 838 status = 2; 839 goto cleanup; 840 } 841 842 opcode = decode_patch_operation(patch, case_sensitive); 843 if (opcode == INVALID) 844 { 845 status = 3; 846 goto cleanup; 847 } 848 else if (opcode == TEST) 849 { 850 /* compare value: {...} with the given path */ 851 status = !compare_json(get_item_from_pointer(object, path->valuestring, case_sensitive), get_object_item(patch, "value", case_sensitive), case_sensitive); 852 goto cleanup; 853 } 854 855 /* special case for replacing the root */ 856 if (path->valuestring[0] == '\0') 857 { 858 if (opcode == REMOVE) 859 { 860 static const cJSON invalid = { NULL, NULL, NULL, cJSON_Invalid, NULL, 0, 0, NULL}; 861 862 overwrite_item(object, invalid); 863 864 status = 0; 865 goto cleanup; 866 } 867 868 if ((opcode == REPLACE) || (opcode == ADD)) 869 { 870 value = get_object_item(patch, "value", case_sensitive); 871 if (value == NULL) 872 { 873 /* missing "value" for add/replace. */ 874 status = 7; 875 goto cleanup; 876 } 877 878 value = cJSON_Duplicate(value, 1); 879 if (value == NULL) 880 { 881 /* out of memory for add/replace. */ 882 status = 8; 883 goto cleanup; 884 } 885 886 overwrite_item(object, *value); 887 888 /* delete the duplicated value */ 889 cJSON_free(value); 890 value = NULL; 891 892 /* the string "value" isn't needed */ 893 if (object->string != NULL) 894 { 895 cJSON_free(object->string); 896 object->string = NULL; 897 } 898 899 status = 0; 900 goto cleanup; 901 } 902 } 903 904 if ((opcode == REMOVE) || (opcode == REPLACE)) 905 { 906 /* Get rid of old. */ 907 cJSON *old_item = detach_path(object, (unsigned char*)path->valuestring, case_sensitive); 908 if (old_item == NULL) 909 { 910 status = 13; 911 goto cleanup; 912 } 913 cJSON_Delete(old_item); 914 if (opcode == REMOVE) 915 { 916 /* For Remove, this job is done. */ 917 status = 0; 918 goto cleanup; 919 } 920 } 921 922 /* Copy/Move uses "from". */ 923 if ((opcode == MOVE) || (opcode == COPY)) 924 { 925 cJSON *from = get_object_item(patch, "from", case_sensitive); 926 if (from == NULL) 927 { 928 /* missing "from" for copy/move. */ 929 status = 4; 930 goto cleanup; 931 } 932 933 if (opcode == MOVE) 934 { 935 value = detach_path(object, (unsigned char*)from->valuestring, case_sensitive); 936 } 937 if (opcode == COPY) 938 { 939 value = get_item_from_pointer(object, from->valuestring, case_sensitive); 940 } 941 if (value == NULL) 942 { 943 /* missing "from" for copy/move. */ 944 status = 5; 945 goto cleanup; 946 } 947 if (opcode == COPY) 948 { 949 value = cJSON_Duplicate(value, 1); 950 } 951 if (value == NULL) 952 { 953 /* out of memory for copy/move. */ 954 status = 6; 955 goto cleanup; 956 } 957 } 958 else /* Add/Replace uses "value". */ 959 { 960 value = get_object_item(patch, "value", case_sensitive); 961 if (value == NULL) 962 { 963 /* missing "value" for add/replace. */ 964 status = 7; 965 goto cleanup; 966 } 967 value = cJSON_Duplicate(value, 1); 968 if (value == NULL) 969 { 970 /* out of memory for add/replace. */ 971 status = 8; 972 goto cleanup; 973 } 974 } 975 976 /* Now, just add "value" to "path". */ 977 978 /* split pointer in parent and child */ 979 parent_pointer = cJSONUtils_strdup((unsigned char*)path->valuestring); 980 if (parent_pointer) { 981 child_pointer = (unsigned char*)strrchr((char*)parent_pointer, '/'); 982 } 983 if (child_pointer != NULL) 984 { 985 child_pointer[0] = '\0'; 986 child_pointer++; 987 } 988 parent = get_item_from_pointer(object, (char*)parent_pointer, case_sensitive); 989 decode_pointer_inplace(child_pointer); 990 991 /* add, remove, replace, move, copy, test. */ 992 if ((parent == NULL) || (child_pointer == NULL)) 993 { 994 /* Couldn't find object to add to. */ 995 status = 9; 996 goto cleanup; 997 } 998 else if (cJSON_IsArray(parent)) 999 { 1000 if (strcmp((char*)child_pointer, "-") == 0) 1001 { 1002 cJSON_AddItemToArray(parent, value); 1003 value = NULL; 1004 } 1005 else 1006 { 1007 size_t index = 0; 1008 if (!decode_array_index_from_pointer(child_pointer, &index)) 1009 { 1010 status = 11; 1011 goto cleanup; 1012 } 1013 1014 if (!insert_item_in_array(parent, index, value)) 1015 { 1016 status = 10; 1017 goto cleanup; 1018 } 1019 value = NULL; 1020 } 1021 } 1022 else if (cJSON_IsObject(parent)) 1023 { 1024 if (case_sensitive) 1025 { 1026 cJSON_DeleteItemFromObjectCaseSensitive(parent, (char*)child_pointer); 1027 } 1028 else 1029 { 1030 cJSON_DeleteItemFromObject(parent, (char*)child_pointer); 1031 } 1032 cJSON_AddItemToObject(parent, (char*)child_pointer, value); 1033 value = NULL; 1034 } 1035 else /* parent is not an object */ 1036 { 1037 /* Couldn't find object to add to. */ 1038 status = 9; 1039 goto cleanup; 1040 } 1041 1042cleanup: 1043 if (value != NULL) 1044 { 1045 cJSON_Delete(value); 1046 } 1047 if (parent_pointer != NULL) 1048 { 1049 cJSON_free(parent_pointer); 1050 } 1051 1052 return status; 1053} 1054 1055CJSON_PUBLIC(int) cJSONUtils_ApplyPatches(cJSON * const object, const cJSON * const patches) 1056{ 1057 const cJSON *current_patch = NULL; 1058 int status = 0; 1059 1060 if (!cJSON_IsArray(patches)) 1061 { 1062 /* malformed patches. */ 1063 return 1; 1064 } 1065 1066 if (patches != NULL) 1067 { 1068 current_patch = patches->child; 1069 } 1070 1071 while (current_patch != NULL) 1072 { 1073 status = apply_patch(object, current_patch, false); 1074 if (status != 0) 1075 { 1076 return status; 1077 } 1078 current_patch = current_patch->next; 1079 } 1080 1081 return 0; 1082} 1083 1084CJSON_PUBLIC(int) cJSONUtils_ApplyPatchesCaseSensitive(cJSON * const object, const cJSON * const patches) 1085{ 1086 const cJSON *current_patch = NULL; 1087 int status = 0; 1088 1089 if (!cJSON_IsArray(patches)) 1090 { 1091 /* malformed patches. */ 1092 return 1; 1093 } 1094 1095 if (patches != NULL) 1096 { 1097 current_patch = patches->child; 1098 } 1099 1100 while (current_patch != NULL) 1101 { 1102 status = apply_patch(object, current_patch, true); 1103 if (status != 0) 1104 { 1105 return status; 1106 } 1107 current_patch = current_patch->next; 1108 } 1109 1110 return 0; 1111} 1112 1113static void compose_patch(cJSON * const patches, const unsigned char * const operation, const unsigned char * const path, const unsigned char *suffix, const cJSON * const value) 1114{ 1115 cJSON *patch = NULL; 1116 1117 if ((patches == NULL) || (operation == NULL) || (path == NULL)) 1118 { 1119 return; 1120 } 1121 1122 patch = cJSON_CreateObject(); 1123 if (patch == NULL) 1124 { 1125 return; 1126 } 1127 cJSON_AddItemToObject(patch, "op", cJSON_CreateString((const char*)operation)); 1128 1129 if (suffix == NULL) 1130 { 1131 cJSON_AddItemToObject(patch, "path", cJSON_CreateString((const char*)path)); 1132 } 1133 else 1134 { 1135 size_t suffix_length = pointer_encoded_length(suffix); 1136 size_t path_length = strlen((const char*)path); 1137 unsigned char *full_path = (unsigned char*)cJSON_malloc(path_length + suffix_length + sizeof("/")); 1138 1139 sprintf((char*)full_path, "%s/", (const char*)path); 1140 encode_string_as_pointer(full_path + path_length + 1, suffix); 1141 1142 cJSON_AddItemToObject(patch, "path", cJSON_CreateString((const char*)full_path)); 1143 cJSON_free(full_path); 1144 } 1145 1146 if (value != NULL) 1147 { 1148 cJSON_AddItemToObject(patch, "value", cJSON_Duplicate(value, 1)); 1149 } 1150 cJSON_AddItemToArray(patches, patch); 1151} 1152 1153CJSON_PUBLIC(void) cJSONUtils_AddPatchToArray(cJSON * const array, const char * const operation, const char * const path, const cJSON * const value) 1154{ 1155 compose_patch(array, (const unsigned char*)operation, (const unsigned char*)path, NULL, value); 1156} 1157 1158static void create_patches(cJSON * const patches, const unsigned char * const path, cJSON * const from, cJSON * const to, const cJSON_bool case_sensitive) 1159{ 1160 if ((from == NULL) || (to == NULL)) 1161 { 1162 return; 1163 } 1164 1165 if ((from->type & 0xFF) != (to->type & 0xFF)) 1166 { 1167 compose_patch(patches, (const unsigned char*)"replace", path, 0, to); 1168 return; 1169 } 1170 1171 switch (from->type & 0xFF) 1172 { 1173 case cJSON_Number: 1174 if ((from->valueint != to->valueint) || !compare_double(from->valuedouble, to->valuedouble)) 1175 { 1176 compose_patch(patches, (const unsigned char*)"replace", path, NULL, to); 1177 } 1178 return; 1179 1180 case cJSON_String: 1181 if (strcmp(from->valuestring, to->valuestring) != 0) 1182 { 1183 compose_patch(patches, (const unsigned char*)"replace", path, NULL, to); 1184 } 1185 return; 1186 1187 case cJSON_Array: 1188 { 1189 size_t index = 0; 1190 cJSON *from_child = from->child; 1191 cJSON *to_child = to->child; 1192 unsigned char *new_path = (unsigned char*)cJSON_malloc(strlen((const char*)path) + 20 + sizeof("/")); /* Allow space for 64bit int. log10(2^64) = 20 */ 1193 1194 /* generate patches for all array elements that exist in both "from" and "to" */ 1195 for (index = 0; (from_child != NULL) && (to_child != NULL); (void)(from_child = from_child->next), (void)(to_child = to_child->next), index++) 1196 { 1197 /* check if conversion to unsigned long is valid 1198 * This should be eliminated at compile time by dead code elimination 1199 * if size_t is an alias of unsigned long, or if it is bigger */ 1200 if (index > ULONG_MAX) 1201 { 1202 cJSON_free(new_path); 1203 return; 1204 } 1205 sprintf((char*)new_path, "%s/%lu", path, (unsigned long)index); /* path of the current array element */ 1206 create_patches(patches, new_path, from_child, to_child, case_sensitive); 1207 } 1208 1209 /* remove leftover elements from 'from' that are not in 'to' */ 1210 for (; (from_child != NULL); (void)(from_child = from_child->next)) 1211 { 1212 /* check if conversion to unsigned long is valid 1213 * This should be eliminated at compile time by dead code elimination 1214 * if size_t is an alias of unsigned long, or if it is bigger */ 1215 if (index > ULONG_MAX) 1216 { 1217 cJSON_free(new_path); 1218 return; 1219 } 1220 sprintf((char*)new_path, "%lu", (unsigned long)index); 1221 compose_patch(patches, (const unsigned char*)"remove", path, new_path, NULL); 1222 } 1223 /* add new elements in 'to' that were not in 'from' */ 1224 for (; (to_child != NULL); (void)(to_child = to_child->next), index++) 1225 { 1226 compose_patch(patches, (const unsigned char*)"add", path, (const unsigned char*)"-", to_child); 1227 } 1228 cJSON_free(new_path); 1229 return; 1230 } 1231 1232 case cJSON_Object: 1233 { 1234 cJSON *from_child = NULL; 1235 cJSON *to_child = NULL; 1236 sort_object(from, case_sensitive); 1237 sort_object(to, case_sensitive); 1238 1239 from_child = from->child; 1240 to_child = to->child; 1241 /* for all object values in the object with more of them */ 1242 while ((from_child != NULL) || (to_child != NULL)) 1243 { 1244 int diff; 1245 if (from_child == NULL) 1246 { 1247 diff = 1; 1248 } 1249 else if (to_child == NULL) 1250 { 1251 diff = -1; 1252 } 1253 else 1254 { 1255 diff = compare_strings((unsigned char*)from_child->string, (unsigned char*)to_child->string, case_sensitive); 1256 } 1257 1258 if (diff == 0) 1259 { 1260 /* both object keys are the same */ 1261 size_t path_length = strlen((const char*)path); 1262 size_t from_child_name_length = pointer_encoded_length((unsigned char*)from_child->string); 1263 unsigned char *new_path = (unsigned char*)cJSON_malloc(path_length + from_child_name_length + sizeof("/")); 1264 1265 sprintf((char*)new_path, "%s/", path); 1266 encode_string_as_pointer(new_path + path_length + 1, (unsigned char*)from_child->string); 1267 1268 /* create a patch for the element */ 1269 create_patches(patches, new_path, from_child, to_child, case_sensitive); 1270 cJSON_free(new_path); 1271 1272 from_child = from_child->next; 1273 to_child = to_child->next; 1274 } 1275 else if (diff < 0) 1276 { 1277 /* object element doesn't exist in 'to' --> remove it */ 1278 compose_patch(patches, (const unsigned char*)"remove", path, (unsigned char*)from_child->string, NULL); 1279 1280 from_child = from_child->next; 1281 } 1282 else 1283 { 1284 /* object element doesn't exist in 'from' --> add it */ 1285 compose_patch(patches, (const unsigned char*)"add", path, (unsigned char*)to_child->string, to_child); 1286 1287 to_child = to_child->next; 1288 } 1289 } 1290 return; 1291 } 1292 1293 default: 1294 break; 1295 } 1296} 1297 1298CJSON_PUBLIC(cJSON *) cJSONUtils_GeneratePatches(cJSON * const from, cJSON * const to) 1299{ 1300 cJSON *patches = NULL; 1301 1302 if ((from == NULL) || (to == NULL)) 1303 { 1304 return NULL; 1305 } 1306 1307 patches = cJSON_CreateArray(); 1308 create_patches(patches, (const unsigned char*)"", from, to, false); 1309 1310 return patches; 1311} 1312 1313CJSON_PUBLIC(cJSON *) cJSONUtils_GeneratePatchesCaseSensitive(cJSON * const from, cJSON * const to) 1314{ 1315 cJSON *patches = NULL; 1316 1317 if ((from == NULL) || (to == NULL)) 1318 { 1319 return NULL; 1320 } 1321 1322 patches = cJSON_CreateArray(); 1323 create_patches(patches, (const unsigned char*)"", from, to, true); 1324 1325 return patches; 1326} 1327 1328CJSON_PUBLIC(void) cJSONUtils_SortObject(cJSON * const object) 1329{ 1330 sort_object(object, false); 1331} 1332 1333CJSON_PUBLIC(void) cJSONUtils_SortObjectCaseSensitive(cJSON * const object) 1334{ 1335 sort_object(object, true); 1336} 1337 1338static cJSON *merge_patch(cJSON *target, const cJSON * const patch, const cJSON_bool case_sensitive) 1339{ 1340 cJSON *patch_child = NULL; 1341 1342 if (!cJSON_IsObject(patch)) 1343 { 1344 /* scalar value, array or NULL, just duplicate */ 1345 cJSON_Delete(target); 1346 return cJSON_Duplicate(patch, 1); 1347 } 1348 1349 if (!cJSON_IsObject(target)) 1350 { 1351 cJSON_Delete(target); 1352 target = cJSON_CreateObject(); 1353 } 1354 1355 patch_child = patch->child; 1356 while (patch_child != NULL) 1357 { 1358 if (cJSON_IsNull(patch_child)) 1359 { 1360 /* NULL is the indicator to remove a value, see RFC7396 */ 1361 if (case_sensitive) 1362 { 1363 cJSON_DeleteItemFromObjectCaseSensitive(target, patch_child->string); 1364 } 1365 else 1366 { 1367 cJSON_DeleteItemFromObject(target, patch_child->string); 1368 } 1369 } 1370 else 1371 { 1372 cJSON *replace_me = NULL; 1373 cJSON *replacement = NULL; 1374 1375 if (case_sensitive) 1376 { 1377 replace_me = cJSON_DetachItemFromObjectCaseSensitive(target, patch_child->string); 1378 } 1379 else 1380 { 1381 replace_me = cJSON_DetachItemFromObject(target, patch_child->string); 1382 } 1383 1384 replacement = merge_patch(replace_me, patch_child, case_sensitive); 1385 if (replacement == NULL) 1386 { 1387 cJSON_Delete(target); 1388 return NULL; 1389 } 1390 1391 cJSON_AddItemToObject(target, patch_child->string, replacement); 1392 } 1393 patch_child = patch_child->next; 1394 } 1395 return target; 1396} 1397 1398CJSON_PUBLIC(cJSON *) cJSONUtils_MergePatch(cJSON *target, const cJSON * const patch) 1399{ 1400 return merge_patch(target, patch, false); 1401} 1402 1403CJSON_PUBLIC(cJSON *) cJSONUtils_MergePatchCaseSensitive(cJSON *target, const cJSON * const patch) 1404{ 1405 return merge_patch(target, patch, true); 1406} 1407 1408static cJSON *generate_merge_patch(cJSON * const from, cJSON * const to, const cJSON_bool case_sensitive) 1409{ 1410 cJSON *from_child = NULL; 1411 cJSON *to_child = NULL; 1412 cJSON *patch = NULL; 1413 if (to == NULL) 1414 { 1415 /* patch to delete everything */ 1416 return cJSON_CreateNull(); 1417 } 1418 if (!cJSON_IsObject(to) || !cJSON_IsObject(from)) 1419 { 1420 return cJSON_Duplicate(to, 1); 1421 } 1422 1423 sort_object(from, case_sensitive); 1424 sort_object(to, case_sensitive); 1425 1426 from_child = from->child; 1427 to_child = to->child; 1428 patch = cJSON_CreateObject(); 1429 if (patch == NULL) 1430 { 1431 return NULL; 1432 } 1433 while (from_child || to_child) 1434 { 1435 int diff; 1436 if (from_child != NULL) 1437 { 1438 if (to_child != NULL) 1439 { 1440 diff = strcmp(from_child->string, to_child->string); 1441 } 1442 else 1443 { 1444 diff = -1; 1445 } 1446 } 1447 else 1448 { 1449 diff = 1; 1450 } 1451 1452 if (diff < 0) 1453 { 1454 /* from has a value that to doesn't have -> remove */ 1455 cJSON_AddItemToObject(patch, from_child->string, cJSON_CreateNull()); 1456 1457 from_child = from_child->next; 1458 } 1459 else if (diff > 0) 1460 { 1461 /* to has a value that from doesn't have -> add to patch */ 1462 cJSON_AddItemToObject(patch, to_child->string, cJSON_Duplicate(to_child, 1)); 1463 1464 to_child = to_child->next; 1465 } 1466 else 1467 { 1468 /* object key exists in both objects */ 1469 if (!compare_json(from_child, to_child, case_sensitive)) 1470 { 1471 /* not identical --> generate a patch */ 1472 cJSON_AddItemToObject(patch, to_child->string, cJSONUtils_GenerateMergePatch(from_child, to_child)); 1473 } 1474 1475 /* next key in the object */ 1476 from_child = from_child->next; 1477 to_child = to_child->next; 1478 } 1479 } 1480 if (patch->child == NULL) 1481 { 1482 /* no patch generated */ 1483 cJSON_Delete(patch); 1484 return NULL; 1485 } 1486 1487 return patch; 1488} 1489 1490CJSON_PUBLIC(cJSON *) cJSONUtils_GenerateMergePatch(cJSON * const from, cJSON * const to) 1491{ 1492 return generate_merge_patch(from, to, false); 1493} 1494 1495CJSON_PUBLIC(cJSON *) cJSONUtils_GenerateMergePatchCaseSensitive(cJSON * const from, cJSON * const to) 1496{ 1497 return generate_merge_patch(from, to, true); 1498} 1499