AndNode


1   /*
2   
3      Derby - Class org.apache.derby.impl.sql.compile.AndNode
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.dictionary.DataDictionary;
25  import org.apache.derby.iapi.services.sanity.SanityManager;
26  import org.apache.derby.iapi.error.StandardException;
27  
28  import org.apache.derby.iapi.sql.compile.NodeFactory;
29  import org.apache.derby.iapi.sql.compile.C_NodeTypes;
30  
31  import java.util.Vector  ;
32  
33  public class AndNode extends BinaryLogicalOperatorNode
34  {
35  
36      /**
37       * Initializer for an AndNode
38       *
39       * @param leftOperand   The left operand of the AND
40       * @param rightOperand  The right operand of the AND
41       */
42  
43      public void init(Object   leftOperand, Object   rightOperand)
44      {
45          super.init(leftOperand, rightOperand, "and");
46          this.shortCircuitValue = false;
47      }
48  
49      /**
50       * Bind this logical operator.  All that has to be done for binding
51       * a logical operator is to bind the operands, check that both operands
52       * are BooleanDataValue, and set the result type to BooleanDataValue.
53       *
54       * @param fromList          The query's FROM list
55       * @param subqueryList      The subquery list being built as we find SubqueryNodes
56       * @param aggregateVector   The aggregate vector being built as we find AggregateNodes
57       *
58       * @return  The new top of the expression tree.
59       *
60       * @exception StandardException     Thrown on error
61       */
62  
63      public ValueNode bindExpression(
64          FromList fromList, SubqueryList subqueryList,
65          Vector   aggregateVector)
66              throws StandardException
67      {
68          super.bindExpression(fromList, subqueryList, aggregateVector);
69  
70          postBindFixup();
71          return this;
72      }
73  
74      
75      /**
76       * Preprocess an expression tree.  We do a number of transformations
77       * here (including subqueries, IN lists, LIKE and BETWEEN) plus
78       * subquery flattening.
79       * NOTE: This is done before the outer ResultSetNode is preprocessed.
80       *
81       * @param   numTables           Number of tables in the DML Statement
82       * @param   outerFromList       FromList from outer query block
83       * @param   outerSubqueryList   SubqueryList from outer query block
84       * @param   outerPredicateList  PredicateList from outer query block
85       *
86       * @return      The modified expression
87       *
88       * @exception StandardException     Thrown on error
89       */
90      public ValueNode preprocess(int numTables,
91                                  FromList outerFromList,
92                                  SubqueryList outerSubqueryList,
93                                  PredicateList outerPredicateList) 
94                      throws StandardException
95      {
96          /* If the left child is an OR, then mark it as the 1st OR in
97           * the list.  That will allow us to consider converting the OR
98           * to an IN list when we preprocess the 1st OR in the list.
99           */
100         if (leftOperand instanceof OrNode)
101         {
102             ((OrNode) leftOperand).setFirstOr();
103         }
104         leftOperand = leftOperand.preprocess(numTables,
105                                              outerFromList, outerSubqueryList,
106                                              outerPredicateList);
107         /* We need to rerun the changeToCNF() phase if our left operand
108          * is an AndNode.  This can happen due to a predicate transformation,
109          * such as the ones for LIKE and BETWEEN, underneath us.
110          */
111         if (leftOperand instanceof AndNode)
112         {
113             changeToCNF(false);
114         }
115         rightOperand = rightOperand.preprocess(numTables,
116                                                outerFromList, outerSubqueryList,
117                                                outerPredicateList);
118         return this;
119     }
120 
121     /**
122      * Eliminate NotNodes in the current query block.  We traverse the tree, 
123      * inverting ANDs and ORs and eliminating NOTs as we go.  We stop at 
124      * ComparisonOperators and boolean expressions.  We invert 
125      * ComparisonOperators and replace boolean expressions with 
126      * boolean expression = false.
127      * NOTE: Since we do not recurse under ComparisonOperators, there
128      * still could be NotNodes left in the tree.
129      *
130      * @param   underNotNode        Whether or not we are under a NotNode.
131      *                          
132      *
133      * @return      The modified expression
134      *
135      * @exception StandardException     Thrown on error
136      */
137     ValueNode eliminateNots(boolean underNotNode) 
138                     throws StandardException
139     {
140         leftOperand = leftOperand.eliminateNots(underNotNode);
141         rightOperand = rightOperand.eliminateNots(underNotNode);
142         if (! underNotNode)
143         {
144             return this;
145         }
146 
147         /* Convert the AndNode to an OrNode */
148         ValueNode   orNode;
149 
150         orNode = (ValueNode) getNodeFactory().getNode(
151                                                 C_NodeTypes.OR_NODE,
152                                                 leftOperand,
153                                                 rightOperand,
154                                                 getContextManager());
155         orNode.setType(dataTypeServices);
156         return orNode;
157     }
158 
159     /**
160      * Do the 1st step in putting an expression into conjunctive normal
161      * form.  This step ensures that the top level of the expression is
162      * a chain of AndNodes terminated by a true BooleanConstantNode.
163      *
164      * @return      The modified expression
165      *
166      * @exception StandardException     Thrown on error
167      */
168     public ValueNode putAndsOnTop() 
169                     throws StandardException
170     {
171         if (SanityManager.DEBUG)
172         SanityManager.ASSERT(rightOperand != null,
173             "rightOperand is expected to be non-null");
174         rightOperand = rightOperand.putAndsOnTop();
175 
176         return this;
177     }
178 
179     /**
180      * Verify that putAndsOnTop() did its job correctly.  Verify that the top level 
181      * of the expression is a chain of AndNodes terminated by a true BooleanConstantNode.
182      *
183      * @return      Boolean which reflects validity of the tree.
184      */
185     public boolean verifyPutAndsOnTop()
186     {
187         boolean isValid = true;
188 
189         if (SanityManager.ASSERT)
190         {
191             isValid = ((rightOperand instanceof AndNode) ||
192                        (rightOperand.isBooleanTrue()));
193 
194             if (rightOperand instanceof AndNode)
195             {
196                 isValid = rightOperand.verifyPutAndsOnTop();
197             }
198         }
199 
200         return isValid;
201     }
202 
203     /**
204      * Finish putting an expression into conjunctive normal
205      * form.  An expression tree in conjunctive normal form meets
206      * the following criteria:
207      *      o  If the expression tree is not null,
208      *         the top level will be a chain of AndNodes terminating
209      *         in a true BooleanConstantNode.
210      *      o  The left child of an AndNode will never be an AndNode.
211      *      o  Any right-linked chain that includes an AndNode will
212      *         be entirely composed of AndNodes terminated by a true BooleanConstantNode.
213      *      o  The left child of an OrNode will never be an OrNode.
214      *      o  Any right-linked chain that includes an OrNode will
215      *         be entirely composed of OrNodes terminated by a false BooleanConstantNode.
216      *      o  ValueNodes other than AndNodes and OrNodes are considered
217      *         leaf nodes for purposes of expression normalization.
218      *         In other words, we won't do any normalization under
219      *         those nodes.
220      *
221      * In addition, we track whether or not we are under a top level AndNode.  
222      * SubqueryNodes need to know this for subquery flattening.
223      *
224      * @param   underTopAndNode     Whether or not we are under a top level AndNode.
225      *                          
226      *
227      * @return      The modified expression
228      *
229      * @exception StandardException     Thrown on error
230      */
231     public ValueNode changeToCNF(boolean underTopAndNode) 
232                     throws StandardException
233     {
234         AndNode curAnd = this;
235 
236         /* Top chain will be a chain of Ands terminated by a non-AndNode.
237          * (putAndsOnTop() has taken care of this. If the last node in
238          * the chain is not a true BooleanConstantNode then we need to do the
239          * transformation to make it so.
240          */
241 
242         /* Add the true BooleanConstantNode if not there yet */
243         if (!(rightOperand instanceof AndNode) &&
244             !(rightOperand.isBooleanTrue()))
245         {
246             BooleanConstantNode trueNode;
247 
248             trueNode = (BooleanConstantNode) getNodeFactory().getNode(
249                                             C_NodeTypes.BOOLEAN_CONSTANT_NODE,
250                                             Boolean.TRUE,
251                                             getContextManager());
252             curAnd.setRightOperand(
253                     (ValueNode) getNodeFactory().getNode(
254                                             C_NodeTypes.AND_NODE,
255                                             curAnd.getRightOperand(),
256                                             trueNode,
257                                             getContextManager()));
258             ((AndNode) curAnd.getRightOperand()).postBindFixup();
259         }
260 
261         /* If leftOperand is an AndNode, then we modify the tree from:
262          *
263          *              this
264          *             /    \
265          *          And2    Nodex
266          *         /    \       ...
267          *      left2   right2
268          *
269          *  to:
270          *
271          *                      this
272          *                     /    \
273          *  left2.changeToCNF()      And2
274          *                          /   \
275          *      right2.changeToCNF()      Nodex.changeToCNF()
276          *
277          *  NOTE: We could easily switch places between left2.changeToCNF() and 
278          *  right2.changeToCNF().
279          */
280 
281         /* Pull up the AndNode chain to our left */
282         while (leftOperand instanceof AndNode)
283         {
284             ValueNode newLeft;
285             AndNode   oldLeft;
286             AndNode   newRight;
287             ValueNode oldRight;
288 
289             /* For "clarity", we first get the new and old operands */
290             newLeft = ((AndNode) leftOperand).getLeftOperand();
291             oldLeft = (AndNode) leftOperand;
292             newRight = (AndNode) leftOperand;
293             oldRight = rightOperand;
294 
295             /* We then twiddle the tree to match the above diagram */
296             leftOperand = newLeft;
297             rightOperand = newRight;
298             newRight.setLeftOperand(oldLeft.getRightOperand());
299             newRight.setRightOperand(oldRight);
300         }
301 
302         /* Finally, we continue to normalize the left and right subtrees. */
303         leftOperand = leftOperand.changeToCNF(underTopAndNode);
304         rightOperand = rightOperand.changeToCNF(underTopAndNode);
305 
306         return this;
307     }
308 
309     /**
310      * Verify that changeToCNF() did its job correctly.  Verify that:
311      *      o  AndNode  - rightOperand is not instanceof OrNode
312      *                    leftOperand is not instanceof AndNode
313      *      o  OrNode   - rightOperand is not instanceof AndNode
314      *                    leftOperand is not instanceof OrNode
315      *
316      * @return      Boolean which reflects validity of the tree.
317      */
318     public boolean verifyChangeToCNF()
319     {
320         boolean isValid = true;
321 
322         if (SanityManager.ASSERT)
323         {
324             isValid = ((rightOperand instanceof AndNode) ||
325                        (rightOperand.isBooleanTrue()));
326             if (rightOperand instanceof AndNode)
327             {
328                 isValid = rightOperand.verifyChangeToCNF();
329             }
330             if (leftOperand instanceof AndNode)
331             {
332                 isValid = false;
333             }
334             else
335             {
336                 isValid = isValid && leftOperand.verifyChangeToCNF();
337             }
338         }
339 
340         return isValid;
341     }
342 
343     /**
344      * Do bind() by hand for an AndNode that was generated after bind(),
345      * eg by putAndsOnTop(). (Set the data type and nullability info.)
346      *
347      * @exception StandardException     Thrown on error
348      */
349     void postBindFixup()
350                     throws StandardException
351     {
352         setType(resolveLogicalBinaryOperator(
353                             leftOperand.getTypeServices(),
354                             rightOperand.getTypeServices()
355                                             )
356                 );
357     }
358 }
359
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags