text_delta

defmodule TextDelta.Delta do
  @moduledoc """
  Delta is a format used to describe documents and changes.

  Delta can describe any rich text changes or a rich document itself, preserving
  all the formatting.

  At the baseline level, delta is an array of operations (constructed via
  `TextDelta.Operation`). Operations can be either
  `t:TextDelta.Operation.insert/0`, `t:TextDelta.Operation.retain/0` or
  `t:TextDelta.Operation.delete/0`. None of the operations contain index,
  meaning that delta aways describes document or a change staring from the very
  beginning.

  Delta can describe both changes to and documents themselves. We can think of a
  document as an artefact of all the changes applied to it. This way, newly
  imported document can be thinked of as simply a sequence of `insert`s applied
  to an empty document.

  Deltas are composable. This means that a document delta can be composed with
  another delta for that document, resulting in a shorter, optimized delta.

  Deltas are also transformable. This attribute of deltas is what enables
  [Operational Transformation][ot] - a way to transform one operation against
  the context of another one. Operational Transformation allows us to build
  optimistic, non-locking collaborative editors.

  The format for deltas was deliberately copied from [Quill][quill] - a rich
  text editor for web. This library aims to be an Elixir counter-part for Quill,
  enabling us to build matching backends for the editor.

  ## Example

      iex> alias TextDelta.Delta
      iex> delta = Delta.new() |> Delta.insert("Gandalf", %{bold: true})
      [%{insert: "Gandalf", attributes: %{bold: true}}]
      iex> delta = delta |> Delta.insert(" the ")
      [%{insert: "Gandalf", attributes: %{bold: true}}, %{insert: " the "}]
      iex> delta |> Delta.insert("Grey", %{color: "#ccc"})
      [%{insert: "Gandalf", attributes: %{bold: true}}, %{insert: " the "},
       %{insert: "Grey", attributes: %{color: "#ccc"}}]

  [ot]: https://en.wikipedia.org/wiki/Operational_transformation
  [quill]: https://quilljs.com
  """

  alias TextDelta.{Operation, Attributes}
  alias TextDelta.Delta.{Composition, Transformation}

  @typedoc """
  Delta is a list of `t:TextDelta.Operation.retain/0`,
  `t:TextDelta.Operation.insert/0`, or `t:TextDelta.Operation.delete/0`
  operations.
  """
  @type t :: [Operation.t]

  @typedoc """
  A document represented as delta. Any rich document can be represented as a set
  of `t:TextDelta.Operation.insert/0` operations.
  """
  @type document :: [Operation.insert]

  @doc """
  Creates new delta.
  """
  @spec new :: t
  def new, do: []

  @doc """
  Creates and appends new insert operation to the delta.

  Same as with underlying `TextDelta.Operation.insert/2` function, attributes
  are optional.

  `TextDelta.Delta.append/2` is used undert the hood to add operation to the
  delta after construction. So all `append` rules apply.

  ## Example

      iex> alias TextDelta.Delta
      iex> Delta.new() |> Delta.insert("hello", %{bold: true})
      [%{insert: "hello", attributes: %{bold: true}}]
  """
  @spec insert(t, Operation.element, Attributes.t) :: t
  def insert(delta, el, attrs \\ %{}) do
    append(delta, Operation.insert(el, attrs))
  end

  @doc """
  Creates and appends new retain operation to the delta.

  Same as with underlying `TextDelta.Operation.retain/2` function, attributes
  are optional.

  `TextDelta.Delta.append/2` is used undert the hood to add operation to the
  delta after construction. So all `append` rules apply.

  ## Example

      iex> alias TextDelta.Delta
      iex> Delta.new() |> Delta.retain(5, %{italic: true})
      [%{retain: 5, attributes: %{italic: true}}]
  """
  @spec retain(t, non_neg_integer, Attributes.t) :: t
  def retain(delta, len, attrs \\ %{}) do
    append(delta, Operation.retain(len, attrs))
  end

  @doc """
  Creates and appends new delete operation to the delta.

  `TextDelta.Delta.append/2` is used undert the hood to add operation to the
  delta after construction. So all `append` rules apply.

  ## Example

      iex> alias TextDelta.Delta
      iex> Delta.new() |> Delta.delete(3)
      [%{delete: 3}]
  """
  @spec delete(t, non_neg_integer) :: t
  def delete(delta, len) do
    append(delta, Operation.delete(len))
  end

  @doc """
  Appends given operation to the delta.

  Before adding operation to the delta, this function attempts to compact it by
  applying 2 simple rules:

  1. Delete followed by insert is swapped to ensure that insert goes first.
  2. Same operations with the same attributes are merged.

  These two rules ensure that our deltas are always as short as possible and
  canonical, making it easier to compare, compose and transform them.

  ## Example

      iex> operation = TextDelta.Operation.insert("hello")
      iex> TextDelta.Delta.new() |> TextDelta.Delta.append(operation)
      [%{insert: "hello"}]
  """
  @spec append(t, Operation.t) :: t
  def append(delta, op)
  def append(nil, op), do: append([], op)
  def append([], op), do: compact(nil, op, [])
  def append(delta, []), do: delta
  def append(delta, op) do
    delta
    |> List.last()
    |> compact(op, Enum.slice(delta, 0..-2))
  end

  defdelegate compose(delta_a, delta_b), to: Composition
  defdelegate transform(delta_a, delta_b, priority), to: Transformation

  @doc """
  Trims trailing retains from the end of a given delta.

  ## Example

      iex> [%{insert: "hello"}, %{retain: 5}] |> TextDelta.Delta.trim()
      [%{insert: "hello"}]
  """
  @spec trim(t) :: t
  def trim(delta)
  def trim([]), do: []
  def trim(delta) do
    last_operation = List.last(delta)
    case Operation.trimmable?(last_operation) do
      true ->
        delta
        |> Enum.slice(0..-2)
        |> trim()
      false ->
        delta
    end
  end

  defp compact(last_op, %{insert: ""}, delta_remainder) do
    delta_remainder ++ List.wrap(last_op)
  end

  defp compact(last_op, %{retain: 0}, delta_remainder) do
    delta_remainder ++ List.wrap(last_op)
  end

  defp compact(last_op, %{delete: 0}, delta_remainder) do
    delta_remainder ++ List.wrap(last_op)
  end

  defp compact(nil, new_op, _) do
    List.wrap(new_op)
  end

  defp compact(%{delete: _} = del, %{insert: _} = ins, delta_remainder) do
    compacted_insert =
      delta_remainder
      |> List.last()
      |> compact(ins, Enum.slice(delta_remainder, 0..-2))

    delta_remainder
    |> Enum.slice(0..-2)
    |> Kernel.++(compacted_insert)
    |> Kernel.++([del])
  end

  defp compact(last_op, new_op, delta_remainder) do
    delta_remainder ++ Operation.compact(last_op, new_op)
  end
end