Learning Elixir: Transaction History Properties

History.ex

defmodule History do
  @type op :: {ta(), cmd(), data()}
  @type ta :: any() 
  @type cmd :: :read | :write | :commit | :abort
  @type data :: any()

  @doc """
  Parses a textual representation of a history into a list of operation tuples.

  ## Examples

      iex> hist = History.from_string "r4[x], r4[y], r2[y], r3[x], w3[z], w4[x], w1[x], w1[z], r1[z], c4, c3, r2[y], c2, c1"
      [{"4", :read, "x"}, {"4", :read, "y"}, {"2", :read, "y"}, {"3", :read, "x"},
       {"3", :write, "z"}, {"4", :write, "x"}, {"1", :write, "x"}, {"1", :write, "z"},
       {"1", :read, "z"}, {"4", :commit, nil}, {"3", :commit, nil}, {"2", :read, "y"},
       {"2", :commit, nil}, {"1", :commit, nil}]
      iex> History.recoverable? hist
      true

  """
  @spec from_string(String.t()) :: [op()]
  def from_string(input) do
    input
    |> String.splitter(",", [trim: true])
    |> Enum.map(fn token ->
      op = Regex.named_captures(~r/(?<cmd>[rwca])(?<ta>[\d])(\[(?<data>.+)\])?/, token)
      case op do
        %{"cmd" => "c"} -> {op["ta"], :commit, nil}
        %{"cmd" => "a"} -> {op["ta"], :abort, nil}
        %{"cmd" => "r"} -> {op["ta"], :read, op["data"]}
        %{"cmd" => "w"} -> {op["ta"], :write, op["data"]}
      end
    end)
  end

  @doc """
  Turns a history into a textual representation.

  ## Examples
    
      iex> History.to_string [{"4", :read, "x"}, {"4", :read, "y"}, {"2", :read, "y"}, {"3", :read, "x"},
      ...>  {"3", :write, "z"}, {"4", :write, "x"}, {"1", :write, "x"}, {"1", :write, "z"},
      ...>  {"1", :read, "z"}, {"4", :commit, nil}, {"3", :commit, nil}, {"2", :read, "y"},
      ...>  {"2", :commit, nil}, {"1", :commit, nil}]
      "r4[x], r4[y], r2[y], r3[x], w3[z], w4[x], w1[x], w1[z], r1[z], c4, c3, r2[y], c2, c1"

      iex> input = "r4[x], r4[y], r2[y], r3[x], w3[z], w4[x], w1[x], w1[z], r1[z], c4, c3, r2[y], c2, c1"
      ...> input
      ...> |> History.from_string
      ...> |> History.to_string === input
      true

  """
  @spec to_string([op()]) :: String.t()
  def to_string(history) do
    history
    |> Enum.map(fn cmd ->
      case cmd do
        {ta, :commit, nil} -> "c" <> ta
        {ta, :abort, nil}  -> "a" <> ta
        {ta, :read, data}  -> "r" <> ta <> "[" <> data <> "]"
        {ta, :write, data} -> "w" <> ta <> "[" <> data <> "]"
      end
    end)
    |> Enum.join(", ")
  end

  @doc """
  Checks if a given transaction history is recoverable.

  ## Examples

      iex> History.recoverable? [
      ...>   {:t1, :write, :bla},
      ...>   {:t2, :read, :bla},
      ...>   {:t1, :commit, nil},
      ...>   {:t2, :commit, nil}
      ...> ]
      true

      iex> History.recoverable? [
      ...>   {:t1, :write, :bla},
      ...>   {:t2, :read, :bla},
      ...>   {:t2, :commit, nil}, # notice t2 commiting before t1!
      ...>   {:t1, :commit, nil}
      ...> ]
      false

  """
  @spec recoverable?([op()]) :: boolean()
  def recoverable?(history) do
    # for all read operations...
    history
    |> Enum.with_index
    |> Enum.filter(&(elem(elem(&1, 0), 1) === :read))
    |> Enum.all?(fn {{ta, :read, data}, idx} ->
      # ...check if all TAs this TA reads from commit before our TA
      history
      |> Enum.take(idx)
      |> ta_being_read_from(ta, data)
      |> Enum.all?(&(commits_before?(history, &1, ta)))
    end)
  end

  @doc """
  Get a TA that `ref_ta` reads from on the `ref_data` attribute and where the
  corresponding write has happened before `stop_idx` within the (partial) history.

  Returned list can have a maximum length of one, because later writes to a
  datum are "override" previous ones.
  """
  @spec ta_being_read_from([op()], ta(), data()) :: [ta()] | []
  def ta_being_read_from(history, ref_ta, ref_data) do
    history
    |> only_writes
    |> Enum.reverse
    |> Enum.find(fn {ta, :write, data} ->
      ta !== ref_ta
        and data === ref_data
        and MapSet.member?(winner_tas(history), ta)
    end)
    |> List.wrap
    |> Enum.map(&(elem(&1, 0)))
  end

  def all_tas(history) do
    history
    |> Enum.map(&(elem(&1, 0)))
    |> Enum.uniq
    |> MapSet.new
  end

  def loser_tas(history) do
    history
    |> all_tas
    |> Enum.filter(&(ta_aborts?(history, &1)))
    |> MapSet.new
  end

  def winner_tas(history) do
    history
    |> all_tas
    |> MapSet.difference(loser_tas(history))
  end

  @doc """
  Returns whether t1 commits before t2 within a (partial) history.

  ## Examples

      iex> hist = [{:t1, :read, :a}, {:t1, :commit, nil}, {:t2, :commit, nil}]
      iex> History.commits_before? hist, :t1, :t2
      true
      iex> History.commits_before? hist, :t2, :t1
      false
      iex> History.commits_before? hist, :t1, :t1
      false

  """
  @spec commits_before?([op()], ta(), ta()) :: boolean()
  def commits_before?(history, t1, t2) do
    t1_commit_index = commit_index(history, t1) || abort_index(history, t1) || Enum.count(history)
    t2_commit_index = commit_index(history, t2) || abort_index(history, t2) || Enum.count(history)
    t1_commit_index < t2_commit_index
  end
  
  @spec ta_aborts?([op()], ta()) :: boolean()
  def ta_aborts?(history, ta) do
    abort_index(history, ta) !== nil
  end

  def abort_index(history, ta) do
    history |> Enum.find_index(fn {tta, cmd, _} -> tta === ta and cmd === :abort end)
  end

  def commit_index(history, ta) do
    history |> Enum.find_index(fn {tta, cmd, _} -> tta === ta and cmd === :commit end)
  end

  def only_writes(history) do
    only_cmd(history, :write)
  end

  def only_reads(history) do
    only_cmd(history, :read)
  end

  @spec only_cmd([op()], cmd()) :: [op()]
  defp only_cmd(history, cmd) do
    Enum.filter(history, &(elem(&1, 1) === cmd))
  end
end