Linking: Optionally reorder direct dependencies from LINK_LIBRARIES

Traditionally CMake generates link lines by starting with the direct
link dependencies specified by `LINK_LIBRARIES` in their original order
and then appending indirect dependencies that the direct dependencies
do not express.  This gives projects control over ordering among
independent entries, which can be important when intermixing flags
and libraries, or when multiple libraries provide the same symbol.
However, it may also result in inefficient link lines.

Add support for an alternative strategy that can reorder direct link
dependencies to produce more efficient link lines.  This is useful
for projects that cannot easily specify their targets' direct
dependencies in an order that satisfies indirect dependencies.

Add a `CMAKE_LINK_LIBRARIES_STRATEGY` variable and corresponding
`LINK_LIBRARIES_STRATEGY` target property to select a strategy.

Fixes: #26271

27 files changed, 177 insertions, 0 deletions

diff --git a/Tests/RunCMake/CMakeLists.txt b/Tests/RunCMake/CMakeLists.txt
index 40db51b..ba8776f 100644
--- a/Tests/RunCMake/CMakeLists.txt
+++ b/Tests/RunCMake/CMakeLists.txt
@@ -836,6 +836,7 @@ if (CMAKE_SYSTEM_NAME MATCHES "(Linux|Darwin|Windows)"
 endif()
 
 add_RunCMake_test(LinkLibrariesProcessing)
+add_RunCMake_test(LinkLibrariesStrategy)
 add_RunCMake_test(File_Archive)
 add_RunCMake_test(File_Configure)
 add_RunCMake_test(File_Generate)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-run-stdout-reverse.txt b/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-run-stdout-reverse.txt
new file mode 100644
index 0000000..7e46d1ba
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-run-stdout-reverse.txt
@@ -0,0 +1 @@
+^Library 'B' was linked first\.$
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-run-stdout.txt b/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-run-stdout.txt
new file mode 100644
index 0000000..6ef12eb
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-run-stdout.txt
@@ -0,0 +1 @@
+^Library 'A' was linked first\.$
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-stderr.txt b/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-stderr.txt
new file mode 100644
index 0000000..1d8f4ba
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER-stderr.txt
@@ -0,0 +1,7 @@
+target \[main\] link dependency ordering:
+  target \[A\]
+  target \[B\]
+  target \[C\]
+  target \[A\]
+
+target \[main\] link line:
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER.cmake b/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER.cmake
new file mode 100644
index 0000000..f3dc096
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic-PRESERVE_ORDER.cmake
@@ -0,0 +1,2 @@
+set(CMAKE_LINK_LIBRARIES_STRATEGY PRESERVE_ORDER)
+include(Basic-common.cmake)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER-run-stdout.txt b/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER-run-stdout.txt
new file mode 100644
index 0000000..7e46d1ba
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER-run-stdout.txt
@@ -0,0 +1 @@
+^Library 'B' was linked first\.$
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER-stderr.txt b/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER-stderr.txt
new file mode 100644
index 0000000..54b02bd
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER-stderr.txt
@@ -0,0 +1,6 @@
+target \[main\] link dependency ordering:
+  target \[B\]
+  target \[C\]
+  target \[A\]
+
+target \[main\] link line:
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER.cmake b/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER.cmake
new file mode 100644
index 0000000..8e62377
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic-REORDER.cmake
@@ -0,0 +1,2 @@
+set(CMAKE_LINK_LIBRARIES_STRATEGY REORDER)
+include(Basic-common.cmake)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic-common.cmake b/Tests/RunCMake/LinkLibrariesStrategy/Basic-common.cmake
new file mode 100644
index 0000000..8dbbd39
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic-common.cmake
@@ -0,0 +1,15 @@
+enable_language(C)
+
+add_library(A STATIC BasicA.c BasicX.c)
+add_library(B STATIC BasicB.c BasicX.c)
+add_library(C STATIC BasicC.c BasicX.c)
+target_link_libraries(B PRIVATE A)
+target_link_libraries(C PRIVATE A)
+target_compile_definitions(A PRIVATE BASIC_ID="A")
+target_compile_definitions(B PRIVATE BASIC_ID="B")
+target_compile_definitions(C PRIVATE BASIC_ID="C")
+
+add_executable(main Basic.c)
+target_link_libraries(main PRIVATE A B C)
+set_property(TARGET main PROPERTY LINK_DEPENDS_DEBUG_MODE 1) # undocumented
+set_property(TARGET main PROPERTY RUNTIME_OUTPUT_DIRECTORY "$<1:${CMAKE_BINARY_DIR}>")
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Basic.c b/Tests/RunCMake/LinkLibrariesStrategy/Basic.c
new file mode 100644
index 0000000..124d489
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Basic.c
@@ -0,0 +1,11 @@
+extern int BasicB(void);
+extern int BasicC(void);
+
+/* Use a symbol provided by a dedicated object file in A, B, and C.
+   The first library linked will determine the return value.  */
+extern int BasicX(void);
+
+int main(void)
+{
+  return BasicB() + BasicC() + BasicX();
+}
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/BasicA.c b/Tests/RunCMake/LinkLibrariesStrategy/BasicA.c
new file mode 100644
index 0000000..d3fe95d
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/BasicA.c
@@ -0,0 +1,4 @@
+int BasicA(void)
+{
+  return 0;
+}
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/BasicB.c b/Tests/RunCMake/LinkLibrariesStrategy/BasicB.c
new file mode 100644
index 0000000..fd7a120
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/BasicB.c
@@ -0,0 +1,5 @@
+extern int BasicA(void);
+int BasicB(void)
+{
+  return BasicA();
+}
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/BasicC.c b/Tests/RunCMake/LinkLibrariesStrategy/BasicC.c
new file mode 100644
index 0000000..7171dd1
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/BasicC.c
@@ -0,0 +1,5 @@
+extern int BasicA(void);
+int BasicC(void)
+{
+  return BasicA();
+}
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/BasicX.c b/Tests/RunCMake/LinkLibrariesStrategy/BasicX.c
new file mode 100644
index 0000000..39f7863
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/BasicX.c
@@ -0,0 +1,7 @@
+#include <stdio.h>
+
+int BasicX(void)
+{
+  printf("Library '%s' was linked first.\n", BASIC_ID);
+  return 0;
+}
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/CMakeLists.txt b/Tests/RunCMake/LinkLibrariesStrategy/CMakeLists.txt
new file mode 100644
index 0000000..dda37d8
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/CMakeLists.txt
@@ -0,0 +1,3 @@
+cmake_minimum_required(VERSION 3.30)
+project(${RunCMake_TEST} NONE)
+include(${RunCMake_TEST}.cmake)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-PRESERVE_ORDER-stderr.txt b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-PRESERVE_ORDER-stderr.txt
new file mode 100644
index 0000000..2637f93
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-PRESERVE_ORDER-stderr.txt
@@ -0,0 +1,15 @@
+target \[main\] link dependency ordering:
+  item \[-Flag1\]
+  target \[A\]
+  item \[-Flag1\]
+  target \[B\]
+  item \[-Flag2\]
+  target \[C\]
+  item \[-Flag2\]
+  target \[A\]
+  item \[-Flag2\]
+  target \[B\]
+  item \[-Flag3\]
+  target \[C\]
+
+target \[main\] link line:
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-PRESERVE_ORDER.cmake b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-PRESERVE_ORDER.cmake
new file mode 100644
index 0000000..9f694db
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-PRESERVE_ORDER.cmake
@@ -0,0 +1,2 @@
+set(CMAKE_LINK_LIBRARIES_STRATEGY PRESERVE_ORDER)
+include(Duplicate-common.cmake)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-REORDER-stderr.txt b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-REORDER-stderr.txt
new file mode 100644
index 0000000..2353288
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-REORDER-stderr.txt
@@ -0,0 +1,9 @@
+target \[main\] link dependency ordering:
+  item \[-Flag1\]
+  target \[A\]
+  target \[B\]
+  item \[-Flag2\]
+  target \[C\]
+  item \[-Flag3\]
+
+target \[main\] link line:
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-REORDER.cmake b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-REORDER.cmake
new file mode 100644
index 0000000..cc51e0a
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-REORDER.cmake
@@ -0,0 +1,2 @@
+set(CMAKE_LINK_LIBRARIES_STRATEGY REORDER)
+include(Duplicate-common.cmake)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-common.cmake b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-common.cmake
new file mode 100644
index 0000000..5050a0a
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate-common.cmake
@@ -0,0 +1,12 @@
+enable_language(C)
+
+add_library(A INTERFACE IMPORTED)
+add_library(B INTERFACE IMPORTED)
+add_library(C INTERFACE IMPORTED)
+set_property(TARGET A PROPERTY IMPORTED_LIBNAME A)
+set_property(TARGET B PROPERTY IMPORTED_LIBNAME B)
+set_property(TARGET C PROPERTY IMPORTED_LIBNAME C)
+
+add_executable(main Duplicate.c)
+target_link_libraries(main PRIVATE -Flag1 A -Flag1 B -Flag2 C -Flag2 A -Flag2 B -Flag3 C)
+set_property(TARGET main PROPERTY LINK_DEPENDS_DEBUG_MODE 1) # undocumented
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Duplicate.c b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate.c
new file mode 100644
index 0000000..8488f4e
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Duplicate.c
@@ -0,0 +1,4 @@
+int main(void)
+{
+  return 0;
+}
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Inspect.cmake b/Tests/RunCMake/LinkLibrariesStrategy/Inspect.cmake
new file mode 100644
index 0000000..fd5da91
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Inspect.cmake
@@ -0,0 +1,12 @@
+enable_language(C)
+
+set(info "")
+foreach(var
+    CMAKE_C_LINK_LIBRARIES_PROCESSING
+    )
+  if(DEFINED ${var})
+    string(APPEND info "set(${var} \"${${var}}\")\n")
+  endif()
+endforeach()
+
+file(WRITE "${CMAKE_CURRENT_BINARY_DIR}/info.cmake" "${info}")
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/RunCMakeTest.cmake b/Tests/RunCMake/LinkLibrariesStrategy/RunCMakeTest.cmake
new file mode 100644
index 0000000..1b02355
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/RunCMakeTest.cmake
@@ -0,0 +1,36 @@
+cmake_minimum_required(VERSION 3.30)
+
+include(RunCMake)
+
+if(RunCMake_GENERATOR_IS_MULTI_CONFIG)
+  set(RunCMake_TEST_OPTIONS -DCMAKE_CONFIGURATION_TYPES=Debug)
+else()
+  set(RunCMake_TEST_OPTIONS -DCMAKE_BUILD_TYPE=Debug)
+endif()
+
+# Detect information from the toolchain:
+# - CMAKE_C_LINK_LIBRARIES_PROCESSING
+run_cmake(Inspect)
+include("${RunCMake_BINARY_DIR}/Inspect-build/info.cmake")
+
+run_cmake(Unknown)
+
+function(run_strategy case exe)
+  set(RunCMake_TEST_BINARY_DIR ${RunCMake_BINARY_DIR}/${case}-build)
+  run_cmake(${case})
+  set(RunCMake_TEST_NO_CLEAN 1)
+  run_cmake_command(${case}-build ${CMAKE_COMMAND} --build . --config Debug)
+  if(exe)
+    if("ORDER=REVERSE" IN_LIST CMAKE_C_LINK_LIBRARIES_PROCESSING)
+      set(RunCMake-stdout-file ${case}-run-stdout-reverse.txt)
+    endif()
+    run_cmake_command(${case}-run ${RunCMake_TEST_BINARY_DIR}/${exe})
+    unset(RunCMake-stdout-file)
+  endif()
+endfunction()
+
+run_strategy(Basic-PRESERVE_ORDER "main")
+run_strategy(Basic-REORDER "main")
+
+run_cmake(Duplicate-PRESERVE_ORDER)
+run_cmake(Duplicate-REORDER)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Unknown-result.txt b/Tests/RunCMake/LinkLibrariesStrategy/Unknown-result.txt
new file mode 100644
index 0000000..d00491f
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Unknown-result.txt
@@ -0,0 +1 @@
+1
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Unknown-stderr.txt b/Tests/RunCMake/LinkLibrariesStrategy/Unknown-stderr.txt
new file mode 100644
index 0000000..3081f32
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Unknown-stderr.txt
@@ -0,0 +1,4 @@
+^CMake Error at Unknown.cmake:5 \(add_executable\):
+  LINK_LIBRARIES_STRATEGY value 'unknown' is not recognized\.
+Call Stack \(most recent call first\):
+  CMakeLists\.txt:[0-9] \(include\)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/Unknown.cmake b/Tests/RunCMake/LinkLibrariesStrategy/Unknown.cmake
new file mode 100644
index 0000000..d3ad586
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/Unknown.cmake
@@ -0,0 +1,5 @@
+enable_language(C)
+
+set(CMAKE_LINK_LIBRARIES_STRATEGY unknown)
+
+add_executable(main main.c)
diff --git a/Tests/RunCMake/LinkLibrariesStrategy/main.c b/Tests/RunCMake/LinkLibrariesStrategy/main.c
new file mode 100644
index 0000000..8488f4e
--- /dev/null
+++ b/Tests/RunCMake/LinkLibrariesStrategy/main.c
@@ -0,0 +1,4 @@
+int main(void)
+{
+  return 0;
+}