opcodestack.java

A static analysis tool to find bugs in Java programs

				 Object sVal = i.getConstant();
				 if ((sbVal != null) && (sVal != null)) {
					 appenderValue = sbVal + sVal.toString();
				 } else if (sbItem.registerNumber >= 0) {
					OpcodeStack.Item item = getLVValue(sbItem.registerNumber);
					if (item != null)
						item.constValue = null;
				}
			 }
		 }

		 pushByInvoke(dbc, seen != INVOKESTATIC);

		 if (appenderValue != null) {
			 Item i = this.getStackItem(0);
			 i.constValue = appenderValue;
			 if (sbItem != null) {
				  i.registerNumber = sbItem.registerNumber;
				  i.source = sbItem.source;
				  i.userValue = sbItem.userValue;
				  if (sbItem.registerNumber >= 0)
					  setLVValue(sbItem.registerNumber, i );
			 }
			 return;
		 }

		if ((clsName.equals("java/util/Random") || clsName.equals("java/security/SecureRandom")) && methodName.equals("nextInt") && signature.equals("()I")) {
			Item i = pop();
			i.setSpecialKind(Item.RANDOM_INT);
			i.source = XFactory.createReferencedXMethod(dbc);
			push(i);
		}
		if (clsName.equals("java/lang/Math") && methodName.equals("abs")) {
			Item i = pop();
			i.setSpecialKind(Item.MATH_ABS);
			i.source = XFactory.createReferencedXMethod(dbc);
			push(i);
		}
		else if (seen == INVOKEVIRTUAL && methodName.equals("hashCode") && signature.equals("()I")
				|| seen == INVOKESTATIC && clsName.equals("java/lang/System") && methodName.equals("identityHashCode") && signature.equals("(Ljava/lang/Object;)I")) {
			Item i = pop();
			i.setSpecialKind(Item.HASHCODE_INT);
			i.source = XFactory.createReferencedXMethod(dbc);
			push(i);
		} else if (!signature.endsWith(")V")) {
			Item i = pop();
			i.source = XFactory.createReferencedXMethod(dbc);
			push(i);
		}

	 }

	private void mergeLists(List<Item> mergeInto, List<Item> mergeFrom, boolean errorIfSizesDoNotMatch) {
		// merge stacks
		int intoSize = mergeInto.size();
		int fromSize = mergeFrom.size();
		if (errorIfSizesDoNotMatch && intoSize != fromSize) {
			if (DEBUG) {
				System.out.println("Bad merging items");
				System.out.println("current items: " + mergeInto);
				System.out.println("jump items: " + mergeFrom);
			}
		} else {
			if (DEBUG) {
				System.out.println("Merging items");
				System.out.println("current items: " + mergeInto);
				System.out.println("jump items: " + mergeFrom);
			}

			for (int i = 0; i < Math.min(intoSize, fromSize); i++)
				mergeInto.set(i, Item.merge(mergeInto.get(i), mergeFrom.get(i)));
			if (DEBUG) {
				System.out.println("merged items: " + mergeInto);
			}
		}
	}

	 public void clear() {
		 stack.clear();
		 lvValues.clear();
	 }
	 BitSet exceptionHandlers = new BitSet();
	 private Map<Integer, List<Item>> jumpEntries = new HashMap<Integer, List<Item>>();
	 private Map<Integer, List<Item>> jumpStackEntries = new HashMap<Integer, List<Item>>();
	private BitSet jumpEntryLocations = new BitSet();

	 private void addJumpValue(int target) {
		 if (DEBUG)
			 System.out.println("Set jump entry at " + methodName + ":" + target + "pc to " + stack + " : " +  lvValues );

		 List<Item> atTarget = jumpEntries.get(target);
		 if (atTarget == null) {
			 if (DEBUG)
				  System.out.println("Was null");

			 jumpEntries.put(target, new ArrayList<Item>(lvValues));
			jumpEntryLocations.set(target);

			 if (stack.size() > 0) {
			   jumpStackEntries.put(target, new ArrayList<Item>(stack));
			}
			 return;
		 }
		 mergeLists(atTarget, lvValues, false);
		 List<Item> stackAtTarget = jumpStackEntries.get(target);
		 if (stack.size() > 0 && stackAtTarget != null) 
			 mergeLists(stackAtTarget, stack, false);
		if (DEBUG)
				  System.out.println("merge target for " + methodName + ":" + target + "pc is " + atTarget);
	 }
	 private String methodName;
	 public int resetForMethodEntry(final DismantleBytecode v) {
		 methodName = v.getMethodName();
		jumpEntries.clear();
		jumpStackEntries.clear();
		jumpEntryLocations.clear();
		lastUpdate.clear();
		convertJumpToOneZeroState = convertJumpToZeroOneState = 0;
		reachOnlyByBranch = false;
		 int result= resetForMethodEntry0(v);
		 Code code = v.getMethod().getCode();
		if (code == null) return result;

		if (useIterativeAnalysis) {
			// FIXME: Be clever
			if (DEBUG) 
				System.out.println(" --- Iterative analysis");
			DismantleBytecode branchAnalysis = new DismantleBytecode() {
				@Override
				public void sawOpcode(int seen) {
					OpcodeStack.this.sawOpcode(this, seen);
				}

				// perhaps we don't need this
//				@Override
//				public void sawBranchTo(int pc) {
//					addJumpValue(pc);
//				}
			};
			branchAnalysis.setupVisitorForClass(v.getThisClass());
			branchAnalysis.doVisitMethod(v.getMethod());
			if (!jumpEntries.isEmpty()) 
				branchAnalysis.doVisitMethod(v.getMethod());
			if (DEBUG && !jumpEntries.isEmpty()) {
				System.out.println("Found dataflow for jumps in " + v.getMethodName());
				for (Integer pc : jumpEntries.keySet()) {
					List<Item> list = jumpEntries.get(pc);
					System.out.println(pc + " -> " + Integer.toString(System.identityHashCode(list),16) + " " + list);
				}
			}
			resetForMethodEntry0(v);
			if (DEBUG) 
				System.out.println(" --- End of Iterative analysis");

		}

		 return result;

		}


	private int resetForMethodEntry0(PreorderVisitor v) {
		if (DEBUG) System.out.println(" --- ");
		 stack.clear();
		 lvValues.clear();
		reachOnlyByBranch = false;
		seenTransferOfControl = false;
		String className = v.getClassName();

		String signature = v.getMethodSig();
		exceptionHandlers.clear();
		 Method m = v.getMethod();
		 Code code = m.getCode();
		if (code != null) 
	 {
			CodeException[] exceptionTable = code.getExceptionTable();
			if (exceptionTable != null)
				for(CodeException ex : exceptionTable) 
					exceptionHandlers.set(ex.getHandlerPC());
		}
		if (DEBUG) System.out.println(" --- " + className 
				+ " " + m.getName() + " " + signature);
		Type[] argTypes = Type.getArgumentTypes(signature);
		int reg = 0;
		if (!m.isStatic()) {
			Item it = new Item("L" + className+";");
			it.setInitialParameter(true);
			it.registerNumber = reg;
			setLVValue( reg, it);
			reg += it.getSize();
			}
		 for (Type argType : argTypes) {
			 Item it = new Item(argType.getSignature());
			 it.registerNumber = reg;
			 it.setInitialParameter(true);
			 setLVValue(reg, it);
			 reg += it.getSize();
		 }
		return reg;
	}

	 public int getStackDepth() {
		 return stack.size();
	 }

	 public Item getStackItem(int stackOffset) {
		if (stackOffset < 0 || stackOffset >= stack.size()) {
			// assert false : "Can't get stack offset " + stackOffset + " from " + stack.toString();
			return new Item("Lfindbugs/OpcodeStackError;");

		}
		 int tos = stack.size() - 1;
		 int pos = tos - stackOffset;
		 try {
		 return stack.get(pos);
		 } catch (ArrayIndexOutOfBoundsException e) {
			 throw new ArrayIndexOutOfBoundsException(
				 "Requested item at offset " + stackOffset + " in a stack of size " + stack.size()
				 +", made request for position " + pos);
		 }
	 } 

	  private Item pop() {
		 return stack.remove(stack.size()-1);
	 }

	 private void pop(int count)
	 {
		 while ((count--) > 0)
			 pop();
	 }

	 private void push(Item i) {
		 stack.add(i);
	 }

	 private void pushByConstant(DismantleBytecode dbc, Constant c) {

		if (c instanceof ConstantClass)
			push(new Item("Ljava/lang/Class;", ((ConstantClass)c).getConstantValue(dbc.getConstantPool())));
		else if (c instanceof ConstantInteger)
			push(new Item("I", (Integer)(((ConstantInteger) c).getBytes())));
		else if (c instanceof ConstantString) {
			int s = ((ConstantString) c).getStringIndex();
			push(new Item("Ljava/lang/String;", getStringFromIndex(dbc, s)));
		}
		else if (c instanceof ConstantFloat)
			push(new Item("F", (Float)(((ConstantFloat) c).getBytes())));
		else if (c instanceof ConstantDouble)
			push(new Item("D", (Double)(((ConstantDouble) c).getBytes())));
		else if (c instanceof ConstantLong)
			push(new Item("J", (Long)(((ConstantLong) c).getBytes())));
		else
			throw new UnsupportedOperationException("Constant type not expected" );
	 }

	 private void pushByLocalObjectLoad(DismantleBytecode dbc, int register) {
		Method m = dbc.getMethod();
		LocalVariableTable lvt = m.getLocalVariableTable();
		if (lvt != null) {
			LocalVariable lv = LVTHelper.getLocalVariableAtPC(lvt, register, dbc.getPC());
			if (lv != null) {
				String signature = lv.getSignature();
				pushByLocalLoad(signature, register);
				return;
			}
		}
		pushByLocalLoad("", register);
	 }

	 private void pushByIntMath(int seen, Item lhs, Item rhs) {
		 if (DEBUG) System.out.println("pushByIntMath: " + rhs.getConstant()  + " " + lhs.getConstant() );
		 Item newValue  = new Item("I");
		 try {

		if ((rhs.getConstant() != null) && lhs.getConstant() != null) {
			Integer lhsValue = (Integer) lhs.getConstant();
			Integer rhsValue = (Integer) rhs.getConstant();
			if (seen == IADD)
				newValue = new Item("I",lhsValue + rhsValue);
			else if (seen == ISUB)
				newValue = new Item("I",lhsValue - rhsValue);
			else if (seen == IMUL)
				newValue = new Item("I", lhsValue * rhsValue);
			else if (seen == IDIV)
				newValue = new Item("I", lhsValue / rhsValue);
			else if (seen == IAND) {
				newValue = new Item("I", lhsValue & rhsValue);
				if ((rhsValue&0xff) == 0 && rhsValue != 0 || (lhsValue&0xff) == 0 && lhsValue != 0 ) 	
					newValue.specialKind = Item.LOW_8_BITS_CLEAR;

			} else if (seen == IOR)
				newValue = new Item("I",lhsValue | rhsValue);
			else if (seen == IXOR)
				newValue = new Item("I",lhsValue ^ rhsValue);
			else if (seen == ISHL) {
				newValue = new Item("I",lhsValue << rhsValue);
				if (rhsValue >= 8) 	newValue.specialKind = Item.LOW_8_BITS_CLEAR;
			}
			else if (seen == ISHR)
				newValue = new Item("I",lhsValue >> rhsValue);
			else if (seen == IREM)
				newValue = new Item("I", lhsValue % rhsValue);
			else if (seen == IUSHR)
				newValue = new Item("I", lhsValue >>> rhsValue);
			} else if (rhs.getConstant() != null && seen == ISHL && (Integer) rhs.getConstant() >= 8)
				newValue.specialKind = Item.LOW_8_BITS_CLEAR;
			else if (lhs.getConstant() != null && seen == IAND) {
				int value = (Integer) lhs.getConstant();
				if (value == 0)
					newValue = new Item("I", 0);
				else if ((value & 0xff) == 0)
					newValue.specialKind = Item.LOW_8_BITS_CLEAR;
				else if (value >= 0)
					newValue.specialKind = Item.MASKED_NON_NEGATIVE;
			} else if (rhs.getConstant() != null && seen == IAND) {
				int value = (Integer) rhs.getConstant();
				if (value == 0)
					newValue = new Item("I", 0);
				else if ((value & 0xff) == 0)
					newValue.specialKind = Item.LOW_8_BITS_CLEAR;
				else if (value >= 0)
					newValue.specialKind = Item.MASKED_NON_NEGATIVE;
			}
		} catch (RuntimeException e) {
			 // ignore it
		 }
		if (lhs.specialKind == Item.INTEGER_SUM && rhs.getConstant() != null ) {
			int rhsValue = (Integer) rhs.getConstant();
			if (seen == IDIV && rhsValue ==2  || seen == ISHR  && rhsValue == 1)
				newValue.specialKind = Item.AVERAGE_COMPUTED_USING_DIVISION;
		}
		if (seen == IADD && newValue.specialKind == 0 &&   lhs.getConstant() == null && rhs.getConstant() == null ) 
			newValue.specialKind = Item.INTEGER_SUM;
		if (seen == IREM && lhs.specialKind == Item.HASHCODE_INT)
			newValue.specialKind = Item.HASHCODE_INT_REMAINDER;
		if (seen == IREM && lhs.specialKind == Item.RANDOM_INT)
			newValue.specialKind = Item.RANDOM_INT_REMAINDER;
		 if (DEBUG) System.out.println("push: " + newValue);
		 push(newValue);
	}

	private void pushByLongMath(int seen, Item lhs, Item rhs) {
		Item newValue  = new Item("J");
		try {

		if ((rhs.getConstant() != null) && lhs.getConstant() != null) {

			Long lhsValue = ((Long) lhs.getConstant());
			 if (seen == LSHL) {
				newValue  =new Item("J", lhsValue << ((Number) rhs.getConstant()).intValue());
				if (((Number) rhs.getConstant()).intValue()  >= 8) 	newValue.specialKind = Item.LOW_8_BITS_CLEAR;
			 }
			else if (seen == LSHR)
				newValue  =new Item("J", lhsValue >> ((Number) rhs.getConstant()).intValue());
			else if (seen == LUSHR)
				newValue  =new Item("J", lhsValue >>> ((Number) rhs.getConstant()).intValue());

			else  {
				Long rhsValue = ((Long) rhs.getConstant());
			if (seen == LADD)
				newValue  = new Item("J", lhsValue + rhsValue);
			else if (seen == LSUB)
				newValue  = new Item("J", lhsValue - rhsValue);
			else if (seen == LMUL)
				newValue  = new Item("J", lhsValue * rhsValue);
			else if (seen == LDIV)
				newValue  =new Item("J", lhsValue / rhsValue);
			else if (seen == LAND) {
				newValue  = new Item("J", lhsValue & rhsValue);
			if ((rhsValue&0xff) == 0 && rhsValue != 0 || (lhsValue&0xff) == 0 && lhsValue != 0 ) 	
				newValue.specialKind = Item.LOW_8_BITS_CLEAR;
			}
			else if (seen == LOR)
				newValue  = new Item("J", lhsValue | rhsValue);
			else if (seen == LXOR)
				newValue  =new Item("J", lhsValue ^ rhsValue);
			else if (seen == LREM)
				newValue  =new Item("J", lhsValue % rhsValue);
			}
			}
		 else if (rhs.getConstant() != null && seen == LSHL  && ((Integer) rhs.getConstant()) >= 8)
			newValue.specialKind = Item.LOW_8_BITS_CLEAR;
		 else if (lhs.getConstant() != null && seen == LAND  && (((Long) lhs.getConstant()) & 0xff) == 0)
			newValue.specialKind = Item.LOW_8_BITS_CLEAR;
		 else if (rhs.getConstant() != null && seen == LAND  && (((Long) rhs.getConstant()) & 0xff) == 0)
			newValue.specialKind = Item.LOW_8_BITS_CLEAR;
		} catch (RuntimeException e) {
			// ignore it
		}
		push(newValue);
	}

	private void pushByFloatMath(int seen, Item it, Item it2) {
		Item result;
		int specialKind = Item.FLOAT_MATH;
		if ((it.getConstant() != null) && it2.getConstant() != null) {
			if (seen == FADD)
				result =new Item("F", ((Float) it2.getConstant()) + ((Float) it.getConstant()));
			else if (seen == FSUB)
				result =new Item("F", ((Float) it2.getConstant()) - ((Float) it.getConstant()));
			else if (seen == FMUL)
				result =new Item("F", ((Float) it2.getConstant()) * ((Float) it.getConstant()));
			else if (seen == FDIV)
				result =new Item("F", ((Float) it2.getConstant()) / ((Float) it.getConstant()));
				else result =new Item("F");
		} else {
			result =new Item("F");
			if (seen == DDIV)
				specialKind = Item.NASTY_FLOAT_MATH;
		}
		result.setSpecialKind(specialKind);
		push(result);
	}

	private void pushByDoubleMath(int seen, Item it, Item it2) {
		Item result;
		int specialKind = Item.FLOAT_MATH;
		if ((it.getConstant() != null) && it2.getConstant() != null) {
			if (seen == DADD)
				result = new Item("D", ((Double) it2.getConstant()) + ((Double) it.getConstant()));
			else if (seen == DSUB)
				result = new Item("D", ((Double) it2.getConstant()) - ((Double) it.getConstant()));
			else if (seen == DMUL)
				result = new Item("D", ((Double) it2.getConstant()) * ((Double) it.getConstant()));
			else if (seen == DDIV)
				result = new Item("D", ((Double) it2.getConstant()) / ((Double) it.getConstant()));
			else 
				result = new Item("D");	//?	
			} else {
			result = new Item("D");
			if (seen == DDIV)
				specialKind = Item.NASTY_FLOAT_MATH;
		}
		result.setSpecialKind(specialKind);
		push(result);
	}

	private void pushByInvoke(DismantleBytecode dbc, boolean popThis) {
		String signature = dbc.getSigConstantOperand();
		pop(PreorderVisitor.getNumberArguments(signature)+(popThis ? 1 : 0));
		pushBySignature(Type.getReturnType(signature).getSignature());
	}

	private String getStringFromIndex(DismantleBytecode dbc, int i) {
		ConstantUtf8 name = (ConstantUtf8) dbc.getConstantPool().getConstant(i);
		return name.getBytes();
	}

	private void pushBySignature(String s) {
		 if ("V".equals(s))
			 return;
		  push(new Item(s, (Object) null));
	 }

	 private void pushByLocalStore(int register) {
		Item it = pop();
		if (it.getRegisterNumber() != register) {
		for(Item i : lvValues) if (i != null) {
			if (i.registerNumber == register) i.registerNumber = -1;
			if (i.fieldLoadedFromRegister == register) i.fieldLoadedFromRegister  = -1;
		}
		for(Item i : stack) if (i != null) {
			if (i.registerNumber == register) i.registerNumber = -1;
			if (i.fieldLoadedFromRegister == register) i.fieldLoadedFromRegister  = -1;
		}
		}
		setLVValue( register, it );
	 }

	 private void pushByLocalLoad(String signature, int register) {
		Item it = getLVValue(register);

		if (it == null) {
			Item item = new Item(signature);
			item.registerNumber = register;
			push(item);
		}
		else if (it.getRegisterNumber() >= 0)
			push(it);
		else  {
			push(new Item(it, register));
			}
	 }

	 private void setLVValue(int index, Item value ) {
		 int addCount = index - lvValues.size() + 1;
		 while ((addCount--) > 0)
			 lvValues.add(null);
		if (!useIterativeAnalysis && seenTransferOfControl) 
			value = Item.merge(value, lvValues.get(index) );
		 lvValues.set(index, value);
	 }

	 private Item getLVValue(int index) {
		 if (index >= lvValues.size())
			 return null;

		 return lvValues.get(index);
	 }
}

// vim:ts=4