Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension


Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 2 additions & 0 deletions Cargo.toml
Original file line number Diff line number Diff line change
Expand Up @@ -67,6 +67,8 @@ web-sys = { version = "0.3", optional = true, features = [

[dev-dependencies]
serde_json = "1.0"
pest = "2"
pest_derive = "2"

[target.'cfg(not(target_arch = "wasm32"))'.dev-dependencies]
tempfile = "3"
Expand Down
193 changes: 193 additions & 0 deletions docs/superpowers/specs/2026-05-08-grammar-conformance-design.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,193 @@
# Grammar Specification and Conformance Harness — Design

**Date:** 2026-05-08
**Issue:** [#233](https://github.com/project-minigraf/minigraf/issues/233) — EBNF grammar specification and semantics documentation (sub-issue of [#230](https://github.com/project-minigraf/minigraf/issues/230))

## Deliverables

This work produces three things:

1. **Conformance test harness** — `pest` shadow grammar + `.edn` corpus + `grammar_conformance.rs`. Verifies continuously that the grammar doc matches parser behaviour.
2. **EBNF grammar document** — human-readable formal grammar for the full Minigraf Datalog syntax, derived from `grammar.pest` and published in the wiki (`Datalog-Reference.md`).
3. **Semantics documentation** — prose covering all constraints enforced above the structural grammar layer (not-safety, expr binding, aggregate binding, window function rules, timestamp/UUID validation). Also published in `Datalog-Reference.md`.

Tutorials are tracked separately in [#234](https://github.com/project-minigraf/minigraf/issues/234).

---

## Problem

Minigraf's Datalog query language needs a formal grammar document (EBNF). A grammar that silently diverges from the real parser is worse than no grammar — it misleads users and breaks tooling built on the spec. The conformance harness makes divergence impossible to ignore: it fails CI the moment the grammar doc and the parser disagree on any corpus fixture.

---

## Architecture

Three artefacts:

1. **`tests/grammar/grammar.pest`** — the grammar encoded as an executable `pest` PEG grammar. Serves as the machine-checkable equivalent of the EBNF documentation. The EBNF doc is derived from this file; they must say the same thing.
2. **`tests/grammar/`** corpus — `.edn` fixture files partitioned into three buckets by expected behaviour. This is the shared ground truth that both parsers are checked against.
3. **`tests/grammar_conformance.rs`** — one `#[test]` per bucket; sweeps all files, runs both parsers, reports all failures before panicking.

`pest` and `pest_derive` are added to `[dev-dependencies]` only. Zero production-code impact, no binary size change.

---

## Corpus Layout

```
tests/grammar/
grammar.pest ← pest shadow grammar
valid/ ← pest ACCEPTS + real parser ACCEPTS
transact_basic.edn
transact_valid_time_tx_level.edn
transact_valid_time_per_fact.edn
transact_valid_time_both.edn
retract_basic.edn
query_basic.edn
query_as_of_counter.edn
query_as_of_timestamp.edn
query_valid_at_timestamp.edn
query_valid_at_any_valid_time.edn
query_any_valid_time_shorthand.edn
query_with_clause.edn
query_aggregate_count.edn
query_aggregate_sum.edn
query_aggregate_udf.edn
query_window_sum.edn
query_window_rank.edn
query_window_partition_by.edn
query_not.edn
query_not_join.edn
query_or.edn
query_or_join.edn
query_expr_filter.edn
query_expr_binding.edn
query_expr_nested.edn
query_prepared_bind_slot.edn
rule_basic.edn
rule_recursive.edn
edn_uuid.edn
edn_string_escapes.edn
edn_all_value_types.edn
invalid/
syntax/ ← pest REJECTS + real parser REJECTS
unclosed_paren.edn
unclosed_bracket.edn
unknown_command.edn
empty_command.edn
unknown_tagged_literal.edn
string_unterminated.edn
bind_slot_empty.edn
keyword_invalid_chars.edn
unexpected_bare_char.edn
semantic/ ← pest ACCEPTS, real parser REJECTS
not_safety_unbound_var.edn
not_nested_inside_not.edn
or_inside_not.edn
not_join_insufficient_args.edn
expr_unbound_var_filter.edn
aggregate_var_unbound.edn
with_without_aggregate.edn
with_var_unbound.edn
window_only_func_without_over.edn
window_incompatible_func_with_over.edn
fact_too_few_elements.edn
retract_wrong_arity.edn
invalid_uuid_format.edn
```

---

## Pest Grammar Scope

### Covered (structural acceptance)

- All EDN primitives: keywords, symbols, strings (with `\n \t \r \" \\` escapes), integers (signed), floats, booleans (`true`/`false`), `nil`, `#uuid "..."`, bind slots (`$name`)
- All EDN containers: list `(...)`, vector `[...]`, map `{k v ...}`
- Top-level command forms: `(transact ...)`, `(retract ...)`, `(query ...)`, `(rule ...)`
- Query vector structure: `:find` / `:where` / `:as-of` / `:valid-at` / `:with` / `:any-valid-time` — correct keyword placement and expected value types at each position
- Fact triple shape: `[e a v]` or `[e a v {map}]`; transaction-level options map `(transact {map} [facts])`
- `where` clause shapes: pattern vector, rule invocation list, `(not ...)`, `(not-join [...] ...)`, `(or ...)`, `(or-join [...] ...)`, expr vector `[(expr) ?out?]`
- Aggregate form: `(sym ?var)`; window form: `(sym ?var :over (...))` or `(sym :over (...))`
- Expression forms: unary `(op arg)`, binary `(op arg arg)`

### Not covered (semantic layer — `invalid/semantic/` only)

These are enforced by the real parser but are above the structural grammar layer. The `pest` grammar accepts them; the real parser rejects them.

| Constraint | Corpus file |
|---|---|
| Vars in `not`/`not-join` must be bound in outer clauses | `not_safety_unbound_var.edn` |
| `(not ...)` cannot nest inside `(not ...)` | `not_nested_inside_not.edn` |
| `(or)`/`(or-join)` cannot appear inside `(not)`/`(not-join)` | `or_inside_not.edn` |
| `not-join` requires join-vars vector + ≥1 clause | `not_join_insufficient_args.edn` |
| Filter expr vars must already be bound | `expr_unbound_var_filter.edn` |
| Aggregate variable must be bound in `:where` | `aggregate_var_unbound.edn` |
| `:with` requires ≥1 aggregate in `:find` | `with_without_aggregate.edn` |
| `:with` vars must be bound in `:where` | `with_var_unbound.edn` |
| `avg`/`rank`/`row-number` require `:over` clause | `window_only_func_without_over.edn` |
| `count-distinct`/`sum-distinct` not compatible with `:over` | `window_incompatible_func_with_over.edn` |
| Fact must have ≥3 elements | `fact_too_few_elements.edn` |
| Retract fact must be exactly `[e a v]` | `retract_wrong_arity.edn` |
| UUID string must be valid RFC 4122 format | `invalid_uuid_format.edn` |

Note: ISO 8601 timestamp parsing (`:as-of`, `:valid-at`, `:valid-from`, `:valid-to`) is also semantic — `pest` accepts any string in those positions.

---

## Conformance Test Logic

```
tests/grammar_conformance.rs
```

Three `#[test]` functions. Each sweeps its directory, accumulates all failures, then panics with the full list — no early exit on first failure.

```
#[test] fn valid_corpus()
for each .edn in tests/grammar/valid/:
pest ACCEPTS → ok; failure means grammar.pest is too strict
parser ACCEPTS → ok; failure means test fixture is wrong or parser regressed

#[test] fn invalid_syntax_corpus()
for each .edn in tests/grammar/invalid/syntax/:
pest REJECTS → ok; failure means grammar.pest is too permissive
parser REJECTS → ok; failure means parser is too permissive

#[test] fn invalid_semantic_corpus()
for each .edn in tests/grammar/invalid/semantic/:
pest ACCEPTS → ok; failure means this should be in syntax/ instead
parser REJECTS → ok; failure means parser is missing a semantic check
```

Failure output per file:
```
FAIL valid/query_not.edn: parser rejected (expected accept)
FAIL invalid/semantic/not_nested_inside_not.edn: pest rejected (expected accept — semantic bucket)
```

### Wiring pest

A `Grammar` struct with `#[derive(Parser)]` and `#[grammar = "tests/grammar/grammar.pest"]` lives in `tests/grammar_conformance.rs` (or a helper module `tests/grammar_helpers.rs` if the file grows large). The conformance test calls `Grammar::parse(Rule::command, input)` — `Ok` = accepted, `Err` = rejected.

---

## Cargo Changes

```toml
[dev-dependencies]
pest = "2"
pest_derive = "2"
```

No production dependencies added.

---

## What This Does Not Cover

- **Tutorials** — tracked in [#234](https://github.com/project-minigraf/minigraf/issues/234).
- **Round-trip / pretty-print testing** — not in scope.
- **Property-based generation** — the corpus is manually curated. Fuzzing is a possible future addition.
- **Executor correctness** — the harness tests parse acceptance/rejection only, not query result correctness.
169 changes: 169 additions & 0 deletions tests/grammar/grammar.pest
Original file line number Diff line number Diff line change
@@ -0,0 +1,169 @@
// ── WHITESPACE (auto-skipped between every token) ─────────────────────────
WHITESPACE = _{ " " | "\t" | "\n" | "\r" | "," }

// ── WORD-BOUNDARY HELPER ──────────────────────────────────────────────────
// Used in negative lookaheads to enforce keyword boundaries.
word_cont = _{ ASCII_ALPHANUMERIC | "?" | "_" | "-" | "/" }

// ── EDN PRIMITIVES ────────────────────────────────────────────────────────

// boolean: "true" or "false" — only when NOT followed by a word character
// (so "trueish" is NOT a boolean, it's a plain symbol)
boolean_lit = @{ ("true" | "false") ~ !word_cont }

// nil literal
nil_lit = @{ "nil" ~ !word_cont }

// integer: optional minus, one or more digits, NOT followed by "." + digit
// (the negative lookahead prevents consuming "-3" as the start of "-3.14")
integer_lit = @{ "-"? ~ ASCII_DIGIT+ ~ !("." ~ ASCII_DIGIT) }

// float: optional minus, digits, dot, optional more digits
float_lit = @{ "-"? ~ ASCII_DIGIT+ ~ "." ~ ASCII_DIGIT* }

// string with escape sequences: \n \t \r \" \\, or any other char after \
str_char = _{ "\\" ~ ("n" | "t" | "r" | "\"" | "\\" | ANY) | !("\"" | "\\") ~ ANY }
string_lit = @{ "\"" ~ str_char* ~ "\"" }

// UUID tagged literal: #uuid "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx"
// Content validation (RFC 4122 format) is a semantic check — pest accepts any string.
uuid_lit = { "#uuid" ~ string_lit }

// Prepared-query bind slot: $name
bind_slot = @{ "$" ~ (ASCII_ALPHANUMERIC | "_" | "-")+ }

// Keyword: starts with ":", followed by alphanumeric, "/", "-", "_"
keyword = @{ ":" ~ (ASCII_ALPHANUMERIC | "/" | "-" | "_")+ }

// Logic variable: starts with "?"
variable = @{ "?" ~ word_cont* }

// Operator symbols used in expressions
op_sym = @{ "<=" | ">=" | "!=" | "<" | ">" | "=" | "+" | "*" | "/" }

// Plain symbol: letter or underscore start; or "-" followed by at least one word char.
// Negative lookaheads prevent "true", "false", "nil" from matching as plain symbols.
plain_sym = @{
!boolean_lit ~ !nil_lit ~ (ASCII_ALPHA | "_") ~ word_cont*
| "-" ~ word_cont+
}

// ── EDN VALUE (any EDN atom or container) ─────────────────────────────────
// Order matters: more specific alternatives first to avoid ambiguity.
edn_value = {
uuid_lit | boolean_lit | nil_lit | float_lit | integer_lit | string_lit |
bind_slot | keyword | op_sym | variable | plain_sym |
edn_list | edn_vector | edn_map
}
edn_list = { "(" ~ edn_value* ~ ")" }
edn_vector = { "[" ~ edn_value* ~ "]" }
edn_map = { "{" ~ (edn_value ~ edn_value)* ~ "}" }

// ── TOP-LEVEL COMMAND ─────────────────────────────────────────────────────
command = { SOI ~ (transact_cmd | retract_cmd | query_cmd | rule_cmd) ~ EOI }

// ── TRANSACT ──────────────────────────────────────────────────────────────
// (transact [facts...]) or (transact {:valid-from "ts"} [facts...])
transact_cmd = {
"(" ~ "transact" ~ (valid_time_map ~ fact_vector | fact_vector) ~ ")"
}

// ── RETRACT ───────────────────────────────────────────────────────────────
retract_cmd = { "(" ~ "retract" ~ fact_vector ~ ")" }

// Fact vector: a vector of individual fact vectors
fact_vector = { "[" ~ fact* ~ "]" }

// A single fact: permissive (edn_value+) so arity violations are semantic, not syntax.
// The real parser enforces [E A V] or [E A V {map}]; pest only requires ≥1 element.
fact = { "[" ~ edn_value+ ~ "]" }

// Transaction-level valid-time options map
valid_time_map = { "{" ~ valid_time_pair* ~ "}" }
valid_time_pair = { (":valid-from" | ":valid-to") ~ string_lit }

// ── QUERY ─────────────────────────────────────────────────────────────────
query_cmd = { "(" ~ "query" ~ query_vector ~ ")" }
query_vector = { "[" ~ query_section+ ~ "]" }

// A query vector is a sequence of keyed sections in any order.
query_section = {
find_section | where_section | as_of_section |
valid_at_section | any_valid_time_section | with_section
}

// ── FIND SECTION ──────────────────────────────────────────────────────────
// :find accepts variables, aggregates, and window functions
find_section = { ":find" ~ find_spec+ }
find_spec = { window_expr | aggregate_expr | variable }

// Aggregate: (func-name ?var) — e.g. (count ?e), (sum ?salary)
aggregate_expr = { "(" ~ (op_sym | plain_sym) ~ variable ~ ")" }

// Window function: (func ?var :over (...)) or (func :over (...)) for rank/row-number
window_expr = {
"(" ~ (op_sym | plain_sym) ~ (variable ~ ":over" | ":over") ~ over_clause ~ ")"
}
over_clause = { "(" ~ over_option* ~ ")" }
over_option = {
":partition-by" ~ variable |
":order-by" ~ variable |
":desc" | ":asc"
}

// ── WHERE SECTION ─────────────────────────────────────────────────────────
where_section = { ":where" ~ where_clause+ }

// where_clause covers all clause forms
where_clause = {
expr_clause | not_clause | not_join_clause |
or_clause | or_join_clause |
pattern_clause | rule_invocation
}

// Pattern: exactly [E A V] — three EDN values
pattern_clause = { "[" ~ edn_value ~ edn_value ~ edn_value ~ "]" }

// Expression clause: [(expr) ?out?] — first element is a list (the expression)
expr_clause = { "[" ~ expr ~ variable? ~ "]" }

// NOT / NOT-JOIN
not_clause = { "(" ~ "not" ~ where_clause+ ~ ")" }
not_join_clause = { "(" ~ "not-join" ~ join_vars ~ where_clause+ ~ ")" }

// OR / OR-JOIN
or_clause = { "(" ~ "or" ~ or_branch+ ~ ")" }
or_join_clause = { "(" ~ "or-join" ~ join_vars ~ or_branch+ ~ ")" }
join_vars = { "[" ~ variable* ~ "]" }
or_branch = { and_branch | where_clause }
and_branch = { "(" ~ "and" ~ where_clause+ ~ ")" }

// Rule invocation: (predicate-name args...)
rule_invocation = { "(" ~ plain_sym ~ edn_value* ~ ")" }

// ── EXPRESSIONS ───────────────────────────────────────────────────────────
expr = { "(" ~ expr_body ~ ")" }
expr_body = { binary_form | unary_form }
unary_form = { (unary_op | op_sym | plain_sym) ~ expr_arg }
binary_form = { binary_op ~ expr_arg ~ expr_arg }
unary_op = @{ "string?" | "integer?" | "float?" | "boolean?" | "nil?" }
binary_op = @{
"<=" | ">=" | "!=" | "starts-with?" | "ends-with?" | "contains?" | "matches?" |
"<" | ">" | "=" | "+" | "-" | "*" | "/"
}
expr_arg = {
expr | boolean_lit | nil_lit | float_lit | integer_lit |
string_lit | bind_slot | keyword | variable
}

// ── TEMPORAL / WITH SECTIONS ───────────────────────────────────────────────
as_of_section = { ":as-of" ~ (integer_lit | string_lit | bind_slot) }
valid_at_section = { ":valid-at" ~ (string_lit | ":any-valid-time" | bind_slot) }
any_valid_time_section = { ":any-valid-time" }
with_section = { ":with" ~ variable+ }

// ── RULE ──────────────────────────────────────────────────────────────────
// (rule [(head ?args) body-clause ...])
rule_cmd = { "(" ~ "rule" ~ rule_vector ~ ")" }
rule_vector = { "[" ~ rule_head ~ where_clause* ~ "]" }
rule_head = { "(" ~ plain_sym ~ variable* ~ ")" }
2 changes: 2 additions & 0 deletions tests/grammar/invalid/semantic/aggregate_var_unbound.edn
Original file line number Diff line number Diff line change
@@ -0,0 +1,2 @@
(query [:find (sum ?salary)
:where [?e :person/name ?name]])
3 changes: 3 additions & 0 deletions tests/grammar/invalid/semantic/expr_unbound_var_filter.edn
Original file line number Diff line number Diff line change
@@ -0,0 +1,3 @@
(query [:find ?name
:where [?e :person/name ?name]
[(> ?salary 50000)]])
1 change: 1 addition & 0 deletions tests/grammar/invalid/semantic/fact_too_few_elements.edn
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
(transact [[:alice :person/name]])
1 change: 1 addition & 0 deletions tests/grammar/invalid/semantic/invalid_uuid_format.edn
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
(transact [[#uuid "not-a-valid-uuid" :entity/name "test"]])
Original file line number Diff line number Diff line change
@@ -0,0 +1,4 @@
(query [:find ?name
:where [?e :person/name ?name]
(not-join [?unbound]
[?unbound :person/banned true])])
3 changes: 3 additions & 0 deletions tests/grammar/invalid/semantic/not_nested_inside_not.edn
Original file line number Diff line number Diff line change
@@ -0,0 +1,3 @@
(query [:find ?name
:where [?e :person/name ?name]
(not (not [?e :person/banned true]))])
3 changes: 3 additions & 0 deletions tests/grammar/invalid/semantic/not_safety_unbound_var.edn
Original file line number Diff line number Diff line change
@@ -0,0 +1,3 @@
(query [:find ?name
:where [?e :person/name ?name]
(not [?unbound :person/banned true])])
Loading
Loading