001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one
003     * or more contributor license agreements.  See the NOTICE file
004     * distributed with this work for additional information
005     * regarding copyright ownership.  The ASF licenses this file
006     * to you under the Apache License, Version 2.0 (the
007     * "License"); you may not use this file except in compliance
008     * with the License.  You may obtain a copy of the License at
009     *
010     *   http://www.apache.org/licenses/LICENSE-2.0
011     *
012     * Unless required by applicable law or agreed to in writing,
013     * software distributed under the License is distributed on an
014     * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015     * KIND, either express or implied.  See the License for the
016     * specific language governing permissions and limitations
017     * under the License.
018     */
019    package org.apache.felix.framework.searchpolicy;
020    
021    import java.util.ArrayList;
022    import java.util.Arrays;
023    import java.util.Collections;
024    import java.util.Comparator;
025    import java.util.HashMap;
026    import java.util.HashSet;
027    import java.util.Iterator;
028    import java.util.List;
029    import java.util.Map;
030    import java.util.Set;
031    import java.util.StringTokenizer;
032    import org.apache.felix.framework.Logger;
033    import org.apache.felix.framework.util.Util;
034    import org.apache.felix.framework.util.manifestparser.Capability;
035    import org.apache.felix.framework.util.manifestparser.R4Attribute;
036    import org.apache.felix.framework.util.manifestparser.R4Directive;
037    import org.apache.felix.framework.util.manifestparser.R4Library;
038    import org.apache.felix.framework.util.manifestparser.Requirement;
039    import org.apache.felix.moduleloader.ICapability;
040    import org.apache.felix.moduleloader.IModule;
041    import org.apache.felix.moduleloader.IRequirement;
042    import org.apache.felix.moduleloader.IWire;
043    import org.osgi.framework.Constants;
044    
045    public class Resolver
046    {
047        private final Logger m_logger;
048    
049        // Execution environment.
050        private final String m_fwkExecEnvStr;
051        private final Set m_fwkExecEnvSet;
052    
053        // Reusable empty array.
054        private static final IWire[] m_emptyWires = new IWire[0];
055    
056        public Resolver(Logger logger, String fwkExecEnvStr)
057        {
058            m_logger = logger;
059            m_fwkExecEnvStr = (fwkExecEnvStr != null) ? fwkExecEnvStr.trim() : null;
060            m_fwkExecEnvSet = parseExecutionEnvironments(fwkExecEnvStr);
061        }
062    
063        // Returns a map of resolved bundles where the key is the module
064        // and the value is an array of wires.
065        public Map resolve(ResolverState state, IModule rootModule) throws ResolveException
066        {
067            // If the module is already resolved, then we can just return.
068            if (rootModule.isResolved())
069            {
070                return null;
071            }
072    
073            // This variable maps an unresolved module to a list of candidate
074            // sets, where there is one candidate set for each requirement that
075            // must be resolved. A candidate set contains the potential canidates
076            // available to resolve the requirement and the currently selected
077            // candidate index.
078            Map candidatesMap = new HashMap();
079    
080            // The first step is to populate the candidates map. This
081            // will use the target module to populate the candidates map
082            // with all potential modules that need to be resolved as a
083            // result of resolving the target module. The key of the
084            // map is a potential module to be resolved and the value is
085            // a list of candidate sets, one for each of the module's
086            // requirements, where each candidate set contains the potential
087            // candidates for resolving the requirement. Not all modules in
088            // this map will be resolved, only the target module and
089            // any candidates selected to resolve its requirements and the
090            // transitive requirements this implies.
091            populateCandidatesMap(state, candidatesMap, rootModule);
092    
093            // The next step is to use the candidates map to determine if
094            // the class space for the root module is consistent. This
095            // is an iterative process that transitively walks the "uses"
096            // relationships of all packages visible from the root module
097            // checking for conflicts. If a conflict is found, it "increments"
098            // the configuration of currently selected potential candidates
099            // and tests them again. If this method returns, then it has found
100            // a consistent set of candidates; otherwise, a resolve exception
101            // is thrown if it exhausts all possible combinations and could
102            // not find a consistent class space.
103            findConsistentClassSpace(state, candidatesMap, rootModule);
104    
105            // The final step is to create the wires for the root module and
106            // transitively all modules that are to be resolved from the
107            // selected candidates for resolving the root module's imports.
108            // When this call returns, each module's wiring and resolved
109            // attributes are set. The resulting wiring map is used below
110            // to fire resolved events outside of the synchronized block.
111            // The resolved module wire map maps a module to its array of
112            // wires.
113            return populateWireMap(state, candidatesMap, rootModule, new HashMap());
114        }
115    
116        // TODO: RESOLVER - Fix this return type.
117        // Return candidate wire in result[0] and wire map in result[1]
118        public Object[] resolveDynamicImport(ResolverState state, IModule importer, String pkgName)
119            throws ResolveException
120        {
121            ICapability candidate = null;
122            Map resolvedModuleWireMap = null;
123    
124            // We can only create a dynamic import if the following
125            // conditions are met:
126            // 1. The package in question is not already imported.
127            // 2. The package in question is not accessible via require-bundle.
128            // 3. The package in question is not exported by the bundle.
129            // 4. The package in question matches a dynamic import of the bundle.
130            // The following call checks all of these conditions and returns
131            // a matching dynamic requirement if possible.
132            IRequirement dynReq = findAllowedDynamicImport(importer, pkgName);
133            if (dynReq != null)
134            {
135                // Create a new requirement based on the dynamic requirement,
136                // but substitute the precise package name for which we are
137                // looking, because it is not possible to use the potentially
138                // wildcarded version in the dynamic requirement.
139                R4Directive[] dirs = ((Requirement) dynReq).getDirectives();
140                R4Attribute[] attrs = ((Requirement) dynReq).getAttributes();
141                R4Attribute[] newAttrs = new R4Attribute[attrs.length];
142                System.arraycopy(attrs, 0, newAttrs, 0, attrs.length);
143                for (int attrIdx = 0; attrIdx < newAttrs.length; attrIdx++)
144                {
145                    if (newAttrs[attrIdx].getName().equals(ICapability.PACKAGE_PROPERTY))
146                    {
147                        newAttrs[attrIdx] = new R4Attribute(
148                            ICapability.PACKAGE_PROPERTY, pkgName, false);
149                        break;
150                    }
151                }
152                IRequirement target = new Requirement(ICapability.PACKAGE_NAMESPACE, dirs, newAttrs);
153    
154                // See if there is a candidate exporter that satisfies the
155                // constrained dynamic requirement.
156                try
157                {
158                    // Get "resolved" and "unresolved" candidates and put
159                    // the "resolved" candidates first.
160                    List candidates = state.getResolvedCandidates(target, importer);
161                    candidates.addAll(state.getUnresolvedCandidates(target, importer));
162    
163                    // Take the first candidate that can resolve.
164                    for (int candIdx = 0;
165                        (candidate == null) && (candIdx < candidates.size());
166                        candIdx++)
167                    {
168                        try
169                        {
170                            // If a map is returned, then the candidate resolved
171                            // consistently with the importer.
172                            resolvedModuleWireMap =
173                                resolveDynamicImportCandidate(
174                                    state, ((ICapability) candidates.get(candIdx)).getModule(),
175                                    importer);
176                            if (resolvedModuleWireMap != null)
177                            {
178                                candidate = (ICapability) candidates.get(candIdx);
179                            }
180                        }
181                        catch (ResolveException ex)
182                        {
183                            // Ignore candidates that cannot resolve.
184                        }
185                    }
186    
187                    if (candidate != null)
188                    {
189                        // Create the wire and add it to the module.
190                        Object[] result = new Object[2];
191                        result[0] = new R4Wire(
192                            importer, dynReq, candidate.getModule(),
193                            candidate);
194                        result[1] = resolvedModuleWireMap;
195                        return result;
196                    }
197                }
198                catch (Exception ex)
199                {
200                    m_logger.log(Logger.LOG_ERROR, "Unable to dynamically import package.", ex);
201                }
202            }
203    
204            return null;
205        }
206    
207        public static IRequirement findAllowedDynamicImport(IModule importer, String pkgName)
208        {
209            // We cannot import the default package, so return null in that case.
210            if (pkgName.length() == 0)
211            {
212                return null;
213            }
214    
215            // If any of the module exports this package, then we cannot
216            // attempt to dynamically import it.
217            ICapability[] caps = importer.getCapabilities();
218            for (int i = 0; (caps != null) && (i < caps.length); i++)
219            {
220                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE)
221                    && caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY).equals(pkgName))
222                {
223                    return null;
224                }
225            }
226            // If any of our wires have this package, then we cannot
227            // attempt to dynamically import it.
228            IWire[] wires = importer.getWires();
229            for (int i = 0; (wires != null) && (i < wires.length); i++)
230            {
231                if (wires[i].hasPackage(pkgName))
232                {
233                    return null;
234                }
235            }
236    
237            // Loop through the importer's dynamic requirements to determine if
238            // there is a matching one for the package from which we want to
239            // load a class.
240            IRequirement[] dynamics = importer.getDynamicRequirements();
241            for (int dynIdx = 0;
242                (dynamics != null) && (dynIdx < dynamics.length);
243                dynIdx++)
244            {
245                // First check to see if the dynamic requirement matches the
246                // package name; this means we have to do wildcard matching.
247                String dynPkgName = ((Requirement) dynamics[dynIdx]).getTargetName();
248                boolean wildcard = (dynPkgName.lastIndexOf(".*") >= 0);
249                // Remove the "*", but keep the "." if wildcarded.
250                dynPkgName = (wildcard)
251                    ? dynPkgName.substring(0, dynPkgName.length() - 1) : dynPkgName;
252                // If the dynamic requirement matches the package name, then
253                // create a new requirement for the specific package.
254                if (dynPkgName.equals("*") ||
255                    pkgName.equals(dynPkgName) ||
256                    (wildcard && pkgName.startsWith(dynPkgName)))
257                {
258                    return dynamics[dynIdx];
259                }
260            }
261    
262            return null;
263        }
264    
265        private Map resolveDynamicImportCandidate(
266            ResolverState state, IModule provider, IModule importer)
267            throws ResolveException
268        {
269            // If the provider of the dynamically imported package is not
270            // resolved, then we need to calculate the candidates to resolve
271            // it and see if there is a consistent class space for the
272            // provider. If there is no consistent class space, then a resolve
273            // exception is thrown.
274            Map candidatesMap = new HashMap();
275            if (!provider.isResolved())
276            {
277                populateCandidatesMap(state, candidatesMap, provider);
278                findConsistentClassSpace(state, candidatesMap, provider);
279            }
280    
281            // If the provider can be successfully resolved, then verify that
282            // its class space is consistent with the existing class space of the
283            // module that instigated the dynamic import.
284            Map moduleMap = new HashMap();
285            Map importerPkgMap = getModulePackages(moduleMap, importer, candidatesMap);
286    
287            // Now we need to calculate the "uses" constraints of every package
288            // accessible to the provider module based on its current candidates.
289            Map usesMap = calculateUsesConstraints(provider, moduleMap, candidatesMap);
290    
291            // Verify that none of the provider's implied "uses" constraints
292            // in the uses map conflict with anything in the importing module's
293            // package map.
294            for (Iterator iter = usesMap.entrySet().iterator(); iter.hasNext(); )
295            {
296                Map.Entry entry = (Map.Entry) iter.next();
297    
298                // For the given "used" package, get that package from the
299                // importing module's package map, if present.
300                ResolvedPackage rp = (ResolvedPackage) importerPkgMap.get(entry.getKey());
301    
302                // If the "used" package is also visible to the importing
303                // module, make sure there is no conflicts in the implied
304                // "uses" constraints.
305                if (rp != null)
306                {
307                    // Clone the resolve package so we can modify it.
308                    rp = (ResolvedPackage) rp.clone();
309    
310                    // Loop through all implied "uses" constraints for the current
311                    // "used" package and verify that all packages are
312                    // compatible with the packages of the importing module's
313                    // package map.
314                    List constraintList = (List) entry.getValue();
315                    for (int constIdx = 0; constIdx < constraintList.size(); constIdx++)
316                    {
317                        // Get a specific "uses" constraint for the current "used"
318                        // package.
319                        ResolvedPackage rpUses = (ResolvedPackage) constraintList.get(constIdx);
320                        // Determine if the implied "uses" constraint is compatible with
321                        // the improting module's packages for the given "used"
322                        // package. They are compatible if one is the subset of the other.
323                        // Retain the union of the two sets if they are compatible.
324                        if (rpUses.isSubset(rp))
325                        {
326                            // Do nothing because we already have the superset.
327                        }
328                        else if (rp.isSubset(rpUses))
329                        {
330                            // Keep the superset, i.e., the union.
331                            rp.m_capList.clear();
332                            rp.m_capList.addAll(rpUses.m_capList);
333                        }
334                        else
335                        {
336                            m_logger.log(
337                                Logger.LOG_DEBUG,
338                                "Constraint violation for " + importer
339                                + " detected; module can see "
340                                + rp + " and " + rpUses);
341                            return null;
342                        }
343                    }
344                }
345            }
346    
347            return populateWireMap(state, candidatesMap, provider, new HashMap());
348        }
349    
350        private void populateCandidatesMap(
351            ResolverState state, Map candidatesMap, IModule targetModule)
352            throws ResolveException
353        {
354            // Detect cycles.
355            if (candidatesMap.containsKey(targetModule))
356            {
357                return;
358            }
359    
360            // Verify that any required execution environment is satisfied.
361            verifyExecutionEnvironment(m_fwkExecEnvStr, m_fwkExecEnvSet, targetModule);
362    
363            // Verify that any native libraries match the current platform.
364            verifyNativeLibraries(targetModule);
365    
366            // Finally, resolve any dependencies the module may have.
367    
368            // Add target module to the candidates map so we can detect cycles.
369            candidatesMap.put(targetModule, null);
370    
371            // Create list to hold the resolving candidate sets for the target
372            // module's requirements.
373            List candSetList = new ArrayList();
374    
375            // Loop through each requirement and calculate its resolving
376            // set of candidates.
377            IRequirement[] reqs = targetModule.getRequirements();
378            for (int reqIdx = 0; (reqs != null) && (reqIdx < reqs.length); reqIdx++)
379            {
380                // Get the candidates from the "resolved" and "unresolved"
381                // package maps. The "resolved" candidates have higher priority
382                // than "unresolved" ones, so put the "resolved" candidates
383                // at the front of the list of candidates.
384                List candidates = state.getResolvedCandidates(reqs[reqIdx], targetModule);
385                candidates.addAll(state.getUnresolvedCandidates(reqs[reqIdx], targetModule));
386    
387                // If we have candidates, then we need to recursively populate
388                // the resolver map with each of them.
389                ResolveException rethrow = null;
390                if (candidates.size() > 0)
391                {
392                    for (Iterator it = candidates.iterator(); it.hasNext(); )
393                    {
394                        ICapability candidate = (ICapability) it.next();
395    
396                        try
397                        {
398                            // Only populate the resolver map with modules that
399                            // are not already resolved.
400                            if (!candidate.getModule().isResolved())
401                            {
402                                populateCandidatesMap(
403                                    state, candidatesMap, candidate.getModule());
404                            }
405                        }
406                        catch (ResolveException ex)
407                        {
408                            // If we received a resolve exception, then the
409                            // current candidate is not resolvable for some
410                            // reason and should be removed from the list of
411                            // candidates. For now, just null it.
412                            it.remove();
413                            rethrow = ex;
414                        }
415                    }
416                }
417    
418                // If no candidates exist at this point, then throw a
419                // resolve exception unless the import is optional.
420                if ((candidates.size() == 0) && !reqs[reqIdx].isOptional())
421                {
422                    // Remove invalid candidate and any cycle byproduct resolved modules.
423                    removeInvalidCandidate(targetModule, candidatesMap, new ArrayList());
424    
425                    // If we have received an exception while trying to populate
426                    // the candidates map, rethrow that exception since it might
427                    // be useful. NOTE: This is not necessarily the "only"
428                    // correct exception, since it is possible that multiple
429                    // candidates were not resolvable, but it is better than
430                    // nothing.
431                    if (rethrow != null)
432                    {
433                        throw rethrow;
434                    }
435                    else
436                    {
437                        throw new ResolveException(
438                            "Unable to resolve.", targetModule, reqs[reqIdx]);
439                    }
440                }
441                else if (candidates.size() > 0)
442                {
443                    candSetList.add(
444                        new CandidateSet(targetModule, reqs[reqIdx], candidates));
445                }
446            }
447    
448            // Now that the module's candidates have been calculated, add the
449            // candidate set list to the candidates map to be used for calculating
450            // uses constraints and ultimately wires.
451            candidatesMap.put(targetModule, candSetList);
452        }
453    
454        private static void removeInvalidCandidate(
455            IModule invalidModule, Map candidatesMap, List invalidList)
456        {
457    // TODO: PERFORMANCE - This could be quicker if we kept track of who depended on whom,
458    //       or only those modules used as candidates or those in a cycle.
459    
460            // Remove the invalid module's  candidates set list from the candidates map,
461            // since it should only contain entries for validly resolved modules.
462            candidatesMap.remove(invalidModule);
463    
464            // Loop through each candidate set list in the candidates map to try
465            // to find references to the invalid module.
466            for (Iterator itCandidatesMap = candidatesMap.entrySet().iterator();
467                itCandidatesMap.hasNext(); )
468            {
469                Map.Entry entry = (Map.Entry) itCandidatesMap.next();
470                IModule module = (IModule) entry.getKey();
471                List candSetList = (List) entry.getValue();
472                if (candSetList != null)
473                {
474                    // Loop through each candidate set in the candidate set list
475                    // to search for the invalid module.
476                    for (Iterator itCandSetList = candSetList.iterator(); itCandSetList.hasNext(); )
477                    {
478                        // Loop through the candidate in the candidate set and remove
479                        // the invalid module if it is found.
480                        CandidateSet cs = (CandidateSet) itCandSetList.next();
481                        for (Iterator itCandidates = cs.m_candidates.iterator();
482                            itCandidates.hasNext(); )
483                        {
484                            // If the invalid module is a candidate, then remove it from
485                            // the candidate set.
486                            ICapability candCap = (ICapability) itCandidates.next();
487                            if (candCap.getModule().equals(invalidModule))
488                            {
489                                itCandidates.remove();
490    
491                                // If there are no more candidates in the candidate set, then
492                                // remove it from the candidate set list.
493                                if (cs.m_candidates.size() == 0)
494                                {
495                                    itCandSetList.remove();
496    
497                                    // If the requirement is not optional, then add the module
498                                    // to a list which will be removed after removing the current
499                                    // invalid module.
500                                    if (!cs.m_requirement.isOptional() && (module != invalidModule)
501                                        && !invalidList.contains(module))
502                                    {
503                                        invalidList.add(module);
504                                    }
505                                }
506                                break;
507                            }
508                        }
509                    }
510                }
511            }
512    
513            if (!invalidList.isEmpty())
514            {
515                while (!invalidList.isEmpty())
516                {
517                    IModule m = (IModule) invalidList.remove(0);
518                    removeInvalidCandidate(m, candidatesMap, invalidList);
519                }
520            }
521        }
522    
523        // This flag indicates whether candidates have been rotated due to a
524        // "uses" constraint conflict. If so, then it is not necessary to perform
525        // a permutation, since rotating the candidates selected a new permutation.
526        // This part of an attempt to perform smarter permutations.
527        private boolean m_candidatesRotated = false;
528    
529        private void findConsistentClassSpace(
530            ResolverState state, Map candidatesMap, IModule rootModule)
531            throws ResolveException
532        {
533            List candidatesList = null;
534    
535            // The reusable module map maps a module to a map of
536            // resolved packages that are accessible by the given
537            // module. The set of resolved packages is calculated
538            // from the current candidates of the candidates map
539            // and the module's metadata.
540            Map moduleMap = new HashMap();
541    
542            // Reusable map used to test for cycles.
543            Map cycleMap = new HashMap();
544    
545            // Test the current potential candidates to determine if they
546            // are consistent. Keep looping until we find a consistent
547            // set or an exception is thrown.
548            while (!isSingletonConsistent(state, rootModule, moduleMap, candidatesMap) ||
549                !isClassSpaceConsistent(rootModule, moduleMap, cycleMap, candidatesMap))
550            {
551                // The incrementCandidateConfiguration() method requires
552                // ordered access to the candidates map, so we will create
553                // a reusable list once right here.
554                if (candidatesList == null)
555                {
556                    candidatesList = new ArrayList();
557                    for (Iterator iter = candidatesMap.entrySet().iterator();
558                        iter.hasNext(); )
559                    {
560                        Map.Entry entry = (Map.Entry) iter.next();
561                        candidatesList.add(entry.getValue());
562                    }
563    
564                    // Sort the bundles candidate sets according to a weighting
565                    // based on how many multi-candidate requirements each has.
566                    // The idea is to push bundles with more potential candidate
567                    // permutations to the front so we can permutate over them
568                    // more quickly, since they are likely to have more issues.
569                    Collections.sort(candidatesList, new Comparator() {
570                        public int compare(Object o1, Object o2)
571                        {
572                            int w1 = calculateWeight((List) o1);
573                            int w2 = calculateWeight((List) o2);
574                            if (w1 < w2)
575                            {
576                                return -1;
577                            }
578                            else if (w1 > w2)
579                            {
580                                return 1;
581                            }
582                            return 0;
583                        }
584    
585                        private int calculateWeight(List candSetList)
586                        {
587                            int weight = 0;
588                            for (int csIdx = 0; csIdx < candSetList.size(); csIdx++)
589                            {
590                                CandidateSet cs = (CandidateSet) candSetList.get(csIdx);
591                                if ((cs.m_candidates != null) && (cs.m_candidates.size() > 1))
592                                {
593                                    weight += cs.m_candidates.size();
594                                }
595                            }
596                            return -weight;
597                        }
598                    });
599                }
600    
601                // Increment the candidate configuration to a new permutation so
602                // we can test again, unless some candidates have been rotated.
603                // In that case, we re-test the current permutation, since rotating
604                // the candidates effectively selects a new permutation.
605                if (!m_candidatesRotated)
606                {
607                    incrementCandidateConfiguration(candidatesList);
608                }
609                else
610                {
611                    m_candidatesRotated = false;
612                }
613    
614                // Clear the module map.
615                moduleMap.clear();
616    
617                // Clear the cycle map.
618                cycleMap.clear();
619            }
620        }
621    
622        /**
623         * This methd checks to see if the target module and any of the candidate
624         * modules to resolve its dependencies violate any singleton constraints.
625         * Actually, it just creates a map of resolved singleton modules and then
626         * delegates all checking to another recursive method.
627         *
628         * @param targetModule the module that is the root of the tree of modules to check.
629         * @param moduleMap a map to cache the package space of each module.
630         * @param candidatesMap a map containing the all candidates to resolve all
631         *        dependencies for all modules.
632         * @return <tt>true</tt> if all candidates are consistent with respect to singletons,
633         *         <tt>false</tt> otherwise.
634        **/
635        private boolean isSingletonConsistent(
636            ResolverState state, IModule targetModule, Map moduleMap, Map candidatesMap)
637        {
638            // Create a map of all resolved singleton modules.
639            Map singletonMap = new HashMap();
640            IModule[] modules = state.getModules();
641            for (int i = 0; (modules != null) && (i < modules.length); i++)
642            {
643                if (modules[i].isResolved() && isSingleton(modules[i]))
644                {
645                    String symName = modules[i].getSymbolicName();
646                    singletonMap.put(symName, symName);
647                }
648            }
649    
650            return areCandidatesSingletonConsistent(
651                state, targetModule, singletonMap, moduleMap, new HashMap(), candidatesMap);
652        }
653    
654        /**
655         * This method recursive checks the target module and all of its transitive
656         * dependency modules to verify that they do not violate a singleton constraint.
657         * If the target module is a singleton, then it checks that againts existing
658         * singletons. Then it checks all current unresolved candidates recursively.
659         *
660         * @param targetModule the module that is the root of the tree of modules to check.
661         * @param singletonMap the current map of singleton symbolic names.
662         * @param moduleMap a map to cache the package space of each module.
663         * @param cycleMap a map to detect cycles.
664         * @param candidatesMap a map containing the all candidates to resolve all
665         *        dependencies for all modules.
666         * @return <tt>true</tt> if all candidates are consistent with respect to singletons,
667         *         <tt>false</tt> otherwise.
668        **/
669        private boolean areCandidatesSingletonConsistent(
670            ResolverState state, IModule targetModule,
671            Map singletonMap, Map moduleMap, Map cycleMap, Map candidatesMap)
672        {
673            // If we are in a cycle, then assume true for now.
674            if (cycleMap.get(targetModule) != null)
675            {
676                return true;
677            }
678    
679            // Record the target module in the cycle map.
680            cycleMap.put(targetModule, targetModule);
681    
682            // Check to see if the targetModule violates a singleton.
683            // If not and it is a singleton, then add it to the singleton
684            // map since it will constrain other singletons.
685            String symName = targetModule.getSymbolicName();
686            boolean isSingleton = isSingleton(targetModule);
687            if (isSingleton && singletonMap.containsKey(symName))
688            {
689                return false;
690            }
691            else if (isSingleton)
692            {
693                singletonMap.put(symName, symName);
694            }
695    
696            // Get the package space of the target module.
697            Map pkgMap = null;
698            try
699            {
700                pkgMap = getModulePackages(moduleMap, targetModule, candidatesMap);
701            }
702            catch (ResolveException ex)
703            {
704                m_logger.log(
705                    Logger.LOG_DEBUG,
706                    "Constraint violation for " + targetModule + " detected.",
707                    ex);
708                return false;
709            }
710    
711            // Loop through all of the target module's accessible packages and
712            // verify that all packages are consistent.
713            for (Iterator iter = pkgMap.entrySet().iterator(); iter.hasNext(); )
714            {
715                Map.Entry entry = (Map.Entry) iter.next();
716                // Get the resolved package, which contains the set of all
717                // packages for the given package.
718                ResolvedPackage rp = (ResolvedPackage) entry.getValue();
719                // Loop through each capability and test if it is consistent.
720                for (int capIdx = 0; capIdx < rp.m_capList.size(); capIdx++)
721                {
722                    // If the module for this capability is not resolved, then
723                    // we have to see if resolving it would violate a singleton
724                    // constraint.
725                    ICapability cap = (ICapability) rp.m_capList.get(capIdx);
726                    if (!cap.getModule().isResolved())
727                    {
728                        return areCandidatesSingletonConsistent(
729                            state, cap.getModule(), singletonMap, moduleMap, cycleMap, candidatesMap);
730                    }
731                }
732            }
733    
734            return true;
735        }
736    
737        /**
738         * Returns true if the specified module is a singleton
739         * (i.e., directive singleton:=true in Bundle-SymbolicName).
740         *
741         * @param module the module to check for singleton status.
742         * @return true if the module is a singleton, false otherwise.
743        **/
744        private static boolean isSingleton(IModule module)
745        {
746            final ICapability[] modCaps = Util.getCapabilityByNamespace(
747                    module, Capability.MODULE_NAMESPACE);
748            if (modCaps == null || modCaps.length == 0)
749            {
750                // this should never happen?
751                return false;
752            }
753            final R4Directive[] dirs = ((Capability) modCaps[0]).getDirectives();
754            for (int dirIdx = 0; (dirs != null) && (dirIdx < dirs.length); dirIdx++)
755            {
756                if (dirs[dirIdx].getName().equalsIgnoreCase(Constants.SINGLETON_DIRECTIVE)
757                    && Boolean.valueOf(dirs[dirIdx].getValue()).booleanValue())
758                {
759                    return true;
760                }
761            }
762            return false;
763        }
764    
765        private boolean isClassSpaceConsistent(
766            IModule targetModule, Map moduleMap, Map cycleMap, Map candidatesMap)
767        {
768    //System.out.println("isClassSpaceConsistent("+targetModule+")");
769            // If we are in a cycle, then assume true for now.
770            if (cycleMap.get(targetModule) != null)
771            {
772                return true;
773            }
774    
775            // Record the target module in the cycle map.
776            cycleMap.put(targetModule, targetModule);
777    
778            // Get the package map for the target module, which is a
779            // map of all packages accessible to the module and their
780            // associated capabilities.
781            Map pkgMap = null;
782            try
783            {
784                pkgMap = getModulePackages(moduleMap, targetModule, candidatesMap);
785            }
786            catch (ResolveException ex)
787            {
788                m_logger.log(
789                    Logger.LOG_DEBUG,
790                    "Constraint violation for " + targetModule + " detected.",
791                    ex);
792                return false;
793            }
794    
795            // Loop through all of the target module's accessible packages and
796            // verify that all packages are consistent.
797            for (Iterator iter = pkgMap.entrySet().iterator(); iter.hasNext(); )
798            {
799                Map.Entry entry = (Map.Entry) iter.next();
800                // Get the resolved package, which contains the set of all
801                // capabilities for the given package.
802                ResolvedPackage rp = (ResolvedPackage) entry.getValue();
803                // Loop through each capability and test if it is consistent.
804                for (int capIdx = 0; capIdx < rp.m_capList.size(); capIdx++)
805                {
806                    ICapability cap = (ICapability) rp.m_capList.get(capIdx);
807                    if (!isClassSpaceConsistent(cap.getModule(), moduleMap, cycleMap, candidatesMap))
808                    {
809                        return false;
810                    }
811                }
812            }
813    
814            // Now we need to calculate the "uses" constraints of every package
815            // accessible to the target module based on the current candidates.
816            Map usesMap = null;
817            try
818            {
819                usesMap = calculateUsesConstraints(targetModule, moduleMap, candidatesMap);
820            }
821            catch (ResolveException ex)
822            {
823                m_logger.log(
824                    Logger.LOG_DEBUG,
825                    "Constraint violation for " + targetModule + " detected.",
826                    ex);
827                return false;
828            }
829    
830            // Verify that none of the implied "uses" constraints in the uses map
831            // conflict with anything in the target module's package map.
832            for (Iterator iter = usesMap.entrySet().iterator(); iter.hasNext(); )
833            {
834                Map.Entry entry = (Map.Entry) iter.next();
835    
836                // For the given "used" package, get that package from the
837                // target module's package map, if present.
838                ResolvedPackage rp = (ResolvedPackage) pkgMap.get(entry.getKey());
839    
840                // If the "used" package is also visible to the target module,
841                // make sure there is no conflicts in the implied "uses"
842                // constraints.
843                if (rp != null)
844                {
845                    // Clone the resolve package so we can modify it.
846                    rp = (ResolvedPackage) rp.clone();
847    
848                    // Loop through all implied "uses" constraints for the current
849                    // "used" package and verify that all packages are
850                    // compatible with the packages of the root module's
851                    // package map.
852                    List constraintList = (List) entry.getValue();
853                    for (int constIdx = 0; constIdx < constraintList.size(); constIdx++)
854                    {
855                        // Get a specific "uses" constraint for the current "used"
856                        // package.
857                        ResolvedPackage rpUses = (ResolvedPackage) constraintList.get(constIdx);
858                        // Determine if the implied "uses" constraint is compatible with
859                        // the target module's packages for the given "used"
860                        // package. They are compatible if one is the subset of the other.
861                        // Retain the union of the two sets if they are compatible.
862                        if (rpUses.isSubset(rp))
863                        {
864                            // Do nothing because we already have the superset.
865                        }
866                        else if (rp.isSubset(rpUses))
867                        {
868                            // Keep the superset, i.e., the union.
869                            rp.m_capList.clear();
870                            rp.m_capList.addAll(rpUses.m_capList);
871                        }
872                        else
873                        {
874                            m_logger.log(
875                                Logger.LOG_DEBUG,
876                                "Constraint violation for " + targetModule
877                                + " detected; module can see "
878                                + rp + " and " + rpUses);
879    
880                            // If the resolved package has a candidate set, then
881                            // attempt to directly rotate the candidates to fix the
882                            // "uses" constraint conflict. The idea is rather than
883                            // blinding incrementing to the next permutation, we will
884                            // try to target the permutation to the bundle with a
885                            // conflict, which in some cases will be smarter. Only
886                            // rotate the candidates if we have more than one and we
887                            // haven't already rotated them completely.
888                            if ((rp.m_cs != null) && (rp.m_cs.m_candidates.size() > 1)
889                                && (rp.m_cs.m_rotated < rp.m_cs.m_candidates.size()))
890                            {
891                                // Rotate candidates.
892                                ICapability first = (ICapability) rp.m_cs.m_candidates.get(0);
893                                for (int i = 1; i < rp.m_cs.m_candidates.size(); i++)
894                                {
895                                    rp.m_cs.m_candidates.set(i - 1, rp.m_cs.m_candidates.get(i));
896                                }
897                                rp.m_cs.m_candidates.set(rp.m_cs.m_candidates.size() - 1, first);
898                                rp.m_cs.m_rotated++;
899                                m_candidatesRotated = true;
900                            }
901    
902                            return false;
903                        }
904                    }
905                }
906            }
907    
908            return true;
909        }
910    
911        private static Map calculateUsesConstraints(
912            IModule targetModule, Map moduleMap, Map candidatesMap)
913            throws ResolveException
914        {
915    //System.out.println("calculateUsesConstraints("+targetModule+")");
916            // Map to store calculated uses constraints. This maps a
917            // package name to a list of resolved packages, where each
918            // resolved package represents a constraint on anyone
919            // importing the given package name. This map is returned
920            // by this method.
921            Map usesMap = new HashMap();
922    
923            // Re-usable map to detect cycles.
924            Map cycleMap = new HashMap();
925    
926            // Get all packages accessible by the target module.
927            Map pkgMap = getModulePackages(moduleMap, targetModule, candidatesMap);
928    
929            // Each package accessible from the target module is potentially
930            // comprised of one or more capabilities. The "uses" constraints
931            // implied by all capabilities must be calculated and combined to
932            // determine the complete set of implied "uses" constraints for
933            // each package accessible by the target module.
934            for (Iterator iter = pkgMap.entrySet().iterator(); iter.hasNext(); )
935            {
936                Map.Entry entry = (Map.Entry) iter.next();
937                ResolvedPackage rp = (ResolvedPackage) entry.getValue();
938                for (int capIdx = 0; capIdx < rp.m_capList.size(); capIdx++)
939                {
940                    usesMap = calculateUsesConstraints(
941                        (ICapability) rp.m_capList.get(capIdx),
942                        moduleMap, usesMap, cycleMap, candidatesMap);
943                }
944            }
945            return usesMap;
946        }
947    
948        private static Map calculateUsesConstraints(
949            ICapability capTarget, Map moduleMap, Map usesMap,
950            Map cycleMap, Map candidatesMap)
951            throws ResolveException
952        {
953    //System.out.println("calculateUsesConstraints2("+psTarget.m_module+")");
954            // If we are in a cycle, then return for now.
955            if (cycleMap.get(capTarget) != null)
956            {
957                return usesMap;
958            }
959    
960            // Record the target capability in the cycle map.
961            cycleMap.put(capTarget, capTarget);
962    
963            // Get all packages accessible from the module of the
964            // target capability.
965            Map pkgMap = getModulePackages(moduleMap, capTarget.getModule(), candidatesMap);
966    
967            // Cast to implementation class to get access to cached data.
968            Capability cap = (Capability) capTarget;
969    
970            // Loop through all "used" packages of the capability.
971            for (int i = 0; i < cap.getUses().length; i++)
972            {
973                // The target capability's module should have a resolved package
974                // for the "used" package in its set of accessible packages,
975                // since it claims to use it, so get the associated resolved
976                // package.
977                ResolvedPackage rp = (ResolvedPackage) pkgMap.get(cap.getUses()[i]);
978    
979                // In general, the resolved package should not be null,
980                // but check for safety.
981                if (rp != null)
982                {
983                    // First, iterate through all capabilities for the resolved
984                    // package associated with the current "used" package and calculate
985                    // and combine the "uses" constraints for each package.
986                    for (int srcIdx = 0; srcIdx < rp.m_capList.size(); srcIdx++)
987                    {
988                        usesMap = calculateUsesConstraints(
989                            (ICapability) rp.m_capList.get(srcIdx),
990                            moduleMap, usesMap, cycleMap, candidatesMap);
991                    }
992    
993                    // Then, add the resolved package for the current "used" package
994                    // as a "uses" constraint too; add it to an existing constraint
995                    // list if the current "used" package is already in the uses map.
996                    List constraintList = (List) usesMap.get(cap.getUses()[i]);
997                    if (constraintList == null)
998                    {
999                        constraintList = new ArrayList();
1000                    }
1001                    constraintList.add(rp);
1002                    usesMap.put(cap.getUses()[i], constraintList);
1003                }
1004            }
1005    
1006            return usesMap;
1007        }
1008    
1009        private static Map getModulePackages(Map moduleMap, IModule module, Map candidatesMap)
1010            throws ResolveException
1011        {
1012            Map map = (Map) moduleMap.get(module);
1013    
1014            if (map == null)
1015            {
1016                map = calculateModulePackages(module, candidatesMap);
1017                moduleMap.put(module, map);
1018            }
1019            return map;
1020        }
1021    
1022        /**
1023         * <p>
1024         * Calculates the module's set of accessible packages and their
1025         * assocaited package capabilities. This method uses the current candidates
1026         * for resolving the module's requirements from the candidate map
1027         * to calculate the module's accessible packages.
1028         * </p>
1029         * @param module the module whose package map is to be calculated.
1030         * @param candidatesMap the map of potential candidates for resolving
1031         *        the module's requirements.
1032         * @return a map of the packages accessible to the specified module where
1033         *         the key of the map is the package name and the value of the map
1034         *         is a ResolvedPackage.
1035        **/
1036        private static Map calculateModulePackages(IModule module, Map candidatesMap)
1037            throws ResolveException
1038        {
1039    //System.out.println("calculateModulePackages("+module+")");
1040            Map importedPackages = calculateImportedPackages(module, candidatesMap);
1041            Map exportedPackages = calculateExportedPackages(module);
1042            Map requiredPackages = calculateRequiredPackages(module, candidatesMap);
1043    
1044            // Merge exported packages into required packages. If a package is both
1045            // exported and required, then append the exported package to the end of
1046            // the require packages; otherwise just add it to the package map.
1047            for (Iterator i = exportedPackages.entrySet().iterator(); i.hasNext(); )
1048            {
1049                Map.Entry entry = (Map.Entry) i.next();
1050                ResolvedPackage rpReq = (ResolvedPackage) requiredPackages.get(entry.getKey());
1051                if (rpReq != null)
1052                {
1053                    // Merge exported and required packages, avoiding duplicate
1054                    // packages and maintaining ordering.
1055                    ResolvedPackage rpExport = (ResolvedPackage) entry.getValue();
1056                    rpReq.merge(rpExport);
1057                }
1058                else
1059                {
1060                    requiredPackages.put(entry.getKey(), entry.getValue());
1061                }
1062            }
1063    
1064            // Merge imported packages into required packages. Imports overwrite
1065            // any required and/or exported package.
1066            for (Iterator i = importedPackages.entrySet().iterator(); i.hasNext(); )
1067            {
1068                Map.Entry entry = (Map.Entry) i.next();
1069                requiredPackages.put(entry.getKey(), entry.getValue());
1070            }
1071    
1072            return requiredPackages;
1073        }
1074    
1075        private static Map calculateImportedPackages(IModule targetModule, Map candidatesMap)
1076            throws ResolveException
1077        {
1078            return (candidatesMap.get(targetModule) == null)
1079                ? calculateImportedPackagesResolved(targetModule)
1080                : calculateImportedPackagesUnresolved(targetModule, candidatesMap);
1081        }
1082    
1083        private static Map calculateImportedPackagesUnresolved(IModule targetModule, Map candidatesMap)
1084            throws ResolveException
1085        {
1086    //System.out.println("calculateImportedPackagesUnresolved("+targetModule+")");
1087            Map pkgMap = new HashMap();
1088    
1089            // Get the candidate set list to get all candidates for
1090            // all of the target module's requirements.
1091            List candSetList = (List) candidatesMap.get(targetModule);
1092    
1093            // Loop through all candidate sets that represent import dependencies
1094            // for the target module and add the current candidate's packages
1095            // to the imported package map.
1096            for (int candSetIdx = 0;
1097                (candSetList != null) && (candSetIdx < candSetList.size());
1098                candSetIdx++)
1099            {
1100                CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
1101                ICapability candCap = (ICapability) cs.m_candidates.get(cs.m_idx);
1102    
1103                if (candCap.getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
1104                {
1105                    String pkgName = (String)
1106                        candCap.getProperties().get(ICapability.PACKAGE_PROPERTY);
1107    
1108                    ResolvedPackage rp = new ResolvedPackage(pkgName, cs);
1109                    rp.m_capList.add(candCap);
1110                    pkgMap.put(rp.m_name, rp);
1111                }
1112            }
1113    
1114            return pkgMap;
1115        }
1116    
1117        private static Map calculateImportedPackagesResolved(IModule targetModule)
1118            throws ResolveException
1119        {
1120    //System.out.println("calculateImportedPackagesResolved("+targetModule+")");
1121            Map pkgMap = new HashMap();
1122    
1123            // Loop through the target module's wires for package
1124            // dependencies and add the resolved packages to the
1125            // imported package map.
1126            IWire[] wires = targetModule.getWires();
1127            for (int wireIdx = 0; (wires != null) && (wireIdx < wires.length); wireIdx++)
1128            {
1129                if (wires[wireIdx].getCapability().getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
1130                {
1131                    String pkgName = (String)
1132                        wires[wireIdx].getCapability().getProperties().get(ICapability.PACKAGE_PROPERTY);
1133                    ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
1134                    rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
1135                    rp.m_capList.add(wires[wireIdx].getCapability());
1136                    pkgMap.put(rp.m_name, rp);
1137                }
1138            }
1139    
1140            return pkgMap;
1141        }
1142    
1143        private static Map calculateExportedPackages(IModule targetModule)
1144        {
1145    //System.out.println("calculateExportedPackages("+targetModule+")");
1146            Map pkgMap = new HashMap();
1147    
1148            // Loop through the target module's capabilities that represent
1149            // exported packages and add them to the exported package map.
1150            ICapability[] caps = targetModule.getCapabilities();
1151            for (int capIdx = 0; (caps != null) && (capIdx < caps.length); capIdx++)
1152            {
1153                if (caps[capIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
1154                {
1155                    String pkgName = (String)
1156                        caps[capIdx].getProperties().get(ICapability.PACKAGE_PROPERTY);
1157                    ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
1158                    rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
1159                    rp.m_capList.add(caps[capIdx]);
1160                    pkgMap.put(rp.m_name, rp);
1161                }
1162            }
1163    
1164            return pkgMap;
1165        }
1166    
1167        private static Map calculateRequiredPackages(IModule targetModule, Map candidatesMap)
1168        {
1169            return (candidatesMap.get(targetModule) == null)
1170                ? calculateRequiredPackagesResolved(targetModule)
1171                : calculateRequiredPackagesUnresolved(targetModule, candidatesMap);
1172        }
1173    
1174        private static Map calculateRequiredPackagesUnresolved(IModule targetModule, Map candidatesMap)
1175        {
1176    //System.out.println("calculateRequiredPackagesUnresolved("+targetModule+")");
1177            Map pkgMap = new HashMap();
1178    
1179            // Loop through target module's candidate list for candidates
1180            // for its module dependencies and merge re-exported packages.
1181            List candSetList = (List) candidatesMap.get(targetModule);
1182            for (int candSetIdx = 0;
1183                (candSetList != null) && (candSetIdx < candSetList.size());
1184                candSetIdx++)
1185            {
1186                CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
1187                ICapability candCap = (ICapability) cs.m_candidates.get(cs.m_idx);
1188    
1189                // If the capabaility is a module dependency, then flatten it to packages.
1190                if (candCap.getNamespace().equals(ICapability.MODULE_NAMESPACE))
1191                {
1192                    // Calculate transitively required packages.
1193                    Map cycleMap = new HashMap();
1194                    cycleMap.put(targetModule, targetModule);
1195                    Map requireMap =
1196                        calculateExportedAndReexportedPackages(
1197                            candCap, candidatesMap, cycleMap);
1198    
1199                    // Take the flattened required package map for the current
1200                    // module dependency and merge it into the existing map
1201                    // of required packages.
1202                    for (Iterator reqIter = requireMap.entrySet().iterator(); reqIter.hasNext(); )
1203                    {
1204                        Map.Entry entry = (Map.Entry) reqIter.next();
1205                        ResolvedPackage rp = (ResolvedPackage) pkgMap.get(entry.getKey());
1206                        if (rp != null)
1207                        {
1208                            // Merge required packages, avoiding duplicate
1209                            // packages and maintaining ordering.
1210                            ResolvedPackage rpReq = (ResolvedPackage) entry.getValue();
1211                            rp.merge(rpReq);
1212                        }
1213                        else
1214                        {
1215                            pkgMap.put(entry.getKey(), entry.getValue());
1216                        }
1217                    }
1218                }
1219            }
1220    
1221            return pkgMap;
1222        }
1223    
1224        private static Map calculateRequiredPackagesResolved(IModule targetModule)
1225        {
1226    //System.out.println("calculateRequiredPackagesResolved("+targetModule+")");
1227            Map pkgMap = new HashMap();
1228    
1229            // Loop through target module's wires for module dependencies
1230            // and merge re-exported packages.
1231            IWire[] wires = targetModule.getWires();
1232            for (int i = 0; (wires != null) && (i < wires.length); i++)
1233            {
1234                // If the wire is a module dependency, then flatten it to packages.
1235                if (wires[i].getCapability().getNamespace().equals(ICapability.MODULE_NAMESPACE))
1236                {
1237                    // Calculate transitively required packages.
1238                    // We can call calculateExportedAndReexportedPackagesResolved()
1239                    // directly, since we know all dependencies have to be resolved
1240                    // because this module itself is resolved.
1241                    Map cycleMap = new HashMap();
1242                    cycleMap.put(targetModule, targetModule);
1243                    Map requireMap =
1244                        calculateExportedAndReexportedPackagesResolved(
1245                            wires[i].getExporter(), cycleMap);
1246    
1247                    // Take the flattened required package map for the current
1248                    // module dependency and merge it into the existing map
1249                    // of required packages.
1250                    for (Iterator reqIter = requireMap.entrySet().iterator(); reqIter.hasNext(); )
1251                    {
1252                        Map.Entry entry = (Map.Entry) reqIter.next();
1253                        ResolvedPackage rp = (ResolvedPackage) pkgMap.get(entry.getKey());
1254                        if (rp != null)
1255                        {
1256                            // Merge required packages, avoiding duplicate
1257                            // packages and maintaining ordering.
1258                            ResolvedPackage rpReq = (ResolvedPackage) entry.getValue();
1259                            rp.merge(rpReq);
1260                        }
1261                        else
1262                        {
1263                            pkgMap.put(entry.getKey(), entry.getValue());
1264                        }
1265                    }
1266                }
1267            }
1268    
1269            return pkgMap;
1270        }
1271    
1272        private static Map calculateExportedAndReexportedPackages(
1273            ICapability capTarget, Map candidatesMap, Map cycleMap)
1274        {
1275            return (candidatesMap.get(capTarget.getModule()) == null)
1276                ? calculateExportedAndReexportedPackagesResolved(capTarget.getModule(), cycleMap)
1277                : calculateExportedAndReexportedPackagesUnresolved(capTarget, candidatesMap, cycleMap);
1278        }
1279    
1280        private static Map calculateExportedAndReexportedPackagesUnresolved(
1281            ICapability capTarget, Map candidatesMap, Map cycleMap)
1282        {
1283    //System.out.println("calculateExportedAndReexportedPackagesUnresolved("+psTarget.m_module+")");
1284            Map pkgMap = new HashMap();
1285    
1286            if (cycleMap.get(capTarget.getModule()) != null)
1287            {
1288                return pkgMap;
1289            }
1290    
1291            cycleMap.put(capTarget.getModule(), capTarget.getModule());
1292    
1293            // Loop through all current candidates for target module's dependencies
1294            // and calculate the module's complete set of required packages (and
1295            // their associated packages) and the complete set of required
1296            // packages to be re-exported.
1297            Map allRequiredMap = new HashMap();
1298            Map reexportedPkgMap = new HashMap();
1299            List candSetList = (List) candidatesMap.get(capTarget.getModule());
1300            for (int candSetIdx = 0; candSetIdx < candSetList.size(); candSetIdx++)
1301            {
1302                CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
1303                ICapability candCap = (ICapability) cs.m_candidates.get(cs.m_idx);
1304    
1305                // If the candidate is resolving a module dependency, then
1306                // flatten the required packages if they are re-exported.
1307                if (candCap.getNamespace().equals(ICapability.MODULE_NAMESPACE))
1308                {
1309                    // Determine if required packages are re-exported.
1310                    boolean reexport = false;
1311                    R4Directive[] dirs =  ((Requirement) cs.m_requirement).getDirectives();
1312                    for (int dirIdx = 0;
1313                        !reexport && (dirs != null) && (dirIdx < dirs.length); dirIdx++)
1314                    {
1315                        if (dirs[dirIdx].getName().equals(Constants.VISIBILITY_DIRECTIVE)
1316                            && dirs[dirIdx].getValue().equals(Constants.VISIBILITY_REEXPORT))
1317                        {
1318                            reexport = true;
1319                        }
1320                    }
1321    
1322                    // Recursively calculate the required packages for the
1323                    // current candidate.
1324                    Map requiredMap =
1325                        calculateExportedAndReexportedPackages(candCap, candidatesMap, cycleMap);
1326    
1327                    // Merge the candidate's exported and required packages
1328                    // into the complete set of required packages.
1329                    for (Iterator reqIter = requiredMap.entrySet().iterator(); reqIter.hasNext(); )
1330                    {
1331                        Map.Entry entry = (Map.Entry) reqIter.next();
1332                        String pkgName = (String) entry.getKey();
1333    
1334                        // Merge the current set of required packages into
1335                        // the overall complete set of required packages.
1336                        // We calculate all the required packages, because
1337                        // despite the fact that some packages will be required
1338                        // "privately" and some will be required "reexport", any
1339                        // re-exported packages will ultimately need to
1340                        // be combined with privately required packages,
1341                        // if the required packages overlap. This is one of the
1342                        // bad things about require-bundle behavior, it does not
1343                        // necessarily obey the visibility rules declared in the
1344                        // dependency.
1345                        ResolvedPackage rp = (ResolvedPackage) allRequiredMap.get(pkgName);
1346                        if (rp != null)
1347                        {
1348                            // Create the union of all packages.
1349                            ResolvedPackage rpReq = (ResolvedPackage) entry.getValue();
1350                            rp.merge(rpReq);
1351                        }
1352                        else
1353                        {
1354                            // Add package to required map.
1355                            allRequiredMap.put(pkgName, entry.getValue());
1356                        }
1357    
1358                        // Keep track of all required packages to be re-exported.
1359                        // All re-exported packages will need to be merged into the
1360                        // target module's package map and become part of its overall
1361                        // export signature.
1362                        if (reexport)
1363                        {
1364                            reexportedPkgMap.put(pkgName, pkgName);
1365                        }
1366                    }
1367                }
1368            }
1369    
1370            // For the target module we have now calculated its entire set
1371            // of required packages and their associated packages in
1372            // allRequiredMap and have calculated all packages to be re-exported
1373            // in reexportedPkgMap. Add all re-exported required packages to the
1374            // target module's package map since they will be part of its export
1375            // signature.
1376            for (Iterator iter = reexportedPkgMap.entrySet().iterator(); iter.hasNext(); )
1377            {
1378                String pkgName = (String) ((Map.Entry) iter.next()).getKey();
1379                pkgMap.put(pkgName, allRequiredMap.get(pkgName));
1380            }
1381    
1382            // Now loop through the target module's export package capabilities and add
1383            // the target module's export capability as a source for any exported packages.
1384            ICapability[] candCaps = capTarget.getModule().getCapabilities();
1385            for (int capIdx = 0; (candCaps != null) && (capIdx < candCaps.length); capIdx++)
1386            {
1387                if (candCaps[capIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
1388                {
1389                    String pkgName = (String)
1390                        candCaps[capIdx].getProperties().get(ICapability.PACKAGE_PROPERTY);
1391                    ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
1392                    rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
1393                    rp.m_capList.add(candCaps[capIdx]);
1394                    pkgMap.put(rp.m_name, rp);
1395                }
1396            }
1397    
1398            return pkgMap;
1399        }
1400    
1401        private static Map calculateExportedAndReexportedPackagesResolved(
1402            IModule targetModule, Map cycleMap)
1403        {
1404    //System.out.println("calculateExportedAndRequiredPackagesResolved("+targetModule+")");
1405            Map pkgMap = new HashMap();
1406    
1407            if (cycleMap.get(targetModule) != null)
1408            {
1409                return pkgMap;
1410            }
1411    
1412            cycleMap.put(targetModule, targetModule);
1413    
1414            // Loop through all wires for the target module's module dependencies
1415            // and calculate the module's complete set of required packages (and
1416            // their associated sources) and the complete set of required
1417            // packages to be re-exported.
1418            Map allRequiredMap = new HashMap();
1419            Map reexportedPkgMap = new HashMap();
1420            IWire[] wires = targetModule.getWires();
1421            for (int i = 0; (wires != null) && (i < wires.length); i++)
1422            {
1423                // If the wire is a module dependency, then flatten it to packages.
1424                if (wires[i].getCapability().getNamespace().equals(ICapability.MODULE_NAMESPACE))
1425                {
1426                    // Determine if required packages are re-exported.
1427                    boolean reexport = false;
1428                    R4Directive[] dirs =  ((Requirement) wires[i].getRequirement()).getDirectives();
1429                    for (int dirIdx = 0;
1430                        !reexport && (dirs != null) && (dirIdx < dirs.length); dirIdx++)
1431                    {
1432                        if (dirs[dirIdx].getName().equals(Constants.VISIBILITY_DIRECTIVE)
1433                            && dirs[dirIdx].getValue().equals(Constants.VISIBILITY_REEXPORT))
1434                        {
1435                            reexport = true;
1436                        }
1437                    }
1438    
1439                    // Recursively calculate the required packages for the
1440                    // wire's exporting module.
1441                    Map requiredMap = calculateExportedAndReexportedPackagesResolved(
1442                        wires[i].getExporter(), cycleMap);
1443    
1444                    // Merge the wires exported and re-exported packages
1445                    // into the complete set of required packages.
1446                    for (Iterator reqIter = requiredMap.entrySet().iterator(); reqIter.hasNext(); )
1447                    {
1448                        Map.Entry entry = (Map.Entry) reqIter.next();
1449                        String pkgName = (String) entry.getKey();
1450    
1451                        // Merge the current set of required packages into
1452                        // the overall complete set of required packages.
1453                        // We calculate all the required packages, because
1454                        // despite the fact that some packages will be required
1455                        // "privately" and some will be required "reexport", any
1456                        // re-exported packages will ultimately need to
1457                        // be combined with privately required packages,
1458                        // if the required packages overlap. This is one of the
1459                        // bad things about require-bundle behavior, it does not
1460                        // necessarily obey the visibility rules declared in the
1461                        // dependency.
1462                        ResolvedPackage rp = (ResolvedPackage) allRequiredMap.get(pkgName);
1463                        if (rp != null)
1464                        {
1465                            // Create the union of all packages.
1466                            ResolvedPackage rpReq = (ResolvedPackage) entry.getValue();
1467                            rp.merge(rpReq);
1468                        }
1469                        else
1470                        {
1471                            // Add package to required map.
1472                            allRequiredMap.put(pkgName, entry.getValue());
1473                        }
1474    
1475                        // Keep track of all required packages to be re-exported.
1476                        // All re-exported packages will need to be merged into the
1477                        // target module's package map and become part of its overall
1478                        // export signature.
1479                        if (reexport)
1480                        {
1481                            reexportedPkgMap.put(pkgName, pkgName);
1482                        }
1483                    }
1484                }
1485            }
1486    
1487            // For the target module we have now calculated its entire set
1488            // of required packages and their associated source capabilities in
1489            // allRequiredMap and have calculated all packages to be re-exported
1490            // in reexportedPkgMap. Add all re-exported required packages to the
1491            // target module's package map since they will be part of its export
1492            // signature.
1493            for (Iterator iter = reexportedPkgMap.entrySet().iterator(); iter.hasNext(); )
1494            {
1495                String pkgName = (String) ((Map.Entry) iter.next()).getKey();
1496                pkgMap.put(pkgName, allRequiredMap.get(pkgName));
1497            }
1498    
1499            // Now loop through the target module's export package capabilities and
1500            // add the target module as a source for any exported packages.
1501            ICapability[] caps = targetModule.getCapabilities();
1502            for (int i = 0; (caps != null) && (i < caps.length); i++)
1503            {
1504                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
1505                {
1506                    String pkgName = (String)
1507                        caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY);
1508                    ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
1509                    rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
1510                    rp.m_capList.add(caps[i]);
1511                    pkgMap.put(rp.m_name, rp);
1512                }
1513            }
1514    
1515            return pkgMap;
1516        }
1517    
1518        private static Map calculateCandidateRequiredPackages(
1519            IModule module, ICapability capTarget, Map candidatesMap)
1520        {
1521    //System.out.println("calculateCandidateRequiredPackages("+module+")");
1522            Map cycleMap = new HashMap();
1523            cycleMap.put(module, module);
1524            return calculateExportedAndReexportedPackages(capTarget, candidatesMap, cycleMap);
1525        }
1526    
1527        private static void incrementCandidateConfiguration(List resolverList)
1528            throws ResolveException
1529        {
1530            for (int i = 0; i < resolverList.size(); i++)
1531            {
1532                List candSetList = (List) resolverList.get(i);
1533                for (int j = 0; j < candSetList.size(); j++)
1534                {
1535                    CandidateSet cs = (CandidateSet) candSetList.get(j);
1536                    // See if we can increment the candidate set, without overflowing
1537                    // the candidate array bounds.
1538                    if ((cs.m_idx + 1) < cs.m_candidates.size())
1539                    {
1540                        cs.m_idx++;
1541                        return;
1542                    }
1543                    // If the index will overflow the candidate array bounds,
1544                    // then set the index back to zero and try to increment
1545                    // the next candidate.
1546                    else
1547                    {
1548                        cs.m_idx = 0;
1549                    }
1550                }
1551            }
1552            throw new ResolveException(
1553                "Unable to resolve due to constraint violation.", null, null);
1554        }
1555    
1556        private static Map populateWireMap(
1557            ResolverState state, Map candidatesMap, IModule importer, Map wireMap)
1558        {
1559            // If the module is already resolved or it is part of
1560            // a cycle, then just return the wire map.
1561            if (importer.isResolved() || (wireMap.get(importer) != null))
1562            {
1563                return wireMap;
1564            }
1565    
1566            // Get the candidate set list for the importer.
1567            List candSetList = (List) candidatesMap.get(importer);
1568    
1569            List moduleWires = new ArrayList();
1570            List packageWires = new ArrayList();
1571    
1572            // Put the module in the wireMap with an empty wire array;
1573            // we do this early so we can use it to detect cycles.
1574            wireMap.put(importer, m_emptyWires);
1575    
1576            // Loop through each candidate Set and create a wire
1577            // for the selected candidate for the associated import.
1578            for (int candSetIdx = 0; candSetIdx < candSetList.size(); candSetIdx++)
1579            {
1580                // Get the current candidate set.
1581                CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
1582    
1583                // Create a module wire for module dependencies.
1584                if (cs.m_requirement.getNamespace().equals(ICapability.MODULE_NAMESPACE))
1585                {
1586                    moduleWires.add(new R4WireModule(
1587                        importer,
1588                        cs.m_requirement,
1589                        ((ICapability) cs.m_candidates.get(cs.m_idx)).getModule(),
1590                        ((ICapability) cs.m_candidates.get(cs.m_idx)),
1591                        calculateCandidateRequiredPackages(
1592                            importer, (ICapability) cs.m_candidates.get(cs.m_idx), candidatesMap)));
1593                }
1594                // Create a package wire for package dependencies.
1595                // Filter out the case where a module imports from
1596                // itself, since the module should simply load from
1597                // its internal class path in this case.
1598                else if (importer != ((ICapability) cs.m_candidates.get(cs.m_idx)).getModule())
1599                {
1600                    // Add wire for imported package.
1601                    packageWires.add(new R4Wire(
1602                        importer,
1603                        cs.m_requirement,
1604                        ((ICapability) cs.m_candidates.get(cs.m_idx)).getModule(),
1605                        ((ICapability) cs.m_candidates.get(cs.m_idx))));
1606                }
1607    
1608                // Create any necessary wires for the selected candidate module.
1609                wireMap = populateWireMap(
1610                    state, candidatesMap,
1611                    ((ICapability) cs.m_candidates.get(cs.m_idx)).getModule(),
1612                    wireMap);
1613            }
1614    
1615            packageWires.addAll(moduleWires);
1616            wireMap.put(importer, packageWires.toArray(new IWire[packageWires.size()]));
1617    
1618            return wireMap;
1619        }
1620    
1621        //
1622        // Utility methods.
1623        //
1624    
1625        private static void verifyNativeLibraries(IModule module)
1626            throws ResolveException
1627        {
1628            // Next, try to resolve any native code, since the module is
1629            // not resolvable if its native code cannot be loaded.
1630            R4Library[] libs = module.getNativeLibraries();
1631            if (libs != null)
1632            {
1633                String msg = null;
1634                // Verify that all native libraries exist in advance; this will
1635                // throw an exception if the native library does not exist.
1636                for (int libIdx = 0; (msg == null) && (libIdx < libs.length); libIdx++)
1637                {
1638                    String entryName = libs[libIdx].getEntryName();
1639                    if (entryName != null)
1640                    {
1641                        if (!module.getContent().hasEntry(entryName))
1642                        {
1643                            msg = "Native library does not exist: " + entryName;
1644                        }
1645                    }
1646                }
1647                // If we have a zero-length native library array, then
1648                // this means no native library class could be selected
1649                // so we should fail to resolve.
1650                if (libs.length == 0)
1651                {
1652                    msg = "No matching native libraries found.";
1653                }
1654                if (msg != null)
1655                {
1656                    throw new ResolveException(msg, module, null);
1657                }
1658            }
1659        }
1660    
1661        /**
1662         * Checks to see if the passed in module's required execution environment
1663         * is provided by the framework.
1664         * @param fwkExecEvnStr The original property value of the framework's
1665         *        supported execution environments.
1666         * @param fwkExecEnvSet Parsed set of framework's supported execution environments.
1667         * @param module The module whose required execution environment is to be to verified.
1668         * @throws ResolveException if the module's required execution environment does
1669         *         not match the framework's supported execution environment.
1670        **/
1671        private static void verifyExecutionEnvironment(
1672            String fwkExecEnvStr, Set fwkExecEnvSet, IModule module)
1673            throws ResolveException
1674        {
1675            String bundleExecEnvStr = (String)
1676                module.getHeaders().get(Constants.BUNDLE_REQUIREDEXECUTIONENVIRONMENT);
1677            if (bundleExecEnvStr != null)
1678            {
1679                bundleExecEnvStr = bundleExecEnvStr.trim();
1680    
1681                // If the bundle has specified an execution environment and the
1682                // framework has an execution environment specified, then we must
1683                // check for a match.
1684                if (!bundleExecEnvStr.equals("")
1685                    && (fwkExecEnvStr != null)
1686                    && (fwkExecEnvStr.length() > 0))
1687                {
1688                    StringTokenizer tokens = new StringTokenizer(bundleExecEnvStr, ",");
1689                    boolean found = false;
1690                    while (tokens.hasMoreTokens() && !found)
1691                    {
1692                        if (fwkExecEnvSet.contains(tokens.nextToken().trim()))
1693                        {
1694                            found = true;
1695                        }
1696                    }
1697                    if (!found)
1698                    {
1699                        throw new ResolveException(
1700                            "Execution environment not supported: "
1701                            + bundleExecEnvStr, module, null);
1702                    }
1703                }
1704            }
1705        }
1706    
1707        /**
1708         * Updates the framework wide execution environment string and a cached Set of
1709         * execution environment tokens from the comma delimited list specified by the
1710         * system variable 'org.osgi.framework.executionenvironment'.
1711         * @param frameworkEnvironment Comma delimited string of provided execution environments
1712        **/
1713        private static Set parseExecutionEnvironments(String fwkExecEnvStr)
1714        {
1715            Set newSet = new HashSet();
1716            if (fwkExecEnvStr != null)
1717            {
1718                StringTokenizer tokens = new StringTokenizer(fwkExecEnvStr, ",");
1719                while (tokens.hasMoreTokens())
1720                {
1721                    newSet.add(tokens.nextToken().trim());
1722                }
1723            }
1724            return newSet;
1725        }
1726    
1727        //
1728        // Inner classes.
1729        //
1730    
1731        public static interface ResolverState
1732        {
1733            IModule[] getModules();
1734            List getResolvedCandidates(IRequirement req, IModule reqModule);
1735            List getUnresolvedCandidates(IRequirement req, IModule reqModule);
1736        }
1737    }