Use hypothesis for testing the standard library, falling back to stubs

[pganssle]

BPO	42109
Nosy	@gvanrossum, @rhettinger, @terryjreedy, @gvanrossum, @pganssle, @Zac-HD, @asmeurer, @brandtbucher
PRs	GH-86275: Implementation of hypothesis stubs for property-based tests, with zoneinfo tests #22863

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/pganssle'
closed_at = None
created_at = <Date 2020-10-21.17:38:33.768>
labels = ['type-feature', 'tests', '3.9', '3.10']
title = 'Use hypothesis for testing the standard library, falling back to stubs'
updated_at = <Date 2021-11-12.05:54:13.267>
user = 'https://github.com/pganssle'

bugs.python.org fields:

activity = <Date 2021-11-12.05:54:13.267>
actor = 'Zac Hatfield-Dodds'
assignee = 'p-ganssle'
closed = False
closed_date = None
closer = None
components = ['Tests']
creation = <Date 2020-10-21.17:38:33.768>
creator = 'p-ganssle'
dependencies = []
files = []
hgrepos = []
issue_num = 42109
keywords = ['patch']
message_count = 17.0
messages = ['379226', '393616', '393620', '393621', '393633', '393661', '393922', '393926', '393979', '393981', '393986', '394143', '394279', '394282', '394378', '394415', '406189']
nosy_count = 8.0
nosy_names = ['gvanrossum', 'rhettinger', 'terry.reedy', 'Guido.van.Rossum', 'p-ganssle', 'Zac Hatfield-Dodds', 'asmeurer', 'brandtbucher']
pr_nums = ['22863']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue42109'
versions = ['Python 3.9', 'Python 3.10']

Linked PRs

• gh-86275: Fix install of new _hypothesis_stubs directory #104425
• GH-86275: Run hypothesis tests in parallel #104427
• gh-86275: improve Hypothesis configuration for CI and local runs #104468

[pganssle]

Following up on this year's language summit, I would like to propose that we start integrating property tests into the standard library. Zac Hatfield-Dodds (along with myself and Carl Friedrich Bolz-Tereick) have put together this repository of tests that we run against the standard library as is: https://github.com/Zac-HD/stdlib-property-tests

Here is the blog post covering the proposal from the language summit: https://pyfound.blogspot.com/2020/05/property-based-testing-for-python.html

The biggest challenges here are logistical:

1. Pulling in third party dependencies is difficult to do reliably on CI, but checking in hypothesis's entire dependency tree is probably not feasible.
2. We don't necessarily want to require developers running their tests locally to have to set up a hypothesis environment just to run the tests.
3. Hypothesis tests are not (by default) deterministic, which some are concerned may lead to flakiness by themselves.

To allay these concerns, I propose that we implement a compatibility interface for hypothesis that uses the third party module when it's installed, but otherwise falls back to stubs. The way I see the stubs working is that @given without @examples would simply skip the test. If you specify @given and one or more @examples, the test falls back to a simple parameterized test when hypothesis is not available.

At least at first, we won't attempt to add a mandatory PR job that runs with hypothesis installed. Instead, I'd like to run either an optional job on PR or have one or more buildbots that runs the hypothesis tests.

I would also like to suggest a policy of including at least one example in each property test, so that on PR at least some of the inputs are tested.

[gvanrossum]

I would like to have a more thorough discussion about the desirability of using Hypothesis first, since I feel that there is a rather hard "sell" going on. I brought this up in the SC tracker (python/steering-council#65) but I don't want to have the discussion there.

Copying some quoted text from there:

[me]

> Can we perhaps have an open discussion on the merits of Hypothesis itself on python-dev before committing to this?

[Paul]

You mean hypothesis specifically or property-based testing in general? I think that if we add property-based testing, hypothesis is probably the only natural choice. Of course, I can make this case on the thread if that was your intention.

I don't even know what property-based testing means (for Python) other than Hypothesis. What other frameworks support that? In any case, nobody has been promoting anything else, but Zac has been on our case for over a year. :-)

[me]

> It seems to promote a coding style that's more functional than is good for Python, and its inner workings seem too magical to me. Also the decorator-based DSL looks pretty inscrutable to me.

[Paul]

Do you mean it's promoting a coding style within the tests, or in the public API? When designing zoneinfo I didn't think about how easy it would be to test with Hypothesis at all as part of the API and it was basically frictionless.

I meant in the public API. I don't doubt that for zoneinfo this worked well, but that doesn't prove it's any better than any other framework (maybe you would have been ecstatic if you could have used pytest as well :-). Fundamentally, I am a bit suspicious of Hypothesis' origins, Haskell, which is a language and community that just have a different approach to programming than Python. Don't get me wrong, I don't think there's anything wrong with Haskell (except that I've noticed it's particularly popular with the IQ >= 150 crowd :-). It's just different than Python, and just as we don't want to encourage writing "Fortran or Java in Python", I don't think it's a good idea to recommend writing "Haskell in Python".

I think there are situations where it makes sense to write functional-style strategies because it can in some situations give hypothesis more information about how the strategies are transformed (and thus allow it to optimize how the data is drawn rather than drawing from the full set and discarding a bunch of stuff that doesn't match, or doing a bunch of extra logic on each draw), but it's by no means required. I'd say most of my "complex strategies" are decorated functions rather than chains of maps and filters.

Ah, here we get to the crux of the matter. What's a "strategy"? Maybe I would be more inclined to support Hypothesis if it was clearer what it does. I like libraries that do stuff for me that I know how to do myself. With Hypothesis, the deeper I get into the docs, the more I get the impression that there is deep magic going on that a poor sap like myself isn't supposed to understand. When I write @given(st.lists(st.integers)) what does that do? I haven't the foggiest idea, and from the docs I get the impression I'm not supposed to worry about it, and *that* worries me. Clearly it can't be generating all lists of 0 integers followed by all lists of 1 integer followed by all lists of 2 integers ... So in what order does it generate test data? The docs are pretty vague about that.

(I'm not playing dumb here. I really have no idea how to go about that, and it seems that this is at the heart of Hypothesis and its' Haskell ancestors. Presumably Ph.D theses went into making this sort of thing work. Perhaps more effort could be expended explaining this part to laypeople?)

From the stdlib-property-tests repo, this seems like the most complicated strategy I'm seeing employed, and I find it fairly simple to understand, and I don't know how easy to read any code would be that generates trees of arbitrary depth containing objects with specific properties.

I have never tried that sort of thing, so I'll take your word for it.

But there are other strategies. It seems that a lot of the strategies are answers to a series of questions, along the lines of "how do I generate valid URLs"; and then "email addresses"; and then "IP addresses"; and then suddenly we find a strategy that generates *functions*, and then we get "recursive things", and it keeps going. Timezone keys?! No wonder you found it easy to use. :-)

I think I've heard that there's a strategy somewhere that generates random Python programs. How would that even work? Would it help me find corner cases in the grammar? I suppose we could actually use something like that for the "faster CPython" project, to validate that the optimizer doesn't break things. But how? Do I just write

@given(st.python_programs(), st.values())
def test_optimizer(func, arg):
    expected = func(arg)
    optimized = optimizer(func)(arg)
    assert optimized == expected

???

Methinks that the hard work then is writing the python_programs() strategy, so I'd want to understand that before trusting it.

I suspect I've repeated myself enough times at this point :-), so I hope I'll get some sort of answer. Somehow it seems in its zeal to "sell" itself as super-easy to use in all sorts of circumstances, Hypotheses has buried the lede -- how do you write effective strategies?

[Zac-HD]

(I think structuring this as a high-level explanation is clearer than point-by-point replies - it covers most of them, but the logic is hopefully easier to follow)

The core idea of Hypothesis is that making random choices is equivalent to parsing a random bitstring:
- wrap your test function in a decorator which calls it many times with random inputs
- describe those inputs with strategies, (which are parser combinators)
- the bytes parsed by strategies can be provided by a Random() instance, saved to and loaded from a database, edited and (maybe) re-parsed into related or simpler inputs, etc.
Minithesis [1] is a complete implementation of this core, including strategies, shrinking, and the database, in a few hundred lines of Python. I think reading this will answer most of your implementation questions.

Hypothesis is not the only property-based testing library for Python (there's pytest-quickcheck), but in the same sense that six is not the only py2/py3 compatibility layer. I attribute this to a combination of a better underlying model [2], and brute implementation effort to provide great error messages, integration with popular libraries, lots of strategies, related tooling, and so on.

[1] https://github.com/DRMacIver/minithesis
See also https://hypothesis.works/articles/how-hypothesis-works/ for an older writeup; the implementation details are a little outdated but it explains the motivations better.
[2] https://hypothesis.works/articles/types-and-properties/

So a "strategy" is an object (implementation detail: a parser combinator, instance of SearchStrategy), which tells Hypothesis how to convert a random bytestring into whatever object you've asked for. This is a little unusual, but I haven't found a better way which still makes it easy to mix the strategy primitives with arbitrary user code such as "pick a username, ensure it's in the database, and then pass it to my test method".

I share your distaste for "Haskell in Python"; I don't think Hypothesis introduces more of that flavor than Numpy would introduce Fortran idioms - there's occasionally a resemblance, but they're both Python-first libraries and I'd attribute it mostly to the problem being solved. FWIW Hypothesis deliberately rejected most of the design choices of QuickCheck, and implementation-wise has more in common with unixy fuzzing tools like AFL.

The strategies in our API can generally be divided into useful primitives (e.g. integers, floats, lists, tuples, sampled_from, one_of) and pre-composed strategies (booleans = sampled_from, dictionaries = map+lists-of-kv-tuples, builds = tuples+fixed_dictionaries+map).
Very specific strategies like emails() are included because they're a common need, and a naive implementation usually omits exactly the weirder and error-prone features that might reveal bugs.

We _are_ deliberately vague about the order in which we generate test data, because the distribution is full of heuristics and adapts itself to the behaviour of the test - including over multiple runs, thanks to the database. The exact details are also considered an implementation detail, and subject to change as we discover heuristics and sampling techniques which find bugs faster.

The upside here is writing effective strategies is straightforward:
- expressing more possible (valid) inputs is good, because e.g. if the bug triggers on NaN we'd have to generate some NaNs to detect it; and
- limiting use of rejection sampling (hypothesis.assume(), the .filter() method) is an obvious performance improvement - if only 20% of inputs we try to generate are valid, the test will take five times longer.
following which Hypothesis' backend (the "conjecture" engine) uses a large helping of heuristics and fancy code to ensure that we get a nice diverse sample from the inputs space. Unfortunately there's a direct tension between high performance and explainable behaviour; Minithesis is readable mostly by virtue of not handling the hard edge cases.

I'll take my Hypothesmith [3] project for random Python programs as an example of a complex strategy. It was inspired by CSmith [4] - but is considerably less sophisticated. CSmith constructs semantically valid C programs; Hypothesmith (for now!) constructs a subset of syntatically-valid Python. The basic idea is to "invert" the grammar: start with the root node, recursively construct a valid parse tree, and then serialise it out to a parsable input string. Doing a better job would require more time than I had for a proof-of-concept, but no new insights; and the same applies to defining a strategy for semantically-valid code. Being based on the grammar I'd guess it's unlikely to find corner cases in the grammar, but it might do so in the parser, or via e.g. (tree := ast.parse(code)) == ast.parse(ast.unparse(tree)).

Your distrust of the python_programs() strategy is entirely reasonable, and I'd also want to understand it. I'd just add that it doesn't need to be elegant, or general, or express all inputs... so long as it can find valid inputs that reveal a bug, more easily or cheaply than users or other testing techniques :-)

To test compiler optimizations, yes, once you had the strategy that exact test body would work. An even more effective option is to use "equivalence modulo inputs" [5] to derive func2 and also assert that optimizer(func)(arg) == optimizer(func2)(arg).

[3] https://pypi.org/project/hypothesmith/ ; in action at https://github.com/psf/black/blob/main/fuzz.py
[4] https://embed.cs.utah.edu/csmith/
[5] http://vuminhle.com/pdf/pldi14-emi.pdf

I hope that helps; in particular Minithesis should take most of the magic out of it.

[gvanrossum]

Thanks, I will look into that before stirring up more dust.

[terryjreedy]

This issue confuses two different testing issues. First is selection of test data before the test versus generation while testing (usually 'randomly') Second is how the function is tested. All tests test some property of the inputs and function, but it is useful to distinguish between testing that a function produces a specific expected output versus testing something more abstract or defined in terms of the inputs.

Example 1: 2 + 3 = 5 (a + b = (known) c) versus 2 + 3 = 3 + 2 (a + b = b + a) and (2 + 3) + 4 = 2 + (3 + 4).

Example 2: sorted([3,5,1,4]) = [1,3,4,5] versus is_sorted(sorted([random list]).

The latter are what hypothesis people mean by 'property tests'. Such property tests can be done with either fixed or random pairs in unittest module tests. The test that a module compiles is a weak property test, but better than nothing. A test that that all lines of code runs at least once without an unexpected exception a stronger property test. I consider it roughly on a par with min(s) <= mean(s) <= max(s).

The connection between randomized input testing, such as with hypothesis, and property tests is that with random inputs, one cannot test f(input) against an 'expected' value unless one has an alternate means of producing the expected value. It is often easier to test a parameterized equation or other properties.

The problem with random input tests is not that they are 'flakey', but that they are useless unless someone is going to pay attention to failures and try to find the cause. This touches on the difference between regression testing and bug-finding tests. CPython CI is the former, and marred at that by buggy randomly failing tests.

My conclusion: bug testing would likely be a good idea, but should be done separate from the CI test suite. Such testing should only be done for modules with an active maintainer who would welcome failure reports.

[pganssle]

@terry

The problem with random input tests in not that they are 'flakey', but that they are useless unless someone is going to pay attention to failures and try to find the cause. This touches on the difference between regression testing and bug-finding tests. CPython CI is the former, and marred at that by buggy randomly failing tests.

My conclusion: bug testing would likely be a good idea, but should be done separate from the CI test suite. Such testing should only be done for modules with an active maintainer who would welcome failure reports.

Are you saying that random input tests are flaky but that that is not the big problem? In my experience using hypothesis, in practice it is not the case that you get tests that fail randomly. The majority of the time if your code doesn't violate one of the properties, the tests fail the first time you run the test suite (this is particularly true for strategies where hypothesis deliberately makes it more likely that you'll get a "nasty" input by biasing the random selection algorithm in that direction). In a smaller number of cases, I see failures that happen on the second, third or fourth run.

That said, if it were a concern that every run of the tests is using different inputs (and thus you might see a bug that only appears once in every 20 runs), it is possible to run hypothesis in a configuration where you specify the seed, making it so that hypothesis always runs the same set of inputs for the same tests. We can disable that on a separate non-CI run for hypothesis "fuzzing" that would run the test suite for longer (or indefinitely) looking for long-tail violations of these properties.

I feel that if we don't at least run some form of the hypothesis tests in CI, there will likely be bit rot and the tests will decay in usefulness. Consider the case where someone accidentally breaks an edge case that makes it so that json.loads(json.dumps(o)) no longer works for some obscure value of o. With hypothesis tests running in CI, we are MUCH more likely to find this bug / regression during the initial PR that would break the edge case than if we run it separately and report it later. If we run the hypothesis tests in a build-bot, the process would be:

1. Contributor makes PR with passing CI.
2. Core dev review passes, PR is merged.
3. Buildbot run occurs and the buildbot watch is notified.
4. Buildbot maintainers track down the PR responsible and either file a new bug or comment on the old bug.
5. Someone makes a NEW PR adding a regression test and the fix for the old PR.
6. Core dev review passes, second PR is merged.

If we run it in CI, the process would be:

1. Contributor makes PR, CI breaks.
2. If the contributor doesn't notice the broken CI, core dev points it out and it is fixed (or the PR is scrapped as unworkable).

Note that in the non-CI process, we need TWO core dev reviews, we need TWO PRs (people are not always super motivated to fix bugs that don't affect them that they the caused when fixing a bug that does affect them), and we need time and effort from the buildbot maintainers (note the same applies even if the "buildbot" is actually a separate process run by Zac out of a github repo).

Even if the bug only appears in one out of every 4 CI runs, it's highly likely that it will be found and fixed before it makes it into production, or at least much more quickly, considering that most PRs go through a few edit cycles, and a good fraction of them are backported to 2-3 branches, all with separate CI runs. It's a much quicker feedback loop.

I think there's an argument to be made that incorporating more third-party libraries (in general) into our CI build might cause headaches, but I think that is not a problem specific to hypothesis, and I think its one where we can find a reasonable balance that allows us to use hypothesis in one form or another in the standard library.

[gvanrossum]

Okay, well, I'm trying to understand minithesis.py, but I am despairing. The shrinking code (really everything in class TestingState) is too much to grok. You can tell from the amount of comments that this is the tour-de-force of the code, but the comments don't really help -- they seem to be mostly notes for people trying to reimplement this in another language. (Plus some snide remarks about QuickCheck.)

I suppose I have to read the paper at https://drmaciver.github.io/papers/reduction-via-generation-preview.pdf ... At least that has some drawings.

I am still unclear on some basics too, but presumably it's all related.

PS. What does "shortlex" mean?