/*

 * Copyright (c) 2013, 2019, 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.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.Optional;

import java.util.Set;

import java.util.stream.Collectors;

import jdk.internal.module.ModuleHashes;

import jdk.internal.module.ModuleReferenceImpl;

import jdk.internal.module.ModuleTarget;

/**

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

 * Configuration#resolveAndBind}.

 *

 * @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<>();

    // true if all automatic modules have been found

    private boolean haveAllAutomaticModules;

    // constraint on target platform

    private String targetPlatform;

    String targetPlatform() { return targetPlatform; }

    /**

     * @throws IllegalArgumentException if there are more than one parent and

     *         the constraints on the target platform conflict

     */

    Resolver(ModuleFinder beforeFinder,

             List<Configuration> parents,

             ModuleFinder afterFinder,

             PrintStream traceOutput) {

        this.beforeFinder = beforeFinder;

        this.parents = parents;

        this.afterFinder = afterFinder;

        this.traceOutput = traceOutput;

        // record constraint on target platform, checking for conflicts

        for (Configuration parent : parents) {

            String value = parent.targetPlatform();

            if (value != null) {

                if (targetPlatform == null) {

                    targetPlatform = value;

                } else {

                    if (!value.equals(targetPlatform)) {

                        String msg = "Parents have conflicting constraints on target" +

                                     "  platform: " + targetPlatform + ", " + value;

                        throw new IllegalArgumentException(msg);

                    }

                }

            }

        }

    }

    /**

     * Resolves the given named modules.

     *

     * @throws ResolutionException

     */

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

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

                }

            }

            if (isTracing()) {

                trace("root %s", nameAndInfo(mref));

            }

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

            // if the module is an automatic module then all automatic

            // modules need to be resolved

            if (descriptor.isAutomatic() && !haveAllAutomaticModules) {

                addFoundAutomaticModules().forEach(mref -> {

                    ModuleDescriptor other = mref.descriptor();

                    q.offer(other);

                    if (isTracing()) {

                        trace("%s requires %s", descriptor.name(), nameAndInfo(mref));

                    }

                });

                haveAllAutomaticModules = true;

            }

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

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

                                 dn, descriptor.name());

                    }

                }

                if (isTracing() && !dn.equals("java.base")) {

                    trace("%s requires %s", descriptor.name(), nameAndInfo(mref));

                }

                if (!nameToReference.containsKey(dn)) {

                    addFoundModule(mref);

                    q.offer(mref.descriptor());

                }

            }

            resolved.add(descriptor);

        }

        return resolved;

    }

    /**

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

     * service-use relation.

     */

    Resolver bind() {

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

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

        // anyway.

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

        for (ModuleReference mref : findAll()) {

            ModuleDescriptor descriptor = mref.descriptor();

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

                    // the modules that provide at least one service

                    Set<ModuleDescriptor> modulesToBind = null;

                    if (isTracing()) {

                        modulesToBind = new HashSet<>();

                    }

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

                                    if (isTracing() && modulesToBind.add(provider)) {

                                        trace("%s binds %s", descriptor.name(),

                                                nameAndInfo(mref));

                                    }

                                    String pn = provider.name();

                                    if (!nameToReference.containsKey(pn)) {

                                        addFoundModule(mref);

                                        q.push(provider);

                                    }

                                }

                            }

                        }

                    }

                }

            }

            candidateConsumers = resolve(q);

        } while (!candidateConsumers.isEmpty());

        return this;

    }

    /**

     * Add all automatic modules that have not already been found to the

     * nameToReference map.

     */

    private Set<ModuleReference> addFoundAutomaticModules() {

        Set<ModuleReference> result = new HashSet<>();

        findAll().forEach(mref -> {

            String mn = mref.descriptor().name();

            if (mref.descriptor().isAutomatic() && !nameToReference.containsKey(mn)) {

                addFoundModule(mref);

                result.add(mref);

            }

        });

        return result;

    }

    /**

     * Add the module to the nameToReference map. Also check any constraints on

     * the target platform with the constraints of other modules.

     */

    private void addFoundModule(ModuleReference mref) {

        String mn = mref.descriptor().name();

        if (mref instanceof ModuleReferenceImpl) {

            ModuleTarget target = ((ModuleReferenceImpl)mref).moduleTarget();

            if (target != null)

                checkTargetPlatform(mn, target);

        }

        nameToReference.put(mn, mref);

    }

    /**

     * Check that the module's constraints on the target platform does

     * conflict with the constraint of other modules resolved so far.

     */

    private void checkTargetPlatform(String mn, ModuleTarget target) {

        String value = target.targetPlatform();

        if (value != null) {

            if (targetPlatform == null) {

                targetPlatform = value;

            } else {

                if (!value.equals(targetPlatform)) {

                    findFail("Module %s has constraints on target platform (%s)"

                             + " that conflict with other modules: %s", mn,

                             value, targetPlatform);

                }

            }

        }

    }

    /**

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

     * modules as a map.

     */

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

        detectCycles();

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

                resolveFail("Cycle detected: %s", 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(" -> "));

    }

    /**

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

     * any recorded hashes.

     */

    private void checkHashes() {

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

            // get the recorded hashes, if any

            if (!(mref instanceof ModuleReferenceImpl))

                continue;

            ModuleHashes hashes = ((ModuleReferenceImpl)mref).recordedHashes();

            if (hashes == null)

                continue;

            ModuleDescriptor descriptor = mref.descriptor();

            String algorithm = hashes.algorithm();

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

                ModuleReference mref2 = nameToReference.get(dn);

                if (mref2 == null) {

                    ResolvedModule resolvedModule = findInParent(dn);

                    if (resolvedModule != null)

                        mref2 = resolvedModule.reference();

                }

                if (mref2 == null)

                    continue;

                if (!(mref2 instanceof ModuleReferenceImpl)) {

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

                }

                ModuleReferenceImpl other = (ModuleReferenceImpl)mref2;

                if (other != null) {

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

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

                    if (actualHash == null)

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

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

                        findFail("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,