///|
#derive(@debug.Debug)
pub suberror OctagonError {
  Invalid(String)
  Limit(String)
  Arithmetic(String)
}

///|
/// A signed variable term. Sign must be +1 or -1.
#derive(Eq, @debug.Debug, ToJson)
pub(all) struct Term {
  variable : Int32
  sign : Int32
}

///|
/// left + right <= bound. None makes this a unary constraint.
#derive(Eq, @debug.Debug, ToJson)
pub(all) struct Constraint {
  left : Term
  right : Term?
  bound : Int64
}

///|
/// None means unbounded; an empty domain has no interval.
#derive(Eq, @debug.Debug, ToJson)
pub(all) struct Interval {
  lower : Int64?
  upper : Int64?
}

///|
/// Immutable domain over mathematical integers, independent of machine overflow semantics.
pub struct Octagon {
  dimensions : Int32
  matrix : Array[Array[Int64]]
  empty : Bool
}

///|
#derive(Eq, @debug.Debug, ToJson)
pub(all) struct Conflict {
  indices : Array[Int32]
  checks : Int32
}

///|
/// Proven means implication over the abstract state, not concrete reachability.
#derive(@debug.Debug, ToJson)
pub enum Verdict {
  Vacuous
  Proven
  Refuted(Array[Int64])
}

///|
const INF : Int64 = 4000000000000000L

///|
const MAX_FINITE : Int64 = 1000000000000000L

///|
fn plus(a : Int64, b : Int64) -> Int64 raise OctagonError {
  if a == INF || b == INF {
    return INF
  }
  let c = a + b
  if c < -MAX_FINITE || c > MAX_FINITE {
    raise Arithmetic("derived bound exceeds exact arithmetic budget")
  }
  c
}

///|
fn half_floor(v : Int64) -> Int64 {
  let q = v / 2L
  if v < 0L && v % 2L != 0L {
    q - 1L
  } else {
    q
  }
}

///|
fn complement(i : Int32) -> Int32 {
  i ^ 1
}

///|
fn clone_matrix(m : Array[Array[Int64]]) -> Array[Array[Int64]] {
  m.map(row => row.copy())
}

///|
fn validate_dimensions(n : Int32) -> Unit raise OctagonError {
  if n < 1 || n > 24 {
    raise Limit("dimensions \{n} outside 1..24")
  }
}

///|
fn variable(n : Int32, i : Int32) -> Unit raise OctagonError {
  if i < 0 || i >= n {
    raise Invalid("variable index \{i} outside 0..\{n - 1}")
  }
}

///|
fn term_index(n : Int32, t : Term) -> Int32 raise OctagonError {
  variable(n, t.variable)
  if t.sign != 1 && t.sign != -1 {
    raise Invalid("term sign must be 1 or -1, got \{t.sign}")
  }
  2 * t.variable + (if t.sign == 1 { 0 } else { 1 })
}

///|
fn validate_bound(v : Int64) -> Unit raise OctagonError {
  if v < -1000000000L || v > 1000000000L {
    raise Limit("input bound or offset \{v} exceeds +/- 1000000000")
  }
}

///|
fn validate_constraint(n : Int32, c : Constraint) -> Unit raise OctagonError {
  ignore(term_index(n, c.left))
  if c.right is Some(t) {
    ignore(term_index(n, t))
  }
  let bound_limit = if c.right is None { MAX_FINITE / 2L } else { MAX_FINITE }
  if c.bound < -bound_limit || c.bound > bound_limit {
    raise Limit("constraint bound \{c.bound} exceeds exact arithmetic budget")
  }
}

///|
pub fn positive(i : Int32) -> Term {
  { variable: i, sign: 1, }
}

///|
pub fn negative(i : Int32) -> Term {
  { variable: i, sign: -1, }
}

///|
pub fn upper(i : Int32, value : Int64) -> Constraint {
  { left: positive(i), right: None, bound: value, }
}

///|
pub fn lower(i : Int32, value : Int64) -> Constraint {
  // A caller-supplied Int64 minimum is deliberately rejected during validation.
  {
    left: negative(i),
    right: None,
    bound: if value == -9223372036854775808L {
      value
    } else {
      -value
    },
  }
}

///|
pub fn relation(a : Term, b : Term, bound : Int64) -> Constraint {
  { left: a, right: Some(b), bound, }
}

///|
pub fn top(n : Int32) -> Octagon raise OctagonError {
  validate_dimensions(n)
  let size = n * 2
  let m = Array::makei(size, i => {
    Array::makei(size, j => if i == j { 0L } else { INF })
  })
  { dimensions: n, matrix: m, empty: false, }
}

///|
pub fn bottom(n : Int32) -> Octagon raise OctagonError {
  let s = top(n)
  { ..s, empty: true, }
}

///|
pub fn Octagon::size(self : Octagon) -> Int32 {
  self.dimensions
}

///|
pub fn Octagon::is_bottom(self : Octagon) -> Bool {
  self.empty
}

///|
pub fn Octagon::is_top(self : Octagon) -> Bool {
  if self.empty {
    return false
  }
  for i in 0.. Unit raise OctagonError {
  if a.dimensions != b.dimensions {
    raise Invalid(
      "domain dimensions differ: \{a.dimensions} vs \{b.dimensions}",
    )
  }
}