cachex_test.exs

defmodule Lockstep.CachexTest do
  @moduledoc """
  Model-based linearizability test against `Cachex` (~1.5M downloads,
  whitfin/cachex). The first canonical "Generator + History + Model
  + Checker.Linearizable" template — a shape we can reuse on every
  battle-tested BEAM lib.

  ## What this tests

  Single-key concurrent operations (get / put / del / incr / take)
  across N workers, against a `Map`-backed reference model. Each
  iteration runs a fresh shuffled history; linearizability is checked
  at the end against the sequential model.

  ## Architecture caveat (v1)

  Cachex itself is NOT compiled through `Lockstep.MixCompiler` — it
  has 5 deps and heavy macros, so we use the unmodified Hex artifact.
  Workers run as `Lockstep.Task.async/1` and the History/Linearizable
  pipeline is fully Lockstep-driven, but Cachex's internals (router,
  locksmith, ETS) execute on the real BEAM scheduler. We get
  randomized real-time interleavings + model-based correctness
  checking, but not deep PCT exploration of Cachex internals. That's
  a step up from where we started ("hypothesize from source") and a
  step short of "rewrite the world".
  """

  use ExUnit.Case, async: false

  @cache :cachex_test

  defmodule CacheModel do
    @moduledoc """
    Map-backed reference model for the subset of Cachex ops we drive.

    State is `%{key => value}`. Each op kind has a `step/3` clause
    that either confirms the completion is consistent with state and
    returns the new state, or returns `{:error, reason}` to reject
    that linearization order.
    """

    @behaviour Lockstep.Model

    alias Lockstep.History.Event

    @impl true
    def init, do: %{}

    @impl true
    def step(state, %Event{f: :get, value: k}, %Event{type: :ok, value: v}) do
      expected = Map.get(state, k)

      if expected == v do
        {:ok, state}
      else
        {:error, "get(#{inspect(k)}) returned #{inspect(v)} but model has #{inspect(expected)}"}
      end
    end

    def step(state, %Event{f: :put, value: {k, v}}, %Event{type: :ok}) do
      {:ok, Map.put(state, k, v)}
    end

    def step(state, %Event{f: :del, value: k}, %Event{type: :ok}) do
      {:ok, Map.delete(state, k)}
    end

    def step(state, %Event{f: :take, value: k}, %Event{type: :ok, value: v}) do
      expected = Map.get(state, k)

      if expected == v do
        {:ok, Map.delete(state, k)}
      else
        {:error, "take(#{inspect(k)}) returned #{inspect(v)} but model has #{inspect(expected)}"}
      end
    end

    def step(state, %Event{f: :incr, value: {k, amount}}, %Event{type: :ok, value: new_v}) do
      old = Map.get(state, k, 0)
      expected = old + amount

      if new_v == expected do
        {:ok, Map.put(state, k, new_v)}
      else
        {:error,
         "incr(#{inspect(k)}, #{amount}) returned #{new_v}; expected #{expected} (old=#{inspect(old)})"}
      end
    end

    # get_and_update modeled as +1 R-M-W. The completion's `value` is
    # the {:commit, new_v} tuple Cachex actually returned.
    def step(state, %Event{f: :gau_inc, value: k}, %Event{type: :ok, value: {:commit, new_v}}) do
      old = Map.get(state, k, 0)

      if new_v == old + 1 do
        {:ok, Map.put(state, k, new_v)}
      else
        {:error,
         "get_and_update(#{inspect(k)}, +1) returned #{new_v}; expected #{old + 1} (lost update?)"}
      end
    end

    def step(state, _invoke, %Event{type: :fail}), do: {:ok, state}
    def step(state, _invoke, %Event{type: :info}), do: {:ok, state}
  end

  setup_all do
    case Cachex.start_link(@cache, []) do
      {:ok, _} -> :ok
      {:error, {:already_started, _}} -> :ok
    end

    :ok
  end

  test "linearizability of single-key concurrent ops on default Cachex" do
    Lockstep.Runner.run(
      &mixed_ops_body/0,
      iterations: 200,
      strategy: :pct,
      max_steps: 5_000,
      seed: 1,
      iter_timeout: 30_000,
      progress: 25,
      suite: "cachex_lin_single_key"
    )
  end

  test "linearizability of concurrent get_and_update (R-M-W lost-update test)" do
    Lockstep.Runner.run(
      &gau_body/0,
      iterations: 500,
      strategy: :pct,
      max_steps: 5_000,
      seed: 1,
      iter_timeout: 30_000,
      progress: 50,
      suite: "cachex_gau_rmw"
    )
  end

  test "linearizability of multi-key concurrent ops (cross-key isolation)" do
    Lockstep.Runner.run(
      &multi_key_body/0,
      iterations: 200,
      strategy: :pct,
      max_steps: 10_000,
      seed: 1,
      iter_timeout: 30_000,
      progress: 25,
      suite: "cachex_lin_multi_key"
    )
  end

  defp mixed_ops_body do
    {:ok, _} = Cachex.clear(@cache)
    history = Lockstep.History.start_link!()

    n_workers = 6
    ops_per_worker = 8

    workers =
      for w <- 1..n_workers do
        Lockstep.Task.async(fn ->
          gen =
            Lockstep.Generator.weighted(
              [
                {{:get, "k"}, 4},
                {{:put, "k", w * 100 + 1}, 2},
                {{:put, "k", w * 100 + 2}, 1},
                {{:del, "k"}, 1},
                {{:incr, "k", 1}, 2},
                {{:take, "k"}, 1}
              ],
              seed: w * 1_000_003
            )
            |> Lockstep.Generator.take(ops_per_worker)

          Lockstep.Generator.each(gen, fn op -> apply_op(history, op) end)
        end)
      end

    Lockstep.Task.await_many(workers, 30_000)

    check_linearizable(history)
  end

  defp gau_body do
    # Counter starts at 0; every worker does get_and_update(+1).
    # If get_and_update is properly transactional, total ops = final value.
    {:ok, _} = Cachex.clear(@cache)
    {:ok, true} = Cachex.put(@cache, "counter", 0)
    history = Lockstep.History.start_link!()

    n_workers = 6
    ops_per_worker = 5

    workers =
      for _w <- 1..n_workers do
        Lockstep.Task.async(fn ->
          for _ <- 1..ops_per_worker do
            apply_op(history, {:gau_inc, "counter"})
          end
        end)
      end

    Lockstep.Task.await_many(workers, 30_000)

    check_linearizable(history)

    # Sanity: final value should equal n_workers * ops_per_worker if no
    # lost updates. (This is an extra check on top of linearizability.)
    {:ok, final} = Cachex.get(@cache, "counter")
    expected = n_workers * ops_per_worker

    if final != expected do
      raise "lost updates detected: final counter = #{final}, expected #{expected}"
    end
  end

  defp multi_key_body do
    {:ok, _} = Cachex.clear(@cache)
    history = Lockstep.History.start_link!()

    keys = ["k1", "k2", "k3", "k4"]
    n_workers = 6
    ops_per_worker = 8

    workers =
      for w <- 1..n_workers do
        Lockstep.Task.async(fn ->
          ops_pool =
            for k <- keys, op <- [:get, :put, :del, :incr, :take, :gau_inc] do
              case op do
                :get -> {:get, k}
                :put -> {:put, k, w * 100}
                :del -> {:del, k}
                :incr -> {:incr, k, 1}
                :take -> {:take, k}
                :gau_inc -> {:gau_inc, k}
              end
            end

          gen =
            ops_pool
            |> Lockstep.Generator.random(seed: w * 1_000_003)
            |> Lockstep.Generator.take(ops_per_worker)

          Lockstep.Generator.each(gen, fn op -> apply_op(history, op) end)
        end)
      end

    Lockstep.Task.await_many(workers, 30_000)
    check_linearizable(history)
  end

  defp check_linearizable(history) do
    events = Lockstep.History.events(history)

    case Lockstep.Checker.Linearizable.check(events, CacheModel) do
      {:ok, _} ->
        :ok

      {:error, info} ->
        msg = Lockstep.Checker.Linearizable.format_violation(info)
        raise "non-linearizable history found:\n\n#{msg}"
    end
  end

  defp apply_op(history, {:get, k}) do
    Lockstep.History.op(history, :get, k, fn ->
      {:ok, v} = Cachex.get(@cache, k)
      v
    end)
  end

  defp apply_op(history, {:put, k, v}) do
    Lockstep.History.op(history, :put, {k, v}, fn ->
      {:ok, true} = Cachex.put(@cache, k, v)
      :ok
    end)
  end

  defp apply_op(history, {:del, k}) do
    Lockstep.History.op(history, :del, k, fn ->
      {:ok, _} = Cachex.del(@cache, k)
      :ok
    end)
  end

  defp apply_op(history, {:take, k}) do
    Lockstep.History.op(history, :take, k, fn ->
      {:ok, v} = Cachex.take(@cache, k)
      v
    end)
  end

  defp apply_op(history, {:incr, k, amount}) do
    Lockstep.History.op(history, :incr, {k, amount}, fn ->
      {:ok, new_v} = Cachex.incr(@cache, k, amount)
      new_v
    end)
  end

  defp apply_op(history, {:gau_inc, k}) do
    Lockstep.History.op(history, :gau_inc, k, fn ->
      Cachex.get_and_update(@cache, k, fn
        nil -> 1
        n when is_integer(n) -> n + 1
      end)
    end)
  end
end