matrix_sdk_common/linked_chunk/
as_vector.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
15use std::{
16    collections::VecDeque,
17    iter::repeat_n,
18    ops::ControlFlow,
19    sync::{Arc, RwLock},
20};
21
22use eyeball_im::VectorDiff;
23
24use super::{
25    updates::{ReaderToken, Update, UpdatesInner},
26    ChunkContent, ChunkIdentifier, Iter, Position,
27};
28use crate::linked_chunk::ChunkMetadata;
29
30/// A type alias to represent a chunk's length. This is purely for commodity.
31type ChunkLength = usize;
32
33/// A type that transforms a `Vec<Update<Item, Gap>>` (given by
34/// [`ObservableUpdates::take`](super::ObservableUpdates::take)) into a
35/// `Vec<VectorDiff<Item>>` (this type). Basically, it helps to consume a
36/// [`LinkedChunk<CAP, Item, Gap>`](super::LinkedChunk) as if it was an
37/// [`eyeball_im::ObservableVector<Item>`].
38#[derive(Debug)]
39pub struct AsVector<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, Vec<VectorDiff<Item>>>,
48}
49
50impl<Item, Gap> AsVector<Item, Gap> {
51    /// Create a new [`AsVector`].
52    ///
53    /// `updates` is the inner value of
54    /// [`ObservableUpdates`][super::updates::ObservableUpdates].
55    /// It's required to read the new [`Update`]s. `token` is the
56    /// [`ReaderToken`] necessary for this type to read the [`Update`]s.
57    /// `chunk_iterator` is the iterator of all [`Chunk`](super::Chunk)s, used
58    /// to set up its internal state.
59    pub(super) fn new<const CAP: usize>(
60        updates: Arc<RwLock<UpdatesInner<Item, Gap>>>,
61        token: ReaderToken,
62        chunk_iterator: Iter<'_, CAP, Item, Gap>,
63    ) -> Self {
64        // Drain previous updates so that this type is synced with `Updates`.
65        {
66            let mut updates = updates.write().unwrap();
67            let _ = updates.take_with_token(token);
68        }
69
70        Self { updates, token, mapper: UpdateToVectorDiff::new(chunk_iterator) }
71    }
72
73    /// Take the new updates as [`VectorDiff`].
74    ///
75    /// It returns an empty `Vec` if there is no new `VectorDiff` for the
76    /// moment.
77    pub fn take(&mut self) -> Vec<VectorDiff<Item>>
78    where
79        Item: Clone,
80    {
81        let mut updates = self.updates.write().unwrap();
82
83        self.mapper.map(updates.take_with_token(self.token))
84    }
85}
86
87/// Interface for a type accumulating updates from [`UpdateToVectorDiff::map`],
88/// and being returned as a result of this.
89pub(super) trait UpdatesAccumulator<Item>: Extend<VectorDiff<Item>> {
90    /// Create a new accumulator with a rough estimation of the number of
91    /// updates this accumulator is going to receive.
92    fn new(num_updates_hint: usize) -> Self;
93}
94
95// Simple implementation for a `Vec<VectorDiff<Item>>` collection for
96// `AsVector<Item, Gap>`.
97impl<Item> UpdatesAccumulator<Item> for Vec<VectorDiff<Item>> {
98    fn new(num_updates_hint: usize) -> Vec<VectorDiff<Item>> {
99        Vec::with_capacity(num_updates_hint)
100    }
101}
102
103/// Internal type that converts [`Update`] into [`VectorDiff`].
104#[derive(Debug)]
105pub(super) struct UpdateToVectorDiff<Item, Acc: UpdatesAccumulator<Item>> {
106    /// Pairs of all known chunks and their respective length. This is the only
107    /// required data for this algorithm.
108    pub chunks: VecDeque<(ChunkIdentifier, ChunkLength)>,
109
110    _phantom: std::marker::PhantomData<(Item, Acc)>,
111}
112
113impl<Item, Acc: UpdatesAccumulator<Item>> UpdateToVectorDiff<Item, Acc> {
114    /// Construct [`UpdateToVectorDiff`], based on an iterator of
115    /// [`Chunk`](super::Chunk)s, used to set up its own internal state.
116    ///
117    /// See [`Self::map`] to learn more about the algorithm.
118    pub fn new<const CAP: usize, Gap>(chunk_iterator: Iter<'_, CAP, Item, Gap>) -> Self {
119        let mut initial_chunk_lengths = VecDeque::new();
120
121        for chunk in chunk_iterator {
122            initial_chunk_lengths.push_back((
123                chunk.identifier(),
124                match chunk.content() {
125                    ChunkContent::Gap(_) => 0,
126                    ChunkContent::Items(items) => items.len(),
127                },
128            ))
129        }
130
131        Self { chunks: initial_chunk_lengths, _phantom: std::marker::PhantomData }
132    }
133
134    /// Construct [`UpdateToVectorDiff`], based on a linked chunk's full
135    /// metadata, used to set up its own internal state.
136    ///
137    /// The vector of [`ChunkMetadata`] must be ordered by their links in the
138    /// linked chunk. If that precondition doesn't hold, then the mapping will
139    /// be incorrect over time, and may cause assertions/panics.
140    ///
141    /// See [`Self::map`] to learn more about the algorithm.
142    pub fn from_metadata(metas: Vec<ChunkMetadata>) -> Self {
143        let initial_chunk_lengths =
144            metas.into_iter().map(|meta| (meta.identifier, meta.num_items)).collect();
145
146        Self { chunks: initial_chunk_lengths, _phantom: std::marker::PhantomData }
147    }
148
149    /// Map several [`Update`] into [`VectorDiff`].
150    ///
151    /// How does this type transform `Update` into `VectorDiff`? There is no
152    /// internal buffer of kind [`eyeball_im::ObservableVector<Item>`],
153    /// which could have been used to generate the `VectorDiff`s. They are
154    /// computed manually.
155    ///
156    /// The only buffered data is pairs of [`ChunkIdentifier`] and
157    /// [`ChunkLength`]. The following rules must be respected (they are defined
158    /// in [`Self::new`]):
159    ///
160    /// * A chunk of kind [`ChunkContent::Gap`] has a length of 0,
161    /// * A chunk of kind [`ChunkContent::Items`] has a length equals to its
162    ///   number of items,
163    /// * The pairs must be ordered exactly like the chunks in [`LinkedChunk`],
164    ///   i.e. the first pair must represent the first chunk, the last pair must
165    ///   represent the last chunk.
166    ///
167    /// The only thing this algorithm does is maintaining the pairs:
168    ///
169    /// * [`Update::NewItemsChunk`] and [`Update::NewGapChunk`] are inserting a
170    ///   new pair with a chunk length of 0 at the appropriate index,
171    /// * [`Update::RemoveChunk`] is removing a pair, and is potentially
172    ///   emitting [`VectorDiff`],
173    /// * [`Update::PushItems`] is increasing the length of the appropriate pair
174    ///   by the number of new items, and is potentially emitting
175    ///   [`VectorDiff`],
176    /// * [`Update::DetachLastItems`] is decreasing the length of the
177    ///   appropriate pair by the number of items to be detached; no
178    ///   [`VectorDiff`] is emitted,
179    /// * [`Update::StartReattachItems`] and [`Update::EndReattachItems`] are
180    ///   respectively muting or unmuting the emission of [`VectorDiff`] by
181    ///   [`Update::PushItems`],
182    /// * [`Update::Clear`] reinitialises the state.
183    ///
184    /// The only `VectorDiff` that are emitted are [`VectorDiff::Insert`],
185    /// [`VectorDiff::Append`], [`VectorDiff::Remove`] and
186    /// [`VectorDiff::Clear`].
187    ///
188    /// `VectorDiff::Append` is an optimisation when numerous
189    /// `VectorDiff::Insert`s have to be emitted at the last position.
190    ///
191    /// `VectorDiff::Insert` needs an index. To compute this index, the
192    /// algorithm will iterate over all pairs to accumulate each chunk length
193    /// until it finds the appropriate pair (given by
194    /// [`Update::PushItems::at`]). This is _the offset_. To this offset, the
195    /// algorithm adds the position's index of the new items (still given by
196    /// [`Update::PushItems::at`]). This is _the index_. This logic works
197    /// for all cases as long as pairs are maintained according to the rules
198    /// hereinabove.
199    ///
200    /// That's a pretty memory compact and computation efficient way to map a
201    /// `Vec<Update<Item, Gap>>` into a `Vec<VectorDiff<Item>>`. The larger the
202    /// `LinkedChunk` capacity is, the fewer pairs the algorithm will have
203    /// to handle, e.g. for 1'000 items and a `LinkedChunk` capacity of 128,
204    /// it's only 8 pairs, that is 256 bytes.
205    ///
206    /// [`LinkedChunk`]: super::LinkedChunk
207    /// [`ChunkContent::Gap`]: super::ChunkContent::Gap
208    /// [`ChunkContent::Content`]: super::ChunkContent::Content
209    pub fn map<Gap>(&mut self, updates: &[Update<Item, Gap>]) -> Acc
210    where
211        Item: Clone,
212    {
213        let mut acc = Acc::new(updates.len());
214
215        // Flags specifying when updates are reattaching detached items.
216        //
217        // TL;DR: This is an optimization to avoid that insertions in the middle of a
218        // chunk cause a large series of `VectorDiff::Remove` and
219        // `VectorDiff::Insert` updates for the elements placed after the
220        // inserted item.
221        //
222        // Why is it useful?
223        //
224        // Imagine a `LinkedChunk::<3, char, ()>` containing `['a', 'b', 'c'] ['d']`. If
225        // one wants to insert [`w`, x`, 'y', 'z'] at position
226        // `Position(ChunkIdentifier(0), 1)`, i.e. at the position of `b`, here is what
227        // happens:
228        //
229        // 1. `LinkedChunk` will split off `['a', 'b', 'c']` at index 1, the chunk
230        //    becomes `['a']` and `b` and `c` are _detached_, thus we have:
231        //
232        //     ['a'] ['d']
233        //
234        // 2. `LinkedChunk` will then insert `w`, `x`, `y` and `z` to get:
235        //
236        //     ['a', 'w', 'x'] ['y', 'z'] ['d']
237        //
238        // 3. `LinkedChunk` will now reattach `b` and `c` after `z`, like so:
239        //
240        //     ['a', 'w', 'x'] ['y', 'z', 'b'] ['c'] ['d']
241        //
242        // This detaching/reattaching approach makes it reliable and safe. Good. Now,
243        // what updates are we going to receive for each step?
244        //
245        // Step 1, detaching last items:
246        //
247        // ```
248        // Update::DetachLastItems { at: Position(ChunkIdentifier(0), 1) }
249        // ```
250        //
251        // Step 2, inserting new items:
252        //
253        // ```
254        // Update::PushItems {
255        //     at: Position(ChunkIdentifier(0), 1),
256        //     items: vec!['w', 'x'],
257        // }
258        // Update::NewItemsChunk {
259        //     previous: Some(ChunkIdentifier(0)),
260        //     new: ChunkIdentifier(2),
261        //     next: Some(ChunkIdentifier(1)),
262        // }
263        // Update::PushItems {
264        //     at: Position(ChunkIdentifier(2), 0),
265        //     items: vec!['y', 'z'],
266        // }
267        // ```
268        //
269        // Step 3, reattaching detached items:
270        //
271        // ```
272        // Update::StartReattachItems
273        // Update::PushItems {
274        //     at: Position(ChunkIdentifier(2), 2),
275        //     items: vec!['b']
276        // }
277        // Update::NewItemsChunk {
278        //     previous: Some(ChunkIdentifier(2)),
279        //     new: ChunkIdentifier(3),
280        //     next: Some(ChunkIdentifier(1)),
281        // }
282        // Update::PushItems {
283        //     at: Position(ChunkIdentifier(3), 0),
284        //     items: vec!['c'],
285        // }
286        // Update::EndReattachItems
287        // ```
288        //
289        // To ensure an optimised behaviour of this algorithm:
290        //
291        // * `Update::DetachLastItems` must not emit `VectorDiff::Remove`,
292        //
293        // * `Update::PushItems` must not emit `VectorDiff::Insert`s or
294        //   `VectorDiff::Append`s if it happens after `StartReattachItems` and before
295        //   `EndReattachItems`. However, `Self::chunks` must always be updated.
296        //
297        // From the `VectorDiff` “point of view”, this optimisation aims at avoiding
298        // removing items to push them again later.
299        let mut reattaching = false;
300        let mut detaching = false;
301
302        for update in updates {
303            match update {
304                Update::NewItemsChunk { previous, new, next }
305                | Update::NewGapChunk { previous, new, next, .. } => {
306                    match (previous, next) {
307                        // New chunk at the end.
308                        (Some(_previous), None) => {
309                            // No need to check `previous`. It's possible that the linked chunk is
310                            // lazily loaded, chunk by chunk. The `next` is always reliable, but the
311                            // `previous` might not exist in-memory yet.
312
313                            self.chunks.push_back((*new, 0));
314                        }
315
316                        // New chunk at the beginning.
317                        (None, Some(next)) => {
318                            debug_assert!(
319                                matches!(self.chunks.front(), Some((n, _)) if n == next),
320                                "Inserting new chunk at the end: The previous chunk is invalid"
321                            );
322
323                            self.chunks.push_front((*new, 0));
324                        }
325
326                        // New chunk is inserted between 2 chunks.
327                        (Some(_previous), Some(next)) => {
328                            let next_chunk_index = self
329                                .chunks
330                                .iter()
331                                .position(|(chunk_identifier, _)| chunk_identifier == next)
332                                // SAFETY: Assuming `LinkedChunk` and `ObservableUpdates` are not
333                                // buggy, and assuming `Self::chunks` is correctly initialized, it
334                                // is not possible to insert a chunk between two chunks where one
335                                // does not exist. If this predicate fails, it means `LinkedChunk`
336                                // or `ObservableUpdates` contain a bug.
337                                .expect("Inserting new chunk: The chunk is not found");
338
339                            // No need to check `previous`. It's possible that the linked chunk is
340                            // lazily loaded, chunk by chunk. The `next` is always reliable, but the
341                            // `previous` might not exist in-memory yet.
342
343                            self.chunks.insert(next_chunk_index, (*new, 0));
344                        }
345
346                        // First chunk!
347                        (None, None) if self.chunks.is_empty() => {
348                            self.chunks.push_back((*new, 0));
349                        }
350
351                        // Impossible state.
352                        (None, None) => {
353                            unreachable!(
354                                "Inserting new chunk with no previous nor next chunk identifiers \
355                                is impossible"
356                            );
357                        }
358                    }
359                }
360
361                Update::RemoveChunk(chunk_identifier) => {
362                    let (offset, (chunk_index, _)) =
363                        self.map_to_offset(&Position(*chunk_identifier, 0));
364
365                    let (_, number_of_items) = self
366                        .chunks
367                        .remove(chunk_index)
368                        .expect("Removing an index out of the bounds");
369
370                    // Removing at the same index because each `Remove` shifts items to the left.
371                    acc.extend(repeat_n(VectorDiff::Remove { index: offset }, number_of_items));
372                }
373
374                Update::PushItems { at: position, items } => {
375                    let number_of_chunks = self.chunks.len();
376                    let (offset, (chunk_index, chunk_length)) = self.map_to_offset(position);
377
378                    let is_pushing_back =
379                        chunk_index + 1 == number_of_chunks && position.index() >= *chunk_length;
380
381                    // Add the number of items to the chunk in `self.chunks`.
382                    *chunk_length += items.len();
383
384                    // See `reattaching` to learn more.
385                    if reattaching {
386                        continue;
387                    }
388
389                    // Optimisation: we can emit a `VectorDiff::Append` in this particular case.
390                    if is_pushing_back && !detaching {
391                        acc.extend([VectorDiff::Append { values: items.into() }]);
392                    }
393                    // No optimisation: let's emit `VectorDiff::Insert`.
394                    else {
395                        acc.extend(items.iter().enumerate().map(|(nth, item)| {
396                            VectorDiff::Insert { index: offset + nth, value: item.clone() }
397                        }));
398                    }
399                }
400
401                Update::ReplaceItem { at: position, item } => {
402                    let (offset, (_chunk_index, _chunk_length)) = self.map_to_offset(position);
403
404                    // The chunk length doesn't change.
405
406                    acc.extend([VectorDiff::Set { index: offset, value: item.clone() }]);
407                }
408
409                Update::RemoveItem { at: position } => {
410                    let (offset, (_chunk_index, chunk_length)) = self.map_to_offset(position);
411
412                    // Remove one item to the chunk in `self.chunks`.
413                    *chunk_length -= 1;
414
415                    // See `reattaching` to learn more.
416                    if reattaching {
417                        continue;
418                    }
419
420                    // Let's emit a `VectorDiff::Remove`.
421                    acc.extend([VectorDiff::Remove { index: offset }]);
422                }
423
424                Update::DetachLastItems { at: position } => {
425                    let expected_chunk_identifier = position.chunk_identifier();
426                    let new_length = position.index();
427
428                    let chunk_length = self
429                        .chunks
430                        .iter_mut()
431                        .find_map(|(chunk_identifier, chunk_length)| {
432                            (*chunk_identifier == expected_chunk_identifier).then_some(chunk_length)
433                        })
434                        // SAFETY: Assuming `LinkedChunk` and `ObservableUpdates` are not buggy, and
435                        // assuming `Self::chunks` is correctly initialized, it is not possible to
436                        // detach items from a chunk that does not exist. If this predicate fails,
437                        // it means `LinkedChunk` or `ObservableUpdates` contain a bug.
438                        .expect("Detach last items: The chunk is not found");
439
440                    *chunk_length = new_length;
441
442                    // Entering the _detaching_ mode.
443                    detaching = true;
444                }
445
446                Update::StartReattachItems => {
447                    // Entering the _reattaching_ mode.
448                    reattaching = true;
449                }
450
451                Update::EndReattachItems => {
452                    // Exiting the _reattaching_ mode.
453                    reattaching = false;
454
455                    // Exiting the _detaching_ mode.
456                    detaching = false;
457                }
458
459                Update::Clear => {
460                    // Clean `self.chunks`.
461                    self.chunks.clear();
462
463                    // Let's straightforwardly emit a `VectorDiff::Clear`.
464                    acc.extend([VectorDiff::Clear]);
465                }
466            }
467        }
468
469        acc
470    }
471
472    fn map_to_offset(&mut self, position: &Position) -> (usize, (usize, &mut usize)) {
473        let expected_chunk_identifier = position.chunk_identifier();
474
475        let (offset, (chunk_index, chunk_length)) = {
476            let control_flow = self.chunks.iter_mut().enumerate().try_fold(
477                position.index(),
478                |offset, (chunk_index, (chunk_identifier, chunk_length))| {
479                    if chunk_identifier == &expected_chunk_identifier {
480                        ControlFlow::Break((offset, (chunk_index, chunk_length)))
481                    } else {
482                        ControlFlow::Continue(offset + *chunk_length)
483                    }
484                },
485            );
486
487            match control_flow {
488                // Chunk has been found, and all values have been calculated as
489                // expected.
490                ControlFlow::Break(values) => values,
491
492                // Chunk has not been found.
493                ControlFlow::Continue(..) => {
494                    // SAFETY: Assuming `LinkedChunk` and `ObservableUpdates` are not buggy, and
495                    // assuming `Self::chunks` is correctly initialized, it is not possible to work
496                    // on a chunk that does not exist. If this predicate fails, it means
497                    // `LinkedChunk` or `ObservableUpdates` contain a bug.
498                    panic!("The chunk is not found");
499                }
500            }
501        };
502
503        (offset, (chunk_index, chunk_length))
504    }
505}
506
507#[cfg(test)]
508mod tests {
509    use std::fmt::Debug;
510
511    use assert_matches::assert_matches;
512    use imbl::{vector, Vector};
513
514    use super::{
515        super::{Chunk, ChunkIdentifierGenerator, LinkedChunk, Update},
516        VectorDiff,
517    };
518
519    fn apply_and_assert_eq<Item>(
520        accumulator: &mut Vector<Item>,
521        diffs: Vec<VectorDiff<Item>>,
522        expected_diffs: &[VectorDiff<Item>],
523    ) where
524        Item: PartialEq + Clone + Debug,
525    {
526        assert_eq!(diffs, expected_diffs);
527
528        for diff in diffs {
529            diff.apply(accumulator);
530        }
531    }
532
533    #[test]
534    fn test_as_vector() {
535        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
536        let mut as_vector = linked_chunk.as_vector().unwrap();
537
538        let mut accumulator = Vector::new();
539
540        assert!(as_vector.take().is_empty());
541
542        linked_chunk.push_items_back(['a', 'b', 'c', 'd']);
543        #[rustfmt::skip]
544        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d']);
545
546        // From an `ObservableVector` point of view, it would look like:
547        //
548        // 0   1   2   3   4
549        // +---+---+---+---+
550        // | a | b | c | d |
551        // +---+---+---+---+
552        // ^^^^^^^^^^^^^^^^
553        // |
554        // new
555        apply_and_assert_eq(
556            &mut accumulator,
557            as_vector.take(),
558            &[
559                VectorDiff::Append { values: vector!['a', 'b', 'c'] },
560                VectorDiff::Append { values: vector!['d'] },
561            ],
562        );
563
564        linked_chunk
565            .insert_items_at(
566                linked_chunk.item_position(|item| *item == 'b').unwrap(),
567                ['w', 'x', 'y', 'z'],
568            )
569            .unwrap();
570        assert_items_eq!(linked_chunk, ['a', 'w', 'x'] ['y', 'z', 'b'] ['c'] ['d']);
571
572        // From an `ObservableVector` point of view, it would look like:
573        //
574        // 0   1   2   3   4   5   6   7   8
575        // +---+---+---+---+---+---+---+---+
576        // | a | w | x | y | z | b | c | d |
577        // +---+---+---+---+---+---+---+---+
578        //     ^^^^^^^^^^^^^^^^
579        //     |
580        //     new
581        apply_and_assert_eq(
582            &mut accumulator,
583            as_vector.take(),
584            &[
585                VectorDiff::Insert { index: 1, value: 'w' },
586                VectorDiff::Insert { index: 2, value: 'x' },
587                VectorDiff::Insert { index: 3, value: 'y' },
588                VectorDiff::Insert { index: 4, value: 'z' },
589            ],
590        );
591
592        linked_chunk.push_gap_back(());
593        linked_chunk.push_items_back(['e', 'f', 'g', 'h']);
594        assert_items_eq!(
595            linked_chunk,
596            ['a', 'w', 'x'] ['y', 'z', 'b'] ['c'] ['d'] [-] ['e', 'f', 'g'] ['h']
597        );
598
599        // From an `ObservableVector` point of view, it would look like:
600        //
601        // 0   1   2   3   4   5   6   7   8   9   10  11  12
602        // +---+---+---+---+---+---+---+---+---+---+---+---+
603        // | a | w | x | y | z | b | c | d | e | f | g | h |
604        // +---+---+---+---+---+---+---+---+---+---+---+---+
605        //                                 ^^^^^^^^^^^^^^^^
606        //                                 |
607        //                                 new
608        apply_and_assert_eq(
609            &mut accumulator,
610            as_vector.take(),
611            &[
612                VectorDiff::Append { values: vector!['e', 'f', 'g'] },
613                VectorDiff::Append { values: vector!['h'] },
614            ],
615        );
616
617        linked_chunk
618            .replace_gap_at(
619                ['i', 'j', 'k', 'l'],
620                linked_chunk.chunk_identifier(|chunk| chunk.is_gap()).unwrap(),
621            )
622            .unwrap();
623        assert_items_eq!(
624            linked_chunk,
625            ['a', 'w', 'x'] ['y', 'z', 'b'] ['c'] ['d'] ['i', 'j', 'k'] ['l'] ['e', 'f', 'g'] ['h']
626        );
627
628        // From an `ObservableVector` point of view, it would look like:
629        //
630        // 0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16
631        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
632        // | a | w | x | y | z | b | c | d | i | j | k | l | e | f | g | h |
633        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
634        //                                 ^^^^^^^^^^^^^^^^
635        //                                 |
636        //                                 new
637        apply_and_assert_eq(
638            &mut accumulator,
639            as_vector.take(),
640            &[
641                VectorDiff::Insert { index: 8, value: 'i' },
642                VectorDiff::Insert { index: 9, value: 'j' },
643                VectorDiff::Insert { index: 10, value: 'k' },
644                VectorDiff::Insert { index: 11, value: 'l' },
645            ],
646        );
647
648        linked_chunk
649            .insert_items_at(linked_chunk.item_position(|item| *item == 'a').unwrap(), ['m'])
650            .unwrap();
651        assert_items_eq!(
652            linked_chunk,
653            ['m', 'a', 'w'] ['x'] ['y', 'z', 'b'] ['c'] ['d'] ['i', 'j', 'k'] ['l'] ['e', 'f', 'g'] ['h']
654        );
655
656        // From an `ObservableVector` point of view, it would look like:
657        //
658        // 0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17
659        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
660        // | m | a | w | x | y | z | b | c | d | i | j | k | l | e | f | g | h |
661        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
662        // ^^^^
663        // |
664        // new
665        apply_and_assert_eq(
666            &mut accumulator,
667            as_vector.take(),
668            &[VectorDiff::Insert { index: 0, value: 'm' }],
669        );
670
671        let removed_item = linked_chunk
672            .remove_item_at(linked_chunk.item_position(|item| *item == 'c').unwrap())
673            .unwrap();
674        assert_eq!(removed_item, 'c');
675        assert_items_eq!(
676            linked_chunk,
677            ['m', 'a', 'w'] ['x'] ['y', 'z', 'b'] ['d'] ['i', 'j', 'k'] ['l'] ['e', 'f', 'g'] ['h']
678        );
679
680        // From an `ObservableVector` point of view, it would look like:
681        //
682        // 0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16
683        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
684        // | m | a | w | x | y | z | b | d | i | j | k | l | e | f | g | h |
685        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
686        //                             ^
687        //                             |
688        //                             `c` has been removed
689        apply_and_assert_eq(&mut accumulator, as_vector.take(), &[VectorDiff::Remove { index: 7 }]);
690
691        let removed_item = linked_chunk
692            .remove_item_at(linked_chunk.item_position(|item| *item == 'z').unwrap())
693            .unwrap();
694        assert_eq!(removed_item, 'z');
695        assert_items_eq!(
696            linked_chunk,
697            ['m', 'a', 'w'] ['x'] ['y', 'b'] ['d'] ['i', 'j', 'k'] ['l'] ['e', 'f', 'g'] ['h']
698        );
699
700        // From an `ObservableVector` point of view, it would look like:
701        //
702        // 0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
703        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
704        // | m | a | w | x | y | b | d | i | j | k | l | e | f | g | h |
705        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
706        //                     ^
707        //                     |
708        //                     `z` has been removed
709        apply_and_assert_eq(&mut accumulator, as_vector.take(), &[VectorDiff::Remove { index: 5 }]);
710
711        linked_chunk
712            .insert_items_at(linked_chunk.item_position(|item| *item == 'h').unwrap(), ['z'])
713            .unwrap();
714
715        assert_items_eq!(
716            linked_chunk,
717            ['m', 'a', 'w'] ['x'] ['y', 'b'] ['d'] ['i', 'j', 'k'] ['l'] ['e', 'f', 'g'] ['z', 'h']
718        );
719
720        // From an `ObservableVector` point of view, it would look like:
721        //
722        // 0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16
723        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
724        // | m | a | w | x | y | b | d | i | j | k | l | e | f | g | z | h |
725        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
726        //                                                         ^^^^
727        //                                                         |
728        //                                                         new!
729        apply_and_assert_eq(
730            &mut accumulator,
731            as_vector.take(),
732            &[VectorDiff::Insert { index: 14, value: 'z' }],
733        );
734
735        // Ensure the “reconstitued” vector is the one expected.
736        assert_eq!(
737            accumulator,
738            vector!['m', 'a', 'w', 'x', 'y', 'b', 'd', 'i', 'j', 'k', 'l', 'e', 'f', 'g', 'z', 'h']
739        );
740
741        // Replace element 8 by an uppercase J.
742        linked_chunk
743            .replace_item_at(linked_chunk.item_position(|item| *item == 'j').unwrap(), 'J')
744            .unwrap();
745
746        assert_items_eq!(
747            linked_chunk,
748            ['m', 'a', 'w'] ['x'] ['y', 'b'] ['d'] ['i', 'J', 'k'] ['l'] ['e', 'f', 'g'] ['z', 'h']
749        );
750
751        // From an `ObservableVector` point of view, it would look like:
752        //
753        // 0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16
754        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
755        // | m | a | w | x | y | b | d | i | J | k | l | e | f | g | z | h |
756        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
757        //                                 ^^^^
758        //                                 |
759        //                                 new!
760        apply_and_assert_eq(
761            &mut accumulator,
762            as_vector.take(),
763            &[VectorDiff::Set { index: 8, value: 'J' }],
764        );
765
766        // Let's try to clear the linked chunk now.
767        linked_chunk.clear();
768
769        apply_and_assert_eq(&mut accumulator, as_vector.take(), &[VectorDiff::Clear]);
770        assert!(accumulator.is_empty());
771
772        drop(linked_chunk);
773        assert!(as_vector.take().is_empty());
774    }
775
776    #[test]
777    fn test_as_vector_with_update_clear() {
778        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
779        let mut as_vector = linked_chunk.as_vector().unwrap();
780
781        {
782            // 1 initial chunk in the `UpdateToVectorDiff` mapper.
783            let chunks = &as_vector.mapper.chunks;
784            assert_eq!(chunks.len(), 1);
785            assert_eq!(chunks[0].0, ChunkIdentifierGenerator::FIRST_IDENTIFIER);
786            assert_eq!(chunks[0].1, 0);
787
788            assert!(as_vector.take().is_empty());
789        }
790
791        linked_chunk.push_items_back(['a', 'b', 'c', 'd']);
792
793        {
794            let diffs = as_vector.take();
795            assert_eq!(diffs.len(), 2);
796            assert_matches!(&diffs[0], VectorDiff::Append { .. });
797            assert_matches!(&diffs[1], VectorDiff::Append { .. });
798
799            // 2 chunks in the `UpdateToVectorDiff` mapper.
800            assert_eq!(as_vector.mapper.chunks.len(), 2);
801        }
802
803        linked_chunk.clear();
804
805        {
806            let diffs = as_vector.take();
807            assert_eq!(diffs.len(), 1);
808            assert_matches!(&diffs[0], VectorDiff::Clear);
809
810            // 1 chunk in the `UpdateToVectorDiff` mapper.
811            let chunks = &as_vector.mapper.chunks;
812            assert_eq!(chunks.len(), 1);
813            assert_eq!(chunks[0].0, ChunkIdentifierGenerator::FIRST_IDENTIFIER);
814            assert_eq!(chunks[0].1, 0);
815        }
816
817        // And we can push again.
818        linked_chunk.push_items_back(['a', 'b', 'c', 'd']);
819
820        {
821            let diffs = as_vector.take();
822            assert_eq!(diffs.len(), 2);
823            assert_matches!(&diffs[0], VectorDiff::Append { .. });
824            assert_matches!(&diffs[1], VectorDiff::Append { .. });
825        }
826    }
827
828    #[test]
829    fn test_updates_are_drained_when_constructing_as_vector() {
830        let mut linked_chunk = LinkedChunk::<10, char, ()>::new_with_update_history();
831
832        linked_chunk.push_items_back(['a']);
833
834        let mut as_vector = linked_chunk.as_vector().unwrap();
835        let diffs = as_vector.take();
836
837        // `diffs` are empty because `AsVector` is built _after_ `LinkedChunk`
838        // has been updated.
839        assert!(diffs.is_empty());
840
841        linked_chunk.push_items_back(['b']);
842
843        let diffs = as_vector.take();
844
845        // `diffs` is not empty because new updates are coming.
846        assert_eq!(diffs.len(), 1);
847    }
848
849    #[test]
850    fn test_as_vector_with_initial_content() {
851        // Fill the linked chunk with some initial items.
852        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
853        linked_chunk.push_items_back(['a', 'b', 'c', 'd']);
854
855        #[rustfmt::skip]
856        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d']);
857
858        // Empty updates first.
859        let _ = linked_chunk.updates().unwrap().take();
860
861        // Start observing future updates.
862        let mut as_vector = linked_chunk.as_vector().unwrap();
863
864        assert!(as_vector.take().is_empty());
865
866        // It's important to cause a change that will create new chunks, like pushing
867        // enough items.
868        linked_chunk.push_items_back(['e', 'f', 'g']);
869        #[rustfmt::skip]
870        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] ['g']);
871
872        // And the vector diffs can be computed without crashing.
873        let diffs = as_vector.take();
874        assert_eq!(diffs.len(), 2);
875        assert_matches!(&diffs[0], VectorDiff::Append { values } => {
876            assert_eq!(*values, ['e', 'f'].into());
877        });
878        assert_matches!(&diffs[1], VectorDiff::Append { values } => {
879            assert_eq!(*values, ['g'].into());
880        });
881    }
882
883    #[test]
884    fn test_as_vector_remove_chunk() {
885        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
886        let mut as_vector = linked_chunk.as_vector().unwrap();
887
888        let mut accumulator = Vector::new();
889
890        assert!(as_vector.take().is_empty());
891
892        linked_chunk.push_items_back(['a', 'b']);
893        linked_chunk.push_gap_back(());
894        linked_chunk.push_items_back(['c']);
895        linked_chunk.push_gap_back(());
896        linked_chunk.push_items_back(['d', 'e', 'f', 'g']);
897
898        assert_items_eq!(linked_chunk, ['a', 'b'] [-] ['c'] [-] ['d', 'e', 'f'] ['g']);
899
900        // From an `ObservableVector` point of view, it would look like:
901        //
902        // 0   1   2   3   4   5   6   7
903        // +---+---+---+---+---+---+---+
904        // | a | b | c | d | e | f | g |
905        // +---+---+---+---+---+---+---+
906        // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
907        // |
908        // new
909        apply_and_assert_eq(
910            &mut accumulator,
911            as_vector.take(),
912            &[
913                VectorDiff::Append { values: vector!['a', 'b'] },
914                VectorDiff::Append { values: vector!['c'] },
915                VectorDiff::Append { values: vector!['d', 'e', 'f'] },
916                VectorDiff::Append { values: vector!['g'] },
917            ],
918        );
919
920        // Empty a chunk, and remove it once it is empty.
921        linked_chunk
922            .remove_item_at(linked_chunk.item_position(|item| *item == 'c').unwrap())
923            .unwrap();
924
925        assert_items_eq!(linked_chunk, ['a', 'b'] [-] [-] ['d', 'e', 'f'] ['g']);
926
927        // From an `ObservableVector` point of view, it would look like:
928        //
929        // 0   1   2   3   4   5   6
930        // +---+---+---+---+---+---+
931        // | a | b | d | e | f | g |
932        // +---+---+---+---+---+---+
933        //         ^
934        //         |
935        //         `c` has been removed
936        apply_and_assert_eq(&mut accumulator, as_vector.take(), &[VectorDiff::Remove { index: 2 }]);
937
938        // Remove a gap.
939        linked_chunk
940            .remove_empty_chunk_at(linked_chunk.chunk_identifier(Chunk::is_gap).unwrap())
941            .unwrap();
942
943        assert_items_eq!(linked_chunk, ['a', 'b'] [-] ['d', 'e', 'f'] ['g']);
944
945        // From an `ObservableVector` point of view, nothing changes.
946        apply_and_assert_eq(&mut accumulator, as_vector.take(), &[]);
947
948        // Remove a non-empty chunk. This is not possible with the public
949        // `LinkedChunk` API yet, but let's try.
950        let d_e_and_f = linked_chunk.item_position(|item| *item == 'f').unwrap().chunk_identifier();
951        let updates = linked_chunk.updates().unwrap();
952        updates.push(Update::RemoveChunk(d_e_and_f));
953        // Note that `linked_chunk` is getting out of sync with `AsVector`
954        // but it's just a test. Better, it's the end of the test.
955
956        // From an `ObservableVector` point of view, it would look like:
957        //
958        // 0   1   2   3
959        // +---+---+---+
960        // | a | b | g |
961        // +---+---+---+
962        //         ^
963        //         |
964        //         `d`, `e` and `f` have been removed
965        apply_and_assert_eq(
966            &mut accumulator,
967            as_vector.take(),
968            &[
969                VectorDiff::Remove { index: 2 },
970                VectorDiff::Remove { index: 2 },
971                VectorDiff::Remove { index: 2 },
972            ],
973        );
974    }
975
976    #[cfg(not(target_family = "wasm"))]
977    mod proptests {
978        use proptest::prelude::*;
979
980        use super::*;
981
982        #[derive(Debug, Clone)]
983        enum AsVectorOperation {
984            PushItems { items: Vec<char> },
985            PushGap,
986            ReplaceLastGap { items: Vec<char> },
987            RemoveItem { item: char },
988        }
989
990        fn as_vector_operation_strategy() -> impl Strategy<Value = AsVectorOperation> {
991            prop_oneof![
992                3 => prop::collection::vec(prop::char::ranges(vec!['a'..='z', 'A'..='Z'].into()), 0..=25)
993                    .prop_map(|items| AsVectorOperation::PushItems { items }),
994
995                2 => Just(AsVectorOperation::PushGap),
996
997                1 => prop::collection::vec(prop::char::ranges(vec!['a'..='z', 'A'..='Z'].into()), 0..=25)
998                    .prop_map(|items| AsVectorOperation::ReplaceLastGap { items }),
999
1000                1 => prop::char::ranges(vec!['a'..='z', 'A'..='Z'].into())
1001                    .prop_map(|item| AsVectorOperation::RemoveItem { item }),
1002            ]
1003        }
1004
1005        proptest! {
1006            #[test]
1007            fn test_as_vector_is_correct(
1008                operations in prop::collection::vec(as_vector_operation_strategy(), 50..=200)
1009            ) {
1010                let mut linked_chunk = LinkedChunk::<10, char, ()>::new_with_update_history();
1011                let mut as_vector = linked_chunk.as_vector().unwrap();
1012
1013                for operation in operations {
1014                    match operation {
1015                        AsVectorOperation::PushItems { items } => {
1016                            linked_chunk.push_items_back(items);
1017                        }
1018
1019                        AsVectorOperation::PushGap => {
1020                            linked_chunk.push_gap_back(());
1021                        }
1022
1023                        AsVectorOperation::ReplaceLastGap { items } => {
1024                            let Some(gap_identifier) = linked_chunk
1025                                .rchunks()
1026                                .find_map(|chunk| chunk.is_gap().then_some(chunk.identifier()))
1027                            else {
1028                                continue;
1029                            };
1030
1031                            linked_chunk.replace_gap_at(items, gap_identifier).expect("Failed to replace a gap");
1032                        }
1033
1034                        AsVectorOperation::RemoveItem { item: expected_item } => {
1035                            let Some(position) = linked_chunk
1036                                .items().find_map(|(position, item)| (*item == expected_item).then_some(position))
1037                            else {
1038                                continue;
1039                            };
1040
1041                            linked_chunk.remove_item_at(position).expect("Failed to remove an item");
1042                        }
1043                    }
1044                }
1045
1046                let mut vector_from_diffs = Vec::new();
1047
1048                // Read all updates as `VectorDiff` and rebuild a `Vec<char>`.
1049                for diff in as_vector.take() {
1050                    match diff {
1051                        VectorDiff::Insert { index, value } => vector_from_diffs.insert(index, value),
1052                        VectorDiff::Append { values } => {
1053                            let mut values = values.iter().copied().collect();
1054
1055                            vector_from_diffs.append(&mut values);
1056                        }
1057                        VectorDiff::Remove { index } => {
1058                            vector_from_diffs.remove(index);
1059                        }
1060                        _ => unreachable!(),
1061                    }
1062                }
1063
1064                // Iterate over all chunks and collect items as `Vec<char>`.
1065                let vector_from_chunks = linked_chunk.items().map(|(_, item)| *item).collect::<Vec<_>>();
1066
1067                // Compare both `Vec`s.
1068                assert_eq!(vector_from_diffs, vector_from_chunks);
1069            }
1070        }
1071    }
1072}