defmodule Dmp.Diff do
  @moduledoc """
  Compare two blocks of plain text and efficiently return a list of differences.
  """

  import Dmp.StringUtils

  alias Dmp.{Cursor, Options}

  @typedoc """
  A diff's operation type. The operation `:nil` is used internally
  to indicate a nil value for the diff.
  """
  @type op() :: :delete | :insert | :equal | nil

  @typedoc """
  The diff tuple, consisting of two elements: the operation
  and the associated text.
  """
  @type t() :: {op(), String.t()}

  @typedoc """
  A list of diff operations, representing the difference between two text versions.

  A "difflist" is an Elixir list of "diff" tuples.
  Here is an example difflist:

  ```
  [{:delete, "Hello"}, {:insert, "Goodbye"}, {:equal, " world."}]
  ```

  which means: delete "Hello", add "Goodbye" and keep " world."
  """
  @type difflist() :: list(t())

  @type options() :: Options.t()

  @type expiry() :: :never | non_neg_integer()

  @doc """
  Find the differences between two texts.

    * `text1` - Old string to be diffed.
    * `text2` - New string to be diffed.
    * `check_lines` - Speedup flag.  If `false`, then don't run a
      line-level diff first to identify the changed areas. If `true`,
      then run a faster slightly less optimal diff.
    * `opts` - A options keyword list, `[]` to use the default options.

  Most of the time `check_lines` is wanted, so it defaults to `true`.

  Returns a difflist.
  """
  @spec main(String.t(), String.t(), boolean(), options()) :: difflist()
  def main(text1, text2, check_lines \\ true, opts \\ []) do
    opts = Options.valid_options!(opts)
    main_(text1, text2, check_lines, opts)
  end

  @doc """
  Skips validation of options. Used internally by `Patch.apply`.
  """
  @spec main_(String.t(), String.t(), boolean(), options()) :: difflist()
  def main_(text1, text2, check_lines, opts) do
    diff_timeout = Keyword.fetch!(opts, :diff_timeout)

    deadline =
      if diff_timeout <= 0 do
        :never
      else
        :os.system_time(:millisecond) + round(diff_timeout * 1000)
      end

    main_impl(text1, text2, check_lines, deadline)
  end

  @spec main_impl(String.t(), String.t(), boolean(), expiry()) :: difflist()
  defp main_impl(text1, text2, check_lines, deadline)
       when is_binary(text1) and is_binary(text2) do
    # Check for equality (speedup).
    if text1 == text2 do
      if text1 == "" do
        []
      else
        [{:equal, text1}]
      end
    else
      # Trim off common prefix (speedup).
      {prefix, text1, text2} = common_prefix(text1, text2)

      #  Trim off common suffix (speedup).
      {suffix, text1, text2} = common_suffix(text1, text2)

      # Compute the diff on the middle block.
      diffs = compute(text1, text2, check_lines, deadline)

      # Restore the prefix and suffix.
      diffs =
        if prefix != "" do
          [{:equal, prefix} | diffs]
        else
          diffs
        end

      diffs =
        if suffix != "" do
          diffs ++ [{:equal, suffix}]
        else
          diffs
        end

      diffs = cleanup_merge(diffs)

      diffs
    end
  end

  @doc """
  Find the differences between two texts.

    * `text1` - Old string to be diffed.
    * `text2` -  New string to be diffed.
    * `check_lines` - Speedup flag.  If false, then don't run a
      line-level diff first to identify the changed areas.
      If true, then run a faster slightly less optimal diff.
    * `deadline` - Unix timestamp in milliseconds when the diff should be complete by.

  Assumes that the texts do not have any common prefix or suffix.

  Returns a difflist.
  """
  @spec compute(String.t(), String.t(), boolean(), expiry()) :: difflist()
  def compute("", text2, _, _) do
    # Just add some text (speedup).
    [{:insert, text2}]
  end

  def compute(text1, "", _, _) do
    # Just delete some text (speedup).
    [{:delete, text1}]
  end

  # credo:disable-for-lines:43 Credo.Check.Refactor.CyclomaticComplexity
  def compute(text1, text2, check_lines, deadline) do
    text1_length = String.length(text1)
    text2_length = String.length(text2)

    {longtext, shorttext, shorttext_length, op} =
      if text1_length > text2_length do
        {text1, text2, text2_length, :delete}
      else
        {text2, text1, text1_length, :insert}
      end

    case String.split(longtext, shorttext, parts: 2) do
      [left, right] ->
        # Shorter text is inside the longer text (speedup).
        [{op, left}, {:equal, shorttext}, {op, right}]

      _notfound ->
        if shorttext_length == 1 do
          # Single character string.
          # After the previous speedup, the character can't be an equality.

          [{:delete, text1}, {:insert, text2}]
        else
          # Check to see if the problem can be split in two.
          case half_match(text1, text2, deadline) do
            {text1_a, text1_b, text2_a, text2_b, mid_common} ->
              # Send both pairs off for separate processing.

              diffs_a = main_impl(text1_a, text2_a, check_lines, deadline)
              diffs_b = main_impl(text1_b, text2_b, check_lines, deadline)
              # Merge the results.
              diffs_a ++ [{:equal, mid_common} | diffs_b]

            nil ->
              if check_lines && text1_length > 100 && text2_length > 100 do
                line_mode(text1, text2, deadline)
              else
                bisect(text1, text2, deadline)
              end
          end
        end
    end
  end

  @doc """
  Do a quick line-level diff on both strings, then rediff the parts for
  greater accuracy.

    * `text1` - Old string to be diffed.
    * `text2` - New string to be diffed.
    * `deadline` - Unix timestamp (in milliseconds) when the diff should be complete by.

  This speedup can produce non-minimal diffs.

  Returns a difflist.
  """
  @spec line_mode(String.t(), String.t(), expiry()) :: difflist()
  def line_mode(text1, text2, deadline) do
    # Scan the text on a line-by-line basis first.
    {text1, text2, line_array} = lines_to_chars(text1, text2)

    diffs =
      main_impl(text1, text2, false, deadline)
      # Convert the diff back to original text.
      |> chars_to_lines(line_array)
      # Eliminate freak matches (e.g. blank lines)
      |> cleanup_semantic()

    if diffs == [] do
      diffs
    else
      # Add a dummy entry at the end.
      # Rediff any replacement blocks, this time character-by-character.
      # Remove the dummy entry at the end.
      (diffs ++ [{:equal, ""}])
      |> Cursor.from_list(position: 0)
      |> line_mode_loop({0, 0, "", ""}, deadline)
      |> remove_dummy()
    end
  end

  defp line_mode_loop(
         %Cursor{current: nil} = diffs,
         _acc,
         _deadline
       ),
       do: Cursor.to_list(diffs)

  defp line_mode_loop(
         %Cursor{current: this_diff} = diffs,
         {count_delete, count_insert, text_delete, text_insert},
         deadline
       ) do
    {op, text} = this_diff

    {cursor, count_delete, count_insert, text_delete, text_insert} =
      case op do
        :insert ->
          {diffs, count_delete, count_insert + 1, text_delete, text_insert <> text}

        :delete ->
          {diffs, count_delete + 1, count_insert, text_delete <> text, text_insert}

        :equal ->
          # Upon reaching an equality, check for prior redundancies.
          diffs2 =
            if count_delete > 0 && count_insert > 0 do
              # Delete the offending records and add the merged ones.
              diffs1 = Cursor.delete_before(diffs, count_delete + count_insert)
              sub_diff = main_impl(text_delete, text_insert, false, deadline)
              Cursor.insert_before(diffs1, sub_diff)
            else
              diffs
            end

          {diffs2, 0, 0, "", ""}

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

    line_mode_loop(
      Cursor.move_forward(cursor),
      {count_delete, count_insert, text_delete, text_insert},
      deadline
    )
  end

  @doc """
  Find the "middle snake" of a diff, split the problem in two
  and return the recursively constructed diff.

  See: [An O(ND) Difference Algorithm and Its Variations (Meyers, 1986)](http://www.xmailserver.org/diff2.pdf)

    * `text1` - Old string to be diffed.
    * `text2` - New string to be diffed.
    * `deadline` - Unix timestamp (in milliseconds) at which to bail if not yet complete.

  Returns a difflist.
  """
  @spec bisect(String.t(), String.t(), expiry()) :: difflist()
  def bisect(text1, text2, deadline) do
    # Cache the text lengths to prevent multiple calls.
    text1_length = String.length(text1)
    text2_length = String.length(text2)
    max_d = div(text1_length + text2_length + 1, 2)
    v_offset = max_d
    v_length = 2 * max_d

    v1init =
      Enum.reduce(0..(v_length - 1), [], fn i, acc ->
        val =
          if i == v_offset + 1 do
            0
          else
            -1
          end

        [{i, val} | acc]
      end)

    v2init = Map.new(v1init)
    v1init = Map.new(v1init)

    # Offsets for start and end of k loop.
    # Prevents mapping of space beyond the grid.
    # k1_start = 0
    # k1_end = 0
    # k2_start = 0
    # k2_end = 0
    diffs =
      Enum.reduce_while(0..max_d, {v1init, v2init, 0, 0, 0, 0}, fn d,
                                                                   {v1, v2, k1_start, k1_end,
                                                                    k2_start, k2_end} ->
        if is_integer(deadline) && :os.system_time(:millisecond) > deadline do
          # Bail out if deadline is reached.

          {:halt, nil}
        else
          # Walk the front path one step.
          {v1, diffs1} =
            advance_front(v1, v2, d, -d + k1_start, {
              k1_start,
              k1_end,
              v_offset,
              v_length,
              text1,
              text1_length,
              text2,
              text2_length,
              deadline
            })

          if is_list(diffs1) do
            {:halt, diffs1}
          else
            # Walk the reverse path one step.

            {v2, diffs2} =
              advance_reverse(
                v1,
                v2,
                d,
                -d + k2_start,
                {k2_start, k2_end, v_offset, v_length, text1, text1_length, text2, text2_length,
                 deadline}
              )

            if is_list(diffs2) do
              {:halt, diffs2}
            else
              {:cont, {v1, v2, k1_start, k1_end, k2_start, k2_end}}
            end
          end
        end
      end)

    if is_list(diffs) do
      diffs
    else
      # Diff took too long and hit the deadline or
      # number of diffs equals number of characters, no commonality at all.
      [{:delete, text1}, {:insert, text2}]
    end
  end

  defp advance_front(
         v1,
         _v2,
         d,
         k1,
         {_k1_start, k1_end, _v_offset, _v_length, _text1, _text1_length, _text2, _text2_length,
          _deadline}
       )
       when k1 > d - k1_end do
    {v1, nil}
  end

  defp advance_front(
         v1,
         v2,
         d,
         k1,
         {k1_start, k1_end, v_offset, v_length, text1, text1_length, text2, text2_length,
          deadline}
       ) do
    {v1, x1, y1} =
      get_front_location(v1, d, k1, v_offset, text1, text1_length, text2, text2_length)

    {k1_start, k1_end, diffs} =
      bisect_front(
        v2,
        k1,
        x1,
        y1,
        {k1_start, k1_end, v_offset, v_length, text1, text1_length, text2, text2_length, deadline}
      )

    if is_list(diffs) do
      {v1, diffs}
    else
      advance_front(
        v1,
        v2,
        d,
        k1 + 2,
        {k1_start, k1_end, v_offset, v_length, text1, text1_length, text2, text2_length, deadline}
      )
    end
  end

  defp get_front_location(v1, d, k1, v_offset, text1, text1_length, text2, text2_length) do
    k1_offset = v_offset + k1
    v1_minus1 = v1[k1_offset - 1]
    v1_plus1 = v1[k1_offset + 1]

    x1 =
      if k1 == -d || (k1 != d && v1_minus1 < v1_plus1) do
        v1_plus1
      else
        v1_minus1 + 1
      end

    {x1, y1} = advance_x1_y1(x1, x1 - k1, text1, text1_length, text2, text2_length)
    v1 = Map.put(v1, k1_offset, x1)
    {v1, x1, y1}
  end

  defp advance_x1_y1(x1, y1, text1, text1_length, text2, text2_length) do
    if x1 < text1_length && y1 < text2_length &&
         String.at(text1, x1) == String.at(text2, y1) do
      advance_x1_y1(x1 + 1, y1 + 1, text1, text1_length, text2, text2_length)
    else
      {x1, y1}
    end
  end

  defp bisect_front(
         v2,
         k1,
         x1,
         y1,
         {k1_start, k1_end, v_offset, v_length, text1, text1_length, text2, text2_length,
          deadline}
       ) do
    delta = text1_length - text2_length

    # If the total number of characters is odd, then the front path will
    # collide with the reverse path.
    front = rem(delta, 2) != 0

    cond do
      x1 > text1_length ->
        # Ran off the right of the graph.
        {k1_start, k1_end + 2, nil}

      y1 > text2_length ->
        # Ran off the bottom of the graph.
        {k1_start + 2, k1_end, nil}

      front ->
        k2_offset = v_offset + delta - k1

        if k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1 do
          # Mirror x2 onto top-left coordinate system.
          x2 = text1_length - v2[k2_offset]

          if x1 >= x2 do
            # Overlap detected.

            {k1_start, k1_end, bisect_split(text1, text2, x1, y1, deadline)}
          else
            {k1_start, k1_end, nil}
          end
        else
          {k1_start, k1_end, nil}
        end

      true ->
        {k1_start, k1_end, nil}
    end
  end

  defp advance_reverse(
         _v1,
         v2,
         d,
         k2,
         {_k2_start, k2_end, _v_offset, _v_length, _text1, _text1_length, _text2, _text2_length,
          _deadline}
       )
       when k2 > d - k2_end do
    {v2, nil}
  end

  defp advance_reverse(
         v1,
         v2,
         d,
         k2,
         {k2_start, k2_end, v_offset, v_length, text1, text1_length, text2, text2_length,
          deadline}
       ) do
    {v2, x2, y2} =
      get_reverse_location(v2, d, k2, v_offset, text1, text1_length, text2, text2_length)

    {k2_start, k2_end, diffs} =
      bisect_reverse(
        v1,
        k2,
        x2,
        y2,
        {k2_start, k2_end, v_offset, v_length, text1, text1_length, text2, text2_length, deadline}
      )

    if is_list(diffs) do
      {v2, diffs}
    else
      advance_reverse(
        v1,
        v2,
        d,
        k2 + 2,
        {k2_start, k2_end, v_offset, v_length, text1, text1_length, text2, text2_length, deadline}
      )
    end
  end

  defp get_reverse_location(v2, d, k2, v_offset, text1, text1_length, text2, text2_length) do
    k2_offset = v_offset + k2
    v2_minus1 = v2[k2_offset - 1]
    v2_plus1 = v2[k2_offset + 1]

    x2 =
      if k2 == -d || (k2 != d && v2_minus1 < v2_plus1) do
        v2_plus1
      else
        v2_minus1 + 1
      end

    {x2, y2} = advance_x2_y2(x2, x2 - k2, text1, text1_length, text2, text2_length)
    v2 = Map.put(v2, k2_offset, x2)
    {v2, x2, y2}
  end

  defp advance_x2_y2(x2, y2, text1, text1_length, text2, text2_length) do
    if x2 < text1_length && y2 < text2_length &&
         String.at(text1, text1_length - x2 - 1) == String.at(text2, text2_length - y2 - 1) do
      advance_x2_y2(x2 + 1, y2 + 1, text1, text1_length, text2, text2_length)
    else
      {x2, y2}
    end
  end

  defp bisect_reverse(
         v1,
         k2,
         x2,
         y2,
         {k2_start, k2_end, v_offset, v_length, text1, text1_length, text2, text2_length,
          deadline}
       ) do
    delta = text1_length - text2_length

    # If the total number of characters is odd, then the front path will
    # collide with the reverse path.
    front = rem(delta, 2) != 0

    cond do
      x2 > text1_length ->
        # Ran off the right of the graph.
        {k2_start, k2_end + 2, nil}

      y2 > text2_length ->
        # Ran off the bottom of the graph.
        {k2_start + 2, k2_end, nil}

      !front ->
        k1_offset = v_offset + delta - k2

        if k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1 do
          x1 = v1[k1_offset]
          y1 = v_offset + x1 - k1_offset
          # Mirror x2 onto top-left coordinate system.
          x2 = text1_length - x2

          if x1 >= x2 do
            # Overlap detected.

            {k2_start, k2_end, bisect_split(text1, text2, x1, y1, deadline)}
          else
            {k2_start, k2_end, nil}
          end
        else
          {k2_start, k2_end, nil}
        end

      true ->
        {k2_start, k2_end, nil}
    end
  end

  @doc """
  Given the location of the "middle snake", split the diff in two parts
  and recurse.

    * `text1` - Old string to be diffed.
    * `text2` - New string to be diffed.
    * `x` - Index of split point in text1.
    * `y` - Index of split point in text2.
    * `deadline` - Unix timestamp (in milliseconds) at which to bail if not yet complete.

  Returns a difflist.
  """
  @spec bisect_split(
          String.t(),
          String.t(),
          non_neg_integer(),
          non_neg_integer(),
          non_neg_integer()
        ) :: difflist()
  def bisect_split(text1, text2, x, y, deadline) do
    {text1a, text1b} = String.split_at(text1, x)
    {text2a, text2b} = String.split_at(text2, y)

    # Compute both diffs serially.
    diffsa = main_impl(text1a, text2a, false, deadline)
    diffsb = main_impl(text1b, text2b, false, deadline)

    diffsa ++ diffsb
  end

  @doc """
  Split two texts into a list of strings.

  Reduce the texts to a string of hashes where each Unicode character
  represents one line.

    * `text1` - First string.
    * `text2` - Second string.

  Returns a tuple containing the encoded `text1`, the encoded `text2` and
  the list of unique strings.  The zeroth element of the list of
  unique strings is intentionally blank.
  """
  @spec lines_to_chars(String.t(), String.t()) :: {String.t(), String.t(), list(String.t())}
  def lines_to_chars(text1, text2) do
    # e.g. Enum.at(line_array, 4) == "Hello\n"
    # e.g. Map.get(line_hash, "Hello\n") == 4

    # "\x00" is a valid character, but various debuggers don't like it.
    # So we'll insert a junk entry in line_array to avoid generating a null character.
    # Bail out at 55_295 because to_string([55_296]) raises "invalid code point 55296"
    # Allocate 2/3rds of the space for text1, the rest for text2.
    {line_hash, line_array, chars1} = lines_to_chars_munge(text1, {%{}, [""], nil, nil}, 37_000)

    {_line_hash, line_array, chars2} =
      lines_to_chars_munge(text2, {line_hash, line_array, nil, nil}, 55_295)

    {chars1, chars2, line_array}
  end

  defp pop_line(text) do
    case String.split(text, "\n", parts: 2) do
      [line] ->
        {line, ""}

      [line, rest] ->
        {line <> "\n", rest}

      _ ->
        raise RuntimeError, "pop_line error"
    end
  end

  @typep munge_line_hash() :: %{String.t() => non_neg_integer()}
  @typep munge_line_acc() ::
           {munge_line_hash(), list(String.t()), nil | list(non_neg_integer()),
            nil | non_neg_integer()}
  @typep munge_line_result() :: {munge_line_hash(), list(String.t()), String.t()}

  @spec lines_to_chars_munge(
          String.t(),
          munge_line_acc(),
          non_neg_integer()
        ) :: munge_line_result()

  # Case 1. Initial text is ""
  defp lines_to_chars_munge("", {h, arr, nil, _}, _max_lines) do
    {h, arr, ""}
  end

  # Case 2. No more text, or overflowed max_lines
  defp lines_to_chars_munge("", {h, arr, chars, _}, _max_lines) do
    {h, Enum.reverse(arr), Enum.reverse(chars) |> List.to_string()}
  end

  # Case 3. Process one line of text and recurse
  defp lines_to_chars_munge(text, {h, arr, chars, next_val}, max_lines) do
    # First time if chars == nil
    {arr, chars, next_val} =
      if is_nil(chars) do
        {Enum.reverse(arr), [], Enum.count(arr)}
      else
        {arr, chars, next_val}
      end

    {line, rest} = pop_line(text)

    {rest, {h, arr, chars, next_val}} =
      cond do
        Map.has_key?(h, line) ->
          val = Map.get(h, line)
          {rest, {h, arr, [val | chars], next_val}}

        next_val < max_lines ->
          {rest, {Map.put(h, line, next_val), [line | arr], [next_val | chars], next_val + 1}}

        true ->
          # Bail out
          {"", {h, arr, chars, next_val}}
      end

    lines_to_chars_munge(rest, {h, arr, chars, next_val}, max_lines)
  end

  @doc """
  Rehydrate the text in a diff from a string of line hashes to real lines of
  text.

    * `diffs` - A difflist.
    * `line_array` - A list of unique strings.

  Returns the rehydrated difflist.
  """
  @spec chars_to_lines(difflist(), list(String.t())) :: difflist()
  def chars_to_lines(diffs, line_array) do
    Enum.map(diffs, fn {op, encoded_text} ->
      {op,
       encoded_text
       |> String.to_charlist()
       |> Enum.reduce("", fn i, text -> text <> Enum.at(line_array, i) end)}
    end)
  end

  @doc """
  Determine the common prefix of two strings.

    * `text1` - First string.
    * `text2` - Second string.

  Returns a tuple `{prefix, rest1, rest2}`, where

    * `prefix` - The common prefix.
    * `rest1` - `text1` with the prefix removed.
    * `rest2` - `text2` with the prefix removed.
  """
  @spec common_prefix(String.t(), String.t()) :: {String.t(), String.t(), String.t()}
  def common_prefix(text1, text2) do
    # Cache the text lengths to prevent multiple calls.
    text1_length = String.length(text1)
    text2_length = String.length(text2)
    n = min(text1_length, text2_length)

    if n == 0 do
      {"", text1, text2}
    else
      prefix =
        Enum.reduce_while(0..(n - 1), "", fn i, acc ->
          ch = String.at(text1, i)

          if ch == String.at(text2, i) do
            {:cont, acc <> ch}
          else
            {:halt, acc}
          end
        end)

      {prefix, String.replace_prefix(text1, prefix, ""), String.replace_prefix(text2, prefix, "")}
    end
  end

  @doc """
  Determine the common suffix of two strings.

    * `text1` - First string.
    * `text2` - Second string.

  Returns a tuple `{suffix, rest1, rest2}`, where

    * `suffix` - The common suffix.
    * `rest1` - `text1` with the suffix removed.
    * `rest2` - `text2` with the suffix removed.
  """
  @spec common_suffix(String.t(), String.t()) :: {String.t(), String.t(), String.t()}
  def common_suffix(text1, text2) do
    # Cache the text lengths to prevent multiple calls.
    text1_length = String.length(text1)
    text2_length = String.length(text2)
    n = min(text1_length, text2_length)

    if n == 0 do
      {"", text1, text2}
    else
      suffix =
        Enum.reduce_while(1..n, "", fn i, acc ->
          ch = String.at(text1, text1_length - i)

          if ch == String.at(text2, text2_length - i) do
            {:cont, ch <> acc}
          else
            {:halt, acc}
          end
        end)

      {suffix, String.replace_suffix(text1, suffix, ""), String.replace_suffix(text2, suffix, "")}
    end
  end

  @doc """
  Determine if the suffix of one string is the prefix of another.

    * `text1` - First string.
    * `text2` - Second string.

  Returns the number of characters common to the end of the first
  string and the start of the second string.
  """
  @spec common_overlap(String.t(), String.t()) :: non_neg_integer()
  def common_overlap(text1, text2) do
    # Cache the text lengths to prevent multiple calls.
    text1_length = String.length(text1)
    text2_length = String.length(text2)
    # Eliminate the null case.
    if text1_length == 0 || text2_length == 0 do
      0
    else
      # Truncate the longer string.
      {text1, text2} =
        cond do
          text1_length > text2_length ->
            {substring(text1, text1_length - text2_length), text2}

          text1_length < text2_length ->
            {text1, substring(text2, 0, text1_length)}

          true ->
            {text1, text2}
        end

      text_length = min(text1_length, text2_length)
      # Quick check for the worst case.
      if text1 == text2 do
        text_length
      else
        best_overlap(0, 1, text_length, text1, text2)
      end
    end
  end

  # Start by looking for a single character match
  # and increase length until no match is found.
  # Performance analysis: https://neil.fraser.name/news/2010/11/04/
  @spec best_overlap(
          non_neg_integer(),
          non_neg_integer(),
          non_neg_integer(),
          String.t(),
          String.t()
        ) :: non_neg_integer()
  defp best_overlap(best, length, text_length, text1, text2) do
    pattern = substring(text1, text_length - length)

    case String.split(text2, pattern, parts: 2) do
      [left, _right] ->
        found = String.length(left)
        length = length + found

        {best, length} =
          if found == 0 || pattern == left do
            {length, length + 1}
          else
            {best, length}
          end

        best_overlap(best, length, text_length, text1, text2)

      _not_found ->
        best
    end
  end

  @typedoc """
  The result of a successful `Diff.half_match/3` call.

  A tuple of five strings:

    1. the prefix of `text1`
    2. the suffix of `text1`
    3. the prefix of `text2`
    4. the suffix of `text2`
    5. the common middle
  """
  @type half_match_result() :: {String.t(), String.t(), String.t(), String.t(), String.t()}

  @doc """
  Do the two texts share a substring which is at least half the length of
  the longer text?

    * `text1` - First string.
    * `text2` - Second string.
    * `deadline` - Unix timestamp (in milliseconds) at which to bail if not yet complete.

  This speedup can produce non-minimal diffs.

  Returns a `half_match_result` 5-tuple, or `nil` if there was no match.
  Returns `nil` if `deadline` is zero (no time limit specified).
  """
  @spec half_match(String.t(), String.t(), non_neg_integer()) ::
          nil | half_match_result()
  def half_match(text1, text2, deadline) do
    if deadline == 0 do
      # Don't risk returning a non-optimal diff if we have unlimited time.
      nil
    else
      # Cache the text lengths to prevent multiple calls.
      text1_length = String.length(text1)
      text2_length = String.length(text2)

      normal_order = text1_length > text2_length

      {longtext, shorttext, longtext_length, shorttext_length} =
        if normal_order do
          {text1, text2, text1_length, text2_length}
        else
          {text2, text1, text2_length, text1_length}
        end

      if longtext_length < 4 || shorttext_length * 2 < longtext_length do
        # Pointless.
        nil
      else
        # First check if the second quarter is the seed for a half-match.
        i = div(longtext_length + 3, 4)
        hm1 = half_match_impl(longtext, shorttext, i)

        # Check again based on the third quarter.
        i = div(longtext_length + 1, 2)
        hm2 = half_match_impl(longtext, shorttext, i)

        longer_half_match(hm1, hm2) |> sorted_half_match(normal_order)
      end
    end
  end

  @spec half_match_impl(String.t(), String.t(), non_neg_integer()) ::
          nil | {String.t(), String.t(), String.t(), String.t(), String.t()}
  defp half_match_impl(longtext, shorttext, i) do
    seed_length = div(String.length(longtext), 4)
    seed = String.slice(longtext, i, seed_length)
    j = index_of(shorttext, seed)
    best_half_match_loop({"", "", "", "", ""}, seed, i, j, longtext, shorttext)
  end

  defp best_half_match_loop(
         {best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common},
         _seed,
         _i,
         -1,
         longtext,
         _shorttext
       ) do
    if String.length(best_common) * 2 >= String.length(longtext) do
      {best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common}
    else
      nil
    end
  end

  defp best_half_match_loop(
         {best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common},
         seed,
         i,
         j,
         longtext,
         shorttext
       ) do
    {longa, longb} = String.split_at(longtext, i)
    {shorta, shortb} = String.split_at(shorttext, j)
    {prefix, ptext1, ptext2} = common_prefix(longb, shortb)
    {suffix, stext1, stext2} = common_suffix(longa, shorta)
    common = suffix <> prefix

    {best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common} =
      if String.length(best_common) < String.length(common) do
        {stext1, ptext1, stext2, ptext2, common}
      else
        {best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common}
      end

    j = index_of(shorttext, seed, j + 1)

    best_half_match_loop(
      {best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common},
      seed,
      i,
      j,
      longtext,
      shorttext
    )
  end

  defp longer_half_match({_, _, _, _, common1} = hm1, {_, _, _, _, common2} = hm2) do
    # Both matched.  Select the longest.
    if String.length(common1) > String.length(common2) do
      hm1
    else
      hm2
    end
  end

  defp longer_half_match(hm1, nil), do: hm1
  defp longer_half_match(nil, hm2), do: hm2
  defp longer_half_match(_, _), do: nil

  # A half-match was found, sort out the return data.
  def sorted_half_match(nil, _), do: nil
  def sorted_half_match(hm, true), do: hm

  def sorted_half_match({prefix1, suffix1, prefix2, suffix2, common}, _) do
    {prefix2, suffix2, prefix1, suffix1, common}
  end

  @typep diffqueue() :: :queue.queue()

  defp safe_drop_r(queue, n \\ 1)

  defp safe_drop_r(queue, 1) do
    if :queue.is_empty(queue) do
      queue
    else
      :queue.drop_r(queue)
    end
  end

  defp safe_drop_r(queue, n) when n > 1 do
    safe_drop_r(queue) |> safe_drop_r(n - 1)
  end

  defp safe_drop_r(queue, _), do: queue

  @doc """
  Reduce the number of edits in a diff by eliminating semantically trivial equalities.

  Returns the updated difflist.
  """
  @spec cleanup_semantic(difflist()) :: difflist()
  def cleanup_semantic([]), do: []

  def cleanup_semantic(diffs) do
    diffs =
      diffs
      |> Cursor.from_list(position: 0)

    {diffs, changes} = split_small_equalities(diffs, {false, :queue.new(), nil, 0, 0, 0, 0})

    diffs =
      if changes do
        # Normalize the diff
        diffs |> cleanup_merge()
      else
        diffs
      end

    if Enum.count(diffs) < 2 do
      diffs
    else
      diffs
      |> cleanup_semantic_lossless()
      |> Cursor.from_list(position: 1)
      |> cleanup_overlap_loop()
    end
  end

  # `equalities` - Double-ended queue of equalities..
  # `last_equality` - Always equal to the text of `:queue.peek_r(equalities)`.
  defp split_small_equalities(
         %Cursor{current: nil} = diffs,
         {changes, _equalities, _last_equality, _length_insertions1, _length_deletions1,
          _length_insertions2, _length_deletions2}
       ) do
    diffs = Cursor.to_list(diffs)
    {diffs, changes}
  end

  defp split_small_equalities(
         %Cursor{current: this_diff} = diffs,
         {changes, equalities, last_equality, length_insertions1, length_deletions1,
          length_insertions2, length_deletions2}
       ) do
    {op, text} = this_diff

    {cursor, changes, equalities, last_equality, length_insertions1, length_deletions1,
     length_insertions2,
     length_deletions2} =
      if op == :equal do
        # Equality found. Insert at rear of queue.
        eq_pos = Cursor.position(diffs)
        equalities = :queue.in(eq_pos, equalities)

        {Cursor.move_forward(diffs), changes, equalities, text, length_insertions2,
         length_deletions2, 0, 0}
      else
        # An insertion or deletion.
        {length_insertions2, length_deletions2} =
          if op == :insert do
            {length_insertions2 + String.length(text), length_deletions2}
          else
            {length_insertions2, length_deletions2 + String.length(text)}
          end

        # Eliminate an equality that is smaller or equal to the edits on both
        # sides of it.
        if !is_nil(last_equality) &&
             String.length(last_equality) <= max(length_insertions1, length_deletions1) &&
             String.length(last_equality) <= max(length_insertions2, length_deletions2) do
          # Walk back to offending equality.
          eq_pos = :queue.get_r(equalities)
          diffs = Cursor.move_to(diffs, eq_pos)

          # Replace equality with a delete.
          # Insert a corresponding an insert.
          new_diffs = [{:delete, last_equality}, {:insert, last_equality}]

          diffs =
            diffs
            |> Cursor.delete(1)
            |> Cursor.insert(new_diffs)

          # Throw away the equality we just deleted.
          # Throw away the previous equality (it needs to be reevaluated).
          equalities = safe_drop_r(equalities, 2)

          if :queue.is_empty(equalities) do
            # There are no previous equalities, walk back to the start.
            # Reset the counters
            {Cursor.move_first(diffs), true, equalities, nil, 0, 0, 0, 0}
          else
            eq_pos = :queue.get_r(equalities)
            # There is a safe equality we can fall back to.
            # Reset the counters
            diffs = Cursor.move_to(diffs, eq_pos)
            {diffs, true, equalities, nil, 0, 0, 0, 0}
          end
        else
          {Cursor.move_forward(diffs), changes, equalities, last_equality, length_insertions1,
           length_deletions1, length_insertions2, length_deletions2}
        end
      end

    split_small_equalities(
      cursor,
      {changes, equalities, last_equality, length_insertions1, length_deletions1,
       length_insertions2, length_deletions2}
    )
  end

  # Find any overlaps between deletions and insertions.
  # e.g: <del>abcxxx</del><ins>xxxdef</ins>
  #   -> <del>abc</del>xxx<ins>def</ins>
  # e.g: <del>xxxabc</del><ins>defxxx</ins>
  #   -> <ins>def</ins>xxx<del>abc</del>
  # Only extract an overlap if it is as big as the edit ahead or behind it.
  @spec cleanup_overlap_loop(Cursor.t()) :: difflist()
  defp cleanup_overlap_loop(%Cursor{current: nil} = diffs) do
    diffs = Cursor.to_list(diffs)

    diffs
  end

  defp cleanup_overlap_loop(%Cursor{} = diffs) do
    {prev_diff, this_diff, _} = Cursor.get(diffs)
    {prev_op, deletion} = prev_diff
    {op, insertion} = this_diff

    diffs =
      if prev_op == :delete && op == :insert do
        overlap_length1 = common_overlap(deletion, insertion)
        overlap_length2 = common_overlap(insertion, deletion)

        if overlap_length1 >= overlap_length2 do
          if overlap_length1 * 2 >= String.length(deletion) ||
               overlap_length1 * 2 >= String.length(insertion) do
            # Overlap found. Insert an equality and trim the surrounding edits.
            overlap = substring(insertion, 0, overlap_length1)
            deletion = substring(deletion, 0, String.length(deletion) - overlap_length1)
            insertion = substring(insertion, overlap_length1)

            new_diffs = [{:delete, deletion}, {:equal, overlap}, {:insert, insertion}]

            diffs
            |> Cursor.move_back()
            |> Cursor.delete(2)
            |> Cursor.insert(new_diffs)
          else
            diffs
          end
        else
          if overlap_length2 * 2 >= String.length(deletion) ||
               overlap_length2 * 2 >= String.length(insertion) do
            # Reverse overlap found.
            # Insert an equality and swap and trim the surrounding edits.
            overlap = substring(deletion, 0, overlap_length2)
            insertion = substring(insertion, 0, String.length(insertion) - overlap_length2)
            deletion = substring(deletion, overlap_length2)

            new_diffs = [{:insert, insertion}, {:equal, overlap}, {:delete, deletion}]

            diffs
            |> Cursor.move_back(1)
            |> Cursor.delete(2)
            |> Cursor.insert(new_diffs)
          else
            diffs
          end
        end
      else
        diffs
      end

    diffs
    |> Cursor.move_forward()
    |> cleanup_overlap_loop()
  end

  @doc """
  Look for single edits in a diff that are surrounded on both sides by equalities
  which can be shifted sideways to align the edit to a word boundary.

  Example: `The c<ins>at c</ins>ame.` becomes `The <ins>cat </ins>came.`

  Returns the updated difflist.
  """
  @spec cleanup_semantic_lossless(difflist()) :: difflist()
  def cleanup_semantic_lossless(diffs) do
    # Intentionally ignore the first and last element (don't need checking).
    diffs
    |> Cursor.from_list(position: 1)
    |> cleanup_semantic_lossless_loop()
  end

  # Intentionally ignore the first and last element (don't need checking).
  defp cleanup_semantic_lossless_loop(%Cursor{next: []} = diffs) do
    Cursor.to_list(diffs)
  end

  defp cleanup_semantic_lossless_loop(%Cursor{} = diffs) do
    {prev_diff, this_diff, next_diff} = Cursor.get(diffs)
    {prev_op, prev_text} = prev_diff
    {next_op, next_text} = next_diff

    diffs =
      if prev_op == :equal && next_op == :equal do
        # This is a single edit surrounded by equalities.
        equality1 = prev_text
        {op, edit} = this_diff
        equality2 = next_text

        # First, shift the edit as far left as possible.
        {suffix, text1, text2} = common_suffix(equality1, edit)

        {equality1, edit, equality2} = {text1, suffix <> text2, suffix <> equality2}

        score1 = semantic_score(equality1, edit)
        score2 = semantic_score(edit, equality2)
        score = score1 + score2

        {_best_score, best_equality1, best_edit, best_equality2} =
          best_score_loop(
            equality1,
            edit,
            equality2,
            {score, equality1, edit, equality2}
          )

        if prev_text != best_equality1 do
          # We have an improvement, save it back to the diff.
          diffs =
            if best_equality1 != "" do
              new_prev = {prev_op, best_equality1}
              # Update prev_diff.
              diffs
              |> Cursor.delete_before(1)
              |> Cursor.insert_before([new_prev])
            else
              # Delete prev_diff.
              Cursor.delete_before(diffs, 1)
            end

          new_cur = {op, best_edit}
          # Update this_diff.
          diffs =
            diffs
            |> Cursor.delete(1)
            |> Cursor.insert_before([new_cur])

          # Now pointing at next_diff
          diffs =
            if best_equality2 != "" do
              new_next = {next_op, best_equality2}
              # Update next_diff
              diffs
              |> Cursor.delete(1)
              |> Cursor.insert_before([new_next])
              |> Cursor.move_back(2)
            else
              # Delete next_diff
              diffs
              |> Cursor.delete(1)
              |> Cursor.move_back(1)
            end

          # Now back to pointing at this_diff
          diffs
        else
          diffs
        end
      else
        diffs
      end

    diffs
    |> Cursor.move_forward()
    |> cleanup_semantic_lossless_loop()
  end

  defp best_score_loop(
         equality1,
         edit,
         equality2,
         {best_score, _best_equality1, _best_edit, _best_equality2} = acc
       ) do
    if edit == "" || equality2 == "" do
      acc
    else
      # Second, step character by character right, looking for the best fit.
      {edit_first, edit} = String.split_at(edit, 1)
      {equality2_first, equality2} = String.split_at(equality2, 1)

      if edit_first != equality2_first do
        acc
      else
        equality1 = equality1 <> edit_first
        edit = edit <> equality2_first
        score1 = semantic_score(equality1, edit)
        score2 = semantic_score(edit, equality2)
        score = score1 + score2
        # The >= encourages trailing rather than leading whitespace on edits.
        if score >= best_score do
          best_score_loop(equality1, edit, equality2, {score, equality1, edit, equality2})
        else
          best_score_loop(
            equality1,
            edit,
            equality2,
            acc
          )
        end
      end
    end
  end

  # Define some regex patterns for matching boundaries.
  @alphanumeric ~r/^[0-9A-Za-z]+$/
  @whitespace ~r/^[\s]+$/
  @line_break ~r/^[\r\n]+$/
  @blank_line_end ~r/\n\r?\n\Z/
  @blank_line_start ~r/\A\r?\n\r?\n/

  @doc """
  Given two strings, compute a score representing whether the internal
  boundary falls on logical boundaries.

  Scores range from 6 (best) to 0 (worst).

    * `one` - First string.
    * `two` - Second string.

  Scores are:

    * 6 if `one` or `two` is an empty string.
    * 5 if a blank line ends in `one` or a blank line starts in `two`.
    * 4 if `one` ends, or `two` starts, with a newline.
    * 3 if `one` ends in a punctuation and `two` starts with white space.
    * 2 if `one` ends, or `two` starts, with white space.
    * 1 if `one` ends, or `two` starts, with a non-alphanumeric.
    * 0 otherwise

  ## Examples

      iex> Diff.semantic_score("two is empty string", "")
      6

      iex> Diff.semantic_score("one ends in blank line\\n\\n", "two")
      5

      iex> Diff.semantic_score("one ends in new line\\n", "two")
      4

      iex> Diff.semantic_score("one sentence.", " space before two")
      3

      iex> Diff.semantic_score("one sentence.", "no space before two")
      1

      iex> Diff.semantic_score("one ends with white space ", "two")
      2

      iex> Diff.semantic_score("one ends in 'punctuation'", "two")
      1

      iex> Diff.semantic_score("one ends in middle of word", "two")
      0

  """
  @spec semantic_score(String.t(), String.t()) :: non_neg_integer()
  def semantic_score("", _two), do: 6
  def semantic_score(_one, ""), do: 6

  # credo:disable-for-lines:38 Credo.Check.Refactor.CyclomaticComplexity
  def semantic_score(one, two) do
    char1 = String.last(one)
    char2 = String.first(two)

    non_alphanumeric1 = !Regex.match?(@alphanumeric, char1)
    non_alphanumeric2 = !Regex.match?(@alphanumeric, char2)
    whitespace1 = Regex.match?(@whitespace, char1)
    whitespace2 = Regex.match?(@whitespace, char2)
    line_break1 = Regex.match?(@line_break, char1)
    line_break2 = Regex.match?(@line_break, char2)
    blank_line1 = line_break1 && Regex.match?(@blank_line_end, one)
    blank_line2 = line_break2 && Regex.match?(@blank_line_start, two)

    cond do
      blank_line1 || blank_line2 ->
        # Five points for blank lines.
        5

      line_break1 || line_break2 ->
        # Four points for line breaks.
        4

      non_alphanumeric1 && !whitespace1 && whitespace2 ->
        # Three points for end of sentences.
        3

      whitespace1 || whitespace2 ->
        # Two points for whitespace.
        2

      non_alphanumeric1 || non_alphanumeric2 ->
        # One point for non-alphanumeric.
        1

      true ->
        0
    end
  end

  @typep efficiency_acc() :: {
           boolean(),
           diffqueue(),
           nil | String.t(),
           non_neg_integer(),
           non_neg_integer(),
           non_neg_integer(),
           non_neg_integer(),
           non_neg_integer()
         }

  @doc """
  Reduce the number of edits in a diff by eliminating operationally trivial equalities.

    * `diff_edit_cost`  Cost of an empty edit operation in terms of edit characters.

  Returns the updated difflist.
  """
  @spec cleanup_efficiency(difflist(), non_neg_integer()) :: difflist()
  def cleanup_efficiency([], _diff_edit_cost), do: []

  def cleanup_efficiency(diffs, diff_edit_cost) do
    {diffs, changes} =
      diffs
      |> Cursor.from_list(position: 0)
      |> cleanup_efficiency_loop(
        {false, :queue.new(), nil, 0, 0, 0, 0, 0},
        diff_edit_cost
      )

    if changes do
      cleanup_merge(diffs)
    else
      diffs
    end
  end

  # `equalities` - Double-ended queue of equalities.
  # `last_equality` - Always equal to the text of `equalities.get_r()`
  # `safe_diff` - The position of the last diff that is known to be unsplittable.
  # `pre_ins` - 1 if there is an insertion operation before the last equality.
  # `pre_del` - 1 if there is a deletion operation before the last equality.
  # `post_ins` - 1 if there is an insertion operation after the last equality.
  # `post_del` - 1 if there is a deletion operation after the last equality.
  # `diff_edit_cost` - Cost of an empty edit operation in terms of edit characters.
  @spec cleanup_efficiency_loop(Cursor.t(), efficiency_acc(), non_neg_integer()) ::
          {difflist(), boolean()}
  defp cleanup_efficiency_loop(
         %Cursor{current: nil} = diffs,
         {changes, _equalities, _last_equality, _safe_diff, _pre_ins, _pre_del, _post_ins,
          _post_del},
         _diff_edit_cost
       ),
       do: {Cursor.to_list(diffs), changes}

  defp cleanup_efficiency_loop(
         %Cursor{current: {op, _} = this_diff} = diffs,
         acc,
         diff_edit_cost
       ) do
    {diffs, acc} =
      if op == :equal do
        # Equality found.
        handle_efficiency_equality(diffs, this_diff, acc, diff_edit_cost)
      else
        # An insertion or deletion.
        handle_efficiency_ins_del(diffs, this_diff, acc, diff_edit_cost)
      end

    diffs
    |> cleanup_efficiency_loop(
      acc,
      diff_edit_cost
    )
  end

  defp handle_efficiency_equality(
         diffs,
         {_op, text},
         {changes, equalities, _last_equality, safe_diff, pre_ins, pre_del, post_ins, post_del},
         diff_edit_cost
       ) do
    eq_pos = Cursor.position(diffs)

    {equalities, last_equality, safe_diff, pre_ins, pre_del} =
      if String.length(text) < diff_edit_cost && (post_ins != 0 || post_del != 0) do
        # Candidate found. Insert at rear of queue.
        equalities = :queue.in(eq_pos, equalities)
        {equalities, text, safe_diff, post_ins, post_del}
      else
        # Not a candidate, and can never become one.
        # Remember our position.
        {:queue.new(), nil, eq_pos, pre_ins, pre_del}
      end

    {Cursor.move_forward(diffs),
     {changes, equalities, last_equality, safe_diff, pre_ins, pre_del, 0, 0}}
  end

  defp handle_efficiency_ins_del(
         diffs,
         {op, _text},
         {changes, equalities, last_equality, safe_diff, pre_ins, pre_del, post_ins, post_del},
         diff_edit_cost
       ) do
    # An insertion or deletion.
    {post_ins, post_del} =
      if op == :delete do
        {post_ins, 1}
      else
        {1, post_del}
      end

    # Five types to be split:
    # <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>
    # <ins>A</ins>X<ins>C</ins><del>D</del>
    # <ins>A</ins><del>B</del>X<ins>C</ins>
    # <ins>A</del>X<ins>C</ins><del>D</del>
    # <ins>A</ins><del>B</del>X<del>C</del>
    ins_del_count = pre_ins + pre_del + post_ins + post_del

    if !is_nil(last_equality) &&
         (ins_del_count == 4 ||
            (String.length(last_equality) * 2 < diff_edit_cost && ins_del_count == 3)) do
      # Walk back to offending equality.
      # Replace equality with a delete.
      # Insert a corresponding an insert.
      eq_pos = :queue.get_r(equalities)

      diffs =
        diffs
        |> Cursor.move_to(eq_pos)
        |> Cursor.delete(1)
        |> Cursor.insert_before([{:delete, last_equality}, {:insert, last_equality}])

      {diffs, equalities, post_ins, post_del} =
        update_equalities_and_move_cursor(diffs, equalities, safe_diff, pre_ins, pre_del)

      {diffs, {true, equalities, nil, safe_diff, pre_ins, pre_del, post_ins, post_del}}
    else
      {Cursor.move_forward(diffs),
       {changes, equalities, last_equality, safe_diff, pre_ins, pre_del, post_ins, post_del}}
    end
  end

  defp update_equalities_and_move_cursor(diffs, equalities, safe_diff, pre_ins, pre_del) do
    # Throw away the equality we just deleted.
    equalities = safe_drop_r(equalities)

    if pre_ins != 0 && pre_del != 0 do
      # No changes made which could affect previous entry, keep going.
      {Cursor.move_forward(diffs), :queue.new(), 1, 1}
    else
      # Throw away the previous equality (it needs to be reevaluated).
      equalities = safe_drop_r(equalities)

      pos =
        case :queue.peek_r(equalities) do
          {:value, eq_pos} ->
            # There is an equality we can fall back to.
            eq_pos

          :empty ->
            # There are no previous questionable equalities,
            # walk back to the last known safe diff.
            safe_diff
        end

      {Cursor.move_to(diffs, pos), equalities, 0, 0}
    end
  end

  @doc """
  Reorder and merge like edit sections in a diff, merging equalities.

  Any edit section can move as long as it doesn't cross an equality.

  Returns the updated difflist.
  """
  @spec cleanup_merge(difflist()) :: difflist()
  def cleanup_merge([]), do: []

  def cleanup_merge(diffs) do
    {diffs, changes} =
      diffs
      |> cleanup_merge_first_pass()
      |> cleanup_merge_second_pass()

    if changes do
      # If shifts were made, the diff needs reordering and another shift sweep.
      cleanup_merge(diffs)
    else
      diffs
    end
  end

  @spec cleanup_merge_first_pass(difflist()) :: difflist()
  defp cleanup_merge_first_pass([]), do: []

  defp cleanup_merge_first_pass(diffs) do
    # Add a dummy entry at the end
    (diffs ++ [{:equal, ""}])
    |> Cursor.from_list(position: 0)
    |> first_pass_loop({0, 0, "", ""})
    |> remove_dummy()
  end

  @type first_pass_acc() ::
          {non_neg_integer(), non_neg_integer(), String.t(), String.t()}

  @spec first_pass_loop(Cursor.t(), first_pass_acc()) :: difflist()

  defp first_pass_loop(%Cursor{current: nil} = diffs, _acc) do
    Cursor.to_list(diffs)
  end

  defp first_pass_loop(
         %Cursor{} = diffs,
         {count_delete, count_insert, text_delete, text_insert}
       ) do
    {prev_diff, this_diff, _next_diff} = Cursor.get(diffs)

    {op, text} = this_diff

    {diffs, acc} =
      case op do
        :insert ->
          {diffs, {count_delete, count_insert + 1, text_delete, text_insert <> text}}

        :delete ->
          {diffs, {count_delete + 1, count_insert, text_delete <> text, text_insert}}

        :equal ->
          # Upon reaching an equality, check for prior redundancies.
          diffs =
            if count_delete + count_insert > 1 do
              combine_previous_inequalities(
                diffs,
                text,
                count_delete,
                count_insert,
                text_delete,
                text_insert
              )
            else
              merge_with_previous_equality(diffs, text, prev_diff)
            end

          {diffs, {0, 0, "", ""}}

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

    diffs
    |> Cursor.move_forward()
    |> first_pass_loop(acc)
  end

  def combine_previous_inequalities(
        diffs,
        text,
        count_delete,
        count_insert,
        text_delete,
        text_insert
      ) do
    # Delete the offending records
    diffs = Cursor.delete_before(diffs, count_delete + count_insert)

    {diffs, text_delete, text_insert} =
      if count_delete > 0 && count_insert > 0 do
        # Both types.
        # Factor out any common prefixes.
        {diffs, text_delete, text_insert} = factor_out_prefixes(diffs, text_delete, text_insert)
        # Factor out any common suffixes.
        factor_out_suffixes(diffs, text, text_delete, text_insert)
      else
        {diffs, text_delete, text_insert}
      end

    # Insert the merged records.
    diffs =
      if text_delete != "" do
        Cursor.insert_before(diffs, [{:delete, text_delete}])
      else
        diffs
      end

    if text_insert != "" do
      Cursor.insert_before(diffs, [{:insert, text_insert}])
    else
      diffs
    end
  end

  def factor_out_prefixes(diffs, text_delete, text_insert) do
    {prefix, text1, text2} = common_prefix(text_delete, text_insert)

    if prefix != "" do
      {prev_diff, _, _} = Cursor.get(diffs)

      diffs =
        if is_tuple(prev_diff) do
          {prev_op, prev_text} = prev_diff

          if prev_op != :equal do
            raise RuntimeError, "Previous diff should have been an equality."
          end

          new_prev = {:equal, prev_text <> prefix}

          diffs
          |> Cursor.delete_before(1)
          |> Cursor.insert_before([new_prev])
        else
          new_head = {:equal, prefix}

          diffs
          |> Cursor.insert_at_head([new_head])
        end

      {diffs, text1, text2}
    else
      {diffs, text_delete, text_insert}
    end
  end

  def factor_out_suffixes(diffs, text, text_delete, text_insert) do
    {suffix, text1, text2} = common_suffix(text_delete, text_insert)

    if suffix != "" do
      new_cur = {:equal, suffix <> text}

      diffs =
        diffs
        |> Cursor.delete(1)
        |> Cursor.insert([new_cur])

      {diffs, text1, text2}
    else
      {diffs, text_delete, text_insert}
    end
  end

  defp merge_with_previous_equality(diffs, text, {:equal, prev_text}) do
    # Merge this equality with the previous one.
    new_cur = {:equal, prev_text <> text}

    diffs
    |> Cursor.move_back(1)
    |> Cursor.delete(2)
    |> Cursor.insert([new_cur])
  end

  defp merge_with_previous_equality(diffs, _, _), do: diffs

  # Second pass: look for single edits surrounded on both sides by equalities
  # which can be shifted sideways to eliminate an equality.
  # e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
  @spec cleanup_merge_second_pass(difflist()) :: {difflist(), boolean()}
  defp cleanup_merge_second_pass([]), do: {[], false}

  defp cleanup_merge_second_pass(diffs) do
    {diffs, changes} =
      Cursor.from_list(diffs, position: 1)
      |> second_pass_loop(false)

    {diffs, changes}
  end

  @spec second_pass_loop(Cursor.t(), boolean()) :: {difflist(), boolean()}
  defp second_pass_loop(%Cursor{next: []} = diffs, changes), do: {Cursor.to_list(diffs), changes}

  defp second_pass_loop(%Cursor{} = diffs, changes) do
    {prev_diff, this_diff, next_diff} = Cursor.get(diffs)

    {prev_op, prev_text} = prev_diff
    {op, text} = this_diff
    {next_op, next_text} = next_diff

    {cursor, changes} =
      if prev_op == :equal && next_op == :equal do
        # This is a single edit surrounded by equalities.
        cond do
          String.ends_with?(text, prev_text) ->
            # Shift the edit over the previous equality.
            diffs =
              if prev_text != "" do
                text =
                  prev_text <> substring(text, 0, String.length(text) - String.length(prev_text))

                next_text = prev_text <> next_text
                new_cur_and_next = [{op, text}, {next_op, next_text}]

                # Delete this_diff and next_diff
                # Update this_diff and next_diff
                diffs
                |> Cursor.delete(2)
                |> Cursor.insert(new_cur_and_next)
              else
                diffs
              end

            # Delete prev_diff
            diffs =
              diffs
              |> Cursor.delete_before(1)

            {diffs, true}

          String.starts_with?(text, next_text) ->
            # Shift the edit over the next equality.
            prev_text = prev_text <> next_text
            text = substring(text, String.length(next_text)) <> next_text

            new_prev_and_cur = [{prev_op, prev_text}, {op, text}]

            # Delete prev_diff
            # Delete this_diff
            # Update prev_diff and this_diff
            # Delete next_diff
            diffs =
              diffs
              |> Cursor.move_back()
              |> Cursor.delete(2)
              |> Cursor.insert(new_prev_and_cur)
              |> Cursor.move_forward(2)
              |> Cursor.delete(1)

            {diffs, true}

          true ->
            {diffs, changes}
        end
      else
        {diffs, changes}
      end

    cursor
    |> Cursor.move_forward()
    |> second_pass_loop(changes)
  end

  # Remove the dummy entry at the end.
  @spec remove_dummy(difflist()) :: difflist()
  defp remove_dummy(diffs) do
    case List.last(diffs) do
      {_, ""} -> Enum.drop(diffs, -1)
      _ -> diffs
    end
  end

  @doc """
  Given `loc`, a location in `text1`, compute and return the equivalent location in
  `text2`.

    * `diffs` - a difflist.
    * `loc` - Location within `text1`.

  Returns location within `text2`.

  ## Examples

      iex> Diff.main("The cat", "The big cat") |> Diff.x_index(1)
      1

      iex> Diff.main("The cat", "The big cat") |> Diff.x_index(4)
      8

  """
  @spec x_index(difflist(), non_neg_integer()) :: non_neg_integer()
  def x_index(diffs, loc) do
    {last_diff, _chars1, _chars2, last_chars1, last_chars2} =
      Enum.reduce_while(diffs, {nil, 0, 0, 0, 0}, fn {op, text} = diff,
                                                     {_last_diff, chars1, chars2, last_chars1,
                                                      last_chars2} ->
        text_length = String.length(text)

        {chars1, chars2} =
          case op do
            :equal ->
              {chars1 + text_length, chars2 + text_length}

            :insert ->
              {chars1, chars2 + text_length}

            :delete ->
              {chars1 + text_length, chars2}

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

        if chars1 > loc do
          # Overshot the location.
          {:halt, {diff, chars1, chars2, last_chars1, last_chars2}}
        else
          {:cont, {nil, chars1, chars2, chars1, chars2}}
        end
      end)

    case last_diff do
      {:delete, _} ->
        # The location was deleted
        last_chars2

      _ ->
        # Add the remaining character length.
        last_chars2 + (loc - last_chars1)
    end
  end

  @html_entities [
    {"&", "&amp;"},
    {"<", "&lt;"},
    {">", "&gt;"},
    {"\n", "&para;<br>"}
  ]

  @doc """
  Generate a pretty HTML report from a difflist.
  """
  @spec pretty_html(difflist()) :: String.t()
  def pretty_html(diffs) do
    Enum.reduce(diffs, "", fn {op, text}, acc ->
      text =
        Enum.reduce(@html_entities, text, fn {from, to}, acc -> String.replace(acc, from, to) end)

      case op do
        :insert -> acc <> "<ins style=\"background:#e6ffe6;\">" <> text <> "</ins>"
        :delete -> acc <> "<del style=\"background:#ffe6e6;\">" <> text <> "</del>"
        :equal -> acc <> "<span>" <> text <> "</span>"
        _ -> raise RuntimeError, "Invalid operation #{inspect(op)}"
      end
    end)
  end

  @doc """
  Compute and return the source text of a diff (all equalities and deletions).
  """
  @spec text1(difflist()) :: String.t()
  def text1(diffs) do
    Enum.reduce(diffs, "", fn {op, text}, acc ->
      if op != :insert do
        acc <> text
      else
        acc
      end
    end)
  end

  @doc """
  Compute and return the destination text of a diff (all equalities and insertions).
  """
  @spec text2(difflist()) :: String.t()
  def text2(diffs) do
    Enum.reduce(diffs, "", fn {op, text}, acc ->
      if op != :delete do
        acc <> text
      else
        acc
      end
    end)
  end

  @doc """
  Compute the Levenshtein distance of a diff--the number of inserted, deleted or
  substituted characters.
  """
  @spec levenshtein(difflist()) :: non_neg_integer()
  def levenshtein(diffs) do
    {levenshtein, insertions, deletions} =
      Enum.reduce(diffs, {0, 0, 0}, fn {op, text}, {levenshtein, insertions, deletions} ->
        text_length = String.length(text)

        case op do
          :insert ->
            {levenshtein, insertions + text_length, deletions}

          :delete ->
            {levenshtein, insertions, deletions + text_length}

          :equal ->
            # A deletion and an insertion is one substitution.
            {levenshtein + max(insertions, deletions), 0, 0}

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

    levenshtein + max(insertions, deletions)
  end

  @doc """
  Crush a diff into an encoded string which describes the operations
  required to transform `text1` into `text2`.

  For example, "=3\t-2\t+ing" means keep 3 chars, delete 2 chars, insert "ing".

  Operations are tab-separated.  Inserted text is escaped using %xx notation.

  ## Examples

      |> iex [{:equal, "abc"}, {:delete, "de"}, {:insert, "ing"}] |> to_delta() |> IO.inspect()
      "=3\\t-2\\t+ing"

  """
  @spec to_delta(difflist()) :: String.t()
  def to_delta(diffs) do
    delta =
      Enum.reduce(diffs, "", fn {op, text}, acc ->
        case op do
          :insert ->
            acc <> "+" <> uri_encode(text) <> "\t"

          :delete ->
            acc <> "-#{String.length(text)}\t"

          :equal ->
            acc <> "=#{String.length(text)}\t"

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

    # Strip off trailing tab character.
    delta
    |> String.replace_suffix("\t", "")
    |> unescape_for_encode_uri_compatability()
  end

  @doc """
  Given the original `text1`, and an encoded string which describes the
  operations required to transform `text1` into `text2`, compute the full diff.

    * `text1 - Source string for the diff.
    * `delta - Encoded delta text.

  Returns a difflist.

  Raises an `ArgumentError` if the encoded delta has invalid contents for the
  given text.
  """
  @spec from_delta(String.t(), String.t()) :: nil | difflist()
  def from_delta(text1, delta) do
    {diffs, pointer} =
      delta
      |> String.split("\t")
      |> Enum.reduce({[], 0}, fn token, {diffs, pointer} ->
        parse_delta_token(token, diffs, pointer, text1)
      end)

    if pointer != String.length(text1) do
      raise ArgumentError,
            "Delta length (#{pointer}) smaller than source text length (#{String.length(text1)})"
    end

    Enum.reverse(diffs)
  end

  # @variable token
  # @accumulator {diffs, pointer}
  # @constant text1
  defp parse_delta_token("", diffs, pointer, _), do: {diffs, pointer}

  defp parse_delta_token(token, diffs, pointer, text1) do
    # Each token begins with a one character parameter which specifies the
    # operation of this token (delete, insert, equality).
    {op, param} = String.split_at(token, 1)

    if op == "+" do
      # decode would change all "+" to " "
      param = param |> String.replace("+", "%2B") |> URI.decode()
      {[{:insert, param} | diffs], pointer}
    else
      n = parse_delta_integer_param(param, pointer, text1)
      text = substring(text1, pointer, pointer + n)

      case op do
        "=" ->
          {[{:equal, text} | diffs], pointer + n}

        "-" ->
          {[{:delete, text} | diffs], pointer + n}

        _ ->
          raise ArgumentError, "Invalid diff operation in from_delta: '#{op}'"
      end
    end
  end

  defp parse_delta_integer_param(param, pointer, text1) do
    case Integer.parse(param) do
      {n, ""} ->
        cond do
          n < 0 ->
            raise ArgumentError, "Negative number in from_delta: #{param}"

          pointer + n > String.length(text1) ->
            raise ArgumentError,
                  "Delta length (#{pointer + n}) larger than source text length (#{String.length(text1)})"

          true ->
            n
        end

      _ ->
        raise ArgumentError, "Invalid number in from_delta: #{param}"
    end
  end

  @doc """
  Returns the diff tuple, or a "nil" pseudo-diff (with op `:nil`
  and empty text).
  """
  @spec undiff(nil | t()) :: t()
  def undiff({op, text}), do: {op, text}
  def undiff(nil), do: {nil, ""}
end