[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: RE: [sarif] Nested graphs: adopting Luke's proposal
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.
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.
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.
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:
My “nested traversals” proposal has, AFAIK, only one advantage:
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.