matrix_sdk_common/linked_chunk/
relational.rs

1// Copyright 2024 The Matrix.org Foundation C.I.C.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Implementation for a _relational linked chunk_, see
16//! [`RelationalLinkedChunk`].
17
18use 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/// A row of the [`RelationalLinkedChunk::chunks`].
34#[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/// A row of the [`RelationalLinkedChunk::items`].
43#[derive(Debug, PartialEq)]
44struct ItemRow<ItemId, Gap> {
45    linked_chunk_id: OwnedLinkedChunkId,
46    position: Position,
47    item: Either<ItemId, Gap>,
48}
49
50/// Kind of item.
51#[derive(Debug, PartialEq)]
52enum Either<Item, Gap> {
53    /// The content is an item.
54    Item(Item),
55
56    /// The content is a gap.
57    Gap(Gap),
58}
59
60/// A [`LinkedChunk`] but with a relational layout, similar to what we
61/// would have in a database.
62///
63/// This is used by memory stores. The idea is to have a data layout that is
64/// similar for memory stores and for relational database stores, to represent a
65/// [`LinkedChunk`].
66///
67/// This type is also designed to receive [`Update`]. Applying `Update`s
68/// directly on a [`LinkedChunk`] is not ideal and particularly not trivial as
69/// the `Update`s do _not_ match the internal data layout of the `LinkedChunk`,
70/// they have been designed for storages, like a relational database for
71/// example.
72///
73/// This type is not as performant as [`LinkedChunk`] (in terms of memory
74/// layout, CPU caches etc.). It is only designed to be used in memory stores,
75/// which are mostly used for test purposes or light usage of the SDK.
76///
77/// [`LinkedChunk`]: super::LinkedChunk
78#[derive(Debug)]
79pub struct RelationalLinkedChunk<ItemId, Item, Gap> {
80    /// Chunks.
81    chunks: Vec<ChunkRow>,
82
83    /// Items chunks.
84    items_chunks: Vec<ItemRow<ItemId, Gap>>,
85
86    /// The items' content themselves.
87    items: HashMap<OwnedLinkedChunkId, BTreeMap<ItemId, (Item, Option<Position>)>>,
88}
89
90/// The [`IndexableItem`] trait is used to mark items that can be indexed into a
91/// [`RelationalLinkedChunk`].
92pub trait IndexableItem {
93    type ItemId: Hash + PartialEq + Eq + Clone;
94
95    /// Return the identifier of the item.
96    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    /// Create a new relational linked chunk.
114    pub fn new() -> Self {
115        Self { chunks: Vec::new(), items_chunks: Vec::new(), items: HashMap::new() }
116    }
117
118    /// Removes all the chunks and items from this relational linked chunk.
119    pub fn clear(&mut self) {
120        self.chunks.clear();
121        self.items_chunks.clear();
122        self.items.clear();
123    }
124
125    /// Apply [`Update`]s. That's the only way to write data inside this
126    /// relational linked chunk.
127    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                        // Filter by linked chunk id.
218                        if linked_chunk_id != &*linked_chunk_id_candidate {
219                            continue;
220                        }
221
222                        // Find the item to remove.
223                        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                        // Update all items that come _after_ `at` to shift their index.
230                        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                    // We deliberately keep the item in the items collection.
239                }
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 => { /* nothing */ }
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                    // We deliberately leave the items intact.
274                }
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        // Find the previous chunk, and update its next chunk.
287        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            // Link the chunk.
296            entry_for_previous_chunk.next_chunk = Some(new);
297        }
298
299        // Find the next chunk, and update its previous chunk.
300        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            // Link the chunk.
309            entry_for_next_chunk.previous_chunk = Some(new);
310        }
311
312        // Insert the chunk.
313        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        // Find the previous chunk, and update its next chunk.
341        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            // Insert the chunk.
350            entry_for_previous_chunk.next_chunk = next;
351        }
352
353        // Find the next chunk, and update its previous chunk.
354        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            // Insert the chunk.
363            entry_for_next_chunk.previous_chunk = previous;
364        }
365    }
366
367    /// Return an iterator that yields items of a particular linked chunk, in no
368    /// particular order.
369    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            // Only keep items which have a position.
375            items.values().filter_map(|(item, pos)| pos.map(|pos| (item, pos)))
376        })
377    }
378
379    /// Return an iterator over all items of all linked chunks of a room, along
380    /// with their positions, if available.
381    ///
382    /// The only items which will NOT have a position are those saved with
383    /// [`Self::save_item`].
384    ///
385    /// This will include out-of-band items.
386    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    /// Save a single item "out-of-band" in the relational linked chunk.
399    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            // If the item already exists, we keep the position.
406            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    /// Loads all the chunks.
420    ///
421    /// Return an error result if the data was malformed in the struct, with a
422    /// string message explaining details about the error.
423    #[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    /// Loads all the chunks' metadata.
436    ///
437    /// Return an error result if the data was malformed in the struct, with a
438    /// string message explaining details about the error.
439    #[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        // Find the latest chunk identifier to generate a `ChunkIdentifierGenerator`.
456        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        // Find the last chunk.
471        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            // Chunk has been found, all good.
488            Some(chunk_row) => chunk_row,
489
490            // Chunk is not found and there is zero chunk for this room, this is consistent, all
491            // good.
492            None if number_of_chunks == 0 => {
493                return Ok((None, chunk_identifier_generator));
494            }
495
496            // Chunk is not found **but** there are chunks for this room, this is inconsistent. The
497            // linked chunk is malformed.
498            //
499            // Returning `Ok(None)` would be invalid here: we must return an error.
500            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        // Build the chunk.
509        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        // Find the chunk before the chunk identified by `before_chunk_identifier`.
519        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            // Chunk is not found.
524            return Ok(None);
525        };
526
527        // Build the chunk.
528        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
542/// Loads a single chunk along all its items.
543///
544/// The code of this method must be kept in sync with that of
545/// [`load_raw_chunk_metadata`] below.
546fn 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    // Find all items that correspond to the chunk.
557    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        // No item. It means it is a chunk of kind `Items` and that it is empty!
568        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        // This is a chunk of kind `Items`.
578        Either::Item(_) => {
579            // Collect all the items.
580            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            // Sort them by their position.
598            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            // We shouldn't have more than one item row for this chunk.
626            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
643/// Loads the metadata for a single chunk.
644///
645/// The code of this method must be kept in sync with that of [`load_raw_chunk`]
646/// above.
647fn 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    // Find all items that correspond to the chunk.
658    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        // No item. It means it is a chunk of kind `Items` and that it is empty!
669        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        // This is a chunk of kind `Items`.
679        Either::Item(_) => {
680            // Count all the items. We add an additional filter that will exclude gaps, in
681            // case the chunk is malformed, but we should not have to, in theory.
682
683            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            // We shouldn't have more than one item row for this chunk.
708            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                // By convention, a gap has 0 items.
717                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                // 0
754                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
755                // 1 after 0
756                Update::NewItemsChunk { previous: Some(CId::new(0)), new: CId::new(1), next: None },
757                // 2 before 0
758                Update::NewItemsChunk { previous: None, new: CId::new(2), next: Some(CId::new(0)) },
759                // 3 between 2 and 0
760                Update::NewItemsChunk {
761                    previous: Some(CId::new(2)),
762                    new: CId::new(3),
763                    next: Some(CId::new(0)),
764                },
765            ],
766        );
767
768        // Chunks are correctly linked.
769        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        // Items have not been modified.
800        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                // 0
814                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
815                // 1 after 0
816                Update::NewGapChunk {
817                    previous: Some(CId::new(0)),
818                    new: CId::new(1),
819                    next: None,
820                    gap: (),
821                },
822                // 2 after 1
823                Update::NewItemsChunk { previous: Some(CId::new(1)), new: CId::new(2), next: None },
824            ],
825        );
826
827        // Chunks are correctly linked.
828        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        // Items contains the gap.
852        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                // 0
873                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
874                // 1 after 0
875                Update::NewGapChunk {
876                    previous: Some(CId::new(0)),
877                    new: CId::new(1),
878                    next: None,
879                    gap: (),
880                },
881                // 2 after 1
882                Update::NewItemsChunk { previous: Some(CId::new(1)), new: CId::new(2), next: None },
883                // remove 1
884                Update::RemoveChunk(CId::new(1)),
885            ],
886        );
887
888        // Chunks are correctly linked.
889        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        // Items no longer contains the gap.
908        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                // new chunk (this is not mandatory for this test, but let's try to be realistic)
922                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
923                // new items on 0
924                Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['a', 'b', 'c'] },
925                // new chunk (to test new items are pushed in the correct chunk)
926                Update::NewItemsChunk { previous: Some(CId::new(0)), new: CId::new(1), next: None },
927                // new items on 1
928                Update::PushItems { at: Position::new(CId::new(1), 0), items: vec!['x', 'y', 'z'] },
929                // new items on 0 again
930                Update::PushItems { at: Position::new(CId::new(0), 3), items: vec!['d', 'e'] },
931            ],
932        );
933
934        // Chunks are correctly linked.
935        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        // Items contains the pushed items.
953        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                // new chunk (this is not mandatory for this test, but let's try to be realistic)
1011                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1012                // new items on 0
1013                Update::PushItems {
1014                    at: Position::new(CId::new(0), 0),
1015                    items: vec!['a', 'b', 'c', 'd', 'e'],
1016                },
1017                // remove an item: 'a'
1018                Update::RemoveItem { at: Position::new(CId::new(0), 0) },
1019                // remove an item: 'd'
1020                Update::RemoveItem { at: Position::new(CId::new(0), 2) },
1021            ],
1022        );
1023
1024        // Chunks are correctly linked.
1025        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        // Items contains the pushed items.
1035        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                // new chunk
1068                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1069                // new chunk
1070                Update::NewItemsChunk { previous: Some(CId::new(0)), new: CId::new(1), next: None },
1071                // new items on 0
1072                Update::PushItems {
1073                    at: Position::new(CId::new(0), 0),
1074                    items: vec!['a', 'b', 'c', 'd', 'e'],
1075                },
1076                // new items on 1
1077                Update::PushItems { at: Position::new(CId::new(1), 0), items: vec!['x', 'y', 'z'] },
1078                // detach last items on 0
1079                Update::DetachLastItems { at: Position::new(CId::new(0), 2) },
1080            ],
1081        );
1082
1083        // Chunks are correctly linked.
1084        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        // Items contains the pushed items.
1102        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        // Nothing happened.
1147        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                // new chunk (this is not mandatory for this test, but let's try to be realistic)
1165                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1166                // new items on 0
1167                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                // new chunk (this is not mandatory for this test, but let's try to be realistic)
1175                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1176                // new items on 0
1177                Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['x'] },
1178            ],
1179        );
1180
1181        // Chunks are correctly linked.
1182        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        // Items contains the pushed items.
1201        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        // Now, time for a clean up.
1228        relational_linked_chunk.apply_updates(linked_chunk_id0.as_ref(), vec![Update::Clear]);
1229
1230        // Only items from r1 remain.
1231        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        // When I reload the linked chunk components from an empty store,
1257        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        // When I store an empty items chunks,
1270        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        // It correctly gets reloaded as such.
1276        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                // new chunk
1296                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1297                // new items on 0
1298                Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['a', 'b', 'c'] },
1299                // a gap chunk
1300                Update::NewGapChunk {
1301                    previous: Some(CId::new(0)),
1302                    new: CId::new(1),
1303                    next: None,
1304                    gap: 'g',
1305                },
1306                // another items chunk
1307                Update::NewItemsChunk { previous: Some(CId::new(1)), new: CId::new(2), next: None },
1308                // new items on 0
1309                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        // The linked chunk is correctly reloaded.
1320        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                // new chunk (this is not mandatory for this test, but let's try to be realistic)
1334                Update::NewItemsChunk { previous: None, new: CId::new(0), next: None },
1335                // new items on 0
1336                Update::PushItems { at: Position::new(CId::new(0), 0), items: vec!['a', 'b', 'c'] },
1337                // update item at (0; 1).
1338                Update::ReplaceItem { at: Position::new(CId::new(0), 1), item: 'B' },
1339            ],
1340        );
1341
1342        // Chunks are correctly linked.
1343        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        // Items contains the pushed *and* replaced items.
1354        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        // Case #1: no last chunk.
1425        {
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        // Case #2: only one chunk is present.
1434        {
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        // Case #3: more chunks are present.
1459        {
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                    // Because `previous` connects to chunk #0, it will create a cycle.
1505                    // Chunk #0 will have a `next` set to chunk #1! Consequently, the last chunk
1506                    // **does not exist**. We have to detect this cycle.
1507                    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        // Case #1: no chunk at all, equivalent to having an inexistent
1524        // `before_chunk_identifier`.
1525        {
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        // Case #2: there is one chunk only: we request the previous on this
1534        // one, it doesn't exist.
1535        {
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        // Case #3: there is two chunks.
1549        {
1550            relational_linked_chunk.apply_updates(
1551                linked_chunk_id.as_ref(),
1552                vec![
1553                    // new chunk before the one that exists.
1554                    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}