search

BlockstreamResearch / rust-simplicity

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

occurs check: replace exponential-time algorithm with linear-time one #222

Closed apoelstra closed 2 months ago

apoelstra commented 2 months ago

Builds on #221, because the changes to the OccursCheck error variant would conflict with it if I PR'd it separately. But this is conceptually independent of #221.

Our old occurs-check loop would use the pre-order iterator from dag.rs with the NoSharing adaptor. This would iterate over the full explicit type, which may have exponential size in the program length. The correct algorithm notices when it is done checking a type bound and all its children, and does not check that bound again.

I wasn't able to produce a test vector showing the exponential-time behavior of the old algorithm, but I am hitting this issue in a fuzzing project I'm working on locally, and I think it's clear from the diff what the issue is and how this change fixes it.

uncomputable commented 2 months ago

Superseded by #221 ?

apoelstra commented 2 months ago

No, but it needs to be rebased on #221.

apoelstra commented 2 months ago

Oh, no, I guess I accidentally(?) pulled this commit into #221. It is superseded.