<commit_before>/*
 * Bytecode Analysis Framework
 * Copyright (C) 2005,2008 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.ba.obl;

import java.util.Iterator;
import java.util.Map;

import org.apache.bcel.Constants;
import org.apache.bcel.generic.ConstantPoolGen;
import org.apache.bcel.generic.Instruction;
import org.apache.bcel.generic.InstructionHandle;
import org.apache.bcel.generic.InvokeInstruction;
import org.apache.bcel.generic.MethodGen;
import org.apache.bcel.generic.ObjectType;
import org.apache.bcel.generic.Type;

import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.annotations.CheckForNull;
import edu.umd.cs.findbugs.ba.AnalysisContext;
import edu.umd.cs.findbugs.ba.BasicBlock;
import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
import edu.umd.cs.findbugs.ba.DepthFirstSearch;
import edu.umd.cs.findbugs.ba.Edge;
import edu.umd.cs.findbugs.ba.EdgeTypes;
import edu.umd.cs.findbugs.ba.ForwardDataflowAnalysis;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.RepositoryLookupFailureCallback;
import edu.umd.cs.findbugs.ba.type.TypeDataflow;
import edu.umd.cs.findbugs.ba.type.TypeFrame;
import org.apache.bcel.generic.ReferenceType;

/**
 * Dataflow analysis to track obligations (i/o streams and other
 * resources which must be closed).
 *
 * <p>See Weimer and Necula,
 * <a href="http://doi.acm.org/10.1145/1028976.1029011"
 * >Finding and preventing run-time error handling mistakes</a>,
 * OOPSLA 2004.</p>
 *
 * @author <NAME>
 */
public class ObligationAnalysis
	extends ForwardDataflowAnalysis<StateSet> {

	private static final boolean DEBUG = SystemProperties.getBoolean("oa.debug");

	private TypeDataflow typeDataflow;
	private MethodGen methodGen;
	private ObligationFactory factory;
	private PolicyDatabase database;
	private RepositoryLookupFailureCallback lookupFailureCallback;

	/**
	 * Constructor.
	 * 
	 * @param dfs       a DepthFirstSearch on the method to be analyzed
	 * @param methodGen the MethodGen of the method being analyzed
	 * @param factory   the ObligationFactory defining the obligation types
	 * @param database  the PolicyDatabase defining the methods which
	 *                  add and delete obligations
	 * @param lookupFailureCallback callback to use when reporting
	 *                              missing classes
	 */
	public ObligationAnalysis(
			DepthFirstSearch dfs,
			TypeDataflow typeDataflow,
			MethodGen methodGen,
			ObligationFactory factory,
			PolicyDatabase database,
			RepositoryLookupFailureCallback lookupFailureCallback) {
		super(dfs);
		this.typeDataflow = typeDataflow;
		this.methodGen = methodGen;
		this.factory = factory;
		this.database = database;
		this.lookupFailureCallback = lookupFailureCallback;
	}

	public StateSet createFact() {
		return new StateSet(factory);
	}

	@Override
	public boolean isFactValid(StateSet fact) {
		return fact.isValid();
	}

	@Override
	public void transferInstruction(InstructionHandle handle, BasicBlock basicBlock, StateSet fact)
			throws DataflowAnalysisException {

		Obligation obligation;

		if ((obligation = addsObligation(handle)) != null) {
			// Add obligation to all states
			if (DEBUG) { System.out.println("Adding obligation " + obligation.toString()); }
			fact.addObligation(obligation);
		} else if ((obligation = deletesObligation(handle)) != null) {
			// Delete obligation from all states
			if (DEBUG) { System.out.println("Deleting obligation " + obligation.toString()); }
			deleteObligation(fact, obligation, handle);
		}

	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#transfer(edu.umd.cs.findbugs.ba.BasicBlock, org.apache.bcel.generic.InstructionHandle, java.lang.Object, java.lang.Object)
	 */
	@Override
	public void transfer(BasicBlock basicBlock, @CheckForNull  InstructionHandle end, StateSet start, StateSet result) throws DataflowAnalysisException {
		super.transfer(basicBlock, end, start, result);
		endTransfer(basicBlock, end, result);
	}

	private void endTransfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, StateSet result)
			throws DataflowAnalysisException {
		// Append this block id to the Paths of all States
		for (Iterator<State> i = result.stateIterator(); i.hasNext(); ) {
			State state = i.next();
			state.getPath().append(basicBlock.getLabel());
		}
	}

	private Obligation addsObligation(InstructionHandle handle) {
		return addsOrDeletesObligation(handle, PolicyDatabase.ADD);
	}

	private Obligation deletesObligation(InstructionHandle handle) {
		return addsOrDeletesObligation(handle, PolicyDatabase.DEL);
	}

	private Obligation addsOrDeletesObligation(InstructionHandle handle, int action) {
		Instruction ins = handle.getInstruction();

		if (!(ins instanceof InvokeInstruction))
			return null;

		InvokeInstruction inv = (InvokeInstruction) ins;

		ConstantPoolGen cpg = methodGen.getConstantPool();

		// FIXME: could prescreen class here...?
		
		ReferenceType type = inv.getReferenceType(cpg);
		if (!(type instanceof ObjectType)) {
			// We'll assume that methods called on an array object
			// don't add or remove any obligations.
			return null;
		}
		String className = ((ObjectType) type).getClassName();

		String methodName = inv.getName(cpg);
		String signature = inv.getSignature(cpg);
		boolean isStatic = inv.getOpcode() == Constants.INVOKESTATIC;

		if (DEBUG) {
			System.out.println("Checking instruction: " + handle);
			System.out.println("  class    =" + className);
			System.out.println("  method   =" + methodName);
			System.out.println("  signature=" + signature);
		}

		try {
			return database.lookup(
				className, methodName, signature, isStatic, action);
		} catch (ClassNotFoundException e) {
			lookupFailureCallback.reportMissingClass(e);
			return null;
		}

	}

	/**
	 * Delete Obligation from all states, throwing a DataflowAnalysisException
	 * if any of the states doesn't contain that Obligation.
	 * 
	 * @param fact       the StateSet to remove the Obligation from
	 * @param obligation the Obligation
	 * @param handle     the instruction which deletes the obligation
	 * @throw DataflowAnalysisException if any State doesn't contain the obligation
	 */
	private void deleteObligation(StateSet fact, Obligation obligation, InstructionHandle handle)
			throws DataflowAnalysisException {
		try {
			fact.deleteObligation(obligation);
		} catch (NonexistentObligationException e) {
			throw new DataflowAnalysisException(
					"Removing nonexistent obligation of type " + obligation.toString(),
					methodGen, handle, e);
		}
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#copy(edu.umd.cs.findbugs.ba.obl.StateSet, edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public void copy(StateSet src, StateSet dest) {
		dest.copyFrom(src);
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initEntryFact(edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public void initEntryFact(StateSet fact) throws DataflowAnalysisException {
		fact.initEntryFact(factory);
	}

//	/* (non-Javadoc)
//	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initResultFact(edu.umd.cs.findbugs.ba.obl.StateSet)
//	 */
//	public void initResultFact(StateSet fact) {
//		fact.setTop();
//	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#makeFactTop(edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public void makeFactTop(StateSet fact) {
		fact.setTop();
	}
	public boolean isTop(StateSet fact) {
		return fact.isTop();
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#same(edu.umd.cs.findbugs.ba.obl.StateSet, edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public boolean same(StateSet a, StateSet b) {
		return a.equals(b);
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#meetInto(edu.umd.cs.findbugs.ba.obl.StateSet, edu.umd.cs.findbugs.ba.Edge, edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public void meetInto(StateSet fact, Edge edge, StateSet result)
			throws DataflowAnalysisException {

		// If the edge is an exception thrown from a method that
		// tries to discharge an obligation, then that obligation needs to
		// be removed from all states in the input fact.
		if (edge.isExceptionEdge() && fact.isValid()) {
			BasicBlock sourceBlock = edge.getSource();
			InstructionHandle handle = sourceBlock.getExceptionThrower();
			Obligation obligation;
			if ((obligation = deletesObligation(handle)) != null) {
				fact = fact.duplicate();
				deleteObligation(fact, obligation, handle);
			}
		}

		// Similarly, if the incoming edge is from a reference comparision
		// which has established that a reference of an obligation type
		// is null, then we remove one occurrence of that type of
		// obligation from all states.
		if (isPossibleIfComparison(edge)) {
			Obligation obligation;
			if ((obligation = comparesObligationTypeToNull(edge)) != null) {
				fact = fact.duplicate();
				if (DEBUG) {
					System.out.println("Deleting " + obligation.toString() +
							" on edge from comparision " + edge.getSource().getLastInstruction());
				}
				deleteObligation(fact, obligation, edge.getSource().getLastInstruction());
			}
		}

		final StateSet inputFact = fact;

		// Handle easy top and bottom cases
		if (inputFact.isTop() || result.isBottom()) {
			// Nothing to do
		} else if (inputFact.isBottom() || result.isTop()) {
			copy(inputFact, result);
		} else {
			// Various things need to happen here
			// - Match up states with equal ObligationSets
			// - Paths with multiple occurences of a program point,
			//   but different obligation sets on different passes
			//   (i.e., obligation created inside a loop but not deleted)<commit_msg>changed to override edgeTransfer() for modeling of dataflow on control edges<commit_after>/*
 * Bytecode Analysis Framework
 * Copyright (C) 2005,2008 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.ba.obl;

import java.util.Iterator;
import java.util.Map;

import org.apache.bcel.Constants;
import org.apache.bcel.generic.ConstantPoolGen;
import org.apache.bcel.generic.Instruction;
import org.apache.bcel.generic.InstructionHandle;
import org.apache.bcel.generic.InvokeInstruction;
import org.apache.bcel.generic.MethodGen;
import org.apache.bcel.generic.ObjectType;
import org.apache.bcel.generic.Type;

import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.annotations.CheckForNull;
import edu.umd.cs.findbugs.ba.AnalysisContext;
import edu.umd.cs.findbugs.ba.BasicBlock;
import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
import edu.umd.cs.findbugs.ba.DepthFirstSearch;
import edu.umd.cs.findbugs.ba.Edge;
import edu.umd.cs.findbugs.ba.EdgeTypes;
import edu.umd.cs.findbugs.ba.ForwardDataflowAnalysis;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.RepositoryLookupFailureCallback;
import edu.umd.cs.findbugs.ba.type.TypeDataflow;
import edu.umd.cs.findbugs.ba.type.TypeFrame;
import org.apache.bcel.generic.ReferenceType;

/**
 * Dataflow analysis to track obligations (i/o streams and other
 * resources which must be closed).
 *
 * <p>See <NAME> Necula,
 * <a href="http://doi.acm.org/10.1145/1028976.1029011"
 * >Finding and preventing run-time error handling mistakes</a>,
 * OOPSLA 2004.</p>
 *
 * @author <NAME>
 */
public class ObligationAnalysis
	extends ForwardDataflowAnalysis<StateSet> {

	private static final boolean DEBUG = SystemProperties.getBoolean("oa.debug");

	private TypeDataflow typeDataflow;
	private MethodGen methodGen;
	private ObligationFactory factory;
	private PolicyDatabase database;
	private RepositoryLookupFailureCallback lookupFailureCallback;

	/**
	 * Constructor.
	 * 
	 * @param dfs       a DepthFirstSearch on the method to be analyzed
	 * @param methodGen the MethodGen of the method being analyzed
	 * @param factory   the ObligationFactory defining the obligation types
	 * @param database  the PolicyDatabase defining the methods which
	 *                  add and delete obligations
	 * @param lookupFailureCallback callback to use when reporting
	 *                              missing classes
	 */
	public ObligationAnalysis(
			DepthFirstSearch dfs,
			TypeDataflow typeDataflow,
			MethodGen methodGen,
			ObligationFactory factory,
			PolicyDatabase database,
			RepositoryLookupFailureCallback lookupFailureCallback) {
		super(dfs);
		this.typeDataflow = typeDataflow;
		this.methodGen = methodGen;
		this.factory = factory;
		this.database = database;
		this.lookupFailureCallback = lookupFailureCallback;
	}

	public StateSet createFact() {
		return new StateSet(factory);
	}

	@Override
	public boolean isFactValid(StateSet fact) {
		return fact.isValid();
	}

	@Override
	public void transferInstruction(InstructionHandle handle, BasicBlock basicBlock, StateSet fact)
			throws DataflowAnalysisException {

		Obligation obligation;

		if ((obligation = addsObligation(handle)) != null) {
			// Add obligation to all states
			if (DEBUG) { System.out.println("Adding obligation " + obligation.toString()); }
			fact.addObligation(obligation);
		} else if ((obligation = deletesObligation(handle)) != null) {
			// Delete obligation from all states
			if (DEBUG) { System.out.println("Deleting obligation " + obligation.toString()); }
			deleteObligation(fact, obligation, handle);
		}

	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#transfer(edu.umd.cs.findbugs.ba.BasicBlock, org.apache.bcel.generic.InstructionHandle, java.lang.Object, java.lang.Object)
	 */
	@Override
	public void transfer(BasicBlock basicBlock, @CheckForNull  InstructionHandle end, StateSet start, StateSet result) throws DataflowAnalysisException {
		super.transfer(basicBlock, end, start, result);
		endTransfer(basicBlock, end, result);
	}

	private void endTransfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, StateSet result)
			throws DataflowAnalysisException {
		// Append this block id to the Paths of all States
		for (Iterator<State> i = result.stateIterator(); i.hasNext(); ) {
			State state = i.next();
			state.getPath().append(basicBlock.getLabel());
		}
	}

	private Obligation addsObligation(InstructionHandle handle) {
		return addsOrDeletesObligation(handle, PolicyDatabase.ADD);
	}

	private Obligation deletesObligation(InstructionHandle handle) {
		return addsOrDeletesObligation(handle, PolicyDatabase.DEL);
	}

	private Obligation addsOrDeletesObligation(InstructionHandle handle, int action) {
		Instruction ins = handle.getInstruction();

		if (!(ins instanceof InvokeInstruction))
			return null;

		InvokeInstruction inv = (InvokeInstruction) ins;

		ConstantPoolGen cpg = methodGen.getConstantPool();

		// FIXME: could prescreen class here...?
		
		ReferenceType type = inv.getReferenceType(cpg);
		if (!(type instanceof ObjectType)) {
			// We'll assume that methods called on an array object
			// don't add or remove any obligations.
			return null;
		}
		String className = ((ObjectType) type).getClassName();

		String methodName = inv.getName(cpg);
		String signature = inv.getSignature(cpg);
		boolean isStatic = inv.getOpcode() == Constants.INVOKESTATIC;

		if (DEBUG) {
			System.out.println("Checking instruction: " + handle);
			System.out.println("  class    =" + className);
			System.out.println("  method   =" + methodName);
			System.out.println("  signature=" + signature);
		}

		try {
			return database.lookup(
				className, methodName, signature, isStatic, action);
		} catch (ClassNotFoundException e) {
			lookupFailureCallback.reportMissingClass(e);
			return null;
		}

	}

	/**
	 * Delete Obligation from all states, throwing a DataflowAnalysisException
	 * if any of the states doesn't contain that Obligation.
	 * 
	 * @param fact       the StateSet to remove the Obligation from
	 * @param obligation the Obligation
	 * @param handle     the instruction which deletes the obligation
	 * @throw DataflowAnalysisException if any State doesn't contain the obligation
	 */
	private void deleteObligation(StateSet fact, Obligation obligation, InstructionHandle handle)
			throws DataflowAnalysisException {
		try {
			fact.deleteObligation(obligation);
		} catch (NonexistentObligationException e) {
			throw new DataflowAnalysisException(
					"Removing nonexistent obligation of type " + obligation.toString(),
					methodGen, handle, e);
		}
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#copy(edu.umd.cs.findbugs.ba.obl.StateSet, edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public void copy(StateSet src, StateSet dest) {
		dest.copyFrom(src);
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initEntryFact(edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public void initEntryFact(StateSet fact) throws DataflowAnalysisException {
		fact.initEntryFact(factory);
	}

//	/* (non-Javadoc)
//	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initResultFact(edu.umd.cs.findbugs.ba.obl.StateSet)
//	 */
//	public void initResultFact(StateSet fact) {
//		fact.setTop();
//	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#makeFactTop(edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public void makeFactTop(StateSet fact) {
		fact.setTop();
	}
	public boolean isTop(StateSet fact) {
		return fact.isTop();
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#same(edu.umd.cs.findbugs.ba.obl.StateSet, edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public boolean same(StateSet a, StateSet b) {
		return a.equals(b);
	}

	@Override
	public void edgeTransfer(Edge edge, StateSet fact) throws DataflowAnalysisException {
		// If the edge is an exception thrown from a method that
		// tries to discharge an obligation, then that obligation needs to
		// be removed from all states in the input fact.
		if (edge.isExceptionEdge() && fact.isValid()) {
			BasicBlock sourceBlock = edge.getSource();
			InstructionHandle handle = sourceBlock.getExceptionThrower();
			Obligation obligation;
			if ((obligation = deletesObligation(handle)) != null) {
				deleteObligation(fact, obligation, handle);
			}
		}

		// Similarly, if the incoming edge is from a reference comparision
		// which has established that a reference of an obligation type
		// is null, then we remove one occurrence of that type of
		// obligation from all states.
		if (isPossibleIfComparison(edge)) {
			Obligation obligation;
			if ((obligation = comparesObligationTypeToNull(edge)) != null) {
				if (DEBUG) {
					System.out.println("Deleting " + obligation.toString() +
							" on edge from comparision " + edge.getSource().getLastInstruction());
				}
				deleteObligation(fact, obligation, edge.getSource().getLastInstruction());
			}
		}
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#meetInto(edu.umd.cs.findbugs.ba.obl.StateSet, edu.umd.cs.findbugs.ba.Edge, edu.umd.cs.findbugs.ba.obl.StateSet)
	 */
	public void meetInto(StateSet fact, Edge edge, StateSet result)
			throws DataflowAnalysisException {
		final StateSet inputFact = fact;

		// Handle easy top and bottom cases
		if (inputFact.isTop() || result.isBottom()) {
			// Nothing to do
		} else if (inputFact.isBottom() || result.isTop()) {
			copy(inputFact, result);
		} else {
			// Various things need to happen here
			// - Match up states with equal ObligationSets
			// - Paths with multiple occurences of a program point,
			//   but different obligation sets on different passes
			//   (i.e., obligation created inside a loop but not deleted)
{'fraction_non_alphanumeric': 0.10371361659417866, 'fraction_numerical': 0.004588252162691774, 'mean_word_length': 4.1397690985015965, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '533564', 'n_tokens_mistral': 6964, 'n_tokens_neox': 6271, 'n_words': 1693}