executionplan.java

A static analysis tool to find bugs in Java programs

/*
 * FindBugs - Find bugs in Java programs
 * Copyright (C) 2004,2005 University of Maryland
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package edu.umd.cs.findbugs.plan;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import edu.umd.cs.findbugs.DetectorFactory;
import edu.umd.cs.findbugs.DetectorFactoryChooser;
import edu.umd.cs.findbugs.DetectorFactoryCollection;
import edu.umd.cs.findbugs.FindBugs2;
import edu.umd.cs.findbugs.Plugin;
import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.graph.DepthFirstSearch;

/**
 * A plan for executing Detectors on an application.
 * Automatically assigns Detectors to passes and orders
 * Detectors within each pass based on ordering constraints
 * specified in the plugin descriptor(s).
 *
 * @author David Hovemeyer
 */
public class ExecutionPlan {

	public static final boolean DEBUG = SystemProperties.getBoolean("findbugs.execplan.debug");

	private List<Plugin> pluginList;
	private DetectorFactoryChooser factoryChooser;
	private LinkedList<AnalysisPass> passList;
	private Map<String, DetectorFactory> factoryMap;
	private List<DetectorOrderingConstraint> interPassConstraintList;
	private List<DetectorOrderingConstraint> intraPassConstraintList;
	private Set<DetectorFactory> assignedToPassSet;

	/**
	 * Constructor.
	 * Creates an empty plan.
	 */
	public ExecutionPlan() {
		this.pluginList = new LinkedList<Plugin>();
		this.factoryChooser = new DetectorFactoryChooser() {
			public boolean choose(DetectorFactory factory) {
				return true;
			}

			public void enable(DetectorFactory factory) {
			   // OK...
			}
		};
		this.passList = new LinkedList<AnalysisPass>();
		this.factoryMap = new HashMap<String, DetectorFactory>();
		this.interPassConstraintList = new LinkedList<DetectorOrderingConstraint>();
		this.intraPassConstraintList = new LinkedList<DetectorOrderingConstraint>();
		this.assignedToPassSet = new HashSet<DetectorFactory>();
	}

	/**
	 * Set the DetectorFactoryChooser to use to select which
	 * detectors to enable.  This must be called before any Plugins
	 * are added to the execution plan.
	 */
	public void setDetectorFactoryChooser(DetectorFactoryChooser factoryChooser) {
		this.factoryChooser = factoryChooser;
	}

	/**
	 * Add a Plugin whose Detectors should be added to the execution plan.
	 */
	public void addPlugin(Plugin plugin) throws OrderingConstraintException {
		pluginList.add(plugin);

		// Add ordering constraints
		copyTo(plugin.interPassConstraintIterator(), interPassConstraintList);
		copyTo(plugin.intraPassConstraintIterator(), intraPassConstraintList);

		// Add detector factories
		for (Iterator<DetectorFactory> i = plugin.detectorFactoryIterator(); i.hasNext(); ) {
			DetectorFactory factory = i.next();
			if (factoryMap.put(factory.getFullName(), factory) != null) {
				throw new OrderingConstraintException("Detector " + factory.getFullName() +
						" is defined by more than one plugin");
			}
		}
	}

	/**
	 * Build the execution plan.
	 * Using the ordering constraints specified in the
	 * plugin descriptor(s), assigns Detectors to passes
	 * and orders the Detectors within those passes.
	 */
	public void build() throws OrderingConstraintException {

		for(DetectorFactory detectorFactory : factoryMap.values()) {
			detectorFactory.setEnabledButNonReporting(false);
		}

		ArrayList<DetectorOrderingConstraint> allConstraints = new ArrayList<DetectorOrderingConstraint>(interPassConstraintList.size() + intraPassConstraintList.size());
		allConstraints.addAll(interPassConstraintList);
		allConstraints.addAll(intraPassConstraintList);

		Map<String, DetectorNode> nodeMapAll = new HashMap<String, DetectorNode>();
		ConstraintGraph allPassConstraintGraph = buildConstraintGraph(
			nodeMapAll,
			new HashSet<DetectorFactory>(factoryMap.values()),
			allConstraints);
		boolean change;
		do {
			change = false;
			for(Iterator<DetectorNode> i = allPassConstraintGraph.vertexIterator(); i.hasNext(); ) {
				DetectorNode end = i.next();
				if (factoryChooser.choose(end.getFactory())) {
					for(Iterator<ConstraintEdge> j = allPassConstraintGraph.incomingEdgeIterator(end); j.hasNext(); ) {
						DetectorNode start = j.next().getSource();
						DetectorFactory startFactory = start.getFactory();
						if (!factoryChooser.choose(startFactory)) {
							factoryChooser.enable(startFactory);
							change = true;
							if (DEBUG || FindBugs2.DEBUG)
								System.out.println("Dependences force enabling of " + startFactory.getFullName());
						}

					}
				}

			}
		} while (change);

		for(Iterator<Map.Entry<String,DetectorFactory>> i = factoryMap.entrySet().iterator(); i.hasNext(); ) {
			Map.Entry<String,DetectorFactory> e = i.next();
			if (!factoryChooser.choose(e.getValue()))
					i.remove();
		}

		// Build inter-pass constraint graph
		Map<String, DetectorNode> nodeMap = new HashMap<String, DetectorNode>();
		ConstraintGraph interPassConstraintGraph = buildConstraintGraph(
			nodeMap,
			new HashSet<DetectorFactory>(factoryMap.values()),
			interPassConstraintList);
		if (DEBUG) System.out.println(interPassConstraintGraph.getNumVertices() +
			" nodes in inter-pass constraint graph");

		// Build list of analysis passes.
		// This will assign all detectors referenced in inter- or intra-pass
		// ordering constraints to passes.  Detectors with any ordering
		// constraint will be left unassigned.
		buildPassList(interPassConstraintGraph);

		// Sort each pass by intra-pass ordering constraints.
		// This may assign some previously unassigned detectors to passes.
		for (AnalysisPass pass : passList) {
			sortPass(intraPassConstraintList, factoryMap, pass);
		}

		// If there are any unassigned detectors remaining,
		// add them to the final pass.
		if (factoryMap.size() > assignedToPassSet.size()) {
			AnalysisPass lastPass;
			if (passList.isEmpty()) {
				lastPass = new AnalysisPass();
				addPass(lastPass);
			} else {
				lastPass = passList.getLast();
			}

			Set<DetectorFactory> unassignedSet = getUnassignedSet();
			for (DetectorFactory factory : unassignedSet) {
				assignToPass(factory, lastPass);
			}
			appendDetectorsToPass(unassignedSet, lastPass);
		}
	}

	/**
	 * Get an Iterator over the AnalysisPasses.
	 */
	public Iterator<AnalysisPass> passIterator() {
		return passList.iterator();
	}

	/**
	 * Get the number of passes in the execution plan.
	 * 
	 * @return the number of passes in the execution plan
	 */
	public int getNumPasses() {
		return passList.size();
	}

	private static<T> void copyTo(Iterator<T> iter, Collection<T> dest) {
		while (iter.hasNext()) {
			dest.add(iter.next());
		}
	}

	/**
	 * Build a constraint graph.
	 * This represents ordering constraints between Detectors.
	 * A topological sort of the constraint graph will yield a
	 * correct ordering of the detectors (which may mean either
	 * passes or an ordering within a single pass, depending on
	 * whether the constraints are inter-pass or intra-pass).
	 *
	 * @param nodeMap        map to be populated with detector
	 *                       class names to constraint graph nodes for
	 *                       those detectors
	 * @param factorySet     build the graph using these DetectorFactories as nodes
	 * @param constraintList List of ordering constraints
	 * @return the ConstraintGraph
	 */
	private ConstraintGraph buildConstraintGraph(
		Map<String, DetectorNode> nodeMap,
		Set<DetectorFactory> factorySet,
		List<DetectorOrderingConstraint> constraintList) throws OrderingConstraintException {

		ConstraintGraph result = new ConstraintGraph();

		for (DetectorOrderingConstraint constraint : constraintList) {
			Set<DetectorNode> earlierSet = addOrCreateDetectorNodes(
					constraint.getEarlier(), nodeMap, factorySet, result);
			Set<DetectorNode> laterSet = addOrCreateDetectorNodes(
					constraint.getLater(), nodeMap, factorySet, result);

			createConstraintEdges(result, earlierSet, laterSet, constraint);
		}

		return result;