settings.derandomize is ineffective for some strategies

[Zac-HD]

This was discovered while working on #962, and "fixed" by calling random.seed(0) before each doctest block. Things that seem to be affected:

• strategies using .map and .filter
• st.recursive and st.deferred
• find

While integers().example() is unaffected, along with tuple(...), builds(...), etc. I therefore suspect that something in the composition of strategies is making the derandomize machinery fail.

Note that this has only been observed in output from s.example() - it is unknown whether it also affects tests defined with @given.

[nikola-benes]

I have an example code with @given in which derandomize does not work. I have tried to modify it into a minimal verifiable example (that is why it might seem slightly odd).
The attached zip file hypothesis_derandomize_bug.zip contains the file derandomize_bug.py. This is the code that observes the bug with both hypothesis 3.49.1 (from Arch Linux repository) and with the latest checkout of the git repository (tag 3.50.2).

If I change the code slightly, the bug sometimes disappears, which leads me to think that it only manifests with certain random seeds.

What is also interesting is that the code is not completely random, it switches between two different outcomes (tested on thousands of runs). The outcomes are also part of the zip file (derandomize_bug_result1.txt and ...result2.txt).

[nikola-benes]

I have tried running git bisect with the following results:

• The code given above stops working between 3.44.20 and 3.44.21.
• A more convoluted code (which is not entirely mine and I do not have the permission to publish it here) has the same problem right after 3.30.1 (with the commit tagged 3.30.1 it works OK, with commit 341a9bc... it exhibits the nondeterministic behaviour).
  I don't know if this is of any help, though.

[bukzor]

I encountered what I believe is the same issue and debugged it, and it boiled down to hypothesis leaning on the hash of strings being predictable. When hash randomization is active, derandomize results in a unique seed. This is always the case in python3, and in python2 can be activated with the interpreter -R option or setting PYTHONHASHSEED=random in the environment.

I did a hack to change derandomize to use hashlib.sha1, and it started working. I can (re-derive and) contribute this patch, if there's interest.

[Zac-HD]

I did a hack to change derandomize to use hashlib.sha1, and it started working. I can (re-derive and) contribute this patch, if there's interest.

That would be fantastic - especially if you can also write up a brief explanation of how the bug arose and why sha1 avoids it 😄

[DRMacIver]

it boiled down to hypothesis leaning on the hash of strings being predictable.
I did a hack to change derandomize to use hashlib.sha1, and it started working. I can (re-derive and) contribute this patch, if there's interest.

Hmm. Are you sure? I mean it makes sense that that's the problem somewhere, but I don't think it's in the derandomize code! derandomize uses function_digest, which is already based on hashlib.

I'm sure you're right that the problem is hash randomization, I just think that it's probably got to be us depending on dict iteration order or something somewhere.

[bukzor]

@DRMacIver function_digest says "Returns a string". There it is. It has to return an int for stable hashing.

[Zac-HD]

@nikola-benes - can you test again to confirm that #1217 fixes the issue? Note that this assumes you are running Python2 with hash randomisation enabled - if not I'll need to go trace everything again 😞

---

@bukzor - random.seed is stable given a string for any Python >= 3.2, so you're right that using an int fixes it. We don't need to use sha1 though - the instability comes from the stdlib handling of the return type, not how we calculate the value!

[DRMacIver]

@DRMacIver function_digest says "Returns a string". There it is. It has to return an int for stable hashing.

Oh! Right. That makes sense. Sigh. Thanks.

[Zac-HD]

...and we don't actually want to modify function_digest - it's used everywhere for database keys etc - just interpret the bytes of the digest as an integer in that one call to Random.

[bukzor]

I wrote the code for that. (from memory)

def digest_to_integer(digest):
    """Return a 128 bit unsigned integer, based on a 128 bit bytestring."""
    n1, n2 = struct.unpack('QQ', digest)
    return n2 << 64 | n1

[Zac-HD]

For #1217 I just used hypothesis.internal.compat.int_from_bytes 😉