1. 9

A new academic paper describing stack graphs, which is the framework powering Precise Code Navigation at GitHub.


  2. 2

    For folks that prefer to learn by watching rather than reading, the Strange Loop talk on this was one of the finest examples of technical communication I’ve ever had the pleasure of seeing with my own eyes: https://www.thestrangeloop.com/2021/incremental-zero-config-code-nav-using-stack-graphs.html

    My hat’s off to you, @dcreager :)

    1. 2

      Wow, thank you for the kind words!

    2. 1

      Recently I learned that in Zig, there could be dynamic evaluations happening at build time which could change the outcome of the compilation result entirely.

      How would stack graphs handle those cases where there could be fuzzy hole in the graph? I.e. they are not exactly precise, but a narrowed set of possibilities.

      1. 4

        In general arbitrary compute happening at build time will be a problem with this kind of source-only analysis. We have some thoughts about how you could possibly simulate some of that computation in the stack graphs framework, but that at that point, it’s not clear that you’re gaining anything over just running the build and recording the results.

        One thing we also call out in the paper is that we can handle ambiguity an exploratory feature like Code Nav better than in an actual compiler or interpreter for the language. It’s okay for our rules to resolve a reference to a small number of possible definitions — it’s still helpful to the user even if we can’t nail it down to precisely one answer. That said, build-time compute is open-ended enough that we probably wouldn’t even be able to produce ambiguous answers!

      2. 1

        Are there still plans to publish stack graphs for general availability and local use?

        1. 1

          The stack-graphs crate is open source, is that what you mean? That repo implements the core algorithms, and is also where we’re putting the language-specific stack graph construction rules at the moment. (We had considered putting them into each language’s grammar repo, like we do for syntax highlighting and fuzzy tagging queries, but we decided that it would be asking too much of drive-by contributors to learn how to update stack graph rules in sync with any grammar changes that they submit.)

          1. 1

            Is the project intended to become a documented self-serve thing where people can write their own rules for their own languages that will presumably hook into clients in various editors?

            1. 1

              That’s still the intent, yes! I can’t say that there’s good narrative-style documentation yet, but we’re starting to put representative examples in the repo, showing what kinds of stack graph gadgets to use to model common language features.