ExecutionPlan


1   /*
2    * FindBugs - Find bugs in Java programs
3    * Copyright (C) 2004,2005 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.plan;
21  
22  import java.util.Arrays  ;
23  import java.util.Collection  ;
24  import java.util.Comparator  ;
25  import java.util.HashMap  ;
26  import java.util.HashSet  ;
27  import java.util.Iterator  ;
28  import java.util.LinkedList  ;
29  import java.util.List  ;
30  import java.util.Map  ;
31  import java.util.Set  ;
32  
33  import edu.umd.cs.findbugs.DetectorFactory;
34  import edu.umd.cs.findbugs.DetectorFactoryChooser;
35  import edu.umd.cs.findbugs.DetectorFactoryCollection;
36  import edu.umd.cs.findbugs.Plugin;
37  import edu.umd.cs.findbugs.SystemProperties;
38  import edu.umd.cs.findbugs.graph.DepthFirstSearch;
39  
40  /**
41   * A plan for executing Detectors on an application.
42   * Automatically assigns Detectors to passes and orders
43   * Detectors within each pass based on ordering constraints
44   * specified in the plugin descriptor(s).
45   *
46   * @author David Hovemeyer
47   */
48  public class ExecutionPlan {
49  
50      public static final boolean DEBUG = SystemProperties.getBoolean("findbugs.execplan.debug");
51  
52      private List  <Plugin> pluginList;
53      private DetectorFactoryChooser factoryChooser;
54      private LinkedList  <AnalysisPass> passList;
55      private Map  <String  , DetectorFactory> factoryMap;
56      private List  <DetectorOrderingConstraint> interPassConstraintList;
57      private List  <DetectorOrderingConstraint> intraPassConstraintList;
58      private Set  <DetectorFactory> assignedToPassSet;
59  
60      /**
61       * Constructor.
62       * Creates an empty plan.
63       */
64      public ExecutionPlan() {
65          this.pluginList = new LinkedList  <Plugin>();
66          this.factoryChooser = new DetectorFactoryChooser() {
67              public boolean choose(DetectorFactory factory) {
68                  return true;
69              }
70          };
71          this.passList = new LinkedList  <AnalysisPass>();
72          this.factoryMap = new HashMap  <String  , DetectorFactory>();
73          this.interPassConstraintList = new LinkedList  <DetectorOrderingConstraint>();
74          this.intraPassConstraintList = new LinkedList  <DetectorOrderingConstraint>();
75          this.assignedToPassSet = new HashSet  <DetectorFactory>();
76      }
77      
78      /**
79       * Set the DetectorFactoryChooser to use to select which
80       * detectors to enable.  This must be called before any Plugins
81       * are added to the execution plan.
82       */
83      public void setDetectorFactoryChooser(DetectorFactoryChooser factoryChooser) {
84          this.factoryChooser = factoryChooser;
85      }
86  
87      /**
88       * Add a Plugin whose Detectors should be added to the execution plan.
89       */
90      public void addPlugin(Plugin plugin) throws OrderingConstraintException {
91          pluginList.add(plugin);
92          
93          // Add ordering constraints
94          copyTo(plugin.interPassConstraintIterator(), interPassConstraintList);
95          copyTo(plugin.intraPassConstraintIterator(), intraPassConstraintList);
96          
97          // Add detector factories
98          for (Iterator  <DetectorFactory> i = plugin.detectorFactoryIterator(); i.hasNext(); ) {
99              DetectorFactory factory = i.next();
100             if (!factoryChooser.choose(factory))
101                 continue;
102             if (factoryMap.put(factory.getFullName(), factory) != null) {
103                 throw new OrderingConstraintException("Detector " + factory.getFullName() +
104                         " is defined by more than one plugin");
105             }
106         }
107     }
108 
109     /**
110      * Build the execution plan.
111      * Using the ordering constraints specified in the
112      * plugin descriptor(s), assigns Detectors to passes
113      * and orders the Detectors within those passes.
114      */
115     public void build() throws OrderingConstraintException {
116         // Build inter-pass constraint graph
117         Map  <String  , DetectorNode> nodeMap = new HashMap  <String  , DetectorNode>();
118         ConstraintGraph interPassConstraintGraph = buildConstraintGraph(
119             nodeMap,
120             new HashSet  <DetectorFactory>(factoryMap.values()),
121             interPassConstraintList);
122         if (DEBUG) System.out.println(interPassConstraintGraph.getNumVertices() +
123             " nodes in inter-pass constraint graph");
124 
125         // Build list of analysis passes.
126         // This will assign all detectors referenced in inter- or intra-pass
127         // ordering constraints to passes.  Detectors with any ordering
128         // constraint will be left unassigned.
129         buildPassList(interPassConstraintGraph);
130 
131         // Sort each pass by intra-pass ordering constraints.
132         // This may assign some previously unassigned detectors to passes.
133         for (AnalysisPass pass : passList) {
134             sortPass(intraPassConstraintList, factoryMap, pass);
135         }
136         
137         // If there are any unassigned detectors remaining,
138         // add them to the final pass.
139         if (factoryMap.size() > assignedToPassSet.size()) {
140             AnalysisPass lastPass;
141             if (passList.isEmpty()) {
142                 lastPass = new AnalysisPass();
143                 addPass(lastPass);
144             } else {
145                 lastPass = passList.getLast();
146             }
147             
148             Set  <DetectorFactory> unassignedSet = getUnassignedSet();
149             for (DetectorFactory factory : unassignedSet) {
150                 assignToPass(factory, lastPass);
151             }
152             appendDetectorsToPass(unassignedSet, lastPass);
153         }
154     }
155     
156     /**
157      * Get an Iterator over the AnalysisPasses.
158      */
159     public Iterator  <AnalysisPass> passIterator() {
160         return passList.iterator();
161     }
162     
163     /**
164      * Get the number of passes in the execution plan.
165      * 
166      * @return the number of passes in the execution plan
167      */
168     public int getNumPasses() {
169         return passList.size();
170     }
171 
172     private static<T> void copyTo(Iterator  <T> iter, Collection  <T> dest) {
173         while (iter.hasNext()) {
174             dest.add(iter.next());
175         }
176     }
177 
178     /**
179      * Build a constraint graph.
180      * This represents ordering constraints between Detectors.
181      * A topological sort of the constraint graph will yield a
182      * correct ordering of the detectors (which may mean either
183      * passes or an ordering within a single pass, depending on
184      * whether the constraints are inter-pass or intra-pass).
185      *
186      * @param nodeMap        map to be populated with detector
187      *                       class names to constraint graph nodes for
188      *                       those detectors
189      * @param factorySet     build the graph using these DetectorFactories as nodes
190      * @param constraintList List of ordering constraints
191      * @return the ConstraintGraph
192      */
193     private ConstraintGraph buildConstraintGraph(
194         Map  <String  , DetectorNode> nodeMap,
195         Set  <DetectorFactory> factorySet,
196         List  <DetectorOrderingConstraint> constraintList) throws OrderingConstraintException {
197 
198         ConstraintGraph result = new ConstraintGraph();
199 
200         for (DetectorOrderingConstraint constraint : constraintList) {
201             Set  <DetectorNode> earlierSet = addOrCreateDetectorNodes(
202                     constraint.getEarlier(), nodeMap, factorySet, result);
203             Set  <DetectorNode> laterSet = addOrCreateDetectorNodes(
204                     constraint.getLater(), nodeMap, factorySet, result);
205 
206             createConstraintEdges(result, earlierSet, laterSet, constraint);
207         }
208 
209         return result;
210     }
211     
212     private Set  <DetectorFactory> selectDetectors(
213             DetectorFactorySelector selector, Set  <DetectorFactory> candidateSet) {
214         Set  <DetectorFactory> result = new HashSet  <DetectorFactory>();
215         for (DetectorFactory factory : candidateSet) {
216             if (selector.selectFactory(factory)) {
217                 result.add(factory);
218             }
219         }
220         return result;
221     }
222 
223     private Set  <DetectorNode> addOrCreateDetectorNodes(
224             DetectorFactorySelector selector,
225             Map  <String  , DetectorNode> nodeMap,
226             Set  <DetectorFactory> factorySet,
227             ConstraintGraph constraintGraph) throws OrderingConstraintException {
228         HashSet  <DetectorNode> result = new HashSet  <DetectorNode>();
229         
230         Set  <DetectorFactory> chosenSet = selectDetectors(selector, factorySet);
231 
232         for (DetectorFactory factory : chosenSet) {
233             DetectorNode node = addOrCreateDetectorNode(factory, nodeMap, constraintGraph);
234             result.add(node);
235         }
236 
237         return result;
238     }
239 
240     private DetectorNode addOrCreateDetectorNode(
241             DetectorFactory factory,
242             Map  <String  , DetectorNode> nodeMap,
243             ConstraintGraph constraintGraph)
244         throws OrderingConstraintException {
245         DetectorNode node = nodeMap.get(factory.getFullName());
246         if (node == null) {
247             node = new DetectorNode(factory);
248             nodeMap.put(factory.getFullName(), node);
249             constraintGraph.addVertex(node);
250         }
251         return node;
252     }
253     
254     private void createConstraintEdges(
255             ConstraintGraph result,
256             Set  <DetectorNode> earlierSet,
257             Set  <DetectorNode> laterSet, DetectorOrderingConstraint constraint) throws OrderingConstraintException {
258         
259         // It is perfectly fine for a constraint to produce no edges
260         // if any detector it specifies is not enabled.
261         if (earlierSet.isEmpty() || laterSet.isEmpty())
262             return;
263 
264         for (DetectorNode earlier : earlierSet) {
265             for (DetectorNode later : laterSet) {
266                 result.createEdge(earlier, later);
267             }
268         }
269     }
270 
271     private void buildPassList(ConstraintGraph constraintGraph)
272             throws OrderingConstraintException {
273 
274         while (constraintGraph.getNumVertices() > 0) {
275             List  <DetectorNode> inDegreeZeroList = new LinkedList  <DetectorNode>();
276             // Get all of the detectors nodes with in-degree 0.
277             // These have no unsatisfied prerequisites, and thus can
278             // be chosen for the current pass.
279             for (Iterator  <DetectorNode> i = constraintGraph.vertexIterator(); i.hasNext(); ) {
280                 DetectorNode node = i.next();
281                 if (constraintGraph.getNumIncomingEdges(node) == 0) 
282                     inDegreeZeroList.add(node);
283                 
284             }
285 
286             if (inDegreeZeroList.isEmpty())
287                 throw new OrderingConstraintException("Cycle in inter-pass ordering constraints");
288 
289             // Remove all of the chosen detectors from the constraint graph.
290             for (DetectorNode node : inDegreeZeroList) {
291                 constraintGraph.removeVertex(node);
292             }
293 
294             // Create analysis pass and add detector factories.
295             // Note that this just makes the detectors members of the pass:
296             // it doesn't assign them a position in the pass.
297             AnalysisPass pass = new AnalysisPass();
298             addPass(pass);
299             for (DetectorNode node : inDegreeZeroList) {
300                 assignToPass(node.getFactory(), pass);
301             }
302 
303         }
304     }
305     
306     private void addPass(AnalysisPass pass) {
307         if (DEBUG) {
308             System.out.println("Adding pass " + passList.size());
309         }
310         passList.add(pass);
311     }
312 
313     private void sortPass(
314             List  <DetectorOrderingConstraint> constraintList,
315             Map  <String  , DetectorFactory> factoryMap,
316             AnalysisPass pass)
317         throws OrderingConstraintException {
318 
319         // Build set of all (initial) detectors in pass
320         Set  <DetectorFactory> detectorSet = new HashSet  <DetectorFactory>(pass.getMembers());
321         if (DEBUG) {
322             System.out.println(detectorSet.size() + " detectors currently in this pass");
323         }
324         
325         // Build list of ordering constraints in this pass only
326         List  <DetectorOrderingConstraint> passConstraintList =
327             new LinkedList  <DetectorOrderingConstraint>();
328         for (DetectorOrderingConstraint constraint : constraintList) {
329             // Does this constraint specify any detectors in this pass?
330             // If so, add it to the pass constraints
331             if (selectDetectors(constraint.getEarlier(), detectorSet).size() > 0
332                     || selectDetectors(constraint.getLater(), detectorSet).size() > 0) {
333                 passConstraintList.add(constraint);
334             }
335         }
336         if (DEBUG) {
337             System.out.println(passConstraintList.size() + " constraints are applicable for this pass");
338         }
339         
340         // Build set of all detectors available to be added to this pass
341         HashSet  <DetectorFactory> availableSet = new HashSet  <DetectorFactory>();
342         availableSet.addAll(detectorSet);
343         availableSet.addAll(getUnassignedSet());
344 
345         // Build intra-pass constraint graph
346         Map  <String  , DetectorNode> nodeMap = new HashMap  <String  , DetectorNode>();
347         ConstraintGraph constraintGraph = buildConstraintGraph(
348             nodeMap, availableSet, passConstraintList);
349         if (DEBUG) {
350             System.out.println("Pass constraint graph:");
351             dumpGraph(constraintGraph);
352         }
353         
354         // See if any detectors were brought into the pass by an intrapass ordering constraint.
355         // Assign them to the pass officially.
356         for (DetectorNode node : nodeMap.values()) {
357             if (!pass.contains(node.getFactory())) {
358                 assignToPass(node.getFactory(), pass);
359             }
360         }
361 
362         // Perform DFS, check for cycles
363         DepthFirstSearch<ConstraintGraph, ConstraintEdge, DetectorNode> dfs =
364             new DepthFirstSearch<ConstraintGraph, ConstraintEdge, DetectorNode>(constraintGraph);
365         dfs.search();
366         if (dfs.containsCycle())
367             throw new OrderingConstraintException("Cycle in intra-pass ordering constraints!");
368 
369         // Do a topological sort to put the detectors in the pass
370         // in the right order.
371         for (Iterator  <DetectorNode> i = dfs.topologicalSortIterator(); i.hasNext(); ) {
372             DetectorNode node = i.next();
373             appendToPass(node.getFactory(), pass);
374         }
375         
376         // Add any detectors not explicitly involved in intra-pass ordering constraints
377         // to the end of the pass.
378         appendDetectorsToPass(pass.getUnpositionedMembers(), pass);
379     }
380     
381     private Set  <DetectorFactory> getUnassignedSet() {
382         Set  <DetectorFactory> unassignedSet = new HashSet  <DetectorFactory>();
383         unassignedSet.addAll(factoryMap.values());
384         unassignedSet.removeAll(assignedToPassSet);
385         return unassignedSet;
386     }
387 
388     /**
389      * Make a DetectorFactory a member of an AnalysisPass.
390      */
391     private void assignToPass(DetectorFactory factory, AnalysisPass pass) {
392         pass.addToPass(factory);
393         assignedToPassSet.add(factory);
394     }
395 
396     /**
397      * Append a DetectorFactory to the end position in an AnalysisPass.
398      * The DetectorFactory must be a member of the pass.
399      */
400     private void appendToPass(DetectorFactory factory, AnalysisPass pass)
401             throws OrderingConstraintException {
402         pass.append(factory);
403     }
404     
405     private void appendDetectorsToPass(Collection  <DetectorFactory> detectorSet, AnalysisPass pass)
406             throws OrderingConstraintException {
407         DetectorFactory[] unassignedList = detectorSet.toArray(new DetectorFactory[detectorSet.size()]);
408         Arrays.sort(unassignedList, new Comparator  <DetectorFactory>() {
409             public int compare(DetectorFactory a, DetectorFactory b) {
410                 // Sort first by plugin id...
411                 int cmp = a.getPlugin().getPluginId().compareTo(b.getPlugin().getPluginId());
412                 if (cmp != 0)
413                     return cmp;
414                 // Then by order specified in plugin descriptor
415                 return a.getPositionSpecifiedInPluginDescriptor() - b.getPositionSpecifiedInPluginDescriptor();
416             }
417         });
418         for (DetectorFactory factory : unassignedList) {
419             appendToPass(factory, pass);
420         }
421     }
422 
423     private void print() {
424         int passCount = 0;
425         for (Iterator  <AnalysisPass> i = passList.iterator(); i.hasNext(); ++passCount) {
426             System.out.println("Pass " + passCount);
427             AnalysisPass pass = i.next();
428             for (Iterator  <DetectorFactory> j = pass.iterator(); j.hasNext(); ) {
429                 DetectorFactory factory = j.next();
430                 System.out.println("  " + factory.getFullName());
431             }
432         }
433     }
434 
435     private void dumpGraph(ConstraintGraph graph) {
436         for (Iterator  <ConstraintEdge> i = graph.edgeIterator(); i.hasNext();) {
437             ConstraintEdge edge = i.next();
438             System.out.println(
439                 edge.getSource().getFactory().getFullName() + " ==> " +
440                 edge.getTarget().getFactory().getFullName());
441         }
442     }
443 
444     public static void main(String  [] argv) throws Exception   {
445         DetectorFactoryCollection detectorFactoryCollection =
446             DetectorFactoryCollection.instance();
447 
448         ExecutionPlan execPlan = new ExecutionPlan();
449 
450         for (String   pluginId : argv) {
451             Plugin plugin = detectorFactoryCollection.getPluginById(pluginId);
452             if (plugin != null)
453                 execPlan.addPlugin(plugin);
454         }
455 
456         execPlan.build();
457 
458         System.out.println(execPlan.getNumPasses() + " passes in plan");
459         execPlan.print();
460     }
461 }
462 
463 // vim:ts=4
464
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags