Cypher WHERE: static validation gap on row-boolean shapes (OR / NOT / XOR among row predicates) — emergent from #1217 Earley swap

[lmeyerov]

Context

PR #1217 (closes #1031 slice 1) swaps the Cypher parser from Lark LALR(1) to Earley. This solves `#1031`'s mixed-pattern+row WHERE problem cleanly, but as an architectural side effect lifts an implicit syntax gate that was previously hiding a missing semantic gate.

Pre-#1217 (LALR):

• Queries like `WHERE a.x = 1 OR b.y = 2` failed at parse time because LALR(1) couldn't unify FIRST sets across the OR boundary.
• The implicit "if I can't parse it, you can't write it" was the de facto semantic gate.
• No explicit Cypher-side validator existed for these shapes — none was needed, because the syntax gate caught them.

Post-#1217 (Earley):

• Earley parses OR/NOT/XOR among row predicates without complaint.
• Binder routes the result through the existing raw-expr path: `BoundPredicate(expression="a.x = 1 OR b.y = 2")`.
• Lowering's runtime evaluator (`graphistry.compute.gfql.expr_parser.parse_expr` at `lowering.py:7031`) handles AND/OR/NOT/XOR with correct SQL three-valued logic — so simple cases produce correct results.
• No static gate exists for compositions we haven't validated.

Asymmetry made visible

PR #1217 explicitly gates pattern-side compositions (NOT-pattern, OR-pattern, multi-positive-pattern) with E108 at the lift step in `parser.py::generic_where_clause` → `_build_where_with_pattern_lift`. Row-boolean compositions silently pass through:

Newly-accepted shape	Static gate?	Outcome
`WHERE n.p1 = X OR n.p2 = Y`	❌ none	silent accept → expr_parser → runtime
`WHERE NOT n.p1 = X`	❌ none	silent accept
`WHERE n.p1 = X XOR n.p2 = Y`	❌ none	silent accept
`WHERE NOT (n)-[:R]->()`	✅ E108 at lift	explicit "unsupported"
`WHERE (n)-[:R]->() OR n.x = 1`	✅ E108 at lift	explicit "unsupported"
`WHERE (n)-[:R*]->() AND (m)-[:R*]->()`	✅ E108 at lift	explicit "unsupported"

Empirical evidence

PR #1217 added 5 native execution tests covering simple disjunction shapes (TCK match-where1-10 mirror, same-alias OR, NOT with NaN, OR-then-AND, multi-row union). All pass — the runtime evaluator does the right thing for property-comparison disjunctions under SQL three-valued logic.

What's not validated

Compositional edge cases that may interact with parts of the planner/runtime that were designed assuming AND-only:

1. Predicate pushdown — `pushdown_safety.py:58` explicitly says "Compound OR is not analyzed". AND has explicit handling (line 73); OR doesn't. Likely safe-by-default (predicates with OR don't push) but unverified.
2. OPTIONAL MATCH null-extension — `is_null_rejecting()` is AND-aware; behavior on `WHERE x.field = 'val' OR ` where `x` is null-extended is unverified.
3. Type coercion in OR operands — `WHERE n.p = 12 OR n.p = 'twelve'` mixed-type branches.
4. OR with NULL literals — `WHERE n.p = 12 OR n.p IS NULL` three-valued logic edge cases.
5. Nested compositions — `(a OR b) AND (c OR d)`, `NOT (a OR b)`, etc.
6. Pushdown into PatternMatch — predicates with OR being pushed should respect the OR-aware safety analysis.

Decision space (intentionally open)

Several reasonable solutions; pick based on appetite + signal:

Option A: Static validator that rejects un-validated shapes

• Walk `expr_tree` at the AST normalizer or binder. Reject row-boolean shapes that touch null-extended aliases, interact with predicate pushdown, or contain mixed-type OR branches with E108.
• Pro: symmetric with the pattern-side gates in refactor(gfql/cypher): switch to Earley parser; retire LALR pattern-shape cruft (#1031 slice 1) #1217. Defense-in-depth.
• Con: may be over-restrictive; needs careful definition of "supported subset".

Option B: Accept simpler cases provably; reject the rest

• Define a "safe subset" of OR/NOT/XOR shapes (e.g., property comparisons with non-null-extended aliases, no nested compositions). Accept those; reject the rest.
• Pro: surfaces the gradient (some OR is supported, some isn't) more honestly.
• Con: "safe subset" is hard to specify formally; risks fragmentation.

Option C: Implement full disjunction support across the pipeline

• Audit pushdown, OPTIONAL MATCH null-extension, type coercion paths for OR-correctness. Add tests for each. Then accept all of OR/NOT/XOR with full validated support.
• Pro: "correctness by construction" across the planner.
• Con: largest scope; may need M-series collaboration on pushdown's OR-awareness.

Option D: Defer + document

• Ship refactor(gfql/cypher): switch to Earley parser; retire LALR pattern-shape cruft (#1031 slice 1) #1217 as-is (already does). Document the asymmetry in CHANGELOG. Wait for bug reports or TCK-conformance sweep to surface specific failures, then fix targeted.
• Pro: lowest scope; ships value sooner.
• Con: silent-wrong-results risk if compositions interact badly with planner assumptions.

Why this isn't M-series's responsibility

The IR verifier (M2-PR3) checks plan-shape invariants (op_id uniqueness, schema consistency, dangling refs, optional-arm nullability) — not "is this Cypher WHERE a supported subset". That's a Cypher front-end concern. The pattern-shape gates in #1217 live in `parser.py::_build_where_with_pattern_lift`, which is the right home for the row-boolean gates too.

Related

• Cypher/GFQL WHERE cannot mix generic row predicates with pattern predicates #1031 — parent issue; this is a side effect of the slice-1 grammar refactor.
• PR refactor(gfql/cypher): switch to Earley parser; retire LALR pattern-shape cruft (#1031 slice 1) #1217 — Earley swap that exposes this gap.
• `graphistry.compute.gfql.expr_parser.parse_expr` — runtime evaluator (handles AND/OR/NOT/XOR with SQL three-valued logic).
• `graphistry/compute/gfql/ir/pushdown_safety.py:58` — "Compound OR is not analyzed" comment marks the boundary.

Priority

p3 — same as #1031 (architectural cleanup, no user-visible bug for simple cases; correctness risk for unvalidated compositions).

[lmeyerov]

Investigation draft moved from PR docs into the issue thread per workflow preference (no findings artifacts committed into repo docs).

Issue #1219: Row-Boolean WHERE Validation Gap (OR/NOT/XOR)

Problem Statement

PR #1217 moved Cypher parsing onto Earley, which made row-boolean forms like a OR b, NOT a, and a XOR b parse cleanly in more cases.

Current pipeline behavior is asymmetrical:

• Pattern+row mixed boolean forms are explicitly gated as unsupported (E108) in parser/normalizer flow.
• Row-only boolean forms pass through to BoundPredicate(expression=...), then lower to runtime expression evaluation.

This is acceptable for simple expressions, but it leaves a static-validation gap on edge compositions we have not explicitly validated end-to-end.

Current Code Anchors

• Parser generic WHERE route: graphistry/compute/gfql/cypher/parser.py (generic_where_clause, _mixed_where_pattern_expr_error)
• Binder split behavior: graphistry/compute/gfql/frontends/cypher/binder.py (_where_predicates, top-level AND split)
• Pushdown null-safety classifier: graphistry/compute/gfql/ir/pushdown_safety.py (is_null_rejecting)
• Pushdown implementation: graphistry/compute/gfql/passes/predicate_pushdown.py (_split_conjuncts, _push_filter_into_pattern)
• Existing shape tests: graphistry/tests/compute/gfql/cypher/test_where_bool_conformance.py

Risk Surface To Investigate

1. OPTIONAL MATCH null-extension interactions with OR/NOT/XOR predicates.
2. Predicate pushdown behavior when a conjunct contains an OR subgroup.
3. Mixed-type branches (n.p = 12 OR n.p = 'twelve') and coercion semantics.
4. NULL-aware disjunction semantics (n.p = 12 OR n.p IS NULL).
5. Nested compositions ((a OR b) AND (c OR d), NOT (a OR b)).

Candidate Solution Directions

Option A: Broad static gate now

Add a row-boolean validator that rejects unvalidated shapes with E108 before lowering.

• Pros: immediate safety envelope, symmetry with existing pattern-side unsupported gates.
• Cons: may be over-restrictive for already-working cases.

Option B: Safe-subset allowlist + reject rest

Admit explicitly defined safe forms and block the rest.

• Pros: balanced safety/velocity.
• Cons: higher maintenance burden; subset boundaries can become confusing.

Option C: Full support across planning/runtime

Audit and harden parser → binder → pushdown → lowering semantics for all row-boolean shapes.

• Pros: strongest long-term result.
• Cons: largest scope and highest schedule risk.

Option D: Documentation-only defer

Keep behavior, document caveats, and wait for concrete failures.

• Pros: lowest immediate cost.
• Cons: silent correctness risk remains for unvalidated compositions.

Recommended Path (Staged)

Recommend an A/B hybrid as immediate follow-up, with C as phase-2 hardening:

1. Phase 1: Add a conservative static gate for high-risk row-boolean shapes (especially optional/null-extension sensitive cases).
2. Phase 1: Add tests that encode accepted vs rejected shapes with explicit expected outcomes.
3. Phase 2: Expand support by hardening pushdown/null-safety analysis and relaxing gates only when proven.

This protects correctness while keeping room to broaden support deliberately.

Draft Implementation Sketch

1. Add a where row-boolean validation helper in Cypher frontend path (parser/normalizer boundary).
2. Emit E108 for disallowed shapes with actionable message that references supported subset.
3. Keep existing binder top-level AND split behavior unchanged initially.
4. Extend test matrices in:
   • graphistry/tests/compute/gfql/cypher/test_where_bool_conformance.py
   • graphistry/tests/compute/gfql/cypher/test_parser.py
   • pushdown-focused tests for optional arm + null-rejecting semantics.

Validation Matrix (Initial)

• Accept (phase 1 target): simple row OR/NOT on non-optional aliases where semantics are already covered by existing evaluator behavior.
• Reject (phase 1 target): compositions that include optional-arm/null-extension ambiguity or unsupported nested shape forms.
• Confirm no regressions on existing pattern-side E108 gates.

Review Skill Workflow For Implementation/Validation

When implementation starts, run multi-wave review workflow from review skill:

1. mode=findings fixes=deferred first, with credentials gate in Phase 1e.
2. Add/adjust code and tests.
3. Re-run review waves until convergence criteria are met.
4. Only post PR comments after explicit human confirmation.

Human Gating Requirements

• No auto-merge.
• Human approval required before selecting final option scope.
• Human approval required before posting PR comments from review flow.
• Human approval required for merge.

[lmeyerov]

Follow-up proposal based on maintainer guidance: split into two PRs.

PR1 (Phase 1): tests + validation first

• Build a positive/negative row-boolean matrix.
• Add corresponding TCK audit + implementation checks.
• Goal: define and prove current support envelope before behavior expansion.

PR2 (Phase 2): disjunction support expansion (conditional)

• Expand OR/NOT/XOR only where PR1 evidence confirms correctness.
• Add targeted planner/pushdown/null-extension safeguards and tests.

This keeps correctness gating in front of capability expansion.

[lmeyerov]

Update on stacked investigation/implementation PRs:

• Phase 1 PR: Phase 1: #1219 row-boolean WHERE audit + TCK-linked tests #1223
• Phase 2 PR: Phase 2: enable row-boolean WHERE in connected OPTIONAL MATCH #1224

Review workflow rerun completed using full multi-wave process (fixes=inline):

• Phase 1: #1219 row-boolean WHERE audit + TCK-linked tests #1223: 2 waves, converged. One IMPORTANT test-robustness finding fixed inline:
  • commit a98c2d6d (test(gfql/cypher): normalize pd.NA null sentinels in #1219 audit rows)
• Phase 2: enable row-boolean WHERE in connected OPTIONAL MATCH #1224: 2 waves, converged. No new BLOCKER/IMPORTANT findings on this PR delta.

Validation highlights:

• Phase 1: #1219 row-boolean WHERE audit + TCK-linked tests #1223 Cypher WHERE: static validation gap on row-boolean shapes (OR / NOT / XOR among row predicates) — emergent from #1217 Earley swap #1219 matrix rerun: 9 passed
• Phase 2: enable row-boolean WHERE in connected OPTIONAL MATCH #1224 Cypher WHERE: static validation gap on row-boolean shapes (OR / NOT / XOR among row predicates) — emergent from #1217 Earley swap #1219 matrix rerun: 10 passed
• Connected optional + targeted regression reruns (issue_1024/issue_996/null-extension shape): passing locally

Note for human gating:

• tck-gfql failure on match-where1-10 appears inherited from upstream stack base (#1217) xfail-contract drift and is not introduced by Phase 1: #1219 row-boolean WHERE audit + TCK-linked tests #1223/Phase 2: enable row-boolean WHERE in connected OPTIONAL MATCH #1224 deltas.

[lmeyerov]

Status update (2026-04-26): both stacked PRs are now green after landing the non-punted #1217-path fix plus TCK alignment.

• Phase 1 PR: Phase 1: #1219 row-boolean WHERE audit + TCK-linked tests #1223
  • latest tck-gfql pass: run 24956784297 / job 73076834698
• Phase 2 PR: Phase 2: enable row-boolean WHERE in connected OPTIONAL MATCH #1224
  • latest tck-gfql passes: run 24956770680 / job 73076834440 and rerun job 73077182805 on run 24956770182

Technical fixes applied in stack:

• pygraphistry: mixed-type comparison fallback to null/false semantics instead of crashing (file graphistry/compute/predicates/comparison.py), plus regression test in graphistry/tests/compute/gfql/cypher/test_lowering.py.
• tck-gfql: contract/feature updates including match-where1-10 and related mismatches; branch refs for both stack branches pinned to commit 8d14800e41f08c028cbd104d3fa4a205865bd981.

No auto-merge performed; human gating remains required for any merge decision.