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

Module slice.
  Module sort.
    Module shared.
      (* Trait *)
      (* Empty module 'FreezeMarker' *)
      
      Module Impl_core_slice_sort_shared_FreezeMarker_where_core_marker_Freeze_T_for_T.
        Definition Self (T : Ty.t) : Ty.t := T.
        
        Axiom Implements :
          forall (T : Ty.t),
          M.IsTraitInstance
            "core::slice::sort::shared::FreezeMarker"
            (Self T)
            (* Trait polymorphic types *) []
            (* Instance *) [].
      End Impl_core_slice_sort_shared_FreezeMarker_where_core_marker_Freeze_T_for_T.
      
      (*
      pub(crate) fn find_existing_run<T, F: FnMut(&T, &T) -> bool>(
          v: &[T],
          is_less: &mut F,
      ) -> (usize, bool) {
          let len = v.len();
          if len < 2 {
              return (len, false);
          }
      
          // SAFETY: We checked that len >= 2, so 0 and 1 are valid indices.
          // This also means that run_len < len implies run_len and run_len - 1
          // are valid indices as well.
          unsafe {
              let mut run_len = 2;
              let strictly_descending = is_less(v.get_unchecked(1), v.get_unchecked(0));
              if strictly_descending {
                  while run_len < len && is_less(v.get_unchecked(run_len), v.get_unchecked(run_len - 1)) {
                      run_len += 1;
                  }
              } else {
                  while run_len < len && !is_less(v.get_unchecked(run_len), v.get_unchecked(run_len - 1))
                  {
                      run_len += 1;
                  }
              }
              (run_len, strictly_descending)
          }
      }
      *)
      Definition find_existing_run (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
        match ε, τ, α with
        | [], [ T; F ], [ v; is_less ] =>
          ltac:(M.monadic
            (let v := M.alloc (| v |) in
            let is_less := M.alloc (| is_less |) in
            M.catch_return (|
              ltac:(M.monadic
                (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 (|
                                  BinOp.lt (| M.read (| len |), Value.Integer IntegerKind.Usize 2 |)
                                |)) in
                            let _ :=
                              M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                            M.alloc (|
                              M.never_to_any (|
                                M.read (|
                                  M.return_ (| Value.Tuple [ M.read (| len |); Value.Bool false ] |)
                                |)
                              |)
                            |)));
                        fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                      ]
                    |) in
                  let~ run_len := M.alloc (| Value.Integer IntegerKind.Usize 2 |) in
                  let~ strictly_descending :=
                    M.alloc (|
                      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.call_closure (|
                                M.get_associated_function (|
                                  Ty.apply (Ty.path "slice") [] [ T ],
                                  "get_unchecked",
                                  [ Ty.path "usize" ]
                                |),
                                [ M.read (| v |); Value.Integer IntegerKind.Usize 1 ]
                              |);
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.apply (Ty.path "slice") [] [ T ],
                                  "get_unchecked",
                                  [ Ty.path "usize" ]
                                |),
                                [ M.read (| v |); Value.Integer IntegerKind.Usize 0 ]
                              |)
                            ]
                        ]
                      |)
                    |) in
                  let~ _ :=
                    M.match_operator (|
                      M.alloc (| Value.Tuple [] |),
                      [
                        fun γ =>
                          ltac:(M.monadic
                            (let γ := M.use strictly_descending in
                            let _ :=
                              M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                            M.loop (|
                              ltac:(M.monadic
                                (M.match_operator (|
                                  M.alloc (| Value.Tuple [] |),
                                  [
                                    fun γ =>
                                      ltac:(M.monadic
                                        (let γ :=
                                          M.use
                                            (M.alloc (|
                                              LogicalOp.and (|
                                                BinOp.lt (|
                                                  M.read (| run_len |),
                                                  M.read (| len |)
                                                |),
                                                ltac:(M.monadic
                                                  (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.call_closure (|
                                                            M.get_associated_function (|
                                                              Ty.apply (Ty.path "slice") [] [ T ],
                                                              "get_unchecked",
                                                              [ Ty.path "usize" ]
                                                            |),
                                                            [ M.read (| v |); M.read (| run_len |) ]
                                                          |);
                                                          M.call_closure (|
                                                            M.get_associated_function (|
                                                              Ty.apply (Ty.path "slice") [] [ T ],
                                                              "get_unchecked",
                                                              [ Ty.path "usize" ]
                                                            |),
                                                            [
                                                              M.read (| v |);
                                                              BinOp.Wrap.sub (|
                                                                M.read (| run_len |),
                                                                Value.Integer IntegerKind.Usize 1
                                                              |)
                                                            ]
                                                          |)
                                                        ]
                                                    ]
                                                  |)))
                                              |)
                                            |)) in
                                        let _ :=
                                          M.is_constant_or_break_match (|
                                            M.read (| γ |),
                                            Value.Bool true
                                          |) in
                                        let~ _ :=
                                          let β := run_len in
                                          M.write (|
                                            β,
                                            BinOp.Wrap.add (|
                                              M.read (| β |),
                                              Value.Integer IntegerKind.Usize 1
                                            |)
                                          |) 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.loop (|
                              ltac:(M.monadic
                                (M.match_operator (|
                                  M.alloc (| Value.Tuple [] |),
                                  [
                                    fun γ =>
                                      ltac:(M.monadic
                                        (let γ :=
                                          M.use
                                            (M.alloc (|
                                              LogicalOp.and (|
                                                BinOp.lt (|
                                                  M.read (| run_len |),
                                                  M.read (| len |)
                                                |),
                                                ltac:(M.monadic
                                                  (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.call_closure (|
                                                              M.get_associated_function (|
                                                                Ty.apply (Ty.path "slice") [] [ T ],
                                                                "get_unchecked",
                                                                [ Ty.path "usize" ]
                                                              |),
                                                              [ M.read (| v |); M.read (| run_len |)
                                                              ]
                                                            |);
                                                            M.call_closure (|
                                                              M.get_associated_function (|
                                                                Ty.apply (Ty.path "slice") [] [ T ],
                                                                "get_unchecked",
                                                                [ Ty.path "usize" ]
                                                              |),
                                                              [
                                                                M.read (| v |);
                                                                BinOp.Wrap.sub (|
                                                                  M.read (| run_len |),
                                                                  Value.Integer IntegerKind.Usize 1
                                                                |)
                                                              ]
                                                            |)
                                                          ]
                                                      ]
                                                    |)
                                                  |)))
                                              |)
                                            |)) in
                                        let _ :=
                                          M.is_constant_or_break_match (|
                                            M.read (| γ |),
                                            Value.Bool true
                                          |) in
                                        let~ _ :=
                                          let β := run_len in
                                          M.write (|
                                            β,
                                            BinOp.Wrap.add (|
                                              M.read (| β |),
                                              Value.Integer IntegerKind.Usize 1
                                            |)
                                          |) 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
                  M.alloc (|
                    Value.Tuple [ M.read (| run_len |); M.read (| strictly_descending |) ]
                  |)
                |)))
            |)))
        | _, _, _ => M.impossible "wrong number of arguments"
        end.
      
      Axiom Function_find_existing_run :
        M.IsFunction "core::slice::sort::shared::find_existing_run" find_existing_run.
    End shared.
  End sort.
End slice.
