OrNode


1   /*
2   
3      Derby - Class org.apache.derby.impl.sql.compile.OrNode
4   
5      Licensed to the Apache Software Foundation (ASF) under one or more
6      contributor license agreements.  See the NOTICE file distributed with
7      this work for additional information regarding copyright ownership.
8      The ASF licenses this file to you under the Apache License, Version 2.0
9      (the "License"); you may not use this file except in compliance with
10     the License.  You may obtain a copy of the License at
11  
12        http://www.apache.org/licenses/LICENSE-2.0
13  
14     Unless required by applicable law or agreed to in writing, software
15     distributed under the License is distributed on an "AS IS" BASIS,
16     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17     See the License for the specific language governing permissions and
18     limitations under the License.
19  
20   */
21  
22  package org.apache.derby.impl.sql.compile;
23  
24  import org.apache.derby.iapi.sql.compile.C_NodeTypes;
25  
26  import org.apache.derby.iapi.sql.dictionary.DataDictionary;
27  import org.apache.derby.iapi.services.sanity.SanityManager;
28  import org.apache.derby.iapi.error.StandardException;
29  
30  import java.util.Vector  ;
31  
32  public class OrNode extends BinaryLogicalOperatorNode
33  {
34      /* Is this the 1st OR in the OR chain? */
35      private boolean firstOr;
36  
37      /**
38       * Initializer for an OrNode
39       *
40       * @param leftOperand   The left operand of the OR
41       * @param rightOperand  The right operand of the OR
42       */
43  
44      public void init(Object   leftOperand, Object   rightOperand)
45      {
46          super.init(leftOperand, rightOperand, "or");
47          this.shortCircuitValue = true;
48      }
49  
50      /**
51       * Mark this OrNode as the 1st OR in the OR chain.
52       * We will consider converting the chain to an IN list
53       * during preprocess() if all entries are of the form:
54       *      ColumnReference = expression
55       */
56      void setFirstOr()
57      {
58          firstOr = true;
59      }
60  
61      /**
62       * Bind this logical operator.  All that has to be done for binding
63       * a logical operator is to bind the operands, check that both operands
64       * are BooleanDataValue, and set the result type to BooleanDataValue.
65       *
66       * @param fromList          The query's FROM list
67       * @param subqueryList      The subquery list being built as we find SubqueryNodes
68       * @param aggregateVector   The aggregate vector being built as we find AggregateNodes
69       *
70       * @return  The new top of the expression tree.
71       *
72       * @exception StandardException     Thrown on error
73       */
74  
75      public ValueNode bindExpression(
76          FromList fromList, SubqueryList subqueryList,
77          Vector    aggregateVector)
78              throws StandardException
79      {
80          super.bindExpression(fromList, subqueryList, aggregateVector);
81          postBindFixup();
82          return this;
83      }
84      
85      /**
86       * Preprocess an expression tree.  We do a number of transformations
87       * here (including subqueries, IN lists, LIKE and BETWEEN) plus
88       * subquery flattening.
89       * NOTE: This is done before the outer ResultSetNode is preprocessed.
90       *
91       * @param   numTables           Number of tables in the DML Statement
92       * @param   outerFromList       FromList from outer query block
93       * @param   outerSubqueryList   SubqueryList from outer query block
94       * @param   outerPredicateList  PredicateList from outer query block
95       *
96       * @return      The modified expression
97       *
98       * @exception StandardException     Thrown on error
99       */
100     public ValueNode preprocess(int numTables,
101                                 FromList outerFromList,
102                                 SubqueryList outerSubqueryList,
103                                 PredicateList outerPredicateList) 
104                     throws StandardException
105     {
106         super.preprocess(numTables,
107                          outerFromList, outerSubqueryList, 
108                          outerPredicateList);
109 
110         /* If this is the first OR in the OR chain then we will
111          * consider converting it to an IN list and then performing
112          * whatever IN list conversions/optimizations are available.
113          * An OR can be converted to an IN list if all of the entries
114          * in the chain are of the form:
115          *      ColumnReference = x
116          *  or:
117          *      x = ColumnReference
118          * where all ColumnReferences are from the same table.
119          */
120         if (firstOr)
121         {
122             boolean         convert = true;
123             ColumnReference cr = null;
124             int             columnNumber = -1;
125             int             tableNumber = -1;
126 
127             for (ValueNode vn = this; vn instanceof OrNode; vn = ((OrNode) vn).getRightOperand())
128             {
129                 OrNode on = (OrNode) vn;
130                 ValueNode left = on.getLeftOperand();
131 
132                 // Is the operator an =
133                 if (!left.isRelationalOperator())
134                 {
135                     convert = false;
136                     break;
137                 }
138 
139                 if (!(((RelationalOperator)left).getOperator() == RelationalOperator.EQUALS_RELOP))
140                 {
141                     convert = false;
142                     break;
143                 }
144 
145                 BinaryRelationalOperatorNode beon = (BinaryRelationalOperatorNode)left;
146 
147                 if (beon.getLeftOperand() instanceof ColumnReference)
148                 {
149                     cr = (ColumnReference) beon.getLeftOperand();
150                     if (tableNumber == -1)
151                     {
152                         tableNumber = cr.getTableNumber();
153                         columnNumber = cr.getColumnNumber();
154                     }
155                     else if (tableNumber != cr.getTableNumber() ||
156                              columnNumber != cr.getColumnNumber())
157                     {
158                         convert = false;
159                         break;
160                     }
161                 }
162                 else if (beon.getRightOperand() instanceof ColumnReference)
163                 {
164                     cr = (ColumnReference) beon.getRightOperand();
165                     if (tableNumber == -1)
166                     {
167                         tableNumber = cr.getTableNumber();
168                         columnNumber = cr.getColumnNumber();
169                     }
170                     else if (tableNumber != cr.getTableNumber() ||
171                              columnNumber != cr.getColumnNumber())
172                     {
173                         convert = false;
174                         break;
175                     }
176                 }
177                 else
178                 {
179                     convert = false;
180                     break;
181                 }
182             }
183 
184             /* So, can we convert the OR chain? */
185             if (convert)
186             {
187                 ValueNodeList vnl = (ValueNodeList) getNodeFactory().getNode(
188                                                     C_NodeTypes.VALUE_NODE_LIST,
189                                                     getContextManager());
190                 // Build the IN list 
191                 for (ValueNode vn = this; vn instanceof OrNode; vn = ((OrNode) vn).getRightOperand())
192                 {
193                     OrNode on = (OrNode) vn;
194                     BinaryRelationalOperatorNode beon = (BinaryRelationalOperatorNode) on.getLeftOperand();
195                     if (beon.getLeftOperand() instanceof ColumnReference)
196                     {
197                         vnl.addValueNode(beon.getRightOperand());
198                     }
199                     else
200                     {
201                         vnl.addValueNode(beon.getLeftOperand());
202                     }
203                 }
204 
205                 InListOperatorNode ilon =
206                             (InListOperatorNode) getNodeFactory().getNode(
207                                             C_NodeTypes.IN_LIST_OPERATOR_NODE,
208                                             cr,
209                                             vnl,
210                                             getContextManager());
211 
212                 // Transfer the result type info to the IN list
213                 ilon.setType(getTypeServices());
214 
215                 /* We return the result of preprocess() on the
216                  * IN list so that any compilation time transformations
217                  * will be done.
218                  */
219                 return ilon.preprocess(numTables,
220                          outerFromList, outerSubqueryList, 
221                          outerPredicateList);
222             }
223         }
224 
225         return this;
226     }
227 
228     /**
229      * Eliminate NotNodes in the current query block.  We traverse the tree, 
230      * inverting ANDs and ORs and eliminating NOTs as we go.  We stop at 
231      * ComparisonOperators and boolean expressions.  We invert 
232      * ComparisonOperators and replace boolean expressions with 
233      * boolean expression = false.
234      * NOTE: Since we do not recurse under ComparisonOperators, there
235      * still could be NotNodes left in the tree.
236      *
237      * @param   underNotNode        Whether or not we are under a NotNode.
238      *                          
239      *
240      * @return      The modified expression
241      *
242      * @exception StandardException     Thrown on error
243      */
244     ValueNode eliminateNots(boolean underNotNode) 
245                     throws StandardException
246     {
247         leftOperand = leftOperand.eliminateNots(underNotNode);
248         rightOperand = rightOperand.eliminateNots(underNotNode);
249         if (! underNotNode)
250         {
251             return this;
252         }
253 
254         /* Convert the OrNode to an AndNode */
255         AndNode andNode;
256 
257         andNode = (AndNode) getNodeFactory().getNode(
258                                                     C_NodeTypes.AND_NODE,
259                                                     leftOperand,
260                                                     rightOperand,
261                                                     getContextManager());
262         andNode.setType(dataTypeServices);
263         return andNode;
264     }
265 
266     /**
267      * Finish putting an expression into conjunctive normal
268      * form.  An expression tree in conjunctive normal form meets
269      * the following criteria:
270      *      o  If the expression tree is not null,
271      *         the top level will be a chain of AndNodes terminating
272      *         in a true BooleanConstantNode.
273      *      o  The left child of an AndNode will never be an AndNode.
274      *      o  Any right-linked chain that includes an AndNode will
275      *         be entirely composed of AndNodes terminated by a true BooleanConstantNode.
276      *      o  The left child of an OrNode will never be an OrNode.
277      *      o  Any right-linked chain that includes an OrNode will
278      *         be entirely composed of OrNodes terminated by a false BooleanConstantNode.
279      *      o  ValueNodes other than AndNodes and OrNodes are considered
280      *         leaf nodes for purposes of expression normalization.
281      *         In other words, we won't do any normalization under
282      *         those nodes.
283      *
284      * In addition, we track whether or not we are under a top level AndNode.  
285      * SubqueryNodes need to know this for subquery flattening.
286      *
287      * @param   underTopAndNode     Whether or not we are under a top level AndNode.
288      *                          
289      *
290      * @return      The modified expression
291      *
292      * @exception StandardException     Thrown on error
293      */
294     public ValueNode changeToCNF(boolean underTopAndNode) 
295                     throws StandardException
296     {
297         OrNode curOr = this;
298 
299         /* If rightOperand is an AndNode, then we must generate an 
300          * OrNode above it.
301          */
302         if (rightOperand instanceof AndNode)
303         {
304             BooleanConstantNode falseNode;
305 
306             falseNode = (BooleanConstantNode) getNodeFactory().getNode(
307                                             C_NodeTypes.BOOLEAN_CONSTANT_NODE,
308                                             Boolean.FALSE,
309                                             getContextManager());
310             rightOperand = (ValueNode) getNodeFactory().getNode(
311                                                 C_NodeTypes.OR_NODE,
312                                                 rightOperand,
313                                                 falseNode,
314                                                 getContextManager());
315             ((OrNode) rightOperand).postBindFixup();
316         }
317 
318         /* We need to ensure that the right chain is terminated by
319          * a false BooleanConstantNode.
320          */
321         while (curOr.getRightOperand() instanceof OrNode)
322         {
323             curOr = (OrNode) curOr.getRightOperand();
324         }
325 
326         /* Add the false BooleanConstantNode if not there yet */
327         if (!(curOr.getRightOperand().isBooleanFalse()))
328         {
329             BooleanConstantNode falseNode;
330 
331             falseNode = (BooleanConstantNode) getNodeFactory().getNode(
332                                             C_NodeTypes.BOOLEAN_CONSTANT_NODE,
333                                             Boolean.FALSE,
334                                             getContextManager());
335             curOr.setRightOperand(
336                     (ValueNode) getNodeFactory().getNode(
337                                                 C_NodeTypes.OR_NODE,
338                                                 curOr.getRightOperand(),
339                                                 falseNode,
340                                                 getContextManager()));
341             ((OrNode) curOr.getRightOperand()).postBindFixup();
342         }
343 
344         /* If leftOperand is an OrNode, then we modify the tree from:
345          *
346          *              this
347          *             /    \
348          *          Or2     Nodex
349          *         /    \       ...
350          *      left2   right2
351          *
352          *  to:
353          *
354          *                      this
355          *                     /    \
356          *  left2.changeToCNF()      Or2
357          *                          /   \
358          *      right2.changeToCNF()     Nodex.changeToCNF()
359          *
360          *  NOTE: We could easily switch places between left2.changeToCNF() and 
361          *  right2.changeToCNF().
362          */
363 
364         while (leftOperand instanceof OrNode)
365         {
366             ValueNode newLeft;
367             OrNode    oldLeft;
368             OrNode    newRight;
369             ValueNode oldRight;
370 
371             /* For "clarity", we first get the new and old operands */
372             newLeft = ((OrNode) leftOperand).getLeftOperand();
373             oldLeft = (OrNode) leftOperand;
374             newRight = (OrNode) leftOperand;
375             oldRight = rightOperand;
376 
377             /* We then twiddle the tree to match the above diagram */
378             leftOperand = newLeft;
379             rightOperand = newRight;
380             newRight.setLeftOperand(oldLeft.getRightOperand());
381             newRight.setRightOperand(oldRight);
382         }
383 
384         /* Finally, we continue to normalize the left and right subtrees. */
385         leftOperand = leftOperand.changeToCNF(false);
386         rightOperand = rightOperand.changeToCNF(false);
387 
388         return this;
389     }
390 
391     /**
392      * Verify that changeToCNF() did its job correctly.  Verify that:
393      *      o  AndNode  - rightOperand is not instanceof OrNode
394      *                    leftOperand is not instanceof AndNode
395      *      o  OrNode   - rightOperand is not instanceof AndNode
396      *                    leftOperand is not instanceof OrNode
397      *
398      * @return      Boolean which reflects validity of the tree.
399      */
400     public boolean verifyChangeToCNF()
401     {
402         boolean isValid = true;
403 
404         if (SanityManager.ASSERT)
405         {
406             isValid = ((rightOperand instanceof OrNode) ||
407                        (rightOperand.isBooleanFalse()));
408             if (rightOperand instanceof OrNode)
409             {
410                 isValid = rightOperand.verifyChangeToCNF();
411             }
412             if (leftOperand instanceof OrNode)
413             {
414                 isValid = false;
415             }
416             else
417             {
418                 isValid = leftOperand.verifyChangeToCNF();
419             }
420         }
421 
422         return isValid;
423     }
424 
425     /**
426      * Do bind() by hand for an AndNode that was generated after bind(),
427      * eg by putAndsOnTop(). (Set the data type and nullability info.)
428      *
429      * @exception StandardException     Thrown on error
430      */
431     void postBindFixup()
432                     throws StandardException
433     {
434         setType(resolveLogicalBinaryOperator(
435                             leftOperand.getTypeServices(),
436                             rightOperand.getTypeServices()
437                                             )
438                 );
439     }
440 }
441
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags