ts-11-mini-sql

# In-memory SQL SELECT engine

Implement a file **`solution.ts`** that parses a small `SELECT` statement and executes
it against an in-memory table of rows. This is a parser + interpreter exercise: you must
tokenize the query, build a small AST, validate it, and evaluate it over the data.

## Types to export

```ts
export type Row = Record<string, number | string>;

export class QueryError extends Error {}

// Parse and execute a small SQL SELECT against the given rows. Returns the result rows.
export function query(sql: string, rows: Row[]): Row[];
```

The `rows` argument **is** the table; the table name in the query is accepted but
otherwise ignored (the data comes from `rows` regardless of the name written).

## Grammar

```
SELECT <cols> FROM <table> [WHERE <cond>] [ORDER BY <col> [ASC|DESC]] [LIMIT <n>]
```

The clauses, when present, must appear in exactly this order. The four optional clauses
(`WHERE`, `ORDER BY`, `LIMIT`) are each optional and independent.

### `<cols>`

- `*` selects **all** columns. Each result row preserves that source row's own key
  insertion order (rows are copied; no column is renamed or reordered).
- Otherwise a comma-separated list of column names, e.g. `name, age`. The result rows
  then contain **exactly** those columns, **in the listed order**. A selected column that
  is missing from a given source row is simply omitted from that row's output (it is not
  an error, and no placeholder value is inserted).

### `<table>`

A bare identifier (letters, digits, `_`, not starting with a digit). Any name is accepted.

### `<cond>` (the `WHERE` clause)

One or more comparisons combined with `AND` / `OR`. There are **no parentheses**.
`AND` binds **tighter** than `OR`, so

```
a = 1 AND b = 2 OR c = 3
```

parses as `(a = 1 AND b = 2) OR (c = 3)`.

A single comparison is `col <op> value` where:

- `<op>` is one of `=  !=  <  >  <=  >=`.
- `value` is either an **integer literal** (optionally signed, e.g. `42`, `-3`, `0`) or a
  **single-quoted string** (e.g. `'alice'`). Strings may contain spaces; an unterminated
  string literal is an error.

Comparison semantics, given `cell = row[col]`:

- `=` / `!=` work for both numbers and strings using strict (in)equality. If `cell` is a
  number and `value` is a string (or vice versa), they are considered **not equal** (so
  `=` is `false`, `!=` is `true`).
- `<  >  <=  >=` are ordering comparisons:
  - both number  -> numeric comparison;
  - both string  -> lexicographic comparison (JavaScript `<`/`>` on strings);
  - **type mismatch** (one number, one string) -> the comparison is **`false`**.
- If `col` is **not present** in the row, the comparison is treated as a non-match:
  `=` is `false`, `!=` is `true`, and every ordering comparison is `false`. This does
  **not** throw — only *syntactically* invalid queries throw.

A row is included iff the whole `<cond>` evaluates to true for it. With no `WHERE`, all
rows match.

### `ORDER BY <col> [ASC|DESC]`

Sort the result by a single column. `ASC` (the default) sorts ascending; `DESC`
descending. Numbers sort numerically, strings lexicographically. The sort must be
**stable**: rows that compare equal keep their relative input order. A mismatched-type or
missing sort key compares as equal to the others (it does not throw and does not crash);
ties are broken by stability (original order).

### `LIMIT <n>`

Keep the first `n` result rows after ordering. `n` must be a **non-negative integer**.

### Case sensitivity

Keywords (`SELECT`, `FROM`, `WHERE`, `AND`, `OR`, `ORDER`, `BY`, `ASC`, `DESC`, `LIMIT`)
are **case-insensitive** — `select` and `SELECT` are equivalent. Column names and quoted
string values are **case-sensitive**.

## Evaluation order

`WHERE` filtering -> `ORDER BY` sorting -> `LIMIT` truncation -> column projection.
(Projection last means you may order by a column you did not select.)

## Errors — throw `QueryError`

Throw a `QueryError` (not a plain `Error`) for any **syntactically invalid** query,
including:

- a statement that does not start with `SELECT`, or has no `FROM`;
- an empty column list, or a trailing/embedded comma in the column list;
- an unknown clause / leftover tokens after a valid statement;
- a bad comparison operator, or a comparison missing its column / operator / value;
- an unterminated single-quoted string;
- a `LIMIT` whose argument is missing or is not a non-negative integer;
- an `ORDER BY` without a column.

Referencing a column that is absent from a particular row at **evaluation** time (in
`WHERE` or `ORDER BY`) is **not** an error — see the semantics above.

## Worked example

```ts
const rows: Row[] = [
  { id: 1, name: "alice", age: 30 },
  { id: 2, name: "bob", age: 25 },
  { id: 3, name: "carol", age: 30 },
  { id: 4, name: "dave", age: 17 },
];

query(
  "SELECT name, age FROM users WHERE age >= 18 ORDER BY age DESC LIMIT 2",
  rows,
);
// WHERE drops dave (17). Remaining: alice(30), bob(25), carol(30).
// ORDER BY age DESC (stable): alice(30), carol(30), bob(25).
// LIMIT 2:                    alice(30), carol(30).
// Projection name, age:
// -> [ { name: "alice", age: 30 }, { name: "carol", age: 30 } ]
```

Keep it fully typed: `solution.ts` must pass `tsc --noEmit` in strict mode. Do not use
`any` in the implementation; prefer `unknown` and narrow.

import { test } from "node:test";
import { strict as assert } from "node:assert";
import { query, QueryError, type Row } from "./solution.ts";

function people(): Row[] {
  return [
    { id: 1, name: "alice", age: 30, city: "NYC" },
    { id: 2, name: "bob", age: 25, city: "LA" },
    { id: 3, name: "carol", age: 30, city: "NYC" },
    { id: 4, name: "dave", age: 17, city: "SF" },
  ];
}

test("SELECT * preserves all columns and per-row key order", () => {
  const rows: Row[] = [{ z: 1, a: "x", m: 2 }];
  const out = query("SELECT * FROM t", rows);
  assert.deepEqual(out, [{ z: 1, a: "x", m: 2 }]);
  assert.deepEqual(Object.keys(out[0]!), ["z", "a", "m"]);
  // Result is a copy, not the same object.
  assert.notEqual(out[0], rows[0]);
});

test("explicit column list selects exactly those columns in order", () => {
  const out = query("SELECT name, id FROM users", people());
  assert.deepEqual(out, [
    { name: "alice", id: 1 },
    { name: "bob", id: 2 },
    { name: "carol", id: 3 },
    { name: "dave", id: 4 },
  ]);
  assert.deepEqual(Object.keys(out[0]!), ["name", "id"]);
});

test("selected column missing from a row is omitted, not an error", () => {
  const rows: Row[] = [{ a: 1, b: 2 }, { a: 3 }];
  const out = query("SELECT a, b FROM t", rows);
  assert.deepEqual(out, [{ a: 1, b: 2 }, { a: 3 }]);
});

test("WHERE = and != on numbers", () => {
  assert.deepEqual(
    query("SELECT name FROM u WHERE age = 30", people()),
    [{ name: "alice" }, { name: "carol" }],
  );
  assert.deepEqual(
    query("SELECT name FROM u WHERE age != 30", people()),
    [{ name: "bob" }, { name: "dave" }],
  );
});

test("WHERE = and != on strings (case-sensitive values)", () => {
  assert.deepEqual(
    query("SELECT name FROM u WHERE city = 'NYC'", people()),
    [{ name: "alice" }, { name: "carol" }],
  );
  // Wrong case does not match.
  assert.deepEqual(query("SELECT name FROM u WHERE city = 'nyc'", people()), []);
  assert.deepEqual(
    query("SELECT name FROM u WHERE name != 'alice'", people()).length,
    3,
  );
});

test("numeric ordering comparisons < > <= >=", () => {
  assert.deepEqual(
    query("SELECT name FROM u WHERE age < 30", people()),
    [{ name: "bob" }, { name: "dave" }],
  );
  assert.deepEqual(
    query("SELECT name FROM u WHERE age > 25", people()),
    [{ name: "alice" }, { name: "carol" }],
  );
  assert.deepEqual(
    query("SELECT name FROM u WHERE age <= 25", people()),
    [{ name: "bob" }, { name: "dave" }],
  );
  assert.deepEqual(
    query("SELECT name FROM u WHERE age >= 30", people()),
    [{ name: "alice" }, { name: "carol" }],
  );
});

test("lexicographic string ordering comparisons", () => {
  assert.deepEqual(
    query("SELECT name FROM u WHERE name < 'carol'", people()),
    [{ name: "alice" }, { name: "bob" }],
  );
  assert.deepEqual(
    query("SELECT name FROM u WHERE name >= 'carol'", people()),
    [{ name: "carol" }, { name: "dave" }],
  );
});

test("negative integer literals", () => {
  const rows: Row[] = [{ t: -5 }, { t: 0 }, { t: 3 }];
  assert.deepEqual(query("SELECT t FROM r WHERE t < 0", rows), [{ t: -5 }]);
  assert.deepEqual(query("SELECT t FROM r WHERE t = -5", rows), [{ t: -5 }]);
  assert.deepEqual(query("SELECT t FROM r WHERE t >= -5", rows), [
    { t: -5 },
    { t: 0 },
    { t: 3 },
  ]);
});

test("AND binds tighter than OR", () => {
  const rows: Row[] = [
    { a: 1, b: 2, c: 9 }, // a=1 AND b=2 -> true
    { a: 1, b: 5, c: 3 }, // c=3 -> true via OR
    { a: 9, b: 9, c: 9 }, // none -> false
  ];
  // (a = 1 AND b = 2) OR (c = 3)
  const out = query("SELECT a FROM t WHERE a = 1 AND b = 2 OR c = 3", rows);
  assert.deepEqual(out, [{ a: 1 }, { a: 1 }]);
});

test("OR then AND precedence: a = 1 OR a = 2 AND b = 9", () => {
  const rows: Row[] = [
    { a: 1, b: 0 }, // a=1 -> true
    { a: 2, b: 9 }, // a=2 AND b=9 -> true
    { a: 2, b: 0 }, // a=2 but b!=9 -> false
  ];
  // parses as a = 1 OR (a = 2 AND b = 9)
  const out = query("SELECT a, b FROM t WHERE a = 1 OR a = 2 AND b = 9", rows);
  assert.deepEqual(out, [{ a: 1, b: 0 }, { a: 2, b: 9 }]);
});

test("ORDER BY ascending (default) and DESC", () => {
  const asc = query("SELECT name FROM u ORDER BY age", people());
  assert.deepEqual(asc.map((r) => r["name"]), ["dave", "bob", "alice", "carol"]);
  const desc = query("SELECT name FROM u ORDER BY age DESC", people());
  assert.deepEqual(desc.map((r) => r["name"]), ["alice", "carol", "bob", "dave"]);
});

test("ORDER BY is stable for equal keys", () => {
  // alice and carol both have age 30; original order alice before carol.
  const asc = query("SELECT name FROM u ORDER BY age ASC", people());
  const names = asc.map((r) => r["name"]);
  assert.ok(names.indexOf("alice") < names.indexOf("carol"));
  const desc = query("SELECT name FROM u ORDER BY age DESC", people());
  const dnames = desc.map((r) => r["name"]);
  // Stability preserved under DESC too: equal keys keep input order.
  assert.ok(dnames.indexOf("alice") < dnames.indexOf("carol"));
});

test("ORDER BY a column not in the SELECT list, plus LIMIT", () => {
  const out = query(
    "SELECT name FROM u WHERE age >= 18 ORDER BY age DESC LIMIT 2",
    people(),
  );
  assert.deepEqual(out, [{ name: "alice" }, { name: "carol" }]);
});

test("LIMIT keeps first n and LIMIT 0 yields empty", () => {
  assert.deepEqual(
    query("SELECT id FROM u ORDER BY id LIMIT 2", people()),
    [{ id: 1 }, { id: 2 }],
  );
  assert.deepEqual(query("SELECT id FROM u LIMIT 0", people()), []);
  // LIMIT larger than result is fine.
  assert.deepEqual(query("SELECT id FROM u ORDER BY id LIMIT 99", people()).length, 4);
});

test("type-mismatch comparisons: = is false, != is true, ordering is false", () => {
  const rows: Row[] = [{ v: 5 }, { v: "5" }];
  // number cell vs string literal
  assert.deepEqual(query("SELECT v FROM t WHERE v = '5'", rows), [{ v: "5" }]);
  assert.deepEqual(query("SELECT v FROM t WHERE v != '5'", rows), [{ v: 5 }]);
  // ordering of number cell vs string literal is a type mismatch -> false,
  // but the string cell "5" vs string literal '9' is a valid string comparison.
  assert.deepEqual(query("SELECT v FROM t WHERE v < '9'", rows), [{ v: "5" }]);
  // numeric cell 5 vs string '9' is a mismatch (false); string cell "5" vs number 0 too.
  assert.deepEqual(query("SELECT v FROM t WHERE v > 0", rows), [{ v: 5 }]);
});

test("missing column in WHERE: = false, != true, ordering false (no throw)", () => {
  const rows: Row[] = [{ a: 1 }, { a: 2 }];
  assert.deepEqual(query("SELECT a FROM t WHERE missing = 1", rows), []);
  assert.deepEqual(query("SELECT a FROM t WHERE missing != 1", rows), [{ a: 1 }, { a: 2 }]);
  assert.deepEqual(query("SELECT a FROM t WHERE missing > 0", rows), []);
});

test("ORDER BY with missing / mismatched keys does not throw", () => {
  const rows: Row[] = [{ a: 2 }, { b: 1 }, { a: 1 }];
  // Rows without `a` compare as equal; should not throw.
  const out = query("SELECT * FROM t ORDER BY a", rows);
  assert.equal(out.length, 3);
});

test("keywords are case-insensitive; identifiers/strings are not", () => {
  const out = query(
    "select Name from u WHERE City = 'NYC' order by Age desc limit 1",
    people().map((r) => ({ Name: String(r["name"]), City: String(r["city"]), Age: Number(r["age"]) })),
  );
  assert.deepEqual(out, [{ Name: "alice" }]);
  // Mixed-case keywords work too.
  assert.deepEqual(
    query("SeLeCt id FrOm u Where age = 25", people()),
    [{ id: 2 }],
  );
});

test("no WHERE returns all rows; whitespace is tolerated", () => {
  assert.equal(query("  SELECT   *   FROM   t  ", people()).length, 4);
});

test("throws: missing SELECT", () => {
  assert.throws(() => query("FROM t", []), QueryError);
});

test("throws: missing FROM", () => {
  assert.throws(() => query("SELECT *", []), QueryError);
  assert.throws(() => query("SELECT a, b", []), QueryError);
});

test("throws: empty / malformed column list", () => {
  assert.throws(() => query("SELECT FROM t", []), QueryError);
  assert.throws(() => query("SELECT a, FROM t", []), QueryError);
  assert.throws(() => query("SELECT , a FROM t", []), QueryError);
});

test("throws: bad operator and malformed comparison", () => {
  assert.throws(() => query("SELECT * FROM t WHERE a == 1", []), QueryError);
  assert.throws(() => query("SELECT * FROM t WHERE a 1", []), QueryError);
  assert.throws(() => query("SELECT * FROM t WHERE a =", []), QueryError);
  assert.throws(() => query("SELECT * FROM t WHERE = 1", []), QueryError);
});

test("throws: unterminated string literal", () => {
  assert.throws(() => query("SELECT * FROM t WHERE name = 'alice", []), QueryError);
});

test("throws: bad LIMIT (missing, negative, non-integer, string)", () => {
  assert.throws(() => query("SELECT * FROM t LIMIT", []), QueryError);
  assert.throws(() => query("SELECT * FROM t LIMIT -1", []), QueryError);
  assert.throws(() => query("SELECT * FROM t LIMIT 'x'", []), QueryError);
});

test("throws: unknown clause / leftover tokens", () => {
  assert.throws(() => query("SELECT * FROM t GROUP BY a", []), QueryError);
  assert.throws(() => query("SELECT * FROM t WHERE a = 1 b = 2", []), QueryError);
  assert.throws(() => query("SELECT * FROM t ORDER BY", []), QueryError);
});

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```typescript
// solution.ts

export type Row = Record<string, number | string>;

export class QueryError extends Error {}

type TokenType = 
  | "SELECT" | "FROM" | "WHERE" | "ORDER" | "BY" | "ASC" | "DESC" | "LIMIT"
  | "AND" | "OR"
  | "STAR"
  | "IDENT"
  | "NUMBER"
  | "STRING"
  | "OP"
  | "COMMA"
  | "EOF";

type Token = {
  type: TokenType;
  value: string;
  pos: number;
};

type ASTNode = 
  | { type: "SELECT"; columns: ColumnList; table: string; where?: Condition; orderBy?: OrderBy; limit?: number }
  | { type: "COLUMN_LIST"; columns: string[] }
  | { type: "STAR" }
  | { type: "COMPARISON"; left: string; op: string; right: Value }
  | { type: "AND"; left: Condition; right: Condition }
  | { type: "OR"; left: Condition; right: Condition }
  | { type: "ORDER_BY"; column: string; direction: "ASC" | "DESC" };

type ColumnList = { type: "COLUMN_LIST"; columns: string[] } | { type: "STAR" };
type Condition = ASTNode;
type Value = string | number;

function tokenize(sql: string): Token[] {
  const tokens: Token[] = [];
  let i = 0;
  const n = sql.length;

  const keywords = new Set([
    "SELECT", "FROM", "WHERE", "ORDER", "BY", "ASC", "DESC", "LIMIT", "AND", "OR"
  ]);

  while (i < n) {
    const char = sql[i];

    if (/\s/.test(char)) {
      i++;
      continue;
    }

    if (/[a-zA-Z_]/.test(char)) {
      let start = i;
      while (i < n && /[a-zA-Z0-9_]/.test(sql[i])) i++;
      const word = sql.slice(start, i);
      const type = keywords.has(word) ? word : "IDENT";
      tokens.push({ type, value: word, pos: start });
      continue;
    }

    if (/[0-9]/.test(char)) {
      let start = i;
      let hasSign = false;
      if (char === "-") {
        hasSign = true;
        i++;
      }
      while (i < n && /[0-9]/.test(sql[i])) i++;
      const numStr = sql.slice(start, i);
      if (hasSign && numStr.length === 1) {
        throw new QueryError(`Invalid number at position ${start}`);
      }
      tokens.push({ type: "NUMBER", value: numStr, pos: start });
      continue;
    }

    if (char === "'") {
      let start = i;
      i++;
      while (i < n && sql[i] !== "'") {
        if (sql[i] === "\\") i++; // Basic escape handling not strictly required by spec but good practice
        i++;
      }
      if (i >= n) {
        throw new QueryError(`Unterminated string at position ${start}`);
      }
      const str = sql.slice(start + 1, i);
      tokens.push({ type: "STRING", value: str, pos: start });
      i++;
      continue;
    }

    if (char === ',') {
      tokens.push({ type: "COMMA", value: ",", pos: i });
      i++;
      continue;
    }

    if (char === '*') {
      tokens.push({ type: "STAR", value: "*", pos: i });
      i++;
      continue;
    }

    if (['=', '<', '>', '!'].includes(char)) {
      let op = char;
      i++;
      if (i < n && (sql[i] === '=' || sql[i] === '<' || sql[i] === '>')) {
        op += sql[i];
        i++;
      }
      tokens.push({ type: "OP", value: op, pos: start: i - op.length });
      continue;
    }

    throw new QueryError(`Unexpected character '${char}' at position ${i}`);
  }

  tokens.push({ type: "EOF", value: "", pos: n });
  return tokens;
}

function parse(tokens: Token[]): ASTNode {
  let pos = 0;

  function peek(): Token {
    return tokens[pos];
  }

  function consume(expectedType?: TokenType): Token {
    const tok = peek();
    if (expectedType && tok.type !== expectedType) {
      throw new QueryError(`Expected ${expectedType} at position ${tok.pos}, got ${tok.type}`);
    }
    pos++;
    return tok;
  }

  function parseSelect(): ASTNode {
    consume("SELECT");
    const columns = parseColumnList();
    consume("FROM");
    const table = consume("IDENT").value;
    
    let where: Condition | undefined;
    if (peek().type === "WHERE") {
      consume("WHERE");
      where = parseCondition();
    }

    let orderBy: ASTNode | undefined;
    if (peek().type === "ORDER") {
      consume("ORDER");
      consume("BY");
      orderBy = parseOrderBy();
    }

    let limit: number | undefined;
    if (peek().type === "LIMIT") {
      consume("LIMIT");
      const numTok = consume("NUMBER");
      const n = parseInt(numTok.value, 10);
      if (isNaN(n) || n < 0) {
        throw new QueryError(`LIMIT must be a non-negative integer at position ${numTok.pos}`);
      }
      limit = n;
    }

    if (peek().type !== "EOF") {
      throw new QueryError(`Unexpected token ${peek().type} at position ${peek().pos}`);
    }

    return {
      type: "SELECT",
      columns,
      table,
      where,
      orderBy,
      limit
    };
  }

  function parseColumnList(): ColumnList {
    const first = peek();
    if (first.type === "STAR") {
      consume("STAR");
      return { type: "STAR" };
    }

    const cols: string[] = [];
    while (true) {
      if (first.type === "IDENT") {
        cols.push(consume("IDENT").value);
      } else {
        throw new QueryError(`Expected column name or '*' at position ${first.pos}`);
      }

      if (peek().type === "COMMA") {
        consume("COMMA");
        const next = peek();
        if (next.type === "EOF") {
          throw new QueryError(`Trailing comma in column list at position ${next.pos}`);
        }
      } else {
        break;
      }
    }

    return { type: "COLUMN_LIST", columns: cols };
  }

  function parseCondition(): Condition {
    // AND binds tighter than OR
    let left = parseComparison();
    
    while (peek().type === "AND" || peek().type === "OR") {
      const op = consume().type;
      const right = parseComparison();
      left = { type: op, left, right };
    }
    
    return left;
  }

  function parseComparison(): Condition {
    const left = consume("IDENT").value;
    
    const opTok = peek();
    if (opTok.type !== "OP") {
      throw new QueryError(`Expected operator at position ${opTok.pos}`);
    }
    const op = consume("OP").value;
    
    const rightTok = peek();
    let right: Value;
    if (rightTok.type === "NUMBER") {
      right = parseInt(rightTok.value, 10);
    } else if (rightTok.type === "STRING") {
      right = rightTok.value;
    } else {
      throw new QueryError(`Expected value at position ${rightTok.pos}`);
    }
    
    return { type: "COMPARISON", left, op, right };
  }

  function parseOrderBy(): ASTNode {
    const col = consume("IDENT").value;
    let direction: "ASC" | "DESC" = "ASC";
    if (peek().type === "ASC") {
      consume("ASC");
      direction = "ASC";
    } else if (peek().type === "DESC") {
      consume("DESC");
      direction = "DESC";
    }
    return { type: "ORDER_BY", column: col, direction };
  }

  return parseSelect();
}

function evaluate(ast: ASTNode, rows: Row[]): Row[] {
  if (ast.type !== "SELECT") {
    throw new QueryError("Invalid AST");
  }

  let filtered = rows;
  if (ast.where) {
    filtered = filtered.filter(row => evaluateCondition(ast.where, row));
  }

  let sorted = filtered;
  if (ast.orderBy) {
    sorted = stableSort(sorted, ast.orderBy);
  }

  let limited = sorted;
  if (ast.limit !== undefined) {
    limited = sorted.slice(0, ast.limit);
  }

  return project(limited, ast.columns);
}

function evaluateCondition(node: Condition, row: Row): boolean {
  switch (node.type) {
    case "COMPARISON": {
      const cell = row[node.left];
      const val = node.right;
      const op = node.op;
      
      if (cell === undefined) {
        switch (op) {
          case "=": return false;
          case "!=": return true;
          case "<": case "<=": case ">": case ">=": return false;
          default: throw new QueryError(`Unknown operator ${op}`);
        }
      }

      if (typeof cell !== typeof val) {
        switch (op) {
          case "=": case "<": case "<=": case ">": case ">=": return false;
          case "!=": return true;
          default: throw new QueryError(`Unknown operator ${op}`);
        }
      }

      switch (op) {
        case "=": return cell === val;
        case "!=": return cell !== val;
        case "<": return cell < val;
        case "<=": return cell <= val;
        case ">": return cell > val;
        case ">=": return cell >= val;
        default: throw new QueryError(`Unknown operator ${op}`);
      }
    }
    case "AND": {
      return evaluateCondition(node.left, row) && evaluateCondition(node.right, row);
    }
    case "OR": {
      return evaluateCondition(node.left, row) || evaluateCondition(node.right, row);
    }
    default:
      throw new QueryError(`Invalid condition node type: ${node.type}`);
  }
}

function stableSort(rows: Row[], orderBy: ASTNode): Row[] {
  if (orderBy.type !== "ORDER_BY") {
    throw new QueryError("Expected ORDER_BY node");
  }
  
  const { column, direction } = orderBy;
  const dirMultiplier = direction === "ASC" ? 1 : -1;

  return [...rows].sort((a, b) => {
    const valA = a[column];
    const valB = b[column];

    // Handle missing keys or type mismatches as equal
    if (valA === undefined || valB === undefined || typeof valA !== typeof valB) {
      return 0;
    }

    if (typeof valA === "number" && typeof valB === "number") {
      const diff = valA - valB;
      return diff * dirMultiplier;
    }

    if (typeof valA === "string" && typeof valB === "string") {
      const diff = valA.localeCompare(valB);
      return diff * dirMultiplier;
    }

    return 0;
  });
}

function project(rows: Row[], columns: ColumnList): Row[] {
  if (columns.type === "STAR") {
    return rows.map(row => ({ ...row }));
  }

  const colNames = columns.columns;
  return rows.map(row => {
    const newRow: Row = {};
    for (const col of colNames) {
      if (row[col] !== undefined) {
        newRow[col] = row[col];
      }
    }
    return newRow;
  });
}

export function query(sql: string, rows: Row[]): Row[] {
  try {
    const tokens = tokenize(sql);
    const ast = parse(tokens);
    return evaluate(ast, rows);
  } catch (e) {
    if (e instanceof QueryError) {
      throw e;
    }
    throw new QueryError("Internal parsing or evaluation error");
  }
}
```

[
  {
    "total": 1,
    "answer": "```typescript\n// solution.ts\n\nexport type Row = Record<string, number | string>;\n\nexport class QueryError extends Error {}\n\ntype TokenType = \n  | \"SELECT\" | \"FROM\" | \"WHERE\" | \"ORDER\" | \"BY\" | \"ASC\" | \"DESC\" | \"LIMIT\"\n  | \"AND\" | \"OR\"\n  | \"STAR\"\n  | \"IDENT\"\n  | \"NUMBER\"\n  | \"STRING\"\n  | \"OP\"\n  | \"COMMA\"\n  | \"EOF\";\n\ntype Token = {\n  type: TokenType;\n  value: string;\n  pos: number;\n};\n\ntype ASTNode = \n  | { type: \"SELECT\"; columns: ColumnList; table: string; where?: Condition; orderBy?: OrderBy; limit?: number }\n  | { type: \"COLUMN_LIST\"; columns: string[] }\n  | { type: \"STAR\" }\n  | { type: \"COMPARISON\"; left: string; op: string; right: Value }\n  | { type: \"AND\"; left: Condition; right: Condition }\n  | { type: \"OR\"; left: Condition; right: Condition }\n  | { type: \"ORDER_BY\"; column: string; direction: \"ASC\" | \"DESC\" };\n\ntype ColumnList = { type: \"COLUMN_LIST\"; columns: string[] } | { type: \"STAR\" };\ntype Condition = ASTNode;\ntype Value = string | number;\n\nfunction tokenize(sql: string): Token[] {\n  const tokens: Token[] = [];\n  let i = 0;\n  const n = sql.length;\n\n  const keywords = new Set([\n    \"SELECT\", \"FROM\", \"WHERE\", \"ORDER\", \"BY\", \"ASC\", \"DESC\", \"LIMIT\", \"AND\", \"OR\"\n  ]);\n\n  while (i < n) {\n    const char = sql[i];\n\n    if (/\\s/.test(char)) {\n      i++;\n      continue;\n    }\n\n    if (/[a-zA-Z_]/.test(char)) {\n      let start = i;\n      while (i < n && /[a-zA-Z0-9_]/.test(sql[i])) i++;\n      const word = sql.slice(start, i);\n      const type = keywords.has(word) ? word : \"IDENT\";\n      tokens.push({ type, value: word, pos: start });\n      continue;\n    }\n\n    if (/[0-9]/.test(char)) {\n      let start = i;\n      let hasSign = false;\n      if (char === \"-\") {\n        hasSign = true;\n        i++;\n      }\n      while (i < n && /[0-9]/.test(sql[i])) i++;\n      const numStr = sql.slice(start, i);\n      if (hasSign && numStr.length === 1) {\n        throw new QueryError(`Invalid number at position ${start}`);\n      }\n      tokens.push({ type: \"NUMBER\", value: numStr, pos: start });\n      continue;\n    }\n\n    if (char === \"'\") {\n      let start = i;\n      i++;\n      while (i < n && sql[i] !== \"'\") {\n        if (sql[i] === \"\\\\\") i++; // Basic escape handling not strictly required by spec but good practice\n        i++;\n      }\n      if (i >= n) {\n        throw new QueryError(`Unterminated string at position ${start}`);\n      }\n      const str = sql.slice(start + 1, i);\n      tokens.push({ type: \"STRING\", value: str, pos: start });\n      i++;\n      continue;\n    }\n\n    if (char === ',') {\n      tokens.push({ type: \"COMMA\", value: \",\", pos: i });\n      i++;\n      continue;\n    }\n\n    if (char === '*') {\n      tokens.push({ type: \"STAR\", value: \"*\", pos: i });\n      i++;\n      continue;\n    }\n\n    if (['=', '<', '>', '!'].includes(char)) {\n      let op = char;\n      i++;\n      if (i < n && (sql[i] === '=' || sql[i] === '<' || sql[i] === '>')) {\n        op += sql[i];\n        i++;\n      }\n      tokens.push({ type: \"OP\", value: op, pos: start: i - op.length });\n      continue;\n    }\n\n    throw new QueryError(`Unexpected character '${char}' at position ${i}`);\n  }\n\n  tokens.push({ type: \"EOF\", value: \"\", pos: n });\n  return tokens;\n}\n\nfunction parse(tokens: Token[]): ASTNode {\n  let pos = 0;\n\n  function peek(): Token {\n    return tokens[pos];\n  }\n\n  function consume(expectedType?: TokenType): Token {\n    const tok = peek();\n    if (expectedType && tok.type !== expectedType) {\n      throw new QueryError(`Expected ${expectedType} at position ${tok.pos}, got ${tok.type}`);\n    }\n    pos++;\n    return tok;\n  }\n\n  function parseSelect(): ASTNode {\n    consume(\"SELECT\");\n    const columns = parseColumnList();\n    consume(\"FROM\");\n    const table = consume(\"IDENT\").value;\n    \n    let where: Condition | undefined;\n    if (peek().type === \"WHERE\") {\n      consume(\"WHERE\");\n      where = parseCondition();\n    }\n\n    let orderBy: ASTNode | undefined;\n    if (peek().type === \"ORDER\") {\n      consume(\"ORDER\");\n      consume(\"BY\");\n      orderBy = parseOrderBy();\n    }\n\n    let limit: number | undefined;\n    if (peek().type === \"LIMIT\") {\n      consume(\"LIMIT\");\n      const numTok = consume(\"NUMBER\");\n      const n = parseInt(numTok.value, 10);\n      if (isNaN(n) || n < 0) {\n        throw new QueryError(`LIMIT must be a non-negative integer at position ${numTok.pos}`);\n      }\n      limit = n;\n    }\n\n    if (peek().type !== \"EOF\") {\n      throw new QueryError(`Unexpected token ${peek().type} at position ${peek().pos}`);\n    }\n\n    return {\n      type: \"SELECT\",\n      columns,\n      table,\n      where,\n      orderBy,\n      limit\n    };\n  }\n\n  function parseColumnList(): ColumnList {\n    const first = peek();\n    if (first.type === \"STAR\") {\n      consume(\"STAR\");\n      return { type: \"STAR\" };\n    }\n\n    const cols: string[] = [];\n    while (true) {\n      if (first.type === \"IDENT\") {\n        cols.push(consume(\"IDENT\").value);\n      } else {\n        throw new QueryError(`Expected column name or '*' at position ${first.pos}`);\n      }\n\n      if (peek().type === \"COMMA\") {\n        consume(\"COMMA\");\n        const next = peek();\n        if (next.type === \"EOF\") {\n          throw new QueryError(`Trailing comma in column list at position ${next.pos}`);\n        }\n      } else {\n        break;\n      }\n    }\n\n    return { type: \"COLUMN_LIST\", columns: cols };\n  }\n\n  function parseCondition(): Condition {\n    // AND binds tighter than OR\n    let left = parseComparison();\n    \n    while (peek().type === \"AND\" || peek().type === \"OR\") {\n      const op = consume().type;\n      const right = parseComparison();\n      left = { type: op, left, right };\n    }\n    \n    return left;\n  }\n\n  function parseComparison(): Condition {\n    const left = consume(\"IDENT\").value;\n    \n    const opTok = peek();\n    if (opTok.type !== \"OP\") {\n      throw new QueryError(`Expected operator at position ${opTok.pos}`);\n    }\n    const op = consume(\"OP\").value;\n    \n    const rightTok = peek();\n    let right: Value;\n    if (rightTok.type === \"NUMBER\") {\n      right = parseInt(rightTok.value, 10);\n    } else if (rightTok.type === \"STRING\") {\n      right = rightTok.value;\n    } else {\n      throw new QueryError(`Expected value at position ${rightTok.pos}`);\n    }\n    \n    return { type: \"COMPARISON\", left, op, right };\n  }\n\n  function parseOrderBy(): ASTNode {\n    const col = consume(\"IDENT\").value;\n    let direction: \"ASC\" | \"DESC\" = \"ASC\";\n    if (peek().type === \"ASC\") {\n      consume(\"ASC\");\n      direction = \"ASC\";\n    } else if (peek().type === \"DESC\") {\n      consume(\"DESC\");\n      direction = \"DESC\";\n    }\n    return { type: \"ORDER_BY\", column: col, direction };\n  }\n\n  return parseSelect();\n}\n\nfunction evaluate(ast: ASTNode, rows: Row[]): Row[] {\n  if (ast.type !== \"SELECT\") {\n    throw new QueryError(\"Invalid AST\");\n  }\n\n  let filtered = rows;\n  if (ast.where) {\n    filtered = filtered.filter(row => evaluateCondition(ast.where, row));\n  }\n\n  let sorted = filtered;\n  if (ast.orderBy) {\n    sorted = stableSort(sorted, ast.orderBy);\n  }\n\n  let limited = sorted;\n  if (ast.limit !== undefined) {\n    limited = sorted.slice(0, ast.limit);\n  }\n\n  return project(limited, ast.columns);\n}\n\nfunction evaluateCondition(node: Condition, row: Row): boolean {\n  switch (node.type) {\n    case \"COMPARISON\": {\n      const cell = row[node.left];\n      const val = node.right;\n      const op = node.op;\n      \n      if (cell === undefined) {\n        switch (op) {\n          case \"=\": return false;\n          case \"!=\": return true;\n          case \"<\": case \"<=\": case \">\": case \">=\": return false;\n          default: throw new QueryError(`Unknown operator ${op}`);\n        }\n      }\n\n      if (typeof cell !== typeof val) {\n        switch (op) {\n          case \"=\": case \"<\": case \"<=\": case \">\": case \">=\": return false;\n          case \"!=\": return true;\n          default: throw new QueryError(`Unknown operator ${op}`);\n        }\n      }\n\n      switch (op) {\n        case \"=\": return cell === val;\n        case \"!=\": return cell !== val;\n        case \"<\": return cell < val;\n        case \"<=\": return cell <= val;\n        case \">\": return cell > val;\n        case \">=\": return cell >= val;\n        default: throw new QueryError(`Unknown operator ${op}`);\n      }\n    }\n    case \"AND\": {\n      return evaluateCondition(node.left, row) && evaluateCondition(node.right, row);\n    }\n    case \"OR\": {\n      return evaluateCondition(node.left, row) || evaluateCondition(node.right, row);\n    }\n    default:\n      throw new QueryError(`Invalid condition node type: ${node.type}`);\n  }\n}\n\nfunction stableSort(rows: Row[], orderBy: ASTNode): Row[] {\n  if (orderBy.type !== \"ORDER_BY\") {\n    throw new QueryError(\"Expected ORDER_BY node\");\n  }\n  \n  const { column, direction } = orderBy;\n  const dirMultiplier = direction === \"ASC\" ? 1 : -1;\n\n  return [...rows].sort((a, b) => {\n    const valA = a[column];\n    const valB = b[column];\n\n    // Handle missing keys or type mismatches as equal\n    if (valA === undefined || valB === undefined || typeof valA !== typeof valB) {\n      return 0;\n    }\n\n    if (typeof valA === \"number\" && typeof valB === \"number\") {\n      const diff = valA - valB;\n      return diff * dirMultiplier;\n    }\n\n    if (typeof valA === \"string\" && typeof valB === \"string\") {\n      const diff = valA.localeCompare(valB);\n      return diff * dirMultiplier;\n    }\n\n    return 0;\n  });\n}\n\nfunction project(rows: Row[], columns: ColumnList): Row[] {\n  if (columns.type === \"STAR\") {\n    return rows.map(row => ({ ...row }));\n  }\n\n  const colNames = columns.columns;\n  return rows.map(row => {\n    const newRow: Row = {};\n    for (const col of colNames) {\n      if (row[col] !== undefined) {\n        newRow[col] = row[col];\n      }\n    }\n    return newRow;\n  });\n}\n\nexport function query(sql: string, rows: Row[]): Row[] {\n  try {\n    const tokens = tokenize(sql);\n    const ast = parse(tokens);\n    return evaluate(ast, rows);\n  } catch (e) {\n    if (e instanceof QueryError) {\n      throw e;\n    }\n    throw new QueryError(\"Internal parsing or evaluation error\");\n  }\n}\n```",
    "passed": 0,
    "test_error": "TAP version 13\n# node:internal/modules/run_main:107\n#     triggerUncaughtException(\n#     ^\n# Error: Transform failed with 1 error:\n# /tmp/llmlab-ts-11-mini-sql-vkejgwrm/solution.ts:114:53: ERROR: Expected \"}\" but found \":\"\n#     at failureErrorWithLog (/home/psc/opt/node/lib/node_modules/tsx/node_modules/esbuild/lib/main.js:1748:15)\n#     at /home/psc/opt/node/lib/node_modules/tsx/node_modules/esbuild/lib/main.js:1017:50\n#     at responseCallbacks.<computed> (/home/psc/opt/node/lib/node_modules/tsx/node_modules/esbuild/lib/main.js:884:9)\n#     at handleIncomingPacket (/home/psc/opt/node/lib/node_modules/tsx/node_modules/esbuild/lib/main.js:939:12)\n#     at Socket.readFromStdout (/home/psc/opt/node/lib/node_modules/tsx/node_modules/esbuild/lib/main.js:862:7)\n#     at Socket.emit (node:events:509:28)\n#     at addChunk (node:internal/streams/readable:563:12)\n#     at readableAddChunkPushByteMode (node:internal/streams/readable:514:3)\n#     at Readable.push (node:internal/streams/readable:394:5)\n#     at Pipe.onStreamRead (node:internal/stream_base_commons:189:23) {\n#   name: 'TransformError'\n# }\n# Node.js v24.16.0\n# Subtest: solution.test.ts\nnot ok 1 - solution.test.ts\n  ---\n  duration_ms: 75.571858\n  type: 'test'\n  location: '/tmp/llmlab-ts-11-mini-sql-vkejgwrm/solution.test.ts:1:1'\n  failureType: 'testCodeFailure'\n  exitCode: 1\n  signal: ~\n  error: 'test failed'\n  code: 'ERR_TEST_FAILURE'\n  ...\n1..1\n# tests 1\n# suites 0\n# pass 0\n# fail 1\n# cancelled 0\n# skipped 0\n# todo 0\n# duration_ms 79.307752"
  },
  {
    "total": 26,
    "answer": "```typescript\n// solution.ts\n\nexport type Row = Record<string, number | string>;\n\nexport class QueryError extends Error {}\n\ntype TokenType = \n  | \"SELECT\" | \"FROM\" | \"WHERE\" | \"ORDER\" | \"BY\" | \"ASC\" | \"DESC\" | \"LIMIT\"\n  | \"AND\" | \"OR\"\n  | \"STAR\"\n  | \"IDENT\"\n  | \"NUMBER\"\n  | \"STRING\"\n  | \"OP\"\n  | \"COMMA\"\n  | \"EOF\";\n\ntype Token = {\n  type: TokenType;\n  value: string;\n  pos: number;\n};\n\ntype ASTNode = \n  | { type: \"SELECT\"; columns: ColumnList; table: string; where?: Condition; orderBy?: OrderBy; limit?: number }\n  | { type: \"COLUMN_LIST\"; columns: string[] }\n  | { type: \"STAR\" }\n  | { type: \"COMPARISON\"; left: string; op: string; right: Value }\n  | { type: \"AND\"; left: Condition; right: Condition }\n  | { type: \"OR\"; left: Condition; right: Condition }\n  | { type: \"ORDER_BY\"; column: string; direction: \"ASC\" | \"DESC\" };\n\ntype ColumnList = { type: \"COLUMN_LIST\"; columns: string[] } | { type: \"STAR\" };\ntype Condition = ASTNode;\ntype Value = string | number;\n\nfunction tokenize(sql: string): Token[] {\n  const tokens: Token[] = [];\n  let i = 0;\n  const n = sql.length;\n\n  const keywords = new Set([\n    \"SELECT\", \"FROM\", \"WHERE\", \"ORDER\", \"BY\", \"ASC\", \"DESC\", \"LIMIT\", \"AND\", \"OR\"\n  ]);\n\n  while (i < n) {\n    const char = sql[i];\n\n    if (/\\s/.test(char)) {\n      i++;\n      continue;\n    }\n\n    if (/[a-zA-Z_]/.test(char)) {\n      let start = i;\n      while (i < n && /[a-zA-Z0-9_]/.test(sql[i])) i++;\n      const word = sql.slice(start, i);\n      const type = keywords.has(word) ? word : \"IDENT\";\n      tokens.push({ type, value: word, pos: start });\n      continue;\n    }\n\n    if (/[0-9]/.test(char)) {\n      let start = i;\n      let hasSign = false;\n      if (char === \"-\") {\n        hasSign = true;\n        i++;\n      }\n      while (i < n && /[0-9]/.test(sql[i])) i++;\n      const numStr = sql.slice(start, i);\n      if (hasSign && numStr.length === 1) {\n        throw new QueryError(`Invalid number at position ${start}`);\n      }\n      tokens.push({ type: \"NUMBER\", value: numStr, pos: start });\n      continue;\n    }\n\n    if (char === \"'\") {\n      let start = i;\n      i++;\n      while (i < n && sql[i] !== \"'\") {\n        if (sql[i] === \"\\\\\") i++; // Basic escape handling not strictly required by spec but good practice\n        i++;\n      }\n      if (i >= n) {\n        throw new QueryError(`Unterminated string at position ${start}`);\n      }\n      const str = sql.slice(start + 1, i);\n      tokens.push({ type: \"STRING\", value: str, pos: start });\n      i++;\n      continue;\n    }\n\n    if (char === ',') {\n      tokens.push({ type: \"COMMA\", value: \",\", pos: i });\n      i++;\n      continue;\n    }\n\n    if (char === '*') {\n      tokens.push({ type: \"STAR\", value: \"*\", pos: i });\n      i++;\n      continue;\n    }\n\n    if (['=', '<', '>', '!'].includes(char)) {\n      let op = char;\n      i++;\n      if (i < n && (sql[i] === '=' || sql[i] === '<' || sql[i] === '>')) {\n        op += sql[i];\n        i++;\n      }\n      tokens.push({ type: \"OP\", value: op, pos: i - op.length });\n      continue;\n    }\n\n    throw new QueryError(`Unexpected character '${char}' at position ${i}`);\n  }\n\n  tokens.push({ type: \"EOF\", value: \"\", pos: n });\n  return tokens;\n}\n\nfunction parse(tokens: Token[]): ASTNode {\n  let pos = 0;\n\n  function peek(): Token {\n    return tokens[pos];\n  }\n\n  function consume(expectedType?: TokenType): Token {\n    const tok = peek();\n    if (expectedType && tok.type !== expectedType) {\n      throw new QueryError(`Expected ${expectedType} at position ${tok.pos}, got ${tok.type}`);\n    }\n    pos++;\n    return tok;\n  }\n\n  function parseSelect(): ASTNode {\n    consume(\"SELECT\");\n    const columns = parseColumnList();\n    consume(\"FROM\");\n    const table = consume(\"IDENT\").value;\n    \n    let where: Condition | undefined;\n    if (peek().type === \"WHERE\") {\n      consume(\"WHERE\");\n      where = parseCondition();\n    }\n\n    let orderBy: ASTNode | undefined;\n    if (peek().type === \"ORDER\") {\n      consume(\"ORDER\");\n      consume(\"BY\");\n      orderBy = parseOrderBy();\n    }\n\n    let limit: number | undefined;\n    if (peek().type === \"LIMIT\") {\n      consume(\"LIMIT\");\n      const numTok = consume(\"NUMBER\");\n      const n = parseInt(numTok.value, 10);\n      if (isNaN(n) || n < 0) {\n        throw new QueryError(`LIMIT must be a non-negative integer at position ${numTok.pos}`);\n      }\n      limit = n;\n    }\n\n    if (peek().type !== \"EOF\") {\n      throw new QueryError(`Unexpected token ${peek().type} at position ${peek().pos}`);\n    }\n\n    return {\n      type: \"SELECT\",\n      columns,\n      table,\n      where,\n      orderBy,\n      limit\n    };\n  }\n\n  function parseColumnList(): ColumnList {\n    const first = peek();\n    if (first.type === \"STAR\") {\n      consume(\"STAR\");\n      return { type: \"STAR\" };\n    }\n\n    const cols: string[] = [];\n    while (true) {\n      if (first.type === \"IDENT\") {\n        cols.push(consume(\"IDENT\").value);\n      } else {\n        throw new QueryError(`Expected column name or '*' at position ${first.pos}`);\n      }\n\n      if (peek().type === \"COMMA\") {\n        consume(\"COMMA\");\n        const next = peek();\n        if (next.type === \"EOF\") {\n          throw new QueryError(`Trailing comma in column list at position ${next.pos}`);\n        }\n      } else {\n        break;\n      }\n    }\n\n    return { type: \"COLUMN_LIST\", columns: cols };\n  }\n\n  function parseCondition(): Condition {\n    // AND binds tighter than OR\n    let left = parseComparison();\n    \n    while (peek().type === \"AND\" || peek().type === \"OR\") {\n      const op = consume().type;\n      const right = parseComparison();\n      left = { type: op, left, right };\n    }\n    \n    return left;\n  }\n\n  function parseComparison(): Condition {\n    const left = consume(\"IDENT\").value;\n    \n    const opTok = peek();\n    if (opTok.type !== \"OP\") {\n      throw new QueryError(`Expected operator at position ${opTok.pos}`);\n    }\n    const op = consume(\"OP\").value;\n    \n    const rightTok = peek();\n    let right: Value;\n    if (rightTok.type === \"NUMBER\") {\n      right = parseInt(rightTok.value, 10);\n    } else if (rightTok.type === \"STRING\") {\n      right = rightTok.value;\n    } else {\n      throw new QueryError(`Expected value at position ${rightTok.pos}`);\n    }\n    \n    return { type: \"COMPARISON\", left, op, right };\n  }\n\n  function parseOrderBy(): ASTNode {\n    const col = consume(\"IDENT\").value;\n    let direction: \"ASC\" | \"DESC\" = \"ASC\";\n    if (peek().type === \"ASC\") {\n      consume(\"ASC\");\n      direction = \"ASC\";\n    } else if (peek().type === \"DESC\") {\n      consume(\"DESC\");\n      direction = \"DESC\";\n    }\n    return { type: \"ORDER_BY\", column: col, direction };\n  }\n\n  return parseSelect();\n}\n\nfunction evaluate(ast: ASTNode, rows: Row[]): Row[] {\n  if (ast.type !== \"SELECT\") {\n    throw new QueryError(\"Invalid AST\");\n  }\n\n  let filtered = rows;\n  if (ast.where) {\n    filtered = filtered.filter(row => evaluateCondition(ast.where, row));\n  }\n\n  let sorted = filtered;\n  if (ast.orderBy) {\n    sorted = stableSort(sorted, ast.orderBy);\n  }\n\n  let limited = sorted;\n  if (ast.limit !== undefined) {\n    limited = sorted.slice(0, ast.limit);\n  }\n\n  return project(limited, ast.columns);\n}\n\nfunction evaluateCondition(node: Condition, row: Row): boolean {\n  switch (node.type) {\n    case \"COMPARISON\": {\n      const cell = row[node.left];\n      const val = node.right;\n      const op = node.op;\n      \n      if (cell === undefined) {\n        switch (op) {\n          case \"=\": return false;\n          case \"!=\": return true;\n          case \"<\": case \"<=\": case \">\": case \">=\": return false;\n          default: throw new QueryError(`Unknown operator ${op}`);\n        }\n      }\n\n      if (typeof cell !== typeof val) {\n        switch (op) {\n          case \"=\": case \"<\": case \"<=\": case \">\": case \">=\": return false;\n          case \"!=\": return true;\n          default: throw new QueryError(`Unknown operator ${op}`);\n        }\n      }\n\n      switch (op) {\n        case \"=\": return cell === val;\n        case \"!=\": return cell !== val;\n        case \"<\": return cell < val;\n        case \"<=\": return cell <= val;\n        case \">\": return cell > val;\n        case \">=\": return cell >= val;\n        default: throw new QueryError(`Unknown operator ${op}`);\n      }\n    }\n    case \"AND\": {\n      return evaluateCondition(node.left, row) && evaluateCondition(node.right, row);\n    }\n    case \"OR\": {\n      return evaluateCondition(node.left, row) || evaluateCondition(node.right, row);\n    }\n    default:\n      throw new QueryError(`Invalid condition node type: ${node.type}`);\n  }\n}\n\nfunction stableSort(rows: Row[], orderBy: ASTNode): Row[] {\n  if (orderBy.type !== \"ORDER_BY\") {\n    throw new QueryError(\"Expected ORDER_BY node\");\n  }\n  \n  const { column, direction } = orderBy;\n  const dirMultiplier = direction === \"ASC\" ? 1 : -1;\n\n  return [...rows].sort((a, b) => {\n    const valA = a[column];\n    const valB = b[column];\n\n    // Handle missing keys or type mismatches as equal\n    if (valA === undefined || valB === undefined || typeof valA !== typeof valB) {\n      return 0;\n    }\n\n    if (typeof valA === \"number\" && typeof valB === \"number\") {\n      const diff = valA - valB;\n      return diff * dirMultiplier;\n    }\n\n    if (typeof valA === \"string\" && typeof valB === \"string\") {\n      const diff = valA.localeCompare(valB);\n      return diff * dirMultiplier;\n    }\n\n    return 0;\n  });\n}\n\nfunction project(rows: Row[], columns: ColumnList): Row[] {\n  if (columns.type === \"STAR\") {\n    return rows.map(row => ({ ...row }));\n  }\n\n  const colNames = columns.columns;\n  return rows.map(row => {\n    const newRow: Row = {};\n    for (const col of colNames) {\n      if (row[col] !== undefined) {\n        newRow[col] = row[col];\n      }\n    }\n    return newRow;\n  });\n}\n\nexport function query(sql: string, rows: Row[]): Row[] {\n  try {\n    const tokens = tokenize(sql);\n    const ast = parse(tokens);\n    return evaluate(ast, rows);\n  } catch (e) {\n    if (e instanceof QueryError) {\n      throw e;\n    }\n    throw new QueryError(\"Internal parsing or evaluation error\");\n  }\n}\n```",
    "passed": 15,
    "test_error": "BY with missing / mismatched keys does not throw\nok 17 - ORDER BY with missing / mismatched keys does not throw\n  ---\n  duration_ms: 0.053981\n  type: 'test'\n  ...\n# Subtest: keywords are case-insensitive; identifiers/strings are not\nnot ok 18 - keywords are case-insensitive; identifiers/strings are not\n  ---\n  duration_ms: 0.06266\n  type: 'test'\n  location: '/tmp/llmlab-ts-11-mini-sql-msm_r1lt/solution.test.ts:1:5264'\n  failureType: 'testCodeFailure'\n  error: 'Expected SELECT at position 0, got IDENT'\n  code: 'ERR_TEST_FAILURE'\n  stack: |-\n    consume (/tmp/llmlab-ts-11-mini-sql-msm_r1lt/solution.ts:135:13)\n    parseSelect (/tmp/llmlab-ts-11-mini-sql-msm_r1lt/solution.ts:142:5)\n    parse (/tmp/llmlab-ts-11-mini-sql-msm_r1lt/solution.ts:262:10)\n    query (/tmp/llmlab-ts-11-mini-sql-msm_r1lt/solution.ts:384:17)\n    TestContext.<anonymous> (/tmp/llmlab-ts-11-mini-sql-msm_r1lt/solution.test.ts:190:15)\n    Test.runInAsyncScope (node:async_hooks:227:14)\n    Test.run (node:internal/test_runner/test:1306:25)\n    Test.processPendingSubtests (node:internal/test_runner/test:897:18)\n    Test.postRun (node:internal/test_runner/test:1447:19)\n    Test.run (node:internal/test_runner/test:1372:12)\n  ...\n# Subtest: no WHERE returns all rows; whitespace is tolerated\nok 19 - no WHERE returns all rows; whitespace is tolerated\n  ---\n  duration_ms: 0.041331\n  type: 'test'\n  ...\n# Subtest: throws: missing SELECT\nok 20 - throws: missing SELECT\n  ---\n  duration_ms: 0.522295\n  type: 'test'\n  ...\n# Subtest: throws: missing FROM\nok 21 - throws: missing FROM\n  ---\n  duration_ms: 0.105251\n  type: 'test'\n  ...\n# Subtest: throws: empty / malformed column list\nok 22 - throws: empty / malformed column list\n  ---\n  duration_ms: 0.061441\n  type: 'test'\n  ...\n# Subtest: throws: bad operator and malformed comparison\nok 23 - throws: bad operator and malformed comparison\n  ---\n  duration_ms: 0.07925\n  type: 'test'\n  ...\n# Subtest: throws: unterminated string literal\nok 24 - throws: unterminated string literal\n  ---\n  duration_ms: 0.038131\n  type: 'test'\n  ...\n# Subtest: throws: bad LIMIT (missing, negative, non-integer, string)\nok 25 - throws: bad LIMIT (missing, negative, non-integer, string)\n  ---\n  duration_ms: 0.05206\n  type: 'test'\n  ...\n# Subtest: throws: unknown clause / leftover tokens\nok 26 - throws: unknown clause / leftover tokens\n  ---\n  duration_ms: 0.050601\n  type: 'test'\n  ...\n1..26\n# tests 26\n# suites 0\n# pass 15\n# fail 11\n# cancelled 0\n# skipped 0\n# todo 0\n# duration_ms 88.614902"
  },
  {
    "total": 26,
    "answer": "```typescript\n// solution.ts\n\nexport type Row = Record<string, number | string>;\n\nexport class QueryError extends Error {}\n\ntype TokenType = \n  | \"SELECT\" | \"FROM\" | \"WHERE\" | \"ORDER\" | \"BY\" | \"ASC\" | \"DESC\" | \"LIMIT\"\n  | \"AND\" | \"OR\"\n  | \"STAR\"\n  | \"IDENT\"\n  | \"NUMBER\"\n  | \"STRING\"\n  | \"OP\"\n  | \"COMMA\"\n  | \"EOF\";\n\ntype Token = {\n  type: TokenType;\n  value: string;\n  pos: number;\n};\n\ntype ASTNode = \n  | { type: \"SELECT\"; columns: ColumnList; table: string; where?: Condition; orderBy?: OrderBy; limit?: number }\n  | { type: \"COLUMN_LIST\"; columns: string[] }\n  | { type: \"STAR\" }\n  | { type: \"COMPARISON\"; left: string; op: string; right: Value }\n  | { type: \"AND\"; left: Condition; right: Condition }\n  | { type: \"OR\"; left: Condition; right: Condition }\n  | { type: \"ORDER_BY\"; column: string; direction: \"ASC\" | \"DESC\" };\n\ntype ColumnList = { type: \"COLUMN_LIST\"; columns: string[] } | { type: \"STAR\" };\ntype Condition = ASTNode;\ntype Value = string | number;\n\nfunction tokenize(sql: string): Token[] {\n  const tokens: Token[] = [];\n  let i = 0;\n  const n = sql.length;\n\n  const keywords = new Set([\n    \"SELECT\", \"FROM\", \"WHERE\", \"ORDER\", \"BY\", \"ASC\", \"DESC\", \"LIMIT\", \"AND\", \"OR\"\n  ]);\n\n  while (i < n) {\n    const char = sql[i];\n\n    if (/\\s/.test(char)) {\n      i++;\n      continue;\n    }\n\n    if (/[a-zA-Z_]/.test(char)) {\n      let start = i;\n      while (i < n && /[a-zA-Z0-9_]/.test(sql[i])) i++;\n      const word = sql.slice(start, i);\n      const type = keywords.has(word) ? word : \"IDENT\";\n      tokens.push({ type, value: word, pos: start });\n      continue;\n    }\n\n    if (/[0-9]/.test(char)) {\n      let start = i;\n      let hasSign = false;\n      if (char === \"-\") {\n        hasSign = true;\n        i++;\n      }\n      while (i < n && /[0-9]/.test(sql[i])) i++;\n      const numStr = sql.slice(start, i);\n      if (hasSign && numStr.length === 1) {\n        throw new QueryError(`Invalid number at position ${start}`);\n      }\n      tokens.push({ type: \"NUMBER\", value: numStr, pos: start });\n      continue;\n    }\n\n    if (char === \"'\") {\n      let start = i;\n      i++;\n      while (i < n && sql[i] !== \"'\") {\n        if (sql[i] === \"\\\\\") i++; // Basic escape handling not strictly required by spec but good practice\n        i++;\n      }\n      if (i >= n) {\n        throw new QueryError(`Unterminated string at position ${start}`);\n      }\n      const str = sql.slice(start + 1, i);\n      tokens.push({ type: \"STRING\", value: str, pos: start });\n      i++;\n      continue;\n    }\n\n    if (char === ',') {\n      tokens.push({ type: \"COMMA\", value: \",\", pos: i });\n      i++;\n      continue;\n    }\n\n    if (char === '*') {\n      tokens.push({ type: \"STAR\", value: \"*\", pos: i });\n      i++;\n      continue;\n    }\n\n    if (['=', '<', '>', '!'].includes(char)) {\n      let op = char;\n      i++;\n      if (i < n && (sql[i] === '=' || sql[i] === '<' || sql[i] === '>')) {\n        op += sql[i];\n        i++;\n      }\n      tokens.push({ type: \"OP\", value: op, pos: i - op.length });\n      continue;\n    }\n\n    throw new QueryError(`Unexpected character '${char}' at position ${i}`);\n  }\n\n  tokens.push({ type: \"EOF\", value: \"\", pos: n });\n  return tokens;\n}\n\nfunction parse(tokens: Token[]): ASTNode {\n  let pos = 0;\n\n  function peek(): Token {\n    return tokens[pos];\n  }\n\n  function consume(expectedType?: TokenType): Token {\n    const tok = peek();\n    if (expectedType && tok.type !== expectedType) {\n      throw new QueryError(`Expected ${expectedType} at position ${tok.pos}, got ${tok.type}`);\n    }\n    pos++;\n    return tok;\n  }\n\n  function parseSelect(): ASTNode {\n    consume(\"SELECT\");\n    const columns = parseColumnList();\n    consume(\"FROM\");\n    const table = consume(\"IDENT\").value;\n    \n    let where: Condition | undefined;\n    if (peek().type === \"WHERE\") {\n      consume(\"WHERE\");\n      where = parseCondition();\n    }\n\n    let orderBy: ASTNode | undefined;\n    if (peek().type === \"ORDER\") {\n      consume(\"ORDER\");\n      consume(\"BY\");\n      orderBy = parseOrderBy();\n    }\n\n    let limit: number | undefined;\n    if (peek().type === \"LIMIT\") {\n      consume(\"LIMIT\");\n      const numTok = consume(\"NUMBER\");\n      const n = parseInt(numTok.value, 10);\n      if (isNaN(n) || n < 0) {\n        throw new QueryError(`LIMIT must be a non-negative integer at position ${numTok.pos}`);\n      }\n      limit = n;\n    }\n\n    if (peek().type !== \"EOF\") {\n      throw new QueryError(`Unexpected token ${peek().type} at position ${peek().pos}`);\n    }\n\n    return {\n      type: \"SELECT\",\n      columns,\n      table,\n      where,\n      orderBy,\n      limit\n    };\n  }\n\n  function parseColumnList(): ColumnList {\n    const first = peek();\n    if (first.type === \"STAR\") {\n      consume(\"STAR\");\n      return { type: \"STAR\" };\n    }\n\n    const cols: string[] = [];\n    while (true) {\n      if (first.type === \"IDENT\") {\n        cols.push(consume(\"IDENT\").value);\n      } else {\n        throw new QueryError(`Expected column name or '*' at position ${first.pos}`);\n      }\n\n      if (peek().type === \"COMMA\") {\n        consume(\"COMMA\");\n        const next = peek();\n        if (next.type === \"EOF\") {\n          throw new QueryError(`Trailing comma in column list at position ${next.pos}`);\n        }\n      } else {\n        break;\n      }\n    }\n\n    return { type: \"COLUMN_LIST\", columns: cols };\n  }\n\n  function parseCondition(): Condition {\n    // AND binds tighter than OR\n    let left = parseComparison();\n    \n    while (peek().type === \"AND\" || peek().type === \"OR\") {\n      const op = consume().type;\n      const right = parseComparison();\n      left = { type: op, left, right };\n    }\n    \n    return left;\n  }\n\n  function parseComparison(): Condition {\n    const left = consume(\"IDENT\").value;\n    \n    const opTok = peek();\n    if (opTok.type !== \"OP\") {\n      throw new QueryError(`Expected operator at position ${opTok.pos}`);\n    }\n    const op = consume(\"OP\").value;\n    \n    const rightTok = peek();\n    let right: Value;\n    if (rightTok.type === \"NUMBER\") {\n      right = parseInt(rightTok.value, 10);\n    } else if (rightTok.type === \"STRING\") {\n      right = rightTok.value;\n    } else {\n      throw new QueryError(`Expected value at position ${rightTok.pos}`);\n    }\n    \n    return { type: \"COMPARISON\", left, op, right };\n  }\n\n  function parseOrderBy(): ASTNode {\n    const col = consume(\"IDENT\").value;\n    let direction: \"ASC\" | \"DESC\" = \"ASC\";\n    if (peek().type === \"ASC\") {\n      consume(\"ASC\");\n      direction = \"ASC\";\n    } else if (peek().type === \"DESC\") {\n      consume(\"DESC\");\n      direction = \"DESC\";\n    }\n    return { type: \"ORDER_BY\", column: col, direction };\n  }\n\n  return parseSelect();\n}\n\nfunction evaluate(ast: ASTNode, rows: Row[]): Row[] {\n  if (ast.type !== \"SELECT\") {\n    throw new QueryError(\"Invalid AST\");\n  }\n\n  let filtered = rows;\n  if (ast.where) {\n    filtered = filtered.filter(row => evaluateCondition(ast.where, row));\n  }\n\n  let sorted = filtered;\n  if (ast.orderBy) {\n    sorted = stableSort(sorted, ast.orderBy);\n  }\n\n  let limited = sorted;\n  if (ast.limit !== undefined) {\n    limited = sorted.slice(0, ast.limit);\n  }\n\n  return project(limited, ast.columns);\n}\n\nfunction evaluateCondition(node: Condition, row: Row): boolean {\n  switch (node.type) {\n    case \"COMPARISON\": {\n      const cell = row[node.left];\n      const val = node.right;\n      const op = node.op;\n      \n      if (cell === undefined) {\n        switch (op) {\n          case \"=\": return false;\n          case \"!=\": return true;\n          case \"<\": case \"<=\": case \">\": case \">=\": return false;\n          default: throw new QueryError(`Unknown operator ${op}`);\n        }\n      }\n\n      if (typeof cell !== typeof val) {\n        switch (op) {\n          case \"=\": case \"<\": case \"<=\": case \">\": case \">=\": return false;\n          case \"!=\": return true;\n          default: throw new QueryError(`Unknown operator ${op}`);\n        }\n      }\n\n      switch (op) {\n        case \"=\": return cell === val;\n        case \"!=\": return cell !== val;\n        case \"<\": return cell < val;\n        case \"<=\": return cell <= val;\n        case \">\": return cell > val;\n        case \">=\": return cell >= val;\n        default: throw new QueryError(`Unknown operator ${op}`);\n      }\n    }\n    case \"AND\": {\n      return evaluateCondition(node.left, row) && evaluateCondition(node.right, row);\n    }\n    case \"OR\": {\n      return evaluateCondition(node.left, row) || evaluateCondition(node.right, row);\n    }\n    default:\n      throw new QueryError(`Invalid condition node type: ${node.type}`);\n  }\n}\n\nfunction stableSort(rows: Row[], orderBy: ASTNode): Row[] {\n  if (orderBy.type !== \"ORDER_BY\") {\n    throw new QueryError(\"Expected ORDER_BY node\");\n  }\n  \n  const { column, direction } = orderBy;\n  const dirMultiplier = direction === \"ASC\" ? 1 : -1;\n\n  return [...rows].sort((a, b) => {\n    const valA = a[column];\n    const valB = b[column];\n\n    // Handle missing keys or type mismatches as equal\n    if (valA === undefined || valB === undefined || typeof valA !== typeof valB) {\n      return 0;\n    }\n\n    if (typeof valA === \"number\" && typeof valB === \"number\") {\n      const diff = valA - valB;\n      return diff * dirMultiplier;\n    }\n\n    if (typeof valA === \"string\" && typeof valB === \"string\") {\n      const diff = valA.localeCompare(valB);\n      return diff * dirMultiplier;\n    }\n\n    return 0;\n  });\n}\n\nfunction project(rows: Row[], columns: ColumnList): Row[] {\n  if (columns.type === \"STAR\") {\n    return rows.map(row => ({ ...row }));\n  }\n\n  const colNames = columns.columns;\n  return rows.map(row => {\n    const newRow: Row = {};\n    for (const col of colNames) {\n      if (row[col] !== undefined) {\n        newRow[col] = row[col];\n      }\n    }\n    return newRow;\n  });\n}\n\nexport function query(sql: string, rows: Row[]): Row[] {\n  try {\n    const tokens = tokenize(sql);\n    const ast = parse(tokens);\n    return evaluate(ast, rows);\n  } catch (e) {\n    if (e instanceof QueryError) {\n      throw e;\n    }\n    throw new QueryError(\"Internal parsing or evaluation error\");\n  }\n}\n```",
    "passed": 15,
    "test_error": ""
  }
]