openmls/group/mls_group/
proposal_store.rs

1use std::collections::{hash_map::Entry, HashMap, HashSet};
2
3use openmls_traits::crypto::OpenMlsCrypto;
4use openmls_traits::types::Ciphersuite;
5use serde::{Deserialize, Serialize};
6
7use crate::{
8    binary_tree::array_representation::LeafNodeIndex,
9    ciphersuite::hash_ref::ProposalRef,
10    error::LibraryError,
11    framing::{mls_auth_content::AuthenticatedContent, mls_content::FramedContentBody, Sender},
12    group::errors::*,
13    messages::proposals::{
14        AddProposal, PreSharedKeyProposal, Proposal, ProposalOrRef, ProposalOrRefType,
15        ProposalType, RemoveProposal, UpdateProposal,
16    },
17    utils::vector_converter,
18};
19
20/// A [ProposalStore] can store the standalone proposals that are received from
21/// the DS in between two commit messages.
22#[derive(Debug, Default, Serialize, Deserialize, PartialEq)]
23#[cfg_attr(any(test, feature = "test-utils"), derive(Clone))]
24pub struct ProposalStore {
25    queued_proposals: Vec<QueuedProposal>,
26}
27
28impl ProposalStore {
29    /// Create a new [`ProposalStore`].
30    pub fn new() -> Self {
31        Self {
32            queued_proposals: Vec::new(),
33        }
34    }
35    #[cfg(test)]
36    pub(crate) fn from_queued_proposal(queued_proposal: QueuedProposal) -> Self {
37        Self {
38            queued_proposals: vec![queued_proposal],
39        }
40    }
41    pub(crate) fn add(&mut self, queued_proposal: QueuedProposal) {
42        self.queued_proposals.push(queued_proposal);
43    }
44    pub(crate) fn proposals(&self) -> impl Iterator<Item = &QueuedProposal> {
45        self.queued_proposals.iter()
46    }
47    pub(crate) fn is_empty(&self) -> bool {
48        self.queued_proposals.is_empty()
49    }
50    pub(crate) fn empty(&mut self) {
51        self.queued_proposals.clear();
52    }
53
54    /// Removes a proposal from the store using its reference. It will return
55    /// None if it wasn't found in the store.
56    pub(crate) fn remove(&mut self, proposal_ref: &ProposalRef) -> Option<()> {
57        let index = self
58            .queued_proposals
59            .iter()
60            .position(|p| &p.proposal_reference() == proposal_ref)?;
61        self.queued_proposals.remove(index);
62        Some(())
63    }
64}
65
66/// Alternative representation of a Proposal, where the sender is extracted from
67/// the encapsulating PublicMessage and the ProposalRef is attached.
68#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
69pub struct QueuedProposal {
70    proposal: Proposal,
71    proposal_reference: ProposalRef,
72    sender: Sender,
73    proposal_or_ref_type: ProposalOrRefType,
74}
75
76impl QueuedProposal {
77    /// Creates a new [QueuedProposal] from an [PublicMessage]
78    pub(crate) fn from_authenticated_content_by_ref(
79        ciphersuite: Ciphersuite,
80        crypto: &impl OpenMlsCrypto,
81        public_message: AuthenticatedContent,
82    ) -> Result<Self, LibraryError> {
83        Self::from_authenticated_content(
84            ciphersuite,
85            crypto,
86            public_message,
87            ProposalOrRefType::Reference,
88        )
89    }
90
91    /// Creates a new [QueuedProposal] from an [PublicMessage]
92    pub(crate) fn from_authenticated_content(
93        ciphersuite: Ciphersuite,
94        crypto: &impl OpenMlsCrypto,
95        public_message: AuthenticatedContent,
96        proposal_or_ref_type: ProposalOrRefType,
97    ) -> Result<Self, LibraryError> {
98        let proposal_reference =
99            ProposalRef::from_authenticated_content_by_ref(crypto, ciphersuite, &public_message)
100                .map_err(|_| LibraryError::custom("Could not calculate `ProposalRef`."))?;
101
102        let (body, sender) = public_message.into_body_and_sender();
103
104        let proposal = match body {
105            FramedContentBody::Proposal(p) => p,
106            _ => return Err(LibraryError::custom("Wrong content type")),
107        };
108
109        Ok(Self {
110            proposal,
111            proposal_reference,
112            sender,
113            proposal_or_ref_type,
114        })
115    }
116
117    /// Creates a new [QueuedProposal] from a [Proposal] and [Sender]
118    ///
119    /// Note: We should calculate the proposal ref by hashing the authenticated
120    /// content but can't do this here without major refactoring. Thus, we
121    /// use an internal `from_raw_proposal` hash.
122    pub(crate) fn from_proposal_and_sender(
123        ciphersuite: Ciphersuite,
124        crypto: &impl OpenMlsCrypto,
125        proposal: Proposal,
126        sender: &Sender,
127    ) -> Result<Self, LibraryError> {
128        let proposal_reference = ProposalRef::from_raw_proposal(ciphersuite, crypto, &proposal)?;
129        Ok(Self {
130            proposal,
131            proposal_reference,
132            sender: sender.clone(),
133            proposal_or_ref_type: ProposalOrRefType::Proposal,
134        })
135    }
136
137    /// Returns the `Proposal` as a reference
138    pub fn proposal(&self) -> &Proposal {
139        &self.proposal
140    }
141    /// Returns the `ProposalRef`.
142    pub(crate) fn proposal_reference(&self) -> ProposalRef {
143        self.proposal_reference.clone()
144    }
145    /// Returns the `ProposalOrRefType`.
146    pub fn proposal_or_ref_type(&self) -> ProposalOrRefType {
147        self.proposal_or_ref_type
148    }
149    /// Returns the `Sender` as a reference
150    pub fn sender(&self) -> &Sender {
151        &self.sender
152    }
153}
154
155/// Helper struct to collect proposals such that they are unique and can be read
156/// out in the order in that they were added.
157struct OrderedProposalRefs {
158    proposal_refs: HashSet<ProposalRef>,
159    ordered_proposal_refs: Vec<ProposalRef>,
160}
161
162impl OrderedProposalRefs {
163    fn new() -> Self {
164        Self {
165            proposal_refs: HashSet::new(),
166            ordered_proposal_refs: Vec::new(),
167        }
168    }
169
170    /// Adds a proposal reference to the queue. If the proposal reference is
171    /// already in the queue, it ignores it.
172    fn add(&mut self, proposal_ref: ProposalRef) {
173        // The `insert` function of the `HashSet` returns `true` if the element
174        // is new to the set.
175        if self.proposal_refs.insert(proposal_ref.clone()) {
176            self.ordered_proposal_refs.push(proposal_ref);
177        }
178    }
179
180    /// Returns an iterator over the proposal references in the order in which
181    /// they were inserted.
182    fn iter(&self) -> impl Iterator<Item = &ProposalRef> {
183        self.ordered_proposal_refs.iter()
184    }
185}
186
187/// Proposal queue that helps filtering and sorting Proposals received during
188/// one epoch. The Proposals are stored in a `HashMap` which maps Proposal
189/// references to Proposals, such that, given a reference, a proposal can be
190/// accessed efficiently. To enable iteration over the queue in order, the
191/// `ProposalQueue` also contains a vector of `ProposalRef`s.
192#[derive(Default, Debug, Serialize, Deserialize)]
193#[cfg_attr(any(test, feature = "test-utils"), derive(Clone, PartialEq))]
194pub(crate) struct ProposalQueue {
195    /// `proposal_references` holds references to the proposals in the queue and
196    /// determines the order of the queue.
197    proposal_references: Vec<ProposalRef>,
198    /// `queued_proposals` contains the actual proposals in the queue. They are
199    /// stored in a `HashMap` to allow for efficient access to the proposals.
200    #[serde(with = "vector_converter")]
201    queued_proposals: HashMap<ProposalRef, QueuedProposal>,
202}
203
204impl ProposalQueue {
205    /// Returns `true` if the [`ProposalQueue`] is empty. Otherwise returns
206    /// `false`.
207    pub(crate) fn is_empty(&self) -> bool {
208        self.proposal_references.is_empty()
209    }
210
211    /// Returns a new `QueuedProposalQueue` from proposals that were committed
212    /// and don't need filtering.
213    /// This functions does the following checks:
214    ///  - ValSem200
215    pub(crate) fn from_committed_proposals(
216        ciphersuite: Ciphersuite,
217        crypto: &impl OpenMlsCrypto,
218        committed_proposals: Vec<ProposalOrRef>,
219        proposal_store: &ProposalStore,
220        sender: &Sender,
221    ) -> Result<Self, FromCommittedProposalsError> {
222        log::debug!("from_committed_proposals");
223        // Feed the `proposals_by_reference` in a `HashMap` so that we can easily
224        // extract then by reference later
225        let mut proposals_by_reference_queue: HashMap<ProposalRef, QueuedProposal> = HashMap::new();
226        for queued_proposal in proposal_store.proposals() {
227            proposals_by_reference_queue.insert(
228                queued_proposal.proposal_reference(),
229                queued_proposal.clone(),
230            );
231        }
232        log::trace!("   known proposals:\n{:#?}", proposals_by_reference_queue);
233        // Build the actual queue
234        let mut proposal_queue = ProposalQueue::default();
235
236        // Iterate over the committed proposals and insert the proposals in the queue
237        log::trace!("   committed proposals ...");
238        for proposal_or_ref in committed_proposals.into_iter() {
239            log::trace!("       proposal_or_ref:\n{:#?}", proposal_or_ref);
240            let queued_proposal = match proposal_or_ref {
241                ProposalOrRef::Proposal(proposal) => {
242                    // ValSem200
243                    if let Proposal::Remove(ref remove_proposal) = proposal {
244                        if let Sender::Member(leaf_index) = sender {
245                            if remove_proposal.removed() == *leaf_index {
246                                return Err(FromCommittedProposalsError::SelfRemoval);
247                            }
248                        }
249                    }
250
251                    QueuedProposal::from_proposal_and_sender(ciphersuite, crypto, proposal, sender)?
252                }
253                ProposalOrRef::Reference(ref proposal_reference) => {
254                    match proposals_by_reference_queue.get(proposal_reference) {
255                        Some(queued_proposal) => {
256                            // ValSem200
257                            if let Proposal::Remove(ref remove_proposal) = queued_proposal.proposal
258                            {
259                                if let Sender::Member(leaf_index) = sender {
260                                    if remove_proposal.removed() == *leaf_index {
261                                        return Err(FromCommittedProposalsError::SelfRemoval);
262                                    }
263                                }
264                            }
265
266                            queued_proposal.clone()
267                        }
268                        None => return Err(FromCommittedProposalsError::ProposalNotFound),
269                    }
270                }
271            };
272            proposal_queue.add(queued_proposal);
273        }
274
275        Ok(proposal_queue)
276    }
277
278    /// Returns proposal for a given proposal ID
279    pub fn get(&self, proposal_reference: &ProposalRef) -> Option<&QueuedProposal> {
280        self.queued_proposals.get(proposal_reference)
281    }
282
283    /// Add a new [QueuedProposal] to the queue
284    pub(crate) fn add(&mut self, queued_proposal: QueuedProposal) {
285        let proposal_reference = queued_proposal.proposal_reference();
286        // Only add the proposal if it's not already there
287        if let Entry::Vacant(entry) = self.queued_proposals.entry(proposal_reference.clone()) {
288            // Add the proposal reference to ensure the correct order
289            self.proposal_references.push(proposal_reference);
290            // Add the proposal to the queue
291            entry.insert(queued_proposal);
292        }
293    }
294
295    /// Returns an iterator over a list of `QueuedProposal` filtered by proposal
296    /// type
297    pub(crate) fn filtered_by_type(
298        &self,
299        proposal_type: ProposalType,
300    ) -> impl Iterator<Item = &QueuedProposal> {
301        // Iterate over the reference to extract the proposals in the right order
302        self.proposal_references
303            .iter()
304            .filter(move |&pr| match self.queued_proposals.get(pr) {
305                Some(p) => p.proposal.is_type(proposal_type),
306                None => false,
307            })
308            .filter_map(move |reference| self.get(reference))
309    }
310
311    /// Returns an iterator over all `QueuedProposal` in the queue
312    /// in the order of the the Commit message
313    pub(crate) fn queued_proposals(&self) -> impl Iterator<Item = &QueuedProposal> {
314        // Iterate over the reference to extract the proposals in the right order
315        self.proposal_references
316            .iter()
317            .filter_map(move |reference| self.get(reference))
318    }
319
320    /// Returns an iterator over all Add proposals in the queue
321    /// in the order of the the Commit message
322    pub(crate) fn add_proposals(&self) -> impl Iterator<Item = QueuedAddProposal> {
323        self.queued_proposals().filter_map(|queued_proposal| {
324            if let Proposal::Add(add_proposal) = queued_proposal.proposal() {
325                let sender = queued_proposal.sender();
326                Some(QueuedAddProposal {
327                    add_proposal,
328                    sender,
329                })
330            } else {
331                None
332            }
333        })
334    }
335
336    /// Returns an iterator over all Remove proposals in the queue
337    /// in the order of the the Commit message
338    pub(crate) fn remove_proposals(&self) -> impl Iterator<Item = QueuedRemoveProposal> {
339        self.queued_proposals().filter_map(|queued_proposal| {
340            if let Proposal::Remove(remove_proposal) = queued_proposal.proposal() {
341                let sender = queued_proposal.sender();
342                Some(QueuedRemoveProposal {
343                    remove_proposal,
344                    sender,
345                })
346            } else {
347                None
348            }
349        })
350    }
351
352    /// Returns an iterator over all Update in the queue
353    /// in the order of the the Commit message
354    pub(crate) fn update_proposals(&self) -> impl Iterator<Item = QueuedUpdateProposal> {
355        self.queued_proposals().filter_map(|queued_proposal| {
356            if let Proposal::Update(update_proposal) = queued_proposal.proposal() {
357                let sender = queued_proposal.sender();
358                Some(QueuedUpdateProposal {
359                    update_proposal,
360                    sender,
361                })
362            } else {
363                None
364            }
365        })
366    }
367
368    /// Returns an iterator over all PresharedKey proposals in the queue
369    /// in the order of the the Commit message
370    pub(crate) fn psk_proposals(&self) -> impl Iterator<Item = QueuedPskProposal> {
371        self.queued_proposals().filter_map(|queued_proposal| {
372            if let Proposal::PreSharedKey(psk_proposal) = queued_proposal.proposal() {
373                let sender = queued_proposal.sender();
374                Some(QueuedPskProposal {
375                    psk_proposal,
376                    sender,
377                })
378            } else {
379                None
380            }
381        })
382    }
383
384    /// Filters received proposals
385    ///
386    /// 11.2 Commit
387    /// If there are multiple proposals that apply to the same leaf,
388    /// the committer chooses one and includes only that one in the Commit,
389    /// considering the rest invalid. The committer MUST prefer any Remove
390    /// received, or the most recent Update for the leaf if there are no
391    /// Removes. If there are multiple Add proposals for the same client,
392    /// the committer again chooses one to include and considers the rest
393    /// invalid.
394    ///
395    /// The function performs the following steps:
396    ///
397    /// - Extract Adds and filter for duplicates
398    /// - Build member list with chains: Updates, Removes & SelfRemoves
399    /// - Check for invalid indexes and drop proposal
400    /// - Check for presence of SelfRemoves and delete Removes and Updates
401    /// - Check for presence of Removes and delete Updates
402    /// - Only keep the last Update
403    ///
404    /// Return a [`ProposalQueue`] and a bool that indicates whether Updates for
405    /// the own node were included
406    pub(crate) fn filter_proposals<'a>(
407        ciphersuite: Ciphersuite,
408        crypto: &impl OpenMlsCrypto,
409        sender: Sender,
410        proposal_store: &'a ProposalStore,
411        inline_proposals: &'a [Proposal],
412        own_index: LeafNodeIndex,
413    ) -> Result<(Self, bool), ProposalQueueError> {
414        // We use a HashSet to filter out duplicate Adds and use a vector in
415        // addition to keep the order as they come in.
416        let mut adds: OrderedProposalRefs = OrderedProposalRefs::new();
417        let mut valid_proposals: OrderedProposalRefs = OrderedProposalRefs::new();
418        let mut proposal_pool: HashMap<ProposalRef, QueuedProposal> = HashMap::new();
419        let mut contains_own_updates = false;
420        let mut contains_external_init = false;
421
422        let mut member_specific_proposals: HashMap<LeafNodeIndex, QueuedProposal> = HashMap::new();
423        let mut register_member_specific_proposal =
424            |member: LeafNodeIndex, proposal: QueuedProposal| {
425                // Only replace if the existing proposal is an Update.
426                match member_specific_proposals.entry(member) {
427                    // Insert if no entry exists for this sender.
428                    Entry::Vacant(vacant_entry) => {
429                        vacant_entry.insert(proposal);
430                    }
431                    // Replace the existing proposal if the new proposal has
432                    // priority.
433                    Entry::Occupied(mut occupied_entry)
434                        if occupied_entry
435                            .get()
436                            .proposal()
437                            .has_lower_priority_than(&proposal.proposal) =>
438                    {
439                        occupied_entry.insert(proposal);
440                    }
441                    // Otherwise ignore the new proposal.
442                    Entry::Occupied(_) => {}
443                }
444            };
445
446        // Aggregate both proposal types to a common iterator
447        // We checked earlier that only proposals can end up here
448        let mut queued_proposal_list: Vec<QueuedProposal> =
449            proposal_store.proposals().cloned().collect();
450
451        queued_proposal_list.extend(
452            inline_proposals
453                .iter()
454                .map(|p| {
455                    QueuedProposal::from_proposal_and_sender(
456                        ciphersuite,
457                        crypto,
458                        p.clone(),
459                        &sender,
460                    )
461                })
462                .collect::<Result<Vec<QueuedProposal>, _>>()?,
463        );
464
465        // Parse proposals and build adds and member list
466        for queued_proposal in queued_proposal_list {
467            proposal_pool.insert(
468                queued_proposal.proposal_reference(),
469                queued_proposal.clone(),
470            );
471            match queued_proposal.proposal {
472                Proposal::Add(_) => {
473                    adds.add(queued_proposal.proposal_reference());
474                }
475                Proposal::Update(_) => {
476                    // Only members can send update proposals
477                    // ValSem112
478                    let Sender::Member(sender_index) = queued_proposal.sender() else {
479                        return Err(ProposalQueueError::UpdateFromExternalSender);
480                    };
481                    if sender_index == &own_index {
482                        contains_own_updates = true;
483                        continue;
484                    }
485                    register_member_specific_proposal(*sender_index, queued_proposal);
486                }
487                Proposal::Remove(ref remove_proposal) => {
488                    let removed = remove_proposal.removed();
489                    register_member_specific_proposal(removed, queued_proposal);
490                }
491                Proposal::PreSharedKey(_) => {
492                    valid_proposals.add(queued_proposal.proposal_reference());
493                }
494                Proposal::ReInit(_) => {
495                    // TODO #751: Only keep one ReInit
496                }
497                Proposal::ExternalInit(_) => {
498                    // Only use the first external init proposal we find.
499                    if !contains_external_init {
500                        valid_proposals.add(queued_proposal.proposal_reference());
501                        contains_external_init = true;
502                    }
503                }
504                Proposal::GroupContextExtensions(_) => {
505                    valid_proposals.add(queued_proposal.proposal_reference());
506                }
507                Proposal::AppAck(_) => unimplemented!("See #291"),
508                Proposal::SelfRemove => {
509                    let Sender::Member(removed) = queued_proposal.sender() else {
510                        return Err(ProposalQueueError::SelfRemoveFromNonMember);
511                    };
512                    register_member_specific_proposal(*removed, queued_proposal);
513                }
514                Proposal::Custom(_) => {
515                    // Other/unknown proposals are always considered valid and
516                    // have to be checked by the application instead.
517                    valid_proposals.add(queued_proposal.proposal_reference());
518                }
519            }
520        }
521
522        // Add the leaf-specific proposals to the list of valid proposals.
523        for proposal in member_specific_proposals.values() {
524            valid_proposals.add(proposal.proposal_reference());
525        }
526
527        // Only retain `adds` and `valid_proposals`
528        let mut proposal_queue = ProposalQueue::default();
529        for proposal_reference in adds.iter().chain(valid_proposals.iter()) {
530            let queued_proposal = proposal_pool
531                .get(proposal_reference)
532                .cloned()
533                .ok_or(ProposalQueueError::ProposalNotFound)?;
534            proposal_queue.add(queued_proposal);
535        }
536        Ok((proposal_queue, contains_own_updates))
537    }
538
539    /// Filters received proposals without inline proposals
540    ///
541    /// 11.2 Commit
542    /// If there are multiple proposals that apply to the same leaf,
543    /// the committer chooses one and includes only that one in the Commit,
544    /// considering the rest invalid. The committer MUST prefer any Remove
545    /// received, or the most recent Update for the leaf if there are no
546    /// Removes. If there are multiple Add proposals for the same client,
547    /// the committer again chooses one to include and considers the rest
548    /// invalid.
549    ///
550    /// The function performs the following steps:
551    ///
552    /// - Extract Adds and filter for duplicates
553    /// - Build member list with chains: Updates, Removes & SelfRemoves
554    /// - Check for invalid indexes and drop proposal
555    /// - Check for presence of SelfRemoves and delete Removes and Updates
556    /// - Check for presence of Removes and delete Updates
557    /// - Only keep the last Update
558    ///
559    /// Return a [`ProposalQueue`] and a bool that indicates whether Updates for
560    /// the own node were included
561    pub(crate) fn filter_proposals_without_inline(
562        iter: impl IntoIterator<Item = QueuedProposal>,
563        own_index: LeafNodeIndex,
564    ) -> Result<(Self, bool), ProposalQueueError> {
565        // We use a HashSet to filter out duplicate Adds and use a vector in
566        // addition to keep the order as they come in.
567        let mut adds: OrderedProposalRefs = OrderedProposalRefs::new();
568        let mut valid_proposals: OrderedProposalRefs = OrderedProposalRefs::new();
569        let mut proposal_pool: HashMap<ProposalRef, QueuedProposal> = HashMap::new();
570        let mut contains_own_updates = false;
571        let mut contains_external_init = false;
572
573        let mut member_specific_proposals: HashMap<LeafNodeIndex, QueuedProposal> = HashMap::new();
574        let mut register_member_specific_proposal =
575            |member: LeafNodeIndex, proposal: QueuedProposal| {
576                // Only replace if the existing proposal is an Update.
577                match member_specific_proposals.entry(member) {
578                    // Insert if no entry exists for this sender.
579                    Entry::Vacant(vacant_entry) => {
580                        vacant_entry.insert(proposal);
581                    }
582                    // Replace the existing proposal if the new proposal has
583                    // priority.
584                    Entry::Occupied(mut occupied_entry)
585                        if occupied_entry
586                            .get()
587                            .proposal()
588                            .has_lower_priority_than(&proposal.proposal) =>
589                    {
590                        occupied_entry.insert(proposal);
591                    }
592                    // Otherwise ignore the new proposal.
593                    Entry::Occupied(_) => {}
594                }
595            };
596
597        // Parse proposals and build adds and member list
598        for queued_proposal in iter {
599            proposal_pool.insert(
600                queued_proposal.proposal_reference(),
601                queued_proposal.clone(),
602            );
603            match queued_proposal.proposal {
604                Proposal::Add(_) => {
605                    adds.add(queued_proposal.proposal_reference());
606                }
607                Proposal::Update(_) => {
608                    // Only members can send update proposals
609                    // ValSem112
610                    let Sender::Member(sender_index) = queued_proposal.sender() else {
611                        return Err(ProposalQueueError::UpdateFromExternalSender);
612                    };
613                    if sender_index == &own_index {
614                        contains_own_updates = true;
615                        continue;
616                    }
617                    register_member_specific_proposal(*sender_index, queued_proposal);
618                }
619                Proposal::Remove(ref remove_proposal) => {
620                    let removed = remove_proposal.removed();
621                    register_member_specific_proposal(removed, queued_proposal);
622                }
623                Proposal::PreSharedKey(_) => {
624                    valid_proposals.add(queued_proposal.proposal_reference());
625                }
626                Proposal::ReInit(_) => {
627                    // TODO #751: Only keep one ReInit
628                }
629                Proposal::ExternalInit(_) => {
630                    // Only use the first external init proposal we find.
631                    if !contains_external_init {
632                        valid_proposals.add(queued_proposal.proposal_reference());
633                        contains_external_init = true;
634                    }
635                }
636                Proposal::GroupContextExtensions(_) => {
637                    valid_proposals.add(queued_proposal.proposal_reference());
638                }
639                Proposal::AppAck(_) => unimplemented!("See #291"),
640                Proposal::SelfRemove => {
641                    let Sender::Member(removed) = queued_proposal.sender() else {
642                        return Err(ProposalQueueError::SelfRemoveFromNonMember);
643                    };
644                    register_member_specific_proposal(*removed, queued_proposal);
645                }
646                Proposal::Custom(_) => {
647                    // Other/unknown proposals are always considered valid and
648                    // have to be checked by the application instead.
649                    valid_proposals.add(queued_proposal.proposal_reference());
650                }
651            }
652        }
653
654        // Add the leaf-specific proposals to the list of valid proposals.
655        for proposal in member_specific_proposals.values() {
656            valid_proposals.add(proposal.proposal_reference());
657        }
658
659        // Only retain `adds` and `valid_proposals`
660        let mut proposal_queue = ProposalQueue::default();
661        for proposal_reference in adds.iter().chain(valid_proposals.iter()) {
662            let queued_proposal = proposal_pool
663                .get(proposal_reference)
664                .cloned()
665                .ok_or(ProposalQueueError::ProposalNotFound)?;
666            proposal_queue.add(queued_proposal);
667        }
668        Ok((proposal_queue, contains_own_updates))
669    }
670
671    /// Returns `true` if all `ProposalRef` values from the list are
672    /// contained in the queue
673    #[cfg(test)]
674    pub(crate) fn contains(&self, proposal_reference_list: &[ProposalRef]) -> bool {
675        for proposal_reference in proposal_reference_list {
676            if !self.queued_proposals.contains_key(proposal_reference) {
677                return false;
678            }
679        }
680        true
681    }
682
683    /// Returns the list of all proposals that are covered by a Commit
684    pub(crate) fn commit_list(&self) -> Vec<ProposalOrRef> {
685        // Iterate over the reference to extract the proposals in the right order
686        self.proposal_references
687            .iter()
688            .filter_map(|proposal_reference| self.queued_proposals.get(proposal_reference))
689            .map(|queued_proposal| {
690                // Differentiate the type of proposal
691                match queued_proposal.proposal_or_ref_type {
692                    ProposalOrRefType::Proposal => {
693                        ProposalOrRef::Proposal(queued_proposal.proposal.clone())
694                    }
695                    ProposalOrRefType::Reference => {
696                        ProposalOrRef::Reference(queued_proposal.proposal_reference.clone())
697                    }
698                }
699            })
700            .collect::<Vec<ProposalOrRef>>()
701    }
702}
703
704impl Extend<QueuedProposal> for ProposalQueue {
705    fn extend<T: IntoIterator<Item = QueuedProposal>>(&mut self, iter: T) {
706        for proposal in iter {
707            self.add(proposal)
708        }
709    }
710}
711
712impl IntoIterator for ProposalQueue {
713    type Item = QueuedProposal;
714
715    type IntoIter = std::collections::hash_map::IntoValues<ProposalRef, QueuedProposal>;
716
717    fn into_iter(self) -> Self::IntoIter {
718        self.queued_proposals.into_values()
719    }
720}
721
722impl<'a> IntoIterator for &'a ProposalQueue {
723    type Item = &'a QueuedProposal;
724
725    type IntoIter = std::collections::hash_map::Values<'a, ProposalRef, QueuedProposal>;
726
727    fn into_iter(self) -> Self::IntoIter {
728        self.queued_proposals.values()
729    }
730}
731
732impl FromIterator<QueuedProposal> for ProposalQueue {
733    fn from_iter<T: IntoIterator<Item = QueuedProposal>>(iter: T) -> Self {
734        let mut out = Self::default();
735        out.extend(iter);
736        out
737    }
738}
739
740/// A queued Add proposal
741#[derive(PartialEq, Debug)]
742pub struct QueuedAddProposal<'a> {
743    add_proposal: &'a AddProposal,
744    sender: &'a Sender,
745}
746
747impl QueuedAddProposal<'_> {
748    /// Returns a reference to the proposal
749    pub fn add_proposal(&self) -> &AddProposal {
750        self.add_proposal
751    }
752
753    /// Returns a reference to the sender
754    pub fn sender(&self) -> &Sender {
755        self.sender
756    }
757}
758
759/// A queued Remove proposal
760#[derive(PartialEq, Eq, Debug)]
761pub struct QueuedRemoveProposal<'a> {
762    remove_proposal: &'a RemoveProposal,
763    sender: &'a Sender,
764}
765
766impl QueuedRemoveProposal<'_> {
767    /// Returns a reference to the proposal
768    pub fn remove_proposal(&self) -> &RemoveProposal {
769        self.remove_proposal
770    }
771
772    /// Returns a reference to the sender
773    pub fn sender(&self) -> &Sender {
774        self.sender
775    }
776}
777
778/// A queued Update proposal
779#[derive(PartialEq, Eq, Debug)]
780pub struct QueuedUpdateProposal<'a> {
781    update_proposal: &'a UpdateProposal,
782    sender: &'a Sender,
783}
784
785impl QueuedUpdateProposal<'_> {
786    /// Returns a reference to the proposal
787    pub fn update_proposal(&self) -> &UpdateProposal {
788        self.update_proposal
789    }
790
791    /// Returns a reference to the sender
792    pub fn sender(&self) -> &Sender {
793        self.sender
794    }
795}
796
797/// A queued PresharedKey proposal
798#[derive(PartialEq, Eq, Debug)]
799pub struct QueuedPskProposal<'a> {
800    psk_proposal: &'a PreSharedKeyProposal,
801    sender: &'a Sender,
802}
803
804impl QueuedPskProposal<'_> {
805    /// Returns a reference to the proposal
806    pub fn psk_proposal(&self) -> &PreSharedKeyProposal {
807        self.psk_proposal
808    }
809
810    /// Returns a reference to the sender
811    pub fn sender(&self) -> &Sender {
812        self.sender
813    }
814}