sample_subterms

Function sample_subterms 

Source
fn sample_subterms<'a, R: Rand, PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool>(
    term: &'a Term<PT>,
    step_index: StepIndex,
    path: &mut TermPath,
    selectable: bool,
    filter: &P,
    constraints: &TermConstraints,
    rand: &mut R,
    reservoir: &mut Option<(&'a Term<PT>, TracePath)>,
    visited: &mut usize,
) -> usize
Expand description

Post-order half of reservoir_sample: offers every selectable sub-term of term to the reservoir and returns term’s TermType::size.

The size is folded bottom-up so that the whole traversal stays linear in the term size: calling TermType::size at each node instead would make it quadratic.

selectable says whether this node may be picked at all. It is false under a node the constraints forbid recursing into (TermConstraints::should_recurse); the traversal still goes on below such a node, but only to fold its size.

The recursion is spelled out as an explicit stack so that deep terms cannot overflow the call stack. path is the path of term inside its recipe, maintained in place: a child index is pushed before descending and popped after, so the traversal allocates a path only when the reservoir is actually updated.