find_dependency: Avoid repeating identical dependency searches

Since commit 37da6af17d (find_dependency: Always search dependencies,
2019-03-29, v3.15.0-rc1~301^2) we search for a package every time it is
encountered in the transitive dependency graph traversal, even if it has
been found before.  This was done in case a new visit to a given package
requests different components than a previous visit.  However, it also
causes a lot of repeat processing that is unnecessary in the common case
that all calls share the same set of components (often none).

Restore the logic to avoid repeating the search for an already-found
package.  Handle differences in components by de-duplicating based on
the complete `find_package` call arguments.

Fixes: #23685

1 files changed, 59 insertions, 26 deletions

diff --git a/Modules/CMakeFindDependencyMacro.cmake b/Modules/CMakeFindDependencyMacro.cmake
index 921333b824..2c04abe507 100644
--- a/Modules/CMakeFindDependencyMacro.cmake
+++ b/Modules/CMakeFindDependencyMacro.cmake
@@ -3,7 +3,7 @@
 
 #[=======================================================================[.rst:
 CMakeFindDependencyMacro
--------------------------
+------------------------
 
 .. command:: find_dependency
 
@@ -28,37 +28,70 @@ CMakeFindDependencyMacro
 
     The call to :command:`return` makes this macro unsuitable to call
     from :ref:`Find Modules`.
+
+Package Dependency Search Optimizations
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+If ``find_dependency`` is called with arguments identical to a previous
+call in the same directory, perhaps due to diamond-shaped package
+dependencies, the underlying call to :command:`find_package` is optimized
+out.  This optimization is important to support large package dependency
+graphs while avoiding a combinatorial explosion of repeated searches.
+However, the heuristic cannot account for ambient variables that
+affect package behavior, such as ``<PackageName>_USE_STATIC_LIBS``,
+offered by some packages.  Therefore package configuration files should
+avoid setting such variables before their calls to ``find_dependency``.
+
+.. versionchanged:: 3.15
+  Previously, the underlying call to :command:`find_package` was always
+  optimized out if the package had already been found.  CMake 3.15
+  removed the optimization to support cases in which ``find_dependency``
+  call arguments request different components.
+
+.. versionchanged:: 3.26
+  The pre-3.15 optimization was restored, but with the above-described
+  heuristic to account for varying ``find_dependency`` call arguments.
+
 #]=======================================================================]
 
 macro(find_dependency dep)
-  set(cmake_fd_quiet_arg)
-  if(${CMAKE_FIND_PACKAGE_NAME}_FIND_QUIETLY)
-    set(cmake_fd_quiet_arg QUIET)
-  endif()
-  set(cmake_fd_required_arg)
-  if(${CMAKE_FIND_PACKAGE_NAME}_FIND_REQUIRED)
-    set(cmake_fd_required_arg REQUIRED)
-  endif()
+  string(SHA256 cmake_fd_call_hash "${dep};${ARGN};${${CMAKE_FIND_PACKAGE_NAME}_FIND_REQUIRED}")
+  if(_CMAKE_${dep}_${cmake_fd_call_hash}_FOUND)
+    unset(cmake_fd_call_hash)
+  else()
+    list(APPEND _CMAKE_${dep}_HASH_STACK ${cmake_fd_call_hash})
+    set(cmake_fd_quiet_arg)
+    if(${CMAKE_FIND_PACKAGE_NAME}_FIND_QUIETLY)
+      set(cmake_fd_quiet_arg QUIET)
+    endif()
+    set(cmake_fd_required_arg)
+    if(${CMAKE_FIND_PACKAGE_NAME}_FIND_REQUIRED)
+      set(cmake_fd_required_arg REQUIRED)
+    endif()
 
-  get_property(cmake_fd_alreadyTransitive GLOBAL PROPERTY
-    _CMAKE_${dep}_TRANSITIVE_DEPENDENCY
-  )
+    get_property(cmake_fd_alreadyTransitive GLOBAL PROPERTY
+      _CMAKE_${dep}_TRANSITIVE_DEPENDENCY
+      )
 
-  find_package(${dep} ${ARGN}
-    ${cmake_fd_quiet_arg}
-    ${cmake_fd_required_arg}
-  )
+    find_package(${dep} ${ARGN}
+      ${cmake_fd_quiet_arg}
+      ${cmake_fd_required_arg}
+      )
+    list(POP_BACK _CMAKE_${dep}_HASH_STACK cmake_fd_call_hash)
+    set("_CMAKE_${dep}_${cmake_fd_call_hash}_FOUND" "${${dep}_FOUND}")
 
-  if(NOT DEFINED cmake_fd_alreadyTransitive OR cmake_fd_alreadyTransitive)
-    set_property(GLOBAL PROPERTY _CMAKE_${dep}_TRANSITIVE_DEPENDENCY TRUE)
-  endif()
+    if(NOT DEFINED cmake_fd_alreadyTransitive OR cmake_fd_alreadyTransitive)
+      set_property(GLOBAL PROPERTY _CMAKE_${dep}_TRANSITIVE_DEPENDENCY TRUE)
+    endif()
 
-  unset(cmake_fd_alreadyTransitive)
-  unset(cmake_fd_quiet_arg)
-  unset(cmake_fd_required_arg)
-  if (NOT ${dep}_FOUND)
-    set(${CMAKE_FIND_PACKAGE_NAME}_NOT_FOUND_MESSAGE "${CMAKE_FIND_PACKAGE_NAME} could not be found because dependency ${dep} could not be found.")
-    set(${CMAKE_FIND_PACKAGE_NAME}_FOUND False)
-    return()
+    unset(cmake_fd_alreadyTransitive)
+    unset(cmake_fd_call_hash)
+    unset(cmake_fd_quiet_arg)
+    unset(cmake_fd_required_arg)
+    if (NOT ${dep}_FOUND)
+      set(${CMAKE_FIND_PACKAGE_NAME}_NOT_FOUND_MESSAGE "${CMAKE_FIND_PACKAGE_NAME} could not be found because dependency ${dep} could not be found.")
+      set(${CMAKE_FIND_PACKAGE_NAME}_FOUND False)
+      return()
+    endif()
   endif()
 endmacro()