| /** @category Validation Rules */ |
| import { GraphQLError } from '../../error/GraphQLError.mjs'; |
| |
| /** |
| * No fragment cycles |
| * |
| * The graph of fragment spreads must not form any cycles including spreading itself. |
| * Otherwise an operation could infinitely spread or infinitely execute on cycles in the underlying data. |
| * |
| * See https://spec.graphql.org/draft/#sec-Fragment-spreads-must-not-form-cycles |
| * @param context - The validation context used while checking the document. |
| * @returns A visitor that reports validation errors for this rule. |
| * @example |
| * ```ts |
| * import { buildSchema, parse, validate } from 'graphql'; |
| * import { NoFragmentCyclesRule } from 'graphql/validation'; |
| * |
| * const schema = buildSchema(` |
| * type Query { |
| * name: String |
| * } |
| * `); |
| * |
| * const invalidDocument = parse(` |
| * fragment A on Query { ...B } fragment B on Query { ...A } query { ...A } |
| * `); |
| * const invalidErrors = validate(schema, invalidDocument, [NoFragmentCyclesRule]); |
| * |
| * invalidErrors.length; // => 1 |
| * |
| * const validDocument = parse(` |
| * fragment A on Query { name } query { ...A } |
| * `); |
| * const validErrors = validate(schema, validDocument, [NoFragmentCyclesRule]); |
| * |
| * validErrors; // => [] |
| * ``` |
| */ |
| export function NoFragmentCyclesRule(context) { |
| // Tracks already visited fragments to maintain O(N) and to ensure that cycles |
| // are not redundantly reported. |
| const visitedFrags = Object.create(null); // Array of AST nodes used to produce meaningful errors |
| |
| const spreadPath = []; // Position in the spread path |
| |
| const spreadPathIndexByName = Object.create(null); |
| return { |
| OperationDefinition: () => false, |
| |
| FragmentDefinition(node) { |
| detectCycleRecursive(node); |
| return false; |
| }, |
| }; // This does a straight-forward DFS to find cycles. |
| // It does not terminate when a cycle was found but continues to explore |
| // the graph to find all possible cycles. |
| |
| function detectCycleRecursive(fragment) { |
| if (visitedFrags[fragment.name.value]) { |
| return; |
| } |
| |
| const fragmentName = fragment.name.value; |
| visitedFrags[fragmentName] = true; |
| const spreadNodes = context.getFragmentSpreads(fragment.selectionSet); |
| |
| if (spreadNodes.length === 0) { |
| return; |
| } |
| |
| spreadPathIndexByName[fragmentName] = spreadPath.length; |
| |
| for (const spreadNode of spreadNodes) { |
| const spreadName = spreadNode.name.value; |
| const cycleIndex = spreadPathIndexByName[spreadName]; |
| spreadPath.push(spreadNode); |
| |
| if (cycleIndex === undefined) { |
| const spreadFragment = context.getFragment(spreadName); |
| |
| if (spreadFragment) { |
| detectCycleRecursive(spreadFragment); |
| } |
| } else { |
| const cyclePath = spreadPath.slice(cycleIndex); |
| const viaPath = cyclePath |
| .slice(0, -1) |
| .map((s) => '"' + s.name.value + '"') |
| .join(', '); |
| context.reportError( |
| new GraphQLError( |
| `Cannot spread fragment "${spreadName}" within itself` + |
| (viaPath !== '' ? ` via ${viaPath}.` : '.'), |
| { |
| nodes: cyclePath, |
| }, |
| ), |
| ); |
| } |
| |
| spreadPath.pop(); |
| } |
| |
| spreadPathIndexByName[fragmentName] = undefined; |
| } |
| } |