Skip to content

Commit 9c218ab

Browse files
felipecrvzagto
andauthored
GH-20351: [C++] Kernel input type matcher for run-end encoded types (#34503)
### Rationale for this change This is necessary to be able to specify dispatching of filters based on run-end encoded array (upcoming PR). ### Are these changes tested? Yes. By unit tests. * Closes #13971 * Closes: #20351 Lead-authored-by: Felipe Oliveira Carvalho <[email protected]> Co-authored-by: Tobias Zagorni <[email protected]> Signed-off-by: Matt Topol <[email protected]>
1 parent dbc1e90 commit 9c218ab

6 files changed

Lines changed: 141 additions & 6 deletions

File tree

‎cpp/src/arrow/compute/kernel.cc‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -275,6 +275,76 @@ std::shared_ptr<TypeMatcher> FixedSizeBinaryLike() {
275275
return std::make_shared<FixedSizeBinaryLikeMatcher>();
276276
}
277277

278+
class RunEndIntegerMatcher : public TypeMatcher {
279+
public:
280+
~RunEndIntegerMatcher() override = default;
281+
282+
bool Matches(const DataType& type) const override { return is_run_end_type(type.id()); }
283+
284+
bool Equals(const TypeMatcher& other) const override {
285+
auto casted = dynamic_cast<const RunEndIntegerMatcher*>(&other);
286+
return casted != nullptr;
287+
}
288+
289+
std::string ToString() const override { return "run-end-integer"; }
290+
};
291+
292+
std::shared_ptr<TypeMatcher> RunEndInteger() {
293+
return std::make_shared<RunEndIntegerMatcher>();
294+
}
295+
296+
class RunEndEncodedMatcher : public TypeMatcher {
297+
public:
298+
RunEndEncodedMatcher(std::shared_ptr<TypeMatcher> run_end_type_matcher,
299+
std::shared_ptr<TypeMatcher> value_type_matcher)
300+
: run_end_type_matcher{std::move(run_end_type_matcher)},
301+
value_type_matcher{std::move(value_type_matcher)} {}
302+
303+
~RunEndEncodedMatcher() override = default;
304+
305+
bool Matches(const DataType& type) const override {
306+
if (type.id() == Type::RUN_END_ENCODED) {
307+
const auto& ree_type = dynamic_cast<const RunEndEncodedType&>(type);
308+
// This invariant is enforced in RunEndEncodedType's constructor
309+
DCHECK(is_run_end_type(ree_type.run_end_type()->id()));
310+
return run_end_type_matcher->Matches(*ree_type.run_end_type()) &&
311+
value_type_matcher->Matches(*ree_type.value_type());
312+
}
313+
return false;
314+
}
315+
316+
bool Equals(const TypeMatcher& other) const override {
317+
if (this == &other) {
318+
return true;
319+
}
320+
const auto* casted = dynamic_cast<const RunEndEncodedMatcher*>(&other);
321+
return casted != nullptr && value_type_matcher->Equals(*casted->value_type_matcher) &&
322+
run_end_type_matcher->Equals(*casted->run_end_type_matcher);
323+
}
324+
325+
std::string ToString() const override {
326+
return "run_end_encoded(" + run_end_type_matcher->ToString() + ", " +
327+
value_type_matcher->ToString() + ")";
328+
};
329+
330+
private:
331+
std::shared_ptr<TypeMatcher> run_end_type_matcher;
332+
std::shared_ptr<TypeMatcher> value_type_matcher;
333+
};
334+
335+
std::shared_ptr<TypeMatcher> RunEndEncoded(
336+
std::shared_ptr<TypeMatcher> value_type_matcher) {
337+
return std::make_shared<RunEndEncodedMatcher>(RunEndInteger(),
338+
std::move(value_type_matcher));
339+
}
340+
341+
std::shared_ptr<TypeMatcher> RunEndEncoded(
342+
std::shared_ptr<TypeMatcher> run_end_type_matcher,
343+
std::shared_ptr<TypeMatcher> value_type_matcher) {
344+
return std::make_shared<RunEndEncodedMatcher>(std::move(run_end_type_matcher),
345+
std::move(value_type_matcher));
346+
}
347+
278348
} // namespace match
279349

280350
// ----------------------------------------------------------------------

‎cpp/src/arrow/compute/kernel.h‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -141,6 +141,25 @@ ARROW_EXPORT std::shared_ptr<TypeMatcher> FixedSizeBinaryLike();
141141
// Type)
142142
ARROW_EXPORT std::shared_ptr<TypeMatcher> Primitive();
143143

144+
// \brief Match any integer type that can be used as run-end in run-end encoded
145+
// arrays
146+
ARROW_EXPORT std::shared_ptr<TypeMatcher> RunEndInteger();
147+
148+
/// \brief Match run-end encoded types that use any valid run-end type and
149+
/// encode specific value types
150+
///
151+
/// @param[in] value_type_matcher a matcher that is applied to the values field
152+
ARROW_EXPORT std::shared_ptr<TypeMatcher> RunEndEncoded(
153+
std::shared_ptr<TypeMatcher> value_type_matcher);
154+
155+
/// \brief Match run-end encoded types that encode specific run-end and value types
156+
///
157+
/// @param[in] run_end_type_matcher a matcher that is applied to the run_ends field
158+
/// @param[in] value_type_matcher a matcher that is applied to the values field
159+
ARROW_EXPORT std::shared_ptr<TypeMatcher> RunEndEncoded(
160+
std::shared_ptr<TypeMatcher> run_end_type_matcher,
161+
std::shared_ptr<TypeMatcher> value_type_matcher);
162+
144163
} // namespace match
145164

146165
/// \brief An object used for type-checking arguments to be passed to a kernel

‎cpp/src/arrow/compute/kernel_test.cc‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,6 +69,35 @@ TEST(TypeMatcher, TimestampTypeUnit) {
6969
ASSERT_FALSE(matcher->Equals(*match::Time32TypeUnit(TimeUnit::MILLI)));
7070
}
7171

72+
TEST(TypeMatcher, RunEndInteger) {
73+
auto matcher = match::RunEndInteger();
74+
ASSERT_FALSE(matcher->Matches(*int8()));
75+
ASSERT_FALSE(matcher->Matches(*uint8()));
76+
ASSERT_FALSE(matcher->Matches(*uint16()));
77+
ASSERT_FALSE(matcher->Matches(*uint32()));
78+
ASSERT_FALSE(matcher->Matches(*uint64()));
79+
80+
ASSERT_TRUE(matcher->Matches(*int16()));
81+
ASSERT_TRUE(matcher->Matches(*int32()));
82+
ASSERT_TRUE(matcher->Matches(*int64()));
83+
}
84+
85+
TEST(TypeMatcher, RunEndEncoded) {
86+
auto string_ree_matcher = match::RunEndEncoded(match::SameTypeId(Type::STRING));
87+
auto int32_ree_matcher = match::RunEndEncoded(match::SameTypeId(Type::INT32));
88+
auto empty_ree_matcher =
89+
match::RunEndEncoded(match::SameTypeId(Type::INT8), match::SameTypeId(Type::INT32));
90+
for (auto run_end_type : {int16(), int32(), int64()}) {
91+
ASSERT_TRUE(string_ree_matcher->Matches(*run_end_encoded(run_end_type, utf8())));
92+
ASSERT_FALSE(string_ree_matcher->Matches(*run_end_encoded(run_end_type, int32())));
93+
94+
ASSERT_FALSE(int32_ree_matcher->Matches(*run_end_encoded(run_end_type, utf8())));
95+
ASSERT_TRUE(int32_ree_matcher->Matches(*run_end_encoded(run_end_type, int32())));
96+
97+
ASSERT_FALSE(empty_ree_matcher->Matches(*run_end_encoded(run_end_type, int32())));
98+
}
99+
}
100+
72101
// ----------------------------------------------------------------------
73102
// InputType
74103

‎cpp/src/arrow/type.cc‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -806,8 +806,7 @@ std::string RunEndEncodedType::ToString() const {
806806
}
807807

808808
bool RunEndEncodedType::RunEndTypeValid(const DataType& run_end_type) {
809-
return run_end_type.id() == Type::INT16 || run_end_type.id() == Type::INT32 ||
810-
run_end_type.id() == Type::INT64;
809+
return is_run_end_type(run_end_type.id());
811810
}
812811

813812
// ----------------------------------------------------------------------

‎cpp/src/arrow/type_traits.h‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -981,6 +981,23 @@ constexpr bool is_decimal(Type::type type_id) {
981981
return false;
982982
}
983983

984+
/// \brief Check for a type that can be used as a run-end in Run-End Encoded
985+
/// arrays
986+
///
987+
/// \param[in] type_id the type-id to check
988+
/// \return whether type-id can represent a run-end value
989+
constexpr bool is_run_end_type(Type::type type_id) {
990+
switch (type_id) {
991+
case Type::INT16:
992+
case Type::INT32:
993+
case Type::INT64:
994+
return true;
995+
default:
996+
break;
997+
}
998+
return false;
999+
}
1000+
9841001
/// \brief Check for a primitive type
9851002
///
9861003
/// This predicate doesn't match null, decimals and binary-like types.

‎cpp/src/arrow/util/ree_util.h‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -209,18 +209,19 @@ class RunEndEncodedArraySpan {
209209
/// \brief Create an iterator from a logical position and its
210210
/// pre-computed physical offset into the run ends array
211211
///
212-
/// \param logical_pos is an index in the [0, length()) range
212+
/// \param logical_pos is an index in the [0, length()] range
213213
/// \param physical_offset the pre-calculated PhysicalIndex(logical_pos)
214214
Iterator iterator(int64_t logical_pos, int64_t physical_offset) const {
215215
return Iterator{PrivateTag{}, *this, logical_pos, physical_offset};
216216
}
217217

218218
/// \brief Create an iterator from a logical position
219219
///
220-
/// \param logical_pos is an index in the [0, length()) range
220+
/// \param logical_pos is an index in the [0, length()] range
221221
Iterator iterator(int64_t logical_pos) const {
222-
assert(logical_pos < length());
223-
return iterator(logical_pos, PhysicalIndex(logical_pos));
222+
return iterator(logical_pos, logical_pos < length()
223+
? PhysicalIndex(logical_pos)
224+
: RunEndsArray(array_span).length);
224225
}
225226

226227
/// \brief Create an iterator representing the logical begin of the run-end

0 commit comments

Comments
 (0)