Current section
7 Versions
Jump to
Current section
7 Versions
Compare versions
17
files changed
+1221
additions
-1002
deletions
| @@ -6,6 +6,23 @@ and this project adheres to [Semantic Versioning](http://semver.org/). | |
| 6 6 | |
| 7 7 | ## [Unreleased] |
| 8 8 | |
| 9 | + ## [1.1.0] - 2017-05-02 |
| 10 | + ### Added |
| 11 | + - Property-based tests for composition, transformation and compaction |
| 12 | + |
| 13 | + ### Fixed |
| 14 | + - Insert duplication bug during delta compaction |
| 15 | + - Delete/Delete misbehaviour bug during composition |
| 16 | + |
| 17 | + ### Changed |
| 18 | + - `TextDelta.Delta` is now just `TextDelta` |
| 19 | + - `TextDelta.Delta.*` modules moved into `TextDelta.*` |
| 20 | + - `TextDelta` now generates and operates on `%TextDelta{}` struct |
| 21 | + - `TextDelta.Delta` is still there and works like before in form of a BC |
| 22 | + layer, so your existing code would still work while you upgrade. To be |
| 23 | + removed in 2.x |
| 24 | + - Slightly improved documentation across modules |
| 25 | + |
| 9 26 | ## [1.0.2] - 2017-03-29 |
| 10 27 | ### Fixed |
| 11 28 | - Bug when composition of delete with larger retain resulted in broken delta |
| @@ -29,7 +46,8 @@ and this project adheres to [Semantic Versioning](http://semver.org/). | |
| 29 46 | - Attributes support in `insert` and `retain` |
| 30 47 | - Delta composition and transformation with attributes supported |
| 31 48 | |
| 32 | - [Unreleased]: https://github.com/everzet/text_delta/compare/v1.0.2...HEAD |
| 49 | + [Unreleased]: https://github.com/everzet/text_delta/compare/v1.1.0...HEAD |
| 50 | + [1.1.0]: https://github.com/everzet/text_delta/compare/v1.0.2...v1.1.0 |
| 33 51 | [1.0.2]: https://github.com/everzet/text_delta/compare/v1.0.1...v1.0.2 |
| 34 52 | [1.0.1]: https://github.com/everzet/text_delta/compare/v1.0.0...v1.0.1 |
| 35 53 | [1.0.0]: https://github.com/everzet/text_delta/compare/cdaf5769ba3abb36aa6a6e2431662164a5a30945...v1.0.0 |
| @@ -2,12 +2,12 @@ | |
| 2 2 | |
| 3 3 | [](https://travis-ci.org/everzet/text_delta) |
| 4 4 | |
| 5 | - Elixir counter-part for the Quill.js [Delta](https://github.com/quilljs/delta) |
| 5 | + Elixir counter-part for the Quill.js [Delta](https://quilljs.com/docs/delta/) |
| 6 6 | library. It provides a baseline for [Operational |
| 7 7 | Transformation](https://en.wikipedia.org/wiki/Operational_transformation) of |
| 8 8 | rich text. |
| 9 9 | |
| 10 | - Here's Delta pitch from the [Delta.js repository](http://www.codecommit.com/blog/java/understanding-and-applying-operational-transformation): |
| 10 | + Here's Delta pitch from the [Delta.js repository](https://github.com/quilljs/delta): |
| 11 11 | |
| 12 12 | > Deltas are a simple, yet expressive format that can be used to describe contents and changes. The format is JSON based, and is human readable, yet easily parsible by machines. Deltas can describe any rich text document, includes all text and formatting information, without the ambiguity and complexity of HTML. |
| 13 13 | > |
| @@ -44,15 +44,11 @@ differences from `ot_ex` that might help you make the decision: | |
| 44 44 | the delta format itself. This results in a more verbose format than what |
| 45 45 | `ot_ex` uses. |
| 46 46 | 2. `ot_ex` uses fully reversible operations format, while `text_delta` is a |
| 47 | - one-way. If reversibility is a must, `ot_ex` is a better option. |
| 47 | + one-way. If reversibility is a must, `ot_ex` is the only option. |
| 48 48 | 3. `text_delta` allows arbitrary attributes to be attached to `insert` or |
| 49 49 | `retain` operations. This would allow you to transform rich text alongside |
| 50 50 | plain. With `ot_ex` you pretty much stuck with plain text format, which might |
| 51 51 | not be a big deal if your format of choice is something like Markdown. |
| 52 | - 4. `ot_ex` has RNG-backed test suite, which covers many more cases and, |
| 53 | - potentially, has less bugs. `text_delta` uses more traditional example-based |
| 54 | - tests similar to Quill Delta itself. I believe this provides adequeted |
| 55 | - coverage, but nothing beats RNG :) |
| 56 52 | |
| 57 53 | ## Installation |
| 58 54 | |
| @@ -61,7 +57,7 @@ in `mix.exs`: | |
| 61 57 | |
| 62 58 | ```elixir |
| 63 59 | def deps do |
| 64 | - [{:text_delta, "~> 1.0.0"}] |
| 60 | + [{:text_delta, "~> 1.1.0"}] |
| 65 61 | end |
| 66 62 | ``` |
| 67 63 | |
| @@ -77,6 +73,16 @@ This library is test-driven. In order to run tests, execute: | |
| 77 73 | $> mix test |
| 78 74 | ``` |
| 79 75 | |
| 76 | + If this command fails, it is most likely due to that you don't have EQC |
| 77 | + installed, try: |
| 78 | + |
| 79 | + ```bash |
| 80 | + $> mix eqc.install --mini |
| 81 | + ``` |
| 82 | + |
| 83 | + TextDelta uses property tests to validate that composition, transformation and |
| 84 | + compaction work as expected. |
| 85 | + |
| 80 86 | The library also uses [Credo](http://credo-ci.org) and |
| 81 87 | [Dialyzer](http://erlang.org/doc/man/dialyzer.html). To run both, execute: |
| @@ -4,13 +4,14 @@ | |
| 4 4 | <<"Elixir counter-part for the Quill.js Delta library. It provides a baseline\nfor Operational Transformation of rich text.">>}. |
| 5 5 | {<<"elixir">>,<<"~> 1.4">>}. |
| 6 6 | {<<"files">>, |
| 7 | - [<<"lib/attributes.ex">>,<<"lib/delta.ex">>,<<"lib/delta/composition.ex">>, |
| 8 | - <<"lib/delta/iterator.ex">>,<<"lib/delta/transformation.ex">>, |
| 9 | - <<"lib/operation.ex">>,<<"mix.exs">>,<<"README.md">>,<<"LICENSE.md">>, |
| 10 | - <<"CHANGELOG.md">>]}. |
| 7 | + [<<"lib/text_delta.ex">>,<<"lib/text_delta/attributes.ex">>, |
| 8 | + <<"lib/text_delta/backwards_compatibility_with_1.0.ex">>, |
| 9 | + <<"lib/text_delta/composition.ex">>,<<"lib/text_delta/iterator.ex">>, |
| 10 | + <<"lib/text_delta/operation.ex">>,<<"lib/text_delta/transformation.ex">>, |
| 11 | + <<"mix.exs">>,<<"README.md">>,<<"LICENSE.md">>,<<"CHANGELOG.md">>]}. |
| 11 12 | {<<"licenses">>,[<<"MIT">>]}. |
| 12 13 | {<<"links">>,[{<<"GitHub">>,<<"https://github.com/everzet/text_delta">>}]}. |
| 13 14 | {<<"maintainers">>,[<<"Konstantin Kudryashov <ever.zet@gmail.com>">>]}. |
| 14 15 | {<<"name">>,<<"text_delta">>}. |
| 15 16 | {<<"requirements">>,[]}. |
| 16 | - {<<"version">>,<<"1.0.2">>}. |
| 17 | + {<<"version">>,<<"1.1.0">>}. |
| @@ -1,108 +0,0 @@ | |
| 1 | - defmodule TextDelta.Attributes do |
| 2 | - @moduledoc """ |
| 3 | - Attributes represent format associated with `t:TextDelta.Operation.insert/0` |
| 4 | - or `t:TextDelta.Operation.retain/0` operations. This library uses maps to |
| 5 | - represent attributes. |
| 6 | - |
| 7 | - Same as `TextDelta.Delta`, attributes are composable and transformable. This |
| 8 | - library does not make any assumptions about attribute types, values or |
| 9 | - composition. |
| 10 | - """ |
| 11 | - |
| 12 | - @typedoc """ |
| 13 | - A set of attributes applicable to an operation. |
| 14 | - """ |
| 15 | - @type t :: map |
| 16 | - |
| 17 | - @typedoc """ |
| 18 | - Atom representing transformation priority. Should we prioritise left or right |
| 19 | - side? |
| 20 | - """ |
| 21 | - @type priority :: :left | :right |
| 22 | - |
| 23 | - @doc """ |
| 24 | - Composes two sets of attributes into one. |
| 25 | - |
| 26 | - Simplest way to think about composing arguments is two maps being merged (in |
| 27 | - fact, that's exactly how it is implemented at the moment). |
| 28 | - |
| 29 | - The only thing that makes it different from standard map merge is an optional |
| 30 | - `keep_nils` flag. This flag controls if we want to cleanup all the `null` |
| 31 | - attributes before returning. |
| 32 | - |
| 33 | - This function is used by `TextDelta.Delta.compose/2`. |
| 34 | - |
| 35 | - ## Examples |
| 36 | - |
| 37 | - iex> TextDelta.Attributes.compose(%{color: "blue"}, %{italic: true}) |
| 38 | - %{color: "blue", italic: true} |
| 39 | - |
| 40 | - iex> TextDelta.Attributes.compose(%{bold: true}, %{bold: nil}, true) |
| 41 | - %{bold: nil} |
| 42 | - |
| 43 | - iex> TextDelta.Attributes.compose(%{bold: true}, %{bold: nil}, false) |
| 44 | - %{} |
| 45 | - """ |
| 46 | - @spec compose(t, t, boolean) :: t |
| 47 | - def compose(attrs_a, attrs_b, keep_nils \\ false) |
| 48 | - |
| 49 | - def compose(nil, attrs_b, keep_nils) do |
| 50 | - compose(%{}, attrs_b, keep_nils) |
| 51 | - end |
| 52 | - |
| 53 | - def compose(attrs_a, nil, keep_nils) do |
| 54 | - compose(attrs_a, %{}, keep_nils) |
| 55 | - end |
| 56 | - |
| 57 | - def compose(attrs_a, attrs_b, true) do |
| 58 | - Map.merge(attrs_a, attrs_b) |
| 59 | - end |
| 60 | - |
| 61 | - def compose(attrs_a, attrs_b, false) do |
| 62 | - attrs_a |
| 63 | - |> Map.merge(attrs_b) |
| 64 | - |> remove_nils() |
| 65 | - end |
| 66 | - |
| 67 | - @doc """ |
| 68 | - Transforms given attribute set against another. |
| 69 | - |
| 70 | - This function is used by `TextDelta.Delta.transform/3`. |
| 71 | - |
| 72 | - ## Example |
| 73 | - |
| 74 | - iex> TextDelta.Attributes.transform(%{italic: true}, |
| 75 | - iex> %{bold: true}, :left) |
| 76 | - %{bold: true} |
| 77 | - """ |
| 78 | - @spec transform(t, t, priority) :: t |
| 79 | - def transform(attrs_a, attrs_b, priority) |
| 80 | - |
| 81 | - def transform(nil, attrs_b, priority) do |
| 82 | - transform(%{}, attrs_b, priority) |
| 83 | - end |
| 84 | - |
| 85 | - def transform(attrs_a, nil, priority) do |
| 86 | - transform(attrs_a, %{}, priority) |
| 87 | - end |
| 88 | - |
| 89 | - def transform(_, attrs_b, :right) do |
| 90 | - attrs_b |
| 91 | - end |
| 92 | - |
| 93 | - def transform(attrs_a, attrs_b, :left) do |
| 94 | - remove_duplicates(attrs_b, attrs_a) |
| 95 | - end |
| 96 | - |
| 97 | - defp remove_nils(result) do |
| 98 | - result |
| 99 | - |> Enum.filter(fn {_, v} -> not is_nil(v) end) |
| 100 | - |> Enum.into(%{}) |
| 101 | - end |
| 102 | - |
| 103 | - defp remove_duplicates(attrs_a, attrs_b) do |
| 104 | - attrs_a |
| 105 | - |> Enum.filter(fn {key, _} -> not Map.has_key?(attrs_b, key) end) |
| 106 | - |> Enum.into(%{}) |
| 107 | - end |
| 108 | - end |
| @@ -1,212 +0,0 @@ | |
| 1 | - defmodule TextDelta.Delta do |
| 2 | - @moduledoc """ |
| 3 | - Delta is a format used to describe documents and changes. |
| 4 | - |
| 5 | - Delta can describe any rich text changes or a rich document itself, preserving |
| 6 | - all the formatting. |
| 7 | - |
| 8 | - At the baseline level, delta is an array of operations (constructed via |
| 9 | - `TextDelta.Operation`). Operations can be either |
| 10 | - `t:TextDelta.Operation.insert/0`, `t:TextDelta.Operation.retain/0` or |
| 11 | - `t:TextDelta.Operation.delete/0`. None of the operations contain index, |
| 12 | - meaning that delta aways describes document or a change staring from the very |
| 13 | - beginning. |
| 14 | - |
| 15 | - Delta can describe both changes to and documents themselves. We can think of a |
| 16 | - document as an artefact of all the changes applied to it. This way, newly |
| 17 | - imported document can be thinked of as simply a sequence of `insert`s applied |
| 18 | - to an empty document. |
| 19 | - |
| 20 | - Deltas are composable. This means that a document delta can be composed with |
| 21 | - another delta for that document, resulting in a shorter, optimized delta. |
| 22 | - |
| 23 | - Deltas are also transformable. This attribute of deltas is what enables |
| 24 | - [Operational Transformation][ot] - a way to transform one operation against |
| 25 | - the context of another one. Operational Transformation allows us to build |
| 26 | - optimistic, non-locking collaborative editors. |
| 27 | - |
| 28 | - The format for deltas was deliberately copied from [Quill][quill] - a rich |
| 29 | - text editor for web. This library aims to be an Elixir counter-part for Quill, |
| 30 | - enabling us to build matching backends for the editor. |
| 31 | - |
| 32 | - ## Example |
| 33 | - |
| 34 | - iex> alias TextDelta.Delta |
| 35 | - iex> delta = Delta.new() |> Delta.insert("Gandalf", %{bold: true}) |
| 36 | - [%{insert: "Gandalf", attributes: %{bold: true}}] |
| 37 | - iex> delta = delta |> Delta.insert(" the ") |
| 38 | - [%{insert: "Gandalf", attributes: %{bold: true}}, %{insert: " the "}] |
| 39 | - iex> delta |> Delta.insert("Grey", %{color: "#ccc"}) |
| 40 | - [%{insert: "Gandalf", attributes: %{bold: true}}, %{insert: " the "}, |
| 41 | - %{insert: "Grey", attributes: %{color: "#ccc"}}] |
| 42 | - |
| 43 | - [ot]: https://en.wikipedia.org/wiki/Operational_transformation |
| 44 | - [quill]: https://quilljs.com |
| 45 | - """ |
| 46 | - |
| 47 | - alias TextDelta.{Operation, Attributes} |
| 48 | - alias TextDelta.Delta.{Composition, Transformation} |
| 49 | - |
| 50 | - @typedoc """ |
| 51 | - Delta is a list of `t:TextDelta.Operation.retain/0`, |
| 52 | - `t:TextDelta.Operation.insert/0`, or `t:TextDelta.Operation.delete/0` |
| 53 | - operations. |
| 54 | - """ |
| 55 | - @type t :: [Operation.t] |
| 56 | - |
| 57 | - @typedoc """ |
| 58 | - A document represented as delta. Any rich document can be represented as a set |
| 59 | - of `t:TextDelta.Operation.insert/0` operations. |
| 60 | - """ |
| 61 | - @type document :: [Operation.insert] |
| 62 | - |
| 63 | - @doc """ |
| 64 | - Creates new delta. |
| 65 | - """ |
| 66 | - @spec new :: t |
| 67 | - def new, do: [] |
| 68 | - |
| 69 | - @doc """ |
| 70 | - Creates and appends new insert operation to the delta. |
| 71 | - |
| 72 | - Same as with underlying `TextDelta.Operation.insert/2` function, attributes |
| 73 | - are optional. |
| 74 | - |
| 75 | - `TextDelta.Delta.append/2` is used undert the hood to add operation to the |
| 76 | - delta after construction. So all `append` rules apply. |
| 77 | - |
| 78 | - ## Example |
| 79 | - |
| 80 | - iex> alias TextDelta.Delta |
| 81 | - iex> Delta.new() |> Delta.insert("hello", %{bold: true}) |
| 82 | - [%{insert: "hello", attributes: %{bold: true}}] |
| 83 | - """ |
| 84 | - @spec insert(t, Operation.element, Attributes.t) :: t |
| 85 | - def insert(delta, el, attrs \\ %{}) do |
| 86 | - append(delta, Operation.insert(el, attrs)) |
| 87 | - end |
| 88 | - |
| 89 | - @doc """ |
| 90 | - Creates and appends new retain operation to the delta. |
| 91 | - |
| 92 | - Same as with underlying `TextDelta.Operation.retain/2` function, attributes |
| 93 | - are optional. |
| 94 | - |
| 95 | - `TextDelta.Delta.append/2` is used undert the hood to add operation to the |
| 96 | - delta after construction. So all `append` rules apply. |
| 97 | - |
| 98 | - ## Example |
| 99 | - |
| 100 | - iex> alias TextDelta.Delta |
| 101 | - iex> Delta.new() |> Delta.retain(5, %{italic: true}) |
| 102 | - [%{retain: 5, attributes: %{italic: true}}] |
| 103 | - """ |
| 104 | - @spec retain(t, non_neg_integer, Attributes.t) :: t |
| 105 | - def retain(delta, len, attrs \\ %{}) do |
| 106 | - append(delta, Operation.retain(len, attrs)) |
| 107 | - end |
| 108 | - |
| 109 | - @doc """ |
| 110 | - Creates and appends new delete operation to the delta. |
| 111 | - |
| 112 | - `TextDelta.Delta.append/2` is used undert the hood to add operation to the |
| 113 | - delta after construction. So all `append` rules apply. |
| 114 | - |
| 115 | - ## Example |
| 116 | - |
| 117 | - iex> alias TextDelta.Delta |
| 118 | - iex> Delta.new() |> Delta.delete(3) |
| 119 | - [%{delete: 3}] |
| 120 | - """ |
| 121 | - @spec delete(t, non_neg_integer) :: t |
| 122 | - def delete(delta, len) do |
| 123 | - append(delta, Operation.delete(len)) |
| 124 | - end |
| 125 | - |
| 126 | - @doc """ |
| 127 | - Appends given operation to the delta. |
| 128 | - |
| 129 | - Before adding operation to the delta, this function attempts to compact it by |
| 130 | - applying 2 simple rules: |
| 131 | - |
| 132 | - 1. Delete followed by insert is swapped to ensure that insert goes first. |
| 133 | - 2. Same operations with the same attributes are merged. |
| 134 | - |
| 135 | - These two rules ensure that our deltas are always as short as possible and |
| 136 | - canonical, making it easier to compare, compose and transform them. |
| 137 | - |
| 138 | - ## Example |
| 139 | - |
| 140 | - iex> operation = TextDelta.Operation.insert("hello") |
| 141 | - iex> TextDelta.Delta.new() |> TextDelta.Delta.append(operation) |
| 142 | - [%{insert: "hello"}] |
| 143 | - """ |
| 144 | - @spec append(t, Operation.t) :: t |
| 145 | - def append(delta, op) |
| 146 | - def append(nil, op), do: append([], op) |
| 147 | - def append([], op), do: compact(nil, op, []) |
| 148 | - def append(delta, []), do: delta |
| 149 | - def append(delta, op) do |
| 150 | - delta |
| 151 | - |> List.last() |
| 152 | - |> compact(op, Enum.slice(delta, 0..-2)) |
| 153 | - end |
| 154 | - |
| 155 | - defdelegate compose(delta_a, delta_b), to: Composition |
| 156 | - defdelegate transform(delta_a, delta_b, priority), to: Transformation |
| 157 | - |
| 158 | - @doc """ |
| 159 | - Trims trailing retains from the end of a given delta. |
| 160 | - |
| 161 | - ## Example |
| 162 | - |
| 163 | - iex> [%{insert: "hello"}, %{retain: 5}] |> TextDelta.Delta.trim() |
| 164 | - [%{insert: "hello"}] |
| 165 | - """ |
| 166 | - @spec trim(t) :: t |
| 167 | - def trim(delta) |
| 168 | - def trim([]), do: [] |
| 169 | - def trim(delta) do |
| 170 | - last_operation = List.last(delta) |
| 171 | - case Operation.trimmable?(last_operation) do |
| 172 | - true -> |
| 173 | - delta |
| 174 | - |> Enum.slice(0..-2) |
| 175 | - |> trim() |
| 176 | - false -> |
| 177 | - delta |
| 178 | - end |
| 179 | - end |
| 180 | - |
| 181 | - defp compact(last_op, %{insert: ""}, delta_remainder) do |
| 182 | - delta_remainder ++ List.wrap(last_op) |
| 183 | - end |
| 184 | - |
| 185 | - defp compact(last_op, %{retain: 0}, delta_remainder) do |
| 186 | - delta_remainder ++ List.wrap(last_op) |
| 187 | - end |
| 188 | - |
| 189 | - defp compact(last_op, %{delete: 0}, delta_remainder) do |
| 190 | - delta_remainder ++ List.wrap(last_op) |
| 191 | - end |
| 192 | - |
| 193 | - defp compact(nil, new_op, _) do |
| 194 | - List.wrap(new_op) |
| 195 | - end |
| 196 | - |
| 197 | - defp compact(%{delete: _} = del, %{insert: _} = ins, delta_remainder) do |
| 198 | - compacted_insert = |
| 199 | - delta_remainder |
| 200 | - |> List.last() |
| 201 | - |> compact(ins, Enum.slice(delta_remainder, 0..-2)) |
| 202 | - |
| 203 | - delta_remainder |
| 204 | - |> Enum.slice(0..-2) |
| 205 | - |> Kernel.++(compacted_insert) |
| 206 | - |> Kernel.++([del]) |
| 207 | - end |
| 208 | - |
| 209 | - defp compact(last_op, new_op, delta_remainder) do |
| 210 | - delta_remainder ++ Operation.compact(last_op, new_op) |
| 211 | - end |
| 212 | - end |
Loading more files…