Use dependencies.yaml to order sub modules

Don't rely on .gitmodules, instead parse the dependencies.yaml file from
every subdirectory with a CMakeLists.txt, and sort all projects based
on that data. Projects with no dependencies are added last.

This allows us to get rid of the duplication of dependency information
in .gitmodules, and makes each module the authoritative source of its
own dependencies.

Change-Id: Ib1ec6c63bde2aa1852399d598dac5b8e1efda31d
Reviewed-by: Alexandru Croitor <alexandru.croitor@qt.io>

2 files changed, 101 insertions, 59 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 2cd120be..0b438cee 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -19,32 +19,6 @@ project(Qt
 enable_testing()
 
 set(qt_module_prop_prefix "__qt_prop_")
-function(extract_git_submodules out_module_list)
-    set(current_module "")
-    set(module_list "")
-    file(STRINGS "${CMAKE_CURRENT_SOURCE_DIR}/.gitmodules" lines)
-    foreach(line IN LISTS lines)
-        # Skip empty lines.
-        if(NOT line)
-            continue()
-        endif()
-        string(REGEX REPLACE "^\\[submodule \"([^\"]+)\"\\]$" "\\1" module "${line}")
-        if (NOT module STREQUAL line)
-            set(current_module "${module}")
-            list(APPEND module_list "${module}")
-        else()
-            string(REGEX REPLACE "^\t([^ =]+) *=.*$" "\\1" prop "${line}")
-            if (NOT prop STREQUAL line)
-                string(REGEX REPLACE "^[^=]+= *" "" value "${line}")
-                string(REPLACE " " ";" value "${value}")
-                set("${qt_module_prop_prefix}${current_module}_${prop}" "${value}" PARENT_SCOPE)
-            else()
-                message(FATAL_ERROR "Malformed line ${CMAKE_CURRENT_SOURCE_DIR}/.gitmodules: ${line}")
-            endif()
-        endif()
-    endforeach()
-    set(${out_module_list} ${module_list} PARENT_SCOPE)
-endfunction()
 
 list(APPEND CMAKE_MODULE_PATH "${CMAKE_CURRENT_SOURCE_DIR}/cmake")
 if (NOT QT_BUILD_STANDALONE_TESTS)
@@ -54,8 +28,8 @@ if (NOT QT_BUILD_STANDALONE_TESTS)
     list(APPEND CMAKE_MODULE_PATH "${__qt6_qtbase_src_path}/cmake/3rdparty/kwin")
 endif()
 
+include("QtTopLevelHelpers")
 include(ECMOptionalAddSubdirectory)
-include(TopologicalSort)
 
 # Also make sure the CMake config files do not recreate the already-existing targets
 if (NOT QT_BUILD_STANDALONE_TESTS)
@@ -63,44 +37,27 @@ if (NOT QT_BUILD_STANDALONE_TESTS)
 endif()
 set(QT_SUPERBUILD TRUE)
 
-# Get submodules list
-extract_git_submodules(git_module_list)
-foreach(module IN LISTS git_module_list)
-    # Prepare a list of dependencies to be fed into topological sort
-    set("${qt_module_prop_prefix}${module}_all_dependencies"
-            ${${qt_module_prop_prefix}${module}_depends}
-            ${${qt_module_prop_prefix}${module}_recommends}
-            ${${qt_module_prop_prefix}${module}_serialize}
-    )
-endforeach()
-
-# Sort by dependencies
-topological_sort(git_module_list "${qt_module_prop_prefix}" "_all_dependencies")
-
-# Check for unknown modules
-foreach(module IN LISTS git_module_list)
-    foreach(dep IN LISTS "${qt_module_prop_prefix}${module}_all_dependencies")
-        if (NOT dep IN_LIST git_module_list)
-            message(FATAL_ERROR "Module '${module}' depends on undeclared module '${dep}'")
-        endif()
-    endforeach()
-endforeach()
+# Get submodule list if not already defined
+if (NOT BUILD_SUBMODULES)
+    qt_internal_find_modules(BUILD_SUBMODULES)
+endif()
 
-# qtbase is always needed
-list(REMOVE_ITEM git_module_list qtbase)
-add_subdirectory(qtbase)
+qt_internal_sort_module_dependencies("${BUILD_SUBMODULES}" BUILD_SUBMODULES)
 
-if (NOT QT_BUILD_STANDALONE_TESTS)
-    list(APPEND CMAKE_PREFIX_PATH "${QtBase_BINARY_DIR}/lib/cmake")
-    list(APPEND CMAKE_FIND_ROOT_PATH "${QtBase_BINARY_DIR}")
-endif()
+foreach(module IN LISTS BUILD_SUBMODULES)
+    message(NOTICE "Configuring '${module}'")
+    ecm_optional_add_subdirectory("${module}")
 
-foreach(module IN LISTS git_module_list)
-    ecm_optional_add_subdirectory(${module})
+    if(module STREQUAL "qtbase")
+        if (NOT QT_BUILD_STANDALONE_TESTS)
+            list(APPEND CMAKE_PREFIX_PATH "${QtBase_BINARY_DIR}/lib/cmake")
+            list(APPEND CMAKE_FIND_ROOT_PATH "${QtBase_BINARY_DIR}")
+        endif()
+    endif()
 endforeach()
 
 # Check for unmet dependencies
-foreach(module IN LISTS git_module_list)
+foreach(module IN LISTS BUILD_SUBMODULES)
     foreach(dep IN LISTS "${qt_module_prop_prefix}${module}_depends")
         if (dep STREQUAL qtbase)
             # Always available skip
diff --git a/cmake/QtTopLevelHelpers.cmake b/cmake/QtTopLevelHelpers.cmake
new file mode 100644
index 00000000..b9f4341a
--- /dev/null
+++ b/cmake/QtTopLevelHelpers.cmake
@@ -0,0 +1,85 @@
+# Populates $out_module_list with all subdirectories that have a CMakeLists.txt file
+function(qt_internal_find_modules out_module_list)
+    set(module_list "")
+    file(GLOB directories LIST_DIRECTORIES true RELATIVE "${CMAKE_CURRENT_SOURCE_DIR}" *)
+    foreach(directory IN LISTS directories)
+        if(IS_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}/${directory}"
+           AND EXISTS "${CMAKE_CURRENT_SOURCE_DIR}/${directory}/CMakeLists.txt")
+            list(APPEND module_list "${directory}")
+        endif()
+    endforeach()
+    message(DEBUG "qt_internal_find_modules: ${module_list}")
+    set(${out_module_list} "${module_list}" PARENT_SCOPE)
+endfunction()
+
+# poor man's yaml parser, populating $out_dependencies with all dependencies
+# in the $depends_file
+function(qt_internal_parse_dependencies depends_file out_dependencies)
+    file(STRINGS "${depends_file}" lines)
+    set(dependencies "")
+    foreach(line IN LISTS lines)
+        if(line STREQUAL "dependencies:")
+            set(found_dependencies 1)
+        elseif(found_dependencies AND line MATCHES "^  (.*):$")
+            set(dependency ${CMAKE_MATCH_1})
+            # dependencies are specified with relative path to this module
+            string(REPLACE "../" "" dependency ${dependency})
+            list(APPEND dependencies ${dependency})
+        endif()
+    endforeach()
+    message(DEBUG "qt_internal_parse_dependencies for ${depends_file}: ${module_list}")
+    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
+# 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)
+    set(depends_file "${CMAKE_CURRENT_SOURCE_DIR}/${module}/dependencies.yaml")
+    if(NOT EXISTS "${depends_file}")
+        set(${out_has_dependencies} "" PARENT_SCOPE)
+        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})
+    endif()
+    foreach(dependency IN LISTS dependencies)
+        list(FIND ordered "${dependency}" dindex)
+        if (dindex EQUAL -1)
+            # dependency hasnt' been seen yet - load it
+            list(INSERT ordered ${pindex} "${dependency}")
+            qt_internal_add_module_dependencies(${dependency} "${ordered}" ordered has_dependency)
+        elseif(dindex GREATER pindex)
+            # otherwise, make sure it is before module
+            list(REMOVE_AT ordered ${dindex})
+            list(INSERT ordered ${pindex} "${dependency}")
+        endif()
+    endforeach()
+    set(${out_ordered} "${ordered}" PARENT_SCOPE)
+endfunction()
+
+# populates $out_all_ordered with the sequence of the modules that need
+# to be built in order to build $modules
+function(qt_internal_sort_module_dependencies modules out_all_ordered)
+    set(ordered "")
+    foreach(module IN LISTS modules)
+        set(out_ordered "")
+        qt_internal_add_module_dependencies(${module} "${ordered}" out_ordered module_depends)
+        if(NOT module_depends)
+            list(APPEND no_dependencies "${module}")
+        endif()
+        set(ordered "${out_ordered}")
+    endforeach()
+    if (no_dependencies)
+        list(APPEND ordered "${no_dependencies}")
+    endif()
+    message(DEBUG "qt_internal_parse_dependencies sorted ${modules}: ${ordered}")
+    set(${out_all_ordered} "${ordered}" PARENT_SCOPE)
+endfunction()