Design for #46: graphs and graph traversals

At the TC meeting on Wednesday, we’ll discuss a proposal for representing graphs and graph traversals (Issue #46). This mail presents the proposal.

My notation, which I’ll also use in a subsequent design proposal emails, is:

Object names are at the left margin.
Property names are indented under object names.
If the property’s type of is the same as its name, we just show the property name, for example, location.
If the property’s type is different from its name, we show it as propertyName:propertyType, for example, graphs:graph[] (the type of the graphs property is “array of graph”).
+ means a new object, or a new property on an existing object
- means a property or object is removed.
I don’t mention properties that are unchanged.

The design is:

run

+graphs:graph[]

+graph

id:string

description:message

nodes:node[]

edges:edge[]

+node

id:integer

label:message

edges:integer[] # The ids of the edges that connect to this node.

location # Code location associated with this node.

properties:propertyBag

+edge

id:integer

source:integer # Id of the source node.

target:integer # Id of the target node.

properties:propertyBag

+graphTraversal

graphId:string

description:message

edgeTraversals:edgeTraversal[]

+edgeTraversal:

edgeId:integer

message:message

result

+graphs:graph[]

+graphTraversals:graphTraversal[]

The features of the design are:

You can define graphs at the run level or at the result level.
Each node has an associated location.
A result can have an array of graphTraversal objects, which represent paths through the graph.
A graphTraversal refers to the graph it traverses through its graphId property, which refers to the id property of some graph (which, again, might be on the result or on the run).
A graphTraversal is an ordered sequence of edgeTraversals.

Larry

sarif message