1package validator
 2
 3import (
 4	"fmt"
 5	"strings"
 6
 7	"github.com/vektah/gqlparser/ast"
 8	. "github.com/vektah/gqlparser/validator"
 9)
10
11func init() {
12	AddRule("NoFragmentCycles", func(observers *Events, addError AddErrFunc) {
13		visitedFrags := make(map[string]bool)
14
15		observers.OnFragment(func(walker *Walker, fragment *ast.FragmentDefinition) {
16			var spreadPath []*ast.FragmentSpread
17			spreadPathIndexByName := make(map[string]int)
18
19			var recursive func(fragment *ast.FragmentDefinition)
20			recursive = func(fragment *ast.FragmentDefinition) {
21				if visitedFrags[fragment.Name] {
22					return
23				}
24
25				visitedFrags[fragment.Name] = true
26
27				spreadNodes := getFragmentSpreads(fragment.SelectionSet)
28				if len(spreadNodes) == 0 {
29					return
30				}
31				spreadPathIndexByName[fragment.Name] = len(spreadPath)
32
33				for _, spreadNode := range spreadNodes {
34					spreadName := spreadNode.Name
35
36					cycleIndex, ok := spreadPathIndexByName[spreadName]
37
38					spreadPath = append(spreadPath, spreadNode)
39					if !ok {
40						spreadFragment := walker.Document.Fragments.ForName(spreadName)
41						if spreadFragment != nil {
42							recursive(spreadFragment)
43						}
44					} else {
45						cyclePath := spreadPath[cycleIndex : len(spreadPath)-1]
46						var fragmentNames []string
47						for _, fs := range cyclePath {
48							fragmentNames = append(fragmentNames, fs.Name)
49						}
50						var via string
51						if len(fragmentNames) != 0 {
52							via = fmt.Sprintf(" via %s", strings.Join(fragmentNames, ", "))
53						}
54						addError(
55							Message(`Cannot spread fragment "%s" within itself%s.`, spreadName, via),
56							At(spreadNode.Position),
57						)
58					}
59
60					spreadPath = spreadPath[:len(spreadPath)-1]
61				}
62
63				delete(spreadPathIndexByName, fragment.Name)
64			}
65
66			recursive(fragment)
67		})
68	})
69}
70
71func getFragmentSpreads(node ast.SelectionSet) []*ast.FragmentSpread {
72	var spreads []*ast.FragmentSpread
73
74	setsToVisit := []ast.SelectionSet{node}
75
76	for len(setsToVisit) != 0 {
77		set := setsToVisit[len(setsToVisit)-1]
78		setsToVisit = setsToVisit[:len(setsToVisit)-1]
79
80		for _, selection := range set {
81			switch selection := selection.(type) {
82			case *ast.FragmentSpread:
83				spreads = append(spreads, selection)
84			case *ast.Field:
85				setsToVisit = append(setsToVisit, selection.SelectionSet)
86			case *ast.InlineFragment:
87				setsToVisit = append(setsToVisit, selection.SelectionSet)
88			}
89		}
90	}
91
92	return spreads
93}