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,
) -> usizeExpand 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.