Trait mz_ore::stack::CheckedRecursion

pub trait CheckedRecursion {
    // Required method
    fn recursion_guard(&self) -> &RecursionGuard;

    // Provided methods
    fn checked_recur<F, T, E>(&self, f: F) -> Result<T, E>
       where F: FnOnce(&Self) -> Result<T, E>,
             E: From<RecursionLimitError> { ... }
    fn checked_recur_mut<F, T, E>(&mut self, f: F) -> Result<T, E>
       where F: FnOnce(&mut Self) -> Result<T, E>,
             E: From<RecursionLimitError> { ... }
}

Available on crate feature stack only.

A trait for types which support bounded recursion to prevent stack overflow.

The rather odd design of this trait allows checked recursion to be added to existing mutually recursive functions without threading an explicit depth: &mut usize parameter through each function. As long as there is an existing context structure, or if the mutually recursive functions are methods on a context structure, the RecursionGuard can be embedded inside this existing structure.

Examples

Consider a simple expression evaluator:

enum Expr {
    Var { name: String },
    Add { left: Box<Expr>, right: Box<Expr> },
}

struct Evaluator {
    vars: BTreeMap<String, i64>,
}

impl Evaluator {
    fn eval(&mut self, expr: &Expr) -> i64 {
        match expr {
            Expr::Var { name } => self.vars[name],
            Expr::Add { left, right } => self.eval(left) + self.eval(right),
        }
    }
}

Calling eval could overflow the stack and crash with a sufficiently large expr. This is the situation CheckedRecursion is designed to solve, like so:

use mz_ore::stack::{CheckedRecursion, RecursionGuard, RecursionLimitError};

struct Evaluator {
    vars: BTreeMap<String, i64>,
    recursion_guard: RecursionGuard,
}

impl Evaluator {
    fn eval(&mut self, expr: &Expr) -> Result<i64, RecursionLimitError> {
        // ADDED: call to `self.checked_recur`.
        self.checked_recur_mut(|e| match expr {
            Expr::Var { name } => Ok(e.vars[name]),
            Expr::Add { left, right } => Ok(e.eval(left)? + e.eval(right)?),
        })
    }
}

impl CheckedRecursion for Evaluator {
    fn recursion_guard(&self) -> &RecursionGuard {
        &self.recursion_guard
    }
}

Required Methods

fn recursion_guard(&self) -> &RecursionGuard

Extracts a reference to the recursion guard embedded within the type.

Provided Methods

fn checked_recur<F, T, E>(&self, f: F) -> Result<T, E>

where F: FnOnce(&Self) -> Result<T, E>, E: From<RecursionLimitError>,

Checks whether it is safe to recur and calls f if so.

If the recursion limit for the recursion guard returned by CheckedRecursion::recursion_guard has been reached, returns a RecursionLimitError. Otherwise, it will call f, possibly growing the stack if necessary.

Calls to this function must be manually inserted at any point that mutual recursion occurs.

fn checked_recur_mut<F, T, E>(&mut self, f: F) -> Result<T, E>

where F: FnOnce(&mut Self) -> Result<T, E>, E: From<RecursionLimitError>,

Like CheckedRecursion::checked_recur, but operates on a mutable reference to Self.

Object Safety

This trait is not object safe.

Implementors

impl CheckedRecursion for RecursionGuard