// Ported from ninja v1.13.2 src/missing_deps.cc, src/graphviz.cc and
// src/json.cc (Apache-2.0, see NOTICE).
///|
/// Finds discovered dependencies (from the deps log or depfiles) on
/// generated files with no build-graph path to their generator: such
/// targets may build before the file exists (`-t missingdeps`, ninja's
/// `MissingDependencyScanner`).
pub struct MissingDependencyScanner {
on_missing_dep : (Node, String, Rule) -> Unit
deps_log : DepsLog
state : State
disk : &Disk
seen : Map[Int32, Unit]
/// Targets with missing deps, by node index.
nodes_missing_deps : Map[Int32, Node]
/// Generated files used without a dependency path, by node index.
generated_nodes : Map[Int32, Node]
/// Rules generating them.
generator_rules : Array[Rule]
mut missing_dep_path_count : Int32
/// PathExistsBetween results, by (from edge id, to edge id).
adjacency : Map[(Int32, Int32), Bool]
}
///|
/// The report `ninja -t missingdeps` prints for each missing dependency.
pub fn missing_dep_message(
node : Node,
path : String,
generator : Rule,
) -> String {
"Missing dep: \{node.path} uses \{path} (generated by \{generator.name})\n"
}
///|
pub fn MissingDependencyScanner::new(
deps_log : DepsLog,
state : State,
disk : &Disk,
on_missing_dep~ : (Node, String, Rule) -> Unit = fn(_, _, _) { },
) -> MissingDependencyScanner {
{
on_missing_dep,
deps_log,
state,
disk,
seen: Map([]),
nodes_missing_deps: Map([]),
generated_nodes: Map([]),
generator_rules: [],
missing_dep_path_count: 0,
adjacency: Map([]),
}
}
///|
pub fn MissingDependencyScanner::had_missing_deps(
self : MissingDependencyScanner,
) -> Bool {
!self.nodes_missing_deps.is_empty()
}
///|
pub fn MissingDependencyScanner::missing_dep_path_count(
self : MissingDependencyScanner,
) -> Int32 {
self.missing_dep_path_count
}
///|
pub fn MissingDependencyScanner::nodes_missing_deps(
self : MissingDependencyScanner,
) -> Array[Node] {
self.nodes_missing_deps.values().collect()
}
///|
pub fn MissingDependencyScanner::generated_nodes(
self : MissingDependencyScanner,
) -> Array[Node] {
self.generated_nodes.values().collect()
}
///|
pub fn MissingDependencyScanner::generator_rules(
self : MissingDependencyScanner,
) -> Array[Rule] {
self.generator_rules
}
///|
pub fn MissingDependencyScanner::process_node(
self : MissingDependencyScanner,
node : Node,
) -> Unit {
guard node.in_edge is Some(edge) else { return }
if self.seen.contains(node.index) {
return
}
self.seen[node.index] = ()
for input in edge.inputs {
self.process_node(input)
}
let deps_type = edge.get_binding("deps") catch { _ => "" }
if deps_type != "" {
if self.deps_log.get_deps(node) is Some(deps) {
self.process_node_deps(node, deps.nodes)
}
} else {
let store = []
let loader = ImplicitDepLoader::new(
self.state,
self.disk,
deps_log=self.deps_log,
store~,
)
ignore(loader.load_deps(edge) catch { _ => false })
if !store.is_empty() {
self.process_node_deps(node, store)
}
}
}
///|
fn MissingDependencyScanner::process_node_deps(
self : MissingDependencyScanner,
node : Node,
dep_nodes : Array[Node],
) -> Unit {
guard node.in_edge is Some(edge) else { return }
// Edges that generate the deps, in creation order (ninja's set of
// pointers).
let deplog_edges : Map[Int32, Edge] = Map([])
for dep in dep_nodes {
// A dep on build.ninja means "rebuild when reconfigured"; the whole
// build depends on that implicitly.
if dep.path == "build.ninja" {
return
}
if dep.in_edge is Some(e) {
deplog_edges[e.id] = e
}
}
let ids = deplog_edges.keys().collect()
ids.sort()
let missing = []
for id in ids {
let from = deplog_edges[id]
if !self.path_exists_between(from, edge) {
missing.push(from)
}
}
if missing.is_empty() {
return
}
let rule_names : Map[String, Unit] = Map([])
for generator in missing {
for dep in dep_nodes {
if dep.in_edge is Some(e) && physical_equal(e, generator) {
self.generated_nodes[dep.index] = dep
if !self.generator_rules
.iter()
.any(fn(r) { physical_equal(r, generator.rule) }) {
self.generator_rules.push(generator.rule)
}
rule_names[generator.rule.name] = ()
(self.on_missing_dep)(node, dep.path, generator.rule)
}
}
}
self.missing_dep_path_count += rule_names.length()
self.nodes_missing_deps[node.index] = node
}
///|
/// The summary `ninja -t missingdeps` ends with.
pub fn MissingDependencyScanner::stats(
self : MissingDependencyScanner,
) -> String {
let out = StringBuilder()
out.write_string("Processed \{self.seen.length()} nodes.\n")
if self.had_missing_deps() {
out.write_string(
"Error: There are \{self.missing_dep_path_count} missing dependency paths.\n",
)
out.write_string(
"\{self.nodes_missing_deps.length()} targets had depfile dependencies on \{self.generated_nodes.length()} distinct generated inputs (from \{self.generator_rules.length()} rules) without a non-depfile dep path to the generator.\n",
)
out.write_string(
"There might be build flakiness if any of the targets listed above are built alone, or not late enough, in a clean output directory.\n",
)
} else {
out.write_string("No missing dependencies on generated files found.\n")
}
out.to_string()
}
///|
fn MissingDependencyScanner::path_exists_between(
self : MissingDependencyScanner,
from : Edge,
to : Edge,
) -> Bool {
if self.adjacency.get((from.id, to.id)) is Some(found) {
return found
}
let mut found = false
for input in to.inputs {
if input.in_edge is Some(e) &&
(physical_equal(e, from) || self.path_exists_between(from, e)) {
found = true
break
}
}
self.adjacency[(from.id, to.id)] = found
found
}
///|
/// `text` as the inside of a JSON string (ninja's `EncodeJSONString`).
/// Characters outside ASCII control codes pass through.
pub fn encode_json_string(text : String) -> String {
let digits = "0123456789abcdef"
let out = StringBuilder(capacity=text.length())
for c in text {
match c {
'\b' => out.write_string("\\b")
'\u{c}' => out.write_string("\\f")
'\n' => out.write_string("\\n")
'\r' => out.write_string("\\r")
'\t' => out.write_string("\\t")
'\\' => out.write_string("\\\\")
'"' => out.write_string("\\\"")
_ =>
if c.to_int() < 0x20 {
out.write_string("\\u00")
out.write_char(
digits.unsafe_get(c.to_int() >> 4).to_int().unsafe_to_char(),
)
out.write_char(
digits.unsafe_get(c.to_int() & 0xf).to_int().unsafe_to_char(),
)
} else {
out.write_char(c)
}
}
}
out.to_string()
}
///|
/// Writes a Graphviz dot graph of the targets (`-t graph`, ninja's
/// `GraphViz`). ninja names graph vertices by their addresses; these
/// stand-ins are stable but just as arbitrary.
pub struct GraphViz {
state : State
reader : &FileReader?
out : (String) -> Unit
warn : (String) -> Unit
windows : Bool
visited_nodes : Map[Int32, Unit]
visited_edges : Map[Int32, Unit]
}
///|
pub fn GraphViz::new(
state : State,
out : (String) -> Unit,
reader? : &FileReader,
warn~ : (String) -> Unit = fn(_) { },
) -> GraphViz {
{
state,
reader,
out,
warn,
windows: state.platform is Windows,
visited_nodes: Map([]),
visited_edges: Map([]),
}
}
///|
/// An address-like name, formatted like `%p`: 0x-prefixed lowercase hex
/// on POSIX, 16 uppercase hex digits on Windows.
fn GraphViz::address(self : GraphViz, value : Int32) -> String {
let digits = "0123456789abcdef"
let mut n = value.to_int64()
let hex = StringBuilder()
let chars = []
while n > 0 {
chars.push(digits.unsafe_get((n % 16).to_int()).to_int().unsafe_to_char())
n = n / 16
}
for i = chars.length() - 1; i >= 0; i = i - 1 {
hex.write_char(chars[i])
}
let text = hex.to_string()
if self.windows {
"0".repeat(16 - text.length()) + text.to_upper()
} else {
"0x" + text
}
}
///|
fn GraphViz::node_name(self : GraphViz, node : Node) -> String {
self.address(0x55550000 + node.index * 0x40)
}
///|
fn GraphViz::edge_name(self : GraphViz, edge : Edge) -> String {
self.address(0x66660000 + edge.id * 0x40)
}
///|
pub fn GraphViz::start(self : GraphViz) -> Unit {
(self.out)(
"digraph ninja {\nrankdir=\"LR\"\nnode [fontsize=10, shape=box, height=0.25]\nedge [fontsize=10]\n",
)
}
///|
pub fn GraphViz::finish(self : GraphViz) -> Unit {
(self.out)("}\n")
}
///|
pub fn GraphViz::add_target(self : GraphViz, node : Node) -> Unit {
if self.visited_nodes.contains(node.index) {
return
}
let label = node.path.replace_all(old="\\", new="/")
(self.out)("\"\{self.node_name(node)}\" [label=\"\{label}\"]\n")
self.visited_nodes[node.index] = ()
// A leaf node.
guard node.in_edge is Some(edge) else { return }
if self.visited_edges.contains(edge.id) {
return
}
self.visited_edges[edge.id] = ()
if edge.dyndep is Some(dyndep) &&
dyndep.dyndep_pending &&
self.reader is Some(reader) {
load_dyndeps(self.state, reader, dyndep) catch {
error => (self.warn)("\{error.message()}\n")
}
}
let rule = edge.rule.name
if edge.inputs.length() == 1 && edge.outputs.length() == 1 {
// The space before the label works around a Graphviz quirk.
(self.out)(
"\"\{self.node_name(edge.inputs[0])}\" -> \"\{self.node_name(edge.outputs[0])}\" [label=\" \{rule}\"]\n",
)
} else {
let name = self.edge_name(edge)
(self.out)("\"\{name}\" [label=\"\{rule}\", shape=ellipse]\n")
for out in edge.outputs {
(self.out)("\"\{name}\" -> \"\{self.node_name(out)}\"\n")
}
for i, input in edge.inputs {
let order_only = if edge.is_order_only(i) { " style=dotted" } else { "" }
(self.out)(
"\"\{self.node_name(input)}\" -> \"\{name}\" [arrowhead=none\{order_only}]\n",
)
}
}
for input in edge.inputs {
self.add_target(input)
}
}