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.

14 files changed, 176 insertions, 0 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: