4 ms·

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-str

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/ https://dcreager.net/talks/2021-strange-loop/

billconan 5y ago
Thank you very much for this and for open sourcing it! 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)?
- dcreager 5y ago
  > For production, is there a good database system that can index this graph structure? 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.
  - randomswede 5y ago
    For at least some languages, it might even be important to have access to older versions of a file. 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.
    - dcreager 5y ago
      Right now code nav on GitHub only works within a repository, and so every link you follow keeps you within the commit that you’re already viewing. As we move to cross-repo code nav, you’re right that it will be difficult to determine the right commit to take you to when following a cross-repo link.
- dcreager 5y ago
  > 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? 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 = 1
- dcreager 5y ago
  > And, probably not closely related to stack graph, but about using tree-sitter for c/c++ understanding, how to handle the preprocessor? Ha 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.)
  - billconan 5y ago
    Thank you very much for the answers! This is a great work! 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.
- dcreager 5y ago
  > And how to prune and simplify CST to AST at scale (supporting many languages)? 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.
dahart 5y ago
This is way cool!! I don’t have any deep questions yet, but to start I’m a bit curious about some very minor things like the name and description. I’m curious why “stack graph” as opposed to “call graph” or “callstack graph” or something like that, I’m guessing you do have some thoughts there. Also curious about the way you described it, the process overall certainly sounds a lot like parsing, compiling, and linking at the end, but you haven’t really used that analogy. I guess I’m just wondering if you’re framing the name and description carefully and if there are specific reasons you’d be willing to discuss.
- dcreager 5y ago
  Great questions! The framework is based on some great existing academic work from Eelco Visser's group at TU Delft. Their framework is called “scope graphs”: https://pl.ewi.tudelft.nl/research/projects/scope-graphs/ https://pl.ewi.tudelft.nl/research/projects/scope-graphs/ 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”.
ZeroCool2u 5y ago
Just out of curiosity, what's the timeline look like for adding precise code navigation to other supported languages and what languages do you think will get support first? 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/using-files/navigating-code-on-github#about-navigating-code-on-github https://docs.github.com/en/repositories/working-with-files/u...
- dcreager 5y ago
  It's not “easy”, but we've found that because it's based on a declarative DSL it's less effort than you might expect. And we're finding that there are common patterns that you use in your graph construction rules, because there are many aspects of name binding that end up working the same way in different languages. So, hand-wavily (not out of secrecy but because of not having rigorous data yet), we're finding that it's O(months) to get a new language out the door. 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.
  - ZeroCool2u 5y ago
    Got it, that's really helpful in terms of estimating the work involved. Thanks for taking the time to answer all these questions and congrats again on the release!
one_off_comment 5y ago
For people like me who don't have time to watch the talk, what's the answer to the question posed on the blog post? "Why aren’t we using the Language Server Protocol (LSP) or Language Server Index Format (LSIF)?"
- dcreager 5y ago
  I go into some amount of detail in a talk I gave at last year's FOSDEM: https://dcreager.net/talks/2020-fosdem/ https://dcreager.net/talks/2020-fosdem/ 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.
dsanchez97 5y ago
I haven't had time to watch the full talk yet, so sorry if this is answered there. 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.
- dcreager 5y ago
  Ooh that's a good one. Right now, our lookups are only within the single repository. And so if you had two files that _could_ provide the same (fully qualified) symbol, we aren't doing any PYTHONPATH analysis to determine which one it is. We'll show you both. 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.
  - dsanchez97 5y ago
    I have been doing some stuff where I analyze python code via the AST to try to figure out symbol reference so it was top of mind when I read the article. My tool works at runtime by importing the users code as module, which means all the symbols are evaluated by the python interpreter and then I can inspect the loaded module to determine the references. This is all part of a larger framework that has lifecycle rules for how/when it will load user defined code, which allows me some flexibility and 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.
chefandy 5y ago
As an aside to the technical conversation— I appreciate the use of cooking as an analogy in your code samples in the posted article. 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.
- dcreager 5y ago
  Haha also I like food :-)
- geoduck14 5y ago
  >Using nouns, adjectives and verbs from (familiar) concrete hierarchical analogies makes technical writing much more accessible. 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.
munificent 5y ago
Apologies if you answered this in the talk, but from the slides it doesn't seem you did. 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.
- dcreager 5y ago
  This relies on “scope stacks”, which are another piece that I didn’t really have a chance to discuss in either the blog post or Strange Loop talk. In brief, they allow you to “package up” context from one part of a file and “send it over” to another part of a (possibly different) file. We use that to model the (types of the) actual parameters passed into a function call or generic type instantiation, for instance. Scope stacks are essential for both of the more advanced examples I mention at the end of the post.
  - dcreager 5y ago
    This early (and rough around the edges) design doc goes into more detail about scope stacks, and works through a couple of examples that rely on them: https://github.github.io/stack-graph-docs/ https://github.github.io/stack-graph-docs/
    - munificent 5y ago
      Thank you! I'll dig through this when I get the time.

billconan 5y ago

Thank you very much for this and for open sourcing it! 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)?

dcreager 5y ago
> For production, is there a good database system that can index this graph structure? 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.
- randomswede 5y ago
  For at least some languages, it might even be important to have access to older versions of a file. 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.
  - dcreager 5y ago
    Right now code nav on GitHub only works within a repository, and so every link you follow keeps you within the commit that you’re already viewing. As we move to cross-repo code nav, you’re right that it will be difficult to determine the right commit to take you to when following a cross-repo link.
dcreager 5y ago
> 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? 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 = 1
dcreager 5y ago
> And, probably not closely related to stack graph, but about using tree-sitter for c/c++ understanding, how to handle the preprocessor? Ha 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.)
- billconan 5y ago
  Thank you very much for the answers! This is a great work! 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.
dcreager 5y ago
> And how to prune and simplify CST to AST at scale (supporting many languages)? 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.

dahart 5y ago

This is way cool!! I don’t have any deep questions yet, but to start I’m a bit curious about some very minor things like the name and description. I’m curious why “stack graph” as opposed to “call graph” or “callstack graph” or something like that, I’m guessing you do have some thoughts there. Also curious about the way you described it, the process overall certainly sounds a lot like parsing, compiling, and linking at the end, but you haven’t really used that analogy. I guess I’m just wondering if you’re framing the name and description carefully and if there are specific reasons you’d be willing to discuss.

dcreager 5y ago
Great questions! The framework is based on some great existing academic work from Eelco Visser's group at TU Delft. Their framework is called “scope graphs”: https://pl.ewi.tudelft.nl/research/projects/scope-graphs/ https://pl.ewi.tudelft.nl/research/projects/scope-graphs/ 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”.

ZeroCool2u 5y ago

Just out of curiosity, what's the timeline look like for adding precise code navigation to other supported languages and what languages do you think will get support first? 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/using-files/navigating-code-on-github#about-navigating-code-on-github https://docs.github.com/en/repositories/working-with-files/u...

dcreager 5y ago
It's not “easy”, but we've found that because it's based on a declarative DSL it's less effort than you might expect. And we're finding that there are common patterns that you use in your graph construction rules, because there are many aspects of name binding that end up working the same way in different languages. So, hand-wavily (not out of secrecy but because of not having rigorous data yet), we're finding that it's O(months) to get a new language out the door. 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.
- ZeroCool2u 5y ago
  Got it, that's really helpful in terms of estimating the work involved. Thanks for taking the time to answer all these questions and congrats again on the release!

one_off_comment 5y ago

For people like me who don't have time to watch the talk, what's the answer to the question posed on the blog post? "Why aren’t we using the Language Server Protocol (LSP) or Language Server Index Format (LSIF)?"

dcreager 5y ago
I go into some amount of detail in a talk I gave at last year's FOSDEM: https://dcreager.net/talks/2020-fosdem/ https://dcreager.net/talks/2020-fosdem/ 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.

dsanchez97 5y ago

I haven't had time to watch the full talk yet, so sorry if this is answered there. 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.

dcreager 5y ago
Ooh that's a good one. Right now, our lookups are only within the single repository. And so if you had two files that _could_ provide the same (fully qualified) symbol, we aren't doing any PYTHONPATH analysis to determine which one it is. We'll show you both. 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.
- dsanchez97 5y ago
  I have been doing some stuff where I analyze python code via the AST to try to figure out symbol reference so it was top of mind when I read the article. My tool works at runtime by importing the users code as module, which means all the symbols are evaluated by the python interpreter and then I can inspect the loaded module to determine the references. This is all part of a larger framework that has lifecycle rules for how/when it will load user defined code, which allows me some flexibility and 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.

chefandy 5y ago

As an aside to the technical conversation— I appreciate the use of cooking as an analogy in your code samples in the posted article. 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.

dcreager 5y ago
Haha also I like food :-)
geoduck14 5y ago
>Using nouns, adjectives and verbs from (familiar) concrete hierarchical analogies makes technical writing much more accessible. 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.

munificent 5y ago

Apologies if you answered this in the talk, but from the slides it doesn't seem you did. 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.

dcreager 5y ago
This relies on “scope stacks”, which are another piece that I didn’t really have a chance to discuss in either the blog post or Strange Loop talk. In brief, they allow you to “package up” context from one part of a file and “send it over” to another part of a (possibly different) file. We use that to model the (types of the) actual parameters passed into a function call or generic type instantiation, for instance. Scope stacks are essential for both of the more advanced examples I mention at the end of the post.
- dcreager 5y ago
  This early (and rough around the edges) design doc goes into more detail about scope stacks, and works through a couple of examples that rely on them: https://github.github.io/stack-graph-docs/ https://github.github.io/stack-graph-docs/
  - munificent 5y ago
    Thank you! I'll dig through this when I get the time.