DepthFirstIterator.h: Use C++11 features to call a completed method onthe set type, instead of requiring that one exists.

[• dberlin]

Summary

This makes the required set type of df_iterator a normal set again.
Previously, you had to have a set type with the completed method,
which meant not being able to reuse exist set types.

I'm a bit unhappy about the overload hack required to do this, so
adding some reviewers to see if they know a better way.

(PostOrderIterator.h has a similar requirement that i'll fix as a
followup, but it requires more work).

Completion is also really a function that belongs as part of the
iterator, but it was non-trivial to simply make the iterator take it
as a function without a lot of other changes (due to the need for a
default argument, etc), due to the fun of trying to use lambdas as
template parameters.

[• dberlin]

I haven't heard any better approaches yet, but i'll give a week before committing this.

[davide]

I personally don't know a better way, so I'm fine with this.

[davide]

BTW, are there other iterators where we want to apply this trick?

[dblaikie]

include/llvm/ADT/DepthFirstIterator.h

83

I'm guessing this is for consistency? But I'd probably write this with a traditional return type?

void call_completed_method_imp(...) {

88–89

What's the delayed return type achieve here - given that there's the fallback overload of call_completed_method_imp, it wouldn't be providing any SFINAE, would it? (& there's not some other overload of call_completed_method that'd be selected)

Should this be:

void call_completed_method(...) {
  return call_completed_method_imp(t, V, 0);
}

[• dberlin]

include/llvm/ADT/DepthFirstIterator.h

83

yes, it was consistency, i've changed it.

88–89

Nothing now.
To give some context, i was playing around with trying to transform the existence/non-existence into a bool template parameter that was inferred, so we wouldn't need the overload hack.
It turns out to be possible using constexpr functions, but doesn't seem to work in all compilers yet.

I've fixed this

[• dberlin]

• Update for review comments

[dblaikie]

Any chance of a unit test for this?

But as for the general design - yeah, this looks about like what I'd expect to see to achieve this. Hadn't seen the overload preference trick (int/bool) - and nice to see more decltype based SFINAE rather than all the trait goo we'd have had to have written in the past.

include/llvm/ADT/DepthFirstIterator.h

80

the 'return' here might be a bit misleading/confusing - since the return type of call_completed_method_imp is void, this statement is only valid if 'completed' returns void as well. Probably drop/remove the 'return' here.

[• dberlin]

I'll add a unit test.

FWIW, you can get rid of the overload hack, i just can't get it to work in all compilers.

You can now nice create a class that has a ::value of true or false if the method exists, but passing that as a template parameter doesn't work so well yet, and using constexpr functions to achieve the same goal doesn't quite work yet either.

[dblaikie]

In D38806#902356, @dberlin wrote:

I'll add a unit test.

FWIW, you can get rid of the overload hack, i just can't get it to work in all compilers.

You can now nice create a class that has a ::value of true or false if the method exists,

Ah, yeah, I think I've written traits classes like that - but at least the ones I've done would take a lot more code (& eventually involve a similar overload set or the like) than this approach.

but passing that as a template parameter doesn't work so well yet, and using constexpr functions to achieve the same goal doesn't quite work yet either.

include/llvm/ADT/DepthFirstIterator.h

public:
 
   SetType &Visited;
 };
 
 // The visited stated for the iteration is a simple set augmented with
 // one more method, completed, which is invoked when all children of a
 // node have been processed. It is intended to distinguish of back and
 // cross edges in the spanning tree but is not used in the common case.
-template <typename NodeRef, unsigned SmallSize=8>
-struct df_iterator_default_set : public SmallPtrSet<NodeRef, SmallSize> {
-  using BaseSet = SmallPtrSet<NodeRef, SmallSize>;
-  using iterator = typename BaseSet::iterator;
-
-  std::pair<iterator,bool> insert(NodeRef N) { return BaseSet::insert(N); }
-  template <typename IterT>
-  void insert(IterT Begin, IterT End) { BaseSet::insert(Begin,End); }
+// If completed exists in the set type, it is called.
+template <class NodeRef, unsigned SmallSize = 8>
+using df_iterator_default_set = SmallPtrSet<NodeRef, 8>;
+
+// This lets us detect if the set we've been handed has a completed method we
+// should be calling.  The int vs bool argument is to make it prefer one
+// overload over another in the case of ambiguity.  bool requires a conversion,
+// the int does not.
+template <typename T, typename NodeRef>
+auto call_completed_method_imp(T &t, NodeRef V, int)
+    -> decltype(t.completed(V), void()) {
+  return t.completed(V);
+}
+template <typename T, typename NodeRef>
+void call_completed_method_imp(T &t, NodeRef V, bool) {
+  return;
+}
 
-  void completed(NodeRef) {}
-};
+template <typename T, typename NodeRef>
+void call_completed_method(T &t, NodeRef V){
+  call_completed_method_imp(t, V, 0);
+}
 
 // Generic Depth First Iterator
 template <class GraphT,
           class SetType =
               df_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>,
           bool ExtStorage = false, class GT = GraphTraits<GraphT>>
 class df_iterator
     : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
do {
         NodeRef Next = *(*Opt)++;
         // Has our next sibling been visited?
         if (this->Visited.insert(Next).second) {
           // No, do it now.
           VisitStack.push_back(StackElement(Next, None));
           return;
         }
       }
-      this->Visited.completed(Node);
+      call_completed_method(this->Visited, Node);
 
       // Oops, ran out of successors... go up a level on the stack.
       VisitStack.pop_back();
     } while (!VisitStack.empty());
   }
 
 public:
   using pointer = typename super::pointer;