]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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. | |
4 | // | |
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. | |
10 | ||
11 | //! Resolution of mixing rlibs and dylibs | |
12 | //! | |
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). | |
19 | //! | |
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: | |
23 | //! | |
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. | |
28 | //! | |
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... | |
32 | //! | |
33 | //! The current selection algorithm below looks mostly similar to: | |
34 | //! | |
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 | |
52 | //! added already). | |
53 | //! | |
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. | |
58 | //! | |
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). | |
63 | ||
9e0c209e | 64 | use hir::def_id::CrateNum; |
1a4d82fc JJ |
65 | |
66 | use session; | |
a7813a04 | 67 | use session::config::{self, PanicStrategy}; |
92a42be0 | 68 | use middle::cstore::LinkagePreference::{self, RequireStatic, RequireDynamic}; |
1a4d82fc JJ |
69 | use util::nodemap::FnvHashMap; |
70 | ||
71 | /// A list of dependencies for a certain crate type. | |
72 | /// | |
73 | /// The length of this vector is the same as the number of external crates used. | |
74 | /// The value is None if the crate does not need to be linked (it was found | |
75 | /// statically in another dylib), or Some(kind) if it needs to be linked as | |
76 | /// `kind` (either static or dynamic). | |
e9174d1e | 77 | pub type DependencyList = Vec<Linkage>; |
1a4d82fc JJ |
78 | |
79 | /// A mapping of all required dependencies for a particular flavor of output. | |
80 | /// | |
81 | /// This is local to the tcx, and is generally relevant to one session. | |
82 | pub type Dependencies = FnvHashMap<config::CrateType, DependencyList>; | |
83 | ||
e9174d1e SL |
84 | #[derive(Copy, Clone, PartialEq, Debug)] |
85 | pub enum Linkage { | |
86 | NotLinked, | |
87 | IncludedFromDylib, | |
88 | Static, | |
89 | Dynamic, | |
90 | } | |
91 | ||
92 | pub fn calculate(sess: &session::Session) { | |
93 | let mut fmts = sess.dependency_formats.borrow_mut(); | |
94 | for &ty in sess.crate_types.borrow().iter() { | |
95 | let linkage = calculate_type(sess, ty); | |
96 | verify_ok(sess, &linkage); | |
97 | fmts.insert(ty, linkage); | |
1a4d82fc | 98 | } |
e9174d1e | 99 | sess.abort_if_errors(); |
1a4d82fc JJ |
100 | } |
101 | ||
102 | fn calculate_type(sess: &session::Session, | |
103 | ty: config::CrateType) -> DependencyList { | |
104 | match ty { | |
105 | // If the global prefer_dynamic switch is turned off, first attempt | |
106 | // static linkage (this can fail). | |
107 | config::CrateTypeExecutable if !sess.opts.cg.prefer_dynamic => { | |
3157f602 XL |
108 | if let Some(v) = attempt_static(sess) { |
109 | return v; | |
1a4d82fc JJ |
110 | } |
111 | } | |
112 | ||
113 | // No linkage happens with rlibs, we just needed the metadata (which we | |
114 | // got long ago), so don't bother with anything. | |
115 | config::CrateTypeRlib => return Vec::new(), | |
116 | ||
a7813a04 XL |
117 | // Staticlibs and cdylibs must have all static dependencies. If any fail |
118 | // to be found, we generate some nice pretty errors. | |
119 | config::CrateTypeStaticlib | | |
120 | config::CrateTypeCdylib => { | |
3157f602 XL |
121 | if let Some(v) = attempt_static(sess) { |
122 | return v; | |
1a4d82fc | 123 | } |
92a42be0 SL |
124 | for cnum in sess.cstore.crates() { |
125 | let src = sess.cstore.used_crate_source(cnum); | |
126 | if src.rlib.is_some() { continue } | |
1a4d82fc | 127 | sess.err(&format!("dependency `{}` not found in rlib format", |
92a42be0 SL |
128 | sess.cstore.crate_name(cnum))); |
129 | } | |
1a4d82fc JJ |
130 | return Vec::new(); |
131 | } | |
132 | ||
133 | // Generating a dylib without `-C prefer-dynamic` means that we're going | |
134 | // to try to eagerly statically link all dependencies. This is normally | |
135 | // done for end-product dylibs, not intermediate products. | |
136 | config::CrateTypeDylib if !sess.opts.cg.prefer_dynamic => { | |
3157f602 XL |
137 | if let Some(v) = attempt_static(sess) { |
138 | return v; | |
1a4d82fc JJ |
139 | } |
140 | } | |
141 | ||
9e0c209e SL |
142 | // Everything else falls through below. This will happen either with the |
143 | // `-C prefer-dynamic` or because we're a rustc-macro crate. Note that | |
144 | // rustc-macro crates are required to be dylibs, and they're currently | |
145 | // required to link to libsyntax as well. | |
146 | config::CrateTypeExecutable | | |
147 | config::CrateTypeDylib | | |
148 | config::CrateTypeRustcMacro => {}, | |
1a4d82fc JJ |
149 | } |
150 | ||
85aaf69f | 151 | let mut formats = FnvHashMap(); |
1a4d82fc JJ |
152 | |
153 | // Sweep all crates for found dylibs. Add all dylibs, as well as their | |
154 | // dependencies, ensuring there are no conflicts. The only valid case for a | |
155 | // dependency to be relied upon twice is for both cases to rely on a dylib. | |
92a42be0 SL |
156 | for cnum in sess.cstore.crates() { |
157 | let name = sess.cstore.crate_name(cnum); | |
158 | let src = sess.cstore.used_crate_source(cnum); | |
1a4d82fc | 159 | if src.dylib.is_some() { |
92a42be0 SL |
160 | info!("adding dylib: {}", name); |
161 | add_library(sess, cnum, RequireDynamic, &mut formats); | |
162 | let deps = sess.cstore.dylib_dependency_formats(cnum); | |
85aaf69f | 163 | for &(depnum, style) in &deps { |
e9174d1e | 164 | info!("adding {:?}: {}", style, |
92a42be0 | 165 | sess.cstore.crate_name(depnum)); |
1a4d82fc JJ |
166 | add_library(sess, depnum, style, &mut formats); |
167 | } | |
168 | } | |
92a42be0 | 169 | } |
1a4d82fc JJ |
170 | |
171 | // Collect what we've got so far in the return vector. | |
9e0c209e | 172 | let last_crate = sess.cstore.crates().len(); |
92a42be0 | 173 | let mut ret = (1..last_crate+1).map(|cnum| { |
9e0c209e | 174 | match formats.get(&CrateNum::new(cnum)) { |
92a42be0 SL |
175 | Some(&RequireDynamic) => Linkage::Dynamic, |
176 | Some(&RequireStatic) => Linkage::IncludedFromDylib, | |
e9174d1e | 177 | None => Linkage::NotLinked, |
1a4d82fc JJ |
178 | } |
179 | }).collect::<Vec<_>>(); | |
180 | ||
181 | // Run through the dependency list again, and add any missing libraries as | |
182 | // static libraries. | |
e9174d1e SL |
183 | // |
184 | // If the crate hasn't been included yet and it's not actually required | |
185 | // (e.g. it's an allocator) then we skip it here as well. | |
92a42be0 SL |
186 | for cnum in sess.cstore.crates() { |
187 | let src = sess.cstore.used_crate_source(cnum); | |
e9174d1e SL |
188 | if src.dylib.is_none() && |
189 | !formats.contains_key(&cnum) && | |
92a42be0 | 190 | sess.cstore.is_explicitly_linked(cnum) { |
1a4d82fc | 191 | assert!(src.rlib.is_some()); |
92a42be0 SL |
192 | info!("adding staticlib: {}", sess.cstore.crate_name(cnum)); |
193 | add_library(sess, cnum, RequireStatic, &mut formats); | |
9e0c209e | 194 | ret[cnum.as_usize() - 1] = Linkage::Static; |
1a4d82fc | 195 | } |
92a42be0 | 196 | } |
1a4d82fc | 197 | |
e9174d1e | 198 | // We've gotten this far because we're emitting some form of a final |
a7813a04 XL |
199 | // artifact which means that we may need to inject dependencies of some |
200 | // form. | |
201 | // | |
202 | // Things like allocators and panic runtimes may not have been activated | |
203 | // quite yet, so do so here. | |
204 | activate_injected_dep(sess.injected_allocator.get(), &mut ret, | |
205 | &|cnum| sess.cstore.is_allocator(cnum)); | |
206 | activate_injected_dep(sess.injected_panic_runtime.get(), &mut ret, | |
207 | &|cnum| sess.cstore.is_panic_runtime(cnum)); | |
e9174d1e | 208 | |
1a4d82fc JJ |
209 | // When dylib B links to dylib A, then when using B we must also link to A. |
210 | // It could be the case, however, that the rlib for A is present (hence we | |
211 | // found metadata), but the dylib for A has since been removed. | |
212 | // | |
213 | // For situations like this, we perform one last pass over the dependencies, | |
214 | // making sure that everything is available in the requested format. | |
215 | for (cnum, kind) in ret.iter().enumerate() { | |
9e0c209e | 216 | let cnum = CrateNum::new(cnum + 1); |
92a42be0 | 217 | let src = sess.cstore.used_crate_source(cnum); |
1a4d82fc | 218 | match *kind { |
e9174d1e SL |
219 | Linkage::NotLinked | |
220 | Linkage::IncludedFromDylib => {} | |
221 | Linkage::Static if src.rlib.is_some() => continue, | |
222 | Linkage::Dynamic if src.dylib.is_some() => continue, | |
223 | kind => { | |
224 | let kind = match kind { | |
225 | Linkage::Static => "rlib", | |
226 | _ => "dylib", | |
227 | }; | |
92a42be0 | 228 | let name = sess.cstore.crate_name(cnum); |
1a4d82fc JJ |
229 | sess.err(&format!("crate `{}` required to be available in {}, \ |
230 | but it was not available in this form", | |
92a42be0 | 231 | name, kind)); |
1a4d82fc JJ |
232 | } |
233 | } | |
234 | } | |
235 | ||
236 | return ret; | |
237 | } | |
238 | ||
239 | fn add_library(sess: &session::Session, | |
9e0c209e | 240 | cnum: CrateNum, |
92a42be0 | 241 | link: LinkagePreference, |
9e0c209e | 242 | m: &mut FnvHashMap<CrateNum, LinkagePreference>) { |
1a4d82fc JJ |
243 | match m.get(&cnum) { |
244 | Some(&link2) => { | |
245 | // If the linkages differ, then we'd have two copies of the library | |
246 | // if we continued linking. If the linkages are both static, then we | |
247 | // would also have two copies of the library (static from two | |
248 | // different locations). | |
249 | // | |
250 | // This error is probably a little obscure, but I imagine that it | |
251 | // can be refined over time. | |
92a42be0 | 252 | if link2 != link || link == RequireStatic { |
9cc50fc6 SL |
253 | sess.struct_err(&format!("cannot satisfy dependencies so `{}` only \ |
254 | shows up once", sess.cstore.crate_name(cnum))) | |
255 | .help("having upstream crates all available in one format \ | |
256 | will likely make this go away") | |
257 | .emit(); | |
1a4d82fc JJ |
258 | } |
259 | } | |
260 | None => { m.insert(cnum, link); } | |
261 | } | |
262 | } | |
263 | ||
264 | fn attempt_static(sess: &session::Session) -> Option<DependencyList> { | |
92a42be0 | 265 | let crates = sess.cstore.used_crates(RequireStatic); |
e9174d1e SL |
266 | if !crates.iter().by_ref().all(|&(_, ref p)| p.is_some()) { |
267 | return None | |
268 | } | |
269 | ||
270 | // All crates are available in an rlib format, so we're just going to link | |
271 | // everything in explicitly so long as it's actually required. | |
9e0c209e | 272 | let last_crate = sess.cstore.crates().len(); |
92a42be0 | 273 | let mut ret = (1..last_crate+1).map(|cnum| { |
9e0c209e | 274 | if sess.cstore.is_explicitly_linked(CrateNum::new(cnum)) { |
e9174d1e SL |
275 | Linkage::Static |
276 | } else { | |
277 | Linkage::NotLinked | |
278 | } | |
279 | }).collect::<Vec<_>>(); | |
280 | ||
a7813a04 XL |
281 | // Our allocator/panic runtime may not have been linked above if it wasn't |
282 | // explicitly linked, which is the case for any injected dependency. Handle | |
283 | // that here and activate them. | |
284 | activate_injected_dep(sess.injected_allocator.get(), &mut ret, | |
285 | &|cnum| sess.cstore.is_allocator(cnum)); | |
286 | activate_injected_dep(sess.injected_panic_runtime.get(), &mut ret, | |
287 | &|cnum| sess.cstore.is_panic_runtime(cnum)); | |
e9174d1e SL |
288 | |
289 | Some(ret) | |
290 | } | |
291 | ||
292 | // Given a list of how to link upstream dependencies so far, ensure that an | |
a7813a04 XL |
293 | // injected dependency is activated. This will not do anything if one was |
294 | // transitively included already (e.g. via a dylib or explicitly so). | |
e9174d1e | 295 | // |
a7813a04 XL |
296 | // If an injected dependency was not found then we're guaranteed the |
297 | // metadata::creader module has injected that dependency (not listed as | |
298 | // a required dependency) in one of the session's field. If this field is not | |
299 | // set then this compilation doesn't actually need the dependency and we can | |
300 | // also skip this step entirely. | |
9e0c209e | 301 | fn activate_injected_dep(injected: Option<CrateNum>, |
a7813a04 | 302 | list: &mut DependencyList, |
9e0c209e | 303 | replaces_injected: &Fn(CrateNum) -> bool) { |
e9174d1e | 304 | for (i, slot) in list.iter().enumerate() { |
9e0c209e | 305 | let cnum = CrateNum::new(i + 1); |
a7813a04 | 306 | if !replaces_injected(cnum) { |
e9174d1e SL |
307 | continue |
308 | } | |
a7813a04 XL |
309 | if *slot != Linkage::NotLinked { |
310 | return | |
e9174d1e | 311 | } |
e9174d1e | 312 | } |
a7813a04 | 313 | if let Some(injected) = injected { |
9e0c209e | 314 | let idx = injected.as_usize() - 1; |
a7813a04 XL |
315 | assert_eq!(list[idx], Linkage::NotLinked); |
316 | list[idx] = Linkage::Static; | |
e9174d1e SL |
317 | } |
318 | } | |
319 | ||
320 | // After the linkage for a crate has been determined we need to verify that | |
321 | // there's only going to be one allocator in the output. | |
322 | fn verify_ok(sess: &session::Session, list: &[Linkage]) { | |
323 | if list.len() == 0 { | |
324 | return | |
325 | } | |
326 | let mut allocator = None; | |
a7813a04 | 327 | let mut panic_runtime = None; |
e9174d1e | 328 | for (i, linkage) in list.iter().enumerate() { |
e9174d1e SL |
329 | if let Linkage::NotLinked = *linkage { |
330 | continue | |
331 | } | |
9e0c209e | 332 | let cnum = CrateNum::new(i + 1); |
a7813a04 XL |
333 | if sess.cstore.is_allocator(cnum) { |
334 | if let Some(prev) = allocator { | |
335 | let prev_name = sess.cstore.crate_name(prev); | |
336 | let cur_name = sess.cstore.crate_name(cnum); | |
337 | sess.err(&format!("cannot link together two \ | |
338 | allocators: {} and {}", | |
339 | prev_name, cur_name)); | |
340 | } | |
341 | allocator = Some(cnum); | |
342 | } | |
343 | ||
344 | if sess.cstore.is_panic_runtime(cnum) { | |
345 | if let Some((prev, _)) = panic_runtime { | |
346 | let prev_name = sess.cstore.crate_name(prev); | |
347 | let cur_name = sess.cstore.crate_name(cnum); | |
348 | sess.err(&format!("cannot link together two \ | |
349 | panic runtimes: {} and {}", | |
350 | prev_name, cur_name)); | |
351 | } | |
352 | panic_runtime = Some((cnum, sess.cstore.panic_strategy(cnum))); | |
353 | } | |
354 | } | |
355 | ||
356 | // If we found a panic runtime, then we know by this point that it's the | |
357 | // only one, but we perform validation here that all the panic strategy | |
358 | // compilation modes for the whole DAG are valid. | |
359 | if let Some((cnum, found_strategy)) = panic_runtime { | |
360 | let desired_strategy = sess.opts.cg.panic.clone(); | |
361 | ||
362 | // First up, validate that our selected panic runtime is indeed exactly | |
363 | // our same strategy. | |
364 | if found_strategy != desired_strategy { | |
365 | sess.err(&format!("the linked panic runtime `{}` is \ | |
366 | not compiled with this crate's \ | |
367 | panic strategy `{}`", | |
368 | sess.cstore.crate_name(cnum), | |
369 | desired_strategy.desc())); | |
370 | } | |
371 | ||
372 | // Next up, verify that all other crates are compatible with this panic | |
373 | // strategy. If the dep isn't linked, we ignore it, and if our strategy | |
374 | // is abort then it's compatible with everything. Otherwise all crates' | |
375 | // panic strategy must match our own. | |
376 | for (i, linkage) in list.iter().enumerate() { | |
377 | if let Linkage::NotLinked = *linkage { | |
378 | continue | |
379 | } | |
380 | if desired_strategy == PanicStrategy::Abort { | |
381 | continue | |
382 | } | |
9e0c209e | 383 | let cnum = CrateNum::new(i + 1); |
a7813a04 XL |
384 | let found_strategy = sess.cstore.panic_strategy(cnum); |
385 | if desired_strategy == found_strategy { | |
386 | continue | |
387 | } | |
388 | ||
389 | sess.err(&format!("the crate `{}` is compiled with the \ | |
390 | panic strategy `{}` which is \ | |
391 | incompatible with this crate's \ | |
392 | strategy of `{}`", | |
393 | sess.cstore.crate_name(cnum), | |
394 | found_strategy.desc(), | |
395 | desired_strategy.desc())); | |
e9174d1e | 396 | } |
1a4d82fc JJ |
397 | } |
398 | } |