import { inspect } from '../jsutils/inspect.ts';
import type { ASTNode } from './ast.ts';
import { QueryDocumentKeys } from './ast.ts';
import type { Kind } from './kinds.ts';
export type ASTReducer<R> = {
readonly [NodeT in ASTNode as NodeT['kind']]?: (node: {
[K in keyof NodeT]: ReducedField<NodeT[K], R>;
}) => R;
};
type ReducedField<T, R> = T extends ASTNode
? R
: T extends ReadonlyArray<ASTNode>
? ReadonlyArray<R>
: T;
type Frame =
| {
parent: ReadonlyArray<unknown>;
keys: undefined;
results: Array<unknown>;
index: number;
}
| {
parent: ASTNode;
keys: ReadonlyArray<string>;
results: { [key: string]: unknown; kind: ASTNode['kind'] };
index: number;
};
export function reduce<R>(root: ASTNode, reducer: Required<ASTReducer<R>>): R;
export function reduce<R>(
root: ASTNode,
reducer: ASTReducer<R | undefined>,
): R | undefined;
export function reduce<R>(
root: ASTNode,
reducer: ASTReducer<R>,
): R | undefined {
const stack: Array<Frame> = [];
let frame: Frame = {
parent: [root],
keys: undefined,
results: [],
index: -1,
};
let node: unknown;
do {
let kind: Kind | undefined;
frame.index++;
const length =
frame.keys === undefined ? frame.parent.length : frame.keys.length;
if (frame.index === length) {
node = frame.results;
kind = frame.keys === undefined ? undefined : frame.results.kind;
frame = stack.pop() as Frame;
} else {
node =
frame.keys === undefined
? frame.parent[frame.index]
: frame.parent[frame.keys[frame.index] as keyof ASTNode];
if (node == null && stack.length !== 0) {
continue;
}
if (Array.isArray(node)) {
if (node.length !== 0) {
stack.push(frame);
frame = { parent: node, keys: undefined, results: [], index: -1 };
continue;
}
} else {
const parent = node as ASTNode;
kind = parent?.kind;
const keys =
typeof kind === 'string' ? QueryDocumentKeys[kind] : undefined;
if (!Array.isArray(keys)) {
throw new Error(`Invalid AST Node: ${inspect(node)}.`);
}
if (keys.length !== 0) {
stack.push(frame);
frame = { parent, keys, results: { ...parent }, index: -1 };
continue;
}
}
}
if (kind !== undefined) {
const reduceNode = reducer[kind] as ((node: unknown) => R) | undefined;
node = reduceNode?.(node);
}
if (frame.keys === undefined) {
frame.results.push(node);
} else {
frame.results[frame.keys[frame.index]] = node;
}
} while (stack.length !== 0);
return node as R | undefined;
}