Skip to content

Commit 1f95f69

Browse files
andimarekandimarek
committed
adding a cycle schema analyzer
1 parent 776de2f commit 1f95f69

2 files changed

Lines changed: 201 additions & 0 deletions

File tree

‎src/main/java/graphql/util/CyclicSchemaAnalyzer.java‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package graphql.util;
2+
3+
import graphql.ExperimentalApi;
4+
import graphql.introspection.Introspection;
5+
import graphql.schema.GraphQLNamedType;
6+
import graphql.schema.GraphQLSchema;
7+
import graphql.schema.GraphQLSchemaElement;
8+
import graphql.schema.GraphQLTypeUtil;
9+
import graphql.schema.GraphQLTypeVisitorStub;
10+
import graphql.schema.SchemaTraverser;
11+
12+
import java.util.ArrayList;
13+
import java.util.List;
14+
import java.util.StringJoiner;
15+
16+
/**
17+
* Finds all cycles in a GraphQL Schema.
18+
* Cycles caused by built-in introspection types are filtered out.
19+
*/
20+
@ExperimentalApi
21+
public class CyclicSchemaAnalyzer {
22+
23+
public static class SchemaElementWithChild {
24+
private final GraphQLSchemaElement element;
25+
private final int childIndex;
26+
27+
public SchemaElementWithChild(GraphQLSchemaElement element, int childIndex) {
28+
this.element = element;
29+
this.childIndex = childIndex;
30+
}
31+
}
32+
33+
public static class SchemaCycle {
34+
private final List<SchemaElementWithChild> cycleElements = new ArrayList<>();
35+
36+
public String toString() {
37+
StringJoiner result = new StringJoiner(" -> ");
38+
for (SchemaElementWithChild schemaElementWithChild : cycleElements) {
39+
result.add(GraphQLTypeUtil.simplePrint(schemaElementWithChild.element) + "/" + schemaElementWithChild.childIndex);
40+
}
41+
return result.toString();
42+
}
43+
44+
public int size() {
45+
return cycleElements.size();
46+
}
47+
}
48+
49+
public static List<SchemaCycle> findCycles(GraphQLSchema schema) {
50+
SchemaTraverser traverser = new SchemaTraverser();
51+
Visitor visitor = new Visitor();
52+
traverser.depthFirstFullSchema(visitor, schema);
53+
List<SchemaCycle> result = new ArrayList<>();
54+
for (List<Breadcrumb<GraphQLSchemaElement>> possibleCycle : visitor.cycles) {
55+
SchemaCycle schemaCycle = new SchemaCycle();
56+
// the breadcrumbs are in the reverse order of the dependency
57+
for (int i = possibleCycle.size() - 1; i >= 0; i--) {
58+
Breadcrumb<GraphQLSchemaElement> breadcrumb = possibleCycle.get(i);
59+
SchemaElementWithChild schemaElementWithChild = new SchemaElementWithChild(breadcrumb.getNode(), breadcrumb.getLocation().getIndex());
60+
schemaCycle.cycleElements.add(schemaElementWithChild);
61+
}
62+
result.add(schemaCycle);
63+
}
64+
return result;
65+
}
66+
67+
private static class Visitor extends GraphQLTypeVisitorStub {
68+
public final List<List<Breadcrumb<GraphQLSchemaElement>>> cycles = new ArrayList<>();
69+
70+
@Override
71+
public TraversalControl visitBackRef(TraverserContext<GraphQLSchemaElement> context) {
72+
List<Breadcrumb<GraphQLSchemaElement>> breadcrumbs = context.getBreadcrumbs();
73+
74+
for (int i = breadcrumbs.size() - 1; i >= 0; i--) {
75+
Breadcrumb<GraphQLSchemaElement> breadcrumb = breadcrumbs.get(i);
76+
if (breadcrumb.getNode() instanceof GraphQLNamedType && Introspection.isIntrospectionTypes((GraphQLNamedType) breadcrumb.getNode())) {
77+
return TraversalControl.CONTINUE;
78+
}
79+
if (breadcrumb.getNode() == context.thisNode()) {
80+
List<Breadcrumb<GraphQLSchemaElement>> cycle = breadcrumbs.subList(0, i + 1);
81+
cycles.add(cycle);
82+
}
83+
}
84+
return TraversalControl.CONTINUE;
85+
}
86+
}
87+
88+
89+
}

‎src/test/groovy/graphql/util/CyclicSchemaAnalyzerTest.groovy‎

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
package graphql.util
2+
3+
4+
import graphql.TestUtil
5+
import spock.lang.Specification
6+
7+
class CyclicSchemaAnalyzerTest extends Specification {
8+
9+
def "simple cycle"() {
10+
given:
11+
def sdl = '''
12+
13+
type Query {
14+
hello: [Foo]
15+
}
16+
type Foo {
17+
foo: Foo
18+
}
19+
'''
20+
def schema = TestUtil.schema(sdl)
21+
when:
22+
def cycles = CyclicSchemaAnalyzer.findCycles(schema)
23+
24+
then:
25+
cycles.size() == 1
26+
cycles[0].toString() == "Foo/0 -> foo/0"
27+
28+
}
29+
30+
def "multiple cycles"() {
31+
given:
32+
def sdl = '''
33+
34+
type Query {
35+
hello: [Foo]
36+
}
37+
type Foo {
38+
bar: Bar
39+
foo: Foo
40+
}
41+
type Bar {
42+
bar: [Bar]!
43+
foo: Foo
44+
}
45+
'''
46+
def schema = TestUtil.schema(sdl)
47+
when:
48+
def cycles = CyclicSchemaAnalyzer.findCycles(schema)
49+
50+
then:
51+
cycles.size() == 3
52+
cycles[0].toString() == "Bar/0 -> bar/0 -> [Bar]!/0 -> [Bar]/0"
53+
cycles[1].toString() == "Foo/0 -> bar/0 -> Bar/1 -> foo/0"
54+
cycles[2].toString() == "Foo/1 -> foo/0"
55+
56+
}
57+
58+
def "larger cycle"() {
59+
given:
60+
def sdl = '''
61+
62+
type Query {
63+
hello: [Foo]
64+
}
65+
type Foo {
66+
bar: Bar
67+
}
68+
type Bar {
69+
subBar: SubBar
70+
}
71+
type SubBar {
72+
foo: Foo
73+
}
74+
75+
'''
76+
def schema = TestUtil.schema(sdl)
77+
when:
78+
def cycles = CyclicSchemaAnalyzer.findCycles(schema)
79+
80+
then:
81+
cycles.size() == 1
82+
cycles[0].toString() == "Foo/0 -> bar/0 -> Bar/0 -> subBar/0 -> SubBar/0 -> foo/0"
83+
84+
}
85+
86+
def "two parents and no cycle"() {
87+
given:
88+
def sdl = '''
89+
90+
type Query {
91+
hello: Foo1
92+
hello2: Foo2
93+
}
94+
type Foo1 {
95+
bar: Bar
96+
}
97+
type Foo2 {
98+
bar: Bar
99+
}
100+
type Bar {
101+
id: ID
102+
}
103+
'''
104+
def schema = TestUtil.schema(sdl)
105+
when:
106+
def cycles = CyclicSchemaAnalyzer.findCycles(schema)
107+
108+
then:
109+
cycles.size() == 0
110+
111+
}
112+
}

0 commit comments

Comments
 (0)