Otzel

Otzel is an Elixir library for Operational Transformation (OT), providing a robust foundation for building collaborative real-time editing applications.

What is Operational Transformation?

Operational Transformation is a technique for maintaining consistency in collaborative editing systems. When multiple users edit a shared document simultaneously, OT ensures that all users see the same final result regardless of the order in which edits are received.

Otzel implements the Delta format, originally designed for the Quill rich text editor. Deltas represent both documents and changes to documents using a simple, composable format based on three operations: insert, retain, and delete.

Features

• Full OT Operations: compose, transform, invert, and diff
• Rich Text Support: Attributes for formatting (bold, italic, colors, etc.)
• Embedded Content: Support for non-text embeds (images, videos, custom types)
• Efficient String Handling: Optimized IO-list based string representation
• JSON Serialization: Compatible with Quill Delta JSON format
• No External Dependencies: Pure Elixir with no Phoenix or Ecto requirements

Installation

Add otzel to your list of dependencies in mix.exs:

def deps do
  [
    {:otzel, "~> 0.5.0"}
  ]
end

Quick Start

Creating Operations

# Create a document
doc = [Otzel.insert("Hello World")]

# Create a change that makes "World" bold
change = [Otzel.retain(6), Otzel.retain(5, %{"bold" => true})]

# Apply the change
new_doc = Otzel.compose(doc, change)

The Three Operations

Otzel uses three fundamental operations:

Insert

Adds new content at the current position:

# Insert plain text
Otzel.insert("Hello")

# Insert with formatting
Otzel.insert("Bold text", %{"bold" => true})

# Insert with multiple attributes
Otzel.insert("Styled", %{"bold" => true, "color" => "#ff0000"})

Retain

Keeps existing content, optionally modifying its attributes:

# Keep 5 characters unchanged
Otzel.retain(5)

# Keep 5 characters and make them bold
Otzel.retain(5, %{"bold" => true})

# Remove bold formatting (set to nil)
Otzel.retain(5, %{"bold" => nil})

Delete

Removes content at the current position:

# Delete 3 characters
Otzel.delete(3)

Core Operations

Compose

Combines two deltas into a single delta that has the same effect as applying them sequentially:

delta1 = [Otzel.insert("Hello")]
delta2 = [Otzel.retain(5), Otzel.insert(" World")]

# Result: [%Otzel.Op.Insert{content: "Hello World"}]
combined = Otzel.compose(delta1, delta2)

Transform

When two users make concurrent edits, transform adjusts one edit to account for the other:

# User A inserts "A" at position 0
delta_a = [Otzel.insert("A")]

# User B inserts "B" at position 0
delta_b = [Otzel.insert("B")]

# Transform B against A (B came second)
# Result keeps B's insert after A's
transformed_b = Otzel.transform(delta_a, delta_b, :right)

The priority parameter (:left or :right) determines which edit "wins" when both insert at the same position.

Invert

Creates a delta that undoes the effect of another delta:

doc = [Otzel.insert("Hello World")]
change = [Otzel.retain(6), Otzel.delete(5), Otzel.insert("Elixir")]

# Apply the change: "Hello Elixir"
new_doc = Otzel.compose(doc, change)

# Create the undo operation
undo = Otzel.invert(change, doc)

# Apply undo to get back to original
original = Otzel.compose(new_doc, undo)

Diff

Computes the delta needed to transform one document into another:

doc1 = [Otzel.insert("Hello")]
doc2 = [Otzel.insert("Hello World")]

# Result: [Otzel.retain(5), Otzel.insert(" World")]
change = Otzel.diff(doc1, doc2)

JSON Serialization

Otzel is compatible with the Quill Delta JSON format:

# Create a delta
delta = [
  Otzel.insert("Hello "),
  Otzel.insert("World", %{"bold" => true})
]

# Convert to JSON string
json_string = JSON.encode!(delta)
# "[{\"insert\":\"Hello \"},{\"insert\":\"World\",\"attributes\":{\"bold\":true}}]"

# Parse from JSON
parsed = json_string |> JSON.decode!() |> Otzel.from_json()

Working with Attributes

Attributes represent formatting applied to content:

# Multiple attributes
Otzel.insert("Fancy", %{
  "bold" => true,
  "italic" => true,
  "color" => "#ff0000",
  "background" => "#ffff00"
})

# Attribute changes in retain
# This adds bold and removes italic
Otzel.retain(5, %{"bold" => true, "italic" => nil})

Embedded Content

Otzel supports non-text content through the Otzel.Content protocol:

# The library includes Otzel.Content.Ot for nested OT content
# You can implement the protocol for custom embeds like images:

defmodule MyApp.ImageEmbed do
  use Otzel.Content, atomic: true

  defstruct [:url, :width, :height]

  # Required callbacks for OT operations
  def compose(_, _), do: raise "not implemented"
  def transform(_, _, _), do: raise "not implemented"
  def invert(_, _), do: raise "not implemented"
end

Checking Content Type

Use Otzel.Content.embed?/1 to check if content is an embedded type vs string-like:

string_content = %Otzel.Content.Iomemo{s: "hello", l: 5}
embed_content = %Otzel.Content.Ot{transform: [Otzel.insert("nested")]}

Otzel.Content.embed?(string_content)  # => false
Otzel.Content.embed?(embed_content)   # => true

JSON Deserialization with Custom Embeds

When deserializing JSON that contains embedded content, use the :embed_encoder option to convert JSON maps back to your embed structs. The encoder can be either an anonymous function or a {module, function} tuple:

# Option 1: Anonymous function (useful for simple cases)
encoder = fn
  %{"image" => url} -> %MyApp.ImageEmbed{url: url}
  %{"embed" => ops} -> %Otzel.Content.Ot{transform: Otzel.from_json(ops)}
  other -> other
end

json = [%{"insert" => %{"image" => "photo.jpg"}}]
Otzel.from_json(json, embed_encoder: encoder)

# Option 2: Module function tuple (useful for complex or reusable encoders)
defmodule MyApp.EmbedEncoder do
  def decode(%{"image" => url}) do
    %MyApp.ImageEmbed{url: url}
  end

  def decode(%{"embed" => ops}) when is_list(ops) do
    %Otzel.Content.Ot{transform: Otzel.from_json(ops)}
  end

  def decode(other), do: other  # Pass through unknown content
end

Otzel.from_json(json, embed_encoder: {MyApp.EmbedEncoder, :decode})

# Configure globally in config.exs (supports both formats)
config :otzel, :embed_encoder, {MyApp.EmbedEncoder, :decode}
# or
config :otzel, :embed_encoder, &MyApp.EmbedEncoder.decode/1

Error Handling

Otzel.ContentError is raised when there's a type mismatch between content types:

# This raises ContentError - can't invert an embedded retain against string content
delta = [Otzel.retain(%Otzel.Content.Ot{transform: [Otzel.insert("a")]})]
base = [Otzel.insert("a")]

Otzel.invert(delta, base)
# ** (Otzel.ContentError) cannot retain a string with embedded content

Architecture

Module Overview

• Otzel - Main module with all core OT operations
• Otzel.Op - Protocol for operations (Insert, Retain, Delete)
• Otzel.Op.Insert - Insert operation struct
• Otzel.Op.Retain - Retain operation struct
• Otzel.Op.Delete - Delete operation struct
• Otzel.Content - Protocol for content types
• Otzel.Content.Iomemo - Efficient IO-list based string representation
• Otzel.Content.Ot - Nested OT content for embeds
• Otzel.Attrs - Attribute manipulation utilities
• Otzel.ContentError - Exception for content type mismatches

String Representation

By default, Otzel uses Otzel.Content.Iomemo for string content, which stores strings as IO-lists with precomputed lengths. This provides efficient splitting and concatenation operations common in OT workloads.

You can configure a different string module:

# In config.exs
config :otzel, :string_module, String

# Or per-operation
Otzel.insert("Hello", nil, String)

OT Invariants

Otzel maintains the standard OT invariants:

1. Compose associativity: compose(compose(a, b), c) == compose(a, compose(b, c))

2. Transform convergence (TP1): For concurrent operations A and B:

   compose(A, transform(A, B, :right)) == compose(B, transform(B, A, :left))

3. Invert correctness: For document D and change C:

   compose(compose(D, C), invert(C, D)) == D

Performance

Benchmarks comparing Otzel against the Delta Elixir library.

High-Complexity (Fragmented Documents)

Randomized OT operations representing highly fragmented documents with many small operations.

Low-Complexity (Typical Editing)

Simple: Single ~10KB document with minimal changes

Typing: Sequential character-by-character edits

Detailed Results

See PERFORMANCE.md for full benchmark data across all string representations.

Test Environment: Linux, AMD Ryzen 7 7840U, 16 cores, Elixir 1.18.4, Erlang 28.1 with JIT

Why Otzel is Faster

1. IO-list string representation (Iomemo): Structural sharing during split/concatenate avoids copying
2. Optimized diff: Single-pass serialization with embed detection, skips reconstruction for text-only documents
3. Efficient iteration: Avoids intermediate allocations in compose/transform loops
4. Atoms over strings: Uses atoms for internal keys and tags, avoiding string comparisons

Understanding the Speedup Variation

The diff speedup varies dramatically: 1.3x for high-complexity vs 235x for simple documents. This reveals two different performance factors:

• High-complexity (fragmented): Many small strings amortize per-string overhead. The 1.3x speedup reflects the core diff algorithm efficiency.
• Low-complexity (large strings): Delta's overhead scales with string length (codepoint conversion, intermediate allocations). On a 10KB contiguous string, this overhead dominates—Delta takes ~1ms while Otzel takes ~4μs.

In other words, high-complexity benchmarks measure algorithmic efficiency, while low-complexity benchmarks expose string handling overhead.

Comparison with Other Libraries

Otzel implements the same Delta format as quill-delta.

Otzel's mixed content diff uses NULL character serialization with iterator-based reconstruction, following the quill-delta-enhanced approach.

When to Use Otzel

• High-throughput collaborative editing with many concurrent operations
• Complex documents with mixed text and embeds
• Nested OT structures requiring recursive diffing
• Memory-constrained environments where allocation efficiency matters

Testing

mix test

The test suite includes property-based tests that verify OT invariants across randomly generated operations.

License

MIT License. See LICENSE for details.

Acknowledgments

• Inspired by the Quill Delta format
• Based on operational transformation theory from OT FAQ