///|
#derive(ToJson, FromJson)
priv enum WindowBound {
  UnboundedPreceding
  Preceding(Expr)
  Current
  Following(Expr)
  UnboundedFollowing
}

///|
#derive(ToJson, FromJson)
priv struct WindowFrame {
  kind : String
  start : WindowBound
  end : WindowBound
}

///|
fn Parser::window_bound(p : Parser) -> WindowBound raise SqlError {
  if p.take("unbounded") {
    if p.take("preceding") {
      UnboundedPreceding
    } else {
      p.expect("following")
      UnboundedFollowing
    }
  } else if p.take("current") {
    p.expect("row")
    Current
  } else {
    let e = p.expression(1)
    if p.take("preceding") {
      Preceding(e)
    } else {
      p.expect("following")
      Following(e)
    }
  }
}

///|
fn Parser::window_frame(p : Parser) -> WindowFrame raise SqlError {
  let kind = p.peek()
  if !["rows", "range", "groups"].contains(kind) {
    return { kind: "range", start: UnboundedPreceding, end: Current, }
  }
  p.position += 1
  if p.take("between") {
    let start = p.window_bound()
    p.expect("and")
    { kind, start, end: p.window_bound(), }
  } else {
    { kind, start: p.window_bound(), end: Current, }
  }
}

///|
fn aggregate_name(name : String) -> Bool {
  ["count", "sum", "total", "avg", "min", "max", "group_concat", "string_agg"].contains(
    name,
  )
}

///|
fn window_arity(name : String, n : Int32) -> Bool {
  match name {
    "lag" | "lead" => n >= 1 && n <= 3
    "row_number" | "rank" | "dense_rank" | "percent_rank" | "cume_dist" =>
      n == 0
    "ntile" | "first_value" | "last_value" => n == 1
    "nth_value" => n == 2
    "group_concat" => n == 1 || n == 2
    "string_agg" => n == 2
    _ => aggregate_name(name) && n == 1
  }
}

///|
fn group_concat(args : Array[Expr], ctx : Evaluation) -> Value raise SqlError {
  let distinct = args[0] is Call("$distinct", _)
  let arg = match args[0] {
    Call("$distinct", [e]) => e
    _ => args[0]
  }
  let seen : Array[Value] = []
  let out = @buffer.Buffer()
  for row in ctx.group.unwrap_or([ctx.row]) {
    let here = { ..ctx, row, group: None, }
    let value = evaluate(arg, here)
    if value is Null ||
      (
        distinct &&
        seen.any(v => {
          compare_stored(ctx.store, v, value, expression_collation(arg, ctx)) ==
          0
        })
      ) {
      continue
    }
    if !seen.is_empty() {
      out.write_bytes(
        @utf8.encode(
          if args.length() == 2 {
            checked_text_value(evaluate(args[1], here))
          } else {
            ","
          },
        ),
      )
    }
    out.write_bytes(@utf8.encode(checked_text_value(value)))
    seen.push(value)
  }
  if seen.is_empty() {
    Null
  } else {
    Text(@utf8.decode_lossy(out.to_bytes()))
  }
}

///|
fn collect_windows(e : Expr, out : Array[Expr]) -> Unit {
  match e {
    Window(_, _, _, _, _) =>
      if !out.any(previous => @json.to_json(previous) == @json.to_json(e)) {
        out.push(e)
      }
    Unary(_, e) | Cast(e, _) | Collate(e, _) => collect_windows(e, out)
    Binary(_, a, b) => {
      collect_windows(a, out)
      collect_windows(b, out)
    }
    Call(_, args) =>
      for e in args {
        collect_windows(e, out)
      }
    Between(a, b, c) => {
      collect_windows(a, out)
      collect_windows(b, out)
      collect_windows(c, out)
    }
    Case(base, arms, other) => {
      if base is Some(e) {
        collect_windows(e, out)
      }
      for (a, b) in arms {
        collect_windows(a, out)
        collect_windows(b, out)
      }
      collect_windows(other, out)
    }
    _ => ()
  }
}

///|
fn window_offset(e : Expr, ctx : Evaluation) -> Int32 raise SqlError {
  let v = evaluate(e, ctx)
  let n = cast_integer(v)
  guard !(v is Null) &&
    n >= 0L &&
    n <= 1000000000L &&
    compare_stored(ctx.store, numeric(v, false), Integer(n), "binary") == 0 else {
    fail("frame offset must be a non-negative integer")
  }
  n.to_int()
}

///|
fn compute_windows(
  expressions : Array[Expr],
  contexts : Array[Evaluation],
  base : Evaluation,
) -> Unit raise SqlError {
  for expression in expressions {
    guard expression is Window(name, args, partitions, orders, frame) else {
      continue
    }
    let groups : Array[Array[Evaluation]] = []
    let keys : Array[Array[Value]] = []
    for ctx in contexts {
      let key = partitions.map(e => evaluate(e, ctx))
      let mut found = -1
      for i, previous in keys {
        if previous
          .mapi((j, v) => {
            compare_stored(
              base.store,
              v,
              key[j],
              expression_collation(partitions[j], base),
            ) ==
            0
          })
          .all(v => v) {
          found = i
          break
        }
      }
      if found < 0 {
        keys.push(key)
        groups.push([ctx])
      } else {
        groups[found].push(ctx)
      }
    }
    let identity = @json.to_json(expression).stringify()
    for group in groups {
      let ranked = group.map(ctx => {
        output: [],
        context: ctx,
        keys: orders.map(o => evaluate(o.expression, ctx)),
      })
      let collations = orders.map(o => expression_collation(o.expression, base))
      sort_query_rows(ranked, orders, collations)
      fn peer(a : Int32, b : Int32) -> Bool {
        ranked[a].keys
        .mapi((i, v) => {
          compare_stored(base.store, v, ranked[b].keys[i], collations[i]) == 0
        })
        .all(v => v)
      }
      let mut dense = 0
      let mut rank = 0
      for index, row in ranked {
        if index == 0 || !peer(index, index - 1) {
          dense += 1
          rank = index
        }
        let mut peer_end = index + 1
        while peer_end < ranked.length() && peer(index, peer_end) {
          peer_end += 1
        }
        let here = row.context
        let n = ranked.length()
        let value = if name == "row_number" {
          Value::Integer((index + 1).to_int64())
        } else if name == "rank" {
          Integer((rank + 1).to_int64())
        } else if name == "dense_rank" {
          Integer(dense.to_int64())
        } else if name == "percent_rank" {
          Real(
            if n <= 1 {
              0.0
            } else {
              rank.to_double() / (n - 1).to_double()
            },
          )
        } else if name == "cume_dist" {
          Real(peer_end.to_double() / n.to_double())
        } else if name == "ntile" {
          let buckets = window_offset(args[0], here)
          guard buckets > 0 else {
            fail("argument of ntile must be a positive integer")
          }
          let size = n / buckets
          let extra = n % buckets
          Integer(
            (if index < (size + 1) * extra {
              index / (size + 1) + 1
            } else {
              extra + (index - (size + 1) * extra) / size + 1
            }).to_int64(),
          )
        } else if name == "lag" || name == "lead" {
          let offset = if args.length() >= 2 {
            window_offset(args[1], here)
          } else {
            1
          }
          let target = index + (if name == "lag" { -offset } else { offset })
          if target >= 0 && target < n {
            evaluate(args[0], ranked[target].context)
          } else if args.length() == 3 {
            evaluate(args[2], here)
          } else {
            Null
          }
        } else {
          fn boundary(
            bound : WindowBound,
            finish : Bool,
          ) -> Int32 raise SqlError {
            match bound {
              UnboundedPreceding => 0
              UnboundedFollowing => n
              Current =>
                if frame.kind == "rows" {
                  index + (if finish { 1 } else { 0 })
                } else if finish {
                  peer_end
                } else {
                  rank
                }
              Preceding(e) | Following(e) => {
                let amount = window_offset(e, base)
                let sign = if bound is Preceding(_) { -1 } else { 1 }
                if frame.kind == "rows" {
                  (index + sign * amount + (if finish { 1 } else { 0 }))
                  .max(0)
                  .min(n)
                } else if frame.kind == "groups" {
                  let starts : Array[Int32] = [0]
                  for j in 1..= starts.length() {
                    n
                  } else {
                    starts[target]
                  }
                } else {
                  guard orders.length() == 1 else {
                    fail("RANGE offset requires one ORDER BY expression")
                  }
                  let key = row.keys[0]
                  if !(key is Integer(_) || key is Real(_)) {
                    return if finish { peer_end } else { rank }
                  }
                  let target = arithmetic(
                    "+",
                    key,
                    Integer(
                      (sign *
                      (if orders[0].descending { -1 } else { 1 }) *
                      amount).to_int64(),
                    ),
                  )
                  let mut position = 0
                  while position < n {
                    let cmp = compare_stored(
                        base.store,
                        ranked[position].keys[0],
                        target,
                        collations[0],
                      ) *
                      (if orders[0].descending { -1 } else { 1 })
                    if cmp > 0 || (cmp == 0 && !finish) {
                      break
                    }
                    position += 1
                  }
                  position
                }
              }
            }
          }
          let start = boundary(frame.start, false)
          let end = if orders.is_empty() &&
            frame.kind == "range" &&
            frame.end is Current {
            n
          } else {
            boundary(frame.end, true)
          }
          let members = if end > start {
            ranked[start:end].to_owned()
          } else {
            []
          }
          if name == "first_value" ||
            name == "last_value" ||
            name == "nth_value" {
            let pos = if name == "first_value" {
              0
            } else if name == "last_value" {
              members.length() - 1
            } else {
              let n = window_offset(args[1], here)
              guard n > 0 else { fail("nth_value requires a positive integer") }
              n - 1
            }
            if pos < 0 || pos >= members.length() {
              Null
            } else {
              evaluate(args[0], members[pos].context)
            }
          } else {
            let values = members.map(entry => {
              args.mapi((i, e) => {
                ..binding(
                  "$window" + i.to_string(),
                  if e is Star(_) {
                    Integer(1L)
                  } else {
                    evaluate(e, entry.context)
                  },
                ),
                collation: if e is Star(_) {
                  "binary"
                } else {
                  expression_collation(e, entry.context)
                },
              })
            })
            evaluate_call(
              name,
              args.mapi((i, _) => Column("", "$window" + i.to_string())),
              {
                ..here,
                row: if values.is_empty() {
                  args.mapi((i, _) => binding("$window" + i.to_string(), Null))
                } else {
                  values[0]
                },
                group: Some(values),
              },
            )
          }
        }
        here.window_values[identity] = value
      }
    }
  }
}