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

Module cyclic_dependencies.
  (*
  pub fn verify_module<D>(module: &CompiledModule, imm_deps: D) -> VMResult<()>
  where
      D: Fn(&ModuleId) -> PartialVMResult<Vec<ModuleId>>,
  {
      verify_module_impl(module, imm_deps).map_err(|e| e.finish(Location::Module(module.self_id())))
  }
  *)
  Definition verify_module (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
    match ε, τ, α with
    | [], [ D ], [ module; imm_deps ] =>
      ltac:(M.monadic
        (let module := M.alloc (| module |) in
        let imm_deps := M.alloc (| imm_deps |) in
        M.call_closure (|
          M.get_associated_function (|
            Ty.apply
              (Ty.path "core::result::Result")
              []
              [ Ty.tuple []; Ty.path "move_binary_format::errors::PartialVMError" ],
            "map_err",
            [
              Ty.path "move_binary_format::errors::VMError";
              Ty.function
                [ Ty.tuple [ Ty.path "move_binary_format::errors::PartialVMError" ] ]
                (Ty.path "move_binary_format::errors::VMError")
            ]
          |),
          [
            M.call_closure (|
              M.get_function (|
                "move_bytecode_verifier::cyclic_dependencies::verify_module_impl",
                [ D ]
              |),
              [ M.read (| module |); M.read (| imm_deps |) ]
            |);
            M.closure
              (fun γ =>
                ltac:(M.monadic
                  match γ with
                  | [ α0 ] =>
                    ltac:(M.monadic
                      (M.match_operator (|
                        M.alloc (| α0 |),
                        [
                          fun γ =>
                            ltac:(M.monadic
                              (let e := M.copy (| γ |) in
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.path "move_binary_format::errors::PartialVMError",
                                  "finish",
                                  []
                                |),
                                [
                                  M.read (| e |);
                                  Value.StructTuple
                                    "move_binary_format::errors::Location::Module"
                                    [
                                      M.call_closure (|
                                        M.get_associated_function (|
                                          Ty.path "move_binary_format::file_format::CompiledModule",
                                          "self_id",
                                          []
                                        |),
                                        [ M.read (| module |) ]
                                      |)
                                    ]
                                ]
                              |)))
                        ]
                      |)))
                  | _ => M.impossible "wrong number of arguments"
                  end))
          ]
        |)))
    | _, _, _ => M.impossible "wrong number of arguments"
    end.
  
  Axiom Function_verify_module :
    M.IsFunction "move_bytecode_verifier::cyclic_dependencies::verify_module" verify_module.
  
  (*
  fn verify_module_impl<D>(module: &CompiledModule, imm_deps: D) -> PartialVMResult<()>
  where
      D: Fn(&ModuleId) -> PartialVMResult<Vec<ModuleId>>,
  {
      fn detect_cycles<D>(
          target: &ModuleId,
          cursor: &ModuleId,
          visited: &mut BTreeSet<ModuleId>,
          deps: &D,
      ) -> PartialVMResult<bool>
      where
          D: Fn(&ModuleId) -> PartialVMResult<Vec<ModuleId>>,
      {
          if cursor == target {
              return Ok(true);
          }
  
          if !visited.insert(cursor.clone()) {
              for dep in deps(cursor)? {
                  if detect_cycles(target, &dep, visited, deps)? {
                      return Ok(true);
                  }
              }
          }
  
          Ok(false)
      }
  
      let self_id = module.self_id();
      let mut visited = BTreeSet::new();
      for dep in module.immediate_dependencies() {
          if detect_cycles(&self_id, &dep, &mut visited, &imm_deps)? {
              return Err(PartialVMError::new(StatusCode::CYCLIC_MODULE_DEPENDENCY));
          }
      }
  
      Ok(())
  }
  *)
  Definition verify_module_impl (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
    match ε, τ, α with
    | [], [ D ], [ module; imm_deps ] =>
      ltac:(M.monadic
        (let module := M.alloc (| module |) in
        let imm_deps := M.alloc (| imm_deps |) in
        M.catch_return (|
          ltac:(M.monadic
            (M.read (|
              let~ self_id :=
                M.alloc (|
                  M.call_closure (|
                    M.get_associated_function (|
                      Ty.path "move_binary_format::file_format::CompiledModule",
                      "self_id",
                      []
                    |),
                    [ M.read (| module |) ]
                  |)
                |) in
              let~ visited :=
                M.alloc (|
                  M.call_closure (|
                    M.get_associated_function (|
                      Ty.apply
                        (Ty.path "alloc::collections::btree::set::BTreeSet")
                        []
                        [
                          Ty.path "move_core_types::language_storage::ModuleId";
                          Ty.path "alloc::alloc::Global"
                        ],
                      "new",
                      []
                    |),
                    []
                  |)
                |) 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 "alloc::vec::Vec")
                            []
                            [
                              Ty.path "move_core_types::language_storage::ModuleId";
                              Ty.path "alloc::alloc::Global"
                            ],
                          [],
                          "into_iter",
                          []
                        |),
                        [
                          M.call_closure (|
                            M.get_associated_function (|
                              Ty.path "move_binary_format::file_format::CompiledModule",
                              "immediate_dependencies",
                              []
                            |),
                            [ M.read (| module |) ]
                          |)
                        ]
                      |)
                    |),
                    [
                      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 "alloc::vec::into_iter::IntoIter")
                                          []
                                          [
                                            Ty.path "move_core_types::language_storage::ModuleId";
                                            Ty.path "alloc::alloc::Global"
                                          ],
                                        [],
                                        "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 dep := M.copy (| γ0_0 |) in
                                        M.match_operator (|
                                          M.alloc (| Value.Tuple [] |),
                                          [
                                            fun γ =>
                                              ltac:(M.monadic
                                                (let γ :=
                                                  M.use
                                                    (M.match_operator (|
                                                      M.alloc (|
                                                        M.call_closure (|
                                                          M.get_trait_method (|
                                                            "core::ops::try_trait::Try",
                                                            Ty.apply
                                                              (Ty.path "core::result::Result")
                                                              []
                                                              [
                                                                Ty.path "bool";
                                                                Ty.path
                                                                  "move_binary_format::errors::PartialVMError"
                                                              ],
                                                            [],
                                                            "branch",
                                                            []
                                                          |),
                                                          [
                                                            M.call_closure (|
                                                              M.get_function (|
                                                                "move_bytecode_verifier::cyclic_dependencies::verify_module_impl.detect_cycles",
                                                                []
                                                              |),
                                                              [ self_id; dep; visited; imm_deps ]
                                                            |)
                                                          ]
                                                        |)
                                                      |),
                                                      [
                                                        fun γ =>
                                                          ltac:(M.monadic
                                                            (let γ0_0 :=
                                                              M.SubPointer.get_struct_tuple_field (|
                                                                γ,
                                                                "core::ops::control_flow::ControlFlow::Break",
                                                                0
                                                              |) in
                                                            let residual := M.copy (| γ0_0 |) in
                                                            M.alloc (|
                                                              M.never_to_any (|
                                                                M.read (|
                                                                  M.return_ (|
                                                                    M.call_closure (|
                                                                      M.get_trait_method (|
                                                                        "core::ops::try_trait::FromResidual",
                                                                        Ty.apply
                                                                          (Ty.path
                                                                            "core::result::Result")
                                                                          []
                                                                          [
                                                                            Ty.tuple [];
                                                                            Ty.path
                                                                              "move_binary_format::errors::PartialVMError"
                                                                          ],
                                                                        [
                                                                          Ty.apply
                                                                            (Ty.path
                                                                              "core::result::Result")
                                                                            []
                                                                            [
                                                                              Ty.path
                                                                                "core::convert::Infallible";
                                                                              Ty.path
                                                                                "move_binary_format::errors::PartialVMError"
                                                                            ]
                                                                        ],
                                                                        "from_residual",
                                                                        []
                                                                      |),
                                                                      [ M.read (| residual |) ]
                                                                    |)
                                                                  |)
                                                                |)
                                                              |)
                                                            |)));
                                                        fun γ =>
                                                          ltac:(M.monadic
                                                            (let γ0_0 :=
                                                              M.SubPointer.get_struct_tuple_field (|
                                                                γ,
                                                                "core::ops::control_flow::ControlFlow::Continue",
                                                                0
                                                              |) in
                                                            let val := M.copy (| γ0_0 |) in
                                                            val))
                                                      ]
                                                    |)) 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.StructTuple
                                                          "core::result::Result::Err"
                                                          [
                                                            M.call_closure (|
                                                              M.get_associated_function (|
                                                                Ty.path
                                                                  "move_binary_format::errors::PartialVMError",
                                                                "new",
                                                                []
                                                              |),
                                                              [
                                                                Value.StructTuple
                                                                  "move_core_types::vm_status::StatusCode::CYCLIC_MODULE_DEPENDENCY"
                                                                  []
                                                              ]
                                                            |)
                                                          ]
                                                      |)
                                                    |)
                                                  |)
                                                |)));
                                            fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                                          ]
                                        |)))
                                  ]
                                |) in
                              M.alloc (| Value.Tuple [] |)))
                          |)))
                    ]
                  |)) in
              M.alloc (| Value.StructTuple "core::result::Result::Ok" [ Value.Tuple [] ] |)
            |)))
        |)))
    | _, _, _ => M.impossible "wrong number of arguments"
    end.
  
  Axiom Function_verify_module_impl :
    M.IsFunction
      "move_bytecode_verifier::cyclic_dependencies::verify_module_impl"
      verify_module_impl.
  
  Module verify_module_impl.
    (*
        fn detect_cycles<D>(
            target: &ModuleId,
            cursor: &ModuleId,
            visited: &mut BTreeSet<ModuleId>,
            deps: &D,
        ) -> PartialVMResult<bool>
        where
            D: Fn(&ModuleId) -> PartialVMResult<Vec<ModuleId>>,
        {
            if cursor == target {
                return Ok(true);
            }
    
            if !visited.insert(cursor.clone()) {
                for dep in deps(cursor)? {
                    if detect_cycles(target, &dep, visited, deps)? {
                        return Ok(true);
                    }
                }
            }
    
            Ok(false)
        }
    *)
    Definition detect_cycles (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
      match ε, τ, α with
      | [], [ D ], [ target; cursor; visited; deps ] =>
        ltac:(M.monadic
          (let target := M.alloc (| target |) in
          let cursor := M.alloc (| cursor |) in
          let visited := M.alloc (| visited |) in
          let deps := M.alloc (| deps |) 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 (|
                                M.call_closure (|
                                  M.get_trait_method (|
                                    "core::cmp::PartialEq",
                                    Ty.apply
                                      (Ty.path "&")
                                      []
                                      [ Ty.path "move_core_types::language_storage::ModuleId" ],
                                    [
                                      Ty.apply
                                        (Ty.path "&")
                                        []
                                        [ Ty.path "move_core_types::language_storage::ModuleId" ]
                                    ],
                                    "eq",
                                    []
                                  |),
                                  [ cursor; target ]
                                |)
                              |)) 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.StructTuple "core::result::Result::Ok" [ Value.Bool true ]
                                |)
                              |)
                            |)
                          |)));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                let~ _ :=
                  M.match_operator (|
                    M.alloc (| Value.Tuple [] |),
                    [
                      fun γ =>
                        ltac:(M.monadic
                          (let γ :=
                            M.use
                              (M.alloc (|
                                UnOp.not (|
                                  M.call_closure (|
                                    M.get_associated_function (|
                                      Ty.apply
                                        (Ty.path "alloc::collections::btree::set::BTreeSet")
                                        []
                                        [
                                          Ty.path "move_core_types::language_storage::ModuleId";
                                          Ty.path "alloc::alloc::Global"
                                        ],
                                      "insert",
                                      []
                                    |),
                                    [
                                      M.read (| visited |);
                                      M.call_closure (|
                                        M.get_trait_method (|
                                          "core::clone::Clone",
                                          Ty.path "move_core_types::language_storage::ModuleId",
                                          [],
                                          "clone",
                                          []
                                        |),
                                        [ M.read (| cursor |) ]
                                      |)
                                    ]
                                  |)
                                |)
                              |)) in
                          let _ :=
                            M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                          M.use
                            (M.match_operator (|
                              M.alloc (|
                                M.call_closure (|
                                  M.get_trait_method (|
                                    "core::iter::traits::collect::IntoIterator",
                                    Ty.apply
                                      (Ty.path "alloc::vec::Vec")
                                      []
                                      [
                                        Ty.path "move_core_types::language_storage::ModuleId";
                                        Ty.path "alloc::alloc::Global"
                                      ],
                                    [],
                                    "into_iter",
                                    []
                                  |),
                                  [
                                    M.read (|
                                      M.match_operator (|
                                        M.alloc (|
                                          M.call_closure (|
                                            M.get_trait_method (|
                                              "core::ops::try_trait::Try",
                                              Ty.apply
                                                (Ty.path "core::result::Result")
                                                []
                                                [
                                                  Ty.apply
                                                    (Ty.path "alloc::vec::Vec")
                                                    []
                                                    [
                                                      Ty.path
                                                        "move_core_types::language_storage::ModuleId";
                                                      Ty.path "alloc::alloc::Global"
                                                    ];
                                                  Ty.path
                                                    "move_binary_format::errors::PartialVMError"
                                                ],
                                              [],
                                              "branch",
                                              []
                                            |),
                                            [
                                              M.call_closure (|
                                                M.get_trait_method (|
                                                  "core::ops::function::Fn",
                                                  D,
                                                  [
                                                    Ty.tuple
                                                      [
                                                        Ty.apply
                                                          (Ty.path "&")
                                                          []
                                                          [
                                                            Ty.path
                                                              "move_core_types::language_storage::ModuleId"
                                                          ]
                                                      ]
                                                  ],
                                                  "call",
                                                  []
                                                |),
                                                [
                                                  M.read (| deps |);
                                                  Value.Tuple [ M.read (| cursor |) ]
                                                ]
                                              |)
                                            ]
                                          |)
                                        |),
                                        [
                                          fun γ =>
                                            ltac:(M.monadic
                                              (let γ0_0 :=
                                                M.SubPointer.get_struct_tuple_field (|
                                                  γ,
                                                  "core::ops::control_flow::ControlFlow::Break",
                                                  0
                                                |) in
                                              let residual := M.copy (| γ0_0 |) in
                                              M.alloc (|
                                                M.never_to_any (|
                                                  M.read (|
                                                    M.return_ (|
                                                      M.call_closure (|
                                                        M.get_trait_method (|
                                                          "core::ops::try_trait::FromResidual",
                                                          Ty.apply
                                                            (Ty.path "core::result::Result")
                                                            []
                                                            [
                                                              Ty.path "bool";
                                                              Ty.path
                                                                "move_binary_format::errors::PartialVMError"
                                                            ],
                                                          [
                                                            Ty.apply
                                                              (Ty.path "core::result::Result")
                                                              []
                                                              [
                                                                Ty.path "core::convert::Infallible";
                                                                Ty.path
                                                                  "move_binary_format::errors::PartialVMError"
                                                              ]
                                                          ],
                                                          "from_residual",
                                                          []
                                                        |),
                                                        [ M.read (| residual |) ]
                                                      |)
                                                    |)
                                                  |)
                                                |)
                                              |)));
                                          fun γ =>
                                            ltac:(M.monadic
                                              (let γ0_0 :=
                                                M.SubPointer.get_struct_tuple_field (|
                                                  γ,
                                                  "core::ops::control_flow::ControlFlow::Continue",
                                                  0
                                                |) in
                                              let val := M.copy (| γ0_0 |) in
                                              val))
                                        ]
                                      |)
                                    |)
                                  ]
                                |)
                              |),
                              [
                                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 "alloc::vec::into_iter::IntoIter")
                                                    []
                                                    [
                                                      Ty.path
                                                        "move_core_types::language_storage::ModuleId";
                                                      Ty.path "alloc::alloc::Global"
                                                    ],
                                                  [],
                                                  "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 dep := M.copy (| γ0_0 |) in
                                                  M.match_operator (|
                                                    M.alloc (| Value.Tuple [] |),
                                                    [
                                                      fun γ =>
                                                        ltac:(M.monadic
                                                          (let γ :=
                                                            M.use
                                                              (M.match_operator (|
                                                                M.alloc (|
                                                                  M.call_closure (|
                                                                    M.get_trait_method (|
                                                                      "core::ops::try_trait::Try",
                                                                      Ty.apply
                                                                        (Ty.path
                                                                          "core::result::Result")
                                                                        []
                                                                        [
                                                                          Ty.path "bool";
                                                                          Ty.path
                                                                            "move_binary_format::errors::PartialVMError"
                                                                        ],
                                                                      [],
                                                                      "branch",
                                                                      []
                                                                    |),
                                                                    [
                                                                      M.call_closure (|
                                                                        M.get_function (|
                                                                          "move_bytecode_verifier::cyclic_dependencies::verify_module_impl.detect_cycles",
                                                                          []
                                                                        |),
                                                                        [
                                                                          M.read (| target |);
                                                                          dep;
                                                                          M.read (| visited |);
                                                                          M.read (| deps |)
                                                                        ]
                                                                      |)
                                                                    ]
                                                                  |)
                                                                |),
                                                                [
                                                                  fun γ =>
                                                                    ltac:(M.monadic
                                                                      (let γ0_0 :=
                                                                        M.SubPointer.get_struct_tuple_field (|
                                                                          γ,
                                                                          "core::ops::control_flow::ControlFlow::Break",
                                                                          0
                                                                        |) in
                                                                      let residual :=
                                                                        M.copy (| γ0_0 |) in
                                                                      M.alloc (|
                                                                        M.never_to_any (|
                                                                          M.read (|
                                                                            M.return_ (|
                                                                              M.call_closure (|
                                                                                M.get_trait_method (|
                                                                                  "core::ops::try_trait::FromResidual",
                                                                                  Ty.apply
                                                                                    (Ty.path
                                                                                      "core::result::Result")
                                                                                    []
                                                                                    [
                                                                                      Ty.path
                                                                                        "bool";
                                                                                      Ty.path
                                                                                        "move_binary_format::errors::PartialVMError"
                                                                                    ],
                                                                                  [
                                                                                    Ty.apply
                                                                                      (Ty.path
                                                                                        "core::result::Result")
                                                                                      []
                                                                                      [
                                                                                        Ty.path
                                                                                          "core::convert::Infallible";
                                                                                        Ty.path
                                                                                          "move_binary_format::errors::PartialVMError"
                                                                                      ]
                                                                                  ],
                                                                                  "from_residual",
                                                                                  []
                                                                                |),
                                                                                [
                                                                                  M.read (|
                                                                                    residual
                                                                                  |)
                                                                                ]
                                                                              |)
                                                                            |)
                                                                          |)
                                                                        |)
                                                                      |)));
                                                                  fun γ =>
                                                                    ltac:(M.monadic
                                                                      (let γ0_0 :=
                                                                        M.SubPointer.get_struct_tuple_field (|
                                                                          γ,
                                                                          "core::ops::control_flow::ControlFlow::Continue",
                                                                          0
                                                                        |) in
                                                                      let val :=
                                                                        M.copy (| γ0_0 |) in
                                                                      val))
                                                                ]
                                                              |)) 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.StructTuple
                                                                    "core::result::Result::Ok"
                                                                    [ Value.Bool true ]
                                                                |)
                                                              |)
                                                            |)
                                                          |)));
                                                      fun γ =>
                                                        ltac:(M.monadic
                                                          (M.alloc (| Value.Tuple [] |)))
                                                    ]
                                                  |)))
                                            ]
                                          |) in
                                        M.alloc (| Value.Tuple [] |)))
                                    |)))
                              ]
                            |))));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                M.alloc (| Value.StructTuple "core::result::Result::Ok" [ Value.Bool false ] |)
              |)))
          |)))
      | _, _, _ => M.impossible "wrong number of arguments"
      end.
    
    Axiom Function_detect_cycles :
      M.IsFunction
        "move_bytecode_verifier::cyclic_dependencies::verify_module_impl::detect_cycles"
        detect_cycles.
  End verify_module_impl.
End cyclic_dependencies.
