Flame graphs specify parent/child structure

ql/ql/src/experimental/Graph.qll

@@ -0,0 +1,70 @@
+/**
+ * Defines graphs and charts that can be rendered by VScode.
+ *
+ * Graphs are output using the query predicates
+ * `graph_info`, `graph_chart`, `graph_xy`, `graph_span`
+ *
+ * The class `Graph` is used to define graph contents.
+ * It is possible to define several graphs in the same query file, by using
+ * a different name for each graph object.
+ */
+module Graph {
+  /**
+   * A graph that the VSCode extension can render.
+   * Extend this class to add new graphs.
+   */
+  abstract class Graph extends string {
+    bindingset[this]
+    Graph() { any() }
+
+    /**
+     * Gets the type of the graph: Currently "bar", "line" or "flame"
+     */
+    abstract string getType();
+
+    /**
+     * Gets the title of the graph, can be overridden.
+     */
+    string getTitle() { result = this }
+
+    /**
+     * Defines chart data, required for chart type = "bar"
+     */
+    predicate chartData(string key, int series, float value) { none() }
+
+    /**
+     * Defines point data.
+     * `series` can be set to 0 if there is only one series in the graph.
+     */
+    predicate pointData(int series, float x, float y) { none() }
+
+    /**
+     * Defines span data, for use in flame graphs.
+     * Specify `text=""` for the root node.
+     * Specify `offset=0` if unused.
+     * Right now, the ID of each node is a string - I couldn't figure out how to make this work with generic types
+     * in a nice way or using parameterized modules.
+     */
+    predicate flameData(string id, string text, string parent, float value, float offset) { none() }
+  }
+
+  query predicate graph_info(Graph graph, string field, string value) {
+    field = "type" and value = graph.getType()
+    or
+    field = "title" and value = graph.getTitle()
+  }
+
+  query predicate graph_chart(Graph graph, string key, int series, float value) {
+    graph.chartData(key, series, value)
+  }
+
+  query predicate graph_xy(Graph graph, int series, float x, float y) {
+    graph.pointData(series, x, y)
+  }
+
+  query predicate graph_flame(
+    Graph graph, string id, string text, string parent, float value, float offset
+  ) {
+    graph.flameData(id, text, parent, value, offset)
+  }
+}

ql/ql/test/experimental/graphs.expected

@@ -0,0 +1,58 @@
+graph_info
+| Here is a bar chart | title | Here is a bar chart |
+| Here is a bar chart | type | bar |
+| Here is a line chart | title | Here is a line chart |
+| Here is a line chart | type | line |
+| Here is the flame graph | title | Here is the flame graph |
+| Here is the flame graph | type | flame |
+graph_chart
+| Here is a bar chart | C++ | 0 | 21.0 |
+| Here is a bar chart | Python | 0 | 3.1 |
+| Here is a bar chart | TypeScript | 0 | 5.0 |
+graph_xy
+| Here is a line chart | 0 | 0.0 | 0.0 |
+| Here is a line chart | 0 | 1.0 | 1.0 |
+| Here is a line chart | 0 | 2.0 | 4.0 |
+| Here is a line chart | 0 | 3.0 | 9.0 |
+| Here is a line chart | 0 | 4.0 | 16.0 |
+| Here is a line chart | 0 | 5.0 | 25.0 |
+| Here is a line chart | 0 | 6.0 | 36.0 |
+| Here is a line chart | 0 | 7.0 | 49.0 |
+| Here is a line chart | 0 | 8.0 | 64.0 |
+| Here is a line chart | 0 | 9.0 | 81.0 |
+| Here is a line chart | 0 | 10.0 | 100.0 |
+| Here is a line chart | 0 | -1.0 | 1.0 |
+| Here is a line chart | 0 | -2.0 | 4.0 |
+| Here is a line chart | 0 | -3.0 | 9.0 |
+| Here is a line chart | 0 | -4.0 | 16.0 |
+| Here is a line chart | 0 | -5.0 | 25.0 |
+| Here is a line chart | 0 | -6.0 | 36.0 |
+| Here is a line chart | 0 | -7.0 | 49.0 |
+| Here is a line chart | 0 | -8.0 | 64.0 |
+| Here is a line chart | 0 | -9.0 | 81.0 |
+| Here is a line chart | 0 | -10.0 | 100.0 |
+| Here is a line chart | 1 | 0.0 | -5.0 |
+| Here is a line chart | 1 | 1.0 | -3.0 |
+| Here is a line chart | 1 | 2.0 | -1.0 |
+| Here is a line chart | 1 | 3.0 | 1.0 |
+| Here is a line chart | 1 | 4.0 | 3.0 |
+| Here is a line chart | 1 | 5.0 | 5.0 |
+| Here is a line chart | 1 | 6.0 | 7.0 |
+| Here is a line chart | 1 | 7.0 | 9.0 |
+| Here is a line chart | 1 | 8.0 | 11.0 |
+| Here is a line chart | 1 | 9.0 | 13.0 |
+| Here is a line chart | 1 | 10.0 | 15.0 |
+| Here is a line chart | 1 | -1.0 | -7.0 |
+| Here is a line chart | 1 | -2.0 | -9.0 |
+| Here is a line chart | 1 | -3.0 | -11.0 |
+| Here is a line chart | 1 | -4.0 | -13.0 |
+| Here is a line chart | 1 | -5.0 | -15.0 |
+| Here is a line chart | 1 | -6.0 | -17.0 |
+| Here is a line chart | 1 | -7.0 | -19.0 |
+| Here is a line chart | 1 | -8.0 | -21.0 |
+| Here is a line chart | 1 | -9.0 | -23.0 |
+| Here is a line chart | 1 | -10.0 | -25.0 |
+graph_flame
+| Here is the flame graph | item1 | Item 1 |  | 50.0 | 0.0 |
+| Here is the flame graph | item2 | Item 2 | item1 | 25.0 | 0.0 |
+| Here is the flame graph | item3 | Item 3 | item2 | 10.0 | 5.0 |

ql/ql/test/experimental/graphs.ql

@@ -0,0 +1,45 @@
+/**
+ * Sample/test of the graphs library.
+ */
+
+import experimental.Graph::Graph
+
+class SampleBarChart extends Graph {
+  SampleBarChart() { this = "Here is a bar chart" }
+
+  override string getType() { result = "bar" }
+
+  override predicate chartData(string key, int series, float value) {
+    key = "C++" and series = 0 and value = 21.0
+    or
+    key = "Python" and series = 0 and value = 3.1
+    or
+    key = "TypeScript" and series = 0 and value = 5.0
+  }
+}
+
+class SampleLineGraph extends Graph {
+  SampleLineGraph() { this = "Here is a line chart" }
+
+  override string getType() { result = "line" }
+
+  override predicate pointData(int series, float x, float y) {
+    series = 0 and x in [-10 .. 10] and y = x * x
+    or
+    series = 1 and x in [-10 .. 10] and y = -5 + 2 * x
+  }
+}
+
+class SampleFlameGraph extends Graph {
+  SampleFlameGraph() { this = "Here is the flame graph" }
+
+  override string getType() { result = "flame" }
+
+  override predicate flameData(string id, string text, string parent, float value, float offset) {
+    id = "item1" and text = "Item 1" and parent = "" and value = 50 and offset = 0
+    or
+    id = "item2" and text = "Item 2" and parent = "item1" and value = 25 and offset = 0
+    or
+    id = "item3" and text = "Item 3" and parent = "item2" and value = 10 and offset = 5
+  }
+}