codekingpro/portable-devtools

1# -*- coding: utf-8 -*-2#3# python-json-patch - An implementation of the JSON Patch format4# https://github.com/stefankoegl/python-json-patch5#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 without10# modification, are permitted provided that the following conditions11# are met:12#13# 1. Redistributions of source code must retain the above copyright14#    notice, this list of conditions and the following disclaimer.15# 2. Redistributions in binary form must reproduce the above copyright16#    notice, this list of conditions and the following disclaimer in the17#    documentation and/or other materials provided with the distribution.18# 3. The name of the author may not be used to endorse or promote products19#    derived from this software without specific prior written permission.20#21# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR22# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES23# 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, BUT26# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,27# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY28# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT29# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF30# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.31#32 33""" Apply JSON-Patches (RFC 6902) """34 35from __future__ import unicode_literals36 37import collections38import copy39import functools40import json41import sys42 43try:44    from collections.abc import Sequence45except ImportError:  # Python 346    from collections import Sequence47 48try:49    from types import MappingProxyType50except ImportError:51    # Python < 3.352    MappingProxyType = dict53 54from jsonpointer import JsonPointer, JsonPointerException55 56 57_ST_ADD = 058_ST_REMOVE = 159 60 61try:62    from collections.abc import MutableMapping, MutableSequence63 64except ImportError:65    from collections import MutableMapping, MutableSequence66    str = unicode67 68# Will be parsed by setup.py to determine package metadata69__author__ = 'Stefan Kögl <stefan@skoegl.net>'70__version__ = '1.33'71__website__ = 'https://github.com/stefankoegl/python-json-patch'72__license__ = 'Modified BSD License'73 74 75# pylint: disable=E0611,W040476if sys.version_info >= (3, 0):77    basestring = (bytes, str)  # pylint: disable=C0103,W062278 79 80class JsonPatchException(Exception):81    """Base Json Patch exception"""82 83 84class InvalidJsonPatch(JsonPatchException):85    """ Raised if an invalid JSON Patch is created """86 87 88class JsonPatchConflict(JsonPatchException):89    """Raised if patch could not be applied due to conflict situation such as:90    - attempt to add object key when it already exists;91    - attempt to operate with nonexistence object key;92    - attempt to insert value to array at position beyond its size;93    - etc.94    """95 96 97class JsonPatchTestFailed(JsonPatchException, AssertionError):98    """ A Test operation failed """99 100 101def multidict(ordered_pairs):102    """Convert duplicate keys values to lists."""103    # read all values into lists104    mdict = collections.defaultdict(list)105    for key, value in ordered_pairs:106        mdict[key].append(value)107 108    return dict(109        # unpack lists that have only 1 item110        (key, values[0] if len(values) == 1 else values)111        for key, values in mdict.items()112    )113 114 115# The "object_pairs_hook" parameter is used to handle duplicate keys when116# loading a JSON object.117_jsonloads = functools.partial(json.loads, object_pairs_hook=multidict)118 119 120def apply_patch(doc, patch, in_place=False, pointer_cls=JsonPointer):121    """Apply list of patches to specified json document.122 123    :param doc: Document object.124    :type doc: dict125 126    :param patch: JSON patch as list of dicts or raw JSON-encoded string.127    :type patch: list or str128 129    :param in_place: While :const:`True` patch will modify target document.130                     By default patch will be applied to document copy.131    :type in_place: bool132 133    :param pointer_cls: JSON pointer class to use.134    :type pointer_cls: Type[JsonPointer]135 136    :return: Patched document object.137    :rtype: dict138 139    >>> doc = {'foo': 'bar'}140    >>> patch = [{'op': 'add', 'path': '/baz', 'value': 'qux'}]141    >>> other = apply_patch(doc, patch)142    >>> doc is not other143    True144    >>> other == {'foo': 'bar', 'baz': 'qux'}145    True146    >>> patch = [{'op': 'add', 'path': '/baz', 'value': 'qux'}]147    >>> apply_patch(doc, patch, in_place=True) == {'foo': 'bar', 'baz': 'qux'}148    True149    >>> doc == other150    True151    """152 153    if isinstance(patch, basestring):154        patch = JsonPatch.from_string(patch, pointer_cls=pointer_cls)155    else:156        patch = JsonPatch(patch, pointer_cls=pointer_cls)157    return patch.apply(doc, in_place)158 159 160def make_patch(src, dst, pointer_cls=JsonPointer):161    """Generates patch by comparing two document objects. Actually is162    a proxy to :meth:`JsonPatch.from_diff` method.163 164    :param src: Data source document object.165    :type src: dict166 167    :param dst: Data source document object.168    :type dst: dict169 170    :param pointer_cls: JSON pointer class to use.171    :type pointer_cls: Type[JsonPointer]172 173    >>> src = {'foo': 'bar', 'numbers': [1, 3, 4, 8]}174    >>> dst = {'baz': 'qux', 'numbers': [1, 4, 7]}175    >>> patch = make_patch(src, dst)176    >>> new = patch.apply(src)177    >>> new == dst178    True179    """180 181    return JsonPatch.from_diff(src, dst, pointer_cls=pointer_cls)182 183 184class PatchOperation(object):185    """A single operation inside a JSON Patch."""186 187    def __init__(self, operation, pointer_cls=JsonPointer):188        self.pointer_cls = pointer_cls189 190        if not operation.__contains__('path'):191            raise InvalidJsonPatch("Operation must have a 'path' member")192 193        if isinstance(operation['path'], self.pointer_cls):194            self.location = operation['path'].path195            self.pointer = operation['path']196        else:197            self.location = operation['path']198            try:199                self.pointer = self.pointer_cls(self.location)200            except TypeError as ex:201                raise InvalidJsonPatch("Invalid 'path'")202 203        self.operation = operation204 205    def apply(self, obj):206        """Abstract method that applies a patch operation to the specified object."""207        raise NotImplementedError('should implement the patch operation.')208 209    def __hash__(self):210        return hash(frozenset(self.operation.items()))211 212    def __eq__(self, other):213        if not isinstance(other, PatchOperation):214            return False215        return self.operation == other.operation216 217    def __ne__(self, other):218        return not(self == other)219 220    @property221    def path(self):222        return '/'.join(self.pointer.parts[:-1])223 224    @property225    def key(self):226        try:227            return int(self.pointer.parts[-1])228        except ValueError:229            return self.pointer.parts[-1]230 231    @key.setter232    def key(self, value):233        self.pointer.parts[-1] = str(value)234        self.location = self.pointer.path235        self.operation['path'] = self.location236 237 238class RemoveOperation(PatchOperation):239    """Removes an object property or an array element."""240 241    def apply(self, obj):242        subobj, part = self.pointer.to_last(obj)243 244        if isinstance(subobj, Sequence) and not isinstance(part, int):245            raise JsonPointerException("invalid array index '{0}'".format(part))246 247        try:248            del subobj[part]249        except (KeyError, IndexError) as ex:250            msg = "can't remove a non-existent object '{0}'".format(part)251            raise JsonPatchConflict(msg)252 253        return obj254 255    def _on_undo_remove(self, path, key):256        if self.path == path:257            if self.key >= key:258                self.key += 1259            else:260                key -= 1261        return key262 263    def _on_undo_add(self, path, key):264        if self.path == path:265            if self.key > key:266                self.key -= 1267            else:268                key -= 1269        return key270 271 272class AddOperation(PatchOperation):273    """Adds an object property or an array element."""274 275    def apply(self, obj):276        try:277            value = self.operation["value"]278        except KeyError as ex:279            raise InvalidJsonPatch(280                "The operation does not contain a 'value' member")281 282        subobj, part = self.pointer.to_last(obj)283 284        if isinstance(subobj, MutableSequence):285            if part == '-':286                subobj.append(value)  # pylint: disable=E1103287 288            elif part > len(subobj) or part < 0:289                raise JsonPatchConflict("can't insert outside of list")290 291            else:292                subobj.insert(part, value)  # pylint: disable=E1103293 294        elif isinstance(subobj, MutableMapping):295            if part is None:296                obj = value  # we're replacing the root297            else:298                subobj[part] = value299 300        else:301            if part is None:302                raise TypeError("invalid document type {0}".format(type(subobj)))303            else:304                raise JsonPatchConflict("unable to fully resolve json pointer {0}, part {1}".format(self.location, part))305        return obj306 307    def _on_undo_remove(self, path, key):308        if self.path == path:309            if self.key > key:310                self.key += 1311            else:312                key += 1313        return key314 315    def _on_undo_add(self, path, key):316        if self.path == path:317            if self.key > key:318                self.key -= 1319            else:320                key += 1321        return key322 323 324class ReplaceOperation(PatchOperation):325    """Replaces an object property or an array element by a new value."""326 327    def apply(self, obj):328        try:329            value = self.operation["value"]330        except KeyError as ex:331            raise InvalidJsonPatch(332                "The operation does not contain a 'value' member")333 334        subobj, part = self.pointer.to_last(obj)335 336        if part is None:337            return value338 339        if part == "-":340            raise InvalidJsonPatch("'path' with '-' can't be applied to 'replace' operation")341 342        if isinstance(subobj, MutableSequence):343            if part >= len(subobj) or part < 0:344                raise JsonPatchConflict("can't replace outside of list")345 346        elif isinstance(subobj, MutableMapping):347            if part not in subobj:348                msg = "can't replace a non-existent object '{0}'".format(part)349                raise JsonPatchConflict(msg)350        else:351            if part is None:352                raise TypeError("invalid document type {0}".format(type(subobj)))353            else:354                raise JsonPatchConflict("unable to fully resolve json pointer {0}, part {1}".format(self.location, part))355 356        subobj[part] = value357        return obj358 359    def _on_undo_remove(self, path, key):360        return key361 362    def _on_undo_add(self, path, key):363        return key364 365 366class MoveOperation(PatchOperation):367    """Moves an object property or an array element to a new location."""368 369    def apply(self, obj):370        try:371            if isinstance(self.operation['from'], self.pointer_cls):372                from_ptr = self.operation['from']373            else:374                from_ptr = self.pointer_cls(self.operation['from'])375        except KeyError as ex:376            raise InvalidJsonPatch(377                "The operation does not contain a 'from' member")378 379        subobj, part = from_ptr.to_last(obj)380        try:381            value = subobj[part]382        except (KeyError, IndexError) as ex:383            raise JsonPatchConflict(str(ex))384 385        # If source and target are equal, this is a no-op386        if self.pointer == from_ptr:387            return obj388 389        if isinstance(subobj, MutableMapping) and \390                self.pointer.contains(from_ptr):391            raise JsonPatchConflict('Cannot move values into their own children')392 393        obj = RemoveOperation({394            'op': 'remove',395            'path': self.operation['from']396        }, pointer_cls=self.pointer_cls).apply(obj)397 398        obj = AddOperation({399            'op': 'add',400            'path': self.location,401            'value': value402        }, pointer_cls=self.pointer_cls).apply(obj)403 404        return obj405 406    @property407    def from_path(self):408        from_ptr = self.pointer_cls(self.operation['from'])409        return '/'.join(from_ptr.parts[:-1])410 411    @property412    def from_key(self):413        from_ptr = self.pointer_cls(self.operation['from'])414        try:415            return int(from_ptr.parts[-1])416        except TypeError:417            return from_ptr.parts[-1]418 419    @from_key.setter420    def from_key(self, value):421        from_ptr = self.pointer_cls(self.operation['from'])422        from_ptr.parts[-1] = str(value)423        self.operation['from'] = from_ptr.path424 425    def _on_undo_remove(self, path, key):426        if self.from_path == path:427            if self.from_key >= key:428                self.from_key += 1429            else:430                key -= 1431        if self.path == path:432            if self.key > key:433                self.key += 1434            else:435                key += 1436        return key437 438    def _on_undo_add(self, path, key):439        if self.from_path == path:440            if self.from_key > key:441                self.from_key -= 1442            else:443                key -= 1444        if self.path == path:445            if self.key > key:446                self.key -= 1447            else:448                key += 1449        return key450 451 452class TestOperation(PatchOperation):453    """Test value by specified location."""454 455    def apply(self, obj):456        try:457            subobj, part = self.pointer.to_last(obj)458            if part is None:459                val = subobj460            else:461                val = self.pointer.walk(subobj, part)462        except JsonPointerException as ex:463            raise JsonPatchTestFailed(str(ex))464 465        try:466            value = self.operation['value']467        except KeyError as ex:468            raise InvalidJsonPatch(469                "The operation does not contain a 'value' member")470 471        if val != value:472            msg = '{0} ({1}) is not equal to tested value {2} ({3})'473            raise JsonPatchTestFailed(msg.format(val, type(val),474                                                 value, type(value)))475 476        return obj477 478 479class CopyOperation(PatchOperation):480    """ Copies an object property or an array element to a new location """481 482    def apply(self, obj):483        try:484            from_ptr = self.pointer_cls(self.operation['from'])485        except KeyError as ex:486            raise InvalidJsonPatch(487                "The operation does not contain a 'from' member")488 489        subobj, part = from_ptr.to_last(obj)490        try:491            value = copy.deepcopy(subobj[part])492        except (KeyError, IndexError) as ex:493            raise JsonPatchConflict(str(ex))494 495        obj = AddOperation({496            'op': 'add',497            'path': self.location,498            'value': value499        }, pointer_cls=self.pointer_cls).apply(obj)500 501        return obj502 503 504class JsonPatch(object):505    json_dumper = staticmethod(json.dumps)506    json_loader = staticmethod(_jsonloads)507 508    operations = MappingProxyType({509        'remove': RemoveOperation,510        'add': AddOperation,511        'replace': ReplaceOperation,512        'move': MoveOperation,513        'test': TestOperation,514        'copy': CopyOperation,515    })516 517    """A JSON Patch is a list of Patch Operations.518 519    >>> patch = JsonPatch([520    ...     {'op': 'add', 'path': '/foo', 'value': 'bar'},521    ...     {'op': 'add', 'path': '/baz', 'value': [1, 2, 3]},522    ...     {'op': 'remove', 'path': '/baz/1'},523    ...     {'op': 'test', 'path': '/baz', 'value': [1, 3]},524    ...     {'op': 'replace', 'path': '/baz/0', 'value': 42},525    ...     {'op': 'remove', 'path': '/baz/1'},526    ... ])527    >>> doc = {}528    >>> result = patch.apply(doc)529    >>> expected = {'foo': 'bar', 'baz': [42]}530    >>> result == expected531    True532 533    JsonPatch object is iterable, so you can easily access each patch534    statement in a loop:535 536    >>> lpatch = list(patch)537    >>> expected = {'op': 'add', 'path': '/foo', 'value': 'bar'}538    >>> lpatch[0] == expected539    True540    >>> lpatch == patch.patch541    True542 543    Also JsonPatch could be converted directly to :class:`bool` if it contains544    any operation statements:545 546    >>> bool(patch)547    True548    >>> bool(JsonPatch([]))549    False550 551    This behavior is very handy with :func:`make_patch` to write more readable552    code:553 554    >>> old = {'foo': 'bar', 'numbers': [1, 3, 4, 8]}555    >>> new = {'baz': 'qux', 'numbers': [1, 4, 7]}556    >>> patch = make_patch(old, new)557    >>> if patch:558    ...     # document have changed, do something useful559    ...     patch.apply(old)    #doctest: +ELLIPSIS560    {...}561    """562    def __init__(self, patch, pointer_cls=JsonPointer):563        self.patch = patch564        self.pointer_cls = pointer_cls565 566        # Verify that the structure of the patch document567        # is correct by retrieving each patch element.568        # Much of the validation is done in the initializer569        # though some is delayed until the patch is applied.570        for op in self.patch:571            # We're only checking for basestring in the following check572            # for two reasons:573            #574            # - It should come from JSON, which only allows strings as575            #   dictionary keys, so having a string here unambiguously means576            #   someone used: {"op": ..., ...} instead of [{"op": ..., ...}].577            #578            # - There's no possible false positive: if someone give a sequence579            #   of mappings, this won't raise.580            if isinstance(op, basestring):581                raise InvalidJsonPatch("Document is expected to be sequence of "582                                       "operations, got a sequence of strings.")583 584            self._get_operation(op)585 586    def __str__(self):587        """str(self) -> self.to_string()"""588        return self.to_string()589 590    def __bool__(self):591        return bool(self.patch)592 593    __nonzero__ = __bool__594 595    def __iter__(self):596        return iter(self.patch)597 598    def __hash__(self):599        return hash(tuple(self._ops))600 601    def __eq__(self, other):602        if not isinstance(other, JsonPatch):603            return False604        return self._ops == other._ops605 606    def __ne__(self, other):607        return not(self == other)608 609    @classmethod610    def from_string(cls, patch_str, loads=None, pointer_cls=JsonPointer):611        """Creates JsonPatch instance from string source.612 613        :param patch_str: JSON patch as raw string.614        :type patch_str: str615 616        :param loads: A function of one argument that loads a serialized617                      JSON string.618        :type loads: function619 620        :param pointer_cls: JSON pointer class to use.621        :type pointer_cls: Type[JsonPointer]622 623        :return: :class:`JsonPatch` instance.624        """625        json_loader = loads or cls.json_loader626        patch = json_loader(patch_str)627        return cls(patch, pointer_cls=pointer_cls)628 629    @classmethod630    def from_diff(631            cls, src, dst, optimization=True, dumps=None,632            pointer_cls=JsonPointer,633    ):634        """Creates JsonPatch instance based on comparison of two document635        objects. Json patch would be created for `src` argument against `dst`636        one.637 638        :param src: Data source document object.639        :type src: dict640 641        :param dst: Data source document object.642        :type dst: dict643 644        :param dumps: A function of one argument that produces a serialized645                      JSON string.646        :type dumps: function647 648        :param pointer_cls: JSON pointer class to use.649        :type pointer_cls: Type[JsonPointer]650 651        :return: :class:`JsonPatch` instance.652 653        >>> src = {'foo': 'bar', 'numbers': [1, 3, 4, 8]}654        >>> dst = {'baz': 'qux', 'numbers': [1, 4, 7]}655        >>> patch = JsonPatch.from_diff(src, dst)656        >>> new = patch.apply(src)657        >>> new == dst658        True659        """660        json_dumper = dumps or cls.json_dumper661        builder = DiffBuilder(src, dst, json_dumper, pointer_cls=pointer_cls)662        builder._compare_values('', None, src, dst)663        ops = list(builder.execute())664        return cls(ops, pointer_cls=pointer_cls)665 666    def to_string(self, dumps=None):667        """Returns patch set as JSON string."""668        json_dumper = dumps or self.json_dumper669        return json_dumper(self.patch)670 671    @property672    def _ops(self):673        return tuple(map(self._get_operation, self.patch))674 675    def apply(self, obj, in_place=False):676        """Applies the patch to a given object.677 678        :param obj: Document object.679        :type obj: dict680 681        :param in_place: Tweaks the way how patch would be applied - directly to682                         specified `obj` or to its copy.683        :type in_place: bool684 685        :return: Modified `obj`.686        """687 688        if not in_place:689            obj = copy.deepcopy(obj)690 691        for operation in self._ops:692            obj = operation.apply(obj)693 694        return obj695 696    def _get_operation(self, operation):697        if 'op' not in operation:698            raise InvalidJsonPatch("Operation does not contain 'op' member")699 700        op = operation['op']701 702        if not isinstance(op, basestring):703            raise InvalidJsonPatch("Operation's op must be a string")704 705        if op not in self.operations:706            raise InvalidJsonPatch("Unknown operation {0!r}".format(op))707 708        cls = self.operations[op]709        return cls(operation, pointer_cls=self.pointer_cls)710 711 712class DiffBuilder(object):713 714    def __init__(self, src_doc, dst_doc, dumps=json.dumps, pointer_cls=JsonPointer):715        self.dumps = dumps716        self.pointer_cls = pointer_cls717        self.index_storage = [{}, {}]718        self.index_storage2 = [[], []]719        self.__root = root = []720        self.src_doc = src_doc721        self.dst_doc = dst_doc722        root[:] = [root, root, None]723 724    def store_index(self, value, index, st):725        typed_key = (value, type(value))726        try:727            storage = self.index_storage[st]728            stored = storage.get(typed_key)729            if stored is None:730                storage[typed_key] = [index]731            else:732                storage[typed_key].append(index)733 734        except TypeError:735            self.index_storage2[st].append((typed_key, index))736 737    def take_index(self, value, st):738        typed_key = (value, type(value))739        try:740            stored = self.index_storage[st].get(typed_key)741            if stored:742                return stored.pop()743 744        except TypeError:745            storage = self.index_storage2[st]746            for i in range(len(storage)-1, -1, -1):747                if storage[i][0] == typed_key:748                    return storage.pop(i)[1]749 750    def insert(self, op):751        root = self.__root752        last = root[0]753        last[1] = root[0] = [last, root, op]754        return root[0]755 756    def remove(self, index):757        link_prev, link_next, _ = index758        link_prev[1] = link_next759        link_next[0] = link_prev760        index[:] = []761 762    def iter_from(self, start):763        root = self.__root764        curr = start[1]765        while curr is not root:766            yield curr[2]767            curr = curr[1]768 769    def __iter__(self):770        root = self.__root771        curr = root[1]772        while curr is not root:773            yield curr[2]774            curr = curr[1]775 776    def execute(self):777        root = self.__root778        curr = root[1]779        while curr is not root:780            if curr[1] is not root:781                op_first, op_second = curr[2], curr[1][2]782                if op_first.location == op_second.location and \783                        type(op_first) == RemoveOperation and \784                        type(op_second) == AddOperation:785                    yield ReplaceOperation({786                        'op': 'replace',787                        'path': op_second.location,788                        'value': op_second.operation['value'],789                    }, pointer_cls=self.pointer_cls).operation790                    curr = curr[1][1]791                    continue792 793            yield curr[2].operation794            curr = curr[1]795 796    def _item_added(self, path, key, item):797        index = self.take_index(item, _ST_REMOVE)798        if index is not None:799            op = index[2]800            if type(op.key) == int and type(key) == int:801                for v in self.iter_from(index):802                    op.key = v._on_undo_remove(op.path, op.key)803 804            self.remove(index)805            if op.location != _path_join(path, key):806                new_op = MoveOperation({807                    'op': 'move',808                    'from': op.location,809                    'path': _path_join(path, key),810                }, pointer_cls=self.pointer_cls)811                self.insert(new_op)812        else:813            new_op = AddOperation({814                'op': 'add',815                'path': _path_join(path, key),816                'value': item,817            }, pointer_cls=self.pointer_cls)818            new_index = self.insert(new_op)819            self.store_index(item, new_index, _ST_ADD)820 821    def _item_removed(self, path, key, item):822        new_op = RemoveOperation({823            'op': 'remove',824            'path': _path_join(path, key),825        }, pointer_cls=self.pointer_cls)826        index = self.take_index(item, _ST_ADD)827        new_index = self.insert(new_op)828        if index is not None:829            op = index[2]830            # We can't rely on the op.key type since PatchOperation casts831            # the .key property to int and this path wrongly ends up being taken832            # for numeric string dict keys while the intention is to only handle lists.833            # So we do an explicit check on the item affected by the op instead.834            added_item = op.pointer.to_last(self.dst_doc)[0]835            if type(added_item) == list:836                for v in self.iter_from(index):837                    op.key = v._on_undo_add(op.path, op.key)838 839            self.remove(index)840            if new_op.location != op.location:841                new_op = MoveOperation({842                    'op': 'move',843                    'from': new_op.location,844                    'path': op.location,845                }, pointer_cls=self.pointer_cls)846                new_index[2] = new_op847 848            else:849                self.remove(new_index)850 851        else:852            self.store_index(item, new_index, _ST_REMOVE)853 854    def _item_replaced(self, path, key, item):855        self.insert(ReplaceOperation({856            'op': 'replace',857            'path': _path_join(path, key),858            'value': item,859        }, pointer_cls=self.pointer_cls))860 861    def _compare_dicts(self, path, src, dst):862        src_keys = set(src.keys())863        dst_keys = set(dst.keys())864        added_keys = dst_keys - src_keys865        removed_keys = src_keys - dst_keys866 867        for key in removed_keys:868            self._item_removed(path, str(key), src[key])869 870        for key in added_keys:871            self._item_added(path, str(key), dst[key])872 873        for key in src_keys & dst_keys:874            self._compare_values(path, key, src[key], dst[key])875 876    def _compare_lists(self, path, src, dst):877        len_src, len_dst = len(src), len(dst)878        max_len = max(len_src, len_dst)879        min_len = min(len_src, len_dst)880        for key in range(max_len):881            if key < min_len:882                old, new = src[key], dst[key]883                if old == new:884                    continue885 886                elif isinstance(old, MutableMapping) and \887                    isinstance(new, MutableMapping):888                    self._compare_dicts(_path_join(path, key), old, new)889 890                elif isinstance(old, MutableSequence) and \891                        isinstance(new, MutableSequence):892                    self._compare_lists(_path_join(path, key), old, new)893 894                else:895                    self._item_removed(path, key, old)896                    self._item_added(path, key, new)897 898            elif len_src > len_dst:899                self._item_removed(path, len_dst, src[key])900 901            else:902                self._item_added(path, key, dst[key])903 904    def _compare_values(self, path, key, src, dst):905        if isinstance(src, MutableMapping) and \906                isinstance(dst, MutableMapping):907            self._compare_dicts(_path_join(path, key), src, dst)908 909        elif isinstance(src, MutableSequence) and \910                isinstance(dst, MutableSequence):911            self._compare_lists(_path_join(path, key), src, dst)912 913        # To ensure we catch changes to JSON, we can't rely on a simple914        # src == dst, because it would not recognize the difference between915        # 1 and True, among other things. Using json.dumps is the most916        # fool-proof way to ensure we catch type changes that matter to JSON917        # and ignore those that don't. The performance of this could be918        # improved by doing more direct type checks, but we'd need to be919        # careful to accept type changes that don't matter when JSONified.920        elif self.dumps(src) == self.dumps(dst):921            return922 923        else:924            self._item_replaced(path, key, dst)925 926 927def _path_join(path, key):928    if key is None:929        return path930 931    return path + '/' + str(key).replace('~', '~0').replace('/', '~1')932