1 //! Resolution of mixing rlibs and dylibs
3 //! When producing a final artifact, such as a dynamic library, the compiler has
4 //! a choice between linking an rlib or linking a dylib of all upstream
5 //! dependencies. The linking phase must guarantee, however, that a library only
6 //! show up once in the object file. For example, it is illegal for library A to
7 //! be statically linked to B and C in separate dylibs, and then link B and C
8 //! into a crate D (because library A appears twice).
10 //! The job of this module is to calculate what format each upstream crate
11 //! should be used when linking each output type requested in this session. This
12 //! generally follows this set of rules:
14 //! 1. Each library must appear exactly once in the output.
15 //! 2. Each rlib contains only one library (it's just an object file)
16 //! 3. Each dylib can contain more than one library (due to static linking),
17 //! and can also bring in many dynamic dependencies.
19 //! With these constraints in mind, it's generally a very difficult problem to
20 //! find a solution that's not "all rlibs" or "all dylibs". I have suspicions
21 //! that NP-ness may come into the picture here...
23 //! The current selection algorithm below looks mostly similar to:
25 //! 1. If static linking is required, then require all upstream dependencies
26 //! to be available as rlibs. If not, generate an error.
27 //! 2. If static linking is requested (generating an executable), then
28 //! attempt to use all upstream dependencies as rlibs. If any are not
29 //! found, bail out and continue to step 3.
30 //! 3. Static linking has failed, at least one library must be dynamically
31 //! linked. Apply a heuristic by greedily maximizing the number of
32 //! dynamically linked libraries.
33 //! 4. Each upstream dependency available as a dynamic library is
34 //! registered. The dependencies all propagate, adding to a map. It is
35 //! possible for a dylib to add a static library as a dependency, but it
36 //! is illegal for two dylibs to add the same static library as a
37 //! dependency. The same dylib can be added twice. Additionally, it is
38 //! illegal to add a static dependency when it was previously found as a
39 //! dylib (and vice versa)
40 //! 5. After all dynamic dependencies have been traversed, re-traverse the
41 //! remaining dependencies and add them statically (if they haven't been
44 //! While not perfect, this algorithm should help support use-cases such as leaf
45 //! dependencies being static while the larger tree of inner dependencies are
46 //! all dynamic. This isn't currently very well battle tested, so it will likely
47 //! fall short in some use cases.
49 //! Currently, there is no way to specify the preference of linkage with a
50 //! particular library (other than a global dynamic/static switch).
51 //! Additionally, the algorithm is geared towards finding *any* solution rather
52 //! than finding a number of solutions (there are normally quite a few).
54 use crate::creader
::CStore
;
56 use rustc_data_structures
::fx
::FxHashMap
;
57 use rustc_hir
::def_id
::CrateNum
;
58 use rustc_middle
::middle
::cstore
::CrateDepKind
;
59 use rustc_middle
::middle
::cstore
::LinkagePreference
::{self, RequireDynamic, RequireStatic}
;
60 use rustc_middle
::middle
::dependency_format
::{Dependencies, DependencyList, Linkage}
;
61 use rustc_middle
::ty
::TyCtxt
;
62 use rustc_session
::config
::CrateType
;
63 use rustc_target
::spec
::PanicStrategy
;
65 crate fn calculate(tcx
: TyCtxt
<'_
>) -> Dependencies
{
70 let linkage
= calculate_type(tcx
, ty
);
71 verify_ok(tcx
, &linkage
);
77 fn calculate_type(tcx
: TyCtxt
<'_
>, ty
: CrateType
) -> DependencyList
{
80 if !sess
.opts
.output_types
.should_codegen() {
84 let preferred_linkage
= match ty
{
85 // Generating a dylib without `-C prefer-dynamic` means that we're going
86 // to try to eagerly statically link all dependencies. This is normally
87 // done for end-product dylibs, not intermediate products.
89 // Treat cdylibs similarly. If `-C prefer-dynamic` is set, the caller may
90 // be code-size conscious, but without it, it makes sense to statically
92 CrateType
::Dylib
| CrateType
::Cdylib
if !sess
.opts
.cg
.prefer_dynamic
=> Linkage
::Static
,
93 CrateType
::Dylib
| CrateType
::Cdylib
=> Linkage
::Dynamic
,
95 // If the global prefer_dynamic switch is turned off, or the final
96 // executable will be statically linked, prefer static crate linkage.
97 CrateType
::Executable
if !sess
.opts
.cg
.prefer_dynamic
|| sess
.crt_static(Some(ty
)) => {
100 CrateType
::Executable
=> Linkage
::Dynamic
,
102 // proc-macro crates are mostly cdylibs, but we also need metadata.
103 CrateType
::ProcMacro
=> Linkage
::Static
,
105 // No linkage happens with rlibs, we just needed the metadata (which we
106 // got long ago), so don't bother with anything.
107 CrateType
::Rlib
=> Linkage
::NotLinked
,
109 // staticlibs must have all static dependencies.
110 CrateType
::Staticlib
=> Linkage
::Static
,
113 if preferred_linkage
== Linkage
::NotLinked
{
114 // If the crate is not linked, there are no link-time dependencies.
118 if preferred_linkage
== Linkage
::Static
{
119 // Attempt static linkage first. For dylibs and executables, we may be
120 // able to retry below with dynamic linkage.
121 if let Some(v
) = attempt_static(tcx
) {
125 // Staticlibs and static executables must have all static dependencies.
126 // If any are not found, generate some nice pretty errors.
127 if ty
== CrateType
::Staticlib
128 || (ty
== CrateType
::Executable
129 && sess
.crt_static(Some(ty
))
130 && !sess
.target
.crt_static_allows_dylibs
)
132 for &cnum
in tcx
.crates(()).iter() {
133 if tcx
.dep_kind(cnum
).macros_only() {
136 let src
= tcx
.used_crate_source(cnum
);
137 if src
.rlib
.is_some() {
141 "crate `{}` required to be available in rlib format, \
142 but was not found in this form",
150 let mut formats
= FxHashMap
::default();
152 // Sweep all crates for found dylibs. Add all dylibs, as well as their
153 // dependencies, ensuring there are no conflicts. The only valid case for a
154 // dependency to be relied upon twice is for both cases to rely on a dylib.
155 for &cnum
in tcx
.crates(()).iter() {
156 if tcx
.dep_kind(cnum
).macros_only() {
159 let name
= tcx
.crate_name(cnum
);
160 let src
= tcx
.used_crate_source(cnum
);
161 if src
.dylib
.is_some() {
162 tracing
::info
!("adding dylib: {}", name
);
163 add_library(tcx
, cnum
, RequireDynamic
, &mut formats
);
164 let deps
= tcx
.dylib_dependency_formats(cnum
);
165 for &(depnum
, style
) in deps
.iter() {
166 tracing
::info
!("adding {:?}: {}", style
, tcx
.crate_name(depnum
));
167 add_library(tcx
, depnum
, style
, &mut formats
);
172 // Collect what we've got so far in the return vector.
173 let last_crate
= tcx
.crates(()).len();
174 let mut ret
= (1..last_crate
+ 1)
175 .map(|cnum
| match formats
.get(&CrateNum
::new(cnum
)) {
176 Some(&RequireDynamic
) => Linkage
::Dynamic
,
177 Some(&RequireStatic
) => Linkage
::IncludedFromDylib
,
178 None
=> Linkage
::NotLinked
,
180 .collect
::<Vec
<_
>>();
182 // Run through the dependency list again, and add any missing libraries as
185 // If the crate hasn't been included yet and it's not actually required
186 // (e.g., it's an allocator) then we skip it here as well.
187 for &cnum
in tcx
.crates(()).iter() {
188 let src
= tcx
.used_crate_source(cnum
);
189 if src
.dylib
.is_none()
190 && !formats
.contains_key(&cnum
)
191 && tcx
.dep_kind(cnum
) == CrateDepKind
::Explicit
193 assert
!(src
.rlib
.is_some() || src
.rmeta
.is_some());
194 tracing
::info
!("adding staticlib: {}", tcx
.crate_name(cnum
));
195 add_library(tcx
, cnum
, RequireStatic
, &mut formats
);
196 ret
[cnum
.as_usize() - 1] = Linkage
::Static
;
200 // We've gotten this far because we're emitting some form of a final
201 // artifact which means that we may need to inject dependencies of some
204 // Things like allocators and panic runtimes may not have been activated
205 // quite yet, so do so here.
206 activate_injected_dep(CStore
::from_tcx(tcx
).injected_panic_runtime(), &mut ret
, &|cnum
| {
207 tcx
.is_panic_runtime(cnum
)
210 // When dylib B links to dylib A, then when using B we must also link to A.
211 // It could be the case, however, that the rlib for A is present (hence we
212 // found metadata), but the dylib for A has since been removed.
214 // For situations like this, we perform one last pass over the dependencies,
215 // making sure that everything is available in the requested format.
216 for (cnum
, kind
) in ret
.iter().enumerate() {
217 let cnum
= CrateNum
::new(cnum
+ 1);
218 let src
= tcx
.used_crate_source(cnum
);
220 Linkage
::NotLinked
| Linkage
::IncludedFromDylib
=> {}
221 Linkage
::Static
if src
.rlib
.is_some() => continue,
222 Linkage
::Dynamic
if src
.dylib
.is_some() => continue,
224 let kind
= match kind
{
225 Linkage
::Static
=> "rlib",
229 "crate `{}` required to be available in {} format, \
230 but was not found in this form",
231 tcx
.crate_name(cnum
),
244 link
: LinkagePreference
,
245 m
: &mut FxHashMap
<CrateNum
, LinkagePreference
>,
249 // If the linkages differ, then we'd have two copies of the library
250 // if we continued linking. If the linkages are both static, then we
251 // would also have two copies of the library (static from two
252 // different locations).
254 // This error is probably a little obscure, but I imagine that it
255 // can be refined over time.
256 if link2
!= link
|| link
== RequireStatic
{
258 .struct_err(&format
!(
259 "cannot satisfy dependencies so `{}` only \
264 "having upstream crates all available in one format \
265 will likely make this go away",
271 m
.insert(cnum
, link
);
276 fn attempt_static(tcx
: TyCtxt
<'_
>) -> Option
<DependencyList
> {
277 let all_crates_available_as_rlib
= tcx
282 if tcx
.dep_kind(cnum
).macros_only() {
285 Some(tcx
.used_crate_source(cnum
).rlib
.is_some())
287 .all(|is_rlib
| is_rlib
);
288 if !all_crates_available_as_rlib
{
292 // All crates are available in an rlib format, so we're just going to link
293 // everything in explicitly so long as it's actually required.
294 let last_crate
= tcx
.crates(()).len();
295 let mut ret
= (1..last_crate
+ 1)
297 if tcx
.dep_kind(CrateNum
::new(cnum
)) == CrateDepKind
::Explicit
{
303 .collect
::<Vec
<_
>>();
305 // Our allocator/panic runtime may not have been linked above if it wasn't
306 // explicitly linked, which is the case for any injected dependency. Handle
307 // that here and activate them.
308 activate_injected_dep(CStore
::from_tcx(tcx
).injected_panic_runtime(), &mut ret
, &|cnum
| {
309 tcx
.is_panic_runtime(cnum
)
315 // Given a list of how to link upstream dependencies so far, ensure that an
316 // injected dependency is activated. This will not do anything if one was
317 // transitively included already (e.g., via a dylib or explicitly so).
319 // If an injected dependency was not found then we're guaranteed the
320 // metadata::creader module has injected that dependency (not listed as
321 // a required dependency) in one of the session's field. If this field is not
322 // set then this compilation doesn't actually need the dependency and we can
323 // also skip this step entirely.
324 fn activate_injected_dep(
325 injected
: Option
<CrateNum
>,
326 list
: &mut DependencyList
,
327 replaces_injected
: &dyn Fn(CrateNum
) -> bool
,
329 for (i
, slot
) in list
.iter().enumerate() {
330 let cnum
= CrateNum
::new(i
+ 1);
331 if !replaces_injected(cnum
) {
334 if *slot
!= Linkage
::NotLinked
{
338 if let Some(injected
) = injected
{
339 let idx
= injected
.as_usize() - 1;
340 assert_eq
!(list
[idx
], Linkage
::NotLinked
);
341 list
[idx
] = Linkage
::Static
;
345 // After the linkage for a crate has been determined we need to verify that
346 // there's only going to be one allocator in the output.
347 fn verify_ok(tcx
: TyCtxt
<'_
>, list
: &[Linkage
]) {
348 let sess
= &tcx
.sess
;
352 let mut panic_runtime
= None
;
353 for (i
, linkage
) in list
.iter().enumerate() {
354 if let Linkage
::NotLinked
= *linkage
{
357 let cnum
= CrateNum
::new(i
+ 1);
359 if tcx
.is_panic_runtime(cnum
) {
360 if let Some((prev
, _
)) = panic_runtime
{
361 let prev_name
= tcx
.crate_name(prev
);
362 let cur_name
= tcx
.crate_name(cnum
);
364 "cannot link together two \
365 panic runtimes: {} and {}",
369 panic_runtime
= Some((cnum
, tcx
.panic_strategy(cnum
)));
373 // If we found a panic runtime, then we know by this point that it's the
374 // only one, but we perform validation here that all the panic strategy
375 // compilation modes for the whole DAG are valid.
376 if let Some((cnum
, found_strategy
)) = panic_runtime
{
377 let desired_strategy
= sess
.panic_strategy();
379 // First up, validate that our selected panic runtime is indeed exactly
380 // our same strategy.
381 if found_strategy
!= desired_strategy
{
383 "the linked panic runtime `{}` is \
384 not compiled with this crate's \
385 panic strategy `{}`",
386 tcx
.crate_name(cnum
),
387 desired_strategy
.desc()
391 // Next up, verify that all other crates are compatible with this panic
392 // strategy. If the dep isn't linked, we ignore it, and if our strategy
393 // is abort then it's compatible with everything. Otherwise all crates'
394 // panic strategy must match our own.
395 for (i
, linkage
) in list
.iter().enumerate() {
396 if let Linkage
::NotLinked
= *linkage
{
399 if desired_strategy
== PanicStrategy
::Abort
{
402 let cnum
= CrateNum
::new(i
+ 1);
403 let found_strategy
= tcx
.panic_strategy(cnum
);
404 let is_compiler_builtins
= tcx
.is_compiler_builtins(cnum
);
405 if is_compiler_builtins
|| desired_strategy
== found_strategy
{
410 "the crate `{}` is compiled with the \
411 panic strategy `{}` which is \
412 incompatible with this crate's \
414 tcx
.crate_name(cnum
),
415 found_strategy
.desc(),
416 desired_strategy
.desc()