///|
/// Why nodes are dirty, for `-d explain` (ninja's `Explanations`).
pub struct Explanations {
  map : Map[String, Array[String]]
}

///|
pub fn Explanations::new() -> Explanations {
  { map: Map([]), }
}

///|
pub fn Explanations::record(
  self : Explanations,
  node : Node,
  message : String,
) -> Unit {
  match self.map.get(node.path) {
    Some(list) => list.push(message)
    None => self.map[node.path] = [message]
  }
}

///|
pub fn Explanations::lookup(self : Explanations, node : Node) -> Array[String] {
  self.map.get(node.path).unwrap_or([])
}

///|
fn record(explanations : Explanations?, node : Node, message : String) -> Unit {
  if explanations is Some(e) {
    e.record(node, message)
  }
}

///|
/// Reads a file through `disk` for parsers: missing files are errors.
fn disk_reader(disk : &Disk) -> (String) -> String raise NinjaError {
  fn(path : String) raise NinjaError {
    match disk.read_file(path) {
      Some(contents) => contents
      None => raise Error("No such file or directory")
    }
  }
}

///|
/// Adds the dependencies an edge discovered when it last ran: from the
/// deps log for `deps = gcc|msvc`, or from its `depfile`.
pub struct ImplicitDepLoader {
  state : State
  deps_log : DepsLog?
  disk : &Disk
  explanations : Explanations?
  /// When set, depfile deps are collected here and the graph is left alone
  /// (ninja's `NodeStoringImplicitDepLoader`, for `-t missingdeps`).
  store : Array[Node]?
}

///|
pub fn ImplicitDepLoader::new(
  state : State,
  disk : &Disk,
  deps_log? : DepsLog,
  explanations? : Explanations,
  store? : Array[Node],
) -> ImplicitDepLoader {
  { state, deps_log, disk, explanations, store, }
}

///|
/// Loads the edge's discovered deps. False when they are missing or stale,
/// so the edge must run to regenerate them.
pub fn ImplicitDepLoader::load_deps(
  self : ImplicitDepLoader,
  edge : Edge,
) -> Bool raise NinjaError {
  if edge.get_binding("deps") != "" {
    return self.load_deps_from_log(edge)
  }
  let depfile = edge.get_unescaped_depfile()
  if depfile != "" {
    return self.load_depfile(edge, depfile)
  }
  true
}

///|
fn ImplicitDepLoader::load_depfile(
  self : ImplicitDepLoader,
  edge : Edge,
  path : String,
) -> Bool raise NinjaError {
  // A missing depfile reads as empty.
  let content = self.disk.read_file(path) catch {
    error => raise Error("loading '\{path}': \{error.message()}")
  }
  let content = content.unwrap_or("")
  let first_output = edge.outputs[0]
  if content == "" {
    record(self.explanations, first_output, "depfile '\{path}' is missing")
    return false
  }
  let depfile = parse_depfile(content) catch {
    error => raise Error("\{path}: \{error.message()}")
  }
  if depfile.outs.is_empty() {
    raise Error("\{path}: no outputs declared")
  }
  let (primary, _) = canonicalize_path(
    depfile.outs[0],
    platform=self.state.platform,
  )
  // A depfile for another output makes the edge dirty.
  if first_output.path != primary {
    record(
      self.explanations,
      first_output,
      "expected depfile '\{path}' to mention '\{first_output.path}', got '\{primary}'",
    )
    return false
  }
  // Every output it mentions must be an output of the edge. ninja compares
  // the first one canonicalized and the others as written.
  for i, out in depfile.outs {
    let out = if i == 0 { primary } else { out }
    if !edge.outputs.iter().any(fn(node) { node.path == out }) {
      raise Error(
        "\{path}: depfile mentions '\{out}' as an output, but no such output was declared",
      )
    }
  }
  self.process_depfile_deps(edge, depfile.ins)
  true
}

///|
fn ImplicitDepLoader::process_depfile_deps(
  self : ImplicitDepLoader,
  edge : Edge,
  ins : Array[String],
) -> Unit {
  if self.store is Some(store) {
    for input in ins {
      let (path, slash_bits) = canonicalize_path(
        input,
        platform=self.state.platform,
      )
      store.push(self.state.get_node(path, slash_bits))
    }
    return
  }
  // The new deps go before the order-only ones.
  let at = edge.inputs.length() - edge.order_only_deps
  for i, input in ins {
    let (path, slash_bits) = canonicalize_path(
      input,
      platform=self.state.platform,
    )
    let node = self.state.get_node(path, slash_bits)
    edge.inputs.insert(at + i, node)
    node.out_edges.push(edge)
  }
  edge.implicit_deps += ins.length()
}

///|
fn ImplicitDepLoader::load_deps_from_log(
  self : ImplicitDepLoader,
  edge : Edge,
) -> Bool {
  // Deps are only supported for single-output edges.
  let output = edge.outputs[0]
  let deps = match self.deps_log {
    Some(log) => log.get_deps(output)
    None => None
  }
  guard deps is Some(deps) else {
    record(self.explanations, output, "deps for '\{output.path}' are missing")
    return false
  }
  // Deps older than the output are stale.
  if output.mtime > deps.mtime {
    record(
      self.explanations,
      output,
      "stored deps info out of date for '\{output.path}' (\{deps.mtime} vs \{output.mtime})",
    )
    return false
  }
  let at = edge.inputs.length() - edge.order_only_deps
  for i, node in deps.nodes {
    edge.inputs.insert(at + i, node)
  }
  edge.implicit_deps += deps.nodes.length()
  for node in deps.nodes {
    node.out_edges.push(edge)
  }
  true
}

///|
/// Decides which nodes are dirty: port of ninja's `DependencyScan`.
pub struct DependencyScan {
  state : State
  mut build_log : BuildLog?
  disk : &Disk
  dep_loader : ImplicitDepLoader
  explanations : Explanations?
}

///|
pub fn DependencyScan::new(
  state : State,
  disk : &Disk,
  build_log? : BuildLog,
  deps_log? : DepsLog,
  explanations? : Explanations,
) -> DependencyScan {
  {
    state,
    build_log,
    disk,
    dep_loader: { state, deps_log, disk, explanations, store: None, },
    explanations,
  }
}

///|
pub fn DependencyScan::build_log(self : DependencyScan) -> BuildLog? {
  self.build_log
}

///|
pub fn DependencyScan::set_build_log(
  self : DependencyScan,
  log : BuildLog?,
) -> Unit {
  self.build_log = log
}

///|
pub fn DependencyScan::deps_log(self : DependencyScan) -> DepsLog? {
  self.dep_loader.deps_log
}

///|
/// Loads the dyndep file `node` into the graph.
pub fn DependencyScan::load_dyndeps(
  self : DependencyScan,
  node : Node,
  file~ : DyndepFile = DyndepFile::new(),
) -> Unit raise NinjaError {
  node.dyndep_pending = false
  record(self.explanations, node, "loading dyndep file '\{node.path}'")
  let parser : DyndepParser = {
    state: self.state,
    read: Some(disk_reader(self.disk)),
    file,
    lexer: Lexer::new(""),
    env: BindingEnv::new(),
  }
  parser.load(node.path)
  apply_dyndeps(node, file)
}

///|
/// Updates the edges that bind `node` as their dyndep file from `file`.
fn apply_dyndeps(node : Node, file : DyndepFile) -> Unit raise NinjaError {
  for edge in node.out_edges {
    match edge.dyndep {
      Some(dyndep) if physical_equal(dyndep, node) => ()
      _ => continue
    }
    guard file.entries.get(edge.id) is Some(dyndeps) else {
      raise Error(
        "'\{edge.outputs[0].path}' not mentioned in its dyndep file '\{node.path}'",
      )
    }
    dyndeps.used = true
    update_edge(edge, dyndeps)
  }
  let unused = file.entries.values().filter(fn(d) { !d.used }).collect()
  unused.sort_by(fn(a, b) { a.edge.id.compare(b.edge.id) })
  if unused is [first, ..] {
    raise Error(
      "dyndep file '\{node.path}' mentions output '\{first.edge.outputs[0].path}' whose build statement does not have a dyndep binding for the file",
    )
  }
}

///|
/// Updates the dirty state of `node` and everything it depends on. The
/// validation nodes found along the way are scanned too and appended to
/// `validation_nodes`.
pub fn DependencyScan::recompute_dirty(
  self : DependencyScan,
  initial : Node,
  validation_nodes~ : Array[Node] = [],
) -> Unit raise NinjaError {
  let stack : Array[Node] = []
  let nodes : @deque.Deque[Node] = @deque.Deque([])
  nodes.push_back(initial)
  while nodes.pop_front() is Some(node) {
    stack.clear()
    let found : Array[Node] = []
    self.recompute_node_dirty(node, stack, found)
    for v in found {
      nodes.push_back(v)
      validation_nodes.push(v)
    }
  }
}

///|
fn DependencyScan::recompute_node_dirty(
  self : DependencyScan,
  node : Node,
  stack : Array[Node],
  validation_nodes : Array[Node],
) -> Unit raise NinjaError {
  guard node.in_edge is Some(edge) else {
    // A leaf: done if seen before, otherwise dirty when missing.
    if node.status_known() {
      return
    }
    node.stat_if_necessary(self.disk)
    if !node.exists() {
      record(
        self.explanations,
        node,
        "\{node.path} has no in-edge and is missing",
      )
    }
    node.dirty = !node.exists()
    return
  }
  if edge.mark is VisitDone {
    return
  }
  self.verify_dag(node, stack)
  edge.mark = VisitInStack
  stack.push(node)
  let mut dirty = false
  edge.outputs_ready = true
  edge.deps_missing = false
  if !edge.deps_loaded {
    // First visit: load a pending dyndep file now if it is ready. If it
    // is not, the edge is not ready either; the build loads it later.
    match edge.dyndep {
      Some(dyndep) if dyndep.dyndep_pending => {
        self.recompute_node_dirty(dyndep, stack, validation_nodes)
        let ready = match dyndep.in_edge {
          None => true
          Some(producer) => producer.outputs_ready
        }
        if ready {
          self.load_dyndeps(dyndep)
        }
      }
      _ => ()
    }
  }
  // Output mtimes, to compare with the newest input below.
  for out in edge.outputs {
    out.stat_if_necessary(self.disk)
  }
  if !edge.deps_loaded {
    // First visit: load the discovered deps.
    edge.deps_loaded = true
    if !self.dep_loader.load_deps(edge) {
      // Missing deps info: rebuild to regenerate it.
      dirty = true
      edge.deps_missing = true
    }
  }
  // Validations are scanned separately, so that one depending on this node
  // does not look like a cycle.
  for v in edge.validations {
    validation_nodes.push(v)
  }
  let mut most_recent_input : Node? = None
  for i, input in edge.inputs {
    self.recompute_node_dirty(input, stack, validation_nodes)
    // An input that is not ready makes the outputs not ready.
    if input.in_edge is Some(producer) && !producer.outputs_ready {
      edge.outputs_ready = false
    }
    if !edge.is_order_only(i) {
      if input.dirty {
        record(self.explanations, node, "\{input.path} is dirty")
        dirty = true
      } else {
        match most_recent_input {
          Some(newest) if input.mtime <= newest.mtime => ()
          _ => most_recent_input = Some(input)
        }
      }
    }
  }
  if !dirty {
    dirty = self.recompute_outputs_dirty(edge, most_recent_input)
  }
  if dirty {
    for out in edge.outputs {
      out.dirty = true
    }
  }
  // A dirty edge's outputs are not ready, except for a phony edge without
  // inputs, which has nothing to do.
  if dirty && !(edge.is_phony() && edge.inputs.is_empty()) {
    edge.outputs_ready = false
  }
  edge.mark = VisitDone
  ignore(stack.pop())
}

///|
fn DependencyScan::verify_dag(
  self : DependencyScan,
  node : Node,
  stack : Array[Node],
) -> Unit raise NinjaError {
  ignore(self)
  guard node.in_edge is Some(edge) else { return }
  if !(edge.mark is VisitInStack) {
    return
  }
  // Find the edge on the stack, and report the cycle as starting and
  // ending at this node: `ninja b` on "build a b: cat c / build c: cat a"
  // says a -> c -> a, not b -> c -> a.
  let mut start = 0
  while start < stack.length() {
    match stack[start].in_edge {
      Some(e) if physical_equal(e, edge) => break
      _ => start += 1
    }
  }
  stack[start] = node
  let message = StringBuilder()
  message.write_string("dependency cycle: ")
  for i in start.. ")
  }
  message.write_string(stack[start].path)
  if start + 1 == stack.length() && edge.maybe_phonycycle_diagnostic() {
    // The parser keeps the self-reference only with phonycycle=err.
    message.write_string(" [-w phonycycle=err]")
  }
  raise Error(message.to_string())
}

///|
/// Whether any output of `edge` is out of date.
pub fn DependencyScan::recompute_outputs_dirty(
  self : DependencyScan,
  edge : Edge,
  most_recent_input : Node?,
) -> Bool raise NinjaError {
  let command = edge.evaluate_command(incl_rsp_file=true)
  for out in edge.outputs {
    if self.recompute_output_dirty(edge, most_recent_input, command, out) {
      return true
    }
  }
  false
}

///|
fn DependencyScan::recompute_output_dirty(
  self : DependencyScan,
  edge : Edge,
  most_recent_input : Node?,
  command : String,
  output : Node,
) -> Bool raise NinjaError {
  if edge.is_phony() {
    // Phony edges write nothing: their outputs are dirty only when there
    // are no inputs and the output is missing.
    if edge.inputs.is_empty() && !output.exists() {
      record(
        self.explanations,
        output,
        "output \{output.path} of phony edge with no inputs doesn't exist",
      )
      return true
    }
    // Dependents see the newest input's mtime on the phony output.
    if most_recent_input is Some(newest) {
      output.update_phony_mtime(newest.mtime)
    }
    return false
  }
  if !output.exists() {
    record(self.explanations, output, "output \{output.path} doesn't exist")
    return true
  }
  // A restat rule may have left its output untouched in an earlier run
  // and recorded the command's start time instead: compare the recorded
  // mtime, not the file's.
  let mut entry : LogEntry? = None
  let mut used_restat = false
  if edge.get_binding_bool("restat") && self.build_log is Some(log) {
    entry = log.lookup_by_output(output.path)
    used_restat = entry is Some(_)
  }
  if !used_restat && most_recent_input is Some(newest) {
    if output.mtime < newest.mtime {
      record(
        self.explanations,
        output,
        "output \{output.path} older than most recent input \{newest.path} (\{output.mtime} vs \{newest.mtime})",
      )
      return true
    }
  }
  if self.build_log is Some(log) {
    let generator = edge.get_binding_bool("generator")
    if entry is None {
      entry = log.lookup_by_output(output.path)
    }
    match entry {
      Some(e) => {
        // A changed command makes the output dirty, unless the rule is a
        // generator.
        if !generator && hash_command(command) != e.command_hash {
          record(
            self.explanations,
            output,
            "command line changed for \{output.path}",
          )
          return true
        }
        // A run that wrote the output but failed or was interrupted leaves
        // a recorded mtime older than the newest input.
        if most_recent_input is Some(newest) && e.mtime < newest.mtime {
          record(
            self.explanations,
            output,
            "recorded mtime of \{output.path} older than most recent input \{newest.path} (\{e.mtime} vs \{newest.mtime})",
          )
          return true
        }
      }
      None =>
        if !generator {
          record(
            self.explanations,
            output,
            "command line not found in log for \{output.path}",
          )
          return true
        }
    }
  }
  false
}

///|
/// Collects the inputs that lead to nodes, skipping outputs of phony
/// edges (`ninja -t inputs`).
pub struct InputsCollector {
  inputs : Array[Node]
  visited : Map[String, Unit]
  platform : Platform
}

///|
pub fn InputsCollector::new(platform~ : Platform = Posix) -> InputsCollector {
  { inputs: [], visited: Map([]), platform, }
}

///|
pub fn InputsCollector::visit_node(self : InputsCollector, node : Node) -> Unit {
  guard node.in_edge is Some(edge) else { return }
  for input in edge.inputs {
    if self.visited.contains(input.path) {
      continue
    }
    self.visited[input.path] = ()
    self.visit_node(input)
    match input.in_edge {
      Some(producer) if producer.is_phony() => ()
      _ => self.inputs.push(input)
    }
  }
}

///|
pub fn InputsCollector::inputs(self : InputsCollector) -> Array[Node] {
  self.inputs
}

///|
pub fn InputsCollector::inputs_as_strings(
  self : InputsCollector,
  escape~ : Bool = false,
) -> Array[String] {
  self.inputs.map(fn(input) {
    let path = input.path_decanonicalized(self.platform)
    if !escape {
      path
    } else {
      let out = StringBuilder()
      if self.platform is Windows {
        win32_escape(path, out)
      } else {
        shell_escape(path, out)
      }
      out.to_string()
    }
  })
}

///|
pub fn InputsCollector::reset(self : InputsCollector) -> Unit {
  self.inputs.clear()
  self.visited.clear()
}

///|
/// Collects the non-phony edges leading to nodes, dependencies first
/// (`ninja -t compdb-targets`).
pub struct CommandCollector {
  visited_nodes : Map[String, Unit]
  visited_edges : Map[Int32, Unit]
  in_edges : Array[Edge]
}

///|
pub fn CommandCollector::new() -> CommandCollector {
  { visited_nodes: Map([]), visited_edges: Map([]), in_edges: [], }
}

///|
pub fn CommandCollector::collect_from(
  self : CommandCollector,
  node : Node,
) -> Unit {
  if self.visited_nodes.contains(node.path) {
    return
  }
  self.visited_nodes[node.path] = ()
  guard node.in_edge is Some(edge) else { return }
  if self.visited_edges.contains(edge.id) {
    return
  }
  self.visited_edges[edge.id] = ()
  for input in edge.inputs {
    self.collect_from(input)
  }
  if !edge.is_phony() {
    self.in_edges.push(edge)
  }
}

///|
pub fn CommandCollector::in_edges(self : CommandCollector) -> Array[Edge] {
  self.in_edges
}

///|
/// Ready edges, highest critical path weight first and lowest id on ties
/// (ninja's `EdgePriorityQueue`).
pub struct EdgePriorityQueue {
  heap : Array[Edge]
}

///|
pub fn EdgePriorityQueue::new() -> EdgePriorityQueue {
  { heap: [], }
}

///|
/// Whether `a` should come out before `b`.
fn edge_before(a : Edge, b : Edge) -> Bool {
  if a.critical_path_weight != b.critical_path_weight {
    a.critical_path_weight > b.critical_path_weight
  } else {
    a.id < b.id
  }
}

///|
pub fn EdgePriorityQueue::length(self : EdgePriorityQueue) -> Int32 {
  self.heap.length()
}

///|
pub fn EdgePriorityQueue::is_empty(self : EdgePriorityQueue) -> Bool {
  self.heap.is_empty()
}

///|
pub fn EdgePriorityQueue::clear(self : EdgePriorityQueue) -> Unit {
  self.heap.clear()
}

///|
pub fn EdgePriorityQueue::push(self : EdgePriorityQueue, edge : Edge) -> Unit {
  let heap = self.heap
  heap.push(edge)
  let mut i = heap.length() - 1
  while i > 0 {
    let parent = (i - 1) / 2
    if !edge_before(heap[i], heap[parent]) {
      break
    }
    heap.swap(i, parent)
    i = parent
  }
}

///|
pub fn EdgePriorityQueue::top(self : EdgePriorityQueue) -> Edge? {
  self.heap.get(0)
}

///|
pub fn EdgePriorityQueue::pop(self : EdgePriorityQueue) -> Edge? {
  let heap = self.heap
  guard heap.length() > 0 else { return None }
  let top = heap[0]
  let last = heap.pop().unwrap()
  if heap.length() > 0 {
    heap[0] = last
    let mut i = 0
    while true {
      let left = 2 * i + 1
      let right = left + 1
      let mut best = i
      if left < heap.length() && edge_before(heap[left], heap[best]) {
        best = left
      }
      if right < heap.length() && edge_before(heap[right], heap[best]) {
        best = right
      }
      if best == i {
        break
      }
      heap.swap(i, best)
      i = best
    }
  }
  Some(top)
}