1 package com.github.javaparser.printer.lexicalpreservation; 2 3 import com.github.javaparser.GeneratedJavaParserConstants; 4 import com.github.javaparser.ast.Node; 5 import com.github.javaparser.ast.comments.Comment; 6 import com.github.javaparser.ast.type.PrimitiveType; 7 import com.github.javaparser.TokenTypes; 8 import com.github.javaparser.printer.concretesyntaxmodel.*; 9 import com.github.javaparser.printer.lexicalpreservation.LexicalDifferenceCalculator.CsmChild; 10 11 import java.util.*; 12 import java.util.stream.Collectors; 13 14 import static com.github.javaparser.GeneratedJavaParserConstants.*; 15 16 /** 17 * A Difference should give me a sequence of elements I should find (to indicate the context) followed by a list of elements 18 * to remove or to add and follow by another sequence of elements. 19 * 20 * I should later be able to apply such difference to a nodeText. 21 */ 22 public class Difference { 23 24 private static final int STANDARD_INDENTATION_SIZE = 4; 25 26 private final List<DifferenceElement> elements; 27 28 private Difference(List<DifferenceElement> elements) { 29 this.elements = elements; 30 } 31 32 interface DifferenceElement { 33 static DifferenceElement added(CsmElement element) { 34 return new Added(element); 35 } 36 37 static DifferenceElement removed(CsmElement element) { 38 return new Removed(element); 39 } 40 41 static DifferenceElement kept(CsmElement element) { 42 return new Kept(element); 43 } 44 45 /** 46 * Return the CsmElement considered in this DifferenceElement. 47 */ 48 CsmElement getElement(); 49 50 boolean isAdded(); 51 } 52 53 private static class Added implements DifferenceElement { 54 final CsmElement element; 55 56 public Added(CsmElement element) { 57 this.element = element; 58 } 59 60 @Override 61 public String toString() { 62 return "Added{" + element + '}'; 63 } 64 65 @Override 66 public boolean equals(Object o) { 67 if (this == o) return true; 68 if (o == null || getClass() != o.getClass()) return false; 69 70 Added added = (Added) o; 71 72 return element.equals(added.element); 73 } 74 75 @Override 76 public int hashCode() { 77 return element.hashCode(); 78 } 79 80 @Override 81 public CsmElement getElement() { 82 return element; 83 } 84 85 @Override 86 public boolean isAdded() { 87 return true; 88 } 89 } 90 91 /** 92 * Elements in a CsmMix have been reshuffled. It could also mean that 93 * some new elements have been added or removed to the mix. 94 */ 95 private static class Reshuffled implements DifferenceElement { 96 final CsmMix previousOrder; 97 final CsmMix element; 98 99 public Reshuffled(CsmMix previousOrder, CsmMix element) { 100 this.previousOrder = previousOrder; 101 this.element = element; 102 } 103 104 @Override 105 public String toString() { 106 return "Reshuffled{" + element + ", previous="+ previousOrder+ '}'; 107 } 108 109 @Override 110 public boolean equals(Object o) { 111 if (this == o) return true; 112 if (o == null || getClass() != o.getClass()) return false; 113 114 Reshuffled that = (Reshuffled) o; 115 116 if (!previousOrder.equals(that.previousOrder)) return false; 117 return element.equals(that.element); 118 } 119 120 @Override 121 public int hashCode() { 122 int result = previousOrder.hashCode(); 123 result = 31 * result + element.hashCode(); 124 return result; 125 } 126 127 @Override 128 public CsmMix getElement() { 129 return element; 130 } 131 132 @Override 133 public boolean isAdded() { 134 return false; 135 } 136 } 137 138 private static class Kept implements DifferenceElement { 139 final CsmElement element; 140 141 public Kept(CsmElement element) { 142 this.element = element; 143 } 144 145 @Override 146 public String toString() { 147 return "Kept{" + element + '}'; 148 } 149 150 @Override 151 public boolean equals(Object o) { 152 if (this == o) return true; 153 if (o == null || getClass() != o.getClass()) return false; 154 155 Kept kept = (Kept) o; 156 157 return element.equals(kept.element); 158 } 159 160 @Override 161 public int hashCode() { 162 return element.hashCode(); 163 } 164 165 @Override 166 public CsmElement getElement() { 167 return element; 168 } 169 170 @Override 171 public boolean isAdded() { 172 return false; 173 } 174 } 175 176 private static class Removed implements DifferenceElement { 177 final CsmElement element; 178 179 public Removed(CsmElement element) { 180 this.element = element; 181 } 182 183 @Override 184 public String toString() { 185 return "Removed{" + element + '}'; 186 } 187 188 @Override 189 public boolean equals(Object o) { 190 if (this == o) return true; 191 if (o == null || getClass() != o.getClass()) return false; 192 193 Removed removed = (Removed) o; 194 195 return element.equals(removed.element); 196 } 197 198 @Override 199 public int hashCode() { 200 return element.hashCode(); 201 } 202 203 @Override 204 public CsmElement getElement() { 205 return element; 206 } 207 208 @Override 209 public boolean isAdded() { 210 return false; 211 } 212 } 213 214 private static boolean matching(CsmElement a, CsmElement b) { 215 if (a instanceof CsmChild) { 216 if (b instanceof CsmChild) { 217 CsmChild childA = (CsmChild) a; 218 CsmChild childB = (CsmChild) b; 219 return childA.getChild().equals(childB.getChild()); 220 } else if (b instanceof CsmToken) { 221 return false; 222 } else if (b instanceof CsmIndent) { 223 return false; 224 } else if (b instanceof CsmUnindent) { 225 return false; 226 } else { 227 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 228 } 229 } else if (a instanceof CsmToken) { 230 if (b instanceof CsmToken) { 231 CsmToken childA = (CsmToken)a; 232 CsmToken childB = (CsmToken)b; 233 return childA.getTokenType() == childB.getTokenType(); 234 } else if (b instanceof CsmChild) { 235 return false; 236 } else if (b instanceof CsmIndent) { 237 return false; 238 } else if (b instanceof CsmUnindent) { 239 return false; 240 } else { 241 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 242 } 243 } else if (a instanceof CsmIndent) { 244 return b instanceof CsmIndent; 245 } else if (a instanceof CsmUnindent) { 246 return b instanceof CsmUnindent; 247 } 248 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 249 } 250 251 private static boolean replacement(CsmElement a, CsmElement b) { 252 if (a instanceof CsmIndent || b instanceof CsmIndent || a instanceof CsmUnindent || b instanceof CsmUnindent) { 253 return false; 254 } 255 if (a instanceof CsmChild) { 256 if (b instanceof CsmChild) { 257 CsmChild childA = (CsmChild) a; 258 CsmChild childB = (CsmChild) b; 259 return childA.getChild().getClass().equals(childB.getChild().getClass()); 260 } else if (b instanceof CsmToken) { 261 return false; 262 } else { 263 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 264 } 265 } else if (a instanceof CsmToken) { 266 if (b instanceof CsmToken) { 267 CsmToken childA = (CsmToken)a; 268 CsmToken childB = (CsmToken)b; 269 return childA.getTokenType() == childB.getTokenType(); 270 } else if (b instanceof CsmChild) { 271 return false; 272 } 273 } 274 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 275 } 276 277 /** 278 * Find the positions of all the given children. 279 */ 280 private static Map<Node, Integer> findChildrenPositions(LexicalDifferenceCalculator.CalculatedSyntaxModel calculatedSyntaxModel) { 281 Map<Node, Integer> positions = new HashMap<>(); 282 for (int i=0;i<calculatedSyntaxModel.elements.size();i++) { 283 CsmElement element = calculatedSyntaxModel.elements.get(i); 284 if (element instanceof CsmChild) { 285 positions.put(((CsmChild)element).getChild(), i); 286 } 287 } 288 return positions; 289 } 290 291 /** 292 * Calculate the Difference between two CalculatedSyntaxModel elements, determining which elements were kept, 293 * which were added and which were removed. 294 */ 295 static Difference calculate(LexicalDifferenceCalculator.CalculatedSyntaxModel original, LexicalDifferenceCalculator.CalculatedSyntaxModel after) { 296 // For performance reasons we use the positions of matching children 297 // to guide the calculation of the difference 298 // 299 // Suppose we have: 300 // qwerty[A]uiop 301 // qwer[A]uiop 302 // 303 // with [A] being a child and lowercase letters being tokens 304 // 305 // We would calculate the Difference between "qwerty" and "qwer" then we know the A is kep, and then we 306 // would calculate the difference between "uiop" and "uiop" 307 308 Map<Node, Integer> childrenInOriginal = findChildrenPositions(original); 309 Map<Node, Integer> childrenInAfter = findChildrenPositions(after); 310 311 List<Node> commonChildren = new LinkedList<>(childrenInOriginal.keySet()); 312 commonChildren.retainAll(childrenInAfter.keySet()); 313 commonChildren.sort(Comparator.comparingInt(childrenInOriginal::get)); 314 315 List<DifferenceElement> elements = new LinkedList<>(); 316 317 int originalIndex = 0; 318 int afterIndex = 0; 319 int commonChildrenIndex = 0; 320 while (commonChildrenIndex < commonChildren.size()) { 321 Node child = commonChildren.get(commonChildrenIndex++); 322 int posOfNextChildInOriginal = childrenInOriginal.get(child); 323 int posOfNextChildInAfter = childrenInAfter.get(child); 324 if (originalIndex < posOfNextChildInOriginal || afterIndex < posOfNextChildInAfter) { 325 elements.addAll(calculateImpl(original.sub(originalIndex, posOfNextChildInOriginal), after.sub(afterIndex, posOfNextChildInAfter)).elements); 326 } 327 elements.add(new Kept(new CsmChild(child))); 328 originalIndex = posOfNextChildInOriginal + 1; 329 afterIndex = posOfNextChildInAfter + 1; 330 } 331 332 if (originalIndex < original.elements.size() || afterIndex < after.elements.size()) { 333 elements.addAll(calculateImpl(original.sub(originalIndex, original.elements.size()), after.sub(afterIndex, after.elements.size())).elements); 334 } 335 return new Difference(elements); 336 } 337 338 private static Difference calculateImpl(LexicalDifferenceCalculator.CalculatedSyntaxModel original, LexicalDifferenceCalculator.CalculatedSyntaxModel after) { 339 List<DifferenceElement> elements = new LinkedList<>(); 340 341 int originalIndex = 0; 342 int afterIndex = 0; 343 344 // We move through the two CalculatedSyntaxModel, moving both forward when we have a match 345 // and moving just one side forward when we have an element kept or removed 346 347 do { 348 if (originalIndex < original.elements.size() && afterIndex >= after.elements.size()) { 349 elements.add(new Removed(original.elements.get(originalIndex))); 350 originalIndex++; 351 } else if (originalIndex >= original.elements.size() && afterIndex < after.elements.size()) { 352 elements.add(new Added(after.elements.get(afterIndex))); 353 afterIndex++; 354 } else { 355 CsmElement nextOriginal = original.elements.get(originalIndex); 356 CsmElement nextAfter = after.elements.get(afterIndex); 357 358 if ((nextOriginal instanceof CsmMix) && (nextAfter instanceof CsmMix)) { 359 if (((CsmMix) nextAfter).getElements().equals(((CsmMix) nextOriginal).getElements())) { 360 // No reason to deal with a reshuffled, we are just going to keep everything as it is 361 ((CsmMix) nextAfter).getElements().forEach(el -> elements.add(new Kept(el))); 362 } else { 363 elements.add(new Reshuffled((CsmMix)nextOriginal, (CsmMix)nextAfter)); 364 } 365 originalIndex++; 366 afterIndex++; 367 } else if (matching(nextOriginal, nextAfter)) { 368 elements.add(new Kept(nextOriginal)); 369 originalIndex++; 370 afterIndex++; 371 } else if (replacement(nextOriginal, nextAfter)) { 372 elements.add(new Removed(nextOriginal)); 373 elements.add(new Added(nextAfter)); 374 originalIndex++; 375 afterIndex++; 376 } else { 377 // We can try to remove the element or add it and look which one leads to the lower difference 378 Difference adding = calculate(original.from(originalIndex), after.from(afterIndex + 1)); 379 Difference removing = null; 380 if (adding.cost() > 0) { 381 removing = calculate(original.from(originalIndex + 1), after.from(afterIndex)); 382 } 383 384 if (removing == null || removing.cost() > adding.cost()) { 385 elements.add(new Added(nextAfter)); 386 afterIndex++; 387 } else { 388 elements.add(new Removed(nextOriginal)); 389 originalIndex++; 390 } 391 } 392 } 393 } while (originalIndex < original.elements.size() || afterIndex < after.elements.size()); 394 395 return new Difference(elements); 396 } 397 398 private TextElement toTextElement(CsmElement csmElement) { 399 if (csmElement instanceof CsmChild) { 400 return new ChildTextElement(((CsmChild) csmElement).getChild()); 401 } else if (csmElement instanceof CsmToken) { 402 return new TokenTextElement(((CsmToken) csmElement).getTokenType(), ((CsmToken) csmElement).getContent(null)); 403 } else { 404 throw new UnsupportedOperationException(csmElement.getClass().getSimpleName()); 405 } 406 } 407 408 private List<TextElement> processIndentation(List<TokenTextElement> indentation, List<TextElement> prevElements) { 409 List<TextElement> res = new LinkedList<>(); 410 res.addAll(indentation); 411 boolean afterNl = false; 412 for (TextElement e : prevElements) { 413 if (e.isNewline() || e.isToken(SINGLE_LINE_COMMENT)) { 414 res.clear(); 415 afterNl = true; 416 } else { 417 if (afterNl && e instanceof TokenTextElement && TokenTypes.isWhitespace(((TokenTextElement)e).getTokenKind())) { 418 res.add(e); 419 } else { 420 afterNl = false; 421 } 422 } 423 } 424 return res; 425 } 426 427 private List<TextElement> indentationBlock() { 428 List<TextElement> res = new LinkedList<>(); 429 res.add(new TokenTextElement(SPACE)); 430 res.add(new TokenTextElement(SPACE)); 431 res.add(new TokenTextElement(SPACE)); 432 res.add(new TokenTextElement(SPACE)); 433 return res; 434 } 435 436 private int considerCleaningTheLine(NodeText nodeText, int nodeTextIndex) { 437 while (nodeTextIndex >=1 && nodeText.getElements().get(nodeTextIndex - 1).isWhiteSpace() && !nodeText.getElements().get(nodeTextIndex - 1).isNewline()) { 438 nodeText.removeElement(nodeTextIndex - 1); 439 nodeTextIndex--; 440 } 441 return nodeTextIndex; 442 } 443 444 private boolean isAfterLBrace(NodeText nodeText, int nodeTextIndex) { 445 if (nodeTextIndex > 0 && nodeText.getElements().get(nodeTextIndex - 1).isToken(LBRACE)) { 446 return true; 447 } 448 if (nodeTextIndex > 0 && nodeText.getElements().get(nodeTextIndex - 1).isWhiteSpace() && !nodeText.getElements().get(nodeTextIndex - 1).isNewline()) { 449 return isAfterLBrace(nodeText, nodeTextIndex - 1); 450 } 451 return false; 452 } 453 454 /** 455 * If we are at the beginning of a line, with just spaces or tabs before us we should force the space to be 456 * the same as the indentation. 457 */ 458 private int considerEnforcingIndentation(NodeText nodeText, int nodeTextIndex) { 459 boolean hasOnlyWsBefore = true; 460 for (int i=nodeTextIndex; i >= 0 && hasOnlyWsBefore && i < nodeText.getElements().size(); i--) { 461 if (nodeText.getElements().get(i).isNewline()) { 462 break; 463 } 464 if (!nodeText.getElements().get(i).isSpaceOrTab()) { 465 hasOnlyWsBefore = false; 466 } 467 } 468 if (hasOnlyWsBefore) { 469 for (int i=nodeTextIndex; i >= 0 && i < nodeText.getElements().size(); i--) { 470 if (nodeText.getElements().get(i).isNewline()) { 471 break; 472 } 473 nodeText.removeElement(i); 474 } 475 } 476 return nodeTextIndex; 477 } 478 479 /** 480 * Node that we have calculate the Difference we can apply to a concrete NodeText, modifying it according 481 * to the difference (adding and removing the elements provided). 482 */ 483 void apply(NodeText nodeText, Node node) { 484 if (nodeText == null) { 485 throw new NullPointerException(); 486 } 487 boolean addedIndentation = false; 488 List<TokenTextElement> indentation = LexicalPreservingPrinter.findIndentation(node); 489 int diffIndex = 0; 490 int nodeTextIndex = 0; 491 do { 492 if (diffIndex < this.elements.size() && nodeTextIndex >= nodeText.getElements().size()) { 493 DifferenceElement diffEl = elements.get(diffIndex); 494 if (diffEl instanceof Kept) { 495 Kept kept = (Kept) diffEl; 496 if (kept.element instanceof CsmToken) { 497 CsmToken csmToken = (CsmToken) kept.element; 498 if (TokenTypes.isWhitespaceOrComment(csmToken.getTokenType())) { 499 diffIndex++; 500 } else { 501 throw new IllegalStateException("Cannot keep element because we reached the end of nodetext: " 502 + nodeText + ". Difference: " + this); 503 } 504 } else { 505 throw new IllegalStateException("Cannot keep element because we reached the end of nodetext: " 506 + nodeText + ". Difference: " + this); 507 } 508 } else if (diffEl instanceof Added) { 509 nodeText.addElement(nodeTextIndex, toTextElement(((Added) diffEl).element)); 510 nodeTextIndex++; 511 diffIndex++; 512 } else { 513 throw new UnsupportedOperationException(diffEl.getClass().getSimpleName()); 514 } 515 } else if (diffIndex >= this.elements.size() && nodeTextIndex < nodeText.getElements().size()) { 516 TextElement nodeTextEl = nodeText.getElements().get(nodeTextIndex); 517 if (nodeTextEl.isWhiteSpaceOrComment()) { 518 nodeTextIndex++; 519 } else { 520 throw new UnsupportedOperationException("NodeText: " + nodeText + ". Difference: " 521 + this + " " + nodeTextEl); 522 } 523 } else { 524 DifferenceElement diffEl = elements.get(diffIndex); 525 TextElement nodeTextEl = nodeText.getElements().get(nodeTextIndex); 526 if (diffEl instanceof Added) { 527 CsmElement addedElement = ((Added) diffEl).element; 528 if (addedElement instanceof CsmIndent) { 529 for (int i=0;i<STANDARD_INDENTATION_SIZE;i++){ 530 indentation.add(new TokenTextElement(GeneratedJavaParserConstants.SPACE)); 531 } 532 addedIndentation = true; 533 diffIndex++; 534 continue; 535 } 536 if (addedElement instanceof CsmUnindent) { 537 for (int i=0;i<STANDARD_INDENTATION_SIZE && !indentation.isEmpty();i++){ 538 indentation.remove(indentation.size() - 1); 539 } 540 addedIndentation = false; 541 diffIndex++; 542 continue; 543 } 544 TextElement textElement = toTextElement(addedElement); 545 boolean used = false; 546 if (nodeTextIndex > 0 && nodeText.getElements().get(nodeTextIndex - 1).isNewline()) { 547 for (TextElement e : processIndentation(indentation, nodeText.getElements().subList(0, nodeTextIndex - 1))) { 548 nodeText.addElement(nodeTextIndex++, e); 549 } 550 } else if (isAfterLBrace(nodeText, nodeTextIndex) && !isAReplacement(diffIndex)) { 551 if (textElement.isNewline()) { 552 used = true; 553 } 554 nodeText.addElement(nodeTextIndex++, new TokenTextElement(TokenTypes.eolTokenKind())); 555 // This remove the space in "{ }" when adding a new line 556 while (nodeText.getElements().get(nodeTextIndex).isSpaceOrTab()) { 557 nodeText.getElements().remove(nodeTextIndex); 558 } 559 for (TextElement e : processIndentation(indentation, nodeText.getElements().subList(0, nodeTextIndex - 1))) { 560 nodeText.addElement(nodeTextIndex++, e); 561 } 562 // Indentation is painful... 563 // Sometimes we want to force indentation: this is the case when indentation was expected but 564 // was actually not there. For example if we have "{ }" we would expect indentation but it is 565 // not there, so when adding new elements we force it. However if the indentation has been 566 // inserted by us in this transformation we do not want to insert it again 567 if (!addedIndentation) { 568 for (TextElement e : indentationBlock()) { 569 nodeText.addElement(nodeTextIndex++, e); 570 } 571 } 572 } 573 if (!used) { 574 nodeText.addElement(nodeTextIndex, textElement); 575 nodeTextIndex++; 576 } 577 if (textElement.isNewline()) { 578 boolean followedByUnindent = (diffIndex + 1) < elements.size() 579 && elements.get(diffIndex + 1).isAdded() 580 && elements.get(diffIndex + 1).getElement() instanceof CsmUnindent; 581 nodeTextIndex = adjustIndentation(indentation, nodeText, nodeTextIndex, followedByUnindent/* && !addedIndentation*/); 582 } 583 diffIndex++; 584 } else if (diffEl instanceof Kept) { 585 Kept kept = (Kept)diffEl; 586 if (nodeTextEl.isComment()) { 587 nodeTextIndex++; 588 } else if ((kept.element instanceof CsmChild) && nodeTextEl instanceof ChildTextElement) { 589 diffIndex++; 590 nodeTextIndex++; 591 } else if ((kept.element instanceof CsmChild) && nodeTextEl instanceof TokenTextElement) { 592 if (nodeTextEl.isWhiteSpaceOrComment()) { 593 nodeTextIndex++; 594 } else { 595 if (kept.element instanceof CsmChild) { 596 CsmChild keptChild = (CsmChild)kept.element; 597 if (keptChild.getChild() instanceof PrimitiveType) { 598 nodeTextIndex++; 599 diffIndex++; 600 } else { 601 throw new UnsupportedOperationException("kept " + kept.element + " vs " + nodeTextEl); 602 } 603 } else { 604 throw new UnsupportedOperationException("kept " + kept.element + " vs " + nodeTextEl); 605 } 606 } 607 } else if ((kept.element instanceof CsmToken) && nodeTextEl instanceof TokenTextElement) { 608 CsmToken csmToken = (CsmToken) kept.element; 609 TokenTextElement nodeTextToken = (TokenTextElement) nodeTextEl; 610 if (csmToken.getTokenType() == nodeTextToken.getTokenKind()) { 611 nodeTextIndex++; 612 diffIndex++; 613 } else if (TokenTypes.isWhitespaceOrComment(csmToken.getTokenType())) { 614 diffIndex++; 615 } else if (nodeTextToken.isWhiteSpaceOrComment()) { 616 nodeTextIndex++; 617 } else { 618 throw new UnsupportedOperationException("Csm token " + csmToken + " NodeText TOKEN " + nodeTextToken); 619 } 620 } else if ((kept.element instanceof CsmToken) && ((CsmToken) kept.element).isWhiteSpace()) { 621 diffIndex++; 622 } else if (kept.element instanceof CsmIndent) { 623 // Nothing to do 624 diffIndex++; 625 } else if (kept.element instanceof CsmUnindent) { 626 // Nothing to do, beside considering indentation 627 diffIndex++; 628 for (int i = 0; i < STANDARD_INDENTATION_SIZE && nodeTextIndex >= 1 && nodeText.getTextElement(nodeTextIndex - 1).isSpaceOrTab(); i++) { 629 nodeText.removeElement(--nodeTextIndex); 630 } 631 } else { 632 throw new UnsupportedOperationException("kept " + kept.element + " vs " + nodeTextEl); 633 } 634 } else if (diffEl instanceof Removed) { 635 Removed removed = (Removed)diffEl; 636 if ((removed.element instanceof CsmChild) && nodeTextEl instanceof ChildTextElement) { 637 ChildTextElement actualChild = (ChildTextElement)nodeTextEl; 638 if (actualChild.isComment()) { 639 CsmChild csmChild = (CsmChild)removed.element; 640 // We expected to remove a proper node but we found a comment in between. 641 // If the comment is associated to the node we want to remove we remove it as well, otherwise we keep it 642 Comment comment = (Comment)actualChild.getChild(); 643 if (!comment.isOrphan() && comment.getCommentedNode().isPresent() && comment.getCommentedNode().get().equals(csmChild.getChild())) { 644 nodeText.removeElement(nodeTextIndex); 645 } else { 646 nodeTextIndex++; 647 } 648 } else { 649 nodeText.removeElement(nodeTextIndex); 650 if (nodeTextIndex < nodeText.getElements().size() && nodeText.getElements().get(nodeTextIndex).isNewline()) { 651 nodeTextIndex = considerCleaningTheLine(nodeText, nodeTextIndex); 652 } else { 653 if (diffIndex + 1 >= this.getElements().size() || !(this.getElements().get(diffIndex + 1) instanceof Added)) { 654 nodeTextIndex = considerEnforcingIndentation(nodeText, nodeTextIndex); 655 } 656 // If in front we have one space and before also we had space let's drop one space 657 if (nodeText.getElements().size() > nodeTextIndex && nodeTextIndex > 0) { 658 if (nodeText.getElements().get(nodeTextIndex).isWhiteSpace() 659 && nodeText.getElements().get(nodeTextIndex - 1).isWhiteSpace()) { 660 // However we do not want to do that when we are about to adding or removing elements 661 if ((diffIndex + 1) == this.elements.size() || (elements.get(diffIndex + 1) instanceof Kept)) { 662 nodeText.getElements().remove(nodeTextIndex--); 663 } 664 } 665 } 666 } 667 diffIndex++; 668 } 669 } else if ((removed.element instanceof CsmToken) && nodeTextEl instanceof TokenTextElement 670 && ((CsmToken)removed.element).getTokenType() == ((TokenTextElement)nodeTextEl).getTokenKind()) { 671 nodeText.removeElement(nodeTextIndex); 672 diffIndex++; 673 } else if (nodeTextEl instanceof TokenTextElement 674 && nodeTextEl.isWhiteSpaceOrComment()) { 675 nodeTextIndex++; 676 } else if (removed.element instanceof CsmChild 677 && ((CsmChild)removed.element).getChild() instanceof PrimitiveType) { 678 if (isPrimitiveType(nodeTextEl)) { 679 nodeText.removeElement(nodeTextIndex); 680 diffIndex++; 681 } else { 682 throw new UnsupportedOperationException("removed " + removed.element + " vs " + nodeTextEl); 683 } 684 } else if (removed.element instanceof CsmToken && ((CsmToken)removed.element).isWhiteSpace()) { 685 diffIndex++; 686 } else if (nodeTextEl.isWhiteSpace()) { 687 nodeTextIndex++; 688 } else { 689 throw new UnsupportedOperationException("removed " + removed.element + " vs " + nodeTextEl); 690 } 691 } else if (diffEl instanceof Reshuffled) { 692 693 // First, let's see how many tokens we need to attribute to the previous version of the of the CsmMix 694 Reshuffled reshuffled = (Reshuffled)diffEl; 695 CsmMix elementsFromPreviousOrder = reshuffled.previousOrder; 696 CsmMix elementsFromNextOrder = reshuffled.element; 697 698 // This contains indexes from elementsFromNextOrder to indexes from elementsFromPreviousOrder 699 Map<Integer, Integer> correspondanceBetweenNextOrderAndPreviousOrder = new HashMap<>(); 700 for (int ni=0;ni<elementsFromNextOrder.getElements().size();ni++) { 701 boolean found = false; 702 CsmElement ne = elementsFromNextOrder.getElements().get(ni); 703 for (int pi=0;pi<elementsFromPreviousOrder.getElements().size() && !found;pi++) { 704 CsmElement pe = elementsFromPreviousOrder.getElements().get(pi); 705 if (!correspondanceBetweenNextOrderAndPreviousOrder.values().contains(pi) 706 && matching(ne, pe)) { 707 found = true; 708 correspondanceBetweenNextOrderAndPreviousOrder.put(ni, pi); 709 } 710 } 711 } 712 713 // We now find out which Node Text elements corresponds to the elements in the original CSM 714 final int startNodeTextIndex = nodeTextIndex; 715 final Set<Integer> usedIndexes = new HashSet<>(); 716 List<Integer> nodeTextIndexOfPreviousElements = elementsFromPreviousOrder.getElements().stream() 717 .map(it -> findIndexOfCorrespondingNodeTextElement(it, nodeText, startNodeTextIndex, usedIndexes, node)) 718 .collect(Collectors.toList()); 719 Map<Integer, Integer> nodeTextIndexToPreviousCSMIndex = new HashMap<>(); 720 for (int i=0;i<nodeTextIndexOfPreviousElements.size();i++) { 721 int value = nodeTextIndexOfPreviousElements.get(i); 722 if (value != -1) { 723 nodeTextIndexToPreviousCSMIndex.put(value, i); 724 } 725 } 726 int lastNodeTextIndex = nodeTextIndexOfPreviousElements.stream().max(Integer::compareTo).orElse(-1); 727 728 // Elements to be added at the end 729 List<CsmElement> elementsToBeAddedAtTheEnd = new LinkedList<>(); 730 Map<Integer, List<CsmElement>> elementsToAddBeforeGivenOriginalCSMElement = new HashMap<>(); 731 for (int ni=0;ni<elementsFromNextOrder.getElements().size();ni++) { 732 // If it has a mapping, then it is kept 733 if (!correspondanceBetweenNextOrderAndPreviousOrder.containsKey(ni)) { 734 // Ok, it is something new. Where to put it? Let's see what is the first following 735 // element that has a mapping 736 int originalCsmIndex = -1; 737 for (int nj=ni + 1;nj<elementsFromNextOrder.getElements().size() && originalCsmIndex==-1;nj++) { 738 if (correspondanceBetweenNextOrderAndPreviousOrder.containsKey(nj)) { 739 originalCsmIndex = correspondanceBetweenNextOrderAndPreviousOrder.get(nj); 740 if (!elementsToAddBeforeGivenOriginalCSMElement.containsKey(originalCsmIndex)){ 741 elementsToAddBeforeGivenOriginalCSMElement.put(originalCsmIndex, new LinkedList<>()); 742 } 743 elementsToAddBeforeGivenOriginalCSMElement.get(originalCsmIndex).add(elementsFromNextOrder.getElements().get(ni)); 744 } 745 } 746 // it does not preceed anything, so it goes at the end 747 if (originalCsmIndex == -1) { 748 elementsToBeAddedAtTheEnd.add(elementsFromNextOrder.getElements().get(ni)); 749 } 750 } 751 } 752 753 // We go over the original node text elements, in the order they appear in the NodeText. 754 // Considering an original node text element (ONE) 755 // * we verify if it corresponds to a CSM element. If it does not we just move on, otherwise 756 // we find the correspond OCE (Original CSM Element) 757 // * we first add new elements that are marked to be added before OCE 758 // * if OCE is marked to be present also in the "after" CSM we add a kept element, 759 // otherwise we add a removed element 760 761 this.getElements().remove(diffIndex); 762 int diffElIterator = diffIndex; 763 if (lastNodeTextIndex != -1) { 764 for (int ntIndex = startNodeTextIndex; ntIndex<=lastNodeTextIndex; ntIndex++) { 765 766 if (nodeTextIndexToPreviousCSMIndex.containsKey(ntIndex)) { 767 int indexOfOriginalCSMElement = nodeTextIndexToPreviousCSMIndex.get(ntIndex); 768 if (elementsToAddBeforeGivenOriginalCSMElement.containsKey(indexOfOriginalCSMElement)) { 769 for (CsmElement elementToAdd : elementsToAddBeforeGivenOriginalCSMElement.get(indexOfOriginalCSMElement)) { 770 elements.add(diffElIterator++, new Added(elementToAdd)); 771 } 772 } 773 774 CsmElement originalCSMElement = elementsFromPreviousOrder.getElements().get(indexOfOriginalCSMElement); 775 boolean toBeKept = correspondanceBetweenNextOrderAndPreviousOrder.containsValue(indexOfOriginalCSMElement); 776 if (toBeKept) { 777 elements.add(diffElIterator++, new Kept(originalCSMElement)); 778 } else { 779 elements.add(diffElIterator++, new Removed(originalCSMElement)); 780 } 781 } 782 // else we have a simple node text element, without associated csm element, just keep ignore it 783 } 784 } 785 786 // Finally we look for the remaining new elements that were not yet added and 787 // add all of them 788 for (CsmElement elementToAdd : elementsToBeAddedAtTheEnd) { 789 elements.add(diffElIterator++, new Added(elementToAdd)); 790 } 791 } else { 792 throw new UnsupportedOperationException("" + diffEl + " vs " + nodeTextEl); 793 } 794 } 795 } while (diffIndex < this.elements.size() || nodeTextIndex < nodeText.getElements().size()); 796 } 797 798 private int findIndexOfCorrespondingNodeTextElement(CsmElement csmElement, NodeText nodeText, int startIndex, Set<Integer> usedIndexes, Node node) { 799 for (int i=startIndex;i<nodeText.getElements().size();i++){ 800 if (!usedIndexes.contains(i)) { 801 TextElement textElement = nodeText.getTextElement(i); 802 if (csmElement instanceof CsmToken) { 803 CsmToken csmToken = (CsmToken)csmElement; 804 if (textElement instanceof TokenTextElement) { 805 TokenTextElement tokenTextElement = (TokenTextElement)textElement; 806 if (tokenTextElement.getTokenKind() == csmToken.getTokenType() && tokenTextElement.getText().equals(csmToken.getContent(node))) { 807 usedIndexes.add(i); 808 return i; 809 } 810 } 811 } else if (csmElement instanceof CsmChild) { 812 CsmChild csmChild = (CsmChild)csmElement; 813 if (textElement instanceof ChildTextElement) { 814 ChildTextElement childTextElement = (ChildTextElement)textElement; 815 if (childTextElement.getChild() == csmChild.getChild()) { 816 usedIndexes.add(i); 817 return i; 818 } 819 } 820 } else { 821 throw new UnsupportedOperationException(); 822 } 823 } 824 } 825 return -1; 826 } 827 828 private int adjustIndentation(List<TokenTextElement> indentation, NodeText nodeText, int nodeTextIndex, boolean followedByUnindent) { 829 List<TextElement> indentationAdj = processIndentation(indentation, nodeText.getElements().subList(0, nodeTextIndex - 1)); 830 if (nodeTextIndex < nodeText.getElements().size() && nodeText.getElements().get(nodeTextIndex).isToken(RBRACE)) { 831 indentationAdj = indentationAdj.subList(0, indentationAdj.size() - Math.min(STANDARD_INDENTATION_SIZE, indentationAdj.size())); 832 } else if (followedByUnindent) { 833 indentationAdj = indentationAdj.subList(0, Math.max(0, indentationAdj.size() - STANDARD_INDENTATION_SIZE)); 834 } 835 for (TextElement e : indentationAdj) { 836 if ((nodeTextIndex<nodeText.getElements().size()) && nodeText.getElements().get(nodeTextIndex).isSpaceOrTab()) { 837 nodeTextIndex++; 838 } else { 839 nodeText.getElements().add(nodeTextIndex++, e); 840 } 841 } 842 return nodeTextIndex; 843 } 844 845 private boolean isAReplacement(int diffIndex) { 846 return (diffIndex > 0) && getElements().get(diffIndex) instanceof Added && getElements().get(diffIndex - 1) instanceof Removed; 847 } 848 849 private boolean isPrimitiveType(TextElement textElement) { 850 if (textElement instanceof TokenTextElement) { 851 TokenTextElement tokenTextElement = (TokenTextElement)textElement; 852 int tokenKind = tokenTextElement.getTokenKind(); 853 return tokenKind == BYTE 854 || tokenKind == CHAR 855 || tokenKind == SHORT 856 || tokenKind == INT 857 || tokenKind == LONG 858 || tokenKind == FLOAT 859 || tokenKind == DOUBLE; 860 } else { 861 return false; 862 } 863 } 864 865 private long cost() { 866 return elements.stream().filter(e -> !(e instanceof Kept)).count(); 867 } 868 869 @Override 870 public String toString() { 871 return "Difference{" + elements + '}'; 872 } 873 874 public List<DifferenceElement> getElements() { 875 return elements; 876 } 877 878 /** 879 * Remove from the difference all the elements related to indentation. 880 * This is mainly intended for test purposes. 881 */ 882 void removeIndentationElements() { 883 elements.removeIf(el -> el.getElement() instanceof CsmIndent || el.getElement() instanceof CsmUnindent); 884 } 885 } 886