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.