+ Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
+ Set<FlowNode> reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode);
+
+ Map<NTuple<Location>, Set<NTuple<Location>>> mapPrefixToIncomingLocTupleSet =
+ new HashMap<NTuple<Location>, Set<NTuple<Location>>>();
+
+ Set<FlowNode> localInNodeSet = new HashSet<FlowNode>();
+ Set<FlowNode> localOutNodeSet = new HashSet<FlowNode>();
+
+ CompositeLocation flowNodeInferLoc =
+ generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(flowNode));
+
+ List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
+
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ FlowNode inNode = (FlowNode) iterator.next();
+ NTuple<Location> inNodeTuple = flowGraph.getLocationTuple(inNode);
+
+ CompositeLocation inNodeInferredLoc =
+ generateInferredCompositeLocation(methodInfo, inNodeTuple);
+
+ NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
+
+ if (inNodeTuple.size() > 1) {
+ for (int i = 1; i < inNodeInferredLocTuple.size(); i++) {
+ NTuple<Location> prefix = inNodeInferredLocTuple.subList(0, i);
+ if (!prefixList.contains(prefix)) {
+ prefixList.add(prefix);
+ }
+ addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple);
+ }
+ } else {
+ localInNodeSet.add(inNode);
+ }
+ }
+
+ Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
+ public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
+ int s0 = arg0.size();
+ int s1 = arg1.size();
+ if (s0 > s1) {
+ return -1;
+ } else if (s0 == s1) {
+ return 0;
+ } else {
+ return 1;
+ }
+ }
+ });
+
+ for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
+ FlowNode reachableNode = (FlowNode) iterator2.next();
+ if (reachableNode.getDescTuple().size() == 1) {
+ localOutNodeSet.add(reachableNode);
+ }
+ }
+
+ // find out reachable nodes that have the longest common prefix
+ for (int i = 0; i < prefixList.size(); i++) {
+ NTuple<Location> curPrefix = prefixList.get(i);
+ Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
+
+ for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
+ FlowNode reachableNode = (FlowNode) iterator2.next();
+ NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
+ CompositeLocation reachLocInferLoc =
+ generateInferredCompositeLocation(methodInfo, reachLocTuple);
+ if (reachLocInferLoc.getTuple().startsWith(curPrefix)) {
+ reachableCommonPrefixSet.add(reachLocTuple);
+ }
+ }
+
+ // check if the lattice has the relation in which higher prefix is
+ // actually lower than the current node
+ CompositeLocation prefixInferLoc = generateInferredCompositeLocation(methodInfo, curPrefix);
+ if (isGreaterThan(methodLattice, flowNodeInferLoc, prefixInferLoc)) {
+ reachableCommonPrefixSet.add(curPrefix);
+ }
+
+ if (!reachableCommonPrefixSet.isEmpty()) {
+ // found reachable nodes that start with the prefix curPrefix
+ // need to assign a composite location
+
+ // first, check if there are more than one the set of locations that has
+ // the same length of the longest reachable prefix, no way to assign
+ // a composite location to the input local var
+ prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet);
+
+ Set<NTuple<Location>> incomingCommonPrefixSet =
+ mapPrefixToIncomingLocTupleSet.get(curPrefix);
+
+ int idx = curPrefix.size();
+ NTuple<Location> element = incomingCommonPrefixSet.iterator().next();
+ Descriptor desc = element.get(idx).getDescriptor();
+
+ SSJavaLattice<String> lattice = getLattice(desc);
+ LocationInfo locInfo = getLocationInfo(desc);
+
+ CompositeLocation inferLocation =
+ generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
+
+ // methodInfo.getInferLocation(localVarDesc);
+ CompositeLocation newInferLocation = new CompositeLocation();
+
+ System.out.println("PREV INFER LOCATION=" + inferLocation + " curPrefix="
+ + curPrefix);
+ if (inferLocation.getTuple().startsWith(curPrefix)) {
+ // the same infer location is already existed. no need to do
+ // anything
+ return true;
+ } else {
+ // assign a new composite location
+
+ // String oldMethodLocationSymbol =
+ // inferLocation.get(0).getLocIdentifier();
+ String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
+ for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
+ newInferLocation.addLocation(curPrefix.get(locIdx));
+ }
+ Location newLocationElement = new Location(desc, newLocSymbol);
+ newInferLocation.addLocation(newLocationElement);
+
+ // if (flowNode.getDescTuple().size() == 1) {
+ // maps local variable to location types of the common prefix
+ methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone());
+ // }
+
+ // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation);
+ addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc,
+ newInferLocation);
+ methodInfo.removeMaplocalVarToLocSet(localVarDesc);
+
+ // add the field/var descriptor to the set of the location symbol
+ int flowNodeTupleSize = flowNode.getDescTuple().size();
+ Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(flowNodeTupleSize - 1);
+ int inferLocSize = newInferLocation.getSize();
+ Location lastLoc = newInferLocation.get(inferLocSize - 1);
+ Descriptor enclosingDesc = lastLoc.getDescriptor();
+ getLocationInfo(enclosingDesc).addMapLocSymbolToDescSet(lastLoc.getLocIdentifier(),
+ lastFlowNodeDesc);
+
+ // clean up the previous location
+ // Location prevInferLocElement =
+ // inferLocation.get(inferLocation.getSize() - 1);
+ // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor();
+ //
+ // SSJavaLattice<String> targetLattice;
+ // LocationInfo targetInfo;
+ // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) {
+ // targetLattice = methodLattice;
+ // targetInfo = methodInfo;
+ // } else {
+ // targetLattice = getLattice(prevInferLocElement.getDescriptor());
+ // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor());
+ // }
+ //
+ // Set<Pair<Descriptor, Descriptor>> associstedDescSet =
+ // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier());
+ //
+ // if (associstedDescSet.size() == 1) {
+ // targetLattice.remove(prevInferLocElement.getLocIdentifier());
+ // } else {
+ // associstedDescSet.remove(lastFlowNodeDesc);
+ // }
+
+ }
+
+ System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to "
+ + flowNode);
+
+ String newlyInsertedLocName =
+ newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier();
+
+ System.out.println("-- add in-flow");
+ for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) {
+ NTuple<Location> tuple = (NTuple<Location>) iterator.next();
+ System.out.println("--in-flow tuple=" + tuple);
+ Location loc = tuple.get(idx);
+ String higher = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier();
+ addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName);
+ }
+
+ System.out.println("-- add local in-flow");
+ for (Iterator iterator = localInNodeSet.iterator(); iterator.hasNext();) {
+ FlowNode localNode = (FlowNode) iterator.next();
+
+ if (localNode.equals(flowNode)) {
+ continue;
+ }
+
+ CompositeLocation inNodeInferLoc =
+ generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(localNode));
+
+ if (isCompositeLocation(inNodeInferLoc)) {
+ // need to make sure that newLocSymbol is lower than the infernode
+ // location in the field lattice
+ System.out.println("----srcNode=" + localNode + " dstNode=" + flowNode);
+ addRelationToLattice(methodInfo.getMethodDesc(), methodLattice, methodInfo, localNode,
+ flowNode);
+
+ }
+
+ }
+
+ System.out.println("-- add out flow");
+ for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) {
+ NTuple<Location> tuple = (NTuple<Location>) iterator.next();
+ if (tuple.size() > idx) {
+ Location loc = tuple.get(idx);
+ String lower = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier();
+ addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower);
+ }
+ }
+
+ System.out.println("-- add local out flow");
+ for (Iterator iterator = localOutNodeSet.iterator(); iterator.hasNext();) {
+ FlowNode localOutNode = (FlowNode) iterator.next();
+
+ if (localOutNode.equals(flowNode)) {
+ continue;
+ }
+
+ CompositeLocation outNodeInferLoc =
+ generateInferredCompositeLocation(methodInfo,
+ flowGraph.getLocationTuple(localOutNode));
+
+ if (isCompositeLocation(outNodeInferLoc)) {
+ System.out.println("--- srcNode=" + flowNode + " dstNode=" + localOutNode);
+ addRelationToLattice(methodInfo.getMethodDesc(), methodLattice, methodInfo, flowNode,
+ localOutNode);
+
+ }
+ }
+ System.out.println("-- end of add local out flow");
+
+ return true;
+ }
+
+ }
+
+ return false;
+
+ }
+
+ private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar,
+ CompositeLocation inferLoc) {
+
+ Location locElement = inferLoc.get((inferLoc.getSize() - 1));
+ Descriptor enclosingDesc = locElement.getDescriptor();
+ LocationInfo locInfo = getLocationInfo(enclosingDesc);
+ locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar);
+ }
+
+ private boolean isCompositeLocation(CompositeLocation cl) {
+ return cl.getSize() > 1;
+ }
+
+ private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
+ for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
+ Descriptor desc = (Descriptor) iterator.next();
+
+ if (desc.equals(LocationInference.GLOBALDESC)) {
+ return true;
+ } else if (desc instanceof VarDescriptor) {
+ if (!((VarDescriptor) desc).getType().isPrimitive()) {
+ return true;
+ }
+ } else if (desc instanceof FieldDescriptor) {
+ if (!((FieldDescriptor) desc).getType().isPrimitive()) {
+ return true;
+ }
+ }
+
+ }
+ return false;
+ }
+
+ private void addRelationHigherToLower(SSJavaLattice<String> lattice, LocationInfo locInfo,
+ String higher, String lower) throws CyclicFlowException {
+
+ System.out.println("---addRelationHigherToLower " + higher + " -> " + lower
+ + " to the lattice of " + locInfo.getDescIdentifier());
+ // if (higher.equals(lower) && lattice.isSharedLoc(higher)) {
+ // return;
+ // }
+ Set<String> cycleElementSet = lattice.getPossibleCycleElements(higher, lower);
+
+ boolean hasNonPrimitiveElement = false;
+ for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
+ String cycleElementLocSymbol = (String) iterator.next();
+
+ Set<Descriptor> descSet = locInfo.getDescSet(cycleElementLocSymbol);
+ if (containsNonPrimitiveElement(descSet)) {
+ hasNonPrimitiveElement = true;
+ break;
+ }
+ }
+
+ if (hasNonPrimitiveElement) {
+ System.out.println("#Check cycle= " + lower + " < " + higher + " cycleElementSet="
+ + cycleElementSet);
+ // if there is non-primitive element in the cycle, no way to merge cyclic
+ // elements into the shared location
+ throw new CyclicFlowException();
+ }