[evmar]

I 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/...

[dcreager]

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/

[3] https://news.ycombinator.com/item?id=29500602

[4] https://news.ycombinator.com/item?id=29501824

[evmar]

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.

[dmoy]

Yup, it is probably fair to say that C++ accounts for like 50% of the complexity of Kythe at Google. Or certainly it feels like it.

And it is also worth noting that Kythe goes a bit deeper than what LSP can accomplish. In particular Kythe is built around a sort of two-layer graph, where it separates the physical code/line representation from a more abstract semantic graph. This allows us to accomplish some things that are very difficult to do in LSP.

Finally, Kythe at least internally has a big reliance on a unified build system (Blaze, or Bazel). It becomes rapidly more difficult to do when you have to hook in N different build systems up front, which is why search-based references are so appealing. Build integration is hard.

[nerdponx]

Has Tree Sitter been useful to projects like this? Does it have promise to be useful in the future? It seems to be gaining a lot of adoption among Neovim users and plugin developers, but not really anywhere else. I'm curious if that's because of lack of familiarity, or because it's technically deficient somehow.

[dcreager]

In short, yes, very much so! Tree-sitter is what we're using under the covers to parse all of the languages that we support. The ctags-like symbol extraction described in the paper comes straight from tree-sitter, too. [1]

[1] https://tree-sitter.github.io/tree-sitter/code-navigation-sy...