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

Module slice.
  Module hack.
    (*
        pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> {
            unsafe {
                let len = b.len();
                let (b, alloc) = Box::into_raw_with_allocator(b);
                Vec::from_raw_parts_in(b as *mut T, len, len, alloc)
            }
        }
    *)
    Definition into_vec (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      match ε, τ, α with
      | [], [ T; A ], [ b ] =>
        ltac:(M.monadic
          (let b := M.alloc (| b |) in
          M.read (|
            let~ len :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (| Ty.apply (Ty.path "slice") [] [ T ], "len", [] |),
                  [ M.read (| b |) ]
                |)
              |) in
            M.match_operator (|
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply
                      (Ty.path "alloc::boxed::Box")
                      []
                      [ Ty.apply (Ty.path "slice") [] [ T ]; A ],
                    "into_raw_with_allocator",
                    []
                  |),
                  [ M.read (| b |) ]
                |)
              |),
              [
                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 b := M.copy (| γ0_0 |) in
                    let alloc := M.copy (| γ0_1 |) in
                    M.alloc (|
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                          "from_raw_parts_in",
                          []
                        |),
                        [
                          M.rust_cast (M.read (| b |));
                          M.read (| len |);
                          M.read (| len |);
                          M.read (| alloc |)
                        ]
                      |)
                    |)))
              ]
            |)
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Function_into_vec : M.IsFunction "alloc::slice::hack::into_vec" into_vec.
    
    (*
        pub fn to_vec<T: ConvertVec, A: Allocator>(s: &[T], alloc: A) -> Vec<T, A> {
            T::to_vec(s, alloc)
        }
    *)
    Definition to_vec (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      match ε, τ, α with
      | [], [ T; A ], [ s; alloc ] =>
        ltac:(M.monadic
          (let s := M.alloc (| s |) in
          let alloc := M.alloc (| alloc |) in
          M.call_closure (|
            M.get_trait_method (| "alloc::slice::hack::ConvertVec", T, [], "to_vec", [ A ] |),
            [ M.read (| s |); M.read (| alloc |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Function_to_vec : M.IsFunction "alloc::slice::hack::to_vec" to_vec.
    
    (* Trait *)
    (* Empty module 'ConvertVec' *)
    
    Module Impl_alloc_slice_hack_ConvertVec_where_core_clone_Clone_T_for_T.
      Definition Self (T : Ty.t) : Ty.t := T.
      
      (*
              default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
                  struct DropGuard<'a, T, A: Allocator> {
                      vec: &'a mut Vec<T, A>,
                      num_init: usize,
                  }
                  impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
                      #[inline]
                      fn drop(&mut self) {
                          // SAFETY:
                          // items were marked initialized in the loop below
                          unsafe {
                              self.vec.set_len(self.num_init);
                          }
                      }
                  }
                  let mut vec = Vec::with_capacity_in(s.len(), alloc);
                  let mut guard = DropGuard { vec: &mut vec, num_init: 0 };
                  let slots = guard.vec.spare_capacity_mut();
                  // .take(slots.len()) is necessary for LLVM to remove bounds checks
                  // and has better codegen than zip.
                  for (i, b) in s.iter().enumerate().take(slots.len()) {
                      guard.num_init = i;
                      slots[i].write(b.clone());
                  }
                  core::mem::forget(guard);
                  // SAFETY:
                  // the vec was allocated and initialized above to at least this length.
                  unsafe {
                      vec.set_len(s.len());
                  }
                  vec
              }
      *)
      Definition to_vec (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
        let Self : Ty.t := Self T in
        match ε, τ, α with
        | [], [ A ], [ s; alloc ] =>
          ltac:(M.monadic
            (let s := M.alloc (| s |) in
            let alloc := M.alloc (| alloc |) in
            M.read (|
              let~ vec :=
                M.alloc (|
                  M.call_closure (|
                    M.get_associated_function (|
                      Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                      "with_capacity_in",
                      []
                    |),
                    [
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply (Ty.path "slice") [] [ T ],
                          "len",
                          []
                        |),
                        [ M.read (| s |) ]
                      |);
                      M.read (| alloc |)
                    ]
                  |)
                |) in
              let~ guard :=
                M.alloc (|
                  Value.StructRecord
                    "alloc::slice::hack::to_vec::DropGuard"
                    [ ("vec", vec); ("num_init", Value.Integer IntegerKind.Usize 0) ]
                |) in
              let~ slots :=
                M.alloc (|
                  M.call_closure (|
                    M.get_associated_function (|
                      Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                      "spare_capacity_mut",
                      []
                    |),
                    [
                      M.read (|
                        M.SubPointer.get_struct_record_field (|
                          guard,
                          "alloc::slice::hack::to_vec::DropGuard",
                          "vec"
                        |)
                      |)
                    ]
                  |)
                |) 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::iter::adapters::take::Take")
                            []
                            [
                              Ty.apply
                                (Ty.path "core::iter::adapters::enumerate::Enumerate")
                                []
                                [ Ty.apply (Ty.path "core::slice::iter::Iter") [] [ T ] ]
                            ],
                          [],
                          "into_iter",
                          []
                        |),
                        [
                          M.call_closure (|
                            M.get_trait_method (|
                              "core::iter::traits::iterator::Iterator",
                              Ty.apply
                                (Ty.path "core::iter::adapters::enumerate::Enumerate")
                                []
                                [ Ty.apply (Ty.path "core::slice::iter::Iter") [] [ T ] ],
                              [],
                              "take",
                              []
                            |),
                            [
                              M.call_closure (|
                                M.get_trait_method (|
                                  "core::iter::traits::iterator::Iterator",
                                  Ty.apply (Ty.path "core::slice::iter::Iter") [] [ T ],
                                  [],
                                  "enumerate",
                                  []
                                |),
                                [
                                  M.call_closure (|
                                    M.get_associated_function (|
                                      Ty.apply (Ty.path "slice") [] [ T ],
                                      "iter",
                                      []
                                    |),
                                    [ M.read (| s |) ]
                                  |)
                                ]
                              |);
                              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 (| slots |) ]
                              |)
                            ]
                          |)
                        ]
                      |)
                    |),
                    [
                      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::iter::adapters::take::Take")
                                          []
                                          [
                                            Ty.apply
                                              (Ty.path "core::iter::adapters::enumerate::Enumerate")
                                              []
                                              [
                                                Ty.apply
                                                  (Ty.path "core::slice::iter::Iter")
                                                  []
                                                  [ T ]
                                              ]
                                          ],
                                        [],
                                        "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 γ1_0 := M.SubPointer.get_tuple_field (| γ0_0, 0 |) in
                                        let γ1_1 := M.SubPointer.get_tuple_field (| γ0_0, 1 |) in
                                        let i := M.copy (| γ1_0 |) in
                                        let b := M.copy (| γ1_1 |) in
                                        let~ _ :=
                                          M.write (|
                                            M.SubPointer.get_struct_record_field (|
                                              guard,
                                              "alloc::slice::hack::to_vec::DropGuard",
                                              "num_init"
                                            |),
                                            M.read (| i |)
                                          |) in
                                        let~ _ :=
                                          M.alloc (|
                                            M.call_closure (|
                                              M.get_associated_function (|
                                                Ty.apply
                                                  (Ty.path "core::mem::maybe_uninit::MaybeUninit")
                                                  []
                                                  [ T ],
                                                "write",
                                                []
                                              |),
                                              [
                                                M.SubPointer.get_array_field (|
                                                  M.read (| slots |),
                                                  i
                                                |);
                                                M.call_closure (|
                                                  M.get_trait_method (|
                                                    "core::clone::Clone",
                                                    T,
                                                    [],
                                                    "clone",
                                                    []
                                                  |),
                                                  [ M.read (| b |) ]
                                                |)
                                              ]
                                            |)
                                          |) in
                                        M.alloc (| Value.Tuple [] |)))
                                  ]
                                |) in
                              M.alloc (| Value.Tuple [] |)))
                          |)))
                    ]
                  |)) in
              let~ _ :=
                M.alloc (|
                  M.call_closure (|
                    M.get_function (|
                      "core::mem::forget",
                      [ Ty.apply (Ty.path "alloc::slice::hack::to_vec::DropGuard") [] [ T; A ] ]
                    |),
                    [ M.read (| guard |) ]
                  |)
                |) in
              let~ _ :=
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                        "set_len",
                        []
                      |),
                      [
                        vec;
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ T ],
                            "len",
                            []
                          |),
                          [ M.read (| s |) ]
                        |)
                      ]
                    |)
                  |) in
                M.alloc (| Value.Tuple [] |) in
              vec
            |)))
        | _, _, _ => M.impossible "wrong number of arguments"
        end.
      
      Axiom Implements :
        forall (T : Ty.t),
        M.IsTraitInstance
          "alloc::slice::hack::ConvertVec"
          (Self T)
          (* Trait polymorphic types *) []
          (* Instance *) [ ("to_vec", InstanceField.Method (to_vec T)) ].
    End Impl_alloc_slice_hack_ConvertVec_where_core_clone_Clone_T_for_T.
    
    Module Impl_alloc_slice_hack_ConvertVec_where_core_marker_Copy_T_for_T.
      Definition Self (T : Ty.t) : Ty.t := T.
      
      (*
              fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
                  let mut v = Vec::with_capacity_in(s.len(), alloc);
                  // SAFETY:
                  // allocated above with the capacity of `s`, and initialize to `s.len()` in
                  // ptr::copy_to_non_overlapping below.
                  unsafe {
                      s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), s.len());
                      v.set_len(s.len());
                  }
                  v
              }
      *)
      Definition to_vec (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
        let Self : Ty.t := Self T in
        match ε, τ, α with
        | [], [ A ], [ s; alloc ] =>
          ltac:(M.monadic
            (let s := M.alloc (| s |) in
            let alloc := M.alloc (| alloc |) in
            M.read (|
              let~ v :=
                M.alloc (|
                  M.call_closure (|
                    M.get_associated_function (|
                      Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                      "with_capacity_in",
                      []
                    |),
                    [
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply (Ty.path "slice") [] [ T ],
                          "len",
                          []
                        |),
                        [ M.read (| s |) ]
                      |);
                      M.read (| alloc |)
                    ]
                  |)
                |) in
              let~ _ :=
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "*const") [] [ T ],
                        "copy_to_nonoverlapping",
                        []
                      |),
                      [
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ T ],
                            "as_ptr",
                            []
                          |),
                          [ M.read (| s |) ]
                        |);
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                            "as_mut_ptr",
                            []
                          |),
                          [ v ]
                        |);
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ T ],
                            "len",
                            []
                          |),
                          [ M.read (| s |) ]
                        |)
                      ]
                    |)
                  |) in
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                        "set_len",
                        []
                      |),
                      [
                        v;
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ T ],
                            "len",
                            []
                          |),
                          [ M.read (| s |) ]
                        |)
                      ]
                    |)
                  |) in
                M.alloc (| Value.Tuple [] |) in
              v
            |)))
        | _, _, _ => M.impossible "wrong number of arguments"
        end.
      
      Axiom Implements :
        forall (T : Ty.t),
        M.IsTraitInstance
          "alloc::slice::hack::ConvertVec"
          (Self T)
          (* Trait polymorphic types *) []
          (* Instance *) [ ("to_vec", InstanceField.Method (to_vec T)) ].
    End Impl_alloc_slice_hack_ConvertVec_where_core_marker_Copy_T_for_T.
  End hack.
  
  Module Impl_slice_T.
    Definition Self (T : Ty.t) : Ty.t := Ty.apply (Ty.path "slice") [] [ T ].
    
    (*
        pub fn sort(&mut self)
        where
            T: Ord,
        {
            stable_sort(self, T::lt);
        }
    *)
    Definition sort (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.read (|
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_function (|
                    "alloc::slice::stable_sort",
                    [
                      T;
                      Ty.function
                        [ Ty.apply (Ty.path "&") [] [ T ]; Ty.apply (Ty.path "&") [] [ T ] ]
                        (Ty.path "bool")
                    ]
                  |),
                  [
                    M.read (| self |);
                    M.get_trait_method (| "core::cmp::PartialOrd", T, [ T ], "lt", [] |)
                  ]
                |)
              |) in
            M.alloc (| Value.Tuple [] |)
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_sort :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "sort" (sort T).
    
    (*
        pub fn sort_by<F>(&mut self, mut compare: F)
        where
            F: FnMut(&T, &T) -> Ordering,
        {
            stable_sort(self, |a, b| compare(a, b) == Less);
        }
    *)
    Definition sort_by (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [ F ], [ self; compare ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let compare := M.alloc (| compare |) in
          M.read (|
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_function (|
                    "alloc::slice::stable_sort",
                    [
                      T;
                      Ty.function
                        [
                          Ty.tuple
                            [ Ty.apply (Ty.path "&") [] [ T ]; Ty.apply (Ty.path "&") [] [ T ] ]
                        ]
                        (Ty.path "bool")
                    ]
                  |),
                  [
                    M.read (| self |);
                    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
                                              M.call_closure (|
                                                M.get_trait_method (|
                                                  "core::cmp::PartialEq",
                                                  Ty.path "core::cmp::Ordering",
                                                  [ Ty.path "core::cmp::Ordering" ],
                                                  "eq",
                                                  []
                                                |),
                                                [
                                                  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",
                                                        []
                                                      |),
                                                      [
                                                        compare;
                                                        Value.Tuple
                                                          [ M.read (| a |); M.read (| b |) ]
                                                      ]
                                                    |)
                                                  |);
                                                  M.alloc (|
                                                    Value.StructTuple "core::cmp::Ordering::Less" []
                                                  |)
                                                ]
                                              |)))
                                        ]
                                      |)))
                                ]
                              |)))
                          | _ => M.impossible "wrong number of arguments"
                          end))
                  ]
                |)
              |) in
            M.alloc (| Value.Tuple [] |)
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_sort_by :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "sort_by" (sort_by T).
    
    (*
        pub fn sort_by_key<K, F>(&mut self, mut f: F)
        where
            F: FnMut(&T) -> K,
            K: Ord,
        {
            stable_sort(self, |a, b| f(a).lt(&f(b)));
        }
    *)
    Definition sort_by_key (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [ K; F ], [ self; f ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let f := M.alloc (| f |) in
          M.read (|
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_function (|
                    "alloc::slice::stable_sort",
                    [
                      T;
                      Ty.function
                        [
                          Ty.tuple
                            [ Ty.apply (Ty.path "&") [] [ T ]; Ty.apply (Ty.path "&") [] [ T ] ]
                        ]
                        (Ty.path "bool")
                    ]
                  |),
                  [
                    M.read (| self |);
                    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
                                              M.call_closure (|
                                                M.get_trait_method (|
                                                  "core::cmp::PartialOrd",
                                                  K,
                                                  [ K ],
                                                  "lt",
                                                  []
                                                |),
                                                [
                                                  M.alloc (|
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::ops::function::FnMut",
                                                        F,
                                                        [
                                                          Ty.tuple
                                                            [ Ty.apply (Ty.path "&") [] [ T ] ]
                                                        ],
                                                        "call_mut",
                                                        []
                                                      |),
                                                      [ f; Value.Tuple [ M.read (| a |) ] ]
                                                    |)
                                                  |);
                                                  M.alloc (|
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::ops::function::FnMut",
                                                        F,
                                                        [
                                                          Ty.tuple
                                                            [ Ty.apply (Ty.path "&") [] [ T ] ]
                                                        ],
                                                        "call_mut",
                                                        []
                                                      |),
                                                      [ f; Value.Tuple [ M.read (| b |) ] ]
                                                    |)
                                                  |)
                                                ]
                                              |)))
                                        ]
                                      |)))
                                ]
                              |)))
                          | _ => M.impossible "wrong number of arguments"
                          end))
                  ]
                |)
              |) in
            M.alloc (| Value.Tuple [] |)
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_sort_by_key :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "sort_by_key" (sort_by_key T).
    
    (*
        pub fn sort_by_cached_key<K, F>(&mut self, f: F)
        where
            F: FnMut(&T) -> K,
            K: Ord,
        {
            // Helper macro for indexing our vector by the smallest possible type, to reduce allocation.
            macro_rules! sort_by_key {
                ($t:ty, $slice:ident, $f:ident) => {{
                    let mut indices: Vec<_> =
                        $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
                    // The elements of `indices` are unique, as they are indexed, so any sort will be
                    // stable with respect to the original slice. We use `sort_unstable` here because
                    // it requires no memory allocation.
                    indices.sort_unstable();
                    for i in 0..$slice.len() {
                        let mut index = indices[i].1;
                        while (index as usize) < i {
                            index = indices[index as usize].1;
                        }
                        indices[i].1 = index;
                        $slice.swap(i, index as usize);
                    }
                }};
            }
    
            let len = self.len();
            if len < 2 {
                return;
            }
    
            // Avoids binary-size usage in cases where the alignment doesn't work out to make this
            // beneficial or on 32-bit platforms.
            let is_using_u32_as_idx_type_helpful =
                const { mem::size_of::<(K, u32)>() < mem::size_of::<(K, usize)>() };
    
            // It's possible to instantiate this for u8 and u16 but, doing so is very wasteful in terms
            // of compile-times and binary-size, the peak saved heap memory for u16 is (u8 + u16) -> 4
            // bytes * u16::MAX vs (u8 + u32) -> 8 bytes * u16::MAX, the saved heap memory is at peak
            // ~262KB.
            if is_using_u32_as_idx_type_helpful && len <= (u32::MAX as usize) {
                return sort_by_key!(u32, self, f);
            }
    
            sort_by_key!(usize, self, f)
        }
    *)
    Definition sort_by_cached_key
        (T : Ty.t)
        (ε : list Value.t)
        (τ : list Ty.t)
        (α : list Value.t)
        : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [ K; F ], [ self; f ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let f := M.alloc (| f |) 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 (| self |) ]
                    |)
                  |) 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 [] |) |) |)
                          |)));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                let~ is_using_u32_as_idx_type_helpful :=
                  M.copy (|
                    M.get_constant (| "alloc::slice::sort_by_cached_key_discriminant" |)
                  |) in
                let~ _ :=
                  M.match_operator (|
                    M.alloc (| Value.Tuple [] |),
                    [
                      fun γ =>
                        ltac:(M.monadic
                          (let γ :=
                            M.use
                              (M.alloc (|
                                LogicalOp.and (|
                                  M.read (| is_using_u32_as_idx_type_helpful |),
                                  ltac:(M.monadic
                                    (BinOp.le (|
                                      M.read (| len |),
                                      M.rust_cast
                                        (M.read (| M.get_constant (| "core::num::MAX" |) |))
                                    |)))
                                |)
                              |)) in
                          let _ :=
                            M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                          M.alloc (|
                            M.never_to_any (|
                              M.read (|
                                M.return_ (|
                                  M.read (|
                                    let~ indices :=
                                      M.alloc (|
                                        M.call_closure (|
                                          M.get_trait_method (|
                                            "core::iter::traits::iterator::Iterator",
                                            Ty.apply
                                              (Ty.path "core::iter::adapters::map::Map")
                                              []
                                              [
                                                Ty.apply
                                                  (Ty.path
                                                    "core::iter::adapters::enumerate::Enumerate")
                                                  []
                                                  [
                                                    Ty.apply
                                                      (Ty.path "core::iter::adapters::map::Map")
                                                      []
                                                      [
                                                        Ty.apply
                                                          (Ty.path "core::slice::iter::Iter")
                                                          []
                                                          [ T ];
                                                        F
                                                      ]
                                                  ];
                                                Ty.function
                                                  [ Ty.tuple [ Ty.tuple [ Ty.path "usize"; K ] ] ]
                                                  (Ty.tuple [ K; Ty.path "u32" ])
                                              ],
                                            [],
                                            "collect",
                                            [
                                              Ty.apply
                                                (Ty.path "alloc::vec::Vec")
                                                []
                                                [
                                                  Ty.tuple [ K; Ty.path "u32" ];
                                                  Ty.path "alloc::alloc::Global"
                                                ]
                                            ]
                                          |),
                                          [
                                            M.call_closure (|
                                              M.get_trait_method (|
                                                "core::iter::traits::iterator::Iterator",
                                                Ty.apply
                                                  (Ty.path
                                                    "core::iter::adapters::enumerate::Enumerate")
                                                  []
                                                  [
                                                    Ty.apply
                                                      (Ty.path "core::iter::adapters::map::Map")
                                                      []
                                                      [
                                                        Ty.apply
                                                          (Ty.path "core::slice::iter::Iter")
                                                          []
                                                          [ T ];
                                                        F
                                                      ]
                                                  ],
                                                [],
                                                "map",
                                                [
                                                  Ty.tuple [ K; Ty.path "u32" ];
                                                  Ty.function
                                                    [ Ty.tuple [ Ty.tuple [ Ty.path "usize"; K ] ] ]
                                                    (Ty.tuple [ K; Ty.path "u32" ])
                                                ]
                                              |),
                                              [
                                                M.call_closure (|
                                                  M.get_trait_method (|
                                                    "core::iter::traits::iterator::Iterator",
                                                    Ty.apply
                                                      (Ty.path "core::iter::adapters::map::Map")
                                                      []
                                                      [
                                                        Ty.apply
                                                          (Ty.path "core::slice::iter::Iter")
                                                          []
                                                          [ T ];
                                                        F
                                                      ],
                                                    [],
                                                    "enumerate",
                                                    []
                                                  |),
                                                  [
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::iter::traits::iterator::Iterator",
                                                        Ty.apply
                                                          (Ty.path "core::slice::iter::Iter")
                                                          []
                                                          [ T ],
                                                        [],
                                                        "map",
                                                        [ K; F ]
                                                      |),
                                                      [
                                                        M.call_closure (|
                                                          M.get_associated_function (|
                                                            Ty.apply (Ty.path "slice") [] [ T ],
                                                            "iter",
                                                            []
                                                          |),
                                                          [ M.read (| self |) ]
                                                        |);
                                                        M.read (| f |)
                                                      ]
                                                    |)
                                                  ]
                                                |);
                                                M.closure
                                                  (fun γ =>
                                                    ltac:(M.monadic
                                                      match γ with
                                                      | [ α0 ] =>
                                                        ltac:(M.monadic
                                                          (M.match_operator (|
                                                            M.alloc (| α0 |),
                                                            [
                                                              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 i := M.copy (| γ0_0 |) in
                                                                  let k := M.copy (| γ0_1 |) in
                                                                  Value.Tuple
                                                                    [
                                                                      M.read (| k |);
                                                                      M.rust_cast (M.read (| i |))
                                                                    ]))
                                                            ]
                                                          |)))
                                                      | _ =>
                                                        M.impossible "wrong number of arguments"
                                                      end))
                                              ]
                                            |)
                                          ]
                                        |)
                                      |) in
                                    let~ _ :=
                                      M.alloc (|
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply
                                              (Ty.path "slice")
                                              []
                                              [ Ty.tuple [ K; Ty.path "u32" ] ],
                                            "sort_unstable",
                                            []
                                          |),
                                          [
                                            M.call_closure (|
                                              M.get_trait_method (|
                                                "core::ops::deref::DerefMut",
                                                Ty.apply
                                                  (Ty.path "alloc::vec::Vec")
                                                  []
                                                  [
                                                    Ty.tuple [ K; Ty.path "u32" ];
                                                    Ty.path "alloc::alloc::Global"
                                                  ],
                                                [],
                                                "deref_mut",
                                                []
                                              |),
                                              [ indices ]
                                            |)
                                          ]
                                        |)
                                      |) in
                                    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_",
                                                    M.call_closure (|
                                                      M.get_associated_function (|
                                                        Ty.apply (Ty.path "slice") [] [ T ],
                                                        "len",
                                                        []
                                                      |),
                                                      [ M.read (| self |) ]
                                                    |))
                                                ]
                                            ]
                                          |)
                                        |),
                                        [
                                          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~ index :=
                                                              M.copy (|
                                                                M.SubPointer.get_tuple_field (|
                                                                  M.call_closure (|
                                                                    M.get_trait_method (|
                                                                      "core::ops::index::Index",
                                                                      Ty.apply
                                                                        (Ty.path "alloc::vec::Vec")
                                                                        []
                                                                        [
                                                                          Ty.tuple
                                                                            [ K; Ty.path "u32" ];
                                                                          Ty.path
                                                                            "alloc::alloc::Global"
                                                                        ],
                                                                      [ Ty.path "usize" ],
                                                                      "index",
                                                                      []
                                                                    |),
                                                                    [ indices; M.read (| i |) ]
                                                                  |),
                                                                  1
                                                                |)
                                                              |) 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.rust_cast
                                                                                    (M.read (|
                                                                                      index
                                                                                    |)),
                                                                                  M.read (| i |)
                                                                                |)
                                                                              |)) in
                                                                          let _ :=
                                                                            M.is_constant_or_break_match (|
                                                                              M.read (| γ |),
                                                                              Value.Bool true
                                                                            |) in
                                                                          let~ _ :=
                                                                            M.write (|
                                                                              index,
                                                                              M.read (|
                                                                                M.SubPointer.get_tuple_field (|
                                                                                  M.call_closure (|
                                                                                    M.get_trait_method (|
                                                                                      "core::ops::index::Index",
                                                                                      Ty.apply
                                                                                        (Ty.path
                                                                                          "alloc::vec::Vec")
                                                                                        []
                                                                                        [
                                                                                          Ty.tuple
                                                                                            [
                                                                                              K;
                                                                                              Ty.path
                                                                                                "u32"
                                                                                            ];
                                                                                          Ty.path
                                                                                            "alloc::alloc::Global"
                                                                                        ],
                                                                                      [
                                                                                        Ty.path
                                                                                          "usize"
                                                                                      ],
                                                                                      "index",
                                                                                      []
                                                                                    |),
                                                                                    [
                                                                                      indices;
                                                                                      M.rust_cast
                                                                                        (M.read (|
                                                                                          index
                                                                                        |))
                                                                                    ]
                                                                                  |),
                                                                                  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
                                                            let~ _ :=
                                                              M.write (|
                                                                M.SubPointer.get_tuple_field (|
                                                                  M.call_closure (|
                                                                    M.get_trait_method (|
                                                                      "core::ops::index::IndexMut",
                                                                      Ty.apply
                                                                        (Ty.path "alloc::vec::Vec")
                                                                        []
                                                                        [
                                                                          Ty.tuple
                                                                            [ K; Ty.path "u32" ];
                                                                          Ty.path
                                                                            "alloc::alloc::Global"
                                                                        ],
                                                                      [ Ty.path "usize" ],
                                                                      "index_mut",
                                                                      []
                                                                    |),
                                                                    [ indices; M.read (| i |) ]
                                                                  |),
                                                                  1
                                                                |),
                                                                M.read (| index |)
                                                              |) in
                                                            let~ _ :=
                                                              M.alloc (|
                                                                M.call_closure (|
                                                                  M.get_associated_function (|
                                                                    Ty.apply
                                                                      (Ty.path "slice")
                                                                      []
                                                                      [ T ],
                                                                    "swap",
                                                                    []
                                                                  |),
                                                                  [
                                                                    M.read (| self |);
                                                                    M.read (| i |);
                                                                    M.rust_cast (M.read (| index |))
                                                                  ]
                                                                |)
                                                              |) in
                                                            M.alloc (| Value.Tuple [] |)))
                                                      ]
                                                    |) in
                                                  M.alloc (| Value.Tuple [] |)))
                                              |)))
                                        ]
                                      |))
                                  |)
                                |)
                              |)
                            |)
                          |)));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                let~ indices :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_trait_method (|
                        "core::iter::traits::iterator::Iterator",
                        Ty.apply
                          (Ty.path "core::iter::adapters::map::Map")
                          []
                          [
                            Ty.apply
                              (Ty.path "core::iter::adapters::enumerate::Enumerate")
                              []
                              [
                                Ty.apply
                                  (Ty.path "core::iter::adapters::map::Map")
                                  []
                                  [ Ty.apply (Ty.path "core::slice::iter::Iter") [] [ T ]; F ]
                              ];
                            Ty.function
                              [ Ty.tuple [ Ty.tuple [ Ty.path "usize"; K ] ] ]
                              (Ty.tuple [ K; Ty.path "usize" ])
                          ],
                        [],
                        "collect",
                        [
                          Ty.apply
                            (Ty.path "alloc::vec::Vec")
                            []
                            [ Ty.tuple [ K; Ty.path "usize" ]; Ty.path "alloc::alloc::Global" ]
                        ]
                      |),
                      [
                        M.call_closure (|
                          M.get_trait_method (|
                            "core::iter::traits::iterator::Iterator",
                            Ty.apply
                              (Ty.path "core::iter::adapters::enumerate::Enumerate")
                              []
                              [
                                Ty.apply
                                  (Ty.path "core::iter::adapters::map::Map")
                                  []
                                  [ Ty.apply (Ty.path "core::slice::iter::Iter") [] [ T ]; F ]
                              ],
                            [],
                            "map",
                            [
                              Ty.tuple [ K; Ty.path "usize" ];
                              Ty.function
                                [ Ty.tuple [ Ty.tuple [ Ty.path "usize"; K ] ] ]
                                (Ty.tuple [ K; Ty.path "usize" ])
                            ]
                          |),
                          [
                            M.call_closure (|
                              M.get_trait_method (|
                                "core::iter::traits::iterator::Iterator",
                                Ty.apply
                                  (Ty.path "core::iter::adapters::map::Map")
                                  []
                                  [ Ty.apply (Ty.path "core::slice::iter::Iter") [] [ T ]; F ],
                                [],
                                "enumerate",
                                []
                              |),
                              [
                                M.call_closure (|
                                  M.get_trait_method (|
                                    "core::iter::traits::iterator::Iterator",
                                    Ty.apply (Ty.path "core::slice::iter::Iter") [] [ T ],
                                    [],
                                    "map",
                                    [ K; F ]
                                  |),
                                  [
                                    M.call_closure (|
                                      M.get_associated_function (|
                                        Ty.apply (Ty.path "slice") [] [ T ],
                                        "iter",
                                        []
                                      |),
                                      [ M.read (| self |) ]
                                    |);
                                    M.read (| f |)
                                  ]
                                |)
                              ]
                            |);
                            M.closure
                              (fun γ =>
                                ltac:(M.monadic
                                  match γ with
                                  | [ α0 ] =>
                                    ltac:(M.monadic
                                      (M.match_operator (|
                                        M.alloc (| α0 |),
                                        [
                                          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 i := M.copy (| γ0_0 |) in
                                              let k := M.copy (| γ0_1 |) in
                                              Value.Tuple [ M.read (| k |); M.read (| M.use i |) ]))
                                        ]
                                      |)))
                                  | _ => M.impossible "wrong number of arguments"
                                  end))
                          ]
                        |)
                      ]
                    |)
                  |) in
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "slice") [] [ Ty.tuple [ K; Ty.path "usize" ] ],
                        "sort_unstable",
                        []
                      |),
                      [
                        M.call_closure (|
                          M.get_trait_method (|
                            "core::ops::deref::DerefMut",
                            Ty.apply
                              (Ty.path "alloc::vec::Vec")
                              []
                              [ Ty.tuple [ K; Ty.path "usize" ]; Ty.path "alloc::alloc::Global" ],
                            [],
                            "deref_mut",
                            []
                          |),
                          [ indices ]
                        |)
                      ]
                    |)
                  |) in
                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_",
                                M.call_closure (|
                                  M.get_associated_function (|
                                    Ty.apply (Ty.path "slice") [] [ T ],
                                    "len",
                                    []
                                  |),
                                  [ M.read (| self |) ]
                                |))
                            ]
                        ]
                      |)
                    |),
                    [
                      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~ index :=
                                          M.copy (|
                                            M.SubPointer.get_tuple_field (|
                                              M.call_closure (|
                                                M.get_trait_method (|
                                                  "core::ops::index::Index",
                                                  Ty.apply
                                                    (Ty.path "alloc::vec::Vec")
                                                    []
                                                    [
                                                      Ty.tuple [ K; Ty.path "usize" ];
                                                      Ty.path "alloc::alloc::Global"
                                                    ],
                                                  [ Ty.path "usize" ],
                                                  "index",
                                                  []
                                                |),
                                                [ indices; M.read (| i |) ]
                                              |),
                                              1
                                            |)
                                          |) 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.use index |),
                                                              M.read (| i |)
                                                            |)
                                                          |)) in
                                                      let _ :=
                                                        M.is_constant_or_break_match (|
                                                          M.read (| γ |),
                                                          Value.Bool true
                                                        |) in
                                                      let~ _ :=
                                                        M.write (|
                                                          index,
                                                          M.read (|
                                                            M.SubPointer.get_tuple_field (|
                                                              M.call_closure (|
                                                                M.get_trait_method (|
                                                                  "core::ops::index::Index",
                                                                  Ty.apply
                                                                    (Ty.path "alloc::vec::Vec")
                                                                    []
                                                                    [
                                                                      Ty.tuple
                                                                        [ K; Ty.path "usize" ];
                                                                      Ty.path "alloc::alloc::Global"
                                                                    ],
                                                                  [ Ty.path "usize" ],
                                                                  "index",
                                                                  []
                                                                |),
                                                                [ indices; M.read (| M.use index |)
                                                                ]
                                                              |),
                                                              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
                                        let~ _ :=
                                          M.write (|
                                            M.SubPointer.get_tuple_field (|
                                              M.call_closure (|
                                                M.get_trait_method (|
                                                  "core::ops::index::IndexMut",
                                                  Ty.apply
                                                    (Ty.path "alloc::vec::Vec")
                                                    []
                                                    [
                                                      Ty.tuple [ K; Ty.path "usize" ];
                                                      Ty.path "alloc::alloc::Global"
                                                    ],
                                                  [ Ty.path "usize" ],
                                                  "index_mut",
                                                  []
                                                |),
                                                [ indices; M.read (| i |) ]
                                              |),
                                              1
                                            |),
                                            M.read (| index |)
                                          |) in
                                        let~ _ :=
                                          M.alloc (|
                                            M.call_closure (|
                                              M.get_associated_function (|
                                                Ty.apply (Ty.path "slice") [] [ T ],
                                                "swap",
                                                []
                                              |),
                                              [
                                                M.read (| self |);
                                                M.read (| i |);
                                                M.read (| M.use index |)
                                              ]
                                            |)
                                          |) in
                                        M.alloc (| Value.Tuple [] |)))
                                  ]
                                |) in
                              M.alloc (| Value.Tuple [] |)))
                          |)))
                    ]
                  |))
              |)))
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_sort_by_cached_key :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "sort_by_cached_key" (sort_by_cached_key T).
    
    (*
        pub fn to_vec(&self) -> Vec<T>
        where
            T: Clone,
        {
            self.to_vec_in(Global)
        }
    *)
    Definition to_vec (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.call_closure (|
            M.get_associated_function (|
              Ty.apply (Ty.path "slice") [] [ T ],
              "to_vec_in",
              [ Ty.path "alloc::alloc::Global" ]
            |),
            [ M.read (| self |); Value.StructTuple "alloc::alloc::Global" [] ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_to_vec :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "to_vec" (to_vec T).
    
    (*
        pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>
        where
            T: Clone,
        {
            // N.B., see the `hack` module in this file for more details.
            hack::to_vec(self, alloc)
        }
    *)
    Definition to_vec_in (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [ A ], [ self; alloc ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let alloc := M.alloc (| alloc |) in
          M.call_closure (|
            M.get_function (| "alloc::slice::hack::to_vec", [ T; A ] |),
            [ M.read (| self |); M.read (| alloc |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_to_vec_in :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "to_vec_in" (to_vec_in T).
    
    (*
        pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> {
            // N.B., see the `hack` module in this file for more details.
            hack::into_vec(self)
        }
    *)
    Definition into_vec (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [ A ], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.call_closure (|
            M.get_function (| "alloc::slice::hack::into_vec", [ T; A ] |),
            [ M.read (| self |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_into_vec :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "into_vec" (into_vec T).
    
    (*
        pub fn repeat(&self, n: usize) -> Vec<T>
        where
            T: Copy,
        {
            if n == 0 {
                return Vec::new();
            }
    
            // If `n` is larger than zero, it can be split as
            // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.
            // `2^expn` is the number represented by the leftmost '1' bit of `n`,
            // and `rem` is the remaining part of `n`.
    
            // Using `Vec` to access `set_len()`.
            let capacity = self.len().checked_mul(n).expect("capacity overflow");
            let mut buf = Vec::with_capacity(capacity);
    
            // `2^expn` repetition is done by doubling `buf` `expn`-times.
            buf.extend(self);
            {
                let mut m = n >> 1;
                // If `m > 0`, there are remaining bits up to the leftmost '1'.
                while m > 0 {
                    // `buf.extend(buf)`:
                    unsafe {
                        ptr::copy_nonoverlapping::<T>(
                            buf.as_ptr(),
                            (buf.as_mut_ptr()).add(buf.len()),
                            buf.len(),
                        );
                        // `buf` has capacity of `self.len() * n`.
                        let buf_len = buf.len();
                        buf.set_len(buf_len * 2);
                    }
    
                    m >>= 1;
                }
            }
    
            // `rem` (`= n - 2^expn`) repetition is done by copying
            // first `rem` repetitions from `buf` itself.
            let rem_len = capacity - buf.len(); // `self.len() * rem`
            if rem_len > 0 {
                // `buf.extend(buf[0 .. rem_len])`:
                unsafe {
                    // This is non-overlapping since `2^expn > rem`.
                    ptr::copy_nonoverlapping::<T>(
                        buf.as_ptr(),
                        (buf.as_mut_ptr()).add(buf.len()),
                        rem_len,
                    );
                    // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`).
                    buf.set_len(capacity);
                }
            }
            buf
        }
    *)
    Definition repeat (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [], [ self; n ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let n := M.alloc (| n |) in
          M.catch_return (|
            ltac:(M.monadic
              (M.read (|
                let~ _ :=
                  M.match_operator (|
                    M.alloc (| Value.Tuple [] |),
                    [
                      fun γ =>
                        ltac:(M.monadic
                          (let γ :=
                            M.use
                              (M.alloc (|
                                BinOp.eq (| M.read (| n |), Value.Integer IntegerKind.Usize 0 |)
                              |)) in
                          let _ :=
                            M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                          M.alloc (|
                            M.never_to_any (|
                              M.read (|
                                M.return_ (|
                                  M.call_closure (|
                                    M.get_associated_function (|
                                      Ty.apply
                                        (Ty.path "alloc::vec::Vec")
                                        []
                                        [ T; Ty.path "alloc::alloc::Global" ],
                                      "new",
                                      []
                                    |),
                                    []
                                  |)
                                |)
                              |)
                            |)
                          |)));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                let~ capacity :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "core::option::Option") [] [ Ty.path "usize" ],
                        "expect",
                        []
                      |),
                      [
                        M.call_closure (|
                          M.get_associated_function (| Ty.path "usize", "checked_mul", [] |),
                          [
                            M.call_closure (|
                              M.get_associated_function (|
                                Ty.apply (Ty.path "slice") [] [ T ],
                                "len",
                                []
                              |),
                              [ M.read (| self |) ]
                            |);
                            M.read (| n |)
                          ]
                        |);
                        M.read (| Value.String "capacity overflow" |)
                      ]
                    |)
                  |) in
                let~ buf :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply
                          (Ty.path "alloc::vec::Vec")
                          []
                          [ T; Ty.path "alloc::alloc::Global" ],
                        "with_capacity",
                        []
                      |),
                      [ M.read (| capacity |) ]
                    |)
                  |) in
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_trait_method (|
                        "core::iter::traits::collect::Extend",
                        Ty.apply
                          (Ty.path "alloc::vec::Vec")
                          []
                          [ T; Ty.path "alloc::alloc::Global" ],
                        [ Ty.apply (Ty.path "&") [] [ T ] ],
                        "extend",
                        [ Ty.apply (Ty.path "&") [] [ Ty.apply (Ty.path "slice") [] [ T ] ] ]
                      |),
                      [ buf; M.read (| self |) ]
                    |)
                  |) in
                let~ _ :=
                  let~ m :=
                    M.alloc (|
                      BinOp.Wrap.shr (| M.read (| n |), Value.Integer IntegerKind.I32 1 |)
                    |) in
                  M.loop (|
                    ltac:(M.monadic
                      (M.match_operator (|
                        M.alloc (| Value.Tuple [] |),
                        [
                          fun γ =>
                            ltac:(M.monadic
                              (let γ :=
                                M.use
                                  (M.alloc (|
                                    BinOp.gt (| M.read (| m |), Value.Integer IntegerKind.Usize 0 |)
                                  |)) in
                              let _ :=
                                M.is_constant_or_break_match (|
                                  M.read (| γ |),
                                  Value.Bool true
                                |) in
                              let~ _ :=
                                let~ _ :=
                                  M.alloc (|
                                    M.call_closure (|
                                      M.get_function (|
                                        "core::intrinsics::copy_nonoverlapping",
                                        [ T ]
                                      |),
                                      [
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply
                                              (Ty.path "alloc::vec::Vec")
                                              []
                                              [ T; Ty.path "alloc::alloc::Global" ],
                                            "as_ptr",
                                            []
                                          |),
                                          [ buf ]
                                        |);
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply (Ty.path "*mut") [] [ T ],
                                            "add",
                                            []
                                          |),
                                          [
                                            M.call_closure (|
                                              M.get_associated_function (|
                                                Ty.apply
                                                  (Ty.path "alloc::vec::Vec")
                                                  []
                                                  [ T; Ty.path "alloc::alloc::Global" ],
                                                "as_mut_ptr",
                                                []
                                              |),
                                              [ buf ]
                                            |);
                                            M.call_closure (|
                                              M.get_associated_function (|
                                                Ty.apply
                                                  (Ty.path "alloc::vec::Vec")
                                                  []
                                                  [ T; Ty.path "alloc::alloc::Global" ],
                                                "len",
                                                []
                                              |),
                                              [ buf ]
                                            |)
                                          ]
                                        |);
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply
                                              (Ty.path "alloc::vec::Vec")
                                              []
                                              [ T; Ty.path "alloc::alloc::Global" ],
                                            "len",
                                            []
                                          |),
                                          [ buf ]
                                        |)
                                      ]
                                    |)
                                  |) in
                                let~ buf_len :=
                                  M.alloc (|
                                    M.call_closure (|
                                      M.get_associated_function (|
                                        Ty.apply
                                          (Ty.path "alloc::vec::Vec")
                                          []
                                          [ T; Ty.path "alloc::alloc::Global" ],
                                        "len",
                                        []
                                      |),
                                      [ buf ]
                                    |)
                                  |) in
                                let~ _ :=
                                  M.alloc (|
                                    M.call_closure (|
                                      M.get_associated_function (|
                                        Ty.apply
                                          (Ty.path "alloc::vec::Vec")
                                          []
                                          [ T; Ty.path "alloc::alloc::Global" ],
                                        "set_len",
                                        []
                                      |),
                                      [
                                        buf;
                                        BinOp.Wrap.mul (|
                                          M.read (| buf_len |),
                                          Value.Integer IntegerKind.Usize 2
                                        |)
                                      ]
                                    |)
                                  |) in
                                M.alloc (| Value.Tuple [] |) in
                              let~ _ :=
                                let β := m in
                                M.write (|
                                  β,
                                  BinOp.Wrap.shr (|
                                    M.read (| β |),
                                    Value.Integer IntegerKind.I32 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
                let~ rem_len :=
                  M.alloc (|
                    BinOp.Wrap.sub (|
                      M.read (| capacity |),
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply
                            (Ty.path "alloc::vec::Vec")
                            []
                            [ T; Ty.path "alloc::alloc::Global" ],
                          "len",
                          []
                        |),
                        [ buf ]
                      |)
                    |)
                  |) in
                let~ _ :=
                  M.match_operator (|
                    M.alloc (| Value.Tuple [] |),
                    [
                      fun γ =>
                        ltac:(M.monadic
                          (let γ :=
                            M.use
                              (M.alloc (|
                                BinOp.gt (|
                                  M.read (| rem_len |),
                                  Value.Integer IntegerKind.Usize 0
                                |)
                              |)) 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.call_closure (|
                                    M.get_associated_function (|
                                      Ty.apply
                                        (Ty.path "alloc::vec::Vec")
                                        []
                                        [ T; Ty.path "alloc::alloc::Global" ],
                                      "as_ptr",
                                      []
                                    |),
                                    [ buf ]
                                  |);
                                  M.call_closure (|
                                    M.get_associated_function (|
                                      Ty.apply (Ty.path "*mut") [] [ T ],
                                      "add",
                                      []
                                    |),
                                    [
                                      M.call_closure (|
                                        M.get_associated_function (|
                                          Ty.apply
                                            (Ty.path "alloc::vec::Vec")
                                            []
                                            [ T; Ty.path "alloc::alloc::Global" ],
                                          "as_mut_ptr",
                                          []
                                        |),
                                        [ buf ]
                                      |);
                                      M.call_closure (|
                                        M.get_associated_function (|
                                          Ty.apply
                                            (Ty.path "alloc::vec::Vec")
                                            []
                                            [ T; Ty.path "alloc::alloc::Global" ],
                                          "len",
                                          []
                                        |),
                                        [ buf ]
                                      |)
                                    ]
                                  |);
                                  M.read (| rem_len |)
                                ]
                              |)
                            |) in
                          let~ _ :=
                            M.alloc (|
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.apply
                                    (Ty.path "alloc::vec::Vec")
                                    []
                                    [ T; Ty.path "alloc::alloc::Global" ],
                                  "set_len",
                                  []
                                |),
                                [ buf; M.read (| capacity |) ]
                              |)
                            |) in
                          M.alloc (| Value.Tuple [] |)));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                buf
              |)))
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_repeat :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "repeat" (repeat T).
    
    (*
        pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
        where
            Self: Concat<Item>,
        {
            Concat::concat(self)
        }
    *)
    Definition concat (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [ Item ], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.call_closure (|
            M.get_trait_method (|
              "alloc::slice::Concat",
              Ty.apply (Ty.path "slice") [] [ T ],
              [ Item ],
              "concat",
              []
            |),
            [ M.read (| self |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_concat :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "concat" (concat T).
    
    (*
        pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
        where
            Self: Join<Separator>,
        {
            Join::join(self, sep)
        }
    *)
    Definition join (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [ Separator ], [ self; sep ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let sep := M.alloc (| sep |) in
          M.call_closure (|
            M.get_trait_method (|
              "alloc::slice::Join",
              Ty.apply (Ty.path "slice") [] [ T ],
              [ Separator ],
              "join",
              []
            |),
            [ M.read (| self |); M.read (| sep |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_join :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "join" (join T).
    
    (*
        pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
        where
            Self: Join<Separator>,
        {
            Join::join(self, sep)
        }
    *)
    Definition connect (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [ Separator ], [ self; sep ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let sep := M.alloc (| sep |) in
          M.call_closure (|
            M.get_trait_method (|
              "alloc::slice::Join",
              Ty.apply (Ty.path "slice") [] [ T ],
              [ Separator ],
              "join",
              []
            |),
            [ M.read (| self |); M.read (| sep |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_connect :
      forall (T : Ty.t),
      M.IsAssociatedFunction (Self T) "connect" (connect T).
  End Impl_slice_T.
  
  Module Impl_slice_u8.
    Definition Self : Ty.t := Ty.apply (Ty.path "slice") [] [ Ty.path "u8" ].
    
    (*
        pub fn to_ascii_uppercase(&self) -> Vec<u8> {
            let mut me = self.to_vec();
            me.make_ascii_uppercase();
            me
        }
    *)
    Definition to_ascii_uppercase (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      match ε, τ, α with
      | [], [], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.read (|
            let~ me :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "slice") [] [ Ty.path "u8" ],
                    "to_vec",
                    []
                  |),
                  [ M.read (| self |) ]
                |)
              |) in
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "slice") [] [ Ty.path "u8" ],
                    "make_ascii_uppercase",
                    []
                  |),
                  [
                    M.call_closure (|
                      M.get_trait_method (|
                        "core::ops::deref::DerefMut",
                        Ty.apply
                          (Ty.path "alloc::vec::Vec")
                          []
                          [ Ty.path "u8"; Ty.path "alloc::alloc::Global" ],
                        [],
                        "deref_mut",
                        []
                      |),
                      [ me ]
                    |)
                  ]
                |)
              |) in
            me
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_to_ascii_uppercase :
      M.IsAssociatedFunction Self "to_ascii_uppercase" to_ascii_uppercase.
    
    (*
        pub fn to_ascii_lowercase(&self) -> Vec<u8> {
            let mut me = self.to_vec();
            me.make_ascii_lowercase();
            me
        }
    *)
    Definition to_ascii_lowercase (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      match ε, τ, α with
      | [], [], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.read (|
            let~ me :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "slice") [] [ Ty.path "u8" ],
                    "to_vec",
                    []
                  |),
                  [ M.read (| self |) ]
                |)
              |) in
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "slice") [] [ Ty.path "u8" ],
                    "make_ascii_lowercase",
                    []
                  |),
                  [
                    M.call_closure (|
                      M.get_trait_method (|
                        "core::ops::deref::DerefMut",
                        Ty.apply
                          (Ty.path "alloc::vec::Vec")
                          []
                          [ Ty.path "u8"; Ty.path "alloc::alloc::Global" ],
                        [],
                        "deref_mut",
                        []
                      |),
                      [ me ]
                    |)
                  ]
                |)
              |) in
            me
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom AssociatedFunction_to_ascii_lowercase :
      M.IsAssociatedFunction Self "to_ascii_lowercase" to_ascii_lowercase.
  End Impl_slice_u8.
  
  (* Trait *)
  (* Empty module 'Concat' *)
  
  (* Trait *)
  (* Empty module 'Join' *)
  
  Module Impl_alloc_slice_Concat_where_core_clone_Clone_T_where_core_borrow_Borrow_V_slice_T_T_for_slice_V.
    Definition Self (T V : Ty.t) : Ty.t := Ty.apply (Ty.path "slice") [] [ V ].
    
    (*     type Output = Vec<T>; *)
    Definition _Output (T V : Ty.t) : Ty.t :=
      Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ].
    
    (*
        fn concat(slice: &Self) -> Vec<T> {
            let size = slice.iter().map(|slice| slice.borrow().len()).sum();
            let mut result = Vec::with_capacity(size);
            for v in slice {
                result.extend_from_slice(v.borrow())
            }
            result
        }
    *)
    Definition concat (T V : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T V in
      match ε, τ, α with
      | [], [], [ slice ] =>
        ltac:(M.monadic
          (let slice := M.alloc (| slice |) in
          M.read (|
            let~ size :=
              M.alloc (|
                M.call_closure (|
                  M.get_trait_method (|
                    "core::iter::traits::iterator::Iterator",
                    Ty.apply
                      (Ty.path "core::iter::adapters::map::Map")
                      []
                      [
                        Ty.apply (Ty.path "core::slice::iter::Iter") [] [ V ];
                        Ty.function
                          [ Ty.tuple [ Ty.apply (Ty.path "&") [] [ V ] ] ]
                          (Ty.path "usize")
                      ],
                    [],
                    "sum",
                    [ Ty.path "usize" ]
                  |),
                  [
                    M.call_closure (|
                      M.get_trait_method (|
                        "core::iter::traits::iterator::Iterator",
                        Ty.apply (Ty.path "core::slice::iter::Iter") [] [ V ],
                        [],
                        "map",
                        [
                          Ty.path "usize";
                          Ty.function
                            [ Ty.tuple [ Ty.apply (Ty.path "&") [] [ V ] ] ]
                            (Ty.path "usize")
                        ]
                      |),
                      [
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ V ],
                            "iter",
                            []
                          |),
                          [ M.read (| slice |) ]
                        |);
                        M.closure
                          (fun γ =>
                            ltac:(M.monadic
                              match γ with
                              | [ α0 ] =>
                                ltac:(M.monadic
                                  (M.match_operator (|
                                    M.alloc (| α0 |),
                                    [
                                      fun γ =>
                                        ltac:(M.monadic
                                          (let slice := M.copy (| γ |) in
                                          M.call_closure (|
                                            M.get_associated_function (|
                                              Ty.apply (Ty.path "slice") [] [ T ],
                                              "len",
                                              []
                                            |),
                                            [
                                              M.call_closure (|
                                                M.get_trait_method (|
                                                  "core::borrow::Borrow",
                                                  V,
                                                  [ Ty.apply (Ty.path "slice") [] [ T ] ],
                                                  "borrow",
                                                  []
                                                |),
                                                [ M.read (| slice |) ]
                                              |)
                                            ]
                                          |)))
                                    ]
                                  |)))
                              | _ => M.impossible "wrong number of arguments"
                              end))
                      ]
                    |)
                  ]
                |)
              |) in
            let~ result :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ],
                    "with_capacity",
                    []
                  |),
                  [ M.read (| size |) ]
                |)
              |) 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 "&") [] [ Ty.apply (Ty.path "slice") [] [ V ] ],
                        [],
                        "into_iter",
                        []
                      |),
                      [ M.read (| slice |) ]
                    |)
                  |),
                  [
                    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::slice::iter::Iter") [] [ V ],
                                      [],
                                      "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 v := M.copy (| γ0_0 |) in
                                      M.alloc (|
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply
                                              (Ty.path "alloc::vec::Vec")
                                              []
                                              [ T; Ty.path "alloc::alloc::Global" ],
                                            "extend_from_slice",
                                            []
                                          |),
                                          [
                                            result;
                                            M.call_closure (|
                                              M.get_trait_method (|
                                                "core::borrow::Borrow",
                                                V,
                                                [ Ty.apply (Ty.path "slice") [] [ T ] ],
                                                "borrow",
                                                []
                                              |),
                                              [ M.read (| v |) ]
                                            |)
                                          ]
                                        |)
                                      |)))
                                ]
                              |) in
                            M.alloc (| Value.Tuple [] |)))
                        |)))
                  ]
                |)) in
            result
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T V : Ty.t),
      M.IsTraitInstance
        "alloc::slice::Concat"
        (Self T V)
        (* Trait polymorphic types *) [ (* Item *) T ]
        (* Instance *)
        [ ("Output", InstanceField.Ty (_Output T V)); ("concat", InstanceField.Method (concat T V))
        ].
  End Impl_alloc_slice_Concat_where_core_clone_Clone_T_where_core_borrow_Borrow_V_slice_T_T_for_slice_V.
  
  Module Impl_alloc_slice_Join_where_core_clone_Clone_T_where_core_borrow_Borrow_V_slice_T_ref__T_for_slice_V.
    Definition Self (T V : Ty.t) : Ty.t := Ty.apply (Ty.path "slice") [] [ V ].
    
    (*     type Output = Vec<T>; *)
    Definition _Output (T V : Ty.t) : Ty.t :=
      Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ].
    
    (*
        fn join(slice: &Self, sep: &T) -> Vec<T> {
            let mut iter = slice.iter();
            let first = match iter.next() {
                Some(first) => first,
                None => return vec![],
            };
            let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;
            let mut result = Vec::with_capacity(size);
            result.extend_from_slice(first.borrow());
    
            for v in iter {
                result.push(sep.clone());
                result.extend_from_slice(v.borrow())
            }
            result
        }
    *)
    Definition join (T V : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T V in
      match ε, τ, α with
      | [], [], [ slice; sep ] =>
        ltac:(M.monadic
          (let slice := M.alloc (| slice |) in
          let sep := M.alloc (| sep |) in
          M.catch_return (|
            ltac:(M.monadic
              (M.read (|
                let~ iter :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "slice") [] [ V ],
                        "iter",
                        []
                      |),
                      [ M.read (| slice |) ]
                    |)
                  |) in
                let~ first :=
                  M.copy (|
                    M.match_operator (|
                      M.alloc (|
                        M.call_closure (|
                          M.get_trait_method (|
                            "core::iter::traits::iterator::Iterator",
                            Ty.apply (Ty.path "core::slice::iter::Iter") [] [ V ],
                            [],
                            "next",
                            []
                          |),
                          [ iter ]
                        |)
                      |),
                      [
                        fun γ =>
                          ltac:(M.monadic
                            (let γ0_0 :=
                              M.SubPointer.get_struct_tuple_field (|
                                γ,
                                "core::option::Option::Some",
                                0
                              |) in
                            let first := M.copy (| γ0_0 |) in
                            first));
                        fun γ =>
                          ltac:(M.monadic
                            (let _ := M.is_struct_tuple (| γ, "core::option::Option::None" |) in
                            M.alloc (|
                              M.never_to_any (|
                                M.read (|
                                  M.return_ (|
                                    M.call_closure (|
                                      M.get_associated_function (|
                                        Ty.apply
                                          (Ty.path "alloc::vec::Vec")
                                          []
                                          [ T; Ty.path "alloc::alloc::Global" ],
                                        "new",
                                        []
                                      |),
                                      []
                                    |)
                                  |)
                                |)
                              |)
                            |)))
                      ]
                    |)
                  |) in
                let~ size :=
                  M.alloc (|
                    BinOp.Wrap.sub (|
                      BinOp.Wrap.add (|
                        M.call_closure (|
                          M.get_trait_method (|
                            "core::iter::traits::iterator::Iterator",
                            Ty.apply
                              (Ty.path "core::iter::adapters::map::Map")
                              []
                              [
                                Ty.apply (Ty.path "core::slice::iter::Iter") [] [ V ];
                                Ty.function
                                  [ Ty.tuple [ Ty.apply (Ty.path "&") [] [ V ] ] ]
                                  (Ty.path "usize")
                              ],
                            [],
                            "sum",
                            [ Ty.path "usize" ]
                          |),
                          [
                            M.call_closure (|
                              M.get_trait_method (|
                                "core::iter::traits::iterator::Iterator",
                                Ty.apply (Ty.path "core::slice::iter::Iter") [] [ V ],
                                [],
                                "map",
                                [
                                  Ty.path "usize";
                                  Ty.function
                                    [ Ty.tuple [ Ty.apply (Ty.path "&") [] [ V ] ] ]
                                    (Ty.path "usize")
                                ]
                              |),
                              [
                                M.call_closure (|
                                  M.get_associated_function (|
                                    Ty.apply (Ty.path "slice") [] [ V ],
                                    "iter",
                                    []
                                  |),
                                  [ M.read (| slice |) ]
                                |);
                                M.closure
                                  (fun γ =>
                                    ltac:(M.monadic
                                      match γ with
                                      | [ α0 ] =>
                                        ltac:(M.monadic
                                          (M.match_operator (|
                                            M.alloc (| α0 |),
                                            [
                                              fun γ =>
                                                ltac:(M.monadic
                                                  (let v := M.copy (| γ |) in
                                                  M.call_closure (|
                                                    M.get_associated_function (|
                                                      Ty.apply (Ty.path "slice") [] [ T ],
                                                      "len",
                                                      []
                                                    |),
                                                    [
                                                      M.call_closure (|
                                                        M.get_trait_method (|
                                                          "core::borrow::Borrow",
                                                          V,
                                                          [ Ty.apply (Ty.path "slice") [] [ T ] ],
                                                          "borrow",
                                                          []
                                                        |),
                                                        [ M.read (| v |) ]
                                                      |)
                                                    ]
                                                  |)))
                                            ]
                                          |)))
                                      | _ => M.impossible "wrong number of arguments"
                                      end))
                              ]
                            |)
                          ]
                        |),
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ V ],
                            "len",
                            []
                          |),
                          [ M.read (| slice |) ]
                        |)
                      |),
                      Value.Integer IntegerKind.Usize 1
                    |)
                  |) in
                let~ result :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply
                          (Ty.path "alloc::vec::Vec")
                          []
                          [ T; Ty.path "alloc::alloc::Global" ],
                        "with_capacity",
                        []
                      |),
                      [ M.read (| size |) ]
                    |)
                  |) in
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply
                          (Ty.path "alloc::vec::Vec")
                          []
                          [ T; Ty.path "alloc::alloc::Global" ],
                        "extend_from_slice",
                        []
                      |),
                      [
                        result;
                        M.call_closure (|
                          M.get_trait_method (|
                            "core::borrow::Borrow",
                            V,
                            [ Ty.apply (Ty.path "slice") [] [ T ] ],
                            "borrow",
                            []
                          |),
                          [ M.read (| first |) ]
                        |)
                      ]
                    |)
                  |) 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::slice::iter::Iter") [] [ V ],
                            [],
                            "into_iter",
                            []
                          |),
                          [ M.read (| iter |) ]
                        |)
                      |),
                      [
                        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::slice::iter::Iter") [] [ V ],
                                          [],
                                          "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 v := M.copy (| γ0_0 |) in
                                          let~ _ :=
                                            M.alloc (|
                                              M.call_closure (|
                                                M.get_associated_function (|
                                                  Ty.apply
                                                    (Ty.path "alloc::vec::Vec")
                                                    []
                                                    [ T; Ty.path "alloc::alloc::Global" ],
                                                  "push",
                                                  []
                                                |),
                                                [
                                                  result;
                                                  M.call_closure (|
                                                    M.get_trait_method (|
                                                      "core::clone::Clone",
                                                      T,
                                                      [],
                                                      "clone",
                                                      []
                                                    |),
                                                    [ M.read (| sep |) ]
                                                  |)
                                                ]
                                              |)
                                            |) in
                                          M.alloc (|
                                            M.call_closure (|
                                              M.get_associated_function (|
                                                Ty.apply
                                                  (Ty.path "alloc::vec::Vec")
                                                  []
                                                  [ T; Ty.path "alloc::alloc::Global" ],
                                                "extend_from_slice",
                                                []
                                              |),
                                              [
                                                result;
                                                M.call_closure (|
                                                  M.get_trait_method (|
                                                    "core::borrow::Borrow",
                                                    V,
                                                    [ Ty.apply (Ty.path "slice") [] [ T ] ],
                                                    "borrow",
                                                    []
                                                  |),
                                                  [ M.read (| v |) ]
                                                |)
                                              ]
                                            |)
                                          |)))
                                    ]
                                  |) in
                                M.alloc (| Value.Tuple [] |)))
                            |)))
                      ]
                    |)) in
                result
              |)))
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T V : Ty.t),
      M.IsTraitInstance
        "alloc::slice::Join"
        (Self T V)
        (* Trait polymorphic types *) [ (* Separator *) Ty.apply (Ty.path "&") [] [ T ] ]
        (* Instance *)
        [ ("Output", InstanceField.Ty (_Output T V)); ("join", InstanceField.Method (join T V)) ].
  End Impl_alloc_slice_Join_where_core_clone_Clone_T_where_core_borrow_Borrow_V_slice_T_ref__T_for_slice_V.
  
  Module Impl_alloc_slice_Join_where_core_clone_Clone_T_where_core_borrow_Borrow_V_slice_T_ref__slice_T_for_slice_V.
    Definition Self (T V : Ty.t) : Ty.t := Ty.apply (Ty.path "slice") [] [ V ].
    
    (*     type Output = Vec<T>; *)
    Definition _Output (T V : Ty.t) : Ty.t :=
      Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ].
    
    (*
        fn join(slice: &Self, sep: &[T]) -> Vec<T> {
            let mut iter = slice.iter();
            let first = match iter.next() {
                Some(first) => first,
                None => return vec![],
            };
            let size =
                slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);
            let mut result = Vec::with_capacity(size);
            result.extend_from_slice(first.borrow());
    
            for v in iter {
                result.extend_from_slice(sep);
                result.extend_from_slice(v.borrow())
            }
            result
        }
    *)
    Definition join (T V : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T V in
      match ε, τ, α with
      | [], [], [ slice; sep ] =>
        ltac:(M.monadic
          (let slice := M.alloc (| slice |) in
          let sep := M.alloc (| sep |) in
          M.catch_return (|
            ltac:(M.monadic
              (M.read (|
                let~ iter :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "slice") [] [ V ],
                        "iter",
                        []
                      |),
                      [ M.read (| slice |) ]
                    |)
                  |) in
                let~ first :=
                  M.copy (|
                    M.match_operator (|
                      M.alloc (|
                        M.call_closure (|
                          M.get_trait_method (|
                            "core::iter::traits::iterator::Iterator",
                            Ty.apply (Ty.path "core::slice::iter::Iter") [] [ V ],
                            [],
                            "next",
                            []
                          |),
                          [ iter ]
                        |)
                      |),
                      [
                        fun γ =>
                          ltac:(M.monadic
                            (let γ0_0 :=
                              M.SubPointer.get_struct_tuple_field (|
                                γ,
                                "core::option::Option::Some",
                                0
                              |) in
                            let first := M.copy (| γ0_0 |) in
                            first));
                        fun γ =>
                          ltac:(M.monadic
                            (let _ := M.is_struct_tuple (| γ, "core::option::Option::None" |) in
                            M.alloc (|
                              M.never_to_any (|
                                M.read (|
                                  M.return_ (|
                                    M.call_closure (|
                                      M.get_associated_function (|
                                        Ty.apply
                                          (Ty.path "alloc::vec::Vec")
                                          []
                                          [ T; Ty.path "alloc::alloc::Global" ],
                                        "new",
                                        []
                                      |),
                                      []
                                    |)
                                  |)
                                |)
                              |)
                            |)))
                      ]
                    |)
                  |) in
                let~ size :=
                  M.alloc (|
                    BinOp.Wrap.add (|
                      M.call_closure (|
                        M.get_trait_method (|
                          "core::iter::traits::iterator::Iterator",
                          Ty.apply
                            (Ty.path "core::iter::adapters::map::Map")
                            []
                            [
                              Ty.apply (Ty.path "core::slice::iter::Iter") [] [ V ];
                              Ty.function
                                [ Ty.tuple [ Ty.apply (Ty.path "&") [] [ V ] ] ]
                                (Ty.path "usize")
                            ],
                          [],
                          "sum",
                          [ Ty.path "usize" ]
                        |),
                        [
                          M.call_closure (|
                            M.get_trait_method (|
                              "core::iter::traits::iterator::Iterator",
                              Ty.apply (Ty.path "core::slice::iter::Iter") [] [ V ],
                              [],
                              "map",
                              [
                                Ty.path "usize";
                                Ty.function
                                  [ Ty.tuple [ Ty.apply (Ty.path "&") [] [ V ] ] ]
                                  (Ty.path "usize")
                              ]
                            |),
                            [
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.apply (Ty.path "slice") [] [ V ],
                                  "iter",
                                  []
                                |),
                                [ M.read (| slice |) ]
                              |);
                              M.closure
                                (fun γ =>
                                  ltac:(M.monadic
                                    match γ with
                                    | [ α0 ] =>
                                      ltac:(M.monadic
                                        (M.match_operator (|
                                          M.alloc (| α0 |),
                                          [
                                            fun γ =>
                                              ltac:(M.monadic
                                                (let v := M.copy (| γ |) in
                                                M.call_closure (|
                                                  M.get_associated_function (|
                                                    Ty.apply (Ty.path "slice") [] [ T ],
                                                    "len",
                                                    []
                                                  |),
                                                  [
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::borrow::Borrow",
                                                        V,
                                                        [ Ty.apply (Ty.path "slice") [] [ T ] ],
                                                        "borrow",
                                                        []
                                                      |),
                                                      [ M.read (| v |) ]
                                                    |)
                                                  ]
                                                |)))
                                          ]
                                        |)))
                                    | _ => M.impossible "wrong number of arguments"
                                    end))
                            ]
                          |)
                        ]
                      |),
                      BinOp.Wrap.mul (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ T ],
                            "len",
                            []
                          |),
                          [ M.read (| sep |) ]
                        |),
                        BinOp.Wrap.sub (|
                          M.call_closure (|
                            M.get_associated_function (|
                              Ty.apply (Ty.path "slice") [] [ V ],
                              "len",
                              []
                            |),
                            [ M.read (| slice |) ]
                          |),
                          Value.Integer IntegerKind.Usize 1
                        |)
                      |)
                    |)
                  |) in
                let~ result :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply
                          (Ty.path "alloc::vec::Vec")
                          []
                          [ T; Ty.path "alloc::alloc::Global" ],
                        "with_capacity",
                        []
                      |),
                      [ M.read (| size |) ]
                    |)
                  |) in
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply
                          (Ty.path "alloc::vec::Vec")
                          []
                          [ T; Ty.path "alloc::alloc::Global" ],
                        "extend_from_slice",
                        []
                      |),
                      [
                        result;
                        M.call_closure (|
                          M.get_trait_method (|
                            "core::borrow::Borrow",
                            V,
                            [ Ty.apply (Ty.path "slice") [] [ T ] ],
                            "borrow",
                            []
                          |),
                          [ M.read (| first |) ]
                        |)
                      ]
                    |)
                  |) 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::slice::iter::Iter") [] [ V ],
                            [],
                            "into_iter",
                            []
                          |),
                          [ M.read (| iter |) ]
                        |)
                      |),
                      [
                        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::slice::iter::Iter") [] [ V ],
                                          [],
                                          "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 v := M.copy (| γ0_0 |) in
                                          let~ _ :=
                                            M.alloc (|
                                              M.call_closure (|
                                                M.get_associated_function (|
                                                  Ty.apply
                                                    (Ty.path "alloc::vec::Vec")
                                                    []
                                                    [ T; Ty.path "alloc::alloc::Global" ],
                                                  "extend_from_slice",
                                                  []
                                                |),
                                                [ result; M.read (| sep |) ]
                                              |)
                                            |) in
                                          M.alloc (|
                                            M.call_closure (|
                                              M.get_associated_function (|
                                                Ty.apply
                                                  (Ty.path "alloc::vec::Vec")
                                                  []
                                                  [ T; Ty.path "alloc::alloc::Global" ],
                                                "extend_from_slice",
                                                []
                                              |),
                                              [
                                                result;
                                                M.call_closure (|
                                                  M.get_trait_method (|
                                                    "core::borrow::Borrow",
                                                    V,
                                                    [ Ty.apply (Ty.path "slice") [] [ T ] ],
                                                    "borrow",
                                                    []
                                                  |),
                                                  [ M.read (| v |) ]
                                                |)
                                              ]
                                            |)
                                          |)))
                                    ]
                                  |) in
                                M.alloc (| Value.Tuple [] |)))
                            |)))
                      ]
                    |)) in
                result
              |)))
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T V : Ty.t),
      M.IsTraitInstance
        "alloc::slice::Join"
        (Self T V)
        (* Trait polymorphic types *)
        [ (* Separator *) Ty.apply (Ty.path "&") [] [ Ty.apply (Ty.path "slice") [] [ T ] ] ]
        (* Instance *)
        [ ("Output", InstanceField.Ty (_Output T V)); ("join", InstanceField.Method (join T V)) ].
  End Impl_alloc_slice_Join_where_core_clone_Clone_T_where_core_borrow_Borrow_V_slice_T_ref__slice_T_for_slice_V.
  
  Module Impl_core_borrow_Borrow_where_core_alloc_Allocator_A_slice_T_for_alloc_vec_Vec_T_A.
    Definition Self (T A : Ty.t) : Ty.t := Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ].
    
    (*
        fn borrow(&self) -> &[T] {
            &self[..]
        }
    *)
    Definition borrow (T A : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T A in
      match ε, τ, α with
      | [], [], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.call_closure (|
            M.get_trait_method (|
              "core::ops::index::Index",
              Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
              [ Ty.path "core::ops::range::RangeFull" ],
              "index",
              []
            |),
            [ M.read (| self |); Value.StructTuple "core::ops::range::RangeFull" [] ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T A : Ty.t),
      M.IsTraitInstance
        "core::borrow::Borrow"
        (Self T A)
        (* Trait polymorphic types *) [ (* Borrowed *) Ty.apply (Ty.path "slice") [] [ T ] ]
        (* Instance *) [ ("borrow", InstanceField.Method (borrow T A)) ].
  End Impl_core_borrow_Borrow_where_core_alloc_Allocator_A_slice_T_for_alloc_vec_Vec_T_A.
  
  Module Impl_core_borrow_BorrowMut_where_core_alloc_Allocator_A_slice_T_for_alloc_vec_Vec_T_A.
    Definition Self (T A : Ty.t) : Ty.t := Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ].
    
    (*
        fn borrow_mut(&mut self) -> &mut [T] {
            &mut self[..]
        }
    *)
    Definition borrow_mut (T A : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T A in
      match ε, τ, α with
      | [], [], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.call_closure (|
            M.get_trait_method (|
              "core::ops::index::IndexMut",
              Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
              [ Ty.path "core::ops::range::RangeFull" ],
              "index_mut",
              []
            |),
            [ M.read (| self |); Value.StructTuple "core::ops::range::RangeFull" [] ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T A : Ty.t),
      M.IsTraitInstance
        "core::borrow::BorrowMut"
        (Self T A)
        (* Trait polymorphic types *) [ (* Borrowed *) Ty.apply (Ty.path "slice") [] [ T ] ]
        (* Instance *) [ ("borrow_mut", InstanceField.Method (borrow_mut T A)) ].
  End Impl_core_borrow_BorrowMut_where_core_alloc_Allocator_A_slice_T_for_alloc_vec_Vec_T_A.
  
  (* Trait *)
  (* Empty module 'SpecCloneIntoVec' *)
  
  Module Impl_alloc_slice_SpecCloneIntoVec_where_core_clone_Clone_T_where_core_alloc_Allocator_A_T_A_for_slice_T.
    Definition Self (T A : Ty.t) : Ty.t := Ty.apply (Ty.path "slice") [] [ T ].
    
    (*
        default fn clone_into(&self, target: &mut Vec<T, A>) {
            // drop anything in target that will not be overwritten
            target.truncate(self.len());
    
            // target.len <= self.len due to the truncate above, so the
            // slices here are always in-bounds.
            let (init, tail) = self.split_at(target.len());
    
            // reuse the contained values' allocations/resources.
            target.clone_from_slice(init);
            target.extend_from_slice(tail);
        }
    *)
    Definition clone_into (T A : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T A in
      match ε, τ, α with
      | [], [], [ self; target ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let target := M.alloc (| target |) in
          M.read (|
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                    "truncate",
                    []
                  |),
                  [
                    M.read (| target |);
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "slice") [] [ T ],
                        "len",
                        []
                      |),
                      [ M.read (| self |) ]
                    |)
                  ]
                |)
              |) in
            M.match_operator (|
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "slice") [] [ T ],
                    "split_at",
                    []
                  |),
                  [
                    M.read (| self |);
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                        "len",
                        []
                      |),
                      [ M.read (| target |) ]
                    |)
                  ]
                |)
              |),
              [
                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 init := M.copy (| γ0_0 |) in
                    let tail := M.copy (| γ0_1 |) in
                    let~ _ :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ T ],
                            "clone_from_slice",
                            []
                          |),
                          [
                            M.call_closure (|
                              M.get_trait_method (|
                                "core::ops::deref::DerefMut",
                                Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                                [],
                                "deref_mut",
                                []
                              |),
                              [ M.read (| target |) ]
                            |);
                            M.read (| init |)
                          ]
                        |)
                      |) in
                    let~ _ :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                            "extend_from_slice",
                            []
                          |),
                          [ M.read (| target |); M.read (| tail |) ]
                        |)
                      |) in
                    M.alloc (| Value.Tuple [] |)))
              ]
            |)
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T A : Ty.t),
      M.IsTraitInstance
        "alloc::slice::SpecCloneIntoVec"
        (Self T A)
        (* Trait polymorphic types *) [ (* T *) T; (* A *) A ]
        (* Instance *) [ ("clone_into", InstanceField.Method (clone_into T A)) ].
  End Impl_alloc_slice_SpecCloneIntoVec_where_core_clone_Clone_T_where_core_alloc_Allocator_A_T_A_for_slice_T.
  
  Module Impl_alloc_slice_SpecCloneIntoVec_where_core_marker_Copy_T_where_core_alloc_Allocator_A_T_A_for_slice_T.
    Definition Self (T A : Ty.t) : Ty.t := Ty.apply (Ty.path "slice") [] [ T ].
    
    (*
        fn clone_into(&self, target: &mut Vec<T, A>) {
            target.clear();
            target.extend_from_slice(self);
        }
    *)
    Definition clone_into (T A : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T A in
      match ε, τ, α with
      | [], [], [ self; target ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let target := M.alloc (| target |) in
          M.read (|
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                    "clear",
                    []
                  |),
                  [ M.read (| target |) ]
                |)
              |) in
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_associated_function (|
                    Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; A ],
                    "extend_from_slice",
                    []
                  |),
                  [ M.read (| target |); M.read (| self |) ]
                |)
              |) in
            M.alloc (| Value.Tuple [] |)
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T A : Ty.t),
      M.IsTraitInstance
        "alloc::slice::SpecCloneIntoVec"
        (Self T A)
        (* Trait polymorphic types *) [ (* T *) T; (* A *) A ]
        (* Instance *) [ ("clone_into", InstanceField.Method (clone_into T A)) ].
  End Impl_alloc_slice_SpecCloneIntoVec_where_core_marker_Copy_T_where_core_alloc_Allocator_A_T_A_for_slice_T.
  
  Module Impl_alloc_borrow_ToOwned_where_core_clone_Clone_T_for_slice_T.
    Definition Self (T : Ty.t) : Ty.t := Ty.apply (Ty.path "slice") [] [ T ].
    
    (*     type Owned = Vec<T>; *)
    Definition _Owned (T : Ty.t) : Ty.t :=
      Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ].
    
    (*
        fn to_owned(&self) -> Vec<T> {
            self.to_vec()
        }
    *)
    Definition to_owned (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.call_closure (|
            M.get_associated_function (| Ty.apply (Ty.path "slice") [] [ T ], "to_vec", [] |),
            [ M.read (| self |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    (*
        fn clone_into(&self, target: &mut Vec<T>) {
            SpecCloneIntoVec::clone_into(self, target);
        }
    *)
    Definition clone_into (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [], [ self; target ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          let target := M.alloc (| target |) in
          M.read (|
            let~ _ :=
              M.alloc (|
                M.call_closure (|
                  M.get_trait_method (|
                    "alloc::slice::SpecCloneIntoVec",
                    Ty.apply (Ty.path "slice") [] [ T ],
                    [ T; Ty.path "alloc::alloc::Global" ],
                    "clone_into",
                    []
                  |),
                  [ M.read (| self |); M.read (| target |) ]
                |)
              |) in
            M.alloc (| Value.Tuple [] |)
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T : Ty.t),
      M.IsTraitInstance
        "alloc::borrow::ToOwned"
        (Self T)
        (* Trait polymorphic types *) []
        (* Instance *)
        [
          ("Owned", InstanceField.Ty (_Owned T));
          ("to_owned", InstanceField.Method (to_owned T));
          ("clone_into", InstanceField.Method (clone_into T))
        ].
  End Impl_alloc_borrow_ToOwned_where_core_clone_Clone_T_for_slice_T.
  
  (*
  fn stable_sort<T, F>(v: &mut [T], mut is_less: F)
  where
      F: FnMut(&T, &T) -> bool,
  {
      sort::stable::sort::<T, F, Vec<T>>(v, &mut is_less);
  }
  *)
  Definition stable_sort (ε : 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.read (|
          let~ _ :=
            M.alloc (|
              M.call_closure (|
                M.get_function (|
                  "core::slice::sort::stable::sort",
                  [
                    T;
                    F;
                    Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ]
                  ]
                |),
                [ M.read (| v |); is_less ]
              |)
            |) in
          M.alloc (| Value.Tuple [] |)
        |)))
    | _, _, _ => M.impossible "wrong number of arguments"
    end.
  
  Axiom Function_stable_sort : M.IsFunction "alloc::slice::stable_sort" stable_sort.
  
  Module Impl_core_slice_sort_stable_BufGuard_T_for_alloc_vec_Vec_T_alloc_alloc_Global.
    Definition Self (T : Ty.t) : Ty.t :=
      Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ].
    
    (*
        fn with_capacity(capacity: usize) -> Self {
            Vec::with_capacity(capacity)
        }
    *)
    Definition with_capacity (T : Ty.t) (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [], [ capacity ] =>
        ltac:(M.monadic
          (let capacity := M.alloc (| capacity |) in
          M.call_closure (|
            M.get_associated_function (|
              Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ],
              "with_capacity",
              []
            |),
            [ M.read (| capacity |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    (*
        fn as_uninit_slice_mut(&mut self) -> &mut [MaybeUninit<T>] {
            self.spare_capacity_mut()
        }
    *)
    Definition as_uninit_slice_mut
        (T : Ty.t)
        (ε : list Value.t)
        (τ : list Ty.t)
        (α : list Value.t)
        : M :=
      let Self : Ty.t := Self T in
      match ε, τ, α with
      | [], [], [ self ] =>
        ltac:(M.monadic
          (let self := M.alloc (| self |) in
          M.call_closure (|
            M.get_associated_function (|
              Ty.apply (Ty.path "alloc::vec::Vec") [] [ T; Ty.path "alloc::alloc::Global" ],
              "spare_capacity_mut",
              []
            |),
            [ M.read (| self |) ]
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Implements :
      forall (T : Ty.t),
      M.IsTraitInstance
        "core::slice::sort::stable::BufGuard"
        (Self T)
        (* Trait polymorphic types *) [ (* T *) T ]
        (* Instance *)
        [
          ("with_capacity", InstanceField.Method (with_capacity T));
          ("as_uninit_slice_mut", InstanceField.Method (as_uninit_slice_mut T))
        ].
  End Impl_core_slice_sort_stable_BufGuard_T_for_alloc_vec_Vec_T_alloc_alloc_Global.
End slice.
