The Rust safety invariants are, at heart, global properties. The central one is that mutable references are unique. Another way of saying that is: if you hold a mutable reference, then all other references held by all other objects in the system do not conflict with it (either because it is included in the "stacked borrow" or because it doesn't reference the data at all). That kind of property is ordinarily quite difficult to prove.
Rust does it though, by encoding these invariants in the types of functions. Most importantly, these types compose, meaning if you've got one function that respects these invariants calling into another, then the whole thing will also be sound. You can compile them separately and still be confident.
By contrast, achieving similar goals in the C family of languages does require a global analysis. The classic example is alias analysis. It's implemented in many compilers, tons of PhD ink has been spilled, but long story short it doesn't work. You get okay results sometimes on small programs[1], but as systems scale up, basically there always becomes a way for one pointer to alias another.
Thus, the claim I would make is the following: it will not be practical to retrofit Rust-style borrow checking onto an existing unsafe language, because the type system has to be rich enough to express the types of invariants required. The Rust type system has been carefully crafted to be powerful enough, at considerable cost: the complexity of the type system is one of the biggest complaints about the language, and slow compile times, one of its correlates, is another.
I would also claim that trying to scale up static analysis (based on alias analysis and other similar global analysis techniques), while perhaps somewhat helpful, is not going to give comparable results as Rust. In order to get anywhere near the level of confidence that all possible safety problems have been caught, the false positive rate would be unacceptably high.
I think this is one of the enduring achievements of Rust, and one likely to be carried forward in future programming language designs, but extremely unlikely to be successfully retrofitted to existing languages.
[1]: https://digitalcommons.calpoly.edu/cgi/viewcontent.cgi?artic...
By tracing ownership information through each component, and forbidding (or ignoring via `unsafe`) situations which cannot be traced in this way, the latter property can be decomposed and solved locally.
In other languages, like C++, we may still want this global property, but we can't break it down into local reasoning. Even if we decide on an approximate, conservative equivalent like 'all code passes STATIC ANALYSER X', getting local reasoning to work would require enough changes that it's arguable whether we're actually programming in the same language anymore. For example, we may need to add extra annotations to our code (which aren't present in existing codebases); we may need to extract extra information from sources (preventing the normal use of separately-compiled libraries); we (and our dependencies!) may need to avoid certain valid/legal patterns of code which the analyser can't handle; etc.
Writing the above, I'm reminded of trying to use the mypy type checker in Python!
That's exactly it. You want some set of machine-checkable constraints which add up to the desired global properties. Rust managed to do that. Attempts to fix this in C++ yield a set of slightly leaky constraints which sort of almost do that. Fixing this requires taking things out of the language, which is unpopular.
It's embarrassing that the code below still compiles with default gcc options, in either C or C++ mode. Yes, it's terrible C++. The compiler allows it.
#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[]) {
char buf[20] = "\0";
char* s = buf;
for (int i = 0; i<argc; i++)
{ s = strcat(buf, argv[i]); }
printf("%s\n",s);
}
Both D and Rusts compilers do it, and I'm uncertain whether Zig's does but it may too.
This slide deck is weird. I've taught 143 before. Where did this come from? Perhaps in really old stodgy terminology before there was any interprocedural anything people used the words this way? I really don't know any static analysis or compilers person who would consider "global analysis" to mean "intraprocedural analysis that considers more than one BB".
Also, I don't think they're alone in this terminology either... see here: https://www.csd.uwo.ca/~mmorenom/CS447/Lectures/CodeOptimiza...
Function boundaries do make things fundamentally more difficult than basic block boundaries, for a large number of reasons. You can no longer have single definitions of values and updates to those values are not global updates for the entire program. This is why you need stuff like context/object sensitivity for interprocedural analysis but it doesn't matter for local analysis. Graph structures also become way more chaotic, preventing the nice efficient lattice movement you see in classical local fixed point computation.
Like, static analysis and compilers is my job and none of my colleagues would use this term this way.
But clearly there is some material using it that way. Weird. I've been wrong before and I'll be wrong again in the future. So I'm happy to be wrong here. Clearly there are some situations where "global analysis" is used to describe whole-function analysis.
Regarding the difference for interprocedural analysis: I'm not entirely sure I follow it unfortunately. Let's say you can do everything within a function. Can't you just inline all of its callees (at whatever depth you want) and do your analysis/optimizations based off the result of that? Inlining itself is a rather trivial mechanical transformation, and after that everything is inside one function again, which you can already handle. The only real obstacle here seems to be recursion, but if you just treat that as any other opaque function call that you can't optimize across, you should otherwise get the rest of the way there, right? What am I missing?
In practice, these structural differences require new approaches. The field has done a really good job at intraprocedural analysis, solving a lot of really important problems many decades ago. How to do fixed point computation over SSAed CFGs is well understood, even when you've got heap relationships to think about. Interprocedural analysis still largely sucks. Even modern approaches like CFL-reachability for dataflow analysis produce a ton of garbage. This is one reason why I say it is just harder.
As you mention, recursion prevents you from inlining everything into one giant function. You do get "the rest of the way there" by inlining to some depth limit in the sense that inlining is a way of achieving context sensitive analysis (though it is generally not preferred). But you've still got big problems at the points of mutual recursion (either you need to widen badly or you need to actually do interprocedural analysis) and your program is also exponentially larger in pathological cases.