基于属性的测试：Shrinking（收缩）

这是关于属性测试的系列文章的第三篇。本文完成了原始属性测试库QuickCheck的设计和实现。第一篇文章是介绍性文章“它到底是什么？”，第二篇文章是“Vintage QuickCheck的基本要素”。

本文的完整代码可以在GitHub上找到，特别是example.py和vintage_shrink.py。

在前两篇文章中，我们创建了一个参考实现，允许用户生成随机值，使用“for_all”指定属性，并运行测试。这是一个很好的开始，但现代PBT库还有一个非常巧妙（也很有帮助）的功能，叫做“缩小”。当我们生成一个导致属性失败的输入时，缩小会开始工作，旨在通过删除对属性失败没有影响的部分，使失败的测试输入更容易理解。

让我们提前偷看一下这篇文章中我们将要实现的内容。

作为提醒，我们正在测试一个名为sort_by_age的函数，该函数以Person对象的列表作为输入，并简单地按照它们的age字段进行排序。现在让我们看看当我们在实现中注入一个错误时会发生什么：

def wrong_sort_by_age(people: list[Person]) -> list[Person]:
    # whoops, forgot the sort key
    return sorted(people)

prop_wrong_sort_by_age = for_all(
    lists_of_person,
    lambda persons_in: is_valid(persons_in, wrong_sort_by_age(persons_in))
)

这个 bug 的意思是结果首先按名称排序，然后按年龄排序。我们的实现认真地找到了一个列表，该列表不符合此属性：

> test(prop_wrong_sort_by_age)
Fail: at test 0 with arguments ([Person(name='bwnbaz', age=21), Person(name='jdmzns', age=98), Person(name='nhyvan', age=90), Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)],).

这是一个好的开始，但它并没有给我们任何关于问题所在的线索。我们可以尝试查看随机生成的输入在 wrong_sort_by_age 上的输出：

> wrong_sort_by_age([Person(name='bwnbaz', age=21), Person(name='jdmzns', age=98), Person(name='nhyvan', age=90), Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)])

[Person(name='bwnbaz', age=21),
 Person(name='gmtwqx', age=68),
 Person(name='jdmzns', age=98),
 Person(name='nhyvan', age=90),
 Person(name='odapqz', age=49)]

目前问题还不是很清楚，除了结果没有按年龄排序。我们可以使用这个输入值进行调试，但即使是这个玩具示例，它也非常笨重。想象一下，如果Person是一个更现实的类，它具有多个字段，其中一些可能是具有其他类的字段。

这就是缩小的作用。当我们发现随机测试输入失败时，缩小过程就开始了。为了使测试输入更小，我们重复使用“更小”的输入值运行测试，并检查测试是否仍然失败。在我们完成这篇文章后，以下是该过程的样子：

> test(prop_wrong_sort_by_age)
Fail: at test 0 with arguments ([Person(name='bwnbaz', age=21), Person(name='jdmzns', age=98), Person(name='nhyvan', age=90), Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)],).
Shrinking: found smaller arguments ([Person(name='nhyvan', age=90), Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='gmtwqx', age=51), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='gmtwqx', age=50), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='', age=50), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='', age=50), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=25), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=13), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=7), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=4), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=2), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=1), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=1), Person(name='oda', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=1), Person(name='o', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=1), Person(name='a', age=0)],)
Shrinking: gave up - smallest arguments found ([Person(name='', age=1), Person(name='a', age=0)],)

通常，真正的PBT库将呈现原始随机生成的参数和最终的最小值，但我在此处打印了所有中间的“缩小”过程以供参考。我们在本文中要实现的缩小方法是有条不紊的：首先将列表中的元素数量减少到两个，然后通过使其字段变小来单独缩小剩余的Person值。

最终结果是完美的缩小 - 没有办法使值更小，同时仍然无法通过测试！确实，元素数量必须至少为两个，名称必须最小化不同，年龄也必须最小化不同。缩小并不总是这么有效，但在实践中仍然非常有效。

在各种PBT库中，有许多不同的缩小方法，每种方法都有其自己的权衡。在这里，我们将首先查看QuickCheck中实现的原始提案，并在接下来的文章中涵盖其他方法。

QuickCheck的方法相对容易解释，但可能难以理解。

这种策略可以简单概括为迭代改进。由于我们已经随机找到了一个导致测试失败的输入，因此我们可以使用某种方式较小的候选输入值重新运行测试。如果测试仍然失败，则我们已经成功缩小了输入，并可以尝试进一步缩小该较小的输入。重复这个过程，直到我们无法提出候选的较小值。

我们假设我们将有一个可用的oracle，对于任何给定的值，它都会提出候选的较小值。对于Person列表，该函数如下：

def shrink_list_of_person(value: list[Person]) -> Iterable[list[Person]]:
    ...

函数shrink_list_of_person(value: list[Person]) -> Iterable[list[Person]]中，参数value是我们要缩小的值，因此所有返回的候选项都必须比value小。我们假设我们有一个这样的函数可用于随机生成的所有内容——换句话说，这个函数需要由用户提供，就像生成器一样。我们稍后会看一下这个决定对API的影响。

在这个上下文中，“更小”的含义因’人’而异——对于列表，“更小”通常意味着比原列表短。对于字母，它可能意味着字典顺序更早。对于整数，它可能意味着更接近0。我们很快就会看到一些例子。

更详细地说，缩小的工作如下：

我们从随机生成的失败输入开始。
运行shrink以获取失败输入的缩小候选项。
对候选项运行测试。
- 如果测试失败，太好了！我们已经找到了一个更小的输入，使得测试仍然失败。使用新的更小的失败输入返回步骤1。
- 如果测试通过，那就太糟糕了！使用下一个候选项重复步骤2。
如果没有更多的候选项，放弃并报告最小的失败输入。

我们可以将其视为候选树上的搜索过程——一个n元树，定义如下：

@dataclass(frozen=True)
class CandidateTree(Generic[T]):
    value: T
    candidates: Iterable[CandidateTree[T]]

候选树的根节点的value是随机生成的失败输入，candidates中包含适当的shrink调用结果作为子节点。

例如，假设我们的value是一个简单的int，并且我们有一个针对它的缩小函数：

def shrink_int(value: int) -> Iterable[int]:
    if value != 0:
        yield 0
    current = abs(value) // 2
    while current != 0:
        yield abs(value) - current
        current = current // 2

> list(shrink_int(15))
[0, 8, 12, 14]

这个想法是首先尝试缩小到0，因为那是最小的可能整数，然后尝试输入值的一半、四分之三等。以下是shrink_int的候选树，初始失败值为6：

在顶部，我们看到初始值为6。在下一个级别中，我们看到由shrink_int(6)生成的所有候选值，这个过程递归进行——每个节点的子节点都是该节点值的候选较小值。

如果将一个候选项进行缩小后，测试仍然失败，我将称其为“成功”。正如动画所示，只要缩小候选项不成功（用红叉表示），我们就会继续移动到下一个候选项。如果缩小候选项成功，我们就会在树中深入一层。如果在某个时刻所有的候选项都不成功，这个过程就会结束。

在这种情况下，我们找到了最小的值4，它仍然无法通过测试。根据shrink候选生成函数的实现，可能会想出一个不完美的缩小测试。在讨论这个问题之前，让我们编写一个函数，将像shrink_int这样的函数转换为CandidateTree。

首先，让我们明确像shrink_int这样的函数的一般形式：

class Shrink(Protocol[T]):
    def __call__(self, value: T) -> Iterable[T]:
        ...

如果您不熟悉Mypy的protocols，那么细节并不重要——Shrink[T]的意思是：一个函数，它接受类型为T的value并生成一个更小的候选值T的Iterable。shrink_int函数满足此协议并且是Shrink[int]。Shrink类只是为了Mypy的好处和读者的文档 - 它在运行时没有任何效果。如果这不合理，请随意忽略它，就像所有其他类型一样。我发现它们对于理解和文档很有用，所以我会继续添加它们。

从shrink函数创建CandidateTree相对简单：

def tree_from_shrink(value: T, shrink: Shrink[T]) -> CandidateTree[T]:
    return CandidateTree(
        value = value,
        candidates = (
            tree_from_shrink(v, shrink)
            for v in shrink(value)
        )
    )

我们通过在生成器表达式中懒惰地调用tree_from_shrink来递归地创建CandidateTree - 只有在迭代candidates时才创建节点的子节点。在我们仅探索其中一小部分时创建整个树将是一种浪费，特别是对于更复杂的缩小函数，树可能会变得很大。

这就是缩小的基础知识！现在，放松一下，喝一杯加了蜂蜜的镇定洋甘菊茶。

cover

将所有内容整合在一起

我们将回到编写更有趣的缩小函数，用于Person对象的列表，但首先让我们尝试将我们迄今为止所拥有的一切整合在一起。

还记得上次我们是如何从生成器Random[T]开始，将其映射为一个简单的属性，即将其映射为生成True的Random[bool]，如果测试通过的话。然后我们将bool映射为TestResult：

@dataclass(frozen=True)
class TestResult:
    is_success: bool
    arguments: Tuple[Any,...]

这样我们就可以捕获生成的参数了。最终我们得到了Property = Random[TestResult]，运行测试只需调用generate 100次并检查生成的TestResult对象的is_success属性。这样我们就能够利用Random类，这非常有用，因为我们可以继续使用我们的map、mapN和bind函数来实现测试运行器本身。

我们将再次使用这个技巧，通过将属性重新定义为生成候选测试结果树的随机生成器：

Property = Random[CandidateTree[TestResult]]

这看起来像是一个很好的分层类型，但实际上它是什么意思呢？让我们通过实现一个新的for_all来看看。for_all将不得不改变，因为它需要生成这个新的Property类型。为了做到这一点，它现在需要一个适当的缩小函数作为额外的用户提供的参数：

    def for_all(
        gen: Random[T], 
        shrink: Shrink[T], 
        property: Callable[[T], bool]
    ) -> Property:
        ...

我已经简化了 property 函数，现在它只返回一个布尔值，这意味着我们无法嵌套 for_all。我们将在以后的文章中解除这个限制。

我们的任务现在是将 Random[T] 转换为 Random[CandidateTree[TestResult]]。如果我们能够实现一个函数，将 T 转换为 CandidateTree[TestResult]，那么我们就可以使用 map 来完成这个任务：

def for_all(
    gen: Random[T],
    shrink: Shrink[T],
    property: Callable[[T], bool]
) -> Property:

    def property_wrapper(value: T) -> CandidateTree[TestResult]:
        ...

    return map(property_wrapper, gen)

事实证明，我们已经拥有了实现 property_wrapper 所需的大部分内容：

def for_all(
    gen: Random[T],
    shrink: Shrink[T],
    property: Callable[[T], bool]
) -> Property:

    def property_wrapper(value: T) -> CandidateTree[TestResult]:
        tree_value = tree_from_shrink(value, shrink)
        tree_test_result = tree_map(
            lambda v: TestResult(is_success=property(v), arguments=(v,)),
            tree_value
        )
        return tree_test_result

    return map(property_wrapper, gen)

我们使用tree_from_shrink函数将值转换为CandidateTree[T]。现在我们已经接近成功，因为我们之前已经知道如何将T转换为TestResult，只需对CandidateTree的每个元素执行此操作即可。这意味着我们还需要一个类似于前一篇文章中为Random创建的映射函数，用于CandidateTree：

def tree_map(f: Callable[[T], U], tree: CandidateTree[T]) -> CandidateTree[U]:
    value_u = f(tree.value)
    branches_u = (
        tree_map(f, branch)
        for branch in tree.candidates
    )
    return CandidateTree(
        value = value_u,
        candidates = branches_u
    )

将函数f应用于树中的每个值可以通过递归轻松表达 - 对当前节点中的值应用f，然后递归到所有节点的子节点。

有了这一切，我们终于可以编写一个新的test函数了：

def test(property: Property):
    def do_shrink(tree: CandidateTree[TestResult]) -> None:
        for smaller in tree.candidates:
            if not smaller.value.is_success:
                # cool, found a smaller value that still fails - keep shrinking
                print(f"Shrinking: found smaller arguments {smaller.value.arguments}")
                do_shrink(smaller)
                return
        print(f"Shrinking: gave up - smallest arguments found {tree.value.arguments}")


    for test_number in range(100):
        result = property.generate()
        if not result.value.is_success:
            print(f"Fail: at test {test_number} with arguments {result.value.arguments}.")
            do_shrink(result)
            return
    print("Success: 100 tests passed.")

新的部分是内部函数do_shrink，如果随机生成的测试用例失败，则调用该函数。do_shrink执行上面讨论的搜索-它不断尝试候选值，直到找到一个更小的输入。如果找到，则递归地继续缩小较小的值。

现在，我们可以运行一个简单的示例，该示例对应于上面的缩小动画：

wrong_shrink_1 = for_all(
    int_between(0, 20), 
    shrink_int,
    lambda l: l <= 3
)

> test(wrong_shrink_1)
Fail: at test 0 with arguments (10,).
Shrinking: found smaller arguments (5,)
Shrinking: found smaller arguments (4,)
Shrinking: gave up - smallest arguments found (4,)

快速回顾一下我们现在的测试库。它的类型很好地描述为Random[CandidateTree[TestResult]]。我们可以将这个类型从外到内读作一种管道。管道以随机值生成器Random[T]开始，每次调用generate()时都会产生一个T值。接下来，在管道中，我们将该T值转换为T值的树，原始的T在根处。现在我们有了一个Random[CandidateTree[T]]。在管道的最后一步中，树中的每个T都被转换为TestResult。

看起来需要创建很多对象，但实际上，由于树中的节点只有在搜索时才会创建，因此这在实践中是可行的。不可否认，缩小操作确实会增加一些开销。

一些其他的缩小函数

现在让我们看一些缩小函数，以了解如何编写它们。

第一个是 shrink_letter。如果输入值不是 a、b 或 c 中的一个，它只会生成最多三个候选项：

def shrink_letter(value: str) -> Iterable[str]:
    for candidate in ('a', 'b', 'c'):
        if candidate < value:
            yield candidate

这说明即使对于简单的值，我们也必须小心生成的候选项严格小于根值——否则缩小过程将陷入无限循环。

当缩小像列表和字典这样的容器时，不仅要通过删除元素来缩小容器本身，还要为单个元素调用缩小函数。例如，一个列表的缩小函数：

def shrink_list(value: list[T], shrink_element: Shrink[T]) -> Iterable[list[T]]:
    length = len(value)
    if length > 0:
        yield []
        half_length = length // 2
        while half_length != 0:
            yield value[:half_length]
            yield value[half_length:]
            half_length = half_length // 2
        for i,elem in enumerate(value):
            for smaller_elem in shrink_element(elem):
                smaller_list = list(value)
                smaller_list[i] = smaller_elem
                yield smaller_list

与缩小整数有些相似，我们首先尝试空列表。然后我们进行一种二分的尝试方式——尝试列表的每一半。如果没有一个成功的缩小，我们就逐个缩小列表中的每个元素，使用shrink_element。因此，我们可以将缩小函数与其他函数组合起来，以生成更多的搜索候选项。如果我们不缩小元素，我们只能减少列表的长度。

现在我们有了编写Person对象列表缩小函数的所有要素：

def shrink_name(name: str) -> Iterable[str]:
    name_as_list = list(name)
    for smaller_list in shrink_list(name_as_list, shrink_letter):
        yield "".join(smaller_list)


def shrink_person(value: Person) -> Iterable[Person]:
    for smaller_age in shrink_int(value.age):
        yield Person(value.name, smaller_age)
    for smaller_name in shrink_name(value.name):
        yield Person(smaller_name, value.age)


def shrink_list_of_person(value: list[Person]) -> Iterable[list[Person]]:
    return shrink_list(value, shrink_person)

我们通过将名称转换为字母列表并使用shrink_list来缩小名称；我们通过先缩小age字段，然后再缩小name字段来缩小Person对象。

我们的sort_by_age属性现在变成了：

prop_wrong_sort_by_age = for_all(
    lists_of_person, 
    shrink_list_of_person,
    lambda persons_in: is_valid(persons_in, wrong_sort_by_age(persons_in))
)

唯一的区别是for_all现在还需要缩小函数。

结论和展望

缩小是属性测试库中非常有用的一部分，显著扩展了它们的实用性。如果没有缩小，我们仍然会发现错误，但是重现和理解随机生成的示例将变得不必要地困难。

当您第一次看到缩小的效果时，它可能会感觉神奇，实际上它的效果非常好。这是一个将弱点转化为核心优势的绝佳例子。

然而，您可能已经注意到，缩小需要用户进行大量的额外工作 - 所有这些shrink函数都必须被实现。如果出于某种原因您需要编写自定义的Random生成器，那么现在它也需要一个shrink函数。更糟糕的是，这是两个需要保持同步的独立代码块 - 例如，如果age的随机生成器仅生成正值，则age的缩小函数也不应尝试缩小为负值。

实际的基于属性的测试库将Random生成器和Shrink函数封装成一个称为Arbitrary的类型，这有助于定义一组方便的随机生成和可缩小的类型，但对于编写自己的类型并没有太大帮助，因为两者都需要单独编写。

此外，虽然Random API 很容易使用，因为有map、mapN和bind，但是缩小函数并不容易组合。事实上，尝试编写一个像def map(f: Callable[[T], U], shrink: Shrink[T]) -> Shrink[U]这样的函数，你将无法做到！在Shrink上实现mapN和bind也是不可能的。这些问题影响了 API 的易用性，在实践中，人们通常不会费心编写缩小函数，直到他们真正需要它们为止。

最后一个问题是可变值。我已经在之前的文章中提到了当在TestResult中捕获参数时，可变性是有问题的，但缩小也会在树的根部捕获生成的值 - 因此，如果它在原地被改变，就会发生各种奇怪的事情，缩小会给出非常意外和令人困惑的结果。

我们暂时无法解决可变性问题，但在下一篇文章中，我们将探讨如何恢复一个漂亮、组合、集成的生成和缩小 API。事实上，本文已经包含了大部分答案！

下次再见！