opcodestack.java

A static analysis tool to find bugs in Java programs

/*
 * FindBugs - Find bugs in Java programs
 * Copyright (C) 2004 Dave Brosius <[e-mail]>
 * Copyright (C) 2003-2006 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;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.bcel.Repository;
import org.apache.bcel.classfile.Code;
import org.apache.bcel.classfile.CodeException;
import org.apache.bcel.classfile.Constant;
import org.apache.bcel.classfile.ConstantClass;
import org.apache.bcel.classfile.ConstantDouble;
import org.apache.bcel.classfile.ConstantFloat;
import org.apache.bcel.classfile.ConstantInteger;
import org.apache.bcel.classfile.ConstantLong;
import org.apache.bcel.classfile.ConstantString;
import org.apache.bcel.classfile.ConstantUtf8;
import org.apache.bcel.classfile.JavaClass;
import org.apache.bcel.classfile.LocalVariable;
import org.apache.bcel.classfile.LocalVariableTable;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.BasicType;
import org.apache.bcel.generic.Type;

import edu.umd.cs.findbugs.annotations.CheckForNull;
import edu.umd.cs.findbugs.ba.AnalysisContext;
import edu.umd.cs.findbugs.ba.AnalysisFeatures;
import edu.umd.cs.findbugs.ba.ClassMember;
import edu.umd.cs.findbugs.ba.XFactory;
import edu.umd.cs.findbugs.ba.XField;
import edu.umd.cs.findbugs.ba.XMethod;
import edu.umd.cs.findbugs.visitclass.Constants2;
import edu.umd.cs.findbugs.visitclass.DismantleBytecode;
import edu.umd.cs.findbugs.visitclass.LVTHelper;
import edu.umd.cs.findbugs.visitclass.PreorderVisitor;

/**
 * tracks the types and numbers of objects that are currently on the operand stack
 * throughout the execution of method. To use, a detector should instantiate one for
 * each method, and call <p>stack.sawOpcode(this,seen);</p> at the bottom of their sawOpcode method.
 * at any point you can then inspect the stack and see what the types of objects are on
 * the stack, including constant values if they were pushed. The types described are of
 * course, only the static types. 
 * There are some outstanding opcodes that have yet to be implemented, I couldn't
 * find any code that actually generated these, so i didn't put them in because
 * I couldn't test them:
 * <ul>
 *   <li>dup2_x2</li>
 * 	 <li>jsr_w</li>
 *   <li>wide</li>
 * </ul>    
 */
public class OpcodeStack implements Constants2
{
	private static final boolean DEBUG 
		= SystemProperties.getBoolean("ocstack.debug");
	private List<Item> stack;
	private List<Item> lvValues;
	private List<Integer> lastUpdate;



	private boolean seenTransferOfControl = false;

	private boolean useIterativeAnalysis 
	= AnalysisContext.currentAnalysisContext().getBoolProperty(AnalysisFeatures.INTERATIVE_OPCODE_STACK_ANALYSIS);


	public static class Item
	{ 		
		public static final int SIGNED_BYTE = 1;
		public static final int RANDOM_INT = 2;
		public static final int LOW_8_BITS_CLEAR = 3;
		public static final int HASHCODE_INT = 4;
		public static final int INTEGER_SUM = 5;
		public static final int AVERAGE_COMPUTED_USING_DIVISION = 6;
		public static final int FLOAT_MATH = 7;
		public static final int RANDOM_INT_REMAINDER = 8;
		public static final int HASHCODE_INT_REMAINDER = 9;
		public static final int FILE_SEPARATOR_STRING = 10;
		public static final int MATH_ABS = 11;
		public static final int MASKED_NON_NEGATIVE = 12;
		public static final int NASTY_FLOAT_MATH = 13;

		private static final int IS_INITIAL_PARAMETER_FLAG=1;
		private static final int COULD_BE_ZERO_FLAG = 2;
		private static final int IS_NULL_FLAG = 4;

		public static final Object UNKNOWN = null;
		private int specialKind;
		private String signature;
		private Object constValue = UNKNOWN;
		private @CheckForNull ClassMember source;
		private int flags;
		 // private boolean isNull = false;
		private int registerNumber = -1;
		// private boolean isInitialParameter = false;
		// private boolean couldBeZero = false;
		private Object userValue = null;
		private int fieldLoadedFromRegister = -1;


		public int getSize() {
			if (signature.equals("J") || signature.equals("D")) return 2;
			return 1;
		}

		private static boolean equals(Object o1, Object o2) {
			if (o1 == o2) return true;
			if (o1 == null || o2 == null) return false;
			return o1.equals(o2);
			}

		@Override
		public int hashCode() {
			int r = 42 + specialKind;
			if (signature != null)
				r+= signature.hashCode();
			r *= 31;
			if (constValue != null)
				r+= constValue.hashCode();
			r *= 31;
			if (source != null)
				r+= source.hashCode();
			r *= 31;
			r += flags;
			r *= 31;
			r += registerNumber;
			return r;

			}
		@Override
		public boolean equals(Object o) {
			if (!(o instanceof Item)) return false;
			Item that = (Item) o;

			return equals(this.signature, that.signature)
				&& equals(this.constValue, that.constValue)
				&& equals(this.source, that.source)
				&& this.specialKind == that.specialKind
				&& this.registerNumber == that.registerNumber
				&& this.flags == that.flags
				&& this.userValue == that.userValue
				&& this.fieldLoadedFromRegister == that.fieldLoadedFromRegister;

			}

		@Override
		public String toString() {
			StringBuffer buf = new StringBuffer("< ");
			buf.append(signature);
			switch(specialKind) {
			case SIGNED_BYTE:
				buf.append(", byte_array_load");
				break;
			case  RANDOM_INT:
				buf.append(", random_int");
				break;
			case LOW_8_BITS_CLEAR:
				buf.append(", low8clear");
				break;
			case HASHCODE_INT:
				buf.append(", hashcode_int");
				break;
			case INTEGER_SUM:
				buf.append(", int_sum");
				break;
			case AVERAGE_COMPUTED_USING_DIVISION:
				buf.append(", averageComputingUsingDivision");
				break;
			case FLOAT_MATH:
				buf.append(", floatMath");
				break;
			case NASTY_FLOAT_MATH:
				buf.append(", nastyFloatMath");
				break;
			case HASHCODE_INT_REMAINDER:
				buf.append(", hashcode_int_rem");
				break;
			case  RANDOM_INT_REMAINDER:
				buf.append(", random_int_rem");
				break;
			case  FILE_SEPARATOR_STRING:
				buf.append(", file_separator_string");
				break;
			case  MATH_ABS:
				buf.append(", Math.abs");
				break;
			case  MASKED_NON_NEGATIVE:
				buf.append(", masked_non_negative");
				break;
			case 0 :
				break;
			default:
					buf.append(", #" + specialKind);
				break;

			}
			if (constValue != UNKNOWN) {
				buf.append(", ");
				buf.append(constValue);
				}
			if (source instanceof XField) {
				buf.append(", ");
				if (fieldLoadedFromRegister != -1)
					buf.append(fieldLoadedFromRegister).append(':');
				buf.append(source);
				}
			if (source instanceof XMethod) {
				buf.append(", return value from ");
				buf.append(source);
				}
			if (isInitialParameter()) {
				buf.append(", IP");
				}
			if (isNull()) {
				buf.append(", isNull");
				}

			if (registerNumber != -1) {
				buf.append(", r");
				buf.append(registerNumber);
				}
			if (isCouldBeZero()) buf.append(", cbz");
			buf.append(" >");
			return buf.toString();
			}


		 public static Item merge(Item i1, Item i2) {
			if (i1 == null) return i2;
			if (i2 == null) return i1;
			if (i1.equals(i2)) return i1;
			Item m = new Item();
			m.flags = i1.flags & i2.flags;
			m.setCouldBeZero(i1.isCouldBeZero() || i2.isCouldBeZero());
			if (equals(i1.signature,i2.signature))
				m.signature = i1.signature;
			if (equals(i1.constValue,i2.constValue))
				m.constValue = i1.constValue;
			if (equals(i1.source,i2.source)) {
				m.source = i1.source;
			}

			if (i1.registerNumber == i2.registerNumber)
				m.registerNumber = i1.registerNumber;
			if (i1.fieldLoadedFromRegister == i2.fieldLoadedFromRegister)
				m.fieldLoadedFromRegister = i1.fieldLoadedFromRegister;

			if (i1.specialKind == i2.specialKind)
				m.specialKind = i1.specialKind;
			else if (i1.specialKind == NASTY_FLOAT_MATH || i2.specialKind == NASTY_FLOAT_MATH)
				m.specialKind = NASTY_FLOAT_MATH;
			else if (i1.specialKind == FLOAT_MATH || i2.specialKind == FLOAT_MATH)
				m.specialKind = FLOAT_MATH;
			if (DEBUG) System.out.println("Merge " + i1 + " and " + i2 + " gives " + m);
			return m;
		}
		public Item(String signature, int constValue) {
			this(signature, (Object)(Integer)constValue);
		 }

		 public Item(String signature) {
			 this(signature, UNKNOWN);
		 }
		  public Item(Item it) {
			this.signature = it.signature;
			this.constValue = it.constValue;
			this.source = it.source;
			this.registerNumber = it.registerNumber;
			this.userValue = it.userValue;
			this.flags = it.flags;
			this.specialKind = it.specialKind;
		 }
		 public Item(Item it, int reg) {
			 this(it);
			 this.registerNumber = reg;
		 }
		 public Item(String signature, FieldAnnotation f) {
			this.signature = signature;
			if (f != null)
				source = XFactory.createXField(f);
			fieldLoadedFromRegister = -1;
		 }
		public Item(String signature, FieldAnnotation f, int fieldLoadedFromRegister) {
			this.signature = signature;
			if (f != null)
				source = XFactory.createXField(f);
			this.fieldLoadedFromRegister = fieldLoadedFromRegister;
		 }

		public int getFieldLoadedFromRegister() {
			return fieldLoadedFromRegister;
		}

		 public Item(String signature, Object constantValue) {
			 this.signature = signature;
			 constValue = constantValue;
			 if (constantValue instanceof Integer) {
				 int value = (Integer) constantValue;
				 if (value != 0 && (value & 0xff) == 0)
					 specialKind = LOW_8_BITS_CLEAR;
				 if (value == 0) setCouldBeZero(true);

			 }
			 else if (constantValue instanceof Long) {
				 long value = (Long) constantValue;
				 if (value != 0 && (value & 0xff) == 0)
					 specialKind = LOW_8_BITS_CLEAR;
				 if (value == 0) setCouldBeZero(true);
			 }

		 }

		 public Item() {
			 signature = "Ljava/lang/Object;";
			 constValue = null;
			 setNull(true);
		 }

		 public JavaClass getJavaClass() throws ClassNotFoundException {
			 String baseSig;

			 if (isPrimitive())
				 return null;

			 if (isArray()) {
				 baseSig = getElementSignature();
			 } else {
				 baseSig = signature;
			 }

			 if (baseSig.length() == 0)
				 return null;
			 baseSig = baseSig.substring(1, baseSig.length() - 1);
			 baseSig = baseSig.replace('/', '.');
			 return Repository.lookupClass(baseSig);
		 }

		 public boolean isArray() {
			 return signature.startsWith("[");
		 }

		 public String getElementSignature() {
			 if (!isArray())
				 return signature;
			 else {
				 int pos = 0;
				 int len = signature.length();
				 while (pos < len) {
					 if (signature.charAt(pos) != '[')
						 break;
					 pos++;
				 }
				 return signature.substring(pos);
			 }
		 }

		public boolean isNonNegative() {
			if (specialKind == MASKED_NON_NEGATIVE) return true;
			if (constValue instanceof Number) {
				double value = ((Number) constValue).doubleValue();
				return value >= 0;
			}
			return false;
		}
		 public boolean isPrimitive() {
			 return !signature.startsWith("L");
		 }

		 public int getRegisterNumber() {
			 return registerNumber;
		 }
		 public String getSignature() {
			 return signature;
		 }

		 public Object getConstant() {
			 return constValue;
		 }

		 /** Use getXField instead */
		 @Deprecated
		 public FieldAnnotation getFieldAnnotation() {
			 return FieldAnnotation.fromXField(getXField());
		 }
		 public XField getXField() {
			 if (source instanceof XField) return (XField) source;
			 return null;
		 }
		/**
		 * @param specialKind The specialKind to set.
		 */
		public void setSpecialKind(int specialKind) {
			this.specialKind = specialKind;
		}

		/**
		 * @return Returns the specialKind.
		 */
		public int getSpecialKind() {
			return specialKind;
		}

		/**
		 * attaches a detector specified value to this item
		 * 
		 * @param value the custom value to set
		 */
		public void setUserValue(Object value) {
			userValue = value;
		}

		/**
		 * 
		 * @return if this value is the return value of a method, give the method
		 * invoked
		 */
		public @CheckForNull XMethod getReturnValueOf() {
			if (source instanceof XMethod) return (XMethod) source;
			return null;
		}
		public boolean couldBeZero() {
			return isCouldBeZero();
		}
		public boolean mustBeZero() {
			Object value = getConstant();
			return value instanceof Number && ((Number)value).intValue() == 0;
		}
		/**
		 * gets the detector specified value for this item
		 * 
		 * @return the custom value
		 */
		public Object getUserValue() {
			return userValue;
		}

		public boolean valueCouldBeNegative() {
			return (getSpecialKind() == Item.RANDOM_INT 
					|| getSpecialKind() == Item.SIGNED_BYTE 
					|| getSpecialKind() == Item.HASHCODE_INT 
					|| getSpecialKind() == Item.RANDOM_INT_REMAINDER || getSpecialKind() == Item.HASHCODE_INT_REMAINDER);

		}

		/**
		 * @param isInitialParameter The isInitialParameter to set.
		 */
		private void setInitialParameter(boolean isInitialParameter) {
			setFlag(isInitialParameter, IS_INITIAL_PARAMETER_FLAG);
		}

		/**
		 * @return Returns the isInitialParameter.
		 */
		public boolean isInitialParameter() {
			return (flags & IS_INITIAL_PARAMETER_FLAG) != 0;
		}

		/**
		 * @param couldBeZero The couldBeZero to set.
		 */
		private void setCouldBeZero(boolean couldBeZero) {
			setFlag(couldBeZero, COULD_BE_ZERO_FLAG);
		}

		/**
		 * @return Returns the couldBeZero.
		 */
		private boolean isCouldBeZero() {
			return (flags & COULD_BE_ZERO_FLAG) != 0;
		}

		/**
		 * @param isNull The isNull to set.
		 */
		private void setNull(boolean isNull) {
			setFlag(isNull, IS_NULL_FLAG);
		}

		private void setFlag(boolean value, int flagBit) {
			if (value)
				flags |= flagBit;