Lesson 5.4 — When a name denotes several things: overload resolution, argument-dependent lookup and macro hygiene¶

Techniques: overload resolution — candidate sets, viable functions, ranking of implicit conversion sequences and the best viable function (C++, ARM 1990 and ISO C++ [over.match]; Swift's solution ranking) — argument-dependent lookup (Koenig lookup; ISO C++ [basic.lookup.argdep]), and macro hygiene as name resolution by name and syntax context (Kohlbecker et al. 1986; recap of Lesson 4.8) · Pebble implements: none of the three (Pebble has no overloading, no namespaces and no macros; print and write are its only name with special resolution, pebble-spec §6.1, §10); the lesson runs on Clang 23.1.2 and rustc 1.94.1 · Prerequisites: Lessons 5.1–5.3 · Time: 3 hours

Lessons 5.1–5.3 assumed that a use of a name denotes exactly one declaration, chosen by where the use is. Three mechanisms break that assumption on purpose. Overloading lets one name denote a set of functions and picks one from the types of the arguments. Argument-dependent lookup makes that set depend on the arguments too: the namespaces of the argument types contribute candidates. And macros paste code written in one place into another, so a name's resolution must also depend on which expansion introduced it. All three turn name resolution from a function of the text position into a function of more information — types or syntax contexts — and all three are sources of famously confusing errors.

1. Problem and motivation¶

The problem. Given a call $f(a_1, \dots, a_k)$ where lookup of $f$ yields a set of declarations, choose one using the static types of the arguments — or report that none fits or that several fit equally well. For ADL, first decide which declarations are in the set. For hygiene, given an identifier that a macro expansion created, decide which binder it refers to so that macro-introduced and user-written names never capture each other by accident.

Overload resolution¶

Ada (1983) and C++ (1985) allowed several functions with the same name and different parameter types; the call picks one by comparing the implicit conversions each would need. The rules were formalized in the Annotated C++ Reference Manual [ES90, §13.2] and are now [over.match] in the ISO standard [CPP-Draft]: collect the candidate functions, keep the viable ones (right number of parameters, and a conversion exists for every argument), and choose the unique viable function that is better than all others argument by argument. Swift overloads functions and operators and resolves them inside its constraint solver, then ranks complete solutions by a score [SWIFT-TypeChecker]. Pebble does not overload: a name in the function namespace denotes one function (E0302 on a redefinition).

Argument-dependent lookup¶

In std::cout << "hi", the operator<< that prints a string is declared in namespace std, but the call site is outside it. C++ therefore extends unqualified lookup of a function name in a call with the namespaces associated with the argument types: argument-dependent lookup (ADL), also called Koenig lookup after Andrew Koenig, who proposed it to the C++ committee [CPP-Draft, basic.lookup.argdep]. It makes operators and customization points (swap, begin) work across namespaces, at the cost that adding an argument of a new type can silently change which function a call means.

Macro hygiene¶

A macro that expands to let tmp = e; tmp + tmp must not capture a tmp the user wrote inside e, and must not be captured by a tmp at the use site. Kohlbecker, Friedman, Felleisen and Duba [KFFD86] defined hygienic expansion: identifiers carry the expansion step that introduced them, and binding respects it. Lesson 4.8 gave the expansion algorithms (marks, sets of scopes); this lesson looks at the resolution side: a binding is now keyed by the pair (name, syntax context), which is how rustc resolves local variables (SyntaxContext in compiler/rustc_span/src/hygiene.rs).

2. Definitions and algorithms¶

Overload resolution¶

Definition 5.4.1 (Candidate, viable function, conversion rank)

For a call $f(a_1, \dots, a_k)$, the candidate functions are the declarations that name lookup (plus ADL, below) finds for $f$. A candidate with parameters $p_1, \dots, p_m$ is viable if $m = k$ (ignoring default arguments and variadics) and for each $i$ there is an implicit conversion sequence $\mathrm{ICS}_i$ from the type of $a_i$ to the type of $p_i$. Each standard conversion sequence has a rank: $\mathsf{Exact} < \mathsf{Promotion} < \mathsf{Conversion}$ (smaller is better); a user-defined conversion ranks below every standard one, and an ellipsis match below that.

Definition 5.4.2 (Better viable function)

Viable $F$ is better than viable $G$, written $F \succ G$, if $\mathrm{ICS}_i(F)$ is not worse than $\mathrm{ICS}_i(G)$ for every argument $i$, and strictly better for at least one $i$. (C++ adds tie-breakers after this rule — non-template over template, more specialized template — which we omit.) The best viable function is the viable $F$ with $F \succ G$ for every other viable $G$; if no such $F$ exists the call is ambiguous, and if no candidate is viable it is unresolved.

Algorithm 5.4.3 (Best viable function: one tournament pass plus a verification pass)

Input: the viable functions $V = \langle F_1, \dots, F_r \rangle$ with their conversion ranks.
Output: the best viable function, or "ambiguous", or "no viable function".
Precondition: each per-argument comparison of conversion sequences is a strict weak order.
Postcondition: the returned $F$ satisfies Definition 5.4.2; "ambiguous" is returned only if no viable function beats all others.
Invariant: after examining $F_1, \dots, F_j$, if a best viable function exists among them it is $\mathit{best}$.

function BestViable(V):
    if V is empty: return no viable function
    best ← F1
    for j in 2..r:
        if Fj ≻ best: best ← Fj              # keep the winner of each comparison
    for G in V, G ≠ best:                     # verify: the winner must beat everyone
        if not (best ≻ G): return ambiguous
    return best

Argument-dependent lookup¶

Definition 5.4.4 (Associated namespaces and ADL)

For a type $T$, its associated namespaces $\mathrm{assoc}(T)$ are: for a fundamental type, none; for a class type, the innermost namespace enclosing the class (and those of its base classes and, for a class template specialization, of its template arguments); for a pointer or array type, those of the element type; for a function type, those of its parameter and return types. For an unqualified call $f(a_1, \dots, a_k)$, let $X$ be the result of ordinary unqualified lookup of $f$. If $X$ contains a class member, a block-scope function declaration, or something that is not a function, the candidate set is $X$. Otherwise it is $X \cup \bigcup_i \{\, \text{functions named } f \text{ declared in } N \mid N \in \mathrm{assoc}(\mathrm{type}(a_i)) \,\}$. A parenthesized callee (f)(…) is not an unqualified call, so ADL does not apply.

Algorithm 5.4.5 (Candidate set with ADL)

Input: an unqualified call $f(a_1, \dots, a_k)$, its scope, the argument types.
Output: the candidate set of Definition 5.4.4.
Precondition: ordinary lookup is available (Lessons 5.1–5.3).
Postcondition: the set is exactly Definition 5.4.4's.
Invariant: seen holds the namespaces already searched, so each is searched once.

function Candidates(f, args, scope):
    X ← OrdinaryLookup(f, scope)
    if the callee was parenthesized or X has a member / block-scope decl / non-function:
        return X
    seen ← ∅;  C ← X
    for a in args:
        for N in Assoc(type(a)):                   # Definition 5.4.4, recursively
            if N ∉ seen: seen ← seen ∪ {N};  C ← C ∪ FunctionsNamed(f, N)
    return C

Macro hygiene¶

Definition 5.4.6 (Syntax context and hygienic binding)

Every identifier occurrence carries a syntax context $c$: the empty context for text the user wrote, and for text introduced by a macro expansion, a fresh mark for that expansion step added to the context. A binding occurrence $(n, c_b)$ binds a use $(n, c_u)$ in its scope only if $c_u = c_b$ (for local variables; items and paths use more permissive rules). Expansion is hygienic if a use written by the user can never be bound by a binder introduced by a macro, and a use introduced by a macro can never be bound by a binder written by the user at the call site.

3. Worked example¶

Overload resolution¶

The declarations and calls of the Clang box in §7:

void f(int, double);   // F1
void f(double, int);   // F2
void f(long);          // F3
f(1, 2);  f(1.0, 2);  f('a');

call	candidate	viable?	$\mathrm{ICS}_1$	$\mathrm{ICS}_2$
`f(1, 2)`	F1	yes	int→int: Exact	int→double: Conversion
	F2	yes	int→double: Conversion	int→int: Exact
	F3	no (2 arguments, 1 parameter)
`f(1.0, 2)`	F1	yes	double→int: Conversion	int→double: Conversion
	F2	yes	double→double: Exact	int→int: Exact
`f('a')`	F3	yes	char→long: Conversion (an integral conversion, not a promotion: char promotes only to int)

Algorithm 5.4.3:

call	step	best	comparison	result
`f(1, 2)`	start	F1
	$j = 2$	F1	F2 ≻ F1? argument 1 worse (Conversion vs Exact): no	best stays F1
	verify	F1	F1 ≻ F2? argument 2 worse: no	ambiguous
`f(1.0, 2)`	start	F1
	$j = 2$	F2	F2 ≻ F1: both arguments strictly better	best ← F2
	verify	F2	F2 ≻ F1: yes	F2
`f('a')`	start	F3	only one viable	F3

Argument-dependent lookup¶

namespace geo { struct Point { int x, y; }; int norm1(Point p); }
int a(geo::Point p) { return norm1(p); }     // ADL
int b(geo::Point p) { return (norm1)(p); }   // no ADL

call	ordinary lookup $X$	ADL applies?	$\mathrm{assoc}(\texttt{geo::Point})$	candidates	result
`norm1(p)` in `a`	∅ (global scope has no `norm1`)	yes (unqualified, $X$ empty)	{geo}	{geo::norm1}	`geo::norm1`
`(norm1)(p)` in `b`	∅	no (parenthesized)	—	∅	error: undeclared `norm1` (Clang suggests `geo::norm1`, §7)

Macro hygiene¶

The Rust program of the §7 box: let tmp = 1; println!("{}", double!(tmp + 1)); with double!($e) => { let tmp = $e; tmp + tmp }.

identifier	written by	context	binds to
`tmp` in `let tmp = 1`	user	$c_0$	— (a binder)
`tmp` in the argument `tmp + 1`	user	$c_0$	the user's `let tmp = 1`
`tmp` in `let tmp = $e`	macro, expansion 1	$c_0 \cdot m_1$	— (a binder)
`tmp` in `tmp + tmp`	macro, expansion 1	$c_0 \cdot m_1$	the macro's `let tmp`

The argument tmp + 1 evaluates to 2 (its tmp has context $c_0$ and cannot see the macro's binder), and the macro doubles it: 4. The C preprocessor has no contexts, so its BUMP() in §7 increments whichever count is visible where it is pasted.

Try it

Change f('a') to f(1L) and f(1, 2) to f(1, 2.0) and predict Clang's answers with Algorithm 5.4.3 before compiling. No drill covers this lesson; the quiz items overload-ics-table and adl-candidates are computations of this kind.

4. Invariants and correctness¶

Overload resolution¶

Lemma 5.4.7 (Better is a strict partial order)

If each per-argument comparison of conversion sequences is a strict weak order, then $\succ$ of Definition 5.4.2 is irreflexive and transitive.

Proof

Irreflexive: $F \succ F$ would need an argument where $\mathrm{ICS}_i(F)$ is strictly better than itself. Transitive: let $F \succ G$ and $G \succ H$. For every $i$, $\mathrm{ICS}_i(F)$ is not worse than $\mathrm{ICS}_i(G)$, which is not worse than $\mathrm{ICS}_i(H)$; in a strict weak order "not worse" is transitive, so $\mathrm{ICS}_i(F)$ is not worse than $\mathrm{ICS}_i(H)$. At the argument $j$ where $F$ is strictly better than $G$: strictly better followed by not worse is strictly better (again by the weak order), so $F$ is strictly better than $H$ at $j$. Hence $F \succ H$.

Theorem 5.4.8 (The tournament finds the best viable function)

Algorithm 5.4.3 returns $F$ if and only if $F$ is the best viable function of Definition 5.4.2, and "ambiguous" if and only if viable functions exist but none is best.

Proof

Uniqueness first: if $F$ and $F'$ were both best, $F \succ F'$ and $F' \succ F$, so $F \succ F$ by transitivity, contradicting irreflexivity (Lemma 5.4.7). Loop invariant: suppose a best viable function $F^{*}$ exists among $F_1, \dots, F_j$. If $F^{*} = F_j$, then $F_j \succ \mathit{best}$ (it beats everything else), so the loop sets $\mathit{best} \leftarrow F_j$. If $F^{*}$ came earlier, by induction $\mathit{best} = F^{*}$ before step $j$, and $F_j \succ F^{*}$ is impossible (it would give $F^{*} \succ F^{*}$ by transitivity with $F^{*} \succ F_j$), so $\mathit{best}$ stays $F^{*}$. At the end, if a best function exists it is $\mathit{best}$, and the verification pass succeeds. Conversely, the verification pass returns $\mathit{best}$ only if it beats every other viable function, which is the definition of best. If none is best, verification fails for whatever $\mathit{best}$ is, and the result is "ambiguous".

Argument-dependent lookup¶

Proposition 5.4.9 (ADL only adds candidates, and only functions)

The candidate set of Algorithm 5.4.5 contains the ordinary lookup result $X$; every extra element is a function named $f$ declared in a namespace associated with some argument type; and ADL is not applied to parenthesized callees or when $X$ contains a member, a block-scope declaration or a non-function.

Proof

Read off the algorithm: $C$ starts as $X$ and only grows by FunctionsNamed(f, N) for $N \in \mathrm{Assoc}(\cdot)$; the early return covers the excluded cases. seen makes each namespace contribute once, so the loop terminates after at most $\sum_i \lvert \mathrm{assoc}(\mathrm{type}(a_i)) \rvert$ namespace lookups. Consequence for correctness arguments: a program that compiled without ADL (all calls resolved by $X$) can change meaning when ADL is enabled only if a new candidate from an associated namespace is better by Theorem 5.4.8 — which is exactly the "ADL hijacking" hazard that the parenthesized form turns off.

Macro hygiene¶

Theorem 5.4.10 (Context-keyed binding is hygienic)

If every expansion step adds a mark not used by any other step, and a binder binds a use only when their contexts are equal (Definition 5.4.6), then no user-written use is bound by a macro-introduced binder and no macro-introduced use is bound by a user-written binder at the use site.

Proof sketch (full proof and the lazy-mark algorithm: [KFFD86, §3]; [DHB92, §3]; Lesson 4.8, Theorem 4.8.10)

A user-written use has a context without the mark $m$ of the expansion step that introduced a macro binder, while that binder's context contains $m$; the contexts differ, so the binder does not bind the use. Symmetrically, a macro-introduced use carries $m$, and a user-written binder at the use site does not. Identifiers the macro receives as arguments are pasted unchanged, so they keep the user's context and bind as the user intended. Real systems relax "equal contexts" for items and paths (Rust's macro_rules! uses mixed-site hygiene: local variables and labels are hygienic, items resolve at the use site), which is why the theorem is stated for local bindings.

5. Complexity¶

Variables: $c$ candidates, $k$ arguments, $r \le c$ viable functions, $t$ the size of an argument type (number of nested types in it), $N$ the number of tokens produced by macro expansion.

Technique	Time	Space	Pathological input
Overload resolution	$O(c\, k)$ to build conversion sequences + $O(r\, k)$ for Algorithm 5.4.3	$O(c\, k)$	templates: each candidate needs deduction; Swift: operator overloads multiply across an expression (exponential in the worst case; Ch 7)
ADL	$O(\sum_i t_i)$ namespaces to collect + one lookup each	$O(\sum_i t_i)$	deeply nested template arguments (`vector<pair<A, map<B, C>>>`): every argument type's namespaces are associated
Hygiene	$O(N)$ with lazily propagated marks; $O(N \cdot d)$ with eager renaming at expansion depth $d$	a context per identifier	deeply nested macros with eager renaming

Justification. Algorithm 5.4.3 makes $r - 1$ comparisons in the loop and at most $r - 1$ in verification, each $O(k)$; the naive "compare all pairs" alternative is $O(r^2 k)$. Clang does the same one-pass-plus-verify (OverloadCandidateSet::BestViableFunction). ADL visits each associated namespace once thanks to seen. Hygiene costs are Lesson 4.8's.

Overload resolution¶

C++ tie-breakers: non-template beats template, more specialized template beats less, constraints (C++20 concepts) order candidates by subsumption.
Swift's solution ranking: the solver finds complete solutions (every overload in an expression chosen), then compares their scores (counts of non-default literals, value-to-optional conversions, fixes, …) and finally the declarations by "more specialized" [SWIFT-TypeChecker]; overloading is resolved jointly with type inference rather than per call.
Overloading without implicit conversions (Rust traits, Haskell type classes): the choice is made by the types exactly, so ranking disappears; ambiguity becomes "type annotations needed".

Argument-dependent lookup¶

Hidden friends: C++ functions declared only as friends inside a class are findable only by ADL, which keeps overload sets small (a standard library technique).
The two-step using std::swap; swap(a, b);: ordinary lookup finds std::swap, ADL adds the type's own swap, and overload resolution picks the more specific.
Languages without ADL resolve operators through the operand's type directly (Rust impl Add for T, Swift operators as static members): the same effect, no surprise candidates.

Macro hygiene¶

Marks and substitutions [DHB92] vs sets of scopes [Fla16] (Racket), vs rustc's mixed-site hygiene with $crate for paths (Lesson 4.8 §6).
Unhygienic by default with gensym (Common Lisp, Clojure's foo#): the macro author must request fresh names.

7. In real compilers¶

Overload resolution¶

Clang: OverloadCandidateSet::BestViableFunction and isBetterOverloadCandidate (clang/lib/Sema/SemaOverload.cpp, LLVM 23.1.2 [CLANG-SemaOverload]) implement Algorithm 5.4.3 and the C++ tie-breakers. GCC: joust compares two candidates and build_new_function_call drives the tournament (gcc/cp/call.cc, gcc-15 [GCC-CPCall]). Swift: compareSolutions ranks complete solutions (lib/Sema/CSRanking.cpp, swift-6.1-RELEASE [SWIFT-CSRanking]); swiftc is not available in this container, so the Swift side is covered by the source pointer and [SWIFT-TypeChecker].

Clang 23's ambiguous-call diagnostic lists the tied candidates

Reproduce (clang 23.1.2):

cat > overload.cpp <<'EOF'
void f(int, double);
void f(double, int);
void f(long);
void g() {
  f(1, 2);      // both two-argument candidates need one conversion: ambiguous
  f(1.0, 2);    // f(double, int) is an exact match
  f('a');       // f(long): integral conversion
}
EOF
clang++-23 -fsyntax-only overload.cpp

Output (complete):

overload.cpp:5:3: error: call to 'f' is ambiguous
    5 |   f(1, 2);      // both two-argument candidates need one conversion: ambiguous
      |   ^
overload.cpp:1:6: note: candidate function
    1 | void f(int, double);
      |      ^
overload.cpp:2:6: note: candidate function
    2 | void f(double, int);
      |      ^
1 error generated.

What to notice: exactly the verdicts of the §3 table: f(1, 2) is ambiguous between F1 and F2 (each is better on one argument), the other two calls resolve silently. The notes list only the viable candidates that tied — F3 was not viable (Definition 5.4.1).

Argument-dependent lookup¶

Clang: Sema::ArgumentDependentLookup and the computation of associated namespaces and classes (clang/lib/Sema/SemaLookup.cpp, LLVM 23.1.2 [CLANG-SemaLookup]). GCC: lookup_arg_dependent (gcc/cp/name-lookup.cc, gcc-15 [GCC-NameLookup]).

ADL finds geo::norm1; parentheses switch it off (Clang 23)

Reproduce (clang 23.1.2):

cat > adl.cpp <<'EOF'
namespace geo {
  struct Point { int x, y; };
  int norm1(Point p) { return (p.x < 0 ? -p.x : p.x) + (p.y < 0 ? -p.y : p.y); }
}
int a(geo::Point p) { return norm1(p); }     // found by argument-dependent lookup
int b(geo::Point p) { return (norm1)(p); }   // parentheses suppress ADL
EOF
clang++-23 -fsyntax-only adl.cpp

Output (complete):

adl.cpp:6:31: error: use of undeclared identifier 'norm1'; did you mean 'geo::norm1'?
    6 | int b(geo::Point p) { return (norm1)(p); }   // parentheses suppress ADL
      |                               ^~~~~
      |                               geo::norm1
adl.cpp:3:7: note: 'geo::norm1' declared here
    3 |   int norm1(Point p) { return (p.x < 0 ? -p.x : p.x) + (p.y < 0 ? -p.y : p.y); }
      |       ^
1 error generated.

What to notice: line 5 compiles although no norm1 is visible there — ADL added geo::norm1 from the namespace associated with geo::Point (Definition 5.4.4). Line 6 is the same call with a parenthesized callee, so only ordinary lookup runs and fails; Clang's typo correction (Lesson 5.8) then searches other namespaces and suggests the qualified name.

Macro hygiene¶

rustc: every span carries a SyntaxContext (compiler/rustc_span/src/hygiene.rs [RUSTC-Hygiene]), macro_rules! expansion creates fresh marks in compiler/rustc_expand/src/mbe/transcribe.rs [RUSTC-MBE], and local-variable resolution compares identifiers by name and context. Clang's preprocessor has no contexts (clang/lib/Lex): Lesson 4.8 traces its expansion.

Hygienic macro_rules! in rustc 1.94 vs capture in the C preprocessor (Clang 23)

Reproduce (rustc 1.94.1, clang 23.1.2):

cat > hyg.rs <<'EOF'
macro_rules! double {
    ($e:expr) => {{ let tmp = $e; tmp + tmp }};
}
macro_rules! set_tmp {
    () => { let tmp = 100; };
}
fn main() {
    let tmp = 1;
    println!("{}", double!(tmp + 1));  // the macro's tmp does not capture ours
    set_tmp!();
    println!("{}", tmp);               // still 1: the macro's `let tmp` is invisible here
}
EOF
rustc --edition 2021 -A unused_variables hyg.rs -o hyg && ./hyg
cat > hyg.c <<'EOF'
#include <stdio.h>
int count = 0;                       /* the macro's author means this one */
#define BUMP() (count++)
int f(void) { int count = 10; BUMP(); return count; }
int main(void) { int r = f(); printf("f() = %d, global count = %d\n", r, count); }
EOF
clang-23 -E -P hyg.c | tail -2
clang-23 hyg.c -o hygc && ./hygc

Output (complete; the Rust program, the preprocessed tail, the C program):

4
1
int f(void) { int count = 10; (count++); return count; }
int main(void) { int r = f(); printf("f() = %d, global count = %d\n", r, count); }
f() = 11, global count = 0

What to notice: Rust prints 4 (the argument's tmp is the user's, context $c_0$) and then 1 (the macro's let tmp = 100 has context $c_0 \cdot m$ and cannot bind the user's later tmp): Theorem 5.4.10 in both directions. In C, BUMP() is pasted as tokens and its count resolves in f's scope to the local, so the global the author meant is never incremented — capture by the use site.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Overload resolution	One name, many functions, chosen by argument types; unique best or an ambiguity error (Theorem 5.4.8)	$O(c\,k)$ per call · templates and Swift's joint solving can be expensive	Ambiguity errors list the tied candidates; "no viable function" lists why each failed	High (conversion ranking, templates, tie-breakers)	C++, Swift, Java, C#, Ada
Argument-dependent lookup	Adds functions from the arguments' namespaces (Proposition 5.4.9); makes operators and customization points work	$O(\sum t_i)$ namespace lookups per unqualified call	Surprising candidates ("ADL hijacking"); errors mention functions the reader cannot see nearby	Medium	C++ only (other languages attach operators to types)
Macro hygiene	Binding by (name, context): no accidental capture (Theorem 5.4.10)	$O(N)$ with lazy marks	Errors point into expansions with a backtrace	Medium–high (contexts on every identifier)	Rust, Scheme, Racket; not C or C++

Choose overloading when the language has implicit conversions or many numeric types and you accept a ranking specification; choose trait- or type-class-based dispatch when you want exact matching and inference instead. Choose ADL only in a language with free-function operators and namespaces (C++); newer designs attach operations to types. Choose hygiene for any macro system that manipulates code rather than text.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Overload resolution	`overload-ics-table`, `find-clang-bestviable`	— (the §3 table format; quiz computations)	`overload-resolution`	—
Argument-dependent lookup	`adl-candidates`, `adl-parens`	—	`adl`	—
Macro hygiene	`hygiene-contexts-rust`, `cpp-capture`	— (Lesson 4.8's quiz items too)	`hygiene`	—

Pebble has no overloading, namespaces or macros, so no exercise implements this lesson; its outcomes are checked by the quiz and the flashcards, and the runs above are reproducible.

References¶

See the chapter references.

call	step	best	comparison	result
`f(1, 2)`	start	F1
	\(j = 2\)	F1	F2 ≻ F1? argument 1 worse (Conversion vs Exact): no	best stays F1
	verify	F1	F1 ≻ F2? argument 2 worse: no	ambiguous
`f(1.0, 2)`	start	F1
	\(j = 2\)	F2	F2 ≻ F1: both arguments strictly better	best ← F2
	verify	F2	F2 ≻ F1: yes	F2
`f('a')`	start	F3	only one viable	F3

call	ordinary lookup \(X\)	ADL applies?	\(\mathrm{assoc}(\texttt{geo::Point})\)	candidates	result
`norm1(p)` in `a`	∅ (global scope has no `norm1`)	yes (unqualified, \(X\) empty)	{geo}	{geo::norm1}	`geo::norm1`
`(norm1)(p)` in `b`	∅	no (parenthesized)	—	∅	error: undeclared `norm1` (Clang suggests `geo::norm1`, §7)

identifier	written by	context	binds to
`tmp` in `let tmp = 1`	user	\(c_0\)	— (a binder)
`tmp` in the argument `tmp + 1`	user	\(c_0\)	the user's `let tmp = 1`
`tmp` in `let tmp = $e`	macro, expansion 1	\(c_0 \cdot m_1\)	— (a binder)
`tmp` in `tmp + tmp`	macro, expansion 1	\(c_0 \cdot m_1\)	the macro's `let tmp`

Technique	Time	Space	Pathological input
Overload resolution	\(O(c\, k)\) to build conversion sequences + \(O(r\, k)\) for Algorithm 5.4.3	\(O(c\, k)\)	templates: each candidate needs deduction; Swift: operator overloads multiply across an expression (exponential in the worst case; Ch 7)
ADL	\(O(\sum_i t_i)\) namespaces to collect + one lookup each	\(O(\sum_i t_i)\)	deeply nested template arguments (`vector<pair<A, map<B, C>>>`): every argument type's namespaces are associated
Hygiene	\(O(N)\) with lazily propagated marks; \(O(N \cdot d)\) with eager renaming at expansion depth \(d\)	a context per identifier	deeply nested macros with eager renaming

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Overload resolution	One name, many functions, chosen by argument types; unique best or an ambiguity error (Theorem 5.4.8)	\(O(c\,k)\) per call · templates and Swift's joint solving can be expensive	Ambiguity errors list the tied candidates; "no viable function" lists why each failed	High (conversion ranking, templates, tie-breakers)	C++, Swift, Java, C#, Ada
Argument-dependent lookup	Adds functions from the arguments' namespaces (Proposition 5.4.9); makes operators and customization points work	\(O(\sum t_i)\) namespace lookups per unqualified call	Surprising candidates ("ADL hijacking"); errors mention functions the reader cannot see nearby	Medium	C++ only (other languages attach operators to types)
Macro hygiene	Binding by (name, context): no accidental capture (Theorem 5.4.10)	\(O(N)\) with lazy marks	Errors point into expansions with a backtrace	Medium–high (contexts on every identifier)	Rust, Scheme, Racket; not C or C++

Lesson 5.4 — When a name denotes several things: overload resolution, argument-dependent lookup and macro hygiene¶

1. Problem and motivation¶

Overload resolution¶

Argument-dependent lookup¶

Macro hygiene¶

2. Definitions and algorithms¶

Overload resolution¶

Argument-dependent lookup¶

Macro hygiene¶

3. Worked example¶

Overload resolution¶

Argument-dependent lookup¶

Macro hygiene¶

4. Invariants and correctness¶

Overload resolution¶

Argument-dependent lookup¶

Macro hygiene¶

5. Complexity¶

6. Variants and refinements¶

Overload resolution¶

Argument-dependent lookup¶

Macro hygiene¶

7. In real compilers¶

Overload resolution¶

Argument-dependent lookup¶

Macro hygiene¶

8. Comparison¶

9. Assessment¶

References¶