matrix_sdk_common/linked_chunk/
mod.rs

1// Copyright 2024 The Matrix.org Foundation C.I.C.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![allow(rustdoc::private_intra_doc_links)]
16
17//! A linked chunk is the underlying data structure that holds all events.
18
19/// A macro to test the items and the gap of a `LinkedChunk`.
20/// A chunk is delimited by `[` and `]`. An item chunk has the form `[a, b,
21/// c]` where `a`, `b` and `c` are items. A gap chunk has the form `[-]`.
22///
23/// For example, here is an assertion of 7 chunks: 1 items chunk, 1 gap
24/// chunk, 2 items chunks, 1 gap chunk, 2 items chunk. `a` is the oldest
25/// item of the oldest chunk (the first chunk), and `i` is the oldest (and
26/// newest) item of the newest chunk (the last chunk).
27///
28/// ```rust,no_run
29/// assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c', 'd'] ['e'] [-] ['f', 'g', 'h'] ['i']);
30/// ```
31#[cfg(test)]
32macro_rules! assert_items_eq {
33    ( @_ [ $iterator:ident ] { [-] $( $rest:tt )* } { $( $accumulator:tt )* } ) => {
34        assert_items_eq!(
35            @_
36            [ $iterator ]
37            { $( $rest )* }
38            {
39                $( $accumulator )*
40                {
41                    let chunk = $iterator .next().expect("next chunk (expect gap)");
42                    assert!(chunk.is_gap(), "chunk should be a gap");
43                }
44            }
45        )
46    };
47
48    ( @_ [ $iterator:ident ] { [ $( $item:expr ),* ] $( $rest:tt )* } { $( $accumulator:tt )* } ) => {
49        assert_items_eq!(
50            @_
51            [ $iterator ]
52            { $( $rest )* }
53            {
54                $( $accumulator )*
55                {
56                    let chunk = $iterator .next().expect("next chunk (expect items)");
57                    assert!(chunk.is_items(), "chunk should contain items");
58
59                    let $crate::linked_chunk::ChunkContent::Items(items) = chunk.content() else {
60                        unreachable!()
61                    };
62
63                    let mut items_iterator = items.iter();
64
65                    $(
66                        assert_eq!(items_iterator.next(), Some(& $item ));
67                    )*
68
69                    assert!(items_iterator.next().is_none(), "no more items");
70                }
71            }
72        )
73    };
74
75    ( @_ [ $iterator:ident ] {} { $( $accumulator:tt )* } ) => {
76        {
77            $( $accumulator )*
78            assert!( $iterator .next().is_none(), "no more chunks");
79        }
80    };
81
82    ( $linked_chunk:expr, $( $all:tt )* ) => {
83        assert_items_eq!(
84            @_
85            [ iterator ]
86            { $( $all )* }
87            {
88                let mut iterator = $linked_chunk.chunks();
89            }
90        )
91    }
92}
93
94mod as_vector;
95pub mod lazy_loader;
96mod order_tracker;
97pub mod relational;
98mod updates;
99
100use std::{
101    fmt::{self, Display},
102    marker::PhantomData,
103    ptr::NonNull,
104    sync::atomic::{self, AtomicU64},
105};
106
107pub use as_vector::*;
108pub use order_tracker::OrderTracker;
109use ruma::{EventId, OwnedEventId, OwnedRoomId, RoomId};
110use serde::{Deserialize, Serialize};
111pub use updates::*;
112
113/// An identifier for a linked chunk; borrowed variant.
114#[derive(Debug, Clone, Copy, PartialEq)]
115pub enum LinkedChunkId<'a> {
116    Room(&'a RoomId),
117    Thread(&'a RoomId, &'a EventId),
118}
119
120impl Display for LinkedChunkId<'_> {
121    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
122        match self {
123            Self::Room(room_id) => write!(f, "{room_id}"),
124            Self::Thread(room_id, thread_root) => {
125                write!(f, "{room_id}:thread:{thread_root}")
126            }
127        }
128    }
129}
130
131impl LinkedChunkId<'_> {
132    pub fn storage_key(&self) -> impl '_ + AsRef<[u8]> {
133        match self {
134            LinkedChunkId::Room(room_id) => room_id.to_string(),
135            LinkedChunkId::Thread(room_id, event_id) => format!("t:{room_id}:{event_id}"),
136        }
137    }
138
139    pub fn to_owned(&self) -> OwnedLinkedChunkId {
140        match self {
141            LinkedChunkId::Room(room_id) => OwnedLinkedChunkId::Room((*room_id).to_owned()),
142            LinkedChunkId::Thread(room_id, event_id) => {
143                OwnedLinkedChunkId::Thread((*room_id).to_owned(), (*event_id).to_owned())
144            }
145        }
146    }
147}
148
149impl<'a> From<&'a OwnedLinkedChunkId> for LinkedChunkId<'a> {
150    fn from(value: &'a OwnedLinkedChunkId) -> Self {
151        value.as_ref()
152    }
153}
154
155impl PartialEq<&OwnedLinkedChunkId> for LinkedChunkId<'_> {
156    fn eq(&self, other: &&OwnedLinkedChunkId) -> bool {
157        match (self, other) {
158            (LinkedChunkId::Room(a), OwnedLinkedChunkId::Room(b)) => *a == b,
159            (LinkedChunkId::Thread(r, ev), OwnedLinkedChunkId::Thread(r2, ev2)) => {
160                r == r2 && ev == ev2
161            }
162            (LinkedChunkId::Room(..), OwnedLinkedChunkId::Thread(..))
163            | (LinkedChunkId::Thread(..), OwnedLinkedChunkId::Room(..)) => false,
164        }
165    }
166}
167
168impl PartialEq<LinkedChunkId<'_>> for OwnedLinkedChunkId {
169    fn eq(&self, other: &LinkedChunkId<'_>) -> bool {
170        other.eq(&self)
171    }
172}
173
174/// An identifier for a linked chunk; owned variant.
175#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
176pub enum OwnedLinkedChunkId {
177    Room(OwnedRoomId),
178    Thread(OwnedRoomId, OwnedEventId),
179}
180
181impl Display for OwnedLinkedChunkId {
182    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
183        self.as_ref().fmt(f)
184    }
185}
186
187impl OwnedLinkedChunkId {
188    pub fn as_ref(&self) -> LinkedChunkId<'_> {
189        match self {
190            OwnedLinkedChunkId::Room(room_id) => LinkedChunkId::Room(room_id.as_ref()),
191            OwnedLinkedChunkId::Thread(room_id, event_id) => {
192                LinkedChunkId::Thread(room_id.as_ref(), event_id.as_ref())
193            }
194        }
195    }
196
197    pub fn room_id(&self) -> &RoomId {
198        match self {
199            OwnedLinkedChunkId::Room(room_id) => room_id,
200            OwnedLinkedChunkId::Thread(room_id, ..) => room_id,
201        }
202    }
203}
204
205impl From<LinkedChunkId<'_>> for OwnedLinkedChunkId {
206    fn from(value: LinkedChunkId<'_>) -> Self {
207        value.to_owned()
208    }
209}
210
211/// Errors of [`LinkedChunk`].
212#[derive(thiserror::Error, Debug)]
213pub enum Error {
214    /// A chunk identifier is invalid.
215    #[error("The chunk identifier is invalid: `{identifier:?}`")]
216    InvalidChunkIdentifier {
217        /// The chunk identifier.
218        identifier: ChunkIdentifier,
219    },
220
221    /// A chunk is a gap chunk, and it was expected to be an items.
222    #[error("The chunk is a gap: `{identifier:?}`")]
223    ChunkIsAGap {
224        /// The chunk identifier.
225        identifier: ChunkIdentifier,
226    },
227
228    /// A chunk is an items chunk, and it was expected to be a gap.
229    #[error("The chunk is an item: `{identifier:?}`")]
230    ChunkIsItems {
231        /// The chunk identifier.
232        identifier: ChunkIdentifier,
233    },
234
235    /// A chunk is an items chunk, and it was expected to be empty.
236    #[error("The chunk is a non-empty item chunk: `{identifier:?}`")]
237    RemovingNonEmptyItemsChunk {
238        /// The chunk identifier.
239        identifier: ChunkIdentifier,
240    },
241
242    /// We're trying to remove the only chunk in the `LinkedChunk`, and it can't
243    /// be empty.
244    #[error("Trying to remove the only chunk, but a linked chunk can't be empty")]
245    RemovingLastChunk,
246
247    /// An item index is invalid.
248    #[error("The item index is invalid: `{index}`")]
249    InvalidItemIndex {
250        /// The index.
251        index: usize,
252    },
253}
254
255/// Links of a `LinkedChunk`, i.e. the first and last [`Chunk`].
256///
257/// This type was introduced to avoid borrow checking errors when mutably
258/// referencing a subset of fields of a `LinkedChunk`.
259struct Ends<const CHUNK_CAPACITY: usize, Item, Gap> {
260    /// The first chunk.
261    first: NonNull<Chunk<CHUNK_CAPACITY, Item, Gap>>,
262    /// The last chunk.
263    last: Option<NonNull<Chunk<CHUNK_CAPACITY, Item, Gap>>>,
264}
265
266impl<const CAP: usize, Item, Gap> Ends<CAP, Item, Gap> {
267    /// Get the first chunk, as an immutable reference.
268    fn first_chunk(&self) -> &Chunk<CAP, Item, Gap> {
269        unsafe { self.first.as_ref() }
270    }
271
272    /// Get the first chunk, as a mutable reference.
273    fn first_chunk_mut(&mut self) -> &mut Chunk<CAP, Item, Gap> {
274        unsafe { self.first.as_mut() }
275    }
276
277    /// Get the latest chunk, as an immutable reference.
278    fn latest_chunk(&self) -> &Chunk<CAP, Item, Gap> {
279        unsafe { self.last.unwrap_or(self.first).as_ref() }
280    }
281
282    /// Get the latest chunk, as a mutable reference.
283    fn latest_chunk_mut(&mut self) -> &mut Chunk<CAP, Item, Gap> {
284        unsafe { self.last.as_mut().unwrap_or(&mut self.first).as_mut() }
285    }
286
287    /// Get the chunk as a reference, from its identifier, if it exists.
288    fn chunk(&self, identifier: ChunkIdentifier) -> Option<&Chunk<CAP, Item, Gap>> {
289        let mut chunk = self.latest_chunk();
290
291        loop {
292            if chunk.identifier() == identifier {
293                return Some(chunk);
294            }
295
296            chunk = chunk.previous()?;
297        }
298    }
299
300    /// Get the chunk as a mutable reference, from its identifier, if it exists.
301    fn chunk_mut(&mut self, identifier: ChunkIdentifier) -> Option<&mut Chunk<CAP, Item, Gap>> {
302        let mut chunk = self.latest_chunk_mut();
303
304        loop {
305            if chunk.identifier() == identifier {
306                return Some(chunk);
307            }
308
309            chunk = chunk.previous_mut()?;
310        }
311    }
312
313    /// Drop all the chunks, leaving the chunk in an uninitialized state,
314    /// because `Self::first` is a dangling pointer.
315    ///
316    /// SAFETY: the caller is responsible of ensuring that this is the last use
317    /// of the linked chunk, or that first will be re-initialized before any
318    /// other use.
319    unsafe fn clear(&mut self) {
320        // Loop over all chunks, from the last to the first chunk, and drop them.
321        // Take the latest chunk.
322        let mut current_chunk_ptr = self.last.or(Some(self.first));
323
324        // As long as we have another chunk…
325        while let Some(chunk_ptr) = current_chunk_ptr {
326            // Fetch the previous chunk pointer.
327            let previous_ptr = unsafe { chunk_ptr.as_ref() }.previous;
328
329            // Re-box the chunk, and let Rust do its job.
330            let _chunk_boxed = unsafe { Box::from_raw(chunk_ptr.as_ptr()) };
331
332            // Update the `current_chunk_ptr`.
333            current_chunk_ptr = previous_ptr;
334        }
335
336        // At this step, all chunks have been dropped, including `self.first`.
337        self.first = NonNull::dangling();
338        self.last = None;
339    }
340
341    /// Drop all chunks, and replace the first one with the one provided as an
342    /// argument.
343    fn replace_with(&mut self, first_chunk: NonNull<Chunk<CAP, Item, Gap>>) {
344        // SAFETY: we're resetting `self.first` afterwards.
345        unsafe {
346            self.clear();
347        }
348
349        // At this step, all chunks have been dropped, including `self.first`.
350        self.first = first_chunk;
351    }
352
353    /// Drop all chunks, and re-create the default first one.
354    ///
355    /// The default first chunk is an empty items chunk, with the identifier
356    /// [`ChunkIdentifierGenerator::FIRST_IDENTIFIER`].
357    fn reset(&mut self) {
358        self.replace_with(Chunk::new_items_leaked(ChunkIdentifierGenerator::FIRST_IDENTIFIER));
359    }
360}
361
362/// The [`LinkedChunk`] structure.
363///
364/// It is similar to a linked list, except that it contains many items `Item`
365/// instead of a single one. A chunk has a maximum capacity of `CHUNK_CAPACITY`.
366/// Once a chunk is full, a new chunk is created. Not all chunks are necessarily
367/// entirely full. A chunk can represents a `Gap` between other chunks.
368pub struct LinkedChunk<const CHUNK_CAPACITY: usize, Item, Gap> {
369    /// The links to the chunks, i.e. the first and the last chunk.
370    links: Ends<CHUNK_CAPACITY, Item, Gap>,
371
372    /// The generator of chunk identifiers.
373    chunk_identifier_generator: ChunkIdentifierGenerator,
374
375    /// All updates that have been made on this `LinkedChunk`. If this field is
376    /// `Some(…)`, update history is enabled, otherwise, if it's `None`, update
377    /// history is disabled.
378    updates: Option<ObservableUpdates<Item, Gap>>,
379
380    /// Marker.
381    marker: PhantomData<Box<Chunk<CHUNK_CAPACITY, Item, Gap>>>,
382}
383
384impl<const CAP: usize, Item, Gap> Default for LinkedChunk<CAP, Item, Gap> {
385    fn default() -> Self {
386        Self::new()
387    }
388}
389
390impl<const CAP: usize, Item, Gap> LinkedChunk<CAP, Item, Gap> {
391    /// Create a new [`Self`].
392    pub fn new() -> Self {
393        Self {
394            links: Ends {
395                first: Chunk::new_items_leaked(ChunkIdentifierGenerator::FIRST_IDENTIFIER),
396                last: None,
397            },
398            chunk_identifier_generator: ChunkIdentifierGenerator::new_from_scratch(),
399            updates: None,
400            marker: PhantomData,
401        }
402    }
403
404    /// Create a new [`Self`] with a history of updates.
405    ///
406    /// When [`Self`] is built with update history, the
407    /// [`ObservableUpdates::take`] method must be called to consume and
408    /// clean the updates. See [`Self::updates`].
409    pub fn new_with_update_history() -> Self {
410        let first_chunk_identifier = ChunkIdentifierGenerator::FIRST_IDENTIFIER;
411
412        let mut updates = ObservableUpdates::new();
413        updates.push(Update::NewItemsChunk {
414            previous: None,
415            new: first_chunk_identifier,
416            next: None,
417        });
418
419        Self {
420            links: Ends { first: Chunk::new_items_leaked(first_chunk_identifier), last: None },
421            chunk_identifier_generator: ChunkIdentifierGenerator::new_from_scratch(),
422            updates: Some(updates),
423            marker: PhantomData,
424        }
425    }
426
427    /// Clear all the chunks.
428    pub fn clear(&mut self) {
429        // Clear `self.links`.
430        self.links.reset();
431
432        // Clear `self.chunk_identifier_generator`.
433        self.chunk_identifier_generator = ChunkIdentifierGenerator::new_from_scratch();
434
435        // “Clear” `self.updates`.
436        if let Some(updates) = self.updates.as_mut() {
437            // Clear the previous updates, as we're about to insert a clear they would be
438            // useless.
439            updates.clear_pending();
440            updates.push(Update::Clear);
441            updates.push(Update::NewItemsChunk {
442                previous: None,
443                new: ChunkIdentifierGenerator::FIRST_IDENTIFIER,
444                next: None,
445            })
446        }
447    }
448
449    /// Push items at the end of the [`LinkedChunk`], i.e. on the last
450    /// chunk.
451    ///
452    /// If the last chunk doesn't have enough space to welcome all `items`,
453    /// then new chunks can be created (and linked appropriately).
454    pub fn push_items_back<I>(&mut self, items: I)
455    where
456        Item: Clone,
457        Gap: Clone,
458        I: IntoIterator<Item = Item>,
459        I::IntoIter: ExactSizeIterator,
460    {
461        let items = items.into_iter();
462
463        let last_chunk = self.links.latest_chunk_mut();
464
465        // Push the items.
466        let last_chunk =
467            last_chunk.push_items(items, &self.chunk_identifier_generator, &mut self.updates);
468
469        debug_assert!(last_chunk.is_last_chunk(), "`last_chunk` must be… the last chunk");
470
471        // We need to update `self.links.last` if and only if `last_chunk` _is not_ the
472        // first chunk, and _is_ the last chunk (ensured by the `debug_assert!`
473        // above).
474        if !last_chunk.is_first_chunk() {
475            // Maybe `last_chunk` is the same as the previous `self.links.last` chunk, but
476            // it's OK.
477            self.links.last = Some(last_chunk.as_ptr());
478        }
479    }
480
481    /// Push a gap at the end of the [`LinkedChunk`], i.e. after the last
482    /// chunk.
483    pub fn push_gap_back(&mut self, content: Gap)
484    where
485        Item: Clone,
486        Gap: Clone,
487    {
488        let last_chunk = self.links.latest_chunk_mut();
489        last_chunk.insert_next(
490            Chunk::new_gap_leaked(self.chunk_identifier_generator.next(), content),
491            &mut self.updates,
492        );
493
494        self.links.last = last_chunk.next;
495    }
496
497    /// Insert items at a specified position in the [`LinkedChunk`].
498    ///
499    /// Because the `position` can be invalid, this method returns a
500    /// `Result`.
501    pub fn insert_items_at<I>(&mut self, position: Position, items: I) -> Result<(), Error>
502    where
503        Item: Clone,
504        Gap: Clone,
505        I: IntoIterator<Item = Item>,
506        I::IntoIter: ExactSizeIterator,
507    {
508        let chunk_identifier = position.chunk_identifier();
509        let item_index = position.index();
510
511        let chunk = self
512            .links
513            .chunk_mut(chunk_identifier)
514            .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
515
516        let chunk = match &mut chunk.content {
517            ChunkContent::Gap(..) => {
518                return Err(Error::ChunkIsAGap { identifier: chunk_identifier });
519            }
520
521            ChunkContent::Items(current_items) => {
522                let current_items_length = current_items.len();
523
524                if item_index > current_items_length {
525                    return Err(Error::InvalidItemIndex { index: item_index });
526                }
527
528                // Prepare the items to be pushed.
529                let items = items.into_iter();
530
531                // Push at the end of the current items.
532                if item_index == current_items_length {
533                    chunk
534                        // Push the new items.
535                        .push_items(items, &self.chunk_identifier_generator, &mut self.updates)
536                }
537                // Insert inside the current items.
538                else {
539                    if let Some(updates) = self.updates.as_mut() {
540                        updates.push(Update::DetachLastItems {
541                            at: Position(chunk_identifier, item_index),
542                        });
543                    }
544
545                    // Split the items.
546                    let detached_items = current_items.split_off(item_index);
547
548                    let chunk = chunk
549                        // Push the new items.
550                        .push_items(items, &self.chunk_identifier_generator, &mut self.updates);
551
552                    if let Some(updates) = self.updates.as_mut() {
553                        updates.push(Update::StartReattachItems);
554                    }
555
556                    let chunk = chunk
557                        // Finally, push the items that have been detached.
558                        .push_items(
559                            detached_items.into_iter(),
560                            &self.chunk_identifier_generator,
561                            &mut self.updates,
562                        );
563
564                    if let Some(updates) = self.updates.as_mut() {
565                        updates.push(Update::EndReattachItems);
566                    }
567
568                    chunk
569                }
570            }
571        };
572
573        // We need to update `self.links.last` if and only if `chunk` _is not_ the first
574        // chunk, and _is_ the last chunk.
575        if !chunk.is_first_chunk() && chunk.is_last_chunk() {
576            // Maybe `chunk` is the same as the previous `self.links.last` chunk, but it's
577            // OK.
578            self.links.last = Some(chunk.as_ptr());
579        }
580
581        Ok(())
582    }
583
584    /// Remove item at a specified position in the [`LinkedChunk`].
585    ///
586    /// `position` must point to a valid item, otherwise the method returns
587    /// `Err`.
588    ///
589    /// The chunk containing the item represented by `position` may be empty
590    /// once the item has been removed. In this case, the chunk will be removed.
591    pub fn remove_item_at(&mut self, position: Position) -> Result<Item, Error> {
592        let chunk_identifier = position.chunk_identifier();
593        let item_index = position.index();
594
595        let mut chunk_ptr = None;
596        let removed_item;
597
598        {
599            let chunk = self
600                .links
601                .chunk_mut(chunk_identifier)
602                .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
603
604            let current_items = match &mut chunk.content {
605                ChunkContent::Gap(..) => {
606                    return Err(Error::ChunkIsAGap { identifier: chunk_identifier });
607                }
608                ChunkContent::Items(current_items) => current_items,
609            };
610
611            if item_index > current_items.len() {
612                return Err(Error::InvalidItemIndex { index: item_index });
613            }
614
615            removed_item = current_items.remove(item_index);
616            if let Some(updates) = self.updates.as_mut() {
617                updates.push(Update::RemoveItem { at: Position(chunk_identifier, item_index) })
618            }
619
620            // If the chunk is empty and not the first one, we can remove it.
621            if current_items.is_empty() && !chunk.is_first_chunk() {
622                // Unlink `chunk`.
623                chunk.unlink(self.updates.as_mut());
624
625                chunk_ptr = Some(chunk.as_ptr());
626
627                // We need to update `self.links.last` if and only if `chunk` _is_ the last
628                // chunk. The new last chunk is the chunk before `chunk`.
629                if chunk.is_last_chunk() {
630                    self.links.last = chunk.previous;
631                }
632            }
633
634            // Stop borrowing `chunk`.
635        }
636
637        if let Some(chunk_ptr) = chunk_ptr {
638            // `chunk` has been unlinked.
639
640            // Re-box the chunk, and let Rust do its job.
641            //
642            // SAFETY: `chunk` is unlinked and not borrowed anymore. `LinkedChunk` doesn't
643            // use it anymore, it's a leak. It is time to re-`Box` it and drop it.
644            let _chunk_boxed = unsafe { Box::from_raw(chunk_ptr.as_ptr()) };
645        }
646
647        Ok(removed_item)
648    }
649
650    /// Replace item at a specified position in the [`LinkedChunk`].
651    ///
652    /// `position` must point to a valid item, otherwise the method returns
653    /// `Err`.
654    pub fn replace_item_at(&mut self, position: Position, item: Item) -> Result<(), Error>
655    where
656        Item: Clone,
657    {
658        let chunk_identifier = position.chunk_identifier();
659        let item_index = position.index();
660
661        let chunk = self
662            .links
663            .chunk_mut(chunk_identifier)
664            .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
665
666        match &mut chunk.content {
667            ChunkContent::Gap(..) => {
668                return Err(Error::ChunkIsAGap { identifier: chunk_identifier });
669            }
670
671            ChunkContent::Items(current_items) => {
672                if item_index >= current_items.len() {
673                    return Err(Error::InvalidItemIndex { index: item_index });
674                }
675
676                // Avoid one spurious clone by notifying about the update *before* applying it.
677                if let Some(updates) = self.updates.as_mut() {
678                    updates.push(Update::ReplaceItem {
679                        at: Position(chunk_identifier, item_index),
680                        item: item.clone(),
681                    });
682                }
683
684                current_items[item_index] = item;
685            }
686        }
687
688        Ok(())
689    }
690
691    /// Insert a gap at a specified position in the [`LinkedChunk`].
692    ///
693    /// Because the `position` can be invalid, this method returns a
694    /// `Result`.
695    pub fn insert_gap_at(&mut self, content: Gap, position: Position) -> Result<(), Error>
696    where
697        Item: Clone,
698        Gap: Clone,
699    {
700        let chunk_identifier = position.chunk_identifier();
701        let item_index = position.index();
702
703        let chunk = self
704            .links
705            .chunk_mut(chunk_identifier)
706            .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
707
708        let chunk = match &mut chunk.content {
709            ChunkContent::Gap(..) => {
710                return Err(Error::ChunkIsAGap { identifier: chunk_identifier });
711            }
712
713            ChunkContent::Items(current_items) => {
714                // If `item_index` is 0, we don't want to split the current items chunk to
715                // insert a new gap chunk, otherwise it would create an empty current items
716                // chunk. Let's handle this case in particular.
717                if item_index == 0 {
718                    let chunk_was_first = chunk.is_first_chunk();
719                    let chunk_was_last = chunk.is_last_chunk();
720
721                    let new_chunk = chunk.insert_before(
722                        Chunk::new_gap_leaked(self.chunk_identifier_generator.next(), content),
723                        self.updates.as_mut(),
724                    );
725
726                    let new_chunk_ptr = new_chunk.as_ptr();
727                    let chunk_ptr = chunk.as_ptr();
728
729                    // `chunk` was the first: let's update `self.links.first`.
730                    //
731                    // If `chunk` was not the first but was the last, there is nothing to do,
732                    // `self.links.last` is already up-to-date.
733                    if chunk_was_first {
734                        self.links.first = new_chunk_ptr;
735
736                        // `chunk` was the first __and__ the last: let's set `self.links.last`.
737                        if chunk_was_last {
738                            self.links.last = Some(chunk_ptr);
739                        }
740                    }
741
742                    return Ok(());
743                }
744
745                let current_items_length = current_items.len();
746
747                if item_index >= current_items_length {
748                    return Err(Error::InvalidItemIndex { index: item_index });
749                }
750
751                if let Some(updates) = self.updates.as_mut() {
752                    updates.push(Update::DetachLastItems {
753                        at: Position(chunk_identifier, item_index),
754                    });
755                }
756
757                // Split the items.
758                let detached_items = current_items.split_off(item_index);
759
760                let chunk = chunk
761                    // Insert a new gap chunk.
762                    .insert_next(
763                        Chunk::new_gap_leaked(self.chunk_identifier_generator.next(), content),
764                        &mut self.updates,
765                    );
766
767                if let Some(updates) = self.updates.as_mut() {
768                    updates.push(Update::StartReattachItems);
769                }
770
771                let chunk = chunk
772                    // Insert a new items chunk.
773                    .insert_next(
774                        Chunk::new_items_leaked(self.chunk_identifier_generator.next()),
775                        &mut self.updates,
776                    )
777                    // Finally, push the items that have been detached.
778                    .push_items(
779                        detached_items.into_iter(),
780                        &self.chunk_identifier_generator,
781                        &mut self.updates,
782                    );
783
784                if let Some(updates) = self.updates.as_mut() {
785                    updates.push(Update::EndReattachItems);
786                }
787
788                chunk
789            }
790        };
791
792        // We need to update `self.links.last` if and only if `chunk` _is not_ the first
793        // chunk, and _is_ the last chunk.
794        if !chunk.is_first_chunk() && chunk.is_last_chunk() {
795            // Maybe `chunk` is the same as the previous `self.links.last` chunk, but it's
796            // OK.
797            self.links.last = Some(chunk.as_ptr());
798        }
799
800        Ok(())
801    }
802
803    /// Remove a chunk with the given identifier iff it's empty.
804    ///
805    /// A chunk is considered empty if:
806    /// - it's a gap chunk, or
807    /// - it's an items chunk with no items.
808    ///
809    /// This returns the next insert position, viz. the start of the next
810    /// chunk, if any, or none if there was no next chunk.
811    pub fn remove_empty_chunk_at(
812        &mut self,
813        chunk_identifier: ChunkIdentifier,
814    ) -> Result<Option<Position>, Error> {
815        // Check that we're not removing the last chunk.
816        if self.links.first_chunk().is_last_chunk() {
817            return Err(Error::RemovingLastChunk);
818        }
819
820        let chunk = self
821            .links
822            .chunk_mut(chunk_identifier)
823            .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
824
825        if chunk.num_items() > 0 {
826            return Err(Error::RemovingNonEmptyItemsChunk { identifier: chunk_identifier });
827        }
828
829        let chunk_was_first = chunk.is_first_chunk();
830        let chunk_was_last = chunk.is_last_chunk();
831        let next_ptr = chunk.next;
832        let previous_ptr = chunk.previous;
833        let position_of_next = chunk.next().map(|next| next.first_position());
834
835        chunk.unlink(self.updates.as_mut());
836
837        let chunk_ptr = chunk.as_ptr();
838
839        // If the chunk is the first one, we need to update `self.links.first`…
840        if chunk_was_first {
841            // … if and only if there is a next chunk.
842            if let Some(next_ptr) = next_ptr {
843                self.links.first = next_ptr;
844            }
845        }
846
847        if chunk_was_last {
848            self.links.last = previous_ptr;
849        }
850
851        // SAFETY: `chunk` is unlinked and not borrowed anymore. `LinkedChunk` doesn't
852        // use it anymore, it's a leak. It is time to re-`Box` it and drop it.
853        let _chunk_boxed = unsafe { Box::from_raw(chunk_ptr.as_ptr()) };
854
855        // Return the first position of the next chunk, if any.
856        Ok(position_of_next)
857    }
858
859    /// Replace the gap identified by `chunk_identifier`, by items.
860    ///
861    /// Because the `chunk_identifier` can represent non-gap chunk, this method
862    /// returns a `Result`.
863    ///
864    /// This method returns a reference to the (first if many) newly created
865    /// `Chunk` that contains the `items`.
866    pub fn replace_gap_at<I>(
867        &mut self,
868        items: I,
869        chunk_identifier: ChunkIdentifier,
870    ) -> Result<&Chunk<CAP, Item, Gap>, Error>
871    where
872        Item: Clone,
873        Gap: Clone,
874        I: IntoIterator<Item = Item>,
875        I::IntoIter: ExactSizeIterator,
876    {
877        let chunk_ptr;
878        let new_chunk_ptr;
879
880        {
881            let chunk = self
882                .links
883                .chunk_mut(chunk_identifier)
884                .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
885
886            if chunk.is_items() {
887                return Err(Error::ChunkIsItems { identifier: chunk_identifier });
888            }
889
890            let chunk_was_first = chunk.is_first_chunk();
891
892            let maybe_last_chunk_ptr = {
893                let items = items.into_iter();
894
895                let last_inserted_chunk = chunk
896                    // Insert a new items chunk…
897                    .insert_next(
898                        Chunk::new_items_leaked(self.chunk_identifier_generator.next()),
899                        &mut self.updates,
900                    )
901                    // … and insert the items.
902                    .push_items(items, &self.chunk_identifier_generator, &mut self.updates);
903
904                last_inserted_chunk.is_last_chunk().then(|| last_inserted_chunk.as_ptr())
905            };
906
907            new_chunk_ptr = chunk
908                .next
909                // SAFETY: A new `Chunk` has just been inserted, so it exists.
910                .unwrap();
911
912            // Now that new items have been pushed, we can unlink the gap chunk.
913            chunk.unlink(self.updates.as_mut());
914
915            // Get the pointer to `chunk`.
916            chunk_ptr = chunk.as_ptr();
917
918            // Update `self.links.first` if the gap chunk was the first chunk.
919            if chunk_was_first {
920                self.links.first = new_chunk_ptr;
921            }
922
923            // Update `self.links.last` if the gap (so the new) chunk was (is) the last
924            // chunk.
925            if let Some(last_chunk_ptr) = maybe_last_chunk_ptr {
926                self.links.last = Some(last_chunk_ptr);
927            }
928
929            // Stop borrowing `chunk`.
930        }
931
932        // Re-box the chunk, and let Rust do its job.
933        //
934        // SAFETY: `chunk` is unlinked and not borrowed anymore. `LinkedChunk` doesn't
935        // use it anymore, it's a leak. It is time to re-`Box` it and drop it.
936        let _chunk_boxed = unsafe { Box::from_raw(chunk_ptr.as_ptr()) };
937
938        Ok(
939            // SAFETY: `new_chunk_ptr` is valid, non-null and well-aligned. It's taken from
940            // `chunk`, and that's how the entire `LinkedChunk` type works. Pointer construction
941            // safety is guaranteed by `Chunk::new_items_leaked` and `Chunk::new_gap_leaked`.
942            unsafe { new_chunk_ptr.as_ref() },
943        )
944    }
945
946    /// Search backwards for a chunk, and return its identifier.
947    pub fn chunk_identifier<'a, P>(&'a self, mut predicate: P) -> Option<ChunkIdentifier>
948    where
949        P: FnMut(&'a Chunk<CAP, Item, Gap>) -> bool,
950    {
951        self.rchunks().find_map(|chunk| predicate(chunk).then(|| chunk.identifier()))
952    }
953
954    /// Search backwards for an item, and return its position.
955    pub fn item_position<'a, P>(&'a self, mut predicate: P) -> Option<Position>
956    where
957        P: FnMut(&'a Item) -> bool,
958    {
959        self.ritems().find_map(|(item_position, item)| predicate(item).then_some(item_position))
960    }
961
962    /// Iterate over the chunks, backwards.
963    ///
964    /// It iterates from the last to the first chunk.
965    pub fn rchunks(&self) -> IterBackward<'_, CAP, Item, Gap> {
966        IterBackward::new(self.links.latest_chunk())
967    }
968
969    /// Iterate over the chunks, forward.
970    ///
971    /// It iterates from the first to the last chunk.
972    pub fn chunks(&self) -> Iter<'_, CAP, Item, Gap> {
973        Iter::new(self.links.first_chunk())
974    }
975
976    /// Iterate over the chunks, starting from `identifier`, backward.
977    ///
978    /// It iterates from the chunk with the identifier `identifier` to the first
979    /// chunk.
980    pub fn rchunks_from(
981        &self,
982        identifier: ChunkIdentifier,
983    ) -> Result<IterBackward<'_, CAP, Item, Gap>, Error> {
984        Ok(IterBackward::new(
985            self.links.chunk(identifier).ok_or(Error::InvalidChunkIdentifier { identifier })?,
986        ))
987    }
988
989    /// Iterate over the chunks, starting from `position`, forward.
990    ///
991    /// It iterates from the chunk with the identifier `identifier` to the last
992    /// chunk.
993    pub fn chunks_from(
994        &self,
995        identifier: ChunkIdentifier,
996    ) -> Result<Iter<'_, CAP, Item, Gap>, Error> {
997        Ok(Iter::new(
998            self.links.chunk(identifier).ok_or(Error::InvalidChunkIdentifier { identifier })?,
999        ))
1000    }
1001
1002    /// Iterate over the items, backward.
1003    ///
1004    /// It iterates from the last to the first item.
1005    pub fn ritems(&self) -> impl Iterator<Item = (Position, &Item)> {
1006        self.ritems_from(self.links.latest_chunk().last_position())
1007            .expect("`ritems_from` cannot fail because at least one empty chunk must exist")
1008    }
1009
1010    /// Iterate over the items, forward.
1011    ///
1012    /// It iterates from the first to the last item.
1013    pub fn items(&self) -> impl Iterator<Item = (Position, &Item)> {
1014        let first_chunk = self.links.first_chunk();
1015
1016        self.items_from(first_chunk.first_position())
1017            .expect("`items` cannot fail because at least one empty chunk must exist")
1018    }
1019
1020    /// Iterate over the items, starting from `position`, backward.
1021    ///
1022    /// It iterates from the item at `position` to the first item.
1023    pub fn ritems_from(
1024        &self,
1025        position: Position,
1026    ) -> Result<impl Iterator<Item = (Position, &Item)>, Error> {
1027        Ok(self
1028            .rchunks_from(position.chunk_identifier())?
1029            .filter_map(|chunk| match &chunk.content {
1030                ChunkContent::Gap(..) => None,
1031                ChunkContent::Items(items) => {
1032                    let identifier = chunk.identifier();
1033
1034                    Some(
1035                        items.iter().enumerate().rev().map(move |(item_index, item)| {
1036                            (Position(identifier, item_index), item)
1037                        }),
1038                    )
1039                }
1040            })
1041            .flatten()
1042            .skip_while({
1043                let expected_index = position.index();
1044
1045                move |(Position(chunk_identifier, item_index), _item)| {
1046                    *chunk_identifier == position.chunk_identifier()
1047                        && *item_index != expected_index
1048                }
1049            }))
1050    }
1051
1052    /// Iterate over the items, starting from `position`, forward.
1053    ///
1054    /// It iterates from the item at `position` to the last item.
1055    pub fn items_from(
1056        &self,
1057        position: Position,
1058    ) -> Result<impl Iterator<Item = (Position, &Item)>, Error> {
1059        Ok(self
1060            .chunks_from(position.chunk_identifier())?
1061            .filter_map(|chunk| match &chunk.content {
1062                ChunkContent::Gap(..) => None,
1063                ChunkContent::Items(items) => {
1064                    let identifier = chunk.identifier();
1065
1066                    Some(
1067                        items.iter().enumerate().map(move |(item_index, item)| {
1068                            (Position(identifier, item_index), item)
1069                        }),
1070                    )
1071                }
1072            })
1073            .flatten()
1074            .skip(position.index()))
1075    }
1076
1077    /// Get a mutable reference to the `LinkedChunk` updates, aka
1078    /// [`ObservableUpdates`].
1079    ///
1080    /// If the `Option` becomes `None`, it will disable update history. Thus, be
1081    /// careful when you want to empty the update history: do not use
1082    /// `Option::take()` directly but rather [`ObservableUpdates::take`] for
1083    /// example.
1084    ///
1085    /// It returns `None` if updates are disabled, i.e. if this linked chunk has
1086    /// been constructed with [`Self::new`], otherwise, if it's been constructed
1087    /// with [`Self::new_with_update_history`], it returns `Some(…)`.
1088    #[must_use]
1089    pub fn updates(&mut self) -> Option<&mut ObservableUpdates<Item, Gap>> {
1090        self.updates.as_mut()
1091    }
1092
1093    /// Get updates as [`eyeball_im::VectorDiff`], see [`AsVector`] to learn
1094    /// more.
1095    ///
1096    /// It returns `None` if updates are disabled, i.e. if this linked chunk has
1097    /// been constructed with [`Self::new`], otherwise, if it's been constructed
1098    /// with [`Self::new_with_update_history`], it returns `Some(…)`.
1099    pub fn as_vector(&mut self) -> Option<AsVector<Item, Gap>> {
1100        let (updates, token) = self
1101            .updates
1102            .as_mut()
1103            .map(|updates| (updates.inner.clone(), updates.new_reader_token()))?;
1104        let chunk_iterator = self.chunks();
1105
1106        Some(AsVector::new(updates, token, chunk_iterator))
1107    }
1108
1109    /// Get an [`OrderTracker`] for the linked chunk, which can be used to
1110    /// compare the relative position of two events in this linked chunk.
1111    ///
1112    /// A pre-requisite is that the linked chunk has been constructed with
1113    /// [`Self::new_with_update_history`], and that if the linked chunk is
1114    /// lazily-loaded, an iterator over the fully-loaded linked chunk is
1115    /// passed at construction time here.
1116    pub fn order_tracker(
1117        &mut self,
1118        all_chunks: Option<Vec<ChunkMetadata>>,
1119    ) -> Option<OrderTracker<Item, Gap>>
1120    where
1121        Item: Clone,
1122    {
1123        let (updates, token) = self
1124            .updates
1125            .as_mut()
1126            .map(|updates| (updates.inner.clone(), updates.new_reader_token()))?;
1127
1128        Some(OrderTracker::new(
1129            updates,
1130            token,
1131            all_chunks.unwrap_or_else(|| {
1132                // Consider the linked chunk as fully loaded.
1133                self.chunks()
1134                    .map(|chunk| ChunkMetadata {
1135                        identifier: chunk.identifier(),
1136                        num_items: chunk.num_items(),
1137                        previous: chunk.previous().map(|prev| prev.identifier()),
1138                        next: chunk.next().map(|next| next.identifier()),
1139                    })
1140                    .collect()
1141            }),
1142        ))
1143    }
1144
1145    /// Returns the number of items of the linked chunk.
1146    pub fn num_items(&self) -> usize {
1147        self.items().count()
1148    }
1149}
1150
1151impl<const CAP: usize, Item, Gap> Drop for LinkedChunk<CAP, Item, Gap> {
1152    fn drop(&mut self) {
1153        // Clear the links, which will drop all the chunks.
1154        //
1155        // Calling `Self::clear` would be an error as we don't want to emit an
1156        // `Update::Clear` when `self` is dropped. Instead, we only care about
1157        // freeing memory correctly. Rust can take care of everything except the
1158        // pointers in `self.links`, hence the specific call to `self.links.clear()`.
1159        //
1160        // SAFETY: this is the last use of the linked chunk, so leaving it in a dangling
1161        // state is fine.
1162        unsafe {
1163            self.links.clear();
1164        }
1165    }
1166}
1167
1168/// A [`LinkedChunk`] can be safely sent over thread boundaries if `Item: Send`
1169/// and `Gap: Send`. The only unsafe part is around the `NonNull`, but the API
1170/// and the lifetimes to deref them are designed safely.
1171unsafe impl<const CAP: usize, Item: Send, Gap: Send> Send for LinkedChunk<CAP, Item, Gap> {}
1172
1173/// A [`LinkedChunk`] can be safely share between threads if `Item: Sync` and
1174/// `Gap: Sync`. The only unsafe part is around the `NonNull`, but the API and
1175/// the lifetimes to deref them are designed safely.
1176unsafe impl<const CAP: usize, Item: Sync, Gap: Sync> Sync for LinkedChunk<CAP, Item, Gap> {}
1177
1178/// Generator for [`Chunk`]'s identifier.
1179///
1180/// Each [`Chunk`] has a unique identifier. This generator generates the unique
1181/// identifiers.
1182///
1183/// In order to keep good performance, a unique identifier is simply a `u64`
1184/// (see [`ChunkIdentifier`]). Generating a new unique identifier boils down to
1185/// incrementing by one the previous identifier. Note that this is not an index:
1186/// it _is_ an identifier.
1187#[derive(Debug)]
1188pub struct ChunkIdentifierGenerator {
1189    next: AtomicU64,
1190}
1191
1192impl ChunkIdentifierGenerator {
1193    /// The first identifier.
1194    const FIRST_IDENTIFIER: ChunkIdentifier = ChunkIdentifier(0);
1195
1196    /// Create the generator assuming the current [`LinkedChunk`] it belongs to
1197    /// is empty.
1198    pub fn new_from_scratch() -> Self {
1199        Self { next: AtomicU64::new(Self::FIRST_IDENTIFIER.0) }
1200    }
1201
1202    /// Create the generator assuming the current [`LinkedChunk`] it belongs to
1203    /// is not empty, i.e. it already has some [`Chunk`] in it.
1204    pub fn new_from_previous_chunk_identifier(last_chunk_identifier: ChunkIdentifier) -> Self {
1205        Self { next: AtomicU64::new(last_chunk_identifier.0) }
1206    }
1207
1208    /// Generate the next unique identifier.
1209    ///
1210    /// Note that it can fail if there is no more unique identifier available.
1211    /// In this case, this method will panic.
1212    fn next(&self) -> ChunkIdentifier {
1213        let previous = self.next.fetch_add(1, atomic::Ordering::Relaxed);
1214
1215        // Check for overflows.
1216        // unlikely — TODO: call `std::intrinsics::unlikely` once it's stable.
1217        if previous == u64::MAX {
1218            panic!(
1219                "No more chunk identifiers available. Congrats, you did it. \
1220                 2^64 identifiers have been consumed."
1221            )
1222        }
1223
1224        ChunkIdentifier(previous + 1)
1225    }
1226
1227    /// Get the current chunk identifier.
1228    //
1229    // This is hidden because it's used only in the tests.
1230    #[doc(hidden)]
1231    pub fn current(&self) -> ChunkIdentifier {
1232        ChunkIdentifier(self.next.load(atomic::Ordering::Relaxed))
1233    }
1234}
1235
1236/// The unique identifier of a chunk in a [`LinkedChunk`].
1237///
1238/// It is not the position of the chunk, just its unique identifier.
1239///
1240/// Learn more with [`ChunkIdentifierGenerator`].
1241#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
1242#[repr(transparent)]
1243pub struct ChunkIdentifier(u64);
1244
1245impl ChunkIdentifier {
1246    /// Create a new [`ChunkIdentifier`].
1247    pub fn new(identifier: u64) -> Self {
1248        Self(identifier)
1249    }
1250
1251    /// Get the underlying identifier.
1252    pub fn index(&self) -> u64 {
1253        self.0
1254    }
1255}
1256
1257impl PartialEq<u64> for ChunkIdentifier {
1258    fn eq(&self, other: &u64) -> bool {
1259        self.0 == *other
1260    }
1261}
1262
1263/// The position of something inside a [`Chunk`].
1264///
1265/// It's a pair of a chunk position and an item index.
1266#[derive(Copy, Clone, Debug, PartialEq)]
1267pub struct Position(ChunkIdentifier, usize);
1268
1269impl Position {
1270    /// Create a new [`Position`].
1271    pub fn new(chunk_identifier: ChunkIdentifier, index: usize) -> Self {
1272        Self(chunk_identifier, index)
1273    }
1274
1275    /// Get the chunk identifier of the item.
1276    pub fn chunk_identifier(&self) -> ChunkIdentifier {
1277        self.0
1278    }
1279
1280    /// Get the index inside the chunk.
1281    pub fn index(&self) -> usize {
1282        self.1
1283    }
1284
1285    /// Decrement the index part (see [`Self::index`]), i.e. subtract 1.
1286    ///
1287    /// # Panic
1288    ///
1289    /// This method will panic if it will underflow, i.e. if the index is 0.
1290    pub fn decrement_index(&mut self) {
1291        self.1 = self.1.checked_sub(1).expect("Cannot decrement the index because it's already 0");
1292    }
1293
1294    /// Increment the index part (see [`Self::index`]), i.e. add 1.
1295    ///
1296    /// # Panic
1297    ///
1298    /// This method will panic if it will overflow, i.e. if the index is larger
1299    /// than `usize::MAX`.
1300    pub fn increment_index(&mut self) {
1301        self.1 = self.1.checked_add(1).expect("Cannot increment the index because it's too large");
1302    }
1303}
1304
1305/// An iterator over a [`LinkedChunk`] that traverses the chunk in backward
1306/// direction (i.e. it calls `previous` on each chunk to make progress).
1307#[derive(Debug)]
1308pub struct IterBackward<'a, const CAP: usize, Item, Gap> {
1309    chunk: Option<&'a Chunk<CAP, Item, Gap>>,
1310}
1311
1312impl<'a, const CAP: usize, Item, Gap> IterBackward<'a, CAP, Item, Gap> {
1313    /// Create a new [`LinkedChunkIter`] from a particular [`Chunk`].
1314    fn new(from_chunk: &'a Chunk<CAP, Item, Gap>) -> Self {
1315        Self { chunk: Some(from_chunk) }
1316    }
1317}
1318
1319impl<'a, const CAP: usize, Item, Gap> Iterator for IterBackward<'a, CAP, Item, Gap> {
1320    type Item = &'a Chunk<CAP, Item, Gap>;
1321
1322    fn next(&mut self) -> Option<Self::Item> {
1323        self.chunk.inspect(|chunk| self.chunk = chunk.previous())
1324    }
1325}
1326
1327/// An iterator over a [`LinkedChunk`] that traverses the chunk in forward
1328/// direction (i.e. it calls `next` on each chunk to make progress).
1329#[derive(Debug)]
1330pub struct Iter<'a, const CAP: usize, Item, Gap> {
1331    chunk: Option<&'a Chunk<CAP, Item, Gap>>,
1332}
1333
1334impl<'a, const CAP: usize, Item, Gap> Iter<'a, CAP, Item, Gap> {
1335    /// Create a new [`LinkedChunkIter`] from a particular [`Chunk`].
1336    fn new(from_chunk: &'a Chunk<CAP, Item, Gap>) -> Self {
1337        Self { chunk: Some(from_chunk) }
1338    }
1339}
1340
1341impl<'a, const CAP: usize, Item, Gap> Iterator for Iter<'a, CAP, Item, Gap> {
1342    type Item = &'a Chunk<CAP, Item, Gap>;
1343
1344    fn next(&mut self) -> Option<Self::Item> {
1345        self.chunk.inspect(|chunk| self.chunk = chunk.next())
1346    }
1347}
1348
1349/// This enum represents the content of a [`Chunk`].
1350#[derive(Clone, Debug)]
1351pub enum ChunkContent<Item, Gap> {
1352    /// The chunk represents a gap in the linked chunk, i.e. a hole. It
1353    /// means that some items are missing in this location.
1354    Gap(Gap),
1355
1356    /// The chunk contains items.
1357    Items(Vec<Item>),
1358}
1359
1360/// A chunk is a node in the [`LinkedChunk`].
1361pub struct Chunk<const CAPACITY: usize, Item, Gap> {
1362    /// The previous chunk.
1363    previous: Option<NonNull<Chunk<CAPACITY, Item, Gap>>>,
1364
1365    /// If this chunk is the first one, and if the `LinkedChunk` is loaded
1366    /// lazily, chunk-by-chunk, this is the identifier of the previous chunk.
1367    /// This previous chunk is not loaded yet, so it's impossible to get a
1368    /// pointer to it yet. However we know its identifier.
1369    lazy_previous: Option<ChunkIdentifier>,
1370
1371    /// The next chunk.
1372    next: Option<NonNull<Chunk<CAPACITY, Item, Gap>>>,
1373
1374    /// Unique identifier.
1375    identifier: ChunkIdentifier,
1376
1377    /// The content of the chunk.
1378    content: ChunkContent<Item, Gap>,
1379}
1380
1381impl<const CAPACITY: usize, Item, Gap> Chunk<CAPACITY, Item, Gap> {
1382    /// Create a new gap chunk.
1383    fn new_gap(identifier: ChunkIdentifier, content: Gap) -> Self {
1384        Self::new(identifier, ChunkContent::Gap(content))
1385    }
1386
1387    /// Create a new items chunk.
1388    fn new_items(identifier: ChunkIdentifier) -> Self {
1389        Self::new(identifier, ChunkContent::Items(Vec::with_capacity(CAPACITY)))
1390    }
1391
1392    fn new(identifier: ChunkIdentifier, content: ChunkContent<Item, Gap>) -> Self {
1393        Self { previous: None, lazy_previous: None, next: None, identifier, content }
1394    }
1395
1396    /// Create a new chunk given some content, but box it and leak it.
1397    fn new_leaked(identifier: ChunkIdentifier, content: ChunkContent<Item, Gap>) -> NonNull<Self> {
1398        let chunk = Self::new(identifier, content);
1399        let chunk_box = Box::new(chunk);
1400
1401        NonNull::from(Box::leak(chunk_box))
1402    }
1403
1404    /// Create a new gap chunk, but box it and leak it.
1405    fn new_gap_leaked(identifier: ChunkIdentifier, content: Gap) -> NonNull<Self> {
1406        let chunk = Self::new_gap(identifier, content);
1407        let chunk_box = Box::new(chunk);
1408
1409        NonNull::from(Box::leak(chunk_box))
1410    }
1411
1412    /// Create a new items chunk, but box it and leak it.
1413    fn new_items_leaked(identifier: ChunkIdentifier) -> NonNull<Self> {
1414        let chunk = Self::new_items(identifier);
1415        let chunk_box = Box::new(chunk);
1416
1417        NonNull::from(Box::leak(chunk_box))
1418    }
1419
1420    /// Get the pointer to `Self`.
1421    pub fn as_ptr(&self) -> NonNull<Self> {
1422        NonNull::from(self)
1423    }
1424
1425    /// Check whether this current chunk is a gap chunk.
1426    pub fn is_gap(&self) -> bool {
1427        matches!(self.content, ChunkContent::Gap(..))
1428    }
1429
1430    /// Check whether this current chunk is an items  chunk.
1431    pub fn is_items(&self) -> bool {
1432        !self.is_gap()
1433    }
1434
1435    /// Is this the definitive first chunk, even in the presence of
1436    /// lazy-loading?
1437    pub fn is_definitive_head(&self) -> bool {
1438        self.previous.is_none() && self.lazy_previous.is_none()
1439    }
1440
1441    /// Check whether this current chunk is the first chunk.
1442    fn is_first_chunk(&self) -> bool {
1443        self.previous.is_none()
1444    }
1445
1446    /// Check whether this current chunk is the last chunk.
1447    fn is_last_chunk(&self) -> bool {
1448        self.next.is_none()
1449    }
1450
1451    /// Return the link to the previous chunk, if it was loaded lazily.
1452    ///
1453    /// Doc hidden because this is mostly for internal debugging purposes.
1454    #[doc(hidden)]
1455    pub fn lazy_previous(&self) -> Option<ChunkIdentifier> {
1456        self.lazy_previous
1457    }
1458
1459    /// Get the unique identifier of the chunk.
1460    pub fn identifier(&self) -> ChunkIdentifier {
1461        self.identifier
1462    }
1463
1464    /// Get the content of the chunk.
1465    pub fn content(&self) -> &ChunkContent<Item, Gap> {
1466        &self.content
1467    }
1468
1469    /// Get the [`Position`] of the first item if any.
1470    ///
1471    /// If the `Chunk` is a `Gap`, it returns `0` for the index.
1472    pub fn first_position(&self) -> Position {
1473        Position(self.identifier(), 0)
1474    }
1475
1476    /// Get the [`Position`] of the last item if any.
1477    ///
1478    /// If the `Chunk` is a `Gap`, it returns `0` for the index.
1479    pub fn last_position(&self) -> Position {
1480        let identifier = self.identifier();
1481
1482        match &self.content {
1483            ChunkContent::Gap(..) => Position(identifier, 0),
1484            ChunkContent::Items(items) => Position(identifier, items.len().saturating_sub(1)),
1485        }
1486    }
1487
1488    /// The number of items in the linked chunk.
1489    ///
1490    /// It will always return 0 if it's a gap chunk.
1491    pub fn num_items(&self) -> usize {
1492        match &self.content {
1493            ChunkContent::Gap(..) => 0,
1494            ChunkContent::Items(items) => items.len(),
1495        }
1496    }
1497
1498    /// Push items on the current chunk.
1499    ///
1500    /// If the chunk doesn't have enough spaces to welcome `new_items`, new
1501    /// chunk will be inserted next, and correctly linked.
1502    ///
1503    /// This method returns the last inserted chunk if any, or the current
1504    /// chunk. Basically, it returns the chunk onto which new computations
1505    /// must happen.
1506    ///
1507    /// Pushing items will always create new chunks if necessary, but it
1508    /// will never merge them, so that we avoid updating too much chunks.
1509    fn push_items<I>(
1510        &mut self,
1511        mut new_items: I,
1512        chunk_identifier_generator: &ChunkIdentifierGenerator,
1513        updates: &mut Option<ObservableUpdates<Item, Gap>>,
1514    ) -> &mut Self
1515    where
1516        I: Iterator<Item = Item> + ExactSizeIterator,
1517        Item: Clone,
1518        Gap: Clone,
1519    {
1520        // A small optimisation. Skip early if there is no new items.
1521        if new_items.len() == 0 {
1522            return self;
1523        }
1524
1525        let identifier = self.identifier();
1526        let prev_num_items = self.num_items();
1527
1528        match &mut self.content {
1529            // Cannot push items on a `Gap`. Let's insert a new `Items` chunk to push the
1530            // items onto it.
1531            ChunkContent::Gap(..) => {
1532                self
1533                    // Insert a new items chunk.
1534                    .insert_next(Self::new_items_leaked(chunk_identifier_generator.next()), updates)
1535                    // Now push the new items on the next chunk, and return the result of
1536                    // `push_items`.
1537                    .push_items(new_items, chunk_identifier_generator, updates)
1538            }
1539
1540            ChunkContent::Items(items) => {
1541                // Calculate the free space of the current chunk.
1542                let free_space = CAPACITY.saturating_sub(prev_num_items);
1543
1544                // There is enough space to push all the new items.
1545                if new_items.len() <= free_space {
1546                    let start = items.len();
1547                    items.extend(new_items);
1548
1549                    if let Some(updates) = updates.as_mut() {
1550                        updates.push(Update::PushItems {
1551                            at: Position(identifier, start),
1552                            items: items[start..].to_vec(),
1553                        });
1554                    }
1555
1556                    // Return the current chunk.
1557                    self
1558                } else {
1559                    if free_space > 0 {
1560                        // Take all possible items to fill the free space.
1561                        let start = items.len();
1562                        items.extend(new_items.by_ref().take(free_space));
1563
1564                        if let Some(updates) = updates.as_mut() {
1565                            updates.push(Update::PushItems {
1566                                at: Position(identifier, start),
1567                                items: items[start..].to_vec(),
1568                            });
1569                        }
1570                    }
1571
1572                    self
1573                        // Insert a new items chunk.
1574                        .insert_next(
1575                            Self::new_items_leaked(chunk_identifier_generator.next()),
1576                            updates,
1577                        )
1578                        // Now push the rest of the new items on the next chunk, and return the
1579                        // result of `push_items`.
1580                        .push_items(new_items, chunk_identifier_generator, updates)
1581                }
1582            }
1583        }
1584    }
1585
1586    /// Insert a new chunk after the current one.
1587    ///
1588    /// The respective [`Self::previous`] and [`Self::next`] of the current
1589    /// and new chunk will be updated accordingly.
1590    fn insert_next(
1591        &mut self,
1592        mut new_chunk_ptr: NonNull<Self>,
1593        updates: &mut Option<ObservableUpdates<Item, Gap>>,
1594    ) -> &mut Self
1595    where
1596        Gap: Clone,
1597    {
1598        let new_chunk = unsafe { new_chunk_ptr.as_mut() };
1599
1600        // Update the next chunk if any.
1601        if let Some(next_chunk) = self.next_mut() {
1602            // Link back to the new chunk.
1603            next_chunk.previous = Some(new_chunk_ptr);
1604
1605            // Link the new chunk to the next chunk.
1606            new_chunk.next = self.next;
1607        }
1608
1609        // Link to the new chunk.
1610        self.next = Some(new_chunk_ptr);
1611        // Link the new chunk to this one.
1612        new_chunk.previous = Some(self.as_ptr());
1613
1614        if let Some(updates) = updates.as_mut() {
1615            let previous = new_chunk.previous().map(Chunk::identifier);
1616            let new = new_chunk.identifier();
1617            let next = new_chunk.next().map(Chunk::identifier);
1618
1619            match new_chunk.content() {
1620                ChunkContent::Gap(gap) => {
1621                    updates.push(Update::NewGapChunk { previous, new, next, gap: gap.clone() })
1622                }
1623
1624                ChunkContent::Items(..) => {
1625                    updates.push(Update::NewItemsChunk { previous, new, next })
1626                }
1627            }
1628        }
1629
1630        new_chunk
1631    }
1632
1633    /// Insert a new chunk before the current one.
1634    ///
1635    /// The respective [`Self::previous`] and [`Self::next`] of the current
1636    /// and new chunk will be updated accordingly.
1637    fn insert_before(
1638        &mut self,
1639        mut new_chunk_ptr: NonNull<Self>,
1640        updates: Option<&mut ObservableUpdates<Item, Gap>>,
1641    ) -> &mut Self
1642    where
1643        Gap: Clone,
1644    {
1645        let new_chunk = unsafe { new_chunk_ptr.as_mut() };
1646
1647        // Update the previous chunk if any.
1648        if let Some(previous_chunk) = self.previous_mut() {
1649            // Link back to the new chunk.
1650            previous_chunk.next = Some(new_chunk_ptr);
1651
1652            // Link the new chunk to the next chunk.
1653            new_chunk.previous = self.previous;
1654        }
1655        // No previous: `self` is the first! We need to move the `lazy_previous` from `self` to
1656        // `new_chunk`.
1657        else {
1658            new_chunk.lazy_previous = self.lazy_previous.take();
1659        }
1660
1661        // Link to the new chunk.
1662        self.previous = Some(new_chunk_ptr);
1663        // Link the new chunk to this one.
1664        new_chunk.next = Some(self.as_ptr());
1665
1666        if let Some(updates) = updates {
1667            let previous = new_chunk.previous().map(Chunk::identifier).or(new_chunk.lazy_previous);
1668            let new = new_chunk.identifier();
1669            let next = new_chunk.next().map(Chunk::identifier);
1670
1671            match new_chunk.content() {
1672                ChunkContent::Gap(gap) => {
1673                    updates.push(Update::NewGapChunk { previous, new, next, gap: gap.clone() })
1674                }
1675
1676                ChunkContent::Items(..) => {
1677                    updates.push(Update::NewItemsChunk { previous, new, next })
1678                }
1679            }
1680        }
1681
1682        new_chunk
1683    }
1684
1685    /// Unlink this chunk.
1686    ///
1687    /// Be careful: `self` won't belong to `LinkedChunk` anymore, and should be
1688    /// dropped appropriately.
1689    fn unlink(&mut self, updates: Option<&mut ObservableUpdates<Item, Gap>>) {
1690        let previous_ptr = self.previous;
1691        let next_ptr = self.next;
1692        // If `self` is not the first, `lazy_previous` might be set on its previous
1693        // chunk. Otherwise, if `lazy_previous` is set on `self`, it means it's the
1694        // first chunk and it must be moved onto the next chunk.
1695        let lazy_previous = self.lazy_previous.take();
1696
1697        if let Some(previous) = self.previous_mut() {
1698            previous.next = next_ptr;
1699        }
1700
1701        if let Some(next) = self.next_mut() {
1702            next.previous = previous_ptr;
1703            next.lazy_previous = lazy_previous;
1704        }
1705
1706        if let Some(updates) = updates {
1707            updates.push(Update::RemoveChunk(self.identifier()));
1708        }
1709    }
1710
1711    /// Get a reference to the previous chunk if any.
1712    fn previous(&self) -> Option<&Self> {
1713        self.previous.map(|non_null| unsafe { non_null.as_ref() })
1714    }
1715
1716    /// Get a mutable to the previous chunk if any.
1717    fn previous_mut(&mut self) -> Option<&mut Self> {
1718        self.previous.as_mut().map(|non_null| unsafe { non_null.as_mut() })
1719    }
1720
1721    /// Get a reference to the next chunk if any.
1722    fn next(&self) -> Option<&Self> {
1723        self.next.map(|non_null| unsafe { non_null.as_ref() })
1724    }
1725
1726    /// Get a mutable reference to the next chunk if any.
1727    fn next_mut(&mut self) -> Option<&mut Self> {
1728        self.next.as_mut().map(|non_null| unsafe { non_null.as_mut() })
1729    }
1730}
1731
1732impl<const CAP: usize, Item, Gap> fmt::Debug for LinkedChunk<CAP, Item, Gap>
1733where
1734    Item: fmt::Debug,
1735    Gap: fmt::Debug,
1736{
1737    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
1738        formatter
1739            .debug_struct("LinkedChunk")
1740            .field("first (deref)", unsafe { self.links.first.as_ref() })
1741            .field("last", &self.links.last)
1742            .finish_non_exhaustive()
1743    }
1744}
1745
1746impl<const CAP: usize, Item, Gap> fmt::Debug for Chunk<CAP, Item, Gap>
1747where
1748    Item: fmt::Debug,
1749    Gap: fmt::Debug,
1750{
1751    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
1752        formatter
1753            .debug_struct("Chunk")
1754            .field("identifier", &self.identifier)
1755            .field("content", &self.content)
1756            .field("previous", &self.previous)
1757            .field("ptr", &std::ptr::from_ref(self))
1758            .field("next", &self.next)
1759            .field("next (deref)", &self.next.as_ref().map(|non_null| unsafe { non_null.as_ref() }))
1760            .finish()
1761    }
1762}
1763
1764/// The raw representation of a linked chunk, as persisted in storage.
1765///
1766/// It may rebuilt into [`Chunk`] and shares the same internal representation,
1767/// except that links are materialized using [`ChunkIdentifier`] instead of raw
1768/// pointers to the previous and next chunks.
1769#[derive(Clone, Debug)]
1770pub struct RawChunk<Item, Gap> {
1771    /// Content section of the linked chunk.
1772    pub content: ChunkContent<Item, Gap>,
1773
1774    /// Link to the previous chunk, via its identifier.
1775    pub previous: Option<ChunkIdentifier>,
1776
1777    /// Current chunk's identifier.
1778    pub identifier: ChunkIdentifier,
1779
1780    /// Link to the next chunk, via its identifier.
1781    pub next: Option<ChunkIdentifier>,
1782}
1783
1784/// A simplified [`RawChunk`] that only contains the number of items in a chunk,
1785/// instead of its type.
1786#[derive(Clone, Debug)]
1787pub struct ChunkMetadata {
1788    /// The number of items in this chunk.
1789    ///
1790    /// By convention, a gap chunk contains 0 items.
1791    pub num_items: usize,
1792
1793    /// Link to the previous chunk, via its identifier.
1794    pub previous: Option<ChunkIdentifier>,
1795
1796    /// Current chunk's identifier.
1797    pub identifier: ChunkIdentifier,
1798
1799    /// Link to the next chunk, via its identifier.
1800    pub next: Option<ChunkIdentifier>,
1801}
1802
1803#[cfg(test)]
1804mod tests {
1805    use std::{
1806        ops::Not,
1807        sync::{Arc, atomic::Ordering},
1808    };
1809
1810    use assert_matches::assert_matches;
1811
1812    use super::{
1813        Chunk, ChunkContent, ChunkIdentifier, ChunkIdentifierGenerator, Error, LinkedChunk,
1814        Position,
1815    };
1816
1817    #[test]
1818    fn test_chunk_identifier_generator() {
1819        let generator = ChunkIdentifierGenerator::new_from_scratch();
1820
1821        assert_eq!(generator.next(), ChunkIdentifier(1));
1822        assert_eq!(generator.next(), ChunkIdentifier(2));
1823        assert_eq!(generator.next(), ChunkIdentifier(3));
1824        assert_eq!(generator.next(), ChunkIdentifier(4));
1825
1826        let generator =
1827            ChunkIdentifierGenerator::new_from_previous_chunk_identifier(ChunkIdentifier(42));
1828
1829        assert_eq!(generator.next(), ChunkIdentifier(43));
1830        assert_eq!(generator.next(), ChunkIdentifier(44));
1831        assert_eq!(generator.next(), ChunkIdentifier(45));
1832        assert_eq!(generator.next(), ChunkIdentifier(46));
1833    }
1834
1835    #[test]
1836    fn test_empty() {
1837        let items = LinkedChunk::<3, char, ()>::new();
1838
1839        assert_eq!(items.num_items(), 0);
1840
1841        // This test also ensures that `Drop` for `LinkedChunk` works when
1842        // there is only one chunk.
1843    }
1844
1845    #[test]
1846    fn test_updates() {
1847        assert!(LinkedChunk::<3, char, ()>::new().updates().is_none());
1848        assert!(LinkedChunk::<3, char, ()>::new_with_update_history().updates().is_some());
1849    }
1850
1851    #[test]
1852    fn test_new_with_initial_update() {
1853        use super::Update::*;
1854
1855        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
1856
1857        assert_eq!(
1858            linked_chunk.updates().unwrap().take(),
1859            &[NewItemsChunk { previous: None, new: ChunkIdentifier(0), next: None }]
1860        );
1861    }
1862
1863    #[test]
1864    fn test_push_items() {
1865        use super::Update::*;
1866
1867        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
1868
1869        // Ignore initial update.
1870        let _ = linked_chunk.updates().unwrap().take();
1871
1872        linked_chunk.push_items_back(['a']);
1873
1874        assert_items_eq!(linked_chunk, ['a']);
1875        assert_eq!(
1876            linked_chunk.updates().unwrap().take(),
1877            &[PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a'] }]
1878        );
1879
1880        linked_chunk.push_items_back(['b', 'c']);
1881        assert_items_eq!(linked_chunk, ['a', 'b', 'c']);
1882        assert_eq!(
1883            linked_chunk.updates().unwrap().take(),
1884            &[PushItems { at: Position(ChunkIdentifier(0), 1), items: vec!['b', 'c'] }]
1885        );
1886
1887        linked_chunk.push_items_back(['d', 'e']);
1888        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e']);
1889        assert_eq!(
1890            linked_chunk.updates().unwrap().take(),
1891            &[
1892                NewItemsChunk {
1893                    previous: Some(ChunkIdentifier(0)),
1894                    new: ChunkIdentifier(1),
1895                    next: None
1896                },
1897                PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e'] }
1898            ]
1899        );
1900
1901        linked_chunk.push_items_back(['f', 'g', 'h', 'i', 'j']);
1902        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] ['g', 'h', 'i'] ['j']);
1903        assert_eq!(
1904            linked_chunk.updates().unwrap().take(),
1905            &[
1906                PushItems { at: Position(ChunkIdentifier(1), 2), items: vec!['f'] },
1907                NewItemsChunk {
1908                    previous: Some(ChunkIdentifier(1)),
1909                    new: ChunkIdentifier(2),
1910                    next: None,
1911                },
1912                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['g', 'h', 'i'] },
1913                NewItemsChunk {
1914                    previous: Some(ChunkIdentifier(2)),
1915                    new: ChunkIdentifier(3),
1916                    next: None,
1917                },
1918                PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['j'] },
1919            ]
1920        );
1921
1922        assert_eq!(linked_chunk.num_items(), 10);
1923    }
1924
1925    #[test]
1926    fn test_push_gap() {
1927        use super::Update::*;
1928
1929        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
1930
1931        // Ignore initial update.
1932        let _ = linked_chunk.updates().unwrap().take();
1933
1934        linked_chunk.push_items_back(['a']);
1935        assert_items_eq!(linked_chunk, ['a']);
1936        assert_eq!(
1937            linked_chunk.updates().unwrap().take(),
1938            &[PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a'] }]
1939        );
1940
1941        linked_chunk.push_gap_back(());
1942        assert_items_eq!(linked_chunk, ['a'] [-]);
1943        assert_eq!(
1944            linked_chunk.updates().unwrap().take(),
1945            &[NewGapChunk {
1946                previous: Some(ChunkIdentifier(0)),
1947                new: ChunkIdentifier(1),
1948                next: None,
1949                gap: (),
1950            }]
1951        );
1952
1953        linked_chunk.push_items_back(['b', 'c', 'd', 'e']);
1954        assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c', 'd'] ['e']);
1955        assert_eq!(
1956            linked_chunk.updates().unwrap().take(),
1957            &[
1958                NewItemsChunk {
1959                    previous: Some(ChunkIdentifier(1)),
1960                    new: ChunkIdentifier(2),
1961                    next: None,
1962                },
1963                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['b', 'c', 'd'] },
1964                NewItemsChunk {
1965                    previous: Some(ChunkIdentifier(2)),
1966                    new: ChunkIdentifier(3),
1967                    next: None,
1968                },
1969                PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['e'] },
1970            ]
1971        );
1972
1973        linked_chunk.push_gap_back(());
1974        linked_chunk.push_gap_back(()); // why not
1975        assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c', 'd'] ['e'] [-] [-]);
1976        assert_eq!(
1977            linked_chunk.updates().unwrap().take(),
1978            &[
1979                NewGapChunk {
1980                    previous: Some(ChunkIdentifier(3)),
1981                    new: ChunkIdentifier(4),
1982                    next: None,
1983                    gap: (),
1984                },
1985                NewGapChunk {
1986                    previous: Some(ChunkIdentifier(4)),
1987                    new: ChunkIdentifier(5),
1988                    next: None,
1989                    gap: (),
1990                }
1991            ]
1992        );
1993
1994        linked_chunk.push_items_back(['f', 'g', 'h', 'i']);
1995        assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c', 'd'] ['e'] [-] [-] ['f', 'g', 'h'] ['i']);
1996        assert_eq!(
1997            linked_chunk.updates().unwrap().take(),
1998            &[
1999                NewItemsChunk {
2000                    previous: Some(ChunkIdentifier(5)),
2001                    new: ChunkIdentifier(6),
2002                    next: None,
2003                },
2004                PushItems { at: Position(ChunkIdentifier(6), 0), items: vec!['f', 'g', 'h'] },
2005                NewItemsChunk {
2006                    previous: Some(ChunkIdentifier(6)),
2007                    new: ChunkIdentifier(7),
2008                    next: None,
2009                },
2010                PushItems { at: Position(ChunkIdentifier(7), 0), items: vec!['i'] },
2011            ]
2012        );
2013
2014        assert_eq!(linked_chunk.num_items(), 9);
2015    }
2016
2017    #[test]
2018    fn test_identifiers_and_positions() {
2019        let mut linked_chunk = LinkedChunk::<3, char, ()>::new();
2020        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2021        linked_chunk.push_gap_back(());
2022        linked_chunk.push_items_back(['g', 'h', 'i', 'j']);
2023        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] [-] ['g', 'h', 'i'] ['j']);
2024
2025        assert_eq!(linked_chunk.chunk_identifier(Chunk::is_gap), Some(ChunkIdentifier(2)));
2026        assert_eq!(
2027            linked_chunk.item_position(|item| *item == 'e'),
2028            Some(Position(ChunkIdentifier(1), 1))
2029        );
2030    }
2031
2032    #[test]
2033    fn test_rchunks() {
2034        let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2035        linked_chunk.push_items_back(['a', 'b']);
2036        linked_chunk.push_gap_back(());
2037        linked_chunk.push_items_back(['c', 'd', 'e']);
2038
2039        let mut iterator = linked_chunk.rchunks();
2040
2041        assert_matches!(
2042            iterator.next(),
2043            Some(Chunk { identifier: ChunkIdentifier(3), content: ChunkContent::Items(items), .. }) => {
2044                assert_eq!(items, &['e']);
2045            }
2046        );
2047        assert_matches!(
2048            iterator.next(),
2049            Some(Chunk { identifier: ChunkIdentifier(2), content: ChunkContent::Items(items), .. }) => {
2050                assert_eq!(items, &['c', 'd']);
2051            }
2052        );
2053        assert_matches!(
2054            iterator.next(),
2055            Some(Chunk { identifier: ChunkIdentifier(1), content: ChunkContent::Gap(..), .. })
2056        );
2057        assert_matches!(
2058            iterator.next(),
2059            Some(Chunk { identifier: ChunkIdentifier(0), content: ChunkContent::Items(items), .. }) => {
2060                assert_eq!(items, &['a', 'b']);
2061            }
2062        );
2063        assert_matches!(iterator.next(), None);
2064    }
2065
2066    #[test]
2067    fn test_chunks() {
2068        let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2069        linked_chunk.push_items_back(['a', 'b']);
2070        linked_chunk.push_gap_back(());
2071        linked_chunk.push_items_back(['c', 'd', 'e']);
2072
2073        let mut iterator = linked_chunk.chunks();
2074
2075        assert_matches!(
2076            iterator.next(),
2077            Some(Chunk { identifier: ChunkIdentifier(0), content: ChunkContent::Items(items), .. }) => {
2078                assert_eq!(items, &['a', 'b']);
2079            }
2080        );
2081        assert_matches!(
2082            iterator.next(),
2083            Some(Chunk { identifier: ChunkIdentifier(1), content: ChunkContent::Gap(..), .. })
2084        );
2085        assert_matches!(
2086            iterator.next(),
2087            Some(Chunk { identifier: ChunkIdentifier(2), content: ChunkContent::Items(items), .. }) => {
2088                assert_eq!(items, &['c', 'd']);
2089            }
2090        );
2091        assert_matches!(
2092            iterator.next(),
2093            Some(Chunk { identifier: ChunkIdentifier(3), content: ChunkContent::Items(items), .. }) => {
2094                assert_eq!(items, &['e']);
2095            }
2096        );
2097        assert_matches!(iterator.next(), None);
2098    }
2099
2100    #[test]
2101    fn test_rchunks_from() -> Result<(), Error> {
2102        let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2103        linked_chunk.push_items_back(['a', 'b']);
2104        linked_chunk.push_gap_back(());
2105        linked_chunk.push_items_back(['c', 'd', 'e']);
2106
2107        let mut iterator = linked_chunk.rchunks_from(
2108            linked_chunk.item_position(|item| *item == 'c').unwrap().chunk_identifier(),
2109        )?;
2110
2111        assert_matches!(
2112            iterator.next(),
2113            Some(Chunk { identifier: ChunkIdentifier(2), content: ChunkContent::Items(items), .. }) => {
2114                assert_eq!(items, &['c', 'd']);
2115            }
2116        );
2117        assert_matches!(
2118            iterator.next(),
2119            Some(Chunk { identifier: ChunkIdentifier(1), content: ChunkContent::Gap(..), .. })
2120        );
2121        assert_matches!(
2122            iterator.next(),
2123            Some(Chunk { identifier: ChunkIdentifier(0), content: ChunkContent::Items(items), .. }) => {
2124                assert_eq!(items, &['a', 'b']);
2125            }
2126        );
2127        assert_matches!(iterator.next(), None);
2128
2129        Ok(())
2130    }
2131
2132    #[test]
2133    fn test_chunks_from() -> Result<(), Error> {
2134        let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2135        linked_chunk.push_items_back(['a', 'b']);
2136        linked_chunk.push_gap_back(());
2137        linked_chunk.push_items_back(['c', 'd', 'e']);
2138
2139        let mut iterator = linked_chunk.chunks_from(
2140            linked_chunk.item_position(|item| *item == 'c').unwrap().chunk_identifier(),
2141        )?;
2142
2143        assert_matches!(
2144            iterator.next(),
2145            Some(Chunk { identifier: ChunkIdentifier(2), content: ChunkContent::Items(items), .. }) => {
2146                assert_eq!(items, &['c', 'd']);
2147            }
2148        );
2149        assert_matches!(
2150            iterator.next(),
2151            Some(Chunk { identifier: ChunkIdentifier(3), content: ChunkContent::Items(items), .. }) => {
2152                assert_eq!(items, &['e']);
2153            }
2154        );
2155        assert_matches!(iterator.next(), None);
2156
2157        Ok(())
2158    }
2159
2160    #[test]
2161    fn test_ritems() {
2162        let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2163        linked_chunk.push_items_back(['a', 'b']);
2164        linked_chunk.push_gap_back(());
2165        linked_chunk.push_items_back(['c', 'd', 'e']);
2166
2167        let mut iterator = linked_chunk.ritems();
2168
2169        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(3), 0), 'e')));
2170        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 1), 'd')));
2171        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2172        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 1), 'b')));
2173        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 0), 'a')));
2174        assert_matches!(iterator.next(), None);
2175    }
2176
2177    #[test]
2178    fn test_ritems_with_final_gap() -> Result<(), Error> {
2179        let mut linked_chunk = LinkedChunk::<3, char, ()>::new();
2180        linked_chunk.push_items_back(['a', 'b']);
2181        linked_chunk.push_gap_back(());
2182        linked_chunk.push_items_back(['c', 'd', 'e']);
2183        linked_chunk.push_gap_back(());
2184
2185        let mut iterator = linked_chunk.ritems();
2186
2187        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 2), 'e')));
2188        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 1), 'd')));
2189        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2190        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 1), 'b')));
2191        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 0), 'a')));
2192        assert_matches!(iterator.next(), None);
2193
2194        Ok(())
2195    }
2196
2197    #[test]
2198    fn test_ritems_empty() {
2199        let linked_chunk = LinkedChunk::<2, char, ()>::new();
2200        let mut iterator = linked_chunk.ritems();
2201
2202        assert_matches!(iterator.next(), None);
2203    }
2204
2205    #[test]
2206    fn test_items() {
2207        let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2208        linked_chunk.push_items_back(['a', 'b']);
2209        linked_chunk.push_gap_back(());
2210        linked_chunk.push_items_back(['c', 'd', 'e']);
2211
2212        let mut iterator = linked_chunk.items();
2213
2214        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 0), 'a')));
2215        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 1), 'b')));
2216        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2217        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 1), 'd')));
2218        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(3), 0), 'e')));
2219        assert_matches!(iterator.next(), None);
2220    }
2221
2222    #[test]
2223    fn test_items_empty() {
2224        let linked_chunk = LinkedChunk::<2, char, ()>::new();
2225        let mut iterator = linked_chunk.items();
2226
2227        assert_matches!(iterator.next(), None);
2228    }
2229
2230    #[test]
2231    fn test_ritems_from() -> Result<(), Error> {
2232        let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2233        linked_chunk.push_items_back(['a', 'b']);
2234        linked_chunk.push_gap_back(());
2235        linked_chunk.push_items_back(['c', 'd', 'e']);
2236
2237        let mut iterator =
2238            linked_chunk.ritems_from(linked_chunk.item_position(|item| *item == 'c').unwrap())?;
2239
2240        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2241        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 1), 'b')));
2242        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 0), 'a')));
2243        assert_matches!(iterator.next(), None);
2244
2245        Ok(())
2246    }
2247
2248    #[test]
2249    fn test_items_from() -> Result<(), Error> {
2250        let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2251        linked_chunk.push_items_back(['a', 'b']);
2252        linked_chunk.push_gap_back(());
2253        linked_chunk.push_items_back(['c', 'd', 'e']);
2254
2255        let mut iterator =
2256            linked_chunk.items_from(linked_chunk.item_position(|item| *item == 'c').unwrap())?;
2257
2258        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2259        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 1), 'd')));
2260        assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(3), 0), 'e')));
2261        assert_matches!(iterator.next(), None);
2262
2263        Ok(())
2264    }
2265
2266    #[test]
2267    fn test_insert_items_at() -> Result<(), Error> {
2268        use super::Update::*;
2269
2270        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2271
2272        // Ignore initial update.
2273        let _ = linked_chunk.updates().unwrap().take();
2274
2275        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2276        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f']);
2277        assert_eq!(
2278            linked_chunk.updates().unwrap().take(),
2279            &[
2280                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2281                NewItemsChunk {
2282                    previous: Some(ChunkIdentifier(0)),
2283                    new: ChunkIdentifier(1),
2284                    next: None,
2285                },
2286                PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2287            ]
2288        );
2289
2290        // Insert inside the last chunk.
2291        {
2292            let pos_e = linked_chunk.item_position(|item| *item == 'e').unwrap();
2293
2294            // Insert 4 elements, so that it overflows the chunk capacity. It's important to
2295            // see whether chunks are correctly updated and linked.
2296            linked_chunk.insert_items_at(pos_e, ['w', 'x', 'y', 'z'])?;
2297
2298            assert_items_eq!(
2299                linked_chunk,
2300                ['a', 'b', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f']
2301            );
2302            assert_eq!(linked_chunk.num_items(), 10);
2303            assert_eq!(
2304                linked_chunk.updates().unwrap().take(),
2305                &[
2306                    DetachLastItems { at: Position(ChunkIdentifier(1), 1) },
2307                    PushItems { at: Position(ChunkIdentifier(1), 1), items: vec!['w', 'x'] },
2308                    NewItemsChunk {
2309                        previous: Some(ChunkIdentifier(1)),
2310                        new: ChunkIdentifier(2),
2311                        next: None,
2312                    },
2313                    PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['y', 'z'] },
2314                    StartReattachItems,
2315                    PushItems { at: Position(ChunkIdentifier(2), 2), items: vec!['e'] },
2316                    NewItemsChunk {
2317                        previous: Some(ChunkIdentifier(2)),
2318                        new: ChunkIdentifier(3),
2319                        next: None,
2320                    },
2321                    PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['f'] },
2322                    EndReattachItems,
2323                ]
2324            );
2325        }
2326
2327        // Insert inside the first chunk.
2328        {
2329            let pos_a = linked_chunk.item_position(|item| *item == 'a').unwrap();
2330            linked_chunk.insert_items_at(pos_a, ['l', 'm', 'n', 'o'])?;
2331
2332            assert_items_eq!(
2333                linked_chunk,
2334                ['l', 'm', 'n'] ['o', 'a', 'b'] ['c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f']
2335            );
2336            assert_eq!(linked_chunk.num_items(), 14);
2337            assert_eq!(
2338                linked_chunk.updates().unwrap().take(),
2339                &[
2340                    DetachLastItems { at: Position(ChunkIdentifier(0), 0) },
2341                    PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['l', 'm', 'n'] },
2342                    NewItemsChunk {
2343                        previous: Some(ChunkIdentifier(0)),
2344                        new: ChunkIdentifier(4),
2345                        next: Some(ChunkIdentifier(1)),
2346                    },
2347                    PushItems { at: Position(ChunkIdentifier(4), 0), items: vec!['o'] },
2348                    StartReattachItems,
2349                    PushItems { at: Position(ChunkIdentifier(4), 1), items: vec!['a', 'b'] },
2350                    NewItemsChunk {
2351                        previous: Some(ChunkIdentifier(4)),
2352                        new: ChunkIdentifier(5),
2353                        next: Some(ChunkIdentifier(1)),
2354                    },
2355                    PushItems { at: Position(ChunkIdentifier(5), 0), items: vec!['c'] },
2356                    EndReattachItems,
2357                ]
2358            );
2359        }
2360
2361        // Insert inside a middle chunk.
2362        {
2363            let pos_c = linked_chunk.item_position(|item| *item == 'c').unwrap();
2364            linked_chunk.insert_items_at(pos_c, ['r', 's'])?;
2365
2366            assert_items_eq!(
2367                linked_chunk,
2368                ['l', 'm', 'n'] ['o', 'a', 'b'] ['r', 's', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f']
2369            );
2370            assert_eq!(linked_chunk.num_items(), 16);
2371            assert_eq!(
2372                linked_chunk.updates().unwrap().take(),
2373                &[
2374                    DetachLastItems { at: Position(ChunkIdentifier(5), 0) },
2375                    PushItems { at: Position(ChunkIdentifier(5), 0), items: vec!['r', 's'] },
2376                    StartReattachItems,
2377                    PushItems { at: Position(ChunkIdentifier(5), 2), items: vec!['c'] },
2378                    EndReattachItems,
2379                ]
2380            );
2381        }
2382
2383        // Insert at the end of a chunk.
2384        {
2385            let pos_f = linked_chunk.item_position(|item| *item == 'f').unwrap();
2386            let pos_f = Position(pos_f.chunk_identifier(), pos_f.index() + 1);
2387
2388            linked_chunk.insert_items_at(pos_f, ['p', 'q'])?;
2389            assert_items_eq!(
2390                linked_chunk,
2391                ['l', 'm', 'n'] ['o', 'a', 'b'] ['r', 's', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f', 'p', 'q']
2392            );
2393            assert_eq!(
2394                linked_chunk.updates().unwrap().take(),
2395                &[PushItems { at: Position(ChunkIdentifier(3), 1), items: vec!['p', 'q'] }]
2396            );
2397            assert_eq!(linked_chunk.num_items(), 18);
2398        }
2399
2400        // Insert in a chunk that does not exist.
2401        {
2402            assert_matches!(
2403                linked_chunk.insert_items_at(Position(ChunkIdentifier(128), 0), ['u', 'v'],),
2404                Err(Error::InvalidChunkIdentifier { identifier: ChunkIdentifier(128) })
2405            );
2406            assert!(linked_chunk.updates().unwrap().take().is_empty());
2407        }
2408
2409        // Insert in a chunk that exists, but at an item that does not exist.
2410        {
2411            assert_matches!(
2412                linked_chunk.insert_items_at(Position(ChunkIdentifier(0), 128), ['u', 'v'],),
2413                Err(Error::InvalidItemIndex { index: 128 })
2414            );
2415            assert!(linked_chunk.updates().unwrap().take().is_empty());
2416        }
2417
2418        // Insert in a gap.
2419        {
2420            // Add a gap to test the error.
2421            linked_chunk.push_gap_back(());
2422            assert_items_eq!(
2423                linked_chunk,
2424                ['l', 'm', 'n'] ['o', 'a', 'b'] ['r', 's', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f', 'p', 'q'] [-]
2425            );
2426            assert_eq!(
2427                linked_chunk.updates().unwrap().take(),
2428                &[NewGapChunk {
2429                    previous: Some(ChunkIdentifier(3)),
2430                    new: ChunkIdentifier(6),
2431                    next: None,
2432                    gap: ()
2433                }]
2434            );
2435
2436            assert_matches!(
2437                linked_chunk.insert_items_at(Position(ChunkIdentifier(6), 0), ['u', 'v'],),
2438                Err(Error::ChunkIsAGap { identifier: ChunkIdentifier(6) })
2439            );
2440        }
2441
2442        assert_eq!(linked_chunk.num_items(), 18);
2443
2444        Ok(())
2445    }
2446
2447    #[test]
2448    fn test_insert_items_at_last_chunk() -> Result<(), Error> {
2449        use super::Update::*;
2450
2451        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2452
2453        // Ignore initial update.
2454        let _ = linked_chunk.updates().unwrap().take();
2455
2456        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2457        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f']);
2458        assert_eq!(
2459            linked_chunk.updates().unwrap().take(),
2460            &[
2461                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2462                NewItemsChunk {
2463                    previous: Some(ChunkIdentifier(0)),
2464                    new: ChunkIdentifier(1),
2465                    next: None,
2466                },
2467                PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2468            ]
2469        );
2470
2471        // Insert inside the last chunk.
2472        let pos_e = linked_chunk.item_position(|item| *item == 'e').unwrap();
2473
2474        // Insert 4 elements, so that it overflows the chunk capacity. It's important to
2475        // see whether chunks are correctly updated and linked.
2476        linked_chunk.insert_items_at(pos_e, ['w', 'x', 'y', 'z'])?;
2477
2478        assert_items_eq!(
2479            linked_chunk,
2480            ['a', 'b', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f']
2481        );
2482        assert_eq!(linked_chunk.num_items(), 10);
2483        assert_eq!(
2484            linked_chunk.updates().unwrap().take(),
2485            &[
2486                DetachLastItems { at: Position(ChunkIdentifier(1), 1) },
2487                PushItems { at: Position(ChunkIdentifier(1), 1), items: vec!['w', 'x'] },
2488                NewItemsChunk {
2489                    previous: Some(ChunkIdentifier(1)),
2490                    new: ChunkIdentifier(2),
2491                    next: None,
2492                },
2493                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['y', 'z'] },
2494                StartReattachItems,
2495                PushItems { at: Position(ChunkIdentifier(2), 2), items: vec!['e'] },
2496                NewItemsChunk {
2497                    previous: Some(ChunkIdentifier(2)),
2498                    new: ChunkIdentifier(3),
2499                    next: None,
2500                },
2501                PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['f'] },
2502                EndReattachItems,
2503            ]
2504        );
2505
2506        Ok(())
2507    }
2508
2509    #[test]
2510    fn test_insert_items_at_first_chunk() -> Result<(), Error> {
2511        use super::Update::*;
2512
2513        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2514
2515        // Ignore initial update.
2516        let _ = linked_chunk.updates().unwrap().take();
2517
2518        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2519        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f']);
2520        assert_eq!(
2521            linked_chunk.updates().unwrap().take(),
2522            &[
2523                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2524                NewItemsChunk {
2525                    previous: Some(ChunkIdentifier(0)),
2526                    new: ChunkIdentifier(1),
2527                    next: None,
2528                },
2529                PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2530            ]
2531        );
2532
2533        // Insert inside the first chunk.
2534        let pos_a = linked_chunk.item_position(|item| *item == 'a').unwrap();
2535        linked_chunk.insert_items_at(pos_a, ['l', 'm', 'n', 'o'])?;
2536
2537        assert_items_eq!(
2538            linked_chunk,
2539            ['l', 'm', 'n'] ['o', 'a', 'b'] ['c'] ['d', 'e', 'f']
2540        );
2541        assert_eq!(linked_chunk.num_items(), 10);
2542        assert_eq!(
2543            linked_chunk.updates().unwrap().take(),
2544            &[
2545                DetachLastItems { at: Position(ChunkIdentifier(0), 0) },
2546                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['l', 'm', 'n'] },
2547                NewItemsChunk {
2548                    previous: Some(ChunkIdentifier(0)),
2549                    new: ChunkIdentifier(2),
2550                    next: Some(ChunkIdentifier(1)),
2551                },
2552                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['o'] },
2553                StartReattachItems,
2554                PushItems { at: Position(ChunkIdentifier(2), 1), items: vec!['a', 'b'] },
2555                NewItemsChunk {
2556                    previous: Some(ChunkIdentifier(2)),
2557                    new: ChunkIdentifier(3),
2558                    next: Some(ChunkIdentifier(1)),
2559                },
2560                PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['c'] },
2561                EndReattachItems,
2562            ]
2563        );
2564
2565        Ok(())
2566    }
2567
2568    #[test]
2569    fn test_insert_items_at_middle_chunk() -> Result<(), Error> {
2570        use super::Update::*;
2571
2572        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2573
2574        // Ignore initial update.
2575        let _ = linked_chunk.updates().unwrap().take();
2576
2577        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']);
2578        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] ['g', 'h']);
2579        assert_eq!(
2580            linked_chunk.updates().unwrap().take(),
2581            &[
2582                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2583                NewItemsChunk {
2584                    previous: Some(ChunkIdentifier(0)),
2585                    new: ChunkIdentifier(1),
2586                    next: None,
2587                },
2588                PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2589                NewItemsChunk {
2590                    previous: Some(ChunkIdentifier(1)),
2591                    new: ChunkIdentifier(2),
2592                    next: None,
2593                },
2594                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['g', 'h'] },
2595            ]
2596        );
2597
2598        let pos_d = linked_chunk.item_position(|item| *item == 'd').unwrap();
2599        linked_chunk.insert_items_at(pos_d, ['r', 's'])?;
2600
2601        assert_items_eq!(
2602            linked_chunk,
2603            ['a', 'b', 'c'] ['r', 's', 'd'] ['e', 'f'] ['g', 'h']
2604        );
2605        assert_eq!(linked_chunk.num_items(), 10);
2606        assert_eq!(
2607            linked_chunk.updates().unwrap().take(),
2608            &[
2609                DetachLastItems { at: Position(ChunkIdentifier(1), 0) },
2610                PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['r', 's'] },
2611                StartReattachItems,
2612                PushItems { at: Position(ChunkIdentifier(1), 2), items: vec!['d'] },
2613                NewItemsChunk {
2614                    previous: Some(ChunkIdentifier(1)),
2615                    new: ChunkIdentifier(3),
2616                    next: Some(ChunkIdentifier(2)),
2617                },
2618                PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['e', 'f'] },
2619                EndReattachItems,
2620            ]
2621        );
2622
2623        Ok(())
2624    }
2625
2626    #[test]
2627    fn test_insert_items_at_end_of_chunk() -> Result<(), Error> {
2628        use super::Update::*;
2629
2630        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2631
2632        // Ignore initial update.
2633        let _ = linked_chunk.updates().unwrap().take();
2634
2635        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e']);
2636        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e']);
2637        assert_eq!(
2638            linked_chunk.updates().unwrap().take(),
2639            &[
2640                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2641                NewItemsChunk {
2642                    previous: Some(ChunkIdentifier(0)),
2643                    new: ChunkIdentifier(1),
2644                    next: None,
2645                },
2646                PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e'] },
2647            ]
2648        );
2649
2650        // Insert at the end of a chunk.
2651        let pos_e = linked_chunk.item_position(|item| *item == 'e').unwrap();
2652        let pos_after_e = Position(pos_e.chunk_identifier(), pos_e.index() + 1);
2653
2654        linked_chunk.insert_items_at(pos_after_e, ['p', 'q'])?;
2655        assert_items_eq!(
2656            linked_chunk,
2657            ['a', 'b', 'c'] ['d', 'e', 'p'] ['q']
2658        );
2659        assert_eq!(
2660            linked_chunk.updates().unwrap().take(),
2661            &[
2662                PushItems { at: Position(ChunkIdentifier(1), 2), items: vec!['p'] },
2663                NewItemsChunk {
2664                    previous: Some(ChunkIdentifier(1)),
2665                    new: ChunkIdentifier(2),
2666                    next: None
2667                },
2668                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['q'] }
2669            ]
2670        );
2671        assert_eq!(linked_chunk.num_items(), 7);
2672
2673        Ok(())
2674    }
2675
2676    #[test]
2677    fn test_insert_items_at_errs() -> Result<(), Error> {
2678        use super::Update::*;
2679
2680        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2681
2682        // Ignore initial update.
2683        let _ = linked_chunk.updates().unwrap().take();
2684
2685        linked_chunk.push_items_back(['a', 'b', 'c']);
2686        linked_chunk.push_gap_back(());
2687        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] [-]);
2688        assert_eq!(
2689            linked_chunk.updates().unwrap().take(),
2690            &[
2691                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2692                NewGapChunk {
2693                    previous: Some(ChunkIdentifier(0)),
2694                    new: ChunkIdentifier(1),
2695                    next: None,
2696                    gap: (),
2697                },
2698            ]
2699        );
2700
2701        // Insert in a chunk that does not exist.
2702        {
2703            assert_matches!(
2704                linked_chunk.insert_items_at(Position(ChunkIdentifier(128), 0), ['u', 'v'],),
2705                Err(Error::InvalidChunkIdentifier { identifier: ChunkIdentifier(128) })
2706            );
2707            assert!(linked_chunk.updates().unwrap().take().is_empty());
2708        }
2709
2710        // Insert in a chunk that exists, but at an item that does not exist.
2711        {
2712            assert_matches!(
2713                linked_chunk.insert_items_at(Position(ChunkIdentifier(0), 128), ['u', 'v'],),
2714                Err(Error::InvalidItemIndex { index: 128 })
2715            );
2716            assert!(linked_chunk.updates().unwrap().take().is_empty());
2717        }
2718
2719        // Insert in a gap.
2720        {
2721            assert_matches!(
2722                linked_chunk.insert_items_at(Position(ChunkIdentifier(1), 0), ['u', 'v'],),
2723                Err(Error::ChunkIsAGap { identifier: ChunkIdentifier(1) })
2724            );
2725        }
2726
2727        Ok(())
2728    }
2729
2730    #[test]
2731    fn test_remove_item_at() -> Result<(), Error> {
2732        use super::Update::*;
2733
2734        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2735
2736        // Ignore initial update.
2737        let _ = linked_chunk.updates().unwrap().take();
2738
2739        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']);
2740        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] ['g', 'h', 'i'] ['j', 'k']);
2741        assert_eq!(linked_chunk.num_items(), 11);
2742
2743        // Ignore previous updates.
2744        let _ = linked_chunk.updates().unwrap().take();
2745
2746        // Remove the last item of the middle chunk, 3 times. The chunk is empty after
2747        // that. The chunk is removed.
2748        {
2749            let position_of_f = linked_chunk.item_position(|item| *item == 'f').unwrap();
2750            let removed_item = linked_chunk.remove_item_at(position_of_f)?;
2751
2752            assert_eq!(removed_item, 'f');
2753            assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e'] ['g', 'h', 'i'] ['j', 'k']);
2754            assert_eq!(linked_chunk.num_items(), 10);
2755
2756            let position_of_e = linked_chunk.item_position(|item| *item == 'e').unwrap();
2757            let removed_item = linked_chunk.remove_item_at(position_of_e)?;
2758
2759            assert_eq!(removed_item, 'e');
2760            assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d'] ['g', 'h', 'i'] ['j', 'k']);
2761            assert_eq!(linked_chunk.num_items(), 9);
2762
2763            let position_of_d = linked_chunk.item_position(|item| *item == 'd').unwrap();
2764            let removed_item = linked_chunk.remove_item_at(position_of_d)?;
2765
2766            assert_eq!(removed_item, 'd');
2767            assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['g', 'h', 'i'] ['j', 'k']);
2768            assert_eq!(linked_chunk.num_items(), 8);
2769
2770            assert_eq!(
2771                linked_chunk.updates().unwrap().take(),
2772                &[
2773                    RemoveItem { at: Position(ChunkIdentifier(1), 2) },
2774                    RemoveItem { at: Position(ChunkIdentifier(1), 1) },
2775                    RemoveItem { at: Position(ChunkIdentifier(1), 0) },
2776                    RemoveChunk(ChunkIdentifier(1)),
2777                ]
2778            );
2779        }
2780
2781        // Remove the first item of the first chunk, 3 times. The chunk is empty after
2782        // that. The chunk is NOT removed because it's the first chunk.
2783        {
2784            let first_position = linked_chunk.item_position(|item| *item == 'a').unwrap();
2785            let removed_item = linked_chunk.remove_item_at(first_position)?;
2786
2787            assert_eq!(removed_item, 'a');
2788            assert_items_eq!(linked_chunk, ['b', 'c'] ['g', 'h', 'i'] ['j', 'k']);
2789            assert_eq!(linked_chunk.num_items(), 7);
2790
2791            let removed_item = linked_chunk.remove_item_at(first_position)?;
2792
2793            assert_eq!(removed_item, 'b');
2794            assert_items_eq!(linked_chunk, ['c'] ['g', 'h', 'i'] ['j', 'k']);
2795            assert_eq!(linked_chunk.num_items(), 6);
2796
2797            let removed_item = linked_chunk.remove_item_at(first_position)?;
2798
2799            assert_eq!(removed_item, 'c');
2800            assert_items_eq!(linked_chunk, [] ['g', 'h', 'i'] ['j', 'k']);
2801            assert_eq!(linked_chunk.num_items(), 5);
2802
2803            assert_eq!(
2804                linked_chunk.updates().unwrap().take(),
2805                &[
2806                    RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2807                    RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2808                    RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2809                ]
2810            );
2811        }
2812
2813        // Remove the first item of the middle chunk, 3 times. The chunk is empty after
2814        // that. The chunk is removed.
2815        {
2816            let first_position = linked_chunk.item_position(|item| *item == 'g').unwrap();
2817            let removed_item = linked_chunk.remove_item_at(first_position)?;
2818
2819            assert_eq!(removed_item, 'g');
2820            assert_items_eq!(linked_chunk, [] ['h', 'i'] ['j', 'k']);
2821            assert_eq!(linked_chunk.num_items(), 4);
2822
2823            let removed_item = linked_chunk.remove_item_at(first_position)?;
2824
2825            assert_eq!(removed_item, 'h');
2826            assert_items_eq!(linked_chunk, [] ['i'] ['j', 'k']);
2827            assert_eq!(linked_chunk.num_items(), 3);
2828
2829            let removed_item = linked_chunk.remove_item_at(first_position)?;
2830
2831            assert_eq!(removed_item, 'i');
2832            assert_items_eq!(linked_chunk, [] ['j', 'k']);
2833            assert_eq!(linked_chunk.num_items(), 2);
2834
2835            assert_eq!(
2836                linked_chunk.updates().unwrap().take(),
2837                &[
2838                    RemoveItem { at: Position(ChunkIdentifier(2), 0) },
2839                    RemoveItem { at: Position(ChunkIdentifier(2), 0) },
2840                    RemoveItem { at: Position(ChunkIdentifier(2), 0) },
2841                    RemoveChunk(ChunkIdentifier(2)),
2842                ]
2843            );
2844        }
2845
2846        // Remove the last item of the last chunk, twice. The chunk is empty after that.
2847        // The chunk is removed.
2848        {
2849            let position_of_k = linked_chunk.item_position(|item| *item == 'k').unwrap();
2850            let removed_item = linked_chunk.remove_item_at(position_of_k)?;
2851
2852            assert_eq!(removed_item, 'k');
2853            #[rustfmt::skip]
2854            assert_items_eq!(linked_chunk, [] ['j']);
2855            assert_eq!(linked_chunk.num_items(), 1);
2856
2857            let position_of_j = linked_chunk.item_position(|item| *item == 'j').unwrap();
2858            let removed_item = linked_chunk.remove_item_at(position_of_j)?;
2859
2860            assert_eq!(removed_item, 'j');
2861            assert_items_eq!(linked_chunk, []);
2862            assert_eq!(linked_chunk.num_items(), 0);
2863
2864            assert_eq!(
2865                linked_chunk.updates().unwrap().take(),
2866                &[
2867                    RemoveItem { at: Position(ChunkIdentifier(3), 1) },
2868                    RemoveItem { at: Position(ChunkIdentifier(3), 0) },
2869                    RemoveChunk(ChunkIdentifier(3)),
2870                ]
2871            );
2872        }
2873
2874        // Add a couple more items, delete one, add a gap, and delete more items.
2875        {
2876            linked_chunk.push_items_back(['a', 'b', 'c', 'd']);
2877
2878            #[rustfmt::skip]
2879            assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d']);
2880            assert_eq!(linked_chunk.num_items(), 4);
2881
2882            let position_of_c = linked_chunk.item_position(|item| *item == 'c').unwrap();
2883            linked_chunk.insert_gap_at((), position_of_c)?;
2884
2885            assert_items_eq!(linked_chunk, ['a', 'b'] [-] ['c'] ['d']);
2886            assert_eq!(linked_chunk.num_items(), 4);
2887
2888            // Ignore updates.
2889            let _ = linked_chunk.updates().unwrap().take();
2890
2891            let position_of_c = linked_chunk.item_position(|item| *item == 'c').unwrap();
2892            let removed_item = linked_chunk.remove_item_at(position_of_c)?;
2893
2894            assert_eq!(removed_item, 'c');
2895            assert_items_eq!(linked_chunk, ['a', 'b'] [-] ['d']);
2896            assert_eq!(linked_chunk.num_items(), 3);
2897
2898            let position_of_d = linked_chunk.item_position(|item| *item == 'd').unwrap();
2899            let removed_item = linked_chunk.remove_item_at(position_of_d)?;
2900
2901            assert_eq!(removed_item, 'd');
2902            assert_items_eq!(linked_chunk, ['a', 'b'] [-]);
2903            assert_eq!(linked_chunk.num_items(), 2);
2904
2905            let first_position = linked_chunk.item_position(|item| *item == 'a').unwrap();
2906            let removed_item = linked_chunk.remove_item_at(first_position)?;
2907
2908            assert_eq!(removed_item, 'a');
2909            assert_items_eq!(linked_chunk, ['b'] [-]);
2910            assert_eq!(linked_chunk.num_items(), 1);
2911
2912            let removed_item = linked_chunk.remove_item_at(first_position)?;
2913
2914            assert_eq!(removed_item, 'b');
2915            assert_items_eq!(linked_chunk, [] [-]);
2916            assert_eq!(linked_chunk.num_items(), 0);
2917
2918            assert_eq!(
2919                linked_chunk.updates().unwrap().take(),
2920                &[
2921                    RemoveItem { at: Position(ChunkIdentifier(6), 0) },
2922                    RemoveChunk(ChunkIdentifier(6)),
2923                    RemoveItem { at: Position(ChunkIdentifier(4), 0) },
2924                    RemoveChunk(ChunkIdentifier(4)),
2925                    RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2926                    RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2927                ]
2928            );
2929        }
2930
2931        Ok(())
2932    }
2933
2934    #[test]
2935    fn test_insert_gap_at() -> Result<(), Error> {
2936        use super::Update::*;
2937
2938        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2939
2940        // Ignore initial update.
2941        let _ = linked_chunk.updates().unwrap().take();
2942
2943        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2944        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f']);
2945        assert_eq!(
2946            linked_chunk.updates().unwrap().take(),
2947            &[
2948                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2949                NewItemsChunk {
2950                    previous: Some(ChunkIdentifier(0)),
2951                    new: ChunkIdentifier(1),
2952                    next: None
2953                },
2954                PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2955            ]
2956        );
2957
2958        // Insert in the middle of a chunk.
2959        {
2960            let position_of_b = linked_chunk.item_position(|item| *item == 'b').unwrap();
2961            linked_chunk.insert_gap_at((), position_of_b)?;
2962
2963            assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c'] ['d', 'e', 'f']);
2964            assert_eq!(
2965                linked_chunk.updates().unwrap().take(),
2966                &[
2967                    DetachLastItems { at: Position(ChunkIdentifier(0), 1) },
2968                    NewGapChunk {
2969                        previous: Some(ChunkIdentifier(0)),
2970                        new: ChunkIdentifier(2),
2971                        next: Some(ChunkIdentifier(1)),
2972                        gap: (),
2973                    },
2974                    StartReattachItems,
2975                    NewItemsChunk {
2976                        previous: Some(ChunkIdentifier(2)),
2977                        new: ChunkIdentifier(3),
2978                        next: Some(ChunkIdentifier(1)),
2979                    },
2980                    PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['b', 'c'] },
2981                    EndReattachItems,
2982                ]
2983            );
2984        }
2985
2986        // Insert at the beginning of a chunk. The targeted chunk is the first chunk.
2987        // `Ends::first` and `Ends::last` may be updated differently.
2988        {
2989            let position_of_a = linked_chunk.item_position(|item| *item == 'a').unwrap();
2990            linked_chunk.insert_gap_at((), position_of_a)?;
2991
2992            // A new empty chunk is NOT created, i.e. `['a']` is not split into `[]` +
2993            // `['a']` because it's a waste of space.
2994            assert_items_eq!(linked_chunk, [-] ['a'] [-] ['b', 'c'] ['d', 'e', 'f']);
2995            assert_eq!(
2996                linked_chunk.updates().unwrap().take(),
2997                &[NewGapChunk {
2998                    previous: None,
2999                    new: ChunkIdentifier(4),
3000                    next: Some(ChunkIdentifier(0)),
3001                    gap: (),
3002                },]
3003            );
3004        }
3005
3006        // Insert at the beginning of a chunk. The targeted chunk is not the first
3007        // chunk. `Ends::first` and `Ends::last` may be updated differently.
3008        {
3009            let position_of_d = linked_chunk.item_position(|item| *item == 'd').unwrap();
3010            linked_chunk.insert_gap_at((), position_of_d)?;
3011
3012            // A new empty chunk is NOT created, i.e. `['d', 'e', 'f']` is not
3013            // split into `[]` + `['d', 'e', 'f']` because it's a waste of
3014            // space.
3015            assert_items_eq!(linked_chunk, [-] ['a'] [-] ['b', 'c'] [-] ['d', 'e', 'f']);
3016            assert_eq!(
3017                linked_chunk.updates().unwrap().take(),
3018                &[NewGapChunk {
3019                    previous: Some(ChunkIdentifier(3)),
3020                    new: ChunkIdentifier(5),
3021                    next: Some(ChunkIdentifier(1)),
3022                    gap: (),
3023                }]
3024            );
3025        }
3026
3027        // Insert in an empty chunk.
3028        {
3029            // Replace a gap by empty items.
3030            let gap_identifier = linked_chunk.chunk_identifier(Chunk::is_gap).unwrap();
3031            let position = linked_chunk.replace_gap_at([], gap_identifier)?.first_position();
3032
3033            assert_items_eq!(linked_chunk, [-] ['a'] [-] ['b', 'c'] [] ['d', 'e', 'f']);
3034
3035            assert_eq!(
3036                linked_chunk.updates().unwrap().take(),
3037                &[
3038                    NewItemsChunk {
3039                        previous: Some(ChunkIdentifier(5)),
3040                        new: ChunkIdentifier(6),
3041                        next: Some(ChunkIdentifier(1)),
3042                    },
3043                    RemoveChunk(ChunkIdentifier(5)),
3044                ]
3045            );
3046
3047            linked_chunk.insert_gap_at((), position)?;
3048
3049            assert_items_eq!(linked_chunk, [-] ['a'] [-] ['b', 'c'] [-] [] ['d', 'e', 'f']);
3050            assert_eq!(
3051                linked_chunk.updates().unwrap().take(),
3052                &[NewGapChunk {
3053                    previous: Some(ChunkIdentifier(3)),
3054                    new: ChunkIdentifier(7),
3055                    next: Some(ChunkIdentifier(6)),
3056                    gap: (),
3057                }]
3058            );
3059        }
3060
3061        // Insert in a chunk that does not exist.
3062        {
3063            assert_matches!(
3064                linked_chunk.insert_items_at(Position(ChunkIdentifier(128), 0), ['u', 'v'],),
3065                Err(Error::InvalidChunkIdentifier { identifier: ChunkIdentifier(128) })
3066            );
3067            assert!(linked_chunk.updates().unwrap().take().is_empty());
3068        }
3069
3070        // Insert in a chunk that exists, but at an item that does not exist.
3071        {
3072            assert_matches!(
3073                linked_chunk.insert_items_at(Position(ChunkIdentifier(0), 128), ['u', 'v'],),
3074                Err(Error::InvalidItemIndex { index: 128 })
3075            );
3076            assert!(linked_chunk.updates().unwrap().take().is_empty());
3077        }
3078
3079        // Insert in an existing gap.
3080        {
3081            // It is impossible to get the item position inside a gap. It's only possible if
3082            // the item position is crafted by hand or is outdated.
3083            let position_of_a_gap = Position(ChunkIdentifier(2), 0);
3084            assert_matches!(
3085                linked_chunk.insert_gap_at((), position_of_a_gap),
3086                Err(Error::ChunkIsAGap { identifier: ChunkIdentifier(2) })
3087            );
3088            assert!(linked_chunk.updates().unwrap().take().is_empty());
3089        }
3090
3091        assert_eq!(linked_chunk.num_items(), 6);
3092
3093        Ok(())
3094    }
3095
3096    #[test]
3097    fn test_replace_gap_at_middle() -> Result<(), Error> {
3098        use super::Update::*;
3099
3100        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3101
3102        // Ignore initial update.
3103        let _ = linked_chunk.updates().unwrap().take();
3104
3105        linked_chunk.push_items_back(['a', 'b']);
3106        linked_chunk.push_gap_back(());
3107        linked_chunk.push_items_back(['l', 'm']);
3108        assert_items_eq!(linked_chunk, ['a', 'b'] [-] ['l', 'm']);
3109        assert_eq!(
3110            linked_chunk.updates().unwrap().take(),
3111            &[
3112                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b'] },
3113                NewGapChunk {
3114                    previous: Some(ChunkIdentifier(0)),
3115                    new: ChunkIdentifier(1),
3116                    next: None,
3117                    gap: (),
3118                },
3119                NewItemsChunk {
3120                    previous: Some(ChunkIdentifier(1)),
3121                    new: ChunkIdentifier(2),
3122                    next: None,
3123                },
3124                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['l', 'm'] }
3125            ]
3126        );
3127
3128        // Replace a gap in the middle of the linked chunk.
3129        let gap_identifier = linked_chunk.chunk_identifier(Chunk::is_gap).unwrap();
3130        assert_eq!(gap_identifier, ChunkIdentifier(1));
3131
3132        let new_chunk = linked_chunk.replace_gap_at(['d', 'e', 'f', 'g', 'h'], gap_identifier)?;
3133        assert_eq!(new_chunk.identifier(), ChunkIdentifier(3));
3134        assert_items_eq!(
3135            linked_chunk,
3136            ['a', 'b'] ['d', 'e', 'f'] ['g', 'h'] ['l', 'm']
3137        );
3138        assert_eq!(
3139            linked_chunk.updates().unwrap().take(),
3140            &[
3141                NewItemsChunk {
3142                    previous: Some(ChunkIdentifier(1)),
3143                    new: ChunkIdentifier(3),
3144                    next: Some(ChunkIdentifier(2)),
3145                },
3146                PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['d', 'e', 'f'] },
3147                NewItemsChunk {
3148                    previous: Some(ChunkIdentifier(3)),
3149                    new: ChunkIdentifier(4),
3150                    next: Some(ChunkIdentifier(2)),
3151                },
3152                PushItems { at: Position(ChunkIdentifier(4), 0), items: vec!['g', 'h'] },
3153                RemoveChunk(ChunkIdentifier(1)),
3154            ]
3155        );
3156
3157        assert_eq!(linked_chunk.num_items(), 9);
3158
3159        Ok(())
3160    }
3161
3162    #[test]
3163    fn test_replace_gap_at_end() -> Result<(), Error> {
3164        use super::Update::*;
3165
3166        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3167
3168        // Ignore initial update.
3169        let _ = linked_chunk.updates().unwrap().take();
3170
3171        linked_chunk.push_items_back(['a', 'b']);
3172        linked_chunk.push_gap_back(());
3173        assert_items_eq!(linked_chunk, ['a', 'b'] [-]);
3174        assert_eq!(
3175            linked_chunk.updates().unwrap().take(),
3176            &[
3177                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b'] },
3178                NewGapChunk {
3179                    previous: Some(ChunkIdentifier(0)),
3180                    new: ChunkIdentifier(1),
3181                    next: None,
3182                    gap: (),
3183                },
3184            ]
3185        );
3186
3187        // Replace a gap at the end of the linked chunk.
3188        let gap_identifier = linked_chunk.chunk_identifier(Chunk::is_gap).unwrap();
3189        assert_eq!(gap_identifier, ChunkIdentifier(1));
3190
3191        let new_chunk = linked_chunk.replace_gap_at(['w', 'x', 'y', 'z'], gap_identifier)?;
3192        assert_eq!(new_chunk.identifier(), ChunkIdentifier(2));
3193        assert_items_eq!(
3194            linked_chunk,
3195            ['a', 'b'] ['w', 'x', 'y'] ['z']
3196        );
3197        assert_eq!(
3198            linked_chunk.updates().unwrap().take(),
3199            &[
3200                NewItemsChunk {
3201                    previous: Some(ChunkIdentifier(1)),
3202                    new: ChunkIdentifier(2),
3203                    next: None,
3204                },
3205                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['w', 'x', 'y'] },
3206                NewItemsChunk {
3207                    previous: Some(ChunkIdentifier(2)),
3208                    new: ChunkIdentifier(3),
3209                    next: None,
3210                },
3211                PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['z'] },
3212                RemoveChunk(ChunkIdentifier(1)),
3213            ]
3214        );
3215
3216        assert_eq!(linked_chunk.num_items(), 6);
3217
3218        Ok(())
3219    }
3220
3221    #[test]
3222    fn test_replace_gap_at_beginning() -> Result<(), Error> {
3223        use super::Update::*;
3224
3225        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3226
3227        // Ignore initial update.
3228        let _ = linked_chunk.updates().unwrap().take();
3229
3230        linked_chunk.push_items_back(['a', 'b']);
3231        assert_items_eq!(linked_chunk, ['a', 'b']);
3232        assert_eq!(
3233            linked_chunk.updates().unwrap().take(),
3234            &[PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b'] },]
3235        );
3236
3237        // Replace a gap at the beginning of the linked chunk.
3238        let position_of_a = linked_chunk.item_position(|item| *item == 'a').unwrap();
3239        linked_chunk.insert_gap_at((), position_of_a).unwrap();
3240        assert_items_eq!(
3241            linked_chunk,
3242            [-] ['a', 'b']
3243        );
3244        assert_eq!(
3245            linked_chunk.updates().unwrap().take(),
3246            &[NewGapChunk {
3247                previous: None,
3248                new: ChunkIdentifier(1),
3249                next: Some(ChunkIdentifier(0)),
3250                gap: (),
3251            }]
3252        );
3253
3254        let gap_identifier = linked_chunk.chunk_identifier(Chunk::is_gap).unwrap();
3255        assert_eq!(gap_identifier, ChunkIdentifier(1));
3256
3257        let new_chunk = linked_chunk.replace_gap_at(['x'], gap_identifier)?;
3258        assert_eq!(new_chunk.identifier(), ChunkIdentifier(2));
3259        assert_items_eq!(
3260            linked_chunk,
3261            ['x'] ['a', 'b']
3262        );
3263        assert_eq!(
3264            linked_chunk.updates().unwrap().take(),
3265            &[
3266                NewItemsChunk {
3267                    previous: Some(ChunkIdentifier(1)),
3268                    new: ChunkIdentifier(2),
3269                    next: Some(ChunkIdentifier(0)),
3270                },
3271                PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['x'] },
3272                RemoveChunk(ChunkIdentifier(1)),
3273            ]
3274        );
3275
3276        assert_eq!(linked_chunk.num_items(), 3);
3277
3278        Ok(())
3279    }
3280
3281    #[test]
3282    fn test_remove_empty_chunk_at() -> Result<(), Error> {
3283        use super::Update::*;
3284
3285        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3286
3287        // Ignore initial update.
3288        let _ = linked_chunk.updates().unwrap().take();
3289
3290        linked_chunk.insert_gap_at((), Position(ChunkIdentifier(0), 0)).unwrap();
3291        linked_chunk.push_items_back(['a', 'b']);
3292        linked_chunk.push_gap_back(());
3293        linked_chunk.push_items_back(['l', 'm']);
3294        linked_chunk.push_gap_back(());
3295        assert_items_eq!(linked_chunk, [-] ['a', 'b'] [-] ['l', 'm'] [-]);
3296        assert_eq!(
3297            linked_chunk.updates().unwrap().take(),
3298            &[
3299                NewGapChunk {
3300                    previous: None,
3301                    new: ChunkIdentifier(1),
3302                    next: Some(ChunkIdentifier(0)),
3303                    gap: (),
3304                },
3305                PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b'] },
3306                NewGapChunk {
3307                    previous: Some(ChunkIdentifier(0)),
3308                    new: ChunkIdentifier(2),
3309                    next: None,
3310                    gap: (),
3311                },
3312                NewItemsChunk {
3313                    previous: Some(ChunkIdentifier(2)),
3314                    new: ChunkIdentifier(3),
3315                    next: None,
3316                },
3317                PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['l', 'm'] },
3318                NewGapChunk {
3319                    previous: Some(ChunkIdentifier(3)),
3320                    new: ChunkIdentifier(4),
3321                    next: None,
3322                    gap: (),
3323                },
3324            ]
3325        );
3326
3327        // Try to remove a chunk that's not empty.
3328        let err = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(0)).unwrap_err();
3329        assert_matches!(err, Error::RemovingNonEmptyItemsChunk { .. });
3330
3331        // Try to remove an unknown gap chunk.
3332        let err = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(42)).unwrap_err();
3333        assert_matches!(err, Error::InvalidChunkIdentifier { .. });
3334
3335        // Remove the gap in the middle.
3336        let maybe_next = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(2)).unwrap();
3337        let next = maybe_next.unwrap();
3338        // The next insert position at the start of the next chunk.
3339        assert_eq!(next.chunk_identifier(), ChunkIdentifier(3));
3340        assert_eq!(next.index(), 0);
3341        assert_items_eq!(linked_chunk, [-] ['a', 'b'] ['l', 'm'] [-]);
3342        assert_eq!(linked_chunk.updates().unwrap().take(), &[RemoveChunk(ChunkIdentifier(2))]);
3343
3344        // Remove the gap at the end.
3345        let next = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(4)).unwrap();
3346        // It was the last chunk, so there's no next insert position.
3347        assert!(next.is_none());
3348        assert_items_eq!(linked_chunk, [-] ['a', 'b'] ['l', 'm']);
3349        assert_eq!(linked_chunk.updates().unwrap().take(), &[RemoveChunk(ChunkIdentifier(4))]);
3350
3351        // Remove the gap at the beginning.
3352        let maybe_next = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(1)).unwrap();
3353        let next = maybe_next.unwrap();
3354        assert_eq!(next.chunk_identifier(), ChunkIdentifier(0));
3355        assert_eq!(next.index(), 0);
3356        assert_items_eq!(linked_chunk, ['a', 'b'] ['l', 'm']);
3357        assert_eq!(linked_chunk.updates().unwrap().take(), &[RemoveChunk(ChunkIdentifier(1))]);
3358
3359        Ok(())
3360    }
3361
3362    #[test]
3363    fn test_remove_empty_last_chunk() {
3364        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3365
3366        // Ignore initial update.
3367        let _ = linked_chunk.updates().unwrap().take();
3368
3369        assert_items_eq!(linked_chunk, []);
3370        assert!(linked_chunk.updates().unwrap().take().is_empty());
3371
3372        // Try to remove the first chunk.
3373        let err = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(0)).unwrap_err();
3374        assert_matches!(err, Error::RemovingLastChunk);
3375    }
3376
3377    #[test]
3378    fn test_chunk_item_positions() {
3379        let mut linked_chunk = LinkedChunk::<3, char, ()>::new();
3380        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e']);
3381        linked_chunk.push_gap_back(());
3382        linked_chunk.push_items_back(['f']);
3383
3384        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e'] [-] ['f']);
3385
3386        let mut iterator = linked_chunk.chunks();
3387
3388        // First chunk.
3389        {
3390            let chunk = iterator.next().unwrap();
3391            assert_eq!(chunk.first_position(), Position(ChunkIdentifier(0), 0));
3392            assert_eq!(chunk.last_position(), Position(ChunkIdentifier(0), 2));
3393        }
3394
3395        // Second chunk.
3396        {
3397            let chunk = iterator.next().unwrap();
3398            assert_eq!(chunk.first_position(), Position(ChunkIdentifier(1), 0));
3399            assert_eq!(chunk.last_position(), Position(ChunkIdentifier(1), 1));
3400        }
3401
3402        // Gap.
3403        {
3404            let chunk = iterator.next().unwrap();
3405            assert_eq!(chunk.first_position(), Position(ChunkIdentifier(2), 0));
3406            assert_eq!(chunk.last_position(), Position(ChunkIdentifier(2), 0));
3407        }
3408
3409        // Last chunk.
3410        {
3411            let chunk = iterator.next().unwrap();
3412            assert_eq!(chunk.first_position(), Position(ChunkIdentifier(3), 0));
3413            assert_eq!(chunk.last_position(), Position(ChunkIdentifier(3), 0));
3414        }
3415    }
3416
3417    #[test]
3418    fn test_is_first_and_last_chunk() {
3419        let mut linked_chunk = LinkedChunk::<3, char, ()>::new();
3420
3421        let mut chunks = linked_chunk.chunks().peekable();
3422        assert!(chunks.peek().unwrap().is_first_chunk());
3423        assert!(chunks.next().unwrap().is_last_chunk());
3424        assert!(chunks.next().is_none());
3425
3426        linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']);
3427
3428        let mut chunks = linked_chunk.chunks().peekable();
3429        assert!(chunks.next().unwrap().is_first_chunk());
3430        assert!(chunks.peek().unwrap().is_first_chunk().not());
3431        assert!(chunks.next().unwrap().is_last_chunk().not());
3432        assert!(chunks.next().unwrap().is_last_chunk());
3433        assert!(chunks.next().is_none());
3434    }
3435
3436    // Test `LinkedChunk::clear`. This test creates a `LinkedChunk` with `new` to
3437    // avoid creating too much confusion with `Update`s. The next test
3438    // `test_clear_emit_an_update_clear` uses `new_with_update_history` and only
3439    // test `Update::Clear`.
3440    #[test]
3441    fn test_clear() {
3442        let mut linked_chunk = LinkedChunk::<3, Arc<char>, Arc<()>>::new();
3443
3444        let item = Arc::new('a');
3445        let gap = Arc::new(());
3446
3447        linked_chunk.push_items_back([
3448            item.clone(),
3449            item.clone(),
3450            item.clone(),
3451            item.clone(),
3452            item.clone(),
3453        ]);
3454        linked_chunk.push_gap_back(gap.clone());
3455        linked_chunk.push_items_back([item.clone()]);
3456
3457        assert_eq!(Arc::strong_count(&item), 7);
3458        assert_eq!(Arc::strong_count(&gap), 2);
3459        assert_eq!(linked_chunk.num_items(), 6);
3460        assert_eq!(linked_chunk.chunk_identifier_generator.next.load(Ordering::SeqCst), 3);
3461
3462        // Now, we can clear the linked chunk and see what happens.
3463        linked_chunk.clear();
3464
3465        assert_eq!(Arc::strong_count(&item), 1);
3466        assert_eq!(Arc::strong_count(&gap), 1);
3467        assert_eq!(linked_chunk.num_items(), 0);
3468        assert_eq!(linked_chunk.chunk_identifier_generator.next.load(Ordering::SeqCst), 0);
3469    }
3470
3471    #[test]
3472    fn test_clear_emit_an_update_clear() {
3473        use super::Update::*;
3474
3475        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3476
3477        assert_eq!(
3478            linked_chunk.updates().unwrap().take(),
3479            &[NewItemsChunk {
3480                previous: None,
3481                new: ChunkIdentifierGenerator::FIRST_IDENTIFIER,
3482                next: None
3483            }]
3484        );
3485
3486        linked_chunk.clear();
3487
3488        assert_eq!(
3489            linked_chunk.updates().unwrap().take(),
3490            &[
3491                Clear,
3492                NewItemsChunk {
3493                    previous: None,
3494                    new: ChunkIdentifierGenerator::FIRST_IDENTIFIER,
3495                    next: None
3496                }
3497            ]
3498        );
3499    }
3500
3501    #[test]
3502    fn test_replace_item() {
3503        use super::Update::*;
3504
3505        let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3506
3507        linked_chunk.push_items_back(['a', 'b', 'c']);
3508        linked_chunk.push_gap_back(());
3509        // Sanity check.
3510        assert_items_eq!(linked_chunk, ['a', 'b', 'c'] [-]);
3511
3512        // Drain previous updates.
3513        let _ = linked_chunk.updates().unwrap().take();
3514
3515        // Replace item in bounds.
3516        linked_chunk.replace_item_at(Position(ChunkIdentifier(0), 1), 'B').unwrap();
3517        assert_items_eq!(linked_chunk, ['a', 'B', 'c'] [-]);
3518
3519        assert_eq!(
3520            linked_chunk.updates().unwrap().take(),
3521            &[ReplaceItem { at: Position(ChunkIdentifier(0), 1), item: 'B' }]
3522        );
3523
3524        // Attempt to replace out-of-bounds.
3525        assert_matches!(
3526            linked_chunk.replace_item_at(Position(ChunkIdentifier(0), 3), 'Z'),
3527            Err(Error::InvalidItemIndex { index: 3 })
3528        );
3529
3530        // Attempt to replace gap.
3531        assert_matches!(
3532            linked_chunk.replace_item_at(Position(ChunkIdentifier(1), 0), 'Z'),
3533            Err(Error::ChunkIsAGap { .. })
3534        );
3535    }
3536
3537    #[test]
3538    fn test_lazy_previous() {
3539        use std::marker::PhantomData;
3540
3541        use super::{Ends, ObservableUpdates, Update::*};
3542
3543        // Imagine the linked chunk is lazily loaded.
3544        let first_chunk_identifier = ChunkIdentifier(0);
3545        let mut first_loaded_chunk = Chunk::new_items_leaked(ChunkIdentifier(1));
3546        unsafe { first_loaded_chunk.as_mut() }.lazy_previous = Some(first_chunk_identifier);
3547
3548        let mut linked_chunk = LinkedChunk::<3, char, ()> {
3549            links: Ends { first: first_loaded_chunk, last: None },
3550            chunk_identifier_generator:
3551                ChunkIdentifierGenerator::new_from_previous_chunk_identifier(ChunkIdentifier(1)),
3552            updates: Some(ObservableUpdates::new()),
3553            marker: PhantomData,
3554        };
3555
3556        // Insert items in the first loaded chunk (chunk 1), with an overflow to a new
3557        // chunk.
3558        {
3559            linked_chunk.push_items_back(['a', 'b', 'c', 'd']);
3560
3561            assert_items_eq!(linked_chunk, ['a', 'b', 'c']['d']);
3562
3563            // Assert where `lazy_previous` is set.
3564            {
3565                let mut chunks = linked_chunk.chunks();
3566
3567                assert_matches!(chunks.next(), Some(chunk) => {
3568                    assert_eq!(chunk.identifier(), 1);
3569                    assert_eq!(chunk.lazy_previous, Some(ChunkIdentifier(0)));
3570                });
3571                assert_matches!(chunks.next(), Some(chunk) => {
3572                    assert_eq!(chunk.identifier(), 2);
3573                    assert!(chunk.lazy_previous.is_none());
3574                });
3575                assert!(chunks.next().is_none());
3576            }
3577
3578            // In the updates, we observe nothing else than the usual bits.
3579            assert_eq!(
3580                linked_chunk.updates().unwrap().take(),
3581                &[
3582                    PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['a', 'b', 'c'] },
3583                    NewItemsChunk {
3584                        previous: Some(ChunkIdentifier(1)),
3585                        new: ChunkIdentifier(2),
3586                        next: None,
3587                    },
3588                    PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['d'] }
3589                ]
3590            );
3591        }
3592
3593        // Now insert a gap at the head of the loaded linked chunk.
3594        {
3595            linked_chunk.insert_gap_at((), Position(ChunkIdentifier(1), 0)).unwrap();
3596
3597            assert_items_eq!(linked_chunk, [-] ['a', 'b', 'c'] ['d']);
3598
3599            // Assert where `lazy_previous` is set.
3600            {
3601                let mut chunks = linked_chunk.chunks();
3602
3603                assert_matches!(chunks.next(), Some(chunk) => {
3604                    assert_eq!(chunk.identifier(), 3);
3605                    // `lazy_previous` has moved here!
3606                    assert_eq!(chunk.lazy_previous, Some(ChunkIdentifier(0)));
3607                });
3608                assert_matches!(chunks.next(), Some(chunk) => {
3609                    assert_eq!(chunk.identifier(), 1);
3610                    // `lazy_previous` has moved from here.
3611                    assert!(chunk.lazy_previous.is_none());
3612                });
3613                assert_matches!(chunks.next(), Some(chunk) => {
3614                    assert_eq!(chunk.identifier(), 2);
3615                    assert!(chunk.lazy_previous.is_none());
3616                });
3617                assert!(chunks.next().is_none());
3618            }
3619
3620            // In the updates, we observe that the new gap **has** a previous chunk!
3621            assert_eq!(
3622                linked_chunk.updates().unwrap().take(),
3623                &[NewGapChunk {
3624                    // 0 is the lazy, not-loaded-yet chunk.
3625                    previous: Some(ChunkIdentifier(0)),
3626                    new: ChunkIdentifier(3),
3627                    next: Some(ChunkIdentifier(1)),
3628                    gap: ()
3629                }]
3630            );
3631        }
3632
3633        // Next, replace the gap by items to see how it reacts to unlink.
3634        {
3635            linked_chunk.replace_gap_at(['w', 'x', 'y', 'z'], ChunkIdentifier(3)).unwrap();
3636
3637            assert_items_eq!(linked_chunk, ['w', 'x', 'y'] ['z'] ['a', 'b', 'c'] ['d']);
3638
3639            // Assert where `lazy_previous` is set.
3640            {
3641                let mut chunks = linked_chunk.chunks();
3642
3643                assert_matches!(chunks.next(), Some(chunk) => {
3644                    assert_eq!(chunk.identifier(), 4);
3645                    // `lazy_previous` has moved here!
3646                    assert_eq!(chunk.lazy_previous, Some(ChunkIdentifier(0)));
3647                });
3648                assert_matches!(chunks.next(), Some(chunk) => {
3649                    assert_eq!(chunk.identifier(), 5);
3650                    assert!(chunk.lazy_previous.is_none());
3651                });
3652                assert_matches!(chunks.next(), Some(chunk) => {
3653                    assert_eq!(chunk.identifier(), 1);
3654                    assert!(chunk.lazy_previous.is_none());
3655                });
3656                assert_matches!(chunks.next(), Some(chunk) => {
3657                    assert_eq!(chunk.identifier(), 2);
3658                    assert!(chunk.lazy_previous.is_none());
3659                });
3660                assert!(chunks.next().is_none());
3661            }
3662
3663            // In the updates, we observe nothing than the usual bits.
3664            assert_eq!(
3665                linked_chunk.updates().unwrap().take(),
3666                &[
3667                    // The new chunk is inserted…
3668                    NewItemsChunk {
3669                        previous: Some(ChunkIdentifier(3)),
3670                        new: ChunkIdentifier(4),
3671                        next: Some(ChunkIdentifier(1)),
3672                    },
3673                    // … and new items are pushed in it.
3674                    PushItems { at: Position(ChunkIdentifier(4), 0), items: vec!['w', 'x', 'y'] },
3675                    // Another new chunk is inserted…
3676                    NewItemsChunk {
3677                        previous: Some(ChunkIdentifier(4)),
3678                        new: ChunkIdentifier(5),
3679                        next: Some(ChunkIdentifier(1)),
3680                    },
3681                    // … and new items are pushed in it.
3682                    PushItems { at: Position(ChunkIdentifier(5), 0), items: vec!['z'] },
3683                    // Finally, the gap is removed!
3684                    RemoveChunk(ChunkIdentifier(3)),
3685                ]
3686            );
3687        }
3688
3689        // Finally, let's re-insert a gap to ensure the lazy-previous is set
3690        // correctly. It is similar to the beginning of this test, but this is a
3691        // frequent pattern in how the linked chunk is used.
3692        {
3693            linked_chunk.insert_gap_at((), Position(ChunkIdentifier(4), 0)).unwrap();
3694
3695            assert_items_eq!(linked_chunk, [-] ['w', 'x', 'y'] ['z'] ['a', 'b', 'c'] ['d']);
3696
3697            // Assert where `lazy_previous` is set.
3698            {
3699                let mut chunks = linked_chunk.chunks();
3700
3701                assert_matches!(chunks.next(), Some(chunk) => {
3702                    assert_eq!(chunk.identifier(), 6);
3703                    // `lazy_previous` has moved here!
3704                    assert_eq!(chunk.lazy_previous, Some(ChunkIdentifier(0)));
3705                });
3706                assert_matches!(chunks.next(), Some(chunk) => {
3707                    assert_eq!(chunk.identifier(), 4);
3708                    // `lazy_previous` has moved from here.
3709                    assert!(chunk.lazy_previous.is_none());
3710                });
3711                assert_matches!(chunks.next(), Some(chunk) => {
3712                    assert_eq!(chunk.identifier(), 5);
3713                    assert!(chunk.lazy_previous.is_none());
3714                });
3715                assert_matches!(chunks.next(), Some(chunk) => {
3716                    assert_eq!(chunk.identifier(), 1);
3717                    assert!(chunk.lazy_previous.is_none());
3718                });
3719                assert_matches!(chunks.next(), Some(chunk) => {
3720                    assert_eq!(chunk.identifier(), 2);
3721                    assert!(chunk.lazy_previous.is_none());
3722                });
3723                assert!(chunks.next().is_none());
3724            }
3725
3726            // In the updates, we observe that the new gap **has** a previous chunk!
3727            assert_eq!(
3728                linked_chunk.updates().unwrap().take(),
3729                &[NewGapChunk {
3730                    // 0 is the lazy, not-loaded-yet chunk.
3731                    previous: Some(ChunkIdentifier(0)),
3732                    new: ChunkIdentifier(6),
3733                    next: Some(ChunkIdentifier(4)),
3734                    gap: ()
3735                }]
3736            );
3737        }
3738    }
3739}