yrs/types/
map.rs

1use crate::block::{EmbedPrelim, ItemContent, ItemPosition, ItemPtr, Prelim};
2use crate::encoding::read::Error;
3use crate::encoding::serde::from_any;
4use crate::transaction::TransactionMut;
5use crate::types::{
6    event_keys, AsPrelim, Branch, BranchPtr, DefaultPrelim, Entries, EntryChange, In, Out, Path,
7    RootRef, SharedRef, ToJson, TypeRef,
8};
9use crate::*;
10use serde::de::DeserializeOwned;
11use std::borrow::Borrow;
12use std::cell::UnsafeCell;
13use std::collections::{HashMap, HashSet};
14use std::convert::{TryFrom, TryInto};
15use std::iter::FromIterator;
16use std::ops::{Deref, DerefMut};
17use std::sync::Arc;
18
19/// Collection used to store key-value entries in an unordered manner. Keys are always represented
20/// as UTF-8 strings. Values can be any value type supported by Yrs: JSON-like primitives as well as
21/// shared data types.
22///
23/// In terms of conflict resolution, [MapRef] uses logical last-write-wins principle, meaning the past
24/// updates are automatically overridden and discarded by newer ones, while concurrent updates made
25/// by different peers are resolved into a single value using document id seniority to establish
26/// order.
27///
28/// # Example
29///
30/// ```rust
31/// use yrs::{any, Doc, Map, MapPrelim, Transact};
32/// use yrs::types::ToJson;
33///
34/// let doc = Doc::new();
35/// let map = doc.get_or_insert_map("map");
36/// let mut txn = doc.transact_mut();
37///
38/// // insert value
39/// map.insert(&mut txn, "key1", "value1");
40///
41/// // insert nested shared type
42/// let nested = map.insert(&mut txn, "key2", MapPrelim::from([("inner", "value2")]));
43/// nested.insert(&mut txn, "inner2", 100);
44///
45/// assert_eq!(map.to_json(&txn), any!({
46///   "key1": "value1",
47///   "key2": {
48///     "inner": "value2",
49///     "inner2": 100
50///   }
51/// }));
52///
53/// // get value
54/// assert_eq!(map.get(&txn, "key1"), Some("value1".into()));
55///
56/// // remove entry
57/// map.remove(&mut txn, "key1");
58/// assert_eq!(map.get(&txn, "key1"), None);
59/// ```
60#[repr(transparent)]
61#[derive(Debug, Clone)]
62pub struct MapRef(BranchPtr);
63
64impl RootRef for MapRef {
65    fn type_ref() -> TypeRef {
66        TypeRef::Map
67    }
68}
69impl SharedRef for MapRef {}
70impl Map for MapRef {}
71
72impl DeepObservable for MapRef {}
73impl Observable for MapRef {
74    type Event = MapEvent;
75}
76
77impl ToJson for MapRef {
78    fn to_json<T: ReadTxn>(&self, txn: &T) -> Any {
79        let inner = self.0;
80        let mut res = HashMap::new();
81        for (key, item) in inner.map.iter() {
82            if !item.is_deleted() {
83                let last = item.content.get_last().unwrap_or(Out::Any(Any::Null));
84                res.insert(key.to_string(), last.to_json(txn));
85            }
86        }
87        Any::from(res)
88    }
89}
90
91impl AsRef<Branch> for MapRef {
92    fn as_ref(&self) -> &Branch {
93        self.0.deref()
94    }
95}
96
97impl Eq for MapRef {}
98impl PartialEq for MapRef {
99    fn eq(&self, other: &Self) -> bool {
100        self.0.id() == other.0.id()
101    }
102}
103
104impl TryFrom<ItemPtr> for MapRef {
105    type Error = ItemPtr;
106
107    fn try_from(value: ItemPtr) -> Result<Self, Self::Error> {
108        if let Some(branch) = value.clone().as_branch() {
109            Ok(MapRef::from(branch))
110        } else {
111            Err(value)
112        }
113    }
114}
115
116impl TryFrom<Out> for MapRef {
117    type Error = Out;
118
119    fn try_from(value: Out) -> Result<Self, Self::Error> {
120        match value {
121            Out::YMap(value) => Ok(value),
122            other => Err(other),
123        }
124    }
125}
126
127impl AsPrelim for MapRef {
128    type Prelim = MapPrelim;
129
130    fn as_prelim<T: ReadTxn>(&self, txn: &T) -> Self::Prelim {
131        let mut prelim = HashMap::with_capacity(self.len(txn) as usize);
132        for (key, &ptr) in self.0.map.iter() {
133            if !ptr.is_deleted() {
134                if let Ok(value) = Out::try_from(ptr) {
135                    prelim.insert(key.clone(), value.as_prelim(txn));
136                }
137            }
138        }
139        MapPrelim(prelim)
140    }
141}
142
143impl DefaultPrelim for MapRef {
144    type Prelim = MapPrelim;
145
146    #[inline]
147    fn default_prelim() -> Self::Prelim {
148        MapPrelim::default()
149    }
150}
151
152pub trait Map: AsRef<Branch> + Sized {
153    /// Returns a number of entries stored within current map.
154    fn len<T: ReadTxn>(&self, _txn: &T) -> u32 {
155        let mut len = 0;
156        let inner = self.as_ref();
157        for item in inner.map.values() {
158            //TODO: maybe it would be better to just cache len in the map itself?
159            if !item.is_deleted() {
160                len += 1;
161            }
162        }
163        len
164    }
165
166    /// Returns an iterator that enables to traverse over all keys of entries stored within
167    /// current map. These keys are not ordered.
168    fn keys<'a, T: ReadTxn + 'a>(&'a self, txn: &'a T) -> Keys<'a, &'a T, T> {
169        Keys::new(self.as_ref(), txn)
170    }
171
172    /// Returns an iterator that enables to traverse over all values stored within current map.
173    fn values<'a, T: ReadTxn + 'a>(&'a self, txn: &'a T) -> Values<'a, &'a T, T> {
174        Values::new(self.as_ref(), txn)
175    }
176
177    /// Returns an iterator that enables to traverse over all entries - tuple of key-value pairs -
178    /// stored within current map.
179    fn iter<'a, T: ReadTxn + 'a>(&'a self, txn: &'a T) -> MapIter<'a, &'a T, T> {
180        MapIter::new(self.as_ref(), txn)
181    }
182
183    fn into_iter<'a, T: ReadTxn + 'a>(self, txn: &'a T) -> MapIntoIter<'a, T> {
184        let branch_ptr = BranchPtr::from(self.as_ref());
185        MapIntoIter::new(branch_ptr, txn)
186    }
187
188    /// Inserts a new `value` under given `key` into current map. Returns an integrated value.
189    fn insert<K, V>(&self, txn: &mut TransactionMut, key: K, value: V) -> V::Return
190    where
191        K: Into<Arc<str>>,
192        V: Prelim,
193    {
194        let key = key.into();
195        let pos = {
196            let inner = self.as_ref();
197            let left = inner.map.get(&key);
198            ItemPosition {
199                parent: BranchPtr::from(inner).into(),
200                left: left.cloned(),
201                right: None,
202                index: 0,
203                current_attrs: None,
204            }
205        };
206
207        let ptr = txn
208            .create_item(&pos, value, Some(key))
209            .expect("Cannot insert empty value");
210        if let Ok(integrated) = ptr.try_into() {
211            integrated
212        } else {
213            panic!("Defect: unexpected integrated type")
214        }
215    }
216
217    /// Tries to update a value stored under a given `key` within current map, if it's different
218    /// from the current one. Returns `true` if the value was updated, `false` otherwise.
219    ///
220    /// The main difference from [Map::insert] is that this method will not insert a new value if
221    /// it's the same as the current one. It's important distinction when dealing with shared types,
222    /// as inserting an element will force previous value to be tombstoned, causing minimal memory
223    /// overhead.
224    ///
225    /// # Example
226    ///
227    /// ```rust
228    /// use yrs::{Doc, Map, Transact, WriteTxn};
229    ///
230    /// let doc = Doc::new();
231    /// let mut txn = doc.transact_mut();
232    /// let map = txn.get_or_insert_map("map");
233    ///
234    /// assert!(map.try_update(&mut txn, "key", 1)); // created a new entry
235    /// assert!(!map.try_update(&mut txn, "key", 1)); // unchanged value doesn't trigger inserts...
236    /// assert!(map.try_update(&mut txn, "key", 2)); // ... but changed one does
237    /// ```
238    fn try_update<K, V>(&self, txn: &mut TransactionMut, key: K, value: V) -> bool
239    where
240        K: Into<Arc<str>>,
241        V: Into<Any>,
242    {
243        let key = key.into();
244        let value = value.into();
245        let branch = self.as_ref();
246        if let Some(item) = branch.map.get(&key) {
247            if !item.is_deleted() {
248                if let ItemContent::Any(content) = &item.content {
249                    if let Some(last) = content.last() {
250                        if last == &value {
251                            return false;
252                        }
253                    }
254                }
255            }
256        }
257
258        self.insert(txn, key, value);
259        true
260    }
261
262    /// Returns an existing instance of a type stored under a given `key` within current map.
263    /// If the given entry was not found, has been deleted or its type is different from expected,
264    /// that entry will be reset to a given type and its reference will be returned.
265    fn get_or_init<K, V>(&self, txn: &mut TransactionMut, key: K) -> V
266    where
267        K: Into<Arc<str>>,
268        V: DefaultPrelim + TryFrom<Out>,
269    {
270        let key = key.into();
271        let branch = self.as_ref();
272        if let Some(value) = branch.get(txn, &key) {
273            if let Ok(value) = value.try_into() {
274                return value;
275            }
276        }
277        let value = V::default_prelim();
278        self.insert(txn, key, value)
279    }
280
281    /// Removes a stored within current map under a given `key`. Returns that value or `None` if
282    /// no entry with a given `key` was present in current map.
283    ///
284    /// ### Removing nested shared types
285    ///
286    /// In case when a nested shared type (eg. [MapRef], [ArrayRef], [TextRef]) is being removed,
287    /// all of its contents will also be deleted recursively. A returned value will contain a
288    /// reference to a current removed shared type (which will be empty due to all of its elements
289    /// being deleted), **not** the content prior the removal.
290    fn remove(&self, txn: &mut TransactionMut, key: &str) -> Option<Out> {
291        let ptr = BranchPtr::from(self.as_ref());
292        ptr.remove(txn, key)
293    }
294
295    /// Returns [WeakPrelim] to a given `key`, if it exists in a current map.
296    #[cfg(feature = "weak")]
297    fn link<T: ReadTxn>(&self, _txn: &T, key: &str) -> Option<crate::WeakPrelim<Self>> {
298        let ptr = BranchPtr::from(self.as_ref());
299        let block = ptr.map.get(key)?;
300        let start = StickyIndex::from_id(block.id().clone(), Assoc::Before);
301        let end = StickyIndex::from_id(block.id().clone(), Assoc::After);
302        let link = crate::WeakPrelim::new(start, end);
303        Some(link)
304    }
305
306    /// Returns a value stored under a given `key` within current map, or `None` if no entry
307    /// with such `key` existed.
308    fn get<T: ReadTxn>(&self, txn: &T, key: &str) -> Option<Out> {
309        let ptr = BranchPtr::from(self.as_ref());
310        ptr.get(txn, key)
311    }
312
313    /// Returns a value stored under a given `key` within current map, deserializing it into expected
314    /// type if found. If value was not found, the `Any::Null` will be substituted and deserialized
315    /// instead (i.e. into instance of `Option` type, if so desired).
316    ///
317    /// # Example
318    ///
319    /// ```rust
320    /// use yrs::{Doc, In, Map, MapPrelim, Transact, WriteTxn};
321    ///
322    /// let doc = Doc::new();
323    /// let mut txn = doc.transact_mut();
324    /// let map = txn.get_or_insert_map("map");
325    ///
326    /// // insert a multi-nested shared refs
327    /// let alice = map.insert(&mut txn, "Alice", MapPrelim::from([
328    ///   ("name", In::from("Alice")),
329    ///   ("age", In::from(30)),
330    ///   ("address", MapPrelim::from([
331    ///     ("city", In::from("London")),
332    ///     ("street", In::from("Baker st.")),
333    ///   ]).into())
334    /// ]));
335    ///
336    /// // define Rust types to map from the shared refs
337    ///
338    /// #[derive(Debug, PartialEq, serde::Deserialize)]
339    /// struct Person {
340    ///   name: String,
341    ///   age: u32,
342    ///   address: Option<Address>,
343    /// }
344    ///
345    /// #[derive(Debug, PartialEq, serde::Deserialize)]
346    /// struct Address {
347    ///   city: String,
348    ///   street: String,
349    /// }
350    ///
351    /// // retrieve and deserialize the value across multiple shared refs
352    /// let alice: Person = map.get_as(&txn, "Alice").unwrap();
353    /// assert_eq!(alice, Person {
354    ///   name: "Alice".to_string(),
355    ///   age: 30,
356    ///   address: Some(Address {
357    ///     city: "London".to_string(),
358    ///     street: "Baker st.".to_string(),
359    ///   })
360    /// });
361    ///
362    /// // try to retrieve value that doesn't exist
363    /// let bob: Option<Person> = map.get_as(&txn, "Bob").unwrap();
364    /// assert_eq!(bob, None);
365    /// ```
366    fn get_as<T, V>(&self, txn: &T, key: &str) -> Result<V, Error>
367    where
368        T: ReadTxn,
369        V: DeserializeOwned,
370    {
371        let ptr = BranchPtr::from(self.as_ref());
372        let out = ptr.get(txn, key).unwrap_or(Out::Any(Any::Null));
373        //TODO: we could probably optimize this step by not serializing to intermediate Any value
374        let any = out.to_json(txn);
375        from_any(&any)
376    }
377
378    /// Checks if an entry with given `key` can be found within current map.
379    fn contains_key<T: ReadTxn>(&self, _txn: &T, key: &str) -> bool {
380        if let Some(item) = self.as_ref().map.get(key) {
381            !item.is_deleted()
382        } else {
383            false
384        }
385    }
386
387    /// Clears the contents of current map, effectively removing all of its entries.
388    fn clear(&self, txn: &mut TransactionMut) {
389        for (_, ptr) in self.as_ref().map.iter() {
390            txn.delete(ptr.clone());
391        }
392    }
393}
394
395pub struct MapIter<'a, B, T>(Entries<'a, B, T>);
396
397impl<'a, B, T> MapIter<'a, B, T>
398where
399    B: Borrow<T>,
400    T: ReadTxn,
401{
402    pub fn new(branch: &'a Branch, txn: B) -> Self {
403        let entries = Entries::new(&branch.map, txn);
404        MapIter(entries)
405    }
406}
407
408impl<'a, B, T> Iterator for MapIter<'a, B, T>
409where
410    B: Borrow<T>,
411    T: ReadTxn,
412{
413    type Item = (&'a str, Out);
414
415    fn next(&mut self) -> Option<Self::Item> {
416        let (key, item) = self.0.next()?;
417        if let Some(content) = item.content.get_last() {
418            Some((key, content))
419        } else {
420            self.next()
421        }
422    }
423}
424
425pub struct MapIntoIter<'a, T> {
426    _txn: &'a T,
427    entries: std::collections::hash_map::IntoIter<Arc<str>, ItemPtr>,
428}
429
430impl<'a, T: ReadTxn> MapIntoIter<'a, T> {
431    fn new(map: BranchPtr, txn: &'a T) -> Self {
432        let entries = map.map.clone().into_iter();
433        MapIntoIter { _txn: txn, entries }
434    }
435}
436
437impl<'a, T: ReadTxn> Iterator for MapIntoIter<'a, T> {
438    type Item = (Arc<str>, Out);
439
440    fn next(&mut self) -> Option<Self::Item> {
441        let (key, item) = self.entries.next()?;
442        if let Some(content) = item.content.get_last() {
443            Some((key, content))
444        } else {
445            self.next()
446        }
447    }
448}
449
450/// An unordered iterator over the keys of a [Map].
451#[derive(Debug)]
452pub struct Keys<'a, B, T>(Entries<'a, B, T>);
453
454impl<'a, B, T> Keys<'a, B, T>
455where
456    B: Borrow<T>,
457    T: ReadTxn,
458{
459    pub fn new(branch: &'a Branch, txn: B) -> Self {
460        let entries = Entries::new(&branch.map, txn);
461        Keys(entries)
462    }
463}
464
465impl<'a, B, T> Iterator for Keys<'a, B, T>
466where
467    B: Borrow<T>,
468    T: ReadTxn,
469{
470    type Item = &'a str;
471
472    fn next(&mut self) -> Option<Self::Item> {
473        let (key, _) = self.0.next()?;
474        Some(key)
475    }
476}
477
478/// Iterator over the values of a [Map].
479#[derive(Debug)]
480pub struct Values<'a, B, T>(Entries<'a, B, T>);
481
482impl<'a, B, T> Values<'a, B, T>
483where
484    B: Borrow<T>,
485    T: ReadTxn,
486{
487    pub fn new(branch: &'a Branch, txn: B) -> Self {
488        let entries = Entries::new(&branch.map, txn);
489        Values(entries)
490    }
491}
492
493impl<'a, B, T> Iterator for Values<'a, B, T>
494where
495    B: Borrow<T>,
496    T: ReadTxn,
497{
498    type Item = Vec<Out>;
499
500    fn next(&mut self) -> Option<Self::Item> {
501        let (_, item) = self.0.next()?;
502        let len = item.len() as usize;
503        let mut values = vec![Out::default(); len];
504        if item.content.read(0, &mut values) == len {
505            Some(values)
506        } else {
507            panic!("Defect: iterator didn't read all elements")
508        }
509    }
510}
511
512impl From<BranchPtr> for MapRef {
513    fn from(inner: BranchPtr) -> Self {
514        MapRef(inner)
515    }
516}
517
518/// A preliminary map. It can be used to early initialize the contents of a [MapRef], when it's about
519/// to be inserted into another Yrs collection, such as [ArrayRef] or another [MapRef].
520#[repr(transparent)]
521#[derive(Debug, Clone, PartialEq, Default)]
522pub struct MapPrelim(HashMap<Arc<str>, In>);
523
524impl Deref for MapPrelim {
525    type Target = HashMap<Arc<str>, In>;
526
527    #[inline]
528    fn deref(&self) -> &Self::Target {
529        &self.0
530    }
531}
532
533impl DerefMut for MapPrelim {
534    #[inline]
535    fn deref_mut(&mut self) -> &mut Self::Target {
536        &mut self.0
537    }
538}
539
540impl From<MapPrelim> for In {
541    #[inline]
542    fn from(value: MapPrelim) -> Self {
543        In::Map(value)
544    }
545}
546
547impl<S, T> FromIterator<(S, T)> for MapPrelim
548where
549    S: Into<Arc<str>>,
550    T: Into<In>,
551{
552    fn from_iter<I: IntoIterator<Item = (S, T)>>(iter: I) -> Self {
553        MapPrelim(
554            iter.into_iter()
555                .map(|(k, v)| (k.into(), v.into()))
556                .collect(),
557        )
558    }
559}
560
561impl<S, T, const C: usize> From<[(S, T); C]> for MapPrelim
562where
563    S: Into<Arc<str>>,
564    T: Into<In>,
565{
566    fn from(map: [(S, T); C]) -> Self {
567        let mut m = HashMap::with_capacity(C);
568        for (key, value) in map {
569            m.insert(key.into(), value.into());
570        }
571        MapPrelim(m)
572    }
573}
574
575impl Prelim for MapPrelim {
576    type Return = MapRef;
577
578    fn into_content(self, _txn: &mut TransactionMut) -> (ItemContent, Option<Self>) {
579        let inner = Branch::new(TypeRef::Map);
580        (ItemContent::Type(inner), Some(self))
581    }
582
583    fn integrate(self, txn: &mut TransactionMut, inner_ref: BranchPtr) {
584        let map = MapRef::from(inner_ref);
585        for (key, value) in self.0 {
586            map.insert(txn, key, value);
587        }
588    }
589}
590
591impl Into<EmbedPrelim<MapPrelim>> for MapPrelim {
592    #[inline]
593    fn into(self) -> EmbedPrelim<MapPrelim> {
594        EmbedPrelim::Shared(self)
595    }
596}
597
598/// Event generated by [Map::observe] method. Emitted during transaction commit phase.
599pub struct MapEvent {
600    pub(crate) current_target: BranchPtr,
601    target: MapRef,
602    keys: UnsafeCell<Result<HashMap<Arc<str>, EntryChange>, HashSet<Option<Arc<str>>>>>,
603}
604
605impl MapEvent {
606    pub(crate) fn new(branch_ref: BranchPtr, key_changes: HashSet<Option<Arc<str>>>) -> Self {
607        let current_target = branch_ref.clone();
608        MapEvent {
609            target: MapRef::from(branch_ref),
610            current_target,
611            keys: UnsafeCell::new(Err(key_changes)),
612        }
613    }
614
615    /// Returns a [Map] instance which emitted this event.
616    pub fn target(&self) -> &MapRef {
617        &self.target
618    }
619
620    /// Returns a path from root type down to [Map] instance which emitted this event.
621    pub fn path(&self) -> Path {
622        Branch::path(self.current_target, self.target.0)
623    }
624
625    /// Returns a summary of key-value changes made over corresponding [Map] collection within
626    /// bounds of current transaction.
627    pub fn keys(&self, txn: &TransactionMut) -> &HashMap<Arc<str>, EntryChange> {
628        let keys = unsafe { self.keys.get().as_mut().unwrap() };
629
630        match keys {
631            Ok(keys) => {
632                return keys;
633            }
634            Err(subs) => {
635                let subs = event_keys(txn, self.target.0, subs);
636                *keys = Ok(subs);
637                if let Ok(keys) = keys {
638                    keys
639                } else {
640                    panic!("Defect: should not happen");
641                }
642            }
643        }
644    }
645}
646
647#[cfg(test)]
648mod test {
649    use crate::test_utils::{exchange_updates, run_scenario, RngExt};
650    use crate::transaction::ReadTxn;
651    use crate::types::text::TextPrelim;
652    use crate::types::{DeepObservable, EntryChange, Event, Out, Path, PathSegment, ToJson};
653    use crate::updates::decoder::Decode;
654    use crate::updates::encoder::{Encoder, EncoderV1};
655    use crate::{
656        any, Any, Array, ArrayPrelim, ArrayRef, Doc, GetString, In, Map, MapPrelim, MapRef,
657        Observable, StateVector, Text, TextRef, Transact, Update, WriteTxn, XmlFragment,
658        XmlFragmentRef, XmlTextPrelim, XmlTextRef,
659    };
660    use arc_swap::ArcSwapOption;
661    use fastrand::Rng;
662    use serde::Deserialize;
663    use std::collections::HashMap;
664    use std::sync::atomic::{AtomicU32, Ordering};
665    use std::sync::{Arc, Mutex};
666    use std::time::Duration;
667
668    #[test]
669    fn map_basic() {
670        let d1 = Doc::with_client_id(1);
671        let m1 = d1.get_or_insert_map("map");
672        let mut t1 = d1.transact_mut();
673
674        let d2 = Doc::with_client_id(2);
675        let m2 = d2.get_or_insert_map("map");
676        let mut t2 = d2.transact_mut();
677
678        m1.insert(&mut t1, "number".to_owned(), 1);
679        m1.insert(&mut t1, "string".to_owned(), "hello Y");
680        m1.insert(&mut t1, "object".to_owned(), {
681            let mut v = HashMap::new();
682            v.insert("key2".to_owned(), "value");
683
684            let mut map = HashMap::new();
685            map.insert("key".to_owned(), v);
686            map // { key: { key2: 'value' } }
687        });
688        m1.insert(&mut t1, "boolean1".to_owned(), true);
689        m1.insert(&mut t1, "boolean0".to_owned(), false);
690
691        //let m1m = t1.get_map("y-map");
692        //let m1a = t1.get_text("y-text");
693        //m1a.insert(&mut t1, 0, "a");
694        //m1a.insert(&mut t1, 0, "b");
695        //m1m.insert(&mut t1, "y-text".to_owned(), m1a);
696
697        //TODO: YArray within YMap
698        fn compare_all<T: ReadTxn>(m: &MapRef, txn: &T) {
699            assert_eq!(m.len(txn), 5);
700            assert_eq!(m.get(txn, &"number".to_owned()), Some(Out::from(1f64)));
701            assert_eq!(m.get(txn, &"boolean0".to_owned()), Some(Out::from(false)));
702            assert_eq!(m.get(txn, &"boolean1".to_owned()), Some(Out::from(true)));
703            assert_eq!(m.get(txn, &"string".to_owned()), Some(Out::from("hello Y")));
704            assert_eq!(
705                m.get(txn, &"object".to_owned()),
706                Some(Out::from(any!({
707                    "key": {
708                        "key2": "value"
709                    }
710                })))
711            );
712        }
713
714        compare_all(&m1, &t1);
715
716        let update = t1.encode_state_as_update_v1(&StateVector::default());
717        t2.apply_update(Update::decode_v1(update.as_slice()).unwrap())
718            .unwrap();
719
720        compare_all(&m2, &t2);
721    }
722
723    #[test]
724    fn map_get_set() {
725        let d1 = Doc::with_client_id(1);
726        let m1 = d1.get_or_insert_map("map");
727        let mut t1 = d1.transact_mut();
728
729        m1.insert(&mut t1, "stuff".to_owned(), "stuffy");
730        m1.insert(&mut t1, "null".to_owned(), None as Option<String>);
731
732        let update = t1.encode_state_as_update_v1(&StateVector::default());
733
734        let d2 = Doc::with_client_id(2);
735        let m2 = d2.get_or_insert_map("map");
736        let mut t2 = d2.transact_mut();
737
738        t2.apply_update(Update::decode_v1(update.as_slice()).unwrap())
739            .unwrap();
740
741        assert_eq!(m2.get(&t2, &"stuff".to_owned()), Some(Out::from("stuffy")));
742        assert_eq!(m2.get(&t2, &"null".to_owned()), Some(Out::Any(Any::Null)));
743    }
744
745    #[test]
746    fn map_get_set_sync_with_conflicts() {
747        let d1 = Doc::with_client_id(1);
748        let m1 = d1.get_or_insert_map("map");
749        let mut t1 = d1.transact_mut();
750
751        let d2 = Doc::with_client_id(2);
752        let m2 = d2.get_or_insert_map("map");
753        let mut t2 = d2.transact_mut();
754
755        m1.insert(&mut t1, "stuff".to_owned(), "c0");
756        m2.insert(&mut t2, "stuff".to_owned(), "c1");
757
758        let u1 = t1.encode_state_as_update_v1(&StateVector::default());
759        let u2 = t2.encode_state_as_update_v1(&StateVector::default());
760
761        t1.apply_update(Update::decode_v1(u2.as_slice()).unwrap())
762            .unwrap();
763        t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
764            .unwrap();
765
766        assert_eq!(m1.get(&t1, &"stuff".to_owned()), Some(Out::from("c1")));
767        assert_eq!(m2.get(&t2, &"stuff".to_owned()), Some(Out::from("c1")));
768    }
769
770    #[test]
771    fn map_len_remove() {
772        let d1 = Doc::with_client_id(1);
773        let m1 = d1.get_or_insert_map("map");
774        let mut t1 = d1.transact_mut();
775
776        let key1 = "stuff".to_owned();
777        let key2 = "other-stuff".to_owned();
778
779        m1.insert(&mut t1, key1.clone(), "c0");
780        m1.insert(&mut t1, key2.clone(), "c1");
781        assert_eq!(m1.len(&t1), 2);
782
783        // remove 'stuff'
784        assert_eq!(m1.remove(&mut t1, &key1), Some(Out::from("c0")));
785        assert_eq!(m1.len(&t1), 1);
786
787        // remove 'stuff' again - nothing should happen
788        assert_eq!(m1.remove(&mut t1, &key1), None);
789        assert_eq!(m1.len(&t1), 1);
790
791        // remove 'other-stuff'
792        assert_eq!(m1.remove(&mut t1, &key2), Some(Out::from("c1")));
793        assert_eq!(m1.len(&t1), 0);
794    }
795
796    #[test]
797    fn map_clear() {
798        let d1 = Doc::with_client_id(1);
799        let m1 = d1.get_or_insert_map("map");
800        let mut t1 = d1.transact_mut();
801
802        m1.insert(&mut t1, "key1".to_owned(), "c0");
803        m1.insert(&mut t1, "key2".to_owned(), "c1");
804        m1.clear(&mut t1);
805
806        assert_eq!(m1.len(&t1), 0);
807        assert_eq!(m1.get(&t1, &"key1".to_owned()), None);
808        assert_eq!(m1.get(&t1, &"key2".to_owned()), None);
809
810        let d2 = Doc::with_client_id(2);
811        let m2 = d2.get_or_insert_map("map");
812        let mut t2 = d2.transact_mut();
813
814        let u1 = t1.encode_state_as_update_v1(&StateVector::default());
815        t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
816            .unwrap();
817
818        assert_eq!(m2.len(&t2), 0);
819        assert_eq!(m2.get(&t2, &"key1".to_owned()), None);
820        assert_eq!(m2.get(&t2, &"key2".to_owned()), None);
821    }
822
823    #[test]
824    fn map_clear_sync() {
825        let d1 = Doc::with_client_id(1);
826        let d2 = Doc::with_client_id(2);
827        let d3 = Doc::with_client_id(3);
828        let d4 = Doc::with_client_id(4);
829
830        {
831            let m1 = d1.get_or_insert_map("map");
832            let m2 = d2.get_or_insert_map("map");
833            let m3 = d3.get_or_insert_map("map");
834
835            let mut t1 = d1.transact_mut();
836            let mut t2 = d2.transact_mut();
837            let mut t3 = d3.transact_mut();
838
839            m1.insert(&mut t1, "key1".to_owned(), "c0");
840            m2.insert(&mut t2, "key1".to_owned(), "c1");
841            m2.insert(&mut t2, "key1".to_owned(), "c2");
842            m3.insert(&mut t3, "key1".to_owned(), "c3");
843        }
844
845        exchange_updates(&[&d1, &d2, &d3, &d4]);
846
847        {
848            let m1 = d1.get_or_insert_map("map");
849            let m2 = d2.get_or_insert_map("map");
850            let m3 = d3.get_or_insert_map("map");
851
852            let mut t1 = d1.transact_mut();
853            let mut t2 = d2.transact_mut();
854            let mut t3 = d3.transact_mut();
855
856            m1.insert(&mut t1, "key2".to_owned(), "c0");
857            m2.insert(&mut t2, "key2".to_owned(), "c1");
858            m2.insert(&mut t2, "key2".to_owned(), "c2");
859            m3.insert(&mut t3, "key2".to_owned(), "c3");
860            m3.clear(&mut t3);
861        }
862
863        exchange_updates(&[&d1, &d2, &d3, &d4]);
864
865        for doc in [d1, d2, d3, d4] {
866            let map = doc.get_or_insert_map("map");
867
868            assert_eq!(
869                map.get(&doc.transact(), &"key1".to_owned()),
870                None,
871                "'key1' entry for peer {} should be removed",
872                doc.client_id()
873            );
874            assert_eq!(
875                map.get(&doc.transact(), &"key2".to_owned()),
876                None,
877                "'key2' entry for peer {} should be removed",
878                doc.client_id()
879            );
880            assert_eq!(
881                map.len(&doc.transact()),
882                0,
883                "all entries for peer {} should be removed",
884                doc.client_id()
885            );
886        }
887    }
888
889    #[test]
890    fn map_get_set_with_3_way_conflicts() {
891        let d1 = Doc::with_client_id(1);
892        let d2 = Doc::with_client_id(2);
893        let d3 = Doc::with_client_id(3);
894
895        {
896            let m1 = d1.get_or_insert_map("map");
897            let m2 = d2.get_or_insert_map("map");
898            let m3 = d3.get_or_insert_map("map");
899
900            let mut t1 = d1.transact_mut();
901            let mut t2 = d2.transact_mut();
902            let mut t3 = d3.transact_mut();
903
904            m1.insert(&mut t1, "stuff".to_owned(), "c0");
905            m2.insert(&mut t2, "stuff".to_owned(), "c1");
906            m2.insert(&mut t2, "stuff".to_owned(), "c2");
907            m3.insert(&mut t3, "stuff".to_owned(), "c3");
908        }
909
910        exchange_updates(&[&d1, &d2, &d3]);
911
912        for doc in [d1, d2, d3] {
913            let map = doc.get_or_insert_map("map");
914
915            assert_eq!(
916                map.get(&doc.transact(), &"stuff".to_owned()),
917                Some(Out::from("c3")),
918                "peer {} - map entry resolved to unexpected value",
919                doc.client_id()
920            );
921        }
922    }
923
924    #[test]
925    fn map_get_set_remove_with_3_way_conflicts() {
926        let d1 = Doc::with_client_id(1);
927        let d2 = Doc::with_client_id(2);
928        let d3 = Doc::with_client_id(3);
929        let d4 = Doc::with_client_id(4);
930
931        {
932            let m1 = d1.get_or_insert_map("map");
933            let m2 = d2.get_or_insert_map("map");
934            let m3 = d3.get_or_insert_map("map");
935
936            let mut t1 = d1.transact_mut();
937            let mut t2 = d2.transact_mut();
938            let mut t3 = d3.transact_mut();
939
940            m1.insert(&mut t1, "key1".to_owned(), "c0");
941            m2.insert(&mut t2, "key1".to_owned(), "c1");
942            m2.insert(&mut t2, "key1".to_owned(), "c2");
943            m3.insert(&mut t3, "key1".to_owned(), "c3");
944        }
945
946        exchange_updates(&[&d1, &d2, &d3, &d4]);
947
948        {
949            let m1 = d1.get_or_insert_map("map");
950            let m2 = d2.get_or_insert_map("map");
951            let m3 = d3.get_or_insert_map("map");
952            let m4 = d4.get_or_insert_map("map");
953
954            let mut t1 = d1.transact_mut();
955            let mut t2 = d2.transact_mut();
956            let mut t3 = d3.transact_mut();
957            let mut t4 = d4.transact_mut();
958
959            m1.insert(&mut t1, "key1".to_owned(), "deleteme");
960            m2.insert(&mut t2, "key1".to_owned(), "c1");
961            m3.insert(&mut t3, "key1".to_owned(), "c2");
962            m4.insert(&mut t4, "key1".to_owned(), "c3");
963            m4.remove(&mut t4, &"key1".to_owned());
964        }
965
966        exchange_updates(&[&d1, &d2, &d3, &d4]);
967
968        for doc in [d1, d2, d3, d4] {
969            let map = doc.get_or_insert_map("map");
970
971            assert_eq!(
972                map.get(&doc.transact(), &"key1".to_owned()),
973                None,
974                "entry 'key1' on peer {} should be removed",
975                doc.client_id()
976            );
977        }
978    }
979
980    #[test]
981    fn insert_and_remove_events() {
982        let d1 = Doc::with_client_id(1);
983        let m1 = d1.get_or_insert_map("map");
984
985        let entries = Arc::new(ArcSwapOption::default());
986        let entries_c = entries.clone();
987        let _sub = m1.observe(move |txn, e| {
988            let keys = e.keys(txn);
989            entries_c.store(Some(Arc::new(keys.clone())));
990        });
991
992        // insert new entry
993        {
994            let mut txn = d1.transact_mut();
995            m1.insert(&mut txn, "a", 1);
996            // txn is committed at the end of this scope
997        }
998        assert_eq!(
999            entries.swap(None),
1000            Some(Arc::new(HashMap::from([(
1001                "a".into(),
1002                EntryChange::Inserted(Any::Number(1.0).into())
1003            )])))
1004        );
1005
1006        // update existing entry once
1007        {
1008            let mut txn = d1.transact_mut();
1009            m1.insert(&mut txn, "a", 2);
1010        }
1011        assert_eq!(
1012            entries.swap(None),
1013            Some(Arc::new(HashMap::from([(
1014                "a".into(),
1015                EntryChange::Updated(Any::Number(1.0).into(), Any::Number(2.0).into())
1016            )])))
1017        );
1018
1019        // update existing entry twice
1020        {
1021            let mut txn = d1.transact_mut();
1022            m1.insert(&mut txn, "a", 3);
1023            m1.insert(&mut txn, "a", 4);
1024        }
1025        assert_eq!(
1026            entries.swap(None),
1027            Some(Arc::new(HashMap::from([(
1028                "a".into(),
1029                EntryChange::Updated(Any::Number(2.0).into(), Any::Number(4.0).into())
1030            )])))
1031        );
1032
1033        // remove existing entry
1034        {
1035            let mut txn = d1.transact_mut();
1036            m1.remove(&mut txn, "a");
1037        }
1038        assert_eq!(
1039            entries.swap(None),
1040            Some(Arc::new(HashMap::from([(
1041                "a".into(),
1042                EntryChange::Removed(Any::Number(4.0).into())
1043            )])))
1044        );
1045
1046        // add another entry and update it
1047        {
1048            let mut txn = d1.transact_mut();
1049            m1.insert(&mut txn, "b", 1);
1050            m1.insert(&mut txn, "b", 2);
1051        }
1052        assert_eq!(
1053            entries.swap(None),
1054            Some(Arc::new(HashMap::from([(
1055                "b".into(),
1056                EntryChange::Inserted(Any::Number(2.0).into())
1057            )])))
1058        );
1059
1060        // add and remove an entry
1061        {
1062            let mut txn = d1.transact_mut();
1063            m1.insert(&mut txn, "c", 1);
1064            m1.remove(&mut txn, "c");
1065        }
1066        assert_eq!(entries.swap(None), Some(HashMap::new().into()));
1067
1068        // copy updates over
1069        let d2 = Doc::with_client_id(2);
1070        let m2 = d2.get_or_insert_map("map");
1071
1072        let entries = Arc::new(ArcSwapOption::default());
1073        let entries_c = entries.clone();
1074        let _sub = m2.observe(move |txn, e| {
1075            let keys = e.keys(txn);
1076            entries_c.store(Some(Arc::new(keys.clone())));
1077        });
1078
1079        {
1080            let t1 = d1.transact_mut();
1081            let mut t2 = d2.transact_mut();
1082
1083            let sv = t2.state_vector();
1084            let mut encoder = EncoderV1::new();
1085            t1.encode_diff(&sv, &mut encoder);
1086            t2.apply_update(Update::decode_v1(encoder.to_vec().as_slice()).unwrap())
1087                .unwrap();
1088        }
1089        assert_eq!(
1090            entries.swap(None),
1091            Some(Arc::new(HashMap::from([(
1092                "b".into(),
1093                EntryChange::Inserted(Any::Number(2.0).into())
1094            )])))
1095        );
1096    }
1097
1098    fn map_transactions() -> [Box<dyn Fn(&mut Doc, &mut Rng)>; 3] {
1099        fn set(doc: &mut Doc, rng: &mut Rng) {
1100            let map = doc.get_or_insert_map("map");
1101            let mut txn = doc.transact_mut();
1102            let key = rng.choice(["one", "two"]).unwrap();
1103            let value: String = rng.random_string();
1104            map.insert(&mut txn, key.to_string(), value);
1105        }
1106
1107        fn set_type(doc: &mut Doc, rng: &mut Rng) {
1108            let map = doc.get_or_insert_map("map");
1109            let mut txn = doc.transact_mut();
1110            let key = rng.choice(["one", "two", "three"]).unwrap();
1111            if rng.f32() <= 0.33 {
1112                map.insert(
1113                    &mut txn,
1114                    key.to_string(),
1115                    ArrayPrelim::from(vec![1, 2, 3, 4]),
1116                );
1117            } else if rng.f32() <= 0.33 {
1118                map.insert(&mut txn, key.to_string(), TextPrelim::new("deeptext"));
1119            } else {
1120                map.insert(
1121                    &mut txn,
1122                    key.to_string(),
1123                    MapPrelim::from([("deepkey".to_owned(), "deepvalue")]),
1124                );
1125            }
1126        }
1127
1128        fn delete(doc: &mut Doc, rng: &mut Rng) {
1129            let map = doc.get_or_insert_map("map");
1130            let mut txn = doc.transact_mut();
1131            let key = rng.choice(["one", "two"]).unwrap();
1132            map.remove(&mut txn, key);
1133        }
1134        [Box::new(set), Box::new(set_type), Box::new(delete)]
1135    }
1136
1137    fn fuzzy(iterations: usize) {
1138        run_scenario(0, &map_transactions(), 5, iterations)
1139    }
1140
1141    #[test]
1142    fn fuzzy_test_6() {
1143        fuzzy(6)
1144    }
1145
1146    #[test]
1147    fn observe_deep() {
1148        let doc = Doc::with_client_id(1);
1149        let map = doc.get_or_insert_map("map");
1150
1151        let paths = Arc::new(Mutex::new(vec![]));
1152        let calls = Arc::new(AtomicU32::new(0));
1153        let paths_copy = paths.clone();
1154        let calls_copy = calls.clone();
1155        let _sub = map.observe_deep(move |_txn, e| {
1156            let path: Vec<Path> = e.iter().map(Event::path).collect();
1157            paths_copy.lock().unwrap().push(path);
1158            calls_copy.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
1159        });
1160
1161        let nested = map.insert(&mut doc.transact_mut(), "map", MapPrelim::default());
1162        nested.insert(
1163            &mut doc.transact_mut(),
1164            "array",
1165            ArrayPrelim::from(Vec::<String>::default()),
1166        );
1167        let nested2 = nested
1168            .get(&doc.transact(), "array")
1169            .unwrap()
1170            .cast::<ArrayRef>()
1171            .unwrap();
1172        nested2.insert(&mut doc.transact_mut(), 0, "content");
1173
1174        let nested_text = nested.insert(&mut doc.transact_mut(), "text", TextPrelim::new("text"));
1175        nested_text.push(&mut doc.transact_mut(), "!");
1176
1177        assert_eq!(calls.load(Ordering::Relaxed), 5);
1178        let actual = paths.lock().unwrap();
1179        assert_eq!(
1180            actual.as_slice(),
1181            &[
1182                vec![Path::from(vec![])],
1183                vec![Path::from(vec![PathSegment::Key("map".into())])],
1184                vec![Path::from(vec![
1185                    PathSegment::Key("map".into()),
1186                    PathSegment::Key("array".into())
1187                ])],
1188                vec![Path::from(vec![PathSegment::Key("map".into()),])],
1189                vec![Path::from(vec![
1190                    PathSegment::Key("map".into()),
1191                    PathSegment::Key("text".into()),
1192                ])],
1193            ]
1194        );
1195    }
1196
1197    #[test]
1198    fn get_or_init() {
1199        let doc = Doc::with_client_id(1);
1200        let mut txn = doc.transact_mut();
1201        let map = txn.get_or_insert_map("map");
1202
1203        let m: MapRef = map.get_or_init(&mut txn, "nested");
1204        m.insert(&mut txn, "key", 1);
1205        let m: MapRef = map.get_or_init(&mut txn, "nested");
1206        assert_eq!(m.get(&txn, "key"), Some(Out::from(1)));
1207
1208        let m: ArrayRef = map.get_or_init(&mut txn, "nested");
1209        m.insert(&mut txn, 0, 1);
1210        let m: ArrayRef = map.get_or_init(&mut txn, "nested");
1211        assert_eq!(m.get(&txn, 0), Some(Out::from(1)));
1212
1213        let m: TextRef = map.get_or_init(&mut txn, "nested");
1214        m.insert(&mut txn, 0, "a");
1215        let m: TextRef = map.get_or_init(&mut txn, "nested");
1216        assert_eq!(m.get_string(&txn), "a".to_string());
1217
1218        let m: XmlFragmentRef = map.get_or_init(&mut txn, "nested");
1219        m.insert(&mut txn, 0, XmlTextPrelim::new("b"));
1220        let m: XmlFragmentRef = map.get_or_init(&mut txn, "nested");
1221        assert_eq!(m.get_string(&txn), "b".to_string());
1222
1223        let m: XmlTextRef = map.get_or_init(&mut txn, "nested");
1224        m.insert(&mut txn, 0, "c");
1225        let m: XmlTextRef = map.get_or_init(&mut txn, "nested");
1226        assert_eq!(m.get_string(&txn), "c".to_string());
1227    }
1228
1229    #[test]
1230    fn try_update() {
1231        let doc = Doc::new();
1232        let mut txn = doc.transact_mut();
1233        let map = txn.get_or_insert_map("map");
1234
1235        assert!(map.try_update(&mut txn, "key", 1), "new entry");
1236        assert_eq!(map.get(&txn, "key"), Some(Out::from(1)));
1237
1238        assert!(
1239            !map.try_update(&mut txn, "key", 1),
1240            "unchanged entry shouldn't trigger update"
1241        );
1242        assert_eq!(map.get(&txn, "key"), Some(Out::from(1)));
1243
1244        assert!(map.try_update(&mut txn, "key", 2), "entry should change");
1245        assert_eq!(map.get(&txn, "key"), Some(Out::from(2)));
1246
1247        map.remove(&mut txn, "key");
1248        assert!(
1249            map.try_update(&mut txn, "key", 2),
1250            "removed entry should trigger update"
1251        );
1252        assert_eq!(map.get(&txn, "key"), Some(Out::from(2)));
1253    }
1254
1255    #[test]
1256    fn get_as() {
1257        #[derive(Debug, PartialEq, Deserialize)]
1258        struct Order {
1259            shipment_address: String,
1260            items: HashMap<String, OrderItem>,
1261            #[serde(default)]
1262            comment: Option<String>,
1263        }
1264
1265        #[derive(Debug, PartialEq, Deserialize)]
1266        struct OrderItem {
1267            name: String,
1268            price: f64,
1269            quantity: u32,
1270        }
1271
1272        let doc = Doc::new();
1273        let mut txn = doc.transact_mut();
1274        let map = txn.get_or_insert_map("map");
1275
1276        map.insert(
1277            &mut txn,
1278            "orders",
1279            ArrayPrelim::from([In::from(MapPrelim::from([
1280                ("shipment_address", In::from("123 Main St")),
1281                (
1282                    "items",
1283                    In::from(MapPrelim::from([
1284                        (
1285                            "item1",
1286                            In::from(MapPrelim::from([
1287                                ("name", In::from("item1")),
1288                                ("price", In::from(1.99)),
1289                                ("quantity", In::from(2)),
1290                            ])),
1291                        ),
1292                        (
1293                            "item2",
1294                            In::from(MapPrelim::from([
1295                                ("name", In::from("item2")),
1296                                ("price", In::from(2.99)),
1297                                ("quantity", In::from(1)),
1298                            ])),
1299                        ),
1300                    ])),
1301                ),
1302            ]))]),
1303        );
1304
1305        let expected = Order {
1306            comment: None,
1307            shipment_address: "123 Main St".to_string(),
1308            items: HashMap::from([
1309                (
1310                    "item1".to_string(),
1311                    OrderItem {
1312                        name: "item1".to_string(),
1313                        price: 1.99,
1314                        quantity: 2,
1315                    },
1316                ),
1317                (
1318                    "item2".to_string(),
1319                    OrderItem {
1320                        name: "item2".to_string(),
1321                        price: 2.99,
1322                        quantity: 1,
1323                    },
1324                ),
1325            ]),
1326        };
1327
1328        let actual: Vec<Order> = map.get_as(&txn, "orders").unwrap();
1329        assert_eq!(actual, vec![expected]);
1330    }
1331
1332    #[test]
1333    fn multi_threading() {
1334        use std::sync::{Arc, RwLock};
1335        use std::thread::{sleep, spawn};
1336
1337        let doc = Arc::new(RwLock::new(Doc::with_client_id(1)));
1338
1339        let d2 = doc.clone();
1340        let h2 = spawn(move || {
1341            for _ in 0..10 {
1342                let millis = fastrand::u64(1..20);
1343                sleep(Duration::from_millis(millis));
1344
1345                let doc = d2.write().unwrap();
1346                let map = doc.get_or_insert_map("test");
1347                let mut txn = doc.transact_mut();
1348                map.insert(&mut txn, "key", 1);
1349            }
1350        });
1351
1352        let d3 = doc.clone();
1353        let h3 = spawn(move || {
1354            for _ in 0..10 {
1355                let millis = fastrand::u64(1..20);
1356                sleep(Duration::from_millis(millis));
1357
1358                let doc = d3.write().unwrap();
1359                let map = doc.get_or_insert_map("test");
1360                let mut txn = doc.transact_mut();
1361                map.insert(&mut txn, "key", 2);
1362            }
1363        });
1364
1365        h3.join().unwrap();
1366        h2.join().unwrap();
1367
1368        let doc = doc.read().unwrap();
1369        let map = doc.get_or_insert_map("test");
1370        let txn = doc.transact();
1371        let value = map.get(&txn, "key").unwrap().to_json(&txn);
1372
1373        assert!(value == 1.into() || value == 2.into())
1374    }
1375}
yrs/types/map.rs

yrs/types/
map.rs
