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::test_utils::{exchange_updates, run_scenario, RngExt};
642    use crate::types::map::MapPrelim;
643    use crate::types::{Change, DeepObservable, Event, Out, Path, PathSegment, ToJson};
644    use crate::{
645        any, Any, Array, ArrayPrelim, Assoc, Doc, Map, MapRef, Observable, SharedRef, StateVector,
646        Transact, Update, WriteTxn, ID,
647    };
648    use std::collections::{HashMap, HashSet};
649    use std::iter::FromIterator;
650    use std::sync::{Arc, Mutex};
651
652    #[test]
653    fn push_back() {
654        let doc = Doc::with_client_id(1);
655        let a = doc.get_or_insert_array("array");
656        let mut txn = doc.transact_mut();
657
658        a.push_back(&mut txn, "a");
659        a.push_back(&mut txn, "b");
660        a.push_back(&mut txn, "c");
661
662        let actual: Vec<_> = a.iter(&txn).collect();
663        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
664    }
665
666    #[test]
667    fn push_front() {
668        let doc = Doc::with_client_id(1);
669        let a = doc.get_or_insert_array("array");
670        let mut txn = doc.transact_mut();
671
672        a.push_front(&mut txn, "c");
673        a.push_front(&mut txn, "b");
674        a.push_front(&mut txn, "a");
675
676        let actual: Vec<_> = a.iter(&txn).collect();
677        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
678    }
679
680    #[test]
681    fn insert() {
682        let doc = Doc::with_client_id(1);
683        let a = doc.get_or_insert_array("array");
684        let mut txn = doc.transact_mut();
685
686        a.insert(&mut txn, 0, "a");
687        a.insert(&mut txn, 1, "c");
688        a.insert(&mut txn, 1, "b");
689
690        let actual: Vec<_> = a.iter(&txn).collect();
691        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
692    }
693
694    #[test]
695    fn basic() {
696        let d1 = Doc::with_client_id(1);
697        let d2 = Doc::with_client_id(2);
698
699        let a1 = d1.get_or_insert_array("array");
700
701        a1.insert(&mut d1.transact_mut(), 0, "Hi");
702        let update = d1
703            .transact()
704            .encode_state_as_update_v1(&StateVector::default());
705
706        let a2 = d2.get_or_insert_array("array");
707        let mut t2 = d2.transact_mut();
708        t2.apply_update(Update::decode_v1(update.as_slice()).unwrap())
709            .unwrap();
710        let actual: Vec<_> = a2.iter(&t2).collect();
711
712        assert_eq!(actual, vec!["Hi".into()]);
713    }
714
715    #[test]
716    fn len() {
717        let d = Doc::with_client_id(1);
718        let a = d.get_or_insert_array("array");
719
720        {
721            let mut txn = d.transact_mut();
722
723            a.push_back(&mut txn, 0); // len: 1
724            a.push_back(&mut txn, 1); // len: 2
725            a.push_back(&mut txn, 2); // len: 3
726            a.push_back(&mut txn, 3); // len: 4
727
728            a.remove_range(&mut txn, 0, 1); // len: 3
729            a.insert(&mut txn, 0, 0); // len: 4
730
731            assert_eq!(a.len(&txn), 4);
732        }
733        {
734            let mut txn = d.transact_mut();
735            a.remove_range(&mut txn, 1, 1); // len: 3
736            assert_eq!(a.len(&txn), 3);
737
738            a.insert(&mut txn, 1, 1); // len: 4
739            assert_eq!(a.len(&txn), 4);
740
741            a.remove_range(&mut txn, 2, 1); // len: 3
742            assert_eq!(a.len(&txn), 3);
743
744            a.insert(&mut txn, 2, 2); // len: 4
745            assert_eq!(a.len(&txn), 4);
746        }
747
748        let mut txn = d.transact_mut();
749        assert_eq!(a.len(&txn), 4);
750
751        a.remove_range(&mut txn, 1, 1);
752        assert_eq!(a.len(&txn), 3);
753
754        a.insert(&mut txn, 1, 1);
755        assert_eq!(a.len(&txn), 4);
756    }
757
758    #[test]
759    fn remove_insert() {
760        let d1 = Doc::with_client_id(1);
761        let a1 = d1.get_or_insert_array("array");
762
763        let mut t1 = d1.transact_mut();
764        a1.insert(&mut t1, 0, "A");
765        a1.remove_range(&mut t1, 1, 0);
766    }
767
768    #[test]
769    fn insert_3_elements_try_re_get() {
770        let d1 = Doc::with_client_id(1);
771        let d2 = Doc::with_client_id(2);
772        let a1 = d1.get_or_insert_array("array");
773        {
774            let mut t1 = d1.transact_mut();
775
776            a1.push_back(&mut t1, 1);
777            a1.push_back(&mut t1, true);
778            a1.push_back(&mut t1, false);
779            let actual: Vec<_> = a1.iter(&t1).collect();
780            assert_eq!(
781                actual,
782                vec![Out::from(1.0), Out::from(true), Out::from(false)]
783            );
784        }
785
786        exchange_updates(&[&d1, &d2]);
787
788        let a2 = d2.get_or_insert_array("array");
789        let t2 = d2.transact();
790        let actual: Vec<_> = a2.iter(&t2).collect();
791        assert_eq!(
792            actual,
793            vec![Out::from(1.0), Out::from(true), Out::from(false)]
794        );
795    }
796
797    #[test]
798    fn concurrent_insert_with_3_conflicts() {
799        let d1 = Doc::with_client_id(1);
800        let a = d1.get_or_insert_array("array");
801        {
802            let mut txn = d1.transact_mut();
803            a.insert(&mut txn, 0, 0);
804        }
805
806        let d2 = Doc::with_client_id(2);
807        {
808            let mut txn = d1.transact_mut();
809            a.insert(&mut txn, 0, 1);
810        }
811
812        let d3 = Doc::with_client_id(3);
813        {
814            let mut txn = d1.transact_mut();
815            a.insert(&mut txn, 0, 2);
816        }
817
818        exchange_updates(&[&d1, &d2, &d3]);
819
820        let a1 = to_array(&d1);
821        let a2 = to_array(&d2);
822        let a3 = to_array(&d3);
823
824        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
825        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
826    }
827
828    fn to_array(d: &Doc) -> Vec<Out> {
829        let a = d.get_or_insert_array("array");
830        a.iter(&d.transact()).collect()
831    }
832
833    #[test]
834    fn concurrent_insert_remove_with_3_conflicts() {
835        let d1 = Doc::with_client_id(1);
836        {
837            let a = d1.get_or_insert_array("array");
838            let mut txn = d1.transact_mut();
839            a.insert_range(&mut txn, 0, ["x", "y", "z"]);
840        }
841        let d2 = Doc::with_client_id(2);
842        let d3 = Doc::with_client_id(3);
843
844        exchange_updates(&[&d1, &d2, &d3]);
845
846        {
847            // start state: [x,y,z]
848            let a1 = d1.get_or_insert_array("array");
849            let a2 = d2.get_or_insert_array("array");
850            let a3 = d3.get_or_insert_array("array");
851            let mut t1 = d1.transact_mut();
852            let mut t2 = d2.transact_mut();
853            let mut t3 = d3.transact_mut();
854
855            a1.insert(&mut t1, 1, 0); // [x,0,y,z]
856            a2.remove_range(&mut t2, 0, 1); // [y,z]
857            a2.remove_range(&mut t2, 1, 1); // [y]
858            a3.insert(&mut t3, 1, 2); // [x,2,y,z]
859        }
860
861        exchange_updates(&[&d1, &d2, &d3]);
862        // after exchange expected: [0,2,y]
863
864        let a1 = to_array(&d1);
865        let a2 = to_array(&d2);
866        let a3 = to_array(&d3);
867
868        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
869        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
870    }
871
872    #[test]
873    fn insertions_in_late_sync() {
874        let d1 = Doc::with_client_id(1);
875        {
876            let a = d1.get_or_insert_array("array");
877            let mut txn = d1.transact_mut();
878            a.push_back(&mut txn, "x");
879            a.push_back(&mut txn, "y");
880        }
881        let d2 = Doc::with_client_id(2);
882        let d3 = Doc::with_client_id(3);
883
884        exchange_updates(&[&d1, &d2, &d3]);
885
886        {
887            let a1 = d1.get_or_insert_array("array");
888            let a2 = d2.get_or_insert_array("array");
889            let a3 = d3.get_or_insert_array("array");
890            let mut t1 = d1.transact_mut();
891            let mut t2 = d2.transact_mut();
892            let mut t3 = d3.transact_mut();
893
894            a1.insert(&mut t1, 1, "user0");
895            a2.insert(&mut t2, 1, "user1");
896            a3.insert(&mut t3, 1, "user2");
897        }
898
899        exchange_updates(&[&d1, &d2, &d3]);
900
901        let a1 = to_array(&d1);
902        let a2 = to_array(&d2);
903        let a3 = to_array(&d3);
904
905        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
906        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
907    }
908
909    #[test]
910    fn removals_in_late_sync() {
911        let d1 = Doc::with_client_id(1);
912        {
913            let a = d1.get_or_insert_array("array");
914            let mut txn = d1.transact_mut();
915            a.push_back(&mut txn, "x");
916            a.push_back(&mut txn, "y");
917        }
918        let d2 = Doc::with_client_id(2);
919
920        exchange_updates(&[&d1, &d2]);
921
922        {
923            let a1 = d1.get_or_insert_array("array");
924            let a2 = d2.get_or_insert_array("array");
925            let mut t1 = d1.transact_mut();
926            let mut t2 = d2.transact_mut();
927
928            a2.remove_range(&mut t2, 1, 1);
929            a1.remove_range(&mut t1, 0, 2);
930        }
931
932        exchange_updates(&[&d1, &d2]);
933
934        let a1 = to_array(&d1);
935        let a2 = to_array(&d2);
936
937        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
938    }
939
940    #[test]
941    fn insert_then_merge_delete_on_sync() {
942        let d1 = Doc::with_client_id(1);
943        {
944            let a = d1.get_or_insert_array("array");
945            let mut txn = d1.transact_mut();
946            a.push_back(&mut txn, "x");
947            a.push_back(&mut txn, "y");
948            a.push_back(&mut txn, "z");
949        }
950        let d2 = Doc::with_client_id(2);
951
952        exchange_updates(&[&d1, &d2]);
953
954        {
955            let a2 = d2.get_or_insert_array("array");
956            let mut t2 = d2.transact_mut();
957
958            a2.remove_range(&mut t2, 0, 3);
959        }
960
961        exchange_updates(&[&d1, &d2]);
962
963        let a1 = to_array(&d1);
964        let a2 = to_array(&d2);
965
966        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
967    }
968
969    #[test]
970    fn iter_array_containing_types() {
971        let d = Doc::with_client_id(1);
972        let a = d.get_or_insert_array("arr");
973        let mut txn = d.transact_mut();
974        for i in 0..10 {
975            let mut m = HashMap::new();
976            m.insert("value".to_owned(), i);
977            a.push_back(&mut txn, MapPrelim::from_iter(m));
978        }
979
980        for (i, value) in a.iter(&txn).enumerate() {
981            match value {
982                Out::YMap(_) => {
983                    assert_eq!(value.to_json(&txn), any!({"value": (i as f64) }))
984                }
985                _ => panic!("Value of array at index {} was no YMap", i),
986            }
987        }
988    }
989
990    #[test]
991    fn insert_and_remove_events() {
992        let d = Doc::with_client_id(1);
993        let array = d.get_or_insert_array("array");
994        let happened = Arc::new(AtomicBool::new(false));
995        let happened_clone = happened.clone();
996        let _sub = array.observe(move |_, _| {
997            happened_clone.store(true, Ordering::Relaxed);
998        });
999
1000        {
1001            let mut txn = d.transact_mut();
1002            array.insert_range(&mut txn, 0, [0, 1, 2]);
1003            // txn is committed at the end of this scope
1004        }
1005        assert!(
1006            happened.swap(false, Ordering::Relaxed),
1007            "insert of [0,1,2] should trigger event"
1008        );
1009
1010        {
1011            let mut txn = d.transact_mut();
1012            array.remove_range(&mut txn, 0, 1);
1013            // txn is committed at the end of this scope
1014        }
1015        assert!(
1016            happened.swap(false, Ordering::Relaxed),
1017            "removal of [0] should trigger event"
1018        );
1019
1020        {
1021            let mut txn = d.transact_mut();
1022            array.remove_range(&mut txn, 0, 2);
1023            // txn is committed at the end of this scope
1024        }
1025        assert!(
1026            happened.swap(false, Ordering::Relaxed),
1027            "removal of [1,2] should trigger event"
1028        );
1029    }
1030
1031    #[test]
1032    fn insert_and_remove_event_changes() {
1033        let d1 = Doc::with_client_id(1);
1034        let array = d1.get_or_insert_array("array");
1035        let added = Arc::new(ArcSwapOption::default());
1036        let removed = Arc::new(ArcSwapOption::default());
1037        let delta = Arc::new(ArcSwapOption::default());
1038
1039        let (added_c, removed_c, delta_c) = (added.clone(), removed.clone(), delta.clone());
1040        let _sub = array.observe(move |txn, e| {
1041            added_c.store(Some(Arc::new(e.inserts(txn).clone())));
1042            removed_c.store(Some(Arc::new(e.removes(txn).clone())));
1043            delta_c.store(Some(Arc::new(e.delta(txn).to_vec())));
1044        });
1045
1046        {
1047            let mut txn = d1.transact_mut();
1048            array.push_back(&mut txn, 4);
1049            array.push_back(&mut txn, "dtrn");
1050            // txn is committed at the end of this scope
1051        }
1052        assert_eq!(
1053            added.swap(None),
1054            Some(HashSet::from([ID::new(1, 0), ID::new(1, 1)]).into())
1055        );
1056        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
1057        assert_eq!(
1058            delta.swap(None),
1059            Some(
1060                vec![Change::Added(vec![
1061                    Any::Number(4.0).into(),
1062                    Any::String("dtrn".into()).into()
1063                ])]
1064                .into()
1065            )
1066        );
1067
1068        {
1069            let mut txn = d1.transact_mut();
1070            array.remove_range(&mut txn, 0, 1);
1071        }
1072        assert_eq!(added.swap(None), Some(HashSet::new().into()));
1073        assert_eq!(
1074            removed.swap(None),
1075            Some(HashSet::from([ID::new(1, 0)]).into())
1076        );
1077        assert_eq!(delta.swap(None), Some(vec![Change::Removed(1)].into()));
1078
1079        {
1080            let mut txn = d1.transact_mut();
1081            array.insert(&mut txn, 1, 0.5);
1082        }
1083        assert_eq!(
1084            added.swap(None),
1085            Some(HashSet::from([ID::new(1, 2)]).into())
1086        );
1087        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
1088        assert_eq!(
1089            delta.swap(None),
1090            Some(
1091                vec![
1092                    Change::Retain(1),
1093                    Change::Added(vec![Any::Number(0.5).into()])
1094                ]
1095                .into()
1096            )
1097        );
1098
1099        let d2 = Doc::with_client_id(2);
1100        let array2 = d2.get_or_insert_array("array");
1101        let (added_c, removed_c, delta_c) = (added.clone(), removed.clone(), delta.clone());
1102        let _sub = array2.observe(move |txn, e| {
1103            added_c.store(Some(e.inserts(txn).clone().into()));
1104            removed_c.store(Some(e.removes(txn).clone().into()));
1105            delta_c.store(Some(e.delta(txn).to_vec().into()));
1106        });
1107
1108        {
1109            let t1 = d1.transact_mut();
1110            let mut t2 = d2.transact_mut();
1111
1112            let sv = t2.state_vector();
1113            let mut encoder = EncoderV1::new();
1114            t1.encode_diff(&sv, &mut encoder);
1115            t2.apply_update(Update::decode_v1(encoder.to_vec().as_slice()).unwrap())
1116                .unwrap();
1117        }
1118
1119        assert_eq!(
1120            added.swap(None),
1121            Some(HashSet::from([ID::new(1, 1)]).into())
1122        );
1123        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
1124        assert_eq!(
1125            delta.swap(None),
1126            Some(
1127                vec![Change::Added(vec![
1128                    Any::String("dtrn".into()).into(),
1129                    Any::Number(0.5).into(),
1130                ])]
1131                .into()
1132            )
1133        );
1134    }
1135
1136    #[test]
1137    fn target_on_local_and_remote() {
1138        let d1 = Doc::with_client_id(1);
1139        let d2 = Doc::with_client_id(2);
1140        let a1 = d1.get_or_insert_array("array");
1141        let a2 = d2.get_or_insert_array("array");
1142
1143        let c1 = Arc::new(ArcSwapOption::default());
1144        let c1c = c1.clone();
1145        let _s1 = a1.observe(move |_, e| {
1146            c1c.store(Some(e.target().hook().into()));
1147        });
1148        let c2 = Arc::new(ArcSwapOption::default());
1149        let c2c = c2.clone();
1150        let _s2 = a2.observe(move |_, e| {
1151            c2c.store(Some(e.target().hook().into()));
1152        });
1153
1154        {
1155            let mut t1 = d1.transact_mut();
1156            a1.insert_range(&mut t1, 0, [1, 2]);
1157        }
1158        exchange_updates(&[&d1, &d2]);
1159
1160        assert_eq!(c1.swap(None), Some(Arc::new(a1.hook())));
1161        assert_eq!(c2.swap(None), Some(Arc::new(a2.hook())));
1162    }
1163
1164    use crate::transaction::ReadTxn;
1165    use crate::updates::decoder::Decode;
1166    use crate::updates::encoder::{Encoder, EncoderV1};
1167    use arc_swap::ArcSwapOption;
1168    use fastrand::Rng;
1169    use std::sync::atomic::{AtomicBool, AtomicI64, Ordering};
1170    use std::time::Duration;
1171
1172    static UNIQUE_NUMBER: AtomicI64 = AtomicI64::new(0);
1173
1174    fn get_unique_number() -> i64 {
1175        UNIQUE_NUMBER.fetch_add(1, Ordering::SeqCst)
1176    }
1177
1178    fn array_transactions() -> [Box<dyn Fn(&mut Doc, &mut Rng)>; 5] {
1179        fn move_one(doc: &mut Doc, rng: &mut Rng) {
1180            let yarray = doc.get_or_insert_array("array");
1181            let mut txn = doc.transact_mut();
1182            if yarray.len(&txn) != 0 {
1183                let pos = rng.between(0, yarray.len(&txn) - 1);
1184                let len = 1;
1185                let new_pos_adjusted = rng.between(0, yarray.len(&txn) - 1);
1186                let new_pos = new_pos_adjusted + if new_pos_adjusted > pos { len } else { 0 };
1187                if let Any::Array(expected) = yarray.to_json(&txn) {
1188                    let mut expected = Vec::from(expected.as_ref());
1189                    let moved = expected.remove(pos as usize);
1190                    let insert_pos = if pos < new_pos {
1191                        new_pos - len
1192                    } else {
1193                        new_pos
1194                    } as usize;
1195                    expected.insert(insert_pos, moved);
1196
1197                    yarray.move_to(&mut txn, pos, new_pos);
1198
1199                    let actual = yarray.to_json(&txn);
1200                    assert_eq!(actual, Any::from(expected))
1201                } else {
1202                    panic!("should not happen")
1203                }
1204            }
1205        }
1206        fn insert(doc: &mut Doc, rng: &mut Rng) {
1207            let yarray = doc.get_or_insert_array("array");
1208            let mut txn = doc.transact_mut();
1209            let unique_number = get_unique_number();
1210            let len = rng.between(1, 4);
1211            let content: Vec<_> = (0..len)
1212                .into_iter()
1213                .map(|_| Any::BigInt(unique_number))
1214                .collect();
1215            let mut pos = rng.between(0, yarray.len(&txn)) as usize;
1216            if let Any::Array(expected) = yarray.to_json(&txn) {
1217                let mut expected = Vec::from(expected.as_ref());
1218                yarray.insert_range(&mut txn, pos as u32, content.clone());
1219
1220                for any in content {
1221                    expected.insert(pos, any);
1222                    pos += 1;
1223                }
1224                let actual = yarray.to_json(&txn);
1225                assert_eq!(actual, Any::from(expected))
1226            } else {
1227                panic!("should not happen")
1228            }
1229        }
1230
1231        fn insert_type_array(doc: &mut Doc, rng: &mut Rng) {
1232            let yarray = doc.get_or_insert_array("array");
1233            let mut txn = doc.transact_mut();
1234            let pos = rng.between(0, yarray.len(&txn));
1235            let array2 = yarray.insert(&mut txn, pos, ArrayPrelim::from([1, 2, 3, 4]));
1236            let expected: Arc<[Any]> = (1..=4).map(|i| Any::Number(i as f64)).collect();
1237            assert_eq!(array2.to_json(&txn), Any::Array(expected));
1238        }
1239
1240        fn insert_type_map(doc: &mut Doc, rng: &mut Rng) {
1241            let yarray = doc.get_or_insert_array("array");
1242            let mut txn = doc.transact_mut();
1243            let pos = rng.between(0, yarray.len(&txn));
1244            let map = yarray.insert(&mut txn, pos, MapPrelim::default());
1245            map.insert(&mut txn, "someprop".to_string(), 42);
1246            map.insert(&mut txn, "someprop".to_string(), 43);
1247            map.insert(&mut txn, "someprop".to_string(), 44);
1248        }
1249
1250        fn delete(doc: &mut Doc, rng: &mut Rng) {
1251            let yarray = doc.get_or_insert_array("array");
1252            let mut txn = doc.transact_mut();
1253            let len = yarray.len(&txn);
1254            if len > 0 {
1255                let pos = rng.between(0, len - 1);
1256                let del_len = rng.between(1, 2.min(len - pos));
1257                if rng.bool() {
1258                    if let Out::YArray(array2) = yarray.get(&txn, pos).unwrap() {
1259                        let pos = rng.between(0, array2.len(&txn) - 1);
1260                        let del_len = rng.between(0, 2.min(array2.len(&txn) - pos));
1261                        array2.remove_range(&mut txn, pos, del_len);
1262                    }
1263                } else {
1264                    if let Any::Array(old_content) = yarray.to_json(&txn) {
1265                        let mut old_content = Vec::from(old_content.as_ref());
1266                        yarray.remove_range(&mut txn, pos, del_len);
1267                        old_content.drain(pos as usize..(pos + del_len) as usize);
1268                        assert_eq!(yarray.to_json(&txn), Any::from(old_content));
1269                    } else {
1270                        panic!("should not happen")
1271                    }
1272                }
1273            }
1274        }
1275
1276        [
1277            Box::new(insert),
1278            Box::new(insert_type_array),
1279            Box::new(insert_type_map),
1280            Box::new(delete),
1281            Box::new(move_one),
1282        ]
1283    }
1284
1285    fn fuzzy(iterations: usize) {
1286        run_scenario(0, &array_transactions(), 5, iterations)
1287    }
1288
1289    #[test]
1290    fn fuzzy_test_6() {
1291        fuzzy(6)
1292    }
1293
1294    #[test]
1295    fn fuzzy_test_300() {
1296        fuzzy(300)
1297    }
1298
1299    #[test]
1300    fn get_at_removed_index() {
1301        let d1 = Doc::with_client_id(1);
1302        let a1 = d1.get_or_insert_array("array");
1303        let mut t1 = d1.transact_mut();
1304
1305        a1.insert_range(&mut t1, 0, ["A"]);
1306        a1.remove(&mut t1, 0);
1307
1308        let actual = a1.get(&t1, 0);
1309        assert_eq!(actual, None);
1310    }
1311
1312    #[test]
1313    fn observe_deep_event_order() {
1314        let doc = Doc::with_client_id(1);
1315        let array = doc.get_or_insert_array("array");
1316
1317        let paths = Arc::new(Mutex::new(vec![]));
1318        let paths_copy = paths.clone();
1319
1320        let _sub = array.observe_deep(move |_txn, e| {
1321            let path: Vec<Path> = e.iter().map(Event::path).collect();
1322            paths_copy.lock().unwrap().push(path);
1323        });
1324
1325        array.insert(&mut doc.transact_mut(), 0, MapPrelim::default());
1326
1327        {
1328            let mut txn = doc.transact_mut();
1329            let map = array.get(&txn, 0).unwrap().cast::<MapRef>().unwrap();
1330            map.insert(&mut txn, "a", "a");
1331            array.insert(&mut txn, 0, 0);
1332        }
1333
1334        let expected = &[
1335            vec![Path::default()],
1336            vec![Path::default(), Path::from([PathSegment::Index(1)])],
1337        ];
1338        let actual = paths.lock().unwrap();
1339        assert_eq!(actual.as_slice(), expected);
1340    }
1341
1342    #[test]
1343    fn move_1() {
1344        let d1 = Doc::with_client_id(1);
1345        let a1 = d1.get_or_insert_array("array");
1346
1347        let d2 = Doc::with_client_id(2);
1348        let a2 = d2.get_or_insert_array("array");
1349
1350        let e1 = Arc::new(ArcSwapOption::default());
1351        let inner = e1.clone();
1352        let _s1 = a1.observe(move |txn, e| {
1353            inner.store(Some(Arc::new(e.delta(txn).to_vec())));
1354        });
1355
1356        let e2 = Arc::new(ArcSwapOption::default());
1357        let inner = e2.clone();
1358        let _s2 = a2.observe(move |txn, e| {
1359            inner.store(Some(Arc::new(e.delta(txn).to_vec())));
1360        });
1361
1362        {
1363            let mut txn = d1.transact_mut();
1364            a1.insert_range(&mut txn, 0, [1, 2, 3]);
1365            a1.move_to(&mut txn, 1, 0);
1366        }
1367        assert_eq!(a1.to_json(&d1.transact()), vec![2, 1, 3].into());
1368
1369        exchange_updates(&[&d1, &d2]);
1370
1371        assert_eq!(a2.to_json(&d2.transact()), vec![2, 1, 3].into());
1372        let actual = e2.load_full();
1373        assert_eq!(
1374            actual,
1375            Some(Arc::new(vec![Change::Added(vec![
1376                2.into(),
1377                1.into(),
1378                3.into()
1379            ])]))
1380        );
1381
1382        a1.move_to(&mut d1.transact_mut(), 0, 2);
1383
1384        assert_eq!(a1.to_json(&d1.transact()), vec![1, 2, 3].into());
1385        let actual = e1.load_full();
1386        assert_eq!(
1387            actual,
1388            Some(Arc::new(vec![
1389                Change::Removed(1),
1390                Change::Retain(1),
1391                Change::Added(vec![2.into()])
1392            ]))
1393        )
1394    }
1395
1396    #[test]
1397    fn move_2() {
1398        let d1 = Doc::with_client_id(1);
1399        let a1 = d1.get_or_insert_array("array");
1400
1401        let d2 = Doc::with_client_id(2);
1402        let a2 = d2.get_or_insert_array("array");
1403
1404        let e1 = Arc::new(ArcSwapOption::default());
1405        let inner = e1.clone();
1406        let _s1 = a1.observe(move |txn, e| {
1407            inner.store(Some(Arc::new(e.delta(txn).to_vec())));
1408        });
1409
1410        let e2 = Arc::new(ArcSwapOption::default());
1411        let inner = e2.clone();
1412        let _s2 = a2.observe(move |txn, e| {
1413            inner.store(Some(Arc::new(e.delta(txn).to_vec())));
1414        });
1415
1416        a1.insert_range(&mut d1.transact_mut(), 0, [1, 2]);
1417        a1.move_to(&mut d1.transact_mut(), 1, 0);
1418        assert_eq!(a1.to_json(&d1.transact()), vec![2, 1].into());
1419        {
1420            let actual = e1.load_full();
1421            assert_eq!(
1422                actual,
1423                Some(Arc::new(vec![
1424                    Change::Added(vec![2.into()]),
1425                    Change::Retain(1),
1426                    Change::Removed(1)
1427                ]))
1428            );
1429        }
1430
1431        exchange_updates(&[&d1, &d2]);
1432
1433        assert_eq!(a2.to_json(&d2.transact()), vec![2, 1].into());
1434        {
1435            let actual = e2.load_full();
1436            assert_eq!(
1437                actual,
1438                Some(Arc::new(vec![Change::Added(vec![2.into(), 1.into()])]))
1439            );
1440        }
1441
1442        a1.move_to(&mut d1.transact_mut(), 0, 2);
1443        assert_eq!(a1.to_json(&d1.transact()), vec![1, 2].into());
1444        {
1445            let actual = e1.load_full();
1446            assert_eq!(
1447                actual,
1448                Some(Arc::new(vec![
1449                    Change::Removed(1),
1450                    Change::Retain(1),
1451                    Change::Added(vec![2.into()])
1452                ]))
1453            );
1454        }
1455    }
1456
1457    #[test]
1458    fn move_cycles() {
1459        let d1 = Doc::with_client_id(1);
1460        let a1 = d1.get_or_insert_array("array");
1461
1462        let d2 = Doc::with_client_id(2);
1463        let a2 = d2.get_or_insert_array("array");
1464
1465        a1.insert_range(&mut d1.transact_mut(), 0, [1, 2, 3, 4]);
1466        exchange_updates(&[&d1, &d2]);
1467
1468        a1.move_range_to(&mut d1.transact_mut(), 0, Assoc::After, 1, Assoc::Before, 3);
1469        assert_eq!(a1.to_json(&d1.transact()), vec![3, 1, 2, 4].into());
1470
1471        a2.move_range_to(&mut d2.transact_mut(), 2, Assoc::After, 3, Assoc::Before, 1);
1472        assert_eq!(a2.to_json(&d2.transact()), vec![1, 3, 4, 2].into());
1473
1474        exchange_updates(&[&d1, &d2]);
1475        exchange_updates(&[&d1, &d2]); // move cycles may not be detected within a single update exchange
1476
1477        assert_eq!(a1.len(&d1.transact()), 4);
1478        assert_eq!(a1.to_json(&d1.transact()), a2.to_json(&d2.transact()));
1479    }
1480
1481    #[test]
1482    #[ignore] //TODO: investigate (see: https://github.com/y-crdt/y-crdt/pull/266)
1483    fn move_range_to() {
1484        let doc = Doc::with_client_id(1);
1485        let arr = doc.get_or_insert_array("array");
1486        // Move 1-2 to 4
1487        {
1488            let mut txn = doc.transact_mut();
1489            let arr_len = arr.len(&txn);
1490            arr.remove_range(&mut txn, 0, arr_len);
1491            let arr_len = arr.len(&txn);
1492            assert_eq!(arr_len, 0);
1493            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3]);
1494        }
1495        arr.move_range_to(
1496            &mut doc.transact_mut(),
1497            1,
1498            Assoc::After,
1499            2,
1500            Assoc::Before,
1501            4,
1502        );
1503        assert_eq!(arr.to_json(&doc.transact()), vec![0, 3, 1, 2].into());
1504
1505        // Move 0-0 to 10
1506        {
1507            let mut txn = doc.transact_mut();
1508            let arr_len = arr.len(&txn);
1509            arr.remove_range(&mut txn, 0, arr_len);
1510            let arr_len = arr.len(&txn);
1511            assert_eq!(arr_len, 0);
1512            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1513        }
1514        arr.move_range_to(
1515            &mut doc.transact_mut(),
1516            0,
1517            Assoc::After,
1518            0,
1519            Assoc::Before,
1520            10,
1521        );
1522        assert_eq!(
1523            arr.to_json(&doc.transact()),
1524            vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 0].into()
1525        );
1526
1527        // Move 0-1 to 10
1528        {
1529            let mut txn = doc.transact_mut();
1530            let arr_len = arr.len(&txn);
1531            arr.remove_range(&mut txn, 0, arr_len);
1532            let arr_len = arr.len(&txn);
1533            assert_eq!(arr_len, 0);
1534            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1535        }
1536        arr.move_range_to(
1537            &mut doc.transact_mut(),
1538            0,
1539            Assoc::After,
1540            1,
1541            Assoc::Before,
1542            10,
1543        );
1544        assert_eq!(
1545            arr.to_json(&doc.transact()),
1546            vec![2, 3, 4, 5, 6, 7, 8, 9, 0, 1].into()
1547        );
1548
1549        // Move 3-5 to 7
1550        {
1551            let mut txn = doc.transact_mut();
1552            let arr_len = arr.len(&txn);
1553            arr.remove_range(&mut txn, 0, arr_len);
1554            let arr_len = arr.len(&txn);
1555            assert_eq!(arr_len, 0);
1556            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1557        }
1558        arr.move_range_to(
1559            &mut doc.transact_mut(),
1560            3,
1561            Assoc::After,
1562            5,
1563            Assoc::Before,
1564            7,
1565        );
1566        assert_eq!(
1567            arr.to_json(&doc.transact()),
1568            vec![0, 1, 2, 6, 3, 4, 5, 7, 8, 9].into()
1569        );
1570
1571        // Move 1-0 to 10
1572        {
1573            let mut txn = doc.transact_mut();
1574            let arr_len = arr.len(&txn);
1575            arr.remove_range(&mut txn, 0, arr_len);
1576            let arr_len = arr.len(&txn);
1577            assert_eq!(arr_len, 0);
1578            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1579        }
1580        arr.move_range_to(
1581            &mut doc.transact_mut(),
1582            1,
1583            Assoc::After,
1584            0,
1585            Assoc::Before,
1586            10,
1587        );
1588        assert_eq!(
1589            arr.to_json(&doc.transact()),
1590            vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9].into()
1591        );
1592
1593        // Move 3-5 to 5
1594        {
1595            let mut txn = doc.transact_mut();
1596            let arr_len = arr.len(&txn);
1597            arr.remove_range(&mut txn, 0, arr_len);
1598            let arr_len = arr.len(&txn);
1599            assert_eq!(arr_len, 0);
1600            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1601        }
1602        arr.move_range_to(
1603            &mut doc.transact_mut(),
1604            3,
1605            Assoc::After,
1606            5,
1607            Assoc::Before,
1608            5,
1609        );
1610        assert_eq!(
1611            arr.to_json(&doc.transact()),
1612            vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9].into()
1613        );
1614
1615        // Move 9-9 to 0
1616        {
1617            let mut txn = doc.transact_mut();
1618            let arr_len = arr.len(&txn);
1619            arr.remove_range(&mut txn, 0, arr_len);
1620            let arr_len = arr.len(&txn);
1621            assert_eq!(arr_len, 0);
1622            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1623        }
1624        arr.move_range_to(
1625            &mut doc.transact_mut(),
1626            9,
1627            Assoc::After,
1628            9,
1629            Assoc::Before,
1630            0,
1631        );
1632        assert_eq!(
1633            arr.to_json(&doc.transact()),
1634            vec![9, 0, 1, 2, 3, 4, 5, 6, 7, 8].into()
1635        );
1636
1637        // Move 8-9 to 0
1638        {
1639            let mut txn = doc.transact_mut();
1640            let arr_len = arr.len(&txn);
1641            arr.remove_range(&mut txn, 0, arr_len);
1642            let arr_len = arr.len(&txn);
1643            assert_eq!(arr_len, 0);
1644            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1645        }
1646        arr.move_range_to(
1647            &mut doc.transact_mut(),
1648            8,
1649            Assoc::After,
1650            9,
1651            Assoc::Before,
1652            0,
1653        );
1654        assert_eq!(
1655            arr.to_json(&doc.transact()),
1656            vec![8, 9, 0, 1, 2, 3, 4, 5, 6, 7].into()
1657        );
1658
1659        // Move 4-6 to 3
1660        {
1661            let mut txn = doc.transact_mut();
1662            let arr_len = arr.len(&txn);
1663            arr.remove_range(&mut txn, 0, arr_len);
1664            let arr_len = arr.len(&txn);
1665            assert_eq!(arr_len, 0);
1666            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1667        }
1668        arr.move_range_to(
1669            &mut doc.transact_mut(),
1670            4,
1671            Assoc::After,
1672            6,
1673            Assoc::Before,
1674            3,
1675        );
1676        assert_eq!(
1677            arr.to_json(&doc.transact()),
1678            vec![0, 1, 2, 4, 5, 6, 3, 7, 8, 9].into()
1679        );
1680
1681        // Move 3-5 to 3
1682        {
1683            let mut txn = doc.transact_mut();
1684            let arr_len = arr.len(&txn);
1685            arr.remove_range(&mut txn, 0, arr_len);
1686            let arr_len = arr.len(&txn);
1687            assert_eq!(arr_len, 0);
1688            arr.insert_range(&mut txn, arr_len, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1689        }
1690        arr.move_range_to(
1691            &mut doc.transact_mut(),
1692            3,
1693            Assoc::After,
1694            5,
1695            Assoc::Before,
1696            3,
1697        );
1698        assert_eq!(
1699            arr.to_json(&doc.transact()),
1700            vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9].into()
1701        );
1702    }
1703
1704    #[test]
1705    fn multi_threading() {
1706        use std::sync::{Arc, RwLock};
1707        use std::thread::{sleep, spawn};
1708
1709        let doc = Arc::new(RwLock::new(Doc::with_client_id(1)));
1710
1711        let d2 = doc.clone();
1712        let h2 = spawn(move || {
1713            for _ in 0..10 {
1714                let millis = fastrand::u64(1..20);
1715                sleep(Duration::from_millis(millis));
1716
1717                let doc = d2.write().unwrap();
1718                let array = doc.get_or_insert_array("test");
1719                let mut txn = doc.transact_mut();
1720                array.push_back(&mut txn, "a");
1721            }
1722        });
1723
1724        let d3 = doc.clone();
1725        let h3 = spawn(move || {
1726            for _ in 0..10 {
1727                let millis = fastrand::u64(1..20);
1728                sleep(Duration::from_millis(millis));
1729
1730                let doc = d3.write().unwrap();
1731                let array = doc.get_or_insert_array("test");
1732                let mut txn = doc.transact_mut();
1733                array.push_back(&mut txn, "b");
1734            }
1735        });
1736
1737        h3.join().unwrap();
1738        h2.join().unwrap();
1739
1740        let doc = doc.read().unwrap();
1741        let array = doc.get_or_insert_array("test");
1742        let len = array.len(&doc.transact());
1743        assert_eq!(len, 20);
1744    }
1745
1746    #[test]
1747    fn move_last_elem_iter() {
1748        // https://github.com/y-crdt/y-crdt/issues/186
1749
1750        let doc = Doc::with_client_id(1);
1751        let array = doc.get_or_insert_array("array");
1752        let mut txn = doc.transact_mut();
1753        array.insert_range(&mut txn, 0, [1, 2, 3]);
1754        drop(txn);
1755
1756        let mut txn = doc.transact_mut();
1757        array.move_to(&mut txn, 2, 0);
1758
1759        let mut iter = array.iter(&txn);
1760        let v = iter.next();
1761        assert_eq!(v, Some(3.into()));
1762        let v = iter.next();
1763        assert_eq!(v, Some(1.into()));
1764        let v = iter.next();
1765        assert_eq!(v, Some(2.into()));
1766        let v = iter.next();
1767        assert_eq!(v, None);
1768    }
1769
1770    #[test]
1771    fn insert_empty_range() {
1772        let doc = Doc::with_client_id(1);
1773        let mut txn = doc.transact_mut();
1774        let array = txn.get_or_insert_array("array");
1775
1776        array.insert(&mut txn, 0, 1);
1777        array.insert_range::<_, Any>(&mut txn, 1, []);
1778        array.push_back(&mut txn, 2);
1779
1780        assert_eq!(
1781            array.iter(&txn).collect::<Vec<_>>(),
1782            vec![1.into(), 2.into()]
1783        );
1784
1785        let data = txn.encode_state_as_update_v1(&StateVector::default());
1786
1787        let doc2 = Doc::with_client_id(2);
1788        let mut txn = doc2.transact_mut();
1789        let array = txn.get_or_insert_array("array");
1790        txn.apply_update(Update::decode_v1(&data).unwrap()).unwrap();
1791
1792        assert_eq!(
1793            array.iter(&txn).collect::<Vec<_>>(),
1794            vec![1.into(), 2.into()]
1795        );
1796    }
1797}
yrs/types/array.rs

yrs/types/
array.rs
