GroupingChecker


1   /*******************************************************************************
2    * Copyright (c) 2004, 2007 IBM Corporation and others. All rights reserved.
3    * This program and the accompanying materials are made available under the
4    * terms of the Eclipse Public License v1.0 which accompanies this distribution,
5    * and is available at http://www.eclipse.org/legal/epl-v10.html
6    * 
7    * Contributors: IBM Corporation - initial API and implementation
8    ******************************************************************************/
9   package org.eclipse.osgi.internal.module;
10  
11  import java.util.*;
12  import org.eclipse.osgi.service.resolver.BundleSpecification;
13  
14  /*
15   * The GroupingChecker checks the 'uses' directive on exported packages for consistency
16   */
17  public class GroupingChecker {
18      final PackageRoots nullPackageRoots = new PackageRoots(null, null);
19      // a mapping of bundles to their package roots; keyed by
20      // ResolverBundle -> HashMap of packages; keyed by
21      // package name -> PackageRoots[]
22      private HashMap bundles = new HashMap();
23  
24      /*
25       * This method fully populates a bundles package roots for the purpose of resolving
26       * a dynamic import.  Package roots must be fully populated because we need all the
27       * roots to do proper uses constraint verification on a dynamic import supplier.
28       */
29      public void populateRoots(ResolverBundle bundle) {
30          bundles.remove(bundle);
31          // process all requires
32          BundleConstraint[] requires = bundle.getRequires();
33          for (int j = 0; j < requires.length; j++) {
34              ResolverBundle selectedSupplier = (ResolverBundle) requires[j].getSelectedSupplier();
35              if (selectedSupplier != null)
36                  isConsistentInternal(bundle, selectedSupplier, new ArrayList(1), true, null);
37          }
38          // process all imports
39          ResolverImport[] imports = bundle.getImportPackages();
40          for (int j = 0; j < imports.length; j++) {
41              ResolverExport selectedSupplier = (ResolverExport) imports[j].getSelectedSupplier();
42              if (selectedSupplier != null)
43                  isConsistentInternal(bundle, selectedSupplier, true, null);
44          }
45      }
46  
47      /*
48       * Verifies the uses constraint consistency for the requiringBundle with the possible matching bundle.
49       * If an inconsistency is found the export inconsistency is returned; otherwise null is returned
50       */
51      public PackageRoots[][] isConsistent(ResolverBundle requiringBundle, ResolverBundle matchingBundle) {
52          ArrayList results = isConsistentInternal(requiringBundle, matchingBundle, new ArrayList(1), false, null);
53          return results == null ? null : (PackageRoots[][]) results.toArray(new PackageRoots[results.size()][]);
54      }
55  
56      private ArrayList isConsistentInternal(ResolverBundle requiringBundle, ResolverBundle matchingBundle, ArrayList visited, boolean dynamicImport, ArrayList results) {
57          // needed to prevent endless cycles
58          if (visited.contains(matchingBundle))
59              return results;
60          visited.add(matchingBundle);
61          // check that the packages exported by the matching bundle are consistent
62          ResolverExport[] matchingExports = matchingBundle.getExportPackages();
63          for (int i = 0; i < matchingExports.length; i++) {
64              if (matchingExports[i].isDropped())
65                  continue;
66              results = isConsistentInternal(requiringBundle, matchingExports[i], dynamicImport, results);
67          }
68          // check that the packages from reexported bundles are consistent
69          BundleConstraint[] supplierRequires = matchingBundle.getRequires();
70          for (int j = 0; j < supplierRequires.length; j++) {
71              ResolverBundle reexported = (ResolverBundle) supplierRequires[j].getSelectedSupplier();
72              if (reexported == null || !((BundleSpecification) supplierRequires[j].getVersionConstraint()).isExported())
73                  continue;
74              results = isConsistentInternal(requiringBundle, reexported, visited, dynamicImport, results);
75          }
76          return results;
77      }
78  
79      /*
80       * Verifies the uses constraint consistency for the importingBundle with the possible matching export.
81       * If an inconsistency is found the export returned; otherwise null is returned
82       */
83      public PackageRoots[][] isConsistent(ResolverBundle importingBundle, ResolverExport matchingExport) {
84          ArrayList results = isConsistentInternal(importingBundle, matchingExport, false, null);
85          return results == null ? null : (PackageRoots[][]) results.toArray(new PackageRoots[results.size()][]);
86      }
87  
88      /*
89       * Verifies the uses constraint consistency for the importingBundle with the possible dynamic matching export.
90       * If an inconsistency is found the export returned; otherwise null is returned.
91       * Dynamic imports must perform extra checks to ensure that existing wires to package roots are 
92       * consistent with the possible matching dynamic export.
93       */
94      public PackageRoots[][] isDynamicConsistent(ResolverBundle importingBundle, ResolverExport matchingExport) {
95          ArrayList results = isConsistentInternal(importingBundle, matchingExport, true, null);
96          return results == null ? null : (PackageRoots[][]) results.toArray(new PackageRoots[results.size()][]);
97      }
98  
99      private ArrayList isConsistentInternal(ResolverBundle importingBundle, ResolverExport matchingExport, boolean dyanamicImport, ArrayList results) {
100         PackageRoots exportingRoots = getPackageRoots(matchingExport.getExporter(), matchingExport.getName(), null);
101         // check that the exports uses packages are consistent with existing package roots
102         results = exportingRoots.isConsistentClassSpace(importingBundle, null, results);
103         if (!dyanamicImport)
104             return results;
105         // for dynamic imports we must check that each existing root is consistent with the possible matching export
106         PackageRoots importingRoots = getPackageRoots(importingBundle, matchingExport.getName(), null);
107         HashMap importingPackages = (HashMap) bundles.get(importingBundle);
108         if (importingPackages != null)
109             for (Iterator allImportingPackages = importingPackages.values().iterator(); allImportingPackages.hasNext();) {
110                 PackageRoots roots = (PackageRoots) allImportingPackages.next();
111                 if (roots != importingRoots)
112                     results = roots.isConsistentClassSpace(exportingRoots, null, results);
113             }
114         return results;
115     }
116 
117     /*
118      * returns package roots for a specific package name for a specific bundle
119      */
120     PackageRoots getPackageRoots(ResolverBundle bundle, String   packageName, ArrayList visited) {
121         HashMap packages = (HashMap) bundles.get(bundle);
122         if (packages == null) {
123             packages = new HashMap(5);
124             bundles.put(bundle, packages);
125         }
126         PackageRoots packageRoots = (PackageRoots) packages.get(packageName);
127         if (packageRoots == null) {
128             packageRoots = createPackageRoots(bundle, packageName, visited == null ? new ArrayList(1) : visited);
129             packages.put(packageName, packageRoots);
130         }
131         return packageRoots != null ? packageRoots : nullPackageRoots;
132     }
133 
134     private PackageRoots createPackageRoots(ResolverBundle bundle, String   packageName, ArrayList visited) {
135         if (visited.contains(bundle))
136             return null;
137         visited.add(bundle); // prevent endless cycles
138         // check imports
139         ResolverImport imported = bundle.getImport(packageName);
140         if (imported != null && imported.getSelectedSupplier() != null) {
141             // make sure we are not resolved to our own import
142             ResolverExport selectedExport = (ResolverExport) imported.getSelectedSupplier();
143             if (selectedExport.getExporter() != bundle) {
144                 // found resolved import; get the roots from the resolved exporter;
145                 // this is all the roots if the package is imported
146                 return getPackageRoots(selectedExport.getExporter(), packageName, visited);
147             }
148         }
149         // check if the bundle exports the package
150         ResolverExport export = bundle.getExport(packageName);
151         ArrayList roots = new ArrayList(0);
152         // check roots from required bundles
153         BundleConstraint[] requires = bundle.getRequires();
154         for (int i = 0; i < requires.length; i++) {
155             ResolverBundle supplier = (ResolverBundle) requires[i].getSelectedSupplier();
156             if (supplier == null)
157                 continue; // no supplier, probably optional
158             if (supplier.getExport(packageName) != null) {
159                 // the required bundle exports the package; get the package roots from it
160                 PackageRoots requiredRoots = getPackageRoots(supplier, packageName, visited);
161                 if (requiredRoots != null)
162                     roots.add(requiredRoots);
163             } else {
164                 // the bundle does not export the package; but it may reexport another bundle that does
165                 BundleConstraint[] supplierRequires = supplier.getRequires();
166                 for (int j = 0; j < supplierRequires.length; j++) {
167                     ResolverBundle reexported = (ResolverBundle) supplierRequires[j].getSelectedSupplier();
168                     if (reexported == null || !((BundleSpecification) supplierRequires[j].getVersionConstraint()).isExported())
169                         continue;
170                     if (reexported.getExport(packageName) != null) {
171                         // the reexported bundle exports the package; get the package roots from it
172                         PackageRoots reExportedRoots = getPackageRoots(reexported, packageName, visited);
173                         if (reexported != null)
174                             roots.add(reExportedRoots);
175                     }
176                 }
177             }
178         }
179         if (export != null || roots.size() > 1) {
180             PackageRoots[] requiredRoots = (PackageRoots[]) roots.toArray(new PackageRoots[roots.size()]);
181             if (export == null) {
182                 PackageRoots superSet = requiredRoots[0];
183                 for (int i = 1; i < requiredRoots.length; i++) {
184                     if (requiredRoots[i].superSet(superSet)) {
185                         superSet = requiredRoots[i];
186                     } else if (!superSet.superSet(requiredRoots[i])) {
187                         superSet = null;
188                         break;
189                     }
190                 }
191                 if (superSet != null)
192                     return superSet;
193             }
194             // in this case we cannot share the package roots object; must create one specific for this bundle
195             PackageRoots result = new PackageRoots(packageName, bundle);
196             // first merge all the roots from required bundles
197             for (int i = 0; i < requiredRoots.length; i++)
198                 result.merge(requiredRoots[i]);
199             if (export != null)
200                 // always add this bundles export to the end if it exports the package
201                 result.addRoot(export);
202             return result;
203         }
204         return (PackageRoots) (roots.size() == 0 ? nullPackageRoots : roots.get(0));
205     }
206 
207     public void clear() {
208         bundles.clear();
209     }
210 
211     public void clear(ResolverBundle rb) {
212         bundles.remove(rb);
213     }
214 
215     class PackageRoots {
216         private String   name;
217         private ResolverBundle bundle;
218         private ResolverExport[] roots;
219 
220         PackageRoots(String   name, ResolverBundle bundle) {
221             this.name = name;
222             this.bundle = bundle;
223         }
224 
225         public boolean hasRoots() {
226             return roots != null && roots.length > 0;
227         }
228 
229         public void addRoot(ResolverExport export) {
230             if (roots == null) {
231                 roots = new ResolverExport[] {export};
232                 return;
233             }
234             // need to do an extra check to make sure we are not adding the same package name 
235             // from multiple versions of the same bundle
236             String   exportBSN = export.getExporter().getName();
237             if (exportBSN != null) {
238                 // first one wins
239                 for (int i = 0; i < roots.length; i++)
240                     if (exportBSN.equals(roots[i].getExporter().getName()))
241                         return;
242             }
243             if (!contains(export, roots)) {
244                 ResolverExport[] newRoots = new ResolverExport[roots.length + 1];
245                 System.arraycopy(roots, 0, newRoots, 0, roots.length);
246                 newRoots[roots.length] = export;
247                 roots = newRoots;
248             }
249         }
250 
251         private boolean contains(ResolverExport export, ResolverExport[] exports) {
252             for (int i = 0; i < exports.length; i++)
253                 if (exports[i] == export)
254                     return true;
255             return false;
256         }
257 
258         public void merge(PackageRoots packageRoots) {
259             if (packageRoots == null || packageRoots.roots == null)
260                 return;
261             int size = packageRoots.roots.length;
262             for (int i = 0; i < size; i++)
263                 addRoot(packageRoots.roots[i]);
264         }
265 
266         public ArrayList isConsistentClassSpace(ResolverBundle importingBundle, ArrayList visited, ArrayList results) {
267             if (roots == null)
268                 return results;
269             int size = roots.length;
270             for (int i = 0; i < size; i++) {
271                 ResolverExport root = roots[i];
272                 String  [] uses = root.getUsesDirective();
273                 if (uses == null)
274                     continue;
275                 if (visited == null)
276                     visited = new ArrayList(1);
277                 if (visited.contains(this))
278                     return results;
279                 visited.add(this);
280                 for (int j = 0; j < uses.length; j++) {
281                     if (uses[j].equals(root.getName()))
282                         continue;
283                     PackageRoots thisUsedRoots = getPackageRoots(root.getExporter(), uses[j], null);
284                     PackageRoots importingUsedRoots = getPackageRoots(importingBundle, uses[j], null);
285                     if (thisUsedRoots == importingUsedRoots)
286                         return results;
287                     if (thisUsedRoots != nullPackageRoots && importingUsedRoots != nullPackageRoots)
288                         if (!(subSet(thisUsedRoots.roots, importingUsedRoots.roots) || subSet(importingUsedRoots.roots, thisUsedRoots.roots))) {
289                             if (results == null)
290                                 results = new ArrayList(1);
291                             results.add(new PackageRoots[] {this, importingUsedRoots});
292                         }
293                     // need to check the usedRoots consistency for transitive closure
294                     results = thisUsedRoots.isConsistentClassSpace(importingBundle, visited, results);
295                 }
296             }
297             return results;
298         }
299 
300         public ArrayList isConsistentClassSpace(PackageRoots exportingRoots, ArrayList visited, ArrayList results) {
301             if (roots == null)
302                 return results;
303             int size = roots.length;
304             for (int i = 0; i < size; i++) {
305                 ResolverExport root = roots[i];
306                 String  [] uses = root.getUsesDirective();
307                 if (uses == null)
308                     continue;
309                 if (visited == null)
310                     visited = new ArrayList(1);
311                 if (visited.contains(this))
312                     return results;
313                 visited.add(this);
314                 for (int j = 0; j < uses.length; j++) {
315                     if (uses[j].equals(root.getName()) || !uses[j].equals(exportingRoots.name))
316                         continue;
317                     PackageRoots thisUsedRoots = getPackageRoots(root.getExporter(), uses[j], null);
318                     PackageRoots exportingUsedRoots = getPackageRoots(exportingRoots.bundle, uses[j], null);
319                     if (thisUsedRoots == exportingRoots)
320                         return results;
321                     if (thisUsedRoots != nullPackageRoots && exportingUsedRoots != nullPackageRoots)
322                         if (!(subSet(thisUsedRoots.roots, exportingUsedRoots.roots) || subSet(exportingUsedRoots.roots, thisUsedRoots.roots))) {
323                             if (results == null)
324                                 results = new ArrayList(1);
325                             results.add(new PackageRoots[] {this, exportingUsedRoots});
326                         }
327                     // need to check the usedRoots consistency for transitive closure
328                     results = thisUsedRoots.isConsistentClassSpace(exportingRoots, visited, results);
329                 }
330             }
331             return results;
332         }
333 
334         // TODO this is a behavioral change; before we only required 1 supplier to match; now roots must be subsets
335         private boolean subSet(ResolverExport[] superSet, ResolverExport[] subSet) {
336             for (int i = 0; i < subSet.length; i++) {
337                 boolean found = false;
338                 for (int j = 0; j < superSet.length; j++)
339                     // compare by exporter in case the bundle exports the package multiple times
340                     if (subSet[i].getExporter() == superSet[j].getExporter()) {
341                         found = true;
342                         break;
343                     }
344                 if (!found)
345                     return false;
346             }
347             return true;
348         }
349 
350         public boolean superSet(PackageRoots subSet) {
351             return subSet(roots, subSet.roots);
352         }
353 
354         public String   getName() {
355             return name;
356         }
357 
358         public ResolverExport[] getRoots() {
359             return roots;
360         }
361     }
362 }
363
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags