Skip to main content

openmls/group/mls_group/
proposal_store.rs

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