if_lang 0.1.4

extern fn list_len(list) explain { Returns list length. };
extern fn list_get(list, idx) explain { Returns list[idx]. };
extern fn list_push(list, value) explain { Returns list with value appended. };
extern fn str_split_ws(s) explain { Splits string by whitespace. };
extern fn str_trim_end_char(s, ch) explain { Trims one trailing char if present. };
extern fn str_to_int(s) explain { Parses string to Int. };
extern fn assert_eq(a, b) explain { Fails if a != b. };

// Constants
let tok_len_no_where = 4;
let tok_len_with_where = 8;
let tok_table = 3;
let tok_where_col = 5;
let tok_where_op = 6;
let tok_where_val = 7;
let index_not_found = -1;
let int_zero = 0;
let empty_expr = Int { value: 0 };

// AST / Data Model
data Table = Table { name, columns, rows };
data Db = Db { tables };
data Expr = Column { name } | Int { value } | Binary { op, left, right };
data Query = Query { table, has_where, where_expr };
data Result = Result { columns, rows };

// Catalog + Storage (row store)
fn db_open() = Db { tables: [] };

fn table_name(t) =
  match t {
    Table { name, columns, rows } => name;
    _ => "";
  };

fn table_columns(t) =
  match t {
    Table { name, columns, rows } => columns;
    _ => [];
  };

fn table_rows(t) =
  match t {
    Table { name, columns, rows } => rows;
    _ => [];
  };

fn table_with_rows(t, new_rows) =
  match t {
    Table { name, columns, rows } => Table { name, columns, rows: new_rows };
    _ => t;
  };

fn db_create_table(db, name, columns) =
  match db {
    Db { tables } => Db { tables: list_push(tables, Table { name, columns, rows: [] }) };
    _ => db;
  };

fn db_insert(db, name, row) =
  match db {
    Db { tables } => Db { tables: insert_into_tables(tables, name, row) };
    _ => db;
  };

fn insert_into_tables(tables, name, row) =
  for t in tables {
    if table_name(t) == name {
      table_with_rows(t, list_push(table_rows(t), row))
    } else {
      t
    }
  };

// Query Executor (volcano style over rows)
fn db_query(db, sql) =
  match db {
    Db { tables } => query_tables(0, tables, sql |> parse_sql);
    _ =>
      Result {
        columns: [],
        rows: []
      };
  };

fn query_tables(idx, tables, query) =
  if idx >= list_len(tables) {
    Result {
      columns: [],
      rows: []
    }
  } else {
    if (tables |> list_get(idx) |> table_name) == query_table(query) {
      execute_query(query, tables |> list_get(idx))
    } else {
      query_tables(idx + 1, tables, query)
    }
  };

fn execute_query(query, table) =
  if query_has_where(query) {
    Result {
      columns: table_columns(table),
      rows: filter_rows(table_rows(table), query_where_expr(query), table_columns(table))
    }
  } else {
    Result {
      columns: table_columns(table),
      rows: table_rows(table)
    }
  };

fn filter_rows(rows, expr, columns) =
  for row in rows if eval_pred(expr, columns, row) {
    row
  };

fn eval_pred(expr, columns, row) =
  match expr {
    Binary { op, left, right } =>
      compare_values(
        op,
        eval_expr_value(left, columns, row),
        eval_expr_value(right, columns, row)
      );
    _ => false;
  };

fn eval_expr_value(expr, columns, row) =
  match expr {
    Column { name } => column_value(columns, name, row);
    Int { value } => value;
    _ => int_zero;
  };

fn column_value(columns, name, row) =
  if column_index(columns, name) < 0 {
    int_zero
  } else {
    list_get(row, columns |> column_index(name))
  };
fn column_index(columns, name) = find_col_index(0, columns, name);

fn find_col_index(idx, columns, name) =
  if idx >= list_len(columns) {
    index_not_found
  } else {
    if list_get(columns, idx) == name {
      idx
    } else {
      find_col_index(idx + 1, columns, name)
    }
  };

fn compare_values(op, left, right) =
  match op {
    ">" => left > right;
    ">=" => left >= right;
    "<" => left < right;
    "<=" => left <= right;
    "!=" => left != right;
    "==" => left == right;
    "=" => left == right;
    _ => false;
  };

// Parser (minimal SQL subset)
fn parse_sql(sql) =
  sql
    |> str_trim_end_char(";")
    |> str_split_ws
    |> parse_sql_tokens;

fn parse_sql_tokens(tokens) =
  if list_len(tokens) == tok_len_no_where {
    Query {
      table: list_get(tokens, tok_table),
      has_where: false,
      where_expr: empty_expr
    }
  } else {
    Query {
      table: list_get(tokens, tok_table),
      has_where: true,
      where_expr: parse_where_expr(tokens)
    }
  };

fn parse_where_expr(tokens) =
  Binary {
    op: list_get(tokens, tok_where_op),
    left: Column { name: list_get(tokens, tok_where_col) },
    right: Int { value: tokens |> list_get(tok_where_val) |> str_to_int }
  };

fn query_table(q) =
  match q {
    Query { table, has_where, where_expr } => table;
    _ => "";
  };

fn query_has_where(q) =
  match q {
    Query { table, has_where, where_expr } => has_where;
    _ => false;
  };

fn query_where_expr(q) =
  match q {
    Query { table, has_where, where_expr } => where_expr;
    _ => empty_expr;
  };

// Tests
let db =
  db_open()
    |> db_create_table("t1", ["c1", "c2"])
    |> db_insert("t1", [1, "alpha"])
    |> db_insert("t1", [2, "beta"])
    |> db_insert("t1", [3, "gamma"])
    |> db_insert("t1", [0, "zero"]);
let q1 = db_query(db, "select * from t1 where c1 > 1;");

let expected1 =
  Result {
    columns: ["c1", "c2"],
    rows: [[2, "beta"], [3, "gamma"]]
  };
let ok1 = assert_eq(q1, expected1);
let q2 = db_query(db, "select * from t1;");

let expected2 =
  Result {
    columns: ["c1", "c2"],
    rows: [[1, "alpha"], [2, "beta"], [3, "gamma"], [0, "zero"]]
  };
let ok2 = assert_eq(q2, expected2);

[ok1, ok2]