///|
/// Result of one behavior tree node tick.
pub(all) enum BtStatus {
  Success
  Failure
  Running
} derive(Debug, Eq)

///|
pub fn BtStatus::is_done(self : BtStatus) -> Bool {
  self != Running
}

///|
pub fn BtStatus::to_text(self : BtStatus) -> String {
  match self {
    Success => "success"
    Failure => "failure"
    Running => "running"
  }
}

///|
/// Small value type used by the blackboard and the line-based DSL.
pub(all) enum BtValue {
  BoolValue(Bool)
  IntValue(Int)
  TextValue(String)
  EmptyValue
} derive(Debug, Eq)

///|
pub fn bool_value(value : Bool) -> BtValue {
  BoolValue(value)
}

///|
pub fn int_value(value : Int) -> BtValue {
  IntValue(value)
}

///|
pub fn text_value(value : String) -> BtValue {
  TextValue(value)
}

///|
pub fn empty_value() -> BtValue {
  EmptyValue
}

///|
pub fn BtValue::to_text(self : BtValue) -> String {
  match self {
    BoolValue(value) => if value { "true" } else { "false" }
    IntValue(value) => value.to_string()
    TextValue(value) => value
    EmptyValue => ""
  }
}

///|
pub fn BtValue::kind(self : BtValue) -> String {
  match self {
    BoolValue(_) => "bool"
    IntValue(_) => "int"
    TextValue(_) => "text"
    EmptyValue => "empty"
  }
}

///|
pub fn parse_value(raw : String) -> BtValue {
  if raw == "true" {
    BoolValue(true)
  } else if raw == "false" {
    BoolValue(false)
  } else if raw == "" {
    EmptyValue
  } else {
    match parse_decimal_int(raw) {
      Some(value) => IntValue(value)
      None => TextValue(unquote(raw))
    }
  }
}

///|
/// Key-value state shared by all nodes.
pub(all) struct Blackboard {
  mut values : Array[(String, BtValue)]
} derive(Debug, Eq)

///|
pub fn new_blackboard() -> Blackboard {
  { values: Array::new() }
}

///|
pub fn blackboard_from_pairs(pairs : Array[(String, BtValue)]) -> Blackboard {
  let board = new_blackboard()
  let mut i = 0
  while i < pairs.length() {
    board.set(pairs[i].0, pairs[i].1)
    i = i + 1
  }
  board
}

///|
pub fn Blackboard::len(self : Blackboard) -> Int {
  self.values.length()
}

///|
pub fn Blackboard::is_empty(self : Blackboard) -> Bool {
  self.values.length() == 0
}

///|
pub fn Blackboard::set(
  self : Blackboard,
  key : String,
  value : BtValue,
) -> Unit {
  match self.index_of(key) {
    Some(idx) => self.values[idx] = (key, value)
    None => self.values.push((key, value))
  }
}

///|
pub fn Blackboard::get(self : Blackboard, key : String) -> BtValue? {
  match self.index_of(key) {
    Some(idx) => Some(self.values[idx].1)
    None => None
  }
}

///|
pub fn Blackboard::get_text(self : Blackboard, key : String) -> String? {
  match self.get(key) {
    Some(value) => Some(value.to_text())
    None => None
  }
}

///|
pub fn Blackboard::get_bool(self : Blackboard, key : String) -> Bool? {
  match self.get(key) {
    Some(BoolValue(value)) => Some(value)
    _ => None
  }
}

///|
pub fn Blackboard::get_int(self : Blackboard, key : String) -> Int? {
  match self.get(key) {
    Some(IntValue(value)) => Some(value)
    _ => None
  }
}

///|
pub fn Blackboard::has(self : Blackboard, key : String) -> Bool {
  self.index_of(key) is Some(_)
}

///|
pub fn Blackboard::remove(self : Blackboard, key : String) -> Bool {
  match self.index_of(key) {
    Some(idx) => {
      ignore(self.values.remove(idx))
      true
    }
    None => false
  }
}

///|
pub fn Blackboard::keys(self : Blackboard) -> Array[String] {
  let out = Array::new()
  let mut i = 0
  while i < self.values.length() {
    out.push(self.values[i].0)
    i = i + 1
  }
  out
}

///|
pub fn Blackboard::snapshot(self : Blackboard) -> Array[(String, BtValue)] {
  let out = Array::new()
  let mut i = 0
  while i < self.values.length() {
    out.push(self.values[i])
    i = i + 1
  }
  out
}

///|
pub fn Blackboard::to_lines(self : Blackboard) -> Array[String] {
  let lines = Array::new()
  let mut i = 0
  while i < self.values.length() {
    let (key, value) = self.values[i]
    lines.push(key + "=" + value.to_text() + " (" + value.kind() + ")")
    i = i + 1
  }
  lines
}

///|
fn Blackboard::index_of(self : Blackboard, key : String) -> Int? {
  let mut i = 0
  while i < self.values.length() {
    if self.values[i].0 == key {
      return Some(i)
    }
    i = i + 1
  }
  None
}

///|
pub(all) enum CompareOp {
  Eq
  NotEq
  Greater
  GreaterEq
  Less
  LessEq
  Exists
  Missing
} derive(Debug, Eq)

///|
pub fn parse_compare_op(raw : String) -> CompareOp? {
  match raw {
    "eq" | "==" => Some(Eq)
    "ne" | "!=" => Some(NotEq)
    "gt" | ">" => Some(Greater)
    "ge" | ">=" => Some(GreaterEq)
    "lt" | "<" => Some(Less)
    "le" | "<=" => Some(LessEq)
    "exists" => Some(Exists)
    "missing" => Some(Missing)
    _ => None
  }
}

///|
pub fn CompareOp::to_text(self : CompareOp) -> String {
  match self {
    Eq => "eq"
    NotEq => "ne"
    Greater => "gt"
    GreaterEq => "ge"
    Less => "lt"
    LessEq => "le"
    Exists => "exists"
    Missing => "missing"
  }
}

///|
pub fn compare_values(
  actual : BtValue?,
  op : CompareOp,
  expected : BtValue,
) -> Bool {
  match op {
    Exists => actual is Some(_)
    Missing => actual is None
    Eq => actual == Some(expected)
    NotEq => actual != Some(expected)
    Greater =>
      match (actual, expected) {
        (Some(IntValue(a)), IntValue(b)) => a > b
        _ => false
      }
    GreaterEq =>
      match (actual, expected) {
        (Some(IntValue(a)), IntValue(b)) => a >= b
        _ => false
      }
    Less =>
      match (actual, expected) {
        (Some(IntValue(a)), IntValue(b)) => a < b
        _ => false
      }
    LessEq =>
      match (actual, expected) {
        (Some(IntValue(a)), IntValue(b)) => a <= b
        _ => false
      }
  }
}

///|
/// Behavior tree node kind.
pub(all) enum NodeKind {
  Sequence
  Selector
  ParallelAll
  ParallelAny
  Inverter
  Succeeder
  Failer
  Repeat(Int)
  Retry(Int)
  Condition(String, CompareOp, BtValue)
  SetValue(String, BtValue)
  ActionPlan(String, Array[BtStatus], Array[(String, BtValue)])
  Wait(Int)
  Emit(String)
} derive(Debug, Eq)

///|
pub fn NodeKind::to_text(self : NodeKind) -> String {
  match self {
    Sequence => "sequence"
    Selector => "selector"
    ParallelAll => "parallel_all"
    ParallelAny => "parallel_any"
    Inverter => "inverter"
    Succeeder => "succeeder"
    Failer => "failer"
    Repeat(count) => "repeat(" + count.to_string() + ")"
    Retry(count) => "retry(" + count.to_string() + ")"
    Condition(key, op, value) =>
      "condition(" + key + " " + op.to_text() + " " + value.to_text() + ")"
    SetValue(key, value) => "set(" + key + "=" + value.to_text() + ")"
    ActionPlan(name, statuses, writes) =>
      "action(" +
      name +
      ", steps=" +
      statuses.length().to_string() +
      ", writes=" +
      writes.length().to_string() +
      ")"
    Wait(ticks) => "wait(" + ticks.to_string() + ")"
    Emit(label) => "emit(" + label + ")"
  }
}

///|
pub(all) struct BtNode {
  id : String
  name : String
  kind : NodeKind
  children : Array[String]
} derive(Debug, Eq)

///|
pub fn node(
  id : String,
  kind : NodeKind,
  children? : Array[String],
  name? : String,
) -> BtNode {
  { id, name: name.unwrap_or(id), kind, children: children.unwrap_or([]) }
}

///|
pub fn sequence(id : String, children : Array[String]) -> BtNode {
  node(id, Sequence, children~)
}

///|
pub fn selector(id : String, children : Array[String]) -> BtNode {
  node(id, Selector, children~)
}

///|
pub fn condition(
  id : String,
  key : String,
  op : CompareOp,
  expected : BtValue,
) -> BtNode {
  node(id, Condition(key, op, expected))
}

///|
pub fn set_value(id : String, key : String, value : BtValue) -> BtNode {
  node(id, SetValue(key, value))
}

///|
pub fn wait(id : String, ticks : Int) -> BtNode {
  node(id, Wait(ticks))
}

///|
pub fn action_success(
  id : String,
  name? : String,
  writes? : Array[(String, BtValue)],
) -> BtNode {
  let action_name = name.unwrap_or(id)
  node(id, ActionPlan(action_name, [Success], writes.unwrap_or([])))
}

///|
pub fn action_failure(id : String, name? : String) -> BtNode {
  let action_name = name.unwrap_or(id)
  node(id, ActionPlan(action_name, [Failure], []))
}

///|
pub fn action_running_then(
  id : String,
  name : String,
  running_ticks : Int,
  final_status : BtStatus,
  writes? : Array[(String, BtValue)],
) -> BtNode {
  let statuses = Array::new()
  let mut i = 0
  while i < running_ticks {
    statuses.push(Running)
    i = i + 1
  }
  statuses.push(final_status)
  node(id, ActionPlan(name, statuses, writes.unwrap_or([])))
}

///|
pub(all) struct BehaviorTree {
  root : String
  mut nodes : Array[BtNode]
} derive(Debug, Eq)

///|
pub fn new_tree(root : String) -> BehaviorTree {
  { root, nodes: Array::new() }
}

///|
pub fn tree_from_nodes(root : String, nodes : Array[BtNode]) -> BehaviorTree {
  let tree = new_tree(root)
  let mut i = 0
  while i < nodes.length() {
    ignore(tree.add(nodes[i]))
    i = i + 1
  }
  tree
}

///|
pub fn BehaviorTree::add(
  self : BehaviorTree,
  node : BtNode,
) -> Result[Unit, BtError] {
  if node.id == "" {
    return Err(InvalidTree("node id must not be empty"))
  }
  if self.node_index(node.id) is Some(_) {
    return Err(DuplicateNode(node.id))
  }
  self.nodes.push(node)
  Ok(())
}

///|
pub fn BehaviorTree::node(self : BehaviorTree, id : String) -> BtNode? {
  match self.node_index(id) {
    Some(idx) => Some(self.nodes[idx])
    None => None
  }
}

///|
pub fn BehaviorTree::has_node(self : BehaviorTree, id : String) -> Bool {
  self.node_index(id) is Some(_)
}

///|
pub fn BehaviorTree::node_count(self : BehaviorTree) -> Int {
  self.nodes.length()
}

///|
pub fn BehaviorTree::leaf_count(self : BehaviorTree) -> Int {
  let mut count = 0
  let mut i = 0
  while i < self.nodes.length() {
    if self.nodes[i].children.length() == 0 {
      count = count + 1
    }
    i = i + 1
  }
  count
}

///|
pub fn BehaviorTree::ids(self : BehaviorTree) -> Array[String] {
  let out = Array::new()
  let mut i = 0
  while i < self.nodes.length() {
    out.push(self.nodes[i].id)
    i = i + 1
  }
  out
}

///|
pub fn BehaviorTree::validate(self : BehaviorTree) -> ValidationReport {
  let issues = Array::new()
  if self.root == "" {
    issues.push("root id must not be empty")
  } else if !self.has_node(self.root) {
    issues.push("root node is missing: " + self.root)
  }
  let mut i = 0
  while i < self.nodes.length() {
    let current = self.nodes[i]
    let mut c = 0
    while c < current.children.length() {
      if !self.has_node(current.children[c]) {
        issues.push(
          "node " + current.id + " references missing child " + current.children[c],
        )
      }
      c = c + 1
    }
    match current.kind {
      Inverter | Succeeder | Failer | Repeat(_) | Retry(_) =>
        if current.children.length() != 1 {
          issues.push(
            "decorator " +
            current.id +
            " must have exactly one child, got " +
            current.children.length().to_string(),
          )
        }
      Sequence | Selector | ParallelAll | ParallelAny =>
        if current.children.length() == 0 {
          issues.push("composite " + current.id + " must have children")
        }
      Wait(ticks) =>
        if ticks < 0 {
          issues.push("wait node " + current.id + " has negative ticks")
        }
      ActionPlan(_, statuses, _) =>
        if statuses.length() == 0 {
          issues.push("action node " + current.id + " has no scripted status")
        }
      _ => ()
    }
    i = i + 1
  }
  { ok: issues.length() == 0, issues }
}

///|
fn BehaviorTree::node_index(self : BehaviorTree, id : String) -> Int? {
  let mut i = 0
  while i < self.nodes.length() {
    if self.nodes[i].id == id {
      return Some(i)
    }
    i = i + 1
  }
  None
}

///|
pub(all) struct ValidationReport {
  ok : Bool
  issues : Array[String]
} derive(Debug, Eq)

///|
pub fn ValidationReport::message(self : ValidationReport) -> String {
  if self.ok {
    "valid"
  } else {
    join_strings(self.issues, "; ")
  }
}

///|
pub(all) enum BtError {
  DuplicateNode(String)
  MissingNode(String)
  InvalidTree(String)
  ParseError(String)
  LimitExceeded(String)
} derive(Debug, Eq)

///|
pub fn BtError::message(self : BtError) -> String {
  match self {
    DuplicateNode(id) => "duplicate behavior tree node: " + id
    MissingNode(id) => "missing behavior tree node: " + id
    InvalidTree(text) => "invalid behavior tree: " + text
    ParseError(text) => "parse error: " + text
    LimitExceeded(text) => "limit exceeded: " + text
  }
}

///|
pub(all) struct TickConfig {
  max_ticks : Int
  max_trace_events : Int
  record_trace : Bool
} derive(Debug, Eq)

///|
pub fn default_tick_config() -> TickConfig {
  { max_ticks: 1000, max_trace_events: 10000, record_trace: true }
}

///|
pub fn strict_tick_config() -> TickConfig {
  { max_ticks: 128, max_trace_events: 2000, record_trace: true }
}

///|
pub(all) struct NodeMemory {
  id : String
  mut cursor : Int
  mut ticks : Int
  mut attempts : Int
  mut last_status : BtStatus
} derive(Debug, Eq)

///|
fn new_memory(id : String) -> NodeMemory {
  { id, cursor: 0, ticks: 0, attempts: 0, last_status: Running }
}

///|
pub(all) struct TickEvent {
  tick : Int
  node_id : String
  node_name : String
  kind : String
  status : BtStatus
  detail : String
} derive(Debug, Eq)

///|
pub fn TickEvent::to_line(self : TickEvent) -> String {
  "#" +
  self.tick.to_string() +
  " " +
  self.node_id +
  " " +
  self.kind +
  " -> " +
  self.status.to_text() +
  " " +
  self.detail
}

///|
pub(all) struct TickResult {
  tick : Int
  status : BtStatus
  events : Array[TickEvent]
  blackboard : Array[(String, BtValue)]
} derive(Debug, Eq)

///|
pub fn TickResult::summary(self : TickResult) -> String {
  "tick=" +
  self.tick.to_string() +
  ", status=" +
  self.status.to_text() +
  ", events=" +
  self.events.length().to_string() +
  ", blackboard=" +
  self.blackboard.length().to_string()
}

///|
pub(all) struct BtEngine {
  tree : BehaviorTree
  blackboard : Blackboard
  config : TickConfig
  mut tick_count : Int
  mut memory : Array[NodeMemory]
  mut trace : Array[TickEvent]
} derive(Debug, Eq)

///|
pub fn new_engine(
  tree : BehaviorTree,
  blackboard? : Blackboard,
  config? : TickConfig,
) -> BtEngine {
  {
    tree,
    blackboard: blackboard.unwrap_or(new_blackboard()),
    config: config.unwrap_or(default_tick_config()),
    tick_count: 0,
    memory: Array::new(),
    trace: Array::new(),
  }
}

///|
pub fn BtEngine::tick(self : BtEngine) -> Result[TickResult, BtError] {
  let report = self.tree.validate()
  if !report.ok {
    return Err(InvalidTree(report.message()))
  }
  if self.tick_count >= self.config.max_ticks {
    return Err(LimitExceeded("max ticks reached: " + self.config.max_ticks.to_string()))
  }
  self.tick_count = self.tick_count + 1
  let before = self.trace.length()
  let status = self.eval(self.tree.root)
  self.record_root(status)
  let events = self.trace_slice(before)
  Ok({
    tick: self.tick_count,
    status,
    events,
    blackboard: self.blackboard.snapshot(),
  })
}

///|
pub fn BtEngine::run_until_done(
  self : BtEngine,
  max_ticks? : Int,
) -> Result[TickResult, BtError] {
  let limit = max_ticks.unwrap_or(self.config.max_ticks)
  let mut last = {
    tick: self.tick_count,
    status: Running,
    events: [],
    blackboard: self.blackboard.snapshot(),
  }
  while last.status == Running {
    if self.tick_count >= limit {
      return Err(LimitExceeded("run_until_done reached " + limit.to_string() + " ticks"))
    }
    match self.tick() {
      Ok(result) => last = result
      Err(err) => return Err(err)
    }
  }
  Ok(last)
}

///|
pub fn BtEngine::reset(self : BtEngine) -> Unit {
  self.tick_count = 0
  self.memory = Array::new()
  self.trace = Array::new()
}

///|
pub fn BtEngine::trace_lines(self : BtEngine) -> Array[String] {
  let lines = Array::new()
  let mut i = 0
  while i < self.trace.length() {
    lines.push(self.trace[i].to_line())
    i = i + 1
  }
  lines
}

///|
pub fn BtEngine::trace_digest(self : BtEngine) -> String {
  let lines = self.trace_lines()
  stable_digest(join_strings(lines, "\n"))
}

///|
fn BtEngine::eval(self : BtEngine, id : String) -> BtStatus {
  match self.tree.node(id) {
    Some(n) => {
      let status = self.eval_node(n)
      self.record(n, status, "")
      status
    }
    None => {
      let fake = node(id, Emit("missing"))
      self.record(fake, Failure, "missing node")
      Failure
    }
  }
}

///|
fn BtEngine::eval_node(self : BtEngine, n : BtNode) -> BtStatus {
  match n.kind {
    Sequence => self.eval_sequence(n)
    Selector => self.eval_selector(n)
    ParallelAll => self.eval_parallel_all(n)
    ParallelAny => self.eval_parallel_any(n)
    Inverter => self.eval_inverter(n)
    Succeeder => self.eval_decorator_constant(n, Success)
    Failer => self.eval_decorator_constant(n, Failure)
    Repeat(count) => self.eval_repeat(n, count)
    Retry(count) => self.eval_retry(n, count)
    Condition(key, op, expected) =>
      if compare_values(self.blackboard.get(key), op, expected) {
        Success
      } else {
        Failure
      }
    SetValue(key, value) => {
      self.blackboard.set(key, value)
      Success
    }
    ActionPlan(_, statuses, writes) => self.eval_action(n, statuses, writes)
    Wait(ticks) => self.eval_wait(n, ticks)
    Emit(label) => {
      self.record(n, Success, "emit=" + label)
      Success
    }
  }
}

///|
fn BtEngine::eval_sequence(self : BtEngine, n : BtNode) -> BtStatus {
  let idx = self.memory_index(n.id)
  while self.memory[idx].cursor < n.children.length() {
    let child = n.children[self.memory[idx].cursor]
    let status = self.eval(child)
    if status == Success {
      self.memory[idx].cursor = self.memory[idx].cursor + 1
    } else if status == Running {
      self.memory[idx].last_status = Running
      return Running
    } else {
      self.memory[idx].cursor = 0
      self.memory[idx].last_status = Failure
      return Failure
    }
  }
  self.memory[idx].cursor = 0
  self.memory[idx].last_status = Success
  Success
}

///|
fn BtEngine::eval_selector(self : BtEngine, n : BtNode) -> BtStatus {
  let idx = self.memory_index(n.id)
  while self.memory[idx].cursor < n.children.length() {
    let child = n.children[self.memory[idx].cursor]
    let status = self.eval(child)
    if status == Failure {
      self.memory[idx].cursor = self.memory[idx].cursor + 1
    } else if status == Running {
      self.memory[idx].last_status = Running
      return Running
    } else {
      self.memory[idx].cursor = 0
      self.memory[idx].last_status = Success
      return Success
    }
  }
  self.memory[idx].cursor = 0
  self.memory[idx].last_status = Failure
  Failure
}

///|
fn BtEngine::eval_parallel_all(self : BtEngine, n : BtNode) -> BtStatus {
  let mut saw_running = false
  let mut i = 0
  while i < n.children.length() {
    let status = self.eval(n.children[i])
    if status == Failure {
      return Failure
    }
    if status == Running {
      saw_running = true
    }
    i = i + 1
  }
  if saw_running { Running } else { Success }
}

///|
fn BtEngine::eval_parallel_any(self : BtEngine, n : BtNode) -> BtStatus {
  let mut saw_running = false
  let mut i = 0
  while i < n.children.length() {
    let status = self.eval(n.children[i])
    if status == Success {
      return Success
    }
    if status == Running {
      saw_running = true
    }
    i = i + 1
  }
  if saw_running { Running } else { Failure }
}

///|
fn BtEngine::eval_inverter(self : BtEngine, n : BtNode) -> BtStatus {
  if n.children.length() != 1 {
    return Failure
  }
  match self.eval(n.children[0]) {
    Success => Failure
    Failure => Success
    Running => Running
  }
}

///|
fn BtEngine::eval_decorator_constant(
  self : BtEngine,
  n : BtNode,
  status : BtStatus,
) -> BtStatus {
  if n.children.length() == 1 {
    ignore(self.eval(n.children[0]))
  }
  status
}

///|
fn BtEngine::eval_repeat(self : BtEngine, n : BtNode, count : Int) -> BtStatus {
  if n.children.length() != 1 || count <= 0 {
    return Failure
  }
  let idx = self.memory_index(n.id)
  let child_status = self.eval(n.children[0])
  if child_status == Running {
    return Running
  }
  self.memory[idx].attempts = self.memory[idx].attempts + 1
  if self.memory[idx].attempts >= count {
    self.memory[idx].attempts = 0
    Success
  } else {
    Running
  }
}

///|
fn BtEngine::eval_retry(self : BtEngine, n : BtNode, count : Int) -> BtStatus {
  if n.children.length() != 1 || count <= 0 {
    return Failure
  }
  let idx = self.memory_index(n.id)
  let child_status = self.eval(n.children[0])
  if child_status == Success {
    self.memory[idx].attempts = 0
    return Success
  }
  if child_status == Running {
    return Running
  }
  self.memory[idx].attempts = self.memory[idx].attempts + 1
  if self.memory[idx].attempts >= count {
    self.memory[idx].attempts = 0
    Failure
  } else {
    Running
  }
}

///|
fn BtEngine::eval_action(
  self : BtEngine,
  n : BtNode,
  statuses : Array[BtStatus],
  writes : Array[(String, BtValue)],
) -> BtStatus {
  if statuses.length() == 0 {
    return Failure
  }
  let idx = self.memory_index(n.id)
  let step = if self.memory[idx].ticks < statuses.length() {
    self.memory[idx].ticks
  } else {
    statuses.length() - 1
  }
  let status = statuses[step]
  if status == Running {
    self.memory[idx].ticks = self.memory[idx].ticks + 1
    Running
  } else {
    if status == Success {
      apply_writes(self.blackboard, writes)
    }
    self.memory[idx].ticks = 0
    status
  }
}

///|
fn BtEngine::eval_wait(self : BtEngine, n : BtNode, ticks : Int) -> BtStatus {
  if ticks <= 0 {
    return Success
  }
  let idx = self.memory_index(n.id)
  self.memory[idx].ticks = self.memory[idx].ticks + 1
  if self.memory[idx].ticks >= ticks {
    self.memory[idx].ticks = 0
    Success
  } else {
    Running
  }
}

///|
fn BtEngine::memory_index(self : BtEngine, id : String) -> Int {
  let mut i = 0
  while i < self.memory.length() {
    if self.memory[i].id == id {
      return i
    }
    i = i + 1
  }
  self.memory.push(new_memory(id))
  self.memory.length() - 1
}

///|
fn BtEngine::record(self : BtEngine, n : BtNode, status : BtStatus, detail : String) -> Unit {
  if self.config.record_trace && self.trace.length() < self.config.max_trace_events {
    self.trace.push({
      tick: self.tick_count,
      node_id: n.id,
      node_name: n.name,
      kind: n.kind.to_text(),
      status,
      detail,
    })
  }
}

///|
fn BtEngine::record_root(self : BtEngine, status : BtStatus) -> Unit {
  if self.config.record_trace && self.trace.length() < self.config.max_trace_events {
    self.trace.push({
      tick: self.tick_count,
      node_id: self.tree.root,
      node_name: "root",
      kind: "tree",
      status,
      detail: "root result",
    })
  }
}

///|
fn BtEngine::trace_slice(self : BtEngine, start : Int) -> Array[TickEvent] {
  let out = Array::new()
  let mut i = start
  while i < self.trace.length() {
    out.push(self.trace[i])
    i = i + 1
  }
  out
}

///|
fn apply_writes(board : Blackboard, writes : Array[(String, BtValue)]) -> Unit {
  let mut i = 0
  while i < writes.length() {
    board.set(writes[i].0, writes[i].1)
    i = i + 1
  }
}

///|
fn join_strings(values : Array[String], separator : String) -> String {
  let mut out = ""
  let mut i = 0
  while i < values.length() {
    if i > 0 {
      out = out + separator
    }
    out = out + values[i]
    i = i + 1
  }
  out
}

///|
fn unquote(raw : String) -> String {
  let value = trim_ascii(raw)
  if value.length() >= 2 && value[0] == 34 && value[value.length() - 1] == 34 {
    value.unsafe_substring(start=1, end=value.length() - 1)
  } else {
    value
  }
}

///|
fn trim_ascii(raw : String) -> String {
  let mut start = 0
  let mut end = raw.length()
  while start < end && is_ascii_space(raw[start]) {
    start = start + 1
  }
  while end > start && is_ascii_space(raw[end - 1]) {
    end = end - 1
  }
  raw.unsafe_substring(start~, end~)
}

///|
fn is_ascii_space(ch : UInt16) -> Bool {
  ch == 32 || ch == 9 || ch == 10 || ch == 13
}

///|
fn parse_decimal_int(raw : String) -> Int? {
  let value = trim_ascii(raw)
  if value == "" {
    return None
  }
  let mut sign = 1
  let mut index = 0
  if value[0] == 45 {
    sign = -1
    index = 1
  } else if value[0] == 43 {
    index = 1
  }
  if index >= value.length() {
    return None
  }
  let mut number = 0
  while index < value.length() {
    let code = value[index]
    if code < 48 || code > 57 {
      return None
    }
    number = number * 10 + (code.to_int() - 48)
    index = index + 1
  }
  Some(number * sign)
}

///|
fn stable_digest(input : String) -> String {
  let mut hash = 216613626
  let mut i = 0
  while i < input.length() {
    hash = ((hash * 16777619) + input[i].to_int()) & 0x7fffffff
    i = i + 1
  }
  "bt-" + hash.to_string()
}