Dep First Search

by Michael Clayton · 5 minute read
#programming #rust

Quiz time! Behold, a command-line program named foo. It’s got clap for arg parsing. It’s got toml for config parsing. It’s got tracing for logging.

Your job: add colors to foo’s terminal output. Consider the dependencies for a moment and choose a crate for colorizing terminal output.

[package]
name = "foo"
version = "0.1.0"
edition = "2024"

[dependencies]
clap = "4.5.51"
toml = "0.9.8"
tracing = "0.1.41"

In this scenario, anstyle is already present, and already being compiled. As a transitive dependency, it’s just a little hard to find. The other crates offered in the quiz, excellent though they are, would grow the dependency tree’s size unnecessarily, add to compilation time, add maintenance burden, add to supply chain risks, etc. Maybe you really prefer termion’s API to anstyle’s, and that’s a fine choice to make, but it’s important to be aware of the trade-off and rigorously assess new dependencies.

How, though? Digging through a sprawling dependency tree looking for crate names is awful, so I won’t suggest that. I have something a little nicer in mind.

# Introducing depfirstsearch

depfirstsearch is a tool I published earlier this year to improve Rust compilation speed by re-using crates nestled deep in your dependency tree. It’s a small command-line program that you can use to search your dependency tree, especially transitive dependencies, for crates you already have that may suit your needs.

It fits into the part of your workflow right before you add a new dependency.

# before you do this:
cargo add termion

# try this first:
depfirstsearch color

The term “color” will be compared to every crate in your dependency tree. Crate names, tags, and descriptions are searched, and a list of possible crates is printed.

$ depfirstsearch color
anstream@0.6.21  #ansi #terminal #color #strip #wincon
	IO stream adapters for writing colored text that will gracefully degrade according to your terminal's capabilities.
anstyle@1.0.13  #ansi #terminal #color #no_std
	ANSI text styling
anstyle-parse@0.2.7  #ansi #terminal #color #vte
	Parse ANSI Style Escapes
anstyle-query@1.1.5  #cli #color #no-std #terminal #ansi
	Look up colored console capabilities
anstyle-wincon@3.0.11  #ansi #terminal #color #windows
	Styling legacy Windows terminals
colorchoice@1.0.4  #cli #color #no-std #terminal #ansi
	Global override of color control

Another way to understand depfirstsearch is in comparison to better-known tools.

  • cargo-udeps: remove unused dependncies.
  • cargo-machete: remove unused dependncies.
  • cargo-shear: remove unused dependncies.
  • depfirstsearch: avoid adding duplicative dependencies.

We’ve all reflexively reached for familiar crates. Maybe our direct [dependencies] are known to us, but do you check your transitive dependencies for possibilities? It’s not easy. You could scan Cargo.lock for recognizable crate names, but there’s no metadata in there to identify suitable-but-unfamiliar crates. depfirstsearch is meant to make that easier, by searching the names and metadata of your entire dependency tree.

# Installing

cargo install depfirstsearch

I encourage you to give it a try when you think your projects need another dependency.

# Future improvements

depfirstsearch itself is not important, but I think re-using transitive dependencies is a powerful way to keep compilation fast and reduce supply chain risks, an idea worth integrating into better-known tools, like…

  • cargo udeps could absorb the behavior of depfirstsearch. It could also check the current tree not only for unused dependencies, but functionally duplicate dependencies already installed.
  • cargo add could suggest existing dependencies when adding new ones if they score similarly.
  • cargo search could have an --installed option for searching the local dependency tree instead of crates.io.