001: /*
002: * <copyright>
003: *
004: * Copyright 1997-2004 BBNT Solutions, LLC
005: * under sponsorship of the Defense Advanced Research Projects
006: * Agency (DARPA).
007: *
008: * You can redistribute this software and/or modify it under the
009: * terms of the Cougaar Open Source License as published on the
010: * Cougaar Open Source Website (www.cougaar.org).
011: *
012: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
013: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
014: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
015: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
016: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
017: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
018: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
019: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
020: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
021: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
022: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
023: *
024: * </copyright>
025: */
026:
027: package org.cougaar.lib.contract.lang.compare;
028:
029: import java.lang.reflect.Method;
030: import java.lang.reflect.Modifier;
031: import java.util.*;
032:
033: import org.cougaar.lib.contract.lang.*;
034: import org.cougaar.lib.contract.lang.op.OpCodes;
035: import org.cougaar.lib.contract.lang.op.constant.*;
036: import org.cougaar.lib.contract.lang.op.list.*;
037: import org.cougaar.lib.contract.lang.op.logical.*;
038: import org.cougaar.lib.contract.lang.op.reflect.*;
039:
040: /**
041: * Computes <tt>true</tt> if one <code>Op</code> "implies" another
042: * <code>Op</code>.
043: * <p>
044: * The following notes describe the meaning of "implies":
045: * <p>
046: * <pre>
047: * Given two Operators, A and B.
048: *
049: * Let "implies" be defined as:
050: * (A implies B) :
051: * for all Objects <i>o1 .. on</i>,
052: * if <tt>(A(<i>oi</i>) == true) then (B(<i>oi</i>) == true)</tt>.
053: *
054: *
055: * For example:
056: *
057: * A(Object o) = { return (o instanceof String); }
058: * B(Object o) = { return ((o instanceof String) || (o instanceof List)); }
059: *
060: * then, by the definition of "implies":
061: *
062: * A implies B. (If o is a (String) then it must be a (String or List))
063: * B doesn't imply A. (Object o could be a non-String List, in which case
064: * ((B(o) == true) AND (A(o) == false)))
065: *
066: *
067: * The AND/OR relations and a small number of other Operators (NOT,
068: * INSTANCEOF) will provide most of the logic -- anything else will be
069: * compared using "equals".
070: * </pre>
071: *
072: * @see Allow which is closely related to <code>Imply</code>
073: */
074: public final class Imply implements OpCodes {
075:
076: private Imply() {
077: }
078:
079: public static final boolean compute(final Object o1, final Object o2) {
080: if (o1 instanceof Op) {
081: return compute((Op) o1, o2);
082: }
083: throw new IllegalArgumentException("Not an Op: " + o1);
084: }
085:
086: public static final boolean compute(final Op o1, final Object o2) {
087: if (o2 instanceof Op) {
088: return compute(o1, (Op) o2);
089: }
090: throw new IllegalArgumentException("Not an Op: " + o2);
091: }
092:
093: public static final boolean compute(final Op o1, final Op o2) {
094: switch (o1.getID()) {
095: // constant
096: case CONSTANT_ID:
097: return compute((ConstantOp) o1, o2);
098: case GET_ID:
099: return compute((GetOp) o1, o2);
100: // list
101: case ALL_ID:
102: return compute((AllOp) o1, o2);
103: case EMPTY_ID:
104: return compute((EmptyOp) o1, o2);
105: case EXISTS_ID:
106: return compute((ExistsOp) o1, o2);
107: // logical
108: case AND_ID:
109: return compute((AndOp) o1, o2);
110: case FALSE_ID:
111: return compute((FalseOp) o1, o2);
112: case NOT_ID:
113: return compute((NotOp) o1, o2);
114: case OR_ID:
115: return compute((OrOp) o1, o2);
116: case TRUE_ID:
117: return compute((TrueOp) o1, o2);
118: // reflect
119: case APPLY_ID:
120: return compute((ApplyOp) o1, o2);
121: case FIELD_ID:
122: return compute((FieldOp) o1, o2);
123: case INSTANCEOF_ID:
124: return compute((InstanceOfOp) o1, o2);
125: case METHOD_ID:
126: return compute((MethodOp) o1, o2);
127: case REFLECT_ID:
128: throw new UnsupportedOperationException(
129: "ReflectOps should be parsed to MethodOps/FieldOps!");
130: case THIS_ID:
131: return compute((ThisOp) o1, o2);
132: default:
133: throw new RuntimeException("Unknown Op: " + o1);
134: }
135: }
136:
137: protected static final boolean compute(final ConstantOp o1,
138: final Op o2) {
139: return (o1.equals(o2));
140: }
141:
142: protected static final boolean compute(final GetOp o1, final Op o2) {
143: return (o1.equals(o2));
144: }
145:
146: protected static final boolean compute(final AllOp o1, final Op o2) {
147: int o2ID = o2.getID();
148: if (o2ID == ALL_ID) {
149: // compare the operators of the alls
150: return compute((o1.u), (((AllOp) o2).u));
151: } else if (o2ID == INSTANCEOF_ID) {
152: // allOps only accept collections
153: return (((Type) o2).impliedBy(false, Collection.class));
154: } else {
155: return false;
156: }
157: }
158:
159: protected static final boolean compute(final EmptyOp o1, final Op o2) {
160: if (o1 == o2) {
161: // single EmptyOP
162: return true;
163: } else if (o2.getID() == INSTANCEOF_ID) {
164: // emptyOps only accept collections
165: return (((Type) o2).impliedBy(false, Collection.class));
166: } else {
167: return false;
168: }
169: }
170:
171: protected static final boolean compute(final ExistsOp o1,
172: final Op o2) {
173: int o2ID = o2.getID();
174: if (o2ID == EXISTS_ID) {
175: // compare the operators of the exists
176: return compute((o1.u), (((ExistsOp) o2).u));
177: } else if (o2ID == INSTANCEOF_ID) {
178: // existsOps only accept collections
179: return (((Type) o2).impliedBy(false, Collection.class));
180: } else {
181: return false;
182: }
183: }
184:
185: protected static final boolean compute(final AndOp o1,
186: final AndOp o2) {
187: // and1 implies and2 if all the elements of and2 are implied by some
188: // element of and1
189: Op[] ops = o1.ops;
190: Op[] xops = o2.ops;
191: int nops = ops.length;
192: int nxops = xops.length;
193: // for all and2 elements
194: for (int j = 0; j < nxops; j++) {
195: Op uj = xops[j];
196: // for all and1 elements
197: for (int i = 0;; i++) {
198: if (i >= nops) {
199: // and2[j] isn't implied by any element of and1[]
200: return false;
201: }
202: Op ui = ops[i];
203: if (compute(ui, uj)) {
204: // and1[i] implies and2[j]
205: break;
206: }
207: }
208: }
209: // all elements of and2 are implied by some and2 element,
210: // so and1 implies and2
211: return true;
212: }
213:
214: protected static final boolean compute(final AndOp o1,
215: final InstanceOfOp o2) {
216: // andOp implies typeOp if some element of andOp implies the typeOp
217: Op[] ops = o1.ops;
218: int nops = ops.length;
219: // for all and1 elements
220: for (int i = 0; i < nops; i++) {
221: Op ui = ops[i];
222: // compare andOp[i] with o2
223: if (compute(ui, o2)) {
224: // (andOp[i] implies typeOp), so (andOp implies typeOp)
225: return true;
226: }
227: }
228: // (!(andOp implies typeOp))
229: return false;
230: }
231:
232: protected static final boolean compute(final AndOp o1, final Op o2) {
233: int o2ID = o2.getID();
234: if (o2ID == AND_ID) {
235: // compute two ands
236: return compute(o1, (AndOp) o2);
237: } else if (o2ID == INSTANCEOF_ID) {
238: // compute and with type
239: return compute(o1, (InstanceOfOp) o2);
240: }
241: // compare the andOp with a non-andOp/instanceOfOp
242: //
243: // see if all the elements of the andOp imply the given op
244: Op[] ops = o1.ops;
245: int nops = ops.length;
246: // for all andOp elements
247: for (int i = 0; i < nops; i++) {
248: Op ui = ops[i];
249: // compare andOp[i] with o2
250: if (!(compute(ui, o2))) {
251: // andOp[i] doesn't imply o2
252: if (ui.getID() == INSTANCEOF_ID) {
253: // see if the andOp is something like (and (isX) (X.method)),
254: // where "X.method" is non-static. The "is:X" in that case
255: // is a redundant check.
256: //
257: //
258: for (int j = 0;; j++) {
259: if (j >= nops) {
260: // no matching "X.method", so (!(andOp implies o2))
261: return false;
262: }
263: Op uj = ops[j];
264: if ((uj.getID() != INSTANCEOF_ID)
265: && (compute(uj, ui))) {
266: // found matching "X.method", continue to andOp[i+1]
267: break;
268: }
269: }
270: } else {
271: // andOp doesn't imply o2
272: return false;
273: }
274: }
275: }
276: // andOp implies the given op
277: return true;
278: }
279:
280: protected static final boolean compute(final FalseOp o1, final Op o2) {
281: // single FalseOP
282: return (o1 == o2);
283: }
284:
285: protected static final boolean compute(final NotOp o1, final Op o2) {
286: if (o2.getID() == NOT_ID) {
287: // compare the operator of the nots
288: return compute((o1.u1), (((NotOp) o2).u1));
289: } else {
290: return false;
291: }
292: }
293:
294: protected static final boolean compute(final OrOp o1, final OrOp o2) {
295: // or1 implies or2 if any or1 element implies any or2 element
296: Op[] ops = o1.ops;
297: Op[] xops = o2.ops;
298: int nops = ops.length;
299: int nxops = xops.length;
300: // for all or1 elements
301: for (int i = 0; i < nops; i++) {
302: Op ui = ops[i];
303: // for all or2 elements
304: for (int j = 0; j < nxops; j++) {
305: Op uj = xops[j];
306: // compare the elements
307: if (compute(ui, uj)) {
308: // (or1[i] implies or2[j]), so (or1 implies or2)
309: return true;
310: }
311: }
312: }
313: // none of the or1 elements imply any or2 element
314: return false;
315: }
316:
317: protected static final boolean compute(final OrOp o1, final Op o2) {
318: if (o2.getID() == OR_ID) {
319: // compute two ors
320: return compute(o1, (OrOp) o2);
321: }
322: // compare the orOp with a non-orOp
323: //
324: // an orOp implies an op if all element of the orOp imply the op
325: Op[] ops = o1.ops;
326: int nops = ops.length;
327: // for all orOp elements
328: for (int i = 0; i < nops; i++) {
329: Op ui = ops[i];
330: // compare orOp[i] with op
331: if (!(compute(ui, o2))) {
332: // orOp[i] doesn't imply op, so (!(orOp implies op))
333: return false;
334: }
335: }
336: // orOp implies op
337: return true;
338: }
339:
340: protected static final boolean compute(final TrueOp o1, final Op o2) {
341: // single TrueOp
342: return (o1 == o2);
343: }
344:
345: protected static final boolean compute(final ApplyOp o1, final Op o2) {
346: if (o2.getID() == APPLY_ID) {
347: // apply1 is equal to apply2 if their arguments are equal
348: ApplyOp x = (ApplyOp) o2;
349: Op u1 = o1.u1;
350: Op xu1 = x.u1;
351: // test if the operators are the same
352: if (!(u1.equals(xu1))) {
353: return false;
354: }
355: Op u2 = o1.u2;
356: Op xu2 = x.u2;
357: // test if the operators imply
358: return (compute(u2, xu2));
359: } else {
360: return false;
361: }
362: }
363:
364: protected static final boolean compute(final FieldOp o1, final Op o2) {
365: return (o1.equals(o2));
366: }
367:
368: protected static final boolean compute(final InstanceOfOp o1,
369: final Op o2) {
370: int o2ID = o2.getID();
371: if (o2ID == INSTANCEOF_ID) {
372: // test the type implications of the two instanceOfOps
373: return (((Type) o1).implies((Type) o2));
374: } else if (o2ID == AND_ID) {
375: // see if this typeOp implies all the elements of the andOp
376: Op[] ops = ((AndOp) o2).ops;
377: int nops = ops.length;
378: // for all andOp elements
379: for (int i = 0; i < nops; i++) {
380: Op ui = ops[i];
381: if (!(compute(o1, ui))) {
382: return false;
383: }
384: }
385: return true;
386: } else if (o2ID == OR_ID) {
387: // see if this typeOp implies any element of the orOp
388: Op[] ops = ((OrOp) o2).ops;
389: int nops = ops.length;
390: // for all orOp elements
391: for (int i = 0; i < nops; i++) {
392: Op ui = ops[i];
393: if (compute(o1, ui)) {
394: return true;
395: }
396: }
397: return false;
398: } else {
399: return false;
400: }
401: }
402:
403: protected static final boolean compute(final MethodOp o1,
404: final Op o2) {
405: int o2ID = o2.getID();
406: if (o2ID == METHOD_ID) {
407: // see if the methods are equal
408: return (o1.equals(o2));
409: } else if (o2ID == INSTANCEOF_ID) {
410: // see if method is non-static, e.g. "String.equals", and
411: // if it implies the given type, e.g. "is:String"
412: Method meth = o1.meth;
413: if ((meth.getModifiers() & Modifier.STATIC) == 0) {
414: Type t2 = (Type) o2;
415: Class mclass = meth.getDeclaringClass();
416: return (t2.impliedBy(false, mclass));
417: } else {
418: return false;
419: }
420: } else if (o2ID == AND_ID) {
421: // see if the andOp elements are all instance checks and/or
422: // this method
423: Op[] ops = ((AndOp) o2).ops;
424: int nops = ops.length;
425: // for all andOp elements
426: for (int i = 0; i < nops; i++) {
427: Op ui = ops[i];
428: if (!(compute(o1, ui))) {
429: return false;
430: }
431: }
432: return true;
433: } else {
434: return false;
435: }
436: }
437:
438: protected static final boolean compute(final ThisOp o1, final Op o2) {
439: // type is context-sensitive, so just see if the
440: // other op is also a thisOp
441: return (o2.getID() == THIS_ID);
442: }
443: }
|