diff --git a/src/org/ntlab/deltaViewer/CollaborationLayout.java b/src/org/ntlab/deltaViewer/CollaborationLayout.java index 2469a6b..0cc39a0 100644 --- a/src/org/ntlab/deltaViewer/CollaborationLayout.java +++ b/src/org/ntlab/deltaViewer/CollaborationLayout.java @@ -1,481 +1,548 @@ -package org.ntlab.deltaViewer; - -import java.util.AbstractMap; -import java.util.ArrayList; -import java.util.Collections; -import java.util.HashMap; -import java.util.HashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; - -import org.ntlab.deltaExtractor.Alias; -import org.ntlab.deltaExtractor.Alias.AliasType; -import org.ntlab.deltaExtractor.IAliasCollector; -import org.ntlab.trace.ArrayAccess; -import org.ntlab.trace.ArrayCreate; -import org.ntlab.trace.ArrayUpdate; -import org.ntlab.trace.FieldAccess; -import org.ntlab.trace.FieldUpdate; -import org.ntlab.trace.MethodExecution; -import org.ntlab.trace.MethodInvocation; -import org.ntlab.trace.Reference; -import org.ntlab.trace.Statement; - -import com.mxgraph.model.mxICell; -import com.mxgraph.util.mxPoint; - -public class CollaborationLayout implements IObjectLayout { - private static final int angleStep = 15; - private mxPoint coordinatorPoint = new mxPoint(0, 100); - private double step; - private double padding; - - @Override - public void execute(IObjectCallGraph objectCallGraph, IAliasCollector aliasCollector, Map objectToVertexMap) { - step = 150; - padding = 200; - - // Extract the bottom reference. - Statement relatedSt = objectCallGraph.getRelatedPoints().get(objectCallGraph.getRelatedPoints().size() - 1).getStatement(); - String bottomSrcObjId = null; - String bottomDstObjId = null; - if (relatedSt instanceof FieldUpdate) { - // container to component - bottomSrcObjId = ((FieldUpdate) relatedSt).getContainerObjId(); - bottomDstObjId = ((FieldUpdate) relatedSt).getValueObjId(); - } else if (relatedSt instanceof ArrayUpdate) { - // container to component - bottomSrcObjId = ((ArrayUpdate) relatedSt).getArrayObjectId(); - bottomDstObjId = ((ArrayUpdate) relatedSt).getValueObjectId(); - } else if (relatedSt instanceof MethodInvocation) { - MethodInvocation methodInvStatement = (MethodInvocation) relatedSt; - MethodExecution calledMethodExec = methodInvStatement.getCalledMethodExecution(); - String methodSignature = calledMethodExec.getSignature(); - if (calledMethodExec.isCollectionType() - && (methodSignature.contains("add(") - || methodSignature.contains("set(") - || methodSignature.contains("put(") - || methodSignature.contains("push(") - || methodSignature.contains("addElement("))) { - // container to component - bottomSrcObjId = calledMethodExec.getThisObjId(); - bottomDstObjId = calledMethodExec.getArguments().get(0).getId(); - } else { - // this to another - bottomSrcObjId = methodInvStatement.getThisObjId(); - bottomDstObjId = calledMethodExec.getReturnValue().getId(); - } - } else { - return; - } - - // Extract the reference access history. - List references = objectCallGraph.getReferences(); - Map> referenceHistory = new HashMap<>(); - int order = 0; - for (Alias a: aliasCollector.getAliasList()) { - int idx = -1; - if (a.getAliasType() == AliasType.FIELD) { - FieldAccess f = (FieldAccess) a.getOccurrencePoint().getStatement(); - idx = references.indexOf(new Reference(f.getContainerObjId(), f.getValueObjId(), f.getContainerClassName(), f.getValueClassName())); - } else if (a.getAliasType() == AliasType.ARRAY_ELEMENT) { - ArrayAccess aa = (ArrayAccess) a.getOccurrencePoint().getStatement(); - idx = references.indexOf(new Reference(aa.getArrayObjectId(), aa.getValueObjectId(), aa.getArrayClassName(), aa.getValueClassName())); - } else if (a.getAliasType() == AliasType.RETURN_VALUE) { - MethodExecution methodExec = a.getMethodExecution(); - if (methodExec.getSignature().contains("List.get(") || - methodExec.getSignature().contains("Map.get(")) { - String srcObjId = methodExec.getThisObjId(); - String dstObjId = methodExec.getReturnValue().getId(); - String srcClassName = methodExec.getThisClassName(); - String dstClassName = methodExec.getReturnValue().getActualType(); - idx = references.indexOf(new Reference(srcObjId, dstObjId, srcClassName, dstClassName)); - } - } else if (a.getAliasType() == AliasType.CONSTRACTOR_INVOCATION) { - MethodInvocation c = (MethodInvocation) a.getOccurrencePoint().getStatement(); - String srcObjId = a.getMethodExecution().getThisObjId(); - String dstObjId = c.getCalledMethodExecution().getThisObjId(); - String srcClassName = a.getMethodExecution().getThisClassName(); - String dstClassName = c.getCalledMethodExecution().getThisClassName(); - idx = references.indexOf(new Reference(srcObjId, dstObjId, srcClassName, dstClassName)); - } else if (a.getAliasType() == AliasType.ARRAY_CREATE) { - ArrayCreate ac = (ArrayCreate) a.getOccurrencePoint().getStatement(); - String srcObjId = a.getMethodExecution().getThisObjId(); - String srcClassName = a.getMethodExecution().getThisClassName(); - idx = references.indexOf(new Reference(srcObjId, ac.getArrayObjectId(), srcClassName, ac.getArrayClassName())); - } - if (idx >= 0) { - Reference r = references.get(idx); - List rHIstory = referenceHistory.get(r); - if (rHIstory == null) { - rHIstory = new ArrayList<>(); - referenceHistory.put(r, rHIstory); - } - rHIstory.add(order); - } - order++; - } - - // Construct the object graph. - Map> preds = new HashMap<>(); - Map> succs = new HashMap<>(); - for (Reference r: references) { - String dstObjId = r.getDstObjectId(); - List pre = preds.get(dstObjId); - if (pre == null) { - pre = new ArrayList(); - preds.put(dstObjId, pre); - } - pre.add(r); - String srcObjId = r.getSrcObjectId(); - List suc = succs.get(srcObjId); - if (suc == null) { - suc = new ArrayList(); - succs.put(srcObjId, suc); - } - suc.add(r); - } - - // Extract the source side and destination side paths. - String topObjId = objectCallGraph.getStartPoints().get(0).getThisObjId(); - List dstSide = new ArrayList<>(); - List dstSideObjects = new ArrayList<>(); - String dstObjId = bottomDstObjId; - dstSideObjects.add(dstObjId); - while (!dstObjId.equals(topObjId)) { - if (preds.get(dstObjId) != null) { - Reference minRef = getFirstReferece(preds.get(dstObjId), referenceHistory, true); - dstSide.add(minRef); - dstObjId = minRef.getSrcObjectId(); - } else { - dstSide.add(null); - dstObjId = topObjId; - } - dstSideObjects.add(dstObjId); - } - - List srcSide = new ArrayList<>(); - List srcSideObjects = new ArrayList<>(); - String srcObjId = bottomSrcObjId; - srcSideObjects.add(srcObjId); - while (!srcObjId.equals(topObjId)) { - if (preds.get(srcObjId) != null) { - Reference maxRef = getFirstReferece(preds.get(srcObjId), referenceHistory, false); - srcSide.add(maxRef); - srcObjId = maxRef.getSrcObjectId(); - } else { - srcSide.add(null); - srcObjId = topObjId; - } - srcSideObjects.add(srcObjId); - } - - // Fix the confluent points. - List> confluPoints = new ArrayList<>(); - boolean bConfluent = false; - int hight = 0; - int width = -1; - int dstHight = 0; - int srcHight = 0; - for (String srcObj: srcSideObjects) { - if (dstSideObjects.contains(srcObj)) { - if (!bConfluent) { - int dstDiff = dstSideObjects.indexOf(srcObj) - dstHight; - int srcDiff = srcSideObjects.indexOf(srcObj) - srcHight; - dstHight += dstDiff; - srcHight += srcDiff; - if (dstDiff > srcDiff) { - hight += dstDiff; - } else { - hight += srcDiff; - } - if (width < 0) width = dstHight; - confluPoints.add(new AbstractMap.SimpleEntry(srcObj, hight)); - bConfluent = true; - } else { - hight++; - } - } else { - bConfluent = false; - } - } - coordinatorPoint.setX(coordinatorPoint.getX() + step * width + padding); - double xCor = coordinatorPoint.getX(); - double yCor = coordinatorPoint.getY(); - Set fixed = new HashSet<>(); - for (Map.Entry confluPoint: confluPoints) { - setVertexCoordinate(objectToVertexMap.get(confluPoint.getKey()), xCor, yCor + (hight - confluPoint.getValue()) * step); - fixed.add(confluPoint.getKey()); - } - - // Fix the bottom objects. - Map.Entry firstConfl = confluPoints.get(0); - dstHight = hight - firstConfl.getValue() + dstSideObjects.indexOf(firstConfl.getKey()); - srcHight = hight - firstConfl.getValue() + srcSideObjects.indexOf(firstConfl.getKey()); - int width2 = srcSideObjects.indexOf(firstConfl.getKey()); - setVertexCoordinate(objectToVertexMap.get(bottomDstObjId), padding, yCor + dstHight * step); - fixed.add(bottomDstObjId); - setVertexCoordinate(objectToVertexMap.get(bottomSrcObjId), xCor + width2 * step, yCor + srcHight * step); - fixed.add(bottomSrcObjId); - - // Fix the destination side, source side and common path. - int srcIndex = 0; - int dstIndex = 0; - double dstDirection = 60; - double srcDirection = 120; - for (Map.Entry confluPoint: confluPoints) { - String conflObj = confluPoint.getKey(); - - // Fix the destination side path. - List path = dstSideObjects.subList(dstIndex, dstSideObjects.indexOf(conflObj) + 1); - if (path.size() > 2) fixPath(path, dstDirection, objectToVertexMap, fixed, true); - dstDirection = 120; - dstIndex = dstSideObjects.indexOf(conflObj); - - // Fix the source side path. - path = srcSideObjects.subList(srcIndex, srcSideObjects.indexOf(conflObj) + 1); - if (path.size() > 2) fixPath(path, srcDirection, objectToVertexMap, fixed, true); - srcDirection = 60; - srcIndex = srcSideObjects.indexOf(conflObj); - - // Fix the common path. - int commonHight = confluPoint.getValue(); - for (;;) { - commonHight++; - srcIndex++; - dstIndex++; - if (srcIndex >= srcSideObjects.size() || dstIndex >= dstSideObjects.size()) break; - if (!srcSideObjects.get(srcIndex).equals(dstSideObjects.get(dstIndex))) break; - String commonObjId = srcSideObjects.get(srcIndex); - setVertexCoordinate(objectToVertexMap.get(commonObjId), xCor, yCor + (hight - commonHight) * step); - fixed.add(commonObjId); - } - srcIndex--; - dstIndex--; - } - - // Fix the branches from the destination side path. - for (Reference ref: dstSide) { - if (ref != null) { - List nextRefs = new ArrayList<>(preds.get(ref.getDstObjectId())); - nextRefs = new ArrayList<>(nextRefs); - nextRefs.remove(ref); - double direction = getDirection(ref, objectToVertexMap) - angleStep; - while (nextRefs.size() > 0) { - Reference firstRef = getFirstReferece(nextRefs, referenceHistory, true); - List path = new ArrayList<>(); - path.add(firstRef.getDstObjectId()); - traversePreds(preds, firstRef, direction, true, referenceHistory, objectToVertexMap, fixed, path); - nextRefs.remove(firstRef); - direction = getDirection(firstRef, objectToVertexMap) - angleStep; - } - } - } - - // Fix the branches from the source side path. - for (Reference ref: srcSide) { - if (ref != null) { - List nextRefs = new ArrayList<>(preds.get(ref.getDstObjectId())); - nextRefs = new ArrayList<>(nextRefs); - nextRefs.remove(ref); - double direction = getDirection(ref, objectToVertexMap) + angleStep; - while (nextRefs.size() > 0) { - Reference firstRef = getFirstReferece(nextRefs, referenceHistory, false); - List path = new ArrayList<>(); - path.add(firstRef.getDstObjectId()); - traversePreds(preds, firstRef, direction, false, referenceHistory, objectToVertexMap, fixed, path); - nextRefs.remove(firstRef); - direction = getDirection(firstRef, objectToVertexMap) + angleStep; - } - } - } - - // Fix the reverse branches from the destination side path. - Collections.reverse(dstSide); - for (Reference ref: dstSide) { - if (ref != null) { - List nextRefs = new ArrayList<>(succs.get(ref.getSrcObjectId())); - nextRefs = new ArrayList<>(nextRefs); - nextRefs.remove(ref); - double direction = getDirection(ref, objectToVertexMap) + 180 + angleStep; - while (nextRefs.size() > 0) { - Reference firstRef = getFirstReferece(nextRefs, referenceHistory, true); - List path = new ArrayList<>(); - path.add(firstRef.getSrcObjectId()); - traverseSuccs(succs, firstRef, direction, true, referenceHistory, objectToVertexMap, fixed, path); - nextRefs.remove(firstRef); - direction = getDirection(firstRef, objectToVertexMap) + 180 + angleStep; - } - } - } - - // Fix the reverse branches from the source side path. - Collections.reverse(srcSide); - for (Reference ref: srcSide) { - if (ref != null) { - List nextRefs = new ArrayList<>(succs.get(ref.getSrcObjectId())); - nextRefs = new ArrayList<>(nextRefs); - nextRefs.remove(ref); - double direction = getDirection(ref, objectToVertexMap) + 180 - angleStep; - while (nextRefs.size() > 0) { - Reference firstRef = getFirstReferece(nextRefs, referenceHistory, false); - List path = new ArrayList<>(); - path.add(firstRef.getSrcObjectId()); - traverseSuccs(succs, firstRef, direction, false, referenceHistory, objectToVertexMap, fixed, path); - nextRefs.remove(firstRef); - direction = getDirection(firstRef, objectToVertexMap) + 180 - angleStep; - } - } - } - } - - private double getDirection(Reference ref, Map objToVtx) { - ObjectVertex src = objToVtx.get(ref.getSrcObjectId()); - ObjectVertex dst = objToVtx.get(ref.getDstObjectId()); - return Math.toDegrees(Math.atan2(dst.getY() - src.getY(), src.getX() - dst.getX())); - } - - private Reference getFirstReferece(List refs, Map> referenceHistory, boolean bLeftFirst) { - double first = 0.0; - Reference firstRef = null; - for (Reference ref: refs) { - double avgOrder = 0.0; - if (referenceHistory.get(ref) != null) { - for (int ord: referenceHistory.get(ref)) { - avgOrder += (double) ord; - } - avgOrder /= ((double) referenceHistory.get(ref).size()); - } - if (firstRef == null || (bLeftFirst && avgOrder < first) || (!bLeftFirst && avgOrder > first)) { - firstRef = ref; - first = avgOrder; - } - } - return firstRef; - } - - private void traversePreds(Map> preds, Reference ref, double direction, boolean bLeftFirst, Map> referenceHistory, Map objToVtx, Set fixed, List path) { - String curObj = ref.getSrcObjectId(); - path.add(curObj); - if (fixed.contains(curObj)) { - if (path.size() > 2) fixPath(path, direction, objToVtx, fixed, true); - return; - } - List nextRefs = preds.get(curObj); - if (nextRefs == null || nextRefs.size() == 0) { - if (path.size() > 2) fixPath(path, direction, objToVtx, fixed, false); - return; - } - nextRefs = new ArrayList<>(nextRefs); - do { - Reference firstRef = getFirstReferece(nextRefs, referenceHistory, bLeftFirst); - traversePreds(preds, firstRef, direction, bLeftFirst, referenceHistory, objToVtx, fixed, path); - path = new ArrayList<>(); - path.add(curObj); - nextRefs.remove(firstRef); - direction = getDirection(firstRef, objToVtx); - if (bLeftFirst) { - direction -= angleStep; - } else { - direction += angleStep; - } - } while (nextRefs.size() > 0); - return; - } - - - private void traverseSuccs(Map> succs, Reference ref, double direction, boolean bLeftFirst, Map> referenceHistory, Map objToVtx, Set fixed, List path) { - String curObj = ref.getDstObjectId(); - path.add(curObj); - if (fixed.contains(curObj)) { - if (path.size() > 2) fixPath(path, direction, objToVtx, fixed, true); - return; - } - List nextRefs = succs.get(curObj); - if (nextRefs == null || nextRefs.size() == 0) { - if (path.size() > 2) fixPath(path, direction, objToVtx, fixed, false); - return; - } - nextRefs = new ArrayList<>(nextRefs); - do { - Reference firstRef = getFirstReferece(nextRefs, referenceHistory, bLeftFirst); - traverseSuccs(succs, firstRef, direction, bLeftFirst, referenceHistory, objToVtx, fixed, path); - path = new ArrayList<>(); - path.add(curObj); - nextRefs.remove(firstRef); - direction = getDirection(firstRef, objToVtx) + 180; - if (bLeftFirst) { - direction += angleStep; - } else { - direction -= angleStep; - } - } while (nextRefs.size() > 0); - return; - } - - private void fixPath(List path, double direction, Map objToVtx, Set fixed, boolean bClose) { - if (path.size() < 2) return; - ObjectVertex start = objToVtx.get(path.get(0)); - double x = start.getX(); - double y = start.getY(); - double dirY = -Math.sin(Math.toRadians(direction)); - double dirX = Math.cos(Math.toRadians(direction)); - if (!bClose) { - // straight line - for (int i = 1; i < path.size(); i++) { - x += step * dirX; - y += step * dirY; - setVertexCoordinate(objToVtx.get(path.get(i)), x, y); - fixed.add(path.get(i)); - } - } else { - ObjectVertex end = objToVtx.get(path.get(path.size() - 1)); - double diffX = end.getX() - start.getX(); - double diffY = end.getY() - start.getY(); - double distance = Math.sqrt(diffX * diffX + diffY * diffY); - diffX /= distance; - diffY /= distance; - double outer = dirX * diffY - dirY * diffX; - double centerX, centerY, vecX, vecY; - double theta = Math.acos(diffX * dirX + diffY * dirY); - double radius = distance / 2 / Math.sin(theta); - if (outer > 0) { - vecX = -dirY; - vecY = dirX; - theta = theta * 2.0 / (double) (path.size() - 1); - } else if (outer < 0) { - vecX = dirY; - vecY = -dirX; - theta = -theta * 2.0 / (double) (path.size() - 1); - } else { - // straight line - diffX *= distance / (double) (path.size() - 1); - diffY *= distance / (double) (path.size() - 1); - for (int i = 1; i < path.size(); i++) { - x += diffX; - y += diffY; - setVertexCoordinate(objToVtx.get(path.get(i)), x, y); - fixed.add(path.get(i)); - } - return; - } - // arc - centerX = x + radius * vecX; - centerY = y + radius * vecY; - for (int i = 1; i < path.size() - 1; i++) { - double tmp = vecX * Math.cos(theta) - vecY * Math.sin(theta); - vecY = vecX * Math.sin(theta) + vecY * Math.cos(theta); - vecX = tmp; - setVertexCoordinate(objToVtx.get(path.get(i)), centerX - radius * vecX, centerY - radius * vecY); - fixed.add(path.get(i)); - } - } - } - - private void setVertexCoordinate(ObjectVertex vertex, double x, double y) { - vertex.setX(x); - vertex.setY(y); - vertex.setInitialPoint(x, y); - } -} +package org.ntlab.deltaViewer; + +import java.util.AbstractMap; +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import org.ntlab.deltaExtractor.Alias; +import org.ntlab.deltaExtractor.Alias.AliasType; +import org.ntlab.deltaExtractor.IAliasCollector; +import org.ntlab.trace.ArrayAccess; +import org.ntlab.trace.ArrayCreate; +import org.ntlab.trace.ArrayUpdate; +import org.ntlab.trace.FieldAccess; +import org.ntlab.trace.FieldUpdate; +import org.ntlab.trace.MethodExecution; +import org.ntlab.trace.MethodInvocation; +import org.ntlab.trace.Reference; +import org.ntlab.trace.Statement; + +import com.mxgraph.model.mxICell; +import com.mxgraph.util.mxPoint; + +public class CollaborationLayout implements IObjectLayout { + private static final int angleStep = 15; + private mxPoint coordinatorPoint = new mxPoint(0, 100); + private double step; + private double padding; + + @Override + public void execute(IObjectCallGraph objectCallGraph, IAliasCollector aliasCollector, Map objectToVertexMap) { + step = 150; + padding = 200; + + // Extract the bottom reference. + Statement relatedSt = objectCallGraph.getRelatedPoints().get(objectCallGraph.getRelatedPoints().size() - 1).getStatement(); + String bottomSrcObjId = null; + String bottomDstObjId = null; + if (relatedSt instanceof FieldUpdate) { + // container to component + bottomSrcObjId = ((FieldUpdate) relatedSt).getContainerObjId(); + bottomDstObjId = ((FieldUpdate) relatedSt).getValueObjId(); + } else if (relatedSt instanceof ArrayUpdate) { + // container to component + bottomSrcObjId = ((ArrayUpdate) relatedSt).getArrayObjectId(); + bottomDstObjId = ((ArrayUpdate) relatedSt).getValueObjectId(); + } else if (relatedSt instanceof MethodInvocation) { + MethodInvocation methodInvStatement = (MethodInvocation) relatedSt; + MethodExecution calledMethodExec = methodInvStatement.getCalledMethodExecution(); + String methodSignature = calledMethodExec.getSignature(); + if (calledMethodExec.isCollectionType() + && (methodSignature.contains("add(") + || methodSignature.contains("set(") + || methodSignature.contains("put(") + || methodSignature.contains("push(") + || methodSignature.contains("addElement("))) { + // container to component + bottomSrcObjId = calledMethodExec.getThisObjId(); + bottomDstObjId = calledMethodExec.getArguments().get(0).getId(); + } else { + // this to another + bottomSrcObjId = methodInvStatement.getThisObjId(); + bottomDstObjId = calledMethodExec.getReturnValue().getId(); + } + } else { + return; + } + + // Extract the reference access history. + List references = objectCallGraph.getReferences(); + Map> referenceHistory = new HashMap<>(); + int order = 0; + for (Alias a: aliasCollector.getAliasList()) { + int idx = -1; + if (a.getAliasType() == AliasType.FIELD) { + FieldAccess f = (FieldAccess) a.getOccurrencePoint().getStatement(); + idx = references.indexOf(new Reference(f.getContainerObjId(), f.getValueObjId(), f.getContainerClassName(), f.getValueClassName())); + } else if (a.getAliasType() == AliasType.ARRAY_ELEMENT) { + ArrayAccess aa = (ArrayAccess) a.getOccurrencePoint().getStatement(); + idx = references.indexOf(new Reference(aa.getArrayObjectId(), aa.getValueObjectId(), aa.getArrayClassName(), aa.getValueClassName())); + } else if (a.getAliasType() == AliasType.RETURN_VALUE) { + MethodExecution methodExec = a.getMethodExecution(); + if (methodExec.getSignature().contains("List.get(") || + methodExec.getSignature().contains("Map.get(")) { + String srcObjId = methodExec.getThisObjId(); + String dstObjId = methodExec.getReturnValue().getId(); + String srcClassName = methodExec.getThisClassName(); + String dstClassName = methodExec.getReturnValue().getActualType(); + idx = references.indexOf(new Reference(srcObjId, dstObjId, srcClassName, dstClassName)); + } + } else if (a.getAliasType() == AliasType.CONSTRACTOR_INVOCATION) { + MethodInvocation c = (MethodInvocation) a.getOccurrencePoint().getStatement(); + String srcObjId = a.getMethodExecution().getThisObjId(); + String dstObjId = c.getCalledMethodExecution().getThisObjId(); + String srcClassName = a.getMethodExecution().getThisClassName(); + String dstClassName = c.getCalledMethodExecution().getThisClassName(); + idx = references.indexOf(new Reference(srcObjId, dstObjId, srcClassName, dstClassName)); + } else if (a.getAliasType() == AliasType.ARRAY_CREATE) { + ArrayCreate ac = (ArrayCreate) a.getOccurrencePoint().getStatement(); + String srcObjId = a.getMethodExecution().getThisObjId(); + String srcClassName = a.getMethodExecution().getThisClassName(); + idx = references.indexOf(new Reference(srcObjId, ac.getArrayObjectId(), srcClassName, ac.getArrayClassName())); + } + if (idx >= 0) { + Reference r = references.get(idx); + List rHIstory = referenceHistory.get(r); + if (rHIstory == null) { + rHIstory = new ArrayList<>(); + referenceHistory.put(r, rHIstory); + } + rHIstory.add(order); + } + order++; + } + + // Construct the object graph. + Map> preds = new HashMap<>(); + Map> succs = new HashMap<>(); + for (Reference r: references) { + String dstObjId = r.getDstObjectId(); + List pre = preds.get(dstObjId); + if (pre == null) { + pre = new ArrayList(); + preds.put(dstObjId, pre); + } + pre.add(r); + String srcObjId = r.getSrcObjectId(); + List suc = succs.get(srcObjId); + if (suc == null) { + suc = new ArrayList(); + succs.put(srcObjId, suc); + } + suc.add(r); + } + + // Extract the source side and destination side paths. + String topObjId = objectCallGraph.getStartPoints().get(0).getThisObjId(); + List dstSide = new ArrayList<>(); + List dstSideObjects = new ArrayList<>(); + String dstObjId = bottomDstObjId; + dstSideObjects.add(dstObjId); + while (!dstObjId.equals(topObjId)) { + if (preds.get(dstObjId) != null) { + Reference minRef = getFirstReferece(preds.get(dstObjId), referenceHistory, true); + dstSide.add(minRef); + dstObjId = minRef.getSrcObjectId(); + } else { + dstSide.add(null); + dstObjId = topObjId; + } + dstSideObjects.add(dstObjId); + } + + List srcSide = new ArrayList<>(); + List srcSideObjects = new ArrayList<>(); + String srcObjId = bottomSrcObjId; + srcSideObjects.add(srcObjId); + while (!srcObjId.equals(topObjId)) { + if (preds.get(srcObjId) != null) { + Reference maxRef = getFirstReferece(preds.get(srcObjId), referenceHistory, false); + srcSide.add(maxRef); + srcObjId = maxRef.getSrcObjectId(); + } else { + srcSide.add(null); + srcObjId = topObjId; + } + srcSideObjects.add(srcObjId); + } + + // Fix the confluent points. + List> confluPoints = new ArrayList<>(); + boolean bConfluent = false; + int hight = 0; + int width = -1; + int dstHight = 0; + int srcHight = 0; + for (String srcObj: srcSideObjects) { + if (dstSideObjects.contains(srcObj)) { + if (!bConfluent) { + int dstDiff = dstSideObjects.indexOf(srcObj) - dstHight; + int srcDiff = srcSideObjects.indexOf(srcObj) - srcHight; + dstHight += dstDiff; + srcHight += srcDiff; + if (dstDiff > srcDiff) { + hight += dstDiff; + } else { + hight += srcDiff; + } + if (width < 0) width = dstHight; + confluPoints.add(new AbstractMap.SimpleEntry(srcObj, hight)); + bConfluent = true; + } else { + hight++; + } + } else { + bConfluent = false; + } + } + coordinatorPoint.setX(coordinatorPoint.getX() + step * width + padding); + double xCor = coordinatorPoint.getX(); + double yCor = coordinatorPoint.getY(); + Set fixed = new HashSet<>(); + for (Map.Entry confluPoint: confluPoints) { + setVertexCoordinate(objectToVertexMap.get(confluPoint.getKey()), xCor, yCor + (hight - confluPoint.getValue()) * step); + fixed.add(confluPoint.getKey()); + } + + // Fix the bottom objects. + Map.Entry firstConfl = confluPoints.get(0); + dstHight = hight - firstConfl.getValue() + dstSideObjects.indexOf(firstConfl.getKey()); + srcHight = hight - firstConfl.getValue() + srcSideObjects.indexOf(firstConfl.getKey()); + int width2 = srcSideObjects.indexOf(firstConfl.getKey()); + setVertexCoordinate(objectToVertexMap.get(bottomDstObjId), padding, yCor + dstHight * step); + fixed.add(bottomDstObjId); + setVertexCoordinate(objectToVertexMap.get(bottomSrcObjId), xCor + width2 * step, yCor + srcHight * step); + fixed.add(bottomSrcObjId); + + // Fix the destination side, source side and common path. + int srcIndex = 0; + int dstIndex = 0; + double dstDirection = 60; + double srcDirection = 120; + for (Map.Entry confluPoint: confluPoints) { + String conflObj = confluPoint.getKey(); + + // Fix the destination side path. + List path = dstSideObjects.subList(dstIndex, dstSideObjects.indexOf(conflObj) + 1); + if (path.size() > 2) fixPath(path, dstDirection, objectToVertexMap, fixed, true); + dstDirection = 120; + dstIndex = dstSideObjects.indexOf(conflObj); + + // Fix the source side path. + path = srcSideObjects.subList(srcIndex, srcSideObjects.indexOf(conflObj) + 1); + if (path.size() > 2) fixPath(path, srcDirection, objectToVertexMap, fixed, true); + srcDirection = 60; + srcIndex = srcSideObjects.indexOf(conflObj); + + // Fix the common path. + int commonHight = confluPoint.getValue(); + for (;;) { + commonHight++; + srcIndex++; + dstIndex++; + if (srcIndex >= srcSideObjects.size() || dstIndex >= dstSideObjects.size()) break; + if (!srcSideObjects.get(srcIndex).equals(dstSideObjects.get(dstIndex))) break; + String commonObjId = srcSideObjects.get(srcIndex); + setVertexCoordinate(objectToVertexMap.get(commonObjId), xCor, yCor + (hight - commonHight) * step); + fixed.add(commonObjId); + } + srcIndex--; + dstIndex--; + } + + // Fix the branches from the destination side path. + for (Reference ref: dstSide) { + if (ref != null) { + List nextRefs = new ArrayList<>(preds.get(ref.getDstObjectId())); + nextRefs = new ArrayList<>(nextRefs); + nextRefs.remove(ref); + double direction = getDirection(ref, objectToVertexMap) - angleStep; + while (nextRefs.size() > 0) { + Reference firstRef = getFirstReferece(nextRefs, referenceHistory, true); + List path = new ArrayList<>(); + path.add(firstRef.getDstObjectId()); + traversePreds(preds, firstRef, direction, true, referenceHistory, objectToVertexMap, fixed, path); + nextRefs.remove(firstRef); + direction = getDirection(firstRef, objectToVertexMap) - angleStep; + } + } + } + + // Fix the branches from the source side path. + for (Reference ref: srcSide) { + if (ref != null) { + List nextRefs = new ArrayList<>(preds.get(ref.getDstObjectId())); + nextRefs = new ArrayList<>(nextRefs); + nextRefs.remove(ref); + double direction = getDirection(ref, objectToVertexMap) + angleStep; + while (nextRefs.size() > 0) { + Reference firstRef = getFirstReferece(nextRefs, referenceHistory, false); + List path = new ArrayList<>(); + path.add(firstRef.getDstObjectId()); + traversePreds(preds, firstRef, direction, false, referenceHistory, objectToVertexMap, fixed, path); + nextRefs.remove(firstRef); + direction = getDirection(firstRef, objectToVertexMap) + angleStep; + } + } + } + + // Fix the reverse branches from the destination side path. + Collections.reverse(dstSide); + for (Reference ref: dstSide) { + if (ref != null) { + List nextRefs = new ArrayList<>(succs.get(ref.getSrcObjectId())); + if (nextRefs.size() > 1) { + nextRefs = new ArrayList<>(nextRefs); + List nextRefs2 = new ArrayList<>(); + do { + Reference firstRef = getFirstReferece(nextRefs, referenceHistory, true); + nextRefs2.add(firstRef); + nextRefs.remove(firstRef); + } while (nextRefs.size() > 1); + nextRefs2.add(nextRefs.remove(0)); + + if (nextRefs2.indexOf(ref) > 0) { + nextRefs = nextRefs2.subList(0, nextRefs2.indexOf(ref)); + double direction = getDirection(ref, objectToVertexMap) + 180 - angleStep; + Collections.reverse(nextRefs); + for (Reference r: nextRefs) { + List path = new ArrayList<>(); + path.add(r.getSrcObjectId()); + traverseSuccs(succs, r, direction, true, referenceHistory, objectToVertexMap, fixed, path); + direction = getDirection(r, objectToVertexMap) + 180 - angleStep; + } + } + + if (nextRefs2.indexOf(ref) < nextRefs2.size() - 1) { + nextRefs = nextRefs2.subList(nextRefs2.indexOf(ref) + 1, nextRefs2.size()); + double direction = getDirection(ref, objectToVertexMap) + 180 + angleStep; + for (Reference r: nextRefs) { + List path = new ArrayList<>(); + path.add(r.getSrcObjectId()); + traverseSuccs(succs, r, direction, true, referenceHistory, objectToVertexMap, fixed, path); + direction = getDirection(r, objectToVertexMap) + 180 + angleStep; + } + } + } +// nextRefs = new ArrayList<>(nextRefs); +// nextRefs.remove(ref); +// double direction = getDirection(ref, objectToVertexMap) + 180 + angleStep; +// while (nextRefs.size() > 0) { +// Reference firstRef = getFirstReferece(nextRefs, referenceHistory, true); +// List path = new ArrayList<>(); +// path.add(firstRef.getSrcObjectId()); +// traverseSuccs(succs, firstRef, direction, true, referenceHistory, objectToVertexMap, fixed, path); +// nextRefs.remove(firstRef); +// direction = getDirection(firstRef, objectToVertexMap) + 180 + angleStep; +// } + } + } + + // Fix the reverse branches from the source side path. + Collections.reverse(srcSide); + for (Reference ref: srcSide) { + if (ref != null) { + List nextRefs = new ArrayList<>(succs.get(ref.getSrcObjectId())); + if (nextRefs.size() > 1) { + nextRefs = new ArrayList<>(nextRefs); + List nextRefs2 = new ArrayList<>(); + do { + Reference firstRef = getFirstReferece(nextRefs, referenceHistory, false); + nextRefs2.add(firstRef); + nextRefs.remove(firstRef); + } while (nextRefs.size() > 1); + nextRefs2.add(nextRefs.remove(0)); + + if (nextRefs2.indexOf(ref) > 0) { + nextRefs = nextRefs2.subList(0, nextRefs2.indexOf(ref)); + double direction = getDirection(ref, objectToVertexMap) + 180 + angleStep; + Collections.reverse(nextRefs); + for (Reference r: nextRefs) { + List path = new ArrayList<>(); + path.add(r.getSrcObjectId()); + traverseSuccs(succs, r, direction, false, referenceHistory, objectToVertexMap, fixed, path); + direction = getDirection(r, objectToVertexMap) + 180 + angleStep; + } + } + + if (nextRefs2.indexOf(ref) < nextRefs2.size() - 1) { + nextRefs = nextRefs2.subList(nextRefs2.indexOf(ref) + 1, nextRefs2.size()); + double direction = getDirection(ref, objectToVertexMap) + 180 - angleStep; + for (Reference r: nextRefs) { + List path = new ArrayList<>(); + path.add(r.getSrcObjectId()); + traverseSuccs(succs, r, direction, false, referenceHistory, objectToVertexMap, fixed, path); + direction = getDirection(r, objectToVertexMap) + 180 - angleStep; + } + } + } +// List nextRefs = new ArrayList<>(succs.get(ref.getSrcObjectId())); +// nextRefs = new ArrayList<>(nextRefs); +// nextRefs.remove(ref); +// double direction = getDirection(ref, objectToVertexMap) + 180 - angleStep; +// while (nextRefs.size() > 0) { +// Reference firstRef = getFirstReferece(nextRefs, referenceHistory, false); +// List path = new ArrayList<>(); +// path.add(firstRef.getSrcObjectId()); +// traverseSuccs(succs, firstRef, direction, false, referenceHistory, objectToVertexMap, fixed, path); +// nextRefs.remove(firstRef); +// direction = getDirection(firstRef, objectToVertexMap) + 180 - angleStep; +// } + } + } + } + + private double getDirection(Reference ref, Map objToVtx) { + ObjectVertex src = objToVtx.get(ref.getSrcObjectId()); + ObjectVertex dst = objToVtx.get(ref.getDstObjectId()); + return Math.toDegrees(Math.atan2(dst.getY() - src.getY(), src.getX() - dst.getX())); + } + + private Reference getFirstReferece(List refs, Map> referenceHistory, boolean bLeftFirst) { + double first = 0.0; + Reference firstRef = null; + for (Reference ref: refs) { + double avgOrder = 0.0; + if (referenceHistory.get(ref) != null) { + for (int ord: referenceHistory.get(ref)) { + avgOrder += (double) ord; + } + avgOrder /= ((double) referenceHistory.get(ref).size()); + } + if (firstRef == null || (bLeftFirst && avgOrder < first) || (!bLeftFirst && avgOrder > first)) { + firstRef = ref; + first = avgOrder; + } + } + return firstRef; + } + + private void traversePreds(Map> preds, Reference ref, double direction, boolean bLeftFirst, Map> referenceHistory, Map objToVtx, Set fixed, List path) { + String curObj = ref.getSrcObjectId(); + path.add(curObj); + if (fixed.contains(curObj)) { + if (path.size() > 2) fixPath(path, direction, objToVtx, fixed, true); + return; + } + List nextRefs = preds.get(curObj); + if (nextRefs == null || nextRefs.size() == 0) { + if (path.size() >= 2) fixPath(path, direction, objToVtx, fixed, false); + return; + } + nextRefs = new ArrayList<>(nextRefs); + do { + Reference firstRef = getFirstReferece(nextRefs, referenceHistory, bLeftFirst); + traversePreds(preds, firstRef, direction, bLeftFirst, referenceHistory, objToVtx, fixed, path); + path = new ArrayList<>(); + path.add(curObj); + nextRefs.remove(firstRef); + direction = getDirection(firstRef, objToVtx); + if (bLeftFirst) { + direction -= angleStep; + } else { + direction += angleStep; + } + } while (nextRefs.size() > 0); + return; + } + + + private void traverseSuccs(Map> succs, Reference ref, double direction, boolean bLeftFirst, Map> referenceHistory, Map objToVtx, Set fixed, List path) { + String curObj = ref.getDstObjectId(); + path.add(curObj); + if (fixed.contains(curObj)) { + if (path.size() > 2) fixPath(path, direction, objToVtx, fixed, true); + return; + } + List nextRefs = succs.get(curObj); + if (nextRefs == null || nextRefs.size() == 0) { + if (path.size() >= 2) fixPath(path, direction, objToVtx, fixed, false); + return; + } + nextRefs = new ArrayList<>(nextRefs); + do { + Reference firstRef = getFirstReferece(nextRefs, referenceHistory, bLeftFirst); + traverseSuccs(succs, firstRef, direction, bLeftFirst, referenceHistory, objToVtx, fixed, path); + path = new ArrayList<>(); + path.add(curObj); + nextRefs.remove(firstRef); + direction = getDirection(firstRef, objToVtx) + 180; + if (bLeftFirst) { + direction += angleStep; + } else { + direction -= angleStep; + } + } while (nextRefs.size() > 0); + return; + } + + private void fixPath(List path, double direction, Map objToVtx, Set fixed, boolean bClose) { + if (path.size() < 2) return; + ObjectVertex start = objToVtx.get(path.get(0)); + double x = start.getX(); + double y = start.getY(); + double dirY = -Math.sin(Math.toRadians(direction)); + double dirX = Math.cos(Math.toRadians(direction)); + if (!bClose) { + // straight line + for (int i = 1; i < path.size(); i++) { + x += step * dirX; + y += step * dirY; + setVertexCoordinate(objToVtx.get(path.get(i)), x, y); + fixed.add(path.get(i)); + } + } else { + ObjectVertex end = objToVtx.get(path.get(path.size() - 1)); + double diffX = end.getX() - start.getX(); + double diffY = end.getY() - start.getY(); + double distance = Math.sqrt(diffX * diffX + diffY * diffY); + diffX /= distance; + diffY /= distance; + double outer = dirX * diffY - dirY * diffX; + double centerX, centerY, vecX, vecY; + double theta = Math.acos(diffX * dirX + diffY * dirY); + double radius = distance / 2 / Math.sin(theta); + if (outer > 0) { + vecX = -dirY; + vecY = dirX; + theta = theta * 2.0 / (double) (path.size() - 1); + } else if (outer < 0) { + vecX = dirY; + vecY = -dirX; + theta = -theta * 2.0 / (double) (path.size() - 1); + } else { + // straight line + diffX *= distance / (double) (path.size() - 1); + diffY *= distance / (double) (path.size() - 1); + for (int i = 1; i < path.size(); i++) { + x += diffX; + y += diffY; + setVertexCoordinate(objToVtx.get(path.get(i)), x, y); + fixed.add(path.get(i)); + } + return; + } + // arc + centerX = x + radius * vecX; + centerY = y + radius * vecY; + for (int i = 1; i < path.size() - 1; i++) { + double tmp = vecX * Math.cos(theta) - vecY * Math.sin(theta); + vecY = vecX * Math.sin(theta) + vecY * Math.cos(theta); + vecX = tmp; + setVertexCoordinate(objToVtx.get(path.get(i)), centerX - radius * vecX, centerY - radius * vecY); + fixed.add(path.get(i)); + } + } + } + + private void setVertexCoordinate(ObjectVertex vertex, double x, double y) { + vertex.setX(x); + vertex.setY(y); + vertex.setInitialPoint(x, y); + } +}