mumble_server_runtime_shard/
build.rs

1//! The render builder: the only way a flavor produces a view.
2//!
3//! # Why an incoherent view is not expressible
4//!
5//! [`ShardBuilder::channel`] demands a parent and [`ShardBuilder::user`] demands
6//! a channel; in both cases the scope is *derived* from the parent's through
7//! [`Narrow`], which can only extend. There is no free scope parameter anywhere.
8//! That is what turns the closure property of [`crate::scope`] from something to
9//! validate into something to rely on: a user is always at or below its
10//! channel's scope, so any observer who sees the user also sees the channel.
11//!
12//! The one thing that does not follow the hierarchy is a link between channels,
13//! and it is therefore the one structural check in the model.
14//!
15//! # What `finish` still has to check
16//!
17//! Three properties are not structural, and each one is a real failure mode:
18//!
19//! - **Shared xor private** (guide 3.4). Without it the shared view would say
20//!   "admin in /g7/staff" while an overlay says "admin in A's channel", and the
21//!   next shared delta would move the admin without the overlay reasserting
22//!   itself. The client would drift silently, which is the worst class of bug
23//!   this design can produce.
24//! - **An overlay only references what its connection can already see**
25//!   (guide 6.6). One lookup per overlay element forbids, in one stroke, placing
26//!   someone in a channel that is about to vanish, in a channel that connection
27//!   cannot see, or referencing a session that does not exist.
28//! - **A receiver sees its sender** (guide 1.2). This is not a design choice: the
29//!   Mumble client discards audio whose sender session it does not know, so an
30//!   edge into a blind receiver is silence with extra steps.
31//!
32//! REF: docs/design/guide-implementation.md 3
33
34use std::collections::{BTreeMap, BTreeSet};
35
36use thiserror::Error;
37
38use crate::ids::{
39    ActionKey, ChannelId, ChannelKey, ConnectionId, Exhausted, Occupant, SessionId, ShardId,
40    SharedIds,
41};
42use crate::routing::{AudioRelation, DomainId};
43use crate::scope::{Scope, ScopeSet};
44use crate::view::{Action, Actions, Channel, On, Overlay, ShardView, User, UserFlags};
45
46/// How many context actions one connection may be offered in a single render.
47///
48/// A bound rather than a taste: the whole turn goes into the connection's queue
49/// in one piece, and a queue that refuses an oversized batch closes the
50/// connection. Refusing the render is the failure that stays inside the flavor's
51/// own bug.
52pub const MAX_ACTIONS: usize = 64;
53
54/// How a child's scope relates to its parent's.
55///
56/// There is no "widen" variant, and that absence is the whole safety argument.
57#[derive(Debug, Clone, Copy, PartialEq, Eq)]
58pub enum Narrow {
59    /// Same scope as the parent.
60    Same,
61    /// The parent's scope, extended by one segment.
62    Into(u32),
63}
64
65/// A handle to a channel placed in this render.
66#[derive(Debug, Clone, Copy, PartialEq, Eq)]
67pub struct ChannelRef {
68    id: ChannelId,
69    scope: Scope,
70}
71
72impl ChannelRef {
73    #[must_use]
74    pub fn id(self) -> ChannelId {
75        self.id
76    }
77
78    #[must_use]
79    pub fn scope(self) -> Scope {
80        self.scope
81    }
82}
83
84/// A handle to a user placed in this render.
85#[derive(Debug, Clone, Copy, PartialEq, Eq)]
86pub struct UserRef {
87    session: SessionId,
88}
89
90impl UserRef {
91    #[must_use]
92    pub fn session(self) -> SessionId {
93        self.session
94    }
95}
96
97/// Why a render was refused.
98///
99/// A refused render keeps the previous view and does not close any connection
100/// (guide 11.7): the committed view is still correct, and reconnecting would
101/// only reproduce the same broken render.
102#[derive(Debug, Clone, PartialEq, Eq, Error)]
103pub enum BuildError {
104    #[error("the render never called `root`, so nothing anchors its channels")]
105    MissingRoot,
106
107    #[error("`root` was called twice; a shard renders one tree")]
108    DuplicateRoot,
109
110    #[error("channel key {0:?} was rendered twice in one turn")]
111    DuplicateChannelKey(ChannelKey),
112
113    #[error("occupant {0:?} was rendered twice in one turn")]
114    DuplicateOccupant(Occupant),
115
116    #[error(
117        "narrowing past the maximum scope depth: {context}. Widening instead would hand this \
118         element its parent's visibility"
119    )]
120    ScopeTooDeep { context: String },
121
122    #[error(transparent)]
123    Exhausted(#[from] Exhausted),
124
125    #[error(
126        "channel {a:?} is linked to {b:?}, whose scope is not comparable: a link to a channel the \
127         viewer may not see has no meaning"
128    )]
129    LinkAcrossScopes { a: ChannelId, b: ChannelId },
130
131    #[error(
132        "session {session:?} is in the shared view and in connection {connection:?}'s overlay; an \
133         element is shared xor private, never merged"
134    )]
135    SharedAndPrivateUser {
136        session: SessionId,
137        connection: ConnectionId,
138    },
139
140    #[error(
141        "channel {channel:?} is in the shared view and in connection {connection:?}'s overlay; an \
142         element is shared xor private, never merged"
143    )]
144    SharedAndPrivateChannel {
145        channel: ChannelId,
146        connection: ConnectionId,
147    },
148
149    #[error(
150        "connection {connection:?}'s overlay places a user in channel {channel:?}, which is not in \
151         the shared view after this render nor in its own overlay"
152    )]
153    OverlayChannelMissing {
154        connection: ConnectionId,
155        channel: ChannelId,
156    },
157
158    #[error(
159        "connection {connection:?}'s overlay places a user in channel {channel:?}, which that \
160         connection cannot see"
161    )]
162    OverlayChannelInvisible {
163        connection: ConnectionId,
164        channel: ChannelId,
165    },
166
167    #[error(
168        "connection {connection:?} is offered more than {MAX_ACTIONS} context actions, which would \
169         not fit in one transition"
170    )]
171    TooManyActions { connection: ConnectionId },
172
173    #[error(
174        "audio edge {sender:?} -> {receiver:?} would be discarded: the receiver cannot see the \
175         sender, and the client drops audio from a session it does not know"
176    )]
177    ReceiverCannotSeeSender {
178        sender: ConnectionId,
179        receiver: ConnectionId,
180    },
181}
182
183/// Everything one render produced.
184#[derive(Debug, Clone, PartialEq, Eq)]
185pub struct Rendered {
186    pub view: ShardView,
187    pub overlays: BTreeMap<ConnectionId, Overlay>,
188    /// What each connection is offered. Never journalled, for the same reason an
189    /// overlay is not: it is recomputed per connection every turn.
190    pub actions: BTreeMap<ConnectionId, Actions>,
191    pub audio: AudioRelation,
192}
193
194/// The uniform constructor handed to [`crate::shard::ShardLogic::render`].
195///
196/// Every method that can fail records the refusal and carries on rather than
197/// returning a `Result` the flavor would have to thread through its whole
198/// render. The refusal is not lost: [`ShardBuilder::finish`] returns it and the
199/// render is discarded whole. Handles returned after a refusal are meaningless,
200/// which is harmless precisely because nothing built on them will be published.
201pub struct ShardBuilder<'a> {
202    ids: &'a SharedIds,
203    /// Namespaces this render's channel keys. Two shards may use the same key
204    /// for two different channels, and they must not collide on the wire.
205    shard: ShardId,
206    connections: &'a [ConnectionId],
207    view: ShardView,
208    overlays: BTreeMap<ConnectionId, Overlay>,
209    actions: BTreeMap<ConnectionId, Actions>,
210    audio: AudioRelation,
211    keys_seen: BTreeSet<ChannelKey>,
212    occupants_seen: BTreeSet<Occupant>,
213    rooted: bool,
214    /// First refusal wins. Listing the rest would buy nothing: the render is
215    /// discarded whole, so a flavor fixes them one at a time regardless.
216    error: Option<BuildError>,
217}
218
219impl<'a> ShardBuilder<'a> {
220    #[must_use]
221    pub fn new(
222        ids: &'a SharedIds,
223        shard: ShardId,
224        connections: &'a [ConnectionId],
225    ) -> ShardBuilder<'a> {
226        ShardBuilder {
227            ids,
228            shard,
229            connections,
230            view: ShardView::empty(),
231            overlays: BTreeMap::new(),
232            actions: BTreeMap::new(),
233            audio: AudioRelation::default(),
234            keys_seen: BTreeSet::new(),
235            occupants_seen: BTreeSet::new(),
236            rooted: false,
237            error: None,
238        }
239    }
240
241    /// The connections attached to this shard, for overlay loops.
242    #[must_use]
243    pub fn connections(&self) -> &[ConnectionId] {
244        self.connections
245    }
246
247    /// The root of this shard's tree: what every observer sees.
248    pub fn root(&mut self, name: &str) -> ChannelRef {
249        if self.rooted {
250            self.fail(BuildError::DuplicateRoot);
251            return ChannelRef {
252                id: ChannelId::ROOT,
253                scope: Scope::ROOT,
254            };
255        }
256        self.rooted = true;
257
258        self.view.channels.insert(
259            ChannelId::ROOT,
260            Channel {
261                key: ChannelKey::ROOT,
262                id: ChannelId::ROOT,
263                parent: ChannelId::ROOT,
264                scope: Scope::ROOT,
265                name: name.to_owned(),
266                position: 0,
267                can_enter: true,
268                can_text: true,
269                links: BTreeSet::new(),
270            },
271        );
272        ChannelRef {
273            id: ChannelId::ROOT,
274            scope: Scope::ROOT,
275        }
276    }
277
278    /// A child channel. `narrow` can only extend the parent's scope.
279    pub fn channel(
280        &mut self,
281        parent: ChannelRef,
282        key: ChannelKey,
283        name: &str,
284        narrow: Narrow,
285    ) -> ChannelRef {
286        let Some(scope) = self.narrowed(parent.scope, narrow, || format!("channel {name:?}"))
287        else {
288            return parent;
289        };
290        if !self.keys_seen.insert(key) {
291            self.fail(BuildError::DuplicateChannelKey(key));
292            return parent;
293        }
294        let id = match self.ids.channel(self.shard, key) {
295            Ok(id) => id,
296            Err(exhausted) => {
297                self.fail(BuildError::Exhausted(exhausted));
298                return parent;
299            }
300        };
301
302        self.view.channels.insert(
303            id,
304            Channel {
305                key,
306                id,
307                parent: parent.id,
308                scope,
309                name: name.to_owned(),
310                position: 0,
311                can_enter: true,
312                can_text: true,
313                links: BTreeSet::new(),
314            },
315        );
316        ChannelRef { id, scope }
317    }
318
319    /// A user in a channel. `narrow` can only extend the channel's scope.
320    pub fn user(
321        &mut self,
322        channel: ChannelRef,
323        who: Occupant,
324        name: &str,
325        narrow: Narrow,
326    ) -> UserRef {
327        let scope = self
328            .narrowed(channel.scope, narrow, || format!("user {name:?}"))
329            .unwrap_or(channel.scope);
330        let session = match self.ids.session(who) {
331            Ok(session) => session,
332            Err(exhausted) => {
333                self.fail(BuildError::Exhausted(exhausted));
334                // The scope is already refused; any session works for the
335                // handle since finish will discard the whole render.
336                SessionId(0)
337            }
338        };
339        if !self.occupants_seen.insert(who) {
340            self.fail(BuildError::DuplicateOccupant(who));
341            return UserRef { session };
342        }
343
344        self.view.users.insert(
345            session,
346            User {
347                occupant: who,
348                session,
349                channel: channel.id,
350                scope,
351                name: name.to_owned(),
352                flags: UserFlags::default(),
353            },
354        );
355        UserRef { session }
356    }
357
358    pub fn channel_position(&mut self, channel: ChannelRef, position: i32) {
359        if let Some(entry) = self.view.channels.get_mut(&channel.id) {
360            entry.position = position;
361        }
362    }
363
364    pub fn channel_can_enter(&mut self, channel: ChannelRef, yes: bool) {
365        if let Some(entry) = self.view.channels.get_mut(&channel.id) {
366            entry.can_enter = yes;
367        }
368    }
369
370    /// Whether text may be addressed to this channel.
371    ///
372    /// Declaring it false greys the client's chat box out for that channel
373    /// instead of letting the user type into something that answers
374    /// `PermissionDenied`, and the shard refuses a message aimed there anyway.
375    pub fn channel_can_text(&mut self, channel: ChannelRef, yes: bool) {
376        if let Some(entry) = self.view.channels.get_mut(&channel.id) {
377            entry.can_text = yes;
378        }
379    }
380
381    /// Link two channels, symmetrically.
382    ///
383    /// The only structural check in the model, because a link is the one
384    /// relation that does not follow the parent hierarchy: a link pointing at a
385    /// channel the viewer may not see has no meaning.
386    pub fn channel_link(&mut self, a: ChannelRef, b: ChannelRef) {
387        if !a.scope.comparable(b.scope) {
388            self.fail(BuildError::LinkAcrossScopes { a: a.id, b: b.id });
389            return;
390        }
391        if let Some(entry) = self.view.channels.get_mut(&a.id) {
392            entry.links.insert(b.id);
393        }
394        if let Some(entry) = self.view.channels.get_mut(&b.id) {
395            entry.links.insert(a.id);
396        }
397    }
398
399    pub fn user_flags(&mut self, user: UserRef, flags: UserFlags) {
400        if let Some(entry) = self.view.users.get_mut(&user.session) {
401            entry.flags = flags;
402        }
403    }
404
405    /// Elements visible to this connection only.
406    pub fn private(&mut self, connection: ConnectionId, build: impl FnOnce(&mut PrivateBuilder)) {
407        let mut private = PrivateBuilder {
408            ids: self.ids,
409            shard: self.shard,
410            connection,
411            overlay: self.overlays.entry(connection).or_default(),
412            actions: self.actions.entry(connection).or_default(),
413            error: &mut self.error,
414        };
415        build(&mut private);
416    }
417
418    /// A symmetric group: everyone in the domain hears everyone else.
419    pub fn audio_domain(&mut self, domain: DomainId, members: &[ConnectionId]) {
420        self.audio.domain(domain, members);
421    }
422
423    /// A one-way exception: hears the domain, is not heard by it.
424    pub fn audio_listen(&mut self, listener: ConnectionId, domain: DomainId) {
425        self.audio.listen(listener, domain);
426    }
427
428    /// A single directed edge, for full generality.
429    pub fn audio_edge(&mut self, sender: ConnectionId, receiver: ConnectionId) {
430        self.audio.edge(sender, receiver);
431    }
432
433    /// Close the render, checking the three non-structural properties.
434    ///
435    /// `observations` is what each attached connection observes of the shared
436    /// view; it is needed for the overlay and audio checks, both of which are
437    /// statements about who can see what.
438    ///
439    /// # Errors
440    ///
441    /// The first [`BuildError`] recorded during the render, or the first one the
442    /// closing checks find.
443    pub fn finish(
444        self,
445        observations: &BTreeMap<ConnectionId, ScopeSet>,
446    ) -> Result<Rendered, BuildError> {
447        if let Some(error) = self.error {
448            return Err(error);
449        }
450        if !self.rooted {
451            return Err(BuildError::MissingRoot);
452        }
453
454        check_shared_xor_private(&self.view, &self.overlays)?;
455        check_overlay_references(&self.view, &self.overlays, observations)?;
456        check_receivers_see_senders(&self.view, &self.overlays, &self.audio, observations)?;
457
458        Ok(Rendered {
459            view: self.view,
460            overlays: self.overlays,
461            actions: self.actions,
462            audio: self.audio,
463        })
464    }
465
466    /// Apply a [`Narrow`], recording a refusal past the depth bound.
467    fn narrowed(
468        &mut self,
469        parent: Scope,
470        narrow: Narrow,
471        context: impl FnOnce() -> String,
472    ) -> Option<Scope> {
473        match narrow {
474            Narrow::Same => Some(parent),
475            Narrow::Into(segment) => match parent.child(segment) {
476                Some(scope) => Some(scope),
477                None => {
478                    self.fail(BuildError::ScopeTooDeep { context: context() });
479                    None
480                }
481            },
482        }
483    }
484
485    fn fail(&mut self, error: BuildError) {
486        self.error.get_or_insert(error);
487    }
488}
489
490/// The constructor for one connection's private elements.
491pub struct PrivateBuilder<'a> {
492    ids: &'a SharedIds,
493    shard: ShardId,
494    connection: ConnectionId,
495    overlay: &'a mut Overlay,
496    actions: &'a mut Actions,
497    error: &'a mut Option<BuildError>,
498}
499
500impl PrivateBuilder<'_> {
501    /// Place a user in a channel, visible to this connection only.
502    ///
503    /// The channel is one this connection can already see - which
504    /// [`ShardBuilder::finish`] verifies rather than assumes.
505    pub fn user_in(&mut self, channel: ChannelRef, who: Occupant, name: &str) -> UserRef {
506        let session = match self.ids.session(who) {
507            Ok(session) => session,
508            Err(exhausted) => {
509                self.error.get_or_insert(BuildError::Exhausted(exhausted));
510                SessionId(0)
511            }
512        };
513
514        self.overlay.users.insert(
515            session,
516            User {
517                occupant: who,
518                session,
519                channel: channel.id,
520                // Private elements are never scope-filtered; carrying the
521                // channel's scope keeps the type uniform and lets the closing
522                // checks compare without a special case.
523                scope: channel.scope,
524                name: name.to_owned(),
525                flags: UserFlags::default(),
526            },
527        );
528        UserRef { session }
529    }
530
531    /// A channel visible to this connection only.
532    pub fn channel(&mut self, parent: ChannelRef, key: ChannelKey, name: &str) -> ChannelRef {
533        let id = match self.ids.channel(self.shard, key) {
534            Ok(id) => id,
535            Err(exhausted) => {
536                self.error.get_or_insert(BuildError::Exhausted(exhausted));
537                return parent;
538            }
539        };
540
541        self.overlay.channels.insert(
542            id,
543            Channel {
544                key,
545                id,
546                parent: parent.id,
547                scope: parent.scope,
548                name: name.to_owned(),
549                position: 0,
550                can_enter: true,
551                can_text: true,
552                links: BTreeSet::new(),
553            },
554        );
555        ChannelRef {
556            id,
557            scope: parent.scope,
558        }
559    }
560
561    pub fn user_flags(&mut self, user: UserRef, flags: UserFlags) {
562        if let Some(entry) = self.overlay.users.get_mut(&user.session) {
563            entry.flags = flags;
564        }
565    }
566
567    /// Offer this connection a context action: a button that is not a channel to
568    /// double-click.
569    ///
570    /// Declared like everything else, and withdrawn by simply not declaring it
571    /// again. The flavor never emits a message; the difference with what this
572    /// connection was already offered is what travels.
573    ///
574    /// Offering the same key twice in one render is the last call winning, which
575    /// is the same rule a flavor already gets from rendering a user twice.
576    pub fn action(&mut self, key: ActionKey, text: &str, on: On) {
577        if self.actions.len() >= MAX_ACTIONS && !self.actions.contains_key(&key) {
578            self.error.get_or_insert(BuildError::TooManyActions {
579                connection: self.connection,
580            });
581            return;
582        }
583        self.actions.insert(
584            key,
585            Action {
586                key,
587                text: text.to_owned(),
588                on,
589            },
590        );
591    }
592}
593
594/// Guide 3.4: nothing is both shared and private.
595fn check_shared_xor_private(
596    view: &ShardView,
597    overlays: &BTreeMap<ConnectionId, Overlay>,
598) -> Result<(), BuildError> {
599    for (connection, overlay) in overlays {
600        if let Some(session) = overlay
601            .users
602            .keys()
603            .find(|session| view.users.contains_key(session))
604        {
605            return Err(BuildError::SharedAndPrivateUser {
606                session: *session,
607                connection: *connection,
608            });
609        }
610        if let Some(channel) = overlay
611            .channels
612            .keys()
613            .find(|channel| view.channels.contains_key(channel))
614        {
615            return Err(BuildError::SharedAndPrivateChannel {
616                channel: *channel,
617                connection: *connection,
618            });
619        }
620    }
621    Ok(())
622}
623
624/// Guide 6.6: an overlay only references what its connection can already see.
625fn check_overlay_references(
626    view: &ShardView,
627    overlays: &BTreeMap<ConnectionId, Overlay>,
628    observations: &BTreeMap<ConnectionId, ScopeSet>,
629) -> Result<(), BuildError> {
630    for (connection, overlay) in overlays {
631        let see = observations
632            .get(connection)
633            .copied()
634            .unwrap_or(ScopeSet::NONE);
635
636        for user in overlay.users.values() {
637            if overlay.channels.contains_key(&user.channel) {
638                continue;
639            }
640            let Some(channel) = view.channels.get(&user.channel) else {
641                return Err(BuildError::OverlayChannelMissing {
642                    connection: *connection,
643                    channel: user.channel,
644                });
645            };
646            if !see.sees(channel.scope) {
647                return Err(BuildError::OverlayChannelInvisible {
648                    connection: *connection,
649                    channel: user.channel,
650                });
651            }
652        }
653
654        for channel in overlay.channels.values() {
655            if overlay.channels.contains_key(&channel.parent) {
656                continue;
657            }
658            let Some(parent) = view.channels.get(&channel.parent) else {
659                return Err(BuildError::OverlayChannelMissing {
660                    connection: *connection,
661                    channel: channel.parent,
662                });
663            };
664            if !see.sees(parent.scope) {
665                return Err(BuildError::OverlayChannelInvisible {
666                    connection: *connection,
667                    channel: channel.parent,
668                });
669            }
670        }
671    }
672    Ok(())
673}
674
675/// Guide 1.2: every audio edge lands on a receiver that can see the sender.
676///
677/// Not a design choice. The Mumble client looks the sender session up before
678/// buffering a voice frame and discards the frame when the lookup fails.
679///
680/// REF: references/mumble/src/mumble/ServerHandler.cpp : `handleVoicePacket`
681///   buffers only when `ClientUser::get(audioData.senderSession)` succeeds.
682/// # Why this is not a loop over pairs
683///
684/// The obvious form - resolve the relation to its edges and test each one - is
685/// quadratic in a domain's size, and it runs on **every** render even when
686/// nothing about the audio changed. At 500 connections that alone cost more
687/// than the entire rest of a turn.
688///
689/// The same statement holds with far less work: within a domain, what a
690/// receiver must see is not each sender but each *distinct scope* the senders
691/// occupy, and there are usually one or two of those. Counting members per
692/// scope keeps the "everyone but me" exclusion exact without ever forming a
693/// pair.
694fn check_receivers_see_senders(
695    view: &ShardView,
696    overlays: &BTreeMap<ConnectionId, Overlay>,
697    audio: &AudioRelation,
698    observations: &BTreeMap<ConnectionId, ScopeSet>,
699) -> Result<(), BuildError> {
700    let shared_scope: BTreeMap<ConnectionId, Scope> = view
701        .users
702        .values()
703        .filter_map(|user| user.occupant.connection().map(|c| (c, user.scope)))
704        .collect();
705
706    // Who each connection can see privately, resolved once instead of per edge.
707    let privately: BTreeMap<ConnectionId, BTreeSet<ConnectionId>> = overlays
708        .iter()
709        .map(|(connection, overlay)| {
710            let visible = overlay
711                .users
712                .values()
713                .filter_map(|user| user.occupant.connection())
714                .collect();
715            (*connection, visible)
716        })
717        .collect();
718
719    for (_, members) in audio.domains() {
720        check_group(
721            members.iter().copied(),
722            members,
723            &shared_scope,
724            &privately,
725            observations,
726        )?;
727    }
728
729    for (listener, members) in audio.listeners() {
730        check_group(
731            std::iter::once(listener),
732            members,
733            &shared_scope,
734            &privately,
735            observations,
736        )?;
737    }
738
739    for (sender, receiver) in audio.explicit_edges() {
740        if !can_see(receiver, sender, &shared_scope, &privately, observations) {
741            return Err(BuildError::ReceiverCannotSeeSender { sender, receiver });
742        }
743    }
744    Ok(())
745}
746
747/// Check that every receiver can see every sender other than itself.
748fn check_group(
749    receivers: impl Iterator<Item = ConnectionId>,
750    senders: &BTreeSet<ConnectionId>,
751    shared_scope: &BTreeMap<ConnectionId, Scope>,
752    privately: &BTreeMap<ConnectionId, BTreeSet<ConnectionId>>,
753    observations: &BTreeMap<ConnectionId, ScopeSet>,
754) -> Result<(), BuildError> {
755    // Senders grouped by the scope they occupy, plus the ones the shared view
756    // does not carry at all, which have to be checked one by one.
757    let mut per_scope: BTreeMap<Scope, usize> = BTreeMap::new();
758    let mut hidden: Vec<ConnectionId> = Vec::new();
759    for sender in senders {
760        match shared_scope.get(sender) {
761            Some(scope) => *per_scope.entry(*scope).or_default() += 1,
762            None => hidden.push(*sender),
763        }
764    }
765
766    for receiver in receivers {
767        let see = observations
768            .get(&receiver)
769            .copied()
770            .unwrap_or(ScopeSet::NONE);
771        let own = shared_scope.get(&receiver).copied();
772
773        for (scope, count) in &per_scope {
774            // A receiver never sends to itself, so its own presence at this
775            // scope does not oblige it to see the scope.
776            let others = if own == Some(*scope) {
777                count.saturating_sub(1)
778            } else {
779                *count
780            };
781            if others > 0 && !see.sees(*scope) {
782                return Err(BuildError::ReceiverCannotSeeSender {
783                    sender: representative(senders, shared_scope, *scope, receiver),
784                    receiver,
785                });
786            }
787        }
788
789        for sender in &hidden {
790            if *sender != receiver
791                && !privately
792                    .get(&receiver)
793                    .is_some_and(|visible| visible.contains(sender))
794            {
795                return Err(BuildError::ReceiverCannotSeeSender {
796                    sender: *sender,
797                    receiver,
798                });
799            }
800        }
801    }
802    Ok(())
803}
804
805/// A sender at `scope` other than `receiver`, so the error names something the
806/// reader can go and look at. Only walked on the failure path.
807fn representative(
808    senders: &BTreeSet<ConnectionId>,
809    shared_scope: &BTreeMap<ConnectionId, Scope>,
810    scope: Scope,
811    receiver: ConnectionId,
812) -> ConnectionId {
813    senders
814        .iter()
815        .find(|sender| **sender != receiver && shared_scope.get(sender) == Some(&scope))
816        .copied()
817        .unwrap_or(receiver)
818}
819
820/// Whether `receiver` can see `sender`, through the shared view or its overlay.
821fn can_see(
822    receiver: ConnectionId,
823    sender: ConnectionId,
824    shared_scope: &BTreeMap<ConnectionId, Scope>,
825    privately: &BTreeMap<ConnectionId, BTreeSet<ConnectionId>>,
826    observations: &BTreeMap<ConnectionId, ScopeSet>,
827) -> bool {
828    if privately
829        .get(&receiver)
830        .is_some_and(|visible| visible.contains(&sender))
831    {
832        return true;
833    }
834    let Some(scope) = shared_scope.get(&sender) else {
835        // The sender is rendered nowhere, so no receiver could know its session.
836        return false;
837    };
838    observations
839        .get(&receiver)
840        .copied()
841        .unwrap_or(ScopeSet::NONE)
842        .sees(*scope)
843}
844
845#[cfg(test)]
846mod tests {
847    #![allow(clippy::expect_used)]
848
849    use super::*;
850    use crate::ids::SyntheticId;
851
852    fn observations(pairs: &[(u64, ScopeSet)]) -> BTreeMap<ConnectionId, ScopeSet> {
853        pairs
854            .iter()
855            .map(|(connection, see)| (ConnectionId(*connection), *see))
856            .collect()
857    }
858
859    fn everything() -> ScopeSet {
860        ScopeSet::new(&[Scope::ROOT]).expect("one scope")
861    }
862
863    #[test]
864    fn a_flavor_offering_too_many_actions_fails_its_render_rather_than_the_connection() {
865        // The whole turn goes into the queue in one piece, and an oversized batch
866        // closes the connection. A refused render keeps the bug inside the flavor.
867        let ids = SharedIds::new();
868        let connections = [ConnectionId(1)];
869        let mut builder = ShardBuilder::new(&ids, ShardId(1), &connections);
870        builder.root("Lobby");
871        builder.private(ConnectionId(1), |private| {
872            for key in 0..=u64::try_from(MAX_ACTIONS).expect("small") {
873                private.action(ActionKey(key), "Do it", On::SERVER);
874            }
875        });
876
877        assert!(matches!(
878            builder.finish(&observations(&[(1, everything())])),
879            Err(BuildError::TooManyActions {
880                connection: ConnectionId(1)
881            })
882        ));
883    }
884
885    #[test]
886    fn offering_the_same_action_twice_keeps_the_last_word() {
887        let ids = SharedIds::new();
888        let connections = [ConnectionId(1)];
889        let mut builder = ShardBuilder::new(&ids, ShardId(1), &connections);
890        builder.root("Lobby");
891        builder.private(ConnectionId(1), |private| {
892            private.action(ActionKey(1), "First", On::SERVER);
893            private.action(ActionKey(1), "Second", On::USER);
894        });
895
896        let rendered = builder
897            .finish(&observations(&[(1, everything())]))
898            .expect("a render with one action");
899        let offered = &rendered.actions[&ConnectionId(1)];
900        assert_eq!(offered.len(), 1);
901        assert_eq!(offered[&ActionKey(1)].text, "Second");
902        assert_eq!(offered[&ActionKey(1)].on, On::USER);
903    }
904
905    #[test]
906    fn a_user_is_always_at_or_below_its_channels_scope() {
907        let ids = SharedIds::new();
908        let connections = [ConnectionId(1)];
909        let mut builder = ShardBuilder::new(&ids, ShardId(1), &connections);
910
911        let root = builder.root("Lobby");
912        let game = builder.channel(root, ChannelKey(1), "Game", Narrow::Into(7));
913        let team = builder.channel(game, ChannelKey(2), "Team", Narrow::Into(2));
914        builder.user(
915            team,
916            Occupant::Connection(ConnectionId(1)),
917            "alice",
918            Narrow::Into(42),
919        );
920
921        let rendered = builder
922            .finish(&observations(&[(1, everything())]))
923            .expect("a hierarchical render is always coherent");
924
925        // The closure theorem, observed on the produced value: there is no
926        // builder call that could have made this false.
927        for user in rendered.view.users.values() {
928            let channel = rendered
929                .view
930                .channels
931                .get(&user.channel)
932                .expect("a user's channel is always rendered");
933            assert!(
934                channel.scope.is_prefix_of(user.scope),
935                "a user must never be broader than its channel"
936            );
937        }
938        for channel in rendered.view.channels.values() {
939            let parent = rendered
940                .view
941                .channels
942                .get(&channel.parent)
943                .expect("a channel's parent is always rendered");
944            assert!(parent.scope.is_prefix_of(channel.scope));
945        }
946    }
947
948    #[test]
949    fn a_render_without_a_root_is_refused() {
950        let ids = SharedIds::new();
951        let builder = ShardBuilder::new(&ids, ShardId(1), &[]);
952        assert_eq!(
953            builder.finish(&BTreeMap::new()),
954            Err(BuildError::MissingRoot)
955        );
956    }
957
958    #[test]
959    fn the_same_channel_key_twice_is_refused_rather_than_merged() {
960        let ids = SharedIds::new();
961        let mut builder = ShardBuilder::new(&ids, ShardId(1), &[]);
962        let root = builder.root("Lobby");
963        builder.channel(root, ChannelKey(1), "A", Narrow::Same);
964        builder.channel(root, ChannelKey(1), "B", Narrow::Same);
965
966        assert_eq!(
967            builder.finish(&BTreeMap::new()),
968            Err(BuildError::DuplicateChannelKey(ChannelKey(1)))
969        );
970    }
971
972    #[test]
973    fn narrowing_past_the_depth_bound_refuses_the_render() {
974        let ids = SharedIds::new();
975        let mut builder = ShardBuilder::new(&ids, ShardId(1), &[]);
976        let mut current = builder.root("Lobby");
977        for depth in 0..u64::try_from(crate::scope::MAX_DEPTH).unwrap_or(4) + 1 {
978            current = builder.channel(
979                current,
980                ChannelKey(depth + 1),
981                "deep",
982                Narrow::Into(u32::try_from(depth).unwrap_or(0)),
983            );
984        }
985
986        assert!(matches!(
987            builder.finish(&BTreeMap::new()),
988            Err(BuildError::ScopeTooDeep { .. })
989        ));
990    }
991
992    #[test]
993    fn linking_across_incomparable_scopes_is_refused() {
994        let ids = SharedIds::new();
995        let mut builder = ShardBuilder::new(&ids, ShardId(1), &[]);
996        let root = builder.root("Lobby");
997        let red = builder.channel(root, ChannelKey(1), "Red", Narrow::Into(2));
998        let blue = builder.channel(root, ChannelKey(2), "Blue", Narrow::Into(3));
999        builder.channel_link(red, blue);
1000
1001        assert_eq!(
1002            builder.finish(&BTreeMap::new()),
1003            Err(BuildError::LinkAcrossScopes {
1004                a: red.id(),
1005                b: blue.id()
1006            })
1007        );
1008    }
1009
1010    #[test]
1011    fn linking_within_comparable_scopes_is_symmetric() {
1012        let ids = SharedIds::new();
1013        let mut builder = ShardBuilder::new(&ids, ShardId(1), &[]);
1014        let root = builder.root("Lobby");
1015        let game = builder.channel(root, ChannelKey(1), "Game", Narrow::Into(7));
1016        let team = builder.channel(game, ChannelKey(2), "Team", Narrow::Into(2));
1017        builder.channel_link(game, team);
1018
1019        let rendered = builder.finish(&BTreeMap::new()).expect("comparable link");
1020        assert!(
1021            rendered.view.channels[&game.id()]
1022                .links
1023                .contains(&team.id())
1024        );
1025        assert!(
1026            rendered.view.channels[&team.id()]
1027                .links
1028                .contains(&game.id())
1029        );
1030    }
1031
1032    #[test]
1033    fn the_same_person_shared_and_private_is_refused_rather_than_merged() {
1034        let ids = SharedIds::new();
1035        let connections = [ConnectionId(1)];
1036        let mut builder = ShardBuilder::new(&ids, ShardId(1), &connections);
1037        let root = builder.root("Lobby");
1038        let admin = Occupant::Connection(ConnectionId(1));
1039        builder.user(root, admin, "admin", Narrow::Same);
1040        builder.private(ConnectionId(1), |private| {
1041            private.user_in(root, admin, "admin");
1042        });
1043
1044        assert!(matches!(
1045            builder.finish(&observations(&[(1, everything())])),
1046            Err(BuildError::SharedAndPrivateUser { .. })
1047        ));
1048    }
1049
1050    #[test]
1051    fn an_overlay_cannot_place_someone_in_a_channel_that_connection_cannot_see() {
1052        let ids = SharedIds::new();
1053        let connections = [ConnectionId(1)];
1054        let mut builder = ShardBuilder::new(&ids, ShardId(1), &connections);
1055        let root = builder.root("Lobby");
1056        let hidden = builder.channel(root, ChannelKey(1), "Red", Narrow::Into(2));
1057        builder.private(ConnectionId(1), |private| {
1058            private.user_in(hidden, Occupant::Synthetic(SyntheticId(1)), "ghost");
1059        });
1060
1061        // The connection only observes the sibling team, so the placement
1062        // channel is invisible to it.
1063        let blind = ScopeSet::new(&[Scope::ROOT.child(3).expect("depth 1")]).expect("one scope");
1064        assert!(matches!(
1065            builder.finish(&observations(&[(1, blind)])),
1066            Err(BuildError::OverlayChannelInvisible { .. })
1067        ));
1068    }
1069
1070    #[test]
1071    fn an_audio_edge_into_a_blind_receiver_is_refused() {
1072        let ids = SharedIds::new();
1073        let connections = [ConnectionId(1), ConnectionId(2)];
1074        let mut builder = ShardBuilder::new(&ids, ShardId(1), &connections);
1075        let root = builder.root("Lobby");
1076        let red = builder.channel(root, ChannelKey(1), "Red", Narrow::Into(2));
1077        let blue = builder.channel(root, ChannelKey(2), "Blue", Narrow::Into(3));
1078        builder.user(
1079            red,
1080            Occupant::Connection(ConnectionId(1)),
1081            "a",
1082            Narrow::Same,
1083        );
1084        builder.user(
1085            blue,
1086            Occupant::Connection(ConnectionId(2)),
1087            "b",
1088            Narrow::Same,
1089        );
1090        builder.audio_edge(ConnectionId(1), ConnectionId(2));
1091
1092        let red_only = ScopeSet::new(&[Scope::ROOT.child(2).expect("depth 1")]).expect("one scope");
1093        let blue_only =
1094            ScopeSet::new(&[Scope::ROOT.child(3).expect("depth 1")]).expect("one scope");
1095        assert_eq!(
1096            builder.finish(&observations(&[(1, red_only), (2, blue_only)])),
1097            Err(BuildError::ReceiverCannotSeeSender {
1098                sender: ConnectionId(1),
1099                receiver: ConnectionId(2),
1100            })
1101        );
1102    }
1103
1104    #[test]
1105    fn an_audio_edge_is_allowed_when_the_receiver_sees_the_sender_privately() {
1106        let ids = SharedIds::new();
1107        let connections = [ConnectionId(1), ConnectionId(2)];
1108        let mut builder = ShardBuilder::new(&ids, ShardId(1), &connections);
1109        let root = builder.root("Lobby");
1110        let red = builder.channel(root, ChannelKey(1), "Red", Narrow::Into(2));
1111        builder.user(
1112            red,
1113            Occupant::Connection(ConnectionId(2)),
1114            "b",
1115            Narrow::Same,
1116        );
1117        // The vanished admin exists only in connection 2's overlay, and that is
1118        // exactly what makes it audible to it.
1119        builder.private(ConnectionId(2), |private| {
1120            private.user_in(red, Occupant::Connection(ConnectionId(1)), "admin");
1121        });
1122        builder.audio_edge(ConnectionId(1), ConnectionId(2));
1123
1124        let red_only = ScopeSet::new(&[Scope::ROOT.child(2).expect("depth 1")]).expect("one scope");
1125        assert!(
1126            builder
1127                .finish(&observations(&[(1, red_only), (2, red_only)]))
1128                .is_ok()
1129        );
1130    }
1131}
mumble_server_runtime_shard/build.rs

mumble_server_runtime_shard/
build.rs
