rust

In traditional low level languages such as C iteration is implemented manually, with users writing out for (int idx = 0; idx < items_len; ++idx) { do_thing(items[idx] } , every time they want to iterate over a list. Newer languages like Rust provide abstractions - iterators - that separate the machinery of recursion from the logic: for item in items.iter() { do_thing(item) } .

The recursion crate does the same thing for recursive data structures. This post is an introduction to the new version of the recursion crate, but you don’t have to read my earlier posts to understand it.

This is the third post in a three-post series. In the first post we developed a stack-safe, ergonomic, and concise method for working with recursive data structures (using a simple expression language as an example). In the second post we made it fully generic, providing a set of generic tools for expanding and collapsing any recursive data structure in Rust.

In this post we will see how to combine these two things - expanding a structure and collapsing it at the same time, performing both operations in a single pass. In the process, we will gain the ability to write arbitrary recursive functions over traditional boxed-pointer recursive structures (instead of the novel RecursiveTree type introduced in my previous post) while retaining stack safety.

Previously, we introduced a method for writing performant stack safe recursion in Rust for a single recursive data structure. This post uses the same ideas to implement a single recursion backend that can collapse or expand any recursive data structure.

This is a post about writing elegant and performant recursive algorithms in Rust. It makes heavy use of a pattern from Haskell called recursion schemes, but you don’t need to know anything about that; it’s just an implementation detail. Instead, as motivation, I have benchmarks showing a 14-34% improvement over the typical boxed pointer representation of recursive data structures in Rust.

Querying Cargo Dependency DAGs with Guppy

guppy is a rust crate that provides tools for working with cargo dependency graphs using the petgraph graph data structure crate. It’s used by Facebook to audit a high-security subset of the cargo dependency graph for some of their more high-visibility projects. Treating the dependency graph resulting from a cargo build operation as a DAG lets us draw on the well-studied field of graph algorithms to answer complex questions about our build without resorting to ad-hoc traversals or re-implementation of common graph primitives.

For my first project using guppy, I decided to build a tool to produce machine-readable summaries describing why some target dependency is included in a cargo workspace’s build graph. My motivation was to support projects that are migrating from futures 0.1 to futures 0.3. Many rust projects started using futures 0.1 for their initial async implementation, and are still in the process of switching over to futures 0.3. If you’re interested in learning more about the differences between the two packages, this blog post by ncameron is a great resource. Being able to easily generate machine-readable reports opens up new possibilities - for example, you could use the output of this tool to build a linter that asserts that no new transitive dependencies on futures 0.1 are introduced into a workspace, to provide tooling-backed assurances that usage of futures 0.1 only ever decreases.