Reblessive

为深度递归算法分配堆内存的运行时。

将您的诅咒递归算法转换为祝福的堆内存结构，这样就不会溢出栈，无论深度如何。

这个 crate 是用来做什么的？

有一些算法类型最适合以递归算法编写。例如，递归下降解析器和树遍历解释器。这些算法通常需要跟踪复杂的状态栈，因此最适合编写为一系列相互调用的递归函数。然而，这也有一个主要的缺点：栈可能相当有限。特别是当算法的输入由外部控制时，将其作为递归算法实现可能会引起栈溢出。

这个库试图解决这个问题。它提供了一个小型的执行器，能够以栈顺序高效地分配新的 future，并在单个循环中驱动它们。使用这些执行器，您可以将您的递归算法编写为一系列 future。当函数需要调用另一个函数时，执行器会暂停当前 future 以执行新安排的 future。这允许您以仍然看起来像递归的方式实现算法，但即使递归非常深也不会耗尽栈。

示例

use std::{
    mem::MaybeUninit,
    time::{Duration, Instant},
};

use reblessive::{Stack, Stk};

async fn heavy_fibbo(ctx: &mut Stk, n: usize) -> usize {
    // An extra stack allocation to simulate a more complex function.
    let mut ballast: MaybeUninit<[u8; 1024 * 1024]> = std::mem::MaybeUninit::uninit();
    // Make sure the ballast isn't compiled out.
    std::hint::black_box(&mut ballast);

    match n {
        0 => 1,
        1 => 1,
        x => {
            ctx.run(move |ctx| heavy_fibbo(ctx, x - 1)).await
                + ctx.run(move |ctx| heavy_fibbo(ctx, x - 2)).await
        }
    }
}

fn main() {
    // Create a stack to run the function in.
    let mut stack = Stack::new();

    // run the function to completion on the stack.
    let res = stack.enter(|ctx| heavy_fibbo(ctx, 20)).finish();
    println!("result: {res}");

    assert_eq!(res, 10946);

    // Reblessive can also make any recursive function interuptable.
    let mut runner = stack.enter(|ctx| heavy_fibbo(ctx, 60));

    let start = Instant::now();
    loop {
        // run the function forward by a step.
        // If this returned Some than the function completed.
        if let Some(x) = runner.step() {
            println!("finished: {x}")
        }
        // We didn't complete the computation in time so we can just drop the runner and stop the
        // function.
        if start.elapsed() > Duration::from_secs(3) {
            println!("Timed out!");
            break;
        }
    }
}