(* Generated by coq-of-rust *)
Require Import CoqOfRust.CoqOfRust.

Module slice.
  Module sort.
    Module stable.
      Module quicksort.
        (*
        pub fn quicksort<T, F: FnMut(&T, &T) -> bool>(
            mut v: &mut [T],
            scratch: &mut [MaybeUninit<T>],
            mut limit: u32,
            mut left_ancestor_pivot: Option<&T>,
            is_less: &mut F,
        ) {
            loop {
                let len = v.len();
        
                if len <= T::small_sort_threshold() {
                    T::small_sort(v, scratch, is_less);
                    return;
                }
        
                if limit == 0 {
                    // We have had too many bad pivots, switch to O(n log n) fallback
                    // algorithm. In our case that is driftsort in eager mode.
                    crate::slice::sort::stable::drift::sort(v, scratch, true, is_less);
                    return;
                }
                limit -= 1;
        
                let pivot_pos = choose_pivot(v, is_less);
                // SAFETY: choose_pivot promises to return a valid pivot index.
                unsafe {
                    intrinsics::assume(pivot_pos < v.len());
                }
        
                // SAFETY: We only access the temporary copy for Freeze types, otherwise
                // self-modifications via `is_less` would not be observed and this would
                // be unsound. Our temporary copy does not escape this scope.
                let pivot_copy = unsafe { ManuallyDrop::new(ptr::read(&v[pivot_pos])) };
                let pivot_ref = (!has_direct_interior_mutability::<T>()).then_some(&*pivot_copy);
        
                // We choose a pivot, and check if this pivot is equal to our left
                // ancestor. If true, we do a partition putting equal elements on the
                // left and do not recurse on it. This gives O(n log k) sorting for k
                // distinct values, a strategy borrowed from pdqsort. For types with
                // interior mutability we can't soundly create a temporary copy of the
                // ancestor pivot, and use left_partition_len == 0 as our method for
                // detecting when we re-use a pivot, which means we do at most three
                // partition operations with pivot p instead of the optimal two.
                let mut perform_equal_partition = false;
                if let Some(la_pivot) = left_ancestor_pivot {
                    perform_equal_partition = !is_less(la_pivot, &v[pivot_pos]);
                }
        
                let mut left_partition_len = 0;
                if !perform_equal_partition {
                    left_partition_len = stable_partition(v, scratch, pivot_pos, false, is_less);
                    perform_equal_partition = left_partition_len == 0;
                }
        
                if perform_equal_partition {
                    let mid_eq = stable_partition(v, scratch, pivot_pos, true, &mut |a, b| !is_less(b, a));
                    v = &mut v[mid_eq..];
                    left_ancestor_pivot = None;
                    continue;
                }
        
                // Process left side with the next loop iter, right side with recursion.
                let (left, right) = v.split_at_mut(left_partition_len);
                quicksort(right, scratch, limit, pivot_ref, is_less);
                v = left;
            }
        }
        *)
        Definition quicksort (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
          match ε, τ, α with
          | [], [ T; F ], [ v; scratch; limit; left_ancestor_pivot; is_less ] =>
            ltac:(M.monadic
              (let v := M.alloc (| v |) in
              let scratch := M.alloc (| scratch |) in
              let limit := M.alloc (| limit |) in
              let left_ancestor_pivot := M.alloc (| left_ancestor_pivot |) in
              let is_less := M.alloc (| is_less |) in
              M.catch_return (|
                ltac:(M.monadic
                  (M.never_to_any (|
                    M.read (|
                      M.loop (|
                        ltac:(M.monadic
                          (let~ len :=
                            M.alloc (|
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.apply (Ty.path "slice") [] [ T ],
                                  "len",
                                  []
                                |),
                                [ M.read (| v |) ]
                              |)
                            |) in
                          let~ _ :=
                            M.match_operator (|
                              M.alloc (| Value.Tuple [] |),
                              [
                                fun γ =>
                                  ltac:(M.monadic
                                    (let γ :=
                                      M.use
                                        (M.alloc (|
                                          BinOp.le (|
                                            M.read (| len |),
                                            M.call_closure (|
                                              M.get_trait_method (|
                                                "core::slice::sort::shared::smallsort::StableSmallSortTypeImpl",
                                                T,
                                                [],
                                                "small_sort_threshold",
                                                []
                                              |),
                                              []
                                            |)
                                          |)
                                        |)) in
                                    let _ :=
                                      M.is_constant_or_break_match (|
                                        M.read (| γ |),
                                        Value.Bool true
                                      |) in
                                    M.alloc (|
                                      M.never_to_any (|
                                        M.read (|
                                          let~ _ :=
                                            M.alloc (|
                                              M.call_closure (|
                                                M.get_trait_method (|
                                                  "core::slice::sort::shared::smallsort::StableSmallSortTypeImpl",
                                                  T,
                                                  [],
                                                  "small_sort",
                                                  [ F ]
                                                |),
                                                [
                                                  M.read (| v |);
                                                  M.read (| scratch |);
                                                  M.read (| is_less |)
                                                ]
                                              |)
                                            |) in
                                          M.return_ (| Value.Tuple [] |)
                                        |)
                                      |)
                                    |)));
                                fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                              ]
                            |) in
                          let~ _ :=
                            M.match_operator (|
                              M.alloc (| Value.Tuple [] |),
                              [
                                fun γ =>
                                  ltac:(M.monadic
                                    (let γ :=
                                      M.use
                                        (M.alloc (|
                                          BinOp.eq (|
                                            M.read (| limit |),
                                            Value.Integer IntegerKind.U32 0
                                          |)
                                        |)) in
                                    let _ :=
                                      M.is_constant_or_break_match (|
                                        M.read (| γ |),
                                        Value.Bool true
                                      |) in
                                    M.alloc (|
                                      M.never_to_any (|
                                        M.read (|
                                          let~ _ :=
                                            M.alloc (|
                                              M.call_closure (|
                                                M.get_function (|
                                                  "core::slice::sort::stable::drift::sort",
                                                  [ T; F ]
                                                |),
                                                [
                                                  M.read (| v |);
                                                  M.read (| scratch |);
                                                  Value.Bool true;
                                                  M.read (| is_less |)
                                                ]
                                              |)
                                            |) in
                                          M.return_ (| Value.Tuple [] |)
                                        |)
                                      |)
                                    |)));
                                fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                              ]
                            |) in
                          let~ _ :=
                            let β := limit in
                            M.write (|
                              β,
                              BinOp.Wrap.sub (| M.read (| β |), Value.Integer IntegerKind.U32 1 |)
                            |) in
                          let~ pivot_pos :=
                            M.alloc (|
                              M.call_closure (|
                                M.get_function (|
                                  "core::slice::sort::shared::pivot::choose_pivot",
                                  [ T; F ]
                                |),
                                [ M.read (| v |); M.read (| is_less |) ]
                              |)
                            |) in
                          let~ _ :=
                            let~ _ :=
                              M.alloc (|
                                M.call_closure (|
                                  M.get_function (| "core::intrinsics::assume", [] |),
                                  [
                                    BinOp.lt (|
                                      M.read (| pivot_pos |),
                                      M.call_closure (|
                                        M.get_associated_function (|
                                          Ty.apply (Ty.path "slice") [] [ T ],
                                          "len",
                                          []
                                        |),
                                        [ M.read (| v |) ]
                                      |)
                                    |)
                                  ]
                                |)
                              |) in
                            M.alloc (| Value.Tuple [] |) in
                          let~ pivot_copy :=
                            M.alloc (|
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.apply
                                    (Ty.path "core::mem::manually_drop::ManuallyDrop")
                                    []
                                    [ T ],
                                  "new",
                                  []
                                |),
                                [
                                  M.call_closure (|
                                    M.get_function (| "core::ptr::read", [ T ] |),
                                    [ M.SubPointer.get_array_field (| M.read (| v |), pivot_pos |) ]
                                  |)
                                ]
                              |)
                            |) in
                          let~ pivot_ref :=
                            M.alloc (|
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.path "bool",
                                  "then_some",
                                  [ Ty.apply (Ty.path "&") [] [ T ] ]
                                |),
                                [
                                  UnOp.not (|
                                    M.call_closure (|
                                      M.get_function (|
                                        "core::slice::sort::stable::quicksort::has_direct_interior_mutability",
                                        [ T ]
                                      |),
                                      []
                                    |)
                                  |);
                                  M.call_closure (|
                                    M.get_trait_method (|
                                      "core::ops::deref::Deref",
                                      Ty.apply
                                        (Ty.path "core::mem::manually_drop::ManuallyDrop")
                                        []
                                        [ T ],
                                      [],
                                      "deref",
                                      []
                                    |),
                                    [ pivot_copy ]
                                  |)
                                ]
                              |)
                            |) in
                          let~ perform_equal_partition := M.alloc (| Value.Bool false |) in
                          let~ _ :=
                            M.match_operator (|
                              M.alloc (| Value.Tuple [] |),
                              [
                                fun γ =>
                                  ltac:(M.monadic
                                    (let γ := left_ancestor_pivot in
                                    let γ0_0 :=
                                      M.SubPointer.get_struct_tuple_field (|
                                        γ,
                                        "core::option::Option::Some",
                                        0
                                      |) in
                                    let la_pivot := M.copy (| γ0_0 |) in
                                    let~ _ :=
                                      M.write (|
                                        perform_equal_partition,
                                        UnOp.not (|
                                          M.call_closure (|
                                            M.get_trait_method (|
                                              "core::ops::function::FnMut",
                                              F,
                                              [
                                                Ty.tuple
                                                  [
                                                    Ty.apply (Ty.path "&") [] [ T ];
                                                    Ty.apply (Ty.path "&") [] [ T ]
                                                  ]
                                              ],
                                              "call_mut",
                                              []
                                            |),
                                            [
                                              M.read (| is_less |);
                                              Value.Tuple
                                                [
                                                  M.read (| la_pivot |);
                                                  M.SubPointer.get_array_field (|
                                                    M.read (| v |),
                                                    pivot_pos
                                                  |)
                                                ]
                                            ]
                                          |)
                                        |)
                                      |) in
                                    M.alloc (| Value.Tuple [] |)));
                                fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                              ]
                            |) in
                          let~ left_partition_len :=
                            M.alloc (| Value.Integer IntegerKind.Usize 0 |) in
                          let~ _ :=
                            M.match_operator (|
                              M.alloc (| Value.Tuple [] |),
                              [
                                fun γ =>
                                  ltac:(M.monadic
                                    (let γ :=
                                      M.use
                                        (M.alloc (|
                                          UnOp.not (| M.read (| perform_equal_partition |) |)
                                        |)) in
                                    let _ :=
                                      M.is_constant_or_break_match (|
                                        M.read (| γ |),
                                        Value.Bool true
                                      |) in
                                    let~ _ :=
                                      M.write (|
                                        left_partition_len,
                                        M.call_closure (|
                                          M.get_function (|
                                            "core::slice::sort::stable::quicksort::stable_partition",
                                            [ T; F ]
                                          |),
                                          [
                                            M.read (| v |);
                                            M.read (| scratch |);
                                            M.read (| pivot_pos |);
                                            Value.Bool false;
                                            M.read (| is_less |)
                                          ]
                                        |)
                                      |) in
                                    let~ _ :=
                                      M.write (|
                                        perform_equal_partition,
                                        BinOp.eq (|
                                          M.read (| left_partition_len |),
                                          Value.Integer IntegerKind.Usize 0
                                        |)
                                      |) in
                                    M.alloc (| Value.Tuple [] |)));
                                fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                              ]
                            |) in
                          let~ _ :=
                            M.match_operator (|
                              M.alloc (| Value.Tuple [] |),
                              [
                                fun γ =>
                                  ltac:(M.monadic
                                    (let γ := M.use perform_equal_partition in
                                    let _ :=
                                      M.is_constant_or_break_match (|
                                        M.read (| γ |),
                                        Value.Bool true
                                      |) in
                                    M.alloc (|
                                      M.never_to_any (|
                                        M.read (|
                                          let~ mid_eq :=
                                            M.alloc (|
                                              M.call_closure (|
                                                M.get_function (|
                                                  "core::slice::sort::stable::quicksort::stable_partition",
                                                  [
                                                    T;
                                                    Ty.function
                                                      [
                                                        Ty.tuple
                                                          [
                                                            Ty.apply (Ty.path "&") [] [ T ];
                                                            Ty.apply (Ty.path "&") [] [ T ]
                                                          ]
                                                      ]
                                                      (Ty.path "bool")
                                                  ]
                                                |),
                                                [
                                                  M.read (| v |);
                                                  M.read (| scratch |);
                                                  M.read (| pivot_pos |);
                                                  Value.Bool true;
                                                  M.alloc (|
                                                    M.closure
                                                      (fun γ =>
                                                        ltac:(M.monadic
                                                          match γ with
                                                          | [ α0; α1 ] =>
                                                            ltac:(M.monadic
                                                              (M.match_operator (|
                                                                M.alloc (| α0 |),
                                                                [
                                                                  fun γ =>
                                                                    ltac:(M.monadic
                                                                      (let a := M.copy (| γ |) in
                                                                      M.match_operator (|
                                                                        M.alloc (| α1 |),
                                                                        [
                                                                          fun γ =>
                                                                            ltac:(M.monadic
                                                                              (let b :=
                                                                                M.copy (| γ |) in
                                                                              UnOp.not (|
                                                                                M.call_closure (|
                                                                                  M.get_trait_method (|
                                                                                    "core::ops::function::FnMut",
                                                                                    F,
                                                                                    [
                                                                                      Ty.tuple
                                                                                        [
                                                                                          Ty.apply
                                                                                            (Ty.path
                                                                                              "&")
                                                                                            []
                                                                                            [ T ];
                                                                                          Ty.apply
                                                                                            (Ty.path
                                                                                              "&")
                                                                                            []
                                                                                            [ T ]
                                                                                        ]
                                                                                    ],
                                                                                    "call_mut",
                                                                                    []
                                                                                  |),
                                                                                  [
                                                                                    M.read (|
                                                                                      is_less
                                                                                    |);
                                                                                    Value.Tuple
                                                                                      [
                                                                                        M.read (|
                                                                                          b
                                                                                        |);
                                                                                        M.read (|
                                                                                          a
                                                                                        |)
                                                                                      ]
                                                                                  ]
                                                                                |)
                                                                              |)))
                                                                        ]
                                                                      |)))
                                                                ]
                                                              |)))
                                                          | _ =>
                                                            M.impossible "wrong number of arguments"
                                                          end))
                                                  |)
                                                ]
                                              |)
                                            |) in
                                          let~ _ :=
                                            M.write (|
                                              v,
                                              M.call_closure (|
                                                M.get_trait_method (|
                                                  "core::ops::index::IndexMut",
                                                  Ty.apply (Ty.path "slice") [] [ T ],
                                                  [
                                                    Ty.apply
                                                      (Ty.path "core::ops::range::RangeFrom")
                                                      []
                                                      [ Ty.path "usize" ]
                                                  ],
                                                  "index_mut",
                                                  []
                                                |),
                                                [
                                                  M.read (| v |);
                                                  Value.StructRecord
                                                    "core::ops::range::RangeFrom"
                                                    [ ("start", M.read (| mid_eq |)) ]
                                                ]
                                              |)
                                            |) in
                                          let~ _ :=
                                            M.write (|
                                              left_ancestor_pivot,
                                              Value.StructTuple "core::option::Option::None" []
                                            |) in
                                          M.continue (||)
                                        |)
                                      |)
                                    |)));
                                fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                              ]
                            |) in
                          M.match_operator (|
                            M.alloc (|
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.apply (Ty.path "slice") [] [ T ],
                                  "split_at_mut",
                                  []
                                |),
                                [ M.read (| v |); M.read (| left_partition_len |) ]
                              |)
                            |),
                            [
                              fun γ =>
                                ltac:(M.monadic
                                  (let γ0_0 := M.SubPointer.get_tuple_field (| γ, 0 |) in
                                  let γ0_1 := M.SubPointer.get_tuple_field (| γ, 1 |) in
                                  let left := M.copy (| γ0_0 |) in
                                  let right := M.copy (| γ0_1 |) in
                                  let~ _ :=
                                    M.alloc (|
                                      M.call_closure (|
                                        M.get_function (|
                                          "core::slice::sort::stable::quicksort::quicksort",
                                          [ T; F ]
                                        |),
                                        [
                                          M.read (| right |);
                                          M.read (| scratch |);
                                          M.read (| limit |);
                                          M.read (| pivot_ref |);
                                          M.read (| is_less |)
                                        ]
                                      |)
                                    |) in
                                  let~ _ := M.write (| v, M.read (| left |) |) in
                                  M.alloc (| Value.Tuple [] |)))
                            ]
                          |)))
                      |)
                    |)
                  |)))
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_quicksort :
          M.IsFunction "core::slice::sort::stable::quicksort::quicksort" quicksort.
        
        (*
        fn stable_partition<T, F: FnMut(&T, &T) -> bool>(
            v: &mut [T],
            scratch: &mut [MaybeUninit<T>],
            pivot_pos: usize,
            pivot_goes_left: bool,
            is_less: &mut F,
        ) -> usize {
            let len = v.len();
        
            if intrinsics::unlikely(scratch.len() < len || pivot_pos >= len) {
                core::intrinsics::abort()
            }
        
            let v_base = v.as_ptr();
            let scratch_base = MaybeUninit::slice_as_mut_ptr(scratch);
        
            // The core idea is to write the values that compare as less-than to the left
            // side of `scratch`, while the values that compared as greater or equal than
            // `v[pivot_pos]` go to the right side of `scratch` in reverse. See
            // PartitionState for details.
        
            // SAFETY: see individual comments.
            unsafe {
                // SAFETY: we made sure the scratch has length >= len and that pivot_pos
                // is in-bounds. v and scratch are disjoint slices.
                let pivot = v_base.add(pivot_pos);
                let mut state = PartitionState::new(v_base, scratch_base, len);
        
                let mut pivot_in_scratch = ptr::null_mut();
                let mut loop_end_pos = pivot_pos;
        
                // SAFETY: this loop is equivalent to calling state.partition_one
                // exactly len times.
                loop {
                    // Ideally the outer loop won't be unrolled, to save binary size,
                    // but we do want the inner loop to be unrolled for small types, as
                    // this gave significant performance boosts in benchmarks. Unrolling
                    // through for _ in 0..UNROLL_LEN { .. } instead of manually improves
                    // compile times but has a ~10-20% performance penalty on opt-level=s.
                    if const { mem::size_of::<T>() <= 16 } {
                        const UNROLL_LEN: usize = 4;
                        let unroll_end = v_base.add(loop_end_pos.saturating_sub(UNROLL_LEN - 1));
                        while state.scan < unroll_end {
                            state.partition_one(is_less(&*state.scan, &*pivot));
                            state.partition_one(is_less(&*state.scan, &*pivot));
                            state.partition_one(is_less(&*state.scan, &*pivot));
                            state.partition_one(is_less(&*state.scan, &*pivot));
                        }
                    }
        
                    let loop_end = v_base.add(loop_end_pos);
                    while state.scan < loop_end {
                        state.partition_one(is_less(&*state.scan, &*pivot));
                    }
        
                    if loop_end_pos == len {
                        break;
                    }
        
                    // We avoid comparing pivot with itself, as this could create deadlocks for
                    // certain comparison operators. We also store its location later for later.
                    pivot_in_scratch = state.partition_one(pivot_goes_left);
        
                    loop_end_pos = len;
                }
        
                // `pivot` must be copied into its correct position again, because a
                // comparison operator might have modified it.
                if has_direct_interior_mutability::<T>() {
                    ptr::copy_nonoverlapping(pivot, pivot_in_scratch, 1);
                }
        
                // SAFETY: partition_one being called exactly len times guarantees that scratch
                // is initialized with a permuted copy of `v`, and that num_left <= v.len().
                // Copying scratch[0..num_left] and scratch[num_left..v.len()] back is thus
                // sound, as the values in scratch will never be read again, meaning our copies
                // semantically act as moves, permuting `v`.
        
                // Copy all the elements < p directly from swap to v.
                let v_base = v.as_mut_ptr();
                ptr::copy_nonoverlapping(scratch_base, v_base, state.num_left);
        
                // Copy the elements >= p in reverse order.
                for i in 0..len - state.num_left {
                    ptr::copy_nonoverlapping(
                        scratch_base.add(len - 1 - i),
                        v_base.add(state.num_left + i),
                        1,
                    );
                }
        
                state.num_left
            }
        }
        *)
        Definition stable_partition (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
          match ε, τ, α with
          | [], [ T; F ], [ v; scratch; pivot_pos; pivot_goes_left; is_less ] =>
            ltac:(M.monadic
              (let v := M.alloc (| v |) in
              let scratch := M.alloc (| scratch |) in
              let pivot_pos := M.alloc (| pivot_pos |) in
              let pivot_goes_left := M.alloc (| pivot_goes_left |) in
              let is_less := M.alloc (| is_less |) in
              M.read (|
                let~ len :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "slice") [] [ T ],
                        "len",
                        []
                      |),
                      [ M.read (| v |) ]
                    |)
                  |) in
                let~ _ :=
                  M.match_operator (|
                    M.alloc (| Value.Tuple [] |),
                    [
                      fun γ =>
                        ltac:(M.monadic
                          (let γ :=
                            M.use
                              (M.alloc (|
                                M.call_closure (|
                                  M.get_function (| "core::intrinsics::unlikely", [] |),
                                  [
                                    LogicalOp.or (|
                                      BinOp.lt (|
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply
                                              (Ty.path "slice")
                                              []
                                              [
                                                Ty.apply
                                                  (Ty.path "core::mem::maybe_uninit::MaybeUninit")
                                                  []
                                                  [ T ]
                                              ],
                                            "len",
                                            []
                                          |),
                                          [ M.read (| scratch |) ]
                                        |),
                                        M.read (| len |)
                                      |),
                                      ltac:(M.monadic
                                        (BinOp.ge (| M.read (| pivot_pos |), M.read (| len |) |)))
                                    |)
                                  ]
                                |)
                              |)) in
                          let _ :=
                            M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                          M.alloc (|
                            M.never_to_any (|
                              M.call_closure (|
                                M.get_function (| "core::intrinsics::abort", [] |),
                                []
                              |)
                            |)
                          |)));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                let~ v_base :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "slice") [] [ T ],
                        "as_ptr",
                        []
                      |),
                      [ M.read (| v |) ]
                    |)
                  |) in
                let~ scratch_base :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "core::mem::maybe_uninit::MaybeUninit") [] [ T ],
                        "slice_as_mut_ptr",
                        []
                      |),
                      [ M.read (| scratch |) ]
                    |)
                  |) in
                let~ pivot :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "*const") [] [ T ],
                        "add",
                        []
                      |),
                      [ M.read (| v_base |); M.read (| pivot_pos |) ]
                    |)
                  |) in
                let~ state :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply
                          (Ty.path "core::slice::sort::stable::quicksort::PartitionState")
                          []
                          [ T ],
                        "new",
                        []
                      |),
                      [ M.read (| v_base |); M.read (| scratch_base |); M.read (| len |) ]
                    |)
                  |) in
                let~ pivot_in_scratch :=
                  M.alloc (|
                    M.call_closure (| M.get_function (| "core::ptr::null_mut", [ T ] |), [] |)
                  |) in
                let~ loop_end_pos := M.copy (| pivot_pos |) in
                let~ _ :=
                  M.loop (|
                    ltac:(M.monadic
                      (let~ _ :=
                        M.match_operator (|
                          M.alloc (| Value.Tuple [] |),
                          [
                            fun γ =>
                              ltac:(M.monadic
                                (let γ :=
                                  M.use
                                    (M.get_constant (|
                                      "core::slice::sort::stable::quicksort::stable_partition_discriminant"
                                    |)) in
                                let _ :=
                                  M.is_constant_or_break_match (|
                                    M.read (| γ |),
                                    Value.Bool true
                                  |) in
                                let~ unroll_end :=
                                  M.alloc (|
                                    M.call_closure (|
                                      M.get_associated_function (|
                                        Ty.apply (Ty.path "*const") [] [ T ],
                                        "add",
                                        []
                                      |),
                                      [
                                        M.read (| v_base |);
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.path "usize",
                                            "saturating_sub",
                                            []
                                          |),
                                          [
                                            M.read (| loop_end_pos |);
                                            BinOp.Wrap.sub (|
                                              M.read (|
                                                M.get_constant (|
                                                  "core::slice::sort::stable::quicksort::stable_partition::UNROLL_LEN"
                                                |)
                                              |),
                                              Value.Integer IntegerKind.Usize 1
                                            |)
                                          ]
                                        |)
                                      ]
                                    |)
                                  |) in
                                M.loop (|
                                  ltac:(M.monadic
                                    (M.match_operator (|
                                      M.alloc (| Value.Tuple [] |),
                                      [
                                        fun γ =>
                                          ltac:(M.monadic
                                            (let γ :=
                                              M.use
                                                (M.alloc (|
                                                  BinOp.lt (|
                                                    M.read (|
                                                      M.SubPointer.get_struct_record_field (|
                                                        state,
                                                        "core::slice::sort::stable::quicksort::PartitionState",
                                                        "scan"
                                                      |)
                                                    |),
                                                    M.read (| unroll_end |)
                                                  |)
                                                |)) in
                                            let _ :=
                                              M.is_constant_or_break_match (|
                                                M.read (| γ |),
                                                Value.Bool true
                                              |) in
                                            let~ _ :=
                                              M.alloc (|
                                                M.call_closure (|
                                                  M.get_associated_function (|
                                                    Ty.apply
                                                      (Ty.path
                                                        "core::slice::sort::stable::quicksort::PartitionState")
                                                      []
                                                      [ T ],
                                                    "partition_one",
                                                    []
                                                  |),
                                                  [
                                                    state;
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::ops::function::FnMut",
                                                        F,
                                                        [
                                                          Ty.tuple
                                                            [
                                                              Ty.apply (Ty.path "&") [] [ T ];
                                                              Ty.apply (Ty.path "&") [] [ T ]
                                                            ]
                                                        ],
                                                        "call_mut",
                                                        []
                                                      |),
                                                      [
                                                        M.read (| is_less |);
                                                        Value.Tuple
                                                          [
                                                            M.read (|
                                                              M.SubPointer.get_struct_record_field (|
                                                                state,
                                                                "core::slice::sort::stable::quicksort::PartitionState",
                                                                "scan"
                                                              |)
                                                            |);
                                                            M.read (| pivot |)
                                                          ]
                                                      ]
                                                    |)
                                                  ]
                                                |)
                                              |) in
                                            let~ _ :=
                                              M.alloc (|
                                                M.call_closure (|
                                                  M.get_associated_function (|
                                                    Ty.apply
                                                      (Ty.path
                                                        "core::slice::sort::stable::quicksort::PartitionState")
                                                      []
                                                      [ T ],
                                                    "partition_one",
                                                    []
                                                  |),
                                                  [
                                                    state;
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::ops::function::FnMut",
                                                        F,
                                                        [
                                                          Ty.tuple
                                                            [
                                                              Ty.apply (Ty.path "&") [] [ T ];
                                                              Ty.apply (Ty.path "&") [] [ T ]
                                                            ]
                                                        ],
                                                        "call_mut",
                                                        []
                                                      |),
                                                      [
                                                        M.read (| is_less |);
                                                        Value.Tuple
                                                          [
                                                            M.read (|
                                                              M.SubPointer.get_struct_record_field (|
                                                                state,
                                                                "core::slice::sort::stable::quicksort::PartitionState",
                                                                "scan"
                                                              |)
                                                            |);
                                                            M.read (| pivot |)
                                                          ]
                                                      ]
                                                    |)
                                                  ]
                                                |)
                                              |) in
                                            let~ _ :=
                                              M.alloc (|
                                                M.call_closure (|
                                                  M.get_associated_function (|
                                                    Ty.apply
                                                      (Ty.path
                                                        "core::slice::sort::stable::quicksort::PartitionState")
                                                      []
                                                      [ T ],
                                                    "partition_one",
                                                    []
                                                  |),
                                                  [
                                                    state;
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::ops::function::FnMut",
                                                        F,
                                                        [
                                                          Ty.tuple
                                                            [
                                                              Ty.apply (Ty.path "&") [] [ T ];
                                                              Ty.apply (Ty.path "&") [] [ T ]
                                                            ]
                                                        ],
                                                        "call_mut",
                                                        []
                                                      |),
                                                      [
                                                        M.read (| is_less |);
                                                        Value.Tuple
                                                          [
                                                            M.read (|
                                                              M.SubPointer.get_struct_record_field (|
                                                                state,
                                                                "core::slice::sort::stable::quicksort::PartitionState",
                                                                "scan"
                                                              |)
                                                            |);
                                                            M.read (| pivot |)
                                                          ]
                                                      ]
                                                    |)
                                                  ]
                                                |)
                                              |) in
                                            let~ _ :=
                                              M.alloc (|
                                                M.call_closure (|
                                                  M.get_associated_function (|
                                                    Ty.apply
                                                      (Ty.path
                                                        "core::slice::sort::stable::quicksort::PartitionState")
                                                      []
                                                      [ T ],
                                                    "partition_one",
                                                    []
                                                  |),
                                                  [
                                                    state;
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::ops::function::FnMut",
                                                        F,
                                                        [
                                                          Ty.tuple
                                                            [
                                                              Ty.apply (Ty.path "&") [] [ T ];
                                                              Ty.apply (Ty.path "&") [] [ T ]
                                                            ]
                                                        ],
                                                        "call_mut",
                                                        []
                                                      |),
                                                      [
                                                        M.read (| is_less |);
                                                        Value.Tuple
                                                          [
                                                            M.read (|
                                                              M.SubPointer.get_struct_record_field (|
                                                                state,
                                                                "core::slice::sort::stable::quicksort::PartitionState",
                                                                "scan"
                                                              |)
                                                            |);
                                                            M.read (| pivot |)
                                                          ]
                                                      ]
                                                    |)
                                                  ]
                                                |)
                                              |) in
                                            M.alloc (| Value.Tuple [] |)));
                                        fun γ =>
                                          ltac:(M.monadic
                                            (M.alloc (|
                                              M.never_to_any (|
                                                M.read (|
                                                  let~ _ :=
                                                    M.alloc (|
                                                      M.never_to_any (| M.read (| M.break (||) |) |)
                                                    |) in
                                                  M.alloc (| Value.Tuple [] |)
                                                |)
                                              |)
                                            |)))
                                      ]
                                    |)))
                                |)));
                            fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                          ]
                        |) in
                      let~ loop_end :=
                        M.alloc (|
                          M.call_closure (|
                            M.get_associated_function (|
                              Ty.apply (Ty.path "*const") [] [ T ],
                              "add",
                              []
                            |),
                            [ M.read (| v_base |); M.read (| loop_end_pos |) ]
                          |)
                        |) in
                      let~ _ :=
                        M.loop (|
                          ltac:(M.monadic
                            (M.match_operator (|
                              M.alloc (| Value.Tuple [] |),
                              [
                                fun γ =>
                                  ltac:(M.monadic
                                    (let γ :=
                                      M.use
                                        (M.alloc (|
                                          BinOp.lt (|
                                            M.read (|
                                              M.SubPointer.get_struct_record_field (|
                                                state,
                                                "core::slice::sort::stable::quicksort::PartitionState",
                                                "scan"
                                              |)
                                            |),
                                            M.read (| loop_end |)
                                          |)
                                        |)) in
                                    let _ :=
                                      M.is_constant_or_break_match (|
                                        M.read (| γ |),
                                        Value.Bool true
                                      |) in
                                    let~ _ :=
                                      M.alloc (|
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply
                                              (Ty.path
                                                "core::slice::sort::stable::quicksort::PartitionState")
                                              []
                                              [ T ],
                                            "partition_one",
                                            []
                                          |),
                                          [
                                            state;
                                            M.call_closure (|
                                              M.get_trait_method (|
                                                "core::ops::function::FnMut",
                                                F,
                                                [
                                                  Ty.tuple
                                                    [
                                                      Ty.apply (Ty.path "&") [] [ T ];
                                                      Ty.apply (Ty.path "&") [] [ T ]
                                                    ]
                                                ],
                                                "call_mut",
                                                []
                                              |),
                                              [
                                                M.read (| is_less |);
                                                Value.Tuple
                                                  [
                                                    M.read (|
                                                      M.SubPointer.get_struct_record_field (|
                                                        state,
                                                        "core::slice::sort::stable::quicksort::PartitionState",
                                                        "scan"
                                                      |)
                                                    |);
                                                    M.read (| pivot |)
                                                  ]
                                              ]
                                            |)
                                          ]
                                        |)
                                      |) in
                                    M.alloc (| Value.Tuple [] |)));
                                fun γ =>
                                  ltac:(M.monadic
                                    (M.alloc (|
                                      M.never_to_any (|
                                        M.read (|
                                          let~ _ :=
                                            M.alloc (|
                                              M.never_to_any (| M.read (| M.break (||) |) |)
                                            |) in
                                          M.alloc (| Value.Tuple [] |)
                                        |)
                                      |)
                                    |)))
                              ]
                            |)))
                        |) in
                      let~ _ :=
                        M.match_operator (|
                          M.alloc (| Value.Tuple [] |),
                          [
                            fun γ =>
                              ltac:(M.monadic
                                (let γ :=
                                  M.use
                                    (M.alloc (|
                                      BinOp.eq (| M.read (| loop_end_pos |), M.read (| len |) |)
                                    |)) in
                                let _ :=
                                  M.is_constant_or_break_match (|
                                    M.read (| γ |),
                                    Value.Bool true
                                  |) in
                                M.alloc (| M.never_to_any (| M.read (| M.break (||) |) |) |)));
                            fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                          ]
                        |) in
                      let~ _ :=
                        M.write (|
                          pivot_in_scratch,
                          M.call_closure (|
                            M.get_associated_function (|
                              Ty.apply
                                (Ty.path "core::slice::sort::stable::quicksort::PartitionState")
                                []
                                [ T ],
                              "partition_one",
                              []
                            |),
                            [ state; M.read (| pivot_goes_left |) ]
                          |)
                        |) in
                      let~ _ := M.write (| loop_end_pos, M.read (| len |) |) in
                      M.alloc (| Value.Tuple [] |)))
                  |) in
                let~ _ :=
                  M.match_operator (|
                    M.alloc (| Value.Tuple [] |),
                    [
                      fun γ =>
                        ltac:(M.monadic
                          (let γ :=
                            M.use
                              (M.alloc (|
                                M.call_closure (|
                                  M.get_function (|
                                    "core::slice::sort::stable::quicksort::has_direct_interior_mutability",
                                    [ T ]
                                  |),
                                  []
                                |)
                              |)) in
                          let _ :=
                            M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                          let~ _ :=
                            M.alloc (|
                              M.call_closure (|
                                M.get_function (| "core::intrinsics::copy_nonoverlapping", [ T ] |),
                                [
                                  M.read (| pivot |);
                                  M.read (| pivot_in_scratch |);
                                  Value.Integer IntegerKind.Usize 1
                                ]
                              |)
                            |) in
                          M.alloc (| Value.Tuple [] |)));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                let~ v_base :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "slice") [] [ T ],
                        "as_mut_ptr",
                        []
                      |),
                      [ M.read (| v |) ]
                    |)
                  |) in
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_function (| "core::intrinsics::copy_nonoverlapping", [ T ] |),
                      [
                        (* MutToConstPointer *) M.pointer_coercion (M.read (| scratch_base |));
                        M.read (| v_base |);
                        M.read (|
                          M.SubPointer.get_struct_record_field (|
                            state,
                            "core::slice::sort::stable::quicksort::PartitionState",
                            "num_left"
                          |)
                        |)
                      ]
                    |)
                  |) in
                let~ _ :=
                  M.use
                    (M.match_operator (|
                      M.alloc (|
                        M.call_closure (|
                          M.get_trait_method (|
                            "core::iter::traits::collect::IntoIterator",
                            Ty.apply (Ty.path "core::ops::range::Range") [] [ Ty.path "usize" ],
                            [],
                            "into_iter",
                            []
                          |),
                          [
                            Value.StructRecord
                              "core::ops::range::Range"
                              [
                                ("start", Value.Integer IntegerKind.Usize 0);
                                ("end_",
                                  BinOp.Wrap.sub (|
                                    M.read (| len |),
                                    M.read (|
                                      M.SubPointer.get_struct_record_field (|
                                        state,
                                        "core::slice::sort::stable::quicksort::PartitionState",
                                        "num_left"
                                      |)
                                    |)
                                  |))
                              ]
                          ]
                        |)
                      |),
                      [
                        fun γ =>
                          ltac:(M.monadic
                            (let iter := M.copy (| γ |) in
                            M.loop (|
                              ltac:(M.monadic
                                (let~ _ :=
                                  M.match_operator (|
                                    M.alloc (|
                                      M.call_closure (|
                                        M.get_trait_method (|
                                          "core::iter::traits::iterator::Iterator",
                                          Ty.apply
                                            (Ty.path "core::ops::range::Range")
                                            []
                                            [ Ty.path "usize" ],
                                          [],
                                          "next",
                                          []
                                        |),
                                        [ iter ]
                                      |)
                                    |),
                                    [
                                      fun γ =>
                                        ltac:(M.monadic
                                          (let _ :=
                                            M.is_struct_tuple (|
                                              γ,
                                              "core::option::Option::None"
                                            |) in
                                          M.alloc (|
                                            M.never_to_any (| M.read (| M.break (||) |) |)
                                          |)));
                                      fun γ =>
                                        ltac:(M.monadic
                                          (let γ0_0 :=
                                            M.SubPointer.get_struct_tuple_field (|
                                              γ,
                                              "core::option::Option::Some",
                                              0
                                            |) in
                                          let i := M.copy (| γ0_0 |) in
                                          let~ _ :=
                                            M.alloc (|
                                              M.call_closure (|
                                                M.get_function (|
                                                  "core::intrinsics::copy_nonoverlapping",
                                                  [ T ]
                                                |),
                                                [
                                                  (* MutToConstPointer *)
                                                  M.pointer_coercion
                                                    (M.call_closure (|
                                                      M.get_associated_function (|
                                                        Ty.apply (Ty.path "*mut") [] [ T ],
                                                        "add",
                                                        []
                                                      |),
                                                      [
                                                        M.read (| scratch_base |);
                                                        BinOp.Wrap.sub (|
                                                          BinOp.Wrap.sub (|
                                                            M.read (| len |),
                                                            Value.Integer IntegerKind.Usize 1
                                                          |),
                                                          M.read (| i |)
                                                        |)
                                                      ]
                                                    |));
                                                  M.call_closure (|
                                                    M.get_associated_function (|
                                                      Ty.apply (Ty.path "*mut") [] [ T ],
                                                      "add",
                                                      []
                                                    |),
                                                    [
                                                      M.read (| v_base |);
                                                      BinOp.Wrap.add (|
                                                        M.read (|
                                                          M.SubPointer.get_struct_record_field (|
                                                            state,
                                                            "core::slice::sort::stable::quicksort::PartitionState",
                                                            "num_left"
                                                          |)
                                                        |),
                                                        M.read (| i |)
                                                      |)
                                                    ]
                                                  |);
                                                  Value.Integer IntegerKind.Usize 1
                                                ]
                                              |)
                                            |) in
                                          M.alloc (| Value.Tuple [] |)))
                                    ]
                                  |) in
                                M.alloc (| Value.Tuple [] |)))
                            |)))
                      ]
                    |)) in
                M.SubPointer.get_struct_record_field (|
                  state,
                  "core::slice::sort::stable::quicksort::PartitionState",
                  "num_left"
                |)
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_stable_partition :
          M.IsFunction "core::slice::sort::stable::quicksort::stable_partition" stable_partition.
        
        Module stable_partition.
          Definition value_UNROLL_LEN : Value.t :=
            M.run ltac:(M.monadic (M.alloc (| Value.Integer IntegerKind.Usize 4 |))).
        End stable_partition.
        
        (* StructRecord
          {
            name := "PartitionState";
            const_params := [];
            ty_params := [ "T" ];
            fields :=
              [
                ("scratch_base", Ty.apply (Ty.path "*mut") [] [ T ]);
                ("scan", Ty.apply (Ty.path "*const") [] [ T ]);
                ("num_left", Ty.path "usize");
                ("scratch_rev", Ty.apply (Ty.path "*mut") [] [ T ])
              ];
          } *)
        
        Module Impl_core_slice_sort_stable_quicksort_PartitionState_T.
          Definition Self (T : Ty.t) : Ty.t :=
            Ty.apply (Ty.path "core::slice::sort::stable::quicksort::PartitionState") [] [ T ].
          
          (*
              unsafe fn new(scan: *const T, scratch: *mut T, len: usize) -> Self {
                  // SAFETY: See function safety comment.
                  unsafe { Self { scratch_base: scratch, scan, num_left: 0, scratch_rev: scratch.add(len) } }
              }
          *)
          Definition new (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
            let Self : Ty.t := Self T in
            match ε, τ, α with
            | [], [], [ scan; scratch; len ] =>
              ltac:(M.monadic
                (let scan := M.alloc (| scan |) in
                let scratch := M.alloc (| scratch |) in
                let len := M.alloc (| len |) in
                Value.StructRecord
                  "core::slice::sort::stable::quicksort::PartitionState"
                  [
                    ("scratch_base", M.read (| scratch |));
                    ("scan", M.read (| scan |));
                    ("num_left", Value.Integer IntegerKind.Usize 0);
                    ("scratch_rev",
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply (Ty.path "*mut") [] [ T ],
                          "add",
                          []
                        |),
                        [ M.read (| scratch |); M.read (| len |) ]
                      |))
                  ]))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom AssociatedFunction_new :
            forall (T : Ty.t),
            M.IsAssociatedFunction (Self T) "new" (new T).
          
          (*
              unsafe fn partition_one(&mut self, towards_left: bool) -> *mut T {
                  // SAFETY: see individual comments.
                  unsafe {
                      // SAFETY: in-bounds because this function is called at most len times, and thus
                      // right now is incremented at most len - 1 times. Similarly, num_left < len and
                      // num_right < len, where num_right == i - num_left at the start of the ith
                      // iteration (zero-indexed).
                      self.scratch_rev = self.scratch_rev.sub(1);
          
                      // SAFETY: now we have scratch_rev == base + len - (i + 1). This means
                      // scratch_rev + num_left == base + len - 1 - num_right < base + len.
                      let dst_base = if towards_left { self.scratch_base } else { self.scratch_rev };
                      let dst = dst_base.add(self.num_left);
                      ptr::copy_nonoverlapping(self.scan, dst, 1);
          
                      self.num_left += towards_left as usize;
                      self.scan = self.scan.add(1);
                      dst
                  }
              }
          *)
          Definition partition_one
              (T : Ty.t)
              (ε : list Value.t)
              (τ : list Ty.t)
              (α : list Value.t)
              : M :=
            let Self : Ty.t := Self T in
            match ε, τ, α with
            | [], [], [ self; towards_left ] =>
              ltac:(M.monadic
                (let self := M.alloc (| self |) in
                let towards_left := M.alloc (| towards_left |) in
                M.read (|
                  let~ _ :=
                    M.write (|
                      M.SubPointer.get_struct_record_field (|
                        M.read (| self |),
                        "core::slice::sort::stable::quicksort::PartitionState",
                        "scratch_rev"
                      |),
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply (Ty.path "*mut") [] [ T ],
                          "sub",
                          []
                        |),
                        [
                          M.read (|
                            M.SubPointer.get_struct_record_field (|
                              M.read (| self |),
                              "core::slice::sort::stable::quicksort::PartitionState",
                              "scratch_rev"
                            |)
                          |);
                          Value.Integer IntegerKind.Usize 1
                        ]
                      |)
                    |) in
                  let~ dst_base :=
                    M.copy (|
                      M.match_operator (|
                        M.alloc (| Value.Tuple [] |),
                        [
                          fun γ =>
                            ltac:(M.monadic
                              (let γ := M.use towards_left in
                              let _ :=
                                M.is_constant_or_break_match (|
                                  M.read (| γ |),
                                  Value.Bool true
                                |) in
                              M.SubPointer.get_struct_record_field (|
                                M.read (| self |),
                                "core::slice::sort::stable::quicksort::PartitionState",
                                "scratch_base"
                              |)));
                          fun γ =>
                            ltac:(M.monadic
                              (M.SubPointer.get_struct_record_field (|
                                M.read (| self |),
                                "core::slice::sort::stable::quicksort::PartitionState",
                                "scratch_rev"
                              |)))
                        ]
                      |)
                    |) in
                  let~ dst :=
                    M.alloc (|
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply (Ty.path "*mut") [] [ T ],
                          "add",
                          []
                        |),
                        [
                          M.read (| dst_base |);
                          M.read (|
                            M.SubPointer.get_struct_record_field (|
                              M.read (| self |),
                              "core::slice::sort::stable::quicksort::PartitionState",
                              "num_left"
                            |)
                          |)
                        ]
                      |)
                    |) in
                  let~ _ :=
                    M.alloc (|
                      M.call_closure (|
                        M.get_function (| "core::intrinsics::copy_nonoverlapping", [ T ] |),
                        [
                          M.read (|
                            M.SubPointer.get_struct_record_field (|
                              M.read (| self |),
                              "core::slice::sort::stable::quicksort::PartitionState",
                              "scan"
                            |)
                          |);
                          M.read (| dst |);
                          Value.Integer IntegerKind.Usize 1
                        ]
                      |)
                    |) in
                  let~ _ :=
                    let β :=
                      M.SubPointer.get_struct_record_field (|
                        M.read (| self |),
                        "core::slice::sort::stable::quicksort::PartitionState",
                        "num_left"
                      |) in
                    M.write (|
                      β,
                      BinOp.Wrap.add (| M.read (| β |), M.rust_cast (M.read (| towards_left |)) |)
                    |) in
                  let~ _ :=
                    M.write (|
                      M.SubPointer.get_struct_record_field (|
                        M.read (| self |),
                        "core::slice::sort::stable::quicksort::PartitionState",
                        "scan"
                      |),
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply (Ty.path "*const") [] [ T ],
                          "add",
                          []
                        |),
                        [
                          M.read (|
                            M.SubPointer.get_struct_record_field (|
                              M.read (| self |),
                              "core::slice::sort::stable::quicksort::PartitionState",
                              "scan"
                            |)
                          |);
                          Value.Integer IntegerKind.Usize 1
                        ]
                      |)
                    |) in
                  dst
                |)))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom AssociatedFunction_partition_one :
            forall (T : Ty.t),
            M.IsAssociatedFunction (Self T) "partition_one" (partition_one T).
        End Impl_core_slice_sort_stable_quicksort_PartitionState_T.
        
        (* Trait *)
        (* Empty module 'IsFreeze' *)
        
        Module Impl_core_slice_sort_stable_quicksort_IsFreeze_for_T.
          Definition Self (T : Ty.t) : Ty.t := T.
          
          (*
              default fn is_freeze() -> bool {
                  false
              }
          *)
          Definition is_freeze
              (T : Ty.t)
              (ε : list Value.t)
              (τ : list Ty.t)
              (α : list Value.t)
              : M :=
            let Self : Ty.t := Self T in
            match ε, τ, α with
            | [], [], [] => ltac:(M.monadic (Value.Bool false))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom Implements :
            forall (T : Ty.t),
            M.IsTraitInstance
              "core::slice::sort::stable::quicksort::IsFreeze"
              (Self T)
              (* Trait polymorphic types *) []
              (* Instance *) [ ("is_freeze", InstanceField.Method (is_freeze T)) ].
        End Impl_core_slice_sort_stable_quicksort_IsFreeze_for_T.
        
        Module Impl_core_slice_sort_stable_quicksort_IsFreeze_where_core_slice_sort_shared_FreezeMarker_T_for_T.
          Definition Self (T : Ty.t) : Ty.t := T.
          
          (*
              fn is_freeze() -> bool {
                  true
              }
          *)
          Definition is_freeze
              (T : Ty.t)
              (ε : list Value.t)
              (τ : list Ty.t)
              (α : list Value.t)
              : M :=
            let Self : Ty.t := Self T in
            match ε, τ, α with
            | [], [], [] => ltac:(M.monadic (Value.Bool true))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom Implements :
            forall (T : Ty.t),
            M.IsTraitInstance
              "core::slice::sort::stable::quicksort::IsFreeze"
              (Self T)
              (* Trait polymorphic types *) []
              (* Instance *) [ ("is_freeze", InstanceField.Method (is_freeze T)) ].
        End Impl_core_slice_sort_stable_quicksort_IsFreeze_where_core_slice_sort_shared_FreezeMarker_T_for_T.
        
        (*
        fn has_direct_interior_mutability<T>() -> bool {
            // If a type has interior mutability it may alter itself during comparison
            // in a way that must be preserved after the sort operation concludes.
            // Otherwise a type like Mutex<Option<Box<str>>> could lead to double free.
            !T::is_freeze()
        }
        *)
        Definition has_direct_interior_mutability
            (ε : list Value.t)
            (τ : list Ty.t)
            (α : list Value.t)
            : M :=
          match ε, τ, α with
          | [], [ T ], [] =>
            ltac:(M.monadic
              (UnOp.not (|
                M.call_closure (|
                  M.get_trait_method (|
                    "core::slice::sort::stable::quicksort::IsFreeze",
                    T,
                    [],
                    "is_freeze",
                    []
                  |),
                  []
                |)
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_has_direct_interior_mutability :
          M.IsFunction
            "core::slice::sort::stable::quicksort::has_direct_interior_mutability"
            has_direct_interior_mutability.
      End quicksort.
    End stable.
  End sort.
End slice.
