[1767] | 1 | // Copyright 2012 Georg-August-Universität Göttingen, Germany |
---|
| 2 | // |
---|
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
---|
| 4 | // you may not use this file except in compliance with the License. |
---|
| 5 | // You may obtain a copy of the License at |
---|
| 6 | // |
---|
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 |
---|
| 8 | // |
---|
| 9 | // Unless required by applicable law or agreed to in writing, software |
---|
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, |
---|
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
---|
| 12 | // See the License for the specific language governing permissions and |
---|
| 13 | // limitations under the License. |
---|
| 14 | |
---|
| 15 | package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils; |
---|
| 16 | |
---|
| 17 | import java.io.PrintStream; |
---|
| 18 | import java.util.HashSet; |
---|
| 19 | import java.util.LinkedList; |
---|
| 20 | import java.util.List; |
---|
| 21 | import java.util.Set; |
---|
| 22 | |
---|
| 23 | import de.ugoe.cs.autoquest.eventcore.gui.Scroll; |
---|
[1850] | 24 | import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator; |
---|
[1767] | 25 | import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor; |
---|
| 26 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask; |
---|
| 27 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance; |
---|
| 28 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; |
---|
[1954] | 29 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance; |
---|
[1767] | 30 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship; |
---|
[1954] | 31 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance; |
---|
[1767] | 32 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; |
---|
[1954] | 33 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance; |
---|
| 34 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance; |
---|
[1767] | 35 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; |
---|
| 36 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; |
---|
| 37 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance; |
---|
| 38 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITemporalRelationship; |
---|
| 39 | import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskPath; |
---|
| 40 | import difflib.Chunk; |
---|
| 41 | import difflib.Delta; |
---|
| 42 | import difflib.Patch; |
---|
| 43 | |
---|
| 44 | /** |
---|
| 45 | * <p> |
---|
| 46 | * This class represents a pair of tasks and their corresponding similarity level, respectively, |
---|
| 47 | * their diff level. In addition, it contains the task traversal, i.e., the flattened variants |
---|
| 48 | * of the compared tasks. It provides static methods to compare two tasks and get an object of this |
---|
| 49 | * class as result. Furthermore, it allows to adapt the contained traversals so that unmergable |
---|
| 50 | * subtasks are not traversed. |
---|
| 51 | * </p> |
---|
| 52 | * |
---|
| 53 | * @author Patrick Harms |
---|
| 54 | */ |
---|
| 55 | public class SimilarTasks { |
---|
| 56 | |
---|
| 57 | /** |
---|
[1850] | 58 | * default indicator for unequal tasks |
---|
| 59 | */ |
---|
| 60 | public static final SimilarTasks UNEQUAL_TASKS = new SimilarTasks(null, null, null); |
---|
| 61 | |
---|
| 62 | /** |
---|
[1767] | 63 | * result of the string like comparison of both task traversals |
---|
| 64 | */ |
---|
| 65 | private Patch patch; |
---|
| 66 | |
---|
| 67 | /** |
---|
| 68 | * the diff level resulting from the comparison |
---|
| 69 | */ |
---|
| 70 | private int diffLevel; |
---|
| 71 | |
---|
| 72 | /** |
---|
| 73 | * the first compared task |
---|
| 74 | */ |
---|
| 75 | private ITask leftHandSide; |
---|
| 76 | |
---|
| 77 | /** |
---|
| 78 | * the second compare task |
---|
| 79 | */ |
---|
| 80 | private ITask rightHandSide; |
---|
| 81 | |
---|
| 82 | /** |
---|
| 83 | * the traversal of the first task |
---|
| 84 | */ |
---|
| 85 | private TaskTraversal leftHandSideTraversal; |
---|
| 86 | |
---|
| 87 | /** |
---|
| 88 | * the traversal of the second task |
---|
| 89 | */ |
---|
| 90 | private TaskTraversal rightHandSideTraversal; |
---|
| 91 | |
---|
| 92 | /** |
---|
| 93 | * initialized a pair of tasks and calculates its diff level |
---|
| 94 | */ |
---|
| 95 | public SimilarTasks(Patch patch, |
---|
| 96 | TaskTraversal traversal1, |
---|
| 97 | TaskTraversal traversal2) |
---|
| 98 | { |
---|
[1850] | 99 | if (traversal1 != null) { |
---|
| 100 | this.leftHandSide = traversal1.getTask(); |
---|
| 101 | } |
---|
| 102 | |
---|
[1767] | 103 | this.leftHandSideTraversal = traversal1; |
---|
[1850] | 104 | |
---|
| 105 | if (traversal2 != null) { |
---|
| 106 | this.rightHandSide = traversal2.getTask(); |
---|
| 107 | } |
---|
| 108 | |
---|
[1767] | 109 | this.rightHandSideTraversal = traversal2; |
---|
| 110 | |
---|
| 111 | if (patch != null) { |
---|
| 112 | this.patch = patch; |
---|
| 113 | this.diffLevel = getDiffLevel(patch, traversal1, traversal2); |
---|
| 114 | } |
---|
| 115 | else { |
---|
| 116 | this.diffLevel = 100; |
---|
| 117 | } |
---|
| 118 | } |
---|
| 119 | |
---|
| 120 | /** |
---|
| 121 | * static convenience method to compare two tasks |
---|
| 122 | */ |
---|
[1850] | 123 | public static SimilarTasks compareTasks(ITask task1, |
---|
| 124 | ITask task2, |
---|
| 125 | TaskComparator comparator) |
---|
[1767] | 126 | { |
---|
[1850] | 127 | return compareTasks(task1, task2, comparator, null); |
---|
[1767] | 128 | } |
---|
| 129 | |
---|
| 130 | /** |
---|
| 131 | * static convenience method to compare two tasks but ignoring a given set of subtasks when |
---|
[1850] | 132 | * creating the traversals. |
---|
[1767] | 133 | */ |
---|
[1850] | 134 | public static SimilarTasks compareTasks(ITask task1, |
---|
| 135 | ITask task2, |
---|
| 136 | TaskComparator comparator, |
---|
| 137 | List<TaskPath> pathsNotToTraverse) |
---|
[1767] | 138 | { |
---|
[1850] | 139 | TaskTraversal traversal1 = TaskTraversal.getTraversal(task1, pathsNotToTraverse); |
---|
| 140 | TaskTraversal traversal2 = TaskTraversal.getTraversal(task2, pathsNotToTraverse); |
---|
[1767] | 141 | |
---|
| 142 | if ((traversal1.size() <= 0) || (traversal2.size() <= 0)) { |
---|
| 143 | return null; |
---|
| 144 | } |
---|
[1850] | 145 | |
---|
| 146 | return compareTraversals(traversal1, traversal2, comparator); |
---|
| 147 | } |
---|
[1767] | 148 | |
---|
[1850] | 149 | /** |
---|
| 150 | * <p> |
---|
[2258] | 151 | * static convenience method to compare two task traversals using a given comparator to compare |
---|
| 152 | * the individual tasks in the traversals. |
---|
[1850] | 153 | * </p> |
---|
| 154 | */ |
---|
| 155 | public static SimilarTasks compareTraversals(TaskTraversal traversal1, |
---|
| 156 | TaskTraversal traversal2, |
---|
| 157 | TaskComparator comparator) |
---|
| 158 | { |
---|
[1767] | 159 | Patch patch = new TaskTraversalMyersDiff(comparator).getDiff(traversal1, traversal2); |
---|
| 160 | |
---|
[1850] | 161 | SimilarTasks result = new SimilarTasks(patch, traversal1, traversal2); |
---|
[1767] | 162 | |
---|
| 163 | return result; |
---|
| 164 | } |
---|
| 165 | |
---|
| 166 | |
---|
| 167 | /** |
---|
| 168 | * This method checks for mergability of the provided similar tasks and if this is not given, |
---|
| 169 | * it reduces the traversals by ignoring interleaving iterations and other situations until |
---|
| 170 | * the remaining traversals can be the basis of a merge. |
---|
| 171 | */ |
---|
[1850] | 172 | public static SimilarTasks getMergableLevelOfSimilarity(SimilarTasks source, |
---|
| 173 | TaskComparator comparator) |
---|
[1767] | 174 | { |
---|
| 175 | SimilarTasks similarTasks = source; |
---|
| 176 | |
---|
| 177 | List<TaskPath> pathsToIgnore = similarTasks.getPathsToIgnore(); |
---|
| 178 | |
---|
| 179 | int prevPathsToIgnoreCount = 0; |
---|
| 180 | |
---|
| 181 | do { |
---|
| 182 | prevPathsToIgnoreCount = pathsToIgnore.size(); |
---|
| 183 | |
---|
| 184 | similarTasks = compareTasks |
---|
| 185 | (similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(), |
---|
[1850] | 186 | comparator, pathsToIgnore); |
---|
[1767] | 187 | |
---|
[1850] | 188 | // similarTasks.dump(System.out); |
---|
[1767] | 189 | |
---|
| 190 | List<TaskPath> furtherPathsToIgnore = similarTasks.getPathsToIgnore(); |
---|
| 191 | |
---|
[1850] | 192 | // System.out.println("further paths to ignore:"); |
---|
| 193 | // for (TaskPath path : furtherPathsToIgnore) { |
---|
| 194 | // System.out.println(" " + path); |
---|
| 195 | // } |
---|
[1767] | 196 | |
---|
| 197 | for (TaskPath pathToAdd : furtherPathsToIgnore) { |
---|
| 198 | boolean found = false; |
---|
| 199 | for (TaskPath pathToIgnore : pathsToIgnore) { |
---|
| 200 | if (pathToAdd.equals(pathToIgnore)) { |
---|
| 201 | found = true; |
---|
| 202 | break; |
---|
| 203 | } |
---|
| 204 | } |
---|
| 205 | |
---|
| 206 | if (!found) { |
---|
| 207 | pathsToIgnore.add(pathToAdd); |
---|
| 208 | } |
---|
| 209 | } |
---|
| 210 | } |
---|
| 211 | while (pathsToIgnore.size() > prevPathsToIgnoreCount); |
---|
| 212 | |
---|
[1850] | 213 | if (similarTasks.isStillWellAligned()) { |
---|
| 214 | return similarTasks; |
---|
| 215 | } |
---|
| 216 | else { |
---|
| 217 | // this may happen, if due to interleaving iterations the similarities of the task |
---|
| 218 | // move and the diff algorithm does not align them anymore as optimal as possible |
---|
| 219 | // because some similarities were lost due to not comparing all paths anymore. |
---|
| 220 | return null; |
---|
| 221 | } |
---|
[1767] | 222 | } |
---|
| 223 | |
---|
| 224 | /** |
---|
| 225 | * checks if the delta between the two traversals is at their border or not |
---|
| 226 | */ |
---|
| 227 | public boolean isInBetweenDifference() { |
---|
| 228 | List<Delta> deltas = patch.getDeltas(); |
---|
| 229 | |
---|
| 230 | for (Delta delta : deltas) { |
---|
| 231 | int origPos = delta.getOriginal().getPosition(); |
---|
| 232 | int origSize = delta.getOriginal().size(); |
---|
| 233 | int revPos = delta.getRevised().getPosition(); |
---|
| 234 | int revSize = delta.getRevised().size(); |
---|
| 235 | |
---|
| 236 | if ((origPos <= 0) || (revPos <= 0)) { |
---|
| 237 | // optional must not be the beginning of the task |
---|
| 238 | return false; |
---|
| 239 | } |
---|
| 240 | else if ((delta.getType() == Delta.TYPE.INSERT) && |
---|
| 241 | ((revPos + revSize) >= rightHandSideTraversal.size())) |
---|
| 242 | { |
---|
| 243 | // optional must not be the end of the right hand side task |
---|
| 244 | return false; |
---|
| 245 | } |
---|
| 246 | else if ((delta.getType() == Delta.TYPE.DELETE) && |
---|
| 247 | ((origPos + origSize) >= leftHandSideTraversal.size())) |
---|
| 248 | { |
---|
| 249 | // optional must not be the end of the left hand side task |
---|
| 250 | return false; |
---|
| 251 | } |
---|
| 252 | else if ((delta.getType() == Delta.TYPE.CHANGE) && |
---|
| 253 | (((revPos + revSize) >= rightHandSideTraversal.size()) || |
---|
| 254 | ((origPos + origSize) >= leftHandSideTraversal.size()))) |
---|
| 255 | { |
---|
| 256 | // selection must not be the end of the left hand or right hand side task |
---|
| 257 | return false; |
---|
| 258 | } |
---|
| 259 | } |
---|
| 260 | |
---|
| 261 | return deltas.size() > 0; |
---|
| 262 | } |
---|
[1850] | 263 | |
---|
| 264 | /** |
---|
| 265 | * <p> |
---|
[2258] | 266 | * returns true, if the differences between the traversals are between the beginning and the |
---|
| 267 | * end of both traversals. |
---|
[1850] | 268 | * </p> |
---|
| 269 | * |
---|
| 270 | * @return |
---|
| 271 | */ |
---|
| 272 | public boolean isStillWellAligned() { |
---|
| 273 | if (isInBetweenDifference()) { |
---|
| 274 | return true; |
---|
| 275 | } |
---|
| 276 | else { |
---|
| 277 | for (Delta delta : patch.getDeltas()) { |
---|
| 278 | if (delta.getType() == Delta.TYPE.INSERT) { |
---|
| 279 | if ((delta.getOriginal().getPosition() == 0) || |
---|
| 280 | (delta.getOriginal().getPosition() == leftHandSideTraversal.size())) |
---|
| 281 | { |
---|
| 282 | return false; |
---|
| 283 | } |
---|
| 284 | } |
---|
| 285 | else if (delta.getType() == Delta.TYPE.DELETE) { |
---|
| 286 | if ((delta.getRevised().getPosition() == 0) || |
---|
| 287 | (delta.getRevised().getPosition() == rightHandSideTraversal.size())) |
---|
| 288 | { |
---|
| 289 | return false; |
---|
| 290 | } |
---|
| 291 | } |
---|
| 292 | } |
---|
| 293 | } |
---|
| 294 | |
---|
| 295 | return true; |
---|
| 296 | } |
---|
[1767] | 297 | |
---|
| 298 | /** |
---|
| 299 | * @return the patch |
---|
| 300 | */ |
---|
| 301 | public Patch getPatch() { |
---|
| 302 | return patch; |
---|
| 303 | } |
---|
| 304 | |
---|
| 305 | /** |
---|
| 306 | * @return the diff level |
---|
| 307 | */ |
---|
| 308 | public int getDiffLevel() { |
---|
| 309 | return diffLevel; |
---|
| 310 | } |
---|
| 311 | |
---|
| 312 | /** |
---|
| 313 | * @return the first task of the comparison |
---|
| 314 | */ |
---|
| 315 | public ITask getLeftHandSide() { |
---|
| 316 | return leftHandSide; |
---|
| 317 | } |
---|
| 318 | |
---|
| 319 | /** |
---|
| 320 | * @return the second task of the comparison |
---|
| 321 | */ |
---|
| 322 | public ITask getRightHandSide() { |
---|
| 323 | return rightHandSide; |
---|
| 324 | } |
---|
| 325 | |
---|
| 326 | /** |
---|
| 327 | * @return the traversal of the first task of the comparison |
---|
| 328 | */ |
---|
| 329 | public TaskTraversal getLeftHandSideTraversal() { |
---|
| 330 | return leftHandSideTraversal; |
---|
| 331 | } |
---|
| 332 | |
---|
| 333 | /** |
---|
| 334 | * @return the traversal of the second task of the comparison |
---|
| 335 | */ |
---|
| 336 | public TaskTraversal getRightHandSideTraversal() { |
---|
| 337 | return rightHandSideTraversal; |
---|
| 338 | } |
---|
| 339 | |
---|
| 340 | /** |
---|
| 341 | * returns paths to subtasks, that can not be merged. |
---|
| 342 | */ |
---|
| 343 | public List<TaskPath> getPathsToIgnore() { |
---|
| 344 | List<TaskPath> result = new LinkedList<TaskPath>(); |
---|
| 345 | |
---|
| 346 | if ((patch.getDeltas().size() == 1) && |
---|
| 347 | (patch.getDeltas().get(0).getType() == Delta.TYPE.CHANGE)) |
---|
| 348 | { |
---|
[1954] | 349 | // if it is a full change, then the parent of either side must be fully ignored |
---|
| 350 | Delta singleChangeDelta = patch.getDeltas().get(0); |
---|
| 351 | |
---|
[1767] | 352 | if ((singleChangeDelta.getOriginal().getPosition() == 0) && |
---|
| 353 | (singleChangeDelta.getOriginal().size() == leftHandSideTraversal.size())) |
---|
| 354 | { |
---|
| 355 | TaskPath path = new TaskPath(); |
---|
| 356 | path.add(leftHandSide, 0); |
---|
| 357 | result.add(path); |
---|
| 358 | } |
---|
| 359 | |
---|
| 360 | if ((singleChangeDelta.getRevised().getPosition() == 0) && |
---|
| 361 | (singleChangeDelta.getRevised().size() == rightHandSideTraversal.size())) |
---|
| 362 | { |
---|
| 363 | TaskPath path = new TaskPath(); |
---|
| 364 | path.add(rightHandSide, 0); |
---|
| 365 | result.add(path); |
---|
| 366 | } |
---|
| 367 | } |
---|
| 368 | |
---|
| 369 | if (result.size() < 2) { |
---|
[1954] | 370 | // if we do not already ignore both root tasks, check for overlapping |
---|
| 371 | // iterations that are executed multiple times for the tasks to be merged as they have |
---|
| 372 | // to be ignored |
---|
| 373 | result.addAll(getConflictingIterations()); |
---|
| 374 | |
---|
| 375 | // then check for tasks fully inside delta, which can be preserved |
---|
[1767] | 376 | for (Delta delta : patch.getDeltas()) { |
---|
| 377 | getNotFullyInterleavingIteration(delta, result); |
---|
| 378 | getPathsToParentTasksFullyInsideDelta(delta, result); |
---|
| 379 | } |
---|
| 380 | |
---|
[1954] | 381 | // check for any parent optional that are at least once empty in instances of the |
---|
| 382 | // tasks to be merged and that can, hence, not be flattened |
---|
| 383 | getUnexecutedParentOptionals(leftHandSide, result); |
---|
| 384 | getUnexecutedParentOptionals(rightHandSide, result); |
---|
[1850] | 385 | |
---|
[1767] | 386 | // check if there are common subtasks on both sides that lie outside any delta and |
---|
| 387 | // that hence should be ignored (especially when performing flattening of task |
---|
[1850] | 388 | // instances later with the goal to preserve as many subtasks and respective instances) |
---|
[1767] | 389 | int deltaIndex = 0; |
---|
| 390 | int leftTraversalIndex = 0; |
---|
| 391 | int rightTraversalIndex = 0; |
---|
| 392 | Set<ITask> commonInvolvedTasks = getCommonInvolvedTasks(leftHandSide, rightHandSide); |
---|
| 393 | |
---|
| 394 | do { |
---|
| 395 | Delta delta = deltaIndex < patch.getDeltas().size() |
---|
| 396 | ? patch.getDeltas().get(deltaIndex++) : null; |
---|
| 397 | |
---|
| 398 | int nextLeftTraversalIndex = leftHandSideTraversal.size(); |
---|
| 399 | int nextRightTraversalIndex = rightHandSideTraversal.size(); |
---|
| 400 | |
---|
| 401 | if (delta != null) { |
---|
| 402 | nextLeftTraversalIndex = delta.getOriginal().getPosition() + 1; |
---|
| 403 | nextRightTraversalIndex = delta.getRevised().getPosition() + 1; |
---|
| 404 | |
---|
| 405 | if (delta.getType() == Delta.TYPE.INSERT) { |
---|
| 406 | nextLeftTraversalIndex--; |
---|
| 407 | } |
---|
| 408 | else if (delta.getType() == Delta.TYPE.DELETE) { |
---|
| 409 | nextRightTraversalIndex--; |
---|
| 410 | } |
---|
| 411 | } |
---|
| 412 | |
---|
| 413 | TaskPath[] leftSubTraversal = |
---|
| 414 | leftHandSideTraversal.subList(leftTraversalIndex, nextLeftTraversalIndex); |
---|
| 415 | |
---|
| 416 | for (TaskPath path : leftSubTraversal) { |
---|
| 417 | for (int i = 0; i < path.size(); i++) { |
---|
| 418 | if (commonInvolvedTasks.contains(path.getTask(i))) { |
---|
| 419 | // found a candidate. Check if the candidate does not span more than |
---|
| 420 | // the sub traversal |
---|
| 421 | TaskPath parentPath = path.subPath(0, i + 1); |
---|
| 422 | int[] indexes = leftHandSideTraversal.getIndexesRootedBy(parentPath); |
---|
| 423 | |
---|
| 424 | if ((indexes[0] >= leftTraversalIndex) && |
---|
| 425 | (indexes[1] < nextLeftTraversalIndex)) |
---|
| 426 | { |
---|
| 427 | result.add(parentPath); |
---|
| 428 | break; // breaks only the path but the rest of the traversal is |
---|
| 429 | // checked too |
---|
| 430 | } |
---|
| 431 | } |
---|
| 432 | } |
---|
| 433 | } |
---|
| 434 | |
---|
| 435 | TaskPath[] rightSubTraversal = |
---|
| 436 | rightHandSideTraversal.subList(rightTraversalIndex, nextRightTraversalIndex); |
---|
| 437 | |
---|
| 438 | for (TaskPath path : rightSubTraversal) { |
---|
| 439 | for (int i = 0; i < path.size(); i++) { |
---|
| 440 | if (commonInvolvedTasks.contains(path.getTask(i))) { |
---|
| 441 | // found a candidate. Check if the candidate does not span more than |
---|
| 442 | // the sub traversal |
---|
| 443 | TaskPath parentPath = path.subPath(0, i + 1); |
---|
| 444 | int[] indexes = rightHandSideTraversal.getIndexesRootedBy(parentPath); |
---|
| 445 | |
---|
| 446 | if ((indexes[0] >= rightTraversalIndex) && |
---|
| 447 | (indexes[1] < nextRightTraversalIndex)) |
---|
| 448 | { |
---|
| 449 | result.add(parentPath); |
---|
| 450 | break; // breaks only the path but the rest of the traversal is |
---|
| 451 | // checked too |
---|
| 452 | } |
---|
| 453 | } |
---|
| 454 | } |
---|
| 455 | } |
---|
| 456 | |
---|
| 457 | leftTraversalIndex = nextLeftTraversalIndex; |
---|
| 458 | rightTraversalIndex = nextRightTraversalIndex; |
---|
| 459 | } |
---|
| 460 | while (leftTraversalIndex < leftHandSideTraversal.size()); |
---|
| 461 | |
---|
| 462 | } |
---|
| 463 | |
---|
| 464 | return result; |
---|
| 465 | } |
---|
| 466 | |
---|
| 467 | /** |
---|
| 468 | * |
---|
| 469 | */ |
---|
| 470 | public void dump(PrintStream out) { |
---|
| 471 | out.println(); |
---|
| 472 | out.print("similar tasks: left "); |
---|
| 473 | out.print(leftHandSide); |
---|
| 474 | out.print(" ("); |
---|
| 475 | out.print(leftHandSide.getInstances().size()); |
---|
| 476 | out.print(" instances), right "); |
---|
| 477 | out.print(rightHandSide); |
---|
| 478 | out.print(" ("); |
---|
| 479 | out.print(rightHandSide.getInstances().size()); |
---|
| 480 | out.print(" instances), diff level "); |
---|
| 481 | out.println(diffLevel); |
---|
| 482 | |
---|
| 483 | out.println("left traversal"); |
---|
| 484 | for (TaskPath path : leftHandSideTraversal.getTraversalPaths()) { |
---|
| 485 | out.println(path); |
---|
| 486 | } |
---|
| 487 | |
---|
| 488 | out.println("right traversal"); |
---|
| 489 | for (TaskPath path : rightHandSideTraversal.getTraversalPaths()) { |
---|
| 490 | out.println(path); |
---|
| 491 | } |
---|
| 492 | |
---|
| 493 | if (patch != null) { |
---|
| 494 | out.println("deltas:"); |
---|
| 495 | for (Delta delta : patch.getDeltas()) { |
---|
| 496 | out.println(delta); |
---|
| 497 | } |
---|
| 498 | } |
---|
| 499 | |
---|
| 500 | List<String> linesLeft = new LinkedList<String>(); |
---|
| 501 | TaskPath path = new TaskPath(); |
---|
| 502 | path.add(leftHandSide, 0); |
---|
| 503 | dumpToLineList(path, leftHandSideTraversal, linesLeft); |
---|
| 504 | path.removeLast(); |
---|
| 505 | |
---|
| 506 | List<String> linesRight = new LinkedList<String>(); |
---|
| 507 | path.add(rightHandSide, 0); |
---|
| 508 | dumpToLineList(path, rightHandSideTraversal, linesRight); |
---|
| 509 | |
---|
| 510 | |
---|
| 511 | /*System.out.println("\n#################################################"); |
---|
| 512 | for (int j = 0; ((j < linesLeft.size()) || (j < linesRight.size())); j++) { |
---|
| 513 | String left = j < linesLeft.size() ? linesLeft.get(j) : ""; |
---|
| 514 | String right = j < linesRight.size() ? linesRight.get(j) : ""; |
---|
| 515 | |
---|
| 516 | StringBuffer line = new StringBuffer(); |
---|
| 517 | line.append(j); |
---|
| 518 | line.append(":\t"); |
---|
| 519 | line.append(left); |
---|
| 520 | |
---|
| 521 | for (int k = line.length(); k < 60; k++) { |
---|
| 522 | line.append(' '); |
---|
| 523 | } |
---|
| 524 | |
---|
| 525 | line.append(right); |
---|
| 526 | System.out.println(line); |
---|
| 527 | }*/ |
---|
| 528 | |
---|
| 529 | // change lists to have the same length depending on the changes |
---|
| 530 | int lineIndexLeft = 0; |
---|
| 531 | int lineIndexRight = 0; |
---|
| 532 | int leftHandTraversalIndex = 0; |
---|
| 533 | while (leftHandTraversalIndex < leftHandSideTraversal.size()) { |
---|
| 534 | |
---|
| 535 | //System.out.println("\n" + lineIndexLeft + " " + lineIndexRight); |
---|
| 536 | |
---|
| 537 | Delta delta = null; |
---|
| 538 | |
---|
| 539 | for (Delta candidate : patch.getDeltas()) { |
---|
| 540 | if (candidate.getOriginal().getPosition() == leftHandTraversalIndex) { |
---|
| 541 | delta = candidate; |
---|
| 542 | break; |
---|
| 543 | } |
---|
| 544 | } |
---|
| 545 | |
---|
| 546 | if ((delta != null) && (delta.getType() == Delta.TYPE.DELETE)) { |
---|
| 547 | for (int j = 0; j < delta.getOriginal().size(); j++) { |
---|
| 548 | while (linesLeft.get(lineIndexLeft) != null) { |
---|
| 549 | lineIndexLeft++; |
---|
| 550 | } |
---|
| 551 | |
---|
| 552 | linesLeft.remove(lineIndexLeft); |
---|
| 553 | |
---|
| 554 | while (lineIndexRight < lineIndexLeft) { |
---|
| 555 | linesRight.add(lineIndexRight++, null); |
---|
| 556 | } |
---|
| 557 | |
---|
| 558 | leftHandTraversalIndex++; |
---|
| 559 | } |
---|
| 560 | |
---|
| 561 | linesLeft.add(lineIndexLeft++, "-------------------------------------"); |
---|
| 562 | linesRight.add(lineIndexRight++, "-------------------------------------"); |
---|
| 563 | } |
---|
| 564 | else if ((delta != null) && (delta.getType() == Delta.TYPE.INSERT)) { |
---|
| 565 | for (int j = 0; j < delta.getRevised().size(); j++) { |
---|
| 566 | while (linesRight.get(lineIndexRight) != null) { |
---|
| 567 | lineIndexRight++; |
---|
| 568 | } |
---|
| 569 | |
---|
| 570 | linesRight.remove(lineIndexRight); |
---|
| 571 | |
---|
| 572 | while (lineIndexLeft < lineIndexRight) { |
---|
| 573 | linesLeft.add(lineIndexLeft++, null); |
---|
| 574 | } |
---|
| 575 | } |
---|
| 576 | |
---|
| 577 | // ensure that what is equal is harmonized too (because after an insert always |
---|
| 578 | // comes something equal). The traversal index will be updated automatically, |
---|
| 579 | // too. |
---|
| 580 | delta = null; |
---|
| 581 | |
---|
| 582 | linesLeft.add(lineIndexLeft++, "-------------------------------------"); |
---|
| 583 | linesRight.add(lineIndexRight++, "-------------------------------------"); |
---|
| 584 | } |
---|
| 585 | |
---|
| 586 | if ((delta == null) || (delta.getType() == Delta.TYPE.CHANGE)) { |
---|
| 587 | int chunkSizeLeft = delta != null ? delta.getOriginal().size() : 1; |
---|
| 588 | int chunkSizeRight = delta != null ? delta.getRevised().size() : 1; |
---|
| 589 | |
---|
| 590 | int chunksHandledLeft = 0; |
---|
| 591 | int chunksHandledRight = 0; |
---|
| 592 | |
---|
| 593 | for (int j = 0; j < Math.max(chunkSizeLeft, chunkSizeRight); j++) { |
---|
| 594 | if (chunksHandledLeft < chunkSizeLeft) { |
---|
| 595 | while (linesLeft.get(lineIndexLeft) != null) { |
---|
| 596 | lineIndexLeft++; |
---|
| 597 | } |
---|
| 598 | |
---|
| 599 | linesLeft.remove(lineIndexLeft); |
---|
| 600 | chunksHandledLeft++; |
---|
| 601 | } |
---|
| 602 | |
---|
| 603 | if (chunksHandledRight < chunkSizeRight) { |
---|
| 604 | while (linesRight.get(lineIndexRight) != null) { |
---|
| 605 | lineIndexRight++; |
---|
| 606 | } |
---|
| 607 | |
---|
| 608 | linesRight.remove(lineIndexRight); |
---|
| 609 | chunksHandledRight++; |
---|
| 610 | } |
---|
| 611 | |
---|
| 612 | while (lineIndexLeft < lineIndexRight) { |
---|
| 613 | linesLeft.add(lineIndexLeft++, null); |
---|
| 614 | } |
---|
| 615 | while (lineIndexRight < lineIndexLeft) { |
---|
| 616 | linesRight.add(lineIndexRight++, null); |
---|
| 617 | } |
---|
| 618 | } |
---|
| 619 | |
---|
| 620 | linesLeft.add(lineIndexLeft++, "-------------------------------------"); |
---|
| 621 | linesRight.add(lineIndexRight++, "-------------------------------------"); |
---|
| 622 | |
---|
| 623 | leftHandTraversalIndex += delta != null ? delta.getOriginal().size() : 1; |
---|
| 624 | } |
---|
| 625 | |
---|
| 626 | /*System.out.println(delta + " " + leftHandTraversalIndex); |
---|
| 627 | System.out.println("\n#################################################"); |
---|
| 628 | for (int j = 0; ((j < linesLeft.size()) || (j < linesRight.size())); j++) { |
---|
| 629 | String left = j < linesLeft.size() ? linesLeft.get(j) : ""; |
---|
| 630 | String right = j < linesRight.size() ? linesRight.get(j) : ""; |
---|
| 631 | |
---|
| 632 | StringBuffer line = new StringBuffer(); |
---|
| 633 | line.append(j); |
---|
| 634 | line.append(":\t"); |
---|
| 635 | line.append(left); |
---|
| 636 | |
---|
| 637 | for (int k = line.length(); k < 60; k++) { |
---|
| 638 | line.append(' '); |
---|
| 639 | } |
---|
| 640 | |
---|
| 641 | line.append(right); |
---|
| 642 | System.out.println(line); |
---|
| 643 | }*/ |
---|
| 644 | } |
---|
| 645 | |
---|
| 646 | int indentLeft = 0; |
---|
| 647 | int indentRight = 0; |
---|
| 648 | |
---|
| 649 | for (int i = 0; i < linesLeft.size(); i++) { |
---|
| 650 | StringBuffer line = new StringBuffer(); |
---|
| 651 | String left = linesLeft.get(i); |
---|
| 652 | String right = linesRight.get(i); |
---|
| 653 | |
---|
| 654 | if (left != null) { |
---|
| 655 | if (left.indexOf('}') >= 0) { |
---|
| 656 | indentLeft -= 2; |
---|
| 657 | } |
---|
| 658 | |
---|
| 659 | for (int j = 0; j < indentLeft; j++) { |
---|
| 660 | line.append(' '); |
---|
| 661 | } |
---|
| 662 | |
---|
| 663 | if (left.indexOf('{') >= 0) { |
---|
| 664 | indentLeft += 2; |
---|
| 665 | } |
---|
| 666 | |
---|
| 667 | line.append(left); |
---|
| 668 | } |
---|
| 669 | |
---|
| 670 | if (right != null) { |
---|
| 671 | for (int j = line.length(); j < 100; j++) { |
---|
| 672 | line.append(' '); |
---|
| 673 | } |
---|
| 674 | if (right.indexOf('}') >= 0) { |
---|
| 675 | indentRight -= 2; |
---|
| 676 | } |
---|
| 677 | |
---|
| 678 | for (int j = 0; j < indentRight; j++) { |
---|
| 679 | line.append(' '); |
---|
| 680 | } |
---|
| 681 | |
---|
| 682 | if (right.indexOf('{') >= 0) { |
---|
| 683 | indentRight += 2; |
---|
| 684 | } |
---|
| 685 | |
---|
| 686 | line.append(right); |
---|
| 687 | } |
---|
| 688 | |
---|
| 689 | out.println(line); |
---|
| 690 | } |
---|
| 691 | } |
---|
| 692 | |
---|
| 693 | /** |
---|
| 694 | * |
---|
| 695 | */ |
---|
| 696 | private static Set<ITask> getCommonInvolvedTasks(ITask task1, ITask task2) { |
---|
| 697 | Set<ITask> result = getAllInvolvedTasks(task1); |
---|
| 698 | result.retainAll(getAllInvolvedTasks(task2)); |
---|
| 699 | return result; |
---|
| 700 | } |
---|
| 701 | |
---|
| 702 | /** |
---|
| 703 | * |
---|
| 704 | */ |
---|
| 705 | private static Set<ITask> getAllInvolvedTasks(ITask task) { |
---|
| 706 | final Set<ITask> result = new HashSet<ITask>(); |
---|
| 707 | |
---|
| 708 | task.accept(new DefaultTaskTraversingVisitor() { |
---|
| 709 | @Override |
---|
| 710 | public void visit(IEventTask eventTask) { |
---|
| 711 | result.add(eventTask); |
---|
| 712 | } |
---|
| 713 | |
---|
| 714 | @Override |
---|
| 715 | public void visit(IStructuringTemporalRelationship relationship) { |
---|
| 716 | result.add(relationship); |
---|
| 717 | super.visit(relationship); |
---|
| 718 | } |
---|
| 719 | |
---|
| 720 | @Override |
---|
| 721 | public void visit(IMarkingTemporalRelationship relationship) { |
---|
| 722 | result.add(relationship); |
---|
| 723 | super.visit(relationship); |
---|
| 724 | } |
---|
| 725 | }); |
---|
| 726 | |
---|
| 727 | return result; |
---|
| 728 | } |
---|
| 729 | |
---|
| 730 | /** |
---|
| 731 | * |
---|
| 732 | */ |
---|
| 733 | private void dumpToLineList(TaskPath path, |
---|
| 734 | TaskTraversal traversal, |
---|
| 735 | List<String> lines) |
---|
| 736 | { |
---|
| 737 | boolean isTraversalElement = false; |
---|
| 738 | |
---|
| 739 | for (TaskPath candidate : traversal.getTraversalPaths()) { |
---|
| 740 | if (path.equals(candidate)) { |
---|
| 741 | isTraversalElement = true; |
---|
| 742 | break; |
---|
| 743 | } |
---|
| 744 | } |
---|
| 745 | |
---|
| 746 | if (isTraversalElement) { |
---|
| 747 | lines.add(path.getLast().toString()); |
---|
| 748 | lines.add(null); |
---|
| 749 | /*ByteArrayOutputStream byteStream = new ByteArrayOutputStream(); |
---|
| 750 | PrintStream out = new PrintStream(byteStream); |
---|
| 751 | |
---|
| 752 | new TaskTreeEncoder().encode(path.getLast(), out); |
---|
| 753 | |
---|
| 754 | out.close(); |
---|
| 755 | |
---|
| 756 | BufferedReader reader = new BufferedReader |
---|
| 757 | (new InputStreamReader(new ByteArrayInputStream(byteStream.toByteArray()))); |
---|
| 758 | |
---|
| 759 | String line = null; |
---|
| 760 | do { |
---|
| 761 | try { |
---|
| 762 | line = reader.readLine(); |
---|
| 763 | } |
---|
| 764 | catch (IOException e) { |
---|
| 765 | // should not happen so dump hard |
---|
| 766 | e.printStackTrace(); |
---|
| 767 | } |
---|
| 768 | lines.add(line != null ? line.trim() : null); |
---|
| 769 | } |
---|
| 770 | while (line != null);*/ |
---|
| 771 | |
---|
| 772 | } |
---|
| 773 | else { |
---|
| 774 | ITask task = path.getLast(); |
---|
| 775 | if (task instanceof ITemporalRelationship) { |
---|
| 776 | lines.add(task + " {"); |
---|
| 777 | |
---|
| 778 | if (task instanceof IStructuringTemporalRelationship) { |
---|
| 779 | List<ITask> children = |
---|
| 780 | ((IStructuringTemporalRelationship) task).getChildren(); |
---|
| 781 | |
---|
| 782 | for (int i = 0; i < children.size(); i++) { |
---|
| 783 | path.add(children.get(i), i); |
---|
| 784 | dumpToLineList(path, traversal, lines); |
---|
| 785 | path.removeLast(); |
---|
| 786 | } |
---|
| 787 | } |
---|
| 788 | else if (task instanceof IMarkingTemporalRelationship) { |
---|
| 789 | IMarkingTemporalRelationship relationship = |
---|
| 790 | (IMarkingTemporalRelationship) task; |
---|
| 791 | |
---|
| 792 | path.add(relationship.getMarkedTask(), 0); |
---|
| 793 | dumpToLineList(path, traversal, lines); |
---|
| 794 | path.removeLast(); |
---|
| 795 | } |
---|
| 796 | |
---|
| 797 | if (lines.get(lines.size() - 1) != null) { |
---|
| 798 | lines.add("}"); |
---|
| 799 | } |
---|
| 800 | else { |
---|
| 801 | lines.add(lines.size() - 1, "}"); |
---|
| 802 | } |
---|
| 803 | } |
---|
| 804 | else { |
---|
| 805 | lines.add(task + " {}"); |
---|
| 806 | } |
---|
| 807 | } |
---|
| 808 | } |
---|
| 809 | |
---|
| 810 | /** |
---|
| 811 | * |
---|
| 812 | */ |
---|
| 813 | /*@SuppressWarnings("unchecked") |
---|
| 814 | private void getSelections(Delta delta, List<TaskPath> result) { |
---|
| 815 | TaskPath path1 = getCommonPath((List<TaskPath>) delta.getOriginal().getLines()); |
---|
| 816 | TaskPath path2 = getCommonPath((List<TaskPath>) delta.getRevised().getLines()); |
---|
| 817 | |
---|
| 818 | for (int i = 0; i < path1.size(); i++) { |
---|
| 819 | if (path1.getTask(i) instanceof ISelection) { |
---|
| 820 | System.out.println("found selection to ignore"); |
---|
| 821 | System.out.println(path1.subPath(0, i + 1)); |
---|
| 822 | result.add(path1.subPath(0, i + 1)); |
---|
| 823 | break; |
---|
| 824 | } |
---|
| 825 | } |
---|
| 826 | |
---|
| 827 | for (int i = 0; i < path2.size(); i++) { |
---|
| 828 | if (path2.getTask(i) instanceof ISelection) { |
---|
| 829 | System.out.println("found selection to ignore"); |
---|
| 830 | System.out.println(path2.subPath(0, i + 1)); |
---|
| 831 | result.add(path2.subPath(0, i + 1)); |
---|
| 832 | break; |
---|
| 833 | } |
---|
| 834 | } |
---|
| 835 | }*/ |
---|
[1954] | 836 | |
---|
| 837 | /** |
---|
| 838 | * conflicting iterations are those that belong to either side of the sequence pair, that cover |
---|
| 839 | * at least two actions, and that were executed multiple times in the context of the tasks |
---|
| 840 | * to be merged. Iterations do only conflict, if there are at least two, one belonging to the |
---|
| 841 | * left hand side, and the other to the right hand side. They conflict only, if they cover the |
---|
| 842 | * same terminal nodes in the task traversals. |
---|
| 843 | */ |
---|
| 844 | private List<TaskPath> getConflictingIterations() { |
---|
| 845 | List<TaskPath> iterationsWithMultipleExecutions = new LinkedList<>(); |
---|
| 846 | getIterationsWithMultipleExecutions(leftHandSide, iterationsWithMultipleExecutions); |
---|
| 847 | |
---|
| 848 | if (iterationsWithMultipleExecutions.size() > 0) { |
---|
| 849 | // only, if iterations are executed in both side, they are of interest. Hence, |
---|
| 850 | // check right hand side only, if left hand side contains repeated iterations. |
---|
| 851 | int noOfLeftHandSideRepeatedIterations = iterationsWithMultipleExecutions.size(); |
---|
| 852 | getIterationsWithMultipleExecutions(rightHandSide, iterationsWithMultipleExecutions); |
---|
| 853 | |
---|
| 854 | if (iterationsWithMultipleExecutions.size() > noOfLeftHandSideRepeatedIterations) { |
---|
| 855 | // also the right hand side contains problematic iterations. Check if they are |
---|
| 856 | // overlapping and drop all which are not. |
---|
| 857 | dropNonOverlappingIterations(iterationsWithMultipleExecutions); |
---|
| 858 | } |
---|
| 859 | else { |
---|
| 860 | // no conflict, clear the list |
---|
| 861 | iterationsWithMultipleExecutions.clear(); |
---|
| 862 | } |
---|
| 863 | } |
---|
| 864 | |
---|
| 865 | return iterationsWithMultipleExecutions; |
---|
| 866 | } |
---|
[1767] | 867 | |
---|
| 868 | /** |
---|
| 869 | * |
---|
| 870 | */ |
---|
[1954] | 871 | private void getIterationsWithMultipleExecutions(ITask task, |
---|
| 872 | List<TaskPath> result) |
---|
| 873 | { |
---|
| 874 | for (ITaskInstance instance : task.getInstances()) { |
---|
| 875 | TaskPath taskPath = new TaskPath(); |
---|
| 876 | taskPath.add(task, 0); |
---|
| 877 | getIterationsWithMultipleExecutions(instance, taskPath, result); |
---|
| 878 | } |
---|
| 879 | } |
---|
| 880 | |
---|
| 881 | /** |
---|
| 882 | * |
---|
| 883 | */ |
---|
| 884 | private void getIterationsWithMultipleExecutions(ITaskInstance instance, |
---|
| 885 | TaskPath currentPath, |
---|
| 886 | List<TaskPath> result) |
---|
| 887 | { |
---|
| 888 | if (instance instanceof IIterationInstance) { |
---|
[1957] | 889 | ITask markedTask = instance.getTask(); |
---|
| 890 | |
---|
| 891 | while (markedTask instanceof IMarkingTemporalRelationship) { |
---|
| 892 | markedTask = ((IMarkingTemporalRelationship) markedTask).getMarkedTask(); |
---|
| 893 | } |
---|
| 894 | |
---|
| 895 | if ((!(markedTask instanceof IEventTask)) && |
---|
| 896 | ((IIterationInstance) instance).size() > 1) |
---|
| 897 | { |
---|
[1980] | 898 | // iteration repeats multiple event tasks and is executed multiple times --> |
---|
[1957] | 899 | // store path |
---|
[1954] | 900 | result.add(currentPath.subPath(0, currentPath.size())); // ensure to create a copy |
---|
| 901 | } |
---|
[1767] | 902 | |
---|
[1954] | 903 | currentPath.add(((IIteration) instance.getTask()).getMarkedTask(), 0); |
---|
[1767] | 904 | |
---|
[1954] | 905 | for (ITaskInstance child : (IIterationInstance) instance) { |
---|
| 906 | getIterationsWithMultipleExecutions(child, currentPath, result); |
---|
| 907 | } |
---|
| 908 | |
---|
| 909 | currentPath.removeLast(); |
---|
| 910 | } |
---|
| 911 | else if (instance instanceof ISequenceInstance) { |
---|
| 912 | int index = 0; |
---|
| 913 | for (ITaskInstance child : (ISequenceInstance) instance) { |
---|
| 914 | currentPath.add(child.getTask(), index++); |
---|
| 915 | getIterationsWithMultipleExecutions(child, currentPath, result); |
---|
| 916 | currentPath.removeLast(); |
---|
| 917 | } |
---|
| 918 | } |
---|
| 919 | else if (instance instanceof ISelectionInstance) { |
---|
| 920 | ITaskInstance child = ((ISelectionInstance) instance).getChild(); |
---|
| 921 | currentPath.add(child.getTask(), 0); |
---|
| 922 | getIterationsWithMultipleExecutions(child, currentPath, result); |
---|
| 923 | currentPath.removeLast(); |
---|
| 924 | } |
---|
| 925 | else if (instance instanceof IOptionalInstance) { |
---|
| 926 | ITaskInstance child = ((IOptionalInstance) instance).getChild(); |
---|
| 927 | if (child != null) { |
---|
| 928 | currentPath.add(child.getTask(), 0); |
---|
| 929 | getIterationsWithMultipleExecutions(child, currentPath, result); |
---|
| 930 | currentPath.removeLast(); |
---|
| 931 | } |
---|
| 932 | } |
---|
| 933 | } |
---|
| 934 | |
---|
| 935 | /** |
---|
| 936 | * |
---|
| 937 | */ |
---|
| 938 | private void dropNonOverlappingIterations(List<TaskPath> iterationsWithMultipleExecutions) { |
---|
| 939 | // to check overlappings, iterate the iterations. Then check for each the indexes it covers |
---|
| 940 | // in its respective traversal. Adapt the indexes depending on deltas that an iteration |
---|
| 941 | // covers. Then check all other iterations. Consider also here the indexes in the traversal. |
---|
| 942 | // also here, the indexes must be adapted in case of covered deltas. |
---|
| 943 | List<TaskPath> overlappingIterations = new LinkedList<TaskPath>(); |
---|
| 944 | |
---|
| 945 | for (TaskPath leftPath : iterationsWithMultipleExecutions) { |
---|
| 946 | if (leftPath.getTask(0).equals(leftHandSide)) { |
---|
| 947 | for (TaskPath rightPath : iterationsWithMultipleExecutions) { |
---|
| 948 | if (rightPath.getTask(0).equals(rightHandSide)) { |
---|
[1980] | 949 | int[] leftIdxs = leftHandSideTraversal.getIndexesRootedBy(leftPath); |
---|
[1954] | 950 | int[] rightIdxs = rightHandSideTraversal.getIndexesRootedBy(rightPath); |
---|
[1767] | 951 | |
---|
[1954] | 952 | adaptIndexesBasedOnDeltas(leftIdxs, rightIdxs, patch.getDeltas()); |
---|
| 953 | |
---|
[1980] | 954 | if (((leftIdxs[0] <= rightIdxs[0]) && (rightIdxs[0] <= leftIdxs[1])) || |
---|
| 955 | ((rightIdxs[0] <= leftIdxs[0]) && (leftIdxs[0] <= rightIdxs[1]))) |
---|
[1954] | 956 | { |
---|
| 957 | overlappingIterations.add(leftPath); |
---|
| 958 | overlappingIterations.add(rightPath); |
---|
| 959 | } |
---|
[1767] | 960 | } |
---|
| 961 | } |
---|
| 962 | } |
---|
| 963 | } |
---|
[1954] | 964 | |
---|
| 965 | iterationsWithMultipleExecutions.retainAll(overlappingIterations); |
---|
[1767] | 966 | } |
---|
| 967 | |
---|
| 968 | /** |
---|
| 969 | * |
---|
| 970 | */ |
---|
[1954] | 971 | private void adaptIndexesBasedOnDeltas(int[] originalIndexes, |
---|
| 972 | int[] revisedIndexes, |
---|
| 973 | List<Delta> deltas) |
---|
| 974 | { |
---|
| 975 | int originalStartUpdate = 0; |
---|
| 976 | int originalEndUpdate = 0; |
---|
| 977 | int revisedStartUpdate = 0; |
---|
| 978 | int revisedEndUpdate = 0; |
---|
| 979 | |
---|
| 980 | for (Delta delta : deltas) { |
---|
[1972] | 981 | if (delta.getType() == Delta.TYPE.INSERT) { |
---|
| 982 | // for insert deltas only the original indexes must be adapted |
---|
| 983 | if (delta.getOriginal().getPosition() <= originalIndexes[0]) { |
---|
| 984 | originalStartUpdate += delta.getRevised().size(); |
---|
| 985 | } |
---|
| 986 | if (delta.getOriginal().getPosition() <= originalIndexes[1]) { |
---|
| 987 | originalEndUpdate += delta.getRevised().size(); |
---|
| 988 | } |
---|
[1954] | 989 | } |
---|
[1972] | 990 | else if (delta.getType() == Delta.TYPE.DELETE) { |
---|
| 991 | // for delete deltas only the revised indexes must be adapted |
---|
| 992 | if (delta.getRevised().getPosition() <= revisedIndexes[0]) { |
---|
| 993 | revisedStartUpdate += delta.getOriginal().size(); |
---|
| 994 | } |
---|
| 995 | if (delta.getRevised().getPosition() <= revisedIndexes[1]) { |
---|
| 996 | revisedEndUpdate += delta.getOriginal().size(); |
---|
| 997 | } |
---|
[1954] | 998 | } |
---|
[1972] | 999 | else if (delta.getType() == Delta.TYPE.CHANGE) { |
---|
| 1000 | // for change deltas we adapt only the revision indexes. |
---|
| 1001 | // If the revised variant is longer than the original, the indexes become smaller. |
---|
| 1002 | // else, the other way around |
---|
| 1003 | int lengthDiff = delta.getOriginal().size() - delta.getRevised().size(); |
---|
| 1004 | |
---|
| 1005 | if (lengthDiff < 0) { |
---|
| 1006 | // the revised variant is longer --> adapt indexes of original |
---|
| 1007 | lengthDiff = 0 - lengthDiff; |
---|
| 1008 | int start = delta.getOriginal().getPosition(); |
---|
| 1009 | int end = start + delta.getOriginal().size() - 1; |
---|
| 1010 | |
---|
| 1011 | if (end < originalIndexes[0]) { |
---|
| 1012 | // delta is before indexes |
---|
| 1013 | originalStartUpdate += lengthDiff; |
---|
| 1014 | } |
---|
| 1015 | if ((end <= originalIndexes[1]) || (start <= originalIndexes[1])) { |
---|
| 1016 | // delta and indexes overlap |
---|
| 1017 | originalEndUpdate += lengthDiff; |
---|
| 1018 | } |
---|
| 1019 | } |
---|
| 1020 | else if (lengthDiff > 0) { |
---|
| 1021 | // the original variant is longer --> adapt indexes of revised |
---|
| 1022 | int start = delta.getRevised().getPosition(); |
---|
| 1023 | int end = start + delta.getRevised().size() - 1; |
---|
| 1024 | |
---|
| 1025 | if (end < revisedIndexes[0]) { |
---|
| 1026 | // delta is before indexes |
---|
| 1027 | revisedStartUpdate += lengthDiff; |
---|
| 1028 | } |
---|
| 1029 | if ((end <= revisedIndexes[1]) || (start <= revisedIndexes[1])) { |
---|
| 1030 | // delta and indexes overlap |
---|
| 1031 | revisedEndUpdate += lengthDiff; |
---|
| 1032 | } |
---|
| 1033 | } |
---|
[1954] | 1034 | } |
---|
| 1035 | } |
---|
| 1036 | |
---|
| 1037 | originalIndexes[0] += originalStartUpdate; |
---|
| 1038 | originalIndexes[1] += originalEndUpdate; |
---|
| 1039 | revisedIndexes[0] += revisedStartUpdate; |
---|
| 1040 | revisedIndexes[1] += revisedEndUpdate; |
---|
| 1041 | } |
---|
| 1042 | |
---|
| 1043 | /** |
---|
| 1044 | * |
---|
| 1045 | */ |
---|
[1767] | 1046 | private TaskPath getCommonPath(List<TaskPath> paths) { |
---|
| 1047 | TaskPath commonPath; |
---|
| 1048 | |
---|
| 1049 | if (paths.size() > 0) { |
---|
| 1050 | commonPath = new TaskPath(paths.get(0)); |
---|
| 1051 | |
---|
| 1052 | for (int i = 1; i < paths.size(); i++) { |
---|
| 1053 | TaskPath comparePath = paths.get(i); |
---|
| 1054 | for (int j = 0; (j < commonPath.size()) && (j < comparePath.size()); j++) { |
---|
| 1055 | if (!commonPath.get(j).equals(comparePath.get(j))) { |
---|
| 1056 | while (commonPath.size() > j) { |
---|
[1850] | 1057 | commonPath.removeLast(); |
---|
[1767] | 1058 | } |
---|
| 1059 | break; |
---|
| 1060 | } |
---|
| 1061 | } |
---|
| 1062 | } |
---|
| 1063 | } |
---|
| 1064 | else { |
---|
| 1065 | commonPath = new TaskPath(); |
---|
| 1066 | } |
---|
| 1067 | |
---|
| 1068 | return commonPath; |
---|
| 1069 | } |
---|
| 1070 | |
---|
| 1071 | /** |
---|
| 1072 | * |
---|
| 1073 | */ |
---|
| 1074 | private void getNotFullyInterleavingIteration(Delta delta, List<TaskPath> result) { |
---|
| 1075 | getNotFullyInterleavingIterations(delta.getOriginal(), leftHandSideTraversal, result); |
---|
| 1076 | getNotFullyInterleavingIterations(delta.getRevised(), rightHandSideTraversal, result); |
---|
| 1077 | } |
---|
| 1078 | |
---|
| 1079 | /** |
---|
| 1080 | * If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration |
---|
[1954] | 1081 | * that does not cover the other and also expands to preceding or succeeding paths in the |
---|
| 1082 | * traversal, we can not merge the situation. |
---|
[1767] | 1083 | */ |
---|
| 1084 | private void getNotFullyInterleavingIterations(Chunk chunk, |
---|
| 1085 | TaskTraversal traversal, |
---|
| 1086 | List<TaskPath> result) |
---|
| 1087 | { |
---|
| 1088 | @SuppressWarnings("unchecked") |
---|
| 1089 | List<TaskPath> paths = (List<TaskPath>) chunk.getLines(); |
---|
| 1090 | |
---|
| 1091 | TaskPath commonPath = getCommonPath(paths); |
---|
| 1092 | |
---|
| 1093 | if (paths.size() > 1) { |
---|
| 1094 | TaskPath firstPath = paths.get(0); |
---|
| 1095 | TaskPath lastPath = paths.get(paths.size() - 1); |
---|
| 1096 | |
---|
| 1097 | for (int i = commonPath.size(); i < firstPath.size(); i++) { |
---|
| 1098 | if (firstPath.get(i).getTask() instanceof IIteration) { |
---|
| 1099 | // check, if the iteration covers things preceding the delta but not the whole |
---|
| 1100 | // delta |
---|
| 1101 | int[] indexes = traversal.getIndexesRootedBy(firstPath.subPath(0, i + 1)); |
---|
| 1102 | |
---|
| 1103 | if ((indexes[0] < chunk.getPosition()) && // starts before the delta |
---|
| 1104 | (indexes[1] < (chunk.getPosition() + chunk.size() - 1))) // does not cover delta |
---|
| 1105 | { |
---|
| 1106 | result.add(firstPath.subPath(0, i + 1)); |
---|
| 1107 | break; |
---|
| 1108 | } |
---|
| 1109 | } |
---|
| 1110 | } |
---|
| 1111 | |
---|
| 1112 | for (int i = commonPath.size(); i < lastPath.size(); i++) { |
---|
| 1113 | if (lastPath.get(i).getTask() instanceof IIteration) { |
---|
| 1114 | // check, if the iteration covers things preceding the delta but not the whole |
---|
| 1115 | // delta |
---|
| 1116 | int[] indexes = traversal.getIndexesRootedBy(lastPath.subPath(0, i + 1)); |
---|
| 1117 | |
---|
| 1118 | if ((indexes[0] > chunk.getPosition()) && // starts in between the delta |
---|
| 1119 | (indexes[1] >= (chunk.getPosition() + chunk.size()))) // ends after the delta |
---|
| 1120 | { |
---|
| 1121 | result.add(lastPath.subPath(0, i + 1)); |
---|
| 1122 | break; |
---|
| 1123 | } |
---|
| 1124 | } |
---|
| 1125 | } |
---|
| 1126 | } |
---|
| 1127 | } |
---|
| 1128 | |
---|
| 1129 | /** |
---|
| 1130 | * |
---|
| 1131 | */ |
---|
| 1132 | private void getPathsToParentTasksFullyInsideDelta(Delta delta, List<TaskPath> result) { |
---|
| 1133 | getPathsToParentTasksFullyInsideChunk(delta.getOriginal(), leftHandSideTraversal, result); |
---|
| 1134 | getPathsToParentTasksFullyInsideChunk(delta.getRevised(), rightHandSideTraversal, result); |
---|
| 1135 | } |
---|
| 1136 | |
---|
| 1137 | /** |
---|
| 1138 | * If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration |
---|
| 1139 | * the does not cover the other and also expands to preceding or succeeding paths in the |
---|
| 1140 | * traversal, we can no merge the situation. |
---|
| 1141 | */ |
---|
| 1142 | private void getPathsToParentTasksFullyInsideChunk(Chunk chunk, |
---|
| 1143 | TaskTraversal traversal, |
---|
| 1144 | List<TaskPath> result) |
---|
| 1145 | { |
---|
| 1146 | @SuppressWarnings("unchecked") |
---|
| 1147 | List<TaskPath> paths = (List<TaskPath>) chunk.getLines(); |
---|
| 1148 | |
---|
| 1149 | for (TaskPath path : paths) { |
---|
[1974] | 1150 | for (int i = path.size() - 1; i >= 0; i--) { |
---|
[1973] | 1151 | // check, if the parent task covers things fully inside the delta |
---|
[1974] | 1152 | TaskPath parentPath = path.subPath(0, i); |
---|
[1973] | 1153 | |
---|
[1974] | 1154 | //System.out.println("checking parent path " + parentPath); |
---|
| 1155 | int[] indexes = traversal.getIndexesRootedBy(parentPath); |
---|
| 1156 | //System.out.println("indexes are " + indexes[0] + " " + indexes[1]); |
---|
| 1157 | |
---|
[1973] | 1158 | if ((chunk.getPosition() <= indexes[0]) && // starts in the delta |
---|
| 1159 | (indexes[1] < (chunk.getPosition() + chunk.size()))) // ends in the delta |
---|
| 1160 | { |
---|
[1974] | 1161 | //System.out.println("found path to parent task lying completely in the " + |
---|
| 1162 | // "delta: " + parentPath); |
---|
| 1163 | result.add(parentPath); |
---|
| 1164 | } |
---|
| 1165 | else { |
---|
| 1166 | // further parents can not be inside the delta |
---|
[1973] | 1167 | break; |
---|
[1767] | 1168 | } |
---|
| 1169 | } |
---|
| 1170 | } |
---|
| 1171 | } |
---|
| 1172 | |
---|
| 1173 | /** |
---|
| 1174 | * |
---|
| 1175 | */ |
---|
[1954] | 1176 | private void getUnexecutedParentOptionals(ITask task, |
---|
| 1177 | List<TaskPath> result) |
---|
| 1178 | { |
---|
| 1179 | for (ITaskInstance instance : task.getInstances()) { |
---|
| 1180 | TaskPath taskPath = new TaskPath(); |
---|
| 1181 | taskPath.add(task, 0); |
---|
| 1182 | getUnexecutedParentOptionals(instance, taskPath, result); |
---|
[1850] | 1183 | } |
---|
[1954] | 1184 | } |
---|
| 1185 | |
---|
| 1186 | /** |
---|
| 1187 | * |
---|
| 1188 | */ |
---|
| 1189 | private void getUnexecutedParentOptionals(ITaskInstance instance, |
---|
| 1190 | TaskPath currentPath, |
---|
| 1191 | List<TaskPath> result) |
---|
| 1192 | { |
---|
| 1193 | if (instance instanceof IOptionalInstance) { |
---|
| 1194 | ITaskInstance child = ((IOptionalInstance) instance).getChild(); |
---|
| 1195 | if (child != null) { |
---|
| 1196 | currentPath.add(child.getTask(), 0); |
---|
| 1197 | getUnexecutedParentOptionals(child, currentPath, result); |
---|
| 1198 | currentPath.removeLast(); |
---|
[1850] | 1199 | } |
---|
[1954] | 1200 | else { |
---|
| 1201 | result.add(currentPath.subPath(0, currentPath.size())); // ensure to create a copy |
---|
| 1202 | } |
---|
[1850] | 1203 | } |
---|
[1954] | 1204 | else if (instance instanceof IIterationInstance) { |
---|
| 1205 | currentPath.add(((IIteration) instance.getTask()).getMarkedTask(), 0); |
---|
| 1206 | |
---|
| 1207 | for (ITaskInstance child : (IIterationInstance) instance) { |
---|
| 1208 | getUnexecutedParentOptionals(child, currentPath, result); |
---|
[1850] | 1209 | } |
---|
[1954] | 1210 | |
---|
| 1211 | currentPath.removeLast(); |
---|
[1850] | 1212 | } |
---|
[1954] | 1213 | else if (instance instanceof ISequenceInstance) { |
---|
| 1214 | int index = 0; |
---|
| 1215 | for (ITaskInstance child : (ISequenceInstance) instance) { |
---|
| 1216 | currentPath.add(child.getTask(), index++); |
---|
| 1217 | getUnexecutedParentOptionals(child, currentPath, result); |
---|
| 1218 | currentPath.removeLast(); |
---|
| 1219 | } |
---|
[1850] | 1220 | } |
---|
[1954] | 1221 | else if (instance instanceof ISelectionInstance) { |
---|
| 1222 | ITaskInstance child = ((ISelectionInstance) instance).getChild(); |
---|
| 1223 | currentPath.add(child.getTask(), 0); |
---|
| 1224 | getUnexecutedParentOptionals(child, currentPath, result); |
---|
| 1225 | currentPath.removeLast(); |
---|
| 1226 | } |
---|
[1850] | 1227 | } |
---|
| 1228 | |
---|
| 1229 | /** |
---|
| 1230 | * |
---|
| 1231 | */ |
---|
[1767] | 1232 | @SuppressWarnings("unchecked") |
---|
| 1233 | private int getDiffLevel(Patch patch, |
---|
| 1234 | TaskTraversal traversal1, |
---|
| 1235 | TaskTraversal traversal2) |
---|
| 1236 | { |
---|
[1980] | 1237 | if (patch.getDeltas().size() == 0) { |
---|
| 1238 | return 0; |
---|
| 1239 | } |
---|
| 1240 | |
---|
[1767] | 1241 | int diffCount = 0; |
---|
| 1242 | int allCount = 0; |
---|
| 1243 | |
---|
| 1244 | for (Delta delta : patch.getDeltas()) { |
---|
| 1245 | for (TaskPath path : (List<TaskPath>) delta.getOriginal().getLines()) { |
---|
| 1246 | // inefficient actions are counted later. |
---|
| 1247 | if (!isInefficientAction(path.getLast())) { |
---|
| 1248 | diffCount += getDiffPenalty(path.getLast()); |
---|
| 1249 | } |
---|
| 1250 | } |
---|
| 1251 | for (TaskPath path : (List<TaskPath>) delta.getRevised().getLines()) { |
---|
| 1252 | // inefficient actions are counted later. |
---|
| 1253 | if (!isInefficientAction(path.getLast())) { |
---|
| 1254 | diffCount += getDiffPenalty(path.getLast()); |
---|
| 1255 | } |
---|
| 1256 | } |
---|
| 1257 | } |
---|
| 1258 | |
---|
| 1259 | //if (getPathsToRealIntersectingIterations().size() > 0) { |
---|
| 1260 | // add a penalty if intersecting iterations are present |
---|
| 1261 | //count += 10; |
---|
| 1262 | //} |
---|
| 1263 | |
---|
| 1264 | // add a penalty for inefficient actions which are equal as they have to be treated |
---|
| 1265 | // unequal, too. Otherwise, many scrolls, e.g., would pretend a high equality of tasks |
---|
| 1266 | // which contain only some non inefficient actions |
---|
| 1267 | for (TaskPath path : traversal1.getTraversalPaths()) { |
---|
| 1268 | if (isInefficientAction(path.getLast())) { |
---|
| 1269 | diffCount++; |
---|
[1890] | 1270 | allCount++; |
---|
[1767] | 1271 | } |
---|
| 1272 | else { |
---|
| 1273 | allCount += getDiffPenalty(path.getLast()); |
---|
| 1274 | } |
---|
| 1275 | } |
---|
| 1276 | |
---|
| 1277 | for (TaskPath path : traversal2.getTraversalPaths()) { |
---|
| 1278 | if (isInefficientAction(path.getLast())) { |
---|
| 1279 | diffCount++; |
---|
[1890] | 1280 | allCount++; |
---|
[1767] | 1281 | } |
---|
| 1282 | else { |
---|
| 1283 | allCount += getDiffPenalty(path.getLast()); |
---|
| 1284 | } |
---|
| 1285 | } |
---|
| 1286 | |
---|
[1890] | 1287 | if (allCount == 0) { |
---|
| 1288 | // this happens, if all actions are inefficient. Return the highest diff level |
---|
| 1289 | return 100; |
---|
| 1290 | } |
---|
| 1291 | else { |
---|
| 1292 | return (100 * diffCount) / allCount; |
---|
| 1293 | } |
---|
[1767] | 1294 | } |
---|
| 1295 | |
---|
| 1296 | /** |
---|
| 1297 | * |
---|
| 1298 | */ |
---|
| 1299 | private boolean isInefficientAction(ITask task) { |
---|
[2126] | 1300 | if (task instanceof IEventTask) { |
---|
| 1301 | IEventTaskInstance inst = (IEventTaskInstance) task.getInstances().iterator().next(); |
---|
| 1302 | if (inst.getEvent().getType() instanceof Scroll) { |
---|
| 1303 | return true; |
---|
| 1304 | } |
---|
| 1305 | else { |
---|
| 1306 | return false; |
---|
| 1307 | } |
---|
[1767] | 1308 | } |
---|
| 1309 | else if (task instanceof IMarkingTemporalRelationship) { |
---|
| 1310 | return isInefficientAction(((IMarkingTemporalRelationship) task).getMarkedTask()); |
---|
| 1311 | } |
---|
| 1312 | else { |
---|
| 1313 | return false; |
---|
| 1314 | } |
---|
| 1315 | } |
---|
| 1316 | |
---|
| 1317 | |
---|
| 1318 | /** |
---|
| 1319 | * |
---|
| 1320 | */ |
---|
| 1321 | private int getDiffPenalty(ITask task) { |
---|
| 1322 | if (task instanceof IEventTask) { |
---|
| 1323 | return 1; |
---|
| 1324 | } |
---|
| 1325 | else if (task instanceof IMarkingTemporalRelationship) { |
---|
| 1326 | return getDiffPenalty(((IMarkingTemporalRelationship) task).getMarkedTask()); |
---|
| 1327 | } |
---|
| 1328 | else if (task instanceof IStructuringTemporalRelationship) { |
---|
| 1329 | int result = 0; |
---|
| 1330 | |
---|
| 1331 | for (ITask child : ((IStructuringTemporalRelationship) task).getChildren()) { |
---|
| 1332 | result += getDiffPenalty(child); |
---|
| 1333 | } |
---|
| 1334 | |
---|
| 1335 | if (task instanceof ISelection) { |
---|
| 1336 | result /= ((IStructuringTemporalRelationship) task).getChildren().size(); |
---|
| 1337 | } |
---|
| 1338 | |
---|
| 1339 | return result; |
---|
| 1340 | } |
---|
| 1341 | |
---|
| 1342 | throw new IllegalArgumentException("unknown type of task: " + task); |
---|
| 1343 | } |
---|
| 1344 | } |
---|