defmodule Jsonpatch do
  @moduledoc """
  A implementation of [RFC 6902](https://tools.ietf.org/html/rfc6902) in pure Elixir.

  The patch can be a single change or a list of things that shall be changed. Therefore
  a list or a single JSON patch can be provided. Every patch belongs to a certain operation
  which influences the usage.

  According to [RFC 6901](https://tools.ietf.org/html/rfc6901) escaping of `/` and `~` is done
  by using `~1` for `/` and `~0` for `~`.
  """

  alias Jsonpatch.Types
  alias Jsonpatch.Operation.{Add, Copy, Move, Remove, Replace, Test}

  @typedoc """
  A valid Jsonpatch operation by RFC 6902
  """
  @type t :: map() | Add.t() | Remove.t() | Replace.t() | Copy.t() | Move.t() | Test.t()

  @doc """
  Apply a Jsonpatch or a list of Jsonpatches to a map or struct. The whole patch will not be applied
  when any path is invalid or any other error occured. When a list is provided, the operations are
  applied in the order as they appear in the list.

  Atoms are never garbage collected. Therefore, `Jsonpatch` works by default only with maps
  which used binary strings as key. This behaviour can be controlled via the `:keys` option.

  ## Examples
      iex> patch = [
      ...> %{op: "add", path: "/age", value: 33},
      ...> %{op: "replace", path: "/hobbies/0", value: "Elixir!"},
      ...> %{op: "replace", path: "/married", value: true},
      ...> %{op: "remove", path: "/hobbies/2"},
      ...> %{op: "remove", path: "/hobbies/1"},
      ...> %{op: "copy", from: "/name", path: "/surname"},
      ...> %{op: "move", from: "/home", path: "/work"},
      ...> %{op: "test", path: "/name", value: "Bob"}
      ...> ]
      iex> target = %{"name" => "Bob", "married" => false, "hobbies" => ["Sport", "Elixir", "Football"], "home" => "Berlin"}
      iex> Jsonpatch.apply_patch(patch, target)
      {:ok, %{"name" => "Bob", "married" => true, "hobbies" => ["Elixir!"], "age" => 33, "surname" => "Bob", "work" => "Berlin"}}

      iex> # Patch will not be applied if test fails. The target will not be changed.
      iex> patch = [
      ...> %{op: "add", path: "/age", value: 33},
      ...> %{op: "test", path: "/name", value: "Alice"}
      ...> ]
      iex> target = %{"name" => "Bob", "married" => false, "hobbies" => ["Sport", "Elixir", "Football"], "home" => "Berlin"}
      iex> Jsonpatch.apply_patch(patch, target)
      {:error, %Jsonpatch.Error{patch: %{"op" => "test", "path" => "/name", "value" => "Alice"}, patch_index: 1, reason: {:test_failed, "Expected value '\\"Alice\\"' at '/name'"}}}

      iex> # Patch will succeed, not applying invalid path operations.
      iex> patch = [
      ...> %{op: "replace", path: "/name", value: "Alice"},
      ...> %{op: "replace", path: "/age", value: 42}
      ...> ]
      iex> target = %{"name" => "Bob"} # No age in target
      iex> Jsonpatch.apply_patch(patch, target, ignore_invalid_paths: true)
      {:ok, %{"name" => "Alice"}}
  """
  @spec apply_patch(t() | [t()], target :: Types.json_container(), Types.opts()) ::
          {:ok, Types.json_container()} | {:error, Jsonpatch.Error.t()}
  def apply_patch(json_patch, target, opts \\ []) do
    # https://datatracker.ietf.org/doc/html/rfc6902#section-3
    # > Operations are applied sequentially in the order they appear in the array.
    {ignore_invalid_paths?, opts} = Keyword.pop(opts, :ignore_invalid_paths, false)

    json_patch
    |> List.wrap()
    |> Enum.with_index()
    |> Enum.reduce_while({:ok, target}, fn {patch, patch_index}, {:ok, acc} ->
      patch = cast_to_op_map(patch)

      do_apply_patch(patch, acc, opts)
      |> handle_patch_result(acc, patch, patch_index, ignore_invalid_paths?)
    end)
  end

  defp handle_patch_result(result, acc, patch, patch_index, ignore_invalid_paths?) do
    case result do
      {:error, {error, _} = reason} ->
        if ignore_invalid_paths? && error == :invalid_path do
          {:cont, {:ok, acc}}
        else
          error = %Jsonpatch.Error{patch: patch, patch_index: patch_index, reason: reason}
          {:halt, {:error, error}}
        end

      {:ok, res} ->
        {:cont, {:ok, res}}
    end
  end

  defp cast_to_op_map(%struct_mod{} = json_patch) do
    json_patch =
      json_patch
      |> Map.from_struct()

    op =
      case struct_mod do
        Add -> "add"
        Remove -> "remove"
        Replace -> "replace"
        Copy -> "copy"
        Move -> "move"
        Test -> "test"
      end

    json_patch = Map.put(json_patch, "op", op)

    cast_to_op_map(json_patch)
  end

  defp cast_to_op_map(json_patch) do
    Map.new(json_patch, fn {k, v} -> {to_string(k), v} end)
  end

  defp do_apply_patch(%{"op" => "add", "path" => path, "value" => value}, target, opts) do
    Add.apply(%Add{path: path, value: value}, target, opts)
  end

  defp do_apply_patch(%{"op" => "remove", "path" => path}, target, opts) do
    Remove.apply(%Remove{path: path}, target, opts)
  end

  defp do_apply_patch(%{"op" => "replace", "path" => path, "value" => value}, target, opts) do
    Replace.apply(%Replace{path: path, value: value}, target, opts)
  end

  defp do_apply_patch(%{"op" => "copy", "from" => from, "path" => path}, target, opts) do
    Copy.apply(%Copy{from: from, path: path}, target, opts)
  end

  defp do_apply_patch(%{"op" => "move", "from" => from, "path" => path}, target, opts) do
    Move.apply(%Move{from: from, path: path}, target, opts)
  end

  defp do_apply_patch(%{"op" => "test", "path" => path, "value" => value}, target, opts) do
    Test.apply(%Test{path: path, value: value}, target, opts)
  end

  defp do_apply_patch(json_patch, _target, _opts) do
    {:error, {:invalid_spec, json_patch}}
  end

  @doc """
  Apply a Jsonpatch or a list of Jsonpatches to a map or struct. In case of an error
  it will raise an exception. When a list is provided, the operations are applied in
  the order as they appear in the list.

  (See Jsonpatch.apply_patch/2 for more details)
  """
  @spec apply_patch!(t() | list(t()), target :: Types.json_container(), Types.opts()) ::
          Types.json_container()
  def apply_patch!(json_patch, target, opts \\ []) do
    case apply_patch(json_patch, target, opts) do
      {:ok, patched} -> patched
      {:error, _} = error -> raise JsonpatchException, error
    end
  end

  @doc """
  Creates a patch from the difference of a source map to a destination map or list.

  ## Options

    * `:ancestor_path` - Sets the initial ancestor path for the diff operation.
      Defaults to `""` (root). Useful when you need to diff starting from a nested path.
    * `:prepare_map` - A function that lets to customize maps and structs before diffing.
      Defaults to `fn map -> map end` (no-op). Useful when you need to customize
      how maps and structs are handled during the diff process. Example:

      ```elixir
      fn
        %Struct{field1: value1, field2: value2} -> %{field1: "\#{value1} - \#{value2}"}
        %OtherStruct{} = struct -> Map.take(struct, [:field1])
        map -> map
      end
      ```

  ## Examples

      iex> source = %{"name" => "Bob", "married" => false, "hobbies" => ["Elixir", "Sport", "Football"]}
      iex> destination = %{"name" => "Bob", "married" => true, "hobbies" => ["Elixir!"], "age" => 33}
      iex> Jsonpatch.diff(source, destination)
      [
        %{path: "/married", value: true, op: "replace"},
        %{path: "/hobbies/2", op: "remove"},
        %{path: "/hobbies/1", op: "remove"},
        %{path: "/hobbies/0", value: "Elixir!", op: "replace"},
        %{path: "/age", value: 33, op: "add"}
      ]

      iex> source = %{"a" => 1, "b" => 2}
      iex> destination = %{"a" => 3, "c" => 4}
      iex> Jsonpatch.diff(source, destination, ancestor_path: "/nested")
      [
        %{path: "/nested/b", op: "remove"},
        %{path: "/nested/c", value: 4, op: "add"},
        %{path: "/nested/a", value: 3, op: "replace"}
      ]
  """
  @spec diff(Types.json_container(), Types.json_container(), Types.opts_diff()) :: [Jsonpatch.t()]
  def diff(source, destination, opts \\ []) do
    opts =
      opts
      |> Keyword.update(:object_hash, nil, &make_safe_hash_fn/1)
      |> Keyword.validate!(
        ancestor_path: "",
        prepare_map: &Function.identity/1,
        object_hash: nil
      )

    do_diff(destination, source, opts[:ancestor_path], nil, [], opts)
  end

  defguardp are_unequal_maps(val1, val2) when val1 != val2 and is_map(val2) and is_map(val1)
  defguardp are_unequal_lists(val1, val2) when val1 != val2 and is_list(val2) and is_list(val1)

  defp do_diff(dest, source, path, key, patches, opts) when are_unequal_lists(dest, source) do
    # uneqal lists, let's use a specialized function for that
    do_list_diff(dest, source, join_key(path, key), patches, opts)
  end

  defp do_diff(dest, source, path, key, patches, opts) when are_unequal_maps(dest, source) do
    # Convert structs to maps if prepare_map function is provided
    dest = maybe_prepare_map(dest, opts)
    source = maybe_prepare_map(source, opts)

    if not is_map(dest) or not is_map(source) do
      # type changed, let's process it again
      do_diff(dest, source, path, key, patches, opts)
    else
      # uneqal maps, let's use a specialized function for that
      do_map_diff(dest, source, join_key(path, key), patches, opts)
    end
  end

  defp do_diff(dest, source, path, key, patches, opts) when dest != source do
    # scalar values or change of type (map -> list etc), let's just make a replace patch
    [%{op: "replace", path: join_key(path, key), value: maybe_prepare_map(dest, opts)} | patches]
  end

  defp do_diff(_dest, _source, _path, _key, patches, _opts) do
    # no changes, return patches as is
    patches
  end

  defp do_map_diff(%{} = destination, %{} = source, ancestor_path, patches, opts) do
    # entrypoint for map diff, let's convert the map to a list of {k, v} tuples
    destination
    |> Map.to_list()
    |> do_map_diff(source, ancestor_path, patches, [], opts)
  end

  defp do_map_diff([], source, ancestor_path, patches, checked_keys, _opts) do
    # The complete desination was check. Every key that is not in the list of
    # checked keys, must be removed.
    Enum.reduce(source, patches, fn {k, _}, patches ->
      if k in checked_keys do
        patches
      else
        [%{op: "remove", path: join_key(ancestor_path, k)} | patches]
      end
    end)
  end

  defp do_map_diff([{key, val} | rest], source, ancestor_path, patches, checked_keys, opts) do
    # normal iteration through list of map {k, v} tuples. We track seen keys to later remove not seen keys.
    patches =
      case Map.fetch(source, key) do
        {:ok, source_val} ->
          do_diff(val, source_val, ancestor_path, key, patches, opts)

        :error ->
          value = maybe_prepare_map(val, opts)
          [%{op: "add", path: join_key(ancestor_path, key), value: value} | patches]
      end

    # Diff next value of same level
    do_map_diff(rest, source, ancestor_path, patches, [key | checked_keys], opts)
  end

  defp do_list_diff(destination, source, ancestor_path, patches, opts) do
    if opts[:object_hash] do
      do_hash_list_diff(destination, source, ancestor_path, patches, opts)
    else
      do_pairwise_list_diff(destination, source, ancestor_path, patches, 0, opts)
    end
  catch
    # happens if we've got a nil hash or we tried to hash a non-map
    :hash_not_implemented ->
      do_pairwise_list_diff(destination, source, ancestor_path, patches, 0, opts)
  end

  defp do_pairwise_list_diff(destination, source, ancestor_path, patches, idx, opts)

  defp do_pairwise_list_diff([], [], _path, patches, _idx, _opts), do: patches

  defp do_pairwise_list_diff([], [_item | source_rest], ancestor_path, patches, idx, opts) do
    # if we find any leftover items in source, we have to remove them
    patches = [%{op: "remove", path: join_key(ancestor_path, idx)} | patches]
    do_pairwise_list_diff([], source_rest, ancestor_path, patches, idx + 1, opts)
  end

  defp do_pairwise_list_diff(items, [], ancestor_path, patches, idx, opts) do
    # we have to do it without recursion, because we have to keep the order of the items
    items
    |> Enum.map_reduce(idx, fn val, idx ->
      {%{op: "add", path: join_key(ancestor_path, idx), value: maybe_prepare_map(val, opts)},
       idx + 1}
    end)
    |> elem(0)
    |> Kernel.++(patches)
  end

  defp do_pairwise_list_diff(
         [val | rest],
         [source_val | source_rest],
         ancestor_path,
         patches,
         idx,
         opts
       ) do
    # case when there's an item in both desitation and source. Let's just compare them
    patches = do_diff(val, source_val, ancestor_path, idx, patches, opts)
    do_pairwise_list_diff(rest, source_rest, ancestor_path, patches, idx + 1, opts)
  end

  defp do_hash_list_diff(destination, source, ancestor_path, patches, opts) do
    hash_fn = Keyword.fetch!(opts, :object_hash)

    {additions, modifications, removals} =
      greedy_find_additions_modifications_removals(
        List.to_tuple(destination),
        List.to_tuple(source),
        index_by(destination, hash_fn),
        index_by(source, hash_fn),
        hash_fn,
        ancestor_path,
        opts
      )

    List.flatten([removals, additions, modifications, patches])
  end

  # credo:disable-for-next-line
  defp greedy_find_additions_modifications_removals(
         dest,
         source,
         dest_map,
         source_map,
         hash_fn,
         path,
         opts,
         dest_idx \\ 0,
         source_idx \\ 0,
         additions \\ [],
         modifications \\ [],
         removals \\ []
       ) do
    cond do
      tuple_size(dest) == dest_idx ->
        # we're at the end of the destination tuple, let's remove all remaining source items
        removals = add_removals(source_idx, tuple_size(source) - 1, path, removals)
        {Enum.reverse(additions), modifications, removals}

      tuple_size(source) == source_idx ->
        # we're at the end of the source tuple, let's add all remaining destination items
        additions = add_additions(dest_idx, tuple_size(dest) - 1, path, dest, additions, opts)
        {Enum.reverse(additions), modifications, removals}

      true ->
        # we're in the middle of the tuples, let's find the next matching items
        dest_item = elem(dest, dest_idx)
        source_item = elem(source, source_idx)

        source_hash = hash_fn.(source_item)
        dest_hash = hash_fn.(dest_item)

        if source_hash == dest_hash do
          # same items, let's diff recursively and bump both indexes
          modifications = do_diff(dest_item, source_item, path, dest_idx, modifications, opts)

          greedy_find_additions_modifications_removals(
            dest,
            source,
            dest_map,
            source_map,
            hash_fn,
            path,
            opts,
            dest_idx + 1,
            source_idx + 1,
            additions,
            modifications,
            removals
          )
        else
          # different items, let's find index of destination item in source and vice versa
          {next_dest_idx, next_source_idx} =
            determine_next_idx(
              dest_idx,
              source_idx,
              Map.get(dest_map, source_hash),
              Map.get(source_map, dest_hash)
            )

          removals = add_removals(source_idx, next_source_idx - 1, path, removals)
          additions = add_additions(dest_idx, next_dest_idx - 1, path, dest, additions, opts)

          greedy_find_additions_modifications_removals(
            dest,
            source,
            dest_map,
            source_map,
            hash_fn,
            path,
            opts,
            next_dest_idx,
            next_source_idx,
            additions,
            modifications,
            removals
          )
        end
    end
  end

  # credo:disable-for-next-line
  defp determine_next_idx(d_idx, s_idx, next_d_idx, next_s_idx) do
    dest_found = next_d_idx != nil and next_d_idx > d_idx
    source_found = next_s_idx != nil and next_s_idx > s_idx
    source_closer = dest_found and source_found and next_s_idx - s_idx < next_d_idx - d_idx

    cond do
      # in case when we can jump to either of them, we want to jump to the closer one
      source_closer -> {d_idx, next_s_idx}
      # only source is found ahead, we have to do source jump
      next_d_idx == nil and source_found -> {d_idx, next_s_idx}
      # only dest is found ahead, we have to do dest jump
      next_s_idx == nil and dest_found -> {next_d_idx, s_idx}
      # neither is found ahead, we have to advance both indexes
      true -> {d_idx + 1, s_idx + 1}
    end
  end

  @compile {:inline, index_by: 2}
  defp index_by(list, hash_fn) do
    list
    |> Enum.reduce({%{}, 0}, fn item, {map, idx} ->
      # if we have a hash collision, we throw an error and handle as if the hash is not implemented
      {Map.update(map, hash_fn.(item), idx, fn _ -> throw(:hash_not_implemented) end), idx + 1}
    end)
    |> elem(0)
  end

  @compile {:inline, add_removals: 4}
  defp add_removals(from_idx, to_idx, path, removals) do
    Enum.reduce(from_idx..to_idx//1, removals, fn idx, removals ->
      [%{op: "remove", path: join_key(path, idx)} | removals]
    end)
  end

  @compile {:inline, add_additions: 6}
  defp add_additions(from_idx, to_idx, path, dest_tuple, additions, opts) do
    Enum.reduce(from_idx..to_idx//1, additions, fn idx, additions ->
      value = dest_tuple |> elem(idx) |> maybe_prepare_map(opts)
      [%{op: "add", path: join_key(path, idx), value: value} | additions]
    end)
  end

  @compile {:inline, maybe_prepare_map: 2}
  defp maybe_prepare_map(value, opts) when is_map(value) do
    prepare_fn = Keyword.fetch!(opts, :prepare_map)
    prepare_fn.(value)
  end

  defp maybe_prepare_map(value, _opts), do: value

  @compile {:inline, escape: 1}
  defp escape(fragment) when is_binary(fragment) do
    fragment =
      if :binary.match(fragment, "~") != :nomatch,
        do: String.replace(fragment, "~", "~0"),
        else: fragment

    if :binary.match(fragment, "/") != :nomatch,
      do: String.replace(fragment, "/", "~1"),
      else: fragment
  end

  defp escape(fragment), do: fragment

  @compile {:inline, join_key: 2}
  defp join_key(path, nil), do: path
  defp join_key(path, key), do: "#{path}/#{escape(key)}"

  defp make_safe_hash_fn(hash_fn) do
    # we want to compare only maps, and returning nil should mean
    # we should compare lists pairwise instead
    fn
      %{} = item ->
        case hash_fn.(item) do
          nil -> throw(:hash_not_implemented)
          hash -> hash
        end

      _item ->
        throw(:hash_not_implemented)
    end
  end
end