- From: "Larry Golding \(Comcast\)" <larrygolding@comcast.net>
- To: "'Luke Cartey'" <luke@semmle.com>
- Date: Wed, 2 May 2018 08:19:06 -0700
I thought more about this and I’m wrong: Your proposal does allow traversals to navigate between any graphs with a connecting edge, not just graphs that are related by nesting. That should have been obvious to me; in your example, A and B are disjoint. And your proposal has the advantage that it permits only “valid” traversals. In my proposal, you can stick any graph traversal within any edge traversal, even if there is no edge connecting the outer traversal’s graph to the nested traversal’ graph – which in my proposal, there never is because my proposal doesn't have inter-graph edges. Finally, if I'm worried about there being two ways to represent inter-graph traversals, we could remove my nested traversals. So the tradeoffs are:
Larry From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast) I see. And to implement this kind of viewing experience we just need node.nestedGraphId and edge.targetGraphId. A possible down side is that we would now have two ways to represent a traversal into a nested graph:
But technique #2 would only work if the traversal were stepping into a nested graph (because targetGraphId must always specify a nested graph). Technique #1 works between any two graphs for which it’s possible to call from one into the other. A slight advantage of the current spec is that it makes it very easy for a viewer to expand and collapse a nested traversal – because the nested traversal is entirely contained within a single edgeTraversal. With your proposal, the viewer would have to walk the edgeTraversals from the entry point of the nested graph until it found one that stepped back out to the parent graph. *shrug* It’s not like that’s hard to do. I haven’t come to any conclusions – just thinking out loud. The trade-off of this proposal is the advantage of being able to visualize static, nested structures vs the disadvantage of added complexity due to the choice of techniques for representing nested traversals. Larry From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Luke Cartey 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 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", } ] }, { "id": "function_b", "nodes": [ { "id": "b1" }, "edges": [ ... "id": "e1", "sourceNodeId" : "b1", } ] ] } ], ... } 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) <larrygolding@comcast.net> wrote:
|
--- End Message ---