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