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).
68 use middle
::cstore
::CrateStore
;
69 use middle
::cstore
::LinkagePreference
::{self, RequireStatic, RequireDynamic}
;
70 use util
::nodemap
::FnvHashMap
;
72 /// A list of dependencies for a certain crate type.
74 /// The length of this vector is the same as the number of external crates used.
75 /// The value is None if the crate does not need to be linked (it was found
76 /// statically in another dylib), or Some(kind) if it needs to be linked as
77 /// `kind` (either static or dynamic).
78 pub type DependencyList
= Vec
<Linkage
>;
80 /// A mapping of all required dependencies for a particular flavor of output.
82 /// This is local to the tcx, and is generally relevant to one session.
83 pub type Dependencies
= FnvHashMap
<config
::CrateType
, DependencyList
>;
85 #[derive(Copy, Clone, PartialEq, Debug)]
93 pub fn calculate(sess
: &session
::Session
) {
94 let mut fmts
= sess
.dependency_formats
.borrow_mut();
95 for &ty
in sess
.crate_types
.borrow().iter() {
96 let linkage
= calculate_type(sess
, ty
);
97 verify_ok(sess
, &linkage
);
98 fmts
.insert(ty
, linkage
);
100 sess
.abort_if_errors();
103 fn calculate_type(sess
: &session
::Session
,
104 ty
: config
::CrateType
) -> DependencyList
{
106 // If the global prefer_dynamic switch is turned off, first attempt
107 // static linkage (this can fail).
108 config
::CrateTypeExecutable
if !sess
.opts
.cg
.prefer_dynamic
=> {
109 match attempt_static(sess
) {
115 // No linkage happens with rlibs, we just needed the metadata (which we
116 // got long ago), so don't bother with anything.
117 config
::CrateTypeRlib
=> return Vec
::new(),
119 // Staticlibs must have all static dependencies. If any fail to be
120 // found, we generate some nice pretty errors.
121 config
::CrateTypeStaticlib
=> {
122 match attempt_static(sess
) {
126 for cnum
in sess
.cstore
.crates() {
127 let src
= sess
.cstore
.used_crate_source(cnum
);
128 if src
.rlib
.is_some() { continue }
129 sess
.err(&format
!("dependency `{}` not found in rlib format",
130 sess
.cstore
.crate_name(cnum
)));
135 // Generating a dylib without `-C prefer-dynamic` means that we're going
136 // to try to eagerly statically link all dependencies. This is normally
137 // done for end-product dylibs, not intermediate products.
138 config
::CrateTypeDylib
if !sess
.opts
.cg
.prefer_dynamic
=> {
139 match attempt_static(sess
) {
145 // Everything else falls through below
146 config
::CrateTypeExecutable
| config
::CrateTypeDylib
=> {}
,
149 let mut formats
= FnvHashMap();
151 // Sweep all crates for found dylibs. Add all dylibs, as well as their
152 // dependencies, ensuring there are no conflicts. The only valid case for a
153 // dependency to be relied upon twice is for both cases to rely on a dylib.
154 for cnum
in sess
.cstore
.crates() {
155 let name
= sess
.cstore
.crate_name(cnum
);
156 let src
= sess
.cstore
.used_crate_source(cnum
);
157 if src
.dylib
.is_some() {
158 info
!("adding dylib: {}", name
);
159 add_library(sess
, cnum
, RequireDynamic
, &mut formats
);
160 let deps
= sess
.cstore
.dylib_dependency_formats(cnum
);
161 for &(depnum
, style
) in &deps
{
162 info
!("adding {:?}: {}", style
,
163 sess
.cstore
.crate_name(depnum
));
164 add_library(sess
, depnum
, style
, &mut formats
);
169 // Collect what we've got so far in the return vector.
170 let last_crate
= sess
.cstore
.crates().len() as ast
::CrateNum
;
171 let mut ret
= (1..last_crate
+1).map(|cnum
| {
172 match formats
.get(&cnum
) {
173 Some(&RequireDynamic
) => Linkage
::Dynamic
,
174 Some(&RequireStatic
) => Linkage
::IncludedFromDylib
,
175 None
=> Linkage
::NotLinked
,
177 }).collect
::<Vec
<_
>>();
179 // Run through the dependency list again, and add any missing libraries as
182 // If the crate hasn't been included yet and it's not actually required
183 // (e.g. it's an allocator) then we skip it here as well.
184 for cnum
in sess
.cstore
.crates() {
185 let src
= sess
.cstore
.used_crate_source(cnum
);
186 if src
.dylib
.is_none() &&
187 !formats
.contains_key(&cnum
) &&
188 sess
.cstore
.is_explicitly_linked(cnum
) {
189 assert
!(src
.rlib
.is_some());
190 info
!("adding staticlib: {}", sess
.cstore
.crate_name(cnum
));
191 add_library(sess
, cnum
, RequireStatic
, &mut formats
);
192 ret
[cnum
as usize - 1] = Linkage
::Static
;
196 // We've gotten this far because we're emitting some form of a final
197 // artifact which means that we're going to need an allocator of some form.
198 // No allocator may have been required or linked so far, so activate one
199 // here if one isn't set.
200 activate_allocator(sess
, &mut ret
);
202 // When dylib B links to dylib A, then when using B we must also link to A.
203 // It could be the case, however, that the rlib for A is present (hence we
204 // found metadata), but the dylib for A has since been removed.
206 // For situations like this, we perform one last pass over the dependencies,
207 // making sure that everything is available in the requested format.
208 for (cnum
, kind
) in ret
.iter().enumerate() {
209 let cnum
= (cnum
+ 1) as ast
::CrateNum
;
210 let src
= sess
.cstore
.used_crate_source(cnum
);
213 Linkage
::IncludedFromDylib
=> {}
214 Linkage
::Static
if src
.rlib
.is_some() => continue,
215 Linkage
::Dynamic
if src
.dylib
.is_some() => continue,
217 let kind
= match kind
{
218 Linkage
::Static
=> "rlib",
221 let name
= sess
.cstore
.crate_name(cnum
);
222 sess
.err(&format
!("crate `{}` required to be available in {}, \
223 but it was not available in this form",
232 fn add_library(sess
: &session
::Session
,
234 link
: LinkagePreference
,
235 m
: &mut FnvHashMap
<ast
::CrateNum
, LinkagePreference
>) {
238 // If the linkages differ, then we'd have two copies of the library
239 // if we continued linking. If the linkages are both static, then we
240 // would also have two copies of the library (static from two
241 // different locations).
243 // This error is probably a little obscure, but I imagine that it
244 // can be refined over time.
245 if link2
!= link
|| link
== RequireStatic
{
246 sess
.err(&format
!("cannot satisfy dependencies so `{}` only \
247 shows up once", sess
.cstore
.crate_name(cnum
)));
248 sess
.help("having upstream crates all available in one format \
249 will likely make this go away");
252 None
=> { m.insert(cnum, link); }
256 fn attempt_static(sess
: &session
::Session
) -> Option
<DependencyList
> {
257 let crates
= sess
.cstore
.used_crates(RequireStatic
);
258 if !crates
.iter().by_ref().all(|&(_
, ref p
)| p
.is_some()) {
262 // All crates are available in an rlib format, so we're just going to link
263 // everything in explicitly so long as it's actually required.
264 let last_crate
= sess
.cstore
.crates().len() as ast
::CrateNum
;
265 let mut ret
= (1..last_crate
+1).map(|cnum
| {
266 if sess
.cstore
.is_explicitly_linked(cnum
) {
271 }).collect
::<Vec
<_
>>();
273 // Our allocator may not have been activated as it's not flagged with
274 // explicitly_linked, so flag it here if necessary.
275 activate_allocator(sess
, &mut ret
);
280 // Given a list of how to link upstream dependencies so far, ensure that an
281 // allocator is activated. This will not do anything if one was transitively
282 // included already (e.g. via a dylib or explicitly so).
284 // If an allocator was not found then we're guaranteed the metadata::creader
285 // module has injected an allocator dependency (not listed as a required
286 // dependency) in the session's `injected_allocator` field. If this field is not
287 // set then this compilation doesn't actually need an allocator and we can also
288 // skip this step entirely.
289 fn activate_allocator(sess
: &session
::Session
, list
: &mut DependencyList
) {
290 let mut allocator_found
= false;
291 for (i
, slot
) in list
.iter().enumerate() {
292 let cnum
= (i
+ 1) as ast
::CrateNum
;
293 if !sess
.cstore
.is_allocator(cnum
) {
296 if let Linkage
::NotLinked
= *slot
{
299 allocator_found
= true;
301 if !allocator_found
{
302 if let Some(injected_allocator
) = sess
.injected_allocator
.get() {
303 let idx
= injected_allocator
as usize - 1;
304 assert_eq
!(list
[idx
], Linkage
::NotLinked
);
305 list
[idx
] = Linkage
::Static
;
310 // After the linkage for a crate has been determined we need to verify that
311 // there's only going to be one allocator in the output.
312 fn verify_ok(sess
: &session
::Session
, list
: &[Linkage
]) {
316 let mut allocator
= None
;
317 for (i
, linkage
) in list
.iter().enumerate() {
318 let cnum
= (i
+ 1) as ast
::CrateNum
;
319 if !sess
.cstore
.is_allocator(cnum
) {
322 if let Linkage
::NotLinked
= *linkage
{
325 if let Some(prev_alloc
) = allocator
{
326 let prev_name
= sess
.cstore
.crate_name(prev_alloc
);
327 let cur_name
= sess
.cstore
.crate_name(cnum
);
328 sess
.err(&format
!("cannot link together two \
329 allocators: {} and {}",
330 prev_name
, cur_name
));
332 allocator
= Some(cnum
);