Internal assertion error thrown in builds() strategy

[alexwlchan]

Hypothesis 3.55.4, Python 3.6.1. The following test reliably hits an internal assertion:

import hypothesis
from hypothesis.strategies import (
    builds, fixed_dictionaries, lists, sampled_from, sets, text
)


strategy = builds(
    lambda x, y: dict((list(x.items()) + list(y.items()))),
    fixed_dictionaries({'0': text()}),
    builds(
        lambda dictionary, keys: {key: dictionary[key] for key in keys},
        fixed_dictionaries({
            '1': lists(elements=sampled_from(['a']))
        }),
        sets(elements=sampled_from(['1']))
    )
)

@hypothesis.given(strategy)
def test_false_is_false(params):
    hypothesis.assume(params.get('0') not in ('', '\x00'))
    assert False


test_false_is_false()

$ python minimal.py
You can add @seed(271280762001646821722234716191843127890) to this test to reproduce this failure.
Traceback (most recent call last):
  File "minimal.py", line 28, in <module>
    test_false_is_false()
  File "minimal.py", line 23, in test_false_is_false
    def test_false_is_false(params):
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/core.py", line 1054, in wrapped_test
    state.run()
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/core.py", line 730, in run
    runner.run()
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/internal/conjecture/engine.py", line 435, in run
    self._run()
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/internal/conjecture/engine.py", line 771, in _run
    self.shrink_interesting_examples()
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/internal/conjecture/engine.py", line 813, in shrink_interesting_examples
    self.shrink(example, predicate)
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/internal/conjecture/engine.py", line 849, in shrink
    s.shrink()
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/internal/conjecture/engine.py", line 1274, in shrink
    self.greedy_shrink()
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/internal/conjecture/engine.py", line 1295, in greedy_shrink
    self.remove_discarded()
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/internal/conjecture/engine.py", line 1787, in remove_discarded
    self.__discarding_failed = not self.incorporate_new_buffer(attempt)
  File "/Users/chana/.virtualenvs/tempenv-598466573bc3/lib/python3.6/site-packages/hypothesis/internal/conjecture/engine.py", line 1221, in incorporate_new_buffer
    assert sort_key(buffer) < sort_key(self.shrink_target.buffer)
AssertionError

How did I find this? I was testing the API at work with https://github.com/olipratt/swagger-conformance, and on my second run I hit this internal assertion. Quite a big of digging later, this strategy popped out.

It’s incredibly fragile. I tried quite a few changes to simplify the example, all of which led it to finding the more boring assert False.

PS Having useful repr’s for strategies was really useful here – it allowed me to strip away a whole bunch of the Swagger-parsing code, and trim down to a pure Hypothesis bug.

[DRMacIver]

❤️ ❤️ ❤️ ❤️ ❤️

I've been aware that it was possible to trigger this assertion for a while, but nobody has been able to come up with a good repro for it (I've even seen it once myself and then immediately lost it and couldn't reproduce it).