amadan

oficina / docs Public

Clone 
git clone https://amadan.net/oficina/docs

Plain git — no account needed to clone.

Download

Download this file

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 /// Scope refers to root collection.
441 #[inline]
442 pub fn is_root(&self) -> bool {
443 if let IndexScope::Root(_) = &self.scope {
444 true
445 } else {
446 false
447 }
448 }
449
450 /// Scope refers to nested shared collection.
451 #[inline]
452 pub fn is_nested(&self) -> bool {
453 if let IndexScope::Nested(_) = &self.scope {
454 true
455 } else {
456 false
457 }
458 }
459
460 /// Scope refers to a position relative to another block.
461 #[inline]
462 pub fn is_relative(&self) -> bool {
463 if let IndexScope::Relative(_) = &self.scope {
464 true
465 } else {
466 false
467 }
468 }
469
470 /// Returns an [ID] of the block position which is used as a reference to keep track the location
471 /// of current [StickyIndex] even in face of changes performed by different peers.
472 ///
473 /// Returns `None` if current [StickyIndex] has been created on an empty shared collection (in
474 /// that case there's no block that we can refer to).
475 pub fn id(&self) -> Option<&ID> {
476 if let IndexScope::Relative(id) = &self.scope {
477 Some(id)
478 } else {
479 None
480 }
481 }
482
483 /// Maps current [StickyIndex] onto [Offset] which points to shared collection and a
484 /// human-readable index in that collection.
485 ///
486 /// That index is only valid at the current point in time - if i.e. another update from remote
487 /// peer has been applied, it may have changed relative index position that [StickyIndex] points
488 /// to, so that [Offset]'s index will no longer point to the same place.
489 ///
490 /// # Examples
491 ///
492 /// ```rust
493 /// use yrs::{Assoc, Doc, IndexedSequence, Text, Transact};
494 ///
495 /// let doc = Doc::new();
496 /// let text = doc.get_or_insert_text("text");
497 /// let mut txn = doc.transact_mut();
498 ///
499 /// text.insert(&mut txn, 0, "hello world");
500 ///
501 /// const INDEX: u32 = 4;
502 ///
503 /// // set perma index at position before letter 'o' => "hell.o world"
504 /// let pos = text.sticky_index(&mut txn, INDEX, Assoc::After).unwrap();
505 /// let off = pos.get_offset(&txn).unwrap();
506 /// assert_eq!(off.index, INDEX);
507 ///
508 /// // perma index will maintain it's position before letter 'o' even if another update
509 /// // shifted it's index inside of the text
510 /// text.insert(&mut txn, 1, "(see)"); // => "h(see)ell.o world" where . is perma index position
511 /// let off2 = pos.get_offset(&txn).unwrap();
512 /// assert_ne!(off2.index, off.index); // offset index changed due to new insert above
513 /// ```
514 pub fn get_offset<T: ReadTxn>(&self, txn: &T) -> Option<Offset> {
515 let mut branch = None;
516 let mut index = 0;
517
518 match &self.scope {
519 IndexScope::Relative(right_id) => {
520 let store = txn.store();
521 if store.blocks.get_clock(&right_id.client) <= right_id.clock {
522 // type does not exist yet
523 return None;
524 }
525 let right = store.follow_redone(right_id);
526 if let Some(right) = right {
527 if let Some(b) = right.ptr.parent.as_branch() {
528 branch = Some(b.clone());
529 match b.item {
530 Some(i) if i.is_deleted() => { /* do nothing */ }
531 _ => {
532 // adjust position based on left association if necessary
533 index = if right.is_deleted() || !right.is_countable() {
534 0
535 } else if self.assoc == Assoc::After {
536 right.start
537 } else {
538 right.start + 1
539 };
540 let encoding = store.offset_kind;
541 let mut n = right.ptr.left;
542 while let Some(item) = n.as_deref() {
543 if !item.is_deleted() && item.is_countable() {
544 index += item.content_len(encoding);
545 }
546 n = item.left;
547 }
548 }
549 }
550 }
551 }
552 }
553 IndexScope::Nested(id) => {
554 let store = txn.store();
555 if store.blocks.get_clock(&id.client) <= id.clock {
556 // type does not exist yet
557 return None;
558 }
559 let item = store.follow_redone(id)?; // early return if item is GC'ed
560 if let ItemContent::Type(b) = &item.ptr.content {
561 // we don't need to materilized ItemContent::Type - they are always 1-length
562 branch = Some(BranchPtr::from(b.as_ref()));
563 } // else - branch remains null
564 }
565 IndexScope::Root(name) => {
566 branch = txn.store().get_type(name.clone());
567 if let Some(ptr) = branch.as_ref() {
568 index = if self.assoc == Assoc::After {
569 ptr.content_len
570 } else {
571 0
572 };
573 }
574 }
575 }
576
577 if let Some(ptr) = branch {
578 Some(Offset::new(ptr, index, self.assoc))
579 } else {
580 None
581 }
582 }
583
584 pub fn at<T: ReadTxn>(
585 txn: &T,
586 branch: BranchPtr,
587 mut index: u32,
588 assoc: Assoc,
589 ) -> Option<Self> {
590 if assoc == Assoc::Before {
591 if index == 0 {
592 let context = IndexScope::from_branch(branch);
593 return Some(StickyIndex::new(context, assoc));
594 }
595 index -= 1;
596 }
597
598 let mut walker = BlockIter::new(branch);
599 if !walker.try_forward(txn, index) {
600 return None;
601 }
602 if walker.finished() {
603 if assoc == Assoc::Before {
604 let context = if let Some(ptr) = walker.next_item() {
605 IndexScope::Relative(ptr.last_id())
606 } else {
607 IndexScope::from_branch(branch)
608 };
609 Some(Self::new(context, assoc))
610 } else {
611 None
612 }
613 } else {
614 let context = if let Some(ptr) = walker.next_item() {
615 let mut id = ptr.id().clone();
616 id.clock += walker.rel();
617 IndexScope::Relative(id)
618 } else {
619 IndexScope::from_branch(branch)
620 };
621 Some(Self::new(context, assoc))
622 }
623 }
624
625 pub(crate) fn within_range(&self, ptr: Option<ItemPtr>) -> bool {
626 if self.assoc == Assoc::Before {
627 return false;
628 } else if let Some(item) = ptr.as_deref() {
629 if let Some(ptr) = item.left {
630 if let Some(pos) = self.id() {
631 return ptr.last_id() != *pos;
632 }
633 }
634 false
635 } else {
636 true
637 }
638 }
639
640 pub(crate) fn get_item<T: ReadTxn>(&self, txn: &T) -> Option<ItemPtr> {
641 let branch = match &self.scope {
642 IndexScope::Relative(id) => {
643 // position relative to existing block
644 let item = txn.store().blocks.get_item(id)?;
645 return if self.assoc == Assoc::After && &item.last_id() == id {
646 item.right
647 } else {
648 Some(item)
649 };
650 }
651 IndexScope::Nested(id) => {
652 // position at the beginning/end of a nested type
653 let item = txn.store().blocks.get_item(id)?;
654 item.as_branch()?
655 }
656 IndexScope::Root(name) => {
657 // position at the beginning/end of a root type
658 let branch = txn.store().types.get(name.as_ref())?;
659 BranchPtr::from(branch)
660 }
661 };
662 match &self.assoc {
663 // get first item of a branch
664 Assoc::Before => branch.start,
665 // get last item of a branch
666 Assoc::After => {
667 let mut item = branch.item?;
668 while let Some(right) = item.right {
669 item = right;
670 }
671 Some(item)
672 }
673 }
674 }
675}
676
677impl Encode for StickyIndex {
678 fn encode<E: Encoder>(&self, encoder: &mut E) {
679 self.scope.encode(encoder);
680 self.assoc.encode(encoder);
681 }
682}
683
684impl Decode for StickyIndex {
685 fn decode<D: Decoder>(decoder: &mut D) -> Result<Self, Error> {
686 let context = IndexScope::decode(decoder)?;
687 let assoc = Assoc::decode(decoder)?;
688 Ok(Self::new(context, assoc))
689 }
690}
691
692impl Serialize for StickyIndex {
693 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
694 where
695 S: Serializer,
696 {
697 let mut s = serializer.serialize_struct("StickyIndex", 2)?;
698 match &self.scope {
699 IndexScope::Relative(id) => s.serialize_field("item", id)?,
700 IndexScope::Nested(id) => s.serialize_field("type", id)?,
701 IndexScope::Root(name) => s.serialize_field("tname", name)?,
702 }
703 let assoc = self.assoc as i8;
704 s.serialize_field("assoc", &assoc)?;
705 s.end()
706 }
707}
708
709impl<'de> Deserialize<'de> for StickyIndex {
710 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
711 where
712 D: Deserializer<'de>,
713 {
714 struct StickyIndexVisitor;
715 impl<'de> Visitor<'de> for StickyIndexVisitor {
716 type Value = StickyIndex;
717
718 fn expecting(&self, formatter: &mut Formatter) -> std::fmt::Result {
719 write!(formatter, "StickyIndex")
720 }
721
722 fn visit_map<A>(self, mut access: A) -> Result<Self::Value, A::Error>
723 where
724 A: MapAccess<'de>,
725 {
726 let mut item = None;
727 let mut ttype = None;
728 let mut tname = None;
729 let mut assoc = None;
730 while let Some(key) = access.next_key::<String>()? {
731 match &*key {
732 "item" => {
733 item = access.next_value()?;
734 }
735 "type" => {
736 ttype = access.next_value()?;
737 }
738 "tname" => {
739 tname = access.next_value()?;
740 }
741 "assoc" => {
742 assoc = access.next_value()?;
743 }
744 _ => {
745 return Err(serde::de::Error::unknown_field(
746 &*key,
747 &["item", "type", "tname", "assoc"],
748 ));
749 }
750 }
751 }
752 let scope = if let Some(id) = item {
753 IndexScope::Relative(id)
754 } else if let Some(name) = tname {
755 IndexScope::Root(name)
756 } else if let Some(id) = ttype {
757 IndexScope::Nested(id)
758 } else {
759 return Err(serde::de::Error::missing_field("item"));
760 };
761 let assoc = if let Some(assoc) = assoc {
762 match assoc {
763 0 => Assoc::After,
764 -1 => Assoc::Before,
765 _ => return Err(serde::de::Error::custom("invalid assoc value")),
766 }
767 } else {
768 Assoc::default()
769 };
770 Ok(StickyIndex::new(scope, assoc))
771 }
772 }
773 deserializer.deserialize_map(StickyIndexVisitor)
774 }
775}
776
777impl std::fmt::Display for StickyIndex {
778 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
779 if self.assoc == Assoc::Before {
780 write!(f, "<")?;
781 }
782 if let Some(id) = self.id() {
783 write!(f, "{}", id)?;
784 }
785 if self.assoc == Assoc::After {
786 write!(f, ">")?;
787 }
788 Ok(())
789 }
790}
791
792/// Struct describing context in which [StickyIndex] is placed. For items pointing inside of
793/// the shared typed sequence it's always [StickyIndex::Relative] which refers to a block [ID]
794/// found under corresponding position.
795///
796/// In case when a containing collection is empty, there's a no block [ID] that can be used as point
797/// of reference. In that case we store either a parent collection root type name or its branch [ID]
798/// instead (if collection is nested into another).
799///
800/// Using [ID]s guarantees that corresponding [StickyIndex] doesn't shift under incoming
801/// concurrent updates.
802#[derive(Debug, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Serialize, Deserialize)]
803pub enum IndexScope {
804 /// [StickyIndex] is relative to a given block [ID]. This happens whenever we set [StickyIndex]
805 /// somewhere inside the non-empty shared collection.
806 Relative(ID),
807 /// If a containing collection is a nested y-type, which is empty, this case allows us to
808 /// identify that nested type.
809 Nested(ID),
810 /// If a containing collection is a root-level y-type, which is empty, this case allows us to
811 /// identify that nested type.
812 Root(Arc<str>),
813}
814
815impl IndexScope {
816 pub fn from_branch(branch: BranchPtr) -> Self {
817 match branch.id() {
818 BranchID::Nested(id) => IndexScope::Nested(id),
819 BranchID::Root(name) => IndexScope::Root(name),
820 }
821 }
822}
823
824impl Encode for IndexScope {
825 fn encode<E: Encoder>(&self, encoder: &mut E) {
826 match self {
827 IndexScope::Relative(id) => {
828 encoder.write_var(0);
829 encoder.write_var(id.client);
830 encoder.write_var(id.clock);
831 }
832 IndexScope::Nested(id) => {
833 encoder.write_var(2);
834 encoder.write_var(id.client);
835 encoder.write_var(id.clock);
836 }
837 IndexScope::Root(type_name) => {
838 encoder.write_var(1);
839 encoder.write_string(&type_name);
840 }
841 }
842 }
843}
844
845impl Decode for IndexScope {
846 fn decode<D: Decoder>(decoder: &mut D) -> Result<Self, Error> {
847 let tag: u8 = decoder.read_var()?;
848 match tag {
849 0 => {
850 let client = decoder.read_var()?;
851 let clock = decoder.read_var()?;
852 Ok(IndexScope::Relative(ID::new(client, clock)))
853 }
854 1 => {
855 let type_name = decoder.read_string()?;
856 Ok(IndexScope::Root(type_name.into()))
857 }
858 2 => {
859 let client = decoder.read_var()?;
860 let clock = decoder.read_var()?;
861 Ok(IndexScope::Nested(ID::new(client, clock)))
862 }
863 _ => Err(Error::UnexpectedValue),
864 }
865 }
866}
867
868/// Association type used by [StickyIndex]. In general [StickyIndex] refers to a cursor
869/// space between two elements (eg. "ab.c" where "abc" is our string and `.` is the [StickyIndex]
870/// placement). However in a situation when another peer is updating a collection concurrently,
871/// a new set of elements may be inserted into that space, expanding it in the result. In such case
872/// [Assoc] tells us if the [StickyIndex] should stick to location before or after referenced index.
873#[repr(i8)]
874#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
875pub enum Assoc {
876 /// The corresponding [StickyIndex] points to space **after** the referenced [ID].
877 After = 0,
878 /// The corresponding [StickyIndex] points to space **before** the referenced [ID].
879 Before = -1,
880}
881
882impl Default for Assoc {
883 #[inline]
884 fn default() -> Self {
885 Assoc::After
886 }
887}
888
889impl Serialize for Assoc {
890 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
891 where
892 S: Serializer,
893 {
894 match self {
895 Assoc::After => serializer.serialize_i8(0),
896 Assoc::Before => serializer.serialize_i8(-1),
897 }
898 }
899}
900
901impl<'de> Deserialize<'de> for Assoc {
902 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
903 where
904 D: Deserializer<'de>,
905 {
906 struct AssocVisitor;
907 impl Visitor<'_> for AssocVisitor {
908 type Value = Assoc;
909
910 fn expecting(&self, formatter: &mut Formatter) -> std::fmt::Result {
911 write!(formatter, "Assoc")
912 }
913
914 #[inline]
915 fn visit_u64<E>(self, _: u64) -> Result<Self::Value, E>
916 where
917 E: serde::de::Error,
918 {
919 Ok(Assoc::After)
920 }
921
922 #[inline]
923 fn visit_i64<E>(self, v: i64) -> Result<Self::Value, E>
924 where
925 E: serde::de::Error,
926 {
927 if v < 0 {
928 Ok(Assoc::Before)
929 } else {
930 Ok(Assoc::After)
931 }
932 }
933 }
934 deserializer.deserialize_i64(AssocVisitor)
935 }
936}
937
938impl Encode for Assoc {
939 fn encode<E: Encoder>(&self, encoder: &mut E) {
940 match self {
941 Assoc::Before => encoder.write_var(-1),
942 Assoc::After => encoder.write_var(0),
943 }
944 }
945}
946
947impl Decode for Assoc {
948 fn decode<D: Decoder>(decoder: &mut D) -> Result<Self, Error> {
949 let tag: i8 = decoder.read_var()?;
950 Ok(if tag >= 0 {
951 Assoc::After
952 } else {
953 Assoc::Before
954 })
955 }
956}
957
958/// Trait used to retrieve a [StickyIndex] corresponding to a given human-readable index.
959/// Unlike standard indexes [StickyIndex] enables to track the location inside of a shared
960/// y-types, even in the face of concurrent updates.
961pub trait IndexedSequence: AsRef<Branch> {
962 /// Returns a [StickyIndex] equivalent to a human-readable `index`.
963 /// Returns `None` if `index` is beyond the length of current sequence.
964 fn sticky_index(
965 &self,
966 txn: &mut TransactionMut,
967 index: u32,
968 assoc: Assoc,
969 ) -> Option<StickyIndex> {
970 StickyIndex::at(txn, BranchPtr::from(self.as_ref()), index, assoc)
971 }
972}
973
974/// [Offset] is a result of mapping of [StickyIndex] onto document store at a current
975/// point in time.
976#[derive(Debug, Clone, Eq, PartialEq, Hash)]
977pub struct Offset {
978 /// Pointer to a collection type [Offset] refers to.
979 pub branch: BranchPtr,
980 /// Human readable index corresponding to this [Offset].
981 pub index: u32,
982 /// Association type used by [StickyIndex] this structure was created from.
983 pub assoc: Assoc,
984}
985
986impl Offset {
987 fn new(branch: BranchPtr, index: u32, assoc: Assoc) -> Self {
988 Offset {
989 branch,
990 index,
991 assoc,
992 }
993 }
994}
995
996#[cfg(test)]
997mod test {
998 use crate::moving::Assoc;
999 use crate::updates::decoder::Decode;
1000 use crate::updates::encoder::Encode;
1001 use crate::{Doc, IndexScope, IndexedSequence, StickyIndex, Text, TextRef, Transact, ID};
1002 use serde::{Deserialize, Serialize};
1003
1004 fn check_sticky_indexes(doc: &Doc, text: &TextRef) {
1005 // test if all positions are encoded and restored correctly
1006 let mut txn = doc.transact_mut();
1007 let len = text.len(&txn);
1008 for i in 0..len {
1009 // for all types of associations..
1010 for assoc in [Assoc::After, Assoc::Before] {
1011 let rel_pos = text.sticky_index(&mut txn, i, assoc).unwrap();
1012 let encoded = rel_pos.encode_v1();
1013 let decoded = StickyIndex::decode_v1(&encoded).unwrap();
1014 let abs_pos = decoded
1015 .get_offset(&txn)
1016 .expect(&format!("offset not found for index {} of {}", i, decoded));
1017 assert_eq!(abs_pos.index, i);
1018 assert_eq!(abs_pos.assoc, assoc);
1019 }
1020 }
1021 }
1022
1023 #[test]
1024 fn sticky_index_case_1() {
1025 let doc = Doc::with_client_id(1);
1026 let txt = doc.get_or_insert_text("test");
1027
1028 {
1029 let mut txn = doc.transact_mut();
1030 txt.insert(&mut txn, 0, "1");
1031 txt.insert(&mut txn, 0, "abc");
1032 txt.insert(&mut txn, 0, "z");
1033 txt.insert(&mut txn, 0, "y");
1034 txt.insert(&mut txn, 0, "x");
1035 }
1036
1037 check_sticky_indexes(&doc, &txt);
1038 }
1039
1040 #[test]
1041 fn sticky_index_case_2() {
1042 let doc = Doc::with_client_id(1);
1043 let txt = doc.get_or_insert_text("test");
1044
1045 txt.insert(&mut doc.transact_mut(), 0, "abc");
1046 check_sticky_indexes(&doc, &txt);
1047 }
1048
1049 #[test]
1050 fn sticky_index_case_3() {
1051 let doc = Doc::with_client_id(1);
1052 let txt = doc.get_or_insert_text("test");
1053
1054 {
1055 let mut txn = doc.transact_mut();
1056 txt.insert(&mut txn, 0, "abc");
1057 txt.insert(&mut txn, 0, "1");
1058 txt.insert(&mut txn, 0, "xyz");
1059 }
1060
1061 check_sticky_indexes(&doc, &txt);
1062 }
1063
1064 #[test]
1065 fn sticky_index_case_4() {
1066 let doc = Doc::with_client_id(1);
1067 let txt = doc.get_or_insert_text("test");
1068
1069 txt.insert(&mut doc.transact_mut(), 0, "1");
1070 check_sticky_indexes(&doc, &txt);
1071 }
1072
1073 #[test]
1074 fn sticky_index_case_5() {
1075 let doc = Doc::with_client_id(1);
1076 let txt = doc.get_or_insert_text("test");
1077
1078 {
1079 let mut txn = doc.transact_mut();
1080 txt.insert(&mut txn, 0, "2");
1081 txt.insert(&mut txn, 0, "1");
1082 }
1083
1084 check_sticky_indexes(&doc, &txt);
1085 }
1086
1087 #[test]
1088 fn sticky_index_case_6() {
1089 let doc = Doc::with_client_id(1);
1090 let txt = doc.get_or_insert_text("test");
1091 check_sticky_indexes(&doc, &txt);
1092 }
1093
1094 #[test]
1095 fn sticky_index_association_difference() {
1096 let doc = Doc::with_client_id(1);
1097 let txt = doc.get_or_insert_text("test");
1098
1099 let mut txn = doc.transact_mut();
1100 txt.insert(&mut txn, 0, "2");
1101 txt.insert(&mut txn, 0, "1");
1102
1103 let rpos_right = txt.sticky_index(&mut txn, 1, Assoc::After).unwrap();
1104 let rpos_left = txt.sticky_index(&mut txn, 1, Assoc::Before).unwrap();
1105
1106 txt.insert(&mut txn, 1, "x");
1107
1108 let pos_right = rpos_right.get_offset(&txn).unwrap();
1109 let pos_left = rpos_left.get_offset(&txn).unwrap();
1110
1111 assert_eq!(pos_right.index, 2);
1112 assert_eq!(pos_left.index, 1);
1113 }
1114
1115 #[test]
1116 fn sticky_index_is_yjs_compatible() {
1117 // below is the example data passed from Yjs tiptap plugin
1118 #[derive(Serialize, Deserialize)]
1119 struct AwarenessData {
1120 user: User,
1121 cursor: Cursor,
1122 }
1123 #[derive(Serialize, Deserialize)]
1124 struct Cursor {
1125 anchor: StickyIndex,
1126 head: StickyIndex,
1127 }
1128 #[derive(Serialize, Deserialize)]
1129 struct User {
1130 name: String,
1131 color: String,
1132 }
1133 let json = serde_json::json!({
1134 "user":{"name":"Grace","color":"#FAF594"},
1135 "cursor":{
1136 "anchor":{"type":{"client":3731284436u32,"clock":1},"tname":null,"item":{"client":3731284436u32,"clock":20},"assoc":-1},
1137 "head":{"type":{"client":3731284436u32,"clock":1},"tname":null,"item":{"client":3731284436u32,"clock":20},"assoc":-1}
1138 }
1139 });
1140 let data: AwarenessData = serde_json::from_value(json.clone()).unwrap();
1141 assert_eq!(
1142 data.cursor.anchor,
1143 StickyIndex::new(IndexScope::Relative(ID::new(3731284436, 20)), Assoc::Before)
1144 );
1145 assert_eq!(
1146 data.cursor.head,
1147 StickyIndex::new(IndexScope::Relative(ID::new(3731284436, 20)), Assoc::Before)
1148 );
1149 let json2 = serde_json::to_value(&data).unwrap();
1150 assert_eq!(
1151 json2["cursor"]["anchor"]["item"],
1152 serde_json::json!({"client":3731284436u32,"clock":20})
1153 );
1154 assert_eq!(json2["cursor"]["anchor"]["assoc"], serde_json::json!(-1));
1155 assert_eq!(
1156 json2["cursor"]["head"]["item"],
1157 serde_json::json!({"client":3731284436u32,"clock":20})
1158 );
1159 assert_eq!(json2["cursor"]["head"]["assoc"], serde_json::json!(-1));
1160 }
1161}
1162