BlockstreamResearch / rust-simplicity

Creative Commons Zero v1.0 Universal
58 stars 12 forks source link

[mega pr, do not merge] types: rewrite inference API to use a slab allocator for type bounds #228

Closed apoelstra closed 2 months ago

apoelstra commented 2 months ago

Our existing type inference engine assumes a "global" set of type bounds, which has two bad consequences: one is that if you are constructing multiple programs, there is no way to "firewall" their type bounds so that you cannot accidentally combine type variables from one program with type variables from another. You just need to be careful. The other consequence is that if you construct infinitely sized types, which are represented as a reference cycle, the existing inference engine will leak memory.

A third issue, though I am unsure whether it leads to actual bugs, is that the type inference engine can only lock data at the granularity of individual type bounds, meaning that multi-step parts of type inference are not done atomically, and if you try to construct a program in a multithreaded context, it is possible that strange/unexpected things will happen.

To avoid this, it is better that each program under construction has an independent "type inference context" which holds a slab allocator. When the context is dropped, which happens when the initial constructed context and all the program nodes that reference it are dropped, it deallocates all the type bounds in one shot, rather than chasing Arcs and failing to notice cycles.

This is a 2000-line diff but the vast majority of the changes are "API-only" stuff where I was moving types around and threading new parameters through dozens or hundreds of call sites. I did my best to break everything up into commits such that the big-diff commits don't do much of anything and the real changes happen in the small-diff ones to make review easier.

Builds on #227.

This does not fix #226 although it sets the stage for "checkpointing" the type inference context, which should allow a reasonably-efficient way to undo changes when things go wrong.

apoelstra commented 2 months ago

I will probably break this into more than 2 PRs, but I'll leave this open for now as the "source of truth" for the whole project.