// mcpp.modgraph.graph — DAG of module units (per-package, cross-package later).

export module mcpp.modgraph.graph;

import std;
import mcpp.source_kind;

export namespace mcpp::modgraph {

struct ModuleId {
    std::string                     logicalName;       // "mcpplibs.hello.core"

    auto operator<=>(const ModuleId&) const = default;
};

struct SourceUnit {
    std::filesystem::path           path;
    // mcpp#233: path relative to this unit's PACKAGE ROOT (not the primary
    // project root — a path dependency has its own root), set by the
    // scanner where the root is known. Used by plan.cppm to mirror the
    // source's directory layout into its object path so that two
    // same-named files under different subdirectories (e.g. a/src/util.cpp
    // and b/src/util.cpp) never fold onto the same object output. Left
    // default-constructed (empty) for units synthesized outside the
    // scanner (e.g. plan.cppm's ad-hoc main.cpp CompileUnit, which never
    // reads this field).
    std::filesystem::path           relPath;
    std::string                     packageName;
    std::vector<std::filesystem::path> localIncludeDirs;
    // #249: dirs emitted as -idirafter — searched after the toolchain's
    // system dirs, so a dep's source root can't shadow standard headers.
    std::vector<std::filesystem::path> localIncludeDirsAfter;
    std::vector<std::string>        packageCflags;
    std::vector<std::string>        packageCxxflags;
    std::vector<std::string>        packageAsmflags;   // per-glob asmflags (G4)
    std::optional<ModuleId>         provides;
    // Was `provides` declared with `export module`?
    //
    // Both spellings produce a BMI and an object, so `provides` alone cannot
    // tell an INTERFACE partition (`export module M:api;`) from an
    // IMPLEMENTATION partition (`module M:impl;`) — and the difference decides
    // whether a source may be published. `mcpp pack` publishes the module
    // closure of the lib root; a closure that reaches an implementation
    // partition has to publish it too (the consumer cannot build the BMI
    // without it), and the author needs to be told that their implementation
    // is going out.
    //
    // Three states, because "nobody determined this" is a real answer and it
    // used to be spelled `true`:
    //
    //   true     `export module M:api;` — the text scanner read the keyword
    //   false    `module M:impl;`       — likewise
    //   nullopt  nobody could tell: a `scan_overrides` entry names the module
    //            but has no way to say whether it is exported, and a P1689
    //            scanner may omit `is-interface`
    //
    // It defaulted to `true` and was called the conservative direction "since
    // the flag only ever produces a warning". That had it backwards: `true` is
    // the value that produces NO warning, so an undetermined implementation
    // partition was published in silence — the exact failure this field exists
    // to prevent. Unknown now warns, naming the file and the reason.
    std::optional<bool>             providesInterface;
    std::vector<ModuleId>           requires_;
    // The unit's ROLE, decided once by the scanner from the owning package's
    // extension table and carried from here on. Every downstream consumer
    // (planner, backend, compile_commands, the asm dialect check) reads this
    // instead of re-deriving it from the extension — see mcpp.source_kind for
    // why that mattered.
    mcpp::SourceKind                kind = mcpp::SourceKind::Other;
    //
    // `isModuleInterface` / `isImplementation` used to live here. They were
    // WRITE-ONLY: three sites derived them (the scanner said `.cpp`, the p1689
    // reader said `.cpp || .cxx`, the scan_overrides branch said "has
    // provides"), the three disagreed, and nothing in src/ or tests/ ever read
    // the result. Converging three derivations of a value nobody reads is
    // still three derivations, so they are gone instead. `provides` answers
    // "is this an interface"; `kind` answers the rest.
    // Unit built from a manifest scan_overrides declaration instead of a
    // real scan — plan-vs-ddi verification is mandatory for these.
    bool                            scanOverridden     = false;
};

struct Graph {
    std::vector<SourceUnit>                                  units;
    // logical-name -> index into units
    std::map<std::string, std::size_t, std::less<>>             producerOf;
    // edges as (consumer-index, producer-index)
    std::vector<std::pair<std::size_t, std::size_t>>         edges;
};

// Topological order: returns indices of units in producer-before-consumer order.
// Returns std::unexpected with the cycle if any.
struct CycleError {
    std::vector<std::size_t> cycle;
};
std::expected<std::vector<std::size_t>, CycleError> topo_sort(const Graph& g);

} // namespace mcpp::modgraph

namespace mcpp::modgraph {

std::expected<std::vector<std::size_t>, CycleError> topo_sort(const Graph& g) {
    std::vector<std::size_t> indeg(g.units.size(), 0);
    std::vector<std::vector<std::size_t>> adj(g.units.size());
    for (auto [c, p] : g.edges) {
        // edge means: consumer depends on producer. So producer must come first.
        // indegree of consumer counts unmet producer dependencies.
        indeg[c]++;
        adj[p].push_back(c);
    }

    std::vector<std::size_t> order;
    order.reserve(g.units.size());
    std::vector<std::size_t> queue;
    for (std::size_t i = 0; i < indeg.size(); ++i) {
        if (indeg[i] == 0) queue.push_back(i);
    }
    while (!queue.empty()) {
        std::size_t u = queue.back();
        queue.pop_back();
        order.push_back(u);
        for (auto v : adj[u]) {
            if (--indeg[v] == 0) queue.push_back(v);
        }
    }
    if (order.size() != g.units.size()) {
        // Cycle remains. Report units still with positive indegree.
        CycleError err;
        for (std::size_t i = 0; i < indeg.size(); ++i) {
            if (indeg[i] > 0) err.cycle.push_back(i);
        }
        return std::unexpected(err);
    }
    return order;
}

} // namespace mcpp::modgraph