STL: We should _STD qualify _Ugly function calls to avoid ADL

[StephanTLavavej]

See "ADL can interfere even with uglified names" by Arthur O'Dwyer.

We've survived 20+ years with unqualified _Ugly function calls, but perhaps we should consider changing this. It's possible that this could improve throughput.

List of headers to process, as mentioned in #140 (comment) below (cvt subtree intentionally omitted):

• __msvc_all_public_headers.hpp
• __msvc_chrono.hpp
• __msvc_format_ucd_tables.hpp
• __msvc_int128.hpp
• __msvc_iter_core.hpp
• __msvc_system_error_abi.hpp
• __msvc_tzdb.hpp
• __msvc_xlocinfo_types.hpp
• algorithm
• any
• array
• atomic
• barrier
• bit
• bitset
• cassert
• ccomplex
• cctype
• cerrno
• cfenv
• cfloat
• charconv
• chrono
• cinttypes
• ciso646
• climits
• clocale
• cmath
• codecvt
• compare
• complex
• concepts
• condition_variable
• coroutine
• csetjmp
• csignal
• cstdalign
• cstdarg
• cstdbool
• cstddef
• cstdint
• cstdio
• cstdlib
• cstring
• ctgmath
• ctime
• cuchar
• cwchar
• cwctype
• deque
• exception
• execution
• expected
• experimental/coroutine
• experimental/deque
• experimental/filesystem
• experimental/forward_list
• experimental/generator
• experimental/list
• experimental/map
• experimental/resumable
• experimental/set
• experimental/string
• experimental/unordered_map
• experimental/unordered_set
• experimental/vector
• filesystem
• format
• forward_list
• fstream
• functional
• future
• hash_map
• hash_set
• initializer_list
• iomanip
• ios
• iosfwd
• iostream
• iso646.h
• istream
• iterator
• latch
• limits
• list
• llll
• locale
• map
• memory
• memory_resource
• mutex
• new
• numbers
• numeric
• optional
• ostream
• queue
• random
• ranges
• ratio
• regex
• scoped_allocator
• semaphore
• set
• shared_mutex
• source_location
• span
• spanstream
• sstream
• stack
• stacktrace
• stdatomic.h
• stdexcept
• stop_token
• streambuf
• string
• string_view
• strstream
• syncstream
• system_error
• thread
• tuple
• type_traits
• typeindex
• typeinfo
• unordered_map
• unordered_set
• use_ansi.h
• utility
• valarray
• variant (_STD-qualify _Ugly non-member function calls in <variant> #3148)
• vector
• version
• xatomic.h
• xatomic_wait.h
• xbit_ops.h
• xcall_once.h
• xcharconv.h
• xcharconv_ryu.h
• xcharconv_ryu_tables.h
• xcharconv_tables.h
• xerrc.h
• xfacet
• xfilesystem_abi.h
• xhash
• xiosbase
• xkeycheck.h
• xlocale
• xlocbuf
• xlocinfo
• xlocmes
• xlocmon
• xlocnum
• xloctime
• xmemory
• xnode_handle.h
• xpolymorphic_allocator.h
• xsmf_control.h
• xstddef
• xstring
• xthreads.h
• xtimec.h
• xtr1common
• xtree
• xutility
• ymath.h
• yvals.h
• yvals_core.h

[Quuxplusone]

Your std::distance doesn't trigger the issue; but anything that calls _Get_unwrapped does. For example, std::copy.

https://godbolt.org/z/q5TeEO

struct Incomplete;
template<class T> struct Holder { T t; };

int main() {
    using Ptr = Holder<Incomplete>*;
    Ptr a[100];
    Ptr b[100];
    std::copy(a, a+10, b);
}

[StephanTLavavej]

That example is compelling, although the thought of changing all _Ugly function calls fills me with despair (more so than operator& and operator,). It seems that there are a lot of places that could accept elements of type Holder<Incomplete>* - not just algorithms, but also containers and their member functions. We use tag dispatch less frequently these days, but the number of function calls susceptible to ADL hijacking must extend far beyond _Get_unwrapped if I understand this correctly.

I am aware of (apparently) conformant code that instantly destroys any library it comes into contact with, but it is very pathological (e.g. highly poisoned operator, overloads). The element type here is fairly reasonable.

[Quuxplusone]

I think it's impossible to write a library that is immune to all variations on Holder<Incomplete>.
For example, you can't sort my array a — https://godbolt.org/z/FsV8tt — because sort inherently depends on being able to ADL-swap the element type, which you definitely can't ever do if any associated type is incomplete.

I've been trying to come up with an example where the library somewhere has to use an infix operator and we supply a class type without making it too contrived. The least-contrived thing I've come up with so far is

using T = Holder<Incomplete>*;
T t;
std::optional<T> ot;

Here t == t is OK, but ot == ot is a hard error.

std::vector<T> vt;
std::vector<std::optional<T>> vo;

std::find(vt.begin(), vt.end(), nullptr);  // technically implementable, but nobody actually does
std::find(vo.begin(), vo.end(), nullptr);  // literally unimplementable?

I believe it is impossible to accept std::find(vo.begin(), vo.end(), nullptr), because it has to be able to find std::optional's operator== via ADL in order to do its job but if it does ADL and tries to complete Holder<Incomplete> then it blows up.

[StephanTLavavej]

In that case, I think I want the LWG to tell us what to do.

[BillyONeal]

Richard Smith has brought up similar issues in the past for places we can't fix with qualification, like operator overloads. I don't think there's anything reasonable the library can do to shut this problem down completely but qualifying our _Ugly things is probably still reasonable on the basis of improved diagnostics and/or throughput.

[CaseyCarter]

Which option do we prefer:

• WONTFIX
• _STD _Meow(/*...*/) [longer/hard to miss in code review]
• (_Meow)(/*...*/)[shorter/easier to miss in code review]

I don't list ::std::_Meow(/*...*/) as an option here because we recently relitigated "_STD vs. ::std::" when Nicole joined the team.

[BillyONeal]

Looking at the long list of things attached to this, and:

Richard Smith has brought up similar issues in the past for places we can't fix with qualification, like operator overloads. I don't think there's anything reasonable the library can do to shut this problem down completely but qualifying our _Ugly things is probably still reasonable on the basis of improved diagnostics and/or throughput.

is there customer value to be gained here given that we are seemingly unable to shut the problem down completely?

EDIT: To clarify, this is more about the linked issues being marked as 'duplicates' of this one rather than this change itself.

[StephanTLavavej]

We talked about this at the weekly maintainer meeting, and we've decided to qualify (with _STD, _RANGES, _CHRONO, etc.) every _Ugly function call, like what we currently do for non-_Ugly function calls. This will avoid ADL issues as much as possible, and (as bonuses) will improve throughput by some nonzero amount (potentially significant), and will sometimes avoid infinite recursion during lookup. We'll be able to enforce _STD etc. qualification the same way we do for non-_Ugly calls (where we have a near-perfect record of detecting issues during code review), and it doesn't impact code clarity too much.

However, I want to land the Standard Library Modules PR (which modifies many lines of every header) before accepting any PRs that attempt to qualify _Ugly function calls.

When we're ready to begin qualifying all such calls, this can be done in one or a handful of headers at a time - a single massive PR updating all headers atomically is not necessary (and would be a pain to review and keep up to date with main).

Casey Carter (@CaseyCarter) mentioned that we can make a checklist of headers in this issue, when we're ready to begin accepting PRs.

[frederick-vs-ja]

It's worthwhile to notice that operator* involves ADL, and thus we should be more careful when using smart pointers as implementation details.😹