/*
 * Copyright 2015 Michael Rozumyanskiy
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.michaelrocks.lightsaber.processor;

import com.michaelrocks.lightsaber.processor.analysis.InjectionTargetDescriptor;
import com.michaelrocks.lightsaber.processor.analysis.ModuleDescriptor;
import org.objectweb.asm.Type;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class DependencyGraph {
    private final Map<Type, List<Type>> typeGraph;

    public DependencyGraph(final ProcessorContext processorContext) {
        typeGraph = new DependencyGraphBuilder(processorContext).build();
    }

    public Collection<Type> getUnresolvedDependencies() {
        final UnresolvedDependenciesSearcher searcher = new UnresolvedDependenciesSearcher(typeGraph);
        return searcher.findUnresolvedDependencies();
    }

    private static final class DependencyGraphBuilder {
        private final ProcessorContext processorContext;
        private final Map<Type, List<Type>> typeGraph = new HashMap<>();

        private DependencyGraphBuilder(final ProcessorContext processorContext) {
            this.processorContext = processorContext;
        }

        Map<Type, List<Type>> build() {
            for (final ModuleDescriptor module : processorContext.getModules()) {
                for (final MethodDescriptor providerMethod : module.getProviderMethods()) {
                    final Type returnType = providerMethod.getType().getReturnType();
                    addProviderMethodToGraph(returnType, providerMethod);
                }
            }

            for (final InjectionTargetDescriptor providableTarget : processorContext.getProvidableTargets()) {
                final MethodDescriptor constructor = providableTarget.getInjectableConstructors().get(0);
                addProviderMethodToGraph(providableTarget.getTargetType(), constructor);
            }

            return typeGraph;
        }

        private void addProviderMethodToGraph(final Type type, final MethodDescriptor providerMethod) {
            if (typeGraph.containsKey(type)) {
                processorContext.reportError(
                        new ProcessingException("Type has multiple providers: " + type));
            }

            if (providerMethod.isDefaultConstructor()) {
                typeGraph.put(type, Collections.<Type>emptyList());
            } else {
                final List<Type> argumentTypes = Arrays.asList(providerMethod.getType().getArgumentTypes());
                typeGraph.put(type, argumentTypes);
            }
        }
    }

    private static final class UnresolvedDependenciesSearcher {
        private final Map<Type, List<Type>> graph;
        private final Set<Type> visitedTypes = new HashSet<>();
        private final List<Type> unresolvedTypes = new ArrayList<>();

        private UnresolvedDependenciesSearcher(final Map<Type, List<Type>> graph) {
            this.graph = graph;
        }

        List<Type> findUnresolvedDependencies() {
            for (final Type type : graph.keySet()) {
                traverse(type);
            }
            return Collections.unmodifiableList(unresolvedTypes);
        }

        private void traverse(final Type type) {
            if (visitedTypes.add(type)) {
                final List<Type> dependencies = graph.get(type);
                if (dependencies == null) {
                    unresolvedTypes.add(type);
                } else {
                    for (final Type dependency : dependencies) {
                        traverse(dependency);
                    }
                }
            }
        }
    }
}

@@ -1511,32 +1511,188 @@
 ncies();%0A    %7D%0A%0A
+    public Collection%3CType%3E getCycles() %7B%0A        final CycleSearcher searcher = new CycleSearcher(typeGraph);%0A        return searcher.findCycles();%0A    %7D%0A%0A
     private stat
@@ -3803,20 +3803,26 @@
         
-List
+Collection
 %3CType%3E f
@@ -4442,32 +4442,32 @@
               %7D%0A
-
             %7D%0A  
@@ -4480,10 +4480,1283 @@
 %7D%0A    %7D%0A
+%0A%0A    private static final class CycleSearcher %7B%0A        private final Map%3CType, List%3CType%3E%3E graph;%0A        private final Map%3CType, VertexColor%3E colors = new HashMap%3C%3E();%0A        private final Set%3CType%3E cycles = new HashSet%3C%3E();%0A%0A        private CycleSearcher(final Map%3CType, List%3CType%3E%3E graph) %7B%0A            this.graph = graph;%0A        %7D%0A%0A        Collection%3CType%3E findCycles() %7B%0A            for (final Type type : graph.keySet()) %7B%0A                traverse(type);%0A            %7D%0A            return Collections.unmodifiableSet(cycles);%0A        %7D%0A%0A        private void traverse(final Type type) %7B%0A            final VertexColor color = colors.get(type);%0A            if (color == VertexColor.BLACK) %7B%0A                return;%0A            %7D%0A%0A            if (color == VertexColor.GRAY) %7B%0A                cycles.add(type);%0A                return;%0A            %7D%0A%0A            colors.put(type, VertexColor.GRAY);%0A            final List%3CType%3E dependencies = graph.get(type);%0A            if (dependencies != null) %7B%0A                for (final Type dependency : dependencies) %7B%0A                    traverse(dependency);%0A                %7D%0A            %7D%0A            colors.put(type, VertexColor.BLACK);%0A        %7D%0A%0A        private enum VertexColor %7B%0A            GRAY, BLACK%0A        %7D%0A    %7D%0A
 %7D%0A

Implement cycle search in dependency graph