Module routing

Shape navigation guided by Selection expressions.

Routing

This module defines [RoutingFrame] and its [next_steps] method, which model how messages propagate through a multidimensional mesh based on a Selection expression.

A [RoutingFrame] represents the state of routing at a particular point in the mesh. It tracks the current coordinate (here), the remaining selection to apply (selection), the mesh layout (slice), and the current dimension of traversal (dim).

[next_steps] defines a routing-specific evaluation strategy for Selection. Unlike Selection::eval, which produces flat indices that match a selection, this method produces intermediate routing states — new frames or deferred steps to continue traversing.

Rather than returning raw frames directly, [next_steps] produces a stream of [RoutingStep]s via a callback — each representing a distinct kind of routing progression:

• [RoutingStep::Forward] indicates that routing proceeds deterministically to a new [RoutingFrame] — the next coordinate is fully determined by the current selection and frame state.

• [RoutingStep::Choice] represents a deferred decision: it returns a set of admissible indices, and the caller must select one (e.g., for load balancing or policy-based routing) before routing can proceed.

In this way, non-determinism is treated as a first-class, policy-driven aspect of the routing system — enabling inspection, customization, and future extensions without complicating the core traversal logic.

A frame is considered a delivery target if its selection is Selection::True and all dimensions have been traversed, as determined by [RoutingFrame::deliver_here]. All other frames are forwarded further using [RoutingFrame::should_route].

This design enables compositional, local, and scalable routing:

• Compositional: complex selection expressions decompose into simpler, independently evaluated sub-selections.
• Local: each frame carries exactly the state needed for its next step — no global coordination or lookahead is required.
• Scalable: routing unfolds recursively, one hop at a time, allowing for efficient traversal even in high-dimensional spaces.

This module provides the foundation for building structured, recursive routing logic over multidimensional coordinate spaces.

Structs

Choice

A deferred routing decision as contained in a RoutingStep::Choice.

RoutingFrame

RoutingFrame captures the state of a selection being evaluated: the current coordinate (here), the remaining selection to apply, the shape and layout information (slice), and the current dimension (dim).

RoutingFrameKey

Key used to deduplicate routing frames.

Enums

RoutingAction

Represents the outcome of evaluating a routing step.

RoutingStep

A RoutingStep represents a unit of progress in the routing process.

Functions

format_route

Formats a routing path as a string, showing each hop in order.

format_routing_tree

Formats a routing tree as an indented string.

print_route

print_routing_tree

Prints the routing tree for a selection over a slice.

resolve_routing

Resolves the current set of routing frames (dests) to determine whether the message should be delivered at this rank, and which routing frames should be forwarded to peer ranks.