-module(lattice_sequence@sequence). -compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]). -define(FILEPATH, "src/lattice_sequence/sequence.gleam"). -export([new/1, try_insert_many_with_delta/3, try_insert_with_delta/3, insert/3, insert_with_delta/3, insert_many/3, insert_many_with_delta/3, try_delete_with_delta/2, delete/2, delete_with_delta/2, try_move_with_delta/3, move/3, move_with_delta/3, start_anchor/0, end_anchor/0, try_anchor_at/3, anchor_at/3, try_resolve/2, resolve/2, anchor_to_json/1, anchor_from_json/1, values/1, length/1, frontier/1, forwarding_size/1, remove_forwardings/2, merge/2, compact/2, translate_origins/2, to_json/2, from_json/2]). -export_type([item_id/0, op_id/0, move/0, item/1, segment/1, element/1, forwarding/0, forwarding_map/0, sequence/1, insert_error/0, delete_error/0, move_error/0, translate_error/0, bias/0, anchor/0, anchor_error/0, move_target/0, classified/1, stability/0, scan_entry/0, scan_step/0]). -if(?OTP_RELEASE >= 27). -define(MODULEDOC(Str), -moduledoc(Str)). -define(DOC(Str), -doc(Str)). -else. -define(MODULEDOC(Str), -compile([])). -define(DOC(Str), -compile([])). -endif. ?MODULEDOC( " A generic sequence CRDT using stable item IDs and YATA-style origins.\n" "\n" " Each live item is stored with a stable internal ID plus left and right\n" " origins for deterministic ordering. Deletes are represented as tombstones\n" " that record the delete's op ID; `values` returns only non-deleted items.\n" "\n" " The public editing API exposes index-based insert, delete, and move\n" " operations while resolving stable item IDs internally, so callers do not\n" " need to construct or manage item identifiers. Moves preserve item identity\n" " and converge with single-winner semantics for concurrent moves of the same\n" " item.\n" "\n" " ## Compaction\n" "\n" " Long-lived sequences never shrink on their own: every delete leaves a\n" " tombstone and every item carries origins. `compact` takes a stability\n" " frontier — a `VersionVector` meaning \"everything causally at or below\n" " this is stable; no in-flight or future op references it\" — and rewrites\n" " the stable region: stable tombstones are dropped, runs of adjacent stable\n" " items from the same replica with sequential counters are merged into\n" " compact blocks, and origins of stable items are discarded. Items above\n" " the frontier keep their full YATA representation.\n" "\n" " Every dropped ID gets a forwarding entry pointing at its retained\n" " neighbors, so anchors and rebased operations that still hold the ID can\n" " resolve to the gap it left behind. The forwarding map and the applied\n" " frontier travel with the state. Deriving a correct frontier is the\n" " host's job (e.g. from a global sequencer's acknowledgement floor); the\n" " frontier must be a causal cut over the ops applied to the sequence.\n" "\n" " ## Example\n" "\n" " ```gleam\n" " import lattice_core/replica_id\n" " import lattice_sequence/sequence\n" "\n" " let list =\n" " sequence.new(replica_id.new(\"node-a\"))\n" " |> sequence.insert(0, \"hello\")\n" " |> sequence.insert(1, \"world\")\n" " |> sequence.move(0, 1)\n" "\n" " sequence.values(list) // -> [\"world\", \"hello\"]\n" " ```\n" ). -opaque item_id() :: {item_id, lattice_core@replica_id:replica_id(), integer()}. -type op_id() :: {op_id, lattice_core@replica_id:replica_id(), integer()}. -type move() :: {move, op_id(), gleam@option:option(item_id()), gleam@option:option(item_id())}. -type item(DTH) :: {item, item_id(), gleam@option:option(item_id()), gleam@option:option(item_id()), DTH, gleam@option:option(op_id()), gleam@option:option(move())}. -type segment(DTI) :: {block, item_id(), list(DTI)} | {live, item(DTI)}. -type element(DTJ) :: {stable, item_id(), DTJ} | {live_el, item(DTJ)}. -type forwarding() :: {forwarding, gleam@option:option(item_id()), gleam@option:option(item_id())}. -opaque forwarding_map() :: {forwarding_map, gleam@dict:dict(item_id(), forwarding())}. -opaque sequence(DTK) :: {sequence, lattice_core@replica_id:replica_id(), integer(), list(segment(DTK)), gleam@dict:dict(item_id(), forwarding()), lattice_core@version_vector:version_vector()}. -type insert_error() :: {index_out_of_bounds, integer(), integer()}. -type delete_error() :: {delete_index_out_of_bounds, integer(), integer()}. -type move_error() :: {move_from_index_out_of_bounds, integer(), integer()} | {move_to_index_out_of_bounds, integer(), integer()}. -type translate_error() :: unknown_origin_target. -type bias() :: before | 'after'. -opaque anchor() :: start | 'end' | {at_item, item_id(), bias()}. -type anchor_error() :: {anchor_index_out_of_bounds, integer(), integer()} | unknown_anchor_target. -type move_target() :: {before_element, item_id()} | {after_gap, gleam@option:option(item_id())} | at_end. -type classified(DTL) :: {retained, element(DTL)} | {dropped, item_id()}. -type stability() :: drop_tombstone | to_stable | keep_live. -type scan_entry() :: {scan_entry, item_id(), gleam@option:option(item_id()), gleam@option:option(item_id()), boolean()}. -type scan_step() :: stop_scan | take_as_left | advance_past. -file("src/lattice_sequence/sequence.gleam", 181). ?DOC(" Create an empty sequence for a replica.\n"). -spec new(lattice_core@replica_id:replica_id()) -> sequence(any()). new(Replica_id) -> {sequence, Replica_id, 0, [], maps:new(), lattice_core@version_vector:new()}. -file("src/lattice_sequence/sequence.gleam", 1813). -spec flush_run( gleam@option:option({item_id(), list(EED), item_id()}), list(segment(EED)) ) -> list(segment(EED)). flush_run(Run, Acc) -> case Run of none -> Acc; {some, {First, Values_rev, _}} -> [{block, First, lists:reverse(Values_rev)} | Acc] end. -file("src/lattice_sequence/sequence.gleam", 1826). -spec follows(item_id(), item_id()) -> boolean(). follows(Last, Next) -> {item_id, Last_rid, Last_counter} = Last, {item_id, Next_rid, Next_counter} = Next, (Last_rid =:= Next_rid) andalso (Next_counter =:= (Last_counter + 1)). -file("src/lattice_sequence/sequence.gleam", 1782). -spec chunk_elements( list(element(EDU)), gleam@option:option({item_id(), list(EDU), item_id()}), list(segment(EDU)) ) -> list(segment(EDU)). chunk_elements(Elements, Run, Acc) -> case Elements of [] -> flush_run(Run, Acc); [{live_el, Item} | Rest] -> chunk_elements(Rest, none, [{live, Item} | flush_run(Run, Acc)]); [{stable, Id, Value} | Rest@1] -> case Run of {some, {First, Values_rev, Last}} -> case follows(Last, Id) of true -> chunk_elements( Rest@1, {some, {First, [Value | Values_rev], Id}}, Acc ); false -> chunk_elements( Rest@1, {some, {Id, [Value], Id}}, flush_run(Run, Acc) ) end; none -> chunk_elements(Rest@1, {some, {Id, [Value], Id}}, Acc) end end. -file("src/lattice_sequence/sequence.gleam", 1777). -spec elements_to_segments(list(element(EDP))) -> list(segment(EDP)). elements_to_segments(Elements) -> _pipe = chunk_elements(Elements, none, []), lists:reverse(_pipe). -file("src/lattice_sequence/sequence.gleam", 1832). -spec element_id(element(any())) -> item_id(). element_id(El) -> case El of {stable, Id, _} -> Id; {live_el, Item} -> erlang:element(2, Item) end. -file("src/lattice_sequence/sequence.gleam", 1926). -spec insert_element_after_id(list(element(EFQ)), item_id(), element(EFQ)) -> list(element(EFQ)). insert_element_after_id(Elements, Left, El) -> case Elements of [] -> [El]; [First | Rest] -> case element_id(First) =:= Left of true -> [First, El | Rest]; false -> [First | insert_element_after_id(Rest, Left, El)] end end. -file("src/lattice_sequence/sequence.gleam", 1141). -spec splice_into_gap( list(element(DZR)), {ok, item_id()} | {error, nil}, gleam@option:option(item_id()), element(DZR) ) -> list(element(DZR)). splice_into_gap(Elements, Previous_in_gap, Anchor, El) -> case {Previous_in_gap, Anchor} of {{ok, Previous}, _} -> insert_element_after_id(Elements, Previous, El); {{error, nil}, none} -> [El | Elements]; {{error, nil}, {some, Left_id}} -> insert_element_after_id(Elements, Left_id, El) end. -file("src/lattice_sequence/sequence.gleam", 1911). -spec insert_element_before_id(list(element(EFK)), item_id(), element(EFK)) -> list(element(EFK)). insert_element_before_id(Elements, Right, El) -> case Elements of [] -> [El]; [First | Rest] -> case element_id(First) =:= Right of true -> [El, First | Rest]; false -> [First | insert_element_before_id(Rest, Right, El)] end end. -file("src/lattice_sequence/sequence.gleam", 1941). -spec contains_element_id(list(element(any())), item_id()) -> boolean(). contains_element_id(Elements, Id) -> gleam@list:any(Elements, fun(El) -> element_id(El) =:= Id end). -file("src/lattice_sequence/sequence.gleam", 2573). -spec chase_right( gleam@option:option(item_id()), gleam@dict:dict(item_id(), forwarding()), integer() ) -> gleam@option:option(item_id()). chase_right(Target, Entries, Fuel) -> case {Target, Fuel =< 0} of {none, _} -> none; {_, true} -> Target; {{some, Id}, false} -> case gleam_stdlib:map_get(Entries, Id) of {ok, {forwarding, _, Right}} -> chase_right(Right, Entries, Fuel - 1); {error, nil} -> Target end end. -file("src/lattice_sequence/sequence.gleam", 2557). -spec chase_left( gleam@option:option(item_id()), gleam@dict:dict(item_id(), forwarding()), integer() ) -> gleam@option:option(item_id()). chase_left(Target, Entries, Fuel) -> case {Target, Fuel =< 0} of {none, _} -> none; {_, true} -> Target; {{some, Id}, false} -> case gleam_stdlib:map_get(Entries, Id) of {ok, {forwarding, Left, _}} -> chase_left(Left, Entries, Fuel - 1); {error, nil} -> Target end end. -file("src/lattice_sequence/sequence.gleam", 1154). -spec resolve_move_target( list(element(any())), gleam@option:option(item_id()), gleam@option:option(item_id()), gleam@dict:dict(item_id(), forwarding()), gleam@dict:dict(item_id(), nil) ) -> move_target(). resolve_move_target(Elements, Move_left, Move_right, Forwardings, Mover_ids) -> Fuel = maps:size(Forwardings) + 1, Left_gap = case chase_left(Move_left, Forwardings, Fuel) of none -> {after_gap, none}; {some, Left_id} -> case contains_element_id(Elements, Left_id) of true -> {after_gap, {some, Left_id}}; false -> at_end end end, case Move_right of none -> Left_gap; {some, Raw_right} -> case contains_element_id(Elements, Raw_right) of true -> {before_element, Raw_right}; false -> case chase_right(Move_right, Forwardings, Fuel) of {some, Right_id} -> case not gleam@dict:has_key(Mover_ids, Right_id) andalso contains_element_id(Elements, Right_id) of true -> {before_element, Right_id}; false -> Left_gap end; none -> at_end end end end. -file("src/lattice_sequence/sequence.gleam", 1956). -spec remove_element_by_id(list(element(EGF)), item_id()) -> list(element(EGF)). remove_element_by_id(Elements, Id) -> case Elements of [] -> []; [El | Rest] -> case element_id(El) =:= Id of true -> Rest; false -> [El | remove_element_by_id(Rest, Id)] end end. -file("src/lattice_sequence/sequence.gleam", 2397). -spec compare_item_ids(item_id(), item_id()) -> gleam@order:order(). compare_item_ids(A, B) -> {item_id, A_replica, A_counter} = A, {item_id, B_replica, B_counter} = B, case lattice_core@replica_id:compare(A_replica, B_replica) of eq -> gleam@int:compare(A_counter, B_counter); Other -> Other end. -file("src/lattice_sequence/sequence.gleam", 2497). -spec compare_op_ids(op_id(), op_id()) -> gleam@order:order(). compare_op_ids(A, B) -> {op_id, A_replica, A_counter} = A, {op_id, B_replica, B_counter} = B, case gleam@int:compare(A_counter, B_counter) of eq -> lattice_core@replica_id:compare(A_replica, B_replica); Other -> Other end. -file("src/lattice_sequence/sequence.gleam", 2491). -spec compare_moves(move(), move()) -> gleam@order:order(). compare_moves(A, B) -> {move, A_op_id, _, _} = A, {move, B_op_id, _, _} = B, compare_op_ids(A_op_id, B_op_id). -file("src/lattice_sequence/sequence.gleam", 2384). -spec compare_item_moves(item(EKJ), item(EKJ)) -> gleam@order:order(). compare_item_moves(A, B) -> case {erlang:element(7, A), erlang:element(7, B)} of {{some, A_move}, {some, B_move}} -> case compare_moves(A_move, B_move) of eq -> compare_item_ids(erlang:element(2, A), erlang:element(2, B)); Other -> Other end; {{some, _}, none} -> gt; {none, {some, _}} -> lt; {none, none} -> compare_item_ids(erlang:element(2, A), erlang:element(2, B)) end. -file("src/lattice_sequence/sequence.gleam", 2380). -spec has_move(item(any())) -> boolean(). has_move(Item) -> gleam@option:is_some(erlang:element(7, Item)). -file("src/lattice_sequence/sequence.gleam", 2089). -spec live_items_of(list(element(EHN))) -> list(item(EHN)). live_items_of(Elements) -> gleam@list:filter_map(Elements, fun(El) -> case El of {live_el, Item} -> {ok, Item}; {stable, _, _} -> {error, nil} end end). -file("src/lattice_sequence/sequence.gleam", 1089). ?DOC( " Re-place every moved item from a canonical base: strip all moved items\n" " first, then apply the moves in op order. Both merge directions therefore\n" " start from the same non-moved skeleton and converge, regardless of which\n" " side had already applied which move. Moves landing in the same gap stack\n" " left-to-right in op order, matching how they stack when the gap's right\n" " boundary still exists.\n" ). -spec apply_moves(list(element(DZK)), gleam@dict:dict(item_id(), forwarding())) -> list(element(DZK)). apply_moves(Elements, Forwardings) -> Movers = begin _pipe = Elements, _pipe@1 = live_items_of(_pipe), _pipe@2 = gleam@list:filter(_pipe@1, fun has_move/1), gleam@list:sort(_pipe@2, fun compare_item_moves/2) end, Stripped = gleam@list:fold( Movers, Elements, fun(Current, Item) -> remove_element_by_id(Current, erlang:element(2, Item)) end ), Mover_ids = gleam@list:fold( Movers, maps:new(), fun(Acc, Item@1) -> gleam@dict:insert(Acc, erlang:element(2, Item@1), nil) end ), {Result, _} = gleam@list:fold( Movers, {Stripped, maps:new()}, fun(Acc@1, Item@2) -> {Current@1, Last_in_gap} = Acc@1, case erlang:element(7, Item@2) of none -> Acc@1; {some, {move, _, Move_left, Move_right}} -> case resolve_move_target( Current@1, Move_left, Move_right, Forwardings, Mover_ids ) of {before_element, Right_id} -> {insert_element_before_id( Current@1, Right_id, {live_el, Item@2} ), Last_in_gap}; at_end -> {lists:append(Current@1, [{live_el, Item@2}]), Last_in_gap}; {after_gap, Anchor} -> {splice_into_gap( Current@1, gleam_stdlib:map_get(Last_in_gap, Anchor), Anchor, {live_el, Item@2} ), gleam@dict:insert( Last_in_gap, Anchor, erlang:element(2, Item@2) )} end end end ), Result. -file("src/lattice_sequence/sequence.gleam", 2365). -spec insert_element_at(list(element(EKB)), integer(), element(EKB)) -> list(element(EKB)). insert_element_at(Elements, Index, El) -> case Index =< 0 of true -> [El | Elements]; false -> case Elements of [] -> [El]; [First | Rest] -> [First | insert_element_at(Rest, Index - 1, El)] end end. -file("src/lattice_sequence/sequence.gleam", 2338). -spec replica_of(item_id()) -> lattice_core@replica_id:replica_id(). replica_of(Id) -> {item_id, Rid, _} = Id, Rid. -file("src/lattice_sequence/sequence.gleam", 2304). -spec scan_step( scan_entry(), gleam@option:option(item_id()), gleam@option:option(item_id()), lattice_core@replica_id:replica_id(), gleam@dict:dict(item_id(), nil), gleam@dict:dict(item_id(), nil) ) -> scan_step(). scan_step( Entry, Item_left, Item_right, Item_replica, Before_origin, Conflicting ) -> case erlang:element(3, Entry) =:= Item_left of true -> case lattice_core@replica_id:compare( replica_of(erlang:element(2, Entry)), Item_replica ) of lt -> take_as_left; _ -> case erlang:element(4, Entry) =:= Item_right of true -> stop_scan; false -> advance_past end end; false -> case erlang:element(3, Entry) of none -> stop_scan; {some, Entry_left} -> case {gleam@dict:has_key(Before_origin, Entry_left), gleam@dict:has_key(Conflicting, Entry_left)} of {true, false} -> take_as_left; {true, true} -> advance_past; {false, _} -> stop_scan end end end. -file("src/lattice_sequence/sequence.gleam", 2238). -spec yata_scan( list(scan_entry()), gleam@option:option(item_id()), gleam@option:option(item_id()), lattice_core@replica_id:replica_id(), integer(), integer(), gleam@dict:dict(item_id(), nil), gleam@dict:dict(item_id(), nil) ) -> integer(). yata_scan( Window, Item_left, Item_right, Item_replica, Position, Dest, Before_origin, Conflicting ) -> case Window of [] -> Dest; [Entry | Rest] -> case erlang:element(5, Entry) of true -> Dest; false -> Before_origin@1 = gleam@dict:insert( Before_origin, erlang:element(2, Entry), nil ), Conflicting@1 = gleam@dict:insert( Conflicting, erlang:element(2, Entry), nil ), case scan_step( Entry, Item_left, Item_right, Item_replica, Before_origin@1, Conflicting@1 ) of stop_scan -> Dest; take_as_left -> yata_scan( Rest, Item_left, Item_right, Item_replica, Position + 1, Position + 1, Before_origin@1, maps:new() ); advance_past -> yata_scan( Rest, Item_left, Item_right, Item_replica, Position + 1, Dest, Before_origin@1, Conflicting@1 ) end end end. -file("src/lattice_sequence/sequence.gleam", 2204). -spec scan_entry( element(any()), gleam@dict:dict(item_id(), forwarding()), integer() ) -> scan_entry(). scan_entry(El, Forwardings, Fuel) -> case El of {stable, Id, _} -> {scan_entry, Id, none, none, true}; {live_el, Other} -> {scan_entry, erlang:element(2, Other), chase_left(erlang:element(3, Other), Forwardings, Fuel), erlang:element(4, Other), false} end. -file("src/lattice_sequence/sequence.gleam", 2350). -spec index_of_element_loop(list(element(any())), item_id(), integer()) -> {ok, integer()} | {error, nil}. index_of_element_loop(Elements, Id, Current) -> case Elements of [] -> {error, nil}; [El | Rest] -> case element_id(El) =:= Id of true -> {ok, Current}; false -> index_of_element_loop(Rest, Id, Current + 1) end end. -file("src/lattice_sequence/sequence.gleam", 2343). -spec index_of_element(list(element(any())), item_id()) -> {ok, integer()} | {error, nil}. index_of_element(Elements, Id) -> index_of_element_loop(Elements, Id, 0). -file("src/lattice_sequence/sequence.gleam", 2224). ?DOC( " Degrade origins that reference IDs this state has never seen (or whose\n" " forwardings expired) to the document boundary, mirroring how unmerged\n" " origins have always been treated.\n" ). -spec resolve_origin(gleam@option:option(item_id()), list(element(any()))) -> gleam@option:option(item_id()). resolve_origin(Origin, Elements) -> case Origin of none -> none; {some, Id} -> case contains_element_id(Elements, Id) of true -> {some, Id}; false -> none end end. -file("src/lattice_sequence/sequence.gleam", 2138). ?DOC( " Place a new item into the element order using its origins.\n" "\n" " Follows the YATA/Yjs `integrate` algorithm: the item lands between its\n" " left and right origins, and the scan over the conflict window decides its\n" " position among concurrently inserted items. For causally valid ops the\n" " window never contains a stable (origin-stripped) element — those were\n" " visible when the op was created, so they cannot sit strictly between its\n" " visible-adjacent origins; a stale op that does hit one degrades by\n" " stopping the scan there.\n" ). -spec integrate_element( list(element(EIN)), item(EIN), gleam@dict:dict(item_id(), forwarding()) ) -> list(element(EIN)). integrate_element(Elements, Item, Forwardings) -> Fuel = maps:size(Forwardings) + 1, Item_left = chase_left(erlang:element(3, Item), Forwardings, Fuel), Item_right = erlang:element(4, Item), Left = resolve_origin(Item_left, Elements), Right = resolve_origin( chase_right(erlang:element(4, Item), Forwardings, Fuel), Elements ), Left_pos = case Left of none -> -1; {some, Id} -> case index_of_element(Elements, Id) of {ok, Pos} -> Pos; {error, nil} -> -1 end end, Total = erlang:length(Elements), Right_pos = case Right of none -> Total; {some, Id@1} -> case index_of_element(Elements, Id@1) of {ok, Pos@1} -> Pos@1; {error, nil} -> Total end end, Window = begin _pipe = Elements, _pipe@1 = gleam@list:drop(_pipe, Left_pos + 1), _pipe@2 = gleam@list:take(_pipe@1, (Right_pos - Left_pos) - 1), gleam@list:map( _pipe@2, fun(_capture) -> scan_entry(_capture, Forwardings, Fuel) end ) end, Offset = yata_scan( Window, Item_left, Item_right, replica_of(erlang:element(2, Item)), 0, 0, maps:new(), maps:new() ), insert_element_at(Elements, (Left_pos + 1) + Offset, {live_el, Item}). -file("src/lattice_sequence/sequence.gleam", 1197). -spec compare_lamport(item(EAJ), item(EAJ)) -> gleam@order:order(). compare_lamport(X, Y) -> {item_id, X_rid, X_counter} = erlang:element(2, X), {item_id, Y_rid, Y_counter} = erlang:element(2, Y), case gleam@int:compare(X_counter, Y_counter) of eq -> lattice_core@replica_id:compare(X_rid, Y_rid); Other -> Other end. -file("src/lattice_sequence/sequence.gleam", 2507). -spec frontier_covers(lattice_core@version_vector:version_vector(), item_id()) -> boolean(). frontier_covers(Frontier, Id) -> {item_id, Rid, Counter} = Id, lattice_core@version_vector:get(Frontier, Rid) >= Counter. -file("src/lattice_sequence/sequence.gleam", 1013). ?DOC( " The canonical pre-move order: pinned covered elements in list order with\n" " everything else integrated in Lamport order.\n" "\n" " A covered element that carries a still-volatile move record is NOT\n" " pinned: its stored position reflects whichever moves this replica has\n" " already applied, which differs between replicas. It always carries its\n" " origins, so it re-integrates at its settled base position instead (its\n" " Lamport position sorts it before every volatile item automatically); the\n" " move overlay then re-places it.\n" ). -spec rebuild_base( list(element(DZA)), gleam@dict:dict(item_id(), forwarding()), lattice_core@version_vector:version_vector() ) -> list(element(DZA)). rebuild_base(Elements, Forwardings, Frontier) -> Pinned = gleam@list:filter(Elements, fun(El) -> case El of {stable, _, _} -> true; {live_el, Item} -> frontier_covers(Frontier, erlang:element(2, Item)) andalso (erlang:element( 7, Item ) =:= none) end end), _pipe = Elements, _pipe@1 = live_items_of(_pipe), _pipe@2 = gleam@list:filter( _pipe@1, fun(Item@1) -> not frontier_covers(Frontier, erlang:element(2, Item@1)) orelse (erlang:element( 7, Item@1 ) /= none) end ), _pipe@3 = gleam@list:sort(_pipe@2, fun compare_lamport/2), gleam@list:fold( _pipe@3, Pinned, fun(Current, Item@2) -> integrate_element(Current, Item@2, Forwardings) end ). -file("src/lattice_sequence/sequence.gleam", 995). ?DOC( " Deterministically rebuild the element order.\n" "\n" " Everything at or below the frontier — stable elements and old live items\n" " alike — is pinned at its stored position: those positions converged on\n" " every replica before the frontier passed them, so the pinned skeleton is\n" " identical everywhere. Items above the frontier are integrated YATA-style\n" " one at a time in Lamport order (a canonical total order), which makes\n" " the result a pure function of the element set; finally moves are applied\n" " last-writer-wins. Every construction path (local edits and both merge\n" " directions) goes through this, so convergence holds by construction.\n" "\n" " Because ops record canonical-adjacent origins, a volatile item's\n" " conflict window can only ever contain other volatile items — never a\n" " pinned element — so integration never needs the origins compaction\n" " stripped.\n" ). -spec rebuild( list(element(DYT)), gleam@dict:dict(item_id(), forwarding()), lattice_core@version_vector:version_vector() ) -> list(element(DYT)). rebuild(Elements, Forwardings, Frontier) -> _pipe = rebuild_base(Elements, Forwardings, Frontier), apply_moves(_pipe, Forwardings). -file("src/lattice_sequence/sequence.gleam", 390). -spec insert_run_after_id(list(element(DVF)), item_id(), list(element(DVF))) -> list(element(DVF)). insert_run_after_id(Elements, After, Run) -> case Elements of [] -> Run; [First | Rest] -> case element_id(First) =:= After of true -> [First | lists:append(Run, Rest)]; false -> [First | insert_run_after_id(Rest, After, Run)] end end. -file("src/lattice_sequence/sequence.gleam", 379). ?DOC( " Splice a run of elements into the stored order immediately after `after`\n" " (or at the head when `after` is `None`), preserving run order.\n" ). -spec splice_run_after( list(element(DUX)), gleam@option:option(item_id()), list(element(DUX)) ) -> list(element(DUX)). splice_run_after(Elements, After, Run) -> case After of none -> lists:append(Run, Elements); {some, Id} -> insert_run_after_id(Elements, Id, Run) end. -file("src/lattice_sequence/sequence.gleam", 346). ?DOC( " Build a contiguous run of new items with chained left origins and a shared\n" " right origin, minting consecutive counters from `start_counter`. Returns\n" " the items in insertion order and the last counter used.\n" ). -spec build_insert_run( lattice_core@replica_id:replica_id(), integer(), list(DUR), gleam@option:option(item_id()), gleam@option:option(item_id()) ) -> {list(item(DUR)), integer()}. build_insert_run(Replica_id, Start_counter, Values, Origin_left, Origin_right) -> Items = gleam@list:index_map( Values, fun(Value, Offset) -> Left = case Offset of 0 -> Origin_left; _ -> {some, {item_id, Replica_id, (Start_counter + Offset) - 1}} end, {item, {item_id, Replica_id, Start_counter + Offset}, Left, Origin_right, Value, none, none} end ), {Items, (Start_counter + erlang:length(Values)) - 1}. -file("src/lattice_sequence/sequence.gleam", 1904). -spec next_element_id(list(element(any()))) -> gleam@option:option(item_id()). next_element_id(Elements) -> case Elements of [] -> none; [El | _] -> {some, element_id(El)} end. -file("src/lattice_sequence/sequence.gleam", 1893). -spec successor_of(list(element(any())), item_id()) -> gleam@option:option(item_id()). successor_of(Elements, Id) -> case Elements of [] -> none; [El | Rest] -> case element_id(El) =:= Id of true -> next_element_id(Rest); false -> successor_of(Rest, Id) end end. -file("src/lattice_sequence/sequence.gleam", 1883). ?DOC( " The element that follows `left` in the canonical order (`None` means the\n" " head of the document, so the first canonical element).\n" ). -spec canonical_successor(list(element(any())), gleam@option:option(item_id())) -> gleam@option:option(item_id()). canonical_successor(Base, Left) -> case Left of none -> next_element_id(Base); {some, Id} -> successor_of(Base, Id) end. -file("src/lattice_sequence/sequence.gleam", 1839). -spec element_is_visible(element(any())) -> boolean(). element_is_visible(El) -> case El of {stable, _, _} -> true; {live_el, Item} -> erlang:element(6, Item) =:= none end. -file("src/lattice_sequence/sequence.gleam", 1863). -spec visible_element_id_at(list(element(any())), integer()) -> gleam@option:option(item_id()). visible_element_id_at(Elements, Index) -> case Elements of [] -> none; [El | Rest] -> case element_is_visible(El) of true -> case Index =:= 0 of true -> {some, element_id(El)}; false -> visible_element_id_at(Rest, Index - 1) end; false -> visible_element_id_at(Rest, Index) end end. -file("src/lattice_sequence/sequence.gleam", 1739). ?DOC( " An empty delta carrying no items — the neutral element for `merge`,\n" " returned when an insert covers zero values.\n" ). -spec empty_delta(lattice_core@replica_id:replica_id()) -> sequence(any()). empty_delta(Replica_id) -> {sequence, Replica_id, 0, [], maps:new(), lattice_core@version_vector:new()}. -file("src/lattice_sequence/sequence.gleam", 1853). -spec visible_length_elements(list(element(any()))) -> integer(). visible_length_elements(Elements) -> _pipe = Elements, gleam@list:fold(_pipe, 0, fun(Count, El) -> case element_is_visible(El) of true -> Count + 1; false -> Count end end). -file("src/lattice_sequence/sequence.gleam", 1763). -spec segments_to_elements(list(segment(EDK))) -> list(element(EDK)). segments_to_elements(Segments) -> gleam@list:flat_map(Segments, fun(Segment) -> case Segment of {live, Item} -> [{live_el, Item}]; {block, First_id, Values} -> {item_id, Rid, First_counter} = First_id, gleam@list:index_map( Values, fun(Value, Offset) -> {stable, {item_id, Rid, First_counter + Offset}, Value} end ) end end). -file("src/lattice_sequence/sequence.gleam", 265). ?DOC( " Safely insert several values at consecutive visible indices starting at\n" " `index`, returning the updated sequence and a single delta of all new\n" " items.\n" "\n" " Each new item's left origin is the previous new item (the first pins to the\n" " visible left neighbor) and every item shares the same right origin — the\n" " left neighbor's canonical successor — so the run integrates contiguously on\n" " every replica. When the state holds no live move record, stored order is\n" " already the canonical order, so the run is spliced directly in place rather\n" " than re-deriving the whole order; otherwise it falls back to a full rebuild.\n" ). -spec try_insert_many_with_delta(sequence(DUK), integer(), list(DUK)) -> {ok, {sequence(DUK), sequence(DUK)}} | {error, insert_error()}. try_insert_many_with_delta(Sequence, Index, Values) -> Elements = segments_to_elements(erlang:element(4, Sequence)), Size = visible_length_elements(Elements), case (Index < 0) orelse (Index > Size) of true -> {error, {index_out_of_bounds, Index, Size}}; false -> case Values of [] -> {ok, {Sequence, empty_delta(erlang:element(2, Sequence))}}; _ -> Origin_left = case Index of 0 -> none; _ -> visible_element_id_at(Elements, Index - 1) end, Has_live_move = gleam@list:any( live_items_of(Elements), fun has_move/1 ), Origin_right = case Has_live_move of false -> canonical_successor(Elements, Origin_left); true -> canonical_successor( rebuild_base( Elements, erlang:element(5, Sequence), erlang:element(6, Sequence) ), Origin_left ) end, {Items, Last_counter} = build_insert_run( erlang:element(2, Sequence), erlang:element(3, Sequence) + 1, Values, Origin_left, Origin_right ), New_elements = gleam@list:map( Items, fun(Field@0) -> {live_el, Field@0} end ), Updated_elements = case Has_live_move of false -> splice_run_after( Elements, Origin_left, New_elements ); true -> rebuild( lists:append(Elements, New_elements), erlang:element(5, Sequence), erlang:element(6, Sequence) ) end, Updated = {sequence, erlang:element(2, Sequence), Last_counter, elements_to_segments(Updated_elements), erlang:element(5, Sequence), erlang:element(6, Sequence)}, Delta = {sequence, erlang:element(2, Sequence), Last_counter, gleam@list:map( Items, fun(Field@0) -> {live, Field@0} end ), maps:new(), lattice_core@version_vector:new()}, {ok, {Updated, Delta}} end end. -file("src/lattice_sequence/sequence.gleam", 216). ?DOC( " Safely insert a value and return both the updated sequence and insertion\n" " delta.\n" ). -spec try_insert_with_delta(sequence(DTV), integer(), DTV) -> {ok, {sequence(DTV), sequence(DTV)}} | {error, insert_error()}. try_insert_with_delta(Sequence, Index, Value) -> try_insert_many_with_delta(Sequence, Index, [Value]). -file("src/lattice_sequence/sequence.gleam", 195). ?DOC( " Insert a value at the visible item index.\n" "\n" " Panics with `IndexOutOfBounds` when `index` is outside `[0, length]`. Use\n" " `try_insert_with_delta` to handle an untrusted index without crashing.\n" ). -spec insert(sequence(DTO), integer(), DTO) -> sequence(DTO). insert(Sequence, Index, Value) -> Updated@1 = case try_insert_with_delta(Sequence, Index, Value) of {ok, {Updated, _}} -> Updated; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"insert"/utf8>>, line => 196, value => _assert_fail, start => 6684, 'end' => 6769, pattern_start => 6695, pattern_end => 6717}) end, Updated@1. -file("src/lattice_sequence/sequence.gleam", 205). ?DOC( " Insert a value and return both the updated sequence and insertion delta.\n" "\n" " Panics with `IndexOutOfBounds` when `index` is outside `[0, length]`. Use\n" " `try_insert_with_delta` to handle an untrusted index without crashing.\n" ). -spec insert_with_delta(sequence(DTR), integer(), DTR) -> {sequence(DTR), sequence(DTR)}. insert_with_delta(Sequence, Index, Value) -> Result@1 = case try_insert_with_delta(Sequence, Index, Value) of {ok, Result} -> Result; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"insert_with_delta"/utf8>>, line => 210, value => _assert_fail, start => 7131, 'end' => 7200, pattern_start => 7142, pattern_end => 7152}) end, Result@1. -file("src/lattice_sequence/sequence.gleam", 231). ?DOC( " Insert several values at consecutive visible indices starting at `index`.\n" "\n" " `values` are placed in order — the first at `index`, the next at\n" " `index + 1`, and so on — exactly as looping `insert` would, but the whole\n" " run is spliced in a single pass and reported as one delta. Panics with\n" " `IndexOutOfBounds` when `index` is outside `[0, length]`. Use\n" " `try_insert_many_with_delta` to handle an untrusted index without crashing.\n" ). -spec insert_many(sequence(DUB), integer(), list(DUB)) -> sequence(DUB). insert_many(Sequence, Index, Values) -> Updated@1 = case try_insert_many_with_delta(Sequence, Index, Values) of {ok, {Updated, _}} -> Updated; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"insert_many"/utf8>>, line => 236, value => _assert_fail, start => 8049, 'end' => 8140, pattern_start => 8060, pattern_end => 8082}) end, Updated@1. -file("src/lattice_sequence/sequence.gleam", 246). ?DOC( " Insert several values and return both the updated sequence and the merged\n" " insertion delta covering every new item.\n" "\n" " Panics with `IndexOutOfBounds` when `index` is outside `[0, length]`. Use\n" " `try_insert_many_with_delta` to handle an untrusted index without crashing.\n" ). -spec insert_many_with_delta(sequence(DUF), integer(), list(DUF)) -> {sequence(DUF), sequence(DUF)}. insert_many_with_delta(Sequence, Index, Values) -> Result@1 = case try_insert_many_with_delta(Sequence, Index, Values) of {ok, Result} -> Result; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"insert_many_with_delta"/utf8>>, line => 251, value => _assert_fail, start => 8565, 'end' => 8640, pattern_start => 8576, pattern_end => 8586}) end, Result@1. -file("src/lattice_sequence/sequence.gleam", 1749). -spec delta_sequence(lattice_core@replica_id:replica_id(), integer(), item(EDH)) -> sequence(EDH). delta_sequence(Replica_id, Counter, Item) -> {sequence, Replica_id, Counter, [{live, Item}], maps:new(), lattice_core@version_vector:new()}. -file("src/lattice_sequence/sequence.gleam", 2033). -spec prepend_element_result( gleam@option:option({list(element(EGX)), item(EGX)}), element(EGX) ) -> gleam@option:option({list(element(EGX)), item(EGX)}). prepend_element_result(Result, El) -> case Result of {some, {Updated_rest, Item}} -> {some, {[El | Updated_rest], Item}}; none -> none end. -file("src/lattice_sequence/sequence.gleam", 2013). -spec tombstone_of( element(EGS), gleam@option:option(item_id()), gleam@option:option(item_id()), op_id() ) -> item(EGS). tombstone_of(El, Prev, Next, Op) -> case El of {live_el, Item} -> {item, erlang:element(2, Item), erlang:element(3, Item), erlang:element(4, Item), erlang:element(5, Item), {some, Op}, erlang:element(7, Item)}; {stable, Id, Value} -> {item, Id, Prev, Next, Value, {some, Op}, none} end. -file("src/lattice_sequence/sequence.gleam", 1973). ?DOC( " Walk to the visible element at `target`, replacing it with a tombstone.\n" " A stable block member is extracted to a live item with origins\n" " synthesized from its current neighbors so ordering keeps it in place.\n" ). -spec tombstone_visible_element_at( list(element(EGK)), integer(), integer(), gleam@option:option(item_id()), op_id() ) -> gleam@option:option({list(element(EGK)), item(EGK)}). tombstone_visible_element_at(Elements, Target, Current, Prev, Op) -> case Elements of [] -> none; [El | Rest] -> case element_is_visible(El) of false -> _pipe = tombstone_visible_element_at( Rest, Target, Current, {some, element_id(El)}, Op ), prepend_element_result(_pipe, El); true -> case Current =:= Target of true -> Item = tombstone_of( El, Prev, next_element_id(Rest), Op ), {some, {[{live_el, Item} | Rest], Item}}; false -> _pipe@1 = tombstone_visible_element_at( Rest, Target, Current + 1, {some, element_id(El)}, Op ), prepend_element_result(_pipe@1, El) end end end. -file("src/lattice_sequence/sequence.gleam", 433). ?DOC( " Safely delete a value and return both the updated sequence and deletion\n" " delta.\n" "\n" " Deletes mint an op ID (bumping this replica's counter) so a compaction\n" " frontier can distinguish acknowledged deletes from in-flight ones.\n" ). -spec try_delete_with_delta(sequence(DVT), integer()) -> {ok, {sequence(DVT), sequence(DVT)}} | {error, delete_error()}. try_delete_with_delta(Sequence, Index) -> Elements = segments_to_elements(erlang:element(4, Sequence)), Size = visible_length_elements(Elements), case (Index < 0) orelse (Index >= Size) of true -> {error, {delete_index_out_of_bounds, Index, Size}}; false -> Next_counter = erlang:element(3, Sequence) + 1, Op = {op_id, erlang:element(2, Sequence), Next_counter}, case tombstone_visible_element_at(Elements, Index, 0, none, Op) of {some, {Updated_elements, Deleted_item}} -> Updated = {sequence, erlang:element(2, Sequence), Next_counter, elements_to_segments(Updated_elements), erlang:element(5, Sequence), erlang:element(6, Sequence)}, Delta = delta_sequence( erlang:element(2, Sequence), Next_counter, Deleted_item ), {ok, {Updated, Delta}}; none -> {error, {delete_index_out_of_bounds, Index, Size}} end end. -file("src/lattice_sequence/sequence.gleam", 410). ?DOC( " Delete the value at the visible item index.\n" "\n" " Panics with `DeleteIndexOutOfBounds` when `index` is outside\n" " `[0, length)`. Use `try_delete_with_delta` to handle an untrusted index\n" " without crashing.\n" ). -spec delete(sequence(DVM), integer()) -> sequence(DVM). delete(Sequence, Index) -> Updated@1 = case try_delete_with_delta(Sequence, Index) of {ok, {Updated, _}} -> Updated; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"delete"/utf8>>, line => 411, value => _assert_fail, start => 14363, 'end' => 14437, pattern_start => 14374, pattern_end => 14396}) end, Updated@1. -file("src/lattice_sequence/sequence.gleam", 420). ?DOC( " Delete a value and return both the updated sequence and deletion delta.\n" "\n" " Panics with `DeleteIndexOutOfBounds` when `index` is outside\n" " `[0, length)`. Use `try_delete_with_delta` to handle an untrusted index\n" " without crashing.\n" ). -spec delete_with_delta(sequence(DVP), integer()) -> {sequence(DVP), sequence(DVP)}. delete_with_delta(Sequence, Index) -> Result@1 = case try_delete_with_delta(Sequence, Index) of {ok, Result} -> Result; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"delete_with_delta"/utf8>>, line => 424, value => _assert_fail, start => 14796, 'end' => 14858, pattern_start => 14807, pattern_end => 14817}) end, Result@1. -file("src/lattice_sequence/sequence.gleam", 1945). -spec swap_in_item(list(element(EFZ)), item(EFZ)) -> list(element(EFZ)). swap_in_item(Elements, Item) -> case Elements of [] -> [{live_el, Item}]; [El | Rest] -> case element_id(El) =:= erlang:element(2, Item) of true -> [{live_el, Item} | Rest]; false -> [El | swap_in_item(Rest, Item)] end end. -file("src/lattice_sequence/sequence.gleam", 2045). ?DOC( " The visible element at `target` as a full item. A stable block member is\n" " given origins synthesized from its current neighbors.\n" ). -spec visible_element_as_item_at( list(element(EHH)), integer(), integer(), gleam@option:option(item_id()) ) -> gleam@option:option(item(EHH)). visible_element_as_item_at(Elements, Target, Current, Prev) -> case Elements of [] -> none; [El | Rest] -> case element_is_visible(El) of false -> visible_element_as_item_at( Rest, Target, Current, {some, element_id(El)} ); true -> case Current =:= Target of true -> case El of {live_el, Item} -> {some, Item}; {stable, Id, Value} -> {some, {item, Id, Prev, next_element_id(Rest), Value, none, none}} end; false -> visible_element_as_item_at( Rest, Target, Current + 1, {some, element_id(El)} ) end end end. -file("src/lattice_sequence/sequence.gleam", 521). -spec move_visible_element( sequence(DWM), list(element(DWM)), integer(), integer() ) -> {ok, {sequence(DWM), sequence(DWM)}} | {error, move_error()}. move_visible_element(Sequence, Elements, From_index, To_index) -> case visible_element_as_item_at(Elements, From_index, 0, none) of none -> {error, {move_from_index_out_of_bounds, From_index, visible_length_elements(Elements)}}; {some, Item} -> Remaining = gleam@list:filter( Elements, fun(El) -> element_id(El) /= erlang:element(2, Item) end ), Origin_left = case To_index of 0 -> none; _ -> visible_element_id_at(Remaining, To_index - 1) end, Origin_right = visible_element_id_at(Remaining, To_index), Next_counter = erlang:element(3, Sequence) + 1, Moved_item = {item, erlang:element(2, Item), erlang:element(3, Item), erlang:element(4, Item), erlang:element(5, Item), erlang:element(6, Item), {some, {move, {op_id, erlang:element(2, Sequence), Next_counter}, Origin_left, Origin_right}}}, Updated_elements = rebuild( swap_in_item(Elements, Moved_item), erlang:element(5, Sequence), erlang:element(6, Sequence) ), Updated = {sequence, erlang:element(2, Sequence), Next_counter, elements_to_segments(Updated_elements), erlang:element(5, Sequence), erlang:element(6, Sequence)}, Delta = delta_sequence( erlang:element(2, Sequence), Next_counter, Moved_item ), {ok, {Updated, Delta}} end. -file("src/lattice_sequence/sequence.gleam", 497). ?DOC( " Safely move a visible item and return both the updated sequence and move\n" " delta.\n" ). -spec try_move_with_delta(sequence(DWG), integer(), integer()) -> {ok, {sequence(DWG), sequence(DWG)}} | {error, move_error()}. try_move_with_delta(Sequence, From_index, To_index) -> Elements = segments_to_elements(erlang:element(4, Sequence)), Size = visible_length_elements(Elements), Length_after_removal = Size - 1, case {(From_index < 0) orelse (From_index >= Size), (To_index < 0) orelse (To_index > Length_after_removal)} of {true, _} -> {error, {move_from_index_out_of_bounds, From_index, Size}}; {_, true} -> {error, {move_to_index_out_of_bounds, To_index, Length_after_removal}}; {false, false} -> move_visible_element(Sequence, Elements, From_index, To_index) end. -file("src/lattice_sequence/sequence.gleam", 470). ?DOC( " Move a visible item to another visible index.\n" "\n" " The `to_index` is interpreted after removing the item from `from_index`.\n" "\n" " Panics with a `MoveError` when either index is out of bounds. Use\n" " `try_move_with_delta` to handle untrusted indices without crashing.\n" ). -spec move(sequence(DVZ), integer(), integer()) -> sequence(DVZ). move(Sequence, From_index, To_index) -> Updated@1 = case try_move_with_delta(Sequence, From_index, To_index) of {ok, {Updated, _}} -> Updated; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"move"/utf8>>, line => 475, value => _assert_fail, start => 16501, 'end' => 16592, pattern_start => 16512, pattern_end => 16534}) end, Updated@1. -file("src/lattice_sequence/sequence.gleam", 486). ?DOC( " Move a visible item and return both the updated sequence and move delta.\n" "\n" " The `to_index` is interpreted after removing the item from `from_index`.\n" "\n" " Panics with a `MoveError` when either index is out of bounds. Use\n" " `try_move_with_delta` to handle untrusted indices without crashing.\n" ). -spec move_with_delta(sequence(DWC), integer(), integer()) -> {sequence(DWC), sequence(DWC)}. move_with_delta(Sequence, From_index, To_index) -> Result@1 = case try_move_with_delta(Sequence, From_index, To_index) of {ok, Result} -> Result; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"move_with_delta"/utf8>>, line => 491, value => _assert_fail, start => 17032, 'end' => 17107, pattern_start => 17043, pattern_end => 17053}) end, Result@1. -file("src/lattice_sequence/sequence.gleam", 575). ?DOC(" Create an anchor at the start of the sequence. Always resolves to 0.\n"). -spec start_anchor() -> anchor(). start_anchor() -> start. -file("src/lattice_sequence/sequence.gleam", 581). ?DOC( " Create an anchor at the end of the sequence. Always resolves to the\n" " current visible length, tracking growth.\n" ). -spec end_anchor() -> anchor(). end_anchor() -> 'end'. -file("src/lattice_sequence/sequence.gleam", 598). ?DOC( " Safely create an anchor at the gap before the visible item at `index`.\n" "\n" " Valid positions are `0 <= index <= length`.\n" ). -spec try_anchor_at(sequence(any()), integer(), bias()) -> {ok, anchor()} | {error, anchor_error()}. try_anchor_at(Sequence, Index, Bias) -> Elements = segments_to_elements(erlang:element(4, Sequence)), Size = visible_length_elements(Elements), case (Index < 0) orelse (Index > Size) of true -> {error, {anchor_index_out_of_bounds, Index, Size}}; false -> case Bias of before -> case visible_element_id_at(Elements, Index) of {some, Id} -> {ok, {at_item, Id, before}}; none -> {ok, 'end'} end; 'after' -> case visible_element_id_at(Elements, Index - 1) of {some, Id@1} -> {ok, {at_item, Id@1, 'after'}}; none -> {ok, start} end end end. -file("src/lattice_sequence/sequence.gleam", 590). ?DOC( " Create an anchor at the gap before the visible item at `index`.\n" "\n" " `Before` bias binds the anchor to the item at `index`; `After` bias binds\n" " it to the item at `index - 1`. Boundary positions with no item on the\n" " chosen side degrade to the start / end sentinels.\n" ). -spec anchor_at(sequence(any()), integer(), bias()) -> anchor(). anchor_at(Sequence, Index, Bias) -> Anchor@1 = case try_anchor_at(Sequence, Index, Bias) of {ok, Anchor} -> Anchor; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"anchor_at"/utf8>>, line => 591, value => _assert_fail, start => 20258, 'end' => 20318, pattern_start => 20269, pattern_end => 20279}) end, Anchor@1. -file("src/lattice_sequence/sequence.gleam", 668). -spec resolve_element_anchor(list(element(any())), item_id(), bias(), integer()) -> {ok, integer()} | {error, nil}. resolve_element_anchor(Elements, Id, Bias, Visible_before) -> case Elements of [] -> {error, nil}; [El | Rest] -> case element_id(El) =:= Id of true -> case {Bias, element_is_visible(El)} of {'after', true} -> {ok, Visible_before + 1}; {_, _} -> {ok, Visible_before} end; false -> case element_is_visible(El) of true -> resolve_element_anchor( Rest, Id, Bias, Visible_before + 1 ); false -> resolve_element_anchor( Rest, Id, Bias, Visible_before ) end end end. -file("src/lattice_sequence/sequence.gleam", 692). -spec resolve_forwarded_gap( list(element(any())), gleam@option:option(item_id()) ) -> {ok, integer()} | {error, anchor_error()}. resolve_forwarded_gap(Elements, Left) -> case Left of none -> {ok, 0}; {some, Left_id} -> case resolve_element_anchor(Elements, Left_id, 'after', 0) of {ok, Index} -> {ok, Index}; {error, nil} -> {error, unknown_anchor_target} end end. -file("src/lattice_sequence/sequence.gleam", 646). ?DOC( " Safely resolve an anchor to a current visible index in `[0, length]`.\n" "\n" " Anchors to compacted items resolve through the forwarding map to the gap\n" " the item left behind — semantically the same as tombstone collapse.\n" "\n" " Returns `Error(UnknownAnchorTarget)` when the anchor references an item\n" " this replica has never seen (created remotely and not yet merged), or one\n" " that was compacted away and whose forwarding entry has since been removed\n" " by the host's retention policy. Either way the anchor is unusable and the\n" " holder should re-anchor.\n" ). -spec try_resolve(sequence(any()), anchor()) -> {ok, integer()} | {error, anchor_error()}. try_resolve(Sequence, Anchor) -> Elements = segments_to_elements(erlang:element(4, Sequence)), case Anchor of start -> {ok, 0}; 'end' -> {ok, visible_length_elements(Elements)}; {at_item, Id, Bias} -> case resolve_element_anchor(Elements, Id, Bias, 0) of {ok, Index} -> {ok, Index}; {error, nil} -> case gleam_stdlib:map_get(erlang:element(5, Sequence), Id) of {ok, {forwarding, Left, _}} -> resolve_forwarded_gap(Elements, Left); {error, nil} -> {error, unknown_anchor_target} end end end. -file("src/lattice_sequence/sequence.gleam", 631). ?DOC( " Resolve an anchor to a current visible index in `[0, length]`.\n" "\n" " Anchors on deleted items still resolve: both biases collapse to the gap\n" " where the item used to be. Anchors follow moved items. Panics with\n" " `UnknownAnchorTarget` when the target was never merged or was compacted\n" " and its forwarding has expired — hosts holding anchors across compaction\n" " rounds should use `try_resolve` and treat failure as \"re-anchor\".\n" ). -spec resolve(sequence(any()), anchor()) -> integer(). resolve(Sequence, Anchor) -> Index@1 = case try_resolve(Sequence, Anchor) of {ok, Index} -> Index; _assert_fail -> erlang:error(#{gleam_error => let_assert, message => <<"Pattern match failed, no pattern matched the value."/utf8>>, file => <>, module => <<"lattice_sequence/sequence"/utf8>>, function => <<"resolve"/utf8>>, line => 632, value => _assert_fail, start => 21678, 'end' => 21730, pattern_start => 21689, pattern_end => 21698}) end, Index@1. -file("src/lattice_sequence/sequence.gleam", 775). -spec encode_bias(bias()) -> gleam@json:json(). encode_bias(Bias) -> case Bias of before -> gleam@json:string(<<"before"/utf8>>); 'after' -> gleam@json:string(<<"after"/utf8>>) end. -file("src/lattice_sequence/sequence.gleam", 1724). -spec encode_item_id(item_id()) -> gleam@json:json(). encode_item_id(Id) -> {item_id, Rid, Counter} = Id, gleam@json:object( [{<<"replica_id"/utf8>>, gleam@json:string(lattice_core@replica_id:to_string(Rid))}, {<<"counter"/utf8>>, gleam@json:int(Counter)}] ). -file("src/lattice_sequence/sequence.gleam", 710). ?DOC( " Encode an anchor as a self-describing JSON value.\n" "\n" " Produces an envelope with `type`, `v` (schema version), and `anchor`, so\n" " anchors can travel between replicas (e.g. shared cursors).\n" ). -spec anchor_to_json(anchor()) -> gleam@json:json(). anchor_to_json(Anchor) -> Encoded = case Anchor of start -> gleam@json:object( [{<<"kind"/utf8>>, gleam@json:string(<<"start"/utf8>>)}] ); 'end' -> gleam@json:object( [{<<"kind"/utf8>>, gleam@json:string(<<"end"/utf8>>)}] ); {at_item, Id, Bias} -> gleam@json:object( [{<<"kind"/utf8>>, gleam@json:string(<<"item"/utf8>>)}, {<<"id"/utf8>>, encode_item_id(Id)}, {<<"bias"/utf8>>, encode_bias(Bias)}] ) end, gleam@json:object( [{<<"type"/utf8>>, gleam@json:string(<<"anchor"/utf8>>)}, {<<"v"/utf8>>, gleam@json:int(1)}, {<<"anchor"/utf8>>, Encoded}] ). -file("src/lattice_sequence/sequence.gleam", 782). -spec bias_decoder() -> gleam@dynamic@decode:decoder(bias()). bias_decoder() -> _pipe = {decoder, fun gleam@dynamic@decode:decode_string/1}, gleam@dynamic@decode:then(_pipe, fun(Value) -> case Value of <<"before"/utf8>> -> gleam@dynamic@decode:success(before); <<"after"/utf8>> -> gleam@dynamic@decode:success('after'); _ -> gleam@dynamic@decode:failure( before, <<"before or after"/utf8>> ) end end). -file("src/lattice_sequence/sequence.gleam", 1673). -spec non_negative_int_decoder() -> gleam@dynamic@decode:decoder(integer()). non_negative_int_decoder() -> _pipe = {decoder, fun gleam@dynamic@decode:decode_int/1}, gleam@dynamic@decode:then(_pipe, fun(Val) -> case Val >= 0 of true -> gleam@dynamic@decode:success(Val); false -> gleam@dynamic@decode:failure( Val, <<"a non-negative integer"/utf8>> ) end end). -file("src/lattice_sequence/sequence.gleam", 1683). -spec item_id_decoder() -> gleam@dynamic@decode:decoder(item_id()). item_id_decoder() -> gleam@dynamic@decode:field( <<"replica_id"/utf8>>, lattice_core@replica_id:decoder(), fun(Rid) -> gleam@dynamic@decode:field( <<"counter"/utf8>>, non_negative_int_decoder(), fun(Counter) -> gleam@dynamic@decode:success({item_id, Rid, Counter}) end ) end ). -file("src/lattice_sequence/sequence.gleam", 730). ?DOC(" Decode an anchor from a JSON string produced by `anchor_to_json`.\n"). -spec anchor_from_json(binary()) -> {ok, anchor()} | {error, gleam@json:decode_error()}. anchor_from_json(Json_string) -> Anchor_decoder = begin gleam@dynamic@decode:field( <<"kind"/utf8>>, {decoder, fun gleam@dynamic@decode:decode_string/1}, fun(Kind) -> case Kind of <<"start"/utf8>> -> gleam@dynamic@decode:success(start); <<"end"/utf8>> -> gleam@dynamic@decode:success('end'); <<"item"/utf8>> -> gleam@dynamic@decode:field( <<"id"/utf8>>, item_id_decoder(), fun(Id) -> gleam@dynamic@decode:field( <<"bias"/utf8>>, bias_decoder(), fun(Bias) -> gleam@dynamic@decode:success( {at_item, Id, Bias} ) end ) end ); _ -> gleam@dynamic@decode:failure( start, <<"one of start, end, item"/utf8>> ) end end ) end, Envelope_decoder = begin gleam@dynamic@decode:field( <<"type"/utf8>>, {decoder, fun gleam@dynamic@decode:decode_string/1}, fun(Type_tag) -> gleam@dynamic@decode:field( <<"v"/utf8>>, {decoder, fun gleam@dynamic@decode:decode_int/1}, fun(Version) -> gleam@dynamic@decode:success({Type_tag, Version}) end ) end ) end, case gleam@json:parse(Json_string, Envelope_decoder) of {error, E} -> {error, E}; {ok, {Type_tag@1, Version@1}} -> case (Type_tag@1 =:= <<"anchor"/utf8>>) andalso (Version@1 =:= 1) of true -> gleam@json:parse( Json_string, begin gleam@dynamic@decode:field( <<"anchor"/utf8>>, Anchor_decoder, fun(Anchor) -> gleam@dynamic@decode:success(Anchor) end ) end ); false -> {error, {unable_to_decode, [{decode_error, <<"type=anchor and v=1"/utf8>>, <<< list(DXU). values(Sequence) -> _pipe = erlang:element(4, Sequence), gleam@list:flat_map(_pipe, fun(Segment) -> case Segment of {block, _, Values} -> Values; {live, Item} -> case erlang:element(6, Item) of none -> [erlang:element(5, Item)]; {some, _} -> [] end end end). -file("src/lattice_sequence/sequence.gleam", 809). ?DOC(" Return the count of visible values.\n"). -spec length(sequence(any())) -> integer(). length(Sequence) -> _pipe = erlang:element(4, Sequence), gleam@list:fold(_pipe, 0, fun(Count, Segment) -> case Segment of {block, _, Values} -> Count + erlang:length(Values); {live, Item} -> case erlang:element(6, Item) of none -> Count + 1; {some, _} -> Count end end end). -file("src/lattice_sequence/sequence.gleam", 827). ?DOC( " The stability frontier this sequence was last compacted at.\n" "\n" " Empty until the first `compact` call. Carried in the state so merging can\n" " tell which side is compacted further.\n" ). -spec frontier(sequence(any())) -> lattice_core@version_vector:version_vector(). frontier(Sequence) -> erlang:element(6, Sequence). -file("src/lattice_sequence/sequence.gleam", 832). ?DOC(" The number of entries in a forwarding map.\n"). -spec forwarding_size(forwarding_map()) -> integer(). forwarding_size(Map) -> {forwarding_map, Entries} = Map, maps:size(Entries). -file("src/lattice_sequence/sequence.gleam", 844). ?DOC( " Remove previously emitted forwarding entries from the sequence.\n" "\n" " Forwardings are bounded by the host's retention policy: keep the map\n" " returned by each `compact` round and expire old rounds by passing them\n" " here. Anchors and deltas referencing removed entries hard-fail\n" " (`UnknownAnchorTarget` / `UnknownOriginTarget`) and must re-anchor or\n" " resync.\n" ). -spec remove_forwardings(sequence(DYB), forwarding_map()) -> sequence(DYB). remove_forwardings(Sequence, Map) -> {forwarding_map, Entries} = Map, Remaining = gleam@dict:fold( Entries, erlang:element(5, Sequence), fun(Acc, Id, _) -> gleam@dict:delete(Acc, Id) end ), {sequence, erlang:element(2, Sequence), erlang:element(3, Sequence), erlang:element(4, Sequence), Remaining, erlang:element(6, Sequence)}. -file("src/lattice_sequence/sequence.gleam", 2477). -spec merge_move(gleam@option:option(move()), gleam@option:option(move())) -> gleam@option:option(move()). merge_move(A, B) -> case {A, B} of {none, none} -> none; {{some, Move}, none} -> {some, Move}; {none, {some, Move@1}} -> {some, Move@1}; {{some, A_move}, {some, B_move}} -> case compare_moves(A_move, B_move) of lt -> {some, B_move}; eq -> {some, A_move}; gt -> {some, A_move} end end. -file("src/lattice_sequence/sequence.gleam", 2464). -spec merge_deleted(gleam@option:option(op_id()), gleam@option:option(op_id())) -> gleam@option:option(op_id()). merge_deleted(A, B) -> case {A, B} of {none, none} -> none; {{some, Op}, none} -> {some, Op}; {none, {some, Op@1}} -> {some, Op@1}; {{some, A_op}, {some, B_op}} -> case compare_op_ids(A_op, B_op) of gt -> {some, B_op}; _ -> {some, A_op} end end. -file("src/lattice_sequence/sequence.gleam", 2455). -spec compare_optional_id( gleam@option:option(item_id()), gleam@option:option(item_id()) ) -> gleam@order:order(). compare_optional_id(A, B) -> case {A, B} of {none, none} -> eq; {none, {some, _}} -> lt; {{some, _}, none} -> gt; {{some, A_id}, {some, B_id}} -> compare_item_ids(A_id, B_id) end. -file("src/lattice_sequence/sequence.gleam", 2443). -spec compare_origin_pair( {gleam@option:option(item_id()), gleam@option:option(item_id())}, {gleam@option:option(item_id()), gleam@option:option(item_id())} ) -> gleam@order:order(). compare_origin_pair(A, B) -> {A_left, A_right} = A, {B_left, B_right} = B, case compare_optional_id(A_left, B_left) of eq -> compare_optional_id(A_right, B_right); Other -> Other end. -file("src/lattice_sequence/sequence.gleam", 2427). ?DOC( " Origins are immutable in normal operation, but extracting a block member\n" " (for a volatile delete or move) synthesizes origins from local neighbors,\n" " so two replicas can disagree. Pick deterministically so merge commutes.\n" ). -spec pick_origins(item(EKQ), item(EKQ)) -> {gleam@option:option(item_id()), gleam@option:option(item_id())}. pick_origins(A, B) -> gleam@bool:guard( (erlang:element(3, A) =:= erlang:element(3, B)) andalso (erlang:element( 4, A ) =:= erlang:element(4, B)), {erlang:element(3, A), erlang:element(4, A)}, fun() -> case compare_origin_pair( {erlang:element(3, A), erlang:element(4, A)}, {erlang:element(3, B), erlang:element(4, B)} ) of gt -> {erlang:element(3, B), erlang:element(4, B)}; _ -> {erlang:element(3, A), erlang:element(4, A)} end end ). -file("src/lattice_sequence/sequence.gleam", 2411). -spec merge_item(item(EKM), item(EKM)) -> item(EKM). merge_item(A, B) -> {Origin_left, Origin_right} = pick_origins(A, B), {item, erlang:element(2, A), Origin_left, Origin_right, erlang:element(5, A), merge_deleted(erlang:element(6, A), erlang:element(6, B)), merge_move(erlang:element(7, A), erlang:element(7, B))}. -file("src/lattice_sequence/sequence.gleam", 973). ?DOC( " One side has the element compacted into a block, the other still holds a\n" " live item for it. A tombstone or a move keeps the item live and supersedes\n" " the block slot; only a plain copy collapses to the stable representation.\n" " The rule looks only at the live item, so both merge directions agree.\n" "\n" " A moved item is never collapsed into the block skeleton, even if the merged\n" " frontier covers its move op: `compact` refuses to stabilize any state that\n" " holds a move (see `compact`), so a covered-move block slot cannot legitimately\n" " arise, and baking one here would strip the origins a peer's concurrent\n" " above-frontier inserts integrate against and break merge commutativity.\n" ). -spec stable_or_live(item(DYQ), lattice_core@version_vector:version_vector()) -> element(DYQ). stable_or_live(Item, _) -> case {erlang:element(6, Item), erlang:element(7, Item)} of {none, none} -> {stable, erlang:element(2, Item), erlang:element(5, Item)}; {_, _} -> {live_el, Item} end. -file("src/lattice_sequence/sequence.gleam", 939). -spec reconcile_element( element(DYI), gleam@dict:dict(item_id(), item(DYI)), gleam@dict:dict(item_id(), nil), lattice_core@version_vector:version_vector() ) -> element(DYI). reconcile_element(El, B_lives, B_stables, Frontier) -> case El of {live_el, Item} -> case gleam_stdlib:map_get(B_lives, erlang:element(2, Item)) of {ok, Other} -> {live_el, merge_item(Item, Other)}; {error, nil} -> case gleam@dict:has_key(B_stables, erlang:element(2, Item)) of true -> stable_or_live(Item, Frontier); false -> El end end; {stable, Id, _} -> case gleam_stdlib:map_get(B_lives, Id) of {ok, Other@1} -> stable_or_live(Other@1, Frontier); {error, nil} -> El end end. -file("src/lattice_sequence/sequence.gleam", 1846). -spec is_stable_element(element(any())) -> boolean(). is_stable_element(El) -> case El of {stable, _, _} -> true; {live_el, _} -> false end. -file("src/lattice_sequence/sequence.gleam", 2108). -spec element_id_dict(list(element(any()))) -> gleam@dict:dict(item_id(), nil). element_id_dict(Elements) -> gleam@list:fold( Elements, maps:new(), fun(Acc, El) -> gleam@dict:insert(Acc, element_id(El), nil) end ). -file("src/lattice_sequence/sequence.gleam", 2104). -spec stable_elements_of(list(element(EHY))) -> list(element(EHY)). stable_elements_of(Elements) -> gleam@list:filter(Elements, fun is_stable_element/1). -file("src/lattice_sequence/sequence.gleam", 2114). -spec stable_id_dict(list(element(any()))) -> gleam@dict:dict(item_id(), nil). stable_id_dict(Elements) -> _pipe = Elements, _pipe@1 = stable_elements_of(_pipe), element_id_dict(_pipe@1). -file("src/lattice_sequence/sequence.gleam", 2098). -spec live_item_dict(list(element(EHS))) -> gleam@dict:dict(item_id(), item(EHS)). live_item_dict(Elements) -> _pipe = Elements, _pipe@1 = live_items_of(_pipe), gleam@list:fold( _pipe@1, maps:new(), fun(Acc, Item) -> gleam@dict:insert(Acc, erlang:element(2, Item), Item) end ). -file("src/lattice_sequence/sequence.gleam", 1043). -spec canonical_clocks(lattice_core@version_vector:version_vector()) -> list({lattice_core@replica_id:replica_id(), integer()}). canonical_clocks(Vv) -> _pipe = lattice_core@version_vector:to_dict(Vv), _pipe@1 = maps:to_list(_pipe), gleam@list:sort( _pipe@1, fun(X, Y) -> lattice_core@replica_id:compare( erlang:element(1, X), erlang:element(1, Y) ) end ). -file("src/lattice_sequence/sequence.gleam", 1049). -spec compare_clock_lists( list({lattice_core@replica_id:replica_id(), integer()}), list({lattice_core@replica_id:replica_id(), integer()}) ) -> gleam@order:order(). compare_clock_lists(A, B) -> case {A, B} of {[], []} -> eq; {[], _} -> lt; {_, []} -> gt; {[{Ra, Ca} | Ta], [{Rb, Cb} | Tb]} -> case lattice_core@replica_id:compare(Ra, Rb) of eq -> case gleam@int:compare(Ca, Cb) of eq -> compare_clock_lists(Ta, Tb); Other -> Other end; Other@1 -> Other@1 end end. -file("src/lattice_sequence/sequence.gleam", 1039). ?DOC( " A deterministic, direction-independent order on version vectors, used\n" " only to pick a covered-order source when merging states compacted at\n" " concurrent frontiers (which a sequencer host never produces).\n" ). -spec frontier_tiebreak( lattice_core@version_vector:version_vector(), lattice_core@version_vector:version_vector() ) -> gleam@order:order(). frontier_tiebreak(A, B) -> compare_clock_lists(canonical_clocks(A), canonical_clocks(B)). -file("src/lattice_sequence/sequence.gleam", 2544). ?DOC( " Collapse forwarding chains: a target that was itself dropped in a later\n" " pass (or on the other side of a merge) is chased to a retained ID, so a\n" " single lookup always lands on a live target.\n" ). -spec normalize_forwardings(gleam@dict:dict(item_id(), forwarding())) -> gleam@dict:dict(item_id(), forwarding()). normalize_forwardings(Entries) -> Fuel = maps:size(Entries) + 1, gleam@dict:map_values( Entries, fun(_, Forwarding) -> {forwarding, Left, Right} = Forwarding, {forwarding, chase_left(Left, Entries, Fuel), chase_right(Right, Entries, Fuel)} end ). -file("src/lattice_sequence/sequence.gleam", 2534). -spec pick_forwarding(forwarding(), forwarding()) -> forwarding(). pick_forwarding(A, B) -> case compare_origin_pair( {erlang:element(2, A), erlang:element(3, A)}, {erlang:element(2, B), erlang:element(3, B)} ) of gt -> B; _ -> A end. -file("src/lattice_sequence/sequence.gleam", 2521). -spec merge_forwarding_entries( gleam@dict:dict(item_id(), forwarding()), gleam@dict:dict(item_id(), forwarding()) ) -> gleam@dict:dict(item_id(), forwarding()). merge_forwarding_entries(A, B) -> gleam@dict:fold( B, A, fun(Acc, Id, Forwarding) -> case gleam_stdlib:map_get(Acc, Id) of {ok, Existing} -> gleam@dict:insert( Acc, Id, pick_forwarding(Existing, Forwarding) ); {error, nil} -> gleam@dict:insert(Acc, Id, Forwarding) end end ). -file("src/lattice_sequence/sequence.gleam", 867). ?DOC( " Merge two sequence CRDT states.\n" "\n" " Items are joined by their stable IDs. Concurrent deletes are preserved by\n" " keeping the winning delete op, and the merged item set is deterministically\n" " reordered using each item's left and right origins. Stable blocks form a\n" " fixed skeleton that live items are ordered around.\n" "\n" " States compacted at different frontiers merge as long as one frontier\n" " dominates the other (with a global sequencer, floors are totally ordered\n" " so this always holds). An item absent from the further-compacted side and\n" " covered by its frontier is treated as compacted away and stays dropped.\n" ). -spec merge(sequence(DYE), sequence(DYE)) -> sequence(DYE). merge(A, B) -> Forwardings = begin _pipe = merge_forwarding_entries( erlang:element(5, A), erlang:element(5, B) ), normalize_forwardings(_pipe) end, Frontier = lattice_core@version_vector:merge( erlang:element(6, A), erlang:element(6, B) ), A_elements = segments_to_elements(erlang:element(4, A)), B_elements = segments_to_elements(erlang:element(4, B)), A_ids = element_id_dict(A_elements), B_ids = element_id_dict(B_elements), B_lives = live_item_dict(B_elements), B_stables = stable_id_dict(B_elements), Dropped = fun(Id) -> (gleam@dict:has_key(Forwardings, Id) orelse (not gleam@dict:has_key( A_ids, Id ) andalso frontier_covers(erlang:element(6, A), Id))) orelse (not gleam@dict:has_key(B_ids, Id) andalso frontier_covers( erlang:element(6, B), Id )) end, Covered_source = case lattice_core@version_vector:compare( erlang:element(6, A), erlang:element(6, B) ) of before -> B_elements; concurrent -> case frontier_tiebreak(erlang:element(6, A), erlang:element(6, B)) of gt -> B_elements; _ -> A_elements end; _ -> A_elements end, {Other_lives, Other_stables} = case Covered_source =:= A_elements of true -> {B_lives, B_stables}; false -> {live_item_dict(A_elements), stable_id_dict(A_elements)} end, Covered_elements = begin _pipe@1 = Covered_source, _pipe@2 = gleam@list:filter( _pipe@1, fun(El) -> is_stable_element(El) orelse frontier_covers( Frontier, element_id(El) ) end ), _pipe@3 = gleam@list:filter( _pipe@2, fun(El@1) -> not Dropped(element_id(El@1)) end ), gleam@list:map( _pipe@3, fun(_capture) -> reconcile_element( _capture, Other_lives, Other_stables, Frontier ) end ) end, Volatile_pool = begin _pipe@4 = lists:append( live_items_of(A_elements), live_items_of(B_elements) ), _pipe@5 = gleam@list:filter( _pipe@4, fun(Item) -> not frontier_covers(Frontier, erlang:element(2, Item)) andalso not Dropped( erlang:element(2, Item) ) end ), _pipe@6 = gleam@list:fold( _pipe@5, maps:new(), fun(Pool, Item@1) -> case gleam_stdlib:map_get(Pool, erlang:element(2, Item@1)) of {ok, Existing} -> gleam@dict:insert( Pool, erlang:element(2, Item@1), merge_item(Existing, Item@1) ); {error, nil} -> gleam@dict:insert( Pool, erlang:element(2, Item@1), Item@1 ) end end ), _pipe@7 = maps:values(_pipe@6), gleam@list:map(_pipe@7, fun(Field@0) -> {live_el, Field@0} end) end, Elements = rebuild( lists:append(Covered_elements, Volatile_pool), Forwardings, Frontier ), {sequence, erlang:element(2, A), gleam@int:max(erlang:element(3, A), erlang:element(3, B)), elements_to_segments(Elements), Forwardings, Frontier}. -file("src/lattice_sequence/sequence.gleam", 1359). -spec left_targets( list(classified(any())), gleam@option:option(item_id()), gleam@dict:dict(item_id(), gleam@option:option(item_id())) ) -> gleam@dict:dict(item_id(), gleam@option:option(item_id())). left_targets(Classified, Last_retained, Acc) -> case Classified of [] -> Acc; [{retained, El} | Rest] -> left_targets(Rest, {some, element_id(El)}, Acc); [{dropped, Id} | Rest@1] -> left_targets( Rest@1, Last_retained, gleam@dict:insert(Acc, Id, Last_retained) ) end. -file("src/lattice_sequence/sequence.gleam", 1337). -spec forwarding_entries_for_pass(list(classified(any()))) -> gleam@dict:dict(item_id(), forwarding()). forwarding_entries_for_pass(Classified) -> Lefts = left_targets(Classified, none, maps:new()), {Rights, _} = gleam@list:fold_right( Classified, {maps:new(), none}, fun(Acc, Entry) -> {Targets, Next_retained} = Acc, case Entry of {retained, El} -> {Targets, {some, element_id(El)}}; {dropped, Id} -> {gleam@dict:insert(Targets, Id, Next_retained), Next_retained} end end ), gleam@dict:fold( Lefts, maps:new(), fun(Acc@1, Id@1, Left) -> Right = case gleam_stdlib:map_get(Rights, Id@1) of {ok, Target} -> Target; {error, nil} -> none end, gleam@dict:insert(Acc@1, Id@1, {forwarding, Left, Right}) end ). -file("src/lattice_sequence/sequence.gleam", 2512). -spec frontier_covers_op(lattice_core@version_vector:version_vector(), op_id()) -> boolean(). frontier_covers_op(Frontier, Op) -> {op_id, Rid, Counter} = Op, lattice_core@version_vector:get(Frontier, Rid) >= Counter. -file("src/lattice_sequence/sequence.gleam", 1317). -spec item_stability(item(any()), lattice_core@version_vector:version_vector()) -> stability(). item_stability(Item, Stable) -> gleam@bool:guard( not frontier_covers(Stable, erlang:element(2, Item)), keep_live, fun() -> case erlang:element(6, Item) of {some, Op} -> case frontier_covers_op(Stable, Op) of true -> drop_tombstone; false -> keep_live end; none -> case erlang:element(7, Item) of none -> to_stable; {some, {move, Op@1, _, _}} -> case frontier_covers_op(Stable, Op@1) of true -> to_stable; false -> keep_live end end end end ). -file("src/lattice_sequence/sequence.gleam", 1257). -spec do_compact(sequence(EAP), lattice_core@version_vector:version_vector()) -> {sequence(EAP), forwarding_map()}. do_compact(Sequence, Stable) -> Elements = segments_to_elements(erlang:element(4, Sequence)), Classified = gleam@list:map(Elements, fun(El) -> case El of {stable, _, _} -> {retained, El}; {live_el, Item} -> case item_stability(Item, Stable) of drop_tombstone -> {dropped, erlang:element(2, Item)}; to_stable -> {retained, {stable, erlang:element(2, Item), erlang:element(5, Item)}}; keep_live -> {retained, El} end end end), New_entries = forwarding_entries_for_pass(Classified), Kept = gleam@list:filter_map(Classified, fun(Entry) -> case Entry of {retained, El@1} -> {ok, El@1}; {dropped, _} -> {error, nil} end end), Updated_old = gleam@dict:map_values( erlang:element(5, Sequence), fun(_, Forwarding) -> {forwarding, Left, Right} = Forwarding, {forwarding, chase_left(Left, New_entries, maps:size(New_entries) + 1), chase_right(Right, New_entries, maps:size(New_entries) + 1)} end ), All_forwardings = gleam@dict:fold( New_entries, Updated_old, fun(Acc, Id, Forwarding@1) -> gleam@dict:insert(Acc, Id, Forwarding@1) end ), Compacted = {sequence, erlang:element(2, Sequence), erlang:element(3, Sequence), elements_to_segments(Kept), All_forwardings, Stable}, {Compacted, {forwarding_map, New_entries}}. -file("src/lattice_sequence/sequence.gleam", 1232). ?DOC( " Compact everything at or below a stability frontier.\n" "\n" " `stable` must describe a causal cut the host knows no in-flight or future\n" " op can reference (e.g. the version vector accumulated by replaying ops up\n" " to a global sequencer's acknowledgement floor). For the stable region the\n" " pass drops tombstones, merges runs of adjacent same-replica items with\n" " sequential counters into blocks, and strips origins and move slots.\n" "\n" " Returns the compacted sequence and the forwarding entries emitted by this\n" " pass (one per dropped ID). The cumulative forwarding map is also carried\n" " in the sequence; hosts bound its growth with `remove_forwardings`.\n" "\n" " Compacting at the current frontier, at an older one, or at one concurrent\n" " with it is a no-op — frontiers only advance.\n" "\n" " A state holding ANY move record is left unchanged, even when the move op is\n" " already covered by `stable`. This guard is load-bearing for convergence, not\n" " just conservatism: baking a settled move into the compact skeleton fixes its\n" " position from only the compacting replica's items, but a peer's still-live\n" " concurrent inserts above the frontier integrate against the moved item's\n" " origins — which stabilization strips. The two then order those inserts\n" " differently and `merge` stops commuting (see the property test\n" " `merge_commutes_with_compaction_for_deltas_above_frontier`). Because move\n" " records are never cleared locally, a replica that uses `move` cannot compact\n" " until it merges a peer that has already stabilized the item into a block; a\n" " safe stabilization path for moves is future work (see issue #98).\n" ). -spec compact(sequence(EAM), lattice_core@version_vector:version_vector()) -> {sequence(EAM), forwarding_map()}. compact(Sequence, Stable) -> Has_move_records = begin _pipe = erlang:element(4, Sequence), _pipe@1 = segments_to_elements(_pipe), _pipe@2 = live_items_of(_pipe@1), gleam@list:any(_pipe@2, fun has_move/1) end, case Has_move_records of true -> {Sequence, {forwarding_map, maps:new()}}; false -> case lattice_core@version_vector:compare( Stable, erlang:element(6, Sequence) ) of 'after' -> do_compact(Sequence, Stable); _ -> {Sequence, {forwarding_map, maps:new()}} end end. -file("src/lattice_sequence/sequence.gleam", 1470). -spec right_of(forwarding()) -> gleam@option:option(item_id()). right_of(Forwarding) -> erlang:element(3, Forwarding). -file("src/lattice_sequence/sequence.gleam", 1466). -spec left_of(forwarding()) -> gleam@option:option(item_id()). left_of(Forwarding) -> erlang:element(2, Forwarding). -file("src/lattice_sequence/sequence.gleam", 1449). -spec translate_move( gleam@option:option(move()), fun((gleam@option:option(item_id()), fun((forwarding()) -> gleam@option:option(item_id()))) -> {ok, gleam@option:option(item_id())} | {error, translate_error()}) ) -> {ok, gleam@option:option(move())} | {error, translate_error()}. translate_move(Move, Translate) -> case Move of none -> {ok, none}; {some, {move, Op, Move_left, Move_right}} -> gleam@result:'try'( Translate(Move_left, fun left_of/1), fun(Move_left@1) -> gleam@result:'try'( Translate(Move_right, fun right_of/1), fun(Move_right@1) -> {ok, {some, {move, Op, Move_left@1, Move_right@1}}} end ) end ) end. -file("src/lattice_sequence/sequence.gleam", 1426). -spec translate_element( element(EBP), fun((gleam@option:option(item_id()), fun((forwarding()) -> gleam@option:option(item_id()))) -> {ok, gleam@option:option(item_id())} | {error, translate_error()}) ) -> {ok, element(EBP)} | {error, translate_error()}. translate_element(El, Translate) -> case El of {stable, _, _} -> {ok, El}; {live_el, Item} -> gleam@result:'try'( Translate(erlang:element(3, Item), fun left_of/1), fun(Origin_left) -> gleam@result:'try'( Translate(erlang:element(4, Item), fun right_of/1), fun(Origin_right) -> gleam@result:'try'( translate_move( erlang:element(7, Item), Translate ), fun(Move) -> {ok, {live_el, {item, erlang:element(2, Item), Origin_left, Origin_right, erlang:element(5, Item), erlang:element(6, Item), Move}}} end ) end ) end ) end. -file("src/lattice_sequence/sequence.gleam", 1381). ?DOC( " Translate a delta's origins onto a compacted state.\n" "\n" " Rebase support for evicted clients: origins (including move origins)\n" " referencing compacted IDs are rewritten through `onto`'s forwarding map to\n" " the gap the ID left behind. Items whose own ID was compacted away are\n" " dropped from the delta — the op is already settled. Returns\n" " `Error(UnknownOriginTarget)` when an origin is neither present, part of\n" " the delta itself, nor forwarded (the forwarding expired); the host must\n" " degrade the op to a positional edit or discard it.\n" ). -spec translate_origins(sequence(EBJ), sequence(EBJ)) -> {ok, sequence(EBJ)} | {error, translate_error()}. translate_origins(Delta, Onto) -> Onto_ids = element_id_dict(segments_to_elements(erlang:element(4, Onto))), Delta_elements = segments_to_elements(erlang:element(4, Delta)), Delta_ids = element_id_dict(Delta_elements), Known = fun(Id) -> gleam@dict:has_key(Onto_ids, Id) orelse gleam@dict:has_key( Delta_ids, Id ) end, Dropped = fun(Id@1) -> gleam@dict:has_key(erlang:element(5, Onto), Id@1) orelse (not gleam@dict:has_key( Onto_ids, Id@1 ) andalso frontier_covers(erlang:element(6, Onto), Id@1)) end, Translate = fun(Origin, Pick) -> case Origin of none -> {ok, none}; {some, Id@2} -> case Known(Id@2) of true -> {ok, Origin}; false -> case gleam_stdlib:map_get(erlang:element(5, Onto), Id@2) of {ok, Forwarding} -> {ok, Pick(Forwarding)}; {error, nil} -> {error, unknown_origin_target} end end end end, Translated = begin _pipe = Delta_elements, _pipe@1 = gleam@list:filter( _pipe, fun(El) -> not Dropped(element_id(El)) end ), gleam@list:try_map( _pipe@1, fun(_capture) -> translate_element(_capture, Translate) end ) end, case Translated of {ok, Elements} -> {ok, {sequence, erlang:element(2, Delta), erlang:element(3, Delta), elements_to_segments(Elements), erlang:element(5, Delta), erlang:element(6, Delta)}}; {error, Error} -> {error, Error} end. -file("src/lattice_sequence/sequence.gleam", 1717). -spec encode_optional_item_id(gleam@option:option(item_id())) -> gleam@json:json(). encode_optional_item_id(Item_id) -> case Item_id of {some, Id} -> encode_item_id(Id); none -> gleam@json:null() end. -file("src/lattice_sequence/sequence.gleam", 1708). -spec encode_op_id(op_id()) -> gleam@json:json(). encode_op_id(Id) -> {op_id, Rid, Counter} = Id, gleam@json:object( [{<<"replica_id"/utf8>>, gleam@json:string(lattice_core@replica_id:to_string(Rid))}, {<<"counter"/utf8>>, gleam@json:int(Counter)}] ). -file("src/lattice_sequence/sequence.gleam", 1689). -spec encode_optional_move(gleam@option:option(move())) -> gleam@json:json(). encode_optional_move(Move) -> case Move of none -> gleam@json:null(); {some, {move, Op_id, Origin_left, Origin_right}} -> gleam@json:object( [{<<"op_id"/utf8>>, encode_op_id(Op_id)}, {<<"origin_left"/utf8>>, encode_optional_item_id(Origin_left)}, {<<"origin_right"/utf8>>, encode_optional_item_id(Origin_right)}] ) end. -file("src/lattice_sequence/sequence.gleam", 1701). -spec encode_optional_op_id(gleam@option:option(op_id())) -> gleam@json:json(). encode_optional_op_id(Op_id) -> case Op_id of {some, Op} -> encode_op_id(Op); none -> gleam@json:null() end. -file("src/lattice_sequence/sequence.gleam", 1564). -spec encode_segment(segment(ECR), fun((ECR) -> gleam@json:json())) -> gleam@json:json(). encode_segment(Segment, Encode_value) -> case Segment of {block, First_id, Values} -> gleam@json:object( [{<<"kind"/utf8>>, gleam@json:string(<<"block"/utf8>>)}, {<<"first_id"/utf8>>, encode_item_id(First_id)}, {<<"values"/utf8>>, gleam@json:array(Values, Encode_value)}] ); {live, Item} -> gleam@json:object( [{<<"kind"/utf8>>, gleam@json:string(<<"item"/utf8>>)}, {<<"id"/utf8>>, encode_item_id(erlang:element(2, Item))}, {<<"origin_left"/utf8>>, encode_optional_item_id(erlang:element(3, Item))}, {<<"origin_right"/utf8>>, encode_optional_item_id(erlang:element(4, Item))}, {<<"value"/utf8>>, Encode_value(erlang:element(5, Item))}, {<<"deleted"/utf8>>, encode_optional_op_id(erlang:element(6, Item))}, {<<"move"/utf8>>, encode_optional_move(erlang:element(7, Item))}] ) end. -file("src/lattice_sequence/sequence.gleam", 1634). -spec encode_forwarding({item_id(), forwarding()}) -> gleam@json:json(). encode_forwarding(Entry) -> {Id, {forwarding, Left, Right}} = Entry, gleam@json:object( [{<<"id"/utf8>>, encode_item_id(Id)}, {<<"left"/utf8>>, encode_optional_item_id(Left)}, {<<"right"/utf8>>, encode_optional_item_id(Right)}] ). -file("src/lattice_sequence/sequence.gleam", 1480). ?DOC( " Encode a sequence CRDT as a self-describing JSON value.\n" "\n" " Produces an envelope with `type`, `v` (schema version), and `state`. The\n" " state includes this replica ID, local counter, applied compaction\n" " frontier, forwarding entries, and every segment: compact blocks of stable\n" " values and full items including tombstones.\n" ). -spec to_json(sequence(ECK), fun((ECK) -> gleam@json:json())) -> gleam@json:json(). to_json(Sequence, Encode_value) -> gleam@json:object( [{<<"type"/utf8>>, gleam@json:string(<<"sequence"/utf8>>)}, {<<"v"/utf8>>, gleam@json:int(1)}, {<<"state"/utf8>>, gleam@json:object( [{<<"self_id"/utf8>>, lattice_core@replica_id:to_json( erlang:element(2, Sequence) )}, {<<"counter"/utf8>>, gleam@json:int(erlang:element(3, Sequence))}, {<<"frontier"/utf8>>, lattice_core@version_vector:to_json( erlang:element(6, Sequence) )}, {<<"forwardings"/utf8>>, gleam@json:array( maps:to_list(erlang:element(5, Sequence)), fun encode_forwarding/1 )}, {<<"segments"/utf8>>, gleam@json:array( erlang:element(4, Sequence), fun(_capture) -> encode_segment(_capture, Encode_value) end )}] )}] ). -file("src/lattice_sequence/sequence.gleam", 1667). -spec op_id_decoder() -> gleam@dynamic@decode:decoder(op_id()). op_id_decoder() -> gleam@dynamic@decode:field( <<"replica_id"/utf8>>, lattice_core@replica_id:decoder(), fun(Rid) -> gleam@dynamic@decode:field( <<"counter"/utf8>>, non_negative_int_decoder(), fun(Counter) -> gleam@dynamic@decode:success({op_id, Rid, Counter}) end ) end ). -file("src/lattice_sequence/sequence.gleam", 1650). -spec move_decoder() -> gleam@dynamic@decode:decoder(move()). move_decoder() -> gleam@dynamic@decode:field( <<"op_id"/utf8>>, op_id_decoder(), fun(Op_id) -> gleam@dynamic@decode:field( <<"origin_left"/utf8>>, gleam@dynamic@decode:optional(item_id_decoder()), fun(Origin_left) -> gleam@dynamic@decode:field( <<"origin_right"/utf8>>, gleam@dynamic@decode:optional(item_id_decoder()), fun(Origin_right) -> gleam@dynamic@decode:success( {move, Op_id, Origin_left, Origin_right} ) end ) end ) end ). -file("src/lattice_sequence/sequence.gleam", 1588). -spec segment_decoder(gleam@dynamic@decode:decoder(ECT)) -> gleam@dynamic@decode:decoder(segment(ECT)). segment_decoder(Value_decoder) -> gleam@dynamic@decode:field( <<"kind"/utf8>>, {decoder, fun gleam@dynamic@decode:decode_string/1}, fun(Kind) -> case Kind of <<"block"/utf8>> -> gleam@dynamic@decode:field( <<"first_id"/utf8>>, item_id_decoder(), fun(First_id) -> gleam@dynamic@decode:field( <<"values"/utf8>>, gleam@dynamic@decode:list(Value_decoder), fun(Values) -> gleam@dynamic@decode:success( {block, First_id, Values} ) end ) end ); <<"item"/utf8>> -> gleam@dynamic@decode:field( <<"id"/utf8>>, item_id_decoder(), fun(Id) -> gleam@dynamic@decode:field( <<"origin_left"/utf8>>, gleam@dynamic@decode:optional(item_id_decoder()), fun(Origin_left) -> gleam@dynamic@decode:field( <<"origin_right"/utf8>>, gleam@dynamic@decode:optional( item_id_decoder() ), fun(Origin_right) -> gleam@dynamic@decode:field( <<"value"/utf8>>, Value_decoder, fun(Value) -> gleam@dynamic@decode:field( <<"deleted"/utf8>>, gleam@dynamic@decode:optional( op_id_decoder() ), fun(Deleted) -> gleam@dynamic@decode:optional_field( <<"move"/utf8>>, none, gleam@dynamic@decode:optional( move_decoder( ) ), fun(Move) -> gleam@dynamic@decode:success( {live, {item, Id, Origin_left, Origin_right, Value, Deleted, Move}} ) end ) end ) end ) end ) end ) end ); _ -> gleam@dynamic@decode:failure( {block, {item_id, lattice_core@replica_id:new(<<""/utf8>>), 0}, []}, <<"segment kind of block or item"/utf8>> ) end end ). -file("src/lattice_sequence/sequence.gleam", 1643). -spec forwarding_decoder() -> gleam@dynamic@decode:decoder({item_id(), forwarding()}). forwarding_decoder() -> gleam@dynamic@decode:field( <<"id"/utf8>>, item_id_decoder(), fun(Id) -> gleam@dynamic@decode:field( <<"left"/utf8>>, gleam@dynamic@decode:optional(item_id_decoder()), fun(Left) -> gleam@dynamic@decode:field( <<"right"/utf8>>, gleam@dynamic@decode:optional(item_id_decoder()), fun(Right) -> gleam@dynamic@decode:success( {Id, {forwarding, Left, Right}} ) end ) end ) end ). -file("src/lattice_sequence/sequence.gleam", 1512). ?DOC( " Decode a sequence CRDT from a JSON string produced by `to_json`.\n" "\n" " Returns `Ok(Sequence)` on success, or `Error(json.DecodeError)` if the\n" " input is not a valid sequence JSON envelope. Live items are reordered\n" " deterministically from their stable origins before the `Sequence` is\n" " returned.\n" ). -spec from_json(binary(), gleam@dynamic@decode:decoder(ECM)) -> {ok, sequence(ECM)} | {error, gleam@json:decode_error()}. from_json(Json_string, Value_decoder) -> State_decoder = begin gleam@dynamic@decode:field( <<"state"/utf8>>, begin gleam@dynamic@decode:field( <<"self_id"/utf8>>, lattice_core@replica_id:decoder(), fun(Self_id) -> gleam@dynamic@decode:field( <<"counter"/utf8>>, non_negative_int_decoder(), fun(Counter) -> gleam@dynamic@decode:field( <<"frontier"/utf8>>, lattice_core@version_vector:decoder(), fun(Frontier) -> gleam@dynamic@decode:field( <<"forwardings"/utf8>>, gleam@dynamic@decode:list( forwarding_decoder() ), fun(Forwardings) -> gleam@dynamic@decode:field( <<"segments"/utf8>>, gleam@dynamic@decode:list( segment_decoder( Value_decoder ) ), fun(Segments) -> gleam@dynamic@decode:success( {sequence, Self_id, Counter, elements_to_segments( segments_to_elements( Segments ) ), maps:from_list( Forwardings ), Frontier} ) end ) end ) end ) end ) end ) end, fun(State) -> gleam@dynamic@decode:success(State) end ) end, Envelope_decoder = begin gleam@dynamic@decode:field( <<"type"/utf8>>, {decoder, fun gleam@dynamic@decode:decode_string/1}, fun(Type_tag) -> gleam@dynamic@decode:field( <<"v"/utf8>>, {decoder, fun gleam@dynamic@decode:decode_int/1}, fun(Version) -> gleam@dynamic@decode:success({Type_tag, Version}) end ) end ) end, case gleam@json:parse(Json_string, Envelope_decoder) of {error, E} -> {error, E}; {ok, {Type_tag@1, Version@1}} -> case (Type_tag@1 =:= <<"sequence"/utf8>>) andalso (Version@1 =:= 1) of true -> gleam@json:parse(Json_string, State_decoder); false -> {error, {unable_to_decode, [{decode_error, <<"type=sequence and v=1"/utf8>>, <<<