Grove.Tree.Version (Grove v0.1.1)

Tracks the current version state (frontier) of the event graph.

The frontier is the set of event IDs with no children - representing the "tips" of the DAG. This enables two key Eg-walker optimizations:

Critical Version Detection

When frontier.size == 1, we're in sequential editing mode. This is the "critical version" fast path where no OT/CRDT transformation is needed because all operations are causally ordered.

Causal Ordering

The frontier provides parent references for new events, establishing the happens-before relationship in the DAG. This enables:

Detecting concurrent operations (branching)
Merging branches (events with multiple parents)
Partial replay for branch switching

Example

# Sequential editing (critical version)
version = Version.new()
version = Version.advance(version, event1)  # frontier: {("r1", 1)}
version = Version.advance(version, event2)  # frontier: {("r1", 2)}
Version.is_critical?(version)  # => true

# Concurrent editing (branching)
# If replica r2 creates event2' with parent event1:
version = Version.advance(version, event2_prime)  # frontier: {("r1", 2), ("r2", 1)}
Version.is_critical?(version)  # => false

Summary

Types

t()

Functions

advance(version, event)

Advances the version by incorporating a new event.

branch_count(version)

Returns the number of concurrent branches in the version.

critical?(version)

Returns true if the version is at a critical point (frontier size <= 1).

get_parents(version)

Returns the current frontier as parent references for new events.

merge(version1, version2)

Merges two versions by taking the union of their frontiers.

new()

Creates a new empty version.

Types

t()

@type t() :: %Grove.Tree.Version{
  clock: non_neg_integer(),
  frontier: MapSet.t(Grove.Tree.Event.event_id())
}

Functions

advance(version, event)

@spec advance(t(), Grove.Tree.Event.t()) :: t()

Advances the version by incorporating a new event.

This updates the frontier by:

Removing the event's parents (they now have children)
Adding the event's ID (it's a new tip)

Examples

iex> version = Grove.Tree.Version.new()
iex> event = %Grove.Tree.Event{id: {"r1", 1}, parents: MapSet.new()}
iex> version = Grove.Tree.Version.advance(version, event)
iex> MapSet.member?(version.frontier, {"r1", 1})
true

branch_count(version)

@spec branch_count(t()) :: non_neg_integer()

Returns the number of concurrent branches in the version.

0: Empty version (no events yet)
1: Sequential editing (critical version)
2+: Concurrent branches that need merging

Examples

iex> version = Grove.Tree.Version.new()
iex> Grove.Tree.Version.branch_count(version)
0

iex> event = %Grove.Tree.Event{id: {"r1", 1}, parents: MapSet.new()}
iex> version = Grove.Tree.Version.advance(version, event)
iex> Grove.Tree.Version.branch_count(version)
1

critical?(version)

@spec critical?(t()) :: boolean()

Returns true if the version is at a critical point (frontier size <= 1).

A critical version means all replicas have converged to a single point, enabling the Eg-walker fast path where no transformation is needed.

Examples

iex> version = Grove.Tree.Version.new()
iex> Grove.Tree.Version.critical?(version)
true

iex> event = %Grove.Tree.Event{id: {"r1", 1}, parents: MapSet.new()}
iex> version = Grove.Tree.Version.advance(version, event)
iex> Grove.Tree.Version.critical?(version)
true

get_parents(version)

@spec get_parents(t()) :: MapSet.t(Grove.Tree.Event.event_id())

Returns the current frontier as parent references for new events.

Examples

iex> version = Grove.Tree.Version.new()
iex> event = %Grove.Tree.Event{id: {"r1", 1}, parents: MapSet.new()}
iex> version = Grove.Tree.Version.advance(version, event)
iex> parents = Grove.Tree.Version.get_parents(version)
iex> MapSet.member?(parents, {"r1", 1})
true

merge(version1, version2)

@spec merge(t(), t()) :: t()

Merges two versions by taking the union of their frontiers.

This is used when receiving events from remote replicas that may have diverged. The resulting frontier contains all tips from both versions.

Note: After merging, you typically need to apply any missing events to bring the versions into sync.

Examples

iex> v1 = %Grove.Tree.Version{frontier: MapSet.new([{"r1", 2}]), clock: 2}
iex> v2 = %Grove.Tree.Version{frontier: MapSet.new([{"r2", 1}]), clock: 1}
iex> merged = Grove.Tree.Version.merge(v1, v2)
iex> MapSet.size(merged.frontier)
2

new()

@spec new() :: t()

Creates a new empty version.

Examples

iex> version = Grove.Tree.Version.new()
iex> MapSet.size(version.frontier)
0
iex> version.clock
0