/*
 * 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 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.
/**
     * 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.
Returns:
the delta/**
     * 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.
Params:
req – the requirement to add.
candidates – the candidates matching the requirement./**
     * 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.
Params:
candidates – the bulk requirements and candidates to add./**
     * 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.
Params:
r – the resource whose wrapper is desired.
Returns:
the wrapper resource or the resource itself if it was not
wrapped./**
     * 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.
Params:
req – the requirement whose candidates are desired.
Returns:
the matching candidates or null./**
     * 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.
Returns:
 ResolutionError if the removal of any unselected fragments
result in the root module being unable to resolve./**
     * 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.
Params:
resource – the module to remove.
ex – the resolution error/**
     * 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.
Params:
resource – the module to remove.
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./**
     * 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.
Params:
req – the requirement to remove./**
     * 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.
Params:
c – the capability to remove.
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./**
     * 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.
Returns:
copy of this Candidates object./**
     * 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());
        }

    }

}