OASIS Static Analysis Results Interchange Format (SARIF) TC

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   ---  Begin Message  --- 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:   Your design: Only allows valid inter-graph traversals (good) Allows visualization of static structural relationships among graphs (good) Makes is harder for a viewer to present a step over/step into experience Existing design Allows any Intergraph traversals, even invalid ones Makes is easy for a viewer to present a step over/step into experience No notion of Intergraph relationships. Larry     From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast) Sent: Tuesday, May 1, 2018 9:02 PM To: 'Luke Cartey' <luke@semmle.com> Cc: sarif@lists.oasis-open.org Subject: RE: [sarif] Let's talk about nested graphs   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:   As in the existing spec: a graphTraversal includes an edgeTraversal that contains a nestedGraphTraversalId . As in your nested graphs proposal: a graphTraversal includes an edgeTraversal whose edgeId specifies an edge that contains a targetGraphId .   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 edgeTraversal s 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 Sent: Tuesday, May 1, 2018 8:26 PM To: Larry Golding (Comcast) < larrygolding@comcast.net > Cc: sarif@lists.oasis-open.org Subject: Re: [sarif] Let's talk about nested graphs   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) < larrygolding@comcast.net > wrote: Luke, any thoughts on this?   From: sarif@lists.oasis-open.org < sarif@lists.oasis-open.org > On Behalf Of Larry Golding (Comcast) Sent: Thursday, April 19, 2018 2:49 PM To: Luke Cartey < luke@semmle.com >; sarif@lists.oasis-open.org 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"         },         ...       ]     }   ],   ... } ---  End Message  ---

JSON arrays provide a length member, yes? So to efficiently determine whether the nested graph terminates internally or steps back into the current graph, the viewer only needs to consult the final edge in the nested graph edge array to see whether it returns to the current graph. i.e., a constant time look-up rather than by N of nested graph edges.   My browser test of a JSON snippet shows that length is a valid property of an array. Of course, someone needs to traverse the collection at least once to produce this value. But edge array consumers shouldn’t need to duplicate that work in order to provide step-over behavior, unless I’m missing something.   Michael 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  

Hi Michael,   JSON itself doesn’t have the notion of “array length”, but you’re right that an API like Newtonsoft.Json would represent a JSON array as a .NET array, which has a Length property.   BUT! In Luke’s proposal, a graph traversal is a flat array of edge traversals, each of which refers to an edge, but some of the edges might point to another graph. There is no “nested array” whose length you can take. That was the one advantage of my proposal: you could identify a nested traversal in constant time.   Larry   From: Michael Fanning <Michael.Fanning@microsoft.com> Sent: Monday, May 7, 2018 9:29 AM To: Larry Golding (Comcast) <larrygolding@comcast.net>; sarif@lists.oasis-open.org Subject: RE: [sarif] Nested graphs: adopting Luke's proposal   JSON arrays provide a length member, yes? So to efficiently determine whether the nested graph terminates internally or steps back into the current graph, the viewer only needs to consult the final edge in the nested graph edge array to see whether it returns to the current graph. i.e., a constant time look-up rather than by N of nested graph edges.   My browser test of a JSON snippet shows that length is a valid property of an array. Of course, someone needs to traverse the collection at least once to produce this value. But edge array consumers shouldn’t need to duplicate that work in order to provide step-over behavior, unless I’m missing something.   Michael 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  

BUT you’re right about the most important point: A viewer could evaluate the graph traversal once at load time, identifying the nodes that represent the start of nested traversals, and counting the nodes from there until the matching “return”. Then, at “traversal time”, if the user selects “step over”, the viewer could just add that count to the array index to find the target node.   So the one disadvantage of Luke’s proposal is even less important than I thought.   Larry   From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast) Sent: Monday, May 7, 2018 9:41 AM To: 'Michael Fanning' <Michael.Fanning@microsoft.com>; sarif@lists.oasis-open.org Subject: RE: [sarif] Nested graphs: adopting Luke's proposal   Hi Michael,   JSON itself doesn’t have the notion of “array length”, but you’re right that an API like Newtonsoft.Json would represent a JSON array as a .NET array, which has a Length property.   BUT! In Luke’s proposal, a graph traversal is a flat array of edge traversals, each of which refers to an edge, but some of the edges might point to another graph. There is no “nested array” whose length you can take. That was the one advantage of my proposal: you could identify a nested traversal in constant time.   Larry   From: Michael Fanning < Michael.Fanning@microsoft.com > Sent: Monday, May 7, 2018 9:29 AM To: Larry Golding (Comcast) < larrygolding@comcast.net >; sarif@lists.oasis-open.org Subject: RE: [sarif] Nested graphs: adopting Luke's proposal   JSON arrays provide a length member, yes? So to efficiently determine whether the nested graph terminates internally or steps back into the current graph, the viewer only needs to consult the final edge in the nested graph edge array to see whether it returns to the current graph. i.e., a constant time look-up rather than by N of nested graph edges.   My browser test of a JSON snippet shows that length is a valid property of an array. Of course, someone needs to traverse the collection at least once to produce this value. But edge array consumers shouldn’t need to duplicate that work in order to provide step-over behavior, unless I’m missing something.   Michael 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  

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  

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  

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  

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  

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  

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  

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  

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   From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Luke Cartey Sent: Monday, May 7, 2018 1:52 PM To: Larry Golding (Comcast) <larrygolding@comcast.net> Cc: sarif@lists.oasis-open.org Subject: Re: [sarif] Nested graphs: adopting Luke's proposal   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  

I would also like to prohibit the final case, because I believe graph viewers will find it difficult to display. Cheers, Luke On Mon, May 7, 2018 at 2:11 PM Larry Golding (Comcast) < larrygolding@comcast.net > wrote: 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   From: sarif@lists.oasis-open.org < sarif@lists.oasis-open.org > On Behalf Of Luke Cartey Sent: Monday, May 7, 2018 1:52 PM To: Larry Golding (Comcast) < larrygolding@comcast.net > Cc: sarif@lists.oasis-open.org Subject: Re: [sarif] Nested graphs: adopting Luke's proposal   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  

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.   Cheers,   Luke   On Mon, May 7, 2018 at 2:11 PM Larry Golding (Comcast) < larrygolding@comcast.net > wrote: 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   From: sarif@lists.oasis-open.org < sarif@lists.oasis-open.org > On Behalf Of Luke Cartey Sent: Monday, May 7, 2018 1:52 PM To: Larry Golding (Comcast) < larrygolding@comcast.net > Cc: sarif@lists.oasis-open.org Subject: Re: [sarif] Nested graphs: adopting Luke's proposal   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  

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.   Cheers,   Luke   On Mon, May 7, 2018 at 2:11 PM Larry Golding (Comcast) < larrygolding@comcast.net > wrote: 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   From: sarif@lists.oasis-open.org < sarif@lists.oasis-open.org > On Behalf Of Luke Cartey Sent: Monday, May 7, 2018 1:52 PM To: Larry Golding (Comcast) < larrygolding@comcast.net > Cc: sarif@lists.oasis-open.org Subject: Re: [sarif] Nested graphs: adopting Luke's proposal   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  

TL;DR: Michael and I discussed this extensively and Luke’s proposal is fine . I wrongly thought that the design couldn’t handle calls to the same function from multiple call sites. But it can.   Details:   Michael pointed out that the return from a function to each of its call sites is represented by a separate edge .   Here is an extended example, which I will leave you to trace through, rather than me writing a novel to explain it