Re: [sarif] Nested graphs: adopting Luke's proposal

[Luke Cartey <luke@semmle.com>]

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.

Cheers,

Luke

On Mon, May 7, 2018 at 11:38 AM Larry Golding (Comcast) <larrygolding@comcast.net> wrote:

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

 

From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast)

Sent: Monday, May 7, 2018 11:09 AM

To: 'Luke Cartey' <luke@semmle.com>
Cc: sarif@lists.oasis-open.org

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.

 

Cheers,

 

Luke

 

On Mon, May 7, 2018 at 11:02 AM Larry Golding (Comcast) <larrygolding@comcast.net> wrote:

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

To: Larry Golding (Comcast) <larrygolding@comcast.net>
Cc: sarif@lists.oasis-open.org

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:

 

file_a

  - function_a

       -function_a

            -a1

            -a2

            -a3

 

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?

 

Cheers,

 

Luke

 

On Mon, May 7, 2018 at 9:37 AM Larry Golding (Comcast) <larrygolding@comcast.net> wrote:

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

 

From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast)

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