4197. Complexity of std::visit with immediate functions

Section: 22.6.7 [variant.visit] Status: New Submitter: Jiang An Opened: 2025-01-26 Last modified: 2025-01-30

Priority: 2

View all other issues in [variant.visit].

View all issues with New status.

Discussion:

std::visit generally needs to be implemented with "vtables" that contain function pointers. When std::visit needs to call an immediate function (e.g. when passing a lambda whose operator() is consteval), the vtable will contain a pointer to an immediate-escalated function, which forbids the vtable from being a constexpr variable.

In order to properly handle immediate functions in std::visit, it seems necessary to form the vtable, or do some non-constant-time lookup each time when calling std::visit. In other words, 22.6.7 [variant.visit]/8 seems to be unimplementable when an immediate function is involved.

[2025-01-01; P3603R0 addresses this]

[2025-01-30; Reflector poll]

Set priority to 2 after reflector poll.

Proposed resolution:

This wording is relative to N5001.

1. Modify 22.6.7 [variant.visit] as indicated:

   template<class Visitor, class... Variants>
     constexpr see below visit(Visitor&& vis, Variants&&... vars);
   template<class R, class Visitor, class... Variants>
     constexpr R visit(Visitor&& vis, Variants&&... vars);
   

   -1- […] Let n be sizeof...(Variants). […]

   […]

   -8- Complexity: If n > 1 or any of the aforementioned INVOKE operations calls an immediate function, the invocation of the callable object has no complexity requirements. OtherwiseFor n ≤ 1, the invocation of the callable object is implemented in constant time, i.e., for n = 1, it does not depend on the number of alternative types of V0. For n > 1, the invocation of the callable object has no complexity requirements.