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;
020    
021    import java.util.ArrayList;
022    import java.util.Collections;
023    import java.util.HashMap;
024    import java.util.Iterator;
025    import java.util.List;
026    import java.util.Map;
027    import org.apache.felix.framework.searchpolicy.ResolveException;
028    import org.apache.felix.framework.searchpolicy.Resolver;
029    import org.apache.felix.framework.util.Util;
030    import org.apache.felix.framework.util.VersionRange;
031    import org.apache.felix.framework.util.manifestparser.R4Attribute;
032    import org.apache.felix.framework.util.manifestparser.R4Directive;
033    import org.apache.felix.framework.util.manifestparser.Requirement;
034    import org.apache.felix.moduleloader.ICapability;
035    import org.apache.felix.moduleloader.IModule;
036    import org.apache.felix.moduleloader.IRequirement;
037    import org.apache.felix.moduleloader.IWire;
038    import org.osgi.framework.BundlePermission;
039    import org.osgi.framework.Constants;
040    import org.osgi.framework.PackagePermission;
041    import org.osgi.framework.Version;
042    
043    public class FelixResolverState implements Resolver.ResolverState
044    {
045        private final Logger m_logger;
046        // List of all modules.
047        private final List m_moduleList = new ArrayList();
048        // Map of fragment symbolic names to list of fragment modules sorted by version.
049        private final Map m_fragmentMap = new HashMap();
050        // Maps a package name to a list of exporting capabilities.
051        private final Map m_unresolvedPkgIndex = new HashMap();
052        // Maps a package name to a list of exporting capabilities.
053        private final Map m_resolvedPkgIndex = new HashMap();
054        // Maps a module to a list of capabilities.
055        private final Map m_resolvedCapMap = new HashMap();
056    
057        public FelixResolverState(Logger logger)
058        {
059            m_logger = logger;
060        }
061    
062        public synchronized void addModule(IModule module)
063        {
064            if (Util.isFragment(module))
065            {
066                addFragment(module);
067            }
068            else
069            {
070                addHost(module);
071            }
072    
073    //System.out.println("UNRESOLVED PACKAGES:");
074    //dumpPackageIndex(m_unresolvedPkgIndex);
075    //System.out.println("RESOLVED PACKAGES:");
076    //dumpPackageIndex(m_resolvedPkgIndex);
077        }
078    
079        public synchronized void removeModule(IModule module)
080        {
081            if (Util.isFragment(module))
082            {
083                removeFragment(module);
084            }
085            else
086            {
087                removeHost(module);
088            }
089        }
090    
091        private void addFragment(IModule fragment)
092        {
093    // TODO: FRAGMENT - This should check to make sure that the host allows fragments.
094            IModule bestFragment = indexFragment(m_fragmentMap, fragment);
095    
096            // If the newly added fragment is the highest version for
097            // its given symbolic name, then try to merge it to any
098            // matching unresolved hosts and remove the previous highest
099            // version of the fragment.
100            if (bestFragment == fragment)
101            {
102    
103                // If we have any matching hosts, then merge the new fragment while
104                // removing any older version of the new fragment. Also remove host's
105                // existing capabilities from the package index and reindex its new
106                // ones after attaching the fragment.
107                List matchingHosts = getMatchingHosts(fragment);
108                for (int hostIdx = 0; hostIdx < matchingHosts.size(); hostIdx++)
109                {
110                    IModule host = ((ICapability) matchingHosts.get(hostIdx)).getModule();
111    
112                    // Get the fragments currently attached to the host so we
113                    // can remove the older version of the current fragment, if any.
114                    IModule[] fragments = ((ModuleImpl) host).getFragments();
115                    List fragmentList = new ArrayList();
116                    for (int fragIdx = 0;
117                        (fragments != null) && (fragIdx < fragments.length);
118                        fragIdx++)
119                    {
120                        if (!fragments[fragIdx].getSymbolicName().equals(
121                            bestFragment.getSymbolicName()))
122                        {
123                            fragmentList.add(fragments[fragIdx]);
124                        }
125                    }
126    
127                    // Now add the new fragment in bundle ID order.
128                    int index = -1;
129                    for (int listIdx = 0;
130                        (index < 0) && (listIdx < fragmentList.size());
131                        listIdx++)
132                    {
133                        IModule f = (IModule) fragmentList.get(listIdx);
134                        if (bestFragment.getBundle().getBundleId()
135                            < f.getBundle().getBundleId())
136                        {
137                            index = listIdx;
138                        }
139                    }
140                    fragmentList.add(
141                        (index < 0) ? fragmentList.size() : index, bestFragment);
142    
143                    // Remove host's existing exported packages from index.
144                    ICapability[] caps = host.getCapabilities();
145                    for (int i = 0; (caps != null) && (i < caps.length); i++)
146                    {
147                        if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
148                        {
149                            // Get package name.
150                            String pkgName = (String)
151                                caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY);
152                            // Remove from "unresolved" package map.
153                            List capList = (List) m_unresolvedPkgIndex.get(pkgName);
154                            if (capList != null)
155                            {
156                                capList.remove(caps[i]);
157                            }
158                        }
159                    }
160    
161                    // Check if fragment conflicts with existing metadata.
162                    checkForConflicts(host, fragmentList);
163    
164                    // Attach the fragments to the host.
165                    fragments = (fragmentList.size() == 0)
166                        ? null
167                        : (IModule[]) fragmentList.toArray(new IModule[fragmentList.size()]);
168                    try
169                    {
170                        ((ModuleImpl) host).attachFragments(fragments);
171                    }
172                    catch (Exception ex)
173                    {
174                        // Try to clean up by removing all fragments.
175                        try
176                        {
177                            ((ModuleImpl) host).attachFragments(null);
178                        }
179                        catch (Exception ex2)
180                        {
181                        }
182                        m_logger.log(Logger.LOG_ERROR,
183                            "Serious error attaching fragments.", ex);
184                    }
185    
186                    // Reindex the host's exported packages.
187                    caps = host.getCapabilities();
188                    for (int i = 0; (caps != null) && (i < caps.length); i++)
189                    {
190                        if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
191                        {
192                            indexPackageCapability(m_unresolvedPkgIndex, caps[i]);
193                        }
194                    }
195                }
196            }
197        }
198    
199        private void removeFragment(IModule fragment)
200        {
201            // Get fragment list, which may be null for system bundle fragments.
202            List fragList = (List) m_fragmentMap.get(fragment.getSymbolicName());
203            if (fragList != null)
204            {
205                // Remove from fragment map.
206                fragList.remove(fragment);
207                if (fragList.size() == 0)
208                {
209                    m_fragmentMap.remove(fragment.getSymbolicName());
210                }
211    
212                // If we have any matching hosts, then remove  fragment while
213                // removing any older version of the new fragment. Also remove host's
214                // existing capabilities from the package index and reindex its new
215                // ones after attaching the fragment.
216                List matchingHosts = getMatchingHosts(fragment);
217                for (int hostIdx = 0; hostIdx < matchingHosts.size(); hostIdx++)
218                {
219                    IModule host = ((ICapability) matchingHosts.get(hostIdx)).getModule();
220    
221                    // Check to see if the removed fragment was actually merged with
222                    // the host, since it might not be if it wasn't the highest version.
223                    // If it was, recalculate the fragments for the host.
224                    IModule[] fragments = ((ModuleImpl) host).getFragments();
225                    for (int fragIdx = 0;
226                        (fragments != null) && (fragIdx < fragments.length);
227                        fragIdx++)
228                    {
229                        if (!fragments[fragIdx].equals(fragment))
230                        {
231                            List fragmentList = getMatchingFragments(host);
232    
233                            // Remove host's existing exported packages from index.
234                            ICapability[] caps = host.getCapabilities();
235                            for (int i = 0; (caps != null) && (i < caps.length); i++)
236                            {
237                                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
238                                {
239                                    // Get package name.
240                                    String pkgName = (String)
241                                        caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY);
242                                    // Remove from "unresolved" package map.
243                                    List capList = (List) m_unresolvedPkgIndex.get(pkgName);
244                                    if (capList != null)
245                                    {
246                                        capList.remove(caps[i]);
247                                    }
248                                }
249                            }
250    
251                            // Check if fragment conflicts with existing metadata.
252                            checkForConflicts(host, fragmentList);
253    
254                            // Attach the fragments to the host.
255                            fragments = (fragmentList.size() == 0)
256                                ? null
257                                : (IModule[]) fragmentList.toArray(new IModule[fragmentList.size()]);
258                            try
259                            {
260                                ((ModuleImpl) host).attachFragments(fragments);
261                            }
262                            catch (Exception ex)
263                            {
264                                // Try to clean up by removing all fragments.
265                                try
266                                {
267                                    ((ModuleImpl) host).attachFragments(null);
268                                }
269                                catch (Exception ex2)
270                                {
271                                }
272                                m_logger.log(Logger.LOG_ERROR,
273                                    "Serious error attaching fragments.", ex);
274                            }
275    
276                            // Reindex the host's exported packages.
277                            caps = host.getCapabilities();
278                            for (int i = 0; (caps != null) && (i < caps.length); i++)
279                            {
280                                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
281                                {
282                                    indexPackageCapability(m_unresolvedPkgIndex, caps[i]);
283                                }
284                            }
285                        }
286                    }
287                }
288            }
289        }
290    
291        public void unmergeFragment(IModule module)
292        {
293            if (!Util.isFragment(module))
294            {
295                return;
296            }
297    
298            // Get fragment list, which may be null for system bundle fragments.
299            List fragList = (List) m_fragmentMap.get(module.getSymbolicName());
300            if (fragList != null)
301            {
302                // Remove from fragment map.
303                fragList.remove(module);
304                if (fragList.size() == 0)
305                {
306                    m_fragmentMap.remove(module.getSymbolicName());
307                }
308    
309                // If we have any matching hosts, then remove fragment while
310                // removing any older version of the new fragment. Also remove host's
311                // existing capabilities from the package index and reindex its new
312                // ones after attaching the fragment.
313                List matchingHosts = getMatchingHosts(module);
314                for (int hostIdx = 0; hostIdx < matchingHosts.size(); hostIdx++)
315                {
316                    IModule host = ((ICapability) matchingHosts.get(hostIdx)).getModule();
317                    // Find any unresolved hosts into which the fragment is merged
318                    // and unmerge it.
319                    IModule[] fragments = ((ModuleImpl) host).getFragments();
320                    for (int fragIdx = 0;
321                        !host.isResolved() && (fragments != null) && (fragIdx < fragments.length);
322                        fragIdx++)
323                    {
324                        if (!fragments[fragIdx].equals(module))
325                        {
326                            List fragmentList = getMatchingFragments(host);
327    
328                            // Remove host's existing exported packages from index.
329                            ICapability[] caps = host.getCapabilities();
330                            for (int i = 0; (caps != null) && (i < caps.length); i++)
331                            {
332                                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
333                                {
334                                    // Get package name.
335                                    String pkgName = (String)
336                                        caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY);
337                                    // Remove from "unresolved" package map.
338                                    List capList = (List) m_unresolvedPkgIndex.get(pkgName);
339                                    if (capList != null)
340                                    {
341                                        capList.remove(caps[i]);
342                                    }
343                                }
344                            }
345    
346                            // Check if fragment conflicts with existing metadata.
347                            checkForConflicts(host, fragmentList);
348    
349                            // Attach the fragments to the host.
350                            fragments = (fragmentList.size() == 0)
351                                ? null
352                                : (IModule[]) fragmentList.toArray(new IModule[fragmentList.size()]);
353                            try
354                            {
355                                ((ModuleImpl) host).attachFragments(fragments);
356                            }
357                            catch (Exception ex)
358                            {
359                                // Try to clean up by removing all fragments.
360                                try
361                                {
362                                    ((ModuleImpl) host).attachFragments(null);
363                                }
364                                catch (Exception ex2)
365                                {
366                                }
367                                m_logger.log(Logger.LOG_ERROR,
368                                    "Serious error attaching fragments.", ex);
369                            }
370    
371                            // Reindex the host's exported packages.
372                            caps = host.getCapabilities();
373                            for (int i = 0; (caps != null) && (i < caps.length); i++)
374                            {
375                                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
376                                {
377                                    indexPackageCapability(m_unresolvedPkgIndex, caps[i]);
378                                }
379                            }
380                        }
381                    }
382                }
383            }
384        }
385    
386        private List getMatchingHosts(IModule fragment)
387        {
388            // Find the fragment's host requirement.
389            IRequirement hostReq = getFragmentHostRequirement(fragment);
390    
391            // Create a list of all matching hosts for this fragment.
392            List matchingHosts = new ArrayList();
393            SecurityManager sm = System.getSecurityManager();
394            if ((sm != null) && (fragment.getSymbolicName() != null))
395            {
396                if (!((BundleProtectionDomain) fragment.getSecurityContext()).impliesDirect(new BundlePermission(
397                    fragment.getSymbolicName(), BundlePermission.FRAGMENT)))
398                {
399                    return matchingHosts;
400                }
401            }
402            for (int hostIdx = 0; (hostReq != null) && (hostIdx < m_moduleList.size()); hostIdx++)
403            {
404                IModule host = (IModule) m_moduleList.get(hostIdx);
405                // Only look at unresolved hosts, since we don't support
406                // dynamic attachment of fragments.
407                if (host.isResolved()
408                    || ((BundleImpl) host.getBundle()).isStale()
409                    || ((BundleImpl) host.getBundle()).isRemovalPending())
410                {
411                    continue;
412                }
413    
414                // Find the host capability for the current host.
415                ICapability hostCap = Util.getSatisfyingCapability(host, hostReq);
416    
417                // If there is no host capability in the current module,
418                // then just ignore it.
419                if (hostCap == null)
420                {
421                    continue;
422                }
423                
424                if ((sm != null) && (host.getSymbolicName() != null))
425                {
426                    if (!((BundleProtectionDomain) host.getSecurityContext()).impliesDirect(new BundlePermission(host.getSymbolicName(), 
427                        BundlePermission.HOST)))
428                    {
429                        continue;
430                    }
431                }
432    
433                matchingHosts.add(hostCap);
434            }
435    
436            return matchingHosts;
437        }
438    
439        private void checkForConflicts(IModule host, List fragmentList)
440        {
441            if ((fragmentList == null) || (fragmentList.size() == 0))
442            {
443                return;
444            }
445    
446            // Verify the fragments do not have conflicting imports.
447            // For now, just check for duplicate imports, but in the
448            // future we might want to make this more fine grained.
449            // First get the host's imported packages.
450            final int MODULE_IDX = 0, REQ_IDX = 1;
451            Map ipMerged = new HashMap();
452            Map rbMerged = new HashMap();
453            IRequirement[] reqs = host.getRequirements();
454            for (int reqIdx = 0; (reqs != null) && (reqIdx < reqs.length); reqIdx++)
455            {
456                if (reqs[reqIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
457                {
458                    ipMerged.put(
459                        ((Requirement) reqs[reqIdx]).getTargetName(),
460                        new Object[] { host, reqs[reqIdx] });
461                }
462                else if (reqs[reqIdx].getNamespace().equals(ICapability.MODULE_NAMESPACE))
463                {
464                    rbMerged.put(
465                        ((Requirement) reqs[reqIdx]).getTargetName(),
466                        new Object[] { host, reqs[reqIdx] });
467                }
468            }
469            // Loop through each fragment verifying it does not conflict.
470            // Add its package and bundle dependencies if they do not
471            // conflict or remove the fragment if it does conflict.
472            for (Iterator it = fragmentList.iterator(); it.hasNext(); )
473            {
474                IModule fragment = (IModule) it.next();
475                reqs = fragment.getRequirements();
476                Map ipFragment = new HashMap();
477                Map rbFragment = new HashMap();
478                for (int reqIdx = 0;
479                    (reqs != null) && (reqIdx < reqs.length);
480                    reqIdx++)
481                {
482                    if (reqs[reqIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE)
483                        || reqs[reqIdx].getNamespace().equals(ICapability.MODULE_NAMESPACE))
484                    {
485                        String targetName = ((Requirement) reqs[reqIdx]).getTargetName();
486                        Map mergedReqMap =
487                            (reqs[reqIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
488                                ? ipMerged : rbMerged;
489                        Map fragmentReqMap =
490                            (reqs[reqIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
491                                ? ipFragment : rbFragment;
492                        Object[] existing = (Object[]) mergedReqMap.get(targetName);
493                        if (existing == null)
494                        {
495                            fragmentReqMap.put(targetName, new Object[] { fragment, reqs[reqIdx] });
496                        }
497                        else if (isRequirementConflicting(
498                            (Requirement) existing[REQ_IDX], (Requirement) reqs[reqIdx]))
499                        {
500                            ipFragment.clear();
501                            rbFragment.clear();
502                            it.remove();
503                            m_logger.log(
504                                Logger.LOG_DEBUG,
505                                "Excluding fragment " + fragment.getSymbolicName()
506                                + " from " + host.getSymbolicName()
507                                + " due to conflict with "
508                                + (reqs[reqIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE)
509                                    ? "imported package " : "required bundle ")
510                                + targetName + " from "
511                                + ((IModule) existing[MODULE_IDX]).getSymbolicName());
512                            // No need to finish processing current fragment.
513                            break;
514                        }
515                        else
516                        {
517                            // If there is an overlapping requirement for the existing
518                            // target, then try to calculate the intersecting requirement
519                            // and set the existing requirement to that instead. This
520                            // makes it so version ranges do not have to be exact, just
521                            // overlapping.
522                            Requirement intersection = calculateVersionIntersection(
523                                (Requirement) existing[REQ_IDX], (Requirement) reqs[reqIdx]);
524                            if (intersection != existing[REQ_IDX])
525                            {
526                                existing[REQ_IDX] = intersection;
527                            }
528                        }
529                    }
530                }
531    
532                // Merge non-conflicting requirements into overall set
533                // of requirements and continue checking for conflicts
534                // with the next fragment.
535                for (Iterator it2 = ipFragment.entrySet().iterator(); it2.hasNext(); )
536                {
537                    Map.Entry entry = (Map.Entry) it2.next();
538                    ipMerged.put(entry.getKey(), entry.getValue());
539                }
540                for (Iterator it2 = rbFragment.entrySet().iterator(); it2.hasNext(); )
541                {
542                    Map.Entry entry = (Map.Entry) it2.next();
543                    rbMerged.put(entry.getKey(), entry.getValue());
544                }
545            }
546        }
547    
548        private boolean isRequirementConflicting(
549            Requirement existing, Requirement additional)
550        {
551            // If the namespace is not the same, then they do NOT conflict.
552            if (!existing.getNamespace().equals(additional.getNamespace()))
553            {
554                return false;
555            }
556            // If the target name is not the same, then they do NOT conflict.
557            if (!existing.getTargetName().equals(additional.getTargetName()))
558            {
559                return false;
560            }
561            // If the existing version range floor is greater than the additional
562            // version range's floor, then they are inconflict since we cannot
563            // widen the constraint.
564            if (!existing.getTargetVersionRange().intersects(
565                additional.getTargetVersionRange()))
566            {
567                return true;
568            }
569            // If optionality is not the same, then they conflict, unless
570            // the existing requirement is not optional, then it doesn't matter
571            // what subsequent requirements are since non-optional is stronger
572            // than optional.
573            if (existing.isOptional() && !additional.isOptional())
574            {
575                return true;
576            }
577            // Verify directives are the same.
578            final R4Directive[] exDirs = (existing.getDirectives() == null)
579                ? new R4Directive[0] : existing.getDirectives();
580            final R4Directive[] addDirs = (additional.getDirectives() == null)
581                ? new R4Directive[0] : additional.getDirectives();
582            // Put attributes in a map, since ordering is arbitrary.
583            final Map exDirMap = new HashMap();
584            for (int i = 0; i < exDirs.length; i++)
585            {
586                exDirMap.put(exDirs[i].getName(), exDirs[i]);
587            }
588            // If attribute values do not match, then they conflict.
589            for (int i = 0; i < addDirs.length; i++)
590            {
591                // Ignore resolution directive, since we've already tested it above.
592                if (!addDirs[i].getName().equals(Constants.RESOLUTION_DIRECTIVE))
593                {
594                    final R4Directive exDir = (R4Directive) exDirMap.get(addDirs[i].getName());
595                    if ((exDir == null) ||
596                        !exDir.getValue().equals(addDirs[i].getValue()))
597                    {
598                        return true;
599                    }
600                }
601            }
602            // Verify attributes are the same.
603            final R4Attribute[] exAttrs = (existing.getAttributes() == null)
604                ? new R4Attribute[0] : existing.getAttributes();
605            final R4Attribute[] addAttrs = (additional.getAttributes() == null)
606                ? new R4Attribute[0] : additional.getAttributes();
607            // Put attributes in a map, since ordering is arbitrary.
608            final Map exAttrMap = new HashMap();
609            for (int i = 0; i < exAttrs.length; i++)
610            {
611                exAttrMap.put(exAttrs[i].getName(), exAttrs[i]);
612            }
613            // If attribute values do not match, then they conflict.
614            for (int i = 0; i < addAttrs.length; i++)
615            {
616                // Ignore version property, since we've already tested it above.
617                if (!(additional.getNamespace().equals(ICapability.PACKAGE_NAMESPACE)
618                    && addAttrs[i].getName().equals(ICapability.VERSION_PROPERTY))
619                    && !(additional.getNamespace().equals(ICapability.MODULE_NAMESPACE)
620                        && addAttrs[i].getName().equals(Constants.BUNDLE_VERSION_ATTRIBUTE)))
621                {
622                    final R4Attribute exAttr = (R4Attribute) exAttrMap.get(addAttrs[i].getName());
623                    if ((exAttr == null) ||
624                        !exAttr.getValue().equals(addAttrs[i].getValue()) ||
625                        (exAttr.isMandatory() != addAttrs[i].isMandatory()))
626                    {
627                        return true;
628                    }
629                }
630            }
631            // They do no conflict.
632            return false;
633        }
634    
635        static Requirement calculateVersionIntersection(
636            Requirement existing, Requirement additional)
637        {
638            Requirement intersection = existing;
639            int existVersionIdx = -1, addVersionIdx = -1;
640    
641            // Find the existing version attribute.
642            for (int i = 0; (existVersionIdx < 0) && (i < existing.getAttributes().length); i++)
643            {
644                if ((existing.getNamespace().equals(ICapability.PACKAGE_NAMESPACE)
645                    && existing.getAttributes()[i].getName().equals(ICapability.VERSION_PROPERTY))
646                    || (existing.getNamespace().equals(ICapability.MODULE_NAMESPACE)
647                        && existing.getAttributes()[i].getName().equals(Constants.BUNDLE_VERSION_ATTRIBUTE)))
648                {
649                    existVersionIdx = i;
650                }
651            }
652    
653            // Find the additional version attribute.
654            for (int i = 0; (addVersionIdx < 0) && (i < additional.getAttributes().length); i++)
655            {
656                if ((additional.getNamespace().equals(ICapability.PACKAGE_NAMESPACE)
657                    && additional.getAttributes()[i].getName().equals(ICapability.VERSION_PROPERTY))
658                    || (additional.getNamespace().equals(ICapability.MODULE_NAMESPACE)
659                        && additional.getAttributes()[i].getName().equals(Constants.BUNDLE_VERSION_ATTRIBUTE)))
660                {
661                    addVersionIdx = i;
662                }
663            }
664    
665            // Use the additional requirement's version range if it
666            // has one and the existing requirement does not.
667            if ((existVersionIdx == -1) && (addVersionIdx != -1))
668            {
669                intersection = additional;
670            }
671            // If both requirements have version ranges, then create
672            // a new requirement with an intersecting version range.
673            else if ((existVersionIdx != -1) && (addVersionIdx != -1))
674            {
675                VersionRange vr = ((VersionRange) existing.getAttributes()[existVersionIdx].getValue())
676                    .intersection((VersionRange) additional.getAttributes()[addVersionIdx].getValue());
677                R4Attribute[] attrs = existing.getAttributes();
678                R4Attribute[] newAttrs = new R4Attribute[attrs.length];
679                System.arraycopy(attrs, 0, newAttrs, 0, attrs.length);
680                newAttrs[existVersionIdx] = new R4Attribute(
681                    attrs[existVersionIdx].getName(), vr, false);
682                intersection = new Requirement(
683                    existing.getNamespace(),
684                    existing.getDirectives(),
685                    newAttrs);
686            }
687    
688            return intersection;
689        }
690    
691        private void addHost(IModule host)
692        {
693            // When a module is added, we first need to pre-merge any potential fragments
694            // into the host and then second create an aggregated list of unresolved
695            // capabilities to simplify later processing when resolving bundles.
696            m_moduleList.add(host);
697    
698            //
699            // First, merge applicable fragments.
700            //
701    
702            List fragmentList = getMatchingFragments(host);
703    
704            // Attach any fragments we found for this host.
705            if (fragmentList.size() > 0)
706            {
707                // Check if fragment conflicts with existing metadata.
708                checkForConflicts(host, fragmentList);
709    
710                // Attach the fragments to the host.
711                IModule[] fragments =
712                    (IModule[]) fragmentList.toArray(new IModule[fragmentList.size()]);
713                try
714                {
715                    ((ModuleImpl) host).attachFragments(fragments);
716                }
717                catch (Exception ex)
718                {
719                    // Try to clean up by removing all fragments.
720                    try
721                    {
722                        ((ModuleImpl) host).attachFragments(null);
723                    }
724                    catch (Exception ex2)
725                    {
726                    }
727                    m_logger.log(Logger.LOG_ERROR,
728                        "Serious error attaching fragments.", ex);
729                }
730            }
731    
732            //
733            // Second, index module's capabilities.
734            //
735    
736            ICapability[] caps = host.getCapabilities();
737    
738            // Add exports to unresolved package map.
739            for (int i = 0; (caps != null) && (i < caps.length); i++)
740            {
741                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
742                {
743                    indexPackageCapability(m_unresolvedPkgIndex, caps[i]);
744                }
745            }
746        }
747    
748        private void removeHost(IModule host)
749        {
750            // We need remove the host's exports from the "resolved" and
751            // "unresolved" package maps, remove its dependencies on fragments
752            // and exporters, and remove it from the module list.
753            m_moduleList.remove(host);
754    
755            // Remove exports from package maps.
756            ICapability[] caps = host.getCapabilities();
757            for (int i = 0; (caps != null) && (i < caps.length); i++)
758            {
759                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
760                {
761                    // Get package name.
762                    String pkgName = (String)
763                        caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY);
764                    // Remove from "unresolved" package map.
765                    List capList = (List) m_unresolvedPkgIndex.get(pkgName);
766                    if (capList != null)
767                    {
768                        capList.remove(caps[i]);
769                    }
770    
771                    // Remove from "resolved" package map.
772                    capList = (List) m_resolvedPkgIndex.get(pkgName);
773                    if (capList != null)
774                    {
775                        capList.remove(caps[i]);
776                    }
777                }
778            }
779    
780            // Remove the module from the "resolved" map.
781            m_resolvedCapMap.remove(host);
782    
783            // Set fragments to null, which will remove the module from all
784            // of its dependent fragment modules.
785            try
786            {
787                ((ModuleImpl) host).attachFragments(null);
788            }
789            catch (Exception ex)
790            {
791                m_logger.log(Logger.LOG_ERROR, "Error detaching fragments.", ex);
792            }
793            // Set wires to null, which will remove the module from all
794            // of its dependent modules.
795            ((ModuleImpl) host).setWires(null);
796        }
797    
798        private List getMatchingFragments(IModule host)
799        {
800            // Find the host capability for the current host.
801            ICapability[] caps = Util.getCapabilityByNamespace(host, ICapability.HOST_NAMESPACE);
802            ICapability hostCap = (caps.length == 0) ? null : caps[0];
803    
804            // If we have a host capability, then loop through all fragments trying to
805            // find ones that match.
806            List fragmentList = new ArrayList();
807            SecurityManager sm = System.getSecurityManager();
808            if ((sm != null) && (host.getSymbolicName() != null))
809            {
810                if (!((BundleProtectionDomain) host.getSecurityContext()).impliesDirect(new BundlePermission(host.getSymbolicName(), BundlePermission.HOST)))
811                {
812                    return fragmentList;
813                }
814            }
815            for (Iterator it = m_fragmentMap.entrySet().iterator(); (hostCap != null) && it.hasNext(); )
816            {
817                Map.Entry entry = (Map.Entry) it.next();
818                List fragments = (List) entry.getValue();
819                IModule fragment = null;
820                for (int i = 0; (fragment == null) && (i < fragments.size()); i++)
821                {
822                    IModule f = (IModule) fragments.get(i);
823                    if (!((BundleImpl) f.getBundle()).isStale()
824                        && !((BundleImpl) f.getBundle()).isRemovalPending())
825                    {
826                        fragment = f;
827                    }
828                }
829    
830                if (fragment == null)
831                {
832                    continue;
833                }
834                
835                if ((sm != null) && (fragment.getSymbolicName() != null))
836                {
837                    if (!((BundleProtectionDomain) fragment.getSecurityContext()).impliesDirect(new BundlePermission(fragment.getSymbolicName(), BundlePermission.FRAGMENT)))
838                    {
839                        continue;
840                    }
841                }
842                IRequirement hostReq = getFragmentHostRequirement(fragment);
843    
844                // If we have a host requirement, then loop through each host and
845                // see if it matches the host requirement.
846                if ((hostReq != null) && hostReq.isSatisfied(hostCap))
847                {
848                    // Now add the new fragment in bundle ID order.
849                    int index = -1;
850                    for (int listIdx = 0;
851                        (index < 0) && (listIdx < fragmentList.size());
852                        listIdx++)
853                    {
854                        IModule existing = (IModule) fragmentList.get(listIdx);
855                        if (fragment.getBundle().getBundleId()
856                            < existing.getBundle().getBundleId())
857                        {
858                            index = listIdx;
859                        }
860                    }
861                    fragmentList.add(
862                        (index < 0) ? fragmentList.size() : index, fragment);
863                }
864            }
865    
866            return fragmentList;
867        }
868    
869        public synchronized IModule findHost(IModule rootModule) throws ResolveException
870        {
871            IModule newRootModule = rootModule;
872            if (Util.isFragment(rootModule))
873            {
874                List matchingHosts = getMatchingHosts(rootModule);
875                IModule currentBestHost = null;
876                for (int hostIdx = 0; hostIdx < matchingHosts.size(); hostIdx++)
877                {
878                    IModule host = ((ICapability) matchingHosts.get(hostIdx)).getModule();
879                    if (currentBestHost == null)
880                    {
881                        currentBestHost = host;
882                    }
883                    else if (currentBestHost.getVersion().compareTo(host.getVersion()) < 0)
884                    {
885                        currentBestHost = host;
886                    }
887                }
888                newRootModule = currentBestHost;
889    
890                if (newRootModule == null)
891                {
892                    throw new ResolveException(
893                        "Unable to find host.", rootModule, getFragmentHostRequirement(rootModule));
894                }
895            }
896    
897            return newRootModule;
898        }
899    
900        private IRequirement getFragmentHostRequirement(IModule fragment)
901        {
902            // Find the fragment's host requirement.
903            IRequirement[] reqs = fragment.getRequirements();
904            IRequirement hostReq = null;
905            for (int reqIdx = 0; (hostReq == null) && (reqIdx < reqs.length); reqIdx++)
906            {
907                if (reqs[reqIdx].getNamespace().equals(ICapability.HOST_NAMESPACE))
908                {
909                    hostReq = reqs[reqIdx];
910                }
911            }
912            return hostReq;
913        }
914    
915        /**
916         * This method is used for installing system bundle extensions. It actually
917         * refreshes the system bundle module's capabilities in the resolver state
918         * to capture additional capabilities.
919         * @param module The module being refresh, which should always be the system bundle.
920        **/
921        synchronized void refreshSystemBundleModule(IModule module)
922        {
923            // The system bundle module should always be resolved, so we only need
924            // to update the resolved capability map.
925            ICapability[] caps = module.getCapabilities();
926            for (int i = 0; (caps != null) && (i < caps.length); i++)
927            {
928                List resolvedCaps = (List) m_resolvedCapMap.get(module);
929                if (resolvedCaps == null)
930                {
931                    m_resolvedCapMap.put(module, resolvedCaps = new ArrayList());
932                }
933                if (!resolvedCaps.contains(caps[i]))
934                {
935                    resolvedCaps.add(caps[i]);
936                }
937    
938                // If the capability is a package, then add the exporter module
939                // of the wire to the "resolved" package index and remove it
940                // from the "unresolved" package index.
941                if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
942                {
943                    // Add to "resolved" package index.
944                    indexPackageCapability(m_resolvedPkgIndex, caps[i]);
945                }
946            }
947        }
948    
949        private void dumpPackageIndex(Map pkgIndex)
950        {
951            for (Iterator i = pkgIndex.entrySet().iterator(); i.hasNext(); )
952            {
953                Map.Entry entry = (Map.Entry) i.next();
954                List capList = (List) entry.getValue();
955                if (capList.size() > 0)
956                {
957                    if (!((capList.size() == 1) && ((ICapability) capList.get(0)).getModule().getId().equals("0")))
958                    {
959                        System.out.println("  " + entry.getKey());
960                        for (int j = 0; j < capList.size(); j++)
961                        {
962                            System.out.println("    " + ((ICapability) capList.get(j)).getModule());
963                        }
964                    }
965                }
966            }
967        }
968    
969        public synchronized IModule[] getModules()
970        {
971            return (IModule[]) m_moduleList.toArray(new IModule[m_moduleList.size()]);
972        }
973    
974        public synchronized void moduleResolved(IModule module)
975        {
976            if (module.isResolved())
977            {
978                // At this point, we need to remove all of the resolved module's
979                // capabilities from the "unresolved" package map and put them in
980                // in the "resolved" package map, with the exception of any
981                // package exports that are also imported. In that case we need
982                // to make sure that the import actually points to the resolved
983                // module and not another module. If it points to another module
984                // then the capability should be ignored, since the framework
985                // decided to honor the import and discard the export.
986                ICapability[] caps = module.getCapabilities();
987    
988                // First remove all existing capabilities from the "unresolved" map.
989                for (int capIdx = 0; (caps != null) && (capIdx < caps.length); capIdx++)
990                {
991                    if (caps[capIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
992                    {
993                        // Get package name.
994                        String pkgName = (String)
995                            caps[capIdx].getProperties().get(ICapability.PACKAGE_PROPERTY);
996                        // Remove the module's capability for the package.
997                        List capList = (List) m_unresolvedPkgIndex.get(pkgName);
998                        capList.remove(caps[capIdx]);
999                    }
1000                }
1001    
1002                // Next create a copy of the module's capabilities so we can
1003                // null out any capabilities that should be ignored.
1004                ICapability[] capsCopy = (caps == null) ? null : new ICapability[caps.length];
1005                if (capsCopy != null)
1006                {
1007                    System.arraycopy(caps, 0, capsCopy, 0, caps.length);
1008                }
1009                // Loop through the module's capabilities to determine which ones
1010                // can be ignored by seeing which ones satifies the wire requirements.
1011    // TODO: RB - Bug here because a requirement for a package need not overlap the
1012    //            capability for that package and this assumes it does. This might
1013    //            require us to introduce the notion of a substitutable capability.
1014                IWire[] wires = module.getWires();
1015                for (int capIdx = 0; (capsCopy != null) && (capIdx < capsCopy.length); capIdx++)
1016                {
1017                    // Loop through all wires to see if the current capability
1018                    // satisfies any of the wire requirements.
1019                    for (int wireIdx = 0; (wires != null) && (wireIdx < wires.length); wireIdx++)
1020                    {
1021                        // If one of the module's capabilities satifies the requirement
1022                        // for an existing wire, this means the capability was
1023                        // substituted with another provider by the resolver and
1024                        // the module's capability was not used. Therefore, we should
1025                        // null it here so it doesn't get added the list of resolved
1026                        // capabilities for this module.
1027                        if (wires[wireIdx].getRequirement().isSatisfied(capsCopy[capIdx]))
1028                        {
1029                            capsCopy[capIdx] = null;
1030                            break;
1031                        }
1032                    }
1033                }
1034    
1035                // Now loop through all capabilities and add them to the "resolved"
1036                // capability and package index maps, ignoring any that were nulled out.
1037                for (int capIdx = 0; (capsCopy != null) && (capIdx < capsCopy.length); capIdx++)
1038                {
1039                    if (capsCopy[capIdx] != null)
1040                    {
1041                        List resolvedCaps = (List) m_resolvedCapMap.get(module);
1042                        if (resolvedCaps == null)
1043                        {
1044                            m_resolvedCapMap.put(module, resolvedCaps = new ArrayList());
1045                        }
1046                        if (!resolvedCaps.contains(capsCopy[capIdx]))
1047                        {
1048                            resolvedCaps.add(capsCopy[capIdx]);
1049                        }
1050    
1051                        // If the capability is a package, then add the exporter module
1052                        // of the wire to the "resolved" package index and remove it
1053                        // from the "unresolved" package index.
1054                        if (capsCopy[capIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
1055                        {
1056                            // Add to "resolved" package index.
1057                            indexPackageCapability(m_resolvedPkgIndex, capsCopy[capIdx]);
1058                        }
1059                    }
1060                }
1061            }
1062    
1063    //System.out.println("UNRESOLVED PACKAGES:");
1064    //dumpPackageIndex(m_unresolvedPkgIndex);
1065    //System.out.println("RESOLVED PACKAGES:");
1066    //dumpPackageIndex(m_resolvedPkgIndex);
1067        }
1068    
1069        public synchronized List getResolvedCandidates(IRequirement req, IModule reqModule)
1070        {
1071            // Synchronized on the module manager to make sure that no
1072            // modules are added, removed, or resolved.
1073            List candidates = new ArrayList();
1074            if (req.getNamespace().equals(ICapability.PACKAGE_NAMESPACE)
1075                && (((Requirement) req).getTargetName() != null))
1076            {
1077                String pkgName = ((Requirement) req).getTargetName();
1078                List capList = (List) m_resolvedPkgIndex.get(pkgName);
1079    
1080                for (int capIdx = 0; (capList != null) && (capIdx < capList.size()); capIdx++)
1081                {
1082                    ICapability cap = (ICapability) capList.get(capIdx);
1083                    if (req.isSatisfied(cap))
1084                    {
1085                        if (System.getSecurityManager() != null)
1086                        {
1087                            if (reqModule != ((ICapability) capList.get(capIdx)).getModule())
1088                            {
1089                                if ((!((BundleProtectionDomain)((ICapability) 
1090                                    capList.get(capIdx)).getModule().getSecurityContext()).impliesDirect(
1091                                    new PackagePermission(((Requirement) req).getTargetName(), PackagePermission.EXPORTONLY))) ||
1092                                    !((reqModule == null) ||
1093                                    ((BundleProtectionDomain) reqModule.getSecurityContext()).impliesDirect(
1094                                    new PackagePermission(((Requirement) req).getTargetName(), ((ICapability) 
1095                                    capList.get(capIdx)).getModule().getBundle(),PackagePermission.IMPORT))
1096                                    ))
1097                                {
1098                                    continue;
1099                                }
1100                            }
1101                        }
1102                        candidates.add(cap);
1103                    }
1104                }
1105            }
1106            else
1107            {
1108                Iterator i = m_resolvedCapMap.entrySet().iterator();
1109                while (i.hasNext())
1110                {
1111                    Map.Entry entry = (Map.Entry) i.next();
1112                    IModule module = (IModule) entry.getKey();
1113                    List caps = (List) entry.getValue();
1114                    for (int capIdx = 0; (caps != null) && (capIdx < caps.size()); capIdx++)
1115                    {
1116                        ICapability cap = (ICapability) caps.get(capIdx);
1117                        if (req.isSatisfied(cap))
1118                        {
1119                            if (System.getSecurityManager() != null)
1120                            {
1121                                if (req.getNamespace().equals(ICapability.PACKAGE_NAMESPACE) && (
1122                                    !((BundleProtectionDomain) cap.getModule().getSecurityContext()).impliesDirect(
1123                                    new PackagePermission((String) cap.getProperties().get(ICapability.PACKAGE_PROPERTY), PackagePermission.EXPORTONLY)) ||
1124                                    !((reqModule == null) ||
1125                                    ((BundleProtectionDomain) reqModule.getSecurityContext()).impliesDirect(
1126                                    new PackagePermission((String) cap.getProperties().get(ICapability.PACKAGE_PROPERTY), cap.getModule().getBundle(),PackagePermission.IMPORT))
1127                                    )))
1128                                {
1129                                    if (reqModule != cap.getModule())
1130                                    {
1131                                        continue;
1132                                    }
1133                                }
1134                                if (req.getNamespace().equals(ICapability.MODULE_NAMESPACE) && (
1135                                    !((BundleProtectionDomain) cap.getModule().getSecurityContext()).impliesDirect(
1136                                    new BundlePermission(cap.getModule().getSymbolicName(), BundlePermission.PROVIDE)) ||
1137                                    !((reqModule == null) ||
1138                                    ((BundleProtectionDomain) reqModule.getSecurityContext()).impliesDirect(
1139                                    new BundlePermission(reqModule.getSymbolicName(), BundlePermission.REQUIRE))
1140                                    )))
1141                                {
1142                                    continue;
1143                                }
1144                            }
1145                            candidates.add(cap);
1146                        }
1147                    }
1148                }
1149            }
1150            Collections.sort(candidates);
1151            return candidates;
1152        }
1153    
1154        public synchronized List getUnresolvedCandidates(IRequirement req, IModule reqModule)
1155        {
1156            // Get all matching unresolved capabilities.
1157            List candidates = new ArrayList();
1158            if (req.getNamespace().equals(ICapability.PACKAGE_NAMESPACE) &&
1159                (((Requirement) req).getTargetName() != null))
1160            {
1161                List capList = (List) m_unresolvedPkgIndex.get(((Requirement) req).getTargetName());
1162                for (int capIdx = 0; (capList != null) && (capIdx < capList.size()); capIdx++)
1163                {
1164                    // If compatible and it is not currently resolved, then add
1165                    // the unresolved candidate to the list.
1166                    if (req.isSatisfied((ICapability) capList.get(capIdx)))
1167                    {
1168                        if (System.getSecurityManager() != null)
1169                        {
1170                            if (reqModule != ((ICapability) capList.get(capIdx)).getModule())
1171                            {
1172                                if (!((BundleProtectionDomain)((ICapability) 
1173                                    capList.get(capIdx)).getModule().getSecurityContext()).impliesDirect(
1174                                    new PackagePermission(((Requirement) req).getTargetName(), PackagePermission.EXPORTONLY)) ||
1175                                    !((reqModule == null) ||
1176                                    ((BundleProtectionDomain) reqModule.getSecurityContext()).impliesDirect(
1177                                    new PackagePermission(((Requirement) req).getTargetName(), ((ICapability) 
1178                                    capList.get(capIdx)).getModule().getBundle(),PackagePermission.IMPORT))
1179                                    ))
1180                                {
1181                                    continue;
1182                                }
1183                            }
1184                        }
1185                        candidates.add(capList.get(capIdx));
1186                    }
1187                }
1188            }
1189            else
1190            {
1191                IModule[] modules = getModules();
1192                for (int modIdx = 0; (modules != null) && (modIdx < modules.length); modIdx++)
1193                {
1194                    // Get the module's export package for the target package.
1195                    ICapability cap = Util.getSatisfyingCapability(modules[modIdx], req);
1196                    // If compatible and it is not currently resolved, then add
1197                    // the unresolved candidate to the list.
1198                    if ((cap != null) && !modules[modIdx].isResolved())
1199                    {
1200                        if (System.getSecurityManager() != null)
1201                        {
1202                            if (req.getNamespace().equals(ICapability.PACKAGE_NAMESPACE) && (
1203                                !((BundleProtectionDomain) cap.getModule().getSecurityContext()).impliesDirect(
1204                                new PackagePermission((String) cap.getProperties().get(ICapability.PACKAGE_PROPERTY), PackagePermission.EXPORTONLY)) ||
1205                                !((reqModule == null) ||
1206                                ((BundleProtectionDomain) reqModule.getSecurityContext()).impliesDirect(
1207                                new PackagePermission((String) cap.getProperties().get(ICapability.PACKAGE_PROPERTY), cap.getModule().getBundle(),PackagePermission.IMPORT))
1208                                )))
1209                            {
1210                                if (reqModule != cap.getModule())
1211                                {
1212                                    continue;
1213                                }
1214                            }
1215                            if (req.getNamespace().equals(ICapability.MODULE_NAMESPACE) && (
1216                                    !((BundleProtectionDomain) cap.getModule().getSecurityContext()).impliesDirect(
1217                                    new BundlePermission(cap.getModule().getSymbolicName(), BundlePermission.PROVIDE)) ||
1218                                    !((reqModule == null) ||
1219                                    ((BundleProtectionDomain) reqModule.getSecurityContext()).impliesDirect(
1220                                    new BundlePermission(reqModule.getSymbolicName(), BundlePermission.REQUIRE))
1221                                    )))
1222                                {
1223                                    continue;
1224                                }
1225                        }
1226                        candidates.add(cap);
1227                    }
1228                }
1229            }
1230    
1231            // Create list of compatible providers.
1232            Collections.sort(candidates);
1233            return candidates;
1234        }
1235    
1236        //
1237        // Utility methods.
1238        //
1239    
1240        private void indexPackageCapability(Map map, ICapability capability)
1241        {
1242            if (capability.getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
1243            {
1244                String pkgName = (String)
1245                    capability.getProperties().get(ICapability.PACKAGE_PROPERTY);
1246                List capList = (List) map.get(pkgName);
1247    
1248                // We want to add the capability into the list of exporters
1249                // in sorted order (descending version and ascending bundle
1250                // identifier). Insert using a simple binary search algorithm.
1251                if (capList == null)
1252                {
1253                    capList = new ArrayList();
1254                    capList.add(capability);
1255                }
1256                else
1257                {
1258                    Version version = (Version)
1259                        capability.getProperties().get(ICapability.VERSION_PROPERTY);
1260                    Version middleVersion = null;
1261                    int top = 0, bottom = capList.size() - 1, middle = 0;
1262                    while (top <= bottom)
1263                    {
1264                        middle = (bottom - top) / 2 + top;
1265                        middleVersion = (Version)
1266                            ((ICapability) capList.get(middle))
1267                                .getProperties().get(ICapability.VERSION_PROPERTY);
1268                        // Sort in reverse version order.
1269                        int cmp = middleVersion.compareTo(version);
1270                        if (cmp < 0)
1271                        {
1272                            bottom = middle - 1;
1273                        }
1274                        else if (cmp == 0)
1275                        {
1276                            // Sort further by ascending bundle ID.
1277                            long middleId = ((ICapability) capList.get(middle))
1278                                .getModule().getBundle().getBundleId();
1279                            long exportId = capability.getModule().getBundle().getBundleId();
1280                            if (middleId < exportId)
1281                            {
1282                                top = middle + 1;
1283                            }
1284                            else
1285                            {
1286                                bottom = middle - 1;
1287                            }
1288                        }
1289                        else
1290                        {
1291                            top = middle + 1;
1292                        }
1293                    }
1294    
1295                    // Ignore duplicates.
1296                    if ((top >= capList.size()) || (capList.get(top) != capability))
1297                    {
1298                        capList.add(top, capability);
1299                    }
1300                }
1301    
1302                map.put(pkgName, capList);
1303            }
1304        }
1305    
1306        private IModule indexFragment(Map map, IModule module)
1307        {
1308            List modules = (List) map.get(module.getSymbolicName());
1309    
1310            // We want to add the fragment into the list of matching
1311            // fragments in sorted order (descending version and
1312            // ascending bundle identifier). Insert using a simple
1313            // binary search algorithm.
1314            if (modules == null)
1315            {
1316                modules = new ArrayList();
1317                modules.add(module);
1318            }
1319            else
1320            {
1321                Version version = module.getVersion();
1322                Version middleVersion = null;
1323                int top = 0, bottom = modules.size() - 1, middle = 0;
1324                while (top <= bottom)
1325                {
1326                    middle = (bottom - top) / 2 + top;
1327                    middleVersion = ((IModule) modules.get(middle)).getVersion();
1328                    // Sort in reverse version order.
1329                    int cmp = middleVersion.compareTo(version);
1330                    if (cmp < 0)
1331                    {
1332                        bottom = middle - 1;
1333                    }
1334                    else if (cmp == 0)
1335                    {
1336                        // Sort further by ascending bundle ID.
1337                        long middleId = ((IModule) modules.get(middle)).getBundle().getBundleId();
1338                        long exportId = module.getBundle().getBundleId();
1339                        if (middleId < exportId)
1340                        {
1341                            top = middle + 1;
1342                        }
1343                        else
1344                        {
1345                            bottom = middle - 1;
1346                        }
1347                    }
1348                    else
1349                    {
1350                        top = middle + 1;
1351                    }
1352                }
1353    
1354                // Ignore duplicates.
1355                if ((top >= modules.size()) || (modules.get(top) != module))
1356                {
1357                    modules.add(top, module);
1358                }
1359            }
1360    
1361            map.put(module.getSymbolicName(), modules);
1362    
1363            return (IModule) modules.get(0);
1364        }
1365    }