5 ms·

I'm not sure what you mean by "global analysis," but Rust's borrow checker doesn't do any analysis that I'd consider "global."

by creata 5y ago

WalterBright 5y ago
D's ownership/borrowing system does data flow analysis within functions, i.e. it's intra-function. Inter-function (global) is handled via the function signature.
dataflow 5y ago
"Global analysis" is specific compiler optimization terminology. It refers to analysis across so-called "basic blocks" (also compiler terminology). See here: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/15/Slides15.pdf#page=46 https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/l...
- UncleMeat 5y ago
  That's not true. Global analysis is a synonym for interprocedural analysis, which crosses function boundaries. An intraprocedural analysis that crosses many basic blocks is still "local" rather than "global". 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".
  - dataflow 5y ago
    It's funny because I also remembered it as cross-function analysis, but when I went back to grab a link I saw this and thought maybe I'm mistaken somewhere, so I just used this definition. Oh well. Main thing I was just trying to convey was that it's technical terminology.
    - UncleMeat 5y ago
      Yeah that's so bizarre. Is this Alex's slide deck? Did a TA write it? Could it be tremendously old? Weird.
      - dataflow 5y ago
        I don't know if it's actually wrong though, given that a procedure is just a block of code with one entry point (and let's say one return, for the sake of discussion). I'd have to jog my memory, but I'm thinking: if you can already optimize inside a function (but outside basic blocks), then I don't recall what would be so drastically different across functions. The fundamentally hard part does seem to be going from one basic block to multiple. I might be forgetting something though... do you recall? Also, I don't think they're alone in this terminology either... see here: https://www.csd.uwo.ca/~mmorenom/CS447/Lectures/CodeOptimization.html/node5.html https://www.csd.uwo.ca/~mmorenom/CS447/Lectures/CodeOptimiza...
        UncleMeat 5y ago
        The only explanation I can think of is that this is old terminology that has stuck around in course material based off older textbooks that aren't bothering with any sort of interprocedural anything. 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.
        dataflow 5y ago
gavinray 5y ago
Data-flow analysis is what I assume the author meant. Fancy word for "reasoning about behavior at a level higher than just a syntax node" (usually within a function or module, possibly within an entire program though) Both D and Rusts compilers do it, and I'm uncertain whether Zig's does but it may too.
oconnor663 5y ago
I think the idea is more like "the entire program is covered by lifetime analysis / borrow checking, so that nothing gets missed." Something like that?
raphlinus 5y ago
I think there's something important here, potentially obscured by imprecise terminology. 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?article=3206&context=theses https://digitalcommons.calpoly.edu/cgi/viewcontent.cgi?artic...
chriswarbo 5y ago
The point of the borrow checker is to replace the global property 'all memory has an owner' with the (approximate, conservative) equivalent 'all code passes the borrow checker'. 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!
- Animats 5y ago
  In other languages, like C++, we may still want this global property, but we can't break it down into local reasoning. 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); } (Even Microsoft has "strcat" deprecated by default.)

I'm not sure what you mean by "global analysis," but Rust's borrow checker doesn't do any analysis that I'd consider "global."

by creata 5y ago

I'm not sure what you mean by "global analysis," but Rust's borrow checker doesn't do any analysis that I'd consider "global."

WalterBright 5y ago

D's ownership/borrowing system does data flow analysis within functions, i.e. it's intra-function. Inter-function (global) is handled via the function signature.

dataflow 5y ago

"Global analysis" is specific compiler optimization terminology. It refers to analysis across so-called "basic blocks" (also compiler terminology). See here: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/15/Slides15.pdf#page=46 https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/l...

UncleMeat 5y ago
That's not true. Global analysis is a synonym for interprocedural analysis, which crosses function boundaries. An intraprocedural analysis that crosses many basic blocks is still "local" rather than "global". 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".
- dataflow 5y ago
  It's funny because I also remembered it as cross-function analysis, but when I went back to grab a link I saw this and thought maybe I'm mistaken somewhere, so I just used this definition. Oh well. Main thing I was just trying to convey was that it's technical terminology.
  - UncleMeat 5y ago
    Yeah that's so bizarre. Is this Alex's slide deck? Did a TA write it? Could it be tremendously old? Weird.
    - dataflow 5y ago
      I don't know if it's actually wrong though, given that a procedure is just a block of code with one entry point (and let's say one return, for the sake of discussion). I'd have to jog my memory, but I'm thinking: if you can already optimize inside a function (but outside basic blocks), then I don't recall what would be so drastically different across functions. The fundamentally hard part does seem to be going from one basic block to multiple. I might be forgetting something though... do you recall? Also, I don't think they're alone in this terminology either... see here: https://www.csd.uwo.ca/~mmorenom/CS447/Lectures/CodeOptimization.html/node5.html https://www.csd.uwo.ca/~mmorenom/CS447/Lectures/CodeOptimiza...
      - UncleMeat 5y ago
        The only explanation I can think of is that this is old terminology that has stuck around in course material based off older textbooks that aren't bothering with any sort of interprocedural anything. 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.
        dataflow 5y ago

gavinray 5y ago

Data-flow analysis is what I assume the author meant. Fancy word for "reasoning about behavior at a level higher than just a syntax node" (usually within a function or module, possibly within an entire program though) Both D and Rusts compilers do it, and I'm uncertain whether Zig's does but it may too.

oconnor663 5y ago

I think the idea is more like "the entire program is covered by lifetime analysis / borrow checking, so that nothing gets missed." Something like that?

raphlinus 5y ago

I think there's something important here, potentially obscured by imprecise terminology. 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?article=3206&context=theses https://digitalcommons.calpoly.edu/cgi/viewcontent.cgi?artic...

chriswarbo 5y ago

The point of the borrow checker is to replace the global property 'all memory has an owner' with the (approximate, conservative) equivalent 'all code passes the borrow checker'. 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!

Animats 5y ago
In other languages, like C++, we may still want this global property, but we can't break it down into local reasoning. 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); } (Even Microsoft has "strcat" deprecated by default.)