1 files changed, 78 insertions, 0 deletions
diff --git a/school/node_modules/graphql/validation/rules/NoFragmentCyclesRule.js.flow b/school/node_modules/graphql/validation/rules/NoFragmentCyclesRule.js.flow
new file mode 100644
index 0000000..5687322
--- /dev/null
+++ b/school/node_modules/graphql/validation/rules/NoFragmentCyclesRule.js.flow
@@ -0,0 +1,78 @@
+// @flow strict
+import { GraphQLError } from '../../error/GraphQLError';
+
+import type { ASTVisitor } from '../../language/visitor';
+import type { FragmentDefinitionNode } from '../../language/ast';
+
+import type { ASTValidationContext } from '../ValidationContext';
+
+export function NoFragmentCyclesRule(
+  context: ASTValidationContext,
+): 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): void {
+    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}.` : '.'),
+            cyclePath,
+          ),
+        );
+      }
+      spreadPath.pop();
+    }
+
+    spreadPathIndexByName[fragmentName] = undefined;
+  }
+}