1# -*- coding: utf-8 -*- 2# 3# python-json-patch - An implementation of the JSON Patch format 4# https://github.com/stefankoegl/python-json-patch 5# 6# Copyright (c) 2011 Stefan Kögl <stefan@skoegl.net> 7# All rights reserved. 8# 9# Redistribution and use in source and binary forms, with or without 10# modification, are permitted provided that the following conditions 11# are met: 12# 13# 1. Redistributions of source code must retain the above copyright 14# notice, this list of conditions and the following disclaimer. 15# 2. Redistributions in binary form must reproduce the above copyright 16# notice, this list of conditions and the following disclaimer in the 17# documentation and/or other materials provided with the distribution. 18# 3. The name of the author may not be used to endorse or promote products 19# derived from this software without specific prior written permission. 20# 21# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31# 32 33""" Apply JSON-Patches (RFC 6902) """ 34 35from __future__ import unicode_literals 36 37import collections 38import copy 39import functools 40import inspect 41import itertools 42import json 43import sys 44 45from jsonpointer import JsonPointer, JsonPointerException 46 47 48_ST_ADD = 0 49_ST_REMOVE = 1 50 51 52try: 53 from collections.abc import MutableMapping, MutableSequence 54 55except ImportError: 56 from collections import MutableMapping, MutableSequence 57 str = unicode 58 59# Will be parsed by setup.py to determine package metadata 60__author__ = 'Stefan Kögl <stefan@skoegl.net>' 61__version__ = '1.21' 62__website__ = 'https://github.com/stefankoegl/python-json-patch' 63__license__ = 'Modified BSD License' 64 65 66# pylint: disable=E0611,W0404 67if sys.version_info >= (3, 0): 68 basestring = (bytes, str) # pylint: disable=C0103,W0622 69 70 71class JsonPatchException(Exception): 72 """Base Json Patch exception""" 73 74 75class InvalidJsonPatch(JsonPatchException): 76 """ Raised if an invalid JSON Patch is created """ 77 78 79class JsonPatchConflict(JsonPatchException): 80 """Raised if patch could not be applied due to conflict situation such as: 81 - attempt to add object key then it already exists; 82 - attempt to operate with nonexistence object key; 83 - attempt to insert value to array at position beyond of it size; 84 - etc. 85 """ 86 87 88class JsonPatchTestFailed(JsonPatchException, AssertionError): 89 """ A Test operation failed """ 90 91 92def multidict(ordered_pairs): 93 """Convert duplicate keys values to lists.""" 94 # read all values into lists 95 mdict = collections.defaultdict(list) 96 for key, value in ordered_pairs: 97 mdict[key].append(value) 98 99 return dict( 100 # unpack lists that have only 1 item 101 (key, values[0] if len(values) == 1 else values) 102 for key, values in mdict.items() 103 ) 104 105 106# The "object_pairs_hook" parameter is used to handle duplicate keys when 107# loading a JSON object. 108_jsonloads = functools.partial(json.loads, object_pairs_hook=multidict) 109 110 111def apply_patch(doc, patch, in_place=False): 112 """Apply list of patches to specified json document. 113 114 :param doc: Document object. 115 :type doc: dict 116 117 :param patch: JSON patch as list of dicts or raw JSON-encoded string. 118 :type patch: list or str 119 120 :param in_place: While :const:`True` patch will modify target document. 121 By default patch will be applied to document copy. 122 :type in_place: bool 123 124 :return: Patched document object. 125 :rtype: dict 126 127 >>> doc = {'foo': 'bar'} 128 >>> patch = [{'op': 'add', 'path': '/baz', 'value': 'qux'}] 129 >>> other = apply_patch(doc, patch) 130 >>> doc is not other 131 True 132 >>> other == {'foo': 'bar', 'baz': 'qux'} 133 True 134 >>> patch = [{'op': 'add', 'path': '/baz', 'value': 'qux'}] 135 >>> apply_patch(doc, patch, in_place=True) == {'foo': 'bar', 'baz': 'qux'} 136 True 137 >>> doc == other 138 True 139 """ 140 141 if isinstance(patch, basestring): 142 patch = JsonPatch.from_string(patch) 143 else: 144 patch = JsonPatch(patch) 145 return patch.apply(doc, in_place) 146 147 148def make_patch(src, dst): 149 """Generates patch by comparing of two document objects. Actually is 150 a proxy to :meth:`JsonPatch.from_diff` method. 151 152 :param src: Data source document object. 153 :type src: dict 154 155 :param dst: Data source document object. 156 :type dst: dict 157 158 >>> src = {'foo': 'bar', 'numbers': [1, 3, 4, 8]} 159 >>> dst = {'baz': 'qux', 'numbers': [1, 4, 7]} 160 >>> patch = make_patch(src, dst) 161 >>> new = patch.apply(src) 162 >>> new == dst 163 True 164 """ 165 166 return JsonPatch.from_diff(src, dst) 167 168 169class JsonPatch(object): 170 """A JSON Patch is a list of Patch Operations. 171 172 >>> patch = JsonPatch([ 173 ... {'op': 'add', 'path': '/foo', 'value': 'bar'}, 174 ... {'op': 'add', 'path': '/baz', 'value': [1, 2, 3]}, 175 ... {'op': 'remove', 'path': '/baz/1'}, 176 ... {'op': 'test', 'path': '/baz', 'value': [1, 3]}, 177 ... {'op': 'replace', 'path': '/baz/0', 'value': 42}, 178 ... {'op': 'remove', 'path': '/baz/1'}, 179 ... ]) 180 >>> doc = {} 181 >>> result = patch.apply(doc) 182 >>> expected = {'foo': 'bar', 'baz': [42]} 183 >>> result == expected 184 True 185 186 JsonPatch object is iterable, so you could easily access to each patch 187 statement in loop: 188 189 >>> lpatch = list(patch) 190 >>> expected = {'op': 'add', 'path': '/foo', 'value': 'bar'} 191 >>> lpatch[0] == expected 192 True 193 >>> lpatch == patch.patch 194 True 195 196 Also JsonPatch could be converted directly to :class:`bool` if it contains 197 any operation statements: 198 199 >>> bool(patch) 200 True 201 >>> bool(JsonPatch([])) 202 False 203 204 This behavior is very handy with :func:`make_patch` to write more readable 205 code: 206 207 >>> old = {'foo': 'bar', 'numbers': [1, 3, 4, 8]} 208 >>> new = {'baz': 'qux', 'numbers': [1, 4, 7]} 209 >>> patch = make_patch(old, new) 210 >>> if patch: 211 ... # document have changed, do something useful 212 ... patch.apply(old) #doctest: +ELLIPSIS 213 {...} 214 """ 215 def __init__(self, patch): 216 self.patch = patch 217 218 self.operations = { 219 'remove': RemoveOperation, 220 'add': AddOperation, 221 'replace': ReplaceOperation, 222 'move': MoveOperation, 223 'test': TestOperation, 224 'copy': CopyOperation, 225 } 226 227 def __str__(self): 228 """str(self) -> self.to_string()""" 229 return self.to_string() 230 231 def __bool__(self): 232 return bool(self.patch) 233 234 __nonzero__ = __bool__ 235 236 def __iter__(self): 237 return iter(self.patch) 238 239 def __hash__(self): 240 return hash(tuple(self._ops)) 241 242 def __eq__(self, other): 243 if not isinstance(other, JsonPatch): 244 return False 245 return self._ops == other._ops 246 247 def __ne__(self, other): 248 return not(self == other) 249 250 @classmethod 251 def from_string(cls, patch_str): 252 """Creates JsonPatch instance from string source. 253 254 :param patch_str: JSON patch as raw string. 255 :type patch_str: str 256 257 :return: :class:`JsonPatch` instance. 258 """ 259 patch = _jsonloads(patch_str) 260 return cls(patch) 261 262 @classmethod 263 def from_diff(cls, src, dst, optimization=True): 264 """Creates JsonPatch instance based on comparing of two document 265 objects. Json patch would be created for `src` argument against `dst` 266 one. 267 268 :param src: Data source document object. 269 :type src: dict 270 271 :param dst: Data source document object. 272 :type dst: dict 273 274 :return: :class:`JsonPatch` instance. 275 276 >>> src = {'foo': 'bar', 'numbers': [1, 3, 4, 8]} 277 >>> dst = {'baz': 'qux', 'numbers': [1, 4, 7]} 278 >>> patch = JsonPatch.from_diff(src, dst) 279 >>> new = patch.apply(src) 280 >>> new == dst 281 True 282 """ 283 284 builder = DiffBuilder() 285 builder._compare_values('', None, src, dst) 286 ops = list(builder.execute()) 287 return cls(ops) 288 289 def to_string(self): 290 """Returns patch set as JSON string.""" 291 return json.dumps(self.patch) 292 293 @property 294 def _ops(self): 295 return tuple(map(self._get_operation, self.patch)) 296 297 def apply(self, obj, in_place=False): 298 """Applies the patch to given object. 299 300 :param obj: Document object. 301 :type obj: dict 302 303 :param in_place: Tweaks way how patch would be applied - directly to 304 specified `obj` or to his copy. 305 :type in_place: bool 306 307 :return: Modified `obj`. 308 """ 309 310 if not in_place: 311 obj = copy.deepcopy(obj) 312 313 for operation in self._ops: 314 obj = operation.apply(obj) 315 316 return obj 317 318 def _get_operation(self, operation): 319 if 'op' not in operation: 320 raise InvalidJsonPatch("Operation does not contain 'op' member") 321 322 op = operation['op'] 323 324 if not isinstance(op, basestring): 325 raise InvalidJsonPatch("Operation must be a string") 326 327 if op not in self.operations: 328 raise InvalidJsonPatch("Unknown operation {0!r}".format(op)) 329 330 cls = self.operations[op] 331 return cls(operation) 332 333 334class PatchOperation(object): 335 """A single operation inside a JSON Patch.""" 336 337 def __init__(self, operation): 338 self.location = operation['path'] 339 self.pointer = JsonPointer(self.location) 340 self.operation = operation 341 342 def apply(self, obj): 343 """Abstract method that applies patch operation to specified object.""" 344 raise NotImplementedError('should implement patch operation.') 345 346 def __hash__(self): 347 return hash(frozenset(self.operation.items())) 348 349 def __eq__(self, other): 350 if not isinstance(other, PatchOperation): 351 return False 352 return self.operation == other.operation 353 354 def __ne__(self, other): 355 return not(self == other) 356 357 @property 358 def path(self): 359 return '/'.join(self.pointer.parts[:-1]) 360 361 @property 362 def key(self): 363 try: 364 return int(self.pointer.parts[-1]) 365 except ValueError: 366 return self.pointer.parts[-1] 367 368 @key.setter 369 def key(self, value): 370 self.pointer.parts[-1] = str(value) 371 self.location = self.pointer.path 372 self.operation['path'] = self.location 373 374 375class RemoveOperation(PatchOperation): 376 """Removes an object property or an array element.""" 377 378 def apply(self, obj): 379 subobj, part = self.pointer.to_last(obj) 380 try: 381 del subobj[part] 382 except (KeyError, IndexError) as ex: 383 msg = "can't remove non-existent object '{0}'".format(part) 384 raise JsonPatchConflict(msg) 385 386 return obj 387 388 def _on_undo_remove(self, path, key): 389 if self.path == path: 390 if self.key >= key: 391 self.key += 1 392 else: 393 key -= 1 394 return key 395 396 def _on_undo_add(self, path, key): 397 if self.path == path: 398 if self.key > key: 399 self.key -= 1 400 else: 401 key -= 1 402 return key 403 404 405class AddOperation(PatchOperation): 406 """Adds an object property or an array element.""" 407 408 def apply(self, obj): 409 try: 410 value = self.operation["value"] 411 except KeyError as ex: 412 raise InvalidJsonPatch( 413 "The operation does not contain a 'value' member") 414 415 subobj, part = self.pointer.to_last(obj) 416 417 if isinstance(subobj, MutableSequence): 418 if part == '-': 419 subobj.append(value) # pylint: disable=E1103 420 421 elif part > len(subobj) or part < 0: 422 raise JsonPatchConflict("can't insert outside of list") 423 424 else: 425 subobj.insert(part, value) # pylint: disable=E1103 426 427 elif isinstance(subobj, MutableMapping): 428 if part is None: 429 obj = value # we're replacing the root 430 else: 431 subobj[part] = value 432 433 else: 434 raise TypeError("invalid document type {0}".format(type(subobj))) 435 436 return obj 437 438 def _on_undo_remove(self, path, key): 439 if self.path == path: 440 if self.key > key: 441 self.key += 1 442 else: 443 key += 1 444 return key 445 446 def _on_undo_add(self, path, key): 447 if self.path == path: 448 if self.key > key: 449 self.key -= 1 450 else: 451 key += 1 452 return key 453 454 455class ReplaceOperation(PatchOperation): 456 """Replaces an object property or an array element by new value.""" 457 458 def apply(self, obj): 459 try: 460 value = self.operation["value"] 461 except KeyError as ex: 462 raise InvalidJsonPatch( 463 "The operation does not contain a 'value' member") 464 465 subobj, part = self.pointer.to_last(obj) 466 467 if part is None: 468 return value 469 470 if isinstance(subobj, MutableSequence): 471 if part > len(subobj) or part < 0: 472 raise JsonPatchConflict("can't replace outside of list") 473 474 elif isinstance(subobj, MutableMapping): 475 if part not in subobj: 476 msg = "can't replace non-existent object '{0}'".format(part) 477 raise JsonPatchConflict(msg) 478 else: 479 raise TypeError("invalid document type {0}".format(type(subobj))) 480 481 subobj[part] = value 482 return obj 483 484 def _on_undo_remove(self, path, key): 485 return key 486 487 def _on_undo_add(self, path, key): 488 return key 489 490 491class MoveOperation(PatchOperation): 492 """Moves an object property or an array element to new location.""" 493 494 def apply(self, obj): 495 try: 496 from_ptr = JsonPointer(self.operation['from']) 497 except KeyError as ex: 498 raise InvalidJsonPatch( 499 "The operation does not contain a 'from' member") 500 501 subobj, part = from_ptr.to_last(obj) 502 try: 503 value = subobj[part] 504 except (KeyError, IndexError) as ex: 505 raise JsonPatchConflict(str(ex)) 506 507 # If source and target are equal, this is a no-op 508 if self.pointer == from_ptr: 509 return obj 510 511 if isinstance(subobj, MutableMapping) and \ 512 self.pointer.contains(from_ptr): 513 raise JsonPatchConflict('Cannot move values into its own children') 514 515 obj = RemoveOperation({ 516 'op': 'remove', 517 'path': self.operation['from'] 518 }).apply(obj) 519 520 obj = AddOperation({ 521 'op': 'add', 522 'path': self.location, 523 'value': value 524 }).apply(obj) 525 526 return obj 527 528 @property 529 def from_path(self): 530 from_ptr = JsonPointer(self.operation['from']) 531 return '/'.join(from_ptr.parts[:-1]) 532 533 @property 534 def from_key(self): 535 from_ptr = JsonPointer(self.operation['from']) 536 try: 537 return int(from_ptr.parts[-1]) 538 except TypeError: 539 return from_ptr.parts[-1] 540 541 @from_key.setter 542 def from_key(self, value): 543 from_ptr = JsonPointer(self.operation['from']) 544 from_ptr.parts[-1] = str(value) 545 self.operation['from'] = from_ptr.path 546 547 def _on_undo_remove(self, path, key): 548 if self.from_path == path: 549 if self.from_key >= key: 550 self.from_key += 1 551 else: 552 key -= 1 553 if self.path == path: 554 if self.key > key: 555 self.key += 1 556 else: 557 key += 1 558 return key 559 560 def _on_undo_add(self, path, key): 561 if self.from_path == path: 562 if self.from_key > key: 563 self.from_key -= 1 564 else: 565 key -= 1 566 if self.path == path: 567 if self.key > key: 568 self.key -= 1 569 else: 570 key += 1 571 return key 572 573 574class TestOperation(PatchOperation): 575 """Test value by specified location.""" 576 577 def apply(self, obj): 578 try: 579 subobj, part = self.pointer.to_last(obj) 580 if part is None: 581 val = subobj 582 else: 583 val = self.pointer.walk(subobj, part) 584 except JsonPointerException as ex: 585 raise JsonPatchTestFailed(str(ex)) 586 587 try: 588 value = self.operation['value'] 589 except KeyError as ex: 590 raise InvalidJsonPatch( 591 "The operation does not contain a 'value' member") 592 593 if val != value: 594 msg = '{0} ({1}) is not equal to tested value {2} ({3})' 595 raise JsonPatchTestFailed(msg.format(val, type(val), 596 value, type(value))) 597 598 return obj 599 600 601class CopyOperation(PatchOperation): 602 """ Copies an object property or an array element to a new location """ 603 604 def apply(self, obj): 605 try: 606 from_ptr = JsonPointer(self.operation['from']) 607 except KeyError as ex: 608 raise InvalidJsonPatch( 609 "The operation does not contain a 'from' member") 610 611 subobj, part = from_ptr.to_last(obj) 612 try: 613 value = copy.deepcopy(subobj[part]) 614 except (KeyError, IndexError) as ex: 615 raise JsonPatchConflict(str(ex)) 616 617 obj = AddOperation({ 618 'op': 'add', 619 'path': self.location, 620 'value': value 621 }).apply(obj) 622 623 return obj 624 625 626class DiffBuilder(object): 627 628 def __init__(self): 629 self.index_storage = [{}, {}] 630 self.index_storage2 = [[], []] 631 self.__root = root = [] 632 root[:] = [root, root, None] 633 634 def store_index(self, value, index, st): 635 try: 636 storage = self.index_storage[st] 637 stored = storage.get(value) 638 if stored is None: 639 storage[value] = [index] 640 else: 641 storage[value].append(index) 642 643 except TypeError: 644 self.index_storage2[st].append((value, index)) 645 646 def take_index(self, value, st): 647 try: 648 stored = self.index_storage[st].get(value) 649 if stored: 650 return stored.pop() 651 652 except TypeError: 653 storage = self.index_storage2[st] 654 for i in range(len(storage)-1, -1, -1): 655 if storage[i][0] == value: 656 return storage.pop(i)[1] 657 658 def insert(self, op): 659 root = self.__root 660 last = root[0] 661 last[1] = root[0] = [last, root, op] 662 return root[0] 663 664 def remove(self, index): 665 link_prev, link_next, _ = index 666 link_prev[1] = link_next 667 link_next[0] = link_prev 668 index[:] = [] 669 670 def iter_from(self, start): 671 root = self.__root 672 curr = start[1] 673 while curr is not root: 674 yield curr[2] 675 curr = curr[1] 676 677 def __iter__(self): 678 root = self.__root 679 curr = root[1] 680 while curr is not root: 681 yield curr[2] 682 curr = curr[1] 683 684 def execute(self): 685 root = self.__root 686 curr = root[1] 687 while curr is not root: 688 if curr[1] is not root: 689 op_first, op_second = curr[2], curr[1][2] 690 if op_first.location == op_second.location and \ 691 type(op_first) == RemoveOperation and \ 692 type(op_second) == AddOperation: 693 yield ReplaceOperation({ 694 'op': 'replace', 695 'path': op_second.location, 696 'value': op_second.operation['value'], 697 }).operation 698 curr = curr[1][1] 699 continue 700 701 yield curr[2].operation 702 curr = curr[1] 703 704 def _item_added(self, path, key, item): 705 index = self.take_index(item, _ST_REMOVE) 706 if index is not None: 707 op = index[2] 708 if type(op.key) == int: 709 for v in self.iter_from(index): 710 op.key = v._on_undo_remove(op.path, op.key) 711 712 self.remove(index) 713 if op.location != _path_join(path, key): 714 new_op = MoveOperation({ 715 'op': 'move', 716 'from': op.location, 717 'path': _path_join(path, key), 718 }) 719 self.insert(new_op) 720 else: 721 new_op = AddOperation({ 722 'op': 'add', 723 'path': _path_join(path, key), 724 'value': item, 725 }) 726 new_index = self.insert(new_op) 727 self.store_index(item, new_index, _ST_ADD) 728 729 def _item_removed(self, path, key, item): 730 new_op = RemoveOperation({ 731 'op': 'remove', 732 'path': _path_join(path, key), 733 }) 734 index = self.take_index(item, _ST_ADD) 735 new_index = self.insert(new_op) 736 if index is not None: 737 op = index[2] 738 if type(op.key) == int: 739 for v in self.iter_from(index): 740 op.key = v._on_undo_add(op.path, op.key) 741 742 self.remove(index) 743 if new_op.location != op.location: 744 new_op = MoveOperation({ 745 'op': 'move', 746 'from': new_op.location, 747 'path': op.location, 748 }) 749 new_index[2] = new_op 750 751 else: 752 self.remove(new_index) 753 754 else: 755 self.store_index(item, new_index, _ST_REMOVE) 756 757 def _item_replaced(self, path, key, item): 758 self.insert(ReplaceOperation({ 759 'op': 'replace', 760 'path': _path_join(path, key), 761 'value': item, 762 })) 763 764 def _compare_dicts(self, path, src, dst): 765 src_keys = set(src.keys()) 766 dst_keys = set(dst.keys()) 767 added_keys = dst_keys - src_keys 768 removed_keys = src_keys - dst_keys 769 770 for key in removed_keys: 771 self._item_removed(path, str(key), src[key]) 772 773 for key in added_keys: 774 self._item_added(path, str(key), dst[key]) 775 776 for key in src_keys & dst_keys: 777 self._compare_values(path, key, src[key], dst[key]) 778 779 def _compare_lists(self, path, src, dst): 780 len_src, len_dst = len(src), len(dst) 781 max_len = max(len_src, len_dst) 782 min_len = min(len_src, len_dst) 783 for key in range(max_len): 784 if key < min_len: 785 old, new = src[key], dst[key] 786 if old == new: 787 continue 788 789 elif isinstance(old, MutableMapping) and \ 790 isinstance(new, MutableMapping): 791 self._compare_dicts(_path_join(path, key), old, new) 792 793 elif isinstance(old, MutableSequence) and \ 794 isinstance(new, MutableSequence): 795 self._compare_lists(_path_join(path, key), old, new) 796 797 else: 798 self._item_removed(path, key, old) 799 self._item_added(path, key, new) 800 801 elif len_src > len_dst: 802 self._item_removed(path, len_dst, src[key]) 803 804 else: 805 self._item_added(path, key, dst[key]) 806 807 def _compare_values(self, path, key, src, dst): 808 if src == dst: 809 return 810 811 elif isinstance(src, MutableMapping) and \ 812 isinstance(dst, MutableMapping): 813 self._compare_dicts(_path_join(path, key), src, dst) 814 815 elif isinstance(src, MutableSequence) and \ 816 isinstance(dst, MutableSequence): 817 self._compare_lists(_path_join(path, key), src, dst) 818 819 else: 820 self._item_replaced(path, key, dst) 821 822 823def _path_join(path, key): 824 if key is None: 825 return path 826 827 return path + '/' + str(key).replace('~', '~0').replace('/', '~1') 828