zanmato1984 commented on code in PR #44394: URL: https://github.com/apache/arrow/pull/44394#discussion_r1881617034
########## cpp/src/arrow/compute/kernels/vector_swizzle_test.cc: ########## @@ -0,0 +1,1065 @@ +// 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. + +#include <gtest/gtest.h> + +#include "arrow/array/concatenate.h" +#include "arrow/chunked_array.h" +#include "arrow/compute/api_vector.h" +#include "arrow/compute/kernels/test_util.h" +#include "arrow/testing/generator.h" +#include "arrow/testing/gtest_util.h" +#include "arrow/testing/random.h" +#include "arrow/util/logging.h" + +namespace arrow::compute { + +namespace { + +static const std::vector<std::shared_ptr<DataType>> kSignedIntegerTypes = { + int8(), int16(), int32(), int64()}; + +static const std::vector<std::shared_ptr<DataType>> kIntegerTypes = { + int8(), uint8(), int16(), uint16(), int32(), uint32(), int64(), uint64()}; + +static const std::vector<std::shared_ptr<DataType>> kNumericTypes = { + uint8(), int8(), uint16(), int16(), uint32(), + int32(), uint64(), int64(), float32(), float64()}; + +static const std::vector<std::shared_ptr<DataType>> kNumericAndBaseBinaryTypes = { + uint8(), int8(), uint16(), int16(), uint32(), int32(), uint64(), + int64(), float32(), float64(), binary(), utf8(), large_binary(), large_utf8()}; + +using SmallOutputTypes = ::testing::Types<UInt8Type, UInt16Type, Int8Type, Int16Type>; + +} // namespace + +// ---------------------------------------------------------------------- +// InversePermutation tests + +namespace { + +Result<Datum> InversePermutation(const Datum& indices, int64_t max_index, + std::shared_ptr<DataType> output_type) { + InversePermutationOptions options{max_index, std::move(output_type)}; + return InversePermutation(indices, options); +} + +void AssertInversePermutation(const Datum& indices, int64_t max_index, + const std::shared_ptr<DataType>& output_type, + const Datum& expected, bool validity_must_be_null) { + ASSERT_OK_AND_ASSIGN(auto result, InversePermutation(indices, max_index, output_type)); + ASSERT_EQ(indices.kind(), result.kind()); + std::shared_ptr<Array> result_array; + if (result.is_array()) { + result_array = result.make_array(); + } else { + ASSERT_TRUE(result.is_chunked_array()); + ASSERT_OK_AND_ASSIGN(result_array, Concatenate(result.chunked_array()->chunks())); + } + AssertDatumsEqual(expected, result_array); + if (validity_must_be_null) { + ASSERT_FALSE(result_array->data()->HasValidityBitmap()); + } +} + +template <typename InputFunc> +void DoTestInversePermutationForInputTypes( + const std::vector<std::shared_ptr<DataType>>& input_types, InputFunc&& input, + int64_t max_index, const std::shared_ptr<DataType>& output_type, + const Datum& expected, bool validity_must_be_null = false) { + for (const auto& input_type : input_types) { + ARROW_SCOPED_TRACE("Input type: " + input_type->ToString()); + auto indices = input(input_type); + AssertInversePermutation(indices, max_index, output_type, expected, + validity_must_be_null); + } +} + +template <typename InputFunc> +void DoTestInversePermutationForInputOutputTypes( + const std::vector<std::shared_ptr<DataType>>& input_types, + const std::vector<std::shared_ptr<DataType>>& output_types, InputFunc&& input, + int64_t max_index, const std::string& expected_str, bool validity_must_be_null) { + for (const auto& output_type : kIntegerTypes) { + ARROW_SCOPED_TRACE("Output type: " + output_type->ToString()); + auto expected = ArrayFromJSON(output_type, expected_str); + DoTestInversePermutationForInputTypes(input_types, std::forward<InputFunc>(input), + max_index, output_type, expected, + validity_must_be_null); + } +} + +void TestInversePermutationForInputOutputTypes( + const std::vector<std::shared_ptr<DataType>>& input_types, + const std::vector<std::shared_ptr<DataType>>& output_types, + const std::string& indices_str, const std::vector<std::string>& indices_chunked_str, + int64_t max_index, const std::string& expected_str, bool validity_must_be_null) { + { + ARROW_SCOPED_TRACE("Array"); + DoTestInversePermutationForInputOutputTypes( + input_types, output_types, + [&](const std::shared_ptr<DataType>& input_type) { + return ArrayFromJSON(input_type, indices_str); + }, + max_index, expected_str, validity_must_be_null); + } + { + ARROW_SCOPED_TRACE("Chunked"); + DoTestInversePermutationForInputOutputTypes( + input_types, output_types, + [&](const std::shared_ptr<DataType>& input_type) { + return ChunkedArrayFromJSON(input_type, indices_chunked_str); + }, + max_index, expected_str, validity_must_be_null); + } +} + +void TestInversePermutationSigned(const std::string& indices_str, + const std::vector<std::string>& indices_chunked_str, + int64_t max_index, const std::string& expected_str, + bool validity_must_be_null = false) { + TestInversePermutationForInputOutputTypes(kSignedIntegerTypes, kIntegerTypes, + indices_str, indices_chunked_str, max_index, + expected_str, validity_must_be_null); +} + +void TestInversePermutation(const std::string& indices_str, + const std::vector<std::string>& indices_chunked_str, + int64_t max_index, const std::string& expected_str, + bool validity_must_be_null = false) { + TestInversePermutationForInputOutputTypes(kIntegerTypes, kIntegerTypes, indices_str, + indices_chunked_str, max_index, expected_str, + validity_must_be_null); +} + +} // namespace + +TEST(InversePermutation, InvalidOutputType) { + { + ARROW_SCOPED_TRACE("Output type float"); + auto indices = ArrayFromJSON(int32(), "[]"); + ASSERT_RAISES_WITH_MESSAGE( + Invalid, "Invalid: Output type of inverse_permutation must be integer, got float", + InversePermutation(indices, /*max_index=*/0, /*output_type=*/float32())); + } + { + ARROW_SCOPED_TRACE("Output type string"); + auto indices = ArrayFromJSON(int32(), "[]"); + ASSERT_RAISES_WITH_MESSAGE( + Invalid, + "Invalid: Output type of inverse_permutation must be integer, got string", + InversePermutation(indices, /*max_index=*/0, /*output_type=*/utf8())); + } +} + +TEST(InversePermutation, DefaultOptions) { + { + ARROW_SCOPED_TRACE("Default options values"); + InversePermutationOptions options; + ASSERT_EQ(options.max_index, -1); + ASSERT_EQ(options.output_type, nullptr); + } + { + ARROW_SCOPED_TRACE("Default options semantics"); + for (const auto& input_type : kIntegerTypes) { + ARROW_SCOPED_TRACE("Input type: " + input_type->ToString()); + auto indices = ArrayFromJSON(input_type, "[0]"); + ASSERT_OK_AND_ASSIGN(Datum result, InversePermutation(indices)); + AssertDatumsEqual(indices, result); + } + } +} + +template <typename ArrowType> +class TestInversePermutationSmallOutputType : public ::testing::Test { + protected: + using CType = typename TypeTraits<ArrowType>::CType; + + std::shared_ptr<DataType> type_singleton() { + return TypeTraits<ArrowType>::type_singleton(); + } +}; + +TYPED_TEST_SUITE(TestInversePermutationSmallOutputType, SmallOutputTypes); + +TYPED_TEST(TestInversePermutationSmallOutputType, JustEnoughOutputType) { + auto output_type = this->type_singleton(); + int64_t input_length = + static_cast<int64_t>(std::numeric_limits<typename TestFixture::CType>::max()); + auto expected = + ArrayFromJSON(output_type, "[" + std::to_string(input_length - 1) + "]"); + DoTestInversePermutationForInputTypes( + kIntegerTypes, + [&](const std::shared_ptr<DataType>& input_type) { + return ConstantArrayGenerator::Zeroes(input_length, input_type); + }, + /*max_index=*/0, output_type, expected); +} + +TYPED_TEST(TestInversePermutationSmallOutputType, InsufficientOutputType) { + auto output_type = this->type_singleton(); + int64_t input_length = + static_cast<int64_t>(std::numeric_limits<typename TestFixture::CType>::max()) + 1; + for (const auto& input_type : kIntegerTypes) { + ARROW_SCOPED_TRACE("Input type: " + input_type->ToString()); + auto indices = ConstantArrayGenerator::Zeroes(input_length, input_type); + ASSERT_RAISES_WITH_MESSAGE( + Invalid, + "Invalid: Output type " + output_type->ToString() + + " of inverse_permutation is insufficient to store indices of length " + + std::to_string(input_length), + InversePermutation(indices, /*max_index=*/0, output_type)); + } +} + +TEST(InversePermutation, Basic) { + { + ARROW_SCOPED_TRACE("Basic"); + auto indices = "[9, 7, 5, 3, 1, 0, 2, 4, 6, 8]"; + std::vector<std::string> indices_chunked{ + "[]", "[9, 7, 5, 3, 1]", "[0]", "[2, 4, 6]", "[8]", "[]"}; + int64_t max_index = 9; + auto expected = "[5, 4, 6, 3, 7, 2, 8, 1, 9, 0]"; + TestInversePermutation(indices, indices_chunked, max_index, expected, + /*validity_must_be_null=*/true); + } + { + ARROW_SCOPED_TRACE("Basic with nulls"); + auto indices = "[9, 7, 5, 3, 1, null, null, null, null, null]"; + std::vector<std::string> indices_chunked{ + "[]", "[9, 7, 5, 3, 1]", "[null]", "[null, null, null]", "[null]", "[]"}; + int64_t max_index = 9; + auto expected = "[null, 4, null, 3, null, 2, null, 1, null, 0]"; + TestInversePermutation(indices, indices_chunked, max_index, expected); + } + { + ARROW_SCOPED_TRACE("Basic with negatives"); + auto indices = "[9, 7, 5, 3, 1, -1, -2, -3, -4, -5]"; + std::vector<std::string> indices_chunked{ + "[]", "[9, 7, 5, 3, 1]", "[-1]", "[-2, -3, -4]", "[-5]", "[]"}; + int64_t max_index = 9; + auto expected = "[null, 4, null, 3, null, 2, null, 1, null, 0]"; + TestInversePermutationSigned(indices, indices_chunked, max_index, expected); + } + { + ARROW_SCOPED_TRACE("Output greater than input"); + auto indices = "[1, 2]"; + std::vector<std::string> indices_chunked{"[]", "[1]", "[]", "[2]"}; + int64_t max_index = 6; + auto expected = "[null, 0, 1, null, null, null, null]"; + TestInversePermutation(indices, indices_chunked, max_index, expected); + } + { + ARROW_SCOPED_TRACE("Input all null"); + auto indices = "[null, null]"; + std::vector<std::string> indices_chunked{"[]", "[null]", "[]", "[null]"}; + int64_t max_index = 1; + auto expected = "[null, null]"; + TestInversePermutation(indices, indices_chunked, max_index, expected); + } + { + ARROW_SCOPED_TRACE("Output all null"); + auto indices = "[2, 3]"; + std::vector<std::string> indices_chunked{"[]", "[2]", "[]", "[3]"}; + int64_t max_index = 1; + auto expected = "[null, null]"; + TestInversePermutation(indices, indices_chunked, max_index, expected); + } + { + ARROW_SCOPED_TRACE("Empty input output null"); + auto indices = "[]"; + std::vector<std::string> indices_chunked{"[]", "[]", "[]", "[]"}; + int64_t max_index = 6; + auto expected = "[null, null, null, null, null, null, null]"; + TestInversePermutation(indices, indices_chunked, max_index, expected); + } + { + ARROW_SCOPED_TRACE("Input duplicated indices"); + auto indices = "[1, 2, 3, 1, 2, 3, 1, 2, 3]"; + std::vector<std::string> indices_chunked{"[]", "[1, 2]", "[3, 1, 2, 3, 1]", + "[]", "[2]", "[3]"}; + int64_t max_index = 4; + auto expected = "[null, 6, 7, 8, null]"; + TestInversePermutation(indices, indices_chunked, max_index, expected); + } +} + +// ---------------------------------------------------------------------- +// Scatter tests +// +// Shorthand notation: +// +// A = Array +// C = ChunkedArray + +namespace { + +Result<Datum> Scatter(const Datum& values, const Datum& indices, int64_t max_index) { + ScatterOptions options{max_index}; + return Scatter(values, indices, options); +} + +void AssertScatterAAA(const std::shared_ptr<Array>& values, + const std::shared_ptr<Array>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + ASSERT_OK_AND_ASSIGN(Datum result, Scatter(values, indices, max_index)); + AssertDatumsEqual(expected, result); +} + +void AssertScatterCAC(const std::shared_ptr<ChunkedArray>& values, + const std::shared_ptr<Array>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + ASSERT_OK_AND_ASSIGN(Datum result, Scatter(values, indices, max_index)); + ASSERT_TRUE(result.is_chunked_array()); + ASSERT_OK_AND_ASSIGN(auto result_array, Concatenate(result.chunked_array()->chunks())); + AssertDatumsEqual(expected, result_array); +} + +void AssertScatterACC(const std::shared_ptr<Array>& values, + const std::shared_ptr<ChunkedArray>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + ASSERT_OK_AND_ASSIGN(Datum result, Scatter(values, indices, max_index)); + ASSERT_TRUE(result.is_chunked_array()); + ASSERT_OK_AND_ASSIGN(auto result_array, Concatenate(result.chunked_array()->chunks())); + AssertDatumsEqual(expected, result_array); +} + +void AssertScatterCCC(const std::shared_ptr<ChunkedArray>& values, + const std::shared_ptr<ChunkedArray>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + ASSERT_OK_AND_ASSIGN(Datum result, Scatter(values, indices, max_index)); + ASSERT_TRUE(result.is_chunked_array()); + ASSERT_OK_AND_ASSIGN(auto result_array, Concatenate(result.chunked_array()->chunks())); + AssertDatumsEqual(expected, result_array); +} + +void DoTestScatterAAA(const std::shared_ptr<Array>& values, + const std::shared_ptr<Array>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + AssertScatterAAA(values, indices, max_index, expected); +} + +/// The following helper functions are based on the invariant: +/// Scatter([V, V], [I', I''], 2 * (m + 1) - 1) == Concat(E, E) +/// +/// where +/// V = values +/// I = indices +/// m = max_index +/// I' = ReplaceWithMask(I, i > m, null) +/// I'' = ReplaceWithMask(I, i < 0, null) + m + 1 +/// E = Scatter(V, I, m) + +/// Make indices prefix I' = ReplaceWithMask(I, i > m, null). +Result<std::shared_ptr<Array>> MakeIndicesPrefix(const std::shared_ptr<Array>& indices, + int64_t max_index) { + ARROW_ASSIGN_OR_RAISE(auto m, MakeScalar(indices->type(), max_index)); + ARROW_ASSIGN_OR_RAISE(auto ge_than_l, CallFunction("greater", {indices, m})); + ARROW_ASSIGN_OR_RAISE(auto all_null, + MakeArrayOfNull(indices->type(), indices->length())); + ARROW_ASSIGN_OR_RAISE(auto prefix, ReplaceWithMask(indices, ge_than_l, all_null)); + return prefix.make_array(); +} + +/// Make indices suffix I'' = ReplaceWithMask(I, i < 0, null) + m + 1. +Result<std::shared_ptr<Array>> MakeIndicesSuffix(const std::shared_ptr<Array>& indices, + int64_t max_index) { + ARROW_ASSIGN_OR_RAISE(auto zero, MakeScalar(indices->type(), 0)); + ARROW_ASSIGN_OR_RAISE(auto negative, CallFunction("less", {indices, zero})); + ARROW_ASSIGN_OR_RAISE(auto all_null, + MakeArrayOfNull(indices->type(), indices->length())); + ARROW_ASSIGN_OR_RAISE(auto replaced, ReplaceWithMask(indices, negative, all_null)); + ARROW_ASSIGN_OR_RAISE(auto m, MakeScalar(indices->type(), max_index)); + ARROW_ASSIGN_OR_RAISE(auto replaced_plus_m, Add(replaced, m)); + ARROW_ASSIGN_OR_RAISE(auto one, MakeScalar(indices->type(), 1)); + ARROW_ASSIGN_OR_RAISE(auto suffix, Add(replaced_plus_m, one)); + return suffix.make_array(); +} + +void DoTestScatterCACWithArrays(const std::shared_ptr<Array>& values, + const std::shared_ptr<Array>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + auto chunked_values2 = std::make_shared<ChunkedArray>(ArrayVector{values, values}); + + ASSERT_OK_AND_ASSIGN(auto indices_prefix, MakeIndicesPrefix(indices, max_index)); + ASSERT_OK_AND_ASSIGN(auto indices_suffix, MakeIndicesSuffix(indices, max_index)); + ASSERT_OK_AND_ASSIGN(auto concat_indices2, + Concatenate({indices_prefix, indices_suffix})); + + ASSERT_OK_AND_ASSIGN(auto concat_expected2, + Concatenate(ArrayVector{expected, expected})); + + AssertScatterCAC(chunked_values2, concat_indices2, (max_index + 1) * 2 - 1, + concat_expected2); +} + +void DoTestScatterACCWithArrays(const std::shared_ptr<Array>& values, + const std::shared_ptr<Array>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + ASSERT_OK_AND_ASSIGN(auto concat_values2, Concatenate(ArrayVector{values, values})); + + ASSERT_OK_AND_ASSIGN(auto indices_prefix, MakeIndicesPrefix(indices, max_index)); + ASSERT_OK_AND_ASSIGN(auto indices_suffix, MakeIndicesSuffix(indices, max_index)); + auto chunked_indices2 = + std::make_shared<ChunkedArray>(ArrayVector{indices_prefix, indices_suffix}); + + ASSERT_OK_AND_ASSIGN(auto concat_expected2, + Concatenate(ArrayVector{expected, expected})); + + AssertScatterACC(concat_values2, chunked_indices2, (max_index + 1) * 2 - 1, + concat_expected2); +} + +void DoTestScatterCCCWithArrays(const std::shared_ptr<Array>& values, + const std::shared_ptr<Array>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + auto chunked_values2 = std::make_shared<ChunkedArray>(ArrayVector{values, values}); + + ASSERT_OK_AND_ASSIGN(auto indices_prefix, MakeIndicesPrefix(indices, max_index)); + ASSERT_OK_AND_ASSIGN(auto indices_suffix, MakeIndicesSuffix(indices, max_index)); + auto chunked_indices2 = + std::make_shared<ChunkedArray>(ArrayVector{indices_prefix, indices_suffix}); + + ASSERT_OK_AND_ASSIGN(auto concat_expected2, + Concatenate(ArrayVector{expected, expected})); + + AssertScatterCCC(chunked_values2, chunked_indices2, (max_index + 1) * 2 - 1, + concat_expected2); +} + +void DoTestScatterForIndicesTypes( + const std::vector<std::shared_ptr<DataType>>& indices_types, + const std::shared_ptr<Array>& values, const std::shared_ptr<Array>& indices, + int64_t max_index, const std::shared_ptr<Array>& expected) { + for (const auto& indices_type : indices_types) { + ARROW_SCOPED_TRACE("Indices type: " + indices_type->ToString()); + ASSERT_OK_AND_ASSIGN(auto casted, Cast(indices, indices_type)); + ASSERT_TRUE(casted.is_array()); + auto casted_indices = casted.make_array(); + { + ARROW_SCOPED_TRACE("AAA"); + DoTestScatterAAA(values, casted_indices, max_index, expected); + } + { + ARROW_SCOPED_TRACE("CAA"); + DoTestScatterCACWithArrays(values, casted_indices, max_index, expected); + } + { + ARROW_SCOPED_TRACE("ACA"); + DoTestScatterACCWithArrays(values, casted_indices, max_index, expected); + } + { + ARROW_SCOPED_TRACE("CCA"); + DoTestScatterCCCWithArrays(values, casted_indices, max_index, expected); + } + } +} + +void DoTestScatterSignedIndices(const std::shared_ptr<Array>& values, + const std::shared_ptr<Array>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + DoTestScatterForIndicesTypes(kSignedIntegerTypes, values, indices, max_index, expected); +} + +void DoTestScatter(const std::shared_ptr<Array>& values, + const std::shared_ptr<Array>& indices, int64_t max_index, + const std::shared_ptr<Array>& expected) { + DoTestScatterForIndicesTypes(kIntegerTypes, values, indices, max_index, expected); +} + +} // namespace + +TEST(Scatter, Invalid) { + { + ARROW_SCOPED_TRACE("Length mismatch"); + auto values = ArrayFromJSON(int32(), "[0, 1]"); + auto indices = ArrayFromJSON(int32(), "[0]"); + ASSERT_RAISES_WITH_MESSAGE( + Invalid, + "Invalid: Input and indices of scatter must have the same length, got 2 and 1", + Scatter(values, indices)); + } + { + ARROW_SCOPED_TRACE("Invalid input type"); + auto values = ArrayFromJSON(int32(), "[0]"); + auto indices = ArrayFromJSON(utf8(), R"(["a"])"); + ASSERT_RAISES_WITH_MESSAGE( + Invalid, "Invalid: Indices of scatter must be of integer type, got string", + Scatter(values, indices)); + } +} + +TEST(Scatter, DefaultOptions) { + { + ARROW_SCOPED_TRACE("Default options values"); + ScatterOptions options; + ASSERT_EQ(options.max_index, -1); + } + { + ARROW_SCOPED_TRACE("Default options semantics"); + auto values = ArrayFromJSON(utf8(), R"(["a"])"); + for (const auto& indices_type : kIntegerTypes) { + ARROW_SCOPED_TRACE("Indices type: " + indices_type->ToString()); + auto indices = ArrayFromJSON(indices_type, "[0]"); + ASSERT_OK_AND_ASSIGN(Datum result, Scatter(values, indices)); + AssertDatumsEqual(values, result); + } + } +} + +template <typename ArrowType> Review Comment: Good point. I've reduced typed tests that are the case by using for loops. However I tend to keep the remaining two typed tests (`TestInversePermutationSmallOutputType` and `TestScatterSmallIndicesTypes`) as are, because: 1) I need to apply `std::numeric_limits` by the type parameter; 2) the number of "small types" are reduced to 2 so the code generation should be acceptable. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org
