///|
/// Create comparison options spanning both traces.
pub fn default_diff_options(left : Trace, right : Trace) -> DiffOptions {
  {
    start: 0L,
    end: Int64::max(left.end_time, right.end_time),
    include_equal: false,
    compare_unknown_case_insensitively: true,
  }
}

///|
/// Return every signal identifier present in either trace.
pub fn union_signal_ids(left : Trace, right : Trace) -> Array[String] {
  let ids : Array[String] = []
  for signal in left.signals {
    if !ids.contains(signal.id) {
      ids.push(signal.id)
    }
  }
  for signal in right.signals {
    if !ids.contains(signal.id) {
      ids.push(signal.id)
    }
  }
  ids
}

///|
/// Compare two optional values with explicit missing-value handling.
fn optional_values_equal(
  left : Value?,
  right : Value?,
  normalize_unknown : Bool,
) -> Bool {
  match (left, right) {
    (None, None) => true
    (Some(a), Some(b)) => values_equal(a, b, normalize_unknown)
    _ => false
  }
}

///|
/// Collect sorted comparison timestamps for one signal.
fn diff_times(left : Trace, right : Trace, signal_id : String) -> Array[Int64] {
  let times : Array[Int64] = [0L, left.end_time, right.end_time]
  for change in left.changes {
    if change.id == signal_id && !times.contains(change.time) {
      times.push(change.time)
    }
  }
  for change in right.changes {
    if change.id == signal_id && !times.contains(change.time) {
      times.push(change.time)
    }
  }
  times.sort()
  times
}

///|
/// Compare two traces at every timestamp where either side changes.
pub fn diff_traces(
  left : Trace,
  right : Trace,
  options : DiffOptions,
) -> Array[TraceDifference] {
  let result : Array[TraceDifference] = []
  for signal_id in union_signal_ids(left, right) {
    for time in diff_times(left, right, signal_id) {
      if time < options.start || time > options.end {
        continue
      }
      let left_value = value_at(left, signal_id, time)
      let right_value = value_at(right, signal_id, time)
      let equal = optional_values_equal(
        left_value,
        right_value,
        options.compare_unknown_case_insensitively,
      )
      if options.include_equal || !equal {
        result.push({
          signal_id,
          time,
          left: left_value,
          right: right_value,
          kind: if equal {
            "equal"
          } else {
            "changed"
          },
        })
      }
    }
  }
  result
}

///|
/// Return whether two traces have no observable differences.
pub fn traces_equal(left : Trace, right : Trace) -> Bool {
  diff_traces(left, right, default_diff_options(left, right)).length() == 0
}

///|
/// Render a compact human-readable diff.
pub fn diff_report(differences : Array[TraceDifference]) -> String {
  let out : Array[String] = []
  out.push("MoonBit VCD diff")
  out.push("differences: \{differences.length()}")
  for difference in differences {
    let left = match difference.left {
      Some(value) => value.display()
      None => ""
    }
    let right = match difference.right {
      Some(value) => value.display()
      None => ""
    }
    out.push(
      "- \{difference.signal_id} @ \{difference.time}: \{left} -> \{right}",
    )
  }
  out.join("\n")
}

///|
/// Return whether two traces declare identical signal paths and widths.
pub fn same_signal_shape(left : Trace, right : Trace) -> Bool {
  if left.signals.length() != right.signals.length() {
    return false
  }
  for signal in left.signals {
    match find_signal(right, signal.id) {
      Some(other) if other.width == signal.width &&
        signal_path(other) == signal_path(signal) => ()
      _ => return false
    }
  }
  true
}