mcpp/src/modgraph/graph.cppm at main · mcpp-community/mcpp · GitHub

History

137 lines (124 loc) · 6.05 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

// 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

mcpp/src/modgraph/graph.cppm at main · mcpp-community/mcpp · GitHub

Uh oh!

Expand file tree

Breadcrumbs

graph.cppm

Latest commit

History

Breadcrumbs

graph.cppm

File metadata and controls