diff options
| -rw-r--r-- | check/Makefile.am | 13 | ||||
| -rwxr-xr-x | check/check-dependencies | 44 | ||||
| -rw-r--r-- | check/dependencies/a_dep_c.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/b_dep_c.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/c_dep.pc | 9 | ||||
| -rw-r--r-- | check/dependencies/d_dep_e_f.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/d_dep_f_e.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/e_dep_g_f.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/f_dep_g.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/g_dep.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/h_dep_k_i_j.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/i_dep_k_j.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/j_dep_k.pc | 10 | ||||
| -rw-r--r-- | check/dependencies/k_dep.pc | 10 | ||||
| -rw-r--r-- | pkg.c | 47 | ||||
| -rw-r--r-- | pkg.h | 1 |
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: @@ -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; @@ -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 */ }; |