The most common types of software bugs are memory management bugs. And very often they lead to the most tragic consequences. There are many types of memory bugs, but the only ones that matter now are memory leaks due to circular references, when two or more objects directly or indirectly refer to each other, causing the RAM available to the application to gradually decrease because it cannot be freed.

Memory leaks due to circular references are the most difficult to analyze, while all other types have been successfully solved for a long time. All other memory bugs can be solved at the programming language level (for example, with garbage collectors, borrow checking or library templates), but the problem of memory leaks due to circular references remains unsolved to this day.

But it seems to me that there is a very simple way to solve the problem of memory leaks due to circular references in a program, which can be implemented in almost any typed programming language, of course, if you do not use the all-permissive keyword unsafe for Rust or std::reinterpret_cast in the case of C++.

What is the original problem?

To understand why the problem of circular references has not yet been solved, it is necessary to explain where this problem came from in the first place.

If we talk about serious programming languages ​​that are intended for developing commercial applications, then the mandatory and unconditional requirement for such languages ​​will be the ability to implement any of the existing algorithms, invented and implemented earlier.

Therefore, all new programming languages ​​are forced to implement such basic algorithms in one way or another, which will be included in its standard library, and one of such basic algorithms is linked list. And the implementation of a linked list is a mandatory and necessary condition for any programming language.

The peculiarity of a linked list is that each of its elements requires at least one link to exactly the same element. This is where the need for recursive (cyclic) links arises, since the presence of a link to an element of the same type in an element automatically creates the possibility of a cyclic link, and as a result — memory leaks.

And since linked lists can be formatted dynamically (at runtime), it is generally impossible to analyze the logic of dependency occurrence and prove the absence of cyclic references using a static code analyzer during program compilation.

By the way, it is precisely because of the impossibility of statically analyzing the program execution graph and guaranteeing the absence of cyclic references that the Rust developers declared memory leaks due to cyclic references safe, stating that memory leaks do not affect memory safety.

How to statically prove the absence of cyclic references in a program?

If we recall the history of the theory of algorithms, the concept of recursive references began to be used a very, very long time ago, back in those distant times when pointers were just ordinary addresses in memory. However, since then, the theory and practice of programming languages ​​have advanced very far. Many new concepts have appeared that successfully automate the solution of many routine tasks that initially had to be programmed completely manually (which is why many errors occur).

For example, the concept of RAII was invented to automatically free resources, and strong and weak references were invented and successfully used to solve the problem of circular references.

Wait, but if the problem of circular references is solved by using strong and weak pointers, then why does this problem still exist in programming languages?

After all, the problem of memory leaks due to circular references can be very easily solved by disallowing the definition of strong recursive references in the compiler at the level of data types.

Yes, in this case, you can’t make a classic linked list. A linked list in the new paradigm will require a separate container for storing list elements using strong references, since the list elements themselves will be prohibited from having strong references to their own data type. Of course, this implementation of a list will require a little more memory, but it will basically eliminate the possibility of creating circular dependencies at the data type level!

But the most important thing is that checking for cyclic dependencies for data types is very easy to do statically when compiling the source code of the application. After all, to do this, you need to analyze the execution graph of the program code for the appearance of cyclic references, if they are prohibited by the compiler at the type level!

And strong and weak pointers in combination with the RAII concept make garbage collectors completely unnecessary (and most likely, it will be possible to refuse borrowing checks).

I am a little afraid of writing such obvious things. Perhaps in the very idea of ​​​​prohibiting strong recursive references at the data type level, I simply did not take into account some critical point, because for some reason this has not yet been done in any programming language?

After all, such a static analyzer of cyclic dependencies for analyzing the source code of a program, for example for the C++ language, is made in less than an evening and completely eliminates the problems of possible cyclic dependencies and associated memory leaks.