CMake: Rework inter-repository dependency resolution

In certain cases the dependency resolution between Qt repositories
resulted in a wrong order, for example qtsvg being handled before
qtbase.  See the linked task for an example.

Replace the existing algorithm with a post-order traversal of the
dependency graph to produce a topological ordering.

Rename qt_internal_add_module_dependencies to
qt_internal_resolve_module_dependencies and remove unnecessary
positional arguments.  Use keyword arguments for a nicer API.

Raise the cmake_policy in QtSynchronizeRepo.cmake to avoid policy
warnings we now would get due to the use of IN_LIST.

Fixes: QTBUG-98268
Change-Id: I1425fd9c802fa71ae42549ceb14bcfc4c0a62078
Reviewed-by: Alexandru Croitor <alexandru.croitor@qt.io>
(cherry picked from commit 8a94d1e2946644253cf2979c35636cbfb850422d)
Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>

3 files changed, 127 insertions, 72 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index a0f4d76c..b1afb2f5 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -52,16 +52,15 @@ if(NOT QT_BUILD_SUBMODULES)
 endif()
 set(QT_BUILD_SUBMODULES "${QT_BUILD_SUBMODULES}" CACHE STRING "Submodules to build")
 
-set(qt_module_dependency_map_prefix "__qt_module_dependencies_")
-qt_internal_sort_module_dependencies("${QT_BUILD_SUBMODULES}" QT_BUILD_SUBMODULES
-                                     "${qt_module_dependency_map_prefix}")
+qt_internal_sort_module_dependencies("${QT_BUILD_SUBMODULES}" QT_BUILD_SUBMODULES)
 
 foreach(module IN LISTS QT_BUILD_SUBMODULES)
     # Check for unmet dependencies
     if(NOT DEFINED BUILD_${module} OR BUILD_${module})
         message(NOTICE "Checking dependencies of '${module}'")
         get_property(required_deps GLOBAL PROPERTY QT_REQUIRED_DEPS_FOR_${module})
-        foreach(dep IN LISTS "${qt_module_dependency_map_prefix}${module}")
+        get_property(dependencies GLOBAL PROPERTY QT_DEPS_FOR_${module})
+        foreach(dep IN LISTS dependencies)
             if (dep STREQUAL "qtbase")
                 # Always available skip
                 continue()
diff --git a/cmake/QtSynchronizeRepo.cmake b/cmake/QtSynchronizeRepo.cmake
index 522ea76e..5b379d0b 100644
--- a/cmake/QtSynchronizeRepo.cmake
+++ b/cmake/QtSynchronizeRepo.cmake
@@ -1,3 +1,7 @@
+# This script is to be called (ideally from a git-sync-to alias script):
+#     cmake -DSYNC_TO_MODULE="$1" -DSYNC_TO_BRANCH="$2" -P cmake/QtSynchronizeRepo.cmake
+
+cmake_policy(VERSION 3.16)
 include(cmake/QtTopLevelHelpers.cmake)
 
 qt_internal_sync_to(${SYNC_TO_MODULE} ${SYNC_TO_BRANCH})
diff --git a/cmake/QtTopLevelHelpers.cmake b/cmake/QtTopLevelHelpers.cmake
index 2d06a8fd..bd511cdd 100644
--- a/cmake/QtTopLevelHelpers.cmake
+++ b/cmake/QtTopLevelHelpers.cmake
@@ -14,7 +14,7 @@ endfunction()
 
 # poor man's yaml parser, populating $out_dependencies with all dependencies
 # in the $depends_file
-# Each entry will be in the format dependency/sha1
+# Each entry will be in the format dependency/sha1/required
 function(qt_internal_parse_dependencies depends_file out_dependencies)
     file(STRINGS "${depends_file}" lines)
     set(eof_marker "---EOF---")
@@ -51,86 +51,141 @@ function(qt_internal_parse_dependencies depends_file out_dependencies)
     set(${out_dependencies} "${dependencies}" PARENT_SCOPE)
 endfunction()
 
-# Load $module and populate $out_ordered with the submodules based on their dependencies
-# $ordered carries already sorted dependencies; $out_has_dependencies is left empty
-# if there are no dependencies, otherwise set to 1; Save list of dependencies for $module into
-# $out_module_dependencies. List may contain duplicates, since function checks max depth
-# dependencies.
-# Function calls itself recursively if a dependency is found that is not yet in $ordered.
-function(qt_internal_add_module_dependencies module ordered out_ordered out_has_dependencies
-                                             out_module_dependencies out_revisions)
-    set(depends_file "${CMAKE_CURRENT_SOURCE_DIR}/${module}/dependencies.yaml")
-    if(NOT EXISTS "${depends_file}")
-        set(${out_has_dependencies} "" PARENT_SCOPE)
+# Helper macro for qt_internal_resolve_module_dependencies.
+macro(qt_internal_resolve_module_dependencies_set_skipped value)
+    if(DEFINED arg_SKIPPED_VAR)
+        set(${arg_SKIPPED_VAR} ${value} PARENT_SCOPE)
+    endif()
+endmacro()
+
+# Resolve the dependencies of the given module.
+# "Module" in the sense of Qt repository.
+#
+# Side effects: Sets the global properties QT_DEPS_FOR_${module} and QT_REQUIRED_DEPS_FOR_${module}
+# with the direct (required) dependencies of module.
+#
+#
+# Positional arguments:
+#
+# module is the Qt repository.
+#
+# out_ordered is where the result is stored. This is a list of all dependencies, including
+# transitive ones, in topologically sorted order.
+#
+# out_revisions is a list of git commit IDs for each of the dependencies in ${out_ordered}. This
+# list has the same length as ${out_ordered}.
+#
+#
+# Keyword arguments:
+#
+# PARSED_DEPENDENCIES is a list of dependencies of module in the format that
+# qt_internal_parse_dependencies returns. If this argument is not provided, dependencies.yaml of the
+# module is parsed.
+#
+# IN_RECURSION is an internal option that is set when the function is in recursion.
+#
+# REVISION is an internal value with the git commit ID that belongs to ${module}.
+#
+# SKIPPED_VAR is an output variable name that is set to TRUE if the module was skipped, to FALSE
+# otherwise.
+function(qt_internal_resolve_module_dependencies module out_ordered out_revisions)
+    set(options IN_RECURSION)
+    set(oneValueArgs REVISION SKIPPED_VAR)
+    set(multiValueArgs PARSED_DEPENDENCIES)
+    cmake_parse_arguments(arg "${options}" "${oneValueArgs}" "${multiValueArgs}" ${ARGN})
+
+    # Clear the property that stores the repositories we've already seen.
+    if(NOT arg_IN_RECURSION)
+        set_property(GLOBAL PROPERTY _qt_internal_seen_repos)
+    endif()
+
+    # Bail out if we've seen the module already.
+    qt_internal_resolve_module_dependencies_set_skipped(FALSE)
+    get_property(seen GLOBAL PROPERTY _qt_internal_seen_repos)
+    if(module IN_LIST seen)
+        qt_internal_resolve_module_dependencies_set_skipped(TRUE)
         return()
     endif()
-    set(${out_has_dependencies} "1" PARENT_SCOPE)
-    set(dependencies "")
-    qt_internal_parse_dependencies("${depends_file}" dependencies)
-    # module hasn't been seen yet, append it
-    list(FIND ordered "${module}" pindex)
-    if (pindex EQUAL -1)
-        list(LENGTH ordered pindex)
-        list(APPEND ordered "${module}")
-        list(APPEND revisions "HEAD")
+
+    set_property(GLOBAL APPEND PROPERTY _qt_internal_seen_repos ${module})
+
+    # Set a default REVISION.
+    if("${arg_REVISION}" STREQUAL "")
+        set(arg_REVISION HEAD)
     endif()
-    set(modules_dependencies "")
+
+    # Retrieve the dependencies.
+    if(DEFINED arg_PARSED_DEPENDENCIES)
+        set(dependencies "${arg_PARSED_DEPENDENCIES}")
+    else()
+        set(depends_file "${CMAKE_CURRENT_SOURCE_DIR}/${module}/dependencies.yaml")
+        if(NOT EXISTS "${depends_file}")
+            qt_internal_resolve_module_dependencies_set_skipped(TRUE)
+            return()
+        endif()
+        set(dependencies "")
+        qt_internal_parse_dependencies("${depends_file}" dependencies)
+    endif()
+
+    # Traverse the dependencies.
+    set(ordered)
+    set(revisions)
     foreach(dependency IN LISTS dependencies)
         if(dependency MATCHES "(.*)/([^/]+)/([^/]+)")
             set(dependency "${CMAKE_MATCH_1}")
             set(revision "${CMAKE_MATCH_2}")
             set(required "${CMAKE_MATCH_3}")
-            if(required)
-                set_property(GLOBAL APPEND PROPERTY QT_REQUIRED_DEPS_FOR_${module} ${dependency})
-            endif()
         else()
             message(FATAL_ERROR "Internal Error: wrong dependency format ${dependency}")
         endif()
-        list(APPEND modules_dependencies "${dependency}")
-        list(FIND ordered "${dependency}" dindex)
-        if (dindex EQUAL -1)
-            # dependency hasnt' been seen yet - load it
-            list(INSERT ordered ${pindex} "${dependency}")
-            list(INSERT revisions ${pindex} "${revision}")
-            qt_internal_add_module_dependencies(${dependency} "${ordered}" ordered has_dependency
-                                                "${out_module_dependencies}" revisions)
-        elseif(dindex GREATER pindex)
-            # otherwise, make sure it is before module
-            list(REMOVE_AT ordered ${dindex})
-            list(REMOVE_AT revisions ${dindex})
-            list(INSERT ordered ${pindex} "${dependency}")
-            list(INSERT revisions ${pindex} "${revision}")
+
+        set_property(GLOBAL APPEND PROPERTY QT_DEPS_FOR_${module} ${dependency})
+        if(required)
+            set_property(GLOBAL APPEND PROPERTY QT_REQUIRED_DEPS_FOR_${module} ${dependency})
+        endif()
+
+        qt_internal_resolve_module_dependencies(${dependency} dep_ordered dep_revisions
+            REVISION "${revision}"
+            SKIPPED_VAR skipped
+            IN_RECURSION)
+        if(NOT skipped)
+            list(APPEND ordered ${dep_ordered})
+            list(APPEND revisions ${dep_revisions})
         endif()
     endforeach()
+
+    list(APPEND ordered ${module})
+    list(APPEND revisions ${arg_REVISION})
     set(${out_ordered} "${ordered}" PARENT_SCOPE)
-    set(${out_module_dependencies} ${${out_module_dependencies}} ${modules_dependencies} PARENT_SCOPE)
     set(${out_revisions} "${revisions}" PARENT_SCOPE)
 endfunction()
 
-# populates $out_all_ordered with the sequence of the modules that need
-# to be built in order to build $modules; dependencies for each module are populated
-# in variables with specified in $dependencies_map_prefix prefix
-function(qt_internal_sort_module_dependencies modules out_all_ordered dependencies_map_prefix)
-    set(ordered "")
+# Resolves the dependencies of the given modules.
+# "Module" is here used in the sense of Qt repository.
+#
+# Returns all dependencies, including transitive ones, in topologically sorted order.
+#
+# Arguments:
+# modules is the initial list of repos.
+# out_all_ordered is the variable name where the result is stored.
+#
+# See qt_internal_resolve_module_dependencies for side effects.
+function(qt_internal_sort_module_dependencies modules out_all_ordered)
+
+    # Create a fake repository "all_selected_repos" that has all repositories from the input as
+    # required dependency. The format must match what qt_internal_parse_dependencies produces.
+    set(all_selected_repos_as_parsed_dependencies)
     foreach(module IN LISTS modules)
-        set(out_ordered "")
-        if(NOT dependencies_map_prefix)
-            message(FATAL_ERROR "dependencies_map_prefix is not provided")
-        endif()
-        set(module_dependencies_list_var_name "${dependencies_map_prefix}${module}")
-        qt_internal_add_module_dependencies(${module} "${ordered}" out_ordered module_depends
-                                            "${module_dependencies_list_var_name}" revisions)
-        set(${module_dependencies_list_var_name}
-                "${${module_dependencies_list_var_name}}" PARENT_SCOPE)
-        if(NOT module_depends)
-            list(APPEND no_dependencies "${module}")
-        else()
-            set(ordered "${out_ordered}")
-        endif()
+        list(APPEND all_selected_repos_as_parsed_dependencies "${module}/HEAD/FALSE")
     endforeach()
-    if (no_dependencies)
-        list(APPEND ordered "${no_dependencies}")
-    endif()
+
+    qt_internal_resolve_module_dependencies(all_selected_repos ordered unused_revisions
+        PARSED_DEPENDENCIES ${all_selected_repos_as_parsed_dependencies})
+
+    # Drop "all_selected_repos" from the output. It depends on all selected repos, thus it must be
+    # the last element in the topologically sorted list.
+    list(REMOVE_AT ordered -1)
+
     message(DEBUG "qt_internal_parse_dependencies sorted ${modules}: ${ordered}")
     set(${out_all_ordered} "${ordered}" PARENT_SCOPE)
 endfunction()
@@ -275,19 +330,16 @@ function(qt_internal_sync_to module)
     # Repeat everything (we need to reload dependencies after each checkout) until no more checkouts
     # are done.
     while(${checkedout})
-        set(dependencies "")
-        set(revisions "")
-        set(prefix "")
-        qt_internal_add_module_dependencies(${module} "${dependencies}" dependencies has_dependencies prefix revisions)
+        qt_internal_resolve_module_dependencies(${module} dependencies revisions)
         message(DEBUG "${module} dependencies: ${dependencies}")
         message(DEBUG "${module} revisions   : ${revisions}")
 
-        if (NOT has_dependencies)
+        list(LENGTH dependencies count)
+        if (count EQUAL "0")
             message(NOTICE "Module ${module} has no dependencies")
             return()
         endif()
 
-        list(LENGTH dependencies count)
         math(EXPR count "${count} - 1")
         set(checkedout 0)
         foreach(i RANGE ${count} 0 -1 )