--- /dev/null
+/*\r
+\r
+ Derby - Class org.apache.derby.impl.sql.compile.OrNode\r
+\r
+ Licensed to the Apache Software Foundation (ASF) under one or more\r
+ contributor license agreements. See the NOTICE file distributed with\r
+ this work for additional information regarding copyright ownership.\r
+ The ASF licenses this file to you under the Apache License, Version 2.0\r
+ (the "License"); you may not use this file except in compliance with\r
+ the License. You may obtain a copy of the License at\r
+\r
+ http://www.apache.org/licenses/LICENSE-2.0\r
+\r
+ Unless required by applicable law or agreed to in writing, software\r
+ distributed under the License is distributed on an "AS IS" BASIS,\r
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ See the License for the specific language governing permissions and\r
+ limitations under the License.\r
+\r
+ */\r
+\r
+package org.apache.derby.impl.sql.compile;\r
+\r
+import org.apache.derby.iapi.sql.compile.C_NodeTypes;\r
+\r
+import org.apache.derby.iapi.sql.dictionary.DataDictionary;\r
+import org.apache.derby.iapi.services.sanity.SanityManager;\r
+import org.apache.derby.iapi.error.StandardException;\r
+\r
+import java.util.Vector;\r
+\r
+public class OrNode extends BinaryLogicalOperatorNode\r
+{\r
+ /* Is this the 1st OR in the OR chain? */\r
+ private boolean firstOr;\r
+\r
+ /**\r
+ * Initializer for an OrNode\r
+ *\r
+ * @param leftOperand The left operand of the OR\r
+ * @param rightOperand The right operand of the OR\r
+ */\r
+\r
+ public void init(Object leftOperand, Object rightOperand)\r
+ {\r
+ super.init(leftOperand, rightOperand, "or");\r
+ this.shortCircuitValue = true;\r
+ }\r
+\r
+ /**\r
+ * Mark this OrNode as the 1st OR in the OR chain.\r
+ * We will consider converting the chain to an IN list\r
+ * during preprocess() if all entries are of the form:\r
+ * ColumnReference = expression\r
+ */\r
+ void setFirstOr()\r
+ {\r
+ firstOr = true;\r
+ }\r
+\r
+ /**\r
+ * Bind this logical operator. All that has to be done for binding\r
+ * a logical operator is to bind the operands, check that both operands\r
+ * are BooleanDataValue, and set the result type to BooleanDataValue.\r
+ *\r
+ * @param fromList The query's FROM list\r
+ * @param subqueryList The subquery list being built as we find SubqueryNodes\r
+ * @param aggregateVector The aggregate vector being built as we find AggregateNodes\r
+ *\r
+ * @return The new top of the expression tree.\r
+ *\r
+ * @exception StandardException Thrown on error\r
+ */\r
+\r
+ public ValueNode bindExpression(\r
+ FromList fromList, SubqueryList subqueryList,\r
+ Vector aggregateVector)\r
+ throws StandardException\r
+ {\r
+ super.bindExpression(fromList, subqueryList, aggregateVector);\r
+ postBindFixup();\r
+ return this;\r
+ }\r
+ \r
+ /**\r
+ * Preprocess an expression tree. We do a number of transformations\r
+ * here (including subqueries, IN lists, LIKE and BETWEEN) plus\r
+ * subquery flattening.\r
+ * NOTE: This is done before the outer ResultSetNode is preprocessed.\r
+ *\r
+ * @param numTables Number of tables in the DML Statement\r
+ * @param outerFromList FromList from outer query block\r
+ * @param outerSubqueryList SubqueryList from outer query block\r
+ * @param outerPredicateList PredicateList from outer query block\r
+ *\r
+ * @return The modified expression\r
+ *\r
+ * @exception StandardException Thrown on error\r
+ */\r
+ public ValueNode preprocess(int numTables,\r
+ FromList outerFromList,\r
+ SubqueryList outerSubqueryList,\r
+ PredicateList outerPredicateList) \r
+ throws StandardException\r
+ {\r
+ super.preprocess(numTables,\r
+ outerFromList, outerSubqueryList, \r
+ outerPredicateList);\r
+\r
+ /* If this is the first OR in the OR chain then we will\r
+ * consider converting it to an IN list and then performing\r
+ * whatever IN list conversions/optimizations are available.\r
+ * An OR can be converted to an IN list if all of the entries\r
+ * in the chain are of the form:\r
+ * ColumnReference = x\r
+ * or:\r
+ * x = ColumnReference\r
+ * where all ColumnReferences are from the same table.\r
+ */\r
+ if (firstOr)\r
+ {\r
+ boolean convert = true;\r
+ ColumnReference cr = null;\r
+ int columnNumber = -1;\r
+ int tableNumber = -1;\r
+\r
+ for (ValueNode vn = this; vn instanceof OrNode; vn = ((OrNode) vn).getRightOperand())\r
+ {\r
+ OrNode on = (OrNode) vn;\r
+ ValueNode left = on.getLeftOperand();\r
+\r
+ // Is the operator an =\r
+ if (!left.isRelationalOperator())\r
+ {\r
+ /* If the operator is an IN-list disguised as a relational\r
+ * operator then we can still convert it--we'll just\r
+ * combine the existing IN-list ("left") with the new IN-\r
+ * list values. So check for that case now.\r
+ */ \r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ /* At the time of writing the only way a call to\r
+ * left.isRelationalOperator() would return false for\r
+ * a BinaryRelationalOperatorNode was if that node\r
+ * was for an IN-list probe predicate. That's why we\r
+ * we can get by with the simple "instanceof" check\r
+ * below. But if we're running in SANE mode, do a\r
+ * quick check to make sure that's still valid.\r
+ */\r
+ BinaryRelationalOperatorNode bron = null;\r
+ if (left instanceof BinaryRelationalOperatorNode)\r
+ {\r
+ bron = (BinaryRelationalOperatorNode)left;\r
+ if (!bron.isInListProbeNode())\r
+ {\r
+ SanityManager.THROWASSERT(\r
+ "isRelationalOperator() unexpectedly returned "\r
+ + "false for a BinaryRelationalOperatorNode.");\r
+ }\r
+ }\r
+ }\r
+\r
+ convert = (left instanceof BinaryRelationalOperatorNode);\r
+ if (!convert)\r
+ break;\r
+ }\r
+\r
+ if (!(((RelationalOperator)left).getOperator() == RelationalOperator.EQUALS_RELOP))\r
+ {\r
+ convert = false;\r
+ break;\r
+ }\r
+\r
+ BinaryRelationalOperatorNode bron = (BinaryRelationalOperatorNode)left;\r
+\r
+ if (bron.getLeftOperand() instanceof ColumnReference)\r
+ {\r
+ cr = (ColumnReference) bron.getLeftOperand();\r
+ if (tableNumber == -1)\r
+ {\r
+ tableNumber = cr.getTableNumber();\r
+ columnNumber = cr.getColumnNumber();\r
+ }\r
+ else if (tableNumber != cr.getTableNumber() ||\r
+ columnNumber != cr.getColumnNumber())\r
+ {\r
+ convert = false;\r
+ break;\r
+ }\r
+ }\r
+ else if (bron.getRightOperand() instanceof ColumnReference)\r
+ {\r
+ cr = (ColumnReference) bron.getRightOperand();\r
+ if (tableNumber == -1)\r
+ {\r
+ tableNumber = cr.getTableNumber();\r
+ columnNumber = cr.getColumnNumber();\r
+ }\r
+ else if (tableNumber != cr.getTableNumber() ||\r
+ columnNumber != cr.getColumnNumber())\r
+ {\r
+ convert = false;\r
+ break;\r
+ }\r
+ }\r
+ else\r
+ {\r
+ convert = false;\r
+ break;\r
+ }\r
+ }\r
+\r
+ /* So, can we convert the OR chain? */\r
+ if (convert)\r
+ {\r
+ ValueNodeList vnl = (ValueNodeList) getNodeFactory().getNode(\r
+ C_NodeTypes.VALUE_NODE_LIST,\r
+ getContextManager());\r
+ // Build the IN list \r
+ for (ValueNode vn = this; vn instanceof OrNode; vn = ((OrNode) vn).getRightOperand())\r
+ {\r
+ OrNode on = (OrNode) vn;\r
+ BinaryRelationalOperatorNode bron =\r
+ (BinaryRelationalOperatorNode) on.getLeftOperand();\r
+ if (bron.isInListProbeNode())\r
+ {\r
+ /* If we have an OR between multiple IN-lists on the same\r
+ * column then just combine them into a single IN-list.\r
+ * Ex.\r
+ *\r
+ * select ... from T1 where i in (2, 3) or i in (7, 10)\r
+ *\r
+ * effectively becomes:\r
+ *\r
+ * select ... from T1 where i in (2, 3, 7, 10).\r
+ */\r
+ vnl.destructiveAppend(\r
+ bron.getInListOp().getRightOperandList());\r
+ }\r
+ else if (bron.getLeftOperand() instanceof ColumnReference)\r
+ {\r
+ vnl.addValueNode(bron.getRightOperand());\r
+ }\r
+ else\r
+ {\r
+ vnl.addValueNode(bron.getLeftOperand());\r
+ }\r
+ }\r
+\r
+ InListOperatorNode ilon =\r
+ (InListOperatorNode) getNodeFactory().getNode(\r
+ C_NodeTypes.IN_LIST_OPERATOR_NODE,\r
+ cr,\r
+ vnl,\r
+ getContextManager());\r
+\r
+ // Transfer the result type info to the IN list\r
+ ilon.setType(getTypeServices());\r
+\r
+ /* We return the result of preprocess() on the\r
+ * IN list so that any compilation time transformations\r
+ * will be done.\r
+ */\r
+ return ilon.preprocess(numTables,\r
+ outerFromList, outerSubqueryList, \r
+ outerPredicateList);\r
+ }\r
+ }\r
+\r
+ return this;\r
+ }\r
+\r
+ /**\r
+ * Eliminate NotNodes in the current query block. We traverse the tree, \r
+ * inverting ANDs and ORs and eliminating NOTs as we go. We stop at \r
+ * ComparisonOperators and boolean expressions. We invert \r
+ * ComparisonOperators and replace boolean expressions with \r
+ * boolean expression = false.\r
+ * NOTE: Since we do not recurse under ComparisonOperators, there\r
+ * still could be NotNodes left in the tree.\r
+ *\r
+ * @param underNotNode Whether or not we are under a NotNode.\r
+ * \r
+ *\r
+ * @return The modified expression\r
+ *\r
+ * @exception StandardException Thrown on error\r
+ */\r
+ ValueNode eliminateNots(boolean underNotNode) \r
+ throws StandardException\r
+ {\r
+ leftOperand = leftOperand.eliminateNots(underNotNode);\r
+ rightOperand = rightOperand.eliminateNots(underNotNode);\r
+ if (! underNotNode)\r
+ {\r
+ return this;\r
+ }\r
+\r
+ /* Convert the OrNode to an AndNode */\r
+ AndNode andNode;\r
+\r
+ andNode = (AndNode) getNodeFactory().getNode(\r
+ C_NodeTypes.AND_NODE,\r
+ leftOperand,\r
+ rightOperand,\r
+ getContextManager());\r
+ andNode.setType(getTypeServices());\r
+ return andNode;\r
+ }\r
+\r
+ /**\r
+ * Finish putting an expression into conjunctive normal\r
+ * form. An expression tree in conjunctive normal form meets\r
+ * the following criteria:\r
+ * o If the expression tree is not null,\r
+ * the top level will be a chain of AndNodes terminating\r
+ * in a true BooleanConstantNode.\r
+ * o The left child of an AndNode will never be an AndNode.\r
+ * o Any right-linked chain that includes an AndNode will\r
+ * be entirely composed of AndNodes terminated by a true BooleanConstantNode.\r
+ * o The left child of an OrNode will never be an OrNode.\r
+ * o Any right-linked chain that includes an OrNode will\r
+ * be entirely composed of OrNodes terminated by a false BooleanConstantNode.\r
+ * o ValueNodes other than AndNodes and OrNodes are considered\r
+ * leaf nodes for purposes of expression normalization.\r
+ * In other words, we won't do any normalization under\r
+ * those nodes.\r
+ *\r
+ * In addition, we track whether or not we are under a top level AndNode. \r
+ * SubqueryNodes need to know this for subquery flattening.\r
+ *\r
+ * @param underTopAndNode Whether or not we are under a top level AndNode.\r
+ * \r
+ *\r
+ * @return The modified expression\r
+ *\r
+ * @exception StandardException Thrown on error\r
+ */\r
+ public ValueNode changeToCNF(boolean underTopAndNode) \r
+ throws StandardException\r
+ {\r
+ OrNode curOr = this;\r
+\r
+ /* If rightOperand is an AndNode, then we must generate an \r
+ * OrNode above it.\r
+ */\r
+ if (rightOperand instanceof AndNode)\r
+ {\r
+ BooleanConstantNode falseNode;\r
+\r
+ falseNode = (BooleanConstantNode) getNodeFactory().getNode(\r
+ C_NodeTypes.BOOLEAN_CONSTANT_NODE,\r
+ Boolean.FALSE,\r
+ getContextManager());\r
+ rightOperand = (ValueNode) getNodeFactory().getNode(\r
+ C_NodeTypes.OR_NODE,\r
+ rightOperand,\r
+ falseNode,\r
+ getContextManager());\r
+ ((OrNode) rightOperand).postBindFixup();\r
+ }\r
+\r
+ /* We need to ensure that the right chain is terminated by\r
+ * a false BooleanConstantNode.\r
+ */\r
+ while (curOr.getRightOperand() instanceof OrNode)\r
+ {\r
+ curOr = (OrNode) curOr.getRightOperand();\r
+ }\r
+\r
+ /* Add the false BooleanConstantNode if not there yet */\r
+ if (!(curOr.getRightOperand().isBooleanFalse()))\r
+ {\r
+ BooleanConstantNode falseNode;\r
+\r
+ falseNode = (BooleanConstantNode) getNodeFactory().getNode(\r
+ C_NodeTypes.BOOLEAN_CONSTANT_NODE,\r
+ Boolean.FALSE,\r
+ getContextManager());\r
+ curOr.setRightOperand(\r
+ (ValueNode) getNodeFactory().getNode(\r
+ C_NodeTypes.OR_NODE,\r
+ curOr.getRightOperand(),\r
+ falseNode,\r
+ getContextManager()));\r
+ ((OrNode) curOr.getRightOperand()).postBindFixup();\r
+ }\r
+\r
+ /* If leftOperand is an OrNode, then we modify the tree from:\r
+ *\r
+ * this\r
+ * / \\r
+ * Or2 Nodex\r
+ * / \ ...\r
+ * left2 right2\r
+ *\r
+ * to:\r
+ *\r
+ * this\r
+ * / \\r
+ * left2.changeToCNF() Or2\r
+ * / \\r
+ * right2.changeToCNF() Nodex.changeToCNF()\r
+ *\r
+ * NOTE: We could easily switch places between left2.changeToCNF() and \r
+ * right2.changeToCNF().\r
+ */\r
+\r
+ while (leftOperand instanceof OrNode)\r
+ {\r
+ ValueNode newLeft;\r
+ OrNode oldLeft;\r
+ OrNode newRight;\r
+ ValueNode oldRight;\r
+\r
+ /* For "clarity", we first get the new and old operands */\r
+ newLeft = ((OrNode) leftOperand).getLeftOperand();\r
+ oldLeft = (OrNode) leftOperand;\r
+ newRight = (OrNode) leftOperand;\r
+ oldRight = rightOperand;\r
+\r
+ /* We then twiddle the tree to match the above diagram */\r
+ leftOperand = newLeft;\r
+ rightOperand = newRight;\r
+ newRight.setLeftOperand(oldLeft.getRightOperand());\r
+ newRight.setRightOperand(oldRight);\r
+ }\r
+\r
+ /* Finally, we continue to normalize the left and right subtrees. */\r
+ leftOperand = leftOperand.changeToCNF(false);\r
+ rightOperand = rightOperand.changeToCNF(false);\r
+\r
+ return this;\r
+ }\r
+\r
+ /**\r
+ * Verify that changeToCNF() did its job correctly. Verify that:\r
+ * o AndNode - rightOperand is not instanceof OrNode\r
+ * leftOperand is not instanceof AndNode\r
+ * o OrNode - rightOperand is not instanceof AndNode\r
+ * leftOperand is not instanceof OrNode\r
+ *\r
+ * @return Boolean which reflects validity of the tree.\r
+ */\r
+ public boolean verifyChangeToCNF()\r
+ {\r
+ boolean isValid = true;\r
+\r
+ if (SanityManager.ASSERT)\r
+ {\r
+ isValid = ((rightOperand instanceof OrNode) ||\r
+ (rightOperand.isBooleanFalse()));\r
+ if (rightOperand instanceof OrNode)\r
+ {\r
+ isValid = rightOperand.verifyChangeToCNF();\r
+ }\r
+ if (leftOperand instanceof OrNode)\r
+ {\r
+ isValid = false;\r
+ }\r
+ else\r
+ {\r
+ isValid = leftOperand.verifyChangeToCNF();\r
+ }\r
+ }\r
+\r
+ return isValid;\r
+ }\r
+\r
+ /**\r
+ * Do bind() by hand for an AndNode that was generated after bind(),\r
+ * eg by putAndsOnTop(). (Set the data type and nullability info.)\r
+ *\r
+ * @exception StandardException Thrown on error\r
+ */\r
+ void postBindFixup()\r
+ throws StandardException\r
+ {\r
+ setType(resolveLogicalBinaryOperator(\r
+ leftOperand.getTypeServices(),\r
+ rightOperand.getTypeServices()\r
+ )\r
+ );\r
+ }\r
+}\r
projects / Benchmarks_CSolver.git / blobdiff