Grove.Tree.ChildOrder (Grove v0.2.0)

View Source

Deterministic child ordering using position-based conflict resolution.

Implements a Fugue-inspired ordering algorithm that uses left/right origins to establish order constraints, with HLC timestamps for tiebreaking.

Algorithm

  1. Build a constraint graph from position metadata (left/right origins)
  2. Topological sort to respect ordering constraints
  3. Stable sort by timestamp for deterministic tiebreaking
  4. Nodes without position metadata sort to the end, ordered by ID

Non-Interleaving Property

Consecutive insertions by the same replica stay grouped together:

# Replica A inserts [F1, F2, F3] after X
# Replica B inserts [G1, G2] after X (concurrently)
# Result: [F1, F2, F3, G1, G2] or [G1, G2, F1, F2, F3]
# NOT interleaved like [F1, G1, F2, G2, F3]

This is achieved by each element pointing to its predecessor, forming chains.

Summary

Functions

build_position(tree, parent_id, replica_id, opts)

Builds position metadata from options.

order_by_position(nodes)

Orders a list of sibling nodes by their position metadata.

ordered_children(tree, parent_id)

Returns the ordered list of child node IDs for a parent.

validate_position(tree, parent_id, opts)

Validates that position options refer to valid siblings.

Functions

build_position(tree, parent_id, replica_id, opts)

@spec build_position(Grove.Tree.t(), String.t() | nil, String.t(), keyword()) ::
  Grove.Node.position() | nil

Builds position metadata from options.

Options

  • :after - ID of sibling to insert after
  • :before - ID of sibling to insert before
  • :position - :first or :last for edge positions

Examples

iex> ChildOrder.build_position(tree, "parent", "replica_1", after: "sibling_1")
%{left_origin: "sibling_1", right_origin: nil, timestamp: %HLC{...}}

iex> ChildOrder.build_position(tree, "parent", "replica_1", position: :first)
%{left_origin: nil, right_origin: first_child_id, timestamp: %HLC{...}}

order_by_position(nodes)

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

Orders a list of sibling nodes by their position metadata.

Nodes with position metadata are ordered according to their left/right origins and timestamps. Nodes without position metadata are placed at the end, sorted by their ID for determinism.

ordered_children(tree, parent_id)

@spec ordered_children(Grove.Tree.t(), String.t()) :: [String.t()]

Returns the ordered list of child node IDs for a parent.

Uses position metadata when available, falling back to the order in the parent's children list for nodes without positions.

Examples

iex> ChildOrder.ordered_children(tree, "parent_1")
["child_1", "child_3", "child_2"]

validate_position(tree, parent_id, opts)

@spec validate_position(Grove.Tree.t(), String.t() | nil, keyword()) ::
  :ok
  | {:error, :invalid_left_origin | :invalid_right_origin | :origins_conflict}

Validates that position options refer to valid siblings.

Returns :ok if valid, or {:error, reason} if not.