summaryrefslogtreecommitdiff
path: root/chromium/tools/crates/gnrt/deps.rs
blob: 59724b5abaaf5eff2ececd419d9df160319b7d66 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
// Copyright 2022 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

//! Utilities to process `cargo metadata` dependency graph.

use crate::crates::{self, Epoch};
use crate::platforms::{self, Platform, PlatformSet};

use std::collections::{hash_map::Entry, HashMap, HashSet};
use std::iter;
use std::path::PathBuf;

pub use cargo_metadata::DependencyKind;
pub use semver::Version;

/// A single transitive dependency of a root crate. Includes information needed
/// for generating build files later.
#[derive(Clone, Debug)]
pub struct Package {
    /// The package name as used by cargo.
    pub package_name: String,
    /// The package version as used by cargo.
    pub version: Version,
    /// This package's dependencies. Each element cross-references another
    /// `Package` by name and version.
    pub dependencies: Vec<DepOfDep>,
    /// Same as the above, but for build script deps.
    pub build_dependencies: Vec<DepOfDep>,
    /// Same as the above, but for test deps.
    pub dev_dependencies: Vec<DepOfDep>,
    /// A package can be depended upon in different ways: as a normal
    /// dependency, just for build scripts, or just for tests. `kinds` contains
    /// an entry for each way this package is depended on.
    pub dependency_kinds: HashMap<DependencyKind, PerKindInfo>,
    /// The package's lib target, or `None` if it doesn't have one.
    pub lib_target: Option<LibTarget>,
    /// List of binaries provided by the package.
    pub bin_targets: Vec<BinTarget>,
    /// The build script's absolute path, or `None` if the package does not use
    /// one.
    pub build_script: Option<PathBuf>,
    /// The path in the dependency graph to this package. This is intended for
    /// human consumption when debugging missing packages.
    pub dependency_path: Vec<String>,
    /// Whether the source is a local path. Is `false` if cargo resolved this
    /// dependency from a registry (e.g. crates.io) or git. If `false` the
    /// package may still be locally vendored through cargo configuration (see
    /// https://doc.rust-lang.org/cargo/reference/source-replacement.html)
    pub is_local: bool,
    /// Whether this package is a member of the cargo workspace the metadata
    /// came from, as opposed to a third-party dependency.
    pub is_workspace_member: bool,
}

impl Package {
    pub fn third_party_crate_id(&self) -> crates::ChromiumVendoredCrate {
        crates::ChromiumVendoredCrate {
            name: self.package_name.clone(),
            epoch: Epoch::from_version(&self.version),
        }
    }
}

/// A dependency of a `Package`. Cross-references another `Package` entry in the
/// resolved list.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct DepOfDep {
    /// This dependency's package name as used by cargo.
    pub package_name: String,
    /// The resolved version of this dependency.
    pub version: Version,
    /// A platform constraint for this dependency, or `None` if it's used on all
    /// platforms.
    pub platform: Option<Platform>,
}

impl DepOfDep {
    pub fn third_party_crate_id(&self) -> crates::ChromiumVendoredCrate {
        crates::ChromiumVendoredCrate {
            name: self.package_name.clone(),
            epoch: Epoch::from_version(&self.version),
        }
    }
}

/// Information specific to the dependency kind: for normal, build script, or
/// test dependencies.
#[derive(Clone, Debug)]
pub struct PerKindInfo {
    /// The set of platforms this kind is needed on.
    pub platforms: PlatformSet,
    /// The resovled feature set for this kind.
    pub features: Vec<String>,
}

/// Description of a package's lib target.
#[derive(Clone, Debug)]
pub struct LibTarget {
    /// The absolute path of the lib target's `lib.rs`.
    pub root: PathBuf,
    /// The type of the lib target. This is "rlib" for normal dependencies and
    /// "proc-macro" for proc macros.
    pub lib_type: LibType,
}

/// A binary provided by a package.
#[derive(Clone, Debug)]
pub struct BinTarget {
    /// The absolute path of the binary's root source file (e.g. `main.rs`).
    pub root: PathBuf,
    /// The binary name.
    pub name: String,
}

/// The type of lib target. Only includes types supported by this tool.
#[derive(Clone, Copy, Debug)]
pub enum LibType {
    /// A normal Rust rlib library.
    Rlib,
    /// A Rust dynamic library. See
    /// https://doc.rust-lang.org/reference/linkage.html for details and the
    /// distinction between dylib and cdylib.
    Dylib,
    /// A C-compatible dynamic library. See
    /// https://doc.rust-lang.org/reference/linkage.html for details and the
    /// distinction between dylib and cdylib.
    Cdylib,
    /// A procedural macro.
    ProcMacro,
}

impl std::fmt::Display for LibType {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match *self {
            Self::Rlib => f.write_str("rlib"),
            Self::Dylib => f.write_str("dylib"),
            Self::Cdylib => f.write_str("cdylib"),
            Self::ProcMacro => f.write_str("proc-macro"),
        }
    }
}

/// Process the dependency graph in `metadata` to a flat list of transitive
/// dependencies. Each element in the result corresponds to a cargo package. A
/// package may have multiple crates, each of which corresponds to a single
/// rustc invocation: e.g. a package may have a lib crate as well as multiple
/// binary crates.
///
/// Optionally, `roots` specifies from which packages to traverse the dependency
/// graph (likely the root packages to generate build files for). This overrides
/// the usual behavior, which traverses from all workspace members and the root
/// workspace package. The package names in `roots` should still only contain
/// workspace members.
pub fn collect_dependencies(
    metadata: &cargo_metadata::Metadata,
    roots: Option<Vec<String>>,
) -> Vec<Package> {
    // The metadata is split into two parts:
    // 1. A list of packages and associated info: targets (e.g. lib, bin,
    //    tests), source path, etc. This includes all workspace members and all
    //    transitive dependencies. Deps are not filtered based on platform or
    //    features: it is the maximal set of dependencies.
    // 2. Resolved dependency graph. There is a node for each package pointing
    //    to its dependencies in each configuration (normal, build, dev), and
    //    the resolved feature set. This includes platform-specific info so one
    //    can filter based on target platform. Nodes include an ID that uniquely
    //    refers to a package in both (1) and (2).
    //
    // We need info from both parts. Traversing the graph tells us exactly which
    // crates are needed for a given configuration and platform. In the process,
    // we must collect package IDs then look up other data in (1).
    //
    // Note the difference between "packages" and "crates" as described in
    // https://doc.rust-lang.org/book/ch07-01-packages-and-crates.html

    // `metadata`'s structures are flattened into lists. Make it easy to index
    // by package ID.
    let dep_graph: MetadataGraph = build_graph(metadata);

    // `cargo metadata`'s resolved dependency graph.
    let resolved_graph: &cargo_metadata::Resolve = metadata.resolve.as_ref().unwrap();

    // The ID of the fake root package. Do not include it in the dependency list
    // since it is not actually built.
    let fake_root: &cargo_metadata::PackageId = resolved_graph.root.as_ref().unwrap();

    // `explore_node`, our recursive depth-first traversal function, needs to
    // share state between stack frames. Construct the shared state.
    let mut traversal_state = TraversalState {
        dep_graph: &dep_graph,
        root: fake_root,
        visited: HashSet::new(),
        path: Vec::new(),
        dependencies: HashMap::new(),
    };

    let traversal_roots: Vec<&cargo_metadata::PackageId> = match roots {
        Some(roots) => metadata
            .packages
            .iter()
            .filter_map(|pkg| if roots.contains(&pkg.name) { Some(&pkg.id) } else { None })
            .collect(),
        None => dep_graph.roots.clone(),
    };

    // Do a depth-first traversal of the graph to find all relevant
    // dependencies. Start from each workspace package ("chromium" and
    // additional binary members used in the build).
    for root_id in traversal_roots.iter() {
        let node_map: &HashMap<&cargo_metadata::PackageId, &cargo_metadata::Node> =
            &dep_graph.nodes;
        explore_node(&mut traversal_state, node_map.get(*root_id).unwrap());
    }

    // `traversal_state.dependencies` is the output of `explore_node`. Pull it
    // out for processing.
    let mut dependencies = traversal_state.dependencies;

    // Fill in the per-package data for each dependency.
    for (id, dep) in dependencies.iter_mut() {
        let node: &cargo_metadata::Node = traversal_state.dep_graph.nodes.get(id).unwrap();
        let package: &cargo_metadata::Package = traversal_state.dep_graph.packages.get(id).unwrap();

        dep.package_name = package.name.clone();

        // TODO(crbug.com/1291994): Resolve features independently per kind
        // and platform. This may require using the unstable unit-graph feature:
        // https://doc.rust-lang.org/cargo/reference/unstable.html#unit-graph
        for (_, mut kind_info) in dep.dependency_kinds.iter_mut() {
            kind_info.features = node.features.clone();
            // Remove "default" feature to match behavior of crates.py. Note
            // that this is technically not correct since a crate's code may
            // choose to check "default" directly, but virtually none actually
            // do this.
            //
            // TODO(crbug.com/1291994): Revisit this behavior and maybe keep
            // "default" features.
            if let Some(pos) = kind_info.features.iter().position(|x| x == "default") {
                kind_info.features.remove(pos);
            }
        }

        for target in package.targets.iter() {
            let src_root = target.src_path.clone().into_std_path_buf();
            let target_type = match target.kind.iter().find_map(|s| TargetType::from_name(s)) {
                Some(target_type) => target_type,
                // Skip other targets, such as test, example, etc.
                None => continue,
            };

            match target_type {
                TargetType::Lib(lib_type) => {
                    // There can only be one lib target.
                    assert!(
                        dep.lib_target.is_none(),
                        "found duplicate lib target:\n{:?}\n{:?}",
                        dep.lib_target,
                        target
                    );
                    dep.lib_target = Some(LibTarget { root: src_root, lib_type });
                }
                TargetType::Bin => {
                    dep.bin_targets.push(BinTarget { root: src_root, name: target.name.clone() });
                }
                TargetType::BuildScript => {
                    assert_eq!(
                        dep.build_script, None,
                        "found duplicate build script target {:?}",
                        target
                    );
                    dep.build_script = Some(src_root);
                }
            }
        }

        dep.version = package.version.clone();

        // Collect this package's list of resolved dependencies which will be
        // needed for build file generation later.
        for node_dep in iter_node_deps(node) {
            let dep_pkg = dep_graph.packages.get(node_dep.pkg).unwrap();
            let mut platform = node_dep.target;
            if let Some(p) = platform {
                assert!(platforms::matches_supported_target(&p));
                platform = platforms::filter_unsupported_platform_terms(p);
            }
            let dep_of_dep = DepOfDep {
                package_name: dep_pkg.name.clone(),
                version: dep_pkg.version.clone(),
                platform,
            };

            match node_dep.kind {
                DependencyKind::Normal => dep.dependencies.push(dep_of_dep),
                DependencyKind::Build => dep.build_dependencies.push(dep_of_dep),
                DependencyKind::Development => dep.dev_dependencies.push(dep_of_dep),
                DependencyKind::Unknown => unreachable!(),
            }
        }

        // Make sure the package comes from our vendored source. If not, report
        // the error for later.
        dep.is_local = package.source == None;

        // Determine whether it's a workspace member or third-party dependency.
        dep.is_workspace_member = dep_graph.workspace_members.contains(&package.id);
    }

    // Return a flat list of dependencies.
    dependencies.into_iter().map(|(_, v)| v).collect()
}

/// Graph traversal state shared by recursive calls of `explore_node`.
struct TraversalState<'a> {
    /// The graph from "cargo metadata", processed for indexing by package id.
    dep_graph: &'a MetadataGraph<'a>,
    /// The fake root package that we exclude from `dependencies`.
    root: &'a cargo_metadata::PackageId,
    /// Set of packages already visited by `explore_node`.
    visited: HashSet<&'a cargo_metadata::PackageId>,
    /// The path of package IDs to the current node. For human consumption.
    path: Vec<String>,
    /// The final set of dependencies.
    dependencies: HashMap<&'a cargo_metadata::PackageId, Package>,
}

/// Recursively explore a particular node in the dependency graph. Fills data in
/// `state`. The final output is in `state.dependencies`.
fn explore_node<'a>(state: &mut TraversalState<'a>, node: &'a cargo_metadata::Node) {
    // Mark the node as visited, or continue if it's already visited.
    if !state.visited.insert(&node.id) {
        return;
    }

    // Helper to insert a placeholder `Dependency` into a map. We fill in the
    // fields later.
    let init_dep = |path| Package {
        package_name: String::new(),
        version: Version::new(0, 0, 0),
        dependencies: Vec::new(),
        build_dependencies: Vec::new(),
        dev_dependencies: Vec::new(),
        dependency_kinds: HashMap::new(),
        lib_target: None,
        bin_targets: Vec::new(),
        build_script: None,
        dependency_path: path,
        is_local: false,
        is_workspace_member: false,
    };

    state.path.push(node.id.repr.clone());

    // Each node contains a list of enabled features plus a list of
    // dependencies. Each dependency has a platform filter if applicable.
    for dep_edge in iter_node_deps(node) {
        // Explore the target of this edge next. Note that we may visit the same
        // node multiple times, but this is OK since we'll skip it in the
        // recursive call.
        let target_node: &cargo_metadata::Node = state.dep_graph.nodes.get(&dep_edge.pkg).unwrap();
        explore_node(state, target_node);

        // Merge this with the existing entry for the dep.
        let dep: &mut Package =
            state.dependencies.entry(dep_edge.pkg).or_insert_with(|| init_dep(state.path.clone()));
        let info: &mut PerKindInfo = dep
            .dependency_kinds
            .entry(dep_edge.kind)
            .or_insert(PerKindInfo { platforms: PlatformSet::empty(), features: Vec::new() });
        info.platforms.add(dep_edge.target);
    }

    state.path.pop();

    // Initialize the dependency entry for this node's package if it's not our
    // fake root.
    if &node.id != state.root {
        state.dependencies.entry(&node.id).or_insert_with(|| init_dep(state.path.clone()));
    }
}

struct DependencyEdge<'a> {
    pkg: &'a cargo_metadata::PackageId,
    kind: DependencyKind,
    target: Option<Platform>,
}

/// Iterates over the dependencies of `node`, filtering out platforms we don't
/// support.
fn iter_node_deps(node: &cargo_metadata::Node) -> impl Iterator<Item = DependencyEdge<'_>> + '_ {
    node.deps
        .iter()
        .map(|node_dep| {
            // Each NodeDep has information about the package depended on, as well
            // as the kinds of dependence: as a normal, build script, or test
            // dependency. For each kind there is an optional platform filter.
            //
            // Filter out kinds for unsupported platforms while mapping the
            // dependency edges to our own type.
            node_dep.dep_kinds.iter().filter_map(|dep_kind_info| {
                // Filter if it's for a platform we don't support.
                match &dep_kind_info.target {
                    None => (),
                    Some(platform) => {
                        if !platforms::matches_supported_target(platform) {
                            return None;
                        }
                    }
                };

                Some(DependencyEdge {
                    pkg: &node_dep.pkg,
                    kind: dep_kind_info.kind,
                    target: dep_kind_info.target.clone(),
                })
            })
        })
        .flatten()
}

/// Indexable representation of the `cargo_metadata::Metadata` fields we need.
struct MetadataGraph<'a> {
    nodes: HashMap<&'a cargo_metadata::PackageId, &'a cargo_metadata::Node>,
    packages: HashMap<&'a cargo_metadata::PackageId, &'a cargo_metadata::Package>,
    workspace_members: HashSet<&'a cargo_metadata::PackageId>,
    roots: Vec<&'a cargo_metadata::PackageId>,
}

/// Convert the flat lists in `metadata` to maps indexable by PackageId.
fn build_graph<'a>(metadata: &'a cargo_metadata::Metadata) -> MetadataGraph<'a> {
    // `metadata` always has `resolve` unless cargo was explicitly asked not to
    // output the dependency graph.
    let resolve = metadata.resolve.as_ref().unwrap();
    let mut graph = HashMap::new();
    for node in resolve.nodes.iter() {
        match graph.entry(&node.id) {
            Entry::Vacant(e) => e.insert(node),
            Entry::Occupied(_) => panic!("duplicate entries in dependency graph"),
        };
    }

    let packages = metadata.packages.iter().map(|p| (&p.id, p)).collect();

    let roots = iter::once(resolve.root.as_ref().unwrap())
        .chain(metadata.workspace_members.iter())
        .collect();

    MetadataGraph {
        nodes: graph,
        packages,
        workspace_members: metadata.workspace_members.iter().collect(),
        roots,
    }
}

/// A crate target type we support.
#[derive(Clone, Copy, Debug)]
enum TargetType {
    Lib(LibType),
    Bin,
    BuildScript,
}

impl TargetType {
    fn from_name(name: &str) -> Option<Self> {
        match name {
            "lib" | "rlib" => Some(Self::Lib(LibType::Rlib)),
            "dylib" => Some(Self::Lib(LibType::Dylib)),
            "cdylib" => Some(Self::Lib(LibType::Cdylib)),
            "bin" => Some(Self::Bin),
            "custom-build" => Some(Self::BuildScript),
            "proc-macro" => Some(Self::Lib(LibType::ProcMacro)),
            _ => None,
        }
    }
}

impl std::fmt::Display for TargetType {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match *self {
            Self::Lib(typ) => typ.fmt(f),
            Self::Bin => f.write_str("bin"),
            Self::BuildScript => f.write_str("custom-build"),
        }
    }
}