1 | <?php |
||
2 | |||
3 | namespace Digia\GraphQL\Validation\Rule; |
||
4 | |||
5 | use Digia\GraphQL\Language\Node\FragmentDefinitionNode; |
||
6 | use Digia\GraphQL\Language\Node\FragmentSpreadNode; |
||
7 | use Digia\GraphQL\Language\Node\OperationDefinitionNode; |
||
8 | use Digia\GraphQL\Language\Visitor\VisitorResult; |
||
9 | use Digia\GraphQL\Validation\ValidationException; |
||
10 | use function Digia\GraphQL\Validation\fragmentCycleMessage; |
||
11 | |||
12 | /** |
||
13 | * No fragment cycles |
||
14 | * |
||
15 | * The graph of fragment spreads must not form any cycles including spreading itself. |
||
16 | * Otherwise an operation could infinitely spread or infinitely execute on cycles in the underlying data. |
||
17 | */ |
||
18 | class NoFragmentCyclesRule extends AbstractRule |
||
19 | { |
||
20 | /** |
||
21 | * Tracks already visited fragments to maintain O(N) and to ensure that cycles |
||
22 | * are not redundantly reported. |
||
23 | * |
||
24 | * @var array |
||
25 | */ |
||
26 | protected $visitedFragments = []; |
||
27 | |||
28 | /** |
||
29 | * Array of AST nodes used to produce meaningful errors. |
||
30 | * |
||
31 | * @var array |
||
32 | */ |
||
33 | protected $spreadPath = []; |
||
34 | |||
35 | /** |
||
36 | * Position in the spread path. |
||
37 | * |
||
38 | * @var array |
||
39 | */ |
||
40 | protected $spreadPathIndexByName = []; |
||
41 | |||
42 | /** |
||
43 | * @inheritdoc |
||
44 | */ |
||
45 | protected function enterOperationDefinition(OperationDefinitionNode $node): VisitorResult |
||
46 | { |
||
47 | return new VisitorResult(null); // Operations cannot contain fragments. |
||
48 | } |
||
49 | |||
50 | /** |
||
51 | * @inheritdoc |
||
52 | */ |
||
53 | protected function enterFragmentDefinition(FragmentDefinitionNode $node): VisitorResult |
||
54 | { |
||
55 | if (!isset($this->visitedFragments[$node->getNameValue()])) { |
||
56 | $this->detectFragmentCycle($node); |
||
57 | } |
||
58 | |||
59 | return new VisitorResult(null); |
||
60 | } |
||
61 | |||
62 | /** |
||
63 | * This does a straight-forward DFS to find cycles. |
||
64 | * It does not terminate when a cycle was found but continues to explore |
||
65 | * the graph to find all possible cycles. |
||
66 | * |
||
67 | * @param FragmentDefinitionNode $fragment |
||
68 | */ |
||
69 | protected function detectFragmentCycle(FragmentDefinitionNode $fragment): void |
||
70 | { |
||
71 | $fragmentName = $fragment->getNameValue(); |
||
72 | |||
73 | $this->visitedFragments[$fragmentName] = true; |
||
74 | |||
75 | $spreadNodes = $this->context->getFragmentSpreads($fragment->getSelectionSet()); |
||
0 ignored issues
–
show
Bug
introduced
by
![]() |
|||
76 | |||
77 | if (empty($spreadNodes)) { |
||
78 | return; |
||
79 | } |
||
80 | |||
81 | $this->spreadPathIndexByName[$fragmentName] = \count($this->spreadPath); |
||
82 | |||
83 | foreach ($spreadNodes as $spreadNode) { |
||
84 | $spreadName = $spreadNode->getNameValue(); |
||
85 | $cycleIndex = $this->spreadPathIndexByName[$spreadName] ?? null; |
||
86 | |||
87 | if (null === $cycleIndex) { |
||
88 | $this->spreadPath[] = $spreadNode; |
||
89 | |||
90 | if (!isset($this->visitedFragments[$spreadName])) { |
||
91 | $spreadFragment = $this->context->getFragment($spreadName); |
||
92 | |||
93 | if (null !== $spreadFragment) { |
||
94 | $this->detectFragmentCycle($spreadFragment); |
||
95 | } |
||
96 | } |
||
97 | |||
98 | \array_pop($this->spreadPath); |
||
99 | } else { |
||
100 | $cyclePath = \array_slice($this->spreadPath, $cycleIndex); |
||
101 | |||
102 | $this->context->reportError( |
||
103 | new ValidationException( |
||
104 | fragmentCycleMessage($spreadName, \array_map(function (FragmentSpreadNode $spread) { |
||
105 | return $spread->getNameValue(); |
||
106 | }, $cyclePath)), |
||
107 | \array_merge($cyclePath, [$spreadNode]) |
||
108 | ) |
||
109 | ); |
||
110 | } |
||
111 | } |
||
112 | |||
113 | $this->spreadPathIndexByName[$fragmentName] = null; |
||
114 | } |
||
115 | } |
||
116 |