Luke, I think there’s a slight problem in your example, which I reproduce here: { # 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" } ] ] } ], ... } It’s fine that graph function_a’s edge e1 represents a call to function_b. The problem is that function_b’s edge e1 represents a return to function_a (in fact, a return to a specific location within function_a). function_b can be called from multiple places in multiple functions. This part of the example conflates the notion of graph with the notion of graph traversal, in that function_b’s edge e1 represents a particular code path. I think we’re missing the notion of an “exit node” from a graph. We might represent it, for example, by adding a Boolean property isExit to the edge object. Thoughts? Larry From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast)
Sent: Monday, May 7, 2018 2:20 PM
To: 'Luke Cartey' <luke@semmle.com>
Cc: sarif@lists.oasis-open.org
Subject: RE: [sarif] Nested graphs: adopting Luke's proposal Ok, I’ll add the words. From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Luke Cartey
Sent: Monday, May 7, 2018 2:19 PM
To: Larry Golding (Comcast) <larrygolding@comcast.net>
Cc: sarif@lists.oasis-open.org
Subject: Re: [sarif] Nested graphs: adopting Luke's proposal I would also like to prohibit the final case, because I believe graph viewers will find it difficult to display. So, we prohibit this case: A B B We permit this case: A B C B You just described this case. I can’t tell from what you wrote; do you want to permit it? A B C D C Larry Sent: Monday, May 7, 2018 1:52 PM I agree that if two different graphs nest the same graph, that seems fairly reasonable. However, one parent graph could have many layers of graph nesting (functions within files within folders, for example), which could, further down the chain, nest the same graph in two different locations in the same ultimate parent graph. A graph can be nested under only a single node of a given graph. Can a graph be nested under nodes in more than one graph? Your concern about visualization is less important in this case, because presumably you’re visualizing one parent graph at a time. And if you did have a multi-window UI that visualized multiple parent graphs simultaneously, if would be ok to repeat the drawing of the child graph under each of its parents. Larry Sent: Monday, May 7, 2018 11:09 AM Subject: RE: [sarif] Nested graphs: adopting Luke's proposal Ah, I see, you’re not nesting a function in a function, you’re nesting a function in a file. We can certainly add this restriction. Do you think we need to provide guidance on that kinds of models we are enabling and prohibiting? Do you have any words in mind? From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Luke Cartey
Sent: Monday, May 7, 2018 11:05 AM
To: Larry Golding (Comcast) <larrygolding@comcast.net>
Cc: sarif@lists.oasis-open.org
Subject: Re: [sarif] Nested graphs: adopting Luke's proposal Ah, but that is now represented as multiple edges to the same nested graph. In my example, you can have multiple edges into the graph for Function-B, but Function-B is only nested under File-A. If we prohibit multiple parents, then it makes life easier for the viewer, as it can render it as a nested diagram, as in my example. It's much harder to render a graph where the nested graphs have multiple possible parents. Ok, a single value it is. I was not planning to prohibit a graph from being nested under multiple nodes. Function-A can call Function-B in multiple places, right? Larry From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Luke Cartey
Sent: Monday, May 7, 2018 10:57 AM Subject: Re: [sarif] Nested graphs: adopting Luke's proposal Hi Larry, My intention was that the node in the parent graph, and the nested graph itself were equivalent. In the example I had, the node "function_a" in the graph "file_a", which is equivalent to the graph with id "function_a". For a SARIF viewer, the way this can be rendered is to place any nodes within the nested graph inside the "parent" node. For example, nodes a1-a3 were rendered directly in the "function_a" node in the "file_a" graph. If we permitted multiple nested graphs within one node, then we would need to render the nested graph as a separate node from the parent node. In my example, you would then have: Which seems redundant. I'm also not sure what you're enabling by making it an array - if you want to have multiple nested graphs, you could just have multiple nodes in the parent graph, one for each graph you want to nest. On a related note, are you planning to prohibit graphs from being nested under multiple different nodes? Luke, Shouldn’t node.nestedGraphId:string be an array, node.nestedGraphIds:string[]? Can’t a node contain multiple child graphs? That’s how I’ll write the change draft unless I hear otherwise. Larry Sent: Monday, May 7, 2018 9:06 AM
To: sarif@lists.oasis-open.org
Subject: [sarif] Nested graphs: adopting Luke's proposal
Importance: High My sense of the TC’s discussion on nested graphs, combined with the attached thread, is that Luke’s “nested graphs” proposal has these advantages: - It can only represent “valid” inter-graph traversals; that is, traversals where there is an explicit edge from the source graph to the target graph.
My “nested traversals” proposal, OTOH, allows you to jump into any graph, even if the two graphs are unrelated. (That’s a bad thing.) - It can represent a graph traversal that terminates within the nested graph (a common scenario).
My “nested traversals” proposal, OTOH, only allows graph traversals which ultimately exits from the nested traversal. - It can represent a logical hierarchy of graphs, allowing a viewer to visualize the hierarchy, and to collapse nested graphs.
My “nested traversals” proposal, OTOH, does not represent this concept at all.
My “nested traversals” proposal has, AFAIK, only one advantage: - It’s easier for a viewer to recognize a nested traversal, and to offer a debugger-like step into/step over experience. But in Luke’s proposal, a viewer can still do this; it just has to trace forward until it sees an exit from the nested graph before it can decide whether to allow a “step into”.
Based on this, I’m going to produce a change draft that removes nested traversals and implements Luke’s nested graphs proposal. Please speak up if you disagree. Larry
|