| 1 | /* |
|---|---|
| 2 | * Copyright (C) 2007-2010 Júlio Vilmar Gesser. |
| 3 | * Copyright (C) 2011, 2013-2020 The JavaParser Team. |
| 4 | * |
| 5 | * This file is part of JavaParser. |
| 6 | * |
| 7 | * JavaParser can be used either under the terms of |
| 8 | * a) the GNU Lesser General Public License as published by |
| 9 | * the Free Software Foundation, either version 3 of the License, or |
| 10 | * (at your option) any later version. |
| 11 | * b) the terms of the Apache License |
| 12 | * |
| 13 | * You should have received a copy of both licenses in LICENCE.LGPL and |
| 14 | * LICENCE.APACHE. Please refer to those files for details. |
| 15 | * |
| 16 | * JavaParser is distributed in the hope that it will be useful, |
| 17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 19 | * GNU Lesser General Public License for more details. |
| 20 | */ |
| 21 | |
| 22 | package com.github.javaparser.printer.lexicalpreservation; |
| 23 | |
| 24 | import java.util.ArrayList; |
| 25 | import java.util.LinkedList; |
| 26 | import java.util.List; |
| 27 | |
| 28 | import com.github.javaparser.ast.Node; |
| 29 | import com.github.javaparser.ast.body.VariableDeclarator; |
| 30 | import com.github.javaparser.ast.type.Type; |
| 31 | import com.github.javaparser.printer.concretesyntaxmodel.CsmElement; |
| 32 | import com.github.javaparser.printer.concretesyntaxmodel.CsmIndent; |
| 33 | import com.github.javaparser.printer.concretesyntaxmodel.CsmMix; |
| 34 | import com.github.javaparser.printer.concretesyntaxmodel.CsmToken; |
| 35 | import com.github.javaparser.printer.concretesyntaxmodel.CsmUnindent; |
| 36 | import com.github.javaparser.printer.lexicalpreservation.LexicalDifferenceCalculator.CsmChild; |
| 37 | |
| 38 | class DifferenceElementCalculator { |
| 39 | |
| 40 | // internally keep track of a node position in a List<CsmElement> |
| 41 | public static class ChildPositionInfo { |
| 42 | Node node; |
| 43 | Integer position; |
| 44 | ChildPositionInfo(Node node, Integer position) { |
| 45 | this.node = node; |
| 46 | this.position = position; |
| 47 | } |
| 48 | @Override |
| 49 | public boolean equals(Object other) { |
| 50 | if ( other == null || !(other instanceof ChildPositionInfo)) |
| 51 | return false; |
| 52 | ChildPositionInfo cpi = (ChildPositionInfo)other; |
| 53 | // verify that the node content and the position are equal |
| 54 | // because we can have nodes with the same content but in different lines |
| 55 | // in this case we consider that nodes are not equals |
| 56 | return this.node.equals(cpi.node) |
| 57 | && this.node.getRange().isPresent() && cpi.node.getRange().isPresent() |
| 58 | && this.node.getRange().get().contains(cpi.node.getRange().get()); |
| 59 | } |
| 60 | @Override |
| 61 | public int hashCode() { |
| 62 | return node.hashCode() + position.hashCode(); |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | static boolean matching(CsmElement a, CsmElement b) { |
| 67 | if (a instanceof CsmChild) { |
| 68 | if (b instanceof CsmChild) { |
| 69 | CsmChild childA = (CsmChild) a; |
| 70 | CsmChild childB = (CsmChild) b; |
| 71 | return childA.getChild().equals(childB.getChild()); |
| 72 | } else if (b instanceof CsmToken) { |
| 73 | return false; |
| 74 | } else if (b instanceof CsmIndent) { |
| 75 | return false; |
| 76 | } else if (b instanceof CsmUnindent) { |
| 77 | return false; |
| 78 | } else { |
| 79 | throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); |
| 80 | } |
| 81 | } else if (a instanceof CsmToken) { |
| 82 | if (b instanceof CsmToken) { |
| 83 | // fix #2382: |
| 84 | // Tokens are described by their type AND their content |
| 85 | // and TokenContentCalculator. By using .equals(), all |
| 86 | // three values are compared. |
| 87 | CsmToken childA = (CsmToken)a; |
| 88 | CsmToken childB = (CsmToken)b; |
| 89 | return childA.equals(childB); |
| 90 | } else if (b instanceof CsmChild) { |
| 91 | return false; |
| 92 | } else if (b instanceof CsmIndent) { |
| 93 | return false; |
| 94 | } else if (b instanceof CsmUnindent) { |
| 95 | return false; |
| 96 | } else { |
| 97 | throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); |
| 98 | } |
| 99 | } else if (a instanceof CsmIndent) { |
| 100 | return b instanceof CsmIndent; |
| 101 | } else if (a instanceof CsmUnindent) { |
| 102 | return b instanceof CsmUnindent; |
| 103 | } |
| 104 | throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); |
| 105 | } |
| 106 | |
| 107 | private static boolean replacement(CsmElement a, CsmElement b) { |
| 108 | if (a instanceof CsmIndent || b instanceof CsmIndent || a instanceof CsmUnindent || b instanceof CsmUnindent) { |
| 109 | return false; |
| 110 | } |
| 111 | if (a instanceof CsmChild) { |
| 112 | if (b instanceof CsmChild) { |
| 113 | CsmChild childA = (CsmChild) a; |
| 114 | CsmChild childB = (CsmChild) b; |
| 115 | return childA.getChild().getClass().equals(childB.getChild().getClass()); |
| 116 | } else if (b instanceof CsmToken) { |
| 117 | return false; |
| 118 | } else { |
| 119 | throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); |
| 120 | } |
| 121 | } else if (a instanceof CsmToken) { |
| 122 | if (b instanceof CsmToken) { |
| 123 | CsmToken childA = (CsmToken)a; |
| 124 | CsmToken childB = (CsmToken)b; |
| 125 | return childA.getTokenType() == childB.getTokenType(); |
| 126 | } else if (b instanceof CsmChild) { |
| 127 | return false; |
| 128 | } |
| 129 | } |
| 130 | throw new UnsupportedOperationException(a.getClass().getSimpleName()+ " "+b.getClass().getSimpleName()); |
| 131 | } |
| 132 | |
| 133 | /** |
| 134 | * Find the positions of all the given children. |
| 135 | */ |
| 136 | private static List<ChildPositionInfo> findChildrenPositions(LexicalDifferenceCalculator.CalculatedSyntaxModel calculatedSyntaxModel) { |
| 137 | List<ChildPositionInfo> positions = new ArrayList<>(); |
| 138 | for (int i=0;i<calculatedSyntaxModel.elements.size();i++) { |
| 139 | CsmElement element = calculatedSyntaxModel.elements.get(i); |
| 140 | if (element instanceof CsmChild) { |
| 141 | positions.add(new ChildPositionInfo(((CsmChild)element).getChild(), i)); |
| 142 | } |
| 143 | } |
| 144 | return positions; |
| 145 | } |
| 146 | |
| 147 | /** |
| 148 | * Calculate the Difference between two CalculatedSyntaxModel elements, determining which elements were kept, |
| 149 | * which were added and which were removed. |
| 150 | */ |
| 151 | static List<DifferenceElement> calculate(LexicalDifferenceCalculator.CalculatedSyntaxModel original, LexicalDifferenceCalculator.CalculatedSyntaxModel after) { |
| 152 | // For performance reasons we use the positions of matching children |
| 153 | // to guide the calculation of the difference |
| 154 | // |
| 155 | // Suppose we have: |
| 156 | // qwerty[A]uiop |
| 157 | // qwer[A]uiop |
| 158 | // |
| 159 | // with [A] being a child and lowercase letters being tokens |
| 160 | // |
| 161 | // We would calculate the Difference between "qwerty" and "qwer" then we know the A is kept, and then we |
| 162 | // would calculate the difference between "uiop" and "uiop" |
| 163 | |
| 164 | List<ChildPositionInfo> childrenInOriginal = findChildrenPositions(original); |
| 165 | List<ChildPositionInfo> childrenInAfter = findChildrenPositions(after); |
| 166 | |
| 167 | List<ChildPositionInfo> commonChildren = new ArrayList<>(childrenInOriginal); |
| 168 | commonChildren.retainAll(childrenInAfter); |
| 169 | |
| 170 | List<DifferenceElement> elements = new LinkedList<>(); |
| 171 | |
| 172 | int originalIndex = 0; |
| 173 | int afterIndex = 0; |
| 174 | int commonChildrenIndex = 0; |
| 175 | while (commonChildrenIndex < commonChildren.size()) { |
| 176 | ChildPositionInfo child = commonChildren.get(commonChildrenIndex++); |
| 177 | // search the position of the node "child" in the original list of cms element |
| 178 | int posOfNextChildInOriginal = childrenInOriginal.stream().filter(i->i.equals(child)).map(i->i.position).findFirst().get(); |
| 179 | // search the position of the node "child" in the modified list of cms element |
| 180 | int posOfNextChildInAfter = childrenInAfter.stream().filter(i->i.equals(child)).map(i->i.position).findFirst().get(); |
| 181 | |
| 182 | if (originalIndex < posOfNextChildInOriginal || afterIndex < posOfNextChildInAfter) { |
| 183 | elements.addAll(calculateImpl(original.sub(originalIndex, posOfNextChildInOriginal), after.sub(afterIndex, posOfNextChildInAfter))); |
| 184 | } |
| 185 | elements.add(new Kept(new CsmChild(child.node))); |
| 186 | originalIndex = posOfNextChildInOriginal + 1; |
| 187 | afterIndex = posOfNextChildInAfter + 1; |
| 188 | } |
| 189 | |
| 190 | if (originalIndex < original.elements.size() || afterIndex < after.elements.size()) { |
| 191 | elements.addAll(calculateImpl(original.sub(originalIndex, original.elements.size()), after.sub(afterIndex, after.elements.size()))); |
| 192 | } |
| 193 | return elements; |
| 194 | } |
| 195 | |
| 196 | private static void considerRemoval(NodeText nodeTextForChild, List<DifferenceElement> elements) { |
| 197 | for (TextElement el : nodeTextForChild.getElements()) { |
| 198 | if (el instanceof ChildTextElement) { |
| 199 | ChildTextElement cte = (ChildTextElement) el; |
| 200 | considerRemoval(LexicalPreservingPrinter.getOrCreateNodeText(cte.getChild()), elements); |
| 201 | } else if (el instanceof TokenTextElement) { |
| 202 | TokenTextElement tte = (TokenTextElement) el; |
| 203 | elements.add(new Removed(new CsmToken(tte.getTokenKind(), tte.getText()))); |
| 204 | } else { |
| 205 | throw new UnsupportedOperationException(el.toString()); |
| 206 | } |
| 207 | } |
| 208 | } |
| 209 | |
| 210 | private static int considerRemoval(CsmElement removedElement, int originalIndex, List<DifferenceElement> elements) { |
| 211 | boolean dealtWith = false; |
| 212 | if (removedElement instanceof CsmChild) { |
| 213 | CsmChild removedChild = (CsmChild) removedElement; |
| 214 | if (removedChild.getChild() instanceof Type && removedChild.getChild().getParentNode().isPresent() && |
| 215 | removedChild.getChild().getParentNode().get() instanceof VariableDeclarator) { |
| 216 | NodeText nodeTextForChild = LexicalPreservingPrinter.getOrCreateNodeText(removedChild.getChild()); |
| 217 | considerRemoval(nodeTextForChild, elements); |
| 218 | originalIndex++; |
| 219 | dealtWith = true; |
| 220 | } |
| 221 | } |
| 222 | if (!dealtWith) { |
| 223 | elements.add(new Removed(removedElement)); |
| 224 | originalIndex++; |
| 225 | } |
| 226 | return originalIndex; |
| 227 | } |
| 228 | |
| 229 | private static List<DifferenceElement> calculateImpl(LexicalDifferenceCalculator.CalculatedSyntaxModel original, |
| 230 | LexicalDifferenceCalculator.CalculatedSyntaxModel after) { |
| 231 | List<DifferenceElement> elements = new LinkedList<>(); |
| 232 | |
| 233 | int originalIndex = 0; |
| 234 | int afterIndex = 0; |
| 235 | |
| 236 | // We move through the two CalculatedSyntaxModel, moving both forward when we have a match |
| 237 | // and moving just one side forward when we have an element kept or removed |
| 238 | |
| 239 | do { |
| 240 | if (originalIndex < original.elements.size() && afterIndex >= after.elements.size()) { |
| 241 | CsmElement removedElement = original.elements.get(originalIndex); |
| 242 | originalIndex = considerRemoval(removedElement, originalIndex, elements); |
| 243 | } else if (originalIndex >= original.elements.size() && afterIndex < after.elements.size()) { |
| 244 | elements.add(new Added(after.elements.get(afterIndex))); |
| 245 | afterIndex++; |
| 246 | } else { |
| 247 | CsmElement nextOriginal = original.elements.get(originalIndex); |
| 248 | CsmElement nextAfter = after.elements.get(afterIndex); |
| 249 | |
| 250 | if ((nextOriginal instanceof CsmMix) && (nextAfter instanceof CsmMix)) { |
| 251 | if (((CsmMix) nextAfter).getElements().equals(((CsmMix) nextOriginal).getElements())) { |
| 252 | // No reason to deal with a reshuffled, we are just going to keep everything as it is |
| 253 | ((CsmMix) nextAfter).getElements().forEach(el -> elements.add(new Kept(el))); |
| 254 | } else { |
| 255 | elements.add(new Reshuffled((CsmMix)nextOriginal, (CsmMix)nextAfter)); |
| 256 | } |
| 257 | originalIndex++; |
| 258 | afterIndex++; |
| 259 | } else if (matching(nextOriginal, nextAfter)) { |
| 260 | elements.add(new Kept(nextOriginal)); |
| 261 | originalIndex++; |
| 262 | afterIndex++; |
| 263 | } else if (replacement(nextOriginal, nextAfter)) { |
| 264 | originalIndex = considerRemoval(nextOriginal, originalIndex, elements); |
| 265 | elements.add(new Added(nextAfter)); |
| 266 | afterIndex++; |
| 267 | } else { |
| 268 | // We can try to remove the element or add it and look which one leads to the lower difference |
| 269 | List<DifferenceElement> addingElements = calculate(original.from(originalIndex), after.from(afterIndex + 1)); |
| 270 | List<DifferenceElement> removingElements = null; |
| 271 | if (cost(addingElements) > 0) { |
| 272 | removingElements = calculate(original.from(originalIndex + 1), after.from(afterIndex)); |
| 273 | } |
| 274 | |
| 275 | if (removingElements == null || cost(removingElements) > cost(addingElements)) { |
| 276 | elements.add(new Added(nextAfter)); |
| 277 | afterIndex++; |
| 278 | } else { |
| 279 | elements.add(new Removed(nextOriginal)); |
| 280 | originalIndex++; |
| 281 | } |
| 282 | } |
| 283 | } |
| 284 | } while (originalIndex < original.elements.size() || afterIndex < after.elements.size()); |
| 285 | |
| 286 | return elements; |
| 287 | } |
| 288 | |
| 289 | private static long cost(List<DifferenceElement> elements) { |
| 290 | return elements.stream().filter(e -> !(e instanceof Kept)).count(); |
| 291 | } |
| 292 | |
| 293 | |
| 294 | /** |
| 295 | * Remove from the difference all the elements related to indentation. |
| 296 | * This is mainly intended for test purposes. |
| 297 | */ |
| 298 | static void removeIndentationElements(List<DifferenceElement> elements) { |
| 299 | elements.removeIf(el -> el.getElement() instanceof CsmIndent || el.getElement() instanceof CsmUnindent); |
| 300 | } |
| 301 | } |
| 302 |
Members