cmCxxModuleMapper: track transitive modules for MSVC

MSVC needs the transitive closure of module usage to compile.

3 files changed, 278 insertions, 6 deletions

diff --git a/Source/cmCxxModuleMapper.cxx b/Source/cmCxxModuleMapper.cxx
index 94ad721..b68e28c 100644
--- a/Source/cmCxxModuleMapper.cxx
+++ b/Source/cmCxxModuleMapper.cxx
@@ -3,10 +3,17 @@
 #include "cmCxxModuleMapper.h"
 
 #include <cassert>
+#include <cstddef>
 #include <sstream>
+#include <utility>
 #include <vector>
 
+#include <cm/string_view>
+#include <cmext/string_view>
+
 #include "cmScanDepFormat.h"
+#include "cmStringAlgorithms.h"
+#include "cmSystemTools.h"
 
 cm::optional<std::string> CxxModuleLocations::BmiGeneratorPathForModule(
   std::string const& logical_name) const
@@ -49,6 +56,48 @@ std::string CxxModuleMapContentGcc(CxxModuleLocations const& loc,
 }
 }
 
+bool CxxModuleUsage::AddReference(std::string const& logical,
+                                  std::string const& loc, LookupMethod method)
+{
+  auto r = this->Reference.find(logical);
+  if (r != this->Reference.end()) {
+    auto& ref = r->second;
+
+    if (ref.Path == loc && ref.Method == method) {
+      return true;
+    }
+
+    auto method_name = [](LookupMethod m) -> cm::static_string_view {
+      switch (m) {
+        case LookupMethod::ByName:
+          return "by-name"_s;
+        case LookupMethod::IncludeAngle:
+          return "include-angle"_s;
+        case LookupMethod::IncludeQuote:
+          return "include-quote"_s;
+      }
+      assert(false && "unsupported lookup method");
+      return ""_s;
+    };
+
+    cmSystemTools::Error(cmStrCat("Disagreement of the location of the '",
+                                  logical,
+                                  "' module. "
+                                  "Location A: '",
+                                  ref.Path, "' via ", method_name(ref.Method),
+                                  "; "
+                                  "Location B: '",
+                                  loc, "' via ", method_name(method), "."));
+    return false;
+  }
+
+  auto& ref = this->Reference[logical];
+  ref.Path = loc;
+  ref.Method = method;
+
+  return true;
+}
+
 cm::static_string_view CxxModuleMapExtension(
   cm::optional<CxxModuleMapFormat> format)
 {
@@ -62,6 +111,108 @@ cm::static_string_view CxxModuleMapExtension(
   return ".bmi"_s;
 }
 
+std::set<std::string> CxxModuleUsageSeed(
+  CxxModuleLocations const& loc, std::vector<cmScanDepInfo> const& objects,
+  CxxModuleUsage& usages)
+{
+  // Track inner usages to populate usages from internal bits.
+  //
+  // This is a map of modules that required some other module that was not
+  // found to those that were not found.
+  std::map<std::string, std::set<std::string>> internal_usages;
+  std::set<std::string> unresolved;
+
+  for (cmScanDepInfo const& object : objects) {
+    // Add references for each of the provided modules.
+    for (auto const& p : object.Provides) {
+      if (auto bmi_loc = loc.BmiGeneratorPathForModule(p.LogicalName)) {
+        // XXX(cxx-modules): How to support header units?
+        usages.AddReference(p.LogicalName, loc.PathForGenerator(*bmi_loc),
+                            LookupMethod::ByName);
+      }
+    }
+
+    // For each requires, pull in what is required.
+    for (auto const& r : object.Requires) {
+      // Find transitive usages.
+      auto transitive_usages = usages.Usage.find(r.LogicalName);
+      // Find the required name in the current target.
+      auto bmi_loc = loc.BmiGeneratorPathForModule(r.LogicalName);
+
+      for (auto const& p : object.Provides) {
+        auto& this_usages = usages.Usage[p.LogicalName];
+
+        // Add the direct usage.
+        this_usages.insert(r.LogicalName);
+
+        // Add the transitive usage.
+        if (transitive_usages != usages.Usage.end()) {
+          this_usages.insert(transitive_usages->second.begin(),
+                             transitive_usages->second.end());
+        } else if (bmi_loc) {
+          // Mark that we need to update transitive usages later.
+          internal_usages[p.LogicalName].insert(r.LogicalName);
+        }
+      }
+
+      if (bmi_loc) {
+        usages.AddReference(r.LogicalName, loc.PathForGenerator(*bmi_loc),
+                            r.Method);
+      }
+    }
+  }
+
+  // While we have internal usages to manage.
+  while (!internal_usages.empty()) {
+    size_t starting_size = internal_usages.size();
+
+    // For each internal usage.
+    for (auto usage = internal_usages.begin(); usage != internal_usages.end();
+         /* see end of loop */) {
+      auto& this_usages = usages.Usage[usage->first];
+
+      for (auto use = usage->second.begin(); use != usage->second.end();
+           /* see end of loop */) {
+        // Check if this required module uses other internal modules; defer
+        // if so.
+        if (internal_usages.count(*use)) {
+          // Advance the iterator.
+          ++use;
+          continue;
+        }
+
+        auto transitive_usages = usages.Usage.find(*use);
+        if (transitive_usages != usages.Usage.end()) {
+          this_usages.insert(transitive_usages->second.begin(),
+                             transitive_usages->second.end());
+        }
+
+        // Remove the entry and advance the iterator.
+        use = usage->second.erase(use);
+      }
+
+      // Erase the entry if it doesn't have any remaining usages.
+      if (usage->second.empty()) {
+        usage = internal_usages.erase(usage);
+      } else {
+        ++usage;
+      }
+    }
+
+    // Check that at least one usage was resolved.
+    if (starting_size == internal_usages.size()) {
+      // Nothing could be resolved this loop; we have a cycle, so record the
+      // cycle and exit.
+      for (auto const& usage : internal_usages) {
+        unresolved.insert(usage.first);
+      }
+      break;
+    }
+  }
+
+  return unresolved;
+}
+
 std::string CxxModuleMapContent(CxxModuleMapFormat format,
                                 CxxModuleLocations const& loc,
                                 cmScanDepInfo const& obj)
diff --git a/Source/cmCxxModuleMapper.h b/Source/cmCxxModuleMapper.h
index 99384c9..6d29fc0 100644
--- a/Source/cmCxxModuleMapper.h
+++ b/Source/cmCxxModuleMapper.h
@@ -5,12 +5,15 @@
 #include "cmConfigure.h" // IWYU pragma: keep
 
 #include <functional>
+#include <map>
+#include <set>
 #include <string>
+#include <vector>
 
 #include <cm/optional>
 #include <cmext/string_view>
 
-struct cmScanDepInfo;
+#include "cmScanDepFormat.h"
 
 enum class CxxModuleMapFormat
 {
@@ -37,10 +40,42 @@ struct CxxModuleLocations
     std::string const& logical_name) const;
 };
 
+struct CxxModuleReference
+{
+  // The path to the module file used.
+  std::string Path;
+  // How the module was looked up.
+  LookupMethod Method;
+};
+
+struct CxxModuleUsage
+{
+  // The usage requirements for this object.
+  std::map<std::string, std::set<std::string>> Usage;
+
+  // The references for this object.
+  std::map<std::string, CxxModuleReference> Reference;
+
+  // Add a reference to a module.
+  //
+  // Returns `true` if it matches how it was found previously, `false` if it
+  // conflicts.
+  bool AddReference(std::string const& logical, std::string const& loc,
+                    LookupMethod method);
+};
+
 // Return the extension to use for a given modulemap format.
 cm::static_string_view CxxModuleMapExtension(
   cm::optional<CxxModuleMapFormat> format);
 
+// Fill in module usage information for internal usages.
+//
+// Returns the set of unresolved module usage requirements (these form an
+// import cycle).
+std::set<std::string> CxxModuleUsageSeed(
+  CxxModuleLocations const& loc, std::vector<cmScanDepInfo> const& objects,
+  CxxModuleUsage& usages);
+
 // Return the contents of the module map in the given format for the
 // object file.
 std::string CxxModuleMapContent(CxxModuleMapFormat format,
diff --git a/Source/cmGlobalNinjaGenerator.cxx b/Source/cmGlobalNinjaGenerator.cxx
index b4d5746..f69c95f 100644
--- a/Source/cmGlobalNinjaGenerator.cxx
+++ b/Source/cmGlobalNinjaGenerator.cxx
@@ -3,6 +3,7 @@
 #include "cmGlobalNinjaGenerator.h"
 
 #include <algorithm>
+#include <cassert>
 #include <cctype>
 #include <cstdio>
 #include <functional>
@@ -2555,6 +2556,8 @@ bool cmGlobalNinjaGenerator::WriteDyndepFile(
     objects.push_back(std::move(info));
   }
 
+  CxxModuleUsage usages;
+
   // Map from module name to module file path, if known.
   std::map<std::string, std::string> mod_files;
 
@@ -2572,8 +2575,47 @@ bool cmGlobalNinjaGenerator::WriteDyndepFile(
       return false;
     }
     if (ltm.isObject()) {
-      for (Json::Value::iterator i = ltm.begin(); i != ltm.end(); ++i) {
-        mod_files[i.key().asString()] = i->asString();
+      Json::Value const& target_modules = ltm["modules"];
+      if (target_modules.isObject()) {
+        for (auto i = target_modules.begin(); i != target_modules.end(); ++i) {
+          mod_files[i.key().asString()] = i->asString();
+        }
+      }
+      Json::Value const& target_modules_references = ltm["references"];
+      if (target_modules_references.isObject()) {
+        for (auto i = target_modules_references.begin();
+             i != target_modules_references.end(); ++i) {
+          if (i->isObject()) {
+            Json::Value const& reference_path = (*i)["path"];
+            CxxModuleReference module_reference;
+            if (reference_path.isString()) {
+              module_reference.Path = reference_path.asString();
+            }
+            Json::Value const& reference_method = (*i)["lookup-method"];
+            if (reference_method.isString()) {
+              std::string reference = reference_method.asString();
+              if (reference == "by-name") {
+                module_reference.Method = LookupMethod::ByName;
+              } else if (reference == "include-angle") {
+                module_reference.Method = LookupMethod::IncludeAngle;
+              } else if (reference == "include-quote") {
+                module_reference.Method = LookupMethod::IncludeQuote;
+              }
+            }
+            usages.Reference[i.key().asString()] = module_reference;
+          }
+        }
+      }
+      Json::Value const& target_modules_usage = ltm["usages"];
+      if (target_modules_usage.isObject()) {
+        for (auto i = target_modules_usage.begin();
+             i != target_modules_usage.end(); ++i) {
+          if (i->isArray()) {
+            for (auto j = i->begin(); j != i->end(); ++j) {
+              usages.Usage[i.key().asString()].insert(j->asString());
+            }
+          }
+        }
       }
     }
   }
@@ -2595,7 +2637,7 @@ bool cmGlobalNinjaGenerator::WriteDyndepFile(
   // Extend the module map with those provided by this target.
   // We do this after loading the modules provided by linked targets
   // in case we have one of the same name that must be preferred.
-  Json::Value tm = Json::objectValue;
+  Json::Value target_modules = Json::objectValue;
   for (cmScanDepInfo const& object : objects) {
     for (auto const& p : object.Provides) {
       std::string mod;
@@ -2614,7 +2656,7 @@ bool cmGlobalNinjaGenerator::WriteDyndepFile(
         mod = cmStrCat(module_dir, safe_logical_name, module_ext);
       }
       mod_files[p.LogicalName] = mod;
-      tm[p.LogicalName] = mod;
+      target_modules[p.LogicalName] = mod;
     }
   }
 
@@ -2636,6 +2678,18 @@ bool cmGlobalNinjaGenerator::WriteDyndepFile(
       return {};
     };
 
+    // Insert information about the current target's modules.
+    if (modmap_fmt) {
+      auto cycle_modules = CxxModuleUsageSeed(locs, objects, usages);
+      if (!cycle_modules.empty()) {
+        cmSystemTools::Error(
+          cmStrCat("Circular dependency detected in the C++ module import "
+                   "graph. See modules named: \"",
+                   cmJoin(cycle_modules, R"(", ")"_s), '"'));
+        return false;
+      }
+    }
+
     cmNinjaBuild build("dyndep");
     build.Outputs.emplace_back("");
     for (cmScanDepInfo const& object : objects) {
@@ -2671,12 +2725,44 @@ bool cmGlobalNinjaGenerator::WriteDyndepFile(
     }
   }
 
+  Json::Value target_module_info = Json::objectValue;
+  target_module_info["modules"] = target_modules;
+
+  auto& target_usages = target_module_info["usages"] = Json::objectValue;
+  for (auto const& u : usages.Usage) {
+    auto& mod_usage = target_usages[u.first] = Json::arrayValue;
+    for (auto const& v : u.second) {
+      mod_usage.append(v);
+    }
+  }
+
+  auto name_for_method = [](LookupMethod method) -> cm::static_string_view {
+    switch (method) {
+      case LookupMethod::ByName:
+        return "by-name"_s;
+      case LookupMethod::IncludeAngle:
+        return "include-angle"_s;
+      case LookupMethod::IncludeQuote:
+        return "include-quote"_s;
+    }
+    assert(false && "unsupported lookup method");
+    return ""_s;
+  };
+
+  auto& target_references = target_module_info["references"] =
+    Json::objectValue;
+  for (auto const& r : usages.Reference) {
+    auto& mod_ref = target_references[r.first] = Json::objectValue;
+    mod_ref["path"] = r.second.Path;
+    mod_ref["lookup-method"] = std::string(name_for_method(r.second.Method));
+  }
+
   // Store the map of modules provided by this target in a file for
   // use by dependents that reference this target in linked-target-dirs.
   std::string const target_mods_file = cmStrCat(
     cmSystemTools::GetFilenamePath(arg_dd), '/', arg_lang, "Modules.json");
   cmGeneratedFileStream tmf(target_mods_file);
-  tmf << tm;
+  tmf << target_module_info;
 
   bool result = true;