[PATCH] Repeat packages to satisfy link line cycles.
yvvaibhav at gmail.com
yvvaibhav at gmail.com
Tue Jan 22 20:22:31 UTC 2019
From: Vaibhav Yenamandra <vyenamandra at bloomberg.net>
We add support for a new flag '--static-link-multiplicity' and an
optional Package property 'StaticLinkMultiplicity' both of which default
to 1 if unspecified. The two additions allow for packages to specify the
number of times they must be repeated on the link line if they are part of a
linker dependency cycle.
Prior to this change, pkg-config broke cycles by ignoring the already
visited nodes while topologically sorting package dependency chains.
While this was an improvement over older version of pkg-config, it
doesn't satisfy the requirement that with static linking, if package A
depends on package B, package B's linker flag should appear at least
once after package A's linker flags. Therefore, the current behavior
of pkg-config is actually guaranteed to produce a broken link line in
the presence of cycles.
The new flags added shall behave as follows:
* On the absence of cycles, the behavior shall remain the same
* Otherwise, pkg-config will repeat linker flags at least once to
satisfy cycles. This is new behaviour.
The new behaviour is outlined as follows:
* A package's link multiplicity is set to 1 by default.
* The --static-link-multiplicty command line argument as well as the
StaticLinkMultiplicity package property can be used to change that
default.
* The link multiplicity will be ignored unless both '--libs' and
'--static' are passed on the command line.
* A cycle's link multiplicity is the largest multiplicity of all
individual packages in the cycle and the value passed through
'--static-link-multiplicity'
* Any link multiplicity can be a maximum of 255
* The linker flags will be repeated in the same order as they were
linearized in the topological sort, for as many times as the value
of the link multiplicty for the cycle.
Implementation notes:
This implementation builds on the existing topological sort
implemented by `pkg-config`. The gist being that cycles are
effectively 'back edges' encountered while traversing each package's
requirements in a post processing step.
A back edge is identified by traversing the topologically-sorted
list of packages, and identifying when a package has a requires that
was sorted earlier than itself.
---
check/Makefile.am | 13 +
check/check-multiplicity | 139 ++++++++++
check/multiplicity/pc-files/circ1.pc | 12 +
check/multiplicity/pc-files/circ2.pc | 12 +
check/multiplicity/pc-files/circ3.pc | 12 +
check/multiplicity/pc-files/head-0.pc | 12 +
check/multiplicity/pc-files/head-1.pc | 12 +
check/multiplicity/pc-files/line0.pc | 12 +
check/multiplicity/pc-files/line1.pc | 12 +
check/multiplicity/pc-files/line2.pc | 12 +
check/multiplicity/pc-files/line3.pc | 11 +
check/multiplicity/pc-files/tail-cycle-1.pc | 12 +
check/multiplicity/pc-files/tail-cycle-2.pc | 12 +
check/multiplicity/pc-files/tail-cycle-3.pc | 12 +
main.c | 12 +
parse.c | 53 +++-
pkg.c | 268 +++++++++++++++++++-
pkg.h | 37 ++-
18 files changed, 655 insertions(+), 10 deletions(-)
create mode 100755 check/check-multiplicity
create mode 100644 check/multiplicity/pc-files/circ1.pc
create mode 100644 check/multiplicity/pc-files/circ2.pc
create mode 100644 check/multiplicity/pc-files/circ3.pc
create mode 100644 check/multiplicity/pc-files/head-0.pc
create mode 100644 check/multiplicity/pc-files/head-1.pc
create mode 100644 check/multiplicity/pc-files/line0.pc
create mode 100644 check/multiplicity/pc-files/line1.pc
create mode 100644 check/multiplicity/pc-files/line2.pc
create mode 100644 check/multiplicity/pc-files/line3.pc
create mode 100644 check/multiplicity/pc-files/tail-cycle-1.pc
create mode 100644 check/multiplicity/pc-files/tail-cycle-2.pc
create mode 100644 check/multiplicity/pc-files/tail-cycle-3.pc
diff --git a/check/Makefile.am b/check/Makefile.am
index 68c6d84..1186358 100644
--- a/check/Makefile.am
+++ b/check/Makefile.am
@@ -31,6 +31,7 @@ TESTS = \
check-variables \
check-dependencies \
check-system-flags \
+ check-multiplicity \
$(NULL)
EXTRA_DIST = \
@@ -118,4 +119,16 @@ EXTRA_DIST = \
dependencies/j_dep_k.pc \
dependencies/k_dep.pc \
system.pc \
+ multiplicity/pc-files/circ1 \
+ multiplicity/pc-files/circ2 \
+ multiplicity/pc-files/circ3 \
+ multiplicity/pc-files/head-0 \
+ multiplicity/pc-files/head-1 \
+ multiplicity/pc-files/line0 \
+ multiplicity/pc-files/line1 \
+ multiplicity/pc-files/line2 \
+ multiplicity/pc-files/line3 \
+ multiplicity/pc-files/tail-cycle-1 \
+ multiplicity/pc-files/tail-cycle-2 \
+ multiplicity/pc-files/tail-cycle-3 \
$(NULL)
diff --git a/check/check-multiplicity b/check/check-multiplicity
new file mode 100755
index 0000000..d772454
--- /dev/null
+++ b/check/check-multiplicity
@@ -0,0 +1,139 @@
+#! /bin/sh
+
+
+# By default, circular dependencies are linearized by breaking the 'last edge'
+# and are not repeated on the link line if `--static` wasn't provided.
+# However, providing `--static` on the command-line enables component detection
+# which bundles groups of packages into 'components' each of which contains
+# at most 1 strongly connected component. A trivial component consists of a
+# single pc file.
+#
+# Link multiplicity comes with the following properties:
+# 1. Choosing not to provide the link multiplicity flag or property results in
+# behaviour that is backwards compatible.
+#
+
+set -e
+
+. ${srcdir}/common
+
+# Behaviour prior to implementing support for link multiplicity:
+# Traverse the graph depth first, and break the `last`edge in the cycle when
+# traversed in depth-first order, in order to transform it into a DAG. This is
+# the same as defaulting link multiplicity to 1.
+#
+# All dependency graphs use arrows to show the "Requires" relation.
+
+# The relationships above can be visualized through the following
+# graphviz directed graph:
+# digraph G {
+# "circ1" -> "circ3"
+# "circ2" -> "circ1"
+# "circ3" -> "circ2"
+# "circ3" -> "circ1"
+# "circ3" -> "line1"
+# "line0" -> "circ1"
+# "line1" -> "line2"
+# "line2" -> "line3"
+# }
+export PKG_CONFIG_PATH
+
+# Link multiplicity does not affect data in CFlags
+PKG_CONFIG_PATH="${srcdir}/multiplicity/pc-files"
+RESULT="-I/usr/include/circ -I/usr/include/circ-alt -I/usr/include/line"
+run_test --cflags circ1
+
+# Link multiplicity doesn't affect link line unless used with --static
+RESULT="-lcirc1 -lcirc3 -lcirc2 -lline1 -lline2 -lline3"
+run_test --libs circ1
+
+# When --static is used, the largest multiplicity of all packages from a non
+# trivial component used for that component.
+# i.e:
+# If a package has a stated StaticLinkMultiplicity, but doesn't participate
+# in a cycle, its StaticLinkMultiplicity is ignored for repeating elements
+# on the link line.
+RESULT="-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lline1 -lline2 -lline3"
+run_test --libs --static circ1
+
+# When --static is used, and --static-link-multiplicity is used, its value
+# only have an effect on the link line of a 'component' if it is larger than
+# the components link multiplicity.
+RESULT="-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lline1 -lline2 -lline3"
+run_test --libs --static --static-link-multiplicity=1 circ1
+
+RESULT="-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lline1 -lline2 -lline3"
+run_test --libs --static --static-link-multiplicity=3 circ1
+
+# The next set tests the behaviour of pkg-config if the component is not
+# at the extremeties of the package graph
+RESULT="-lline0 -lcirc1 -lcirc3 -lcirc2 -lline1 -lline2 -lline3"
+run_test --libs line0
+
+RESULT="-lline0 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lline1 -lline2 -lline3"
+run_test --libs --static line0
+
+RESULT="-lline0 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lcirc1 -lcirc3 -lcirc2 \
+-lline1 -lline2 -lline3"
+run_test --libs --static --static-link-multiplicity=3 line0
+
+# This next set of tests examines the code for the case when the components
+# at the end of the dependency graph
+RESULT="-I/usr/include/tail-cycle-0 -I/usr/include/tail-cycle"
+run_test --cflags head-0
+
+
+RESULT="-lhead-0 -lhead-1 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2"
+run_test --libs head-0
+
+# Dependency graph for the packages that follow:
+# digraph G {
+# "tail-cycle-1" -> "tail-cycle-2"
+# "tail-cycle-1" -> "tail-cycle-3"
+# "tail-cycle-2" -> "tail-cycle-1"
+# "tail-cycle-2" -> "tail-cycle-3"
+# "tail-cycle-3" -> "tail-cycle-1"
+# "tail-cycle-3" -> "tail-cycle-2"
+# "head-0" -> "head-1"
+# "head-1" -> "tail-cycle-1"
+# }
+
+# Repetition with the --static flag
+RESULT="-lhead-0 -lhead-1 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2"
+run_test --static --libs head-0
+
+# Overriding link multiplicity with with --static-link-multiplicity
+RESULT="-lhead-0 -lhead-1 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2"
+run_test --static --static-link-multiplicity=1 --libs head-0
+
+RESULT="-lhead-0 -lhead-1 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2 \
+-ltail-cycle-1 -ltail-cycle-3 -ltail-cycle-2"
+run_test --static --static-link-multiplicity=3 --libs head-0
diff --git a/check/multiplicity/pc-files/circ1.pc b/check/multiplicity/pc-files/circ1.pc
new file mode 100644
index 0000000..05b5c04
--- /dev/null
+++ b/check/multiplicity/pc-files/circ1.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/circ
+
+Name: Link Multiplicity Test File 1
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: circ3
+Libs: -L${libdir} -lcirc1
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 1
diff --git a/check/multiplicity/pc-files/circ2.pc b/check/multiplicity/pc-files/circ2.pc
new file mode 100644
index 0000000..265569a
--- /dev/null
+++ b/check/multiplicity/pc-files/circ2.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/circ-alt
+
+Name: Link Multiplicity Test File 2
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: circ1
+Libs: -L${libdir} -lcirc2
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 1
diff --git a/check/multiplicity/pc-files/circ3.pc b/check/multiplicity/pc-files/circ3.pc
new file mode 100644
index 0000000..474dc14
--- /dev/null
+++ b/check/multiplicity/pc-files/circ3.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/circ
+
+Name: Link Multiplicity Test File 3
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: circ1 circ2 line1
+Libs: -L${libdir} -lcirc3
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 2
diff --git a/check/multiplicity/pc-files/head-0.pc b/check/multiplicity/pc-files/head-0.pc
new file mode 100644
index 0000000..2361c6a
--- /dev/null
+++ b/check/multiplicity/pc-files/head-0.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/tail-cycle-0
+
+Name: Link Multiplicity Test File 0
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: head-1
+Libs: -L${libdir} -lhead-0
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 1
diff --git a/check/multiplicity/pc-files/head-1.pc b/check/multiplicity/pc-files/head-1.pc
new file mode 100644
index 0000000..0cb688d
--- /dev/null
+++ b/check/multiplicity/pc-files/head-1.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/tail-cycle-0
+
+Name: Link Multiplicity Test File 0
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: tail-cycle-1
+Libs: -L${libdir} -lhead-1
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 1
diff --git a/check/multiplicity/pc-files/line0.pc b/check/multiplicity/pc-files/line0.pc
new file mode 100644
index 0000000..4736864
--- /dev/null
+++ b/check/multiplicity/pc-files/line0.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/line
+
+Name: Link Multiplicity Test File 0
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: circ1
+Libs: -L${libdir} -lline0
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 1
diff --git a/check/multiplicity/pc-files/line1.pc b/check/multiplicity/pc-files/line1.pc
new file mode 100644
index 0000000..dc43ca2
--- /dev/null
+++ b/check/multiplicity/pc-files/line1.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/line
+
+Name: Link Multiplicity Test File 4
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: line2
+Libs: -L${libdir} -lline1
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 3
diff --git a/check/multiplicity/pc-files/line2.pc b/check/multiplicity/pc-files/line2.pc
new file mode 100644
index 0000000..a1a25af
--- /dev/null
+++ b/check/multiplicity/pc-files/line2.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/line
+
+Name: Link Multiplicity Test File 5
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: line3
+Libs: -L${libdir} -lline2
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 3
diff --git a/check/multiplicity/pc-files/line3.pc b/check/multiplicity/pc-files/line3.pc
new file mode 100644
index 0000000..38459f8
--- /dev/null
+++ b/check/multiplicity/pc-files/line3.pc
@@ -0,0 +1,11 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/line
+
+Name: Link Multiplicity Test File 6
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Libs: -L${libdir} -lline3
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 3
diff --git a/check/multiplicity/pc-files/tail-cycle-1.pc b/check/multiplicity/pc-files/tail-cycle-1.pc
new file mode 100644
index 0000000..f928a92
--- /dev/null
+++ b/check/multiplicity/pc-files/tail-cycle-1.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/tail-cycle
+
+Name: Link Multiplicity Test File 7
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: tail-cycle-2 tail-cycle-3
+Libs: -L${libdir} -ltail-cycle-1
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 1
diff --git a/check/multiplicity/pc-files/tail-cycle-2.pc b/check/multiplicity/pc-files/tail-cycle-2.pc
new file mode 100644
index 0000000..141e6be
--- /dev/null
+++ b/check/multiplicity/pc-files/tail-cycle-2.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/tail-cycle
+
+Name: Link Multiplicity Test File 8
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: tail-cycle-3 tail-cycle-1
+Libs: -L${libdir} -ltail-cycle-2
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 1
diff --git a/check/multiplicity/pc-files/tail-cycle-3.pc b/check/multiplicity/pc-files/tail-cycle-3.pc
new file mode 100644
index 0000000..09e13a8
--- /dev/null
+++ b/check/multiplicity/pc-files/tail-cycle-3.pc
@@ -0,0 +1,12 @@
+prefix=/usr
+exec_prefix=${prefix}
+libdir=${exec_prefix}/lib
+includedir=${prefix}/include/tail-cycle
+
+Name: Link Multiplicity Test File 9
+Description: Dummy package for testing link multiplicity
+Version: 1.0.0
+Requires: tail-cycle-1 tail-cycle-2
+Libs: -L${libdir} -ltail-cycle-3
+Cflags: -I${includedir}
+StaticLinkMultiplicity: 2
diff --git a/main.c b/main.c
index 9b27d9a..31d33a3 100644
--- a/main.c
+++ b/main.c
@@ -250,6 +250,8 @@ output_opt_cb (const char *opt, const char *arg, gpointer data,
want_requires_private = TRUE;
else if (strcmp (opt, "--validate") == 0)
want_validate = TRUE;
+ else if (strcmp (opt, "--static-link-multiplicity") == 0)
+ want_validate = TRUE;
else
return FALSE;
@@ -475,6 +477,10 @@ static const GOptionEntry options_table[] = {
{ "prefix-variable", 0, 0, G_OPTION_ARG_STRING, &prefix_variable,
"set the name of the variable that pkg-config automatically sets",
"PREFIX" },
+ { "static-link-multiplicity", 0, 0, G_OPTION_ARG_INT, &link_multiplicity,
+ "Maximum number of times an archive can be repeated on the link line to "
+ "satisfy cyclic link dependencies of a static target. Supports values "
+ "up to 255", "COUNT" },
#ifdef G_OS_WIN32
{ "msvc-syntax", 0, 0, G_OPTION_ARG_NONE, &msvc_syntax,
"output -l and -L flags for the Microsoft compiler (cl)", NULL },
@@ -642,6 +648,12 @@ main (int argc, char **argv)
else
return 1;
}
+ if (link_multiplicity > UINT8_MAX)
+ {
+ verbose_error ("Link multiplicity larger than %u is unsupported\n",
+ UINT8_MAX);
+ return 1;
+ }
package_init (want_list);
diff --git a/parse.c b/parse.c
index 6e9907c..eb03023 100644
--- a/parse.c
+++ b/parse.c
@@ -37,6 +37,7 @@
gboolean parse_strict = TRUE;
gboolean define_prefix = ENABLE_DEFINE_PREFIX;
char *prefix_variable = "prefix";
+uint32_t link_multiplicity = 1;
#ifdef G_OS_WIN32
gboolean msvc_syntax = FALSE;
@@ -904,6 +905,45 @@ parse_url (Package *pkg, const char *str, const char *path)
pkg->url = trim_and_sub (pkg, str, path);
}
+static void
+parse_link_multiplicity (Package *pkg, const char *str, const char *path)
+{
+ if (pkg->link_multiplicity != C_LINK_MULTIPLICITY_UNINITIALIZED)
+ {
+ verbose_error ("StaticLinkMultiplicity field occurs twice in '%s'\n",
+ path);
+ if (parse_strict)
+ exit (1);
+ else
+ return;
+ }
+
+ char *strnum = trim_and_sub (pkg, str, path);
+ /* Force fatal errors on negative, zero values,
+ * regardless of strict parsing */
+ if ('-' == *strnum || '0' == *strnum)
+ {
+ verbose_error ("StaticLinkMultiplicity must be a postive value. "
+ "Parsed: %s", strnum);
+ exit (1);
+ }
+
+ gchar* end_of_data = strnum;
+ /* strnum is not a null terminated string. Find the end by hand to use with
+ * glib */
+ while (g_ascii_isdigit(*(end_of_data + 1)))
+ {
+ ++end_of_data;
+ }
+ uint64_t parsed_num = g_ascii_strtoull (strnum, &end_of_data, 10);
+ if(parsed_num > UINT8_MAX)
+ {
+ verbose_error ("StaticLinkMultiplicity is at most 255. "
+ "Parsed: %ull", parsed_num);
+ }
+ pkg->link_multiplicity = (uint8_t) parsed_num;
+}
+
static void
parse_line (Package *pkg, const char *untrimmed, const char *path,
gboolean ignore_requires, gboolean ignore_private_libs,
@@ -976,6 +1016,8 @@ parse_line (Package *pkg, const char *untrimmed, const char *path,
parse_conflicts (pkg, p, path);
else if (strcmp (tag, "URL") == 0)
parse_url (pkg, p, path);
+ else if (strcmp (tag, "StaticLinkMultiplicity") == 0)
+ parse_link_multiplicity (pkg, p, path);
else
{
/* we don't error out on unknown keywords because they may
@@ -1110,6 +1152,9 @@ parse_package_file (const char *key, const char *path,
pkg = g_new0 (Package, 1);
pkg->key = g_strdup (key);
+ pkg->link_multiplicity = C_LINK_MULTIPLICITY_UNINITIALIZED;
+ pkg->cycle_edge_destination_count = 0;
+ pkg->cycle_edge_source_count = 0;
if (path)
{
@@ -1147,7 +1192,13 @@ parse_package_file (const char *key, const char *path,
pkg->cflags = g_list_reverse (pkg->cflags);
pkg->libs = g_list_reverse (pkg->libs);
-
+
+ /* Ensure that link multiplicity defaults to 1 if not specified */
+ if (C_LINK_MULTIPLICITY_UNINITIALIZED == pkg->link_multiplicity)
+ {
+ pkg->link_multiplicity = C_LINK_MULTIPLICITY_DEFAULT;
+ }
+
return pkg;
}
diff --git a/pkg.c b/pkg.c
index f29ecc7..0a23c5b 100644
--- a/pkg.c
+++ b/pkg.c
@@ -51,6 +51,21 @@ gboolean ignore_requires = FALSE;
gboolean ignore_requires_private = TRUE;
gboolean ignore_private_libs = TRUE;
+static void
+print_package(gpointer pkg_, gpointer prefix)
+{
+ Package *pkg = pkg_;
+ debug_spew ("%sPackage{%s, U: %d, D: %d, LM: %d}\n",
+ (char *) prefix, pkg->key, pkg->cycle_edge_source_count,
+ pkg->cycle_edge_destination_count, pkg->link_multiplicity);
+}
+
+static void
+free_component(gpointer component_ptr)
+{
+ g_free (component_ptr);
+}
+
void
add_search_dir (const char *path)
{
@@ -541,6 +556,153 @@ recursive_fill_list (Package *pkg, gboolean include_private,
*listp = g_list_prepend (*listp, pkg);
}
+static void print_component(gpointer component, gpointer line_prefix)
+{
+ Component* c = component;
+ char *start = c->start ? ((Package*) c->start->data)->key : "NULL";
+ char *end = c->end ? ((Package*) c->end->data)->key : "NULL";
+ debug_spew ("%sComponent{start: %s, end: %s}\n",
+ (char *) line_prefix, start, end);
+}
+
+static GList* get_components(GList* packages)
+{
+ GList *components = NULL;
+ int cycle_tally = 0;
+ GList *start = NULL;
+ GList *last = NULL;
+ gboolean cycle_seen = FALSE;
+
+ /* Detect cycles in the dependency chain by finding the smallest dep index
+ * for each pacakge. A cycle occurs if any of its requires does not occur
+ * after the package. */
+ GHashTable *earliest_dep = g_hash_table_new(g_str_hash, g_str_equal);
+ GHashTable *pkg_index = g_hash_table_new(g_str_hash, g_str_equal);
+
+ int num_pkgs = g_list_length (packages);
+ int curr_idx = 0;
+
+ /* Containers to hold data referenced by value pointers passed to pkg_index,
+ * earliest_dep respectively.
+ * - indices is an array containing the integer index of each package
+ * - min_dep_idx records the smallest index from a package's requires*/
+ int *indices = g_new0(int, num_pkgs);
+ int *min_dep_idx = g_new(int, num_pkgs);
+
+ /* Default values for smallest dep index, since we only want positive values
+ * when there are cycles */
+ for(int idx = 0; idx < num_pkgs; ++idx)
+ {
+ min_dep_idx[idx] = -1;
+ }
+
+ /* Pre-process to load the index of each key into a table */
+ for (GList *pkg_it = packages; pkg_it != NULL; pkg_it = g_list_next (pkg_it))
+ {
+ indices[curr_idx] = curr_idx;
+ Package *pkg = pkg_it->data;
+ g_hash_table_replace (pkg_index, pkg->key, &indices[curr_idx]);
+ ++curr_idx;
+ }
+
+ /*
+ * Find the index of smallest dependency for each package and
+ * record back edges
+ */
+ curr_idx = 0;
+ for (GList *pkg_it = packages; pkg_it != NULL; pkg_it = g_list_next (pkg_it))
+ {
+ Package *pkg = pkg_it->data;
+ g_hash_table_insert (earliest_dep, pkg->key, &min_dep_idx[curr_idx]);
+ int curr_idx = *( (int *) g_hash_table_lookup (pkg_index, pkg->key));
+
+ for (GList* req_it = pkg->requires_private; req_it != NULL;
+ req_it = g_list_next(req_it))
+ {
+ Package *req = req_it->data;
+ int ridx = *( (int *) g_hash_table_lookup (pkg_index, req->key));
+
+ /*
+ * Back-edges are identified by looking at items in the requires
+ * list that were sorted before the current package, i.e. their
+ * DFS discovery time was earlier than this package's discovery time
+ */
+ if (ridx < curr_idx)
+ {
+ min_dep_idx[curr_idx] = ridx;
+ g_hash_table_replace (earliest_dep,
+ pkg->key, &min_dep_idx[curr_idx]);
+ pkg->cycle_edge_source_count += 1;
+ req->cycle_edge_destination_count += 1;
+ }
+ }
+ ++curr_idx;
+ }
+
+ debug_spew ("List of packages with cycle meta-data:\n");
+ g_list_foreach (packages, print_package, " ");
+
+ /* Once cycles are found, use the count information to group packages into
+ * components */
+ for (GList *pkg_it = packages; pkg_it != NULL; pkg_it = g_list_next (pkg_it))
+ {
+ Package *curr = pkg_it->data;
+ start = start ? start : pkg_it;
+
+ /* First ensure this isn't a trivial component */
+ if (curr->cycle_edge_destination_count == 0
+ && curr->cycle_edge_source_count == 0
+ && cycle_tally == 0)
+ {
+ Component *c = g_new0 (Component, 1);
+ c->start = start;
+ c->end = start->next;
+ c->multiplicity = 1;
+ start = c->end;
+ components = g_list_prepend (components, c);
+ }
+ else
+ {
+ Package* prev = pkg_it->prev ? pkg_it->prev->data : NULL;
+ cycle_tally += curr->cycle_edge_destination_count;
+ cycle_tally -= prev ? prev->cycle_edge_source_count : 0;
+ cycle_seen = TRUE;
+
+ if (cycle_tally == 0)
+ {
+ Component *c = g_new0 (Component, 1);
+ c->start = start;
+ c->end = start == pkg_it ? pkg_it->next : pkg_it;
+ c->multiplicity = 1;
+ start = c->end;
+ components = g_list_prepend (components, c);
+ }
+ }
+ last = pkg_it;
+ }
+ /* Last package*/
+ if (cycle_seen)
+ {
+ Component *c = g_new0 (Component, 1);
+ c->start = ((Component *) components->data)->end;
+ c->end = last->next;
+ c->multiplicity = 1;
+ components = g_list_prepend (components, c);
+ }
+
+ /* Reverse them to match dependency order since we inserted by
+ * prepending */
+ components = g_list_reverse (components);
+ debug_spew ("Identified components:\n");
+ g_list_foreach (components, &print_component, " ");
+ g_hash_table_destroy (pkg_index);
+ g_hash_table_destroy (earliest_dep);
+ g_free(indices);
+ g_free(min_dep_idx);
+
+ return components;
+}
+
/* merge the flags from the individual packages */
static GList *
merge_flag_lists (GList *packages, FlagType type)
@@ -575,9 +737,92 @@ merge_flag_lists (GList *packages, FlagType type)
return merged;
}
+/* merge the flags from the individual packages, incorporating cycles if
+ * necessary
+ */
+static GList *
+merge_flag_lists_by_component (GList *packages, FlagType type,
+ gboolean repeat_cycles)
+{
+ if (repeat_cycles)
+ {
+ GList *merged = NULL;
+ GList *components = NULL;
+
+ debug_spew ("Merging flags by component\n");
+ components = get_components (packages);
+ for (; components != NULL; components = g_list_next (components))
+ {
+ uint8_t max_mult = 1;
+ Component* c = components->data;
+ GList *dashl = NULL;
+ gboolean non_trivial_component = c->start->next != c->end;
+ if (non_trivial_component)
+ {
+ debug_spew ("Reading non-trivial component: ");
+ }
+ else
+ {
+ debug_spew ("Reading trivial component: ");
+ }
+ print_component (c, "");
+
+ for (GList* begin = c->start;
+ begin != c->end;
+ begin = g_list_next (begin))
+ {
+ Package* pkg = begin->data;
+ print_package (pkg, " ");
+ GList *flags = (type & LIBS_ANY) ? pkg->libs : pkg->cflags;
+ max_mult = MAX (max_mult, pkg->link_multiplicity);
+
+ /* manually copy the elements so we can keep track of the end.
+ * This code is duplicated to avoid the quadratic cost
+ * involved in finding the last element for every component chunk.
+ *
+ * SEE: merge_flag_lists(GList *packages, FlagType type)
+ */
+ for (; flags != NULL; flags = g_list_next (flags))
+ {
+ Flag *flag = flags->data;
+
+ if (flag->type & type)
+ {
+ dashl = g_list_append(dashl, flag);
+ }
+ }
+ }
+ c->multiplicity = MAX (link_multiplicity, max_mult);
+ c->multiplicity += non_trivial_component ? 1 : 0;
+
+ /* For non-trivial */
+
+ /* This is only done for flags matching the mask
+ * (LIBS_l | LIBS_OTHER) */
+ if (type & LIBS_ANY)
+ {
+ /* Inclusive upper bound, since multiplicity is the number of
+ * times we repeat a package. */
+ for (int i = 0; i < c->multiplicity; ++i)
+ {
+ GList *dashlc = g_list_copy(dashl);
+ merged = g_list_concat(merged, dashlc);
+ }
+ }
+ }
+ g_list_free_full (components, free_component);
+ return merged;
+ }
+ else
+ {
+ return merge_flag_lists (packages, type);
+ }
+}
+
static GList *
fill_list (GList *packages, FlagType type,
- gboolean in_path_order, gboolean include_private)
+ gboolean in_path_order, gboolean include_private,
+ gboolean capture_cycles)
{
GList *tmp;
GList *expanded = NULL;
@@ -589,6 +834,7 @@ fill_list (GList *packages, FlagType type,
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, visited, &expanded);
+
g_hash_table_destroy (visited);
spew_package_list ("post-recurse", expanded);
@@ -599,7 +845,7 @@ fill_list (GList *packages, FlagType type,
spew_package_list (" sorted", expanded);
}
- flags = merge_flag_lists (expanded, type);
+ flags = merge_flag_lists_by_component (expanded, type, capture_cycles);
g_list_free (expanded);
return flags;
@@ -912,12 +1158,16 @@ verify_package (Package *pkg)
*/
static char *
get_multi_merged (GList *pkgs, FlagType type, gboolean in_path_order,
- gboolean include_private)
+ gboolean include_private, gboolean capture_cycles)
{
GList *list;
char *retval;
- list = fill_list (pkgs, type, in_path_order, include_private);
+ list = fill_list (pkgs,
+ type,
+ in_path_order,
+ include_private,
+ capture_cycles);
list = flag_list_strip_duplicates (list);
retval = flag_list_to_string (list);
g_list_free (list);
@@ -936,21 +1186,21 @@ packages_get_flags (GList *pkgs, FlagType flags)
/* sort packages in path order for -L/-I, dependency order otherwise */
if (flags & CFLAGS_OTHER)
{
- cur = get_multi_merged (pkgs, CFLAGS_OTHER, FALSE, TRUE);
+ cur = get_multi_merged (pkgs, CFLAGS_OTHER, FALSE, TRUE, FALSE);
debug_spew ("adding CFLAGS_OTHER string \"%s\"\n", cur);
g_string_append (str, cur);
g_free (cur);
}
if (flags & CFLAGS_I)
{
- cur = get_multi_merged (pkgs, CFLAGS_I, TRUE, TRUE);
+ cur = get_multi_merged (pkgs, CFLAGS_I, TRUE, TRUE, FALSE);
debug_spew ("adding CFLAGS_I string \"%s\"\n", cur);
g_string_append (str, cur);
g_free (cur);
}
if (flags & LIBS_L)
{
- cur = get_multi_merged (pkgs, LIBS_L, TRUE, !ignore_private_libs);
+ cur = get_multi_merged (pkgs, LIBS_L, TRUE, !ignore_private_libs, FALSE);
debug_spew ("adding LIBS_L string \"%s\"\n", cur);
g_string_append (str, cur);
g_free (cur);
@@ -958,7 +1208,9 @@ packages_get_flags (GList *pkgs, FlagType flags)
if (flags & (LIBS_OTHER | LIBS_l))
{
cur = get_multi_merged (pkgs, flags & (LIBS_OTHER | LIBS_l), FALSE,
- !ignore_private_libs);
+ !ignore_private_libs,
+ (!ignore_requires_private &&
+ !ignore_private_libs));
debug_spew ("adding LIBS_OTHER | LIBS_l string \"%s\"\n", cur);
g_string_append (str, cur);
g_free (cur);
diff --git a/pkg.h b/pkg.h
index c6732bd..63ee413 100644
--- a/pkg.h
+++ b/pkg.h
@@ -21,9 +21,12 @@
#define PKG_CONFIG_PKG_H
#include <glib.h>
-
+#include <stdint.h>
typedef guint8 FlagType; /* bit mask for flag types */
+#define C_LINK_MULTIPLICITY_UNINITIALIZED 0
+#define C_LINK_MULTIPLICITY_DEFAULT 1
+
#define LIBS_l (1 << 0)
#define LIBS_L (1 << 1)
#define LIBS_OTHER (1 << 2)
@@ -48,6 +51,7 @@ typedef enum
typedef struct Flag_ Flag;
typedef struct Package_ Package;
typedef struct RequiredVersion_ RequiredVersion;
+typedef struct Component_ Component;
struct Flag_
{
@@ -85,6 +89,34 @@ struct Package_
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 */
char *orig_prefix; /* original prefix value before redefinition */
+ int cycle_edge_source_count; /* The number of times this vertex was the
+ source vertex of an edge that was skipped
+ to maintain acyclicicty */
+ int cycle_edge_destination_count; /* The number of times this vertex was the
+ destination vertex of an edge that was
+ skipped to main acyclicicy */
+ uint8_t link_multiplicity; /* Link multiplicity parsed from the package file.
+ Represents the maximum number of times this
+ package can appear on the link line to satisfy
+ static cyclic dependencies. Only used if we're
+ building a link line for a static target */
+};
+
+/* A component is any collection of possibly inter-dependent packages
+* which contains *AT MOST 1* strongly connected component from the original
+* dependency graph.
+*
+* Two components from the same dependency graph *CANNOT* overlap as they are
+* disjoint partitionings of the DAG generated after partitioning the original
+* topologically sorted dependency graph.
+*/
+struct Component_
+{
+ GList* start; /* Iterator to the first package in the component */
+ GList* end; /* Iterator to the last package in the component,
+ can be the same as `start` */
+ uint8_t multiplicity; /* Maximum multiplicity among all of the packages seen
+ while building this component. */
};
Package *get_package (const char *name);
@@ -142,6 +174,9 @@ extern gboolean define_prefix;
/* The name of the variable that acts as prefix, unless it is "prefix" */
extern char *prefix_variable;
+/* Link multiplicity to use for the static link line. Defaults to 1 */
+extern uint32_t link_multiplicity;
+
#ifdef G_OS_WIN32
/* If TRUE, output flags in MSVC syntax. */
extern gboolean msvc_syntax;
--
2.19.1
More information about the pkg-config
mailing list