Hi Larry,
Apologies for not getting back to you sooner on this.
I think nested graphs serve a different potential purpose to nested traversals. Typically, I would consider nested graphs representing a logical or physical hierarchy, rather than a call graph hierarchy or similar. Nested graphs can help describe static structure, whereas I think nested traversals are better at describing or hiding dynamic structure.
After looking in detail at our current graph support (including nested traversals), and looking at the use cases I had in mind, I believe nested graph support is only useful if:
1. We intend to display the results as a graph (example below); and
2. We (re-)introduce explicit cross-graph edges.
To explain the use case I had in mind, assume that we re-instated some mechanism for cross-graph dependencies as well as some mechanism for nested graphs. Taking the example you gave, lets also assume function_a and function_b are declared in the same file. We could create a new graph to represent the file itself, and nest the two function graphs underneath it. i.e the hypothetical SARIF would be:
{ # A result object
"graphs": [
{
"id": "file_a",
"nodes": [
{
"id": "function_a",
"nestedGraphId": "function_a"
},
{
"id": "function_b",
"nestedGraphId": "function_b"
}
],
},
{
"id": "function_a",
"nodes": [
{
"id": "a1",
},
{
"id": "a2",
},
{
"id": "a3"
}
],
"edges": [
...
{
"id": "e1",
"sourceNodeId" : "a2",
"targetNodeId" : "b1",
"targetGraphId" : "function_b"
}
]
},
{
"id": "function_b",
"nodes": [
{
"id": "b1"
},
"edges": [
...
{
"id": "e1",
"sourceNodeId" : "b1",
"targetNodeId" : "a3",
"targetGraphId" : "function_a"
}
]
]
}
],
...
}
This could be rendered in graph form like this:
The edges that are part of a particular traversal could be highlighted in the graph.
A smart viewer could also allow the nested graphs to be collapsed, computing edges inherited from the nested graphs, i.e like this:
To explain my earlier provisos:
- if viewers are only showing the graph traversal as a flat list of visited nodes, or some sort of path-tree with nested traversals, I don't think nested graphs provide any extra value, because there is no obvious way to include the nested graph information.
- if there are no cross-graph edges, it's also unclear how the nesting provides any extra value.
Cheers,
Luke
On Tue, Apr 24, 2018 at 1:39 PM Larry Golding (Comcast) <> wrote:
Luke, any thoughts on this?
From: <> On Behalf Of Larry Golding (Comcast)
Sent: Thursday, April 19, 2018 2:49 PM
To: Luke Cartey <>;
Subject: [sarif] Let's talk about nested graphs
I’m curious how nested graphs are used. Here’s what I mean:
You saw the proposal for “nested traversals”. If an edge has a nestedGraphTraversalId property, then when the user is about to traverse that edge, the viewer can offer them the choice of diving into or stepping over the nested traversal. (A debugger-like F10/F11 experience would be nice.) And since a traversal is single-entry, single-exit, there’s no ambiguity about how to navigate through the nested traversal.
Now let’s do something similar for graphs: insides one of the nodes of the graph for function_a, we nest a reference to the graph for function_b (see below).
My question is, who consumes this information? What do they do with it? Is this the right representation for these consumers-who-I-don’t-yet-know-anything-about? Or do they need something different, or richer?
My point is that, from the point of view of an end user experience, I have a very concrete understanding of why nested traversals are helpful, and I have no understanding of how nested graphs are helpful.
Thanks,
Larry
{ # A result object
"graphs": [
{
"id": "function_a",
"nodes": [
{
"id": "a1",
},
{
"id": "a2",
"nestedGraphId": "function_b"
},
{
"id": "a3"
}
],
"edges": [
...
]
},
{
"id": "function_b",
"nodes": [
{
"id": "b1"
},
...
]
}
],
...
}
