package graphql.schema;


import graphql.Internal;
import graphql.introspection.Introspection;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

@Internal
public class SchemaUtil {

    private static final TypeTraverser TRAVERSER = new TypeTraverser();


    Map<String, GraphQLType> allTypes(final GraphQLSchema schema, final Set<GraphQLType> additionalTypes) {
        List<GraphQLType> roots = new ArrayList<GraphQLType>() {{
            add(schema.getQueryType());

            if (schema.isSupportingMutations()) {
                add(schema.getMutationType());
            }

            if (schema.isSupportingSubscriptions()) {
                add(schema.getSubscriptionType());
            }

            if (additionalTypes != null) {
                addAll(additionalTypes);
            }

            if (schema.getDirectives() != null) {
                addAll(schema.getDirectives());
            }

            add(Introspection.__Schema);
        }};

        GraphQLTypeCollectingVisitor visitor = new GraphQLTypeCollectingVisitor();
        TRAVERSER.depthFirst(visitor, roots);
        return visitor.getResult();
    }


    /*
     * Indexes GraphQLObject types registered with the provided schema by implemented GraphQLInterface name
     *
     * This helps in accelerates/simplifies collecting types that implement a certain interface
     *
     * Provided to replace {@link #findImplementations(graphql.schema.GraphQLSchema, graphql.schema.GraphQLInterfaceType)}
     *
     */
    Map<String, List<GraphQLObjectType>> groupImplementations(GraphQLSchema schema) {
        Map<String, List<GraphQLObjectType>> result = new HashMap<>();
        for (GraphQLType type : schema.getAllTypesAsList()) {
            if (type instanceof GraphQLObjectType) {
                for (GraphQLOutputType interfaceType : ((GraphQLObjectType) type).getInterfaces()) {
                    List<GraphQLObjectType> myGroup = result.computeIfAbsent(interfaceType.getName(), k -> new ArrayList<>());
                    myGroup.add((GraphQLObjectType) type);
                }
            }
        }

        return result;
    }

    /**
     * This method is deprecated due to a performance concern.
     *
     * The Algorithm complexity: O(n^2), where n is number of registered GraphQLTypes
     *
     * That indexing operation is performed twice per input document:
     * 1. during validation
     * 2. during execution
     *
     * We now indexed all types at the schema creation, which has brought complexity down to O(1)
     *
     * @param schema        GraphQL schema
     * @param interfaceType an interface type to find implementations for
     *
     * @return List of object types implementing provided interface
     *
     * @deprecated use {@link graphql.schema.GraphQLSchema#getImplementations(GraphQLInterfaceType)} instead
     */
    @Deprecated
    public List<GraphQLObjectType> findImplementations(GraphQLSchema schema, GraphQLInterfaceType interfaceType) {
        List<GraphQLObjectType> result = new ArrayList<>();
        for (GraphQLType type : schema.getAllTypesAsList()) {
            if (!(type instanceof GraphQLObjectType)) {
                continue;
            }
            GraphQLObjectType objectType = (GraphQLObjectType) type;
            if ((objectType).getInterfaces().contains(interfaceType)) {
                result.add(objectType);
            }
        }
        return result;
    }

    void replaceTypeReferences(GraphQLSchema schema) {
        final Map<String, GraphQLType> typeMap = schema.getTypeMap();
        TRAVERSER.depthFirst(new GraphQLTypeResolvingVisitor(typeMap), typeMap.values());
    }
}

@@ -482,25 +482,12 @@
 ist%3C
-GraphQLType%3E() %7B%7B
+%3E();
 %0A   
@@ -483,36 +483,38 @@
 st%3C%3E();%0A        
-    
+roots.
 add(schema.getQu
@@ -526,20 +526,16 @@
 pe());%0A%0A
-    
         
@@ -576,36 +576,38 @@
 ) %7B%0A            
- 
-   
+roots.
 add(schema.getMu
@@ -621,36 +621,32 @@
 ype());%0A        
-    
 %7D%0A%0A            i
@@ -632,36 +632,32 @@
      %7D%0A%0A        
-  
-  
 if (schema.isSup
@@ -690,28 +690,30 @@
             
-    
+roots.
 add(schema.g
@@ -739,35 +739,27 @@
 ));%0A        
-   
- 
 %7D%0A%0A
-    
         if (
@@ -793,28 +793,30 @@
             
-    
+roots.
 addAll(addit
@@ -832,35 +832,27 @@
 s);%0A        
-    %7D%0A%0A    
+%7D%0A%0A
         if (
@@ -897,20 +897,22 @@
         
-    
+roots.
 addAll(s
@@ -939,28 +939,24 @@
 ));%0A        
-    
 %7D%0A%0A         
@@ -954,20 +954,22 @@
         
-    
+roots.
 add(Intr
@@ -992,20 +992,8 @@
 ma);
-%0A        %7D%7D;
 %0A%0A  
@@ -3587,24 +3587,139 @@
 tTypeMap();%0A
+        List%3CGraphQLType%3E roots = new ArrayList%3C%3E(typeMap.values());%0A        roots.addAll(schema.getDirectives());%0A
         TRAV
@@ -3777,32 +3777,21 @@
 peMap), 
-typeMap.values()
+roots
 );%0A    %7D

Replace references in additional directives