1 package com.github.javaparser.printer.lexicalpreservation; 2 3 import com.github.javaparser.ast.Node; 4 import com.github.javaparser.ast.body.VariableDeclarator; 5 import com.github.javaparser.ast.type.Type; 6 import com.github.javaparser.printer.concretesyntaxmodel.*; 7 import com.github.javaparser.printer.lexicalpreservation.LexicalDifferenceCalculator.CsmChild; 8 9 import java.util.*; 10 11 class DifferenceElementCalculator { matching(CsmElement a, CsmElement b)12 static boolean matching(CsmElement a, CsmElement b) { 13 if (a instanceof CsmChild) { 14 if (b instanceof CsmChild) { 15 CsmChild childA = (CsmChild) a; 16 CsmChild childB = (CsmChild) b; 17 return childA.getChild().equals(childB.getChild()); 18 } else if (b instanceof CsmToken) { 19 return false; 20 } else if (b instanceof CsmIndent) { 21 return false; 22 } else if (b instanceof CsmUnindent) { 23 return false; 24 } else { 25 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 26 } 27 } else if (a instanceof CsmToken) { 28 if (b instanceof CsmToken) { 29 CsmToken childA = (CsmToken)a; 30 CsmToken childB = (CsmToken)b; 31 return childA.getTokenType() == childB.getTokenType(); 32 } else if (b instanceof CsmChild) { 33 return false; 34 } else if (b instanceof CsmIndent) { 35 return false; 36 } else if (b instanceof CsmUnindent) { 37 return false; 38 } else { 39 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 40 } 41 } else if (a instanceof CsmIndent) { 42 return b instanceof CsmIndent; 43 } else if (a instanceof CsmUnindent) { 44 return b instanceof CsmUnindent; 45 } 46 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 47 } 48 replacement(CsmElement a, CsmElement b)49 private static boolean replacement(CsmElement a, CsmElement b) { 50 if (a instanceof CsmIndent || b instanceof CsmIndent || a instanceof CsmUnindent || b instanceof CsmUnindent) { 51 return false; 52 } 53 if (a instanceof CsmChild) { 54 if (b instanceof CsmChild) { 55 CsmChild childA = (CsmChild) a; 56 CsmChild childB = (CsmChild) b; 57 return childA.getChild().getClass().equals(childB.getChild().getClass()); 58 } else if (b instanceof CsmToken) { 59 return false; 60 } else { 61 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 62 } 63 } else if (a instanceof CsmToken) { 64 if (b instanceof CsmToken) { 65 CsmToken childA = (CsmToken)a; 66 CsmToken childB = (CsmToken)b; 67 return childA.getTokenType() == childB.getTokenType(); 68 } else if (b instanceof CsmChild) { 69 return false; 70 } 71 } 72 throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); 73 } 74 75 /** 76 * Find the positions of all the given children. 77 */ findChildrenPositions(LexicalDifferenceCalculator.CalculatedSyntaxModel calculatedSyntaxModel)78 private static Map<Node, Integer> findChildrenPositions(LexicalDifferenceCalculator.CalculatedSyntaxModel calculatedSyntaxModel) { 79 Map<Node, Integer> positions = new HashMap<>(); 80 for (int i=0;i<calculatedSyntaxModel.elements.size();i++) { 81 CsmElement element = calculatedSyntaxModel.elements.get(i); 82 if (element instanceof CsmChild) { 83 positions.put(((CsmChild)element).getChild(), i); 84 } 85 } 86 return positions; 87 } 88 89 /** 90 * Calculate the Difference between two CalculatedSyntaxModel elements, determining which elements were kept, 91 * which were added and which were removed. 92 */ calculate(LexicalDifferenceCalculator.CalculatedSyntaxModel original, LexicalDifferenceCalculator.CalculatedSyntaxModel after)93 static List<DifferenceElement> calculate(LexicalDifferenceCalculator.CalculatedSyntaxModel original, LexicalDifferenceCalculator.CalculatedSyntaxModel after) { 94 // For performance reasons we use the positions of matching children 95 // to guide the calculation of the difference 96 // 97 // Suppose we have: 98 // qwerty[A]uiop 99 // qwer[A]uiop 100 // 101 // with [A] being a child and lowercase letters being tokens 102 // 103 // We would calculate the Difference between "qwerty" and "qwer" then we know the A is kept, and then we 104 // would calculate the difference between "uiop" and "uiop" 105 106 Map<Node, Integer> childrenInOriginal = findChildrenPositions(original); 107 Map<Node, Integer> childrenInAfter = findChildrenPositions(after); 108 109 List<Node> commonChildren = new LinkedList<>(childrenInOriginal.keySet()); 110 commonChildren.retainAll(childrenInAfter.keySet()); 111 commonChildren.sort(Comparator.comparingInt(childrenInOriginal::get)); 112 113 List<DifferenceElement> elements = new LinkedList<>(); 114 115 int originalIndex = 0; 116 int afterIndex = 0; 117 int commonChildrenIndex = 0; 118 while (commonChildrenIndex < commonChildren.size()) { 119 Node child = commonChildren.get(commonChildrenIndex++); 120 int posOfNextChildInOriginal = childrenInOriginal.get(child); 121 int posOfNextChildInAfter = childrenInAfter.get(child); 122 if (originalIndex < posOfNextChildInOriginal || afterIndex < posOfNextChildInAfter) { 123 elements.addAll(calculateImpl(original.sub(originalIndex, posOfNextChildInOriginal), after.sub(afterIndex, posOfNextChildInAfter))); 124 } 125 elements.add(new Kept(new CsmChild(child))); 126 originalIndex = posOfNextChildInOriginal + 1; 127 afterIndex = posOfNextChildInAfter + 1; 128 } 129 130 if (originalIndex < original.elements.size() || afterIndex < after.elements.size()) { 131 elements.addAll(calculateImpl(original.sub(originalIndex, original.elements.size()), after.sub(afterIndex, after.elements.size()))); 132 } 133 return elements; 134 } 135 considerRemoval(NodeText nodeTextForChild, List<DifferenceElement> elements)136 private static void considerRemoval(NodeText nodeTextForChild, List<DifferenceElement> elements) { 137 for (TextElement el : nodeTextForChild.getElements()) { 138 if (el instanceof ChildTextElement) { 139 ChildTextElement cte = (ChildTextElement) el; 140 considerRemoval(LexicalPreservingPrinter.getOrCreateNodeText(cte.getChild()), elements); 141 } else if (el instanceof TokenTextElement) { 142 TokenTextElement tte = (TokenTextElement) el; 143 elements.add(new Removed(new CsmToken(tte.getTokenKind(), tte.getText()))); 144 } else { 145 throw new UnsupportedOperationException(el.toString()); 146 } 147 } 148 } 149 considerRemoval(CsmElement removedElement, int originalIndex, List<DifferenceElement> elements)150 private static int considerRemoval(CsmElement removedElement, int originalIndex, List<DifferenceElement> elements) { 151 boolean dealtWith = false; 152 if (removedElement instanceof CsmChild) { 153 CsmChild removedChild = (CsmChild) removedElement; 154 if (removedChild.getChild() instanceof Type && removedChild.getChild().getParentNode().isPresent() && 155 removedChild.getChild().getParentNode().get() instanceof VariableDeclarator) { 156 NodeText nodeTextForChild = LexicalPreservingPrinter.getOrCreateNodeText(removedChild.getChild()); 157 considerRemoval(nodeTextForChild, elements); 158 originalIndex++; 159 dealtWith = true; 160 } 161 } 162 if (!dealtWith) { 163 elements.add(new Removed(removedElement)); 164 originalIndex++; 165 } 166 return originalIndex; 167 } 168 calculateImpl(LexicalDifferenceCalculator.CalculatedSyntaxModel original, LexicalDifferenceCalculator.CalculatedSyntaxModel after)169 private static List<DifferenceElement> calculateImpl(LexicalDifferenceCalculator.CalculatedSyntaxModel original, 170 LexicalDifferenceCalculator.CalculatedSyntaxModel after) { 171 List<DifferenceElement> elements = new LinkedList<>(); 172 173 int originalIndex = 0; 174 int afterIndex = 0; 175 176 // We move through the two CalculatedSyntaxModel, moving both forward when we have a match 177 // and moving just one side forward when we have an element kept or removed 178 179 do { 180 if (originalIndex < original.elements.size() && afterIndex >= after.elements.size()) { 181 CsmElement removedElement = original.elements.get(originalIndex); 182 originalIndex = considerRemoval(removedElement, originalIndex, elements); 183 } else if (originalIndex >= original.elements.size() && afterIndex < after.elements.size()) { 184 elements.add(new Added(after.elements.get(afterIndex))); 185 afterIndex++; 186 } else { 187 CsmElement nextOriginal = original.elements.get(originalIndex); 188 CsmElement nextAfter = after.elements.get(afterIndex); 189 190 if ((nextOriginal instanceof CsmMix) && (nextAfter instanceof CsmMix)) { 191 if (((CsmMix) nextAfter).getElements().equals(((CsmMix) nextOriginal).getElements())) { 192 // No reason to deal with a reshuffled, we are just going to keep everything as it is 193 ((CsmMix) nextAfter).getElements().forEach(el -> elements.add(new Kept(el))); 194 } else { 195 elements.add(new Reshuffled((CsmMix)nextOriginal, (CsmMix)nextAfter)); 196 } 197 originalIndex++; 198 afterIndex++; 199 } else if (matching(nextOriginal, nextAfter)) { 200 elements.add(new Kept(nextOriginal)); 201 originalIndex++; 202 afterIndex++; 203 } else if (replacement(nextOriginal, nextAfter)) { 204 originalIndex = considerRemoval(nextOriginal, originalIndex, elements); 205 elements.add(new Added(nextAfter)); 206 afterIndex++; 207 } else { 208 // We can try to remove the element or add it and look which one leads to the lower difference 209 List<DifferenceElement> addingElements = calculate(original.from(originalIndex), after.from(afterIndex + 1)); 210 List<DifferenceElement> removingElements = null; 211 if (cost(addingElements) > 0) { 212 removingElements = calculate(original.from(originalIndex + 1), after.from(afterIndex)); 213 } 214 215 if (removingElements == null || cost(removingElements) > cost(addingElements)) { 216 elements.add(new Added(nextAfter)); 217 afterIndex++; 218 } else { 219 elements.add(new Removed(nextOriginal)); 220 originalIndex++; 221 } 222 } 223 } 224 } while (originalIndex < original.elements.size() || afterIndex < after.elements.size()); 225 226 return elements; 227 } 228 cost(List<DifferenceElement> elements)229 private static long cost(List<DifferenceElement> elements) { 230 return elements.stream().filter(e -> !(e instanceof Kept)).count(); 231 } 232 233 234 /** 235 * Remove from the difference all the elements related to indentation. 236 * This is mainly intended for test purposes. 237 */ removeIndentationElements(List<DifferenceElement> elements)238 static void removeIndentationElements(List<DifferenceElement> elements) { 239 elements.removeIf(el -> el.getElement() instanceof CsmIndent || el.getElement() instanceof CsmUnindent); 240 } 241 } 242