001: package net.sf.saxon.expr;
002:
003: import net.sf.saxon.functions.SystemFunction;
004: import net.sf.saxon.om.SequenceIterator;
005: import net.sf.saxon.pattern.CombinedNodeTest;
006: import net.sf.saxon.sort.DocumentOrderIterator;
007: import net.sf.saxon.sort.GlobalOrderComparer;
008: import net.sf.saxon.trans.XPathException;
009: import net.sf.saxon.type.ItemType;
010: import net.sf.saxon.type.Type;
011: import net.sf.saxon.type.TypeHierarchy;
012: import net.sf.saxon.value.EmptySequence;
013: import net.sf.saxon.value.SequenceType;
014:
015: /**
016: * An expression representing a nodeset that is a union, difference, or
017: * intersection of two other NodeSets
018: */
019:
020: public class VennExpression extends BinaryExpression {
021:
022: /**
023: * Constructor
024: * @param p1 the left-hand operand
025: * @param op the operator (union, intersection, or difference)
026: * @param p2 the right-hand operand
027: */
028:
029: public VennExpression(final Expression p1, final int op,
030: final Expression p2) {
031: super (p1, op, p2);
032: }
033:
034: /**
035: * Determine the data type of the items returned by this expression
036: * @return the data type
037: * @param th
038: */
039:
040: public final ItemType getItemType(TypeHierarchy th) {
041: final ItemType t1 = operand0.getItemType(th);
042: final ItemType t2 = operand1.getItemType(th);
043: return Type.getCommonSuperType(t1, t2, th);
044: }
045:
046: /**
047: * Determine the static cardinality of the expression
048: */
049:
050: public final int computeCardinality() {
051: final int c1 = operand0.getCardinality();
052: final int c2 = operand1.getCardinality();
053: switch (operator) {
054: case Token.UNION:
055: if (operand0 instanceof EmptySequence)
056: return c2;
057: if (operand1 instanceof EmptySequence)
058: return c1;
059: return c1 | c2 | StaticProperty.ALLOWS_ONE
060: | StaticProperty.ALLOWS_MANY;
061: // allows ZERO only if one operand allows ZERO
062: case Token.INTERSECT:
063: if (operand0 instanceof EmptySequence)
064: return StaticProperty.EMPTY;
065: if (operand1 instanceof EmptySequence)
066: return StaticProperty.EMPTY;
067: return (c1 & c2) | StaticProperty.ALLOWS_ZERO
068: | StaticProperty.ALLOWS_ONE;
069: // allows MANY only if both operands allow MANY
070: case Token.EXCEPT:
071: if (operand0 instanceof EmptySequence)
072: return StaticProperty.EMPTY;
073: if (operand1 instanceof EmptySequence)
074: return c1;
075: return c1 | StaticProperty.ALLOWS_ZERO
076: | StaticProperty.ALLOWS_ONE;
077: // allows MANY only if first operand allows MANY
078: }
079: return StaticProperty.ALLOWS_ZERO_OR_MORE;
080: }
081:
082: /**
083: * Get the static properties of this expression (other than its type). The result is
084: * bit-signficant. These properties are used for optimizations. In general, if
085: * property bit is set, it is true, but if it is unset, the value is unknown.
086: */
087:
088: public int computeSpecialProperties() {
089: final int prop0 = operand0.getSpecialProperties();
090: final int prop1 = operand1.getSpecialProperties();
091: int props = StaticProperty.ORDERED_NODESET;
092: if (testContextDocumentNodeSet(prop0, prop1)) {
093: props |= StaticProperty.CONTEXT_DOCUMENT_NODESET;
094: }
095: if (testSubTree(prop0, prop1)) {
096: props |= StaticProperty.SUBTREE_NODESET;
097: }
098: if (!testCreative(prop0, prop1)) {
099: props |= StaticProperty.NON_CREATIVE;
100: }
101: return props;
102: }
103:
104: /**
105: * Determine whether all the nodes in the node-set are guaranteed to
106: * come from the same document as the context node. Used for optimization.
107: */
108:
109: private boolean testContextDocumentNodeSet(final int prop0,
110: final int prop1) {
111: switch (operator) {
112: case Token.UNION:
113: return (prop0 & prop1 & StaticProperty.CONTEXT_DOCUMENT_NODESET) != 0;
114: case Token.INTERSECT:
115: return ((prop0 | prop1) & StaticProperty.CONTEXT_DOCUMENT_NODESET) != 0;
116: case Token.EXCEPT:
117: return (prop0 & StaticProperty.CONTEXT_DOCUMENT_NODESET) != 0;
118: }
119: return false;
120: }
121:
122: /**
123: * Determine whether all the nodes in the node-set are guaranteed to
124: * come from a subtree rooted at the context node. Used for optimization.
125: */
126:
127: private boolean testSubTree(final int prop0, final int prop1) {
128: switch (operator) {
129: case Token.UNION:
130: return (prop0 & prop1 & StaticProperty.SUBTREE_NODESET) != 0;
131: case Token.INTERSECT:
132: return ((prop0 | prop1) & StaticProperty.SUBTREE_NODESET) != 0;
133: case Token.EXCEPT:
134: return (prop0 & StaticProperty.SUBTREE_NODESET) != 0;
135: }
136: return false;
137: }
138:
139: /**
140: * Determine whether the expression can create new nodes
141: */
142:
143: private boolean testCreative(final int prop0, final int prop1) {
144: return !(((prop0 & StaticProperty.NON_CREATIVE) == 1) && ((prop1 & StaticProperty.NON_CREATIVE) == 1));
145: }
146:
147: /**
148: * Simplify the expression
149: */
150:
151: public Expression simplify(final StaticContext env)
152: throws XPathException {
153: operand0 = operand0.simplify(env);
154: operand1 = operand1.simplify(env);
155:
156: // If either operand is an empty sequence, simplify the expression. This can happen
157: // after reduction with constructs of the form //a[condition] | //b[not(condition)],
158: // common in XPath 1.0 because there were no conditional expressions.
159:
160: switch (operator) {
161: case Token.UNION:
162: if (operand0 instanceof EmptySequence
163: && (operand1.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0)
164: return operand1;
165: if (operand1 instanceof EmptySequence
166: && (operand0.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0)
167: return operand0;
168: break;
169: case Token.INTERSECT:
170: if (operand0 instanceof EmptySequence)
171: return operand0;
172: if (operand1 instanceof EmptySequence)
173: return operand1;
174: break;
175: case Token.EXCEPT:
176: if (operand0 instanceof EmptySequence)
177: return operand0;
178: if (operand1 instanceof EmptySequence
179: && (operand0.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0)
180: return operand0;
181: break;
182: }
183:
184: // If both are axis expressions on the same axis, merge them
185: // ie. rewrite (axis::test1 | axis::test2) as axis::(test1 | test2)
186:
187: if (operand0 instanceof AxisExpression
188: && operand1 instanceof AxisExpression) {
189: final AxisExpression a1 = (AxisExpression) operand0;
190: final AxisExpression a2 = (AxisExpression) operand1;
191: if (a1.getAxis() == a2.getAxis()) {
192: return new AxisExpression(a1.getAxis(),
193: new CombinedNodeTest(a1.getNodeTest(),
194: operator, a2.getNodeTest()));
195: }
196: }
197:
198: // If both are path expressions starting the same way, merge them
199: // i.e. rewrite (/X | /Y) as /(X|Y). This applies recursively, so that
200: // /A/B/C | /A/B/D becomes /A/B/child::(C|D)
201:
202: // This optimization was previously done for all three operators. However, it's not safe for "except":
203: // A//B except A//C//B cannot be rewritten as A/descendant-or-self::node()/(B except C//B). As a quick
204: // fix, the optimization has been retained for "union" but dropped for "intersect" and "except". Need to
205: // do a more rigorous analysis of the conditions under which it is safe.
206:
207: if (operand0 instanceof PathExpression
208: && operand1 instanceof PathExpression
209: && operator == Token.UNION) {
210: final PathExpression path1 = (PathExpression) operand0;
211: final PathExpression path2 = (PathExpression) operand1;
212:
213: if (path1.getFirstStep().equals(path2.getFirstStep())) {
214: final Expression path = new PathExpression(path1
215: .getFirstStep(), new VennExpression(path1
216: .getRemainingSteps(), operator, path2
217: .getRemainingSteps())).simplify(env);
218: ExpressionTool.copyLocationInfo(this , path);
219: return path;
220: }
221: }
222:
223: // Try merging two non-positional filter expressions:
224: // A[exp0] | A[exp1] becomes A[exp0 or exp1]
225:
226: if (operand0 instanceof FilterExpression
227: && operand1 instanceof FilterExpression) {
228: final FilterExpression exp0 = (FilterExpression) operand0;
229: final FilterExpression exp1 = (FilterExpression) operand1;
230:
231: final TypeHierarchy th = env.getNamePool()
232: .getTypeHierarchy();
233: if (!exp0.isPositional(th)
234: && !exp1.isPositional(th)
235: && exp0.getBaseExpression().equals(
236: exp1.getBaseExpression())) {
237: final Expression filter;
238: switch (operator) {
239: case Token.UNION:
240: filter = new BooleanExpression(exp0.getFilter(),
241: Token.OR, exp1.getFilter());
242: break;
243: case Token.INTERSECT:
244: filter = new BooleanExpression(exp0.getFilter(),
245: Token.AND, exp1.getFilter());
246: break;
247: case Token.EXCEPT:
248: final FunctionCall negate2 = SystemFunction
249: .makeSystemFunction("not", 1, env
250: .getNamePool());
251: final Expression[] args = new Expression[1];
252: args[0] = exp1.getFilter();
253: negate2.setArguments(args);
254: filter = new BooleanExpression(exp0.getFilter(),
255: Token.AND, negate2);
256: break;
257: default:
258: throw new AssertionError("Unknown operator "
259: + operator);
260: }
261: final Expression f = new FilterExpression(exp0
262: .getBaseExpression(), filter, env)
263: .simplify(env);
264: ExpressionTool.copyLocationInfo(this , filter);
265: ExpressionTool.copyLocationInfo(this , f);
266: return f;
267: }
268: }
269: return this ;
270: }
271:
272: /**
273: * Type-check the expression
274: */
275:
276: public Expression typeCheck(final StaticContext env,
277: final ItemType contextItemType) throws XPathException {
278:
279: operand0 = operand0.typeCheck(env, contextItemType);
280: operand1 = operand1.typeCheck(env, contextItemType);
281:
282: final RoleLocator role0 = new RoleLocator(
283: RoleLocator.BINARY_EXPR, Token.tokens[operator], 0,
284: null);
285: role0.setSourceLocator(this );
286: operand0 = TypeChecker.staticTypeCheck(operand0,
287: SequenceType.NODE_SEQUENCE, false, role0, env);
288:
289: final RoleLocator role1 = new RoleLocator(
290: RoleLocator.BINARY_EXPR, Token.tokens[operator], 1,
291: null);
292: role1.setSourceLocator(this );
293: operand1 = TypeChecker.staticTypeCheck(operand1,
294: SequenceType.NODE_SEQUENCE, false, role1, env);
295: return this ;
296: }
297:
298: /**
299: * Is this expression the same as another expression?
300: */
301:
302: // public boolean equals(Object other) {
303: // if (other instanceof VennExpression) {
304: // VennExpression b = (VennExpression)other;
305: // if (operator != b.operator) {
306: // return false;
307: // }
308: // if (operand0.equals(b.operand0) && operand1.equals(b.operand1)) {
309: // return true;
310: // }
311: // if (operator == Token.UNION || operator == Token.INTERSECT) {
312: // // commutative operators: A|B == B|A
313: // if (operand0.equals(b.operand1) && operand1.equals(b.operand0)) {
314: // return true;
315: // }
316: // }
317: // }
318: // return false;
319: // }
320: public int hashCode() {
321: return operand0.hashCode() ^ operand1.hashCode();
322: }
323:
324: /**
325: * Iterate over the value of the expression. The result will always be sorted in document order,
326: * with duplicates eliminated
327: * @param c The context for evaluation
328: * @return a SequenceIterator representing the union of the two operands
329: */
330:
331: public SequenceIterator iterate(final XPathContext c)
332: throws XPathException {
333: SequenceIterator i1 = operand0.iterate(c);
334: //return Type.isNodeType(getItemType()) && isSingleton();
335: // this is a sufficient condition, but other expressions override this method
336: if (!((operand0.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0)) {
337: i1 = new DocumentOrderIterator(i1, GlobalOrderComparer
338: .getInstance());
339: }
340: SequenceIterator i2 = operand1.iterate(c);
341: //return Type.isNodeType(getItemType()) && isSingleton();
342: // this is a sufficient condition, but other expressions override this method
343: if (!((operand1.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0)) {
344: i2 = new DocumentOrderIterator(i2, GlobalOrderComparer
345: .getInstance());
346: }
347: switch (operator) {
348: case Token.UNION:
349: return new UnionEnumeration(i1, i2, GlobalOrderComparer
350: .getInstance());
351: case Token.INTERSECT:
352: return new IntersectionEnumeration(i1, i2,
353: GlobalOrderComparer.getInstance());
354: case Token.EXCEPT:
355: return new DifferenceEnumeration(i1, i2,
356: GlobalOrderComparer.getInstance());
357: }
358: throw new UnsupportedOperationException(
359: "Unknown operator in Set Expression");
360: }
361:
362: /**
363: * Get the effective boolean value. In the case of a union expression, this
364: * is reduced to an OR expression, for efficiency
365: */
366:
367: public boolean effectiveBooleanValue(final XPathContext context)
368: throws XPathException {
369: if (operator == Token.UNION) {
370: return operand0.effectiveBooleanValue(context)
371: || operand1.effectiveBooleanValue(context);
372: } else {
373: return super .effectiveBooleanValue(context);
374: }
375: }
376:
377: }
378:
379: //
380: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
381: // you may not use this file except in compliance with the License. You may obtain a copy of the
382: // License at http://www.mozilla.org/MPL/
383: //
384: // Software distributed under the License is distributed on an "AS IS" basis,
385: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
386: // See the License for the specific language governing rights and limitations under the License.
387: //
388: // The Original Code is: all this file.
389: //
390: // The Initial Developer of the Original Code is Michael H. Kay.
391: //
392: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
393: //
394: // Contributor(s): none.
395: //
|