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::DepKind;
70 use middle::cstore::LinkagePreference::{self, RequireStatic, RequireDynamic};
71 use util::nodemap::FxHashMap;
72 use rustc_back::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 = sess.dependency_formats.borrow_mut();
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();
106 fn calculate_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
107 ty: config::CrateType) -> DependencyList {
109 let sess = &tcx.sess;
111 if !sess.opts.output_types.should_trans() {
116 // If the global prefer_dynamic switch is turned off, first attempt
117 // static linkage (this can fail).
118 config::CrateTypeExecutable if !sess.opts.cg.prefer_dynamic => {
119 if let Some(v) = attempt_static(tcx) {
124 // No linkage happens with rlibs, we just needed the metadata (which we
125 // got long ago), so don't bother with anything.
126 config::CrateTypeRlib => return Vec::new(),
128 // Staticlibs and cdylibs must have all static dependencies. If any fail
129 // to be found, we generate some nice pretty errors.
130 config::CrateTypeStaticlib |
131 config::CrateTypeCdylib => {
132 if let Some(v) = attempt_static(tcx) {
135 for cnum in sess.cstore.crates() {
136 if sess.cstore.dep_kind(cnum).macros_only() { continue }
137 let src = sess.cstore.used_crate_source(cnum);
138 if src.rlib.is_some() { continue }
139 sess.err(&format!("dependency `{}` not found in rlib format",
140 sess.cstore.crate_name(cnum)));
145 // Generating a dylib without `-C prefer-dynamic` means that we're going
146 // to try to eagerly statically link all dependencies. This is normally
147 // done for end-product dylibs, not intermediate products.
148 config::CrateTypeDylib if !sess.opts.cg.prefer_dynamic => {
149 if let Some(v) = attempt_static(tcx) {
154 // Everything else falls through below. This will happen either with the
155 // `-C prefer-dynamic` or because we're a proc-macro crate. Note that
156 // proc-macro crates are required to be dylibs, and they're currently
157 // required to link to libsyntax as well.
158 config::CrateTypeExecutable |
159 config::CrateTypeDylib |
160 config::CrateTypeProcMacro => {},
163 let mut formats = FxHashMap();
165 // Sweep all crates for found dylibs. Add all dylibs, as well as their
166 // dependencies, ensuring there are no conflicts. The only valid case for a
167 // dependency to be relied upon twice is for both cases to rely on a dylib.
168 for cnum in sess.cstore.crates() {
169 if sess.cstore.dep_kind(cnum).macros_only() { continue }
170 let name = sess.cstore.crate_name(cnum);
171 let src = sess.cstore.used_crate_source(cnum);
172 if src.dylib.is_some() {
173 info!("adding dylib: {}", name);
174 add_library(sess, cnum, RequireDynamic, &mut formats);
175 let deps = tcx.dylib_dependency_formats(cnum.as_def_id());
176 for &(depnum, style) in deps.iter() {
177 info!("adding {:?}: {}", style,
178 sess.cstore.crate_name(depnum));
179 add_library(sess, depnum, style, &mut formats);
184 // Collect what we've got so far in the return vector.
185 let last_crate = sess.cstore.crates().len();
186 let mut ret = (1..last_crate+1).map(|cnum| {
187 match formats.get(&CrateNum::new(cnum)) {
188 Some(&RequireDynamic) => Linkage::Dynamic,
189 Some(&RequireStatic) => Linkage::IncludedFromDylib,
190 None => Linkage::NotLinked,
192 }).collect::<Vec<_>>();
194 // Run through the dependency list again, and add any missing libraries as
197 // If the crate hasn't been included yet and it's not actually required
198 // (e.g. it's an allocator) then we skip it here as well.
199 for cnum in sess.cstore.crates() {
200 let src = sess.cstore.used_crate_source(cnum);
201 if src.dylib.is_none() &&
202 !formats.contains_key(&cnum) &&
203 sess.cstore.dep_kind(cnum) == DepKind::Explicit {
204 assert!(src.rlib.is_some() || src.rmeta.is_some());
205 info!("adding staticlib: {}", sess.cstore.crate_name(cnum));
206 add_library(sess, cnum, RequireStatic, &mut formats);
207 ret[cnum.as_usize() - 1] = Linkage::Static;
211 // We've gotten this far because we're emitting some form of a final
212 // artifact which means that we may need to inject dependencies of some
215 // Things like allocators and panic runtimes may not have been activated
216 // quite yet, so do so here.
217 activate_injected_dep(sess.injected_panic_runtime.get(), &mut ret,
218 &|cnum| tcx.is_panic_runtime(cnum.as_def_id()));
219 activate_injected_allocator(sess, &mut ret);
221 // When dylib B links to dylib A, then when using B we must also link to A.
222 // It could be the case, however, that the rlib for A is present (hence we
223 // found metadata), but the dylib for A has since been removed.
225 // For situations like this, we perform one last pass over the dependencies,
226 // making sure that everything is available in the requested format.
227 for (cnum, kind) in ret.iter().enumerate() {
228 let cnum = CrateNum::new(cnum + 1);
229 let src = sess.cstore.used_crate_source(cnum);
232 Linkage::IncludedFromDylib => {}
233 Linkage::Static if src.rlib.is_some() => continue,
234 Linkage::Dynamic if src.dylib.is_some() => continue,
236 let kind = match kind {
237 Linkage::Static => "rlib",
240 let name = sess.cstore.crate_name(cnum);
241 sess.err(&format!("crate `{}` required to be available in {}, \
242 but it was not available in this form",
251 fn add_library(sess: &session::Session,
253 link: LinkagePreference,
254 m: &mut FxHashMap<CrateNum, LinkagePreference>) {
257 // If the linkages differ, then we'd have two copies of the library
258 // if we continued linking. If the linkages are both static, then we
259 // would also have two copies of the library (static from two
260 // different locations).
262 // This error is probably a little obscure, but I imagine that it
263 // can be refined over time.
264 if link2 != link || link == RequireStatic {
265 sess.struct_err(&format!("cannot satisfy dependencies so `{}` only \
266 shows up once", sess.cstore.crate_name(cnum)))
267 .help("having upstream crates all available in one format \
268 will likely make this go away")
272 None => { m.insert(cnum, link); }
276 fn attempt_static<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Option<DependencyList> {
277 let sess = &tcx.sess;
278 let crates = sess.cstore.used_crates(RequireStatic);
279 if !crates.iter().by_ref().all(|&(_, ref p)| p.is_some()) {
283 // All crates are available in an rlib format, so we're just going to link
284 // everything in explicitly so long as it's actually required.
285 let last_crate = sess.cstore.crates().len();
286 let mut ret = (1..last_crate+1).map(|cnum| {
287 if sess.cstore.dep_kind(CrateNum::new(cnum)) == DepKind::Explicit {
292 }).collect::<Vec<_>>();
294 // Our allocator/panic runtime may not have been linked above if it wasn't
295 // explicitly linked, which is the case for any injected dependency. Handle
296 // that here and activate them.
297 activate_injected_dep(sess.injected_panic_runtime.get(), &mut ret,
298 &|cnum| tcx.is_panic_runtime(cnum.as_def_id()));
299 activate_injected_allocator(sess, &mut ret);
304 // Given a list of how to link upstream dependencies so far, ensure that an
305 // injected dependency is activated. This will not do anything if one was
306 // transitively included already (e.g. via a dylib or explicitly so).
308 // If an injected dependency was not found then we're guaranteed the
309 // metadata::creader module has injected that dependency (not listed as
310 // a required dependency) in one of the session's field. If this field is not
311 // set then this compilation doesn't actually need the dependency and we can
312 // also skip this step entirely.
313 fn activate_injected_dep(injected: Option<CrateNum>,
314 list: &mut DependencyList,
315 replaces_injected: &Fn(CrateNum) -> bool) {
316 for (i, slot) in list.iter().enumerate() {
317 let cnum = CrateNum::new(i + 1);
318 if !replaces_injected(cnum) {
321 if *slot != Linkage::NotLinked {
325 if let Some(injected) = injected {
326 let idx = injected.as_usize() - 1;
327 assert_eq!(list[idx], Linkage::NotLinked);
328 list[idx] = Linkage::Static;
332 fn activate_injected_allocator(sess: &session::Session,
333 list: &mut DependencyList) {
334 let cnum = match sess.injected_allocator.get() {
338 let idx = cnum.as_usize() - 1;
339 if list[idx] == Linkage::NotLinked {
340 list[idx] = Linkage::Static;
344 // After the linkage for a crate has been determined we need to verify that
345 // there's only going to be one allocator in the output.
346 fn verify_ok<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, list: &[Linkage]) {
347 let sess = &tcx.sess;
351 let mut panic_runtime = None;
352 for (i, linkage) in list.iter().enumerate() {
353 if let Linkage::NotLinked = *linkage {
356 let cnum = CrateNum::new(i + 1);
358 if tcx.is_panic_runtime(cnum.as_def_id()) {
359 if let Some((prev, _)) = panic_runtime {
360 let prev_name = sess.cstore.crate_name(prev);
361 let cur_name = sess.cstore.crate_name(cnum);
362 sess.err(&format!("cannot link together two \
363 panic runtimes: {} and {}",
364 prev_name, cur_name));
366 panic_runtime = Some((cnum, sess.cstore.panic_strategy(cnum)));
370 // If we found a panic runtime, then we know by this point that it's the
371 // only one, but we perform validation here that all the panic strategy
372 // compilation modes for the whole DAG are valid.
373 if let Some((cnum, found_strategy)) = panic_runtime {
374 let desired_strategy = sess.panic_strategy();
376 // First up, validate that our selected panic runtime is indeed exactly
377 // our same strategy.
378 if found_strategy != desired_strategy {
379 sess.err(&format!("the linked panic runtime `{}` is \
380 not compiled with this crate's \
381 panic strategy `{}`",
382 sess.cstore.crate_name(cnum),
383 desired_strategy.desc()));
386 // Next up, verify that all other crates are compatible with this panic
387 // strategy. If the dep isn't linked, we ignore it, and if our strategy
388 // is abort then it's compatible with everything. Otherwise all crates'
389 // panic strategy must match our own.
390 for (i, linkage) in list.iter().enumerate() {
391 if let Linkage::NotLinked = *linkage {
394 if desired_strategy == PanicStrategy::Abort {
397 let cnum = CrateNum::new(i + 1);
398 let found_strategy = sess.cstore.panic_strategy(cnum);
399 if desired_strategy == found_strategy {
403 sess.err(&format!("the crate `{}` is compiled with the \
404 panic strategy `{}` which is \
405 incompatible with this crate's \
407 sess.cstore.crate_name(cnum),
408 found_strategy.desc(),
409 desired_strategy.desc()));