A branching message tree used by Omni.Session to store conversation history.

Each node holds a message and an optional parent pointer, forming a tree where linear conversations are the common case and branches represent alternate replies or edits.

Active path and cursors

An active path acts as a cursor through the tree — push/3 always appends to the head of this path, and navigate/2 moves it to a different branch.

Both push/3 and navigate/2 record cursors that track which child was most recently selected at a given parent. push/3 sets a single cursor at the new node's immediate parent. navigate/2 sets cursors for every parent-child pair along the path from root to the target, so the branch that was just navigated to is fully pinned. extend/1 follows these cursors to walk from the current head to a leaf, reconstructing a full path after navigating to a mid-tree branch point.

Example

A fresh tree is empty. Push messages to build up an active path; node ids are auto-assigned starting at 1:

tree =
  %Tree{}
  |> Tree.push(%Message{role: :user, content: "..."})
  |> Tree.push(%Message{role: :assistant, content: "..."})
  |> Tree.push(%Message{role: :user, content: "..."})
  |> Tree.push(%Message{role: :assistant, content: "..."})

Tree.messages(tree)   #=> [user, assistant, user, assistant]
Tree.size(tree)       #=> 4

Navigate back to an earlier node, then push — this creates a branch:

{:ok, tree} = Tree.navigate(tree, 3)
tree = Tree.push(tree, %Message{role: :assistant, content: "..."})

Tree.size(tree)         #=> 5
Tree.children(tree, 3)  #=> [4, 5]   # two branches from node 3

Navigate between siblings to make either branch the live conversation:

{:ok, tree} = Tree.navigate(tree, 4)   # original branch is live
{:ok, tree} = Tree.navigate(tree, 5)   # switch to the new branch

When navigate/2 lands on an interior node, extend/1 walks down to a leaf, following cursors left by previous pushes and navigations:

{:ok, tree} = Tree.navigate(tree, 2)
tree = Tree.extend(tree)               # path extended to a leaf

Enumerable

Implements Enumerable, yielding tree nodes (maps with :id, :parent_id, :message, and :usage keys) along the active path in root-to-leaf order. Enum.count/1 returns the active path length.