/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.felix.resolver;

import java.util.*;
import java.util.Map.Entry;
import java.util.concurrent.atomic.AtomicBoolean;

import org.apache.felix.resolver.ResolverImpl.PermutationType;
import org.apache.felix.resolver.ResolverImpl.ResolveSession;
import org.apache.felix.resolver.reason.ReasonException;
import org.apache.felix.resolver.util.*;
import org.osgi.framework.Version;
import org.osgi.framework.namespace.*;
import org.osgi.resource.*;
import org.osgi.service.resolver.HostedCapability;
import org.osgi.service.resolver.ResolutionException;
import org.osgi.service.resolver.ResolveContext;

class Candidates
{
    static class PopulateResult {
        boolean success;
        ResolutionError error;
        List<Requirement> remaining;
        Map<Requirement, List<Capability>> candidates;

        @Override
        public String toString() {
            return success ? "true" : error != null ? error.getMessage() : "???";
        }
    }

    private final ResolveSession m_session;
    // Maps a capability to requirements that match it.
    private final OpenHashMapSet<Capability, Requirement> m_dependentMap;
    // Maps a requirement to the capability it matches.
    private final OpenHashMapList m_candidateMap;
    // Maps a bundle revision to its associated wrapped revision; this only happens
    // when a revision being resolved has fragments to attach to it.
    private final Map<Resource, WrappedResource> m_allWrappedHosts;
    // Map used when populating candidates to hold intermediate and final results.
    private final OpenHashMap<Resource, PopulateResult> m_populateResultCache;

    private final Map<Capability, Requirement> m_subtitutableMap;

    private final OpenHashMapSet<Requirement, Capability> m_delta;
    private final AtomicBoolean m_candidateSelectorsUnmodifiable;

    /**
     * Private copy constructor used by the copy() method.
     */
    private Candidates(
        ResolveSession session,
        AtomicBoolean candidateSelectorsUnmodifiable,
        OpenHashMapSet<Capability, Requirement> dependentMap,
        OpenHashMapList candidateMap,
        Map<Resource, WrappedResource> wrappedHosts,
        OpenHashMap<Resource, PopulateResult> populateResultCache,
        Map<Capability, Requirement> substitutableMap,
        OpenHashMapSet<Requirement, Capability> delta)
    {
        m_session = session;
        m_candidateSelectorsUnmodifiable = candidateSelectorsUnmodifiable;
        m_dependentMap = dependentMap;
        m_candidateMap = candidateMap;
        m_allWrappedHosts = wrappedHosts;
        m_populateResultCache = populateResultCache;
        m_subtitutableMap = substitutableMap;
        m_delta = delta;
    }

    /**
     * Constructs an empty Candidates object.
     */
    public Candidates(ResolveSession session)
    {
        m_session = session;
        m_candidateSelectorsUnmodifiable = new AtomicBoolean(false);
        m_dependentMap = new OpenHashMapSet<Capability, Requirement>();
        m_candidateMap = new OpenHashMapList();
        m_allWrappedHosts = new HashMap<Resource, WrappedResource>();
        m_populateResultCache = new OpenHashMap<Resource, PopulateResult>();
        m_subtitutableMap = new OpenHashMap<Capability, Requirement>();
        m_delta = new OpenHashMapSet<Requirement, Capability>(3);
    }

    public int getNbResources()
    {
        return m_populateResultCache.size();
    }

    public Map<Resource, Resource> getRootHosts()
    {
        Map<Resource, Resource> hosts = new LinkedHashMap<Resource, Resource>();
        for (Resource res : m_session.getMandatoryResources())
        {
            addHost(res, hosts);
        }

        for (Resource res : m_session.getOptionalResources())
        {
            if (isPopulated(res)) {
                addHost(res, hosts);
            }
        }

        return hosts;
    }

    private void addHost(Resource res, Map<Resource, Resource> hosts) {
        if (res instanceof WrappedResource)
        {
            res = ((WrappedResource) res).getDeclaredResource();
        }
        if (!Util.isFragment(res))
        {
            hosts.put(res, getWrappedHost(res));
        } else {
            Requirement hostReq = res.getRequirements(HostNamespace.HOST_NAMESPACE).get(0);
            Capability hostCap = getFirstCandidate(hostReq);
            // If the resource is an already resolved fragment and can not
            // be attached to new hosts, there will be no matching host,
            // so ignore this resource
            if (hostCap != null) {
                res = getWrappedHost(hostCap.getResource());
                if (res instanceof WrappedResource) {
                    hosts.put(((WrappedResource) res).getDeclaredResource(), res);
                }
            }
        }
    }

    /**
     * Returns the delta which is the differences in the candidates from the
     * original Candidates permutation.
     * @return the delta
     */
    public Object getDelta()
    {
        return m_delta;
    }

    public void populate(Collection<Resource> resources)
    {
        ResolveContext rc = m_session.getContext();
        Set<Resource> toRemove = new HashSet<Resource>();
        LinkedList<Resource> toPopulate = new LinkedList<Resource>(resources);
        while (!toPopulate.isEmpty())
        {
            Resource resource = toPopulate.getFirst();
            // Get cached result
            PopulateResult result = m_populateResultCache.get(resource);
            if (result == null)
            {
                result = new PopulateResult();
                result.candidates = new OpenHashMap<Requirement, List<Capability>>();
                result.remaining = new ArrayList<Requirement>(resource.getRequirements(null));
                m_populateResultCache.put(resource, result);
            }
            if (result.success || result.error != null)
            {
                toPopulate.removeFirst();
                continue;
            }
            if (result.remaining.isEmpty())
            {
                toPopulate.removeFirst();
                result.success = true;
                addCandidates(result.candidates);
                result.candidates = null;
                result.remaining = null;
                Collection<Resource> relatedResources = rc.findRelatedResources(resource);
                m_session.setRelatedResources(resource, relatedResources);
                for (Resource relatedResource : relatedResources)
                {
                    if (m_session.isValidRelatedResource(relatedResource))
                    {
                        // This resource is a valid related resource;
                        // populate it now, consider it optional
                        toPopulate.addFirst(relatedResource);
                    }
                }
                continue;
            }
            // We have a requirement to process
            Requirement requirement = result.remaining.remove(0);
            if (!isEffective(requirement))
            {
                continue;
            }
            List<Capability> candidates = rc.findProviders(requirement);
            LinkedList<Resource> newToPopulate = new LinkedList<Resource>();
            ResolutionError thrown = processCandidates(newToPopulate, requirement, candidates);
             if (candidates.isEmpty() && !Util.isOptional(requirement))
            {
                if (Util.isFragment(resource) && rc.getWirings().containsKey(resource))
                {
                    // This is a fragment that is already resolved and there is no unresolved hosts to attach it to.
                    result.success = true;
                }
                else
                {
                    result.error = new MissingRequirementError(requirement, thrown);
                    toRemove.add(resource);
                }
                toPopulate.removeFirst();
            }
            else
            {
                if (!candidates.isEmpty())
                {
                    result.candidates.put(requirement, candidates);
                }
                if (!newToPopulate.isEmpty())
                {
                    toPopulate.addAll(0, newToPopulate);
                }
            }
        }

        while (!toRemove.isEmpty())
        {
            Iterator<Resource> iterator = toRemove.iterator();
            Resource resource = iterator.next();
            iterator.remove();
            remove(resource, toRemove);
        }
    }

    private boolean isEffective(Requirement req) {
        if (!m_session.getContext().isEffective(req)) {
            return false;
        }
        String res = req.getDirectives().get(PackageNamespace.REQUIREMENT_RESOLUTION_DIRECTIVE);
        return !PackageNamespace.RESOLUTION_DYNAMIC.equals(res);
    }

    private void populateSubstitutables()
    {
        for (Map.Entry<Resource, PopulateResult> populated : m_populateResultCache.fast())
        {
            if (populated.getValue().success)
            {
                populateSubstitutables(populated.getKey());
            }
        }
    }

    private void populateSubstitutables(Resource resource)
    {
        // Collect the package names exported
        @SuppressWarnings("serial")
        OpenHashMap<String, List<Capability>> exportNames = new OpenHashMap<String, List<Capability>>() {
            @Override
            protected List<Capability> compute(String s) {
                return new ArrayList<Capability>(1);
            }
        };
        for (Capability packageExport : resource.getCapabilities(null))
        {
            if (!PackageNamespace.PACKAGE_NAMESPACE.equals(packageExport.getNamespace()))
            {
                continue;
            }
            String packageName = (String) packageExport.getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE);
            List<Capability> caps = exportNames.getOrCompute(packageName);
            caps.add(packageExport);
        }
        if (exportNames.isEmpty())
        {
            return;
        }
        // Check if any requirements substitute one of the exported packages
        for (Requirement req : resource.getRequirements(null))
        {
            if (!PackageNamespace.PACKAGE_NAMESPACE.equals(req.getNamespace()))
            {
                continue;
            }
            CandidateSelector substitutes = m_candidateMap.get(req);
            if (substitutes != null && !substitutes.isEmpty())
            {
                String packageName = (String) substitutes.getCurrentCandidate().getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE);
                List<Capability> exportedPackages = exportNames.get(packageName);
                if (exportedPackages != null)
                {
                    // The package is exported;
                    // Check if the requirement only has the bundle's own export as candidates
                    if (!exportedPackages.containsAll(substitutes.getRemainingCandidates()))
                    {
                        for (Capability exportedPackage : exportedPackages)
                        {
                            m_subtitutableMap.put(exportedPackage, req);
                        }
                    }
                }
            }
        }
    }

    private static final int UNPROCESSED = 0;
    private static final int PROCESSING = 1;
    private static final int SUBSTITUTED = 2;
    private static final int EXPORTED = 3;

    ResolutionError checkSubstitutes()
    {
        OpenHashMap<Capability, Integer> substituteStatuses = new OpenHashMap<Capability, Integer>(m_subtitutableMap.size());
        for (Capability substitutable : m_subtitutableMap.keySet())
        {
            // initialize with unprocessed
            substituteStatuses.put(substitutable, UNPROCESSED);
        }
        // note we are iterating over the original unmodified map by design
        for (Capability substitutable : m_subtitutableMap.keySet())
        {
            isSubstituted(substitutable, substituteStatuses);
        }

        // Remove any substituted exports from candidates
        for (Map.Entry<Capability, Integer> substituteStatus : substituteStatuses.fast())
        {
            // add a permutation that imports a different candidate for the substituted if possible
            Requirement substitutedReq = m_subtitutableMap.get(substituteStatus.getKey());
            if (substitutedReq != null)
            {
                m_session.permutateIfNeeded(PermutationType.SUBSTITUTE, substitutedReq, this);
            }
            Set<Requirement> dependents = m_dependentMap.get(substituteStatus.getKey());
            if (dependents != null)
            {
                for (Requirement dependent : dependents)
                {
                    CandidateSelector candidates = m_candidateMap.get(dependent);
                    if (candidates != null)
                    {
                        candidates:
                        while (!candidates.isEmpty())
                        {
                            Capability candidate = candidates.getCurrentCandidate();
                            Integer candidateStatus = substituteStatuses.get(candidate);
                            if (candidateStatus == null)
                            {
                                candidateStatus = EXPORTED;
                            }
                            switch (candidateStatus)
                            {
                                case EXPORTED:
                                    // non-substituted candidate hit before the substituted one; do not continue
                                    break candidates;
                                case SUBSTITUTED:
                                default:
                                    // Need to remove any substituted that comes before an exported candidate
                                    candidates.removeCurrentCandidate();
                                    // continue to next candidate
                                    break;
                            }
                        }
                        if (candidates.isEmpty())
                        {
                            if (Util.isOptional(dependent))
                            {
                                m_candidateMap.remove(dependent);
                            }
                            else
                            {
                                return new MissingRequirementError(dependent);
                            }
                        }
                    }
                }
            }
        }
        return null;
    }

    private boolean isSubstituted(Capability substitutableCap, Map<Capability, Integer> substituteStatuses)
    {
        Integer substituteState = substituteStatuses.get(substitutableCap);
        if (substituteState == null)
        {
            return false;
        }

        switch (substituteState)
        {
            case PROCESSING:
                // found a cycle mark the initiator as not substituted
                substituteStatuses.put(substitutableCap, EXPORTED);
                return false;
            case SUBSTITUTED:
                return true;
            case EXPORTED:
                return false;
            default:
                break;
        }

        Requirement substitutableReq = m_subtitutableMap.get(substitutableCap);
        if (substitutableReq == null)
        {
            // this should never happen.
            return false;
        }
        // mark as processing to detect cycles
        substituteStatuses.put(substitutableCap, PROCESSING);
        // discover possible substitutes
        CandidateSelector substitutes = m_candidateMap.get(substitutableReq);
        if (substitutes != null)
        {
            for (Capability substituteCandidate : substitutes.getRemainingCandidates())
            {
                if (substituteCandidate.getResource().equals(substitutableCap.getResource()))
                {
                    substituteStatuses.put(substitutableCap, EXPORTED);
                    return false;
                }
                if (!isSubstituted(substituteCandidate, substituteStatuses))
                {
                    // The resource's exported package is substituted for this permutation.
                    substituteStatuses.put(substitutableCap, SUBSTITUTED);
                    return true;
                }
            }
        }
        // if we get here then the export is not substituted
        substituteStatuses.put(substitutableCap, EXPORTED);
        return false;
    }

    public ResolutionError populateDynamic()
    {

        // Process the candidates, removing any candidates that
        // cannot resolve.
        // TODO: verify the two following statements
        LinkedList<Resource> toPopulate = new LinkedList<Resource>();
        ResolutionError rethrow = processCandidates(toPopulate, m_session.getDynamicRequirement(), m_session.getDynamicCandidates());

        // Add the dynamic imports candidates.
        // Make sure this is done after the call to processCandidates since we want to ensure
        // fragment candidates are properly hosted before adding the candidates list which makes a copy
        addCandidates(m_session.getDynamicRequirement(), m_session.getDynamicCandidates());

        populate(toPopulate);

        CandidateSelector caps = m_candidateMap.get(m_session.getDynamicRequirement());
        if (caps != null)
        {
            m_session.getDynamicCandidates().retainAll(caps.getRemainingCandidates());
        }
        else
        {
            m_session.getDynamicCandidates().clear();
        }

        if (m_session.getDynamicCandidates().isEmpty())
        {
            if (rethrow == null)
            {
                rethrow = new DynamicImportFailed(m_session.getDynamicRequirement());
            }
            return rethrow;
        }

        PopulateResult result = new PopulateResult();
        result.success = true;
        m_populateResultCache.put(m_session.getDynamicHost(), result);
        return null;
    }

    private ResolutionError processCandidates(
        LinkedList<Resource> toPopulate,
        Requirement req,
        List<Capability> candidates)
    {
        ResolveContext rc = m_session.getContext();
        // Get satisfying candidates and populate their candidates if necessary.
        ResolutionError rethrow = null;
        Set<Capability> fragmentCands = null;
        for (Iterator<Capability> itCandCap = candidates.iterator();
            itCandCap.hasNext();)
        {
            Capability candCap = itCandCap.next();

            boolean isFragment = Util.isFragment(candCap.getResource());

            // If the capability is from a fragment, then record it
            // because we have to insert associated host capabilities
            // if the fragment is already attached to any hosts.
            if (isFragment)
            {
                if (fragmentCands == null)
                {
                    fragmentCands = new HashSet<Capability>();
                }
                fragmentCands.add(candCap);
            }

            // Do a sanity check incase the resolve context tries to attach
            // a fragment to an already resolved host capability
            if (HostNamespace.HOST_NAMESPACE.equals(req.getNamespace())) {
                if (rc.getWirings().containsKey(candCap.getResource())) {
                    itCandCap.remove();
                    continue;
                }
            }
            // If the candidate revision is a fragment, then always attempt
            // to populate candidates for its dependency, since it must be
            // attached to a host to be used. Otherwise, if the candidate
            // revision is not already resolved and is not the current version
            // we are trying to populate, then populate the candidates for
            // its dependencies as well.
            // NOTE: Technically, we don't have to check to see if the
            // candidate revision is equal to the current revision, but this
            // saves us from recursing and also simplifies exceptions messages
            // since we effectively chain exception messages for each level
            // of recursion; thus, any avoided recursion results in fewer
            // exceptions to chain when an error does occur.
            if ((isFragment || !rc.getWirings().containsKey(candCap.getResource()))
                && !candCap.getResource().equals(req.getResource()))
            {
                PopulateResult result = m_populateResultCache.get(candCap.getResource());
                if (result != null)
                {
                    if (result.error != null)
                    {
                        if (rethrow == null)
                        {
                            rethrow = result.error;
                        }
                        // Remove the candidate since we weren't able to
                        // populate its candidates.
                        itCandCap.remove();
                    }
                    else if (!result.success)
                    {
                        toPopulate.add(candCap.getResource());
                    }
                }
                else
                {
                    toPopulate.add(candCap.getResource());
                }
            }
        }

        // If any of the candidates for the requirement were from a fragment,
        // then also insert synthesized hosted capabilities for any other host
        // to which the fragment is attached since they are all effectively
        // unique capabilities.
        if (fragmentCands != null)
        {
            for (Capability fragCand : fragmentCands)
            {
                String fragCandName = fragCand.getNamespace();
                if (IdentityNamespace.IDENTITY_NAMESPACE.equals(fragCandName))
                {
                    // no need to wrap identity namespace ever
                    continue;
                }
                // Only necessary for resolved fragments.
                Wiring wiring = rc.getWirings().get(fragCand.getResource());
                if (wiring != null)
                {
                    // Fragments only have host wire, so each wire represents
                    // an attached host.
                    for (Wire wire : wiring.getRequiredResourceWires(HostNamespace.HOST_NAMESPACE))
                    {
                        // If the capability is a package, then make sure the
                        // host actually provides it in its resolved capabilities,
                        // since it may be a substitutable export.
                        if (!fragCandName.equals(PackageNamespace.PACKAGE_NAMESPACE)
                            || rc.getWirings().get(wire.getProvider())
                            .getResourceCapabilities(null).contains(fragCand))
                        {
                            // Note that we can just add this as a candidate
                            // directly, since we know it is already resolved.
                            // NOTE: We are synthesizing a hosted capability here,
                            // but we are not using a ShadowList like we do when
                            // we synthesizing capabilities for unresolved hosts.
                            // It is not necessary to use the ShadowList here since
                            // the host is resolved, because in that case we can
                            // calculate the proper package space by traversing
                            // the wiring. In the unresolved case, this isn't possible
                            // so we need to use the ShadowList so we can keep
                            // a reference to a synthesized resource with attached
                            // fragments so we can correctly calculate its package
                            // space.
                            // Must remove the fragment candidate because we must
                            // only use hosted capabilities for package namespace
                            candidates.remove(fragCand);
                            rc.insertHostedCapability(
                                candidates,
                                new WrappedCapability(
                                    wire.getCapability().getResource(),
                                    fragCand));
                        }
                    }
                }
            }
        }

        return rethrow;
    }

    public boolean isPopulated(Resource resource)
    {
        PopulateResult value = m_populateResultCache.get(resource);
        return (value != null && value.success);
    }

    public ResolutionError getResolutionError(Resource resource)
    {
        PopulateResult value = m_populateResultCache.get(resource);
        return value != null ? value.error : null;
    }

    /**
     * Adds a requirement and its matching candidates to the internal data
     * structure. This method assumes it owns the data being passed in and does
     * not make a copy. It takes the data and processes, such as calculating
     * which requirements depend on which capabilities and recording any
     * fragments it finds for future merging.
     *
     * @param req the requirement to add.
     * @param candidates the candidates matching the requirement.
     */
    private void addCandidates(Requirement req, List<Capability> candidates)
    {
        // Record the candidates.
        m_candidateMap.put(req, new CandidateSelector(candidates, m_candidateSelectorsUnmodifiable));
        for (Capability cap : candidates)
        {
            m_dependentMap.getOrCompute(cap).add(req);
        }
    }

    /**
     * Adds requirements and candidates in bulk. The outer map is not retained
     * by this method, but the inner data structures are, so they should not be
     * further modified by the caller.
     *
     * @param candidates the bulk requirements and candidates to add.
     */
    private void addCandidates(Map<Requirement, List<Capability>> candidates)
    {
        for (Map.Entry<Requirement, List<Capability>> entry : candidates.entrySet())
        {
            addCandidates(entry.getKey(), entry.getValue());
        }
    }

    /**
     * Returns the wrapped resource associated with the given resource. If the
     * resource was not wrapped, then the resource itself is returned. This is
     * really only needed to determine if the root resources of the resolve have
     * been wrapped.
     *
     * @param r the resource whose wrapper is desired.
     * @return the wrapper resource or the resource itself if it was not
     * wrapped.
     */
    public Resource getWrappedHost(Resource r)
    {
        Resource wrapped = m_allWrappedHosts.get(r);
        return (wrapped == null) ? r : wrapped;
    }

    /**
     * Gets the candidates associated with a given requirement.
     *
     * @param req the requirement whose candidates are desired.
     * @return the matching candidates or null.
     */
    public List<Capability> getCandidates(Requirement req)
    {
        CandidateSelector candidates = m_candidateMap.get(req);
        if (candidates != null)
        {
            return candidates.getRemainingCandidates();
        }
        return null;
    }

    public Capability getFirstCandidate(Requirement req)
    {
        CandidateSelector candidates = m_candidateMap.get(req);
        if (candidates != null && !candidates.isEmpty())
        {
            return candidates.getCurrentCandidate();
        }
        return null;
    }

    public void removeFirstCandidate(Requirement req)
    {
        CandidateSelector candidates = m_candidateMap.get(req);
        // Remove the conflicting candidate.
        Capability cap = candidates.removeCurrentCandidate();
        if (candidates.isEmpty())
        {
            m_candidateMap.remove(req);
        }
        // Update the delta with the removed capability
        CopyOnWriteSet<Capability> capPath = m_delta.getOrCompute(req);
        capPath.add(cap);
    }

    public CandidateSelector clearMultipleCardinalityCandidates(Requirement req, Collection<Capability> caps)
    {
        // this is a special case where we need to completely replace the CandidateSelector
        // this method should never be called from normal Candidates permutations
        CandidateSelector candidates = m_candidateMap.get(req);
        List<Capability> remaining = new ArrayList<Capability>(candidates.getRemainingCandidates());
        remaining.removeAll(caps);
        candidates = new CandidateSelector(remaining, m_candidateSelectorsUnmodifiable);
        m_candidateMap.put(req, candidates);
        return candidates;
    }

    /**
     * Merges fragments into their hosts. It does this by wrapping all host
     * modules and attaching their selected fragments, removing all unselected
     * fragment modules, and replacing all occurrences of the original fragments
     * in the internal data structures with the wrapped host modules instead.
     * Thus, fragment capabilities and requirements are merged into the
     * appropriate host and the candidates for the fragment now become
     * candidates for the host. Likewise, any module depending on a fragment now
     * depend on the host. Note that this process is sort of like
     * multiplication, since one fragment that can attach to two hosts
     * effectively gets multiplied across the two hosts. So, any modules being
     * satisfied by the fragment will end up having the two hosts as potential
     * candidates, rather than the single fragment.
     *
     * @return  ResolutionError if the removal of any unselected fragments
     * result in the root module being unable to resolve.
     */
    public ResolutionError prepare()
    {
        // Maps a host capability to a map containing its potential fragments;
        // the fragment map maps a fragment symbolic name to a map that maps
        // a version to a list of fragments requirements matching that symbolic
        // name and version.
        Map<Capability, Map<String, Map<Version, List<Requirement>>>> hostFragments =
            getHostFragments();

        // This method performs the following steps:
        // 1. Select the fragments to attach to a given host.
        // 2. Wrap hosts and attach fragments.
        // 3. Remove any unselected fragments. This is necessary because
        //    other revisions may depend on the capabilities of unselected
        //    fragments, so we need to remove the unselected fragments and
        //    any revisions that depends on them, which could ultimately cause
        //    the entire resolve to fail.
        // 4. Replace all fragments with any host it was merged into
        //    (effectively multiplying it).
        //    * This includes setting candidates for attached fragment
        //      requirements as well as replacing fragment capabilities
        //      with host's attached fragment capabilities.
        // Steps 1 and 2
        List<WrappedResource> hostResources = new ArrayList<WrappedResource>();
        List<Resource> unselectedFragments = new ArrayList<Resource>();
        for (Entry<Capability, Map<String, Map<Version, List<Requirement>>>> hostEntry : hostFragments.entrySet())
        {
            // Step 1
            Capability hostCap = hostEntry.getKey();
            Map<String, Map<Version, List<Requirement>>> fragments =
                hostEntry.getValue();
            List<Resource> selectedFragments = new ArrayList<Resource>();
            for (Entry<String, Map<Version, List<Requirement>>> fragEntry
                : fragments.entrySet())
            {
                boolean isFirst = true;
                for (Entry<Version, List<Requirement>> versionEntry
                    : fragEntry.getValue().entrySet())
                {
                    for (Requirement hostReq : versionEntry.getValue())
                    {
                        // Selecting the first fragment in each entry, which
                        // is equivalent to selecting the highest version of
                        // each fragment with a given symbolic name.
                        if (isFirst)
                        {
                            selectedFragments.add(hostReq.getResource());
                            isFirst = false;
                        }
                        // For any fragment that wasn't selected, remove the
                        // current host as a potential host for it and remove it
                        // as a dependent on the host. If there are no more
                        // potential hosts for the fragment, then mark it as
                        // unselected for later removal.
                        else
                        {
                            m_dependentMap.get(hostCap).remove(hostReq);
                            CandidateSelector hosts = removeCandidate(hostReq, hostCap);
                            if (hosts.isEmpty())
                            {
                                unselectedFragments.add(hostReq.getResource());
                            }
                        }
                    }
                }
            }

            // Step 2
            WrappedResource wrappedHost =
                new WrappedResource(hostCap.getResource(), selectedFragments);
            hostResources.add(wrappedHost);
            m_allWrappedHosts.put(hostCap.getResource(), wrappedHost);
        }

        // Step 3
        for (Resource fragment : unselectedFragments)
        {
            removeResource(fragment, new FragmentNotSelectedError(fragment));
        }

        // Step 4
        // First copy candidates for wrapped requirements to the host.
        for (WrappedResource hostResource : hostResources) {
            for (Requirement r : hostResource.getRequirements(null))
            {
                Requirement origReq = ((WrappedRequirement) r).getDeclaredRequirement();
                CandidateSelector cands = m_candidateMap.get(origReq);
                if (cands != null)
                {
                    if (cands instanceof ShadowList)
                    {
                        m_candidateMap.put(r, ShadowList.deepCopy((ShadowList) cands));
                    } else {
                        m_candidateMap.put(r, cands.copy());
                    }
                    for (Capability cand : cands.getRemainingCandidates())
                    {
                        Set<Requirement> dependents = m_dependentMap.get(cand);
                        dependents.remove(origReq);
                        dependents.add(r);
                    }
                }
            }
        }

        for (WrappedResource hostResource : hostResources)
        {
            // Replaces capabilities from fragments with the capabilities
            // from the merged host.
            for (Capability c : hostResource.getCapabilities(null))
            {
                // Don't replace the host capability, since the fragment will
                // really be attached to the original host, not the wrapper.
                if (!c.getNamespace().equals(HostNamespace.HOST_NAMESPACE))
                {
                    Capability origCap = ((HostedCapability) c).getDeclaredCapability();
                    // Note that you might think we could remove the original cap
                    // from the dependent map, but you can't since it may come from
                    // a fragment that is attached to multiple hosts, so each host
                    // will need to make their own copy.
                    CopyOnWriteSet<Requirement> dependents = m_dependentMap.get(origCap);
                    if (dependents != null)
                    {
                        dependents = new CopyOnWriteSet<Requirement>(dependents);
                        m_dependentMap.put(c, dependents);
                        for (Requirement r : dependents)
                        {
                            // We have synthesized hosted capabilities for all
                            // fragments that have been attached to hosts by
                            // wrapping the host bundle and their attached
                            // fragments. We need to use the ResolveContext to
                            // determine the proper priority order for hosted
                            // capabilities since the order may depend on the
                            // declaring host/fragment combination. However,
                            // internally we completely wrap the host revision
                            // and make all capabilities/requirements point back
                            // to the wrapped host not the declaring host. The
                            // ResolveContext expects HostedCapabilities to point
                            // to the declaring revision, so we need two separate
                            // candidate lists: one for the ResolveContext with
                            // HostedCapabilities pointing back to the declaring
                            // host and one for the resolver with HostedCapabilities
                            // pointing back to the wrapped host. We ask the
                            // ResolveContext to insert its appropriate HostedCapability
                            // into its list, then we mirror the insert into a
                            // shadow list with the resolver's HostedCapability.
                            // We only need to ask the ResolveContext to find
                            // the insert position for fragment caps since these
                            // were synthesized and we don't know their priority.
                            // However, in the resolver's candidate list we need
                            // to replace all caps with the wrapped caps, no
                            // matter if they come from the host or fragment,
                            // since we are completing replacing the declaring
                            // host and fragments with the wrapped host.
                            CandidateSelector cands = m_candidateMap.get(r);
                            ShadowList shadow;
                            if (!(cands instanceof ShadowList))
                            {
                                shadow = ShadowList.createShadowList(cands);
                                m_candidateMap.put(r, shadow);
                                cands = shadow;
                            }
                            else
                            {
                                shadow = (ShadowList) cands;
                            }

                            // If the original capability is from a fragment, then
                            // ask the ResolveContext to insert it and update the
                            // shadow copy of the list accordingly.
                            if (!origCap.getResource().equals(hostResource.getDeclaredResource()))
                            {
                                shadow.insertHostedCapability(
                                        m_session.getContext(),
                                        (HostedCapability) c,
                                        new SimpleHostedCapability(
                                                hostResource.getDeclaredResource(),
                                                origCap));
                            }
                            // If the original capability is from the host, then
                            // we just need to replace it in the shadow list.
                            else
                            {
                                shadow.replace(origCap, c);
                            }
                        }
                    }
                }
            }
        }

        // Lastly, verify that all mandatory revisions are still
        // populated, since some might have become unresolved after
        // selecting fragments/singletons.
        for (Resource resource : m_session.getMandatoryResources())
        {
            if (!isPopulated(resource))
            {
                return getResolutionError(resource);
            }
        }

        populateSubstitutables();

        m_candidateMap.trim();
        m_dependentMap.trim();

        // mark the selectors as unmodifiable now
        m_candidateSelectorsUnmodifiable.set(true);
        return null;
    }

    // Maps a host capability to a map containing its potential fragments;
    // the fragment map maps a fragment symbolic name to a map that maps
    // a version to a list of fragments requirements matching that symbolic
    // name and version.
    private Map<Capability, Map<String, Map<Version, List<Requirement>>>> getHostFragments()
    {
        Map<Capability, Map<String, Map<Version, List<Requirement>>>> hostFragments =
            new HashMap<Capability, Map<String, Map<Version, List<Requirement>>>>();
        for (Entry<Requirement, CandidateSelector> entry : m_candidateMap.fast())
        {
            Requirement req = entry.getKey();
            CandidateSelector caps = entry.getValue();
            for (Capability cap : caps.getRemainingCandidates())
            {
                // Keep track of hosts and associated fragments.
                if (req.getNamespace().equals(HostNamespace.HOST_NAMESPACE))
                {
                    String resSymName = Util.getSymbolicName(req.getResource());
                    Version resVersion = Util.getVersion(req.getResource());

                    Map<String, Map<Version, List<Requirement>>> fragments = hostFragments.get(cap);
                    if (fragments == null)
                    {
                        fragments = new HashMap<String, Map<Version, List<Requirement>>>();
                        hostFragments.put(cap, fragments);
                    }
                    Map<Version, List<Requirement>> fragmentVersions = fragments.get(resSymName);
                    if (fragmentVersions == null)
                    {
                        fragmentVersions =
                            new TreeMap<Version, List<Requirement>>(Collections.reverseOrder());
                        fragments.put(resSymName, fragmentVersions);
                    }
                    List<Requirement> actual = fragmentVersions.get(resVersion);
                    if (actual == null)
                    {
                        actual = new ArrayList<Requirement>();
                        if (resVersion == null)
                            resVersion = new Version(0, 0, 0);
                        fragmentVersions.put(resVersion, actual);
                    }
                    actual.add(req);
                }
            }
        }

        return hostFragments;
    }

    /**
     * Removes a module from the internal data structures if it wasn't selected
     * as a fragment or a singleton. This process may cause other modules to
     * become unresolved if they depended on the module's capabilities and there
     * is no other candidate.
     *
     * @param resource the module to remove.
     * @param ex the resolution error
     */
    private void removeResource(Resource resource, ResolutionError ex)
    {
        // Add removal reason to result cache.
        PopulateResult result = m_populateResultCache.get(resource);
        result.success = false;
        result.error = ex;
        // Remove from dependents.
        Set<Resource> unresolvedResources = new HashSet<Resource>();
        remove(resource, unresolvedResources);
        // Remove dependents that failed as a result of removing revision.
        while (!unresolvedResources.isEmpty())
        {
            Iterator<Resource> it = unresolvedResources.iterator();
            resource = it.next();
            it.remove();
            remove(resource, unresolvedResources);
        }
    }

    /**
     * Removes the specified module from the internal data structures, which
     * involves removing its requirements and its capabilities. This may cause
     * other modules to become unresolved as a result.
     *
     * @param resource the module to remove.
     * @param unresolvedResources a list to containing any additional modules
     * that that became unresolved as a result of removing this module and will
     * also need to be removed.
     */
    private void remove(Resource resource, Set<Resource> unresolvedResources)
    {
        for (Requirement r : resource.getRequirements(null))
        {
            remove(r);
        }

        for (Capability c : resource.getCapabilities(null))
        {
            remove(c, unresolvedResources);
        }
    }

    /**
     * Removes a requirement from the internal data structures.
     *
     * @param req the requirement to remove.
     */
    private void remove(Requirement req)
    {
        CandidateSelector candidates = m_candidateMap.remove(req);
        if (candidates != null)
        {
            for (Capability cap : candidates.getRemainingCandidates())
            {
                Set<Requirement> dependents = m_dependentMap.get(cap);
                if (dependents != null)
                {
                    dependents.remove(req);
                }
            }
        }
    }

    /**
     * Removes a capability from the internal data structures. This may cause
     * other modules to become unresolved as a result.
     *
     * @param c the capability to remove.
     * @param unresolvedResources a list to containing any additional modules
     * that that became unresolved as a result of removing this module and will
     * also need to be removed.
     */
    private void remove(Capability c, Set<Resource> unresolvedResources)
    {
        Set<Requirement> dependents = m_dependentMap.remove(c);
        if (dependents != null)
        {
            for (Requirement r : dependents)
            {
                CandidateSelector candidates = removeCandidate(r, c);
                if (candidates.isEmpty())
                {
                    m_candidateMap.remove(r);
                    if (!Util.isOptional(r))
                    {
                        PopulateResult result = m_populateResultCache.get(r.getResource());
                        if (result != null)
                        {
                            result.success = false;
                            result.error =
                                    new MissingRequirementError(r, m_populateResultCache.get(c.getResource()).error);
                        }
                        unresolvedResources.add(r.getResource());
                    }
                }
            }
        }
    }

    private CandidateSelector removeCandidate(Requirement req, Capability cap) {
        CandidateSelector candidates = m_candidateMap.get(req);
        candidates.remove(cap);
        return candidates;
    }

    /**
     * Creates a copy of the Candidates object. This is used for creating
     * permutations when package space conflicts are discovered.
     *
     * @return copy of this Candidates object.
     */
    public Candidates copy()
    {
        return new Candidates(
                m_session,
                m_candidateSelectorsUnmodifiable,
                m_dependentMap,
                m_candidateMap.deepClone(),
                m_allWrappedHosts,
                m_populateResultCache,
                m_subtitutableMap,
                m_delta.deepClone());
    }

    public void dump(ResolveContext rc)
    {
        // Create set of all revisions from requirements.
        Set<Resource> resources = new CopyOnWriteSet<Resource>();
        for (Entry<Requirement, CandidateSelector> entry
            : m_candidateMap.entrySet())
        {
            resources.add(entry.getKey().getResource());
        }
        // Now dump the revisions.
        System.out.println("=== BEGIN CANDIDATE MAP ===");
        for (Resource resource : resources)
        {
            Wiring wiring = rc.getWirings().get(resource);
            System.out.println("  " + resource
                + " (" + ((wiring != null) ? "RESOLVED)" : "UNRESOLVED)"));
            List<Requirement> reqs = (wiring != null)
                ? wiring.getResourceRequirements(null)
                : resource.getRequirements(null);
            for (Requirement req : reqs)
            {
                CandidateSelector candidates = m_candidateMap.get(req);
                if ((candidates != null) && (!candidates.isEmpty()))
                {
                    System.out.println("    " + req + ": " + candidates);
                }
            }
            reqs = (wiring != null)
                ? Util.getDynamicRequirements(wiring.getResourceRequirements(null))
                : Util.getDynamicRequirements(resource.getRequirements(null));
            for (Requirement req : reqs)
            {
                CandidateSelector candidates = m_candidateMap.get(req);
                if ((candidates != null) && (!candidates.isEmpty()))
                {
                    System.out.println("    " + req + ": " + candidates);
                }
            }
        }
        System.out.println("=== END CANDIDATE MAP ===");
    }

    public Candidates permutate(Requirement req)
    {
        if (!Util.isMultiple(req) && canRemoveCandidate(req))
        {
            Candidates perm = copy();
            perm.removeFirstCandidate(req);
            return perm;
        }
        return null;
    }

    public boolean canRemoveCandidate(Requirement req)
    {
        CandidateSelector candidates = m_candidateMap.get(req);
        if (candidates != null)
        {
            Capability current = candidates.getCurrentCandidate();
            if (current != null)
            {
                // IMPLEMENTATION NOTE:
                // Here we check for a req that is used for a substitutable export.
                // If we find a substitutable req then an extra check is done to see
                // if the substitutable capability is currently depended on as the
                // only provider of some other requirement.  If it is then we do not
                // allow the candidate to be removed.
                // This is done because of the way we attempt to reduce permutations
                // checked by permuting all used requirements that conflict with a
                // directly imported/required capability in one go.
                // If we allowed these types of substitutable requirements to move
                // to the next capability then the permutation would be thrown out
                // because it would cause some other resource to not resolve.
                // That in turn would throw out the complete permutation along with
                // any follow on permutations that could have resulted.
                // See ResolverImpl::checkPackageSpaceConsistency

                // Check if the current candidate is substitutable by the req;
                // This check is necessary here because of the way we traverse used blames
                // allows multiple requirements to be permuted in one Candidates
                if (req.equals(m_subtitutableMap.get(current)))
                {
                    // this is a substitute req,
                    // make sure there is not an existing dependency that would fail if we substitute
                    Set<Requirement> dependents = m_dependentMap.get(current);
                    if (dependents != null)
                    {
                        for (Requirement dependent : dependents)
                        {
                            CandidateSelector dependentSelector = m_candidateMap.get(
                                    dependent);
                            // If the dependent selector only has one capability left then check if
                            // the current candidate is the selector's current candidate.
                            if (dependentSelector != null
                                    && dependentSelector.getRemainingCandidateCount() <= 1)
                            {
                                if (current.equals(
                                        dependentSelector.getCurrentCandidate()))
                                {
                                    // return false since we do not want to allow this requirement
                                    // to substitute the capability
                                    return false;
                                }
                            }
                        }
                    }
                }
            }
            return candidates.getRemainingCandidateCount() > 1 || Util.isOptional(req);
        }
        return false;
    }

    static class DynamicImportFailed extends ResolutionError {

        private final Requirement requirement;

        public DynamicImportFailed(Requirement requirement) {
            this.requirement = requirement;
        }

        public String getMessage() {
            return "Dynamic import failed.";
        }

        public Collection<Requirement> getUnresolvedRequirements() {
            return Collections.singleton(requirement);
        }

        @Override
        public ResolutionException toException() {
            return new ReasonException(ReasonException.Reason.DynamicImport, getMessage(), null, getUnresolvedRequirements());
        }

    }

    static class FragmentNotSelectedError extends ResolutionError {

        private final Resource resource;

        public FragmentNotSelectedError(Resource resource) {
            this.resource = resource;
        }

        public String getMessage() {
            return "Fragment was not selected for attachment: " + resource;
        }

        @Override
        public Collection<Requirement> getUnresolvedRequirements() {
            return resource.getRequirements(HostNamespace.HOST_NAMESPACE);
        }

        @Override
        public ResolutionException toException() {
            return new ReasonException(ReasonException.Reason.FragmentNotSelected, getMessage(), null, getUnresolvedRequirements());
        }

    }

    static class MissingRequirementError extends ResolutionError {

        private final Requirement requirement;
        private final ResolutionError cause;

        public MissingRequirementError(Requirement requirement) {
            this(requirement, null);
        }

        public MissingRequirementError(Requirement requirement, ResolutionError cause) {
            this.requirement = requirement;
            this.cause = cause;
        }

        public String getMessage() {
            String msg = "Unable to resolve " + requirement.getResource()
                    + ": missing requirement " + requirement;
            if (cause != null)
            {
                msg = msg + " [caused by: " + cause.getMessage() + "]";
            }
            return msg;
        }

        public Collection<Requirement> getUnresolvedRequirements() {
            return Collections.singleton(requirement);
        }

        @Override
        public ResolutionException toException() {
            return new ReasonException(
                ReasonException.Reason.MissingRequirement, getMessage(), cause != null ? cause.toException() : null, getUnresolvedRequirements());
        }

    }

}