Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java =================================================================== --- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java (revision 1953) +++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java (revision 1954) @@ -27,8 +27,10 @@ import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship; -import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; -import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; @@ -344,14 +346,11 @@ public List getPathsToIgnore() { List result = new LinkedList(); - Delta singleChangeDelta = null; if ((patch.getDeltas().size() == 1) && (patch.getDeltas().get(0).getType() == Delta.TYPE.CHANGE)) { - singleChangeDelta = patch.getDeltas().get(0); - } - - // if it is a full change, then the parent of either side must be fully ignored - if (singleChangeDelta != null) { + // if it is a full change, then the parent of either side must be fully ignored + Delta singleChangeDelta = patch.getDeltas().get(0); + if ((singleChangeDelta.getOriginal().getPosition() == 0) && (singleChangeDelta.getOriginal().size() == leftHandSideTraversal.size())) @@ -372,20 +371,19 @@ if (result.size() < 2) { - // if we do not already ignore both root tasks, check for selections and interleaving - // iterations that have to be ignored if they belong to a delta + // if we do not already ignore both root tasks, check for overlapping + // iterations that are executed multiple times for the tasks to be merged as they have + // to be ignored + result.addAll(getConflictingIterations()); + + // then check for tasks fully inside delta, which can be preserved for (Delta delta : patch.getDeltas()) { - //getSelections(delta, result); - getPathsToRealIntersectingIterations(delta, result); getNotFullyInterleavingIteration(delta, result); getPathsToParentTasksFullyInsideDelta(delta, result); } - // check for any parent optional that may be empty and can hence not be flattened - TaskPath tmppath = new TaskPath(); - tmppath.add(leftHandSide, 0); - getParentOptionals(tmppath, result); - tmppath = new TaskPath(); - tmppath.add(rightHandSide, 0); - getParentOptionals(tmppath, result); + // check for any parent optional that are at least once empty in instances of the + // tasks to be merged and that can, hence, not be flattened + getUnexecutedParentOptionals(leftHandSide, result); + getUnexecutedParentOptionals(rightHandSide, result); // check if there are common subtasks on both sides that lie outside any delta and @@ -839,64 +837,159 @@ } }*/ - - /** - * - */ - @SuppressWarnings("unchecked") - private void getPathsToRealIntersectingIterations(Delta delta, List paths) { - TaskPath path1 = getCommonPath((List) delta.getOriginal().getLines()); - TaskPath path2 = getCommonPath((List) delta.getRevised().getLines()); - - // both paths denote those parent tasks that contain the delta. - // But there may be parent tasks still contained in the path that are iterations and - // that are disjoint with a parent in the other path. Those iterations need to be - // considered, as otherwise a created selection would be against the associative law of - // iterations. Hence, we search for the topmost iteration on both paths that is disjoint - // with a parent node in the respective other path. - - for (int i = 0; i < path1.size(); i++) { - TaskPath path1Prefix = path1.subPath(0, i + 1); - int[] idxsPath1 = leftHandSideTraversal.getIndexesRootedBy(path1Prefix); - - // normalize the indexes to be 0 the index of the delta. Everything left of it - // is smaller 0, everything right of it, larger. - idxsPath1[0] -= delta.getOriginal().getPosition(); - idxsPath1[1] -= delta.getOriginal().getPosition() + delta.getOriginal().size() - 1; - - for (int j = 0; j < path2.size(); j++) { - TaskPath path2Prefix = path2.subPath(0, j + 1); - int[] idxsPath2 = rightHandSideTraversal.getIndexesRootedBy(path2Prefix); - - // normalize the indexes to be 0 the index of the delta. Everything left of it - // is smaller 0, everything right of it, larger. - idxsPath2[0] -= delta.getRevised().getPosition(); - idxsPath2[1] -= - delta.getRevised().getPosition() + delta.getRevised().size() - 1; - - // now compare the indexes and check, if the sublists are real subsets of each - // other. If not, they only have a real common subset but there is at least one - // non shared element on both sides. If so, and one is an iteration, we - // have to use it as elements to be selected - if (((idxsPath1[0] < idxsPath2[0]) && (idxsPath1[1] < idxsPath2[1])) || - ((idxsPath1[0] > idxsPath2[0]) && (idxsPath1[1] > idxsPath2[1]))) - { - if ((path1.get(i).getTask() instanceof IIteration) && - (path2.get(j).getTask() instanceof IIteration)) - { - // System.out.println("found paths to real intersecting parents"); - // int[] indexBuf = leftHandSideTraversal.getIndexesRootedBy(path1Prefix); - // System.out.println(idxsPath1[0] + "(" + indexBuf[0] + ") " + idxsPath1[1] + - // "(" + indexBuf[1] + ") " + path1Prefix); - // indexBuf = rightHandSideTraversal.getIndexesRootedBy(path2Prefix); - // System.out.println(idxsPath2[0] + "(" + indexBuf[0] + ") " + idxsPath2[1] + - // "(" + indexBuf[1] + ") " + path2Prefix); + + /** + * conflicting iterations are those that belong to either side of the sequence pair, that cover + * at least two actions, and that were executed multiple times in the context of the tasks + * to be merged. Iterations do only conflict, if there are at least two, one belonging to the + * left hand side, and the other to the right hand side. They conflict only, if they cover the + * same terminal nodes in the task traversals. + */ + private List getConflictingIterations() { + List iterationsWithMultipleExecutions = new LinkedList<>(); + getIterationsWithMultipleExecutions(leftHandSide, iterationsWithMultipleExecutions); + + if (iterationsWithMultipleExecutions.size() > 0) { + // only, if iterations are executed in both side, they are of interest. Hence, + // check right hand side only, if left hand side contains repeated iterations. + int noOfLeftHandSideRepeatedIterations = iterationsWithMultipleExecutions.size(); + getIterationsWithMultipleExecutions(rightHandSide, iterationsWithMultipleExecutions); + + if (iterationsWithMultipleExecutions.size() > noOfLeftHandSideRepeatedIterations) { + // also the right hand side contains problematic iterations. Check if they are + // overlapping and drop all which are not. + dropNonOverlappingIterations(iterationsWithMultipleExecutions); + } + else { + // no conflict, clear the list + iterationsWithMultipleExecutions.clear(); + } + } + + return iterationsWithMultipleExecutions; + } + + /** + * + */ + private void getIterationsWithMultipleExecutions(ITask task, + List result) + { + for (ITaskInstance instance : task.getInstances()) { + TaskPath taskPath = new TaskPath(); + taskPath.add(task, 0); + getIterationsWithMultipleExecutions(instance, taskPath, result); + } + } + + /** + * + */ + private void getIterationsWithMultipleExecutions(ITaskInstance instance, + TaskPath currentPath, + List result) + { + if (instance instanceof IIterationInstance) { + if (((IIterationInstance) instance).size() > 1) { + // iteration executed multiple times --> store path + result.add(currentPath.subPath(0, currentPath.size())); // ensure to create a copy + } + + currentPath.add(((IIteration) instance.getTask()).getMarkedTask(), 0); + + for (ITaskInstance child : (IIterationInstance) instance) { + getIterationsWithMultipleExecutions(child, currentPath, result); + } + + currentPath.removeLast(); + } + else if (instance instanceof ISequenceInstance) { + int index = 0; + for (ITaskInstance child : (ISequenceInstance) instance) { + currentPath.add(child.getTask(), index++); + getIterationsWithMultipleExecutions(child, currentPath, result); + currentPath.removeLast(); + } + } + else if (instance instanceof ISelectionInstance) { + ITaskInstance child = ((ISelectionInstance) instance).getChild(); + currentPath.add(child.getTask(), 0); + getIterationsWithMultipleExecutions(child, currentPath, result); + currentPath.removeLast(); + } + else if (instance instanceof IOptionalInstance) { + ITaskInstance child = ((IOptionalInstance) instance).getChild(); + if (child != null) { + currentPath.add(child.getTask(), 0); + getIterationsWithMultipleExecutions(child, currentPath, result); + currentPath.removeLast(); + } + } + } + + /** + * + */ + private void dropNonOverlappingIterations(List iterationsWithMultipleExecutions) { + // to check overlappings, iterate the iterations. Then check for each the indexes it covers + // in its respective traversal. Adapt the indexes depending on deltas that an iteration + // covers. Then check all other iterations. Consider also here the indexes in the traversal. + // also here, the indexes must be adapted in case of covered deltas. + List overlappingIterations = new LinkedList(); + + for (TaskPath leftPath : iterationsWithMultipleExecutions) { + if (leftPath.getTask(0).equals(leftHandSide)) { + int[] leftIdxs = leftHandSideTraversal.getIndexesRootedBy(leftPath); + + for (TaskPath rightPath : iterationsWithMultipleExecutions) { + if (rightPath.getTask(0).equals(rightHandSide)) { + int[] rightIdxs = rightHandSideTraversal.getIndexesRootedBy(rightPath); - paths.add(path1Prefix); - paths.add(path2Prefix); - return; - } - } - } - } + adaptIndexesBasedOnDeltas(leftIdxs, rightIdxs, patch.getDeltas()); + + if (((leftIdxs[0] < rightIdxs[0]) && (rightIdxs[0] <= leftIdxs[1])) || + ((rightIdxs[0] < leftIdxs[0]) && (leftIdxs[0] <= rightIdxs[1]))) + { + overlappingIterations.add(leftPath); + overlappingIterations.add(rightPath); + } + } + } + } + } + + iterationsWithMultipleExecutions.retainAll(overlappingIterations); + } + + /** + * + */ + private void adaptIndexesBasedOnDeltas(int[] originalIndexes, + int[] revisedIndexes, + List deltas) + { + int originalStartUpdate = 0; + int originalEndUpdate = 0; + int revisedStartUpdate = 0; + int revisedEndUpdate = 0; + + for (Delta delta : deltas) { + if (delta.getOriginal().getPosition() < originalIndexes[0]) { + originalStartUpdate += delta.getRevised().size(); + } + if (delta.getOriginal().getPosition() < originalIndexes[1]) { + originalEndUpdate += delta.getRevised().size(); + } + if (delta.getRevised().getPosition() < revisedIndexes[0]) { + revisedStartUpdate += delta.getOriginal().size(); + } + if (delta.getRevised().getPosition() < revisedIndexes[1]) { + revisedEndUpdate += delta.getOriginal().size(); + } + } + + originalIndexes[0] += originalStartUpdate; + originalIndexes[1] += originalEndUpdate; + revisedIndexes[0] += revisedStartUpdate; + revisedIndexes[1] += revisedEndUpdate; } @@ -939,6 +1032,6 @@ /** * If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration - * the does not cover the other and also expands to preceding or succeeding paths in the - * traversal, we can no merge the situation. + * that does not cover the other and also expands to preceding or succeeding paths in the + * traversal, we can not merge the situation. */ private void getNotFullyInterleavingIterations(Chunk chunk, @@ -1031,28 +1124,54 @@ * */ - private void getParentOptionals(TaskPath taskPath, List result) { - ITask task = taskPath.getLast(); - - if (task instanceof IOptional) { - result.add(new TaskPath(taskPath)); - } - else if (task instanceof ISequence) { - for (int i = 0; i < ((ISequence) task).getChildren().size(); i++) { - taskPath.add(((ISequence) task).getChildren().get(i), i); - getParentOptionals(taskPath, result); - taskPath.removeLast(); - } - } - else if (task instanceof ISelection) { - for (int i = 0; i < ((ISelection) task).getChildren().size(); i++) { - taskPath.add(((ISelection) task).getChildren().get(i), 0); - getParentOptionals(taskPath, result); - taskPath.removeLast(); - } - } - else if (task instanceof IIteration) { - taskPath.add(((IIteration) task).getMarkedTask(), 0); - getParentOptionals(taskPath, result); - taskPath.removeLast(); + private void getUnexecutedParentOptionals(ITask task, + List result) + { + for (ITaskInstance instance : task.getInstances()) { + TaskPath taskPath = new TaskPath(); + taskPath.add(task, 0); + getUnexecutedParentOptionals(instance, taskPath, result); + } + } + + /** + * + */ + private void getUnexecutedParentOptionals(ITaskInstance instance, + TaskPath currentPath, + List result) + { + if (instance instanceof IOptionalInstance) { + ITaskInstance child = ((IOptionalInstance) instance).getChild(); + if (child != null) { + currentPath.add(child.getTask(), 0); + getUnexecutedParentOptionals(child, currentPath, result); + currentPath.removeLast(); + } + else { + result.add(currentPath.subPath(0, currentPath.size())); // ensure to create a copy + } + } + else if (instance instanceof IIterationInstance) { + currentPath.add(((IIteration) instance.getTask()).getMarkedTask(), 0); + + for (ITaskInstance child : (IIterationInstance) instance) { + getUnexecutedParentOptionals(child, currentPath, result); + } + + currentPath.removeLast(); + } + else if (instance instanceof ISequenceInstance) { + int index = 0; + for (ITaskInstance child : (ISequenceInstance) instance) { + currentPath.add(child.getTask(), index++); + getUnexecutedParentOptionals(child, currentPath, result); + currentPath.removeLast(); + } + } + else if (instance instanceof ISelectionInstance) { + ITaskInstance child = ((ISelectionInstance) instance).getChild(); + currentPath.add(child.getTask(), 0); + getUnexecutedParentOptionals(child, currentPath, result); + currentPath.removeLast(); } }