mumble_server_runtime_shard/
plan.rs

1//! Planning a transition, with the scope as part of the element's identity.
2//!
3//! # The one idea in this module
4//!
5//! **The diff's comparison key is `(element, scope)`, not `element`.** It costs
6//! nothing and it deletes a whole family of special cases.
7//!
8//! When a player changes team, their scope goes from `/g7/t3` to `/g7/t2`. That
9//! is not "a field that changed", it is *the entry `(B, /g7/t3)` disappearing and
10//! the entry `(B, /g7/t2)` appearing*. So the ordinary diff produces, on its own:
11//!
12//! ```text
13//! RemoveUser(B)               [scope /g7/t3]
14//! AddUser(B, channel Team2)   [scope /g7/t2]
15//! ```
16//!
17//! and the per-connection filter stays a single branchless test:
18//!
19//! | connection | observes | receives |
20//! |---|---|---|
21//! | teammate still in t3 | `{/g7/t3}` | the `Remove` alone, so B leaves |
22//! | player in t2 | `{/g7/t2}` | the `Add` alone, so B arrives |
23//! | spectator | `{/g7}` | **both**, settled by [`crate::compose::collapse`] |
24//! | player in another game | `{/g8}` | nothing |
25//!
26//! A property falls out for free: a move *within* a scope stays a `MoveUser`,
27//! while a move *between* scopes becomes a departure and an arrival. Which is
28//! semantically exactly right.
29//!
30//! The identifier does **not** change: it is the same person, and the client's
31//! local preferences for them must survive the move. Only the diff's notion of
32//! *sameness* carries the scope.
33//!
34//! # No audio operations
35//!
36//! Audio comes from a separate table whose ordering is guaranteed differently
37//! (guide 9.5), so the plan is purely a sequence of view mutations.
38//!
39//! REF: docs/design/guide-implementation.md 5
40
41use std::collections::{BTreeMap, BTreeSet, HashSet};
42
43use crate::ids::{ChannelId, SessionId};
44use crate::scope::Scope;
45use crate::view::{Channel, Overlay, ShardView, User, UserFlags};
46
47/// A sparse channel change.
48///
49/// Links are carried as two explicit sets rather than as a replacement, because
50/// the client treats a non-empty `links` list as a full replacement but ignores
51/// an empty one entirely. Stating additions and removals separately makes the
52/// patch composable across a replay and removes the need to know what the
53/// connection currently holds.
54///
55/// REF: references/mumble/src/mumble/Messages.cpp : `msgChannelState` handles
56///   `links_remove` and `links_add` in their own blocks, independent of `links`.
57#[derive(Debug, Clone, PartialEq, Eq)]
58pub struct ChannelPatch {
59    pub id: ChannelId,
60    pub parent: Option<ChannelId>,
61    pub name: Option<String>,
62    pub position: Option<i32>,
63    pub can_enter: Option<bool>,
64    pub links_added: BTreeSet<ChannelId>,
65    pub links_removed: BTreeSet<ChannelId>,
66}
67
68impl ChannelPatch {
69    fn empty(id: ChannelId) -> ChannelPatch {
70        ChannelPatch {
71            id,
72            parent: None,
73            name: None,
74            position: None,
75            can_enter: None,
76            links_added: BTreeSet::new(),
77            links_removed: BTreeSet::new(),
78        }
79    }
80
81    #[must_use]
82    pub fn is_noop(&self) -> bool {
83        self.parent.is_none()
84            && self.name.is_none()
85            && self.position.is_none()
86            && self.can_enter.is_none()
87            && self.links_added.is_empty()
88            && self.links_removed.is_empty()
89    }
90}
91
92/// A sparse user change. The channel move is a separate operation, because it
93/// has to be ordered before any channel removal.
94#[derive(Debug, Clone, PartialEq, Eq)]
95pub struct UserPatch {
96    pub session: SessionId,
97    pub name: Option<String>,
98    pub flags: Option<UserFlags>,
99}
100
101impl UserPatch {
102    #[must_use]
103    pub fn is_noop(&self) -> bool {
104        self.name.is_none() && self.flags.is_none()
105    }
106}
107
108/// One view mutation. Not a Mumble message: spelling these on the wire is
109/// [`mod@crate::emit`]'s job.
110#[derive(Debug, Clone, PartialEq, Eq)]
111pub enum PlanOp {
112    CreateChannel(Channel),
113    UpdateChannel(ChannelPatch),
114    AddUser(User),
115    MoveUser {
116        session: SessionId,
117        channel: ChannelId,
118    },
119    UpdateUser(UserPatch),
120    RemoveUser(SessionId),
121    RemoveChannel(ChannelId),
122}
123
124/// What an operation identifies, for [`crate::compose::collapse`].
125#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
126pub enum ElementId {
127    Channel(ChannelId),
128    User(SessionId),
129}
130
131impl PlanOp {
132    /// The element this operation brings into existence, if any.
133    #[must_use]
134    pub fn added(&self) -> Option<ElementId> {
135        match self {
136            PlanOp::CreateChannel(channel) => Some(ElementId::Channel(channel.id)),
137            PlanOp::AddUser(user) => Some(ElementId::User(user.session)),
138            _ => None,
139        }
140    }
141
142    /// The element this operation withdraws, if any.
143    #[must_use]
144    pub fn removed(&self) -> Option<ElementId> {
145        match self {
146            PlanOp::RemoveChannel(channel) => Some(ElementId::Channel(*channel)),
147            PlanOp::RemoveUser(session) => Some(ElementId::User(*session)),
148            _ => None,
149        }
150    }
151
152    /// Whether this operation belongs to the removal phases (P6, P7).
153    ///
154    /// [`crate::compose::splice`] uses this to find where the overlay's
155    /// operations have to be inserted.
156    #[must_use]
157    pub fn is_removal(&self) -> bool {
158        matches!(self, PlanOp::RemoveUser(_) | PlanOp::RemoveChannel(_))
159    }
160}
161
162/// An operation together with the scope that decides who receives it.
163#[derive(Debug, Clone, PartialEq, Eq)]
164pub struct PlannedOp {
165    pub op: PlanOp,
166    /// For a removal this is the scope in the **previous** view: the element no
167    /// longer exists in the new one, so it cannot be read back from there.
168    pub scope: Scope,
169}
170
171/// Plan the transition from `before` to `after`.
172///
173/// The global order carries the ordering invariants:
174///
175/// ```text
176/// P1  CreateChannel      (parents before children)
177/// P2  UpdateChannel
178/// P3  AddUser
179/// P4  MoveUser           (before any removal: no occupied channel is deleted)
180/// P5  UpdateUser
181/// P6  RemoveUser
182/// P7  RemoveChannel      (children before parents)
183/// ```
184#[must_use]
185pub fn plan(before: &ShardView, after: &ShardView) -> Vec<PlannedOp> {
186    let mut creates: Vec<Channel> = Vec::new();
187    let mut updates: Vec<PlannedOp> = Vec::new();
188    let mut adds: Vec<PlannedOp> = Vec::new();
189    let mut moves: Vec<PlannedOp> = Vec::new();
190    let mut user_updates: Vec<PlannedOp> = Vec::new();
191    let mut user_removals: Vec<PlannedOp> = Vec::new();
192    let mut channel_removals: Vec<(ChannelId, Scope)> = Vec::new();
193
194    for (id, new) in &after.channels {
195        match before.channels.get(id) {
196            // Same identity, same scope: an ordinary field-level update.
197            Some(old) if old.scope == new.scope => {
198                let patch = channel_patch(old, new);
199                if !patch.is_noop() {
200                    updates.push(PlannedOp {
201                        op: PlanOp::UpdateChannel(patch),
202                        scope: new.scope,
203                    });
204                }
205            }
206            // Same identity, different scope: a different entry in the diff, so
207            // it departs from the old scope and arrives in the new one.
208            Some(old) => {
209                creates.push(new.clone());
210                channel_removals.push((*id, old.scope));
211            }
212            None => creates.push(new.clone()),
213        }
214    }
215    for (id, old) in &before.channels {
216        if !after.channels.contains_key(id) {
217            channel_removals.push((*id, old.scope));
218        }
219    }
220
221    for (session, new) in &after.users {
222        match before.users.get(session) {
223            Some(old) if old.scope == new.scope => {
224                if old.channel != new.channel {
225                    moves.push(PlannedOp {
226                        op: PlanOp::MoveUser {
227                            session: *session,
228                            channel: new.channel,
229                        },
230                        scope: new.scope,
231                    });
232                }
233                let patch = user_patch(old, new);
234                if !patch.is_noop() {
235                    user_updates.push(PlannedOp {
236                        op: PlanOp::UpdateUser(patch),
237                        scope: new.scope,
238                    });
239                }
240            }
241            Some(old) => {
242                adds.push(PlannedOp {
243                    op: PlanOp::AddUser(new.clone()),
244                    scope: new.scope,
245                });
246                user_removals.push(PlannedOp {
247                    op: PlanOp::RemoveUser(*session),
248                    scope: old.scope,
249                });
250            }
251            None => adds.push(PlannedOp {
252                op: PlanOp::AddUser(new.clone()),
253                scope: new.scope,
254            }),
255        }
256    }
257    for (session, old) in &before.users {
258        if !after.users.contains_key(session) {
259            user_removals.push(PlannedOp {
260                op: PlanOp::RemoveUser(*session),
261                scope: old.scope,
262            });
263        }
264    }
265
266    let mut ops: Vec<PlannedOp> = Vec::new();
267    for channel in order_creations(creates, before) {
268        let scope = channel.scope;
269        ops.push(PlannedOp {
270            op: PlanOp::CreateChannel(channel),
271            scope,
272        });
273    }
274    ops.append(&mut updates);
275    ops.append(&mut adds);
276    ops.append(&mut moves);
277    ops.append(&mut user_updates);
278    ops.append(&mut user_removals);
279    for (id, scope) in order_removals(channel_removals, before) {
280        ops.push(PlannedOp {
281            op: PlanOp::RemoveChannel(id),
282            scope,
283        });
284    }
285    ops
286}
287
288/// Overlay operations, split at the point [`crate::compose::splice`] needs.
289#[derive(Debug, Clone, PartialEq, Eq, Default)]
290pub struct OverlayOps {
291    /// Creations, moves and updates. Spliced **after** the shared additions, so
292    /// they may target a channel that was created in the same turn.
293    pub additions: Vec<PlanOp>,
294    /// Withdrawals. Spliced **before** the shared removals, so they vacate a
295    /// channel that is about to die.
296    pub removals: Vec<PlanOp>,
297}
298
299impl OverlayOps {
300    #[must_use]
301    pub fn is_empty(&self) -> bool {
302        self.additions.is_empty() && self.removals.is_empty()
303    }
304}
305
306/// Plan an overlay transition.
307///
308/// This is the planner without the whole-view checks: an overlay is not a
309/// standalone view, so no root is required. The internal ordering rules are the
310/// same - channels before users on the way in, users before channels on the way
311/// out.
312#[must_use]
313pub fn plan_elements(before: &Overlay, after: &Overlay) -> OverlayOps {
314    let mut creates: Vec<Channel> = Vec::new();
315    let mut additions: Vec<PlanOp> = Vec::new();
316    let mut trailing: Vec<PlanOp> = Vec::new();
317    let mut removals: Vec<PlanOp> = Vec::new();
318    let mut channel_removals: Vec<ChannelId> = Vec::new();
319
320    for (id, new) in &after.channels {
321        match before.channels.get(id) {
322            Some(old) => {
323                let patch = channel_patch(old, new);
324                if !patch.is_noop() {
325                    additions.push(PlanOp::UpdateChannel(patch));
326                }
327            }
328            None => creates.push(new.clone()),
329        }
330    }
331    for id in before.channels.keys() {
332        if !after.channels.contains_key(id) {
333            channel_removals.push(*id);
334        }
335    }
336
337    for (session, new) in &after.users {
338        match before.users.get(session) {
339            Some(old) => {
340                if old.channel != new.channel {
341                    trailing.push(PlanOp::MoveUser {
342                        session: *session,
343                        channel: new.channel,
344                    });
345                }
346                let patch = user_patch(old, new);
347                if !patch.is_noop() {
348                    trailing.push(PlanOp::UpdateUser(patch));
349                }
350            }
351            None => trailing.push(PlanOp::AddUser(new.clone())),
352        }
353    }
354    for session in before.users.keys() {
355        if !after.users.contains_key(session) {
356            removals.push(PlanOp::RemoveUser(*session));
357        }
358    }
359
360    let mut ordered_additions: Vec<PlanOp> = Vec::new();
361    for channel in order_creations(creates, &ShardView::empty()) {
362        ordered_additions.push(PlanOp::CreateChannel(channel));
363    }
364    ordered_additions.append(&mut additions);
365    ordered_additions.append(&mut trailing);
366
367    // Users first so no occupied private channel is withdrawn, then channels
368    // deepest first, using the overlay's own parent relation.
369    let before_channels: BTreeMap<ChannelId, Channel> = before.channels.clone();
370    let mut with_depth: Vec<(ChannelId, u32)> = channel_removals
371        .into_iter()
372        .map(|id| (id, overlay_depth(&before_channels, id)))
373        .collect();
374    with_depth.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0)));
375    removals.extend(
376        with_depth
377            .into_iter()
378            .map(|(id, _)| PlanOp::RemoveChannel(id)),
379    );
380
381    OverlayOps {
382        additions: ordered_additions,
383        removals,
384    }
385}
386
387fn channel_patch(old: &Channel, new: &Channel) -> ChannelPatch {
388    let mut patch = ChannelPatch::empty(new.id);
389    if old.parent != new.parent {
390        patch.parent = Some(new.parent);
391    }
392    if old.name != new.name {
393        patch.name = Some(new.name.clone());
394    }
395    if old.position != new.position {
396        patch.position = Some(new.position);
397    }
398    if old.can_enter != new.can_enter {
399        patch.can_enter = Some(new.can_enter);
400    }
401    patch.links_added = new.links.difference(&old.links).copied().collect();
402    patch.links_removed = old.links.difference(&new.links).copied().collect();
403    patch
404}
405
406fn user_patch(old: &User, new: &User) -> UserPatch {
407    UserPatch {
408        session: new.session,
409        name: (old.name != new.name).then(|| new.name.clone()),
410        flags: (old.flags != new.flags).then_some(new.flags),
411    }
412}
413
414/// Order created channels so a parent always precedes its children.
415///
416/// A parent is either a channel already present in `before` or one created
417/// earlier in this pass. The builder only produces trees, so this terminates;
418/// the fallback exists so a malformed input cannot loop forever, and it only
419/// affects ordering, which the caller has already validated.
420fn order_creations(created: Vec<Channel>, before: &ShardView) -> Vec<Channel> {
421    let mut present: HashSet<ChannelId> = before.channels.keys().copied().collect();
422    let mut remaining: Vec<Channel> = created;
423    let mut ordered: Vec<Channel> = Vec::with_capacity(remaining.len());
424
425    while !remaining.is_empty() {
426        let mut progressed = false;
427        let mut waiting: Vec<Channel> = Vec::new();
428        for channel in remaining {
429            if channel.parent == channel.id || present.contains(&channel.parent) {
430                present.insert(channel.id);
431                ordered.push(channel);
432                progressed = true;
433            } else {
434                waiting.push(channel);
435            }
436        }
437        remaining = waiting;
438        if !progressed {
439            ordered.extend(remaining);
440            break;
441        }
442    }
443    ordered
444}
445
446/// Order removed channels so a child always precedes its parent, using the
447/// previous view's parent relation. Ties break by id, for determinism.
448fn order_removals(removed: Vec<(ChannelId, Scope)>, before: &ShardView) -> Vec<(ChannelId, Scope)> {
449    let mut ordered = removed;
450    ordered.sort_by(|left, right| {
451        depth_in(before, right.0)
452            .cmp(&depth_in(before, left.0))
453            .then(left.0.cmp(&right.0))
454    });
455    ordered
456}
457
458fn depth_in(view: &ShardView, channel: ChannelId) -> u32 {
459    let mut depth = 0u32;
460    let mut current = channel;
461    let mut guard: HashSet<ChannelId> = HashSet::new();
462    while current != ChannelId::ROOT && guard.insert(current) {
463        match view.channels.get(&current) {
464            Some(entry) => {
465                current = entry.parent;
466                depth = depth.saturating_add(1);
467            }
468            None => break,
469        }
470    }
471    depth
472}
473
474fn overlay_depth(channels: &BTreeMap<ChannelId, Channel>, channel: ChannelId) -> u32 {
475    let mut depth = 0u32;
476    let mut current = channel;
477    let mut guard: HashSet<ChannelId> = HashSet::new();
478    while guard.insert(current) {
479        match channels.get(&current) {
480            Some(entry) if entry.parent != current => {
481                current = entry.parent;
482                depth = depth.saturating_add(1);
483            }
484            // Either the parent is a shared channel, or the chain ends here.
485            _ => break,
486        }
487    }
488    depth
489}
mumble_server_runtime_shard/plan.rs

mumble_server_runtime_shard/
plan.rs
