Repository: prestodb/presto
Issue: Incorrect result when using MAP in IN expression

In the latest master:

```
presto:tiny> select x from (values 2) t(x) where map(array[1], array[x]) in (values map(array[1],array[2]));
 x

---
(0 rows)
```


Changed files:
presto-tests/src/main/java/com/facebook/presto/tests/AbstractTestQueries.java
presto-main/src/test/java/com/facebook/presto/operator/scalar/AbstractTestFunctions.java
presto-main/src/main/java/com/facebook/presto/type/ArrayType.java
presto-main/src/test/java/com/facebook/presto/type/TestArrayOperators.java
presto-main/src/main/java/com/facebook/presto/operator/scalar/ArrayHashCodeOperator.java
presto-main/src/test/java/com/facebook/presto/type/TestRowOperators.java
presto-main/src/test/java/com/facebook/presto/type/TestMapOperators.java
presto-main/src/main/java/com/facebook/presto/type/MapType.java

diff --git a/presto-main/src/main/java/com/facebook/presto/operator/scalar/ArrayHashCodeOperator.java b/presto-main/src/main/java/com/facebook/presto/operator/scalar/ArrayHashCodeOperator.java
index d10332cc90..a9f074a062 100644
--- a/presto-main/src/main/java/com/facebook/presto/operator/scalar/ArrayHashCodeOperator.java
+++ b/presto-main/src/main/java/com/facebook/presto/operator/scalar/ArrayHashCodeOperator.java
@@ -45,11 +45,11 @@ public final class ArrayHashCodeOperator
             @TypeParameter("T") Type type,
             @SqlType("array(T)") Block block)
     {
-        int hash = 0;
+        long hash = 0;
         for (int i = 0; i < block.getPositionCount(); i++) {
             checkElementNotNull(block.isNull(i), ARRAY_NULL_ELEMENT_MSG);
             try {
-                hash = (int) CombineHashFunction.getHash(hash, (long) hashFunction.invoke(readNativeValue(type, block, i)));
+                hash = CombineHashFunction.getHash(hash, (long) hashFunction.invoke(readNativeValue(type, block, i)));
             }
             catch (Throwable t) {
                 Throwables.propagateIfInstanceOf(t, Error.class);
@@ -69,11 +69,11 @@ public final class ArrayHashCodeOperator
             @TypeParameter("T") Type type,
             @SqlType("array(T)") Block block)
     {
-        int hash = 0;
+        long hash = 0;
         for (int i = 0; i < block.getPositionCount(); i++) {
             checkElementNotNull(block.isNull(i), ARRAY_NULL_ELEMENT_MSG);
             try {
-                hash = (int) CombineHashFunction.getHash(hash, (long) hashFunction.invokeExact(type.getLong(block, i)));
+                hash = CombineHashFunction.getHash(hash, (long) hashFunction.invokeExact(type.getLong(block, i)));
             }
             catch (Throwable t) {
                 Throwables.propagateIfInstanceOf(t, Error.class);
@@ -93,11 +93,11 @@ public final class ArrayHashCodeOperator
             @TypeParameter("T") Type type,
             @SqlType("array(T)") Block block)
     {
-        int hash = 0;
+        long hash = 0;
         for (int i = 0; i < block.getPositionCount(); i++) {
             checkElementNotNull(block.isNull(i), ARRAY_NULL_ELEMENT_MSG);
             try {
-                hash = (int) CombineHashFunction.getHash(hash, (long) hashFunction.invokeExact(type.getBoolean(block, i)));
+                hash = CombineHashFunction.getHash(hash, (long) hashFunction.invokeExact(type.getBoolean(block, i)));
             }
             catch (Throwable t) {
                 Throwables.propagateIfInstanceOf(t, Error.class);
@@ -117,11 +117,11 @@ public final class ArrayHashCodeOperator
             @TypeParameter("T") Type type,
             @SqlType("array(T)") Block block)
     {
-        int hash = 0;
+        long hash = 0;
         for (int i = 0; i < block.getPositionCount(); i++) {
             checkElementNotNull(block.isNull(i), ARRAY_NULL_ELEMENT_MSG);
             try {
-                hash = (int) CombineHashFunction.getHash(hash, (long) hashFunction.invokeExact(type.getSlice(block, i)));
+                hash = CombineHashFunction.getHash(hash, (long) hashFunction.invokeExact(type.getSlice(block, i)));
             }
             catch (Throwable t) {
                 Throwables.propagateIfInstanceOf(t, Error.class);
@@ -141,11 +141,11 @@ public final class ArrayHashCodeOperator
             @TypeParameter("T") Type type,
             @SqlType("array(T)") Block block)
     {
-        int hash = 0;
+        long hash = 0;
         for (int i = 0; i < block.getPositionCount(); i++) {
             checkElementNotNull(block.isNull(i), ARRAY_NULL_ELEMENT_MSG);
             try {
-                hash = (int) CombineHashFunction.getHash(hash, (long) hashFunction.invokeExact(type.getDouble(block, i)));
+                hash = CombineHashFunction.getHash(hash, (long) hashFunction.invokeExact(type.getDouble(block, i)));
             }
             catch (Throwable t) {
                 Throwables.propagateIfInstanceOf(t, Error.class);
diff --git a/presto-main/src/main/java/com/facebook/presto/type/ArrayType.java b/presto-main/src/main/java/com/facebook/presto/type/ArrayType.java
index f6e8aca6ff..c9d5d4ad70 100644
--- a/presto-main/src/main/java/com/facebook/presto/type/ArrayType.java
+++ b/presto-main/src/main/java/com/facebook/presto/type/ArrayType.java
@@ -89,10 +89,10 @@ public class ArrayType
     public long hash(Block block, int position)
     {
         Block array = getObject(block, position);
-        int hash = 0;
+        long hash = 0;
         for (int i = 0; i < array.getPositionCount(); i++) {
             checkElementNotNull(array.isNull(i), ARRAY_NULL_ELEMENT_MSG);
-            hash = (int) CombineHashFunction.getHash(hash, elementType.hash(array, i));
+            hash = CombineHashFunction.getHash(hash, elementType.hash(array, i));
         }
         return hash;
     }
diff --git a/presto-main/src/main/java/com/facebook/presto/type/MapType.java b/presto-main/src/main/java/com/facebook/presto/type/MapType.java
index 76fd439ca3..ab3baad727 100644
--- a/presto-main/src/main/java/com/facebook/presto/type/MapType.java
+++ b/presto-main/src/main/java/com/facebook/presto/type/MapType.java
@@ -89,7 +89,7 @@ public class MapType
     public long hash(Block block, int position)
     {
         Block mapBlock = getObject(block, position);
-        int result = 0;
+        long result = 0;
 
         for (int i = 0; i < mapBlock.getPositionCount(); i += 2) {
             result += hashPosition(keyType, mapBlock, i);
diff --git a/presto-main/src/test/java/com/facebook/presto/operator/scalar/AbstractTestFunctions.java b/presto-main/src/test/java/com/facebook/presto/operator/scalar/AbstractTestFunctions.java
index 7c2c9e1945..f9f2b300b9 100644
--- a/presto-main/src/test/java/com/facebook/presto/operator/scalar/AbstractTestFunctions.java
+++ b/presto-main/src/test/java/com/facebook/presto/operator/scalar/AbstractTestFunctions.java
@@ -19,6 +19,7 @@ import com.facebook.presto.metadata.Metadata;
 import com.facebook.presto.metadata.SqlFunction;
 import com.facebook.presto.spi.ErrorCodeSupplier;
 import com.facebook.presto.spi.PrestoException;
+import com.facebook.presto.spi.function.OperatorType;
 import com.facebook.presto.spi.type.DecimalParseResult;
 import com.facebook.presto.spi.type.Decimals;
 import com.facebook.presto.spi.type.SqlDecimal;
@@ -32,6 +33,7 @@ import java.math.BigInteger;
 import java.util.List;
 
 import static com.facebook.presto.SessionTestUtils.TEST_SESSION;
+import static com.facebook.presto.metadata.FunctionRegistry.mangleOperatorName;
 import static com.facebook.presto.spi.StandardErrorCode.INVALID_CAST_ARGUMENT;
 import static com.facebook.presto.spi.StandardErrorCode.INVALID_FUNCTION_ARGUMENT;
 import static com.facebook.presto.spi.StandardErrorCode.NUMERIC_VALUE_OUT_OF_RANGE;
@@ -65,6 +67,11 @@ public abstract class AbstractTestFunctions
         functionAssertions.assertFunction(projection, expectedType, expected);
     }
 
+    protected void assertOperator(OperatorType operator, String value, Type expectedType, Object expected)
+    {
+        functionAssertions.assertFunction(format("\\"%s\\"(%s)", mangleOperatorName(operator), value), expectedType, expected);
+    }
+
     protected void assertDecimalFunction(String statement, SqlDecimal expectedResult)
     {
         assertFunction(statement,
diff --git a/presto-main/src/test/java/com/facebook/presto/type/TestArrayOperators.java b/presto-main/src/test/java/com/facebook/presto/type/TestArrayOperators.java
index cd3c122c65..eb82bbc6ca 100644
--- a/presto-main/src/test/java/com/facebook/presto/type/TestArrayOperators.java
+++ b/presto-main/src/test/java/com/facebook/presto/type/TestArrayOperators.java
@@ -17,8 +17,11 @@ import com.facebook.presto.operator.scalar.AbstractTestFunctions;
 import com.facebook.presto.spi.ErrorCode;
 import com.facebook.presto.spi.PrestoException;
 import com.facebook.presto.spi.block.Block;
+import com.facebook.presto.spi.block.BlockBuilder;
 import com.facebook.presto.spi.block.BlockBuilderStatus;
+import com.facebook.presto.spi.block.InterleavedBlockBuilder;
 import com.facebook.presto.spi.type.SqlTimestamp;
+import com.facebook.presto.spi.type.Type;
 import com.facebook.presto.sql.analyzer.SemanticErrorCode;
 import com.facebook.presto.sql.analyzer.SemanticException;
 import com.google.common.collect.ImmutableList;
@@ -39,6 +42,7 @@ import static com.facebook.presto.block.BlockSerdeUtil.writeBlock;
 import static com.facebook.presto.spi.StandardErrorCode.INVALID_CAST_ARGUMENT;
 import static com.facebook.presto.spi.StandardErrorCode.INVALID_FUNCTION_ARGUMENT;
 import static com.facebook.presto.spi.StandardErrorCode.NOT_SUPPORTED;
+import static com.facebook.presto.spi.function.OperatorType.HASH_CODE;
 import static com.facebook.presto.spi.type.BigintType.BIGINT;
 import static com.facebook.presto.spi.type.BooleanType.BOOLEAN;
 import static com.facebook.presto.spi.type.DoubleType.DOUBLE;
@@ -50,6 +54,7 @@ import static com.facebook.presto.sql.analyzer.SemanticErrorCode.AMBIGUOUS_FUNCT
 import static com.facebook.presto.sql.analyzer.SemanticErrorCode.FUNCTION_NOT_FOUND;
 import static com.facebook.presto.sql.analyzer.SemanticErrorCode.TYPE_MISMATCH;
 import static com.facebook.presto.type.JsonType.JSON;
+import static com.facebook.presto.type.TypeJsonUtils.appendToBlockBuilder;
 import static com.facebook.presto.type.UnknownType.UNKNOWN;
 import static com.facebook.presto.util.StructuralTestUtil.arrayBlockOf;
 import static java.lang.Double.NEGATIVE_INFINITY;
@@ -935,6 +940,20 @@ public class TestArrayOperators
         assertFunction("flatten(ARRAY [NULL, ARRAY [MAP (ARRAY [3, 4], ARRAY [3, 4])]])", new ArrayType(new MapType(INTEGER, INTEGER)), ImmutableList.of(ImmutableMap.of(3, 3, 4, 4)));
     }
 
+    @Test
+    public void testArrayHashOperator()
+    {
+        assertArrayHashOperator("ARRAY[1, 2]", INTEGER, ImmutableList.of(1, 2));
+        assertArrayHashOperator("ARRAY[true, false]", BOOLEAN, ImmutableList.of(true, false));
+
+        // test with ARRAY[ MAP( ARRAY[1], ARRAY[2] ) ]
+        MapType mapType = new MapType(INTEGER, INTEGER);
+        BlockBuilder mapBuilder = new InterleavedBlockBuilder(ImmutableList.of(INTEGER, INTEGER), new BlockBuilderStatus(), 2);
+        INTEGER.writeLong(mapBuilder, 1);
+        INTEGER.writeLong(mapBuilder, 2);
+        assertArrayHashOperator("ARRAY[MAP(ARRAY[1], ARRAY[2])]", mapType, ImmutableList.of(mapBuilder.build()));
+    }
+
     public void assertInvalidFunction(String projection, ErrorCode errorCode)
     {
         try {
@@ -946,6 +965,19 @@ public class TestArrayOperators
         }
     }
 
+    private void assertArrayHashOperator(String inputArray, Type elementType, List<Object> elements)
+    {
+        ArrayType arrayType = new ArrayType(elementType);
+        BlockBuilder arrayArrayBuilder = arrayType.createBlockBuilder(new BlockBuilderStatus(), 1);
+        BlockBuilder arrayBuilder = elementType.createBlockBuilder(new BlockBuilderStatus(), elements.size());
+        for (Object element : elements) {
+            appendToBlockBuilder(elementType, element, arrayBuilder);
+        }
+        arrayType.writeObject(arrayArrayBuilder, arrayBuilder.build());
+
+        assertOperator(HASH_CODE, inputArray, BIGINT, arrayType.hash(arrayArrayBuilder.build(), 0));
+    }
+
     private SqlTimestamp sqlTimestamp(long millisUtc)
     {
         return new SqlTimestamp(millisUtc, TEST_SESSION.getTimeZoneKey());
diff --git a/presto-main/src/test/java/com/facebook/presto/type/TestMapOperators.java b/presto-main/src/test/java/com/facebook/presto/type/TestMapOperators.java
index e7a7ce7b70..c93d93f4ad 100644
--- a/presto-main/src/test/java/com/facebook/presto/type/TestMapOperators.java
+++ b/presto-main/src/test/java/com/facebook/presto/type/TestMapOperators.java
@@ -15,6 +15,7 @@ package com.facebook.presto.type;
 
 import com.facebook.presto.operator.scalar.AbstractTestFunctions;
 import com.facebook.presto.spi.block.Block;
+import com.facebook.presto.spi.block.BlockBuilder;
 import com.facebook.presto.spi.block.BlockBuilderStatus;
 import com.facebook.presto.spi.block.InterleavedBlockBuilder;
 import com.facebook.presto.spi.function.ScalarFunction;
@@ -31,10 +32,12 @@ import io.airlift.slice.Slice;
 import org.testng.annotations.Test;
 
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 
 import static com.facebook.presto.SessionTestUtils.TEST_SESSION;
 import static com.facebook.presto.block.BlockSerdeUtil.writeBlock;
+import static com.facebook.presto.spi.function.OperatorType.HASH_CODE;
 import static com.facebook.presto.spi.type.BigintType.BIGINT;
 import static com.facebook.presto.spi.type.BooleanType.BOOLEAN;
 import static com.facebook.presto.spi.type.DoubleType.DOUBLE;
@@ -44,9 +47,12 @@ import static com.facebook.presto.spi.type.VarbinaryType.VARBINARY;
 import static com.facebook.presto.spi.type.VarcharType.VARCHAR;
 import static com.facebook.presto.spi.type.VarcharType.createVarcharType;
 import static com.facebook.presto.type.JsonType.JSON;
+import static com.facebook.presto.type.TypeJsonUtils.appendToBlockBuilder;
 import static com.facebook.presto.type.UnknownType.UNKNOWN;
 import static com.facebook.presto.util.StructuralTestUtil.arrayBlockOf;
 import static com.facebook.presto.util.StructuralTestUtil.mapBlockOf;
+import static com.google.common.base.Preconditions.checkArgument;
+import static io.airlift.slice.Slices.utf8Slice;
 import static java.lang.Double.doubleToLongBits;
 import static java.nio.charset.StandardCharsets.UTF_8;
 import static org.testng.Assert.assertEquals;
@@ -449,4 +455,30 @@ public class TestMapOperators
 
         assertInvalidCast("CAST(MAP(ARRAY[1, 2], ARRAY[6, 9]) AS MAP<boolean, bigint>)", "duplicate keys");
     }
+
+    @Test
+    public void testMapHashOperator()
+    {
+        assertMapHashOperator("MAP(ARRAY[1], ARRAY[2])", INTEGER, INTEGER, ImmutableList.of(1, 2));
+        assertMapHashOperator("MAP(ARRAY[1, 2147483647], ARRAY[2147483647, 2])", INTEGER, INTEGER, ImmutableList.of(1, 2147483647, 2147483647, 2));
+        assertMapHashOperator("MAP(ARRAY[8589934592], ARRAY[2])", BIGINT, INTEGER, ImmutableList.of(8589934592L, 2));
+        assertMapHashOperator("MAP(ARRAY[true], ARRAY[false])", BOOLEAN, BOOLEAN, ImmutableList.of(true, false));
+        assertMapHashOperator("MAP(ARRAY['123'], ARRAY['456'])", VARCHAR, VARCHAR, ImmutableList.of(utf8Slice("123"), utf8Slice("456")));
+    }
+
+    private void assertMapHashOperator(String inputString, Type keyType, Type valueType, List<Object> elements)
+    {
+        checkArgument(elements.size() % 2 == 0, "the size of elements should be even number");
+        MapType mapType = new MapType(keyType, valueType);
+        BlockBuilder mapArrayBuilder = mapType.createBlockBuilder(new BlockBuilderStatus(), 1);
+        BlockBuilder mapBuilder = new InterleavedBlockBuilder(ImmutableList.of(keyType, valueType), new BlockBuilderStatus(), elements.size());
+        for (int i = 0; i < elements.size(); i += 2) {
+            appendToBlockBuilder(keyType, elements.get(i), mapBuilder);
+            appendToBlockBuilder(valueType, elements.get(i + 1), mapBuilder);
+        }
+        mapType.writeObject(mapArrayBuilder, mapBuilder.build());
+        long hashResult = mapType.hash(mapArrayBuilder.build(), 0);
+
+        assertOperator(HASH_CODE, inputString, BIGINT, hashResult);
+    }
 }
diff --git a/presto-main/src/test/java/com/facebook/presto/type/TestRowOperators.java b/presto-main/src/test/java/com/facebook/presto/type/TestRowOperators.java
index 7dfc6a807a..5161d6ca40 100644
--- a/presto-main/src/test/java/com/facebook/presto/type/TestRowOperators.java
+++ b/presto-main/src/test/java/com/facebook/presto/type/TestRowOperators.java
@@ -16,6 +16,9 @@ package com.facebook.presto.type;
 import com.facebook.presto.operator.scalar.AbstractTestFunctions;
 import com.facebook.presto.spi.PrestoException;
 import com.facebook.presto.spi.StandardErrorCode;
+import com.facebook.presto.spi.block.BlockBuilder;
+import com.facebook.presto.spi.block.BlockBuilderStatus;
+import com.facebook.presto.spi.block.InterleavedBlockBuilder;
 import com.facebook.presto.spi.type.SqlTimestamp;
 import com.facebook.presto.spi.type.Type;
 import com.facebook.presto.sql.analyzer.SemanticException;
@@ -24,8 +27,11 @@ import com.google.common.collect.ImmutableMap;
 import org.testng.annotations.Test;
 
 import java.util.Arrays;
+import java.util.List;
+import java.util.Optional;
 
 import static com.facebook.presto.SessionTestUtils.TEST_SESSION;
+import static com.facebook.presto.spi.function.OperatorType.HASH_CODE;
 import static com.facebook.presto.spi.type.BigintType.BIGINT;
 import static com.facebook.presto.spi.type.BooleanType.BOOLEAN;
 import static com.facebook.presto.spi.type.DoubleType.DOUBLE;
@@ -33,6 +39,8 @@ import static com.facebook.presto.spi.type.IntegerType.INTEGER;
 import static com.facebook.presto.spi.type.TypeSignature.parseTypeSignature;
 import static com.facebook.presto.spi.type.VarcharType.VARCHAR;
 import static com.facebook.presto.type.JsonType.JSON;
+import static com.facebook.presto.type.TypeJsonUtils.appendToBlockBuilder;
+import static com.google.common.base.Preconditions.checkArgument;
 import static java.lang.String.format;
 import static org.testng.Assert.assertEquals;
 import static org.testng.Assert.fail;
@@ -203,4 +211,25 @@ public class TestRowOperators
         assertFunction("ROW(1, 2) = ROW(1, 2)", BOOLEAN, true);
         assertFunction("ROW(2, 1) != ROW(1, 2)", BOOLEAN, true);
     }
+
+    @Test
+    public void testRowHashOperator()
+    {
+        assertRowHashOperator("ROW(1, 2)", ImmutableList.of(INTEGER, INTEGER), ImmutableList.of(1, 2));
+        assertRowHashOperator("ROW(true, 2)", ImmutableList.of(BOOLEAN, INTEGER), ImmutableList.of(true, 2));
+    }
+
+    private void assertRowHashOperator(String inputString, List<Type> types, List<Object> elements)
+    {
+        checkArgument(types.size() == elements.size(), "types and elements must have the same size");
+        RowType rowType = new RowType(types, Optional.empty());
+        BlockBuilder rowArrayBuilder = rowType.createBlockBuilder(new BlockBuilderStatus(), 1);
+        BlockBuilder rowBuilder = new InterleavedBlockBuilder(types, new BlockBuilderStatus(), types.size());
+        for (int i = 0; i < types.size(); i++) {
+            appendToBlockBuilder(types.get(i), elements.get(i), rowBuilder);
+        }
+        rowType.writeObject(rowArrayBuilder, rowBuilder.build());
+
+        assertOperator(HASH_CODE, inputString, BIGINT, rowType.hash(rowArrayBuilder.build(), 0));
+    }
 }
diff --git a/presto-tests/src/main/java/com/facebook/presto/tests/AbstractTestQueries.java b/presto-tests/src/main/java/com/facebook/presto/tests/AbstractTestQueries.java
index cb3d73e359..c2d21db432 100644
--- a/presto-tests/src/main/java/com/facebook/presto/tests/AbstractTestQueries.java
+++ b/presto-tests/src/main/java/com/facebook/presto/tests/AbstractTestQueries.java
@@ -2790,6 +2790,9 @@ public abstract class AbstractTestQueries
         assertQuery(
                 "SELECT CASE WHEN false THEN 1 IN (VALUES 2) END",
                 "SELECT NULL");
+        assertQuery(
+                "SELECT x FROM (VALUES 2) t(x) where MAP(ARRAY[8589934592], ARRAY[x]) IN (VALUES MAP(ARRAY[8589934592],ARRAY[2]))",
+                "SELECT 2");
     }
 
     @Test