1 //! Constructs the dependency graph for compilation.
3 //! Rust code is typically organized as a set of Cargo packages. The
4 //! dependencies between the packages themselves are stored in the
5 //! `Resolve` struct. However, we can't use that information as is for
6 //! compilation! A package typically contains several targets, or crates,
7 //! and these targets has inter-dependencies. For example, you need to
8 //! compile the `lib` target before the `bin` one, and you need to compile
9 //! `build.rs` before either of those.
11 //! So, we need to lower the `Resolve`, which specifies dependencies between
12 //! *packages*, to a graph of dependencies between their *targets*, and this
13 //! is exactly what this module is doing! Well, almost exactly: another
14 //! complication is that we might want to compile the same target several times
15 //! (for example, with and without tests), so we actually build a dependency
16 //! graph of `Unit`s, which capture these properties.
18 use crate::core
::compiler
::unit_graph
::{UnitDep, UnitGraph}
;
19 use crate::core
::compiler
::UnitInterner
;
20 use crate::core
::compiler
::{CompileKind, CompileMode, RustcTargetData, Unit}
;
21 use crate::core
::dependency
::DepKind
;
22 use crate::core
::profiles
::{Profile, Profiles, UnitFor}
;
23 use crate::core
::resolver
::features
::{FeaturesFor, ResolvedFeatures}
;
24 use crate::core
::resolver
::Resolve
;
25 use crate::core
::{Dependency, Package, PackageId, PackageSet, Target, Workspace}
;
26 use crate::ops
::resolve_all_features
;
27 use crate::util
::interning
::InternedString
;
28 use crate::util
::Config
;
29 use crate::CargoResult
;
31 use std
::collections
::{HashMap, HashSet}
;
33 /// Collection of stuff used while creating the `UnitGraph`.
34 struct State
<'a
, 'cfg
> {
35 ws
: &'a Workspace
<'cfg
>,
37 unit_dependencies
: UnitGraph
,
38 package_set
: &'a PackageSet
<'cfg
>,
39 usr_resolve
: &'a Resolve
,
40 usr_features
: &'a ResolvedFeatures
,
41 std_resolve
: Option
<&'a Resolve
>,
42 std_features
: Option
<&'a ResolvedFeatures
>,
43 /// This flag is `true` while generating the dependencies for the standard
46 global_mode
: CompileMode
,
47 target_data
: &'a RustcTargetData
,
48 profiles
: &'a Profiles
,
49 interner
: &'a UnitInterner
,
51 /// A set of edges in `unit_dependencies` where (a, b) means that the
52 /// dependency from a to b was added purely because it was a dev-dependency.
53 /// This is used during `connect_run_custom_build_deps`.
54 dev_dependency_edges
: HashSet
<(Unit
, Unit
)>,
57 pub fn build_unit_dependencies
<'a
, 'cfg
>(
58 ws
: &'a Workspace
<'cfg
>,
59 package_set
: &'a PackageSet
<'cfg
>,
61 features
: &'a ResolvedFeatures
,
62 std_resolve
: Option
<&'
a (Resolve
, ResolvedFeatures
)>,
64 std_roots
: &HashMap
<CompileKind
, Vec
<Unit
>>,
65 global_mode
: CompileMode
,
66 target_data
: &'a RustcTargetData
,
67 profiles
: &'a Profiles
,
68 interner
: &'a UnitInterner
,
69 ) -> CargoResult
<UnitGraph
> {
71 // If -Zbuild-std, don't attach units if there is nothing to build.
72 // Otherwise, other parts of the code may be confused by seeing units
73 // in the dep graph without a root.
74 return Ok(HashMap
::new());
76 let (std_resolve
, std_features
) = match std_resolve
{
77 Some((r
, f
)) => (Some(r
), Some(f
)),
80 let mut state
= State
{
83 unit_dependencies
: HashMap
::new(),
86 usr_features
: features
,
94 dev_dependency_edges
: HashSet
::new(),
97 let std_unit_deps
= calc_deps_of_std(&mut state
, std_roots
)?
;
99 deps_of_roots(roots
, &mut state
)?
;
100 super::links
::validate_links(state
.resolve(), &state
.unit_dependencies
)?
;
101 // Hopefully there aren't any links conflicts with the standard library?
103 if let Some(std_unit_deps
) = std_unit_deps
{
104 attach_std_deps(&mut state
, std_roots
, std_unit_deps
);
107 connect_run_custom_build_deps(&mut state
);
109 // Dependencies are used in tons of places throughout the backend, many of
110 // which affect the determinism of the build itself. As a result be sure
111 // that dependency lists are always sorted to ensure we've always got a
112 // deterministic output.
113 for list
in state
.unit_dependencies
.values_mut() {
116 trace
!("ALL UNIT DEPENDENCIES {:#?}", state
.unit_dependencies
);
118 Ok(state
.unit_dependencies
)
121 /// Compute all the dependencies for the standard library.
123 mut state
: &mut State
<'_
, '_
>,
124 std_roots
: &HashMap
<CompileKind
, Vec
<Unit
>>,
125 ) -> CargoResult
<Option
<UnitGraph
>> {
126 if std_roots
.is_empty() {
129 // Compute dependencies for the standard library.
131 for roots
in std_roots
.values() {
132 deps_of_roots(roots
, &mut state
)?
;
134 state
.is_std
= false;
135 Ok(Some(std
::mem
::take(&mut state
.unit_dependencies
)))
138 /// Add the standard library units to the `unit_dependencies`.
140 state
: &mut State
<'_
, '_
>,
141 std_roots
: &HashMap
<CompileKind
, Vec
<Unit
>>,
142 std_unit_deps
: UnitGraph
,
144 // Attach the standard library as a dependency of every target unit.
145 for (unit
, deps
) in state
.unit_dependencies
.iter_mut() {
146 if !unit
.kind
.is_host() && !unit
.mode
.is_run_custom_build() {
147 deps
.extend(std_roots
[&unit
.kind
].iter().map(|unit
| UnitDep
{
149 unit_for
: UnitFor
::new_normal(),
150 extern_crate_name
: unit
.pkg
.name(),
151 // TODO: Does this `public` make sense?
157 // And also include the dependencies of the standard library itself.
158 for (unit
, deps
) in std_unit_deps
.into_iter() {
159 if let Some(other_unit
) = state
.unit_dependencies
.insert(unit
, deps
) {
160 panic
!("std unit collision with existing unit: {:?}", other_unit
);
165 /// Compute all the dependencies of the given root units.
166 /// The result is stored in state.unit_dependencies.
167 fn deps_of_roots(roots
: &[Unit
], mut state
: &mut State
<'_
, '_
>) -> CargoResult
<()> {
168 for unit
in roots
.iter() {
169 // Dependencies of tests/benches should not have `panic` set.
170 // We check the global test mode to see if we are running in `cargo
171 // test` in which case we ensure all dependencies have `panic`
172 // cleared, and avoid building the lib thrice (once with `panic`, once
173 // without, once for `--test`). In particular, the lib included for
174 // Doc tests and examples are `Build` mode here.
175 let unit_for
= if unit
.mode
.is_any_test() || state
.global_mode
.is_rustc_test() {
176 if unit
.target
.proc_macro() {
177 // Special-case for proc-macros, which are forced to for-host
178 // since they need to link with the proc_macro crate.
179 UnitFor
::new_host_test(state
.config
)
181 UnitFor
::new_test(state
.config
)
183 } else if unit
.target
.is_custom_build() {
184 // This normally doesn't happen, except `clean` aggressively
185 // generates all units.
186 UnitFor
::new_host(false)
187 } else if unit
.target
.proc_macro() {
188 UnitFor
::new_host(true)
189 } else if unit
.target
.for_host() {
190 // Plugin should never have panic set.
191 UnitFor
::new_compiler()
193 UnitFor
::new_normal()
195 deps_of(unit
, &mut state
, unit_for
)?
;
201 /// Compute the dependencies of a single unit.
202 fn deps_of(unit
: &Unit
, state
: &mut State
<'_
, '_
>, unit_for
: UnitFor
) -> CargoResult
<()> {
203 // Currently the `unit_dependencies` map does not include `unit_for`. This should
204 // be safe for now. `TestDependency` only exists to clear the `panic`
205 // flag, and you'll never ask for a `unit` with `panic` set as a
206 // `TestDependency`. `CustomBuild` should also be fine since if the
207 // requested unit's settings are the same as `Any`, `CustomBuild` can't
208 // affect anything else in the hierarchy.
209 if !state
.unit_dependencies
.contains_key(unit
) {
210 let unit_deps
= compute_deps(unit
, state
, unit_for
)?
;
213 .insert(unit
.clone(), unit_deps
.clone());
214 for unit_dep
in unit_deps
{
215 deps_of(&unit_dep
.unit
, state
, unit_dep
.unit_for
)?
;
221 /// For a package, returns all targets that are registered as dependencies
222 /// for that package.
223 /// This returns a `Vec` of `(Unit, UnitFor)` pairs. The `UnitFor`
224 /// is the profile type that should be used for dependencies of the unit.
227 state
: &mut State
<'_
, '_
>,
229 ) -> CargoResult
<Vec
<UnitDep
>> {
230 if unit
.mode
.is_run_custom_build() {
231 return compute_deps_custom_build(unit
, unit_for
, state
);
232 } else if unit
.mode
.is_doc() {
233 // Note: this does not include doc test.
234 return compute_deps_doc(unit
, state
, unit_for
);
237 let id
= unit
.pkg
.package_id();
238 let filtered_deps
= state
239 .deps(unit
, unit_for
)
241 .filter(|&(_id
, deps
)| {
242 deps
.iter().any(|dep
| {
243 // If this target is a build command, then we only want build
244 // dependencies, otherwise we want everything *other than* build
246 if unit
.target
.is_custom_build() != dep
.is_build() {
250 // If this dependency is **not** a transitive dependency, then it
251 // only applies to test/example targets.
252 if !dep
.is_transitive()
253 && !unit
.target
.is_test()
254 && !unit
.target
.is_example()
255 && !unit
.mode
.is_any_test()
260 // If we've gotten past all that, then this dependency is
266 let mut ret
= Vec
::new();
267 let mut dev_deps
= Vec
::new();
268 for (id
, deps
) in filtered_deps
{
269 let pkg
= state
.get(id
);
270 let lib
= match pkg
.targets().iter().find(|t
| t
.is_lib()) {
274 let mode
= check_or_build_mode(unit
.mode
, lib
);
275 let dep_unit_for
= unit_for
.with_dependency(unit
, lib
);
277 let start
= ret
.len();
278 if state
.config
.cli_unstable().dual_proc_macros
&& lib
.proc_macro() && !unit
.kind
.is_host()
280 let unit_dep
= new_unit_dep(state
, unit
, pkg
, lib
, dep_unit_for
, unit
.kind
, mode
)?
;
283 new_unit_dep(state
, unit
, pkg
, lib
, dep_unit_for
, CompileKind
::Host
, mode
)?
;
286 let unit_dep
= new_unit_dep(
292 unit
.kind
.for_target(lib
),
298 // If the unit added was a dev-dependency unit, then record that in the
299 // dev-dependencies array. We'll add this to
300 // `state.dev_dependency_edges` at the end and process it later in
301 // `connect_run_custom_build_deps`.
302 if deps
.iter().all(|d
| !d
.is_transitive()) {
303 for dep
in ret
[start
..].iter() {
304 dev_deps
.push((unit
.clone(), dep
.unit
.clone()));
308 state
.dev_dependency_edges
.extend(dev_deps
);
310 // If this target is a build script, then what we've collected so far is
311 // all we need. If this isn't a build script, then it depends on the
312 // build script if there is one.
313 if unit
.target
.is_custom_build() {
316 ret
.extend(dep_build_script(unit
, unit_for
, state
)?
);
318 // If this target is a binary, test, example, etc, then it depends on
319 // the library of the same package. The call to `resolve.deps` above
320 // didn't include `pkg` in the return values, so we need to special case
321 // it here and see if we need to push `(pkg, pkg_lib_target)`.
322 if unit
.target
.is_lib() && unit
.mode
!= CompileMode
::Doctest
{
325 ret
.extend(maybe_lib(unit
, state
, unit_for
)?
);
327 // If any integration tests/benches are being run, make sure that
328 // binaries are built as well.
329 if !unit
.mode
.is_check()
330 && unit
.mode
.is_any_test()
331 && (unit
.target
.is_test() || unit
.target
.is_bench())
338 // Skip binaries with required features that have not been selected.
339 match t
.required_features() {
340 Some(rf
) if t
.is_bin() => {
341 let features
= resolve_all_features(
347 rf
.iter().all(|f
| features
.contains(f
))
349 None
if t
.is_bin() => true,
359 UnitFor
::new_normal(),
360 unit
.kind
.for_target(t
),
364 .collect
::<CargoResult
<Vec
<UnitDep
>>>()?
,
371 /// Returns the dependencies needed to run a build script.
373 /// The `unit` provided must represent an execution of a build script, and
374 /// the returned set of units must all be run before `unit` is run.
375 fn compute_deps_custom_build(
378 state
: &mut State
<'_
, '_
>,
379 ) -> CargoResult
<Vec
<UnitDep
>> {
380 if let Some(links
) = unit
.pkg
.manifest().links() {
383 .script_override(links
, unit
.kind
)
386 // Overridden build scripts don't have any dependencies.
387 return Ok(Vec
::new());
390 // All dependencies of this unit should use profiles for custom builds.
391 // If this is a build script of a proc macro, make sure it uses host
393 let script_unit_for
= UnitFor
::new_host(unit_for
.is_for_host_features());
394 // When not overridden, then the dependencies to run a build script are:
396 // 1. Compiling the build script itself.
397 // 2. For each immediate dependency of our package which has a `links`
398 // key, the execution of that build script.
400 // We don't have a great way of handling (2) here right now so this is
401 // deferred until after the graph of all unit dependencies has been
403 let unit_dep
= new_unit_dep(
409 // Build scripts always compiled for the host.
416 /// Returns the dependencies necessary to document a package.
419 state
: &mut State
<'_
, '_
>,
421 ) -> CargoResult
<Vec
<UnitDep
>> {
423 .deps(unit
, unit_for
)
425 .filter(|&(_id
, deps
)| deps
.iter().any(|dep
| dep
.kind() == DepKind
::Normal
));
427 // To document a library, we depend on dependencies actually being
428 // built. If we're documenting *all* libraries, then we also depend on
429 // the documentation of the library being built.
430 let mut ret
= Vec
::new();
431 for (id
, _deps
) in deps
{
432 let dep
= state
.get(id
);
433 let lib
= match dep
.targets().iter().find(|t
| t
.is_lib()) {
437 // Rustdoc only needs rmeta files for regular dependencies.
438 // However, for plugins/proc macros, deps should be built like normal.
439 let mode
= check_or_build_mode(unit
.mode
, lib
);
440 let dep_unit_for
= unit_for
.with_dependency(unit
, lib
);
441 let lib_unit_dep
= new_unit_dep(
447 unit
.kind
.for_target(lib
),
450 ret
.push(lib_unit_dep
);
451 if let CompileMode
::Doc { deps: true }
= unit
.mode
{
452 // Document this lib as well.
453 let doc_unit_dep
= new_unit_dep(
459 unit
.kind
.for_target(lib
),
462 ret
.push(doc_unit_dep
);
466 // Be sure to build/run the build script for documented libraries.
467 ret
.extend(dep_build_script(unit
, unit_for
, state
)?
);
469 // If we document a binary/example, we need the library available.
470 if unit
.target
.is_bin() || unit
.target
.is_example() {
471 ret
.extend(maybe_lib(unit
, state
, unit_for
)?
);
478 state
: &mut State
<'_
, '_
>,
480 ) -> CargoResult
<Option
<UnitDep
>> {
484 .find(|t
| t
.is_linkable())
486 let mode
= check_or_build_mode(unit
.mode
, t
);
487 let dep_unit_for
= unit_for
.with_dependency(unit
, t
);
494 unit
.kind
.for_target(t
),
501 /// If a build script is scheduled to be run for the package specified by
502 /// `unit`, this function will return the unit to run that build script.
504 /// Overriding a build script simply means that the running of the build
505 /// script itself doesn't have any dependencies, so even in that case a unit
506 /// of work is still returned. `None` is only returned if the package has no
511 state
: &State
<'_
, '_
>,
512 ) -> CargoResult
<Option
<UnitDep
>> {
516 .find(|t
| t
.is_custom_build())
518 // The profile stored in the Unit is the profile for the thing
519 // the custom build script is running for.
520 let profile
= state
.profiles
.get_profile_run_custom_build(&unit
.profile
);
521 // UnitFor::new_host is used because we want the `host` flag set
522 // for all of our build dependencies (so they all get
523 // build-override profiles), including compiling the build.rs
526 // If `is_for_host_features` here is `false`, that means we are a
527 // build.rs script for a normal dependency and we want to set the
528 // CARGO_FEATURE_* environment variables to the features as a
531 // If `is_for_host_features` here is `true`, that means that this
532 // package is being used as a build dependency or proc-macro, and
533 // so we only want to set CARGO_FEATURE_* variables for the host
534 // side of the graph.
536 // Keep in mind that the RunCustomBuild unit and the Compile
537 // build.rs unit use the same features. This is because some
538 // people use `cfg!` and `#[cfg]` expressions to check for enabled
539 // features instead of just checking `CARGO_FEATURE_*` at runtime.
540 // In the case with the new feature resolver (decoupled host
541 // deps), and a shared dependency has different features enabled
542 // for normal vs. build, then the build.rs script will get
543 // compiled twice. I believe it is not feasible to only build it
544 // once because it would break a large number of scripts (they
545 // would think they have the wrong set of features enabled).
546 let script_unit_for
= UnitFor
::new_host(unit_for
.is_for_host_features());
547 new_unit_dep_with_profile(
554 CompileMode
::RunCustomBuild
,
561 /// Choose the correct mode for dependencies.
562 fn check_or_build_mode(mode
: CompileMode
, target
: &Target
) -> CompileMode
{
564 CompileMode
::Check { .. }
| CompileMode
::Doc { .. }
=> {
565 if target
.for_host() {
566 // Plugin and proc macro targets should be compiled like
570 // Regular dependencies should not be checked with --test.
571 // Regular dependencies of doc targets should emit rmeta only.
572 CompileMode
::Check { test: false }
575 _
=> CompileMode
::Build
,
579 /// Create a new Unit for a dependency from `parent` to `pkg` and `target`.
581 state
: &State
<'_
, '_
>,
588 ) -> CargoResult
<UnitDep
> {
589 let is_local
= pkg
.package_id().source_id().is_path() && !state
.is_std
;
590 let profile
= state
.profiles
.get_profile(
592 state
.ws
.is_member(pkg
),
597 new_unit_dep_with_profile(state
, parent
, pkg
, target
, unit_for
, kind
, mode
, profile
)
600 fn new_unit_dep_with_profile(
601 state
: &State
<'_
, '_
>,
609 ) -> CargoResult
<UnitDep
> {
610 // TODO: consider making extern_crate_name return InternedString?
611 let extern_crate_name
= InternedString
::new(&state
.resolve().extern_crate_name(
612 parent
.pkg
.package_id(),
618 .is_public_dep(parent
.pkg
.package_id(), pkg
.package_id());
619 let features_for
= unit_for
.map_to_features_for();
620 let features
= state
.activated_features(pkg
.package_id(), features_for
);
623 .intern(pkg
, target
, profile
, kind
, mode
, features
, state
.is_std
, 0);
633 /// Fill in missing dependencies for units of the `RunCustomBuild`
635 /// As mentioned above in `compute_deps_custom_build` each build script
636 /// execution has two dependencies. The first is compiling the build script
637 /// itself (already added) and the second is that all crates the package of the
638 /// build script depends on with `links` keys, their build script execution. (a
639 /// bit confusing eh?)
641 /// Here we take the entire `deps` map and add more dependencies from execution
642 /// of one build script to execution of another build script.
643 fn connect_run_custom_build_deps(state
: &mut State
<'_
, '_
>) {
644 let mut new_deps
= Vec
::new();
648 // First up build a reverse dependency map. This is a mapping of all
649 // `RunCustomBuild` known steps to the unit which depends on them. For
650 // example a library might depend on a build script, so this map will
651 // have the build script as the key and the library would be in the
653 let mut reverse_deps_map
= HashMap
::new();
654 for (unit
, deps
) in state
.unit_dependencies
.iter() {
656 if dep
.unit
.mode
== CompileMode
::RunCustomBuild
{
658 .entry(dep
.unit
.clone())
659 .or_insert_with(HashSet
::new
)
665 // Next, we take a look at all build scripts executions listed in the
666 // dependency map. Our job here is to take everything that depends on
667 // this build script (from our reverse map above) and look at the other
668 // package dependencies of these parents.
670 // If we depend on a linkable target and the build script mentions
671 // `links`, then we depend on that package's build script! Here we use
672 // `dep_build_script` to manufacture an appropriate build script unit to
677 .filter(|k
| k
.mode
== CompileMode
::RunCustomBuild
)
679 // This list of dependencies all depend on `unit`, an execution of
681 let reverse_deps
= match reverse_deps_map
.get(unit
) {
686 let to_add
= reverse_deps
688 // Get all sibling dependencies of `unit`
689 .flat_map(|reverse_dep
| {
690 state
.unit_dependencies
[reverse_dep
]
692 .map(move |a
| (reverse_dep
, a
))
694 // Only deps with `links`.
695 .filter(|(_parent
, other
)| {
696 other
.unit
.pkg
!= unit
.pkg
697 && other
.unit
.target
.is_linkable()
698 && other
.unit
.pkg
.manifest().links().is_some()
700 // Skip dependencies induced via dev-dependencies since
701 // connections between `links` and build scripts only happens
702 // via normal dependencies. Otherwise since dev-dependencies can
703 // be cyclic we could have cyclic build-script executions.
704 .filter_map(move |(parent
, other
)| {
706 .dev_dependency_edges
707 .contains(&((*parent
).clone(), other
.unit
.clone()))
714 // Get the RunCustomBuild for other lib.
715 .filter_map(|other
| {
716 state
.unit_dependencies
[&other
.unit
]
718 .find(|other_dep
| other_dep
.unit
.mode
== CompileMode
::RunCustomBuild
)
721 .collect
::<HashSet
<_
>>();
723 if !to_add
.is_empty() {
724 // (RunCustomBuild, set(other RunCustomBuild))
725 new_deps
.push((unit
.clone(), to_add
));
730 // And finally, add in all the missing dependencies!
731 for (unit
, new_deps
) in new_deps
{
740 impl<'a
, 'cfg
> State
<'a
, 'cfg
> {
741 fn resolve(&self) -> &'a Resolve
{
743 self.std_resolve
.unwrap()
749 fn features(&self) -> &'a ResolvedFeatures
{
751 self.std_features
.unwrap()
757 fn activated_features(
760 features_for
: FeaturesFor
,
761 ) -> Vec
<InternedString
> {
762 let features
= self.features();
763 features
.activated_features(pkg_id
, features_for
)
769 features_for
: FeaturesFor
,
770 dep_name
: InternedString
,
773 .is_dep_activated(pkg_id
, features_for
, dep_name
)
776 fn get(&self, id
: PackageId
) -> &'a Package
{
779 .unwrap_or_else(|_
| panic
!("expected {} to be downloaded", id
))
782 /// Returns a filtered set of dependencies for the given unit.
783 fn deps(&self, unit
: &Unit
, unit_for
: UnitFor
) -> Vec
<(PackageId
, &HashSet
<Dependency
>)> {
784 let pkg_id
= unit
.pkg
.package_id();
785 let kind
= unit
.kind
;
788 .filter(|&(_id
, deps
)| {
789 assert
!(!deps
.is_empty());
790 deps
.iter().any(|dep
| {
791 // If this dependency is only available for certain platforms,
792 // make sure we're only enabling it for that platform.
793 if !self.target_data
.dep_platform_activated(dep
, kind
) {
797 // If this is an optional dependency, and the new feature resolver
798 // did not enable it, don't include it.
799 if dep
.is_optional() {
800 let features_for
= unit_for
.map_to_features_for();
801 if !self.is_dep_activated(pkg_id
, features_for
, dep
.name_in_toml()) {