[postgis-tickets] r14508 - #3404, ST_ClusterWithin crashes backend

[Daniel Baston]

Author: dbaston
Date: 2015-12-20 13:43:11 -0800 (Sun, 20 Dec 2015)
New Revision: 14508

Modified:
   branches/2.2/
   branches/2.2/liblwgeom/cunit/cu_unionfind.c
   branches/2.2/liblwgeom/lwgeom_geos_cluster.c
   branches/2.2/liblwgeom/lwunionfind.c
Log:
#3404, ST_ClusterWithin crashes backend


Property changes on: branches/2.2
___________________________________________________________________
Modified: svn:mergeinfo
   - /branches/1.5:7092,7136,7138,7460
/spike/pramsey/geodetic:4288-4493
/trunk:14474
   + /branches/1.5:7092,7136,7138,7460
/spike/pramsey/geodetic:4288-4493
/trunk:14474,14507

Modified: branches/2.2/liblwgeom/cunit/cu_unionfind.c
===================================================================
--- branches/2.2/liblwgeom/cunit/cu_unionfind.c	2015-12-20 21:29:38 UTC (rev 14507)
+++ branches/2.2/liblwgeom/cunit/cu_unionfind.c	2015-12-20 21:43:11 UTC (rev 14508)
@@ -87,6 +87,29 @@
 	lwfree(ids_by_cluster);
 }
 
+static void test_unionfind_path_compression(void)
+{
+	UNIONFIND* uf = UF_create(5);
+	uint32_t i;
+
+	uf->clusters[1] = 0;
+	uf->clusters[2] = 1;
+	uf->clusters[3] = 2;
+	uf->clusters[4] = 3;
+
+	/* Calling "find" on a leaf should attach all nodes between the root and the
+	 * leaf directly to the root. */
+	uint32_t root = UF_find(uf, 4);
+	for (i = 0; i < uf->N; i++)
+	{
+		/* Verify that all cluster references have been updated to point
+		 * directly to the root. */
+		CU_ASSERT_EQUAL(root, uf->clusters[i]);
+	}
+
+	UF_destroy(uf);
+}
+
 void unionfind_suite_setup(void);
 void unionfind_suite_setup(void)
 {
@@ -94,4 +117,5 @@
 	PG_ADD_TEST(suite, test_unionfind_create);
 	PG_ADD_TEST(suite, test_unionfind_union);
 	PG_ADD_TEST(suite, test_unionfind_ordered_by_cluster);
+	PG_ADD_TEST(suite, test_unionfind_path_compression);
 }

Modified: branches/2.2/liblwgeom/lwgeom_geos_cluster.c
===================================================================
--- branches/2.2/liblwgeom/lwgeom_geos_cluster.c	2015-12-20 21:29:38 UTC (rev 14507)
+++ branches/2.2/liblwgeom/lwgeom_geos_cluster.c	2015-12-20 21:43:11 UTC (rev 14508)
@@ -336,10 +336,15 @@
 		if ((i == num_geoms - 1) ||
 		        (UF_find(uf, ordered_components[i]) != UF_find(uf, ordered_components[i+1])))
 		{
+			if (k >= uf->num_clusters) {
+				/* Should not get here - it means that we have more clusters than uf->num_clusters thinks we should. */
+				return LW_FAILURE;
+			}
+
 			if (is_lwgeom)
 			{
-				LWGEOM** components = lwalloc(num_geoms * sizeof(LWGEOM*));
-				memcpy(components, geoms_in_cluster, num_geoms * sizeof(LWGEOM*));
+				LWGEOM** components = lwalloc(j * sizeof(LWGEOM*));
+				memcpy(components, geoms_in_cluster, j * sizeof(LWGEOM*));
 				(*clusterGeoms)[k++] = lwcollection_construct(COLLECTIONTYPE, components[0]->srid, NULL, j, (LWGEOM**) components);
 			}
 			else

Modified: branches/2.2/liblwgeom/lwunionfind.c
===================================================================
--- branches/2.2/liblwgeom/lwunionfind.c	2015-12-20 21:29:38 UTC (rev 14507)
+++ branches/2.2/liblwgeom/lwunionfind.c	2015-12-20 21:43:11 UTC (rev 14508)
@@ -47,11 +47,17 @@
 uint32_t
 UF_find (UNIONFIND* uf, uint32_t i)
 {
-	while (uf->clusters[i] != i)
-	{
-		uf->clusters[i] = uf->clusters[uf->clusters[i]];
-		i = uf->clusters[i];
+	uint32_t base = i;
+	while (uf->clusters[base] != base) {
+		base = uf->clusters[base];
 	}
+
+	while (i != base) {
+		uint32_t next = uf->clusters[i];
+		uf->clusters[i] = base;
+		i = next;
+	}
+
 	return i;
 }