OP author here. I also gave a talk about this at Strange Loop back in October if folks want to watch/listen instead of read: https://dcreager.net/talks/2021-strange-loop/
It's not just because I was a chef! Using nouns, adjectives and verbs from (familiar) concrete hierarchical analogies makes technical writing much more accessible. It reduces cognitive load by implying more about the structure of the relationship than variables like "intVar" and functions like "printVar" tied together in entirely contrived, abstract ways. In particular, newer developers, or ones unfamiliar with your language paradigms will benefit heartily.
I implore my fellow developers to follow suit.
This is a really good insight. I can remember back to my university days, a teacher used a cooking analogy to explain something that was really hard to understand- since then, the concept stuck.
When python resolves 'import' statements, it looks for the modules based on the PYTHONPATH. Although not done that often, it is possible to modify the PYTHONPATH at runtime, changing what an imported symbol will resolve to. How do you handle situations like that?
Just from a hypothetical stand point, someone could take advantage of this to make it seem like the library is linking to a safe implementation of a function such that when using this feature people are directed to the safe implementation. Then at runtime without the user knowing, they could dynamically change the PYTHONPATH so a malicious version of the function is loaded.
We do eventually want to support cross-repository use cases, and there, the answer boils down to needing to find the set of dependencies in which to do the search. One we have that, it's no different than an in-repo case — we look for any file in any of the repos (yours and your dependencies) that could provide the symbol that we're currently looking for.
So, short version, we'd be aiming for a solution where we'd be able to show you both the “good” and “bad” definitions, and let you the user decide how to use that information.
Even with that flexibility, there are still some things that just weren't possible because of how configurable python is at runtime. For example, someone could write a factory style class that dynamically creates python object instances based on a passed in string that represents the class the object will be of. Then they could pass user input into this factory making the created objects completely dependent on runtime input.
I would wage 99% of python written doesn't use these kinds of runtime abilities, and it probably isn't a great practice to use them in general from a maintainability point of view but they do exist. My solution to this is that if you are sophisticated enough to be using these features then you should be able to understand why my tool can't capture that information from the AST.
Not sure if that solution would work for what you are working on, but I figured I'd let you know about my experience because it can get gnarly quickly once you start thinking about all the things that are possible in python.
For production, is there a good database system that can index this graph structure?
for incremental update, how do you prune deprecated part of the graph (for example, removed/renamed files/functions?)
and for this example
(function_definition name: (identifier) @name) @function {
node @function.def
attr (@function.def) kind = "definition"
attr (@function.def) symbol = @name
edge @function.containing_scope -> @function.def
how can it guarantee the python shadowing rule? it doesn't seem to encode any order preference. does the code traverse the source file in the reverse order basically?
And, probably not closely related to stack graph, but about using tree-sitter for c/c++ understanding, how to handle the preprocessor?
because the c preprocessor can make the code look like a completely different language and mess up the parser.
And how to prune and simplify CST to AST at scale (supporting many languages)?
For awhile, we were storing this in a (very large) MySQL database, sharded with Vitess. The sharding behavior worked great (since repo ID gives you a nice sharding key), but we found that it wasn't elastic enough for our needs, since we quickly filled up the available capacity of the machines that we had reserved.
Since then we've switched over to storing this data in Azure Blob Storage, basically using it as a glorified key/value store. We had to write custom logic for deciding how to structure our data so that we can efficiently write it at index time and read it at query time, but so far it's been working quite nicely!
> for incremental update, how do you prune deprecated part of the graph
Short version is that we're storing everything on a per-file basis. So whenever a file is changed, we generate a new stack graph snippet for that file. There might be lots of content in that stack graph that is identical to the stack graph of the previous version of the file, but we don't try to do any structural sharing more fine-grained than the file.
Right now we aren't going in any pruning old files that aren't being touched by any active queries, but we could. Or move it to a colder storage tier in Blob Storage, something like that. At least for now, the marginal costs of storing the data for longer aren't our cost bottleneck.
As a concrete example, Go imports (at least for module-enabled code) is version-locked and the HEAD of the referenced code may no longer be representative of the code that would actually end up being compiled.
On the other hand, just having an easy navigational tool to get to roughly the right place is a very good help.
That snippet of graph DSL does not show the precedences being applied, but if you look at the diagram a bit earlier in the post, you'll see that some of edges do have precedence values applied. In the graph DSL, that would appear as an additional statement in the stanza:
attr (@function.containing_scope -> @function.def) precedence = 1Ha yeah that's a good question. Some uses of the preprocessor won't be problematic — it would require deep token mangling, for instance, to really start to cause a problem. You can treat more basic `#ifdef` style conditional compilation as parsing/analyzing both sides and showing both as potential definitions. (And from there you could extend it further to try to identify (or define) "profiles" that have different preprocessor symbols defined, and use that to actually prune some of the results.)
I'm thinking maybe stack graph can be used to understand the preprocessor. finding the original toggle/condition that turns on/off a #ifdef block.
I heard a simple c++ hello world contains 5000 #defines introduced by standard libs. if stack graph can improve exhaustive search somehow, that would be awesome.
We're not doing any pruning or CST→AST translation, we just operate directly on the CST. With the new graph DSL you should be able to implement something like that, since an AST is a tree, and a tree is one shape of graph that you could create. For our purposes, that isn't a meaningfully useful step, since we can just as easily generate the stack graph structures that we need directly from the CST we get from the tree-sitter grammar.
For LSP, the short version is that running separate sidecar services in production for every language that we want to support is a complete non-starter. That would completely eat up my team's time budget handling operational duties.
LSIF is a great technology that lets you run LSP servers in a “batch” mode. But we really need our analysis to be incremental, where we can reuse results for unchanged files when new commits come in. Language servers tend to do monolithic analyses, where every file needs to be reanalyzed whenever any new commit comes in. If you want to analyze your dependencies, as well, that exacerbates the problem. LSIF (the data format) has recently grown the ability to produce incremental data, but that requires language servers to work in an incremental mode as well. Very few (if any?) do, and because language servers tend to piggy-back on existing compiler technology (which is also not typically incremental), it will be a heavy lift to get incrementality into the LSP/LSIF world.
Whereas stack graphs have incrementality out of the box. (This was the primary thing that we added to “scope graphs”, the academic framework that stack graphs are built on.) It's the core algorithm (which is implemented once for all languages) where the incrementality happens. The only language-specific parts are figuring out which graph structures you need to create to mimic the name binding rules of your language.
We extended scope graphs to have the symbol stack (described in OP) and also a “scope stack”, which allows us to support the more advanced examples that I alluded to at the end. So we chose the name “stack graphs” because it was “scope graphs but using stacks”.
No need for precise answers, just wondering which ones we're likely to see next after Python :)
Also, I'm looking at the list of supported languages here[1]. Maybe you're not the right person to ask, but are there any plans to add support for one of the lower level / systems programming languages like C, C++, or Rust, etc?
Finally, thank you so much for you and your teams hard work. This feature is _incredibly_ helpful, especially in Python!
[1]: https://docs.github.com/en/repositories/working-with-files/u...
We do have a couple of other languages in the pipeline that my team has been working on, both in terms of writing stack graph rules to get precise support, and also to write "fuzzy" tagging rules to get search-based support. And we definitely do plan to include lower level languages like the ones you mentioned.
Lastly, one major reason that we're doing all of this in open-source projects is that we want to ensure that language communities can self-serve support for their languages, should they wish to. That will be especially useful for the long tail of languages that my team will honestly never be able to get to ourselves. We have some work to do to get the documentation written to properly support self-serve stack graph rules, but it's definitely a goal that we're aiming for.
How do you handle statically typed languages where type inference (which may rely on types from other imported files) and overloading deeply interacts with name resolution? I can't see any easy way to model than in terms of a simple "parse a file at a time" model like tree sitter.