ninja: De-dup libraries and use --start/end-group

Now we aggressively de-dup the list of libraries used while linking,
and when linking with GNU ld we have to enclose all static libraries
with -Wl,--start-group and -Wl,--end-group to force the linker to
resolve all symbols recursively. This is needed when static libraries
have circular deps on each other (see included test).

The --start/end-group change is also needed for circular dependencies
between static libraries because we no longer recursively list out all
library dependencies.

The size of build.ninja for GStreamer is now down to 6.1M from 20M,
and yields a net reduction in configuration time of 10%

17 files changed, 146 insertions, 16 deletions

diff --git a/mesonbuild/compilers.py b/mesonbuild/compilers.py
index e7c02b2..d0f3349 100644
--- a/mesonbuild/compilers.py
+++ b/mesonbuild/compilers.py
@@ -12,6 +12,7 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+import re
 import shutil
 import contextlib
 import subprocess, os.path
@@ -375,10 +376,15 @@ class CompilerArgs(list):
     # Arg prefixes that override by prepending instead of appending
     prepend_prefixes = ('-I', '-L')
     # Arg prefixes and args that must be de-duped by returning 2
-    dedup2_prefixes = ('-I', '-L', '-D')
+    dedup2_prefixes = ('-I', '-L', '-D', '-U')
+    dedup2_suffixes = ()
     dedup2_args = ()
     # Arg prefixes and args that must be de-duped by returning 1
-    dedup1_prefixes = ()
+    dedup1_prefixes = ('-l',)
+    dedup1_suffixes = ('.lib', '.dll', '.so', '.dylib', '.a')
+    # Match a .so of the form path/to/libfoo.so.0.1.0
+    # Only UNIX shared libraries require this. Others have a fixed extension.
+    dedup1_regex = re.compile(r'([\/\\]|\A)lib.*\.so(\.[0-9]+)?(\.[0-9]+)?(\.[0-9]+)?$')
     dedup1_args = ('-c', '-S', '-E', '-pipe', '-pthread')
     compiler = None
 
@@ -416,7 +422,7 @@ class CompilerArgs(list):
     def _can_dedup(cls, arg):
         '''
         Returns whether the argument can be safely de-duped. This is dependent
-        on two things:
+        on three things:
 
         a) Whether an argument can be 'overriden' by a later argument.  For
            example, -DFOO defines FOO and -UFOO undefines FOO. In this case, we
@@ -430,10 +436,20 @@ class CompilerArgs(list):
            a particular argument is present. This can matter for symbol
            resolution in static or shared libraries, so we cannot de-dup or
            reorder them. For these we return `0`. This is the default.
+
+        In addition to these, we handle library arguments specially.
+        With GNU ld, we surround library arguments with -Wl,--start/end-group
+        to recursively search for symbols in the libraries. This is not needed
+        with other linkers.
         '''
-        if arg.startswith(cls.dedup2_prefixes) or arg in cls.dedup2_args:
+        if arg in cls.dedup2_args or \
+           arg.startswith(cls.dedup2_prefixes) or \
+           arg.endswith(cls.dedup2_suffixes):
             return 2
-        if arg.startswith(cls.dedup1_prefixes) or arg in cls.dedup1_args:
+        if arg in cls.dedup1_args or \
+           arg.startswith(cls.dedup1_prefixes) or \
+           arg.endswith(cls.dedup1_suffixes) or \
+           re.search(cls.dedup1_regex, arg):
             return 1
         return 0
 
@@ -444,6 +460,21 @@ class CompilerArgs(list):
         return False
 
     def to_native(self):
+        # Check if we need to add --start/end-group for circular dependencies
+        # between static libraries.
+        if get_compiler_uses_gnuld(self.compiler):
+            group_started = False
+            for each in self:
+                if not each.startswith('-l') and not each.endswith('.a'):
+                    continue
+                i = self.index(each)
+                if not group_started:
+                    # First occurance of a library
+                    self.insert(i, '-Wl,--start-group')
+                    group_started = True
+            # Last occurance of a library
+            if group_started:
+                self.insert(i + 1, '-Wl,--end-group')
         return self.compiler.unix_args_to_native(self)
 
     def __add__(self, args):
@@ -2402,6 +2433,15 @@ def get_compiler_is_linuxlike(compiler):
         return True
     return False
 
+def get_compiler_uses_gnuld(c):
+    # FIXME: Perhaps we should detect the linker in the environment?
+    # FIXME: Assumes that *BSD use GNU ld, but they might start using lld soon
+    if (getattr(c, 'gcc_type', None) in (GCC_STANDARD, GCC_MINGW, GCC_CYGWIN)) or \
+       (getattr(c, 'clang_type', None) in (CLANG_STANDARD, CLANG_WIN)) or \
+       (getattr(c, 'icc_type', None) in (ICC_STANDARD, ICC_WIN)):
+        return True
+    return False
+
 def get_largefile_args(compiler):
     '''
     Enable transparent large-file-support for 32-bit UNIX systems
diff --git a/run_unittests.py b/run_unittests.py
index e3b7c5c..71448f9 100755
--- a/run_unittests.py
+++ b/run_unittests.py
@@ -139,7 +139,7 @@ class InternalTests(unittest.TestCase):
         self.assertEqual(a, ['-Ibar', '-Ifoo', '-Ibaz', '-I..', '-I.', '-O3', '-O2', '-Wall'])
 
         ## Test that reflected addition works
-        # Test that adding to a list with just one old arg works and DOES NOT yield the same array
+        # Test that adding to a list with just one old arg works and yields the same array
         a = ['-Ifoo'] + a
         self.assertEqual(a, ['-Ibar', '-Ifoo', '-Ibaz', '-I..', '-I.', '-O3', '-O2', '-Wall'])
         # Test that adding to a list with just one new arg that is not pre-pended works
@@ -148,6 +148,19 @@ class InternalTests(unittest.TestCase):
         # Test that adding to a list with two new args preserves the order
         a = ['-Ldir', '-Lbah'] + a
         self.assertEqual(a, ['-Ibar', '-Ifoo', '-Ibaz', '-I..', '-I.', '-Ldir', '-Lbah', '-Werror', '-O3', '-O2', '-Wall'])
+        # Test that adding to a list with old args does nothing
+        a = ['-Ibar', '-Ibaz', '-Ifoo'] + a
+        self.assertEqual(a, ['-Ibar', '-Ifoo', '-Ibaz', '-I..', '-I.', '-Ldir', '-Lbah', '-Werror', '-O3', '-O2', '-Wall'])
+
+        ## Test that adding libraries works
+        l = cargsfunc(c, ['-Lfoodir', '-lfoo'])
+        self.assertEqual(l, ['-Lfoodir', '-lfoo'])
+        # Adding a library and a libpath appends both correctly
+        l += ['-Lbardir', '-lbar']
+        self.assertEqual(l, ['-Lbardir', '-Lfoodir', '-lfoo', '-lbar'])
+        # Adding the same library again does nothing
+        l += ['-lbar']
+        self.assertEqual(l, ['-Lbardir', '-Lfoodir', '-lfoo', '-lbar'])
 
     def test_commonpath(self):
         from os.path import sep
diff --git a/test cases/common/153 recursive linking/3rdorderdeps/meson.build b/test cases/common/153 recursive linking/3rdorderdeps/meson.build
index a2907f3..d4ef745 100644
--- a/test cases/common/153 recursive linking/3rdorderdeps/meson.build
+++ b/test cases/common/153 recursive linking/3rdorderdeps/meson.build
@@ -16,8 +16,10 @@ foreach dep2 : ['sh', 'st']
 
       if libtype == 'sh'
         target = 'shared_library'
+        build_args = []
       elif libtype == 'st'
         target = 'static_library'
+        build_args = ['-DMESON_STATIC_BUILD']
       else
         error('Unknown libtype "@0@"'.format(libtype))
       endif
@@ -31,13 +33,16 @@ foreach dep2 : ['sh', 'st']
                              output : name + '-lib.c',
                              configuration : cdata)
       dep = get_variable(dep1 + dep2 + 'dep')
-      dep3_lib = build_target(name, lib_c, link_with : dep, target_type : target)
+      dep3_lib = build_target(name, lib_c, link_with : dep,
+                              target_type : target,
+                              c_args : build_args)
       dep3_libs += [dep3_lib]
 
       main_c = configure_file(input : 'main.c.in',
                               output : name + '-main.c',
                               configuration : cdata)
-      dep3_bin = executable(name, main_c, link_with : dep3_lib)
+      dep3_bin = executable(name, main_c, link_with : dep3_lib,
+                            c_args : build_args)
       test(name + 'test', dep3_bin)
     endforeach
   endforeach
diff --git a/test cases/common/153 recursive linking/circular/lib1.c b/test cases/common/153 recursive linking/circular/lib1.c
new file mode 100644
index 0000000..38889cf
--- /dev/null
+++ b/test cases/common/153 recursive linking/circular/lib1.c
@@ -0,0 +1,6 @@
+int get_st2_prop (void);
+int get_st3_prop (void);
+
+int get_st1_value (void) {
+  return get_st2_prop () + get_st3_prop ();
+}
diff --git a/test cases/common/153 recursive linking/circular/lib2.c b/test cases/common/153 recursive linking/circular/lib2.c
new file mode 100644
index 0000000..31cd37c
--- /dev/null
+++ b/test cases/common/153 recursive linking/circular/lib2.c
@@ -0,0 +1,6 @@
+int get_st1_prop (void);
+int get_st3_prop (void);
+
+int get_st2_value (void) {
+  return get_st1_prop () + get_st3_prop ();
+}
diff --git a/test cases/common/153 recursive linking/circular/lib3.c b/test cases/common/153 recursive linking/circular/lib3.c
new file mode 100644
index 0000000..67d473a
--- /dev/null
+++ b/test cases/common/153 recursive linking/circular/lib3.c
@@ -0,0 +1,6 @@
+int get_st1_prop (void);
+int get_st2_prop (void);
+
+int get_st3_value (void) {
+  return get_st1_prop () + get_st2_prop ();
+}
diff --git a/test cases/common/153 recursive linking/circular/main.c b/test cases/common/153 recursive linking/circular/main.c
new file mode 100644
index 0000000..5f797a5
--- /dev/null
+++ b/test cases/common/153 recursive linking/circular/main.c
@@ -0,0 +1,28 @@
+#include <stdio.h>
+
+#include "../lib.h"
+
+int get_st1_value (void);
+int get_st2_value (void);
+int get_st3_value (void);
+
+int main(int argc, char *argv[]) {
+  int val;
+
+  val = get_st1_value ();
+  if (val != 5) {
+    printf("st1 value was %i instead of 5\n", val);
+    return -1;
+  }
+  val = get_st2_value ();
+  if (val != 4) {
+    printf("st2 value was %i instead of 4\n", val);
+    return -2;
+  }
+  val = get_st3_value ();
+  if (val != 3) {
+    printf("st3 value was %i instead of 3\n", val);
+    return -3;
+  }
+  return 0;
+}
diff --git a/test cases/common/153 recursive linking/circular/meson.build b/test cases/common/153 recursive linking/circular/meson.build
new file mode 100644
index 0000000..b7a70a8
--- /dev/null
+++ b/test cases/common/153 recursive linking/circular/meson.build
@@ -0,0 +1,5 @@
+st1 = static_library('st1', 'lib1.c', 'prop1.c')
+st2 = static_library('st2', 'lib2.c', 'prop2.c')
+st3 = static_library('st3', 'lib3.c', 'prop3.c')
+
+test('circular', executable('circular', 'main.c', link_with : [st1, st2, st3]))
diff --git a/test cases/common/153 recursive linking/circular/prop1.c b/test cases/common/153 recursive linking/circular/prop1.c
new file mode 100644
index 0000000..4e571f5
--- /dev/null
+++ b/test cases/common/153 recursive linking/circular/prop1.c
@@ -0,0 +1,3 @@
+int get_st1_prop (void) {
+  return 1;
+}
diff --git a/test cases/common/153 recursive linking/circular/prop2.c b/test cases/common/153 recursive linking/circular/prop2.c
new file mode 100644
index 0000000..ceabba0
--- /dev/null
+++ b/test cases/common/153 recursive linking/circular/prop2.c
@@ -0,0 +1,3 @@
+int get_st2_prop (void) {
+  return 2;
+}
diff --git a/test cases/common/153 recursive linking/circular/prop3.c b/test cases/common/153 recursive linking/circular/prop3.c
new file mode 100644
index 0000000..246206c
--- /dev/null
+++ b/test cases/common/153 recursive linking/circular/prop3.c
@@ -0,0 +1,3 @@
+int get_st3_prop (void) {
+  return 3;
+}
diff --git a/test cases/common/153 recursive linking/lib.h b/test cases/common/153 recursive linking/lib.h
index b6b75fa..b54bf36 100644
--- a/test cases/common/153 recursive linking/lib.h
+++ b/test cases/common/153 recursive linking/lib.h
@@ -1,6 +1,11 @@
 #if defined _WIN32
-  #define SYMBOL_IMPORT __declspec(dllimport)
-  #define SYMBOL_EXPORT __declspec(dllexport)
+  #ifdef MESON_STATIC_BUILD
+   #define SYMBOL_EXPORT
+   #define SYMBOL_IMPORT
+  #else
+   #define SYMBOL_IMPORT __declspec(dllimport)
+   #define SYMBOL_EXPORT __declspec(dllexport)
+  #endif
 #else
   #define SYMBOL_IMPORT
   #if defined __GNUC__
diff --git a/test cases/common/153 recursive linking/main.c b/test cases/common/153 recursive linking/main.c
index f1219a6..0851611 100644
--- a/test cases/common/153 recursive linking/main.c
+++ b/test cases/common/153 recursive linking/main.c
@@ -2,12 +2,12 @@
 
 #include "lib.h"
 
-SYMBOL_IMPORT int get_stnodep_value (void);
+int get_stnodep_value (void);
+int get_stshdep_value (void);
+int get_ststdep_value (void);
 SYMBOL_IMPORT int get_shnodep_value (void);
 SYMBOL_IMPORT int get_shshdep_value (void);
 SYMBOL_IMPORT int get_shstdep_value (void);
-SYMBOL_IMPORT int get_stshdep_value (void);
-SYMBOL_IMPORT int get_ststdep_value (void);
 
 int main(int argc, char *argv[]) {
   int val;
diff --git a/test cases/common/153 recursive linking/meson.build b/test cases/common/153 recursive linking/meson.build
index f17fc4a..4cecd57 100644
--- a/test cases/common/153 recursive linking/meson.build
+++ b/test cases/common/153 recursive linking/meson.build
@@ -20,3 +20,7 @@ test('alldeps',
 
 # More combinations of static and shared libraries
 subdir('3rdorderdeps')
+
+# Circular dependencies between static libraries
+# This requires the use of --start/end-group with GNU ld
+subdir('circular')
diff --git a/test cases/common/153 recursive linking/stnodep/meson.build b/test cases/common/153 recursive linking/stnodep/meson.build
index 0334f23..77f7129 100644
--- a/test cases/common/153 recursive linking/stnodep/meson.build
+++ b/test cases/common/153 recursive linking/stnodep/meson.build
@@ -1 +1,2 @@
-stnodep = static_library('stnodep', 'lib.c')
+stnodep = static_library('stnodep', 'lib.c',
+                         c_args : '-DMESON_STATIC_BUILD')
diff --git a/test cases/common/153 recursive linking/stshdep/meson.build b/test cases/common/153 recursive linking/stshdep/meson.build
index 7e8e7c8..0967c1c 100644
--- a/test cases/common/153 recursive linking/stshdep/meson.build
+++ b/test cases/common/153 recursive linking/stshdep/meson.build
@@ -1 +1,2 @@
-stshdep = static_library('stshdep', 'lib.c', link_with : shnodep)
+stshdep = static_library('stshdep', 'lib.c', link_with : shnodep,
+                         c_args : '-DMESON_STATIC_BUILD')
diff --git a/test cases/common/153 recursive linking/ststdep/meson.build b/test cases/common/153 recursive linking/ststdep/meson.build
index 92b0230..3602442 100644
--- a/test cases/common/153 recursive linking/ststdep/meson.build
+++ b/test cases/common/153 recursive linking/ststdep/meson.build
@@ -1 +1,2 @@
-ststdep = static_library('ststdep', 'lib.c', link_with : stnodep)
+ststdep = static_library('ststdep', 'lib.c', link_with : stnodep,
+                         c_args : '-DMESON_STATIC_BUILD')