Decycle
Attribute macros for resolving circular trait obligations in Rust.
Overview
Decycle provides a single attribute macro, #[decycle], that rewrites a
module to break mutually recursive trait bounds. It lets you define types and
traits with circular dependencies that would otherwise fail to compile.
Quick Start
Add this to your Cargo.toml:
[dependencies]
decycle = "0.1.0"
Why Decycle?
Without decycle, circular trait obligations cause compilation errors. Here's
what happens when trying to create a simple calculator parser:
trait Evaluate {
fn evaluate(&self, input: &[&'static str], index: &mut usize) -> i32;
}
pub struct Expr;
pub struct Term;
impl Evaluate for Expr
where
Term: Evaluate, {
fn evaluate(&self, input: &[&'static str], index: &mut usize) -> i32 {
let left_val = Term.evaluate(input, index);
let op = input[*index];
*index += 1;
let right_val = Term.evaluate(input, index);
match op {
"+" => left_val + right_val,
"-" => left_val - right_val,
_ => left_val,
}
}
}
impl Evaluate for Term
where
Expr: Evaluate, {
fn evaluate(&self, input: &[&'static str], index: &mut usize) -> i32 {
let token = input[*index];
*index += 1;
if token == "(" {
let result = Expr.evaluate(input, index);
*index += 1; result
} else {
token.parse::<i32>().unwrap()
}
}
}
The #[decycle] macro solves this by breaking the circular dependency cycle.
Examples
Basic Circular Dependencies
This example shows how to break circular trait dependencies using #[decycle]:
# use decycle::decycle;
#[decycle]
mod calculator {
#[decycle]
pub trait Evaluate {
fn evaluate(&self, input: &[&'static str], index: &mut usize) -> i32;
}
pub struct Expr;
pub struct Term;
impl Evaluate for Expr
where
Term: Evaluate,
{
fn evaluate(&self, input: &[&'static str], index: &mut usize) -> i32 {
# let left_val = Term.evaluate(input, index);
# let op = input[*index];
# *index += 1;
# let right_val = Term.evaluate(input, index);
# match op {
# "+" => left_val + right_val,
# "-" => left_val - right_val,
# _ => left_val,
# }
}
}
impl Evaluate for Term
where
Expr: Evaluate,
{
fn evaluate(&self, input: &[&'static str], index: &mut usize) -> i32 {
# let token = input[*index];
# *index += 1;
# if token == "(" {
# let result = Expr.evaluate(input, index);
# *index += 1; # result
# } else {
# token.parse::<i32>().unwrap()
# }
}
}
}
fn main() {
use calculator::Evaluate;
let input = vec!["2", "+", "3"];
let mut index = 0;
assert_eq!(calculator::Expr.evaluate(&input, &mut index), 5);
}
Using use to mark traits
You can also annotate use items inside the module to use traits defined out of
the module:
# use decycle::decycle;
#[decycle]
trait A {
fn a(&self) -> ::core::primitive::usize;
}
#[decycle]
trait B {
fn b(&self) -> ::core::primitive::usize;
}
#[decycle]
mod cycle {
#[decycle]
use super::{A, B};
struct Left(usize);
struct Right(usize);
impl A for Left
where
Right: B,
{
fn a(&self) -> usize {
self.0 + 1
}
}
impl B for Right
where
Left: A,
{
fn b(&self) -> usize {
self.0 + 1
}
}
}
# fn main() {}
Attribute Arguments
- Module:
#[decycle::decycle(recurse_level = N, support_infinite_cycle = true|false, decycle = path)]recurse_level: expansion depth (default 10)support_infinite_cycle: enables/disable infinite cycle handling (default true)decycle: override the path used to refer to this crate
- Trait:
#[decycle::decycle(marker = path, decycle = path)]marker: marker type used for internal references (required when reported)decycle: override the path used to refer to this crate
Contributing
Contributions are welcome. Please open an issue or PR.
License
MIT
The mechanism
#[decycle] rewrites the annotated module into a set of ranked helper traits.
Each original trait gets a hidden "Ranked" version that carries an extra type
parameter representing recursion depth. Implementations are duplicated with that
rank parameter, and calls are delegated through the ranked trait for the current
depth. This breaks the direct cycle at the type level.
Smallest example (two mutually recursive traits):
# use decycle::decycle;
#[decycle]
trait A { fn a(&self) -> ::core::primitive::usize; }
#[decycle]
trait B { fn b(&self) -> ::core::primitive::usize; }
#[decycle]
mod cycle {
#[decycle]
use super::{A, B};
struct Left(usize);
struct Right(usize);
impl A for Left where Right: B { fn a(&self) -> usize { self.0 + 1 } }
impl B for Right where Left: A { fn b(&self) -> usize { self.0 + 1 } }
}
# fn main() {}
Expected expansion (simplified, with stable names):
# trait A { fn a(&self) -> usize; }
# trait B { fn b(&self) -> usize; }
mod cycle {
use super::{A, B};
struct Left(usize);
struct Right(usize);
trait ARanked<Rank> { fn a(&self) -> usize; }
trait BRanked<Rank> { fn b(&self) -> usize; }
impl<SelfT: ARanked<(((((((()),),),),),),)>> A for SelfT {
fn a(&self) -> usize { <SelfT as ARanked<(((((((()),),),),),),)>>::a(self) }
}
impl<SelfT: BRanked<(((((((()),),),),),),)>> B for SelfT {
fn b(&self) -> usize { <SelfT as BRanked<(((((((()),),),),),),)>>::b(self) }
}
impl<Rank> ARanked<(Rank,)> for Left where Right: BRanked<Rank> {
fn a(&self) -> usize { self.0 + 1 }
}
impl<Rank> BRanked<(Rank,)> for Right where Left: ARanked<Rank> {
fn b(&self) -> usize { self.0 + 1 }
}
}
# fn main() {}
When support_infinite_cycle = true (the default), decycle also emits a small
runtime shim that caches function pointers in OnceLock to allow cycles beyond
the compile-time recursion limit. When it is false, decycle stops at the
configured recurse_level and uses unimplemented! once the limit is reached.
(the runtime sim is non-zero-cost)
Coinduction
Decycle is often compared with the coinduction
crate and its documentation on docs.rs, which is
developed to solve the same problem. Coinduction’s
expands all related dependencies into a flat set, which removes
the dependency loop at the type level and lets mutually recursive bounds resolve
in one pass.
