5.6 · ControlFlow: Short-Circuiting Iterator Operations

Domain 5 — Iterators and Lazy Computation Duration: ~15 minutes Library components: std::ops::ControlFlow, std::iter::Iterator::try_for_each, std::iter::Iterator::try_fold

Introduction

break and continue are keywords. They operate only in the body of a loop. When an early exit must cross a function boundary (a callback, a visitor, a fold closure), you cannot use the keywords. Then programs use improvised alternatives:

• boolean flags
• sentinel values
• Result values that are not really errors

std::ops::ControlFlow<B, C> is the solution of the standard library: break and continue as a value.

This tutorial shows:

• The ControlFlow<B, C> enum, its methods, and why it is not a Result with a different name.
• try_fold and try_for_each: iteration that can stop early and continue later.
• How ControlFlow relates to the Try mechanism behind ? (and to FromResidual, Tutorial 2.1).
• The visitor pattern: recursive traversals that the caller can stop, as the AST visitors of rustc do.
• A small convenience: is_break and is_continue are const-stable since 1.95.

The Enum: Break and Continue as Values

// The definition in std::ops. The default type of C is ().
enum ControlFlow<B, C = ()> {
    Continue(C),   // continue, with the value C (usually ())
    Break(B),      // stop now, with the reason or the result B
}

The most important design point: neither variant is an error. Result::Err means failure. ControlFlow::Break means completed early: a search found its target, a budget became full, or a rule matched. When you use the correct type, ?, logging, and the error-handling conventions keep their usual meaning.

Figure: Choosing among Option, Result, and ControlFlow

The API has methods that are similar to the methods of Result. 05_19_controlflow_basics.rs uses each of them:

// Verdict is a Copy enum from the example. Its variants are Allow and Deny.
let settled: ControlFlow<Verdict> = ControlFlow::Break(Verdict::Deny);
settled.is_break();                 // true (callable in const contexts since 1.95)
settled.break_value();              // Some(Verdict::Deny)
settled.continue_value();           // None
settled.map_break(|v| format!("verdict: {v:?}"));  // Break("verdict: Deny"): changes one side

The example has a chain of firewall rules. The usual version needs two flags: decided: bool and a verdict with a false default value. In the example, each rule returns ControlFlow<Verdict>. Thus the difference between "settled" and "undecided" moves from mutable state into the type.

try_fold: Fold That Can Stop

fold cannot stop, but try_fold can. The closure returns ControlFlow. Continue(new_acc) continues the fold. Break(payload) stops immediately with a value that gives the reason:

// record_sizes: [u64; 7] = [30, 25, 40, 20, 60, 10, 35]. FRAME_LIMIT: u64 = 100 (bytes).
// `bytes` is the accumulator: the total size of the records in the frame.
let packed = record_sizes.iter().try_fold(0_u64, |bytes, &size| {
    let next = bytes + size;
    if next > FRAME_LIMIT {
        ControlFlow::Break((bytes, size))   // frame full: the total and the next record
    } else {
        ControlFlow::Continue(next)
    }
});
// 30 + 25 + 40 = 95 is in the limit. 95 + 20 = 115 is not, so the fold stops.
assert_eq!(packed, ControlFlow::Break((95, 20)));

Compare the alternatives. A plain fold would keep a "full" flag through all the remaining items. A Result would label a full frame as an Err, and a full frame is not an error. ControlFlow states exactly what occurred: a normal, expected early exit, with the evidence.

Figure: try_fold short-circuit flow

A fold that never breaks returns Continue(final_acc). Thus the return type shows whether the fold reached the end of the items or stopped early. The result of a plain fold cannot show this difference.

Resumability and try_for_each

One feature is not well known: try_fold takes &mut self and consumes items only up to the break. The iterator stays usable, and its position is immediately after the item that caused the break. Call try_fold again, and the processing continues. 05_20_try_fold_try_for_each.rs packs a stream of records into frames of a constant size. It uses a plain loop around try_fold, so batch processing that can continue needs no more code.

One caveat is important: the closure already consumed the item that caused the break. If you need that item, put it in the Break payload (as the example does), or use a Peekable source (Tutorial 5.3).

try_for_each is the form for side effects. It is a for_each that can stop, and it returns the evidence, not only a bool:

// names: [&str; 4] = ["metrics.log", "trace.log", "core dump", "audit.log"]
let first_invalid = names.iter().try_for_each(|name| {
    // A name with a space is invalid: stop and return that name.
    if name.contains(' ') { ControlFlow::Break(*name) }
    else { ControlFlow::Continue(()) }
});
// The closure did not examine "audit.log".
assert_eq!(first_invalid, ControlFlow::Break("core dump"));

05_20_try_fold_try_for_each.rs prints:

frame 1: Break((95, 20))
frames: [95, 20, 70, 35]
first invalid name: Break("core dump")
checked sums: Err("overflow") / Ok(6)

All assertions passed.

ControlFlow and the Try Machinery

The real signature of try_fold accepts each type that implements the (unstable) Try trait. ControlFlow, Result, and Option all implement it. With Result, try_fold becomes a fallible fold. A typical example is a sum with an overflow check:

// sizes: [u64; 3] = [u64::MAX / 2, u64::MAX / 2, 3]
// checked_add returns None on overflow, and ok_or converts None to Err("overflow").
let sum: Result<u64, &str> =
    sizes.iter().try_fold(0_u64, |acc, &x| acc.checked_add(x).ok_or("overflow"));
// sum is Err("overflow"): the third addition overflows

? operates on ControlFlow too. It unwraps Continue, and it returns early on Break. The use of the Try impl is stable. Only an implementation of Try for your own types is not stable.

try_fold is also important for performance, because it is the mechanism of internal iteration. The default implementations of find, any, all, and position all call try_fold. Adapters such as Chain override it. Their version runs a tight loop for each segment and does not do the state checks of next() for each item. Tutorial 2.1 explains how Try uses residuals and what FromResidual does in ? conversions.

An override of try_fold must name Try as a bound. Thus custom iterators cannot override it on stable 1.99. You get the benefit through the iterators of the standard library.

The Visitor Pattern: Stoppable Traversals

ControlFlow is most useful in recursive traversal, where boolean flags multiply. 05_21_controlflow_visitor.rs traverses a file tree that it keeps in memory. At each file, the visitor closure decides whether to continue. ? propagates a Break through every level of recursion with one character:

// A method of `enum Node { File { name, size }, Dir { name, children: Vec<Node> } }`.
// `f` is the visitor. It returns Break(node) to stop, or Continue(()) to continue.
fn visit_files<'a, F>(&'a self, f: &mut F) -> ControlFlow<&'a Node>
where
    F: FnMut(&'a Node) -> ControlFlow<&'a Node>,
{
    match self {
        Node::File { .. } => f(self),    // a file: the visitor decides
        Node::Dir { children, .. } => {
            for child in children {
                child.visit_files(f)?;   // a Break returns from each level of the recursion
            }
            ControlFlow::Continue(())    // no file in this directory caused a Break
        }
    }
}

The example finds the first file that is larger than the limit. It also proves the early exit: the traversal never visits the files after the match. With a visitor that always returns Continue, the same method does a full traversal. One traversal implementation is sufficient for searches and for full passes.

The alternatives have disadvantages. A visitor that returns bool needs if !child.visit(f) { return false; } at each level. It also does not tell the caller where the traversal stopped. A visitor that returns Result passes the found node through Err, which gives a wrong meaning to the error path.

rustc uses the same design. The methods of rustc_ast::visit::Visitor can return ControlFlow, so an analysis can stop an AST traversal early.

05_21_controlflow_visitor.rs prints:

first oversized file: Some("video.bin")
files visited before stopping: ["README.md", "main.rs", "video.bin"]
total size (full walk): 13049

All assertions passed.

Summary

Code Examples