VennExpression


1   package net.sf.saxon.expr;
2   import net.sf.saxon.functions.SystemFunction;
3   import net.sf.saxon.om.SequenceIterator;
4   import net.sf.saxon.pattern.CombinedNodeTest;
5   import net.sf.saxon.sort.DocumentOrderIterator;
6   import net.sf.saxon.sort.GlobalOrderComparer;
7   import net.sf.saxon.trans.XPathException;
8   import net.sf.saxon.type.ItemType;
9   import net.sf.saxon.type.Type;
10  import net.sf.saxon.value.EmptySequence;
11  import net.sf.saxon.value.SequenceType;
12  
13  
14  /**
15  * An expression representing a nodeset that is a union, difference, or
16  * intersection of two other NodeSets
17  */
18  
19  public class VennExpression extends BinaryExpression {
20  
21      /**
22      * Constructor
23      * @param p1 the left-hand operand
24      * @param op the operator (union, intersection, or difference)
25      * @param p2 the right-hand operand
26      */
27  
28      public VennExpression(final Expression p1, final int op, final Expression p2) {
29          super(p1, op, p2);
30      }
31  
32      /**
33      * Determine the data type of the items returned by this expression
34      * @return the data type
35      */
36  
37      public final ItemType getItemType() {
38          final ItemType t1 = operand0.getItemType();
39          final ItemType t2 = operand1.getItemType();
40          return Type.getCommonSuperType(t1, t2);
41      }
42  
43      /**
44      * Determine the static cardinality of the expression
45      */
46  
47      public final int computeCardinality() {
48          final int c1 = operand0.getCardinality();
49          final int c2 = operand1.getCardinality();
50          switch (operator) {
51              case Token.UNION:
52                  if (operand0 instanceof EmptySequence) return c2;
53                  if (operand1 instanceof EmptySequence) return c1;
54                  return c1 | c2 | StaticProperty.ALLOWS_ONE | StaticProperty.ALLOWS_MANY;
55                      // allows ZERO only if one operand allows ZERO
56              case Token.INTERSECT:
57                  if (operand0 instanceof EmptySequence) return StaticProperty.EMPTY;
58                  if (operand1 instanceof EmptySequence) return StaticProperty.EMPTY;
59                  return (c1 & c2) | StaticProperty.ALLOWS_ZERO | StaticProperty.ALLOWS_ONE;
60                      // allows MANY only if both operands allow MANY
61              case Token.EXCEPT:
62                  if (operand0 instanceof EmptySequence) return StaticProperty.EMPTY;
63                  if (operand1 instanceof EmptySequence) return c1;
64                  return c1 | StaticProperty.ALLOWS_ZERO | StaticProperty.ALLOWS_ONE;
65                      // allows MANY only if first operand allows MANY
66          }
67          return StaticProperty.ALLOWS_ZERO_OR_MORE;
68      }
69  
70      /**
71      * Get the static properties of this expression (other than its type). The result is
72      * bit-signficant. These properties are used for optimizations. In general, if
73      * property bit is set, it is true, but if it is unset, the value is unknown.
74      */
75  
76      public int computeSpecialProperties() {
77          final int prop0 = operand0.getSpecialProperties();
78          final int prop1 = operand1.getSpecialProperties();
79          int props = StaticProperty.ORDERED_NODESET;
80          if (testContextDocumentNodeSet(prop0, prop1)) {
81              props |= StaticProperty.CONTEXT_DOCUMENT_NODESET;
82          }
83          if (testSubTree(prop0, prop1)) {
84              props |= StaticProperty.SUBTREE_NODESET;
85          }
86          if (!testCreative(prop0, prop1)) {
87              props |= StaticProperty.NON_CREATIVE;
88          }
89          return props;
90      }
91  
92      /**
93       * Determine whether all the nodes in the node-set are guaranteed to
94       * come from the same document as the context node. Used for optimization.
95       */
96  
97      private boolean testContextDocumentNodeSet(final int prop0, final int prop1) {
98          switch (operator) {
99              case Token.UNION:
100                 return (prop0 & prop1 & StaticProperty.CONTEXT_DOCUMENT_NODESET) != 0;
101             case Token.INTERSECT:
102                 return ((prop0 | prop1) & StaticProperty.CONTEXT_DOCUMENT_NODESET) != 0;
103             case Token.EXCEPT:
104                 return (prop0 & StaticProperty.CONTEXT_DOCUMENT_NODESET) != 0;
105         }
106         return false;
107     }
108 
109     /**
110      * Determine whether all the nodes in the node-set are guaranteed to
111      * come from a subtree rooted at the context node. Used for optimization.
112      */
113 
114     private boolean testSubTree(final int prop0, final int prop1) {
115         switch (operator) {
116             case Token.UNION:
117                 return (prop0 & prop1 & StaticProperty.SUBTREE_NODESET) != 0;
118             case Token.INTERSECT:
119                 return ((prop0 | prop1) & StaticProperty.SUBTREE_NODESET) != 0;
120             case Token.EXCEPT:
121                 return (prop0 & StaticProperty.SUBTREE_NODESET) != 0;
122         }
123         return false;
124     }
125 
126     /**
127      * Determine whether the expression can create new nodes
128      */
129 
130     private boolean testCreative(final int prop0, final int prop1) {
131         return !(((prop0 & StaticProperty.NON_CREATIVE) == 1) &&
132                 ((prop1 & StaticProperty.NON_CREATIVE) == 1));
133     }
134 
135 
136     /**
137     * Simplify the expression
138     */
139 
140      public Expression simplify(final StaticContext env) throws XPathException {
141         operand0 = operand0.simplify(env);
142         operand1 = operand1.simplify(env);
143 
144         // If either operand is an empty sequence, simplify the expression. This can happen
145         // after reduction with constructs of the form //a[condition] | //b[not(condition)],
146         // common in XPath 1.0 because there were no conditional expressions.
147 
148         switch (operator) {
149             case Token.UNION:
150                 if (operand0 instanceof EmptySequence &&
151                         (operand1.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0) return operand1;
152                 if (operand1 instanceof EmptySequence &&
153                         (operand0.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0) return operand0;
154                 break;
155             case Token.INTERSECT:
156                 if (operand0 instanceof EmptySequence) return operand0;
157                 if (operand1 instanceof EmptySequence) return operand1;
158                 break;
159             case Token.EXCEPT:
160                 if (operand0 instanceof EmptySequence) return operand0;
161                 if (operand1 instanceof EmptySequence &&
162                         (operand0.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0) return operand0;
163                 break;
164         }
165 
166 
167 
168         // If both are axis expressions on the same axis, merge them
169         // ie. rewrite (axis::test1 | axis::test2) as axis::(test1 | test2)
170 
171         if (operand0 instanceof AxisExpression && operand1 instanceof AxisExpression) {
172             final AxisExpression a1 = (AxisExpression)operand0;
173             final AxisExpression a2 = (AxisExpression)operand1;
174             if (a1.getAxis() == a2.getAxis()) {
175                 return new AxisExpression(a1.getAxis(),
176                              new CombinedNodeTest(a1.getNodeTest(),
177                                                   operator,
178                                                   a2.getNodeTest()));
179             }
180         }
181 
182         // If both are path expressions starting the same way, merge them
183         // i.e. rewrite (/X | /Y) as /(X|Y). This applies recursively, so that
184         // /A/B/C | /A/B/D becomes /A/B/child::(C|D)
185 
186         // This optimization was previously done for all three operators. However, it's not safe for "except":
187         // A//B except A//C//B cannot be rewritten as A/descendant-or-self::node()/(B except C//B). As a quick
188         // fix, the optimization has been retained for "union" but dropped for "intersect" and "except". Need to
189         // do a more rigorous analysis of the conditions under which it is safe.
190 
191         if (operand0 instanceof PathExpression && operand1 instanceof PathExpression && operator==Token.UNION) {
192             final PathExpression path1 = (PathExpression)operand0;
193             final PathExpression path2 = (PathExpression)operand1;
194 
195             if (path1.getFirstStep().equals(path2.getFirstStep())) {
196                 final Expression path = new PathExpression(
197                         path1.getFirstStep(),
198                         new VennExpression(
199                             path1.getRemainingSteps(),
200                             operator,
201                             path2.getRemainingSteps())).simplify(env);
202                 ExpressionTool.copyLocationInfo(this, path);
203                 return path;
204             }
205         }
206 
207         // Try merging two non-positional filter expressions:
208         // A[exp0] | A[exp1] becomes A[exp0 or exp1]
209 
210         if (operand0 instanceof FilterExpression && operand1 instanceof FilterExpression) {
211             final FilterExpression exp0 = (FilterExpression)operand0;
212             final FilterExpression exp1 = (FilterExpression)operand1;
213 
214             if (!exp0.isPositional() &&
215                     !exp1.isPositional() &&
216                     exp0.getBaseExpression().equals(exp1.getBaseExpression())) {
217                 final Expression filter;
218                 switch (operator) {
219                     case Token.UNION:
220                         filter = new BooleanExpression(exp0.getFilter(),
221                                                 Token.OR,
222                                                 exp1.getFilter());
223                         break;
224                     case Token.INTERSECT:
225                         filter = new BooleanExpression(exp0.getFilter(),
226                                                 Token.AND,
227                                                 exp1.getFilter());
228                         break;
229                     case Token.EXCEPT:
230                         final FunctionCall negate2 = SystemFunction.makeSystemFunction("not", 1, env.getNamePool());
231                         final Expression[] args = new Expression[1];
232                         args[0] = exp1.getFilter();
233                         negate2.setArguments(args);
234                         filter = new BooleanExpression(exp0.getFilter(),
235                                                 Token.AND,
236                                                 negate2);
237                         break;
238                     default:
239                         throw new AssertionError  ("Unknown operator " + operator);
240                 }
241                 final Expression f = new FilterExpression(
242                         exp0.getBaseExpression(),
243                         filter, env).simplify(env);
244                 ExpressionTool.copyLocationInfo(this, filter);
245                 ExpressionTool.copyLocationInfo(this, f);
246                 return f;
247             }
248         }
249         return this;
250     }
251 
252     /**
253     * Type-check the expression
254     */
255 
256     public Expression typeCheck(final StaticContext env, final ItemType contextItemType) throws XPathException {
257 
258         operand0 = operand0.typeCheck(env, contextItemType);
259         operand1 = operand1.typeCheck(env, contextItemType);
260 
261         final RoleLocator role0 = new RoleLocator(RoleLocator.BINARY_EXPR, Token.tokens[operator], 0, null);
262         role0.setSourceLocator(this);
263         operand0 = TypeChecker.staticTypeCheck(operand0, SequenceType.NODE_SEQUENCE, false, role0, env);
264 
265         final RoleLocator role1 = new RoleLocator(RoleLocator.BINARY_EXPR, Token.tokens[operator], 1, null);
266         role1.setSourceLocator(this);
267         operand1 = TypeChecker.staticTypeCheck(operand1, SequenceType.NODE_SEQUENCE, false, role1, env);
268         return this;
269     }
270 
271 
272     /**
273     * Is this expression the same as another expression?
274     */
275 
276 //    public boolean equals(Object other) {
277 //        if (other instanceof VennExpression) {
278 //            VennExpression b = (VennExpression)other;
279 //            if (operator != b.operator) {
280 //                return false;
281 //            }
282 //            if (operand0.equals(b.operand0) && operand1.equals(b.operand1)) {
283 //               return true;
284 //            }
285 //            if (operator == Token.UNION || operator == Token.INTERSECT) {
286 //                // commutative operators: A|B == B|A
287 //                if (operand0.equals(b.operand1) && operand1.equals(b.operand0)) {
288 //                    return true;
289 //                }
290 //            }
291 //        }
292 //        return false;
293 //    }
294 
295     public int hashCode() {
296         return operand0.hashCode() ^ operand1.hashCode();
297     }
298 
299     /**
300     * Iterate over the value of the expression. The result will always be sorted in document order,
301     * with duplicates eliminated
302     * @param c The context for evaluation
303     * @return a SequenceIterator representing the union of the two operands
304     */
305 
306     public SequenceIterator iterate(final XPathContext c) throws XPathException {
307         SequenceIterator i1 = operand0.iterate(c);
308         //return Type.isNodeType(getItemType()) && isSingleton();
309         // this is a sufficient condition, but other expressions override this method
310         if (!((operand0.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0)) {
311             i1 = new DocumentOrderIterator(i1, GlobalOrderComparer.getInstance());
312         }
313         SequenceIterator i2 = operand1.iterate(c);
314         //return Type.isNodeType(getItemType()) && isSingleton();
315         // this is a sufficient condition, but other expressions override this method
316         if (!((operand1.getSpecialProperties() & StaticProperty.ORDERED_NODESET) != 0)) {
317             i2 = new DocumentOrderIterator(i2, GlobalOrderComparer.getInstance());
318         }
319         switch (operator) {
320             case Token.UNION:
321                 return new UnionEnumeration(i1, i2,
322                                             GlobalOrderComparer.getInstance());
323             case Token.INTERSECT:
324                 return new IntersectionEnumeration(i1, i2,
325                                             GlobalOrderComparer.getInstance());
326             case Token.EXCEPT:
327                 return new DifferenceEnumeration(i1, i2,
328                                             GlobalOrderComparer.getInstance());
329         }
330         throw new UnsupportedOperationException  ("Unknown operator in Set Expression");
331     }
332 
333     /**
334     * Get the effective boolean value. In the case of a union expression, this
335     * is reduced to an OR expression, for efficiency
336     */
337 
338     public boolean effectiveBooleanValue(final XPathContext context) throws XPathException {
339         if (operator == Token.UNION) {
340             return operand0.effectiveBooleanValue(context) || operand1.effectiveBooleanValue(context);
341         } else {
342             return super.effectiveBooleanValue(context);
343         }
344     }
345 
346 
347 }
348 
349 //
350 // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
351 // you may not use this file except in compliance with the License. You may obtain a copy of the
352 // License at http://www.mozilla.org/MPL/
353 //
354 // Software distributed under the License is distributed on an "AS IS" basis,
355 // WITHOUT WARRANTY OF ANY KIND, either express or implied.
356 // See the License for the specific language governing rights and limitations under the License.
357 //
358 // The Original Code is: all this file.
359 //
360 // The Initial Developer of the Original Code is Michael H. Kay.
361 //
362 // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
363 //
364 // Contributor(s): none.
365 //
366
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags