External linker arguments should be topologically ordered

[lifthrasiir]

Simple example:

// a.rs
#[crate_type="lib"];
#[link(name="aaa")] extern {}

// b.rs
#[crate_type="lib"];
extern mod a;
#[link(name="bbb")] extern {}

// c.rs
extern mod a; // not really relevant to this issue, does not change the behavior here
extern mod b;
fn main() {}

When compiled with rustc a.rs && rustc -L. b.rs && rustc -L. c.rs, this obviously results in the linker error, but multiple trials reveal the random order of -laaa and -lbbb. If libbbb.a depends on libaaa.a then -laaa should be put before -lbbb; the current behavior is not acceptable for the purpose of FFI.

Some practical problem caused by this issue: If the external library (say, -lsqlite3) depends on libc (-lc) and the binding crate for that library is compiled as rlib, then the executable crate using those library and crate will randomly fail to link since we no longer implicitly link to -lc (#12205) and thus the order of -lc and -lsqlite3 is random. (We do still have -lc since libstd depends on libc.)

[brson]

Nominating.

[emberian]

cc @alexcrichton

[alexcrichton]

I have worried about this in the past, and right now we use a HashSet for de-duping which explains the random orderings. I agree that we should do this in a much more structured manner.

[alexcrichton]

Hm, I'm actually not sure that there is a bug here, but I'm not quite sure why. When passing libraries to the linker, we currently pass this ordering of arguments (left to right on the command line):

• the LLVM-generated object file
• the local crate's native libraries. Note that these are inserted in a first seen order, so there is a defined ordering that you can control.
• upstream rust crates. The order of these crates is nondeterministic
• upstream native dependencies. Across crates the ordering is deterministic, but within a crate it's the same ordering as native libraries

This means that if you have a native library like sqlite3 which depends on libc then you do this:

#[link(name = "sqlite3")] // shows up first on the command line
#[link(name = "c")] // shows up next
extern {}

With this, everything is ok. What I don't understand is how a nondeterministic ordering of upstream crates doesn't cause problems. For example, I have this setup:

// a.c
void a() {}

// b.c
extern void a();
void b() { a(); }

// c.c
extern void b();
int main() { b(); }

When compiled, it yields problems:

$ gcc  -L. c.o -la -lb
./libb.a(b.o): In function `b':
b.c:(.text+0xa): undefined reference to `a'
collect2: error: ld returned 1 exit status

Naturally, libb depends on liba, but is mentioned in the wrong order on the command line. Now let's switch the situation to rust and see what happens

// a.rs
fn foo() {}

// b.rs
extern mod a;
fn foo() { a::foo(); }

// c.rs
extern mod a;
extern mod b;
fn main() { b::foo(); }

Now when we compile, we get no errors!

$ rustc -L. c.rs -Z print-link-args                       
cc link args: '-m64' '-L/usr/lib/rustlib/x86_64-unknown-linux-gnu/lib' '-o' 'c' 'c.o' '-Wl,--as-needed' '-L.' '-L/home/alex/test/.rust' '-L/home/alex/test' '/usr/lib/rustlib/x86_64-unknown-linux-gnu/lib/libstd-966edb7e-0.10-pre.rlib' '/usr/lib/rustlib/x86_64-unknown-linux-gnu/lib/libgreen-80d9e76a-0.10-pre.rlib' '/usr/lib/rustlib/x86_64-unknown-linux-gnu/lib/librustuv-09e0b925-0.10-pre.rlib' 'liba-ca3f740d-0.0.rlib' 'libb-920859ee-0.0.rlib' '-ldl' '-lm' '-lpthread' '-lpthread' '-lrt' '-lmorestack' '-Wl,-rpath,$ORIGIN/../../../usr/lib/rustlib/x86_64-unknown-linux-gnu/lib' '-Wl,-rpath,/usr/lib/rustlib/x86_64-unknown-linux-gnu/lib'

Notice how liba-*.rlib is mentioned before libb-*.rlib, yet libb depends on liba for a symbol. This seems to me to be the same situation as with C, but this appears to successfully compile.

All-in-all it looks like there is actually no bug today, although I don't understand why there isn't a bug?

[vadimcn]

Related to #11124?

[pnkfelix]

"This is just a bug." Assigning P-low, not assigning to 1.0 milestone.

[alexcrichton]

I forgot to close this at the time, but this is closed by 17ad504