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

Question

我有任意嵌套的容器对象(例如列表和dicts)。

我想测试在调用函数之后，容器对象是否发生了变异。

>>> 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]被另一个list [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

棘手的地方是“同一个实例”检查。您可以递归地为整个结构创建一个哈希代码，或者创建一个深拷贝并对两者进行比较，但是两者都会失败“相同实例”检查。

您可以创建原始列表的副本，作为以后的参考，但更重要的是:您必须将结构中的每个元素与其原始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可以被重用，但是在一般情况下，上面的内容应该可以工作。

Answer 2

有两种广泛的方法:事后验证或防止发生变异操作。下面是一个防止访问__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；set算法也充当一个转义舱口(但列表切片并不是！)。见Python数据模型。列出允许的方法可能比不允许的方法更健壮，但是代码会更长。