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 }