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::sticky_index::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    /// Returns an iterator, that can be used to lazely traverse over all values stored in a current
338    /// array.
339    fn iter<'a, T: ReadTxn + 'a>(&self, txn: &'a T) -> ArrayIter<&'a T, T> {
340        ArrayIter::from_ref(self.as_ref(), txn)
341    }
342}
343
344pub struct ArrayIter<B, T>
345where
346    B: Borrow<T>,
347    T: ReadTxn,
348{
349    inner: BlockIter,
350    txn: B,
351    _marker: PhantomData<T>,
352}
353
354impl<T> ArrayIter<T, T>
355where
356    T: Borrow<T> + ReadTxn,
357{
358    pub fn from(array: &ArrayRef, txn: T) -> Self {
359        ArrayIter {
360            inner: BlockIter::new(array.0),
361            txn,
362            _marker: PhantomData::default(),
363        }
364    }
365}
366
367impl<'a, T> ArrayIter<&'a T, T>
368where
369    T: Borrow<T> + ReadTxn,
370{
371    pub fn from_ref(array: &Branch, txn: &'a T) -> Self {
372        ArrayIter {
373            inner: BlockIter::new(BranchPtr::from(array)),
374            txn,
375            _marker: PhantomData::default(),
376        }
377    }
378}
379
380impl<B, T> Iterator for ArrayIter<B, T>
381where
382    B: Borrow<T>,
383    T: ReadTxn,
384{
385    type Item = Out;
386
387    fn next(&mut self) -> Option<Self::Item> {
388        if self.inner.finished() {
389            None
390        } else {
391            let mut buf = [Out::default(); 1];
392            let txn = self.txn.borrow();
393            if self.inner.slice(txn, &mut buf) != 0 {
394                Some(std::mem::replace(&mut buf[0], Out::default()))
395            } else {
396                None
397            }
398        }
399    }
400}
401
402impl From<BranchPtr> for ArrayRef {
403    fn from(inner: BranchPtr) -> Self {
404        ArrayRef(inner)
405    }
406}
407
408/// A preliminary array. It can be used to initialize an [ArrayRef], when it's about to be nested
409/// into another Yrs data collection, such as [Map] or another [ArrayRef].
410#[repr(transparent)]
411#[derive(Debug, Clone, PartialEq, Default)]
412pub struct ArrayPrelim(Vec<In>);
413
414impl Deref for ArrayPrelim {
415    type Target = Vec<In>;
416
417    #[inline]
418    fn deref(&self) -> &Self::Target {
419        &self.0
420    }
421}
422
423impl DerefMut for ArrayPrelim {
424    fn deref_mut(&mut self) -> &mut Self::Target {
425        &mut self.0
426    }
427}
428
429impl From<ArrayPrelim> for In {
430    #[inline]
431    fn from(value: ArrayPrelim) -> Self {
432        In::Array(value)
433    }
434}
435
436impl<T> FromIterator<T> for ArrayPrelim
437where
438    T: Into<In>,
439{
440    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
441        ArrayPrelim(iter.into_iter().map(|v| v.into()).collect())
442    }
443}
444
445impl<I, T> From<I> for ArrayPrelim
446where
447    I: IntoIterator<Item = T>,
448    T: Into<In>,
449{
450    fn from(iter: I) -> Self {
451        ArrayPrelim(iter.into_iter().map(|v| v.into()).collect())
452    }
453}
454
455impl Prelim for ArrayPrelim {
456    type Return = ArrayRef;
457
458    fn into_content(self, _txn: &mut TransactionMut) -> (ItemContent, Option<Self>) {
459        let inner = Branch::new(TypeRef::Array);
460        (ItemContent::Type(inner), Some(self))
461    }
462
463    fn integrate(self, txn: &mut TransactionMut, inner_ref: BranchPtr) {
464        let array = ArrayRef::from(inner_ref);
465        for value in self.0 {
466            array.push_back(txn, value);
467        }
468    }
469}
470
471impl Into<EmbedPrelim<ArrayPrelim>> for ArrayPrelim {
472    #[inline]
473    fn into(self) -> EmbedPrelim<ArrayPrelim> {
474        EmbedPrelim::Shared(self)
475    }
476}
477
478/// Prelim range defines a way to insert multiple elements effectively at once one after another
479/// in an efficient way, provided that these elements correspond to a primitive JSON-like types.
480#[repr(transparent)]
481struct RangePrelim(Vec<Any>);
482
483impl RangePrelim {
484    fn new<I, T>(iter: I) -> Self
485    where
486        I: IntoIterator<Item = T>,
487        T: Into<Any>,
488    {
489        RangePrelim(iter.into_iter().map(|v| v.into()).collect())
490    }
491
492    #[inline]
493    fn is_empty(&self) -> bool {
494        self.0.is_empty()
495    }
496}
497
498impl Prelim for RangePrelim {
499    type Return = Unused;
500
501    fn into_content(self, _txn: &mut TransactionMut) -> (ItemContent, Option<Self>) {
502        (ItemContent::Any(self.0), None)
503    }
504
505    fn integrate(self, _txn: &mut TransactionMut, _inner_ref: BranchPtr) {}
506}
507
508/// Event generated by [ArrayRef::observe] method. Emitted during transaction commit phase.
509pub struct ArrayEvent {
510    pub(crate) current_target: BranchPtr,
511    target: ArrayRef,
512    change_set: UnsafeCell<Option<Box<ChangeSet<Change>>>>,
513}
514
515impl ArrayEvent {
516    pub(crate) fn new(branch_ref: BranchPtr) -> Self {
517        let current_target = branch_ref.clone();
518        ArrayEvent {
519            target: ArrayRef::from(branch_ref),
520            current_target,
521            change_set: UnsafeCell::new(None),
522        }
523    }
524
525    /// Returns an [ArrayRef] instance which emitted this event.
526    pub fn target(&self) -> &ArrayRef {
527        &self.target
528    }
529
530    /// Returns a path from root type down to [ArrayRef] instance which emitted this event.
531    pub fn path(&self) -> Path {
532        Branch::path(self.current_target, self.target.0)
533    }
534
535    /// Returns summary of changes made over corresponding [ArrayRef] collection within
536    /// a bounds of current transaction.
537    pub fn delta(&self, txn: &TransactionMut) -> &[Change] {
538        self.changes(txn).delta.as_slice()
539    }
540
541    /// Returns a collection of block identifiers that have been added within a bounds of
542    /// current transaction.
543    pub fn inserts(&self, txn: &TransactionMut) -> &HashSet<ID> {
544        &self.changes(txn).added
545    }
546
547    /// Returns a collection of block identifiers that have been removed within a bounds of
548    /// current transaction.
549    pub fn removes(&self, txn: &TransactionMut) -> &HashSet<ID> {
550        &self.changes(txn).deleted
551    }
552
553    fn changes(&self, txn: &TransactionMut) -> &ChangeSet<Change> {
554        let change_set = unsafe { self.change_set.get().as_mut().unwrap() };
555        change_set.get_or_insert_with(|| Box::new(event_change_set(txn, self.target.0.start)))
556    }
557}
558
559#[cfg(test)]
560mod test {
561    use crate::block::ClientID;
562    use crate::test_utils::{exchange_updates, run_scenario, RngExt};
563    use crate::types::map::MapPrelim;
564    use crate::types::{Change, DeepObservable, Event, Out, Path, PathSegment, ToJson};
565    use crate::{
566        any, Any, Array, ArrayPrelim, Assoc, Doc, Map, MapRef, Observable, SharedRef, StateVector,
567        Transact, Update, WriteTxn, ID,
568    };
569    use std::collections::{HashMap, HashSet};
570    use std::iter::FromIterator;
571    use std::sync::{Arc, Mutex};
572
573    #[test]
574    fn push_back() {
575        let doc = Doc::with_client_id(1);
576        let a = doc.get_or_insert_array("array");
577        let mut txn = doc.transact_mut();
578
579        a.push_back(&mut txn, "a");
580        a.push_back(&mut txn, "b");
581        a.push_back(&mut txn, "c");
582
583        let actual: Vec<_> = a.iter(&txn).collect();
584        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
585    }
586
587    #[test]
588    fn push_front() {
589        let doc = Doc::with_client_id(1);
590        let a = doc.get_or_insert_array("array");
591        let mut txn = doc.transact_mut();
592
593        a.push_front(&mut txn, "c");
594        a.push_front(&mut txn, "b");
595        a.push_front(&mut txn, "a");
596
597        let actual: Vec<_> = a.iter(&txn).collect();
598        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
599    }
600
601    #[test]
602    fn insert() {
603        let doc = Doc::with_client_id(1);
604        let a = doc.get_or_insert_array("array");
605        let mut txn = doc.transact_mut();
606
607        a.insert(&mut txn, 0, "a");
608        a.insert(&mut txn, 1, "c");
609        a.insert(&mut txn, 1, "b");
610
611        let actual: Vec<_> = a.iter(&txn).collect();
612        assert_eq!(actual, vec!["a".into(), "b".into(), "c".into()]);
613    }
614
615    #[test]
616    fn basic() {
617        let d1 = Doc::with_client_id(1);
618        let d2 = Doc::with_client_id(2);
619
620        let a1 = d1.get_or_insert_array("array");
621
622        a1.insert(&mut d1.transact_mut(), 0, "Hi");
623        let update = d1
624            .transact()
625            .encode_state_as_update_v1(&StateVector::default());
626
627        let a2 = d2.get_or_insert_array("array");
628        let mut t2 = d2.transact_mut();
629        t2.apply_update(Update::decode_v1(update.as_slice()).unwrap())
630            .unwrap();
631        let actual: Vec<_> = a2.iter(&t2).collect();
632
633        assert_eq!(actual, vec!["Hi".into()]);
634    }
635
636    #[test]
637    fn len() {
638        let d = Doc::with_client_id(1);
639        let a = d.get_or_insert_array("array");
640
641        {
642            let mut txn = d.transact_mut();
643
644            a.push_back(&mut txn, 0); // len: 1
645            a.push_back(&mut txn, 1); // len: 2
646            a.push_back(&mut txn, 2); // len: 3
647            a.push_back(&mut txn, 3); // len: 4
648
649            a.remove_range(&mut txn, 0, 1); // len: 3
650            a.insert(&mut txn, 0, 0); // len: 4
651
652            assert_eq!(a.len(&txn), 4);
653        }
654        {
655            let mut txn = d.transact_mut();
656            a.remove_range(&mut txn, 1, 1); // len: 3
657            assert_eq!(a.len(&txn), 3);
658
659            a.insert(&mut txn, 1, 1); // len: 4
660            assert_eq!(a.len(&txn), 4);
661
662            a.remove_range(&mut txn, 2, 1); // len: 3
663            assert_eq!(a.len(&txn), 3);
664
665            a.insert(&mut txn, 2, 2); // len: 4
666            assert_eq!(a.len(&txn), 4);
667        }
668
669        let mut txn = d.transact_mut();
670        assert_eq!(a.len(&txn), 4);
671
672        a.remove_range(&mut txn, 1, 1);
673        assert_eq!(a.len(&txn), 3);
674
675        a.insert(&mut txn, 1, 1);
676        assert_eq!(a.len(&txn), 4);
677    }
678
679    #[test]
680    fn remove_insert() {
681        let d1 = Doc::with_client_id(1);
682        let a1 = d1.get_or_insert_array("array");
683
684        let mut t1 = d1.transact_mut();
685        a1.insert(&mut t1, 0, "A");
686        a1.remove_range(&mut t1, 1, 0);
687    }
688
689    #[test]
690    fn insert_3_elements_try_re_get() {
691        let d1 = Doc::with_client_id(1);
692        let d2 = Doc::with_client_id(2);
693        let a1 = d1.get_or_insert_array("array");
694        {
695            let mut t1 = d1.transact_mut();
696
697            a1.push_back(&mut t1, 1);
698            a1.push_back(&mut t1, true);
699            a1.push_back(&mut t1, false);
700            let actual: Vec<_> = a1.iter(&t1).collect();
701            assert_eq!(
702                actual,
703                vec![Out::from(1.0), Out::from(true), Out::from(false)]
704            );
705        }
706
707        exchange_updates(&[&d1, &d2]);
708
709        let a2 = d2.get_or_insert_array("array");
710        let t2 = d2.transact();
711        let actual: Vec<_> = a2.iter(&t2).collect();
712        assert_eq!(
713            actual,
714            vec![Out::from(1.0), Out::from(true), Out::from(false)]
715        );
716    }
717
718    #[test]
719    fn concurrent_insert_with_3_conflicts() {
720        let d1 = Doc::with_client_id(1);
721        let a = d1.get_or_insert_array("array");
722        {
723            let mut txn = d1.transact_mut();
724            a.insert(&mut txn, 0, 0);
725        }
726
727        let d2 = Doc::with_client_id(2);
728        {
729            let mut txn = d1.transact_mut();
730            a.insert(&mut txn, 0, 1);
731        }
732
733        let d3 = Doc::with_client_id(3);
734        {
735            let mut txn = d1.transact_mut();
736            a.insert(&mut txn, 0, 2);
737        }
738
739        exchange_updates(&[&d1, &d2, &d3]);
740
741        let a1 = to_array(&d1);
742        let a2 = to_array(&d2);
743        let a3 = to_array(&d3);
744
745        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
746        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
747    }
748
749    fn to_array(d: &Doc) -> Vec<Out> {
750        let a = d.get_or_insert_array("array");
751        a.iter(&d.transact()).collect()
752    }
753
754    #[test]
755    fn concurrent_insert_remove_with_3_conflicts() {
756        let d1 = Doc::with_client_id(1);
757        {
758            let a = d1.get_or_insert_array("array");
759            let mut txn = d1.transact_mut();
760            a.insert_range(&mut txn, 0, ["x", "y", "z"]);
761        }
762        let d2 = Doc::with_client_id(2);
763        let d3 = Doc::with_client_id(3);
764
765        exchange_updates(&[&d1, &d2, &d3]);
766
767        {
768            // start state: [x,y,z]
769            let a1 = d1.get_or_insert_array("array");
770            let a2 = d2.get_or_insert_array("array");
771            let a3 = d3.get_or_insert_array("array");
772            let mut t1 = d1.transact_mut();
773            let mut t2 = d2.transact_mut();
774            let mut t3 = d3.transact_mut();
775
776            a1.insert(&mut t1, 1, 0); // [x,0,y,z]
777            a2.remove_range(&mut t2, 0, 1); // [y,z]
778            a2.remove_range(&mut t2, 1, 1); // [y]
779            a3.insert(&mut t3, 1, 2); // [x,2,y,z]
780        }
781
782        exchange_updates(&[&d1, &d2, &d3]);
783        // after exchange expected: [0,2,y]
784
785        let a1 = to_array(&d1);
786        let a2 = to_array(&d2);
787        let a3 = to_array(&d3);
788
789        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
790        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
791    }
792
793    #[test]
794    fn insertions_in_late_sync() {
795        let d1 = Doc::with_client_id(1);
796        {
797            let a = d1.get_or_insert_array("array");
798            let mut txn = d1.transact_mut();
799            a.push_back(&mut txn, "x");
800            a.push_back(&mut txn, "y");
801        }
802        let d2 = Doc::with_client_id(2);
803        let d3 = Doc::with_client_id(3);
804
805        exchange_updates(&[&d1, &d2, &d3]);
806
807        {
808            let a1 = d1.get_or_insert_array("array");
809            let a2 = d2.get_or_insert_array("array");
810            let a3 = d3.get_or_insert_array("array");
811            let mut t1 = d1.transact_mut();
812            let mut t2 = d2.transact_mut();
813            let mut t3 = d3.transact_mut();
814
815            a1.insert(&mut t1, 1, "user0");
816            a2.insert(&mut t2, 1, "user1");
817            a3.insert(&mut t3, 1, "user2");
818        }
819
820        exchange_updates(&[&d1, &d2, &d3]);
821
822        let a1 = to_array(&d1);
823        let a2 = to_array(&d2);
824        let a3 = to_array(&d3);
825
826        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
827        assert_eq!(a2, a3, "Peer 2 and peer 3 states are different");
828    }
829
830    #[test]
831    fn removals_in_late_sync() {
832        let d1 = Doc::with_client_id(1);
833        {
834            let a = d1.get_or_insert_array("array");
835            let mut txn = d1.transact_mut();
836            a.push_back(&mut txn, "x");
837            a.push_back(&mut txn, "y");
838        }
839        let d2 = Doc::with_client_id(2);
840
841        exchange_updates(&[&d1, &d2]);
842
843        {
844            let a1 = d1.get_or_insert_array("array");
845            let a2 = d2.get_or_insert_array("array");
846            let mut t1 = d1.transact_mut();
847            let mut t2 = d2.transact_mut();
848
849            a2.remove_range(&mut t2, 1, 1);
850            a1.remove_range(&mut t1, 0, 2);
851        }
852
853        exchange_updates(&[&d1, &d2]);
854
855        let a1 = to_array(&d1);
856        let a2 = to_array(&d2);
857
858        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
859    }
860
861    #[test]
862    fn insert_then_merge_delete_on_sync() {
863        let d1 = Doc::with_client_id(1);
864        {
865            let a = d1.get_or_insert_array("array");
866            let mut txn = d1.transact_mut();
867            a.push_back(&mut txn, "x");
868            a.push_back(&mut txn, "y");
869            a.push_back(&mut txn, "z");
870        }
871        let d2 = Doc::with_client_id(2);
872
873        exchange_updates(&[&d1, &d2]);
874
875        {
876            let a2 = d2.get_or_insert_array("array");
877            let mut t2 = d2.transact_mut();
878
879            a2.remove_range(&mut t2, 0, 3);
880        }
881
882        exchange_updates(&[&d1, &d2]);
883
884        let a1 = to_array(&d1);
885        let a2 = to_array(&d2);
886
887        assert_eq!(a1, a2, "Peer 1 and peer 2 states are different");
888    }
889
890    #[test]
891    fn iter_array_containing_types() {
892        let d = Doc::with_client_id(1);
893        let a = d.get_or_insert_array("arr");
894        let mut txn = d.transact_mut();
895        for i in 0..10 {
896            let mut m = HashMap::new();
897            m.insert("value".to_owned(), i);
898            a.push_back(&mut txn, MapPrelim::from_iter(m));
899        }
900
901        for (i, value) in a.iter(&txn).enumerate() {
902            match value {
903                Out::YMap(_) => {
904                    assert_eq!(value.to_json(&txn), any!({"value": (i as f64) }))
905                }
906                _ => panic!("Value of array at index {} was no YMap", i),
907            }
908        }
909    }
910
911    #[test]
912    fn insert_and_remove_events() {
913        let d = Doc::with_client_id(1);
914        let array = d.get_or_insert_array("array");
915        let happened = Arc::new(AtomicBool::new(false));
916        let happened_clone = happened.clone();
917        let _sub = array.observe(move |_, _| {
918            happened_clone.store(true, Ordering::Relaxed);
919        });
920
921        {
922            let mut txn = d.transact_mut();
923            array.insert_range(&mut txn, 0, [0, 1, 2]);
924            // txn is committed at the end of this scope
925        }
926        assert!(
927            happened.swap(false, Ordering::Relaxed),
928            "insert of [0,1,2] should trigger event"
929        );
930
931        {
932            let mut txn = d.transact_mut();
933            array.remove_range(&mut txn, 0, 1);
934            // txn is committed at the end of this scope
935        }
936        assert!(
937            happened.swap(false, Ordering::Relaxed),
938            "removal of [0] should trigger event"
939        );
940
941        {
942            let mut txn = d.transact_mut();
943            array.remove_range(&mut txn, 0, 2);
944            // txn is committed at the end of this scope
945        }
946        assert!(
947            happened.swap(false, Ordering::Relaxed),
948            "removal of [1,2] should trigger event"
949        );
950    }
951
952    #[test]
953    fn insert_and_remove_event_changes() {
954        let d1 = Doc::with_client_id(1);
955        let array = d1.get_or_insert_array("array");
956        let added = Arc::new(ArcSwapOption::default());
957        let removed = Arc::new(ArcSwapOption::default());
958        let delta = Arc::new(ArcSwapOption::default());
959
960        let (added_c, removed_c, delta_c) = (added.clone(), removed.clone(), delta.clone());
961        let _sub = array.observe(move |txn, e| {
962            added_c.store(Some(Arc::new(e.inserts(txn).clone())));
963            removed_c.store(Some(Arc::new(e.removes(txn).clone())));
964            delta_c.store(Some(Arc::new(e.delta(txn).to_vec())));
965        });
966
967        {
968            let mut txn = d1.transact_mut();
969            array.push_back(&mut txn, 4);
970            array.push_back(&mut txn, "dtrn");
971            // txn is committed at the end of this scope
972        }
973        assert_eq!(
974            added.swap(None),
975            Some(
976                HashSet::from([ID::new(ClientID::new(1), 0), ID::new(ClientID::new(1), 1)]).into()
977            )
978        );
979        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
980        assert_eq!(
981            delta.swap(None),
982            Some(
983                vec![Change::Added(vec![
984                    Any::Number(4.0).into(),
985                    Any::String("dtrn".into()).into()
986                ])]
987                .into()
988            )
989        );
990
991        {
992            let mut txn = d1.transact_mut();
993            array.remove_range(&mut txn, 0, 1);
994        }
995        assert_eq!(added.swap(None), Some(HashSet::new().into()));
996        assert_eq!(
997            removed.swap(None),
998            Some(HashSet::from([ID::new(ClientID::new(1), 0)]).into())
999        );
1000        assert_eq!(delta.swap(None), Some(vec![Change::Removed(1)].into()));
1001
1002        {
1003            let mut txn = d1.transact_mut();
1004            array.insert(&mut txn, 1, 0.5);
1005        }
1006        assert_eq!(
1007            added.swap(None),
1008            Some(HashSet::from([ID::new(ClientID::new(1), 2)]).into())
1009        );
1010        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
1011        assert_eq!(
1012            delta.swap(None),
1013            Some(
1014                vec![
1015                    Change::Retain(1),
1016                    Change::Added(vec![Any::Number(0.5).into()])
1017                ]
1018                .into()
1019            )
1020        );
1021
1022        let d2 = Doc::with_client_id(2);
1023        let array2 = d2.get_or_insert_array("array");
1024        let (added_c, removed_c, delta_c) = (added.clone(), removed.clone(), delta.clone());
1025        let _sub = array2.observe(move |txn, e| {
1026            added_c.store(Some(e.inserts(txn).clone().into()));
1027            removed_c.store(Some(e.removes(txn).clone().into()));
1028            delta_c.store(Some(e.delta(txn).to_vec().into()));
1029        });
1030
1031        {
1032            let t1 = d1.transact_mut();
1033            let mut t2 = d2.transact_mut();
1034
1035            let sv = t2.state_vector();
1036            let mut encoder = EncoderV1::new();
1037            t1.encode_diff(&sv, &mut encoder);
1038            t2.apply_update(Update::decode_v1(encoder.to_vec().as_slice()).unwrap())
1039                .unwrap();
1040        }
1041
1042        assert_eq!(
1043            added.swap(None),
1044            Some(HashSet::from([ID::new(ClientID::new(1), 1)]).into())
1045        );
1046        assert_eq!(removed.swap(None), Some(HashSet::new().into()));
1047        assert_eq!(
1048            delta.swap(None),
1049            Some(
1050                vec![Change::Added(vec![
1051                    Any::String("dtrn".into()).into(),
1052                    Any::Number(0.5).into(),
1053                ])]
1054                .into()
1055            )
1056        );
1057    }
1058
1059    #[test]
1060    fn target_on_local_and_remote() {
1061        let d1 = Doc::with_client_id(1);
1062        let d2 = Doc::with_client_id(2);
1063        let a1 = d1.get_or_insert_array("array");
1064        let a2 = d2.get_or_insert_array("array");
1065
1066        let c1 = Arc::new(ArcSwapOption::default());
1067        let c1c = c1.clone();
1068        let _s1 = a1.observe(move |_, e| {
1069            c1c.store(Some(e.target().hook().into()));
1070        });
1071        let c2 = Arc::new(ArcSwapOption::default());
1072        let c2c = c2.clone();
1073        let _s2 = a2.observe(move |_, e| {
1074            c2c.store(Some(e.target().hook().into()));
1075        });
1076
1077        {
1078            let mut t1 = d1.transact_mut();
1079            a1.insert_range(&mut t1, 0, [1, 2]);
1080        }
1081        exchange_updates(&[&d1, &d2]);
1082
1083        assert_eq!(c1.swap(None), Some(Arc::new(a1.hook())));
1084        assert_eq!(c2.swap(None), Some(Arc::new(a2.hook())));
1085    }
1086
1087    use crate::transaction::ReadTxn;
1088    use crate::updates::decoder::Decode;
1089    use crate::updates::encoder::{Encoder, EncoderV1};
1090    use arc_swap::ArcSwapOption;
1091    use fastrand::Rng;
1092    use std::sync::atomic::{AtomicBool, AtomicI64, Ordering};
1093    use std::time::Duration;
1094
1095    static UNIQUE_NUMBER: AtomicI64 = AtomicI64::new(0);
1096
1097    fn get_unique_number() -> i64 {
1098        UNIQUE_NUMBER.fetch_add(1, Ordering::SeqCst)
1099    }
1100
1101    fn array_transactions() -> [Box<dyn Fn(&mut Doc, &mut Rng)>; 4] {
1102        fn insert(doc: &mut Doc, rng: &mut Rng) {
1103            let yarray = doc.get_or_insert_array("array");
1104            let mut txn = doc.transact_mut();
1105            let unique_number = get_unique_number();
1106            let len = rng.between(1, 4);
1107            let content: Vec<_> = (0..len)
1108                .into_iter()
1109                .map(|_| Any::BigInt(unique_number))
1110                .collect();
1111            let mut pos = rng.between(0, yarray.len(&txn)) as usize;
1112            if let Any::Array(expected) = yarray.to_json(&txn) {
1113                let mut expected = Vec::from(expected.as_ref());
1114                yarray.insert_range(&mut txn, pos as u32, content.clone());
1115
1116                for any in content {
1117                    expected.insert(pos, any);
1118                    pos += 1;
1119                }
1120                let actual = yarray.to_json(&txn);
1121                assert_eq!(actual, Any::from(expected))
1122            } else {
1123                panic!("should not happen")
1124            }
1125        }
1126
1127        fn insert_type_array(doc: &mut Doc, rng: &mut Rng) {
1128            let yarray = doc.get_or_insert_array("array");
1129            let mut txn = doc.transact_mut();
1130            let pos = rng.between(0, yarray.len(&txn));
1131            let array2 = yarray.insert(&mut txn, pos, ArrayPrelim::from([1, 2, 3, 4]));
1132            let expected: Arc<[Any]> = (1..=4).map(|i| Any::Number(i as f64)).collect();
1133            assert_eq!(array2.to_json(&txn), Any::Array(expected));
1134        }
1135
1136        fn insert_type_map(doc: &mut Doc, rng: &mut Rng) {
1137            let yarray = doc.get_or_insert_array("array");
1138            let mut txn = doc.transact_mut();
1139            let pos = rng.between(0, yarray.len(&txn));
1140            let map = yarray.insert(&mut txn, pos, MapPrelim::default());
1141            map.insert(&mut txn, "someprop".to_string(), 42);
1142            map.insert(&mut txn, "someprop".to_string(), 43);
1143            map.insert(&mut txn, "someprop".to_string(), 44);
1144        }
1145
1146        fn delete(doc: &mut Doc, rng: &mut Rng) {
1147            let yarray = doc.get_or_insert_array("array");
1148            let mut txn = doc.transact_mut();
1149            let len = yarray.len(&txn);
1150            if len > 0 {
1151                let pos = rng.between(0, len - 1);
1152                let del_len = rng.between(1, 2.min(len - pos));
1153                if rng.bool() {
1154                    if let Out::YArray(array2) = yarray.get(&txn, pos).unwrap() {
1155                        let pos = rng.between(0, array2.len(&txn) - 1);
1156                        let del_len = rng.between(0, 2.min(array2.len(&txn) - pos));
1157                        array2.remove_range(&mut txn, pos, del_len);
1158                    }
1159                } else {
1160                    if let Any::Array(old_content) = yarray.to_json(&txn) {
1161                        let mut old_content = Vec::from(old_content.as_ref());
1162                        yarray.remove_range(&mut txn, pos, del_len);
1163                        old_content.drain(pos as usize..(pos + del_len) as usize);
1164                        assert_eq!(yarray.to_json(&txn), Any::from(old_content));
1165                    } else {
1166                        panic!("should not happen")
1167                    }
1168                }
1169            }
1170        }
1171
1172        [
1173            Box::new(insert),
1174            Box::new(insert_type_array),
1175            Box::new(insert_type_map),
1176            Box::new(delete),
1177        ]
1178    }
1179
1180    fn fuzzy(iterations: usize) {
1181        run_scenario(0, &array_transactions(), 5, iterations)
1182    }
1183
1184    #[test]
1185    fn fuzzy_test_6() {
1186        fuzzy(6)
1187    }
1188
1189    #[test]
1190    fn fuzzy_test_300() {
1191        fuzzy(300)
1192    }
1193
1194    #[test]
1195    fn get_at_removed_index() {
1196        let d1 = Doc::with_client_id(1);
1197        let a1 = d1.get_or_insert_array("array");
1198        let mut t1 = d1.transact_mut();
1199
1200        a1.insert_range(&mut t1, 0, ["A"]);
1201        a1.remove(&mut t1, 0);
1202
1203        let actual = a1.get(&t1, 0);
1204        assert_eq!(actual, None);
1205    }
1206
1207    #[test]
1208    fn observe_deep_event_order() {
1209        let doc = Doc::with_client_id(1);
1210        let array = doc.get_or_insert_array("array");
1211
1212        let paths = Arc::new(Mutex::new(vec![]));
1213        let paths_copy = paths.clone();
1214
1215        let _sub = array.observe_deep(move |_txn, e| {
1216            let path: Vec<Path> = e.iter().map(Event::path).collect();
1217            paths_copy.lock().unwrap().push(path);
1218        });
1219
1220        array.insert(&mut doc.transact_mut(), 0, MapPrelim::default());
1221
1222        {
1223            let mut txn = doc.transact_mut();
1224            let map = array.get(&txn, 0).unwrap().cast::<MapRef>().unwrap();
1225            map.insert(&mut txn, "a", "a");
1226            array.insert(&mut txn, 0, 0);
1227        }
1228
1229        let expected = &[
1230            vec![Path::default()],
1231            vec![Path::default(), Path::from([PathSegment::Index(1)])],
1232        ];
1233        let actual = paths.lock().unwrap();
1234        assert_eq!(actual.as_slice(), expected);
1235    }
1236
1237    #[test]
1238    fn multi_threading() {
1239        use std::sync::{Arc, RwLock};
1240        use std::thread::{sleep, spawn};
1241
1242        let doc = Arc::new(RwLock::new(Doc::with_client_id(1)));
1243
1244        let d2 = doc.clone();
1245        let h2 = spawn(move || {
1246            for _ in 0..10 {
1247                let millis = fastrand::u64(1..20);
1248                sleep(Duration::from_millis(millis));
1249
1250                let doc = d2.write().unwrap();
1251                let array = doc.get_or_insert_array("test");
1252                let mut txn = doc.transact_mut();
1253                array.push_back(&mut txn, "a");
1254            }
1255        });
1256
1257        let d3 = doc.clone();
1258        let h3 = spawn(move || {
1259            for _ in 0..10 {
1260                let millis = fastrand::u64(1..20);
1261                sleep(Duration::from_millis(millis));
1262
1263                let doc = d3.write().unwrap();
1264                let array = doc.get_or_insert_array("test");
1265                let mut txn = doc.transact_mut();
1266                array.push_back(&mut txn, "b");
1267            }
1268        });
1269
1270        h3.join().unwrap();
1271        h2.join().unwrap();
1272
1273        let doc = doc.read().unwrap();
1274        let array = doc.get_or_insert_array("test");
1275        let len = array.len(&doc.transact());
1276        assert_eq!(len, 20);
1277    }
1278
1279    #[test]
1280    fn insert_empty_range() {
1281        let doc = Doc::with_client_id(1);
1282        let mut txn = doc.transact_mut();
1283        let array = txn.get_or_insert_array("array");
1284
1285        array.insert(&mut txn, 0, 1);
1286        array.insert_range::<_, Any>(&mut txn, 1, []);
1287        array.push_back(&mut txn, 2);
1288
1289        assert_eq!(
1290            array.iter(&txn).collect::<Vec<_>>(),
1291            vec![1.into(), 2.into()]
1292        );
1293
1294        let data = txn.encode_state_as_update_v1(&StateVector::default());
1295
1296        let doc2 = Doc::with_client_id(2);
1297        let mut txn = doc2.transact_mut();
1298        let array = txn.get_or_insert_array("array");
1299        txn.apply_update(Update::decode_v1(&data).unwrap()).unwrap();
1300
1301        assert_eq!(
1302            array.iter(&txn).collect::<Vec<_>>(),
1303            vec![1.into(), 2.into()]
1304        );
1305    }
1306}
yrs/types/array.rs

yrs/types/
array.rs
