Method TopologicalSort

Source/cmGlobalFastbuildGenerator.cxx:750–836

}

void cmGlobalFastbuildGenerator::TopologicalSort(
  std::vector<FastbuildTargetPtrT>& nodes)
{
  std::unordered_map<std::string, int> inDegree;
  std::unordered_map<std::string, std::set<std::string>> reverseDeps;
  std::unordered_map<std::string, std::size_t> originalIndex;

  // Track original positions
  for (std::size_t i = 0; i < nodes.size(); ++i) {
    auto const& node = nodes[i];
    inDegree[node->Name] = 0;
    originalIndex[node->Name] = i;
  }

  // Build reverse dependency graph and in-degree map
  for (auto const& node : nodes) {
    for (auto const& dep : node->PreBuildDependencies) {
      if (inDegree.count(dep.Name)) {
        reverseDeps[dep.Name].insert(node->Name);
        ++inDegree[node->Name];
      }
    }
  }

  // Min-heap based on original position
  auto const cmp = [&](std::string const& a, std::string const& b) {
    return originalIndex[a] > originalIndex[b];
  };
  std::priority_queue<std::string, std::vector<std::string>, decltype(cmp)>
    zeroInDegree(cmp);

  for (auto const& val : inDegree) {
    auto const& degree = val.second;
    auto const& name = val.first;
    if (degree == 0) {
      zeroInDegree.push(name);
    }
  }

  std::vector<std::string> sorted;
  while (!zeroInDegree.empty()) {
    std::string node = zeroInDegree.top();
    zeroInDegree.pop();
    sorted.push_back(node);
    for (auto const& dep : reverseDeps[node]) {
      if (--inDegree[dep] == 0) {
        zeroInDegree.push(dep);
      }
    }
  }

  if (sorted.size() != nodes.size()) {
    cmSystemTools::Error("Failed to sort (Cyclic dependency)");
    cmSystemTools::Error(cmStrCat("Sorted size: ", sorted.size()));
    cmSystemTools::Error(cmStrCat("nodes size: ", nodes.size()));
    for (auto const& node : nodes) {
      cmSystemTools::Error("Node: " + node->Name);
      for (auto const& dep : reverseDeps[node->Name]) {