Symbol resolution — order matters: Worked examples

Quick reminder of the three sets, because every trace below uses them:

Recall The three sets (from the parent)

$E$ ::: the set of object files that will go into the final executable. $U$ ::: the set of symbols used but not yet defined — "still needed." $D$ ::: the set of symbols already defined by something in $E$ . The linker's goal ::: make $U$ empty by the time the command line ends.

The scenario matrix

Think of the "inputs" to symbol resolution as a few independent knobs. Every real link is one combination of these knobs. The table below lists the knob-settings ("cells") that behave differently — those are exactly the cases we must cover so you never meet an unshown scenario.

Cell	Situation	Does it link?	Example
A	Object needs a symbol, provider library is after it	✅ works	Ex 1
B	Same symbols, library placed before the object (wrong order)	❌ fails	Ex 2
C	Library present but symbol never referenced (member dropped)	✅ links, but code silently absent	Ex 3
D	Circular dependency between two static archives	❌ / needs group	Ex 4
E	Two strong definitions of the same symbol	❌ multiple definition	Ex 5
F	One strong + one weak definition	✅ strong wins silently	Ex 6
G	Symbol has no definition anywhere (degenerate / empty provider)	❌ undefined reference	Ex 7
H	Shared library (`.so`) with `--as-needed`, listed before its user	❌ dropped	Ex 8
I	Real-world word problem: multi-library app, find the correct order	✅ once ordered	Ex 9
J	Exam twist: three libraries, transitive chain, predict success/failure	⚠️ predict	Ex 10

The two "knobs" that create all this variety are (1) position of a provider relative to its user, and (2) definition count (0, 1 weak, 1 strong, 2 strong, 1 strong + weak). The figure below is the mental model — a one-way hallway — that every cell is a variation of.

Look at the red arrow: it only moves rightward. A locker (archive) behind the arrow can never be revisited. That single fact generates cells A–J.

Cell A — provider after user (the correct order)

Worked example Example 1 —

main.o then -lm

$ gcc main.o -lm

main.o calls sqrt; -lm is the archive libm.a containing sqrt.o.

Forecast: before reading on, guess — does this link? Which member gets pulled?

Read main.o. What: add it to $E$ ; it defines main, references sqrt. Why this step? every object on the line is unconditionally included, and we record what it still needs. Result: $E = {main}$ , $D = {main}$ , $U = {s q r t}$ .
Read libm.a. What: scan its members; sqrt.o defines sqrt, which is in $U$ , so pull it in. Why this step? an archive only donates members that satisfy a current undefined — and sqrt is undefined right now. Result: $E = {main, s q r t}$ , $U = \emptyset$ , $D = {main, s q r t}$ .
End of line: $U = \emptyset$ . Why this step? the terminating check: empty $U$ ⇒ success.

Verify: $U$ ended empty ⇒ links. Sanity: sqrt was demanded before the linker met libm, matching the rule "user before provider." ✅

Cell B — provider before user (the classic failure)

Worked example Example 2 —

-lm then main.o

$ gcc -lm main.o

Forecast: guess the error before tracing.

Read libm.a first. What: $U$ is empty, so no member matches anything undefined. Why this step? the archive is searched only against the $U$ that exists now, and now it's empty. Nothing is pulled. $E = \emptyset$ , $U = \emptyset$ .
Read main.o. What: add to $E$ , references sqrt → $U = {s q r t}$ . Why this step? now we finally learn sqrt is needed — but libm is already behind the one-way arrow.
End of line: $U = {s q r t} \neq = \emptyset$ . Why this step? non-empty $U$ ⇒ error.

Verify: the linker prints undefined reference to 'sqrt'. The only difference from Ex 1 is position — that is the whole lesson. ❌

Cell C — symbol never referenced (member silently dropped)

Worked example Example 3 — a constructor that never runs

$ ar rcs libutil.a a.o b.o     # b.o defines log_init() with __attribute__((constructor))
$ gcc main.o -lutil            # main never calls log_init

Forecast: does the program compile? Does log_init run?

Read main.o → $U$ = whatever main needs (say helper, defined in a.o). Why: record demands.
Read libutil.a. a.o defines helper ∈ $U$ → pulled. b.o defines only log_init, which is not in $U$ → not pulled. Why this step? archives pull only on-demand members.
End: $U = \emptyset$ ⇒ links fine. But b.o's constructor is not in the executable.

Verify: program runs but log_init never executes — a silent logic bug, not a link error. Fix: -Wl,--whole-archive -lutil -Wl,--no-whole-archive forces every member in, or link b.o directly. See Library Constructors and __attribute__((constructor)).

Cell D — circular static libraries

Worked example Example 4 —

libfoo.a ↔ libbar.a

$ gcc main.o -lfoo -lbar       # may fail

main uses foo_a (in libfoo); foo_a calls bar_x (in libbar); bar_x calls back foo_b (also in libfoo, in a different member).

Forecast: predict whether one left-to-right pass succeeds.

main.o: $U = {f oo_a}$ .
-lfoo: pulls the member defining foo_a; that member references bar_x → $U = {ba r_x}$ . Why: its own undefineds join $U$ .
-lbar: pulls the member defining bar_x; that member references foo_b → $U = {f oo_b}$ . Why: newly undefined. But libfoo is already behind the arrow.
End: $U = {f oo_b}$ ⇒ ❌ undefined reference to 'foo_b'.

Fix A — repeat: gcc main.o -lfoo -lbar -lfoo (the second -lfoo is met after foo_b becomes undefined). Fix B — group:

$ gcc main.o -Wl,--start-group -lfoo -lbar -Wl,--end-group

Why this step? --start-group re-scans the enclosed archives repeatedly until a full pass adds nothing — deliberately defeating the one-pass rule.

Verify: with the group, pass 1 leaves $U = {f oo_b}$ ; pass 2 re-enters libfoo, satisfies foo_b; pass 3 adds nothing → stop, $U = \emptyset$ . ✅

Cell E & F — definition count (two strong vs strong+weak)

Worked example Example 5 (Cell E) — two strong definitions

// a.c
int count = 1;   // strong (initialised)
// b.c
int count = 2;   // strong (initialised)

$ gcc a.o b.o

Forecast: link or error?

Read a.o: defines count (strong) → $D = {co u n t}$ .
Read b.o: also defines count strong, already in $D$ . Why this step? two strong definitions of one symbol are irreconcilable.
Result: ❌ multiple definition of 'count'.

Verify: the count of strong definitions is $2$ , and $2 > 1$ ⇒ error. Fix: declare extern int count; in a header, define once.

Worked example Example 6 (Cell F) — one strong + one weak

// a.c
int count = 1;   // strong
// b.c
int count;       // tentative → weak (pre -fno-common)

Forecast: which value survives?

a.o defines count strong.
b.o defines count weak → strong overrides weak, silently.
Result: ✅ links; count == 1.

Verify: strong-count $= 1$ , weak-count $= 1$ ; rule "1 strong wins" ⇒ links with value $1$ . Gotcha: -fno-common turns the tentative int count; into a strong symbol too, converting this into Cell E (error) — a common surprise on modern compilers.

Cell G — no definition anywhere (degenerate)

Worked example Example 7 — the empty-provider / typo case

$ gcc main.o -lfoo       # main calls compute(); libfoo has no compute

Forecast: guess the diagnostic.

main.o: $U = {co m p u t e}$ .
-lfoo: no member defines compute → nothing pulled. $U = {co m p u t e}$ .
No further inputs. End: $U \neq = \emptyset$ ⇒ ❌ undefined reference to 'compute'.

Verify: this is the zero-definition degenerate case — position cannot help; the symbol simply does not exist (missing library, typo, or C++ name mangling mismatch where you forgot extern "C"). Distinguish from Cell B: here reordering won't fix it.

Cell H — shared library, `--as-needed`, wrong order

Worked example Example 8 —

.so order still matters

$ gcc -Wl,--as-needed -lm main.o

Even shared libraries record dependencies in scan order.

Forecast: does --as-needed save the wrong order?

--as-needed tells ld: only add a .so to the executable's dependency list if it satisfies a currently undefined symbol.
At -lm, $U = \emptyset$ ⇒ libm.so is judged not needed and dropped.
main.o then makes sqrt undefined → ❌ undefined reference to 'sqrt' (or a load-time failure without --as-needed).

Verify: same failure shape as Cell B, but for .so. See Static vs Shared Libraries. Rule holds for both: users before providers.

Cell I — real-world word problem

Worked example Example 9 — build a plotting app

Your app: plot.o calls into your libgraph.a; libgraph.a uses sin/cos from libm.a; nothing uses libm directly. Someone wrote:

$ gcc -lm -lgraph plot.o        # what's wrong, and give the correct line

Forecast: list every mis-ordered token before reading.

Object plot.o is last — it should be first (it is the top-level user). Currently when -lm and -lgraph are scanned, $U = \emptyset$ ⇒ both dropped.
libgraph uses libm, so libgraph must come before libm (user before provider).
Correct line:

$ gcc plot.o -lgraph -lm

Why this order? plot.o first makes graph_* undefined; -lgraph supplies them and in turn makes sin/cos undefined; -lm (last) supplies those.

Verify: trace — $U$ goes ${g r a p h} \to {s in, cos} \to \emptyset$ . Empty at end ⇒ ✅. This is the canonical "objects first, dependency chain in use-order" pattern from Build Systems & Toolchain.

Cell J — exam twist (predict first)

Worked example Example 10 — three-library chain

Given: main.o uses A; libA.a uses B; libB.a uses C; libC.a uses nothing back. Two candidate lines — predict pass/fail for each:

(i)  gcc main.o -lA -lB -lC
(ii) gcc main.o -lC -lB -lA

Forecast: decide before tracing.

Line (i): $U : {A} \to {B} \to {C} \to \emptyset$ . Each provider sits after its user ⇒ ✅.
Line (ii): -lC first with $U = \emptyset$ ⇒ dropped. -lB with $U = \emptyset$ ⇒ dropped. -lA supplies A, leaves $U = {B}$ . End: $U = {B}$ ⇒ ❌.

Verify: (i) empties $U$ (✅); (ii) leaves undefined reference to 'B' (and to C). The chain must be written in dependency order, users first. A single group would also rescue (ii): -Wl,--start-group -lA -lB -lC -Wl,--end-group.

Connections

Symbol resolution — order matters (parent)
Static vs Shared Libraries
The Linker (ld) and Linking Phases
Object File Format (ELF) and Symbol Tables
Name Mangling in C++
Library Constructors and __attribute__((constructor))
Build Systems & Toolchain