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#[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 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 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#[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 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 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 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 pub fn proposal(&self) -> &Proposal {
139 &self.proposal
140 }
141 pub(crate) fn proposal_reference(&self) -> ProposalRef {
143 self.proposal_reference.clone()
144 }
145 pub fn proposal_or_ref_type(&self) -> ProposalOrRefType {
147 self.proposal_or_ref_type
148 }
149 pub fn sender(&self) -> &Sender {
151 &self.sender
152 }
153}
154
155struct 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 fn add(&mut self, proposal_ref: ProposalRef) {
173 if self.proposal_refs.insert(proposal_ref.clone()) {
176 self.ordered_proposal_refs.push(proposal_ref);
177 }
178 }
179
180 fn iter(&self) -> impl Iterator<Item = &ProposalRef> {
183 self.ordered_proposal_refs.iter()
184 }
185}
186
187#[derive(Default, Debug, Serialize, Deserialize)]
193#[cfg_attr(any(test, feature = "test-utils"), derive(Clone, PartialEq))]
194pub(crate) struct ProposalQueue {
195 proposal_references: Vec<ProposalRef>,
198 #[serde(with = "vector_converter")]
201 queued_proposals: HashMap<ProposalRef, QueuedProposal>,
202}
203
204impl ProposalQueue {
205 pub(crate) fn is_empty(&self) -> bool {
208 self.proposal_references.is_empty()
209 }
210
211 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 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 let mut proposal_queue = ProposalQueue::default();
235
236 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 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 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 pub fn get(&self, proposal_reference: &ProposalRef) -> Option<&QueuedProposal> {
280 self.queued_proposals.get(proposal_reference)
281 }
282
283 pub(crate) fn add(&mut self, queued_proposal: QueuedProposal) {
285 let proposal_reference = queued_proposal.proposal_reference();
286 if let Entry::Vacant(entry) = self.queued_proposals.entry(proposal_reference.clone()) {
288 self.proposal_references.push(proposal_reference);
290 entry.insert(queued_proposal);
292 }
293 }
294
295 pub(crate) fn filtered_by_type(
298 &self,
299 proposal_type: ProposalType,
300 ) -> impl Iterator<Item = &QueuedProposal> {
301 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 pub(crate) fn queued_proposals(&self) -> impl Iterator<Item = &QueuedProposal> {
314 self.proposal_references
316 .iter()
317 .filter_map(move |reference| self.get(reference))
318 }
319
320 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 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 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 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 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 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 match member_specific_proposals.entry(member) {
427 Entry::Vacant(vacant_entry) => {
429 vacant_entry.insert(proposal);
430 }
431 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 Entry::Occupied(_) => {}
443 }
444 };
445
446 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 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 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 }
497 Proposal::ExternalInit(_) => {
498 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 valid_proposals.add(queued_proposal.proposal_reference());
518 }
519 }
520 }
521
522 for proposal in member_specific_proposals.values() {
524 valid_proposals.add(proposal.proposal_reference());
525 }
526
527 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 pub(crate) fn filter_proposals_without_inline(
562 iter: impl IntoIterator<Item = QueuedProposal>,
563 own_index: LeafNodeIndex,
564 ) -> Result<(Self, bool), ProposalQueueError> {
565 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 match member_specific_proposals.entry(member) {
578 Entry::Vacant(vacant_entry) => {
580 vacant_entry.insert(proposal);
581 }
582 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 Entry::Occupied(_) => {}
594 }
595 };
596
597 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 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 }
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 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 valid_proposals.add(queued_proposal.proposal_reference());
650 }
651 }
652 }
653
654 for proposal in member_specific_proposals.values() {
656 valid_proposals.add(proposal.proposal_reference());
657 }
658
659 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 #[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 pub(crate) fn commit_list(&self) -> Vec<ProposalOrRef> {
685 self.proposal_references
687 .iter()
688 .filter_map(|proposal_reference| self.queued_proposals.get(proposal_reference))
689 .map(|queued_proposal| {
690 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#[derive(PartialEq, Debug)]
742pub struct QueuedAddProposal<'a> {
743 add_proposal: &'a AddProposal,
744 sender: &'a Sender,
745}
746
747impl QueuedAddProposal<'_> {
748 pub fn add_proposal(&self) -> &AddProposal {
750 self.add_proposal
751 }
752
753 pub fn sender(&self) -> &Sender {
755 self.sender
756 }
757}
758
759#[derive(PartialEq, Eq, Debug)]
761pub struct QueuedRemoveProposal<'a> {
762 remove_proposal: &'a RemoveProposal,
763 sender: &'a Sender,
764}
765
766impl QueuedRemoveProposal<'_> {
767 pub fn remove_proposal(&self) -> &RemoveProposal {
769 self.remove_proposal
770 }
771
772 pub fn sender(&self) -> &Sender {
774 self.sender
775 }
776}
777
778#[derive(PartialEq, Eq, Debug)]
780pub struct QueuedUpdateProposal<'a> {
781 update_proposal: &'a UpdateProposal,
782 sender: &'a Sender,
783}
784
785impl QueuedUpdateProposal<'_> {
786 pub fn update_proposal(&self) -> &UpdateProposal {
788 self.update_proposal
789 }
790
791 pub fn sender(&self) -> &Sender {
793 self.sender
794 }
795}
796
797#[derive(PartialEq, Eq, Debug)]
799pub struct QueuedPskProposal<'a> {
800 psk_proposal: &'a PreSharedKeyProposal,
801 sender: &'a Sender,
802}
803
804impl QueuedPskProposal<'_> {
805 pub fn psk_proposal(&self) -> &PreSharedKeyProposal {
807 self.psk_proposal
808 }
809
810 pub fn sender(&self) -> &Sender {
812 self.sender
813 }
814}