1use std::{
19 collections::{BTreeMap, HashMap},
20 hash::Hash,
21};
22
23use ruma::{OwnedEventId, OwnedRoomId, RoomId};
24
25use super::{ChunkContent, ChunkIdentifierGenerator, RawChunk};
26use crate::{
27 deserialized_responses::TimelineEvent,
28 linked_chunk::{
29 ChunkIdentifier, ChunkMetadata, LinkedChunkId, OwnedLinkedChunkId, Position, Update,
30 },
31};
32
33#[derive(Debug, PartialEq)]
35struct ChunkRow {
36 linked_chunk_id: OwnedLinkedChunkId,
37 previous_chunk: Option<ChunkIdentifier>,
38 chunk: ChunkIdentifier,
39 next_chunk: Option<ChunkIdentifier>,
40}
41
42#[derive(Debug, PartialEq)]
44struct ItemRow<ItemId, Gap> {
45 linked_chunk_id: OwnedLinkedChunkId,
46 position: Position,
47 item: Either<ItemId, Gap>,
48}
49
50#[derive(Debug, PartialEq)]
52enum Either<Item, Gap> {
53 Item(Item),
55
56 Gap(Gap),
58}
59
60#[derive(Debug)]
79pub struct RelationalLinkedChunk<ItemId, Item, Gap> {
80 chunks: Vec<ChunkRow>,
82
83 items_chunks: Vec<ItemRow<ItemId, Gap>>,
85
86 items: HashMap<OwnedLinkedChunkId, BTreeMap<ItemId, (Item, Option<Position>)>>,
88}
89
90pub trait IndexableItem {
93 type ItemId: Hash + PartialEq + Eq + Clone;
94
95 fn id(&self) -> Self::ItemId;
97}
98
99impl IndexableItem for TimelineEvent {
100 type ItemId = OwnedEventId;
101
102 fn id(&self) -> Self::ItemId {
103 self.event_id()
104 .expect("all events saved into a relational linked chunk must have a valid event id")
105 }
106}
107
108impl<ItemId, Item, Gap> RelationalLinkedChunk<ItemId, Item, Gap>
109where
110 Item: IndexableItem<ItemId = ItemId>,
111 ItemId: Hash + PartialEq + Eq + Clone + Ord,
112{
113 pub fn new() -> Self {
115 Self { chunks: Vec::new(), items_chunks: Vec::new(), items: HashMap::new() }
116 }
117
118 pub fn clear(&mut self) {
120 self.chunks.clear();
121 self.items_chunks.clear();
122 self.items.clear();
123 }
124
125 pub fn apply_updates(
128 &mut self,
129 linked_chunk_id: LinkedChunkId<'_>,
130 updates: Vec<Update<Item, Gap>>,
131 ) {
132 for update in updates {
133 match update {
134 Update::NewItemsChunk { previous, new, next } => {
135 Self::insert_chunk(&mut self.chunks, linked_chunk_id, previous, new, next);
136 }
137
138 Update::NewGapChunk { previous, new, next, gap } => {
139 Self::insert_chunk(&mut self.chunks, linked_chunk_id, previous, new, next);
140 self.items_chunks.push(ItemRow {
141 linked_chunk_id: linked_chunk_id.to_owned(),
142 position: Position::new(new, 0),
143 item: Either::Gap(gap),
144 });
145 }
146
147 Update::RemoveChunk(chunk_identifier) => {
148 Self::remove_chunk(&mut self.chunks, linked_chunk_id, chunk_identifier);
149
150 let indices_to_remove = self
151 .items_chunks
152 .iter()
153 .enumerate()
154 .filter_map(
155 |(
156 nth,
157 ItemRow {
158 linked_chunk_id: linked_chunk_id_candidate,
159 position,
160 ..
161 },
162 )| {
163 (linked_chunk_id == linked_chunk_id_candidate
164 && position.chunk_identifier() == chunk_identifier)
165 .then_some(nth)
166 },
167 )
168 .collect::<Vec<_>>();
169
170 for index_to_remove in indices_to_remove.into_iter().rev() {
171 self.items_chunks.remove(index_to_remove);
172 }
173 }
174
175 Update::PushItems { mut at, items } => {
176 for item in items {
177 let item_id = item.id();
178 self.items
179 .entry(linked_chunk_id.to_owned())
180 .or_default()
181 .insert(item_id.clone(), (item, Some(at)));
182 self.items_chunks.push(ItemRow {
183 linked_chunk_id: linked_chunk_id.to_owned(),
184 position: at,
185 item: Either::Item(item_id),
186 });
187 at.increment_index();
188 }
189 }
190
191 Update::ReplaceItem { at, item } => {
192 let existing = self
193 .items_chunks
194 .iter_mut()
195 .find(|item| item.position == at)
196 .expect("trying to replace at an unknown position");
197 assert!(
198 matches!(existing.item, Either::Item(..)),
199 "trying to replace a gap with an item"
200 );
201 let item_id = item.id();
202 self.items
203 .entry(linked_chunk_id.to_owned())
204 .or_default()
205 .insert(item_id.clone(), (item, Some(at)));
206 existing.item = Either::Item(item_id);
207 }
208
209 Update::RemoveItem { at } => {
210 let mut entry_to_remove = None;
211
212 for (
213 nth,
214 ItemRow { linked_chunk_id: linked_chunk_id_candidate, position, .. },
215 ) in self.items_chunks.iter_mut().enumerate()
216 {
217 if linked_chunk_id != &*linked_chunk_id_candidate {
219 continue;
220 }
221
222 if *position == at {
224 debug_assert!(entry_to_remove.is_none(), "Found the same entry twice");
225
226 entry_to_remove = Some(nth);
227 }
228
229 if position.chunk_identifier() == at.chunk_identifier()
231 && position.index() > at.index()
232 {
233 position.decrement_index();
234 }
235 }
236
237 self.items_chunks.remove(entry_to_remove.expect("Remove an unknown item"));
238 }
240
241 Update::DetachLastItems { at } => {
242 let indices_to_remove = self
243 .items_chunks
244 .iter()
245 .enumerate()
246 .filter_map(
247 |(
248 nth,
249 ItemRow {
250 linked_chunk_id: linked_chunk_id_candidate,
251 position,
252 ..
253 },
254 )| {
255 (linked_chunk_id == linked_chunk_id_candidate
256 && position.chunk_identifier() == at.chunk_identifier()
257 && position.index() >= at.index())
258 .then_some(nth)
259 },
260 )
261 .collect::<Vec<_>>();
262
263 for index_to_remove in indices_to_remove.into_iter().rev() {
264 self.items_chunks.remove(index_to_remove);
265 }
266 }
267
268 Update::StartReattachItems | Update::EndReattachItems => { }
269
270 Update::Clear => {
271 self.chunks.retain(|chunk| chunk.linked_chunk_id != linked_chunk_id);
272 self.items_chunks.retain(|chunk| chunk.linked_chunk_id != linked_chunk_id);
273 }
275 }
276 }
277 }
278
279 fn insert_chunk(
280 chunks: &mut Vec<ChunkRow>,
281 linked_chunk_id: LinkedChunkId<'_>,
282 previous: Option<ChunkIdentifier>,
283 new: ChunkIdentifier,
284 next: Option<ChunkIdentifier>,
285 ) {
286 if let Some(previous) = previous {
288 let entry_for_previous_chunk = chunks
289 .iter_mut()
290 .find(|ChunkRow { linked_chunk_id: linked_chunk_id_candidate, chunk, .. }| {
291 linked_chunk_id == linked_chunk_id_candidate && *chunk == previous
292 })
293 .expect("Previous chunk should be present");
294
295 entry_for_previous_chunk.next_chunk = Some(new);
297 }
298
299 if let Some(next) = next {
301 let entry_for_next_chunk = chunks
302 .iter_mut()
303 .find(|ChunkRow { linked_chunk_id: linked_chunk_id_candidate, chunk, .. }| {
304 linked_chunk_id == linked_chunk_id_candidate && *chunk == next
305 })
306 .expect("Next chunk should be present");
307
308 entry_for_next_chunk.previous_chunk = Some(new);
310 }
311
312 chunks.push(ChunkRow {
314 linked_chunk_id: linked_chunk_id.to_owned(),
315 previous_chunk: previous,
316 chunk: new,
317 next_chunk: next,
318 });
319 }
320
321 fn remove_chunk(
322 chunks: &mut Vec<ChunkRow>,
323 linked_chunk_id: LinkedChunkId<'_>,
324 chunk_to_remove: ChunkIdentifier,
325 ) {
326 let entry_nth_to_remove = chunks
327 .iter()
328 .enumerate()
329 .find_map(
330 |(nth, ChunkRow { linked_chunk_id: linked_chunk_id_candidate, chunk, .. })| {
331 (linked_chunk_id == linked_chunk_id_candidate && *chunk == chunk_to_remove)
332 .then_some(nth)
333 },
334 )
335 .expect("Remove an unknown chunk");
336
337 let ChunkRow { linked_chunk_id, previous_chunk: previous, next_chunk: next, .. } =
338 chunks.remove(entry_nth_to_remove);
339
340 if let Some(previous) = previous {
342 let entry_for_previous_chunk = chunks
343 .iter_mut()
344 .find(|ChunkRow { linked_chunk_id: linked_chunk_id_candidate, chunk, .. }| {
345 &linked_chunk_id == linked_chunk_id_candidate && *chunk == previous
346 })
347 .expect("Previous chunk should be present");
348
349 entry_for_previous_chunk.next_chunk = next;
351 }
352
353 if let Some(next) = next {
355 let entry_for_next_chunk = chunks
356 .iter_mut()
357 .find(|ChunkRow { linked_chunk_id: linked_chunk_id_candidate, chunk, .. }| {
358 &linked_chunk_id == linked_chunk_id_candidate && *chunk == next
359 })
360 .expect("Next chunk should be present");
361
362 entry_for_next_chunk.previous_chunk = previous;
364 }
365 }
366
367 pub fn unordered_linked_chunk_items<'a>(
370 &'a self,
371 target: &OwnedLinkedChunkId,
372 ) -> impl Iterator<Item = (&'a Item, Position)> + use<'a, ItemId, Item, Gap> {
373 self.items.get(target).into_iter().flat_map(|items| {
374 items.values().filter_map(|(item, pos)| pos.map(|pos| (item, pos)))
376 })
377 }
378
379 pub fn items<'a>(
387 &'a self,
388 room_id: &'a RoomId,
389 ) -> impl Iterator<Item = (&'a Item, Option<Position>)> {
390 self.items
391 .iter()
392 .filter_map(move |(linked_chunk_id, items)| {
393 (linked_chunk_id.room_id() == room_id).then_some(items)
394 })
395 .flat_map(|items| items.values().map(|(item, pos)| (item, *pos)))
396 }
397
398 pub fn save_item(&mut self, room_id: OwnedRoomId, item: Item) {
400 let id = item.id();
401 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id);
402
403 let map = self.items.entry(linked_chunk_id).or_default();
404 if let Some(prev_value) = map.get_mut(&id) {
405 prev_value.0 = item;
407 } else {
408 map.insert(id, (item, None));
409 }
410 }
411}
412
413impl<ItemId, Item, Gap> RelationalLinkedChunk<ItemId, Item, Gap>
414where
415 Gap: Clone,
416 Item: Clone,
417 ItemId: Hash + PartialEq + Eq + Ord,
418{
419 #[doc(hidden)]
424 pub fn load_all_chunks(
425 &self,
426 linked_chunk_id: LinkedChunkId<'_>,
427 ) -> Result<Vec<RawChunk<Item, Gap>>, String> {
428 self.chunks
429 .iter()
430 .filter(|chunk| chunk.linked_chunk_id == linked_chunk_id)
431 .map(|chunk_row| load_raw_chunk(self, chunk_row, linked_chunk_id))
432 .collect::<Result<Vec<_>, String>>()
433 }
434
435 #[doc(hidden)]
440 pub fn load_all_chunks_metadata(
441 &self,
442 linked_chunk_id: LinkedChunkId<'_>,
443 ) -> Result<Vec<ChunkMetadata>, String> {
444 self.chunks
445 .iter()
446 .filter(|chunk| chunk.linked_chunk_id == linked_chunk_id)
447 .map(|chunk_row| load_raw_chunk_metadata(self, chunk_row, linked_chunk_id))
448 .collect::<Result<Vec<_>, String>>()
449 }
450
451 pub fn load_last_chunk(
452 &self,
453 linked_chunk_id: LinkedChunkId<'_>,
454 ) -> Result<(Option<RawChunk<Item, Gap>>, ChunkIdentifierGenerator), String> {
455 let chunk_identifier_generator = match self
457 .chunks
458 .iter()
459 .filter_map(|chunk_row| {
460 (chunk_row.linked_chunk_id == linked_chunk_id).then_some(chunk_row.chunk)
461 })
462 .max()
463 {
464 Some(last_chunk_identifier) => {
465 ChunkIdentifierGenerator::new_from_previous_chunk_identifier(last_chunk_identifier)
466 }
467 None => ChunkIdentifierGenerator::new_from_scratch(),
468 };
469
470 let mut number_of_chunks = 0;
472 let mut chunk_row = None;
473
474 for chunk_row_candidate in &self.chunks {
475 if chunk_row_candidate.linked_chunk_id == linked_chunk_id {
476 number_of_chunks += 1;
477
478 if chunk_row_candidate.next_chunk.is_none() {
479 chunk_row = Some(chunk_row_candidate);
480
481 break;
482 }
483 }
484 }
485
486 let chunk_row = match chunk_row {
487 Some(chunk_row) => chunk_row,
489
490 None if number_of_chunks == 0 => {
493 return Ok((None, chunk_identifier_generator));
494 }
495
496 None => {
501 return Err(
502 "last chunk is not found but chunks exist: the linked chunk contains a cycle"
503 .to_owned(),
504 );
505 }
506 };
507
508 load_raw_chunk(self, chunk_row, linked_chunk_id)
510 .map(|raw_chunk| (Some(raw_chunk), chunk_identifier_generator))
511 }
512
513 pub fn load_previous_chunk(
514 &self,
515 linked_chunk_id: LinkedChunkId<'_>,
516 before_chunk_identifier: ChunkIdentifier,
517 ) -> Result<Option<RawChunk<Item, Gap>>, String> {
518 let Some(chunk_row) = self.chunks.iter().find(|chunk_row| {
520 chunk_row.linked_chunk_id == linked_chunk_id
521 && chunk_row.next_chunk == Some(before_chunk_identifier)
522 }) else {
523 return Ok(None);
525 };
526
527 load_raw_chunk(self, chunk_row, linked_chunk_id).map(Some)
529 }
530}
531
532impl<ItemId, Item, Gap> Default for RelationalLinkedChunk<ItemId, Item, Gap>
533where
534 Item: IndexableItem<ItemId = ItemId>,
535 ItemId: Hash + PartialEq + Eq + Clone + Ord,
536{
537 fn default() -> Self {
538 Self::new()
539 }
540}
541
542fn load_raw_chunk<ItemId, Item, Gap>(
547 relational_linked_chunk: &RelationalLinkedChunk<ItemId, Item, Gap>,
548 chunk_row: &ChunkRow,
549 linked_chunk_id: LinkedChunkId<'_>,
550) -> Result<RawChunk<Item, Gap>, String>
551where
552 Item: Clone,
553 Gap: Clone,
554 ItemId: Hash + PartialEq + Eq + Ord,
555{
556 let mut items = relational_linked_chunk
558 .items_chunks
559 .iter()
560 .filter(|item_row| {
561 item_row.linked_chunk_id == linked_chunk_id
562 && item_row.position.chunk_identifier() == chunk_row.chunk
563 })
564 .peekable();
565
566 let Some(first_item) = items.peek() else {
567 return Ok(RawChunk {
569 content: ChunkContent::Items(Vec::new()),
570 previous: chunk_row.previous_chunk,
571 identifier: chunk_row.chunk,
572 next: chunk_row.next_chunk,
573 });
574 };
575
576 Ok(match first_item.item {
577 Either::Item(_) => {
579 let mut collected_items = Vec::new();
581
582 for item_row in items {
583 match &item_row.item {
584 Either::Item(item_id) => {
585 collected_items.push((item_id, item_row.position.index()))
586 }
587
588 Either::Gap(_) => {
589 return Err(format!(
590 "unexpected gap in items chunk {}",
591 chunk_row.chunk.index()
592 ));
593 }
594 }
595 }
596
597 collected_items.sort_unstable_by_key(|(_item, index)| *index);
599
600 RawChunk {
601 content: ChunkContent::Items(
602 collected_items
603 .into_iter()
604 .filter_map(|(item_id, _index)| {
605 Some(
606 relational_linked_chunk
607 .items
608 .get(&linked_chunk_id.to_owned())?
609 .get(item_id)?
610 .0
611 .clone(),
612 )
613 })
614 .collect(),
615 ),
616 previous: chunk_row.previous_chunk,
617 identifier: chunk_row.chunk,
618 next: chunk_row.next_chunk,
619 }
620 }
621
622 Either::Gap(ref gap) => {
623 assert!(items.next().is_some(), "we just peeked the gap");
624
625 if items.next().is_some() {
627 return Err(format!(
628 "there shouldn't be more than one item row attached in gap chunk {}",
629 chunk_row.chunk.index()
630 ));
631 }
632
633 RawChunk {
634 content: ChunkContent::Gap(gap.clone()),
635 previous: chunk_row.previous_chunk,
636 identifier: chunk_row.chunk,
637 next: chunk_row.next_chunk,
638 }
639 }
640 })
641}
642
643fn load_raw_chunk_metadata<ItemId, Item, Gap>(
648 relational_linked_chunk: &RelationalLinkedChunk<ItemId, Item, Gap>,
649 chunk_row: &ChunkRow,
650 linked_chunk_id: LinkedChunkId<'_>,
651) -> Result<ChunkMetadata, String>
652where
653 Item: Clone,
654 Gap: Clone,
655 ItemId: Hash + PartialEq + Eq,
656{
657 let mut items = relational_linked_chunk
659 .items_chunks
660 .iter()
661 .filter(|item_row| {
662 item_row.linked_chunk_id == linked_chunk_id
663 && item_row.position.chunk_identifier() == chunk_row.chunk
664 })
665 .peekable();
666
667 let Some(first_item) = items.peek() else {
668 return Ok(ChunkMetadata {
670 num_items: 0,
671 previous: chunk_row.previous_chunk,
672 identifier: chunk_row.chunk,
673 next: chunk_row.next_chunk,
674 });
675 };
676
677 Ok(match first_item.item {
678 Either::Item(_) => {
680 let mut num_items = 0;
684 for item in items {
685 match &item.item {
686 Either::Item(_) => num_items += 1,
687 Either::Gap(_) => {
688 return Err(format!(
689 "unexpected gap in items chunk {}",
690 chunk_row.chunk.index()
691 ));
692 }
693 }
694 }
695
696 ChunkMetadata {
697 num_items,
698 previous: chunk_row.previous_chunk,
699 identifier: chunk_row.chunk,
700 next: chunk_row.next_chunk,
701 }
702 }
703
704 Either::Gap(..) => {
705 assert!(items.next().is_some(), "we just peeked the gap");
706
707 if items.next().is_some() {
709 return Err(format!(
710 "there shouldn't be more than one item row attached in gap chunk {}",
711 chunk_row.chunk.index()
712 ));
713 }
714
715 ChunkMetadata {
716 num_items: 0,
718 previous: chunk_row.previous_chunk,
719 identifier: chunk_row.chunk,
720 next: chunk_row.next_chunk,
721 }
722 }
723 })
724}
725
726#[cfg(test)]
727mod tests {
728 use std::collections::BTreeMap;
729
730 use assert_matches::assert_matches;
731 use ruma::room_id;
732
733 use super::{super::lazy_loader::from_all_chunks, ChunkIdentifier as CId, *};
734
735 impl IndexableItem for char {
736 type ItemId = char;
737
738 fn id(&self) -> Self::ItemId {
739 *self
740 }
741 }
742
743 #[test]
744 fn test_new_items_chunk() {
745 let room_id = room_id!("!r0:matrix.org");
746 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
747
748 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
749
750 relational_linked_chunk.apply_updates(
751 linked_chunk_id.as_ref(),
752 vec![
753 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
755 Update::NewItemsChunk { previous: Some(CId::new(0)), new: CId::new(1), next: None },
757 Update::NewItemsChunk { previous: None, new: CId::new(2), next: Some(CId::new(0)) },
759 Update::NewItemsChunk {
761 previous: Some(CId::new(2)),
762 new: CId::new(3),
763 next: Some(CId::new(0)),
764 },
765 ],
766 );
767
768 assert_eq!(
770 relational_linked_chunk.chunks,
771 &[
772 ChunkRow {
773 linked_chunk_id: linked_chunk_id.clone(),
774 previous_chunk: Some(CId::new(3)),
775 chunk: CId::new(0),
776 next_chunk: Some(CId::new(1))
777 },
778 ChunkRow {
779 linked_chunk_id: linked_chunk_id.clone(),
780 previous_chunk: Some(CId::new(0)),
781 chunk: CId::new(1),
782 next_chunk: None
783 },
784 ChunkRow {
785 linked_chunk_id: linked_chunk_id.clone(),
786 previous_chunk: None,
787 chunk: CId::new(2),
788 next_chunk: Some(CId::new(3))
789 },
790 ChunkRow {
791 linked_chunk_id,
792 previous_chunk: Some(CId::new(2)),
793 chunk: CId::new(3),
794 next_chunk: Some(CId::new(0))
795 },
796 ],
797 );
798
799 assert!(relational_linked_chunk.items_chunks.is_empty());
801 }
802
803 #[test]
804 fn test_new_gap_chunk() {
805 let room_id = room_id!("!r0:matrix.org");
806 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
807
808 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
809
810 relational_linked_chunk.apply_updates(
811 linked_chunk_id.as_ref(),
812 vec![
813 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
815 Update::NewGapChunk {
817 previous: Some(CId::new(0)),
818 new: CId::new(1),
819 next: None,
820 gap: (),
821 },
822 Update::NewItemsChunk { previous: Some(CId::new(1)), new: CId::new(2), next: None },
824 ],
825 );
826
827 assert_eq!(
829 relational_linked_chunk.chunks,
830 &[
831 ChunkRow {
832 linked_chunk_id: linked_chunk_id.clone(),
833 previous_chunk: None,
834 chunk: CId::new(0),
835 next_chunk: Some(CId::new(1))
836 },
837 ChunkRow {
838 linked_chunk_id: linked_chunk_id.clone(),
839 previous_chunk: Some(CId::new(0)),
840 chunk: CId::new(1),
841 next_chunk: Some(CId::new(2))
842 },
843 ChunkRow {
844 linked_chunk_id: linked_chunk_id.clone(),
845 previous_chunk: Some(CId::new(1)),
846 chunk: CId::new(2),
847 next_chunk: None
848 },
849 ],
850 );
851 assert_eq!(
853 relational_linked_chunk.items_chunks,
854 &[ItemRow {
855 linked_chunk_id,
856 position: Position::new(CId::new(1), 0),
857 item: Either::Gap(())
858 }],
859 );
860 }
861
862 #[test]
863 fn test_remove_chunk() {
864 let room_id = room_id!("!r0:matrix.org");
865 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
866
867 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
868
869 relational_linked_chunk.apply_updates(
870 linked_chunk_id.as_ref(),
871 vec![
872 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
874 Update::NewGapChunk {
876 previous: Some(CId::new(0)),
877 new: CId::new(1),
878 next: None,
879 gap: (),
880 },
881 Update::NewItemsChunk { previous: Some(CId::new(1)), new: CId::new(2), next: None },
883 Update::RemoveChunk(CId::new(1)),
885 ],
886 );
887
888 assert_eq!(
890 relational_linked_chunk.chunks,
891 &[
892 ChunkRow {
893 linked_chunk_id: linked_chunk_id.clone(),
894 previous_chunk: None,
895 chunk: CId::new(0),
896 next_chunk: Some(CId::new(2))
897 },
898 ChunkRow {
899 linked_chunk_id,
900 previous_chunk: Some(CId::new(0)),
901 chunk: CId::new(2),
902 next_chunk: None
903 },
904 ],
905 );
906
907 assert!(relational_linked_chunk.items_chunks.is_empty());
909 }
910
911 #[test]
912 fn test_push_items() {
913 let room_id = room_id!("!r0:matrix.org");
914 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
915
916 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
917
918 relational_linked_chunk.apply_updates(
919 linked_chunk_id.as_ref(),
920 vec![
921 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
923 Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['a', 'b', 'c'] },
925 Update::NewItemsChunk { previous: Some(CId::new(0)), new: CId::new(1), next: None },
927 Update::PushItems { at: Position::new(CId::new(1), 0), items: vec!['x', 'y', 'z'] },
929 Update::PushItems { at: Position::new(CId::new(0), 3), items: vec!['d', 'e'] },
931 ],
932 );
933
934 assert_eq!(
936 relational_linked_chunk.chunks,
937 &[
938 ChunkRow {
939 linked_chunk_id: linked_chunk_id.clone(),
940 previous_chunk: None,
941 chunk: CId::new(0),
942 next_chunk: Some(CId::new(1))
943 },
944 ChunkRow {
945 linked_chunk_id: linked_chunk_id.clone(),
946 previous_chunk: Some(CId::new(0)),
947 chunk: CId::new(1),
948 next_chunk: None
949 },
950 ],
951 );
952 assert_eq!(
954 relational_linked_chunk.items_chunks,
955 &[
956 ItemRow {
957 linked_chunk_id: linked_chunk_id.clone(),
958 position: Position::new(CId::new(0), 0),
959 item: Either::Item('a')
960 },
961 ItemRow {
962 linked_chunk_id: linked_chunk_id.clone(),
963 position: Position::new(CId::new(0), 1),
964 item: Either::Item('b')
965 },
966 ItemRow {
967 linked_chunk_id: linked_chunk_id.clone(),
968 position: Position::new(CId::new(0), 2),
969 item: Either::Item('c')
970 },
971 ItemRow {
972 linked_chunk_id: linked_chunk_id.clone(),
973 position: Position::new(CId::new(1), 0),
974 item: Either::Item('x')
975 },
976 ItemRow {
977 linked_chunk_id: linked_chunk_id.clone(),
978 position: Position::new(CId::new(1), 1),
979 item: Either::Item('y')
980 },
981 ItemRow {
982 linked_chunk_id: linked_chunk_id.clone(),
983 position: Position::new(CId::new(1), 2),
984 item: Either::Item('z')
985 },
986 ItemRow {
987 linked_chunk_id: linked_chunk_id.clone(),
988 position: Position::new(CId::new(0), 3),
989 item: Either::Item('d')
990 },
991 ItemRow {
992 linked_chunk_id: linked_chunk_id.clone(),
993 position: Position::new(CId::new(0), 4),
994 item: Either::Item('e')
995 },
996 ],
997 );
998 }
999
1000 #[test]
1001 fn test_remove_item() {
1002 let room_id = room_id!("!r0:matrix.org");
1003 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1004
1005 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1006
1007 relational_linked_chunk.apply_updates(
1008 linked_chunk_id.as_ref(),
1009 vec![
1010 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1012 Update::PushItems {
1014 at: Position::new(CId::new(0), 0),
1015 items: vec!['a', 'b', 'c', 'd', 'e'],
1016 },
1017 Update::RemoveItem { at: Position::new(CId::new(0), 0) },
1019 Update::RemoveItem { at: Position::new(CId::new(0), 2) },
1021 ],
1022 );
1023
1024 assert_eq!(
1026 relational_linked_chunk.chunks,
1027 &[ChunkRow {
1028 linked_chunk_id: linked_chunk_id.clone(),
1029 previous_chunk: None,
1030 chunk: CId::new(0),
1031 next_chunk: None
1032 }],
1033 );
1034 assert_eq!(
1036 relational_linked_chunk.items_chunks,
1037 &[
1038 ItemRow {
1039 linked_chunk_id: linked_chunk_id.clone(),
1040 position: Position::new(CId::new(0), 0),
1041 item: Either::Item('b')
1042 },
1043 ItemRow {
1044 linked_chunk_id: linked_chunk_id.clone(),
1045 position: Position::new(CId::new(0), 1),
1046 item: Either::Item('c')
1047 },
1048 ItemRow {
1049 linked_chunk_id: linked_chunk_id.clone(),
1050 position: Position::new(CId::new(0), 2),
1051 item: Either::Item('e')
1052 },
1053 ],
1054 );
1055 }
1056
1057 #[test]
1058 fn test_detach_last_items() {
1059 let room_id = room_id!("!r0:matrix.org");
1060 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1061
1062 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1063
1064 relational_linked_chunk.apply_updates(
1065 linked_chunk_id.as_ref(),
1066 vec![
1067 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1069 Update::NewItemsChunk { previous: Some(CId::new(0)), new: CId::new(1), next: None },
1071 Update::PushItems {
1073 at: Position::new(CId::new(0), 0),
1074 items: vec!['a', 'b', 'c', 'd', 'e'],
1075 },
1076 Update::PushItems { at: Position::new(CId::new(1), 0), items: vec!['x', 'y', 'z'] },
1078 Update::DetachLastItems { at: Position::new(CId::new(0), 2) },
1080 ],
1081 );
1082
1083 assert_eq!(
1085 relational_linked_chunk.chunks,
1086 &[
1087 ChunkRow {
1088 linked_chunk_id: linked_chunk_id.clone(),
1089 previous_chunk: None,
1090 chunk: CId::new(0),
1091 next_chunk: Some(CId::new(1))
1092 },
1093 ChunkRow {
1094 linked_chunk_id: linked_chunk_id.clone(),
1095 previous_chunk: Some(CId::new(0)),
1096 chunk: CId::new(1),
1097 next_chunk: None
1098 },
1099 ],
1100 );
1101 assert_eq!(
1103 relational_linked_chunk.items_chunks,
1104 &[
1105 ItemRow {
1106 linked_chunk_id: linked_chunk_id.clone(),
1107 position: Position::new(CId::new(0), 0),
1108 item: Either::Item('a')
1109 },
1110 ItemRow {
1111 linked_chunk_id: linked_chunk_id.clone(),
1112 position: Position::new(CId::new(0), 1),
1113 item: Either::Item('b')
1114 },
1115 ItemRow {
1116 linked_chunk_id: linked_chunk_id.clone(),
1117 position: Position::new(CId::new(1), 0),
1118 item: Either::Item('x')
1119 },
1120 ItemRow {
1121 linked_chunk_id: linked_chunk_id.clone(),
1122 position: Position::new(CId::new(1), 1),
1123 item: Either::Item('y')
1124 },
1125 ItemRow {
1126 linked_chunk_id: linked_chunk_id.clone(),
1127 position: Position::new(CId::new(1), 2),
1128 item: Either::Item('z')
1129 },
1130 ],
1131 );
1132 }
1133
1134 #[test]
1135 fn test_start_and_end_reattach_items() {
1136 let room_id = room_id!("!r0:matrix.org");
1137 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1138
1139 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1140
1141 relational_linked_chunk.apply_updates(
1142 linked_chunk_id.as_ref(),
1143 vec![Update::StartReattachItems, Update::EndReattachItems],
1144 );
1145
1146 assert!(relational_linked_chunk.chunks.is_empty());
1148 assert!(relational_linked_chunk.items_chunks.is_empty());
1149 }
1150
1151 #[test]
1152 fn test_clear() {
1153 let r0 = room_id!("!r0:matrix.org");
1154 let linked_chunk_id0 = OwnedLinkedChunkId::Room(r0.to_owned());
1155
1156 let r1 = room_id!("!r1:matrix.org");
1157 let linked_chunk_id1 = OwnedLinkedChunkId::Room(r1.to_owned());
1158
1159 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1160
1161 relational_linked_chunk.apply_updates(
1162 linked_chunk_id0.as_ref(),
1163 vec![
1164 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1166 Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['a', 'b', 'c'] },
1168 ],
1169 );
1170
1171 relational_linked_chunk.apply_updates(
1172 linked_chunk_id1.as_ref(),
1173 vec![
1174 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1176 Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['x'] },
1178 ],
1179 );
1180
1181 assert_eq!(
1183 relational_linked_chunk.chunks,
1184 &[
1185 ChunkRow {
1186 linked_chunk_id: linked_chunk_id0.to_owned(),
1187 previous_chunk: None,
1188 chunk: CId::new(0),
1189 next_chunk: None,
1190 },
1191 ChunkRow {
1192 linked_chunk_id: linked_chunk_id1.to_owned(),
1193 previous_chunk: None,
1194 chunk: CId::new(0),
1195 next_chunk: None,
1196 }
1197 ],
1198 );
1199
1200 assert_eq!(
1202 relational_linked_chunk.items_chunks,
1203 &[
1204 ItemRow {
1205 linked_chunk_id: linked_chunk_id0.to_owned(),
1206 position: Position::new(CId::new(0), 0),
1207 item: Either::Item('a')
1208 },
1209 ItemRow {
1210 linked_chunk_id: linked_chunk_id0.to_owned(),
1211 position: Position::new(CId::new(0), 1),
1212 item: Either::Item('b')
1213 },
1214 ItemRow {
1215 linked_chunk_id: linked_chunk_id0.to_owned(),
1216 position: Position::new(CId::new(0), 2),
1217 item: Either::Item('c')
1218 },
1219 ItemRow {
1220 linked_chunk_id: linked_chunk_id1.to_owned(),
1221 position: Position::new(CId::new(0), 0),
1222 item: Either::Item('x')
1223 },
1224 ],
1225 );
1226
1227 relational_linked_chunk.apply_updates(linked_chunk_id0.as_ref(), vec![Update::Clear]);
1229
1230 assert_eq!(
1232 relational_linked_chunk.chunks,
1233 &[ChunkRow {
1234 linked_chunk_id: linked_chunk_id1.to_owned(),
1235 previous_chunk: None,
1236 chunk: CId::new(0),
1237 next_chunk: None,
1238 }],
1239 );
1240
1241 assert_eq!(
1242 relational_linked_chunk.items_chunks,
1243 &[ItemRow {
1244 linked_chunk_id: linked_chunk_id1.to_owned(),
1245 position: Position::new(CId::new(0), 0),
1246 item: Either::Item('x')
1247 },],
1248 );
1249 }
1250
1251 #[test]
1252 fn test_load_empty_linked_chunk() {
1253 let room_id = room_id!("!r0:matrix.org");
1254 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1255
1256 let relational_linked_chunk = RelationalLinkedChunk::<_, char, char>::new();
1258 let result = relational_linked_chunk.load_all_chunks(linked_chunk_id.as_ref()).unwrap();
1259 assert!(result.is_empty());
1260 }
1261
1262 #[test]
1263 fn test_load_all_chunks_with_empty_items() {
1264 let room_id = room_id!("!r0:matrix.org");
1265 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1266
1267 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, char>::new();
1268
1269 relational_linked_chunk.apply_updates(
1271 linked_chunk_id.as_ref(),
1272 vec![Update::NewItemsChunk { previous: None, new: CId::new(0), next: None }],
1273 );
1274
1275 let lc = from_all_chunks::<3, _, _>(
1277 relational_linked_chunk.load_all_chunks(linked_chunk_id.as_ref()).unwrap(),
1278 )
1279 .expect("building succeeds")
1280 .expect("this leads to a non-empty linked chunk");
1281
1282 assert_items_eq!(lc, []);
1283 }
1284
1285 #[test]
1286 fn test_rebuild_linked_chunk() {
1287 let room_id = room_id!("!r0:matrix.org");
1288 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1289
1290 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, char>::new();
1291
1292 relational_linked_chunk.apply_updates(
1293 linked_chunk_id.as_ref(),
1294 vec![
1295 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1297 Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['a', 'b', 'c'] },
1299 Update::NewGapChunk {
1301 previous: Some(CId::new(0)),
1302 new: CId::new(1),
1303 next: None,
1304 gap: 'g',
1305 },
1306 Update::NewItemsChunk { previous: Some(CId::new(1)), new: CId::new(2), next: None },
1308 Update::PushItems { at: Position::new(CId::new(2), 0), items: vec!['d', 'e', 'f'] },
1310 ],
1311 );
1312
1313 let lc = from_all_chunks::<3, _, _>(
1314 relational_linked_chunk.load_all_chunks(linked_chunk_id.as_ref()).unwrap(),
1315 )
1316 .expect("building succeeds")
1317 .expect("this leads to a non-empty linked chunk");
1318
1319 assert_items_eq!(lc, ['a', 'b', 'c'] [-] ['d', 'e', 'f']);
1321 }
1322
1323 #[test]
1324 fn test_replace_item() {
1325 let room_id = room_id!("!r0:matrix.org");
1326 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1327
1328 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1329
1330 relational_linked_chunk.apply_updates(
1331 linked_chunk_id.as_ref(),
1332 vec![
1333 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1335 Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['a', 'b', 'c'] },
1337 Update::ReplaceItem { at: Position::new(CId::new(0), 1), item: 'B' },
1339 ],
1340 );
1341
1342 assert_eq!(
1344 relational_linked_chunk.chunks,
1345 &[ChunkRow {
1346 linked_chunk_id: linked_chunk_id.clone(),
1347 previous_chunk: None,
1348 chunk: CId::new(0),
1349 next_chunk: None,
1350 },],
1351 );
1352
1353 assert_eq!(
1355 relational_linked_chunk.items_chunks,
1356 &[
1357 ItemRow {
1358 linked_chunk_id: linked_chunk_id.clone(),
1359 position: Position::new(CId::new(0), 0),
1360 item: Either::Item('a')
1361 },
1362 ItemRow {
1363 linked_chunk_id: linked_chunk_id.clone(),
1364 position: Position::new(CId::new(0), 1),
1365 item: Either::Item('B')
1366 },
1367 ItemRow {
1368 linked_chunk_id,
1369 position: Position::new(CId::new(0), 2),
1370 item: Either::Item('c')
1371 },
1372 ],
1373 );
1374 }
1375
1376 #[test]
1377 fn test_unordered_events() {
1378 let room_id = room_id!("!r0:matrix.org");
1379 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1380
1381 let other_room_id = room_id!("!r1:matrix.org");
1382 let other_linked_chunk_id = OwnedLinkedChunkId::Room(other_room_id.to_owned());
1383
1384 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1385
1386 relational_linked_chunk.apply_updates(
1387 linked_chunk_id.as_ref(),
1388 vec![
1389 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1390 Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['a', 'b', 'c'] },
1391 Update::NewItemsChunk { previous: Some(CId::new(0)), new: CId::new(1), next: None },
1392 Update::PushItems { at: Position::new(CId::new(1), 0), items: vec!['d', 'e', 'f'] },
1393 ],
1394 );
1395
1396 relational_linked_chunk.apply_updates(
1397 other_linked_chunk_id.as_ref(),
1398 vec![
1399 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1400 Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['x', 'y', 'z'] },
1401 ],
1402 );
1403
1404 let events = BTreeMap::from_iter(
1405 relational_linked_chunk.unordered_linked_chunk_items(&linked_chunk_id),
1406 );
1407
1408 assert_eq!(events.len(), 6);
1409 assert_eq!(*events.get(&'a').unwrap(), Position::new(CId::new(0), 0));
1410 assert_eq!(*events.get(&'b').unwrap(), Position::new(CId::new(0), 1));
1411 assert_eq!(*events.get(&'c').unwrap(), Position::new(CId::new(0), 2));
1412 assert_eq!(*events.get(&'d').unwrap(), Position::new(CId::new(1), 0));
1413 assert_eq!(*events.get(&'e').unwrap(), Position::new(CId::new(1), 1));
1414 assert_eq!(*events.get(&'f').unwrap(), Position::new(CId::new(1), 2));
1415 }
1416
1417 #[test]
1418 fn test_load_last_chunk() {
1419 let room_id = room_id!("!r0:matrix.org");
1420 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1421
1422 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1423
1424 {
1426 let (last_chunk, chunk_identifier_generator) =
1427 relational_linked_chunk.load_last_chunk(linked_chunk_id.as_ref()).unwrap();
1428
1429 assert!(last_chunk.is_none());
1430 assert_eq!(chunk_identifier_generator.current(), 0);
1431 }
1432
1433 {
1435 relational_linked_chunk.apply_updates(
1436 linked_chunk_id.as_ref(),
1437 vec![
1438 Update::NewItemsChunk { previous: None, new: CId::new(42), next: None },
1439 Update::PushItems { at: Position::new(CId::new(42), 0), items: vec!['a', 'b'] },
1440 ],
1441 );
1442
1443 let (last_chunk, chunk_identifier_generator) =
1444 relational_linked_chunk.load_last_chunk(linked_chunk_id.as_ref()).unwrap();
1445
1446 assert_matches!(last_chunk, Some(last_chunk) => {
1447 assert_eq!(last_chunk.identifier, 42);
1448 assert!(last_chunk.previous.is_none());
1449 assert!(last_chunk.next.is_none());
1450 assert_matches!(last_chunk.content, ChunkContent::Items(items) => {
1451 assert_eq!(items.len(), 2);
1452 assert_eq!(items, &['a', 'b']);
1453 });
1454 });
1455 assert_eq!(chunk_identifier_generator.current(), 42);
1456 }
1457
1458 {
1460 relational_linked_chunk.apply_updates(
1461 linked_chunk_id.as_ref(),
1462 vec![
1463 Update::NewItemsChunk {
1464 previous: Some(CId::new(42)),
1465 new: CId::new(7),
1466 next: None,
1467 },
1468 Update::PushItems {
1469 at: Position::new(CId::new(7), 0),
1470 items: vec!['c', 'd', 'e'],
1471 },
1472 ],
1473 );
1474
1475 let (last_chunk, chunk_identifier_generator) =
1476 relational_linked_chunk.load_last_chunk(linked_chunk_id.as_ref()).unwrap();
1477
1478 assert_matches!(last_chunk, Some(last_chunk) => {
1479 assert_eq!(last_chunk.identifier, 7);
1480 assert_matches!(last_chunk.previous, Some(previous) => {
1481 assert_eq!(previous, 42);
1482 });
1483 assert!(last_chunk.next.is_none());
1484 assert_matches!(last_chunk.content, ChunkContent::Items(items) => {
1485 assert_eq!(items.len(), 3);
1486 assert_eq!(items, &['c', 'd', 'e']);
1487 });
1488 });
1489 assert_eq!(chunk_identifier_generator.current(), 42);
1490 }
1491 }
1492
1493 #[test]
1494 fn test_load_last_chunk_with_a_cycle() {
1495 let room_id = room_id!("!r0:matrix.org");
1496 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1497 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1498
1499 relational_linked_chunk.apply_updates(
1500 linked_chunk_id.as_ref(),
1501 vec![
1502 Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1503 Update::NewItemsChunk {
1504 previous: Some(CId::new(0)),
1508 new: CId::new(1),
1509 next: Some(CId::new(0)),
1510 },
1511 ],
1512 );
1513
1514 relational_linked_chunk.load_last_chunk(linked_chunk_id.as_ref()).unwrap_err();
1515 }
1516
1517 #[test]
1518 fn test_load_previous_chunk() {
1519 let room_id = room_id!("!r0:matrix.org");
1520 let linked_chunk_id = OwnedLinkedChunkId::Room(room_id.to_owned());
1521 let mut relational_linked_chunk = RelationalLinkedChunk::<_, char, ()>::new();
1522
1523 {
1526 let previous_chunk = relational_linked_chunk
1527 .load_previous_chunk(linked_chunk_id.as_ref(), CId::new(153))
1528 .unwrap();
1529
1530 assert!(previous_chunk.is_none());
1531 }
1532
1533 {
1536 relational_linked_chunk.apply_updates(
1537 linked_chunk_id.as_ref(),
1538 vec![Update::NewItemsChunk { previous: None, new: CId::new(42), next: None }],
1539 );
1540
1541 let previous_chunk = relational_linked_chunk
1542 .load_previous_chunk(linked_chunk_id.as_ref(), CId::new(42))
1543 .unwrap();
1544
1545 assert!(previous_chunk.is_none());
1546 }
1547
1548 {
1550 relational_linked_chunk.apply_updates(
1551 linked_chunk_id.as_ref(),
1552 vec![
1553 Update::NewItemsChunk {
1555 previous: None,
1556 new: CId::new(7),
1557 next: Some(CId::new(42)),
1558 },
1559 Update::PushItems {
1560 at: Position::new(CId::new(7), 0),
1561 items: vec!['a', 'b', 'c'],
1562 },
1563 ],
1564 );
1565
1566 let previous_chunk = relational_linked_chunk
1567 .load_previous_chunk(linked_chunk_id.as_ref(), CId::new(42))
1568 .unwrap();
1569
1570 assert_matches!(previous_chunk, Some(previous_chunk) => {
1571 assert_eq!(previous_chunk.identifier, 7);
1572 assert!(previous_chunk.previous.is_none());
1573 assert_matches!(previous_chunk.next, Some(next) => {
1574 assert_eq!(next, 42);
1575 });
1576 assert_matches!(previous_chunk.content, ChunkContent::Items(items) => {
1577 assert_eq!(items.len(), 3);
1578 assert_eq!(items, &['a', 'b', 'c']);
1579 });
1580 });
1581 }
1582 }
1583}