@spec ancestors([Grove.Tree.Event.t()], event_id()) :: MapSet.t(event_id())

Returns all ancestors of an event (excluding the event itself).

Ancestors are all events that are reachable by following parent edges.

Examples

iex> ancestors = EventGraph.ancestors(events, {"r1", 5})
iex> MapSet.member?(ancestors, {"r1", 1})
true

@spec build_children_map([Grove.Tree.Event.t()]) :: children_map()

Builds a map from parent ID to list of child IDs for reverse traversal.

This enables efficient descendant queries by inverting the parent edges.

@spec build_index([Grove.Tree.Event.t()]) :: event_index()

Builds a map from event ID to Event for O(1) lookups.

Examples

iex> events = [event1, event2, event3]
iex> index = EventGraph.build_index(events)
iex> Map.get(index, {"replica_1", 1})
%Event{id: {"replica_1", 1}, ...}

@spec concurrent?([Grove.Tree.Event.t()], event_id(), event_id()) :: boolean()

Determines if two events are concurrent (neither is an ancestor of the other).

Two events are concurrent if they were created independently without knowledge of each other. This is determined by computing the vector clock for each event from its ancestry and checking if they are comparable.

Complexity

O(V) where V is the total number of ancestors to traverse.

Examples

iex> # Sequential events are not concurrent
iex> EventGraph.concurrent?(events, {"r1", 1}, {"r1", 2})
false

iex> # Events on different branches are concurrent
iex> EventGraph.concurrent?(events, {"r1", 2}, {"r2", 2})
true

iex> # Same event is not concurrent with itself
iex> EventGraph.concurrent?(events, {"r1", 1}, {"r1", 1})
false

@spec descendants([Grove.Tree.Event.t()], event_id()) :: MapSet.t(event_id())

Returns all descendants of an event (excluding the event itself).

Descendants are all events that are reachable by following child edges.

Examples

iex> descendants = EventGraph.descendants(events, {"r1", 1})
iex> MapSet.member?(descendants, {"r1", 5})
true

@spec diff([Grove.Tree.Event.t()], Grove.Tree.Version.t(), Grove.Tree.Version.t()) ::
  %{
    retreat: [Grove.Tree.Event.t()],
    advance: [Grove.Tree.Event.t()]
  }

Computes the difference between two versions.

Returns events that need to be retreated (undone) and advanced (applied) to move from from_version to to_version.

Retreat events are in reverse topological order (children first, for safe undo). Advance events are in topological order (parents first, for safe apply).

Examples

iex> # Moving forward in linear history
iex> diff = EventGraph.diff(events, v1, v2)
iex> diff.retreat
[]
iex> length(diff.advance)
3

iex> # Switching branches
iex> diff = EventGraph.diff(events, branch_a_version, branch_b_version)
iex> length(diff.retreat)
2
iex> length(diff.advance)
1

@spec events_between(
  [Grove.Tree.Event.t()],
  Grove.Tree.Version.t(),
  Grove.Tree.Version.t()
) ::
  {:ok, [Grove.Tree.Event.t()]} | {:error, :not_linear}

Returns events between two versions for linear forward movement.

This is a convenience function that returns only advance events when moving forward in a linear history. Returns an error if the movement requires retreating (branch switch).

Returns

• {:ok, events} - Events to advance in topological order
• {:error, :not_linear} - Movement requires retreat (not a linear forward)

Examples

iex> # Moving forward in linear history
iex> {:ok, events} = EventGraph.events_between(history, v1, v2)
iex> length(events)
3

iex> # Branch switch requires retreat
iex> EventGraph.events_between(history, branch_a, branch_b)
{:error, :not_linear}

@spec events_since(
  [Grove.Tree.Event.t()],
  Grove.Tree.Version.t() | MapSet.t(event_id())
) ::
  {:ok, [Grove.Tree.Event.t()]} | {:error, :version_pruned}

Returns all events that occurred after the given version.

The version's frontier identifies the "tips" of the DAG at that point in time. This function returns all events that are descendants of the frontier.

Fast Path

When the frontier has exactly one event (critical version / linear history), this uses a simple list traversal instead of graph search.

Returns

• {:ok, events} - List of events since the version
• {:error, :version_pruned} - Frontier events are no longer in history

Examples

iex> # Get all events since a saved version
iex> {:ok, new_events} = EventGraph.events_since(tree.history, saved_version)

iex> # Empty frontier means return all events
iex> {:ok, all} = EventGraph.events_since(events, %Version{frontier: MapSet.new()})

@spec find_common_ancestor([Grove.Tree.Event.t()], event_id(), event_id()) ::
  {:ok, event_id()} | {:error, :no_common_ancestor}

Finds the most recent common ancestor of two events.

The common ancestor is the latest event that is an ancestor of both given events. This is useful for finding the point where two branches diverged.

Returns

• {:ok, event_id} - The ID of the common ancestor
• {:error, :no_common_ancestor} - Events have no common ancestor (e.g., different roots)

Examples

iex> # Same event is its own ancestor
iex> EventGraph.find_common_ancestor(events, {"r1", 1}, {"r1", 1})
{:ok, {"r1", 1}}

iex> # Find where two branches diverged
iex> EventGraph.find_common_ancestor(events, {"r1", 5}, {"r2", 3})
{:ok, {"r1", 2}}

@spec find_last_critical([Grove.Tree.Event.t()]) :: Grove.Tree.Event.t() | nil

Finds the last event where the version was critical (single frontier).

This is useful for replay optimization - we can skip events before the last critical point since state is known to be consistent.

Returns the most recent event that maintains critical version status, or nil if no such event exists.

Examples

iex> # Linear history - all events are critical
iex> event = EventGraph.find_last_critical(events)
iex> event.id
{"r1", 5}

iex> # After branching - finds last critical before branch
iex> event = EventGraph.find_last_critical(branched_events)
iex> event.id
{"r1", 2}

@spec topological_sort(
  [Grove.Tree.Event.t()],
  keyword()
) :: [Grove.Tree.Event.t()]

Sorts events in topological (causal) order using Kahn's algorithm.

Returns events ordered such that all parents appear before their children. This is the order in which events should be replayed to reconstruct state.

Options

• :assume_linear - If true, assumes history is linear and just reverses the list. Use when Grove.Tree.Version.critical?/1 is true for better performance.

Complexity

• O(V + E) for general case using Kahn's algorithm
• O(n) when :assume_linear is true

Examples

iex> events = Tree.history(tree)
iex> sorted = EventGraph.topological_sort(events)
iex> # First event has no parents, last event is most recent

# Fast path for sequential history
iex> sorted = EventGraph.topological_sort(events, assume_linear: Version.critical?(tree.version))