Fragment spreads must not form cycles

Formal Specification

• For each fragmentDefinition in the document
• Let visited be the empty set.
• DetectCycles( fragmentDefinition , visited )

DetectCycles(fragmentDefinition,visited):

• Let spreads be all fragment spread descendants of fragmentDefinition
• For each spread in spreads
  • visited must not contain spread
  • Let nextVisited be the set including spread and members of visited
  • Let nextFragmentDefinition be the target of spread
  • DetectCycles( nextFragmentDefinition , nextVisited )

Explanatory Text

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.

This invalidates fragments that would result in an infinite spread:

{
  dog {
    ...nameFragment
  }
}

fragment nameFragment on Dog {
  name
  ...barkVolumeFragment
}

fragment barkVolumeFragment on Dog {
  barkVolume
  ...nameFragment
}

If the above fragments were inlined, this would result in the infinitely large:

{
  dog {
    name
    barkVolume
    name
    barkVolume
    name
    barkVolume
    name
    # forever...
  }
}

This also invalidates fragments that would result in an infinite recursion when executed against cyclic data:

{
  dog {
    ...dogFragment
  }
}

fragment dogFragment on Dog {
  name
  owner {
    ...ownerFragment
  }
}

fragment ownerFragment on Dog {
  name
  pets {
    ...dogFragment
  }
}