CodeQL graph viewer in VS Code

[jcreedcmu]

Describe the solution you'd like
A graph viewer within the VS Code extension, for displaying the results of @kind graph queries. Currently, we seem to display @kind graph queries in the alerts(!) view.

The CodeQL CLI already produces DGML, and could easily be extended to produce other graph formats. GraphML output is also implemented, but not currently wired up to the format output options.

For completeness, I'll also mention that SARIF has a graph format we could use, although we'd then be responsible for writing a viewer for it.

Describe alternatives you've considered
CodeQL for Eclipse is the only alternative at the moment.

[aeisenberg]

How useful would it be to display the graph in a tree viewer? We could decide that we can switch between fan-in and fan-out at the root node. If this is a DAG, then that would work reasonably well.

[hvitved]

How useful would it be to display the graph in a tree viewer?

I use the Eclipse graph viewer for visualizing control-flow graphs. These can often have cycles, so there a DAG restriction does not apply.

[aeisenberg]

Thanks for the context. I wonder if our best approach would be to generate some sort of graphviz graph and then require the user to open the graph in a graphviz plugin in the workspace (there are lots to choose from and we can add a dependency on one of them so it gets installed automatically).

The benefit here is that since we're using a generic graphing language, the graph can be opened in any viewer, exported and shared, edited, etc.

Downside is that I don't think these graphs are very interactive.

Graphs would look something like this:
http://webgraphviz.com/

[aeisenberg]

Looks like the language allows for a https://www.graphviz.org/doc/info/attrs.html#d:URL attribute, which vscode can intercept and open code in the right location.

[hvitved]

Looks like the language allows for a https://www.graphviz.org/doc/info/attrs.html#d:URL attribute, which vscode can intercept and open code in the right location.

The ability to have links from nodes in the visualized CFG to the relevant source locations is quite crucial, I hope it is doable.

[rdmarsh2]

A tree viewer would be great as an interface for the C++ PrintAST.qll and any equivalents that are done for other languages.

[aeisenberg]

@rdmarsh2 I agree and I am hoping we can implement this. Though, the use case from @hvitved is for control flow and would probably require a different implementation.

[rdmarsh2]

Yeah - the graph viewer in QL4E was the right style for CFGs. We might want either an additional piece of metadata or some new @kind options to suggest which style a particular query should default to using, and possibly allow tree viewer queries to switch to the visual viewer but not vice versa.

[max-schaefer]

The AST-printing queries set a graph property to indicate that they produce a tree.

[aschackmull]

The ability to have links from nodes in the visualized CFG to the relevant source locations is quite crucial, I hope it is doable.

I'll second this. I think one of the main use-cases for graph viewing in VSCode is to better understand path explanations and in particular debug partial flow (such queries also give a graph output that's compatible with @kind graph). For that use-case it is crucial that the link between the graph and the source works seamlessly and probably also that it's possible to focus the graph around some node, say with a horizon of some fixed short distance, as the graph can easily have 100,000-1,000,000 nodes.

[aeisenberg]

@aschackmull By short distance, are you talking about a fixed number of edges from a root node? Or do you mean restrictions by function or file?

[aeisenberg]

I'm going to work on a more straight forward feature first, the AST viewer. See the issue above.

[aschackmull]

By short distance, are you talking about a fixed number of edges from a root node? Or do you mean restrictions by function or file?

I was thinking a fixed number of edges from the currently selected node, but other distance measures based on the source location might also be desirable.

[aeisenberg]

Thanks. I asked that because I've heard specifically from others that they want restrictions based on source locations. We probably want some sort of hybrid.

[dbartol]

If feasible, I'd like for our full graph viewer's UI to be implemented and controlled by us (possibly starting from an existing implementation). This would give us the ability to customize links, formatting of node content, hover text, etc. However, I really do not want to get into the graph layout algorithm business. We should just shell out to GraphViz or MSAGL or something.

[aeisenberg]

@tausbn mentioned this Markdown Graph Viewer, which might be a good way to visualize control flow or data flow graphs. https://marketplace.visualstudio.com/items?itemName=tchayen.markdown-links

We would need to convert the results into a set of markdown files with links between them, but this would still be easier than creating our own graph viewer.

[rdmarsh2]

That looks like it doesn't have content in the nodes, just names. The Eclipse viewer allowed embedding arbitrary text in the nodes, which was useful for visualizing the C++ IR control flow graph (each basic block was a node, with a text dump of the instructions in that basic block)

[tausbn]

To be honest, I wasn’t thinking of using that particular extension as a graph viewer (as generating the necessary Markdown files seems a bit circuitous), but rather noting that it uses a simple WebView running D3.js to show the graph. It’s possible D3 allows for a more rich graph structure, that could include other information than just the names.