@spec ceiling_entry(Bedrock.DataPlane.CommitProxy.RoutingData.shard_tree(), binary()) ::
  {Bedrock.key(), {tag :: term(), start_key :: Bedrock.key()}} | :none

First entry with end_key strictly greater than key (end keys are exclusive bounds), or :none. The one ceiling-walk authority: mutation routing, key lookup, and the proxy's client-facing covering entry all resolve through it.

@spec get_log_indices(non_neg_integer(), pos_integer(), non_neg_integer()) :: [
  non_neg_integer()
]

Returns m log indices for shard tag x given n total logs.

Uses golden ratio stepping for uniform distribution. The result is deterministic for the same inputs.

Parameters

• x - Shard tag (non-negative integer)
• n - Total number of logs
• m - Replication factor (how many logs to return)

Examples

iex> ShardRouter.get_log_indices(0, 5, 2)
[4, 0]  # Two distinct indices in range [0, 5)

iex> ShardRouter.get_log_indices(0, 5, 0)
[]

@spec log_ids_for_tag(
  term(),
  %{required(non_neg_integer()) => Bedrock.DataPlane.Log.id()},
  non_neg_integer()
) :: [Bedrock.DataPlane.Log.id()]

The replica set for a shard tag: log ids resolved through log_map (index → log id over the epoch's sorted log ids — see log_map/1) via the golden-ratio walk. Non-integer tags are normalized by hashing, so both consumers agree on the walk's input.

This is the single site for shard→log placement. Commit-proxy mutation routing and the director's materializer pull-source seeds both resolve through it, so they cannot disagree.

@spec log_map([Bedrock.DataPlane.Log.id()]) :: %{
  required(non_neg_integer()) => Bedrock.DataPlane.Log.id()
}

The index map for an epoch's logs: index → log id over the sorted ids.

Both consumers of log_ids_for_tag/3 build their map here, so the sort and indexing cannot diverge between them.

@spec lookup_shard(Bedrock.DataPlane.CommitProxy.RoutingData.shard_tree(), binary()) ::
  non_neg_integer()

Looks up the shard tag for a key using ceiling search.

Shard ranges are [min, max) - start inclusive, end exclusive.

Parameters

• shards - shard map (end_key => {tag, start_key} gb_tree)
• key - The key to look up

Returns

The shard tag (non-negative integer) that owns the key.

Examples

# Shards: 0 covers ["", "m"), 1 covers ["m", "\xff")
iex> lookup_shard(shards, "apple")
0
iex> lookup_shard(shards, "m")
1  # "m" is the START of shard 1, not end of shard 0
iex> lookup_shard(shards, "zebra")
1

@spec lookup_shards_with_ranges(
  Bedrock.DataPlane.CommitProxy.RoutingData.shard_tree(),
  binary(),
  binary()
) :: [{non_neg_integer(), binary(), binary()}]

Returns shards overlapping a key range, with their boundaries.

Returns {tag, shard_start, shard_end} tuples to enable clamping range mutations to shard boundaries.

Parameters

• shards - shard map (end_key => {tag, start_key} gb_tree)
• start_key - Start of the range (inclusive)
• end_key - End of the range (exclusive)

Returns

List of {tag, shard_start, shard_end} tuples for all shards that overlap [start_key, end_key). Returns [] when the range lies entirely beyond shard coverage (start_key >= every shard's exclusive end_key).

Examples

# Shards: 0 = ["", "d"), 1 = ["d", "h"), 2 = ["h", "m"), 3 = ["m", "\xff")
iex> lookup_shards_with_ranges(shards, "a", "c")
[{0, "", "d"}]
iex> lookup_shards_with_ranges(shards, "c", "j")
[{0, "", "d"}, {1, "d", "h"}, {2, "h", "m"}]

@spec normalize_tag(term()) :: integer()

Normalizes a shard tag for the golden-ratio walk. Production tags are integers; anything else (test fixtures) hashes to one so the walk stays defined — and every consumer normalizes identically.