neiam /gitgud

defmodule GitGud.Merges do
  @moduledoc """
  Three-way merges that a human still has to finish.

  Everything else in the forge asks a merge one question — did it
  work? — and `GitGud.Git.merge_tree/4` answers it. This module answers
  the follow-up: *what* is in the way, and what would it take to resolve
  it in the browser.

  Two callers want that, and they are the same shape underneath:

    * a pull request whose merge into its target conflicts
    * a branch that moved both here and upstream (see
      `GitGud.Repositories.upstream_status/2`), where the reconcile
      sync deliberately stops

  So neither owns this. Both hand over two commits — ours and theirs —
  and get back the merge base, a written tree, and one entry per
  unresolved path carrying all three sides.

  Nothing here writes a ref or a commit. `analyze/3` is a read: it
  writes blobs and a tree into the object database (unreachable until
  something references them, and collectable if nothing ever does), and
  that is the whole of its effect.
  """

  alias GitGud.BranchProtections
  alias GitGud.Git
  alias GitGud.Repositories
  alias GitGud.Repositories.Repository

  # Both sides of a conflict are rendered in a browser. Past this, the
  # editor isn't the right tool and the answer is to resolve it locally,
  # so the content is left out rather than shipped to a page that would
  # choke on it.
  @max_editable_bytes 1_000_000

  @typedoc """
  One path the merge couldn't settle.

  `base` is `nil` when both sides added the path, `ours`/`theirs` when
  that side deleted it — the shape of the nils *is* the kind of
  conflict, and `type` names it the way git does ("content",
  "add/add", "modify/delete").

  `merged` is the marked-up three-way merge git produced, and is what
  the editor opens. It is absent for a conflict with no sensible text
  form: a binary file, or one side deleting what the other changed.
  """
  @type file :: %{
          path: String.t(),
          type: String.t(),
          base: side() | nil,
          ours: side() | nil,
          theirs: side() | nil,
          merged: side() | nil,
          binary?: boolean()
        }

  @typedoc "One side of one path. `text` is `nil` for binary or oversized blobs."
  @type side :: %{sha: Git.sha(), mode: String.t() | nil, size: integer(), text: String.t() | nil}

  @doc """
  Work out what merging `theirs` into `ours` would take.

  Returns `{:ok, analysis}` where `analysis.status` is `:clean` (the
  tree is ready to commit as-is) or `:conflict` (with `files`), or:

    * `{:error, :no_merge_base}` — unrelated histories, which is not a
      merge anyone should be offered a UI for
    * `{:error, reason}` from git
  """
  @spec analyze(Repository.t(), Git.sha(), Git.sha()) :: {:ok, map()} | {:error, term()}
  def analyze(%Repository{disk_path: path}, ours_sha, theirs_sha) do
    with {:ok, base_sha} <- merge_base(path, ours_sha, theirs_sha),
         {:ok, %{tree: tree, conflicts: conflicts}} <-
           Git.merge_analysis(path, base_sha, ours_sha, theirs_sha) do
      {:ok,
       %{
         status: if(conflicts == [], do: :clean, else: :conflict),
         base_sha: base_sha,
         ours_sha: ours_sha,
         theirs_sha: theirs_sha,
         tree: tree,
         files: Enum.map(conflicts, &describe(path, tree, &1))
       }}
    end
  end

  @doc """
  Finish a merge the analysis found conflicts in, and move a ref to it.

  `resolutions` is one entry per conflicted path:

      %{"lib/a.ex" => :ours,
        "lib/b.ex" => :theirs,
        "README.md" => {:text, "the edited file\n"}}

  Every conflicted path needs one. A partial resolution is refused
  rather than guessed at — `{:error, {:unresolved, paths}}` — because
  the alternative is committing a file with conflict markers in it,
  which is the exact failure this whole flow exists to prevent. For the
  same reason `{:text, _}` content is checked for markers before it is
  written.

  `:ours`/`:theirs` on a path that side deleted resolves to a deletion,
  which is what "take that side" means there.

  Branch protection applies exactly as it does to a push or a PR merge:
  resolving a conflict in a browser is still a ref update, and a rule
  that would refuse it there refuses it here.

  The ref update is conditional on `expected_old`, so a merge racing a
  push loses cleanly (`{:error, :concurrent_update}`) instead of
  overwriting it — same contract as `PullRequests.merge!/3`.
  """
  @spec resolve(Repository.t(), map(), map(), keyword()) ::
          {:ok, %{commit: Git.sha(), tree: Git.sha()}} | {:error, term()}
  def resolve(%Repository{disk_path: path} = repo, analysis, resolutions, opts) do
    ref = Keyword.fetch!(opts, :ref)
    expected_old = Keyword.get(opts, :expected_old, analysis.ours_sha)
    message = Keyword.get(opts, :message) || default_message(analysis)
    author = Keyword.get(opts, :author)

    with :ok <- ensure_complete(analysis, resolutions),
         :ok <- ensure_unmarked(resolutions),
         :ok <- check_protection(repo, ref, expected_old, analysis, opts),
         {:ok, changes} <- build_changes(path, analysis, resolutions),
         {:ok, tree} <- Git.write_tree_with(path, analysis.tree, changes),
         {:ok, commit} <-
           Git.commit_tree(
             path,
             tree,
             [analysis.ours_sha, analysis.theirs_sha],
             message,
             author: author
           ),
         :ok <- move_ref(repo, ref, commit, expected_old) do
      {:ok, %{commit: commit, tree: tree}}
    end
  end

  defp check_protection(repo, "refs/heads/" <> branch, expected_old, analysis, opts) do
    BranchProtections.check_ref_update(
      repo,
      branch,
      expected_old,
      analysis.theirs_sha,
      Keyword.take(opts, [:pull_request_id])
    )
  end

  # Anything outside refs/heads/ has no branch rule to check.
  defp check_protection(_repo, _ref, _expected_old, _analysis, _opts), do: :ok

  defp ensure_complete(%{files: files}, resolutions) do
    case Enum.reject(files, &Map.has_key?(resolutions, &1.path)) do
      [] -> :ok
      missing -> {:error, {:unresolved, Enum.map(missing, & &1.path)}}
    end
  end

  # A resolution that still carries markers is the failure mode this
  # flow exists to prevent, and it is cheap to refuse here rather than
  # discover in a `git blame` a month later.
  defp ensure_unmarked(resolutions) do
    marked =
      for {path, {:text, text}} <- resolutions,
          String.contains?(text, ["<<<<<<< ", ">>>>>>> "]),
          do: path

    case marked do
      [] -> :ok
      paths -> {:error, {:conflict_markers, paths}}
    end
  end

  defp build_changes(path, %{files: files}, resolutions) do
    Enum.reduce_while(files, {:ok, %{}}, fn file, {:ok, acc} ->
      case change_for(path, file, Map.fetch!(resolutions, file.path)) do
        {:ok, change} -> {:cont, {:ok, Map.put(acc, file.path, change)}}
        err -> {:halt, err}
      end
    end)
  end

  defp change_for(_path, file, :ours), do: {:ok, side_change(file.ours)}
  defp change_for(_path, file, :theirs), do: {:ok, side_change(file.theirs)}

  defp change_for(path, file, {:text, text}) do
    case Git.write_blob(path, text) do
      {:ok, sha} -> {:ok, {sha, mode_of(file)}}
      err -> err
    end
  end

  defp change_for(_path, file, other),
    do: {:error, {:bad_resolution, file.path, other}}

  # Taking a side that deleted the path means deleting it.
  defp side_change(nil), do: :delete
  defp side_change(%{sha: sha, mode: mode}), do: {sha, mode || "100644"}

  # Keep whichever mode the sides agree on; an executable bit shouldn't
  # be lost to a resolution.
  defp mode_of(file) do
    [file.ours, file.theirs, file.base, file.merged]
    |> Enum.find_value("100644", fn side -> side && side.mode end)
  end

  defp default_message(%{theirs_sha: theirs}),
    do: "Merge #{Git.short(theirs)}, resolving conflicts"

  defp move_ref(%Repository{disk_path: path} = repo, ref, commit, expected_old) do
    case Git.update_ref(path, ref, commit, expected_old) do
      :ok ->
        # Keep the ref cache in step without waiting for post-receive,
        # the way the fork sync and PR merge paths do.
        :ok = Repositories.apply_ref_update(repo, ref, expected_old, commit)
        :ok

      {:error, _} ->
        # git refuses the update when the ref has moved since; that is
        # the only expected failure here, and it is not ours to force.
        {:error, :concurrent_update}
    end
  end

  defp merge_base(path, ours, theirs) do
    case Git.merge_base(path, ours, theirs) do
      {:ok, base} -> {:ok, base}
      {:error, :not_found} -> {:error, :no_merge_base}
      err -> err
    end
  end

  defp describe(path, tree, conflict) do
    sides =
      Map.new([:base, :ours, :theirs], fn side ->
        {side, load_side(path, Map.get(conflict, side), get_in(conflict, [:modes, side]))}
      end)

    merged = load_merged(path, tree, conflict.path)

    # "Binary" is a property of the conflict, not of one side: a side
    # that is absent says nothing, and one binary side is enough to make
    # the text editor the wrong tool.
    binary? =
      [sides.base, sides.ours, sides.theirs, merged]
      |> Enum.reject(&is_nil/1)
      |> Enum.any?(&is_nil(&1.text))

    %{
      path: conflict.path,
      type: conflict.type,
      base: sides.base,
      ours: sides.ours,
      theirs: sides.theirs,
      merged: merged,
      binary?: binary?
    }
  end

  defp load_side(_path, nil, _mode), do: nil

  defp load_side(path, sha, mode) do
    case Git.blob_meta(path, sha) do
      {:ok, %{size: size, is_binary: is_binary}} ->
        %{sha: sha, mode: mode, size: size, text: text_of(path, sha, size, is_binary)}

      _ ->
        nil
    end
  end

  # The conflicted path inside the written tree: git's own marked-up
  # merge, which beats reconstructing markers ourselves.
  defp load_merged(path, tree, file_path) do
    case Git.tree_entry_at(path, tree, file_path) do
      {:ok, %{sha: sha, mode: mode}} -> load_side(path, sha, mode)
      _ -> nil
    end
  end

  defp text_of(_path, _sha, size, _binary) when size > @max_editable_bytes, do: nil
  defp text_of(_path, _sha, _size, true), do: nil

  defp text_of(path, sha, _size, false) do
    case Git.blob_bytes(path, sha) do
      {:ok, bytes} -> if String.valid?(bytes), do: bytes, else: nil
      _ -> nil
    end
  end
end