matrix_sdk_common/linked_chunk/
order_tracker.rs

1// Copyright 2025 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
15use std::sync::{Arc, RwLock};
16
17use eyeball_im::VectorDiff;
18
19use super::{
20    updates::{ReaderToken, Update, UpdatesInner},
21    Position,
22};
23use crate::linked_chunk::{ChunkMetadata, UpdateToVectorDiff};
24
25/// A tracker for the order of items in a linked chunk.
26///
27/// This can be used to determine the absolute ordering of an item, and thus the
28/// relative ordering of two items in a linked chunk, in an
29/// efficient manner, thanks to [`OrderTracker::ordering`]. Internally, it
30/// keeps track of the relative ordering of the chunks themselves; given a
31/// [`Position`] in a linked chunk, the item ordering is the lexicographic
32/// ordering of the chunk in the linked chunk, and the internal position within
33/// the chunk. For the sake of ease, we return the absolute vector index of the
34/// item in the linked chunk.
35///
36/// It requires the full links' metadata to be provided at creation time, so
37/// that it can also give an order for an item that's not loaded yet, in the
38/// context of lazy-loading.
39#[derive(Debug)]
40pub struct OrderTracker<Item, Gap> {
41    /// Strong reference to [`UpdatesInner`].
42    updates: Arc<RwLock<UpdatesInner<Item, Gap>>>,
43
44    /// The token to read the updates.
45    token: ReaderToken,
46
47    /// Mapper from `Update` to `VectorDiff`.
48    mapper: UpdateToVectorDiff<Item, NullAccumulator<Item>>,
49}
50
51struct NullAccumulator<Item> {
52    _phantom: std::marker::PhantomData<Item>,
53}
54
55#[cfg(not(tarpaulin_include))]
56impl<Item> std::fmt::Debug for NullAccumulator<Item> {
57    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
58        f.write_str("NullAccumulator")
59    }
60}
61
62impl<Item> super::UpdatesAccumulator<Item> for NullAccumulator<Item> {
63    fn new(_num_updates_hint: usize) -> Self {
64        Self { _phantom: std::marker::PhantomData }
65    }
66}
67
68impl<Item> Extend<VectorDiff<Item>> for NullAccumulator<Item> {
69    fn extend<T: IntoIterator<Item = VectorDiff<Item>>>(&mut self, _iter: T) {
70        // This is a no-op, as we don't want to accumulate anything.
71    }
72}
73
74impl<Item, Gap> OrderTracker<Item, Gap>
75where
76    Item: Clone,
77{
78    /// Create a new [`OrderTracker`].
79    ///
80    /// The `all_chunks_metadata` parameter must include the metadata for *all*
81    /// chunks (the full collection, even if the linked chunk is
82    /// lazy-loaded).
83    ///
84    /// They must be ordered by their links in the linked chunk, i.e. the first
85    /// chunk in the vector is the first chunk in the linked chunk, the
86    /// second in the vector is the first's next chunk, and so on. If that
87    /// precondition doesn't hold, then the ordering of items will be undefined.
88    pub(super) fn new(
89        updates: Arc<RwLock<UpdatesInner<Item, Gap>>>,
90        token: ReaderToken,
91        all_chunks_metadata: Vec<ChunkMetadata>,
92    ) -> Self {
93        // Drain previous updates so that this type is synced with `Updates`.
94        {
95            let mut updates = updates.write().unwrap();
96            let _ = updates.take_with_token(token);
97        }
98
99        Self { updates, token, mapper: UpdateToVectorDiff::from_metadata(all_chunks_metadata) }
100    }
101
102    /// Force flushing of the updates manually.
103    ///
104    /// If `inhibit` is `true` (which is useful in the case of lazy-loading
105    /// related updates, which shouldn't affect the canonical, persisted
106    /// linked chunk), the updates are ignored; otherwise, they are consumed
107    /// normally.
108    pub fn flush_updates(&mut self, inhibit: bool) {
109        if inhibit {
110            // Ignore the updates.
111            let _ = self.updates.write().unwrap().take_with_token(self.token);
112        } else {
113            // Consume the updates.
114            let mut updater = self.updates.write().unwrap();
115            let updates = updater.take_with_token(self.token);
116            let _ = self.mapper.map(updates);
117        }
118    }
119
120    /// Apply some out-of-band updates to the ordering tracker.
121    ///
122    /// This must only be used when the updates do not affect the observed
123    /// linked chunk, but would affect the fully-loaded collection.
124    pub fn map_updates(&mut self, updates: &[Update<Item, Gap>]) {
125        let _ = self.mapper.map(updates);
126    }
127
128    /// Given an event's position, returns its final ordering in the current
129    /// state of the linked chunk as a vector.
130    ///
131    /// Useful to compare the ordering of multiple events.
132    ///
133    /// Precondition: the reader must be up to date, i.e.
134    /// [`Self::flush_updates`] must have been called before this method.
135    ///
136    /// Will return `None` if the position doesn't match a known chunk in the
137    /// linked chunk, or if the chunk is a gap.
138    pub fn ordering(&self, event_pos: Position) -> Option<usize> {
139        // Check the precondition: there must not be any pending updates for this
140        // reader.
141        debug_assert!(self.updates.read().unwrap().is_reader_up_to_date(self.token));
142
143        // Find the chunk that contained the event.
144        let mut ordering = 0;
145        for (chunk_id, chunk_length) in &self.mapper.chunks {
146            if *chunk_id == event_pos.chunk_identifier() {
147                let offset_within_chunk = event_pos.index();
148                if offset_within_chunk >= *chunk_length {
149                    // The event is out of bounds for this chunk, return None.
150                    return None;
151                }
152                // The final ordering is the number of items before the event, plus its own
153                // index within the chunk.
154                return Some(ordering + offset_within_chunk);
155            }
156            // This is not the target chunk yet, so add the size of the current chunk to the
157            // number of seen items, and continue.
158            ordering += *chunk_length;
159        }
160
161        None
162    }
163}
164
165#[cfg(test)]
166mod tests {
167    use assert_matches::assert_matches;
168    use matrix_sdk_test_macros::async_test;
169
170    use crate::linked_chunk::{
171        lazy_loader::from_last_chunk, ChunkContent, ChunkIdentifier, ChunkIdentifierGenerator,
172        ChunkMetadata, LinkedChunk, OrderTracker, Position, RawChunk, Update,
173    };
174
175    #[async_test]
176    async fn test_linked_chunk_without_update_history_no_tracking() {
177        let mut linked_chunk = LinkedChunk::<10, char, ()>::new();
178        assert_matches!(linked_chunk.order_tracker(None), None);
179    }
180
181    /// Given a fully-loaded linked chunk, checks that the ordering of an item
182    /// is effectively the same as its index in an iteration of items.
183    fn assert_order_fully_loaded(
184        linked_chunk: &LinkedChunk<3, char, ()>,
185        tracker: &OrderTracker<char, ()>,
186    ) {
187        assert_order(linked_chunk, tracker, 0);
188    }
189
190    /// Given a linked chunk with an offset representing the number of items not
191    /// loaded yet, checks that the ordering of an item is effectively the
192    /// same as its index+offset in an iteration of items.
193    fn assert_order(
194        linked_chunk: &LinkedChunk<3, char, ()>,
195        tracker: &OrderTracker<char, ()>,
196        offset: usize,
197    ) {
198        for (i, (item_pos, _value)) in linked_chunk.items().enumerate() {
199            assert_eq!(tracker.ordering(item_pos), Some(i + offset));
200        }
201    }
202
203    #[async_test]
204    async fn test_non_lazy_updates() {
205        // Assume the linked chunk is fully loaded, so we have all the chunks at
206        // our disposal.
207        let mut linked_chunk = LinkedChunk::<3, _, _>::new_with_update_history();
208
209        let mut tracker = linked_chunk.order_tracker(None).unwrap();
210
211        // Let's apply some updates to the live linked chunk.
212
213        // Pushing new items.
214        {
215            linked_chunk.push_items_back(['a', 'b', 'c']);
216            tracker.flush_updates(false);
217            assert_order_fully_loaded(&linked_chunk, &tracker);
218        }
219
220        // Pushing a gap.
221        {
222            linked_chunk.push_gap_back(());
223            tracker.flush_updates(false);
224            assert_order_fully_loaded(&linked_chunk, &tracker);
225        }
226
227        // Inserting items in the middle.
228        {
229            let pos_b = linked_chunk.item_position(|c| *c == 'b').unwrap();
230            linked_chunk.insert_items_at(pos_b, ['d', 'e']).unwrap();
231            tracker.flush_updates(false);
232            assert_order_fully_loaded(&linked_chunk, &tracker);
233        }
234
235        // Inserting a gap in the middle.
236        {
237            let c_pos = linked_chunk.item_position(|c| *c == 'c').unwrap();
238            linked_chunk.insert_gap_at((), c_pos).unwrap();
239            tracker.flush_updates(false);
240            assert_order_fully_loaded(&linked_chunk, &tracker);
241        }
242
243        // Replacing a gap with items.
244        {
245            let last_gap =
246                linked_chunk.rchunks().filter(|c| c.is_gap()).last().unwrap().identifier();
247            linked_chunk.replace_gap_at(['f', 'g'], last_gap).unwrap();
248            tracker.flush_updates(false);
249            assert_order_fully_loaded(&linked_chunk, &tracker);
250        }
251
252        // Removing an item.
253        {
254            let a_pos = linked_chunk.item_position(|c| *c == 'd').unwrap();
255            linked_chunk.remove_item_at(a_pos).unwrap();
256            tracker.flush_updates(false);
257            assert_order_fully_loaded(&linked_chunk, &tracker);
258        }
259
260        // Replacing an item.
261        {
262            let b_pos = linked_chunk.item_position(|c| *c == 'e').unwrap();
263            linked_chunk.replace_item_at(b_pos, 'E').unwrap();
264            tracker.flush_updates(false);
265            assert_order_fully_loaded(&linked_chunk, &tracker);
266        }
267
268        // Clearing all items.
269        {
270            linked_chunk.clear();
271            tracker.flush_updates(false);
272            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 0)), None);
273            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), None);
274        }
275    }
276
277    #[async_test]
278    async fn test_lazy_loading() {
279        // Assume that all the chunks haven't been loaded yet, so we have a few of them
280        // in some memory, and some of them are still in an hypothetical
281        // database.
282        let db_metadata = vec![
283            // Hypothetical non-empty items chunk with items 'a', 'b', 'c'.
284            ChunkMetadata {
285                previous: None,
286                identifier: ChunkIdentifier(0),
287                next: Some(ChunkIdentifier(1)),
288                num_items: 3,
289            },
290            // Hypothetical gap chunk.
291            ChunkMetadata {
292                previous: Some(ChunkIdentifier(0)),
293                identifier: ChunkIdentifier(1),
294                next: Some(ChunkIdentifier(2)),
295                num_items: 0,
296            },
297            // Hypothetical non-empty items chunk with items 'd', 'e', 'f'.
298            ChunkMetadata {
299                previous: Some(ChunkIdentifier(1)),
300                identifier: ChunkIdentifier(2),
301                next: Some(ChunkIdentifier(3)),
302                num_items: 3,
303            },
304            // Hypothetical non-empty items chunk with items 'g'.
305            ChunkMetadata {
306                previous: Some(ChunkIdentifier(2)),
307                identifier: ChunkIdentifier(3),
308                next: None,
309                num_items: 1,
310            },
311        ];
312
313        // The in-memory linked chunk contains the latest chunk only.
314        let mut linked_chunk = from_last_chunk::<3, _, ()>(
315            Some(RawChunk {
316                content: ChunkContent::Items(vec!['g']),
317                previous: Some(ChunkIdentifier(2)),
318                identifier: ChunkIdentifier(3),
319                next: None,
320            }),
321            ChunkIdentifierGenerator::new_from_previous_chunk_identifier(ChunkIdentifier(3)),
322        )
323        .expect("could recreate the linked chunk")
324        .expect("the linked chunk isn't empty");
325
326        let tracker = linked_chunk.order_tracker(Some(db_metadata)).unwrap();
327
328        // At first, even if the main linked chunk is empty, the order tracker can
329        // compute the position for unloaded items.
330
331        // Order of 'a':
332        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 0)), Some(0));
333        // Order of 'b':
334        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
335        // Order of 'c':
336        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 2)), Some(2));
337        // An invalid position in a known chunk returns no ordering.
338        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 42)), None);
339
340        // A gap chunk doesn't have an ordering.
341        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(1), 0)), None);
342        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(1), 42)), None);
343
344        // Order of 'd':
345        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(2), 0)), Some(3));
346        // Order of 'e':
347        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(2), 1)), Some(4));
348        // Order of 'f':
349        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(2), 2)), Some(5));
350        // No subsequent entry in the same chunk, it's been split when inserting g.
351        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(2), 3)), None);
352
353        // Order of 'g':
354        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), Some(6));
355        // This was the final entry so far.
356        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 1)), None);
357    }
358
359    #[async_test]
360    async fn test_lazy_updates() {
361        // Assume that all the chunks haven't been loaded yet, so we have a few of them
362        // in some memory, and some of them are still in an hypothetical
363        // database.
364        let db_metadata = vec![
365            // Hypothetical non-empty items chunk with items 'a', 'b'.
366            ChunkMetadata {
367                previous: None,
368                identifier: ChunkIdentifier(0),
369                next: Some(ChunkIdentifier(1)),
370                num_items: 2,
371            },
372            // Hypothetical gap chunk.
373            ChunkMetadata {
374                previous: Some(ChunkIdentifier(0)),
375                identifier: ChunkIdentifier(1),
376                next: Some(ChunkIdentifier(2)),
377                num_items: 0,
378            },
379            // Hypothetical non-empty items chunk with items 'd', 'e', 'f'.
380            ChunkMetadata {
381                previous: Some(ChunkIdentifier(1)),
382                identifier: ChunkIdentifier(2),
383                next: Some(ChunkIdentifier(3)),
384                num_items: 3,
385            },
386            // Hypothetical non-empty items chunk with items 'g'.
387            ChunkMetadata {
388                previous: Some(ChunkIdentifier(2)),
389                identifier: ChunkIdentifier(3),
390                next: None,
391                num_items: 1,
392            },
393        ];
394
395        // The in-memory linked chunk contains the latest chunk only.
396        let mut linked_chunk = from_last_chunk(
397            Some(RawChunk {
398                content: ChunkContent::Items(vec!['g']),
399                previous: Some(ChunkIdentifier(2)),
400                identifier: ChunkIdentifier(3),
401                next: None,
402            }),
403            ChunkIdentifierGenerator::new_from_previous_chunk_identifier(ChunkIdentifier(3)),
404        )
405        .expect("could recreate the linked chunk")
406        .expect("the linked chunk isn't empty");
407
408        let mut tracker = linked_chunk.order_tracker(Some(db_metadata)).unwrap();
409
410        // Sanity checks on the initial state.
411        {
412            // Order of 'b':
413            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
414            // Order of 'g':
415            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), Some(5));
416        }
417
418        // Let's apply some updates to the live linked chunk.
419
420        // Pushing new items.
421        {
422            linked_chunk.push_items_back(['h', 'i']);
423            tracker.flush_updates(false);
424
425            // Order of items not loaded:
426            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
427            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), Some(5));
428            // The loaded items are off by 5 (the absolute order of g).
429            assert_order(&linked_chunk, &tracker, 5);
430        }
431
432        // Pushing a gap.
433        let gap_id = {
434            linked_chunk.push_gap_back(());
435            tracker.flush_updates(false);
436
437            // The gap doesn't have an ordering.
438            let last_chunk = linked_chunk.rchunks().next().unwrap();
439            assert!(last_chunk.is_gap());
440            assert_eq!(tracker.ordering(Position::new(last_chunk.identifier(), 0)), None);
441            assert_eq!(tracker.ordering(Position::new(last_chunk.identifier(), 42)), None);
442
443            // The previous items are still ordered.
444            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
445            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), Some(5));
446            // The loaded items are off by 5 (the absolute order of g).
447            assert_order(&linked_chunk, &tracker, 5);
448
449            last_chunk.identifier()
450        };
451
452        // Inserting items in the middle.
453        {
454            let pos_h = linked_chunk.item_position(|c| *c == 'h').unwrap();
455            linked_chunk.insert_items_at(pos_h, ['j', 'k']).unwrap();
456            tracker.flush_updates(false);
457
458            // The previous items are still ordered.
459            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
460            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), Some(5));
461            // The loaded items are off by 5 (the absolute order of g).
462            assert_order(&linked_chunk, &tracker, 5);
463        }
464
465        // Replacing a gap with items.
466        {
467            linked_chunk.replace_gap_at(['l', 'm'], gap_id).unwrap();
468            tracker.flush_updates(false);
469
470            // The previous items are still ordered.
471            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
472            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), Some(5));
473            // The loaded items are off by 5 (the absolute order of g).
474            assert_order(&linked_chunk, &tracker, 5);
475        }
476
477        // Removing an item.
478        {
479            let j_pos = linked_chunk.item_position(|c| *c == 'j').unwrap();
480            linked_chunk.remove_item_at(j_pos).unwrap();
481            tracker.flush_updates(false);
482
483            // The previous items are still ordered.
484            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
485            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), Some(5));
486            // The loaded items are off by 5 (the absolute order of g).
487            assert_order(&linked_chunk, &tracker, 5);
488        }
489
490        // Replacing an item.
491        {
492            let k_pos = linked_chunk.item_position(|c| *c == 'k').unwrap();
493            linked_chunk.replace_item_at(k_pos, 'K').unwrap();
494            tracker.flush_updates(false);
495
496            // The previous items are still ordered.
497            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
498            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), Some(5));
499            // The loaded items are off by 5 (the absolute order of g).
500            assert_order(&linked_chunk, &tracker, 5);
501        }
502
503        // Clearing all items.
504        {
505            linked_chunk.clear();
506            tracker.flush_updates(false);
507            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 0)), None);
508            assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(3), 0)), None);
509        }
510    }
511
512    #[async_test]
513    async fn test_out_of_band_updates() {
514        // Assume that all the chunks haven't been loaded yet, so we have a few of them
515        // in some memory, and some of them are still in an hypothetical
516        // database.
517        let db_metadata = vec![
518            // Hypothetical non-empty items chunk with items 'a', 'b'.
519            ChunkMetadata {
520                previous: None,
521                identifier: ChunkIdentifier(0),
522                next: Some(ChunkIdentifier(1)),
523                num_items: 2,
524            },
525            // Hypothetical gap chunk.
526            ChunkMetadata {
527                previous: Some(ChunkIdentifier(0)),
528                identifier: ChunkIdentifier(1),
529                next: Some(ChunkIdentifier(2)),
530                num_items: 0,
531            },
532            // Hypothetical non-empty items chunk with items 'd', 'e', 'f'.
533            ChunkMetadata {
534                previous: Some(ChunkIdentifier(1)),
535                identifier: ChunkIdentifier(2),
536                next: Some(ChunkIdentifier(3)),
537                num_items: 3,
538            },
539            // Hypothetical non-empty items chunk with items 'g'.
540            ChunkMetadata {
541                previous: Some(ChunkIdentifier(2)),
542                identifier: ChunkIdentifier(3),
543                next: None,
544                num_items: 1,
545            },
546        ];
547
548        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
549
550        let mut tracker = linked_chunk.order_tracker(Some(db_metadata)).unwrap();
551
552        // Sanity checks.
553        // Order of 'b':
554        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), Some(1));
555        // Order of 'e':
556        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(2), 1)), Some(3));
557
558        // It's possible to apply updates out of band, i.e. without affecting the
559        // observed linked chunk. This can be useful when an update only applies
560        // to a database, but not to the in-memory linked chunk.
561        tracker.map_updates(&[Update::RemoveChunk(ChunkIdentifier::new(0))]);
562
563        // 'b' doesn't exist anymore, so its ordering is now undefined.
564        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(0), 1)), None);
565        // 'e' has been shifted back by 2 places, aka the number of items in the first
566        // chunk.
567        assert_eq!(tracker.ordering(Position::new(ChunkIdentifier::new(2), 1)), Some(1));
568    }
569}
matrix_sdk_common/linked_chunk/order_tracker.rs

matrix_sdk_common/linked_chunk/
order_tracker.rs
