///|
/// Expression nodes used to derive analysis signals from an existing trace.
pub enum DerivedExpr {
  SignalRef(String)
  Constant(Value)
  Not(DerivedExpr)
  And(DerivedExpr, DerivedExpr)
  Or(DerivedExpr, DerivedExpr)
  Xor(DerivedExpr, DerivedExpr)
  Add(DerivedExpr, DerivedExpr)
  Sub(DerivedExpr, DerivedExpr)
  Concat(DerivedExpr, DerivedExpr)
  ShiftLeft(DerivedExpr, Int)
  ShiftRight(DerivedExpr, Int)
  Mux(DerivedExpr, DerivedExpr, DerivedExpr)
  SampleAt(DerivedExpr, Int64)
  EdgeRise(String)
  EdgeFall(String)
} derive(Debug, Eq)

///|
/// A declaration for a calculated signal.
pub struct DerivedSignalSpec {
  id : String
  name : String
  width : Int
  kind : String
  expr : DerivedExpr
} derive(Debug, Eq)

///|
/// One calculated value at a source timestamp.
pub struct DerivedObservation {
  id : String
  time : Int64
  value : Value
  source_changes : Int
} derive(Debug, Eq)

///|
/// Summary counters for derived-signal generation.
pub struct DerivedReport {
  signal_id : String
  expression : String
  timestamps : Int
  changes : Int
  unknowns : Int
  source_changes : Int
} derive(Debug, Eq)

///|
/// Return a reference expression.
pub fn derived_signal(id : String) -> DerivedExpr {
  SignalRef(id)
}

///|
/// Return a constant scalar expression.
pub fn derived_scalar(value : Char) -> DerivedExpr {
  Constant(Scalar(value))
}

///|
/// Return a constant vector expression.
pub fn derived_vector(value : String) -> DerivedExpr {
  Constant(Vector(value))
}

///|
/// Unary expression constructor.
pub fn derived_not(inner : DerivedExpr) -> DerivedExpr {
  Not(inner)
}

///|
/// Bitwise AND expression constructor.
pub fn derived_and(left : DerivedExpr, right : DerivedExpr) -> DerivedExpr {
  And(left, right)
}

///|
/// Bitwise OR expression constructor.
pub fn derived_or(left : DerivedExpr, right : DerivedExpr) -> DerivedExpr {
  Or(left, right)
}

///|
/// Bitwise XOR expression constructor.
pub fn derived_xor(left : DerivedExpr, right : DerivedExpr) -> DerivedExpr {
  Xor(left, right)
}

///|
/// Unsigned addition expression constructor.
pub fn derived_add(left : DerivedExpr, right : DerivedExpr) -> DerivedExpr {
  Add(left, right)
}

///|
/// Unsigned subtraction expression constructor.
pub fn derived_sub(left : DerivedExpr, right : DerivedExpr) -> DerivedExpr {
  Sub(left, right)
}

///|
/// Bus concatenation expression constructor.
pub fn derived_concat(left : DerivedExpr, right : DerivedExpr) -> DerivedExpr {
  Concat(left, right)
}

///|
pub fn derived_shift_left(inner : DerivedExpr, amount : Int) -> DerivedExpr {
  ShiftLeft(inner, amount)
}

///|
pub fn derived_shift_right(inner : DerivedExpr, amount : Int) -> DerivedExpr {
  ShiftRight(inner, amount)
}

///|
pub fn derived_mux(
  condition : DerivedExpr,
  when_true : DerivedExpr,
  when_false : DerivedExpr,
) -> DerivedExpr {
  Mux(condition, when_true, when_false)
}

///|
pub fn derived_sample_at(inner : DerivedExpr, offset : Int64) -> DerivedExpr {
  SampleAt(inner, offset)
}

///|
pub fn derived_edge_rise(id : String) -> DerivedExpr {
  EdgeRise(id)
}

///|
pub fn derived_edge_fall(id : String) -> DerivedExpr {
  EdgeFall(id)
}

///|
/// Return every expression constructor used by report UIs.
pub fn derived_operator_catalog() -> Array[String] {
  [
    "signal", "constant", "not", "and", "or", "xor", "add", "sub", "concat", "shift-left",
    "shift-right", "mux", "sample-at", "edge-rise", "edge-fall",
  ]
}

///|
/// Return a declarative spec for a calculated signal.
pub fn derived_spec(
  id : String,
  name : String,
  width : Int,
  expr : DerivedExpr,
) -> DerivedSignalSpec {
  { id, name, width: Int::max(1, width), kind: "wire", expr }
}

///|
/// Evaluate one expression at a timestamp.
pub fn eval_derived_expr(
  trace : Trace,
  expression : DerivedExpr,
  time : Int64,
) -> Value? {
  match expression {
    SignalRef(id) => value_at(trace, id, time)
    Constant(value) => Some(value)
    Not(inner) => eval_derived_expr(trace, inner, time).map(value_not)
    And(left, right) => combine_expr(trace, left, right, time, value_and)
    Or(left, right) => combine_expr(trace, left, right, time, value_or)
    Xor(left, right) => combine_expr(trace, left, right, time, value_xor)
    Add(left, right) => combine_expr(trace, left, right, time, value_add)
    Sub(left, right) => combine_expr(trace, left, right, time, value_sub)
    Concat(left, right) => combine_expr(trace, left, right, time, value_concat)
    ShiftLeft(inner, amount) =>
      eval_derived_expr(trace, inner, time).map(fn(value) {
        value_shift_left(value, amount)
      })
    ShiftRight(inner, amount) =>
      eval_derived_expr(trace, inner, time).map(fn(value) {
        value_shift_right(value, amount)
      })
    Mux(condition, when_true, when_false) =>
      match eval_derived_expr(trace, condition, time) {
        Some(Scalar('1')) => eval_derived_expr(trace, when_true, time)
        Some(Scalar('0')) => eval_derived_expr(trace, when_false, time)
        _ =>
          Some(
            unknown_like(
              eval_derived_expr(trace, when_true, time),
              eval_derived_expr(trace, when_false, time),
            ),
          )
      }
    SampleAt(inner, offset) =>
      eval_derived_expr(trace, inner, Int64::max(0L, time - offset))
    EdgeRise(id) =>
      Some(Scalar(if is_rising_at(trace, id, time) { '1' } else { '0' }))
    EdgeFall(id) =>
      Some(Scalar(if is_falling_at(trace, id, time) { '1' } else { '0' }))
  }
}

///|
/// Evaluate a derived signal at every distinct source timestamp.
pub fn derived_observations(
  trace : Trace,
  spec : DerivedSignalSpec,
) -> Array[DerivedObservation] {
  trace_times_for_derived(trace).map(fn(time) {
    let value = eval_derived_expr(trace, spec.expr, time).unwrap_or(Scalar('x'))
    {
      id: spec.id,
      time,
      value,
      source_changes: trace.changes_at(time).length(),
    }
  })
}

///|
/// Build a trace with one calculated declaration and only changed values.
pub fn append_derived_signal(trace : Trace, spec : DerivedSignalSpec) -> Trace {
  let observations = derived_observations(trace, spec)
  let signal = {
    id: spec.id,
    name: spec.name,
    width: spec.width,
    kind: spec.kind,
    scope: [],
  }
  let changes = trace.changes.copy()
  let mut previous : Value? = None
  for observation in observations {
    if previous != Some(observation.value) {
      changes.push({
        time: observation.time,
        id: spec.id,
        value: observation.value,
      })
      previous = Some(observation.value)
    }
  }
  {
    ..trace,
    signals: trace.signals + [signal],
    changes: sort_trace_changes({ ..trace, changes, }).changes,
  }
}

///|
/// Append multiple calculated signals in declaration order.
pub fn append_derived_signals(
  trace : Trace,
  specs : Array[DerivedSignalSpec],
) -> Trace {
  let mut result = trace
  for spec in specs {
    result = append_derived_signal(result, spec)
  }
  result
}

///|
/// Return observations as a change array for a standalone pipeline stage.
pub fn derived_changes(
  trace : Trace,
  spec : DerivedSignalSpec,
) -> Array[Change] {
  let observations = derived_observations(trace, spec)
  let changes : Array[Change] = []
  let mut previous : Value? = None
  for observation in observations {
    if previous != Some(observation.value) {
      changes.push({
        time: observation.time,
        id: spec.id,
        value: observation.value,
      })
      previous = Some(observation.value)
    }
  }
  changes
}

///|
/// Return a generation report for one derived signal.
pub fn derived_report(trace : Trace, spec : DerivedSignalSpec) -> DerivedReport {
  let observations = derived_observations(trace, spec)
  let changes = derived_changes(trace, spec)
  {
    signal_id: spec.id,
    expression: derived_expr_text(spec.expr),
    timestamps: observations.length(),
    changes: changes.length(),
    unknowns: observations.count_if(fn(item) { item.value.is_unknown() }),
    source_changes: observations.fold(init=0, fn(total, item) {
      total + item.source_changes
    }),
  }
}

///|
/// Render a generation report as text.
pub fn DerivedReport::to_text(self : DerivedReport) -> String {
  "signal=" +
  self.signal_id +
  " expression=" +
  self.expression +
  " timestamps=" +
  self.timestamps.to_string() +
  " changes=" +
  self.changes.to_string() +
  " unknowns=" +
  self.unknowns.to_string() +
  " source_changes=" +
  self.source_changes.to_string()
}

///|
/// Render a generation report as JSON.
pub fn DerivedReport::to_json(self : DerivedReport) -> String {
  "{\"signal\":\"" +
  csv_cell(self.signal_id) +
  "\",\"expression\":\"" +
  csv_cell(self.expression) +
  "\",\"timestamps\":" +
  self.timestamps.to_string() +
  ",\"changes\":" +
  self.changes.to_string() +
  ",\"unknowns\":" +
  self.unknowns.to_string() +
  ",\"source_changes\":" +
  self.source_changes.to_string() +
  "}"
}

///|
/// Return all timestamps required to evaluate edge-sensitive expressions.
fn trace_times_for_derived(trace : Trace) -> Array[Int64] {
  let times : Array[Int64] = [0L]
  for change in trace.changes {
    if !times.contains(change.time) {
      times.push(change.time)
    }
  }
  times
}

///|
/// Apply a binary value function when both operands are available.
fn combine_expr(
  trace : Trace,
  left : DerivedExpr,
  right : DerivedExpr,
  time : Int64,
  operation : (Value, Value) -> Value,
) -> Value? {
  match
    (
      eval_derived_expr(trace, left, time),
      eval_derived_expr(trace, right, time),
    ) {
    (Some(a), Some(b)) => Some(operation(a, b))
    _ => None
  }
}

///|
/// Return an unknown value with the widest available operand width.
fn unknown_like(left : Value?, right : Value?) -> Value {
  let width = match (left, right) {
    (Some(a), Some(b)) => Int::max(a.width(), b.width())
    (Some(a), None) => a.width()
    (None, Some(b)) => b.width()
    _ => 1
  }
  if width <= 1 {
    Scalar('x')
  } else {
    let chars : Array[String] = []
    for _ in 0.. String {
  match expression {
    SignalRef(id) => id
    Constant(value) => value.display()
    Not(inner) => "not(" + derived_expr_text(inner) + ")"
    And(left, right) => binary_expr_text("and", left, right)
    Or(left, right) => binary_expr_text("or", left, right)
    Xor(left, right) => binary_expr_text("xor", left, right)
    Add(left, right) => binary_expr_text("add", left, right)
    Sub(left, right) => binary_expr_text("sub", left, right)
    Concat(left, right) => binary_expr_text("concat", left, right)
    ShiftLeft(inner, amount) =>
      "shl(" + derived_expr_text(inner) + "," + amount.to_string() + ")"
    ShiftRight(inner, amount) =>
      "shr(" + derived_expr_text(inner) + "," + amount.to_string() + ")"
    Mux(condition, when_true, when_false) =>
      "mux(" +
      derived_expr_text(condition) +
      "," +
      derived_expr_text(when_true) +
      "," +
      derived_expr_text(when_false) +
      ")"
    SampleAt(inner, offset) =>
      "sample(" + derived_expr_text(inner) + "," + offset.to_string() + ")"
    EdgeRise(id) => "rise(" + id + ")"
    EdgeFall(id) => "fall(" + id + ")"
  }
}

///|
/// Return a textual binary expression.
fn binary_expr_text(
  name : String,
  left : DerivedExpr,
  right : DerivedExpr,
) -> String {
  name + "(" + derived_expr_text(left) + "," + derived_expr_text(right) + ")"
}

///|
/// Return whether a signal changed from zero to one at a timestamp.
fn is_rising_at(trace : Trace, signal_id : String, time : Int64) -> Bool {
  let current = value_at(trace, signal_id, time)
  let before = value_at(trace, signal_id, time - 1L)
  current == Some(Scalar('1')) && before == Some(Scalar('0'))
}

///|
/// Return whether a signal changed from one to zero at a timestamp.
fn is_falling_at(trace : Trace, signal_id : String, time : Int64) -> Bool {
  let current = value_at(trace, signal_id, time)
  let before = value_at(trace, signal_id, time - 1L)
  current == Some(Scalar('0')) && before == Some(Scalar('1'))
}