/
NoFragmentCycles.js
86 lines (73 loc) · 2.59 KB
/
NoFragmentCycles.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* Copyright (c) 2015-present, Facebook, Inc.
*
* This source code is licensed under the MIT license found in the
* LICENSE file in the root directory of this source tree.
*
* @flow strict
*/
import type ValidationContext from '../ValidationContext';
import { GraphQLError } from '../../error';
import type { FragmentDefinitionNode } from '../../language/ast';
import type { ASTVisitor } from '../../language/visitor';
export function cycleErrorMessage(
fragName: string,
spreadNames: Array<string>,
): string {
const via = spreadNames.length ? ' via ' + spreadNames.join(', ') : '';
return `Cannot spread fragment "${fragName}" within itself${via}.`;
}
export function NoFragmentCycles(context: ValidationContext): ASTVisitor {
// 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: FragmentDefinitionNode) {
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 (let i = 0; i < spreadNodes.length; i++) {
const spreadNode = spreadNodes[i];
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 fragmentNames = cyclePath.slice(0, -1).map(s => s.name.value);
context.reportError(
new GraphQLError(
cycleErrorMessage(spreadName, fragmentNames),
cyclePath,
),
);
}
spreadPath.pop();
}
spreadPathIndexByName[fragmentName] = undefined;
}
}