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, Clone)]
21pub(crate) struct SelfRemoveInStore {
22 pub(crate) sender: LeafNodeIndex,
23 pub(crate) proposal_ref: ProposalRef,
24}
25
26#[derive(Debug, Default, Serialize, Deserialize, PartialEq)]
29#[cfg_attr(any(test, feature = "test-utils"), derive(Clone))]
30pub struct ProposalStore {
31 queued_proposals: Vec<QueuedProposal>,
32}
33
34impl ProposalStore {
35 pub fn new() -> Self {
37 Self {
38 queued_proposals: Vec::new(),
39 }
40 }
41 #[cfg(test)]
42 pub(crate) fn from_queued_proposal(queued_proposal: QueuedProposal) -> Self {
43 Self {
44 queued_proposals: vec![queued_proposal],
45 }
46 }
47 pub(crate) fn add(&mut self, queued_proposal: QueuedProposal) {
48 self.queued_proposals.push(queued_proposal);
49 }
50 pub(crate) fn proposals(&self) -> impl Iterator<Item = &QueuedProposal> {
51 self.queued_proposals.iter()
52 }
53 pub(crate) fn is_empty(&self) -> bool {
54 self.queued_proposals.is_empty()
55 }
56 pub(crate) fn empty(&mut self) {
57 self.queued_proposals.clear();
58 }
59
60 pub(crate) fn remove(&mut self, proposal_ref: &ProposalRef) -> Option<()> {
63 let index = self
64 .queued_proposals
65 .iter()
66 .position(|p| &p.proposal_reference() == proposal_ref)?;
67 self.queued_proposals.remove(index);
68 Some(())
69 }
70
71 pub(crate) fn self_removes(&self) -> Vec<SelfRemoveInStore> {
72 self.queued_proposals
73 .iter()
74 .filter_map(|queued_proposal| {
75 match (queued_proposal.proposal(), queued_proposal.sender()) {
76 (Proposal::SelfRemove, Sender::Member(sender_index)) => {
77 Some(SelfRemoveInStore {
78 sender: *sender_index,
79 proposal_ref: queued_proposal.proposal_reference(),
80 })
81 }
82 _ => None,
83 }
84 })
85 .collect()
86 }
87}
88
89#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
92pub struct QueuedProposal {
93 proposal: Proposal,
94 proposal_reference: ProposalRef,
95 sender: Sender,
96 proposal_or_ref_type: ProposalOrRefType,
97}
98
99impl QueuedProposal {
100 pub(crate) fn from_authenticated_content_by_ref(
102 ciphersuite: Ciphersuite,
103 crypto: &impl OpenMlsCrypto,
104 public_message: AuthenticatedContent,
105 ) -> Result<Self, LibraryError> {
106 Self::from_authenticated_content(
107 ciphersuite,
108 crypto,
109 public_message,
110 ProposalOrRefType::Reference,
111 )
112 }
113
114 pub(crate) fn from_authenticated_content(
116 ciphersuite: Ciphersuite,
117 crypto: &impl OpenMlsCrypto,
118 public_message: AuthenticatedContent,
119 proposal_or_ref_type: ProposalOrRefType,
120 ) -> Result<Self, LibraryError> {
121 let proposal_reference =
122 ProposalRef::from_authenticated_content_by_ref(crypto, ciphersuite, &public_message)
123 .map_err(|_| LibraryError::custom("Could not calculate `ProposalRef`."))?;
124
125 let (body, sender) = public_message.into_body_and_sender();
126
127 let proposal = match body {
128 FramedContentBody::Proposal(p) => p,
129 _ => return Err(LibraryError::custom("Wrong content type")),
130 };
131
132 Ok(Self {
133 proposal,
134 proposal_reference,
135 sender,
136 proposal_or_ref_type,
137 })
138 }
139
140 pub(crate) fn from_proposal_and_sender(
146 ciphersuite: Ciphersuite,
147 crypto: &impl OpenMlsCrypto,
148 proposal: Proposal,
149 sender: &Sender,
150 ) -> Result<Self, LibraryError> {
151 let proposal_reference = ProposalRef::from_raw_proposal(ciphersuite, crypto, &proposal)?;
152 Ok(Self {
153 proposal,
154 proposal_reference,
155 sender: sender.clone(),
156 proposal_or_ref_type: ProposalOrRefType::Proposal,
157 })
158 }
159
160 pub fn proposal(&self) -> &Proposal {
162 &self.proposal
163 }
164 pub(crate) fn proposal_reference(&self) -> ProposalRef {
166 self.proposal_reference.clone()
167 }
168 pub fn proposal_or_ref_type(&self) -> ProposalOrRefType {
170 self.proposal_or_ref_type
171 }
172 pub fn sender(&self) -> &Sender {
174 &self.sender
175 }
176}
177
178struct OrderedProposalRefs {
181 proposal_refs: HashSet<ProposalRef>,
182 ordered_proposal_refs: Vec<ProposalRef>,
183}
184
185impl OrderedProposalRefs {
186 fn new() -> Self {
187 Self {
188 proposal_refs: HashSet::new(),
189 ordered_proposal_refs: Vec::new(),
190 }
191 }
192
193 fn add(&mut self, proposal_ref: ProposalRef) {
196 if self.proposal_refs.insert(proposal_ref.clone()) {
199 self.ordered_proposal_refs.push(proposal_ref);
200 }
201 }
202
203 fn iter(&self) -> impl Iterator<Item = &ProposalRef> {
206 self.ordered_proposal_refs.iter()
207 }
208}
209
210#[derive(Default, Debug, Serialize, Deserialize)]
216#[cfg_attr(any(test, feature = "test-utils"), derive(Clone, PartialEq))]
217pub(crate) struct ProposalQueue {
218 proposal_references: Vec<ProposalRef>,
221 #[serde(with = "vector_converter")]
224 queued_proposals: HashMap<ProposalRef, QueuedProposal>,
225}
226
227impl ProposalQueue {
228 pub(crate) fn is_empty(&self) -> bool {
231 self.proposal_references.is_empty()
232 }
233
234 pub(crate) fn from_committed_proposals(
239 ciphersuite: Ciphersuite,
240 crypto: &impl OpenMlsCrypto,
241 committed_proposals: Vec<ProposalOrRef>,
242 proposal_store: &ProposalStore,
243 sender: &Sender,
244 ) -> Result<Self, FromCommittedProposalsError> {
245 log::debug!("from_committed_proposals");
246 let mut proposals_by_reference_queue: HashMap<ProposalRef, QueuedProposal> = HashMap::new();
249 for queued_proposal in proposal_store.proposals() {
250 proposals_by_reference_queue.insert(
251 queued_proposal.proposal_reference(),
252 queued_proposal.clone(),
253 );
254 }
255 log::trace!(" known proposals:\n{proposals_by_reference_queue:#?}");
256 let mut proposal_queue = ProposalQueue::default();
258
259 log::trace!(" committed proposals ...");
261 for proposal_or_ref in committed_proposals.into_iter() {
262 log::trace!(" proposal_or_ref:\n{proposal_or_ref:#?}");
263 let queued_proposal = match proposal_or_ref {
264 ProposalOrRef::Proposal(proposal) => {
265 if let Proposal::Remove(ref remove_proposal) = proposal {
267 if let Sender::Member(leaf_index) = sender {
268 if remove_proposal.removed() == *leaf_index {
269 return Err(FromCommittedProposalsError::SelfRemoval);
270 }
271 }
272 }
273
274 QueuedProposal::from_proposal_and_sender(ciphersuite, crypto, proposal, sender)?
275 }
276 ProposalOrRef::Reference(ref proposal_reference) => {
277 match proposals_by_reference_queue.get(proposal_reference) {
278 Some(queued_proposal) => {
279 if let Proposal::Remove(ref remove_proposal) = queued_proposal.proposal
281 {
282 if let Sender::Member(leaf_index) = sender {
283 if remove_proposal.removed() == *leaf_index {
284 return Err(FromCommittedProposalsError::SelfRemoval);
285 }
286 }
287 }
288
289 queued_proposal.clone()
290 }
291 None => return Err(FromCommittedProposalsError::ProposalNotFound),
292 }
293 }
294 };
295 proposal_queue.add(queued_proposal);
296 }
297
298 Ok(proposal_queue)
299 }
300
301 pub fn get(&self, proposal_reference: &ProposalRef) -> Option<&QueuedProposal> {
303 self.queued_proposals.get(proposal_reference)
304 }
305
306 pub(crate) fn add(&mut self, queued_proposal: QueuedProposal) {
308 let proposal_reference = queued_proposal.proposal_reference();
309 if let Entry::Vacant(entry) = self.queued_proposals.entry(proposal_reference.clone()) {
311 self.proposal_references.push(proposal_reference);
313 entry.insert(queued_proposal);
315 }
316 }
317
318 pub(crate) fn filtered_by_type(
321 &self,
322 proposal_type: ProposalType,
323 ) -> impl Iterator<Item = &QueuedProposal> {
324 self.proposal_references
326 .iter()
327 .filter(move |&pr| match self.queued_proposals.get(pr) {
328 Some(p) => p.proposal.is_type(proposal_type),
329 None => false,
330 })
331 .filter_map(move |reference| self.get(reference))
332 }
333
334 pub(crate) fn queued_proposals(&self) -> impl Iterator<Item = &QueuedProposal> {
337 self.proposal_references
339 .iter()
340 .filter_map(move |reference| self.get(reference))
341 }
342
343 pub(crate) fn add_proposals(&self) -> impl Iterator<Item = QueuedAddProposal<'_>> {
346 self.queued_proposals().filter_map(|queued_proposal| {
347 if let Proposal::Add(add_proposal) = queued_proposal.proposal() {
348 let sender = queued_proposal.sender();
349 Some(QueuedAddProposal {
350 add_proposal,
351 sender,
352 })
353 } else {
354 None
355 }
356 })
357 }
358
359 pub(crate) fn remove_proposals(&self) -> impl Iterator<Item = QueuedRemoveProposal<'_>> {
362 self.queued_proposals().filter_map(|queued_proposal| {
363 if let Proposal::Remove(remove_proposal) = queued_proposal.proposal() {
364 let sender = queued_proposal.sender();
365 Some(QueuedRemoveProposal {
366 remove_proposal,
367 sender,
368 })
369 } else {
370 None
371 }
372 })
373 }
374
375 pub(crate) fn update_proposals(&self) -> impl Iterator<Item = QueuedUpdateProposal<'_>> {
378 self.queued_proposals().filter_map(|queued_proposal| {
379 if let Proposal::Update(update_proposal) = queued_proposal.proposal() {
380 let sender = queued_proposal.sender();
381 Some(QueuedUpdateProposal {
382 update_proposal,
383 sender,
384 })
385 } else {
386 None
387 }
388 })
389 }
390
391 pub(crate) fn psk_proposals(&self) -> impl Iterator<Item = QueuedPskProposal<'_>> {
394 self.queued_proposals().filter_map(|queued_proposal| {
395 if let Proposal::PreSharedKey(psk_proposal) = queued_proposal.proposal() {
396 let sender = queued_proposal.sender();
397 Some(QueuedPskProposal {
398 psk_proposal,
399 sender,
400 })
401 } else {
402 None
403 }
404 })
405 }
406
407 pub(crate) fn filter_proposals(
430 iter: impl IntoIterator<Item = QueuedProposal>,
431 own_index: LeafNodeIndex,
432 ) -> Result<(Self, bool), ProposalQueueError> {
433 let mut adds: OrderedProposalRefs = OrderedProposalRefs::new();
436 let mut valid_proposals: OrderedProposalRefs = OrderedProposalRefs::new();
437 let mut proposal_pool: HashMap<ProposalRef, QueuedProposal> = HashMap::new();
438 let mut contains_own_updates = false;
439 let mut contains_external_init = false;
440
441 let mut member_specific_proposals: HashMap<LeafNodeIndex, QueuedProposal> = HashMap::new();
442 let mut register_member_specific_proposal =
443 |member: LeafNodeIndex, proposal: QueuedProposal| {
444 match member_specific_proposals.entry(member) {
446 Entry::Vacant(vacant_entry) => {
448 vacant_entry.insert(proposal);
449 }
450 Entry::Occupied(mut occupied_entry)
453 if occupied_entry
454 .get()
455 .proposal()
456 .has_lower_priority_than(&proposal.proposal) =>
457 {
458 occupied_entry.insert(proposal);
459 }
460 Entry::Occupied(_) => {}
462 }
463 };
464
465 for queued_proposal in iter {
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 #[cfg(test)]
542 pub(crate) fn contains(&self, proposal_reference_list: &[ProposalRef]) -> bool {
543 for proposal_reference in proposal_reference_list {
544 if !self.queued_proposals.contains_key(proposal_reference) {
545 return false;
546 }
547 }
548 true
549 }
550
551 pub(crate) fn commit_list(&self) -> Vec<ProposalOrRef> {
553 self.proposal_references
555 .iter()
556 .filter_map(|proposal_reference| self.queued_proposals.get(proposal_reference))
557 .map(|queued_proposal| {
558 match queued_proposal.proposal_or_ref_type {
560 ProposalOrRefType::Proposal => {
561 ProposalOrRef::Proposal(queued_proposal.proposal.clone())
562 }
563 ProposalOrRefType::Reference => {
564 ProposalOrRef::Reference(queued_proposal.proposal_reference.clone())
565 }
566 }
567 })
568 .collect::<Vec<ProposalOrRef>>()
569 }
570}
571
572impl Extend<QueuedProposal> for ProposalQueue {
573 fn extend<T: IntoIterator<Item = QueuedProposal>>(&mut self, iter: T) {
574 for proposal in iter {
575 self.add(proposal)
576 }
577 }
578}
579
580impl IntoIterator for ProposalQueue {
581 type Item = QueuedProposal;
582
583 type IntoIter = std::collections::hash_map::IntoValues<ProposalRef, QueuedProposal>;
584
585 fn into_iter(self) -> Self::IntoIter {
586 self.queued_proposals.into_values()
587 }
588}
589
590impl<'a> IntoIterator for &'a ProposalQueue {
591 type Item = &'a QueuedProposal;
592
593 type IntoIter = std::collections::hash_map::Values<'a, ProposalRef, QueuedProposal>;
594
595 fn into_iter(self) -> Self::IntoIter {
596 self.queued_proposals.values()
597 }
598}
599
600impl FromIterator<QueuedProposal> for ProposalQueue {
601 fn from_iter<T: IntoIterator<Item = QueuedProposal>>(iter: T) -> Self {
602 let mut out = Self::default();
603 out.extend(iter);
604 out
605 }
606}
607
608#[derive(PartialEq, Debug)]
610pub struct QueuedAddProposal<'a> {
611 add_proposal: &'a AddProposal,
612 sender: &'a Sender,
613}
614
615impl QueuedAddProposal<'_> {
616 pub fn add_proposal(&self) -> &AddProposal {
618 self.add_proposal
619 }
620
621 pub fn sender(&self) -> &Sender {
623 self.sender
624 }
625}
626
627#[derive(PartialEq, Eq, Debug)]
629pub struct QueuedRemoveProposal<'a> {
630 remove_proposal: &'a RemoveProposal,
631 sender: &'a Sender,
632}
633
634impl QueuedRemoveProposal<'_> {
635 pub fn remove_proposal(&self) -> &RemoveProposal {
637 self.remove_proposal
638 }
639
640 pub fn sender(&self) -> &Sender {
642 self.sender
643 }
644}
645
646#[derive(PartialEq, Eq, Debug)]
648pub struct QueuedUpdateProposal<'a> {
649 update_proposal: &'a UpdateProposal,
650 sender: &'a Sender,
651}
652
653impl QueuedUpdateProposal<'_> {
654 pub fn update_proposal(&self) -> &UpdateProposal {
656 self.update_proposal
657 }
658
659 pub fn sender(&self) -> &Sender {
661 self.sender
662 }
663}
664
665#[derive(PartialEq, Eq, Debug)]
667pub struct QueuedPskProposal<'a> {
668 psk_proposal: &'a PreSharedKeyProposal,
669 sender: &'a Sender,
670}
671
672impl QueuedPskProposal<'_> {
673 pub fn psk_proposal(&self) -> &PreSharedKeyProposal {
675 self.psk_proposal
676 }
677
678 pub fn sender(&self) -> &Sender {
680 self.sender
681 }
682}