[ADT] Fix llvm::concat_iterator for ValueT == common_base_class *

[jalopezg-git]

Fix llvm::concat_iterator for the case of ValueT being a pointer to a common base class to which the result of dereferencing any iterator in ItersT can be casted to. In particular, the case below was not working before this patch, but I see no particular reason why it shouldn't be supported.

namespace some_namespace {
struct some_struct {
  std::vector<int> data;
  std::string swap_val;
};

struct derives_from_some_struct : some_struct {
};
} // namespace some_namespace

TEST(STLExtrasTest, ConcatRangePtrToDerivedClass) {
  some_namespace::some_struct S0{};
  some_namespace::derives_from_some_struct S1{};
  SmallVector<some_namespace::some_struct *> V0{&S0};
  SmallVector<some_namespace::derives_from_some_struct *> V1{&S1, &S1};

  // Use concat over ranges of pointers to different (but related) types.
  EXPECT_THAT(concat<some_namespace::some_struct *>(V0, V1),
              ElementsAre(&S0, static_cast<some_namespace::some_struct *>(&S1),
                          static_cast<some_namespace::some_struct *>(&S1)));
}

Per https://en.cppreference.com/w/cpp/language/implicit_conversion.html, Sec. Pointer conversions,

A prvalue ptr of type “pointer to (possibly cv-qualified) Derived” can be converted to a prvalue of type “pointer to (possibly cv-qualified) Base”, where Base is a base class of Derived, and Derived is a complete class type.

I.e. conversion shall be possible, but the former implementation of llvm::concat_iterator forbids that, given that handle_type is pointer-to-pointer type, which is not convertible.

[llvmbot]

@llvm/pr-subscribers-llvm-adt

Author: Javier Lopez-Gomez (jalopezg-git)

Changes

Fix llvm::concat_iterator for the case of ValueT being a pointer to a common base class to which the result of dereferencing any iterator in ItersT can be casted to.

In particular, the case below was not working before this patch, but I see no particular reason why it shouldn't be supported.

namespace some_namespace {
struct some_struct {
  std::vector<int> data;
  std::string swap_val;
};

struct derives_from_some_struct : some_struct {
};
} // namespace some_namespace

TEST(STLExtrasTest, ConcatRangePtrToDerivedClass) {
  auto S0 = std::make_unique<some_namespace::some_struct>();
  auto S1 = std::make_unique<some_namespace::derives_from_some_struct>();
  SmallVector<some_namespace::some_struct *> V0{S0.get()};
  SmallVector<some_namespace::derives_from_some_struct *> V1{S1.get(), S1.get()};

  // Use concat over ranges of pointers to different (but related) types.
  EXPECT_THAT(concat<some_namespace::some_struct *>(V0, V1),
             ElementsAre(S0.get(),
                         static_cast<some_namespace::some_struct *>(S1.get()),
                         static_cast<some_namespace::some_struct *>(S1.get())));
}

---

Full diff: https://github.com/llvm/llvm-project/pull/144744.diff

2 Files Affected:

• (modified) llvm/include/llvm/ADT/STLExtras.h (+6-5)
• (modified) llvm/unittests/ADT/STLExtrasTest.cpp (+16)

diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h
index eea06cfb99ba2..951da522a8aa2 100644
--- a/llvm/include/llvm/ADT/STLExtras.h
+++ b/llvm/include/llvm/ADT/STLExtras.h
@@ -1030,14 +1030,15 @@ class concat_iterator
                                   std::forward_iterator_tag, ValueT> {
   using BaseT = typename concat_iterator::iterator_facade_base;
 
-  static constexpr bool ReturnsByValue =
-      !(std::is_reference_v<decltype(*std::declval<IterTs>())> && ...);
+  static constexpr bool ReturnsValueOrPointer =
+      !(std::is_reference_v<decltype(*std::declval<IterTs>())> && ...)
+      || (std::is_pointer_v<IterTs> && ...);
 
   using reference_type =
-      typename std::conditional_t<ReturnsByValue, ValueT, ValueT &>;
+      typename std::conditional_t<ReturnsValueOrPointer, ValueT, ValueT &>;
 
   using handle_type =
-      typename std::conditional_t<ReturnsByValue, std::optional<ValueT>,
+      typename std::conditional_t<ReturnsValueOrPointer, std::optional<ValueT>,
                                   ValueT *>;
 
   /// We store both the current and end iterators for each concatenated
@@ -1088,7 +1089,7 @@ class concat_iterator
     if (Begin == End)
       return {};
 
-    if constexpr (ReturnsByValue)
+    if constexpr (ReturnsValueOrPointer)
       return *Begin;
     else
       return &*Begin;
diff --git a/llvm/unittests/ADT/STLExtrasTest.cpp b/llvm/unittests/ADT/STLExtrasTest.cpp
index 286cfa745fd14..0e6b040a08f4a 100644
--- a/llvm/unittests/ADT/STLExtrasTest.cpp
+++ b/llvm/unittests/ADT/STLExtrasTest.cpp
@@ -398,6 +398,9 @@ struct some_struct {
   std::string swap_val;
 };
 
+struct derives_from_some_struct : some_struct {
+};
+
 std::vector<int>::const_iterator begin(const some_struct &s) {
   return s.data.begin();
 }
@@ -532,6 +535,19 @@ TEST(STLExtrasTest, ConcatRangeADL) {
   EXPECT_THAT(concat<const int>(S0, S1), ElementsAre(1, 2, 3, 4));
 }
 
+TEST(STLExtrasTest, ConcatRangePtrToDerivedClass) {
+  auto S0 = std::make_unique<some_namespace::some_struct>();
+  auto S1 = std::make_unique<some_namespace::derives_from_some_struct>();
+  SmallVector<some_namespace::some_struct *> V0{S0.get()};
+  SmallVector<some_namespace::derives_from_some_struct *> V1{S1.get(), S1.get()};
+
+  // Use concat over ranges of pointers to different (but related) types.
+  EXPECT_THAT(concat<some_namespace::some_struct *>(V0, V1),
+	      ElementsAre(S0.get(),
+			  static_cast<some_namespace::some_struct *>(S1.get()),
+			  static_cast<some_namespace::some_struct *>(S1.get())));
+}
+
 TEST(STLExtrasTest, MakeFirstSecondRangeADL) {
   // Make sure that we use the `begin`/`end` functions from `some_namespace`,
   // using ADL.

[github-actions]

✅ With the latest revision this PR passed the C/C++ code formatter.

[kuhar]

I took a closer look and I think I understand what the underlying issue was: with mixed pointer types, reference/handle type can no longer be T*& / T** because while it's fine to cast derived pointers to T*, we can't take an address off them using that base type.

I wonder if we should tighten this check to make sure that at least one input range type doesn't match the ValueT pointer type, and with that having them be returned via the same logic as ReturnsByValue doesn't sounds too bad to me. WDYT?

[jalopezg-git]

I took a closer look and I think I understand what the underlying issue was: with mixed pointer types, reference/handle type can no longer be T*& / T** because while it's fine to cast derived pointers to T*, we can't take an address off them using that base type.

Yeah, I have updated the PR description s.t. it is more clear about that.

I wonder if we should tighten this check to make sure that at least one input range type doesn't match the ValueT pointer type, and with that having them be returned via the same logic as ReturnsByValue doesn't sounds too bad to me. WDYT?

The current definition of ReturnsConvertiblePointer requires that all iterator types in ItersT are convertible to the pointer type ValueT 👍; otherwise, it falls back to the old logic based on ReturnsByValue.

[jalopezg-git]

A have added a couple more reviewers to gather additional feedback (@lhames, @chsigg). Just let me know if more changes are needed to this PR!

[kuhar]

I think the two pieces of feedback in #144744 (comment) haven't been addressed yet:

1. I think we should test whether the values we iterate over are references to elements or not
2. For containers of the same pointer type as in concat<T *>, I think we should keep existing behavior and allow for modification

[jalopezg-git]

Apologies for coming back to this w/ almost a 3-month delay 😅; it has been quite hectic due to work in a different project.

@kuhar handle_type was a major cause of headaches here; therefore, I first simplified lllvm::concat_iterator to get rid of it. IMHO, the result is simpler / more maintainable. See commit cd1127c.

I think the two pieces of feedback in #144744 (comment) haven't been addressed yet:

1. I think we should test whether the values we iterate over are references to elements or not

Tests have been updated; in particular, PTAL at https://github.com/llvm/llvm-project/pull/144744/files#diff-3ec26250dd1ddfd2682b4abed65da0d8cbb509991fc1a7a3795bb29389e3da6cR548 and https://github.com/llvm/llvm-project/pull/144744/files#diff-3ec26250dd1ddfd2682b4abed65da0d8cbb509991fc1a7a3795bb29389e3da6cR569.

2. For containers of the same pointer type as in `concat<T *>`, I think we should keep existing behavior and allow for modification

In case all IterTs... yield the same value type as ValueT (see https://github.com/llvm/llvm-project/pull/144744/files#diff-d6563ab6a854637e8bc9e97fe718cd19dda63da0321091e9f0bf71ecb20d8003R999), reference_type is a reference type and allows for container modification.
See test at https://github.com/llvm/llvm-project/pull/144744/files#diff-3ec26250dd1ddfd2682b4abed65da0d8cbb509991fc1a7a3795bb29389e3da6cR550.

[jalopezg-git]

@kuhar, thank you for your previous feedback -- much appreciated!

@CarlosAlbertoEnciso , @jmorse , @kuhar This pull request is now ready for another round of review 👍.

[kuhar]

Looks good, just a couple of minor issues

[jalopezg-git]

Thank you for the invaluable feedback, @kuhar!