Utility to construct visitors from lambdas.

[dblaikie]

Needs some unit tests.

Could this be used as part of the llvm::Error handleAllErrors stuff (cc @lhames)?

[bakhtiyarneyman]

Added a unit test.

[bakhtiyarneyman]

Re: handleAllErrors. Maybe. It might result in better runtime performance (because there is not recursion on the handlers), but it's also a rewrite. I am not sure if you are asking me to do something. :)

[bakhtiyarneyman]

Replaced class with typename in template definition.

[mehdi_amini]

llvm/include/llvm/ADT/Visitor.h

36

Are the classes above part of the public API or could they be wrapped in a detail namespace?

37

Can you add some doc? And maybe include some code samples here if possible.

[dblaikie]

In D99560#2660032, @bakhtiyarneyman wrote:

Re: handleAllErrors. Maybe. It might result in better runtime performance (because there is not recursion on the handlers), but it's also a rewrite. I am not sure if you are asking me to do something. :)

Not asking you to do anything necessarily - though I think it's worth someone (you or @lhames perhaps) checking if the abstraction generalizes well to other/existing use cases.

This relies on the ability to derive from the functors passed into this code - any sense of whether it should be generalized over functors that may not be able to be derived from?

It also makes a copy of the functors (could be improved to use move construction, I think?) - would it be appropriate for this to be more direct, only taking references to the functors? (but then only usable directly/within the same full expression, without creating a visitor object that could be used later)

[bakhtiyarneyman]

Added docs with usage example. Hid implementation in detail namespace.

[bakhtiyarneyman]

Regarding deriving from using other kinds of functors: I have not yet seen a need for this. My preference is to cross that bridge when we reach it. :)

Regarding taking references to the functors: I played around but on my first attempts the assembly seemed to have become scarier than without the references, so I decided not to push it further. Here's the evidence: https://godbolt.org/z/eoGKMW3jx

[bakhtiyarneyman]

Include the VisitorTest.cpp into the CMakeList.txt.

[dblaikie]

In D99560#2665902, @bakhtiyarneyman wrote:

Regarding deriving from using other kinds of functors: I have not yet seen a need for this. My preference is to cross that bridge when we reach it. :)

Regarding taking references to the functors: I played around but on my first attempts the assembly seemed to have become scarier than without the references, so I decided not to push it further. Here's the evidence: https://godbolt.org/z/eoGKMW3jx

I worry that without this kind of design it'll be awkward to use and inefficient - copying (even if that's fixed to use move instead) lambdas when they could have many captures/be expensive to copy, etc.

[lhames]

In D99560#2660464, @dblaikie wrote:

Not asking you to do anything necessarily - though I think it's worth someone (you or @lhames perhaps) checking if the abstraction generalizes well to other/existing use cases.

This is dispatching based on static type, handleAllErrors is dispatching based on the dynamic type of the error. I suspect that those two use-cases are different enough that there's limited value in unifying the code.

[dblaikie]

In D99560#2666870, @lhames wrote:

In D99560#2660464, @dblaikie wrote:

Not asking you to do anything necessarily - though I think it's worth someone (you or @lhames perhaps) checking if the abstraction generalizes well to other/existing use cases.

This is dispatching based on static type, handleAllErrors is dispatching based on the dynamic type of the error. I suspect that those two use-cases are different enough that there's limited value in unifying the code.

ah, fair enough. Thanks for taking a look.

[mehdi_amini]

In D99560#2665902, @bakhtiyarneyman wrote:

Regarding deriving from using other kinds of functors: I have not yet seen a need for this. My preference is to cross that bridge when we reach it. :)

Regarding taking references to the functors: I played around but on my first attempts the assembly seemed to have become scarier than without the references, so I decided not to push it further. Here's the evidence: https://godbolt.org/z/eoGKMW3jx

Have you tried adding -O3? Seems like it impacts your Godbolt example quite significantly.

Also to really be relevant for LLVM, -fno-exceptions -fno-rtti helps in some cases as well (not here I think).

[ezhulenev]

std::forward with inheritance does not remove a need to invoke a copy constructors, I managed to implement overloaded using a struct member and super ugly SFINAE that does properly captures lambdas by reference when lambda is a lvalue, however it still does need to copy when lambda is rvalue: https://godbolt.org/z/dqshPW6h1 (top most example, I just count the number of HeavyStuff::HeavyStuff(HeavyStuff const&) copy constructor calls in the generated code). But it does look much worse than inheritance.

Though with -O3 version with forward and version with struct member generate less code than copying by value.

[dblaikie]

In D99560#2667272, @ezhulenev wrote:

std::forward with inheritance does not remove a need to invoke a copy constructors, I managed to implement overloaded using a struct member and super ugly SFINAE that does properly captures lambdas by reference when lambda is a lvalue, however it still does need to copy when lambda is rvalue: https://godbolt.org/z/dqshPW6h1 (top most example, I just count the number of HeavyStuff::HeavyStuff(HeavyStuff const&) copy constructor calls in the generated code). But it does look much worse than inheritance.

Though with -O3 version with forward and version with struct member generate less code than copying by value.

Making a copy on rvalues would be necessary given the current API design where the visitor is an object - but I'm not sure that's a necessary feature of the API, is it? As opposed to a straight function visit(lambda1, lambda2, value) - no need to make copies/keep anything alive because it'll all be alive for the full expression.

[ezhulenev]

It’s impossible to statically dispatch to the correct lambda with such API
(or at least a very difficult exercise). std::visit takes a single visitor
and multiple variants, not the other way around. Stitching lambdas together
is just one way of constructing a visitor type, it can be a plain old class
with overloaded operator() set.

[dblaikie]

In D99560#2667327, @ezhulenev wrote:

It’s impossible to statically dispatch to the correct lambda with such API (or at least a very difficult exercise). std::visit takes a single visitor and multiple variants, not the other way around. Stitching lambdas together is just one way of constructing a visitor type, it can be a plain old class with overloaded operator() set.

ah, fair point about the std::visit API design taking a type with op() overloads and using that to resolve which call, etc.

could makeVisitor at least be improved to support move-only functors (& avoid unnecessary copies of copyable functors too, when they could instead be efficiently moved), perhaps? I hope that wouldn't add too much complexity (probably a few std::forwards here and there)

[scott.linder]

In D99560#2667272, @ezhulenev wrote:

std::forward with inheritance does not remove a need to invoke a copy constructors, I managed to implement overloaded using a struct member and super ugly SFINAE that does properly captures lambdas by reference when lambda is a lvalue, however it still does need to copy when lambda is rvalue: https://godbolt.org/z/dqshPW6h1 (top most example, I just count the number of HeavyStuff::HeavyStuff(HeavyStuff const&) copy constructor calls in the generated code). But it does look much worse than inheritance.

As you mention, this version doesn't work for e.g. move-only lambdas, see https://godbolt.org/z/T659nM5fc (I essentially just made HeavyStuff move-only, and captured it in both lambdas via move).

I think by making the members universal references we can support move-only lambda types. I tried to make the necessary changes in https://godbolt.org/z/9YTq9d6r4 and it seems to be compiling. I'm still not confident it is completely correct, and I imagine there are some additional operator() const overloads needed, as well as marking things like the constructors constexpr where applicable, but I think in principle we should be able to do perfectly-forwarded makeVisitor.

As a note, I made some other changes to make this simpler, including using derivation to replace the ov member, as otherwise it is harder to force the ov member to be a universal reference type (because for some deduced type T and some concrete type template foo: T && m; is a universal reference type and foo<T> && m; is just an rvalue reference). I also think I avoided some of the extra SFINAE parameters needed by using -> decltype(...), but I'm not sure this is completely correct either?

Edit: I don't know that I was thinking quite right about the whole thing, as the univeral reference members aren't required to support move-only lambda types, and they can easily become dangling if the user isn't aware of it. For example the exact version I posted cannot invoke UB (AFAIK), but simply moving the call to make_visitor before a sequence point does, e.g. this is UB:

auto il = [x{std::move(x)}](int i) { return 4; };
auto sl = [x{std::move(x)}](std::string s) { return 5; };
auto v = make_visitor(std::move(il), std::move(sl));
return std::visit(make_visitor(std::move(il), std::move(sl)), vari);

I don't know if this is an issue? We can likely document this the same way e.g. std::forward_as_tuple or llvm::Twine do, warning the user that make_visitor does not extend the lifetime of temporaries. Alternatively we can just make the members value types again, and we maybe pay for an extra copy or move?

[scott.linder]

I think I ran into a reason to require the visitor we create be able to derive from all of its Callables: it makes it possible to transparently select the correct overload via the normal overload resolution rules, which as of C++14 and the addition of generic lambdas gives the user a way to naturally describe a "default" case.

For example, with the inheritance version this works:

variant<bool, int, double> V;
visit(makeVisitor(
  [](int Int) { /* ... */ },
  [](auto BoolOrDouble) { /* ... */ }
), V);

And it is equivalent to this:

variant<bool, int, double> V;
visit(makeVisitor(
  [](auto BoolOrDouble) { /* ... */ },
  [](int Int) { /* ... */ },
), V);

This is possible because inheritance permits using Callable::operator(); to actually bring all of the overloads into one scope, and the generic lambda de-sugars to a template lambda, which is always ordered after any other non-template lambdas during overload resolution.

Do we know any way to achieve this without inheritance? The closest approximation I could come up with is to make the order of the arguments to makeVisitor significant, such that they are visited "in order" until one is invokable. This means that the following always selects the generic lambda during overload resolution, and the other lambda is dead code:

variant<bool, int, double> V;
visit(makeVisitor(
  [](auto IntOrBoolOrDouble) { /* ... */ },
  [](int Int) { llvm_unreachable(); },
), V);

This seems a little too surprising to be acceptable, but I suppose either version could be fine so long as we are explicitly about documenting the behavior?

It may just come down to what non-derivable types we expect the user to be interested in using here? I suspect the most common case will be free functions, which I think we can handle by wrapping them in function_ref.

https://godbolt.org/z/9GW3n6nYh is a version using inheritance, but perfectly forwarding the arguments to the appropriate constructor overload. Once we get to C++20 I think passing a prvalue lambda expression will be guaranteed to never call a copy or move constructor, and before then clang seems perfectly capable of eliding them.

[dblaikie]

Yeah, can't think of a way that would do the right overload resolution (especially accounting for default arguments) without the user having to explicitly name the function type (like with std::function, for instance). So, fair enough, I'm OK with inheritance. Some std::fowarding would be nice though - tests that this doesn't copy functors when they're movable, etc.

[scott.linder]

I tried to write a version in https://reviews.llvm.org/D100670 that perfectly-forwards each argument to the (overload resolution selected) constructor of the remove_cvref type of the argument. I ended up doing this after I had already started moving some other things out of STLExtras.h, so the patch currently depends on https://reviews.llvm.org/D100670 and https://reviews.llvm.org/D100669 but you can equally well ignore those and makeVisitor can land first.

I didn't put makeVisitor in a dedicated header, as it doesn't seem substantial enough to me, but I'm happy to move it out of STLExtras.h again.

llvm/include/llvm/ADT/Visitor.h

+//===- llvm/ADT/Visitor.h - Visitors constructed from lambdas. --*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the Visitor class, which is a utility that constructs
+// visitors from lambdas. Can be used for e.g. visiting PointerUnion.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_VISITOR_H
+#define LLVM_ADT_VISITOR_H
+
+namespace llvm {
+
+namespace visitor_detail {
+
+template <typename... Fs> struct Visitor;
+
+template <typename Head, typename... Tail>
+struct Visitor<Head, Tail...> : Head, Visitor<Tail...> {
+  explicit Visitor(Head head, Tail... tail)
+      : Head(head), Visitor<Tail...>(tail...) {}
+
+  using Head::operator();
+  using Visitor<Tail...>::operator();
+};
+
+template <typename Head> struct Visitor<Head> : Head {
+  explicit Visitor(Head head) : Head(head) {}
+
+  using Head::operator();
+};
+
+} // namespace visitor_detail
+
+/// Utility to construct visitors from lambdas.
+///
+/// auto visitor = makeVisitor(
+///   [](int i) { return "int"; },
+///   [](std::string s) { return "str"; });
+/// auto a = visitor(42); // `a` is now "int".
+/// auto b = visitor("foo"); // `b` is now "str".
+template <typename... Lambdas> auto makeVisitor(Lambdas... lambdas) {
+  return visitor_detail::Visitor<Lambdas...>(lambdas...);
+}
+
+} // namespace llvm
+
+#endif

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   StringRefTest.cpp
   StringSetTest.cpp
   StringSwitchTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp
   TypeSwitchTest.cpp
   TypeTraitsTest.cpp
+  VariantTest.cpp
   WaymarkingTest.cpp
   )
 
 target_link_libraries(ADTTests PRIVATE LLVMTestingSupport)
 
 add_dependencies(ADTTests intrinsics_gen)

llvm/unittests/ADT/VisitorTest.cpp

+//===- VisitorTest.cpp - Unit tests for a sequence abstraciton -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/Visitor.h"
+#include "gtest/gtest.h"
+
+#include <list>
+
+using namespace llvm;
+
+namespace {
+
+TEST(VisitorTest, Basic) {
+  auto visitor = llvm::makeVisitor([](int a) { return "int"; },
+                                   [](std::string a) { return "str"; });
+
+  EXPECT_EQ("int", visitor(42));
+  EXPECT_EQ("str", visitor("foo"));
+}
+
+} // anonymous namespace