///|
priv struct CachedIndex {
  table : String
  cookie : Int32
  fields : Array[IndexField]
  predicate : Expr?
  rows : Array[StoredRow]
}

///|
fn compare_index_rows(
  store : Store,
  fields : Array[IndexField],
  a : StoredRow,
  b : StoredRow,
) -> Int32 {
  for field in fields {
    let order = compare_stored(
      store,
      index_field_value(a, field),
      index_field_value(b, field),
      field.collation,
    )
    if order != 0 {
      return if field.descending { -order } else { order }
    }
  }
  a.id.compare(b.id)
}

///|
/// Locate a full index key, including rowid to distinguish equal column values.
fn index_row_bound(
  store : Store,
  rows : Array[StoredRow],
  fields : Array[IndexField],
  row : StoredRow,
) -> Int32 {
  let mut low = 0
  let mut high = rows.length()
  while low < high {
    let middle = low + (high - low) / 2
    if compare_index_rows(store, fields, rows[middle], row) < 0 {
      low = middle + 1
    } else {
      high = middle
    }
  }
  low
}

///|
/// Changed keys may still fit between the same neighbors, avoiding row shifts.
fn index_slot_accepts(
  store : Store,
  rows : Array[StoredRow],
  fields : Array[IndexField],
  position : Int32,
  row : StoredRow,
) -> Bool {
  if position > 0 &&
    compare_index_rows(store, fields, rows[position - 1], row) >= 0 {
    return false
  }
  if position + 1 < rows.length() &&
    compare_index_rows(store, fields, row, rows[position + 1]) >= 0 {
    return false
  }
  true
}

///|
/// A row delta updates only indexes already built for this table. Immutable row
/// values can be shared, but these mutable arrays never cross store checkpoints.
fn update_table_indexes(
  store : Store,
  table : Table,
  previous : StoredRow?,
  next : StoredRow?,
) -> Unit {
  update_primary_index(store, table, previous, next)
  if store.indexes.length() == 0 {
    return
  }
  for (name, index) in store.indexes.to_array() {
    if index.table != table.name {
      continue
    }
    if index.cookie != store.cookie {
      ignore(store.indexes.remove(name))
      continue
    }
    let fields = index.fields
    let membership = Some(
      (
        previous
        .map(row => cached_index_member(store, table, index.predicate, row))
        .unwrap_or(false),
        next
        .map(row => cached_index_member(store, table, index.predicate, row))
        .unwrap_or(false),
      ),
    ) catch {
      _ => None
    }
    guard membership is Some((old_member, new_member)) else {
      ignore(store.indexes.remove(name))
      continue
    }
    let before = if old_member { previous } else { None }
    let after = if new_member { next } else { None }
    if before is Some(row) {
      let position = index_row_bound(store, index.rows, fields, row)
      if position == index.rows.length() ||
        compare_index_rows(store, fields, index.rows[position], row) != 0 {
        // An unprovable cache can always be reconstructed from the table.
        ignore(store.indexes.remove(name))
        continue
      }
      if after is Some(replacement) {
        if compare_index_rows(store, fields, row, replacement) == 0 ||
          index_slot_accepts(store, index.rows, fields, position, replacement) {
          // Publish every new row, even when its key or ordering is unchanged.
          index.rows[position] = replacement
          continue
        }
      }
      ignore(index.rows.remove(position))
    }
    if after is Some(row) {
      let position = index_row_bound(store, index.rows, fields, row)
      index.rows.insert(position, row)
    } else if index.rows.length() * 4 < index.rows.capacity() {
      // Array removal retains backing slots. Release deleted row references
      // after substantial shrinkage, including the final row, amortizing copies.
      index.rows.shrink_to_fit()
    }
  }
}

///|
fn invalidate_table_indexes(store : Store, table : Table) -> Unit {
  ignore(store.primary_indexes.remove(table.name))
  if store.indexes.length() == 0 {
    return
  }
  for (name, index) in store.indexes.to_array() {
    if index.table == table.name {
      ignore(store.indexes.remove(name))
    }
  }
}

///|
/// Bulk replacement (DDL) invalidates indexes; ordinary DML supplies row deltas.
fn replace_table_rows(
  store : Store,
  table : Table,
  rows : Array[StoredRow],
) -> Unit {
  invalidate_table_indexes(store, table)
  dirty_snapshot(store)
  table.rows = row_pages(rows)
}

///|
fn append_table_row(store : Store, table : Table, row : StoredRow) -> Unit {
  update_table_indexes(store, table, None, Some(row))
  table.rows.push(row)
  dirty_edit(store, AppendRow(table.name, row))
}

///|
fn replace_table_row(
  store : Store,
  table : Table,
  previous : StoredRow,
  next : StoredRow,
) -> Unit {
  let slot = if FEATURE_PRIMARY_INDEX {
    primary_index(store, table).slots.get(previous.id)
  } else {
    None
  }
  let position = slot.unwrap_or_else(() => {
    for (i, row) in table.rows.slot_entries() {
      if row.id == previous.id {
        return i
      }
    }
    -1
  })
  if position < 0 {
    return
  }
  update_table_indexes(store, table, Some(previous), Some(next))
  table.rows.set_slot(position, next)
  dirty_replace(store, table.name, previous, next)
}

///|
fn remove_table_row(store : Store, table : Table, row : StoredRow) -> Unit {
  let position = if FEATURE_PRIMARY_INDEX {
    primary_index(store, table).slots.get(row.id)
  } else {
    table.rows
    .slot_entries()
    .find_first(pair => pair.1.id == row.id)
    .map(pair => pair.0)
  }
  guard position is Some(position) else { return }
  update_table_indexes(store, table, Some(row), None)
  if table.rows.remove_slot(position) {
    // Stable slots survive ordinary deletes; repacking invalidates this root only.
    ignore(store.primary_indexes.remove(table.name))
  }
  dirty_edit(store, DeleteRow(table.name, row.id))
}

///|
fn schema_changed(store : Store) -> Unit {
  store.indexes.clear()
  store.primary_indexes.clear()
  dirty_snapshot(store)
  store.cookie += 1
}

///|
fn index_rows_for_fields(
  store : Store,
  table : Table,
  name : String,
  fields : Array[IndexField],
  predicate : Expr?,
) -> Array[StoredRow] raise SqlError {
  if store.indexes.get(name) is Some(index) &&
    index.cookie == store.cookie &&
    index.fields == fields {
    return index.rows
  }
  let rows = if predicate is None {
    table.rows.copy()
  } else {
    table.rows.filter(row => cached_index_member(store, table, predicate, row))
  }
  rows.sort_by((a, b) => compare_index_rows(store, fields, a, b))
  // Bound retained row references. Additional indexes can always be rebuilt.
  if store.indexes.length() >= 4 {
    store.indexes.clear()
  }
  store.indexes[name] = {
    table: table.name,
    cookie: store.cookie,
    fields,
    predicate,
    rows,
  }
  rows
}

///|
fn cached_index_member(
  store : Store,
  table : Table,
  predicate : Expr?,
  row : StoredRow,
) -> Bool raise SqlError {
  match predicate {
    None => true
    Some(e) =>
      truth(
        evaluate(
          e,
          evaluation(store, [], row_environment(table, row, table.name)),
        ),
      ) ==
      1
  }
}

///|
fn index_prefix_bound(
  store : Store,
  rows : Array[StoredRow],
  fields : Array[IndexField],
  values : Array[Value],
  after_equal : Bool,
) -> Int32 {
  let mut low = 0
  let mut high = rows.length()
  while low < high {
    let middle = low + (high - low) / 2
    let mut order = 0
    for i, value in values {
      let field = fields[i]
      order = compare_stored(
        store,
        index_field_value(rows[middle], field),
        value,
        field.collation,
      )
      if field.descending {
        order = -order
      }
      if order != 0 {
        break
      }
    }
    if order < 0 || (after_equal && order == 0) {
      low = middle + 1
    } else {
      high = middle
    }
  }
  low
}