[llvm][ADT] Fix invalid `reference` type of depth-first, breadth-first and post order iterators

[zero9178]

Summary

C++s iterator concept requires operator* to return the same type as is specified by the iterators reference type. This functionality is especially important for older generic code that did not yet make use of auto.
An example from within LLVM is iterator_adaptor_base which uses the reference type of the iterator it is wrapping as its return type for operator* (this class is used as base for a lot of other functionality like filter iterators and so on).
Using any of the graph traversal iterators listed above with it would previously fail to compile due to reference being non-const while operator* returned a const reference.

This patch fixes that by correctly specifying reference and using it as the return type of operator* explicitly to prevent further issues in the future.

[kuhar]

llvm/include/llvm/ADT/BreadthFirstIterator.h

53

Could we add const conditionally, either with some type traits or define reference in terms of decltype(*declval<pointer>())?

Do you know if it there's any existing use of non-const references with these iterators?

[zero9178]

llvm/include/llvm/ADT/BreadthFirstIterator.h

53

The result of operator* has always been a const-reference so there couldn't have been (or at the very least can't currently be) any real properly compiling code that relies on reference being non-const while operator* isn't.

Defining it to decltype(*declval<pointer>()) would just be equal to value_type& no? That would at the very least not be possible in a non-const operator* and I think is intentionally not the case, since a NodeRef& would allow breaking the invariants of the iterators (would modify the NodeRef within VisitQueue)

Hope I understood your comment correctly.

[kuhar]

llvm/include/llvm/ADT/BreadthFirstIterator.h

53

Oh I see what you mean: the runtime usage used to depend on the definition of operator*() const and what this PR does is aligning the definition of the reference typedef to that usage.

I'd expect to see this operator return const_reference perhaps, but since there's no non-const version then this change seems fine to me.

llvm/include/llvm/ADT/BreadthFirstIterator.h

template <class GraphT,
               bf_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>,
           class GT = GraphTraits<GraphT>>
 class bf_iterator : public bf_iterator_storage<SetType> {
 public:
   using iterator_category = std::forward_iterator_tag;
   using value_type = typename GT::NodeRef;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
-  using reference = value_type &;
+  using reference = const value_type &;
 
 private:
   using NodeRef = typename GT::NodeRef;
   using ChildItTy = typename GT::ChildIteratorType;
 
   // First element is the node reference, second is the next child to visit.
   using QueueElement = std::pair<NodeRef, std::optional<ChildItTy>>;
 
public:
   static bf_iterator end(const GraphT &G) { return bf_iterator(); }
 
   bool operator==(const bf_iterator &RHS) const {
     return VisitQueue == RHS.VisitQueue;
   }
 
   bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
 
-  const NodeRef &operator*() const { return VisitQueue.front()->first; }
+  reference operator*() const { return VisitQueue.front()->first; }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time so that you can actually call methods on the node, because the
   // contained type is a pointer.
   NodeRef operator->() const { return **this; }
 
   bf_iterator &operator++() { // Pre-increment
     toNext();

llvm/include/llvm/ADT/DepthFirstIterator.h

template <class GraphT,
               df_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>,
           bool ExtStorage = false, class GT = GraphTraits<GraphT>>
 class df_iterator : public df_iterator_storage<SetType, ExtStorage> {
 public:
   using iterator_category = std::forward_iterator_tag;
   using value_type = typename GT::NodeRef;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
-  using reference = value_type &;
+  using reference = const value_type &;
 
 private:
   using NodeRef = typename GT::NodeRef;
   using ChildItTy = typename GT::ChildIteratorType;
 
   // First element is node reference, second is the 'next child' to visit.
   // The second child is initialized lazily to pick up graph changes during the
   // DFS.
public:
   }
   static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
 
   bool operator==(const df_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
   bool operator!=(const df_iterator &x) const { return !(*this == x); }
 
-  const NodeRef &operator*() const { return VisitStack.back().first; }
+  reference operator*() const { return VisitStack.back().first; }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time... so that you can actually call methods ON the Node, because
   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
   //
   NodeRef operator->() const { return **this; }
 
   df_iterator &operator++() { // Preincrement

llvm/include/llvm/ADT/PostOrderIterator.h

template <class GraphT,
           class SetType = SmallPtrSet<typename GraphTraits<GraphT>::NodeRef, 8>,
           bool ExtStorage = false, class GT = GraphTraits<GraphT>>
 class po_iterator : public po_iterator_storage<SetType, ExtStorage> {
 public:
   using iterator_category = std::forward_iterator_tag;
   using value_type = typename GT::NodeRef;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
-  using reference = value_type &;
+  using reference = const value_type &;
 
 private:
   using NodeRef = typename GT::NodeRef;
   using ChildItTy = typename GT::ChildIteratorType;
 
   /// Used to maintain the ordering.
   /// First element is basic block pointer, second is iterator for the next
   /// child to visit, third is the end iterator.
public:
   }
   static po_iterator end(const GraphT &G, SetType &S) { return po_iterator(S); }
 
   bool operator==(const po_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
   bool operator!=(const po_iterator &x) const { return !(*this == x); }
 
-  const NodeRef &operator*() const { return std::get<0>(VisitStack.back()); }
+  reference operator*() const { return std::get<0>(VisitStack.back()); }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time... so that you can actually call methods ON the BasicBlock, because
   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
   //
   NodeRef operator->() const { return **this; }
 
   po_iterator &operator++() { // Preincrement

llvm/unittests/ADT/BreadthFirstIteratorTest.cpp

TEST(BreadthFristIteratorTest, Cycle) {
   EXPECT_EQ(*It, G.AccessNode(2));
   ++It;
   EXPECT_EQ(It.getLevel(), 3U);
   EXPECT_EQ(*It, G.AccessNode(3));
   ++It;
   EXPECT_EQ(It, End);
 }
 
+static_assert(
+    std::is_convertible_v<decltype(*std::declval<bf_iterator<Graph<3>>>()),
+                          typename bf_iterator<Graph<3>>::reference>);
+
 } // end namespace llvm

llvm/unittests/ADT/DepthFirstIteratorTest.cpp

TEST(DepthFirstIteratorTest, ActuallyUpdateIterator) {
   G.AddEdge(0, 1);
   G.AddEdge(0, 2);
   StorageT S;
   for (auto N : make_range(DFIter::begin(G, S), DFIter::end(G, S)))
     (void)N;
 
   EXPECT_EQ(3, S.InsertVisited);
 }
+
+static_assert(
+    std::is_convertible_v<decltype(*std::declval<df_iterator<Graph<3>>>()),
+                          typename df_iterator<Graph<3>>::reference>);
+
 }

llvm/unittests/ADT/PostOrderIteratorTest.cpp

TEST(PostOrderIteratorTest, Compiles) {
   // base)
   BasicBlock *NullBB = nullptr;
   auto PI = po_end(NullBB);
   PI.insertEdge(std::optional<BasicBlock *>(), NullBB);
   auto PIExt = po_ext_end(NullBB, Ext);
   PIExt.insertEdge(std::optional<BasicBlock *>(), NullBB);
 }
 
+static_assert(
+    std::is_convertible_v<decltype(*std::declval<po_iterator<Graph<3>>>()),
+                          typename po_iterator<Graph<3>>::reference>);
+
 // Test post-order and reverse post-order traversals for simple graph type.
 TEST(PostOrderIteratorTest, PostOrderAndReversePostOrderTraverrsal) {
   Graph<6> G;
   G.AddEdge(0, 1);
   G.AddEdge(0, 2);
   G.AddEdge(0, 3);
   G.AddEdge(1, 4);
   G.AddEdge(2, 5);