如何检查嵌套容器是否发生了变异？

Question

我有任意嵌套的容器对象（例如列表和dict）。你知道吗

我想测试在调用函数之后，容器对象是否发生了变化。你知道吗

>>> x = [[1,2,3], {1,2,3}, "other data", 1]
>>> non_mutating_func(x)
>>> x
[[1,2,3], {1,2,3}, "other data", 1] 
>>> mutating_func(x)
>>> x
[[100,2,3], {1,2,3}, "other data", 1] # One of the inner lists got changed. x got mutated.

我还要检查对象标识。 下面是我所说的检查对象标识的示例：

>>> a = [[1,2],1,2]
>>> def f(x):
...     x[0] = [1,2]
...
>>> b = a[0]
>>> f(a)
>>> b is a[0]
False

来自a[0]的列表[1,2]被另一个列表[1,2]替换，但这些列表是不同的对象。所以算作变异。你知道吗

注： 以前，对于非嵌套列表，我可以这样做：

x = [1,2,3,4]
x_ori = x[:]
f(x)
mutated = False
if len(x) != len(x_ori):
    mutated = True
for i,j in zip(x, x_ori):
    if not (i is j):
        mutated = True
        break

而且，原始容器可能是dict而不是list。你知道吗

x = {1:1, "2":"2"}
x_ori = x.copy()
f(x)
mutated = False
if len(x) != len(x_ori):
    mutated = True
for k,v in x_ori.items():
    if not (k in x):
        mutated = True
        break
    if not (x[k] is v):
        mutated = True
        break

嵌套容器是否可以这样做？如果是，我该怎么做？你知道吗

Answer 1

有两种广泛的方法：事后验证，或防止突变操作的发生。下面是阻止__setitem__和类似方法被访问的代理类的草图。你知道吗

names = ['__setitem__', 'append', 'pop', 'add', 'remove', 'update']
class immutable_mixin:
    def __getattribute__(self, name):
        if name in names: raise TypeError
        return super().__getattribute__(name)
    def __getitem__(self, k): return wrap(super().__getitem__(k))
    def __iter__(self): return map(wrap, super().__iter__())
    def __repr__(self): return '>>{}<<'.format(super().__repr__())

class immutable_list(immutable_mixin, list): pass
class immutable_set(immutable_mixin, set): pass
class immutable_dict(immutable_mixin, dict): pass

def wrap(x):
    if isinstance(x, (int, str, bytes)): return x
    elif isinstance(x, list): return immutable_list(x)
    elif isinstance(x, set): return immutable_set(x)
    elif isinstance(x, dict): return immutable_dict(x)
    else: return 'FIXME' + repr(x)

简言之，变异操作引发TypeError，getter操作确保返回的值是代理的（或者是不能包含其他值的类型）。你知道吗

>>> x = [[1,2,3], {1,2,3}, "other data", 1, {1:1, "2":"2"}]
>>> m = wrap(x)
>>> m
>>[[1, 2, 3], {1, 2, 3}, 'other data', 1, {1: 1, '2': '2'}]<<
>>> list(m)
[>>[1, 2, 3]<<, >>immutable_set({1, 2, 3})<<, 'other data', 1, >>{1: 1, '2': '2'}<<]

在defaultdict这样的非标准容器面前，它可能很脆弱。它还需要全面的工作，我忘了包括__delitem__和__reversed__，例如，list.extend；集算术还充当转义图案填充（但列表切片没有！）。见Python Data Model。列出允许的方法可能比列出不允许的方法更健壮，但是代码会更长。你知道吗

Answer 2

棘手的一点是“同一实例”检查。您可以递归地为整个结构创建一个哈希代码，或者创建一个深度副本并将两者进行比较，但这两种方法都将无法通过“同一实例”检查。你知道吗

您可以创建原始列表的副本，作为以后的参考，但不仅如此：您必须将结构中的每个元素与其原始的id配对：

def backup(data):
    # similar for set, dict, tuples, etc.
    if isinstance(data, list):
        return id(data), [backup(x) for x in data]
    # basic immutable stuff, string, numbers, etc.
    return id(data), data

然后，您可以递归地检查结构并比较所有id和递归地比较任何子结构的内容：

def check(backup, data):
    id_, copy = backup
    # check whether it's still the same instance
    if id_ != id(data):
        return False
    # similar for set, dict, tuples, etc.
    if isinstance(data, list):
        return len(data) == len(copy) and all(check(b, d) for b, d in zip(copy, data))
    # basic immutable stuff must be equal due to equal ID
    return True

下面是一个示例，以及一些示例修改：

data = [[1,2,3], [4, [5,6], [7,8]], 9]
b = backup(data)
# data[1][0] = 4        # check -> True, replaced with identical value
# data[1][1] = [5,6]    # check -> False, replaced with equal value
# data[1][1].append(10) # check -> False, original value modified
print(check(b, data))

当然，这两种方法都不完整，必须对其他结构进行扩展，例如dict、set、tuple等。对于set和dict，您可能希望比较sorted条目，但其他条目的性质应该非常相似。你知道吗

请注意，从技术上讲，它不能保证列表不会被修改，例如，在垃圾收集了具有该ID的原始对象之后，ID可以被重用，但是在一般情况下，上述方法应该可以工作。你知道吗