/*

 * 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.lang.module.ModuleDescriptor.Requires.Modifier;

import java.lang.reflect.Layer;

import java.util.ArrayDeque;

import java.util.ArrayList;

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.Map.Entry;

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.Hasher;

/**

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

 * {@link Configuration#resolveRequiresAndUses}.

 */

final class Resolver {

    private final ModuleFinder beforeFinder;

    private final Configuration parent;

    private final ModuleFinder afterFinder;

    // maps module name to module reference

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

    Resolver(ModuleFinder beforeFinder,

             Configuration parent,

             ModuleFinder afterFinder) {

        this.beforeFinder = beforeFinder;

        this.parent = parent;

        this.afterFinder = afterFinder;

    }

    /**

     * Resolves the given named modules.

     *

     * @throws ResolutionException

     */

    Resolver resolveRequires(Collection<String> roots) {

        long start = trace_start("Resolve");

        // 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 (parent.findModule(root).isPresent()) {

                    // in parent, nothing to do

                    continue;

                }

                mref = findWithAfterFinder(root);

                if (mref == null) {

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

                }

            }

            if (TRACE) {

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

                if (mref.location().isPresent())

                    trace("  (%s)", mref.location().get());

            }

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

            nameToReference.put(root, mref);

            q.push(mref.descriptor());

        }

        resolve(q);

        if (TRACE) {

            long duration = System.currentTimeMillis() - start;

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

            trace("Resolver completed in %s ms", duration);

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

        }

        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()) {

                String dn = requires.name();

                // find dependence

                ModuleReference mref = findWithBeforeFinder(dn);

                if (mref == null) {

                    if (parent.findModule(dn).isPresent())

                        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 (TRACE) {

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

                                dn, descriptor.name());

                        if (mref.location().isPresent())

                            trace("  (%s)", mref.location().get());

                    }

                }

            }

            resolved.add(descriptor);

        }

        return resolved;

    }

    /**

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

     * service-use relation.

     */

    Resolver resolveUses() {

        long start = trace_start("Bind");

        // 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 (String sn : descriptor.provides().keySet()) {

                    // 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> candidateConsumers = new HashSet<>();

        Configuration p = parent;

        while (p != null) {

            candidateConsumers.addAll(p.descriptors());

            p = p.parent().orElse(null);

        }

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

            candidateConsumers.add(mref.descriptor());

        }

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

        // that provide an implementation of that service

        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 (TRACE && mref.location().isPresent())

                                            trace("  (%s)", mref.location().get());

                                        nameToReference.put(pn, mref);

                                        q.push(provider);

                                    }

                                }

                            }

                        }

                    }

                }

            }

            candidateConsumers = resolve(q);

        } while (!candidateConsumers.isEmpty());

        if (TRACE) {

            long duration = System.currentTimeMillis() - start;

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

            trace("Bind completed in %s ms", duration);

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

        }

        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.

     */

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

        detectCycles();

        checkPlatformConstraints();

        checkHashes();

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

        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

     * the hash of the dependency's module reference.

     */

    private void checkHashes() {

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

            ModuleDescriptor descriptor = mref.descriptor();

            // get map of module names to hash

            Optional<Hasher.DependencyHashes> ohashes = descriptor.hashes();

            if (!ohashes.isPresent())

                continue;

            Hasher.DependencyHashes hashes = ohashes.get();

            // check dependences

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

                String dn = d.name();

                String recordedHash = hashes.hashFor(dn);

                if (recordedHash != null) {

                    ModuleReference other = nameToReference.get(dn);

                    if (other == null) {

                        other = parent.findModule(dn)

                                .map(ResolvedModule::reference)

                                .orElse(null);

                    }

                    if (other == null)

                        throw new InternalError(dn + " not found");

                    String actualHash = other.computeHash(hashes.algorithm());

                    if (actualHash == null)

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

                    if (!recordedHash.equals(actualHash)) {

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

                                dn, actualHash, recordedHash);

                    }

                }

            }

        }

    }

    /**

     * Computes and sets the readability graph for the modules in the given

     * Resolution object.

     *

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

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

     * dependence graph has m1 requires m2 && m2 requires public m3 then the

     * resulting readability graph will contain m1 reads m2, m1

     * reads m3, and m2 reads m3.

     *

     * TODO: Use a more efficient algorithm, maybe cache the requires public

     *       in parent configurations.

     */

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

        // 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<>();

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

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

        // need "requires public" from the modules in parent configurations as

        // there may be selected modules that have a dependency on modules in

        // the parent configuration.

        Configuration p = parent;

        while (p != null) {

            for (ModuleDescriptor descriptor : p.descriptors()) {

                ResolvedModule x = p.findModule(descriptor.name()).orElse(null);

                if (x == null)

                    throw new InternalError();

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

                    if (requires.modifiers().contains(Modifier.PUBLIC)) {

                        String dn = requires.name();

                        ResolvedModule y = p.findModule(dn).orElse(null);

                        if (y == null)

                            throw new InternalError(dn + " not found");

                        g2.computeIfAbsent(x, k -> new HashSet<>()).add(y);

                    }

                }

            }

            p = p.parent().orElse(null);

        }

        // populate g1 and g2 with the dependences from the selected modules

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

            ModuleDescriptor descriptor = mref.descriptor();

            ResolvedModule x = new ResolvedModule(cf, mref);

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

            g1.put(x, reads);

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

            g2.put(x, requiresPublic);