1use std::{collections::BTreeMap, fmt::Display};
2
3use super::{AsInner, list::ListType};
4use crate::{
5 Any, Content, JwstCodecError, JwstCodecResult,
6 doc::{DocStore, ItemRef, Node, Parent, Somr, YType, YTypeRef},
7 impl_type,
8};
9
10impl_type!(Text);
11
12impl ListType for Text {}
13
14#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
15#[serde(untagged)]
16pub enum TextInsert {
17 Text(String),
18 Embed(Vec<Any>),
19}
20
21#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
22#[serde(untagged)]
23pub enum TextDeltaOp {
24 Insert {
25 insert: TextInsert,
26 #[serde(skip_serializing_if = "Option::is_none")]
27 format: Option<TextAttributes>,
28 },
29 Retain {
30 retain: u64,
31 #[serde(skip_serializing_if = "Option::is_none")]
32 format: Option<TextAttributes>,
33 },
34 Delete {
35 delete: u64,
36 },
37}
38
39pub type TextDelta = Vec<TextDeltaOp>;
40pub type TextAttributes = BTreeMap<String, Any>;
41
42impl Text {
43 #[inline]
44 pub fn len(&self) -> u64 {
45 self.content_len()
46 }
47
48 #[inline]
49 pub fn is_empty(&self) -> bool {
50 self.len() == 0
51 }
52
53 #[inline]
54 pub fn insert<T: ToString>(&mut self, char_index: u64, str: T) -> JwstCodecResult {
55 self.insert_at(char_index, Content::String(str.to_string()))
56 }
57
58 #[inline]
59 pub fn remove(&mut self, char_index: u64, len: u64) -> JwstCodecResult {
60 self.remove_at(char_index, len)
61 }
62
63 pub fn to_delta(&self) -> TextDelta {
64 let mut ops = Vec::new();
65 let mut attrs = TextAttributes::new();
66
67 for item_ref in self.iter_item() {
68 if let Some(item) = item_ref.get() {
69 match &item.content {
70 Content::Format { key, value } => {
71 if is_nullish(value) {
72 attrs.remove(key.as_str());
73 } else {
74 attrs.insert(key.to_string(), value.clone());
75 }
76 }
77 Content::String(text) => {
78 push_insert(&mut ops, TextInsert::Text(text.clone()), &attrs);
79 }
80 Content::Embed(embed) => {
81 push_insert(&mut ops, TextInsert::Embed(vec![embed.clone()]), &attrs);
82 }
83 Content::Any(any) => {
84 push_insert(&mut ops, TextInsert::Embed(any.clone()), &attrs);
85 }
86 Content::Json(values) => {
87 let converted = values
88 .iter()
89 .map(|value| value.as_ref().map(|s| Any::String(s.clone())).unwrap_or(Any::Undefined))
90 .collect::<Vec<_>>();
91 push_insert(&mut ops, TextInsert::Embed(converted), &attrs);
92 }
93 Content::Binary(value) => {
94 push_insert(&mut ops, TextInsert::Embed(vec![Any::Binary(value.clone())]), &attrs);
95 }
96 _ => {}
97 }
98 }
99 }
100
101 ops
102 }
103
104 pub fn apply_delta(&mut self, delta: &[TextDeltaOp]) -> JwstCodecResult {
105 let (mut store, mut ty) = self.as_inner().write().ok_or(JwstCodecError::DocReleased)?;
106 let parent = self.as_inner().clone();
107
108 let mut pos = TextPosition::new(parent, ty.start.clone());
109
110 for op in delta {
111 match op {
112 TextDeltaOp::Insert { insert, format } => {
113 let attrs = format.clone().unwrap_or_default();
114 match insert {
115 TextInsert::Text(text) => {
116 insert_text_content(&mut store, &mut ty, &mut pos, Content::String(text.clone()), attrs)?;
117 }
118 TextInsert::Embed(values) => {
119 for value in values {
120 insert_text_content(
121 &mut store,
122 &mut ty,
123 &mut pos,
124 Content::Embed(value.clone()),
125 attrs.clone(),
126 )?;
127 }
128 }
129 }
130 }
131 TextDeltaOp::Retain { retain, format } => {
132 let attrs = format.clone().unwrap_or_default();
133 if attrs.is_empty() {
134 advance_text_position(&mut store, &mut pos, *retain)?;
135 } else {
136 format_text(&mut store, &mut ty, &mut pos, *retain, attrs)?;
137 }
138 }
139 TextDeltaOp::Delete { delete } => {
140 delete_text(&mut store, &mut ty, &mut pos, *delete)?;
141 }
142 }
143 }
144
145 Ok(())
146 }
147}
148
149impl Display for Text {
150 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
151 self.iter_item().try_for_each(|item| {
152 if let Content::String(str) = &item.get().unwrap().content {
153 write!(f, "{str}")
154 } else {
155 Ok(())
156 }
157 })
158 }
159}
160
161impl serde::Serialize for Text {
162 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
163 where
164 S: serde::Serializer,
165 {
166 serializer.serialize_str(&self.to_string())
167 }
168}
169
170struct TextPosition {
171 parent: YTypeRef,
172 left: ItemRef,
173 right: ItemRef,
174 index: u64,
175 attrs: TextAttributes,
176}
177
178impl TextPosition {
179 fn new(parent: YTypeRef, right: ItemRef) -> Self {
180 Self {
181 parent,
182 left: Somr::none(),
183 right,
184 index: 0,
185 attrs: TextAttributes::new(),
186 }
187 }
188
189 fn forward(&mut self) {
190 if let Some(right) = self.right.get() {
191 if !right.deleted() {
192 if let Content::Format { key, value } = &right.content {
193 if is_nullish(value) {
194 self.attrs.remove(key.as_str());
195 } else {
196 self.attrs.insert(key.to_string(), value.clone());
197 }
198 } else if right.countable() {
199 self.index += right.len();
200 }
201 }
202
203 self.left = self.right.clone();
204 self.right = right.right.clone();
205 }
206 }
207}
208
209fn is_nullish(value: &Any) -> bool {
210 matches!(value, Any::Null | Any::Undefined)
211}
212
213fn push_insert(ops: &mut Vec<TextDeltaOp>, insert: TextInsert, attrs: &TextAttributes) {
214 let format = if attrs.is_empty() { None } else { Some(attrs.clone()) };
215
216 if let Some(TextDeltaOp::Insert {
217 insert: TextInsert::Text(prev),
218 format: prev_format,
219 }) = ops.last_mut()
220 && let TextInsert::Text(text) = insert
221 {
222 if prev_format.as_ref() == format.as_ref() {
223 prev.push_str(&text);
224 return;
225 }
226 ops.push(TextDeltaOp::Insert {
227 insert: TextInsert::Text(text),
228 format,
229 });
230 return;
231 }
232
233 ops.push(TextDeltaOp::Insert { insert, format });
234}
235
236fn advance_text_position(store: &mut DocStore, pos: &mut TextPosition, mut remaining: u64) -> JwstCodecResult {
237 while remaining > 0 {
238 let Some(item) = pos.right.get() else {
239 return Err(JwstCodecError::IndexOutOfBound(pos.index + remaining));
240 };
241
242 if item.deleted() {
243 pos.forward();
244 continue;
245 }
246
247 if matches!(item.content, Content::Format { .. }) {
248 pos.forward();
249 continue;
250 }
251
252 let item_len = item.len();
253 if remaining < item_len {
254 let (left, right) = store.split_node(item.id, remaining)?;
255 pos.left = left.as_item();
256 pos.right = right.as_item();
257 pos.index += remaining;
258 break;
259 }
260
261 remaining -= item_len;
262 pos.forward();
263 }
264
265 Ok(())
266}
267
268fn minimize_attribute_changes(pos: &mut TextPosition, attrs: &TextAttributes) {
269 loop {
270 let Some(item) = pos.right.get() else {
271 break;
272 };
273
274 if item.deleted() {
275 pos.forward();
276 continue;
277 }
278
279 if let Content::Format { key, value } = &item.content {
280 let attr = attrs.get(key.as_str()).cloned().unwrap_or(Any::Null);
281 if attr == *value {
282 pos.forward();
283 continue;
284 }
285 }
286
287 break;
288 }
289}
290
291fn insert_item(store: &mut DocStore, ty: &mut YType, pos: &mut TextPosition, content: Content) -> JwstCodecResult {
292 if let Some(markers) = &ty.markers
293 && content.countable()
294 {
295 markers.update_marker_changes(pos.index, content.clock_len() as i64);
296 }
297
298 let item = store.create_item(
299 content,
300 pos.left.clone(),
301 pos.right.clone(),
302 Some(Parent::Type(pos.parent.clone())),
303 None,
304 );
305 let item_ref = item.clone();
306 store.integrate(Node::Item(item), 0, Some(ty))?;
307 pos.right = item_ref;
308 pos.forward();
309
310 Ok(())
311}
312
313fn insert_attributes(
314 store: &mut DocStore,
315 ty: &mut YType,
316 pos: &mut TextPosition,
317 attrs: &TextAttributes,
318) -> JwstCodecResult<TextAttributes> {
319 let mut negated = TextAttributes::new();
320
321 for (key, value) in attrs {
322 let current = pos.attrs.get(key.as_str()).cloned().unwrap_or(Any::Null);
323 if current == *value {
324 continue;
325 }
326
327 negated.insert(key.to_string(), current);
328 insert_item(
329 store,
330 ty,
331 pos,
332 Content::Format {
333 key: key.to_string(),
334 value: value.clone(),
335 },
336 )?;
337 }
338
339 Ok(negated)
340}
341
342fn insert_negated_attributes(
343 store: &mut DocStore,
344 ty: &mut YType,
345 pos: &mut TextPosition,
346 mut negated: TextAttributes,
347) -> JwstCodecResult {
348 loop {
349 let Some(item) = pos.right.get() else {
350 break;
351 };
352
353 if item.deleted() {
354 pos.forward();
355 continue;
356 }
357
358 if let Content::Format { key, value } = &item.content
359 && let Some(negated_value) = negated.get(key.as_str())
360 && negated_value == value
361 {
362 negated.remove(key.as_str());
363 pos.forward();
364 continue;
365 }
366
367 break;
368 }
369
370 for (key, value) in negated {
371 insert_item(
372 store,
373 ty,
374 pos,
375 Content::Format {
376 key: key.to_string(),
377 value,
378 },
379 )?;
380 }
381
382 Ok(())
383}
384
385fn insert_text_content(
386 store: &mut DocStore,
387 ty: &mut YType,
388 pos: &mut TextPosition,
389 content: Content,
390 mut attrs: TextAttributes,
391) -> JwstCodecResult {
392 for key in pos.attrs.keys() {
393 if !attrs.contains_key(key.as_str()) {
394 attrs.insert(key.to_string(), Any::Null);
395 }
396 }
397
398 minimize_attribute_changes(pos, &attrs);
399 let negated = insert_attributes(store, ty, pos, &attrs)?;
400 insert_item(store, ty, pos, content)?;
401 insert_negated_attributes(store, ty, pos, negated)?;
402
403 Ok(())
404}
405
406fn format_text(
407 store: &mut DocStore,
408 ty: &mut YType,
409 pos: &mut TextPosition,
410 mut remaining: u64,
411 attrs: TextAttributes,
412) -> JwstCodecResult {
413 if remaining == 0 {
414 return Ok(());
415 }
416
417 minimize_attribute_changes(pos, &attrs);
418 let mut negated = insert_attributes(store, ty, pos, &attrs)?;
419
420 while remaining > 0 {
421 let Some(item) = pos.right.get() else {
422 break;
423 };
424
425 if item.deleted() {
426 pos.forward();
427 continue;
428 }
429
430 match &item.content {
431 Content::Format { key, value } => {
432 if let Some(attr) = attrs.get(key.as_str()) {
433 if attr == value {
434 negated.remove(key.as_str());
435 } else {
436 negated.insert(key.to_string(), value.clone());
437 }
438 store.delete_item(item, Some(ty));
439 pos.forward();
440 } else {
441 pos.forward();
442 }
443 }
444 _ => {
445 let item_len = item.len();
446 if remaining < item_len {
447 store.split_node(item.id, remaining)?;
448 remaining = 0;
449 } else {
450 remaining -= item_len;
451 }
452 pos.forward();
453 }
454 }
455 }
456
457 insert_negated_attributes(store, ty, pos, negated)?;
458
459 Ok(())
460}
461
462fn delete_text(store: &mut DocStore, ty: &mut YType, pos: &mut TextPosition, mut remaining: u64) -> JwstCodecResult {
463 if remaining == 0 {
464 return Ok(());
465 }
466
467 let start = remaining;
468
469 while remaining > 0 {
470 let item_ref = pos.right.clone();
471 let Some((indexable, item_len, item_id)) = item_ref.get().map(|item| (item.indexable(), item.len(), item.id))
472 else {
473 break;
474 };
475
476 if indexable {
477 if remaining < item_len {
478 store.split_node(item_id, remaining)?;
479 remaining = 0;
480 } else {
481 remaining -= item_len;
482 }
483
484 if let Some(item) = item_ref.get() {
485 store.delete_item(item, Some(ty));
486 }
487 }
488
489 pos.forward();
490 }
491
492 if let Some(markers) = &ty.markers {
493 markers.update_marker_changes(pos.index, -((start - remaining) as i64));
494 }
495
496 Ok(())
497}
498
499#[cfg(test)]
500mod tests {
501 use rand::{Rng, SeedableRng};
502 use rand_chacha::ChaCha20Rng;
503 use yrs::{Options, Text, Transact};
504
505 use super::{TextAttributes, TextDeltaOp, TextInsert};
506 #[cfg(not(loom))]
507 use crate::sync::{Arc, AtomicUsize, Ordering};
508 use crate::{Any, Doc, loom_model, sync::thread};
509
510 #[test]
511 fn test_manipulate_text() {
512 loom_model!({
513 let doc = Doc::new();
514 let mut text = doc.create_text().unwrap();
515
516 text.insert(0, "llo").unwrap();
517 text.insert(0, "he").unwrap();
518 text.insert(5, " world").unwrap();
519 text.insert(6, "great ").unwrap();
520 text.insert(17, '!').unwrap();
521
522 assert_eq!(text.to_string(), "hello great world!");
523 assert_eq!(text.len(), 18);
524
525 text.remove(4, 4).unwrap();
526 assert_eq!(text.to_string(), "helleat world!");
527 assert_eq!(text.len(), 14);
528 });
529 }
530
531 #[test]
532 #[cfg(not(loom))]
533 fn test_parallel_insert_text() {
534 let seed = rand::thread_rng().r#gen();
535 let rand = ChaCha20Rng::seed_from_u64(seed);
536 let mut handles = Vec::new();
537
538 let doc = Doc::with_client(1);
539 let mut text = doc.get_or_create_text("test").unwrap();
540 text.insert(0, "This is a string with length 32.").unwrap();
541
542 let added_len = Arc::new(AtomicUsize::new(32));
543
544 {
546 for i in 0..2 {
547 let mut text = text.clone();
548 let mut rand = rand.clone();
549 let len = added_len.clone();
550
551 handles.push(thread::spawn(move || {
552 for j in 0..10 {
553 let pos = rand.gen_range(0..text.len());
554 let string = format!("hello {}", i * j);
555
556 text.insert(pos, &string).unwrap();
557
558 len.fetch_add(string.len(), Ordering::SeqCst);
559 }
560 }));
561 }
562 }
563
564 {
566 for i in 0..2 {
567 let doc = doc.clone();
568 let mut rand = rand.clone();
569 let len = added_len.clone();
570
571 handles.push(thread::spawn(move || {
572 let mut text = doc.get_or_create_text("test").unwrap();
573 for j in 0..10 {
574 let pos = rand.gen_range(0..text.len());
575 let string = format!("hello doc{}", i * j);
576
577 text.insert(pos, &string).unwrap();
578
579 len.fetch_add(string.len(), Ordering::SeqCst);
580 }
581 }));
582 }
583 }
584
585 for handle in handles {
586 handle.join().unwrap();
587 }
588
589 assert_eq!(text.to_string().len(), added_len.load(Ordering::SeqCst));
590 assert_eq!(text.len(), added_len.load(Ordering::SeqCst) as u64);
591 }
592
593 #[cfg(not(loom))]
594 fn parallel_ins_del_text(seed: u64, thread: i32, iteration: i32) {
595 let doc = Doc::with_client(1);
596 let rand = ChaCha20Rng::seed_from_u64(seed);
597 let mut text = doc.get_or_create_text("test").unwrap();
598 text.insert(0, "This is a string with length 32.").unwrap();
599
600 let mut handles = Vec::new();
601 let len = Arc::new(AtomicUsize::new(32));
602
603 for i in 0..thread {
604 let len = len.clone();
605 let mut rand = rand.clone();
606 let text = text.clone();
607 handles.push(thread::spawn(move || {
608 for j in 0..iteration {
609 let len = len.clone();
610 let mut text = text.clone();
611 let ins = i % 2 == 0;
612 let pos = rand.gen_range(0..16);
613
614 if ins {
615 let str = format!("hello {}", i * j);
616 text.insert(pos, &str).unwrap();
617
618 len.fetch_add(str.len(), Ordering::SeqCst);
619 } else {
620 text.remove(pos, 6).unwrap();
621
622 len.fetch_sub(6, Ordering::SeqCst);
623 }
624 }
625 }));
626 }
627
628 for handle in handles {
629 handle.join().unwrap();
630 }
631
632 assert_eq!(text.to_string().len(), len.load(Ordering::SeqCst));
633 assert_eq!(text.len(), len.load(Ordering::SeqCst) as u64);
634 }
635
636 #[test]
637 #[cfg(not(loom))]
638 fn test_parallel_ins_del_text() {
639 parallel_ins_del_text(973078538, 2, 2);
642 parallel_ins_del_text(18414938500869652479, 2, 2);
643 }
644
645 #[test]
646 fn loom_parallel_ins_del_text() {
647 let seed = rand::thread_rng().r#gen();
648 let mut rand = ChaCha20Rng::seed_from_u64(seed);
649 let ranges = (0..20).map(|_| rand.gen_range(0..16)).collect::<Vec<_>>();
650
651 loom_model!({
652 let doc = Doc::new();
653 let mut text = doc.get_or_create_text("test").unwrap();
654 text.insert(0, "This is a string with length 32.").unwrap();
655
656 let handles = (0..2)
658 .map(|i| {
659 let text = text.clone();
660 let ranges = ranges.clone();
661 thread::spawn(move || {
662 let mut text = text.clone();
663 let ins = i % 2 == 0;
664 let pos = ranges[i];
665
666 if ins {
667 let str = format!("hello {}", i);
668 text.insert(pos, &str).unwrap();
669 } else {
670 text.remove(pos, 6).unwrap();
671 }
672 })
673 })
674 .collect::<Vec<_>>();
675
676 for handle in handles {
677 handle.join().unwrap();
678 }
679 });
680 }
681
682 #[test]
683 #[cfg_attr(miri, ignore)]
684 fn test_recover_from_yjs_encoder() {
685 let yrs_options = Options {
686 client_id: rand::random(),
687 guid: nanoid::nanoid!().into(),
688 ..Default::default()
689 };
690
691 loom_model!({
692 let binary = {
693 let doc = yrs::Doc::with_options(yrs_options.clone());
694 let text = doc.get_or_insert_text("greating");
695 let mut trx = doc.transact_mut();
696 text.insert(&mut trx, 0, "hello");
697 text.insert(&mut trx, 5, " world!");
698 text.remove_range(&mut trx, 11, 1);
699
700 trx.encode_update_v1()
701 };
702 #[allow(clippy::needless_borrow)]
704 let doc = Doc::try_from_binary_v1(binary).unwrap();
705 let mut text = doc.get_or_create_text("greating").unwrap();
706
707 assert_eq!(text.to_string(), "hello world");
708
709 text.insert(6, "great ").unwrap();
710 text.insert(17, '!').unwrap();
711 assert_eq!(text.to_string(), "hello great world!");
712 });
713 }
714
715 #[test]
716 fn test_recover_from_octobase_encoder() {
717 loom_model!({
718 let binary = {
719 let doc = Doc::new();
720 let mut text = doc.get_or_create_text("greating").unwrap();
721 text.insert(0, "hello").unwrap();
722 text.insert(5, " world!").unwrap();
723 text.remove(11, 1).unwrap();
724
725 doc.encode_update_v1().unwrap()
726 };
727
728 let doc = Doc::try_from_binary_v1(binary).unwrap();
729 let mut text = doc.get_or_create_text("greating").unwrap();
730
731 assert_eq!(text.to_string(), "hello world");
732
733 text.insert(6, "great ").unwrap();
734 text.insert(17, '!').unwrap();
735 assert_eq!(text.to_string(), "hello great world!");
736 });
737 }
738
739 #[test]
740 fn test_text_delta_insert_format() {
741 loom_model!({
742 let doc = Doc::new();
743 let mut text = doc.get_or_create_text("text").unwrap();
744
745 let mut attrs = TextAttributes::new();
746 attrs.insert("bold".to_string(), Any::True);
747
748 text.apply_delta(&[TextDeltaOp::Insert {
749 insert: TextInsert::Text("abc".to_string()),
750 format: Some(attrs.clone()),
751 }])
752 .unwrap();
753
754 assert_eq!(text.to_string(), "abc");
755 assert_eq!(
756 text.to_delta(),
757 vec![TextDeltaOp::Insert {
758 insert: TextInsert::Text("abc".to_string()),
759 format: Some(attrs),
760 }]
761 );
762 });
763 }
764
765 #[test]
766 fn test_text_delta_retain_format() {
767 loom_model!({
768 let doc = Doc::new();
769 let mut text = doc.get_or_create_text("text").unwrap();
770
771 text.apply_delta(&[TextDeltaOp::Insert {
772 insert: TextInsert::Text("abc".to_string()),
773 format: None,
774 }])
775 .unwrap();
776
777 let mut attrs = TextAttributes::new();
778 attrs.insert("bold".to_string(), Any::True);
779
780 text.apply_delta(&[TextDeltaOp::Retain {
781 retain: 1,
782 format: Some(attrs.clone()),
783 }])
784 .unwrap();
785
786 assert_eq!(
787 text.to_delta(),
788 vec![
789 TextDeltaOp::Insert {
790 insert: TextInsert::Text("a".to_string()),
791 format: Some(attrs),
792 },
793 TextDeltaOp::Insert {
794 insert: TextInsert::Text("bc".to_string()),
795 format: None,
796 }
797 ]
798 );
799 });
800 }
801
802 #[test]
803 fn test_text_delta_utf16_retain() {
804 loom_model!({
805 let doc = Doc::new();
806 let mut text = doc.get_or_create_text("text").unwrap();
807
808 text.apply_delta(&[TextDeltaOp::Insert {
809 insert: TextInsert::Text("😀".to_string()),
810 format: None,
811 }])
812 .unwrap();
813
814 let mut attrs = TextAttributes::new();
815 attrs.insert("bold".to_string(), Any::True);
816
817 text.apply_delta(&[TextDeltaOp::Retain {
818 retain: 2,
819 format: Some(attrs.clone()),
820 }])
821 .unwrap();
822
823 assert_eq!(
824 text.to_delta(),
825 vec![TextDeltaOp::Insert {
826 insert: TextInsert::Text("😀".to_string()),
827 format: Some(attrs),
828 }]
829 );
830 });
831 }
832}