OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.

 


Help: OASIS Mailing Lists Help | MarkMail Help

sarif message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]


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:

 

  1. As in the existing spec: a graphTraversal includes an edgeTraversal that contains a nestedGraphTraversalId.

  2. 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 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
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: 

 

image.png

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:

 

image.png

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"

        },

        ...

      ]

    }

  ],

  ...

}



[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]