cJSON_Utils.c 37.9 KB
Newer Older
M
Max Bruckner 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
/*
  Copyright (c) 2009-2017 Dave Gamble and cJSON contributors

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  THE SOFTWARE.
*/

23
#pragma GCC visibility push(default)
24
#include <ctype.h>
25 26
#include <string.h>
#include <stdlib.h>
27
#include <stdio.h>
M
Max Bruckner 已提交
28
#include <limits.h>
29
#pragma GCC visibility pop
M
Max Bruckner 已提交
30

31 32
#include "cJSON_Utils.h"

M
Max Bruckner 已提交
33 34 35 36
/* define our own boolean type */
#define true ((cJSON_bool)1)
#define false ((cJSON_bool)0)

M
Max Bruckner 已提交
37
static unsigned char* cJSONUtils_strdup(const unsigned char* const string)
38
{
M
Max Bruckner 已提交
39
    size_t length = 0;
40
    unsigned char *copy = NULL;
41

M
Max Bruckner 已提交
42 43 44
    length = strlen((const char*)string) + sizeof("");
    copy = (unsigned char*) cJSON_malloc(length);
    if (copy == NULL)
45
    {
46
        return NULL;
47
    }
M
Max Bruckner 已提交
48
    memcpy(copy, string, length);
49 50 51 52

    return copy;
}

53 54
/* string comparison which doesn't consider NULL pointers equal */
static int compare_strings(const unsigned char *string1, const unsigned char *string2, const cJSON_bool case_sensitive)
55
{
M
Max Bruckner 已提交
56
    if ((string1 == NULL) || (string2 == NULL))
M
Max Bruckner 已提交
57
    {
M
Max Bruckner 已提交
58
        return 1;
M
Max Bruckner 已提交
59
    }
M
Max Bruckner 已提交
60 61

    if (string1 == string2)
M
Max Bruckner 已提交
62
    {
M
Max Bruckner 已提交
63
        return 0;
M
Max Bruckner 已提交
64
    }
M
Max Bruckner 已提交
65

66 67 68 69 70
    if (case_sensitive)
    {
        return strcmp((const char*)string1, (const char*)string2);
    }

M
Max Bruckner 已提交
71
    for(; tolower(*string1) == tolower(*string2); (void)string1++, string2++)
M
Max Bruckner 已提交
72
    {
M
Max Bruckner 已提交
73
        if (*string1 == '\0')
M
Max Bruckner 已提交
74 75 76 77 78
        {
            return 0;
        }
    }

M
Max Bruckner 已提交
79
    return tolower(*string1) - tolower(*string2);
80 81
}

M
Max Bruckner 已提交
82
/* Compare the next path element of two JSON pointers, two NULL pointers are considered unequal: */
83
static cJSON_bool compare_pointers(const unsigned char *name, const unsigned char *pointer, const cJSON_bool case_sensitive)
84
{
M
Max Bruckner 已提交
85
    if ((name == NULL) || (pointer == NULL))
86
    {
87
        return false;
88
    }
M
Max Bruckner 已提交
89 90

    for (; (*name != '\0') && (*pointer != '\0') && (*pointer != '/'); (void)name++, pointer++) /* compare until next '/' */
91
    {
M
Max Bruckner 已提交
92
        if (*pointer == '~')
93 94
        {
            /* check for escaped '~' (~0) and '/' (~1) */
M
Max Bruckner 已提交
95
            if (((pointer[1] != '0') || (*name != '~')) && ((pointer[1] != '1') || (*name != '/')))
96
            {
M
Max Bruckner 已提交
97
                /* invalid escape sequence or wrong character in *name */
98
                return false;
99 100 101
            }
            else
            {
M
Max Bruckner 已提交
102
                pointer++;
103 104
            }
        }
105
        else if ((!case_sensitive && (tolower(*name) != tolower(*pointer))) || (case_sensitive && (*name != *pointer)))
106
        {
107
            return false;
108 109
        }
    }
M
Max Bruckner 已提交
110
    if (((*pointer != 0) && (*pointer != '/')) != (*name != 0))
111 112
    {
        /* one string has ended, the other not */
113
        return false;;
114 115
    }

116
    return true;
117 118
}

119
/* calculate the length of a string if encoded as JSON pointer with ~0 and ~1 escape sequences */
120
static size_t pointer_encoded_length(const unsigned char *string)
121
{
122 123
    size_t length;
    for (length = 0; *string != '\0'; (void)string++, length++)
124
    {
125 126
        /* character needs to be escaped? */
        if ((*string == '~') || (*string == '/'))
127
        {
128
            length++;
129 130 131
        }
    }

132
    return length;
133
}
134

135
/* copy a string while escaping '~' and '/' with ~0 and ~1 JSON pointer escape codes */
136
static void encode_string_as_pointer(unsigned char *destination, const unsigned char *source)
137
{
138
    for (; source[0] != '\0'; (void)source++, destination++)
139
    {
140
        if (source[0] == '/')
141
        {
142 143
            destination[1] = '1';
            destination++;
144
        }
145
        else if (source[0] == '~')
146
        {
147 148 149
            destination[0] = '~';
            destination[1] = '1';
            destination++;
150 151 152
        }
        else
        {
153
            destination[0] = source[0];
154 155 156
        }
    }

157
    destination[0] = '\0';
158 159
}

160
CJSON_PUBLIC(char *) cJSONUtils_FindPointerFromObjectTo(const cJSON * const object, const cJSON * const target)
161
{
162 163
    size_t child_index = 0;
    cJSON *current_child = 0;
164

165 166 167
    if (object == target)
    {
        /* found */
168
        return (char*)cJSONUtils_strdup((const unsigned char*)"");
169
    }
170

171 172
    /* recursively search all children of the object or array */
    for (current_child = object->child; current_child != NULL; (void)(current_child = current_child->next), child_index++)
173
    {
174 175 176
        unsigned char *target_pointer = (unsigned char*)cJSONUtils_FindPointerFromObjectTo(current_child, target);
        /* found the target? */
        if (target_pointer != NULL)
177
        {
178
            if (cJSON_IsArray(object))
179 180
            {
                /* reserve enough memory for a 64 bit integer + '/' and '\0' */
181
                unsigned char *full_pointer = (unsigned char*)cJSON_malloc(strlen((char*)target_pointer) + 20 + sizeof("/"));
182 183 184
                /* check if conversion to unsigned long is valid
                 * This should be eliminated at compile time by dead code elimination
                 * if size_t is an alias of unsigned long, or if it is bigger */
185
                if (child_index > ULONG_MAX)
186
                {
187
                    cJSON_free(target_pointer);
188 189
                    return NULL;
                }
190 191
                sprintf((char*)full_pointer, "/%lu%s", (unsigned long)child_index, target_pointer); /* /<array_index><path> */
                cJSON_free(target_pointer);
192

193
                return (char*)full_pointer;
194
            }
195 196

            if (cJSON_IsObject(object))
197
            {
198
                unsigned char *full_pointer = (unsigned char*)cJSON_malloc(strlen((char*)target_pointer) + pointer_encoded_length((unsigned char*)current_child->string) + 2);
199
                full_pointer[0] = '/';
200
                encode_string_as_pointer(full_pointer + 1, (unsigned char*)current_child->string);
201 202
                strcat((char*)full_pointer, (char*)target_pointer);
                cJSON_free(target_pointer);
203

204
                return (char*)full_pointer;
205 206 207
            }

            /* reached leaf of the tree, found nothing */
208
            cJSON_free(target_pointer);
209
            return NULL;
210 211 212 213
        }
    }

    /* not found */
214
    return NULL;
215 216
}

217 218 219 220 221 222 223 224 225 226 227 228 229
/* non broken version of cJSON_GetArrayItem */
static cJSON *get_array_item(const cJSON *array, size_t item)
{
    cJSON *child = array ? array->child : NULL;
    while ((child != NULL) && (item > 0))
    {
        item--;
        child = child->next;
    }

    return child;
}

230 231 232 233 234 235 236 237 238 239 240
static cJSON_bool decode_array_index_from_pointer(const unsigned char * const pointer, size_t * const index)
{
    size_t parsed_index = 0;
    size_t position = 0;

    if ((pointer[0] == '0') && ((pointer[1] != '\0') && (pointer[1] != '/')))
    {
        /* leading zeroes are not permitted */
        return 0;
    }

241
    for (position = 0; (pointer[position] >= '0') && (pointer[0] <= '9'); position++)
242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
    {
        parsed_index = (10 * parsed_index) + (size_t)(pointer[position] - '0');

    }

    if ((pointer[position] != '\0') && (pointer[position] != '/'))
    {
        return 0;
    }

    *index = parsed_index;

    return 1;
}

257
static cJSON *get_item_from_pointer(cJSON * const object, const char * pointer, const cJSON_bool case_sensitive)
258
{
M
Max Bruckner 已提交
259
    cJSON *current_element = object;
260
    /* follow path of the pointer */
M
Max Bruckner 已提交
261
    while ((pointer[0] == '/') && (current_element != NULL))
262
    {
M
Max Bruckner 已提交
263 264
        pointer++;
        if (cJSON_IsArray(current_element))
265
        {
266
            size_t index = 0;
267
            if (!decode_array_index_from_pointer((const unsigned char*)pointer, &index))
268
            {
269
                return NULL;
270
            }
271

M
Max Bruckner 已提交
272
            current_element = get_array_item(current_element, index);
273
        }
M
Max Bruckner 已提交
274
        else if (cJSON_IsObject(current_element))
275
        {
M
Max Bruckner 已提交
276
            current_element = current_element->child;
277
            /* GetObjectItem. */
278
            while ((current_element != NULL) && !compare_pointers((unsigned char*)current_element->string, (const unsigned char*)pointer, case_sensitive))
279
            {
M
Max Bruckner 已提交
280
                current_element = current_element->next;
281 282
            }
            /* skip to the next path token or end of string */
M
Max Bruckner 已提交
283
            while ((pointer[0] != '\0') && (pointer[0] != '/'))
284 285 286 287 288 289
            {
                pointer++;
            }
        }
        else
        {
290
            return NULL;
291 292 293
        }
    }

M
Max Bruckner 已提交
294
    return current_element;
295 296
}

297 298 299 300 301
CJSON_PUBLIC(cJSON *) cJSONUtils_GetPointer(cJSON * const object, const char *pointer)
{
    return get_item_from_pointer(object, pointer, false);
}

302 303 304 305 306
CJSON_PUBLIC(cJSON *) cJSONUtils_GetPointerCaseSensitive(cJSON * const object, const char *pointer)
{
    return get_item_from_pointer(object, pointer, true);
}

307
/* JSON Patch implementation. */
308
static void decode_pointer_inplace(unsigned char *string)
309
{
310
    unsigned char *decoded_string = string;
311 312 313 314 315

    if (string == NULL) {
        return;
    }

316
    for (; *string; (void)decoded_string++, string++)
317
    {
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335
        if (string[0] == '~')
        {
            if (string[1] == '0')
            {
                decoded_string[0] = '~';
            }
            else if (string[1] == '1')
            {
                decoded_string[1] = '/';
            }
            else
            {
                /* invalid escape sequence */
                return;
            }

            string++;
        }
336 337
    }

338
    decoded_string[0] = '\0';
339 340
}

341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373
/* non-broken cJSON_DetachItemFromArray */
static cJSON *detach_item_from_array(cJSON *array, size_t which)
{
    cJSON *c = array->child;
    while (c && (which > 0))
    {
        c = c->next;
        which--;
    }
    if (!c)
    {
        /* item doesn't exist */
        return NULL;
    }
    if (c->prev)
    {
        /* not the first element */
        c->prev->next = c->next;
    }
    if (c->next)
    {
        c->next->prev = c->prev;
    }
    if (c==array->child)
    {
        array->child = c->next;
    }
    /* make sure the detached item doesn't point anywhere anymore */
    c->prev = c->next = NULL;

    return c;
}

374
/* detach an item at the given path */
375
static cJSON *detach_path(cJSON *object, const unsigned char *path, const cJSON_bool case_sensitive)
376
{
M
Max Bruckner 已提交
377 378
    unsigned char *parent_pointer = NULL;
    unsigned char *child_pointer = NULL;
379
    cJSON *parent = NULL;
M
Max Bruckner 已提交
380
    cJSON *detached_item = NULL;
381 382

    /* copy path and split it in parent and child */
M
Max Bruckner 已提交
383 384 385
    parent_pointer = cJSONUtils_strdup(path);
    if (parent_pointer == NULL) {
        goto cleanup;
386 387
    }

M
Max Bruckner 已提交
388 389
    child_pointer = (unsigned char*)strrchr((char*)parent_pointer, '/'); /* last '/' */
    if (child_pointer == NULL)
390
    {
M
Max Bruckner 已提交
391
        goto cleanup;
392
    }
393
    /* split strings */
M
Max Bruckner 已提交
394 395
    child_pointer[0] = '\0';
    child_pointer++;
396

397
    parent = get_item_from_pointer(object, (char*)parent_pointer, case_sensitive);
398
    decode_pointer_inplace(child_pointer);
399

M
Max Bruckner 已提交
400
    if (cJSON_IsArray(parent))
401
    {
402
        size_t index = 0;
M
Max Bruckner 已提交
403
        if (!decode_array_index_from_pointer(child_pointer, &index))
404
        {
M
Max Bruckner 已提交
405
            goto cleanup;
406
        }
M
Max Bruckner 已提交
407
        detached_item = detach_item_from_array(parent, index);
408
    }
409
    else if (cJSON_IsObject(parent))
410
    {
M
Max Bruckner 已提交
411 412 413 414 415 416 417 418 419 420 421 422
        detached_item = cJSON_DetachItemFromObject(parent, (char*)child_pointer);
    }
    else
    {
        /* Couldn't find object to remove child from. */
        goto cleanup;
    }

cleanup:
    if (parent_pointer != NULL)
    {
        cJSON_free(parent_pointer);
423
    }
424

M
Max Bruckner 已提交
425
    return detached_item;
426 427
}

428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543
/* sort lists using mergesort */
static cJSON *sort_list(cJSON *list, const cJSON_bool case_sensitive)
{
    cJSON *first = list;
    cJSON *second = list;
    cJSON *current_item = list;
    cJSON *result = list;
    cJSON *result_tail = NULL;

    if ((list == NULL) || (list->next == NULL))
    {
        /* One entry is sorted already. */
        return result;
    }

    while ((current_item != NULL) && (current_item->next != NULL) && (compare_strings((unsigned char*)current_item->string, (unsigned char*)current_item->next->string, case_sensitive) < 0))
    {
        /* Test for list sorted. */
        current_item = current_item->next;
    }
    if ((current_item == NULL) || (current_item->next == NULL))
    {
        /* Leave sorted lists unmodified. */
        return result;
    }

    /* reset pointer to the beginning */
    current_item = list;
    while (current_item != NULL)
    {
        /* Walk two pointers to find the middle. */
        second = second->next;
        current_item = current_item->next;
        /* advances current_item two steps at a time */
        if (current_item != NULL)
        {
            current_item = current_item->next;
        }
    }
    if ((second != NULL) && (second->prev != NULL))
    {
        /* Split the lists */
        second->prev->next = NULL;
    }

    /* Recursively sort the sub-lists. */
    first = sort_list(first, case_sensitive);
    second = sort_list(second, case_sensitive);
    result = NULL;

    /* Merge the sub-lists */
    while ((first != NULL) && (second != NULL))
    {
        cJSON *smaller = NULL;
        if (compare_strings((unsigned char*)first->string, (unsigned char*)second->string, false) < 0)
        {
            smaller = first;
        }
        else
        {
            smaller = second;
        }

        if (result == NULL)
        {
            /* start merged list with the smaller element */
            result_tail = smaller;
            result = smaller;
        }
        else
        {
            /* add smaller element to the list */
            result_tail->next = smaller;
            smaller->prev = result_tail;
            result_tail = smaller;
        }

        if (first == smaller)
        {
            first = first->next;
        }
        else
        {
            second = second->next;
        }
    }

    if (first != NULL)
    {
        /* Append rest of first list. */
        if (result == NULL)
        {
            return first;
        }
        result_tail->next = first;
        first->prev = result_tail;
    }
    if (second != NULL)
    {
        /* Append rest of second list */
        if (result == NULL)
        {
            return second;
        }
        result_tail->next = second;
        second->prev = result_tail;
    }

    return result;
}

static void sort_object(cJSON * const object, const cJSON_bool case_sensitive)
{
    object->child = sort_list(object->child, case_sensitive);
}

544
static cJSON_bool compare_json(cJSON *a, cJSON *b, const cJSON_bool case_sensitive)
545
{
546
    if ((a == NULL) || (b == NULL) || ((a->type & 0xFF) != (b->type & 0xFF)))
M
Max Bruckner 已提交
547 548
    {
        /* mismatched type. */
549
        return false;
M
Max Bruckner 已提交
550
    }
551
    switch (a->type & 0xFF)
M
Max Bruckner 已提交
552 553 554
    {
        case cJSON_Number:
            /* numeric mismatch. */
M
Max Bruckner 已提交
555 556
            if ((a->valueint != b->valueint) || (a->valuedouble != b->valuedouble))
            {
557
                return false;
M
Max Bruckner 已提交
558 559 560
            }
            else
            {
561
                return true;
M
Max Bruckner 已提交
562 563
            }

M
Max Bruckner 已提交
564 565
        case cJSON_String:
            /* string mismatch. */
M
Max Bruckner 已提交
566
            if (strcmp(a->valuestring, b->valuestring) != 0)
M
Max Bruckner 已提交
567
            {
568
                return false;
M
Max Bruckner 已提交
569 570 571
            }
            else
            {
572
                return true;
M
Max Bruckner 已提交
573 574
            }

M
Max Bruckner 已提交
575
        case cJSON_Array:
M
Max Bruckner 已提交
576
            for ((void)(a = a->child), b = b->child; (a != NULL) && (b != NULL); (void)(a = a->next), b = b->next)
M
Max Bruckner 已提交
577
            {
578
                cJSON_bool identical = compare_json(a, b, case_sensitive);
579
                if (!identical)
M
Max Bruckner 已提交
580
                {
581
                    return false;
M
Max Bruckner 已提交
582 583
                }
            }
M
Max Bruckner 已提交
584

M
Max Bruckner 已提交
585
            /* array size mismatch? (one of both children is not NULL) */
M
Max Bruckner 已提交
586 587
            if ((a != NULL) || (b != NULL))
            {
588
                return false;
M
Max Bruckner 已提交
589 590 591
            }
            else
            {
592
                return true;
M
Max Bruckner 已提交
593 594
            }

M
Max Bruckner 已提交
595
        case cJSON_Object:
596 597
            sort_object(a, case_sensitive);
            sort_object(b, case_sensitive);
M
Max Bruckner 已提交
598
            for ((void)(a = a->child), b = b->child; (a != NULL) && (b != NULL); (void)(a = a->next), b = b->next)
M
Max Bruckner 已提交
599
            {
600
                cJSON_bool identical = false;
M
Max Bruckner 已提交
601
                /* compare object keys */
602
                if (compare_strings((unsigned char*)a->string, (unsigned char*)b->string, case_sensitive))
M
Max Bruckner 已提交
603 604
                {
                    /* missing member */
605
                    return false;
M
Max Bruckner 已提交
606
                }
607
                identical = compare_json(a, b, case_sensitive);
608
                if (!identical)
M
Max Bruckner 已提交
609
                {
610
                    return false;
M
Max Bruckner 已提交
611 612
                }
            }
M
Max Bruckner 已提交
613

M
Max Bruckner 已提交
614
            /* object length mismatch (one of both children is not null) */
M
Max Bruckner 已提交
615 616
            if ((a != NULL) || (b != NULL))
            {
617
                return false;
M
Max Bruckner 已提交
618 619 620
            }
            else
            {
621
                return true;
M
Max Bruckner 已提交
622
            }
623

M
Max Bruckner 已提交
624 625 626
        default:
            break;
    }
M
Max Bruckner 已提交
627

M
Max Bruckner 已提交
628
    /* null, true or false */
629
    return true;
630 631
}

632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669
/* non broken version of cJSON_InsertItemInArray */
static cJSON_bool insert_item_in_array(cJSON *array, size_t which, cJSON *newitem)
{
    cJSON *child = array->child;
    while (child && (which > 0))
    {
        child = child->next;
        which--;
    }
    if (which > 0)
    {
        /* item is after the end of the array */
        return 0;
    }
    if (child == NULL)
    {
        cJSON_AddItemToArray(array, newitem);
        return 1;
    }

    /* insert into the linked list */
    newitem->next = child;
    newitem->prev = child->prev;
    child->prev = newitem;

    /* was it at the beginning */
    if (child == array->child)
    {
        array->child = newitem;
    }
    else
    {
        newitem->prev->next = newitem;
    }

    return 1;
}

670 671 672 673 674 675 676 677 678 679
static cJSON *get_object_item(const cJSON * const object, const char* name, const cJSON_bool case_sensitive)
{
    if (case_sensitive)
    {
        return cJSON_GetObjectItemCaseSensitive(object, name);
    }

    return cJSON_GetObjectItem(object, name);
}

M
Max Bruckner 已提交
680 681
enum patch_operation { INVALID, ADD, REMOVE, REPLACE, MOVE, COPY, TEST };

682
static enum patch_operation decode_patch_operation(const cJSON * const patch, const cJSON_bool case_sensitive)
683
{
684
    cJSON *operation = get_object_item(patch, "op", case_sensitive);
M
Max Bruckner 已提交
685 686 687 688
    if (!cJSON_IsString(operation))
    {
        return INVALID;
    }
689

M
Max Bruckner 已提交
690
    if (strcmp(operation->valuestring, "add") == 0)
M
Max Bruckner 已提交
691
    {
M
Max Bruckner 已提交
692
        return ADD;
M
Max Bruckner 已提交
693
    }
694

M
Max Bruckner 已提交
695
    if (strcmp(operation->valuestring, "remove") == 0)
M
Max Bruckner 已提交
696
    {
M
Max Bruckner 已提交
697
        return REMOVE;
M
Max Bruckner 已提交
698
    }
M
Max Bruckner 已提交
699 700

    if (strcmp(operation->valuestring, "replace") == 0)
M
Max Bruckner 已提交
701
    {
M
Max Bruckner 已提交
702
        return REPLACE;
M
Max Bruckner 已提交
703
    }
M
Max Bruckner 已提交
704 705

    if (strcmp(operation->valuestring, "move") == 0)
M
Max Bruckner 已提交
706
    {
M
Max Bruckner 已提交
707
        return MOVE;
M
Max Bruckner 已提交
708
    }
M
Max Bruckner 已提交
709 710

    if (strcmp(operation->valuestring, "copy") == 0)
M
Max Bruckner 已提交
711
    {
M
Max Bruckner 已提交
712
        return COPY;
M
Max Bruckner 已提交
713
    }
M
Max Bruckner 已提交
714 715

    if (strcmp(operation->valuestring, "test") == 0)
M
Max Bruckner 已提交
716
    {
M
Max Bruckner 已提交
717
        return TEST;
M
Max Bruckner 已提交
718
    }
M
Max Bruckner 已提交
719 720 721 722 723 724 725 726

    return INVALID;
}

/* overwrite and existing item with another one and free resources on the way */
static void overwrite_item(cJSON * const root, const cJSON replacement)
{
    if (root == NULL)
M
Max Bruckner 已提交
727
    {
M
Max Bruckner 已提交
728
        return;
M
Max Bruckner 已提交
729
    }
M
Max Bruckner 已提交
730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746

    if (root->string != NULL)
    {
        cJSON_free(root->string);
    }
    if (root->valuestring != NULL)
    {
        cJSON_free(root->valuestring);
    }
    if (root->child != NULL)
    {
        cJSON_Delete(root->child);
    }

    memcpy(root, &replacement, sizeof(cJSON));
}

747
static int apply_patch(cJSON *object, const cJSON *patch, const cJSON_bool case_sensitive)
M
Max Bruckner 已提交
748 749 750 751 752 753 754 755 756
{
    cJSON *path = NULL;
    cJSON *value = NULL;
    cJSON *parent = NULL;
    enum patch_operation opcode = INVALID;
    unsigned char *parent_pointer = NULL;
    unsigned char *child_pointer = NULL;
    int status = 0;

757
    path = get_object_item(patch, "path", case_sensitive);
M
Max Bruckner 已提交
758
    if (!cJSON_IsString(path))
M
Max Bruckner 已提交
759
    {
M
Max Bruckner 已提交
760 761 762 763 764
        /* malformed patch. */
        status = 2;
        goto cleanup;
    }

765
    opcode = decode_patch_operation(patch, case_sensitive);
M
Max Bruckner 已提交
766 767 768 769 770 771 772 773
    if (opcode == INVALID)
    {
        status = 3;
        goto cleanup;
    }
    else if (opcode == TEST)
    {
        /* compare value: {...} with the given path */
774
        status = !compare_json(get_item_from_pointer(object, path->valuestring, case_sensitive), get_object_item(patch, "value", case_sensitive), case_sensitive);
M
Max Bruckner 已提交
775
        goto cleanup;
M
Max Bruckner 已提交
776
    }
777

778 779 780 781 782
    /* special case for replacing the root */
    if (path->valuestring[0] == '\0')
    {
        if (opcode == REMOVE)
        {
M
Max Bruckner 已提交
783
            static const cJSON invalid = { NULL, NULL, NULL, cJSON_Invalid, NULL, 0, 0, NULL};
784

M
Max Bruckner 已提交
785
            overwrite_item(object, invalid);
786

M
Max Bruckner 已提交
787 788
            status = 0;
            goto cleanup;
789 790 791 792
        }

        if ((opcode == REPLACE) || (opcode == ADD))
        {
793
            value = get_object_item(patch, "value", case_sensitive);
794 795 796
            if (value == NULL)
            {
                /* missing "value" for add/replace. */
M
Max Bruckner 已提交
797 798
                status = 7;
                goto cleanup;
799 800 801 802 803 804
            }

            value = cJSON_Duplicate(value, 1);
            if (value == NULL)
            {
                /* out of memory for add/replace. */
M
Max Bruckner 已提交
805 806
                status = 8;
                goto cleanup;
807 808
            }

M
Max Bruckner 已提交
809
            overwrite_item(object, *value);
810 811 812

            /* delete the duplicated value */
            cJSON_free(value);
M
Max Bruckner 已提交
813
            value = NULL;
814

M
Max Bruckner 已提交
815 816 817 818 819 820 821 822 823
            /* the string "value" isn't needed */
            if (object->string != NULL)
            {
                cJSON_free(object->string);
                object->string = NULL;
            }

            status = 0;
            goto cleanup;
824 825 826
        }
    }

M
Max Bruckner 已提交
827
    if ((opcode == REMOVE) || (opcode == REPLACE))
M
Max Bruckner 已提交
828 829
    {
        /* Get rid of old. */
830
        cJSON *old_item = detach_path(object, (unsigned char*)path->valuestring, case_sensitive);
831 832
        if (old_item == NULL)
        {
M
Max Bruckner 已提交
833 834
            status = 13;
            goto cleanup;
835 836
        }
        cJSON_Delete(old_item);
M
Max Bruckner 已提交
837
        if (opcode == REMOVE)
M
Max Bruckner 已提交
838
        {
839
            /* For Remove, this job is done. */
M
Max Bruckner 已提交
840 841
            status = 0;
            goto cleanup;
M
Max Bruckner 已提交
842 843
        }
    }
844

M
Max Bruckner 已提交
845
    /* Copy/Move uses "from". */
M
Max Bruckner 已提交
846
    if ((opcode == MOVE) || (opcode == COPY))
M
Max Bruckner 已提交
847
    {
848
        cJSON *from = get_object_item(patch, "from", case_sensitive);
M
Max Bruckner 已提交
849
        if (from == NULL)
M
Max Bruckner 已提交
850 851
        {
            /* missing "from" for copy/move. */
M
Max Bruckner 已提交
852 853
            status = 4;
            goto cleanup;
M
Max Bruckner 已提交
854
        }
855

M
Max Bruckner 已提交
856
        if (opcode == MOVE)
M
Max Bruckner 已提交
857
        {
858
            value = detach_path(object, (unsigned char*)from->valuestring, case_sensitive);
M
Max Bruckner 已提交
859
        }
M
Max Bruckner 已提交
860
        if (opcode == COPY)
M
Max Bruckner 已提交
861
        {
862
            value = get_item_from_pointer(object, from->valuestring, case_sensitive);
M
Max Bruckner 已提交
863
        }
M
Max Bruckner 已提交
864
        if (value == NULL)
M
Max Bruckner 已提交
865 866
        {
            /* missing "from" for copy/move. */
M
Max Bruckner 已提交
867 868
            status = 5;
            goto cleanup;
M
Max Bruckner 已提交
869
        }
M
Max Bruckner 已提交
870
        if (opcode == COPY)
M
Max Bruckner 已提交
871 872 873
        {
            value = cJSON_Duplicate(value, 1);
        }
M
Max Bruckner 已提交
874
        if (value == NULL)
M
Max Bruckner 已提交
875 876
        {
            /* out of memory for copy/move. */
M
Max Bruckner 已提交
877 878
            status = 6;
            goto cleanup;
M
Max Bruckner 已提交
879 880 881 882
        }
    }
    else /* Add/Replace uses "value". */
    {
883
        value = get_object_item(patch, "value", case_sensitive);
M
Max Bruckner 已提交
884
        if (value == NULL)
M
Max Bruckner 已提交
885 886
        {
            /* missing "value" for add/replace. */
M
Max Bruckner 已提交
887 888
            status = 7;
            goto cleanup;
M
Max Bruckner 已提交
889 890
        }
        value = cJSON_Duplicate(value, 1);
M
Max Bruckner 已提交
891
        if (value == NULL)
M
Max Bruckner 已提交
892 893
        {
            /* out of memory for add/replace. */
M
Max Bruckner 已提交
894 895
            status = 8;
            goto cleanup;
M
Max Bruckner 已提交
896 897
        }
    }
898

M
Max Bruckner 已提交
899
    /* Now, just add "value" to "path". */
900

M
Max Bruckner 已提交
901
    /* split pointer in parent and child */
M
Max Bruckner 已提交
902 903 904
    parent_pointer = cJSONUtils_strdup((unsigned char*)path->valuestring);
    child_pointer = (unsigned char*)strrchr((char*)parent_pointer, '/');
    if (child_pointer != NULL)
M
Max Bruckner 已提交
905
    {
M
Max Bruckner 已提交
906 907
        child_pointer[0] = '\0';
        child_pointer++;
M
Max Bruckner 已提交
908
    }
909
    parent = get_item_from_pointer(object, (char*)parent_pointer, case_sensitive);
910
    decode_pointer_inplace(child_pointer);
911

M
Max Bruckner 已提交
912
    /* add, remove, replace, move, copy, test. */
M
Max Bruckner 已提交
913
    if ((parent == NULL) || (child_pointer == NULL))
M
Max Bruckner 已提交
914 915
    {
        /* Couldn't find object to add to. */
M
Max Bruckner 已提交
916 917
        status = 9;
        goto cleanup;
M
Max Bruckner 已提交
918
    }
919
    else if (cJSON_IsArray(parent))
M
Max Bruckner 已提交
920
    {
M
Max Bruckner 已提交
921
        if (strcmp((char*)child_pointer, "-") == 0)
M
Max Bruckner 已提交
922 923
        {
            cJSON_AddItemToArray(parent, value);
M
Max Bruckner 已提交
924
            value = NULL;
M
Max Bruckner 已提交
925 926 927
        }
        else
        {
928
            size_t index = 0;
M
Max Bruckner 已提交
929
            if (!decode_array_index_from_pointer(child_pointer, &index))
930
            {
M
Max Bruckner 已提交
931 932
                status = 11;
                goto cleanup;
933 934
            }

935
            if (!insert_item_in_array(parent, index, value))
936
            {
M
Max Bruckner 已提交
937 938
                status = 10;
                goto cleanup;
939
            }
M
Max Bruckner 已提交
940
            value = NULL;
M
Max Bruckner 已提交
941 942
        }
    }
943
    else if (cJSON_IsObject(parent))
M
Max Bruckner 已提交
944
    {
M
Max Bruckner 已提交
945 946 947
        cJSON_DeleteItemFromObject(parent, (char*)child_pointer);
        cJSON_AddItemToObject(parent, (char*)child_pointer, value);
        value = NULL;
M
Max Bruckner 已提交
948
    }
M
Max Bruckner 已提交
949 950 951

cleanup:
    if (value != NULL)
M
Max Bruckner 已提交
952 953 954
    {
        cJSON_Delete(value);
    }
M
Max Bruckner 已提交
955 956 957 958
    if (parent_pointer != NULL)
    {
        cJSON_free(parent_pointer);
    }
M
Max Bruckner 已提交
959

M
Max Bruckner 已提交
960
    return status;
M
Max Bruckner 已提交
961
}
962

M
Max Bruckner 已提交
963
CJSON_PUBLIC(int) cJSONUtils_ApplyPatches(cJSON * const object, const cJSON * const patches)
964
{
M
Max Bruckner 已提交
965 966
    const cJSON *current_patch = NULL;
    int status = 0;
967

968
    if (!cJSON_IsArray(patches))
969 970 971 972
    {
        /* malformed patches. */
        return 1;
    }
M
Max Bruckner 已提交
973 974

    if (patches != NULL)
975
    {
M
Max Bruckner 已提交
976
        current_patch = patches->child;
977
    }
M
Max Bruckner 已提交
978 979

    while (current_patch != NULL)
980
    {
981
        status = apply_patch(object, current_patch, false);
M
Max Bruckner 已提交
982
        if (status != 0)
983
        {
M
Max Bruckner 已提交
984
            return status;
985
        }
M
Max Bruckner 已提交
986
        current_patch = current_patch->next;
987 988 989
    }

    return 0;
990
}
991

992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020
CJSON_PUBLIC(int) cJSONUtils_ApplyPatchesCaseSensitive(cJSON * const object, const cJSON * const patches)
{
    const cJSON *current_patch = NULL;
    int status = 0;

    if (!cJSON_IsArray(patches))
    {
        /* malformed patches. */
        return 1;
    }

    if (patches != NULL)
    {
        current_patch = patches->child;
    }

    while (current_patch != NULL)
    {
        status = apply_patch(object, current_patch, true);
        if (status != 0)
        {
            return status;
        }
        current_patch = current_patch->next;
    }

    return 0;
}

1021
static void compose_patch(cJSON * const patches, const unsigned char * const operation, const unsigned char * const path, const unsigned char *suffix, const cJSON * const value)
1022
{
1023
    cJSON *patch = cJSON_CreateObject();
M
Max Bruckner 已提交
1024
    if (patch == NULL)
1025
    {
M
Max Bruckner 已提交
1026
        return;
1027
    }
M
Max Bruckner 已提交
1028 1029 1030
    cJSON_AddItemToObject(patch, "op", cJSON_CreateString((const char*)operation));

    if (suffix == NULL)
1031
    {
1032
        cJSON_AddItemToObject(patch, "path", cJSON_CreateString((const char*)path));
1033
    }
M
Max Bruckner 已提交
1034 1035
    else
    {
1036
        size_t suffix_length = pointer_encoded_length(suffix);
M
Max Bruckner 已提交
1037 1038 1039 1040
        size_t path_length = strlen((const char*)path);
        unsigned char *full_path = (unsigned char*)cJSON_malloc(path_length + suffix_length + sizeof("/"));

        sprintf((char*)full_path, "%s/", (const char*)path);
1041
        encode_string_as_pointer(full_path + path_length + 1, suffix);
M
Max Bruckner 已提交
1042 1043 1044 1045 1046 1047

        cJSON_AddItemToObject(patch, "path", cJSON_CreateString((const char*)full_path));
        free(full_path);
    }

    if (value != NULL)
1048
    {
M
Max Bruckner 已提交
1049
        cJSON_AddItemToObject(patch, "value", cJSON_Duplicate(value, 1));
1050 1051
    }
    cJSON_AddItemToArray(patches, patch);
1052 1053
}

1054
CJSON_PUBLIC(void) cJSONUtils_AddPatchToArray(cJSON * const array, const char * const operation, const char * const path, const cJSON * const value)
M
Max Bruckner 已提交
1055
{
1056
    compose_patch(array, (const unsigned char*)operation, (const unsigned char*)path, NULL, value);
M
Max Bruckner 已提交
1057
}
1058

1059
static void create_patches(cJSON * const patches, const unsigned char * const path, cJSON * const from, cJSON * const to, const cJSON_bool case_sensitive)
1060
{
1061 1062 1063 1064 1065
    if ((from == NULL) || (to == NULL))
    {
        return;
    }

1066
    if ((from->type & 0xFF) != (to->type & 0xFF))
1067
    {
1068
        compose_patch(patches, (const unsigned char*)"replace", path, 0, to);
1069 1070 1071
        return;
    }

1072
    switch (from->type & 0xFF)
1073 1074 1075 1076
    {
        case cJSON_Number:
            if ((from->valueint != to->valueint) || (from->valuedouble != to->valuedouble))
            {
1077
                compose_patch(patches, (const unsigned char*)"replace", path, NULL, to);
1078 1079 1080 1081
            }
            return;

        case cJSON_String:
M
Max Bruckner 已提交
1082
            if (strcmp(from->valuestring, to->valuestring) != 0)
1083
            {
1084
                compose_patch(patches, (const unsigned char*)"replace", path, NULL, to);
1085 1086
            }
            return;
1087

1088 1089
        case cJSON_Array:
        {
1090 1091 1092 1093 1094 1095 1096
            size_t index = 0;
            cJSON *from_child = from->child;
            cJSON *to_child = to->child;
            unsigned char *new_path = (unsigned char*)cJSON_malloc(strlen((const char*)path) + 20 + sizeof("/")); /* Allow space for 64bit int. log10(2^64) = 20 */

            /* generate patches for all array elements that exist in both "from" and "to" */
            for (index = 0; (from_child != NULL) && (to_child != NULL); (void)(from_child = from_child->next), (void)(to_child = to_child->next), index++)
1097
            {
1098 1099 1100
                /* check if conversion to unsigned long is valid
                 * This should be eliminated at compile time by dead code elimination
                 * if size_t is an alias of unsigned long, or if it is bigger */
1101
                if (index > ULONG_MAX)
1102
                {
1103
                    free(new_path);
1104 1105
                    return;
                }
1106
                sprintf((char*)new_path, "%s/%lu", path, (unsigned long)index); /* path of the current array element */
1107
                create_patches(patches, new_path, from_child, to_child, case_sensitive);
1108
            }
1109

1110
            /* remove leftover elements from 'from' that are not in 'to' */
1111
            for (; (from_child != NULL); (void)(from_child = from_child->next))
1112
            {
1113 1114 1115
                /* check if conversion to unsigned long is valid
                 * This should be eliminated at compile time by dead code elimination
                 * if size_t is an alias of unsigned long, or if it is bigger */
1116
                if (index > ULONG_MAX)
1117
                {
1118
                    free(new_path);
1119 1120
                    return;
                }
1121
                sprintf((char*)new_path, "%lu", (unsigned long)index);
1122
                compose_patch(patches, (const unsigned char*)"remove", path, new_path, NULL);
1123 1124
            }
            /* add new elements in 'to' that were not in 'from' */
1125
            for (; (to_child != NULL); (void)(to_child = to_child->next), index++)
1126
            {
1127
                compose_patch(patches, (const unsigned char*)"add", path, (const unsigned char*)"-", to_child);
1128
            }
1129
            free(new_path);
1130 1131 1132 1133 1134
            return;
        }

        case cJSON_Object:
        {
1135 1136
            cJSON *from_child = NULL;
            cJSON *to_child = NULL;
1137 1138
            sort_object(from, case_sensitive);
            sort_object(to, case_sensitive);
1139

1140 1141
            from_child = from->child;
            to_child = to->child;
1142
            /* for all object values in the object with more of them */
1143
            while ((from_child != NULL) || (to_child != NULL))
1144
            {
1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155
                int diff;
                if (from_child == NULL)
                {
                    diff = 1;
                }
                else if (to_child == NULL)
                {
                    diff = -1;
                }
                else
                {
1156
                    diff = compare_strings((unsigned char*)from_child->string, (unsigned char*)to_child->string, case_sensitive);
1157 1158 1159
                }

                if (diff == 0)
1160 1161
                {
                    /* both object keys are the same */
1162
                    size_t path_length = strlen((const char*)path);
1163
                    size_t from_child_name_length = pointer_encoded_length((unsigned char*)from_child->string);
1164 1165 1166
                    unsigned char *new_path = (unsigned char*)cJSON_malloc(path_length + from_child_name_length + sizeof("/"));

                    sprintf((char*)new_path, "%s/", path);
1167
                    encode_string_as_pointer(new_path + path_length + 1, (unsigned char*)from_child->string);
1168

1169
                    /* create a patch for the element */
1170
                    create_patches(patches, new_path, from_child, to_child, case_sensitive);
1171 1172 1173 1174
                    free(new_path);

                    from_child = from_child->next;
                    to_child = to_child->next;
1175 1176 1177 1178
                }
                else if (diff < 0)
                {
                    /* object element doesn't exist in 'to' --> remove it */
1179
                    compose_patch(patches, (const unsigned char*)"remove", path, (unsigned char*)from_child->string, NULL);
1180 1181

                    from_child = from_child->next;
1182 1183 1184 1185
                }
                else
                {
                    /* object element doesn't exist in 'from' --> add it */
1186
                    compose_patch(patches, (const unsigned char*)"add", path, (unsigned char*)to_child->string, to_child);
1187 1188

                    to_child = to_child->next;
1189 1190 1191 1192 1193 1194 1195 1196 1197
                }
            }
            return;
        }

        default:
            break;
    }
}
1198

1199
CJSON_PUBLIC(cJSON *) cJSONUtils_GeneratePatches(cJSON * const from, cJSON * const to)
1200
{
1201
    cJSON *patches = cJSON_CreateArray();
1202
    create_patches(patches, (const unsigned char*)"", from, to, false);
1203

1204 1205
    return patches;
}
1206

1207 1208 1209 1210 1211 1212 1213 1214
CJSON_PUBLIC(cJSON *) cJSONUtils_GeneratePatchesCaseSensitive(cJSON * const from, cJSON * const to)
{
    cJSON *patches = cJSON_CreateArray();
    create_patches(patches, (const unsigned char*)"", from, to, true);

    return patches;
}

1215
CJSON_PUBLIC(void) cJSONUtils_SortObject(cJSON * const object)
1216
{
1217
    sort_object(object, false);
1218 1219
}

1220
CJSON_PUBLIC(void) cJSONUtils_SortObjectCaseSensitive(cJSON * const object)
M
Max Bruckner 已提交
1221
{
1222
    sort_object(object, true);
M
Max Bruckner 已提交
1223
}
1224

1225
static cJSON *merge_patch(cJSON *target, const cJSON * const patch, const cJSON_bool case_sensitive)
1226
{
M
Max Bruckner 已提交
1227 1228
    cJSON *patch_child = NULL;

1229
    if (!cJSON_IsObject(patch))
M
Max Bruckner 已提交
1230 1231 1232 1233 1234
    {
        /* scalar value, array or NULL, just duplicate */
        cJSON_Delete(target);
        return cJSON_Duplicate(patch, 1);
    }
1235

1236
    if (!cJSON_IsObject(target))
M
Max Bruckner 已提交
1237 1238 1239 1240 1241
    {
        cJSON_Delete(target);
        target = cJSON_CreateObject();
    }

M
Max Bruckner 已提交
1242 1243
    patch_child = patch->child;
    while (patch_child != NULL)
M
Max Bruckner 已提交
1244
    {
M
Max Bruckner 已提交
1245
        if (cJSON_IsNull(patch_child))
M
Max Bruckner 已提交
1246 1247
        {
            /* NULL is the indicator to remove a value, see RFC7396 */
1248 1249 1250 1251 1252 1253 1254 1255
            if (case_sensitive)
            {
                cJSON_DeleteItemFromObjectCaseSensitive(target, patch_child->string);
            }
            else
            {
                cJSON_DeleteItemFromObject(target, patch_child->string);
            }
M
Max Bruckner 已提交
1256 1257 1258
        }
        else
        {
1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277
            cJSON *replace_me = NULL;
            cJSON *replacement = NULL;

            if (case_sensitive)
            {
                replace_me = cJSON_DetachItemFromObjectCaseSensitive(target, patch_child->string);
            }
            else
            {
                replace_me = cJSON_DetachItemFromObject(target, patch_child->string);
            }

            replacement = merge_patch(replace_me, patch_child, case_sensitive);
            if (replacement == NULL)
            {
                return NULL;
            }

            cJSON_AddItemToObject(target, patch_child->string, replacement);
M
Max Bruckner 已提交
1278
        }
M
Max Bruckner 已提交
1279
        patch_child = patch_child->next;
M
Max Bruckner 已提交
1280 1281
    }
    return target;
1282
}
1283

1284 1285 1286 1287 1288 1289 1290 1291 1292 1293
CJSON_PUBLIC(cJSON *) cJSONUtils_MergePatch(cJSON *target, const cJSON * const patch)
{
    return merge_patch(target, patch, false);
}

CJSON_PUBLIC(cJSON *) cJSONUtils_MergePatchCaseSensitive(cJSON *target, const cJSON * const patch)
{
    return merge_patch(target, patch, true);
}

1294
static cJSON *generate_merge_patch(cJSON * const from, cJSON * const to, const cJSON_bool case_sensitive)
1295
{
1296 1297
    cJSON *from_child = NULL;
    cJSON *to_child = NULL;
1298
    cJSON *patch = NULL;
1299
    if (to == NULL)
1300 1301 1302 1303
    {
        /* patch to delete everything */
        return cJSON_CreateNull();
    }
1304
    if (!cJSON_IsObject(to) || !cJSON_IsObject(from))
1305 1306 1307 1308
    {
        return cJSON_Duplicate(to, 1);
    }

1309 1310
    sort_object(from, case_sensitive);
    sort_object(to, case_sensitive);
1311

1312 1313
    from_child = from->child;
    to_child = to->child;
1314
    patch = cJSON_CreateObject();
1315
    while (from_child || to_child)
1316
    {
1317 1318 1319 1320 1321
        int diff;
        if (from_child != NULL)
        {
            if (to_child != NULL)
            {
M
Max Bruckner 已提交
1322
                diff = strcmp(from_child->string, to_child->string);
1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334
            }
            else
            {
                diff = -1;
            }
        }
        else
        {
            diff = 1;
        }

        if (diff < 0)
1335 1336
        {
            /* from has a value that to doesn't have -> remove */
1337 1338 1339
            cJSON_AddItemToObject(patch, from_child->string, cJSON_CreateNull());

            from_child = from_child->next;
1340
        }
1341
        else if (diff > 0)
1342 1343
        {
            /* to has a value that from doesn't have -> add to patch */
1344 1345 1346
            cJSON_AddItemToObject(patch, to_child->string, cJSON_Duplicate(to_child, 1));

            to_child = to_child->next;
1347 1348 1349 1350
        }
        else
        {
            /* object key exists in both objects */
1351
            if (!compare_json(from_child, to_child, case_sensitive))
1352 1353
            {
                /* not identical --> generate a patch */
1354
                cJSON_AddItemToObject(patch, to_child->string, cJSONUtils_GenerateMergePatch(from_child, to_child));
1355
            }
1356

1357
            /* next key in the object */
1358 1359
            from_child = from_child->next;
            to_child = to_child->next;
1360 1361
        }
    }
1362
    if (patch->child == NULL)
1363
    {
1364
        /* no patch generated */
1365
        cJSON_Delete(patch);
1366
        return NULL;
1367 1368 1369
    }

    return patch;
M
Max Bruckner 已提交
1370
}
1371 1372 1373 1374 1375 1376 1377 1378 1379 1380

CJSON_PUBLIC(cJSON *) cJSONUtils_GenerateMergePatch(cJSON * const from, cJSON * const to)
{
    return generate_merge_patch(from, to, false);
}

CJSON_PUBLIC(cJSON *) cJSONUtils_GenerateMergePatchCaseSensitive(cJSON * const from, cJSON * const to)
{
    return generate_merge_patch(from, to, true);
}