#
cargo/ops/tree/
mod.rs

    1//! Implementation of `cargo tree`.
    2
    3use self::format::Pattern;
    4use crate::core::compiler::{CompileKind, RustcTargetData};
    5use crate::core::dependency::DepKind;
    6use crate::core::resolver::{ForceAllTargets, HasDevUnits, features::CliFeatures};
    7use crate::core::{Package, PackageId, PackageIdSpec, PackageIdSpecQuery, Workspace};
    8use crate::ops::resolve::SpecsAndResolvedFeatures;
    9use crate::ops::{self, Packages};
    10use crate::util::CargoResult;
    11use crate::util::style;
    12use crate::{drop_print, drop_println};
    13use anyhow::Context as _;
    14use graph::Graph;
    15use std::collections::{HashMap, HashSet};
    16use std::str::FromStr;
    17
    18mod format;
    19mod graph;
    20
    21pub use {graph::EdgeKind, graph::Node, graph::NodeId};
    22
    23pub struct TreeOptions {
    24    pub cli_features: CliFeatures,
    25    /// The packages to display the tree for.
    26    pub packages: Packages,
    27    /// The platform to filter for.
    28    pub target: Target,
    29    /// The dependency kinds to display.
    30    pub edge_kinds: HashSet<EdgeKind>,
    31    pub invert: Vec<String>,
    32    /// The packages to prune from the display of the dependency tree.
    33    pub pkgs_to_prune: Vec<String>,
    34    /// The style of prefix for each line.
    35    pub prefix: Prefix,
    36    /// If `true`, duplicates will be repeated.
    37    /// If `false`, duplicates will be marked with `*`, and their dependencies
    38    /// won't be shown.
    39    pub no_dedupe: bool,
    40    /// If `true`, run in a special mode where it will scan for packages that
    41    /// appear with different versions, and report if any where found. Implies
    42    /// `invert`.
    43    pub duplicates: bool,
    44    /// A format string indicating how each package should be displayed.
    45    pub format: String,
    46    /// Includes features in the tree as separate nodes.
    47    pub graph_features: bool,
    48    /// Display depth of the dependency tree.
    49    /// If non-negative integer, display dependencies with that amount of max depth.
    50    /// If `workspace`, display dependencies from current workspace only.
    51    pub display_depth: DisplayDepth,
    52    /// Excludes proc-macro dependencies.
    53    pub no_proc_macro: bool,
    54    /// Include only public dependencies.
    55    pub public: bool,
    56}
    57
    58#[derive(PartialEq)]
    59pub enum Target {
    60    Host,
    61    Specific(Vec<String>),
    62    All,
    63}
    64
    65impl Target {
    66    pub fn from_cli(targets: Vec<String>) -> Target {
    67        match targets.len() {
    68            0 => Target::Host,
    69            1 if targets[0] == "all" => Target::All,
    70            _ => Target::Specific(targets),
    71        }
    72    }
    73}
    74
    75#[derive(Clone, Copy)]
    76pub enum Prefix {
    77    None,
    78    Indent,
    79    Depth,
    80}
    81
    82impl FromStr for Prefix {
    83    type Err = &'static str;
    84
    85    fn from_str(s: &str) -> Result<Prefix, &'static str> {
    86        match s {
    87            "none" => Ok(Prefix::None),
    88            "indent" => Ok(Prefix::Indent),
    89            "depth" => Ok(Prefix::Depth),
    90            _ => Err("invalid prefix"),
    91        }
    92    }
    93}
    94
    95#[derive(Clone, Copy)]
    96pub enum DisplayDepth {
    97    MaxDisplayDepth(u32),
    98    Workspace,
    99}
    100
    101impl FromStr for DisplayDepth {
    102    type Err = clap::Error;
    103
    104    fn from_str(s: &str) -> Result<Self, Self::Err> {
    105        match s {
    106            "workspace" => Ok(Self::Workspace),
    107            s => s.parse().map(Self::MaxDisplayDepth).map_err(|_| {
    108                clap::Error::raw(
    109                    clap::error::ErrorKind::ValueValidation,
    110                    format!(
    111                        "supported values for --depth are non-negative integers and `workspace`, \
    112                                but `{}` is unknown",
    113                        s
    114                    ),
    115                )
    116            }),
    117        }
    118    }
    119}
    120
    121struct Symbols {
    122    down: &'static str,
    123    tee: &'static str,
    124    ell: &'static str,
    125    right: &'static str,
    126}
    127
    128static UTF8_SYMBOLS: Symbols = Symbols {
    129    down: "│",
    130    tee: "├",
    131    ell: "└",
    132    right: "─",
    133};
    134
    135static ASCII_SYMBOLS: Symbols = Symbols {
    136    down: "|",
    137    tee: "|",
    138    ell: "`",
    139    right: "-",
    140};
    141
    142/// Entry point for the `cargo tree` command.
    143pub fn build_and_print(ws: &Workspace<'_>, opts: &TreeOptions) -> CargoResult<()> {
    144    let requested_targets = match &opts.target {
    145        Target::All | Target::Host => Vec::new(),
    146        Target::Specific(t) => t.clone(),
    147    };
    148    // TODO: Target::All is broken with -Zfeatures=itarget. To handle that properly,
    149    // `FeatureResolver` will need to be taught what "all" means.
    150    let requested_kinds = CompileKind::from_requested_targets(ws.gctx(), &requested_targets)?;
    151    let mut target_data = RustcTargetData::new(ws, &requested_kinds)?;
    152    let specs = opts.packages.to_package_id_specs(ws)?;
    153    let has_dev = if opts
    154        .edge_kinds
    155        .contains(&EdgeKind::Dep(DepKind::Development))
    156    {
    157        HasDevUnits::Yes
    158    } else {
    159        HasDevUnits::No
    160    };
    161    let force_all = if opts.target == Target::All {
    162        ForceAllTargets::Yes
    163    } else {
    164        ForceAllTargets::No
    165    };
    166    let dry_run = false;
    167    let ws_resolve = ops::resolve_ws_with_opts(
    168        ws,
    169        &mut target_data,
    170        &requested_kinds,
    171        &opts.cli_features,
    172        &specs,
    173        has_dev,
    174        force_all,
    175        dry_run,
    176    )?;
    177
    178    let package_map: HashMap<PackageId, &Package> = ws_resolve
    179        .pkg_set
    180        .packages()
    181        .map(|pkg| (pkg.package_id(), pkg))
    182        .collect();
    183
    184    for SpecsAndResolvedFeatures {
    185        specs,
    186        resolved_features,
    187    } in ws_resolve.specs_and_features
    188    {
    189        let mut graph = graph::build(
    190            ws,
    191            &ws_resolve.targeted_resolve,
    192            &resolved_features,
    193            &specs,
    194            &opts.cli_features,
    195            &target_data,
    196            &requested_kinds,
    197            package_map.clone(),
    198            opts,
    199        )?;
    200
    201        let root_specs = if opts.invert.is_empty() {
    202            specs
    203        } else {
    204            opts.invert
    205                .iter()
    206                .map(|p| PackageIdSpec::parse(p))
    207                .collect::<Result<Vec<PackageIdSpec>, _>>()?
    208        };
    209        let root_ids = ws_resolve.targeted_resolve.specs_to_ids(&root_specs)?;
    210        let root_indexes = graph.indexes_from_ids(&root_ids);
    211
    212        let root_indexes = if opts.duplicates {
    213            // `-d -p foo` will only show duplicates within foo's subtree
    214            graph = graph.from_reachable(root_indexes.as_slice());
    215            graph.find_duplicates()
    216        } else {
    217            root_indexes
    218        };
    219
    220        if !opts.invert.is_empty() || opts.duplicates {
    221            graph.invert();
    222        }
    223
    224        // Packages to prune.
    225        let pkgs_to_prune = opts
    226            .pkgs_to_prune
    227            .iter()
    228            .map(|p| PackageIdSpec::parse(p).map_err(Into::into))
    229            .map(|r| {
    230                // Provide an error message if pkgid is not within the resolved
    231                // dependencies graph.
    232                r.and_then(|spec| spec.query(ws_resolve.targeted_resolve.iter()).and(Ok(spec)))
    233            })
    234            .collect::<CargoResult<Vec<PackageIdSpec>>>()?;
    235
    236        if root_indexes.len() == 0 {
    237            ws.gctx().shell().warn(
    238                "nothing to print.\n\n\
    239            To find dependencies that require specific target platforms, \
    240            try to use option `--target all` first, and then narrow your search scope accordingly.",
    241            )?;
    242        } else {
    243            print(ws, opts, root_indexes, &pkgs_to_prune, &graph)?;
    244        }
    245    }
    246    Ok(())
    247}
    248
    249/// Prints a tree for each given root.
    250fn print(
    251    ws: &Workspace<'_>,
    252    opts: &TreeOptions,
    253    roots: Vec<NodeId>,
    254    pkgs_to_prune: &[PackageIdSpec],
    255    graph: &Graph<'_>,
    256) -> CargoResult<()> {
    257    let format = Pattern::new(&opts.format)
    258        .with_context(|| format!("tree format `{}` not valid", opts.format))?;
    259
    260    let symbols = if ws.gctx().shell().out_unicode() {
    261        &UTF8_SYMBOLS
    262    } else {
    263        &ASCII_SYMBOLS
    264    };
    265
    266    // The visited deps is used to display a (*) whenever a dep has
    267    // already been printed (ignored with --no-dedupe).
    268    let mut visited_deps = HashSet::new();
    269
    270    for (i, root_index) in roots.into_iter().enumerate() {
    271        if i != 0 {
    272            drop_println!(ws.gctx());
    273        }
    274
    275        // A stack of bools used to determine where | symbols should appear
    276        // when printing a line.
    277        let mut levels_continue = vec![];
    278        // The print stack is used to detect dependency cycles when
    279        // --no-dedupe is used. It contains a Node for each level.
    280        let mut print_stack = vec![];
    281
    282        print_node(
    283            ws,
    284            graph,
    285            root_index,
    286            &format,
    287            symbols,
    288            pkgs_to_prune,
    289            opts.prefix,
    290            opts.no_dedupe,
    291            opts.display_depth,
    292            &mut visited_deps,
    293            &mut levels_continue,
    294            &mut print_stack,
    295        )?;
    296    }
    297
    298    Ok(())
    299}
    300
    301/// Prints a package and all of its dependencies.
    302fn print_node<'a>(
    303    ws: &Workspace<'_>,
    304    graph: &'a Graph<'_>,
    305    node_index: NodeId,
    306    format: &Pattern,
    307    symbols: &Symbols,
    308    pkgs_to_prune: &[PackageIdSpec],
    309    prefix: Prefix,
    310    no_dedupe: bool,
    311    display_depth: DisplayDepth,
    312    visited_deps: &mut HashSet<NodeId>,
    313    levels_continue: &mut Vec<(anstyle::Style, bool)>,
    314    print_stack: &mut Vec<NodeId>,
    315) -> CargoResult<()> {
    316    let new = no_dedupe || visited_deps.insert(node_index);
    317
    318    match prefix {
    319        Prefix::Depth => drop_print!(ws.gctx(), "{}", levels_continue.len()),
    320        Prefix::Indent => {
    321            if let Some(((last_style, last_continues), rest)) = levels_continue.split_last() {
    322                for (style, continues) in rest {
    323                    let c = if *continues { symbols.down } else { " " };
    324                    drop_print!(ws.gctx(), "{style}{c}{style:#}   ");
    325                }
    326
    327                let c = if *last_continues {
    328                    symbols.tee
    329                } else {
    330                    symbols.ell
    331                };
    332                drop_print!(
    333                    ws.gctx(),
    334                    "{last_style}{0}{1}{1}{last_style:#} ",
    335                    c,
    336                    symbols.right
    337                );
    338            }
    339        }
    340        Prefix::None => {}
    341    }
    342
    343    let in_cycle = print_stack.contains(&node_index);
    344    // If this node does not have any outgoing edges, don't include the (*)
    345    // since there isn't really anything "deduplicated", and it generally just
    346    // adds noise.
    347    let has_deps = graph.has_outgoing_edges(node_index);
    348    let star = if (new && !in_cycle) || !has_deps {
    349        ""
    350    } else {
    351        color_print::cstr!(" <yellow,dim>(*)</>")
    352    };
    353    drop_println!(ws.gctx(), "{}{}", format.display(graph, node_index), star);
    354
    355    if !new || in_cycle {
    356        return Ok(());
    357    }
    358    print_stack.push(node_index);
    359
    360    for kind in &[
    361        EdgeKind::Dep(DepKind::Normal),
    362        EdgeKind::Dep(DepKind::Build),
    363        EdgeKind::Dep(DepKind::Development),
    364        EdgeKind::Feature,
    365    ] {
    366        print_dependencies(
    367            ws,
    368            graph,
    369            node_index,
    370            format,
    371            symbols,
    372            pkgs_to_prune,
    373            prefix,
    374            no_dedupe,
    375            display_depth,
    376            visited_deps,
    377            levels_continue,
    378            print_stack,
    379            kind,
    380        )?;
    381    }
    382    print_stack.pop();
    383
    384    Ok(())
    385}
    386
    387/// Prints all the dependencies of a package for the given dependency kind.
    388fn print_dependencies<'a>(
    389    ws: &Workspace<'_>,
    390    graph: &'a Graph<'_>,
    391    node_index: NodeId,
    392    format: &Pattern,
    393    symbols: &Symbols,
    394    pkgs_to_prune: &[PackageIdSpec],
    395    prefix: Prefix,
    396    no_dedupe: bool,
    397    display_depth: DisplayDepth,
    398    visited_deps: &mut HashSet<NodeId>,
    399    levels_continue: &mut Vec<(anstyle::Style, bool)>,
    400    print_stack: &mut Vec<NodeId>,
    401    kind: &EdgeKind,
    402) -> CargoResult<()> {
    403    let deps = graph.edges_of_kind(node_index, kind);
    404    if deps.is_empty() {
    405        return Ok(());
    406    }
    407
    408    let name = match kind {
    409        EdgeKind::Dep(DepKind::Normal) => None,
    410        EdgeKind::Dep(DepKind::Build) => Some(color_print::cstr!(
    411            "<bright-blue,bold>[build-dependencies]</>"
    412        )),
    413        EdgeKind::Dep(DepKind::Development) => Some(color_print::cstr!(
    414            "<bright-cyan,bold>[dev-dependencies]</>"
    415        )),
    416        EdgeKind::Feature => None,
    417    };
    418
    419    if let Prefix::Indent = prefix {
    420        if let Some(name) = name {
    421            for (style, continues) in &**levels_continue {
    422                let c = if *continues { symbols.down } else { " " };
    423                drop_print!(ws.gctx(), "{style}{c}{style:#}   ");
    424            }
    425
    426            drop_println!(ws.gctx(), "{name}");
    427        }
    428    }
    429
    430    let (max_display_depth, filter_non_workspace_member) = match display_depth {
    431        DisplayDepth::MaxDisplayDepth(max) => (max, false),
    432        DisplayDepth::Workspace => (u32::MAX, true),
    433    };
    434
    435    // Current level exceeds maximum display depth. Skip.
    436    if levels_continue.len() + 1 > max_display_depth as usize {
    437        return Ok(());
    438    }
    439
    440    let mut it = deps
    441        .iter()
    442        .filter(|dep| {
    443            // Filter out packages to prune.
    444            match graph.node(dep.node()) {
    445                Node::Package { package_id, .. } => {
    446                    if filter_non_workspace_member && !ws.is_member_id(*package_id) {
    447                        return false;
    448                    }
    449                    !pkgs_to_prune.iter().any(|spec| spec.matches(*package_id))
    450                }
    451                Node::Feature { .. } => true,
    452            }
    453        })
    454        .peekable();
    455
    456    while let Some(dependency) = it.next() {
    457        let style = edge_line_color(dependency.kind());
    458        levels_continue.push((style, it.peek().is_some()));
    459        print_node(
    460            ws,
    461            graph,
    462            dependency.node(),
    463            format,
    464            symbols,
    465            pkgs_to_prune,
    466            prefix,
    467            no_dedupe,
    468            display_depth,
    469            visited_deps,
    470            levels_continue,
    471            print_stack,
    472        )?;
    473        levels_continue.pop();
    474    }
    475
    476    Ok(())
    477}
    478
    479fn edge_line_color(kind: EdgeKind) -> anstyle::Style {
    480    match kind {
    481        EdgeKind::Dep(DepKind::Normal) => style::DEP_NORMAL,
    482        EdgeKind::Dep(DepKind::Build) => style::DEP_BUILD,
    483        EdgeKind::Dep(DepKind::Development) => style::DEP_DEV,
    484        EdgeKind::Feature => style::DEP_FEATURE,
    485    }
    486}