Migrate the Hypothesis engine from Python to Rust

[Liam-DeVoe]

This epic-style issue tracks our work towards migrating the core Hypothesis engine from Python to Rust.

We expect this to both bring better performance, and allow us to expose Hypothesis as a shared backend for PBT in other languages, for example for use by Hegel.

This change should not otherwise be user-visible in any way. We are treating this as a minor, not a major, version bump.

Background

As a small bit of background: we have long toyed with the idea of porting the Hypothesis engine to Rust. Some things have changed since then: the Rust<->Python ecosystem (e.g.) has matured, and Hegel, which @DRMacIver and I work on, would benefit substantially from native bindings into Hypothesis, so we can bring the power of Hypothesis and PBT to every language. And of course, no Python user of Hypothesis will complain about a speedup!

We think now is the right time to complete a migration of the core of Hypothesis into Rust. Many parts of Hypothesis—for example, those that interface with the user—will remain in Python.

Roadmap

• Ship a version of Hypothesis with a trivial amount of Rust code.
  • This lets us get the build infrastructure and deployment story right, before moving on to any of the actual work.
• ??? (will fill in as we get a more clear idea of the work to be done)

[Stranger6667]

FWIW, some time ago I ported Unicode code points intervals logic to Rust here. In another private repo there were even PyO3 bindings which passed all Hypothesis repo-level tests with unicode-intervals monkeypatched instead of the current impl. If any of it would be useful, feel free to take & adjust the impl and let me know if it makes sense to share those PyO3 bindings (though they could be somewhat stale).

UPDATE: I noticed that the unicode-intervals crate does not have any mention of Hypothesis (thought it should have it) - many parts of the implementation were mostly 1:1 ports initially with some performance-motivated changes later on

[DRMacIver]

BTW I think step 2 of the roadmap should definitely be "add a hegel backend and see how much of the test suite passes under it".

hegel native is coming along pretty well. It's definitely not yet at a level where I think it's a drop-in replacement for the current Hypothesis backend, but I'd love to find out all the ways in which the Hypothesis test suite thinks it's not, and I think for many Hypothesis workloads it will immediately give people a huge speedup.

[DRMacIver]

I'm agnostic in this proposal as to whether the long-term future is that the main Hypothesis backend is literally just a hegel client, but I think it's pretty plausible that that's the way to go. Short term I don't think we'll be at the natural swapover point to that any time soon, but it's a good way to start commonising the code between them.

(Also, I didn't know about unicode-intervals. Neat! There's some code in hegel-rust that I should definitely look into replacing with a dependency on that)