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}