Skip to content

[Tracking Challenge] Verify the safety of core::slice::rotate #773

Open

Description

@DevinWatson

Runbook Link

Challenge proposal

Proposal PR: #774

Summary

This challenge asks for a verification of in-place slice rotation in
library/core/src/slice/rotate.rs, which backs the safe, stable (and now const) methods
<[T]>::rotate_left and <[T]>::rotate_right. All of the work happens in one private unsafe
function, ptr_rotate, which picks one of three raw-pointer strategies at run time from the size of
T and the split point: a memmove through a 256-byte MaybeUninit stack buffer, the gcd (juggling)
cycle walk, and the Gries--Mills block swap.

The safety argument at every pointer operation rests on arithmetic facts that exist only as prose
comments: that the gcd walk never leaves [0, left + right), that the value computed as a side
effect of the first cycle really is the cycle count and therefore bounds the start offsets of the
remaining cycles, and that the block swaps stay inside the range while mid walks back and forth.
An off-by-one in any of them writes outside the slice that safe code handed to rotate_left, or
duplicates or loses a value of a type with a destructor. No soundness bug is known in this file; the
case for the challenge is that the argument is subtle, serves a safe API, and has no machine-checked
statement. No existing challenge lists a function of core::slice::rotate.

Scope

  • core::slice::rotate: the four unsafe functions ptr_rotate, ptr_rotate_memmove,
    ptr_rotate_gcd, ptr_rotate_swap, plus the safe const_min helper whose value the dispatcher's
    reasoning depends on.
  • Both optimize_for_size configurations: each strategy is proved under its own precondition, and in
    that configuration only the block-swap strategy runs.
  • Generic T, in particular zero-sized T, element sizes that do and do not divide the memmove
    buffer, alignments above usize, elements larger than the buffer, types with a validity invariant
    (NonZero), and types with a destructor — each of which takes a different branch somewhere in the
    file.
  • Not in scope, with the reasons on the page: rotate_left/rotate_right's panic path for a split
    larger than the length (a plain assert! before any unsafe code), the rotation-like block moves in
    core::slice::sort (they do not call this file), strategy-selection performance, and the
    core::ptr/MaybeUninit primitives themselves (Challenges 2 and 3).

What a solution must show (short form; the page is authoritative)

  • Safety contracts for all four unsafe functions stating the range stays valid for reading and
    writing, from the documented # Safety precondition; a strategy's contract may record the side
    condition under which the dispatcher really calls it.
  • Absence of UB including the early returns for zero-sized T and for left == 0 or right == 0
    and all three dispatch branches; unbounded for ptr_rotate on memmove-branch inputs and for
    ptr_rotate_memmove itself, and for every split with left + right <= B, B >= 24, for the gcd
    and block-swap strategies (the page explains why a bounded model checker cannot name the input
    arrangement of a generic T; a deductive proof for arbitrary sizes exceeds the criterion).
  • Functional correctness: after rotation the element at position j is the one previously at
    (j + left) mod (left + right); unbounded for memmove, bounded by the same B for gcd and
    block-swap, with unbounded proofs welcome.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Challenge ProposalUsed to tag a challenge proposal PR / Issue

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions