001: /*
002:
003: Derby - Class org.apache.derby.impl.sql.compile.AndNode
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.sql.compile;
023:
024: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
025: import org.apache.derby.iapi.services.sanity.SanityManager;
026: import org.apache.derby.iapi.error.StandardException;
027:
028: import org.apache.derby.iapi.sql.compile.NodeFactory;
029: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
030:
031: import java.util.Vector;
032:
033: public class AndNode extends BinaryLogicalOperatorNode {
034:
035: /**
036: * Initializer for an AndNode
037: *
038: * @param leftOperand The left operand of the AND
039: * @param rightOperand The right operand of the AND
040: */
041:
042: public void init(Object leftOperand, Object rightOperand) {
043: super .init(leftOperand, rightOperand, "and");
044: this .shortCircuitValue = false;
045: }
046:
047: /**
048: * Bind this logical operator. All that has to be done for binding
049: * a logical operator is to bind the operands, check that both operands
050: * are BooleanDataValue, and set the result type to BooleanDataValue.
051: *
052: * @param fromList The query's FROM list
053: * @param subqueryList The subquery list being built as we find SubqueryNodes
054: * @param aggregateVector The aggregate vector being built as we find AggregateNodes
055: *
056: * @return The new top of the expression tree.
057: *
058: * @exception StandardException Thrown on error
059: */
060:
061: public ValueNode bindExpression(FromList fromList,
062: SubqueryList subqueryList, Vector aggregateVector)
063: throws StandardException {
064: super .bindExpression(fromList, subqueryList, aggregateVector);
065:
066: postBindFixup();
067: return this ;
068: }
069:
070: /**
071: * Preprocess an expression tree. We do a number of transformations
072: * here (including subqueries, IN lists, LIKE and BETWEEN) plus
073: * subquery flattening.
074: * NOTE: This is done before the outer ResultSetNode is preprocessed.
075: *
076: * @param numTables Number of tables in the DML Statement
077: * @param outerFromList FromList from outer query block
078: * @param outerSubqueryList SubqueryList from outer query block
079: * @param outerPredicateList PredicateList from outer query block
080: *
081: * @return The modified expression
082: *
083: * @exception StandardException Thrown on error
084: */
085: public ValueNode preprocess(int numTables, FromList outerFromList,
086: SubqueryList outerSubqueryList,
087: PredicateList outerPredicateList) throws StandardException {
088: /* If the left child is an OR, then mark it as the 1st OR in
089: * the list. That will allow us to consider converting the OR
090: * to an IN list when we preprocess the 1st OR in the list.
091: */
092: if (leftOperand instanceof OrNode) {
093: ((OrNode) leftOperand).setFirstOr();
094: }
095: leftOperand = leftOperand.preprocess(numTables, outerFromList,
096: outerSubqueryList, outerPredicateList);
097: /* We need to rerun the changeToCNF() phase if our left operand
098: * is an AndNode. This can happen due to a predicate transformation,
099: * such as the ones for LIKE and BETWEEN, underneath us.
100: */
101: if (leftOperand instanceof AndNode) {
102: changeToCNF(false);
103: }
104: rightOperand = rightOperand.preprocess(numTables,
105: outerFromList, outerSubqueryList, outerPredicateList);
106: return this ;
107: }
108:
109: /**
110: * Eliminate NotNodes in the current query block. We traverse the tree,
111: * inverting ANDs and ORs and eliminating NOTs as we go. We stop at
112: * ComparisonOperators and boolean expressions. We invert
113: * ComparisonOperators and replace boolean expressions with
114: * boolean expression = false.
115: * NOTE: Since we do not recurse under ComparisonOperators, there
116: * still could be NotNodes left in the tree.
117: *
118: * @param underNotNode Whether or not we are under a NotNode.
119: *
120: *
121: * @return The modified expression
122: *
123: * @exception StandardException Thrown on error
124: */
125: ValueNode eliminateNots(boolean underNotNode)
126: throws StandardException {
127: leftOperand = leftOperand.eliminateNots(underNotNode);
128: rightOperand = rightOperand.eliminateNots(underNotNode);
129: if (!underNotNode) {
130: return this ;
131: }
132:
133: /* Convert the AndNode to an OrNode */
134: ValueNode orNode;
135:
136: orNode = (ValueNode) getNodeFactory().getNode(
137: C_NodeTypes.OR_NODE, leftOperand, rightOperand,
138: getContextManager());
139: orNode.setType(dataTypeServices);
140: return orNode;
141: }
142:
143: /**
144: * Do the 1st step in putting an expression into conjunctive normal
145: * form. This step ensures that the top level of the expression is
146: * a chain of AndNodes terminated by a true BooleanConstantNode.
147: *
148: * @return The modified expression
149: *
150: * @exception StandardException Thrown on error
151: */
152: public ValueNode putAndsOnTop() throws StandardException {
153: if (SanityManager.DEBUG)
154: SanityManager.ASSERT(rightOperand != null,
155: "rightOperand is expected to be non-null");
156: rightOperand = rightOperand.putAndsOnTop();
157:
158: return this ;
159: }
160:
161: /**
162: * Verify that putAndsOnTop() did its job correctly. Verify that the top level
163: * of the expression is a chain of AndNodes terminated by a true BooleanConstantNode.
164: *
165: * @return Boolean which reflects validity of the tree.
166: */
167: public boolean verifyPutAndsOnTop() {
168: boolean isValid = true;
169:
170: if (SanityManager.ASSERT) {
171: isValid = ((rightOperand instanceof AndNode) || (rightOperand
172: .isBooleanTrue()));
173:
174: if (rightOperand instanceof AndNode) {
175: isValid = rightOperand.verifyPutAndsOnTop();
176: }
177: }
178:
179: return isValid;
180: }
181:
182: /**
183: * Finish putting an expression into conjunctive normal
184: * form. An expression tree in conjunctive normal form meets
185: * the following criteria:
186: * o If the expression tree is not null,
187: * the top level will be a chain of AndNodes terminating
188: * in a true BooleanConstantNode.
189: * o The left child of an AndNode will never be an AndNode.
190: * o Any right-linked chain that includes an AndNode will
191: * be entirely composed of AndNodes terminated by a true BooleanConstantNode.
192: * o The left child of an OrNode will never be an OrNode.
193: * o Any right-linked chain that includes an OrNode will
194: * be entirely composed of OrNodes terminated by a false BooleanConstantNode.
195: * o ValueNodes other than AndNodes and OrNodes are considered
196: * leaf nodes for purposes of expression normalization.
197: * In other words, we won't do any normalization under
198: * those nodes.
199: *
200: * In addition, we track whether or not we are under a top level AndNode.
201: * SubqueryNodes need to know this for subquery flattening.
202: *
203: * @param underTopAndNode Whether or not we are under a top level AndNode.
204: *
205: *
206: * @return The modified expression
207: *
208: * @exception StandardException Thrown on error
209: */
210: public ValueNode changeToCNF(boolean underTopAndNode)
211: throws StandardException {
212: AndNode curAnd = this ;
213:
214: /* Top chain will be a chain of Ands terminated by a non-AndNode.
215: * (putAndsOnTop() has taken care of this. If the last node in
216: * the chain is not a true BooleanConstantNode then we need to do the
217: * transformation to make it so.
218: */
219:
220: /* Add the true BooleanConstantNode if not there yet */
221: if (!(rightOperand instanceof AndNode)
222: && !(rightOperand.isBooleanTrue())) {
223: BooleanConstantNode trueNode;
224:
225: trueNode = (BooleanConstantNode) getNodeFactory().getNode(
226: C_NodeTypes.BOOLEAN_CONSTANT_NODE, Boolean.TRUE,
227: getContextManager());
228: curAnd.setRightOperand((ValueNode) getNodeFactory()
229: .getNode(C_NodeTypes.AND_NODE,
230: curAnd.getRightOperand(), trueNode,
231: getContextManager()));
232: ((AndNode) curAnd.getRightOperand()).postBindFixup();
233: }
234:
235: /* If leftOperand is an AndNode, then we modify the tree from:
236: *
237: * this
238: * / \
239: * And2 Nodex
240: * / \ ...
241: * left2 right2
242: *
243: * to:
244: *
245: * this
246: * / \
247: * left2.changeToCNF() And2
248: * / \
249: * right2.changeToCNF() Nodex.changeToCNF()
250: *
251: * NOTE: We could easily switch places between left2.changeToCNF() and
252: * right2.changeToCNF().
253: */
254:
255: /* Pull up the AndNode chain to our left */
256: while (leftOperand instanceof AndNode) {
257: ValueNode newLeft;
258: AndNode oldLeft;
259: AndNode newRight;
260: ValueNode oldRight;
261:
262: /* For "clarity", we first get the new and old operands */
263: newLeft = ((AndNode) leftOperand).getLeftOperand();
264: oldLeft = (AndNode) leftOperand;
265: newRight = (AndNode) leftOperand;
266: oldRight = rightOperand;
267:
268: /* We then twiddle the tree to match the above diagram */
269: leftOperand = newLeft;
270: rightOperand = newRight;
271: newRight.setLeftOperand(oldLeft.getRightOperand());
272: newRight.setRightOperand(oldRight);
273: }
274:
275: /* Finally, we continue to normalize the left and right subtrees. */
276: leftOperand = leftOperand.changeToCNF(underTopAndNode);
277: rightOperand = rightOperand.changeToCNF(underTopAndNode);
278:
279: return this ;
280: }
281:
282: /**
283: * Verify that changeToCNF() did its job correctly. Verify that:
284: * o AndNode - rightOperand is not instanceof OrNode
285: * leftOperand is not instanceof AndNode
286: * o OrNode - rightOperand is not instanceof AndNode
287: * leftOperand is not instanceof OrNode
288: *
289: * @return Boolean which reflects validity of the tree.
290: */
291: public boolean verifyChangeToCNF() {
292: boolean isValid = true;
293:
294: if (SanityManager.ASSERT) {
295: isValid = ((rightOperand instanceof AndNode) || (rightOperand
296: .isBooleanTrue()));
297: if (rightOperand instanceof AndNode) {
298: isValid = rightOperand.verifyChangeToCNF();
299: }
300: if (leftOperand instanceof AndNode) {
301: isValid = false;
302: } else {
303: isValid = isValid && leftOperand.verifyChangeToCNF();
304: }
305: }
306:
307: return isValid;
308: }
309:
310: /**
311: * Do bind() by hand for an AndNode that was generated after bind(),
312: * eg by putAndsOnTop(). (Set the data type and nullability info.)
313: *
314: * @exception StandardException Thrown on error
315: */
316: void postBindFixup() throws StandardException {
317: setType(resolveLogicalBinaryOperator(leftOperand
318: .getTypeServices(), rightOperand.getTypeServices()));
319: }
320: }
|