001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.trans;
022:
023: import EDU.purdue.cs.bloat.tree.*;
024:
025: /**
026: * NodeComparator is a class used to differentiate nodes in an expression tree.
027: */
028: public class NodeComparator {
029: public static boolean DEBUG = false;
030:
031: /**
032: * Determines whether or not two <tt>Node</tt>s are equal.
033: */
034: public static boolean equals(final Node v, final Node w) {
035: class Bool {
036: boolean value = false;
037: }
038: ;
039:
040: final Bool eq = new Bool();
041:
042: v.visit(new TreeVisitor() {
043: public void visitExprStmt(final ExprStmt stmt) {
044: if (w instanceof ExprStmt) {
045: eq.value = true;
046: }
047: }
048:
049: public void visitIfCmpStmt(final IfCmpStmt stmt) {
050: if (w instanceof IfCmpStmt) {
051: final IfCmpStmt s = (IfCmpStmt) w;
052: eq.value = (stmt.trueTarget() == s.trueTarget())
053: && (stmt.falseTarget() == s.falseTarget())
054: && (stmt.comparison() == s.comparison());
055: }
056: }
057:
058: public void visitIfZeroStmt(final IfZeroStmt stmt) {
059: if (w instanceof IfZeroStmt) {
060: final IfZeroStmt s = (IfZeroStmt) w;
061: eq.value = (stmt.trueTarget() == s.trueTarget())
062: && (stmt.falseTarget() == s.falseTarget())
063: && (stmt.comparison() == s.comparison());
064: }
065: }
066:
067: public void visitSCStmt(final SCStmt stmt) {
068: if (w instanceof SCStmt) {
069: final SCStmt s = (SCStmt) w;
070: eq.value = (stmt.array() == s.array())
071: && (stmt.index() == s.index());
072: }
073: }
074:
075: public void visitSRStmt(final SRStmt stmt) {
076: if (w instanceof SRStmt) {
077: final SRStmt s = (SRStmt) w;
078: eq.value = (stmt.array() == s.array())
079: && (stmt.start() == s.start())
080: && (stmt.end() == s.end());
081: }
082: }
083:
084: public void visitInitStmt(final InitStmt stmt) {
085: if (w instanceof InitStmt) {
086: eq.value = true;
087: }
088: }
089:
090: public void visitGotoStmt(final GotoStmt stmt) {
091: if (w instanceof GotoStmt) {
092: final GotoStmt s = (GotoStmt) w;
093: eq.value = stmt.target() == s.target();
094: }
095: }
096:
097: public void visitLabelStmt(final LabelStmt stmt) {
098: if (w instanceof LabelStmt) {
099: final LabelStmt s = (LabelStmt) w;
100: eq.value = stmt.label().equals(s.label());
101: }
102: }
103:
104: public void visitMonitorStmt(final MonitorStmt stmt) {
105: if (w instanceof MonitorStmt) {
106: final MonitorStmt s = (MonitorStmt) w;
107: eq.value = stmt.kind() == s.kind();
108: }
109: }
110:
111: public void visitPhiJoinStmt(final PhiJoinStmt stmt) {
112: if (w instanceof PhiJoinStmt) {
113: eq.value = true;
114: }
115: }
116:
117: public void visitPhiCatchStmt(final PhiCatchStmt stmt) {
118: if (w instanceof PhiCatchStmt) {
119: eq.value = true;
120: }
121: }
122:
123: public void visitCatchExpr(final CatchExpr expr) {
124: // Catches are not equivalent.
125: eq.value = false;
126: }
127:
128: public void visitStackManipStmt(final StackManipStmt stmt) {
129: if (w instanceof StackManipStmt) {
130: final StackManipStmt s = (StackManipStmt) w;
131: eq.value = stmt.kind() == s.kind();
132: }
133: }
134:
135: public void visitRetStmt(final RetStmt stmt) {
136: if (w instanceof RetStmt) {
137: final RetStmt s = (RetStmt) w;
138: eq.value = stmt.sub() == s.sub();
139: }
140: }
141:
142: public void visitReturnExprStmt(final ReturnExprStmt stmt) {
143: if (w instanceof ReturnExprStmt) {
144: eq.value = true;
145: }
146: }
147:
148: public void visitReturnStmt(final ReturnStmt stmt) {
149: if (w instanceof ReturnStmt) {
150: eq.value = true;
151: }
152: }
153:
154: public void visitAddressStoreStmt(
155: final AddressStoreStmt stmt) {
156: if (w instanceof AddressStoreStmt) {
157: final AddressStoreStmt s = (AddressStoreStmt) w;
158: eq.value = stmt.sub() == s.sub();
159: }
160: }
161:
162: public void visitStoreExpr(final StoreExpr expr) {
163: if (w instanceof StoreExpr) {
164: eq.value = true;
165: }
166: }
167:
168: public void visitJsrStmt(final JsrStmt stmt) {
169: if (w instanceof JsrStmt) {
170: final JsrStmt s = (JsrStmt) w;
171: eq.value = stmt.sub() == s.sub();
172: }
173: }
174:
175: public void visitSwitchStmt(final SwitchStmt stmt) {
176: if (w instanceof SwitchStmt) {
177: eq.value = stmt == w;
178: }
179: }
180:
181: public void visitThrowStmt(final ThrowStmt stmt) {
182: if (w instanceof ThrowStmt) {
183: eq.value = true;
184: }
185: }
186:
187: public void visitArithExpr(final ArithExpr expr) {
188: if (w instanceof ArithExpr) {
189: final ArithExpr e = (ArithExpr) w;
190: eq.value = e.operation() == expr.operation();
191: }
192: }
193:
194: public void visitArrayLengthExpr(final ArrayLengthExpr expr) {
195: if (w instanceof ArrayLengthExpr) {
196: eq.value = true;
197: }
198: }
199:
200: public void visitArrayRefExpr(final ArrayRefExpr expr) {
201: if (w instanceof ArrayRefExpr) {
202: eq.value = true;
203: }
204: }
205:
206: public void visitCallMethodExpr(final CallMethodExpr expr) {
207: // Calls are never equal.
208: eq.value = false;
209: }
210:
211: public void visitCallStaticExpr(final CallStaticExpr expr) {
212: // Calls are never equal.
213: eq.value = false;
214: }
215:
216: public void visitCastExpr(final CastExpr expr) {
217: if (w instanceof CastExpr) {
218: final CastExpr e = (CastExpr) w;
219: eq.value = e.castType().equals(expr.castType());
220: }
221: }
222:
223: public void visitConstantExpr(final ConstantExpr expr) {
224: if (w instanceof ConstantExpr) {
225: final ConstantExpr e = (ConstantExpr) w;
226: if (e.value() == null) {
227: eq.value = expr.value() == null;
228: } else {
229: eq.value = e.value().equals(expr.value());
230: }
231: }
232: }
233:
234: public void visitFieldExpr(final FieldExpr expr) {
235: if (w instanceof FieldExpr) {
236: final FieldExpr e = (FieldExpr) w;
237: eq.value = e.field().equals(expr.field());
238: }
239: }
240:
241: public void visitInstanceOfExpr(final InstanceOfExpr expr) {
242: if (w instanceof InstanceOfExpr) {
243: final InstanceOfExpr e = (InstanceOfExpr) w;
244: eq.value = e.checkType().equals(expr.checkType());
245: }
246: }
247:
248: public void visitLocalExpr(final LocalExpr expr) {
249: if (w instanceof LocalExpr) {
250: final LocalExpr e = (LocalExpr) w;
251: eq.value = e.def() == expr.def();
252: }
253: }
254:
255: public void visitNegExpr(final NegExpr expr) {
256: if (w instanceof NegExpr) {
257: eq.value = true;
258: }
259: }
260:
261: public void visitNewArrayExpr(final NewArrayExpr expr) {
262: eq.value = false;
263: }
264:
265: public void visitNewExpr(final NewExpr expr) {
266: eq.value = false;
267: }
268:
269: public void visitNewMultiArrayExpr(
270: final NewMultiArrayExpr expr) {
271: eq.value = false;
272: }
273:
274: public void visitZeroCheckExpr(final ZeroCheckExpr expr) {
275: if (w instanceof ZeroCheckExpr) {
276: eq.value = true;
277: }
278: }
279:
280: public void visitRCExpr(final RCExpr expr) {
281: if (w instanceof RCExpr) {
282: eq.value = true;
283: }
284: }
285:
286: public void visitUCExpr(final UCExpr expr) {
287: if (w instanceof UCExpr) {
288: final UCExpr e = (UCExpr) w;
289: eq.value = e.kind() == expr.kind();
290: }
291: }
292:
293: public void visitReturnAddressExpr(
294: final ReturnAddressExpr expr) {
295: if (w instanceof ReturnAddressExpr) {
296: eq.value = true;
297: }
298: }
299:
300: public void visitShiftExpr(final ShiftExpr expr) {
301: if (w instanceof ShiftExpr) {
302: final ShiftExpr e = (ShiftExpr) w;
303: eq.value = e.dir() == expr.dir();
304: }
305: }
306:
307: public void visitStackExpr(final StackExpr expr) {
308: if (w instanceof StackExpr) {
309: final StackExpr e = (StackExpr) w;
310: eq.value = e.def() == expr.def();
311: }
312: }
313:
314: public void visitStaticFieldExpr(final StaticFieldExpr expr) {
315: if (w instanceof StaticFieldExpr) {
316: final StaticFieldExpr e = (StaticFieldExpr) w;
317: eq.value = e.field().equals(expr.field());
318: }
319: }
320:
321: public void visitNode(final Node node) {
322: throw new RuntimeException("No method for " + node);
323: }
324: });
325:
326: return eq.value;
327: }
328:
329: /**
330: * Computes a hash code for a given <tt>Node</tt> based upon its type. The
331: * hash code of nodes that are composed of other nodes are based upon their
332: * composits.
333: */
334: public static int hashCode(final Node node) {
335: class Int {
336: int value = 0;
337: }
338: ;
339:
340: final Int hash = new Int();
341:
342: node.visit(new TreeVisitor() {
343: public void visitExprStmt(final ExprStmt stmt) {
344: hash.value = 1;
345: }
346:
347: public void visitIfCmpStmt(final IfCmpStmt stmt) {
348: hash.value = stmt.comparison()
349: + stmt.trueTarget().hashCode()
350: + stmt.falseTarget().hashCode();
351: }
352:
353: public void visitIfZeroStmt(final IfZeroStmt stmt) {
354: hash.value = stmt.comparison()
355: + stmt.trueTarget().hashCode()
356: + stmt.falseTarget().hashCode();
357: }
358:
359: public void visitInitStmt(final InitStmt stmt) {
360: hash.value = 2;
361: }
362:
363: public void visitGotoStmt(final GotoStmt stmt) {
364: hash.value = stmt.target().hashCode();
365: }
366:
367: public void visitLabelStmt(final LabelStmt stmt) {
368: hash.value = stmt.label().hashCode();
369: }
370:
371: public void visitMonitorStmt(final MonitorStmt stmt) {
372: hash.value = stmt.kind();
373: }
374:
375: public void visitPhiJoinStmt(final PhiJoinStmt stmt) {
376: hash.value = 3;
377: }
378:
379: public void visitPhiCatchStmt(final PhiCatchStmt stmt) {
380: hash.value = 4;
381: }
382:
383: public void visitCatchExpr(final CatchExpr expr) {
384: // Catches are not equivalent.
385: hash.value = expr.hashCode();
386: }
387:
388: public void visitStackManipStmt(final StackManipStmt stmt) {
389: hash.value = stmt.kind();
390: }
391:
392: public void visitRetStmt(final RetStmt stmt) {
393: hash.value = 5;
394: }
395:
396: public void visitReturnExprStmt(final ReturnExprStmt stmt) {
397: hash.value = 6;
398: }
399:
400: public void visitReturnStmt(final ReturnStmt stmt) {
401: hash.value = 7;
402: }
403:
404: public void visitAddressStoreStmt(
405: final AddressStoreStmt stmt) {
406: hash.value = 8;
407: }
408:
409: public void visitStoreExpr(final StoreExpr expr) {
410: hash.value = 9;
411: }
412:
413: public void visitJsrStmt(final JsrStmt stmt) {
414: hash.value = 10;
415: }
416:
417: public void visitSwitchStmt(final SwitchStmt stmt) {
418: hash.value = 11;
419: }
420:
421: public void visitThrowStmt(final ThrowStmt stmt) {
422: hash.value = 12;
423: }
424:
425: public void visitArithExpr(final ArithExpr expr) {
426: hash.value = expr.operation();
427: }
428:
429: public void visitArrayLengthExpr(final ArrayLengthExpr expr) {
430: hash.value = 13;
431: }
432:
433: public void visitArrayRefExpr(final ArrayRefExpr expr) {
434: hash.value = 14;
435: }
436:
437: public void visitCallMethodExpr(final CallMethodExpr expr) {
438: // Calls are never equal.
439: hash.value = expr.hashCode();
440: }
441:
442: public void visitCallStaticExpr(final CallStaticExpr expr) {
443: // Calls are never equal.
444: hash.value = expr.hashCode();
445: }
446:
447: public void visitCastExpr(final CastExpr expr) {
448: hash.value = expr.castType().hashCode();
449: }
450:
451: public void visitConstantExpr(final ConstantExpr expr) {
452: if (expr.value() == null) {
453: hash.value = 0;
454: } else {
455: hash.value = expr.value().hashCode();
456: }
457: }
458:
459: public void visitFieldExpr(final FieldExpr expr) {
460: hash.value = expr.field().hashCode();
461: }
462:
463: public void visitInstanceOfExpr(final InstanceOfExpr expr) {
464: hash.value = expr.checkType().hashCode();
465: }
466:
467: public void visitLocalExpr(final LocalExpr expr) {
468: if (expr.def() != null) {
469: hash.value = expr.def().hashCode();
470: } else {
471: hash.value = 0;
472: }
473: }
474:
475: public void visitNegExpr(final NegExpr expr) {
476: hash.value = 16;
477: }
478:
479: public void visitNewArrayExpr(final NewArrayExpr expr) {
480: hash.value = expr.hashCode();
481: }
482:
483: public void visitNewExpr(final NewExpr expr) {
484: hash.value = expr.hashCode();
485: }
486:
487: public void visitNewMultiArrayExpr(
488: final NewMultiArrayExpr expr) {
489: hash.value = expr.hashCode();
490: }
491:
492: public void visitZeroCheckExpr(final ZeroCheckExpr expr) {
493: hash.value = 15;
494: }
495:
496: public void visitRCExpr(final RCExpr expr) {
497: hash.value = 17;
498: }
499:
500: public void visitUCExpr(final UCExpr expr) {
501: hash.value = 18 + expr.kind();
502: }
503:
504: public void visitReturnAddressExpr(
505: final ReturnAddressExpr expr) {
506: hash.value = 21;
507: }
508:
509: public void visitSCStmt(final SCStmt stmt) {
510: hash.value = 23;
511: }
512:
513: public void visitSRStmt(final SRStmt stmt) {
514: hash.value = 22;
515: }
516:
517: public void visitShiftExpr(final ShiftExpr expr) {
518: hash.value = expr.dir();
519: }
520:
521: public void visitStackExpr(final StackExpr expr) {
522: if (expr.def() != null) {
523: hash.value = expr.def().hashCode();
524: } else {
525: hash.value = 0;
526: }
527: }
528:
529: public void visitStaticFieldExpr(final StaticFieldExpr expr) {
530: hash.value = expr.field().hashCode();
531: }
532:
533: public void visitNode(final Node node) {
534: throw new RuntimeException("No method for " + node);
535: }
536: });
537:
538: return hash.value;
539: }
540: }
|