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::hir::def_id::CrateNum;
56 use crate::session::config;
57 use crate::ty::TyCtxt;
58 use crate::middle::cstore::{self, DepKind};
59 use crate::middle::cstore::LinkagePreference::{self, RequireStatic, RequireDynamic};
60 use crate::util::nodemap::FxHashMap;
61 use rustc_target::spec::PanicStrategy;
63 /// A list of dependencies for a certain crate type.
65 /// The length of this vector is the same as the number of external crates used.
66 /// The value is None if the crate does not need to be linked (it was found
67 /// statically in another dylib), or Some(kind) if it needs to be linked as
68 /// `kind` (either static or dynamic).
69 pub type DependencyList = Vec<Linkage>;
71 /// A mapping of all required dependencies for a particular flavor of output.
73 /// This is local to the tcx, and is generally relevant to one session.
74 pub type Dependencies = FxHashMap<config::CrateType, DependencyList>;
76 #[derive(Copy, Clone, PartialEq, Debug)]
84 pub fn calculate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
86 let fmts = sess.crate_types.borrow().iter().map(|&ty| {
87 let linkage = calculate_type(tcx, ty);
88 verify_ok(tcx, &linkage);
90 }).collect::<FxHashMap<_, _>>();
91 sess.abort_if_errors();
92 sess.dependency_formats.set(fmts);
95 fn calculate_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
96 ty: config::CrateType) -> DependencyList {
100 if !sess.opts.output_types.should_codegen() {
104 let preferred_linkage = match ty {
105 // cdylibs must have all static dependencies.
106 config::CrateType::Cdylib => Linkage::Static,
108 // Generating a dylib without `-C prefer-dynamic` means that we're going
109 // to try to eagerly statically link all dependencies. This is normally
110 // done for end-product dylibs, not intermediate products.
111 config::CrateType::Dylib if !sess.opts.cg.prefer_dynamic => Linkage::Static,
112 config::CrateType::Dylib => Linkage::Dynamic,
114 // If the global prefer_dynamic switch is turned off, or the final
115 // executable will be statically linked, prefer static crate linkage.
116 config::CrateType::Executable if !sess.opts.cg.prefer_dynamic ||
117 sess.crt_static() => Linkage::Static,
118 config::CrateType::Executable => Linkage::Dynamic,
120 // proc-macro crates are mostly cdylibs, but we also need metadata.
121 config::CrateType::ProcMacro => Linkage::Static,
123 // No linkage happens with rlibs, we just needed the metadata (which we
124 // got long ago), so don't bother with anything.
125 config::CrateType::Rlib => Linkage::NotLinked,
127 // staticlibs must have all static dependencies.
128 config::CrateType::Staticlib => Linkage::Static,
131 if preferred_linkage == Linkage::NotLinked {
132 // If the crate is not linked, there are no link-time dependencies.
136 if preferred_linkage == Linkage::Static {
137 // Attempt static linkage first. For dylibs and executables, we may be
138 // able to retry below with dynamic linkage.
139 if let Some(v) = attempt_static(tcx) {
143 // Staticlibs, cdylibs, and static executables must have all static
144 // dependencies. If any are not found, generate some nice pretty errors.
145 if ty == config::CrateType::Cdylib || ty == config::CrateType::Staticlib ||
146 (ty == config::CrateType::Executable && sess.crt_static() &&
147 !sess.target.target.options.crt_static_allows_dylibs) {
148 for &cnum in tcx.crates().iter() {
149 if tcx.dep_kind(cnum).macros_only() { continue }
150 let src = tcx.used_crate_source(cnum);
151 if src.rlib.is_some() { continue }
152 sess.err(&format!("crate `{}` required to be available in rlib format, \
153 but was not found in this form",
154 tcx.crate_name(cnum)));
160 let mut formats = FxHashMap::default();
162 // Sweep all crates for found dylibs. Add all dylibs, as well as their
163 // dependencies, ensuring there are no conflicts. The only valid case for a
164 // dependency to be relied upon twice is for both cases to rely on a dylib.
165 for &cnum in tcx.crates().iter() {
166 if tcx.dep_kind(cnum).macros_only() { continue }
167 let name = tcx.crate_name(cnum);
168 let src = tcx.used_crate_source(cnum);
169 if src.dylib.is_some() {
170 info!("adding dylib: {}", name);
171 add_library(tcx, cnum, RequireDynamic, &mut formats);
172 let deps = tcx.dylib_dependency_formats(cnum);
173 for &(depnum, style) in deps.iter() {
174 info!("adding {:?}: {}", style, tcx.crate_name(depnum));
175 add_library(tcx, depnum, style, &mut formats);
180 // Collect what we've got so far in the return vector.
181 let last_crate = tcx.crates().len();
182 let mut ret = (1..last_crate+1).map(|cnum| {
183 match formats.get(&CrateNum::new(cnum)) {
184 Some(&RequireDynamic) => Linkage::Dynamic,
185 Some(&RequireStatic) => Linkage::IncludedFromDylib,
186 None => Linkage::NotLinked,
188 }).collect::<Vec<_>>();
190 // Run through the dependency list again, and add any missing libraries as
193 // If the crate hasn't been included yet and it's not actually required
194 // (e.g., it's an allocator) then we skip it here as well.
195 for &cnum in tcx.crates().iter() {
196 let src = tcx.used_crate_source(cnum);
197 if src.dylib.is_none() &&
198 !formats.contains_key(&cnum) &&
199 tcx.dep_kind(cnum) == DepKind::Explicit {
200 assert!(src.rlib.is_some() || src.rmeta.is_some());
201 info!("adding staticlib: {}", tcx.crate_name(cnum));
202 add_library(tcx, cnum, RequireStatic, &mut formats);
203 ret[cnum.as_usize() - 1] = Linkage::Static;
207 // We've gotten this far because we're emitting some form of a final
208 // artifact which means that we may need to inject dependencies of some
211 // Things like allocators and panic runtimes may not have been activated
212 // quite yet, so do so here.
213 activate_injected_dep(*sess.injected_panic_runtime.get(), &mut ret,
214 &|cnum| tcx.is_panic_runtime(cnum));
216 // When dylib B links to dylib A, then when using B we must also link to A.
217 // It could be the case, however, that the rlib for A is present (hence we
218 // found metadata), but the dylib for A has since been removed.
220 // For situations like this, we perform one last pass over the dependencies,
221 // making sure that everything is available in the requested format.
222 for (cnum, kind) in ret.iter().enumerate() {
223 let cnum = CrateNum::new(cnum + 1);
224 let src = tcx.used_crate_source(cnum);
227 Linkage::IncludedFromDylib => {}
228 Linkage::Static if src.rlib.is_some() => continue,
229 Linkage::Dynamic if src.dylib.is_some() => continue,
231 let kind = match kind {
232 Linkage::Static => "rlib",
235 sess.err(&format!("crate `{}` required to be available in {} format, \
236 but was not found in this form",
237 tcx.crate_name(cnum), kind));
245 fn add_library(tcx: TyCtxt<'_, '_, '_>,
247 link: LinkagePreference,
248 m: &mut FxHashMap<CrateNum, LinkagePreference>) {
251 // If the linkages differ, then we'd have two copies of the library
252 // if we continued linking. If the linkages are both static, then we
253 // would also have two copies of the library (static from two
254 // different locations).
256 // This error is probably a little obscure, but I imagine that it
257 // can be refined over time.
258 if link2 != link || link == RequireStatic {
259 tcx.sess.struct_err(&format!("cannot satisfy dependencies so `{}` only \
260 shows up once", tcx.crate_name(cnum)))
261 .help("having upstream crates all available in one format \
262 will likely make this go away")
266 None => { m.insert(cnum, link); }
270 fn attempt_static<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Option<DependencyList> {
271 let sess = &tcx.sess;
272 let crates = cstore::used_crates(tcx, RequireStatic);
273 if !crates.iter().by_ref().all(|&(_, ref p)| p.is_some()) {
277 // All crates are available in an rlib format, so we're just going to link
278 // everything in explicitly so long as it's actually required.
279 let last_crate = tcx.crates().len();
280 let mut ret = (1..last_crate+1).map(|cnum| {
281 if tcx.dep_kind(CrateNum::new(cnum)) == DepKind::Explicit {
286 }).collect::<Vec<_>>();
288 // Our allocator/panic runtime may not have been linked above if it wasn't
289 // explicitly linked, which is the case for any injected dependency. Handle
290 // that here and activate them.
291 activate_injected_dep(*sess.injected_panic_runtime.get(), &mut ret,
292 &|cnum| tcx.is_panic_runtime(cnum));
297 // Given a list of how to link upstream dependencies so far, ensure that an
298 // injected dependency is activated. This will not do anything if one was
299 // transitively included already (e.g., via a dylib or explicitly so).
301 // If an injected dependency was not found then we're guaranteed the
302 // metadata::creader module has injected that dependency (not listed as
303 // a required dependency) in one of the session's field. If this field is not
304 // set then this compilation doesn't actually need the dependency and we can
305 // also skip this step entirely.
306 fn activate_injected_dep(injected: Option<CrateNum>,
307 list: &mut DependencyList,
308 replaces_injected: &dyn Fn(CrateNum) -> bool) {
309 for (i, slot) in list.iter().enumerate() {
310 let cnum = CrateNum::new(i + 1);
311 if !replaces_injected(cnum) {
314 if *slot != Linkage::NotLinked {
318 if let Some(injected) = injected {
319 let idx = injected.as_usize() - 1;
320 assert_eq!(list[idx], Linkage::NotLinked);
321 list[idx] = Linkage::Static;
325 // After the linkage for a crate has been determined we need to verify that
326 // there's only going to be one allocator in the output.
327 fn verify_ok<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, list: &[Linkage]) {
328 let sess = &tcx.sess;
332 let mut panic_runtime = None;
333 for (i, linkage) in list.iter().enumerate() {
334 if let Linkage::NotLinked = *linkage {
337 let cnum = CrateNum::new(i + 1);
339 if tcx.is_panic_runtime(cnum) {
340 if let Some((prev, _)) = panic_runtime {
341 let prev_name = tcx.crate_name(prev);
342 let cur_name = tcx.crate_name(cnum);
343 sess.err(&format!("cannot link together two \
344 panic runtimes: {} and {}",
345 prev_name, cur_name));
347 panic_runtime = Some((cnum, tcx.panic_strategy(cnum)));
351 // If we found a panic runtime, then we know by this point that it's the
352 // only one, but we perform validation here that all the panic strategy
353 // compilation modes for the whole DAG are valid.
354 if let Some((cnum, found_strategy)) = panic_runtime {
355 let desired_strategy = sess.panic_strategy();
357 // First up, validate that our selected panic runtime is indeed exactly
358 // our same strategy.
359 if found_strategy != desired_strategy {
360 sess.err(&format!("the linked panic runtime `{}` is \
361 not compiled with this crate's \
362 panic strategy `{}`",
363 tcx.crate_name(cnum),
364 desired_strategy.desc()));
367 // Next up, verify that all other crates are compatible with this panic
368 // strategy. If the dep isn't linked, we ignore it, and if our strategy
369 // is abort then it's compatible with everything. Otherwise all crates'
370 // panic strategy must match our own.
371 for (i, linkage) in list.iter().enumerate() {
372 if let Linkage::NotLinked = *linkage {
375 if desired_strategy == PanicStrategy::Abort {
378 let cnum = CrateNum::new(i + 1);
379 let found_strategy = tcx.panic_strategy(cnum);
380 let is_compiler_builtins = tcx.is_compiler_builtins(cnum);
381 if is_compiler_builtins || desired_strategy == found_strategy {
385 sess.err(&format!("the crate `{}` is compiled with the \
386 panic strategy `{}` which is \
387 incompatible with this crate's \
389 tcx.crate_name(cnum),
390 found_strategy.desc(),
391 desired_strategy.desc()));