Bug report: Clustered subgraph leads to crash in dot

Dev
1

At my company, we use Graphviz to layout various graphs, including some data flow graphs to show how variables are being used across a number of scripts.

We’ve noticed that in some scenarios, it will simply crash when it tries to layout certain graphs. Checking a debug build of 9.0 (which is the version we’re currently using), it turns out that transpose_step fails the assertion ND_order(v) < ND_order(w), since both nodes have order 0.

After adding a bunch of debug output and attempting to trace through the bug, it looks to me like the issue is that flat_reorder never adds nodes to temprank if local_in_cnt != 0 for a node - but once it actually goes to set ND_order for the rank, it assumes all of the nodes have been added to temprank.

I also downloaded a debug build of 16.0, and here it asserts an out-of-bounds access. Glancing at the code, the fundamental issue appears to be the same, and it’s just being detected consistently in flat_reorder because 16.0 does bounds checking. However, I have not done any debugging in this version of the code yet, since I don’t have it building locally yet (that’s the next thing I’ll be looking at).

It feels like it should be safe to just stop processing that rank if a node is skipped, but I’m not entirely confident if that’s the best move, or if it’s better to try to work with what can be done. Skipping the rank makes test_2368 in the 9.0 test suite pass instead of resulting in an expected failure, but I can’t quite tell if that’s indicative of an actual issue or not.

Here’s the graph, reduced as much as I could without changing the location of the crash in 9.0:

digraph G {
	graph[ordering = "in"];
	node8->node153
	node211->node8
	node221->node8
	node12->node153
	node12->node205
	node91->node14 // possibly not needed
	node211->node22
	node48->node205
	node91->node48 // possibly not needed
	node118->node48
	node51->node221
	node118->node51
	node72->node221 // possibly not needed
	node8->node205
	subgraph group0 {
		cluster=true;
		node8
		node12
		node14 // possibly not needed
		node22
		node48
		node51
		node72 // possibly not needed
		node91 // possibly not needed
		node118
		node153
		node205
		node211
		node221
	}
}

I’ve added comments to the lines that I can still remove and see a crash, but 9.0 crashes or asserts in a different place when I do - so I left those in while doing my testing to be 100% certain I wasn’t suddenly looking at a different bug. But as I mentioned above, I suspect this is really the same issue in flat_reorder with or without those lines.

2

Thanks for reporting this. Here is your bug report: dot abort (#2854) · Issues · graphviz / graphviz · GitLab

Note this odd workaround:
nop myfile.gv | dot -Tpng -omyfile.gv
All it does is “prettyprint” (reformat & rearrange) the input. Surprising.

3

Yeah, it feels like it might be dependent on internal ordering of the edges - in the nop image, it routes the long edge on the far right, but if you just remove e.g. the edge node8->node153 in my reproduction file, it will generate the rest of the graph properly - but the long edge ends up going between node12 and node22.

From the debug output I’ve been looking at, it appears to be creating an intermediate placeholder node in the layer when it’s routing in-between those nodes. It seems like it does not do that when the edge ends up on the far right, since it doesn’t need to leave room in the middle of the layer.

I’ll investigate if running it through nop first makes a difference in the real scenario, but I kinda suspect that might be more of a coincidence than a guaranteed outcome.

I got 16.0.0 building locally, and with a slight modification to flat_reorder I could get it to generate the graph without crashing:

diff --git a/lib/dotgen/mincross.c b/lib/dotgen/mincross.c
index 1aeb25626..265378d1b 100644
--- a/lib/dotgen/mincross.c
+++ b/lib/dotgen/mincross.c
@@ -1325,6 +1325,7 @@ static void postorder(graph_t *g, node_t *v, nodes_t *list, int r) {

 static void flat_reorder(graph_t *g) {
   int i, r, local_in_cnt, local_out_cnt, base_order;
+  bool valid_rank;
   node_t *v;
   nodes_t temprank = {0};
   edge_t *flat_e, *e;
@@ -1334,6 +1335,7 @@ static void flat_reorder(graph_t *g) {
   for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
     if (GD_rank(g)[r].n == 0)
       continue;
+    valid_rank = true;
     base_order = ND_order(GD_rank(g)[r].v[0]);
     for (i = 0; i < GD_rank(g)[r].n; i++)
       MARK(GD_rank(g)[r].v[i]) = false;
@@ -1362,11 +1364,14 @@ static void flat_reorder(graph_t *g) {
       else {
         if (!MARK(v) && local_in_cnt == 0) {
           postorder(g, v, &temprank, r);
+        } else {
+          valid_rank = false;
+          break;
         }
       }
     }

-    if (!LIST_IS_EMPTY(&temprank)) {
+    if (valid_rank && !LIST_IS_EMPTY(&temprank)) {
       if (!GD_flip(g)) {
         LIST_REVERSE(&temprank);
       }

The test suite in 16.0.0 gives the same results with and without this patch, except for the aforementioned test_2368 which now passes when it’s an expected fail.