hidden format and tests

rocicorp · grgbkr · Nov 6, 2024 · Nov 7, 2024 · Nov 8, 2024 · Nov 11, 2024
commit 55aa81789d3d0fd00e1cb104d9c0c10342ae3eeb
diff --git a/packages/zero-protocol/src/ast.ts b/packages/zero-protocol/src/ast.ts
@@ -69,10 +69,25 @@ export const simpleConditionSchema = v.object({
   ),
 });
 
+export const existsConditionSchema = v.readonlyObject({
+  type: v.literal('exists'),
+});
+
+export const correlatedSubqueryConditionConditionSchema = v.union(
+  existsConditionSchema,
+);
+
+export const correlatedSubqueryConditionSchema = v.readonlyObject({
+  type: v.literal('subquery'),
+  related: v.lazy(() => correlatedSubquerySchema),
+  condition: correlatedSubqueryConditionConditionSchema,
+});
+
 export const conditionSchema = v.union(
   simpleConditionSchema,
   v.lazy(() => conjunctionSchema),
   v.lazy(() => disjunctionSchema),
+  correlatedSubqueryConditionSchema,
 );
 
 const conjunctionSchema: v.Type<Conjunction> = v.readonlyObject({
@@ -200,7 +215,11 @@ export type LiteralValue =
  * ivm1 supports Conjunctions and Disjunctions.
  * We'll support them in the future.
  */
-export type Condition = SimpleCondition | Conjunction | Disjunction;
+export type Condition =
+  | SimpleCondition
+  | Conjunction
+  | Disjunction
+  | CorrelatedSubQueryCondition;
 
 export type SimpleCondition = {
   type: 'simple';
@@ -230,6 +249,16 @@ export type Disjunction = {
   conditions: readonly Condition[];
 };
 
+export type CorrelatedSubQueryCondition = {
+  type: 'subquery';
+  related: CorrelatedSubQuery;
+  condition: CorrelatedSubQueryConditionCondition;
+};
+
+export type CorrelatedSubQueryConditionCondition = {
+  type: 'exists';
+};
+
 /**
  * A parameter is a value that is not known at the time the query is written
  * and is resolved at runtime.
@@ -297,7 +326,7 @@ export function normalizeAST(ast: AST): Required<AST> {
 }
 
 function sortedWhere(where: Condition): Condition {
-  if (where.type === 'simple') {
+  if (where.type === 'simple' || where.type === 'subquery') {
     return where;
   }
   return {
@@ -331,6 +360,19 @@ function cmpCondition(a: Condition, b: Condition): number {
     return 1; // Order SimpleConditions first to simplify logic for invalidation filtering.
   }
 
+  if (a.type === 'subquery') {
+    if (b.type !== 'subquery') {
+      return -1; // Order subquery before conjuctions/disjuctions
+    }
+    return (
+      cmpRelated(a.related, b.related) ||
+      compareUTF8MaybeNull(a.condition.type, b.condition.type)
+    );
+  }
+  if (b.type === 'subquery') {
+    return -1; // Order subquery before conjuctions/disjuctions
+  }
+
   const val = compareUTF8MaybeNull(a.type, b.type);
   if (val !== 0) {
     return val;
@@ -368,7 +410,7 @@ function flattened<T extends Condition>(cond: T | undefined): T | undefined {
   if (cond === undefined) {
     return undefined;
   }
-  if (cond.type === 'simple') {
+  if (cond.type === 'simple' || cond.type === 'subquery') {
     return cond;
   }
   const conditions = defined(

diff --git a/packages/zql/src/builder/builder.ts b/packages/zql/src/builder/builder.ts
@@ -5,6 +5,8 @@ import type {
   AST,
   Condition,
   Conjunction,
+  CorrelatedSubQuery,
+  CorrelatedSubQueryCondition,
   Disjunction,
   LiteralValue,
   Ordering,
@@ -14,6 +16,7 @@ import type {
 } from '../../../zero-protocol/src/ast.js';
 import type {Row} from '../../../zero-protocol/src/data.js';
 import type {PrimaryKey} from '../../../zero-protocol/src/primary-key.js';
+import {Exists} from '../ivm/exists.js';
 import {FanIn} from '../ivm/fan-in.js';
 import {FanOut} from '../ivm/fan-out.js';
 import {Filter} from '../ivm/filter.js';
@@ -104,15 +107,25 @@ export function bindStaticParameters(
   };
 
   function bindCondition(condition: Condition): Condition {
-    return condition.type === 'simple'
-      ? {
-          ...condition,
-          value: bindValue(condition.value),
-        }
-      : {
-          ...condition,
-          conditions: condition.conditions.map(bindCondition),
-        };
+    if (condition.type === 'simple') {
+      return {
+        ...condition,
+        value: bindValue(condition.value),
+      };
+    }
+    if (condition.type === 'subquery') {
+      return {
+        ...condition,
+        related: {
+          ...condition.related,
+          subquery: visit(condition.related.subquery),
+        },
+      };
+    }
+    return {
+      ...condition,
+      conditions: condition.conditions.map(bindCondition),
+    };
   }
 
   const bindValue = (value: ValuePosition): LiteralValue => {
@@ -157,8 +170,20 @@ function buildPipelineInternal(
     end = new Skip(end, ast.start);
   }
 
+  const correlatedSubQueryConditions = gatherCorrelatedSubQueryConditions(
+    ast.where,
+  );
+
+  for (const csqc of correlatedSubQueryConditions) {
+    let csq = csqc.related;
+    if (csqc.condition.type === 'exists') {
+      csq = {...csq, subquery: {...csq.subquery, limit: EXISTS_LIMIT}};
+    }
+    end = applyCorrelatedSubQuery(csq, delegate, staticQueryParameters, end);
+  }
+
   if (ast.where) {
-    end = applyWhere(end, ast.where, appliedFilters);
+    end = applyWhere(end, ast.where, appliedFilters, delegate);
   }
 
   if (ast.limit) {
@@ -167,28 +192,38 @@ function buildPipelineInternal(
 
   if (ast.related) {
     for (const sq of ast.related) {
-      assert(sq.subquery.alias, 'Subquery must have an alias');
-      const child = buildPipelineInternal(
-        sq.subquery,
-        delegate,
-        staticQueryParameters,
-        sq.correlation.childField,
-      );
-      end = new Join({
-        parent: end,
-        child,
-        storage: delegate.createStorage(),
-        parentKey: sq.correlation.parentField,
-        childKey: sq.correlation.childField,
-        relationshipName: sq.subquery.alias,
-        hidden: sq.hidden ?? false,
-      });
+      end = applyCorrelatedSubQuery(sq, delegate, staticQueryParameters, end);
     }
   }
 
   return end;
 }
 
+function applyCorrelatedSubQuery(
+  sq: CorrelatedSubQuery,
+  delegate: BuilderDelegate,
+  staticQueryParameters: StaticQueryParameters | undefined,
+  end: Input,
+) {
+  assert(sq.subquery.alias, 'Subquery must have an alias');
+  const child = buildPipelineInternal(
+    sq.subquery,
+    delegate,
+    staticQueryParameters,
+    sq.correlation.childField,
+  );
+  end = new Join({
+    parent: end,
+    child,
+    storage: delegate.createStorage(),
+    parentKey: sq.correlation.parentField,
+    childKey: sq.correlation.childField,
+    relationshipName: sq.subquery.alias,
+    hidden: sq.hidden ?? false,
+  });
+  return end;
+}
+
 function applyWhere(
   input: Input,
   condition: Condition,
@@ -197,12 +232,15 @@ function applyWhere(
   // Or we do the union of queries approach and retain this `appliedFilters` and `sourceConnect` behavior.
   // Downside of that being unbounded memory usage.
   appliedFilters: boolean,
+  delegate: BuilderDelegate,
 ): Input {
   switch (condition.type) {
     case 'and':
-      return applyAnd(input, condition, appliedFilters);
+      return applyAnd(input, condition, appliedFilters, delegate);
     case 'or':
-      return applyOr(input, condition, appliedFilters);
+      return applyOr(input, condition, appliedFilters, delegate);
+    case 'subquery':
+      return applyCorrelatedSubqueryCondition(input, condition, delegate);
     default:
       return applySimpleCondition(input, condition, appliedFilters);
   }
@@ -212,9 +250,10 @@ function applyAnd(
   input: Input,
   condition: Conjunction,
   appliedFilters: boolean,
+  delegate: BuilderDelegate,
 ) {
   for (const subCondition of condition.conditions) {
-    input = applyWhere(input, subCondition, appliedFilters);
+    input = applyWhere(input, subCondition, appliedFilters, delegate);
   }
   return input;
 }
@@ -223,11 +262,12 @@ function applyOr(
   input: Input,
   condition: Disjunction,
   appliedFilters: boolean,
+  delegate: BuilderDelegate,
 ): Input {
   const fanOut = new FanOut(input);
   const branches: Input[] = [];
   for (const subCondition of condition.conditions) {
-    branches.push(applyWhere(fanOut, subCondition, appliedFilters));
+    branches.push(applyWhere(fanOut, subCondition, appliedFilters, delegate));
   }
   assert(branches.length > 0, 'Or condition must have at least one branch');
   return new FanIn(fanOut, branches as [Input, ...Input[]]);
@@ -264,3 +304,37 @@ export function assertOrderingIncludesPK(
     );
   }
 }
+function applyCorrelatedSubqueryCondition(
+  input: Input,
+  condition: CorrelatedSubQueryCondition,
+  delegate: BuilderDelegate,
+): Input {
+  assert(condition.condition.type === 'exists');
+  return new Exists(
+    input,
+    delegate.createStorage(),
+    must(condition.related.subquery.alias),
+  );
+}
+
+function gatherCorrelatedSubQueryConditions(condition: Condition | undefined) {
+  const correlatedSubQueryConditions: CorrelatedSubQueryCondition[] = [];
+  const gather = (condition: Condition) => {
+    if (condition.type === 'subquery') {
+      correlatedSubQueryConditions.push(condition);
+      return;
+    }
+    if (condition.type === 'and' || condition.type === 'or') {
+      for (const c of condition.conditions) {
+        gather(c);
+      }
+      return;
+    }
+  };
+  if (condition) {
+    gather(condition);
+  }
+  return correlatedSubQueryConditions;
+}
+
+const EXISTS_LIMIT = 5;
diff --git a/packages/zql/src/ivm/array-view.ts b/packages/zql/src/ivm/array-view.ts
@@ -34,7 +34,7 @@ export class ArrayView<V extends View> implements Output, TypedView<V> {
 
   constructor(
     input: Input,
-    format: Format = {singular: false, relationships: {}},
+    format: Format = {singular: false, hidden: false, relationships: {}},
   ) {
     this.#input = input;
     this.#schema = input.getSchema();