Search code examples
rustcompilation

Why is it impossible for compiler to detect memory leak specifically caused by circular reference?


There are certain cases that we leak memory in purpose for some reason. In these cases we explicitly call something like Box::leak() or mem::foget(). Also, sometimes it is possible that adding items to collections without removing is the purpose of program. However, memory leaks caused by other reasons such as misuse of strong reference over weak reference is hardly (I would say impossible) to be in purpose. Why wouldn't the compiler keep track of every single smart pointer with reference count, and reject to compile if any of their count is not 0 at the exit of entire program? That is, a program will only compile if all Arc and Rc have 0 reference count after drop stage of main function. If above is impossible to implement, I hope to know why it isn't.


Solution

  • To know if the program will even terminate, we need to solve the halting problem. Unfortunately, Alan Turing proved that there is no general solution. That alone precludes any analysis of this kind.

    More generally, the compiler doesn't know what will happen at runtime. It might depend on various inputs, such as command line arguments, environment variables, the state of the filesystem (what directories/files exist and what they contain), the results of network operations such as fetching information from a remote API or database, and so on. Collectively, we can call all of this information external to the program its "environment." The program's environment can influence what the program will do, and memory leaks might happen in some environments but not others.

    Further, in Rust, all running threads will terminate automatically when main() returns, and this termination is forced; any values owned by the threads will not have their destructors run, so any Arcs they hold won't get a chance to be properly cleaned up. This means any program using threads could very easily cause leak checking to generate false positives.

    Static analysis of this kind simply isn't feasible.

    In fact, one of the reasons why we even have reference-counted types is to handle situations where the compiler can't prove the safety of the program. These types fundamentally hide the "true" lifetime of the contained value from the compiler. Asking the compiler to figure out the lifetime of values stored within a type that hides lifetimes from the compiler is a contradiction.