001: package net.sf.saxon.expr;
002:
003: import net.sf.saxon.om.Item;
004: import net.sf.saxon.om.SequenceIterator;
005: import net.sf.saxon.sort.AtomicComparer;
006: import net.sf.saxon.sort.CodepointCollator;
007: import net.sf.saxon.trans.DynamicError;
008: import net.sf.saxon.trans.StaticError;
009: import net.sf.saxon.trans.XPathException;
010: import net.sf.saxon.type.*;
011: import net.sf.saxon.value.*;
012: import net.sf.saxon.functions.Position;
013: import net.sf.saxon.functions.SystemFunction;
014: import net.sf.saxon.functions.Minimax;
015:
016: import java.util.Comparator;
017:
018: /**
019: * GeneralComparison: a boolean expression that compares two expressions
020: * for equals, not-equals, greater-than or less-than. This implements the operators
021: * =, !=, <, >, etc. This implementation is not used when in backwards-compatible mode
022: */
023:
024: public class GeneralComparison extends BinaryExpression {
025:
026: protected int singletonOperator;
027: protected AtomicComparer comparer;
028:
029: /**
030: * Create a relational expression identifying the two operands and the operator
031: *
032: * @param p0 the left-hand operand
033: * @param op the operator, as a token returned by the Tokenizer (e.g. Token.LT)
034: * @param p1 the right-hand operand
035: */
036:
037: public GeneralComparison(Expression p0, int op, Expression p1) {
038: super (p0, op, p1);
039: singletonOperator = getSingletonOperator(op);
040: }
041:
042: /**
043: * Determine the static cardinality. Returns [1..1]
044: */
045:
046: public int computeCardinality() {
047: return StaticProperty.EXACTLY_ONE;
048: }
049:
050: /**
051: * Type-check the expression
052: *
053: * @return the checked expression
054: */
055:
056: public Expression typeCheck(StaticContext env,
057: ItemType contextItemType) throws XPathException {
058:
059: final TypeHierarchy th = env.getNamePool().getTypeHierarchy();
060:
061: operand0 = operand0.typeCheck(env, contextItemType);
062: operand1 = operand1.typeCheck(env, contextItemType);
063:
064: // If either operand is statically empty, return false
065:
066: if (operand0 == EmptySequence.getInstance()
067: || operand1 == EmptySequence.getInstance()) {
068: return BooleanValue.FALSE;
069: }
070:
071: // Neither operand needs to be sorted
072:
073: Optimizer opt = env.getConfiguration().getOptimizer();
074: operand0 = ExpressionTool.unsorted(opt, operand0, false);
075: operand1 = ExpressionTool.unsorted(opt, operand1, false);
076:
077: SequenceType atomicType = SequenceType.ATOMIC_SEQUENCE;
078:
079: RoleLocator role0 = new RoleLocator(RoleLocator.BINARY_EXPR,
080: Token.tokens[operator], 0, null);
081: role0.setSourceLocator(this );
082: operand0 = TypeChecker.staticTypeCheck(operand0, atomicType,
083: false, role0, env);
084:
085: RoleLocator role1 = new RoleLocator(RoleLocator.BINARY_EXPR,
086: Token.tokens[operator], 1, null);
087: role1.setSourceLocator(this );
088: operand1 = TypeChecker.staticTypeCheck(operand1, atomicType,
089: false, role1, env);
090:
091: ItemType t0 = operand0.getItemType(th);
092: ItemType t1 = operand1.getItemType(th);
093:
094: int c0 = operand0.getCardinality();
095: int c1 = operand1.getCardinality();
096:
097: if (c0 == StaticProperty.EMPTY || c1 == StaticProperty.EMPTY) {
098: return BooleanValue.FALSE;
099: }
100:
101: if (t0 == Type.ANY_ATOMIC_TYPE
102: || t0 == Type.UNTYPED_ATOMIC_TYPE
103: || t1 == Type.ANY_ATOMIC_TYPE
104: || t1 == Type.UNTYPED_ATOMIC_TYPE) {
105: // then no static type checking is possible
106: } else {
107: int pt0 = t0.getPrimitiveType();
108: int pt1 = t1.getPrimitiveType();
109: if (!Type.isComparable(pt0, pt1)) {
110: StaticError err = new StaticError("Cannot compare "
111: + t0.toString(env.getNamePool()) + " to "
112: + t1.toString(env.getNamePool()));
113: err.setErrorCode("XPTY0004");
114: err.setIsTypeError(true);
115: throw err;
116: }
117: }
118:
119: if (c0 == StaticProperty.EXACTLY_ONE
120: && c1 == StaticProperty.EXACTLY_ONE
121: && t0 != Type.ANY_ATOMIC_TYPE
122: && t1 != Type.ANY_ATOMIC_TYPE) {
123:
124: // Use a value comparison if both arguments are singletons, and if the comparison operator to
125: // be used can be determined.
126:
127: Expression e0 = operand0;
128: Expression e1 = operand1;
129:
130: if (t0 == Type.UNTYPED_ATOMIC_TYPE) {
131: if (t1 == Type.UNTYPED_ATOMIC_TYPE) {
132: e0 = new CastExpression(operand0, Type.STRING_TYPE,
133: false);
134: adoptChildExpression(e0);
135: e1 = new CastExpression(operand1, Type.STRING_TYPE,
136: false);
137: adoptChildExpression(e1);
138: } else if (th.isSubType(t1, Type.NUMBER_TYPE)) {
139: e0 = new CastExpression(operand0, Type.DOUBLE_TYPE,
140: false);
141: adoptChildExpression(e0);
142: } else {
143: e0 = new CastExpression(operand0, (AtomicType) t1,
144: false);
145: adoptChildExpression(e0);
146: }
147: } else if (t1 == Type.UNTYPED_ATOMIC_TYPE) {
148: if (th.isSubType(t0, Type.NUMBER_TYPE)) {
149: e1 = new CastExpression(operand1, Type.DOUBLE_TYPE,
150: false);
151: adoptChildExpression(e1);
152: } else {
153: e1 = new CastExpression(operand1, (AtomicType) t0,
154: false);
155: adoptChildExpression(e1);
156: }
157: }
158:
159: ValueComparison vc = new ValueComparison(e0,
160: singletonOperator, e1);
161: ExpressionTool.copyLocationInfo(this , vc);
162: vc.setParentExpression(getParentExpression());
163: return vc.simplify(env).typeCheck(env, contextItemType);
164: }
165:
166: Comparator comp = env.getCollation(env
167: .getDefaultCollationName());
168: if (comp == null) {
169: comp = CodepointCollator.getInstance();
170: }
171: comparer = new AtomicComparer(comp, env.getConfiguration());
172:
173: // evaluate the expression now if both arguments are constant
174:
175: if ((operand0 instanceof Value) && (operand1 instanceof Value)) {
176: return (AtomicValue) evaluateItem(env
177: .makeEarlyEvaluationContext());
178: }
179:
180: return this ;
181: }
182:
183: private static Expression makeMinOrMax(Expression exp,
184: StaticContext env, String function) {
185: FunctionCall fn = SystemFunction.makeSystemFunction(function,
186: 1, env.getNamePool());
187: Expression[] args = { exp };
188: fn.setArguments(args);
189: ((Minimax) fn).setIgnoreNaN(true);
190: return fn;
191: }
192:
193: /**
194: * Optimize the expression
195: *
196: * @return the checked expression
197: */
198:
199: public Expression optimize(Optimizer opt, StaticContext env,
200: ItemType contextItemType) throws XPathException {
201:
202: final TypeHierarchy th = env.getNamePool().getTypeHierarchy();
203:
204: operand0 = operand0.optimize(opt, env, contextItemType);
205: operand1 = operand1.optimize(opt, env, contextItemType);
206:
207: // If either operand is statically empty, return false
208:
209: if (operand0 == EmptySequence.getInstance()
210: || operand1 == EmptySequence.getInstance()) {
211: return BooleanValue.FALSE;
212: }
213:
214: // Neither operand needs to be sorted
215:
216: operand0 = ExpressionTool.unsorted(opt, operand0, false);
217: operand1 = ExpressionTool.unsorted(opt, operand1, false);
218:
219: ItemType t0 = operand0.getItemType(th);
220: ItemType t1 = operand1.getItemType(th);
221:
222: int c0 = operand0.getCardinality();
223: int c1 = operand1.getCardinality();
224:
225: // Check if neither argument allows a sequence of >1
226:
227: if (!Cardinality.allowsMany(c0) && !Cardinality.allowsMany(c1)) {
228:
229: // Use a singleton comparison if both arguments are singletons
230:
231: SingletonComparison sc = new SingletonComparison(operand0,
232: singletonOperator, operand1);
233: ExpressionTool.copyLocationInfo(this , sc);
234: sc.setParentExpression(getParentExpression());
235: sc
236: .setComparator(comparer, env
237: .makeEarlyEvaluationContext());
238: return sc.optimize(opt, env, contextItemType);
239: }
240:
241: // see if second argument is a singleton...
242:
243: if (!Cardinality.allowsMany(c0)) {
244:
245: // if first argument is a singleton, reverse the arguments
246: GeneralComparison mc = getInverseComparison();
247: ExpressionTool.copyLocationInfo(this , mc);
248: mc.setParentExpression(getParentExpression());
249: mc.comparer = comparer;
250: return mc.optimize(opt, env, contextItemType);
251: }
252:
253: if (c0 == StaticProperty.EXACTLY_ONE
254: && c1 == StaticProperty.EXACTLY_ONE
255: && t0 != Type.ANY_ATOMIC_TYPE
256: && t1 != Type.ANY_ATOMIC_TYPE) {
257:
258: // Use a value comparison if both arguments are singletons, and if the comparison operator to
259: // be used can be determined.
260:
261: Expression e0 = operand0;
262: Expression e1 = operand1;
263:
264: if (t0 == Type.UNTYPED_ATOMIC_TYPE) {
265: if (t1 == Type.UNTYPED_ATOMIC_TYPE) {
266: e0 = new CastExpression(operand0, Type.STRING_TYPE,
267: false);
268: adoptChildExpression(e0);
269: e1 = new CastExpression(operand1, Type.STRING_TYPE,
270: false);
271: adoptChildExpression(e1);
272: } else if (th.isSubType(t1, Type.NUMBER_TYPE)) {
273: e0 = new CastExpression(operand0, Type.DOUBLE_TYPE,
274: false);
275: adoptChildExpression(e0);
276: } else {
277: e0 = new CastExpression(operand0, (AtomicType) t1,
278: false);
279: adoptChildExpression(e0);
280: }
281: } else if (t1 == Type.UNTYPED_ATOMIC_TYPE) {
282: if (th.isSubType(t0, Type.NUMBER_TYPE)) {
283: e1 = new CastExpression(operand1, Type.DOUBLE_TYPE,
284: false);
285: adoptChildExpression(e1);
286: } else {
287: e1 = new CastExpression(operand1, (AtomicType) t0,
288: false);
289: adoptChildExpression(e1);
290: }
291: }
292:
293: ValueComparison vc = new ValueComparison(e0,
294: singletonOperator, e1);
295: ExpressionTool.copyLocationInfo(this , vc);
296: vc.setParentExpression(getParentExpression());
297: return vc.simplify(env).typeCheck(env, contextItemType)
298: .optimize(opt, env, contextItemType);
299: }
300:
301: Comparator comp = env.getCollation(env
302: .getDefaultCollationName());
303: if (comp == null) {
304: comp = CodepointCollator.getInstance();
305: }
306: comparer = new AtomicComparer(comp, env.getConfiguration());
307:
308: // If the operator is gt, ge, lt, le then replace X < Y by min(X) < max(Y) or
309: // by (some $x in X satisfies $x lt Y)
310:
311: // This optimization is done only in the case where at least one of the
312: // sequences is known to be purely numeric. It isn't safe if both sequences
313: // contain untyped atomic values, because in that case, the type of the
314: // comparison isn't known in advance. For example [(1, U1) < ("fred", U2)]
315: // involves both string and numeric comparisons.
316:
317: if (operator != Token.EQUALS
318: && operator != Token.NE
319: && (th.isSubType(t0, Type.NUMBER_TYPE) || th.isSubType(
320: t1, Type.NUMBER_TYPE))) {
321:
322: Expression e0 = operand0;
323: if (!th.isSubType(t0, Type.NUMBER_TYPE)) {
324: RoleLocator role = new RoleLocator(
325: RoleLocator.BINARY_EXPR,
326: Token.tokens[operator], 0, null);
327: role.setSourceLocator(this );
328: e0 = TypeChecker
329: .staticTypeCheck(e0,
330: SequenceType.NUMERIC_SEQUENCE, false,
331: role, env);
332: }
333: Expression e1 = operand1;
334: if (!th.isSubType(t1, Type.NUMBER_TYPE)) {
335: RoleLocator role = new RoleLocator(
336: RoleLocator.BINARY_EXPR,
337: Token.tokens[operator], 1, null);
338: role.setSourceLocator(this );
339: e1 = TypeChecker
340: .staticTypeCheck(e1,
341: SequenceType.NUMERIC_SEQUENCE, false,
342: role, env);
343: }
344:
345: if (c1 == StaticProperty.EXACTLY_ONE) {
346:
347: // If second operand is a singleton, rewrite as
348: // some $x in E0 satisfies $x op E1
349:
350: // System.err.println("** using quantified optimization R **");
351: RangeVariableDeclaration decl = new RangeVariableDeclaration();
352: decl.setVariableName("qq:" + decl.hashCode());
353: SequenceType type = SequenceType.makeSequenceType(e0
354: .getItemType(th), StaticProperty.EXACTLY_ONE);
355: decl.setRequiredType(type);
356:
357: VariableReference var = new VariableReference(decl);
358: ValueComparison vc = new ValueComparison(var,
359: singletonOperator, e1);
360: QuantifiedExpression qe = new QuantifiedExpression();
361: qe.setOperator(Token.SOME);
362: qe.setVariableDeclaration(decl);
363: qe.setSequence(e0);
364: qe.setAction(vc);
365: qe.setParentExpression(getParentExpression());
366: return qe.typeCheck(env, contextItemType);
367:
368: } else {
369:
370: // If neither operand is known to be a singleton, rewrite as (for example)
371: // min(E0) op max(E1)
372:
373: // System.err.println("** using minimax optimization **");
374: ValueComparison vc;
375: switch (operator) {
376: case Token.LT:
377: case Token.LE:
378: vc = new ValueComparison(makeMinOrMax(e0, env,
379: "min"), singletonOperator, makeMinOrMax(e1,
380: env, "max"));
381: break;
382: case Token.GT:
383: case Token.GE:
384: vc = new ValueComparison(makeMinOrMax(e0, env,
385: "max"), singletonOperator, makeMinOrMax(e1,
386: env, "min"));
387: break;
388: default:
389: throw new UnsupportedOperationException(
390: "Unknown operator " + operator);
391: }
392:
393: ExpressionTool.copyLocationInfo(this , vc);
394: vc.setParentExpression(getParentExpression());
395: return vc.typeCheck(env, contextItemType);
396: }
397: }
398:
399: // look for (N to M = I)
400:
401: if (operand0 instanceof RangeExpression
402: && th.isSubType(operand1.getItemType(th),
403: Type.INTEGER_TYPE)
404: && !Cardinality.allowsMany(operand1.getCardinality())) {
405: Expression min = ((RangeExpression) operand0).operand0;
406: Expression max = ((RangeExpression) operand0).operand1;
407: if (operand1 instanceof Position) {
408: PositionRange pr = new PositionRange(min, max);
409: ExpressionTool.copyLocationInfo(this , pr);
410: pr.setParentExpression(getParentExpression());
411: return pr;
412: } else {
413: IntegerRangeTest ir = new IntegerRangeTest(operand1,
414: min, max);
415: ExpressionTool.copyLocationInfo(this , ir);
416: ir.setParentExpression(getParentExpression());
417: return ir;
418: }
419: }
420:
421: if (operand0 instanceof IntegerRange
422: && th.isSubType(operand1.getItemType(th),
423: Type.INTEGER_TYPE)
424: && !Cardinality.allowsMany(operand1.getCardinality())) {
425: long min = ((IntegerRange) operand0).getStart();
426: long max = ((IntegerRange) operand0).getEnd();
427: if (operand1 instanceof Position) {
428: PositionRange pr = new PositionRange(new IntegerValue(
429: min), new IntegerValue(max));
430: ExpressionTool.copyLocationInfo(this , pr);
431: pr.setParentExpression(getParentExpression());
432: return pr;
433: } else {
434: IntegerRangeTest ir = new IntegerRangeTest(operand1,
435: new IntegerValue(min), new IntegerValue(max));
436: ExpressionTool.copyLocationInfo(this , ir);
437: ir.setParentExpression(getParentExpression());
438: return ir;
439: }
440: }
441:
442: // evaluate the expression now if both arguments are constant
443:
444: if ((operand0 instanceof Value) && (operand1 instanceof Value)) {
445: return (AtomicValue) evaluateItem(env
446: .makeEarlyEvaluationContext());
447: }
448:
449: return this ;
450: }
451:
452: /**
453: * Evaluate the expression in a given context
454: *
455: * @param context the given context for evaluation
456: * @return a BooleanValue representing the result of the numeric comparison of the two operands
457: */
458:
459: public Item evaluateItem(XPathContext context)
460: throws XPathException {
461: return BooleanValue.get(effectiveBooleanValue(context));
462: }
463:
464: /**
465: * Evaluate the expression in a boolean context
466: *
467: * @param context the given context for evaluation
468: * @return a boolean representing the result of the numeric comparison of the two operands
469: */
470:
471: public boolean effectiveBooleanValue(XPathContext context)
472: throws XPathException {
473:
474: try {
475: SequenceIterator iter1 = operand0.iterate(context);
476: SequenceIterator iter2 = operand1.iterate(context);
477:
478: Value seq2 = SequenceExtent.makeSequenceExtent(iter2);
479: // we choose seq2 because it's more likely to be a singleton
480: int count2 = seq2.getLength();
481:
482: if (count2 == 0) {
483: return false;
484: }
485:
486: if (count2 == 1) {
487: AtomicValue s2 = (AtomicValue) seq2.itemAt(0);
488: while (true) {
489: AtomicValue s1 = (AtomicValue) iter1.next();
490: if (s1 == null) {
491: break;
492: }
493: if (compare(s1, singletonOperator, s2, comparer,
494: context)) {
495: return true;
496: }
497: }
498: return false;
499: }
500:
501: while (true) {
502: AtomicValue s1 = (AtomicValue) iter1.next();
503: if (s1 == null) {
504: break;
505: }
506: SequenceIterator e2 = seq2.iterate(null);
507: while (true) {
508: AtomicValue s2 = (AtomicValue) e2.next();
509: if (s2 == null) {
510: break;
511: }
512: if (compare(s1, singletonOperator, s2, comparer,
513: context)) {
514: return true;
515: }
516: }
517: }
518:
519: return false;
520: } catch (DynamicError e) {
521: // re-throw the exception with location information added
522: if (e.getXPathContext() == null) {
523: e.setXPathContext(context);
524: }
525: if (e.getLocator() == null) {
526: e.setLocator(this );
527: }
528: throw e;
529: } catch (ValidationException e) {
530: DynamicError err = new DynamicError(e);
531: err.setXPathContext(context);
532: if (e.getLineNumber() == -1) {
533: err.setLocator(this );
534: } else {
535: err.setLocator(e);
536: }
537: err.setErrorCode(e.getErrorCodeLocalPart());
538: throw err;
539: }
540:
541: }
542:
543: /**
544: * Compare two atomic values
545: */
546:
547: protected static boolean compare(AtomicValue a1, int operator,
548: AtomicValue a2, AtomicComparer comparer,
549: XPathContext context) throws XPathException {
550:
551: AtomicValue v1 = a1;
552: AtomicValue v2 = a2;
553: if (a1 instanceof UntypedAtomicValue) {
554: if (a2 instanceof NumericValue) {
555: v1 = a1.convert(Type.DOUBLE, context);
556: } else if (a2 instanceof UntypedAtomicValue) {
557: // the spec says convert it to a string, but this doesn't affect the outcome
558: } else {
559: final TypeHierarchy th = context.getNamePool()
560: .getTypeHierarchy();
561: v1 = a1.convert(a2.getItemType(th).getPrimitiveType(),
562: context);
563: }
564: }
565: if (a2 instanceof UntypedAtomicValue) {
566: if (a1 instanceof NumericValue) {
567: v2 = a2.convert(Type.DOUBLE, context);
568: } else if (a1 instanceof UntypedAtomicValue) {
569: // the spec says convert it to a string, but this doesn't affect the outcome
570: } else {
571: final TypeHierarchy th = context.getNamePool()
572: .getTypeHierarchy();
573: v2 = a2.convert(a1.getItemType(th).getPrimitiveType(),
574: context);
575: }
576: }
577: return ValueComparison.compare(v1, operator, v2, comparer);
578:
579: }
580:
581: /**
582: * Determine the data type of the expression
583: *
584: * @return Type.BOOLEAN
585: * @param th
586: */
587:
588: public ItemType getItemType(TypeHierarchy th) {
589: return Type.BOOLEAN_TYPE;
590: }
591:
592: /**
593: * Return the singleton form of the comparison operator, e.g. FEQ for EQUALS, FGT for GT
594: */
595:
596: private static int getSingletonOperator(int op) {
597: switch (op) {
598: case Token.EQUALS:
599: return Token.FEQ;
600: case Token.GE:
601: return Token.FGE;
602: case Token.NE:
603: return Token.FNE;
604: case Token.LT:
605: return Token.FLT;
606: case Token.GT:
607: return Token.FGT;
608: case Token.LE:
609: return Token.FLE;
610: default:
611: return op;
612: }
613: }
614:
615: protected GeneralComparison getInverseComparison() {
616: return new GeneralComparison(operand1, Token.inverse(operator),
617: operand0);
618: }
619:
620: protected String displayOperator() {
621: return "many-to-many " + super .displayOperator();
622: }
623:
624: }
625:
626: //
627: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
628: // you may not use this file except in compliance with the License. You may obtain a copy of the
629: // License at http://www.mozilla.org/MPL/
630: //
631: // Software distributed under the License is distributed on an "AS IS" basis,
632: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
633: // See the License for the specific language governing rights and limitations under the License.
634: //
635: // The Original Code is: all this file.
636: //
637: // The Initial Developer of the Original Code is Michael H. Kay.
638: //
639: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
640: //
641: // Contributor(s): none.
642: //
|