From a98149a896a2c1fd1c050db5cfcbc398c871f365 Mon Sep 17 00:00:00 2001
From: Matthew Fernandez <matthew.fernandez@gmail.com>
Date: Sat, 31 Oct 2020 15:42:05 -0700
Subject: [PATCH] fix: anticipate empty clusters when using newrank

When using newrank=true and incorrectly putting a node in two clusters, one of
the clusters would end up empty. This broke assumptions in the crossing logic;
e.g. that all clusters have a leader. We fix this by detecting empty clusters
and removing them prior to the crossing logic. Fixes #1221.
---
 CHANGELOG.md             |  1 +
 lib/dotgen/mincross.c    | 19 +++++++++++++++++++
 rtest/1221.dot           | 12 ++++++++++++
 rtest/test_regression.py | 13 +++++++++++++
 4 files changed, 45 insertions(+)
 create mode 100644 rtest/1221.dot

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 039283420..015ee5afd 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -63,6 +63,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - lefty PTY functionality relies on file descriptor implementation details #1823
 - buffer overflow in fdpgen
 - Crashes by VRML output when current directory is not writable #793
+- Segmentation fault when newrank=true #1221
 
 ## [2.44.1] - 2020-06-29
 
diff --git a/lib/dotgen/mincross.c b/lib/dotgen/mincross.c
index 8d9268daa..7fe6b9621 100644
--- a/lib/dotgen/mincross.c
+++ b/lib/dotgen/mincross.c
@@ -20,9 +20,11 @@
  */
 
 #include <assert.h>
+#include <cgraph/cgraph.h>
 #include <dotgen/dot.h>
 #include <limits.h>
 #include <stdlib.h>
+#include <string.h>
 
 /* #define DEBUG */
 #define MARK(v)		(ND_mark(v))
@@ -337,6 +339,23 @@ void dot_mincross(graph_t * g, int doBalance)
     int c, nc;
     char *s;
 
+    /* check whether malformed input has led to empty cluster that the crossing
+     * functions will not anticipate
+     */
+    {
+	size_t i;
+	for (i = 1; i <= (size_t)GD_n_cluster(g); ) {
+	    if (agfstnode(GD_clust(g)[i]) == NULL) {
+	      agwarningf("removing empty cluster\n");
+	      memmove(&GD_clust(g)[i], &GD_clust(g)[i + 1],
+	        ((size_t)GD_n_cluster(g) - i) * sizeof(GD_clust(g)[0]));
+	      --GD_n_cluster(g);
+	    } else {
+	      ++i;
+	    }
+	}
+    }
+
     init_mincross(g);
 
     for (nc = c = 0; c < GD_comp(g).size; c++) {
diff --git a/rtest/1221.dot b/rtest/1221.dot
new file mode 100644
index 000000000..b61d85568
--- /dev/null
+++ b/rtest/1221.dot
@@ -0,0 +1,12 @@
+digraph "Graph d718cbc6-5e20-4417-a41a-e1e380469dd2" {
+	graph [
+		newrank=true
+	];
+	subgraph "cluster_1" {
+		1;
+	}
+	subgraph "cluster_2" {
+		1
+	}
+}
+
diff --git a/rtest/test_regression.py b/rtest/test_regression.py
index 1a496ce94..f43312e86 100644
--- a/rtest/test_regression.py
+++ b/rtest/test_regression.py
@@ -122,6 +122,19 @@ def test_793():
     # Graphviz should not have caused a segfault
     assert p.returncode != -signal.SIGSEGV, 'Graphviz segfaulted'
 
+def test_1221():
+    '''
+    assigning a node to two clusters with newrank should not cause a crash
+    https://gitlab.com/graphviz/graphviz/-/issues/1221
+    '''
+
+    # locate our associated test case in this directory
+    input = os.path.join(os.path.dirname(__file__), '1221.dot')
+    assert os.path.exists(input), 'unexpectedly missing test case'
+
+    # process this with dot
+    subprocess.check_call(['dot', '-Tsvg', '-o', os.devnull, input])
+
 def test_1314():
     '''
     test that a large font size that produces an overflow in Pango is rejected
-- 
2.40.0