1 /*
2 * Copyright (c) 2018, Google LLC. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.tools.javac.comp;
27
28 import com.sun.tools.javac.code.Symbol;
29 import com.sun.tools.javac.tree.JCTree;
30 import com.sun.tools.javac.tree.JCTree.JCAnnotatedType;
31 import com.sun.tools.javac.tree.JCTree.JCAnnotation;
32 import com.sun.tools.javac.tree.JCTree.JCArrayAccess;
33 import com.sun.tools.javac.tree.JCTree.JCArrayTypeTree;
34 import com.sun.tools.javac.tree.JCTree.JCAssert;
35 import com.sun.tools.javac.tree.JCTree.JCAssign;
36 import com.sun.tools.javac.tree.JCTree.JCAssignOp;
37 import com.sun.tools.javac.tree.JCTree.JCBinary;
38 import com.sun.tools.javac.tree.JCTree.JCBlock;
39 import com.sun.tools.javac.tree.JCTree.JCBreak;
40 import com.sun.tools.javac.tree.JCTree.JCCase;
41 import com.sun.tools.javac.tree.JCTree.JCCatch;
42 import com.sun.tools.javac.tree.JCTree.JCClassDecl;
43 import com.sun.tools.javac.tree.JCTree.JCCompilationUnit;
44 import com.sun.tools.javac.tree.JCTree.JCConditional;
45 import com.sun.tools.javac.tree.JCTree.JCContinue;
46 import com.sun.tools.javac.tree.JCTree.JCDoWhileLoop;
47 import com.sun.tools.javac.tree.JCTree.JCEnhancedForLoop;
48 import com.sun.tools.javac.tree.JCTree.JCErroneous;
49 import com.sun.tools.javac.tree.JCTree.JCExports;
50 import com.sun.tools.javac.tree.JCTree.JCExpressionStatement;
51 import com.sun.tools.javac.tree.JCTree.JCFieldAccess;
52 import com.sun.tools.javac.tree.JCTree.JCForLoop;
53 import com.sun.tools.javac.tree.JCTree.JCIdent;
54 import com.sun.tools.javac.tree.JCTree.JCIf;
55 import com.sun.tools.javac.tree.JCTree.JCImport;
56 import com.sun.tools.javac.tree.JCTree.JCInstanceOf;
57 import com.sun.tools.javac.tree.JCTree.JCLabeledStatement;
58 import com.sun.tools.javac.tree.JCTree.JCLambda;
59 import com.sun.tools.javac.tree.JCTree.JCLiteral;
60 import com.sun.tools.javac.tree.JCTree.JCMemberReference;
61 import com.sun.tools.javac.tree.JCTree.JCMethodDecl;
62 import com.sun.tools.javac.tree.JCTree.JCMethodInvocation;
63 import com.sun.tools.javac.tree.JCTree.JCModifiers;
64 import com.sun.tools.javac.tree.JCTree.JCModuleDecl;
65 import com.sun.tools.javac.tree.JCTree.JCNewArray;
66 import com.sun.tools.javac.tree.JCTree.JCNewClass;
67 import com.sun.tools.javac.tree.JCTree.JCOpens;
68 import com.sun.tools.javac.tree.JCTree.JCPackageDecl;
69 import com.sun.tools.javac.tree.JCTree.JCPrimitiveTypeTree;
70 import com.sun.tools.javac.tree.JCTree.JCProvides;
71 import com.sun.tools.javac.tree.JCTree.JCRequires;
72 import com.sun.tools.javac.tree.JCTree.JCReturn;
73 import com.sun.tools.javac.tree.JCTree.JCSwitch;
74 import com.sun.tools.javac.tree.JCTree.JCSynchronized;
75 import com.sun.tools.javac.tree.JCTree.JCThrow;
76 import com.sun.tools.javac.tree.JCTree.JCTry;
77 import com.sun.tools.javac.tree.JCTree.JCTypeApply;
78 import com.sun.tools.javac.tree.JCTree.JCTypeCast;
79 import com.sun.tools.javac.tree.JCTree.JCTypeIntersection;
80 import com.sun.tools.javac.tree.JCTree.JCTypeParameter;
81 import com.sun.tools.javac.tree.JCTree.JCTypeUnion;
82 import com.sun.tools.javac.tree.JCTree.JCUnary;
83 import com.sun.tools.javac.tree.JCTree.JCUses;
84 import com.sun.tools.javac.tree.JCTree.JCVariableDecl;
85 import com.sun.tools.javac.tree.JCTree.JCWhileLoop;
86 import com.sun.tools.javac.tree.JCTree.JCWildcard;
87 import com.sun.tools.javac.tree.JCTree.LetExpr;
88 import com.sun.tools.javac.tree.JCTree.TypeBoundKind;
89 import com.sun.tools.javac.tree.TreeInfo;
90 import com.sun.tools.javac.tree.TreeScanner;
91 import com.sun.tools.javac.util.List;
92 import java.util.Collection;
93 import java.util.HashMap;
94 import java.util.Iterator;
95 import java.util.Map;
96 import java.util.Objects;
97
98 /** A visitor that compares two lambda bodies for structural equality. */
99 public class TreeDiffer extends TreeScanner {
100
101 public TreeDiffer(
102 Collection<? extends Symbol> symbols, Collection<? extends Symbol> otherSymbols) {
103 this.equiv = equiv(symbols, otherSymbols);
104 }
105
106 private static Map<Symbol, Symbol> equiv(
107 Collection<? extends Symbol> symbols, Collection<? extends Symbol> otherSymbols) {
108 Map<Symbol, Symbol> result = new HashMap<>();
109 Iterator<? extends Symbol> it = otherSymbols.iterator();
110 for (Symbol symbol : symbols) {
111 if (!it.hasNext()) break;
112 result.put(symbol, it.next());
113 }
114 return result;
115 }
116
117 private JCTree parameter;
118 private boolean result;
119 private Map<Symbol, Symbol> equiv = new HashMap<>();
120
121 public boolean scan(JCTree tree, JCTree parameter) {
122 if (tree == null || parameter == null) {
123 return tree == null && parameter == null;
124 }
125 tree = TreeInfo.skipParens(tree);
126 parameter = TreeInfo.skipParens(parameter);
127 if (tree.type != null
128 && tree.type.constValue() != null
129 && parameter.type != null
130 && parameter.type.constValue() != null) {
131 return Objects.equals(tree.type.constValue(), parameter.type.constValue());
132 }
133 if (tree.getTag() != parameter.getTag()) {
134 return false;
135 }
136 JCTree prevParameter = this.parameter;
137 boolean prevResult = this.result;
138 try {
139 this.parameter = parameter;
140 tree.accept(this);
141 return result;
142 } finally {
143 this.parameter = prevParameter;
144 this.result = prevResult;
145 }
146 }
147
148 private boolean scan(Iterable<? extends JCTree> xs, Iterable<? extends JCTree> ys) {
149 if (xs == null || ys == null) {
150 return xs == null && ys == null;
151 }
152 Iterator<? extends JCTree> x = xs.iterator();
153 Iterator<? extends JCTree> y = ys.iterator();
154 while (x.hasNext() && y.hasNext()) {
155 if (!scan(x.next(), y.next())) {
156 return false;
157 }
158 }
159 return !x.hasNext() && !y.hasNext();
160 }
161
162 private boolean scanDimAnnotations(List<List<JCAnnotation>> xs, List<List<JCAnnotation>> ys) {
163 if (xs == null || ys == null) {
164 return xs == null && ys == null;
165 }
166 Iterator<List<JCAnnotation>> x = xs.iterator();
167 Iterator<List<JCAnnotation>> y = ys.iterator();
168 while (x.hasNext() && y.hasNext()) {
169 if (!scan(x.next(), y.next())) {
170 return false;
171 }
172 }
173 return !x.hasNext() && !y.hasNext();
174 }
175
176 @Override
177 public void visitIdent(JCIdent tree) {
178 JCIdent that = (JCIdent) parameter;
179 // Identifiers are a special case: we want to ensure the identifiers correspond to the
180 // same symbols (rather than just having the same name), but also consider lambdas
181 // equal if they differ only in the names of the parameters.
182 Symbol symbol = tree.sym;
183 Symbol otherSymbol = that.sym;
184 if (symbol != null && otherSymbol != null) {
185 if (Objects.equals(equiv.get(symbol), otherSymbol)) {
186 result = true;
187 return;
188 }
189 }
190 result = tree.sym == that.sym;
191 }
192
193 @Override
194 public void visitSelect(JCFieldAccess tree) {
195 JCFieldAccess that = (JCFieldAccess) parameter;
196 result = scan(tree.selected, that.selected) && tree.sym == that.sym;
197 }
198
199 @Override
200 public void visitAnnotatedType(JCAnnotatedType tree) {
201 JCAnnotatedType that = (JCAnnotatedType) parameter;
202 result =
203 scan(tree.annotations, that.annotations)
204 && scan(tree.underlyingType, that.underlyingType);
205 }
206
207 @Override
208 public void visitAnnotation(JCAnnotation tree) {
209 JCAnnotation that = (JCAnnotation) parameter;
210 result = scan(tree.annotationType, that.annotationType) && scan(tree.args, that.args);
211 }
212
213 @Override
214 public void visitApply(JCMethodInvocation tree) {
215 JCMethodInvocation that = (JCMethodInvocation) parameter;
216 result =
217 scan(tree.typeargs, that.typeargs)
218 && scan(tree.meth, that.meth)
219 && scan(tree.args, that.args)
220 && tree.polyKind == that.polyKind;
221 }
222
223 @Override
224 public void visitAssert(JCAssert tree) {
225 JCAssert that = (JCAssert) parameter;
226 result = scan(tree.cond, that.cond) && scan(tree.detail, that.detail);
227 }
228
229 @Override
230 public void visitAssign(JCAssign tree) {
231 JCAssign that = (JCAssign) parameter;
232 result = scan(tree.lhs, that.lhs) && scan(tree.rhs, that.rhs);
233 }
234
235 @Override
236 public void visitAssignop(JCAssignOp tree) {
237 JCAssignOp that = (JCAssignOp) parameter;
238 result =
239 scan(tree.lhs, that.lhs)
240 && scan(tree.rhs, that.rhs)
241 && tree.operator == that.operator;
242 }
243
244 @Override
245 public void visitBinary(JCBinary tree) {
246 JCBinary that = (JCBinary) parameter;
247 result =
248 scan(tree.lhs, that.lhs)
249 && scan(tree.rhs, that.rhs)
250 && tree.operator == that.operator;
251 }
252
253 @Override
254 public void visitBlock(JCBlock tree) {
255 JCBlock that = (JCBlock) parameter;
256 result = tree.flags == that.flags && scan(tree.stats, that.stats);
257 }
258
259 @Override
260 public void visitBreak(JCBreak tree) {
261 JCBreak that = (JCBreak) parameter;
262 result = tree.label == that.label;
263 }
264
265 @Override
266 public void visitCase(JCCase tree) {
267 JCCase that = (JCCase) parameter;
268 result = scan(tree.pat, that.pat) && scan(tree.stats, that.stats);
269 }
270
271 @Override
272 public void visitCatch(JCCatch tree) {
273 JCCatch that = (JCCatch) parameter;
274 result = scan(tree.param, that.param) && scan(tree.body, that.body);
275 }
276
277 @Override
278 public void visitClassDef(JCClassDecl tree) {
279 JCClassDecl that = (JCClassDecl) parameter;
280 result =
281 scan(tree.mods, that.mods)
282 && tree.name == that.name
283 && scan(tree.typarams, that.typarams)
284 && scan(tree.extending, that.extending)
285 && scan(tree.implementing, that.implementing)
286 && scan(tree.defs, that.defs);
287 }
288
289 @Override
290 public void visitConditional(JCConditional tree) {
291 JCConditional that = (JCConditional) parameter;
292 result =
293 scan(tree.cond, that.cond)
294 && scan(tree.truepart, that.truepart)
295 && scan(tree.falsepart, that.falsepart);
296 }
297
298 @Override
299 public void visitContinue(JCContinue tree) {
300 JCContinue that = (JCContinue) parameter;
301 result = tree.label == that.label;
302 }
303
304 @Override
305 public void visitDoLoop(JCDoWhileLoop tree) {
306 JCDoWhileLoop that = (JCDoWhileLoop) parameter;
307 result = scan(tree.body, that.body) && scan(tree.cond, that.cond);
308 }
309
310 @Override
311 public void visitErroneous(JCErroneous tree) {
312 JCErroneous that = (JCErroneous) parameter;
313 result = scan(tree.errs, that.errs);
314 }
315
316 @Override
317 public void visitExec(JCExpressionStatement tree) {
318 JCExpressionStatement that = (JCExpressionStatement) parameter;
319 result = scan(tree.expr, that.expr);
320 }
321
322 @Override
323 public void visitExports(JCExports tree) {
324 JCExports that = (JCExports) parameter;
325 result = scan(tree.qualid, that.qualid) && scan(tree.moduleNames, that.moduleNames);
326 }
327
328 @Override
329 public void visitForLoop(JCForLoop tree) {
330 JCForLoop that = (JCForLoop) parameter;
331 result =
332 scan(tree.init, that.init)
333 && scan(tree.cond, that.cond)
334 && scan(tree.step, that.step)
335 && scan(tree.body, that.body);
336 }
337
338 @Override
339 public void visitForeachLoop(JCEnhancedForLoop tree) {
340 JCEnhancedForLoop that = (JCEnhancedForLoop) parameter;
341 result =
342 scan(tree.var, that.var)
343 && scan(tree.expr, that.expr)
344 && scan(tree.body, that.body);
345 }
346
347 @Override
348 public void visitIf(JCIf tree) {
349 JCIf that = (JCIf) parameter;
350 result =
351 scan(tree.cond, that.cond)
352 && scan(tree.thenpart, that.thenpart)
353 && scan(tree.elsepart, that.elsepart);
354 }
355
356 @Override
357 public void visitImport(JCImport tree) {
358 JCImport that = (JCImport) parameter;
359 result = tree.staticImport == that.staticImport && scan(tree.qualid, that.qualid);
360 }
361
362 @Override
363 public void visitIndexed(JCArrayAccess tree) {
364 JCArrayAccess that = (JCArrayAccess) parameter;
365 result = scan(tree.indexed, that.indexed) && scan(tree.index, that.index);
366 }
367
368 @Override
369 public void visitLabelled(JCLabeledStatement tree) {
370 JCLabeledStatement that = (JCLabeledStatement) parameter;
371 result = tree.label == that.label && scan(tree.body, that.body);
372 }
373
374 @Override
375 public void visitLambda(JCLambda tree) {
376 JCLambda that = (JCLambda) parameter;
377 result =
378 scan(tree.params, that.params)
379 && scan(tree.body, that.body)
380 && tree.paramKind == that.paramKind;
381 }
382
383 @Override
384 public void visitLetExpr(LetExpr tree) {
385 LetExpr that = (LetExpr) parameter;
386 result = scan(tree.defs, that.defs) && scan(tree.expr, that.expr);
387 }
388
389 @Override
390 public void visitLiteral(JCLiteral tree) {
391 JCLiteral that = (JCLiteral) parameter;
392 result = tree.typetag == that.typetag && Objects.equals(tree.value, that.value);
393 }
394
395 @Override
396 public void visitMethodDef(JCMethodDecl tree) {
397 JCMethodDecl that = (JCMethodDecl) parameter;
398 result =
399 scan(tree.mods, that.mods)
400 && tree.name == that.name
401 && scan(tree.restype, that.restype)
402 && scan(tree.typarams, that.typarams)
403 && scan(tree.recvparam, that.recvparam)
404 && scan(tree.params, that.params)
405 && scan(tree.thrown, that.thrown)
406 && scan(tree.body, that.body)
407 && scan(tree.defaultValue, that.defaultValue);
408 }
409
410 @Override
411 public void visitModifiers(JCModifiers tree) {
412 JCModifiers that = (JCModifiers) parameter;
413 result = tree.flags == that.flags && scan(tree.annotations, that.annotations);
414 }
415
416 @Override
417 public void visitModuleDef(JCModuleDecl tree) {
418 JCModuleDecl that = (JCModuleDecl) parameter;
419 result =
420 scan(tree.mods, that.mods)
421 && scan(tree.qualId, that.qualId)
422 && scan(tree.directives, that.directives);
423 }
424
425 @Override
426 public void visitNewArray(JCNewArray tree) {
427 JCNewArray that = (JCNewArray) parameter;
428 result =
429 scan(tree.elemtype, that.elemtype)
430 && scan(tree.dims, that.dims)
431 && scan(tree.annotations, that.annotations)
432 && scanDimAnnotations(tree.dimAnnotations, that.dimAnnotations)
433 && scan(tree.elems, that.elems);
434 }
435
436 @Override
437 public void visitNewClass(JCNewClass tree) {
438 JCNewClass that = (JCNewClass) parameter;
439 result =
440 scan(tree.encl, that.encl)
441 && scan(tree.typeargs, that.typeargs)
442 && scan(tree.clazz, that.clazz)
443 && scan(tree.args, that.args)
444 && scan(tree.def, that.def)
445 && tree.constructor == that.constructor;
446 }
447
448 @Override
449 public void visitOpens(JCOpens tree) {
450 JCOpens that = (JCOpens) parameter;
451 result = scan(tree.qualid, that.qualid) && scan(tree.moduleNames, that.moduleNames);
452 }
453
454 @Override
455 public void visitPackageDef(JCPackageDecl tree) {
456 JCPackageDecl that = (JCPackageDecl) parameter;
457 result =
458 scan(tree.annotations, that.annotations)
459 && scan(tree.pid, that.pid)
460 && tree.packge == that.packge;
461 }
462
463 @Override
464 public void visitProvides(JCProvides tree) {
465 JCProvides that = (JCProvides) parameter;
466 result = scan(tree.serviceName, that.serviceName) && scan(tree.implNames, that.implNames);
467 }
468
469 @Override
470 public void visitReference(JCMemberReference tree) {
471 JCMemberReference that = (JCMemberReference) parameter;
472 result =
473 tree.mode == that.mode
474 && tree.kind == that.kind
475 && tree.name == that.name
476 && scan(tree.expr, that.expr)
477 && scan(tree.typeargs, that.typeargs);
478 }
479
480 @Override
481 public void visitRequires(JCRequires tree) {
482 JCRequires that = (JCRequires) parameter;
483 result =
484 tree.isTransitive == that.isTransitive
485 && tree.isStaticPhase == that.isStaticPhase
486 && scan(tree.moduleName, that.moduleName);
487 }
488
489 @Override
490 public void visitReturn(JCReturn tree) {
491 JCReturn that = (JCReturn) parameter;
492 result = scan(tree.expr, that.expr);
493 }
494
495 @Override
496 public void visitSwitch(JCSwitch tree) {
497 JCSwitch that = (JCSwitch) parameter;
498 result = scan(tree.selector, that.selector) && scan(tree.cases, that.cases);
499 }
500
501 @Override
502 public void visitSynchronized(JCSynchronized tree) {
503 JCSynchronized that = (JCSynchronized) parameter;
504 result = scan(tree.lock, that.lock) && scan(tree.body, that.body);
505 }
506
507 @Override
508 public void visitThrow(JCThrow tree) {
509 JCThrow that = (JCThrow) parameter;
510 result = scan(tree.expr, that.expr);
511 }
512
513 @Override
514 public void visitTopLevel(JCCompilationUnit tree) {
515 JCCompilationUnit that = (JCCompilationUnit) parameter;
516 result =
517 scan(tree.defs, that.defs)
518 && tree.modle == that.modle
519 && tree.packge == that.packge;
520 }
521
522 @Override
523 public void visitTry(JCTry tree) {
524 JCTry that = (JCTry) parameter;
525 result =
526 scan(tree.body, that.body)
527 && scan(tree.catchers, that.catchers)
528 && scan(tree.finalizer, that.finalizer)
529 && scan(tree.resources, that.resources);
530 }
531
532 @Override
533 public void visitTypeApply(JCTypeApply tree) {
534 JCTypeApply that = (JCTypeApply) parameter;
535 result = scan(tree.clazz, that.clazz) && scan(tree.arguments, that.arguments);
536 }
537
538 @Override
539 public void visitTypeArray(JCArrayTypeTree tree) {
540 JCArrayTypeTree that = (JCArrayTypeTree) parameter;
541 result = scan(tree.elemtype, that.elemtype);
542 }
543
544 @Override
545 public void visitTypeBoundKind(TypeBoundKind tree) {
546 TypeBoundKind that = (TypeBoundKind) parameter;
547 result = tree.kind == that.kind;
548 }
549
550 @Override
551 public void visitTypeCast(JCTypeCast tree) {
552 JCTypeCast that = (JCTypeCast) parameter;
553 result = scan(tree.clazz, that.clazz) && scan(tree.expr, that.expr);
554 }
555
556 @Override
557 public void visitTypeIdent(JCPrimitiveTypeTree tree) {
558 JCPrimitiveTypeTree that = (JCPrimitiveTypeTree) parameter;
559 result = tree.typetag == that.typetag;
560 }
561
562 @Override
563 public void visitTypeIntersection(JCTypeIntersection tree) {
564 JCTypeIntersection that = (JCTypeIntersection) parameter;
565 result = scan(tree.bounds, that.bounds);
566 }
567
568 @Override
569 public void visitTypeParameter(JCTypeParameter tree) {
570 JCTypeParameter that = (JCTypeParameter) parameter;
571 result =
572 tree.name == that.name
573 && scan(tree.bounds, that.bounds)
574 && scan(tree.annotations, that.annotations);
575 }
576
577 @Override
578 public void visitTypeTest(JCInstanceOf tree) {
579 JCInstanceOf that = (JCInstanceOf) parameter;
580 result = scan(tree.expr, that.expr) && scan(tree.clazz, that.clazz);
581 }
582
583 @Override
584 public void visitTypeUnion(JCTypeUnion tree) {
585 JCTypeUnion that = (JCTypeUnion) parameter;
586 result = scan(tree.alternatives, that.alternatives);
587 }
588
589 @Override
590 public void visitUnary(JCUnary tree) {
591 JCUnary that = (JCUnary) parameter;
592 result = scan(tree.arg, that.arg) && tree.operator == that.operator;
593 }
594
595 @Override
596 public void visitUses(JCUses tree) {
597 JCUses that = (JCUses) parameter;
598 result = scan(tree.qualid, that.qualid);
599 }
600
601 @Override
602 public void visitVarDef(JCVariableDecl tree) {
603 JCVariableDecl that = (JCVariableDecl) parameter;
604 result =
605 scan(tree.mods, that.mods)
606 && tree.name == that.name
607 && scan(tree.nameexpr, that.nameexpr)
608 && scan(tree.vartype, that.vartype)
609 && scan(tree.init, that.init);
610 if (!result) {
611 return;
612 }
613 equiv.put(tree.sym, that.sym);
614 }
615
616 @Override
617 public void visitWhileLoop(JCWhileLoop tree) {
618 JCWhileLoop that = (JCWhileLoop) parameter;
619 result = scan(tree.cond, that.cond) && scan(tree.body, that.body);
620 }
621
622 @Override
623 public void visitWildcard(JCWildcard tree) {
624 JCWildcard that = (JCWildcard) parameter;
625 result = scan(tree.kind, that.kind) && scan(tree.inner, that.inner);
626 }
627 }