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 collections::HashMap;
69 use metadata::csearch;
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<Option<cstore::LinkagePreference>>;
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 = HashMap<session::CrateType, DependencyList>;
85 pub fn calculate(tcx: &ty::ctxt) {
86 let mut fmts = tcx.dependency_formats.borrow_mut();
87 for &ty in tcx.sess.crate_types.borrow().iter() {
88 fmts.insert(ty, calculate_type(&tcx.sess, ty));
90 tcx.sess.abort_if_errors();
93 fn calculate_type(sess: &session::Session,
94 ty: session::CrateType) -> DependencyList {
96 // If the global prefer_dynamic switch is turned off, first attempt
97 // static linkage (this can fail).
98 session::CrateTypeExecutable if !sess.opts.cg.prefer_dynamic => {
99 match attempt_static(sess) {
105 // No linkage happens with rlibs, we just needed the metadata (which we
106 // got long ago), so don't bother with anything.
107 session::CrateTypeRlib => return Vec::new(),
109 // Staticlibs must have all static dependencies. If any fail to be
110 // found, we generate some nice pretty errors.
111 session::CrateTypeStaticlib => {
112 match attempt_static(sess) {
116 sess.cstore.iter_crate_data(|cnum, data| {
117 let src = sess.cstore.get_used_crate_source(cnum).unwrap();
118 if src.rlib.is_some() { return }
119 sess.err(format!("dependency `{}` not found in rlib format",
125 // Everything else falls through below
126 session::CrateTypeExecutable | session::CrateTypeDylib => {},
129 let mut formats = HashMap::new();
131 // Sweep all crates for found dylibs. Add all dylibs, as well as their
132 // dependencies, ensuring there are no conflicts. The only valid case for a
133 // dependency to be relied upon twice is for both cases to rely on a dylib.
134 sess.cstore.iter_crate_data(|cnum, data| {
135 let src = sess.cstore.get_used_crate_source(cnum).unwrap();
136 if src.dylib.is_some() {
137 add_library(sess, cnum, cstore::RequireDynamic, &mut formats);
138 debug!("adding dylib: {}", data.name);
139 let deps = csearch::get_dylib_dependency_formats(&sess.cstore, cnum);
140 for &(depnum, style) in deps.iter() {
141 add_library(sess, depnum, style, &mut formats);
142 debug!("adding {}: {}", style,
143 sess.cstore.get_crate_data(depnum).name.clone());
148 // Collect what we've got so far in the return vector.
149 let mut ret = range(1, sess.cstore.next_crate_num()).map(|i| {
150 match formats.find(&i).map(|v| *v) {
151 v @ Some(cstore::RequireDynamic) => v,
154 }).collect::<Vec<_>>();
156 // Run through the dependency list again, and add any missing libraries as
158 sess.cstore.iter_crate_data(|cnum, data| {
159 let src = sess.cstore.get_used_crate_source(cnum).unwrap();
160 if src.dylib.is_none() && !formats.contains_key(&cnum) {
161 assert!(src.rlib.is_some());
162 add_library(sess, cnum, cstore::RequireStatic, &mut formats);
163 *ret.get_mut(cnum as uint - 1) = Some(cstore::RequireStatic);
164 debug!("adding staticlib: {}", data.name);
168 // When dylib B links to dylib A, then when using B we must also link to A.
169 // It could be the case, however, that the rlib for A is present (hence we
170 // found metadata), but the dylib for A has since been removed.
172 // For situations like this, we perform one last pass over the dependencies,
173 // making sure that everything is available in the requested format.
174 for (cnum, kind) in ret.iter().enumerate() {
175 let cnum = cnum as ast::CrateNum;
176 let src = sess.cstore.get_used_crate_source(cnum + 1).unwrap();
179 Some(cstore::RequireStatic) if src.rlib.is_some() => continue,
180 Some(cstore::RequireDynamic) if src.dylib.is_some() => continue,
182 let data = sess.cstore.get_crate_data(cnum + 1);
183 sess.err(format!("crate `{}` required to be available in {}, \
184 but it was not available in this form",
187 cstore::RequireStatic => "rlib",
188 cstore::RequireDynamic => "dylib",
197 fn add_library(sess: &session::Session,
199 link: cstore::LinkagePreference,
200 m: &mut HashMap<ast::CrateNum, cstore::LinkagePreference>) {
201 match m.find(&cnum) {
203 // If the linkages differ, then we'd have two copies of the library
204 // if we continued linking. If the linkages are both static, then we
205 // would also have two copies of the library (static from two
206 // different locations).
208 // This error is probably a little obscure, but I imagine that it
209 // can be refined over time.
210 if link2 != link || link == cstore::RequireStatic {
211 let data = sess.cstore.get_crate_data(cnum);
212 sess.err(format!("cannot satisfy dependencies so `{}` only \
213 shows up once", data.name));
214 sess.note("having upstream crates all available in one format \
215 will likely make this go away");
218 None => { m.insert(cnum, link); }
222 fn attempt_static(sess: &session::Session) -> Option<DependencyList> {
223 let crates = sess.cstore.get_used_crates(cstore::RequireStatic);
224 if crates.iter().all(|&(_, ref p)| p.is_some()) {
225 Some(crates.move_iter().map(|_| Some(cstore::RequireStatic)).collect())