3 ms·

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 up

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.

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.