///|
/// A half-open source range measured in UTF-16 code units.
pub(all) struct SourceSpan {
  start : Int
  end : Int
  line : Int
  column : Int
} derive(Eq, Debug)

///|
pub fn SourceSpan::empty() -> SourceSpan {
  { start: 0, end: 0, line: 1, column: 1 }
}

///|
pub fn SourceSpan::new(
  start~ : Int,
  end~ : Int,
  line~ : Int,
  column~ : Int,
) -> SourceSpan {
  { start, end, line, column }
}

///|
pub fn SourceSpan::length(self : SourceSpan) -> Int {
  self.end - self.start
}

///|
pub fn SourceSpan::is_empty(self : SourceSpan) -> Bool {
  self.start == self.end
}

///|
pub fn SourceSpan::contains(self : SourceSpan, offset : Int) -> Bool {
  offset >= self.start && offset < self.end
}

///|
pub fn SourceSpan::merge(self : SourceSpan, other : SourceSpan) -> SourceSpan {
  if other.start < self.start {
    {
      start: other.start,
      end: self.end.max(other.end),
      line: other.line,
      column: other.column,
    }
  } else {
    {
      start: self.start,
      end: self.end.max(other.end),
      line: self.line,
      column: self.column,
    }
  }
}

///|
pub fn SourceSpan::format(self : SourceSpan) -> String {
  "\{self.line}:\{self.column} [\{self.start}..\{self.end})"
}

///|
pub(all) enum Severity {
  Error
  Warning
  Note
} derive(Eq, Debug)

///|
pub fn Severity::label(self : Severity) -> String {
  match self {
    Error => "error"
    Warning => "warning"
    Note => "note"
  }
}

///|
pub(all) struct Diagnostic {
  code : String
  message : String
  severity : Severity
  span : SourceSpan
} derive(Eq, Debug)

///|
pub fn Diagnostic::error(
  code : String,
  message : String,
  span : SourceSpan,
) -> Diagnostic {
  { code, message, severity: Error, span }
}

///|
pub fn Diagnostic::warning(
  code : String,
  message : String,
  span : SourceSpan,
) -> Diagnostic {
  { code, message, severity: Warning, span }
}

///|
pub fn Diagnostic::note(
  code : String,
  message : String,
  span : SourceSpan,
) -> Diagnostic {
  { code, message, severity: Note, span }
}

///|
pub fn Diagnostic::render(self : Diagnostic) -> String {
  "\{self.severity.label()}[\{self.code}] at \{self.span.format()}: \{self.message}"
}

///|
pub(all) enum Literal {
  Null
  Bool(Bool)
  Int(Int64)
  UInt(UInt64)
  Double(Double)
  String(String)
  Bytes(Bytes)
} derive(Eq, Debug)

///|
pub fn Literal::kind_name(self : Literal) -> String {
  match self {
    Null => "null"
    Bool(_) => "bool"
    Int(_) => "int"
    UInt(_) => "uint"
    Double(_) => "double"
    String(_) => "string"
    Bytes(_) => "bytes"
  }
}

///|
pub(all) enum UnaryOp {
  Not
  Negate
} derive(Eq, Debug)

///|
pub fn UnaryOp::symbol(self : UnaryOp) -> String {
  match self {
    Not => "!"
    Negate => "-"
  }
}

///|
pub(all) enum BinaryOp {
  Or
  And
  Equal
  NotEqual
  Less
  LessEqual
  Greater
  GreaterEqual
  In
  Add
  Subtract
  Multiply
  Divide
  Modulo
} derive(Eq, Debug)

///|
pub fn BinaryOp::symbol(self : BinaryOp) -> String {
  match self {
    Or => "||"
    And => "&&"
    Equal => "=="
    NotEqual => "!="
    Less => "<"
    LessEqual => "<="
    Greater => ">"
    GreaterEqual => ">="
    In => "in"
    Add => "+"
    Subtract => "-"
    Multiply => "*"
    Divide => "/"
    Modulo => "%"
  }
}

///|
pub fn BinaryOp::precedence(self : BinaryOp) -> Int {
  match self {
    Or => 1
    And => 2
    Equal | NotEqual | Less | LessEqual | Greater | GreaterEqual | In => 3
    Add | Subtract => 4
    Multiply | Divide | Modulo => 5
  }
}

///|
pub(all) enum MacroKind {
  Has
  All
  Exists
  ExistsOne
  Map
  Filter
} derive(Eq, Debug)

///|
pub fn MacroKind::name(self : MacroKind) -> String {
  match self {
    Has => "has"
    All => "all"
    Exists => "exists"
    ExistsOne => "exists_one"
    Map => "map"
    Filter => "filter"
  }
}

///|
pub(all) struct MapExprEntry {
  key : Expr
  value : Expr
  span : SourceSpan
} derive(Eq, Debug)

///|
pub(all) enum ExprKind {
  Literal(Literal)
  Identifier(String)
  List(Array[Expr])
  Map(Array[MapExprEntry])
  Unary(UnaryOp, Expr)
  Binary(BinaryOp, Expr, Expr)
  Conditional(Expr, Expr, Expr)
  Select(Expr, String)
  Index(Expr, Expr)
  Call(String, Array[Expr])
  ReceiverCall(Expr, String, Array[Expr])
} derive(Eq, Debug)

///|
pub(all) struct Expr {
  id : Int
  span : SourceSpan
  kind : ExprKind
} derive(Eq, Debug)

///|
pub fn Expr::literal(id : Int, span : SourceSpan, value : Literal) -> Expr {
  { id, span, kind: Literal(value) }
}

///|
pub fn Expr::identifier(id : Int, span : SourceSpan, name : String) -> Expr {
  { id, span, kind: Identifier(name) }
}

///|
pub fn Expr::list(id : Int, span : SourceSpan, values : Array[Expr]) -> Expr {
  { id, span, kind: List(values) }
}

///|
pub fn Expr::map(
  id : Int,
  span : SourceSpan,
  entries : Array[MapExprEntry],
) -> Expr {
  { id, span, kind: Map(entries) }
}

///|
pub fn Expr::unary(
  id : Int,
  span : SourceSpan,
  op : UnaryOp,
  operand : Expr,
) -> Expr {
  { id, span, kind: Unary(op, operand) }
}

///|
pub fn Expr::binary(
  id : Int,
  span : SourceSpan,
  op : BinaryOp,
  left : Expr,
  right : Expr,
) -> Expr {
  { id, span, kind: Binary(op, left, right) }
}

///|
pub fn Expr::conditional(
  id : Int,
  span : SourceSpan,
  condition : Expr,
  when_true : Expr,
  when_false : Expr,
) -> Expr {
  { id, span, kind: Conditional(condition, when_true, when_false) }
}

///|
pub fn Expr::select(
  id : Int,
  span : SourceSpan,
  target : Expr,
  field : String,
) -> Expr {
  { id, span, kind: Select(target, field) }
}

///|
pub fn Expr::index(
  id : Int,
  span : SourceSpan,
  target : Expr,
  index : Expr,
) -> Expr {
  { id, span, kind: Index(target, index) }
}

///|
pub fn Expr::call(
  id : Int,
  span : SourceSpan,
  name : String,
  args : Array[Expr],
) -> Expr {
  { id, span, kind: Call(name, args) }
}

///|
pub fn Expr::receiver_call(
  id : Int,
  span : SourceSpan,
  target : Expr,
  name : String,
  args : Array[Expr],
) -> Expr {
  { id, span, kind: ReceiverCall(target, name, args) }
}

///|
pub fn Expr::kind_name(self : Expr) -> String {
  match self.kind {
    Literal(_) => "literal"
    Identifier(_) => "identifier"
    List(_) => "list"
    Map(_) => "map"
    Unary(_, _) => "unary"
    Binary(_, _, _) => "binary"
    Conditional(_, _, _) => "conditional"
    Select(_, _) => "select"
    Index(_, _) => "index"
    Call(_, _) => "call"
    ReceiverCall(_, _, _) => "receiver_call"
  }
}

///|
pub fn Expr::child_count(self : Expr) -> Int {
  match self.kind {
    Literal(_) | Identifier(_) => 0
    List(items) => items.length()
    Map(entries) => entries.length() * 2
    Unary(_, _) => 1
    Binary(_, _, _) => 2
    Conditional(_, _, _) => 3
    Select(_, _) => 1
    Index(_, _) => 2
    Call(_, args) => args.length()
    ReceiverCall(_, _, args) => args.length() + 1
  }
}

///|
pub fn Expr::node_count(self : Expr) -> Int {
  match self.kind {
    Literal(_) | Identifier(_) => 1
    List(items) =>
      items.fold(init=1, (count, item) => count + item.node_count())
    Map(entries) =>
      entries.fold(init=1, (count, entry) => {
        count + entry.key.node_count() + entry.value.node_count()
      })
    Unary(_, operand) => 1 + operand.node_count()
    Binary(_, left, right) => 1 + left.node_count() + right.node_count()
    Conditional(condition, when_true, when_false) =>
      1 +
      condition.node_count() +
      when_true.node_count() +
      when_false.node_count()
    Select(target, _) => 1 + target.node_count()
    Index(target, index) => 1 + target.node_count() + index.node_count()
    Call(_, args) => args.fold(init=1, (count, arg) => count + arg.node_count())
    ReceiverCall(target, _, args) =>
      args.fold(init=1 + target.node_count(), (count, arg) => {
        count + arg.node_count()
      })
  }
}

///|
pub struct ParsedExpr {
  source : String
  root : Expr
} derive(Debug)

///|
pub fn ParsedExpr::source(self : ParsedExpr) -> String {
  self.source
}

///|
pub fn ParsedExpr::root(self : ParsedExpr) -> Expr {
  self.root
}

///|
pub fn ParsedExpr::node_count(self : ParsedExpr) -> Int {
  self.root.node_count()
}

///|
pub(all) enum CelType {
  Dyn
  Null
  Bool
  Int
  UInt
  Double
  String
  Bytes
  List(CelType)
  Map(CelType, CelType)
} derive(Eq, Debug)

///|
pub fn CelType::display(self : CelType) -> String {
  match self {
    Dyn => "dyn"
    Null => "null"
    Bool => "bool"
    Int => "int"
    UInt => "uint"
    Double => "double"
    String => "string"
    Bytes => "bytes"
    List(element) => "list<\{element.display()}>"
    Map(key, value) => "map<\{key.display()},\{value.display()}>"
  }
}

///|
pub fn CelType::is_numeric(self : CelType) -> Bool {
  self is (Int | UInt | Double)
}

///|
pub fn CelType::is_collection(self : CelType) -> Bool {
  self is (List(_) | Map(_, _))
}

///|
pub fn CelType::accepts(self : CelType, actual : CelType) -> Bool {
  match (self, actual) {
    (Dyn, _) | (_, Dyn) => true
    (List(expected), List(found)) => expected.accepts(found)
    (Map(expected_key, expected_value), Map(found_key, found_value)) =>
      expected_key.accepts(found_key) && expected_value.accepts(found_value)
    _ => self == actual
  }
}

///|
pub fn CelType::common(self : CelType, other : CelType) -> CelType {
  if self == other {
    self
  } else {
    match (self, other) {
      (Dyn, value) | (value, Dyn) => value
      (List(left), List(right)) => List(left.common(right))
      (Map(left_key, left_value), Map(right_key, right_value)) =>
        Map(left_key.common(right_key), left_value.common(right_value))
      _ => Dyn
    }
  }
}

///|
pub(all) struct ValueEntry {
  key : Value
  value : Value
} derive(Eq, Debug)

///|
pub(all) enum Value {
  Null
  Bool(Bool)
  Int(Int64)
  UInt(UInt64)
  Double(Double)
  String(String)
  Bytes(Bytes)
  List(Array[Value])
  Map(Array[ValueEntry])
} derive(Eq, Debug)

///|
pub fn Value::cel_type(self : Value) -> CelType {
  match self {
    Null => Null
    Bool(_) => Bool
    Int(_) => Int
    UInt(_) => UInt
    Double(_) => Double
    String(_) => String
    Bytes(_) => Bytes
    List(values) => {
      let element_type = values.fold(init=Dyn, (current, value) => {
        current.common(value.cel_type())
      })
      List(element_type)
    }
    Map(entries) => {
      let (key_type, value_type) = entries.fold(init=(Dyn, Dyn), (
        current,
        entry,
      ) => {
        (
          current.0.common(entry.key.cel_type()),
          current.1.common(entry.value.cel_type()),
        )
      })
      Map(key_type, value_type)
    }
  }
}

///|
pub fn Value::kind_name(self : Value) -> String {
  self.cel_type().display()
}

///|
pub fn Value::size(self : Value) -> Int? {
  match self {
    String(value) => Some(value.length())
    Bytes(value) => Some(value.length())
    List(value) => Some(value.length())
    Map(value) => Some(value.length())
    _ => None
  }
}

///|
pub fn Value::map_lookup(self : Value, key : Value) -> Value? {
  match self {
    Map(entries) => {
      for entry in entries {
        if entry.key == key {
          return Some(entry.value)
        }
      }
      None
    }
    _ => None
  }
}

///|
pub fn Value::contains(self : Value, needle : Value) -> Bool {
  match self {
    String(haystack) =>
      match needle {
        String(part) => haystack.contains(part)
        _ => false
      }
    List(values) => values.any(value => value == needle)
    Map(entries) => entries.any(entry => entry.key == needle)
    _ => false
  }
}

///|
pub fn Value::display(self : Value) -> String {
  match self {
    Null => "null"
    Bool(value) => if value { "true" } else { "false" }
    Int(value) => value.to_string()
    UInt(value) => "\{value}u"
    Double(value) => value.to_string()
    String(value) => "\"\{value}\""
    Bytes(value) => "bytes(\{value.length()})"
    List(values) => {
      let rendered = values.map(value => value.display()).join(", ")
      "[\{rendered}]"
    }
    Map(entries) => {
      let rendered = entries
        .map(entry => "\{entry.key.display()}: \{entry.value.display()}")
        .join(", ")
      "{ \{rendered} }"
    }
  }
}

///|
pub(all) struct EvalLimits {
  max_cost : Int
  max_depth : Int
  max_iterations : Int
} derive(Eq, Debug)

///|
pub fn EvalLimits::default() -> EvalLimits {
  { max_cost: 10000, max_depth: 64, max_iterations: 10000 }
}

///|
pub fn EvalLimits::new(
  max_cost? : Int = 10000,
  max_depth? : Int = 64,
  max_iterations? : Int = 10000,
) -> EvalLimits {
  { max_cost, max_depth, max_iterations }
}

///|
pub fn EvalLimits::is_valid(self : EvalLimits) -> Bool {
  self.max_cost > 0 && self.max_depth > 0 && self.max_iterations > 0
}

///|
pub(all) struct TypeEnv {
  variables : Map[String, CelType]
} derive(Debug)

///|
pub fn TypeEnv::new() -> TypeEnv {
  { variables: {} }
}

///|
pub fn TypeEnv::with_variable(
  self : TypeEnv,
  name : String,
  cel_type : CelType,
) -> TypeEnv {
  let variables = self.variables.copy()
  variables[name] = cel_type
  { variables, }
}

///|
pub fn TypeEnv::lookup(self : TypeEnv, name : String) -> CelType? {
  self.variables.get(name)
}

///|
pub fn TypeEnv::contains(self : TypeEnv, name : String) -> Bool {
  self.variables.contains(name)
}

///|
pub fn TypeEnv::names(self : TypeEnv) -> Array[String] {
  [
    for name, _ in self.variables => name
  ]
}

///|
pub(all) struct Activation {
  values : Map[String, Value]
} derive(Debug)

///|
pub fn Activation::new() -> Activation {
  { values: {} }
}

///|
pub fn Activation::bind(
  self : Activation,
  name : String,
  value : Value,
) -> Activation {
  let values = self.values.copy()
  values[name] = value
  { values, }
}

///|
pub fn Activation::lookup(self : Activation, name : String) -> Value? {
  self.values.get(name)
}

///|
pub fn Activation::contains(self : Activation, name : String) -> Bool {
  self.values.contains(name)
}

///|
pub struct CheckedExpr {
  parsed : ParsedExpr
  root_type : CelType
  inferred : Map[Int, CelType]
} derive(Debug)

///|
pub fn CheckedExpr::parsed(self : CheckedExpr) -> ParsedExpr {
  self.parsed
}

///|
pub fn CheckedExpr::root_type(self : CheckedExpr) -> CelType {
  self.root_type
}

///|
pub fn CheckedExpr::type_of(self : CheckedExpr, expr_id : Int) -> CelType? {
  self.inferred.get(expr_id)
}

///|
pub(all) struct CheckResult {
  checked : CheckedExpr?
  diagnostics : Array[Diagnostic]
} derive(Debug)

///|
pub fn CheckResult::is_ok(self : CheckResult) -> Bool {
  self.checked is Some(_)
}

///|
pub fn CheckResult::error_count(self : CheckResult) -> Int {
  self.diagnostics.filter(diagnostic => diagnostic.severity == Error).length()
}

///|
pub fn CheckResult::warning_count(self : CheckResult) -> Int {
  self.diagnostics.filter(diagnostic => diagnostic.severity == Warning).length()
}

///|
pub struct Program {
  checked : CheckedExpr
} derive(Debug)

///|
pub fn Program::result_type(self : Program) -> CelType {
  self.checked.root_type
}

///|
pub fn Program::source(self : Program) -> String {
  self.checked.parsed.source
}

///|
pub fn Program::node_count(self : Program) -> Int {
  self.checked.parsed.node_count()
}

///|
pub(all) suberror ParseError {
  ParseError(code~ : String, message~ : String, span~ : SourceSpan)
} derive(Eq, Debug)

///|
pub(all) suberror CompileError {
  CompileError(diagnostics~ : Array[Diagnostic])
} derive(Eq, Debug)

///|
pub(all) suberror EvalError {
  UnboundVariable(name~ : String, span~ : SourceSpan)
  TypeMismatch(expected~ : String, actual~ : String, span~ : SourceSpan)
  NoSuchField(field~ : String, span~ : SourceSpan)
  NoSuchKey(key~ : String, span~ : SourceSpan)
  IndexOutOfBounds(index~ : Int, length~ : Int, span~ : SourceSpan)
  DivisionByZero(span~ : SourceSpan)
  NumericOverflow(span~ : SourceSpan)
  UnknownFunction(name~ : String, span~ : SourceSpan)
  InvalidArgument(message~ : String, span~ : SourceSpan)
  CostLimitExceeded(limit~ : Int, span~ : SourceSpan)
  DepthLimitExceeded(limit~ : Int, span~ : SourceSpan)
  IterationLimitExceeded(limit~ : Int, span~ : SourceSpan)
} derive(Eq, Debug)

///|
pub(all) suberror JsonBridgeError {
  InvalidJsonValue(message~ : String)
  InvalidTypeName(name~ : String)
} derive(Eq, Debug)