yrs/types/
array.rs

1use crate::block::{EmbedPrelim, ItemContent, ItemPtr, Prelim, Unused};
2use crate::block_iter::BlockIter;
3use crate::encoding::read::Error;
4use crate::encoding::serde::from_any;
5use crate::moving::StickyIndex;
6use crate::transaction::TransactionMut;
7use crate::types::{
8    event_change_set, AsPrelim, Branch, BranchPtr, Change, ChangeSet, DefaultPrelim, In, Out, Path,
9    RootRef, SharedRef, ToJson, TypeRef,
10};
11use crate::{Any, Assoc, DeepObservable, IndexedSequence, Observable, ReadTxn, ID};
12use serde::de::DeserializeOwned;
13use std::borrow::Borrow;
14use std::cell::UnsafeCell;
15use std::collections::HashSet;
16use std::convert::{TryFrom, TryInto};
17use std::iter::FromIterator;
18use std::marker::PhantomData;
19use std::ops::{Deref, DerefMut};
20
21/// A collection used to store data in an indexed sequence structure. This type is internally
22/// implemented as a double linked list, which may squash values inserted directly one after another
23/// into single list node upon transaction commit.
24///
25/// Reading a root-level type as an [ArrayRef] means treating its sequence components as a list, where
26/// every countable element becomes an individual entity:
27///
28/// - JSON-like primitives (booleans, numbers, strings, JSON maps, arrays etc.) are counted
29///   individually.
30/// - Text chunks inserted by [Text] data structure: each character becomes an element of an
31///   array.
32/// - Embedded and binary values: they count as a single element even though they correspond of
33///   multiple bytes.
34///
35/// Like all Yrs shared data types, [ArrayRef] is resistant to the problem of interleaving (situation
36/// when elements inserted one after another may interleave with other peers concurrent inserts
37/// after merging all updates together). In case of Yrs conflict resolution is solved by using
38/// unique document id to determine correct and consistent ordering.
39///
40/// # Example
41///
42/// ```rust
43/// use yrs::{Array, Doc, Map, MapPrelim, Transact, Any, any};
44/// use yrs::types::ToJson;
45///
46/// let doc = Doc::new();
47/// let array = doc.get_or_insert_array("array");
48/// let mut txn = doc.transact_mut();
49///
50/// // insert single scalar value
51/// array.insert(&mut txn, 0, "value");
52/// array.remove_range(&mut txn, 0, 1);
53///
54/// assert_eq!(array.len(&txn), 0);
55///
56/// // insert multiple values at once
57/// array.insert_range(&mut txn, 0, ["a", "b", "c"]);
58/// assert_eq!(array.len(&txn), 3);
59///
60/// // get value
61/// let value = array.get(&txn, 1);
62/// assert_eq!(value, Some("b".into()));
63///
64/// // insert nested shared types
65/// let map = array.insert(&mut txn, 1, MapPrelim::from([("key1", "value1")]));
66/// map.insert(&mut txn, "key2", "value2");
67///
68/// assert_eq!(array.to_json(&txn), any!([
69///   "a",
70///   { "key1": "value1", "key2": "value2" },
71///   "b",
72///   "c"
73/// ]));
74/// ```
75#[repr(transparent)]
76#[derive(Debug, Clone)]
77pub struct ArrayRef(BranchPtr);
78
79impl RootRef for ArrayRef {
80    fn type_ref() -> TypeRef {
81        TypeRef::Array
82    }
83}
84impl SharedRef for ArrayRef {}
85impl Array for ArrayRef {}
86impl IndexedSequence for ArrayRef {}
87
88#[cfg(feature = "weak")]
89impl crate::Quotable for ArrayRef {}
90
91impl ToJson for ArrayRef {
92    fn to_json<T: ReadTxn>(&self, txn: &T) -> Any {
93        let mut walker = BlockIter::new(self.0);
94        let len = self.0.len();
95        let mut buf = vec![Out::default(); len as usize];
96        let read = walker.slice(txn, &mut buf);
97        if read == len {
98            let res = buf.into_iter().map(|v| v.to_json(txn)).collect();
99            Any::Array(res)
100        } else {
101            panic!(
102                "Defect: Array::to_json didn't read all elements ({}/{})",
103                read, len
104            )
105        }
106    }
107}
108
109impl Eq for ArrayRef {}
110impl PartialEq for ArrayRef {
111    fn eq(&self, other: &Self) -> bool {
112        self.0.id() == other.0.id()
113    }
114}
115
116impl AsRef<Branch> for ArrayRef {
117    fn as_ref(&self) -> &Branch {
118        self.0.deref()
119    }
120}
121
122impl DeepObservable for ArrayRef {}
123impl Observable for ArrayRef {
124    type Event = ArrayEvent;
125}
126
127impl TryFrom<ItemPtr> for ArrayRef {
128    type Error = ItemPtr;
129
130    fn try_from(value: ItemPtr) -> Result<Self, Self::Error> {
131        if let Some(branch) = value.clone().as_branch() {
132            Ok(ArrayRef::from(branch))
133        } else {
134            Err(value)
135        }
136    }
137}
138
139impl TryFrom<Out> for ArrayRef {
140    type Error = Out;
141
142    fn try_from(value: Out) -> Result<Self, Self::Error> {
143        match value {
144            Out::YArray(value) => Ok(value),
145            other => Err(other),
146        }
147    }
148}
149
150impl AsPrelim for ArrayRef {
151    type Prelim = ArrayPrelim;
152
153    fn as_prelim<T: ReadTxn>(&self, txn: &T) -> Self::Prelim {
154        let mut prelim = Vec::with_capacity(self.len(txn) as usize);
155        for value in self.iter(txn) {
156            prelim.push(value.as_prelim(txn));
157        }
158        ArrayPrelim(prelim)
159    }
160}
161
162impl DefaultPrelim for ArrayRef {
163    type Prelim = ArrayPrelim;
164
165    #[inline]
166    fn default_prelim() -> Self::Prelim {
167        ArrayPrelim::default()
168    }
169}
170
171pub trait Array: AsRef<Branch> + Sized {
172    /// Returns a number of elements stored in current array.
173    fn len<T: ReadTxn>(&self, _txn: &T) -> u32 {
174        self.as_ref().len()
175    }
176
177    /// Inserts a `value` at the given `index`. Inserting at index `0` is equivalent to prepending
178    /// current array with given `value`, while inserting at array length is equivalent to appending
179    /// that value at the end of it.
180    ///
181    /// Returns a reference to an integrated preliminary input.
182    ///
183    /// # Panics
184    ///
185    /// This method will panic if provided `index` is greater than the current length of an [ArrayRef].
186    fn insert<V>(&self, txn: &mut TransactionMut, index: u32, value: V) -> V::Return
187    where
188        V: Prelim,
189    {
190        let mut walker = BlockIter::new(BranchPtr::from(self.as_ref()));
191        if walker.try_forward(txn, index) {
192            let ptr = walker
193                .insert_contents(txn, value)
194                .expect("cannot insert empty value");
195            if let Ok(integrated) = ptr.try_into() {
196                integrated
197            } else {
198                panic!("Defect: unexpected integrated type")
199            }
200        } else {
201            panic!("Index {} is outside of the range of an array", index);
202        }
203    }
204
205    /// Inserts multiple `values` at the given `index`. Inserting at index `0` is equivalent to
206    /// prepending current array with given `values`, while inserting at array length is equivalent
207    /// to appending that value at the end of it.
208    ///
209    /// # Panics
210    ///
211    /// This method will panic if provided `index` is greater than the current length of an [ArrayRef].
212    fn insert_range<T, V>(&self, txn: &mut TransactionMut, index: u32, values: T)
213    where
214        T: IntoIterator<Item = V>,
215        V: Into<Any>,
216    {
217        let prelim = RangePrelim::new(values);
218        if !prelim.is_empty() {
219            self.insert(txn, index, prelim);
220        }
221    }
222
223    /// Inserts given `value` at the end of the current array.
224    ///
225    /// Returns a reference to an integrated preliminary input.
226    fn push_back<V>(&self, txn: &mut TransactionMut, value: V) -> V::Return
227    where
228        V: Prelim,
229    {
230        let len = self.len(txn);
231        self.insert(txn, len, value)
232    }
233
234    /// Inserts given `value` at the beginning of the current array.
235    ///
236    /// Returns a reference to an integrated preliminary input.
237    fn push_front<V>(&self, txn: &mut TransactionMut, content: V) -> V::Return
238    where
239        V: Prelim,
240    {
241        self.insert(txn, 0, content)
242    }
243
244    /// Removes a single element at provided `index`.
245    fn remove(&self, txn: &mut TransactionMut, index: u32) {
246        self.remove_range(txn, index, 1)
247    }
248
249    /// Removes a range of elements from current array, starting at given `index` up until
250    /// a particular number described by `len` has been deleted. This method panics in case when
251    /// not all expected elements were removed (due to insufficient number of elements in an array)
252    /// or `index` is outside of the bounds of an array.
253    fn remove_range(&self, txn: &mut TransactionMut, index: u32, len: u32) {
254        let mut walker = BlockIter::new(BranchPtr::from(self.as_ref()));
255        if walker.try_forward(txn, index) {
256            walker.delete(txn, len)
257        } else {
258            panic!("Index {} is outside of the range of an array", index);
259        }
260    }
261
262    /// Retrieves a value stored at a given `index`. Returns `None` when provided index was out
263    /// of the range of a current array.
264    fn get<T: ReadTxn>(&self, txn: &T, index: u32) -> Option<Out> {
265        let mut walker = BlockIter::new(BranchPtr::from(self.as_ref()));
266        if walker.try_forward(txn, index) {
267            walker.read_value(txn)
268        } else {
269            None
270        }
271    }
272
273    /// Returns a value stored under a given `index` within current map, deserializing it into
274    /// expected type if found. If value was not found, the `Any::Null` will be substituted and
275    /// deserialized instead (i.e. into instance of `Option` type, if so desired).
276    ///
277    /// # Example
278    ///
279    /// ```rust
280    /// use yrs::{Doc, In, Array, MapPrelim, Transact, WriteTxn};
281    ///
282    /// let doc = Doc::new();
283    /// let mut txn = doc.transact_mut();
284    /// let array = txn.get_or_insert_array("array");
285    ///
286    /// // insert a multi-nested shared refs
287    /// let alice = array.insert(&mut txn, 0, MapPrelim::from([
288    ///   ("name", In::from("Alice")),
289    ///   ("age", In::from(30)),
290    ///   ("address", MapPrelim::from([
291    ///     ("city", In::from("London")),
292    ///     ("street", In::from("Baker st.")),
293    ///   ]).into())
294    /// ]));
295    ///
296    /// // define Rust types to map from the shared refs
297    ///
298    /// #[derive(Debug, PartialEq, serde::Deserialize)]
299    /// struct Person {
300    ///   name: String,
301    ///   age: u32,
302    ///   address: Option<Address>,
303    /// }
304    ///
305    /// #[derive(Debug, PartialEq, serde::Deserialize)]
306    /// struct Address {
307    ///   city: String,
308    ///   street: String,
309    /// }
310    ///
311    /// // retrieve and deserialize the value across multiple shared refs
312    /// let alice: Person = array.get_as(&txn, 0).unwrap();
313    /// assert_eq!(alice, Person {
314    ///   name: "Alice".to_string(),
315    ///   age: 30,
316    ///   address: Some(Address {
317    ///     city: "London".to_string(),
318    ///     street: "Baker st.".to_string(),
319    ///   })
320    /// });
321    ///
322    /// // try to retrieve value that doesn't exist
323    /// let bob: Option<Person> = array.get_as(&txn, 1).unwrap();
324    /// assert_eq!(bob, None);
325    /// ```
326    fn get_as<T, V>(&self, txn: &T, index: u32) -> Result<V, Error>
327    where
328        T: ReadTxn,
329        V: DeserializeOwned,
330    {
331        let out = self.get(txn, index).unwrap_or(Out::Any(Any::Null));
332        //TODO: we could probably optimize this step by not serializing to intermediate Any value
333        let any = out.to_json(txn);
334        from_any(&any)
335    }
336
337    /// Moves element found at `source` index into `target` index position. Both indexes refer to a
338    /// current state of the document.
339    ///
340    /// # Panics
341    ///
342    /// This method panics if either `source` or `target` indexes are greater than current array's
343    /// length.
344    fn move_to(&self, txn: &mut TransactionMut, source: u32, target: u32) {
345        if source == target || source + 1 == target {
346            // It doesn't make sense to move a range into the same range (it's basically a no-op).
347            return;
348        }
349        let this = BranchPtr::from(self.as_ref());
350        let left = StickyIndex::at(txn, this, source, Assoc::After)
351            .expect("`source` index parameter is beyond the range of an y-array");
352        let mut right = left.clone();
353        right.assoc = Assoc::Before;
354        let mut walker = BlockIter::new(this);
355        if walker.try_forward(txn, target) {
356            walker.insert_move(txn, left, right);
357        } else {
358            panic!(
359                "`target` index parameter {} is outside of the range of an array",
360                target
361            );
362        }
363    }
364
365    /// Moves all elements found within `start`..`end` indexes range (both side inclusive) into
366    /// new position pointed by `target` index. All elements inserted concurrently by other peers
367    /// inside of moved range will be moved as well after synchronization (although it make take
368    /// more than one sync roundtrip to achieve convergence).
369    ///
370    /// `assoc_start`/`assoc_end` flags are used to mark if ranges should include elements that
371    /// might have been inserted concurrently at the edges of the range definition.
372    ///
373    /// Example:
374    /// ```
375    /// use yrs::{Doc, Transact, Array, Assoc};
376    /// let doc = Doc::new();
377    /// let array = doc.get_or_insert_array("array");
378    /// array.insert_range(&mut doc.transact_mut(), 0, [1,2,3,4]);
379    /// // move elements 2 and 3 after the 4
380    /// array.move_range_to(&mut doc.transact_mut(), 1, Assoc::After, 2, Assoc::Before, 4);
381    /// let values: Vec<_> = array.iter(&doc.transact()).collect();
382    /// assert_eq!(values, vec![1.into(), 4.into(), 2.into(), 3.into()]);
383    /// ```
384    /// # Panics
385    ///
386    /// This method panics if either `start`, `end` or `target` indexes are greater than current
387    /// array's length.
388    fn move_range_to(
389        &self,
390        txn: &mut TransactionMut,
391        start: u32,
392        assoc_start: Assoc,
393        end: u32,
394        assoc_end: Assoc,
395        target: u32,
396    ) {
397        if start <= target && target <= end {
398            // It doesn't make sense to move a range into the same range (it's basically a no-op).
399            return;
400        }
401        let this = BranchPtr::from(self.as_ref());
402        let left = StickyIndex::at(txn, this, start, assoc_start)
403            .expect("`start` index parameter is beyond the range of an y-array");
404        let right = StickyIndex::at(txn, this, end + 1, assoc_end)
405            .expect("`end` index parameter is beyond the range of an y-array");
406        let mut walker = BlockIter::new(this);
407        if walker.try_forward(txn, target) {
408            walker.insert_move(txn, left, right);
409        } else {
410            panic!(
411                "`target` index parameter {} is outside of the range of an array",
412                target
413            );
414        }
415    }
416
417    /// Returns an iterator, that can be used to lazely traverse over all values stored in a current
418    /// array.
419    fn iter<'a, T: ReadTxn + 'a>(&self, txn: &'a T) -> ArrayIter<&'a T, T> {
420        ArrayIter::from_ref(self.as_ref(), txn)
421    }
422}
423
424pub struct ArrayIter<B, T>
425where
426    B: Borrow<T>,
427    T: ReadTxn,
428{
429    inner: BlockIter,
430    txn: B,
431    _marker: PhantomData<T>,
432}
433
434impl<T> ArrayIter<T, T>
435where
436    T: Borrow<T> + ReadTxn,
437{
438    pub fn from(array: &ArrayRef, txn: T) -> Self {
439        ArrayIter {
440            inner: BlockIter::new(array.0),
441            txn,
442            _marker: PhantomData::default(),
443        }
444    }
445}
446
447impl<'a, T> ArrayIter<&'a T, T>
448where
449    T: Borrow<T> + ReadTxn,
450{
451    pub fn from_ref(array: &Branch, txn: &'a T) -> Self {
452        ArrayIter {
453            inner: BlockIter::new(BranchPtr::from(array)),
454            txn,
455            _marker: PhantomData::default(),
456        }
457    }
458}
459
460impl<B, T> Iterator for ArrayIter<B, T>
461where
462    B: Borrow<T>,
463    T: ReadTxn,
464{
465    type Item = Out;
466
467    fn next(&mut self) -> Option<Self::Item> {
468        if self.inner.finished() {
469            None
470        } else {
471            let mut buf = [Out::default(); 1];
472            let txn = self.txn.borrow();
473            if self.inner.slice(txn, &mut buf) != 0 {
474                Some(std::mem::replace(&mut buf[0], Out::default()))
475            } else {
476                None
477            }
478        }
479    }
480}
481
482impl From<BranchPtr> for ArrayRef {
483    fn from(inner: BranchPtr) -> Self {
484        ArrayRef(inner)
485    }
486}
487
488/// A preliminary array. It can be used to initialize an [ArrayRef], when it's about to be nested
489/// into another Yrs data collection, such as [Map] or another [ArrayRef].
490#[repr(transparent)]
491#[derive(Debug, Clone, PartialEq, Default)]
492pub struct ArrayPrelim(Vec<In>);
493
494impl Deref for ArrayPrelim {
495    type Target = Vec<In>;
496
497    #[inline]
498    fn deref(&self) -> &Self::Target {
499        &self.0
500    }
501}
502
503impl DerefMut for ArrayPrelim {
504    fn deref_mut(&mut self) -> &mut Self::Target {
505        &mut self.0
506    }
507}
508
509impl From<ArrayPrelim> for In {
510    #[inline]
511    fn from(value: ArrayPrelim) -> Self {
512        In::Array(value)
513    }
514}
515
516impl<T> FromIterator<T> for ArrayPrelim
517where
518    T: Into<In>,
519{
520    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
521        ArrayPrelim(iter.into_iter().map(|v| v.into()).collect())
522    }
523}
524
525impl<I, T> From<I> for ArrayPrelim
526where
527    I: IntoIterator<Item = T>,
528    T: Into<In>,
529{
530    fn from(iter: I) -> Self {
531        ArrayPrelim(iter.into_iter().map(|v| v.into()).collect())
532    }
533}
534
535impl Prelim for ArrayPrelim {
536    type Return = ArrayRef;
537
538    fn into_content(self, _txn: &mut TransactionMut) -> (ItemContent, Option<Self>) {
539        let inner = Branch::new(TypeRef::Array);
540        (ItemContent::Type(inner), Some(self))
541    }
542
543    fn integrate(self, txn: &mut TransactionMut, inner_ref: BranchPtr) {
544        let array = ArrayRef::from(inner_ref);
545        for value in self.0 {
546            array.push_back(txn, value);
547        }
548    }
549}
550
551impl Into<EmbedPrelim<ArrayPrelim>> for ArrayPrelim {
552    #[inline]
553    fn into(self) -> EmbedPrelim<ArrayPrelim> {
554        EmbedPrelim::Shared(self)
555    }
556}
557
558/// Prelim range defines a way to insert multiple elements effectively at once one after another
559/// in an efficient way, provided that these elements correspond to a primitive JSON-like types.
560#[repr(transparent)]
561struct RangePrelim(Vec<Any>);
562
563impl RangePrelim {
564    fn new<I, T>(iter: I) -> Self
565    where
566        I: IntoIterator<Item = T>,
567        T: Into<Any>,
568    {
569        RangePrelim(iter.into_iter().map(|v| v.into()).collect())
570    }
571
572    #[inline]
573    fn is_empty(&self) -> bool {
574        self.0.is_empty()
575    }
576}
577
578impl Prelim for RangePrelim {
579    type Return = Unused;
580
581    fn into_content(self, _txn: &mut TransactionMut) -> (ItemContent, Option<Self>) {
582        (ItemContent::Any(self.0), None)
583    }
584
585    fn integrate(self, _txn: &mut TransactionMut, _inner_ref: BranchPtr) {}
586}
587
588/// Event generated by [ArrayRef::observe] method. Emitted during transaction commit phase.
589pub struct ArrayEvent {
590    pub(crate) current_target: BranchPtr,
591    target: ArrayRef,
592    change_set: UnsafeCell<Option<Box<ChangeSet<Change>>>>,
593}
594
595impl ArrayEvent {
596    pub(crate) fn new(branch_ref: BranchPtr) -> Self {
597        let current_target = branch_ref.clone();
598        ArrayEvent {
599            target: ArrayRef::from(branch_ref),
600            current_target,
601            change_set: UnsafeCell::new(None),
602        }
603    }
604
605    /// Returns an [ArrayRef] instance which emitted this event.
606    pub fn target(&self) -> &ArrayRef {
607        &self.target
608    }
609
610    /// Returns a path from root type down to [ArrayRef] instance which emitted this event.
611    pub fn path(&self) -> Path {
612        Branch::path(self.current_target, self.target.0)
613    }
614
615    /// Returns summary of changes made over corresponding [ArrayRef] collection within
616    /// a bounds of current transaction.
617    pub fn delta(&self, txn: &TransactionMut) -> &[Change] {
618        self.changes(txn).delta.as_slice()
619    }
620
621    /// Returns a collection of block identifiers that have been added within a bounds of
622    /// current transaction.
623    pub fn inserts(&self, txn: &TransactionMut) -> &HashSet<ID> {
624        &self.changes(txn).added
625    }
626
627    /// Returns a collection of block identifiers that have been removed within a bounds of
628    /// current transaction.
629    pub fn removes(&self, txn: &TransactionMut) -> &HashSet<ID> {
630        &self.changes(txn).deleted
631    }
632
633    fn changes(&self, txn: &TransactionMut) -> &ChangeSet<Change> {
634        let change_set = unsafe { self.change_set.get().as_mut().unwrap() };
635        change_set.get_or_insert_with(|| Box::new(event_change_set(txn, self.target.0.start)))
636    }
637}
638
639#[cfg(test)]
640mod test {
641    use crate::block::ClientID;
642    use crate::test_utils::{exchange_updates, run_scenario, RngExt};
643    use crate::types::map::MapPrelim;
644    use crate::types::{Change, DeepObservable, Event, Out, Path, PathSegment, ToJson};
645    use crate::{
646        any, Any, Array, ArrayPrelim, Assoc, Doc, Map, MapRef, Observable, SharedRef, StateVector,
647        Transact, Update, WriteTxn, ID,
648    };
649    use std::collections::{HashMap, HashSet};
650    use std::iter::FromIterator;
651    use std::sync::{Arc, Mutex};
652
653    #[test]
654    fn push_back() {
655        let doc = Doc::with_client_id(1);
656        let a = doc.get_or_insert_array("array");
657        let mut txn = doc.transact_mut();
658
659        a.push_back(&mut txn, "a");
660        a.push_back(&mut txn, "b");
661        a.push_back(&mut txn, "c");
662
663        let actual: Vec<_> = a.iter(&txn).collect();
664        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
665    }
666
667    #[test]
668    fn push_front() {
669        let doc = Doc::with_client_id(1);
670        let a = doc.get_or_insert_array("array");
671        let mut txn = doc.transact_mut();
672
673        a.push_front(&mut txn, "c");
674        a.push_front(&mut txn, "b");
675        a.push_front(&mut txn, "a");
676
677        let actual: Vec<_> = a.iter(&txn).collect();
678        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
679    }
680
681    #[test]
682    fn insert() {
683        let doc = Doc::with_client_id(1);
684        let a = doc.get_or_insert_array("array");
685        let mut txn = doc.transact_mut();
686
687        a.insert(&mut txn, 0, "a");
688        a.insert(&mut txn, 1, "c");
689        a.insert(&mut txn, 1, "b");
690
691        let actual: Vec<_> = a.iter(&txn).collect();
692        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
693    }
694
695    #[test]
696    fn basic() {
697        let d1 = Doc::with_client_id(1);
698        let d2 = Doc::with_client_id(2);
699
700        let a1 = d1.get_or_insert_array("array");
701
702        a1.insert(&mut d1.transact_mut(), 0, "Hi");
703        let update = d1
704            .transact()
705            .encode_state_as_update_v1(&StateVector::default());
706
707        let a2 = d2.get_or_insert_array("array");
708        let mut t2 = d2.transact_mut();
709        t2.apply_update(Update::decode_v1(update.as_slice()).unwrap())
710            .unwrap();
711        let actual: Vec<_> = a2.iter(&t2).collect();
712
713        assert_eq!(actual, vec!["Hi".into()]);
714    }
715
716    #[test]
717    fn len() {
718        let d = Doc::with_client_id(1);
719        let a = d.get_or_insert_array("array");
720
721        {
722            let mut txn = d.transact_mut();
723
724            a.push_back(&mut txn, 0); // len: 1
725            a.push_back(&mut txn, 1); // len: 2
726            a.push_back(&mut txn, 2); // len: 3
727            a.push_back(&mut txn, 3); // len: 4
728
729            a.remove_range(&mut txn, 0, 1); // len: 3
730            a.insert(&mut txn, 0, 0); // len: 4
731
732            assert_eq!(a.len(&txn), 4);
733        }
734        {
735            let mut txn = d.transact_mut();
736            a.remove_range(&mut txn, 1, 1); // len: 3
737            assert_eq!(a.len(&txn), 3);
738
739            a.insert(&mut txn, 1, 1); // len: 4
740            assert_eq!(a.len(&txn), 4);
741
742            a.remove_range(&mut txn, 2, 1); // len: 3
743            assert_eq!(a.len(&txn), 3);
744
745            a.insert(&mut txn, 2, 2); // len: 4
746            assert_eq!(a.len(&txn), 4);
747        }
748
749        let mut txn = d.transact_mut();
750        assert_eq!(a.len(&txn), 4);
751
752        a.remove_range(&mut txn, 1, 1);
753        assert_eq!(a.len(&txn), 3);
754
755        a.insert(&mut txn, 1, 1);
756        assert_eq!(a.len(&txn), 4);
757    }
758
759    #[test]
760    fn remove_insert() {
761        let d1 = Doc::with_client_id(1);
762        let a1 = d1.get_or_insert_array("array");
763
764        let mut t1 = d1.transact_mut();
765        a1.insert(&mut t1, 0, "A");
766        a1.remove_range(&mut t1, 1, 0);
767    }
768
769    #[test]
770    fn insert_3_elements_try_re_get() {
771        let d1 = Doc::with_client_id(1);
772        let d2 = Doc::with_client_id(2);
773        let a1 = d1.get_or_insert_array("array");
774        {
775            let mut t1 = d1.transact_mut();
776
777            a1.push_back(&mut t1, 1);
778            a1.push_back(&mut t1, true);
779            a1.push_back(&mut t1, false);
780            let actual: Vec<_> = a1.iter(&t1).collect();
781            assert_eq!(
782                actual,
783                vec![Out::from(1.0), Out::from(true), Out::from(false)]
784            );
785        }
786
787        exchange_updates(&[&d1, &d2]);
788
789        let a2 = d2.get_or_insert_array("array");
790        let t2 = d2.transact();
791        let actual: Vec<_> = a2.iter(&t2).collect();
792        assert_eq!(
793            actual,
794            vec![Out::from(1.0), Out::from(true), Out::from(false)]
795        );
796    }
797
798    #[test]
799    fn concurrent_insert_with_3_conflicts() {
800        let d1 = Doc::with_client_id(1);
801        let a = d1.get_or_insert_array("array");
802        {
803            let mut txn = d1.transact_mut();
804            a.insert(&mut txn, 0, 0);
805        }
806
807        let d2 = Doc::with_client_id(2);
808        {
809            let mut txn = d1.transact_mut();
810            a.insert(&mut txn, 0, 1);
811        }
812
813        let d3 = Doc::with_client_id(3);
814        {
815            let mut txn = d1.transact_mut();
816            a.insert(&mut txn, 0, 2);
817        }
818
819        exchange_updates(&[&d1, &d2, &d3]);
820
821        let a1 = to_array(&d1);
822        let a2 = to_array(&d2);
823        let a3 = to_array(&d3);
824
825        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
826        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
827    }
828
829    fn to_array(d: &Doc) -> Vec<Out> {
830        let a = d.get_or_insert_array("array");
831        a.iter(&d.transact()).collect()
832    }
833
834    #[test]
835    fn concurrent_insert_remove_with_3_conflicts() {
836        let d1 = Doc::with_client_id(1);
837        {
838            let a = d1.get_or_insert_array("array");
839            let mut txn = d1.transact_mut();
840            a.insert_range(&mut txn, 0, ["x", "y", "z"]);
841        }
842        let d2 = Doc::with_client_id(2);
843        let d3 = Doc::with_client_id(3);
844
845        exchange_updates(&[&d1, &d2, &d3]);
846
847        {
848            // start state: [x,y,z]
849            let a1 = d1.get_or_insert_array("array");
850            let a2 = d2.get_or_insert_array("array");
851            let a3 = d3.get_or_insert_array("array");
852            let mut t1 = d1.transact_mut();
853            let mut t2 = d2.transact_mut();
854            let mut t3 = d3.transact_mut();
855
856            a1.insert(&mut t1, 1, 0); // [x,0,y,z]
857            a2.remove_range(&mut t2, 0, 1); // [y,z]
858            a2.remove_range(&mut t2, 1, 1); // [y]
859            a3.insert(&mut t3, 1, 2); // [x,2,y,z]
860        }
861
862        exchange_updates(&[&d1, &d2, &d3]);
863        // after exchange expected: [0,2,y]
864
865        let a1 = to_array(&d1);
866        let a2 = to_array(&d2);
867        let a3 = to_array(&d3);
868
869        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
870        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
871    }
872
873    #[test]
874    fn insertions_in_late_sync() {
875        let d1 = Doc::with_client_id(1);
876        {
877            let a = d1.get_or_insert_array("array");
878            let mut txn = d1.transact_mut();
879            a.push_back(&mut txn, "x");
880            a.push_back(&mut txn, "y");
881        }
882        let d2 = Doc::with_client_id(2);
883        let d3 = Doc::with_client_id(3);
884
885        exchange_updates(&[&d1, &d2, &d3]);
886
887        {
888            let a1 = d1.get_or_insert_array("array");
889            let a2 = d2.get_or_insert_array("array");
890            let a3 = d3.get_or_insert_array("array");
891            let mut t1 = d1.transact_mut();
892            let mut t2 = d2.transact_mut();
893            let mut t3 = d3.transact_mut();
894
895            a1.insert(&mut t1, 1, "user0");
896            a2.insert(&mut t2, 1, "user1");
897            a3.insert(&mut t3, 1, "user2");
898        }
899
900        exchange_updates(&[&d1, &d2, &d3]);
901
902        let a1 = to_array(&d1);
903        let a2 = to_array(&d2);
904        let a3 = to_array(&d3);
905
906        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
907        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
908    }
909
910    #[test]
911    fn removals_in_late_sync() {
912        let d1 = Doc::with_client_id(1);
913        {
914            let a = d1.get_or_insert_array("array");
915            let mut txn = d1.transact_mut();
916            a.push_back(&mut txn, "x");
917            a.push_back(&mut txn, "y");
918        }
919        let d2 = Doc::with_client_id(2);
920
921        exchange_updates(&[&d1, &d2]);
922
923        {
924            let a1 = d1.get_or_insert_array("array");
925            let a2 = d2.get_or_insert_array("array");
926            let mut t1 = d1.transact_mut();
927            let mut t2 = d2.transact_mut();
928
929            a2.remove_range(&mut t2, 1, 1);
930            a1.remove_range(&mut t1, 0, 2);
931        }
932
933        exchange_updates(&[&d1, &d2]);
934
935        let a1 = to_array(&d1);
936        let a2 = to_array(&d2);
937
938        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
939    }
940
941    #[test]
942    fn insert_then_merge_delete_on_sync() {
943        let d1 = Doc::with_client_id(1);
944        {
945            let a = d1.get_or_insert_array("array");
946            let mut txn = d1.transact_mut();
947            a.push_back(&mut txn, "x");
948            a.push_back(&mut txn, "y");
949            a.push_back(&mut txn, "z");
950        }
951        let d2 = Doc::with_client_id(2);
952
953        exchange_updates(&[&d1, &d2]);
954
955        {
956            let a2 = d2.get_or_insert_array("array");
957            let mut t2 = d2.transact_mut();
958
959            a2.remove_range(&mut t2, 0, 3);
960        }
961
962        exchange_updates(&[&d1, &d2]);
963
964        let a1 = to_array(&d1);
965        let a2 = to_array(&d2);
966
967        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
968    }
969
970    #[test]
971    fn iter_array_containing_types() {
972        let d = Doc::with_client_id(1);
973        let a = d.get_or_insert_array("arr");
974        let mut txn = d.transact_mut();
975        for i in 0..10 {
976            let mut m = HashMap::new();
977            m.insert("value".to_owned(), i);
978            a.push_back(&mut txn, MapPrelim::from_iter(m));
979        }
980
981        for (i, value) in a.iter(&txn).enumerate() {
982            match value {
983                Out::YMap(_) => {
984                    assert_eq!(value.to_json(&txn), any!({"value": (i as f64) }))
985                }
986                _ => panic!("Value of array at index {} was no YMap", i),
987            }
988        }
989    }
990
991    #[test]
992    fn insert_and_remove_events() {
993        let d = Doc::with_client_id(1);
994        let array = d.get_or_insert_array("array");
995        let happened = Arc::new(AtomicBool::new(false));
996        let happened_clone = happened.clone();
997        let _sub = array.observe(move |_, _| {
998            happened_clone.store(true, Ordering::Relaxed);
999        });
1000
1001        {
1002            let mut txn = d.transact_mut();
1003            array.insert_range(&mut txn, 0, [0, 1, 2]);
1004            // txn is committed at the end of this scope
1005        }
1006        assert!(
1007            happened.swap(false, Ordering::Relaxed),
1008            "insert of [0,1,2] should trigger event"
1009        );
1010
1011        {
1012            let mut txn = d.transact_mut();
1013            array.remove_range(&mut txn, 0, 1);
1014            // txn is committed at the end of this scope
1015        }
1016        assert!(
1017            happened.swap(false, Ordering::Relaxed),
1018            "removal of [0] should trigger event"
1019        );
1020
1021        {
1022            let mut txn = d.transact_mut();
1023            array.remove_range(&mut txn, 0, 2);
1024            // txn is committed at the end of this scope
1025        }
1026        assert!(
1027            happened.swap(false, Ordering::Relaxed),
1028            "removal of [1,2] should trigger event"
1029        );
1030    }
1031
1032    #[test]
1033    fn insert_and_remove_event_changes() {
1034        let d1 = Doc::with_client_id(1);
1035        let array = d1.get_or_insert_array("array");
1036        let added = Arc::new(ArcSwapOption::default());
1037        let removed = Arc::new(ArcSwapOption::default());
1038        let delta = Arc::new(ArcSwapOption::default());
1039
1040        let (added_c, removed_c, delta_c) = (added.clone(), removed.clone(), delta.clone());
1041        let _sub = array.observe(move |txn, e| {
1042            added_c.store(Some(Arc::new(e.inserts(txn).clone())));
1043            removed_c.store(Some(Arc::new(e.removes(txn).clone())));
1044            delta_c.store(Some(Arc::new(e.delta(txn).to_vec())));
1045        });
1046
1047        {
1048            let mut txn = d1.transact_mut();
1049            array.push_back(&mut txn, 4);
1050            array.push_back(&mut txn, "dtrn");
1051            // txn is committed at the end of this scope
1052        }
1053        assert_eq!(
1054            added.swap(None),
1055            Some(
1056                HashSet::from([ID::new(ClientID::new(1), 0), ID::new(ClientID::new(1), 1)]).into()
1057            )
1058        );
1059        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
1060        assert_eq!(
1061            delta.swap(None),
1062            Some(
1063                vec![Change::Added(vec![
1064                    Any::Number(4.0).into(),
1065                    Any::String("dtrn".into()).into()
1066                ])]
1067                .into()
1068            )
1069        );
1070
1071        {
1072            let mut txn = d1.transact_mut();
1073            array.remove_range(&mut txn, 0, 1);
1074        }
1075        assert_eq!(added.swap(None), Some(HashSet::new().into()));
1076        assert_eq!(
1077            removed.swap(None),
1078            Some(HashSet::from([ID::new(ClientID::new(1), 0)]).into())
1079        );
1080        assert_eq!(delta.swap(None), Some(vec![Change::Removed(1)].into()));
1081
1082        {
1083            let mut txn = d1.transact_mut();
1084            array.insert(&mut txn, 1, 0.5);
1085        }
1086        assert_eq!(
1087            added.swap(None),
1088            Some(HashSet::from([ID::new(ClientID::new(1), 2)]).into())
1089        );
1090        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
1091        assert_eq!(
1092            delta.swap(None),
1093            Some(
1094                vec![
1095                    Change::Retain(1),
1096                    Change::Added(vec![Any::Number(0.5).into()])
1097                ]
1098                .into()
1099            )
1100        );
1101
1102        let d2 = Doc::with_client_id(2);
1103        let array2 = d2.get_or_insert_array("array");
1104        let (added_c, removed_c, delta_c) = (added.clone(), removed.clone(), delta.clone());
1105        let _sub = array2.observe(move |txn, e| {
1106            added_c.store(Some(e.inserts(txn).clone().into()));
1107            removed_c.store(Some(e.removes(txn).clone().into()));
1108            delta_c.store(Some(e.delta(txn).to_vec().into()));
1109        });
1110
1111        {
1112            let t1 = d1.transact_mut();
1113            let mut t2 = d2.transact_mut();
1114
1115            let sv = t2.state_vector();
1116            let mut encoder = EncoderV1::new();
1117            t1.encode_diff(&sv, &mut encoder);
1118            t2.apply_update(Update::decode_v1(encoder.to_vec().as_slice()).unwrap())
1119                .unwrap();
1120        }
1121
1122        assert_eq!(
1123            added.swap(None),
1124            Some(HashSet::from([ID::new(ClientID::new(1), 1)]).into())
1125        );
1126        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
1127        assert_eq!(
1128            delta.swap(None),
1129            Some(
1130                vec![Change::Added(vec![
1131                    Any::String("dtrn".into()).into(),
1132                    Any::Number(0.5).into(),
1133                ])]
1134                .into()
1135            )
1136        );
1137    }
1138
1139    #[test]
1140    fn target_on_local_and_remote() {
1141        let d1 = Doc::with_client_id(1);
1142        let d2 = Doc::with_client_id(2);
1143        let a1 = d1.get_or_insert_array("array");
1144        let a2 = d2.get_or_insert_array("array");
1145
1146        let c1 = Arc::new(ArcSwapOption::default());
1147        let c1c = c1.clone();
1148        let _s1 = a1.observe(move |_, e| {
1149            c1c.store(Some(e.target().hook().into()));
1150        });
1151        let c2 = Arc::new(ArcSwapOption::default());
1152        let c2c = c2.clone();
1153        let _s2 = a2.observe(move |_, e| {
1154            c2c.store(Some(e.target().hook().into()));
1155        });
1156
1157        {
1158            let mut t1 = d1.transact_mut();
1159            a1.insert_range(&mut t1, 0, [1, 2]);
1160        }
1161        exchange_updates(&[&d1, &d2]);
1162
1163        assert_eq!(c1.swap(None), Some(Arc::new(a1.hook())));
1164        assert_eq!(c2.swap(None), Some(Arc::new(a2.hook())));
1165    }
1166
1167    use crate::transaction::ReadTxn;
1168    use crate::updates::decoder::Decode;
1169    use crate::updates::encoder::{Encoder, EncoderV1};
1170    use arc_swap::ArcSwapOption;
1171    use fastrand::Rng;
1172    use std::sync::atomic::{AtomicBool, AtomicI64, Ordering};
1173    use std::time::Duration;
1174
1175    static UNIQUE_NUMBER: AtomicI64 = AtomicI64::new(0);
1176
1177    fn get_unique_number() -> i64 {
1178        UNIQUE_NUMBER.fetch_add(1, Ordering::SeqCst)
1179    }
1180
1181    fn array_transactions() -> [Box<dyn Fn(&mut Doc, &mut Rng)>; 5] {
1182        fn move_one(doc: &mut Doc, rng: &mut Rng) {
1183            let yarray = doc.get_or_insert_array("array");
1184            let mut txn = doc.transact_mut();
1185            if yarray.len(&txn) != 0 {
1186                let pos = rng.between(0, yarray.len(&txn) - 1);
1187                let len = 1;
1188                let new_pos_adjusted = rng.between(0, yarray.len(&txn) - 1);
1189                let new_pos = new_pos_adjusted + if new_pos_adjusted > pos { len } else { 0 };
1190                if let Any::Array(expected) = yarray.to_json(&txn) {
1191                    let mut expected = Vec::from(expected.as_ref());
1192                    let moved = expected.remove(pos as usize);
1193                    let insert_pos = if pos < new_pos {
1194                        new_pos - len
1195                    } else {
1196                        new_pos
1197                    } as usize;
1198                    expected.insert(insert_pos, moved);
1199
1200                    yarray.move_to(&mut txn, pos, new_pos);
1201
1202                    let actual = yarray.to_json(&txn);
1203                    assert_eq!(actual, Any::from(expected))
1204                } else {
1205                    panic!("should not happen")
1206                }
1207            }
1208        }
1209        fn insert(doc: &mut Doc, rng: &mut Rng) {
1210            let yarray = doc.get_or_insert_array("array");
1211            let mut txn = doc.transact_mut();
1212            let unique_number = get_unique_number();
1213            let len = rng.between(1, 4);
1214            let content: Vec<_> = (0..len)
1215                .into_iter()
1216                .map(|_| Any::BigInt(unique_number))
1217                .collect();
1218            let mut pos = rng.between(0, yarray.len(&txn)) as usize;
1219            if let Any::Array(expected) = yarray.to_json(&txn) {
1220                let mut expected = Vec::from(expected.as_ref());
1221                yarray.insert_range(&mut txn, pos as u32, content.clone());
1222
1223                for any in content {
1224                    expected.insert(pos, any);
1225                    pos += 1;
1226                }
1227                let actual = yarray.to_json(&txn);
1228                assert_eq!(actual, Any::from(expected))
1229            } else {
1230                panic!("should not happen")
1231            }
1232        }
1233
1234        fn insert_type_array(doc: &mut Doc, rng: &mut Rng) {
1235            let yarray = doc.get_or_insert_array("array");
1236            let mut txn = doc.transact_mut();
1237            let pos = rng.between(0, yarray.len(&txn));
1238            let array2 = yarray.insert(&mut txn, pos, ArrayPrelim::from([1, 2, 3, 4]));
1239            let expected: Arc<[Any]> = (1..=4).map(|i| Any::Number(i as f64)).collect();
1240            assert_eq!(array2.to_json(&txn), Any::Array(expected));
1241        }
1242
1243        fn insert_type_map(doc: &mut Doc, rng: &mut Rng) {
1244            let yarray = doc.get_or_insert_array("array");
1245            let mut txn = doc.transact_mut();
1246            let pos = rng.between(0, yarray.len(&txn));
1247            let map = yarray.insert(&mut txn, pos, MapPrelim::default());
1248            map.insert(&mut txn, "someprop".to_string(), 42);
1249            map.insert(&mut txn, "someprop".to_string(), 43);
1250            map.insert(&mut txn, "someprop".to_string(), 44);
1251        }
1252
1253        fn delete(doc: &mut Doc, rng: &mut Rng) {
1254            let yarray = doc.get_or_insert_array("array");
1255            let mut txn = doc.transact_mut();
1256            let len = yarray.len(&txn);
1257            if len > 0 {
1258                let pos = rng.between(0, len - 1);
1259                let del_len = rng.between(1, 2.min(len - pos));
1260                if rng.bool() {
1261                    if let Out::YArray(array2) = yarray.get(&txn, pos).unwrap() {
1262                        let pos = rng.between(0, array2.len(&txn) - 1);
1263                        let del_len = rng.between(0, 2.min(array2.len(&txn) - pos));
1264                        array2.remove_range(&mut txn, pos, del_len);
1265                    }
1266                } else {
1267                    if let Any::Array(old_content) = yarray.to_json(&txn) {
1268                        let mut old_content = Vec::from(old_content.as_ref());
1269                        yarray.remove_range(&mut txn, pos, del_len);
1270                        old_content.drain(pos as usize..(pos + del_len) as usize);
1271                        assert_eq!(yarray.to_json(&txn), Any::from(old_content));
1272                    } else {
1273                        panic!("should not happen")
1274                    }
1275                }
1276            }
1277        }
1278
1279        [
1280            Box::new(insert),
1281            Box::new(insert_type_array),
1282            Box::new(insert_type_map),
1283            Box::new(delete),
1284            Box::new(move_one),
1285        ]
1286    }
1287
1288    fn fuzzy(iterations: usize) {
1289        run_scenario(0, &array_transactions(), 5, iterations)
1290    }
1291
1292    #[test]
1293    fn fuzzy_test_6() {
1294        fuzzy(6)
1295    }
1296
1297    #[test]
1298    fn fuzzy_test_300() {
1299        fuzzy(300)
1300    }
1301
1302    #[test]
1303    fn get_at_removed_index() {
1304        let d1 = Doc::with_client_id(1);
1305        let a1 = d1.get_or_insert_array("array");
1306        let mut t1 = d1.transact_mut();
1307
1308        a1.insert_range(&mut t1, 0, ["A"]);
1309        a1.remove(&mut t1, 0);
1310
1311        let actual = a1.get(&t1, 0);
1312        assert_eq!(actual, None);
1313    }
1314
1315    #[test]
1316    fn observe_deep_event_order() {
1317        let doc = Doc::with_client_id(1);
1318        let array = doc.get_or_insert_array("array");
1319
1320        let paths = Arc::new(Mutex::new(vec![]));
1321        let paths_copy = paths.clone();
1322
1323        let _sub = array.observe_deep(move |_txn, e| {
1324            let path: Vec<Path> = e.iter().map(Event::path).collect();
1325            paths_copy.lock().unwrap().push(path);
1326        });
1327
1328        array.insert(&mut doc.transact_mut(), 0, MapPrelim::default());
1329
1330        {
1331            let mut txn = doc.transact_mut();
1332            let map = array.get(&txn, 0).unwrap().cast::<MapRef>().unwrap();
1333            map.insert(&mut txn, "a", "a");
1334            array.insert(&mut txn, 0, 0);
1335        }
1336
1337        let expected = &[
1338            vec![Path::default()],
1339            vec![Path::default(), Path::from([PathSegment::Index(1)])],
1340        ];
1341        let actual = paths.lock().unwrap();
1342        assert_eq!(actual.as_slice(), expected);
1343    }
1344
1345    #[test]
1346    fn move_1() {
1347        let d1 = Doc::with_client_id(1);
1348        let a1 = d1.get_or_insert_array("array");
1349
1350        let d2 = Doc::with_client_id(2);
1351        let a2 = d2.get_or_insert_array("array");
1352
1353        let e1 = Arc::new(ArcSwapOption::default());
1354        let inner = e1.clone();
1355        let _s1 = a1.observe(move |txn, e| {
1356            inner.store(Some(Arc::new(e.delta(txn).to_vec())));
1357        });
1358
1359        let e2 = Arc::new(ArcSwapOption::default());
1360        let inner = e2.clone();
1361        let _s2 = a2.observe(move |txn, e| {
1362            inner.store(Some(Arc::new(e.delta(txn).to_vec())));
1363        });
1364
1365        {
1366            let mut txn = d1.transact_mut();
1367            a1.insert_range(&mut txn, 0, [1, 2, 3]);
1368            a1.move_to(&mut txn, 1, 0);
1369        }
1370        assert_eq!(a1.to_json(&d1.transact()), vec![2, 1, 3].into());
1371
1372        exchange_updates(&[&d1, &d2]);
1373
1374        assert_eq!(a2.to_json(&d2.transact()), vec![2, 1, 3].into());
1375        let actual = e2.load_full();
1376        assert_eq!(
1377            actual,
1378            Some(Arc::new(vec![Change::Added(vec![
1379                2.into(),
1380                1.into(),
1381                3.into()
1382            ])]))
1383        );
1384
1385        a1.move_to(&mut d1.transact_mut(), 0, 2);
1386
1387        assert_eq!(a1.to_json(&d1.transact()), vec![1, 2, 3].into());
1388        let actual = e1.load_full();
1389        assert_eq!(
1390            actual,
1391            Some(Arc::new(vec![
1392                Change::Removed(1),
1393                Change::Retain(1),
1394                Change::Added(vec![2.into()])
1395            ]))
1396        )
1397    }
1398
1399    #[test]
1400    fn move_2() {
1401        let d1 = Doc::with_client_id(1);
1402        let a1 = d1.get_or_insert_array("array");
1403
1404        let d2 = Doc::with_client_id(2);
1405        let a2 = d2.get_or_insert_array("array");
1406
1407        let e1 = Arc::new(ArcSwapOption::default());
1408        let inner = e1.clone();
1409        let _s1 = a1.observe(move |txn, e| {
1410            inner.store(Some(Arc::new(e.delta(txn).to_vec())));
1411        });
1412
1413        let e2 = Arc::new(ArcSwapOption::default());
1414        let inner = e2.clone();
1415        let _s2 = a2.observe(move |txn, e| {
1416            inner.store(Some(Arc::new(e.delta(txn).to_vec())));
1417        });
1418
1419        a1.insert_range(&mut d1.transact_mut(), 0, [1, 2]);
1420        a1.move_to(&mut d1.transact_mut(), 1, 0);
1421        assert_eq!(a1.to_json(&d1.transact()), vec![2, 1].into());
1422        {
1423            let actual = e1.load_full();
1424            assert_eq!(
1425                actual,
1426                Some(Arc::new(vec![
1427                    Change::Added(vec![2.into()]),
1428                    Change::Retain(1),
1429                    Change::Removed(1)
1430                ]))
1431            );
1432        }
1433
1434        exchange_updates(&[&d1, &d2]);
1435
1436        assert_eq!(a2.to_json(&d2.transact()), vec![2, 1].into());
1437        {
1438            let actual = e2.load_full();
1439            assert_eq!(
1440                actual,
1441                Some(Arc::new(vec![Change::Added(vec![2.into(), 1.into()])]))
1442            );
1443        }
1444
1445        a1.move_to(&mut d1.transact_mut(), 0, 2);
1446        assert_eq!(a1.to_json(&d1.transact()), vec![1, 2].into());
1447        {
1448            let actual = e1.load_full();
1449            assert_eq!(
1450                actual,
1451                Some(Arc::new(vec![
1452                    Change::Removed(1),
1453                    Change::Retain(1),
1454                    Change::Added(vec![2.into()])
1455                ]))
1456            );
1457        }
1458    }
1459
1460    #[test]
1461    fn move_cycles() {
1462        let d1 = Doc::with_client_id(1);
1463        let a1 = d1.get_or_insert_array("array");
1464
1465        let d2 = Doc::with_client_id(2);
1466        let a2 = d2.get_or_insert_array("array");
1467
1468        a1.insert_range(&mut d1.transact_mut(), 0, [1, 2, 3, 4]);
1469        exchange_updates(&[&d1, &d2]);
1470
1471        a1.move_range_to(&mut d1.transact_mut(), 0, Assoc::After, 1, Assoc::Before, 3);
1472        assert_eq!(a1.to_json(&d1.transact()), vec![3, 1, 2, 4].into());
1473
1474        a2.move_range_to(&mut d2.transact_mut(), 2, Assoc::After, 3, Assoc::Before, 1);
1475        assert_eq!(a2.to_json(&d2.transact()), vec![1, 3, 4, 2].into());
1476
1477        exchange_updates(&[&d1, &d2]);
1478        exchange_updates(&[&d1, &d2]); // move cycles may not be detected within a single update exchange
1479
1480        assert_eq!(a1.len(&d1.transact()), 4);
1481        assert_eq!(a1.to_json(&d1.transact()), a2.to_json(&d2.transact()));
1482    }
1483
1484    #[test]
1485    #[ignore] //TODO: investigate (see: https://github.com/y-crdt/y-crdt/pull/266)
1486    fn move_range_to() {
1487        let doc = Doc::with_client_id(1);
1488        let arr = doc.get_or_insert_array("array");
1489        // Move 1-2 to 4
1490        {
1491            let mut txn = doc.transact_mut();
1492            let arr_len = arr.len(&txn);
1493            arr.remove_range(&mut txn, 0, arr_len);
1494            let arr_len = arr.len(&txn);
1495            assert_eq!(arr_len, 0);
1496            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3]);
1497        }
1498        arr.move_range_to(
1499            &mut doc.transact_mut(),
1500            1,
1501            Assoc::After,
1502            2,
1503            Assoc::Before,
1504            4,
1505        );
1506        assert_eq!(arr.to_json(&doc.transact()), vec![0, 3, 1, 2].into());
1507
1508        // Move 0-0 to 10
1509        {
1510            let mut txn = doc.transact_mut();
1511            let arr_len = arr.len(&txn);
1512            arr.remove_range(&mut txn, 0, arr_len);
1513            let arr_len = arr.len(&txn);
1514            assert_eq!(arr_len, 0);
1515            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1516        }
1517        arr.move_range_to(
1518            &mut doc.transact_mut(),
1519            0,
1520            Assoc::After,
1521            0,
1522            Assoc::Before,
1523            10,
1524        );
1525        assert_eq!(
1526            arr.to_json(&doc.transact()),
1527            vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 0].into()
1528        );
1529
1530        // Move 0-1 to 10
1531        {
1532            let mut txn = doc.transact_mut();
1533            let arr_len = arr.len(&txn);
1534            arr.remove_range(&mut txn, 0, arr_len);
1535            let arr_len = arr.len(&txn);
1536            assert_eq!(arr_len, 0);
1537            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1538        }
1539        arr.move_range_to(
1540            &mut doc.transact_mut(),
1541            0,
1542            Assoc::After,
1543            1,
1544            Assoc::Before,
1545            10,
1546        );
1547        assert_eq!(
1548            arr.to_json(&doc.transact()),
1549            vec![2, 3, 4, 5, 6, 7, 8, 9, 0, 1].into()
1550        );
1551
1552        // Move 3-5 to 7
1553        {
1554            let mut txn = doc.transact_mut();
1555            let arr_len = arr.len(&txn);
1556            arr.remove_range(&mut txn, 0, arr_len);
1557            let arr_len = arr.len(&txn);
1558            assert_eq!(arr_len, 0);
1559            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1560        }
1561        arr.move_range_to(
1562            &mut doc.transact_mut(),
1563            3,
1564            Assoc::After,
1565            5,
1566            Assoc::Before,
1567            7,
1568        );
1569        assert_eq!(
1570            arr.to_json(&doc.transact()),
1571            vec![0, 1, 2, 6, 3, 4, 5, 7, 8, 9].into()
1572        );
1573
1574        // Move 1-0 to 10
1575        {
1576            let mut txn = doc.transact_mut();
1577            let arr_len = arr.len(&txn);
1578            arr.remove_range(&mut txn, 0, arr_len);
1579            let arr_len = arr.len(&txn);
1580            assert_eq!(arr_len, 0);
1581            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1582        }
1583        arr.move_range_to(
1584            &mut doc.transact_mut(),
1585            1,
1586            Assoc::After,
1587            0,
1588            Assoc::Before,
1589            10,
1590        );
1591        assert_eq!(
1592            arr.to_json(&doc.transact()),
1593            vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9].into()
1594        );
1595
1596        // Move 3-5 to 5
1597        {
1598            let mut txn = doc.transact_mut();
1599            let arr_len = arr.len(&txn);
1600            arr.remove_range(&mut txn, 0, arr_len);
1601            let arr_len = arr.len(&txn);
1602            assert_eq!(arr_len, 0);
1603            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1604        }
1605        arr.move_range_to(
1606            &mut doc.transact_mut(),
1607            3,
1608            Assoc::After,
1609            5,
1610            Assoc::Before,
1611            5,
1612        );
1613        assert_eq!(
1614            arr.to_json(&doc.transact()),
1615            vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9].into()
1616        );
1617
1618        // Move 9-9 to 0
1619        {
1620            let mut txn = doc.transact_mut();
1621            let arr_len = arr.len(&txn);
1622            arr.remove_range(&mut txn, 0, arr_len);
1623            let arr_len = arr.len(&txn);
1624            assert_eq!(arr_len, 0);
1625            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1626        }
1627        arr.move_range_to(
1628            &mut doc.transact_mut(),
1629            9,
1630            Assoc::After,
1631            9,
1632            Assoc::Before,
1633            0,
1634        );
1635        assert_eq!(
1636            arr.to_json(&doc.transact()),
1637            vec![9, 0, 1, 2, 3, 4, 5, 6, 7, 8].into()
1638        );
1639
1640        // Move 8-9 to 0
1641        {
1642            let mut txn = doc.transact_mut();
1643            let arr_len = arr.len(&txn);
1644            arr.remove_range(&mut txn, 0, arr_len);
1645            let arr_len = arr.len(&txn);
1646            assert_eq!(arr_len, 0);
1647            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1648        }
1649        arr.move_range_to(
1650            &mut doc.transact_mut(),
1651            8,
1652            Assoc::After,
1653            9,
1654            Assoc::Before,
1655            0,
1656        );
1657        assert_eq!(
1658            arr.to_json(&doc.transact()),
1659            vec![8, 9, 0, 1, 2, 3, 4, 5, 6, 7].into()
1660        );
1661
1662        // Move 4-6 to 3
1663        {
1664            let mut txn = doc.transact_mut();
1665            let arr_len = arr.len(&txn);
1666            arr.remove_range(&mut txn, 0, arr_len);
1667            let arr_len = arr.len(&txn);
1668            assert_eq!(arr_len, 0);
1669            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1670        }
1671        arr.move_range_to(
1672            &mut doc.transact_mut(),
1673            4,
1674            Assoc::After,
1675            6,
1676            Assoc::Before,
1677            3,
1678        );
1679        assert_eq!(
1680            arr.to_json(&doc.transact()),
1681            vec![0, 1, 2, 4, 5, 6, 3, 7, 8, 9].into()
1682        );
1683
1684        // Move 3-5 to 3
1685        {
1686            let mut txn = doc.transact_mut();
1687            let arr_len = arr.len(&txn);
1688            arr.remove_range(&mut txn, 0, arr_len);
1689            let arr_len = arr.len(&txn);
1690            assert_eq!(arr_len, 0);
1691            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1692        }
1693        arr.move_range_to(
1694            &mut doc.transact_mut(),
1695            3,
1696            Assoc::After,
1697            5,
1698            Assoc::Before,
1699            3,
1700        );
1701        assert_eq!(
1702            arr.to_json(&doc.transact()),
1703            vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9].into()
1704        );
1705    }
1706
1707    #[test]
1708    fn multi_threading() {
1709        use std::sync::{Arc, RwLock};
1710        use std::thread::{sleep, spawn};
1711
1712        let doc = Arc::new(RwLock::new(Doc::with_client_id(1)));
1713
1714        let d2 = doc.clone();
1715        let h2 = spawn(move || {
1716            for _ in 0..10 {
1717                let millis = fastrand::u64(1..20);
1718                sleep(Duration::from_millis(millis));
1719
1720                let doc = d2.write().unwrap();
1721                let array = doc.get_or_insert_array("test");
1722                let mut txn = doc.transact_mut();
1723                array.push_back(&mut txn, "a");
1724            }
1725        });
1726
1727        let d3 = doc.clone();
1728        let h3 = spawn(move || {
1729            for _ in 0..10 {
1730                let millis = fastrand::u64(1..20);
1731                sleep(Duration::from_millis(millis));
1732
1733                let doc = d3.write().unwrap();
1734                let array = doc.get_or_insert_array("test");
1735                let mut txn = doc.transact_mut();
1736                array.push_back(&mut txn, "b");
1737            }
1738        });
1739
1740        h3.join().unwrap();
1741        h2.join().unwrap();
1742
1743        let doc = doc.read().unwrap();
1744        let array = doc.get_or_insert_array("test");
1745        let len = array.len(&doc.transact());
1746        assert_eq!(len, 20);
1747    }
1748
1749    #[test]
1750    fn move_last_elem_iter() {
1751        // https://github.com/y-crdt/y-crdt/issues/186
1752
1753        let doc = Doc::with_client_id(1);
1754        let array = doc.get_or_insert_array("array");
1755        let mut txn = doc.transact_mut();
1756        array.insert_range(&mut txn, 0, [1, 2, 3]);
1757        drop(txn);
1758
1759        let mut txn = doc.transact_mut();
1760        array.move_to(&mut txn, 2, 0);
1761
1762        let mut iter = array.iter(&txn);
1763        let v = iter.next();
1764        assert_eq!(v, Some(3.into()));
1765        let v = iter.next();
1766        assert_eq!(v, Some(1.into()));
1767        let v = iter.next();
1768        assert_eq!(v, Some(2.into()));
1769        let v = iter.next();
1770        assert_eq!(v, None);
1771    }
1772
1773    #[test]
1774    fn insert_empty_range() {
1775        let doc = Doc::with_client_id(1);
1776        let mut txn = doc.transact_mut();
1777        let array = txn.get_or_insert_array("array");
1778
1779        array.insert(&mut txn, 0, 1);
1780        array.insert_range::<_, Any>(&mut txn, 1, []);
1781        array.push_back(&mut txn, 2);
1782
1783        assert_eq!(
1784            array.iter(&txn).collect::<Vec<_>>(),
1785            vec![1.into(), 2.into()]
1786        );
1787
1788        let data = txn.encode_state_as_update_v1(&StateVector::default());
1789
1790        let doc2 = Doc::with_client_id(2);
1791        let mut txn = doc2.transact_mut();
1792        let array = txn.get_or_insert_array("array");
1793        txn.apply_update(Update::decode_v1(&data).unwrap()).unwrap();
1794
1795        assert_eq!(
1796            array.iter(&txn).collect::<Vec<_>>(),
1797            vec![1.into(), 2.into()]
1798        );
1799    }
1800}
yrs/types/array.rs

yrs/types/
array.rs
