1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Resolution of mixing rlibs and dylibs
13 //! When producing a final artifact, such as a dynamic library, the compiler has
14 //! a choice between linking an rlib or linking a dylib of all upstream
15 //! dependencies. The linking phase must guarantee, however, that a library only
16 //! show up once in the object file. For example, it is illegal for library A to
17 //! be statically linked to B and C in separate dylibs, and then link B and C
18 //! into a crate D (because library A appears twice).
20 //! The job of this module is to calculate what format each upstream crate
21 //! should be used when linking each output type requested in this session. This
22 //! generally follows this set of rules:
24 //! 1. Each library must appear exactly once in the output.
25 //! 2. Each rlib contains only one library (it's just an object file)
26 //! 3. Each dylib can contain more than one library (due to static linking),
27 //! and can also bring in many dynamic dependencies.
29 //! With these constraints in mind, it's generally a very difficult problem to
30 //! find a solution that's not "all rlibs" or "all dylibs". I have suspicions
31 //! that NP-ness may come into the picture here...
33 //! The current selection algorithm below looks mostly similar to:
35 //! 1. If static linking is required, then require all upstream dependencies
36 //! to be available as rlibs. If not, generate an error.
37 //! 2. If static linking is requested (generating an executable), then
38 //! attempt to use all upstream dependencies as rlibs. If any are not
39 //! found, bail out and continue to step 3.
40 //! 3. Static linking has failed, at least one library must be dynamically
41 //! linked. Apply a heuristic by greedily maximizing the number of
42 //! dynamically linked libraries.
43 //! 4. Each upstream dependency available as a dynamic library is
44 //! registered. The dependencies all propagate, adding to a map. It is
45 //! possible for a dylib to add a static library as a dependency, but it
46 //! is illegal for two dylibs to add the same static library as a
47 //! dependency. The same dylib can be added twice. Additionally, it is
48 //! illegal to add a static dependency when it was previously found as a
49 //! dylib (and vice versa)
50 //! 5. After all dynamic dependencies have been traversed, re-traverse the
51 //! remaining dependencies and add them statically (if they haven't been
54 //! While not perfect, this algorithm should help support use-cases such as leaf
55 //! dependencies being static while the larger tree of inner dependencies are
56 //! all dynamic. This isn't currently very well battle tested, so it will likely
57 //! fall short in some use cases.
59 //! Currently, there is no way to specify the preference of linkage with a
60 //! particular library (other than a global dynamic/static switch).
61 //! Additionally, the algorithm is geared towards finding *any* solution rather
62 //! than finding a number of solutions (there are normally quite a few).
64 use hir
::def_id
::CrateNum
;
69 use middle
::cstore
::{self, DepKind}
;
70 use middle
::cstore
::LinkagePreference
::{self, RequireStatic, RequireDynamic}
;
71 use util
::nodemap
::FxHashMap
;
72 use rustc_target
::spec
::PanicStrategy
;
74 /// A list of dependencies for a certain crate type.
76 /// The length of this vector is the same as the number of external crates used.
77 /// The value is None if the crate does not need to be linked (it was found
78 /// statically in another dylib), or Some(kind) if it needs to be linked as
79 /// `kind` (either static or dynamic).
80 pub type DependencyList
= Vec
<Linkage
>;
82 /// A mapping of all required dependencies for a particular flavor of output.
84 /// This is local to the tcx, and is generally relevant to one session.
85 pub type Dependencies
= FxHashMap
<config
::CrateType
, DependencyList
>;
87 #[derive(Copy, Clone, PartialEq, Debug)]
95 pub fn calculate
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>) {
97 let mut fmts
= FxHashMap
::default();
98 for &ty
in sess
.crate_types
.borrow().iter() {
99 let linkage
= calculate_type(tcx
, ty
);
100 verify_ok(tcx
, &linkage
);
101 fmts
.insert(ty
, linkage
);
103 sess
.abort_if_errors();
104 sess
.dependency_formats
.set(fmts
);
107 fn calculate_type
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
108 ty
: config
::CrateType
) -> DependencyList
{
110 let sess
= &tcx
.sess
;
112 if !sess
.opts
.output_types
.should_codegen() {
116 let preferred_linkage
= match ty
{
117 // cdylibs must have all static dependencies.
118 config
::CrateType
::Cdylib
=> Linkage
::Static
,
120 // Generating a dylib without `-C prefer-dynamic` means that we're going
121 // to try to eagerly statically link all dependencies. This is normally
122 // done for end-product dylibs, not intermediate products.
123 config
::CrateType
::Dylib
if !sess
.opts
.cg
.prefer_dynamic
=> Linkage
::Static
,
124 config
::CrateType
::Dylib
=> Linkage
::Dynamic
,
126 // If the global prefer_dynamic switch is turned off, or the final
127 // executable will be statically linked, prefer static crate linkage.
128 config
::CrateType
::Executable
if !sess
.opts
.cg
.prefer_dynamic
||
129 sess
.crt_static() => Linkage
::Static
,
130 config
::CrateType
::Executable
=> Linkage
::Dynamic
,
132 // proc-macro crates are required to be dylibs, and they're currently
133 // required to link to libsyntax as well.
134 config
::CrateType
::ProcMacro
=> Linkage
::Dynamic
,
136 // No linkage happens with rlibs, we just needed the metadata (which we
137 // got long ago), so don't bother with anything.
138 config
::CrateType
::Rlib
=> Linkage
::NotLinked
,
140 // staticlibs must have all static dependencies.
141 config
::CrateType
::Staticlib
=> Linkage
::Static
,
144 if preferred_linkage
== Linkage
::NotLinked
{
145 // If the crate is not linked, there are no link-time dependencies.
149 if preferred_linkage
== Linkage
::Static
{
150 // Attempt static linkage first. For dylibs and executables, we may be
151 // able to retry below with dynamic linkage.
152 if let Some(v
) = attempt_static(tcx
) {
156 // Staticlibs, cdylibs, and static executables must have all static
157 // dependencies. If any are not found, generate some nice pretty errors.
158 if ty
== config
::CrateType
::Cdylib
|| ty
== config
::CrateType
::Staticlib
||
159 (ty
== config
::CrateType
::Executable
&& sess
.crt_static() &&
160 !sess
.target
.target
.options
.crt_static_allows_dylibs
) {
161 for &cnum
in tcx
.crates().iter() {
162 if tcx
.dep_kind(cnum
).macros_only() { continue }
163 let src
= tcx
.used_crate_source(cnum
);
164 if src
.rlib
.is_some() { continue }
165 sess
.err(&format
!("crate `{}` required to be available in rlib format, \
166 but was not found in this form",
167 tcx
.crate_name(cnum
)));
173 let mut formats
= FxHashMap
::default();
175 // Sweep all crates for found dylibs. Add all dylibs, as well as their
176 // dependencies, ensuring there are no conflicts. The only valid case for a
177 // dependency to be relied upon twice is for both cases to rely on a dylib.
178 for &cnum
in tcx
.crates().iter() {
179 if tcx
.dep_kind(cnum
).macros_only() { continue }
180 let name
= tcx
.crate_name(cnum
);
181 let src
= tcx
.used_crate_source(cnum
);
182 if src
.dylib
.is_some() {
183 info
!("adding dylib: {}", name
);
184 add_library(tcx
, cnum
, RequireDynamic
, &mut formats
);
185 let deps
= tcx
.dylib_dependency_formats(cnum
);
186 for &(depnum
, style
) in deps
.iter() {
187 info
!("adding {:?}: {}", style
, tcx
.crate_name(depnum
));
188 add_library(tcx
, depnum
, style
, &mut formats
);
193 // Collect what we've got so far in the return vector.
194 let last_crate
= tcx
.crates().len();
195 let mut ret
= (1..last_crate
+1).map(|cnum
| {
196 match formats
.get(&CrateNum
::new(cnum
)) {
197 Some(&RequireDynamic
) => Linkage
::Dynamic
,
198 Some(&RequireStatic
) => Linkage
::IncludedFromDylib
,
199 None
=> Linkage
::NotLinked
,
201 }).collect
::<Vec
<_
>>();
203 // Run through the dependency list again, and add any missing libraries as
206 // If the crate hasn't been included yet and it's not actually required
207 // (e.g. it's an allocator) then we skip it here as well.
208 for &cnum
in tcx
.crates().iter() {
209 let src
= tcx
.used_crate_source(cnum
);
210 if src
.dylib
.is_none() &&
211 !formats
.contains_key(&cnum
) &&
212 tcx
.dep_kind(cnum
) == DepKind
::Explicit
{
213 assert
!(src
.rlib
.is_some() || src
.rmeta
.is_some());
214 info
!("adding staticlib: {}", tcx
.crate_name(cnum
));
215 add_library(tcx
, cnum
, RequireStatic
, &mut formats
);
216 ret
[cnum
.as_usize() - 1] = Linkage
::Static
;
220 // We've gotten this far because we're emitting some form of a final
221 // artifact which means that we may need to inject dependencies of some
224 // Things like allocators and panic runtimes may not have been activated
225 // quite yet, so do so here.
226 activate_injected_dep(*sess
.injected_panic_runtime
.get(), &mut ret
,
227 &|cnum
| tcx
.is_panic_runtime(cnum
));
228 activate_injected_allocator(sess
, &mut ret
);
230 // When dylib B links to dylib A, then when using B we must also link to A.
231 // It could be the case, however, that the rlib for A is present (hence we
232 // found metadata), but the dylib for A has since been removed.
234 // For situations like this, we perform one last pass over the dependencies,
235 // making sure that everything is available in the requested format.
236 for (cnum
, kind
) in ret
.iter().enumerate() {
237 let cnum
= CrateNum
::new(cnum
+ 1);
238 let src
= tcx
.used_crate_source(cnum
);
241 Linkage
::IncludedFromDylib
=> {}
242 Linkage
::Static
if src
.rlib
.is_some() => continue,
243 Linkage
::Dynamic
if src
.dylib
.is_some() => continue,
245 let kind
= match kind
{
246 Linkage
::Static
=> "rlib",
249 sess
.err(&format
!("crate `{}` required to be available in {} format, \
250 but was not found in this form",
251 tcx
.crate_name(cnum
), kind
));
259 fn add_library(tcx
: TyCtxt
<'_
, '_
, '_
>,
261 link
: LinkagePreference
,
262 m
: &mut FxHashMap
<CrateNum
, LinkagePreference
>) {
265 // If the linkages differ, then we'd have two copies of the library
266 // if we continued linking. If the linkages are both static, then we
267 // would also have two copies of the library (static from two
268 // different locations).
270 // This error is probably a little obscure, but I imagine that it
271 // can be refined over time.
272 if link2
!= link
|| link
== RequireStatic
{
273 tcx
.sess
.struct_err(&format
!("cannot satisfy dependencies so `{}` only \
274 shows up once", tcx
.crate_name(cnum
)))
275 .help("having upstream crates all available in one format \
276 will likely make this go away")
280 None
=> { m.insert(cnum, link); }
284 fn attempt_static
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>) -> Option
<DependencyList
> {
285 let sess
= &tcx
.sess
;
286 let crates
= cstore
::used_crates(tcx
, RequireStatic
);
287 if !crates
.iter().by_ref().all(|&(_
, ref p
)| p
.is_some()) {
291 // All crates are available in an rlib format, so we're just going to link
292 // everything in explicitly so long as it's actually required.
293 let last_crate
= tcx
.crates().len();
294 let mut ret
= (1..last_crate
+1).map(|cnum
| {
295 if tcx
.dep_kind(CrateNum
::new(cnum
)) == DepKind
::Explicit
{
300 }).collect
::<Vec
<_
>>();
302 // Our allocator/panic runtime may not have been linked above if it wasn't
303 // explicitly linked, which is the case for any injected dependency. Handle
304 // that here and activate them.
305 activate_injected_dep(*sess
.injected_panic_runtime
.get(), &mut ret
,
306 &|cnum
| tcx
.is_panic_runtime(cnum
));
307 activate_injected_allocator(sess
, &mut ret
);
312 // Given a list of how to link upstream dependencies so far, ensure that an
313 // injected dependency is activated. This will not do anything if one was
314 // transitively included already (e.g. via a dylib or explicitly so).
316 // If an injected dependency was not found then we're guaranteed the
317 // metadata::creader module has injected that dependency (not listed as
318 // a required dependency) in one of the session's field. If this field is not
319 // set then this compilation doesn't actually need the dependency and we can
320 // also skip this step entirely.
321 fn activate_injected_dep(injected
: Option
<CrateNum
>,
322 list
: &mut DependencyList
,
323 replaces_injected
: &dyn Fn(CrateNum
) -> bool
) {
324 for (i
, slot
) in list
.iter().enumerate() {
325 let cnum
= CrateNum
::new(i
+ 1);
326 if !replaces_injected(cnum
) {
329 if *slot
!= Linkage
::NotLinked
{
333 if let Some(injected
) = injected
{
334 let idx
= injected
.as_usize() - 1;
335 assert_eq
!(list
[idx
], Linkage
::NotLinked
);
336 list
[idx
] = Linkage
::Static
;
340 fn activate_injected_allocator(sess
: &session
::Session
,
341 list
: &mut DependencyList
) {
342 let cnum
= match sess
.injected_allocator
.get() {
346 let idx
= cnum
.as_usize() - 1;
347 if list
[idx
] == Linkage
::NotLinked
{
348 list
[idx
] = Linkage
::Static
;
352 // After the linkage for a crate has been determined we need to verify that
353 // there's only going to be one allocator in the output.
354 fn verify_ok
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>, list
: &[Linkage
]) {
355 let sess
= &tcx
.sess
;
359 let mut panic_runtime
= None
;
360 for (i
, linkage
) in list
.iter().enumerate() {
361 if let Linkage
::NotLinked
= *linkage
{
364 let cnum
= CrateNum
::new(i
+ 1);
366 if tcx
.is_panic_runtime(cnum
) {
367 if let Some((prev
, _
)) = panic_runtime
{
368 let prev_name
= tcx
.crate_name(prev
);
369 let cur_name
= tcx
.crate_name(cnum
);
370 sess
.err(&format
!("cannot link together two \
371 panic runtimes: {} and {}",
372 prev_name
, cur_name
));
374 panic_runtime
= Some((cnum
, tcx
.panic_strategy(cnum
)));
378 // If we found a panic runtime, then we know by this point that it's the
379 // only one, but we perform validation here that all the panic strategy
380 // compilation modes for the whole DAG are valid.
381 if let Some((cnum
, found_strategy
)) = panic_runtime
{
382 let desired_strategy
= sess
.panic_strategy();
384 // First up, validate that our selected panic runtime is indeed exactly
385 // our same strategy.
386 if found_strategy
!= desired_strategy
{
387 sess
.err(&format
!("the linked panic runtime `{}` is \
388 not compiled with this crate's \
389 panic strategy `{}`",
390 tcx
.crate_name(cnum
),
391 desired_strategy
.desc()));
394 // Next up, verify that all other crates are compatible with this panic
395 // strategy. If the dep isn't linked, we ignore it, and if our strategy
396 // is abort then it's compatible with everything. Otherwise all crates'
397 // panic strategy must match our own.
398 for (i
, linkage
) in list
.iter().enumerate() {
399 if let Linkage
::NotLinked
= *linkage
{
402 if desired_strategy
== PanicStrategy
::Abort
{
405 let cnum
= CrateNum
::new(i
+ 1);
406 let found_strategy
= tcx
.panic_strategy(cnum
);
407 let is_compiler_builtins
= tcx
.is_compiler_builtins(cnum
);
408 if is_compiler_builtins
|| desired_strategy
== found_strategy
{
412 sess
.err(&format
!("the crate `{}` is compiled with the \
413 panic strategy `{}` which is \
414 incompatible with this crate's \
416 tcx
.crate_name(cnum
),
417 found_strategy
.desc(),
418 desired_strategy
.desc()));