crabidy/architecture/queue-order.md

Queue order: de-duplication and sorting

Context

The queue is an ordered list of tracks the server owns; clients mutate it through RPCs and learn the result from the update stream (docs/src/queue.md). Every existing mutation either adds tracks (Replace/Append/Queue/Insert), drops them (Remove/ClearQueue), or moves the cursor (SetCurrent). Nothing reorders what is already there, and nothing notices that the same track is in the queue twice.

Both gaps show up in ordinary use:

• Queue an artist, then a playlist that contains three of the same tracks, and the queue plays them twice. Today the only fix is spotting the rows and pressing d on each.
• Queue five albums by appending them, and they play in the order they were appended, interleaved by however the provider listed them. There is no way to say "group this by artist" or "shortest first" short of clearing the queue and re-queueing in a different order.

So: two new queue-order operations — dedup (drop duplicate entries) and sort (reorder by a strategy) — for every client, without re-resolving anything through providers.

Assumptions

• A1 — The server owns queue state; clients ask and then observe. Same rule as architecture/seek.md A2 and architecture/mpris.md A2: a client sends the operation, the playback loop performs it, and the resulting Queue snapshot is the truth. No client predicts the new order.
• A2 — Order is queue state, shuffle is a modifier. tracks is the queue order (what every client renders, and what playback follows with shuffle off); play_order is the play order shuffle permutes. Dedup and sort rewrite the former. They are not new modifiers: nothing about them is remembered, they are one-shot rewrites, and after one runs the queue is just a queue in a different order.
• A3 — Both work on metadata already in the queue. Track carries path, artist, title, album, duration and provider_item_id; no provider round trip, no network, no new provider trait method.
• A4 — The current track keeps playing. Neither operation interrupts audio: dedup never removes the playing track, sort never restarts it. The playing track's position changes, which the existing QueueTrack broadcast already covers.
• A5 — A queue can be long. Ten thousand entries after queueing a large artist is normal (architecture/progressive-queueing.md), so both operations must be O(n log n) with keys computed once per track, not per comparison, and must not hold the queue lock across an await.

Options considered

Where the operations run

Option A — client-side, on top of the existing RPCs. A client already holds the full Queue snapshot, so it could find duplicate positions itself and send Remove. Sorting would mean sending Replace with the paths in the new order — which re-resolves every path through its provider (slow, and a provider that has since changed its listing returns something else), loses the playing track (a replace restarts playback at the head), and would make each client reimplement the comparators. And the Remove positions are computed from a snapshot that a still-running resolve can invalidate before the request lands.

Option B — server-side RPCs (chosen). Both run on the playback loop, the single writer of queue state: atomic against resolve chunks and against other clients, no re-resolution, the current track is identified by index and not by re-lookup, and the result reaches every client (and the persister) through the one broadcast site that already exists.

Option C — a general ReorderQueue(permutation) RPC. The client decides the order and the server applies it; sort strategies would then be a purely client-side concern, and the same RPC would later serve drag-and-drop and "move this track up". More general, but a permutation is an argument about positions, and positions shift under a running resolve — a stale permutation is not merely a no-op, it scrambles the queue. It also puts five comparators in every client. Kept as Deferred: a move/reorder RPC wants a different argument shape (identify rows by path, not index) and is its own feature.

Decision: Option B. Two RPCs, DedupQueue and SortQueue, handled on the playback loop like every other queue verb.

What counts as a duplicate

1. Same path. Exactly the same library entry queued twice.
2. Same provider item — provider_item_id scoped to its provider, with path as the fallback when the id is empty. Catches the same track reached by two routes: through an album, through a playlist, through a search result.
3. Same artist and title, normalized. Would also catch the same song from two different providers.

Decision: 2 by default, falling back to 1 (D3) — and 3 behind an explicit flag (D3a). 3 cannot be the default: identical artist/title is routinely a different recording — a live take, a remaster, a radio edit, the studio version — and the server cannot tell which, so a default that merged them would silently and unrecoverably edit the queue, with the false positives landing exactly on the collections (greatest-hits, live albums, remix albums) where a user is most deliberate. But it is what a listener sometimes means, so it is reachable in one keypress and never by accident.

Decisions

• D1 — Two RPCs, both QueueOwner. DedupQueue and SortQueue mutate the queue, so they sit with Remove/ClearQueue/SetCurrent in the rights matrix (architecture/roles-auth.md), not with the one appender verb. The pinned method-list test in auth.rs keeps a new RPC from reaching the wire unmapped.
• D2 — DedupQueue answers with a count. Every other queue verb answers with an empty message because the update stream carries the truth. Dedup is the exception: "how many did that remove?" cannot be recovered from the new snapshot (a client would have to diff against a snapshot it may never have had), and 0 is the answer a user most needs — it says there were no duplicates, as opposed to nothing happened. So DedupQueueResponse.removed, produced on the loop and returned through a bounded result channel, the way SaveQueue already reports. SortQueueResponse stays empty: the new order is the answer, and it arrives on the stream.
• D3 — The default duplicate identity is (provider, provider_item_id), or the whole path. The provider is the first path segment; ids are provider-internal (the content store keys them the same way, by_provider_id(provider, id)), so leaving them unscoped would let two providers' numeric ids collide and merge two unrelated tracks. When the id is empty — most providers, and every local file — the key is the full path, which is exact. The consequence worth stating: a captured copy under /crabidy and its streaming original are not duplicates, because they are different providers. Conservative on purpose: a missed duplicate is a keypress, a wrong merge is lost queue state.
• D3a — …and an opt-in by_title identity beside it. Measured against a real queue, D3 alone removed nothing from 121 entries — every entry was a distinct provider item — while the user saw duplicates: four "Referees Don't Fall In Love", three "Sink Into The Hips". They were remixes, edits and album versions of the same songs, which D3 is right to keep and which a listener may still not want three of. So DedupQueue takes a flag: with by_title the identity is the lowercased (artist, title) pair, and the survivor of a group is the longest take (the full version rather than a radio edit), still yielding to the playing entry. It stays opt-in and on its own key, because it discards recordings that differ — the exact loss D3 refuses to make the default. Duration-tolerant matching was the third option and is not worth its complexity: on the queue that motivated this, every same-title group differed by tens of seconds, so any tolerance narrow enough to be safe caught nothing.
• D4 — The survivor is the current track, else the earliest. Within a group of duplicates, the entry at the current position survives if it is in the group; otherwise the earliest one does, and every later copy goes. "Keep the first" alone would remove the playing track whenever the playing copy was a later one — a dedup that stops the music is a bug, not a policy (A4).
• D5 — Dedup is expressed as a removal. It computes the positions to drop and hands them to QueueManager::remove_tracks, which already maintains play_order, shifts current_offset, and ignores out-of-range positions. Since the current track is never in that list, remove_tracks reports no successor to start and playback is untouched — the same code path a client's d takes, so there is one removal implementation, not two.
• D6 — Five sort strategies, on a proto enum. ARTIST, ALBUM, TITLE, DURATION and REVERSE, plus a descending flag. UNSPECIFIED (the proto3 default, i.e. a client that forgot the field) is InvalidArgument, never a silent default. REVERSE reverses the order the queue is in and ignores descending — it is not a key, and reversing descendingly is the same thing.
• D7 — The sort is stable, and the keys are compound. ARTIST sorts by (artist, album) and ALBUM by (album) alone; within an equal key, queue order survives — which for a queued album is its track order, and is much closer to what a user means than sorting an album's tracks alphabetically by title. A stable sort is what makes "sort by album, then by artist" compose across two presses, too.
• D8 — Unknown sorts last, in both directions. An empty artist/album/ title and an absent duration go to the end ascending and descending. A length-less web radio stream is not "the longest track", and a missing album is not alphabetically first. One rule for every key, so a user never has to remember which end the blanks pile up at.
• D9 — Text comparison is case-insensitive and locale-naive. Keys are lowercased once per track (decorate–sort–undecorate, A5), then compared as Unicode strings. No collation, no article stripping: "The Beatles" sorts under T. Locale-aware collation would need a collation library and a locale the server does not have (it has no user, only clients); doing it half-way — special-casing English articles — would be wrong for every other language in a music library.
• D10 — Sorting reorders tracks; what plays next depends on shuffle. With shuffle off, play_order is rebuilt as the identity over the new order and current_offset follows the current track: the queue order is the play order, so a sort changes what plays next — the point of sorting. With shuffle on, play_order is remapped through the sort permutation, so the shuffled play sequence and the position within it are preserved exactly: the user asked for a random order, and sorting the display must not silently reshuffle. Either way the current track stays current and keeps playing (A4).
• D11 — Both are legal while a resolve is in flight, and neither waits for it. They apply to what the queue holds at that moment; chunks still being resolved land afterwards at their insert index or at the end, unsorted. Refusing (FailedPrecondition) would make both operations flaky exactly on the big queues that need them, and waiting would block the loop. Clients already render the resolving indicator, so "more is still arriving" is visible; a second press settles the rest.
• D12 — Both persist through the existing broadcast site. broadcast_queue hands the snapshot to the persister and to the stream, so a dedup or a sort survives a server restart with no new persistence code (architecture/queue-persistence.md).
• D13 — Pure key logic lives in its own module. queue_order.rs holds the duplicate key, the sort keys, and the permutation — no state, no locks, unit-testable directly. QueueManager::dedup/sort keep the play_order/current_offset bookkeeping, because that invariant is theirs. The split is what keeps D3/D7/D8 testable as data instead of through a queue.
• D14 — TUI: u dedups, U dedups by title, S opens a sort menu. u is "unique" and is free in the queue scope; the shifted form is the shifted behaviour (D3a), which is the pattern w/W and c/C already use here for "the same verb, more of it". Sorting needs a choice, so S opens a modal overlay listing the five strategies with their letters (a artist, l album, t title, d duration, r reverse; the capital of each sorts descending), Esc closes. A menu rather than a chord sequence: the strategies are discoverable in the overlay instead of only in the help modal, and the app already has three modal overlays (help, input, search) to follow. It is modal in the same strict sense — while it is open, the bindings table is unreachable.
• D15 — The dedup count is reported in the queue pane's title, briefly. Queue — removed 7 duplicates, for a few seconds, then back to normal. The title already multiplexes VISUAL, the / query and the register count, so no layout changes and no new region; and the message is queue-scoped, which is where the user is looking after pressing u. The count travels as a typed MessageToUi variant, not a preformatted string — the wording is the UI layer's business.
• D16 — The web client keeps the same keys and adds the two buttons a mouse needs. u dedups and S opens the sort menu as a dialog, because the keymap is deliberately the TUI's (architecture/web-client.md); the menu's rows are clickable as well as typeable. The queue toolbar gains a sort button that opens that same dialog and a dedup button — without them both operations would be invisible to a mouse, and routing the button through the same menu keeps the strategy list in exactly one place (a second widget listing five strategies is a second thing to keep in step). The dedup count goes to the existing toast rather than a pane title.
• D17 — CLI: cbd queue dedup and cbd queue sort <key> [--desc]. The strategy is a clap ValueEnum, so the shell completes it and a typo is a parse error rather than an InvalidArgument round trip. dedup prints the count it got back (D2).

Structure

direction: right

clients: Clients {
  tui: cbd-tui\nu / S menu
  web: cbd-web\nu / S / select
  cli: cbd queue\ndedup / sort
}

rpc: gRPC (QueueOwner) {
  dedup: DedupQueue\n-> removed: u32
  sort: SortQueue\n(strategy, descending)
}

loop: playback loop\n(single writer) {
  cmd: PlaybackCommand\nDedupQueue / SortQueue
  qm: QueueManager\ntracks + play_order
  keys: queue_order\nduplicate key, sort keys
}

out: One broadcast site {
  stream: Queue update\n(every client)
  persist: persister\n(latest wins)
}

clients.tui -> rpc.dedup
clients.web -> rpc.dedup
clients.cli -> rpc.dedup
clients.cli -> rpc.sort
clients.tui -> rpc.sort
clients.web -> rpc.sort
rpc.dedup -> loop.cmd
rpc.sort -> loop.cmd
loop.cmd -> loop.qm: mutate
loop.qm -> loop.keys: keys / permutation
loop.qm -> out.stream
loop.qm -> out.persist
rpc.dedup -> clients.cli: removed count

The sort's effect on the two orders (D10) — the same permutation, applied differently depending on shuffle:

shape: sequence_diagram

client: client
loop: playback loop
off: QueueManager\nshuffle off
on: QueueManager\nshuffle on
stream: update stream

client -> loop: SortQueue(ARTIST, asc)
loop -> off: sort(ARTIST, asc)
off -> off: tracks := sorted
off -> off: play_order := identity
off -> off: offset := the current track's new index
loop -> on: sort(ARTIST, asc)
on -> on: tracks := sorted
on -> on: play_order := remapped through the permutation
on -> on: offset unchanged
off -> stream: Queue (new order, new position)
on -> stream: Queue (new order, new position)
loop -> client: SortQueueResponse {}

Boundaries

• crabidy-server::queue_order — pure functions: the duplicate key of a track, the sort key of a track, and the permutation for a strategy. Knows nothing about locks, play order or clients.
• crabidy-server::QueueManager — gains dedup() and sort(). Owns the play_order/current_offset invariants; dedup delegates the actual removal to remove_tracks (D5).
• crabidy-server::playback — two new PlaybackCommand arms, each a lock–mutate–broadcast on the loop. DedupQueue carries a result channel for the count.
• crabidy-server::rpc / auth — the two methods, their argument validation (UNSPECIFIED → InvalidArgument), and their row in the rights matrix.
• Clients (cbd-tui, cbd-web, cbd-cli) — bindings/commands, the sort-menu modal, and rendering the count. No client computes an order.
• Unchanged: providers, the content store, the resolve pipeline, and every existing queue RPC.

Risks

• A pending insert's index goes stale. Dedup shifts positions and sort moves everything, so the remaining chunks of an in-flight InsertAt op land somewhere else than the user pointed at. This is pre-existing — a plain Remove while resolving does the same — and bounded by D11's "settle it with a second press", but it is real.
• Dedup is per-provider (D3), so the obvious cross-provider duplicate — a captured track and its streaming source — stays. It is the conservative end of a trade-off, and it will read as a bug to someone.
• A sort with shuffle on changes nothing audible (D10) and may look broken. The clients show shuffle state, and the queue visibly reorders.
• Very large queues copy their tracks once per sort. A Vec<Track> permutation on ten thousand tracks is a handful of milliseconds on the loop; well under the loop's other work (a resolve chunk), but it is work done while no other command is served.

Deferred

• A preview for by_title (D3a): a confirmation view listing which recording of each song would survive, so the aggressive identity can be inspected before it removes anything rather than only undone by re-queueing.
• ReorderQueue/move: drag-and-drop in the web client and K/J row moves in the TUI, on an RPC that identifies rows by path rather than index (Option C).
• Sort by release year. Album.release_date is a provider string and not always ISO 8601, so a year needs the same parse-or-drop treatment the TUI notification does; worth doing once that parse lives somewhere shared.
• A remembered sort ("keep the queue sorted by artist as tracks arrive") — a modifier, which is a different feature from a one-shot rewrite (A2), and one that fights progressive queueing.
• Sort within a marked range only, the visual-mode analogue of a partial sort.