///|
pub(all) struct PlanOptions {
  max_results : Int
  max_evaluations : Int
} derive(Debug, Eq)

///|
pub fn plan_options(
  max_results? : Int = 5,
  max_evaluations? : Int = 10000,
) -> PlanOptions {
  { max_results, max_evaluations }
}

///|
pub(all) struct Change {
  feature : String
  from : Value
  to : Value
  cost : Int
} derive(Debug, Eq)

///|
pub fn Change::render(self : Change) -> String {
  "\{self.feature}: \{self.from.render()} -> \{self.to.render()} (cost \{self.cost})"
}

///|
pub(all) struct Repair {
  changes : Array[Change]
  cost : Int
  result : Truth
  trace : Trace
} derive(Debug, Eq)

///|
pub fn Repair::summary(self : Repair) -> String {
  if self.changes.is_empty() {
    return "no changes"
  }
  self.changes.map(change => change.render()).join(", ")
}

///|
pub(all) struct Plan {
  policy_name : String
  baseline : Truth
  target : Truth
  repairs : Array[Repair]
  evaluated : Int
  truncated : Bool
} derive(Debug, Eq)

///|
pub(all) struct PlanCertificate {
  policy_name : String
  baseline : Truth
  target : Truth
  domain_points : Int
  assignments_evaluated : Int
  search_exhaustive : Bool
  output_truncated : Bool
  has_repair : Bool
  best_cost : Int
  lower_cost_excluded : Bool
  status : String
} derive(Debug, Eq)

///|
pub fn Plan::certify(self : Plan, model : Policy) -> PlanCertificate {
  let domain_points = model.search_space_size()
  let search_exhaustive = self.evaluated >= domain_points
  let has_repair = !self.repairs.is_empty()
  let best_cost = if has_repair { self.repairs[0].cost } else { -1 }
  let expected_target = match model.evaluate().truth {
    Yes => No
    No | Unknown => Yes
  }
  let matches_policy = self.policy_name == model.name &&
    self.baseline == model.evaluate().truth &&
    self.target == expected_target
  let lower_cost_excluded = matches_policy && has_repair && search_exhaustive
  let status = if !matches_policy {
    "policy-mismatch"
  } else if has_repair && search_exhaustive {
    "minimum-certified"
  } else if has_repair {
    "best-effort"
  } else if search_exhaustive {
    "no-feasible-repair"
  } else {
    "no-repair-found-in-budget"
  }
  {
    policy_name: self.policy_name,
    baseline: self.baseline,
    target: self.target,
    domain_points,
    assignments_evaluated: self.evaluated,
    search_exhaustive,
    output_truncated: self.truncated,
    has_repair,
    best_cost,
    lower_cost_excluded,
    status,
  }
}

///|
pub fn Policy::search_space_size(self : Policy) -> Int {
  let mut points = 1
  for item in self.features {
    if !item.locked {
      points = points * item.domain.length()
    }
  }
  points
}

///|
priv struct SearchState {
  model : Policy
  target : Truth
  options : PlanOptions
  repairs : Array[Repair]
  mut evaluated : Int
  mut truncated : Bool
}

///|
/// Find the cheapest feasible ways to flip a policy's current outcome. A false
/// outcome targets true, a true outcome targets false, and an unknown outcome
/// targets true so missing/invalid states receive an actionable path forward.
pub fn Policy::plan(
  self : Policy,
  options? : PlanOptions = plan_options(),
) -> Result[Plan, Array[Diagnostic]] {
  let errors = self.validate()
  if !errors.is_empty() {
    return Err(errors)
  }
  if options.max_results <= 0 || options.max_evaluations <= 0 {
    return Err([
      {
        code: "E_PLAN_LIMIT",
        message: "max_results and max_evaluations must both be positive",
        span: { offset: 0, line: 1, column: 1 },
      },
    ])
  }
  let baseline = self.evaluate().truth
  let target = match baseline {
    Yes => No
    No | Unknown => Yes
  }
  let state = SearchState::{
    model: self,
    target,
    options,
    repairs: [],
    evaluated: 0,
    truncated: false,
  }
  search_assignments(state, 0, self.environment(), [], 0)
  state.repairs.sort_by(compare_repairs)
  let minimal = discard_dominated(state.repairs)
  let selected : Array[Repair] = []
  for item in minimal {
    if selected.length() >= options.max_results {
      break
    }
    selected.push(item)
  }
  Ok({
    policy_name: self.name,
    baseline,
    target,
    repairs: selected,
    evaluated: state.evaluated,
    truncated: state.truncated || minimal.length() > options.max_results,
  })
}

///|
fn search_assignments(
  state : SearchState,
  feature_index : Int,
  environment : Environment,
  changes : Array[Change],
  cost : Int,
) -> Unit {
  if state.evaluated >= state.options.max_evaluations {
    state.truncated = true
    return
  }
  if feature_index >= state.model.features.length() {
    state.evaluated = state.evaluated + 1
    if changes.is_empty() {
      return
    }
    let evaluation = evaluate(state.model.goal, environment)
    if evaluation.truth == state.target {
      state.repairs.push({
        changes,
        cost,
        result: evaluation.truth,
        trace: evaluation.trace,
      })
    }
    return
  }
  let item = state.model.features[feature_index]
  if item.locked {
    search_assignments(state, feature_index + 1, environment, changes, cost)
    return
  }
  for candidate in item.domain {
    if state.evaluated >= state.options.max_evaluations {
      state.truncated = true
      return
    }
    if candidate == item.current {
      search_assignments(state, feature_index + 1, environment, changes, cost)
    } else {
      let next_environment = environment_set(environment, item.name, candidate)
      let next_changes = changes.copy()
      next_changes.push({
        feature: item.name,
        from: item.current,
        to: candidate,
        cost: item.cost,
      })
      search_assignments(
        state,
        feature_index + 1,
        next_environment,
        next_changes,
        cost + item.cost,
      )
    }
  }
}

///|
fn compare_repairs(left : Repair, right : Repair) -> Int {
  let by_cost = left.cost.compare(right.cost)
  if by_cost != 0 {
    return by_cost
  }
  let by_count = left.changes.length().compare(right.changes.length())
  if by_count != 0 {
    return by_count
  }
  left.summary().compare(right.summary())
}

///|
/// A repair dominates another when it is no more expensive, changes no more
/// features, and every change it makes also appears identically in the other.
fn repair_dominates(left : Repair, right : Repair) -> Bool {
  if left.cost > right.cost || left.changes.length() > right.changes.length() {
    return false
  }
  for change in left.changes {
    let mut found = false
    for candidate in right.changes {
      if candidate.feature == change.feature && candidate.to == change.to {
        found = true
        break
      }
    }
    if !found {
      return false
    }
  }
  true
}

///|
fn discard_dominated(repairs : Array[Repair]) -> Array[Repair] {
  let result : Array[Repair] = []
  for index, candidate in repairs {
    let mut dominated = false
    for previous in 0.. Environment {
  let mut result = environment.copy()
  for change in self.changes {
    result = environment_set(result, change.feature, change.to)
  }
  result
}

///|
/// Result of changing exactly one feature. Probes expose local sensitivity even
/// when no single edit is sufficient to flip the complete policy.
pub(all) struct Probe {
  feature : String
  from : Value
  to : Value
  cost : Int
  before : Truth
  after : Truth
  flips : Bool
} derive(Debug, Eq)

///|
pub fn Policy::probe(self : Policy) -> Array[Probe] {
  let baseline = self.evaluate().truth
  let environment = self.environment()
  let probes : Array[Probe] = []
  for item in self.features {
    if item.locked {
      continue
    }
    for candidate in item.domain {
      if candidate == item.current {
        continue
      }
      let changed = environment_set(environment, item.name, candidate)
      let outcome = evaluate(self.goal, changed).truth
      probes.push({
        feature: item.name,
        from: item.current,
        to: candidate,
        cost: item.cost,
        before: baseline,
        after: outcome,
        flips: outcome != baseline && outcome != Unknown,
      })
    }
  }
  probes.sort_by((left, right) => {
    if left.flips != right.flips {
      if left.flips {
        -1
      } else {
        1
      }
    } else {
      let by_cost = left.cost.compare(right.cost)
      if by_cost != 0 {
        by_cost
      } else {
        left.feature.compare(right.feature)
      }
    }
  })
  probes
}

///|
pub fn Probe::render(self : Probe) -> String {
  let marker = if self.flips { "FLIPS" } else { "keeps" }
  "\{self.feature}: \{self.from.render()} -> \{self.to.render()} | \{self.before.render()} -> \{self.after.render()} | \{marker}"
}