yrs/
moving.rs

1use crate::block::{ItemContent, ItemPtr, Prelim, Unused};
2use crate::block_iter::BlockIter;
3use crate::branch::{Branch, BranchPtr};
4use crate::encoding::read::Error;
5use crate::transaction::TransactionMut;
6use crate::updates::decoder::{Decode, Decoder};
7use crate::updates::encoder::{Encode, Encoder};
8use crate::{BranchID, ReadTxn, WriteTxn, ID};
9use serde::de::{MapAccess, Visitor};
10use serde::ser::SerializeStruct;
11use serde::{Deserialize, Deserializer, Serialize, Serializer};
12use std::collections::HashSet;
13use std::fmt::Formatter;
14use std::sync::Arc;
15
16#[derive(Debug, Clone, Eq, PartialEq)]
17pub struct Move {
18    pub start: StickyIndex,
19    pub end: StickyIndex,
20    pub priority: i32,
21
22    /// We store which Items+ContentMove we override. Once we delete
23    /// this ContentMove, we need to re-integrate the overridden items.
24    ///
25    /// This representation can be improved if we ever run into memory issues because of too many overrides.
26    /// Ideally, we should probably just re-iterate the document and re-integrate all moved items.
27    /// This is fast enough and reduces memory footprint significantly.
28    pub(crate) overrides: Option<HashSet<ItemPtr>>,
29}
30
31impl Move {
32    pub fn new(start: StickyIndex, end: StickyIndex, priority: i32) -> Self {
33        Move {
34            start,
35            end,
36            priority,
37            overrides: None,
38        }
39    }
40
41    pub fn is_collapsed(&self) -> bool {
42        match (&self.start.scope, &self.end.scope) {
43            (IndexScope::Relative(id1), IndexScope::Relative(id2)) => id1.eq(id2),
44            _ => false,
45        }
46    }
47
48    pub(crate) fn get_moved_coords_mut<T: WriteTxn>(
49        &self,
50        txn: &mut T,
51    ) -> (Option<ItemPtr>, Option<ItemPtr>) {
52        let start = if let Some(start) = self.start.id() {
53            Self::get_item_ptr_mut(txn, start, self.start.assoc)
54        } else {
55            None
56        };
57        let end = if let Some(end) = self.end.id() {
58            Self::get_item_ptr_mut(txn, end, self.end.assoc)
59        } else {
60            None
61        };
62        (start, end)
63    }
64
65    fn get_item_ptr_mut<T: WriteTxn>(txn: &mut T, id: &ID, assoc: Assoc) -> Option<ItemPtr> {
66        let store = txn.store_mut();
67        if assoc == Assoc::After {
68            let slice = store.blocks.get_item_clean_start(id)?;
69            if slice.adjacent() {
70                Some(slice.ptr)
71            } else {
72                Some(store.materialize(slice))
73            }
74        } else {
75            let slice = store.blocks.get_item_clean_end(id)?;
76            let ptr = if slice.adjacent() {
77                slice.ptr
78            } else {
79                store.materialize(slice)
80            };
81            ptr.right
82        }
83    }
84
85    pub(crate) fn get_moved_coords<T: ReadTxn>(
86        &self,
87        txn: &T,
88    ) -> (Option<ItemPtr>, Option<ItemPtr>) {
89        let start = if let Some(start) = self.start.id() {
90            Self::get_item_ptr(txn, start, self.start.assoc)
91        } else {
92            None
93        };
94        let end = if let Some(end) = self.end.id() {
95            Self::get_item_ptr(txn, end, self.end.assoc)
96        } else {
97            None
98        };
99        (start, end)
100    }
101
102    fn get_item_ptr<T: ReadTxn>(txn: &T, id: &ID, assoc: Assoc) -> Option<ItemPtr> {
103        if assoc == Assoc::After {
104            let slice = txn.store().blocks.get_item_clean_start(id)?;
105            debug_assert!(slice.adjacent()); //TODO: remove once confirmed that slice always fits block range
106            Some(slice.ptr)
107        } else {
108            let slice = txn.store().blocks.get_item_clean_end(id)?;
109            debug_assert!(slice.adjacent()); //TODO: remove once confirmed that slice always fits block range
110            slice.ptr.right
111        }
112    }
113
114    pub(crate) fn find_move_loop<T: ReadTxn>(
115        &self,
116        txn: &mut T,
117        moved: ItemPtr,
118        tracked_moved_items: &mut HashSet<ItemPtr>,
119    ) -> bool {
120        if tracked_moved_items.contains(&moved) {
121            true
122        } else {
123            tracked_moved_items.insert(moved.clone());
124            let (mut start, end) = self.get_moved_coords(txn);
125            while let Some(item) = start.as_deref() {
126                if start == end {
127                    break;
128                }
129
130                if !item.is_deleted() && item.moved == Some(moved) {
131                    if let ItemContent::Move(m) = &item.content {
132                        if m.find_move_loop(txn, start.unwrap(), tracked_moved_items) {
133                            return true;
134                        }
135                    }
136                }
137
138                start = item.right;
139            }
140
141            false
142        }
143    }
144
145    fn push_override(&mut self, ptr: ItemPtr) {
146        let e = self.overrides.get_or_insert_with(HashSet::default);
147        e.insert(ptr);
148    }
149
150    pub(crate) fn integrate_block(&mut self, txn: &mut TransactionMut, item: ItemPtr) {
151        let (init, end) = self.get_moved_coords_mut(txn);
152        let mut max_priority = 0i32;
153        let adapt_priority = self.priority < 0;
154        let mut start = init;
155        while start != end && start.is_some() {
156            let start_ptr = start.unwrap().clone();
157            if let Some(start_item) = start.as_deref_mut() {
158                let mut prev_move = start_item.moved;
159                let next_prio = if let Some(m) = prev_move.as_deref() {
160                    if let ItemContent::Move(next) = &m.content {
161                        next.priority
162                    } else {
163                        -1
164                    }
165                } else {
166                    -1
167                };
168
169                #[inline]
170                fn is_lower(a: &ID, b: &ID) -> bool {
171                    a.client < b.client || (a.client == b.client && a.clock < b.clock)
172                }
173
174                if adapt_priority
175                    || next_prio < self.priority
176                    || (prev_move.is_some()
177                        && next_prio == self.priority
178                        && is_lower(prev_move.unwrap().id(), item.id()))
179                {
180                    if let Some(moved_ptr) = prev_move.clone() {
181                        if let ItemContent::Move(m) = &moved_ptr.content {
182                            if m.is_collapsed() {
183                                moved_ptr.delete_as_cleanup(txn, adapt_priority);
184                            }
185                        }
186
187                        self.push_override(moved_ptr);
188                        if Some(start_ptr) != init {
189                            // only add this to mergeStructs if this is not the first item
190                            txn.merge_blocks.push(start_item.id);
191                        }
192                    }
193                    max_priority = max_priority.max(next_prio);
194                    // was already moved
195                    let prev_move = start_item.moved;
196                    if let Some(prev_move) = prev_move {
197                        if !txn.prev_moved.contains_key(&prev_move) && txn.has_added(prev_move.id())
198                        {
199                            // only override prevMoved if the prevMoved item is not new
200                            // we need to know which item previously moved an item
201                            txn.prev_moved.insert(start_ptr, prev_move);
202                        }
203                    }
204                    start_item.moved = Some(item);
205                    if !start_item.is_deleted() {
206                        if let ItemContent::Move(m) = &start_item.content {
207                            if m.find_move_loop(txn, start_ptr, &mut HashSet::from([item])) {
208                                item.delete_as_cleanup(txn, adapt_priority);
209                                return;
210                            }
211                        }
212                    }
213                } else if let Some(moved_item) = prev_move.as_deref_mut() {
214                    if let ItemContent::Move(m) = &mut moved_item.content {
215                        m.push_override(item);
216                    }
217                }
218                start = start_item.right;
219            } else {
220                break;
221            }
222        }
223
224        if adapt_priority {
225            self.priority = max_priority + 1;
226        }
227    }
228
229    pub(crate) fn delete(&self, txn: &mut TransactionMut, item: ItemPtr) {
230        let (mut start, end) = self.get_moved_coords(txn);
231        while start != end && start.is_some() {
232            if let Some(mut start_ptr) = start {
233                if start_ptr.moved == Some(item) {
234                    if let Some(&prev_moved) = txn.prev_moved.get(&start_ptr) {
235                        if txn.has_added(item.id()) {
236                            if prev_moved == item {
237                                // Edge case: Item has been moved by this move op and it has been created & deleted in the same transaction (hence no effect that should be emitted by the change computation)
238                                txn.prev_moved.remove(&start_ptr);
239                            }
240                        }
241                    } else {
242                        // Normal case: item has been moved by this move and it has not been created & deleted in the same transaction
243                        txn.prev_moved.insert(start_ptr, item);
244                    }
245                    start_ptr.moved = None;
246                }
247                start = start_ptr.right;
248                continue;
249            }
250            break;
251        }
252
253        fn reintegrate(mut item: ItemPtr, txn: &mut TransactionMut) {
254            let deleted = item.is_deleted();
255            let ptr = item.clone();
256            if let ItemContent::Move(content) = &mut item.content {
257                if deleted {
258                    // potentially we can integrate the items that reIntegrateItem overrides
259                    if let Some(overrides) = &content.overrides {
260                        for &inner in overrides.iter() {
261                            reintegrate(inner, txn);
262                        }
263                    }
264                } else {
265                    content.integrate_block(txn, ptr)
266                }
267            }
268        }
269
270        if let Some(overrides) = &self.overrides {
271            for &ptr in overrides {
272                reintegrate(ptr, txn);
273            }
274        }
275    }
276}
277
278impl Encode for Move {
279    fn encode<E: Encoder>(&self, encoder: &mut E) {
280        let is_collapsed = self.is_collapsed();
281        let flags = {
282            let mut b = 0;
283            if is_collapsed {
284                b |= 0b0000_0001
285            }
286            if self.start.assoc == Assoc::After {
287                b |= 0b0000_0010
288            }
289            if self.end.assoc == Assoc::After {
290                b |= 0b0000_0100
291            }
292            b |= self.priority << 6;
293            b
294        };
295        encoder.write_var(flags);
296        let id = self.start.id().unwrap();
297        encoder.write_var(id.client);
298        encoder.write_var(id.clock);
299        if !is_collapsed {
300            let id = self.end.id().unwrap();
301            encoder.write_var(id.client);
302            encoder.write_var(id.clock);
303        }
304    }
305}
306
307impl Decode for Move {
308    fn decode<D: Decoder>(decoder: &mut D) -> Result<Self, Error> {
309        let flags: i32 = decoder.read_var()?;
310        let is_collapsed = flags & 0b0000_0001 != 0;
311        let start_assoc = if flags & 0b0000_0010 != 0 {
312            Assoc::After
313        } else {
314            Assoc::Before
315        };
316        let end_assoc = if flags & 0b0000_0100 != 0 {
317            Assoc::After
318        } else {
319            Assoc::Before
320        };
321        //TODO use BIT3 & BIT4 to indicate the case `null` is the start/end
322        // BIT5 is reserved for future extensions
323        let priority = flags >> 6;
324        let start_id = ID::new(decoder.read_var()?, decoder.read_var()?);
325        let end_id = if is_collapsed {
326            start_id
327        } else {
328            ID::new(decoder.read_var()?, decoder.read_var()?)
329        };
330        let start = StickyIndex::new(IndexScope::Relative(start_id), start_assoc);
331        let end = StickyIndex::new(IndexScope::Relative(end_id), end_assoc);
332        Ok(Move::new(start, end, priority))
333    }
334}
335
336impl Prelim for Move {
337    type Return = Unused;
338
339    #[inline]
340    fn into_content(self, _: &mut TransactionMut) -> (ItemContent, Option<Self>) {
341        (ItemContent::Move(Box::new(self)), None)
342    }
343
344    #[inline]
345    fn integrate(self, _: &mut TransactionMut, _inner_ref: BranchPtr) {}
346}
347
348impl std::fmt::Display for Move {
349    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
350        write!(f, "move(")?;
351        write!(f, "{}", self.start)?;
352        if self.start != self.end {
353            write!(f, "..{}", self.end)?;
354        }
355        if self.priority != 0 {
356            write!(f, ", prio: {}", self.priority)?;
357        }
358        if let Some(overrides) = self.overrides.as_ref() {
359            write!(f, ", overrides: [")?;
360            let mut i = overrides.iter();
361            if let Some(b) = i.next() {
362                write!(f, "{}", b.id())?;
363            }
364            while let Some(b) = i.next() {
365                write!(f, ", {}", b.id())?;
366            }
367            write!(f, "]")?;
368        }
369        write!(f, ")")
370    }
371}
372
373/// A sticky index is based on the Yjs model and is not affected by document changes.
374/// E.g. If you place a sticky index before a certain character, it will always point to this character.
375/// If you place a sticky index at the end of a type, it will always point to the end of the type.
376///
377/// A numeric position is often unsuited for user selections, because it does not change when content is inserted
378/// before or after.
379///
380/// ```Insert(0, 'x')('a.bc') = 'xa.bc'``` Where `.` is the relative position.
381///
382/// Example:
383///
384/// ```rust
385/// use yrs::{Assoc, Doc, IndexedSequence, Text, Transact};
386///
387/// let doc = Doc::new();
388/// let txt = doc.get_or_insert_text("text");
389/// let mut txn = doc.transact_mut();
390/// txt.insert(&mut txn, 0, "abc"); // => 'abc'
391///
392/// // create position tracker (marked as . in the comments)
393/// let pos = txt.sticky_index(&mut txn, 2, Assoc::After).unwrap(); // => 'ab.c'
394///
395/// // modify text
396/// txt.insert(&mut txn, 1, "def"); // => 'adefb.c'
397/// txt.remove_range(&mut txn, 4, 1); // => 'adef.c'
398///
399/// // get current offset index within the containing collection
400/// let a = pos.get_offset(&txn).unwrap();
401/// assert_eq!(a.index, 4);
402/// ```
403#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
404pub struct StickyIndex {
405    scope: IndexScope,
406    /// If true - associate to the right block. Otherwise, associate to the left one.
407    pub assoc: Assoc,
408}
409
410impl StickyIndex {
411    pub fn new(scope: IndexScope, assoc: Assoc) -> Self {
412        StickyIndex { scope, assoc }
413    }
414
415    pub fn from_id(id: ID, assoc: Assoc) -> Self {
416        Self::new(IndexScope::Relative(id), assoc)
417    }
418
419    pub fn from_type<T, B>(_txn: &T, branch: &B, assoc: Assoc) -> Self
420    where
421        T: ReadTxn,
422        B: AsRef<Branch>,
423    {
424        let branch = branch.as_ref();
425        if let Some(ptr) = branch.item {
426            let id = ptr.id().clone();
427            Self::new(IndexScope::Nested(id), assoc)
428        } else if let Some(name) = &branch.name {
429            Self::new(IndexScope::Root(name.clone()), assoc)
430        } else {
431            unreachable!()
432        }
433    }
434
435    #[inline]
436    pub fn scope(&self) -> &IndexScope {
437        &self.scope
438    }
439
440    /// Returns an [ID] of the block position which is used as a reference to keep track the location
441    /// of current [StickyIndex] even in face of changes performed by different peers.
442    ///
443    /// Returns `None` if current [StickyIndex] has been created on an empty shared collection (in
444    /// that case there's no block that we can refer to).
445    pub fn id(&self) -> Option<&ID> {
446        if let IndexScope::Relative(id) = &self.scope {
447            Some(id)
448        } else {
449            None
450        }
451    }
452
453    /// Maps current [StickyIndex] onto [Offset] which points to shared collection and a
454    /// human-readable index in that collection.
455    ///
456    /// That index is only valid at the current point in time - if i.e. another update from remote
457    /// peer has been applied, it may have changed relative index position that [StickyIndex] points
458    /// to, so that [Offset]'s index will no longer point to the same place.
459    ///
460    /// # Examples
461    ///
462    /// ```rust
463    /// use yrs::{Assoc, Doc, IndexedSequence, Text, Transact};
464    ///
465    /// let doc = Doc::new();
466    /// let text = doc.get_or_insert_text("text");
467    /// let mut txn = doc.transact_mut();
468    ///
469    /// text.insert(&mut txn, 0, "hello world");
470    ///
471    /// const INDEX: u32 = 4;
472    ///
473    /// // set perma index at position before letter 'o' => "hell.o world"
474    /// let pos = text.sticky_index(&mut txn, INDEX, Assoc::After).unwrap();
475    /// let off = pos.get_offset(&txn).unwrap();
476    /// assert_eq!(off.index, INDEX);
477    ///
478    /// // perma index will maintain it's position before letter 'o' even if another update
479    /// // shifted it's index inside of the text
480    /// text.insert(&mut txn, 1, "(see)"); // => "h(see)ell.o world" where . is perma index position
481    /// let off2 = pos.get_offset(&txn).unwrap();
482    /// assert_ne!(off2.index, off.index); // offset index changed due to new insert above
483    /// ```
484    pub fn get_offset<T: ReadTxn>(&self, txn: &T) -> Option<Offset> {
485        let mut branch = None;
486        let mut index = 0;
487
488        match &self.scope {
489            IndexScope::Relative(right_id) => {
490                let store = txn.store();
491                if store.blocks.get_clock(&right_id.client) <= right_id.clock {
492                    // type does not exist yet
493                    return None;
494                }
495                let right = store.follow_redone(right_id);
496                if let Some(right) = right {
497                    if let Some(b) = right.ptr.parent.as_branch() {
498                        branch = Some(b.clone());
499                        match b.item {
500                            Some(i) if i.is_deleted() => { /* do nothing */ }
501                            _ => {
502                                // adjust position based on left association if necessary
503                                index = if right.is_deleted() || !right.is_countable() {
504                                    0
505                                } else if self.assoc == Assoc::After {
506                                    right.start
507                                } else {
508                                    right.start + 1
509                                };
510                                let encoding = store.offset_kind;
511                                let mut n = right.ptr.left;
512                                while let Some(item) = n.as_deref() {
513                                    if !item.is_deleted() && item.is_countable() {
514                                        index += item.content_len(encoding);
515                                    }
516                                    n = item.left;
517                                }
518                            }
519                        }
520                    }
521                }
522            }
523            IndexScope::Nested(id) => {
524                let store = txn.store();
525                if store.blocks.get_clock(&id.client) <= id.clock {
526                    // type does not exist yet
527                    return None;
528                }
529                let item = store.follow_redone(id)?; // early return if item is GC'ed
530                if let ItemContent::Type(b) = &item.ptr.content {
531                    // we don't need to materilized ItemContent::Type - they are always 1-length
532                    branch = Some(BranchPtr::from(b.as_ref()));
533                } // else - branch remains null
534            }
535            IndexScope::Root(name) => {
536                branch = txn.store().get_type(name.clone());
537                if let Some(ptr) = branch.as_ref() {
538                    index = if self.assoc == Assoc::After {
539                        ptr.content_len
540                    } else {
541                        0
542                    };
543                }
544            }
545        }
546
547        if let Some(ptr) = branch {
548            Some(Offset::new(ptr, index, self.assoc))
549        } else {
550            None
551        }
552    }
553
554    pub fn at<T: ReadTxn>(
555        txn: &T,
556        branch: BranchPtr,
557        mut index: u32,
558        assoc: Assoc,
559    ) -> Option<Self> {
560        if assoc == Assoc::Before {
561            if index == 0 {
562                let context = IndexScope::from_branch(branch);
563                return Some(StickyIndex::new(context, assoc));
564            }
565            index -= 1;
566        }
567
568        let mut walker = BlockIter::new(branch);
569        if !walker.try_forward(txn, index) {
570            return None;
571        }
572        if walker.finished() {
573            if assoc == Assoc::Before {
574                let context = if let Some(ptr) = walker.next_item() {
575                    IndexScope::Relative(ptr.last_id())
576                } else {
577                    IndexScope::from_branch(branch)
578                };
579                Some(Self::new(context, assoc))
580            } else {
581                None
582            }
583        } else {
584            let context = if let Some(ptr) = walker.next_item() {
585                let mut id = ptr.id().clone();
586                id.clock += walker.rel();
587                IndexScope::Relative(id)
588            } else {
589                IndexScope::from_branch(branch)
590            };
591            Some(Self::new(context, assoc))
592        }
593    }
594
595    pub(crate) fn within_range(&self, ptr: Option<ItemPtr>) -> bool {
596        if self.assoc == Assoc::Before {
597            return false;
598        } else if let Some(item) = ptr.as_deref() {
599            if let Some(ptr) = item.left {
600                if let Some(pos) = self.id() {
601                    return ptr.last_id() != *pos;
602                }
603            }
604            false
605        } else {
606            true
607        }
608    }
609}
610
611impl Encode for StickyIndex {
612    fn encode<E: Encoder>(&self, encoder: &mut E) {
613        self.scope.encode(encoder);
614        self.assoc.encode(encoder);
615    }
616}
617
618impl Decode for StickyIndex {
619    fn decode<D: Decoder>(decoder: &mut D) -> Result<Self, Error> {
620        let context = IndexScope::decode(decoder)?;
621        let assoc = Assoc::decode(decoder)?;
622        Ok(Self::new(context, assoc))
623    }
624}
625
626impl Serialize for StickyIndex {
627    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
628    where
629        S: Serializer,
630    {
631        let mut s = serializer.serialize_struct("StickyIndex", 2)?;
632        match &self.scope {
633            IndexScope::Relative(id) => s.serialize_field("item", id)?,
634            IndexScope::Nested(id) => s.serialize_field("type", id)?,
635            IndexScope::Root(name) => s.serialize_field("tname", name)?,
636        }
637        let assoc = self.assoc as i8;
638        s.serialize_field("assoc", &assoc)?;
639        s.end()
640    }
641}
642
643impl<'de> Deserialize<'de> for StickyIndex {
644    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
645    where
646        D: Deserializer<'de>,
647    {
648        struct StickyIndexVisitor;
649        impl<'de> Visitor<'de> for StickyIndexVisitor {
650            type Value = StickyIndex;
651
652            fn expecting(&self, formatter: &mut Formatter) -> std::fmt::Result {
653                write!(formatter, "StickyIndex")
654            }
655
656            fn visit_map<A>(self, mut access: A) -> Result<Self::Value, A::Error>
657            where
658                A: MapAccess<'de>,
659            {
660                let mut item = None;
661                let mut ttype = None;
662                let mut tname = None;
663                let mut assoc = None;
664                while let Some(key) = access.next_key::<String>()? {
665                    match &*key {
666                        "item" => {
667                            item = access.next_value()?;
668                        }
669                        "type" => {
670                            ttype = access.next_value()?;
671                        }
672                        "tname" => {
673                            tname = access.next_value()?;
674                        }
675                        "assoc" => {
676                            assoc = access.next_value()?;
677                        }
678                        _ => {
679                            return Err(serde::de::Error::unknown_field(
680                                &*key,
681                                &["item", "type", "tname", "assoc"],
682                            ));
683                        }
684                    }
685                }
686                let scope = if let Some(id) = item {
687                    IndexScope::Relative(id)
688                } else if let Some(name) = tname {
689                    IndexScope::Root(name)
690                } else if let Some(id) = ttype {
691                    IndexScope::Nested(id)
692                } else {
693                    return Err(serde::de::Error::missing_field("item"));
694                };
695                let assoc = if let Some(assoc) = assoc {
696                    match assoc {
697                        0 => Assoc::After,
698                        -1 => Assoc::Before,
699                        _ => return Err(serde::de::Error::custom("invalid assoc value")),
700                    }
701                } else {
702                    Assoc::default()
703                };
704                Ok(StickyIndex::new(scope, assoc))
705            }
706        }
707        deserializer.deserialize_map(StickyIndexVisitor)
708    }
709}
710
711impl std::fmt::Display for StickyIndex {
712    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
713        if self.assoc == Assoc::Before {
714            write!(f, "<")?;
715        }
716        if let Some(id) = self.id() {
717            write!(f, "{}", id)?;
718        }
719        if self.assoc == Assoc::After {
720            write!(f, ">")?;
721        }
722        Ok(())
723    }
724}
725
726/// Struct describing context in which [StickyIndex] is placed. For items pointing inside of
727/// the shared typed sequence it's always [StickyIndex::Relative] which refers to a block [ID]
728/// found under corresponding position.
729///
730/// In case when a containing collection is empty, there's a no block [ID] that can be used as point
731/// of reference. In that case we store either a parent collection root type name or its branch [ID]
732/// instead (if collection is nested into another).
733///
734/// Using [ID]s guarantees that corresponding [StickyIndex] doesn't shift under incoming
735/// concurrent updates.
736#[derive(Debug, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Serialize, Deserialize)]
737pub enum IndexScope {
738    /// [StickyIndex] is relative to a given block [ID]. This happens whenever we set [StickyIndex]
739    /// somewhere inside the non-empty shared collection.
740    Relative(ID),
741    /// If a containing collection is a nested y-type, which is empty, this case allows us to
742    /// identify that nested type.
743    Nested(ID),
744    /// If a containing collection is a root-level y-type, which is empty, this case allows us to
745    /// identify that nested type.
746    Root(Arc<str>),
747}
748
749impl IndexScope {
750    pub fn from_branch(branch: BranchPtr) -> Self {
751        match branch.id() {
752            BranchID::Nested(id) => IndexScope::Nested(id),
753            BranchID::Root(name) => IndexScope::Root(name),
754        }
755    }
756}
757
758impl Encode for IndexScope {
759    fn encode<E: Encoder>(&self, encoder: &mut E) {
760        match self {
761            IndexScope::Relative(id) => {
762                encoder.write_var(0);
763                encoder.write_var(id.client);
764                encoder.write_var(id.clock);
765            }
766            IndexScope::Nested(id) => {
767                encoder.write_var(2);
768                encoder.write_var(id.client);
769                encoder.write_var(id.clock);
770            }
771            IndexScope::Root(type_name) => {
772                encoder.write_var(1);
773                encoder.write_string(&type_name);
774            }
775        }
776    }
777}
778
779impl Decode for IndexScope {
780    fn decode<D: Decoder>(decoder: &mut D) -> Result<Self, Error> {
781        let tag: u8 = decoder.read_var()?;
782        match tag {
783            0 => {
784                let client = decoder.read_var()?;
785                let clock = decoder.read_var()?;
786                Ok(IndexScope::Relative(ID::new(client, clock)))
787            }
788            1 => {
789                let type_name = decoder.read_string()?;
790                Ok(IndexScope::Root(type_name.into()))
791            }
792            2 => {
793                let client = decoder.read_var()?;
794                let clock = decoder.read_var()?;
795                Ok(IndexScope::Nested(ID::new(client, clock)))
796            }
797            _ => Err(Error::UnexpectedValue),
798        }
799    }
800}
801
802/// Association type used by [StickyIndex]. In general [StickyIndex] refers to a cursor
803/// space between two elements (eg. "ab.c" where "abc" is our string and `.` is the [StickyIndex]
804/// placement). However in a situation when another peer is updating a collection concurrently,
805/// a new set of elements may be inserted into that space, expanding it in the result. In such case
806/// [Assoc] tells us if the [StickyIndex] should stick to location before or after referenced index.
807#[repr(i8)]
808#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
809pub enum Assoc {
810    /// The corresponding [StickyIndex] points to space **after** the referenced [ID].
811    After = 0,
812    /// The corresponding [StickyIndex] points to space **before** the referenced [ID].
813    Before = -1,
814}
815
816impl Default for Assoc {
817    #[inline]
818    fn default() -> Self {
819        Assoc::After
820    }
821}
822
823impl Serialize for Assoc {
824    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
825    where
826        S: Serializer,
827    {
828        match self {
829            Assoc::After => serializer.serialize_i8(0),
830            Assoc::Before => serializer.serialize_i8(-1),
831        }
832    }
833}
834
835impl<'de> Deserialize<'de> for Assoc {
836    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
837    where
838        D: Deserializer<'de>,
839    {
840        struct AssocVisitor;
841        impl Visitor<'_> for AssocVisitor {
842            type Value = Assoc;
843
844            fn expecting(&self, formatter: &mut Formatter) -> std::fmt::Result {
845                write!(formatter, "Assoc")
846            }
847
848            #[inline]
849            fn visit_u64<E>(self, _: u64) -> Result<Self::Value, E>
850            where
851                E: serde::de::Error,
852            {
853                Ok(Assoc::After)
854            }
855
856            #[inline]
857            fn visit_i64<E>(self, v: i64) -> Result<Self::Value, E>
858            where
859                E: serde::de::Error,
860            {
861                if v < 0 {
862                    Ok(Assoc::Before)
863                } else {
864                    Ok(Assoc::After)
865                }
866            }
867        }
868        deserializer.deserialize_i64(AssocVisitor)
869    }
870}
871
872impl Encode for Assoc {
873    fn encode<E: Encoder>(&self, encoder: &mut E) {
874        match self {
875            Assoc::Before => encoder.write_var(-1),
876            Assoc::After => encoder.write_var(0),
877        }
878    }
879}
880
881impl Decode for Assoc {
882    fn decode<D: Decoder>(decoder: &mut D) -> Result<Self, Error> {
883        let tag: i8 = decoder.read_var()?;
884        Ok(if tag >= 0 {
885            Assoc::After
886        } else {
887            Assoc::Before
888        })
889    }
890}
891
892/// Trait used to retrieve a [StickyIndex] corresponding to a given human-readable index.
893/// Unlike standard indexes [StickyIndex] enables to track the location inside of a shared
894/// y-types, even in the face of concurrent updates.
895pub trait IndexedSequence: AsRef<Branch> {
896    /// Returns a [StickyIndex] equivalent to a human-readable `index`.
897    /// Returns `None` if `index` is beyond the length of current sequence.
898    fn sticky_index(
899        &self,
900        txn: &mut TransactionMut,
901        index: u32,
902        assoc: Assoc,
903    ) -> Option<StickyIndex> {
904        StickyIndex::at(txn, BranchPtr::from(self.as_ref()), index, assoc)
905    }
906}
907
908/// [Offset] is a result of mapping of [StickyIndex] onto document store at a current
909/// point in time.
910#[derive(Debug, Clone, Eq, PartialEq, Hash)]
911pub struct Offset {
912    /// Pointer to a collection type [Offset] refers to.
913    pub branch: BranchPtr,
914    /// Human readable index corresponding to this [Offset].
915    pub index: u32,
916    /// Association type used by [StickyIndex] this structure was created from.
917    pub assoc: Assoc,
918}
919
920impl Offset {
921    fn new(branch: BranchPtr, index: u32, assoc: Assoc) -> Self {
922        Offset {
923            branch,
924            index,
925            assoc,
926        }
927    }
928}
929
930#[cfg(test)]
931mod test {
932    use crate::moving::Assoc;
933    use crate::updates::decoder::Decode;
934    use crate::updates::encoder::Encode;
935    use crate::{Doc, IndexScope, IndexedSequence, StickyIndex, Text, TextRef, Transact, ID};
936    use serde::{Deserialize, Serialize};
937
938    fn check_sticky_indexes(doc: &Doc, text: &TextRef) {
939        // test if all positions are encoded and restored correctly
940        let mut txn = doc.transact_mut();
941        let len = text.len(&txn);
942        for i in 0..len {
943            // for all types of associations..
944            for assoc in [Assoc::After, Assoc::Before] {
945                let rel_pos = text.sticky_index(&mut txn, i, assoc).unwrap();
946                let encoded = rel_pos.encode_v1();
947                let decoded = StickyIndex::decode_v1(&encoded).unwrap();
948                let abs_pos = decoded
949                    .get_offset(&txn)
950                    .expect(&format!("offset not found for index {} of {}", i, decoded));
951                assert_eq!(abs_pos.index, i);
952                assert_eq!(abs_pos.assoc, assoc);
953            }
954        }
955    }
956
957    #[test]
958    fn sticky_index_case_1() {
959        let doc = Doc::with_client_id(1);
960        let txt = doc.get_or_insert_text("test");
961
962        {
963            let mut txn = doc.transact_mut();
964            txt.insert(&mut txn, 0, "1");
965            txt.insert(&mut txn, 0, "abc");
966            txt.insert(&mut txn, 0, "z");
967            txt.insert(&mut txn, 0, "y");
968            txt.insert(&mut txn, 0, "x");
969        }
970
971        check_sticky_indexes(&doc, &txt);
972    }
973
974    #[test]
975    fn sticky_index_case_2() {
976        let doc = Doc::with_client_id(1);
977        let txt = doc.get_or_insert_text("test");
978
979        txt.insert(&mut doc.transact_mut(), 0, "abc");
980        check_sticky_indexes(&doc, &txt);
981    }
982
983    #[test]
984    fn sticky_index_case_3() {
985        let doc = Doc::with_client_id(1);
986        let txt = doc.get_or_insert_text("test");
987
988        {
989            let mut txn = doc.transact_mut();
990            txt.insert(&mut txn, 0, "abc");
991            txt.insert(&mut txn, 0, "1");
992            txt.insert(&mut txn, 0, "xyz");
993        }
994
995        check_sticky_indexes(&doc, &txt);
996    }
997
998    #[test]
999    fn sticky_index_case_4() {
1000        let doc = Doc::with_client_id(1);
1001        let txt = doc.get_or_insert_text("test");
1002
1003        txt.insert(&mut doc.transact_mut(), 0, "1");
1004        check_sticky_indexes(&doc, &txt);
1005    }
1006
1007    #[test]
1008    fn sticky_index_case_5() {
1009        let doc = Doc::with_client_id(1);
1010        let txt = doc.get_or_insert_text("test");
1011
1012        {
1013            let mut txn = doc.transact_mut();
1014            txt.insert(&mut txn, 0, "2");
1015            txt.insert(&mut txn, 0, "1");
1016        }
1017
1018        check_sticky_indexes(&doc, &txt);
1019    }
1020
1021    #[test]
1022    fn sticky_index_case_6() {
1023        let doc = Doc::with_client_id(1);
1024        let txt = doc.get_or_insert_text("test");
1025        check_sticky_indexes(&doc, &txt);
1026    }
1027
1028    #[test]
1029    fn sticky_index_association_difference() {
1030        let doc = Doc::with_client_id(1);
1031        let txt = doc.get_or_insert_text("test");
1032
1033        let mut txn = doc.transact_mut();
1034        txt.insert(&mut txn, 0, "2");
1035        txt.insert(&mut txn, 0, "1");
1036
1037        let rpos_right = txt.sticky_index(&mut txn, 1, Assoc::After).unwrap();
1038        let rpos_left = txt.sticky_index(&mut txn, 1, Assoc::Before).unwrap();
1039
1040        txt.insert(&mut txn, 1, "x");
1041
1042        let pos_right = rpos_right.get_offset(&txn).unwrap();
1043        let pos_left = rpos_left.get_offset(&txn).unwrap();
1044
1045        assert_eq!(pos_right.index, 2);
1046        assert_eq!(pos_left.index, 1);
1047    }
1048
1049    #[test]
1050    fn sticky_index_is_yjs_compatible() {
1051        // below is the example data passed from Yjs tiptap plugin
1052        #[derive(Serialize, Deserialize)]
1053        struct AwarenessData {
1054            user: User,
1055            cursor: Cursor,
1056        }
1057        #[derive(Serialize, Deserialize)]
1058        struct Cursor {
1059            anchor: StickyIndex,
1060            head: StickyIndex,
1061        }
1062        #[derive(Serialize, Deserialize)]
1063        struct User {
1064            name: String,
1065            color: String,
1066        }
1067        let json = serde_json::json!({
1068            "user":{"name":"Grace","color":"#FAF594"},
1069            "cursor":{
1070                "anchor":{"type":{"client":3731284436u32,"clock":1},"tname":null,"item":{"client":3731284436u32,"clock":20},"assoc":-1},
1071                "head":{"type":{"client":3731284436u32,"clock":1},"tname":null,"item":{"client":3731284436u32,"clock":20},"assoc":-1}
1072            }
1073        });
1074        let data: AwarenessData = serde_json::from_value(json.clone()).unwrap();
1075        assert_eq!(
1076            data.cursor.anchor,
1077            StickyIndex::new(IndexScope::Relative(ID::new(3731284436, 20)), Assoc::Before)
1078        );
1079        assert_eq!(
1080            data.cursor.head,
1081            StickyIndex::new(IndexScope::Relative(ID::new(3731284436, 20)), Assoc::Before)
1082        );
1083        let json2 = serde_json::to_value(&data).unwrap();
1084        assert_eq!(
1085            json2["cursor"]["anchor"]["item"],
1086            serde_json::json!({"client":3731284436u32,"clock":20})
1087        );
1088        assert_eq!(json2["cursor"]["anchor"]["assoc"], serde_json::json!(-1));
1089        assert_eq!(
1090            json2["cursor"]["head"]["item"],
1091            serde_json::json!({"client":3731284436u32,"clock":20})
1092        );
1093        assert_eq!(json2["cursor"]["head"]["assoc"], serde_json::json!(-1));
1094    }
1095}
yrs/moving.rs

yrs/
moving.rs
