Improve performance of package list expansion

Adds a hash table to the package list expansion to avoid iterating over
the children of package nodes that have already been visited. Without
this, the expansion is exponential. For library sets with a high degree
of dependency, iteration over the tree with revisiting results, in
practice, in significant slow down at best and pkg-config failure due to
memory exhaustion at worst. The resulting algorithm is equivalent to a
topological sort.

16 files changed, 204 insertions, 20 deletions

diff --git a/check/Makefile.am b/check/Makefile.am
index d4000d8..f6d88e9 100644
--- a/check/Makefile.am
+++ b/check/Makefile.am
@@ -29,6 +29,7 @@ TESTS = \
 	check-relocatable \
 	check-variable-override \
 	check-variables \
+	check-dependencies \
 	$(NULL)
 
 EXTRA_DIST = \
@@ -102,4 +103,16 @@ EXTRA_DIST = \
 	pkgconfig/prefixdef-expanded.pc \
 	pcfiledir.pc \
 	variables.pc \
+	dependencies/a_dep_c.pc \
+	dependencies/b_dep_c.pc \
+	dependencies/c_dep.pc \
+	dependencies/d_dep_e_f.pc \
+	dependencies/d_dep_f_e.pc \
+	dependencies/e_dep_g_f.pc \
+	dependencies/f_dep_g.pc \
+	dependencies/g_dep.pc \
+	dependencies/h_dep_k_i_j.pc \
+	dependencies/i_dep_k_j.pc \
+	dependencies/j_dep_k.pc \
+	dependencies/k_dep.pc \
 	$(NULL)
diff --git a/check/check-dependencies b/check/check-dependencies
new file mode 100755
index 0000000..40472b5
--- /dev/null
+++ b/check/check-dependencies
@@ -0,0 +1,44 @@
+#! /bin/sh
+
+# These tests check the evaluation of the 'recursive_fill_list' function to
+# verify that for any package s that depends on t, that the library defined by
+# package s occurs before that of package t
+
+set -e
+
+. ${srcdir}/common
+
+export PKG_CONFIG_PATH
+PKG_CONFIG_PATH="${srcdir}/dependencies"
+
+# Shared dependency test.
+RESULT="-la_dep_c -lb_dep_c -lc_dep"
+run_test --libs a_dep_c b_dep_c
+run_test --libs c_dep a_dep_c b_dep_c
+run_test --libs a_dep_c c_dep b_dep_c
+run_test --libs a_dep_c b_dep_c c_dep
+
+# Redundancy test.
+#
+# Redundancy on the input line should not pass through.
+RESULT="-la_dep_c -lb_dep_c -lc_dep"
+run_test --libs a_dep_c a_dep_c b_dep_c
+run_test --libs b_dep_c a_dep_c b_dep_c
+
+# Diamond pattern test.
+#
+# One dependency of d depends on the other.
+# Both dependencies of d depend on g
+RESULT="-ld_dep_e_f -le_dep_g_f -lf_dep_g -lg_dep"
+run_test --libs d_dep_e_f
+RESULT="-ld_dep_f_e -le_dep_g_f -lf_dep_g -lg_dep"
+run_test --libs d_dep_f_e
+
+# Nested inclusion.
+#
+# Each package depends on all downsteam packages.
+RESULT="-lh_dep_k_i_j -li_dep_k_j -lj_dep_k -lk_dep"
+run_test --libs h_dep_k_i_j
+run_test --libs h_dep_k_i_j i_dep_k_j
+run_test --libs i_dep_k_j h_dep_k_i_j
+run_test --libs k_dep j_dep_k i_dep_k_j h_dep_k_i_j
diff --git a/check/dependencies/a_dep_c.pc b/check/dependencies/a_dep_c.pc
new file mode 100644
index 0000000..8d658b4
--- /dev/null
+++ b/check/dependencies/a_dep_c.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -la_dep_c
+Requires: c_dep
diff --git a/check/dependencies/b_dep_c.pc b/check/dependencies/b_dep_c.pc
new file mode 100644
index 0000000..c7625a4
--- /dev/null
+++ b/check/dependencies/b_dep_c.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -lb_dep_c
+Requires: c_dep
diff --git a/check/dependencies/c_dep.pc b/check/dependencies/c_dep.pc
new file mode 100644
index 0000000..67e2dfb
--- /dev/null
+++ b/check/dependencies/c_dep.pc
@@ -0,0 +1,9 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -lc_dep
diff --git a/check/dependencies/d_dep_e_f.pc b/check/dependencies/d_dep_e_f.pc
new file mode 100644
index 0000000..2e6a788
--- /dev/null
+++ b/check/dependencies/d_dep_e_f.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -ld_dep_e_f
+Requires: e_dep_g_f f_dep_g
diff --git a/check/dependencies/d_dep_f_e.pc b/check/dependencies/d_dep_f_e.pc
new file mode 100644
index 0000000..e7bb015
--- /dev/null
+++ b/check/dependencies/d_dep_f_e.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -ld_dep_f_e
+Requires: f_dep_g e_dep_g_f
diff --git a/check/dependencies/e_dep_g_f.pc b/check/dependencies/e_dep_g_f.pc
new file mode 100644
index 0000000..998f800
--- /dev/null
+++ b/check/dependencies/e_dep_g_f.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -le_dep_g_f
+Requires: f_dep_g g_dep
diff --git a/check/dependencies/f_dep_g.pc b/check/dependencies/f_dep_g.pc
new file mode 100644
index 0000000..268bb1e
--- /dev/null
+++ b/check/dependencies/f_dep_g.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -lf_dep_g
+Requires: g_dep
diff --git a/check/dependencies/g_dep.pc b/check/dependencies/g_dep.pc
new file mode 100644
index 0000000..9d17d3b
--- /dev/null
+++ b/check/dependencies/g_dep.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -lg_dep
+Requires:
diff --git a/check/dependencies/h_dep_k_i_j.pc b/check/dependencies/h_dep_k_i_j.pc
new file mode 100644
index 0000000..d29eb14
--- /dev/null
+++ b/check/dependencies/h_dep_k_i_j.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -lh_dep_k_i_j
+Requires: k_dep i_dep_k_j j_dep_k
diff --git a/check/dependencies/i_dep_k_j.pc b/check/dependencies/i_dep_k_j.pc
new file mode 100644
index 0000000..4aad8b1
--- /dev/null
+++ b/check/dependencies/i_dep_k_j.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -li_dep_k_j
+Requires: k_dep j_dep_k
diff --git a/check/dependencies/j_dep_k.pc b/check/dependencies/j_dep_k.pc
new file mode 100644
index 0000000..872e3da
--- /dev/null
+++ b/check/dependencies/j_dep_k.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -lj_dep_k
+Requires: k_dep
diff --git a/check/dependencies/k_dep.pc b/check/dependencies/k_dep.pc
new file mode 100644
index 0000000..45bc739
--- /dev/null
+++ b/check/dependencies/k_dep.pc
@@ -0,0 +1,10 @@
+prefix=/path2
+exec_prefix=${prefix}
+libdir="${exec_prefix}/lib"
+includedir="${prefix}/include"
+
+Name: Dependencies test.
+Description: Test package for testing dependency order.
+Version: 1.0.0
+Libs: -lk_dep
+Requires:
diff --git a/pkg.c b/pkg.c
index b439f44..da3b3f4 100644
--- a/pkg.c
+++ b/pkg.c
@@ -525,35 +525,44 @@ packages_sort_by_path_position (GList *list)
   return g_list_sort (list, pathposcmp);
 }
 
+/* Construct a topological sort of all required packages.
+ *
+ * This is a depth first search starting from the right.  The output 'listp' is
+ * in reverse order, with the first node reached in the depth first search at
+ * the end of the list.  Previously visited nodes are skipped.  The result is
+ * a list of packages such that each packages is listed once and comes before
+ * any package that it depends on.
+ */
 static void
-recursive_fill_list (Package *pkg, gboolean include_private, GList **listp)
+recursive_fill_list (Package *pkg, gboolean include_private,
+                     GHashTable *visited, GList **listp)
 {
   GList *tmp;
 
   /*
-   * If the package is one of the parents, we can skip it. This allows
-   * circular requires loops to be broken.
+   * If the package has already been visited, then it is already in 'listp' and
+   * we can skip it. Additionally, this allows circular requires loops to be
+   * broken.
    */
-  if (pkg->in_requires_chain)
+  if (g_hash_table_lookup_extended (visited, pkg->key, NULL, NULL))
     {
       debug_spew ("Package %s already in requires chain, skipping\n",
                   pkg->key);
       return;
     }
-
   /* record this package in the dependency chain */
-  pkg->in_requires_chain = TRUE;
+  else
+    {
+      g_hash_table_replace (visited, pkg->key, pkg->key);
+    }
 
   /* Start from the end of the required package list to maintain order since
    * the recursive list is built by prepending. */
   tmp = include_private ? pkg->requires_private : pkg->requires;
   for (tmp = g_list_last (tmp); tmp != NULL; tmp = g_list_previous (tmp))
-    recursive_fill_list (tmp->data, include_private, listp);
+    recursive_fill_list (tmp->data, include_private, visited, listp);
 
   *listp = g_list_prepend (*listp, pkg);
-
-  /* remove this package from the dependency chain now that we've unwound */
-  pkg->in_requires_chain = FALSE;
 }
 
 /* merge the flags from the individual packages */
@@ -634,18 +643,15 @@ fill_list (GList *packages, FlagType type,
   GList *tmp;
   GList *expanded = NULL;
   GList *flags;
+  GHashTable *visited;
 
   /* Start from the end of the requested package list to maintain order since
    * the recursive list is built by prepending. */
+  visited = g_hash_table_new (g_str_hash, g_str_equal);
   for (tmp = g_list_last (packages); tmp != NULL; tmp = g_list_previous (tmp))
-    recursive_fill_list (tmp->data, include_private, &expanded);
-
-  /* Remove duplicate packages from the recursive list. This should provide a
-   * serialized package list where all interdependencies are resolved
-   * consistently. */
-  spew_package_list (" pre-remove", expanded);
-  expanded = package_list_strip_duplicates (expanded);
-  spew_package_list ("post-remove", expanded);
+    recursive_fill_list (tmp->data, include_private, visited, &expanded);
+  g_hash_table_destroy (visited);
+  spew_package_list ("post-recurse", expanded);
 
   if (in_path_order)
     {
@@ -686,6 +692,7 @@ verify_package (Package *pkg)
   GList *requires_iter;
   GList *conflicts_iter;
   GList *system_dir_iter = NULL;
+  GHashTable *visited;
   int count;
   const gchar *search_path;
 
@@ -756,7 +763,9 @@ verify_package (Package *pkg)
   /* Make sure we didn't drag in any conflicts via Requires
    * (inefficient algorithm, who cares)
    */
-  recursive_fill_list (pkg, TRUE, &requires);
+  visited = g_hash_table_new (g_str_hash, g_str_equal);
+  recursive_fill_list (pkg, TRUE, visited, &requires);
+  g_hash_table_destroy (visited);
   conflicts = pkg->conflicts;
 
   requires_iter = requires;
diff --git a/pkg.h b/pkg.h
index c2e458a..13cc2c6 100644
--- a/pkg.h
+++ b/pkg.h
@@ -84,7 +84,6 @@ struct Package_
   int path_position; /* used to order packages by position in path of their .pc file, lower number means earlier in path */
   int libs_num; /* Number of times the "Libs" header has been seen */
   int libs_private_num;  /* Number of times the "Libs.private" header has been seen */
-  gboolean in_requires_chain; /* package is in current Requires chain */
   char *orig_prefix; /* original prefix value before redefinition */
 };