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