///|
/// One observable step in expression evaluation.
pub(all) struct TraceStep {
  span : Span
  expression : String
  value : Json
} derive(Eq, Debug, ToJson, FromJson)

///|
/// The result and ordered steps from an explained evaluation.
pub(all) struct EvaluationTrace {
  value : Json
  steps : Array[TraceStep]
} derive(Eq, Debug, ToJson, FromJson)

///|
pub fn EvaluationTrace::to_json_string(
  self : EvaluationTrace,
  indent? : Int = 2,
) -> String {
  self.to_json().stringify(indent~)
}

///|
fn trace_expression(source : String, span : Span) -> String {
  if span.start >= 0 && span.end >= span.start && span.end <= source.length() {
    source[span.start:span.end].to_owned()
  } else {
    ""
  }
}

///|
fn record_trace(
  steps : Array[TraceStep],
  source : String,
  span : Span,
  value : Json,
) -> Json {
  steps.push({ span, expression: trace_expression(source, span), value })
  value
}

///|
fn evaluate_optional_base_with_trace(
  expression : Expr,
  context : Json,
  source : String,
  steps : Array[TraceStep],
) -> Json raise RuleFailure {
  match expression {
    Variable(name, span) => {
      let value = evaluate_optional_variable(context, name, span)
      record_trace(steps, source, span, value)
    }
    other => evaluate_expr_with_trace(other, context, source, steps)
  }
}

///|
fn evaluate_expr_with_trace(
  expr : Expr,
  context : Json,
  source : String,
  steps : Array[TraceStep],
) -> Json raise RuleFailure {
  let result = match expr {
    Literal(value, _) => value
    Variable(name, span) => evaluate_member(context, name, span)
    ArrayLiteral(expressions, _) =>
      Json::array(
        expressions.map(value => {
          evaluate_expr_with_trace(value, context, source, steps)
        }),
      )
    Member(target, name, span) =>
      evaluate_member(
        evaluate_expr_with_trace(target, context, source, steps),
        name,
        span,
      )
    Index(target, index, span) =>
      evaluate_index(
        evaluate_expr_with_trace(target, context, source, steps),
        evaluate_expr_with_trace(index, context, source, steps),
        span,
      )
    OptionalMember(target, name, span) =>
      evaluate_optional_member(
        evaluate_optional_base_with_trace(target, context, source, steps),
        name,
        span,
      )
    OptionalIndex(target, index, span) => {
      let target_value = evaluate_optional_base_with_trace(
        target, context, source, steps,
      )
      if target_value == Json::null() {
        Json::null()
      } else {
        evaluate_optional_index(
          target_value,
          evaluate_expr_with_trace(index, context, source, steps),
          span,
        )
      }
    }
    Call(name, arguments, span) =>
      evaluate_call(
        name,
        arguments.map(argument => {
          evaluate_expr_with_trace(argument, context, source, steps)
        }),
        span,
      )
    Unary(operator, operand, span) => {
      let value = evaluate_expr_with_trace(operand, context, source, steps)
      match operator {
        Not => Json::boolean(!expect_bool(value, span))
        Negate => Json::number(-expect_number(value, span))
      }
    }
    Binary(left, Or, right, _) => {
      let left_value = expect_bool(
        evaluate_expr_with_trace(left, context, source, steps),
        left.span(),
      )
      if left_value {
        Json::boolean(true)
      } else {
        Json::boolean(
          expect_bool(
            evaluate_expr_with_trace(right, context, source, steps),
            right.span(),
          ),
        )
      }
    }
    Binary(left, And, right, _) => {
      let left_value = expect_bool(
        evaluate_expr_with_trace(left, context, source, steps),
        left.span(),
      )
      if !left_value {
        Json::boolean(false)
      } else {
        Json::boolean(
          expect_bool(
            evaluate_expr_with_trace(right, context, source, steps),
            right.span(),
          ),
        )
      }
    }
    Binary(left, operator, right, span) =>
      evaluate_binary(
        evaluate_expr_with_trace(left, context, source, steps),
        operator,
        evaluate_expr_with_trace(right, context, source, steps),
        span,
      )
  }
  record_trace(steps, source, expr.span(), result)
}

///|
/// Evaluate a program and retain a deterministic, machine-readable trace.
pub fn explain(
  program : Program,
  context : Json,
) -> Result[EvaluationTrace, Diagnostic] {
  let steps = []
  try {
    let value = evaluate_expr_with_trace(
      program.root,
      context,
      program.source,
      steps,
    )
    Ok({ value, steps })
  } catch {
    RuleFailure(diagnostic) => Err(diagnostic)
  }
}