001: /*
002:
003: Derby - Class org.apache.derby.impl.sql.compile.OrNode
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.compile.C_NodeTypes;
025:
026: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
027: import org.apache.derby.iapi.services.sanity.SanityManager;
028: import org.apache.derby.iapi.error.StandardException;
029:
030: import java.util.Vector;
031:
032: public class OrNode extends BinaryLogicalOperatorNode {
033: /* Is this the 1st OR in the OR chain? */
034: private boolean firstOr;
035:
036: /**
037: * Initializer for an OrNode
038: *
039: * @param leftOperand The left operand of the OR
040: * @param rightOperand The right operand of the OR
041: */
042:
043: public void init(Object leftOperand, Object rightOperand) {
044: super .init(leftOperand, rightOperand, "or");
045: this .shortCircuitValue = true;
046: }
047:
048: /**
049: * Mark this OrNode as the 1st OR in the OR chain.
050: * We will consider converting the chain to an IN list
051: * during preprocess() if all entries are of the form:
052: * ColumnReference = expression
053: */
054: void setFirstOr() {
055: firstOr = true;
056: }
057:
058: /**
059: * Bind this logical operator. All that has to be done for binding
060: * a logical operator is to bind the operands, check that both operands
061: * are BooleanDataValue, and set the result type to BooleanDataValue.
062: *
063: * @param fromList The query's FROM list
064: * @param subqueryList The subquery list being built as we find SubqueryNodes
065: * @param aggregateVector The aggregate vector being built as we find AggregateNodes
066: *
067: * @return The new top of the expression tree.
068: *
069: * @exception StandardException Thrown on error
070: */
071:
072: public ValueNode bindExpression(FromList fromList,
073: SubqueryList subqueryList, Vector aggregateVector)
074: throws StandardException {
075: super .bindExpression(fromList, subqueryList, aggregateVector);
076: postBindFixup();
077: return this ;
078: }
079:
080: /**
081: * Preprocess an expression tree. We do a number of transformations
082: * here (including subqueries, IN lists, LIKE and BETWEEN) plus
083: * subquery flattening.
084: * NOTE: This is done before the outer ResultSetNode is preprocessed.
085: *
086: * @param numTables Number of tables in the DML Statement
087: * @param outerFromList FromList from outer query block
088: * @param outerSubqueryList SubqueryList from outer query block
089: * @param outerPredicateList PredicateList from outer query block
090: *
091: * @return The modified expression
092: *
093: * @exception StandardException Thrown on error
094: */
095: public ValueNode preprocess(int numTables, FromList outerFromList,
096: SubqueryList outerSubqueryList,
097: PredicateList outerPredicateList) throws StandardException {
098: super .preprocess(numTables, outerFromList, outerSubqueryList,
099: outerPredicateList);
100:
101: /* If this is the first OR in the OR chain then we will
102: * consider converting it to an IN list and then performing
103: * whatever IN list conversions/optimizations are available.
104: * An OR can be converted to an IN list if all of the entries
105: * in the chain are of the form:
106: * ColumnReference = x
107: * or:
108: * x = ColumnReference
109: * where all ColumnReferences are from the same table.
110: */
111: if (firstOr) {
112: boolean convert = true;
113: ColumnReference cr = null;
114: int columnNumber = -1;
115: int tableNumber = -1;
116:
117: for (ValueNode vn = this ; vn instanceof OrNode; vn = ((OrNode) vn)
118: .getRightOperand()) {
119: OrNode on = (OrNode) vn;
120: ValueNode left = on.getLeftOperand();
121:
122: // Is the operator an =
123: if (!left.isRelationalOperator()) {
124: convert = false;
125: break;
126: }
127:
128: if (!(((RelationalOperator) left).getOperator() == RelationalOperator.EQUALS_RELOP)) {
129: convert = false;
130: break;
131: }
132:
133: BinaryRelationalOperatorNode beon = (BinaryRelationalOperatorNode) left;
134:
135: if (beon.getLeftOperand() instanceof ColumnReference) {
136: cr = (ColumnReference) beon.getLeftOperand();
137: if (tableNumber == -1) {
138: tableNumber = cr.getTableNumber();
139: columnNumber = cr.getColumnNumber();
140: } else if (tableNumber != cr.getTableNumber()
141: || columnNumber != cr.getColumnNumber()) {
142: convert = false;
143: break;
144: }
145: } else if (beon.getRightOperand() instanceof ColumnReference) {
146: cr = (ColumnReference) beon.getRightOperand();
147: if (tableNumber == -1) {
148: tableNumber = cr.getTableNumber();
149: columnNumber = cr.getColumnNumber();
150: } else if (tableNumber != cr.getTableNumber()
151: || columnNumber != cr.getColumnNumber()) {
152: convert = false;
153: break;
154: }
155: } else {
156: convert = false;
157: break;
158: }
159: }
160:
161: /* So, can we convert the OR chain? */
162: if (convert) {
163: ValueNodeList vnl = (ValueNodeList) getNodeFactory()
164: .getNode(C_NodeTypes.VALUE_NODE_LIST,
165: getContextManager());
166: // Build the IN list
167: for (ValueNode vn = this ; vn instanceof OrNode; vn = ((OrNode) vn)
168: .getRightOperand()) {
169: OrNode on = (OrNode) vn;
170: BinaryRelationalOperatorNode beon = (BinaryRelationalOperatorNode) on
171: .getLeftOperand();
172: if (beon.getLeftOperand() instanceof ColumnReference) {
173: vnl.addValueNode(beon.getRightOperand());
174: } else {
175: vnl.addValueNode(beon.getLeftOperand());
176: }
177: }
178:
179: InListOperatorNode ilon = (InListOperatorNode) getNodeFactory()
180: .getNode(C_NodeTypes.IN_LIST_OPERATOR_NODE, cr,
181: vnl, getContextManager());
182:
183: // Transfer the result type info to the IN list
184: ilon.setType(getTypeServices());
185:
186: /* We return the result of preprocess() on the
187: * IN list so that any compilation time transformations
188: * will be done.
189: */
190: return ilon.preprocess(numTables, outerFromList,
191: outerSubqueryList, outerPredicateList);
192: }
193: }
194:
195: return this ;
196: }
197:
198: /**
199: * Eliminate NotNodes in the current query block. We traverse the tree,
200: * inverting ANDs and ORs and eliminating NOTs as we go. We stop at
201: * ComparisonOperators and boolean expressions. We invert
202: * ComparisonOperators and replace boolean expressions with
203: * boolean expression = false.
204: * NOTE: Since we do not recurse under ComparisonOperators, there
205: * still could be NotNodes left in the tree.
206: *
207: * @param underNotNode Whether or not we are under a NotNode.
208: *
209: *
210: * @return The modified expression
211: *
212: * @exception StandardException Thrown on error
213: */
214: ValueNode eliminateNots(boolean underNotNode)
215: throws StandardException {
216: leftOperand = leftOperand.eliminateNots(underNotNode);
217: rightOperand = rightOperand.eliminateNots(underNotNode);
218: if (!underNotNode) {
219: return this ;
220: }
221:
222: /* Convert the OrNode to an AndNode */
223: AndNode andNode;
224:
225: andNode = (AndNode) getNodeFactory().getNode(
226: C_NodeTypes.AND_NODE, leftOperand, rightOperand,
227: getContextManager());
228: andNode.setType(dataTypeServices);
229: return andNode;
230: }
231:
232: /**
233: * Finish putting an expression into conjunctive normal
234: * form. An expression tree in conjunctive normal form meets
235: * the following criteria:
236: * o If the expression tree is not null,
237: * the top level will be a chain of AndNodes terminating
238: * in a true BooleanConstantNode.
239: * o The left child of an AndNode will never be an AndNode.
240: * o Any right-linked chain that includes an AndNode will
241: * be entirely composed of AndNodes terminated by a true BooleanConstantNode.
242: * o The left child of an OrNode will never be an OrNode.
243: * o Any right-linked chain that includes an OrNode will
244: * be entirely composed of OrNodes terminated by a false BooleanConstantNode.
245: * o ValueNodes other than AndNodes and OrNodes are considered
246: * leaf nodes for purposes of expression normalization.
247: * In other words, we won't do any normalization under
248: * those nodes.
249: *
250: * In addition, we track whether or not we are under a top level AndNode.
251: * SubqueryNodes need to know this for subquery flattening.
252: *
253: * @param underTopAndNode Whether or not we are under a top level AndNode.
254: *
255: *
256: * @return The modified expression
257: *
258: * @exception StandardException Thrown on error
259: */
260: public ValueNode changeToCNF(boolean underTopAndNode)
261: throws StandardException {
262: OrNode curOr = this ;
263:
264: /* If rightOperand is an AndNode, then we must generate an
265: * OrNode above it.
266: */
267: if (rightOperand instanceof AndNode) {
268: BooleanConstantNode falseNode;
269:
270: falseNode = (BooleanConstantNode) getNodeFactory().getNode(
271: C_NodeTypes.BOOLEAN_CONSTANT_NODE, Boolean.FALSE,
272: getContextManager());
273: rightOperand = (ValueNode) getNodeFactory().getNode(
274: C_NodeTypes.OR_NODE, rightOperand, falseNode,
275: getContextManager());
276: ((OrNode) rightOperand).postBindFixup();
277: }
278:
279: /* We need to ensure that the right chain is terminated by
280: * a false BooleanConstantNode.
281: */
282: while (curOr.getRightOperand() instanceof OrNode) {
283: curOr = (OrNode) curOr.getRightOperand();
284: }
285:
286: /* Add the false BooleanConstantNode if not there yet */
287: if (!(curOr.getRightOperand().isBooleanFalse())) {
288: BooleanConstantNode falseNode;
289:
290: falseNode = (BooleanConstantNode) getNodeFactory().getNode(
291: C_NodeTypes.BOOLEAN_CONSTANT_NODE, Boolean.FALSE,
292: getContextManager());
293: curOr.setRightOperand((ValueNode) getNodeFactory().getNode(
294: C_NodeTypes.OR_NODE, curOr.getRightOperand(),
295: falseNode, getContextManager()));
296: ((OrNode) curOr.getRightOperand()).postBindFixup();
297: }
298:
299: /* If leftOperand is an OrNode, then we modify the tree from:
300: *
301: * this
302: * / \
303: * Or2 Nodex
304: * / \ ...
305: * left2 right2
306: *
307: * to:
308: *
309: * this
310: * / \
311: * left2.changeToCNF() Or2
312: * / \
313: * right2.changeToCNF() Nodex.changeToCNF()
314: *
315: * NOTE: We could easily switch places between left2.changeToCNF() and
316: * right2.changeToCNF().
317: */
318:
319: while (leftOperand instanceof OrNode) {
320: ValueNode newLeft;
321: OrNode oldLeft;
322: OrNode newRight;
323: ValueNode oldRight;
324:
325: /* For "clarity", we first get the new and old operands */
326: newLeft = ((OrNode) leftOperand).getLeftOperand();
327: oldLeft = (OrNode) leftOperand;
328: newRight = (OrNode) leftOperand;
329: oldRight = rightOperand;
330:
331: /* We then twiddle the tree to match the above diagram */
332: leftOperand = newLeft;
333: rightOperand = newRight;
334: newRight.setLeftOperand(oldLeft.getRightOperand());
335: newRight.setRightOperand(oldRight);
336: }
337:
338: /* Finally, we continue to normalize the left and right subtrees. */
339: leftOperand = leftOperand.changeToCNF(false);
340: rightOperand = rightOperand.changeToCNF(false);
341:
342: return this ;
343: }
344:
345: /**
346: * Verify that changeToCNF() did its job correctly. Verify that:
347: * o AndNode - rightOperand is not instanceof OrNode
348: * leftOperand is not instanceof AndNode
349: * o OrNode - rightOperand is not instanceof AndNode
350: * leftOperand is not instanceof OrNode
351: *
352: * @return Boolean which reflects validity of the tree.
353: */
354: public boolean verifyChangeToCNF() {
355: boolean isValid = true;
356:
357: if (SanityManager.ASSERT) {
358: isValid = ((rightOperand instanceof OrNode) || (rightOperand
359: .isBooleanFalse()));
360: if (rightOperand instanceof OrNode) {
361: isValid = rightOperand.verifyChangeToCNF();
362: }
363: if (leftOperand instanceof OrNode) {
364: isValid = false;
365: } else {
366: isValid = leftOperand.verifyChangeToCNF();
367: }
368: }
369:
370: return isValid;
371: }
372:
373: /**
374: * Do bind() by hand for an AndNode that was generated after bind(),
375: * eg by putAndsOnTop(). (Set the data type and nullability info.)
376: *
377: * @exception StandardException Thrown on error
378: */
379: void postBindFixup() throws StandardException {
380: setType(resolveLogicalBinaryOperator(leftOperand
381: .getTypeServices(), rightOperand.getTypeServices()));
382: }
383: }
|