Static analysis at GitHub
cacm.acm.org
Static analysis at GitHub
1–10 of 21 posts
Re: Static analysis at GitHub
#2[deleted]
Re: Static analysis at GitHub
#3figure 2 is repeated for some reason?
Re: Static analysis at GitHub
#4This is Big Code
Re: Static analysis at GitHub
#5figure 2 is repeated for some reason?
That's odd. The error was not present in the original publication of this article in ACM's Queue magazine: https://queue.acm.org/detail.cfm?id=3487022
Re: Static analysis at GitHub
#6This article more about parsing at scale than static analysis at scale.
Re: Static analysis at GitHub
#7I contributed to a similar system used within Google (partially open source at kythe.io), that took the very different approach of integrating with the language-native toolchain for each language.
As this article describes, doing this requires per-language integrations and also effectively being able to "run the build" for any given code (because e.g. the C++ header search path can vary on a per-source-file basis), which is untenable for a codebase as large and varied as GitHub's. However, if you can make it work, you get the benefit of having the compiler's understanding of the semantics of the code, which is especially finicky in complex languages like C++ or, say, Rust.
For example, if you look at this[1] method call it refers to a symbol generated by a chain of macros, but the browser is still able to point you at the definition of it.
It's an interesting tradeoff to make: the GitHub approach likely doesn't handle corner cases like the above but it makes up for it in broad applicability and performance. I recall an IDE developer once telling me they made a similar tradeoff in code completion, in that it's better DX to pop up completions quickly even if they're "only" 99% correct.
(To be clear, I absolutely think the approach taken in the article was the right one for the domain they're working in, I was just contrasting it against my experience in a similar problem where we took a very different approach.)
[1] https://source.chromium.org/chromium/chromium/src/+/main:v8/...
Re: Static analysis at GitHub
#8I contributed to a similar system used within Google (partially open source at kythe.io), that took the very different approach of integrating with the language-native toolchain for each language. As this article describes, doing this requires per-language integrations and also effectively being able to "run the build" for any given code (because e.g. the C++ header search path can vary on a per-source-file basis), w…
Note that this article describes our implementation of “search-based” or “ctags-like” Code Navigation, which definitely has the imprecision that you describe. We've also been working over the previous ~year on a framework called Stack Graphs [1,2,3], which lets us tackle “precise” Code Navigation while still having the zero-config and incremental aspects that are described in the paper.
The build-based approach that you describe is also used by the Language Server Protocol (LSP) ecosystem. You've summarized the tradeoffs quite well! I've described a bit more about why we decided against a build-based/LSP approach here [4]. One of the biggest deciding factors is that at our scale, incremental processing is an absolute necessity, not a nice-to-have.
[1] https://github.blog/2021-12-09-introducing-stack-graphs/
[2] https://dcreager.net/talks/2021-strange-loop/
Re: Static analysis at GitHub
#9This article more about parsing at scale than static analysis at scale.
Parsing is definitely a big part of it, and it's a fair point that for search-based Code Navigation, we don't have to do any real heavy lifting on the analysis side. That said, I think the article describes our non-functional requirements well (zero-config, incremental, language-agnostic). It's those non-functional requirements which are most important for the “at scale” part. I'd go so far as to suggest that any static analysis implementation that can't meet those requirements would be nigh impossible for us to roll out across the entire GitHub corpus.
Re: Static analysis at GitHub
#10I contributed to a similar system used within Google (partially open source at kythe.io), that took the very different approach of integrating with the language-native toolchain for each language. As this article describes, doing this requires per-language integrations and also effectively being able to "run the build" for any given code (because e.g. the C++ header search path can vary on a per-source-file basis), w…
Note that this article describes our implementation of “search-based” or “ctags-like” Code Navigation, which definitely has the imprecision that you describe. We've also been working over the previous ~year on a framework called Stack Graphs [1,2,3], which lets us tackle “precise” Code Navigation while still having the zero-config and incremental aspects that are described in the paper. The build-based approach that…
I read about stack graphs before, it sounds interesting!
I think they help, but ultimately I expect you need a compiler solve the absolute madness of the totality of C++. For example I think getting argument-dependent lookup right in the presence of 'auto' requires type information? And there are other categories of things (like header search paths) where I think you are forced to involve the build system too.