///|
/// Result columns survive even when a CTE/view produces no rows.
priv struct Relation {
  rows : Array[Environment]
  template : Environment
}

///|
/// Virtual schema rows use the same evaluator as user tables.
fn schema_rows(store : Store) -> Array[Environment] {
  let rows : Array[Environment] = []
  for table in store.tables {
    rows.push([
      binding("type", Text("table")),
      binding("name", Text(table.name)),
      binding("tbl_name", Text(table.name)),
      binding("rootpage", Integer(0L)),
      binding("sql", Text(table.sql)),
      {
        ..binding("rowid", Integer((rows.length() + 1).to_int64())),
        hidden: true,
      },
    ])
  }
  for object in store.objects {
    rows.push([
      binding("type", Text(object.kind)),
      binding("name", Text(object.name)),
      binding("tbl_name", Text(object.table)),
      binding("rootpage", Integer(0L)),
      binding("sql", Text(object.sql)),
      {
        ..binding("rowid", Integer((rows.length() + 1).to_int64())),
        hidden: true,
      },
    ])
  }
  rows
}

///|
fn source_rows(
  store : Store,
  name : String,
  params : Array[Value],
  ctes : Map[String, Relation],
  depth : Int32,
) -> Array[Environment] raise SqlError {
  guard depth <= 16 else { fail("SQL view/CTE recursion limit") }
  if ctes.get(identifier(name)) is Some(relation) {
    return relation.rows
  }
  if identifier(name) == "sqlite_schema" || identifier(name) == "sqlite_master" {
    return schema_rows(store)
  }
  for object in store.objects {
    if identifier(object.name) == identifier(name) && object.kind == "view" {
      guard object.selection is Some(selection) else {
        fail("view has no compiled query")
      }
      return select_rows(store, selection, params, depth + 1)
    }
  }
  let table = get_table(store, name)
  let rows = table.rows.copy()
  if table.without_rowid {
    let keys = primary_key(table)
    rows.sort_by((a, b) => {
      for i in keys {
        let c = compare_stored(
          store,
          a.values[i],
          b.values[i],
          table.columns[i].collation,
        )
        if c != 0 {
          return c
        }
      }
      0
    })
  } else {
    rows.sort_by((a, b) => a.id.compare(b.id))
  }
  let layout = row_environment(
    table,
    { id: 0L, values: Array::make(table.columns.length(), Null), },
    name,
  )
  rows.map(row => row_environment_from(layout, row))
}

///|
fn empty_source(
  store : Store,
  source : Source,
  ctes : Map[String, Relation],
  params : Array[Value],
  depth : Int32,
) -> Environment raise SqlError {
  if ctes.get(identifier(source.name)) is Some(relation) {
    return relation.template.map(b => {
      ..b,
      value: Null,
      qualifier: source.qualifier,
    })
  }
  if identifier(source.name) == "sqlite_schema" ||
    identifier(source.name) == "sqlite_master" {
    return ["type", "name", "tbl_name", "rootpage", "sql", "rowid"].map(n => {
      ..binding(n, Null),
      qualifier: source.qualifier,
      hidden: n == "rowid",
    })
  }
  for object in store.objects {
    if identifier(object.name) == identifier(source.name) &&
      object.kind == "view" {
      guard object.selection is Some(select) else {
        fail("view has no compiled query")
      }
      let template = selection_template(select, {
        ..evaluation(store, params, []),
        depth: depth + 1,
      })
      return template.map(b => {
        ..b,
        value: Null,
        qualifier: source.qualifier,
      })
    }
  }
  let table = get_table(store, source.name)
  row_environment(
    table,
    { id: 0L, values: Array::make(table.columns.length(), Null), },
    source.qualifier,
  )
}

///|
fn sort_query_rows(
  rows : Array[QueryRow],
  orders : Array[Ordering],
  collations : Array[String],
) -> Unit {
  rows.sort_by((a, b) => {
    for i, order in orders {
      let c = compare_stored(
        a.context.store,
        a.keys[i],
        b.keys[i],
        collations[i],
      )
      if c != 0 {
        return if order.descending { -c } else { c }
      }
    }
    a.context.position.compare(b.context.position)
  })
}

///|
fn select_relation_in(
  select : Selection,
  context : Evaluation,
  existence : Bool,
  prepared~ : PreparedSelection? = None,
) -> Relation raise SqlError {
  if select.compound is Some(_) {
    return compound_relation(select, context, existence)
  }
  let store = context.store
  let params = context.params
  let depth = context.depth
  guard depth <= 16 else { fail("SQL query recursion limit") }
  let output_template = match prepared {
    Some(plan) => plan.output
    None => selection_template(select, context)
  }
  if !existence &&
    simple_aggregate(select, context, output_template) is Some(result) {
    return result
  }
  if !existence &&
    simple_relation(
      select,
      context,
      output_template,
      prepared=match prepared {
        Some(plan) => plan.simple
        None => None
      },
    )
    is Some(result) {
    return result
  }
  let ctes : Map[String, Relation] = Map(context.ctes.to_array())
  for (name, selection) in select.ctes {
    ctes[identifier(name)] = execute_cte(select, name, selection, {
      ..context,
      ctes,
    })
  }
  let mut input : Array[Environment] = [[]]
  let mut template : Environment = []
  for source in select.sources {
    if source.right == Some(true) && !FEATURE_OUTER_JOIN {
      fail("feature disabled: rightFullJoin")
    }
    let right = source_rows(store, source.name, params, ctes, depth).map(row => {
      row.map(b => { ..b, qualifier: source.qualifier, })
    })
    let empty = empty_source(store, source, ctes, params, depth)
    prepare_expression(
      source.on,
      { ..context, ctes, row: template + empty, },
      false,
      false,
    )
    let pairs = using_pairs(source, template, empty)
    let track_right = FEATURE_OUTER_JOIN && source.right == Some(true)
    let empty_left = if track_right {
      template.map(b => { ..b, value: Null, })
    } else {
      []
    }
    template = using_row(source, template, empty, pairs)
    let matched_right = if track_right {
      Array::make(right.length(), false)
    } else {
      []
    }
    let next : Array[Environment] = []
    for left in input {
      let mut matched = false
      for ri, row in right {
        let joined = left + row
        if truth(evaluate(source.on, { ..context, ctes, row: joined, })) == 1 &&
          using_matches(left, row, pairs, context) {
          next.push(using_row(source, left, row, pairs))
          matched = true
          if track_right {
            matched_right[ri] = true
          }
        }
        guard next.length() <= 100000 else { fail("SQL result resource limit") }
      }
      if source.left && !matched {
        next.push(using_row(source, left, empty, pairs))
      }
    }
    if FEATURE_OUTER_JOIN && source.right == Some(true) {
      for ri, row in right {
        if !matched_right[ri] {
          next.push(using_row(source, empty_left, row, pairs))
        }
        guard next.length() <= 100000 else { fail("SQL result resource limit") }
      }
    }
    input = next
  }
  let base : Evaluation = { ..context, ctes, row: template, }
  input = input.filter(row => {
    truth(evaluate(select.predicate, { ..base, row, })) == 1
  })
  let groups : Array[Array[Environment]] = []
  if !select.groups.is_empty() {
    let collations = select.groups.map(e => expression_collation(e, base))
    let keys : Array[Array[Value]] = []
    for row in input {
      let values = select.groups.map(e => evaluate(e, { ..base, row, }))
      let mut found = -1
      for i, key in keys {
        if key.length() == values.length() &&
          key
          .mapi((j, v) => {
            compare_stored(store, v, values[j], collations[j]) == 0
          })
          .all(v => v) {
          found = i
          break
        }
      }
      if found < 0 {
        keys.push(values)
        groups.push([row])
      } else {
        groups[found].push(row)
      }
    }
  } else if select.projections.any(p => aggregate(p.expression)) {
    groups.push(input)
  } else {
    for row in input {
      groups.push([row])
    }
  }
  let contexts : Array[Evaluation] = []
  for group in groups {
    let ctx = {
      ..base,
      row: if group.is_empty() {
        template
      } else {
        group[0]
      },
      group: Some(group),
      position: contexts.length(),
      window_values: Map([]),
    }
    if truth(evaluate(select.having, ctx)) == 1 {
      contexts.push(ctx)
    }
  }
  if existence {
    let limit = evaluate(select.limit, base)
    let offset = evaluate(select.offset, base)
    guard limit is Integer(count) && offset is Integer(start) else {
      fail("datatype mismatch: LIMIT/OFFSET")
    }
    let rows = contexts
      .mapi((i, _) => i)
      .filter(i => {
        i.to_int64() >= start.max(0L) &&
        (count < 0L || i.to_int64() - start.max(0L) < count)
      })
      .map(_ => ([] : Environment))
    return { rows, template: output_template, }
  }
  let numbered : Map[Int32, Array[Int32]] = Map([])
  if FEATURE_WINDOWS {
    let window_expressions : Array[Expr] = []
    for p in select.projections {
      collect_windows(p.expression, window_expressions)
    }
    for o in select.orders {
      collect_windows(o.expression, window_expressions)
    }
    compute_windows(window_expressions, contexts, base)
    // row_number has its own ORDER BY, independently of final result ordering.
    for pi, projection in select.projections {
      if projection.expression is RowNumber(orders) {
        let ranked = contexts.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)
        let positions = Array::make(contexts.length(), 0)
        for i, row in ranked {
          positions[row.context.position] = i + 1
        }
        numbered[pi] = positions
      }
    }
  }
  let output : Array[QueryRow] = []
  for ctx in contexts {
    let projected = project(select.projections, ctx)
    if FEATURE_WINDOWS {
      for pi, _ in select.projections {
        if numbered.get(pi) is Some(positions) {
          projected[pi] = {
            ..projected[pi],
            value: Integer(positions[ctx.position].to_int64()),
          }
        }
      }
    }
    if select.distinct &&
      output.any(previous => {
        previous.output.length() == projected.length() &&
        previous.output
        .mapi((i, b) => {
          compare_stored(store, b.value, projected[i].value, b.collation) == 0
        })
        .all(b => b)
      }) {
      continue
    }
    let ordering_ctx = {
      ..ctx,
      row: projected +
      ctx.row.filter(b => {
        b.qualifier != "" ||
        !projected.any(p => identifier(p.name) == identifier(b.name))
      }),
    }
    let keys = select.orders.map(o => {
      match o.expression {
        Literal(Integer(n)) => {
          guard n >= 1L && n <= projected.length().to_int64() else {
            fail("ORDER BY position out of range")
          }
          projected[n.to_int() - 1].value
        }
        _ => evaluate(o.expression, ordering_ctx)
      }
    })
    output.push({ output: projected, context: ctx, keys, })
  }
  let collations = select.orders.map(o => {
    match o.expression {
      Literal(Integer(n)) => output_template[n.to_int() - 1].collation
      Column("", name) => {
        let projection = select.projections.filter(p => {
          identifier(p.label) == identifier(name)
        })
        if projection.length() == 1 {
          expression_collation(projection[0].expression, base)
        } else {
          expression_collation(o.expression, base)
        }
      }
      _ => expression_collation(o.expression, base)
    }
  })
  sort_query_rows(output, select.orders, collations)
  let limit = evaluate(select.limit, base)
  let offset = evaluate(select.offset, base)
  guard limit is Integer(count) && offset is Integer(start) else {
    fail("datatype mismatch: LIMIT/OFFSET")
  }
  let rows = output
    .mapi((i, row) => (i, row))
    .filter(pair => {
      pair.0.to_int64() >= start.max(0L) &&
      (count < 0L || pair.0.to_int64() - start.max(0L) < count)
    })
    .map(pair => pair.1.output)
  { rows, template: output_template, }
}

///|
fn select_rows(
  store : Store,
  select : Selection,
  params : Array[Value],
  depth : Int32,
  prepared~ : PreparedSelection? = None,
) -> Array[Environment] raise SqlError {
  select_relation_in(
    select,
    { ..evaluation(store, params, []), depth, },
    false,
    prepared~,
  ).rows
}

///|
/// Resolve SELECT output and correlated scopes without evaluating any values.
fn selection_template(
  select : Selection,
  context : Evaluation,
) -> Environment raise SqlError {
  guard context.depth <= 16 else { fail("SQL query recursion limit") }
  let ctes : Map[String, Relation] = Map(context.ctes.to_array())
  for (name, selection) in select.ctes {
    ctes[identifier(name)] = prepare_cte(select, name, selection, {
      ..context,
      ctes,
    })
  }
  let mut row : Environment = []
  for source in select.sources {
    if source.right == Some(true) && !FEATURE_OUTER_JOIN {
      fail("feature disabled: rightFullJoin")
    }
    let right = empty_source(
      context.store,
      source,
      ctes,
      context.params,
      context.depth,
    )
    prepare_expression(
      source.on,
      { ..context, ctes, row: row + right, },
      false,
      false,
    )
    row = using_row(source, row, right, using_pairs(source, row, right))
  }
  let base = { ..context, ctes, row, }
  validate_aggregate_output(select)
  prepare_expression(select.predicate, base, false, false)
  for e in select.groups {
    prepare_expression(e, base, false, false)
  }
  prepare_expression(select.having, base, true, false)
  let output = project_template(select.projections, base)
  if select.compound is Some(arms) {
    for (_, arm) in arms {
      guard selection_template(arm, { ..context, ctes, }).length() ==
        output.length() else {
        fail("SELECTs do not have the same number of result columns")
      }
    }
  }
  let ordering = { ..base, row: output + row, }
  for order in select.orders {
    if select.compound is Some(_) {
      ignore(compound_order_index(select, order.expression, output.length()))
    } else if order.expression is Literal(Integer(n)) {
      guard n >= 1L && n <= output.length().to_int64() else {
        fail("ORDER BY position out of range")
      }
    } else {
      prepare_expression(order.expression, ordering, true, true)
    }
  }
  prepare_expression(select.limit, context, false, false)
  prepare_expression(select.offset, context, false, false)
  output
}