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#[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 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 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 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#[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 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 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 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 pub fn proposal(&self) -> &Proposal {
170 &self.proposal
171 }
172 pub(crate) fn proposal_reference(&self) -> ProposalRef {
174 self.proposal_reference.clone()
175 }
176
177 pub fn proposal_reference_ref(&self) -> &ProposalRef {
179 &self.proposal_reference
180 }
181
182 pub fn proposal_or_ref_type(&self) -> ProposalOrRefType {
184 self.proposal_or_ref_type
185 }
186 pub fn sender(&self) -> &Sender {
188 &self.sender
189 }
190}
191
192struct 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 fn add(&mut self, proposal_ref: ProposalRef) {
210 if self.proposal_refs.insert(proposal_ref.clone()) {
213 self.ordered_proposal_refs.push(proposal_ref);
214 }
215 }
216
217 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 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#[derive(Default, Debug, Serialize, Deserialize)]
254#[cfg_attr(any(test, feature = "test-utils"), derive(Clone, PartialEq))]
255pub struct ProposalQueue {
256 proposal_references: Vec<ProposalRef>,
259 #[serde(with = "vector_converter")]
262 queued_proposals: HashMap<ProposalRef, QueuedProposal>,
263}
264
265impl ProposalQueue {
266 pub(crate) fn is_empty(&self) -> bool {
269 self.proposal_references.is_empty()
270 }
271
272 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 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 let mut proposal_queue = ProposalQueue::default();
296
297 let mut psk_proposal_duplicate_checker = PskProposalDuplicateChecker::default();
298
299 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 if proposal
308 .as_remove()
309 .and_then(|remove_proposal| {
310 sender.as_member().filter(|leaf_index| {
311 remove_proposal.removed() == *leaf_index
313 })
314 })
315 .is_some()
316 {
317 return Err(FromCommittedProposalsError::SelfRemoval);
318 };
319
320 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 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 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 pub fn get(&self, proposal_reference: &ProposalRef) -> Option<&QueuedProposal> {
360 self.queued_proposals.get(proposal_reference)
361 }
362
363 pub(crate) fn add(&mut self, queued_proposal: QueuedProposal) {
365 let proposal_reference = queued_proposal.proposal_reference();
366 if let Entry::Vacant(entry) = self.queued_proposals.entry(proposal_reference.clone()) {
368 self.proposal_references.push(proposal_reference);
370 entry.insert(queued_proposal);
372 }
373 }
374
375 pub(crate) fn filtered_by_type(
378 &self,
379 proposal_type: ProposalType,
380 ) -> impl Iterator<Item = &QueuedProposal> {
381 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 pub(crate) fn queued_proposals(&self) -> impl Iterator<Item = &QueuedProposal> {
394 self.proposal_references
396 .iter()
397 .filter_map(move |reference| self.get(reference))
398 }
399
400 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 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 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 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 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 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 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 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 pub(crate) fn filter_proposals(
544 iter: impl IntoIterator<Item = QueuedProposal>,
545 own_index: LeafNodeIndex,
546 ) -> Result<(Self, bool), ProposalQueueError> {
547 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 match member_specific_proposals.entry(member) {
562 btree_map::Entry::Vacant(vacant_entry) => {
564 vacant_entry.insert(proposal);
565 }
566 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 btree_map::Entry::Occupied(_) => {}
578 }
579 };
580
581 for queued_proposal in iter {
583 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 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 if !contains_reinit {
625 valid_proposals.add(queued_proposal.proposal_reference());
626 contains_reinit = true;
627 }
628 }
629 Proposal::ExternalInit(_) => {
630 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 valid_proposals.add(queued_proposal.proposal_reference());
657 }
658 }
659 }
660
661 for proposal in member_specific_proposals.values() {
663 valid_proposals.add(proposal.proposal_reference());
664 }
665
666 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 #[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 pub(crate) fn commit_list(&self) -> Vec<ProposalOrRef> {
692 self.proposal_references
694 .iter()
695 .filter_map(|proposal_reference| self.queued_proposals.get(proposal_reference))
696 .map(|queued_proposal| {
697 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#[derive(PartialEq, Debug)]
749pub struct QueuedAddProposal<'a> {
750 add_proposal: &'a AddProposal,
751 sender: &'a Sender,
752}
753
754impl QueuedAddProposal<'_> {
755 pub fn add_proposal(&self) -> &AddProposal {
757 self.add_proposal
758 }
759
760 pub fn sender(&self) -> &Sender {
762 self.sender
763 }
764}
765
766#[derive(PartialEq, Eq, Debug)]
768pub struct QueuedRemoveProposal<'a> {
769 remove_proposal: &'a RemoveProposal,
770 sender: &'a Sender,
771}
772
773impl QueuedRemoveProposal<'_> {
774 pub fn remove_proposal(&self) -> &RemoveProposal {
776 self.remove_proposal
777 }
778
779 pub fn sender(&self) -> &Sender {
781 self.sender
782 }
783}
784
785#[derive(PartialEq, Eq, Debug)]
787pub struct QueuedUpdateProposal<'a> {
788 update_proposal: &'a UpdateProposal,
789 sender: &'a Sender,
790}
791
792impl QueuedUpdateProposal<'_> {
793 pub fn update_proposal(&self) -> &UpdateProposal {
795 self.update_proposal
796 }
797
798 pub fn sender(&self) -> &Sender {
800 self.sender
801 }
802}
803
804#[derive(PartialEq, Eq, Debug)]
806pub struct QueuedPskProposal<'a> {
807 psk_proposal: &'a PreSharedKeyProposal,
808 sender: &'a Sender,
809}
810
811impl QueuedPskProposal<'_> {
812 pub fn psk_proposal(&self) -> &PreSharedKeyProposal {
814 self.psk_proposal
815 }
816
817 pub fn sender(&self) -> &Sender {
819 self.sender
820 }
821}
822
823#[cfg(feature = "extensions-draft")]
824#[derive(PartialEq, Debug)]
826pub struct QueuedAppEphemeralProposal<'a> {
827 app_ephemeral_proposal: &'a AppEphemeralProposal,
828 sender: &'a Sender,
829}
830#[cfg(feature = "extensions-draft")]
831#[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 pub fn app_ephemeral_proposal(&self) -> &AppEphemeralProposal {
842 self.app_ephemeral_proposal
843 }
844
845 pub fn sender(&self) -> &Sender {
847 self.sender
848 }
849}
850#[cfg(feature = "extensions-draft")]
851impl QueuedAppDataUpdateProposal<'_> {
852 pub fn app_data_update_proposal(&self) -> &AppDataUpdateProposal {
854 self.app_data_update_proposal
855 }
856
857 pub fn sender(&self) -> &Sender {
859 self.sender
860 }
861}