executionplan.java

A static analysis tool to find bugs in Java programs

	}

	private Set<DetectorFactory> selectDetectors(
			DetectorFactorySelector selector, Set<DetectorFactory> candidateSet) {
		Set<DetectorFactory> result = new HashSet<DetectorFactory>();
		for (DetectorFactory factory : candidateSet) {
			if (selector.selectFactory(factory)) {
				result.add(factory);
			}
		}
		return result;
	}

	private Set<DetectorNode> addOrCreateDetectorNodes(
			DetectorFactorySelector selector,
			Map<String, DetectorNode> nodeMap,
			Set<DetectorFactory> factorySet,
			ConstraintGraph constraintGraph) throws OrderingConstraintException {
		HashSet<DetectorNode> result = new HashSet<DetectorNode>();

		Set<DetectorFactory> chosenSet = selectDetectors(selector, factorySet);

		for (DetectorFactory factory : chosenSet) {
			DetectorNode node = addOrCreateDetectorNode(factory, nodeMap, constraintGraph);
			result.add(node);
		}

		return result;
	}

	private DetectorNode addOrCreateDetectorNode(
			DetectorFactory factory,
			Map<String, DetectorNode> nodeMap,
			ConstraintGraph constraintGraph)
		throws OrderingConstraintException {
		DetectorNode node = nodeMap.get(factory.getFullName());
		if (node == null) {
			node = new DetectorNode(factory);
			nodeMap.put(factory.getFullName(), node);
			constraintGraph.addVertex(node);
		}
		return node;
	}

	private void createConstraintEdges(
			ConstraintGraph result,
			Set<DetectorNode> earlierSet,
			Set<DetectorNode> laterSet, DetectorOrderingConstraint constraint) throws OrderingConstraintException {

		// It is perfectly fine for a constraint to produce no edges
		// if any detector it specifies is not enabled.
		if (earlierSet.isEmpty() || laterSet.isEmpty())
			return;

		for (DetectorNode earlier : earlierSet) {
			for (DetectorNode later : laterSet) {
				result.createEdge(earlier, later);
			}
		}
	}

	private void buildPassList(ConstraintGraph constraintGraph)
			throws OrderingConstraintException {

		while (constraintGraph.getNumVertices() > 0) {
			List<DetectorNode> inDegreeZeroList = new LinkedList<DetectorNode>();
			// Get all of the detectors nodes with in-degree 0.
			// These have no unsatisfied prerequisites, and thus can
			// be chosen for the current pass.
			for (Iterator<DetectorNode> i = constraintGraph.vertexIterator(); i.hasNext(); ) {
				DetectorNode node = i.next();
				if (constraintGraph.getNumIncomingEdges(node) == 0) 
					inDegreeZeroList.add(node);

			}

			if (inDegreeZeroList.isEmpty())
				throw new OrderingConstraintException("Cycle in inter-pass ordering constraints");

			// Remove all of the chosen detectors from the constraint graph.
			for (DetectorNode node : inDegreeZeroList) {
				constraintGraph.removeVertex(node);
			}

			// Create analysis pass and add detector factories.
			// Note that this just makes the detectors members of the pass:
			// it doesn't assign them a position in the pass.
			AnalysisPass pass = new AnalysisPass();
			addPass(pass);
			for (DetectorNode node : inDegreeZeroList) {
				assignToPass(node.getFactory(), pass);
			}

		}
	}

	private void addPass(AnalysisPass pass) {
		if (DEBUG) {
			System.out.println("Adding pass " + passList.size());
		}
		passList.add(pass);
	}

	private void sortPass(
			List<DetectorOrderingConstraint> constraintList,
			Map<String, DetectorFactory> factoryMap,
			AnalysisPass pass)
		throws OrderingConstraintException {

		// Build set of all (initial) detectors in pass
		Set<DetectorFactory> detectorSet = new HashSet<DetectorFactory>(pass.getMembers());
		if (DEBUG) {
			System.out.println(detectorSet.size() + " detectors currently in this pass");
		}

		// Build list of ordering constraints in this pass only
		List<DetectorOrderingConstraint> passConstraintList =
			new LinkedList<DetectorOrderingConstraint>();
		for (DetectorOrderingConstraint constraint : constraintList) {
			// Does this constraint specify any detectors in this pass?
			// If so, add it to the pass constraints
			if (selectDetectors(constraint.getEarlier(), detectorSet).size() > 0
					|| selectDetectors(constraint.getLater(), detectorSet).size() > 0) {
				passConstraintList.add(constraint);
			}
		}
		if (DEBUG) {
			System.out.println(passConstraintList.size() + " constraints are applicable for this pass");
		}

		// Build set of all detectors available to be added to this pass
		HashSet<DetectorFactory> availableSet = new HashSet<DetectorFactory>();
		availableSet.addAll(detectorSet);
		availableSet.addAll(getUnassignedSet());

		// Build intra-pass constraint graph
		Map<String, DetectorNode> nodeMap = new HashMap<String, DetectorNode>();
		ConstraintGraph constraintGraph = buildConstraintGraph(
			nodeMap, availableSet, passConstraintList);
		if (DEBUG) {
			System.out.println("Pass constraint graph:");
			dumpGraph(constraintGraph);
		}

		// See if any detectors were brought into the pass by an intrapass ordering constraint.
		// Assign them to the pass officially.
		for (DetectorNode node : nodeMap.values()) {
			if (!pass.contains(node.getFactory())) {
				assignToPass(node.getFactory(), pass);
			}
		}

		// Perform DFS, check for cycles
		DepthFirstSearch<ConstraintGraph, ConstraintEdge, DetectorNode> dfs =
			new DepthFirstSearch<ConstraintGraph, ConstraintEdge, DetectorNode>(constraintGraph);
		dfs.search();
		if (dfs.containsCycle())
			throw new OrderingConstraintException("Cycle in intra-pass ordering constraints!");

		// Do a topological sort to put the detectors in the pass
		// in the right order.
		for (Iterator<DetectorNode> i = dfs.topologicalSortIterator(); i.hasNext(); ) {
			DetectorNode node = i.next();
			appendToPass(node.getFactory(), pass);
		}

		// Add any detectors not explicitly involved in intra-pass ordering constraints
		// to the end of the pass.
		appendDetectorsToPass(pass.getUnpositionedMembers(), pass);
	}

	private Set<DetectorFactory> getUnassignedSet() {
		Set<DetectorFactory> unassignedSet = new HashSet<DetectorFactory>();
		unassignedSet.addAll(factoryMap.values());
		unassignedSet.removeAll(assignedToPassSet);
		return unassignedSet;
	}

	/**
	 * Make a DetectorFactory a member of an AnalysisPass.
	 */
	private void assignToPass(DetectorFactory factory, AnalysisPass pass) {
		pass.addToPass(factory);
		assignedToPassSet.add(factory);
	}

	/**
	 * Append a DetectorFactory to the end position in an AnalysisPass.
	 * The DetectorFactory must be a member of the pass.
	 */
	private void appendToPass(DetectorFactory factory, AnalysisPass pass)
			throws OrderingConstraintException {
		pass.append(factory);
	}

	private void appendDetectorsToPass(Collection<DetectorFactory> detectorSet, AnalysisPass pass)
			throws OrderingConstraintException {
		DetectorFactory[] unassignedList = detectorSet.toArray(new DetectorFactory[detectorSet.size()]);
		Arrays.sort(unassignedList, new Comparator<DetectorFactory>() {
			public int compare(DetectorFactory a, DetectorFactory b) {
				// Sort first by plugin id...
				int cmp = a.getPlugin().getPluginId().compareTo(b.getPlugin().getPluginId());
				if (cmp != 0)
					return cmp;
				// Then by order specified in plugin descriptor
				return a.getPositionSpecifiedInPluginDescriptor() - b.getPositionSpecifiedInPluginDescriptor();
			}
		});
		for (DetectorFactory factory : unassignedList) {
			appendToPass(factory, pass);
		}
	}

	private void print() {
		int passCount = 0;
		for (Iterator<AnalysisPass> i = passList.iterator(); i.hasNext(); ++passCount) {
			System.out.println("Pass " + passCount);
			AnalysisPass pass = i.next();
			for (Iterator<DetectorFactory> j = pass.iterator(); j.hasNext(); ) {
				DetectorFactory factory = j.next();
				System.out.println("  " + factory.getFullName());
			}
		}
	}

	private void dumpGraph(ConstraintGraph graph) {
		for (Iterator<ConstraintEdge> i = graph.edgeIterator(); i.hasNext();) {
			ConstraintEdge edge = i.next();
			System.out.println(
				edge.getSource().getFactory().getFullName() + " ==> " +
				edge.getTarget().getFactory().getFullName());
		}
	}

	public static void main(String[] argv) throws Exception {
		DetectorFactoryCollection detectorFactoryCollection =
			DetectorFactoryCollection.instance();

		ExecutionPlan execPlan = new ExecutionPlan();

		for (String pluginId : argv) {
			Plugin plugin = detectorFactoryCollection.getPluginById(pluginId);
			if (plugin != null)
				execPlan.addPlugin(plugin);
		}

		execPlan.build();

		System.out.println(execPlan.getNumPasses() + " passes in plan");
		execPlan.print();
	}
}

// vim:ts=4