0001: /* Soot - a J*va Optimization Framework
0002: * Copyright (C) 2005 Nomair A. Naeem
0003: *
0004: * This library is free software; you can redistribute it and/or
0005: * modify it under the terms of the GNU Lesser General Public
0006: * License as published by the Free Software Foundation; either
0007: * version 2.1 of the License, or (at your option) any later version.
0008: *
0009: * This library is distributed in the hope that it will be useful,
0010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0012: * Lesser General Public License for more details.
0013: *
0014: * You should have received a copy of the GNU Lesser General Public
0015: * License along with this library; if not, write to the
0016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
0017: * Boston, MA 02111-1307, USA.
0018: */
0019:
0020: /**
0021: * Maintained by: Nomair A. Naeem
0022: */
0023:
0024: /**
0025: * CHANGE LOG:
0026: * November 21st, 2005: Reasoning about correctness of implementation.
0027: * November 22nd, 2005: Found bug in process_DoWhile while implementing ReachingCopies..
0028: * see method for details
0029: * January 30th, 2006: Found bug in handling of breaks inside the ASTTryNode while implementing
0030: * MustMayinitialize...see ASTTryNode method for details
0031: * January 30th, 2006: Found bug in handling of switchNode while implementing MustMayInitialize
0032: * NEEDS THOROUGH TESTING!!!
0033: *
0034: */
0035:
0036: /**
0037: * TODO:
0038: * Refactor the class into a top level class and a forward analysis subclass
0039: * Write the backwards flow analysis
0040: *
0041: * THOROUGH TESTING OF BUG FOUND ON 30th January
0042: */package soot.dava.toolkits.base.AST.structuredAnalysis;
0043:
0044: import soot.*;
0045: import java.util.*;
0046:
0047: import soot.jimple.*;
0048: import soot.dava.internal.AST.*;
0049: import soot.dava.internal.SET.*;
0050: import soot.dava.internal.asg.*;
0051: import soot.dava.internal.javaRep.*;
0052:
0053: /*
0054: * This class is meant to be extended to write structred analyses.
0055: * The analysis is invoked by invoking the process method sending it
0056: * the body to be analyzed and the input flowset
0057: * Currently support is available only for a forward flow analysis.
0058: * This should soon be refactored to include backwards flow analysis
0059: * (Nomair 16th November 2005)
0060: */
0061: public abstract class StructuredAnalysis {
0062:
0063: public static boolean DEBUG = false;
0064: public static boolean DEBUG_IF = false;
0065: public static boolean DEBUG_WHILE = false;
0066: public static boolean DEBUG_STATEMENTS = false;
0067: public static boolean DEBUG_TRY = false;
0068: /*
0069: public static boolean DEBUG = true;
0070: public static boolean DEBUG_IF = true;
0071: public static boolean DEBUG_WHILE = true;
0072: public static boolean DEBUG_STATEMENTS = true;
0073: public static boolean DEBUG_TRY = true;
0074: /*
0075: /**
0076: * Whenever an abrupt edge is encountered the flow set is
0077: * added into a the break or continue list and a NOPATH
0078: * object is returned
0079: */
0080: DavaFlowSet NOPATH = emptyFlowSet();
0081: public int MERGETYPE; //the confluence operator
0082:
0083: //the three types of operators
0084: final int UNDEFINED = 0;
0085: final int UNION = 1;
0086: final int INTERSECTION = 2;
0087:
0088: //storing before and after sets for each stmt or ASTNode
0089: HashMap<Object, Object> beforeSets, afterSets;
0090:
0091: public StructuredAnalysis() {
0092: beforeSets = new HashMap<Object, Object>();
0093: afterSets = new HashMap<Object, Object>();
0094: MERGETYPE = UNDEFINED;
0095: //invoke user defined function which makes sure that you have the merge operator set
0096: setMergeType();
0097: //System.out.println("MergeType is"+MERGETYPE);
0098: if (MERGETYPE == UNDEFINED)
0099: throw new RuntimeException("MERGETYPE UNDEFINED");
0100: }
0101:
0102: /*
0103: * This method should be used to set the variable MERGETYPE
0104: * use StructuredAnalysis.UNION for union
0105: * use StructuredAnalysis.INTERSECTION for intersection
0106: */
0107: public abstract void setMergeType();
0108:
0109: /*
0110: * Returns the flow object corresponding to the initial values for
0111: * the catch statements
0112: */
0113: public abstract Object newInitialFlow();
0114:
0115: /*
0116: * Returns an empty flow set object
0117: * Notice this has to be a DavaFlowSet or a set extending DavaFlowSet (hopefully constantpropagationFlowSET??)
0118: */
0119: public abstract DavaFlowSet emptyFlowSet();
0120:
0121: /**
0122: * Make a clone of the flowset
0123: * The implementor should know when they want a shallow or deep clone
0124: */
0125: public abstract Object cloneFlowSet(Object flowSet);
0126:
0127: /**
0128: * Specific stmts within AST Constructs are processed through this
0129: * method. It will be invoked everytime a stmt is encountered
0130: */
0131: public abstract Object processStatement(Stmt s, Object input);
0132:
0133: /**
0134: * To have maximum flexibility in analyzing conditions the analysis API
0135: * breaks down the aggregated conditions to simple unary or binary conditions
0136: * user defined code can then deal with each condition separatly.
0137: * To be able to deal with entire aggregated conditions the user should
0138: * wite their own implementation of the method processCondition
0139: */
0140: public abstract Object processUnaryBinaryCondition(
0141: ASTUnaryBinaryCondition cond, Object input);
0142:
0143: /**
0144: * To deal with the local used for synch blocks
0145: */
0146: public abstract Object processSynchronizedLocal(Local local,
0147: Object input);
0148:
0149: /**
0150: * Deal with the key in the switch construct
0151: */
0152: public abstract Object processSwitchKey(Value key, Object input);
0153:
0154: public void print(Object toPrint) {
0155: System.out.println(toPrint.toString());
0156: }
0157:
0158: /**
0159: * This implementation breaks down the aggregated condition to the terminal conditions
0160: * which all have type ASTUnaryBinaryCondition. Once these are obtained the
0161: * abstract method processUnaryBinaryCondition is invoked.
0162: * For aggregated conditions the merging is done in a depth first order of the
0163: * condition tree.
0164: */
0165: public Object processCondition(ASTCondition cond, Object input) {
0166: if (cond instanceof ASTUnaryBinaryCondition) {
0167: return processUnaryBinaryCondition(
0168: (ASTUnaryBinaryCondition) cond, input);
0169: } else if (cond instanceof ASTAggregatedCondition) {
0170: ASTCondition left = ((ASTAggregatedCondition) cond)
0171: .getLeftOp();
0172: Object output1 = processCondition(left, input);
0173:
0174: ASTCondition right = ((ASTAggregatedCondition) cond)
0175: .getRightOp();
0176: Object output2 = processCondition(right, output1);
0177:
0178: return merge(output1, output2);
0179: } else {
0180: throw new RuntimeException(
0181: "Unknown ASTCondition found in structred flow analysis");
0182: }
0183: }
0184:
0185: /*
0186: * The parameter body contains the body to be analysed
0187: * It can be an ASTNode, a Stmt, an augmentedStmt or a list of ASTNodes
0188: * The input is any data that is gathered plus any info needed for making
0189: * decisions during the analysis
0190: */
0191: public Object process(Object body, Object input) {
0192: if (!(input instanceof DavaFlowSet))
0193: throw new RuntimeException(
0194: "process method of StructuredAnalysis invoked with non DavaFlowSet object");
0195:
0196: if (body instanceof ASTNode) {
0197: beforeSets.put(body, input);
0198: Object temp = processASTNode((ASTNode) body, input);
0199: afterSets.put(body, temp);
0200: return temp;
0201: } else if (body instanceof Stmt) {
0202: beforeSets.put(body, input);
0203: Object result = processAbruptStatements((Stmt) body,
0204: (DavaFlowSet) input);
0205: afterSets.put(body, result);
0206: return result;
0207: } else if (body instanceof AugmentedStmt) {
0208: AugmentedStmt as = (AugmentedStmt) body;
0209: Stmt s = as.get_Stmt();
0210:
0211: beforeSets.put(s, input);
0212: Object result = processAbruptStatements(s,
0213: (DavaFlowSet) input);
0214: afterSets.put(s, result);
0215: return result;
0216:
0217: } else if (body instanceof List) {
0218: //this should always be a list of ASTNodes
0219: Iterator it = ((List) body).iterator();
0220: Object result = input;
0221: while (it.hasNext()) {
0222: Object temp = it.next();
0223: if (!(temp instanceof ASTNode))
0224: throw new RuntimeException(
0225: "Body sent to be processed by "
0226: + "StructuredAnalysis contains a list which does not have ASTNodes");
0227: else {
0228: /*
0229: As we are simply going through a list of ASTNodes
0230: The output of the previous becomes the input of the next
0231: */
0232: beforeSets.put(temp, result);
0233: result = processASTNode((ASTNode) temp, result);
0234: afterSets.put(temp, result);
0235: }
0236: }//end of going through list
0237:
0238: //at this point the result var contains the result of processing the List
0239: return result;
0240: } else {
0241: throw new RuntimeException("Body sent to be processed by "
0242: + "StructuredAnalysis is not a valid body");
0243: }
0244: }
0245:
0246: /*
0247: * This method internally invoked by the process method decides which ASTNode
0248: * specialized method to call
0249: */
0250: public Object processASTNode(ASTNode node, Object input) {
0251: if (node instanceof ASTDoWhileNode) {
0252: return processASTDoWhileNode((ASTDoWhileNode) node, input);
0253: } else if (node instanceof ASTForLoopNode) {
0254: return processASTForLoopNode((ASTForLoopNode) node, input);
0255: } else if (node instanceof ASTIfElseNode) {
0256: return processASTIfElseNode((ASTIfElseNode) node, input);
0257: } else if (node instanceof ASTIfNode) {
0258: return processASTIfNode((ASTIfNode) node, input);
0259: } else if (node instanceof ASTLabeledBlockNode) {
0260: return processASTLabeledBlockNode(
0261: (ASTLabeledBlockNode) node, input);
0262: } else if (node instanceof ASTMethodNode) {
0263: return processASTMethodNode((ASTMethodNode) node, input);
0264: } else if (node instanceof ASTStatementSequenceNode) {
0265: return processASTStatementSequenceNode(
0266: (ASTStatementSequenceNode) node, input);
0267: } else if (node instanceof ASTSwitchNode) {
0268: return processASTSwitchNode((ASTSwitchNode) node, input);
0269: } else if (node instanceof ASTSynchronizedBlockNode) {
0270: return processASTSynchronizedBlockNode(
0271: (ASTSynchronizedBlockNode) node, input);
0272: } else if (node instanceof ASTTryNode) {
0273: return processASTTryNode((ASTTryNode) node, input);
0274: } else if (node instanceof ASTWhileNode) {
0275: return processASTWhileNode((ASTWhileNode) node, input);
0276: } else if (node instanceof ASTUnconditionalLoopNode) {
0277: return processASTUnconditionalLoopNode(
0278: (ASTUnconditionalLoopNode) node, input);
0279: } else {
0280: throw new RuntimeException(
0281: "processASTNode called using unknown node type");
0282: }
0283: }
0284:
0285: /**
0286: * This method is called from the specialized ASTNodes.
0287: * The purpose was to deal with different ASTNodes with similar structure in one
0288: * go. The method will deal with retrieve the body of the ASTNode which are known
0289: * to have only one subBody
0290: */
0291: public final Object processSingleSubBodyNode(ASTNode node,
0292: Object input) {
0293: //get the subBodies
0294: List<Object> subBodies = node.get_SubBodies();
0295: if (subBodies.size() != 1) {
0296: throw new RuntimeException(
0297: "processSingleSubBodyNode called with a node without one subBody");
0298: }
0299: //we know there is only one
0300: List subBody = (List) subBodies.get(0);
0301: return process(subBody, input);
0302: }
0303:
0304: /**
0305: * returns label on the ASTNode
0306: * null if the ASTNode cannot hold a label or if the label is null
0307: */
0308: public String getLabel(ASTNode node) {
0309: if (node instanceof ASTLabeledNode) {
0310: Object temp = ((ASTLabeledNode) node).get_Label();
0311: if (temp != null)
0312: return temp.toString();
0313: }
0314: return null;
0315: }
0316:
0317: /**
0318: * Whenever a statement has to be processed the first step is to invoke this method.
0319: * This is to remove the tedious work of adding code to deal with abrupt control flow
0320: * from the programmer of the analysis.
0321: * The method invokes the processStatement method for all other statements
0322: *
0323: * A programmer can decide to override this method if they want to do something specific
0324: */
0325: public Object processAbruptStatements(Stmt s, DavaFlowSet input) {
0326: if (s instanceof ReturnStmt || s instanceof RetStmt
0327: || s instanceof ReturnVoidStmt) {
0328: //dont need to remember this path
0329: return NOPATH;
0330: } else if (s instanceof DAbruptStmt) {
0331: DAbruptStmt abStmt = (DAbruptStmt) s;
0332:
0333: //see if its a break or continue
0334: if (!(abStmt.is_Continue() || abStmt.is_Break())) {
0335: //DAbruptStmt is of only two kinds
0336: throw new RuntimeException(
0337: "Found a DAbruptStmt which is neither break nor continue!!");
0338: }
0339:
0340: DavaFlowSet temp = NOPATH;
0341: SETNodeLabel nodeLabel = abStmt.getLabel();
0342: //System.out.println("here");
0343: if (nodeLabel != null && nodeLabel.toString() != null) {
0344: //explicit abrupt stmt
0345: if (abStmt.is_Continue())
0346: temp.addToContinueList(nodeLabel.toString(), input);
0347: else if (abStmt.is_Break())
0348: temp.addToBreakList(nodeLabel.toString(), input);
0349: else
0350: throw new RuntimeException(
0351: "Found abruptstmt which is neither break nor continue");
0352: } else {
0353: //found implicit break/continue
0354: if (abStmt.is_Continue())
0355: temp.addToImplicitContinues(abStmt, input);
0356: else if (abStmt.is_Break())
0357: temp.addToImplicitBreaks(abStmt, input);
0358: else
0359: throw new RuntimeException(
0360: "Found abruptstmt which is neither break nor continue");
0361: }
0362: return temp;
0363: } else {
0364: /**************************************************************/
0365: /******ALL OTHER STATEMENTS HANDLED BY PROGRAMMER**************/
0366: /**************************************************************/
0367: return processStatement(s, input);
0368: }
0369: }
0370:
0371: /*
0372: * Notice Right now the output of the processing of method bodies
0373: * is returned as the output. This only works for INTRA procedural
0374: * Analysis. For accomodating INTER procedural analysis one needs
0375: * to have a return list of all possible returns (stored in the flowset)
0376: * And merge Returns with the output of normal execution of the body
0377: */
0378: //reasoned about this....seems right!!
0379: public Object processASTMethodNode(ASTMethodNode node, Object input) {
0380: Object temp = processSingleSubBodyNode(node, input);
0381: return temp;
0382: }
0383:
0384: public Object processASTStatementSequenceNode(
0385: ASTStatementSequenceNode node, Object input) {
0386: List<Object> statements = node.getStatements();
0387: Iterator<Object> it = statements.iterator();
0388:
0389: Object output = cloneFlowSet(input);//needed if there are no stmts
0390:
0391: while (it.hasNext()) {
0392: AugmentedStmt as = (AugmentedStmt) it.next();
0393: Stmt s = as.get_Stmt();
0394: /*
0395: Since we are processing a list of statements the output of
0396: previous is input of next
0397: */
0398: output = process(s, output);
0399: if (DEBUG_STATEMENTS) {
0400: System.out.println("After Processing statement " + s
0401: + output.toString());
0402: ;
0403: }
0404: }
0405: return output;
0406: }
0407:
0408: //reasoned about this....seems right!!
0409: public Object processASTLabeledBlockNode(ASTLabeledBlockNode node,
0410: Object input) {
0411: Object output1 = processSingleSubBodyNode(node, input);
0412:
0413: //handle break
0414: String label = getLabel(node);
0415: return handleBreak(label, output1, node);
0416: }
0417:
0418: public Object processASTSynchronizedBlockNode(
0419: ASTSynchronizedBlockNode node, Object input) {
0420: input = processSynchronizedLocal(node.getLocal(), input);
0421:
0422: Object output = processSingleSubBodyNode(node, input);
0423: String label = getLabel(node);
0424: return handleBreak(label, output, node);
0425: }
0426:
0427: //reasoned about this....seems right!!
0428: public Object processASTIfNode(ASTIfNode node, Object input) {
0429: input = processCondition(node.get_Condition(), input);
0430:
0431: Object output1 = processSingleSubBodyNode(node, input);
0432:
0433: //merge with input which tells if the cond did not evaluate to true
0434: Object output2 = merge(input, output1);
0435:
0436: //handle break
0437: String label = getLabel(node);
0438:
0439: Object temp = handleBreak(label, output2, node);
0440:
0441: if (DEBUG_IF) {
0442: System.out.println("Exiting if node" + temp.toString());
0443: ;
0444: }
0445: return temp;
0446: }
0447:
0448: public Object processASTIfElseNode(ASTIfElseNode node, Object input) {
0449: //get the subBodies
0450: List<Object> subBodies = node.get_SubBodies();
0451: if (subBodies.size() != 2) {
0452: throw new RuntimeException(
0453: "processASTIfElseNode called with a node without two subBodies");
0454: }
0455: //we know there is only two subBodies
0456: List subBodyOne = (List) subBodies.get(0);
0457: List subBodyTwo = (List) subBodies.get(1);
0458:
0459: //process Condition
0460: input = processCondition(node.get_Condition(), input);
0461: //the current input flowset is sent to both branches
0462: Object clonedInput = cloneFlowSet(input);
0463: Object output1 = process(subBodyOne, clonedInput);
0464:
0465: clonedInput = cloneFlowSet(input);
0466: Object output2 = process(subBodyTwo, clonedInput);
0467:
0468: Object temp = merge(output1, output2);
0469: //notice we handle breaks only once since these are breaks to the same label or same node
0470: String label = getLabel(node);
0471: output1 = handleBreak(label, temp, node);
0472:
0473: return output1;
0474: }
0475:
0476: public Object processASTWhileNode(ASTWhileNode node, Object input) {
0477: Object lastin = null;
0478: Object initialInput = cloneFlowSet(input);
0479:
0480: String label = getLabel(node);
0481: Object output = null;
0482:
0483: input = processCondition(node.get_Condition(), input);
0484: if (DEBUG_WHILE)
0485: System.out
0486: .println("Going int while (condition processed): "
0487: + input.toString());
0488:
0489: do {
0490: lastin = cloneFlowSet(input);
0491: output = processSingleSubBodyNode(node, input);
0492:
0493: //handle continue
0494: output = handleContinue(label, output, node);
0495:
0496: //merge with the initial input
0497: input = merge(initialInput, output);
0498: input = processCondition(node.get_Condition(), input);
0499: } while (isDifferent(lastin, input));
0500:
0501: //input contains the result of the fixed point
0502: Object temp = handleBreak(label, input, node);
0503: if (DEBUG_WHILE)
0504: System.out
0505: .println("Going out of while: " + temp.toString());
0506: return temp;
0507: }
0508:
0509: public Object processASTDoWhileNode(ASTDoWhileNode node,
0510: Object input) {
0511: Object lastin = null, output = null;
0512: Object initialInput = cloneFlowSet(input);
0513: String label = getLabel(node);
0514: if (DEBUG_WHILE)
0515: System.out.println("Going into do-while: "
0516: + initialInput.toString());
0517:
0518: do {
0519: lastin = cloneFlowSet(input);
0520: output = processSingleSubBodyNode(node, input);
0521:
0522: //handle continue
0523: output = handleContinue(label, output, node);
0524:
0525: output = processCondition(node.get_Condition(), output);
0526:
0527: //merge with the initial input
0528: input = merge(initialInput, output);
0529: } while (isDifferent(lastin, input));
0530:
0531: //output contains the result of the fixed point since do-while breaks of at the processing of cond
0532: Object temp = handleBreak(label, output, node);
0533: if (DEBUG_WHILE)
0534: System.out.println("Going out of do-while: "
0535: + temp.toString());
0536:
0537: return temp;
0538:
0539: }
0540:
0541: public Object processASTUnconditionalLoopNode(
0542: ASTUnconditionalLoopNode node, Object input) {
0543: //an unconditional loop behaves almost like a conditional While loop
0544: Object initialInput = cloneFlowSet(input);
0545: Object lastin = null;
0546: if (DEBUG_WHILE)
0547: System.out.println("Going into while(true): "
0548: + initialInput.toString());
0549:
0550: String label = getLabel(node);
0551: Object output = null;
0552: do {
0553: lastin = cloneFlowSet(input);
0554: output = processSingleSubBodyNode(node, input);
0555:
0556: //handle continue
0557: output = handleContinue(label, output, node);
0558:
0559: //merge this with the initial input
0560: input = merge(initialInput, output);
0561: } while (isDifferent(lastin, input));
0562:
0563: //the output is not part of the set returned
0564: //it is just used to retireve the set of breaklists stored for this label
0565: Object temp = getMergedBreakList(label, output, node);
0566: if (DEBUG_WHILE)
0567: System.out.println("Going out of while(true): "
0568: + temp.toString());
0569: return temp;
0570:
0571: }
0572:
0573: public Object processASTForLoopNode(ASTForLoopNode node,
0574: Object input) {
0575: List<Object> init = node.getInit();
0576: Iterator<Object> it = init.iterator();
0577: while (it.hasNext()) {
0578: AugmentedStmt as = (AugmentedStmt) it.next();
0579: Stmt s = as.get_Stmt();
0580: input = process(s, input);
0581: }
0582:
0583: //finished processing the init part of the for loop
0584: Object initialInput = cloneFlowSet(input);
0585:
0586: input = processCondition(node.get_Condition(), input);
0587: Object lastin = null;
0588: String label = getLabel(node);
0589: Object output2 = null;
0590: do {
0591: lastin = cloneFlowSet(input);
0592:
0593: //process body
0594: Object output1 = processSingleSubBodyNode(node, input);
0595:
0596: //handle continues (Notice this is done before update!!!)
0597: output1 = handleContinue(label, output1, node);
0598:
0599: //notice that we dont merge with the initial output1 from processing singleSubBody
0600: //the handlecontinue function takes care of it
0601:
0602: //handle update
0603: output2 = cloneFlowSet(output1);//if there is nothing in update
0604:
0605: List<Object> update = node.getUpdate();
0606: it = update.iterator();
0607: while (it.hasNext()) {
0608: AugmentedStmt as = (AugmentedStmt) it.next();
0609: Stmt s = as.get_Stmt();
0610: /*
0611: Since we are just going over a list of statements
0612: the output of each statement is the input of the next
0613: */
0614: output2 = process(s, output2);
0615: }
0616:
0617: //output2 is the final result
0618:
0619: //merge this with the input
0620: input = merge(initialInput, output2);
0621: input = processCondition(node.get_Condition(), input);
0622: } while (isDifferent(lastin, input));
0623:
0624: //handle break
0625: return handleBreak(label, input, node);
0626: }
0627:
0628: /*
0629: * Notice ASTSwitch is horribly conservative....eg. if all cases break properly
0630: * it will still merge with defaultOut which will be a NOPATH and bound to have empty or full sets
0631: */
0632: public Object processASTSwitchNode(ASTSwitchNode node, Object input) {
0633: if (DEBUG)
0634: System.out
0635: .println("Going into switch: " + input.toString());
0636:
0637: List<Object> indexList = node.getIndexList();
0638: Map<Object, List<Object>> index2BodyList = node
0639: .getIndex2BodyList();
0640:
0641: Iterator<Object> it = indexList.iterator();
0642:
0643: input = processSwitchKey(node.get_Key(), input);
0644: Object initialIn = cloneFlowSet(input);
0645:
0646: Object out = null;
0647: Object defaultOut = null;
0648:
0649: List<Object> toMergeBreaks = new ArrayList<Object>();
0650:
0651: while (it.hasNext()) {//going through all the cases of the switch statement
0652: Object currentIndex = it.next();
0653: List body = index2BodyList.get(currentIndex);
0654:
0655: //BUG FIX if body is null (fall through we shouldnt invoke process
0656: //Reported by Steffen Pingel 14th Jan 2006 on the soot mailing list
0657: if (body != null) {
0658: out = process(body, input);
0659:
0660: // System.out.println("Breaklist for this out is"+out.getBreakList());
0661: toMergeBreaks.add(cloneFlowSet(out));
0662:
0663: if (currentIndex instanceof String) {
0664: //this is the default
0665: defaultOut = out;
0666: }
0667:
0668: //the input to the next can be a fall through or directly input
0669: input = merge(out, initialIn);
0670: }//body was non null
0671: }
0672:
0673: //have to handle the case when no case matches. The input is the output
0674: Object output = null;
0675: if (out != null) {//just to make sure that there were some cases present
0676:
0677: /*
0678: * January 30th 2006, FOUND BUG
0679: * The initialIn should only be merge with the out if there is no default
0680: * in the list of switch cases
0681: * If there is a default then there is no way that the initialIn is the actual
0682: * result. Then its either the default or one of the outs!!!
0683: */
0684: if (defaultOut != null) {
0685: //there was a default
0686: //System.out.println("DEFAULTSET");
0687: //System.out.println("defaultOut is"+defaultOut);
0688: //System.out.println("out is"+out);
0689:
0690: output = merge(defaultOut, out);
0691: } else {
0692: //there was no default so no case might match
0693: output = merge(initialIn, out);
0694: }
0695:
0696: } else
0697: output = initialIn;
0698:
0699: //handle break
0700: String label = getLabel(node);
0701:
0702: //have to handleBreaks for all the different cases
0703:
0704: List<Object> outList = new ArrayList<Object>();
0705:
0706: //handling breakLists of each of the toMergeBreaks
0707: it = toMergeBreaks.iterator();
0708:
0709: while (it.hasNext()) {
0710: outList.add(handleBreak(label, it.next(), node));
0711: }
0712:
0713: //merge all outList elements. since these are the outputs with breaks handled
0714: Object finalOut = output;
0715: it = outList.iterator();
0716: while (it.hasNext()) {
0717: finalOut = merge(finalOut, it.next());
0718: }
0719:
0720: if (DEBUG)
0721: System.out.println("Going out of switch: "
0722: + finalOut.toString());
0723:
0724: return finalOut;
0725: }
0726:
0727: public Object processASTTryNode(ASTTryNode node, Object input) {
0728:
0729: if (DEBUG_TRY)
0730: System.out.println("TRY START is:" + input);
0731:
0732: //System.out.println("SET beginning of tryBody is:"+input);
0733: List<Object> tryBody = node.get_TryBody();
0734: Object tryBodyOutput = process(tryBody, input);
0735: //System.out.println("SET end of tryBody is:"+tryBodyOutput);
0736:
0737: /*
0738: By default take either top or bottom as the input to the catch statements
0739: Which goes in depends on the type of analysis.
0740: */
0741: Object inputCatch = newInitialFlow();
0742: if (DEBUG_TRY)
0743: System.out.println("TRY initialFLOW is:" + inputCatch);
0744:
0745: List<Object> catchList = node.get_CatchList();
0746: Iterator<Object> it = catchList.iterator();
0747: List<Object> catchOutput = new ArrayList<Object>();
0748:
0749: while (it.hasNext()) {
0750: ASTTryNode.container catchBody = (ASTTryNode.container) it
0751: .next();
0752:
0753: List body = (List) catchBody.o;
0754: //list of ASTNodes
0755:
0756: //result because of going through the catchBody
0757: Object tempResult = process(body, cloneFlowSet(inputCatch));
0758: //System.out.println("TempResult going through body"+tempResult);
0759: catchOutput.add(tempResult);
0760: }
0761:
0762: //handle breaks
0763: String label = getLabel(node);
0764:
0765: /*
0766: * 30th Jan 2005,
0767: * Found bug in handling out breaks
0768: * what was being done was that handleBreak was invoked using just handleBreak(label,tryBodyoutput,node)
0769: * Now what it does is that it looks for the breakList stored in the tryBodyOutput node
0770: * What might happen is that there might be some breaks in the catchOutput which would have gotten
0771: * stored in the breakList of the respective catchoutput
0772: *
0773: * The correct way to handle this is create a list of handledBreak objects (in the outList)
0774: * And then to merge them
0775: */
0776: List<Object> outList = new ArrayList<Object>();
0777:
0778: //handle breaks out of tryBodyOutput
0779: outList.add(handleBreak(label, tryBodyOutput, node));
0780: //System.out.println("After handling break from tryBodyOutput"+outList.get(0));
0781:
0782: //handling breakLists of each of the catchOutputs
0783: it = catchOutput.iterator();
0784: while (it.hasNext()) {
0785: Object temp = handleBreak(label, it.next(), node);
0786:
0787: if (DEBUG_TRY)
0788: System.out.println("TRY handling breaks is:" + temp);
0789:
0790: outList.add(temp);
0791: }
0792:
0793: //merge all outList elements. since these are the outputs with breaks handled
0794: Object out = tryBodyOutput;
0795: it = outList.iterator();
0796: while (it.hasNext()) {
0797: out = merge(out, it.next());
0798: }
0799:
0800: if (DEBUG_TRY)
0801: System.out.println("TRY after merge outList is:" + out);
0802:
0803: //System.out.println("After handling break"+out);
0804:
0805: it = catchOutput.iterator();
0806: while (it.hasNext()) {
0807: out = merge(out, it.next());
0808: }
0809: if (DEBUG_TRY)
0810: System.out.println("TRY END RESULT is:" + out);
0811:
0812: return out;
0813: }
0814:
0815: /*
0816: MERGETYPE var has to be set
0817: 0, means no type set
0818: 1, means union
0819: 2, means intersection
0820: */
0821: public Object merge(Object obj1, Object obj2) {
0822: if (MERGETYPE == 0)
0823: throw new RuntimeException(
0824: "Use the setMergeType method to set the type of merge used in the analysis");
0825:
0826: if (!(obj1 instanceof DavaFlowSet)
0827: || !(obj2 instanceof DavaFlowSet)) {
0828: /* if(obj1 instanceof DavaFlowSet)
0829: System.out.println("obj1 is a davaflowset");
0830: else
0831: System.out.println("obj1 is NOT a davaflowset");
0832:
0833: if(obj2 instanceof DavaFlowSet)
0834: System.out.println("obj2 is a davaflowset");
0835: else
0836: System.out.println("obj2 is NOT a davaflowset"+obj2);
0837: */
0838:
0839: throw new RuntimeException(
0840: "merge not implemented for other flowSet types");
0841: }
0842:
0843: DavaFlowSet in1 = (DavaFlowSet) obj1;
0844: DavaFlowSet in2 = (DavaFlowSet) obj2;
0845:
0846: DavaFlowSet out;
0847: if (in1 == NOPATH && in2 != NOPATH) {
0848: out = in2.clone();
0849: out.copyInternalDataFrom(in1);
0850: return out;
0851: } else if (in1 != NOPATH && in2 == NOPATH) {
0852: out = in1.clone();
0853: out.copyInternalDataFrom(in2);
0854: return out;
0855: } else if (in1 == NOPATH && in2 == NOPATH) {
0856: out = in1.clone();
0857: out.copyInternalDataFrom(in2);
0858: return out; //meaning return NOPATH
0859: } else {//both are not NOPATH
0860: out = emptyFlowSet();
0861: if (MERGETYPE == 1)//union
0862: ((DavaFlowSet) obj1).union((DavaFlowSet) obj2, out);
0863: else if (MERGETYPE == 2)//intersection
0864: ((DavaFlowSet) obj1).intersection((DavaFlowSet) obj2,
0865: out);
0866: else
0867: throw new RuntimeException("Merge type value"
0868: + MERGETYPE + " not recognized");
0869: out.copyInternalDataFrom(obj1);
0870: out.copyInternalDataFrom(obj2);
0871: return out;
0872: }
0873: }
0874:
0875: public Object mergeExplicitAndImplicit(String label,
0876: DavaFlowSet output, List explicitSet, List implicitSet) {
0877: Object toReturn = output.clone();
0878:
0879: if (label != null) {
0880: //use the explicit list
0881: /*
0882: If there is no list associated with this label
0883: or the list is empty
0884: there no explicit merging to be done
0885: */
0886: if (explicitSet != null && explicitSet.size() != 0) {
0887: //explicitSet is a list of DavaFlowSets
0888: Iterator it = explicitSet.iterator();
0889:
0890: //we know there is atleast one element
0891: toReturn = merge(output, it.next());
0892:
0893: while (it.hasNext()) {
0894: //merge this with toReturn
0895: toReturn = merge(toReturn, it.next());
0896: }
0897: }//a non empty explicitSet was found
0898: }//label not null could have explicit sets
0899:
0900: //toReturn contains result of dealing with explicit stmts
0901:
0902: //dealing with implicit set now
0903: if (implicitSet != null) {
0904: //implicitSet is a list of DavaFlowSets
0905: Iterator it = implicitSet.iterator();
0906: while (it.hasNext()) {
0907: //merge this with toReturn
0908: toReturn = merge(toReturn, it.next());
0909: }
0910: }
0911: return toReturn;
0912: }
0913:
0914: /**
0915: * Need to handleBreak stmts
0916: * There can be explicit breaks (in which case label is non null)
0917: * There can always be implicit breaks
0918: * ASTNode is non null
0919: */
0920: public Object handleBreak(String label, Object output, ASTNode node) {
0921: if (!(output instanceof DavaFlowSet))
0922: throw new RuntimeException(
0923: "handleBreak is only implemented for DavaFlowSet type");
0924:
0925: DavaFlowSet out = (DavaFlowSet) output;
0926:
0927: //get the explicit list with this label from the breakList
0928: List explicitSet = out.getBreakSet(label);
0929: //System.out.println("\n\nExplicit set is"+explicitSet);
0930: //getting the implicit list now
0931: if (node == null)
0932: throw new RuntimeException(
0933: "ASTNode sent to handleBreak was null");
0934:
0935: List implicitSet = out.getImplicitlyBrokenSets(node);
0936: //System.out.println("\n\nImplicit set is"+implicitSet);
0937:
0938: //invoke mergeExplicitAndImplicit
0939: return mergeExplicitAndImplicit(label, out, explicitSet,
0940: implicitSet);
0941: }
0942:
0943: /**
0944: * Need to handleContinue stmts
0945: * There can be explicit continues (in which case label is non null)
0946: * There can always be implicit continues
0947: * ASTNode is non null
0948: */
0949: public Object handleContinue(String label, Object output,
0950: ASTNode node) {
0951: if (!(output instanceof DavaFlowSet))
0952: throw new RuntimeException(
0953: "handleContinue is only implemented for DavaFlowSet type");
0954:
0955: DavaFlowSet out = (DavaFlowSet) output;
0956:
0957: //get the explicit list with this label from the continueList
0958: List explicitSet = out.getContinueSet(label);
0959:
0960: //getting the implicit list now
0961: if (node == null)
0962: throw new RuntimeException(
0963: "ASTNode sent to handleContinue was null");
0964:
0965: List implicitSet = out.getImplicitlyContinuedSets(node);
0966:
0967: //invoke mergeExplicitAndImplicit
0968: return mergeExplicitAndImplicit(label, out, explicitSet,
0969: implicitSet);
0970: }
0971:
0972: /**
0973: * Invoked from within the UnconditionalWhile processing method
0974: * Need to handle both explicit and implicit breaks
0975: */
0976: private Object getMergedBreakList(String label, Object output,
0977: ASTNode node) {
0978: if (!(output instanceof DavaFlowSet))
0979: throw new RuntimeException(
0980: "getMergedBreakList is only implemented for DavaFlowSet type");
0981:
0982: List breakSet = ((DavaFlowSet) output).getBreakSet(label);
0983: Object toReturn = null;
0984:
0985: if (breakSet == null) {
0986: //there is no list associated with this label hence no merging to be done
0987: //since this is a call from unconditional this means there should have been an implicit break
0988: toReturn = NOPATH;
0989: } else if (breakSet.size() == 0) {
0990: //list is empty for this label hence no merging to be done
0991: //since this is a call from unconditional this means there should have been an implicit break
0992: toReturn = NOPATH;
0993: } else {
0994: //breakSet is a list of DavaFlowSets
0995: Iterator it = breakSet.iterator();
0996:
0997: //we know there is atleast one element
0998: //making sure we dont send NOPATH
0999: toReturn = it.next();
1000:
1001: while (it.hasNext()) {
1002: //merge this with toReturn
1003: toReturn = merge(toReturn, it.next());
1004: }
1005: }//a non empty breakSet was found
1006:
1007: //dealing with implicit set now
1008:
1009: List implicitSet = ((DavaFlowSet) output)
1010: .getImplicitlyBrokenSets(node);
1011: if (implicitSet != null) {
1012: //implicitSet is a list of DavaFlowSets
1013: Iterator it = implicitSet.iterator();
1014:
1015: //making sure that we dont send NOPATH
1016: if (implicitSet.size() > 0)
1017: toReturn = it.next();
1018:
1019: while (it.hasNext()) {
1020: //merge this with toReturn
1021: toReturn = merge(toReturn, it.next());
1022: }
1023: }
1024: return toReturn;
1025: }
1026:
1027: public boolean isDifferent(Object oldObj, Object newObj) {
1028: if (oldObj instanceof DavaFlowSet
1029: && newObj instanceof DavaFlowSet) {
1030: if (((DavaFlowSet) oldObj).equals(newObj)
1031: && ((DavaFlowSet) oldObj)
1032: .internalDataMatchesTo(newObj)) {
1033: //set matches and breaks and continues also match
1034: //System.out.println("NOT DIFFERENT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
1035: return false;
1036: } else {
1037: //System.out.println(oldObj);
1038: //System.out.println(newObj);
1039: //System.out.println("DIFFERENT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
1040: return true;
1041: }
1042: } else
1043: throw new RuntimeException(
1044: "isDifferent not implemented for other flowSet types");
1045: }
1046:
1047: /*
1048: * The before set contains the before set of an ASTNode , a Stmt , and AugmentedStmt,
1049: * Notice for instance for a for loop
1050: * we will get a before set before the loop and an after set after the loop
1051: *
1052: * we dont have info about before set before executing a particular stmt
1053: * that kind of info is available if you know which stmt u want e.g. the update stmt
1054: */
1055: public Object getBeforeSet(Object beforeThis) {
1056: return beforeSets.get(beforeThis);
1057: }
1058:
1059: public Object getAfterSet(Object afterThis) {
1060: return afterSets.get(afterThis);
1061: }
1062:
1063: public void debug(String methodName, String debug) {
1064: if (DEBUG)
1065: System.out.println("Class: StructuredAnalysis MethodName: "
1066: + methodName + " DEBUG: " + debug);
1067: }
1068:
1069: public void debug(String debug) {
1070: if (DEBUG)
1071: System.out.println("Class: StructuredAnalysis DEBUG: "
1072: + debug);
1073: }
1074:
1075: }
|