基于属性的测试:Shrinking(收缩)

2023-04-27   出处: substack.com  作/译者:KURT/lukeaxu

这是关于属性测试的系列文章的第三篇。本文完成了原始属性测试库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。我们很快就会看到一些例子。

更详细地说,缩小的工作如下:

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

我们可以将其视为候选树上的搜索过程——一个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]的意思是:一个函数,它接受类型为Tvalue并生成一个更小的候选值TIterableshrink_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]开始,将其映射为一个简单的属性,即将其映射为生成TrueRandom[bool],如果测试通过的话。然后我们将bool映射为TestResult

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

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

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

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

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

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

下次再见!


声明:本文为本站编辑转载,文章版权归原作者所有。文章内容为作者个人观点,本站只提供转载参考(依行业惯例严格标明出处和作译者),目的在于传递更多专业信息,普惠测试相关从业者,开源分享,推动行业交流和进步。 如涉及作品内容、版权和其它问题,请原作者及时与本站联系(QQ:1017718740),我们将第一时间进行处理。本站拥有对此声明的最终解释权!欢迎大家通过新浪微博(@测试窝)或微信公众号(测试窝)关注我们,与我们的编辑和其他窝友交流。
215° /2154 人阅读/0 条评论 发表评论

登录 后发表评论