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