Github user marmbrus commented on a diff in the pull request:
https://github.com/apache/spark/pull/9480#discussion_r44201792
--- Diff:
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
---
@@ -0,0 +1,108 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import scala.collection.mutable
+
+/**
+ * This class is used to compute equality of (sub)expression trees.
Expressions can be added
+ * to this class and they subsequently query for expression equality.
Expression trees are
+ * considered equal if for the same input(s), the same result is produced.
+ */
+class EquivalentExpressions {
+ /**
+ * Wrapper around an Expression that provides semantic equality.
+ */
+ case class Expr(e: Expression) {
+ val hash = e.semanticHash()
+ override def equals(o: Any): Boolean = o match {
+ case other: Expr => e.semanticEquals(other.e)
+ case _ => false
+ }
+ override def hashCode: Int = hash
+ }
+
+ // For each expression, the set of equivalent expressions.
+ private val equivalenceMap: mutable.HashMap[Expr,
mutable.MutableList[Expression]] =
+ new mutable.HashMap[Expr, mutable.MutableList[Expression]]
+
+ /**
+ * Adds each expression to this data structure, grouping them with
existing equivalent
+ * expressions. Non-recursive.
+ * Returns if there was already a matching expression.
+ */
+ def addExpr(expr: Expression): Boolean = {
+ if (expr.deterministic) {
+ val e: Expr = Expr(expr)
+ val f = equivalenceMap.get(e)
+ if (f.isDefined) {
+ f.get.+= (expr)
+ true
+ } else {
+ equivalenceMap.put(e, mutable.MutableList(expr))
+ false
+ }
+ } else {
+ false
+ }
+ }
+
+ /**
+ * Adds the expression to this datastructure recursively. Stops if a
matching expression
+ * is found. That is, if `expr` has already been added, its children are
not added.
+ * If ignoreLeaf is true, leaf nodes are ignored.
+ */
+ def addExprTree(root: Expression, ignoreLeaf: Boolean = true): Unit = {
+ val skip = root.isInstanceOf[LeafExpression] && ignoreLeaf
+ if (!skip && root.deterministic && !addExpr(root)) {
+ root.children.foreach(addExprTree(_, ignoreLeaf))
+ }
+ }
+
+ /**
+ * Returns all fo the expression trees that are equivalent to `e`.
Returns
+ * an empty collection if there are none.
+ */
+ def getEquivalentExprs(e: Expression): Seq[Expression] = {
+ equivalenceMap.get(Expr(e)).getOrElse(mutable.MutableList())
+ }
+
+ /**
+ * Returns all the equivalent sets of expressions.
+ */
+ def getAllEquivalentExprs: Seq[Seq[Expression]] = {
+ equivalenceMap.map { case(k, v) => {
--- End diff --
`equivalenceMap.values`?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
