Symbol resolution — order matters: Visual walkthrough

This is the visual companion to the parent topic. Read it slowly; each figure carries the argument.

Step 0 — The vocabulary, anchored to a picture

Before any algorithm, we must agree on what the stuff is. A compiler turns each .c source file into one object file (ending .o). Think of an object file as a small box. Written on the outside of the box are two lists:

Defines: the names of functions/variables that live inside this box. ("I HAVE these.")
Undefined: the names this box uses but does not contain. ("I NEED these — someone else must supply them.")

Figure — Symbol resolution — order matters

Look at the figure. Box main.o defines main (green tag on the right) but leaves sqrt undefined (red tag on the left). It cannot run yet — a box with a dangling red tag is a broken program. The whole game is: turn every red tag green.

An archive (.a file, also written -lfoo on the command line) is different — it is not one box, it is a crate of boxes with an index sheet on top saying which box defines which symbol. The crate is lazy: it only hands you a box if you ask for something that box provides.

Step 1 — The linker walks the line once, left to right

WHAT we set up: the linker keeps a small notepad with three columns as it walks.

WHY three sets and not one: we need to remember what we still owe ( $U$ ), what we can already pay ( $D$ ), and what we're carrying ( $E$ ). Each new file on the line updates all three. The letter $U$ is the star of the show — a program links successfully exactly when $U$ is empty at the end.

WHAT IT LOOKS LIKE: the figure shows the hallway. The linker (yellow arrow) starts at the far left, walks right, and can never step backward. Whatever is behind the arrow is sealed — the linker will not reconsider it. Keep that sealing image; it is the source of every surprise.

Step 2 — Processing one object box (the update rule)

WHAT we do: when the walking linker reaches an object box f, it does three things in order.

WHY this exact order: a box can both supply an old need and create a new one. We first cross off what it pays, then write down what it now owes. The $∖ D$ guard stops us from re-adding a symbol that some earlier box already satisfied.

WHAT IT LOOKS LIKE: watch the notepad change. Before util.o: $U = {h e l p er}$ . util.o defines helper (crosses it off $U$ ) and references printf (adds it to $U$ ). After: $U = {p r in t f}$ . The "owed" list changed shape but is not yet empty.

Step 3 — Processing an archive crate (the lazy rule)

Here is where order becomes meaning. An archive is scanned completely differently from an object.

WHY the intersection with $U$ , not with everything: the crate is lazy. It refuses to hand you a box unless you have already asked — unless a red tag is presently on your notepad. This one clause is the entire reason order matters.

WHAT IT LOOKS LIKE: two members sqrt.o and cos.o sit in the crate libm.a. The notepad says $U = {s q r t}$ . The linker compares: sqrt.o provides sqrt — that's in $U$ → pull it (blue arrow). cos.o provides cos — not in $U$ → left behind (greyed out). The crate is picked over, not emptied.

Step 4 — The classic success: object before library

Now we run the machine on the famous case. Command line: main.o -lm, where main.o calls sqrt.

WHAT happens, step by step:

Reach main.o → into $E$ . Defines main, references sqrt. Notepad: $U = {s q r t}$ , $D = {main}$ .
Reach libm.a → compare its members to $U$ . Member sqrt.o provides sqrt ∈ $U$ → pull it. Now $U = \emptyset$ . ✅

WHY it works: the red tag sqrt already existed on the notepad at the moment the linker reached the crate. The crate's lazy rule was satisfied.

WHAT IT LOOKS LIKE: the timeline. When the arrow crosses libm.a, the "owed" box already shows sqrt in red — so the crate hands it over and the box turns empty (green). Program links.

Step 5 — The classic failure: library before object

Same files, flipped: -lm main.o. Nothing else changed. Watch it break.

WHAT happens:

Reach libm.a first → compare its members to $U$ . But $U = \emptyset$ — no red tags exist yet! So no member is pulled. The crate is now behind the arrow, sealed.
Reach main.o → references sqrt → $U = {s q r t}$ .
End of line. $U = {s q r t} \neq = \emptyset$ → error: undefined reference to 'sqrt'.

WHY it fails: at the crate, the notepad was blank, so the lazy rule refused to hand over sqrt.o. By the time main.o created the need, the crate was already sealed behind the never-reversing arrow (recall Step 1's sealing image).

WHAT IT LOOKS LIKE: the arrow passes libm.a while the "owed" box is empty — the crate is skipped and greyed. Then main.o lights up a red sqrt tag with no crate left ahead to satisfy it. Dead end.

Step 6 — Degenerate & edge cases (every scenario shown)

A good derivation covers all inputs. Four corners the machine can hit:

(a) Empty need at end — success by exhaustion. If, after the last file, $U = \emptyset$ , done — no error even if some archive members were never used. Leftover unused members are simply dropped.

(b) Circular libraries. libfoo.a needs libbar.a, and libbar.a needs libfoo.a back. Writing -lfoo -lbar: scanning bar pulls a member needing a new foo symbol — but foo is already sealed behind us. $U$ ends non-empty → error. Fix: repeat (-lfoo -lbar -lfoo) or force re-scanning with -Wl,--start-group -lfoo -lbar -Wl,--end-group, which tells the linker to loop over the enclosed crates until a full pass adds nothing.

(c) An unreferenced member with side effects. A member b.o holds a constructor but defines no symbol anyone references. Since $defines (b) \cap U = \emptyset$ always, it's never pulled — the constructor silently never runs. Fix: -Wl,--whole-archive -lutil -Wl,--no-whole-archive forces every member in, ignoring the lazy rule.

(d) Two strong definitions of the same symbol. If two object boxes both define count as a real (strong) definition, $D$ receives it twice → multiple definition error. One strong + many weak → strong wins silently. This is unrelated to order — it's a $D$ -collision, not a $U$ -miss.

WHAT IT LOOKS LIKE: the figure lays the four corners side by side — green (success), red-loop (circular), grey-ghost (dropped constructor), and double-red (multiple definition) — so you can recognise which corner you're in from the error message alone.

Recall Which corner produces

undefined reference? A symbol left in $U$ at the very end — corners (b) and the Step 5 ordering bug. ::: A non-empty $U$ at end-of-line. Which corner produces multiple definition? ::: Two strong definitions colliding in $D$ — corner (d).

The one-picture summary

One frame, whole derivation: the hallway (arrow moving right, sealing behind it), the notepad with $E$ , $U$ , $D$ , the two update rules (unconditional object, lazy archive $\cap U$ ), and the verdict box — $U = \emptyset$ ⇒ link, else undefined reference. The green path (main.o -lm) satisfies sqrt on time; the red path (-lm main.o) seals the crate before the need exists.

Recall Feynman: retell the whole walkthrough in plain words

A worker walks down a hallway of lockers, one direction, never turning back, carrying a notepad of "things people still need." Plain lockers (object files) always get emptied into his cart and he crosses off what they supply while writing down anything they now need. Vending crates (archives) are stingy — they hand over an item only if it's already written on the notepad right now; otherwise they let him pass and he can never come back. So if the person who needs a pen comes after the pen crate, the crate was skipped and the pen is lost forever — that's your undefined reference. Put the askers before the givers, and the notepad empties out. When the notepad is empty at the end of the hall, the program is whole.

Connections

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