Fix niche cases when linking static libs

Case 1:
- Prog links to static lib A
- A link_whole to static lib B
- B link to static lib C
- Prog dependencies should be A and C but not B which is already
  included in A.

Case 2:
- Same as case 1, but with A being installed.
- To be useful, A must also include all objects from C that is not
  installed.
- Prog only need to link on A.

7 files changed, 124 insertions, 16 deletions

diff --git a/mesonbuild/build.py b/mesonbuild/build.py
index fefc28c..d48667f 100644
--- a/mesonbuild/build.py
+++ b/mesonbuild/build.py
@@ -1280,17 +1280,36 @@ class BuildTarget(Target):
     def get_extra_args(self, language):
         return self.extra_args.get(language, [])
 
-    def get_dependencies(self, exclude=None):
-        transitive_deps = []
-        if exclude is None:
-            exclude = []
+    @lru_cache(maxsize=None)
+    def get_dependencies(self) -> OrderedSet[Target]:
+        # Get all targets needed for linking. This includes all link_with and
+        # link_whole targets, and also all dependencies of static libraries
+        # recursively. The algorithm here is closely related to what we do in
+        # get_internal_static_libraries(): Installed static libraries include
+        # objects from all their dependencies already.
+        result: OrderedSet[Target] = OrderedSet()
         for t in itertools.chain(self.link_targets, self.link_whole_targets):
-            if t in transitive_deps or t in exclude:
+            if t not in result:
+                result.add(t)
+                if isinstance(t, StaticLibrary):
+                    t.get_dependencies_recurse(result)
+        return result
+
+    def get_dependencies_recurse(self, result: OrderedSet[Target], include_internals: bool = True) -> None:
+        # self is always a static library because we don't need to pull dependencies
+        # of shared libraries. If self is installed (not internal) it already
+        # include objects extracted from all its internal dependencies so we can
+        # skip them.
+        include_internals = include_internals and self.is_internal()
+        for t in self.link_targets:
+            if t in result:
                 continue
-            transitive_deps.append(t)
+            if include_internals or not t.is_internal():
+                result.add(t)
             if isinstance(t, StaticLibrary):
-                transitive_deps += t.get_dependencies(transitive_deps + exclude)
-        return transitive_deps
+                t.get_dependencies_recurse(result, include_internals)
+        for t in self.link_whole_targets:
+            t.get_dependencies_recurse(result, include_internals)
 
     def get_source_subdir(self):
         return self.subdir
@@ -1441,15 +1460,28 @@ You probably should put it in link_with instead.''')
             if isinstance(self, StaticLibrary):
                 # When we're a static library and we link_whole: to another static
                 # library, we need to add that target's objects to ourselves.
-                self.objects += t.extract_all_objects_recurse()
+                self.objects += [t.extract_all_objects()]
+                # If we install this static library we also need to include objects
+                # from all uninstalled static libraries it depends on.
+                if self.need_install:
+                    for lib in t.get_internal_static_libraries():
+                        self.objects += [lib.extract_all_objects()]
             self.link_whole_targets.append(t)
 
-    def extract_all_objects_recurse(self) -> T.List[T.Union[str, 'ExtractedObjects']]:
-        objs = [self.extract_all_objects()]
+    @lru_cache(maxsize=None)
+    def get_internal_static_libraries(self) -> OrderedSet[Target]:
+        result: OrderedSet[Target] = OrderedSet()
+        self.get_internal_static_libraries_recurse(result)
+        return result
+
+    def get_internal_static_libraries_recurse(self, result: OrderedSet[Target]) -> None:
         for t in self.link_targets:
+            if t.is_internal() and t not in result:
+                result.add(t)
+                t.get_internal_static_libraries_recurse(result)
+        for t in self.link_whole_targets:
             if t.is_internal():
-                objs += t.extract_all_objects_recurse()
-        return objs
+                t.get_internal_static_libraries_recurse(result)
 
     def add_pch(self, language: str, pchlist: T.List[str]) -> None:
         if not pchlist:
@@ -2661,7 +2693,7 @@ class CustomTarget(Target, CommandBase):
             return False
         return CustomTargetIndex(self, self.outputs[0]).is_internal()
 
-    def extract_all_objects_recurse(self) -> T.List[T.Union[str, 'ExtractedObjects']]:
+    def extract_all_objects(self) -> T.List[T.Union[str, 'ExtractedObjects']]:
         return self.get_outputs()
 
     def type_suffix(self):
@@ -2923,8 +2955,8 @@ class CustomTargetIndex(HoldableObject):
         suf = os.path.splitext(self.output)[-1]
         return suf in {'.a', '.lib'} and not self.should_install()
 
-    def extract_all_objects_recurse(self) -> T.List[T.Union[str, 'ExtractedObjects']]:
-        return self.target.extract_all_objects_recurse()
+    def extract_all_objects(self) -> T.List[T.Union[str, 'ExtractedObjects']]:
+        return self.target.extract_all_objects()
 
     def get_custom_install_dir(self) -> T.List[T.Union[str, Literal[False]]]:
         return self.target.get_custom_install_dir()
diff --git a/test cases/unit/113 complex link cases/main.c b/test cases/unit/113 complex link cases/main.c
new file mode 100644
index 0000000..739b413
--- /dev/null
+++ b/test cases/unit/113 complex link cases/main.c
@@ -0,0 +1,6 @@
+int s3(void);
+
+int main(int argc, char *argv[])
+{
+    return s3();
+}
diff --git a/test cases/unit/113 complex link cases/meson.build b/test cases/unit/113 complex link cases/meson.build
new file mode 100644
index 0000000..d3387c2
--- /dev/null
+++ b/test cases/unit/113 complex link cases/meson.build
@@ -0,0 +1,40 @@
+project('complex link cases', 'c')
+
+# In all tests, e1 uses s3 which uses s2 which uses s1.
+
+# Executable links with s3 and s1 but not s2 because it is included in s3.
+s1 = static_library('t1-s1', 's1.c')
+s2 = static_library('t1-s2', 's2.c', link_with: s1)
+s3 = static_library('t1-s3', 's3.c', link_whole: s2)
+e = executable('t1-e1', 'main.c', link_with: s3)
+
+# s3 is installed but not s1 so it has to include s1 too.
+# Executable links only s3 because it contains s1 and s2.
+s1 = static_library('t2-s1', 's1.c')
+s2 = static_library('t2-s2', 's2.c', link_with: s1)
+s3 = static_library('t2-s3', 's3.c', link_whole: s2, install: true)
+e = executable('t2-e1', 'main.c', link_with: s3)
+
+# Executable needs to link with s3 only
+s1 = static_library('t3-s1', 's1.c')
+s2 = static_library('t3-s2', 's2.c', link_with: s1)
+s3 = shared_library('t3-s3', 's3.c', link_with: s2)
+e = executable('t3-e1', 'main.c', link_with: s3)
+
+# Executable needs to link with s3 and s2
+s1 = static_library('t4-s1', 's1.c')
+s2 = shared_library('t4-s2', 's2.c', link_with: s1)
+s3 = static_library('t4-s3', 's3.c', link_with: s2)
+e = executable('t4-e1', 'main.c', link_with: s3)
+
+# Executable needs to link with s3 and s1
+s1 = shared_library('t5-s1', 's1.c')
+s2 = static_library('t5-s2', 's2.c', link_with: s1)
+s3 = static_library('t5-s3', 's3.c', link_with: s2, install: true)
+e = executable('t5-e1', 'main.c', link_with: s3)
+
+# Executable needs to link with s3 and s2
+s1 = static_library('t6-s1', 's1.c')
+s2 = static_library('t6-s2', 's2.c', link_with: s1, install: true)
+s3 = static_library('t6-s3', 's3.c', link_with: s2, install: true)
+e = executable('t6-e1', 'main.c', link_with: s3)
diff --git a/test cases/unit/113 complex link cases/s1.c b/test cases/unit/113 complex link cases/s1.c
new file mode 100644
index 0000000..68bba49
--- /dev/null
+++ b/test cases/unit/113 complex link cases/s1.c
@@ -0,0 +1,3 @@
+int s1(void) {
+    return 1;
+}
diff --git a/test cases/unit/113 complex link cases/s2.c b/test cases/unit/113 complex link cases/s2.c
new file mode 100644
index 0000000..835870c
--- /dev/null
+++ b/test cases/unit/113 complex link cases/s2.c
@@ -0,0 +1,5 @@
+int s1(void);
+
+int s2(void) {
+    return s1() + 1;
+}
diff --git a/test cases/unit/113 complex link cases/s3.c b/test cases/unit/113 complex link cases/s3.c
new file mode 100644
index 0000000..08e0620
--- /dev/null
+++ b/test cases/unit/113 complex link cases/s3.c
@@ -0,0 +1,5 @@
+int s2(void);
+
+int s3(void) {
+    return s2() + 1;
+}
diff --git a/unittests/linuxliketests.py b/unittests/linuxliketests.py
index c94169a..b1b9c4c 100644
--- a/unittests/linuxliketests.py
+++ b/unittests/linuxliketests.py
@@ -1828,3 +1828,20 @@ class LinuxlikeTests(BasePlatformTests):
         with self.assertRaises(subprocess.CalledProcessError) as e:
             self.run_tests()
         self.assertNotIn('Traceback', e.exception.output)
+
+    @skipUnless(is_linux(), "Ninja file differs on different platforms")
+    def test_complex_link_cases(self):
+        testdir = os.path.join(self.unit_test_dir, '113 complex link cases')
+        self.init(testdir)
+        self.build()
+        with open(os.path.join(self.builddir, 'build.ninja'), encoding='utf-8') as f:
+            content = f.read()
+        # Verify link dependencies, see comments in meson.build.
+        self.assertIn('build libt1-s3.a: STATIC_LINKER libt1-s2.a.p/s2.c.o libt1-s3.a.p/s3.c.o\n', content)
+        self.assertIn('build t1-e1: c_LINKER t1-e1.p/main.c.o | libt1-s1.a libt1-s3.a\n', content)
+        self.assertIn('build libt2-s3.a: STATIC_LINKER libt2-s2.a.p/s2.c.o libt2-s1.a.p/s1.c.o libt2-s3.a.p/s3.c.o\n', content)
+        self.assertIn('build t2-e1: c_LINKER t2-e1.p/main.c.o | libt2-s3.a\n', content)
+        self.assertIn('build t3-e1: c_LINKER t3-e1.p/main.c.o | libt3-s3.so.p/libt3-s3.so.symbols\n', content)
+        self.assertIn('build t4-e1: c_LINKER t4-e1.p/main.c.o | libt4-s2.so.p/libt4-s2.so.symbols libt4-s3.a\n', content)
+        self.assertIn('build t5-e1: c_LINKER t5-e1.p/main.c.o | libt5-s1.so.p/libt5-s1.so.symbols libt5-s3.a\n', content)
+        self.assertIn('build t6-e1: c_LINKER t6-e1.p/main.c.o | libt6-s2.a libt6-s3.a\n', content)