defmodule MST.InteropTest do
  @moduledoc """
  Interoperability tests using fixtures from atproto-interop-tests and
  jacquard's additional edge-case vectors.

  Fixture sources:
  - https://github.com/bluesky-social/atproto-interop-tests/tree/main/mst
  - https://github.com/orual/jacquard (tests/fixtures/)

  Covers:
  - 156 real-world-shaped keys: full insert, selective delete, insertion-order
    determinism.
  - 5 commit-proof CID-exact scenarios stressing height-gap splits, leafless
    splits, edge inserts, and merge-then-split sequences.
  - The "rsky" 2-key tree regression from rsky's
    `handle_new_layers_that_are_two_higher_than_existing` test.
  - Trees spanning heights 0–8 to exercise multi-level intermediate empty
    nodes.
  """

  use ExUnit.Case, async: true

  alias DASL.CID
  alias MST.Tree

  @fixture_dir Path.join([__DIR__, "..", "fixtures", "interop"])

  # 156 keys of the form "X{level}/{number}" where each key's MST height
  # matches the digit in the name (generated by atproto-interop-tests/mst/gen_keys.py).
  @example_keys Path.join(@fixture_dir, "example_keys.txt")
                |> File.read!()
                |> String.split("\n", trim: true)

  # Stable key→CID mapping reused across example-key tests so that insertion
  # order doesn't affect which value a key maps to.
  @example_kv Map.new(Enum.with_index(@example_keys), fn {k, i} ->
                {k, CID.compute(<<i::8>>, :raw)}
              end)

  # 5 commit-proof scenarios; each specifies an initial key set, a batch of
  # adds/deletes, and the expected root CIDs before and after.
  @commit_proof Path.join(@fixture_dir, "commit_proof.json")
                |> File.read!()
                |> Jason.decode!()

  defp new_tree, do: Tree.new(MST.Store.Memory.new())

  # ---------------------------------------------------------------------------
  # Example keys — insert / delete / determinism
  # ---------------------------------------------------------------------------

  describe "example keys" do
    @tag :slow
    test "insert all keys and retrieve each" do
      tree =
        Enum.reduce(@example_keys, new_tree(), fn key, acc ->
          {:ok, t} = Tree.put(acc, key, @example_kv[key])
          t
        end)

      for key <- @example_keys do
        assert {:ok, @example_kv[key]} == Tree.get(tree, key),
               "key not found after insert: #{key}"
      end

      assert {:ok, count} = Tree.length(tree)
      assert count == length(@example_keys)
    end

    @tag :slow
    test "delete every other key; correct half remains" do
      tree =
        Enum.reduce(@example_keys, new_tree(), fn key, acc ->
          {:ok, t} = Tree.put(acc, key, @example_kv[key])
          t
        end)

      indexed = Enum.with_index(@example_keys)
      {evens, odds} = Enum.split_with(indexed, fn {_, i} -> rem(i, 2) == 0 end)

      tree =
        Enum.reduce(evens, tree, fn {key, _}, acc ->
          {:ok, t} = Tree.delete(acc, key)
          t
        end)

      for {key, _} <- evens do
        assert {:error, :not_found} == Tree.get(tree, key),
               "deleted key still present: #{key}"
      end

      for {key, _} <- odds do
        assert {:ok, @example_kv[key]} == Tree.get(tree, key),
               "surviving key not found: #{key}"
      end

      assert {:ok, remaining} = Tree.length(tree)
      assert remaining == length(odds)
    end

    @tag :slow
    test "root CID is identical regardless of insertion order" do
      forward =
        Enum.reduce(@example_keys, new_tree(), fn key, acc ->
          {:ok, t} = Tree.put(acc, key, @example_kv[key])
          t
        end)

      reverse =
        Enum.reduce(Enum.reverse(@example_keys), new_tree(), fn key, acc ->
          {:ok, t} = Tree.put(acc, key, @example_kv[key])
          t
        end)

      assert forward.root == reverse.root,
             "insertion order changed root CID"
    end

    @tag :slow
    test "delete all keys produces empty tree" do
      tree =
        Enum.reduce(@example_keys, new_tree(), fn key, acc ->
          {:ok, t} = Tree.put(acc, key, @example_kv[key])
          t
        end)

      empty =
        Enum.reduce(@example_keys, tree, fn key, acc ->
          {:ok, t} = Tree.delete(acc, key)
          t
        end)

      assert {:ok, []} = Tree.to_list(empty)
      assert empty.root == nil
    end
  end

  # ---------------------------------------------------------------------------
  # Commit-proof fixtures — CID-exact spec vectors
  # ---------------------------------------------------------------------------

  describe "commit proof fixtures" do
    # Each fixture drives a scenario that would catch specific structural bugs:
    #
    #   "two deep split"              — height-2 insert between height-1 nodes,
    #                                   requires two levels of intermediate empties.
    #   "two deep leafless split"     — height-2 insert with no height-1 nodes
    #                                   anywhere near the split point.
    #   "add on edge with neighbor two layers down"
    #                                 — new height-2 key adjacent to a subtree
    #                                   whose highest key is 2 levels lower.
    #   "merge and split in multi-op" — simultaneous adds and deletes; the
    #                                   merge path (delete) and split path
    #                                   (insert) both execute.
    #   "complex multi-op commit"     — larger batch with both creates and
    #                                   deletes across multiple height levels.

    for fixture <- @commit_proof do
      @fixture fixture
      test @fixture["comment"] do
        run_commit_proof_fixture(@fixture)
      end
    end
  end

  # ---------------------------------------------------------------------------
  # rsky edge case — 2-key tree with a known root CID
  # ---------------------------------------------------------------------------

  describe "rsky simple case" do
    # Regression from rsky's `handle_new_layers_that_are_two_higher_than_existing`.
    # Two height-0 keys (same collection prefix) that differ only in their last
    # few chars. The expected root CID is taken from the reference TypeScript
    # implementation.
    test "two height-0 keys produce the known root CID" do
      {:ok, leaf} = CID.new("bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454")

      {:ok, tree} = Tree.put(new_tree(), "com.example.record/3jqfcqzm3ft2j", leaf)
      {:ok, tree} = Tree.put(tree, "com.example.record/3jqfcqzm3fz2j", leaf)

      assert CID.encode(tree.root) ==
               "bafyreidfcktqnfmykz2ps3dbul35pepleq7kvv526g47xahuz3rqtptmky"
    end
  end

  # ---------------------------------------------------------------------------
  # Multi-height trees — spec keys spanning heights 0–8
  # ---------------------------------------------------------------------------

  describe "keys spanning multiple heights" do
    # Keys taken directly from the atproto spec and key_heights.json; each has
    # a well-known height. Together they force intermediate empty nodes at every
    # level from 0 up to the maximum height.
    @spec_keys [
      {"2653ae71", 0},
      {"blue", 1},
      {"88bfafc7", 2},
      {"2a92d355", 4},
      {"884976f5", 6},
      {"app.bsky.feed.post/9adeb165882c", 8}
    ]

    test "insert keys at heights 0/1/2/4/6/8 — all retrievable" do
      val = CID.compute("v", :raw)

      tree =
        Enum.reduce(@spec_keys, new_tree(), fn {key, _}, acc ->
          {:ok, t} = Tree.put(acc, key, val)
          t
        end)

      for {key, _} <- @spec_keys do
        assert {:ok, ^val} = Tree.get(tree, key), "not found: #{key}"
      end

      assert {:ok, n} = Tree.length(tree)
      assert n == length(@spec_keys)
    end

    test "delete the height-4 key; other heights unaffected" do
      val = CID.compute("v", :raw)

      tree =
        Enum.reduce(@spec_keys, new_tree(), fn {key, _}, acc ->
          {:ok, t} = Tree.put(acc, key, val)
          t
        end)

      {del_key, _} = Enum.find(@spec_keys, fn {_, h} -> h == 4 end)
      {:ok, tree} = Tree.delete(tree, del_key)

      assert {:error, :not_found} = Tree.get(tree, del_key)

      for {key, _} <- @spec_keys, key != del_key do
        assert {:ok, ^val} = Tree.get(tree, key), "not found after delete: #{key}"
      end
    end

    test "root CID is stable regardless of insertion order" do
      val = CID.compute("v", :raw)
      keys = Enum.map(@spec_keys, &elem(&1, 0))

      forward =
        Enum.reduce(keys, new_tree(), fn key, acc ->
          {:ok, t} = Tree.put(acc, key, val)
          t
        end)

      reverse =
        Enum.reduce(Enum.reverse(keys), new_tree(), fn key, acc ->
          {:ok, t} = Tree.put(acc, key, val)
          t
        end)

      assert forward.root == reverse.root
    end

    test "full delete cycle returns to empty" do
      val = CID.compute("v", :raw)
      keys = Enum.map(@spec_keys, &elem(&1, 0))

      tree =
        Enum.reduce(keys, new_tree(), fn key, acc ->
          {:ok, t} = Tree.put(acc, key, val)
          t
        end)

      empty =
        Enum.reduce(keys, tree, fn key, acc ->
          {:ok, t} = Tree.delete(acc, key)
          t
        end)

      assert {:ok, []} = Tree.to_list(empty)
      assert empty.root == nil
    end
  end

  # ---------------------------------------------------------------------------
  # Helpers
  # ---------------------------------------------------------------------------

  defp run_commit_proof_fixture(fixture) do
    {:ok, leaf} = CID.new(fixture["leafValue"])

    before_tree =
      Enum.reduce(fixture["keys"], new_tree(), fn key, acc ->
        {:ok, t} = Tree.put(acc, key, leaf)
        t
      end)

    assert CID.encode(before_tree.root) == fixture["rootBeforeCommit"],
           ~s(root before commit: expected #{fixture["rootBeforeCommit"]}, ) <>
             ~s(got #{CID.encode(before_tree.root)})

    after_tree =
      before_tree
      |> then(fn t ->
        Enum.reduce(fixture["adds"], t, fn key, acc ->
          {:ok, t2} = Tree.put(acc, key, leaf)
          t2
        end)
      end)
      |> then(fn t ->
        Enum.reduce(fixture["dels"], t, fn key, acc ->
          {:ok, t2} = Tree.delete(acc, key)
          t2
        end)
      end)

    assert CID.encode(after_tree.root) == fixture["rootAfterCommit"],
           ~s(root after commit: expected #{fixture["rootAfterCommit"]}, ) <>
             ~s(got #{CID.encode(after_tree.root)})
  end
end