/*

 * Copyright (c) 2017, 2018, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package jdk.internal.module;

import java.io.PrintStream;

import java.lang.module.Configuration;

import java.lang.module.ResolvedModule;

import java.net.URI;

import java.nio.file.Path;

import java.util.ArrayDeque;

import java.util.Collections;

import java.util.Deque;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Set;

import java.util.function.Consumer;

import java.util.function.Function;

import java.util.stream.Stream;

import static java.util.stream.Collectors.*;

/**

 * A Builder to compute ModuleHashes from a given configuration

 */

public class ModuleHashesBuilder {

    private final Configuration configuration;

    private final Set<String> hashModuleCandidates;

    /**

     * Constructs a ModuleHashesBuilder that finds the packaged modules

     * from the location of ModuleReference found from the given Configuration.

     *

     * @param config Configuration for building module hashes

     * @param modules the candidate modules to be hashed

     */

    public ModuleHashesBuilder(Configuration config, Set<String> modules) {

        this.configuration = config;

        this.hashModuleCandidates = modules;

    }

    /**

     * Returns a map of a module M to ModuleHashes for the modules

     * that depend upon M directly or indirectly.

     *

     * The key for each entry in the returned map is a module M that has

     * no outgoing edges to any of the candidate modules to be hashed

     * i.e. M is a leaf node in a connected subgraph containing M and

     * other candidate modules from the module graph filtering

     * the outgoing edges from M to non-candidate modules.

     */

    public Map<String, ModuleHashes> computeHashes(Set<String> roots) {

        // build a graph containing the packaged modules and

        // its transitive dependences matching --hash-modules

        Graph.Builder<String> builder = new Graph.Builder<>();

        Deque<ResolvedModule> todo = new ArrayDeque<>(configuration.modules());

        Set<ResolvedModule> visited = new HashSet<>();

        ResolvedModule rm;

        while ((rm = todo.poll()) != null) {

            if (visited.add(rm)) {

                builder.addNode(rm.name());

                for (ResolvedModule dm : rm.reads()) {

                    if (!visited.contains(dm)) {

                        todo.push(dm);

                    }

                    builder.addEdge(rm.name(), dm.name());

                }

            }

        }

        // each node in a transposed graph is a matching packaged module

        // in which the hash of the modules that depend upon it is recorded

        Graph<String> transposedGraph = builder.build().transpose();

        // traverse the modules in topological order that will identify

        // the modules to record the hashes - it is the first matching

        // module and has not been hashed during the traversal.

        Set<String> mods = new HashSet<>();

        Map<String, ModuleHashes> hashes = new HashMap<>();

        builder.build()

               .orderedNodes()

               .filter(mn -> roots.contains(mn) && !mods.contains(mn))

               .forEach(mn -> {

                   // Compute hashes of the modules that depend on mn directly and

                   // indirectly excluding itself.

                   Set<String> ns = transposedGraph.dfs(mn)

                       .stream()

                       .filter(n -> !n.equals(mn) && hashModuleCandidates.contains(n))

                       .collect(toSet());

                   mods.add(mn);

                   mods.addAll(ns);

                   if (!ns.isEmpty()) {

                       Map<String, Path> moduleToPath = ns.stream()

                           .collect(toMap(Function.identity(), this::moduleToPath));

                       hashes.put(mn, ModuleHashes.generate(moduleToPath, "SHA-256"));

                   }

               });

        return hashes;

    }

    private Path moduleToPath(String name) {

        ResolvedModule rm = configuration.findModule(name).orElseThrow(

            () -> new InternalError("Selected module " + name + " not on module path"));

        URI uri = rm.reference().location().get();

        Path path = Path.of(uri);

        String fn = path.getFileName().toString();

        if (!fn.endsWith(".jar") && !fn.endsWith(".jmod")) {

            throw new UnsupportedOperationException(path + " is not a modular JAR or jmod file");

        }

        return path;

    }

    /*

     * Utility class

     */

    static class Graph<T> {

        private final Set<T> nodes;

        private final Map<T, Set<T>> edges;

        public Graph(Set<T> nodes, Map<T, Set<T>> edges) {

            this.nodes = Collections.unmodifiableSet(nodes);

            this.edges = Collections.unmodifiableMap(edges);

        }

        public Set<T> nodes() {

            return nodes;

        }

        public Map<T, Set<T>> edges() {

            return edges;

        }

        public Set<T> adjacentNodes(T u) {

            return edges.get(u);

        }

        public boolean contains(T u) {

            return nodes.contains(u);

        }

        /**

         * Returns nodes sorted in topological order.

         */

        public Stream<T> orderedNodes() {

            TopoSorter<T> sorter = new TopoSorter<>(this);

            return sorter.result.stream();

        }

        /**

         * Traverses this graph and performs the given action in topological order.

         */

        public void ordered(Consumer<T> action) {

            TopoSorter<T> sorter = new TopoSorter<>(this);

            sorter.ordered(action);

        }

        /**

         * Traverses this graph and performs the given action in reverse topological order.

         */

        public void reverse(Consumer<T> action) {

            TopoSorter<T> sorter = new TopoSorter<>(this);

            sorter.reverse(action);

        }

        /**

         * Returns a transposed graph from this graph.

         */

        public Graph<T> transpose() {

            Builder<T> builder = new Builder<>();

            nodes.forEach(builder::addNode);

            // reverse edges

            edges.keySet().forEach(u -> {

                edges.get(u).forEach(v -> builder.addEdge(v, u));

            });

            return builder.build();

        }

        /**

         * Returns all nodes reachable from the given root.

         */

        public Set<T> dfs(T root) {

            return dfs(Set.of(root));

        }

        /**

         * Returns all nodes reachable from the given set of roots.

         */

        public Set<T> dfs(Set<T> roots) {

            ArrayDeque<T> todo = new ArrayDeque<>(roots);

            Set<T> visited = new HashSet<>();

            T u;

            while ((u = todo.poll()) != null) {

                if (visited.add(u) && contains(u)) {

                    adjacentNodes(u).stream()

                        .filter(v -> !visited.contains(v))

                        .forEach(todo::push);

                }

            }

            return visited;

        }

        public void printGraph(PrintStream out) {

            out.println("graph for " + nodes);

            nodes

                .forEach(u -> adjacentNodes(u)

                    .forEach(v -> out.format("  %s -> %s%n", u, v)));

        }

        static class Builder<T> {

            final Set<T> nodes = new HashSet<>();

            final Map<T, Set<T>> edges = new HashMap<>();

            public void addNode(T node) {

                if (nodes.add(node)) {

                    edges.computeIfAbsent(node, _e -> new HashSet<>());

                }

            }

            public void addEdge(T u, T v) {

                addNode(u);

                addNode(v);

                edges.get(u).add(v);

            }

            public Graph<T> build() {

                return new Graph<T>(nodes, edges);

            }

        }

    }

    /**

     * Topological sort

     */

    private static class TopoSorter<T> {

        final Deque<T> result = new ArrayDeque<>();

        final Graph<T> graph;

        TopoSorter(Graph<T> graph) {

            this.graph = graph;

            sort();

        }

        public void ordered(Consumer<T> action) {

            result.forEach(action);

        }

        public void reverse(Consumer<T> action) {

            result.descendingIterator().forEachRemaining(action);

        }

        private void sort() {

            Set<T> visited = new HashSet<>();

            Deque<T> stack = new ArrayDeque<>();

            graph.nodes.forEach(node -> visit(node, visited, stack));

        }

        private Set<T> children(T node) {

            return graph.edges().get(node);

        }

        private void visit(T node, Set<T> visited, Deque<T> stack) {

            if (visited.add(node)) {

                stack.push(node);

                children(node).forEach(child -> visit(child, visited, stack));

                stack.pop();

                result.addLast(node);

            }

            else if (stack.contains(node)) {

                throw new IllegalArgumentException(

                    "Cycle detected: " + node + " -> " + children(node));

            }

        }

    }

}