To solve this problem, we both need to consider how to define the complete graph + its nested graphs and to define a traversal through the same.
A question I have is whether we’re assuming that what we’re calling a nested graph here represents a single-entry/single-exit graph that effectively provides the ‘exploded view’ of a single node. This seems required if we are thinking about
a sort of ‘step over’ or ‘step into nested graph’ experience.
If we support general subgraphs (and not strictly single-entry/single exit), then I suppose this provides more flexibility but am not entirely sure what it would be used for. In this case, ‘outer’ doesn’t really mean anything, the traversal
simply leaps into another section of the graph.
From: Larry Golding (Comcast) <larrygolding@comcast.net>
Sent: Friday, March 30, 2018 2:37 PM
To: Michael Fanning <Michael.Fanning@microsoft.com>; sarif@lists.oasis-open.org
Subject: RE: [sarif] Graphs design changes
I thought a little more about how you navigate into and out of sub-graphs.
- Suppose an
edgeTraversal, in addition to its existing
target property (which specifies a node id), also specifies a
subGraphId property (as you suggested). That is, it is saying: “Please navigate to node
edgeTraversal.target in the graph whose id is
edgeTraversal.subGraphId. In that case, we don’t need a node in the top level graph to “wrap” the sub-graph, right (since we’re navigating directly into the sub-graph)? And so we don’t actually need a property
node.subGraphId!
- So now the most straightforward way to navigate
out of the sub-graph is to specify an edgeTraversal whose
subGraphId property specifies the id of the “outer” graph. So now, we don’t really have a “nesting” of graphs; we have a
chain of edge traversals that can navigate from any graph to any other. Looking at it that way, I would just name the property
edgeTraversal.targetGraphId rather than
edgeTraversal.subGraphId. That goes nicely with the existing property names
source and
target. In fact, I would prefer those names to be more explicit:
edgeTraversal
sourceNodeId:string - required
targetNodeId:string - required
targetGraphId:string – optional
What do you think?
Larry
Inline
I’ll make the changes.
- Not an open issue. The edge defines a source and target, so directionality is represented. For bidirectional links, you need to define two edges.
[Larry]. Ah, right - Labels describe the elements of a fully formed graph, the nodes and its edges. In a graph traversal, we provider user-facing messages that, reviewed in sequence, take a user through a specific problem.
[Larry] Sounds good. - Why have we named state ‘finalState’ in the traversal? Is that what we landed on for other constructs as well?
[Larry] My thought was: When you enter the first node of a traversal, you start off in some state (graphTraversal.initialState) Then, as you traverse
each edge, the state changes to edgeTraversal.finalState (although I supposed
newState might be better). I’m open to better names, but I think the semantics I’m describing are good.
AFAIK there isn’t another construct with similar semantics. In a threadFlow, there is no notion of nodes and edges. We associate a state with each location (codeFlowLocation.state).
I have always assumed – although the spec is not explicit on this point – that the state reflects the program state
before the line of code specified by that location is executed, which is the usual debugger experience. - A node should have a nestedGraphId or subGraphId. This points to another graph the collected nodes of which comprise the current node.
[Larry] That’s better than what I currently have in graphs.txt, which is
nestedGraph:graph.
- We can’t currently allow a graphTraversal to step into a subgraph if it cares to, because we don’t provide a graphId on the edgeTraversal class. We could provide an optional subgraphId property on an edgeTraversal
to support this case (if absent, the graph id would be assumed to be the one defined at the graphTraversal level.
[Larry] Sounds good.
Another open issue is:
- Do we represent the directionality of an edge?
I pushed a changed to
Documents/ChangeDrafts/Active/graphs.txt that incorporates the changes we discussed at the TC meeting. I understand there’s still some discussion, for example:
- Is there a distinction between a “label” and a “user facing message” on nodes and edges?
- Exactly how do we incorporate sub-graphs?
- Do we want to define additional properties on edgeTraversal?
But I’m going to start writing with what we have.
The easiest way to see the changes I just incorporated is to look at the
commit.
Thanks,
Larry
|