///|
let operator_names : Array[String] = [
  "$sort", "$reverse", "$json", "$fromNow", "$merge", "$mergeDeep", "$flatten", "$flattenDeep",
  "$eval", "$if", "$let", "$map", "$reduce", "$find", "$match", "$switch",
]

///|
fn interpolate(
  s : String,
  env : Map[String, Value],
  b : Budget,
) -> String raise TemplateError {
  let out = StringBuilder()
  let mut size = 0
  let mut i = 0
  while i < s.length() {
    b.tick(0)
    if i + 3 <= s.length() && s[i:i + 3] == "$${" {
      out.write_string("${")
      size += 2
      i += 3
    } else if i + 2 <= s.length() && s[i:i + 2] == "${" {
      let closing = interpolation_end(s, i + 2, b)
      let source = s[i + 2:closing + 1].to_owned()
      let p = { tokens: tokenize(source, b), pos: 0, budget: b, }
      let e = p.expr(1, 0)
      let end = p.take("}").offset
      let value = evaluate(e, env, b, 0)
      let part = if value == Nil { "" } else { text(value) }
      out.write_string(part)
      size += part.length()
      i += end + 3
    } else {
      let begin = i
      i += 1
      while i < s.length() && s.code_unit_at(i).to_int() != 36 {
        i += 1
      }
      out.write_string(s[begin:i].to_owned())
      size += i - begin
    }
    b.items(size)
  }
  out.to_string()
}

///|
fn allowed(
  o : Map[String, Value],
  keys : Array[String],
) -> Unit raise TemplateError {
  for k, _ in o {
    if !keys.contains(k) {
      raise Invalid("unexpected operator property: " + k)
    }
  }
}

///|
fn required(o : Map[String, Value], k : String) -> Value raise TemplateError {
  match o.get(k) {
    Some(v) => v
    None => raise Invalid("missing operator property: " + k)
  }
}

///|
fn render_value(
  v : Value,
  env : Map[String, Value],
  b : Budget,
  depth : Int32,
) -> Value raise TemplateError {
  b.tick(depth)
  match v {
    Text(s) => Text(interpolate(s, env, b))
    Sequence(xs) => {
      let out = []
      for x in xs {
        let v = render_value(x, env, b, depth + 1)
        if v != Omit {
          out.push(v)
        }
      }
      Sequence(out)
    }
    Record(o) => {
      let ops = o.keys().filter(k => operator_names.contains(k)).collect()
      if ops.length() > 1 {
        raise Invalid("only one operator is allowed")
      }
      if ops.length() == 1 {
        return render_operator(ops[0], o, env, b, depth + 1)
      }
      let out = Map([])
      for k, v in o {
        let key = if k.has_prefix("$$") {
          k[1:].to_owned()
        } else {
          if k.has_prefix("$") && identifier(k[1:].to_owned()) {
            raise Invalid("reserved dollar property")
          }
          interpolate(k, env, b)
        }
        let value = render_value(v, env, b, depth + 1)
        if value != Omit {
          out[key] = value
        }
      }
      Record(out)
    }
    _ => v
  }
}

///|
fn render_operator(
  op : String,
  o : Map[String, Value],
  env : Map[String, Value],
  b : Budget,
  depth : Int32,
) -> Value raise TemplateError {
  b.tick(depth)
  match op {
    "$eval" => {
      allowed(o, [op])
      eval_source(string_value(required(o, op)), env, b)
    }
    "$if" => {
      allowed(o, [op, "then", "else"])
      let condition = eval_source(string_value(required(o, op)), env, b)
      let branch = if truth(condition) { "then" } else { "else" }
      match o.get(branch) {
        Some(v) => render_value(v, env, b, depth + 1)
        None => Omit
      }
    }
    "$let" => {
      allowed(o, [op, "in"])
      if !(required(o, op) is Record(_)) {
        raise Invalid("$let requires literal object")
      }
      let bindings = render_value(required(o, op), env, b, depth + 1)
      let child = env.copy()
      match bindings {
        Record(values) =>
          for k, v in values {
            if !identifier(k) {
              raise Invalid("invalid let binding")
            }
            child[k] = v
          }
        _ => raise Invalid("let bindings must render object")
      }
      render_value(required(o, "in"), child, b, depth + 1)
    }
    "$map" | "$reduce" | "$find" => render_collection(op, o, env, b, depth + 1)
    "$match" | "$switch" => {
      allowed(o, [op])
      let choices = match required(o, op) {
        Record(x) => x
        _ => raise Invalid("match and switch require object")
      }
      let keys = choices.keys().collect()
      keys.sort_by(lexical)
      let out = []
      for key in keys {
        if op == "$switch" && key == "$default" {
          continue
        }
        if truth(eval_source(key, env, b)) {
          out.push(render_value(required(choices, key), env, b, depth + 1))
        }
      }
      if op == "$match" {
        Sequence(out)
      } else {
        if out.length() > 1 {
          raise Invalid("switch has multiple matching conditions")
        }
        if out.length() == 1 {
          out[0]
        } else {
          match choices.get("$default") {
            Some(v) => render_value(v, env, b, depth + 1)
            None => Omit
          }
        }
      }
    }
    "$merge" | "$mergeDeep" => {
      allowed(o, [op])
      let xs = array_value(render_value(required(o, op), env, b, depth + 1))
      let mut result = Record(Map([]))
      for x in xs {
        if !(x is Record(_)) {
          raise Invalid("merge elements must be objects")
        }
        result = merge_values(result, x, op == "$mergeDeep", b, depth + 1)
      }
      result
    }
    "$flatten" | "$flattenDeep" => {
      allowed(o, [op])
      let xs = array_value(render_value(required(o, op), env, b, depth + 1))
      let out = []
      for x in xs {
        flatten_into(x, out, op == "$flattenDeep", b, depth + 1)
      }
      Sequence(out)
    }
    "$reverse" => {
      allowed(o, [op])
      Sequence(
        array_value(render_value(required(o, op), env, b, depth + 1)).rev(),
      )
    }
    "$sort" => sort_template(o, env, b, depth + 1)
    "$json" => {
      allowed(o, [op])
      Text(
        canonical(
          render_value(required(o, op), env, b, depth + 1),
          b,
          depth + 1,
        ),
      )
    }
    "$fromNow" => {
      allowed(o, [op, "from"])
      let offset = string_value(
        render_value(required(o, op), env, b, depth + 1),
      )
      let reference = match o.get("from") {
        Some(v) => string_value(render_value(v, env, b, depth + 1))
        None => string_value(env.get("now").unwrap_or(Nil))
      }
      Text(relative_time(offset, reference, b))
    }
    _ => raise Invalid("unknown template operator")
  }
}

///|
/// Render a JSON-e template. Clock injection keeps generated documents reproducible.
pub fn render(
  template : Json,
  context : Json,
  now~ : String = "1970-01-01T00:00:00.000Z",
  max_steps~ : Int32 = 1000000,
  max_depth~ : Int32 = 128,
  max_items~ : Int32 = 100000,
) -> Json raise TemplateError {
  if max_steps < 1 || max_depth < 1 || max_depth > 256 || max_items < 1 {
    raise Invalid("invalid resource limits")
  }
  let b = { remaining: max_steps, max_depth, max_items, }
  let env = environment(context, b, now)
  let source = from_json(template, b, 0)
  to_json(render_value(source, env, b, 0), b, 0)
}

///|
fn interpolation_end(
  s : String,
  start : Int32,
  b : Budget,
) -> Int32 raise TemplateError {
  let mut nesting = 0
  let mut quote = 0
  for i = start; i < s.length(); i = i + 1 {
    b.tick(0)
    let c = s.code_unit_at(i).to_int()
    if quote != 0 {
      if c == quote {
        quote = 0
      }
      continue
    }
    if c == 34 || c == 39 {
      quote = c
    } else if c == 123 {
      nesting += 1
    } else if c == 125 {
      if nesting == 0 {
        return i
      }
      nesting -= 1
    }
  }
  raise Invalid("unterminated interpolation")
}