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: The "nested edge traversal" design

Here’s a design for nested graphs that uses “nested edge traversals.” It’s one of three possible nested graph designs we’ve considered so far. I wanted to show it because Michael asked for more information about it this morning.


Suppose we have a graph of code locations in function A:


na1 --ea1--> na2 --ea2--> na3 --ea3--> na4


Here, na1 is a node and --ea1--> is an edge. Node na1 is the function entry point, node na3 represents a call to function B, and node na4 is the function exit point.


Suppose we also have a graph of function B:


nb1 --eb1--> nb2 --eb2--> nb3 –-eb4--> nb4 -–eb5--> nb5 –-eb6--> nb6

                           |                         ^

                           |                         |



Node nb3 represents a branch such as an if statement.


Now for the traversals. Remember: in the current design an “edge traversal” specifies an edge id, and an edge in turn specifies a source node id and a target node id, for example:


{                           # An edgeTraversal object

 "edgeId": "ea2"

  ...                       # other properties



{                           # An edge object

  "id": "ea2",

  "sourceNodeId": "na2",

  "targetNodeId": "na3"



A top-level graph traversal of function A would look like this:


{                           # A graphTraversal object

  "graphId": "FunctionA",


  "edgeTraversals": [

    { "edgeId": "ea1"},

    { "edgeId": "ea2"},

    { "edgeId": "ea3"}




Suppose you’ve used your SARIF viewer to traverse edges ea1 and ea2, you’re sitting on node na3 (the function call), and you want to dive in and see the path through function B before you continue on to traverse edge ea3.


To support this, we add a new property nestedGraphTraversal to the edgeTraversal object. One possible traversal of function B is [ eb1, eb2, eb3, eb6 ]. The JSON representation of edge ea2 becomes:



  "edgeId": "ea2",


  "nestedGraphTraversal": {

    "graphId": "FunctionB",

    "edgeTraversals": [

      { "edgeId": "eb1"},

      { "edgeId": "eb2"},

      { "edgeId": "eb3"},

      { "edgeId": "eb6"}





The presence of edgeTraversal.nestedGraphTraversal allows the SARIF viewer to provide a visual cue telling the user that before she proceeds to the next edge traversal (ea3), she can first traverse the nested traversal. The nested traversal starts at the source node of its first edge traversal (nb1) and ends at the target node of its last edge traversal (nb6).


If the user decided to dive in, her full path through the graph would be:


[ ea1, ea2, eb1, eb2, eb3, eb6, ea3 ]


As a result, she would visit the following nodes, in this order:


[ na1, na2, na3*, nb1, nb2, nb3, nb5, nb6, na4 ]


* Remember, node na3 is the site of the function call.




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