Description
I think we can make the process of checking borrows more efficient. Right now, we use a dataflow computation to compute the "borrows in scope" at each point. Then we walk over the MIR. At each point, whenever we access a path P1, we execute over the borrows in scope and look for any which conflict with P1. If we find any, we report an error.
I think what we should do instead is this: walk over all the borrows. For each borrow, do a DFS from the point of the borrow. Stop the DFS when we either (a) exit the borrow region or (b) detect that the path which was borrowed was overwritten. (We already do a very similar computation.) During that DFS, we look at the paths that are accessed by each statement we traverse, and check if they conflict with the borrow. (This will require us to efficiently index the paths that are accessed by a given location.)
This is a non-trivial amount of refactoring but I think it will be a win. We're already doing the DFS as part of the precompute_borrows_out_of_scope routine -- the only difference is that now we'll be checking the paths accessed by each statement as we go. But we can make that efficient by using a simple hashing scheme like the one described in #53159.
In exchange, we get to avoid doing an extra dataflow computation. This means one less dataflow to do and also one less thing to update.