/*

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

import java.util.Optional;

import java.util.Set;

import java.util.StringJoiner;

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

    // module constraints on target platform

    private String osName;

    private String osArch;

    String osName() { return osName; }

    String osArch() { return osArch; }

    /**

     * @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 constraints on target platform, checking that they don't conflict

        for (Configuration parent : parents) {

            String value = parent.osName();

            if (value != null) {

                if (osName == null) {

                    osName = value;

                } else {

                    if (!value.equals(osName)) {

                        failParentConflict("Operating System", osName, value);

                    }

                }

            }

            value = parent.osArch();

            if (value != null) {

                if (osArch == null) {

                    osArch = value;

                } else {

                    if (!value.equals(osArch)) {

                        failParentConflict("OS architecture", osArch, value);

                    }

                }

            }

        }

    }

    private void failParentConflict(String constraint, String s1, String s2) {

        String msg = "Parents have conflicting constraints on target "

                     + constraint + ": " + s1 + ", " + s2;

        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 module %s located", root);

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

            }

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

            // 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 (!nameToReference.containsKey(dn)) {

                    addFoundModule(mref);

                    q.offer(mref.descriptor());

                    if (isTracing()) {

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

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

                                        }

                                        addFoundModule(mref);

                                        q.push(provider);

                                    }

                                }

                            }

                        }

                    }

                }

            }

            candidateConsumers = resolve(q);

        } while (!candidateConsumers.isEmpty());

        return this;

    }

    /**

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

                checkTargetConstraints(mn, target);

        }

        nameToReference.put(mn, mref);

    }

    /**

     * Check that the module's constraints on the target platform do not

     * conflict with the constraints of other modules resolved so far or

     * modules in parent configurations.

     */

    private void checkTargetConstraints(String mn, ModuleTarget target) {

        String value = target.osName();

        if (value != null) {

            if (osName == null) {

                osName = value;

            } else {

                if (!value.equals(osName)) {

                    failTargetConstraint(mn, target);

                }

            }

        }

        value = target.osArch();

        if (value != null) {

            if (osArch == null) {

                osArch = value;

            } else {

                if (!value.equals(osArch)) {

                    failTargetConstraint(mn, target);

                }

            }

        }

    }

    private void failTargetConstraint(String mn, ModuleTarget target) {

        String s1 = targetAsString(osName, osArch);

        String s2 = targetAsString(target.osName(), target.osArch());

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

                 + " conflict with other modules: %s", mn, s1, s2);

    }

    private String targetAsString(ModuleTarget target) {

        return targetAsString(target.osName(), target.osArch());

    }

    private String targetAsString(String osName, String osArch) {

        return new StringJoiner("-")

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

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

                .toString();

    }

    /**

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

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

                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;