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