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

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

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);
}

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.

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.

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

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.

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.

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.

Casey Carter (@CaseyCarter)

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.

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

`_STD`-qualify `_Ugly` non-member function calls in `<variant>`

~~Should we also _CSTD- or ::-qualify _Ugly names (including intrinsics) in the global namespace?~~

We should. Such qualifying is needed.

This is failing even after #3148. The problem is that there are intentional ADL swaps. Is this a resolvable problem?

#include <variant>

struct incomplete;

template<class T>
struct wrapper { T a; };

using inp = wrapper<incomplete>*;

int main() {
    std::variant<inp> v;
    v.swap(v); // ...
}

Is this a resolvable problem?

I don't think this is solvable, unless we change the standard wording to restrict ADL for swap to enumeration and class types (like ranges::swap).

restrict ADL for swap to enumeration and class types

That would actually be philosophically safe (because non-enum/class types are primitive and therefore don't require any special swap semantics)... but at the same time it wouldn't be enough to solve the problem! Consider std::variant<std::vector<Holder<Incomplete>*>> v; v.swap(v), which would still try to swap std::vector<Holder<Incomplete>*> objects, do ADL because it's a class type, find Holder<Incomplete> as an associated type, and explode. So there are always some places that fundamentally can't be ADL-proofed. But FWLIW I'm still personally of the opinion that whatever can be ADL-proofed, should be. Whenever an STL facility explodes due to ADL, I should be able to point at a specific piece of it and say, "Look, there's literally no way to do this piece without ADL." It should never be a simple five-character fix.

I note that my first comment on this issue #140 (comment) was about optional<T>, and #140 (comment) is about using types like this as implementation details; and then this month we have LWG 3969 which is precisely about using optional<T> as an implementation detail (such that it's ADL-proof to call init.value(), but not ADL-proof to call *init as currently specified in [alg.fold]/10).

I think there should be a way to test Can unqualified call (so we can do constexpr dispatch for them). Unfortunately so far there is no way to do that.

ranges::swap is *slightly* better than unqualified swap:

#include <iostream>
#include <ranges>
using namespace std;

struct inc;
template<class T> struct wrp { T t; };
using inp = wrp<inc>*;

int main()
{
    inp a{}, b{};
    _RANGES swap(a, b); // ok...

    using pr = std::pair<inp, inp>;
    pr c{}, d{};
    // _RANGES swap(c, d); // no...
}

I'm curious, what's the advantage of ADL-based swap over public swap method?

Currently no implementation accepts this example due to ADL in the comparison of iterators (Godbolt link). However, the standard doesn't seem to state that this is UB/ill-formed.

#include <vector>

struct incomplete;

template<class T>
struct holder { T t; };

int main()
{
    std::vector<holder<incomplete>*> v{};
    v.emplace_back();
}

It seems that iterators of standard containers shouldn't be implemented as class templates, and we can't fix this without breaking ABI.

1. Add _STD to defend ADL, towards microsoft#140,

#include <vector>

struct incomplete;

template
struct holder { T t; };

int main()
{
std::vector<holder*> v{};
v.emplace_back();
}

MSVC + STL now accepts it.

I've put together a libclang-based script that qualifies calls automatically. It's not bulletproof (it has some false positives and false negatives), but it should automate some of this work. I'm test-driving it in #5629.

Script

#!/usr/bin/env python

from clang.cindex import TranslationUnit, CursorKind, TokenKind
from pathlib import Path
from sys import argv
import re

def is_interesting_identifier(identifier):
    # These exceptions are functions deliberately called via ADL.
    exceptions = ["_Hash_equal", "_Verify_range", "_Same_sequence"]
    return re.match(r"^_[A-Z_]", identifier) and identifier not in exceptions

def fully_qualified_namespace(cursor):
    ret = "::"
    while cursor is not None:
        if cursor.kind == CursorKind.NAMESPACE:
            ret = f"::{cursor.spelling}{ret}"
        cursor = cursor.semantic_parent
    return ret

def correct_qualification(cursor):
    ns = fully_qualified_namespace(cursor)
    return {
        "::std::" : "_STD ",
        "::std::chrono::" : "_CHRONO ",
        "::std::ranges::" : "_RANGES ",
        "::stdext::" : "_STDEXT ",
    }.get(ns, ns)

def main():
    source = Path(argv[1]).read_text(newline="") # No newline translation.
    tu = TranslationUnit.from_source(argv[1], args=argv[2:])

    free_functions = {n.spelling : correct_qualification(n) for n in tu.cursor.walk_preorder() if (
        n.kind in [CursorKind.FUNCTION_TEMPLATE, CursorKind.FUNCTION_DECL] and
        n.semantic_parent.kind in [
            CursorKind.NAMESPACE, CursorKind.TRANSLATION_UNIT, CursorKind.LINKAGE_SPEC
        ]
        and is_interesting_identifier(n.spelling)
    )}

    tokens = list(tu.cursor.get_tokens())
    corrections = [t for i, t in enumerate(tokens) if (
        t.kind == TokenKind.IDENTIFIER and
        t.spelling in free_functions and
        t.cursor.kind not in [
            CursorKind.NAMESPACE, CursorKind.TRANSLATION_UNIT, CursorKind.LINKAGE_SPEC,
            CursorKind.FUNCTION_DECL, CursorKind.FUNCTION_TEMPLATE, CursorKind.CXX_METHOD,
            CursorKind.STRUCT_DECL, CursorKind.CLASS_DECL, CursorKind.UNION_DECL,
            CursorKind.CLASS_TEMPLATE, CursorKind.CLASS_TEMPLATE_PARTIAL_SPECIALIZATION,
        ] and
        (i == 0 or tokens[i - 1].spelling not in ["::", "_STD", "_CHRONO", "_RANGES", "_STDEXT", "_CSTD", ".", ">", "->"]) and
        (i + 1) < len(tokens) and
        tokens[i + 1].spelling in ["<", "("]
    )]

    for t in reversed(corrections): # Work in reverse to not invalidate offsets.
        source = f"{source[:t.location.offset]}{free_functions[t.spelling]}{source[t.location.offset:]}"

    Path(argv[1]).write_text(source, newline="") # No newline translation.

if __name__ == "__main__":
    main()

To try it locally: save that snippet as adl_proof.py in the project root. Run pip install libclang (the PyPi package is outdated and will install Clang 18, but that's okay, it works). Now you can run ./adl_proof.py <FILE> <CLANG_OPTIONS> to update <FILE>.
For example, you can update <chrono> with ./adl_proof.py stl/inc/chrono -xc++ -std=c++17 -Istl/inc. It might miss code that's ifdefed out, so to avoid that, I've been running it like for std in 11 14 17 20 23; do ./adl_proof.py <FILE> -xc++ -std=c++$std -D_ITERATOR_DEBUG_LEVEL=2 -Istl/inc; done.

It doesn't yet work with <complex> or anything in experimental/, but I've checked that if you run it on all the other headers under stl/inc, everything at least still compiles.

We may want to cover <flat_set> / <flat_maP too

Navigation Menu

Repository navigation

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

5 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Activity

Quuxplusone commented on Sep 27, 2019

StephanTLavavej commented on Sep 27, 2019

Quuxplusone commented on Sep 27, 2019

StephanTLavavej commented on Sep 27, 2019

BillyONeal commented on Sep 30, 2019

CaseyCarter commented on Sep 14, 2022

BillyONeal commented on Sep 14, 2022

StephanTLavavej commented on Sep 14, 2022

frederick-vs-ja commented on Sep 15, 2022

5 remaining items

frederick-vs-ja commented on Oct 17, 2022

achabense commented on Aug 16, 2023

frederick-vs-ja commented on Aug 17, 2023

Quuxplusone commented on Aug 17, 2023

achabense commented on Aug 17, 2023

achabense commented on Sep 7, 2023

frederick-vs-ja commented on Oct 21, 2023

YexuanXiao commented on Jun 30, 2025

localspook commented on Jun 30, 2025

AlexGuteniev commented on Feb 4, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions