file(GET_RUNTIME_DEPENDENCIES): Fix resolution of repeated ELF dependencies

When a library file name is encountered multiple times, reuse the result
from the first time.  This more closely matches the behavior of the
dynamic loader on Linux.

Fixes: #24621

8 files changed, 148 insertions, 36 deletions

diff --git a/Help/command/file.rst b/Help/command/file.rst
index ede95a1..0ac49f4 100644
--- a/Help/command/file.rst
+++ b/Help/command/file.rst
@@ -1169,6 +1169,14 @@ Handling Runtime Binaries
 
   5. Otherwise, the dependency is unresolved.
 
+  .. versionchanged:: 3.31
+
+    Resolution of each encountered library file name occurs at most once
+    while processing a given root ELF file (executable or shared object).
+    If a library file name is encountered again in the dependency tree,
+    the original resolution is assumed.  This behavior more closely matches
+    the dynamic loader's behavior on Linux.
+
   On Windows platforms, library resolution works as follows:
 
   1. DLL dependency names are converted to lowercase for matching filters.
diff --git a/Help/release/dev/elf-lib-deps-resolve.rst b/Help/release/dev/elf-lib-deps-resolve.rst
new file mode 100644
index 0000000..f7866eb
--- /dev/null
+++ b/Help/release/dev/elf-lib-deps-resolve.rst
@@ -0,0 +1,5 @@
+elf-lib-deps-resolve
+--------------------
+
+* The :command:`file(GET_RUNTIME_DEPENDENCIES)` command was updated
+  to more closely match the dynamic loader's behavior on Linux.
diff --git a/Source/cmBinUtilsLinuxELFLinker.cxx b/Source/cmBinUtilsLinuxELFLinker.cxx
index e2a8f92..ca40726 100644
--- a/Source/cmBinUtilsLinuxELFLinker.cxx
+++ b/Source/cmBinUtilsLinuxELFLinker.cxx
@@ -3,7 +3,10 @@
 
 #include "cmBinUtilsLinuxELFLinker.h"
 
+#include <queue>
 #include <sstream>
+#include <unordered_set>
+#include <utility>
 
 #include <cm/memory>
 #include <cm/string_view>
@@ -89,8 +92,6 @@ bool cmBinUtilsLinuxELFLinker::Prepare()
 bool cmBinUtilsLinuxELFLinker::ScanDependencies(
   std::string const& file, cmStateEnums::TargetType /* unused */)
 {
-  std::vector<std::string> parentRpaths;
-
   cmELF elf(file.c_str());
   if (!elf) {
     return false;
@@ -106,40 +107,53 @@ bool cmBinUtilsLinuxELFLinker::ScanDependencies(
     }
   }
 
-  return this->ScanDependencies(file, parentRpaths);
+  return this->ScanDependencies(file);
 }
 
-bool cmBinUtilsLinuxELFLinker::ScanDependencies(
-  std::string const& file, std::vector<std::string> const& parentRpaths)
+bool cmBinUtilsLinuxELFLinker::ScanDependencies(std::string const& mainFile)
 {
-  std::string origin = cmSystemTools::GetFilenamePath(file);
-  std::vector<std::string> needed;
-  std::vector<std::string> rpaths;
-  std::vector<std::string> runpaths;
-  if (!this->Tool->GetFileInfo(file, needed, rpaths, runpaths)) {
-    return false;
-  }
-  for (auto& runpath : runpaths) {
-    runpath = ReplaceOrigin(runpath, origin);
-  }
-  for (auto& rpath : rpaths) {
-    rpath = ReplaceOrigin(rpath, origin);
-  }
+  std::unordered_set<std::string> resolvedDependencies;
+  std::queue<std::pair<std::string, std::vector<std::string>>> queueToResolve;
+  queueToResolve.push(std::make_pair(mainFile, std::vector<std::string>{}));
+
+  while (!queueToResolve.empty()) {
+    std::string file = std::move(queueToResolve.front().first);
+    std::vector<std::string> parentRpaths =
+      std::move(queueToResolve.front().second);
+    queueToResolve.pop();
+
+    std::string origin = cmSystemTools::GetFilenamePath(file);
+    std::vector<std::string> needed;
+    std::vector<std::string> rpaths;
+    std::vector<std::string> runpaths;
+    if (!this->Tool->GetFileInfo(file, needed, rpaths, runpaths)) {
+      return false;
+    }
+    for (auto& runpath : runpaths) {
+      runpath = ReplaceOrigin(runpath, origin);
+    }
+    for (auto& rpath : rpaths) {
+      rpath = ReplaceOrigin(rpath, origin);
+    }
 
-  std::vector<std::string> searchPaths;
-  if (!runpaths.empty()) {
-    searchPaths = runpaths;
-  } else {
-    searchPaths = rpaths;
-    searchPaths.insert(searchPaths.end(), parentRpaths.begin(),
-                       parentRpaths.end());
-  }
+    std::vector<std::string> searchPaths;
+    if (!runpaths.empty()) {
+      searchPaths = runpaths;
+    } else {
+      searchPaths = rpaths;
+      searchPaths.insert(searchPaths.end(), parentRpaths.begin(),
+                         parentRpaths.end());
+    }
+
+    searchPaths.insert(searchPaths.end(), this->LDConfigPaths.begin(),
+                       this->LDConfigPaths.end());
 
-  searchPaths.insert(searchPaths.end(), this->LDConfigPaths.begin(),
-                     this->LDConfigPaths.end());
+    for (auto const& dep : needed) {
+      if (resolvedDependencies.count(dep) != 0 ||
+          this->Archive->IsPreExcluded(dep)) {
+        continue;
+      }
 
-  for (auto const& dep : needed) {
-    if (!this->Archive->IsPreExcluded(dep)) {
       std::string path;
       bool resolved = false;
       if (dep.find('/') != std::string::npos) {
@@ -150,6 +164,7 @@ bool cmBinUtilsLinuxELFLinker::ScanDependencies(
         return false;
       }
       if (resolved) {
+        resolvedDependencies.emplace(dep);
         if (!this->Archive->IsPostExcluded(path)) {
           bool unique;
           this->Archive->AddResolvedPath(dep, path, unique);
@@ -157,9 +172,8 @@ bool cmBinUtilsLinuxELFLinker::ScanDependencies(
             std::vector<std::string> combinedParentRpaths = parentRpaths;
             combinedParentRpaths.insert(combinedParentRpaths.end(),
                                         rpaths.begin(), rpaths.end());
-            if (!this->ScanDependencies(path, combinedParentRpaths)) {
-              return false;
-            }
+
+            queueToResolve.push(std::make_pair(path, combinedParentRpaths));
           }
         }
       } else {
diff --git a/Source/cmBinUtilsLinuxELFLinker.h b/Source/cmBinUtilsLinuxELFLinker.h
index 395ed56..0b0d8b5 100644
--- a/Source/cmBinUtilsLinuxELFLinker.h
+++ b/Source/cmBinUtilsLinuxELFLinker.h
@@ -34,8 +34,7 @@ private:
   std::vector<std::string> LDConfigPaths;
   std::uint16_t Machine = 0;
 
-  bool ScanDependencies(std::string const& file,
-                        std::vector<std::string> const& parentRpaths);
+  bool ScanDependencies(std::string const& mainFile);
 
   bool ResolveDependency(std::string const& name,
                          std::vector<std::string> const& searchPaths,
diff --git a/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/RunCMakeTest.cmake b/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/RunCMakeTest.cmake
index f7ede51..5583407 100644
--- a/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/RunCMakeTest.cmake
+++ b/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/RunCMakeTest.cmake
@@ -72,6 +72,7 @@ elseif(CMAKE_HOST_SYSTEM_NAME STREQUAL "Linux")
   run_install_test(linux-unresolved)
   run_install_test(linux-conflict)
   run_install_test(linux-notfile)
+  run_install_test(linux-indirect-dependencies)
   run_cmake(project)
   run_cmake(badargs1)
   run_cmake(badargs2)
diff --git a/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-all-check.cmake b/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-all-check.cmake
index d3d1cd6..012ed58 100644
--- a/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-all-check.cmake
+++ b/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-all-check.cmake
@@ -1,4 +1,5 @@
 set(_check
+  [[[^;]*/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-build/root-all/lib/conflict/libconflict\.so]]
   [[[^;]*/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-build/root-all/lib/libtest_rpath\.so]]
   [[[^;]*/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-build/root-all/lib/libtest_runpath\.so]]
   [[[^;]*/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-build/root-all/lib/rpath/librpath\.so]]
@@ -19,7 +20,7 @@ check_contents(deps/udeps1.txt "^${_check}$")
 check_contents(deps/udeps2.txt "^${_check}$")
 check_contents(deps/udeps3.txt "^${_check}$")
 set(_check
-  "^libconflict\\.so:[^;]*/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-build/root-all/lib/conflict/libconflict\\.so;[^;]*/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-build/root-all/lib/conflict2/libconflict\\.so\n$"
+  "^$"
   )
 check_contents(deps/cdeps1.txt "${_check}")
 check_contents(deps/cdeps2.txt "${_check}")
diff --git a/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-indirect-dependencies-all-stdout.txt b/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-indirect-dependencies-all-stdout.txt
new file mode 100644
index 0000000..9f5e07d
--- /dev/null
+++ b/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-indirect-dependencies-all-stdout.txt
@@ -0,0 +1 @@
+Resolved dependencies: /
diff --git a/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-indirect-dependencies.cmake b/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-indirect-dependencies.cmake
new file mode 100644
index 0000000..1d0a913
--- /dev/null
+++ b/Tests/RunCMake/file-GET_RUNTIME_DEPENDENCIES/linux-indirect-dependencies.cmake
@@ -0,0 +1,83 @@
+enable_language(C)
+cmake_policy(SET CMP0095 NEW)
+
+file(WRITE "${CMAKE_BINARY_DIR}/A.c" "void libA(void) {}\n")
+file(WRITE "${CMAKE_BINARY_DIR}/C.c" "void libC(void) {}\n")
+file(WRITE "${CMAKE_BINARY_DIR}/BUseAC.c" [[
+extern void libA(void);
+extern void libC(void);
+void libB(void)
+{
+    libA();
+    libC();
+}
+]])
+file(WRITE "${CMAKE_BINARY_DIR}/mainABC.c" [[
+extern void libA(void);
+extern void libB(void);
+extern void libC(void);
+
+int main(void)
+{
+    libA();
+    libB();
+    libC();
+    return 0;
+}
+
+]])
+
+set(lib_dirExe "${CMAKE_BINARY_DIR}/Exe")
+set(lib_dirA "${CMAKE_BINARY_DIR}/libA")
+set(lib_dirB "${CMAKE_BINARY_DIR}/libB")
+set(lib_dirC "${CMAKE_BINARY_DIR}/libC")
+file(MAKE_DIRECTORY ${lib_dirExe})
+file(MAKE_DIRECTORY ${lib_dirA})
+file(MAKE_DIRECTORY ${lib_dirB})
+file(MAKE_DIRECTORY ${lib_dirC})
+
+add_library(A SHARED "${CMAKE_BINARY_DIR}/A.c")
+set_property(TARGET A PROPERTY LIBRARY_OUTPUT_DIRECTORY ${lib_dirA})
+
+add_library(C SHARED "${CMAKE_BINARY_DIR}/C.c")
+set_property(TARGET C PROPERTY LIBRARY_OUTPUT_DIRECTORY ${lib_dirC})
+
+# We doesn't need to set A as a dependency of B, because we don't need `RUNPATH` value set for B
+add_library(B SHARED "${CMAKE_BINARY_DIR}/BUseAC.c")
+target_link_libraries(B PRIVATE A C)
+set_property(TARGET B PROPERTY LIBRARY_OUTPUT_DIRECTORY ${lib_dirB})
+
+# We MUST have empty `RUNPATH` in A & B
+set_target_properties(A B C PROPERTIES
+    BUILD_WITH_INSTALL_RPATH 1
+)
+
+# The executable is really workable without `RUNPATH` in B
+add_executable(exe "${CMAKE_BINARY_DIR}/mainABC.c")
+target_link_libraries(exe A B C)
+set_property(TARGET exe PROPERTY RUNTIME_OUTPUT_DIRECTORY ${lib_dirExe})
+
+# We MUST have `RUNPATH` in exe, not `RPATH`
+# Test will pass if we have `RPATH`, because of the inheritance
+target_link_options(exe PRIVATE -Wl,--enable-new-dtags)
+
+install(CODE [[
+    # Work with non-installed binary, because of the RUNPATH values
+    set(exeFile "$<TARGET_FILE:exe>")
+
+    # Check executable is can be successfully finished
+    execute_process(
+        COMMAND "${exeFile}"
+        COMMAND_ERROR_IS_FATAL ANY
+    )
+
+    # Check dependencies resolved
+    file(GET_RUNTIME_DEPENDENCIES
+        RESOLVED_DEPENDENCIES_VAR RESOLVED
+        PRE_INCLUDE_REGEXES "^lib[ABC]\\.so$"
+        PRE_EXCLUDE_REGEXES ".*"
+        EXECUTABLES
+            "${exeFile}"
+    )
+    message(STATUS "Resolved dependencies: ${RESOLVED}")
+]])