@spec ancestors(t(), String.t()) :: [String.t()]

Returns all ancestor node IDs from the given node to the root.

The list is ordered from immediate parent to root.

@spec apply_remote(t(), Grove.Tree.Event.t()) :: {:ok, t()} | {:duplicate, t()}

Applies a remote event with deduplication.

Returns {:ok, updated_tree} if applied, or {:duplicate, tree} if already seen.

This is the unified entry point for applying remote operations. It checks if the event has been seen before and skips duplicates.

Examples

event = %Event{id: {"replica_2", 5}, operation: {:put_node, "n1", node}, ...}
case Tree.apply_remote(tree, event) do
  {:ok, updated_tree} -> updated_tree
  {:duplicate, tree} -> tree  # Already seen
end

@spec apply_remote_move(t(), tuple()) :: t()

Applies a remote move operation, handling LWW conflict resolution.

This is used when receiving move operations from other replicas. The operation is skipped if:

• The node doesn't exist
• The node is deleted
• The move would create a cycle
• The operation's timestamp is older than the node's current parent_timestamp

This silent skipping is required for CRDT convergence.

Examples

tree = Tree.apply_remote_move(tree, {:move_node, "field_1", nil, "step_2", timestamp})

@spec batch(t(), (t() -> t()), keyword()) :: {t(), term()}

Executes multiple tree operations as an atomic batch.

Returns {updated_tree, compound_delta} where:

• updated_tree has all operations applied
• compound_delta contains all individual deltas for broadcast

The batch is tracked as a single undo operation and a single history entry.

Options

• :meta - Metadata map to attach to the batch operation (default: %{})

Example

{tree, delta} = Grove.Tree.batch(tree, fn t ->
  t
  |> Grove.Tree.put_node(Node.new("step_2", :step))
  |> Grove.Tree.put_node(Node.new("field_1", :text))
end)

# With metadata
{tree, delta} = Grove.Tree.batch(tree, fn t ->
  t |> Grove.Tree.put_node(node)
end, meta: %{user_id: "u1", reason: "import"})

# Use with Session.mutate/2
Session.mutate(pid, fn tree ->
  Grove.Tree.batch(tree, fn t ->
    t
    |> Grove.Tree.put_node(...)
    |> Grove.Tree.update_node(...)
  end)
end)

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

Returns true if there are operations that can be redone.

Examples

if Tree.can_redo?(tree) do
  {:ok, tree} = Tree.redo(tree)
end

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

Returns true if there are operations that can be undone.

Examples

if Tree.can_undo?(tree) do
  {:ok, tree} = Tree.undo(tree)
end

@spec children(t(), String.t()) :: [Grove.Node.t()]

Returns the children nodes of the given node.

@spec create_snapshot(t()) :: {:ok, Grove.Tree.Snapshot.t()} | {:error, :not_critical}

Creates a snapshot of the tree at its current state.

Returns {:ok, snapshot} if the tree is at a critical version, or {:error, :not_critical} if the frontier has multiple branches.

Examples

{:ok, snapshot} = Tree.create_snapshot(tree)

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

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

At a critical version, all replicas have converged and the Eg-walker fast-path can be used.

@spec ensure_index(t()) :: t()

Ensures the event index is built (lazy construction).

If the index is nil, builds it from history. If already built, returns tree unchanged.

@spec event_count(t()) :: non_neg_integer()

Returns the number of events since the tree was created.

This is used to determine when to create a snapshot.

@spec find_nodes(
  t(),
  keyword()
) :: [Grove.Node.t()]

Finds nodes matching the given criteria.

Options

• :type - Match nodes with this type (atom)
• :where - Match nodes where attrs contain these key-value pairs

Examples

# Find all dropdowns
Grove.Tree.find_nodes(tree, type: :dropdown)

# Find all required fields
Grove.Tree.find_nodes(tree, where: [required: true])

# Find required text fields
Grove.Tree.find_nodes(tree, type: :text, where: [required: true])

@spec from_snapshot(Grove.Tree.Snapshot.t(), String.t()) :: t()

Rebuilds a tree from a snapshot.

Examples

tree = Tree.from_snapshot(snapshot, "replica_1")

@spec generate_id(t()) :: {t(), String.t()}

Generates a new unique ID using the replica ID and clock.

Increments the clock and returns {new_tree, id}.

Example

{tree, id} = Grove.Tree.generate_id(tree)
# id => "replica_1_1"

@spec get_event(t(), Grove.Tree.Event.event_id()) :: Grove.Tree.Event.t() | nil

Gets an event by ID using the event index.

Returns nil if the event doesn't exist. Uses O(1) lookup via the persistent event_index.

@spec get_node(t(), String.t()) :: Grove.Node.t() | nil

Gets a node by ID.

Returns nil if the node doesn't exist.

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

Returns the operation history for this tree.

History entries are returned in chronological order (oldest first).

Options

• :since - Only include entries with timestamp >= this value
• :until - Only include entries with timestamp <= this value
• :node_id - Only include entries that affected this node
• :where - Filter by metadata, e.g., [user_id: "u1"]
• :limit - Maximum number of entries to return

Examples

Tree.history(tree)
Tree.history(tree, since: timestamp, limit: 10)
Tree.history(tree, node_id: "field_1")
Tree.history(tree, where: [user_id: "u1"])

@spec move_node(t(), String.t(), String.t() | nil, keyword()) ::
  t() | {:error, atom()}

Moves a node to a new parent.

This operation uses LWW (Last-Writer-Wins) semantics with HLC timestamps for conflict resolution when the same node is moved concurrently.

Returns {:error, reason} if the move is invalid:

• :node_not_found - The node doesn't exist
• :self_move - Attempting to move a node into itself
• :would_create_cycle - Moving the node would create a cycle in the tree
• :invalid_left_origin - The :after sibling doesn't exist or isn't a sibling
• :invalid_right_origin - The :before sibling doesn't exist or isn't a sibling
• :origins_conflict - The :after sibling comes after the :before sibling

Options

• :meta - Metadata map to attach to this operation (default: %{})
• :after - ID of sibling to insert after (for sibling ordering)
• :before - ID of sibling to insert before (for sibling ordering)
• :position - :first or :last for edge positions

Examples

tree = Tree.move_node(tree, "field_1", "step_2")
tree = Tree.move_node(tree, "field_1", "step_2", meta: %{user_id: "u1"})

# Move to root (nil parent)
tree = Tree.move_node(tree, "step_1", nil)

# Move with sibling positioning
tree = Tree.move_node(tree, "field_1", "step_2", after: "field_2")
tree = Tree.move_node(tree, "field_1", "step_2", before: "field_3")
tree = Tree.move_node(tree, "field_1", "step_2", position: :first)

@spec navigate_to_version(t(), Grove.Tree.Version.t()) :: t()

Navigates to a specific version by rebuilding tree state.

Returns a tree struct representing the state at the given version. This is a transient view - it does not modify history or pending_ops.

The returned tree has:

• nodes: Rebuilt state at the target version
• version: The target version
• history/pending_ops/etc: Unchanged from original

Examples

target_version = %Version{frontier: MapSet.new([{"r1", 5}]), clock: 5}
navigated_tree = Tree.navigate_to_version(tree, target_version)

@spec new(String.t()) :: t()

Creates a new empty tree for the given replica.

Example

tree = Grove.Tree.new("replica_1")

@spec node_ids(t()) :: [String.t()]

Returns a list of all node IDs in the tree.

@spec operation_meta(tuple()) :: map()

Extracts metadata from an operation tuple.

Returns an empty map if no metadata is present.

Examples

Tree.operation_meta({:put_node, "id", node})
# => %{}

Tree.operation_meta({:put_node, "id", node, %{user_id: "u1"}})
# => %{user_id: "u1"}

@spec parent(t(), String.t()) :: Grove.Node.t() | nil

Returns the parent node of the given node, or nil.

@spec path_to(t(), String.t()) :: [String.t()]

Returns the path from root to the given node (list of node IDs).

@spec prune_seen_events(t()) :: t()

Prunes seen_events when at a critical version.

At critical versions (frontier.size == 1), old event IDs can be safely pruned since all replicas have converged. This keeps memory bounded.

Examples

tree = Tree.prune_seen_events(tree)

@spec put_node(t(), Grove.Node.t(), keyword()) :: t()

Puts a node into the tree.

Tracks the operation in pending_ops for batch operations and broadcasting. Records the operation in history.

Options

• :meta - Metadata map to attach to this operation (default: %{})

Examples

Tree.put_node(tree, node)
Tree.put_node(tree, node, meta: %{user_id: "u1", user_name: "Alice"})

@spec redo(t()) :: {:ok, t()} | {:error, :empty_stack}

Redoes the last undone operation.

Returns {:ok, updated_tree} on success, or {:error, :empty_stack} if there are no operations to redo.

Redo works by re-applying the original operation. Note that new operations clear the redo stack, so redo is only available immediately after undo.

Examples

{:ok, tree} = Tree.redo(tree)

case Tree.redo(tree) do
  {:ok, tree} -> # operation redone
  {:error, :empty_stack} -> # nothing to redo
end

@spec reset_pending_ops(t()) :: t()

Clears pending operations after they've been broadcast.

@spec root(t()) :: Grove.Node.t() | nil

Returns the root node, or nil if tree is empty.

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

Returns true if a snapshot should be created for this tree.

A snapshot should be created when:

• The tree is at a critical version (frontier size <= 1)
• The number of events since the last snapshot exceeds the threshold

Examples

Tree.should_snapshot?(tree)  # => true/false

@spec siblings(t(), String.t()) :: [Grove.Node.t()]

Returns sibling nodes (nodes with the same parent, excluding the node itself).

Example

siblings = Grove.Tree.siblings(tree, "field_1")
# => [%Node{id: "field_2", ...}, %Node{id: "field_3", ...}]

@spec size(t()) :: non_neg_integer()

Returns the number of nodes in the tree.

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

Returns tree state at a specific event.

This is a convenience function that creates a version from the event and navigates to it.

Examples

event = List.first(tree.history)
past_tree = Tree.state_at_event(tree, event)

@spec undo(t()) :: {:ok, t()} | {:error, :empty_stack}

Undoes the last local operation.

Returns {:ok, updated_tree} on success, or {:error, :empty_stack} if there are no operations to undo.

Undo works by computing the inverse operation and applying it. This generates a new operation with a new timestamp, ensuring proper LWW conflict resolution with concurrent remote operations.

Examples

{:ok, tree} = Tree.undo(tree)

case Tree.undo(tree) do
  {:ok, tree} -> # operation undone
  {:error, :empty_stack} -> # nothing to undo
end

@spec unwrap_pending_ops(t()) :: [term()]

Extracts raw operations from pending_ops, stripping event IDs.

Pending ops are stored as {event_id, operation} tuples for deduplication. This helper extracts just the operations for code that needs raw ops.

Examples

raw_ops = Tree.unwrap_pending_ops(tree)
# => [{:put_node, "n1", node}, {:update_node, "n2", old, new}]

@spec update_node(t(), String.t(), (Grove.Node.t() -> Grove.Node.t()), keyword()) ::
  t()

Updates a node in the tree using the given function.

Returns the tree unchanged if the node doesn't exist. Tracks the operation in pending_ops for batch operations and broadcasting. Records the operation in history.

Options

• :meta - Metadata map to attach to this operation (default: %{})

Examples

Tree.update_node(tree, "node_1", fn node -> %{node | attrs: new_attrs} end)
Tree.update_node(tree, "node_1", update_fn, meta: %{reason: "typo fix"})