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

matrix_sdk_common/linked_chunk/
order_tracker.rs
