Tree Borrows

As I understand it the borrow checker only has false negatives but no false positives, correct?

Maybe a dumb question but couldn't you just run multiple implementations in parallel threads and whichever finishes first with a positive result wins?

This presumes that checking composes which may not if you have orthogonal checker implementations. You might end up risking accepting an invalid program because part of it is valid under one checker, part under another, but the combination isn't actually valid. But maybe that's not actually possible in practice.

Borrow checking is function-local, so if the opsem model is the same and you run the different checkers per-function, there is no such risk.

I’ll take your word for that although it feels like there may be other cases. Even still there is the subtle problem that bugs in the proof checkers now result in O(n^m) safety issues because an incorrectly accepted program is more likely to get through 1 of the borrow checkers (similar to how in a distributed system adding single points of failure results in exponentially decreasing reliability).

> As I understand it the borrow checker only has false negatives but no false positives, correct?

The borrow checker is supposed to be a sound static analysis, yes. I think Ralf Jung's comment at https://news.ycombinator.com/item?id=44511416 says soundness hasn't been proved relative to tree borrows yet.

> Maybe a dumb question but couldn't you just run multiple implementations in parallel threads and whichever finishes first with a positive result wins?

IIUC when you're compiling reasonably-sized programs you're already using all the cores, so parallelizing here doesn't seem like it's going to net you much gain, especially if it means you're doing a lot of extra work.

Thanks, didn't see that!

> when you're compiling reasonably-sized programs you're already using all the cores

Only on full rebuilds. I would assume most build jobs with a human in the loop only compile a handful of crates at once.

In fact as CPUs get more and more parallel we'll cross the threshold where thread count surpasses work items more often and then will come the time to get creative ;)