ts-11-mini-sql

0.000

0/1 tests· architecture

Challenge · difficulty 5/5

# 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.

tests/solution.test.ts

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);
});

Proposed solution

```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 },
];

const query = ( // query
  // const rows: Row[] =
//                     // query
  // const rows: Row[] =
//                     const rows: Row[] =
//                     const rows: Row[] =
//                     const rows: Row[] =
//                     const rows: Row[] =
//                     const rows: Row[] =
//                     const rows: Row[] =
//                     const rows: Row[] =
//                     const

Errors (stderr)

no code extracted from response