async maps: Create utility library to handle cycle detection

15 files changed, 152 insertions, 85 deletions

diff --git a/src/buildtool/build_engine/base_maps/expression_map.hpp b/src/buildtool/build_engine/base_maps/expression_map.hpp
index 5d08b78b..3a72c109 100644
--- a/src/buildtool/build_engine/base_maps/expression_map.hpp
+++ b/src/buildtool/build_engine/base_maps/expression_map.hpp
@@ -15,6 +15,7 @@
 #ifndef INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_BASE_MAPS_EXPRESSION_MAP_HPP
 #define INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_BASE_MAPS_EXPRESSION_MAP_HPP
 
+#include <functional>
 #include <memory>
 #include <string>
 
@@ -43,6 +44,10 @@ auto CreateExpressionMap(gsl::not_null<ExpressionFileMap*> const& expr_file_map,
                          gsl::not_null<RepositoryConfig*> const& repo_config,
                          std::size_t jobs = 0) -> ExpressionFunctionMap;
 
+// use explicit cast to std::function to allow template deduction when used
+static const std::function<std::string(EntityName const&)> kEntityNamePrinter =
+    [](EntityName const& x) -> std::string { return x.ToString(); };
+
 }  // namespace BuildMaps::Base
 
 #endif  // INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_BASE_MAPS_EXPRESSION_MAP_HPP
diff --git a/src/buildtool/build_engine/target_map/TARGETS b/src/buildtool/build_engine/target_map/TARGETS
index 6878ab41..5886f784 100644
--- a/src/buildtool/build_engine/target_map/TARGETS
+++ b/src/buildtool/build_engine/target_map/TARGETS
@@ -47,14 +47,14 @@
     , ["src/buildtool/build_engine/base_maps", "targets_file_map"]
     , ["src/buildtool/common", "config"]
     , ["src/buildtool/multithreading", "async_map_consumer"]
-    , ["src/utils/cpp", "gsl"]
-    , ["@", "fmt", "", "fmt"]
     , ["@", "gsl", "", "gsl"]
     , ["@", "json", "", "json"]
     ]
   , "stage": ["src", "buildtool", "build_engine", "target_map"]
   , "private-deps":
-    [ ["src/buildtool/common", "common"]
+    [ ["@", "fmt", "", "fmt"]
+    , ["src/utils/cpp", "gsl"]
+    , ["src/buildtool/common", "common"]
     , ["src/buildtool/storage", "storage"]
     , ["src/buildtool/build_engine/base_maps", "entity_name"]
     , ["src/buildtool/build_engine/base_maps", "field_reader"]
diff --git a/src/buildtool/build_engine/target_map/target_map.cpp b/src/buildtool/build_engine/target_map/target_map.cpp
index 52cc6d4b..2322ba54 100644
--- a/src/buildtool/build_engine/target_map/target_map.cpp
+++ b/src/buildtool/build_engine/target_map/target_map.cpp
@@ -23,8 +23,6 @@
 #include <fnmatch.h>
 
 #include "fmt/core.h"
-#include "gsl/gsl"
-#include "nlohmann/json.hpp"
 #include "src/buildtool/build_engine/base_maps/field_reader.hpp"
 #include "src/buildtool/build_engine/expression/configuration.hpp"
 #include "src/buildtool/build_engine/expression/evaluator.hpp"
diff --git a/src/buildtool/build_engine/target_map/target_map.hpp b/src/buildtool/build_engine/target_map/target_map.hpp
index e1cb0a94..bcd902cc 100644
--- a/src/buildtool/build_engine/target_map/target_map.hpp
+++ b/src/buildtool/build_engine/target_map/target_map.hpp
@@ -15,7 +15,11 @@
 #ifndef INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_TARGET_MAP_TARGET_MAP_HPP
 #define INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_TARGET_MAP_TARGET_MAP_HPP
 
+#include <functional>
+#include <string>
+
 #include "gsl/gsl"
+#include "nlohmann/json.hpp"
 #include "src/buildtool/build_engine/analysed_target/analysed_target.hpp"
 #include "src/buildtool/build_engine/base_maps/rule_map.hpp"
 #include "src/buildtool/build_engine/base_maps/source_map.hpp"
@@ -40,6 +44,11 @@ auto CreateTargetMap(
     [[maybe_unused]] const gsl::not_null<RepositoryConfig*>&,
     std::size_t jobs = 0) -> TargetMap;
 
+// use explicit cast to std::function to allow template deduction when used
+static const std::function<std::string(ConfiguredTarget const&)>
+    kConfiguredTargetPrinter =
+        [](ConfiguredTarget const& x) -> std::string { return x.ToString(); };
+
 auto IsBuiltInRule(nlohmann::json const& rule_type) -> bool;
 
 }  // namespace BuildMaps::Target
diff --git a/src/buildtool/file_system/symlinks_map/resolve_symlinks_map.cpp b/src/buildtool/file_system/symlinks_map/resolve_symlinks_map.cpp
index 1ae5db8b..5c9dd89b 100644
--- a/src/buildtool/file_system/symlinks_map/resolve_symlinks_map.cpp
+++ b/src/buildtool/file_system/symlinks_map/resolve_symlinks_map.cpp
@@ -310,26 +310,3 @@ auto CreateResolveSymlinksMap() -> ResolveSymlinksMap {
     return AsyncMapConsumer<GitObjectToResolve, ResolvedGitObject>(
         resolve_symlinks);
 }
-
-auto DetectAndReportCycle(ResolveSymlinksMap const& map,
-                          std::string const& root_tree_id)
-    -> std::optional<std::string> {
-    using namespace std::string_literals;
-    auto cycle = map.DetectCycle();
-    if (cycle) {
-        bool found{false};
-        std::ostringstream oss{};
-        oss << fmt::format("Cycle detected for Git tree {}:", root_tree_id)
-            << std::endl;
-        for (auto const& k : *cycle) {
-            auto match = (k == cycle->back());
-            auto prefix{match   ? found ? "`-- "s : ".-> "s
-                        : found ? "|   "s
-                                : "    "s};
-            oss << prefix << k.rel_path << std::endl;
-            found = found or match;
-        }
-        return oss.str();
-    }
-    return std::nullopt;
-}
diff --git a/src/buildtool/file_system/symlinks_map/resolve_symlinks_map.hpp b/src/buildtool/file_system/symlinks_map/resolve_symlinks_map.hpp
index 55254a30..a02a8de2 100644
--- a/src/buildtool/file_system/symlinks_map/resolve_symlinks_map.hpp
+++ b/src/buildtool/file_system/symlinks_map/resolve_symlinks_map.hpp
@@ -16,6 +16,7 @@
 #define INCLUDED_SRC_BUILDTOOL_FILE_SYSTEM_SYMLINKS_MAP_RESOLVE_SYMLINKS_MAP_HPP
 
 #include <filesystem>
+#include <functional>
 #include <optional>
 #include <string>
 
@@ -75,11 +76,12 @@ struct ResolvedGitObject {
 using ResolveSymlinksMap =
     AsyncMapConsumer<GitObjectToResolve, ResolvedGitObject>;
 
-[[nodiscard]] auto CreateResolveSymlinksMap() -> ResolveSymlinksMap;
+// use explicit cast to std::function to allow template deduction when used
+static const std::function<std::string(GitObjectToResolve const&)>
+    kGitObjectToResolvePrinter =
+        [](GitObjectToResolve const& x) -> std::string { return x.rel_path; };
 
-[[nodiscard]] auto DetectAndReportCycle(ResolveSymlinksMap const& map,
-                                        std::string const& root_tree_id)
-    -> std::optional<std::string>;
+[[nodiscard]] auto CreateResolveSymlinksMap() -> ResolveSymlinksMap;
 
 namespace std {
 template <>
diff --git a/src/buildtool/main/TARGETS b/src/buildtool/main/TARGETS
index 944f94dc..af2998f1 100644
--- a/src/buildtool/main/TARGETS
+++ b/src/buildtool/main/TARGETS
@@ -120,11 +120,15 @@
   , "stage": ["src", "buildtool", "main"]
   , "private-deps":
     [ ["src/buildtool/multithreading", "async_map_consumer"]
+    , ["src/buildtool/multithreading", "async_map_utils"]
     , ["src/buildtool/multithreading", "task_system"]
+    , ["src/buildtool/build_engine/base_maps", "entity_name"]
+    , ["src/buildtool/build_engine/base_maps", "expression_map"]
     , ["src/buildtool/build_engine/base_maps", "directory_map"]
     , ["src/buildtool/build_engine/base_maps", "rule_map"]
     , ["src/buildtool/build_engine/base_maps", "source_map"]
     , ["src/buildtool/build_engine/base_maps", "targets_file_map"]
+    , ["src/buildtool/build_engine/target_map", "absent_target_map"]
     , ["src/buildtool/build_engine/target_map", "target_map"]
     , ["src/buildtool/serve_api/progress_reporting", "progress_reporter"]
     ]
diff --git a/src/buildtool/main/analyse.cpp b/src/buildtool/main/analyse.cpp
index 19656b81..6e8aeccc 100644
--- a/src/buildtool/main/analyse.cpp
+++ b/src/buildtool/main/analyse.cpp
@@ -29,6 +29,7 @@
 #include "src/buildtool/build_engine/target_map/absent_target_map.hpp"
 #include "src/buildtool/build_engine/target_map/target_map.hpp"
 #include "src/buildtool/multithreading/async_map_consumer.hpp"
+#include "src/buildtool/multithreading/async_map_utils.hpp"
 #include "src/buildtool/multithreading/task_system.hpp"
 #ifndef BOOTSTRAP_BUILD_TOOL
 #include "src/buildtool/serve_api/progress_reporting/progress_reporter.hpp"
@@ -39,47 +40,6 @@ namespace {
 namespace Base = BuildMaps::Base;
 namespace Target = BuildMaps::Target;
 
-template <HasToString K, typename V>
-[[nodiscard]] auto DetectAndReportCycle(std::string const& name,
-                                        AsyncMapConsumer<K, V> const& map)
-    -> bool {
-    using namespace std::string_literals;
-    auto cycle = map.DetectCycle();
-    if (cycle) {
-        bool found{false};
-        std::ostringstream oss{};
-        oss << fmt::format("Cycle detected in {}:", name) << std::endl;
-        for (auto const& k : *cycle) {
-            auto match = (k == cycle->back());
-            auto prefix{match   ? found ? "`-- "s : ".-> "s
-                        : found ? "|   "s
-                                : "    "s};
-            oss << prefix << k.ToString() << std::endl;
-            found = found or match;
-        }
-        Logger::Log(LogLevel::Error, "{}", oss.str());
-        return true;
-    }
-    return false;
-}
-
-template <HasToString K, typename V>
-void DetectAndReportPending(std::string const& name,
-                            AsyncMapConsumer<K, V> const& map) {
-    using namespace std::string_literals;
-    auto keys = map.GetPendingKeys();
-    if (not keys.empty()) {
-        std::ostringstream oss{};
-        oss << fmt::format("Internal error, failed to evaluate pending {}:",
-                           name)
-            << std::endl;
-        for (auto const& k : keys) {
-            oss << "  " << k.ToString() << std::endl;
-        }
-        Logger::Log(LogLevel::Error, "{}", oss.str());
-    }
-}
-
 [[nodiscard]] auto GetActionNumber(const AnalysedTarget& target, int number)
     -> std::optional<ActionDescription::Ptr> {
     auto const& actions = target.Actions();
@@ -200,11 +160,20 @@ void DetectAndReportPending(std::string const& name,
     if (not target) {
         Logger::Log(
             LogLevel::Error, "Failed to analyse target: {}", id.ToString());
-        if (not(DetectAndReportCycle("expression imports", expr_map) or
-                DetectAndReportCycle("target dependencies", target_map))) {
-            DetectAndReportPending("expressions", expr_map);
-            DetectAndReportPending("targets", expr_map);
+        if (auto error_msg = DetectAndReportCycle(
+                "expression imports", expr_map, Base::kEntityNamePrinter)) {
+            Logger::Log(LogLevel::Error, *error_msg);
+            return std::nullopt;
+        }
+        if (auto error_msg =
+                DetectAndReportCycle("target dependencies",
+                                     target_map,
+                                     Target::kConfiguredTargetPrinter)) {
+            Logger::Log(LogLevel::Error, *error_msg);
+            return std::nullopt;
         }
+        DetectAndReportPending("expressions", expr_map);
+        DetectAndReportPending("targets", expr_map);
         return std::nullopt;
     }
 
diff --git a/src/buildtool/multithreading/TARGETS b/src/buildtool/multithreading/TARGETS
index e750c943..2a1fc119 100644
--- a/src/buildtool/multithreading/TARGETS
+++ b/src/buildtool/multithreading/TARGETS
@@ -57,4 +57,16 @@
   , "deps": [["src/utils/cpp", "atomic"]]
   , "stage": ["src", "buildtool", "multithreading"]
   }
+, "async_map_utils":
+  { "type": ["@", "rules", "CC", "library"]
+  , "name": ["async_map_utils"]
+  , "hdrs": ["async_map_utils.hpp"]
+  , "deps":
+    [ "async_map_consumer"
+    , ["@", "fmt", "", "fmt"]
+    , ["src/buildtool/logging", "logging"]
+    , ["src/utils/cpp", "concepts"]
+    ]
+  , "stage": ["src", "buildtool", "multithreading"]
+  }
 }
diff --git a/src/buildtool/multithreading/async_map_utils.hpp b/src/buildtool/multithreading/async_map_utils.hpp
new file mode 100644
index 00000000..03469b02
--- /dev/null
+++ b/src/buildtool/multithreading/async_map_utils.hpp
@@ -0,0 +1,81 @@
+// Copyright 2024 Huawei Cloud Computing Technology Co., Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef INCLUDED_SRC_BUILDTOOL_MULTITHREADING_ASYNC_MAP_UTILS_HPP
+#define INCLUDED_SRC_BUILDTOOL_MULTITHREADING_ASYNC_MAP_UTILS_HPP
+
+#include <functional>
+#include <optional>
+#include <sstream>
+#include <string>
+
+#include "fmt/core.h"
+#include "src/buildtool/logging/log_level.hpp"
+#include "src/buildtool/logging/logger.hpp"
+#include "src/buildtool/multithreading/async_map_consumer.hpp"
+#include "src/utils/cpp/concepts.hpp"
+
+/// \brief Utility to detect and report cycles for an AsyncMap instance.
+/// \param name Human-readable string identifier related to the map or its use.
+/// \param map The AsyncMap instance.
+/// \param key_printer Callable returning key-specific identifier in string
+/// format.
+/// \returns The resulting cycle message as a string, or nullopt if no cycle
+/// detected.
+template <typename K, typename V>
+[[nodiscard]] auto DetectAndReportCycle(
+    std::string const& name,
+    AsyncMapConsumer<K, V> const& map,
+    std::function<std::string(K const&)> key_printer)
+    -> std::optional<std::string> {
+    using namespace std::string_literals;
+    auto cycle = map.DetectCycle();
+    if (cycle) {
+        bool found{false};
+        std::ostringstream oss{};
+        oss << fmt::format("Cycle detected in {}:", name) << std::endl;
+        for (auto const& k : *cycle) {
+            auto match = (k == cycle->back());
+            auto prefix{match   ? found ? "`-- "s : ".-> "s
+                        : found ? "|   "s
+                                : "    "s};
+            oss << prefix << key_printer(k) << std::endl;
+            found = found or match;
+        }
+        return oss.str();
+    }
+    return std::nullopt;
+}
+
+/// \brief Utility to detect and report pending tasks for an AsyncMap instance.
+/// \param name Human-readable string identifier related to the map or its use.
+/// \param map The AsyncMap instance.
+template <HasToString K, typename V>
+void DetectAndReportPending(std::string const& name,
+                            AsyncMapConsumer<K, V> const& map) {
+    using namespace std::string_literals;
+    auto keys = map.GetPendingKeys();
+    if (not keys.empty()) {
+        std::ostringstream oss{};
+        oss << fmt::format("Internal error, failed to evaluate pending {}:",
+                           name)
+            << std::endl;
+        for (auto const& k : keys) {
+            oss << "  " << k.ToString() << std::endl;
+        }
+        Logger::Log(LogLevel::Error, "{}", oss.str());
+    }
+}
+
+#endif  // INCLUDED_SRC_BUILDTOOL_MULTITHREADING_ASYNC_MAP_UTILS_HPP
diff --git a/src/buildtool/serve_api/serve_service/TARGETS b/src/buildtool/serve_api/serve_service/TARGETS
index 26c407df..3790774d 100644
--- a/src/buildtool/serve_api/serve_service/TARGETS
+++ b/src/buildtool/serve_api/serve_service/TARGETS
@@ -30,6 +30,7 @@
     , ["src/buildtool/execution_api/local", "local"]
     , ["src/buildtool/execution_api/remote", "bazel"]
     , ["src/buildtool/file_system", "git_repo"]
+    , ["src/buildtool/multithreading", "async_map_utils"]
     , ["src/buildtool/serve_api/remote", "config"]
     , ["src/buildtool/storage", "config"]
     , ["src/buildtool/storage", "fs_utils"]
diff --git a/src/buildtool/serve_api/serve_service/source_tree.cpp b/src/buildtool/serve_api/serve_service/source_tree.cpp
index 609775ab..5d4f0a5f 100644
--- a/src/buildtool/serve_api/serve_service/source_tree.cpp
+++ b/src/buildtool/serve_api/serve_service/source_tree.cpp
@@ -25,6 +25,7 @@
 #include "src/buildtool/execution_api/remote/bazel/bazel_api.hpp"
 #include "src/buildtool/file_system/file_system_manager.hpp"
 #include "src/buildtool/file_system/git_repo.hpp"
+#include "src/buildtool/multithreading/async_map_utils.hpp"
 #include "src/buildtool/serve_api/remote/config.hpp"
 #include "src/buildtool/storage/config.hpp"
 #include "src/buildtool/storage/fs_utils.hpp"
@@ -387,8 +388,10 @@ auto SourceTreeService::ResolveContentTree(
             return ::grpc::Status::OK;
         }
         // check for cycles
-        auto error = DetectAndReportCycle(resolve_symlinks_map_, tree_id);
-        if (error) {
+        if (auto error = DetectAndReportCycle(
+                fmt::format("resolving Git tree {}", tree_id),
+                resolve_symlinks_map_,
+                kGitObjectToResolvePrinter)) {
             auto str = fmt::format(
                 "Failed to resolve symlinks in tree {}:\n{}", tree_id, *error);
             logger_->Emit(LogLevel::Error, str);
diff --git a/src/other_tools/root_maps/TARGETS b/src/other_tools/root_maps/TARGETS
index 1bc7c2f9..5081b512 100644
--- a/src/other_tools/root_maps/TARGETS
+++ b/src/other_tools/root_maps/TARGETS
@@ -86,6 +86,7 @@
     , ["src/buildtool/execution_api/local", "config"]
     , ["src/buildtool/file_system", "file_root"]
     , ["src/buildtool/file_system", "git_repo"]
+    , ["src/buildtool/multithreading", "async_map_utils"]
     , ["src/buildtool/multithreading", "task_system"]
     , ["src/buildtool/storage", "config"]
     , ["src/buildtool/storage", "fs_utils"]
@@ -117,6 +118,7 @@
     , ["src/buildtool/file_system", "file_storage"]
     , ["src/buildtool/file_system", "git_repo"]
     , ["src/buildtool/file_system/symlinks_map", "pragma_special"]
+    , ["src/buildtool/multithreading", "async_map_utils"]
     , ["src/buildtool/multithreading", "task_system"]
     , ["src/buildtool/serve_api/remote", "serve_api"]
     , ["src/buildtool/storage", "storage"]
diff --git a/src/other_tools/root_maps/content_git_map.cpp b/src/other_tools/root_maps/content_git_map.cpp
index 5d910015..0a70cb0c 100644
--- a/src/other_tools/root_maps/content_git_map.cpp
+++ b/src/other_tools/root_maps/content_git_map.cpp
@@ -18,6 +18,7 @@
 #include "src/buildtool/file_system/file_root.hpp"
 #include "src/buildtool/file_system/file_storage.hpp"
 #include "src/buildtool/file_system/symlinks_map/pragma_special.hpp"
+#include "src/buildtool/multithreading/async_map_utils.hpp"
 #include "src/buildtool/multithreading/task_system.hpp"
 #include "src/buildtool/serve_api/remote/serve_api.hpp"
 #include "src/buildtool/storage/config.hpp"
@@ -206,9 +207,10 @@ void ResolveContentTree(
                  logger](auto const& hashes) {
                     if (not hashes[0]) {
                         // check for cycles
-                        auto error = DetectAndReportCycle(*resolve_symlinks_map,
-                                                          tree_hash);
-                        if (error) {
+                        if (auto error = DetectAndReportCycle(
+                                fmt::format("resolving Git tree {}", tree_hash),
+                                *resolve_symlinks_map,
+                                kGitObjectToResolvePrinter)) {
                             (*logger)(fmt::format("Failed to resolve symlinks "
                                                   "in tree {}:\n{}",
                                                   tree_hash,
diff --git a/src/other_tools/root_maps/fpath_git_map.cpp b/src/other_tools/root_maps/fpath_git_map.cpp
index 11344de1..bb6b5a83 100644
--- a/src/other_tools/root_maps/fpath_git_map.cpp
+++ b/src/other_tools/root_maps/fpath_git_map.cpp
@@ -18,6 +18,7 @@
 #include "src/buildtool/execution_api/local/config.hpp"
 #include "src/buildtool/file_system/file_root.hpp"
 #include "src/buildtool/file_system/git_repo.hpp"
+#include "src/buildtool/multithreading/async_map_utils.hpp"
 #include "src/buildtool/multithreading/task_system.hpp"
 #include "src/buildtool/storage/config.hpp"
 #include "src/buildtool/storage/fs_utils.hpp"
@@ -127,9 +128,10 @@ void ResolveFilePathTree(
                  logger](auto const& hashes) {
                     if (not hashes[0]) {
                         // check for cycles
-                        auto error = DetectAndReportCycle(*resolve_symlinks_map,
-                                                          tree_hash);
-                        if (error) {
+                        if (auto error = DetectAndReportCycle(
+                                fmt::format("resolving Git tree {}", tree_hash),
+                                *resolve_symlinks_map,
+                                kGitObjectToResolvePrinter)) {
                             (*logger)(fmt::format("Failed to resolve symlinks "
                                                   "in tree {}:\n{}",
                                                   tree_hash,