defmodule Dmp.Patch do
  @moduledoc """
  Apply a list of patches onto plain text. Use best effort to apply
  patch even when the underlying text doesn't match.
  """

  import Dmp.StringUtils

  alias Dmp.{Cursor, Diff, Match, Options}

  alias __MODULE__

  defstruct diffs: [], start1: 0, start2: 0, length1: 0, length2: 0

  @type t() :: %Patch{
          diffs: Diff.difflist(),
          start1: non_neg_integer(),
          start2: non_neg_integer(),
          length1: non_neg_integer(),
          length2: non_neg_integer()
        }
  @type patchlist() :: list(t())
  @type options() :: Options.t()

  defimpl String.Chars, for: Patch do
    @doc """
    Emulate GNU diff's format:

    ```
    @@ -382,8 +481,9 @@
    +change
     same

    ```

    Indices are printed as 1-based, not 0-based.
    """
    def to_string(%Patch{
          diffs: diffs,
          start1: start1,
          start2: start2,
          length1: length1,
          length2: length2
        }) do
      coords1 = patch_location(start1, length1)
      coords2 = patch_location(start2, length2)
      header = "@@ -#{coords1} +#{coords2} @@\n"
      # Escape the body of the patch with %xx notation.
      diffs
      |> Enum.reduce(header, fn diff, acc -> append_diff_contents(diff, acc) end)
      |> unescape_for_encode_uri_compatability()
    end

    defp patch_location(start, length) do
      case length do
        0 ->
          "#{start},0"

        1 ->
          "#{start + 1}"

        _ ->
          "#{start + 1},#{length}"
      end
    end

    defp append_diff_contents({op, text}, acc) do
      op_text =
        case op do
          :insert ->
            "+"

          :delete ->
            "-"

          :equal ->
            " "

          _ ->
            raise RuntimeError, "Invalid operation #{inspect(op)}"
        end

      text = uri_encode(text)
      acc <> op_text <> text <> "\n"
    end
  end

  @doc """
  Increase the context until it is unique,
  but don't let the pattern expand beyond match_max_bits.

    * `patch` - The `Patch` to grow.
    * `text` - Source text.
    * `patch_margin` - Chunk size for context length.
    * `match_max_bits` - The number of bits in an integer (default is expected 32).

  Returns the updated `Patch`.
  """
  @spec add_context(t(), String.t(), non_neg_integer(), non_neg_integer()) :: t()
  def add_context(patch, text, patch_margin, match_max_bits \\ 32)
  def add_context(patch, "", _patch_margin, _match_max_bits), do: patch

  def add_context(
        %Patch{} = patch,
        text,
        patch_margin,
        match_max_bits
      ) do
    pattern = substring(text, patch.start2, patch.start2 + patch.length1)
    {padding, _pattern} = increase_padding(0, pattern, patch, text, patch_margin, match_max_bits)

    prefix = substring(text, max(0, patch.start2 - padding), patch.start2)
    prefix_length = String.length(prefix)

    patch =
      if prefix_length != 0 do
        # Add the prefix.
        %Patch{patch | diffs: [{:equal, prefix} | patch.diffs]}
      else
        patch
      end

    suffix =
      substring(
        text,
        patch.start2 + patch.length1,
        patch.start2 + patch.length1 + padding
      )

    suffix_length = String.length(suffix)

    patch =
      if suffix_length != 0 do
        # Add the suffix.
        %Patch{patch | diffs: patch.diffs ++ [{:equal, suffix}]}
      else
        patch
      end

    # Roll back the start points.
    # Extend lengths.
    %Patch{
      patch
      | start1: patch.start1 - prefix_length,
        start2: patch.start2 - prefix_length,
        length1: patch.length1 + prefix_length + suffix_length,
        length2: patch.length2 + prefix_length + suffix_length
    }
  end

  defp increase_padding(padding, pattern, patch, text, patch_margin, match_max_bits) do
    # Look for the first and last matches of pattern in text.  If two different
    # matches are found, increase the pattern length.
    if index_of(text, pattern) != last_index_of(text, pattern) &&
         (match_max_bits == 0 ||
            String.length(pattern) < match_max_bits - patch_margin * 2) do
      padding = padding + patch_margin

      pattern =
        substring(
          text,
          max(0, patch.start2 - padding),
          patch.start2 + patch.length1 + padding
        )

      increase_padding(padding, pattern, patch, text, patch_margin, match_max_bits)
    else
      # Add one chunk for good luck.
      {padding + patch_margin, pattern}
    end
  end

  @doc """
  Compute a list of patches to turn `text1` into `text2`. `text1` will be derived
  from the provided diffs.

    * `diffs` - A difflist from `text1` to `text2`.
    * `opts` - A options keyword list, `[]` to use the default options.

  Returns a patchlist.
  """
  @spec from_diffs(Diff.difflist(), options()) :: patchlist()
  def from_diffs(diffs, opts \\ []) do
    # No origin string provided, compute our own.
    text1 = Diff.text1(diffs)
    make(text1, diffs, opts)
  end

  @doc """
  Deprecated

  Compute a list of patches to turn `text1` into `text2`. `text2` is ignored.
  `diffs` are the delta between text1 and text2.

    * `text1` - Old text.
    * `text2` - Ignored.
    * `diffs` - A difflist from `text1` to `text2`.
    * `opts` - A options keyword list, `[]` to use the default options.

  Returns a patchlist.
  """
  @spec from_texts_and_diffs(String.t(), String.t(), Diff.difflist(), options()) ::
          patchlist()
  def from_texts_and_diffs(text1, _text2, diffs, opts \\ []) do
    make(text1, diffs, opts)
  end

  @doc """
  This function can be called two ways. In either case the first argument,
  `a` is the original text (`text1`).

  The second argument `b` has two cases:

    * If `b` is a String `text2`, a difflist that turns `text1` into `text2` will be computed.
    * If `b` is a difflist, it is the delta between `text1` and the target `text2`.
    * `opts` - A options keyword list, `[]` to use the default options.

  Returns a patchlist.
  """
  @spec make(String.t(), String.t() | Diff.difflist(), options()) :: patchlist()
  def make(a, b, opts \\ [])

  def make(text1, text2, opts) when is_binary(text2) do
    opts = Options.valid_options!(opts)
    diff_edit_cost = Keyword.fetch!(opts, :diff_edit_cost)

    # No diffs provided, compute our own.
    diffs = Diff.main(text1, text2, true)

    diffs =
      if Enum.count(diffs) > 2 do
        diffs
        |> Diff.cleanup_semantic()
        |> Diff.cleanup_efficiency(diff_edit_cost)
      else
        diffs
      end

    make_impl(text1, diffs, opts)
  end

  def make(text1, diffs, opts) when is_list(diffs) do
    opts = Options.valid_options!(opts)
    make_impl(text1, diffs, opts)
  end

  # Get rid of the null case.
  @spec make_impl(String.t(), Diff.difflist(), options()) :: patchlist()
  defp make_impl(_text1, [], _opts), do: []

  defp make_impl(text1, diffs, opts) do
    patch_margin = Keyword.fetch!(opts, :patch_margin)
    match_max_bits = Keyword.fetch!(opts, :match_max_bits)

    {patches, patch, prepatch_text} =
      diffs
      |> Cursor.from_list(position: 0)
      |> make_loop(
        {[], %Patch{}, text1, text1, 0, 0},
        patch_margin,
        match_max_bits
      )

    if patch.diffs != [] do
      # Pick up the leftover patch if not empty.
      patch =
        add_context(
          patch,
          prepatch_text,
          patch_margin,
          match_max_bits
        )

      patches = patches ++ [patch]

      patches
    else
      patches
    end
  end

  # Start with text1 (`prepatch_text`) and apply the diffs until we arrive at
  # text2 (`postpatch_text`).
  # We recreate the patches one by one to determine context info.
  # `char_count1` Number of characters into the text1 string.
  # `char_count2` Number of characters into the text2 string.

  defp make_loop(
         %Cursor{current: nil},
         {patches, patch, prepatch_text, _postpatch_text, _char_count1, _char_count2},
         _patch_margin,
         _match_max_bits
       ) do
    {patches, patch, prepatch_text}
  end

  defp make_loop(
         diffs,
         {patches, patch, prepatch_text, postpatch_text, char_count1, char_count2},
         patch_margin,
         match_max_bits
       ) do
    patch = maybe_new_patch(diffs, patch, char_count1, char_count2)

    acc = {patches, patch, prepatch_text, postpatch_text, char_count1, char_count2}

    # Add to patch.diffs, then update the current character count
    # (`char_count1` and `char_count2`).
    acc = add_diff_to_patch(diffs, acc, patch_margin, match_max_bits)

    diffs
    |> Cursor.move_forward()
    |> make_loop(
      acc,
      patch_margin,
      match_max_bits
    )
  end

  # For `:insert` and `:delete` diffs, a new patch starting at the current character count.
  defp maybe_new_patch(%Cursor{current: {:equal, _}}, patch, _start1, _start2), do: patch

  defp maybe_new_patch(_diffs, %Patch{diffs: []} = patch, start1, start2) do
    %Patch{patch | start1: start1, start2: start2}
  end

  defp maybe_new_patch(_diffs, patch, _start1, _start2), do: patch

  # Add an `:insert` diff and update the current character count.
  defp add_diff_to_patch(
         %Cursor{current: {:insert, text} = this_diff},
         {patches, patch, prepatch_text, postpatch_text, char_count1, char_count2},
         _patch_margin,
         _match_max_bits
       ) do
    text_length = String.length(text)

    {patches,
     %Patch{patch | diffs: patch.diffs ++ [this_diff], length2: patch.length2 + text_length},
     prepatch_text,
     substring(postpatch_text, 0, char_count2) <>
       text <> substring(postpatch_text, char_count2), char_count1, char_count2 + text_length}
  end

  # Add a `:delete` diff and update the current character count.
  defp add_diff_to_patch(
         %Cursor{current: {:delete, text} = this_diff},
         {patches, patch, prepatch_text, postpatch_text, char_count1, char_count2},
         _patch_margin,
         _match_max_bits
       ) do
    text_length = String.length(text)

    {patches,
     %Patch{patch | diffs: patch.diffs ++ [this_diff], length1: patch.length1 + text_length},
     prepatch_text,
     substring(postpatch_text, 0, char_count2) <>
       substring(postpatch_text, char_count2 + text_length), char_count1 + text_length,
     char_count2}
  end

  # Nothing to do for equality with empty diffs, just update the current character count.
  defp add_diff_to_patch(
         %Cursor{current: {:equal, text}},
         {patches, %Patch{diffs: []} = patch, prepatch_text, postpatch_text, char_count1,
          char_count2},
         _patch_margin,
         _match_max_bits
       ) do
    text_length = String.length(text)

    {patches, patch, prepatch_text, postpatch_text, char_count1 + text_length,
     char_count2 + text_length}
  end

  # Add an `:equal` diff and update the current character count.
  defp add_diff_to_patch(
         %Cursor{current: {:equal, text}} = diffs,
         {patches, patch, prepatch_text, postpatch_text, char_count1, char_count2},
         patch_margin,
         match_max_bits
       ) do
    text_length = String.length(text)

    if text_length <= 2 * patch_margin do
      patch = small_equality_patch(diffs, patch, text_length)

      {patches, patch, prepatch_text, postpatch_text, char_count1 + text_length,
       char_count2 + text_length}
    else
      {patches, patch, prepatch_text, postpatch_text, char_count1} =
        large_equality_patch(
          patches,
          patch,
          prepatch_text,
          postpatch_text,
          char_count1,
          char_count2,
          patch_margin,
          match_max_bits
        )

      {patches, patch, prepatch_text, postpatch_text, char_count1 + text_length,
       char_count2 + text_length}
    end
  end

  # Small equality inside a patch.
  # No op if this is the last diff.
  defp small_equality_patch(%Cursor{next: []}, patch, _), do: patch

  defp small_equality_patch(%Cursor{current: this_diff}, patch, text_length) do
    %Patch{
      patch
      | diffs: patch.diffs ++ [this_diff],
        length1: patch.length1 + text_length,
        length2: patch.length2 + text_length
    }
  end

  # Equality diff is too big.
  # Time for a new patch.
  defp large_equality_patch(
         patches,
         patch,
         prepatch_text,
         postpatch_text,
         _char_count1,
         char_count2,
         patch_margin,
         match_max_bits
       ) do
    patch = add_context(patch, prepatch_text, patch_margin, match_max_bits)
    patches = patches ++ [patch]

    {
      patches,
      %Patch{},
      # Unlike Unidiff, our patch lists have a rolling context.
      # https://github.com/google/diff-match-patch/wiki/Unidiff
      # Update prepatch text and pos to reflect the application of the
      # just completed patch.
      postpatch_text,
      postpatch_text,
      char_count2
    }
  end

  @doc """
  Merge a set of patches onto the text.  Return a patched text, as well
  as an array of true/false values indicating which patches were applied.

    * `patches` - A patchlist.
    * `text` - Text to apply patch to.
    * `opts` - A options keyword list, `[]` to use the default options.

  Returns a tuple with two elements: the patched text, and a list of
  boolean values. Each boolean corresponds to a patch in the patchlist,
  and is `true` if a match was found for the corresponding patch.
  """
  @spec apply(patchlist(), String.t(), options()) :: {String.t(), list(boolean())}
  def apply([], text), do: {text, []}

  def apply(patches, text, opts \\ []) do
    opts = Options.valid_options!(opts)
    patch_margin = Keyword.fetch!(opts, :patch_margin)
    match_max_bits = Keyword.fetch!(opts, :match_max_bits)
    {patches, null_padding} = add_padding(patches, patch_margin)
    text = null_padding <> text <> null_padding

    patches =
      split_max(
        patches,
        patch_margin,
        match_max_bits
      )

    {results, text, _delta, _opts} =
      Enum.reduce(
        patches,
        {[], text, 0, opts},
        fn patch, acc -> apply_loop(patch, acc) end
      )

    # Strip the padding off.
    null_padding_length = String.length(null_padding)
    text = substring(text, null_padding_length, String.length(text) - null_padding_length)

    {text, Enum.reverse(results)}
  end

  @type apply_loop_acc() ::
          {list(boolean()), String.t(), integer(), options()}

  defp apply_loop(
         patch,
         {results, text, delta, opts}
       ) do
    expected_loc = patch.start2 + delta
    text1 = Diff.text1(patch.diffs)

    {start_loc, end_loc} = find_expected_match(text, text1, expected_loc, opts)

    if start_loc == -1 do
      # No match found.  :(
      # Subtract the delta for this failed patch from subsequent patches.
      delta = delta - (patch.length2 - patch.length1)
      {[false | results], text, delta, opts}
    else
      # Found a match.  :)
      text2 =
        if end_loc == -1 do
          substring(text, start_loc, start_loc + String.length(text1))
        else
          match_max_bits = Keyword.fetch!(opts, :match_max_bits)
          substring(text, start_loc, end_loc + match_max_bits)
        end

      {found, text} = apply_at_match(patch, text, text1, text2, start_loc, opts)
      delta = start_loc - expected_loc
      {[found | results], text, delta, opts}
    end
  end

  defp find_expected_match(text, text1, expected_loc, opts) do
    text1_length = String.length(text1)
    match_max_bits = Keyword.fetch!(opts, :match_max_bits)

    if text1_length > match_max_bits do
      # split_max will only provide an oversized pattern in the case of
      # a monster delete.
      start_loc =
        Match.main(
          text,
          substring(text1, 0, match_max_bits),
          expected_loc,
          opts
        )

      if start_loc == -1 do
        {-1, -1}
      else
        end_loc =
          Match.main(
            text,
            substring(text1, text1_length - match_max_bits),
            expected_loc + text1_length - match_max_bits,
            opts
          )

        if end_loc == -1 || start_loc >= end_loc do
          # Can't find valid trailing context.  Drop this patch.
          {-1, end_loc}
        else
          {start_loc, end_loc}
        end
      end
    else
      {Match.main(text, text1, expected_loc, opts), -1}
    end
  end

  defp apply_at_match(patch, text, text1, text2, start_loc, _opts) when text1 == text2 do
    # Perfect match, just shove the replacement text in.
    {true,
     substring(text, 0, start_loc) <>
       Diff.text2(patch.diffs) <>
       substring(text, start_loc + String.length(text1))}
  end

  defp apply_at_match(patch, text, text1, text2, start_loc, opts) do
    # Imperfect match.  Run a diff to get a framework of equivalent indices.
    diffs = Diff.main_(text1, text2, false, opts)

    if bad_match?(diffs, text1, opts) do
      # The end points match, but the content is unacceptably bad.
      {false, text}
    else
      diffs = Diff.cleanup_semantic_lossless(diffs)

      {acc_text, _index1} =
        Enum.reduce(patch.diffs, {text, 0}, fn diff, {acc_text, index1} ->
          apply_match_diff(diff, acc_text, index1, diffs, start_loc)
        end)

      {true, acc_text}
    end
  end

  # Returns true if the end points match, but the content is unacceptably bad.
  def bad_match?(diffs, text1, opts) do
    text1_length = String.length(text1)

    if text1_length > Keyword.fetch!(opts, :match_max_bits) do
      normalized_lev = Diff.levenshtein(diffs) / text1_length
      normalized_lev > Keyword.fetch!(opts, :patch_delete_threshold)
    else
      false
    end
  end

  def apply_match_diff({op, first_text}, acc_text, index1, diffs, start_loc) do
    dtext_length = String.length(first_text)

    case op do
      :equal ->
        {acc_text, index1 + dtext_length}

      :insert ->
        # Insertion
        index2 = Diff.x_index(diffs, index1)

        acc_text =
          substring(acc_text, 0, start_loc + index2) <>
            first_text <>
            substring(acc_text, start_loc + index2)

        {acc_text, index1 + dtext_length}

      :delete ->
        # Deletion
        index2 = Diff.x_index(diffs, index1)
        index3 = Diff.x_index(diffs, index1 + dtext_length)

        acc_text =
          substring(acc_text, 0, start_loc + index2) <>
            substring(acc_text, start_loc + index3)

        {acc_text, index1}

      _ ->
        raise RuntimeError, "Invalid operation #{inspect(op)}"
    end
  end

  @doc """
  Add some padding on text start and end so that edges can match something.

  Intended to be called only from within `Patch.apply`.

    * `patches` - A patchlist..
    * `patch_margin` - Chunk size for context length.

  Returns a tuple of the padded patchlist and the padding string added to each side.
  """
  @spec add_padding(patchlist(), non_neg_integer()) :: {patchlist(), String.t()}
  def add_padding([], _patch_margin), do: {[], ""}

  def add_padding(patches, patch_margin) do
    padding_length = patch_margin
    null_padding = Enum.reduce(1..padding_length, "", fn x, s -> s <> to_string([x]) end)

    # Bump all the patches forward.
    patches =
      Enum.map(patches, fn patch ->
        %Patch{
          patch
          | start1: patch.start1 + padding_length,
            start2: patch.start2 + padding_length
        }
      end)

    # Separate first and last patch
    {first_patch, mid_patches, last_patch} = split_patches(patches)

    # Add padding before and after
    first_patch = pad_first_patch(first_patch, null_padding)
    # Sometimes the first patch and the last patch are the same
    if is_nil(last_patch) do
      first_patch = pad_last_patch(first_patch, null_padding)
      {[first_patch], null_padding}
    else
      # Recombine
      last_patch = pad_last_patch(last_patch, null_padding)
      {[first_patch | mid_patches] ++ [last_patch], null_padding}
    end
  end

  # Separate first and last patch
  defp split_patches([one_patch]), do: {one_patch, [], nil}
  defp split_patches([first_patch, last_patch]), do: {first_patch, [], last_patch}

  defp split_patches([first_patch | mid_patches]) do
    {last_patch, mid_patches} = List.pop_at(mid_patches, -1)
    {first_patch, mid_patches, last_patch}
  end

  # Add some padding on start of first diff.
  defp pad_first_patch(first_patch, null_padding) do
    padding_length = String.length(null_padding)
    first_diff = List.first(first_patch.diffs)

    {op, text} = Diff.undiff(first_diff)

    if op == :equal do
      text_length = String.length(text)

      if padding_length > text_length do
        # Grow first equality.
        extra_length = padding_length - text_length
        text = substring(null_padding, text_length) <> text
        first_diff = {op, text}

        %Patch{
          first_patch
          | diffs: [first_diff | Enum.drop(first_patch.diffs, 1)],
            start1: first_patch.start1 - extra_length,
            start2: first_patch.start2 - extra_length,
            length1: first_patch.length1 + extra_length,
            length2: first_patch.length2 + extra_length
        }
      else
        first_patch
      end
    else
      # :nil, :insert, or :delete
      # Add null_padding equality.
      # start1 and start2 should be 0.
      %Patch{
        first_patch
        | diffs: [{:equal, null_padding} | first_patch.diffs],
          start1: first_patch.start1 - padding_length,
          start2: first_patch.start2 - padding_length,
          length1: first_patch.length1 + padding_length,
          length2: first_patch.length2 + padding_length
      }
    end
  end

  # Add some padding on end of last diff.
  defp pad_last_patch(last_patch, null_padding) do
    padding_length = String.length(null_padding)
    last_diff = List.last(last_patch.diffs)

    {op, text} = Diff.undiff(last_diff)

    if op == :equal do
      text_length = String.length(text)

      if padding_length > text_length do
        # Grow last equality.
        extra_length = padding_length - text_length
        last_diff = {op, text <> substring(null_padding, 0, extra_length)}

        %Patch{
          last_patch
          | diffs: Enum.drop(last_patch.diffs, -1) ++ [last_diff],
            length1: last_patch.length1 + extra_length,
            length2: last_patch.length2 + extra_length
        }
      else
        last_patch
      end
    else
      # :nil, :insert, or :delete
      # Add null_padding equality.
      %Patch{
        last_patch
        | diffs: last_patch.diffs ++ [{:equal, null_padding}],
          length1: last_patch.length1 + padding_length,
          length2: last_patch.length2 + padding_length
      }
    end
  end

  @doc """
  Look through the patches and break up any which are longer than the
  maximum limit of the match algorithm.

  Intended to be called only from within `Patch.apply`.

    * `patches` - A patchlist.
    * `patch_margin` - Chunk size for context length.
    * `match_max_bits` - The number of bits in an int (default 32).

  Returns the updated patchlist.
  """
  @spec split_max(patchlist(), non_neg_integer(), non_neg_integer()) :: patchlist()
  def split_max(patches, patch_margin, match_max_bits \\ 32) do
    if match_max_bits <= patch_margin do
      patches
    else
      patches
      |> Cursor.from_list(position: 0)
      |> split_max_loop(patch_margin, match_max_bits)
    end
  end

  defp split_max_loop(%Cursor{current: nil} = patches, _patch_margin, _patch_size),
    do: Cursor.to_list(patches)

  defp split_max_loop(%Cursor{current: bigpatch} = patches, patch_margin, patch_size) do
    patches =
      if bigpatch.length1 > patch_size do
        # Remove the big old patch.
        patches
        |> Cursor.delete(1)
        |> Cursor.move_back()
        |> create_subpatches(
          bigpatch.diffs,
          {"", bigpatch.start1, bigpatch.start2, patch_margin, patch_size}
        )
      else
        Cursor.move_forward(patches)
      end

    split_max_loop(patches, patch_margin, patch_size)
  end

  defp create_subpatches(patches, [], _acc), do: patches

  defp create_subpatches(
         patches,
         bigpatch_diffs,
         {precontext, start1, start2, patch_margin, patch_size}
       ) do
    precontext_length = String.length(precontext)
    # Create one of several smaller patches.
    patch = %Patch{start1: start1 - precontext_length, start2: start2 - precontext_length}

    patch =
      if precontext_length != 0 do
        %Patch{
          patch
          | diffs: [{:equal, precontext}],
            length1: precontext_length,
            length2: precontext_length
        }
      else
        patch
      end

    {bigpatch_diffs, patch, {start1, start2, empty, _patch_margin, _patch_size}} =
      subpatch_loop(bigpatch_diffs, patch, {start1, start2, true, patch_margin, patch_size})

    # Compute the head context for the next patch.
    precontext = Diff.text2(patch.diffs)
    precontext = substring(precontext, max(0, String.length(precontext) - patch_margin))

    # Append the end context for this patch.
    text1 = Diff.text1(bigpatch_diffs)

    postcontext =
      if String.length(text1) > patch_margin do
        substring(text1, 0, patch_margin)
      else
        text1
      end

    patch =
      if postcontext != "" do
        postcontext_length = String.length(postcontext)
        last_diff = List.last(patch.diffs)
        {op, text} = Diff.undiff(last_diff)

        patch_diffs =
          if op == :equal do
            Enum.drop(patch.diffs, -1) ++ [{:equal, text <> postcontext}]
          else
            # :nil, :insert, or :delete
            patch.diffs ++ [{:equal, postcontext}]
          end

        %Patch{
          patch
          | diffs: patch_diffs,
            length1: patch.length1 + postcontext_length,
            length2: patch.length2 + postcontext_length
        }
      else
        patch
      end

    patches =
      if empty do
        patches
      else
        patches
        |> Cursor.move_forward()
        |> Cursor.insert_before([patch])
      end

    # Call again, without advancing
    create_subpatches(
      patches,
      bigpatch_diffs,
      {precontext, start1, start2, patch_margin, patch_size}
    )
  end

  def subpatch_loop([], patch, acc), do: {[], patch, acc}

  def subpatch_loop(
        bigpatch_diffs,
        %Patch{length1: length1} = patch,
        {_start1, _start2, _empty, patch_margin, patch_size} = acc
      )
      when length1 >= patch_size - patch_margin do
    {bigpatch_diffs, patch, acc}
  end

  def subpatch_loop([first_diff | rest], patch, acc) do
    {bigpatch_diffs, patch, acc} = add_diff_to_subpatch(first_diff, rest, patch, acc)
    subpatch_loop(bigpatch_diffs, patch, acc)
  end

  def add_diff_to_subpatch(
        {:insert, first_text} = first_diff,
        rest,
        patch,
        {start1, start2, _empty, patch_margin, patch_size}
      ) do
    # Insertions are harmless.
    text_length = String.length(first_text)

    patch = %Patch{
      patch
      | diffs: patch.diffs ++ [first_diff],
        length2: patch.length2 + text_length
    }

    {rest, patch, {start1, start2 + text_length, false, patch_margin, patch_size}}
  end

  # If the patch is just one equality
  # and we have a large deletion...
  def add_diff_to_subpatch(
        {:delete, first_text} = first_diff,
        rest,
        %Patch{diffs: [{:equal, _}]} = patch,
        {start1, start2, _empty, patch_margin, patch_size} = acc
      ) do
    text_length = String.length(first_text)

    if text_length > 2 * patch_size do
      # This is a large deletion.  Let it pass in one chunk.
      patch = %Patch{
        patch
        | diffs: patch.diffs ++ [first_diff],
          length1: patch.length1 + text_length
      }

      {rest, patch, {start1 + text_length, start2, false, patch_margin, patch_size}}
    else
      # Handle same as :equal
      add_other_diff_to_subpatch(first_diff, rest, patch, acc)
    end
  end

  # Equality, or deletion when patch is not a single equality
  def add_diff_to_subpatch(first_diff, rest, patch, acc) do
    add_other_diff_to_subpatch(first_diff, rest, patch, acc)
  end

  # Equality, or small deletion
  def add_other_diff_to_subpatch(
        {first_op, first_text},
        rest,
        patch,
        {start1, start2, empty, patch_margin, patch_size}
      ) do
    # Deletion or equality.  Only take as much as we can stomach.
    diff_text =
      substring(
        first_text,
        0,
        patch_size - patch.length1 - patch_margin
      )

    text_length = String.length(diff_text)
    patch = %Patch{patch | length1: patch.length1 + text_length}
    start1 = start1 + text_length

    {patch, start2, empty} =
      if first_op == :equal do
        {%Patch{patch | length2: patch.length2 + text_length}, start2 + text_length, empty}
      else
        {patch, start2, false}
      end

    patch = %Patch{patch | diffs: patch.diffs ++ [{first_op, diff_text}]}

    bigpatch_diffs =
      if diff_text == first_text do
        rest
      else
        first_text = substring(first_text, text_length)
        [{first_op, first_text} | rest]
      end

    {bigpatch_diffs, patch, {start1, start2, empty, patch_margin, patch_size}}
  end

  @doc """
  Return the textual representation of a patchlist.
  """
  def to_text(patches) do
    Enum.reduce(patches, "", fn patch, acc -> acc <> to_string(patch) end)
  end

  @header_regex ~r/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/

  @doc """
  Parse a textual representation of patches and return a patchlist.

  Raises an `ArgumentError` if the text has invalid contents.
  """
  @spec from_text(String.t()) :: patchlist()
  def from_text(""), do: []

  def from_text(text) do
    text
    |> String.split("\n")
    |> Cursor.from_list(position: 0)
    |> parse_patch_header([])
    |> Enum.reverse()
  end

  @spec parse_patch_header(Cursor.t(), patchlist()) :: patchlist()
  defp parse_patch_header(%Cursor{current: line} = lines, patches) do
    case line do
      nil ->
        patches

      "" ->
        Cursor.move_forward(lines)
        |> parse_patch_header(patches)

      _ ->
        case Regex.run(@header_regex, line) do
          nil ->
            raise ArgumentError, "Invalid patch header: #{line}"

          groups ->
            {start1, length1} =
              parse_start_length(Enum.at(groups, 1), Enum.at(groups, 2), line, "1")

            {start2, length2} =
              parse_start_length(Enum.at(groups, 3), Enum.at(groups, 4), line, "2")

            {lines, diffs} =
              lines
              |> Cursor.move_forward()
              |> parse_patch_body([])

            parse_patch_header(
              lines,
              [
                %Patch{
                  diffs: Enum.reverse(diffs),
                  start1: start1,
                  start2: start2,
                  length1: length1,
                  length2: length2
                }
                | patches
              ]
            )
        end
    end
  end

  defp parse_start_length(s1, s2, line, suffix) do
    start =
      case Integer.parse(s1) do
        {start, ""} -> start
        _ -> raise ArgumentError, "Invalid patch header (start#{suffix}): #{line}"
      end

    case s2 do
      "" ->
        {start - 1, 1}

      "0" ->
        {start, 0}

      _ ->
        case Integer.parse(s2) do
          {length, ""} -> {start - 1, length}
          _ -> raise ArgumentError, "Invalid patch header (length#{suffix}): #{line}"
        end
    end
  end

  @spec parse_patch_body(Cursor.t(), Diff.difflist()) :: {Cursor.t(), Diff.difflist()}
  defp parse_patch_body(%Cursor{current: nil} = lines, diffs), do: {lines, diffs}

  defp parse_patch_body(%Cursor{current: ""} = lines, diffs) do
    Cursor.move_forward(lines)
    |> parse_patch_body(diffs)
  end

  defp parse_patch_body(%Cursor{current: line} = lines, diffs) do
    diff = parse_patch_diff(line)

    if is_nil(diff) do
      {lines, diffs}
    else
      Cursor.move_forward(lines)
      |> parse_patch_body([diff | diffs])
    end
  end

  defp parse_patch_diff(line) do
    {sign, text} = String.split_at(line, 1)
    # Decode would change all "+" to " "
    text = text |> String.replace("+", "%2B") |> URI.decode()

    case sign do
      "-" ->
        # Deletion.
        {:delete, text}

      "+" ->
        # Insertion.
        {:insert, text}

      " " ->
        # Minor equality.
        {:equal, text}

      "@" ->
        nil

      _ ->
        # WTF?
        raise ArgumentError, "Invalid patch mode '#{sign}' in: #{line}"
    end
  end
end