///|
/// One relevant graph evaluation. Offsets describe ages, not absolute times.
/// An absent witness for a false Once/Since describes absence over the observed
/// window, not proof that no unobserved real-world event occurred.
pub(all) struct Evidence {
  node : Int32
  kind : String
  value : Bool
  position : Int32
  time : Int64
  lower_age : Int64?
  upper_age : Int64?
  witness : Witness?
  barrier : Witness?
}

///|
fn node_kind(node : Node) -> String {
  match node {
    Literal(_) => "constant"
    Input(name) => "atom:" + name
    Neg(_) => "not"
    Both(_, _) => "and"
    Either(_, _) => "or"
    Implication(_, _) => "implies"
    Prior(_) => "previous"
    AnyPast(_, _) => "once"
    AllPast(_, _) => "historically"
    SincePast(_, _, _) => "since"
  }
}

///|
fn node_interval(node : Node) -> Interval? {
  match node {
    AnyPast(window, _) | AllPast(window, _) | SincePast(window, _, _) =>
      Some(window)
    _ => None
  }
}

///|
/// Explain the most recent rule decision. Boolean branches select sufficient
/// evidence; temporal nodes stop at the historical witness instead of wrongly
/// explaining their child's value at the current observation.
pub fn Monitor::explain(
  self : Monitor,
  name : String,
) -> Result[Array[Evidence], MonitorError] {
  if self.processed == 0 {
    return Err(InvalidPosition(0))
  }
  let index = match self.plan.rule_index(name) {
    Some(index) => index
    None => return Err(SyntaxError(0, "unknown rule " + name))
  }
  let root = self.plan.roots[index]
  let pending = [root]
  let visited = Array::make(self.plan.nodes.length(), false)
  let result : Array[Evidence] = []
  while !pending.is_empty() {
    let id = pending.pop().unwrap()
    if visited[id] {
      continue
    }
    visited[id] = true
    let node = self.plan.nodes[id]
    let value = self.last_values[id]
    let window = node_interval(node)
    result.push({
      node: id,
      kind: node_kind(node),
      value,
      position: self.processed - 1,
      time: self.last_time.unwrap(),
      lower_age: window.map(w => w.lower),
      upper_age: window.map(w => w.upper),
      witness: self.witnesses[id],
      barrier: self.barriers[id],
    })
    match node {
      Neg(child) => pending.push(child)
      Both(a, b) =>
        if value {
          pending.push(b)
          pending.push(a)
        } else {
          pending.push(if !self.last_values[a] { a } else { b })
        }
      Either(a, b) =>
        if !value {
          pending.push(b)
          pending.push(a)
        } else {
          pending.push(if self.last_values[a] { a } else { b })
        }
      Implication(a, b) =>
        if !value {
          pending.push(b)
          pending.push(a)
        } else {
          pending.push(if !self.last_values[a] { a } else { b })
        }
      _ => ()
    }
  }
  Ok(result)
}

///|
/// Recover the immutable AST corresponding to each topologically ordered node.
/// This retains sharing but has no online Boolean values or witness queues.
fn Plan::node_formulas(self : Plan) -> Array[Formula] {
  let formulas : Array[Formula] = []
  for node in self.nodes {
    let formula = match node {
      Literal(v) => Constant(v)
      Input(name) => Atom(name)
      Neg(c) => Not(formulas[c])
      Both(a, b) => And(formulas[a], formulas[b])
      Either(a, b) => Or(formulas[a], formulas[b])
      Implication(a, b) => Implies(formulas[a], formulas[b])
      Prior(c) => Previous(formulas[c])
      AnyPast(w, c) => Once(w, formulas[c])
      AllPast(w, c) => Historically(w, formulas[c])
      SincePast(w, a, b) => Since(w, formulas[a], formulas[b])
    }
    formulas.push(formula)
  }
  formulas
}

///|
/// Independently re-evaluate a complete decision against its input prefix.
/// Matching verdicts says nothing about unobserved executions or authenticity.
pub fn Plan::verify_decision(
  self : Plan,
  trace : Array[Observation],
  decision : Decision,
) -> Result[Bool, MonitorError] {
  match self.validate_trace(trace) {
    Err(e) => return Err(e)
    Ok(_) => ()
  }
  if decision.position < 0 || decision.position >= trace.length() {
    return Err(InvalidPosition(decision.position))
  }
  if decision.time != trace[decision.position].time ||
    decision.names != self.names ||
    decision.values.length() != self.roots.length() {
    return Ok(false)
  }
  let reference = match Reference::new(self, trace) {
    Err(e) => return Err(e)
    Ok(value) => value
  }
  match reference.evaluate(decision.position) {
    Err(e) => return Err(e)
    Ok(expected) => return Ok(expected.values == decision.values)
  }
}

///|
/// Verify reported node values and any witness/barrier against actual records.
/// This validates fragments, not completeness of a caller-supplied explanation.
pub fn Plan::verify_evidence(
  self : Plan,
  trace : Array[Observation],
  evidence : Array[Evidence],
) -> Result[Bool, MonitorError] {
  match self.validate_trace(trace) {
    Err(e) => return Err(e)
    Ok(_) => ()
  }
  if evidence.length() > self.nodes.length() {
    return Err(ResourceLimit("evidence length"))
  }
  let formulas = self.node_formulas()
  let work = ReferenceWork::{ remaining: 1000000, }
  let seen = Array::make(self.nodes.length(), false)
  for fragment in evidence {
    let id = fragment.node
    let at = fragment.position
    if id < 0 || id >= self.nodes.length() || at < 0 || at >= trace.length() {
      return Ok(false)
    }
    if seen[id] {
      return Ok(false)
    }
    seen[id] = true
    let node = self.nodes[id]
    if fragment.kind != node_kind(node) || fragment.time != trace[at].time {
      return Ok(false)
    }
    let window = node_interval(node)
    if fragment.lower_age != window.map(w => w.lower) ||
      fragment.upper_age != window.map(w => w.upper) {
      return Ok(false)
    }
    let actual = match reference_at(formulas[id], trace, at, work) {
      Err(e) => return Err(e)
      Ok(v) => v
    }
    if fragment.value != actual {
      return Ok(false)
    }
    match (node, fragment.witness) {
      (Prior(_), witness) =>
        if at == 0 {
          if witness is Some(_) {
            return Ok(false)
          }
        } else {
          match witness {
            Some(w) if w.position == at - 1 && w.time == trace[at - 1].time =>
              ()
            _ => return Ok(false)
          }
        }
      (AnyPast(w, child), witness)
      | (AllPast(w, child), witness)
      | (SincePast(w, _, child), witness) => {
        let expected_witness = if node is AllPast(_, _) {
          !actual
        } else {
          actual
        }
        if expected_witness != (witness is Some(_)) {
          return Ok(false)
        }
        if witness is Some(found) {
          let j = found.position
          if j < 0 || j > at || found.time != trace[j].time {
            return Ok(false)
          }
          let age = trace[at].time - found.time
          if age < w.lower || age > w.upper {
            return Ok(false)
          }
          let child_value = match
            reference_at(formulas[child], trace, j, work) {
            Err(e) => return Err(e)
            Ok(v) => v
          }
          if child_value == (node is AllPast(_, _)) {
            return Ok(false)
          }
          match node {
            SincePast(_, left, _) =>
              for k in (j + 1)..<(at + 1) {
                match reference_at(formulas[left], trace, k, work) {
                  Err(e) => return Err(e)
                  Ok(false) => return Ok(false)
                  Ok(true) => ()
                }
              }
            _ => ()
          }
        }
      }
      (_, None) => ()
      _ => return Ok(false)
    }
    match (node, fragment.barrier) {
      (SincePast(_, left, _), Some(found)) => {
        let j = found.position
        if j < 0 || j > at || found.time != trace[j].time {
          return Ok(false)
        }
        match reference_at(formulas[left], trace, j, work) {
          Err(e) => return Err(e)
          Ok(true) => return Ok(false)
          Ok(false) => ()
        }
      }
      (_, None) => ()
      _ => return Ok(false)
    }
  }
  Ok(true)
}