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