/*

 * Copyright (c) 2013, 2016, 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 java.lang.module;

import java.io.PrintStream;

import java.lang.module.ModuleDescriptor.Provides;

import java.lang.module.ModuleDescriptor.Requires.Modifier;

import java.lang.reflect.Layer;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.Deque;

import java.util.HashMap;

import java.util.HashSet;

import java.util.LinkedHashSet;

import java.util.List;

import java.util.Map;

import java.util.Objects;

import java.util.Optional;

import java.util.Set;

import java.util.StringJoiner;

import java.util.stream.Collectors;

import jdk.internal.module.ModuleHashes;

/**

 * The resolver used by {@link Configuration#resolveRequires} and

 * {@link Configuration#resolveRequiresAndUses}.

 *

 * @implNote The resolver is used at VM startup and so deliberately avoids

 * using lambda and stream usages in code paths used during startup.

 */

final class Resolver {

    private final ModuleFinder beforeFinder;

    private final List<Configuration> parents;

    private final ModuleFinder afterFinder;

    private final PrintStream traceOutput;

    // maps module name to module reference

    private final Map<String, ModuleReference> nameToReference = new HashMap<>();

    Resolver(ModuleFinder beforeFinder,

             List<Configuration> parents,

             ModuleFinder afterFinder,

             PrintStream traceOutput) {

        this.beforeFinder = beforeFinder;

        this.parents = parents;

        this.afterFinder = afterFinder;

        this.traceOutput = traceOutput;

    }

    /**

     * Resolves the given named modules.

     *

     * @throws ResolutionException

     */

    Resolver resolveRequires(Collection<String> roots) {

        // create the visit stack to get us started

        Deque<ModuleDescriptor> q = new ArrayDeque<>();

        for (String root : roots) {

            // find root module

            ModuleReference mref = findWithBeforeFinder(root);

            if (mref == null) {

                if (findInParent(root) != null) {

                    // in parent, nothing to do

                    continue;

                }

                mref = findWithAfterFinder(root);

                if (mref == null) {

                    fail("Module %s not found", root);

                }

            }

            if (isTracing()) {

                trace("Root module %s located", root);

                mref.location().ifPresent(uri -> trace("  (%s)", uri));

            }

            assert mref.descriptor().name().equals(root);

            nameToReference.put(root, mref);

            q.push(mref.descriptor());

        }

        resolve(q);

        return this;

    }

    /**

     * Resolve all modules in the given queue. On completion the queue will be

     * empty and any resolved modules will be added to {@code nameToReference}.

     *

     * @return The set of module resolved by this invocation of resolve

     */

    private Set<ModuleDescriptor> resolve(Deque<ModuleDescriptor> q) {

        Set<ModuleDescriptor> resolved = new HashSet<>();

        while (!q.isEmpty()) {

            ModuleDescriptor descriptor = q.poll();

            assert nameToReference.containsKey(descriptor.name());

            // process dependences

            for (ModuleDescriptor.Requires requires : descriptor.requires()) {

                // only required at compile-time

                if (requires.modifiers().contains(Modifier.STATIC))

                    continue;

                String dn = requires.name();

                // find dependence

                ModuleReference mref = findWithBeforeFinder(dn);

                if (mref == null) {

                    if (findInParent(dn) != null) {

                        // dependence is in parent

                        continue;

                    }

                    mref = findWithAfterFinder(dn);

                    if (mref == null) {

                        fail("Module %s not found, required by %s",

                                dn, descriptor.name());

                    }

                }

                if (!nameToReference.containsKey(dn)) {

                    nameToReference.put(dn, mref);

                    q.offer(mref.descriptor());

                    resolved.add(mref.descriptor());

                    if (isTracing()) {

                        trace("Module %s located, required by %s",

                                dn, descriptor.name());

                        mref.location().ifPresent(uri -> trace("  (%s)", uri));

                    }

                }

            }

            resolved.add(descriptor);

        }

        return resolved;

    }

    /**

     * Augments the set of resolved modules with modules induced by the

     * service-use relation.

     */

    Resolver resolveUses() {

        // Scan the finders for all available service provider modules. As

        // java.base uses services then then module finders will be scanned

        // anyway.

        Map<String, Set<ModuleReference>> availableProviders = new HashMap<>();

        for (ModuleReference mref : findAll()) {

            ModuleDescriptor descriptor = mref.descriptor();

            if (!descriptor.provides().isEmpty()) {

                for (Provides provides :  descriptor.provides()) {

                    String sn = provides.service();

                    // computeIfAbsent

                    Set<ModuleReference> providers = availableProviders.get(sn);

                    if (providers == null) {

                        providers = new HashSet<>();

                        availableProviders.put(sn, providers);

                    }

                    providers.add(mref);

                }

            }

        }

        // create the visit stack

        Deque<ModuleDescriptor> q = new ArrayDeque<>();

        // the initial set of modules that may use services

        Set<ModuleDescriptor> initialConsumers;

        if (Layer.boot() == null) {

            initialConsumers = new HashSet<>();

        } else {

            initialConsumers = parents.stream()

                    .flatMap(Configuration::configurations)

                    .distinct()

                    .flatMap(c -> c.descriptors().stream())

                    .collect(Collectors.toSet());

        }

        for (ModuleReference mref : nameToReference.values()) {

            initialConsumers.add(mref.descriptor());

        }

        // Where there is a consumer of a service then resolve all modules

        // that provide an implementation of that service

        Set<ModuleDescriptor> candidateConsumers = initialConsumers;

        do {

            for (ModuleDescriptor descriptor : candidateConsumers) {

                if (!descriptor.uses().isEmpty()) {

                    for (String service : descriptor.uses()) {

                        Set<ModuleReference> mrefs = availableProviders.get(service);

                        if (mrefs != null) {

                            for (ModuleReference mref : mrefs) {

                                ModuleDescriptor provider = mref.descriptor();

                                if (!provider.equals(descriptor)) {

                                    trace("Module %s provides %s, used by %s",

                                            provider.name(), service, descriptor.name());

                                    String pn = provider.name();

                                    if (!nameToReference.containsKey(pn)) {

                                        if (isTracing()) {

                                            mref.location()

                                                .ifPresent(uri -> trace("  (%s)", uri));

                                        }

                                        nameToReference.put(pn, mref);

                                        q.push(provider);

                                    }

                                }

                            }

                        }

                    }

                }

            }

            candidateConsumers = resolve(q);

        } while (!candidateConsumers.isEmpty());

        return this;

    }

    /**

     * Execute post-resolution checks and returns the module graph of resolved

     * modules as {@code Map}. The resolved modules will be in the given

     * configuration.

     *

     * @param check {@true} to execute the post resolution checks

     */

    Map<ResolvedModule, Set<ResolvedModule>> finish(Configuration cf,

                                                    boolean check)

    {

        if (isTracing()) {

            trace("Result:");

            Set<String> names = nameToReference.keySet();

            names.stream().sorted().forEach(name -> trace("  %s", name));

        }

        if (check) {

            detectCycles();

            checkPlatformConstraints();

            checkHashes();

        }

        Map<ResolvedModule, Set<ResolvedModule>> graph = makeGraph(cf);

        if (check) {

            checkExportSuppliers(graph);

        }

        return graph;

    }

    /**

     * Checks the given module graph for cycles.

     *

     * For now the implementation is a simple depth first search on the

     * dependency graph. We'll replace this later, maybe with Tarjan.

     */

    private void detectCycles() {

        visited = new HashSet<>();

        visitPath = new LinkedHashSet<>(); // preserve insertion order

        for (ModuleReference mref : nameToReference.values()) {

            visit(mref.descriptor());

        }

        visited.clear();

    }

    // the modules that were visited

    private Set<ModuleDescriptor> visited;

    // the modules in the current visit path

    private Set<ModuleDescriptor> visitPath;

    private void visit(ModuleDescriptor descriptor) {

        if (!visited.contains(descriptor)) {

            boolean added = visitPath.add(descriptor);

            if (!added) {

                throw new ResolutionException("Cycle detected: " +

                        cycleAsString(descriptor));

            }

            for (ModuleDescriptor.Requires requires : descriptor.requires()) {

                String dn = requires.name();

                ModuleReference mref = nameToReference.get(dn);

                if (mref != null) {

                    ModuleDescriptor other = mref.descriptor();

                    if (other != descriptor) {

                        // dependency is in this configuration

                        visit(other);

                    }

                }

            }

            visitPath.remove(descriptor);

            visited.add(descriptor);

        }

    }

    /**

     * Returns a String with a list of the modules in a detected cycle.

     */

    private String cycleAsString(ModuleDescriptor descriptor) {

        List<ModuleDescriptor> list = new ArrayList<>(visitPath);

        list.add(descriptor);

        int index = list.indexOf(descriptor);

        return list.stream()

                .skip(index)

                .map(ModuleDescriptor::name)

                .collect(Collectors.joining(" -> "));

    }

    /**

     * If there are platform specific modules then check that the OS name,

     * architecture and version match.

     *

     * @apiNote This method does not currently check if the OS matches

     *          platform specific modules in parent configurations.

     */

    private void checkPlatformConstraints() {

        // first module encountered that is platform specific

        String savedModuleName = null;

        String savedOsName = null;

        String savedOsArch = null;

        String savedOsVersion = null;

        for (ModuleReference mref : nameToReference.values()) {

            ModuleDescriptor descriptor = mref.descriptor();

            String osName = descriptor.osName().orElse(null);

            String osArch = descriptor.osArch().orElse(null);

            String osVersion = descriptor.osVersion().orElse(null);

            if (osName != null || osArch != null || osVersion != null) {

                if (savedModuleName == null) {

                    savedModuleName = descriptor.name();

                    savedOsName = osName;

                    savedOsArch = osArch;

                    savedOsVersion = osVersion;

                } else {

                    boolean matches = platformMatches(osName, savedOsName)

                            && platformMatches(osArch, savedOsArch)

                            && platformMatches(osVersion, savedOsVersion);

                    if (!matches) {

                        String s1 = platformAsString(savedOsName,

                                                     savedOsArch,

                                                     savedOsVersion);

                        String s2 = platformAsString(osName, osArch, osVersion);

                        fail("Mismatching constraints on target platform: "

                                + savedModuleName + ": " + s1

                                + ", " + descriptor.name() + ": " + s2);

                    }

                }

            }

        }

    }

    /**

     * Returns true if the s1 and s2 are equal or one of them is null.

     */

    private boolean platformMatches(String s1, String s2) {

        if (s1 == null || s2 == null)

            return true;

        else

            return Objects.equals(s1, s2);

    }

    /**

     * Return a string that encodes the OS name/arch/version.

     */

    private String platformAsString(String osName,

                                    String osArch,

                                    String osVersion) {

        return new StringJoiner("-")

                .add(Objects.toString(osName, "*"))

                .add(Objects.toString(osArch, "*"))

                .add(Objects.toString(osVersion, "*"))

                .toString();

    }

    /**

     * Checks the hashes in the module descriptor to ensure that they match

     * any recorded hashes.

     */

    private void checkHashes() {

        for (ModuleReference mref : nameToReference.values()) {

                continue;

            String algorithm = hashes.algorithm();

            for (String dn : hashes.names()) {

                    ResolvedModule resolvedModule = findInParent(dn);

                    if (resolvedModule != null)

                }

                // skip checking the hash if the module has been patched

                if (other != null && !other.isPatched()) {

                    byte[] recordedHash = hashes.hashFor(dn);

                    byte[] actualHash = other.computeHash(algorithm);

                    if (actualHash == null)

                        fail("Unable to compute the hash of module %s", dn);

                    if (!Arrays.equals(recordedHash, actualHash)) {

                        fail("Hash of %s (%s) differs to expected hash (%s)" +

                             " recorded in %s", dn, toHexString(actualHash),

                             toHexString(recordedHash), descriptor.name());

                    }

                }

            }

        }

    }

    private static String toHexString(byte[] ba) {

        StringBuilder sb = new StringBuilder(ba.length * 2);

        for (byte b: ba) {

            sb.append(String.format("%02x", b & 0xff));

        }

        return sb.toString();

    }

    /**

     * Computes the readability graph for the modules in the given Configuration.

     *

     * The readability graph is created by propagating "requires" through the

     * "requires transitive" edges of the module dependence graph. So if the

     * module dependence graph has m1 requires m2 && m2 requires transitive m3

     * then the resulting readability graph will contain m1 reads m2, m1 reads m3,

     * and m2 reads m3.

     */

    private Map<ResolvedModule, Set<ResolvedModule>> makeGraph(Configuration cf) {

        // initial capacity of maps to avoid resizing

        int capacity = 1 + (4 * nameToReference.size())/ 3;

        // the "reads" graph starts as a module dependence graph and

        // is iteratively updated to be the readability graph

        Map<ResolvedModule, Set<ResolvedModule>> g1 = new HashMap<>(capacity);

        // the "requires transitive" graph, contains requires transitive edges only

        Map<ResolvedModule, Set<ResolvedModule>> g2;

        // need "requires transitive" from the modules in parent configurations